SKR Engineering College 2007 B.E Computer Science CS 1151 – Data Structures - Question Paper

SKR Engineering College
Department Of Computer Science & Engineering
Model ques. Paper
CS 1151 – Data Structures


PART-A 2*10=20

1. Give the prefix form of infix expression (A*B+(C/D))-E
2. State the properties of binary tree
3. What is the time complexity of insertion sort?
4. Compare linear and binary search
5. What are the factors to be considered while choosing a sorting technique?
6. What is NP complete problem?
7. Write the avg. and best case analysis of heap sort
8. What is AVL tree?
9. What is dequeue?
10. Define terminal node, degree of a node, sibling, depth of a node

PART-B 5*16=80

11.a(i) Write an algorithm to perform matrix multiplication and analyze the identical. (6)
(ii) discuss the complete Merge sort algorithm. Sort the subsequent set of numbers
Using Merge sort algorithm (10)

(OR)

b(i) discuss the concept of Top-down approach (8)
(ii) define the different operations of Stack. List its applications (8)

12 a(i) discuss the operation of AVL tree (8)
(ii) Write a procedure for the subsequent Linked list operation
Ø Inserting a new node at the end
Ø Deleting a node from the beginning (8)

(OR)

b(i) Trace the quick sort algorithm for the subsequent list of numbers
86,55,75,32,58,89,90
(ii) discuss the preorder and post order traversal of a binary tree (8)

13 a(i) discuss the Dijikstra’s algorithm with an example (8)
(ii) discuss the topological sorting algorithm (8)

(OR)

b(i)Explain in detail the kinds of analysis that can be performed on an algorithm (8)

(ii) elaborate strongly connected components? Explain (6)
(iii) Distinguish internal and external sorting (2)

14 a(i) Write an algorithm to obtain the shortest path ranging from any 2 nodes in a graph using Dijikstra’s algorithm (10)
(ii) describe and discuss Quick sort (6)

(OR)
b Write down the merge sort algorithm and provide its worst case, best case and
avg. case analysis (16)

15(a) Show the heap sort processes the input 12,56,89,41,23,45,65,78,2,69,35,49 (16)

(OR)
b(i) Write down the procedure to convert an infix expression a+b*c+(d*e+f)*g (12)
(ii) obtain the avg. search cost of the binary search algorithm (4)























SKR Engineering College
Department Of Computer Science & Engineering
Model ques. Paper
CS 1151 – Data Structures

PART-A 2*10=20

1. What is a graph?
2. What are the benefits of doubly linked list over singly linked list?
3. Define priority queue
4. How do you represent a graph in multi-list organization?
5. Write an algorithm for fibonacci series
6. What are the factor that is involved in radix sort?
7. Write the different kinds of control structures
8. Define complete binary tree
9. Explain Kruskal’s algorithm
10. What do you mean by Abstract Data Type?

PART-B 16*5=80

11 a(i) Write algorithm to locate an element from binary search tree (6)
(ii) describe an efficient representation of 2 STACKS in a provided area of memory with ‘n’ words and discuss (10)

(OR)

b(i) elaborate the various tree traversals? discuss with examples (8)
(ii) discuss an algorithm to convert a hexadecimal to decimal representation
(8)

12 a(i) discuss in detail about the operation of queue (6)
(ii) define the different hash functions (6)
(iii) discuss unweighted shortest path (4)

(OR)

12 b(i) What is biconnectivity (4)
(ii) discuss the prim’s algorithm with an example (6)
(iii) Construct the heap for the subsequent array structure
15 85 12 23 60

13 a(i) elaborate strongly connected components? Explain (6)
(ii) discuss the concept of Top-down approach (6)
(iii) discuss any 1 of the sorting techniques (4)

(OR)

b(i) discuss how to replace Dijikstra’s algorithm to produce a count of the number of various minimum paths from v to w (8)
(ii) discuss program verification with example (8)

14 a(i) Briefly discuss the need of time complexity in an analysis of algorithms
(4)
(ii) discuss Topological Sorting with examples (4)
(iii) How the efficiency of an algorithm is computed. discuss it with an example
(8)

(OR)

b(i) provided 2 sorted lists L1 and L2 write a procedure to calculate L1 Ç L2 using
Only the basic operations

15 a(i) discuss the algorithm for insertion and deletion (8)
(ii) Devise an algorithm to evaluate the postfix expression (8)

(OR)

b(i) discuss Separate chaining and Open addressing in detail (8)
(ii) Write a procedure to sort the set of ‘n’ numbers using insertion sort algorithm
(8)

Earning:   Approval pending.