 |
DSA521S - DATA STRUCTURES AND ALGORITHMS 1 - 1ST OPP - NOV 2023 |
|
|
1 Page 1 |
▲back to top |
n Am I BIA u n IVER s ITY
OFSCIEnCEAno TECHnoLOGY
FACULTY OF COMPUTING AND INFORMATICS
DEPARTMENTOF SOFTWAREENGINEERING
QUALIFICATION:BACHELOROF COMPUTERSCIENCE,BACHELOROF INFORMATICS
QUALIFICATIONCODE:07BCMS, 07BAIT
LEVEL:5
COURSE:DATA STRUCTURESAND ALGORITHMS1
COURSECODE: DSA5215
DATE: NOVEMBER 2023
PAPER:THEORY
DURATION: 3 HOURS
MARKS: 100
EXAMINER(S)
FIRSTOPPORTUNITYEXAMINATION QUESTION PAPER
MRS. TJIRASO
MODERATOR:
MRS S. CHIVUNO-KURIA
INSTRUCTIONS
1. Answer ALL the questions.
2. Answer All the questions in the answer booklet provided.
3. Read all the questions carefully before answering.
4. Number the answers clearly in your answer booklet.
5. All things that should not be marked, e.g., any "rough work", should be
crossed out unambiguously.
THIS QUESTION PAPERCONSISTSOF 7 PAGES
(Including this front page)
PERMISSIBLE MATERIALS
NON-PRGRAMMABLE CALCULATOR
|
|
2 Page 2 |
▲back to top |
SECTIONA: Multiple Choice Questions
• Answer all the questions in the provided answer booklet.
• The section consists of 10 problems.
Problem Al
Which one of the below mentioned data structures is a linear data structure?
A. Binary tree
B. Binary search tree
C. Graph
D. Stack
Problem A2
Which of the following statement(s) is true?
Statement A: A binary tree is always a binary search tree.
Statement B: A binary search tree is a graph.
A. Statement A is true, and statement Bis false.
B. Statement A is false, and statement Bis true.
C. Both statement A and statement Bare true.
D. Both statement A and statement Bare false.
Problem A3
Which of the following statement(s) is true?
Statement A: All trees are graphs.
Statement B: Not all graphs are trees.
A. Statement A is true, and statement Bis false.
B. Statement A is false, and statement Bis true.
C. Both statement A and statement Bare true.
D. Both statement A and statement Bare false.
(20 Marks]
[2 Marks)
[2 Marks)
[2 Marks)
Problem A4
Which one of the following operations can be performed on a Binary Search Tree (BST)?
[2 Marks]
A. Insertion-adding a node into the BST
B. Deletion-removing a node from the graph
C. Traversal-visiting all nodes in a BST
D. All of the above
1
|
|
3 Page 3 |
▲back to top |
Problem AS
Which one of the following
Fibonacci number?
is a time complexity
of a recurrence
relation for computing the nth
[2 Marks]
A. T(n)= T(n-2) +c
B. T(n)= T(n-1) + T(n-2) +c
C. T(n)= T(n/2) +c
D. none of the above
Problem A6
What is the minimum number of edges a graph with 2 vertices can have?
A.6
B. 9
c.o
D. none of the above
[2 Marks]
Problem A7
What is the maximum number of edges a graph with 5 vertices can have?
A.6
B.9
C. 4
D. none of the above
[2 Marks]
Problem AS
In ..., searching starts at the
Marks]
A. Binary Search
B. Linear Search
C. Jump Search
D. none of the above
beginning
of the list and checks every
element
in the list. [2
Problem A9
..... is the term used to delete an element from stack?
A. Pop
B. Insert
C. sort
D. none of the above
[2 Marks]
Problem AlO
............are a series of instructions
or solve a problem.
A. Graph
B. Algorithm
C. Queue
D. Stack
that are followed,
step by step, to do something useful
[2 Marks]
2
|
|
4 Page 4 |
▲back to top |
SECTIONB: True and False Questions
• Answer all the questions in the provided booklet.
• The section consists of 5 problems.
Problem Bl
Deletion in a queue is performed from the rear.
Problem 82
The Pop() operation is used to insert an element in a queue.
Problem 83
A Stack follows a LIFO (last-in-first-out) rule.
Problem 84
Enqueue and Dequeue operations are associated with stack data structure.
Problem BS
Big-0 is an asymptotic notation.
[10 Marks]
[2 Marks]
[2 marks]
[2 marks]
[2 marks]
[2 marks]
3
|
|
5 Page 5 |
▲back to top |
SECTIONC: Structured questions
• Answer all the questions in the provided booklet.
• The section consists of 17 problems.
Problem Cl
What is a data structure?
[70 Marks]
(2 Marks)
Problem C2
What are the two types or categories of non-primitive data structures?
[2 Marks)
Problem C3
What is a linked-list?
[2 Marks)
Problem C4
Singly linked-list and doubly linked-list are data structures
Provide a graphical representation of singly linked-list and the doubly linked-list using the elements
below in that order.
[8 Marks)
Data= 3, 1, 7
Problem CS
The following are statements to insert an integer element/ data into a static stack.
a. Check if the stack is full
i. If the stack is full, display an appropriate message
b. If the stack is not full
i. Move top to the next index
ii. Insert the element/ data in the stack
[5 Marks)
Taking num as the variable containing the data and n as the size of the stack, write a simple
pseudocode close to a programming language to satisfy all the statements in (a, a.i) and (b, b.i,
b.ii) above.
Problem C6
Write a pseudocode to display() the elements of a static stack in problem CS.
[3 Marks)
Problem C7
Consider the queue below and write a function display() to print all values in the queue.
[6 Marks]
front
rear
-i----••1~ 100
_1_3__._2_10__.----.ai•l~_1_2--1_3_9__0__0.._.:_-"-_-•uI_~"_
100
210
300
4
|
|
6 Page 6 |
▲back to top |
Problem C8
Discussthe difference between merge and Insertion sort algorithms.
[4 Marks]
Problem C9
Consider an array data structure below and answer the questions that follow.
[8 marks]
I I I I I I I I I I I - I 2 4 11 110 111 78 112 1o 16 9 11s 119 7 3 23 133 114 113 -1 s 8 116 7
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
(a). How many elements must be checked to try to find the value 33 in the above array using linear
search?
(b). How many elements must be checked to try to find the value 2 in the above array using linear search?
(c). How many elements must be checked to try to find the value -7 in the above array using linear search?
(d). How many elements must be checked to try to find the value 22 in the above array using linear
search?
Problem ClO
Given that a list has n elements, what would be the best case that could occur when linear searching for
an element?
[2 marks]
Problem Cll
Given that a list has n elements, what would be the worst case that could occur when linear searching for
an element?
[2 marks]
Problem C12
What would be the complexity of the best case for linear search?
[2 marks]
Problem C13
What would be the complexity of the worst case for linear search?
[2 marks]
Problem C14
Given the following array: 12, 18, 10, 14, 17, 8, 5, 11, 7
Provide a logical representation of the Quick sort partition. Use first element as pivot.
[S marks]
Problem C15
Discussthe difference between the linear search and binary search algorithms.
[4 Marks]
Problem C16
Given the following operations of a stack which are performed in that order,
Push(5), push(3), push(l), pop(), pop(), push(7)
(a). Draw a logical representation of a static stack after all the above operations are performed. You must
include the top pointer.
[3 marks]
(b). What will be the output of the pseudocode when the display() function is called?
[2 Marks]
5
|
|
7 Page 7 |
▲back to top |
Problem 17
If you want to create a binary tree whose nodes contain integer values, we can represent the nodes using
the following blue print.
Node
integer data; // value contained in this node
Node leftChild; // left subtree; null if empty
Node rightChild; // right subtree; null if empty
}
Complete the definition of the following method so that it returns the sum of the data values contained
in all of the nodes of the binary tree with root; rootNode. Rewrite the complete method in the provided
booklet by filling the missing code lines. Hint: use Recursion.
[8 Marks]
public int sum(Node rootNode)
{
IF(_______
_
return O
ELSE
return rootNode. ____
+ sum(______
.leftChild) + sum(_, _____
_
ENDIF
********* *** ****** ******* ** **** ** *** End of Exam****************************************
6