Home / ModelQuestions / KTU B.TECH S3 MODEL QUESTION CS 205 DATA STRUCTURES

# KTU B.TECH S3 MODEL QUESTION CS 205 DATA STRUCTURES

MODEL QUESTION PAPER by ktubtechquestions.com

THIRD SEMESTER B.TECH  DEGREE EXAMINATION  DECEMBER 2016

CS 205: DATA STRUCTURES

Time: 3 Hrs                                                                                                                      Marks: 100

PART A

( Answer All Questions Each carries 3 Marks )

1. List out four factors that affect running time of an algorithm.
2. Define O-notation .
3. What is step-wise refinement?
4. Write C language statements to check if a circular, double linked list is empty.

PART B

( Answer any TWO, Each carries 9 Marks )

1. a) Briefly distinguish between top-down and bottom-up styles of program development.

(4 Marks)

b) What is the effect of the following code snippets on matrix A of size _ × _?

1. a) Write a function that deletes the last element of a singly linked list.                      (3 mark)

b) Concatenate two circular double linked lists A and B so that B appears after     (6 Mark)

1. (a) Show, by identifying suitable constants, that,                                                         (6 Marks)

( b) Distinguish between worst-case, best-case and average-case running times of an algorithm.  Give example for an algorithm which has the same worst, best and average running times. ` (3 Marks)

PART C

( Answer All Questions Each Carries 3 Marks )

1. Give examples for complete binary tree and full binary tree.
2. What is the use of stacks in recursion?
3. Draw the following:

(i) A binary tree of height 4 with minimum nodes.

(ii) Two distinct binary trees, each of ten nodes, which generate the same sequence by in-order      traversal.

1. Represent the following infix expression as a binary tree and show its pre-fix equivalent.

P +    (Q*R)/W – (A – B)/E

PART D

( Answer any TWO, Each carries 9 Marks )

1. (a) Give the algorithm for best-fit allocation.                                                                (4 Marks)

(b) Compare first-fit, best-fit and worst-fit strategies.                                               (5 Marks)

1. (a) Show pictorially the contents an initially empty circular queue of size 6 after each of the following                          operations: insert (2), insert(3), insert(5), delete, insert (4), insert(9), delete, insert(10), insert(1), delete,    insert(7), insert(8).                                                                                                      (4 Marks)

(b) Show the structure of the binary search tree after adding each of the following values in that   order: 1, 12,                      5,  7, 1, 0.                                                                                                                      (5 Marks)

1. a)  Show the contents of the stack and output after each token when the following infix expression is processed        to generate the equivalent postfix expression:

A + B – C *(D/F)/G.                                                                                         (6 Marks)

b) Prove,by induction on number of internal nodes that a full binary tree with I internal nodes have I+1 leaf                        nodes.                                                                                                                                       (3 Marks)

PART E

( Answer any FOUR, Each carries 10 Marks )

1. Show (pictorially or otherwise) how split an merge take place when merge sort is applied on the following list of numbers: 2, 5, 2, 0, 10, 9, 8, 23, 7.
1. (a) When does binary search give the best and worst performances? Give examples of for each of these                          situations. (4 Marks)

(b) Give the algorithm/C function for inserting an element in to a heap. (6 Marks)

1. Deduce the expression for best and worst case running times of insertion sort.
1. a)Show (pictorially or otherwise) how the following list is partitioned into smaller sub-lists when quick sort is applied: 3, 4, 6, 20, 10, 9, 7, 5, 1. (8 Marks)

b) Illustrate how mid-square method is used for hashing. (2 marks)

1. a) For the following undirected graph, show the adjacency list and adjacency matrix representations

(7 marks)

b) For the following list of integers how many comparisons are done by insertion sort and selection sort?

2, 4, 6, 8, 7, 5, 3 (3 marks)

20.   a) Give the algorithm/C function for inserting an element in to a heap. (7 marks)

b) Explain how overflow is handled in hashing.                                           (3 marks)

x

## KTU B.Tech S5 ModelQuestions -Power Electronics and Instrumentation

KTU B.Tech S5 ModelQuestions -Power Electronics and Instrumentation

## KTU B.Tech S5 ModelQuestions – Geomatics

KTU B.Tech S5 ModelQuestions -Geomatics