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

学院 专业 级 学号 姓名 密封线一、判断题（每小题1分，共10分）1、算法可以没有输出语句。2、顺序存储结构的主要缺点是插入或者删除时效率较低。3、如果某栈的输入序列为1, 2, 3, 4, 5, 6，则可以输出1, 5, 4, 6, 2, 3。4、多维数组可以看成是线性结构的推广，因此与线性表一样，可以进行插入、删除等操作。5、在完全二叉树中，如果一个结点没有左孩子，则它必是叶子结点。6、一棵树中叶子结点总数一定等于与其对应二叉树的叶子结点总数。7、用邻接矩阵存储某图所需的存储单元数量与该图的边数有关。8、拓扑排序算法只能适用于有向无环图。9、顺序查找法适用于存储结构为顺序或者链接存储的线性表。10、排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。二、填空题（每小题1分，共10分）1、数据元素之间的逻辑关系称为数据的_结构。2、在双向循环链表中插入一个新的结点时，应修改_个指针域的值。3、使用一个100 个元素空间的数组存储循环队列，如果采取少用一个元素空间的方法来区分循环队列的队空和队满，当队头标志front = 68, 队尾标志rear = 27 时，该队列中的元素个数为_。4、假设某15 阶的对称矩阵A 按行优先的顺序，压缩存储在以B0 开始的一维数组B 中，则元素A7, 11 在B 中的存储位置为_。（注：对称矩阵元素下标从1 开始）5、当使用二叉链表作为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) 表示，则其中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、取队头元素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、无向完全图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、下列关键字序列中，构成小根堆的是_。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, 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、编写完整的算法，原地逆置顺序表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;/ 左右孩子指针 BiTNode, *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分）字符编码字符编码a0101e011b10f000c01000g01001d11h0013、深度优先：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;/