Get premium membership and access revision papers, questions with answers as well as video lessons.

Got a question or eager to learn? Discover limitless learning on WhatsApp now - Start Now!

Data Structures And Algorithms Question Paper

Data Structures And Algorithms

Course:Bachelor Of Science In Information Technology

Institution: Kca University question papers

Exam Year:2010

UNIVERSITY EXAMINATIONS: 2010/2011
FIRST YEAR STAGE EXAMINATION FOR THE DEGREE OF BACHELOR
OF SCIENCE IN INFORMATION TECHNOLOGY
BIT 2102: DATA STRUCTURES AND ALGORITHMS
DATE: DECEMBER 2010 TIME: 2 HOURS
INSTRUCTIONS: Answer question ONE and any other TWO questions
QUESTION ONE
a) Briefly distinguish between following terms:
(i) Data types and data structures (2 Marks)
(ii) Abstract data types and data abstraction (2 Marks)
(iii)Single dimensional and multidimensional array (2 Marks)
(iv) Binary search and sequential search (2 Marks)
(v) Insertion sort and merge sort (2 Marks)
(vi) Define the term algorithm. (2 Marks)
b) (i) State and describe the five important features of an algorithm (5 Marks)
(ii) Give at least three types of algorithm used in data structures (3 Marks)
c) (i) Describe the three standard ways of traversing a data structure (6 Marks)
(ii) Traverse the given tree below using the various ways mentioned in (i) above(3 Marks)
Figure 1
2
(iii) Explain how a binary tree can be used to represent an expression tree. (1 Mark)
QUESTION TWO [20 Marks]
a) (i) Describe an array. (2 Marks)
(ii) Show how one can increase the size of a dynamically allocated array and explain why a
dynamically allocated array waste space and time (4 Marks)
(iii) What is the address of A [0, 0, 0] in an array stored linearly in row-major beginning in address
alpha if it is declared as A [-2….2, -1....5, -1...3]? (4 Marks)
b) (i) Distinguish between a linked list and a doubly linked list (4 Marks)
(ii) Describe a situation when a doubly linked list is appropriate. (2 Marks)
(iii) Describe a situation where storing items in an array is better than storing items in a linked list.
(2 Marks)
c) If the character D, C, B, A are placed in a given queue (in that order), and then removed one at a
time, in what order will they be removed. (2 Marks)
QUESTION THREE [20 Marks]
(a) Briefly describe the following terms with respect to binary tree:
(i) Height of a tree
(ii) Complete binary tree
(iii)Subtree of a tree
(iv) Balanced binary tree (4 Marks)
(b) (i) What is the minimum number of nodes in a complete binary tree of height 3? Draw it.
(2 Marks)
ii) Suppose T is a binary tree with 15 nodes. What is the minimum possible height of the
tree? Draw it. (2 Marks)
iii) If a binary tree has 10 internal nodes, how many nodes does the binary tree have?
(2 Marks)
(c) The recursive definition of the Fibonacci function is
? ? ?
?
?
- + - >
=
=
=
( 1) ( 2) 2
1 2
1 1
( )
F n F n if n
if n
if n
F n
i) Write the C++ function that implements the definition including the precondition and post
conditions (4 Marks)
ii) Write the first five terms of the sequence. (2 Marks)
3
(d) Describe any four queue operations. (4 Marks)
QUESTION FOUR [20 Marks]
a) Explain clearly how to delete a node from a binary search tree. (4 Marks)
b) Distinguish between a heap and heapsort. (4 Marks)
c) State and describe any four stack operations. (4 Marks)
d) Differentiate between recurrence relation and recursion procedure. (4 Marks)
e) Evaluate the following postfix expression: AB+C-DE+*. Assume the following values for the
identifiers: A=7, B=3, C=12, D=-5 and E=1. (4 Marks)
QUESTION FIVE [20 Marks]
(a) Show the steps of converting the following infix expression into its postfix equivalent using a stack.
Show the contents of the output as well as the stack after each step:
(i) A/B/C-(D+E)*F
(ii) A+(B*CC-D)*E (6 Marks)
(b) Consider the binary tree in Figure 2 below.
Figure 2
(i) Starting with an empty binary search tree, in what order should you insert items to get
the binary search tree in the Figure 2. ( 2 Marks)
(ii) Using the tree in Figure 2 above, trace the algorithm that searches a binary search tree
given a search key of 30 and 15. In each case, list the nodes in the order in which the
search visits them. (4 Marks)
(c) Imagine that you have 101 Dalmatian, no two Dalmatian have the same number of spots. Suppose
you create an array of 101 integers. The first integer is the number of spots on the first Dalmatian,
the second Dalmatian, and so on. Your friend wants to know whether you have a Dalmatian with
99 spots. Thus you need to determine whether the array contains the integer 99.
(i) If you plan to use a binary search to look for the 99, if anything, what would you need to do to
the array before search it? (1 Mark)
(ii) What is the index of the integer in the array that a binary search would examine first?
4
(2 Marks)
(iii) If all the Dalmatians have more than 99 spots, exactly how many comparisons will a binary
search require to determine that 99 is not in the array. (3 Marks)
(d) Differentiate between internal sort and external sort. (2 Marks)

Data Structures And Algorithms Question Paper

More Question Papers

Popular Exams