SEMESTER II

CS2201 DATA STRUCTURES TUTORIAL SHEET

DEPARTMENT OF COMPUTER SCIENCE AND ENGINEERING, B. I. T. MESRA

Module – I

1. How can you define algorithms? Discuss structure and properties of algorithms.

2. Define and Classify data structures.

3. How does one measure the efficiency of algorithms?

4. Distinguish between best, worst and average case complexities of an algorithm.

5. Define O, Ω and Θ notations of time complexity.

6. Compare and contrast exponential time complexity with polynomial time complexity.

7. How are recursive programs analyzed?

8. Analyze the time complexity of the following program:

for send = 1 to n do

for receive = 1 to send do

for ack = 2 to receive do

Message = send – (receive + ack);

end

end

end

9. Solve the recurrence relation:

S(n) = 2 • S(n – 1) + b • n, if n > 1

= a, if n = 1

Module – II

10. Distinguish between row major and column major ordering of an array.

11. For an n-dimensional array [1 : u1, 1: u2, … 1 : un] obtain the address of the element A[i1, i2, i3, … in]
given β to be the home address.

12. Declare a one, two and a three-dimensional array in a programming language ( C/C++) which has the
capability to display the addresses of array elements. Verify the various address calculation formulae for
any arbitrary element of these arrays.

13. Open an ordered list L[d1, d2, … dn] where each di is the name of a peripheral device, which is
maintained in the alphabetical order. Write a program to
 a. Insert a device dk onto the list L.

b. Delete an existing device di from L. In this case the new ordered list should be Lnew = (d1, d2,
… di-1, di+1, … dn) with (n – 1) elements.

c. Find the length of L.

d. Update the device dj to dk and print the new list.

14. How are insert operations carried out in a stack?

15. What are demerits of a linear stack?

16. If a stack S[1 : N] were to be implemented with the bottom of the stack at S[N], write a procedure to
undertake push and pop operations on S.

17. For the following logical expression

( a and b and c) or d or e or (not h)

(i) Obtain the equivalent postfix expression.

(ii) Evaluate the postfix expression for a = true, b = false, c = true, d = true, e = true, h = false.

18. Implement a stack S of n elements using arrays. Write functions to perform PUSH and POP operations.
Implement queries using push and pop functions to

a. Retrieve the mth element of the stack S from the top (m < n), leaving the stack without its top
m – 1 elements.

b. Retain only the elements in the odd position of the stack and pop out all even positioned
elements.

19. Write a recursive program to obtain the nth order Fibonacci sequence number. Include appropriate
input/output statements to track the variables participating in recursion.

20. Implement a program to evaluate any given postfix expression. Test your program for the evaluation of
the equivalent postfix form of the expression ( - (A*B)/D) ↑ C + E – F * H * I for A = 1, B = 2, D = 3, C =
14, E = 110, F = 220, H = 16.78, I = 364.621.

21. What are the disadvantages of the linear queues? How do circular queues help overcome the
disadvantages of linear queues?

22. If FRONT and REAR were pointers to the physical front and rear of a linear queue, comment on the
condition, FRONT = REAR.

23. How priority queues are implemented using a single queue?

24. Write a program to maintain a list of items as a circular queue which is implemented using an array.
Simulate insertions and deletions to the queue and display the content of the queue after every operation.

25. Let PQUE be a priority queue data structure and , be n elements with priorities pi (
0 ≤ pi ≤ m – 1). Implement PQUE as a two dimensional array ARR_PQUE[1:m, 1:d] where m is the number
of priority values and d is the maximum number of data items with a given priority. Execute insertions and
deletions presented in a random sequence.
 26. Implement a deque DQUE in a one dimensional array.

Module – III

27. What is the need for linked representation of lists?

28. What are the advantages of circular lists over singly linked lists?

29. What are the advantages and disadvantages of doubly linked lists over singly linked lists?

30. What is the use of a head node in a linked list?

31. What are the conditions for testing a linked list T is empty, if T is a (i) Simple singly linked list (ii)
headed singly linked list (iii) Simple circularly linked list and (iv) headed circularly linked list?

32. Sketch a multiply linked list representation for the following sparse matrix:

-9 0 0 0

0 0 0 0

0 5 0 2

0 7 0 5

33. Demonstrate the application of singly linked lists for the addition of the polynomials P1 and P2 given below:

P1: 19x6 + 78x4 + 6x3 – 23x2 – 34

P2: 67x6 + 89x5 – 23x3 – 75x2 – 89x -21

33. Let X = (x1, x2, … xn), Y = (y1, y2, …yn) be two lists with a sorted sequence of elements. Write a
program to merge the two lists together as a single list Z with m + n elements. Implement the lists using
singly linked list representations.

34. Write a program which will split a circularly linked list P with n nodes into two circularly linked lists
P1, P2 with the first and the last n - nodes of the list P in them, respectively.

35. What are the merits of linked stacks and queues over their sequential counterparts?

36. How is the memory storage pool associated with a linked stack data structure for its operations?

37. How are push and pop operations implemented on a linked stack?

38. What are traversable queues?

39. Outline the node structure and a linked queue to represent the polynomial: 17x5 + 18x2 + 9x + 89.

40. Write a program to evaluate a postfix expression using a linked stack implementation.

Module – IV

41. Distinguish between digraphs and undirected graphs.

42. For a graph of your choice, trace its (i) adjacency matrix and (ii) adjacency list representations.

43. Draw graphs that contain (i) an Eulerian walk and (ii) a Hamiltonian circuit.
 44. How can graph traversal procedures help in detecting graph connectivity?

45. Discuss an algorithm for finding minimum cost spanning tree.

46. Implement Dijkstra’s algorithm to obtain shortest path from a given source vertex (of your choice) to
every other vertex of a graph of your choice which must at least 10 nodes with 5 cycles.

Module - V

47. Sketch (i) an array representation and (ii) a linked representation for the binary tree shown in figure 1.

4 9

5 7

Fig. 1

48. Sketch a linked representation for a threaded binary tree equivalent of the binary tree shown in fig. 1.

49. Obtain inorder and post order traversals for the binary tree shown in fig. 1.

50. Draw an expression tree for the following logical expression: p and (q or not k) and (s or b or h)

51. Given the following inorder and preorder traversals, trace the binary tree.

Inorder traversal: B F G H P R S T W Y Z Preorder traversal: P F B H G S R Y T W Z.

52. Write a program to implement a binary tree using linked representation. Use functions to traverse it in
inorder, preorder and post order.

53. Write a recursive function to count the number of nodes in a binary tree.

54. Write non-recursive functions to perform inorder, preorder and post order traversals of a binary tree.

55. How is binary search tree representation of lists advantageous over their sequential list representations?

56. How is the deletion of a node that has both left and right subtrees, undertaken in a binary search tree?

57. What is the need for an AVL Tree?

58. How is the rotation free deletion of a node having both the subtrees, done in an AVL search tree?
 59. For the data list { AND, BEGIN, CASE, DO , END , FOR, GOTO, IF, IN, LET, NOT, OR, QUIT,
READ, REPEAT, RESET, THEN, UNTIL, WHILE, XOR}

a. Construct a binary search tree. What are your observations?

b. Construct an AVL search tree.

60. What are the merits of m-way search trees over AVL search trees?

61. What are the demerits of m-way search trees?

62. What is the need for B trees?

63. What is the height of a B tree of order m?

64. Insert the following elements in the order given into an empty B tree of order (i) 3 (ii) 4 and (iii) 7: Z R
T A D F H Q W C V B S E O P L J K M N U T X.

Undertake the following operations on the B trees: (i) delete Q (ii) delete A (iii) delete M

65. For the data list given in Question 63, construct a 3-way search tree. Insert G and delete J K and Z from
the search tree.

Module – VI

66. Distinguish between internal sorting and external sorting.

67. When is a sorting process said to be stable? Why is bubble sort stable?

68. What is the principle behind Shell sort?

69. Distinguish between a heap and a binary search tree. Give an example.

70. Can bubble sort ever perform better than quick sort? If so, list a case.

71. Trace Quick sort on the following list L = { 123, 678, 345, 225, 890, 345, 111, 654, 789, 144, 324,
209}.

Module – VII

72. What are the advantages of binary search over sequential search?

73. When is a transpose sequential search said to be most successful?

74. What is the principle behind interpolation search?

75. For the following search list undertake (i) linear ordered search (ii) binary search in the data list given.
Tabulate the number of comparisons made for each key in the search list.

Search list: {766, 009, 999, 238}

Data list: {111, 453, 231, 112, 679, 238, 876, 655, 766, 877, 988, 009, 122, 233, 344, 566}

76. For the given data list and search list, tabulate the number of comparisons made when (i) a transpose
sequential search and (ii) interpolation search is undertaken on the keys belonging to the search list.

Data list: {pin, ink, pen, clip, ribbon, eraser, duster, chalk, pencil, paper, stapler, pot, scale, calculator}
Search list: {pen, clip, paper, pin, calculator}

------