湖北省计算机类专业人才培养合作联盟联合考试试卷(数据结构A卷).doc

1、 学院 专业 级 学号 姓名 密封线一、判断题（每小题1分，共10分）1、算法可以没有输出语句。2、顺序存储结构的主要缺点是插入或者删除时效率较低。3、如果某栈的输入序列为1, 2, 3, 4, 5, 6，则可以输出1, 5, 4, 6, 2, 3。4、多维数组可以看成是线性结构的推广，因此与线性表一样，可以进行插入、删除等操作。5、在完全二叉树中，如果一个结点没有左孩子，则它必是叶子结点。6、一棵树中叶子结点总数一定等于与其对应二叉树的叶子结点总数。7、用邻接矩阵存储某图所需的存储单元数量与该图的边数有关。8、拓扑排序算法只能适用于有向无环图。9、顺序查找法适用于存储结构为顺序或者链接存储的

2、线性表。10、排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。二、填空题（每小题1分，共10分）1、数据元素之间的逻辑关系称为数据的_结构。2、在双向循环链表中插入一个新的结点时，应修改_个指针域的值。3、使用一个100 个元素空间的数组存储循环队列，如果采取少用一个元素空间的方法来区分循环队列的队空和队满，当队头标志front = 68, 队尾标志rear = 27 时，该队列中的元素个数为_。4、假设某15 阶的对称矩阵A 按行优先的顺序，压缩存储在以B0 开始的一维数组B 中，则元素A7, 11 在B 中的存储位置为_。（注：对称矩阵元素下标从1 开始）5、当使用二叉链表作

3、为n 个结点二叉树的存储结构时，空指针域的个数是_。6、设二叉树根结点的层次为1，则高度为h 的二叉树的最多可能的结点数为_。7、在一个具有n 个顶点的无向图中，要连通全部顶点至少需要_条边。8、某无向图具有n 个顶点e 条边，当使用邻接表表示时，邻接表中边结点的个数为_。9、对任一m 阶的B- 树，每个结点中最多包含_个关键字。10、用希尔排序对关键字序列(98, 36, 9, 0, 47, 23, 1, 8, 10, 7) 排序，增量序列依次是4, 2, 1，则排序共进行_趟。三、单项选择题（每小题2分，共30分） 学院 专业 级 学号 姓名 1、如果一个算法的时间复杂度用T(n) 表示，

4、则其中n 的含义是_。密封线A、问题规模B、语句条数C、循环层数D、函数数量2、在长度为n 的顺序表中删除第i 个元素(1 i n) 时，元素移动的次数为_。A、n i + 1B、iC、i + 1D、n i3、设非空带头结点的单循环链表头指针为head，则指针变量p 指向尾结点的条件是_。A、p-next-next = headB、p-next = headC、p-next-next = NULLD、p-next = NULL4、栈是一种操作受限的线性结构，其操作的主要特征是_。A、先进先出B、后进先出C、进优于出D、出优于进5、引起循环队列队头位置发生变化的操作是_。A、出队B、入队C、取队

5、头元素D、取队尾元素6、设10 12 的二维数组A 按“行优先顺序”存储，每个元素占1个存储单元，已知A11 的存储地址为420，则A55 的存储地址为_。A、470B、471C、472D、4737、对于广义表A，如果head(A) 等于tail(A)，则表A为_。A、( )B、( )C、( ), ( )D、( ), ( ), ( )8、已知一棵含50 个结点的二叉树中只有一个叶子结点，则该树中度为1 的结点个数为_。A、0B、1C、48D、499、使用线索二叉树的目的是便于_。A、在二叉树中插入或者删除结点B、在二叉树中查找双亲C、确定二叉树的高度D、查找某结点在遍历序列中的前趋和后继10、

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

7、。A、(84, 46, 62, 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)密封线 学院 专业 级 学号 姓名 四、综合应用题（每小题6分，共30分）1、已知二叉树的先序序列和中序序列分别为ABDEHCFI和DBHEACIF：1) 画出该二叉树； 2) 写出该二叉树的后序序列。2、假设通信电文使用的字符集为a, b, c, d, e, f, g, h，各字符在电文中出现的频度分别为：7, 26, 2

8、, 28, 13, 10, 3, 11，试为这8个字符设计Huffman 编码。1) 画出该Huffman 树(左孩子权值不大于右孩子权值)；2) 按左分支0、右分支1，分别写出各字符的编码。3、某有向图的邻接表如右图，分别写出从顶点A 出发进行深度优先遍历和广度优先遍历的序列。4、对关键字序列 (5, 8, 1, 3, 9, 6, 2, 7, 4, 0) 进行递增快速排序，以最左元素为基准，写出排序过程中第一趟的划分结果。5、设带权无向图如右图所示，用Prim 算法从顶点a 开始求得最小生成树，请写出算法的每一步结果。五、算法设计题（每小题10分，共20分）1、编写完整的算法，原地逆置顺序表

9、L 中的元素，顺序表的类型声明和算法的原型如下：typedef struct/ 顺序表的类型声明ElemType *elem;/ 存储空间基址int length;/ 顺序表当前长度int listsize;/ 当前分配的存储容量 SqList;void Reverse(SqList &L);/ 逆置函数原型2、设二叉树以二叉链表为存贮结构，设计算法统计二叉树中度为1 的结点个数。二叉树的类型声明和算法的原型声明如下：typedef struct BiTNode/ 二叉链表的类型声明TElemType data;struct BiTNode *lchild,*rchild;/ 左右孩子指针 B

10、iTNode, *BiTree;int Count(BiTree T);/ 统计函数原型，T 指向根结点13-14-1数据结构A卷参考答案一、判断题（10 1 = 10分） 二、填空题（10 1 = 10分）1、逻辑2、43、594、B615、n + 16、2h 17、n 18、2e9、m 110、3三、单项选择题（15 2 = 30分）A D B B AC B D D CC C D A D四、综合应用题（5 6 = 30分）1、二叉树（3分）、后序DHEBIFCA（3分）2、Huffman 树（3分）、Huffman 编码共（3分）字符编码字符编码a0101e011b10f000c01000

11、g01001d11h0013、深度优先：ABCED；广度优先：ABCDE（每个遍历序列3分）4、(0, 4, 1, 3, 2, 5, 6, 7, 9, 8)（6分）5、Prim 算法步骤(6分)第一步第二步第三步第四步第五步五、算法设计题（2 10 =20分）1、（本题共10分）void Reverse(SqList &L)/ 原地逆置顺序表L 中的元素int i, j;ElemType temp;/ 交换用中间变量（2分）for (i = 0, j = L.length 1; i lchild & T-rchild | T-lchild & ! T-rchild)（3分）+ count;count += Count(T-lchild) + Count(T-rchild);（3分）return count;（1分） A7 共 8 页