 |
DSA711S - DATA STRUCTURES AND ALGORITHMS 2 - 2ND OPP- JULY 2025 |
|
|
1 Page 1 |
▲back to top |
n Am I BI A u n IVER s ITY
OF SCIEnCE Ano TECHnOLOGY
FACULTY OF COMPUTING AND INFORMATICS
DEPARTMENTOF SOFTWAREENGINEERING
QUALIFICATION: BACHELOROF COMPUTERSCIENCE
QUALIFICATION CODE: 07BCHS
LEVEL: 7
COURSE:DATA STRUCTURESAND ALGORITHMS2
COURSECODE: DSA711S
DATE:JULY2025
PAPER:THEORY
DURATION: 2 HOURS
MARKS: 100
SECONDOPPORTUNITY/SUPPLEMENTARYEXAMINATION QUESTIONPAPER
EXAMINER
PROFAMBROSE AZETA
MODERATOR:
MRS P. DOLIAN
INSTRUCTIONS
1. Answer ALL the questions.
2. Read all the questions carefully before answering.
3. Number the answers clearly.
THIS QUESTION PAPERCONSISTSOF 6 PAGES
(Including this front page)
PERMISSIBLEMATERIALS
1. NON-PROGRAMMABLECALCULATOR
1
|
|
2 Page 2 |
▲back to top |
SECTION A: TRUE OR FALSE
This section consists of 15 questions. Answer all the questions
Each correct answer is allocated 2 Marks
Write True or False for Questions 1 to 15.
Study the Trees below in Figures a, band c, and use them to answer the questions in Al, A2, A3
2- -)
Figure a
@
G)
3
Figure b
G{~6
c£
Figure c
Al: Figure a, is a Binary Search Tree {BST)
[2 Marks]
A2: When 5 is inserted in BSTFigure b, the resulting tree will not be the BSTin Figure c. [2 Marks]
A3: Figure c is a Binary Search Tree
[2 Marks]
A4: AVL is a type of Balanced Binary search tree
[2 Marks]
AS: 1-6-2 Search Trees is a type of tree in Data Structures
[2 Marks]
AG: Repeated search of half of binary tree is done in binary search tree algorithm to
find a key/element.
[2 Marks]
A7: Deletion is not one of the operations of binary search trees
AS: Bloom filters is one of the examples of probabilistic data structures
A9: Linear probing is one of the methods for resolving collision in hashing
[2 Marks]
[2 Marks]
[2 Marks]
AlO: The output of the input statement: txt= "aabaacaadaabaaba", pat= "aaba"
is: [9, 0, 12] in pattern matching
[2 Marks]
All: Insertion and deletion have the same worst case time complexity in B-trees and AVL trees.
[2 Marks]
Al2: Every node will always have 2 or 3 children/sons in binary tree.
[2 Marks]
Al3: It is possible for a balanced BSTto turn to unbalanced BSTafter deleting a node [2 Marks)
A14: The time complexity of naive pattern matching algorithm is O{m/n)
[2 Marks)
AlS: A Balance Factor (BF) is the difference between the heights of left and right subtrees
[2 Marks)
2
|
|
3 Page 3 |
▲back to top |
SECTION B: MULTIPLE CHOICE QUESTIONS (MCQs)
This section consists of 20 MCQs. Answer all the questions
Select only one option, each correct answer is allocated 2 Marks
Bl: A Each position of the Hash table is often called
A. Slot
B. Variable C. Identifier
D. HashMe
B2: One of the following defines an unbalanced BST
A. A BST is unbalanced if the difference between the height of left and right subtree for every
node is more than 1.
B. A BST is unbalanced if the difference between the height of left and right subtree for every
node is less than 1.
C. A BST is unbalanced if the difference between the height of left and right subtree for every
node is more than 2.
D. A BST is unbalanced if the difference between the height of left and right subtree for every
node is more than
Figure 2
B3: When 7 is deleted from the above Tree in Figure 2, is the Tree a BST? Yes or No
B4: When 7 is deleted from the above Tree in Figure 2, is the Tree AVL? Yes or No
BS: When 7 is deleted from the above Tree in Figure 2, is the Tree Red-Black Tree ? Yes or No
BG:When 7 is deleted from the above Tree, is the Tree a 2-3 Tree ? Yes or No
B7. What will be the output of the following program?
main()
{
char str[]="san foundry";
int len = strlen(str);
inti;
for(i=O;i<len;i++)
push(str[i]); // pushes an element into stack
for(i=O;i<len;i++)
pop(); //pops an element from the stack
A. yrdnuof nas
B. foundry nas
C. sanfoundry
D. san foundry
3
|
|
4 Page 4 |
▲back to top |
88. Which of the following is an advantage of a hash table in data structures?
A. Complex to implement
B. Faster access of data
C. Exhibit low locality of reference
D. Very inefficient for less number of entries
89. Postorder of the Tree in Figure c gives:
A. 6,2,14,3,8,7,5,9
B. 1,3,4,2,5,7,9,8,6 C. 1,2,3,4,6,5,7,8,9 D. 112233344455566
810: If at any time a BSTis not balanced, to restore the properties of AVL Trees, re-balancing is
done using
A. Rotation
B. Rotation and/or Exchange of colour red/black
C. Upward Promotion and/or Splitting D. None
811: Which of the following is the most widely used external memory data structure?
A. AVL tree
B. B-tree
C. Red-black tree
D. Both AVL tree and Red-black tree
812: If at anytime a SSTis not balanced, to restore the properties of Red-Black Trees, re-balancing is
done using
A. Rotation
B. Rotation and/or Exchange of colour red/black
C. Upward Promotion and/or Splitting D. None
B13: The best-case time complexity for search, insertion, and deletion in an AVL tree is:.
A. O(log n)
B. O(n)
C. Log (n)
D. Log (On)
B14: One of the following is the result of factorial (n) or n ! where n = 4
A. 2
B. 24
C.6
D. 120
B15: What is a data structure?
A. A programming language
B. A collection of algorithms and codes
C. A way to store and organize data
D. A type of computer hardware
816: In developing a dynamic programming solution, the following are/is not included in the
steps:
A. Characterise the structure of an optimal solution
B. Recursively define the value of an optimal solution
C. Compute the value of an optimal solution
D. All of the above
817:
In pattern
matching, the
output
of the
statement:
Input: txt
=
11abcab
11
,
pat=
A. [O, 3]
B. [3, O]
C. [1, 3]
D. [3, 1]
"ab" will give:
4
|
|
5 Page 5 |
▲back to top |
B18: In pattern matching, the string below would give the output:
Input:
main String: "AAAABCAAAABCBAAAABC"
pattern: "AAABC"
Output:
A. [1, 7, 15]
B. [7, 1, 14]
C. [1, 7, 14]
D. [1, 7]
B19: If the following elements are inserted into BST:21, 11, 32
Is the tree a balanced BST? Yes or No
B20: If the following elements are inserted into BST: 21, 3, 11
Is the tree an AVL?
Yes or No
SECTION C: STRUCTURED/THEORY QUESTIONS
This section consists of 3 questions. Answer ALLthe questions
Each correct answer is allocated 10 Marks
Question One [10 Marks]
(A) Insert 4 and 9 separately one after the order in the 2-3 B Tree below, show the new
trees at every step.
(5 Marks)
3
37 51
(B) Differentiate between KMP Algorithm for pattern matching and dynamic programming
with example(s)
(5 Marks)
Question Two [10 Marks]
(A) (i) Create and insert the following elements in a BST:14, 26, 35.
(ii) If the BSTan AVL? If Yes, then stop and do nothing.
If No, then do re-balancing using ROTATION.
Mention the ROTATIONapplied.
(5 Marks)
(5 Marks)
5
|
|
6 Page 6 |
▲back to top |
(B) Show how Hashing can be used to store the following elements: 55, 47, using a
Hash table of size 5.
(5 Marks)
(i)
Describe what happens when you want to insert a new element 33.
(ii) Use two methods - chaining and linear probing to resolve any collision.
Question Three [10 Marks]
(A) Create and insert the following elements in a BST:6, 40, 25
Is the BSTan AVL? If Yes, then stop and do nothing.
If No then do re-balancing using ROTATION.
(5 Marks)
(B) Use insertion operation to create a 2-3 B Tree from the following elements: 6, 13, 4, 70, 40, 80
(5 Marks)
---THE
END
6