《数据结构试题(白明)试题 参考答案》由会员分享，可在线阅读，更多相关《数据结构试题(白明)试题 参考答案（8页珍藏版）》请在金锄头文库上搜索。
1、试卷编号命题人： 白明 试卷分类A卷或B卷 A 五邑大学 试 卷学期： 2021 至 2021 学年度 第 二 学期课程： 数据结构 专业： 班级： AP0706 姓名： 学号： 题号一二三四五总分得分一、单项选择题(10小题，每题1分，共10分)1假设一个栈的输入序列是1，2，3，n，输出序列的第一个元素是n ，那么第i个输出元素是_D_。A不确定Bn-iCn-i-1Dn-i+12设计一个判别表达式中左右括号是否配对的算法，采用_B_数据结构最正确。A顺序表B栈C队列 D链表3设有两个串p和q，求q在p中首次出现的位置的运算称作_C_。A连接B求子串C模式匹配D求串长 4线性表的顺序存储结构
2、是一种_A_的存储结构。A随机存取B顺序存取C索引存取D散列存取 5对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是_C_。AO(1) BO(n)CO(n2)DO(nlog2n)6关键路径是AOE网中_A_。A从源点到终点的最长路径B从源点到终点的最短路径C最长的回路D最短的回路 7数据元素为34,76,45,18,26,54,92,65，按照依次插入结点的方法生成一棵二叉排序树，那么该树的深度为_B_。A3B5C7D9 8对数列25,84,21,47,15,27,68,35,20进行排序，元素序列的变化情况如下：(1) 25，84，21，47，15，27，68，35，20(2) 2
3、0，15，21，25，47，27，68，35，84(3) 15，20，21，25，35，27，47，68，84(4) 15，20，21，25，27，35，47，68，84那么采用的排序方法是_A_。A快速排序B归并排序C基数排序D希尔排序 9任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序_A_。A肯定不发生改变B肯定发生改变C不能确定D有时发生变化 10对特殊矩阵采用压缩存储的目的主要是为了_D_。A表达变得简单B对矩阵元素的存取变得简单C去掉矩阵中的多余元素D减少不必要的存储空间二、判断题(10小题，每题1分，共10分) 1一个图的邻接矩阵表示是惟一的，邻接表表示也惟一。 2
4、设有5000个元素，希望用最快的速度挑选出前10个最大的，采用快速排序方法比采用堆排序更好。 3在散列函数H(k)=k mod m 中，一般来讲，m应取素数。 4从逻辑关系上讲，数据结构主要分为集合、线性结构、树结构和图结构。 5一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，那么第1个元素的地址为112。 6数组Qn用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为(rearfrontn)%n。 7将数组称为随机存取结构是因为数组元素是随机的。 8排序的主要目的时为了以后对已排序的数据进行查找。 9在一
5、个有向图中，所有顶点的入度之和等于所有顶点的出度之和。 10拓扑排序算法和广度优先遍历算法都能判断一个有向图是否存在回路。三、填空题(10小题，每空1分，共16分)1表示有100个顶点，1000条边的有向图的邻接矩阵有_1000_个非零矩阵元素。2如果要将序列50,16,23,68,94,70,73建成堆，只须把16与_50_交换。3具有6个顶点的无向图至少应该有_5_条边才能确保是一个连通图。4含A、B、C这3个结点的不同形态的树有_2_棵，不同形态的二叉树有_5_棵。5 中缀表达式(5620)(42)转换为后缀表达式为56#20-4#2+/，后缀表达式A BC D E 转换为中缀表达式为A
6、/B-C*D+E。6一个有序表的关键字序列为1，8，12，25，29，32，40，62，98，当二分查找值为29的元素时，需要_1_次比拟才能查找成功；假设采用顺序查找时，需要_5_次比拟才能查找成功。7一棵树T的边集为I,M,I,N,E,I,B,E,B,D,C,B,G ,J,G ,K,A,G,A,F,H,L,A,H,C,A，那么该树的根结点是_C_，叶子结点共_7_ 个， 该树的深度为_5_。8设待处理问题的规模为n，假设一个算法的时间复杂度为一个常数，那么表示成数量级的形式为_O(1)_；假设为nlog25n, 那么表示成数量级的形式为_O(nlog2n)_。 9在由尾指针rear指示的单
7、循环链表中，在表尾插入一个结点s的操作序列是s-next=rear-next; rear-next=s;和rear=s。10二叉树的前序序列和后序序列正好相反，那么该二叉树一定是_高度等于其结点数_的二叉树。四、应用题(共有7小题，共计50分)1 一棵二叉树的中序遍历序列是ABCDEFG，后序遍历序列是BDCAFGE，画出该二叉树，并给出该二叉树的前序遍历序列，画出该二叉树对应的森林。(10分)解答：二叉树如下5分： 对应的森林如下3分：ECAGFDB ECADB GF前序遍历序列是：EACBDGF 2分2 证明：对于一棵非空的二叉树，如果叶结点数为n0，度为2的结点数为n2，那么有n0=n2
8、+1。5分证明：设n为二叉树的结点总数，n1为二叉树中度为1的结点数，那么有： nn0n1n2 2分在二叉树中，除了根结点外，其余结点都有唯一的一个分枝进入，由于这些分枝是由度为1和度为2的结点射出的，一个度为1的结点射出一个分枝，一个度为2的结点射出两个分枝，所以有： nn12n21 2分合并两式，可以得到：n0n21 。1分3 假设输入序列是3，5，1，9，4，10，2，8，7，6，试画出所产生的大根堆和所对应的二叉排序树。7分大根堆：4分二叉排序树：3分 134569710824 某字符串S中共有5种字符(A，B，C，D，,E)，各种字符出现的频率分别是15，36，3，6，20，建立相应
9、的哈夫曼树，对该字符串用0，1进行前缀编码，给出5种字符的哈夫曼编码，并计算其WPL。7分哈夫曼树：4分哈夫曼编码：2分WPL：1分A：111B：0C：1100D：1101E：10WPL=36+40+45+36=157 5 给定表19,14,22,01,66,21,83,27,56,13,10，按表中元素顺序构造一棵AVL树。7分每个平衡步骤1分。 6某图的邻接表如下7分：（1） 分别给出从A、B点出发进行广度优先搜索的序列。（2） 画出该图。解答：分别给出从A、B点出发进行广度优先搜索的序列。各2分A： A B C D B： B A C D对应的图如下： 3分7设有一组关键字72，35，12
10、4，153，84，57需要插入到表长为12 的散列表中。试设计一个适当的散列函数；用此散列函数将上述关键字插入散列表，用线性探测法解决冲突。试画出最终的散列表结构。 说明：哈希函数不同，数据在哈希表中的位置不同。多解假设设：H(key)=key%112分 那么最终的哈希表结构为：3分所有关键字求散列值：2分0 1 2 3 4 5 6 7 872153124358457 3五、算法设计题(2小题，每题7分，共14分)1设计一个算法，判断一个单链表中的元素是否递增有序。templateint order(Node *h)Node *p=h; 以上1分while(p-next!=NULL)if(p-
11、datanext-data)p=p-next; 以上3分elsebreak;if(p-next=NULL)return 1;elsereturn 0; 以上3分 2一棵具有n个结点的二叉树采用顺序存储结构，编写算法对该二叉树进行前序遍历。 说明：仅给出一种参考算法，可以用递归算法或其它情况。template void PreOrder(T a,int n) top=-1;i=1; coutai;S+top=i; j=2*i; 以上2分 while(top!=-1) while(j=n) coutai; S+top=j; i=j; j=2*i 以上3分 i=Stop-; j=2*i+1; 以上2分【唯美句子】 走累的时候，我就到升国旗哪里的一角台阶坐下，双手抚膝，再闭眼，让心灵受到阳光的洗涤。懒洋洋的幸福。顶 3 收藏 2【唯美句子】 一个人踮着脚尖，在窄窄的跑道白线上走，走到很远的地方又走回来。阳光很好，温暖，柔和。漫天的安静。顶 7 收藏 7【唯美句子】 清风飘然，秋水缓淌。一丝云起，一片叶落，剔透生命的空灵。轻轻用手触摸，就点碎了河面的脸。落叶舞步婀娜不肯去，是眷恋，是装点？瞬间回
