Transcript CS2006review

COSC2006 - Data Structures
I
Review & Final Exam
Topics


2
Review
Final Exam
Review

Software Engineering



Problem Solving
Software Life Cycle
Modular Design
OO Design
 Top Down Design


3
Structure Chart
Review

Recursion



Recursion and Iteration
Recursion Examples
How to trace recursion


4
Run-time Stack
Recursion Problem
Review

ADT



5
Concepts
How to define a ADT?
Array-based ADT List
Review

Linked List




Comparison with Array
Object & Reference
Referenced-based LL
LL operations:





LL-based ADT List
Variation of LL

6
Insertion
Deletion
Traverse
Doubly LL
Review

Stack


Characteristics of ADT Stack
Stack Applications



Stack operations
Stack implementation




Array-based
LL-based
ADT List-based
More Detail Examples


7
Bracket balancing
Evaluating postfix, prefix
Convert from infix to postfix
Review

Queue


Characteristics of ADT Queue
Queue Applications




Queue operations
Queue implementation




8
Convert digit to decimal
Palindrome
Array-based
LL-based
ADT List-based
Queue Applications
Review

Efficiency


Big-O
Searching



Linear search
Binary Search
Sorting

Three O(n2)



9
Bubble sort
Insertion sort
Selection sort
Review

Efficiency

Sorting
Merge Sort
 Quick Sort
 Radix Sort

10
Review
Which of the following is a base case for a
recursive binary search algorithm?
(first is the index of the first item in the array, last is
the index of the last item in the array, and mid is
the midpoint of the array).





11
last > first
first > last
0 <= first
last <= SIZE-1
Review

A recursive binary search algorithm
always reduces the problem size by
______ at each recursive call.




12
1
2
half
one-third
Review

An array is a(n) ______.




13
class
method
object
variable
Review

An ADT’s ______ govern(s) what its
operations are and what they do.




14
specifications
implementation
documentation
data structure
Review

The insertion operation of the ADT list can
insert new items ______.




15
only at the front of the list
only at the end of the list
only in the middle of the list
into any position of the list
Review

Which of the following is true about a
constructor in Java?




16
all constructors have a return type of void
a constructor cannot have parameters
a constructor has the same name as the class
a class can only have a single constructor
Review

The ______ keyword is used to call the
constructor of the superclass.




17
extends
super
this
implements
Review

When you declare a variable that refers to
an object of a given class, you are
creating a(n) ______ to the object.




18
interface
reference
Method
ADT
Review

A reference variable whose sole purpose
is to locate the first node in a linked list is
called ______.




19
top
front
head
first
Review

Which of the following statements deletes
the node that curr references?




20
prev.setNext(curr);
curr.setNext(prev);
curr.setNext(curr.getNext());
prev.setNext(curr.getNext());
Review

An array-based implementation of an ADT
list ______.




21
requires less memory to store an item than a
reference-based implementation
is not a good choice for a small list
has a variable size
has items which explicitly reference the next
items
Review

If the array: 6, 2, 7, 13, 5, 4 is added to a
stack, in the order given, which number
will be the first number to be removed
from the stack?




22
6
2
5
4
Review

Which of the following methods of the ADT
stack accepts a parameter?




23
push
pop
createStack
peek
Review

Typically, ______ are used by a compiler
to implement recursive methods.




24
linked-lists
arrays
Stacks
queues
Review

A reference-based implementation of a
queue that uses a linear linked list would
need at least ______ external references.




25
one
two
three
four
Review

Which of the following methods of
QueueInterface does NOT throw a
QueueException?




26
enqueue
dequeue
dequeueAll
peek
Review

The Java ______ operator is used to
obtain the wraparound effect of a circular
array-based queue.




27
*
+
%
/
Review

If a queue is implemented as the ADT list,
which of the following queue operations
can be implemented as list.remove(1)?




28
enqueue()
dequeue()
isEmpty()
peek()
Final Exam

Topics


No specific questions from chapter 1 & 2
All other parts you have learned in class




29
Chapter 3, 4, 5, 7, 8, 10
Class Notes
Tutorials (the solutions are on-line)
Assignments
Final Exam



Time: Wednesday, Dec 16, 2:00 pm
Place: EW206
Format



30
20 multiple choices (30%)
Short Answer Questions (~40%)
Programming Questions (~30%)