数据结构(本)期末综合练习(2023年11月)

数据结构（本）期末综合练习2023年11月综合练习一一、单项选择题1.对稀疏矩阵进行压缩存储,可采用三元组表，一个10行8列的稀疏矩阵A共有73个零元素，其相应的三元组表共有(C)个元素。A．8B．80C．7D．102.对稀疏矩阵进行压缩存储,可采用三元组表，一个10行8列的稀疏矩阵A，其相应的三元组表共有6个元素，矩阵A共有(C)个零元素。A．8B．72C．74D．103.字符串(A)是“abcd321ABCD”的子串。A.“21AB”B.“abcD”C.“aBCD”D.“321a”4.程序段chara[]=“abdcacdef”;char*p=a;intn=0;while(*p!=‘\0’){n++;p++;}结果中,n的值是（D）A.6B.8C.7D.95.栈和队列的共同特点是（A）。A．都是操作受限的线性结构B．元素都可以随机进出C．都是先进后出D．都是先进先出6.10,6,2,1按顺序依次进栈，该队列的可能输出序列是（A）。(进栈出栈可以交替进行）。A．6,10,1,2B．2,10,6,1C．6,1,10,1D．1,6,10,27.在一个链队中，假设f和r分别为队头和队尾指针，p指向一个新结点,要为结点p所指结点赋值x,并入队的运算为p->data=x;p->next=NULL;（B）。A.f->next=p;f=p;B．r->next=p;r=p;C．r=p;p->next=r;D．p->next=f;f=p;8.对一个栈顶指针为top的链栈进行出栈操作，用变量e保存栈顶元素的值，则执行(B）。A．e=top->next;top->data=e;B．e=top->data;top=top->next;C．top=top->next;e=top->data;D．top=top->next;e=data;9.数据结构中，与所使用的计算机无关的是数据的(A)结构。A.逻辑B.存储C.逻辑与存储D.物理10.算法的时间复杂度与(A)有关。A.算法本身B.所使用的计算机C.算法的程序设计D.数据结构11．顺序表所具备的特点之一是（A）。A．可以随机访问任一结点B．不需要占用连续的存储空间C．插入元素的操作不需要移动元素D．删除元素的操作不需要移动元素12．在一个单向链表中,在p所指结点之后插入一个s所指的结点时，可执行s->next=p->next;和（D）。A．p=s;B．p->next=s->next;C．p=s->nextD．p->next=s;13.数据元素是数据的基本单位，它（C）。A．只能有一个数据项组成B．至少有二个数据项组成C．可以是一个数据项也可以由若干个数据项组成D．至少有一个数据项为指针类型14.一种逻辑结构在存储时（C）。A．只要存储数据元素间的关系B．只能采用一种存储结构C．可采用不同的存储结构D．只要存储数据元素的值15．设有头指针为head的非空的单向链表,指针p指向其尾结点,要使该单向链表成为单向循环链表,则可利用下述语句（C）。A．p=head;B．p=NULL;C．p->next=head;D．head=p;16.单向链表所具备的特点是(C)。A.可以随机访问任一结点B.占用连续的存储空间C.插入删除不需要移动元素D.可以通过某结点的指针域访问其前驱结点17.在线性表的顺序结构中，以下说法正确的是（C）。A．逻辑上相邻的元素在物理位置上不一定相邻B．数据元素是不能随机访问的C．逻辑上相邻的元素在物理位置上也相邻D．进行数据元素的插入、删除效率较高18.数据结构在计算机内存中的表示是指(B)。A．数据元素之间的关系B．数据的存储结构C．数据元素的类型D．数据的逻辑结构19.对链表,以下叙述中正确的是（A）。A．不能随机访问任一结点B．结点占用的存储空间是连续的C．插入删除元素的操作一定要要移动结点D．可以通过下标对链表进行直接访问20.下面关于线性表的叙述中,错误的是(B)。A.线性表采用顺序存储,必须占用一片连续的存储空间。B.线性表采用顺序存储,进行插入和删除操作,不需要进行数据元素间的移动。C.线性表采用链式存储，不必占用连续的存储空间。D.线性表采用链式存储，进行插入删除操作，不需要移动元素21.设有一个长度为35的顺序表，要在第5个元素之前插入1个元素（也就是插入元素作为新表的第5个元素），则移动元素个数为（B）。A．30B．31C.5D．622.设有一个长度为18的顺序表，要在第5个元素之前插入1个元素（也就是插入元素作为新表的第5个元素），则移动元素个数为（B）。A．15B．14C.5D．623．设有一个长度为40的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数为（C）。A．11B．10C．30D．3124．设有一个长度为25的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数为（C）。A．10B．17C．15D．1625．设有一个25阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a7,5在一维数组B中的下标是（C）。A．25B．24C．26D．2726．设有一个18阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则矩阵中元素a10,8在一维数组B中的下标是（D）。A．62,B．63C．51D．5327．线性表在存储后,如果相关操作中有要求:利用已知的指向某结点的指针或序号,访问该结点的前驱结点，则采用（A）的存储方式是不可行的。A．单向链表B．双向链表C．单向循环链表D．顺序表28．在一个尾指针为rear的不带头结点的单循环链表中,插入一个s所指的结点,并作为第一个结点，可执行snext=rearnext;和（D）。A．rearnext=snext;B．rear=snext;C．rear=s;D．rearnext=s;29．在一棵二叉树中，若编号为i的结点存在左孩子,i结点的左孩子的顺序编号为（B）。A．i/2.0B．2*iC．2*i+1D．i+230．在一棵二叉树中，若编号为15的结点是其双亲结点的右孩子，则双亲结点的顺序编号为（D）。A．30B．8C．31D．7二、填空题1.广义表((b,a,c),c,d,f,e,((i,j),k))的长度是___6_____。2.结构中的元素之间存在一对多的关系是___树形_____结构。3.数据结构中，数据元素之间的抽象关系称为____逻辑____结构。4.结构中的元素之间存在多对多的关系是___图状_____结构。5.栈的操作特点是后进___先出_____。6.循环队列的最大存储空间为MaxSize,若队头指针front，队尾指针rear，采用少用一个存储空间以有效地判断栈空或栈满，队空的判定条件为___rear==front为真_____。7.广义表((b,a,c),c,d,f,e,((i,j),k))的表头是____（b,a,c）____。8.广义表((b,a,c),c,d,f,e,((i,j),k))的长度是____6____。9.设有一个长度为18的顺序表,第8号元素到第18号元素依次存放的值为8,9,…,18.某人想要删除第8号元素，程序中他的做法是用语句for(i=18;i<=9;i--)a[i-1]=a[i];即从第18号元素开始,直到第9号元素,每个元素依次向前(左)移动1个位置.事实上这样做是错误的.其结果新表中第9号元素的值为___18_____。10．要求在n个数据元素中找值最大的元素，其基本操作为元素间的比较。算法的时间复杂度为____O(n)___。11.一棵二叉树,有1个2度结点,，2个1度结点，则该树共有_5______个结点。12．一棵有8个叶结点的二叉树，其1度结点的个数为3，则该树共有___18____个结点。13．设有一棵深度为5的完全二叉树，该树共有21个结点,第5层上有6个结点。（根所在结点为第1层）14.对于一棵具有n个结点的二叉树，其相应的链式存储结构中共有__n+1______个指针域为空。15．中序遍历____二叉排序树____树可得到一个有序序列。16.对一组记录（5，8，9，2，12，7，56，44，39）进行直接插入排序(由小到大排序)，当把第6个记录7插入有序表，为寻找插入位置需比较__4______次。17.序列12,10,13,11,16,14,采用冒泡排序算法,经一趟冒泡后,序列的结果是____10，12，11，13，14，16____。（按升序排序）18．设有一棵深度为6的完全二叉树，第6层上有3个结点，该树共有__34_____个结点。（根所在结点为第1层）19.对16个元素的序列用冒泡排序法进行排序，共需要进行___15_____趟冒泡。20．一棵有16个叶结点的哈夫曼树，则该树共有___31____个结点。21.一棵有16个叶结点的哈夫曼树，则该树共有__15_____个非叶结点。22.20个元素进行冒泡法排序，通常第6趟冒泡要进行___14___次元素间的比较。23.在对一组记录（40，24，82，9，1，78，46，31，69）进行直接插入排序(由小到大排序)，当把第7个记录46插入到有序表时，为寻找插入位置需比较____3____次。24．对稀疏矩阵进行压缩存储,可采用三元组表，一个6行7列的稀疏矩阵A共有38个零元素，其相应的三元组表共有____4___个元素。三、综合题1．设有序表为(5,8,14,15,33,51,61,73,81,82,93),元素的序号依次为1,2,3,……，11.（1）画出对上述查找表进行折半查找所对应的判定树（树中结点可用序号表示）（2）说明成功查找到元素33需要经过多少次比较？(3)在等概率条件下,给出成功查找的平均查找长度（1）图451148151561828337393(2)4次(3)(1+2*2+3*4+4*4)/11=33/11=32.设数据集合a={1,5,8,3,10,7,13,9}（1）依次取a中各数据，构造一棵二叉排序树。（2）对该二叉树进行查找，成功查找到7要进行多少次元素间的比较？（3）给出对该二叉树中序遍历的序列。(1)图5(2)4次 (3)中序遍历1,3,5,7,8,9,10,133．dcdceabfhe图1(1)acdbfeh(2)152364或152634或156234(2)设有向图如图2所示下，写出首先删除顶点1的1种拓扑序列11234543465图24．设有序表为(30,48,58,70,78,79,90),元素的序号依次为1,2,3,……，7.（1）画出对上述查找表进行折半查找所对应的判定树（树中结点用序号表示）（2）给出有序表中经3次比较成功查找到的所有元素(3)说明不成功查找元素59需要经过多少次比较？（1）图670487930587890(2)30587890(3)3次5.(1)设数据集合a={7,4,9,8,6,5,3},依次取a中各数据，构造一棵二叉排序树。(2)对该二叉树进行查找，成功查找到5要进行多少次元素间的比较？(3)给出对上述二叉排序树进行中序遍历的序列(1)图7(2)4(3)3,4,,5,6,7,8,96．(1)如图3所示，若从顶点a出发，首先经过c按广度优先搜索法进行遍历，给出可能得到的一种顶点序列。（2）同图3所示,若从顶点h出发，按深度优先搜索法进行遍历，给出可能得到的2种顶点序列。aa阿decfhecdeccdeceec图3(3)一组记录的关键字序列为（75，63，95，80，53，45，38，20），利用堆排序的方法建立小根堆(堆顶元素是最小元素）,给出按筛选法建立的的初始堆。(1)acefdh(2)hdeacfhdfcae（3）20,53，38，63，75，45，95，80四、程序填空题1．以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-1，完成程序中的空格typedefstruct{intkey;……}NODE;intBinary_Search(NODEa[],intn,intk){intlow,mid,high;low=0;high=n-1;while(___(1)_____){mid=(low+high)/2;if(a[mid].key==k)return__(2)______; elseif(___(3)_____)low=mid+1; else__(4)______; }___(5)_____; }(1)low<=high(2)mid(3)a[mid].key<k(4)high=mid-1(5)return-12．以下函数为直接选择排序算法，对a[1],a[2],…a[n]中的记录进行直接选择排序，完成程序中的空格typedefstruct{intkey;……}NODE;voidselsort(NODEa[],intn){ inti,j,k;NODEtemp; for(i=1;i<=___(1)___;i++){ k=i; for(j=i+1;___(2)__;j++) if(a[j].key<a[k].key)__(3)____; if(i!=k) { temp=a[i];___(4)____;___(5)____; } }}(1)n-1(2)j<=n(3)k=j(4)a[i]=a[k](5)a[k]=temp3.以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为栈顶指针structnode{ElemTypedata;structnode*next;};structnode*top;voidPush(ElemTypex){structnode*p;p=(structnode*)malloc(___(1)___);p->data=x;__(2)____;___(3)___;}(1)sizeof(structnode)(2)pnext=top(3)top=p4.以下函数为链队列的入队操作，x为要入队的结点的数据域的值，front、rear分别是链队列的队头、队尾指针structnode{ElemTypedata;structnode*next;};structnode*front，*rear;voidInQueue(ElemTypex){structnode*p;p=(structnode*)___(1)_____;p->data=x;p->next=NULL;___(2)_____;;rear=___(3)_____;}(1)malloc(sizeof(structnode))(2)rear->next=p;(3)rear=p;综合练习二一、单项选择题1.对稀疏矩阵进行压缩存储,可采用三元组表，一个有10行的稀疏矩阵A共有97个零元素，其相应的三元组表共有3个元素。该矩阵A有(D)列。A．8B．9C．7D．102.单向链表所具备的特点是(C)。A.可以随机访问任一结点B.占用连续的存储空间C.插入删除不需要移动元素D.可以通过某结点的指针域访问其前驱结点3.子串“acd”在主串“abdcacdefac”中的位置是(B)。A．3B．5C．7D．14.设有一个长度为18的顺序表，要在第6个元素之前插入一个元素（也就是插入元素作为新表的第6个元素），则移动元素个数为（C）。A．12B．55.序列12,16,8,4按顺序依次进栈，按该栈的可能输出序列依次入队列，该队列的不可能输出序列是（B）。(进栈、出栈可以交替进行）。A．16,12,8,4B．4,8,12,16C．8,4,16,12D．16,12,4,86．栈和队列的共同特点是（A）。A．都是线性结构B．元素都可以随机进出C．都是先进后出D．都是先进先出7.在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，对该队列进行出队操作,并把结点的值保存在变量e中,其运算为（C）。A．e=f->data；r=r->next;B．e=f->data；r->next=r;C．e=f->data；f=f->next;D．e=f->data；f->next=f;8．元素1，3，5，7按顺序依次入队列，按该队列的出队序列进栈，该栈的可能输出序列是（D）（进栈出栈可以交替进行）。A．7，5，1，3B．7，3，1，5C．5，1，3，7D．7，5，3，19.数据的逻辑结构在计算机内存中的表示是(B)。A.给相关变量分配存储单元B.数据的存储结构C.数据的逻辑结构D.算法的具体体现10．在一个不带头结点的链队中，假设f和r分别为队头和队尾指针，则对该队列进行出队操作中并把结点的值保存在变量e中,其运算为e=fdata；和（C）。A．r=rnext;B．rnext=r;C．f=fnext;D．fnext=f11.以下说法正确的是(B)。A.线性表的链式存储结构必须占用连续的存储空间B.一种逻辑结构可以有不同的存储结构C．一种逻辑结构只能有唯一的存储结构D．线性表的顺序存储结构不必占用连续的存储空间12．设有一个对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），B数组共有45个元素,则该矩阵是（D）阶的对称矩阵。A．15B．11C．10D．913．在一个单链表中要删除p所指结点的后继结点，可执行q=p->next;和（A）。A．p->next=q->next;B．p=q->next;C．p->next=q;D．p->next=q;14.下列是C语言中〝abcd321ABCD〞的子串的选项是（A）。A.〝21ABC〞B.〝abcABCD〞C.abcDD.〝321a〞15.在数据结构和算法中，与所使用的计算机有关的是（B）。A．数据元数间的抽象关系B．数据的存储结构C．算法的时间复杂度D．数据的逻辑结构16.字符串a1=〝BEIJING〞,a2=〝BEF〞,a3=〝BEFANG〞,a4=“BEFI〞最小的是（B）.A.a1B.a2C.a3D.a417.以下表中可以随机访问的是（D）。A．单向链表B．双向链表C．单向循环链表D．顺序表18．一棵有20个结点采用链式存储的二叉树中，共有（A）个指针域为空。A．21B．20C．19D．1819.头指针为head的不带头结点的单向链表为空的判定条件是逻辑表达式(A)为真。A.head==NULLB.head->next==NULLC.head->next=NULLD.head->next!=NULL20．设一棵哈夫曼树共有18个叶结点，则该树有（C）个非叶结点。A．18B．19C．17D．1621.设有一个长度为32的顺序表，要在第5个元素之前插入1个元素（也就是插入元素作为新表的第5个元素），需移动元素个数为（B）。A．25B．28C.5D．622．如图1所示的一个图，若从顶点g出发，按深度优先搜索法进行遍历，则可能得到的一种顶点序列为（D）。A．gabecdfB．gacfebdC．gaebcfdD．gaedfcbbbdfeCag图123．设有一个长度为33的顺序表，要删除第10个元素(下标从1开始)需移动元素的个数为（C）。A．11B．10C．23D．1424．线性表以（B）方式存储，能进行折半查找。A．关键字有序的B．关键字有序的顺序C．链接D．顺序25．设有一个28阶的对称矩阵A，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始），则数组中第26号元素对应于矩阵中的元素是（A）。A．a7,5,B．a7,6C．a6,5D．a26．有一个长度为8的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（D）。A．22/8B．20/827.在一个不带头结点的单循环链表中，p、q分别指向表中第一个结点和尾结点，现要删除第一个结点，且p、q仍然分别指向新表中第一个结点和尾结点。可用的语句是p=p->next;和（D）。A．p=q->next;B．p->next=q;C．q=p;D．q->next=p;28.排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是（A）。A．折半插入排序B．直接插入排序C．归并排序D．选择排序29．在一棵二叉树中，若编号为16的结点是其双亲结点的左孩子，则他的双亲结点的顺序编号为（B）。A．7B．8C．32D．3330．排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的一端的方法，称为（C）排序。A．堆B．冒泡C．选择D．快速二、填空题1.数据的逻辑结构在计算机中的表示称为__物理(存储)______结构。2.结构中的数据元素存在一对多的关系称为__树形______结构。3.四类基本结构分别为____集合线性树形图状___结构。4.栈的操作特点是____先进后出__________。5.队列的操作特点是先进____先出____。6.广义表的(a,(a,b),d,e,((i,j),k))深度是____3____。7.广义表((b,a,c),c,d,(e,i,j,k))的表尾是___(c,d,(e,i,j,k))_____。8.广义表((a,b),d,e,((i,j),k))的长度是______4__。9.设有一个长度为20的顺序表,第8号元素到第20号元素依次存放的值为8,9,…,20。某人想要在第8号元素前插入1个元素7（也就是插入元素作为新表的第8个元素），程序中他的做法是用语句for(i=8;i<=20;i++)a[i+1]=a[i];a[8]=7;即从第8号元素开始,直到第20号元素,每个元素依次向后(右）移动1个位置,然后把7存放在第8号位置。事实上这样做是错误的.其结果是新表中第20号元素的值为___8_____。10.设顺序队列的类型为typedefstruct{ElemTypedata[MaxSise];intfront,rear;}Squeue;Squeue*sq;sq为指向顺序队列的指针变量，要进行元素的出队操作，并把元素赋给边量x,按教科书约定,可用语句x=sq->data[sq->front];和__sq->fronf++;______。11．设有一棵有38个结点的完全二叉树，该树共有_____6____层。（根所在结点为第1层）12.设顺序队列的类型为typedefstruct{ElemTypedata[MaxSise];intfront,rear;}Squeue;Squeue*sq;sq为指向顺序队列的指针变量，要进行新元素x的入队操作，按教课书约定,可用语句sq->data[sq->rear]=x;和___sq->rear++;_____。13．一棵有18个结点的二叉树，其2度结点数的个数为8，则该树共有___1____个1度结点。14.序列14,12,15,13,18,16,采用冒泡排序算法,经一趟冒泡后,序列的结果是___12,14,13,15,16,18_____。（由小到大排序）15.对一组记录（1，3，9，2，12，7，5，4，6）进行直接插入排序(由小到大排序)，当把第6个记录7插入有序表，为寻找插入位置需比较_____3___次。16.数据结构中,_____数据元素___之间的抽象关系称为逻辑结构。17.序列5,3,8,4,7,6,采用冒泡排序算法,经一趟冒泡后,序列的结果是___3,5,4,7,6,8_____。(按升序排序)18.循环队列中，设front和rear分别为队头和队尾指针，(最多元素为MaxSize,),判断循环队列为空的条件为____front==rear____为真。19.广义表(b,a,(c,b),f,e,((i,j),k))的长度是____6____。20.排序算法中，从尚未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（要求比较次数尽量少），然后将其放入已排序序列的正确位置的方法是折半插入排序。21．一棵有18个叶结点的哈夫曼树，则该树共有____17___个非叶结点。22.对稀疏矩阵进行压缩存储,可采用三元组表,矩阵元素a3,4对应的三元组为__(3,4,a3,4)_____。23．对稀疏矩阵进行压缩存储,可采用三元组表，一个8行7列的稀疏矩阵A共有51个零元素，其相应的三元组表共有____5___个元素24．在双向链表中，要删除p所指的结点，其中所用的一条语句（p->next）->prior=p->prior;的功能是：使P所指结点的直接后继的左指针指向___P所指结点的直接前驱_____。综合题1.设数据集合a={6,17,10,13,8,15,12,18,14}（1）依次取a中各数据，构造一棵二叉排序树。（2）给出对该二叉树中序遍历的序列（3）对该二叉树进行查找，成功查找到14要进行多少次元素间的比较？图2(2)中序遍历6,8,10,12,13,14,15,17,18(3)6次2.设数据集合a={62,74,30,15,56,48}（1）依次取a中各数据，构造一棵二叉排序树。（2）对该二叉树进行查找，不成功查找有多少种可能？画出不成功查找树的示意图。（3）不成功查找的平均查找长度是多少?（4）为了成功查找到48需要进行多少次元素间的比较?（5）给出对该二叉树后序遍历的序列。(1)图3(2)图47种可能(3)(2*2+3*3+4*2)/7=21/7(4)4次(5)15,48,56,30,74,623．设有序表为(2,5,11,12,30,48,58),元素的序号依次为1,2,3,……，7.（1）画出对上述查找表进行折半查找所对应的判定树（树中结点用序号表示）（2）说明成功查找到元素11需要经过多少次比较？(3)在等概率条件下,给出成功查找的平均查找长度（1）图5(2)3次(3)(1+2*2+3*4)/7=17/74．设有序表为（3，9，15，26，38，41，53，74，81，96，97，99），元素的序号依次为1,2,……,12。（1）说出有哪几个元素需要经过3次元素间的比较才能成功查到。（2）画出对上述有序表进行折半查找所对应的判定树（树结点用序号表示）。（3）设查找5号元素(38)，需要进行多少次元素间的比较才能确定不能查到,依次和哪些元素进行了比较？（要求写出具体元素）。（4）给出后序遍历该二叉树的序列。(5)给出中序遍历该二叉树的序列。(1)3,26,53,97(2)图7(3)4次41,15,26,38(4)2(9),1(3),5(38),4(26),3(15),8(74),7(53),10(96),12(99),11(97),9(81),6(41)（5）1(3）,2(9),3(15),4(26),5(38),6(41),7(53),8(74),9(81),10(96),11(97),12(99)5.(1)如图1所示，若从顶点a出发，首先经过顶点c按广度优先搜索法进行遍历，给出可能得到的一种顶点序列。(2)如图1所示，给出从顶点h出发，首先经过顶点d和e按深度优先搜索法进行遍历，给出可能得到的一种顶点序列。aa阿decfhecdeccdeceecb图1（3）一组记录的关键字序列为（80,57,41,39,46,47），利用堆排序的方法的方法建立小根堆(堆顶元素是最小元素）,给出按筛选法建立的的初始堆。(1)acefdbh(2)hdeacfb（3）394641578047四、程序填空题1．以下冒泡法程序对存放在a[1]，a[2]，……，a[n]中的序列进行冒泡排序完成程序中的空格部分，其中n是元素个数，程序按升序排列。voidbsort(NODEa[],int){NODEtemp;inti,j,flag;for(j=1;j<=n-1;(1)){flag=0;for(i=1;(2);i++)if(a[i].key>a[i+1].key){flag=1;(3)a[i]=a[i+1];(4);}if(flag==0)break;}}程序中flag的功能是(5)1.(1)j++(2)i<=n-j(3)temp=a[i];(4)a[i+1]=temp;(5)判断某一趟排序中是否有元素交换2.学生信息存放在结构数组中，每个数组元素存放一个学生的信息，下标从0到n-1。数组元素按学号num由小到大有序排列，以下函数在a[0]到a[n-1]中，用折半查找算法查找关键字num等于k的记录，查找成功返回该记录的下标(数组元素的下标)。失败时返回-1，完成程序中的空格。typedefstruct{charsex;intnum;……}NODE;intBinary_Search(NODEa[],intn,intk){intlow,mid,high;low=0;high=n-1;while(___(1)_____){mid=(low+high)/2;if(a[mid].num==k)return__(2)______;elseif(___(3)_____)low=mid+1;else__(4)______;}return-1;}(1)low<=high(2)mid(3)a[mid].num<k(4)high=mid-1;3．以下函数为链栈的出栈操作，出栈结点的数据由x返回structnode{ElemTypedata;structnode*next;};ElemTypePop(){intx;if(top==___(1)_____){printf("栈下溢错误！\n");exit(1);}x=___(2)_____;top=___(3)_____;returnx;}(1)NULL(2)top->data(3)top->next4．以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回值是指向树结点的结构指针p（查找成功p指向查找到的树结点，不成功，则p指向为NULL），完成程序中的空格。structbnode{intkey;structbnode*left;structbnode*right;};typedefstructbnodeBnodeBnode*BSearch(Bnode*bt,intk)/*bt用于接收二叉排序树的根结点的指针，k用以接收要查找的关键字*/{Bnode*p;if(bt==NULL)return(bt);___(1)_____while(p->key!=__(2)___) {if(k<p->key)___(3)_____;else___(4)_____;if(p==NULL)break;}returnp;}(1)p=bt;(2)k(3)p=p->left(4)p=p->right综合练习一答案一、单项选择题1．C2．C3．A4．D5．A6．A7．B8．B9．A10．A11．A12．D13．C14．C15．C16．C17．C18．B19．A20．B21．B22．B23．C24．C25．C26．D27．A28．D29．B30．D二、填空题1.62.树形3.逻辑4.图状5.先出6.rear==front为真7.（b,a,c）8.69.1810.O(n)11.512.1813.614.n+115.二叉排序树16.,417.10，12，11，13，14，1618.3419.1520.3121.