 |
DSA521S - DATA STRUCTURES AND ALGORITHMS 1 - 2ND OPP - JULY 2022 |
|
|
1 Page 1 |
▲back to top |
n Am I BIA u n IV ERs ITY
OF SCIEnCE Ano TECHn OLOGY
FACULTY OF COMPUTING AND INFORMATICS
DEPARTMENT OF COMPUTER SCIENCE
QUALIFICATION: BACHELOR OF COMPUTER SCIENCE, BACHELOR OF INFORMATICS
QUALIFICATION CODE: 07BCMS, 07BAIT
LEVEL: 5
COURSE: DATA STRUCTURESAND ALGORITHMS 1
COURSE CODE: DSA521S
DATE: JULY 2022
PAPER:THEORY
DURATION: 1 HOUR
MARKS: 50
SECOND OPPORTUNITY /SUPPLEMENTARY EXAMINATION QUESTION PAPER
EXAMINER(S)
Mr S. TJIRASO
MODERATOR:
Ms S. CHIVUNO-KURIA
INSTRUCTIONS
1. Answer ALL the questions.
2. Read all the questions carefully before answering.
3. Number the answers clearly
THIS QUESTION PAPER CONSISTS OF 5 PAGES
(Including this front page)
|
|
2 Page 2 |
▲back to top |
SECTION A: Multiple Choice Questions [15 Marks]
• Answer all the questions in the provided booklet.
• The section consists of 15 questions.
1. ___
Data structure does not require its size to be specified in advance
A. Linked list
B. Array
C. Both A & B
D. None of the above
2.
_is the term used to insert an element in the Queue?
A. Pop
B. Dequeue
C.Enqueue
D. Push
3.
When trying to delete data from a stack, but the stack is empty; this situation is usually
called ...
A. Underflow
B. Overflow
C. Full Capacity
D. Error
4.
A binary tree has n levels where level zero is the level of the root. And n denotes the last
level. Given that the root has only one child, what is the minimum number of leaves of level n of
the tree?
A.4
B. 1
C. 8
D. -1
5.
Given a list of elements; 3, 12, 6,16,9 inserted into a data structure in that order. An
element is deleted using a basic data structure operation. If the deleted element is 9, the data
structure cannot be a
.?
A. Queue
B. Tree
C. Stack
D.Graph
6.
In __ search, start at the beginning of the list and check every element in the list.
A. Binary Search
|
|
3 Page 3 |
▲back to top |
B. Linear Search
C. Bubble Search
D. Jump Search
7.
A_is an ordered collection of items from which the items may be deleted from one end
(front end) and items may be inserted at the other end (rear end).
A. Binary Search
B. Array
C. Stack
D. Queue
8. Given the following tree. Give the Preorder traversal.
A. ABDHIECGFS
B. HDIBEAFCJG
C. HIDEBFSFCA
D. ABDHIECFGS
9. What are the applications of Stack?
A. Queues in routers/switches
B. check parenthesis matching in an expression
C. Process scheduling
D. Shared resource
10. The time complexity of Binary Search Tree (BST) is
A. O(n)
B. O(log n)
C. O(h)
D. O(n log n)
11. Which of the following is/are the levels of implementation of data structures?
A. Abstract level
B. Application level
|
|
4 Page 4 |
▲back to top |
C. Implementation level
D. All the above
12. _is not a component of data structures and algorithms.
A. Operations
B. Storage Structures
C. Algorithms
D. None of the above
13. Two vertices in a graph are said to be adjacent vertices (or neighbours} if there is a path of
length __ connecting them.
A. At least 1
B. At least 2
C. At least less than 2
D. l
14. If an array is sorted, it is recommended to use __
A. Sequential
B. Binary
C. Sentinel
D. Probability
search to search it.
__ 15. If the node to be deleted has
_, we delete the node and attach the left subtree to the
deleted node's parent.
A. Only a left subtree
B. Only a right subtree
C. No children
D. Has no children
SECTION B: Structured Questions [35]
• Answer all the questions in the provided booklet.
• The section consists of 5 questions.
2.1. Briefly discuss Give the difference between the following terms as used in Data Structures:
1. Queue and Array
[4]
2. Binary search and Linear search algorithms
[4]
2.2. Given the following array {20, 30, 60, 100, 90, 50, 130, 210, 160, 110}. Construct a Binary
Search Tree (BST} . Using Postorder traversal.
[10]
|
|
5 Page 5 |
▲back to top |
2.3. Study the BSTbelow:
1. Delete the following nodes: 2, 5 and 50 and draw the new BST.
[4]
b. What is the maximum height/level of the BSTafter the operations in (a}?
[2]
2.4. Study the Flowchart below.
S=(A+B+C}.!2.0
Area=sqrt[ SI(!S·A)x(S-Bjx(S-C))
Perim:t:r-A+B+c
Write a pseudocode corresponding to the Flowchart program above.
[5]
2.5. Use the Insertion sort algorithm to sort the array below: 4,3,2,10,12,1,5,6. Show content for
each step.
[6]
**************************** End of the Paper***********************************