Data Structures And Algorithms Question Paper
Data Structures And Algorithms
Course:Bachelor Of Science In Information Technology
Institution: Kca University question papers
Exam Year:2009
UNIVERSITY EXAMINATIONS: 2008/2009
SECOND YEAR EXAMINATION FOR THE DEGREE OF BACHELOR OF
SCIENCE IN INFORMATION TECHNOLOGY
BIT 2102: DATA STRUCTURES AND ALGORITHMS
DATE: AUGUST 2009 TIME: 2 HOURS
INSTRUCTIONS: Answer question ONE and any other TWO questions
QUESTION ONE [30 Marks]
(a) Briefly define the following terms:
(i) Algorithm
(ii) Preconditions
(iii) Data Abstractions and
(iv) Sequential search
(4 Marks)
(b) (i) Distinguish between a data structure and abstract data types (ADT) (4 Marks)
(ii) State and explain the need for data structures (4 Marks)
(c) (i) Explain why a stack is referred to as LIFO (2 Marks)
(ii) How is a stack similar to a list? How is it different? Explain (3 Marks)
(d) (i) Define a recursive procedure and give any two examples of problems that can be solved
recursively. (4 Marks)
(ii) Why must every recursive procedure have a base case? (2 Marks)
(iii) Explain how the divide and conquer technique works. (3 Marks)
(e) The numbers 80 55 65 85 10 25 90 8 72 and 5 are to be stored for some processing in that order.
Write down the order in which the numbers will be printed if they are:
2
(i) Stored in a queue (1 Mark)
(ii) Stored in a stack (1 Mark)
(iii) Stored in a binary search tree and traversed in order. (2 Marks)
QUESTION TWO [20 Marks]
(a) Briefly discuss the following forms of a linked list
(i) Singly Linked list
(ii) Doubly Linked list
(iii)Circular Linked list
(6 Marks)
(b) (i) State the advantage and disadvantage of a doubly linked list. (2 Marks)
(ii) With the aid a diagram explain how to insert a new node in a doubly-linked list. Write the C++
assignment statement to accomplish the insertion. (4 Marks)
(c) Outline the advantages and disadvantages between using linked list and an array. (4 Marks)
(d) Compare and contrast linked list and array storage allocation of a tree. (4 Marks)
QUESTION THREE [20 Marks]
(a) (i) What complete binary tree does the array below represents
5 1 2 8 6 10 3 9 4 7
0 1 2 3 4 5 6 7 8 9
(2 Marks)
(ii) Arrange nodes that contain the letters A C E F L V Z into two binary search trees, one that has
maximum height and one that has minimum height. (2 Marks)
(iii) Trace the tree sort algorithm as it sorts the following array into ascending order:
20 80 40 25 60 30 (2 Marks)
(b) (i) What is a priority Queue? Is a priority Queue a kind of queue? Explain. (3 Marks)
(ii) How can stacks and ordinary queue be simulated using a priority queue? (2 Marks)
(c) (i) Describe the pseudo code algorithm for merge sort (3 Marks)
(ii) Show that the merge sort algorithm satisfies the four criteria of recursion (4 Marks)
(iii) Why is it easy to solve for the worst case time of merge sort if the input size is a power of two?
(2 Marks)
3
QUESTION FOUR [20 Marks]
a) In an experiment to determine the time complexity of different algorithm as the input characteristic
changed, the following functions were obtained. Determine the Big O notation in each case and
arrange them in order of increasing performance.
(i) F(N) = 3N3 + 4N 2 + 7
(ii) F(N) = 2N + 2N + 3
(iii) F(N) = 3N +10 and
(iv) F N N 2 ( ) = 3log
(6 Marks)
b) Suppose that you sort a large array of integers by merge sort. Next you use a binary search to
determine whether a given integer occurs in the array. Finally, you display all the integers in the
sorter array.
i) Which algorithm is faster in general: the merge sort or the binary search? Explain in
terms of the Big O notations (2 Marks)
ii) Which algorithm is faster, in general, the binary search or displaying the integers?
Explain in terms of the Big O notations. (2 Marks)
c) Given the expression A/B-C+D*E-A+C, construct an expression tree. Use the tree to obtain the
postfix and prefix expression. (8 Marks)
d) Show, by example that distinct binary trees with vertices A, B and C can have the same preorder
listing ABC. (2 Marks)
QUESTION FIVE [20 Marks]
(a) (i) Describe the algorithm that evaluate postfix expression (3 Marks)
(ii) Find the value of the postfix expression: ABC**ABC++- if A=1, B=2 and C=3.
(3 Marks)
(b) Provide brief answers to the following questions
(i) Why is an ordered array better than an unordered array?
(ii) How does a binary search works
4
(iii) What is the maximum number of comparisons necessary when performing a binary
search of 100,000 items?
(iv) When would you use bubble sort instead of insertion sort?
(4 Marks)
(c) (i) Using an example of a linked list, explain how insertion and deletion in a singly linked list
are special. (2 Marks)
(ii) What is a dummy node and what is its characteristic? (2 Marks)
(d) The tribonnacci sequence is defined by the equation
1, 4 1 2 3 1 2 3 = = = = + + = - - - t t t t t t t n n n n n
(i) Find t4 and t5. (2 Marks)
(ii) Write a recurrence algorithm to compute t , n = 1 n (4 Marks)
------------------------------------------------------------------
More Question Papers
Exams With Marking Schemes