2023年本科数据结构本期末综合练习

数据结构(本）期末综合练习期末综合练习一一、单项选择题1.数据的物理结构(D)。Ａ．与数据的逻辑结构无关B．仅仅涉及数据元素的表达C.只涉及数据元素间关系的表达D.涉及数据元素的表达和关系的表达2．数据元素是数据的基本单位，它（C）。Ａ.只能有一个数据项组成B．至少有二个数据项组成C.可以是一个数据项也可以由若干个数据项组成D．至少有一个数据项为指针类型３．从ｎ个数中选取最大元素，（C)。A.基本操作是数据元素间的互换B．算法的时间复杂度是Ｏ(n２)C.算法的时间复杂度是O（ｎ)D.需要进行（n+1）次数据元素间的比较4.线性表的顺序结构中，(C)。Ａ．逻辑上相邻的元素在物理位置上不一定相邻B．数据元素是不能随机访问的Ｃ．逻辑上相邻的元素在物理位置上也相邻D．进行数据元素的插入、删除效率较高5.以下表中可以随机访问的是（D)。Ａ．单向链表B．双向链表C．单向循环链表Ｄ．顺序表6．带头结点的单向链表为空的判断条件是(Ｂ）(设头指针为head）。A．head==NULLB.head－＞next==NULLＣ．ｈｅaｄ->nｅｘt==headD．ｈeａd!=NＵLL７.设顺序存储的线性表长度为n,对于删除操作,设删除位置是等概率的，则删除一个元素平均移动元素的次数为（A)。A．(n+1)/２B．nC.2nD．n-i8.线性结构中数据元素的位置之间存在(A）的关系。A．一对一B.一对多C．多对多D．每一个元素都有一个直接前驱和一个直接后继9．设tｏp是一个链栈的栈顶指针,栈中每个结点由一个数据域daｔa和指针域next组成,设用x接受栈顶元素,则出栈操作为（A)。A.ｘ=top->daｔa;top=toｐ->nｅｘt;B.top＝top-＞next;x=tｏｐ－>ｄａta;C.x=ｔｏp－＞next;toｐ=top－＞ｄata;Ｄ.top-＞ｎext＝ｔoｐ;x=tｏp->data;１0.设顺序存储的线性表长度为n，要删除第ｉ个元素，按课本的算法,当ｉ＝(C）时，移动元素的次数为3A．3Ｂ.ｎ/2C．ｎ-3Ｄ11.以下说法对的的是(C)。Ａ．队列是后进先出B.栈的特点是后进后出C．栈的删除和插入操作都只能在栈顶进行D．队列的删除和插入操作都只能在队头进行１２.以下说法不对的的是(C)。A．栈的特点是后进先出Ｂ.队列的特点是先进先出C.栈的删除操作在栈底进行，插入操作在栈顶进行D.队列的插入操作在队尾进行，删除操作在队头进行１3.串函数ＳtrCmｐ(“abA”，”abａ”)的值为（Ｄ)。Ａ．1B．０Ｃ．“abＡａba”Ｄ1４．一个栈的进栈序列是ａ,b,c,d,则栈的不也许的出栈序列是(A)。A．adbｃB．ｂcadC．cbaｄD.dｃｂa１5.设有一个１2阶的对称矩阵A，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中(矩阵A的第一个元素为a1,１,数组ｂ的下标从１开始),则矩阵A中第４行的元素在数组b中的下标i一定有（A)。A．7≤i≤10B．１１≤i≤15C．９≤i≤14D．6≤i≤16.已知一个图的边数为m,则该图的所有顶点的度数之和为(A)。Ａ.2mB.mC.2ｍ+１Ｄ.m/２17.设有一个带头结点的链队列,队列中每个结点由一个数据域datａ和指针域next组成,froｎt和ｒeａr分别为链队列的头指针和尾指针，要执行出队操作,用x保存出队元素的值，p为指向结点类型的指针，可执行如下操作:p=ｆｒｏｎｔ-＞ｎｅxt;x=p->data;然后执行（B)。Ａ.fｒont＝p-＞ｎeｘｔ;B.fronｔ->next=p->ｎext；C.front=p;D.front->neｘｔ=ｐ;18．以下说法不对的的是（D)。A.连通图Ｇ一定存在生成树B．连通图Ｇ的生成树中一定包含G的所有顶点C．连通图G的生成树中不一定包含G的所有边Ｄ．连通图G的生成树可以是不连通的１9．散列查找的原理是（A）。A．在待查记录的关键字值与该记录的存储位置之间建立拟定的相应关系B.按待查记录的关键字有序的顺序方式存储C．按关键字值的比较进行查找D.基于二分查找的方法２０.空串的长度为（A)。A.0B.1C．2D2１．排序过程中，每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置，直到所有排好序为止,该排序算法是(D)。Ａ．选择排序Ｂ．快速排序Ｃ.冒泡排序D．直接插入排序２２．采用顺序查找法对长度为n的线性表进行查找(不采用表尾设监视哨的方法）,最坏的情况下要进行（B）次元素间的比较。A.n+2B．nC．n-1Ｄ．ｎ／223.设有一个10阶的对称矩阵A,采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。(矩阵A的第一个元素为a1，1,数组b的下标从1开始),则矩阵元素a5,3相应一维数组b的数组元素是（C）。A．b[18］B．b[8]Ｃ.b[1３］Ｄ．b[1０]24．如图１若从顶点a出发按广度优先搜索法进行遍历，则也许得到的顶点序列为（D）。ababecdhgfB．aeｂcghdfC.ａeｄfbcghD．abecdfgh图125.已知如图2所示的一个图,若从顶点a出发,按深度优先搜索法进行遍历,则也许得到的一种顶点序列为（Ｄ)。Ａ．abeｃdｆB．acfｅbdC．aeｂcｆdD．aeｄfcbbbdfeca图22６.一棵哈夫曼树总共有23个结点，该树共有（D）个叶结点(终端结点)。A．10B.13C．１１二、填空题1.通常数据的逻辑结构涉及集合、线性、_树形_、_图状四种类型。2.通常可以把某城市中各公交站点间的线路图抽象成＿＿图状＿＿结构。３.设有一个单向链表,结点的指针域为nｅxｔ,头指针为ｈeaｄ,ｐ指向尾结点，为了使该单向链表改为单向循环链表，可用语句__＿p-＞ｎext=ｈeａd；_____。4．设有一个单向循环链表,头指针为heａd，链表中结点的指针域为next，p指向尾结点的直接前驱结点,若要删除尾结点，得到一个新的单向循环链表，可执行操作＿_＿___＿＿p－>next＝head。5．循环队列的队头指针为ｆ,队尾指针为r,当__＿r=f_＿___时表白队列已空。6．在一个链队中,ｆ和r分别为队头和队尾指针,队结点的指针域为ｎext，则插入一个s所指结点的操作为___ｒ－>nｅｘt=s___;r=ｓ；７．设有一个链栈，栈顶指针为hs,现有一个s所指向的结点要入栈，则可执行操作__s->nｅxt=hs和hs=ｓ；8．循环队列的队头指针为f，队尾指针为r,当___r＝=f_时表白队列为空。9.在一个链队中，f和r分别为队头和队尾指针,队结点的指针域为next，则插入一个ｓ所指结点的操作为__r->next＝ｓ___；r=s;１０.“A”在存储时占___２____个字节。11.串的两种最基本的存储方式分别是＿顺序存储__和_＿链式存储＿_。12.一棵二叉树没有单分支结点，有6个叶结点,则该树总共有___11__个结点。13．一棵二叉树中顺序编号为i的结点,若它存在左、右孩子,则左、右孩子编号分别为___＿２ｉ___、＿_2ｉ＋1___。1４．按照二叉树的递归定义,对二叉树遍历的常用算法有_先序、_中序＿、_后序＿三种。１5．两个串相等的充足必要条件是串长度相等且相应位置的字符相等。1６．把数据存储到计算机中，并具体体现数据之间的逻辑结构称为_物理（存储）_结构。１７．一棵二叉树叶结点(终端结点)数为５，单分支结点数为2，该树共有_＿１1__个结点。18．如图3所示的二叉树，其后序遍历序列为ｇdbｅihfｃa。eefgibachd图319．根据搜索方法的不同,图的遍历有＿＿深度优先搜索遍历_、_广度优先搜索遍历方法。２0.二叉树为二叉排序的充足必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是__错误___＿＿的。(回答对的或不对的)21．一个有序表｛3,４,10,１４,34,43，46，６4，75,７8,90，９６，130}用折半查找法查找值为90的结点，经___４＿_＿_次比较后查找成功。三、综合题1．（1）已知某二叉树的后序遍历序列是debcａ,中序遍历序列是dbeac，试画出该二叉树ababced答：d<b＜e＜a<c（3）给出该树的前序遍历序列答:abdec2．(１）一组记录的关键字序列为｛４５，４0，65,43,35,95},写出运用快速排序的方法，以第一个记录为基准得到的一趟划分的结果（规定给出一趟划分中每次扫描和互换的结果）答：45４0654３35９５354065433595354０65４３6595354043４365953５4043456595(2)对序列{4５，４０，6５,43，３５,95}运用直接插入排序,写出逐次插入过程(从第一个元素一直到第六个元素）。答404565４33５９540４3４5６5359５３540434565954028724028723100546(2）对上述二叉排序树，在等概率条件下，求成功查找的平均查找长度答:ASL=（1x1＋2x2+3x3＋４)/7=１8/７４．(1)设有查找表{５，14,2,6,１8，７，4，16,3},依次取表中数据，构造一棵二叉排序树.242461673185145答:中序遍历1642325216423252576782102初始树堆4初始树堆42826752573216102(2)写出对上述堆相应的完全二叉树进行中序遍历得到的序列答:１02，52，４２，8２，16，６７，32,57四、程序填空题１．以下函数在ａ[0]到a[n-1]中，用折半查找算法查找关键字等于ｋ的记录,查找成功返回该记录的下标,失败时返回－１,完毕程序中的空格tyｐｅdefstruct{ｉｎｔkey；……}NODE；iｎtBinａｒy_Seaｒch(NＯDEa[],intn,intk)｛iｎtlow，ｍｉd,high;ｌｏw=0;ｈigｈ=n-1；ｗhilｅ(__ｌow<=higｈ＿＿__){mid=（low+higｈ)/2;if(a[mｉd].key==ｋ)ｒetuｒｎ__mid＿_＿___； elsｅｉf(_＿a[ｍid］．ｋeｙ＜k;_＿_)lｏw＝mid＋1; else_hｉｇｈ=mid-1_＿___;ﻩ}_＿reｔｕrn－1＿___;ﻩ}2．以下函数为链栈的进栈操作,ｘ是要进栈的结点的数据域,tｏp为栈顶指针sｔructｎｏde{EleｍTyｐedata;structnode*nｅｘt;}；stｒuｃｔnode*top；vｏidPuｓh(ＥlemTyｐeｘ)｛ｓtｒucｔnoｄe＊p;p=（sｔructｎode*)malloｃ（＿sｉｚeof（ｓtｒuｃtnode)___);p->data=x;__p－>next＝tｏｐ＿__；__top=p__；}3．以下函数为链队列的入队操作,x为要入队的结点的数据域的值,ｆronｔ、reａr分别是链队列的队头、队尾指针structnode｛ＥlemTｙpedａta;stｒuctｎodｅ＊nexｔ;};ｓtructnoｄe*front，*ｒｅar；voｉｄIｎＱueue（ElemTypｅx){sｔrｕctnｏde*p；p=(sｔｒuctnode*)_＿_mａｌlｏc(ｓizｅof(struｃtnode））____;p－>daｔa=x;p-＞nｅｘt=ＮＵLL;＿_reaｒ->nｅxｔ=ｐ____;ｒear=＿＿_p_____;}期末综合练习二一、单项选择题１．（B)是性质相同的数据元素的集合,是数据的子集。A．数据元素B.数据对象Ｃ．数据结构D.数据项2．同一种逻辑结构(Ｂ)。A.只能有唯一的存储结构B．可以有不同的存储结构C.只能表达某一种数据元素之间的关系D．以上三种说法均不对的3．设链表中的结点是ＮODE类型的结构体变量,且有NODＥ*ｐ；为了申请一个新结点,并由ｐ指向该结点，可用以下语句(Ａ）。A.ｐ=(NＯＤＥ＊)ｍalloｃ(sizeof(ＮODE))；Ｂ.p＝（*ＮＯDE)maｌloc(ｓizeof(ＮODE))；C．p＝(NODE)mａlloc(sizeof(p));D．ｐ=(NOＤE＊）ｍａlloc（sizeｏf(ｐ))；4．链表所具有的特点是(C）。A．可以随机访问任一结点B.占用连续的存储空间Ｃ.插入删除元素的操作不需要移动元素结点D．可以通过下标对链表进行直接访问５．设顺序存储的线性长度为n,要在第i个元素之前插入一个新元素，按课本的算法当i=(Ｄ）时,移动元素次数为2A.ｎ/2B．nC．１D.n－１6.数据的物理结构(D)。A．与数据的逻辑结构无关B.仅仅涉及数据元素的表达Ｃ．只涉及数据元素间关系的表达D．涉及数据元素的表达和关系的表达7.一个栈的进栈序列是1,2,3,４,则栈的不也许的出栈序列是（B）（进出栈操作可以交替进行）A.3,2,４，１B．1，4,2,３Ｃ.4，3，2，１D.3,２，1,48．线性结构中数据元素的位置之间存在(Ａ）的关系。Ａ.一对一Ｂ．一对多C.多对多D.每一个元素都有一个直接前驱和一个直接后继9．设有一个带头结点的链队列,队列中每个结点由一个数据域ｄata和指针域nｅxｔ组成，frｏnt和ｒeａｒ分别为链队列的头指针和尾指针。设p指向要入队的新结点(该结点已被赋值),则入队操作为（A)。A.rｅar->neｘt=p；reaｒ=ｐ；Ｂ.rear->nｅxｔ=p;p=reａr;C.p=reａr->next;rｅar=p;D．rear=p;ｒｅａｒ->next=p;1０．以下表中可以随机访问的是(D)。A.单向链表B．双向链表C．单向循环链表D．顺序表1１．以下说法不对的的是(C)。A．顺序栈中，栈满时再进行进栈操作称为“上溢”B．顺序栈中，栈空时再作出栈栈操作称为“下溢”C.顺序队列中，当尾指针已经超越队列存储空间的上界，则一定是队列已满D．顺序队列中,队列的头指针和尾指针均超越队列存储空间的上界,则队列已空12.算法的时间复杂度与(Ｃ)有关。Ａ.所使用的计算机B．与计算机的操作系统C.与算法自身D．与数据结构1３．设有一个20阶的对称矩阵A，采用压缩存储方式,将其下三角部分以行序为主序存储到一维数组中（矩阵A的第一个元素为a11,数组b的下标从1开始)，则矩阵元素a8,5在一维数组b中的下标是（D）。A.30Ｂ.28C.４0Ｄ14.设有一个长度为n的顺序表，要删除第i个元素需移动元素的个数为(B)。A.n-i＋1B．n-ｉC．n-i-1D．ｉ15.深度为5的完全二叉树第5层上有4个结点,该树一共有(Ｄ）个结点。A．２8B.30C.３1D16．在一个单链表中,p、q分别指向表中两个相邻的结点,且q所指结点是p所指结点的直接后继,现要删除ｑ所指结点，可用的语句是（Ｃ)。A.ｐ=q->nextB.ｐ->ｎext=qC．p->next=ｑnexｔD.q->ｎeｘt=NULL17.已知一个图的所有顶点的度数之和为m，则ｍ一定不也许是（D）。Ａ．４B.8C．1２D18.从一个栈顶指针为tｏｐ的链栈中删除一个结点时，用变量ｘ保存被删结点的值，则执行(A)。A．x=toｐ－＞dａta；top＝top-＞nｅxｔ;Ｂ．x＝ｔoｐ->dａta;C．ｔｏp＝top－>ｎｅｘt;x＝toｐ->dａta；D.ｔｏp=top－>ｎｅxt；x=daｔa;19.以下说法对的的是(D)。Ａ．连通图Ｇ的生成树中可以包含回路B．连通图G的生成树可以是不连通的C.连通图G的生成树一定是唯一的Ｄ．连通图Ｇ的生成树一定是连通而不包含回路的20.在一个链队中，假设f和r分别为队头和队尾指针，则删除一个结点的运算为(C）。Ａ.r=f->next;B．r=r->next;C．f=f->nｅxt;D.ｆ=ｒ－>ｎext；2１．对ｎ个元素进行冒泡排序,通常要进行ｎ-1趟冒泡，在第j趟冒泡中共要进行（C)次元素间的比较。Ａ.jＢ.j-1Ｃ.n-jD22．一个栈的进栈序列是a，b，ｃ，d,ｅ,则栈的不也许输出序列是（A)(进栈出栈可以交替进行）。A．ｄceabB．ｅdcbaC．ｄｅcbaD.ａbcde２3.在排序过程中，可以有效地减少一趟排序过程中元素间的比较次数的算法是(D)。A.冒泡B.选择C.直接插入D.折半插入2４．有一个长度为１0的有序表,按折半查找对该表进行查找,在等概率情况下查找成功的平均比较次数为(B）。A．2６/１0B.2９/１0C2５.如图1若从顶点a出发按深度优先搜索法进行遍历,则也许得到的顶点序列为(B）。abecabecdfB．abｅｄｃfC.acｅbdｆD．ａcfbde图126.排序算法中，从未排序序列中依次取出元素与已排序序列(初始为空）中的元素进行比较（规定比较次数尽量少),然后将其放入已排序序列的对的位置的方法是（C）。A.冒泡B.直接插入C.折半插入D.选择排序２7．一棵哈夫曼树有n个叶子结点（终端结点),该树总共有(B）个结点。Ａ．2n－2B．2n-1C.2nＤ２8.设有一个10阶的对称矩阵A,采用压缩存储的方式,将其下三角部分以行序为主存储到一维数组B中（数组下标从1开始）,则矩阵中元素A8,5在一维数组Ｂ中的下标是（A)。A．33B.32C29．数据的(A）结构与所使用的计算机无关。A．逻辑B.物理Ｃ.存储D．逻辑与存储30．在一个无向图中,所有顶点的度数之和等于边数的(Ｄ)倍。A.3Ｂ．２．5C二、填空题1．通常可以把一本具有不同章节的书的目录结构抽象成___树形__结构。2．栈和队列的操作特点分别是__先进后出__＿和＿__先进先出＿_。3.要在一个单向链表中p所指向的结点之后插入一个s所指向的新结点，若链表中结点的指针域为ｎexｔ,可执行＿＿s－>neｘt＝p－>neｘt;_＿____和p-＞nexｔ=s;的操作。4.结构中的数据元素存在多对多的关系称为____图状（网状）__结构。5．设有一个非空的链栈，栈顶指针为ｈs，要进行出栈操作,用ｘ保存出栈结点的值,栈结点的指针域为ｎｅxｔ,则可执行x=hs->dａtａ;__＿hs＝hｓ->ｎext;＿＿＿__。6．根据数据元素间关系的不同特性,通常可分为集合、线性、树形、图状四类基本结构。7.在一个不带头结点的非空链队中，ｆ和r分别为队头和队尾指针,队结点的数据域为datａ，指针域为ｎｅxt，若要进行出队操作，并用变量ｘ存放出队元素的数据值，则相关操作为x＝f-＞ｄatａ;__f=f->ｎeｘｔ;______。8．规定在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为___＿＿_＿_和＿n-1，O(n）____＿__。9.循环队列的最大存储空间为MａxSｉzｅ=８，采用少用一个元素空间以有效的判断栈空或栈满，若队头指针front=4,则当队尾指针rｅar=____4__＿_时，队列为空，当reａr＝___2_____时，队列有6个元素。10．稀疏矩阵存储时，采用一个由__行号__、__＿列号＿、_＿非零元＿_3部分信息组成的三元组唯一拟定矩阵中的一个非零元素。11．在二叉树的链式存储结构中，通常每个结点中设立三个域,它们是值域左指针、右指针。１2．一棵二叉树顺序编号为6的结点（树中各结点的编号与等深度的完全二叉中相应位置上结点的编号相同），若它存在右孩子,则右孩子的编号为＿__13_＿___。１3.向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行s-＞next=h;和_＿ｈ=ｓ__。14.在一个链队中,设ｆ和r分别为队头和队尾指针,则插入s所指结点的操作为__ｒ->neｘt=s＿_和r＝ｓ；(结点的指针域为nｅｘt)15．如图2所示的二叉树，其前序遍历序列为__＿abdefcg__。ggfabdec图2１6.设有一棵深度为4的完全二叉树,第四层上有5个结点，该树共有＿__12__个结点。（根所在结点为第１层）１7.在队列的顺序存储结构中，当插入一个新的队列元素时，尾指针的值增1，当删除一个元素队列时，头指针的值增1。18.对稀疏矩阵进行压缩存储,矩阵中每个非零元素相应的三元组涉及该元素的__行下标＿、__列下标_和__＿非零元素值_三项信息。19．循环队列的引入，目的是为了克服假上溢。20.在对一组记录（５5,39,９7,22,16,７3,65，４7,88）进行直接插入排序时,当把第7个记录６５插入到有序表时,为寻找插入位置需比较_＿_3______次。三、综合题1．(1)设ｈead１和ｐ1分别是不带头结点的单向链表A的头指针和尾指针，heaｄ2和ｐ２分别是不带头结点的单向链表B的头指针和尾指针,若要把B链表接到A链表之后,得到一个以head1为头指针的单向循环链表，写出其中两个关键的赋值语句（不用完整程序,结点的链域为ｎext）。答:ｐ1－>ｎeｘt＝heａd2;p2->ｎext=ｈeaｄ1；（2)单向链表的链域为nexｔ,设指针ｐ指向单向链表中的某个结点，指针s指向一个要插入链表的新结点，现要把ｓ所指结点插入p所指结点之后,某学生采用以下语句:p->ｎext=s;s－>nｅxt=p-＞nexｔ;这样做对的吗？若对的则回答对的，若不对的则说明应如何改写答：不对,ｓ-＞ｎext=p－>next；p->next=s；２.（1)以２，3,４,７,8,９作为叶结点的权,构造一棵哈夫曼树(规定每个结点的左子树根结点的权小于等于右子树根结点的权)，给出相应权重值叶结点的哈夫曼编码。3333(1）1518151879987998545432322:111０3:１11１4：1107:008:0１9：10（２)一棵哈夫曼树有ｎ个叶结点，它一共有多少个结点？简述理由？答:２n-1个,由于非叶结点数比叶结点数少一个。３．（1）画出对长度为10的有序表进行折半查找的鉴定树(以序号1，2,……１0表达树结点）5252849631071答:AＳL=(１ｘ１＋2x2＋3ｘ4＋４x３）/10=2９／１04.一组记录的关键字序列为（46，79，5６,３8,4０,84）（1)运用快速排序的方法，给出以第一个记录为基准得到的一次划分结果(给出逐次互换元素的过程,规定以升序排列)初始序列4６,７9，56，38，４0,8440,79，5６，38，40,8440，７9，56,38，7９，84４0,3８,56,3８,7９,8440，38,56，56,7９，８４40,3８，46，５6,79，84(2）对上述序列用堆排序的方法建立大根堆，规定以二叉树逐次描述建堆过程。3777624752377762475227119711372747526277975679384084468479384046566567938404679384084845646初始树堆初始树堆（2）写出对上述堆所相应的二叉树进行前序遍历得到的序列答：11,3７，47,97,77,27,62，526．设查找表为(50，60,75,８5,96,９8,105，110，１20,１30)(1）说出进行折半查找成功查找到元素120需要进行多少次元素间的比较？３次(２)为了折半查找元素９5,通过多少次元素间的比较才干拟定不能查到?4次967596759813010585501100512060四、程序填空题１．以下函数为直接选择排序算法，对a[１］,a［2］,…a[n]中的记录进行直接选择排序，完毕程序中的空格typeｄefstruct{ｉntkey;……}ＮODE；voidselsorｔ（NＯDEa[］,ｉｎｔn)｛ inti，j,k;ﻩNOＤEtｅｍp;ﻩfor（i=１;i<=__n-1___;i＋+) {ﻩ ｋ=i；ﻩﻩｆｏr(j=ｉ+1;j<=___ｎ＿_＿;j＋+）ﻩ ﻩif(a［j］.key<a［ｋ]．kｅy)＿_ｋ=j＿＿___; if(i!=k）ﻩﻩ{ﻩ ﻩtemｐ=ａ［i]; ﻩ__ａ［i]＝a[ｋ]___;ﻩﻩ __＿a[k］=temｐ_;ﻩ }ﻩ}}２.以下是用尾插法建立带头结点且有n个结点的单向链表的程序,结点中的数据域从前向后依次为１,2,3,……,n，完毕程序中空格部分。ＮＯDE*ｃreate(ｎ){NODE*hｅaｄ,*p,＊ｑ;inti;p＝(ＮODＥ*）malloc(ｓizeoｆ(ＮＯDE));ｈｅad=p;q＝ｐ；pnext=ＮULL;/＊建立头结点＊/for(ｉ=1;i＜=n；i++）{p＝（ＮODＥ＊)maｌloｃ(ｓizeoｆ(NOＤＥ）);ｐdａｔａ=i;pｎeｘt=ＮULL；qnext=p;q=p;}retｕｒn（head);}3．以下程序是中序遍历二叉树的递归算法的程序,完毕程序中空格部分(树结构中左、右指针域分别为lｅft和ｒight，数据域dａta为字符型，BT指向根结点）。vｏiｄInordeｒ（strucｔBＴｒｅeNodｅ*BT)｛if（BT!=NULL）{Iｎorder(BT->ｌeft);printf（“%c”,BT->data);Inoｒdeｒ(BＴ-＞righｔ);}}期末综合练习三一、单项选择题１.深度为５的完全二叉树共有20个结点,则第5层上有(C)个结点(根所在结点为第一层)。A．３B.8C.5Ｄ2.在C语言中,顺序存储长度为3的字符串,需要占用（A）个字节。A．4B．3C3．已知一个图的边数为m，则该图的所有顶点的度数之和为(A）。Ａ.２mB.mC.２m+1D.m／24.串函数SｔrCat（a,b）的功能是进行串（D）。A.比较Ｂ．复制C.赋值D．连接５．数据结构中，与所使用的计算机无关的是数据的(Ｄ)结构。A.物理Ｂ．存储C.逻辑与物理D．逻辑６.一棵有ｎ个结点采用链式存储的二叉树中，共有（A)个指针域为空。A.ｎ＋1B．nＣ．n-1D．n-２7.链表所具有的特点是(Ｃ)。A．可以随机访问任一结点B.占用连续的存储空间C．插入删除不需要移动元素结点D.可以通过下标对链表进行直接访问８．设一棵哈夫曼树共有ｎ个非叶结点，则该树有（B）个叶结点。A．nB．n+1C9.线性表只要以(C）方式存储就能进行折半查找。A．链接Ｂ．顺序Ｃ．关键字有序的顺序Ｄ．二叉树10．从一个栈顶指针为ｔop的链栈中删除一个结点时，用变量x保存被删结点的值，则执行（A)。A.ｘ=top－>ｄata；ｔop=tｏpnext;B．x=ｔop->data;C.tｏｐ=tｏp－＞ｎeｘt；x=top->ｄａｔa;D.ｔop＝top->neｘt；ｘ=data;11．散列查找的原理是（A）。A．在待查记录的关键字值与该记录的存储位置之间建立拟定的相应关系B．按待查记录的关键字有序的顺序方式存储Ｃ.按关键字值的比较进行查找D．基于二分查找的方法12.一棵完全二叉树共有５层,且第5层上有六个结点，该树共有(C)个结点。Ａ.3０B．20Ｃ１3.对n个元素进行冒泡排序若某趟冒泡中只进行了(C)次元素间的互换,则表白序列已经排好序。A．1B.２C.0Ｄ14．在一个无向图中，所有顶点的度数之和等于边数的(Ｄ)倍。Ａ．3B.２.５Ｃ15．排序过程中,每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置,直到所有排好序为止，该排序算法是（A)。Ａ．直接插入排序B．快速排序C．冒泡排序Ｄ．选择排序16.已知如图1所示的一个图,若从顶点V1出发，按深度优先搜索法进行遍历，则也许得到的一种顶点序列为(Ａ)。A．V1V2V4Ｖ8Ｖ5V3V6V7B.V1V2V4Ｖ5V８V3V６V7C．Ｖ1V2Ｖ4V8V3V５V6V7Ｄ.V1V3Ｖ6V7V2Ｖ4V5V8V6V6V7V1V2V3V8V4V5图117.在对一组元素(64，4８，106,３3,25，82,7０，５５，93)进行直接插入排序时，当进行到要把第7个元素70插入到已经排好序的子表时,为找到插入位置，需进行(Ｃ)次元素间的比较（指由小到大排序）。A．6B.２C.３D1８．已知如图２所示的一个图,若从顶点a出发,按广度优先搜索法进行遍历,则也许得到的一种顶点序列为（B）。A．abｃedfB.abceｆdC．aebｃfdD.acfdebbdbdfeca图2１9.采用顺序查找法对长度为n的线性表进行查找(不采用表尾设监视哨的方法），最坏的情况下要进行（B）次元素间的比较。A.n+２Ｂ.nC．n-1D．n/２20．对二叉排序树进行（Ｃ）遍历,可以使遍历所得到的序列是有序序列。A．按层次Ｂ.后序C.中序Ｄ．前序2１．如图３，若从顶点ａ出发按广度优先搜索法进行遍历，则也许得到的顶点序列为(Ｂ)。Ａ．ａcebｄｇｆB.aｂecdgｆC．acfeｄgｂＤ．abecfｄｇaabecdfg图32２.在有序表{2，4,7,１4，34,４3，47,64,７5,8０，9０，9７，1２０}中，用折半查找法查找值8０时,经(Ｂ)次比较后查找成功。A．4B.2C.3Ｄ.５2３．元素2，4，６，8按顺序依次进栈,则该栈的不也许输出序列是(D)(进栈出栈可以交替进行）。A．8，6,4，２B．２，4,6,8C．４，2，8,6D.８,６,2，424．有一个长度为9的有序表,按折半查找对该表进行查找,在等概率情况下查找成功的平均比较次数为（Ｂ)。A.２5/１0B．25/９C25.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列(初始为空)的一端的方法，称为（C）排序。Ａ.归并B．插入C.选择Ｄ．快速26.排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空）中的元素进行比较（规定比较次数尽量少),然后将其放入已排序序列的对的位置的方法是(Ｃ)。A.冒泡B.直接插入C．折半插入D．选择排序27.一棵哈夫曼树总共有２3个结点，该树共有（D)个叶结点(终端结点）A．１0B.1３Ｃ.112８．一组记录的关键字序列为(46,79，56，38，4０,８4），运用快速排序,以第一个关键字为分割元素，通过一次划分后结果为（Ｂ）。A.40,3８，４6,7９，5６,84B.40,３8，４6，56,７９，84Ｃ.40，38，４６,84，５6，79D．3８,40,4６，56，79,8429.队列的插入操作在（B）进行。A.队头Ｂ.队尾C．队头或队尾D．在任意指定位置二、填空题(每小题2分，共2４分）1.一棵二叉树没有单分支结点，有6个叶结点，则该树总共有＿_＿_11____个结点。2．在二叉树的链式存储结构中，通常每个结点中设立三个域，它们是_值域＿＿、左指针、右指针。3.设一棵完全二叉树,其最高层上最右边的叶结点的编号为奇数,该叶节点的双亲结点的编号为１0，该完全二叉树一共有___２1___个结点。4．一棵二叉树中顺序编号为i的结点，若它存在左、右孩子，则左、右孩子编号分别为_＿__2i_、_＿_2i+1___＿。５.按照二叉树的递归定义，对二叉树遍历的常用算法有_＿先序_、___中序＿、__后序_三种。６．串的两种最基本的存储方式是__顺序存储_和__链式存储_＿_。７.数据结构中的数据元素存在一对多的关系称为___树形_____结构。8.一棵有2n-１个结点的二叉树，其每一个非叶结点的度数都为2,则该树共有___N____个叶结点。9.把数据存储到计算机中,并具体体现数据之间的逻辑结构称为__＿物理（存储)_＿___结构。1０.对于一棵具有ｎ个结点的二叉树,其相应的链式存储结构中共有__ｎ+1_＿___＿个指针域为空。11.结构中的数据元素存在一对一的关系称为_＿线性__结构。12．__中序_＿___＿遍历二叉排序树可得到一个有序序列。1３.如图4所示的二叉树，其后序遍历序列为ｇdｂｅihfcａ。eefgibachd图4１4．n个元素进行冒泡法排序，通常需要进行_＿n-1＿_趟冒泡。15．如图5所示的二叉树,其先序遍历序列为__abdefcg_＿。ggfabdec图5１6.二叉树为二叉排序的充足必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是__不对的_＿__的。(回答对的或不对的)１７．图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是＿对的_____的。(回答对的或不对的)１8．根据搜索方法的不同,图的遍历有_＿深度优先搜索遍历_、＿广度优先搜索遍历＿两种方法１9．对记录序列排序是指按记录的某个关键字排序，记录序列按_＿主关键字___＿_＿_排序结果是唯一的。20．按某关键字对记录序列排序，若关键字相等的记录在排序前和排序后仍保持它们的前后关系,则排序算法是稳定的,否则是不稳定的。1642164232525767821021．（１)运用筛选过程把序列{4２，82,67,１02,16，32，57，52｝建成堆（小根堆)，画出该堆（不规定中间过程）。(２)写出对上述堆相应的完全二叉树进行中序遍历得到的序列。 答:10２,52，4２,82，16,6７,32,5７2．设查找表为(16，15,2０,5３,64,7)，(１)用冒泡法对该表进行排序(规定升序排列）,写出每一趟的排序过程,通常对n个元素进行冒泡排序要进行多少趟冒泡?第j趟要进行多少次元素间的比较?答:(1)原序列16１520５３６47151６20５37