一、是非题(下列各题，你认为正确的，请在题干的括号内打“√”，错的打“×”。每题1分，共15分）
1、 数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三个方面...............( y)
2、线性表中的每个结点最多只有一个前驱和一个后继。......( y)
3、从本质上看，文件是一种非线性结构。..................(n )
4、线性的数据结构可以顺序存储，也可以链接存储。非线性的数据结构只能链接存储。.......................( n)
5、栈和队列逻辑上都是线性表。..........................( y)
6、单链表从任何一个结点出发，都能访问到所有结点........(n )
7、单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。.................................................(? )
8、对某一确定的可利用空间表，给定一串内存请求，若采用最佳适配和首次适配这两
种方法之中的一种能满足该串请求，则也一定能用另一种方法满足该串请求。(n )
9、多维数组是向量的推广。..............................(y? )
10、设串S=a1a2...ai...aj...an,则有ord(ai)>ord(aj)。....( n)
11、设串S的长度为n,则S的子串个数为n(n+1)/2。...........(n )
12、一般树和二叉树的结点数目都可以为0。................( n)
13、在拓朴排序序列中，任意两个相继结点Vi和Vj都存在从Vi到Vj的路径。(n )
14、网络的最小代价生成树是唯一的。.....................(n )
15、磁带是顺序存取的外存储设备。.......................(y? )
二、填空题(每空1分，共10分）
1、在树结构里，有且仅有一个结点没有前驱，称为根。非根结点有且仅有一个( 前驱),且存在一条从根到该结点的( 路径)。
2、评价数据结构的两条基本标准是：(存贮需要量 )和(运算的时间效率 )。
3、对于顺序存储的栈，因为栈的空间是有限的，在进行(push )运算时，可能发生栈的上溢，在进行( pop)运算时，可能发生栈的下溢。
4、对于单链表形式的队列，其空队列的F指针和R指针都等于(null )。
5、若S1=‘linked￡st",S2="ring",则S1//S2=( linked￡string)。
6、设根结点的层数为0，定义树的高度为树中层数最大的结点的层数加1。则高度为k的二叉树具有的结点数目，最少为(k ),最多为((2^k)-1 )。
三、单选题(在本题的每一小题的备选答案中，只有一个答案是正确的，请把你认为正确答案的题号，填入题干的括号内。多选不给分。每题3分，共9分)
1、对于顺序存储的队列，存储空间大小为n，头指针为F，尾指针为R。若在逻辑上看一个环，则队列中元素的个数为......................( d)
⑴.R-F ⑵.n+R-F ⑶.(R-F+1)mod n ⑷.(n+
R-F）mod n
2、n个记录直接插入排序所需的记录最小移动次数是.......(a )
⑴.2(n-1) ⑵.2n ⑶.(n+3)(n-2)/2 ⑷.n2/2
3、现有一“遗传”关系：设x是y的父亲，则x可以把它的属性遗传给y。表示该遗传关系最适合的数据结构为..............................b
⑴.向量 ⑵.树 ⑶.图 ⑷.二叉树
四、简单应用题(第1题6分，其它题每题3分，共18分）
1、已知稀疏矩阵如下：
⑴请写出该稀疏矩阵顺序存储的带辅助行向量的二元组表示。
⑵请写出该稀疏矩阵链接存储的带行指针向量的单链表示。
解：
2、在包含n个关键码的线性表里进行顺序查找，若查找第i个关键码的概率为pi，pi如下分布：p1=1/2,p2=1/4,......,pn-1=1/2n-1,pn=1/2n。求成功检索的平均比较次数。
解：
3、设根结点的层数为0，定义树的高度为树中层数最大的结点的层数加1，试问高度为k≥1、非叶结点的度数等于1的树有多少棵？
解：
4、给出下列二叉树的前序序列。
解：
5、设二叉树t的对称序序列为BADCE，后序序列为BDECA，请给出二叉树。
解：
五、综合题(每题4分，共16分)
1、假设有如下关键码及其散列函数值：
key ABCD ABDC ACBD ACDB BDAC BACD CADB CBDA
h(key) 4 4 0 1 2 3 6 5
基本存储区编址为0--7，请用建立分离的同义词子表的方法解决碰撞问题，画出其存储图式。
解：
2、下面列举的是常用的排序方法：直接插入排序，二分法插入排序，起泡排序，快速排序，直接选择排序，堆排序，归并排序。试问，哪些排序方法是稳定的？
解：
3、设有50个值不同的元素存于内存一片连续单元中，若用顺序选择的方法，选出这50个元素的最大值和最小值则至少需要97次比较。请给出另一种选出最大值和最小值的方法，其比较次数一定少于97次，说明该方法的操作过程和比较次数。
解：
4、快速排序在什么情况下，所需记录之关键码的比较次数为最多？此时记录之关键码比较次数应为多少？
解：
六、算法设计题(第1、2题，每题8分，第3题6分，第4题10分，共32分)
1、双链表结点类型和变量说明如下：
TYPE pointer=↑node;
node=RECORD
info:datatype;
llink,rlink:pointer
END;
double=RECORD
head,rear:pointer
END;
VAR DL:double;
p,q:pointer;
设DL.head和DL.rear已分别指向该双链表的头结点和尾结点。下述算法应实现的操作为：在信息值为x0的结点(设该结点一定存在)之后，插入信息值为x1的新结点。试填充算法中的空框，使该算法正确。
⑴[置初值]
P←DL.head
⑵[查找]
循环 当P↑info≠x0时，反复执行
⑶[准备结点］
new(q)；q↑.info←x1
⑷[插入］
若P=DL.rea
r
则q↑.rlinknil；q↑.llinkP；
点击查看更多福建招生考试网信息(https://www.doczj.com/doc/3e9900170.html,)
数据结构练习题
第一章绪论
一、单选题
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||n==1) return 1;
Else return n*f(n-1);
}
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 的类型相同。
1
5.从一维数组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)。
第二章线性表
一、（答案）
⑴解：(79,62,34,57,26,48)
⑵解：(26,34,48,57,62,79)
⑶解：(48,56,57,62,79,34)
⑷解：(56,57,79,34)
⑸解：(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))
⑵给出它的顺序存储表示；
解：
下标 1 2 3 4 5 6 7 8 ... MaxTerms
row(行号) 1 2 2 3 4 5 5 6
col(列号) 2 4 7 1 4 2 6 4
val(元素值) 4 -3 1 8 5 -7 2 6
⑶给出它的转置矩阵的三元组线性表和顺序存储表示；
解：
((1,3,8),(2,1,4),(2,5,-7),(4,2,-3),(4,4,5),(4,6,6),(6,5,2),(7,2,1))
解：下标 1 2 3 4 5 6 7
row(行号) 1 2
col(列号) 3 1
val(元素值) 8 4
3.画出下列每个广义表的带表头附加结点的链接存储结构图并分别计算出它们的长度和深度。
⑴ 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)))
解：每小题的长度和深度如下表示。
题号 1 2 3 4 5 6
长度 1 3 2 2 3 1
深度 2 1 3 2 3 4
第四章 栈和队列
一、应用题
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<<"输入"<
它赋给av元素的值域
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<
}
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 * + @
⑵画出在转换成后缀表达式的过程中运算符栈的变化。
解：略
4.已知一个后缀算术表达式为：
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)表示，则计算公式为：
1 (n=1或n=2)
Fib(n)= Fib(n-1)+Fib(n-2) (n>=2)
试编写计算Fib(n)的递归算法和非递归算法，并分析它们的时间复杂度和空间复杂度。
解：
递归算法为：
long Fib(int n)
{
if(n==1||n==2) //终止递归条件
return 1;
else
return Fib(n-1)+Fib(n-2);
}
非递归算法为
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:"<
//下标为j的结点是下标为i结点的双亲
if(j>0)
cout<<"parent:"<
cout<<"树根结点没有双亲结点!"<
else if(2*i==n){
cout<<"left 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)，画出按元素排列顺序输入生成的一棵二叉树。
2.已知一棵二叉排序树如图6-11所示，若从中依次删除72,12,49,28结点，试分别画出每删除一个结点后得到的二叉排序树。
28
/ \
12 49
\ / \
16 34 72
/ /
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.~7. 解略