Get premium membership and access revision papers, questions with answers as well as video lessons.
Data Structures And Algorithms Question Paper
Data Structures And Algorithms
Course:Bachelor Of Science In Information Technology
Institution: Masinde Muliro University Of Science And Technology question papers
Exam Year:2010
SECOND YEAR EXAMINATION FOR THE DEGREE OF BACHELOR OF
SCIENCE IN INFORMATION TECHNOLOGY
DATA STRUCTURES AND ALGORITHMS
DATE: APRIL 2010 TIME: 2 HOURS
INSTRUCTIONS: Answer question ONE and any other TWO questions
QUESTION ONE
(a) Explain briefly the following terms:
(i) Data abstraction
(ii) Dummy head node
(iii) Selection sort
(iv) Recursion (8 Marks)
(b) Outline the major data structures used in the following areas: RDMS, Network data models and
Hierarchical data model. (3 Marks)
(c) Explain any four reasons why analysis of algorithm is necessary. (4 Marks)
(d) (i) Explain the main advantage of implementing a stack using dynamic memory allocation
(linked list) as opposed to static memory allocation (array). (2 Marks)
(ii) Suppose that we perform the operation shown below on a stack. Assume that the stack
is initially empty. In what order will the element be pooped, push A, push B, Push C,
Pop, Pop, Push D, Pop, and Pop. (2 Marks)
(e) (i) Distinguish between a binary tree and a binary search tree. (4 Marks)
2
(ii) Beginning with an empty binary search tree what BST is formed when insert the following
values in the order given: 50,40,45,47,46,41,35. (4 Marks)
(f) Suppose that you sort a large array of integers by using merge sort. Next you use a binary
search to array. Finally, you display all the integers in the sorted array.
(i) Which algorithm is faster in general: the merge sort 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 integers? Explain
in terms of the Big O notation. (2 Marks)
QUESTION TWO
(a) State any four areas where data structures are used extensively. (4 Marks)
(b) Distinguish between the following types of lists:
(i) Sorted list and linked list
(ii) Circular list and doubly-linked list (4 Marks)
(c) (i) Define the concept of ‘column-major’ ordering the multidimensional arrays (2 Marks)
(ii) What is the address of A [0,0] in an array stored linearly in column-major ordering
beginning in address alpha if it is declared as A [-1..5,-2..2] (2 Marks)
(d) (i) Explain two advantages of a linked list as compared to an array
(ii) Discuss two disadvantages of a linked list as compared to an array. (4 Marks)
QUESTION THREE
(a) Draw the expression tree ((A + B) *C - (D - E)^ (F + G)) and then use the tree to obtain the
prefix and postfix in expression. (6 Marks)
(b) Use a stack to evaluate the following postfix expression: ABC*-DEF/-G*+. Show the status of
stack after each step of the algorithm. Assume the following values for the identifies:
A=9,B=3,C=2,D=8,E=6,F=2,G=3. (4 Marks)
(c) (i) Consider the vowels from a tree with ‘O’ as the root and its children are ‘U”,”I”,”A”, left to
right and “E” is the only child of “I”. Reconstruct this tree as a binary tree. (4 Marks)
3
(ii) Show how the vowel binary tree of (i) above would appear in single array and three-array form.
(Note in three-array form, the vowels are to be sorted in alphabetical order) (6 Marks)
QUESTION FOUR
a) (i) What is a priority queue? Is a priority queue a kind of queue? (3 Marks)
(ii) How can stacks and ordinary queue be simulated using a priority queue? (2 Marks)
b) Robot walking function can be defined by the following recurrence relation
i) Write down the C++ function that implements the definition indicating the preconditions
and post conditions. (4 Marks)
ii) Compute the first 6 sequences of the function. (2 Marks)
c) (i) Discuss the motivation behind the use of recursion (2 Marks)
(ii) Explain how the divide and conquer technique works. (2 Marks)
d) (i) Explain how the merge algorithm works? What properties must the input have? (4 Marks)
(ii) What is the worst-case time of merge algorithm? [1 Mark]
QUESTION FIVE
a) (i) Explain how bubble sort works?
(ii) Trace bubble sort as it sorts the following array in ascending order:
25 30 20 80 40 60 (4 Marks)
b) Convert the following infix expression to equivalent postfix form: Show the status of the stack
after each of the algorithms.
(i) (A-B*C)/D-(E+F) (3 Marks)
(ii) A/(B*C/D)+E (3 Marks)
c) What is the order of magnitude for the following expression
n n
i n n n ii n n n
+
+
+ 2
2 2
2
( ) 2 log , ( ) ( 1)( log ) (4 Marks)
d) Estimate how many times faster an average successful search will be in a sorted array of one
million elements if it is done by binary search versus sequential search (4 Marks)
More Question Papers
Popular Exams
Return to Question Papers