(完整版)湖北省计算机类专业人才培养合作联盟联合考试试卷(数据结构A卷)范文

1、湖北省计算机类专业人才培养合作联盟 联合考2013-201学年1学期末考试试课程名称：数据结试卷类型8考试形式：闭笔适用范围学院（系专本一、判断分分，1（每小、算法可以没有输出语句、顺序存储结构的主要缺点是插入或者删除时效率较低、如果某栈的输入序列1, 2, 3, 4, 5, ，则可以输1, 5, 4, 6,2, 、多维数组可以看成是线性结构的推广，因此与线性表一样，可以进插入、删除等操作、在完全二叉树中，如果一个结点没有左孩子，则它必是叶子结点、一棵树中叶子结点总数一定等于与其对应二叉树的叶子结点总数、用邻接矩阵存储某图所需的存储单元数量与该图的边数有关、拓扑排序算法只能适用于有向无环图、顺

2、序查找法适用于存储结构为顺序或者链接存储的线性表1、排序的稳定性是指排序算法中的比较次数保持不变，且算法能够止二、填空分分，1（每小、数据元素之间的逻辑关系称为数据_结构 81 注意事项： 考生将姓名、学号等信息写在试卷相应位置；1. 色钢笔或签字笔在规定位置答题；)(黑必须使用蓝 2. 注意字迹清楚，保持卷面整洁。 3. 2、在双向循环链表中插入一个新的结点时，应修改_个指针域的值。 3、使用一个100 个元素空间的数组存储循环队列，如果采取少用一个元front = 68, 素空间的方法来区分循环队列的队空和队满，当队头标志rear = 27 时，该队列中的元素个数为_队尾标志。 AB0 按

3、行优先的顺序，压缩存储在以阶的对称矩阵开 4、假设某15 BAB 中的存储位置为_。中，则元素（ 在始的一维数组注： 117, 对称矩阵元素下标从1 开始） n 个结点二叉树的存储结构时，、当使用二叉链表作为空指针域的个数5是_。 h 的二叉树的最多可能的结点，则高度为6、设二叉树根结点的层次为1数为_。 n 个顶点的无向图中，要连通全部顶点至少需要_7、在一个具有条边。 ne 条边，当使用邻接表表示时，邻接表中边 8、某无向图具有个顶点结点的个数为_。 m 阶的B- 树，每个结点中最多包含_个关键字。 9、对任一10、用希尔排序对关键字序列(98, 36, 9, 0, 47, 23, 1,

4、8, 10, 7) 排序，增量序列依次是4, 2, 1，则排序共进行_趟。 三、单项选择题 分）分，共30（每小题2 nnT的含义是、如果一个算法的时间复杂度用表示，则其中( ) 1 。_ D、函数数量C、循环层数 A、问题规模 B、语句条数 8 共A2 页 名姓 niin) 时，元素移的顺序表中删除第 个元素(1 2、在长度为 动的次数为_。 niiini D、 C、 A、 + 1 、 + 1 Bheadp ，则指针变量3、设非空带头结点的单循环链表头指针为指向尾结点的条件是_。 pnextnextheadpnexthead =-> = B A 、 ->、-> pnextn

5、extnextp -> = = NULL C、->、 NULL ->D 4、栈是一种操作受限的线性结构，其操作的主要特征是_。 A、先进先出 B、后进先出 C、进优于出 D、出优于进 5、引起循环队列队头位置发生变化的操作是_。 A、出队 B、入队 C、取队头元素 D、取队尾元素 6、设10 × 12 的二维数组A 按“行优先顺序”存储，每个元素占1个存储单元，已知A11 的存储地址为420，则A55 的存储地址为_。 A、470 B、471 C、472 D、473 headtail(A)，则表A为_。7、对于广义表A，如果 (A) 等于 A、( ) B、( ) C

6、、( ), ( ) D、( ), ( ), ( ) 个结点的二叉树中只有一个叶子结点，则该树中度为8、已知一棵含50 _。1 的结点个数为49 D、48 A 、0 B、1 C、 9、使用线索二叉树的目的是便于_。 A、在二叉树中插入或者删除结点 B、在二叉树中查找双亲 C、确定二叉树的高度 D、查找某结点在遍历序列中的前趋和后继 页8 共3 A 注意事项： 1. 考生将姓名、学号等信息写在试卷相应位置；色钢笔或签字笔在规定位置答题；)必须使用蓝(黑 2. 注意字迹清楚，保持卷面整洁。 3. n 个顶点，则其边的总数为_条。10、无向完全图G 有 2nnnnnn 、 1 1) C、 A、 1)

7、/ 2 B、(D11、如右图所示的有向图可以排出_种不同的fb拓扑序列。 eac A、 5 B、6 C、12 D、其它 gd12、要输出二叉排序树结点的有序序列，则可以采用的遍历方法是_遍历。 A、按层 B、先序 C、中序 D、后序 n 、下列查找方法中，平均查找长度与关键字数量不直接相关的查找13方法是_查找。 A、分块 B、顺序 C、折半 D、哈希 14、用“大数下沉”的冒泡排序法对初始关键字序列(8, 13, 26, 55, 29, 44) 递增排序，第一趟排序时关键字需要交换_次。 A、2 B、3 C、4 D、5 15、下列关键字序列中，构成小根堆的是_。 A、(84, 46, 62,

8、 41, 28, 58, 15, 37) B、(84, 62, 58, 46, 41, 37, 28, 15) C、(15, 28, 46, 37, 84, 41, 58, 62) D、(15, 28, 46, 37, 84, 58, 62, 41) 四、综合应用题 分）30（每小题6分，共1、已知二叉树的先序序列和中序序列分别为ABDEHCFI和DBHEACIF： 1) 画出该二叉树； 2) 写出该二叉树的后序序列。 abcdefgh, , , , , , , ，各字符在、假设通信电文使用的字符集为2 名 页 4 A共8 姓 密 87, 26, 2, 28, 13, 10, 3, 11，试为

9、这电文中出现的频度分别为：Huffman 个字符设计编码。Huffman )；树(1) 画出该左孩子权值不大于右孩子权值 1，分别写出各字符的编码。按左分支0、右分支2) 2 1A0分别写出从、某有向图的邻接表如右图，33 2B1出发进行深度优先遍历和广度顶点A C24 优先遍历的序列。D32 E43 0 (5, 8, 1, 3, 9, 6, 2, 4、对关键字序列进行递增快速排序，以最左元素为基准，写出排序过程中第0) 7, 4, 一趟的划分结果。1caPrim算法从顶点 5、设带权无向图如右图所示，用35946fea请写出算法的每一步结开始求得最小生成树， 27108db 果。 五、算法设

10、计题分）20（每小题10分，共L顺序表的类型声明和 、编写完整的算法，原地逆置顺序表中的元素，1 算法的原型如下： struct typedef 顺序表的类型声明 / elem 存储空间基址 ; ElemType */ length / 顺序表当前长度; intlistsize / int 当前分配的存储容量; SqList; LSqListReverse 逆置函数原型( &/ ); void 的结设二叉树以二叉链表为存贮结构，设计算法统计二叉树中度为1 、2 页8 共5 A 注意事项： 1. 考生将姓名、学号等信息写在试卷相应位置；色钢笔或签字笔在规定位置答题；必须使用蓝(黑) 2.

11、注意字迹清楚，保持卷面整洁。 3. 点个数。二叉树的类型声明和算法的原型声明如下： BiTNode struct typedef / 二叉链表的类型声明 data; TElemType rchildBiTNodelchild / ,*左右孩子指针struct *; BiTreeBiTNode; , * TBiTreeCountT / ); 统计函数原型，指向根结点int ( 卷参考答案A13-14-1数据结构 分）一、判断题（10 × 1 = 10 ? ? ? ? ? ? ? ? ? 1 = 10分）二、填空题（10 ×4 、2 1、逻辑 页8 共6 A61 4、B3、59

12、 h 1 25、n + 1 6、 1 7、n 2e8、 1 9、m3 10、 2 = 30分）三、单项选择题（15 ×D C C D A D B B A C B D D C A 6 = 30分）四、综合应用题（5 ×A 3分）、后序DHEBIFCA（3分）1、二叉树（B CF ED HI 100 32、Huffman 树（3分）、Huffman 编码共（分）4654 编码字符编码 字符 21011 e a 0101 262528000 b 10 f 1011121301001 g c 01000 5001 h d 11 7 23ABCDE 广度优先：3、深度优先：ABCED

13、； （每个遍历序列3分） 分） （4、(0, 4, 1, 3, 2, 5, 6, 7, 9, 8) 6) 分 (6 Prim 算法步骤 5、1 ca11ca1ca 第一步 ac3393 441eefcae22 23dbbd be 第五步 第四步 第二步 第三步 分）五、算法设计题（2 × 10 =20 分）（本题共101、 页8 共7 A 注意事项： 1. 考生将姓名、学号等信息写在试卷相应位置；色钢笔或签字笔在规定位置答题；必须使用蓝()黑 2. 注意字迹清楚，保持卷面整洁。 3. ) LSqList &void Reverse( 中的元素L / 原地逆置顺序表; ji, int 分）2（ ElemType temp; / 交换用中间变量) , - j; + length 1; i < ji for (i = 0, j = L. 分）（ 当前最左元素下标，j 当前最右元素下标 3 / i 分）（5 temp = L.elemi; ; L.elemi = L.elemj; = tempelemj L. 分） （本题共102、) T(BiTree int Count 使用先序遍历 /