REGULAR UNIVERSITY EXAMINATIONS
2018/2019 ACADEMIC YEAR
SECOND YEAR FIRST SEMESTER
SCHOOL OF SCIENCE & INFORMATION SCIENCE
EXAMINATIONS FOR B SC. IN COMPUTER
SCIENCE
COURSE CODE: COM 2204
COURSE TITLE: DATA STRUCTURES
DATE: 7TH, DECEMBER, 2018 TIME: 0830 – 1030 HRS
INSTRUCTIONS
Answer Question ONE and any other TWO Questions From
Section II
Question 1 is compulsory.
Time 2HRS.
SWITCH OFF your mobile phone.
SECTION I-COMPULSORY
1
A) Define the following terms [4 marks]
i. Algorithm.
ii. Data structure.
B) Given the following queue operations on an empty existing queue
called nameQueue. What would be displayed after the series of
operations? [2 marks]
[Link](Sid)
[Link](Sal)
[Link](Sue)
[Link](Sam)
[Link]()
display ([Link]())
C) What would this for loop to do? [2 marks]
for (position = 1 through [Link]())
{
dataItem = [Link](position)
print(dataItem)
}
D) Given the array [4, 15, 8, 3, 28, 21], determine the state of the
array after a second swap of the selection sort. Show all your
working in the answer booklet. [3 marks]
E) How does the quicksort partition an array? [2 marks]
F) Describe any two desirable properties of an algorithm [4 marks]
G) Explain an advantage that arrays have over linked lists.
[2 marks]
H) A stack is initially empty, then the following commands are performed:
push 5, push 7, pop, push 10, push 5, pop. Give the list of elements
in the stack after the operations. Explain your answer (assume the top of
the stack is from the left). [3 marks]
I) What is the difference between the stack pop and top operations?
[4 marks]
J) What restriction does the array-based implementation of a stack
place on the push operation? [2 marks]
K) Describe what happens when we insert a new item into the
middle of the list. [2 marks]
L) List differences in operations between the list as opposed to the
stack or queue. [2 marks]
M) Perform a post order traversal of the following tree. [3 marks]
2
SECTION II -CHOOSEANY TWO QUESTIONS
Question Two
A) Write a complete C++ program to implement a stack. Your program
should give a user the following options to choose, which then, it
implements. [15 Marks]
1. Insert an element into a stack.
2. Delete an element from the stack.
3. Determine the size of the stack.
4. Display the top element of the stack
5. Exit.
B Define an algorithm and explain at least four desirable properties
of a good algorithm. [5 marks]
Question Three
A) Describe the following list operations [6 marks]
i. Insert
ii. Delete
iii. Merge
B) Describe the following stack operations [6 marks]
i. Empty(s)
ii. Makenull(s)
iii. Push
C) Describe a linked list. You may use an appropriate diagram.
[2 marks]
D) Write a complete C++ program to implement a stack. Your
program should have the following.
i. Declare list1 [2 marks]
ii. Initialize an array with elements 1,2,3,4. [2 marks]
iii. Use assign() function to insert 4 and 2 to list1.
[2 marks]
3
Question Four
A) Does the following tree meet the heap property of a binary tree?
Explain your answer. If your answer in no, draw a tree, using the
same elements, that meets the heap property.-
[ 4 marks]
12
10 11
7 8
3 4
1 0 5
B) If your tree in B above to sort the following array in ascending order.
[16 marks]
12 10 11 7 8 3 4 1 0 5