搜索
湖北省计算机类专业人才培养合作联盟联合考试2013-2014学年第1学期期末考试试卷课程名称：数据结构试卷类型：A卷共8页考试形式：闭卷笔试适用范围：学院（系）年级专业本科A－1共8页一、判断题（每小题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.考生将姓名、学号等信息写在试卷相应位置；2.必须使用蓝(黑)色钢笔或签字笔在规定位置答题；3.注意字迹清楚，保持卷面整洁。A－2共8页二、填空题（每小题1分，共10分）1、数据元素之间的逻辑关系称为数据的________结构。2、在双向循环链表中插入一个新的结点时，应修改________个指针域的值。3、使用一个100个元素空间的数组存储循环队列，如果采取少用一个元素空间的方法来区分循环队列的队空和队满，当队头标志front=68,队尾标志rear=27时，该队列中的元素个数为________。4、假设某15阶的对称矩阵A按行优先的顺序，压缩存储在以B[0]开始的一维数组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分）A－3共8页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个存储单元，已知A[1][1]的存储地址为420，则A[5][5]的存储地址为________。A、470B、471C、472D、4737、对于广义表A，如果head(A)等于tail(A)，则表A为________。A、()B、(())C、((),())D、((),(),())8、已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为________。A、0B、1C、48D、499、使用线索二叉树的目的是便于________。…………………………密……………………封……………………线………………………………学院专业级学号姓名注意事项：1.考生将姓名、学号等信息写在试卷相应位置；2.必须使用蓝(黑)色钢笔或签字笔在规定位置答题；3.注意字迹清楚，保持卷面整洁。A－4共8页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)adbfecgA－5共8页afbdec10169873254012341ABCDE23^4^2^2^03^四、综合应用题（每小题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中的元素，顺序表的类型声明和算法的原型如下：typedefstruct{//顺序表的类型声明ElemType*elem;//存储空间基址intlength;//顺序表当前长度intlistsize;//当前分配的存储容量…………………………密……………………封……………………线………………………………学院专业级学号姓名注意事项：1.考生将姓名、学号等信息写在试卷相应位置；2.必须使用蓝(黑)色钢笔或签字笔在规定位置答题；3.注意字迹清楚，保持卷面整洁。A－6共8页}SqList;voidReverse(SqList&L);//逆置函数原型2、设二叉树以二叉链表为存贮结构，设计算法统计二叉树中度为1的结点个数。二叉树的类型声明和算法的原型声明如下：typedefstructBiTNode{//二叉链表的类型声明TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指针}BiTNode,*BiTree;intCount(BiTreeT);//统计函数原型，T指向根结点A－7共8页ACEBFDHI51110461225713322854100262113-14-1《数据结构》A卷参考答案一、判断题（10×1=10分）二、填空题（10×1=10分）1、逻辑2、43、594、B[61]5、n+16、2h–17、n–18、2e9、m–110、3三、单项选择题（15×2=30分）ADBBACBDDCCCDAD四、综合应用题（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分)注意事项：1.考生将姓名、学号等信息写在试卷相应位置；2.必须使用蓝(黑)色钢笔或签字笔在规定位置答题；3.注意字迹清楚，保持卷面整洁。A－8共8页第一步第二步第三步第四步第五步五、算法设计题（2×10=20分）1、（本题共10分）voidReverse(SqList&L){//原地逆置顺序表L中的元素inti,j;ElemTypetemp;//交换用中间变量（2分）for(i=0,j=L.length–1;ij;++i,--j){//i当前最左元素下标，j当前最右元素下标（3分）temp=L.elem[i];（5分）L.elem[i]=L.elem[j];L.elem[j]=temp;}}2、（本题共10分）intCount(BiTreeT){//使用先序遍历intcount=0;（1分）if(T)（2分）{if(!T-lchild&&T-rchild||T-lchild&&!T-rchild)（3分）++count;count+=Count(T-lchild)+Count(T-rchild);（3分）}returncount;（1分）}ac1aec13abec132afbdec19324abdec1324