Kurukshetra University 2007 B.Tech Electronics and Communications Engineering Data Structures - Question Paper

DATA STRUCTURES
Paper: CSE-203-E
Time: 3 Hours
Maximum Marks: 100

Note: Attempt any 5 ques.

1. (a) describe abstract data kind and provide any 3 applications of ADTS. [5]

(b) Wnte an algorithm which translates a POSTFIX expression to an INFIX expression. [8]

(c) Show with an example how a UNION is implemented Also differentiate ranging from a UNION and a STRUCTURE in C. [7]

2. (a) Show with an example how an array is passed as a parameter in C. [7]

(b) elaborate the main kinds of PRIORITY QUEUES ? discuss every 1 in detail. [8]

(c) Show how to implement 3 stacks in 1 array. [5]

3. (a) elaborate the advantages and disadvantages of representing a group of items as an array versus a linear line list? [7]

(b) elaborate the steps to inserting a new item at the head of a linked list ? Use 1 short English sentence for every step. [5]

Write a program to swap 2 adjacent elements by adjusting only the pointer (and not the data) using:

(i) Singly linked lists. [4]

(ii) Doubly linked lists. [4]


4.(a) discuss in detail why dynamic data structures are needed. [7]

(b) elaborate the 3 primitive operations that can be applied to Queues ? discuss briefly. [5]

(c) Write an algorithm to reverse the order of items on a list. Prove that your algorithm works correctly. [8]


5.(a) discuss the following:

(i) STRICTLY binary tree. [2]
(ii) Complete binary tree. [2]
(iii) Almost complete binary tree. [2]

(b) The order of nodes of a binary tree id PREOROER and INORDER Traversal are as under :

PREORDER—B C E D F A G H.
INORDER —A B C D E F G H.
Draw the corresponding Binary Tree. [5]

(c) 2 binary trees are similar if they are both empty or both non empty and have similar left and right subtrees. Write a function to decide whether 2 binary trees are similar. [9]

6.(a) Write a note on:

(i) Efficiency of Binary Search tree operations.
(ii) Balanced trees. [5]

(b) Write an algorithm to obtain Kth element of a list represented by a tree and also show that the number of tree nodes examined in finding the Kth list element is less than or equal to one more than the depth of the tree. [7]

(c) elaborate the broad categories of non-binary trees ? define any 1 in detail. [8]

7.(a) Write a non-recursive depth 1st traversal algorithm for graphs. [10]

(b) discuss Prim's algorithm in detail. . [10]

8.(a) What is the purpose of hashing ? define any 1 method used to handle collisions in hashing. [8]

(b) Sort the lists 3, 1, 4, 1. five , 9, two ,6, 5, 3, 5, 8, 9, seven using any 1 of them:

(i) Heapsort.
(ii) Quicksort. [12]

Earning:   Approval pending.