Data Structures and Algorithms Analysis Exam - CP 213
THE UNIVERSITY OF DODOMA
OFFICE OF THE DEPUTY VICE CHANCELLOR ACADEMIC, RESEARCH AND CONSULTANCY
COLLEGE OF INFORMATICS AND VIRTUAL EDUCATION
Department of Computer Science and Engineering
End of Semester One University Examination for the 2020/2021 Academic Year
Course Name: Data Structures and Algorithms Analysis
Paper Code Number: CP 213
Date of Examination: 25th March, 2021
Time: 03:30 PM - 06:30 PM
Duration: 3 Hours
Venue(s): CIVE - AUDITORIUM
Sitting Programme(s): CS2, SE2, CNISE2, CE2, TE2, CSDFE2
INSTRUCTIONS TO CANDIDATES
i. This examination paper consists of TWO (2) sections with SEVEN (7) questions in FOURTEEN (14) printed pages.
ii. Answer all questions in Sections A and THREE (3) questions in Section B.
iii. The total score for this examination is 60 points. Marks are allocated at the end of each question.
iv. ALL responses should be written in the answer book provided. Insert the examination paper into the answer book after the examination. Students should not take any examination paper(s) out of the examination room.
v. All regulations guiding the administration of university examinations apply.
SECTION A: (15 MARKS)
Question One
- Read each question carefully and choose the most correct response. (0.5 Marks Each)
i. Which of the following uses FIFO method?
A) Queue
B) Stack
C) Hash Table
D) Binary Search Tree
E) Binary Tree
ii. Linked list search complexity is
A) O(n)
B) O(1)
C) O(log n)
D) O(log log n)
E) O(log2n)
iii. Shell sort uses
A) merge sort
B) quick sort
C) selection sort
D) insertion sort
E) bubble sort
iv. Depth First Search is equivalent to which of the traversal in the Binary Trees?
A) Post-order Traversal
B) Level-order Traversal
C) Pre-order Traversal
D) In-order Traversal
E) Breadth First Search
v. The Data structure used in standard implementation of Breadth First Search is?
A) Queue
B) Linked List
C) Tree
D) Stack
E) Double Linked List
vi. Time complexity of DFS is? (V - number of vertices, E - number of edges)
A) O(V+E)
B) O(V)
C) O(E)
D) O(V*E)
E) O(V/E)
vii. Breadth First Search is equivalent to which of the traversal in the Binary Trees?
A) Pre-order Traversal
B) Post-order Traversal
C) Level-order Traversal
D) In-order Traversal
E) Depth First Search
viii. Time complexity of Breadth First Search is? (V – number of vertices, E – number of edges)
A) ( O(V + E) )
B) O(V)
C) ( O(E) )
D) O(V*E)
E) O(V/E)
ix. Data structure that contains a relationship between a pair of elements, this is not necessarily hierarchical in nature
A) Tree
B) String
C) Graph
D) Array
E) Structure
x. Which of the following involves arranging the records in a logical order?
A) Merging
B) Sorting
C) Traversing
D) Searching
Question Two
- Match the item in Column A with its corresponding item in Column B. (0.5 Marks Each)
| COLUMN A | COLUMN B |
|---|---|
| i. Combines record into different sorted files into a single file | A) Linear search |
| ii. A set of data values and associated operations that is specified accurately, independent of any particular implementation. | B) Merging |
| iii. It is not a primitive data type. | C) Edges |
| iv. A data structure which is very useful in situation when data have stored and then retrieved in reverse order. | D) Deletion |
| v. A data structure which can store the non-homogeneous data element. | E) False |
| vi. A search that start at the beginning of the list and check every element in the list. | F) Array |
| vii. An operation that is implemented similarly in both queue and stack. | G) Structure |
| viii. The name given to nodes in a graph. | H) Data structure |
| ix. It defines the way in which the data item or items are logically related. | I) Abstract data type |
| x. In linked list, Pointers store the next data element of a list. | J) Vertices |
| K) True | |
| L) Stack | |
| M) Insertion |
Question Three
- With the aid of a code segment, briefly describe the following flow of control as used in structure:
i. Recursive functions (2 Marks)
ii. Sentineal while loop (2 Marks)
iii. Points (1 Mark)
SECTION B: (45 MARKS)
Attempt THREE (3) out of FOUR (4) questions provided.
Question Four
- Members from computer programming club at the University of Dodoma were doing a computer programming challenge. A linked list of four nodes as Figure 1 was displayed to the members. Consider yourself as a member of the club, take into account the given structure definition below.
struct attendeeCard
{
int card_no;
struct attendeeCard * next;
};Figure 1: Singly Linked List
Write a piece of code to perform the following operations on Figure 1:
(Hint: use card as the node name, each operation should be performed on the original Figure 1)
i. Insert a new node at the beginning of the list. (3 Marks)
ii. Insert a new node between cards with card_no 7 and 40. (3 Marks)
iii. Delete the last node. (3 Marks)
iv. Delete a card with card_no 7. (3 Marks)
v. Display all card_no stored. (3 Marks)
Question Five
- Binary tree is a graph with special characteristics that gives it distinct features from normal trees and other graphs. Figure 2 and Figure 3 gives the diagrammatical difference between a graph and a binary tree.
Figure 2: Directed graph
Figure 3: Binary Tree
i. Consider Figure 2 to answer the following questions:
(a) Demonstrate the use of stack in performing Depth First Search (4 Marks)
(b) Demonstrate the use of queue in performing Breadth First Search (4 Marks)
ii. Consider Figure 3 to state:
(a) Level order traversal (1 Mark)
(b) In-order traversal (2 Marks)
(c) Post-order traversal (2 Marks)
(d) Pre-order traversal (2 Marks)
Question Six
- Given array A as shown Figure 4.
Figure 4: Unsorted array
i. If 56 is taken as pivot (piv = A[high]) and lower bound (lb) and upper bound (ub) are set to lb = A[low]; and ub = A[high] respectively. Using the partition pseudocode of quick sort given below:
partition(A[], low, high)
{
piv = A[high];
i = (low - 1);
for(j = low; j < high-1; j++)
{
if(A[j] <= piv)
{
i++;
swap A[i] and A[j];
}
}
swap A[i+1] and A[high];
return (i + 1);
}Show:
(a) The value of the lower bound (lb) and the upper bound (ub) when the first swap will have to take place
(b) The value of the lb and ub when the second swap will have to take place
(c) The return value of the code.
ii. Write a piece bubble sort code to sort the array A.
Question Seven
- Queue and stack data structure have various technical application in our daily life.
i. Consider Figure 5 which indicate a four node linked list created from the given structure definition below, and the node name as student.
struct StudentWeight
{
float weight;
StudentWeight * next;
};Figure 5: Linked list with 4 nodes
(a) Assume Figure 5 is a stack;
a) Write a piece of code to push two students weighted 39 and 65. (3 Marks)
b) If after an operation in 7 i (a) a) the nodes take addresses 500 and 600, sketch the resultant stack. (1 Mark)
(b) Assume Figure 5 is a queue;
a) Write a piece of code to enqueue two students weighted 49 and 71. (3 Marks)
b) If after an operation in 7 i (b) a) the nodes take addresses 500 and 600, sketch the resultant stack. (1 Mark)
ii. Using stack concept, show each step you will pass to respond to the following questions
(a) Covert the following infix expression into postfix A * (B + C * D) + E (4 Marks)
(b) Evaluate the following postfix expression 22842 - / * + 10 - (3 Marks)
END OF EXAMINATION PAPER