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

数据结构(本）期末综合练习202３年6月为了帮助同学们进行期末复习，特拟定以下三套期末综合练习题,望同学们逐个认真完毕。数据结构(本)期末综合练习一一、单项选择题1.针对线性表，在存储后假如最常用的操作是取第i个结点及其前驱,则采用(）存储方式最节省时间。A.单链表B．双链表C.单循环链表D．顺序表２.线性表采用链式存储时，其地址()。A.一定是不连续的Ｂ．必须是连续的C.可以连续也可以不连续D．部分地址必须是连续的3.数据结构中,与所使用的计算机无关的是数据的(）结构。Ａ.物理B.存储Ｃ.逻辑与物理D．逻辑4.带头结点的单向链表的头指针为heａｄ,该链表为空的鉴定条件是（）的值为真。Ａ．ｈead==NＵLLＢ．ｈeａｄ->nｅxt＝＝headC．heａｄ-＞nexｔ==NＵLＬD.head==heａd－>next5．以下特性中，（)不是算法的特性。A．有穷性B．拟定性C．可行性Ｄ.有0个或多个输出6．设顺序存储的线性表长度为n,对于插入操作，设插入位置是等概率的,则插入一个元素平均移动元素的次数为()。A.ｎ／2B.nC．n－1Ｄ．n-ｉ＋1７．设有一个长度为n的顺序表，要在第i个元素之前（也就是插入元素作为新表的第i个元素)，则移动元素个数为（）。A．n-i+1Ｂ．n－iC.n-i-1Ｄ.i8．一个栈的进栈序列是５，６，７,８，则栈的不也许的出栈序列是（）（进出栈操作可以交替进行）A.5,8,6,7Ｂ.7，6,8，5C．7，６,５，８Ｄ．８，7，6，５9．栈的插入删除操作在（)进行。Ａ.栈底B.任意位置C.指定位置D．栈顶１0.栈和队列的相同点是（)。Ａ.都是后进先出Ｂ．都是后进后出Ｃ．逻辑结构与线性表不同D.逻辑结构与线性表相同,都是操作规则受到限制的线性表１1．以下说法对的的是（)。A．栈的特点是先进先出，队列的特点是先进后出B．栈和队列的特点都是先进后出C．栈的特点是先进后出，队列的特点是先进先出D.栈和队列的特点都是先进先出１2．在C语言中,运用数组ａ存放字符串“Heｌlｏ”，以下语句中对的的是（)。A．ｃhaｒa[1０]=“Hｅllo”;B．ｃhara[10];ａ=“Helｌo”;C.chara[10］＝‘Hello’;Ｄ．chara[1０]=｛‘H’,’e’,’l’,’l’，’o’};1３.元素2,４,６,8按顺序依次进栈，则该栈的不也许输出序列是（）(进栈出栈可以交替进行)。A．8,6，4，2B．２，4,6，8C．４，2,8，6D．8,６,２，414.设有一个1５阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。（矩阵A的第一个元素为ａ1,1,数组b的下标从1开始），则数组元素b[１3]相应Ａ的矩阵元素是(）。A.a5,３B.a6，4C．a7,2Ｄ15.设有一个1５阶的对称矩阵A,采用压缩存储的方式,将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始）,则矩阵中元素ａ７,６在一维数组B中的下标是()。A.42Ｂ.13C16．一棵完全二叉树共有30个结点,则该树一共有（)层(根结点所在层为第一层)。A.6B.4Ｃ.３D17.串函数StｒCmp（“d”,“D”）的值为（)。A．0B.1C18．以下说法对的的是(）。A．连通图Ｇ的生成树中不一定包含G的所有顶点B.连通图G的生成树中一定要包含Ｇ的所有边C.连通图G的生成树一定是唯一的D．连通图G一定存在生成树19.在一棵二叉树中，若编号为i的结点存在右孩子,则右孩子的顺序编号为()。A.2iB．2i-1Ｃ20.对二叉排序树进行（)遍历，遍历所得到的序列是有序序列。A.按层次B.前序C.中序D．后序21.设一棵有n个结点采用链式存储的二叉树，则该树共有()个指针域为空。A．２nB.2n＋1Ｃ.2n+２２2．以下排序算法中，在一趟排序过程中,除了其它相关操作外，只进行一次元素间的互换的算法是（）。Ａ．直接选择Ｂ.冒泡C.直接插入D．折半插入2３.已知如图１所示的一个图，若从顶点a出发,按广度优先搜索法进行遍历,则也许得到的一种顶点序列为（）。A.aｂcedfB.ａbｃefdC．ａebcfdＤ.acｆdebbbdfeca图124．对长度为n的线性表进行顺序查找，在等概率情况下，平均查找长度为(）。A.nＢ．（n+1)／２C.2n25.在有序表{1，3，８，13,3３，42，46,６３，7６,７８，86,９7,10０}中,用折半查找值86时，经()次比较后查找成功。A.6B．3C２6.如图若从顶点a出发按深度优先搜索法进行遍历，则也许得到的顶点序列为(）。ababecdfgB.aedcｂｇfＣ.ａｃfebdgＤ.aecｂdgf2７．有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为(）。Ａ．29/1０B．３1/10C28.一棵哈夫曼树有1２个叶子结点(终端结点),该树总共有（)个结点。A．22B．２1C.23Ｄ.29．一组记录的关键字序列为（３7,７0，４7，２9，31，8５)，运用快速排序,以第一个关键字为分割元素,通过一次划分后结果为（）。Ａ．31，２9,37,47，７0,85Ｂ．29，31，３7，47，7０,85Ｃ.31,2９，３７,7０，47，８5D.31,29，37，８5，47,703０.队列的删除操作在（）进行。A．队头B.队尾C．队头或队尾D.在任意指定位置得分评卷人二、填空题1．把数据存储到计算机中,并具体体现数据之间的逻辑结构称为＿______＿结构。2．设有一个不带头结点的单向循环链表,结点的指针域为nｅxt,指针p指向尾结点,现要使p指向第一个结点，可用语句__＿＿_＿__。３．结构中的数据元素存在一对一的关系称为_＿____＿_结构。４.要在一个带头结点的单向循环链表中删除头结点，得到一个新的不带头结点的单向循环链表，若结点的指针域为ｎeｘt，头指针为head,尾指针为p,，则可执行head=heaｄ－>ｎexｔ；________。５．在双向链表中,每个结点有两个指针域,一个指向＿＿＿__＿＿＿,另一个指向＿＿_____＿_。6．设有一个非空的链栈，栈顶指针为hｓ，要进行出栈操作,用ｘ保存出栈结点的值，栈结点的指针域为nexｔ，数据域为ｄａtａ，则可执行x=＿__＿_＿__;和hs=___＿___＿；7．设有一个头指针为head的单向链表,p指向表中某一个结点,且有p->ｎext=＝ＮULL,通过操作___＿__＿_,就可使该单向链表构导致单向循环链表。8.循环队列的最大存储空间为MaxSize，队头指针为f，队尾指针为r，当__＿＿___＿时表白队列已满。9.从一个栈顶指针为h的链栈中删除一个结点时,用x保存被删结点的值，可执行x=h->dａtａ;和________。（结点的指针域为nｅxt）１0.程序段intcount=0;char*s=”AＢCＤ”;wｈile(*s!=’＼0’执行后cｏunt=___＿____１１．两个串相等的充足必要条件是＿___＿＿_＿＿＿。12.一棵二叉树总结点数为11,叶结点数为5,该树有____＿_＿_个双分支结点,__＿_____个单分支结点。13．对二叉树的遍历可分为___＿____、、、四种不同的遍历顺序。14．设一棵完全二叉树，其最高层上最右边的叶结点的编号为偶数，该叶节点的双亲结点的编号为９,该完全二叉树一共有＿＿____＿＿个结点。1５．一棵有n个叶结点的二叉树，其每一个非叶结点的度数都为2,则该树共有___＿__＿个结点。1６．双向循环链表中，p指向表中某结点,则通过p可以访问到p所指结点的直接后继结点和直接前驱结点，这种说法是_＿_＿_＿＿＿的（回答对的或不对的)。１7.一棵有１4个结点的完全二叉树，则它的最高层上有__＿_＿__个结点。１8.栈和队列的操作特点分别是________和___＿＿＿__。１９.如图2所示的二叉树,其先序遍历序列为_＿___＿_＿_。efefgibachd图22０.折半查找只合用于存储的有序表。21．哈希函数是记录关键字值与该记录＿＿____之间所构造的相应关系。22．深度为k的二叉树最多有结点。23.二叉树排序中任一棵子树都是二叉排序树,这种说法是＿__＿___的。(回答对的或不对的)24.串的两种最基本的存储方式是_______＿和____＿_＿_。得分评卷人三、综合题1.设一组记录的关键字序列为（49,83，59,4１,４３，４7)，采用堆排序算法完毕以下操作：（规定小根堆,并画出中间过程)(１）以二叉树描述6个元素的初始堆(２)以二叉树描述逐次取走堆顶元素后，经调整得到的５个元素、4个元素的堆2．设有一个不带头结点的单向链表,头指针为hｅad，结点类型为NOＤE，每个结点包含一个数据域ｄａta和一个指针域next,该链表有两个结点,p指向第二个结点(尾结点）,按以下规定写出相应语句（不规定完整程序，(1)、(2)、（3)、（４）是一个连续的过程）。(1)新开辟一个结点,使指针s指向该结点，结点的数据成员datａ赋值为1（2)把该结点插入链表的尾部，释放指针s的指向(3）删除链表的第一个结点(4）已知p１指向另一个新结点，把它插入到p所指结点和尾结点之间3．设有序表为(１3,19,２5，36，4８，51，6３,84,91,116,１35，２00)，元素的下标依次为1，２，……，１2。（１）说出有哪几个元素需要通过4次元素间的比较才干成功查到（2）画出对上述有序表进行折半查找所相应的鉴定树(树结点用下标表达)(３)设查找元素5,需要进行多少次元素间的比较才干拟定不能查到４．(１)设有序列{１０,12,15,19,2２,２5,10０,1３0，１５0,200｝画出对上述序列进行折半查找的鉴定树（以序列中的元素作为树的结点)（2）为了成功查找到１00需要进行多少次元素间的比较？为了查找９，通过多少次元素间的比较可知道查找失败？5.（1)对给定数列｛７,１6,4,8,20，9，6，18，5},依次取数列中的数据，构造一棵二叉排序树。(2)对一个给定的查找值，简述针对二叉排序树进行查找的算法环节,在上述二叉树中查找元素20共要进行多少次元素的比较？6.（１)设有查找表｛5,14,2,6,１８，7,4,１６,3},依次取表中数据，构造一棵二叉排序树。（２）说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。四、程序填空题1．以下冒泡法程序对存放在a[1］,a[2]，……，a[ｎ]中的序列进行排序，完毕程序中的空格部分,其中ｎ是元素个数,规定按升序排列。vｏidbsｏrｔ(ＮOＤEa［],intn)｛ＮOＤEteｍｐ;inti,j,fｌag；for(j=1;（1）；ｊ++);{flａg=０;for(i=１;(2）;i++）iｆ(a[ｉ].key>a[i+1].key）{ｆｌaｇ=1;temp=a［ｉ];(3);(4);}iｆ(ｆlag==0)bｒeaｋ;}}程序中flag的功能是（５）2．以下程序是先序遍历二叉树的递归算法的程序，完毕程序中空格部分（树结构中左、右指针域分别为lｅft和ｒｉght,数据域dａtａ为字符型，BＴ指向根结点)。ｖｏiｄPreordeｒ(sｔructBＴreｅNode*BT）{iｆ（BＴ!=NＵLＬ){(１）;（2）;（3）;}}3．设线性表为（６，10，16,４)，以下程序用说明结构变量的方法建立单向链表,并输出链表中各结点中的数据。＃ｄefinｅNULL０ｖoｉdmaｉｎ()｛NODEa，b，c,ｄ，*heａd,＊ｐ;a.datａ=6;b.ｄａta＝１0；ｃ.data=16;d.ｄaｔa=4;／*ｄ是尾结点*/heａｄ=(1)；ａ.neｘt＝&b;ｂ.neｘt=&c;c．nｅxt=&d；（2）;／*以上结束建表过程*／p=head;/*p为工作指针，准备输出链表＊/do{priｎｔｆ（“%d＼ｎ”,（3）);（４)；｝ｗhilｅ(（５))；}4.以下程序是中序遍历二叉树的递归算法的程序,完毕程序中空格部分(树结构中左、右指针域分别为ｌeｆt和rｉgｈt,数据域dａta为字符型，ＢT指向根结点）。ｖoｉdInoｒdｅｒ(strucｔBTreeＮode＊ＢT)｛if(BＴ!=NＵLL)｛(1）;（2);(3）;}}答案一、单项选择题1．D2.C3.D4.C5.D6．A7.A8.A9．Ｄ10．D11．C1２．A1３．D14.Ａ１５.C16．Ｄ1７．B18.D19.D2０．C２1．Ｄ２２.Ａ23．B2４、B25.D26．A2７.Ａ2８.C29．A30．A二、填空题1.物理（存储）3．线性5．结点的直接后继结点的直接前驱7．p->nｅxt=hｅａd;９.ｈ=h->nexｔ;11．串长度相等且相应位置的字符相等１3．先序、中序、后序、层次１5．2n-117.719.ａbdgcｅfhi21．存储地址２3．对的2.p=ｐ->nｅxｔ;4．p->neｘt＝heaｄ；6．hs->data；hs->neｘt;８．（r+1）％MaxSｉｚe=ｆ10.４12.４；２１4．1８16．对的18.先进后出（后进先出)先进先出（后进后出）20．顺序存储结构2２.２k-1２4.顺序存储链式存储三、综合题4959495983414347834741435949498341434783435949414347834959414759(1)图3594759474149834347414741835943494347415983494747414383495959594741438349图42．（1)s＝（NOＤＥ＊）mallｏｃ（sｉzｅoｆ（NODE));s->dａta=1;(2）p-＞ｎext=s;s-＞neｘt=NULL;fｒee（ｓ)（３)head=head－>neｘt；(4）p１->nｅxt＝p->nexｔ；ｐ->ｎext=p1；3．（１)19,４8,８4,１１6,200（2)4471285211110639图５（３）3次2212221213019150251520010010(１）（２）4次;3次５．46468957162018图６(2)先将给定值与根结点比较，若相等则查找成功，否则若小于根结点则在左子树中继续查找，大于根结点在右子树中查找，查找20共进行3次比较。６.24246167318514图6(2)中序遍历中序2，3,4,5,６，7，14，16，18四、程序填空题１.(1)j<=n-１（2)ｉ<=n-j（3)a［i]＝a[i+１](4）a[i+1]=temp（5)当某趟冒泡中没有出现互换则已排好序,结束循环２.(1）pｒiｎtf（“%ｃ”,ＢT->ｄaｔａ）（2）Preorｄer(BＴ->lｅft)(3）Preoｒder(ＢT->rｉght)3．(1)&a(2）ｄｎeｘt=ＮULL（3）ｐ-＞daｔａ(4)p＝ｐ－>next(5)ｐ!=NULL4．(1)Ｉnｏrｄｅr(ＢT->ｌeft)(２)priｎｔf（“%c”,BT->dａta)(3）Inoｒder(BT－＞right)数据结构（本）期末综合练习二202３年6月一、单项选择题1．数据元素是数据的基本单位，它（)。A.只能有一个数据项组成B.至少有二个数据项组成Ｃ.可以是一个数据项也可以由若干个数据项组成D．至少有一个数据项为指针类型2.一种逻辑结构()存储结构。Ａ.可以有不同的B.只能有唯一的C．的数据元素在计算机中的表达称为Ｄ.的数据元素之间的关系称为3.线性表的顺序结构中，(）。Ａ．逻辑上相邻的元素在物理位置上不一定相邻B．数据元素是不能随机访问的C．逻辑上相邻的元素在物理位置上也相邻D.进行数据元素的插入、删除效率较高4．以下说法中不对的的是（)。Ａ.双向循环链表中每个结点需要包含两个指针域B.已知单向链表中任一结点的指针就能访问到链表中每个结点Ｃ．顺序存储的线性链表是可以随机访问的D.单向循环链表中尾结点的指针域中存放的是头指针５.以下表中可以随机访问的是()。Ａ．单向链表Ｂ.双向链表C．单向循环链表D．顺序表6．双向循环链表结点的数据类型为:ｓtructnode｛ｉｎtｄａta;stｒｕctnode*next；／*指向直接后继*／struｃtｎodｅ*prior;};设p指向表中某一结点,要显示p所指结点的直接前驱结点的数据元素，可用操作()。A.printf(“%ｄ”，ｐ-＞ｎext-＞dａtａ);B.ｐrintf(“%d”,p->prｉor->data);C．prｉntf(“％d”,p->priｏr->next);Ｄ.ｐrintf(“％d”,p->data);7.设顺序存储的线性表长度为n，对于删除操作，设删除位置是等概率的,则删除一个元素平均移动元素的次数为（）。A.（ｎ+1）/2B．nC.２nD．n-ｉ8．一个栈的进栈序列是eｆgｈ,则栈的不也许的出栈序列是(）(进出栈操作可以交替进行）。A.ｈgfｅB.ｇfｅhC．fｇeｈＤ.eｈfｇ9.设ｔoｐ是一个链栈的栈顶指针,栈中每个结点由一个数据域ｄａta和指针域nｅｘt组成,设用x接受栈顶元素,则出栈操作为（)。A.x=toｐ->ｄaｔa；top=top->nｅxt;Ｂ.top=ｔｏp->next;ｘ=ｔop->datａ;C.ｘ=toｐ-＞ｎext;toｐ=tｏp->data;D.toｐ->nｅxt=top;ｘ=ｔop－>datａ;１0．设top是一个链栈的栈顶指针，栈中每个结点由一个数据域data和指针域next组成,设用ｘ接受栈顶元素，则取栈顶元素的操作为（）。A.tｏｐ-＞ｄａta=x;B.top=top－>next;C.x=top->ｄata;D.ｘ=toｐ->data;ｔｏp=tｏp－>nｅxt;11.以下说法对的的是（）。Ａ.队列是后进先出Ｂ．栈的特点是后进后出C.栈的删除和插入操作都只能在栈顶进行D．队列的删除和插入操作都只能在队头进行12.以下说法不对的的是（)。A．栈的特点是后进先出Ｂ.队列的特点是先进先出C．栈的删除操作在栈底进行，插入操作在栈顶进行D.队列的插入操作在队尾进行，删除操作在队头进行13．串函数StrＣmp(“abA”,”ａｂa”)的值为（)。Ａ．１B.０C.“abＡａba”D1４.chａr*ｐ;ｐ=ＳｔｒCａt(“AＢD”,”ABＣ”）；Priｎtf（“%ｓ”,ｐ);的显示结果为(）。A.-１B.ABDABCＣ．AＢD.115.设有一个１2阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组ｂ中(矩阵A的第一个元素为a1,１，数组b的下标从1开始）,则矩阵Ａ中第4行的元素在数组b中的下标i一定有（)。A、7≤i≤10B、1１≤ｉ≤１5Ｃ、9≤ｉ≤１4D、6≤i≤16.深度为５的满二叉树至多有（)个结点(根结点为第一层）Ａ.40B.３１Ｃ．34Ｄ1７．已知一个图的边数为m,则该图的所有顶点的度数之和为（)。A.2mB.mC.2m+1D.m/21８．已知一个图的所有顶点的度数之和为m，则该图的边数为()。A．２mB．mＣ.2m＋1Ｄ．m/２19.以下说法不对的的是()。A.连通图G一定存在生成树B.连通图Ｇ的生成树中一定包含G的所有顶点C.连通图Ｇ的生成树中不一定包含G的所有边Ｄ.连通图Ｇ的生成树可以是不连通的20．以下说法不对的的是()。A.连通图Ｇ的生成树一定是唯一的B.连通图G一定存在生成树C.连通图G的生成树中一定要包含G的所有顶点Ｄ.连通图G的生成树一定是连通并且不包含回路２1．散列查找的原理是(）。A．在待查记录的关键字值与该记录的存储位置之间建立拟定的相应关系B．按待查记录的关键字有序的顺序方式存储Ｃ.按关键字值的比较进行查找D.基于二分查找的方法２2.有序表为{1，２,４,6，１0,18,2０，3２}，用课本中折半查找算法查找值18，经()次比较后成功查到。Ａ.３B.2Ｃ．4D2３.排序过程中，每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置，直到所有排好序为止，该排序算法是（)。A.直接插入排序Ｂ.快速排序C.冒泡排序Ｄ．选择排序24．在排序过程中，可以通过某一趟排序的相关操作所提供的信息，判断序列是否已经排好序，从而可以提前结束排序过程的排序算法是（)。A.冒泡Ｂ.选择C．直接插入D.折半插入2５.采用顺序查找法对长度为ｎ的线性表进行查找（不采用表尾设监视哨的方法）,最坏的情况下要进行（)次元素间的比较。A.n+2B.nC．n－1Ｄ．n/226.用折半查找法,对长度为１2的有序的线性表进行查找,最坏情况下要进行（）次元素间的比较A.４B.3C．5Ｄ2７．如图若从顶点a出发按广度优先搜索法进行遍历，则也许得到的顶点序列为()。ababecdhgfB.ａeｂｃghｄfC.aedｆｂcghD．abecｄfｇh图128.如图若从顶点ａ出发按深度优先搜索法进行遍历，则也许得到的顶点序列为(）。bcbcgdafeＢ．aedｂgfcＣ．ａcfeｂdgD.ａeｃbdgf29．一棵哈夫曼树总共有2３个结点,该树共有（)个叶结点（终端结点)Ａ.1０B．1３Ｃ.1１30.一棵哈夫曼树总共有25个结点,该树共有（）个非叶结点（非终端结点)。Ａ．12B．13C．14二、填空题（每小题2分，共24分)1.通常数据的逻辑结构涉及____、__＿_、__＿＿、____四种类型。２.结构中的元素之间存在多对多的关系称为_＿＿_____结构。３.设有一个单向链表，结点的指针域为nｅxt，头指针为ｈead,ｐ指向尾结点，为了使该单向链表改为单向循环链表,可用语句___＿_＿__。4.设有一个单向循环链表,结点的指针域为next，头指针为ｈｅａd,指针p指向表中某结点,若逻辑表达式____＿___的结果为真，则p所指结点为尾结点。５．设有一个单向循环链表,头指针为ｈead，链表中结点的指针域为next,ｐ指向尾结点的直接前驱结点，若要删除尾结点，得到一个新的单向循环链表,可执行操作________。6．设有一个链栈，栈顶指针为hs，现有一个s所指向的结点要入栈，则可执行操作s->nｅxt=hs；_＿______。7．在一个链队中，f和r分别为队头和队尾指针,队结点的指针域为next，则插入一个s所指结点的操作为____＿___；r=ｓ；8．在一个链队中，f和r分别为队头和队尾指针,队结点的指针域为nexｔ，s指向一个要入队的结点，则入队操作为_＿___＿＿＿；_＿_＿____;9.循环队列的队头指针为f,队尾指针为r,当___＿_时表白队列为空。10．循环队列的最大存储空间为MaxSizｅ=6,采用少用一个元素空间以有效地判断栈空或栈满,若队头指针front=4，当队尾指针rｅar=_＿____＿_时队满，队列中共有________个元素。11.‘A‘在存储时占________个字节。“A”在存储时占______＿＿个字节。12．程序段chａr*s＝”aBcＤ”;n=0;ｗhilｅ（*ｓ!＝’\0’｛if(＊ｓ>=’ａ’＆＆*s<=’z’)n++;s++；}执行后n=___＿_＿__13.一棵二叉树没有单分支结点，有６个叶结点，则该树总共有___＿____个结点。１4.一棵二叉树中顺序编号为5的结点（树中各结点的编号与等深度的完全二叉中相应位置上结点的编号相同）,若它存在左孩子，则左孩子的编号为______＿_。15.按照二叉树的递归定义，对二叉树遍历的常用算法有＿＿__、_＿__、__＿_三种。１6.根据搜索方法的不同,图的遍历有______＿_两种方法。１７.把数据存储到计算机中,并具体体现数据之间的逻辑结构称为_＿______结构。1８.结构中的数据元素存在多对多的关系称为_______＿结构。19．如图２所示的二叉树,其后序遍历序列为。eefgibachd图2２0．一棵有n个叶结点的二叉树，其每一个非叶结点的度数都为2,则该树共有_______个结点。21.二叉树为二叉排序的充足必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是__________的。(回答对的或不对的)２２.串的两种最基本的存储方式分别是___＿_＿_和_＿_＿____。2３．根据搜索方法的不同,图的遍历有_＿＿＿、＿___两种方法24.按某关键字对记录序列排序,若关键字的记录在排序前和排序后仍保持它们的前后关系,则排序算法是稳定的,否则是不稳定的。三、综合题１.（1）已知某二叉树的后序遍历序列是debca，中序遍历序列是dbeａc,试画出该二叉树(２)若上述二叉树的各个结点的字符分别代表不同的整数（其中没有相等的）,并恰好使该树成为一棵二叉排序树，试给出a、b、c、d、ｅ的大小关系（3）给出该树的前序遍历序列2.（1)已知某二叉树的先序遍历序列是aecdｂ，中序遍历序列是eaｄcb，试画出该二叉树（2)给出上述二叉树的后序遍历序列(3)若上述二叉树的各个结点的字符分别是１，2,3，4,5，并恰好使该树成为一棵二叉排序树,试问a、b、c、ｄ、e的值各为多少？3.（1)设有一个整数序列{40,２8,6,72,１00,3，５４}依次取出序列中的数，构造一棵二叉排序树（2）对上述二叉排序树,在等概率条件下,求成功查找的平均查找长度４.（１）给定数列｛8,17，5,9，21,１0,7,１9，6｝,依次取序列中的数构造一棵二叉排序树（2）对上述二叉树给出中序遍历得到的序列5.（1）运用筛选过程把序列{4２,8２,67，10２,1６，32,57,5２}建成堆(小根堆）,画出相应的完全二叉树（不规定中间过程)(2)写出对上述堆相应的完全二叉树进行中序遍历得到的序列6．(１)以给定权重值1,２,12,13，20,25为叶结点，建立一棵哈夫曼树（２)若哈夫曼树有n个非叶子结点，则树中共有多少结点。对给定的一组权重值建立的棵哈夫曼树是否一定唯一四、程序填空题1．以下函数在a[０]到a[n-1]中，用折半查找算法查找关键字等于k的记录，查找成功返回该记录的下标，失败时返回-１,完毕程序中的空格tｙpedefstｒuct｛intkey;……}NＯDE;iｎtBinａry＿Ｓeａrｃh（ＮOＤEａ[],intｎ,intk）{inｔlow，mid,hiｇh;loｗ=0;hｉgh=n-１;whiｌe(___(１)_____){mｉd=（lｏｗ+high）/2；if(a[mｉd]．ｋey＝=k)ｒetｕrｎ__(２）__＿＿__; elseiｆ（_＿＿(3)_____)ｌow=mid+１;ﻩeｌｓｅ__（4)______;ﻩ}＿__(５)__＿＿_;ﻩ}2．以下函数是二叉排序树的查找算法，若二叉树为空，则返回根结点的指针，否则，返回值是指向树结点的结构指针p（查找成功p指向查到的树结点,不成功p指向为NULL）完毕程序中的空格typｅｄefstｒuｃｔＢnｏdｅ{ｉntkｅy;sｔｒuｃtＢnｏdｅ*left;ｓｔrｕctBnｏｄｅ*right;｝Ｂnｏdｅ;Bnｏde*BSearcｈ（Ｂｎoｄe*bｔ,ｉnｔk）/＊bt用于接受二叉排序树的根结点的指针,k用以接受要查找的关键字*/{Bｎode*ｐ;iｆ(ｂt==___(1)_____)rｅｔurｎ(bｔ);p=bt;ｗhｉlｅ(p－>key!=＿_(２)＿＿____) {if(ｋ<ｐ->kｅｙ） ﻩ___(3)＿＿__＿；else＿＿_(4）__＿__;ﻩｉf(p==ＮULL)break；}Retuｒn(＿＿_（５)___＿_);}3.以下函数为链队列的入队操作，x为要入队的结点的数据域的值,frｏnt、rｅar分别是链队列的队头、队尾指针stｒuctｎode｛EｌemＴｙpedata;strucｔnode＊ｎext;}；structnode*fｒoｎt，*ｒear;vｏｉdInＱueue(ElｅｍTypeｘ){ｓtrｕctnode*ｐ;p=（stｒuctnoｄｅ*)_＿_（1)__＿__；p->datａ＝ｘ;ｐ-＞ｎexｔ=NＵLＬ；___(2)_____；rｅaｒ=__＿(3)__＿_＿;}4．以下函数为链队列的出队操作（链队列带有头结点），出队结点的数据域的值由x返回,front、rｅar分别是链队列的队头、队尾指针ｓｔrｕctnode{ＥleｍTypedata;structnoｄe＊ｎexｔ;};strｕｃtnode＊ｆrｏnｔ，*rear;ElemTypｅOuｔＱueue(){ﻩElｅｍＴyｐex；ﻩif(＿__（1)_____)｛priｎｔｆ("队列下溢错误！\n"）;exiｔ(1);}ｅlse{ｓtｒuctnoｄe*p=fronｔ->next;x=p->datａ;fｒoｎt->neｘｔ=___(2)＿__＿_;if（p->ｎｅxt=＝ＮＵLL)ｒear＝frｏnt;frｅe(p);＿__(3)＿_＿_＿;｝｝答案一、单项选择题1.Ｃ2.A3．C4．B5．Ｄ6.B7.Ａ8.D９．A1０.Ｃ11．C1２．C13.D14.B15．A1６.B17.Ａ18．Ｄ19.D20.Ａ21.A2２.B２3.A24．A25．B26.Ａ27．D２8．B29．D３0.A二、填空题1.集合;线性；树形；图状2．图状3.p->neｘt=heaｄ;4．p－>nｅxt==ｈead；5．ｐ->nｅxｔ=hｅad;6.hs=ｓ;7.ｒ－>neｘt=s8．ｒ->next=s；r＝s；9．r==f10.３；５１１．1;212.2１3．１１14.1０15.先序;中序;后序1６.深度优先；广度优先17.物理(存储)18.图状（网状）19．gdbeihｆca２0.2n-121．错误22．顺序存储链式存储23.深度优先广度优先24.关键字相等的记录三、综合应用题abceabced(２)d<b＜ｅ<a<c(３)abdｅｃaecbdaecbd(２)eｄbca(3）e=１,ａ=2,d=3,c＝4,ｂ=540287231004028723100546（2)ASL=（1ｘ1+2x2+3x3+4）/7=１8/785176218517621971910(２）５,6，７,8,9,10，１７,1８,１9,215.16423252571642325257678242826752573216102102初始树堆102初始树堆(2）102，52,4２,82,１6,67，32,572845284513213573209131525012321（2）2ｎ－1不一定唯一四、程序填空题（每空2分，共16分）1．(1）low<=hiｇh(2）mid（３)a[mid］．kｅy<ｋ；(4）hiｇｈ=miｄ-1(5)reｔｕrn-１;2．（１)ＮULL(2）k(3）p=p－>ｌeft（4)ｐ＝p-＞riｇhｔ(5)p3．（1)malｌoc(siｚeof（strｕcｔnodｅ))(2）rear－＞neｘt=ｐ(3）p4．(1）froｎｔ==reａr（2）p->ｎｅxt(３)ｒeｔurｎ(x)数据结构(本）期末综合练习三202３年6月一、单项选择题1．（)是性质相同的数据元素的集合，是数据的子集。A、数据元素Ｂ．数据对象C.数据结构D.数据项２．从ｎ个数中选取最大元素（)。A.基本操作是数据元素间的互换Ｂ.算法的时间复杂度是O(n２）C.算法的时间复杂度是O(ｎ)D.需要进行(n+1）次数据元素间的比较３．设链表中的结点是NＯＤE类型的结构体变量，且有ＮODE*p；为了申请一个新结点,并由p指向该结点，可用以下语句()。Ａ.p＝(NOＤE＊)maｌloｃ(ｓizeｏｆ(NODE）);Ｂ.p=(*ＮODE)malloｃ（sｉzeoｆ(NODE）);C.ｐ=(NOＤE)malloc(sｉｚeof(p）);Ｄ.p＝(NODE＊)ｍalloc（ｓiｚeｏf(p））；4.设ｈead为非空的单向循环链表头指针,p指向链表的尾结点,则满足逻辑表达式(）的值为真。A．ｐ-＞next=NUＬLＢ．ｐ==NUＬLC．p－>next=hｅadＤ．p->nｅxｔ＝=head5．设顺序存储的线性长度为n,要在第ｉ个元素之前插入一个新元素,按课本的算法当i=(）时,移动元素次数为２A．ｎ／2B．nC．1D.n-16．设顺序存储的线性表长度为n,要删除第i个元素,按课本的算法,当i=（)时，移动元素的次数为3A.3Ｂ.n／２C．n-3D7.一个栈的进栈序列是1，２,3，４,则栈的不也许的出栈序列是（）（进出栈操作可以交替进行)A.３，２,4,1B．１,4，2，3C．4，3，2,1D．3,2，1,４8．一个栈的进栈序列是a,b,c，d，则栈的不也许的出栈序列是（）。A.ａｄbｃＢ．bcadC.cbadD．dcｂa9.设有一个带头结点的链队列,队列中每个结点由一个数据域ｄaｔa和指针域nexｔ组成,froｎt和rear分别为链队列的头指针和尾指针。设p指向要入队的新结点(该结点已被赋值),则入队操作为()。A．rｅａr->neｘt=p;reａｒ＝p;Ｂ.rｅａｒ-＞nexｔ=p;p=reaｒ;C.ｐ=ｒear->ｎext;reaｒ＝ｐ;D.ｒｅar=p;ｒｅａr->ｎext=p;1０．设有一个带头结点的链队列，队列中每个结点由一个数据域data和指针域next组成，ｆｒont和rear分别为链队列的头指针和尾指针，要执行出队操作,用x保存出队元素的值，p为指向结点类型的指针,可执行如下操作:p=fｒont->neｘt;x=p->ｄａta;然后指行（)。A.ｆｒｏnt=ｐ->ｎext;B．fｒonｔ->nｅxt＝p－>ｎexｔ;C．front=p;Ｄ.froｎt->next=p;1１.以下说法不对的的是(）。A.顺序栈中，栈满时再进行进栈操作称为“上溢”B．顺序栈中，栈空时再作出栈栈操作称为“下溢”C.顺序队列中,当尾指针已经超越队列存储空间的上界，则一定是队列已满D.顺序队列中，队列的头指针和尾指针均超越队列存储空间的上界，则队列已空１3．设有一个２0阶的对称矩阵Ａ,采用压缩存储方式，将其下三角部分以行序为主序存储到一维数组中（矩阵Ａ的第一个元素为a11,数组b的下标从1开始），则矩阵元素a８,5在一维数组ｂ中的下标是()。Ａ．30Ｂ．28C.40Ｄ1４.设有一个10阶的对称矩阵Ａ,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。（矩阵A的第一个元素为ａ1,1，数组b的下标从1开始),则矩阵元素ａ5,３相应一维数组ｂ的数组元素是(）。A.b[18]B.ｂ[8]C.b[13]Ｄ．b[1０]1５.深度为5的完全二叉树第5层上有4个结点，该树一共有(）个结点。A．２8Ｂ．30C．3１D１6.深度为５的完全二叉树共有20个结点,则第５层上有（）个结点(根所在结点为第一层）。Ａ．3B．8Ｃ.5D１７．已知一个图的所有顶点的度数之和为m，则m一定不也许是()。Ａ.４B．８C.12Ｄ18．已知一个图的所有顶点的度数之和为m,且m是以下4中情况之一，则m只也许是（）。A.9B．7Ｃ．15D19．以下说法对的的是()。A．连通图Ｇ的生成树中可以包含回路B.连通图Ｇ的生成树可以是不连通的C．连通图G的生成树一定是唯一的D.连通图G的生成树一定是连通而不包含回路的20.线性表只要以（)方式存储就能进行折半查找。A.链接B．顺序C.关键字有序的顺序D.二叉树21．对n个元素进行冒泡排序,通常要进行n－1趟冒泡,在第ｊ趟冒泡中共要进行（)次元素间的比较。A．jＢ．j-1C.n-jD22．对n个元素进行冒泡排序若某趟冒泡中只进行了（）次元素间的互换,则表白序列已经排好序。A．１Ｂ.２Ｃ．0D23．在排序过程中，可以有效地减少一趟排序过程中元素间的比较次数的算法是()。A．冒泡B．选择C.直接插入D．折半插入24.在对一组元素(6４,４8,１06,33,25，8２，70，５５，9３）进行直接插入排序时，当进行到要把第7个元素7０插入到已经排好序的子表时,为找到插入位置，需进行(）次元素间的比较(指由小到大排序）。A.6B．２C．3D25.如图若从顶点ａ出发按深度优先搜索法进行遍历，则也许得到的顶点序列为（）。abecabecdfB.abｅdcfＣ．ａcebdｆD.aｃｆｂｄｅ图１26．如图，若从顶点a出发按广度优先搜索法进行遍历，则也许得到的顶点序列为(）。abecdfgabecdfgB．abｅcdgｆC．ａcfedｇbD．abecfdｇ２7．一棵哈夫曼树有n个叶子结点(终端结点）,该树总共有（)个结点。A.2ｎ－2B．2n－1C．2nD．２28．一棵哈夫曼树有10个非叶子结点（非终端结点),该树总共有（)个结点。A．21B．20C．２2９.数据的()结构与所使用的计算机无关。A.逻辑B.物理C.存储Ｄ.逻辑与存储３0．队列的插入操作在（)进行。Ａ．队头B．队尾C.队头或队尾D.在任意指定位置二、填空题1.通常可以把一本具有不同章节的书的目录结构抽象成_____＿__结构。2．通常可以把某城市中各公交站点间的线路图抽象成___＿____结构。３.要在一个单向链表中p所指向的结点之后插入一个s所指向的新结点，若链表中结点的指针域为next,可执行_＿_____＿和p->nexｔ＝s;的操作。4.要在一个单向链表中删除p所指向的结点,已知q指向p所指结点的直接前驱结点，若链表中结点的指针域为neｘｔ，则可执行＿＿______。5．设有一个非空的链栈，栈顶指针为ｈs,要进行出栈操作,用x保存出栈结点的值，栈结点的指针域为next,则可执行x=hs－>datａ；________。6.设有一个链栈，栈顶指针为hｓ,现有一个s所指向的结点要入栈，则可执行操作________和hs＝ｓ;7.在一个不带头结点的非空链队中，f和r分别为队头和队尾指针,队结点的数据域为dａta，指针域为nexｔ，若要进行出队操作,并用变量x存放出队元素的数据值,则相关操作为ｘ＝f->ｄatａ；__＿__＿__。8．在一个不带头结点的非空链队中，ｆ和r分别为队头和队尾指针，队结点的数据域为ｄaｔa,指针域为nexｔ,若要进行出队操作，并用变量x存放出队元素的数据值，则相关操作为___＿_＿__;__＿__＿__。９.循环队列的最大存储空间为MaxSize=8,采用少用一个元素空间以有效的判断栈空或栈满，若队头指针froｎｔ=4，则当队尾指针reａr=__＿_____时,队列为空，当ｒｅaｒ=____＿___时,队列有6个元素。10，顺序存储字符串“AＢCD”需要占用_______＿个字节。11．稀疏矩阵存储时，采用一个由____、__＿_、＿＿__3部分信息组成的三元组唯一拟定矩阵中的一个非零元素。12.一棵二叉树叶结点(终端结点）数为5，单分支结点数为２，该树共有___＿＿_个结点。13．一棵二叉树顺序编号为6的结点(树中各结点的编号与等深度的完全二叉中相应位置上结点的编号相同),若它存在右孩子，则右孩子的编号为_＿_＿___＿。１4．设一棵完全二叉树,其最高层上最右边的叶结点的编号为奇数，该叶节点的双亲结点的编号为10,该完全二叉树一共有＿_____＿_个结点。15．结构中的数据元素存在多对多的关系称为_____＿__结构。1６.结构中的数据元素存在一对多的关系称为_____＿＿_结构。１7.结构中的数据元素存在一对多的关系称为＿＿_＿_＿_＿结构。18．结构中的数据元素存在一对一的关系称为_＿______结构。19.如图2所示的二叉树,其前序遍历序列为__＿＿__＿__。ggfabdec图22０.如图2所示的二叉树,其后序遍历序列为。eefgibachd图22１.在队列的顺序存储结构中，当插入一个新的队列元素时,指针的值增１,当删除一个元素队列时，指针的值增1。２2．图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是______的。(回答对的或不对的)23．循环队列的引入,目的是为了克服。24．按某关键字对记录序列排序,若关键字的记录在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的，否则是不稳定的。三、综合题1.(１）设head1和p1分别是不带头结点的单向链表Ａ的头指针和尾指针，heaｄ２和p２分别是不带头结点的单向链表B的头指针和尾指针，若要把B链表接到A链表之后，得到一个以head1为头指针的单向循环链表，写出其中两个关键的赋值语句(不用完整程序,结点的链域为neｘｔ)。（2)单向链表的链域为neｘｔ，设指针p指向单向链表中的某个结点,指针s指向一个要插入链表的新结点,现要把s所指结点插入ｐ所指结点之后,某学生采用以下语句:p->next＝s；s->next=p－>nｅxt;这样做对的吗？若对的则回答对的，若不对的则说明应如何改写2．（１)一组记录的关键字序列为｛４５，40,65,４3，35，９5}写出运用快速排序的方法，以第一个记录为基准得到的一趟划分的结果(规定给出一趟划分中每次扫描和互换的结果）（２)同样对序列{45,４０，65，43，35，９5}运用直接插入排序，写出逐次插入过程（从第一个元素一直到第六个元素）。3．（1)画出对长度为１0的有序表进行折半查找的鉴定树（以序号1，2，……１０表达树结点）(2)对上述序列进行折半查找，求等概率条件下,成功查找的平均查找长度4．（1)运用筛选过程把序列｛42，82,6７,102,16，32,5７，５2}建成堆(小根堆)，画出相应的完全二叉树（不规定中间过程)（2)写出对上述堆相应的完全二叉树进行中序遍历得到的序列5.（1）运用筛选法，把序列{３７,7７，６2,9７，11,２7,5２，4７}建成堆(小根堆），画出相应的完全二叉树(2)写出对上述堆所相应的二叉树进行前序遍历得到的序列6.(1）设有一个整数序列{50,３8，1６,８２,１１0，13,6４},依次取出序列中的数,构造一棵二叉排序树(2）运用上述二叉排序树，为了查找110，经多少次元素间的比较能成功查到，为了查找15,经多少次元素间的比较可知道查找失败四、程序填空题1．以下函数为直接选择排