BASIC CONCEPTS
TRUE/FALSE
 AN INSTANCE IS A PROBLEM WITH VALUES ASSIGNED TO PARAMETERS.
ANSWER TO QUESTION 1
 THE "PRECONDITION" IS A CONDITION THAT MUST BE TESTED BEFORE EACH ITERATION
OF THE LOOP.
ANSWER TO QUESTION 2
 BOTH STACK AND QUEUE REMOVE AN ELEMENT FROM TOP (FIRST) POSITION.
ANSWER TO QUESTION 3
 REHASHING IS A COLLISION RESOLUTION MECHANISM USING THE SEPARATE CHAINING APPROACH.
ANSWER TO QUESTION 4
 A DOUBLYLINKED LIST USES TWO REFERENCES: FIRST AND LAST, TO POINT TO THE
FIRST AND LAST ELEMENT IN THE LIST.
ANSWER TO QUESTION 5

All the three basic sorting algorithms (bubble sort, insertion sort, and selection sort)
run in the order of ___ time.
 0(1)
 0(N)
 0(N, logN)
 0(N^{2})
ANSWER TO QUESTION 1

Which of the folloing sorting methods require the most memory space?
 bubble sort
 shell sort
 quick sort
 merge sort
ANSWER TO QUESTION 2

Which of the folloing sorting methods require the most efficient time?
 shell sort
 quick sort
 insertion sort
 bubble sort
ANSWER TO QUESTION 3
 The purpose of using a balanced tree is to
 reduce the number of nodes
 improve the search efficiency
 reduce the insertion and deletion time
 cut down the memory space for nodes
ANSWER TO QUESTION 4
 Which of the following tree(s) is(are) commonly used for
external data that are stored in a file to provide fast search,
insertion, and deletion time?
 RedBlack Tree (RB Tree)
 234 Tree
 BTree
 All of the above
ANSWER TO QUESTION 5
 Which of the following is part of redblack rules that ensure the balance
of a RB tree?
 If a node is black, its children must be red.
 The roof must always be red.
 Every path from the root to a leaf,or to a null child, must contain the same number
of black nodes.
 The parent and child nodes must have a different color.
ANSWER TO QUESTION 6
 In a 234 tree, each node can contain ___ keys.
 0,1,2 or 3
 1,2,3, or 4
 2,3, or 4
 1,2, or 3
ANSWER TO QUESTION 7
 A full binary tree with height K contains how many nodes?
 2^{K}
 2^{K}1
 2^{K+1}1
 2^{K1}1
ANSWER TO QUESTION 8
 If a fully connected graph contains N vertices, then it should have ___ edges.
 N
 N1
 N*N/2
 N*(N1)/2
ANSWER TO QUESTION 9
 A topologic sorting can be carried out only on a ___, ___ graph.
 undirected, cyclic
 undirected, acyclic
 directed, cyclic
 directed, acyclic
ANSWER TO QUESTION 10
 The depthfirst search uses a ___ to remember where it should go when it
reaches a dead end.
 stack
 queue
 priority queue
 linked list
ANSWER TO QUESTION 11
 Which of the following features in ADT provides data security?
 abstraction
 encapsulation
 separation of data from code
 none of the above
ANSWER TO QUESTION 12
 An ADT specification must specify the following two kinds of information.
 instance and operation
 data type and data content
 problem and algorithm
 time and space
ANSWER TO QUESTION 13
 In the set of (key, value) pairs for a hash table, which component(s)
must be unique?
 key
 value
 both key and value
 neither key nor value
ANSWER TO QUESTION 14
 A minimum spanning tree for a weighted graph best represents
 the minimum number of edges necessary to connect all the vertices
in the graph.
 the shortest (or cheapest) distance from one vertex to another.
 the smallest set of edges that have value smaller than a given
minimum weight.
 none of the above
ANSWER TO QUESTION 15
