资源描述：
《数据结构期末试卷2》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。专业班级学号学生签名： 试卷编号： （A）卷数据结构课程课程类别：必开卷(范围)（A4纸一张）： 考试日期： 题号一二三四五六七八九十总分累分人签名题分30203812100得分考生注意事项：1、本试卷共7页，总分 100 分，考试时间 120分钟。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。得分评阅人一、选择题(
2、每题2分，共30分)1.假设某算法语句总的执行次数为T(n)=6n4+n³+n2,那么该算法的时间复杂性量级为(C)。A)O(2)B)O(n5)C)O(n4)D)O(1)2.线性表采用顺序存储结构时，其地址(A)。A)必须是连续的B)部分地址必须是连续的C)一定是不连续的D)连续与否均可以3.从物理结构上可以把数据结构分为（B）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构4.在顺序线性表（a1,a2,···,a29,a30）中，在a20之前插入一个新的结点，需要将(A)个结点后移。A
3、)11B)20C)19D)105.带头结点的单循环链表为空的条件是(C)。A)head->next==NULLB)head==NULLC)head->next==headD)head!=NULL6.栈S最多能容纳4个元素。现在6个元素按A、B、C、D、E、F的顺序进栈，下列哪一个序列是不可能的出栈序列？(B)A)A、B、C、D、E、FB)A、F、E、D、C、BC)C、B、E、D、A、FD)C、D、B、F、E、A7.深度为K的二叉树最多有(C)个结点。A)2KB)2K–1C)2K–1D)2K+18.n个顶点的无向完全图的弧数为(D)。第8页
4、共页A)n(n-1)B)n×nC)2nD)n(n-1)/21.在一个图中，图的边数等于所有顶点的度数之和的(A)倍。A)1/2B)1C)2D)42.图的广度优先遍历类似于二叉树的（C）A)先序遍历B)中序遍历C)层次遍历D)后序遍历3.在有n个叶子结点的哈夫曼树中，其结点总数为(C)。A)不确定B)2nC)2n+1D)2n-14.将一棵有100个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为1，则编号为36的结点的左孩子的编号为(B)A)71B)72C)73D)375.利用逐点插入法建立序列(50，72，4
5、3，85，75，20，35，45，65，30)对应的二叉排序树以后，查找元素35要进行（A）元素间的比较。A)4次B)5次C)7次D)10次6.在顺序表(3,6,8,10,12,15,16,18,21,25,30)中，用折半法查找关键码值11，所需的关键码比较次数为：(B)A)2B)3C)4D)57.链表适用于（A）查找(备注：上次有同学问过我这个题目，上次给的答案是错误的)A)顺序B)二分法C)顺序，也能二分法D)随机一、填空题（每空1分,共20分）1.通常是以算法执行所耗费的时间和所占用的空间来判断一个算法的优劣。2.队列中允许进行删
6、除的一端为队头。3.在顺序队列中，虽然仍有空闲，但不能进行入队操作，这被称为是假溢出。4.n个顶点的连通图的生成树有n-1条边。5.后缀算式79220+-62/*的值为_171_。中缀算式（8-X*Y）-4*Y/7对应的后缀算式为__8XY*-4Y*7/-。6.若要求一个稀疏图G的最小生成树，最好用克鲁斯卡尔算法来求解。A1A2A4A5A6A7A3图17.若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的不同排列个数为:5（备注：abcacbcbabacbca）8.有一棵树如图1所示，回答下面的问题：（1）这棵树的根结点是（9
7、）A1;（2）这棵树的叶子结点是（10）A2,A4,A5,A7（3）结点A3的度是（11）2（4）这棵树的度是（12）3（5）这棵树的深度是（13）4（6）结点A3的子女是（14）A5,A6（7）结点A3的父结点是（15）A19.设一棵完全二叉树有678个结点，则共有（16）339个叶子结点。10.假定一棵二叉树的结点数为18，则它的最小深度为_5，最大深度为_18。11.若要求一个稠密图G的最小生成树，最好用普里姆算法来求解。第8页共页1.n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为n2。已知数据结构DS的定义如下，请给出其逻
8、辑结构图示。（5分）DS=(D,R)D={a,b,c,d,e,f}R={T}T={,,,,,,}已知二叉树的中序序列为DB
