22C:30, 22C:115 Review Questions for Exam 2
Exam 2 is scheduled for Friday, November 1, from 10:30 to 11:20 in
Room 321, CB
Note that this is an open notes/book exam.
Given below are questions that you should attempt to answer in studying for
The problems on the exam will involve (i) answering questions about small code
fragments that are given or (ii) writing small code fragments to perform a
specific task. You will not be asked to write large functions or entire classes.
You should read Chapters 5, 7, 8 (with the exception of Section 8.4), and
9 for the exam.
In addition, you should know the material on breadth-first search and
depth-first search of graphs covered in class.
If you need additional material to read on these topics, you can read
Sections 15.1, 15.2, and 15.3, though this is not required.
You should also look over the solution to Project 1 that I have posted
and should bring a printout of the latest version to the exam.
Focus of material that relates to what was discussed in class and in the
- How do we insert a node into a linked list? How do we insert at the
beginning? or at the end? or immediately after a given node?
- How do we delete a node from a linked list? How do we delete the
first node? the last node? or a node immediately after a given node?
- What advantages and disadvantages do linked lists have when compared
- What are some close relatives of singly-linked lists? When would
one use one of these relatives, as opposed to singly-linked lists?
- What are queues? How are queues implemented using arrays?
How are they implemented using linked lists?
- What is breadth-first search of a graph? What properties does
such a search have and how is a queue data structure usefuel in doing
- What are stacks? How are stacks implemented using arrays? How are
they implemented using linked lists?
- What are some important uses of stacks? How is a stack used in doing
depth-first search of a graph?
- What are some differences between a depth-first search and breadth-first
search of a graph?
- How is depth-first search implemented using recursion? Is this more
efficient than implementing depth-first search using stacks?
- What is the connection between recursion and stacks? How is recursion
useful in search with back-tracking, in general and in specific examples
such as the Knight's Tour problem?