ITE6201 Data Structures and Algorithms
(Final Q1, Q2 & Final Exam)
Question 1
Question text
The complexity of bubble sort algorithm.
Question 2
Question text
TREE[1]=NULL indicates tree is _________
Question 3
Question text
The rearranging of pairs of elements which are out of order, until no such pairs remain.
Question 4
Question text
In binary trees, nodes with no successor are called _______________.
Question 5
Question text
Binary search algorithm cannot be applied to _______________.
Question 6
Question text
Trees are ________ if they are similar and have the same contents at corresponding nodes.
Question 7
Question text
These are binary trees with threads.
Question 8
Question text
Every node N in a binary tree T except the root has a unique parent called the ________ of N.
Question 9
Question text
__________________ is putting an element in the appropriate place in a sorted list yields a larger sorted order list.
Question 10
Question text
Sorting algorithm can be characterized as ________________.
Question 1
Question text
Which of the following data structure is non-linear type?
Question 2
Question text
Indicate which structure would be a more suitable choice for each of the following applications.
A program to receive data that is to be saved and processed in the reverse order.
Question 3
Question text
____________________ level is where the model becomes compatible executable code.
Question 4
Question text
The following algorithm is a count-controlled loop going from 1 through 5. At each iteration, the loop counter is either printed or put on a queue depending on the result of Boolean function RanFun(). (The behavior of RanFun() is immaterial.) At the end of the loop, the items on the queue are dequeued and printed. Because of the logical properties of a queue, this algorithm cannot print certain sequences of the values of the loop counter. You are given an output and asked if the algorithm could generate the output.
Set count to 0
WHILE (count < 5)
Set count to count + 1
IF (RanFun())
Write count, ' '
ELSE
Enqueue(myQueue, count)
WHILE (NOT IsEmpty(myQueue))
Dequeue(myQueue, number)
Write number, ' '
The following output is possible using a queue: 1 3 5 4 2
Question 5
Question text
Draw the binary search tree whose elements are inserted in the following order:
50 72 96 94 107 26 12 11 9 2 10 25 51 16 17 95
If Print is applied to the tree formed above, in which order would the elements be printed?
Question 6
Question text
The value in the left child of a node (if it exists) in a binary search tree will be greater than the value in the node itself.
Question 7
Question text
A list may be linear or nonlinear, depending on its implementation.
Question 8
Question text
A binary tree is a tree in which each node can have zero, one, or two children.
Question 9
Question text
The root of a tree is the node that has no ancestors.
Question 10
Question text
Algorithms that use a list must know whether the list is array based or linked.
Question 1
Question text
____________________ level is where the model becomes compatible executable code.
Question 2
Question text
On average, searching in a binary search tree is faster than searching in a list.
Question 3
Question text
A list may be linear or nonlinear, depending on its implementation.
Question 4
Question text
Indicate which structure would be a more suitable choice for each of the following applications.
A program to receive data that is to be saved and processed in the reverse order.
Question 5
Question text
Indicate which structure would be a more suitable choice for each of the following applications.
A program keeping track of where canned goods are located on a shelf.
Question 6
Question text
Which of the following is true about the characteristics of abstract data types?
i. It exports a type.
ii. It exports a set of operations.
Question 7
Question text
Draw the binary search tree whose elements are inserted in the following order:
50 72 96 94 107 26 12 11 9 2 10 25 51 16 17 95
If Print is applied to the tree formed above, in which order would the elements be printed?
Question 8
Question text
A binary search tree whose left subtree and right subtree differ in height by at most 1 unit is called ____________________.
Question 9
Question text
A leaf in a tree is a node with no children.
Question 10
Question text
In a graph, the vertices represent the items being modeled.
Question 11
Question text
The value in the left child of a node (if it exists) in a binary search tree will be greater than the value in the node itself.
Question 12
Question text
Which data structure is suitable to represent the hierarchal relationship between elements?
Question 13
Question text
A stack and a queue are different names for the same ADT.
Question 14
Question text
Which of the following is not the part of ADT description?
Question 15
Question text
A queue displays LIFO behavior.
Question 16
Question text
It is a pile in which items are added at one end and removed from the other.
Question 17
Question text
Which of the following data structure can't store the non-homogeneous data elements?
Question 18
Question text
Which data structure allows deleting data elements from and inserting at rear?
Question 19
Question text
This is very useful in situation when data have to be stored and then retrieved in reverse order.
Question 20
Question text
The root of a tree is the node that has no ancestors.
Question 21
Question text
Indicate which structure would be a more suitable choice for each of the following applications.
A word processor to have a PF key that causes the preceding command to be redisplayed. Every time the PF key is pressed, the program is to show the command that preceded the one currently displayed
Question 22
Question text
Stack is also called the ________________.
Question 23
Question text
Indicate which structure would be a more suitable choice for each of the following applications.
A program to keep track of the soccer teams in a city tournament
Question 24
Question text
Inserting an item into the stack when stack is not full is called ____________ while operation and deletion of item from the stack, when stack is not empty is called ________________ operation.
Question 25
Question text
Binary search trees are ordered.
Question 26
Question text
Indicate which structure would be a more suitable choice for each of the following applications.
A program to maintain the routes in an airline.
Question 27
Question text
Which of the following data structure is non-linear type?
Question 28
Question text
Which of the following data structures is linear type?
Question 29
Question text
Indicate which structure would be a more suitable choice for each of the following applications.
An electronic address book ordered by name
Question 30
Question text
A stack displays FIFO behavior.
Question 31
Question text
Indicate which structure would be a more suitable choice for each of the following applications.
A program to keep track of patients as they check into a medical clinic, assigning patients to doctors on a first-come, first-served basis.
Question 32
Question text
A binary search cannot be applied to a tree.
Question 33
Question text
Algorithms that use a list must know whether the list is array based or linked.
Question 34
Question text
What is written by the following algorithm?
Push(myStack, 5)
Push(myStack, 4)
Push(myStack, 4)
Pop(myStack, item)
Pop(myStack, item)
Push(myStack, item)
WHILE (NOT IsEmpty(myStack))
Pop(myStack, item)
Write item, ' '
Question 35
Question text
____________________ is not the component of data structure.
Question 36
Question text
Which data structure is used in breadth first search of a graph to hold nodes?
Question 37
Question text
Indicate which structure would be a more suitable choice for each of the following applications.
A bank simulation of its teller operation to see how waiting times would be affected by adding another teller.
Question 38
Question text
What is written by the following algorithm?
Enqueue(myQueue, 5)
Enqueue(myQueue, 4)
Enqueue(myQueue, 4)
Dequeue(myQueue, item)
Dequeue(myQueue, item)
Enqueue(myQueue, item)
WHILE (NOT IsEmpty(myQueue))
Dequeue(myQueue, item)
Write item, ' '
Question 39
Question text
Which of the following is non-linear data structure?
Question 40
Question text
Indicate which structure would be a more suitable choice for each of the following applications.
A program to keep track of family relationships
Question 41
Question text
A binary tree is a tree in which each node can have zero, one, or two children.
Question 42
Question text
Identify the data structure which allows deletions at both ends of the list but insertion at only one end.
Question 43
Question text
The value in the right child of a node (if it exists) in a binary search tree will be greater than the value in the node itself.
Question 44
Question text
Herder node is used as sentinel in __________________.
Question 45
Question text
A binary search tree is another name for a binary tree.
Question 46
Question text
Which of the following is/are the levels of implementation of data structure?
Question 47
Question text
A _______________ is a data structure that organizes data similar to a line in the supermarket, where the first one in line is the first one out.
Question 48
Question text
Indicate which structure would be a more suitable choice for each of the following applications.
A dictionary of words used by a spelling checker to be built and maintained.
Question 49
Question text
The following algorithm is a count-controlled loop going from 1 through 5. At each iteration, the loop counter is either printed or put on a queue depending on the result of Boolean function RanFun(). (The behavior of RanFun() is immaterial.) At the end of the loop, the items on the queue are dequeued and printed. Because of the logical properties of a queue, this algorithm cannot print certain sequences of the values of the loop counter. You are given an output and asked if the algorithm could generate the output.
Set count to 0
WHILE (count < 5)
Set count to count + 1
IF (RanFun())
Write count, ' '
ELSE
Enqueue(myQueue, count)
WHILE (NOT IsEmpty(myQueue))
Dequeue(myQueue, number)
Write number, ' '
The following output is possible using a queue: 1 3 5 4 2
Question 50
Question text
The following algorithm is a count-controlled loop going from 1 through 5. At each iteration, the loop counter is either printed or put on a queue depending on the result of Boolean function RanFun(). (The behavior of RanFun() is immaterial.) At the end of the loop, the items on the queue are dequeued and printed. Because of the logical properties of a queue, this algorithm cannot print certain sequences of the values of the loop counter. You are given an output and asked if the algorithm could generate the output.
Set count to 0
WHILE (count < 5)
Set count to count + 1
IF (RanFun())
Write count, ' '
ELSE
Enqueue(myQueue, count)
WHILE (NOT IsEmpty(myQueue))
Dequeue(myQueue, number)
Write number, ' '
The following output is possible using a queue: 1 3 5 2 4