1. Suppose cursor refers to a node in a linked list (using the IntNode class with instance variables Called data and link). What statement changes cursor so that it refers to the next node?
A. cursor++;
B. cursor = link;
C. cursor += link;
D. cursor = cursor.link;
2. Suppose cursor refers to a node in a linked list (using the Node class with instance variables called data and link). What boolean expression will be true when cursor refers to the tail node of the list?
A. (cursor == null)
B. (cursor.link == null)
C. (cursor.data == null)
D. (cursor.data == 0.0)
E. None of the above.
3. Which boolean expression indicates whether the numbers in two nodes (p and q) are the same. Assume that neither p nor q is null.
A. p == q
B. p.data == q.data
C. p.link == q.link
D. None of the above.
4. Suppose that p is a reference variable that contains the null reference. What happens at runtime if the program tries to activate a method of p?
A. IllegalArgumentException
B. IllegalStateException
C. NullPointerException
D. The results are unpredictable.
5. Suppose that a method has one node as a parameter and it returns two references to nodes. What's the best header for the method?
A. IntNode foo(IntNode p)
B. IntNode, IntNode foo(IntNode p)
C. IntNode[ ] foo(IntNode p)
D. void foo(IntNode p, IntNode answer1, IntNode answer2)
6. In the linked list version of the Bag class an instance variable manyNodes is used to keep track of how long the linked list is. Why not just make a call to the IntNode method listLength()?
A. The listLength() method is O(n) and the alternative is O(1).
B. The listLength() method is private.
C. The listLength() method results in an infinite loop for circular lists.
D. The listLength() method works only for lists of integers.
7. Suppose that the Bag is implemented with a linked list. Which of these operations are likely to have a constant worst-case time?
A. add
B. countOccurrences
C. remove
D. None of (A), (B), and (C) have a constant worst-case time
E. TWO of (A), (B), and (C) have a constant worst-case time
F. ALL of (A), (B), and (C) have a constant worst-case time
8. What is the expression for generating a pseudorandom number in the range 1...N?
A. (int) (Math.random() * N);
B. (int) (Math.random() / N);
C. (int) (Math.random() * (N + 1));
D. (int) (Math.random() / (N + 1));
E. (int) (Math.random() * N) + 1;
9. Which expression computes a pseudorandom integer between -10 and 10 using rand() from stdlib.h?
A. (int) (Math.random( ) * 20) - 10
B. (int) (Math.random( ) * 21) - 10
C. (int) (Math.random( ) * 22) - 10
D. (int) (Math.random( ) * 20) - 11
E. (int) (Math.random( ) * 21) - 11
10. For the linked-list version of the Sequence ADT, which operations are constant time operations in the worst case?
A. addAfter is constant time, but not addBefore
B. addBefore is constant time, but not addAfter
C. Both addAfter and addBefore are constant time
D. Neither addAfter nor addBefore are constant time
11. Suppose that the Sequence is implemented with a linked list. Which of these operations are likely to have a constant worst-case time?
A. addBefore
B. countOccurrences
C. remove
D. None of (A), (B), and (C) have a constant worst-case time
E. TWO of (A), (B), and (C) have a constant worst-case time
F. ALL of (A), (B), and (C) have a constant worst-case time
12. What kind of list is best to answer questions such as "What is the item at position n?"
A. Lists implemented with an array.
B. Doubly-linked lists.
C. Singly-linked lists.
D. Doubly-linked or singly-linked lists are equally best
13. . Entries in a stack are "ordered". What is the meaning of this statement?
A. A collection of Stacks can be sorted.
B. Stack entries may be compared with the '<' operation.
C. The entries must be stored in a linked list.
D. There is a first entry, a second entry, and so on.
14. . The operation for adding an entry to a stack is traditionally called:
A. add
B. append
C. insert
D. push
15. The operation for removing an entry from a stack is traditionally called:
A. delete
B. peek
C. pop
D. remove
16. Which of the following stack operations could result in stack underflow?
A. is_empty
B. pop
C. push
D. Two or more of the above answers
17. . Which of the following applications may use a stack?
A. A parentheses balancing program.
B. Keeping track of local variables at run time.
C. Syntax analyzer for a compiler.
D. All of the above.
18. . Consider the following pseudocode:
declare a stack of characters
while ( there are more characters in the word to read )
{
read a character
push the character on the stack
}
while ( the stack is not empty )
{
pop a character off the stack
write the character to the screen
}
19.What is written to the screen for the input "carpets"?
1. A. serc
2. B. carpets
3. C. steprac
4. D. ccaarrppeettss
20. Here is an INCORRECT pseudocode for the algorithm which is supposed to determine whether a sequence of parentheses is balanced:
declare a character stack
while ( more input is available)
{
read a character
if ( the character is a '(' )
push it on the stack
else if ( the character is a ')' and the stack is not empty )
pop a character off the stack
else
print "unbalanced" and exit
}
print "balanced"
21.Which of these unbalanced sequences does the above code think is balanced?
A. ((())
B. ())(()
C. (()()))
D. (()))()
22. Consider the usual algorithm for determining whether a sequence of parentheses is balanced. What is the maximum number of parentheses that will appear on the stack AT ANY ONE TIME when the algorithm analyzes: (()(())(()))?
A. 1
B. 2
C. 3
D. 4
E. 5 or more
23.. Consider the usual algorithm for determining whether a sequence of parentheses is balanced. Suppose that you run the algorithm on a sequence that contains 2 left parentheses and 3 right parentheses (in some order). What is the maximum number of parentheses that will ever appear on the stack AT ONE TIME during the computation?
A. 1
B. 2
C. 3
D. 4
E. 5 or more
24. Suppose we have an array implementation of the stack class, with ten items in the stack stored at data[0] through data[9]. The CAPACITY is 42. Where does the push method place the new entry in the array?
A. data[0]
B. data[1]
C. data[9]
D. data[10]
25.. Consider the implementation of the Stack using a partially-filled array. What goes wrong if we try to store the top of the Stack at location [0] and the bottom of the Stack at the last used position of the array?
A. Both peek and pop would require linear time.
B. Both push and pop would require linear time.
C. The Stack could not be used to check balanced parentheses.
D. The Stack could not be used to evaluate postfix expressions.
26. In the linked list implementation of the stack class, where does the push method place the new entry on the linked list?
A. At the head
B. At the tail
C. After all other entries that are greater than the new entry.
D. After all other entries that are smaller than the new entry.
27.. In the array version of the Stack class, which operations require linear time for their worst-case behavior?
A. is_empty
B. peek
C. pop
D. push when the stack is below capacity
E. None of these operations require linear time.
28.. In the linked-list version of the Stack class, which operations require linear time for their worst-case behavior?
A. is_empty
B. peek
C. pop
D. push
E. None of these operations require linear time.
29.What is the value of the postfix expression 6 3 2 4 + - *:
A. Something between -15 and -100
B. Something between -5 and -15
C. Something between 5 and -5
D. Something between 5 and 15
E. Something between 15 and 100
30. Here is an infix expression: 4+3*(6*3-12). Suppose that we are using the usual Stack algorithm to convert the expression from infix to postfix notation. What is the maximum number of symbols that will appear on the stack AT ONE TIME during the conversion of this expression?
A. 1
B. 2
C. 3
D. 4
E. 5
31. One difference between a queue and a stack is:
A. Queues require linked lists, but stacks do not.
B. Stacks require linked lists, but queues do not.
C. Queues use two ends of the structure; stacks use only one.
D. Stacks use two ends of the structure, queues use only one.
32. If the characters 'D', 'C', 'B', 'A' are placed in a queue (in that order), and then removed one at a time, in what order will they be removed?
A. ABCD
B. ABDC
C. DCAB
D. DCBA
Which of the following expressions evaluates to true with approximate probability equal to P? (P is double and 0 <= P <= 1).
A. Math.random() < P
B. Math.random() > P
C. Math.random() < P * 100
D. Math.random() > P * 100
33. Suppose we have a circular array implementation of the queue class, with ten items in the queue stored at data[2] through data[11]. The current capacity is 42. Where does the insert method place the new entry in the array?
A. data[1]
B. data[2]
C. data[11]
D. data[12]
34. Consider the implementation of the Queue using a circular array. What goes wrong if we try to keep all the items at the front of a partially-filled array (so that data[0] is always the front).
A. The constructor would require linear time.
B. The getFront method would require linear time.
C. The insert method would require linear time.
D. The isEmpty method would require linear time.
36. Consider an undirected graph G with n vertices and e edges. What is the time taken by Depth First Search(DFS) if the graph is represented by(i)Adjacency matrix, and(ii)Adjacency list?
(a) O(n^2),O(n) (b) O(n^2),O(e)
(c) O(e),O(n^2) (d) O(e + n),O(e)
37 . An undirected graph G with n vertices and e edges is represented by adjacency list. What is the time required to generate all the connected components?
(a) O(n) (b) O(e)
(c) O(e + n) (d) O(e^2)
38 . Which of the following statements is false?
(a) every tree is a bipartite graph (b) a tree contains a cycle
(c) a tree with n nodes contains (d) a tree is a connected graph
n-1 edges
39 . A graph G with n nodes is bipartite if it contains
(a) n edges (b) a cycle of odd length
(c) no cycle of odd length (d) n^2 edges
40 . In what tree, for every node the height of its left sub tree and right subtree differ at least by one
(a) binary search tree (b) AVL-tree
(c) Complete tree (d) Threaded binary tree
41 . Which of the following sorting method is stable?
(a) straight insertion sort (b) binary insertion sort
(c) Shell sort (d) Heap sort
42 . A complete binary tree with the property that the value at each node is at least as large as the values at its children is known as
(a) binary search tree (b) AVL tree
(c) Completely balanced tree (d) Heap
43. The recurrence relation T(n)=mT(n/2)+an^2 is satisfied by
(a) T(n) = O(n^m) (b) T(n) = O(n log m)
(c) T(n) = O(n log m) (d) T(n) = O(m log n)
44. The time required to find shortest path in a graph with n vertices and e edges is
(a) O(e) (b) O(n)
(c) O(e^2) (d) O(n^2)
45. The goal of hashing is to produce search that takes
(a) O(1) time (b) O(n^2)time
(c) O(log n)time (d) O(n log n)time
46. In which of the folling sorting algorithm the num of comparisons needed is the minimum
if the items sre initially in reverse order and is maximum if the items are in order?
(a) Straight insertion (b) Binary insertion sort
(c) Heap sort (d) Bubble sort
47. Which of the following best describes sorting?
(a) accessing and processing each record exactly once
(b) finding the location of the record with a given key
(c) arranging the data (record) in some given order
(d) adding a new record to the data struture
48. The order of magnitude of the worst case performance of the linear search over N elements is
(a) N log2 n (b) N
(c) N^2 (d) log2 N
49. The order of magnitude of the worst case performance of the binary search ove N elements is
(a) N log2 n (b) N
(c) N^2 (d) log2 N
50. The order of magnitude of the worst case performance of ordered binary tree with N elements is
(a) N log2 N (b) N
(c) Hash coded search (d) Radix search
51. A search procedure which associates an address with a key value and provides a machnism
for dealing with two or more values assigned to the same address is called
(a) Linear search (b) Binary search
(c) Hash coded search (d) Radix search
52. The order of magnitude of the worst case performance of a coded search (over N elements) is
(a) N (b) N log2 N
(c) log2 N (d) not dependent upon N
53. When key values are reals a similar data representation might de produced by using a hashing function with
(a) mod (b) heap sort
(c) trunc (d) log N
54. A characteristic of the data that binary search uses but the linear search ignores, is the
(a) insertion sort (b) length of the list
(c) maximum value in the list (d) bubble sort
55. A sort which compares adjacent element in a list and switch where nessary is a
(a) insertion sort (b) heap sort
(c) quick sort (d) bubble sort
56. A sort which iteratively passes through a list to exchange the first element with any element
less than it and then repeats with a new first element is called
(a) insertion sort (b) selection sort
(c) heap sort (d) quick sort
57. A full binary tree with n leaves contains
(a) n nodes (b) log2 n nodes
(c) 2n-1 nodes (d) 2^n nodes
58. A full binary tree with n non leaf nodes contains
(a) log2 n nodes (b) n+1 nodes
(c) 2n nodes (d) 2n+1 nodes
59. A sort which uses the binary tree concept such that any number is larger than all the numbers
in the subtree below it is called
(a) selection sort (b) insertion sort
(c) heap sort (d) quick sort
60. Which of the following sortingalgorithms does not have a worst case running time of O(n^2)
(a) insertion sort (b) merge sort
(c) quick sort (d) bubble sort
61. Which of the following sortingalgorithms has a worst case running time of O(n^r)where
1
(a) bubble sort (b) insertion sort
(c) shell sort (d) merge sort
62 . For a linear search in an array of n elements the time complexity for best, worst and average cases are…., …and ……respectively.
(a) O(n),O(1),and O(n/2) (b) O(1),O(n) and O(n/2)
(c) O/1, O(n) and O(n) (d) O(1), O(n) and(n-1/2)
63 . What is the minimum number of fields with each node of doubly linked list
(a) 1 (b) 2
(c) 3 (d) 4
64 . Let A be a sorted array of n = 10 elements. Assume that only one comparison is required to determine whether the target is equal to, less than, or greater than A[i].Which of the following denotes the average successful time of finding an arbitrary element x in A using binary search?
(a) 1.6 (b) 2.9
(c) 4.2 (d) 5.5
65 . A digital search key is implemented as a tree with n nodes each of which can contain m pointers, corresponding to the m possible symbols in each position of the key. The number of nodes that must be accessed to find a particular tree is
(a) m (b) n
(c) n^m (d) m^n
66. In the linked list implementation of the queue class, where does the insert method place the new entry on the linked list?
1. A. At the head
2. B. At the tail
3. C. After all other entries that are greater than the new entry.
4. D. After all other entries that are smaller than the new entry.
67. In the circular array version of the Queue class, which operations require linear time for their worst-case behavior?
a. A. getFront
b. B. insert when the capacity has not yet been reached
c. C. isEmpty
d. D. None of these operations require linear time.
68. In the linked-list version of the Queue class, which operations require linear time for their worst-case behavior?
a. A. getFront
b. B. insert
c. C. isEmpty
d. D. None of these operations require linear time.
69. If data is a circular array of CAPACITY elements, and rear is an index into that array, what is the formula for the index after rear?
a. A. (rear % 1) + CAPACITY
b. B. rear % (1 + CAPACITY)
c. C. (rear + 1) % CAPACITY
d. D. rear + (1 % CAPACITY)
70. I have implemented the queue with a circular array, keeping track of front, rear, and manyItems (the number of items in the array). Suppose front is zero, and rear is one less than the current capacity. What can you tell me about manyItems?
a. A. manyItems must be zero.
b. B. manyItems must be equal to the current capacity.
c. C. count could be zero or the capacity, but no other values could occur.
d. D. None of the above.
Ques.#71
The number of edges in a complete graph of n vertices is
(a) n
(b) n(n-1)/2
(c) n(n-1)/2
(d) n^2/2
Ques.#72
A vertex of in-degree zero in a directed graph is called a/an
(a) articulation point
(b) sink
(c) isolated vertex
(d) root vertex
Ques.#73
If there exists at least on path between every pair of vertices in a graph,the graph is known as
(a) connected graph
(b) complete graph
(c) planar graph
(d) simple graph
Ques.# 74
The minimum number of spanning trees in a connected graph with n vertices is
(a) 1
(b) n-1
(c) 2
(d)n/2
Ques.#75
The number of edges in a spanning tree of a graph with n vertices is
(a) (n-1)/2
(b) n-1
(c) n(n+1/2
(d) n^2/2
Ques.#76
What is the best definition of a collision in a hash table?
(a) Two entries are identical except for their keys.
(b) Two entries with different data have the exact same key.
(c) Two entries with different keys have the same exact has value.
(d) Two entries with the exact same key have different hash values.
Ques.#77
Which guideline is NOT suggested from empirical or theoretical studies of hash table;
(a) Hash table size should be the product of two primes.
(b) Hash table size should be the upper of pair of twin primes.
(c) Hash table size should have the form 4K+3 for some K.
(d) Hash table size should not be too near a power of two.
Ques.#78
To represent a binary tree of height h using an array,an array of minimum size_______ will be required.
(a) 2^h
(b) 2h+1
(c) 2^h-1
(d) 2(h-1)
Ques.#79
Which of the following statement is true about topological sort of a directed graph?
(a) It indicate precedence among vertices representing events.
(b) It is basically a linear ordering of vertices such that if a graph
contains edge(u,v) then u appears before v in the ordering.
(c) Topological sort is possible only if the directed graph is acyclic.
(d) All of above
Ques.#80
Which of the following is not an open addressing technique to resolve collisions?
(a) Quadratic probing
(b) Double hashing
(d) Cubic probing
(d) Linear probing.
Ques.#81
A chained hash table has an array size of 512.What is the maximum number of entries that can be placed in the table?
(a) 256
(b) 512
(c) 1024
(d) There is no maximum.
Ques.#82
Given an array named nums containing 22 integer numbers sorted on descending order?In the worst case,what will be number of comparison performed by binary search technique?
(a) 22
(b) 5
(c) 4
(d) 6
Ques.#83
The average case complexity of quicksort for sorting n numbers is
(a) O(log2n)
(b) O(n)
(c) O(nlog2n)
(d) O(n2)
Ques.#84
In a selection sort of n elements, how many times ,at most, the swap function is called in the complete execution of the algorithm?
(a) 1
(b) n-1
(c) nlog2n
(d) n2
Ques.#85
Merge sort and quick sort both fall into the same category of sorting algorithms. What is this category?
(a) O(nlog2n)sorts
(b) Interchange sort
(c) Average time is quadratic
(d) None of above
Ques.#86
Suppose that a selection sort of 100 items has completed 42 iteration of the main loop. How many elements are now guaranteed to be in their final spot?
(a) 21
(b) 41
(c) 42
(d) 43
Ques.#87
Suppose we are sorting an array of eight integers in the ascending order using some quadratic sorting algorithm. After four iterations of the algorithm’s main loop, the array elements are ordered as shown below here:
52 54 55 57 58 51 53
Which statement is correct ?
(a) The algorithm might be either selection sort or insertion sort
(b) The algorithm might be selection sort, but it is not insertion sort
(c) The algorithm is not selection sort, but if might be insertion sort
(d) The algorithm is neither selection sort nor insertion sort
Ques.#88
Suppose we are sorting an array of ten integers in ascending order using some quadratic sorting algorithm. After four iterations of the algorithm’s main loop,the array elements are ordered as shown here :
11 22 33 42 55 50 66 87 98 80
Which statement is correct ?
(a) The algorithm might be either selection sort or insertion sort
(b) The algorithm might be selection sort,but it is not insertion sort
(c) The algorithm is not selection sort, but if might be insertion sort
(d) The algorithm is neither selection sort nor insertion sort
Ques.#89
When is insertion sort a good choice for sorting an array?
(a) Each element of array requires a large amount of memory
(b) The processor speed is fast
(c) Each element of array requires a small amount of memory
(d) The array has only a few elements out of place
Ques.#90
What is the worst-case time for merge sort an array of n elements in element in descending order?
(a) O(n2)
(b) O(log2n)
(c) O(nlog2n)
(d) O(n)
Ques.#91
What is the worst-case time for quicksort to sort an array of n elements?
(a) O(n2)
(b) O(log2n)
(c) O(nlog2n)
(d) O(n)
Ques.#92
Merge sort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step?
(a) Elements in the first of the array are less than or equal to elements in the second half of the array
(b) Array elements form a heap
(c) Elements in each half of the array are sorted amongst themselves
(d) None of the above
Ques.#93
Suppose we are sorting an array of eight integers in ascending order using quick sort, and we have just finished the first partitioning with the array looking like this:
2 5 1 7 9 12 11 10
Which statement is correct?
(a) The pivot could be the 7,but it is not the 9
(b) Neither the 7 nor the 9 is the pivot
(c) The pivot could be either the 7 or the 9
(d) The pivot is not the 7, but it could be the 9
Ques.#94
What is the best-case time for quick to sort an array of n alements?
(a) O(n2)
(b) O(log2n)
(c) O(nlog2n)
(d) O(n)
Ques.#95
Suppose we are sorting an array of eight integers in ascending order, using heapsort, and we have just finished one of the downheap operations. The array now looks like this:
6 4 5 1 2 7 8
How many downheap downward have been performed
(a) 1
(b) 2
(c) 3
(d) 4
Ques.#96
What is the best-case time for quicksort to sort an array of n elements?
(a) O(n2)
(b) O(log2n)
(c) O(nlog2n)
(d) O(n)
Ques.#97
Consider te following array
23 15 5 12 40 10 7
After the first pass of a particular algorithm,the array looks like
15 5 12 23 10 7 40
Name the algorithm used
(a) Heap sort
(b) Selection sort
(c) Insertion sort
(d) Bubble sort
Ques.#98
Which of the following algorithms can be used even if all the elements of an array are not available before stating the process?
(a) Heap sort
(b) Shell sort
(c) Tree sort
(d) Bubble sort
Ques.#99
A queue where all the elements have equal priority is a
(a) LIFO data structure
(b) FIFO data structure
(c) LILO data structure
(d) ILFO data structure
Ques.#100
With an array based queue.the algorithm for enqueue operation is
(a) Save the item in position 0;shift the items towards 0;decrement rear
(b) Decrement rear;save the item in position 0;shift the item toward 0
(c) Add the item to the last location and the increment rear
(d) Increment rear and add item to te new rear location
Ques.#101
If the charaters ‘z’,’y’,’x’, and ‘w’ enqueue in a queue, in that order, and then dequeued one at a time,in what order will they be dequeued?
(a) wxzy
(b) zywx
(c) zyxw
(d) wxyz
Ques.#102
Suppose we have a circular array implementation of the queue with 18 items n the queue stored at data[12] through data[29].The CAPACITY of the queue is 30.Where does the enqueue operation place the new entry in the array?
(a) Data[30]
(b) Data[0]
(c) Data[13]
(d) Data[11]
Ques.#103
In the linked list implementation of the queue,where does the enqueue operation place the new entry in the linked list?
(a) At the beginning
(b) At the end
(c) After all other entries that are greater than the new entry
(d) After all other entries that are similar than the new entry.
Ques.#104
In the circular queue,with a fixed-sized array,which operations require linear time for its worst-case behavior?
(a) Is empty()
(b) Enqueue()
(c) Dequeue()
(d) None of the above
Ques.#105
Suppose we have implemented a circular queue with track of first element(front),last element(rear),and the number of items in the array(count).suppose front is zero and rear is CAPACITY-1.What can you tell about the count?
(a) Count must be equal to zero
(b) Count must be equal to CAPACITY
(c) Count could be equal to zero or CAPACITY,but no other values could occur
(d) None of he above.
106. Which of the following abstract data types can be used to represent a many to many relation?
(a) tree only (b) plex only
(c) graph only (d) b and c above
107. Which of the following remarks about Trie Indexing if false?
(a) It is efficient in dealing with strings of variable length.
(b) It is efficient if there are a few number of data items.
(c) The number of disk accesses can’t exceed the length of the particular string that is
searched.
(d) It can handle insertions and deletions, dynamically and efficiently.
108. The average search time of hashing with linear probing will be less if the load factor
(a) is far less than one (b) equals one
(c) is far greater than one (d) none of the above
109. Which of the following remarks about Trie Indexing is false?
(a) It is an m-ary tree.
(b) It is a search tree of order m.
(c) Successful searches should terminate in leaf nodes.
(d) Unsuccessful searches may terminate at any level of the tree structure.
110. The number of vertices of odd degree in a graph is
(a) always even (b) always odd
(c) either even or odd (d) always zero
111. A graph in which all nodes are of equal degree are known as
(a) multigraph (b) non regular graph
(c) regular graph (d) complete graph
112. A vertex of degree one is called as
(a) pendant (b) isolated vetex
(c) null vertex (d) coloured vertex
113. The maximum degree of any node in a simple graph with n vertices is
(a) n-1 (b) n
(c) n/2 (d) n-2
114. Two isomorphic graphs must have
(a) the same number of vertices (b) the same number of edges
(c) an equal number of vertices (d) all of the above
115. The terminal vertices of a path are of degree
(a) one (b) two
(c) zero (d) more than four
116. If there exists one path between every pair of vertices in a graph, the graph is known as
(a) complete graph (b) disconnected graph
(c) connected graph (d) Euler graph
117. A simple graph with n vertices and k components can have atmost
(a) n edges (b) n-k edges
(c) (n-k)(n-k-1)/2 edges (d) (n-k)(n-k+1)/2 edges
118. A given connected graph G is a Euler graph if and only if all vertices of G are of
(a) same degree (b) even degree
(c) odd degree (d) different degree
119. A circuit in a connected graph which includes every vertex of the graph is known as
(a) Euler (b) Unicursal
(c) Hamiltonian (d) Clique
120. The length of a Hamiltonian path (if exists) in a connected graph of n vertices is
(a) n - 1 (b) n
(c) n + 1 (d) n/2
121. A simple graph in which there exists an edge between every pair of vertices is called a(an)
(a) incomplete graph (b) complete graph
(c) Euler graph (d) planner graph
122. The total number of edges in a complete graph of n vertices is
(a) n (b) n2/2
(c) n(n+1)/2 (d) n(n-1)/2
123. A tree with n nodes has
(a) n/2 edges (b) n – 1 edges
(c) n edges (d) n + 1 edges
124. The number of paths between any pair of nodes in a tree on n nodes is
(a) 0 (b) 1
(c) (n – 1) (d) n
125. A complete graph with five vertices is
(a) nonplanar (b) planar
(c) a non - regular graph (d) a tree
126. Kuratowski’s first graph is the nonplanar complete graph with the smallest number of vertices.
The number of vertices is
(a) 4 (b) 5
(c) 6 (d) 7
127. I have implemented the queue with a linked list, keeping track of a front node and a rear node with two reference variables. Which of these reference variables will change during an insertion into a NONEMPTY queue?
A. Neither changes
B. Only front changes.
C. Only rear changes.
D. Both change.
128. I have implemented the queue with a linked list, keeping track of a front node and a rear node with two reference variables. Which of these reference variables will change during an insertion into an EMPTY queue?
A. Neither changes
B. Only front changes.
C. Only rear changes.
D. Both change.
129. The number of circuits in a tree with n nodes is
(a) zero (b) 1 (c) n-1 (d) n/2
130. A graph is a tree if and only if it
(a) is completely connected (b) is minimally connected
(c) contains a circuit (d) is planar
131.The minimum number of spanning trees in a connected graph with n nodes is
(a) 1 (b) 2 (c) n-1 (d) n/2
132. The rank of a graph with n vertices , e edges and k components is
(a) n (b) e- n+ k (c) n-1 (d) n+ k
133. The nullity of a graph with n vertices , e edges and k components is
(a) n (b) e-n+ k (c) n-k (d) n+ k
134. The number of elements (edges) in a cutest of a tree with n vertices is
(a) 1 (b) n/2 (c) n-1 (d) n
135. Let a graph G has edge connectivity and node connectivity. Then
(a) α < β (b) α = β (c) α >= β (d) α <= β
136. What is the edge connectivity of a complete graph with n vertices?
(a) 1 (b) n-1 (c) n +1 (d) n(n+1)/2
137. If A(G) is an incident matrix of a connected graph G with n vertices, the rank of
A(G) is
(a) 1 (b) 2 (c) n-1 (d) n
138. If G is a disconnected graph with n vertices and k components, the rank of the incident matrix A(G) of the graph is
(a) n-k-1 (b) n-k (c) n+ k-1 (d) n+ k
139. A graph with n vertices and n-1 edges that is not a tree is
(a) connected (b) disconnected (c) Eular (d) a circuit
140. If B is a circuit matrix of a graph with k components, e edges and n vertices, the
rank of B is
(a) n-k (b) e-n-k (c) e-n+ k (d) e+ n-k
141. Consider a graph G having cutest matrix C(G) and incidence matrix A(G). the rank of C(G) is
(a) same as the rank of A(G) (b) more than the rank of A(G)
(c) less than the rank of S(G) (d) independent of the rank of A(G)
142. Let X be the adjacency matrix of graph G with no self loops. The entries along the principle diagonal of X are
(a) all zeros (b) all ones
(c) both zeros and ones (d)different
143. If a graph requires k different colour for its proper colouring, then the chromatic number of the graph is
(a) k/2 (b) k-1
(c) k (d) 1
144. A graph consisting of only isolated n vertices is
(a) 1-chromatic (b) 2-chromatic
(c) 3-chromatic (d) n-chromatic
145.A graph with one or more edges(without self loop) is at least
(a) 1-chromatic (b) 2-chromatic
(c) 3-chromatic (d) n-chromatic
146. A complete graph with n vertices is
(a) 2-chromatic (b) n/2 chromatic
(c) (n-1) chromatic (d) n-chromatic
147. If d(max) is the maximum degree of the vertices in a graph G, the chromatic number of G is
(a) equal to d (b) less than or equal to d(max)
(c) less than or equal to d(max)+1 (c) greater than d(max)
148. If the vertex set V of a graph can be decomposed into two subsets V1 and V2 such that every edge in G joins a vertex in V1 with a vertex in V2, the graph is called
(a) bipartite (b) tri-partite
(c) 1-chromatic (d) V-partite
149. A covering of an n-vertex graph has atleast
(a) n/2 edge (b) [n/2] edges
(c) [(n-1)/2] edges (d) n edges
150. The number of colours required to properly colour the vertices of every planar graph is
(a) 3 (b) 2
(c) 4 (d) 5
151.If A(G) is the incidence matrix of a connected digraph of n vertices the rank of A(G) is
(a) n (b) n/2
(c) 2 (d) n-1
152.The number of different rooted labeled trees with n vertices is
(a) 2^n-1 (b) 2^n
(c) n^n-1 (d) n^n
153.Let A={1,2,3,4,5} Which of the following sets equal A?
(a) {4,1,2,3,5} (b) {5,1,3,2,1}
(c) {3,2,4,1} (d) {3,4,5}
154. Which of the following sets are empty?
(a) {x/x is a real number and x^2-1=0} (b) {x/x is a real number and x^2+1=0}
(c) {x/x is a real number and x=2x+1} (d) {x/x is a real number and x^2=-9}
155. Let a={1,2,5,8,11}. Which of the following is false?
(a) {5,1}is subset of or equal to A (b) {8,1} belongs to A
(c) ø is subset of or equal to A (d) {2} is subset of or equal to A
156. Suppose we have implemented the queue with a linked list keeping track of a front element with frontptr pointer and a rear element with rearptr pointer. Which of these pointer will change with an enqueue operation on a nonempty queue?
(a) neither changes
(b) only frontptr changes
(c) only rearptr changes
(d) both changes
157:- Suppose we have implemented the queue with a linked list, keeping track of a front element with frontptr pointer and a rear element with rearptr pointer. Which of these pointer will change with a enqueue operation on an empty queue?
(a) neither changes
(b) only frontptr changes
(c) only rearptr changes
(d) both change
158:- Suppose we have implemented the queue with a linked list, keeping tarck of a front element with frontptr pointer and a rear element with rearptr pointer. Which of these pointers will changes with a dequeue operation on a queue having two or more elements?
(a) neither changes
(b) only frontptr changes
(c) only rearptr changes
(d) both changes
159:- Suppose we have implemented the queue with a linked list. keeping tarck of front element with frontptr pointer and a rear element with rearptr pointer. Which of these pointer will change with a dequeue operation on a queue having only one element?
(a) neither changes
(b) only frontptr changes
(c) only rearptr changes
(d) both changes
160:- Suppose a priority queue has two elements with same priority. How is the return value of dequeue operation selected?
(a) The implementation needs to choose either one.
(b) The one which was inserted first
(c) The one which was inserted most recently
(d) This can never happen, i.e. its violates the precondition
161:- Which of the following data structure is required to convert an arithmetic expression in infix to its equivalent postfix notation?
(a) linked list
(b) binary search tree
(c) queue
(d) none of above
162:- Which of the following statement is not true about a binary search tree?
(a) It is a two way search tree.
(b) At eachj node, the elements of the left sub tree are less than the node valve and the element in the right subtree are greater than the node value.
(c) It can be efficiently represented using an array.
(d) It provides the best of both arrays and linked list
163:- Which of the following tree maintains a list of the keys in sequential order?
(a) m-way search tree
(b) B-tree
(c) B*-tree
(d) B+-tree
164:- An array is declared as
int a[3][4] { {1,2}, {4,5,6} };
What is the value of a[1][2]?
(a) 5
(b) 6
(c) 2
(d) Garbage
165:- Which of the following statement is true about strings in C?
(a) String is a primitive data type in C
(b) Every string must be terminated by a newline character('\n')
(c) A string value can be assigned to a string variable using assignment operator '='
(d) Strings are represented in C using array of type char.
166:- If a number 125.456 is written to a file that is opened in text mode, how many bytes it will need for its storage?
(a) 4 bytes
(b) 7 bytes
(c) 8 bytes
(d) 5 bytes
167:- Which of the following file organization allow an application to access the records directly as well as sequentially?
(a) Relative file organization
(b) sequential file organization
(c) indexed sequential file organization
(d) none of above
168:- Changes that are going to be applied to a master file, in a batch-oriented application, are collected in a file?
(a) work file
(b) report file
(c) activity file
(d) transaction file
169:- Which of the following file organizations is not suitable for an interactive application?
(a) ralative file organization
(b) sequential file organization
(c) indexed sequential file organization
(d) inverted file organization
170:- If an undirected graph with n vertices and e edges is represented using an adjacency list, what will the total number of nodes in the adjacency lists?
(a) n
(b) e
(c) 2e
(d) 2n
171:- Suppose we have a linear array implementation of the queue, with 18 items in the queue atored at data[12] through data[29]. The CAPACITY of the queue is 30. Where does the enqueue operation place the new entry in the array, when the queue is readjusted if it is not full?
(a) data[30]
(b) data[18]
(c) data[0]
(d) data[17]
172:- An index is a pair of elements comprising key and a file pointer or record number. A file in which indices are stored is known as _________
(a) sort file
(b) key file
(c) index file
(d) none of above
173:- A file is only read by a program is known as_____________________
(a) temporary file
(b) work file
(c) I/o file
(d) input file
174:- Which of following operation are generally not performed on report files?
(a) Updation
(b) Maintenance
(C) Retreval
(d) All the above
175:- Which of following is not a type of a I/O channel?
(a) selector
(b) multiplexer
(c) demoltiplexer
(d) block multiplexer
176:- Name the tree in which, for every node, the height of left subtree
and height of right subtree can difer by at most one
(a) Complete tree
(b) AVL tree
(c) Threaded tree
(d) B-tree
177:- A graph in which all vertices have equal degree is known as______
(a) complete graph
(b) simple graph
(c) multiple graph
(d) regular graph
178:- A binary tree in all its levels except the last, have maximum members of nodes, and all nodes in the last level having only one child it will be its left child name the tree.
(a) Full binary tree
(b) M-way search tree
(c) Complete binary tree
(d) Threaded tree
179:- A linear list in which elements ca be added or removed at either end is known as
(a) Deque
(b) Queue
(c) priorty queue
(d) Circular queue
180:- Items A,B,C,D and E are pushed onto a stack, in order. Then the stack is popped four times and each popped element is added to a FIFO queue, then two elements are removed from the queue and pushed onto a stack again in order. Finally,one element is popped from the stack. The popped element is..........
(a) B
(b) D
(c) A
(d) E
181:- Which of the following sorting algo is the slowest?
(a) Quick sort
(b) Shel sort
(c) Heap sort
(d) Bubble sort
182. Items A,B,C,D and E are added to an empty FIFO queue ,in order. The three elements are removed frpm the queue and pushed to an empty stack, in order.then two elements are popped from the stack and added to the queue, Finally, one elements is removed from the Queue. The removed element is
(a) B
(b) A
(c) D
(d) E
183:- Items A,B,C,D and E are pushed onto first stack, in order. Then the elements of stack are popped one by one and pushed onto second stack. Then the process is reversed, that is elements of second stack are popped one by one and pushed onto first stack. Which item will be on top of the first stack?
(a) E
(b) C
(c) A
(d) B
184:- If two trees have same structure and node content, then they are called __________
(a) similar trees
(b) equivalent trees
(c) joint trees
(d) synonyms trees
185:- Minimum number of fields in each node of a doubly linked list is ___________
(a) 2
(b) 3
(c) 4
(d) none of above
186:- Consider the following graph
Which of the following represents its correct topological sort?
(a) 2 1 3 4
(b) 1 2 3 4
(c) 1 3 4 2
(d) 1 3 4 2
187:- If two trees have same structure and but different node content, then they are called __________
(a) similar trees
(b) equivalent trees
(c) joint trees
(d) synonyms trees
188:- Consider the directed graph
Suppose the graph is represented using the following adjacency list
1-->2-->3
2-->4
3-->2-->4
4
Which of the following represents its correct breadth first search(BFS) with vertex 1 as the starting vertex?
(a) 2 1 3 4
(b) 1 2 3 4
(c) 1 3 2 4
(d) 1 3 4 2
189:- Consider the directed graph
Suppose the graph is represented using the following adjacency list
1-->2-->3
2-->4
3-->2-->4
4
Which of the following represents its correct depth first search (DFS) with vertex 1 as the starting vertex?
(a) 4 1 3 1
(b) 1 2 3 4
(c) 4 2 1 3
(d) 4 2 3 1
190:- Which of the following data structure can be used to represent many-to-many relation?
(a) binary tree
(b) graph
(c) B-tree
(d) all of above
191:- Given an arithmetic expression in infix notation as "(A+B)*C/D". What be its equivalent in postfix notation?
(a) AB+CD*/
(b) AB+C*/D
(c) AB+*CD/
(d) AB+C*D/
192:-Given following traversal of a tree T:
In-order : C F A K L D
Pre-order A C F D K L
The tree is
(a) (b) (c) (d)
193:- Given an arithmetic expression in infix notation as "(a+b)*c/d". what be its equivalent in prefix notation?
(a) +AB*/CD
(b) /*A+BCD
(c) /*+ABCD
(d) /+*ABCD
194:- The expresion "75 - 92/ * " in postfix notation evaluates to
(a) 10
(b) 9.5
(c) 9
(d) 11
195:- Given an arithmetic expression in postfix notation as "PQ+R*S/". What be its equivalent expression in infix notation?
(a) (P+Q)*R/S
(b) P+Q*R/S
(c) (P+Q)/R*S
(d) (P+Q*R)/S
196:-
which of the following data structure is more appropriate for
implementing quick sort iteratively?
(a) stack
(b) Queue
(c) priorty oueue
(d) deque
197:- Which of the following data structure is more appropriate
to represent a heap?
(a) Linked list
(b) Linear Array
(c) Doubly linked list
(d) Two-dimensional array
198:- The desired complexity of the pop operation on a stack, irrespective of whether it is implemented using an array or a linked list, must be......
(a)O(i)
(b)O(n)
(c)O(logn)
(d)O(nlogn)
199:- Which of the following operation is not supported by a queue?
(a) Inserting element at rear
(b) Removing element from front
(c) Removing element from middle
(d) None of above
200:- Which of the following statement is not true about linked lists?
(a) Elements are not necessarily stored in contigous location.
(b) Inserteion and deletions can be performed efficiently as
compared to arrays.
(c) Element in a linked list,if it is stored,can be quickely
searched by applying binary search technique.
(d) Linked list is a dynamic structure.
201. An enqueue operation adds an element
(a) to the rear of the queue
(b) to the front of the queue
(c) at any position in the queue
(d) none of above
202. Which of the following sequence of operations does not result in a queue containing: 2,3,5,7?
(a) enqueue(1), enqueue(2), enqueue(3), enqueue(5), enqueue(7), dequeue()
(b) enqueue(2), enqueue(3), enqueue(5), enqueue(7)
(c) enqueue(1), dequeue(), enqueue(2), enqueue(3), enqueue(5), enqueue(7)
(d) enqueue(2), enqueue(3), enqueue(4), dequeue(), enqueue(5), enqueue(7)
203. One difference between a queue and a stack is that
(a) Queues have a first-in-last-out algorithm; stacks have a first-in-first-out
(b) Stacks require implementation as a dynamic linked list; queues do not
(c) Queues require using two ends of the structure; stack use only one
(d) Stacks require using two ends of the structure; queues use only one
204. To implement a queue as a circular array of CAPACITY elements, we need to keep rear as an index to the tail of the queue, and front as an index to the head. What is the formula to calculate the position where an element should be pushed?
(a) front + 1
(b) (rear % CAPACITY) + 1
(c) (rear + 1) % CAPACITY
(d) (front + 1) % CAPACITY
205. Which of the following statements about a binary tree is not true?
(a) It allows traversals that are inorder, preorder, and postorder
(b) Each node has both a pointer to the left and a pointer to the right
(c) None of above
206. What is the maximum number of nodes at level l, when root is given level 0?
(a) 2l
(b) 2(l-1)
(c) 2l-1
(d) none of above
207. What is the maximum number of nodes in a binary tree of height h?
(a) 2h
(b) 2h+1
(c) 2h-1
(d) 2(h-1)
208. To perform level-order traversal on a binary tree, which of the following data structure will be required?
(a) Stack
(b) Binary search tree
(c) Queue
(d) Hash table
Question 209-213 pertains to the following binary tree.
Question#209
How many leaves does it have?
(a) 2
(b) 4
(c) 6
(d) 8
Question#210
How many of the nodes have at least one sibling?
(a) 5
(b) 6
(c) 7
(d) 8
Question#211
How many descendants does the root have?
(a) 2
(b) 6
(c) 7
(d) 8
Question#212
What is the depth of the tree?
(a) 2
(b) 4
(c) 5
(d) 3
Question#213
Which of the following statement is correct?
(a) The tree is neither complete not full
(b) The tree is complete but not full
(c) The tree is full but not complete
(d) The tree is both full and complete
Question#214
What is the number of nodes in a full binary tree with depth 3?
(a) 5
(b) 6
(c) 7
(d) 8
Question#215
What is the minimum number of nodes in a complete binary tree with depth 3?
(a) 4
(b) 5
(c) 7
(d) 6
Question#216
Which of the following statements about a binary tree is correct?
(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) No binary tree is both complete and full
Question#217
Suppose T is a binary tree with 14 nodes. What is the minimum possible height of T?
(a) 4
(b) 5
(c) 3
(d) 6
Question#218
Suppose T is a binary tree with 14 nodes. What is the maximum possible height of T?
(a) 4
(b) 14
(c) 10
(d) 9
Question#219
Which of the following statements about a binary tree is not correct?
(a) Every binary tree has at least one node
(b) Every non-empty tree has exactly one root node
(c) Every node has at most two children
(d) Every non-root node has exactly one parent
Question#220
Consider the node of a complete binary tree whose value is stored in tree[i] for an array implementation. If this node has a right child, where will the right child’s value be stored?
(a) tree[i+1]
(b) tree[2*i]
(c) tree[2*i+1]
(d) tree[2*i+2]
Question#221
Tree algorithms typically run in time O(d). What is d?
(a) The height of the tree
(b) The number of nodes at level d
(c) The number of nodes in the tree
(d) The number of leaf nodes
Question 222-225 pertains to the following tree.
Question#222
What is the order of nodes visited using a pre-order traversal?
(a) 1 2 3 14 7 10 11 40 30
(b) 14 2 1 3 11 10 7 30 40
(c) 1 3 2 7 10 40 30 11 14
(d) 14 2 11 1 3 10 30 7 40
Question#223
What is the order of nodes visited using an in-order traversal?
(a) 1 2 3 14 7 10 11 40 30
(b) 14 2 1 3 11 10 7 30 40
(c) 1 3 2 7 10 40 30 11 14
(d) 14 2 11 1 3 10 30 7 40
Question#224
What is the order of nodes visited using a post-order traversal?
(a) 1 2 3 14 7 10 11 40 30
(b) 14 2 1 3 11 10 7 30 40
(c) 1 3 2 7 10 40 30 11 14
(d) 14 2 11 1 3 10 30 7 40
Question#225
What is the order of nodes visited using a level-order traversal?
(a) 1 2 3 14 7 10 11 40 30
(b) 14 2 1 3 11 10 7 30 40
(c) 1 3 2 7 10 40 30 11 14
(d) 14 2 11 1 3 10 30 7 40
Question#226
Consider the following binary search tree
Suppose we remove the root, replacing it with something from the left subtree. What will be the new root?
(a) 12
(b) 16
(c) 9
(d) 13
Question#227
Consider the following binary search tree
Suppose we remove the root, replacing it with something from the right subtree. What will be the new root?
(a) 25
(b) 27
(c) 45
(d) 39
Question#228
What feature of heaps allows them to be efficiently implemented using a partially filled array?
(a) Heaps are binary search trees
(b) Heaps are complete binary trees
(c) Heaps are full binary trees
(d) Heaps contain only integer data
Question#229
If a max heap is implemented using a partially filled array named data[1..CAPACITY-1], and the array contains n elements (n>0), where is the entry with the greatest value?
(a) data[1]
(b) data[n-1]
(c) data[2*n+1]
(d) data[2*n+2]
Question#230
Select the true statement about the worst-case time for operation on heaps.
(a) Neither insertion nor removal is better than linear
(b) Insertion is better than linear, but removal is not
(c) Removal is better than linear, but insertion is not
(d) Both insertion and removal are better than linear
Question#231
Suppose that we have implemented a priority queue by storing the items in a max heap, where max heap is represented using a partially filled array named data[1..CAPACITY-1]. We are now executing an reheapify upward operation and the out-of-place node is at data[i] with priority given by data[i]. Which of the following Boolean expressions is TRUE to indicate that the reheapify upward IS NOT YET DONE?
(a) i > 1
(b) data[i/2] < data[i]
(c) i > 1 && data[i/2]
(d) i > 1
data[i/2] < data[i]
Question#232
Suppose that we have implemented a priority queue by storing the items in a max heap, where max heap is represented using a partially filled array named data[1..CAPACITY-1]. We are now executing an reheapify downward operaton and the out-of-place node is at data[i] with priority given by data[i]. Which of the following boolean expression is TRUE to indicate that the reheapify downward IS NOT YET DONE?
(a) i < CAPACITY-1
(b) data[i] < max(data[2i], data[2i+1])
(c) i < CAPACITY-1
data[i] < max(data[2i], data[2i+1)
(d) i < CAPACITY-1 && data[i] < max(data[2i], data[2i+1])
Question#233
Suppose that we have implemented a priority queue by storing the items in a max heap, where max heap is represented using a partially filled array named data[1..CAPACITY-1]. We are now executing a reheapify upward operation and the out-of-place node has priority of 42. The node’s parent has a priority of 72, the left child has priority 52 and the right child has priority 62. Which statement best describes the status of the reheapify upward operation?
(a) The reheapify upward is done
(b) It will interchange the two children of the out-of-place node
(c) It will swap the out-of-place node with its parent
(d) It will swap the out-of-place node with its right child
Question#234
Which of the following formula gives best approximation for the height of a heap with n nodes?
(a) log2n
(b) log10n
(c) n
(d) n(1/2)
Question#235
A graph is a tree if and only if graph is
(a) completely connected
(b) planar
(c) contains no cycles
(d) directed graph
236. In the linked list implementation of the queue class, where does the insert method place the new entry on the linked list?
A. At the head
B. At the tail
C. After all other entries that are greater than the new entry.
D. After all other entries that are smaller than the new entry.
237. In the circular array version of the Queue class, which operations require linear time for their worst-case behavior?
A. getFront
B. insert when the capacity has not yet been reached
C. isEmpty
D. None of these operations require linear time.
238. In the linked-list version of the Queue class, which operations require linear time for their worst-case behavior?
A. getFront
B. insert
C. isEmpty
D. None of these operations require linear time.
239. If data is a circular array of CAPACITY elements, and rear is an index into that array, what is the formula for the index after rear?
A. (rear % 1) + CAPACITY
B. rear % (1 + CAPACITY)
C. (rear + 1) % CAPACITY
D. rear + (1 % CAPACITY)
240. I have implemented the queue with a circular array, keeping track of front, rear, and manyItems (the number of items in the array). Suppose front is zero, and rear is one less than the current capacity. What can you tell me about manyItems?
A. manyItems must be zero.
B. manyItems must be equal to the current capacity.
C. count could be zero or the capacity, but no other values could occur.
D. None of the above.
241. I have implemented the queue with a linked list, keeping track of a front node and a rear node with two reference variables. Which of these reference variables will change during an insertion into a NONEMPTY queue?
A. Neither changes
B. Only front changes.
C. Only rear changes.
D. Both change.
242. I have implemented the queue with a linked list, keeping track of a front node and a rear node with two reference variables. Which of these reference variables will change during an insertion into an EMPTY queue?
A. Neither changes
B. Only front changes.
C. Only rear changes.
D. Both change.
243. Suppose getFront is called on a priority queue that has exactly two entries with equal priority. How is the return value of getFront selected?
A. One is chosen at random.
B. The one which was inserted first.
C. The one which was inserted most recently.
D. This can never happen (violates the precondition)
244. An array of queues can be used to implement a priority queue, with each possible priority corresponding to its own element in the array. When is this implementation not feasible?
A. When the number of possible priorities is huge.
B. When the number of possible priorities is small.
C. When the queues are implemented using a linked list.
D. When the queues are implemented with circular arrays.
245. There is a tree in the box at the top of this section. How many leaves does it have?
A. 2
B. 4
C. 6
D. 8
E. 9
246. There is a tree in the box at the top of this section. How many of the nodes have at least one sibling?
A. 5
B. 6
C. 7
D. 8
E. 9
247. There is a tree in the box at the top of this section. What is the value stored in the parent node of the node containing 30?
A. 10
B. 11
C. 14
D. 40
E. None of the above
248. There is a tree in the box at the top of this section. How many descendants does the root have?
A. 0
B. 2
C. 4
D. 8
249. There is a tree in the box at the top of this section. What is the depth of the tree?
A. 2
B. 3
C. 4
D. 8
E. 9
250. There is a tree in the box at the top of this section. How many children does the root have?
A. 2
B. 4
C. 6
D. 8
E. 9
251. Consider the binary tree in the box at the top of this section. Which statement is correct?
A. The tree is neither complete nor full.
B. The tree is complete but not full.
C. The tree is full but not complete.
D. The tree is both full and complete.
252. What is the minimum number of nodes in a full binary tree with depth 3?
A. 3
B. 4
C. 8
D. 11
E. 15
253. What is the minimum number of nodes in a complete binary tree with depth 3?
A. 3
B. 4
C. 8
D. 11
E. 15
254. Select the one true statement.
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. No binary tree is both complete and full.
255. Suppose T is a binary tree with 14 nodes. What is the minimum possible depth of T?
A. 0
B. 3
C. 4
D. 5
256. Select the one FALSE statement about binary trees:
A. Every binary tree has at least one node.
B. Every non-empty tree has exactly one root node.
C. Every node has at most two children.
D. Every non-root node has exactly one parent.
257. Suppose t is a BTNode variable from Chapter 9, which expression indicates that t represents an empty tree?
A. (t == null)
B. (t->data == 0)
C. (t->data == null)
D. ((t->left == null) && (t->right == null))
258. Consider the node of a complete binary tree whose value is stored in data[i] for an array implementation. If this node has a right child, where will the right child's value be stored?
A. data[i+1]
B. data[i+2]
C. data[2*i + 1]
D. data[2*i + 2]
259. Suppose that a binary taxonomy tree includes 8 animals. What is the minimum number of NONLEAF nodes in the tree?
A. 1
B. 3
C. 5
D. 7
E. 8
14
/ \
2 11
/ \ / \
1 3 10 30
/ /
7 40
260. There is a tree in the box at the top of this section. What is the order of nodes visited using a pre-order traversal?
A. 1 2 3 7 10 11 14 30 40
B. 1 2 3 14 7 10 11 40 30
C. 1 3 2 7 10 40 30 11 14
D. 14 2 1 3 11 10 7 30 40
261. There is a tree in the box at the top of this section. What is the order of nodes visited using an in-order traversal?
A. 1 2 3 7 10 11 14 30 40
B. 1 2 3 14 7 10 11 40 30
C. 1 3 2 7 10 40 30 11 14
D. 14 2 1 3 11 10 7 30 40
262. There is a tree in the box at the top of this section. What is the order of nodes visited using a post-order traversal?
A. 1 2 3 7 10 11 14 30 40
B. 1 2 3 14 7 10 11 40 30
C. 1 3 2 7 10 40 30 11 14
D. 14 2 1 3 11 10 7 30 40
263. Consider this binary search tree:
14
/ \
2 16
/ \
1 5
/
4
Suppose we remove the root, replacing it with something from the left subtree. What will be the new root?
A. 1
B. 2
C. 4
D. 5
E. 16
264. What is the worst-case time for serial search finding a single item in an array?
A. Constant time
B. Logarithmic time
C. Linear time
D. Quadratic time
265. What is the worst-case time for binary search finding a single item in an array?
A. Constant time
B. Logarithmic time
C. Linear time
D. Quadratic time
266. What additional requirement is placed on an array, so that binary search may be used to locate an entry?
A. The array elements must form a heap.
B. The array must have at least 2 entries.
C. The array must be sorted.
D. The array's size must be a power of two.
267. What is the best definition of a collision in a hash table?
A. Two entries are identical except for their keys.
B. Two entries with different data have the exact same key.
C. Two entries with different keys have the same exact hash value.
D. Two entries with the exact same key have different hash values.
268. Which guideline is NOT suggested from from empirical or theoretical studies of hash tables:
A. Hash table size should be the product of two primes.
B. Hash table size should be the upper of a pair of twin primes.
C. Hash table size should have the form 4K+3 for some K.
D. Hash table size should not be too near a power of two.
269. In an open-address hash table there is a difference between those spots which have never been used and those spots which have previously been used but no longer contain an item. Which method has a better implementation because of this difference?
A. put
B. containsKey
C. remove
D. size
E. Two or more of the above methods
270. What kind of initialization needs to be done for an open-address hash table?
A. None.
B. The key at each array location must be initialized.
C. The head pointer of each chain must be set to null.
D. Both B and C must be carried out.
271. What kind of initialization needs to be done for a chained hash table?
A. None.
B. The key at each array location must be initialized.
C. The head pointer of each chain must be set to null.
D. Both B and C must be carried out.
272. A chained hash table has an array size of 512. What is the maximum number of entries that can be placed in the table?
A. 256
B. 511
C. 512
D. 1024
E. There is no maximum.
273. Suppose you place m items in a hash table with an array size of s. What is the correct formula for the load factor?
A. s + m
B. s - m
C. m - s
D. m * s
E. m / s
274. In a selection sort of n elements, how many times is the swap function called in the complete execution of the algorithm?
A. 1
B. n - 1
C. n log n
D. n²
275. Selection sort and quick sort both fall into the same category of sorting algorithms. What is this category?
A. O(n log n) sorts
B. Divide-and-conquer sorts
C. Interchange sorts
D. Average time is quadratic.
276. Suppose that a selection sort of 100 items has completed 42 iterations of the main loop. How many items are now guaranteed to be in their final spot (never to be moved again)?
A. 21
B. 41
C. 42
D. 43
277. Suppose we are sorting an array of ten integers using some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here:
1 2 3 4 5 0 6 7 8 9
Which statement is correct? (Note: Our selection sort picks largest items first.)
A. The algorithm might be either selection sort or insertion sort.
B. The algorithm might be selection sort, but could not be insertion sort.
C. The algorithm might be insertion sort, but could not be selection sort.
D. The algorithm is neither selection sort nor insertion sort.
278. Suppose we are sorting an array of eight integers using a some quadratic sorting algorithm. After four iterations of the algorithm's main loop, the array elements are ordered as shown here:
2 4 5 7 8 1 3 6
Which statement is correct? (Note: Our selection sort picks largest items first.)
A. The algorithm might be either selection sort or insertion sort.
B. The algorithm might be selection sort, but it is not insertion sort.
C. The algorithm is not selection sort, but it might be insertion sort.
D. The algorithm is neither selection sort nor insertion sort.
279. When is insertion sort a good choice for sorting an array?
A. Each component of the array requires a large amount of memory.
B. Each component of the array requires a small amount of memory.
C. The array has only a few items out of place.
D. The processor speed is fast.
280. What is the worst-case time for mergesort to sort an array of n elements?
A. O(log n)
B. O(n)
C. O(n log n)
D. O(n²)
281. What is the worst-case time for quicksort to sort an array of n elements?
A. O(log n)
B. O(n)
C. O(n log n)
D. O(n²)
282. Mergesort makes two recursive calls. Which statement is true after these recursive calls finish, but before the merge step?
A. The array elements form a heap.
B. Elements in each half of the array are sorted amongst themselves.
C. Elements in the first half of the array are less than or equal to elements in the second half of the array.
D. None of the above.
283. Suppose we are sorting an array of eight integers using quicksort, and we have just finished the first partitioning with the array looking like this:
2 5 1 7 9 12 11 10
Which statement is correct?
A. The pivot could be either the 7 or the 9.
B. The pivot could be the 7, but it is not the 9.
C. The pivot is not the 7, but it could be the 9.
D. Neither the 7 nor the 9 is the pivot.
284. What is the worst-case time for heapsort to sort an array of n elements?
A. O(log n)
B. O(n)
C. O(n log n)
D. O(n²)
285. Suppose we are sorting an array of eight integers using heap sort, and we have just finished one of the reheapifications downward. The array now looks like this:
6 4 5 1 2 7 8
How many reheapifications downward have been performed so far?
A. 1
B. 2
C. 3 or 4
D. 5 or 6
286. In a real computer, what will happen if you make a recursive call without making the problem smaller?
A. The operating system detects the infinite recursion because of the "repeated state"
B. The program keeps running until you press Ctrl-C
C. The results are nondeterministic
D. The run-time stack overflows, halting the program
287. When the compiler compiles your program, how is a recursive call treated differently than a non-recursive method call?
A. Primitive values are all treated as reference variables
B. Reference variables are all treated as primitive values
C. There is no duplication of local variables
D. None of the above
288. When a method call is executed, which information is not saved in the activation record?
A. Current depth of recursion.
B. Formal parameters.
C. Location where the method should return when done.
D. Local variables.
289. Consider the following statements:
int *p;
int i;
int k;
i = 42;
k = i;
p = &i;
After these statements, which of the following statements will change the value of i to 75?
A. k = 75;
B. *k = 75;
C. p = 75;
D. *p = 75;
E. Two or more of the answers will change i to 75.
290. Consider the following statements:
int i = 42;
int j = 80;
int *p1;
int *p2;
p1 = &i;
p2 = &j;
*p1 = *p2;
cout << i << j << endl;
What numbers are printed by the output statement?
A. 42 and then another 42
B. 42 and then 80
C. 80 and then 42
D. 80 and then another 80
291. What is printed by these statements?
int i = 1;
int k = 2;
int *p1;
int *p2;
p1 = &i;
p2 = &k;
p1 = p2;
*p1 = 3;
*p2 = 4;
cout << i;
A. 1
B. 2
C. 3
D. 4
292. What is printed by these statements?
int i = 1;
int k = 2;
int* p1;
int* p2;
p1 = &i;
p2 = &k;
p1 = p2;
*p1 = 3;
*p2 = 4;
cout << k;
A. 1
B. 2
C. 3
D. 4
293.What is printed by these statements?
int i = 1;
int k = 2;
int* p1;
int* p2;
p1 = &i;
p2 = &k;
*p1 = *p2;
*p1 = 3;
*p2 = 4;
cout << i;
A. 1
B. 2
C. 3
D. 4
294.When allocating an array of objects, what constructor is used to initialize all of the objects in the array?
A. The automatic copy constructor.
B. The constructor specified at the declaration.
C. The default constructor.
D. None of the above.
295.In which location do dynamic variables reside?
A. The code segment.
B. The data segment.
C. The heap.
D. The run-time stack.
296. When should a pointer parameter p be a reference parameter?
A. When the function changes p, and you want the change to affect the actual pointer argument.
B. When the function changes p, and you do NOT want the change to affect the actual pointer argument.
C. When the function changes *p, and you want the change to affect the the object that is pointed at.
D. When the function changes *p, and you do NOT want the change to affect the the object that is pointed at.
E. When the pointer points to a large object.
297.Suppose you have the following function prototype and variable declaration:
void goop(int z[ ]);
int x[10];
Which is the correct way to call the goop function with x as the argument:
A. goop(x);
B. goop(x[ ]);
C. goop(x[10]);
D. goop(&x);
E. goop(&x[ ]);
298.Suppose that the goop function from the previous question changes the value of z[1]. Does this change effect the value of the actual argument?
A. Yes
B. No
299.Here is a function declaration:
void goo(int* x)
{
*x = 1;
}
Suppose that a is an int* variable pointing to some integer, and *a is equal to zero. What is printed if you print *a after the function call goo(a)?
A. 0
B. 1
C. address of a
D. address of x
E. None of the above
300.Suppose you are implementing an assignment operator, a copy constructor, and an operator +=. For which of these functions do you need to worry about possible "self-application" (where the argument is the same as the object that activates the function):
A. Only one of the three functions has possible self-application
B. The assignment operator and the copy construtor have possible self-application
C. The assignment operator and the operator += have possible self-application
D. The copy construtor and the operator += have possible self-application
E. All three functions have possible self-application
301.What is the usual worst-case performance for resizing a container class that stores its data in a dynamic array?
A. Constant time
B. Logarithmic time
C. Linear time
D. Quadratic time
302.When a class uses dynamic memory, what member functions should be provided by the class?
A. The assignment operator.
B. The copy constructor.
C. A destructor.
D. All of the above.
303.Which situation does not use the copy constructor?
A. Calling a function with a reference parameter
B. Calling a function with a value parameter
C. Declaring a variable to be a copy of another existing object
D. Returning a value from a function
E. All of the above situations use the copy constructor
304. Suppose that you want to declare an array of characters to hold a C++ string with exactly 9 letters. Which declaration is best?
A. char s[8];
B. char s[9];
C. char s[10];
D. char s[11];
E. char s[12];
305.Suppose that x and y are two C++ strings. Which expression will return true whenever x and y contain the same sequence of characters?
A. (x = y)
B. (x == y)
C. (x != y)
D. (strcmp(x, y))
306.Suppose that you want to develop two different + operators that calculate and return an object of some class. Which statement is correct?
A. One operator must be a friend and the other must not.
B. One operator must be public and the other private.
C. The operators must have a different parameter lists.
D. It is not possible to have two different + operators
307. Linked lists are collections of data items "lined up in a row"—insertions and deletions can be made only at the front and the back of a linked list.
True
False
308. Binary trees facilitate high-speed searching and sorting of data, efficient elimination of duplicate data items, compilation of expressions into machine language and many other interesting applications.
True
False
309. Self-referential objects can be linked together to form useful data structures such as lists, queues, stacks and trees.
True
False
310. A null pointer normally indicates the end of a data structure.
True
False
311. The limit for dynamic memory allocation can be as large as the amount of available physical memory in the computer or the amount of available disk space in a virtual-memory system
True
False
312. The size of lists, stacks, queues and trees must be determined in advance of using these data structures to ensure that the proper amount of memory is allocated for their elements.
True
False
313. Stacks and queues are linear data structures and are constrained versions of linked lists.
True
False
314. Conventional Java arrays can change size dynamically to accommodate new elements.
True
False
315. An array can be declared to contain more elements than the number of items expected, but this can waste memory. Linked lists can provide better memory utilization in these situations. Linked lists allow the program to adapt at run time.
True
False
316. The elements of a linked list are stored contiguously in memory. This allows immediate access to any linked list element because the address of any element can be calculated directly based on its offset from the beginning of the linked list.
True
False
317. The primary methods used to manipulate a stack are put and get. Method put adds a new node to the top of the stack. Method get removes a node from the top of the stack and returns the data object from the popped node.
True
False
318. Compilers use stacks to evaluate arithmetic expressions and generate machine language code to process the expressions. [
True
False
319. Composition enables us to hide the methods of class List that should not be in the interface to a stack by providing public interface methods only to the required List methods. This technique of implementing each stack method as a call to a List method is called offloading—the stack method invoked delegates the call to the appropriate List method.
True
False
320. Information packets wait in queues in computer networks. Each time a packet arrives at a network node, it must be routed to the next node on the network along the path to the packet's final destination. The routing node routes one packet at a time, so additional packets are enqueued until the router can route them.
True
False
321. A queue can be implemented by extending a stack class. ] True
False
322. Computer scientists normally draw trees from the root node down—exactly the opposite of the way most trees grow in nature.
True
False
323. The steps for an inorder traversal are:
1. Traverse the left subtree.
2. Process the value in the node.
3. Traverse the right subtree.
True
False
324. The steps for a postorder traversal are:
1. Process the value in the node.
2. Traverse the left subtree.
3. Traverse the right subtree.
True
False
True or False Quiz
325.
Which of the following abstract data types are NOT used by Integer Abstract Data type group?
Short
Int
float
long
326.
The byte abstract data type is the smallest abstract data type in the integer group and is declared by using the keyword byte
True
False
327.
Signed numbers do not have any impact on the memory
True
False
