2012 University of Delhi B.Sc Computer Science (Honours) B.Sc Comp Sci(hon) 1st year data structure delhi university University Question paper
B.SC. (hONS.) COMPUTER SCIENCE /2ND Sem Paper CSHT 203 : Data Structures Time: 3 Hours Maximum Marks :75
Question 1 is compulsory. Attempt any four questions out of the remaining Q2Q7. Parts of a question must be anwered together. 1. (a) Write an algorith that examines whether each occurence of delimiter is matched with a corresponding delimiter in a string,say,s.The algorithm should return true if all delimiters are Matched and false otherwise. The delimiter to be matvhed may be {, [, ( against }, ], ) respectively. (5) (b) Define a class for implementing Queue of data type X(using arrays) and size s. Write a statement to create a queue of integers of size 10. Details of the methods are not required. X is a generic data type. (5) (c) Consider a list of unsorted elements. An application requires frequent insertions and deletions. Which of the two data structures array and linked list should be used and why? (5) (d) Consider the following triangular matrix: 6 0 0 0 2 5 0 0 9 0 1 0 7 3 8 0 Show how the elements will be stored in one dimensional array in row major order and coulmn major order? (5)
(e) Deine a class to represent a node of Binary Tree. Traverse the following tree rooted at A, in preorder, inorder,postorder.(5) (f) A function h(n) is defined recursilvely as h(n)=0, if n=0 h(n)=n, ifn>4 h(n)=h(n +h(2*n)) if n<=4 find the value of h(1) and h(5). (5) (g) Consider the following array with exactly 15 elements: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 Suppose binary search is applied or searching an elements. Find the elements, that can be found in binary search by examining one or two elements from the array. How many comparisions will be done for searching 16 in the above array.(5)
2. (a) Write a function merge that merges two sorted linked lists arranged in ascending order. (5) (b) What is an activation record? What all information is stored in activation record ? When are they allocated memory and where?(5) 3.(a) Show the contents of stack after each operation when the following postfix expression is evaluated : ABC+*CBA+* where A=5,B=6 and C=4 (5) (B) A linked list is represented using head and tail pointers. The following operations are applied on an empty linked list L L.add_at_head(4) L.add_at_head(6) L.add_at_tail(7) L.delete(7) L.delete_from_tail() Show the stayus of linked list after each opearation. (5) 4. (a) Suppose a skip list has 18 nodes. How many nodes will be there having one pointer, two pointers, three pointers,four pointers? What is the maximum level of node in this skip list? (5) (b) Draw a hash table with open addressing and a size of 11. Use of hash function "k%9" and linear probing for collision. Insert the keys: 5, 29, 20, 0, 27 and 18 into your table(in that order).(5) 5.(a) Write an algorithm that seaches for a number X in a binary seach Tree. It should throw an exception if element is not found.(5) (b) Create a rightinthreaded binary search tree using the following data: 25, 10, 11, 65, 12, 15, 70, 80 Show the tree after each insertion (show all the threads and child).(5) 6.(a)Define a class to store 2Dmatrix using 1D array.Define constructor and overload operator) to store and retreive the i,jth element.(6) (b) Write an algorith to insert a node at the end of a doubly linked list.(4) 7.(a) Write a function to count the number of leaf nodes in Binary Tree.(5) (b) Consider the following Btree with order 5.Delete H,T and R from the following tree. Show the status of Btree after each deletion.
Attachments:
Return to question paper search
