DS MID-II QUESTION BANK

CMR COLLEGE OF ENGINEERING & TECHNOLOGY
(AUTONOMOUS)
(Regulations: CMRCET-R22)
Subject Name: DATA STRUCTURES Subject Code: A405301
DS MID-II QUESTION BANK

1. Define Complete Binary Tree?
2. For the tree below, write the pre-order & post-order traversal.
3. Discuss about the Properties of B-Tree.

4. Define Splaying and list out the types of rotations in Splay Tree
5. Differentiate between Internal Sorting and External Sorting
6. Define Graph? List out the types of Graph Representations
7. Differentiate between Max-Heap and Min-Heap
8. Define Pattern Matching and also list out the types of applications
9. What is the time complexity of brute-force algorithm?
10. Construct a standard trie tree for the given set of strings
S = {bear, bell, bid, bull, buy, sell, stock, stop }
11. List out the steps involved in deleting a node from a binary search tree.
12. Distinguish between Complete Binary tree and Full Binary tree.
13. Write down the following tree terminologies.
a) terminal nodes b) siblings c) height d) depth
14. What are the properties in Red-Black tree.
15. How Graph can be represented?
16. Name the different ways of representing a graph? Give examples
17. What is the output of quick sort after the 3rd iteration given the following sequence?
24 56 47 35 10 90 82 31
18. Write down the best, average and worst time complexities of merge sort.
19. Define a trie.
20. What is meant by LPS? Write down the time complexity for KMP?
21. Create a B-Tree of order 3 from the following lists of data items: 1,2,3,4,5,6,7
22. Discuss the advantages of AVL trees over BST

Page 1 of 4
23. Write any two characteristics of Red-Black tree.
24. In how many ways, can you represent a graph in a computer memory? Which one is advantageous
and why?
25. Write two key differences between BFS and DFS.
26. Compare and contrast internal and external sorting?
27. Construct the initial max heap of the following array 32, 15, 20,30,12,25,16
28. What are the applications of pattern matching algorithms?
29. Which pattern matching technique is best among Brute-Force, KMP and Boyer-Moore? Give
your reason
30. Differentiate between standard tries and compressed tries
31. What is tree data structure how many types are there?
32. Explain Types of binary tree ?
33. What is binary search tree .
34. What is directed, undirnected, mixed graph explain
35. What is the difference between Adjacency Matrix and Adjacency List explain?
36. Write the difference between heap and merge sort?
37. Define patterm matching
38. Write about boyer moore matching algorithmn
39. List out the steps involved in deleting a node from a binary search tree.
40. What are the rotations of AVL trees?
41. Write the properties of red-black trees.
42. Define complete binary tree?
43. Write the steps involved in BFS.
44. What is the various representation of a graph?
45. What is LPS?
46. Explain memory representation of compressed tries
47. List out steps in KMP?
48. Create a binary search tree for the following numbers start from an empty binary search tree.
45,26,10,60,70,30,40. Delete keys 10,60 and 45 one after the other and show the trees at each stage.
49. a) Explain Splay-trees with neat diagram.
b) Explain B+ trees and its operations.
50. a) Write and perform heap sort algorithm for 10 15 6 2 25 18 16 2 20 4.
b) Discuss how to represent graph storage using Adjacency list.
51. Write and explain the depth-first search traversal algorithm with an example.
Page 2 of 4
52. Solve the Knuth Morris-Pratt algorithm for the following:
Text: HEREISASIMPLEEXAMPLE
Pattern: EXAMPLE.
53. a) How Compressed Tries Work? Explain its operations with an example.
b) Explain Standard Tries with an example.
54. Construct AVL Tree for the following sequence of numbers- 50, 20, 60, 10, 8, 15, 32, 46, 11
55. Create a RED BLACK Tree by inserting following sequence of elements 8,18,5,15,17,25,40
56. Write the C Program to implement the merge sort technique.
57. Consider the following graph which marks the order in which the nodes would be discovered
by traversing in BFS
58. Explain KMP matcher and find the occurrence of ‘Pattern’ in given Text
59. Explain about: i. Compressed Trie ii. Suffix Trie

60. (a).Construct the binary search for the following elements. 48,2,98,12,56,32,4,6
(b). Write the post-order non-recursive traversal for the same using stack
61. Show the AVL tree that results after each of the integer keys 9, 27, 50, 15, 2, 21, and 36 are
inserted, in that order, into an initially empty AVL tree. Clearly show the tree that results after
each insertion, and make clear any rotations that must be performed.
62. Write the DFS traversal for the above graph by applying the algorithm step by step.
63. Sort out following elements by using quick sort technique and write a function for the same.
54,26.9317,77,31,44, 55,20
64. Explain KMP algorithm with an example.
65. Explain the types of tries each with an example.
66. Write a c program to find the height of a binary tree
Page 3 of 4
67. Write a c program to implement AVL tree create, delete & traversal?
68. Explain about DFS & BFS
69. Discuss about heap sort algorithm with an example 1,2,5,9,10,15
70. Perform Knuth-Morris-Pratt algorithm(KMP )
Text: B A D B A B A BA B A D A A B Pattern: A B A B A D A
71. Explain about brute force pattern matching algorithm with an example?
72. Implement Splay tree for the given keys. 25,20,37,8,23,16

73. Construct a Red-Black tree with following keys 1,2,4,5,9,3,6,7
74. Implement a program for Quick sort.
75. Describe various graph representation methods.
76. Analyze the position of pattern from given text using KMP algorithm
Text: abc abc bab abc dabcdabde pattern: abcdabd
77. S= {ball, box, bomb, basket, start, stop, stock} construct compressed tries from the standard tries.
78. Draw the B-tree of order 3 created by inserting the following data arriving in sequence –
92,24,6,7,11,8,22,4,5,16,19,20,78
79. Write a program for heap sort.

80. Construct the BFS and DFS for the following graph.
81. Illustrate Boyer-Moore algorithm with following text and pattern

Text: welcome to data structures Pattern: data
Page 4 of 4

DS MID-II QUESTION BANK

Uploaded by

Copyright:

Available Formats

DS MID-II QUESTION BANK

Uploaded by

Document Information

Original Description:

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

DS MID-II QUESTION BANK

Uploaded by

Copyright:

Available Formats

CMR COLLEGE OF ENGINEERING & TECHNOLOGY

Subject Name: DATA STRUCTURES Subject Code: A405301

DS MID-II QUESTION BANK

3. Discuss about the Properties of B-Tree.

22. Discuss the advantages of AVL trees over BST

25. Write two key differences between BFS and DFS.

26. Compare and contrast internal and external sorting?

59. Explain about: i. Compressed Trie ii. Suffix Trie

72. Implement Splay tree for the given keys. 25,20,37,8,23,16

79. Write a program for heap sort.

81. Illustrate Boyer-Moore algorithm with following text and pattern

You might also like