Data structure (module 3)

MODULE III
1. Write a C function to insert_front and delete_front using Doubly Linked List(8)
2. Write a c function for concatenation of two doubly linked list(5)
3. Describe the doubly linked list with advantages and disadvantages. Write a c function to
delete a node from a circular doubly linked list with header node(8)
4. For the given sparse matrix, write the diagrammatic linked list representation(4)
3000
5006
A 0000
4008
0090
5. What is a tree. With suitable example define (10)
a. Binary tree
b. Complete binary tree
c. Level of the binary tree
d. Degree of the tree
e. Strictly binary tree
f. Skewed binary tree
6. Consider the following tree T. Write the in-order, pre-order and post-order traversals for
the tree T along with C functions. Also find the depth of the tree T(10)

A


B C




D G H
E



J K


7. Give the following traversal, draw a binary tree
a. Inorder:4 2 5 1 6 7 3 8 L
Postorder: 4 5 2 6 7 8 3 1
b. Preorder: A B C E I F J D G H K L
Inorder: E I C F J B G D K H L
8. Represent the below given tree in A
a. Linked list representation
b. Left child right sibling representation B D
C



E G H
F



I



J K

,9. Define Threaded binary tree. List its advantages and disadvantages. Draw the one way
threading and two way threading of the following binary tree (8)
A

B C



D F G
E
G

H
10. Explain threaded binary trees and their representation with a neat diagram. Also develop a
C function to do the in-order traversal of a Threaded binary tree(8)
11. Draw the binary tree for the following expression: ((6+(3-2)*5)^2+3. Traverse the above
generated tree using in-order, pre-order and post-order traversals and also write their
respective functions(10)
12. Define expression tree. For the given tree traverse using in-order, pre-order and post-order
traversals.(7)
+

*



*
+




B *



C
E



D

13. Outline the steps involved in construction of expression tree. Construct expression tree for
the following input: AB+C* (10)
14. Write the routines for(10)
a. Copying of Binary trees
b. Testing equality of binary trees

, 1. Write a C function to insert_front and delete_front using Doubly Linked List(8)
Doubly Linked List
• A doubly linked list or a two-way linked list is a more complex type of linked list which
contains a pointer to the next as well as the previous node in the sequence.
• Each node has three parts
• data – contains data element
• next – contains the address of the next node in the list
• prev - contains the address of the preceding node in the list




Insert Front
struct node *insert_beg(struct node *start)
{
struct node *new_node;
int num;
printf("\n Enter the data : ");
scanf("%d", &num);
new_node = (struct node *)malloc(sizeof(struct node));
new_node -> data = num;
start -> prev = new_node;
new_node -> next = start;
new_node -> prev = NULL;
start = new_node;
return start;
}

Delete Front
struct node *delete_beg(struct node *start)
{
struct node *ptr;
ptr = start;
start = start -> next;
start -> prev = NULL;
free(ptr);
return start;
}

2. Write C function for the concatenation of two doubly linked lists. (5marks)
C Function to concatenate two doubly linked lists
void concatenate()
{
struct node *link;