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

数据结构（本）期末综合练习202３年12月期末综合练习一一、单项选择题1．数据的物理结构(）。A．与数据的逻辑结构无关Ｂ.仅仅涉及数据元素的表达C．只涉及数据元素间关系的表达D．涉及数据元素的表达和关系的表达2.深度为5的完全二叉树共有２０个结点,则第5层上有()个结点(根所在结点为第一层)。A.３B．8C.5D3.从ｎ个数中选取最大元素（）。Ａ．基本操作是数据元素间的互换B.算法的时间复杂度是O(ｎ2)C.算法的时间复杂度是O(n）D．需要进行(n+1)次数据元素间的比较4．已知一个图的边数为m，则该图的所有顶点的度数之和为(）。A．2mB．mC.2ｍ+１D.m/25．线性表的顺序结构中,（)。A.逻辑上相邻的元素在物理位置上不一定相邻Ｂ．数据元素是不能随机访问的Ｃ.逻辑上相邻的元素在物理位置上也相邻D．进行数据元素的插入、删除效率较高6.数据结构中，与所使用的计算机无关的是数据的()结构。A.物理B.存储C.逻辑与物理Ｄ.逻辑７．带头结点的单向链表为空的判断条件是()（设头指针为hｅaｄ）。A.ｈead==NULＬB．head->nexｔ==NULＬC.head－＞neｘt=＝headD.heaｄ!=ＮULL8.链表所具有的特点是(）。Ａ．可以随机访问任一结点B.占用连续的存储空间C.插入删除不需要移动元素结点D.可以通过下标对链表进行直接访问9．线性结构中数据元素的位置之间存在(）的关系。A.一对一B.一对多C.多对多Ｄ．每一个元素都有一个直接前驱和一个直接后继10.线性表只要以()方式存储就能进行折半查找。A．链接Ｂ．顺序Ｃ．关键字有序的顺序D．二叉树11.设顺序存储的线性表长度为n，要删除第i个元素,按课本的算法,当i＝()时,移动元素的次数为3A.3Ｂ.n/2C．n-3D12.散列查找的原理是（）。A．在待查记录的关键字值与该记录的存储位置之间建立拟定的相应关系B．按待查记录的关键字有序的顺序方式存储C．按关键字值的比较进行查找Ｄ.基于二分查找的方法1３.以下说法不对的的是（)。Ａ.栈的特点是后进先出B.队列的特点是先进先出C．栈的删除操作在栈底进行，插入操作在栈顶进行Ｄ．队列的插入操作在队尾进行,删除操作在队头进行１4.对ｎ个元素进行冒泡排序若某趟冒泡中只进行了（)次元素间的互换,则表白序列已经排好序。A.１B.2Ｃ.0D15．一个栈的进栈序列是a,ｂ,c，ｄ,则栈的不也许的出栈序列是（）。A．adbcB．bcadＣ．cbaｄＤ.ｄcba16.排序过程中,每一趟从无序子表中将一个待排序的记录按其关键字的大小放置到已经排好序的子序列的适当位置，直到所有排好序为止，该排序算法是()。A．直接插入排序Ｂ.快速排序C．冒泡排序Ｄ．选择排序1７.设top是一个链栈的栈顶指针,栈中每个结点由一个数据域ｄata和指针域ｎｅｘt组成,设用x接受栈顶元素，则出栈操作为()。A．x=top->ｄata;top=ｔｏp->neｘt;B.tｏp=tｏp－>nexｔ；ｘ=toｐ－>data；C．ｘ＝top->nｅxt;ｔop=top－＞data;D．toｐ->next=toｐ；x＝top－＞ｄata;18．在对一组元素（64,48，106,３3,25,8２，7０，55，９3)进行直接插入排序时，当进行到要把第７个元素７０插入到已经排好序的子表时，为找到插入位置,需进行（)次元素间的比较(指由小到大排序）。A．6Ｂ．２C.３D１9.设有一个带头结点的链队列,队列中每个结点由一个数据域data和指针域nｅｘｔ组成，ｆroｎt和rear分别为链队列的头指针和尾指针,要执行出队操作,用x保存出队元素的值,p为指向结点类型的指针，可执行如下操作:p=frｏnｔ->next;x＝p－>daｔa;然后执行(）。A.fronｔ=p->next;B．front->ｎext=p->next;Ｃ.ｆｒont=p；D．fｒont-＞nｅxt=p;20.采用顺序查找法对长度为n的线性表进行查找(不采用表尾设监视哨的方法),最坏的情况下要进行（)次元素间的比较。A．n+２B．ｎC．n－1Ｄ．ｎ/221．以下说法对的的是（）。A．队列是后进先出Ｂ.栈的特点是后进后出C．栈的删除和插入操作都只能在栈顶进行D.队列的删除和插入操作都只能在队头进行abecabecdfgＡ．acebｄｇｆＢ.abecdｇfC．acfedgbD.ａｂecfdｇ图１23．空串的长度为(）。A．０B．１C.２24．元素2，4，6,8按顺序依次进栈，则该栈的不也许输出序列是（)（进栈出栈可以交替进行)。A.８，6，4,2B．2,4，6，8Ｃ．4,2,8，6Ｄ．８,6,２，425.串函数ＳtrCmp(“abA”,”aba”)的值为()。A．1B.0C．“ａbAaba”D２６．排序方法中,从未排序序列中挑选元素，并将其依次放入已排序序列（初始为空）的一端的方法,称为（）排序。Ａ.归并Ｂ.插入C.选择D．快速２7．设有一个10阶的对称矩阵Ａ，采用压缩存储方式将其下三角部分以行序为主序存储到一维数组b中。(矩阵A的第一个元素为a1,1,数组ｂ的下标从1开始),则矩阵元素a5,３相应一维数组b的数组元素是（)。A．ｂ[１8]Ｂ．b[8]Ｃ．b[13]Ｄ.b[1０]2８.一棵哈夫曼树总共有２3个结点,该树共有(）个叶结点（终端结点)A．10B.13C.1129．已知如图２所示的一个图,若从顶点a出发，按深度优先搜索法进行遍历，则也许得到的一种顶点序列为（)。A.ａbecｄfB.ａcfebdC.aeｂcfdD．aeｄfcbbbdfeca图230．队列的插入操作在()进行。A．队头B.队尾C.队头或队尾Ｄ.在任意指定位置二、填空题１.通常数据的逻辑结构涉及集合、线性、____、__＿＿四种类型。2．一棵二叉树没有单分支结点，有６个叶结点，则该树总共有_＿___＿__个结点。3.通常可以把某城市中各公交站点间的线路图抽象成______＿＿结构。４.设一棵完全二叉树，其最高层上最右边的叶结点的编号为奇数,该叶节点的双亲结点的编号为１0,该完全二叉树一共有＿＿______个结点。5.设有一个单向链表,结点的指针域为ｎext，头指针为ｈead，p指向尾结点，为了使该单向链表改为单向循环链表,可用语句___＿____。6.按照二叉树的递归定义,对二叉树遍历的常用算法有__＿_、____、___＿三种。7.循环队列的队头指针为ｆ,队尾指针为r,当＿______＿时表白队列已空。8.数据结构中的数据元素存在一对多的关系称为__＿___＿_结构。９.设有一个链栈,栈顶指针为hs,现有一个s所指向的结点要入栈,则可执行操作___＿____和hs=ｓ;10.把数据存储到计算机中,并具体体现数据之间的逻辑结构称为___＿____结构。1１.在一个链队中，f和r分别为队头和队尾指针,队结点的指针域为next,则插入一个ｓ所指结点的操作为________；r=s；12.结构中的数据元素存在一对一的关系称为_＿__＿_＿_结构。13.串的两种最基本的存储方式分别是＿______和__＿＿＿＿＿＿。14.如图3所示的二叉树，其后序遍历序列为。eefgibachd图31５.一棵二叉树中顺序编号为ｉ的结点，若它存在左、右孩子，则左、右孩子编号分别为＿__＿＿__＿、＿_____＿_。１6.n个元素进行冒泡法排序,通常需要进行____＿___趟冒泡。1７，两个串相等的充足必要条件是。18.二叉树为二叉排序的充足必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是______＿___的。(回答对的或不对的）１9．一棵二叉树叶结点(终端结点)数为5,单分支结点数为2,该树共有＿_____个结点。2０．图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是______的。（回答对的或不对的)21.根据搜索方法的不同,图的遍历有_＿__、__＿＿两种方法。2２.根据搜索方法的不同,图的遍历有_＿__、____两种方法2３．一个有序表{３,4,10,１4，34,４3，46，64,75,78,90，96，130}用折半查找法查找值为90的结点，经_＿_____＿次比较后查找成功。２4.按某关键字对记录序列排序，若关键字的记录在排序前和排序后仍保持它们的前后关系,则排序算法是稳定的,否则是不稳定的。三、综合题１.(1）已知某二叉树的后序遍历序列是debｃa，中序遍历序列是dbeaｃ，试画出该二叉树(2)若上述二叉树的各个结点的字符分别代表不同的整数(其中没有相等的),并恰好使该树成为一棵二叉排序树，试给出ａ、b、c、d、e的大小关系。（３)给出该树的前序遍历序列2．（1)运用筛选过程把序列{42，82,６7，102,16，３２,5７，52}建成堆（小根堆)，画出该堆（不规定中间过程)。(2）写出对上述堆相应的完全二叉树进行中序遍历得到的序列。３.（1）一组记录的关键字序列为{4５,40，65,４３，3５，9５}，写出运用快速排序的方法,以第一个记录为基准得到的一趟划分的结果（规定给出一趟划分中每次扫描和互换的结果)（2)对序列{４5，40,65，4３,３5,9５}运用直接插入排序,写出逐次插入过程（从第一个元素一直到第六个元素)。4.设查找表为(１6，15,20,５3,64,7）,（１）用冒泡法对该表进行排序(规定升序排列）,规定写出每一趟的排序过程。(2)在排序后的有序表的基础上,画出对其进行折半查找所相应的鉴定树.(规定以数据元素作为树结点)（3)求在等概率条件下,对上述有序表成功查找的平均查找长度.5．(1)设有查找表{5，14,2,6,１8,7,４,１6，3},依次取表中数据,构造一棵二叉排序树．（2)说明如何通过序列的二叉排序树得到相应序列的排序结果。6．(１）设有一个整数序列｛50，38，16，82，１10,1３,64},依次取出序列中的数,构造一棵二叉排序树（2)运用上述二叉排序树,为了查找11０,经多少次元素间的比较能成功查到，为了查找1５，经多少次元素间的比较可知道查找失败四、程序填空题1.以下函数在a［0]到a[n-1]中，用折半查找算法查找关键字等于ｋ的记录，查找成功返回该记录的下标,失败时返回-1，完毕程序中的空格typedｅfstruct{intｋeｙ;……}ＮOＤＥ;intBinarｙ_Seａrch(ＮODEa[],intn,iｎtｋ){ｉntlow，mid,high;ｌow=０;ｈigh=n-１;ｗhilｅ（___(１）_＿___){mid＝(loｗ＋hiｇh)/2;iｆ（a[mid].key＝＝ｋ）ｒeturn＿_（２)____＿_; ｅlsｅｉf(___（3)_____)low=ｍid+１; elsｅ__(４)______;ﻩ}__＿（5)__＿__;ﻩ}2．以下函数为链队列的入队操作，x为要入队的结点的数据域的值,front、rear分别是链队列的队头、队尾指针ｓtｒuctnodｅ{ＥlemTyｐｅdatａ;stｒucｔnode*next;};structｎｏde*froｎt，*ｒｅar；vｏｉdInＱｕeｕe(EleｍTｙpeｘ){stｒuctnｏde*p;ｐ=(ｓｔruｃtnodｅ*）＿＿_（１)__＿＿_;p->daｔａ=ｘ；p->nexｔ＝NUＬL;__＿(2)_＿__＿;rｅaｒ＝_＿＿(3）___＿_；}３．以下函数为链栈的进栈操作,x是要进栈的结点的数据域，toｐ为栈顶指针strｕctnode｛ElemTｙpｅdaｔa;structnode*neｘt;};structnode*tｏp;voiｄPush(ElｅmTypex){sｔｒuctｎoｄe*p；ｐ=(stｒuｃtnode＊)ｍalｌoc（___（1)_____)；p->ｄaｔa=ｘ;_＿_(2)_____;_＿＿__(3)__＿;}4．以下函数在heａd为头指针的具有头结点的单向链表中删除第i个结点，ｓtruｃtnoｄｅ{ｉｎtｄata;ｓｔrｕｃｔｎｏdｅ*next;};typedeｆstructnodｅNODEintdeleｔe（ＮOＤE＊head，inti){NODＥ*p,*q;iｎtｊ;q=heａd;j＝０；whｉｌe((q!＝NULL）&&(__＿(１)__＿__)）｛___(2)＿__＿_;j+＋；}if(q==ＮＵLL）reｔurｎ（0）;ｐ=__＿(3)__＿__;___(4)＿__＿_＝p－>ｎｅxｔ;freｅ(＿_＿(５)__＿_＿);rｅtｕｒn（1);}答案一、单项选择题1．D２．C3．Ｃ4.A５.C6．D7.B8.C9．A１0．C11.C1２．Ａ1３.C14.Ｃ15.Ａ16.A１7.Ａ18.Ｃ19.B20.Ｂ21.Ｄ22.Ｂ２3.Ａ24.Ｄ25.D２６．C２7.C28.D２9．D3０．Ｂ二、填空题1．树形;图状2.11３．图状4．215.ｐ->nexｔ=head；6.先序;中序;后序7.r＝f8.树形9.ｓ－>ｎexｔ=hs;10．物理（存储）１1.r->ｎexｔ＝s12.线性1３．顺序存储链式存储14．gdｂeihfcａ１５．2ｉ和２i+1１6．n-１17．串长度相等且相应位置的字符相等１8.不对的19．1１20.对的21.深度优先搜索遍历广度优先搜索遍历22．深度优先搜索遍历广度优先搜索遍历2３．４24．相等三、综合应用题abced1abced图4(２)d<b＜e＜ａ<c(３）abdeｃ2．（1）1616423252576782102图5（2）１02，52,42，82，16，６７,32，573．(1)4５406543３59５3540654３359535406５43６595３５40434３6595３5404３４565９５(2）40４5６543３5954０４3456535953５404３４５65９54．（1)原序列1615205364７1516205３76４15162０75３6４15１67２０5364１57１620536471５16２05３6４715715206416535图６(3)平均查找长度=(1*1＋２*2+３*3）/6=14/65.（1)22461673185145图７（2)中序遍历50503882131106416图８（2)三次；四次四、程序填空题１.(1)lｏw<=hiｇh(2）ｍid（3)a[miｄ]．key<k;(4)high=mid-1（５)retｕrn－1;2．(１）ｍalloc(siｚeoｆ(strｕctnoｄe）)(2)rear－>nexｔ=p(3）p3.（1）sizeof（sｔrｕctnode)(２)ｐ->ｎext＝top（3）ｔop=p4.(1)j<i－1（2)q=ｑ->nｅxt(3）q->next(4）q－>ｎｅｘｔ(5）p期末综合练习二一、单项选择题1．同一种逻辑结构()。A.只能有唯一的存储结构Ｂ.可以有不同的存储结构Ｃ．只能表达某一种数据元素之间的关系D.以上三种说法均不对的2．在C语言中，顺序存储长度为３的字符串，需要占用（)个字节。Ａ.4B.3C3．链表所具有的特点是（)。Ａ.可以随机访问任一结点B.占用连续的存储空间C.插入删除元素的操作不需要移动元素结点Ｄ．可以通过下标对链表进行直接访问4．串函数StrＣaｔ（a，b)的功能是进行串（)。A．比较B．复制C．赋值D.连接5.数据的物理结构（）。A.与数据的逻辑结构无关B.仅仅涉及数据元素的表达C．只涉及数据元素间关系的表达Ｄ.涉及数据元素的表达和关系的表达6.一棵有n个结点采用链式存储的二叉树中，共有（)个指针域为空。A．n＋1B．nＣ．n－1D.n-27.线性结构中数据元素的位置之间存在()的关系。A．一对一B．一对多C.多对多Ｄ．每一个元素都有一个直接前驱和一个直接后继8．设一棵哈夫曼树共有ｎ个非叶结点，则该树有(）个叶结点。Ａ．ｎB.n+1C9.以下表中可以随机访问的是（)。A．单向链表B.双向链表Ｃ.单向循环链表D．顺序表１0.从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值，则执行（)。A.x＝top-＞data;toｐ=topｎｅxt;B．x＝top->datａ;C．ｔop=top->neｘt;x＝toｐ->ｄaｔa;D．ｔop=tｏp－>ｎext;x=dａta;1１．算法的时间复杂度与（）有关。A.所使用的计算机B.与计算机的操作系统C．与算法自身D.与数据结构１２.一棵完全二叉树共有5层,且第5层上有六个结点，该树共有（）个结点。A．３0Ｂ．20C13.设有一个长度为ｎ的顺序表，要删除第ｉ个元素需移动元素的个数为()。A.ｎ-i＋１B．ｎ-ｉC．n-i-1Ｄ.i14．在一个无向图中，所有顶点的度数之和等于边数的(）倍。A.3B.2.5C１５.在一个单链表中，ｐ、q分别指向表中两个相邻的结点，且q所指结点是p所指结点的直接后继，现要删除ｑ所指结点，可用的语句是()。A．p＝q－>nextＢ．p->nexｔ=qＣ．ｐ->ｎext=ｑnｅｘtＤ.q->ｎexｔ＝NULL１6.已知如图1所示的一个图,若从顶点V１出发,按深度优先搜索法进行遍历,则也许得到的一种顶点序列为（)。A．Ｖ１Ｖ2V4V８V5V3V6V7B．V1Ｖ2V4V５Ｖ８V３Ｖ6Ｖ７C.V1Ｖ2V4V8V３Ｖ5V6V7D．V1V3Ｖ6V7V2V4V5V８V6V6V7V1V2V3V8V4V5图１17．从一个栈顶指针为top的链栈中删除一个结点时，用变量x保存被删结点的值,则执行(）。A.x=top-＞ｄatａ;ｔop=ｔｏp－＞ｎext；B.ｘ=tｏp->datａ；C．tｏp=ｔop－＞next;ｘ＝top－>datａ；Ｄ．top=top-＞ｎext;x=ｄata；18．已知如图2所示的一个图，若从顶点a出发，按广度优先搜索法进行遍历，则也许得到的一种顶点序列为（)。A.ａｂcedfB．abcefdC.aebｃｆdD.acfdｅbbdbdfeca图219.在一个链队中，假设ｆ和ｒ分别为队头和队尾指针,则删除一个结点的运算为(）。A．r=ｆ－>nｅxt;B.ｒ＝r->next;C.f=ｆ->next;D.f=r－>ｎeｘt;20.对二叉排序树进行（)遍历，可以使遍历所得到的序列是有序序列。Ａ．按层次B.后序C.中序D．前序21.一个栈的进栈序列是a,ｂ，c，ｄ,e，则栈的不也许输出序列是()(进栈出栈可以交替进行）。A.dceabＢ.edcbaC.decbaＤ.abｃｄe22.在有序表｛2，4，7,14，34，43,47,64,75,８0，90,9７,１20}中,用折半查找法查找值8０时，经（）次比较后查找成功。A．4B．2C23.有一个长度为10的有序表，按折半查找对该表进行查找,在等概率情况下查找成功的平均比较次数为()。A．26/1０B.29/102４．有一个长度为9的有序表,按折半查找对该表进行查找,在等概率情况下查找成功的平均比较次数为（）。Ａ．25／10B．25/9C２5.排序算法中，从未排序序列中依次取出元素与已排序序列（初始为空)中的元素进行比较（规定比较次数尽量少),然后将其放入已排序序列的对的位置的方法是（)。Ａ．冒泡B.直接插入C.折半插入D．选择排序2６.排序算法中,从未排序序列中依次取出元素与已排序序列（初始为空)中的元素进行比较（规定比较次数尽量少），然后将其放入已排序序列的对的位置的方法是()。A.冒泡B.直接插入C．折半插入D．选择排序27．设有一个10阶的对称矩阵Ａ,采用压缩存储的方式，将其下三角部分以行序为主存储到一维数组B中（数组下标从１开始),则矩阵中元素Ａ8,5在一维数组B中的下标是(）。A.3３B.3２C．852８.一组记录的关键字序列为（4６,79，56,38，４0,８４),运用快速排序,以第一个关键字为分割元素，通过一次划分后结果为()。A.４0,38,46，７9，5６,84Ｂ．4０,３8，46,５6,7９，84C.40，３8，４６，８４，５６,79D．3８，40,46，56,７9，8429．在一个无向图中,所有顶点的度数之和等于边数的（）倍。Ａ．３B．2.５C3０.排序方法中，从尚未排序序列中挑选元素,并将其依次放入已排序序列（初始为空）的一端的方法,称为（）排序。A．归并B．插入Ｃ.快速D.选择二、填空题1．栈和队列的操作特点分别是＿___＿__和＿_______。2．在二叉树的链式存储结构中，通常每个结点中设立三个域,它们是______＿、、右指针。3.结构中的数据元素存在多对多的关系称为＿______＿结构。４．一棵二叉树中顺序编号为i的结点,若它存在左、右孩子，则左、右孩子编号分别为＿_＿＿__、____＿___。5．根据数据元素间关系的不同特性,通常可分为集合、线性、、四类基本结构。6.串的两种最基本的存储方式是＿＿__＿___和＿_______。7．规定在n个数据元素中找其中值最大的元素，设基本操作为元素间的比较。则比较的次数和算法的时间复杂度分别为＿＿__＿＿__和__＿＿＿＿__。8．一棵有2n-1个结点的二叉树，其每一个非叶结点的度数都为２，则该树共有_______个叶结点。9.在一个单向链表中p所指结点之后插入一个ｓ所指向的结点时，应执行＿＿＿＿____和p-＞next=s;的操作。１0．对于一棵具有n个结点的二叉树，其相应的链式存储结构中共有____＿___个指针域为空。1１．在二叉树的链式存储结构中，通常每个结点中设立三个域，它们是值域、。1２.＿＿___＿__遍历二叉排序树可得到一个有序序列。1３．一棵二叉树中顺序编号为ｉ的结点，若它存在左、右孩子，则左、右孩子编号分别为________、_＿_____＿。１4．如图３所示的二叉树，其后序遍历序列为。eefgibachd图315．向一个栈顶指针为h的链栈中插入一个s所指结点时，可执行s-＞next＝h;和____＿___。16.如图4所示的二叉树，其先序遍历序列为_________。ggfabdec图4１7．在一个链队中,设f和r分别为队头和队尾指针,则插入s所指结点的操作为_＿_＿____和r=ｓ;(结点的指针域为ｎext)18.图的深度优先搜索和广度优先搜索序列不一定是唯一的。此断言是＿＿__＿_的。(回答对的或不对的）1９．设有一棵深度为4的完全二叉树，第四层上有5个结点，该树共有＿_______＿个结点。(根所在结点为第１层)２0．二叉树为二叉排序的充足必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法是______＿＿__的。（回答对的或不对的)21.对稀疏矩阵进行压缩存储，矩阵中每个非零元素相应的三元组涉及该元素的＿_＿__＿_、_______和___＿__＿三项信息。2２.对记录序列排序是指按记录的某个关键字排序，记录序列按＿＿_＿____＿排序结果是唯一的。23．在对一组记录(55,39，97,2２，１6,73，6５,47,8８）进行直接插入排序时，当把第7个记录65插入到有序表时，为寻找插入位置需比较_______＿＿次。24．按某关键字对记录序列排序,若在排序前和排序后仍保持它们的前后关系，则排序算法是稳定的,否则是不稳定的。三、综合题1.（1)以2，3,４,7,８,9作为叶结点的权，构造一棵哈夫曼树(规定每个结点的左子树根结点的权小于等于右子树根结点的权)，给出相应权重值叶结点的哈夫曼编码。(2)一棵哈夫曼树有ｎ个叶结点,它一共有多少个结点?简述理由？2．设查找表为（16,１5，20,53,6４,7）,(1)用冒泡法对该表进行排序(规定升序排列),写出每一趟的排序过程，通常对n个元素进行冒泡排序要进行多少趟冒泡？第j趟要进行多少次元素间的比较？(2)在排序后的有序表的基础上，画出对其进行折半查找所相应的鉴定树.（规定以数据元素作为树结点)3.一组记录的关键字序列为(46，79，56，3８，４0,8４）（1）运用快速排序的方法,给出以第一个记录为基准得到的一次划分结果(给出逐次互换元素的过程，规定以升序排列)（２)对上述序列用堆排序的方法建立大根堆,规定以二叉树逐次描述建堆过程。4.（1)设有查找表｛５,1４,2,6,18,7，４,16,３｝，依次取表中数据,构造一棵二叉排序树。(2）说明如何由序列的二叉排序树得到相应序列的排序结果，对上述二叉排序给出中序遍历的结果。5.设查找表为（５0，６0,7５,85,96,98,１０５,110,120，130）(1)说出进行折半查找成功查找到元素１20需要进行多少次元素间的比较?(2)为了折半查找元素95,通过多少次元素间的比较才干拟定不能查到?（３）画出对上述有序表进行折半查找所相应的鉴定树(规定以数据元素作为树结点)６.(1）对给定权值２，1,3,３，4，5，构造哈夫曼树。(2)同样用上述权值构造另一棵哈夫曼树,使两棵哈夫曼树有不同的高度，并分别求两棵树的带权途径长度。四、程序填空题1.以下是用尾插法建立带头结点且有n个结点的单向链表的程序，结点中的数据域从前向后依次为1,2,3,……,ｎ,完毕程序中空格部分。NODE*create（n)｛ＮＯＤＥ*heaｄ,＊p,*q;inti；p＝（ＮODE*)ｍalloｃ(sｉzeof（NＯDE));heａd=（1)；（2)；ｐnexｔ=NULＬ;/＊建立头结点*／for(i=1;i<＝n；i++)｛p=（3);pdata＝ｉ；pnext=NULL;qneｘt＝(4);（5）;}retuｒn(head）;}2．设线性表为(6，１0，16,4)，以下程序用说明结构变量的方法建立单向链表,并输出链表中各结点中的数据。#deｆiｎeNＵＬL0voｉdmain(){ＮODEa,b，c,d,*head,*p；a.dａtａ＝６;ｂ．data=10；c.ｄatａ=16;ｄ.ｄata=4;/*ｄ是尾结点＊/ｈｅad=(1）；a.next=&b;b.next=&ｃ；c．next=&d；(2）;/*以上结束建表过程＊/ｐ=heaｄ；／*ｐ为工作指针,准备输出链表＊／do{printf(“%d\n”，(3)）;（４）；}while((5))；｝3．以下程序是中序遍历二叉树的递归算法的程序,完毕程序中空格部分（树结构中左、右指针域分别为lｅft和right，数据域daｔa为字符型，BT指向根结点)。voidIｎｏrdｅr(strucｔBTreeNｏde＊BT)｛if(ＢT!=NＵLL)｛(１）;(2）;（３);｝}4．以下程序是后序遍历二叉树的递归算法的程序，完毕程序中空格部分(树结构中,左、右指针域分别为lefｔ和riｇht，数据域daｔa为字符型，ＢＴ指向根结点)。ｖoidＰostordeｒ(struｃｔBTreeNode*ＢT){if（BT!=ＮUＬL){(１);（2）;（３)