CS3 Test 1 Study Guide

Term 20053

Here are the concepts you should be studying for the first exam.

• Linked Data Structures
  • Linked List
  • Linked implementation of Stack and Queue
• Time Complexity of algorithms
• Search algorithms
  • Linear
  • Binary
• Recursive algorithms
  

Study Questions

1.Why does a linked stack need only one "pointer" into its linked list, while a linked queue needs two?

2. In a linked queue that uses a singly-linked list, which choice makes the algorithms simpler:

• insert in front, remove from rear, or
• insert in rear, remove from front?

3. Declare a link node class that is suitable for a doubly-linked list.

4. If a search algorithm runs in less than linear time, what does that mean about the data structure that stores the values?

5. In search algorithms, what operation do we consider to be the "dominant" one, i.e., the one that gets counted? Can you think of situations where another choice should be made?

6. What is the time complexity of an algorithm that

• only checks array elements at even indices?
• only checks array elements at indices that are powers of two?

7. What kind of data structure does this code build?