The dummy header in linked list contains ____________________.
b. first record of the actual data
Which of the following is an application of stack?
c. all of these
This refers to a linear collection of data items.
b. List
In linked representation of stack, ___________ fields hold the elements of the stack.
d. INFO
Which of the following is two way lists?
c. List traversed in two directions
This is a linear list in which insertions and deletions are made to form either end of the structure.
c. Dequeue
This indicates the end of the list.
a. Last pointer
Value of first linked list index is _______________.
c. 0
This form of access is used to add/remove nodes from a stack.
c. LIFO
A linear list in which the pointer points only to the successive node.
a. singly linked list
The term push and pop is related to _____________.
c. stacks
Each node in singly linked list has _______ fields.
c. TOP
This is the term used to delete an element from the stack.
c. Pop
What is a run list?
d. small batches of records from a file
In linked lists, there are no NULL links in ______________
d. circular linked list
Stack follows the strategy of ________________.
a. LIFO
A pointer variable which contains the location at the top element of the stack.
a. Top
In a linked list, the ____________ contains the address of next element in the list.
a. Link field
In the linked representation of the stack, __________ pointer behaves as the top pointer
variable of stack.
d. Start
What is a queue?
c. FIFO
The retrieval of items in a stack is ___________ operation.
c. pop
The term used to insert an element into stack.
b. push
Which is the pointer associated with the availability list?
a. AVAIL
A linear list in which the last node points to the first node.
d. circular linked list
The elements are removal from a stack in _________ order.
b. Reverse
This form of access is used to add and remove nodes from a queue.
d. FIFO, First In First Out
This is the insertion operation in the stack.
b. push
LINK is the pointer pointing to the ____________________.
b. predecessor node
Deletion operation is done using __________ in a queue.
d. front
i. Internal sorting are applied when the entire collection if data to be sorted is small enough that
the sorting can take place within main memory.
ii. The time required to read or write is considered significant in evaluating the performance of
internal sorting.
a. True, False
_____________ order is the best possible for array sorting algorithm which sorts n item.
a. O(n+logn)
The complexity of linear search algorithm.
b. O(n)
The complexity of sorting algorithm measures the __________ as a function of the number n of
items to be shorter.
b. running time
Which of the following is not the required condition for binary search algorithm?
c. There must be mechanism to delete and/or insert elements in list
___________ sorting algorithm is frequently used when n is small, where n is the total number
of elements.
a. Insertion
The method used by card sorter.
b. Radix sort
The worst case occurs in linear search algorithm when ________________.
c. Item is the last element in the array or item is not there at all
The average case occurs in linear search algorithm _______________.
a. when item is somewhere in the middle of the array
The complexity of merge sort algorithm.
c. O(n logn)
The complexity of linear search algorithm.
b. O(n)
A connected graph T without any cycles is called a ____________.
a. A tree
Another name for directed graph.
a. Digraph
In a graph, if e=[u,v], then u and v are called _______________
a. All of the choices
Which indicates pre-order traversal?
c. Root, Left sub-tree, Right sub-tree
Each node in a linked list must contain at least ___________________.
c. Two fields
The operation of processing each element in the list is known as ________________.
b. traversal
In linked representation of stack, the null pointer of the last node in the list signals
_____________________.
b. Bottom of the stack
Which is the pointer associated with the stack?
a. TOP
The situation when in a linked list START=NULL is ____________________.
d. Underflow
This is a binary tree whose every node has either zero or two children.
a. complete binary tree
What happens when you push a new node onto a stack?
c. The new node is placed at the front of the linked list
The depth of complete binary tree is given by ________________.
b. Dn = log2n+1
Indexing the ________________ element in the list is not possible in linked lists.
c. middle
This may take place only when there is some minimum amount or no space left in free storage
list.
c. Garbage collection
New nodes are added to the ________ of the queue.
d. Back
Each node in singly linked list has _______ fields.
b. 2
Linked lists are best suited _____________________.
b. for the size of the structure and the data in the structure are constantly changing
__________________ is putting an element in the appropriate place in a sorted list yields a
larger sorted order list.
c. insertion
If the number of records to be sorted is small, then __________ sorting can be efficient.
c. Selection
In an extended binary tree, nodes with 2 children are called _________________.
d. Internal node
Which of the following sorting algorithm is of the divide and conquer type
d. Merge sort
In binary trees, nodes with no successor are called _______________.
b. Terminal nodes
Linked representation of binary tree needs ______ parallel arrays.
b. 3
Every node N in a binary tree T except the root has a unique parent called the ________ of N.
d. Predecessor
This is the operation of processing each element in the list.
a. traversal
Partition and exchange sort is ____________.
d. quick sort
Binary search algorithm cannot be applied to _______________.
c. pointer array
On average, searching in a binary search tree is faster than searching in a list.
False
A list may be linear or nonlinear, depending on its implementation.
False
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.
True
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.
e. Stack
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.
b. True, True
A binary search tree is another name for a binary tree.
False
A program to keep track of the soccer teams in a city tournament
d. Tree
A stack displays FIFO behavior.
False
A binary search tree whose left subtree and right subtree differ in height by at most 1 unit is
called ____________________.
d. AVL tree
A program to maintain the routes in an airline.
d. Graph
Which of the following data structure is non-linear type?
c. Graph
A program to keep track of family relationships
b. Tree or e. Graph
Which of the following is not the part of ADT description?
c. None of these
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.
True
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, ' '
4,4
In a graph, the vertices represent the items being modeled.
True
Which of the following is/are the levels of implementation of data structure?
a. All of these
A list may be linear or nonlinear, depending on its implementation.
False
Which of the following data structures is linear type?
c. Stack
Algorithms that use a list must know whether the list is array based or linked.
False
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.
False
Which of the following is non-linear data structure?
b. Trees
Stack is also called the ________________.
c. Last in, first out
Which data structure is suitable to represent the hierarchal relationship between elements?
c. Tree
Which data structure allows deleting data elements from and inserting at rear?
c. queues
This is very useful in situation when data have to be stored and then retrieved in reverse order.
d. stack
A program keeping track of where canned goods are located on a shelf.
c. Stack
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
b. Stack
A binary tree is a tree in which each node can have zero, one, or two children.
True
The root of a tree is the node that has no ancestors.
True
A binary search tree is another name for a binary tree.
False
A stack and a queue are different names for the same ADT.
False
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.
d. Queue linked list
____________________ is not the component of data structure.
a. None of these
____________________ level is where the model becomes compatible executable code.
d. Implementation level
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.
b. Queue
A binary search cannot be applied to a tree.
False
Identify the data structure which allows deletions at both ends of the list but insertion at only one
end.
d. Input restricted dequeue
Herder node is used as sentinel in __________________.
c. Binary tree
Which of the following data structure can't store the non-homogeneous data elements?
a. Arrays
Binary search trees are ordered.
True
Which data structure is used in breadth first search of a graph to hold nodes?
b. Queue
A dictionary of words used by a spelling checker to be built and maintained.
e. Binary search tree
A queue displays LIFO behavior.
False
A bank simulation of its teller operation to see how waiting times would be affected by adding
another teller.
c. Queue
It is a pile in which items are added at one end and removed from the other.
b. queue
An electronic address book ordered by name
a. Binary search tree
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.
d. push, pop
A program to receive data that is to be saved and processed in the reverse order.
d. Stack
A leaf in a tree is a node with no children.
True