2021年南京晓庄学院数据结构题库参考答案

数据构造与算法习题册（课后某些参照答案）《数据构造与算法》课程组目录课后习题部分第一章绪论 1第二章线性表 3第三章栈和队列 5第四章串 8第五章数组和广义表 10第六章树和二叉树 13第七章图 16第九章查找 20第十章排序 23第一章绪论一.填空题1.从逻辑关系上讲，数据构造类型重要分为集合、线性构造、树构造和图构造。2.数据存储构造重要有顺序存储和链式存储两种基本办法，无论哪种存储构造，都要存储两方面内容：数据元素和数据元素之间关系。3.算法具备五个特性，分别是有穷性、拟定性、可行性、输入、输出。4.算法设计规定中健壮性指是算法在发生非法操作时可以作出解决特性。二.选取题1.顺序存储构造中数据元素之间逻辑关系是由C表达，链接存储构造中数据元素之间逻辑关系是由D表达。A线性构造B非线性构造C存储位置D指针2.假设有如下遗产继承规则：丈夫和妻子可以互相继承遗产；子女可以继承爸爸或妈妈遗产；子女间不能互相继承。则表达该遗产继承关系最适当数据构造应当是B。A树B图C线性表D集合3.算法指是A。A对特定问题求解环节一种描述，是指令有限序列。B计算机程序C解决问题计算办法D数据解决三.简答题1.分析如下各程序段，并用大O记号表达其执行时间。(1)(2) i=1;k=0; i=1;k=0;While(i<n-1) do{{k=k+10*i； k=k+10*i；i++； i++;} }while(i<=n)⑴基本语句是k=k+10*i，共执行了n-2次，因此T(n)=O(n)。

⑵基本语句是k=k+10*i，共执行了n次，因此T(n)=O(n)。

2.设有数据构造（D，R），其中D={1，2，3，4，5，6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。试画出其逻辑构造图并指出属于何种构造。其逻辑构造图如下所示，它是一种图构造。3.求多项式A(x)算法可依照下列两个公式之一来设计：⑴A(x)=anxn+an-1xn-1+…+a1x+a0⑵A(x)=(…(anx+an-1)x+…+a1)x)+a0依照算法时间复杂度分析比较这两种算法优劣。第二种算法时间性能要好些。第一种算法需执行大量乘法运算，而第二种算法进行了优化，减少了不必要乘法运算。第二章线性表一.填空题1.在顺序表中，等概率状况下，插入和删除一种元素平均需移动表长一半个元素，详细移动元素个数与表长和插入位置关于。2.在一种长度为n顺序表第i（1≤i≤n+1）个元素之前插入一种元素，需向后移动n-i+1个元素，删除第i（1≤i≤n）个元素时，需向前移动n-i个元素。3.在单循环链表中，由rear指向表尾，在表尾插入一种结点s操作顺序是s->next=rear->next；rear->next=s；rear=s;；删除开始结点操作顺序为q=rear->next->next；rear->next->next=q->next；deleteq；。二.选取题1.数据在计算机存储器内表达时物理地址与逻辑地址相似并且是持续，称之为：CA存储构造B逻辑构造C顺序存储构造D链式存储构造2.在n个结点顺序表中，算法时间复杂度是O（1）操作是：AA访问第i个结点（1≤i≤n）和求第i个结点直接前驱（2≤i≤n）B在第i个结点后插入一种新结点（1≤i≤n）C删除第i个结点（1≤i≤n）D将n个结点从小到大排序3.线性表L在B状况下合用于使用链式构造实现。A需经常修改L中结点值B需不断对L进行删除插入CL中具有大量结点DL中结点构造复杂4.单链表存储密度CA不不大于1B等于1C不大于1D不能拟定三.判断题1.线性表逻辑顺序和存储顺序总是一致。F2.线性表顺序存储构造优于链接存储构造。F3.设p，q是指针，若p=q，则*p=*q。F4.线性构造基本特性是：每个元素有且仅有一种直接前驱和一种直接后继。F四.简答题1.分析下列状况下，采用何种存储构造更好些。(1)若线性表总长度基本稳定，且很少进行插入和删除操作，但规定以最迅速度存取线性表中元素。(2)如果n个线性表同步并存，并且在解决过程中各表长度会动态发生变化。(3)描述一种都市设计和规划。⑴应选用顺序存储构造。很少进行插入和删除操作，因此空间变化不大，且需要迅速存取，因此应选用顺序存储构造。

⑵应选用链式存储构造。链表容易实现表容量扩充，适合表长度动态发生变化。

⑶应选用链式存储构造。由于一种都市设计和规划涉及活动诸多，需要经常修改、扩充和删除各种信息，才干适应不断发展需要。而顺序表插入、删除效率低，故不适当。五.算法设计1.已知数组A[n]中元素为整型，设计算法将其调节为左右两某些，左边所有元素为奇数，右边所有元素为偶数，并规定算法时间复杂度为O(n)。2.线性表存储在整型数组A[arrsize]前elenum个单元中，且递增有序。编写算法，将元素x插入到线性表恰当位置上，以保持线性表有序性，并且分析算法时间复杂度。intinsert(datatypeA[],int*elenum,datatypex)

/*设elenum为表最大下标*/

{if(*elenum==arrsize-1)

return0;

/*表已满，无法插入*/

else{i=*elenum;

while(i>=0&&A[i]>x)

/*边找位置边移动*/

{A[i+1]=A[i];

i--;

}

A[i+1]=x;

/*找到位置是插入位下一位*/

(*elenum)++;

return1;

/*插入成功*/

}

}O（n）第三章栈和队列一.填空题1.设有一种空栈，栈顶指针为1000H，既有输入序列为1.2.3.4.5，通过push，push，pop，push，pop，push，push后，输出序列是23，栈顶指针为1003H。2.栈普通采用两种存储构造是顺序栈、链栈；其鉴定栈空条件分别是TOP=-1、TOP=NULL，鉴定栈满条件分别是TOP=数组长度、存储空间满。3.栈可作为实现递归函数调用一种数据构造。4.表达式a*(b+c)-d后缀表达式是abc+*d-。二.选取题1.若一种栈输入序列是1，2，3，…，n，输出序列第一种元素是n，则第i个输出元素是D。A不拟定Bn-iCn-i-1Dn-i+12.设栈S和队列Q初始状态为空，元素e1.e2.e3.e4.e5.e6依次通过栈S，一种元素出栈后即进入队列Q，若6个元素出队顺序是e2.e4.e3.e6.e5.e1，则栈S容量至少应当是C。A6B4C3D23.一种栈入栈序列是1，2，3，4，5，则栈不也许输出序列是C。A54321B45321C43512D12345三.判断题1.有n个元素依次进栈，则出栈序列有(n-1)/2种。F2.栈可以作为实现过程调用一种数据构造。T3.在栈满状况下不能做进栈操作，否则将产生“上溢”。T4.在循环队列中，front指向队头元素前一种位置，rear指向队尾元素位置，则队满条件是front=rear。F四.简答题1.设有一种栈，元素进栈顺序为A，B，C，D，E，能否得到如下出栈序列，若能，请写出操作序列，若不能，请阐明因素。⑴C，E，A，B，D⑵C，B，A，D，E⑴不能，由于在C、E出栈后，A一定在栈中，并且在B下面，不也许先于B出栈⑵可以，设Ｉ为进栈操作，Ｏ为入栈操作，则其操作序列为IIIOOOIOIO。2.在操作序列push(1).push(2).pop.push(5).push(7).pop.push(6)之后，栈顶元素和栈底元素分别是什么？（push(k)表达k入栈，pop表达栈顶元素出栈。）栈顶元素为6，栈底元素为1。3.在操作序列EnQueue(1).EnQueue(3).DeQueue.EnQueue(5).EnQueue(7).DeQueue.EnQueue(9)之后，队头元素和队尾元素分别是什么？（EnQueue(k)表达整数k入队，DeQueue表达队头元素出队）。队头元素为5，队尾元素为9。4.简述如下算法功能（栈元素类型SElemType为int）。(1)statusalgo1(StackS,inte) { StackT；intd；InitStack(T); while(!StackEmpty(S)){ Pop(S,d); if(d!=e)Push(T,d); } while(!StackEmpty(T)){ Pop(T,d)；Push(S,d); } }//S中如果存在e，则删除它。(2)voidalgo2(Queue&Q) { StackS；intd；InitStack(S); while(!QueueEmpty(Q)) { DeQueue(Q，d)；Push(S，d); } while(!StackEmpty(S)) { Pop(S，d)；EnQueue(Q，d); } }//队列逆置五.算法设计1.试写一种鉴别表达式中开、闭括号与否配对浮现算法BOOLBracketCorrespondency(chara[]){ inti=0; Stacks; InitStack(s); ElemTypex; while(a[i]){ switch(a[i]){ case'(': Push(s,a[i]); break; case'[': Push(s,a[i]); break; case')': GetTop(s,x); if(x=='(') Pop(s,x); elsereturnFALSE; break; case']': GetTop(s,x); if(x=='[')Pop(s,x); elsereturnFALSE; break; default: break; } i++; } if(s.size!=0)returnFALSE; returnTRUE;}2.假设称正读和反读都相似字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试写一种算法鉴别读入一种以‘@’为结束符字符序列与否是“回文”。StatusSymmetryString(char*p){ Queueq; if(!InitQueue(q))return0; Stacks; InitStack(s); ElemTypee1,e2; while(*p){ Push(s,*p); EnQueue(q,*p); p++; } while(!StackEmpty(s)){ Pop(s,e1); DeQueue(q,e2); if(e1!=e2)returnFALSE; } returnOK;}第四章串一.填空题1.不包括任何字符（长度为0）串称为空串；由一种或各种空格（仅由空格符）构成串称为空白串。2.设S=“A;/document/Mary.doc”，则strlen(s)=20，“/”字符定位位置为3。3.若n为主串长，m为子串长，则串典型模式匹配算法最坏状况下需要比较字符总次数为(n-m+1)*m。二.选取题1.串是一种特殊线性表，其特殊性体当前：（B）A可以顺序存储B数据元素是一种字符C可以链式存储D数据元素可以是各种字符2.设有两个串p和q，求q在p中初次浮现位置运算称作：（B）A连接B模式匹配C求子串D求串长3.设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串连接串，subs(s，i，j)返回串s从序号i开始j个字符构成子串，len(s)返回串s长度，则con(subs(s1，2，len(s2))，subs(s1，len(s2)，2))成果串是：（D）A‘BCDEF’B‘BCDEFG’C‘BCPQRST’D‘BCDEFEF’4.若串S=”software”，其子串数目是（B）。A8B37C36D9三.计算题1.设s=’IAMASTUDENT’，t=’GOOD’，q=’WORKER’，求：1）Replace(s,’STUDENT’,q)2）Concat(t,SubString(s,7,8)))1、Replace(s,’STUDENT’,q)＝’IAMAWORKER’2、由于SubString(s,7,8)＝‘STUDENT’Concat(t,SubString(s,7,8))＝’GOODSTUDENT’四.算法设计1.运用C库函数strlen，strcpy（或strncpy）写一种算法voidStrDelete(char*S,intt,intm)，删除串S中从位置i开始持续m个字符。若i≥strlen(S)，则没有字符被删除；若i+m≥strlen(S)，则将S中从位置i开始直至末尾字符均被删去。提示：strlen是求串长(length)函数：intstrlen(chars)；//求串长度strcpy是串复制(copy)函数：char*strcpy(charto,charfrom)；//该函数将串from复制到串to中，并且返回一种指向串to开始处指针。voidStrDelete(char*S，inti,intm)

{//串删除

charTemp[Maxsize];//定义一种暂时串

if(i+m<strlen(S))

{

strcpy(Temp，&S[i+m]);//把删除字符后来字符保存到暂时串中

strcpy(&S[i],Temp);//用暂时串中字符覆盖位置i之后字符

}

elseif(i+m>=strlen(S)&&i<strlen(S))

{

strcpy(&S[i],"\0");//把位置i元素置为'\0'，表达串结束

}

}第五章数组和广义表一.填空1.假设有二维数组A6×8，每个元素用相邻6个字节存储，存储器按字节编址。已知A起始存储位置（基地址）为1000，则数组A体积（存储量）为288；末尾元素A57第一种字节地址为1282；若按行存储时，元素A14第一种字节地址为1072；若按列存储时，元素A47第一种字节地址为1276。2.三元素组表中每个结点相应于稀疏矩阵一种非零元素，它包具有三个数据项，分别表达该元素行下标、列下标和元素值。。3.广义表((a)，(((b),c)),(d))长度是3，深度是4，表头是(a)，表尾是(((b),c)),(d)。4.已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b运算是Head(Head(Tail(LS)))。二.选取题1.假设有60行70列二维数组a[1…60，1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列元素a[32,58]存储地址为(A)。（无第0行第0列元素）A16902B16904C14454D答案A，B，C均不对2.设矩阵A是一种对称矩阵，为了节约存储，将其下三角某些按行序存储在一维数组B[1，n(n-1)/2]中，下三角某些中任一元素ai,j(i≤j)，在一维数组B中下标k值是：(B)Ai(i-1)/2+j-1Bi(i-1)/2+jCi(i+1)/2+j-1Di(i+1)/2+j3.一种n*n对称矩阵，用压缩存储办法解决其对称性质后存储，则其容量为：(C)。An*nBn*n/2C(n+1)*n/2D(n+1)*(n+1)/2三.计算题1.设有一种二维数组A[m][n]，假设A[0][0]存储位置在644，A[2][2]存储位置在676，每个元素占一种空间，问A[3][3]存储在什么位置？写出计算过程。(676-644)/1=32A[2][2]地址相对A[0][0]偏移量为32，则A[3][3]相较于A[0][0]偏移量为32*3/2=48A[3][3]地址为48+644=6922.设A[9][9]是一种10*10对称矩阵，采用压缩存储方式存储其下三角某些，已知每个元素占用两个存储单元，其第一种元素A[0][0]存储位置在1000，求下面问题计算过程及成果：给出A[4][5]存储位置。A[4][5]是上三角某些，因此存在A[5][4]若以行序为主序，则地址为1000+2（5（1+5）/2+4）=1036若以列序为主序，则地址为1000+2（4（10+7）/2+5）=1062给出存储位置为1080元素下标。i(i+1)/2+j或j(10+10-j+1)/2+i=40得i=9，j=4或i=8j=5，A[8][5]或A[9][4]3.一种稀疏矩阵如图所示，则相应三元组线性表是什么？其相应十字链表是什么？00200020300000-1500004.下列各三元组表分别表达一种稀疏矩阵，试写出它们稀疏矩阵。0202001200030000004006016000四.算法设计1.设计一种算法，计算一种三元组表表达稀疏矩阵对角线元素之和。2.若在矩阵A中存在一种元素ai,j（0≤i≤n-1，0≤j≤m-1），该元素是第i行元素中最小值且又是第j列元素中最大值，则称此元素为该矩阵一种鞍点。假设以二维数组存储矩阵A，试设计一种求该矩阵所有鞍点算法，并分析最坏状况下时间复杂度voidSaddle(intA[m][n])//A是m*n矩阵,本算法求矩阵A中马鞍点.{intmax[n]={0}，//max数组存储各列最大值元素行号,初始化为行号0;min[m]={0}，//min数组存储各行最小值元素列号,初始化为列号0;i，j;for(i=0;i<m;i++)//选各行最小值元素和各列最大值元素.{for(j=0;j<n;j++){if(A[max[j]][j]<A[i][j])max[j]=i；//修改第j列最大元素行号if(A[i][min[i]]>A[i][j])min[i]=j；//修改第i行最小元素列号.}for(i=0;i<m;i++){j=min[i]；//第i行最小元素列号if(i==max[j])printf(“A[%d][%d]是马鞍点，元素值是%d”,i,j,A[i][j])；}}}//Saddle分析算法，外层for循环共执行m次，内层第一种for循环执行n次，第二个for循环最坏状况下执行m次，因此，最坏状况下时间复杂度为Ｏ(mn+mm)。第六章树和二叉树一.填空题1.树是n（n≥0）结点有限集合。在一棵空树中有0个元素；在一棵非空树中，有且仅有一种个根结点，别的结点提成m（m＞0）个互不相交集合，每个集合都是根结点子树。2.一棵二叉树第i（i≥1）层最多有2i-1个结点；一棵有n（n>0）个结点满二叉树共有(n+1)/2个叶子结点和(n-1)/2个非终端结点。3.设深度为k二叉树上只有度为0和度为2结点，该二叉树结点数也许达到最大值是2k-1，最小值是2k-1。4.深度为k二叉树中，所含叶子个数最多为2k-1。5.在顺序存储二叉树中编号为i和j两个结点处在同一层条件为：二.选取题1.前序遍历和中序遍历成果相似二叉树是（D）。A根结点无左孩子二叉树B根结点无右孩子二叉树C所有结点只有左子树二叉树D所有结点只有右子树二叉树2.序存储办法将完全二叉树中所有结点逐级存储在数组A[1]~A[n]中，结点A[i]若有左子树，则左子树根结点是（D）。AA[2i-1]BA[2i+1]CA[i/2]DA[2i]3.完全二叉树中任一结点，若其右分支下子孙最大层次为h，则其左分支下子孙最大层次为（C）。AhBh+1Ch或h+1D任意4.在线索二叉树中，一种结点是叶子结点充要条件为（C）。A左线索标志为0，右线索标志为1B左线索标志为1，右线索标志为0C左.右线索标志均为0D左.右线索标志均为15.由权值为{3，8，6，2，5}叶子结点生成一棵哈夫曼树，其带权途径长度为（C）。A24B48C53D72三.简答题1.已知二叉树中序和后序序列分别为CBEDAFIGH和CEDBIFHGA，请构造出此二叉树，并写出此树后序遍历序列。2.将下图所示树转换为二叉树，3.图5-17所示二叉树转换为树或森林4.已知某字符串S中共有8种字符[A,B,C,D,E,F,G,H]，分别浮现2次.1次.4次.5次.7次.3次.4次和9次。1）试构造出哈夫曼编码树，并对每个字符进行编码EH2）问该字符串编码至少有多少位。EHCGDFBAA:00000B:00001C:100D:001E:11F:0001G:101H:01CGDFBA其带权途径长度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，因此，该字符串编码长度至少为98位。四.算法设计1.设计算法求二叉树结点个数2.以二叉链表为存储构造，编写算法求二叉树中结点x双亲3.编写算法互换二叉树中所有结点左右子树。第七章图一.填空题1.设无向图G中顶点数为n，则图G至少有0条边，至多有n(n-1)/2条边；若G为有向图，则至少有0条边，至多有n(n-1)条边。2.任何连通图连通分量只有一种，即是它自身3.若一种有向图由邻接矩阵表达，则计算第j个顶点入度办法是求矩阵第j列元素之和4.图深度优先遍历类似于树先根遍历，广度优先遍历类似于树层序遍历。5.对于具有n个顶点e条边连通图，运用Prim算法求最小生成树时间复杂度为Ｏ(n2)，运用Kruskal算法求最小生成树时间复杂度为Ｏ(elog2e)。二.选取题1.在一种无向图中，所有顶点度数之和等于所有边数（C）倍。A1/2B1C2D42.n个顶点强连通图至少有（A）条边。AnBn+1Cn-1Dn×(n-1)3.含n个顶点连通图中任意一条简朴途径，其长度不也许超过（C）。A1Bn/2Cn-1Dn4.对于一种具备n个顶点无向图用邻接矩阵存储，则该矩阵大小是（D）。AnB(n-1)2Cn-1Dn25.设无向图G=(V，E)和G'=(V'，E')，如果G'是G生成树，则下面说法中错误是（B）。AG'为G子图BG'为G连通分量CG'为G极小连通子图且V=V'DG'是G一种无环子图6.鉴定一种有向图与否存在回路除了可以运用拓扑排序办法外，还可以用（D）。A求核心途径办法B求最短途径办法C广度优先遍历算法D深度优先遍历算法7.下面关于工程筹划AOE网论述中，不对的是（B）A核心活动不按期完毕就会影响整个工程完毕时间B任何一种核心活动提前完毕，那么整个工程将会提前完毕C所有核心活动都提前完毕，那么整个工程将会提前完毕D某些核心活动若提前完毕，那么整个工程将会提前完三.计算题1.已知一种连通图如图所示，试给出图邻接矩阵和邻接表存储示意图，若从顶点v1出发对该图进行遍历，分别给出一种按深度优先遍历和广度优先遍历顶点序列。邻接矩阵表达如下：

深度优先遍历序列为：v1v2v3v5v4v6

广度优先遍历序列为：v1v2v4v6v3v5

邻接表表达如右：2.已知无向图G邻接表如下图所示，分别写出从顶点1出发深度遍历和广度遍历序列，并画出相应生成树。深度优先遍历序列为：1，2，3，4，5，6

相应生成树为：

广度优先遍历序列为：1，2，4，3，5，6

相应生成树为：3.下图所示是一种无向带权图，请分别按Prim算法和Kruskal算法求最小生成树。4.如右图所示有向网图，运用Dijkstra算法求从顶点v1到其她各顶点最短途径。从源点v1到其她各顶点最短途径如下表所示。源点终点最短途径最短途径长度v1v3v1v315

v1v5v1v515

v1v2v1v3v225

v1v6v1v3v2v640

v1v4v1v3v2v4455.已知一种AOV网如下图所示，写出所有拓扑序列。拓扑序列为：v0v1v5v2v3v6v4、v0v1v5v2v6v3v4、v0v1v5v6v2v3v4。四.算法设计1.设计算法，将一种无向图邻接表转换成邻接矩阵。2.设计算法，计算图中出度为零顶点个数。3.已知一种有向图邻接表，编写算法建立其逆邻接表第九章查找一.填空题1.顺序查找技术适合于存储构造为顺序和链式存储线性表，而折半查找技术合用于存储构造为顺序存储线性表，并且表中元素必要是按核心码有序。2.折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素28，6，12，20比较大小。3.在各种查找办法中，平均查找长度与结点个数n无关查找办法是散列（哈希）查找。4.为了能有效地应用哈希查找技术，必要解决两个问题是构造散列函数和解决冲突。5.有一种表长为m散列表，初始状态为空，现将n（n<m）个不同核心码插入到散列表中，解决冲突办法是用线性探测法。如果这n个核心码散列地址都相似，则探测总次数是n(n-1)/2=（1＋2＋…＋n-1）。二.选取题1.静态查找与动态查找主线区别在于（B）。A它们逻辑构造不同样B施加在其上操作不同C所包括数据元素类型不同样D存储实现不同样2.用n个键值构造一棵二叉排序树，其最低高度为（D）。An/2BnClog2nDlog2n+13.散列技术中冲突指是（D）。A两个元素具备相似序号B两个元素键值不同，而其她属性相似C数据元素过多D不同键值元素相应于相似存储地址4.链表合用于A查找A顺序B二分法C顺序，也能二分法D随机三.简答题1.分别画出在线性表（a，b，c，d，e，f，g）中进行折半查找核心码e和g过程。见下页2.画出对长度为10有序表进行折半查找鉴定树，并求其等概率时查找成功平均查找长度。第1题答案3.设哈希（Hash）表地址范畴为0～17，哈希函数为：H（K）＝KMOD16。K为核心字，用线性探测法再散列法解决冲突，输入核心字序列：（10，24，32，17，31，30，46，47，40，63，49）构造出Hash表，试回答下列问题：(1)画出哈希表达意图；(2)若分别查找核心字63和60，分别需要依次与哪些核心字进行比较？(3)假定每个核心字查找概率相等，求查找成功时平均查找长度。解：（1）画表如下：012345678910111213141516173217634924401030314647（2）查找63,一方面要与H(63)=63%16=15号单元内容比较，即63vs31,no;然后顺移，与46,47,32,17,63相比，一共比较了6次！（3）查找60,一方面要与H(60)=60%16=12号单元内容比较，但由于12号单元为空（应当有空标记），因此应当只比较这一次即可。（4）对于黑色数据元素，各比较1次；共6次；对红色元素则各不相似，要记录移位位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，因此ASL=1/11（6＋2＋3×3）＝17/11=1.≈1.55四.算法设计1.编写算法求给定结点在二叉排序树中所在层数2.一种鉴别给定二叉树与否为二叉排序树算法，设此二叉树以二叉链表作存储构造。且树中结点核心字均不同。解：注意仔细研究二叉排序树定义。易犯典型错误是按下述思路进行鉴别：“若一棵非空二叉树其左、右子树均为二叉排序树，且左子树根值不大于根结点值，又根结点值不不不大于右子树根值，则是二叉排序树”（刘注：即不能只判断左右孩子状况，还要判断左右孩子与双亲甚至根结点比值也要遵循（左小右大）原则）。若要采用递归算法，建议您采用如下函数首部：boolBisortTree(BiTreeT，BiTree&PRE)，其中PRE为指向当前访问结点前驱指针。（或者直接存储前驱数值，随时与当前根结点比较）一种美丽算法设计如下：intlast=0，flag=1；//last是全局变量，用来记录前驱结点值，只要每个结点都比前驱大就行。intIs_BSTree(BitreeT)//判断二叉树T与否二叉排序树，是则返回1，否则返回0{if(T->lchild&&flag)Is_BSTree(T->lchild)；if(T->data<last)flag=0；//与其中序前驱相比较，flag=0表达当前结点比直接前驱小，则及时返回last=T->data；if(T->rchild&&flag)Is_BSTree(T->rchild)；returnflag；}//Is_BSTree第十章排序一.填空题1.排序办法有诸各种，插入排序法从未排序序列中依次取出元素，与已排序序列中元素作比较，将其放入已排序序列对的位置上。选取排序法从未排序序列中挑选元素，并将其依次放入已排序序列一端。互换排序是对序列中元素进行一系列比较，当被比较两元素为逆序时，进行互换；冒泡排序和迅速排序是基于此类办法两种排序办法，而迅速排序是比冒泡排序效率更高办法；堆排序法是基于选取排序一种办法，是完全二叉树构造一种重要应用。2.一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需比较3次。3.对n个待排序记录序列进行迅速排序，所需要最佳时间是O(nlog2n)，最坏时间是O(n2)二.选取题1.下列序列中，（A）是执行第一趟迅速排序成果。A[da，ax，eb，de，bb]ff[ha，gc]B[