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

Comp 123:: Data Structures And Algorithm Question Paper

Comp 123:: Data Structures And Algorithm

Course:Bsc.Computer Science

Institution: Kabarak University question papers

Exam Year:2012

KABARAK UNIVERSITY
UNIVERSITY EXAMINATIONS
2011/2012 ACADEMIC YEAR
FOR THE DEGREE OF BACHELOR OF EDUCATION SCIEN
CE
COMP 123: DATA STRUCTURES AND ALGORITHM
DAY: THURSDAY DATE: 12/04/2012
TIME: 11.00 – 1.00 P.M. STREA
M: SESS 2
INSTRUCTIONS:
Answer ALL questions in section A.
SECTION A. (Compulsory)
QUESTION ONE (30 MARKS)
1.
What is a data structure? Explain the various types of dat
a structure with suitable
example
(6 marks)
2.
Construct a binary tree W with 8 nodes using inorder and pos
torder traversal as follows
Inorder F B G A D C E J
Postorder F G B D J E C A
(6 marks)
3.
Describe the time complexity or how to compute total tim
e for executing an algorithm
(2 marks)
4.
Distinguish between infix,prefix and postfix algebraic expr
ession giving examples of
each.
(3 marks)
5.
Differentiate between isolated node and a Null grapgh
(3 marks)
6.
Assume that each element of an array B occupies 7 units
of storage. If B is declared as int
B[2000] and the address of the first element of B is 2000,find t
he address of B[10].
(2 marks)
7.
What is a stack.Given a stack A. describe what POPA and P
USHA represent
(2 marks)
8.
What is a circular queue?how is it different from simp
le queue?
(2 marks)
Page
2
of
4
9.
Describe what happens when the following operation is perfo
rmed in the stack.
Pop(create(S))
(2 marks)
10.
What is the significance of NULL pointer in a linked l
ist
(2 marks)
QUESTION TWO (20 MARKS)
1.
What is a binary tree? What is the advantage and the disa
dvantage of threaded binary tree
(3 marks)
2.
Write the pre-order, in-order and post order notation of th
e following binary expression
trees
(6 marks)
(a)
+
/
+
C
a
-
d
e
b
Page
3
of
4
(b)
3.
What is binary search tree? Write an algorithm to searc
h a value in binary search tree
(5 marks)
4.
What is meant by traversal of a graph? Discuss Breadth f
irst traversal technique with the
help of an example
(3 marks)
5.
Write the adjacency matrix of the following graph. The
order of nodes is shown below
(2 marks)
1
2
3
5
4
+
*
/
+
5
10
5
-
*
5
4
5
4
A
B
C
E
D
Page
4
of
4
QUESTION THREE (20 MARKS)
1. Highlight the disadvantage of Linear search
( 2 marks)
2. Differentiate between directed and undirected graph? Dis
cuss adjacency matrix representation
of graphs with examples
(5 marks)
3. Given the following directed graph G. Write the adjace
ncy matrix of the graph.
(4 marks)
4. Explain the technique of insertion sort
(4 marks)
5. What do you understand by the time and space complexity of
Algorithms? Provide the
complexity of various searching and sorting techniques
(4 marks)
6. Comment on the efficiency of linear search and binary
search in relation to the number of
elements in the list being searched
(2 marks)
QUESTION FOUR (20 MARKS)
1. Let there be a binatry tree T with 8 nodes.The Inor
der and preorder traversals of the binary
tree T are as under
Inorder F B G A D C E J
Preorder A B F G C D E J
Required:
Construct a binary tree
(10 marks)
2. Suppose each element of an array MARKS occupies 4 byt
es,and the address of the 1
st
element
is 493 .what will be the address of the 3
rd
element? (
2 marks)
3. Explain the operations performed on the stack with examp
les
(6 marks)
4. How is the queue different from the stack?
(2 marks)
2
1
5
4
3

Comp 123:: Data Structures And Algorithm Question Paper

More Question Papers

Popular Exams