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 Exam 1. 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 discussion sections.

• 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 to arrays?

• 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 breadth-first search?

• 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?