作业一
（（第一章--第二章）
一、单选题
1.一个数组元素a[i]与 A 的表示等价。
A *(a+i) B a+i C *a+i D &a+i
2.对于两个函数，若函数名相同，但只是 C 不同则不是重载函数。
A 参数类型 B 参数个数 C 函数类型
3.若需要利用形参直接访问实参，则应把形参变量说明为 B 参数。
A 指针 B 引用 C 值
4.下面程序段的复杂度为 C 。
for(int i=0;i
A O(m2) B O(n2) C O(m*n) D O(m+n)
5.执行下面程序段时，执行S语句的次数为 D 。
for(int i=1;i<=n;i++)
for(int j=1; j<=i;j++)
S;
A n2 B n2/2 C n(n+1) D n(n+1)/2
6.下面算法的时间复杂度为 B 。
int f(unsigned int n)
if(n==0
A O(1) B O(n) C O(n2) D O(n!)
二、填空题
1.数据的逻辑结构被除数分为 集合结构 、 线性结构 、 树型结构 和 图形结构 四种。
2.数据的存储结构被分为 顺序结构 、 链接结构 、 索引结构 和 散列结构 四种。
3.在线性结构、树型结构和图形结构中，前驱和后继结点之间分别存在着 1对1 、 1对N 和 M对N 的关系。
4.一种抽象数据类型包括 数据 和 操作 两个部分。
5.当一个形参类型的长度较大时，应最好说明为 引用 ，以节省参数值的传输时间和存储参数的空间。
6.当需要用一个形参访问对应的实参时，则该形参应说明为 引用 。
7.在函数中对引用形参的修改就是对相应 实参 的修改，对 值(或赋值)形参的修改只局限在该函数的内部，不会反映到对应的实参上。
8.当需要进行标准I/O操作时，则应在程序文件中包含 iostream.h 头文件，当需要进行文件I/O操作时，则应在程序文件中包含 fstream.h 头文件。
9.在包含有 stdlib.h 头文件的程序文件中，使用 rand()%21 能够产生0-20之间的一个随机数。
10.一个记录r理论上占有的存储空间的大小等于所有域的 长度之和 ，实际上占有的存储空间的大小即记录长度为 sizeof(r) 。
11.一个数组a所占有的存储空间的大小即数组长度为 sizeof(a) ，下标为i的元数a[i]的存储地址为 a+1 ，或者为 (char*)a+i*sizeof(a[i]) 。
12.函数重载要求 参数类型 、 参数个数 或 排列顺序 有所不同。
13.对于双目操作符，其重载函数带有 2 个参数，其中至少有一个为 用户自定义 的类型。
14.若对象ra和rb中至少有一个属于用户定义的类型，则执行ra==rb时，需要调用 等于号(==) 重载函数，该函数第一个参数应与 ra ，的类型相同，第二个参数应与 rb 的类型相同。
15.从一维数组a[n]中顺序查找出一个最大值元素的时间复杂度为 O(n) ，输出一个二维
数组b[m][n]中所有元素值的时间复杂度为 O(m*n) 。
16.在下面程序段中，s=s+p语句的执行次数为 n ，p*=j语句的执行次数为n(n+1)/2，该
程序段的时间复杂度为 O(n2) 。
int i=0,s=0;
while(++i<=n)
int p=1;
for(int j=1;j<=i;j++) P*=j;
s=s+p;
17.一个算法的时间复杂度为(3n2+2nlog2n+4n-7)/(5n),其数量级表示为 O(n) 。
18.从一个数组a[7]中顺序查找元素时，假定查找第一个元素a[0]的概率为1/3，查找第二个元素a[1]的概率为1/4，查找其余元素的概率均相同，则在查找成功时同元素的平均比较次数为 35/12 。
三、应用题
1.设计二次多项式ax2+bx+c的一种抽象数据类型，假定起名为QIAdratic,该类型的数据部分分为三个系数项a、b和c，操作部分为：(请写出下面每一个操作的具体实现)。
⑴ 初始化数据成员ab和c(假定用记录类型Quadratie定义成员)，每个数据成
员的默认值为0。
Quadratic InitQuadratic(float aa=0,float bb=0,float cc=0);
解：
Quadratic InitQuadratic(float aa,float bb,float cc)
Quadratic q;
q.a=aa;
q.b=bb;
q.c=cc;
return q;
⑵ 做两个多项式加法,即使对应的系数相加,并返回相加的结果。
Quadratic Add(Quadratic q1,Quadratic q2);
解：
Quadratic Add(Quadratic q1,Quadratic q2);
Quadratic q;
q.a=q1.a+q2.a;
q.b=q1.b+q2.b;
q.c=q1.c+q2.c;
return q;
⑶ 根据给定x的值计算多项式的值。
float Eval(Quadratic q,float x);
解：
float Eval(Quadratic q,float x)
return(q.a*x*x+q.b*x+q.c);
⑷ 计算方程ax2+bx+c=0的两个实数根，对于有实根、无实根和不是实根方程
(即a==0)这三种情况要返回不同的整数值，以便于工作调用函数做不同的处理。
int Root(Quadratic q,float& r1,float& r2);
解：
int Root(Quadratic q,float& r1,float& r2)
{
if(q.a==0)return -1;
float x=q.b*q.b-4*q.a*q.c;
if(x>=0)
r1=(float)(-q.b+sqrt(x))/(2*q.a);
r2=(float)(-q.b-sqrt(x))/(2*q.a);
return 1;
else
return 0;
}
⑸ 按照ax**2+bx+c的格式(x2用x**2表示)输出二次多项式，在输出时要注意
去掉系数为0的项，并且当b和c的值为负时，其前不能出现加号。
void Print(Quadratic q)
解：
void Print(Quadratic q)
if(q.a) cout<
if(q.b>0)
cout<<"+"<
cout<
if(q.c>0)
cout<<"+"<
cout<
2.指出下列各算法的功能并求出其时间复杂度。
⑴ int prime(int n)
int i=1;
int x=(int)sqrt(n);
while(++i<=x)
if(n%i==0)break;
if(i>x) return 1;
else return 0;
解：
判断n是否是一个素数，若是则返回数值1，否则返回0。该算法的时间复杂度为 O(n1/2)。
⑵ int sum1(int n)
{
int p=1,s=0;
for(int i=1;i<=n;i++)
p*=i;
s+=p;
return s;
}
解： 计算∑i!(上标为n，下标为i=1)的值，其时间的复杂度为O(n)。
⑶ int sum2(int n)
{
int s=0;
for(int i=1;i<=n;i++)
int p=1;
for(int j=1;j<=i;j++)
p*=j;
s+=p;
return s;
}
解： 计算∑i!的值，时间复杂度为O(n2)
⑷ int fun(int n)
int i=1,s=1;
while(s
return i;
解： 求出满足不等式1+2+3...+i≥n的最小i值， 其时间复杂度为O(n1/2)。
⑸ void UseFile(ifstream& inp,int c[10])
//假定inp所对应的文件中保存有n个整数
{
for(int i=0;i<10;i++)
c[i]=0;
int x;
while(inp>>x)
i=x%10;
c[i]++;
}
解：
利用数组c[10]中的每个元素c[i]对应统计出inp所联系的整数文件中个位值同为i的整数个
数，时间复杂度为O(n)
⑹ void mtable(int n)
{
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
cout<
}
解：
打印出一个具有n行的乘法表，第i行(1≤i≤n)中有n-i+1个乘法项，每个乘法项为i与j(i≤j≤n)的乘积，时间复杂度为O(n2)。
⑺ void cmatrix(int a[M][N],int d)
//M和N为全局整型常量
for(int i=0;i
解：
使数组a[M][N]中的每一个元素均详细以d的值，时间复杂度为O(M*N)
⑻ void matrimult(int a[M][N],int b[N][L],int c[M][L])
int i,j,k;
for(i=0;i
for(i=0;i
解：
矩阵相乘，即a[M][N]×b[N][L]→c[M][L]，时间复杂度为O(M×N×L)。
第二章 线性表
一、在下面每个程序段中，假定线性表La的类型为List，元素类型ElemType为int，并假定每个程序段是连续执行的，试写出每个程序段执行后所得到的线性表La。
⑴ InitList(La);
int a[ ]=48,26,57,34,62,79;
for(i=0;i<6;i++)
InsertFront(La,a[i];
TraverseList(La);
解：(79,62,34,57,26,48)
⑵InitList(La);
for(I=0;I<6;I++)
Insert (La,a[i]);
TraverseList(La);
解：(26,34,48,57,62,79)
⑶Insert(La,56);
DeleteFront(La);
InsertRear(La,DeleteFront(La));
TraverseList(La);
解：(48,56,57,62,79,34)
⑷for(i=1;i<=3;i++)
int x=GetElem(La,i);
if(x%2==0)Delete(La,x);
TraverseList(La);
解：(56,57,79,34)
⑸ClearList(La);
for(i=0;i<6;i++)
InsertRear(La,a[i]);
Delete(La,a[5]);
Sort(La);
Insert(La,a[5]/2);
TraverseList(La);
解：(26,34,39,48,57,62)
二、对于List类型的线性表,编写出下列每个算法。
⑴ 从线性表中删除具有最小值的元素并由函数返回，空出的位置由最后一个元素填补，若
线性表为空则显示出错信息并退出运行。
解： ElemType DMValue(List&L)
//从线性表中删除具有最小值的元素并由函数返回,空出的位置
//由最后一个元素填补,若线性表为空则显示出错信息并退出运行
{
if(ListEmpty(L))
cerr<<"List is Empty!"<
ElemType x;
x=L.list[0];
int k=0;
for(int i=1;i
if(y
L.list[k]=L.list[L.size-1];
L.size--;
return x;}
⑵ 从线性表中删除第i个元素并由函数返回。
解：int Deletel(List& L,int i)
//从线性表中删除第i个元素并由函数返回
{
if(i<1||i>L.size)
cerr<<"Index is out range!"<
ElemType x;
x=L.list[i-1];
for(int j=i-1;j
L.size--;
return x;
}
⑶ 向线性表中第i个元素位置插入一个元素。
解：void Inser1(List& L,int i,ElemType x)
//向线性表中第i个元素位置插入一个元素
{
if(i<1||i>L.size+1)
cerr<<"Index is out range!"<
if(L.size==MaxSize)
cerr<<"List overflow!"<
for(int j=L.size-1;j>i-1;j--)
L.list[j+1]=L.list[j];
L.list[i-1]=x;
L.size++;
}
⑷ 从线性表中删除具有给定值x的所有元素。
解：void Delete2(List& L,ElemType x)
//从线性表中删除具有给定值x的所有元素
{
int i=0;
while(i
for(int j=i+1;j
L.size--;
else
i++;
}
4.对于结点类型为LNode的单链接表,编写出下列每个算法。
⑴ 将一个单链接表按逆序链接,即若原单链表中存储元素的次序为a1,a2,...,an,则
逆序链接后变为an,an-1,...a1。
解：void Contrary(LNode*&HL)
//将一个单多办实事有按逆序链接
{
LNode*p=HL;//p指向待逆序的第一个结点，初始指向原表头结点
HL=NULL;//HL仍为逆序后的表头指针，禄始值为空
while(p!=NULL)
//把原单链表中的结点依次进行逆序链接
LNode*q=p; //q指向待处理的结点
p=p->next; //p指向下一个待逆序的结点
//将q结点插入到已陈序单链表的表头
q->next=HL;
HL=q;
}
⑵ 删除单链表中的第i个结点。
解：void Delete1(LNode*&HL,int i)
//删除单链表中的第i个结点
{
if(i<1||HL==NULL)
cerr<<"Index is out range!"<
LNode*ap,*cp;
ap=NULL;cp=HL; //cp指向当前结点，ap指向其前驱结点
int j=1;
while(cp!=NULL)
if(j==i)
break; //cp结点即为第i个结点
else//继续向后寻找
ap=cp;
cp=cp->next;
j++;
if(cp==NULL)
cerr<<"Index is out range!"<
if(ap==NULL)
HL=HL->next;
else
ap->next=cp->next;
delete cp;}
⑶ 从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息
并停止运行。
解：ElemType MaxValue(LNode*HL)
//从单链表中查找出所有元素的最大值，该值由函数返回
{
if(HL==NULL)
cerr<<"Linked list is empty!"<
ElemType max=HL->data;
LNode*p=HL->next;
while(p!=NULL)
if(max
p=p->next;
return max;
}
⑷ 统计出单链表中结点的值等于给定值x的结点数。
解：int Count(LNode*HL,ElemType x)
//统计出单链表中结点的值等于给定值x的结点数
{
int n=0;
while(HL!=NULL)
if(HL->data==x) n++;
HL=HL->next;
return n;}
作业二
（（第三章--第四章）
一、单选题
1.在稀疏矩阵的带行指针指向量的链接存储中，每个行单链表中的结点都具有相同的
A 。
A 行号 B 列号 C 元素值 D 地址
2.设一个具有t个非零元素的m*n大小的稀疏矩阵采用顺序存储，求其转置矩阵的普通
转置算法的时间复杂度为 D 。
A O(m) B O(n) C O(n+t) D O(n*t)
3.设一个广义表中结点的个数为n，则求广义表深度算法的时间复杂度为 B。
A O(1) B O(n) C O(n2) D O(log2n)
二、填空题
1.在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的 行号 、 列号 、和
元素值 。
2.在稀疏矩阵所对应的三元组线性表中，每个三元组元素按 行号 为主序、 列号 为辅
助的次序排列。
3.在初始化一个稀疏矩阵的函数定义中，矩阵形参应说明为 引用 参数。
4.在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应 大于
等于 对应的三元线性表的长度。
5.在稀疏矩阵的带行指针向量的链接存储中，每个结点包含有 4 个域，在相应的
十字链接存储中，每个结点包含有 5 个域。
6.在稀疏矩阵的十字链接存储中，每个结点的down指针域指向 行号 相同的下一个结点，
right指针指向 列号 相同的下一个结点。
7.一个广义表中的元素为 单 元素和 表 元素两类。
8.一个广义表的深度等于 括号 嵌套的最大层数。
9.在广义表的存储结构中，每个结点均包含有 3 个域。
10.在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为
值 域和 子表指针域 。
11.若把整个广义表也看为一个表结点，则该结点的tag域的值为 true或1 、next域的值为 NULL或0 。
三、应用题
1.已知一个稀疏矩阵如图3-11所示:
0 4 0 0 0 0 0
0 0 0 -3 0 0 1
8 0 0 0 0 0 0
0 0 0 5 0 0 0
0 -7 0 0 0 2 0
0 0 0 6 0 0 0
图3-11 具有6行×7列的一个稀疏矩阵
⑴写出它的三元组线性表；
解：((1,2,4),(2,4,-3),(2,7,1),(3,1,8),(4,4,5),(5,,2,-7),(5,6,2),(6,4,6))
⑵给出它的顺序存储表示；
解：
下标12345678...MaxTermsrow(行号)12234556 col(列号)24714264 val(元素值)4-3185-726
⑶给出它的转置矩阵的三元组线性表和顺序存储表示；
解：((1,3,8),(2,1,4),(2,5,-7),(4,2,-3),(4,4,5),(4,6,6),(6,5,2),(7,2,1))
下标1234567row(行号)12 col(列号)31 val(元素值)84 2.画出下列每个广义表的带表头附加结点的链接存储结构图并分别计算出它们的长度和深度。
⑴ A=(())
⑵ B=(a,b,c)
⑶ C=(a,(b,(c)))
⑷ D=((a,b),(c,d))
⑸ E=(a,(b,(c,d)),(e))
⑹ F=((a,(b,(),c),((d)),e)))
解：每小题的长度和深度如下表示。
题号123456长度132231深度213234
第四章 栈和队列
一、应用题
1.设用第二章定义的类型为AlinkList的一维数组MS[MaxSize]建立三个链接堆栈，其中前三个元素的next域用来存储三个栈顶指针，从下标为3的元素起作为空闲元素提供给三个栈共同使用，试编写一个算法把从键盘上输入的n个整数按照下列条件分别进入不同的栈：
⑴若输入的整数x小于60，则进第一个栈；
⑵若输入的整数x大于等于60同时小于100，则进第二个栈；
⑶若输入的整数大于100，则进第三个栈。
解：
void MoreStack(ALinkList MS,int n)
//把从键盘上输入的n个整数按不同条件分别进入到三个不同的链接栈中
{
if(n>MaxSize-3)
cerr<<"存储空间不足!";
exit(1);
int i,x,av;
for(i=0;i<3;i++)
MS[i].next=0//置空栈，即给三个栈顶指针赋0
av=3;//av指向可利用元素的下标，赋初值为3
cout<<"输入"<
cin>>x;
MS[av].data=x;
//按条件把av元素压入不同的栈，即链接到相应栈的栈顶
if(x<60)
Ms[av].next=MS[0].next;
MS[0].next=av;
else if(x>=60&&x<=100)
MS[av].next=MS[1].next;
MS[1].next=av;
else
MS[av].next=MS[2].next;
MS[2].next=av;
//使av指向下一个可利用元素
av++;
}
}
2.编写一个程序，首先调用上题算法，然后分别打印出每个栈中的内容。
解：
#include
#include
const int MaxSize=50;//要至少定义为比输入的整数个数大3
typedef int ElemType;
struct ALNode
ElemType data;
int next;
;
typedef ALNode ALinkList[MaxSize];
void MoreStack(ALinkList MS,int n)
//函数体在此省略
void main()
{
ALinkList a;
int n;
cout<<"从键盘输入的整数个数(1～47):";
cin>>n;
MoreStack(a,n);
for(int i=0;i<3;i++)
{ //依次将每个栈中的元素全部出栈并打印出来
int j=a[i].next;
while(j!=0)
cout< j=a[j].next;
cout<
}
一次输入和运行结果如下：
从键盘上输入的整数个数为(1～47)：12
输入12个整数：
38 64 97 120 78 33 45 214 88 25 143 60
25 45 33 38
60 88 78 97 64
143 214 120
3.已知一个中缀算术表达式为：
3+4/(25-(6+15))*8@
⑴写出对应的后缀算术表达式。
解：3 4 25 6 15 + - /8 * + @
⑵画出在转换成后缀表达式的过程中运算符栈的变化。
解：
步序运算符栈的变化 0# 1#+ 2#- 3#/ 4#* 5#+4.已知一个后缀算术表达式为：
24 8 + 3 * 4 10 7 - * / @
⑴写出对应的中缀算术表达式。
解： (24+8)*3/(4*(10-7))
⑵画出在进行后缀算术表达式求值的过程中数值栈的变化。
解： 24 8 + 3 * 4 10 7 - * / @
5.编写把十进制正整数转换为十六进制数输出的算法。
解：
void Transform(long num)
//把一个正整数num转为一个十六进制数输出
{
Stack a;
InitStack(a);
while(num!=0)
int k=num % 16;
Push(a,k);
num/=16;
while(!StackEmpty(a))
{
int X=Pop(a);
if(x<10)
cout<
switch(x)
cass 10:
cout<<'A';
break;
cass 11:
cout<<'B';
break;
cass 12:
cout<<'C';
break;
cass 13:
cout<<'D';
break;
cass 14:
cout<<'E';
break;
cass 15:
cout<<'F';
}
}
cout<
6.编写把十进制正整数转换为S进制(2≤S≤9)数输出的递归算法，然后若把425转换为六进制数，画出每次递归调用前和返回后系统栈的状态。
解：
只给出递归算法，画图从略。
void Transform(long num,int s)
//把十进制正整数转换为S进制数的递归算法
{
int k;
if(num!=0)
k=num%S;
Transfrom(num/S,S);
cout<
}
7.裴波那契(Fibonacci)数列的定义为：它的第一项和第二项均为1，以后各项为其前两项之和。若裴波那契数列中的第n项用Fid(n)表示，则计算公式为：
试编写计算Fib(n)的递归算法和非递归算法，并分析它们的时间复杂度和空间复杂度。
解：
递归算法为：
long Fib(int n)
if(n==1
非递归算法为
long Fib1(int n)
{
int a,b,c;//C代表当前项，a和b分别代表当前项前面的第2项和第1项
a=b=1; //给a和b赋初值1
if(n==1||n==2)
return 1;
else
for(int i=3;i<=n;i++)
c=a+b; //求出当前项
a=b;//把前面第1项赋给前面第2项
b=c;//把当前项赋给前面第1项
return c;//返回所求的第n项
}
递归算法时间复杂度O（2n）、空间复杂度O（n）
非递归算法时间复杂度O（n）、空间复杂度O（1）
作业三
（（第五章--第七章）
第五章 树和二叉树
一、填空题
1.对于一棵具有n个结点的树,该树中所有结点的度数之和为 n-1 。
2.假定一棵三叉树的结点个数为50，则它的最小深度为 5 ，最大深度为 50 。
3.在一棵高度为h的四叉树中，最多含有 （4h-1）/3 结点。
4.在地棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有 6 个。
5.一棵深度为5的满二叉树中的结点数为 31 个，一棵深度为3的满四叉树中的结点数为
21 个。
6.假定一棵树的广义表示为A(B(C，D(E，F，G)，H(I，J)))，则树中所含的结点数为 10
个，树的深度为 4 个，树的度为 3 。
7.假定一棵树的广义表表示为A(B(C，D(E，F，G)，H(I，J)))，则度为3，2，1，0的结点数分别为 2 、 1 、 1 和 6 个。
8.假定一棵树的广义表示为A(B(C，D(E，F，G)，H(I，J)))，则结点H的双亲结点为 B 个，
孩子结点为 I和J 。
9.在一棵二叉树中，假定双亲结点数为5个，单分支结点数为6个，则叶子结点数为 6 个。
10.对于一棵二叉树，若一个结点的编号为i，则它的左孩子结点的编号为 2i ,右孩子
结点的编号为 2i+1 ，双亲结点编号为 i/2 。
11.在一棵二叉树中，第5层上的结点数最多为 16 。
12.假定一棵二叉树的结点数为18，则它的最小深度为 5 ，最大深度为 18 。
13.一棵二叉树的广义表表示为a(b(e,d),e(f(,g))),则e结点的双亲结点为 a ，左孩
子结点为 f ，右孩子结点为 空 。
14.一棵二叉树的广义表表示为a(b(e,d),e(f(,g))),它含有双亲结点 2 个，单分支结
点 2 个，叶子结点 3 个。
15.对于一棵含有40个结点的理想平衡树，它的高度为 6 。
16.假一定一棵二叉树顺序存储在一维数组a中，则a[i]元素的左孩子元素为 a[2i] ,右
孩子元素为 a[2i+1] ，双亲元素(i-1)为 a[i/2] 。
17.假定一棵二叉树顺序存储在一维数组a中，但让编号为1的结点存入a[0]元素中，
让编号为2的结点存入a[1]元素中，其余类推，则编号为i结点的左孩子结点对应的
存储位置为 2i-1 ，若编号为i结点的存储位置用j表示，则其左孩子结点对
应的存储位置为 2j+1 。
18.若对一棵二叉树从0开始进行结点编号，并按此编号把它顺序存储到一维数组a中，
即编号为0的结点存储到a[0]中，其余类推，则a[i]元素的左孩子元素为 a[2i+1] ，
右孩子元素为 a[2i+2] ，双亲元素(i->0)为 a[(i-1)/2] 。
19.对于一棵具有n个结点的二叉树，对应二叉链接表中指针总数为 2n 个，其中
n-1 个用于指向孩子结点， n+1 个指针空闲着。
20.一棵二叉树广义表表示为a(b(d(,h)),c(e,f(g,i(k)))),该树的结点数为 10 个，
深度为 5 。
21.在一棵高度为5的理想平衡树中，最少含有 16 个结点，最多含有 31 个结点。
22.在一棵高度为h的理想平衡树中，最少含有 2h-1 个结点，最多含有 2h-1个结点。
23.假定一棵二叉树广义表表示为a(b(c),d(e,f)),则对它进行的先序遍历结果为 a b c d e f,中序遍历结果为 c b a e d f,后序遍历结果为 c b e f d a,按层遍历结果为 a b
d c e f。
24.假定一棵普通树的广义表表示为a(b((e),c(f(h,i,j),g),d),则先根遍历结果为 a b e c f h i j g d,按层遍历结果为 a b c d e f g h i j。
二、应用题
1.已知一棵具有n个结点的完全二叉树被顺序存储于一维数组的A[1]～A[n]元素中，试编写一个算法打印出编号为i的结点的双亲和所有孩子。
解：
void Request(int a[],int n,int i)
//从数组A中打印出编号为i的结点的双亲和孩子
{
if(i>n)
cerr<<"编号为"<
cout<<"current element:"< int j=i/2; //下标为j的结点是下标为i结点的双亲
if(j>0)
cout<<"parent:"< else
cout<<"树根结点没有双亲结点!"<
else if(2*i==n)
cout<<"left child:"< cout<<"no right child!"<
else
cout<<"no children!"<
2.编写一算法，求出一棵二叉树中所有结点数和叶子结点，假定分别用变参C1和C2统计所有结点数和叶子结点数，初值均为0。
解：
void Count(BTreeNode* BT,int& C1,int& C2)
//分别统计出二叉树中所有结点数和叶子结点数
{
if(BT!=NULL)
C1++;//统计所有结点
if(BT->left==NULL&&BT->right==NULL)
C2++; //统计叶子结点数
Count(BT->left,C1,C2);
Count(BT->right,C1,C2);
}
12.对于图5-16所示的树：
? 写出先根遍历得到的结点序列；a b e c f g k d h I l m j
? 写出按层遍历得到的结点序列；a b c d e f g h I j k l m
? 画出转换后得到的二叉树和二叉链表。
解： 略
第六章 二叉树的应用
一、单选题
1.从二叉搜索树中查找一个元素时，其时间复杂度大致为 C 。
A O(n) B O(1) C O(log2n) D O(n2)
2.向二叉搜索树中插入一个元素时，其时间复杂度大致为 B 。
A O(1) B O(log2n) C O(n) D O(nlog2n)
3.根据n个元素建立一棵二叉搜索树时，其时间复杂度大致为 D 。
A O(n) B O(log2n) C O(n2) D O(nlog2n)
4.从堆中删除一个元素的时间复杂度为 C 。
A O(1) B O(n) C O(log2n) D O(nlog2n)
5.向堆中插入一个元素的时间复杂度为 A 。
A O(log2n) B O(n) C O(1) D O(nlog2n)
6.权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为 D 。
A 24 B 48 C 72 D 53
二、填空题
1.在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定 小于 该结点的值，右子树上所有结点的值一定 大于 该结点的值。
2.对一棵二叉搜索树进行中序遍历时，得到结点序列是一个 有序序列 。
3.从一棵二叉搜索树中查找一个元素时，若元素的值等于根结点的值，则表明 查找成功 ，
若元素的值小于根结点的值，则继续向 左子树 查找，若元素的值大于根结点的值，则继续向 右子树 查找。
4.在一个堆的顺序存储中，若一个元素的下标为i，则它的左孩子元素的下标为 2i+1 ，
右孩子元素的下标为 2i+2 。
5.在一个小根堆中，堆顶结点的值是所有结点中的 最小值 ，在一个大根堆中，堆顶
结点的值是所有结点中的 最大值 。
6.当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层 向上 调整，直到被
调整到 堆顶 位置为止。
7.当从一个小根堆中删除一个元素时，需要把 堆尾 元素填补到 堆顶 位置，然后再按条件把它逐层 向下 调整。
8.在哈夫曼编码中，若编码长度只允许小于等于4，则除了已对两个字符编码为0和10外，
还可以最多对 4 个字符编码。
三、应用题
1.已知一组元素(46,25,78,62,12,37,70,29)，画出按元素排列顺序输入生成的一棵二叉树。
解：
广义表表示为：46(25(12,37(29)),78(62(,70)))
46
/ /
25 78
/ / /
12 37 62
/ /
29 70
2.已知一棵二叉排序树如图6-11所示，若从中依次删除72,12,49,28结点，试分别画出每删除一个结点后得到的二叉排序树。
解：
广义表表示：
删除72：28(12(,16),49(34(30),63))
删除12：28(16,49(34(30),63))
删除49：28(16,34(30,63))
删除28：16(,34(30,63))
3.编写一个非递归算法，求出二叉排序树中的关键字最大的元素。
解：
ElemType FindMax(BTreeNode* BST)
//从二叉排序树中返回关键字最大的元素
{
if(BST==NULL)
cerr<<"不能在空树上查找最大值!"<
BTreeNode* t=BST;
while(t->right!=NULL)
t=t->right;
return t->data;
}
4.已知一个堆中插入线性表（38，64，52，15，73，40，55，26，12）中的每个元素，请以线性表的形式给出每插入一个元素后堆的状态。
解：每插入一个元素后堆的状态用线性表表示如下：
解：
(1) (38)
(2) (38,64)
(3) (38,64,52)
(4) (15,38,52,64)
(5) (15,38,52,64,73)
(6) (15,38,40,64,73,52)
(7) (15,38,40,64,73,52,48)
(8) (15,38,40,55,73,52,48,64)
(9) (15,26,40,38,73,52,48,64,55)
(10) (12,15,40,38,26,52,48,64,55,73)
5.已知一个堆为（12，15，40，38，26，52，48，64），若需要从堆中依次删除四个元素，请给出每删除一个元素后堆的状态。
解：
(1) (15,26,40,38,64,52,48)
(2) (26,38,40,48,64,52)
(3) (38,48,40,52,64)
(4) (40,48,64,52)
6. 有七个带权结点，其权值分别为3，7，8，2，6，10，14，试以它们为叶子结点构造一棵哈夫曼树，并计算出带权路径长度WPL
解：
得到的哈夫曼树用二叉树广义表表示为：
50(21(10,11(5(2,3),6)),29(14,15(7,8)))
WPL=(2+3)*4+（6+7+8）*3+（10+14）*2=131
7．在一份电文中使用五种字符：a，b，c，d，e，它们的出现频率依次为4，7，5，2，9，
试画出对应的哈弗曼树，求出每个字符的哈弗曼编码，并求出传说电文的总长度。
解：
电文的总长度为：
（2+4）*3+(5+7+9)*2=60
第七章 图
一、填空题
1.在一个图中，所有顶点的读数之和等于所有边数的 2 倍。
2.在一个具有n个顶点的无向完全图中，包含有 n(n-1)/2 条边，在一个具有n个顶点的所有向完全图中，包含有 n(n-1) 条边。
3.在一个具有n个顶点的无向图中，要连通所有顶点则至少需要 n-1 条边。
4.表示图的三种存储结构为 邻接矩阵 、 邻接表 和 边集数组 。
5.对于一个具有n个顶点的图，若采用邻接矩阵表示，则其矩阵大小为 n2。
6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别为 e 和 2e 条。
7.在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该点的所有出边 和
入边 结点。
8.对于一个具有n个顶点和e条边的有向图和无向图，若采用边集数组表示，则存于数组中的边数分别为 e 和 e 条。
9.对于一个具有n个顶点和e条边的无向图，当分别采用邻接矩阵，邻接表和边集数组表示时，求任一顶点度数的时间复杂度依次为 O(n) 、O(e/n) 和O(e)。
10.假定一个图具有n个顶点和e条边，则采用邻接矩阵、邻接表和边集数组表示时，其相应的空间复杂度分别为O(n2)、O(n+e)和O(e)。
11.对用邻接矩阵表示的图进行任一种遍历时，其时间复杂度为O(n2),对用邻接表
表示的图进行任一遍历时，其时间复杂度为O(e) 。
12.对于图7-1(a)所示的无向图，假定用邻接矩阵表示，则从顶点v0开始进行深度优先搜索遍历得到的顶点序列为0，1，4，2，5，3；从顶点v0开始进行广度优先搜索遍历得到的顶点序列为0，1，2，3，4，5。
13.对于图7-1(b)所示的有向图，假定用邻接矩阵表示，则从顶点v0开始进行深度优先搜索遍历得到的顶点序列为A，B，C，D，E；从顶点v0开始进行广度优先搜索遍历得到的顶点序列为A，B，C，E，D。
14.对于一个有n个顶点和e条边的连通图，其生成树中的对点数和边数分别为 n 和n-1。
15.对于图7-5(a)所示的带权图，其最小生成树的权为 22 。
16.对于图7-5(a)所示的图，若从顶点v0出发，则按照普里姆算法生成的最小生成树中，依次得到的各条边为(0,1)5,(1,3)3,(3,2)6,(1,4)8。
17.对于图7-5(a)所示的图，若按照克鲁斯卡算法产生最小生成树，则得到的各条边依次为(1,3)3,(0,1)5,(2,3)6,(1,4)8 。
18.假定用一给数组d[n]存储一个AOV网中用于拓朴排序的顶点入度，则值为0的元素被链接成为一个 栈 。
二、应用题
1.对于图7-25(a)和(b)，按下列条件试分别写出从顶点v0出发按深度优先搜索遍历得
到的顶点序列和按广度优先搜索遍历得到的顶点序列。
? 假定它们均采用邻接矩阵表示；
? 假定它们均采用邻接表表示，并且假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。
解：
(1) 采用邻接矩阵表示得到的顶点序列如下表所示：
图深度优先序列广度优先序列(a)0,1,2,8,3,4,5,6,7,90,1,4,2,7,3,8,6,5,9(b)0,1,2,5,8,4,7,3,60,1,3,4,2,6,7,5,8(2)采用邻接表表示得到的顶点序列如下表所示：
图深度优先序列广度优先序列(a)0,4,3,8,9,5,6,7,1,20,4,1,3,7,2,8,6,9,5(b)0,4,7,5,8,3,6,1,20,4,3,1,7,5,6,2,8
2.假定采用邻接矩阵表示，编写出进行深度优先遍历的非递归算法。
解：
void dfss(adjmatrix GA,int i,int n)
{
stack s;
Initstack(s);
push(s,i);
while(!StackEmpty(s)){
int k=pos(s);
if(!visited[k])
cout<
for(int j=0;j
push(s,j);
}
}
3.对于图7-27(图略)，试给出一种拓朴序列，若在它的邻接表存储结构中，每个顶点邻接表中的边结点都是按照终点序号从大到小链接的，则按此给出唯一一种拓朴序列。
解： 唯一一种拓朴序列：1,4,0,2,3,5,7,6,8,9
作业四
（第八章--第九章）
第八章查找
一、填空题
1.以顺序查找方法从长度为n的线性表中查找一个元素时，平均查找长度为(n+1)/2,时间复杂度为O(n) 。
2.以二分查找方法从长度为n的线性表中查找一个元素时，平均查找长度小于等于
log2(n+1) ，时间复杂度为O(log2n)。
3.以二分查找方法从长度为12的有序表中查找一个元素时，平均查找长度为37/12。
4.以二分查找方法查找一个线性表时，此线性表必须是顺序存储的有序表。
5.从有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素时，其查找长度
分别为 1 和 3 。
6.对于二分查找所对应的判定树，它即是一棵二叉搜索树，又是一棵理想平衡树 。
7.假守对长度n=50的有序表进行二分查找，则对应的判断树高度为6 ，判定树前5层的结点数
为 31 ，最后一层的结点数为 19 。
8.在索引表中，每个索引向至少包含有 索引值 域和 子表开始 域这两项。
9.假定一个线性表为(12,23,74,55,63,40,82,36),若按key%3条件进行划分，使得同一
余数的元素成为一个子表，则得到的三个子表分别为(12,63,36)、(55,40,82)和(23,74)。
10.假定一个线性表为"abcd","baabd","beef","cfg","ahij","bkwte","ccdt","aayb"),
若按照字符串的第一个字母进行划分，使得同一个字母被划分在一个子表中，则得到的a,b,c三个子表的长度分别为 3 、 3 和 2 。
11.在索引表中，若一个索引项对应主表中的一条记录，则称此索引为 稠密 索引，若对应主表中若干条记录，则称此索引为 稀疏 索引。
12.在稀疏索引表上进行二分查找时，若当前查找区间为空，则不是返回-1表示查找失败，而是返回该区间的 下限值(即low值) 。
13.假定长度n=100的线性表进行索引查找，并假定每个子表的长度为n1/2，则进行索引查找的平均查找长度为 11 ，时间复杂度为 O(n1/2)。
14.若对长度n=1000的线性表进行二级索引存储，每级索引表中的索引项是下一级20个记录的索引,则一级索引表的长度为 500 ,二级索引表的长度为 25 .
15.在线性表的 散列 存储中,无常找到一个元素的前驱或后继元素.
16.在线性表的 链接 存储中,对每一个元素只能采用顺序查找.
17.假定对线性表(38,25,74,52,48)进行散列存储,采用H(K)=K%7作为散列函数,若分别采用线性探查法和链接法处理冲突,则对各自散列表进行查找的平均查找长度分别为 2 和 4/3 .
18.假定要对长度n=100的线性表进行散列存储,并采用链接法处理冲突,则对于长度m=20的散列表,每个散列地址的单链表的长度分别为 5 .
19.在线性表的散列存储中,装填因子α又称为装填系数,若用m表示散列表的长度,n表示待散列存储的元素的个数,则α等于 n/m 。
20.在线性表的散列存储中,处理冲突有 开放定址法 和 链接法 两种方法。
21.对于线性表(18,25,63,50,42,32,90)进行散列存储时,若选用H(K)=K%9作为散列函数,则散列地址为0的元素有 3 个,散列地址为5的元素有 2 个。
22.对于一个含有N个关键字的m阶B_树,其最小高度为logm(N+1),最大高度为
1+?log?m/2?(N+1/2)?。
23.已知一棵3阶B_树中含有50个关键字，则该树的最小高度为 4 ，最大高度为 5 。
24.在一棵9阶的B_树上中，每个非树根结点的关键字数目最少为 4 个，最多为 8 个。
25.在一棵m阶B_树上，每个非树根结点的关健字数目最小为m/2-1 个，最多为 m-1 个，其子树目最小为 m/2，最多为 m 。
26.在一棵B_阶树中，所有叶子结点都处在 同一层 上，所有叶子结点中空指针等于所有 关键字 总数加1。
27.在对m阶B_树插入元素的过程中，每向一个结点插入一个索引项(叶子结点中的索引项为关键字和空指针)后，若该结点的索引项数等于 m 个，则必须把它分裂为 两 个结点。
28.在从m阶的B_树删除元素的过程中，当一个结点被删除掉一个索引项后，所含索引项等于m/2-2个，并且它的左右兄弟结点中的索引项数均等于m/2-1个，则必须进行结点合并。
29.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度 增加1 。
30.从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树比原树的高度 减少1 。
二、应用题
1、假定查找有序表A[25]中每一元素的概率相等，试分别求出进行顺序、二分和分块（假定被分为5块，每块5个元素）查找每一元素的平均查找长度。
解：
顺序查找：ASL=12.5 二分查找: ASL=99/25 分块查找: ASL=6
2. 编写一个非递归算法，在稀疏有序索引表中二分查找出给定值K所对应的索引项，即索引值刚好大于等于K的索引项，返回该索引项的start域的值，若查找失败则返回-1。
解：
int Binsch(indexlist B, int m, IndexKeyType K)
{
int low=0, high=m-1;
while(low<=high)
int mid=(low+high)/2;
if(K==B[mid].index)
return B[mid].start;
else if(K
else
low=mid+1;
if(low
}
3. 假定一个待散列存储的线性表为(32,75,29,63,48,94,25,46,18,70)，散列地址空间为HT[13]，若采用除留余数法构造散列函数和线性探查法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。
解：
每一元素的散列地址为：
h(32)=32%13=6 h(75)=75%13=10 h(29)=29%13=3
h(63)=63%13=11 h(48)=48%13=9 h(94)=94%13=3 冲突
h1(94)=h(94)+1=4 h(25)=25%13=12 h(46)=46%13=7
h(18)=18%13=5 h(70)=70%13=5 冲突 h1(70)=h(70)+1=6 冲突
h2(70)=7 冲突 h3(70)=8
平均查找长度ASL=(8+2+4)/10=1.4
散列表Ht[13]为：
0 12345678910111229941832467048756325
4. 假定一个待散列存储的线性表为(32,75,29,63,48,94,25,36,18,70)，散列地址空间为HT[11]，若采用除留余数法构造散列函数和链接法处理冲突，试求出每一元素的散列地址，画出最后得到的散列表，求出平均查找长度。
解：平均查找长度ASL=(7*1+3*2)/10=1.3
5. 已知一组关键字为(26,38,12,45,73,64,30,56)，试依次插入关键字生成一棵3阶的B_树，画出每次插入一个关键字后B_树的结构。
第九章排序
一、填空题
1.每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做 插入 排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做 选择排序。
2每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就交换它们的位置，此种排序方法叫做交换排序，每次使两个相邻的有序表合并成一个有序表的排序方法叫做二路归并排序。
3在直接选择排序中，记录比较次数的时间复杂度为 O(n2)，记录移动次数的时间复
杂度为 O(n) 。
4在堆排序的过程中，对n个记录建立初始堆需要进行[n/2]次筛运算，由初始堆到堆排序结束，需要对树根结点进行n-1次筛运算。
5在堆排序过程中，对任一分支结点进行筛运算的时间复杂度为O(log2n),整个堆排序过程的时间复杂度为O(nlog2n)。
6假定一组的记录的排序码为(46,79,56,38,40,84)，则利用堆排序方法建立的初始堆为(84,79,56,38,40,46)。
7快速排序在平均情况下的时间复杂度为O(nlog2n)，在最坏情况下的时间复杂度为O(n2)。
8快速排序在平均情况下的空间复杂度为O(log2n)，在最坏情况下的空间复杂度为O(n) 。
9在快速排序方法中，进行每次划分时，是从当前待排序空间的 两端 向 中间 依次查找出处于逆序的元素并交换之,最后将基准元素交换到一个确定位置,从而以该位置把当前区间划分为前后两个子区间。
10假定一组记录的排序码为(46,79,56,38,40,80)，对其进行快速排序的一次划分的结果为[38 40]46[56 79 84]。
11假定一组记录的排序码为(46,79,56,38,40,80)，对其进行快速排序过程中，对应二叉树的深度为4 ，分支点结点数为 4 。
12在二路归并排中，对n个记录进行归并的趟数为 [log2n] 。
13在归并排序中，进行每趟归并的时间复杂度为O(n)，整个排序过程的时间复杂度为O(nlog2n)，空间复杂度为 O(n) 。
14对20个记录进行归并排序时，共需要进行 5 趟归并，在第三趟归并时是把长度为 4 的有序表两两归并为长度为 8 的有序表。
15假定一组记录的排序码为(46,79,56,38,40,80)，对其进行归并排序的过程中，第二趟归并后的结果为[38 46 56 79][40 84]。
二、应用题
1. 给出每一种排序算法的时间复杂度、空间复杂度及稳定性。
解：排序方法 时间复杂度 空间复杂度 稳定性
快速 O(nlog2n) O(log2n) 不稳定
堆 O(nlog2n) O(1) 不稳定
归并 O(nlog2n) O(n) 稳定
直接插入 O(n2) O(1) 稳定
直接选择 O(n2) O(1) 不稳定
气泡 O(n2) O(1) 稳定
2. 已知一组元素的排序码为
(46，74，16，53，14，26，40，38，86，65，27，34)
(1)利用直接插入排序的方法写出每次向前面有序表插入一个元素后的排列结果。（略）
(2) 利用直接选择排序方法写出每次选择和交换后的排列结果。（略）
(3) 利用堆排序的方法写出在构成初始堆和利用堆排序的过程中，每次筛运算后的排列结果，并画出初始堆所对应的完全二叉树。
解：
在构成初始堆的过程中，每次筛运算后的数据排列情况为：
0 1 2 3 4 5 6 7 8 9 10 11
(0) 46 74 16 53 14 26 40 38 86 65 27 34
(1) 46 74 16 53 14 34 40 38 86 65 27 26
(2) 46 74 16 53 65 34 40 38 86 14 27 26
(3) 46 74 16 86 65 34 40 38 53 14 27 26
(4) 46 74 40 86 65 34 16 38 53 14 27 26
(5) 46 86 40 74 65 34 16 38 53 14 27 26
(6) 86 74 40 53 65 34 16 38 46 14 27 26
在利用堆排序的过程中，每次筛运算后的数据排列情况为：
0 1 2 3 4 5 6 7 8 9 10 11
(0) 86 74 40 53 65 34 16 38 46 14 27 26
(1) 74 65 40 53 27 34 16 38 46 14 26 86
(2) 65 53 40 46 27 34 16 38 26 14 74 86
(3) 53 46 40 38 27 34 16 14 26 65 74 86
(4) 46 38 40 26 27 34 16 14 53 65 74 86
(5) 40 38 34 26 27 14 16 46 53 65 74 86
(6) 38 27 34 26 16 14 40 46 53 65 74 86
(7) 34 27 14 26 16 38 40 46 53 65 74 86
(8) 27 26 14 16 34 38 40 46 53 65 74 86
(9) 26 16 14 27 34 38 40 46 53 65 74 86
(10)16 14 26 27 34 38 40 46 53 65 74 86
(11)14 16 26 27 34 38 40 46 53 65 74 86
(4) 利用快速排序的方法写出每一层划分后的排列结果，并画出由此快速排序得到的二叉搜索树。
解：
0 1 2 3 4 5 6 7 8 9 10 11
(0) 46 74 16 53 14 26 40 38 86 65 27 34
(1) [38 34 16 27 14 26 40] 46 [86 65 53 74]
(2) [26 34 16 27 14] 38 40 46 [74 65 53] 86
(3) [16 14] 26 [27 34] 38 40 46 [53 65] 74 86
(4) 14 16 26 27 34 38 40 46 53 65 74 86
(5) 利用归并排序的方法写出每一趟二路归并排序后的结果。
解：
0 1 2 3 4 5 6 7 8 9 10 11
(0) [46] [74] [16] [53] [14] [26] [40] [38] [86] [65] [27] [34]
(1) [46 74] [16 53] [14 26] [38 40] [65 86] [27 34]
(2) [16 46 53 74] [14 26 38 40] [27 34 65 86]
(3) [14 16 26 38 40 46 53 74] [27 34 65 86]
(4) 14 16 26 27 34 38 40 46 53 65 74 86
来源：网络整理 免责声明：本文仅限学习分享，如产生版权问题，请联系我们及时删除。
相关文章：
《植物学》形成性考核册1-4作业04-30
《植物生产技术》形考册04-30
《水利工程测量》形成性考核册04-30
《水力学》形成性考核册（暂无答案）04-30
《文秘管理与应用写作》形成性考核册104-30
《文秘管理与应用写作》形成性考核册答案04-30
《文秘管理与应用写作》形考作业104-30
《文论专题》形成性考核册04-30