第1页 / 共676页
第2页 / 共676页
第3页 / 共676页
第4页 / 共676页
第5页 / 共676页
第6页 / 共676页
第7页 / 共676页
第8页 / 共676页
数据结构与课程设计答案 影印版 RObert L. Kruse.pdf
1.2 The Game of Life
1.3 Programming Style
1.4 Coding, Testing, and Further Refinement
1.5 Program Maintenance
1.6 Conclusions and Preview
Review Questions
2.1 Stack Specifications
2.2 Implementation of Stacks
2.3 Application: A Desk Calculator
2.4 Application: Bracket Matching
2.5 Abstract Data Types and Their Implementations
Review Questions
3.1 Definitions
3.3 Circular Implementation of Queues in C++
3.4 Demonstration and Testing
3.5 Application of Queues: Simulation
Review Questions
4.1 Pointers and Linked Structures
4.2 Linked Stacks
4.3 Linked Stacks with Safeguards
4.4 Linked Queues
4.5 Application: Polynomial Arithmetic
4.6 Abstract Data Types and Their Implementations
Review Questions
5.1 Introduction to Recursion
5.2 Principles of Recursion
5.3 Backtracking: Postponing the Work
5.4 Tree-Structured Programs: Look-Ahead in Games
Review Questions
6.1 List Definition
6.2 Implementation of Lists
6.3 Strings
6.4 Application: A Text Editor
6.5 Linked Lists in Arrays
6.6 Application: par penalty -500 Generating Permutations
Review Questions
7.2 Sequential Search
7.3 Binary Search
7.4 Comparison Trees
7.5 Lower Bounds
7.6 Asymptotics
Review Questions
8.2 Insertion Sort
8.3 Selection Sort
8.4 Shell Sort
8.5 Lower Bounds
8.6 Divide-and-Conquer Sorting
8.7 Mergesort for Linked Lists
8.8 Quicksort for Contiguous Lists
8.9 Heaps and Heapsort
8.10 Review: Comparison of Methods
Review Questions
9.2 Rectangular Tables
9.3 Tables of Various Shapes
9.5 Application: Radix Sort
9.6 Hashing
9.7 Analysis of Hashing
9.9 Application: The Life Game Revisited
Review Questions
10.1 Binary Trees
10.2 Binary Search Trees
10.3 Building a Binary Search Tree
10.4 Height Balance: AVL Trees
10.5 Splay Trees: A Self-Adjusting Data Structure
Review Questions
11.1 Orchards, Trees, and Binary Trees
11.2 Lexicographic Search Trees: Tries
11.3 External Searching: B-Trees
11.4 Red-Black Trees
Review Questions
12.7 Graphs as Data Structures
Review Questions
13.2 The Idea
13.3 Evaluation of Polish Expressions
13.4 Translation from Infix Form to Polish Form
13.5 An Interactive Expression Evaluator
B.3 Program Development
Programming
Principles
1
1.2 THE GAME OF LIFE
Exercises 1.2
Determine by hand calculation what will happen to each of the configurations shown in Figure 1.1 over
the course of five generations. [Suggestion: Set up the Life configuration on a checkerboard. Use one
color of checkers for living cells in the current generation and a second color to mark those that will be
born or die in the next generation.]
Answer
Figure remains stable.
(a)
(b)
(c)
Figure is stable.
(d)
1
课后答案网 www.khdaw.com
2
Chapter 1 Programming Principles
(e)
(f)
(g)
(h)
(i)
(j)
(k)
(l)
Figure repeats itself.
Figure repeats itself.
Figure repeats itself.
课后答案网 www.khdaw.com
1.3 PROGRAMMING STYLE
Exercises 1.3
Section 1.3 Programming Style
3
E1. What classes would you define in implementing the following projects? What methods would your classes
possess?
(a) A program to store telephone numbers.
Answer The program could use classes called Phone_book and Person. The methods for a Phone_book
object would include look_up_name, add_person, remove_person. The methods for a Person
object would include Look_up_number. Additional methods to initialize and print objects of
both classes would also be useful.
(b) A program to play Monopoly.
Answer The program could use classes called Game_board, Property, Bank, Player, and Dice. In addition
to initialization and printing methods for all classes, the following methods would be useful. The
class Game_board needs methods next_card and operate_jail. The class Property needs methods
change_owner, look_up_owner, rent, build, mortgage, and unmortgage. The class Bank needs
methods pay and collect. The class Player needs methods roll_dice, move_location, buy_property
and pay_rent. The class Dice needs a method roll.
(c) A program to play tic-tac-toe.
Answer The program could use classes called Game_board and Square. The classes need initializa-
tion and printing methods. The class Game_board would also need methods make_move and
is_game_over. The class Square would need methods is_occupied, occupied_by, and occupy.
(d) A program to model the build up of queues of cars waiting at a busy intersection with a traffic light.
Answer The program could use classes Car, Traffic_light, and Queue. The classes would all need initializa-
tion and printing methods. The class Traffic_light would need additional methods change_status
and status. The class Queue would need additional methods add_car and remove_car.
E2. Rewrite the following class definition, which is supposed to model a deck of playing cards, so that it
conforms to our principles of style.
/* X is the location of the top card in the deck. Y1 lists the cards. */ pub-
//
a deck of cards
//
//
Shuffle randomly arranges the cards.
deals the top card off the deck
Answer
class a {
int X; thing Y1[52];
lic: a( );
void Shuffle( );
thing d( );
}
;
class Card_deck {
Card deck[52];
int top_card;
public:
Card_deck( );
void Shuffle( );
Card deal( );
};
课后答案网 www.khdaw.com
4
Chapter 1 Programming Principles
E3. Given the declarations
int a[n][n], i, j;
where n is a constant, determine what the following statement does, and rewrite the statement to accom-
plish the same effect in a less tricky way.
for (i = 0; i < n; i)
for (j = 0; j < n; j)
a[i][j] = ((i 1)/(j 1)) * ((j 1)/(i 1));
Answer This statement initializes the array a with all 0’s except for 1’s down the main diagonal. A less
tricky way to accomplish this initialization is:
for (i = 0; i < n; i)
for (j = 0; j < n; j)
if (i == j) a[i][j] = 1;
else a[i][j] = 0;
E4. Rewrite the following function so that it accomplishes the same result in a less tricky way.
void does_something(int &first, int &second)
{
first = second − first;
second = second − first;
first = second first;
}
Answer The function interchanges the values of its parameters:
void swap(int &first, int &second)
/* Pre: The integers first and second have been initialized.
Post: The values of first and second have been switched. */
int temp = first;
first = second;
second = temp;
{
}
E5. Determine what each of the following functions does. Rewrite each function with meaningful variable
names, with better format, and without unnecessary variables and statements.
(a) int calculate(int apple, int orange)
{ int peach, lemon;
peach = 0; lemon = 0; if (apple < orange)
peach = orange; else if (orange <= apple)
peach = apple; else { peach = 17;
lemon = 19; }
return(peach);
}
Answer The function calculate returns the larger of its two parameters.
int larger(int a, int b)
/* Pre: The integers a and b have been initialized.
Post: The value of the larger of a and b is returned. */
if (a < b) return b;
return a;
{
}
课后答案网 www.khdaw.com
(b) For this part assume the declaration typedef float vector[max];
Section 1.3 Programming Style
5
float figure (vector vector1)
{ int loop1, loop4; float loop2, loop3;
loop1 = 0; loop2 = vector1[loop1]; loop3 = 0.0;
loop4 = loop1; for (loop4 = 0;
loop4 < max; loop4) { loop1 = loop1 1;
loop2 = vector1[loop1 − 1];
loop3 = loop2 loop3; } loop1 = loop1 − 1;
loop2 = loop1 1;
return(loop2 = loop3/loop2); }
Answer The function figure obtains the mean of an array of floating point numbers.
float mean(vector v)
/* Pre: The vector v contains max floating point values.
Post: The mean of the values in v is returned. */
float total = 0.0;
for (int i = 0; i < max; i)
total += v[i];
return total/((float) max);
{
}
(c)
int question(int &a17, int &stuff)
{ int another, yetanother, stillonemore;
another = yetanother; stillonemore = a17;
yetanother = stuff; another = stillonemore;
a17 = yetanother; stillonemore = yetanother;
stuff = another; another = yetanother;
yetanother = stuff; }
Answer The function question interchanges the values of its parameters.
void swap(int &first, int &second)
/* Pre: The integers first and second have been initialized.
Post: The values of first and second have been switched. */
int temp = first;
first = second;
second = temp;
{
}
(d)
int mystery(int apple, int orange, int peach)
{ if (apple > orange) if (apple > peach) if
(peach > orange) return(peach); else if (apple < orange)
return(apple); else return(orange); else return(apple); else
if (peach > apple) if (peach > orange) return(orange); else
return(peach); else return(apple); }
Answer The function mystery returns the middle value of its three parameters.
课后答案网 www.khdaw.com
6
Chapter 1 Programming Principles
int median(int a, int b, int c)
/* Pre: None.
Post: Returns the middle value of the three integers a, b, c. */
if (a > b)
if (c > a) return a;
else if (c > b) return c;
else return b;
else
if (c > b) return b;
else if (c > a) return c;
else return a;
//
//
//
//
//
//
c > a > b
a >= c > b
a > b >= c
c > b >= a
b >= c > a
b >= a >= c
{
}
E6. The following statement is designed to check the relative sizes of three integers, which you may assume
to be different from each other:
if (x < z) if (x < y) if (y < z) c = 1; else c = 2; else
if (y < z) c = 3; else c = 4; else if (x < y)
if (x < z) c = 5; else c = 6; else if (y < z) c = 7; else
if (z < x) if (z < y) c = 8; else c = 9; else c = 10;
(a) Rewrite this statement in a form that is easier to read.
Answer
if (x < z)
if (x < y)
if (y < z) c = 1;
else c = 2;
else
if (y < z) c = 3;
else c = 4;
else
if (x < y)
if (x < z) c = 5;
else c = 6;
else
if (y < z) c = 7;
//
z <= y <= x
if (z < x)
if (z < y) c = 8;
else c = 9;
else c = 10;
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
//
x < z and x < y
x < y < z
x < z <= y
y <= x < z
y <= x < z
impossible
z <= x
z <= x < y
impossible
z <= x < y
z <= x and y <= x
y < z <= x
z <= y <= x, z < x
z < y <= x
z == y < x, impossible
y <= z == x, impossible
(b) Since there are only six possible orderings for the three integers, only six of the ten cases can actually
occur. Find those that can never occur, and eliminate the redundant checks.
Answer The impossible cases are shown in the remarks for the preceding program segment. After their
removal we have:
if (x < z)
if (x < y)
if (y < z) c = 1;
else c = 2;
else c = 3;
else
if (x < y) c = 6;
else
if (y < z) c = 7;
else c = 8;
//
//
//
//
//
//
//
//
//
x < z and x < y
x < y < z
x < z <= y
y <= x < z
z <= x
z <= x < y
z <= x and y <= x
y < z <= x
z <= y <= x
课后答案网 www.khdaw.com
(c) Write a simpler, shorter statement that accomplishes the same result.
Section 1.3 Programming Style
7
Answer
if ((x < y) && (y < z)) c = 1;
else if ((x < z) && (z < y)) c = 2;
else if ((y < x) && (x < z)) c = 3;
else if ((z < x) && (x < y)) c = 6;
else if ((y < z) && (z < x)) c = 7;
else c = 8;
E7. The following C++ function calculates the cube root of a floating-point number (by the Newton approx-
imation), using the fact that, if y is one approximation to the cube root of x, then
cube roots
is a closer approximation.
z 2y x=y2
3
float function fcn(float stuff)
{ float april, tim, tiny, shadow, tom, tam, square; int flag;
tim = stuff; tam = stuff; tiny = 0.00001;
if (stuff != 0) do {shadow = tim tim; square = tim * tim;
tom = (shadow stuff/square); april = tom/3.0;
if (april*april * april − tam > −tiny) if (april*april*april − tam
< tiny) flag = 1; else flag = 0; else flag = 0;
if (flag == 0) tim = april; else tim = tam; } while (flag != 1);
if (stuff == 0) return(stuff); else return(april); }
(a) Rewrite this function with meaningful variable names, without the extra variables that contribute nothing
to the understanding, with a better layout, and without the redundant and useless statements.
Answer After some study it can be seen that both stuff and tam play the role of the quantity x in the
formula, tim plays the role of y , and tom and april both play the role of z. The object tiny is a
small constant which serves as a tolerance to stop the loop. The variable shadow is nothing but
2y and square is y2. The complicated two-line if statement checks whether the absolute value
jz3 − xj is less than the tolerance, and the boolean flag is used then only to terminate the loop.
Changing all these variables to their mathematical forms and eliminating the redundant ones
gives:
const double tolerance = 0.00001;
double cube_root(double x)
{
//
Find cube root of x by Newton method
double y, z;
y = z = x;
if (x != 0.0)
do {
z = (y y x/(y * y))/3.0;
y = z;
} while (z * z * z − x > tolerance || x − z * z * z > tolerance);
return z;
}
(b) Write a function for calculating the cube root of x directly from the mathematical formula, by starting
with the assignment y = x and then repeating
until abs(y * y * y − x) < 0.00001.
y = (2 * y (x/(y * y)))/3
课后答案网 www.khdaw.com
8
Chapter 1 Programming Principles
Answer
const double tolerance = 0.00001;
double formula(double x)
{
//
Find cube root of x directly from formula
double y = x;
if (x != 0.0)
y = (y y x/(y * y))/3.0;
do {
} while (y * y * y − x > tolerance || x − y * y * y > tolerance);
return y;
}
(c) Which of these tasks is easier?
Answer
It is often easier to write a program from scratch than it is to decipher and rewrite a poorly written
program.
statistics
E8. The mean of a sequence of numbers is their sum divided by the count of numbers in the sequence. The
(population) variance of the sequence is the mean of the squares of all numbers in the sequence, minus
the square of the mean of the numbers in the sequence. The standard deviation is the square root of the
variance. Write a well-structured C++ function to calculate the standard deviation of a sequence of n
floating-point numbers, where n is a constant and the numbers are in an array indexed from 0 to n − 1,
which is a parameter to the function. Use, then write, subsidiary functions to calculate the mean and
variance.
Answer
#include
double variance(double v[ ], int n);
double standard_deviation(double v[ ], int n) //
{
return sqrt(variance(v, n));
}
Standard deviation of v[ ]
This function uses a subsidiary function to calculate the variance.
double mean(double v[ ], int n);
double variance(double v[ ], int n)
Find the variance for n numbers in v[ ]
//
{
int i;
double temp;
double sum_squares = 0.;
for (i = 0; i < n; i)
sum_squares += v[i] * v[i];
temp = mean(v, n);
return sum_squares/n − temp * temp;
}
This function in turn requires another function to calculate the mean.
double mean(double v[ ], int n)
{
//
Find the mean of an array of n numbers
int i;
double sum = 0.0;
for (i = 0; i < n; i)
sum += v[i];
return sum/n;
}
课后答案网 www.khdaw.com
相关推荐
2023年江西萍乡中考道德与法治真题及答案.doc
2012年重庆南川中考生物真题及答案.doc
2013年江西师范大学地理学综合及文艺理论基础考研真题.doc
2020年四川甘孜小升初语文真题及答案I卷.doc
2020年注册岩土工程师专业基础考试真题及答案.doc
2023-2024学年福建省厦门市九年级上学期数学月考试题及答案.doc
2021-2022学年辽宁省沈阳市大东区九年级上学期语文期末试题及答案.doc
2022-2023学年北京东城区初三第一学期物理期末试卷及答案.doc
2018上半年江西教师资格初中地理学科知识与教学能力真题及答案.doc
2012年河北国家公务员申论考试真题及答案-省级.doc
2020-2021学年江苏省扬州市江都区邵樊片九年级上学期数学第一次质量检测试题及答案.doc
2022下半年黑龙江教师资格证中学综合素质真题及答案.doc
