Quiz
Data Structures 1 - Review 1
Create a free account to finish this quiz
Save your progress and see your final score.
Already have an account? Sign in
Questions in this quiz (32)
1How is a non-circular, doubly-linked list different from a circular, doubly-linked list (which is true for a non-circular list)?
- AThe "next" points to the "prev" and "prev" points to "next" for the head and tail nodes
- BThe "next" of tail node is null, and the "previous" of the head node is null
- CThe "next" of tail node points to the tail node and the "previous" of the head node points to the head node
- DThe "next" of tail node points to the head node and the "previous" of the head node points to the tail node
2What term is used to describe a O(n^2) algorithm?
- AConstant
- BExponential
- CQuadratic
- DLinear
- ELogarithmic
3Which of the following would be the Big-O function for the funtion (5x^2 + 4x^4 + 3)?
- AO( 3 )
- BO( 5x^2 )
- CO( 4x )
- DO( x^4 )
4For which of the following structures can a binary search be used?
- Aunsorted, array-based lists
- Bsorted, array-based lists
- Cunsorted, linked lists
- Dsorted, linked lists
- Eall of the others are possible
5How is a circular, doubly-linked list different from a non-circular, doubly-linked list (which is true for a circular list)?
- A"next" points to the "prev" and "prev" points to "next" for the head and tail nodes
- BThe "next" of tail node points to the head node and the "previous" of the head node points to the tail node
- CThe "next" of tail node is null, and the "previous" of the head node is null
- DThe "next" of tail node points to the tail node and the "previous" of the head node points to the head node
6Which of the following describe a difference between a queue and a stack is:
- AStacks modify both ends of the structure, queues modify only one.
- BQueues require linked lists, but stacks do not.
- CQueues modify both ends of the structure; stacks modify only one.
- DStacks require linked lists, but queues do not.
7Consider the following code segment where "n" was passed in as a parameter.
for (int i = n; i >= 1; i = i / 2) {
System.out.println(i);
}
Of the following, which best characterizes the running time of this code segment?- AO(log n)
- BO(n log n)
- CO(n^2)
- DO(n)
8When comparing the equations shown below, some equations will give you relatively larger values for smaller input values. However, as values of n become large enough, which of the following will give you the smallest value?
- A0.005 * n^2
- B4 * n^3
- C20000 * log2(n)
- D50 * n + n^(2/3)
9Given an unsorted list of items, the selection sort algorithm complexity for the number of assignments (memory moves) is:
- An(n-1)
- BO(n^2 + n)
- CO(log n)
- DO(n^2)
- EO(n)
10Which of the following is NOT an example of empirical analysis?
- AWeighing two equal volume containers of rocks of where each container has a different type rock in it
- BMeasuring the clock time used by a specific code segment in a program for a specific input set
- CShowing that C^2 = A^2 + B^2 for all right triangles where A, B, and C are the lengths of the sides, and C is the length of the hypotenuse.
- DComparing hourly air pressure readings to hourly rainfall measurements during one day
11Consider the following code segment where "n" was passed in as a parameter.
for (int i = 1; i <= n; i++) {
for (int j = n; j >= 1; j = j - 1) {
System.out.println(i + " " + j);
} }
Of the following, which best characterizes the running time of this code segment?- AO(n)
- BO(log n)
- CO(n^2)
- DO(n log n)
12What term is used to describe a O(log N) algorithm?
- ALogarithmic
- BLinear
- CQuadratic
- DConstant
- EExponential
13If a SORTED, array based list has 1024 items, a binary search would take approximately how many comparisons to do a search?
- A1024*1024 (n^2 comparisons)
- B10 (log N comparisons)
- C1024 (N comparisons)
- D256 (N/4 comparisons)
- E512 (N/2 comparisons)
14The function ____ implies that the growth rate is exponential.
- Ag(n) = 1
- Bg(n) = n^2
- Cg(n) = 2^n
- Dg(n) = 2
15In a [circular array] implementation of a Queue class, which operation would require linear time for the worst-case behavior?
- Aremove when the queue is full
- Binsert when the capacity has not yet been reached
- CisEmpty
- DNone of these operations require linear time.
16Consider the following code segment where "n" was passed in as a parameter.
for (int i = 1; i <= n; i++) {
for (int j = n; j >= 1; j = j / 2) {
System.out.println(i + " " + j);
} }
Of the following, which best characterizes the running time of this code segment?- AO(n)
- BO(n log n)
- CO(n^2)
- DO(log n)
17What does Big-O time complexity measure?
- AThe programs relative memory usage complexity
- BRelative complexity of algorithms
- CThe clock speed of a particular program
- DThe amount of estimated time before you need to have your tires replaced.
18Adding an item to an unsorted array that does not allow duplicate items in the array requires approximately how many comparisons of elements?
- AO(n) comparisons between elements
- BO(n^2) comparisons between elements
- CO(n log n) comparisons between elements
- DO(log n) comparisons between elements
19If a SORTED, pointer based list size is 1024, on average, a sequential search would take how many comparisons for elements that are found in the list?
- A10 (log N comparisons)
- B256 (N/4 comparisons)
- C512 (N/2 comparisons)
- D2024 (2N comparisons)
- E1024*1024 (n^2 comparisons)
20Given an array implementation of a Queue. Which of the following is true if we keep all the items at the front of a partially-filled array (so that data[0] is always the front/head).
- AThe remove/dequeue method would require linear time.
- BNone of these would require linear time.
- CThe add/enqueue method would require linear time.
- DThe empty method would require linear time.
21What term is used to describe a O(n) algorithm?
- AConstant
- BQuadratic
- CLinear
- DExponential
- ELogarithmic
22Suppose a variable named "cursor" is a pointer to a node in a singly linked, non-circular list (using a Node class with fields called "data" and "next"). What boolean expression will always be true when cursor refers to the tail node of the list?
- A(cursor.next == head)
- B(cursor.data == 42)
- C(cursor.next == null)
- D(cursor == null)
23We are writing a program to simulate traffic flow at a 4-way stop. Which is the best data structure choice for simulating the cars waiting at each stop sign?
- ADoubly-Linked List
- BStack
- CQueue
- DSingly-Linked List
- ECircular, doubly-linked list
24Suppose variable named "cursor" refers to a node in a singly-linked, non-circular list (using a Node class with instance variables called "data" and "next"). What statement changes cursor so that it refers to the next node?
- Acursor = next;
- Bcursor = cursor.next;
- Ccursor.next = cursor;
- Dcursor++;
- Ecursor += next;
25Which of the following formulas in big-O notation best represent the expression: n^3+35n+6
- AO(n^2)
- BO(42)
- CO(35n)
- DO(n)
- EO(n^3)
26If a Queue is set up as a circular array of CAPACITY (a constant) size, and rear is an index into that array, what is the formula for the next index after rear (the slot where the next item will be added)?
- Arear % (1 + CAPACITY)
- Brear + (1 % CAPACITY)
- C(rear % 1) + CAPACITY
- D(rear + 1) % CAPACITY
27You are writing a pointer-based, doubly linked, non-circular list using a Node class with fields called "prev", "data" and "next". Which code fragment would remove the first node in the list?
- Ahead.prev.next = null;
head.next = head; - Bhead.next = null;
head = head.next; - Chead.next.prev = null;
head = head.next; - Dhead = head.next;
head.next.prev = null;
- Ahead.prev.next = null;
28The function _____ implies that the growth rate is constant and thus does not depend on n, the size of the problem.
- Ag(n) = 2^n
- Bg(n) = logn
- Cg(n) = 1
- Dg(n) = n
29Consider the following code segment where "n" was passed in as a parameter.
for (int i = n; i >= 1; i--) {
System.out.println(i);
}
Of the following, which best characterizes the running time of this code segment?- AO(n log n)
- BO(n^2)
- CO(log n)
- DO(n)
30You are writing a pointer-based, doubly linked, non-circular list using a Node class with fields called "prev", "data" and "next". Which code fragment would remove the last node in the list?
- Atail = tail.prev;
tail.prev.next = null; - Btail.prev = null;
tail = tail.next; - Ctail.next.prev = null;
tail.prev = tail; - Dtail.prev.next = null;
tail = tail.prev;
- Atail = tail.prev;
31What kind of list has the best performance when answering questions such as "What is the item at position n?"
- ADoubly-linked lists.
- BLists implemented with an array.
- CSingly-linked lists.
- DDoubly-linked or singly-linked lists are equally the best.
32Items in a queue are added to the _______, and removed from the __________. (answers are in the order of the blanks).
- Atail for both
- Bhead, tail
- Chead for both
- Dtail, head
Information
- Description
- Quiz on Data Structures 1 - Review 1, created by jshin13 on 09/03/2015.
- Author
- jshin13
- Language
- English
- Views
- 28
- Rating
- No ratings yet Rate this quiz