《2022年《数据结构》期末考试题及答案 .pdf》由会员分享，可在线阅读，更多相关《2022年《数据结构》期末考试题及答案 .pdf（6页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、1 2011-2012 学年第一学期期末考查数据结构试卷（答案一律写在答题纸上，在本试卷上做答无效）一、选择（每题1 分，共 10 分）1.长度为 n 的线性表采用顺序存储结构，一个在其第i 个位置插入新元素的算法时间复杂度为（D）A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4， 3，2，1 的顺序入栈，下列哪一个是合法的出栈序列？（D）A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4 的结点个数分别是4、2、1、2，则树中叶子个数为（B ）A.8 B.9 C.10 D.11 4.设 森林F
2、对 应 的 二 叉树B 有m 个 结 点 ， B 的 右 子 树 结 点 个 数为n， 森林F 中第 一棵 树 的结 点 个 数 是（ B ）A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10 个度为 2 的结点， 5 个度为 1 的结点，则度为0 的结点个数是（B）A.9 B.11 C.15 D.不确定6.下列哪一个方法可以判断出一个有向图是否有环。（A）A.深度优先遍历B.拓扑排序C. 求最短路径D.求关键路径7.第 7层有 10 个叶子结点的完全二叉树不可能有（B ）个结点。A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其
3、他三个序列构造的结果不同的是（B）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 则采用的排序方法是（B ）A.选择排序B.起泡排序C.快速排序D.插入排序10.对线性表进行折半
4、查找时，要求线性表必须（D）A.以顺序方式存储B.以顺序方式存储，且数据元素有序名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 6 页 - - - - - - - - - 2 C.以链接方式存储D.以链接方式存储，且数据元素有序二、填空（每空1 分，共 15 分）1.数据结构中评价算法的两个重要指标是时间复杂度、空间复杂度。2.在单链表中，指针P 所指结点有后继的条件是p-next.data!=null 。（结点构成：data 和 next）3.栈的特点是先进后出。4.判
5、断循环队列是否队满的条件表达式是。5.完全二叉树中的结点个数为n，则编号最大的分支结点的编号为2n-1 。6.如果 A 有 7 个兄弟，而B 是 A 的双亲，则B 的度是2 。7.如果二叉树中有20 个叶子节点，30 个度为 1 的结点，则该二叉树的总结点数为。8.设二叉树中每个结点均用一个字母表示，若一个结点的左子树或者右子树为空，用.表示。现前序遍历二叉树的结点序列为 ABD.G CE.H.F. ，则中序遍历二叉树的结点序列为。9.若用 n 表示图中的顶点数目，则有条边的无向图被称为完全图。10.如果具有n 个顶点的图是一个环，则它有棵生成树。11.克鲁斯卡尔算法的时间复杂度是，它适合求图
6、的最小生成树。12.顺序查找n 个元素的线性表，若查找成功时的平均查找长度为。13.高度为 5 的完全二叉树，其结点最少有个。14.直接插入排序中使用的监视哨的作用是。三、判断题（每题1 分，共 10 分）1.算法独立于具体的程序设计语言，与具体的计算机无关。（）2.线性表采用链式存储时，结点内部的存储空间可以是不连续的。（）3.栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。（）4.哈夫曼树的结点总个数一定是偶数。（）5.已知二叉树的先序遍历序列和中序遍历序列，可以画出这棵二叉树（）。6.有 e条边的无向图，在其对应的邻接表中有e 个结点。（）7.连通分量指的是无向图的极大连通子图。
7、（）8.在哈希表的查找过程中的“比较”操作是无法避免的。（）9.完全二叉树肯定是平衡二叉树。（）10.堆排序是稳定的排序算法。（）名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 6 页 - - - - - - - - - 3 四、简答题（共30 分）1. 线性结构的特点是？（4 分）2. 已知图的邻接矩阵存储如下所示，请根据该邻接矩阵画出对应的图，并给出从A 出发的广度优先搜索序列，以及相应的广度优先生成树。（6 分）A B C D E F A B C D E F 3.
8、已知一棵二叉树的后序遍历序列为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 分）（1）按先序次序输入
9、二叉树中的结点值(字符 )构造二叉树Status CreateBiTree(BiTree &T) char ch; read(ch); if( ch= ) T = NULL; else T = (BiTree)malloc(sizeof(BiTNode); (1) ; CreateBiTree(T-lchild); (2) ; 010010100011000101001001110000011100 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 6 页 - - - -
10、- - - - - 4 return OK; （2）在顺序表L 的第i 个元素之前插入新的元素e Status 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 个位置数据元素的实现算法。（给出相应的结构体定义，关键部分给出注释。）
11、20112012 学年第一学期期末考查数据结构标准答案一、 选择（每题1 分，共 10 分）1-5 DBBBB 6-10 ACCDB 二、填空（每空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 分）c d f e b a 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4
12、页，共 6 页 - - - - - - - - - 5 1.2. 3. 4. 5. 6. 7. 8. 9. 10. 四、简答题（共30 分）1. (1)在二叉树的第i 层上至多有2i-1 个结点；(i 1) (2)深度为k 的二叉树上至多含2k-1 个结点（ k1）；(3)对任何一棵二叉树，若它含有n0 个叶子结点、n2 个度为2 的结点，则必存在关系式：n0 = n2+1；(4)具有n 个结点的完全二叉树的深度为log2n +1 。(5)若对含n 个结点的完全二叉树从上到下且从左至右进行1 至 n 的编号，则对完全二叉树中任意一个编号为i 的结点： 若 i=1，则该结点是二叉树的根，无双亲，
13、 否则， 编号为i/2的结点为其双亲结点；若 2in，则该结点无左孩子，否则，编号为2i 的结点为其左孩子结点；若2i+1n，则该结点无右孩子结点，否则，编号为2i+1 的结点为其右孩子结点。评分标准：答对5条中的 4 条得 4 分。2. 深度优先遍历序列：abefdc 深度优先生成树：a-.b-c-e-f-d-c 评分标准：深度优先遍历序列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.5.11， 3，7，7
14、7，20，45，90 A B C D E F 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 6 页 - - - - - - - - - 6 查找过程： 11，3，7，77 或者 90，45，20，77 6.34，17，6，29，33， 11，80，37 d=5 11， 17，6， 29，33，34， 80，37 d=3 11， 17，6， 29，33，34， 80，37 d=1 6，11，17， 29，33，34， 37，80 五、算法填空（每空5 分，共 20 分）1
15、. (1)visit(T-data); 或者 printf(T-data); (2)PreOrderTraverse(T-rchild); 2.(1)return mid; (2)high=mid-1; 六、写算法（共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; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 6 页 - - - - - - - - -