ADMASUNIVERSITY

DepartmentComputerScience
Data Structure and Algorithm

Name:
ID.No.:
Section: Timeallowed: 1:00Hrs.
Instructor:

Instructions

This Examination Paper consists of three parts on 7 pages with answer sheets (excluding
WriteyourNAMEandIDonbothquestionpaperandanswersheet.
AnyattempttocheatandcheatwillsubjecttoGradeFresult.
Putallyouranswersontheattachedanswersheetonly.
Switchoffyourmobilephones.
Thisexaminationisclosedbookexam.
Makeyourhandwritinglegible
 PARTI:TrueOrFalseItems(10pts)
Instruction:-Readeachstatementcarefully.Writetrueifthestatementiscorrectandfalseif the
statement is not correct on the space provided

1. Queue is a simple data structure, in which insertion and deletion occur at the same end.
2. Linked list uses two pointers/indices to keep track of information/data.
3. A binary search tree: the values in any left subtree are less than the value in its parent node, and the values in
any right subtree are greater than the value in its parent node.
4. In Queue, the operation Peek() returns the value of the rear element.
5. Every node in a linked list has two components: one to store the relevant information and one to store the
address.
6. The link component of each node is a pointer.
7. In a Full Binary Tree, each node has either 0 or 2 children.
8. Binary searching algorithms work only on an ordered list.
9. Sorting is a process of looking for a specific element in a list of items or determining that the item is not in the
list.
10. Algorithm analysis refers to the process of determining the amount of computing time and storage.

PARTII:MultipleChoiceItems(20pts)
Instruction:-Readeachstatementcarefully.Choosethecorrectanswerfromthegivenchoices. Write the
letter of your answer on the space provided

Here is the corrected version with proper spacing and formatting:

1) What happens when you push a new node onto a stack?

A) The new node is placed at the front of the linked list.

B) The new node is placed at the back of the linked list.
C) The new node is placed in the middle of the linked list.
D) No change happens.

2) Merge Sort can be categorized into which of the following?

A) Brute Force technique

B) Divide and conquer
C) Greedy algorithm
D) Dynamic programming

3) The sequence of computational steps to solve a problem is called:

A) Data Structure
B) Algorithm
C) Data
D) None

2
4) The postfix form of A * B + C / D is?

A) AB/CD+
B) ABCD/+
C) ABC+/D
D) ABCD+/

5) The pointer in a node points to:

A) The data part of a node

B) The count part of a node
C) The pointer part of the node
D) The whole node

6) If the elements "A", "B", "C" and "D" are placed in a queue and are deleted one at a time, in what order will
they be removed?

A) ABCD
B) DCBA
C) DCAB
D) ABCD

7) Suppose we have a given list L = {7, 14, 12, 33, 5, 19}, and we need to sort this list in ascending order using
Bubble Sort. What will be the list after the completion of the second iteration?

A) 7, 12, 14, 33, 5, 19

B) 7, 12, 14, 5, 19, 33
C) 7, 12, 5, 14, 19, 33
D) 7, 12, 14, 5, 19, 33

8) In a stack, if a user tries to remove an element from an empty stack, it is called:

A) Underflow
B) Empty collection
C) Overflow
D) Garbage Collection

9) In a node type named MyNode, which of the following correctly declares a pointer named ptr to a node of that
type?

A) MyNode* ptr;
B) MyNode ptr;
C) ptr myNode*;
D) MyNode.data* ptr;

10) Consider the following array:

int num = {14, 33, 27, 10, 35, 19, 42, 44};
After three passes of selection sort, what would be the content of the array?
A) {10, 14, 19, 27, 33, 35, 42, 44}
B) {10, 33, 27, 14, 35, 19, 42, 44}
3
C) {10, 14, 19, 33, 35, 27, 42, 44}
D) {14, 27, 33, 44, 42}

11) While searching in a binary tree, how should the index move?

A) If the searching key is less than the root, go to the right.

B) If the searching key is greater than the root, go to the left.
C) If the searching key is equal to the root, go to the left.
D) None

12) A linear list of elements in which deletion can be done from one end and insertion can take place only at the
other end is known as:

A) Queue
B) Stack
C) Tree
D) Linked List

13) Let us say the initial contents of a stack have the elements ‘V, W, Z, Y, X’ from bottom to top. To get the new
configuration ‘V, W, X, Y, Z’, one needs a minimum of:

A) 3 push and 4 pop operations

B) 3 pop and 4 push operations
C) 3 pop and 3 push operations
D) 3 pop and 2 push operations
E) 5 pop and 5 push operations

14) A binary tree in which all leaf nodes are at the same level is called:

A) Full binary tree

B) Complete binary tree
C) Perfect binary tree
D) Balanced binary tree

15) Which of the following is true about Binary Trees?

A) Every binary tree is either complete or full.

B) Every complete binary tree is also a full binary tree.
C) Every full binary tree is also a complete binary tree.
D) None

16) A Binary Tree can have:

A) 2 children
B) 1 child
C) 0 children
D) All of the above

4
17) Inserting an item into the stack when the stack is not full is called a push operation, and deleting an item
from the stack when the stack is not empty is called a pop operation.

A) Push, pop
B) Pop, push
C) Insert, delete
D) Delete, insert

18) Which of the following statements is true?

A) The binary search algorithm is less efficient than the linear search, but it requires that the array be sorted.
B) The binary search algorithm is more efficient than the linear search, but it requires that the array be sorted.
C) The binary search algorithm is more efficient than the linear search, but it requires that the array be unsorted.
D) The binary search algorithm is less efficient than the linear search, but it requires that the array be unsorted.

19) What are the correct intermediate steps of the following dataset when it is being sorted with the Bubble
Sort?

Dataset: 15, 20, 10, 18

A) 15, 10, 20, 18 → 15, 10, 18, 20 → 10, 15, 18, 20

B) 10, 20, 15, 18 → 10, 15, 20, 18 → 10, 15, 18, 20
C) 15, 20, 10, 18 → 15, 10, 20, 18 → 10, 15, 20, 18 → 10, 15, 18, 20
D) 15, 18, 10, 20 → 10, 18, 15, 20 → 10, 15, 18, 20 → 10, 15, 18, 20

20) In order to get the information stored in a binary search tree in descending order, one should traverse it in
which of the following order?

A) Left, parent, right

B) Right, parent, left
C) Parent, left, right
D) Right, left, parent

21) Using binary search, what is the maximum number of comparisons required to find a search key in a 31-
element sorted array?

A) 4
B) 5
C) 32
D) 1

22) What does each iteration of the insertion sort algorithm do?

A) Each iteration takes the next smallest element and inserts it at the beginning of the array.
B) Each iteration takes the next element in the unsorted portion of the array and inserts it into the sorted portion.
C) Sorted subarrays are inserted into the larger array.
D) Each iteration determines the location of a pivot and inserts it into place.

5
PartIII:AnswerthefollowingQuestionsbriefly{20pts)
Instruction:-Readeachstatementcarefully.Writeappropriateansweronthespaceprovidedand youranswer should be
clear and neat.

1. Consider the following array:

2. int list[] = {9, 24, 3, 14, 16, 7, -11, 12, 1};

Apply the insertion sort algorithm to sort the given array list in ascending order. [3 Pts.]

3. Given the following infix expression:

4. A – B + (C / D + E) * E – F + G

Change the given infix expression to postfix expression. [3 Pts.]

5. Consider the following list of integers:

6. L = {20, 30, 5, 15, 26, 16, 38, 42, 52, 19, 43, 2, 4, 3, 8}

A) Create a binary search tree (BST) by inserting the elements in the given order. (2 Pts.)
B) Perform the following traversals on the BST and write down the sequence of elements visited during each
traversal. (2 Pts. each)

o I. Preorder traversal
o II. Postorder traversal
o III. Inorder traversal
7. You are developing a student record management system and need to implement a stack to store student
records. Each student record consists of the student's Name, ID, and Result. Write the function that can be
used to perform the above requirement. (4 Pts.)

8. Discuss the following ADT elements and their basic operations used by each ADT, and specify how these
operations work. (6 Pts.)
A) Stack
B) Queue
C) Linked List

6
 ADMASUNIVERSITY
DepartmentComputerScience
DataStructureandAlgorithm
Makeup FinalExam
Name: -
ID. No: TotalWeight: 50%
Section: Time allowed: 1:00Hrs.
Instructor:

Answersheet
PartI
1 6
2 7
3 8
4 9
5 10

PartII
1 6 11 16
2 7 12 17
3 8 13 18
4 9 14 19
5 10 15 20

21

22

7
AnswerSheet forWorkout Questions

8
9
1
0