- 547.00 KB
- 2022-04-22 11:32:18 发布
- 1、本文档共5页，可阅读全部内容。
- 2、本文档内容版权归属内容提供方，所产生的收益全部归内容提供方所有。如果您对本文有版权争议，可选择认领，认领后既往收益都归您。
- 3、本文档由用户上传，本站不保证质量和数量令人满意，可能有诸多瑕疵，付费之前，请仔细先通过免费阅读内容等途径辨别内容交易风险。如存在严重挂羊头卖狗肉之情形，可联系本站下载客服投诉处理。
- 文档侵权举报电话：19940600175。
'贵州大学理学院数学系信息与计算科学专业《数据结构》期末考试试题及答案(2003-2004学年第2学期)一、单项选择题1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。(A)、正确性(B).可行性(C).健壮性(D).输入性2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。for(i=n-1；i>=0；i--)for(j=0；jnext;p->next=Q.front->next;（B）、p=Q.front->next;Q.front->next=p->next;（C）、p=Q.rear->next;p->next=Q.rear->next;（D）、p=Q->next;Q->next=p->next;9．Huffman树的带权路径长度WPL等于（）（A）、除根结点之外的所有结点权值之和（B）、所有结点权值之和（C）、各叶子结点的带权路径长度之和（D）、根结点的值第127页共127页
10．线索二叉链表是利用（）域存储后继结点的地址。（A）、lchild（B）、data（C）、rchild（D）、root二、填空题1．逻辑结构决定了算法的，而存储结构决定了算法的。2．栈和队列都是一种的线性表，栈的插入和删除只能在进行。3．线性表（a1,a2,…,an）的顺序存储结构中，设每个单元的长度为L，元素ai的存储地址LOC(ai)为4．已知一双向链表如下(指针域名为next和prior)：yxeqp现将p所指的结点插入到x和y结点之间，其操作步骤为：；；；；5．n个结点无向完全图的的边数为，n个结点的生成树的边数为。6．已知一有向无环图如下：BACDFEG任意写出二种拓扑排序序列：、。7．已知二叉树的中序遍历序列为BCA，后序遍历序列为CBA，则该二叉树的先序遍历序列为，层序遍历序列为。三、应用题1．设散列函数H(k)=k%13,设关键字系列为{22,12,24,6,45,7,8,13,21},要求用线性探测法处理冲突。(6分)(1)构造HASH表。(2)分别求查找成功和不成功时的平均查找长度。2．给定表（19,14,22,15,20,21,56,10）.（8分）（1）按元素在表中的次序，建立一棵二叉排序树（2）对(1)中所建立的二叉排序树进行中序遍历，写出遍历序列。第127页共127页
（1）画出对(2)中的遍历序列进行折半查找过程的判定树。1．已知二个稀疏矩阵A和B的压缩存储三元组表如下：ABijVijV13-525224633725241342-152-9529558写出A-B压缩存储的三元组表。（5分）2．已知一维数组中的数据为（18,12,25,53,18）,试写出插入排序（升序）过程。并指出具有n个元素的插入排序的时间复杂度是多少？(5分)3．已知一网络的邻接矩阵如下，求从顶点A开始的最小生成树。(8分，要有过程)ABCDEF（1）求从顶点A开始的最小生成树。（2）分别画出以A为起点的DFS生成树和BFS生成树。6．已知数据六个字母及在通信中出现频率如下表：ABCDEF0.150.150.10.10.20.3把这些字母和频率作为叶子结点及权值，完成如下工作(7分，要有过程)。（1）画出对应的Huffman树。（2）计算带权路径长度WPL。（3）求A、B、C、D、E、F的Huffman编码。7．已知有如下的有向网：第127页共127页
25364106122AEBDC求顶点A到其它各顶点的最短路径（采用Dijkstra算法，要有过程）。（6分）三、设计题（30分，每题10分,用C语言写出算法，做在答题纸上）1．已知线性表（a1,a2,…,an）以顺序存储结构为存储结构，其类型定义如下：#defineLIST_INIT_SIZE100//顺序表初始分配容量typedefstruct{Elemtype*elem;//顺序存储空间基址intlength;//当前长度（存储元素个数）}SqList;设计一个算法，删除其元素值为x的结点（假若x是唯一的）。并求出其算法的平均时间复杂度。其算法函数头部如下：StatusListDelete(Sqlist&L,Elemtypex){……}an…a2a12．设顺序栈如左图所示。其中结点定义如下：toptypedefstruct{Elemtype*base;//栈底指针Elemtype*top;//栈顶指针}Stack;设计算法，将栈顶元素出栈并存入e中．base3．设二叉链树的类型定义如下：typedefintElemtype;typedefstructnode{Elemtypedata;structnode*lchild,*rchild;}BinNode,*BinTree;试写出求该二叉树叶子结点数的算法:StatusCountLeaves(BinTree&root,int&n)第127页共127页
{//nisthenumberofleaves……}答案：选择题（每题1分）1、C2、D3、A4、D5、C6、D7、A8、B9、C10、C一、填空题1．设计、实现2．特殊、栈顶3．LOC（a1）+(i-1)*L4．p->next=q->next;q->next->prior=p;q->next=p;p->prior=q;5．n(n-1)/2、n-16．ADCBFEG、ABCDEFFG7．ABC、ABC二、应用题1（1）Hash表（4分）地址0123456789101112关键安132164572282412探测次数171231311（2）查找成功的平均查找长度：（1分）（5*1+1*2+2*3+1*7）/9=20/9查找不成功的平均查找长度：（1分）（2+1+9+8+7+6+5+4+3+2+1）/13=2（1）、构造（3分）1914221015205621(2)、1014151920212256（2分）（3）、（3分）第127页共127页
3、(5分，每行0.5)ijv13-524633741342-152185584、初始关键字：[18]12255318第一趟：[1218]255318第二趟：[121825]5318第三趟：[12182553]18第四趟：[1218182553]（4分）O（n2）（1分）。5、7分（1）4分AB1C325D4EF（2）4分6、(1)3分EFABCD第127页共127页
（2）WPL=0.1*3+0.1*3+0.2*2+0.15*3+0.15*3+03*21=(1分)（3）A：010B：011C：110D：111E：00F；10（3分）12、A-B：（A、B）1分A-C：（A、D、C）2分A-D：（A、D）1分A-E：（A、D、E）2分三，设计题（20分）1、(10分)StatusListDelete(Sqlist&L,ElemTypex){inti,j;for(i=0;ilength;i++)if(L->elem[i]==x)break;if(i=L->length)returnERROR;for(j=i;jlengthi-1;j++)L->elem[j]=L->elem[j+1];L->length--;}（8分）平均时间复杂度：（2分）设元素个数记为n，则平均时间复杂度为：2（10分）voidpop(Stack&S,Elemtype&e){if(S.top==S.base)returnERROR;S.top--;e=*s.top;}2、（10分）voidCountLeaves(BinTreeT,int&n){if(T){if((!(T->lchild)&&!(T->rchild))n++;CountLeaves(T->lchild,n);CountLeaves(T->rchild,n);}}第127页共127页
习题1一、单项选择题1.数据结构是指（）。A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（）。A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构3.树形结构是数据元素之间存在一种（）。A.一对一关系B.多对多关系C.多对一关系D.一对多关系4.设语句x++的时间是单位时间，则以下语句的时间复杂度为（）。for(i=1;i<=n;i++)for(j=i;j<=n;j++)x++;A.O(1)B.O()C.O(n)D.O()5.算法分析的目的是（1第127页共127页
），算法分析的两个主要方面是（2）。（1）A.找出数据结构的合理性B.研究算法中的输入和输出关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性（2）A.空间复杂度和时间复杂度B.正确性和简明性C.可读性和文档性D.数据复杂性和程序复杂性6.计算机算法指的是（1），它具备输入，输出和（2）等五个特性。（1）A.计算方法B.排序方法C.解决问题的有限运算序列D.调度方法（2）A.可行性，可移植性和可扩充性B.可行性，确定性和有穷性C.确定性，有穷性和稳定性D.易读性，稳定性和安全性7.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储比顺序存储要（）。第127页共127页
A.低B.高C.相同D.不好说8.数据结构作为一门独立的课程出现是在（）年。A.1946B.1953C.1964D.19689.数据结构只是研究数据的逻辑结构和物理结构，这种观点（）。A.正确B.错误C.前半句对，后半句错D.前半句错，后半句对10.计算机内部数据处理的基本单位是（）。A.数据B.数据元素C.数据项D.数据库二、填空题1.数据结构按逻辑结构可分为两大类，分别是____________?__和_________________。2.数据的逻辑结构有四种基本形态，分别是________________、__________________、__________________和__________________。3.线性结构反映结点间的逻辑关系是__________________的，非线性结构反映结点间的逻辑关系是__________________的。4.一个算法的效率可分为__________________效率和第127页共127页
__________________效率。5.在树型结构中，树根结点没有__________________结点，其余每个结点的有且只有__________________个前趋驱结点；叶子结点没有__________________结点；其余每个结点的后续结点可以__________________。6.在图型结构中，每个结点的前趋结点数和后续结点数可以__________________。7.线性结构中元素之间存在__________________关系；树型结构中元素之间存在__________________关系；图型结构中元素之间存在__________________关系。8.下面程序段的时间复杂度是__________________。for(i=0;i=0)&&A[i]!=k))j--;return(i);5.fact(n){第127页共127页
if(n<=1)return(1);elsereturn(n*fact(n-1));}习题1参考答案一、单项选择题1.A2.C3.D4.B5.C、A6.C、B7.B8.D9.B10.B二、填空题1.线性结构，非线性结构2.集合，线性，树，图3.一对一，一对多或多对多4.时间，空间5.前趋，一，后继，多6.有多个7.一对一，一对多，多对多8.O()9.O()10.O(第127页共127页
)11.O(logn)12.程序对于精心设计的典型合法数据输入能得出符合要求的结果。13.事后统计，事前估计三、算法设计题1.O()2.O()3.O(n)4.O(n)5.O(n)习题2一、单项选择题1.线性表是________。A．一个有限序列，可以为空B．一个有限序列，不可以为空C．一个无限序列，可以为空D．一个无限序列，不可以为空2.在一个长度为n的顺序表中删除第i个元素(0<=i<=n)时，需向前移动个元素。A．n-iB．n-i+lC．n-i-1D．i3.线性表采用链式存储时，其地址________。第127页共127页
A．必须是连续的B．一定是不连续的C．部分地址必须是连续的D．连续与否均可以4.从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。A．n/2B．nC．（n+1）/2D．（n-1）/25.在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是____。A．p->next=s;s->prior=p;p->next->prior=s;s->next=p->next;B．s->prior=p;s->next=p->next;p->next=s;p->next->prior=s;C．p->next=s;p->next->prior=s;s->prior=p;s->next=p->next;D．s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;6.设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为________。A．p->next=p->next->next;B．第127页共127页
p=p->next;C．p=p->next->next;D．p->next=p;7.在一个长度为n的顺序表中向第i个元素(0next=p->next;p->next=sB．q->next=s;s->next=pC．p->next=s->next;s->next=pD．p->next=s;s->next=q9.以下关于线性表的说法不正确的是______。A．线性表中的数据元素可以是数字、字符、记录等不同类型。B．线性表中包含的数据元素个数不是任意的。C．线性表中的每个结点都有且只有一个直接前趋和直接后继。D．存在这样的线性表：表中各结点都没有直接前趋和直接后继。10.线性表的顺序存储结构是一种_______的存储结构。第127页共127页
A．随机存取B．顺序存取C．索引存取D．散列存取11.在顺序表中，只要知道_______，就可在相同时间内求出任一结点的存储地址。A．基地址B．结点大小C．向量大小D．基地址和结点大小12.在等概率情况下，顺序表的插入操作要移动______结点。A．全部B．一半C．三分之一D．四分之一13.在______运算中，使用顺序表比链表好。A．插入B．删除C．根据序号查找D．根据元素值查找14.在一个具有n个结点的有序单链表中插入一个新结点并保持该表有序的时间复杂度是_______。A．O(1)B．O(n)C．O(n2)D．O(log2n)15.设有一个栈，元素的进栈次序为A,B,C,D,E,下列是不可能的出栈序列__________。A．A,B,C,D,EB．B,C,D,E,AC．E,A,B,C,DD．E,D,C,B,A第127页共127页
16.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为______。A．top不变B．top=0C．top--D．top++17.向一个栈顶指针为hs的链栈中插入一个s结点时，应执行______。A．hs->next=s;B．s->next=hs;hs=s;C．s->next=hs->next;hs->next=s;D．s->next=hs;hs=hs->next;18.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为________。A．rear％n==frontB．（front+l）％n==rearC．rear％n-1==frontD．(rear+l)％n==front19.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为________。A．rear％n==frontB．front+l=第127页共127页
rearC．rear==frontD．(rear+l)％n=front20.在一个链队列中，假定front和rear分别为队首和队尾指针，则删除一个结点的操作为________。A．front=front->next B．rear=rear->nextC．rear=front->next D．front=rear->next二、填空题1.线性表是一种典型的_________结构。2.在一个长度为n的顺序表的第i个元素之前插入一个元素，需要后移____个元素。3.顺序表中逻辑上相邻的元素的物理位置________。4.要从一个顺序表删除一个元素时，被删除元素之后的所有元素均需_______一个位置，移动过程是从_______向_______依次移动每一个元素。5.在线性表的顺序存储中，元素之间的逻辑关系是通过_______决定的；在线性表的链接存储中，元素之间的逻辑关系是通过_______决定的。6.在双向链表中，每个结点含有两个指针域，一个指向_______结点，另一个指向_______结点。7.第127页共127页
当对一个线性表经常进行存取操作，而很少进行插入和删除操作时，则采用_______存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用_______存储结构为宜。8.顺序表中逻辑上相邻的元素，物理位置_______相邻，单链表中逻辑上相邻的元素，物理位置_______相邻。9.线性表、栈和队列都是_______结构，可以在线性表的______位置插入和删除元素；对于栈只能在_______位置插入和删除元素；对于队列只能在_______位置插入元素和在_______位置删除元素。10.根据线性表的链式存储结构中每个结点所含指针的个数，链表可分为_________和_______；而根据指针的联接方式，链表又可分为________和_________。11.在单链表中设置头结点的作用是________。12.对于一个具有n个结点的单链表，在已知的结点p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为_______。13.对于一个栈作进栈运算时，应先判别栈是否为_______，作退栈运算时，应先判别栈是否为_______，当栈中元素为m时，作进栈运算时发生上溢，则说明栈的可用最大容量为_______第127页共127页
。为了增加内存空间的利用率和减少发生上溢的可能性，由两个栈共享一片连续的内存空间时，应将两栈的_______分别设在这片内存空间的两端，这样只有当_______时才产生上溢。14.设有一空栈，现有输入序列1，2，3，4，5，经过push,push,pop,push,pop,push,push后，输出序列是_________。15.无论对于顺序存储还是链式存储的栈和队列来说，进行插入或删除运算的时间复杂度均相同为__________。三、简答题1.描述以下三个概念的区别：头指针，头结点，表头结点。2.线性表的两种存储结构各有哪些优缺点？3.对于线性表的两种存储结构，如果有n个线性表同时并存，而且在处理过程中各表的长度会动态发生变化，线性表的总数也会自动改变，在此情况下，应选用哪一种存储结构？为什么？4.对于线性表的两种存储结构，若线性表的总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素，应选用何种存储结构？试说明理由。5.在单循环链表中设置尾指针比设置头指针好吗？为什么?第127页共127页
6.假定有四个元素A,B,C,D依次进栈，进栈过程中允许出栈，试写出所有可能的出栈序列。7.什么是队列的上溢现象？一般有几种解决方法，试简述之。8.下述算法的功能是什么?LinkList*Demo(LinkList*L){//L是无头结点的单链表LinkList*q,*p;if(L&&L->next){q=L;L=L->next;p=L; while(p->next)p=p->next; p->next=q;q->next=NULL; } return(L);}四、算法设计题1.设计在无头结点的单链表中删除第i个结点的算法。2.在单链表上实现线性表的求表长ListLength(L)运算。3.设计将带表头的链表逆置算法。第127页共127页
4.假设有一个带表头结点的链表，表头指针为head，每个结点含三个域：data,next和prior。其中data为整型数域，next和prior均为指针域。现在所有结点已经由next域连接起来，试编一个算法，利用prior域（此域初值为NULL）把所有结点按照其值从小到大的顺序链接起来。5.已知线性表的元素按递增顺序排列，并以带头结点的单链表作存储结构。试编写一个删除表中所有值大于min且小于max的元素（若表中存在这样的元素）的算法。6.已知线性表的元素是无序的，且以带头结点的单链表作为存储结构。设计一个删除表中所有值小于max但大于min的元素的算法。7.假定用一个单循环链表来表示队列（也称为循环队列），该队列只设一个队尾指针，不设队首指针，试编写下列各种运算的算法：（1）向循环链队列插入一个元素值为x的结点；（2）从循环链队列中删除一个结点。8.设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。习题2参考答案第127页共127页
一、单项选择题1．A2．A3．D4．C5．D6．A7．B8．B9．C10．A11．D12．B13．C14．B15．C16．C17．B18．D19．C20．A二、填空题1．线性2．n-i+13．相邻4．前移，前，后5．物理存储位置，链域的指针值6．前趋，后继7．顺序，链接8．一定，不一定9．线性，任何，栈顶，队尾，队头10．单链表，双链表，非循环链表，循环链表11．使空表和非空表统一；算法处理一致12．O(1)，O(n)13．栈满，栈空，m，栈底，两个栈的栈顶在栈空间的某一位置相遇第127页共127页
14．2、315．O(1)三、简答题1．头指针是指向链表中第一个结点（即表头结点）的指针；在表头结点之前附设的结点称为头结点；表头结点为链表中存储线性表中第一个数据元素的结点。若链表中附设头结点，则不管线性表是否为空表，头指针均不为空，否则表示空表的链表的头指针为空。2．线性表具有两种存储结构即顺序存储结构和链接存储结构。线性表的顺序存储结构可以直接存取数据元素，方便灵活、效率高，但插入、删除操作时将会引起元素的大量移动，因而降低效率：而在链接存储结构中内存采用动态分配，利用率高，但需增设指示结点之间关系的指针域，存取数据元素不如顺序存储方便，但结点的插入、删除操作较简单。3．应选用链接存储结构，因为链式存储结构是用一组任意的存储单元依次存储线性表中的各元素，这里存储单元可以是连续的，也可以是不连续的：这种存储结构对于元素的删除或插入运算是不需要移动元素的，只需修改指针即可，所以很容易实现表的容量的扩充。第127页共127页
4．应选用顺序存储结构，因为每个数据元素的存储位置和线性表的起始位置相差一个和数据元素在线性表中的序号成正比的常数。因此，只要确定了其起始位置，线性表中的任一个数据元素都可随机存取，因此，线性表的顺序存储结构是一种随机存取的存储结构，而链表则是一种顺序存取的存储结构。5．设尾指针比设头指针好。尾指针是指向终端结点的指针，用它来表示单循环链表可以使得查找链表的开始结点和终端结点都很方便，设一带头结点的单循环链表，其尾指针为rear，则开始结点和终端结点的位置分别是rear->next->next和rear,查找时间都是O(1)。若用头指针来表示该链表，则查找终端结点的时间为O(n)。6．共有14种可能的出栈序列，即为：ABCD,ABDC，ACBD,ACDB，BACD，ADCB，BADC，BCAD,BCDA，BDCA,CBAD,CBDA，CDBA,DCBA7．在队列的顺序存储结构中，设队头指针为front，队尾指针为rear，队列的容量（即存储的空间大小）为maxnum。当有元素要加入队列（即入队）时，若rear=maxnum第127页共127页
，则会发生队列的上溢现象，此时就不能将该元素加入队列。对于队列，还有一种“假溢出”现象，队列中尚余有足够的空间，但元素却不能入队，一般是由于队列的存储结构或操作方式的选择不当所致，可以用循环队列解决。一般地，要解决队列的上溢现象可有以下几种方法：（1）可建立一个足够大的存储空间以避免溢出，但这样做往往会造成空间使用率低，浪费存储空间。（2）要避免出现“假溢出”现象可用以下方法解决：第一种：采用移动元素的方法。每当有一个新元素入队，就将队列中已有的元素向队头移动一个位置，假定空余空间足够。第二种：每当删去一个队头元素，则可依次移动队列中的元素总是使front指针指向队列中的第一个位置。第三种：采用循环队列方式。将队头、队尾看作是一个首尾相接的循环队列，即用循环数组实现，此时队首仍在队尾之前，作插入和删除运算时仍遵循“先进先出”的原则。8．该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。四、算法设计题第127页共127页
1．算法思想为：（1）应判断删除位置的合法性，当i<0或i>n-1时，不允许进行删除操作；（2）当i=0时，删除第一个结点：（3）当０next;free(s);}else{j=0;s=q;第127页共127页
while((jnext;j++;}if(s==NULL)printf("Cant"tdelete");else{p->next=s->next;free(s);}}}2．由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法描述如下：intListLength(LinkList*L){//求带头结点的单链表的表长 intlen=0; ListList*p;第127页共127页
p=L; while(p->next!=NULL){p=p->next; len++; } return(len);}3．设单循环链表的头指针为head，类型为LinkList。逆置时需将每一个结点的指针域作以修改，使其原前趋结点成为后继。如要更改q结点的指针域时，设s指向其原前趋结点，p指向其原后继结点，则只需进行q->next=s;操作即可，算法描述如下：voidinvert(LinkList*head){//逆置head指针所指向的单循环链表linklist*p,*q,*s;q=head;p=head->next;while(p!=head)//当表不为空时，逐个结点逆置{s=q;第127页共127页
q=p;p=p->next;q->next=s;}p->next=q;}4．定义类型LinkList如下：typedefstructnode{intdata;structnode*next,*prior;}LinkList;此题可采用插入排序的方法，设p指向待插入的结点，用q搜索已由prior域链接的有序表找到合适位置将p结点链入。算法描述如下：insert(LinkList*head){LinkList*p,*s,*q;p=head->next;//p指向待插入的结点，初始时指向第一个结点while(p!=NULL)第127页共127页
{s=head;//s指向q结点的前趋结点q=head->prior;//q指向由prior域构成的链表中待比较的结点while((q!=NULL)&&(p->data>q->data))//查找插入结点p的合适的插入位置{s=q;q=q->prior;}s->prior=p;p->prior=q;//结点p插入到结点s和结点q之间p=p->next;}}5．算法描述如下：delete(LinkList*head,intmax,intmin){linklist*p,*q;if(head!=NULL){q=head;p=head->next;第127页共127页
while((p!=NULL)&&(p->data<=min)){q=p;p=p->next;}while((p!=NULL)&&(p->datanext;q->next=p; }}6．算法描述如下：delete(LinkList*head,intmax,intmin){LinkList*p,*q;q=head;p=head->next;while(p!=NULL)if((p->data<=min)||(p->data>=max)){q=p;p=p->next;第127页共127页
}else{q->next=p->next;free(p);p=q->next;}}7．本题是对一个循环链队列做插入和删除运算，假设不需要保留被删结点的值和不需要回收结点，算法描述如下：（1）插入（即入队）算法：insert(LinkList*rear,elemtypex){//设循环链队列的队尾指针为rear,x为待插入的元素LinkList*p;p=(LinkList*)malloc(sizeof(LinkList));if(rear==NULL)//如为空队，建立循环链队列的第一个结点{rear=p;rear->next=p;//链接成循环链表}else//否则在队尾插入p结点第127页共127页
{p->next=rear->next;rear->next=p;rear=p;}}（2）删除（即出队）算法：delete(LinkList*rear){//设循环链队列的队尾指针为rearif(rear==NULL)//空队printf("underflown");if(rear->next==rear)//队中只有一个结点rear=NULL;elserear->next=rear->next->next;//rear->next指向的结点为循环链队列的队头结点}8．只要从终端结点开始往前找到第一个比x大(或相等)的结点数据，在这个位置插入就可以了。算法描述如下：intInsertDecreaseList(SqList*L,elemtypex第127页共127页
){inti;if((*L).len>=maxlen){printf(“overflow");return(0);}for(i=(*L).len;i>0&&(*L).elem[i-1]data!=pt->data))pt=pt->next;if(pt==NULL)ps=NULL;else{ps=ps->next;s=ps;}}returns;}//find习题4一、单项选择题1.设二维数组A[0…m-1][0…n-1]第127页共127页
按行优先顺序存储在内存中，第一个元素的地址为p，每个元素占k个字节，则元素aij的地址为（）。A.p+[i*n+j-1]*kB.p+[(i-1)*n+j-1]*kC.p+[(j-1)*n+i-1]*kD.p+[j*n+i-1]*k2.已知二维数组A10×10中，元素a20的地址为560，每个元素占4个字节，则元素a10的地址为（）。A.520B.522C.524D.5183.若数组A[0…m][0…n]按列优先顺序存储，则aij地址为（）。A.LOC(a00)+[j*m+i]B.LOC(a00)+[j*n+i]C.LOC(a00)+[(j-1)*n+i-1]D.LOC(a00)+[(j-1)*m+i-1]4.若下三角矩阵An×n，按列顺序压缩存储在数组Sa[0…(n+1)n/2]中，则非零元素aij的地址为（）。（设每个元素占d个字节）A.[(j-1)*n-+i-1]*dB.[(j-1)*n-+i]*dC．[(j-1)*n-+i+1]*dD．[(j-1)*n-+i-2]*d5.设有广义表D=(a,b,D)，其长度为（），深度为（）。第127页共127页
A.无穷大B.3C.2D.56.广义表A=（a），则表尾为（）。A.aB.(())C.空表D.(a)7.广义表A=((x,(a,B)),(x,(a,B),y))，则运算head(head(tail(A)))的结果为（）。A.xB.(a,B)C.(x,(a,B))D.A8.下列广义表用图来表示时，分支结点最多的是（）。A.L=((x,(a,B)),(x,(a,B),y))B.A=(s,(a,B))C.B=((x,(a,B),y))D.D=((a,B),(c,(a,B),D)9.通常对数组进行的两种基本操作是（）。A.建立与删除B.索引和修改C.查找和修改D.查找与索引10.假定在数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，存放该数组至少需要的单元数为（）。A.80B.100C.240D.27011.数组A中，每个元素的长度为3个字节，行下标i从1到8，列下标j从1到10，从首地址SA开始连续存放在存储器内，该数组按行存放时，元素A[8][5]的起始地址为（）。第127页共127页
A.SA+141B.SA+144C.SA+222D.SA+22512.稀疏矩阵一般的压缩存储方法有两种，即（）。A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表13.若采用三元组压缩技术存储稀疏矩阵，只要把每个元素的行下标和列下标互换，就完成了对该矩阵的转置运算，这种观点（）。A.正确B.不正确14.一个广义表的表头总是一个（）。A.广义表B.元素C.空表D.元素或广义表15.一个广义表的表尾总是一个（）。A.广义表B.元素C.空表D.元素或广义表16.数组就是矩阵，矩阵就是数组，这种说法（）。A.正确B.错误C.前句对，后句错D.后句对二、填空题1.一维数组的逻辑结构是______________，存储结构是______________；对于二维或多维数组，分为______________和______________两种不同的存储方式。第127页共127页
2.对于一个二维数组A[m][n]，若按行序为主序存储，则任一元素A[i][j]相对于A[0][0]的地址为______________。3.一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度为_____，深度为_____。4.一个稀疏矩阵为，则对应的三元组线性表为_____________。5.一个n×n的对称矩阵，如果以行为主序或以列为主序存入内存，则其容量为______________。6.已知广义表A=((a,b,c),(d,e,f))，则运算head(tail(tail(A)))=____________。7.设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a的地址为______________。8.已知广义表Ls=(a,(b,c,d),e)，运用head和tail函数取出Ls中的原子b的运算是______________。9.三维数组R[c1…d1,c2…d2,c3…d3]共含有第127页共127页
______________个元素。（其中：c1≤d1,c2≤d2,c3≤d3）10.数组A[1…10，-2…6，2…8]以行优先的顺序存储，设第一个元素的首地址是100，每个元素占3个存储长度的存储空间，则元素A[5，0，7]的存储地址为______________。三、判断题1.数组可看作基本线性表的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。（）2.多维数组可以看作数据元素也是基本线性表的基本线性表。（）3.以行为主序或以列为主序对于多维数组的存储没有影响。（）4.对于不同的特殊矩阵应该采用不同的存储方式。（）5.采用压缩存储之后，下三角矩阵的存储空间可以节约一半。（）6.在一般情况下，采用压缩存储之后，对称矩阵是所有特殊矩阵中存储空间节约最多的。（）7.矩阵不仅是表示多维数组，而且是表示图的重要工具。（）8.距阵中的数据元素可以是不同的数据类型。（）9.矩阵中的行列数往往是不相等的。（）第127页共127页
10.广义表的表头可以是广义表，也可以是单个元素。（）11.广义表的表尾一定是一个广义表。（）12.广义表的元素可以是子表，也可以是单元素。（）13.广义表不能递归定义。（）14.广义表实际上是基本线性表的推广。（）15.广义表的组成元素可以是不同形式的元素。（）习题4参考答案一、单项选择题1.A2.A3.A4.B5.BA6.C7.A8.A9.C10.C11.C12.C13.B14.D15.A16.B二、填空题1.线性结构，顺序结构，以行为主序，以列为主序2.i×n+j个元素位置3.5，34.（（0，2，2），（1，0，3），（2，2，-1），（2，3，5））5.n×(n+1)/26.e7.418.第127页共127页
head(head(tail(Ls)))9.（d-c+1）×（d-c+1）×（d-c+1）10.913三、判断题1.×2.√3.√4.√5.×6.×7.√8.×9.×10.√11.√12.√13.×14.√15.√习题5一、单项选择题1.在一棵度为3的树中，度为3的结点数为2个，度为2的结点数为1个，度为1的结点数为2个，则度为0的结点数为（）个。A.4B.5C.6D.72.假设在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为（）个。A.15B.16C.17D.473.假定一棵三叉树的结点数为50，则它的最小高度为（）。A.3B.4C.5D.第127页共127页
64.在一棵二叉树上第4层的结点数最多为（）。A.2B.4C.6D.85.用顺序存储的方法将完全二叉树中的所有结点逐层存放在数组中R[1..n]，结点R[i]若有左孩子，其左孩子的编号为结点（）。A.R[2i+1]B.R[2i]C.R[i/2]D.R[2i-1]6.由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。A.24B.48C.72D.537.线索二叉树是一种（）结构。A.逻辑B.逻辑和存储C.物理D.线性8.线索二叉树中，结点p没有左子树的充要条件是（）。A.p->lc=NULLB.p->ltag=1C.p->ltag=1且p->lc=NULLD.以上都不对9.设n,m为一棵二叉树上的两个结点，在中序遍历序列中n在m前的条件是（）。A.n在m右方B.n在m左方C.n是m的祖先D.n是m的子孙10.如果F是由有序树T转换而来的二叉树，那么T第127页共127页
中结点的前序就是F中结点的（）。A.中序B.前序C.后序D.层次序11.欲实现任意二叉树的后序遍历的非递归算法而不必使用栈，最佳方案是二叉树采用（）存储结构。A.三叉链表B.广义表C.二叉链表D.顺序12.下面叙述正确的是（）。A.二叉树是特殊的树B.二叉树等价于度为2的树C.完全二叉树必为满二叉树D.二叉树的左右子树有次序之分13.任何一棵二叉树的叶子结点在先序、中序和后序遍历序列中的相对次序（）。A.不发生改变B.发生改变C.不能确定D.以上都不对14.已知一棵完全二叉树的结点总数为9个，则最后一层的结点数为（）。A.1B.2C.3D.415.根据先序序列ABDC和中序序列DBAC确定对应的二叉树，该二叉树（）。第127页共127页
A.是完全二叉树B.不是完全二叉树C.是满二叉树D.不是满二叉树二、判断题1.二叉树中每个结点的度不能超过2，所以二叉树是一种特殊的树。（ ）2.二叉树的前序遍历中，任意结点均处在其子女结点之前。（ ）3.线索二叉树是一种逻辑结构。（ ）4.哈夫曼树的总结点个数（多于1时）不能为偶数。（ ）5.由二叉树的先序序列和后序序列可以唯一确定一颗二叉树。（ ）6.树的后序遍历与其对应的二叉树的后序遍历序列相同。（ ）7.根据任意一种遍历序列即可唯一确定对应的二叉树。（ ）8.满二叉树也是完全二叉树。（ ）9.哈夫曼树一定是完全二叉树。（ ）10.树的子树是无序的。（ ）第127页共127页
三、填空题1.假定一棵树的广义表表示为A（B（E），C（F（H，I，J），G），D），则该树的度为_____，树的深度为_____，终端结点的个数为______，单分支结点的个数为______，双分支结点的个数为______，三分支结点的个数为_______，C结点的双亲结点为_______，其孩子结点为_______和_______结点。2.设F是一个森林，B是由F转换得到的二叉树，F中有n个非终端结点，则B中右指针域为空的结点有_______个。3.对于一个有n个结点的二叉树，当它为一棵________二叉树时具有最小高度，即为_______，当它为一棵单支树具有_______高度，即为_______。4.由带权为3，9，6，2，5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为___。5.在一棵二叉排序树上按_______遍历得到的结点序列是一个有序序列。6.对于一棵具有n个结点的二叉树，当进行链接存储时，其二叉链表中的指针域的总数为_______个，其中_______个用于链接孩子结点，_______个空闲着。第127页共127页
7.在一棵二叉树中，度为0的结点个数为n0，度为2的结点个数为n2，则n0=______。8.一棵深度为k的满二叉树的结点总数为_______，一棵深度为k的完全二叉树的结点总数的最小值为_____，最大值为______。9.由三个结点构成的二叉树，共有____种不同的形态。10.设高度为h的二叉树中只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为____。11.一棵含有n个结点的k叉树，______形态达到最大深度，____形态达到最小深度。12.对于一棵具有n个结点的二叉树，若一个结点的编号为i(1≤i≤n)，则它的左孩子结点的编号为________，右孩子结点的编号为________，双亲结点的编号为________。13.对于一棵具有n个结点的二叉树，采用二叉链表存储时，链表中指针域的总数为_________个，其中___________个用于链接孩子结点，_____________个空闲着。14.哈夫曼树是指________________________________________________的二叉树。第127页共127页
15.空树是指________________________，最小的树是指_______________________。16.二叉树的链式存储结构有______________和_______________两种。17.三叉链表比二叉链表多一个指向______________的指针域。18.线索是指___________________________________________。19.线索链表中的rtag域值为_____时，表示该结点无右孩子，此时______域为指向该结点后继线索的指针。20.本节中我们学习的树的存储结构有_____________、___________和___________。四、应用题1.已知一棵树边的集合为{，，，，，，，，，，，，}，请画出这棵树，并回答下列问题：（1）哪个是根结点？（2）哪些是叶子结点？第127页共127页
（3）哪个是结点g的双亲？（4）哪些是结点g的祖先？（5）哪些是结点g的孩子？（6）哪些是结点e的孩子？（7）哪些是结点e的兄弟？哪些是结点f的兄弟？（8）结点b和n的层次号分别是什么？（9）树的深度是多少？（10）以结点c为根的子树深度是多少？2.一棵度为2的树与一棵二叉树有何区别。3.试分别画出具有3个结点的树和二叉树的所有不同形态？4.已知用一维数组存放的一棵完全二叉树：ABCDEFGHIJKL，写出该二叉树的先序、中序和后序遍历序列。5.一棵深度为H的满k叉树有如下性质：第H层上的结点都是叶子结点，其余各层上每个结点都有k棵非空子树，如果按层次自上至下，从左到右顺序从1开始对全部结点编号，回答下列问题：（1）各层的结点数目是多少？（2）编号为n的结点的父结点如果存在，编号是多少？第127页共127页
（3）编号为n的结点的第i个孩子结点如果存在，编号是多少？（4）编号为n的结点有右兄弟的条件是什么？其右兄弟的编号是多少？6.找出所有满足下列条件的二叉树：（1）它们在先序遍历和中序遍历时，得到的遍历序列相同；（2）它们在后序遍历和中序遍历时，得到的遍历序列相同；（3）它们在先序遍历和后序遍历时，得到的遍历序列相同；7.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请写出该二叉树的后序遍历序列。8.假设一棵二叉树的后序序列为DCEGBFHKJIA，中序序列为DCBGEAHFIJK，请写出该二叉树的后序遍历序列。9.给出如图5-14所示的森林的先根、后根遍历结点序列，然后画出该森林对应的二叉树。10．给定一组权值（5，9，11，2，7，16），试设计相应的哈夫曼树。第127页共127页
五、算法设计题1.一棵具有n个结点的完全二叉树以一维数组作为存储结构，试设计一个对该完全二叉树进行先序遍历的算法。2.给定一棵用二叉链表表示的二叉树，其中的指针t指向根结点，试写出从根开始，按层次遍历二叉树的算法，同层的结点按从左至右的次序访问。3.写出在中序线索二叉树中结点P的右子树中插入一个结点s的算法。4.给定一棵二叉树，用二叉链表表示，其根指针为t，试写出求该二叉树中结点n的双亲结点的算法。若没有结点n或者该结点没有双亲结点，分别输出相应的信息；若结点n有双亲，输出其双亲的值。习题5参考答案一、单项选择题1.C2.B3.C4.D5.B6.D7.C8.B9.B10.B11.A12.D13.A14.B15.A第127页共127页
二、判断题1.×2.√3.×4.√5.×6.√7.√8.√9.×10.×三、填空题1.3，4，6，1，1，2，A，F，G2.n+13.完全，，最大，n4.555.中序6.2n，n-1，n+17.n2+18.2k-1，2k-1，2k-19.510.2h-111.单支树，完全二叉树12.2i，2i+1，i/2（或?i/2?）13.2n，n-1，n+114.带权路径长度最小15.结点数为0，只有一个根结点的树16.二叉链表，三叉链表第127页共127页
17.双亲结点18.指向结点前驱和后继信息的指针19.1，RChild20.孩子表示法，双亲表示法，长子兄弟表示法四、应用题1.解答：根据给定的边确定的树如图5-15所示。其中根结点为a；叶子结点有：d、m、n、j、k、f、l；c是结点g的双亲；a、c是结点g的祖先；j、k是结点g的孩子；m、n是结点e的子孙；e是结点d的兄弟；g、h是结点f的兄弟；结点b和n的层次号分别是2和5；树的深度为5。2.解答：度为2第127页共127页
的树有两个分支，但分支没有左右之分；一棵二叉树也有两个分支，但有左右之分，左右子树不能交换。3.解答： 略4.解答： 先序序列：ABDHIEJKCFLG中序序列：HDIBJEKALFCG后序序列：HIDJKEBLFGCA5.解答：（1）第i层上的结点数目是mi-1。（2）编号为n的结点的父结点如果存在，编号是((n-2)/m)+1。（3）编号为n的结点的第i个孩子结点如果存在，编号是(n-1)*m+i+1。（4）编号为n的结点有右兄弟的条件是(n-1)%m≠0。其右兄弟的编号是n+1。6.解答：（1）先序序列和中序序列相同的二叉树为：空树或者任一结点均无左孩子的非空二叉树；（2）中序序列和后序序列相同的二叉树为：空树或者任一结点均无右孩子的非空二叉树；（3第127页共127页
）先序序列和后序序列相同的二叉树为：空树或仅有一个结点的二叉树。7.解答：后序序列：ACDBGJKIHFE8.解答：先序序列：ABCDGEIHFJK9.解答：先根遍历：ABCDEFGHIJKLMNO后根遍历：BDEFCAHJIGKNOML森林转换成二叉树如图5-16所示。10.解答：构造而成的哈夫曼树如图5-17所示。试题及答案一、 单选题（每题2分，共20分）1.1. 对一个算法的评价，不包括如下（B）方面的内容。A．健壮性和可读性B．并行性C．正确性D．时空复杂度2.2. 在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行()。A.p->next=HL->next;HL->next=p;B.p->next=HL;HL=p;C.p->next=HL;p=HL;D.HL=p;p->next=HL;3.3. 对线性表，在下列哪种情况下应当采用链表表示？()A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变4.4. 一个栈的输入序列为123，则下列序列中不可能是栈的输出序列的是(C)第127页共127页
A.231B.321C.312D.1231.5. AOV网是一种（）。A．有向图B．无向图C．无向无环图D．有向无环图2.6. 采用开放定址法处理散列表的冲突时，其平均查找长度（）。A．低于链接法处理冲突B.高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找3.7. 若需要利用形参直接访问实参时，应将形参变量说明为（）参数。A．值B．函数C．指针D．引用4.8. 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。A．行号B．列号C．元素值D．非零元素个数5.9. 快速排序在最坏情况下的时间复杂度为（）。A．O(log2n)B．O(nlog2n)C．0(n)D．0(n2)6.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为()。A.O(n)B.O(1)C.O(log2n)D.O(n2) 二、二、 运算题（每题6分，共24分）1.1. 数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。2.2. 队列的插入操作是在队列的___尾______进行，删除操作是在队列的____首______进行。3.3. 当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是___top==0___(要超出才为满)_______________。4.4. 对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为第127页共127页
____________。1.5. 设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7，列下标j从0到3，则二维数组W的数据元素共占用＿_____＿个字节。W中第6行的元素和第4列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。2.6. 广义表A=(a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。3.7. 二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结点的度的总和是_____________。4.8. 对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的__________________。5.9. 对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_____________个，其中_______________个用于指向孩子，_________________个指针是空闲的。6.10. 若对一棵完全二叉树从0开始进行结点的编号，并按此编号把它顺序存储到一维数组A中，即编号为0的结点存储到A[0]中。其余类推，则A[i]元素的左孩子元素为________,右孩子元素为_______________，双亲元素为____________。7.11. 在线性表的散列存储中，处理冲突的常用方法有________________________和_____________________________两种。8.12. 当待排序的记录数较大，排序码较随机且对稳定性不作要求时，宜采用_______________排序；当待排序的记录数较大，存储空间允许且要求排序是稳定时，宜采用________________________排序。 一、三、 运算题（每题6分，共24分）1.1. 已知一个6´5稀疏矩阵如下所示，第127页共127页
试：（1）（1） 写出它的三元组线性表；（2）（2） 给出三元组线性表的顺序存储表示。1.2. 设有一个输入数据的序列是{46,25,78,62,12,80},试画出从空树起，逐个输入各个数据而生成的二叉搜索树。2.3. 对于图6所示的有向图若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，试写出：(1)从顶点①出发进行深度优先搜索所得到的深度优先生成树；(2)从顶点②出发进行广度优先搜索所得到的广度优先生成树；3.4. 已知一个图的顶点集V和边集E分别为：图6V={1,2,3,4,5,6,7};E={<2,1>,<3,2>,<3,6>,<4,3>,<4,5>,<4,6>,<5,1>,<5,7>,<6,1>,<6,2>,<6,5>};若存储它采用邻接表，并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的，按主教材中介绍的拓朴排序算法进行排序，试给出得到的拓朴排序的序列。 第127页共127页
一、四、 阅读算法（每题7分，共14分）1.1. intPrime(intn){inti=1;intx=(int)sqrt(n);while(++i<=x)if(n%i==0)break;if(i>x)return1;elsereturn0;}(1)(1) 指出该算法的功能；(2)(2) 该算法的时间复杂度是多少？2.2. 写出下述算法的功能：voidAJ(adjlistGL,inti,intn){QueueQ;InitQueue(Q);cout<adjvex;if(!visited[j]){cout<next;第127页共127页
}}} 一、五、 算法填空（共8分）如下为二分查找的非递归算法，试将其填写完整。IntBinsch(ElemTypeA[],intn,KeyTypeK){intlow=0;inthigh=n-1;while(low<=high){intmid=_______________________________；if(K==A[mid].key)returnmid;//查找成功，返回元素的下标elseif(K<[mid].key)______________________________________;//在左子表上继续查找else__________________________________;//在右子表上继续查找}return-1;//查找失败，返回-1} 二、六、 编写算法（共8分）HL是单链表的头指针，试写出删除头结点的算法。ElemTypeDeleFront(LNode*&HL) 参考答案一、一、 单选题（每题2分，共20分）1.B2.A3.B4.C5.D6.B7.D8.A9.D10.C二、二、 填空题（每空1分，共26分）第127页共127页
1.1. 联系图（或图结构）2.2. 尾首3.3. top==04.4. O（1）O（n）5.5. 128441086.6. 337.7. 65515132-145-2515637图7有序n-18.8. 有序序列后缀表达式（或逆波兰式）9.9. 2nn-1n+110.10. 2i+12i+2(i-1)/211.11. 开放定址法链接法12.12. 快速归并一、三、 运算题（每题6分，共24分）1.1. （1）((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7))(3分)（2）三元组线性表的顺序存储表示如图7示。2.2. 图8如图8所示。3.3. DFS：&BFS：&4.4. 拓朴排序为：4365721二、四、 阅读算法（每题7分，共14分）1.1. (1)判断n是否是素数（或质数）（2）O（）2.2. 功能为：从初始点vi出发广度优先搜索由邻接表GL所表示的图。三、五、 算法填空（8分）(low+high)/2high=mid-1low=mid+1四、六、 编写算法（8分）ElemTypeDeleFront(LNode*&HL){if(HL==NULL){cerr<<"空表"<next;ElemTypetemp=p->data;第127页共127页
deletep;returntemp;} 一、一、 单选题（每题2分，共20分）1.1. 栈和队列的共同特点是()。A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.2. 用链接方式存储的队列，在进行插入运算时().A.仅修改头指针 B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改3.3. 以下数据结构中哪一个是非线性结构？()A.队列 B.栈C.线性表 D.二叉树4.4. 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。A．688B．678C．692D．6965.5. 树最适合用来表示()。A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.6. 二叉树的第k层的结点数最多为().A．2k-1B.2K+1C.2K-1 D.2k-17.7. 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为()A.1，2，3B.9，5，2，3第127页共127页
C.9，5，3D.9，4，2，31.8. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A.O（1） B.O（n） C.O（1og2n）D.O（n2）2.9. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K%9作为散列函数，则散列地址为1的元素有（）个，A．1B．2C．3D．43.10.设有6个结点的无向图，该图至少应有()条边才能确保是一个连通图。A.5B.6C.7D.8 二、二、 填空题（每空1分，共26分）1.1. 通常从四个方面评价算法的质量：_________、_________、_________和_________。2.2. 一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。3.3. 假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为_ _________个，树的深度为___________，树的度为_________。4.4. 后缀算式923+-102/-的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式为_______________________________。5.5. 若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。6.6. 对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有_______个和________个。7.7. AOV网是一种___________________的图。8.8. 在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中，包含有________条边。第127页共127页
1.9. 假定一个线性表为(12,23,74,55,63,40)，若按Key%4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。2.10. 向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。3.11. 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复杂度为________。4.12. 在快速排序、堆排序、归并排序中，_________排序是稳定的。 一、三、 运算题（每题6分，共24分）1.1. 在如下数组A中链接存储了一个线性表，表头指针为A[0].next，试写出该线性表。A01234567data 6050789034 40next357204 12.2. 图10请画出图10的邻接矩阵和邻接表。3.3. 已知一个图的顶点集V和边集E分别为：V={1,2,3,4,5,6,7};E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25};用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。4.4. 画出向小根堆中加入数据4,2,5,8,3时，每加入一个数据后堆的变化。 二、四、 阅读算法（每题7分，共14分）1.1. LinkListmynote(LinkListL){//L是不带头结点的单链表的头指针if(L&&L->next){第127页共127页
q=L；L=L－>next；p=L；S1：while(p－>next)p=p－>next；S2：p－>next=q；q－>next=NULL；}returnL；}请回答下列问题：（1）说明语句S1的功能；（2）说明语句组S2的功能；（3）设链表表示的线性表为（a1,a2,…,an）,写出算法执行后的返回值所表示的线性表。1.2. voidABC(BTNode*BT){ifBT{ABC(BT->left);ABC(BT->right);cout<data<<"";}}该算法的功能是： 一、五、 算法填空（共8分）二叉搜索树的查找——递归算法:boolFind(BTreeNode*BST,ElemType&item){if(BST==NULL)returnfalse;//查找失败else{if(item==BST->data){item=BST->data;//查找成功return ___________;}elseif(itemdata)returnFind(______________,item);第127页共127页
elsereturnFind(_______________,item);}//if} 一、六、 编写算法（共8分）统计出单链表HL中结点的值等于给定值X的结点数。intCountX(LNode*HL,ElemTypex) 参考答案一、一、 单选题（每题2分，共20分）1.A2.D3.D4.C5.C6.D7.D8.C9.D10.A二、二、 填空题（每空1分，共26分）1.1. 正确性易读性强壮性高效率2.2. O(n)3.3. 9334.4. -134X*+2Y*3/-5.5. 2nn-1n+16.6. e2e7.7. 有向无回路8.8. n(n-1)/2n(n-1)9.9. （12，40）（）（74）（23,55，63）10.10. 增加111.11. O(log2n)O(nlog2n)12.12. 归并三、三、 运算题（每题6分，共24分）1.1. 线性表为：（78，50，40，60，34，90）2.2. 邻接矩阵：邻接表如图11所示：第127页共127页
图111.3. 用克鲁斯卡尔算法得到的最小生成树为：(1,2)3,(4,6)4,(1,3)5,(1,4)8,(2,5)10,(4,7)202.4. 见图124444422255285283452843 图12一、四、 阅读算法（每题7分，共14分）1.1. （1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a2,a3,…,an,a1）2.2. 递归地后序遍历链式存储的二叉树。二、五、 算法填空（每空2分，共8分）trueBST->leftBST->right三、六、 编写算法（8分）intCountX(LNode*HL,ElemTypex){inti=0;LNode*p=HL;//i为计数器while(p!=NULL){if(P->data==x)i++;p=p->next;}//while,出循环时i中的值即为x结点个数returni;}//CountX 第127页共127页
一、一、 单选题（每小题2分，共8分）1、1、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为()。AnBn/2C(n+1)/2D(n-1)/22、2、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行()。As→link=p→link;p→link=s;Bp→link=s;s→link=q;Cp→link=s→link;s→link=p;Dq→link=s;s→link=p;3、3、 栈的插入和删除操作在（）进行。A栈顶B栈底C任意位置D指定位置4、4、 由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A24B71C48D53二、二、 填空题（每空1分，共32分）1、1、数据的逻辑结构被分为__________、___________、________和________四种。2、2、一种抽象数据类型包括______________和_____________两个部分。3、3、在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则该线性表为_________________________________________________。a012345678 60564238 7425 4376201 datanext 4、4、在以HL第127页共127页
为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为________________和____________________。1、5、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的___________，该循环队列的最大长度为__________。2、6、当堆栈采用顺序存储结构时，栈顶元素的值可用———————表示；当堆栈采用链接存储结构时，栈顶元素的值可用_______________表示。3、7、一棵高度为5的二叉树中最少含有_________个结点，最多含有________个结点；一棵高度为5的理想平衡树中，最少含有_________个结点，最多含有_________个结点。4、8、在图的邻接表中，每个结点被称为____________，通常它包含三个域：一是_____________；二是___________；三是_____________。5、9、在一个索引文件的索引表中，每个索引项包含对应记录的_________和___________两项数据。6、10、 假定一棵树的广义表表示为A（B（C，D（E，F，G），H（I，J））），则树中所含的结点数为_________个，树的深度为_________,树的度为________,结点H的双亲结点为________,孩子结点为_______________。7、11、 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_________,整个堆排序过程的时间复杂度为________________。8、12、 在对m阶的B_树插入元素的过程中，每向一个结点插入一个索引项（叶子结点中的索引项为关键字和空指针）后，若该结点的索引项数等于______个，则必须把它分裂为_______个结点。 二、三、 运算题（每小题6分，共24分）1、1、已知一组记录的排序码为（46，79，56，38，40，80,95，24），写出对其进行快速排序的每一次划分结果。 第127页共127页
1、2、一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）=key%13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。 2、3、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。 3、4、已知一个图的顶点集V各边集G如下：V={0，1，2，3，4，5，6，7，8，9}；E={（0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3，8），（5，6），（5，8），（5，9），（6，7），（7，8），（8，9）}当它用邻接矩阵表示和邻接表表示时，分别写出从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。图深度优先序列广度优先序列邻接矩阵表示时 邻接表表示时 二、四、 阅读算法，回答问题（每小题8分，共16分） 1、假定从键盘上输入一批整数，依次为：786345309134第127页共127页
–1，请写出输出结果。#include#includeconsstintstackmaxsize=30;typedefintelemtype;structstack{elemtypestack[stackmaxsize];inttop;};#include“stack.h”Voidmain(){stacka;initstack(a);intx;cin>>x;while(x!=-1){push(a,x);cin>>x;}while(!stackempty(a))cout<voidBinTree：：unknown(BinTreeNode*t){BinTreeNode*p=t,*temp;if(p!=NULL){第127页共127页
temp=p→leftchild;p→leftchild=p→rightchild;p→rightchild=temp;unknown(p→leftchild);undnown(p→rightchild);}}该算法的功能是：________________________________ 一、五、 算法填空，在画有横线的地方填写合适的内容（10分） 对顺序存储的有序表进行二分查找的递归算法。intBinsch(ElemTypeA[],intlow,inthigh,KeyTypeK){if(low<=high){intmid=1if(K==A[mid].key)returnmid;elseif(Kdatedate)return－1；if(s1－>date>s2－>date)return1；①；②；}if(③)return－1；if(④)return1；⑤；}①②③④⑤31．阅读下面的算法LinkListmynote(LinkListL)第127页共127页
{//L是不带头结点的单链表的头指针if(L&&L->next){q=L；L=L－>next；p=L；S1：while(p－>next)p=p－>next；S2：p－>next=q；q－>next=NULL；}returnL；}请回答下列问题：（1）说明语句S1的功能；（2）说明语句组S2的功能；（3）设链表表示的线性表为（a1,a2,…,an）,写出算法执行后的返回值所表示的线性表。32．假设两个队列共享一个循环向量空间（参见右下图），其类型Queue2定义如下：typedefstruct{DateTypedata[MaxSize]；intfront[2],rear[2]；}Queue2；对于i=0或1，front[i]和rear[i]分别为第i个队列的头指针和尾指针。请对以下算法填空，实现第i个队列的入队操作。intEnQueue(Queue2*Q,inti,DateTypex){//若第i个队列不满，则元素x入队列，并返回1；否则返回0if(i<0||i>1)return0；if(Q－>rear[i]==Q－>front[①]return0；Q－>data[②]=x；Q－>rear[i]=[③];return1；}①②第127页共127页
③33．已知二叉树的存储结构为二叉链表，阅读下面算法。typedefstructnode{DateTypedata；Structnode*next；}ListNode；typedefListNode*LinkList；LinkListLeafhead=NULL；VoidInorder(BinTreeT){LinkLists；If(T){Inorder(T－>lchild)；If((!T－>lchild)&&(!T－>rchild)){s=(ListNode*)malloc(sizeof(ListNode))；s－>data=T－>data；s－>next=Leafhead；Leafhead=s；}Inorder(T－>rchild)；}}对于如下所示的二叉树 （1）画出执行上述算法后所建立的结构；第127页共127页
（2）说明该算法的功能。五、算法设计题（本题共10分）34．阅读下列函数arrange()intarrange(inta[],int1,inth,intx){//1和h分别为数据区的下界和上界inti,j,t；i=1；j=h；while(i=x)j--；while(i=x)i++；if(inext②s2=s2－>next③s2(或s2!=NULL或s2&&!s1)④s1(或s1!=NULL或s1&&!s2)⑤return031.（1）查询链表的尾结点（2）将第一个结点链接到链表的尾部，作为新的尾结点（3）返回的线性表为（a2,a3,…,an,a1）32.①(i＋1)%2(或1－i)②Q－>rear[i]③(Q－>rear[i]＋)%Maxsize33.(1)LeafheadF H G D∧（2）中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以Leafhead为头指针的逆序单链表（或按二叉树中叶子结点数据自右至左链接成一个链表）。 五、算法设计题（本题共10分）34．（1）该函数的功能是：调整整数数组a[]中的元素并返回分界值i，使所有＜x的元素均落在a[1..i]上，使所有≥x的元素均落在a[i＋1..h]上。（2）intf(intb[],intn)或intf(intb[],intn){{intp,q；intp,q；p=arrange(b,0,n－1,0)；p=arrange(b,0,n－1,1)；q=arrange(b,p+1,n－1,1)；q=arrange(b,0,p,0)；returnq－p；returnp－q；}} 一、选择题（20分）第127页共127页
1．组成数据的基本单位是（）。(A)数据项(B)数据类型(C)数据元素(D)数据变量2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（）。(A)线性结构(B)树型结构(C)图型结构(D)集合3．数组的逻辑结构不同于下列（）的逻辑结构。(A)线性表(B)栈(C)队列(D)树4．二叉树中第i(i≥1)层上的结点数最多有（）个。(A)2i(B)2i(C)2i-1(D)2i-15．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（）。(A)p->next=p->next->next(B)p=p->next(C)p=p->next->next(D)p->next=p6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（）。(A)6(B)4(C)3(D)27．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）。(A)100(B)40(C)55(D)808．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（）。(A)3(B)4(C)5(D)19．根据二叉树的定义可知二叉树共有（）种不同的形态。(A)4(B)5(C)6(D)710.10.设有以下四种排序方法，则（）的空间复杂度最大。(A)冒泡排序(B)快速排序(C)堆排序(D)希尔排序 二、填空题(30分)1.1. 设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F=____________;。第127页共127页
1.2. 设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________，在链式存储结构上实现顺序查找的平均时间复杂度为___________。2.3. 设一棵二叉树中有n个结点，则当用二叉链表作为其存储结构时，该二叉链表中共有________个指针域，__________个空指针域。3.4. 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点B，则在结点A的后面插入结点B的操作序列为______________________________________。4.5. 设无向图G中有n个顶点和e条边，则其对应的邻接表中有_________个表头结点和_________个表结点。5.6. 设无向图G中有n个顶点e条边，所有顶点的度数之和为m，则e和m有______关系。6.7. 设一棵二叉树的前序遍历序列和中序遍历序列均为ABC，则该二叉树的后序遍历序列为__________。7.8. 设一棵完全二叉树中有21个结点，如果按照从上到下、从左到右的顺序从1开始顺序编号，则编号为8的双亲结点的编号是___________，编号为8的左孩子结点的编号是_____________。8.9. 下列程序段的功能实现子串t在主串s中位置的算法，要求在下划线处填上正确语句。intindex(chars[],chart[]){i=j=0;while(inext=p->next;s->next=s5.5. n,2e6.6. m=2e7.7. CBA8.8. 4，169.9. i-j+1，010.10. n-1三、应用题1.1. 链式存储结构略，前序ABDEC，中序DBEAC，后序DEBCA。2.2. 哈夫曼树略，WPL=783.3. (18,5,16,19,21,23)，(5，16，21，19，18，23)4.4. 线性探测：链地址法：5.5. 深度：125364，广度：123456，最小生成树T的边集为E={(1，4)，(1，3)，(3，5)，(5，6)，(5,6)}四、算法设计题1.1. 设计判断单链表中结点是否关于中心对称算法。typedefstruct{ints[100];inttop;}sqstack;intlklistsymmetry(lklist*head){sqstackstack;stack.top=-1;lklist*p;for(p=head;p!=0;p=p->next){stack.top++;stack.s[stack.top]=p->data;}第127页共127页
for(p=head;p!=0;p=p->next)if(p->data==stack.s[stack.top])stack.top=stack.top-1;elsereturn(0);return(1);}1.2. 设计在链式存储结构上建立一棵二叉树的算法。typedefchardatatype;typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;voidcreatebitree(bitree*&bt){charch;scanf("%c",&ch);if(ch=="#"){bt=0;return;}bt=(bitree*)malloc(sizeof(bitree));bt->data=ch;createbitree(bt->lchild);createbitree(bt->rchild);}2.3. 设计判断一棵二叉树是否是二叉排序树的算法。intminnum=-32768,flag=1;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){if(bt!=0){inorder(bt->lchild);if(minnum>bt->key)flag=0;minnum=bt->key;inorder(bt->rchild);}} 数据结构试卷（二） 一、选择题(24分)1．下面关于线性表的叙述错误的是（）。(A)线性表采用顺序存储必须占用一片连续的存储空间(B)线性表采用链式存储不必占用一片连续的存储空间(C)线性表采用链式存储便于插入和删除操作的实现(D)线性表采用顺序存储便于插入和删除操作的实现第127页共127页
2．设哈夫曼树中的叶子结点总数为m，若用二叉链表作为存储结构，则该哈夫曼树中总共有（）个空指针域。(A)2m-1(B)2m(C)2m+1(D)4m3．设顺序循环队列Q[0：M-1]的头指针和尾指针分别为F和R，头指针F总是指向队头元素的前一位置，尾指针R总是指向队尾元素的当前位置，则该循环队列中的元素个数为（）。(A)R-F(B)F-R(C)(R-F+M)％M(D)(F-R+M)％M4．设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。(A)BADC(B)BCDA(C)CDAB(D)CBDA5．设某完全无向图中有n个顶点，则该完全无向图中有（）条边。(A)n(n-1)/2(B)n(n-1)(C)n2(D)n2-16．设某棵二叉树中有2000个结点，则该二叉树的最小高度为（）。(A)9(B)10(C)11(D)127．设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。(A)n-1(B)n(C)n+1(D)2n-18．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为（）。(A)2，3，5，8，6(B)3，2，5，8，6(C)3，2，5，6，8(D)2，3，6，5，8 二、填空题(24分)1.1. 为了能有效地应用HASH查找技术，必须解决的两个问题是____________________和__________________________。2.2. 下面程序段的功能实现数据x进栈，要求在下划线处填上正确的语句。typedefstruct{ints[100];inttop;}sqstack;voidpush(sqstack&stack,intx){if(stack.top==m-1)printf(“overflow”);else{____________________;_________________;}}3.3. 中序遍历二叉排序树所得到的序列是___________序列（填有序或无序）。4.4. 快速排序的最坏时间复杂度为___________，平均时间复杂度为__________。5.5. 设某棵二叉树中度数为0的结点数为N0，度数为1的结点数为N1，则该二叉树中度数为2的结点数为_________；若采用二叉链表作为该二叉树的存储结构，则该二叉树中共有_______个空指针域。6.6. 设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则e=_______。7.7. 设一组初始记录关键字序列为(55，63，44，38，75，80，31，56)，则利用筛选法建立的初始堆为___________________________。第127页共127页
1.8. 设某无向图G的邻接表为，则从顶点V1开始的深度优先遍历序列为___________；广度优先遍历序列为____________。 三、应用题(36分)1．1． 设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。2．2． 设指针变量p指向双向链表中结点A，指针变量q指向被插入结点B，要求给出在结点A的后面插入结点B的操作序列（设双向链表中结点的两个指针域分别为llink和rlink）。3．3． 设一组有序的记录关键字序列为(13，18，24，35，47，50，62，83，90)，查找方法用二分查找，要求计算出查找关键字62时的比较次数并计算出查找成功时的平均查找长度。4．4． 设一棵树T中边的集合为{(A，B)，(A，C)，(A，D)，(B，E)，(C，F)，(C，G)}，要求用孩子兄弟表示法（二叉链表）表示出该树的存储结构并将该树转化成对应的二叉树。5．5． 设有无向图G（如右图所示），要求给出用普里姆算法构造最小生成树所走过的边的集合。6．6． 设有一组初始记录关键字为(45，80，48，40，22，78)，要求构造一棵二叉排序树并给出构造过程。 四、算法设计题(16分)1．1． 设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。2．2． 设有两个集合A和集合B，要求设计生成集合C=A∩B的算法，其中集合A、B和C用链式存储结构表示。第127页共127页
数据结构试卷（二）参考答案 一、选择题1.D2.B3.C4.A5.A6.C7.B8.C 二、填空题1.1. 构造一个好的HASH函数，确定解决冲突的方法2.2. stack.top++，stack.s[stack.top]=x3.3. 有序4.4. O(n2)，O(nlog2n)5.5. N0-1，2N0+N16.6. d/27.7. (31，38，54，56，75，80，55，63)8.8. (1，3，4，2)，(1，3，2，4) 三、应用题1.1. (22，40，45，48，80，78)，(40，45，48，80，22，78)2.2. q->llink=p;q->rlink=p->rlink;p->rlink->llink=q;p->rlink=q;3.3. 2,ASL=91*1+2*2+3*4+4*2)=25/94.4. 树的链式存储结构略，二叉树略5.5. E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}6.6. 略 四、算法设计题1.1. 设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。voidquickpass(intr[],ints,intt){inti=s,j=t,x=r[s];while(ix)j=j-1;if(inext){for(q=hb;q!=0;q=q->next)if(q->data==p->data)break;if(q!=0){t=(lklist*)malloc(sizeof(lklist));t->data=p->data;t->next=hc;hc=t;}第127页共127页
}}第127页共127页
数据结构试卷（三） 一、选择题(30分)1．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（）。(A)线性结构(B)树型结构(C)物理结构(D)图型结构2．下面程序的时间复杂为（）for（i=1，s=0；i<=n；i++）{t=1；for(j=1；j<=i；j++)t=t*j；s=s+t；}(A)O(n)(B)O(n2)(C)O(n3)(D)O(n4)3．设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。(A)q=p->next；p->data=q->data；p->next=q->next；free(q)；(B)q=p->next；q->data=p->data；p->next=q->next；free(q)；(C)q=p->next；p->next=q->next；free(q)；(D)q=p->next；p->data=q->data；free(q)；4．设有n个待排序的记录关键字，则在堆排序中需要（）个辅助记录单元。(A)1(B)n(C)nlog2n(D)n25．设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为()。(A)10，15，14，18，20，36，40，21(B)10，15，14，18，20，40，36，21(C)10，15，14，20，18，40，36，2l(D)15，10，14，18，20，36，40，216．设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。(A)O(1)(B)O(log2n)(C)(D)O(n2)7．设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）。(A)n，e(B)e，n(C)2n，e(D)n，2e8.设某强连通图中有n个顶点，则该强连通图中至少有（）条边。(A)n(n-1)(B)n+1(C)n(D)n(n+1)9．设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（）方法可以达到此目的。(A)快速排序(B)堆排序(C)归并排序(D)插入排序10.下列四种排序中（）的空间复杂度最大。(A)插入排序(B)冒泡排序(C)堆排序(D)归并排序 二、填空殖(48分，其中最后两小题各6分)1.1. 数据的物理结构主要包括_____________和______________两种情况。2.2. 设一棵完全二叉树中有500个结点，则该二叉树的深度为__________；若用二叉链表作为该完全二叉树的存储结构，则共有___________个空指针域。3.3. 设输入序列为1、2、3，则经过栈的作用后可以得到___________种不同的输出序列。第127页共127页
1.4. 设有向图G用邻接矩阵A[n][n]作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的________，第i列上所有元素之和等于顶点i的________。2.5. 设哈夫曼树中共有n个结点，则该哈夫曼树中有________个度数为1的结点。3.6. 设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为_________。4.7. __________遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。5.8. 设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较________次就可以断定数据元素X是否在查找表中。6.9. 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为____________。7.10. 设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为____________，右孩子结点的编号为___________。8.11. 设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序结果为___________________________。9.12. 设有向图G中有向边的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，则该图的一种拓扑序列为____________________。10.13. 下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。structrecord{intkey;intothers;};inthashsqsearch(structrecordhashtable[],intk){inti,j;j=i=k%p;while(hashtable[j].key!=k&&hashtable[j].flag!=0){j=(____)%m;if(i==j)return(-1);}if(_______________________)return(j);elsereturn(-1);}11.14. 下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。typedefstructnode{intkey;structnode*lchild;structnode*rchild;}bitree;bitree*bstsearch(bitree*t,intk){if(t==0)return(0);elsewhile(t!=0)if(t->key==k)_____________;elseif(t->key>k)t=t->lchild;else_____________;} 三、算法设计题(22分)1．1． 设计在单链表中删除值相同的多余结点的算法。2．2． 设计一个求结点x在二叉树中的双亲结点算法。数据结构试卷（三）参考答案第127页共127页
一、选择题1.B2.B3.A4.A5.A6.B7.D8.C9.B10.D第3小题分析：首先用指针变量q指向结点A的后继结点B，然后将结点B的值复制到结点A中，最后删除结点B。第9小题分析：9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为O(log2n)。 二、填空题1.1. 顺序存储结构、链式存储结构2.2. 9，5013.3. 54.4. 出度，入度5.5. 06.6. e=d7.7. 中序8.8. 79.9. O(1)10.10. i/2，2i+111.11. (5，16，71，23，72，94，73)12.12. (1，4，3，2)13.13. j+1，hashtable[j].key==k14.14. return(t)，t=t->rchild第8小题分析：二分查找的过程可以用一棵二叉树来描述，该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1+log2n。 三、算法设计题1.1. 设计在单链表中删除值相同的多余结点的算法。typedefintdatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voiddelredundant(lklist*&head){lklist*p,*q,*s;for(p=head;p!=0;p=p->next){for(q=p->next,s=q;q!=0;)if(q->data==p->data){s->next=q->next;free(q);q=s->next;}else{s=q,q=q->next;}}}2.2. 设计一个求结点x在二叉树中的双亲结点算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;bitree*q[20];intr=0,f=0,flag=0;第127页共127页
voidpreorder(bitree*bt,charx){if(bt!=0&&flag==0)if(bt->data==x){flag=1;return;}else{r=(r+1)%20;q[r]=bt;preorder(bt->lchild,x);preorder(bt->rchild,x);}}voidparent(bitree*bt,charx){inti;preorder(bt,x);for(i=f+1;i<=r;i++)if(q[i]->lchild->data==x||q[i]->rchild->data)break;if(flag==0)printf("notfoundxn");elseif(i<=r)printf("%c",bt->data);elseprintf("notparent");}数据结构试卷（四） 一、选择题(30分)1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。(A)O(n)(B)O(nlog2n)(C)O(1)(D)O(n2)2．设一棵二叉树的深度为k，则该二叉树中最多有（）个结点。(A)2k-1(B)2k(C)2k-1(D)2k-13．设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（）。(A)n(B)e(C)2n(D)2e4．在二叉排序树中插入一个结点的时间复杂度为（）。(A)O(1)(B)O(n)(C)O(log2n)(D)O(n2)5．设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（）条有向边。(A)n(B)n-1(C)m(D)m-16．设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。(A)3(B)4(C)5(D)87．设用链表作为栈的存储结构则退栈操作（）。(A)必须判别栈是否为满(B)必须判别栈是否为空(C)判别栈元素的类型(D)对栈不作任何判别8．下列四种排序中（）的空间复杂度最大。(A)快速排序(B)冒泡排序(C)希尔排序(D)堆9．设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。(A)N0=N1+1(B)N0=Nl+N2(C)N0=N2+1(D)N0=2N1+l10.设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。第127页共127页
(A)log2n+1(B)log2n-1(C)log2n(D)log2(n+1) 二、填空题(42分)1．1． 设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度为_________。2．2． 设指针变量p指向双向循环链表中的结点X，则删除结点X需要执行的语句序列为_________________________________________________________（设结点中的两个指针域分别为llink和rlink）。3．3． 根据初始关键字序列(19，22，01，38，10)建立的二叉排序树的高度为____________。4．4． 深度为k的完全二叉树中最少有____________个结点。5．5． 设初始记录关键字序列为(K1，K2，…，Kn)，则用筛选法思想建堆必须从第______个元素开始进行筛选。6．6． 设哈夫曼树中共有99个结点，则该树中有_________个叶子结点；若采用二叉链表作为存储结构，则该树中有_____个空指针域。7．7． 设有一个顺序循环队列中有M个存储单元，则该循环队列中最多能够存储________个队列元素；当前实际存储________________个队列元素（设头指针F指向当前队头元素的前一个位置，尾指针指向当前队尾元素的位置）。8．8． 设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中_______个数据元素；删除第i个位置上的数据元素需要移动表中_______个元素。9．9． 设一组初始记录关键字序列为(20，18，22，16，30，19)，则以20为中轴的一趟快速排序结果为______________________________。10．10．设一组初始记录关键字序列为(20，18，22，16，30，19)，则根据这些初始关键字序列建成的初始堆为________________________。11．11．设某无向图G中有n个顶点，用邻接矩阵A作为该图的存储结构，则顶点i和顶点j互为邻接点的条件是______________________。12．12．设无向图对应的邻接矩阵为A，则A中第i上非0元素的个数_________第i列上非0元素的个数（填等于，大于或小于）。13．13．设前序遍历某二叉树的序列为ABCD，中序遍历该二叉树的序列为BADC，则后序遍历该二叉树的序列为_____________。14．14．设散列函数H(k)=kmodp，解决冲突的方法为链地址法。要求在下列算法划线处填上正确的语句完成在散列表hashtalbe中查找关键字值等于k的结点，成功时返回指向关键字的指针，不成功时返回标志0。typedefstructnode{intkey;structnode*next;}lklist;voidcreatelkhash(lklist*hashtable[]){inti,k;lklist*s;for(i=0;ikey=a[i];第127页共127页
k=a[i]%p;s->next=hashtable[k];_______________________;}} 三、算法设计题(28分)1．1． 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。2.2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。3.3. 在链式存储结构上建立一棵二叉排序树。数据结构试卷（四）参考答案 一、选择题1．C2．D3．D4．B5．C6．A7．B8．A9．C10．A 二、填空题1.1. O(n2)，O(nlog2n)2.2. p>llink->rlink=p->rlink;p->rlink->llink=p->rlink3.3. 34.4. 2k-15.5. n/26.6. 50，517.7. m-1，(R-F+M)%M8.8. n+1-i，n-i9.9. (19，18，16，20，30，22)10.10. (16，18，19，20，32，22)11.11. A[i][j]=112.12. 等于13.13. BDCA14.14. hashtable[i]=0，hashtable[k]=s 三、算法设计题1.1. 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。typedefchardatatype;typedefstructnode{datatypedata;structnode*next;}lklist;voidsplit(lklist*head,lklist*&ha,lklist*&hb,lklist*&hc){lklist*p;ha=0,hb=0,hc=0;for(p=head;p!=0;p=head){head=p->next;p->next=0;第127页共127页
if(p->data>="A"&&p->data<="Z"){p->next=ha;ha=p;}elseif(p->data>="0"&&p->data<="9"){p->next=hb;hb=p;}else{p->next=hc;hc=p;}}}1.2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。typedefstructnode{intdata;structnode*lchild,*rchild;}bitree;voidswapbitree(bitree*bt){bitree*p;if(bt==0)return;swapbitree(bt->lchild);swapbitree(bt->rchild);p=bt->lchild;bt->lchild=bt->rchild;bt->rchild=p;}2.3. 在链式存储结构上建立一棵二叉排序树。#definen10typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidbstinsert(bitree*&bt,intkey){if(bt==0){bt=(bitree*)malloc(sizeof(bitree));bt->key=key;bt->lchild=bt->rchild=0;}elseif(bt->key>key)bstinsert(bt->lchild,key);elsebstinsert(bt->rchild,key);}voidcreatebsttree(bitree*&bt){inti;for(i=1;i<=n;i++)bstinsert(bt,random(100));}数据结构试卷（五） 一、选择题(30分)1．数据的最小单位是（）。(A)数据项(B)数据类型(C)数据元素(D)数据变量2．设一组初始记录关键字序列为(50，40，95，20，15，70，60，45)，则以增量d=4的一趟希尔排序结束后前4条记录关键字为（）。(A)40，50，20，95(B)15，40，60，20(C)15，20，40，45(D)45，40，15，203．设一组初始记录关键字序列为(25，50，15，35，80，85，20，40，36，70)，其中含有5个长度为2的有序子表，则用归并排序的方法对该记录关键字序列进行一趟归并后的结果为（）。(A)15，25，35，50，20，40，80，85，36，70(B)15，25，35，50，80，20，85，40，70，36(C)15，25，35，50，80，85，20，36，40，70(D)15，25，35，50，80，20，36，40，70，854．函数substr(“DATASTRUCTURE”，5，9)的返回值为（）。第127页共127页
(A)“STRUCTURE”(B)“DATA”(C)“ASTRUCTUR”(D)“DATASTRUCTURE”5．设一个有序的单链表中有n个结点，现要求插入一个新结点后使得单链表仍然保持有序，则该操作的时间复杂度为（）。(A)O(log2n)(B)O(1)(C)O(n2)(D)O(n)6．设一棵m叉树中度数为0的结点数为N0，度数为1的结点数为Nl，……，度数为m的结点数为Nm，则N0=（）。(A)Nl+N2+……+Nm(B)l+N2+2N3+3N4+……+(m-1)Nm(C)N2+2N3+3N4+……+(m-1)Nm(D)2Nl+3N2+……+(m+1)Nm7．设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。(A)25(B)10(C)7(D)18．设连通图G中的边集E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发可以得到一种深度优先遍历的顶点序列为（）。(A)abedfc(B)acfebd(C)aebdfc(D)aedfcb9．设输入序列是1、2、3、……、n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（）。(A)n-i(B)n-1-i(C)n+1-i(D)不能确定10设一组初始记录关键字序列为(45，80，55，40，42，85)，则以第一个记录关键字45为基准而得到一趟快速排序的结果是（）。(A)40，42，45，55，80，83(B)42，40，45，80，85，88(C)42，40，45，55，80，85(D)42，40，45，85，55，80 二、填空题(共30分)1.1. 设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是____________________。2.2. 在图的邻接表中用顺序存储结构存储表头结点的优点是____________________。3.3. 设有一个n阶的下三角矩阵A，如果按照行的顺序将下三角矩阵中的元素（包括对角线上元素）存放在n(n+1)个连续的存储单元中，则A[i][j]与A[0][0]之间有_______个数据元素。4.4. 栈的插入和删除只能在栈的栈顶进行，后进栈的元素必定先出栈，所以又把栈称为__________表；队列的插入和删除运算分别在队列的两端进行，先进队列的元素必定先出队列，所以又把队列称为_________表。5.5. 设一棵完全二叉树的顺序存储结构中存储数据元素为ABCDEF，则该二叉树的前序遍历序列为___________，中序遍历序列为___________，后序遍历序列为___________。6.6. 设一棵完全二叉树有128个结点，则该完全二叉树的深度为________，有__________个叶子结点。7.7. 设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素个数之和等于顶点i的________，第i列中所有非零元素个数之和等于顶点i的__________。第127页共127页
1.8. 设一组初始记录关键字序列(k1，k2，……，kn)是堆，则对i=1，2，…，n/2而言满足的条件为_______________________________。2.9. 下面程序段的功能是实现冒泡排序算法，请在下划线处填上正确的语句。voidbubble(intr[n]){for(i=1;i<=n-1;i++){for(exchange=0,j=0;j<_____________;j++)if(r[j]>r[j+1]){temp=r[j+1];______________;r[j]=temp;exchange=1;}if(exchange==0)return；}}3.10. 下面程序段的功能是实现二分查找算法，请在下划线处填上正确的语句。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low<=high){________________________________;if(r[mid].key==k)return(mid+1);elseif(____________)high=mid-1;elselow=mid+1;}return(0);}三、应用题(24分)1.1. 设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列。2.2. 设无向图G（如右图所示），给出该图的最小生成树上边的集合并计算最小生成树各边上的权值之和。3.3. 设一组初始记录关键字序列为(15，17，18，22，35，51，60)，要求计算出成功查找时的平均查找长度。4.4. 设散列表的长度为8，散列函数H(k)=kmod7，初始记录关键字序列为(25，31，8，27，13，68)，要求分别计算出用线性探测法和链地址法作为解决冲突方法的平均查找长度。 四、算法设计题(16分)1．1． 设计判断两个二叉树是否相同的算法。2．2． 设计两个有序单链表的合并排序算法。 数据结构试卷（五）参考答案第127页共127页
一、选择题1．A2．B3．A4．A5．D6．B7．B8．B9．C10．C 二、填空题1.1. top1+1=top22.2. 可以随机访问到任一个顶点的简单链表3.3. i(i+1)/2+j-14.4. FILO，FIFO5.5. ABDECF，DBEAFC，DEBFCA6.6. 8，647.7. 出度，入度8.8. ki<=k2i&&ki<=k2i+19.9. n-i，r[j+1]=r[j]10.10. mid=(low+high)/2，r[mid].key>k 三、应用题1.1. DEBCA2.2. E={(1,5),(5,2),(5,3),(3,4)},W=103.3. ASL=(1*1+2*2+3*4)/7=17/74.4. ASL1=7/6，ASL2=4/3四、算法设计题1.1. 设计判断两个二叉树是否相同的算法。typedefstructnode{datatypedata;structnode*lchild,*rchild;}bitree;intjudgebitree(bitree*bt1,bitree*bt2){if(bt1==0&&bt2==0)return(1);elseif(bt1==0||bt2==0||bt1->data!=bt2->data)return(0);elsereturn(judgebitree(bt1->lchild,bt2->lchild)*judgebitree(bt1->rchild,bt2->rchild));}2.2. 设计两个有序单链表的合并排序算法。voidmergelklist(lklist*ha,lklist*hb,lklist*&hc){lklist*s=hc=0;while(ha!=0&&hb!=0)if(ha->datadata){if(s==0)hc=s=ha;else{s->next=ha;s=ha;};ha=ha->next;}else{if(s==0)hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;}if(ha==0)s->next=hb;elses->next=ha;}第127页共127页
数据结构试卷（六） 一、选择题(30分)1．设一组权值集合W={2，3，4，5，6}，则由该权值集合构造的哈夫曼树中带权路径长度之和为（）。(A)20(B)30(C)40(D)452．执行一趟快速排序能够得到的序列是（）。(A)[41，12，34，45，27]55[72，63](B)[45，34，12，41]55[72，63，27](C)[63，12，34，45，27]55[41，72](D)[12，27，45，41]55[34，63，72]3．设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是（）。(A)head==0(B)head->next==0(C)head->next==head(D)head!=04．时间复杂度不受数据初始状态影响而恒为O(nlog2n)的是（）。(A)堆排序(B)冒泡排序(C)希尔排序(D)快速排序5．设二叉树的先序遍历序列和后序遍历序列正好相反，则该二叉树满足的条件是（）。(A)空或只有一个结点(B)高度等于其结点数(C)任一结点无左孩子(D)任一结点无右孩子6．一趟排序结束后不一定能够选出一个元素放在其最终位置上的是（）。(A)堆排序(B)冒泡排序(C)快速排序(D)希尔排序7．设某棵三叉树中有40个结点，则该三叉树的最小高度为（）。(A)3(B)4(C)5(D)68．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。(A)O(n)(B)O(n2)(C)O(n1/2)(D)O(1og2n)9．二路归并排序的时间复杂度为（）。(A)O(n)(B)O(n2)(C)O(nlog2n)(D)O(1og2n)10.深度为k的完全二叉树中最少有（）个结点。(A)2k-1-1(B)2k-1(C)2k-1+1(D)2k-111.设指针变量front表示链式队列的队头指针，指针变量rear表示链式队列的队尾指针，指针变量s指向将要入队列的结点X，则入队列的操作序列为（）。(A)front->next=s；front=s；(B)s->next=rear；rear=s；(C)rear->next=s；rear=s；(D)s->next=front；front=s；12.设某无向图中有n个顶点e条边，则建立该图邻接表的时间复杂度为（）。(A)O(n+e)(B)O(n2)(C)O(ne)(D)O(n3)13.设某哈夫曼树中有199个结点，则该哈夫曼树中有（）个叶子结点。(A)99(B)100(C)101(D)10214.设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。(A)O(n)(B)O(n2)(C)O(nlog2n)(D)O(1og2n)第127页共127页
15.设用邻接矩阵A表示有向图G的存储结构，则有向图G中顶点i的入度为（）。(A)第i行非0元素的个数之和(B)第i列非0元素的个数之和(C)第i行0元素的个数之和(D)第i列0元素的个数之和 二、判断题(20分)1．调用一次深度优先遍历可以访问到图中的所有顶点。（）2．分块查找的平均查找长度不仅与索引表的长度有关，而且与块的长度有关。（）3．冒泡排序在初始关键字序列为逆序的情况下执行的交换次数最多。（）4．满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。（）5．设一棵二叉树的先序序列和后序序列，则能够唯一确定出该二叉树的形状。（）6．层次遍历初始堆可以得到一个有序的序列。（）7．设一棵树T可以转化成二叉树BT，则二叉树BT中一定没有右子树。（）8．线性表的顺序存储结构比链式存储结构更好。（）9．中序遍历二叉排序树可以得到一个有序的序列。（）10.快速排序是排序算法中平均性能最好的一种排序。（） 三、填空题(30分)1．for(i=1，t=1，s=0；i<=n；i++){t=t*i；s=s+t；}的时间复杂度为_________。2．设指针变量p指向单链表中结点A，指针变量s指向被插入的新结点X，则进行插入操作的语句序列为__________________________（设结点的指针域为next）。3．设有向图G的二元组形式表示为G=（D，R），D={1，2，3，4，5}，R={r}，r={<1,2>，<2,4>，<4,5>，<1,3>，<3,2>，<3,5>}，则给出该图的一种拓扑排序序列__________。4．设无向图G中有n个顶点，则该无向图中每个顶点的度数最多是_________。5．设二叉树中度数为0的结点数为50，度数为1的结点数为30，则该二叉树中总共有_______个结点数。6．设F和R分别表示顺序循环队列的头指针和尾指针，则判断该循环队列为空的条件为_____________________。7．设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子结点的条件是_____________________________________________。8．简单选择排序和直接插入排序算法的平均时间复杂度为___________。9．快速排序算法的空间复杂度平均情况下为__________，最坏的情况下为__________。10.散列表中解决冲突的两种方法是_____________和_____________。 四、算法设计题(20分)１．１． 设计在顺序有序表中实现二分查找的算法。２．２． 设计判断二叉树是否为二叉排序树的算法。３．３． 在链式存储结构上设计直接插入排序算法第127页共127页
数据结构试卷（六）参考答案 一、选择题1．D2．A3．A4．A5．D6．D7．B8．A9．C10．B11．C12．A13．B14．D15．B 二、判断题1．错2．对3．对4．对5．错6．错7．对8．错9．对10．对 三、填空题1.1. O(n)2.2. s->next=p->next;p->next=s3.3. (1，3，2，4，5)4.4. n-15.5. 1296.6. F==R7.7. p->lchild==0&&p->rchild==08.8. O(n2)9.9. O(nlog2n)，O(n)10.10. 开放定址法，链地址法 四、算法设计题1.1. 设计在顺序有序表中实现二分查找的算法。structrecord{intkey;intothers;};intbisearch(structrecordr[],intk){intlow=0,mid,high=n-1;while(low<=high){mid=(low+high)/2;if(r[mid].key==k)return(mid+1);elseif(r[mid].key>k)high=mid-1;elselow=mid+1;}return(0);}2.2. 设计判断二叉树是否为二叉排序树的算法。intminnum=-32768,flag=1;typedefstructnode{intkey;structnode*lchild,*rchild;}bitree;voidinorder(bitree*bt){if(bt!=0){inorder(bt->lchild);if(minnum>bt->key)flag=0;minnum=bt->key;inorder(bt->rchild);}}第127页共127页
1.3. 在链式存储结构上设计直接插入排序算法voidstraightinsertsort(lklist*&head){lklist*s,*p,*q;intt;if(head==0||head->next==0)return;elsefor(q=head,p=head->next;p!=0;p=q->next){for(s=head;s!=q->next;s=s->next)if(s->data>p->data)break;if(s==q->next)q=p;else{q->next=p->next;p->next=s->next;s->next=p;t=p->data;p->data=s->data;s->data=t;}}}数据结构试卷（七） 一、选择题(30分)1．设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。(A)2n(B)n(C)n/2(D)n(n-1)2．设无向图G中有n个顶点，则该无向图的最小生成树上有（）条边。(A)n(B)n-1(C)2n(D)2n-13．设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是（）。(A)40，42，60，55，80，85(B)42，45，55，60，85，80(C)42，40，55，60，80，85(D)42，40，60，85，55，804．（）二叉排序树可以得到一个从小到大的有序序列。(A)先序遍历(B)中序遍历(C)后序遍历(D)层次遍历5．设按照从上到下、从左到右的顺序从1开始对完全二叉树进行顺序编号，则编号为i结点的左孩子结点的编号为（）。(A)2i+1(B)2i(C)i/2(D)2i-16．程序段s=i=0；do{i=i+1；s=s+i；}while(i<=n)；的时间复杂度为（）。(A)O(n)(B)O(nlog2n)(C)O(n2)(D)O(n3/2)7．设带有头结点的单向循环链表的头指针变量为head，则其判空条件是（）。(A)head==0(B)head->next==0(C)head->next==head(D)head!=08．设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。(A)20(B)256(C)512(D)10249．设一组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利用二分法查找关键字90需要比较的关键字个数为（）。(A)1(B)2(C)3(D)410.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为（）。(A)top=top+1;(B)top=top-1;(C)top->next=top;(D)top=top->next; 二、判断题(20分)第127页共127页
1．不论是入队列操作还是入栈操作，在顺序存储结构上都需要考虑“溢出”情况。（）2．当向二叉排序树中插入一个结点，则该结点一定成为叶子结点。（）3．设某堆中有n个结点，则在该堆中插入一个新结点的时间复杂度为O(log2n)。（）4．完全二叉树中的叶子结点只可能在最后两层中出现。（）5．哈夫曼树中没有度数为1的结点。（）6．对连通图进行深度优先遍历可以访问到该图中的所有顶点。（）7．先序遍历一棵二叉排序树得到的结点序列不一定是有序的序列。（）8．由树转化成二叉树，该二叉树的右子树不一定为空。（）9．线性表中的所有元素都有一个前驱元素和后继元素。（）10.带权无向图的最小生成树是唯一的。（） 三、填空题(30分)1.1. 设指针变量p指向双向链表中的结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为_________=p；s->right=p->right；__________=s；p->right->left=s；（设结点中的两个指针域分别为left和right）。2.2. 设完全有向图中有n个顶点，则该完全有向图中共有________条有向条；设完全无向图中有n个顶点，则该完全无向图中共有________条无向边。3.3. 设关键字序列为(Kl，K2，…，Kn)，则用筛选法建初始堆必须从第______个元素开始进行筛选。4.4. 解决散列表冲突的两种方法是________________和__________________。5.5. 设一棵三叉树中有50个度数为0的结点，21个度数为2的结点，则该二叉树中度数为3的结点数有______个。6.6. 高度为h的完全二叉树中最少有________个结点，最多有________个结点。7.7. 设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟直接插入排序结束后的结果的是__________________________________。8.8. 设有一组初始关键字序列为(24，35，12，27，18，26)，则第3趟简单选择排序结束后的结果的是__________________________________。9.9. 设一棵二叉树的前序序列为ABC，则有______________种不同的二叉树可以得到这种序列。10.10. 下面程序段的功能是实现一趟快速排序，请在下划线处填上正确的语句。structrecord{intkey;datatypeothers;};voidquickpass(structrecordr[],ints,intt,int&i){intj=t;structrecordx=r[s];i=s;while(ix.key)j=j-1;if(ileft=p，p->right2.2. n(n-1)，n(n-1)/23.3. n/24.4. 开放定址法，链地址法5.5. 146.6. 2h-1，2h-17.7. (12，24，35，27，18，26)8.8. (12，18，24，27，35，26)9.9. 510.10. inext==0)return;for(q=head;q!=0;q=q->next){min=q->data;s=q;for(p=q->next;p!=0;p=p->next)if(min>p->data){min=p->data;s=p;}if(s!=q){t=s->data;s->data=q->data;q->data=t;}}}第127页共127页
1.2. 设计在顺序存储结构上实现求子串算法。voidsubstring(chars[],longstart,longcount,chart[]){longi,j,length=strlen(s);if(start<1||start>length)printf("Thecopypositioniswrong");elseif(start+count-1>length)printf("Toocharacterstobecopied");else{for(i=start-1,j=0;ikey==x)return;elseif(bt->key>x)level(bt->lchild,x);elselevel(bt->rchild,x);}}数据结构试卷（八） 一、选择题(30分)1.1. 字符串的长度是指（）。(A)串中不同字符的个数(B)串中不同字母的个数(C)串中所含字符的个数(D)串中不同数字的个数2.2. 建立一个长度为n的有序单链表的时间复杂度为（）(A)O(n)(B)O(1)(C)O(n2)(D)O(log2n)3.3. 两个字符串相等的充要条件是（）。(A)两个字符串的长度相等(B)两个字符串中对应位置上的字符相等(C)同时具备(A)和(B)两个条件(D)以上答案都不对4.4. 设某散列表的长度为100，散列函数H(k)=k%P，则P通常情况下最好选择（）。(A)99(B)97(C)91(D)935.5. 在二叉排序树中插入一个关键字值的平均时间复杂度为（）。(A)O(n)(B)O(1og2n)(C)O(nlog2n)(D)O(n2)6.6. 设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为()。(A)A[1]，A[2]，A[3]，A[4](B)A[1]，A[14]，A[7]，A[4](C)A[7]，A[3]，A[5]，A[4](D)A[7]，A[5]，A[3]，A[4]7.7. 设一棵完全二叉树中有65个结点，则该完全二叉树的深度为（）。(A)8(B)7(C)6(D)58.8. 设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点，则该三叉链权中有（）个度数为0的结点。(A)5(B)6(C)7(D)8第127页共127页
1.9. 设无向图G中的边的集合E={(a，b)，(a，e)，(a，c)，(b，e)，(e，d)，(d，f)，(f，c)}，则从顶点a出发进行深度优先遍历可以得到的一种顶点序列为（）。(A)aedfcb(B)acfebd(C)aebcfd(D)aedfbc2.10. 队列是一种（）的线性表。(A)先进先出(B)先进后出(C)只能插入(D)只能删除 二、判断题(20分)1.1. 如果两个关键字的值不等但哈希函数值相等，则称这两个关键字为同义词。（）2.2. 设初始记录关键字基本有序，则快速排序算法的时间复杂度为O(nlog2n)。（）3.3. 分块查找的基本思想是首先在索引表中进行查找，以便确定给定的关键字可能存在的块号，然后再在相应的块内进行顺序查找。（）4.4. 二维数组和多维数组均不是特殊的线性结构。（）5.5. 向二叉排序树中插入一个结点需要比较的次数可能大于该二叉树的高度。（）6.6. 如果某个有向图的邻接表中第i条单链表为空，则第i个顶点的出度为零。（）7.7. 非空的双向循环链表中任何结点的前驱指针均不为空。（）8.8. 不论线性表采用顺序存储结构还是链式存储结构，删除值为X的结点的时间复杂度均为O(n)。（）9.9. 图的深度优先遍历算法中需要设置一个标志数组，以便区分图中的每个顶点是否被访问过。（）10.10. 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非0元素。（） 三、填空题(30分)1．1． 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则以d=4为增量的一趟希尔排序结束后的结果为_____________________________。2．2． 下面程序段的功能是实现在二叉排序树中插入一个新结点，请在下划线处填上正确的内容。typedefstructnode{intdata;structnode*lchild;structnode*rchild;}bitree;voidbstinsert(bitree*&t,intk){if(t==0){____________________________;t->data=k;t->lchild=t->rchild=0;}elseif(t->data>k)bstinsert(t->lchild,k);else__________________________;}3．3． 设指针变量p指向单链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X需要执行的语句序列：s->next=p->next;_________________;。4．4． 设指针变量head指向双向链表中的头结点，指针变量p指向双向链表中的第一个结点，则指针变量p和指针变量head之间的关系是第127页共127页
p=_________和head=__________（设结点中的两个指针域分别为llink和rlink）。1．5． 设某棵二叉树的中序遍历序列为ABCD，后序遍历序列为BADC，则其前序遍历序列为__________。2．6． 完全二叉树中第5层上最少有__________个结点，最多有_________个结点。3．7． 设有向图中不存在有向边，则其对应的邻接矩阵A中的数组元素A[i][j]的值等于____________。4．8． 设一组初始记录关键字序列为(49，38，65，97，76，13，27，50)，则第4趟直接选择排序结束后的结果为_____________________________。5．9． 设连通图G中有n个顶点e条边，则对应的最小生成树上有___________条边。6．10． 设有一组初始记录关键字序列为(50，16，23，68，94，70，73)，则将它们调整成初始堆只需把16与___________相互交换即可。 四、算法设计题(20分)1.1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。2.2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。 数据结构试卷（八）参考答案 一、选择题1．C2．C3．C4．B5．B6．C7．B8．C9．A10．A 二、判断题1．对2．错3．对4．错5．错6．对7．对8．对9．对10．对 三、填空题1.1. (49，13，27，50，76，38，65，97)2.2. t=(bitree*)malloc(sizeof(bitree))，bstinsert(t->rchild,k)3.3. p->next=s4.4. head->rlink，p->llink5.5. CABD6.6. 1，167.7. 08.8. (13，27，38，50，76，49，65，97)9.9. n-110.10. 50 四、算法设计题1.1. 设计一个在链式存储结构上统计二叉树中结点个数的算法。第127页共127页
voidcountnode(bitree*bt,int&count){if(bt!=0){count++;countnode(bt->lchild,count);countnode(bt->rchild,count);}}1.2. 设计一个算法将无向图的邻接矩阵转为对应邻接表的算法。typedefstruct{intvertex[m];intedge[m][m];}gadjmatrix;typedefstructnode1{intinfo;intadjvertex;structnode1*nextarc;}glinklistnode;typedefstructnode2{intvertexinfo;glinklistnode*firstarc;}glinkheadnode;voidadjmatrixtoadjlist(gadjmatrixg1[],glinkheadnodeg2[]){inti,j;glinklistnode*p;for(i=0;i<=n-1;i++)g2[i].firstarc=0;for(i=0;i<=n-1;i++)for(j=0;j<=n-1;j++)if(g1.edge[i][j]==1){p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjvertex=j;p->nextarc=g[i].firstarc;g[i].firstarc=p;p=(glinklistnode*)malloc(sizeof(glinklistnode));p->adjvertex=i;p->nextarc=g[j].firstarc;g[j].firstarc=p;}}数据结构试卷（九） 一、选择题(30分)1．下列程序段的时间复杂度为（）。for(i=0；iright=s；s->left=p；p->right->left=s；s->right=p->right；(B)s->left=p；s->right=p->right；p->right=s；p->right->left=s；(C)p->right=s；p->right->left=s；s->left=p；s->right=p->right；(D)s->left=p；s->right=p->right；p->right->left=s；p->right=s；第127页共127页
6．下列各种排序算法中平均时间复杂度为O(n2)是（）。(A)快速排序(B)堆排序(C)归并排序(D)冒泡排序7．设输入序列1、2、3、…、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是（）。(A)n-i(B)n-1-i(C)n+l-i(D)不能确定8．设散列表中有m个存储单元，散列函数H(key)=key%p，则p最好选择（）。(A)小于等于m的最大奇数(B)小于等于m的最大素数(C)小于等于m的最大偶数(D)小于等于m的最大合数9．设在一棵度数为3的树中，度数为3的结点数有2个，度数为2的结点数有1个，度数为1的结点数有2个，那么度数为0的结点数有（）个。(A)4(B)5(C)6(D)710.设完全无向图中有n个顶点，则该完全无向图中有（）条边。(A)n(n-1)/2(B)n(n-1)(C)n(n+1)/2(D)(n-1)/211.设顺序表的长度为n，则顺序查找的平均比较次数为（）。(A)n(B)n/2(C)(n+1)/2(D)(n-1)/212.设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。(A)1(B)2(C)3(D)413.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为（）。(A)6(B)11(C)5(D)6.514.设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则下列属于该有向图G的一种拓扑排序序列的是（）。(A)1，2，3，4(B)2，3，4，1(C)1，4，2，3(D)1，2，4，315.设有一组初始记录关键字序列为(34，76，45，18，26，54，92)，则由这组记录关键字生成的二叉排序树的深度为（）。(A)4(B)5(C)6(D)7二、填空题(30分)1．1． 设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前面插入结点X时的操作序列为：1)s->next=___________；2)p->next=s；3)t=p->data；4)p->data=___________；5)s->data=t；2．2． 设某棵完全二叉树中有100个结点，则该二叉树中有______________个叶子结点。3．3． 设某顺序循环队列中有m个元素，且规定队头指针F指向队头元素的前一个位置，队尾指针R指向队尾元素的当前位置，则该循环队列中最多存储_______队列元素。4．4． 对一组初始关键字序列（40，50，95，20，15，70，60，45，10）进行冒泡排序，则第一趟需要进行相邻记录的比较的次数为__________，在整个排序过程中最多需要进行__________趟排序才可以完成。5．5． 在堆排序和快速排序中，如果从平均情况下排序的速度最快的角度来考虑应最好选择_________排序，如果从节省存储空间的角度来考虑则最好选择________排序。第127页共127页
1．6． 设一组初始记录关键字序列为(20，12，42，31，18，14，28)，则根据这些记录关键字构造的二叉排序树的平均查找长度是_______________________________。2．7． 设一棵二叉树的中序遍历序列为BDCA，后序遍历序列为DBAC，则这棵二叉树的前序序列为____________________。3．8． 设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为7、19、2、6、32、3、21、10，根据这些频率作为权值构造哈夫曼树，则这棵哈夫曼树的高度为________________。4．9． 设一组记录关键字序列为(80，70，33，65，24，56，48)，则用筛选法建成的初始堆为_______________________。5．10． 设无向图G（如右图所示），则其最小生成树上所有边的权值之和为_________________。 三、判断题(20分)1．1． 有向图的邻接表和逆邻接表中表结点的个数不一定相等。()2．2． 对链表进行插入和删除操作时不必移动链表中结点。()3．3． 子串“ABC”在主串“AABCABCD”中的位置为2。()4．4． 若一个叶子结点是某二叉树的中序遍历序列的最后一个结点，则它必是该二叉树的先序遍历序列中的最后一个结点。()5．5． 希尔排序算法的时间复杂度为O(n2)。()6．6． 用邻接矩阵作为图的存储结构时，则其所占用的存储空间与图中顶点数无关而与图中边数有关。()7．7． 中序遍历一棵二叉排序树可以得到一个有序的序列。()8．8． 入栈操作和入队列操作在链式存储结构上实现时不需要考虑栈溢出的情况。()9．9． 顺序表查找指的是在顺序存储结构上进行查找。（）10．10．堆是完全二叉树，完全二叉树不一定是堆。（） 五、算法设计题(20分)1．1． 设计计算二叉树中所有结点值之和的算法。2．2． 设计将所有奇数移到所有偶数之前的算法。3．3． 设计判断单链表中元素是否是递增的算法。 数据结构试卷（九）参考答案 一、选择题1．A2．A3．A4．C5．D6．D7．C8．B9．C10．A11．C12．C13．D14．A15．A 二、填空题第127页共127页
1.1. p->next，s->data2.2. 503.3. m-14.4. 6，85.5. 快速，堆6.6. 19/77.7. CBDA8.8. 69.9. (24，65，33，80，70，56，48)10.10. 8 三、判断题1．错2．对3．对4．对5．错6．错7．对8．对9．错10．对四、算法设计题1．1． 设计计算二叉树中所有结点值之和的算法。voidsum(bitree*bt,int&s){if(bt!=0){s=s+bt->data;sum(bt->lchild,s);sum(bt->rchild,s);}}2．2． 设计将所有奇数移到所有偶数之前的算法。voidquickpass(intr[],ints,intt){inti=s,j=t,x=r[s];while(inext==0)return(1);elsefor(q=head,p=head->next;p!=0;q=p,p=p->next)if(q->data>p->data)return(0);return(1);}数据结构试卷（十） 一、选择题(24分)1．下列程序段的时间复杂度为（）。i=0，s=0；while(snext=p->next；p->next=-s；(B)q->next=s；s->next=p；(C)p->next=s->next；s->next=p；(D)p->next=s；s->next=q；4．设输入序列为1、2、3、4、5、6，则通过栈的作用后可以得到的输出序列为（）。(A)5，3，4，6，1，2(B)3，2，5，6，4，1(C)3，1，2，5，4，6(D)1，5，4，6，2，35．设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（）。(A)10(B)19(C)28(D)556．设一棵m叉树中有N1个度数为1的结点，N2个度数为2的结点，……，Nm个度数为m的结点，则该树中共有（）个叶子结点。(A)(B)(C)(D)7.二叉排序树中左子树上所有结点的值均（）根结点的值。(A)<(B)>(C)=(D)!=8.设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（）。(A)129(B)219(C)189(D)2299.设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做（）次线性探测。(A)n2(B)n(n+1)(C)n(n+1)/2(D)n(n-1)/210.设某棵二叉树中只有度数为0和度数为2的结点且度数为0的结点数为n，则这棵二叉中共有（）个结点。(A)2n(B)n+l(C)2n-1(D)2n+l11.设一组初始记录关键字的长度为8，则最多经过（）趟插入排序可以得到有序序列。(A)6(B)7(C)8(D)912.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是（）。(A)F，H，C，D，P，A，M，Q，R，S，Y，X(B)P，A，C，S，Q，D，F，X，R，H，M，Y(C)A，D，C，R，F，Q，M，S，Y，P，H，X(D)H，C，Q，P，A，M，S，R，D，F，X，Y第127页共127页
二、填空题(48分，其中最后两小题各6分)1.1. 设需要对5个不同的记录关键字进行排序，则至少需要比较_____________次，至多需要比较_____________次。2.2. 快速排序算法的平均时间复杂度为____________，直接插入排序算法的平均时间复杂度为___________。3.3. 设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较_________次。4.4. 设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有_________个，比较两次查找成功有结点数有_________个。5.5. 设一棵m叉树脂的结点数为n，用多重链表表示其存储结构，则该树中有_________个空指针域。6.6. 设指针变量p指向单链表中结点A，则删除结点A的语句序列为：q=p->next；p->data=q->data；p->next=___________；feee(q)；7.7. 数据结构从逻辑上划分为三种基本类型：___________、__________和___________。8.8. 设无向图G中有n个顶点e条边，则用邻接矩阵作为图的存储结构进行深度优先或广度优先遍历时的时间复杂度为_________；用邻接表作为图的存储结构进行深度优先或广度优先遍历的时间复杂度为_________。9.9. 设散列表的长度为8，散列函数H(k)=k%7，用线性探测法解决冲突，则根据一组初始关键字序列(8，15，16，22，30，32)构造出的散列表的平均查找长度是________。10.10. 设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟冒泡排序结束后的结果为_____________________。11.11. 设一组初始关键字序列为(38，65，97，76，13，27，10)，则第3趟简单选择排序后的结果为______________________。12.12. 设有向图G中的有向边的集合E={<1，2>，<2，3>，<1，4>，<4，5>，<5，3>，<4，6>，<6，5>}，则该图的一个拓扑序列为_________________________。13.13. 下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。typedefstructnode{intdata;structnode*lchild;________________;}bitree;voidcreatebitree(bitree*&bt){scanf(“%c”,&ch);if(ch=="#")___________;else{bt=(bitree*)malloc(sizeof(bitree));bt->data=ch;________;createbitree(bt->rchild);}}14.14. 下面程序段的功能是利用从尾部插入的方法建立单链表的算法，请在下划线处填上正确的内容。typedefstructnode{intdata;structnode*next;}lklist;voidlklistcreate(_____________*&head){第127页共127页
for(i=1;i<=n;i++){p=(lklist*)malloc(sizeof(lklist));scanf(“%d”,&(p->data));p->next=0;if(i==1)head=q=p;else{q->next=p;____________;}}} 三、算法设计题(22分)1．1． 设计在链式存储结构上合并排序的算法。2．2． 设计在二叉排序树上查找结点X的算法。3．3． 设关键字序列(k1，k2，…，kn-1)是堆，设计算法将关键字序列(k1，k2，…，kn-1，x)调整为堆。 数据结构试卷（十）参考答案 一、选择题1．A2．D3．B4．B5．B6．D7．A8．D9．D10．C11．B12．D 二、填空题1.1. 4，102.2. O(nlog2n)，O(n2)3.3. n4.4. 1，25.5. n(m-1)+16.6. q->next7.7. 线性结构，树型结构，图型结构8.8. O(n2)，O(n+e)9.9. 8/310.10. (38，13，27，10，65，76，97)11.11. (10，13，27，76，65，97，38)12.12. 12465313.13. structnode*rchild，bt=0，createbitree(bt->lchild)14.14. lklist，q=p 三、算法设计题1.1. 设计在链式存储结构上合并排序的算法。voidmergelklist(lklist*ha,lklist*hb,lklist*&hc){lklist*s=hc=0;while(ha!=0&&hb!=0)if(ha->datadata){if(s==0)hc=s=ha;else{s->next=ha;s=ha;};ha=ha->next;}else{if(s==0)hc=s=hb;else{s->next=hb;s=hb;};hb=hb->next;}if(ha==0)s->next=hb;elses->next=ha;}第127页共127页
1.2. 设计在二叉排序树上查找结点X的算法。bitree*bstsearch1(bitree*t,intkey){bitree*p=t;while(p!=0)if(p->key==key)return(p);elseif(p->key>key)p=p->lchild;elsep=p->rchild;return(0);}2.3. 设关键字序列(k1，k2，…，kn-1)是堆，设计算法将关键字序列(k1，k2，…，kn-1，x)调整为堆。voidadjustheap(intr[],intn){intj=n,i=j/2,temp=r[j-1];while(i>=1)if(temp>=r[i-1])break;else{r[j-1]=r[i-1];j=i;i=i/2;}r[j-1]=temp;}第127页共127页'
您可能关注的文档
- 《数据结构(含上机实训)》课后题答案.doc
- 《数据结构Java版》习题解答.doc
- 《数据结构——C语言描述》习题及答案 耿国华 2.doc
- 《数据结构——C语言描述》习题及答案 耿国华.doc
- 《数据结构—用C语言描述》习题答案.doc
- 《数据结构—用C语言描述》课后习题答案.doc
- 《数据结构》(c语言版)测试题答案.doc
- 《数据结构》复习题及参考答案.doc
- 《数据结构》期中题库及答案.doc
- 《数据结构》系统答案严蔚敏李冬梅人民邮电出版社.pdf
- 《数据结构》课后题及答案.doc
- 《数据结构与算法(徐凤生)》习题答案.doc
- 《数据结构与算法》课后习题答案.doc
- 《数据结构与算法》课后习题答案.pdf
- 《数据结构基础教程》习题及解答.doc
- 《数控加工与编程一体化教程》教学指南及习题答案.doc
- 《数控加工工艺》课后练习题答案(1).doc
- 《数控加工工艺》课后练习题答案.doc
相关文档
- 施工规范CECS140-2002给水排水工程埋地管芯缠丝预应力混凝土管和预应力钢筒混凝土管管道结构设计规程
- 施工规范CECS141-2002给水排水工程埋地钢管管道结构设计规程
- 施工规范CECS142-2002给水排水工程埋地铸铁管管道结构设计规程
- 施工规范CECS143-2002给水排水工程埋地预制混凝土圆形管管道结构设计规程
- 施工规范CECS145-2002给水排水工程埋地矩形管管道结构设计规程
- 施工规范CECS190-2005给水排水工程埋地玻璃纤维增强塑料夹砂管管道结构设计规程
- cecs 140：2002 给水排水工程埋地管芯缠丝预应力混凝土管和预应力钢筒混凝土管管道结构设计规程（含条文说明）
- cecs 141：2002 给水排水工程埋地钢管管道结构设计规程 条文说明
- cecs 140：2002 给水排水工程埋地管芯缠丝预应力混凝土管和预应力钢筒混凝土管管道结构设计规程 条文说明
- cecs 142：2002 给水排水工程埋地铸铁管管道结构设计规程 条文说明
微信/支付宝扫码支付下载