Difference- Singly and Doubly Linked Circullar List [CS62 june 2001]

Queastion: 2(b) List the difference between a Singly Linked Circular List and Doubly Linked Circular List. List the advantages of each list.

Answer: In single linked circular list one cannot traverse a list backward, nor can a node be deleted from a circularly linked list, given only a pointer to that node. Whereas in double linked list each node in such a list contains two pointers, one to its predecessores and another its successor. Deleting a given node is possible in double linked list whereas it is not possible in simple linked lists.

Binary Search Tree -CS62 june 2001

Queation: 1.(c): Define binary search tree. Write a function in C to creat a binary search tree.
Answer: A binary search has porperty that all elements in the left subtree of a node n are less than the contents of n and alll elements in the sight subtree of n are greater than or equal to the contents of n.
If a binary search tree is traversed in inorder (left, root, sight) and the contents of each node are printed as the node is visited, the numbers as the node is visited, the numbers are printed in ascending order.
q=null;
p=tree;
while(p!=null){
if (key==k(p))
return(p);
q=p;
if(key
p=left(p);
else
p=right(p);
}
v=maketree(rec,key);
if(q==null)
tree=v;
else
if(key
left(q)=v;
else
right(q)=v;
return(v);

CS62 2001 December 4 (ii) algorithm to implement breadth first search

Question: Write an algorithm / Program to implement breadth first search and also describe the program/algorithm in terms of data structure and its functioning. [CS62, 2001 December, Question 4(ii) ]

Answer:
The algorithm to implement breadth first search is listed below:
Step 1: Initialization of vertices by assigning the vaule 1 to dummy.
Step 2: Place the beginning vertix in Z and set it to halt by assigning 0 to dummy
Step 3: Loop through step 5 until Z becomes NULL.
Step 4: Delete the front vertex of Z. Manipulate the front vertex and set to active state by assigning -1 to dummy.
Step 5: Towards the back of Z, add all the active neighbors of the front vertex y assigning 1 to Dummy, and set them to halt by again assigning 0 to Dummy.
Step 6: Quit