Data Structures And Algorithms Question Paper
Data Structures And Algorithms
Course:Bachelor Of Science In Information Technology
Institution: Kca University question papers
Exam Year:2011
UNIVERSITY EXAMINATIONS: 2010/2011
SECOND YEAR STAGE EXAMINATION FOR THE DEGREE OF BACHELOR
OF SCIENCE IN INFORMATION TECHNOLOGY
BIT 2102: DATA STRUCTURES AND ALGORITHMS
DATE: APRIL 2011 TIME: 2 HOURS
INSTRUCTIONS: Answer question ONE and any other TWO questions
QUESTION ONE [30 Marks]
(a) Define briefly the following terms:
(i) Doubly linked list
(ii) Binary search tree
(iii) Insertion sort
(iv) Order of magnitude analysis [8 Marks]
(b) If you push the letters D, C, B and A in order onto a stack of characters and then pop them, in
what order will they be deleted from the stack? [2 Marks]
(c) Suppose that you sort a large array of integers by using mergesort. Next you use a binary search
to determine whether a given integers occurs in the array. Finally, you display all integers
in the sorted array.
(i) which algorithm is faster, in general, the mergesort or the binary search? Explain in terms of
the Big O notation. [3 Marks]
(ii) Which algorithm is faster, in general: the binary search or displaying the integer? Explain
in terms of the Big O notation. [3 Marks]
(d) Explain why rightward drift can cause a queue full condition even though the queue contains few
entries. Illustrate this situation and give two solution? [4 Marks]
2
(e) i) What advantages do prefix and postfix forms of expression have over the infix form.
[1 Mark]
ii) Represent the prefix expression -*E/BD-CA as a binary tree. Also write the postfix
form and the fully parenthesized infix form of the expression. [5 Marks]
(f) i) What is a balanced binary tree? [2 Marks]
ii) If T is a full binary tree with n external nodes, how many total nodes does T have?
[2 Marks]
QUESTION TWO [20 MARKS]
a) Show how the following items: 30, 20, 10 can be implemented in an ADT stack that uses
i) An array
ii) Linked list and
iii) An ADT list. [6 Marks]
b) i) Explain with the aid of a diagram how to insert an item to an empty queue. [3 Marks]
ii) Write the C++ assignment statement to accomplish (i) above. [1 Marks]
c) Suppose you delete items from an array based implement of a list but do not close up the gaps.
State any two problems of not closing up the gaps. What is the solution? [4 Marks]
d) i) Discuss the procedure of inserting on node N in a doubly linked list.
Illustrate your answer with a diagram. [4 Marks]
ii) Write C++ assignment statement to accomplish (i) above. [2 Marks]
QUESTION THREE [20 MARKS]
a) The Fibonacci function can be defined by the recurrence relation
( )
( ) ( ) ??
??
?
- + - >
=
=
=
1 2 2
1 2
1 1
Fib n Fib n n
n
n
Fib n
i) Compute the first 6 sequence of the function. [3 Marks]
ii) Write down the C++ function that implements the definition indicating the preconditions and post
conditions. [3 Marks]
b) i) Explain how binary search works. What properties must the input have? [4 Marks]
ii) Derive the worst case time required by binary search. [3 Marks]
3
c) i) Explain what is an in-order traversal? [2 Marks]
ii) Write an algorithm to execute an in-order traversal. [3 Marks]
d) Give examples of distinct binary trees 1 2 , B and B each with two vertices, with pre-order vertices
listing of 1 B equals to the pre-order listing of B2, and the postorder vertex listing of B1 equals to
the postorder listing of B2. [2 Marks]
QUESTION FOUR [20 MARKS]
a) Represent the expression tree ((A -C) *D)/ (A + (B+D)) as a binary tree and write the prefix and
postfix form of the expression. [6 Marks]
b) i) Write a pseudocode algorithm that evaluates a postfix expression. [3 Marks]
ii) Find the value of the postfix expression ABC**ABCD+ +*- given the following identifier
A=1 B=2 C=3 and D=4. [3 Marks]
c) i) Using the properties of logarithm show that log n! =O (nlog n) [3 Marks]
ii) What is the order of magnitude for the expression (3n + 2)2 ? [2 Marks]
d) An array-based implementation requires less memory than an pointer-based implementation.
Explain. [3 Marks]
QUESTION FIVE [20 MARKS]
a) Briefly explain the following terms:
(i) Access time
(ii) Ancestor of a node n
(iii)Exhaustive search
(iv) Divide and conquer. [4 Marks]
b) The following function computes the product of the first n = 1real numbers in an array.
Demonstrate that the function is recursive by writing the criteria of a recursive solution and stating
how the function meets each criterion.
Double Product (const double A [], int N)
// Preconditions: 1<=N<=Max Size of A
// Post conditions: Return the product of the first N items in A; A is unchanged
4
{
If (N= =1)
return A [0];
else
return A [N-1]*Product (A, N-1);
} end Product [8 Marks]
c) i) Beginning with an empty binary search tree, what binary search tree is formed when you insert
the following values in the order given? A, B, W, J, N, T, E [2 marks]
ii) If you delete an item from a binary search tree and then insert it back into the tree, will you ever
change the shape of the tree? Explain [2 Marks]
d) When sorting an array by using mergesort,
i) Do the recursive calls to mergesort depend on the values in the array, the number of items in
the array, or both? Explain [2 Marks]
ii) In what step of mergesort are the items in the array actually swapped (that is, sorted)?
Explain [2 Marks]
More Question Papers
Exams With Marking Schemes