还剩3页未读，继续阅读
文本内容:
数据结构期中试卷
一、填空题每空分，共分2201,你学过的线性数据结构有O
2.稀疏矩阵的压缩存储方法有两种分别是和o
3.a+b*c-d/e+0的后缀表达式是
4.假设以一维数组S[nn+l/2]作为n阶对称矩阵A的存储空间，以行序为主序存储A的下三角，则元素A
[5]
[8]的值存储在S[]中
5.设n0,且有如下程序段cin»n;1=n;while i0i=i/2;则该程序的时间复杂度为O
6.下列函数的功能是实现两个字符串的比较，试根据字符串比较运算的定义，完善该函数int strcmpchars[],char t[]{int i=0;while s[i]==t[i]s[i]!=,\0,i++;
7.设栈S和队列Q的初始状态均为空，元素abcdefg依次进入栈S若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是bdcfeag,则栈S的容量至少是
8.若一棵树中度为1的结点有功个，度为2结点有小个……度为〃2的结点有小〃个，则该树的叶结点有个o
9.将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是
10.线索二叉树中的“线索”是指o二.简要回答下列问题第题每小题分，第、题每题分，共分1〜56671050L什么是算法？如何评价算法的好坏？
2.试比较顺序存储结构与链式存储结构的优缺点
3.请说明编写递归算法的思路
4.已知A、B、C、D、E、F的权值分别为
10、
30、
8、
12、
15、25,按步骤求解它们的Huffman编码
5.已知某二叉树的中序遍历序列为ACBFDE,后序遍历序列为ABCDEF,试画出该二叉树，并写出前序遍历序列
6.设有一个广义表L=x,,x,y,x,y,z,试画出它的存储结构，写出其结点的类型定义
7.树有哪些存储方法？设有一棵树T=D,R,其中D=A,B,C,X,E,F,R={A,B,A,E,A,F,B,X,F,C},分别画出它的各种存储结构
三、算法设计题每题分，共分
10301.设线索二叉树使用二叉链表存储，试编写算法查找指针p所指结点的父结点
2.已知模式串的next数组，试编写串的模式匹配算法KMP
3.已知一个带表头结点的单链表，结点结构为data和link,假设该链表只给出头指针head,请设计一个尽可能高效的算法，查找链表中倒数第k个的结点如查找成功，则输出该结点的data值，并返回1；否则返回0数据结构期终试卷（A卷）
一、填空题（每题分，共分）
2201.算法的健壮性是指O
2.对一个线性表分别进行遍历和逆置运算，最好的时间复杂度分别为—和o
3.〃个数入栈，所有可能的出栈序列共有种
4.下面程序段的时间复杂度为（nl）osum=l;for（i=0;sumn;i++）sum+=i;
5.若某二叉树有20个叶子节点，有30个节点仅有一个孩子，则该二叉树的总的结点数是o
6.若以｛4,5,6,7,8｝作为叶子节点的权值构造Huffman树，则该Huffman树的根结点权值为O
7.线索二叉树的左线索指向其,右线索指向其o
8.若含n个顶点的图形成一个环，则它的生成树可能有种9•对于具有300个记录的文件，采用分块索引查找法查找，其中用二分查找法查找索引表，用顺序查找法查找块内元素，假定每块长度均为30个元素，则平均查找长度为O
10.有一个有序表为｛1,3,9,12,32,41,45,62,75,77,82,95,100｝,当二分查找值为82的结点时，经次比较后查找成功
二、回答问题（共分）5611设一组记录的关键字为｛4,5,7,2,1,3,6｝,请回答相关问题
（1）按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成后的二叉排序树，并求出在等概率情况下查找成功的平均查找长度（3分）
（2）按表中元素的顺序进行插入生成一棵AVL树，画出该树并求出在等概率情况下查找成功的平均查找长度（4分）12下图是一个四阶B树，请回答相关问题
（1）B+树和B树的主要区别是什么？（4分）
（2）插入关键字87,画出插入调整后树的形状（4分）13已知记录关键字集合为（53,17,19,61,98,75,79,63,46,49）,要求散列到地址区间［0,10］中，散列函数选用除留余数法（mod11）请回答相关问题
（1）画出形成的散列表（若产生冲突，用开放定址的线性探测再散列法解决）（4分）
（2）计算在等概率情况下查找成功时的平均查找长度（2分）
4.有7个顶点（也，吸，V3，U4，W，⑴的有向图的邻接矩阵如右图请回答相关问,题
（1）画出该有向图（2分）00253000000
（2）画出邻接表（2分）000020000800
（3）写出从vi出发的深度优先遍历和广度优先遍历序00000013500列（4分）000000co50000
（4）将图看成AOE网，画出关键活动及相应的有向边，000000000039写出关键路径的长度（4分）
50000000000005.阅读下列函数，回答相关问题00000000000000int arrange（int a[],int1,int h,int x）{〃1和h分别为数据区的下界和上界int i,j,t；i=l；j=h;while（ij）while ija[j]=x j—;while ija[i]x i++;t=a[jl;a[j]=a[i];a[i]=t;if a[i]x returni;else returni-1;}写出该函数的功能（4分）1写一个调用上述函数实现下列功能的算法对一整型数组b[n]中的元素进行重新排2列，将所有负数均调整到数组的低下标端，将所有正数均调整到数组的高下标端，若有零值，则置于两者之间，并返回数组中零元素的个数（6分）
6.数组存储了N个整数，请回答相关问题
（1）请完善对数组a进行堆排序的程序（6分）void HeapAdjust（int a[],int h,int s）rc=a[h];for j=;j=s;j*=2ifjsa[j]aU+l]++j;if!rc=a[j]break;_____________；h=j;void HeapSortinta[l,int n〃对a[l],a
[2],…，a[n]进行堆排序for i=;i0;-iHeap Adjusta,i,n;fori=;i l;-i t=a[l];a[l]=a[i];a[i]=t;
（2）上面程序建成的堆是大顶堆还是小顶堆？（2分）
（3）对n个元素进行初始建堆的过程中，最多进行次数据比较（2分）
（4）堆排序稳定吗？请举例说明（3分）
三、算法设计题（每题分，共分）
12241.已知一棵树T用二叉链表表示，其结点形式如下，试编写一算法求树T中各结点的度数
（1）写出相应的结构定义（4分）left dataright degree
（2）编写算法（8分）
2.判断有向图是否存在回路若存在返回1,否则返回0
（1）写出相应的结构定义（4分）
（2）编写算法（8分）数据结构期终试卷（B卷）
一、填空题（每题分，共分）
2201.算法是指
2.下面程序段的时间复杂度为（n0）oi=n;while（i0）i=i/2;
3.设有2个顺序栈共享一个数组S[N],其中第一个栈的栈顶指针topi的初值为-1,进栈时topl++；第二个栈的栈顶指针top2的初值为N,进栈时top2--,则判断该共享栈满的条件是o
4.循环队列的元素存放在一维数组data[MaxSize]中，用变量front和rear分别表示队头元素和队尾元素后一个位置在数组中的下标，则该队列中元素的个数可表示为
5.假设以一维数组S[〃（〃+l）/2]作为〃阶对称矩阵A的存储空间，以行序为主序存储A的下三角，则元素A
[3]⑹的值存储在S[]中
6.设源串S二bcdcdc源,模式串P=ncdcbn,按KMP算法进行模式匹配，当S2s3s父二P1P2P3”，而S5WP40寸，S5应与比较
7.一棵完全二叉树共有2023个结点，则该二叉树叶子结点个数为o
8.具有〃个结点的连通图中，至少有条边
9.有一个有序表为｛1,3,9,12,32,41,45,62,75,77,82,95,100）,当二分查找值为82的结点时，经次比较后查找成功
10.时间复杂度为O（〃k）g2〃）的排序方法请至少写出两种
二、简答题（共分，每题分）
2051.评价一个算法好坏的标准是什么？（5分）
2.已知一棵二叉树的顺序存储如下（依照完全二叉树的结点编号次序，依次存放各个结点），请写出该二叉树的先序、中序和后序序列（5分）123456789101112131415A BC DE FG HI J
3.请简述最短路径算法Dijkstra的基本思想
4.将序列｛50,38,66,98,77,13,28,50｝建立一个堆结构，试画出该堆，并标明其是大根堆或是小根堆（5分）
三、求解题（共分，每题分）
30101.假设给定一个电文“ADCEBDABDCEBDBCDCDCDE”，请根据各字符在该电文中出现的频率完成
（1）建立一棵Huffman树（5分）
（2）给出电文中各字符所对应的Huffman编码及平均码长（5分）
2.已知一个无向带权图G（含有结点
1、
2、
3、
4、5）的邻接矩阵如下
（1）画出图G（3分）
（2）画出图G的邻接表（4分）［040082
（3）画出该图的最小生成树（3分）
404813.已知记录关键字集合为｛53,17,19,61,98,75,79,63,°°4°6146,49｝,要求散列到地址区间［0,10］中，散列函数选用除留余数法8°°6°8（mod11）请回答相关问题Hl180J
（1）画出形成的散列表（若产生冲突，用开放定址的线性探测再散列法解决）（6分）
（2）计算在等概率情况下查找成功时的平均查找长度（4分）
四、算法设计题（共分，每题分）
30101.设有整型数组及一整数七试编写算法将数组中所有小于攵的数集中在数组的左端，其余数集中在数组的右端要求算法时间复杂度为0（〃）（10分）
2.试编写算法实现图的广度优先搜索（遍历）（10分）
3.试编写算法，将二叉树中叶子结点的数据组成一个线性表（10分）例如，对于如下二叉树可以构成单链表或顺序表，单链表的一个示例Head。
个人认证
优秀文档
获得点赞 0
