Problem 25
Suppose the entries in a queue require one memory cell each, the head pointer contains the value 11 , and the tail pointer contains the value 17 . What are the values of these pointers after one entry is inserted and two are removed?
Problem 26
The Towers of Hanoi is a classic puzzle that consists of 3 towers, and \(n\) disks of different sizes that can slide onto any tower. The puzzle starts with the disks sorted in ascending order of size from top to bottom. It has the following constraints: a. Only one disk can be moved at a time. b. A disk can only be moved from the top of one tower to another tower. c. A disk can only be placed on top of a larger disk. Write a program to move the disks from the first tower to the last using stacks.
Problem 27
Design a recursive function that counts all the possible ways in which a person can run up the stairs, if he can jump 1,2, or 3 steps at a time.
Problem 28
Suppose you were given two queues and you were only allowed to move one entry at a time from the head of a queue to the tail of either. Design an algorithm for reversing two adjacent entries in one of the queues.
Problem 34
Design a function to check if a binary tree is balanced. A balanced tree is defined to be a tree such that the heights of the two subtrees of any node never differ by more than one.
Problem 36
Suppose each node in a binary tree contains a value. Design a function that prints all the paths that sum to a specified value passed into the function. The path can start at an arbitrary node.
Problem 37
Give an example in which you might want to implement a list (the conceptual structure) as a tree (the actual underlying structure). Give an example in which you might want to implement a tree (the conceptual structure) as a list (the actual underlying structure).
Problem 39
Describe a data structure suitable for representing a board configuration during a chess game.
Problem 42
Suppose a call center has three levels of employees-respondent, manager, and director. An incoming telephone call must first be allocated to a respondent who is free. If the respondent cannot handle the call, the call must be escalated to a manager. If the manager is occupied, then the call should be escalated to a director. Design the classes and data structures for this problem. Implement a method dispatchCa11 () that assigns a call to the first available employee.
Problem 44
In the traditional implementation of a tree, each node is constructed with a separate pointer for each possible child. The number of such pointers is a design decision and represents the maximum number of children any node can have. If a node has fewer children than pointers, some of its pointers are simply set to null. But such a node can never have more children than pointers. Describe how a tree could be implemented without limiting the number of children a node could have.
