《防灾科技学院数据结构2014-2015-1 期末考试A标准答案及评分细则》由会员分享，可在线阅读，更多相关《防灾科技学院数据结构2014-2015-1 期末考试A标准答案及评分细则（4页珍藏版）》请在金锄头文库上搜索。
1、第 1 页(共 4 页)|装|订|线|防灾科技学院2014 2015 学年 第一学期期末考试数据结构试卷(A) 标准答案及评分细则使用班级 灾害信息工程系 13 级本科班 答题时间 120 分钟题号 一 二 三 四 五 总分阅卷教师得分一、单选题（本大题共 15 小题，每题 2 分，共 30 分。 ）1、在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（ ） 。A数据的处理方法 B数据元素的类型C数据元素之间的关系 D数据的存储方法2、在以下的叙述中，正确的是（ ） 。A线性表的顺序存储结构优于链表存储结构B二维数组是其数据元素为线性表的线性表C栈的操作方式是先进先出D队列的操作方式是
2、先进后出3、如果对线性表的操作只有两种，即删除第一个元素，在最后一个元素的后面插入新元素，则最好使用（ ） 。A只有表头指针没有表尾指针的循环单链表B只有表尾指针没有表头指针的循环单链表C非循环双链表D循环双链表4、一个栈的进栈序列是 a，b，c，d，e ，则栈的不可能的输出序列是（ ） 。Aedcba Bdecba C dceabD abcde5、允许对队列进行的操作有（ ） 。A对队列中的元素排序 B取出最近进队的元素C在队头元素之前插入元素D删除队头元素6、数组 A 中，每个元素的长度为 3 个字节，行下标 i 从 1 到 8，列下标 j 从 1 到 10，从首地址 SA 开始连续存放的
3、存储器内，该数组按行存放，元素 A85的起始地址为（ ） 。ASA 141 B SA144 CSA222D SA 2257、对矩阵进行压缩存储是为了（ ） 。A方便运算B 方便存储C提高运算速度 D减少存储空间8、树最适合用来表示（ ） 。A有序数据元素 B无序数据元素C元素之间具有分支层次关系的数据D元素之间无联系的数据9、若一棵二叉树具有 15 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点的个数是（ ） 。A14 B16 C20 D不能确定10、设森林 F 对应的二叉树为 B，它有 m 个结点，B 的根为 p，p 的左子树的结点个数为n，森林 F 中其他树的结点的个数是（
4、 ） 。Amn Bmn1 Cn1D 不能确定11、在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。A1/2 B 1C 2 D 4 12、已知一个图，如图 1 所示，若从顶点 a 出发按深度搜索法进行遍历，则可能得到的一种顶点序列为（ ） 。Aa，b，e，c，d，f Ba，c ，f ，e ，b，dCa， e，b，c，f，d， Da，e ，d，f ，c ，b13、下列查找方法中， （ a ）适用于查找有序单链表。A顺序查找 B二分查找 C分块查找 D哈希查找14、查找效率最高的二叉排序树是（ ） 。A所有结点的左子树都为空的二叉排序树。 B平衡二叉树。C所有结点的右子树都为空的二叉排序树
5、。D没有左子树的二叉排序树。15、 （ ）在链表中进行操作比在顺序表中进行操作效率高。A顺序查找B折半查找C分块查找D插入选择题请将答案填写在下面的表格中。阅卷教师得 分1-5 CBBCD 6-10 CDCBB 11-15 CDABD试卷序号： 班级：学号：姓名： abcdef图 1第 2 页(共 4 页)评分细则：每题 2分，错误即扣 2 分。|装|订|线|二、 填空题（本大题共 8 小题，每空 1 分，共 10 分。 ）1、数据的逻辑结构分为集合、线性构、 树(形) 结构和 图(状) 结构 4 种。2、在顺序表中访问任意一结点的时间复杂度均为 O(1)。3、带头结点的循环链表 L 为空的条
6、件是L-next=L 或 L=L-next 。4、队列是限定仅在表头进行插入， (在) 表尾或(在)队尾或末尾或尾部 进行删除操作的线性表，其运算遵循先进先出的原则。5、在具有 n 个结点的二叉链表中，其中 n-1 个指针域用于指向其左右孩子。6、一棵深度为 6 的满二叉树有 31 个分支结点和 32 或 25 个叶子。7、具有 10 个顶点的无向图，边的总数最多为_ 45 或 C102 _。8、折半查找有序表（4，6，12，20，28，38，50，70，88，100） ，若查找表中元素 20，它将依次与表中元素 28，6，12，20 比较大小。评分细则：每空 1 分，意思表达正确即可得分。三
7、、 判断题（本大题共 10 小题，每题 1 分，共 10 分。 ）（ ）1. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （ ）2. 链表的每个结点中都恰好包含一个指针。 （ ）3. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（ ）4.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（ ）5.具有 12 个结点的完全二叉树有 5 个度为 2 的结点。（ ）6.二叉树中每个结点有两棵非空子树或有两棵空子树。（ ）7.邻接矩阵可以表示有向图，也可以表示无向图。（ ）8对于任意一个图，从它的某个结点进行一次深度或广度优先遍历可以访问到
8、该图的每个顶点。（ ）9散列法存储的思想是由关键字值决定数据的存储地址。（ ）10在待排序的记录集中，存在多个具有相同键值的记录，若经过排序，这些记录的相对次序仍然保持不变，称这种排序为稳定排序。评分细则：每题 1 分，错误即扣 1 分。四、 应用题（本大题共 5 小题，每题 8 分，共 40 分。 ）1、已知二叉树的先序序列和中序序列分别为HDACBGFE和ADCBHFEG。（1）画出该二叉树；(3分)（2）给出该二叉树的后序遍历序列；(2分)（3）画出与（1）求得的二叉树对应的树或森林。(3分) 答：(1) (2)ABCDEFGH (3)HD GACBFEHDGACBF E评分细则：(1)
9、 1) 一个叶子结点错误扣 1 分,非叶子结点错误扣 3 分;2) 画图不规范,不画圆圈不扣分。(2) ABCD 结点顺序错 2-3 个扣 1 分，EFG 结点顺序错 2-3 个扣 1 分，如果 ABCD 结点和EFG 结点混排不得分，少一个字母扣 1 分。(3)全部正确得 3 分，第一颗树 2 分，第二颗树 1 分;其它情况酌情扣分。2、假设通信电文使用的字符集为a，b，c，d，e，f，g，h，各字符在电文中出现的频度分别为：7，26，2，28，13，10，3，11，试为这8个字符设计哈夫曼编码。要求：(1)画出你所构造的哈夫曼树( 要求树中左孩子结点的权值不大于右孩子结点的权值) (4分)
10、 ；(2)按左分支为0和右分支为1的规则，分别写出与每个字符对应的编码 (2分)；(3)问该字符串的编码至少有多少位 (2分)。答：（1） (2) a:0101b:10c:01000d:11e:011f:000g:01001h:001(3) (2+3)*5+7*4+(10+11+13)*3+(26+28)*2=263评分细则：(1)哈夫曼编码树全部正确得 4 分;阅卷教师得 分阅卷教师得 分阅卷教师得 分试卷序号： 班级：学号：姓名：235712351024646281001abcdefgh第 3 页(共 4 页)1) 未按照(1)中要求的权值次序构造的哈夫曼树扣 2 分。2) 结点值计算错误
11、或未标明，扣 1 分;3) 画图不规范,不画框,圆圈,汉字字符不扣分；|装|订|线|(2).若构造的哈夫曼树错误，编码不得分；字符编码错误 12 个扣 0.5 分，全部错误扣 2 分;(3).编码位数计算公式正确,结果错误，扣 1 分，全部错误扣 2 分;其他情况酌情扣分。3、图2表示一个地区的交通网，顶点表示城市，边表示连结城市间的公路，边上的权表示修建公路花费的代价。怎样选择能够沟通每个城市且总造价最省的n-1条公路（6分） ，并求出公路花费总值M(2分)。要求：源点从1开始，使用Prim算法，并画出每一个步骤。答：(1) (2) (3) (4)1313531366531346(5) (6
12、) (7)465313456462531341564625312341567M=3+6+4+5+2+1=21评分细则：1) 画图不规范,不画圆圈,不标权值,不扣分;2) 最小生成树的生成从第 2 步至第 7 步每步 1 分,表述形式可多样,思路正确可得分;3) M 值计算公式正确,结果错误,扣 1 分, 全部错误扣 2 分;4) 其它情况酌情扣分。4、已知一组数据元素为57，24，96，73，18，45，30，40，82 ，要求：(1) 试画出按元素排列顺序输入而生成的一棵二叉排序树(4 分)；(2) 计算在等概率情况下该二叉排序树的平均查找长度ASL (2 分)。(3) 画出删除结点57后的
13、二叉排序树(2 分)。答： (1) 二叉排序树:5 72 41 84 53 09 67 38 24 0（2）删除结点57后的二叉排序树:或： 4 52 41 8 3 09 67 38 24 07 32 41 8 4 53 09 68 24 0评分细则：1) 二叉排序树错一个叶子结点扣 1 分,分支结点错误不得分;2) ASL 计算公式正确,结果错误 ,扣 1 分, 全部错误扣 2 分;3) 删除后的二叉排序树根结点正确,而被删结点的分支结点位置错误扣 1 分；根结点错误不得分。4）其它情况酌情扣分。5、已知关键字序列34,26,47,12,63,41,22,59，用下列方法进行升序排序，(1)
14、 写出采用直接插入排序算法第一趟结束时关键字的排列状态 (2分)；试卷序号： 班级：学号：姓名：第 4 页(共 4 页)(2) 写出构建的大根堆(3分) ，并写出采用堆排序算法第一趟结束时关键字的排列状态(3分)。答：(1) 26, 34,47,12,63,41,22,59(2) (3) 59,34,47,12,26,41,22,63或是下面的大根堆6 35 93 42 64 74 12 21 25 93 41 22 64 74 12 26 3评分细则：(1)直接插入排序结果正确得 2 分，采用其他排序方法不得分；(2) 大根堆构建正确得 3 分；1) 只写出完全二叉树扣 2 分，由完全二叉树到大根推的调整，最后一步未调整扣 1 分；2) 59 与 47 互换不得分；第三层34,26,41,22的顺序 34 与 26 互换扣1 分，其他排列不得分；12 位置不对扣 1 分；(3)只将(2)中的大根堆中的 63 与 12 互换未调整扣 2 分；没有标明或写出 63 扣 1
