 |
DSA610S - DATA STRUCTURES AND ALGORITHMS - JULY 2019 - 2ND OPP |
|
|
1 Page 1 |
▲back to top |
NAMIBIA UNIVERSITY
OF SCIENCE AND TECHNOLOGY
Faculty of Computing and Informatics
Department of Computer Science
QUALIFICATION : Bachelor of Computer Science, Bachelor of Informatics
QUALIFICATION CODE: 07BACS, 07BAIF
LEVEL: NQF 6
COURSE: Data Structures and Algorithms
DATE: July 2019
COURSE CODE: DSA610S
SESSION: 2
DURATION: 3 Hours
MARKS: 100
SECOND OPPORTUNITY/SUPPLEMENTARY EXAMINATION QUESTION PAPER
EXAMINER(S)
MR MIKE ABIA
DR CAMERON MACRAE
MR JEREMIA LUMBASI
MR HERMAN KANDJIMI
MR VEERABHADRAM PADURI
MR STEVEN TJIRASO
MODERATOR
PROF. JOSE QUENUM
THIS QUESTION PAPER CONSISTS OF 4 PAGES
(Excluding this front page)
INSTRUCTIONS
Respond to ALL problems in sections A, B and C.
Use the examination script booklet provided.
Each section must be started on a new page.
NUST examination rules and regulations apply.
Follow instructions in the examination script booklet.
Write clearly and neatly.
|
|
2 Page 2 |
▲back to top |
SECTION A: Multiple Choice
e Respond to ALL problems in this section.
e Select the best option in each of the problems in this section.
e Your responses must be written in the answer booklet provided.
e Marks to each question or part of question are given in [ ].
[20 marks]
Problem A1
Which one of the below mentioned data structures is a linear data structure?
A. Binary tree
B. Binary search tree
C. Graph
D. Queue
(2 marks]
Problem A2
Which of the following statements 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 B is false.
B. Statement A is false, and statement B is true.
C. Both Statement A and Statement B are true.
D. Both Statement A and Statement B are false.
[2 marks]
Problem A3
Which of the following algorithms makes use of the divide and conquer approach to solving a
problem?
A. Binary search tree
B. Binary search
C. Program
D. Graph
[2 marks]
Problem A4
Which of the following operations can be performed ona graph?
A. Insertion-adding an element to the graph
B. Deletion-removing an element from the graph
C. Search-seek for an element in a given graph
D. All of the above
[2 marks]
Problem A5
An algorithm can be represented using the following.
A. Pseudo code
B. Flow chart
C. None of the above
D. BothAandB
[2 marks]
Problem A6
If the number of records to be sorted is small, then
sorting can be efficient.
A. Binary
B. Insertion
C. Selection
D. Bubble
[2 marks]
|
|
3 Page 3 |
▲back to top |
Problem A7
Given a binary search tree, which traversal type would print the values in the nodes in sorted order?
A. Pre-order
B. Post-order
C. In-order
D. level order
{2 marks]
SS Oe Problem A8&
After deleting the key 77, which key replaces it if the tree is to maintain its binary search property?
41
47
80
52
[2 marks]
Problem A9
IfT is a binary search tree storing 128 elements. What is the biggest possible height of T?
A. 125 0r126
B. 127 0r128
C. 129 or 130
D. 131 0r132
[2 marks]
Problem Ai0
Bubble sort is similar to selection sort in the sense that
A. Both algorithms compare every element of the list with its predecessor only if the
predecessor of the given element exists.
B. Both algorithms sort the list by pushing the biggest or the smallest element to the
extreme end of the list.
Both algorithms are used in the binary search algorithm.
D. None of the above answers.
{2 marks]
|
|
4 Page 4 |
▲back to top |
SECTION B
e Respond to ALL problems in this section
e Clearly mark each of the following assertions as true (T) or false (F)
e Your responses must be written in the answer booklet provided.
e Marks to each question or part of question are given in [].
[20 marks]
Problem B1
A doubly-linked list is a linear data structure.
[2 marks]
Problem B2
It is not sensible to discuss depth-first and breath-first searches in linear data structures. [2 marks]
Problem B3
A stack follows a LIFO (last-in-first-out) rule.
{2 marks]
Problem B4
Push and pop operations are associated with queue data structure.
{2 marks]
Problem B5
Probabilistic complexity represents the probability of an algorithm processing input in a specific
time.
[2 marks]
Problem B6
An algorithm is needed for every useful computer program.
[2 marks]
Problem B7
Arrays can store homogeneous data elements.
(2 marks]
Problem B8
Big-O and Big-O (Big-Theta) are both asymptotic notations.
[2 marks]
Problem B9
A queue is a first-in-last-out (FILO) data structure.
[2 marks]
Problem B10
Singly-linked lists and doubly-linked lists have no root node.
[2 marks]
|
|
5 Page 5 |
▲back to top |
SECTION C
e Respond to ALL problems in this section.
e Your responses must be written in the answer booklet provided.
e Marks to each question or part of question are given in [ ].
Problem C1
The following sequence of numbers needs to be sorted in descending order:
17,14,11,15,18,12,10,13,9,16. Copy and complete the table below:
Sequence after 1 swap
Sequence after 2 swaps
Sequence after 3 swaps
Sequence after 4 swaps
Selection Sort
[60 marks]
[20 marks]
Problem C2
[10 marks]
Binary search was used to search for an element in a list of elements. The element searched was
found at position 3 after visiting 3 elements (including element at position 3). Assume the position
numbers start at position 1.
a. Give the number of elements that were in the list if no rounding was necessary in the
calculations.
(3 marks]
b. Give the number of elements that were in the list if rounding down was necessary three
times in the calculations.
[7 marks]
Problem C3
[30 marks]
Given the following sequence of keys: 63 28 51 53 80 35 57 61 42 81;
a. Construct a binary search tree (BST), start with the first key in the sequence (63) as the root
and proceed from left to right of the sequence.
[10 marks]
b. Give the pre-order traversal of the BST. Your answer should be a sequence of 10 integers,
separated by whitespace.
[10 marks]
c. Give the in-order traversal of the BST. Your answer should be a sequence of 10 integers,
separated by whitespace.
[10 marks]
eREKE
of Paper****