SKR Engineering College 2007 B.E Computer Science CS1211 - DATA STRUCTURES - Question Paper

SKR Engineering College
DEPARTMENT OF ELECTRICAL AND ELECTRONICS ENGINEERING
MODEL ques. PAPER
CS1211 - DATA STRUCTURES
II YEAR/III SEMESTER

PART-A

1. What is the structure of 2 dimensional arrays in C?
2. What are the kinds of data structure
3. State the properties of binary tree
4. What is the time complexity of bubble sort?
5. Compare linear and binary search
6. What are the factors to be considered while choosing a sorting technique?
7. What is polynomial and exponential?
8. Write the avg. and best case analysis of insertion sort
9. What is AVL tree?
10. What is queue?
11. Define terminal node, degree of a node, sibling, depth of a node

PART-B

11.a(i) Write an program to perform matrix multiplication. (6)
(ii) discuss the recursion in C (10)

(OR)

b(i) discuss the concept of Arrays (8)
(ii) define the different data types (8)


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

(OR)

b.Explain the inserting and deleting node from linked list implementing stack and queue. (16)


13 a(i) discuss the operation of AVL tree (8)
(ii) Write a procedure for the subsequent operation
Ø Inserting a new element
Ø Deleting a element (8)

(OR)

b(i) discuss the threaded binary tree (8)
(ii) discuss the preorder and postorder traversal of a binary tree (8)


14.a(i)Write down the procedure to convert an infix expression a+b*c+(d*e+f)*g (8)
(ii) discuss the topological sorting algorithm (8)

(OR)

b(i) Trace the quick sort algorithm for the subsequent list of numbers
86,55,75,32,58,89,90,78 (12)
(ii) Distinguish internal and external sorting (2)


15 a(i) Write an algorithm to obtain the shortest path ranging from any 2 nodes in a graph using Dijikstra’s algorithm (16)
(OR)

b Write down the depth 1st traversal algorithm and breath 1st traversal. (16)

























SKR Engineering College
DEPARTMENT OF ELECTRICAL AND ELECTRONICS ENGINEERING
MODEL ques. PAPER
CS1211 - DATA STRUCTURES
II YEAR/III SEMESTER

PART-A

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

PART-B

11.a(i) Write about the pointers in C (8)
(ii)Explain in detail about the function. (8)

(OR)

b(i) How is the implementation of structure done in C (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) describe an efficient representation of 2 STACKS in a provided area of memory with ‘n’ words and discuss (10)

(OR)

b(i) discuss in detail about insertion and deletion of elements in the doubly linked list
(16)


13 a(i) elaborate the various tree traversals? discuss with examples (8)
(ii)How do you insert an element in a binary tree (8)

(OR)

b(i)Explain the operation of AVL tree (8)
(ii)Using recursive procedure, discuss the operation of post order and pre order traversal of binary tree. (8)


14.a(i)Write the procedure for insertion sort. (8)
(ii)Sort the subsequent array using insertion sort
25,30,66,99,54,28,13,58 (8)

(OR)

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


15.a,(i)Explain the Prim’s algoritm (8)
(ii)Define unweighted shortest path (4)
(iii)Explain the following: Degree, Complete graph (4)

(OR)

b(i)Explain the Krusal’s algorithm (8)
(ii)Give a few applications of depth 1st traversal (8)

Earning:   Approval pending.