第一章绪论 一、单选题
1. 一个数组元素a[i]与 A 2.对于两个函数，若函数名相同，但只是A *(a+i) B a+i C *a+i 的表示等价。D &a+i
C 不同则不是重载函数。
3.A 参数类型 B 参数个数 C 函数类型B 若需要利用形参直接访问实参，则应把形参变量说明为 参数。 4.A
下面程序段的复杂度为指针 B 引用 C 值 C 。 for(int i=0;i 5. for(int i=1;i<=n;i++) 执行下面程序段时，执行S语句的次数为 D 。 S; for(int j=1; j<=i;j++) A n2 B n2/2 C n(n+1) D n(n+1)/2 6. 下面算法的时间复杂度为 B 。 if(n==0||n==1) return 1; int f(unsigned int n){ 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.iostream.h 当需要进行标准头文件，I/O当需要进行文件操作时，则应在程序文件中包含I/O操作时，则应在 程序文件中包含 fstream.h 头文件。 9.rand()! 在包含有10.一个记录能够产生 stdlib.h r理论上占有的存储空间的大小等于所有域0-20头文之间的一个随机数。件的程序文件中 ，使用 的 长度之和 ，实际上占有的存储空间的大小即记录长度为 sizeof(r) 。 11.sizeof(a) 一个数组，下标为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 1/7 语句的执行次数为n(n+1)/2，该程序段的时间复杂度为 O(n2) 。 while(++i<=n){ int i=0,s=0; int p=1; for(int j=1;j<=i;j++) P*=j; 17.一个算法的时间复杂度为} s=s+p; (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。 cc=0); Quadratic InitQuadratic(float aa=0,float bb=0,float 解 { Quadratic InitQuadratic(float aa,float bb,float cc) q.a=aa; Quadratic q; 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; return 0; else } ⑸ 按照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) cout<<\ else cout< if(q.c) cout<<\ else cout< ⑴ int prime(int n) int i=1; { int x=(int)sqrt(n); while(++i<=x) if(i>x) return 1; if(n%i==0)break; 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++) s+=p; p*=j; } return s; } 解： 计算∑i!的值，时间复杂度为O(n2) ⑷ int fun(int n) { int i=1,s=1; s+=++i; 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; i=x; while(inp>>x){ int x; c[i]++; } } 解：利用数组c[10]中的每个元素c[i]对应统计出inp所联系的整数文件中个位值同为i的整数个数，时间复杂度为O(n) ⑹ void mtable(int n) { for(int i=1;i<=n;i++){ 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 for(int j=0;j 使数组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(j=0;j } c[i][j]+=a[i][k]*b[k][j]; 解： 矩阵相乘，即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<<\ } exit(1); ElemType x; int k=0; x=L.list[0]; for(int i=1;i if(y ⑵ 从线性表中删除第i个元素并由函数返回。 解：int Deletel(List& L,int i) { //从线性表中删除第i个元素并由函数返回 cerr<<\if(i<1||i>L.size){ exit(1); ElemType x; } x=L.list[i-1]; L.list[j]=L.list[j+1]; for(int j=i-1;j return x; ⑶ 向线性表中第i个元素位置插入一个元素。 解：void Inser1(List& L,int i,ElemType x) //向线性表中第i个元素位置插入一个元素 { if(i<1||i>L.size+1){ cerr<<\ } exit(1); if(L.size==MaxSize) { cerr<<\ exit(1); 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; if(L.list[i]==x){ while(i 3/7 L.list[j-1]=L.list[j]; } L.size--; i++; else } 4.对于结点类型为LNode的单链接表,编写出下列每个算法。 ⑴ 将一个单链接表按逆序链接,即若原单链表中存储元素的次序为a1,a2,...,an,则 逆序链接后变为an,an-1,...a1。 解：void Contrary(LNode*&HL) { //将一个单多办实事有按逆序链接 LNode*p=HL;//p指向待逆序的第一个结点，初始指向原表头结点 //HL 仍为逆序后的表头指针，禄始值为空HL=NULL; { //while(p!=NULL) LNode*q=p; //q把原单链表中的结点依次进行逆序链接 p=p->next; //p指向待处理的结点 //将q结点插入到已陈序单链表的表头指向下一个待逆序的结点 HL=q; q->next=HL; } } ⑵ 删除单链表中的第i个结点。 解：void Delete1(LNode*&HL,int i) { //删除单链表中的第i个结点 if(i<1||HL==NULL){ exit(1); cerr<<\ } LNode*ap,*cp; ap=NULL;cp=HL; //cp指向当前结点，ap指向其前驱结点 while(cp!=NULL) int j=1; break; //cpif(j==i) else{ // 继续向后寻找结点即为第 i个结点 j++; cp=cp->next; ap=cp; } if(cp==NULL){ excerr<<\ it(1); } if(ap==NULL) HL=HL->next; ap->next=cp->next; else delete cp; } ⑶ 从单链表中查找出所有元素的最大值，该值由函数返回，若单链表为空，则显示出错信息并停止运行。 解：ElemType MaxValue(LNode*HL) //从单链表中查找出所有元素的最大值，该值由函数返回 { if(HL==NULL){ cerr<<\ exit(1); } ElemType max=HL->data; LNode*p=HL->next; if(max p=p->next; return max; } } ⑷ 统计出单链表中结点的值等于给定值x的结点数。 解：int Count(LNode*HL,ElemType x) //统计出单链表中结点的值等于给定值x的结点数 int n=0; { if(HL->data==x) n++; while(HL!=NULL){ } HL=HL->next; return n; } 第三章 稀疏距阵和广义表 一、单选题 1.在稀疏矩阵的带行指针指向量的链接存储中，每个行单链表中的结点都具有相同的A 。 2.设一个具有A 行号 B t个非零元素的列号 C 元素值m*n 大小的稀疏矩阵采用顺D 地址 序存储，求其转置矩阵的普通转置算法的时间复杂度为 D 3.设一个广义表中结点的个数为A O(m) 。 B O(n) C O(n+t) n，则求广义表深度算法D O(n*t) 的时间复杂度为 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.一个广义表的深度等于 表 元素两类。 10.在广义表的存储结构中，每个结点均包含有 括号 嵌套的最大层数。 在广义表的存储结构中，单元素结点与表元素结点有 3 个域。 一个域对应不同，各自分别为值 域和 子表指针域 。 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 4/7 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(col(行号) 1 2 2 3 4 5 5 6 val(列号 ⑶给出它的转置矩阵的三元组线性表和顺序存储表示；元素值) 2 4 7 1 4 2 6 4 ) 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(col(行号) 1 2 val(列号3.画出下列每个广义表的带表头附加结点的链接存储结元素值) 3 1 ) 8 4 构图并分别计算出它们的长度和深度。 ⑴ 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.MS[MaxSize]设用第二建立三个链接堆栈，章定义的类型为其中前三个元素的AlinkList的一维数next组域用来存储三个栈顶指针，从下标为3的元素起作为空闲元素提供给三个栈共同使用，试编写一个算法把从键盘上输入的n个整数按照下列条件分别进入不同的栈： ⑴若输入的整数x小于60，则进第一个栈； ⑵若输入的整数x大于等于60同时小于100，则进第二个栈； ⑶若输入的整数大于100，则进第三个栈。 解： void MoreStack(ALinkList MS,int n) //把从键盘上输入的n个整数按不同条件分别进入到三个不同的链接栈中 if(n>MaxSize-3){ { cerr<<\ exit(1); 存储空间不足!\ } for(i=0;i<3;i++) int i,x,av; av=3;//avMS[i].next=0//置空栈，即给三个栈顶指针赋 cout<<\ for(i=0;i 输入指向可利用元素的下标，赋初值为\个整数：\3 0 // cin>>x; 从键盘读入一个整数并把它赋给av元素的值域 //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 int next; {//void MoreStack(ALinkList MS,int n) } 函数体在此省略 void main() { ALinkList a; cout<<\int n; 从键盘输入的整数个数(1 cin>>n; ～47):\ for(int i=0;i<3;i++) MoreStack(a,n); int j=a[i].next; { //依次将每个栈中的元素全部出栈并打印出来 while(j!=0){ cout< cout< 一次输入和运行结果如下： 从键盘上输入的整数个数为(1 输入12个整数： ～47)：12 38 64 97 120 78 33 45 214 88 25 143 60 25 45 33 38 60 88 78 97 64 3. 3+4/(25-(6+15))*8@ 已知一个中缀算术表达式为：143 214 120 ⑴写出对应的后缀算术表达式。 解：3 4 25 6 15 + - /8 * + @ ⑵画出在转换成后缀表达式的过程中运算符栈的变化。 解：略 4.已知一个后缀算术表达式为： 5/7 24 8 + 3 * 4 10 7 - * / @ ⑴写出对应的中缀算术表达式。 解： (24+8)*3/(4*(10-7)) ⑵画出在进行后缀算术表达式求值的过程中数值栈的变化。 解：略 5.编写把十进制正整数转换为十六进制数输出的算法。 解： void Transform(long num) // { 把一个正整数num转为一个十六进制数输出 Stack a; while(num!=0){ InitStack(a); int k=num % 16; Push(a,k); } num/=16; while(!StackEmpty(a)) int X=Pop(a); { if(x<10) cout< { cass 10: break; cout<<'A'; cass 11: cout<<'B'; cass 12: break; cout<<'C'; cass 13: break; cout<<'D'; cass 14: break; cout<<'E'; cass 15: break; } cout<<'F'; } } cout< S进制(2≤S≤9)数输出的递归算法，然后若把425转换为六进制数，画出每次递归调用前和返回后系统栈的状态。 解： 只给出递归算法，画图从略。 void Transform(long num,int s) //把十进制正整数转换为S进制数的递归算法 { if(num!=0){ int k; k=num%S; cout< (Fibonacci)数列的定义为：它的第一项和第二项均为1，以后各项为其前两项之和。 若裴波那契数列中的第n项用Fid(n)表示，则计算公式为： 1 (n=1或 试编写计算Fib(n)= Fib(n-1)+Fib(n-2) Fib(n)的递归算法和非递归算法，(n>=2) n=2) 并分析它们的时间复杂度和空间复杂度。 解： 递归算法为： { long Fib(int n) return 1; if(n==1||n==2) //终止递归条件 else return Fib(n-1)+Fib(n-2); } long Fib1(int n) 非递归算法为 { int a,b,c;//C代表当前项，a和b分别代表当前项前面的第2项和第1项 a=b=1; // if(n==1||n==2) 给a和b赋初值1 else return 1; for(int i=3;i<=n;i++){ c=a+b; // a=b;// } b=c;//把当前项赋给前面第把前面第求出当前项1项赋给前面第 1项 2项 } return c;//返回所求的第n项 递归算法时间复杂度O（2n）、空间复杂度O（n） 非递归算法时间复杂度O（n）、空间复杂度O（1） 第五章 树和二叉树 1.一、填空题对于一棵具有 n个结点的树,该树中所有结点的度数之和为 n-1 。 2.5 假定一棵三叉树的结点个数为3.在一棵高度为，最大深度为 50，则它的最小深度为 h50 的四叉树中，最多含有。 （4h-1）/3 结点。 4.在地棵三叉树中，度为3的结点数有2个，度为2的结点数有1个，度为1的结点数为2个，那么度为0的结点数有 6 个。 5.一棵深度为5的满二叉树中的结点数为 31 个，一棵深度为3的满四叉树中的结点数为21 个。 6.J)))假定一棵树的广义表示为，则树中所含的结点数为A(B(C 10 个，树的深度为，D(E，F，G)， H(I4 个，，树的度为 3 。 7.J)))假定一棵树的广义表表示为6 ，则度为3，2，1，0的结点数分别为A(B(C，D(E 2 ，、F， 1 G)、， 1 H(I和， 8.J)))假定一棵树的广义表示为个。 A(B(C，D(E，F，G)9.在一棵二叉树中，，则结点H的双亲结点为假定双亲结点数为 B 个，孩子结点为，H(I，5个，单分支结点 I和J 。 数为6个，则叶子结点数为 6 个。 10.对于一棵二叉树，若一个结点的编号为i，则它的左孩子结点的编号为 2i ,右孩子结点的编号为 2i+1 ，双亲结点编号为 i/2 。 11.12.在一棵二叉树中，第5层上的结点数最多为 16 5 13.，最大深度为假定一棵二叉树的结点数为一棵二叉树的广义表表示为 18 。 18，则它的最小深度为。 a(b(e,d),e(f(,g))),则e结点的双亲结点为 a，左孩子结点为 f ，右孩子结点为 空 14.一棵二叉树的广义表表示为a(b(e,d),e(f(,g))),它含有 6/7 双亲结点 2 个，单分支结点 2 个，叶子结点 3 个。 15.16.对于一棵含有假一定一棵二叉树顺序存储在一维数组40个结点的理想平衡树，它的高度为a中，则a[i] 6 元素的左孩子元素为 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,e f后序遍历结果为 c b e f d a,按层遍历结果为 a b d c 24.。a(b((e),c(f(h,i,j),g),d),假 定一棵普通树的广义表表示为f h i j g d,按层遍历结果为则先根遍历结果为 a b c d e f g h i j a b e c 。 二、应用题 1.已知一棵具有n个结点的完全二叉树被顺序存储于一维数组的A[1]～A[n]元素中，试编写一个算法打印出编号为i的结点的双亲和所有孩子。 解： //void Request(int a[],int n,int i) 从数组A中打印出编号为i的结点的双亲和孩子 if(i>n){ { cerr<<\\ 编号为\的结点不存在！ exit(1); cout<<\} int j=i/2; if(j>0) //下标为j的结点是下标为i结点的双亲 else cout<<\ cout<<\ if(2*i 树根结点没有双亲结点!\ cout<<\ cout<<\ } else if(2*i==n){ cout<<\ cout<<\ } cout<<\else 2.编写一算法，求出一棵二叉树中所有结点数和叶子结} 点，假定分别用变参C1和C2统计所有结点数和叶子结 点数，初值均为0。 解： //void Count(BTreeNode* BT { 分别统计出二叉树中所有结点数和叶子结点数,int& C1,int& C2) if(BT!=NULL){ C1++;//统计所有结点 C2++; //if(BT->left==NULL&&BT->right==NULL) 统计叶子结点数 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 从二叉搜索树中查找一个元素时，其时间复杂度大致为 2.A O(n) B O(1) C O(log2n) D O(n2) 。 B 向二叉搜索树中插入一个元素时，其时间复杂度大致为 。 3.根据A O(1) B O(log2n) n个元素建立一棵二叉搜索树时，C O(n) D O(nlog2n) 其时间复杂度大致为 D 。 4.A O(n) B O(log2n) C O(n2) D O(nlog2n) 从堆中删除一个元素的时间复杂度为5.A O(1) C 。 向堆中插入一个元素的时间复杂度为B O(n) C O(log2n) D O(nlog2n) A 。 6.权值分别为A O(log2n) 3，B O(n) 8，6，2，C O(1) D O(nlog2n) 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.72,12,49,28已知一棵二叉排序树如图结点，试分别画出每删除一个结点后得到的 6-11所示，若从中依次删除7/7 二叉排序树。 / 28 12 \\ 49 \\ / \\ 16 34 72 30 / / 63 3.编写一个非递归算法，求出二叉排序树中的关键字最大的元素。 解：ElemType FindMax(BTreeNode* BST) { //从二叉排序树中返回关键字最大的元素 if(BST==NULL){ cerr<<\ exit(1); 不能在空树上查找最大值!\ BTreeNode* t=BST; } while(t->right!=NULL) t=t->right; return t->data; 4.~7. } 解略