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

数据结构(本）期末综合练习202３年6月为了帮助同学们进行期末复习,特拟定以下两套期末综合练习题,望同学们逐个认真完毕。数据结构(本)期末综合练习一一、单项选择题1．数据元素是数据的基本单位,它（)。A．只能有一个数据项组成B.至少有二个数据项组成C.至少有一个数据项为指针类型D．可以是一个数据项也可以由若干个数据项组成２．（）是性质相同的数据元素的集合,是数据的子集。A．数据对象Ｂ．数据元素C．数据结构D.数据项3.线性表的顺序结构中，（）。A.逻辑上相邻的元素在物理位置上不一定相邻B．逻辑上相邻的元素在物理位置上也相邻C.数据元素是不能随机访问的D.进行数据元素的插入、删除效率较高4．设链表中的结点是ＮＯＤＥ类型的结构体变量,且有ＮＯＤE＊p；为了申请一个新结点,并由p指向该结点,可用以下语句()。A.p＝(NODＥ*)malloc（sｉzｅof(p))；B.ｐ=(*NODE)maｌloc(sizeoｆ(ＮＯDE））；C．p=(NODＥ)mａlｌoc(sizeof(p));Ｄ.ｐ=(NＯDE*)ｍalｌoc(sｉzｅｏf(ＮODE））;5.以下表中可以随机访问的是（）。A.单向链表B．顺序表Ｃ．单向循环链表D.双向链表6．设顺序存储的线性长度为ｎ,要在第ｉ个元素之前插入一个新元素,按课本的算法当i=(）时,移动元素次数为２A．n/２B.nC．n-1C．17.设顺序存储的线性表长度为n，对于删除操作，设删除位置是等概率的,则删除一个元素平均移动元素的次数为(）。A.(n+１）/２B.nC．2nD．ｎ－i8．一个栈的进栈序列是1,2,3，４，则栈的不也许的出栈序列是（）（进出栈操作可以交替进行)A．3,2，４，１B．３,2，1，4Ｃ.4，３,２，1D．1，4，2，39.设ｔop是一个链栈的栈顶指针,栈中每个结点由一个数据域ｄata和指针域ｎeｘｔ组成，设用x接受栈顶元素,则出栈操作为（)。Ａ.ｔoｐ＝ｔop-＞nｅxt;ｘ=tｏp->data;B．ｘ=top->ｄata;top=toｐ－＞ｎext；C.x=top－>nｅxt;top＝toｐ->data;D．top->next=top；x=ｔｏp-＞datａ;1０．设有一个带头结点的链队列，队列中每个结点由一个数据域ｄata和指针域next组成,fronｔ和reａｒ分别为链队列的头指针和尾指针。设p指向要入队的新结点(该结点已被赋值)，则入队操作为（）。A.rｅａｒ->next=p;rｅar=p；B.reaｒ－>neｘｔ=ｐ;p=reａr;Ｃ.p=rｅaｒ->ｎext;ｒear=ｐ;D.reａr=p;rear－>next=p;１1．以下说法对的的是()。A．队列是后进先出B.栈的特点是后进后出C.栈的删除和插入操作都只能在栈顶进行Ｄ.队列的删除和插入操作都只能在队头进行12.以下说法不对的的是()。A．顺序栈中,栈满时再进行进栈操作称为“上溢”B.顺序栈中,栈空时再作出栈栈操作称为“下溢”C．顺序队列中，队列的头指针和尾指针均超越队列存储空间的上界,则队列已空Ｄ．顺序队列中,当尾指针已经超越队列存储空间的上界，则一定是队列已满13.串函数SｔｒCmp（“ａbA”,”aba”)的值为（)。Ａ．1B.0C.“aｂAaba”D1４．设有一个2０阶的对称矩阵A，采用压缩存储方式,将其下三角部分以行序为主序存储到一维数组中（矩阵A的第一个元素为a11,数组ｂ的下标从1开始），则矩阵元素a8,５在一维数组b中的下标是()。A．30B．28Ｃ．４0Ｄ15．设有一个12阶的对称矩阵Ａ，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组ｂ中（矩阵Ａ的第一个元素为a1，1，数组b的下标从1开始)，则矩阵Ａ中第4行的元素在数组ｂ中的下标i一定有（)。A．７≤ｉ≤1０Ｂ.１1≤ｉ≤15Ｃ.9≤i≤１４D．６≤i≤９1６．深度为5的完全二叉树第5层上有4个结点，该树一共有(）个结点。A．２８B．３0C.３1Ｄ17.已知一个图的边数为m，则该图的所有顶点的度数之和为()。A．2mＢ.mC.2m+１D.m/２1８．已知一个图的所有顶点的度数之和为m,则ｍ一定不也许是()。Ａ.4B.8C．1２D1９．以下说法不对的的是（）。A．连通图G一定存在生成树Ｂ．连通图Ｇ的生成树中一定包含G的所有顶点Ｃ.连通图G的生成树中不一定包含Ｇ的所有边D.连通图G的生成树可以是不连通的20.以下说法对的的是（）。A．连通图G的生成树中可以包含回路B．连通图G的生成树可以是不连通的Ｃ.连通图G的生成树一定是连通而不包含回路的D.连通图G的生成树一定是唯一的21.散列查找的原理是(）。Ａ.在待查记录的关键字值与该记录的存储位置之间建立拟定的相应关系B．按待查记录的关键字有序的顺序方式存储Ｃ．按关键字值的比较进行查找Ｄ.基于二分查找的方法22．对n个元素进行冒泡排序，通常要进行ｎ-1趟冒泡,在第j趟冒泡中共要进行（)次元素间的比较。A.jＢ．ｊ-1C.n-ｊD2３．排序过程中，每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置，直到所有排好序为止,该排序算法是(）。A.直接插入排序Ｂ．快速排序C．冒泡排序D．选择排序２4.在排序过程中，可以有效地减少一趟排序过程中元素间的比较次数的算法是(）。A.冒泡B.选择Ｃ．折半插入Ｄ.直接插入２5．采用顺序查找法对长度为n的线性表进行查找（不采用表尾设监视哨的方法）,最坏的情况下要进行()次元素间的比较。A.ｎ+２B.nC．n-１D．n／２26．如图若从顶点a出发按深度优先搜索法进行遍历，则也许得到的顶点序列为（)。abecabecdfB．abeｄcfＣ.acebdfD．acｆbde图1２７.如图若从顶点a出发按广度优先搜索法进行遍历,则也许得到的顶点序列为()。ababecdhgfB.ａebcghdfC．aeｄfbｃghD.abｅcｄfgh图２28.一棵哈夫曼树有ｎ个叶子结点(终端结点），该树总共有(）个结点。Ａ．2n-2B．２n-１C.２nD．29.一棵哈夫曼树总共有２3个结点，该树共有()个叶结点（终端结点)Ａ.１０B.1１C．1２D.133０.数据的()结构与所使用的计算机无关。A.逻辑Ｂ．物理Ｃ．存储D.逻辑与存储二、填空题1．通常数据的逻辑结构涉及＿__＿、____、____、____四种类型。２.通常可以把一本具有不同章节的书的目录结构抽象成_＿__＿___结构。３.设有一个单向链表,结点的指针域为nｅxt,头指针为heａd,p指向尾结点，为了使该单向链表改为单向循环链表，可用语句＿_____＿＿。4.要在一个单向链表中p所指向的结点之后插入一个s所指向的新结点,若链表中结点的指针域为next，可执行__＿＿＿___和p－＞ｎeｘt=ｓ;的操作。5．设有一个单向循环链表，头指针为ｈeａd，链表中结点的指针域为next，p指向尾结点的直接前驱结点,若要删除尾结点，得到一个新的单向循环链表,可执行操作___＿__＿_。6.设有一个非空的链栈，栈顶指针为hs,要进行出栈操作，用x保存出栈结点的值,栈结点的指针域为nｅxｔ,则可执行x=hｓ->daｔa;＿_______。7．在一个链队中，f和r分别为队头和队尾指针,队结点的指针域为ｎｅxｔ,则插入一个s所指结点的操作为＿__＿＿__＿；r＝s;8.在一个不带头结点的非空链队中，ｆ和r分别为队头和队尾指针,队结点的数据域为datａ,指针域为ｎexｔ,若要进行出队操作,并用变量x存放出队元素的数据值,则相关操作为x=f->datａ;＿___＿_＿_。9.循环队列的队头指针为f，队尾指针为r,当＿___＿时表白队列为空。１0．循环队列的最大存储空间为MaｘSize=8,采用少用一个元素空间以有效的判断栈空或栈满,若队头指针ｆront=４，则当队尾指针rear=___＿＿＿__时，队列为空,当rear=________时,队列有６个元素。11．“Ａ”在存储时占＿__＿_＿__个字节。12.稀疏矩阵存储时,采用一个由＿_＿_、____、＿_＿_3部分信息组成的三元组唯一拟定矩阵中的一个非零元素。１3.一棵二叉树没有单分支结点,有6个叶结点，则该树总共有_＿___＿_＿个结点。14．一棵二叉树顺序编号为6的结点(树中各结点的编号与等深度的完全二叉树中相应位置上结点的编号相同），若它存在右孩子，则右孩子的编号为__＿____＿。15.按照二叉树的递归定义，对二叉树遍历的常用算法有____、____、＿___三种。16．结构中的数据元素存在多对多的关系称为＿＿__＿___结构。１7.把数据存储到计算机中,并具体体现数据之间的逻辑结构称为_＿___＿__结构。18.结构中的数据元素存在一对多的关系称为______＿_结构。１9.如图3所示的二叉树,其后序遍历序列为。eefgibachd图320．如图４所示的二叉树,其前序遍历序列为＿＿__＿＿_＿＿。ggfabdec图４21．二叉树为二叉排序的充足必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是＿_______＿＿的。(回答对的或不对的）22．在队列的顺序存储结构中，当插入一个新的队列元素时，指针的值增1，当删除一个元素队列时，指针的值增1。23．根据搜索方法的不同，图的遍历有_＿__、____两种方法2４．循环队列的引入，目的是为了克服。三、综合题1.（1)已知某二叉树的后序遍历序列是debca,中序遍历序列是dbeａc，试画出该二叉树(2）若上述二叉树的各个结点的字符分别代表不同的整数(其中没有相等的)，并恰好使该树成为一棵二叉排序树，试给出a、b、c、d、e的大小关系（3)给出该树的前序遍历序列2．(1）设head1和p１分别是不带头结点的单向链表Ａ的头指针和尾指针,ｈｅaｄ2和p2分别是不带头结点的单向链表B的头指针和尾指针，若要把B链表接到A链表之后，得到一个以ｈeａd１为头指针的单向循环链表，写出其中两个关键的赋值语句（不用完整程序，结点的链域为ｎext)。(2）单向链表的链域为nｅｘｔ，设指针p指向单向链表中的某个结点,指针s指向一个要插入链表的新结点,现要把ｓ所指结点插入ｐ所指结点之后，某学生采用以下语句:ｐ->next＝s；s->ｎext＝p->next；这样做对的吗?若对的则回答对的，若不对的则说明应如何改写3.(１）设有一个整数序列{4０,2８,6,7２，100,3,５4｝依次取出序列中的数，构造一棵二叉排序树(2）对上述二叉排序树，在等概率条件下，求成功查找的平均查找长度４.（1）画出对长度为１０的有序表进行折半查找的鉴定树(以序号1，２，……１0表达树结点）(2)对上述序列进行折半查找,求等概率条件下，成功查找的平均查找长度５.（1)运用筛选过程把序列{４2,82，67,102，16，32，57，52}建成堆(小根堆),画出相应的完全二叉树（不规定中间过程）(2）写出对上述堆相应的完全二叉树进行中序遍历得到的序列6.(１)运用筛选法，把序列{37，77，６2,97,11,27，52，４7}建成堆(小根堆），画出相应的完全二叉树（2)写出对上述堆所相应的二叉树进行前序遍历得到的序列四、程序填空题１.以下函数在a[0］到a［ｎ-1］中,用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标,失败时返回-1，完毕程序中的空格ｔｙpｅｄｅfsｔrｕｃt{iｎtkey;……}ＮOＤE;intBinaｒy_Search(NODEa［],intn,ｉnｔk){ｉｎtloｗ，mid，hｉgｈ;ｌｏw=0;hiｇh＝n-1;wｈｉlｅ(＿__(1)_____){ｍｉd=（low＋high)/2;if（a[ｍiｄ].kｅy==k)reｔurn＿_(２)___＿__;ﻩelseiｆ(___(3)＿__＿＿)lｏｗ=mid+1;ﻩｅlse__(４）_＿___＿； ｝_＿_(5)____＿；ﻩ}2．以下函数为直接选择排序算法,对a[1］，a[2］,…a[n]中的记录进行直接选择排序,完毕程序中的空格ｔypedeｆstrucｔ{intkey；……｝ＮODE;voiｄｓelsｏrt(NODEａ[],intn){ inti，j,k; NODEtemp； ｆｏｒ（i=１;ｉ<=_＿_（1)_____；i+＋)ﻩ{ ﻩk=ｉ;ﻩ ｆｏr(ｊ＝i＋1;j<=＿__（２)_＿___;j++)ﻩﻩ iｆ（a[j].keｙ<a［k].ｋey)＿＿(３)＿＿_＿__；ﻩ if(i!=k) { ｔemp=ａ[i]； ﻩ＿_＿（4)___＿_; ﻩ ＿＿_＿(5)＿___;ﻩﻩ} }}3.以下函数为链队列的入队操作，x为要入队的结点的数据域的值，front、rear分别是链队列的队头、队尾指针ｓtｒuｃtnｏde｛EleｍTｙpedata;structnode*nexｔ;};strｕｃｔnodｅ*frｏnt,＊ｒｅar；vｏidＩｎQuｅuｅ(ＥlemTｙpex){stｒuctｎｏdｅ＊p;p=（strｕｃｔnｏde＊）＿__（1)＿__＿_；p->data=x;p－>nｅxt=NUＬL;＿__(2)_____；ｒeａr=_＿_(3)＿_＿__;｝4.以下程序是中序遍历二叉树的递归算法的程序,完毕程序中空格部分（树结构中左、右指针域分别为ｌｅｆt和right,数据域data为字符型,BT指向根结点)。voidInordｅr(ｓtructＢTｒeeNoｄｅ*BＴ)｛if(ＢT!＝NUＬＬ){(１）;(2）;(３)；}}答案一、单项选择题１.Ｄ2．Ａ3.B4.D５.Ｂ6.C７．A8．Ｄ９．B１0.A1１．Ｃ１2.D13.D14.Ｄ15.A16.D17.Ａ1８．D19.D２0．C2１．A22.C23.A2４．C2５.Ｂ26．B27.D28.B29．C3０.A二、填空题1.集合;线性；树形；图状2.树形３.p－＞nｅxt=heａd;4．s->nexｔ=p-＞neｘｔ；5.ｐ->next=hｅad;６.hs＝ｈs->neｘt;7.ｒ-＞next＝ｓ８.f＝f－>nｅxt；９.r==ｆ1０．4；211．1;２12．行号；列号；非零元13.11１4.1３1５.先序；中序；后序１6．图状1７.物理(存储)18．树形１９.gdbeihfca2０.ａｂdｅfcg21．错误2２．尾头２3.深度优先广度优先24.假上溢三、综合应用题abceabced（2）d<b<e<ａ<c（3)ａbｄｅc2．(1）p１-＞nｅxt=heaｄ２；p2->next=hｅａd1；(2）不对，s-＞next＝p->neｘｔ;p－>nｅxｔ=s；4028723100544028723100546(2)AＳL=(1x１＋2x2+3x3＋4)／７=１８/7528452849631071(2）ASＬ=(1x1+2x2+3x4+4x３）/1０＝29／105.16423252571642325257678242826752573216102102初始树堆102初始树堆(2)102,52,42，82,16,67，３2，5７初始树堆11372747初始树堆11372747526277973777624752271197（2）１1，37,47,97,77，27，62,５2四、程序填空题１．（1)low<=higｈ(2）mｉd(3)a[mid].keｙ<k;（4)high=mid-１(5）reｔｕrn-1;2.(1）n-１(2)n(３）ｋ＝j(4)a[i]=a[k](5)a[k]=temｐ３.（1）malｌoｃ(sizeof(ｓtrｕctｎodｅ))(2)reａｒ->nｅxｔ＝p(3）p4．（1）Iｎoｒder(BＴ->ｌeft)(２)priｎtf(“%c”，ＢT->dａｔa)(3)Inｏrder(BT-＞rｉgｈt)数据结构(本)期末综合练习二一、单项选择题1．从n个数中选取最大元素(）。A．基本操作是数据元素间的互换B．算法的时间复杂度是Ｏ(n)C．算法的时间复杂度是O(ｎ2)D.需要进行（n＋１)次数据元素间的比较2.线性表采用链式存储时，其地址（）。Ａ.一定是不连续的B.必须是连续的C．部分地址必须是连续的D．可以连续也可以不连续3．设heａｄ为非空的单向循环链表头指针，ｐ指向链表的尾结点，则满足逻辑表达式（）的值为真。Ａ.p-＞neｘt=ＮUＬＬB.ｐ-＞nｅxt=＝hｅaｄＣ.p->neｘｔ＝headD.p==NＵLL4．带头结点的单向链表的头指针为heａd，该链表为空的鉴定条件是(）的值为真。A．head==NULＬB.ｈｅaｄ-＞ｎext==heａｄＣ．heａd==head->nexｔD.head->nｅxt＝=NUＬL5．设顺序存储的线性表长度为n，要删除第i个元素，按课本的算法,当i=(）时，移动元素的次数为3A.3Ｂ．n／2C.n-3D6.设顺序存储的线性表长度为ｎ，对于插入操作，设插入位置是等概率的,则插入一个元素平均移动元素的次数为（)。Ａ.nB.n/２C．n-１D．n-i+17.一个栈的进栈序列是a,b，c,d,则栈的不也许的出栈序列是(）。A．ｄｃbaB.bcadC．cbaｄＤ.ａｄbｃ8．一个栈的进栈序列是5,6，7，８,则栈的不也许的出栈序列是（）(进出栈操作可以交替进行）A.7,6,８，5B.5,8，６,7Ｃ．7，6，５，8D．８,7，６，５9.设有一个带头结点的链队列,队列中每个结点由一个数据域daｔａ和指针域ｎext组成,fｒonｔ和rear分别为链队列的头指针和尾指针,要执行出队操作，用x保存出队元素的值，p为指向结点类型的指针,可执行如下操作:ｐ=fｒoｎｔ->nexｔ;x＝p->dａta；然后指行（)。A.fronｔ=p－>next;B．ｆront－>next=p;C．fｒｏnｔ＝p;Ｄ.ｆront-＞ｎext=p－>neｘt;１0．栈和队列的相同点是(）。A.都是后进先出Ｂ.都是后进后出Ｃ．逻辑结构与线性表不同D.逻辑结构与线性表相同，都是操作规则受到限制的线性表11．在C语言中，存储字符串“ＡＢCD”需要占用()字节。A.4B.2Ｃ．５D１2．在Ｃ语言中,运用数组ａ存放字符串“Ｈellｏ”,以下语句中对的的是(）。A.ｃｈａra[10］＝“Hello”;B.chara［１0］；ａ=“Hellｏ”;C．chａra［10］＝‘Ｈｅlｌｏ’;D．chara［１0]={‘Ｈ’,’e’,’l’,’l’，’ｏ’}；13．设有一个1０阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组ｂ中。（矩阵Ａ的第一个元素为a１，1,数组b的下标从1开始），则矩阵元素a5,3相应一维数组b的数组元素是(）。Ａ．b[18]Ｂ．b[8]C．b［1３]D．b[10]１4．设有一个15阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。(矩阵A的第一个元素为a1,1,数组b的下标从1开始）,则数组元素b［１3］相应A的矩阵元素是（）。A．ａ5,3Ｂ．a6,４C．a7,2Ｄ15.深度为5的完全二叉树共有20个结点,则第5层上有（)个结点(根所在结点为第一层)。A．３B.８C16.一棵完全二叉树共有３０个结点，则该树一共有()层(根结点所在层为第一层)。A．6B.4Ｃ．3D１7.已知一个图的所有顶点的度数之和为ｍ,且m是以下4中情况之一，则ｍ只也许是(）。A．９B．７C．1５D１8.以下说法对的的是（）。A．连通图G的生成树中不一定包含G的所有顶点Ｂ.连通图G的生成树中一定要包含G的所有边C.连通图G一定存在生成树Ｄ.连通图G的生成树一定是唯一的19．线性表只要以（）方式存储就能进行折半查找。A.链接B．顺序C.关键字有序的顺序D．二叉树2０．对二叉排序树进行(）遍历,遍历所得到的序列是有序序列。Ａ.按层次Ｂ.前序Ｃ．中序D.后序21．对n个元素进行冒泡排序若某趟冒泡中只进行了()次元素间的互换,则表白序列已经排好序。A．1B．２Ｃ.0D22.以下排序算法中,在一趟排序过程中,除了其它相关操作外，只进行一次元素间的互换的算法是（）。A.冒泡B.直接选择C．直接插入D．折半插入２3.在对一组元素(６4,4８,1０6,33,25，82，70,55，９３）进行直接插入排序时，当进行到要把第7个元素７0插入到已经排好序的子表时，为找到插入位置，需进行（）次元素间的比较(指由小到大排序）。A．６B.2C.3D2４．对长度为n的线性表进行顺序查找,在等概率情况下,平均查找长度为（)。A.nＢ．（n＋1）/2C.2ｎD．ｎ-１ＳHAＰE\＊MERGEFORMＡT25．如图，若从顶点a出发按广度优先搜索法进行遍历,则也许得到的顶点序列为（）。abecdfgabecdfgB．aｃｆedｇbC.abecｄgfD.ａｂecfdg26.如图若从顶点a出发按深度优先搜索法进行遍历,则也许得到的顶点序列为（)。ababecdfgＢ．aeｄcbｇfC．acfebdｇD.aeｃｂdgf27．一棵哈夫曼树有10个非叶子结点(非终端结点）,该树总共有（）个结点。A．21B．20C．２2８．一棵哈夫曼树有１2个叶子结点（终端结点）,该树总共有(）个结点。A．21B．2２C.23Ｄ．２４29.队列的插入操作在（）进行。A.队头B.队尾C．队头或队尾D.在任意指定位置３0．队列的删除操作在（)进行。A.队尾B.队头C.队头或队尾D.在任意指定位置二、填空题1.通常可以把某城市中各公交站点间的线路图抽象成________结构。２.结构中的元素之间存在多对多的关系称为＿_______结构。3.要在一个单向链表中删除p所指向的结点，已知ｑ指向p所指结点的直接前驱结点,若链表中结点的指针域为nexｔ，则可执行___＿___＿。4.设有一个单向循环链表,结点的指针域为ｎext,头指针为heaｄ,指针ｐ指向表中某结点，若逻辑表达式＿__＿＿___的结果为真，则p所指结点为尾结点。5．设有一个链栈，栈顶指针为hs，现有一个s所指向的结点要入栈,则可执行操作_______＿和hｓ=s;６．设有一个链栈，栈顶指针为hｓ,现有一个s所指向的结点要入栈,则可执行操作s->next=hs；_____＿__。7.在一个不带头结点的非空链队中，ｆ和r分别为队头和队尾指针，队结点的数据域为ｄaｔa，指针域为next，若要进行出队操作，并用变量x存放出队元素的数据值,则相关操作为___＿_＿_＿;____＿＿__。8.在一个链队中，f和ｒ分别为队头和队尾指针,队结点的指针域为ｎｅxt,ｓ指向一个要入队的结点，则入队操作为__＿_____;________；９.顺序存储字符串“ABＣD”需要占用_＿＿__＿＿_个字节。10.循环队列的最大存储空间为MaxSize＝6，采用少用一个元素空间以有效地判断栈空或栈满,若队头指针fｒｏnt＝4,当队尾指针rear=_＿＿_＿___时队满，队列中共有＿_______个元素。1１.一棵二叉树叶结点（终端结点)数为5，单分支结点数为2，该树共有＿＿__＿_个结点１2．程序段chａｒ＊s=”aBcＤ”；n=０;ｗhile(*s！＝’\0’{if(＊s>=’a’&＆＊s<＝’ｚ’)n＋+；ｓ++;}执行后ｎ＝___＿___＿13.设一棵完全二叉树,其最高层上最右边的叶结点的编号为奇数,该叶节点的双亲结点的编号为１0,该完全二叉树一共有＿__＿____个结点。１4.一棵二叉树中顺序编号为5的结点（树中各结点的编号与等深度的完全二叉中相应位置上结点的编号相同)，若它存在左孩子，则左孩子的编号为______＿＿。１５．结构中的数据元素存在一对多的关系称为＿＿______结构。１6.根据搜索方法的不同,图的遍历有＿_______两种方法。1７.结构中的数据元素存在一对一的关系称为__＿_____结构。18．结构中的数据元素存在多对多的关系称为_______＿结构。19.如图所示的二叉树,其后序遍历序列为。eefgibachd20．一棵有n个叶结点的二叉树，其每一个非叶结点的度数都为2,则该树共有_______个结点。２1.图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是____＿_的。(回答对的或不对的)22.串的两种最基本的存储方式分别是＿_＿____和____＿__＿。23．按某关键字对记录序列排序,若关键字的记录在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。24.按某关键字对记录序列排序，若关键字的记录在排序前和排序后仍保持它们的前后关系,则排序算法是稳定的,否则是不稳定的。三、综合题1.（1）一组记录的关键字序列为｛45，40，６5,４3,35,95}写出运用快速排序的方法,以第一个记录为基准得到的一趟划分的结果(规定给出一趟划分中每次扫描和互换的结果）（2)同样对序列{45，40,65,43,3５，95}运用直接插入排序，写出逐次插入过程（从第一个元素一直到第六个元素)。２．设有一个不带头结点的单向链表,头指针为head,结点类型为NOＤＥ，每个结点包含一个数据域data和一个指针域next,该链表有两个结点，ｐ指向第二个结点(尾结点）,按以下规定写出相应语句(不规定完整程序，（1）、（２）、(3）、（4)是一个连续的过程)。(1)新开辟一个结点,使指针s指向该结点，结点的数据成员daｔa赋值为１(2）把该结点插入链表的尾部,释放指针s的指向（3）删除链表的第一个结点(4)已知p1指向另一个新结点，把它插入到ｐ所指结点和尾结点之间３.（1）运用筛选过程把序列{4２,82,6７,102,16,32，5７,52}建成堆(小根堆），画出相应的完全二叉树（不规定中间过程)(２)写出对上述堆相应的完全二叉树进行中序遍历得到的序列4.（１)设有序列{10，１2,15,19,22，25,１０0，1３０,1５０,２００｝画出对上述序列进行折半查找的鉴定树(以序列中的元素作为树的结点）（2)为了成功查找到１０0需要进行多少次元素间的比较?为了查找9，通过多少次元素间的比较可知道查找失败？5．(1)设有一个整数序列{50，38,16,８2，11０，1３，6４｝，依次取出序列中的数，构造一棵二叉排序树（２)运用上述二叉排序树，为了查找11０，经多少次元素间的比较能成功查到,为了查找15，经多少次元素间的比较可知道查找失败6.(１）设有查找表{５，１4,2,6,18，７,4，1６,3},依次取表中数据，构造一棵二叉排序树。(2)说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。四、程序填空题1．以下函数为链栈的进栈操作，x是要进栈的结点的数据域，top为栈顶指针sｔrｕctｎｏdｅ{EｌemＴypedata;strｕcｔnode*nｅｘt；}；sｔruｃtｎode*tｏｐ；ｖｏiｄＰｕsh(ＥlｅmTｙpｅx）{struｃｔnｏdｅ*p;ｐ＝(ｓtｒuｃtnode*）mａlｌoｃ（___（1)__＿__)；ｐ－>data＝x；___（２）___＿_;_____(3）___;}2.设线性表为(6,10,16，４），以下程序用说明结构变量的方法建立单向链表，并输出链表中各结点中的数据。＃ｄeｆｉｎｅＮULL0vｏidmain(){ＮOＤEａ，b,c,d,*head,*ｐ；a．datａ＝6；ｂ．data=10;c.data=16;d.daｔa=4;/*d是尾结点*/hｅad=(1);a.ｎｅｘt=&b;ｂ．ｎeｘt=＆c；ｃ.ｎext＝&d；(2）;／*以上结束建表过程*/p＝heａd；/*ｐ为工作指针,准备输出链表*/dｏ{printf(“%d＼n”,(3))；(4)；}ｗhilｅ（（５）);}3.以下函数在hｅad为头指针的具有头结点的单向链表中删除第i个结点,structnodｅ{ｉntdata;strｕｃtnoｄe*nexｔ;｝;tyｐedeｆ