Questions
These questions are intended as a self-test for readers.Answers to the questions may be found in Appendix C.
1.In many data structures you can________a single record,_________it,and
_______it.
2.Rearranging the contents of a data structure into a certain order is called
_________.
30CHAPTER1Overviewsorting out
3.In a database,a field is
a.a specific data item.
b.a specific object.
c.part of a recor
d.
d.part of an algorithm.
4.The field used when searching for a particular record is the______________.
5.In object-oriented programming,an object
a.is a class.
b.may contain data and methods.
c.is a program.
d.may contain classes.
6.A class
a.is a blueprint for many objects.
c.will hold specific values in its fields.
d.specifies the type of a method.
7.In Java,a class specification
< of the abov
e.
8.When an object wants to do something,it uses a________.
9.In Java,accessing an object’s methods requires the_____operator.
10.In Java,boolean and byte are_____________.
(There are no experiments or programming projects for Chapter1.)
Questions31
Chapter1,Overview
Answers to Questions
1.insert,search for,delete
2.sorting
3.c
4.search key
5.b
6.a
7.d
9.dot
10.data types
Questions
These questions are intended as a self-test for readers.Answers may be found in Appendix C.
1.Inserting an item into an unordered array
a.takes time proportional to the size of the array.
d.takes the same time no matter how many items there ar
e.
2.True or False:When you delete an item from an unordered array,in most cases you shift other items to fill in the gap.
3.In an unordered array,allowing duplicates
a.increases times for all operations.
b.increases search times in some situations.
c.always increases insertion times.
d.sometimes decreases insertion times.
4.True or False:In an unordered array,it’s generally faster to find out an item is not in the array than to find out it is.
5.Creating an array in Java requires using the keyword________.
6.If class A is going to use class B for something,then
a.class A’s methods should be easy to understand.
b.it’s preferable if class B communicates with the program’s user.
c.the more complex operations should be placed in class A.
d.the more work that class B can do,the better.
7.When class A is using class B for something,the methods and fields class A can access in class B are called class B’s__________.
74CHAPTER2Arrays
8.Ordered arrays,compared with unordered arrays,are
a.much quicker at deletion.
b.quicker at insertion.
c.quicker to create.
d.quicker at searching.
9.A logarithm is the inverse of_____________.
10.The base10logarithm of1,000is_____.
11.The maximum number of elements that must be examined to complete a binary search in an array of200elements is
a.200.
b.8.
c.1.
d.13.
12.The base2logarithm of64is______.
13.True or False:The base2logarithm of100is2.
14.Big O notation tells
a.how the speed of an algorithm relates to the number of items.
b.the running time of an algorithm for a given size data structure.
c.the running time of an algorithm for a given number of items.
d.how the size of a data structure relates to the number of items.
15.O(1)means a process operates in_________time.
16.Either variables of primitive types or_________can be placed in an array. Chapter2,Arrays
Answers to Questions
1.d
2.True
3.b
4.False
6.d
740APPENDIX C Answers to Questions
7.interface
8.d
9.raising to a power
10.3
11.8
12.6
13.False
14.a
16.objects
uestions
These questions are intended as a self-test for readers.Answers may be found in Appendix C.
1.Computer sorting algorithms are more limited than humans in that
a.humans are better at inventing new algorithms.
bputers can handle only a fixed amount of data.
c.humans know what to sort,whereas computers need to be tol
d.
dputers can compare only two things at a tim
e.
2.The two basic operations in simple sorting are_________items and_________ them(or sometimes_________them).
3.True or False:The bubble sort always ends up comparing every item with every other item.
4.The bubble sort algorithm alternates between
aparing and swapping.
5.True or False:If there are N items,the bubble sort makes exactly N*N comparisons.
Questions109
6.In the selection sort,
a.the largest keys accumulate on the left(low indices).
b.a minimum key is repeatedly discovered.
c.a number of items must be shifted to insert each item in its correctly
sorted position.
d.the sorted items accumulate on the right.
7.True or False:If,in a particular sorting situation,swaps take much longer than comparisons,the selection sort is about twice as fast as the bubble sort.
8.A copy is________times as fast as a swap.
9.What is the invariant in the selection sort?
10.In the insertion sort,the“marked player”described in the text corresponds to which variable in the insertSort.java program?
a.in
b.out
d.a[out]
11.In the insertion sort,“partially sorted”means that
a.some items are already sorted,but they may need to be moved.
d.
may need to be inserted in it.
12.Shifting a group of items left or right requires repeated__________.
13.In the insertion sort,after an item is inserted in the partially sorted group,it will
c.often be moved out of this group.
d.find that its group is steadily shrinking.
110CHAPTER3Simple Sorting
14.The invariant in the insertion sort is that________.
15.Stability might refer to
a.items with secondary keys being excluded from a sort.
b.keeping cities sorted by increasing population within each state,in a sort
by state.
c.keeping the same first names matched with the same last names.
d.items keeping the same order of primary keys without regard to secondary keys.
Chapter3,Simple Sorting
Answers to Questions
1.d
2paring and swapping(or copying)
3.False
4.a
5.False
6.b
7.False
8.three
9.Items with indices less than or equal to outer are sorted.
10.c
11.d
13.b
14.Items with indices less than outer are partially sorted.
15.b
uestions
These questions are intended as a self-test for readers.Answers may be found in Appendix C.
1.Suppose you push10,20,30,and40onto the stack.Then you pop three items. Which one is left on the stack?
2.Which of the following is true?
a.The pop operation on a stack is considerably simpler than the remove operation on a queue.
b.The contents of a queue can wrap around,while those of a stack cannot.
c.The top of a stack corresponds to the front of a queue.
d.In both the stack and the queue,items removed in sequence are taken
from increasingly high index cells in the array.
3.What do LIFO and FIFO mean?
4.True or False:A stack or a queue often serves as the underlying mechanism on which an ADT array is based.
5.Assume an array is numbered with index0on the left.A queue representing a line of movie-goers,with the first to arrive numbered1,has the ticket window on the right.Then
a.there is no numerical correspondence between the index numbers and
the movie-goer numbers.
b.the array index numbers and the movie-goer numbers increase in
opposite left-right directions.
c.the array index numbers correspond numerically to the locations in the
line of movie-goers.
d.the movie-goers and the items in the array move in the same direction.
6.As other items are inserted and removed,does a particular item in a queue move along the array from lower to higher indices,or higher to lower?
7.Suppose you insert15,25,35,and45into a queue.Then you remove three items.Which one is left?
8.True or False:Pushing and popping items on a stack and inserting and removing items in a queue all take O(N)time.

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。