3.3: Unit Summary
- Page ID
- 48202
\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \) \( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)\(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\) \(\newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\) \( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\) \( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\) \( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\) \( \newcommand{\Span}{\mathrm{span}}\)\(\newcommand{\AA}{\unicode[.8,0]{x212B}}\)
This unit covered data structures and abstract data types. In the data structures section, different structures were discussed. These included arrays, links, Linked lists, Stacks, Queues, Hashing and Trees. These structures are used to organize data in the computer to make it work efficiently. In the abstract data types section, the operations performed on the data structures are discussed.
Check your understanding!
Question and answer session
Instructions
Answer all the questions and test your grasp of the unit.
- Differentiate between Abstract Data Type, Data Type and Data Structure.
- What is a tree as learned in computer science?
- Give two importance of hashing.
- State the difference between arrays and linked lists.
- In tree construction which is the suitable efficient data structure? (Array, Linked list, Stack, Queue)
- What is a spanning Tree?
- Feedback
-
- An abstract data type is the specification of the data type which specifies the logical and mathematical model of the data type.
- A data type is the implementation of an abstract data type.
- Data structure refers to the collection of computer variables that are connected in some specific manner .i.e) Data type has its root in the abstract data type and a data structure comprises a set of computer variables of same or different data types.
- A tree is a collection of nodes. The collection can be empty; otherwise, a tree consists of a distinguished node r, called the root, and zero or more non empty (sub) trees T1, T2,…,Tk, each of whose roots are connected by a directed edge from r.
- The importance of hashing.
- Maps key with the corresponding value using hash function.
- Hash tables support the efficient addition of new entries and the time spent on searching for the required data is independent of the number of items stored.
- The difference between arrays and linked lists:
- Size of an array is fixed
- Size of a list is variable in a linked list
- It is necessary to specify the number of elements during declaration in an array
- It is not necessary to specify the number of elements during declaration in a linked list
- Linked list is the suitable efficient data structure.
- A spanning tree is a tree associated with a network. All the nodes of the graph appear on the tree once. A minimum spanning tree is a spanning tree organized so that the total edge weight between nodes is minimized.
- An abstract data type is the specification of the data type which specifies the logical and mathematical model of the data type.
Grading Scheme
The marks will be awarded as shown below:
| Question | Scores (marks) |
|---|---|
| 1 | 2 |
| 2 | 2 |
| 3 | 4 |
| 4 | 4 |
| 5 | 2 |
| 6 | 2 |
| Total | 16 |
Unit Readings and Other Resources
The readings in this unit are to be found at course level readings and other resources.