第一章 绪论
1．（第18页，第（5）题）
确定下列各程序段的程序步，确定划线语句的执行次数，计算它们的渐近时间复杂度。 (1) i=1; k=0; do {
k=k+10*i; i++; } while(i
划线语句的执行次数为 n-1 。 (2）i=1; x=0; do{
x++; i=2*i; } while （i
划线语句的执行次数为 ⎡log 2n ⎤。 (3) for(int i=1;i
for (int k=1;k
划线语句的执行次数为n(n+1)(n+2)/6 。 (4）x=n;y=0;
while(x>=(y+1)*(y+1)) y++; 划线语句的执行次数为⎣ √n ⎦。
第二章 线性表
1．第37页 习题(2).2
在类LinearList 中增加一个成员函数，将顺序表逆置，实现该函数并分析算法的时间复杂度。不利用类SeqList 提供的操作直接实现。
template
void SeqList::Invert() {
T e;
for (int i=1;i
elements[i-1]=elements[length-i]; elements[length-i]=e; } }
2．第37页习题(5)
在类SingleList 中增加一个成员函数，将单链表逆置运算，直接实现该函数并分析其时间复杂度。
template
void SingleList::invert() {
Node *p=first,*q; first=NULL; while (p){
q=p->link; p->link=first; first=p; p=q; } }
3．（第37页，第7题） 单链表中结点按元素值递增链接，在类SingleList 中增加一个成员函数，直接实现删除结点值在a 至b 之间的结点(a b) 。
template
void SingleList::DeleteAb(T a,T b)//第37页，习题（7） {
Node *p=first,*q=first; while (p && p->datadatalink; }
else if (q==first){ q=p->link; delete p; p=first=q; } else{ q->link=p->link; delete p; p=q->link; } } } 4.（第37页，第8题） 在类CircularList 中增加一个成员函数，在不增加新结点的情况下，直接实现两个链表合并为一个链表的算法，并分析其时间复杂度。
template
void Merge(CircularList &a, CircularList &b) {
Node *p=b.first;
while (p->link!=b.first) p=p->link; p->link=a.first->link;
a.first->link=b.first->link;
b.first->link=b.first;
b.length=0; }
template
void Merge1(CircularList &a, CircularList &b) {
Node *p=b.first->link;
b.first->data=b.first->link->data; b.first->link=a.first->link; a.first->link=p->link; p->link=p; b.first=p; }
第三章 栈与队列
1．第50页 习题(1）
设A 、B 、C 、D 、E 五个元素依次进栈(进栈后可立即出栈) ，问能否得到下列序列。若能得到，则给出相应的push 和pop 序列；若不能，则说明理由。 1）A,B,C,D,E 2) A,C,E,B,D
3) C,A,B,D,E 4) E,D,C,B,A
答：2）和3）不能。对2）中的E ，B ，D 而言，E 最先出栈，则表明，此时B 和D 均在栈中，由于，B 先于D 进栈，所以应有D 先出栈。同理3）。 2. 第50页 习题（9）
利用栈可以检查表达式中括号是否配对，试编写算法实现之。
bool match(char a[],int n) {
int top=-1;
for (int i=0;i-1) top--; else return true; if (top>-1) return true; return false; }
3. 第50页 习题(10)
声明并实现链式队列类LinkedQueue 。
template
class LinkedStack: public Stack {
public:
LinkedStack(); ~LinkedStack();
virtual bool IsEmpty() const; virtual bool IsFull() const; virtual bool GetTop(T& x); virtual bool Push(const T x);
virtual bool Pop();
virtual void SetNull(); private:
Node *top; };
template
LinkedStack::LinkedStack() {
top=NULL; }
template
LinkedStack::~LinkedStack() {
Node *q; while (top){ q=top->link; delete top; top=q; } }
template
bool LinkedStack::IsEmpty() const {
return !top; }
template
bool LinkedStack::IsFull() const {
return false; }
template
bool LinkedStack::GetTop(T &x) {
if (IsEmpty()){ cout
x=top->data; return true; }
template
bool LinkedStack::Push(const T x) {
Node *q=new Node; q->data=x; q->link=top; top=q;
return true; }
template
bool LinkedStack::Pop() {
Node *q=top; if (IsEmpty()){ cout
top=top->link; delete q; return true; }
template
void LinkedStack::SetNull() {
Node *q; while (top){ q=top->link; delete top; top=q; } }
第四章 数组与字符串
1. 给出三维数组元素A[i][j][k]的存储地址loc(A[i][j][k])。
答： 设有三维数组声明为A[n1][n2][n3]，每个元素占k 个存储单元，则 loc(A[i][j][k])=loc(A[0][0][0])+k*(i*n2*n3+j*n3+k) 2．（第68页，第5题）给出下列稀疏矩阵的
顺序三元组的行优先和列优先表示。
3．（第68页，第6题）
对题图4-5的稀疏矩阵执行矩阵转置时数组num[]和k[]的值。 答：
}
4． （第69页，第15题（2））
在顺序串类String 中增加一个成员函数，实现统计该串中出现的字符、字符个数和每个字符出现的次数。
void String::count(char ch[],int &n, int num[]) {
n=0;
for (int i=0;i
while (j
else num[j]++; }
第五章 递归
1．设计一个递归算法，实现对一个有序表的顺序搜索。
template
int SeqList::Search4(const T& x) const {
elements[length]=1000; return Sch4(x,0); }
template
int SeqList::Sch4(const T& x,int i) const
if (x
else if (x==elements[i]) return ++i; else return Sch4(x,i+1); } 补充题：
（2）求顺序搜索有序表失败时的平均搜索长度。设有序表为（a 1,a 2, …,a n ），通常可以假定待查元素位于a 1之前，a 1与a 2之间，a 2与a 3之间, …,a n-1与a n 之间以及 an 之后的共n+1个位置处的概率是相等的。 答：
第六章 树
1．第107页，第（2）题
对于三个结点A ，B 和C ，可分别组成多少不同的无序树、有序树和二叉树？ 答：（1）无序树：9棵 （2）有序树：12棵 （3）二叉树：30棵 2、（1）k 的i －1次方 （2）（i ＋k －2）/k取整 （3）（i －1）k ＋m ＋1 （4）（i －1）%k不等于0 2．第107页，第（4）题
设对一棵二叉树进行中序遍历和后序遍历的结果分别为： （1）中序遍历 B D C E A F H G （2）后序遍历 D E C B H G F A 画出该二叉树。 答：
3. 第107页，第（6）题的第6小题
设计算法，交换一棵二叉树中每个结点的左、右子树。 template
void BTree::Exch(BTNode *p)
{
if (p){ BTNode *q=p->lchild; p->lchild=p->rchild; p->rchild=q; Exch(p->lchild); Exch(p->rchild); } }
4. 第107页，第10题
将图题6-24中的树转换成二叉树，并将图6-23中的二叉树转换成森林。
5. 第107页，第11题
给出对图6-24中的树的先序遍历和后序遍历的结果。 答：先序：A ，D ，E ，F ，J ，G ，M ，B ，L ，H ，C ，K
后序：J ，G ，F ，E ，D ，M ，H ，L ，K ，C ，B ，A 6. 第107页，第12题
分别以下列数据为输入，构造最小堆。 (1) 10，20，30，40，50，60，70，80 (2) 80，70，60，50，40，30，20，10 (3) 80，10，70，20，60，30，50，40 （1）
（2）
（3）
7. 第107页，第13题
分别以上题的数据为输入，从空的优先权队列开始，依此插入这些元素，求结果优先权队列的状态。
8. 第108页，第14题第（1）、（2）小题
设S={A,B,C,D,E,F}，W={2,3,5,7,9,12}，对字符集合进行哈夫曼编码，W 为各字符的频率。 （1) 画出哈夫曼树
（2）计算带权路径长度
第七章 集合与搜索树
1．第137页，第（5）,
建立37，45，91，25，14，76，56，65为输入时的二叉搜索树，再从该树上依此删除76，45，则树形分别如何？
2． 第137页，第（6）
试写一个判定任意给定的二叉树是否二叉搜索树算法。 int k=- ; bool fail=false; template
void BTree::IsBiTree(BTNode *p,int &k,bool &fail) {
if (p&& !fail){
IsBiTree(p->lchild,k,fail);
if(k
element) k=p->element; else fail=true;
IsBiTree(p->rchild,k,fail); } }
3． 第137页，第（8）
以下列序列为输入，从空树开始构造AVL 搜索树。 （1)A ，Z ，B ，Y ，C ，X （2)A,V,L,T,R,E,I,S,O,K
4． 第137页，第（12）
5阶B-树的高度为2时，树中元素个数最少为多少？ 答: 5
5． 第137页，第（13）题
从空树开始，以关键字序列：a,g,f,b,k,d,h,m,j,e,s,i,r,x ,建立 (1) 4阶B-树
;
(2) 5阶B-树。
(1) 4阶B-树
(2) 5阶B-树
6． 第137页，第（14）题
从上题的4阶B-树上依次删除a,e,f,h 。
第八章 散列与跳表
1． 第154页，第（3）题
设散列表ht[11]，散列函数h(key)=key % 11。采用线性探查法解决冲突，试用关键字值序 列：70，25，80，35，60，45，50，55 建立散列表。
2． 第154页，第（6）题
给出用拉链方法解决冲突的散列表搜索操作的C++函数实现。 template
bool LinkedHashTable::Search(const K &k,E&e)const {
int i=k % M,j;
HNode* p=ht[i];//元素结点类型Hnode while (p){
if(p->element==k)return true; p=p->nextsynonym; }
return false;
}
3． 第154页，第（3）题
设散列表ht[11]，散列函数h(key)=key % 11。采用二次探查法解决冲突，试用关键字值 序列：70，25，80，35，60，45，50，55 建立散列表。
4． 第154页，第（4）题
对上题的例子，若采用双散列法，试以散列函数h 1(key)=key % 11，h 2(key)= key % 9+1 建立散列表。
第九章 图
1． 第188页，第（1）题 对下面的有向图求
(1) 每个顶点的入度和出度； (2) 强连通分量 (3) 邻接矩阵
2． 第188页，第（2）题
当以边〈1，0〉，〈1，3〉，〈2，1〉，〈2，4〉，〈3，2〉，〈3，4〉，〈4，0〉，〈4，1〉，〈4，5〉， 〈5，0〉的次序从只有6个顶点没有边的图开始，通过依此插入这些边，建立邻接表结构。 画出该邻接表。
3． 第188页，第（4）题
已知有向图的邻接表，试写出计算各顶点的入度的算法。 template
void LinkedGraph::Degree() {
int *d=new int[n];int i; ENode* p;
for ( i=0;i
d[p->adjvex]++; p=p->nextarc; } }
for ( i=0;i
4． 第188页，第（6）题
在题2所建立的邻接表上进行以顶点2为起始顶点的深度优先搜索和广度优先搜索。分别 画出遍历所得到的深度优先搜索和广度优先搜索的生成森林（或生成树）。
5． 第188页，第（8）题
分别设计算法，在邻接矩阵上实现有向图的深度优先搜索. template
void MGraph::DFS(int v,bool visited[]) {
visited[v]=true; cout
for ( int j=0;j
if (a[v][j]&&!visited[j]) DFS(j,visited); }
6． 第188页，第（10）题
设某项工程由图题9-3所示的工序组成。若各工序以流水方式进行（即串行进行）。
(1) 画出给工程的AOV 网络；
(2) 给出该工程的全部合理的工程流程。
7． 第188页，第（11）题 设有边集合：〈0，1〉，〈1，2〉，〈4，1〉，〈4，5〉，〈5，3〉，〈2，3〉
(1) 求此图的所有可能的拓扑序列；
(2) 若以此顺序通过加入边的方式建立邻接表，则在该邻接表上执行拓扑排序算法
（TopoSort ），则得到的拓扑序列是其中哪一种？
8. 第188页，第（13）题
使用普里姆算法以1为源点，画出图题9-5的无向图的最小代价生成树。
9. 第188页，第（16）题
用迪杰斯特拉算法求图题9-6的有向图中以顶点A 为源点的单源最短路径。写出一维数组d 和 path在执行该算法的过程中各步的状态。
10. 第188页，第（17）题
用弗洛伊德算法求图题9-6的有向图的所有顶点之间的最短路径。写出二维数组d 和path 在 执行该算法的过程中各步的状态。
（1）初始状态
dB
21. 第200页，第（1）题
元素序列(61,87,12,03,08,70,97,75,53,26)按下列算法排序，给出各趟排序结果。 (1) 简单选择排序； (2) 冒泡排序；
(3) 直接插入排序； (4) 快速排序；
(5) 两路合并排序；
(1) 简单选择排序
初始序列（61 87 12 03 08 70 97 75 53 26 第1趟 （03）87 12 61 08 70 97 75 53 26 第2趟 （03 08）12 61 87 70 97 75 53 26 第3趟 （03 08 12）61 87 70 97 75 53 26 第4趟 （03 08 12 26）87 70 97 75 53 61 第5趟 （03 08 12 26 53）70 97 75 87 61 第6趟 （03 08 12 26 53 61）97 75 87 70 第7趟 （03 08 12 26 53 61 70）75 87 97 第8趟 （03 08 12 26 53 61 70 75）87 97 第9趟 （03 08 12 26 53 61 70 75 87）97
（2）冒泡排序
初始序列（61 87 12 03 08 70 97 75 53 26 第1趟 61 12 03 08 70 87 75 53 26 97
第2趟 12 03 08 61 70 75 53 26 87 97 第3趟 03 08 12 61 70 53 26 75 87 97 第4趟 03 08 12 61 53 26 70 75 87 97 第5趟 03 08 12 53 26 61 70 75 87 97 第6趟 03 08 12 26 53 61 70 75 87 97 第7趟 03 08 12 26 53 61 70 75 87 97 第8趟 03 08 12 26 53 61 70 75 87 97 第9趟 03 08 12 26 53 61 70 75 87 97
（3）直接插入排序
初始序列（61）87 12 03 08 70 97 75 53 26 第1趟 （61 87）12 03 08 70 97 75 53 26 第2趟 （12 61 87）03 08 70 97 75 53 26 第3趟 （03 12 61 87）08 70 97 75 53 26 第4趟 （03 08 12 61 87）70 97 75 53 26 第5趟 （03 08 12 61 70 87） 97 75 53 26 第6趟 （03 08 12 61 70 87 97）75 53 26 第7趟 （03 08 12 61 70 75 87 97）53 26 第8趟 （03 08 12 53 61 70 75 87 97）26 第9趟 （03 08 12 26 53 61 70 75 87 97）
22. 第200页，第（3）题
在带表头结点的单链表上实现简单选择排序。 template
void SingleList::select_sort() { Node *p,*r,*small; p=first->link; if(p)
for(; p->link; p=p->link)
{ for(small=p,r=p->link; r; r=r->link)
if(small->data>r->data) small=r;
if(small!=p) swap(p->data, small->data); } };
直接插入排序：
template //用带表头节点的单链表存储 void SingleList::DirInsert() { Node *head,*q,*p1,*p2; if(first->link)
{ head=first->link->link; //head是待插入元素的链表头 first->link->link=NULL; //first是只有一个节点的有序链表 while(head)
{ q=head; head=head->link;//从待插入链中取下一个节点 p1=first; p2=first->link; //p1是p2的直接前驱节点 while(p2&&p2->datadata) //从前往后找插入位置 { p1=p2; p2=p2->link; } if(p2) //q插入在p1和p2之间 { q->link=p2; p1->link=q; }
else //q插入在p2之后，即有序链的最后 { q->link=NULL; p1->link=q; } } }
10．4
template void sort(T a[],int n) { int i,j,k=0,m=-1,s,t; T x;
while (k
for (i=k;ia[i+1]) { x=a[i]; a[i]=a[i+1]; a[i+1]=x; s=i; } m=s; t =m; for (j=m;j>k;j--) //从下向上冒泡 if (a[j]
10．6
证明: 快速排序算法的基本思想时，每次把一个集合划分成大于和小于某个基准值的两个子集合。最坏情况是两个子集合中总有一个是空集合，即将一个集合分成了一个子集合和一个作为基准值的元素。即最坏情况下划分的自己和比原集合的元素只少一个。故要划分n-1次才能使得子集合中的元素少于2，而每次划分子集合都要扫描整个集合，所以时间复杂度是O(n2) 。
10．7
template //方法一 void sort(T a[],int n) {
int i=0,j=n-1; T x=a[0]; while (i
while (a[j]>=0&&j>i) j--; //找负数 if (j>i) a[i++]=a[j];
while (a[i]
a[j]=x; }
10．8
template
void Merge(T A[],T Temp[],int i1,int j1,int i2,int j2,int &k) { if (i1>j1&&i2>j2) cout
else if (i1>j1) while (i2j2) while (i1template //p.196 void MergeSort(T A[],int n) { T *Temp=new T [n];
int i1,i2,j1,j2,i,k,size=1; while (sizen-1) j2=n-1; else j2=j1+size; Merge(A,Temp,i1,j1,i2,j2,k); i1=j2+1; } for (i=0;i
delete [] Temp;
}
第一章 绪论
1．（第18页，第（5）题）
确定下列各程序段的程序步，确定划线语句的执行次数，计算它们的渐近时间复杂度。 (1) i=1; k=0; do {
k=k+10*i; i++; } while(i
划线语句的执行次数为 n-1 。 (2）i=1; x=0; do{
x++; i=2*i; } while （i
划线语句的执行次数为 ⎡log 2n ⎤。 (3) for(int i=1;i
for (int k=1;k
划线语句的执行次数为n(n+1)(n+2)/6 。 (4）x=n;y=0;
while(x>=(y+1)*(y+1)) y++; 划线语句的执行次数为⎣ √n ⎦。
第二章 线性表
1．第37页 习题(2).2
在类LinearList 中增加一个成员函数，将顺序表逆置，实现该函数并分析算法的时间复杂度。不利用类SeqList 提供的操作直接实现。
template
void SeqList::Invert() {
T e;
for (int i=1;i
elements[i-1]=elements[length-i]; elements[length-i]=e; } }
2．第37页习题(5)
在类SingleList 中增加一个成员函数，将单链表逆置运算，直接实现该函数并分析其时间复杂度。
template
void SingleList::invert() {
Node *p=first,*q; first=NULL; while (p){
q=p->link; p->link=first; first=p; p=q; } }
3．（第37页，第7题） 单链表中结点按元素值递增链接，在类SingleList 中增加一个成员函数，直接实现删除结点值在a 至b 之间的结点(a b) 。
template
void SingleList::DeleteAb(T a,T b)//第37页，习题（7） {
Node *p=first,*q=first; while (p && p->datadatalink; }
else if (q==first){ q=p->link; delete p; p=first=q; } else{ q->link=p->link; delete p; p=q->link; } } } 4.（第37页，第8题） 在类CircularList 中增加一个成员函数，在不增加新结点的情况下，直接实现两个链表合并为一个链表的算法，并分析其时间复杂度。
template
void Merge(CircularList &a, CircularList &b) {
Node *p=b.first;
while (p->link!=b.first) p=p->link; p->link=a.first->link;
a.first->link=b.first->link;
b.first->link=b.first;
b.length=0; }
template
void Merge1(CircularList &a, CircularList &b) {
Node *p=b.first->link;
b.first->data=b.first->link->data; b.first->link=a.first->link; a.first->link=p->link; p->link=p; b.first=p; }
第三章 栈与队列
1．第50页 习题(1）
设A 、B 、C 、D 、E 五个元素依次进栈(进栈后可立即出栈) ，问能否得到下列序列。若能得到，则给出相应的push 和pop 序列；若不能，则说明理由。 1）A,B,C,D,E 2) A,C,E,B,D
3) C,A,B,D,E 4) E,D,C,B,A
答：2）和3）不能。对2）中的E ，B ，D 而言，E 最先出栈，则表明，此时B 和D 均在栈中，由于，B 先于D 进栈，所以应有D 先出栈。同理3）。 2. 第50页 习题（9）
利用栈可以检查表达式中括号是否配对，试编写算法实现之。
bool match(char a[],int n) {
int top=-1;
for (int i=0;i-1) top--; else return true; if (top>-1) return true; return false; }
3. 第50页 习题(10)
声明并实现链式队列类LinkedQueue 。
template
class LinkedStack: public Stack {
public:
LinkedStack(); ~LinkedStack();
virtual bool IsEmpty() const; virtual bool IsFull() const; virtual bool GetTop(T& x); virtual bool Push(const T x);
virtual bool Pop();
virtual void SetNull(); private:
Node *top; };
template
LinkedStack::LinkedStack() {
top=NULL; }
template
LinkedStack::~LinkedStack() {
Node *q; while (top){ q=top->link; delete top; top=q; } }
template
bool LinkedStack::IsEmpty() const {
return !top; }
template
bool LinkedStack::IsFull() const {
return false; }
template
bool LinkedStack::GetTop(T &x) {
if (IsEmpty()){ cout
x=top->data; return true; }
template
bool LinkedStack::Push(const T x) {
Node *q=new Node; q->data=x; q->link=top; top=q;
return true; }
template
bool LinkedStack::Pop() {
Node *q=top; if (IsEmpty()){ cout
top=top->link; delete q; return true; }
template
void LinkedStack::SetNull() {
Node *q; while (top){ q=top->link; delete top; top=q; } }
第四章 数组与字符串
1. 给出三维数组元素A[i][j][k]的存储地址loc(A[i][j][k])。
答： 设有三维数组声明为A[n1][n2][n3]，每个元素占k 个存储单元，则 loc(A[i][j][k])=loc(A[0][0][0])+k*(i*n2*n3+j*n3+k) 2．（第68页，第5题）给出下列稀疏矩阵的
顺序三元组的行优先和列优先表示。
3．（第68页，第6题）
对题图4-5的稀疏矩阵执行矩阵转置时数组num[]和k[]的值。 答：
}
4． （第69页，第15题（2））
在顺序串类String 中增加一个成员函数，实现统计该串中出现的字符、字符个数和每个字符出现的次数。
void String::count(char ch[],int &n, int num[]) {
n=0;
for (int i=0;i
while (j
else num[j]++; }
第五章 递归
1．设计一个递归算法，实现对一个有序表的顺序搜索。
template
int SeqList::Search4(const T& x) const {
elements[length]=1000; return Sch4(x,0); }
template
int SeqList::Sch4(const T& x,int i) const
if (x
else if (x==elements[i]) return ++i; else return Sch4(x,i+1); } 补充题：
（2）求顺序搜索有序表失败时的平均搜索长度。设有序表为（a 1,a 2, …,a n ），通常可以假定待查元素位于a 1之前，a 1与a 2之间，a 2与a 3之间, …,a n-1与a n 之间以及 an 之后的共n+1个位置处的概率是相等的。 答：
第六章 树
1．第107页，第（2）题
对于三个结点A ，B 和C ，可分别组成多少不同的无序树、有序树和二叉树？ 答：（1）无序树：9棵 （2）有序树：12棵 （3）二叉树：30棵 2、（1）k 的i －1次方 （2）（i ＋k －2）/k取整 （3）（i －1）k ＋m ＋1 （4）（i －1）%k不等于0 2．第107页，第（4）题
设对一棵二叉树进行中序遍历和后序遍历的结果分别为： （1）中序遍历 B D C E A F H G （2）后序遍历 D E C B H G F A 画出该二叉树。 答：
3. 第107页，第（6）题的第6小题
设计算法，交换一棵二叉树中每个结点的左、右子树。 template
void BTree::Exch(BTNode *p)
{
if (p){ BTNode *q=p->lchild; p->lchild=p->rchild; p->rchild=q; Exch(p->lchild); Exch(p->rchild); } }
4. 第107页，第10题
将图题6-24中的树转换成二叉树，并将图6-23中的二叉树转换成森林。
5. 第107页，第11题
给出对图6-24中的树的先序遍历和后序遍历的结果。 答：先序：A ，D ，E ，F ，J ，G ，M ，B ，L ，H ，C ，K
后序：J ，G ，F ，E ，D ，M ，H ，L ，K ，C ，B ，A 6. 第107页，第12题
分别以下列数据为输入，构造最小堆。 (1) 10，20，30，40，50，60，70，80 (2) 80，70，60，50，40，30，20，10 (3) 80，10，70，20，60，30，50，40 （1）
（2）
（3）
7. 第107页，第13题
分别以上题的数据为输入，从空的优先权队列开始，依此插入这些元素，求结果优先权队列的状态。
8. 第108页，第14题第（1）、（2）小题
设S={A,B,C,D,E,F}，W={2,3,5,7,9,12}，对字符集合进行哈夫曼编码，W 为各字符的频率。 （1) 画出哈夫曼树
（2）计算带权路径长度
第七章 集合与搜索树
1．第137页，第（5）,
建立37，45，91，25，14，76，56，65为输入时的二叉搜索树，再从该树上依此删除76，45，则树形分别如何？
2． 第137页，第（6）
试写一个判定任意给定的二叉树是否二叉搜索树算法。 int k=- ; bool fail=false; template
void BTree::IsBiTree(BTNode *p,int &k,bool &fail) {
if (p&& !fail){
IsBiTree(p->lchild,k,fail);
if(k
element) k=p->element; else fail=true;
IsBiTree(p->rchild,k,fail); } }
3． 第137页，第（8）
以下列序列为输入，从空树开始构造AVL 搜索树。 （1)A ，Z ，B ，Y ，C ，X （2)A,V,L,T,R,E,I,S,O,K
4． 第137页，第（12）
5阶B-树的高度为2时，树中元素个数最少为多少？ 答: 5
5． 第137页，第（13）题
从空树开始，以关键字序列：a,g,f,b,k,d,h,m,j,e,s,i,r,x ,建立 (1) 4阶B-树
;
(2) 5阶B-树。
(1) 4阶B-树
(2) 5阶B-树
6． 第137页，第（14）题
从上题的4阶B-树上依次删除a,e,f,h 。
第八章 散列与跳表
1． 第154页，第（3）题
设散列表ht[11]，散列函数h(key)=key % 11。采用线性探查法解决冲突，试用关键字值序 列：70，25，80，35，60，45，50，55 建立散列表。
2． 第154页，第（6）题
给出用拉链方法解决冲突的散列表搜索操作的C++函数实现。 template
bool LinkedHashTable::Search(const K &k,E&e)const {
int i=k % M,j;
HNode* p=ht[i];//元素结点类型Hnode while (p){
if(p->element==k)return true; p=p->nextsynonym; }
return false;
}
3． 第154页，第（3）题
设散列表ht[11]，散列函数h(key)=key % 11。采用二次探查法解决冲突，试用关键字值 序列：70，25，80，35，60，45，50，55 建立散列表。
4． 第154页，第（4）题
对上题的例子，若采用双散列法，试以散列函数h 1(key)=key % 11，h 2(key)= key % 9+1 建立散列表。
第九章 图
1． 第188页，第（1）题 对下面的有向图求
(1) 每个顶点的入度和出度； (2) 强连通分量 (3) 邻接矩阵
2． 第188页，第（2）题
当以边〈1，0〉，〈1，3〉，〈2，1〉，〈2，4〉，〈3，2〉，〈3，4〉，〈4，0〉，〈4，1〉，〈4，5〉， 〈5，0〉的次序从只有6个顶点没有边的图开始，通过依此插入这些边，建立邻接表结构。 画出该邻接表。
3． 第188页，第（4）题
已知有向图的邻接表，试写出计算各顶点的入度的算法。 template
void LinkedGraph::Degree() {
int *d=new int[n];int i; ENode* p;
for ( i=0;i
d[p->adjvex]++; p=p->nextarc; } }
for ( i=0;i
4． 第188页，第（6）题
在题2所建立的邻接表上进行以顶点2为起始顶点的深度优先搜索和广度优先搜索。分别 画出遍历所得到的深度优先搜索和广度优先搜索的生成森林（或生成树）。
5． 第188页，第（8）题
分别设计算法，在邻接矩阵上实现有向图的深度优先搜索. template
void MGraph::DFS(int v,bool visited[]) {
visited[v]=true; cout
for ( int j=0;j
if (a[v][j]&&!visited[j]) DFS(j,visited); }
6． 第188页，第（10）题
设某项工程由图题9-3所示的工序组成。若各工序以流水方式进行（即串行进行）。
(1) 画出给工程的AOV 网络；
(2) 给出该工程的全部合理的工程流程。
7． 第188页，第（11）题 设有边集合：〈0，1〉，〈1，2〉，〈4，1〉，〈4，5〉，〈5，3〉，〈2，3〉
(1) 求此图的所有可能的拓扑序列；
(2) 若以此顺序通过加入边的方式建立邻接表，则在该邻接表上执行拓扑排序算法
（TopoSort ），则得到的拓扑序列是其中哪一种？
8. 第188页，第（13）题
使用普里姆算法以1为源点，画出图题9-5的无向图的最小代价生成树。
9. 第188页，第（16）题
用迪杰斯特拉算法求图题9-6的有向图中以顶点A 为源点的单源最短路径。写出一维数组d 和 path在执行该算法的过程中各步的状态。
10. 第188页，第（17）题
用弗洛伊德算法求图题9-6的有向图的所有顶点之间的最短路径。写出二维数组d 和path 在 执行该算法的过程中各步的状态。
（1）初始状态
dB
21. 第200页，第（1）题
元素序列(61,87,12,03,08,70,97,75,53,26)按下列算法排序，给出各趟排序结果。 (1) 简单选择排序； (2) 冒泡排序；
(3) 直接插入排序； (4) 快速排序；
(5) 两路合并排序；
(1) 简单选择排序
初始序列（61 87 12 03 08 70 97 75 53 26 第1趟 （03）87 12 61 08 70 97 75 53 26 第2趟 （03 08）12 61 87 70 97 75 53 26 第3趟 （03 08 12）61 87 70 97 75 53 26 第4趟 （03 08 12 26）87 70 97 75 53 61 第5趟 （03 08 12 26 53）70 97 75 87 61 第6趟 （03 08 12 26 53 61）97 75 87 70 第7趟 （03 08 12 26 53 61 70）75 87 97 第8趟 （03 08 12 26 53 61 70 75）87 97 第9趟 （03 08 12 26 53 61 70 75 87）97
（2）冒泡排序
初始序列（61 87 12 03 08 70 97 75 53 26 第1趟 61 12 03 08 70 87 75 53 26 97
第2趟 12 03 08 61 70 75 53 26 87 97 第3趟 03 08 12 61 70 53 26 75 87 97 第4趟 03 08 12 61 53 26 70 75 87 97 第5趟 03 08 12 53 26 61 70 75 87 97 第6趟 03 08 12 26 53 61 70 75 87 97 第7趟 03 08 12 26 53 61 70 75 87 97 第8趟 03 08 12 26 53 61 70 75 87 97 第9趟 03 08 12 26 53 61 70 75 87 97
（3）直接插入排序
初始序列（61）87 12 03 08 70 97 75 53 26 第1趟 （61 87）12 03 08 70 97 75 53 26 第2趟 （12 61 87）03 08 70 97 75 53 26 第3趟 （03 12 61 87）08 70 97 75 53 26 第4趟 （03 08 12 61 87）70 97 75 53 26 第5趟 （03 08 12 61 70 87） 97 75 53 26 第6趟 （03 08 12 61 70 87 97）75 53 26 第7趟 （03 08 12 61 70 75 87 97）53 26 第8趟 （03 08 12 53 61 70 75 87 97）26 第9趟 （03 08 12 26 53 61 70 75 87 97）
22. 第200页，第（3）题
在带表头结点的单链表上实现简单选择排序。 template
void SingleList::select_sort() { Node *p,*r,*small; p=first->link; if(p)
for(; p->link; p=p->link)
{ for(small=p,r=p->link; r; r=r->link)
if(small->data>r->data) small=r;
if(small!=p) swap(p->data, small->data); } };
直接插入排序：
template //用带表头节点的单链表存储 void SingleList::DirInsert() { Node *head,*q,*p1,*p2; if(first->link)
{ head=first->link->link; //head是待插入元素的链表头 first->link->link=NULL; //first是只有一个节点的有序链表 while(head)
{ q=head; head=head->link;//从待插入链中取下一个节点 p1=first; p2=first->link; //p1是p2的直接前驱节点 while(p2&&p2->datadata) //从前往后找插入位置 { p1=p2; p2=p2->link; } if(p2) //q插入在p1和p2之间 { q->link=p2; p1->link=q; }
else //q插入在p2之后，即有序链的最后 { q->link=NULL; p1->link=q; } } }
10．4
template void sort(T a[],int n) { int i,j,k=0,m=-1,s,t; T x;
while (k
for (i=k;ia[i+1]) { x=a[i]; a[i]=a[i+1]; a[i+1]=x; s=i; } m=s; t =m; for (j=m;j>k;j--) //从下向上冒泡 if (a[j]
10．6
证明: 快速排序算法的基本思想时，每次把一个集合划分成大于和小于某个基准值的两个子集合。最坏情况是两个子集合中总有一个是空集合，即将一个集合分成了一个子集合和一个作为基准值的元素。即最坏情况下划分的自己和比原集合的元素只少一个。故要划分n-1次才能使得子集合中的元素少于2，而每次划分子集合都要扫描整个集合，所以时间复杂度是O(n2) 。
10．7
template //方法一 void sort(T a[],int n) {
int i=0,j=n-1; T x=a[0]; while (i
while (a[j]>=0&&j>i) j--; //找负数 if (j>i) a[i++]=a[j];
while (a[i]
a[j]=x; }
10．8
template
void Merge(T A[],T Temp[],int i1,int j1,int i2,int j2,int &k) { if (i1>j1&&i2>j2) cout
else if (i1>j1) while (i2j2) while (i1template //p.196 void MergeSort(T A[],int n) { T *Temp=new T [n];
int i1,i2,j1,j2,i,k,size=1; while (sizen-1) j2=n-1; else j2=j1+size; Merge(A,Temp,i1,j1,i2,j2,k); i1=j2+1; } for (i=0;i
delete [] Temp;
}