Data Structures Past Paper (Arabic) PDF

# علوم الحاسب ## الفرقة الثانية ### Session 7 ## هياكل البيانات ### Data Structures ## Q.1. Define doubly linked list, state its operations, advantages and disadvantages. Doubly Linked List (DDL) contains an extra pointer, called previous pointer, together with next pointer and data. **Head** - Ne...

# علوم الحاسب ## الفرقة الثانية ### Session 7 ## هياكل البيانات ### Data Structures ## Q.1. Define doubly linked list, state its operations, advantages and disadvantages. Doubly Linked List (DDL) contains an extra pointer, called previous pointer, together with next pointer and data. **Head** - Next - Next - Next - Next - NULL - A - B - C - D - NULL **Prev** - Prev - Prev - Prev - Prev **struct Node** ``` { int data; struct Node* next; struct Node* prev; / }; ``` ### Operations: - **Add a node at the front:** **Head** - Next - Next - Next - Next - ABCD - NULL **Prev** - Next - E - NULL **Prev** - Prev - Prev - Prev - Prev - **Add a node after a given node.** **Head** - Next - Next - Next - NULLL - ABCD - NULL **Prev** - Next - Prev - Prev - E - Prev **Prev** - Next - **Add a node at the end.** **Head** - Next - Next - Next - Next - A - B - C - D - NULL **Prev** - Prev - Prev - Prev - Prev - **Add a node before a given node.** **NEW NODE** - NEXT - PREV - B - PREV - NEXT - NEXT - NEXT - NEXT - NEXT - NULL - A - C - D - PREV - PREV - PREV - HEAD - NEXT NODE 1. Check if the next_node is NULL or not. If it's NULL, return from the function because any new node cannot be added before a NULL. 2. Allocate memory for the new node, let it be called new_node 3. Set new_node->data = new_data 4. Set the previous pointer of this new_node as the previous node of the next_node, ``` new_node->prev = next_node->prev ``` 5. Set the previous pointer of the next_node as the new_node, ``` next_node->prev = new_node ``` 6. Set the next pointer of this new_node as the next_node, ``` new_node->next = next_node; ``` 7. If the previous node of the new_node is not NULL, then set the next pointer of this previous node as new_node, ``` new_node->prev->next = new_node ``` ### Advantages: - A DLL can be traversed in both forward and backward direction. - The delete operation in DLL is more efficient. - We can quickly insert a new node before a given node. ### Disadvantages over singly linked list - Every node of DLL Require extra space for a previous pointer. - All operations require an extra pointer previous to be maintained. - For example, in insertion, we need to modify. ## Q.2. Define Circular Linked List. State its advantages. Circular linked list is a linked list where all nodes are connected to form a circle. There is no NULL at the end. A circular linked list can be a singly circular linked list or doubly circular linked list. **Head** | | |---| | 2 | | 5 | | 7 | | 8 | | 10 | ### Advantages: - Any node can be used as a starting point. - We can traverse the whole list by starting from any point. - We just need to stop when the first visited node is visited again. - Useful for implementation of queue unlike this implementation, we don't need to maintain two pointers for front and rear. - Circular lists are useful in applications to repeatedly go around the list. (e.g., when multiple applications are running on a PC). - Used for implementation of advanced data structures like Fibonacci Heap. ## Q.3. Define binary tree. A tree data structure in which each node has at most two children, referred to as the left child and the right child. The elements of two disjoint binary trees are called the left subtree and right subtree of the root. | | |---| |Left Subtree | B |W | A |X | |S | |T | C |E | |M | 10 |P | Root Node |N | 20 |H | 50 |0 | 30 | | Nodes | | 40 | | 60 | | 70 | | 90 | | 80 | | 25 | | Leaf Node |Right Subtree | **Root** - A - Left Child - B - Level 0 - C - Right Child - Level 1 - parent - D - Siblings - E - F - G - Level 2 - H - I - J - Sub tree - Level 3 - Leaf Node Each root is said to be the parent of the roots of its subtrees. Two nodes with the same parent are said to be siblings. The root node has no parent. Direct edge connects a parent with the child. An undirected edge extends in both directions between a parent and all children. The number of subtrees of a node is called the degree of the node. Degree of all nodes in a binary tree, O or 1 or 2. A node of degree zero is called a terminal node or leaf node. A non-leaf node is often called a branch node or inner node. The degree of a tree is the maximum degree of a node in the tree. A binary tree is degree 2. The length of path is the number of edges on the path, namely k - 1 (the number of nodes – 1). There is a path of length zero from every node to itself. In a binary tree there is exactly one path from the root to each node. The height of ni is the length of the longest path from ni to a leaf, Thus, all leaves in the tree are at height O The height of a tree is equal to the height of the root. The depth of a tree is equal to the level or depth of the deepest leaf; must equal to the height of the tree. If there is a directed path from n1 to n2, then n1 is an ancestor of n2 and n2 is a descendant of n1. | | |---| | depth 0 | height 3 | depth 1 | height 1 | depth 1 | height 2 | depth 2 | height 0 | depth 2 | height 0 | depth 2 | height 1 | root node | inner node | depth 3 | height 0 | leaf node If every non-leaf node in a binary tree has nonempty left and right subtrees, the tree is termed a strictly binary tree. strictly binary tree all the nodes in are of degree zero or two, never degree one. A strictly binary tree with N leaves always contains 2N - 1 nodes. | | |---| | 1 | | 2 | | 3 | | 4 | | 5 | | 6 | | 7 | | 8 | | 9 | A complete binary tree of depth d is the strictly binary tree all whose leaves are at level d. The total number of nodes in a complete binary tree of depth d equals 2d+1 - 1. The tree contains 2d leaves and, therefore, 2d - 1 internal node. There is only a single almost complete binary tree with N nodes, this tree is strictly binary if and only if N is odd. | | |---| | E | | C | | A | | M | | S | | X | | O | ## Q.4. Store the next complete binary trees in an array. If a binary tree is not complete or almost complete, we prefer to use linked list structure. **root** - C - N - M - A - X - Ο For a complete or almost complete binary tree, storing the binary tree as an array may be a good choice. - Store the root of the tree in the first element of the array. - Left child can be stored at subscript 2k+1 - Right child can be stored at subscript 2k+2. | | | |---| ---| |E | [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] |C| A |N| C |M| X | | E | | M | | S | | Ο | | K | | W | | N |A| |X| | | |---| |C | [0] [1] [2] [3] [4] [5] [6] [7] [8] [9] |M| A |A| C | | X |N| M |O| 0 | | N | | 0 ## Q.5. Write the three algorithms for tree traversal. 1. In-order Traversal - Step 1 - Recursively traverse left subtree. - Step 2 - Visit root node. - Step 3 - Recursively traverse right subtree. **D** → **B** → **E** → **A** → **F** → **C** → **G** **Root** | | |---| | 2 | | A | | 3 | | C | | B | | 2 | | 2 | | D | | E | | F | | G | | 3 | | 3 | | Left Subtree | | Right Subtree | 2. Pre-order Traversal - Step 1 - Visit root node. - Step 2 - Recursively traverse left subtree. - Step 3 - Recursively traverse right subtree. **A**→ **B**→ **D** → **E**→ **C** → **F**→ **G** **Root** | | |---| | A | | 2 | | 3 | | B | | 1 | | C | | D | | E | | F | | G | | 2 | | 3 | | 2 | | 3 | | Left Subtree | | Right Subtree | 3. Post-order Traversal - Step 1 - Recursively traverse left subtree. - Step 2 - Recursively traverse right subtree. - Step 3 - Visit root node. **D**→ **E**→ **B**→ **F** → **G** → **C** → **A** **Root** | | |---| | 3 | | A | | 2 | | B | | C | | 3 | | 3 | | D | | E | | F | | G | | 1 | | 2 | | 2 | | Left Subtree | | Right Subtree |