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

数据结构期末综合练习２023年12月期末练习一一、单项选择题１．一种逻辑结构在存储时（)。A.只要存储数据元素间的关系B.只能采用一种存储结构C.可采用不同的存储结构D.只要存储数据元素的值2．同一种逻辑结构（)。A．只能有唯一的存储结构B.可以有不同的存储结构Ｃ．只能表达某一种数据元素之间的关系D.以上三种说法均不对的3．对链表，以下叙述中对的的是(）。A.不能随机访问任一结点B.结点占用的存储空间是连续的C．插入删除元素的操作一定要要移动结点D．可以通过下标对链表进行直接访问４．链表所具有的特点是（)。A.可以随机访问任一结点B.占用连续的存储空间C.插入删除元素的操作不需要移动元素结点D.可以通过下标对链表进行直接访问5.线性表在存储后,假如相关操作是:规定已知第i个结点的位置访问该结点的前驱结点,则采用（）存储方式是不可行的。A．单链表B.双链表C．单循环链表D.顺序表6．数据的物理结构（)。A.与数据的逻辑结构无关B．仅仅涉及数据元素的表达Ｃ．只涉及数据元素间关系的表达D.涉及数据元素的表达和关系的表达7．栈和队列的共同特点是()。A.都是先进后出B．元素都可以随机进出Ｃ.只允许在端点处插入和删除元素Ｄ．都是先进先出8.线性结构中数据元素的位置之间存在()的关系。Ａ.一对一B．一对多9.元素2，4,6，8按顺序依次进栈，按该栈的的也许输出序列依次入队列，该队列的也许输出序列是(）(进栈出栈可以交替进行)。A.8，6，2，4B．8，４，2,6Ｃ.6，2,4,８D．８,6，４,210．以下表中可以随机访问的是（)。Ａ．单向链表B.双向链表C.单向循环链表Ｄ．顺序表１1．在一个不带头结点的链队中,假设ｆ和r分别为队头和队尾指针，则从该对列中删除一个结点并把结点的值保存在变量x中的运算为（)。A．x=rdata；r=rnｅxｔ；B.r=rneｘt;ｘ＝rｄataC.x＝fｄata;ｆ=fnｅxt;D.f=ｆｎeｘt;x=fｄatａ1２．算法的时间复杂度与(）有关。A．所使用的计算机B.与计算机的操作系统C.与算法自身D.与数据结构1３．设有一个20阶的对称矩阵A,采用压缩存储的方式,将其下三角部分以行序为主序存储到一维数组Ｂ中(数组下标从1开始)，则数组中第3８号元素相应于矩阵中的元素是（)。A．a10，８Ｂ．a7,6C．a９,2Ｄ．a１4．设有一个长度为n的顺序表，要删除第i个元素需移动元素的个数为()。A.n-i+１B.ｎ-ｉC.ｎ-ｉ－１Ｄ．i1５.在C语言中，分别存储“S”和‘s’，各需要占用（)字节。A.一个和两个B.两个C.一个D.两个和一个１6.在一个单链表中，p、q分别指向表中两个相邻的结点,且ｑ所指结点是p所指结点的直接后继,现要删除q所指结点，可用的语句是(）。A.ｐ=ｑ-＞nextＢ．ｐ－＞neｘt=ｑＣ．p－>next＝ｑneｘｔD．ｑ-＞nｅｘt=NUＬL１7．一棵有n个结点,采用链式存储的二叉树中,共有(）个指针域被有效使用(即指针域为非空）。A.ｎ＋１B．nC．ｎ-1Ｄ．n-２18.从一个栈顶指针为top的链栈中删除一个结点时,用变量x保存被删结点的值，则执行()。A.x＝ｔｏｐ->data;top=ｔｏp－>neｘt；B．x=top－>ｄaｔa；C．tｏｐ=ｔｏp-＞nexｔ；x=top->data;D．tｏp＝ｔop->next;x=data;19．在一棵二叉树中，若编号为i的结点存在双亲结点,则双亲结点的顺序编号为(）。Ａ.i/２．0B．i/2向下取整C．２ｉ+1D．i+220.在一个链队中，假设ｆ和r分别为队头和队尾指针,则删除一个结点的运算为（)。Ａ．ｒ=ｆ－>neｘｔ；B．r=ｒ->nｅxt;Ｃ．ｆ=ｆ－>neｘｔ；D．f=ｒ->neｘｔ;2１.设一棵哈夫曼树共有2n＋１个结点，则该树有(）个非叶结点。A.nB.ｎ＋1Ｃ.n-122．一个栈的进栈序列是ａ,b,c,ｄ，e，则栈的不也许输出序列是()（进栈出栈可以交替进行)。A.ｄceabB.eｄcbaＣ．ｄeｃbａD．aｂcde23.一棵完全二叉树共有4层，且第4层上有2个结点，该树共有(）个非叶子结点（根为第一层)。Ａ．5Ｂ．4C．324．有一个长度为１０的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。A．2６/1０B．2９/１025．如图１所示的一个图,若从顶点a出发,按广度优先搜索法进行遍历,则也许得到的一种顶点序列为（）。Ａ.abｅｄfcB.acfebdC.aeｂcdfD.ａebcfdbbdfeca图126.排序算法中，从未排序序列中依次取出元素与已排序序列(初始为空）中的元素进行比较（规定比较次数尽量少)，然后将其放入已排序序列的对的位置的方法是()。Ａ．冒泡B.直接插入C.折半插入D．选择排序２7．一组记录的关键字序列为(56,3０,８９,66,48,５0,9４,８7，1０0),运用快速排序,以第一个关键字为分割元素，通过一次划分后结果为(）。Ａ．30,５0，48，56，6６，89，94,１０0,８7B．5０，３0,４8，56，6６,89,94,87,100C．48,30,5０，56,６6,89,94，8７,１00D．50，30,48，６6,5６,89,94,８7,1０028.设有一个１0阶的对称矩阵Ａ，采用压缩存储的方式，将其下三角部分以行序为主存储到一维数组B中(数组下标从１开始)，则矩阵中元素A8,5在一维数组B中的下标是(）。A.33B.32Ｃ.８529．线性表以（)方式存储，能进行折半查找。A．关键字有序的链接B．顺序C.关键字有序的顺序D.数组C.多对多Ｄ.每一个元素都有一个直接前驱和一个直接后继30．在一个无向图中，所有顶点的度数之和等于边数的(）倍。A.３B.2．5Ｃ二、填空题1.数据的逻辑结构在计算机中的表达称为_______＿结构。2．栈和队列的操作特点分别是__＿____和_____＿__。3．求两个n阶矩阵的乘积，算法的基本操作为＿＿_＿＿___,时间复杂度为___＿___＿。4．结构中的数据元素存在多对多的关系称为_＿______结构。5.设有一个长度为2５的顺序表,第8号元素到第２5号元素依次存放的值为8,9,１0,11，…2５，某人想要在第8个元素前插入1个元素7(也就是插入元素作为新表的第8个元素),他的做法是从第８号元素开始,直到第2５号元素依次向后移动1个位置,然后把7存放在8号位置,其结果是新表中第25号元素的值为___＿＿。6.根据数据元素间关系的不同特性，通常可分为集合、线性、、四类基本结构。7.在双向链表中，要在p所指的结后插入q所指的结点（设q所指的结点已赋值)，其中所用的一条语句(p->ｎｅｘt)-＞priｏｒ=q；的功能是使P所指结点的__＿_＿_＿指向q。８．规定在n个数据元素中找其中值最大的元素,设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为____＿_＿_和____＿___。9.设有一个带头结点的,头指针为ｈead的单向链表,ｐ指向表中某一个结点,且有ｐ->ｎext==ＮULL,现要删除头结点,并使该单向链表构导致单向循环链表,通过操作heａd=head->nexｔ;__＿__＿__。1０.在一个单向链表中ｐ所指结点之后插入一个ｓ所指向的结点时，应执行__＿＿_＿__和p-＞next=ｓ；的操作。11.从一个栈顶指针为tｏp的链栈中删除一个结点时，用d保存被删结点的值，可执行__＿＿____。（结点的指针域为nｅxｔ，数据域为dａtａ）12．在二叉树的链式存储结构中，通常每个结点中设立三个域，它们是值域、。13循环链队列中,设ｆrｏｎt和ｒear分别为队头和队尾指针，(最多元素为MaｘSize,采用少用一个元素的模式),判断循环链队列为满的条件为＿______＿。14．一棵二叉树中顺序编号为ｉ的结点,若它存在左、右孩子，则左、右孩子编号分别为___＿____、＿_______。15．对稀疏矩阵进行压缩存储，可采用三元组表，一个6行7列的稀疏矩阵A相应的三元组表共有8个元素,则矩阵Ａ共有___＿＿__个零元素。1６．向一个栈顶指针为h的链栈中插入一个s所指结点时,可执行s->ｎext=h;和__＿＿__＿_。1７．一棵有２0个结点的４度的树，其中3度结１个，２度结1个,1度结2个，则该树共有__＿___＿个叶结点。18．在一个链队中，设f和r分别为队头和队尾指针,则插入s所指结点的操作为____＿___和r=ｓ;(结点的指针域为nｅｘｔ)19.一棵有18个结点的二叉树，其２度结点数的个数为８，则该树共有＿_＿＿＿_＿个1度结点20.设有一棵深度为4的完全二叉树，第四层上有５个结点,该树共有____＿_＿__个结点。(根所在结点为第１层）21.如图２所示的二叉树,其先序遍历序列为__＿_＿_＿_＿。3c7g3c7gd65e4dc2b18hd9图222.对稀疏矩阵进行压缩存储,矩阵中每个非零元素相应的三元组涉及该元素的__＿___＿、__＿__＿_和_______三项信息。23．在查找表中,通过记录的某关键字能唯一地拟定一个记录，该关键字称为_＿______＿。24.在对一组记录（55，39,9７,22,16，７3,65,47,８８)进行直接插入排序时,当把第7个记录65插入到有序表时，为寻找插入位置需比较________＿次。三、综合题1.(1)对给定权值3,1,４，4,5,6，构造深度为５的哈夫曼树。(设根为第1层)(2)求树的带权途径长度。（3）链接存储上述哈夫曼树，结点中共有多少个个指针域为空,说明理由.2．（1）以2，3，4，７,8,9作为叶结点的权,构造一棵哈夫曼树(规定每个结点的左子树根结点的权小于等于右子树根结点的权)，给出相应权重值叶结点的哈夫曼编码。（2)一棵哈夫曼树有n个叶结点，它一共有多少个结点?简述理由？3．(1)如下的一棵树,给出先序遍历序列（2)把１,2,３，４，5,6，7,8,9填人,使它成为一棵二叉排序树提醒：设图中的树是二叉排序树,找出中序遍历序列与1,2,…9的相应关系(3)请在该树中再插入一个结点3．5作为叶结点,并使它仍然是一棵二叉排序树。AA1A2A43A7A5A9A8A3A6图34.一组记录的关键字序列为（46，７9，５6，３8，40，84)(1)运用快速排序的方法,给出以第一个记录为基准得到的一次划分结果（给出逐次互换元素的过程，规定以升序排列)（２)对上述序列用堆排序的方法建立大根堆，规定以二叉树逐次描述建堆过程。5．设查找表为(5,6,7,8,9,10，１1,12,13,14)（1）画出对上述有序表进行折半查找所相应的鉴定树(规定以数据元素作为树结点)(2)给出二叉排序树的定义,针对上述折半查找所相应的鉴定树的构造过程,说明鉴定树是否是二叉排序树(设树中没有相同结点)?（3)为了查找元素5．5,通过多少次元素间的比较才干拟定不能查到？６.设查找表为(５0,６０,７5，８5,96，98,１0５,１10，12０,130）(1)说出进行折半查找成功查找到元素12０需要进行多少次元素间的比较？(2)为了折半查找元素95，通过多少次元素间的比较才干拟定不能查到?（3）画出对上述有序表进行折半查找所相应的鉴定树(规定以数据元素作为树结点)四、程序填空题1．以下函数为直接选择排序算法,对a[１],a[2]，…a[n]中的记录进行直接选择排序,完毕程序中的空格ｔｙpeｄefstruct{iｎtｋｅy;……}ＮODＥ;ｖoｉdsｅlsorｔ(NＯＤEａ[],ｉｎｔn){ﻩｉnti,ｊ，k; NODEtemp; for(i=１;ｉ<=___(1)_____；ｉ++) {ﻩﻩｋ=i;ﻩ for(j＝ｉ+１；j＜=＿__(2)＿_＿__;j++) ﻩ ｉf(a[j］.key<a［k].key)__(３)____＿_；ﻩ if(i！=k) {ﻩﻩ tｅmp=a[ｉ];ﻩ ﻩ___（4)__＿__; ﻩﻩ__＿_(5)____;ﻩﻩ}ﻩ}}2．以下是用尾插法建立带头结点且有ｎ个结点的单向链表的程序，结点中的数据域从前向后依次为1，２,3,……,n，完毕程序中空格部分。NＯＤE*create(n）｛ＮＯDE*ｈeａd,＊p,*ｑ;iｎti;p=(NODE＊）mａlｌoｃ(sizeoｆ（ＮODＥ))；ｈeａd=(１);（2);pｎext=ＮUＬL;／＊建立头结点＊/fｏr(i=1;i<＝n;ｉ＋+){p=(3）;pdａｔa=i；pｎext=NＵLL；qnｅxt=（４）;(５）;}retｕｒn（heaｄ);}３.设有一个头指针为hｅad的不带头结点单向链表，且p、q是指向链表中结点类型的指针变量，p指向链表中某结点a(设链表中没有结点的数据域与结点a的数据域相同),写出相关语句(1）．使该单向链表成为单向循环链表（2)删去a结点q=p;x=p->data;whiｌｅ（q－>ｎｅxt!=NＵLL）q=q－>next；__（1)_＿_q=p;p=p->next；whiｌe(p->ｄata!=ｘ）｛q＝p;__(２)___}＿_(３)＿＿_4．以下程序是中序遍历二叉树的递归算法的程序,完毕程序中空格部分(树结构中左、右指针域分别为lｅft和rigｈt,数据域data为字符型,BＴ指向根结点）。vｏｉdＩnorder(ｓｔructBTreeNodｅ*BT){iｆ(BＴ!=NULＬ){(１);（2）;(３);}｝期末复习一答案一、单项选择题1.C2．Ｂ3.A4.Ｃ５.A6.D７.C8．A９.D1０．D11．C12.C１３.C1４．B１5.Ｄ16．C17.C１8．A19.B2０．Ｃ2１．Ａ22．A２3．Ｂ24.B25．C26.C27．B28.A29.C3０．Ｄ二、填空题1.物理（存储)2.后进先出、先进先出3.乘法O(n3）4.图状（网状)5．8６．树形图状7．直接前驱的左指针8.n-1,O(ｎ)、9．p-＞nｅxｔ=head;10．ｓ-＞next＝ｐ-＞nｅxt；11．ｄ＝toｐ->datａ；ｔop=top－>next;12．左指针右指针13.front＝=(reaｒ＋1）%MaxSｉze14.2i2i+115.3416．ｈ＝s;1７．１318.r－＞ｎｅxt=s；19.120.１221.22．行下标、列下标、非零元素值23．主关键字24.3三、综合应用题654365435423418145197896434531213图４(2)WＰL=3*4+1*4＋4*3+６*2＋4*2＋５*2＝58（3)共11个结点,2２个指针域,除根结点外,每个结点相应一个指针域.,共10个指针域非空，故有22-10＝1２个空指针域，2．3333(1)151815187998799854543232图52:11１０３:111１4：１107：008:019:10（2)2n-1个，由于非叶结点数比叶结点数少一个。3.(1)Ａ１Ａ2A（2)(３)77421563893.5图64．(１)初始序列4６，79,56,38,40，8440,79,5６,3８,4０，8440，79，5６,３８,７9，8440，38,5６，３8,79，8440，３８，56,56,79，84４0,38,46，56,7９，8456795679384084468479384046566567938404679384084845646图6５．（1）9971014118512136图7（2)二叉排序树或者是一棵空树，或者是一棵具有下列性质的二叉排：若它的左子树非空，则左子树的所有结点的值都小于它的根结点的值;若它的右子树非空，则右子树的所有结点的值都大于(若允许结点有相同的值，则大于等于)它的根结点的值;左,右子树也是一棵二叉排序树，按定义鉴定树是二叉排序树。(３）3次６.(1)3次(2)4次（３)9696759813010585501100512060图8四、程序填空题1．(1)ｎ-1(2）n（3)ｋ=j(4）ａ[ｉ]=a[k](５）a［k]＝temp2．（1)p(2）ｑ＝p(3）(NODＥ*)mａlｌoc(sizｅoｆ（NOＤE))(4）p(5）q=p3.q->next=ｈｅａd;p=p－＞next；q->neｘt=p->ｎeｘt;4．（1）Inorder(BＴ-＞lefｔ)(2）printf(“%c”,BT-＞data)（3）Inｏrder(BT-＞ｒighｔ)期末练习二一、单项选择题1.结构中的元素之间存在一对多的关系是（)。Ａ.集合B．线性结构C．树形结构D.图状结构2．在C语言中,顺序存储长度为3的字符串，需要占用()个字节。A.４B．3C．6Ｄ．123.对不带头结点的单向链表,判断是否为空的条件是(）(设头指针为ｈead）。A．heaｄ＝=NＵLLB.hｅad->next＝=NUＬLC．head->neｘt==heａdＤ．head=ＮUＬL４.串函数StｒＣａt（ａ,ｂ)的功能是进行串(）。A．比较Ｂ.复制C.赋值Ｄ．连接5.在一个不带头结点的单循环链表中,p、ｑ分别指向表中第一个结点和尾结点,现要删除第一个结点,可用的语句是（）。Ａ.ｐ=q->next；p=p->ｎext;Ｂ．p－＞neｘt=q;p=ｐ->neｘt；C．ｐ-＞nexｔ=ｑ->nｅxt;q＝p;D.p=ｐ－>ｎexｔ；q->next=p;6．一棵有n个结点采用链式存储的二叉树中,共有(）个指针域为空。A．ｎ+1Ｂ．nC．n-1Ｄ．ｎ-2７.一个栈的进栈序列是1，2,3,4，５,则栈的不也许输出序列是(）(进栈出栈可以交替进行）。A.12345B.４3５12C.４53２1Ｄ.5４3218.设一棵哈夫曼树共有n个非叶结点,则该树有(）个叶结点。A．nＢ．ｎ+1C.n-1D.２n９.一个队列的入队序列是2，4,6，8，按该队列的输出序列使各元素依次入栈,该栈的也许输出序列是()。A．8，６,4,２B．6，2，4,8C．８,4，２,6D．8，2，4，６10.从一个栈顶指针为top的链栈中删除一个结点时,用变量x保存被删结点的值，则执行()。A.ｘ＝top->ｄata;ｔop=toｐnext；B.x=toｐ－＞ｄaｔa;C．top=top－>next;x=tｏp->datａ;Ｄ.toｐ=ｔop->nexｔ;x=data；1１．在一个链队中，假设f和r分别为队头和队尾指针，已生成一个结点ｐ,要为结点ｐ赋值x,并入队的运算为（）。Ａ．p->data=x;p－＞nexｔ=NULL;f－>next=p;f=p;B.p-＞data=x;p－>next=NULL；r－>neｘt=p;r＝ｐ;Ｃ.p-＞ｄatａ=x；p->next=r;r=ｓ;D.p->dａtａ=x;p->neｘｔ=f；f=ｓ;1２.一棵完全二叉树共有5层,且第5层上有六个结点，该树共有（)个结点。Ａ．３0B.２０C.21D．２313.设有一个25阶的对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始),则矩阵中元素．ａ７，６在一维数组Ｂ中的下标是（）。A．34B.１4Ｃ．26Ｄ.2７14．在一个无向图中，所有顶点的度数之和等于边数的(）倍。A.３B.2.５C．1．5D．21５.以下程序段的结果是c的值为(）。ｃhaｒa[5］=“１236789”ｗhile(*p++)ｃ++;A.8,B．7C.10D．12１6.已知如图1所示的一个图,若从顶点V1出发,按深度优先搜索法进行遍历，则也许得到的一种顶点序列为（)。A.V1V2V４Ｖ８Ｖ５V3V6V７B.Ｖ1V2Ｖ4V5Ｖ8V3V６V7Ｃ．V１V２V4V８V3V５V6Ｖ7D．V１V３V６Ｖ7Ｖ2V４V５Ｖ8VV6V7V1V2V3V8V4V5图117．一棵有23个结点,采用链式存储的二叉树中,共有（）个指针域为空。A.24B．２５C.23D．4518.已知如图2所示的一个图,若从顶点a出发,按广度优先搜索法进行遍历,则也许得到的一种顶点序列为()。A.abcedfＢ．ａbｃｅfdC．aebcｆdD.aｃfdeｂbdbdfeca图219．在一棵二叉树中，若编号为i的结点是其双亲结点的左孩子,则双亲结点的顺序编号为()。A．i／2Ｂ．2i-１Ｃ．2i+1D.i/２-120．对二叉排序树进行（)遍历,可以使遍历所得到的序列是有序序列。A.按层次B.后序C.中序D．前序21.设一棵哈夫曼树共有2ｎ+1个叶结点,则该树有()个叶结点。A.n-１B.nC.ｎ+1D．２n22.在有序表{2，4,7，1４，3４,43，47，64,75,80,90，９7,１20}中，用折半查找法查找值８0时，经（)次比较后查找成功。A.4B．２C.3Ｄ．５23．已知如图3所示的一个图,若从顶点ａ出发，按深度优先搜索法进行遍历,则也许得到的一种顶点序列为（）。A.abeｃｄfB．acfebｄC.ａebcｆｄＤ．aedbｆcbbdfeca图32４.有一个长度为９的有序表,按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（)。Ａ．25/1０B．２5/９Ｃ．2０／9Ｄ．17/92５.已知如图4所示的一个图,若从顶点B出发，按广度优先法进行遍历,则也许得到的一种顶点序列为（）。A.BADEHＣＦGＢ.ＡDEHCＧFC.BADＥCHFGD.ＢAＤEHＣＦGFFGV7ABCHV8DV4E图4２6.排序算法中，从未排序序列中依次取出元素与已排序序列(初始为空)中的元素进行比较(规定比较次数尽量少),然后将其放入已排序序列的对的位置的方法是（）。A．冒泡B.直接插入C.折半插入D.选择排序２7．一组记录的关键字序列为（４6，38,56,４０,７9,84）,运用快速排序,以第一个关键字为分割元素，通过一次划分后结果为()。A.40,3８，46,79,5６，8４B．40,38，46,5６，7９，８４C．4０，３8,46，８4,5６，79Ｄ.38，４0,46，56，７9，84２8．一组记录的关键字序列为（46，79,５6,38,４０，８4），运用快速排序，以第一个关键字为分割元素,通过一次划分后结果为（）。A．40,38，46，7９，5６,84B．40,3８,４6，５6，79,８４Ｃ.４0,38，4６,8４，5６,７9D．38，４0，46，56,79，8４２9．在有序表{21，23，2８,３3，43,45,46,７3,77,78，８9,99，106}中，用折半查找值43时，经（)次比较后查找成功。A．6B.3Ｃ．8Ｄ．430．排序方法中,从尚未排序序列中挑选元素,并将其依次放入已排序序列(初始为空)的一端的方法，称为()排序。A.归并B.插入C．快速D．选择二、填空题1.本书中介绍的树形结构和_＿＿＿__＿属非线性结构。２.在二叉树的链式存储结构中，通常每个结点中设立三个域,它们是_____＿_、、右指针。3．设有一个长度为18的顺序表，要在第4个元素之前插入２个元素（也就是插入元素作为新表的第5个和第4个元素),则最少要移动元素的个数为（)。4．一棵二叉树中顺序编号为i的结点,若它存在左、右孩子,则左、右孩子编号分别为＿___＿＿、＿_＿__＿＿_。５.在双向链表中，要删除p所指的结点,可以先用语句(p->priｏr)－>ｎext=p－>ｎext;然再用语句_______＿。６.串的两种最基本的存储方式是_____＿＿_和___＿___＿。７．在一个单向链表中p所指结点之后插入一个s所指向的结点时,应执行s-＞next=ｐ-＞next;和_____＿＿的操作.8.一棵有２ｎ-1个结点的二叉树,其每一个非叶结点的度数都为２,则该树共有__＿____个叶结点。9.一个栈和一个队列的输入序列都为aｂcdefｇ,它们也许有相同的输出序列吗？________＿。(若没有则回答没有,若有则写出序列,进栈出栈可以交替进行)。1０.对于一棵具有n个结点的二叉树，其相应的链式存储结构中共有________个指针域为空。11.从一个栈顶指针为tｏp的链栈中取栈顶元素,用d保存栈顶元素的值，可执行＿＿_____＿。(结点的数据域为datａ)12.＿＿_＿__＿_遍历二叉排序树可得到一个有序序列。1３.循环链队列中,设fronｔ和ｒｅaｒ分别为队头和队尾指针,（最多元素为MaｘSｉze,),判断循环链队列为空的条件是_＿__＿_＿_为真。1４.如图5所示的二叉树，其后序遍历序列为。eefgibachd图５15.对稀疏矩阵进行压缩存储,可采用三元组表,设a是稀疏矩阵A相应的三元组表类型(结构体类型）变量，ａ中的一个成员项是三元组类型的结构体数组dａｔａ，按书中定义,若a.daｔａ[0].i=2;a．ｄata[0].j=３;a.dａta[０］．v=１6;它提供的Ａ数组的相关信息有___＿___１6.如图6所示的二叉树,其先序遍历序列为_＿_______。ggfabdec图６1７.设有一棵深度为5的完全二叉树,该树共有２0个结点,第五层上有个叶结点。（根所在结点为第1层）18.图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是___＿＿_的。(回答对的或不对的）19．中序遍历______＿＿树可得到一个有序序列。20．二叉树为二叉排序的充足必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是＿_______＿_的。（回答对的或不对的）21.如图７所示的二叉树，其后序遍历序列为___＿_____。3c3c7gd6f5e4dc2b1a8hd9图722.对记录序列排序是指按记录的某个关键字排序,记录序列按＿＿_＿_＿__＿排序结果是唯一的。23.给定一组权重值,构造哈夫曼树，哈夫曼树的高度一定是唯一的,这种说法是_＿＿_______的。(回答对的或不对的)24．按某关键字对记录序列排序，若在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的,否则是不稳定的。三、综合题1.（１）说明什么是顶点活动网(AOV网)和拓扑序列(2)设有向图G如下，写出3种拓扑序列,(3)在图G中增长一条边，使图G仅有一条拓扑序列aabcd图８２．设查找表为（16,１5，20,５３,64,７),（１)用冒泡法对该表进行排序（规定升序排列),写出每一趟的排序过程，通常对ｎ个元素进行冒泡排序要进行多少趟冒泡?第ｊ趟要进行多少次元素间的比较?(2)在排序后的有序表的基础上，画出对其进行折半查找所相应的鉴定树.（规定以数据元素作为树结点）3．如下是一棵二叉排序树,A1,A2,…A9代表１,2，３,…9中各个不同数字,(1)给出对该树中序遍历的结果（2）A3,A５，A7的值各为多少?(3）请在该树中再插入一个结点9.5作为叶结点，并使它仍然是一棵二叉排序树AA1A2A4A7A5A9A8A3A6图94.(1)设有查找表{５,１4,2,6,１８，7,4,１6,3｝，依次取表中数据,构造一棵二叉排序树。(2)说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。５.（1)设有查找表{17,26,14,1６,15,3０,18,19，28},依次取表中数据构造一棵二叉排序树．(2)对上述二叉树给出后序遍历的结果(3).对上述二叉树给出中后序遍历的结果（４)）在上述二叉树中查找元素15共要进行多少次元素的比较?6．(1)对给定权值2,1,３，3，4，5，构造哈夫曼树。(２)同样用上述权值构造另一棵哈夫曼树，使两棵哈夫曼树有不同的高度，并分别求两棵树的带权途径长度。四、程序填空题1．以下函数是二叉排序树的查找算法,若二叉树为空，则返回根结点的指针,否则，返回值是指向树结点的结构指针p(查找成功p指向查到的树结点，不成功ｐ指向为NUＬL)完毕程序中的空格tｙｐedefstｒｕctBnoｄe{iｎtｋeｙ;struｃｔBnｏde*left；structBnode*ｒigｈt；}Bｎｏde；Bnoｄe*BＳearｃh（Ｂnｏde*bｔ,iｎtk)／*bt用于接受二叉排序树的根结点的指针,k用以接受要查找的关键字*/｛Bnｏde*p;ｉｆ(bｔ==__＿(１)__＿__)return（bt);p=ｂt;whｉｌe(p->key!=__(2）______) ﻩ{if(k<p－>ｋey)ﻩﻩ___(3)__＿__；else＿＿_(4）＿____;ﻩif（p==ＮULＬ)bｒeak;}rｅturn(__＿(5)_____）；}}３.设有一个头指针为hｅaｄ的不带头结点单向链表,ｐ、q是指向链表中结点类型的指针变量，p指向链表中结点a,（设链表中没有结点的数据域与结点a的数据域相同）,写出相关语句（1).使该单向链表成为单向循环链表(２）插入结点s,使它成为a结点的直接前驱q=p;x＝p-＞ｄatａ;whilｅ(__(１)＿__）q=q->next;q-＞nexｔ=hｅaｄ;ｑ=p;p＝p－＞nｅxt；ｗhilｅ(p->ｄata!＝x）{q=p;_＿（2)＿_＿｝s-＞neｘt=p;__(3）_＿_答案一、单项选择题1．C2．A3.A４．D5．D6.A7．B8．B9．A１0.A11．Ｂ12．C13．D14．Ｄ１5．B1６.A17.A１8.B19．A２0．Ｃ21.Ｃ２2．Ａ23．D24．B25．Ｃ2６．C27．B28.B29．Ｂ３0.Ｄ二、填空题1．图状结构2．值域左指针3．15４.2i和2i+15.(p->nexｔ)->prｉor=p->prior；６．顺序存储链式存储7.p－>nexｔ=ｓ;８．n9.ａｂcdefg１０.ｎ+111．d=ｔｏｐ->data;12.中序13．fronｔ＝＝rｅar１4.ｇdbｅihfcａ15．A的第一个非零元素的下标为２，3，元素为1６16.aｂdefcg17．５18．对的1９.二叉排序20．不对的２1.22.主关键字23．不对的24．关键字相等的记录三、综合应用题1.(1)原序列1６15205３６4７151６2053７６4ｎ-1趟１51620753６4n-j次1516７205364１５71６205３64７1516２０5３6４71571520641653图1０2．(1）原序列16152053６471516２０53764n-１-j次1５1６720536415７１６2053647１516205３6471571520641653图11（3）平均查找长度=（1＊1+２*2+3*3）/6=14/6３.24246167318514图12(2）中序遍历中序2,3，４,5，6,7，14,16，１８4．(1)2246167318514图13(2）中序遍历中序2,3,4，5，6，7,14，16,18５．535341811763312wｐｌ1=4５1871871131233465图１5wｐl２=４5535341811763312wpl1＝45四、程序填空题１.(１）NＵLL（2)k(3）p=p->left(4)p=p－>ｒighｔ(５)ｐ２.（１）＆a（2)dｎext=NULＬ(3）p->daｔa（4）p=p->neｘｔ(５)p!＝NULL3.（1）q－>next!=NULL（2)p＝p－>ｎext;(3)ｑ->nexｔ=s；4.(1）Pｏｓtorder(BT->ｌeft）（2）Pｏｓｔordｅr(ＢT-＞righｔ）(3)printｆ(“％c”,BＴ->ｄatａ)期末练习三一、单项选择题1．数据结构在计算机内存中的表达是指()。A.数据元素之间的关系B.数据的存储结构Ｃ．数据元素的类型Ｄ.数据的逻辑结构2．在数据结构和算法中,与所使用的计算机有关的是（)。Ａ.数据元数间的抽象关系B．数据的存储结构C．算法的时间复杂度D．数据的逻辑结构3.结构中的元素之间存在多对多的关系是()。A．集合B.线性结构Ｃ.树形结构D．图状结构４.对顺序表，以下叙述中对的的是（）。A．用一组地址连续的存储单元依次存放线性表的数据元素B．各个数据元素的首地址是连续的C.数据元素不能随机访问D.插入操作不需要移动元素5.设有一个长度为2０的顺序表，要在第5个元素之前插入1个元素(也就是插入元素作为新表的第5个元素）,则移动元素个数为（)。A.１5B.１６C.５D.6．设有一个长度为２5的顺序表，要删除第10个元素（下标从1开始），需移动元素的个数为（）。A．9B．10C.15D.7．在一个尾指针为ｒear的不带头结点的单循环链表中,插入一个s所指的结点,并作为第一个结点,可执行()。A．rｅarnｅxt=s;snexｔ＝rearnextB.rearnｅxt=snｅｘt;C．rear＝snｅxtD.sｎexｔ=reaｒｎeｘt;rearｎｅxt＝ｓ;8.设单向链表中,指针p指向结点A，若要删除A的直接后继，则所需修改指针的操作为()。A.p－>next=ｐ->neｘt->next;ﻩＢ.p=p->nexｔ;C.ｐ=p－＞neｘt->ｎeｘt； D.p－>ｎext＝p;9．元素ａ,b，c,ｄ按顺序依次进栈，则该栈的也许输出序列是()（进栈出栈可以交替进行）。Ａ.ｃ,ａ,b,dＢ．ｄ,b,c,aC.a,ｃ,ｂ,ｄＤ．d，c,ａ,ｂ1０．元素1，3,5，7按顺序依次进栈，按该栈的也许输出序列依次入队列，该队列的也许输出序列是(）。(进栈出栈可以交替进行）。A．7，5，3,1B．7,3,1，５C．7,5,1,3D．5,１，3，711.从一个栈顶指针为ｔop的链栈中取栈顶元素,用变量x保存该元素的值,则执行（）。Ａ．ｘ＝ｔoｐ->datａ;tｏp=topnｅxt;Ｂ．ｘ=toｐ->dａta;C．top=ｔｏp－>nｅxt;x=tｏｐ－＞ｄatａ；Ｄ．ｔｏp=top-＞neｘｔ;x=daｔａ;１2．对一个栈顶指针为top的链栈进行进栈操作,设Ｐ为待进栈的结点,则执行（）。Ａ.ｐ＝tｏp->next;top=topnｅｘt;B．ｐ-＞ｎext=top；C.ｐ->neｘt＝ｔoｐ;ｔop=p;Ｄ.tｏｐ=ｐ;1３．设有一个对称矩阵A,采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始），Ｂ数组共有55个元素,则该矩阵是（)阶的对称矩阵。A.5B．20Ｃ.10Ｄ．１5１4．设有一个18阶的对称矩阵A，采用压缩存储的方式,将其下三角部分以行序为主序存储到一维数组B中(数组下标从1开始),则数组中第33号元素相应于矩阵中的元素是()。B.ａ7,6Ａ.a10，8C.a9,215.设有一个１8阶的对称矩阵A，采用压缩存储的方式,将其下三角部分以行序为主序存储到一维数组Ｂ中（数组下标从１开始)，则数组中第53号元素相应于矩阵中的元素是(）。A．a8,５,B．a10，８C．ａ8,1,Ｄ.a7,61６．设有一个1７阶的对称矩阵Ａ，采用压缩存储的方式，将其下三角部分以行序为主序存储到一维数组B中（数组下标从1开始)，则矩阵中元素a16在一维数组B中的下标是（）。Ａ.4５，Ｂ.18C1７.以下程序段的结果是ｃ的值为（）。char*ａ[５]=｛“1237８”，“1237”,“１２36789”，“１237”，inti，ｃ=0;for(ｉ=0;ｉ＜５:i++)ｉｆ(SｔrCmp(a［i],“１237”A.２，B.５C．０Ｄ.１2３7１8．串函数StｒCmp(“ABＣd”,“ABCD”)的值为()。A.０B.-1１9．一棵采用链式存储的二叉树中,共有n个指针域被有效使用（即指针域为非空）。该二叉树有()个结点。A．n+１Ｂ．nC．ｎ-1Ｄ．n-22０．一棵采用链式存储的二叉树中有n个指针域为空,该二叉树共有()个结点。A.n+1Ｂ．nC.ｎ-1D.ｎ-22１.在一棵二叉树中,若编号为ｉ的结点是其双亲结点的右孩子，则双亲结点的顺序编号为（）。A.ｉ/２.０B.i/2+1C.２i+122．设一棵哈夫曼树共有ｎ个非叶结点，则该树有()个结点。A．2nB．２n+2Ｃ.２ｎ－1D.2ｎ+123．设一棵采用链式存储的二叉树，除叶结点外每个结点度数都为２,该树结点中共有2n个指针域为空。则该树有(）个叶结点。Ａ．2nＢ.2n＋1C2４．一棵结点数31<ｎ<40的完全二叉树,最后一层有4个结点,则该树有（)个叶结点Ａ．1８B．１7C.362５．已知如图1所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历,则也许得到的一种顶点序列为(）。A.ａcｅdｆｂB.aecｆdbC．aecdfbＤ．ａcebfdbbdfeca图１２6.已知如图1所示的一个图，若从顶点a出发，按深度优先搜索法进行遍历，则也许得到的一种顶点序列为（）。A.abedｆcＢ．acfeｂｄＣ.aebcfdＤ.aｅdfｂｃ２7.一组记录的关键字序列为（42,37，6２,４0,３2，９２)，运用快速排序算法,以第一个关键字为分割元素，算法通过一次划分后结果为（)。Ａ．３２,37，40，42，62，92B．37,３2，４０，42,62，92C．32,40,3７,42,62，9２D.32，37，42,40，62，9228.一组记录的关键字序列为（46,20,30,79，5６，3８,4０,84,９0,1１0),运用快速排序,以第一个关键字为分割元素,通过一次划分后结果为（）。Ａ.２0,30，４0，38，46，7９,56，８4,90，1０0Ｂ.４0,20，3０,3８,46，５6,７9，84,９０,110C.3０，20,40,3８，46,8４,56，79，９０,100Ｄ．2０,３０３8，４0，46，5６,７9,8４，90,10029．一组记录的关键字序列为(8０,57,４1,39，46,4７)，运用堆排序(堆顶元素是最小元素）的方法建立的初始堆为()。A.39,46,41，57,８0，47B．39,４7，46，80，4１,57C．41，３９,4６，47,5７，80Ｄ.３9，80,46，47,41,５7bbdfeca图230．一组记录的关键字序列为（７５,６3,95，8０，53,４5，38，2０)，运用堆排序（堆顶元素是最大元素)的方法建立的初始堆为（）。A.９5,80,75,63，53，4５,38，２0B.95，63，75,8０，53,45，38,２0c.95,80,4５,63,53,75，3８,20D.9５,8０，７5,20，53,4５，3８,63二、填空题1.数据元素可以有一个或＿______＿组成。2.数据元素之间的抽象关系称为________结构。3.结构中的数据元素存在一对一的关系称为线性结构。而数据元素存在＿＿_＿___的关系称为图状结构。４.规定在ｎ个数据元素中找值最大的元素,其基本操作为＿__＿＿___。算法的时间复杂度为＿__＿_＿＿。5.设有一个长度为2５的顺序表,要删除前3个元素,则最少要移动元素的个数为()。6．设有一个长度为２5的顺序表,第8号元素到第２5号元素依次存放的值为8,9,10,1１,…,2５，某人想要删除第８个元素，他的做法是从第25号元素开始,直到第9号元素依次向前移动1个位置,其结果新表中第9号元素的值为（）。7.在双向链表中，要删除ｐ所指的结点,其中所用的一条语句(p-＞pｒior)->ｎｅxt=p-＞neｘt；的功能是：使P所指结点的直接前驱的右指针指向＿__＿___＿。8．在双向链表中，要在p所指的结后插入q所指的结点(设q所指的结点已赋值),可以先用语句q-＞next=p->nｅxt;（p－>neｘt)->prｉｏr=q；然后再用语句q－>priｏr＝p;和语句__＿__＿__。9．设有一个头指针为hｅａd的单向链表，p指向链表中的某结点，若要使该链表成为单向循环链表,可用语句whilｅ（ｐ->next!＝ＮULＬ）ｐ=p->nexｔ；和＿＿____＿＿。10.在一个单向链表中，要删除p所指结点的直接后继结点。则可以用操作_____＿__。（用一条语句)１１．向一个栈顶指针为ｔop的链栈中插入一个ｐ所指结点时,某人用语句top=p;p->neｘｔ=tｏｐ；这样做的结果使p所指向的结点的指针域指向了__＿__＿_。12．向一个栈顶指针为top的链栈中插入一个ｐ所指结点时，可执行__＿__＿__操作。(填两条语句,结点的指针域为next）１3．在一个链队中,设froｎt和ｒear分别为队头和队尾指针,则s所指结点(数据域已赋值)的入队操作为ｓ->ｎext＝NＵLL;.＿＿___＿__和rear＝s;１４．在一个带头结点的链队中,设ｆront和reaｒ分别为队头和队尾指针，则删除一个结点的操作为ｐ＝front->neｘt；_＿＿____=ｐ->neｘt；(结点的指针域为next，p为辅助用指针）１5．设有ｎ阶对称矩阵A,用一维数组ｓ压缩存储A的下三角元素，s的下标从零开始,元素ｓ[26］相应于A中的元素为_______。１6.设有n阶对称矩阵A，用一维数组s压缩存储A的下三角元素，s的下标从零开始，最后一个元素的下标为2７，则n＝_______。17.对稀疏矩阵进行压缩存储,可采用三元组表，设a是稀疏矩阵Ａ相应的三元组表类型（结构体类型)变量,a中的一个成员项是三元组类型的结构体数组data,按书中定义，若data的下标从零开始,最后一个元素下标为１0，又ｄata[10]．i=8；a.data［10].j=5;a.ｄata[10］．v=3６;它提供的A数组的相关信息有_______。１８.一棵３度的树,其中3度结１个，2度结2个，１度结２个，则该树共有__＿____个叶结点。１9．设有一棵有78个结点的完全二叉树，该树共有＿__＿_____层。(根所在结点为第1层)2０.一棵有7个叶结点的二叉树,其1度结点数的个数为２,则该树共有＿______个结点。21.对于一棵具有_______＿个结点的二叉树，其相应的链式存储结构中共有n+１个指针域空．22.如图２所示的二叉树,其中序遍历序列为____＿_＿_＿。２3．如图２所示的二叉树，其中序遍历序列为__＿___＿__。4g4g3f9a7b58e6c图33c3c7gd65e4dc2b18hd9图424.二叉排序树或者是一棵空树,或者是一棵具有下列性质的二叉排：若它的左子树非空,则左子树的所有结点的值都小于它的根结点的值;若它的右子树非空，则右子的所有结点的值都大于(若允许结点有相同的值,则大于等于）它的根结点的值。这种说法是____＿＿＿___的。(回答对的或不对的)三、综合题1.（１）已知某二叉树的后序遍历序列是debca，中序遍历序列是dbeac,试画出该二叉树。(2）若上述二叉树的各个结点的字符分别代表不同的整数(其中没有相等的)，并恰好使该树成为一棵二叉排序树，试给出a、b、ｃ、d、e的大小关系。（３）给出该树的前序遍历序列。2.(1)以３，4，5，8，９，10作为叶结点的权，构造一棵哈夫曼树。(2)给出相应权重值叶结点的哈夫曼编码。(2)一棵哈夫曼树有2ｎ-1个结点，它是共有多少个权重值构造而成的？简述理由？3.(1)运用筛选过程把序列{42，82，67,１０2，16,32，57，52}建成堆(小根堆)，画出相应的完全二叉树（不规定中间过程）。(2)写出对上述堆相应的完全二叉树进行中序遍历得到的序列。4．（1)简述拓扑排序的环节。（２)说明有向图的拓扑序列不一定是唯一的因素。（3)如何运用拓扑排序算法鉴定图是否存在回路。（４）设有向图G如下，写出一方面删除顶点１的３种拓扑序列。11234543465图５5．设查找表为(1１,12,13,14,15,１6,１7,18,19,2０,21),元素的下标从0开始。（1）画出对上述查找表进行折半查找所相应的鉴定树（树中结点用数值表达）(2)说明成功查找到元素15,１9各需要通过多少次比较？（3)说明查找不到元素10，１5.5各需要通过多少次比较?(4）給出中序遍历鉴定树的序列。6.设有序表为（21，22，２3，2４,25，26，２7,28,29，30,31,32)，元素的下标从0开始。（1）说出有哪几个元素需要通过4次元素间的比较才干成功查到。(2)画出对上述有序表进行折半查找所相应的鉴定树（树结点用数值表达）(3）设查找元素为5,需要进行多少次元素间的比较才干拟定不能查到。(4）求在等概率条件下，成功查找的平均比较次数?四、程序填空题１.以下程序是折半插入排序的算法设待排序的记录序列存放在ａ[1],…ａ[ｎ]中,以ａ[0]作为辅助工作单元，以下程序是要把a[ｉ]插入到已有序的序列a[1],…a[i－1]中。voidbinｓort（NODEａ[],iｎtn)｛iｎtx,ｉ，j,ｓ，k,m;ｆor(i=2;i<=_＿(1)_＿_；i++）{a［0]=a[i]；ｘ=a[ｉ]．key；s=１;j＝i-1;while(s＜=j）｛ｍ＝__(２)_＿_ｉf(x＜a[m].kｅy)__(3)__＿elｓe＿_(4）＿__}for(ｋ=i-1；k>=ｊ+1;ｋ--)_＿(5）___=a［k］;a[j+1]=ａ[0];}}2．以下程序是快速排序的算法设待序的记录序列存放在a[stａｒｔ］,…a[enｄ］中,按记录的关键字进行快速排序,先进行一次划分，再分别进行递归调用ｖoｉdqｕicｋsort(NODEa［］，intstａrt,inｔend){inti，ｊ；NODEｍｉd；ｉf(sｔaｒt＞=end)ｒetｕｒn;ｉ=stａｒt;j＝end;mid=a[i];