华东交大数据结构自测卷及答案

PAGEPAGE57第一章绪论一、填空题1.算法的计算量的大小称为计算的（B）。A．效率B.复杂性C.现实实性D.难度2.算法的时时间复杂度取取决于（CC）A．问题的规模模B.待待处理数据的的初态C..A和B3.计算机算法法指的是（CC），它必须须具备（B）这三个特性性。(1)A．计计算方法B..排序方法法CC.解决问问题的步骤序序列D.调度方法(2)A．可可执行性、可可移植性、可可扩充性B.可执行性、确确定性、有穷穷性C.确定性、有有穷性、稳定定性D.易易读性、稳定定性、安全性性4．从逻辑上可可以把数据结结构分为（C）两两大类。A．动态结构、静静态结构B．顺序结结构、链式结结构C．线性结构、非非线性结构DD．初等结构构、构造型结结构5．以下与数据据的存储结构构无关的术语语是（D）。A．循环队列B.链链表CC.哈希表表D.栈栈6．以下数据结结构中，哪一一个不是线性性结构（B）？？A．广义表B.二叉树CC.稀疏矩矩阵D.串串7．以下那一个个术语与数据据的存储结构构无关？（A）A．栈BB.哈希表表C.线线索树D..双向链链表8．在下面的程程序段中，对对x的赋值语语句的频度为为（C）FORi:==1TOOnDOFORRj:=11TOnDDOxx:=x+11;A．O(2nn)B．．O(n)C．O((n2)D．O(llog2n)9．程序段FFORii:=n-11DOWWNTO1DOOFORjj:=1TTOiDDOIFFA[j]>A[j+1]THENNA[j]与A[j+1]对换；其中n为正整整数，则最后后一行的语句句频度在最坏坏情况下是（D）A.O（n）B..O(nllogn)CC.O(nn3)D.OO(n2)10．以下哪个个数据结构不不是多型数据据类型（D）A．栈BB．广义表C．有向向图D．．字符串11．以下数据据结构中，（A）是是非线性数据据结构A．树BB．字符串C．队D．栈12.下列数数据中，（C）是非线性数据结构。A．栈B..队列C..完全二二叉树D.堆堆13．连续存储储设计时，存存储单元的地地址（AA）。A．一定连续B．一定定不连续C．不一定定连续DD．部分连续续，部分不连连续14．以下属于于逻辑结构的的是（CC）。A．顺序表B.哈希希表CC.有序表DD.单链链表二、判断题1.数据元素素是数据的最最小单位。((F)2.记录是数数据处理的最最小单位。(T)3.数据的逻逻辑结构是指指数据的各数数据项之间的的逻辑关系；；(F)4．算法的优劣劣与算法描述述语言无关，但但与所用计算算机有关。((F)5．健壮的算法法不会因非法法的输入数据据而出现莫名名其妙的状态态。(T)6．算法可以用用不同的语言言描述，如果果用C语言言或PASCCAL语言等等高级语言来来描述，则算算法实际上就就是程序了。(T)7．程序一定是是算法。(T))8．数据的物理理结构是指数数据在计算机机内的实际存存储形式。((T))9.数据结构构的抽象操作作的定义与具具体实现有关关。(F)10.在顺序序存储结构中中，有时也存存储数据结构构中元素之间间的关系。((F)11.顺序存存储方式的优优点是存储密密度大，且插插入、删除运运算效率高。((F)12.数据结结构的基本操操作的设置的的最重要的准准则是，实现现应用程序与与存储结构的的独立。(T))13.数据的的逻辑结构说说明数据元素素之间的顺序序关系,它依依赖于计算机机的储存结构构.(FF)三、填空1．数据的物理理结构包括数据元素素的表示示和数数据关系的的表示。2.对于给定定的n个元素素,可以构造造出的逻辑结结构有集集合，线性，树，__图（网网）_四种。3．数据的逻辑辑结构是指数据元素素之间的逻辑辑关系。4．一个数据结结构在计算机机中表示称为存存储结构。5．抽象数据类类型的定义仅仅取决于它的的一组__逻逻辑特性_，而而与_其在计计算机内部如如何表示和实实现_无关，即即不论其内部部结构如何变变化，只要它它的_数学特特性_不变，都都不影响其外外部使用。6．数据结构中中评价算法的的两个重要指指标是时间复复杂度和空间间复杂度7.数据结构构是研讨数据据的_逻辑结结构_和_物理结结构_，以及及它们之间的的相互关系，并并对与这种结结构定义相应应的_操作_，设计计出相应的算算法_。8．一个算法法具有5个特特性:有穷穷性、确定性、可行性，有零个或或多个输入、有有一个或多个个输出。9．已知如下程程序段for(i=nn;i>=11;i--){语句句1}{x=x+1；{语句2}for(j=nn;j>i;;j--){语句句3}y=y+1;;{{语句4}}；语句1执行的频频度为n++1；语句句2执行的频频度为n；语句3执执行的频度为为n（n+11）/2；语句句4执行的频频度为(nn-1)n//2。10．在下面的的程序段中，对对ｘ的赋值语语句的频度为为(n3+3n2+2n)//6______（表示为为n的函数）for((i=1;ii<=n;ii++)for(jj=1;j<<=i;j+++)foor(k=11;k<=jj;k++))ｘ：＝ｘ＋deelta；11.下面程序序段中带下划划线的语句的的执行次数的的数量级是：：log2ni=1;whiile(i<<n)i=ii*2;12.下面程程序段中带下下划线的语句句的执行次数数的数量级是是(nloog2n))。i=1;while(ii<n){ffor(j==1;j<==n;j+++)x=x++1;i=ii*2}13.下面程程序段中带有有下划线的语语句的执行次次数的数量级级是(logg2n)i=n*nwhilee(i!=11)i=i//2;14.计算机机执行下面的的语句时，语语句s的执行行次数为___(n+33)(n-22)/2______。for(ii=l；i<<n-l；ii++)forr(j=n;;j>=i;;j--)s;15.下面程程序段的时间间复杂度为___n1/22_______。(n>>1)sum==1；for(i=0;;sum<nn;i++))sum++=i;四、应用题1、有如下几种种用二元组表表示的数据结结构，画出它它们分别对应应的逻辑图表表示形式，并并指出它们分分别属于何种种结构。（注注意：<>表表示有方向，（）表表示无方向）（1）、A=（KK，R），其中：K=={a,b,,c,d,ee,,f,gg,h}RR={r}r={<a,,b>,<bb,c>,<<c,d>,,<d,e>>,<e,ff>,<f,,g>,<gg.h>}（2）、B=（KK，R），其其中：K={{a,b,cc,d,e,,f,g,hh}R=={r}rr={<d,,b>，<dd,g>,<<d,a>,,<b,c>>,<g,ee>,<g,,h>,<ee.f>}（3）、C=((K,R),,其中:K=={1,2,,3,4,55,6},RR={r}r=={(1,22),(2,,3),(22,4),((3,4),,(3,5)),(3,66),(4,,5),(44,6)}线性表、栈和队队列测试题姓名班级学号选择题（共255分）（B）1、下面关于于线性表的叙叙述中，错误误的是哪一个个？A．线性表采用用顺序存储，必必须占用一片片连续的存储储单元。B．线性表采用用顺序存储，便便于进行插入入和删除操作作。C．线性表采用用链接存储，不不必占用一片片连续的存储储单元。D．线性表采用用链接存储，便便于插入和删删除操作。（A）2、若某线性表表最常用的操操作是存取任任一指定序号号的元素和在在最后进行插插入和删除运运算，则利用用（

）存储方式式最节省时间间。A．顺序表

B．双双链表

C．带头结点点的双循环链链表

DD．单循环链链表（C）3、若长度为为n的线性表采采用顺序存储储结构，在其其第i个位置插入入一个新元素素的算法的时时间复杂度为为（

）(1<=ii<=n+11)。A.O(0))

B.OO(1)

C.O(n)

DD.O(nn2)（B）4、在单链表表指针为p的结点之后后插入指针为为s的结点，正正确的操作是是：A．p->neext=s;;s->neext=p-->nextt;

B．．s->nnext=pp->nexxt;p->>next==s;C．p->neext=s;;p->neext=s-->nextt;

D．．p->nnext=ss->nexxt;p->>next==s;（B）5、对于一个个头指针为hhead的带带头结点的单单链表，判定定该表为空表表的条件是（

）head==NNULL

BB．head-->nextt==NULLL

C．head-->nextt==heaad

DD．head-->NULLL（B）6.栈中中元素的进出出原则是A．先进进先出B.后进先出出C栈空则进进D栈满则出出（C）7.若已已知一个栈的的入栈序列是是1，2，3，…，n，其输出序序列为p1，p2，p3，…，pn，若p1=nn，则pi为Ａ．iＢ．．n=iＣＣ．n-i++1Ｄ．．不确定（B）8.判定定一个栈STT（最多元素素为m0）为空的的条件是Ａ．STT->topp<>0Ｂ．ST->>top=00Ｃ．．ST->ttop<>mm0Ｄ．ST->>top=mm0（A）9.判定定一个队列QQU（最多元元素为m0）为满队队列的条件是是Ａ．QU->>rear－QU->>frontt==m0ＢＢ．QU->>rear－QU->>frontt－1==m0Ｃ．QUU->froont==QU-->rearrＤ．QU->>frontt==QU->rrear+11（D）10．数组ＱＱ［ｎ］用来来表示一个循循环队列，ｆｆ为当前队列列头元素的前前一位置，ｒｒ为队尾元素素的位置，假假定队列中元元素的个数小小于ｎ，计算算队列中元素素的公式为（Ａ）r－f;;（Ｂ）（n＋f－r）%n;（Ｃ）n＋r－f;（Ｄ）（n＋r－f）%n11.设有有4个数据元素素a1、a2、a3和a4，对他们们分别进行栈栈操作或队操操作。在进栈栈或进队操作作时，按a11、a2、a3、a4次序每次次进入一个元元素。假设栈栈或队的初始始状态都是空空。现要进行的栈操操作是进栈两两次，出栈一一次，再进栈栈两次，出栈栈一次；这时时，第一次出出栈得到的元元素是②，第二次出出栈得到的元元素是④；类似似地，考虑对对这四个数据据元素进行的的队操作是进进队两次，出出队一次，再再进队两次，出出队一次；这这时，第一次次出队得到的的元素是①，第二二次出队得到到的元素是②。经操操作后，最后后在栈中或队队中的元素还还有②个。供选择的答案：：A～D：①a1②a2③a3④a4E：①1②2③3④0答：A、B、CC、D、E分别为、、、、12.栈是是一种线性表表，它的特点点是A。设用用一维数组AA[1,…,,n]来表示示一个栈，AA[n]为栈栈底，用整型型变量T指示当前栈栈顶位置，AA[T]为栈栈顶元素。往往栈中推入（PUSH）一个新元素时，变量T的值B；从栈中弹出（POP）一个元素时，变量T的值C。设栈空时，有输入序列a，b，c，经过PUSH，POP，PUSH，PUSH，POP操作后，从栈中弹出的元素的序列是D，变量T的值是E。供选择的答案：：A：①先进先出②后进先出 ③进优于出 ④出优于进⑤随机进出B，C： ①加1②减1③③不变④清0⑤加2⑥⑥减2D：①①a,b②b,c ③c,a ④b,a⑤c,b⑥a,cE：①①n+1②n+2③n ④n-1⑤n-2答：A、B、CC、D、E分别为②、②、①、⑥、④13.在做做进栈运算时时，应先判别别栈是否A；；在做退栈运运算时，应先先判别栈是否否B。当栈中中元素为n个，做进栈栈运算时发生生上溢，则说说明该栈的最最大容量为C。为了增加内存空空间的利用率率和减少溢出出的可能性，由由两个栈共享享一片连续的的内存空间时时，应将两栈栈的D分别设设在这片内存存空间的两端端，这样，只只有当EE时，才才产生上溢。供选择的答案：：A，B：①空②满③上溢④下溢C： ①①n-1②②n③n+1④n/2D：①长度②深度③栈顶④栈底E：①两个栈的的栈顶同时到到达栈空间的的中心点②其中一一个栈的栈顶顶到达栈空间间的中心点③两个栈的栈栈顶在栈空间间的某一位置置相遇④两个栈均不空空，且一个栈栈的栈顶到达达另一个栈的的栈底答：A、B、CC、D、E分别为②、①、②、④、③判断题（共100分）（F）1..线性表的的每个结点只只能是一个简简单类型，而而链表的每个个结点可以是是一个复杂类类型。（F）2..在表结构构中最常用的的是线性表，栈栈和队列不太太常用。（T）3..栈是一种种对所有插入入、删除操作作限于在表的的一端进行的的线性表，是是一种后进先先出型结构。（T）4..对于不同同的使用者，一一个表结构既既可以是栈，也也可以是队列列，也可以是是线性表。（F）5..栈和链表表是两种不同同的数据结构构。（F）6..栈和队列列是一种非线线性数据结构构。（T）7..栈和队列列的存储方式式既可是顺序序方式，也可可是链接方式式。（T）8..两个栈共共享一片连续续内存空间时时，为提高内内存利用率，减减少溢出机会会，应把两个个栈的栈底分分别设在这片片内存空间的的两端。（F）9..队是一种种插入与删除除操作分别在在表的两端进进行的线性表表，是一种先先进后出型结结构。（F）100.一个栈栈的输入序列列是123445，则栈的的输出序列不不可能是122345。填空题（共200分）1.线性表表、栈和队列列都是线性结构，可可以在线性表表的任意位置插插入和删除元元素；对于栈栈只能在栈顶插入和和删除元素；；对于队列只只能在队尾插入和和队头删除元素。2.栈是一种种特殊的线性性表，允许插插入和删除运运算的一端称称为栈顶。不允允许插入和删删除运算的一一端称为栈底。3.队列列是被限定为为只能在表的的一端进行插插入运算，在在表的另一端端进行删除运运算的线性表表。4.在一个循循环队列中，队队首指针指向向队首元素的的当前前位置。5.在具有nn个单元的循循环队列中，队队满时共有nn-1个元元素。6.向栈中压压入元素的操操作是先插入入数据，后移动指指针。7.从循环队队列中删除一一个元素时，其其操作是先读取元素素，后后移动指针针。8.带表头头结点的空循循环双向链表表的长度等于于0。9．表达式233+((122*3-2))/4+344*5/7))+108//9的后缀表表达式是__231223*2-4/345**7/++1089/+______10．已知L是是无表头结点点的单链表，且且P结点既不是是首元素结点点，也不是尾尾元素结点。按按要求从下列列语句中选择择合适的语句句序列。a.在P结点点后插入S结点的语句句序列是：

(4)(1)

。b.在P结点点前插入S结点的语句句序列是：

7

118441

。c.在表首插插入S结点的语句句序列是：

512

。d.在表尾插插入S结点的语句句序列是：

9166

。供选择的语句有有：（1）P->nnext=SS;（2）P->neext=PP->nexxt->neext;（3）P->neext=SS->nexxt;（4）S->nnext=P->neext;（5）S->neext=LL;（6）S->neext=NNULL;（7）Q=P;;（8）whille(P->>next!!=Q)PP=P->nnext;（9）whilee(P->nnext!==NULL))P=P-->nextt;（10）P=Q;（11）P=L;;（12）L=S;;（13）L=P;;简答题(共155分)说明线性表、栈栈与队的异同同点。顺序队的“假溢溢出”是怎样产生生的？如何知知道循环队列列是空还是满满？设循环队列的容容量为40（序号从从0到39），现经经过一系列的的入队和出队队运算后，有有①frontt=11，rear==19;②fronnt=19，rear==11；问在在这两种情况况下，循环队队列中各有元元素多少个？？算法设计（共330分）写一算法，从顺顺序表中删除除自第i个元素开始始的k个元素。StatusDelette_k(SSqlisttL,innti,iintk)){if(ii<0||ii>L.leength|||i+k>>L.lenngth)rreturnnerroor;for((intjj=i+k;;j<L.llengthh;j++)){L.eleem[j-kk]=L.eelem[jj];}L.leength--=k;rreturnnOK;}试写一个算法，判判别读入的一一个以‘@’’为结束符的的字符序列是是否是“回文”。（正读和反读读都相同的字字符序列为“回文”，例如，‘aabba’和和‘abcbba’是回文文，‘abccde’和和‘ababbab’则不不是回文。）StattusHuuiWen((chars[]){ inti==0; SqStacckS; InitSttack(SS); while((s[i]!!='@')) { Push((S,s[ii]); cout<<<"pussh"<<ss[i]; i++; } i=0; while((s[i]!!='@')) { chare; Pop(SS,e); cout<<<e<<""*"<<ss[i]; if(e!!=s[i]])breaak; i++; } if(s[ii]=='@@')retturn11;//返返回结果1表表示是回文，00表示不是回回文 elserreturnn0;}假设有一个循环环链表的长度度大于1，且表中既既无头结点也也无头指针。已已知s为指向链表表某个结点的的指针，试编编写算法在链链表中删除指指针s所指结点的的前趋结点。StatusDelette(LinnkListts){p=s;while(pp->nexxt->neext!=ss)///查找s的前前一个结点的的前一个结点点；p=p-->nextt;q=p->neext;p->nextt=s;deleteq;returnOK;}第6章树和和图自测卷卷姓名班级学号题号一二三四五总分题分1017174016100得分一、下面是有关关二叉树的叙叙述，请判断断正误（每小小题1分，共共10分）（）1..若二叉树用用二叉链表作作存贮结构，则则在n个结点点的二叉树链链表中只有nn—1个非空指针针域。（）2..二叉树中每每个结点的两两棵子树的高高度差等于11。（）3..二叉树中每每个结点的两两棵子树是有有序的。（）4..二叉树中每每个结点有两两棵非空子树树或有两棵空空子树。（）5..二叉树树中所有结点点个数是2kk-1-1，其其中k是树的的深度。（）6..对于一一棵非空二叉叉树，它的根根结点作为第第一层，则它它的第i层上上最多能有22i－1个结点点。（）7..具有122个结点的完完全二叉树有有5个度为22的结点。（）8..不同的求求最小生成树树的方法最后后得到的生成成树是相同的的.（）9..有n个顶顶点的无向图图,采用邻邻接矩阵表示示,图中的的边数等于邻邻接矩阵中非非零元素之和和的一半。（）100.无向图图的邻接矩阵阵一定是对称称矩阵，有向向图的邻接矩矩阵一定是非非对称矩阵。二、填空（每空空1分，共117分）1．由３个结结点所构成的的二叉树有种形态。2.一棵深深度为6的满满二叉树有个分分支结点和个叶子。3．一棵具有有257个结结点的完全二二叉树，它的的深度为。4．设一棵完完全二叉树有有700个结结点，则共有有个叶子结点点。5.用5个权权值{3,2,,4,55,1}构造的哈夫夫曼（Hufffman）树树的带权路径径长度是。6.判断一个个无向图是一一棵树的条件件是_______。7.在有nn个顶点的有有向图中，若若要使任意两两点间可以互互相到达，则则至少需要________条弧。8.G是一个个非连通无向向图，共有228条边，则则该图至少有有_______个顶点9.N个顶点点的连通图用用邻接矩阵表表示时,该矩矩阵至少有_________个非零元元素。10．在有n个个顶点的有向向图中，每个个顶点的度最最大可达_______。11．设有一稀稀疏图G，则则G采用存储较省省空间。12．设有一稠稠密图G，则则G采用存储较省空空间。13．n个顶点点e条边的图图采用邻接矩矩阵存储，深深度优先遍历历算法的时间间复杂度为；若采采用邻接表存存储时，该算算法的时间复复杂度为。14．已知图图的邻接矩阵阵，根据算法法思想，则从从顶点0出发发按深度优先先遍历的结点点序列是。则从顶顶点0出发按按广度优先遍遍历的结点序序列是。三、选择题（每每小题1分，共共17分）（）11．不含任任何结点的空空树。（Ａ）是一棵树树;（Ｂ）是一一棵二叉树;;（Ｃ）是一棵树树也是一棵二二叉树;（Ｄ）既既不是树也不不是二叉树（）22．二叉树是是非线性数据据结构，所以以。（Ａ）它不能用用顺序存储结结构存储;（Ｂ）它它不能用链式式存储结构存存储;（Ｃ）顺序存储储结构和链式式存储结构都都能存储;（Ｄ）顺顺序存储结构构和链式存储储结构都不能能使用（）33.具有有n(n>00)个结点的的完全二叉树树的深度为。(Ａ)logg2(n)(Ｂ)logg2(n)(Ｃ)logg2(n)+11(Ｄ)log2(n)+11（）44．把一棵树树转换为二叉叉树后，这棵棵二叉树的形形态是。（Ａ）唯一的（Ｂ）有多多种（Ｃ）有多种，但但根结点都没没有左孩子（ＤＤ）有多种，但但根结点都没没有右孩子（）55.在一个个图中，所有有顶点的度数数之和等于图图的边数的倍。A．1//2B..1C.2DD.4（）77.在一个个有向图中，所所有顶点的入入度之和等于于所有顶点的的出度之和的的倍。A．1//2B..1C.2DD.4（）88.用邻接接表表示图进进行广度优先先遍历时，通通常是采用来实实现算法的。A．栈B..队列C..树D..图（）99.深度优优先遍历类似似于二叉树的的A．先序遍历B.中序序遍历C.后序遍历历DD.层次次遍历（）110.广度度优先遍历类类似于二叉树树的A．先序遍历B.中序序遍历C.后序遍历历DD.层次次遍历11.树是是结点的有限限集合，它A根结点，记记为T。其余余的结点分成成为m（m≥≥0）个BB的集合T1，TT2，…，Tm，每每个集合又都都是树，此时时结点T称为为Ti的父结点，TTi称为T的子子结点（1≤≤i≤m）。一个个结点的子结结点个数为该该结点的C。供选择的答案A：①有00个或1个②有0个或多多个③有且只有11个④有1个或11个以上B:①互互不相交 ②允许相交交③③允许叶结结点相交④允许树枝枝结点相交C：①权 ②维数③次数④序答案：A=BB=C=12.二叉树树A。在完全全的二叉树中中，若一个结结点没有B，则则它必定是叶叶结点。每棵棵树都能惟一一地转换成与与它对应的二二叉树。由树树转换成的二二叉树里，一一个结点N的的左子女是NN在原树里对对应结点的C，而N的右右子女是它在在原树里对应应结点的D。供选择的答案A：①是特殊殊的树②不是树的特特殊形式③是两棵树的的总称④有是只有二二个根结点的的树形结构B:①左左子结点②右子结点点③左子结点点或者没有右右子结点④兄弟C～D：①最最左子结点②最右子结结点③最邻近的的右兄弟④最邻近的的左兄弟⑤最左的兄兄弟⑥最右的兄兄弟答案：A=BB=C=D＝四、阅读分析题题（每题5分分，共40分分）1.给定二叉叉树的两种遍遍历序列，分分别是：前序遍历序列：：D，A，CC，E，B，HH，F，G，II；中序序遍历序列：：D，C，BB，E，H，AA，G，I，FF，图1试画该出二叉树树图1图2图2图3图12．试写出如图图1所示的二二叉树分别按按先序、中序序、后序遍历历时得到的结结点序列。3.把如图图2所示的树树转化成二叉叉树。4.画出图3二二叉树相应的的森林。5．.已知如图图所示的有向向图，请给出出该图的:顶点1234顶点123456入度321122出度022313邻接矩阵；邻接表；逆邻接表。6．请对下图的的无向带权图图：写出它的邻接矩矩阵，并按普普里姆算法求求其最小生成成树；写出它的邻接表表，并按克鲁鲁斯卡尔算法法求其最小生生成树。7．已知二维数数组表示的图图的邻接矩阵阵如下图所示示。试分别画画出自顶点11出发进行遍遍历所得的深深度优先生成成树和广度优优先生成树。8．给定下列网网G:（110分）1试着找出网网G的最小生生成树，画出出其逻辑结构构图；2用两种不同同的表示法画画出网G的存存储结构图；；3用C语言（或或其他算法语语言）定义其其中一种表示示法（存储结结构）的数据据类型。五、算法设计题题（前1~55题中任选22题，第6~~7题中任选选1题，共116分）1.编写递归算算法，计算二二叉树中叶子子结点的数目目。2.写出求二二叉树深度的的算法，先定定义二叉树的的抽象数据类类型。3．编写递归算算法，求二叉叉树中以元素素值为x的结结点为根的子子树的深度。4.编写按层次次顺序（同一一层自左至右右）遍历二叉叉树的算法。5.编写算法判判别给定二叉叉树是否为完完全二叉树。6．编写算法，由由依次输入的的顶点数目、弧弧的数目、各各顶点的信息息和各条弧的的信息建立有有向图的邻接接表。解：StatuusBuiild_AddjListt(ALGrraph&&G)///输入有向向图的顶点数数,边数,顶顶点信息和边边的信息，以以建立邻接表表{returrnOK;;}//Builld_AdjjList7.试在邻接矩矩阵存储结构构上实现图的的基本操作：：DeletteArc((G,v,ww)，即删除除一条边的操操作。（如果要删除所所有从第i个个顶点出发的的边呢？提示：将将邻接矩阵的的第i行全部部置0）解：//设设本题中的图图G为有向无无权图StatusDeletteArc((MGrapph&G,,chaarv,charrw)///在邻接矩阵阵表示的图GG上删除边((v,w){}returrnOK;;}//DDeletee_Arc答案：一、12345678910√×××××√×√×二、156n个顶点n-11条边的连通通图11邻接表231,327n12邻接矩阵398913O(n2)O(n+ee)435092(n-1)140134256601234655533102*(n-1))15三、四、1、答：前序遍历序列：：D，A，CC，E，B，HH，F，G，II；中序序遍历序列：：D，C，BB，E，H，AA，G，I，FF，试画出二叉树BB，并简述由由任意二叉树树B的前序遍遍历序列和中中序遍历序列列求二叉树BB的思想方法法。解：方法是：由由前序先确定定root，由由中序可确定定root的左左、右子树。然然后由其左子子树的元素集集合和右子树树的集合对应应前序遍历序序列中的元素素集合，可继继续确定rooot的左右右孩子。将他他们分别作为为新的rooot，不断递递归，则所有有元素都将被被唯一确定，问问题得解。2、答：DLRR：ABDFJGKCEHILM LDR:BFJDGKACHELIM LRD：JFKGDBHLMIECA3、答：注意全部兄兄弟之间都要要连线（包括括度为2的兄兄弟）,并注意原有有连线结点一一律归入左子子树，新添连连线结点一律律归入右子树树。4、答：注意根右边边的子树肯定定是森林，而而孩子结点的的右子树均为为兄弟。五、1、顶点1顶点123456入度321122出度022313（2）（3）12→1→43→2→64→3→5→65→16→1→2→5（4） 1→2→5→62→3→63→44→25→4→66→3→4 6、解：设起点为aa。可以直接接由原始图画画出最小生成成树，而且最最小生成树只只有一种（类类）!邻接矩阵为：最小生成树最小生成树→PRIM算法（横横向变化）：：VbcdefghUV-UVexlowcostta4a3a∞a∞a∞a∞a∞{a}{b,c,d,,e,f,gg,h}Vexlowcostta40c5a∞a∞a∞c5{a,c}{b,d,ee,f,g,,h}Vexlowcostt00c5b9a∞a∞c5{a,c,b}}{d,e,f,,g,h}Vexlowcostt000d7d6d5d4{a,c,b,,d}{e,f,g,,h}Vexlowcostt000d7d6d50{a,c,b,,d,h}{e,f,g}Vexlowcostt000d7g200{a,c,b,,d,h,g}{f,e}}Vexlowcostt000f3000{a,c,b,,d,h,g,ff}{e}Vexlowcostt0000000{a,c,b,,d,h,g,ff,e}}{}邻接表为：0a→14→231b→04→25→35→49^2c→03→15→35→75^3d→15→25→47→56→65→74^4e→19→37→53^5f→36→43→62^6g→35→52→76^7h→25→34→66^克鲁斯卡尔算法步骤克鲁斯卡尔算法步骤(按边归并,堆排序)：先罗列：f2ga—3--cf—3—ea—4bd—44—h(a,b,c))(ee,f,g))(dd,h)取b—5—d,g—5--d就把三个连连通分量连接接起来了。7、8、1试着找出网网G的最小生生成树，画出出其逻辑结构构图；2用两种不同同的表示法画画出网G的存存储结构图；；3用C语言（或或其他算法语语言）定义其其中一种表示示法（存储结结构）的数据据类型。AB———————CE————FG————D解：AB———————CE————FG————D2.可用邻接接矩阵和邻接接表来描述：：描述存储结构的数据类型可参见教材或电子教案：注：描述存储结构的数据类型可参见教材或电子教案：注：用两个数组分别存储顶点表和邻接矩阵#defineINFINITYINT_MAX//最大值∞#defineMAX_VERTEX_NUM20//假设的最大顶点数（可取为7）Typedefenum{DG,DN,AG,AN}GraphKind;//有向/无向图，有向/无向网TypedefstructArcCell{//弧（边）结点的定义VRTypeadj;//顶点间关系，无权图取1或0；有权图取权值类型InfoType*info;//该弧相关信息的指针}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];Typedefstruct{//图的定义VertexTypevexs[MAX_VERTEX_NUM];//顶点表，用一维向量即可AdjMatrixarcs;//邻接矩阵IntVernum,arcnum;//顶点总数（7），弧（边）总数（9）GraphKindkind;//图的种类标志}Mgraph;邻接表为：0a→112→44^1b→012→220→48→59^2c→120→315→612^3d→215→610^4e→04→18→56^5f→19→46^6g→212→310五、1、intLeaafCounnt_BiTTree(BBitreeeT)///求二叉树中中叶子结点的的数目{if(!TT)retturn00;//空空树没有叶子子elseif(!TT->lchhild&&&!T->rrchildd)retturn11;//叶叶子结点elsereturrnLeaaf_Couunt(T-->lchiild)+LLeaf_CCount((T->rcchild));//左子子树的叶子数数加上右子树的叶子子数}//LeaffCountt_BiTrree2、intGett_Deptth(BittreeTT)//求子子树深度的递递归算法{if(!TT)retturn00;else{m=GGet_Deepth(TT->lchhild);;n=GGet_Deepth(TT->rchhild);;retturn((m>n?mm:n)+11;}}//Get__Depthh3、intGett_Sub__Depthh(BitrreeT,,intxx)//求二二叉树中以值值为x的结点点为根的子树树深度{if(T-->dataa==x){priintf(""%d\n"",Get__Depthh(T));;//找到到了值为x的的结点,求其其深度exiit1;}}else{if((T->lcchild))Get__Sub_DDepth((T->lcchild,,x);if((T->rcchild))Get__Sub_DDepth((T->rcchild,,x);///在左右子子树中继续寻寻找}}//Get__Sub_DDepth4、voidLaayerOrrder(BBitreeeT)///层序遍历二二叉树{InitQQueue((Q);///建立工作作队列EnQueeue(Q,,T);whilee(!QueeueEmppty(Q))){DeQQueue((Q,p);;vissit(p));if((p->lcchild))EnQuueue(QQ,p->llchildd);if((p->rcchild))EnQuueue(QQ,p->rrchildd);}}//LayeerOrdeer5、答：intIIsFulll_Bitrree(BiitreeT)//判判断二叉树是是否完全二叉叉树,是则返返回1,否则则返回0{InitQQueue((Q);flag==0;EnQueeue(Q,,T);///建立工作作队列whilee(!QueeueEmppty(Q))){{DeQQueue((Q,p);;if((!p)fflag=11;elsseif((flag))retuurn0;;elsse{EEnQueuue(Q,pp->lchhild);;EEnQueuue(Q,pp->rchhild);;//不管管孩子是否为为空,都入队队列}}//whhilereturrn1;}//IsFuull_Biitree分析:该问题可可以通过层序序遍历的方法法来解决.与与6.47相相比,作了一一个修改,不不管当前结点点是否有左右孩子子,都入队列列.这样当树树为完全二叉叉树时,遍历历时得到是一一个连续的不不包含空指针的序列.反反之,则序列列中会含有空空指针.6、解：StatuusBuiild_AddjListt(ALGrraph&&G)///输入有向向图的顶点数数,边数,顶顶点信息和边边的信息建立立邻接表{InitAALGrapph(G);;scanff("%d"",&v);;if(v<<0)reeturnERRORR;//顶顶点数不能为为负G.vexxnum=vv;scanff("%d"",&a);;if(a<<0)reeturnERRORR;//边边数不能为负负G.arccnum=aa;for(mm=0;m<<v;m+++)G.vverticces[m]].dataa=getcchar());//输输入各顶点的的符号for(mm=1;m<<=a;m+++){t=ggetchaar();hh=getcchar());//tt为弧尾,hh为弧头if(((i=LoocateVVex(G,,t))<00)retturnEERROR;;if(((j=LoocateVVex(G,,h))<00)retturnEERROR;;//顶点点未找到p=((ArcNoode*)mmallocc(sizeeof(ArrcNodee));if((!G.veerticees.[i]].firsstarc))G.veerticees[i]..firsttarc=pp;elsse{ffor(q==G.verrticess[i].ffirstaarc;q-->nexttarc;qq=q->nnextarrc);qq->nexxtarc==p;}p->>adjveex=j;pp->nexxtarc==NULL;;}//whhilereturrnOK;;}//Builld_AdjjList7、解：//本题中中的图G均为为有向无权图。StatusDelette_Arcc(MGraaph&GG,charrv,chharw))//在邻接接矩阵表示的的图G上删除除边(v,ww){if((ii=LocaateVexx(G,v)))<0)returrnERRROR;if((jj=LocaateVexx(G,w)))<0)returrnERRROR;if(G..arcs[[i][j]].adj)){G.aarcs[ii][j]..adj=00;G.aarcnumm--;}returrnOK;;}//Deleete_Arrc第9章查找自测卷答答案姓名班级A题号一二三四五总分题分1027162423100得分一、填空题（每每空1分，共共10分）1.在数据的的存放无规律律而言的线性性表中进行检检索的最佳方方法是顺序查找找（线性查找找）。2.线性有序序表（a1，a2，a3，…，a256)是从小到大大排列的，对对一个给定的的值k，用二二分法检索表表中与k相等等的元素，在在查找不成功功的情况下，最最多需要检索索8次。设有有100个结结点，用二分分法查找时，最最大比较次数数是7。3.假设在有有序线性表aa[20]上上进行折半查查找，则比较较一次查找成成功的结点数数为1；比较两次次查找成功的的结点数为2；比较较四次查找成成功的结点数数为8；平均均查找长度为为3.77。解：显然，平均均查找长度＝＝O（logg2n）<5次（225）。但具体体是多少次，则则不应当按照照公式来计算（即（221×log221）/220＝4.66次并不正确确！）。因为为这是在假设设n＝2m-1的情况下下推导出来的的公式。应当当用穷举法罗罗列：全部元素的查找找次数为＝（11＋2×2＋4×3＋8×4＋5×5）＝744；ASLL＝74/220=3.77！！！！4．折半查找有有序表（4，66，12，220，28，338，50，770，88，1100），若若查找表中元元素20，它它将依次与表表中元素28，6，12，20比较较大小。5.在各种查查找方法中，平平均查找长度度与结点个数数n无关的查查找方法是散列查找找。6.散列法存存储的基本思思想是由关键字的值值决定数据的的存储地址。7.有一个表表长为m的散散列表，初始始状态为空，现现将n（n<m）个不不同的关键码码插入到散列列表中，解决决冲突的方法法是用线性探探测法。如果果这n个关键键码的散列地地址都相同，则则探测的总次次数是n(n-1)/2=（1＋2＋…＋n-1）。(而任一元素素查找次数≤n-1)二、单项选择题题（每小题11分，共277分）（B）11．在表长为为ｎ的链表中中进行线性查查找，它的平平均查找长度度为Ａ.ＡＳＬ＝＝ｎ;Ｂ.ＡＳＬ＝＝（ｎ＋１）／／２;Ｃ.ＡＳＬ＝＝＋１;ＤＤ.ＡＳＬ≈ｌｏｇ２（ｎ＋１）－－１（A）2．折半查找找有序表（44，6，100，12，220，30，550，70，888，1000）。若查找找表中元素558，则它将将依次与表中中比较大小，查查找结果是失失败。A．20，700，30，550B．330，88，770，50C．20，550D．300，88，550（C）3．对22个个记录的有序序表作折半查查找，当查找找失败时，至至少需要比较较次关关键字。A．3B．4C．．5D．6（A）4.链表适用于于查找找A．顺序B．．二分法C．顺序序，也能二分分法D．随机（C）5.折半搜索索与二叉搜索索树的时间性性能A.相相同B..完全不不同CC.有时不不相同DD.数量级级都是O（llog2n）6．从供选择的的答案中，选选出应填入下下面叙述？内的最确切切的解答，把把相应编号写写在答卷的对对应栏内。要进行线性查找找，则线性表表A；要进行二二分查找，则则线性表B；；要进行散列列查找，则线线性表CC。某顺序存储的表表格，其中有有900000个元素，已已按关键项的的值的上升顺顺序排列。现现假定对各个个元素进行查查找的概率是是相同的，并并且各个元素素的关键项的的值皆不相同同。当用顺序序查找法查找找时，平均比比较次数约为为D，最大比比较次数为E。供选择的答案：：A~C：①必必须以顺序方方式存储②必须以链链表方式存储储③必须以散散列方式存储储④④既可以以以顺序方式，也也可以以链表表方式存储⑤必须以顺序序方式存储且且数据元素已已按值递增或或递减的次序序排好⑥必须以链表表方式存储且且数据元素已已按值递增或或递减的次序序排好D，E：①250000②300000③450000④900000答案：A=④B=⑤C=③D＝③E＝④7.从供选择的的答案中，选选出应填入下下面叙述？内的最确切切的解答，把把相应编号写写在答卷的对对应栏内。数据结构反映了了数据元素之之间的结构关关系。链表是是一种A，它它对于数据元元素的插入和和删除B。通通常查找线性性表数据元素素的方法有C和D两种方方法，其中C是一种只只适合于顺序序存储结构但但E的方法法；而D是是一种对顺序序和链式存储储结构均适用用的方法。供选择的答案：：A：①顺序存储储线性表②非顺序存储储非线性表 ③顺序存储非非线性表 ④非顺序存储储线性表B： ①不需需要移动结点点，不需改变变结点指针②不需要移动动结点，只需需改变结点指指针 ③只需移动结点点，不需改变变结点指针 ④既需移动结结点，又需改改变结点指针针C：①顺序查查找②循环查找 ③条件查找 ④二分法查找找D：①顺序查查找②随机查找 ③二分法查找找 ④分块查找E：①效率较较低的线性查查找 ②效率较低的的非线性查找找 ③效率较高的的非线性查找找 ④效率较高的的线性查找答案：A＝④B＝②C＝④D＝①E＝③8.从供选择的的答案中，选选出应填入下下面叙述？内的最确切切的解答，把把相应编号写写在答卷的对对应栏内。在二叉排序树中中，每个结点点的关键码值值A，B一棵二二叉排序，即即可得到排序序序列。同一一个结点集合合，可用不同同的二叉排序序树表示，人人们把平均检检索长度最短短的二叉排序序树称作最佳佳二叉排序，最最佳二叉排序序树在结构上上的特点是C。供选择的答案A：①比左子子树所有结点点的关键码值值大，比右子子树所有结点点的关键码值值小②比左子树所有有结点的关键键码值小，比比右子树所有有结点的关键键码值大③比左右子树树的所有结点点的关键码值值都大④与左子树所所有结点的关关键码值和右右子树所有结结点的关键码码值无必然的的大小关系B:①前前序遍历②中序（对对称）遍历③后序遍历历④④层次遍历历C：①除最下下二层可以不不满外，其余余都是充满的的②除最下一层层可以不满外外，其余都是是充满的③每个个结点的左右右子树的高度度之差的绝对对值不大于11④最下层的的叶子必须在在最左边答案：A＝①B＝②C＝②9.从供选择择的答案中，选选出应填入下下面叙述？内的最确切切的解答，把把相应编号写写在答卷的对对应栏内。散列法存储的基基本思想是根根据A来决定定B，碰撞撞（冲突）指指的是CC，处理理碰撞的两类类主要方法是是DD。供选择的答案A，B：①存存储地址②元素的符符号③元素个数数④关键码值值⑤⑤非码属性性⑥⑥平均检索索长度⑦负载因子子⑧散列表空空间C:①两两个元素具有有相同序号②两个元素素的关键码值值不同，而非非码属性相同同③不同关键键码值对应到到相同的存储储地址④负载因子子过大⑤数据元素素过多D：①线性性探查法和双双散列函数法法②建溢出区区法和不建溢溢出区法③除余法和折折叠法 ④拉链法和和开地址法答案：A＝④BB＝①CC＝③D＝④10.考虑具有有如下性质的的二叉树：除除叶子结点外外，每个结点点的值都大于于其左子树上上的一切结点点的值。并小小于等于其右右子树上的一一切结点的值值。现把9个数1，22，3，…，8，9填填入右图所示的二二叉树的9个个结点中，并并使之具有上上述性质。此此时，n1的的值是A，n22的值是B，nn9的值是C。现欲把把放入此树并并使该树保持持前述性质，增增加的一个结结点可以放在在D或E。供选择的答案A～C：①11②2③3④4⑤5⑥6⑦7⑧8⑨9D～E：①n7下面②n8下面面③n9下面面④n6下面面⑤n1与nn2之间⑥n2与nn4之间⑦n6与nn9之间⑧n3与nn6之间答案：A＝⑦B＝④C＝⑥D＝②E＝⑥三、简答题（每每小题4分，共共16分）1.对分（折半半）查找适不不适合链表结结构的序列，为为什么？用二二分查找的查查找速度必然然比线性查找找的速度快，这这种说法对吗吗？答：不适合！虽虽然有序的单单链表的结点点是按从小到到大（或从大大到小）顺序序排列，但因因其存储结构构为单链表，查查找结点时只只能从头指针针开始逐步搜搜索，故不能能进行折半查查找。二分查找的速度度在一般情况况下是快些，但但在特殊情况况下未必快。例例如所查数据据位于首位时时，则线性查查找快；而二二分查找则慢慢得多。2.假定对有序序表：（3，44，5，7，224，30，442，54，663，72，887，95）进进行折半查找找，试回答下下列问题：画出描述折半查查找过程的判判定树；若查找元素544，需依次与与哪些元素比比较？若查找元素900，需依次与与哪些元素比比较？假定每个元素的的查找概率相相等，求查找找成功时的平平均查找长度度。解：先画出判定树如如下（注：mmid=(11+12)//2=6）：305633774287424554722995(2)查找元元素54，需需依次与300,63,,42,54等元元素比较；(3)查找元元素90，需需依次与300,63,,87,995,722等元素比较较；（4）求ASSL之前，需需要统计每个个元素的查找找次数。判定定树的前3层层共查找1＋＋2×2＋4×3=17次次；但最后一层未满满，不能用88×4，只能用用5×4=20次次，所以ASL＝11/12（117＋20）＝＝37/122≈3.083.用比较两个个元素大小的的方法在一个个给定的序列列中查找某个个元素的时间间复杂度下限限是什么?如果要求时时间复杂度更更小,你采用用什么方法？？此方法的时时间复杂度是是多少?答：查找某个元元素的时间复复杂度下限，如如果理解为最最短查找时间间，则当关键键字值与表头头元素相同时时，比较1次次即可。要想想降低时间复复杂度，可以以改用Hassh查找法。此此方法对表内内每个元素的的比较次数都都是O（1）。4.设哈希（HHash）表表的地址范围围为0～177，哈希函数数为：H（KK）＝KMOD16。K为关键字，用用线性探测法法再散列法处处理冲突，输输入关键字序序列：（10，224，32，117，31，330，46，447，40，663，49）造出Hash表表，试回答下下列问题：画出哈希表的示示意图；若查找关键字663，需要依依次与哪些关关键字进行比比较？若查找关键字660，需要依依次与哪些关关键字比较？？假定每个关键字字的查找概率率相等，求查查找成功时的的平均查找长长度。解：（1）画画表如下：012345678910111213141516173217634924401030314647（2）查找663,首先要要与H(633)=63%%16=155号单元内容容比较，即663vs31,noo;然后顺移，与446,47,,32,177,63相比比，一共比较较了6次！（3）查找600,首先要与与H(60)=60%16=112号单元内内容比较，但但因为12号号单元为空（应应当有空标记记），所以应应当只比较这这一次即可。（4）对于黑黑色数据元素素，各比较11次；共6次次；对红色元素则各各不相同，要要统计移位的的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，所以ASL=11/11（66＋2＋3××3）＝177/11=11.545445454554≈1.55四、分析题（每每小题6分，共共24分）1.画出对对长度为100的有序表进进行折半查找找的判定树，并并求其等概率率时查找成功功的平均查找找长度。解：判定树应当当描述每次查查找的位置：：58136944771102.在一棵空的的二叉查找树树中依次插入入关键字序列列为12，77