USN 10EC/TE761

Seventh Semester B.E. Degree Examination, Dec.2016/Jan.2017

Data Structures Using C++

Time: 3 hrs. Max. Marks:100

Note: Answer FIVE full questions, selecting
at least TWO questions from each part.
2. Any revealing of identification, appeal to evaluator and /or equations written eg, 42+8 = 50, will be treated as malpractice.

PART – A
1 a. How dynamic memory allocation is performed in C++? Explain with suitable examples.
(06 Marks)
b. What is linear list? Write the abstract class specification of a linear list. (06 Marks)
c. In linked list representation explain the class “chain”, define member function for header,
Important Note : 1. On completing your answers, compulsorily draw diagonal cross lines on the remaining blank pages.

for the class chain. (08 Marks)

2 a. Write a C++ program to illustrate the class diagonal matrix. (12 Marks)
b. Explain row major and column major mapping with a suitable example. (08 Marks)

3 a. Write a program to explain the concept of Towers of Hanoi problem, using recursive method
and using stacks. (10 Marks)
b. Write a C++ program for abstract class stack and explain. Write a program to explain the
concept of parenthesis matching. (10 Marks)

4 a. What are the abstract data type of queue? Write a C++ program to explain push and pop
methods of linked queue. (08 Marks)
b. Write a program to explain and implement image-component labeling with an example.
(12 Marks)

PART – B
5 a. Give abstract data type specification for dictionary. Explain the method of sorted chain using
skip list representation. (12 Marks)
b. Develop the C++ class for has table to perform search and insert operation. (08 Marks)

6 a. Define binary trees. State and prove any three properties of binary trees. (08 Marks)
b. Explain with C++ program the four traversal methods of binary tree. (12 Marks)

7 a. What is Max Heap? Write a program to initialize a max heap. (10 Marks)
b. Define height biased leftist tree. Write a C++ program to illustrate melding of two leftist
trees. (10 Marks)

8 a. What is histogramming? Write a C++ program to demonstrate simple histogramming.

(08 Marks)
b. Write a program to insert an element with key K in a binary search tree. (08 Marks)
c. Define B-Tree of order m. List out the properties if the B-Tree is not empty. (04 Marks)

*****