 Suppose that Table is an array of records used to implement a
linked list, as shown below.
Each component of Table contains an information field and a
pointer to the next element in a linked list. (The pointer values are
indices of Table, and 0 signifies the end of a list.) What is the
list off characters starting with Table[5]?
 da
 djaba
 daadjaba
 dajabadj
 dadjhlabce
 Which of the following is true of stacks and queues?
 A stack is a lastin, firstout structure, and a queue is a
firstin, firstout structure
 A stack is a firstin, firstout structure, and both structures
are random access structures.
 A stack is a lastin, firstout structure, and a queue is a random
access structure.
 A queue is a lastin, firstout structure, and a stack is a
firstin, firstout structure.
 A queue is a firstin, firstout structure, and a stack is a
random access structure.
Questions 3839 are based on the following information.
A newspaper route has recently been computerized. Information about each
of the 100 customers is stored in individual records containing first
name, last name, and payment due. In writing a computer program to
process the customer records, the programmer is uncertain whether to add
a procedure to sort the records.
 If the records are not sorted, what is the maximum possible
number of comparisons that must be made to obtain a particular customer's
record using a sequential search?
 100
 50
 7
 5
 3
 If the records are first sorted, what will be the maximum number of
comparisons needed with a binary search to find a particular customer's
record?
 100
 50
 7
 5
 3
 What is the least order of execution time for the following code
segment, if the segment terminates without error?
i := 1;
Count := 0;
while i < N do
begin
Current := A[i];
while (Current = A[i]) and (i < N) do
i := i + 1;
Count = Count + 1
end
 O(log N)
 O(√N)
 O(N)
 O(N log N)
 O(N^{2})
 If the inorder traversal of the binary tree T is
A D B G C F E
and each node of T has either 0 or 2 children, which of the
following nodes is NOT a leaf of that tree?
 A
 B
 C
 D
 E
 In a procedure, value parameters do not necessarily protect the contents
of the caller's data structures from being affected by execution of the
procedure under which of the following conditions?
 The procedure is recursive.
 The value parameters are integers.
 The value parameters are pointers.
 The value parameters are arrays.
 The procedure is used with a forward declaration.
 The alphamem, a new data structure, supports two operations.
The insert operation allows "words" to be stored in the
alphamem.
The remove operation causes the "word" in the alphamem
which is first alphabetically to be printed and removed from the
alphamem.
Which of the following is true of an alphamem?
 If words are inserted in alphabetical order and all words are
inserted before any are removed, then it works like a stack
 If words are inserted in alphabetical order, then it works like a
stack whether or not all inserts precede any removes.
 If all words are inserted before any are removed, then it works
like a queue.
 If words are inserted in reverse alphabetical order, then it works
like a queue whether or not all inserts precede any removes.
 If words are inserted in alphabetical order, then it works like a
queue whether or not all inserts precede any removes.
 Consider the partially completed program below.
Root := 0;
Lim := n;
while BBB do
{ Invariant: (Root)^{2} ≤ n ≤ (Lim + 1)^{2} }
begin
<code to increment Root or decrement Lim,>
<leaving Invariant true >
end
With which of the following should BBB be replaced in order for
the loop above to compute an integer approximation of the square root of
nonnegative n>?
 Lim <> Root
 Lim = Root
 Root * Root <> n
 Lim * Lim <> n
 Lim * Lim = Root * Root
 Suppose that the only Pascal implementation available does not support
pointers or dynamic storage allocation using new. A Pascal
program is given that uses pointers and new for creating and
manipulating instances of the following type.
type
NodePtr = ^Node;
Node = record
Info : integer;
Next : NodePtr
end;
To modify this program so that it can be run using the available
resources, one should
 simulate pointers by using indices into a large array, and change
the program accordingly
 simulate pointers by using trees and recursion
 simulate pointers by using a combination of value parameters and
var parameters
 modify the Pascal implementation so that it does support pointers
and new
 identify the queues and stacks in the program, and reimplement
each by using an array
 A property of binary trees is said to be an "inherited" property if each
of the subtrees has the property whenever the binary tree itself does.
One inherited property for binary tree is having
 an odd number of nodes
 an even number of nodes
 the same number of nodes in the left and right subtrees
 at least 10 nodes
 no node with exactly one child
 Consider the following procedure.
procedure Delete(p : Pointer);
{ Deletes the node pointed to by p from a doubly linked list }
{ (without a header node) whose pointer fields are called }
{ BackLink and NextLink. }
begin
p^.BackLink^.NextLink = p^.NextLink;
p^.NextLink^.BackLink = p^.BackLink;
end;
In which of the following cases will the procedure above fail to work
properly?
 p points to the first node in the list.
 p points to the last node in the list.
 p = nil
 III only
 I and II only
 I and III only
 II and III only
 I, II, and III
 Of the following, which has the most impact on the efficiency of
searching for an item in a hash table?
 The number of nonkey fields
 The size of the table
 The density of the table
 Whether the size of the table is a prime number
 The difficulty of computing the inverse of the hash function
 Of the following data structures, which would be best suited for an
application where search time must be minimized and where data can be
easily added?
 Singly linked list
 Sorted array
 Hash table
 Sequential file
 Circularly linked list with two header nodes
 The program segment below uses a Monte Carlo technique to approximate
the area of the shaded region shown. The function Random returns
a real number in the range 0 ≤ Random < 1 each time it is
executed. Assume that the numbers are randomly chosen.
Points := 0;
for i := 1 to n do
begin
x := Random;
y := Random;
S
end;
Area := Points/n
Which of the following statements should be used in place of S to
make the segment work as indicated?

if y >= 1  x*x then Points := Points + 1

if y <= 1  x*x then Points := Points + 1

if y < 1  x*x then
Points := Points + 1
else
Points := Points  1

if y = 1  x*x then Points := Points + 1

if y > 1  x*x then Points := Points + 1
The contents of this web page come from