FOURTH SEMESTER DIPLOMA EXAMINATION IN ENGINEERING/TECHNOLOGY-MARCH, 2009
DATA STRUCTURES
PART-A
(Maximum marks:15)
v Answer the following questions in one or two sentences:
1.Define pointer.
2.What is a structure?
3.Identify the number of comparisons required for binary search to find the element 60 in the list given:
12
|
16
|
20
|
35
|
42
|
47
|
50
|
55
|
60
|
65
|
4.Give two sorting techniques which apply divide and conquer method to sort a list.
5.Write about the best,worst and average performance of the linear search.
6.What output will be produced by the following C code?Node is a self referential structure with a member named data.
Void fun(struct node *f)
{
Struct node q=f,p=NULL;
While(q!=p)
{
Printf(“%d”,q->data);
Q=q->link;
};
7.Write the prefix notation of(2+7)*(8/6-(3+1))).
8.List two applications of the datastructure queue.
9.Write about ‘degree of a node’.
10.Draw a tree to represent the expression(5-x)*y+6/(x+z)
PART-B
(Maximum marks:60)
(Answer one full question from each unit)
Unit-1
v (a)Write a recursive function in C language to reverse a string.(8)
(b)Give the pointer representation of a two dimensional array.Explain how the array elements are processed.(6)
OR
v (a)Compares structure and union.(6)
(b)Write notes on: (i)Passing structure to pointers
(ii)Pointer to pointer.(6)
Unit-2
v (a)Write an algorithm for bubble sort.(7)
(b)Trace the execution of quick sort algorithm on the list given below:
65
|
70
|
75
|
80
|
85
|
60
|
(5)
OR
v (a)Explain merge sort with example.(7)
(b)Compare linear search and binary search.(5)
UNIT-3
v (a)Explain the operations insert and delete performed on singly linked list.(6)
(b)Write an algorithm to search an element in the linked list.(6)
OR
v (a)Explain doubly linked list with example.(6)
(b)Write about the operations performed on it.(6)
UNIT-4
v (a)Illustrate with suitable diagram the evaluation of the expression:
*
|
+
|
2
|
7
|
/
|
8
|
+
|
-
|
6
|
3
|
1
|
(7)
(b)Write an algorithm to implement push operation on a stack.(5)
OR
v (a)Define queue.Explain the operations performed on queue.(6)
(b)Write notes on(i)dqueue (ii)priority queue.(6)
UNIT-5
v (a)Write a recursive procedure for inorder traversals of binary tree.(6)
(b)Write about the binary search tree.(6)
OR
v Explain Dijkstra algorithm to find shortest path.(12)
0 comments:
Post a Comment