《数据结构》期末考试题及答案.pdf

12011-2012 学年第一学期期末考查数据结构试卷 （答案一律写在答题纸上，在本试卷上做答无效）一、选择（每题 1 分，共 10 分）1.长度为 n 的线性表采用顺序存储结构，在其第 i 个位置插入一个新元素的算法时间复杂度为（）A.O(0)B.O(1)C.O(n)D.O(n2)2.六个元素按照 6，5，4，3，2，1 的顺序入栈，下列哪一个是合法的出栈序列？（）A.543612 B.453126 C.346512 D.2341563.设树的度为 4，其中度为 1、2、3、4 的结点个数分别是 4、2、1、2，则树中叶子个数为（）A.8 B.9 C.10 D.114.设森林 F 对应的二叉树 B 有 m 个结点，B 的右子树结点个数为 n，森林 F 中第一棵树的结点个数是（）A.m-n B.m-n-1 C.n+1 D.m+n5.若一棵二叉树具有 10 个度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点个数是（）A.9 B.11 C.15 D.不确定6.下列哪一个方法可以判断出一个有向图是否有环。（）A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径7.第 7 层有 10 个叶子结点的完全二叉树不可能有（）个结点。A.73 B.234 C.235 D.2368.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（）A.（100,80,90,60,120,110,130）B.（100,120,110,130,80,60,90）C.（100,60,80,90,120,110,130）D.（100,80,60,90,120,130,110）9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21（2）15 47 25 84 21（3）15 21 25 84 47（4）15 21 25 47 84 则采2用的排序方法是（）A.选择排序 B.起泡排序 C.快速排序 D.插入排序10.对线性表进行折半查找时，要求线性表必须（）A.以顺序方式存储 B.以顺序方式存储，且数据元素有序C.以链接方式存储 D.以链接方式存储，且数据元素有序二、填空（每空 1 分，共 15 分）1.数据结构中评价算法的两个重要指标是 、空间复杂度。2.在单链表中，指针 P 所指结点有后继的条件是 。（结点构成：data 和next）3.栈的特点是 。4.判断循环队列是否队满的条件表达式是 。5.完全二叉树中的结点个数为 n，则编号最大的分支结点的编号为 。6.如果 A 有 7 个兄弟，而 B 是 A 的双亲，则 B 的度是 。7.如果二叉树中有 20 个叶子节点，30 个度为 1 的结点，则该二叉树的总结点数为 。8.设二叉树中每个结点均用一个字母表示，若一个结点的左子树或者右子树为空，用.表示。现前序遍历二叉树的结点序列为 ABD.GCE.H.F.，则中序遍历二叉树的结点序列为 。9.若用 n 表示图中的顶点数目，则有 条边的无向图被称为完全图。10.如果具有 n 个顶点的图是一个环，则它有 棵生成树。11.克鲁斯卡尔算法的时间复杂度是 ，它适合求 图的最小生成树。12.顺序查找 n 个元素的线性表，若查找成功时的平均查找长度为 。13.高度为 5 的完全二叉树，其结点最少有 个。14.直接插入排序中使用的监视哨的作用是 。三、判断题（每题 1 分，共 10 分）1.算法独立于具体的程序设计语言，与具体的计算机无关。（）2.线性表采用链式存储时，结点内部的存储空间可以是不连续的。（）33.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（）4.哈夫曼树的结点总个数一定是偶数。（）5.已知二叉树的先序遍历序列和中序遍历序列，可以画出这棵二叉树（）。6.有 e 条边的无向图，在其对应的邻接表中有 e 个结点。（）7.连通分量指的是无向图的极大连通子图。（）8.在哈希表的查找过程中的“比较”操作是无法避免的。（）9.完全二叉树肯定是平衡二叉树。（）10.堆排序是稳定的排序算法。（）四、简答题（共 30 分）1.线性结构的特点是？（4 分）2.已知图的邻接矩阵存储如下所示，请根据该邻接矩阵画出对应的图，并给出从 A 出发的广度优先搜索序列，以及相应的广度优先生成树。（6 分）A B C D E F A B C D E F3.已知一棵二叉树的后序遍历序列为 EICBGAHDF，中序遍历序列为 CEIFGBADH，请画出这棵二叉树，并把这棵二叉树转换成相应的树（或森林）。（6 分）4.已知电文内容为：ACACBACDAACDBAACADAA，字符集为 A，B，C，D，设计一套二进制编码，使得上述电文的编码最短。（6 分）5.已知有序序列3，7，11，20，45，77，90，请分别写出折半查找 10 和查找 99 的过程，并求出 ASL（4 分）6.已知序列34，17，6，29，33，11，80，37请用快速排序的方法进行排序，并给出详细过程。（4 分）五、算法填空（每空 5 分，共 20 分）01 1001 101 10001 11 10001 101 1001 1001 11 11 1000001 11 11 1004（1）按先序次序输入二叉树中的结点值(字符)构造二叉树 Status CreateBiTree(BiTree&T)char ch;read(ch);if(ch=)T=NULL;else T=(BiTree)malloc(sizeof(BiTNode);(1);CreateBiTree(T-lchild);(2);return OK;（2）在顺序表 L 的第 i 个元素之前插入新的元素 eStatus ListInsert(SqList&L,int i,ElemType e)if(i L.length+1)return ERROR;/插入位置不合法 for(j=L.length;ji;j-)(3);L.elemi-1=e;/插入 e (4);return OK;/ListInsert_Sq 六、写算法（共 15 分）1.请写出链式存储的线性表中，删除第 i 个位置数据元素的实现算法。（给出相应的结构体定义，关键部分给出注释。）20112012 学年第一学期期末考查数据结构标准答案一、选择（每题 1 分，共 10 分）1-5 DBBBB 6-10 ACCDB5二、填空（每空 1 分，共 15 分）1.时间复杂度，空间复杂度 2.FIFO，LIFO 3.Q.rear=Q.front 4.7 5.8 6.O(n2)，稠密图7.极大连通子图 8.n(n-1)9.n-1 10.集合结构，树形结构，图状结构三、判断题（每题 1 分，共 10 分）1.2.3.4.5.6.7.8.9.10.四、简答题（共 30 分）1.(1)在二叉树的第 i 层上至多有 2i-1 个结点；(i1)(2)深度为 k 的二叉树上至多含 2k-1 个结点（k1）；(3)对任何一棵二叉树，若它含有 n0 个叶子结点、n2 个度为 2 的结点，则必存在关系式：n0=n2+1；(4)具有 n 个结点的完全二叉树的深度为 log2n+1。(5)若对含 n 个结点的完全二叉树从上到下且从左至右进行 1 至 n 的编号，则对完全二叉树中任意一个编号为 i 的结点：若 i=1，则该结点是二叉树的根，无双亲，否则，编号为 i/2 的结点为其双亲结点；若 2in，则该结点无左孩子，否则，编号为 2i 的结点为其左孩子结点；若 2i+1n，则该结点无右孩子结点，否则，编号为 2i+1 的结点为其右孩子结点。评分标准：答对 5 条中的 4 条得 4 分。2.深度优先遍历序列：abefdc6深度优先生成树：评分标准：深度优先遍历序列 3 分，深度优先生成树 3 分。3.(1)T-next-next=P-next;(2)Q=T;While(Q-!=P)Q=Q-next;Q-next=P-next;free(P);评分标准：回答（1）或者（2）都正确。4.ABCDEF5.11，3，7，77，20，45，90查找过程：11，3，7，77 或者 90，45，20，776.34，17，6，29，33，11，80，37d=5 11，17，6，29，33，34，80，37d=3 11，17，6，29，33，34，80，37d=1 6，11，17，29，33，34，37，80五、算法填空（每空 5 分，共 20 分）1.(1)visit(T-data);或者printf(T-data);(2)PreOrderTraverse(T-rchild);2.(1)return mid;(2)high=mid-1;cdfeba7六、写算法（共 15 分）/删除表 L 中第 i 个元素，结果用 e 返回，操作成功返回 OK，失败时返回 ERROR Status ListDelete(SqList&L,int i,ElemType&e)if(iL.length)return ERROR;e=L.elemi-1;for(int j=i+1;j=L.length;j+)L.elemj-2=L.elemj-1;L.length-;return OK;