Data Structure Exam 2

1. How is the order of the entries of an ADT list determined?

a) by the list itself

b) by the client

c) by the operating system

d) the order doesn't matter

B.

2. Which element of the list does not have a unique predecessor?

a) the head of the list

b) the tail of the list

c) the middle element of the list

d) all have unique predecessors

A.

3. Changing the value of an entry at a given position on the list would probably be the task of which of these

methods?

a) replace

b) get

c) push

d) insert

A.

# What type would the getLength method for a list return?

a) boolean

b) ItemType

c) integer

d) void

C

4. Which of the following list methods would have only one parameter?

a) isEmpty

b) setEntry

c) insert

d) remove

D

5. Which of the following methods from list would have no parameters and void for the return type?

a) setEntry

b) getEntry

c) insert

d) clear

D.

6. Given bList: snibble, nibble, tribble, wibble, quibble. The command

bList.insert(3, Bob) is executed. What is the appearance of the list?

a) snibble, nibble, tribble, Bob, wibble, quibble

b) snibble, nibble, Bob, tribble, wibble, quibble

c) snibble, nibble, tribble, wibble, quibble, Bob, Bob, Bob

d) Bob, Bob, Bob, snibble, nibble, tribble, wibble, quibble

B.

7. Given bList: bob, slob, snob, cob, hob, rob and the operation bList.remove(4) is

executed. What does the list become?

a) bob, slob, snob, hob, rob

b) bob, slob, snob, cob, rob

c) bob, slob

d) hob, rob

A.

8. Given cList: bip, snip, pip, rip, dip, clip. What value would be returned by the call to

method cList.getEntry(3)?

a) bip

b) snip

c) pip

d) rip

C.

9. Given cList: bip, snip, pip, rip, dip, clip. What value would be returned by the call to

method cList.insert(9, sip)?

a) true

b) false

c) it throws an exception

d) sip

B.

10. What should be returned by the list operation (aList.insert(2,x)).getEntry(2) ?

a) false

b) 2

c) x

d) an exception is thrown

C.

11. What would be returned by the list operation (bList.insert(3,x)).remove(3)?

a) 2

b) x

c) false

d) bList

D.

12. Consider nameList of size 12. For the operation nameList.insert(Clyde,x), which of the

following would be an invalid value for x?

a) 0

b) 1

c) 3

d) 12

A

13. Given the commands below, what do they do?

n = 0

for (position = 1 through intList.getLength())

n+= intList.getEntry(position)

a) insert integers into the list

b) sum the values found in list

c) sum the numbers 0 through n

d) calculate n!

B.

14. Given the commands below, what do they do?

for (position = 1 through aList.getLength()/2)

{

a = aList.getEntry(aList.getLength()-position+1)

aList.setEntry(aList.getEntry(aList.getLength()-position+1))

aList.setEntry(a,position)

}

a) randomize the entries

b) sort the entries

c) reverse the order of the entries

d) count how many entries there are

C.

1. A pointer variable contains the ______ of a memory cell.

a. content

b. address

c. data type

d. ADT

b.

2. The members of a node structure can be accessed with the ______ operator.

a. []

b. &

c. ->

d. at

c.

3. A pointer variable whose sole purpose is to locate the first node in a linked list is called ______.

a. the list's top

b. the node's link

c. the list's link

d. the list's head

d.

4. A(n) ______ operation sequentially visits each node in a linked list.

a. access

b. delete

c. get

d. traverse

d.

5. To remove a node N from a linear linked list, you will need to ______.

a. set the pointer next in the node that precedes N to point to the node that follows N

b. set the pointer next in the node that precedes N to point to N

c. set the pointer next in the node that follows N to point to the node that precedes N

d. set the pointer next in N to point to the node that follows N

a.

6. Which of the following statements deletes the node to which cur points?

a. prev->next = cur;

b. cur->next = prev;

c. cur->next = cur->next;

d. prev->next = cur->next;

d.

7. Which of the following statements deletes the first node of a linear linked list that has 10 nodes?

a. head->next = cur->next;

b. prev->next = cur->next;

c. head = head->next;

d. head = NULL;

c.

8. Which of the following statements inserts a new node, pointed to by newPtr, at the end of a linear linked list?

a. newPtr->next = cur;

prev->next = newPtr;

b. newPtr->next = head;

head = newPtr;

c. newPtr->next = NULL;

d. prev->next = cur;

newPtr->next = cur;

a.

9. A ______ allows the deletion of a node from a linked list without the need to traverse the list to establish a trailing reference.

a. head pointer

b. dummy head node

c. tail pointer

d. precede pointer

d.

10. The author suggests that when you first look at implementing an ADT List, that "list" is simply a fancy name for

a. an array

b. a bag

c. a linked list

d. a stack

a.

11. What operation does the ADT List have that an array does not?

a. identify their items by number

b. getLength()

c. insertItem()

d. isEmpty()

B.

12. When designing an array based implementation of an ADT List, which of the following are not specified as private?

a. items

b. itemCount

c. clear()

d. maxItems

C.

13. What is the return type of the list operator remove(int position)?

a. void

b. int

c. itemType

d. bool

D.

14. Which of the following operators uses two parameters?

a. insert

b. getLength

c. remove

d. clear

A.

15. Given the following diagram.

What list operation does this depict?

a. deleting an item in the list

b. inserting an item in the list

c. expanding the array to make it larger

d. counting the number of items in the list

B.

16. To thoroughly test the insert method in an array-based implementation of ADT List, what other method do we need?

a. clear

b. remove

c. getEntry

d. the constructor

C.

17. Given the following diagram.

What list operation does this depict?

a. deleting an item in the list

b. inserting an item in the list

c. expanding the array to make it larger

d. counting the number of items in the list

A.

18. In the author's array based implementation of the ADT List, to what one variable does the clear method assign a value?

a. items[0]

b. items[maxItems]

c. position

d. itemCount

D.

19. In the list based implementation of the ADT List, which of the following is not a private variable in the classe?

a. headPtr

b. isEmpty

c. itemCount

d. getNodeAt

B

20. Given the following diagram.

What List action does this depict?

a. insert a new node

b. get the value stored at a node

c. remove a node from the chain

d. get the value stored at a node

C.

21. In the link based implementation of the ADT List, what method does the destructor call?

a. remove

b. insert

c. isEmpty

d. clear

D.

22. Given the following pseudocode logic:

if ( the insertion position is 1 )

Add the new node to the beginning of the chain

else

Ignore the first node and add the new node to the rest of the chain

What does this describe?

a. recursive addition of a node to the list

b. iterative addition of a node to the list

c. addition of a node to the beginning of the list

d. adding a node to the end of the list

A.

23. In an array based implementation of the ADT List, what is a characteristic of the time required to access any particular element in the list?

a. you have no way of knowing how long it will take

b. the time required is a constant

c. the time required is a function of the size of the list

d. It is of order O(n2)

B

24. When calling the insert or remove methods, what is an advantage for the link-based implementation of the ADT List?

a. searching for that position is quicker

b. takes less memory

c. no need to shift data

d. easier to understand

C.

25. When calling the insert or remove methods, what is an disadvantage for the link-based implementation of the ADT List?

a. searching for that position is slower

b. takes more memory

c. must shift data

d. harder to understand

A.

26. Adding or removing an entry anywhere within a link based list requires a change of at least how many pointers?

a. one

b. two

c. three

d. four

B.

27. A link based getEntry method requires how many steps to access the nth item in the list?

a. n - 1

b. n

c. n + 1

d. n2

B.

28. In either the link based or array based implementation of the ADT List, what is the single parameter for both the remove and getEntry methods?

a. itemCount

b. maxItems

c. position

d. ItemType

C.

29. What is the last step in the insertion process for a linked implementation of the ADT List?

a. Connect the new node to the linked chain by changing pointers

b. Create a new node and store the new data in it

c. Determine the point of insertion

d. The order of these steps really doesn't matter

A.

30. What is the first step in the deletion process for a linked implementation of the ADT List?

a. Return the node to the system

b. Disconnect the node from the linked chain by changing pointers

c. Locate the node you want to delete

d. The order of these steps really doesn't matter

C.

1. Which of the following is NOT part of the human cost of developing a computer program?

a. efficiency of a program

b. the the readability of a program

c. the modifiability of a program

d. the maintainability a program

a.

2. Algorithm analysis should be independent of all of the following EXCEPT ______.

a. the programming style used in the implementation of the algorithm

b. the computer used to run a program which implements an algorithm

c. the number of significant operations in an algorithm

d. the test data used to test a program which implements an algorithm

c.

3. An algorithm's execution time is related to the number of ______ it requires.

a. parameters

b. test data sets

c. data fields

d. operations

d.

4. Assuming a linked list of n nodes, the C++ statements

Node *cur = head;

while (cur != null)

{ cout << curr->item << endl;

cur = cur->next;

} // end while

require ______ assignment(s).

a. n

b. n - 1

c. n + 1

d. 1

c.

5. Assuming a linked list of n nodes, the C++ statements

Node *cur = head;

while (cur != null)

{ cout << curr->item << endl;

cur = cur->next;

} // end while

require ______ comparison(s).

a. n

b. n - 1

c. n + 1

d. 1

c.

6. Assuming a linked list of n nodes, the C++ statements

Node *cur = head;

while (cur != null) {

cout << curr->item << endl;

cur = cur->next;

} // end while

perform ______ write operations.

a. n

b. n - 1

c. n + 1

d. 1

a.

7. The solution to the Towers of Hanoi problem with n disks requires 2 n - 1 moves. If each move requires the

same time m, the solution requires ______ time units.

a. 2 n - 1

b. (2 n - 1) + m

c. (2 n - 1) / m

d. (2 n - 1) * m

d.

8. Consider an algorithm that contains loops of this form:

for (i = 1 through n)

{ for (j = 1 through i)

{ for (k = 1 through 10)

{ Task T

}

}

}

If task T requires t time units, the innermost loop on k requires ______ time units.

a. j

b. 10

c. k * t

d. 10 * t

d.

9. Consider an algorithm that contains loops of this form:

for (i = 1 through n )

{ for (j = 1 through i)

{ for (k = 1 through 10)

{ Task T

}

}

}

If task T requires t time units, the loop on j requires ______ time units.

a. 10 * t

b. (10 * t) + i

c. 10 t i

d. t * i

c.

10. Which of the following can be used to compare two algorithms?

a. growth rates of the two algorithms

b. implementations of the two algorithms

c. test data used to test programs which implement the two algorithms

d. computers on which programs which implement the two algorithms are run

a.

11. Algorithm efficiency is typically a concern for ______.

a. small problems only

b. large problems only

c. medium sized problems only

d. problems of all sizes

Chapter 10 Questions

© 2017 Pearson Education, Inc., Hoboken, NJ. All rights reserved.

b.

12. If a problem of size n requires time that is directly proportional to n, the problem is ______.

a. O(1)

b. O(n)

c. O(n 2 )

d. O(log 2 n)

b.

13. Which of the following growth-rate functions grows the fastest in value?

a. 1

b. n

c. n 2

d. log 2 n

c.

14. Which of the following growth-rate functions grows the slowest in value?

a. 1

b. n

c. n 2

d. log 2 n

a.

15. Which of the following growth-rate functions indicates a problem whose time requirement is constant?

a. 1

b. n

c. 2 n

d. log 2 n

a.

16. Which of the following growth-rate functions indicates a problem whose time requirement is independent of the

size of the problem?

a. 1

b. n

c. 2 n

d. log 2 n

a.

17. A linear algorithm has the growth-rate function ______.

a. 1

b. n

c. 2 n

d. log 2 n

b.

18. A quadratic algorithm is ______.

a. O(n 2 )

b. O(n 3 )

c. O(2 n )

d. O(log 2 n)

a.

19. An exponential algorithm is ______.

a. O(n 2 )

b. O(n 3 )

c. O(2 n )

d. O(log 2 n)

c.

1. In the worst case, a binary search is ______.

a. O(n)

b. O(1)

c. O(log 2 n)

d. O(n 2 )

c.

2. The selection sort continues until ______ of the n items in an array have been swapped.

a. n/2

b. n - 2

c. n - 1

d. n

c.

3. Given the following array:

4 15 8 3 28 21

which of the following represents the array after the second swap of the selection sort?

a. 4 3 8 15 21 28

b. 4 15 8 3 21 28

c. 3 4 8 15 21 28

d. 21 4 3 8 15 28

b.

4. Given the fact that a selection sort of n items requires n 2 /2 + 5 * n/2 - 3 major operations, the selection sort is

______.

a. O(1)

b. O(n)

c. O(n 2 )

d. O(log 2 n)

c.

5. The ______ compares adjacent items and exchanges them if they are out of order.

a. selection sort

b. binary search

c. bubble sort

d. quicksort

c.

6. A bubble sort requires at most ______ passes to sort an array of n items.

a. n/2

b. n - 2

c. n - 1

d. n

c.

7. In the worst case, the insertion sort's comparison occurs ______ times.

a. n

b. n - 1

c. (n - 1) / 2

d. n * (n - 1)/2

d.

8. Each merge step of the mergesort requires ______ major operations.

a. 3 * n - 1

b. 4 * n - 1

c. (n - 1)/2

d. n - 1

a.

9. The quicksort is ______ in the worst case.

a. O(n 2 )

b. O(n 3 )

c. O(n * log 2 n)

d. O(log 2 n)

a.

10. Select the sorting algorithm(s) that is O(n 2 )

a) insertion sort

b) selection sort

c) bubble sort

d) all three

D

11. The worst scenario for insertion sort is

a) 9 8 7 6 5 4 3 2 1

b) 1 9 2 8 3 7 4 6 5

c) 8 2 6 4 5 3 7 1 9

d) 5 6 3 8 9 2 1 7 4

A

12. The ___ compares adjacent items and exchanges them if they are out of order.

a) selection sort

b) binary search

c) bubble sort

d) quicksort

C

13. A merge sort operation runs in:

a) O(log n) time.

b) O(n) time.

c) O(n log n) time.

d) O(n 2 ) time.

C

1. Which of the following operations was NOT included in the ADT sorted list operations?

a. print the sorted list

b. insert an entry into a sorted list

c. remove the entry at a given position from a sorted list

d. remove a given entry from a sorted list

A

2. Which of the following operations from the ADT sorted list behave as they do in the ADT list?

a. getPosition(anEntry)

b. getLength()

c. removeSorted(anEntry)

d. insertSorted(newEntry)

B

3. Given the following sequence of names added to an ADT sorted list:

nameListPtr->insertSorted("Tammie");

nameListPtr->insertSorted("Brenda");

nameListPtr->insertSorted("Sarah");

nameListPtr->insertSorted("Tom");

nameListPtr->insertSorted("Carlos");

What would be returned by the call

nameListPtr-> getPosition("Tammie")

a. 1

b. 3

c. 4

d. 5

C

4. In the class LinkedSortedList, which of the following items are private?

a. the constructor

b. isEmpty()

c. getEntry(position)

d. getNodeAt(position)

D

5. Given a sorted list with entries in ascending order, where do you insert a new entry?

a. just before the first entry that is not smaller than the new entry

b. just after the first entry that is not smaller than the new entry

c. just before the first entry that is not larger than the new entry

d. at the end of the list

A

6. Given the following figure to the right:

According to the text, what is the relationship between List A and List B?

a. List A is composed of an instance of List B

b. List B is composed of an instance of List A

c. List A is concatenated to list B

d. List B is a subset of list A

B

7. When an ADT sorted list is implemented using an instance of the ADT list which is link based, what is the worst case efficiency?

a. O(1)

b. O(n)

c. O(n2)

d. O(n * log2 n)

C

8. When an ADT sorted list is implemented using an instance of the ADT list which is link based, which of the following operations has worst case efficiency?

a. insertSorted (newEntry)

b. getEntry (position)

c. clear()

d. isEmpty()

D

9. Given the following figure to the right:

According to the text, what is the relationship between List A and List B?

a. List B is a descendant of List B

b. List A is a descendant of List A

c. List A comes after list B

d. List B is a clone of list A

A

10. In the class LinkedSortedList, the method copyChain(ptr)is classified as which of the following?

a. public

b. private

c. shared

d. virtual

B

11. In the array based implementation of the ADT List operation replace, what is the efficiency?

a. O(n)

b. O(n2)

c. O(1)

d. O(log n)

C

12. Which operation creates a new list and then copies the entries in the given sorted list to the new list.

a. newList

b. destructor

c. constructor

d. copy constructor

D

1. A priority queue orders its items by ______.

a. position

b. value

c. priority value

d. size

c

2. The first item to be removed from a priority queue is the item ______.

a. at the front of the priority queue

b. at the end the priority queue

c. with the highest value

d. with the highest priority value

d

3. Which data structure represents a waiting line and limits insertions to be made at the back of the data structure and limits removals to be made from the front?

a. Stack.

b. tree.

c. Linked list

d. Queue.

D

4. Which of the following characterizes a stack?

a. FIFO

b. LIFO

c. FILO

d. LILO

B

5. Which of the following characterizes a queue?

a. FIFO

b. LIFO

c. FILO

d. LILO

A

6. Which of the following is not an ADT Queue operation as presented by the author?

a. test if queue is empty

b. add new entry to back of queue

c. add new entry to front of queue

d. get entry that was added earliest to the queue

C

7. Which of the following ADT Queue operators does not have return type specified as bool?

a. isEmpty

b. dequeue

c. peekFront

d. enqueue

C

8. Which of the following ADT Queue operators has a parameter?

a. isEmpty

b. dequeue

c. peekFront

d. enqueue

D

9. Given the following queue operations on an empty existing queue called nameQueue.

nameQueue.enqueue(Sid)

nameQueue.enqueue(Sal)

nameQueue.enqueue(Sue)

nameQueue.enqueue(Sam)

nameQueue.dequeue()

display (nameQueue.peekFront())

What name is displayed?

a. Sid

b. Sal

c. Sue

d. Sam

B

10. Given the following queue operations on an empty existing queue called nameQueue.

nameQueue.enqueue(Bob)

nameQueue.enqueue(Bill)

nameQueue.enqueue(Bud)

nameQueue.dequeue()

nameQueue.enqueue(Boo)

What is now the contents of the queue (with front of the queue listed leftmost)?

a. Bob, Bill, Bud

b. Bob, Bud, Boo

c. Bill, Bud, Boo

d. Boo, Bud, Bill

C

11. Given two initially empty queues, queue1 and queue2 and the following commands.

queue1.enqueue(1)

queue1.enqueue(2)

queue2.enqueue(3)

queue2.enqueue(4)

queue1.dequeue()

queueFront = queue2.peekFront()

queue1.enqueue(queueFront)

queue1.enqueue(5)

queue2.dequeue()

queue2.enqueue(6)

What are now the contents of What is now the contents of queue1 (with front of the queue listed leftmost)?

a. 2, 3, 5

b. 5, 3, 2

c. 4, 6

d. 6, 4

A