2022年2021~2021学年《数据结构》A .pdf

《2022年2021~2021学年《数据结构》A .pdf》由会员分享，可在线阅读，更多相关《2022年2021~2021学年《数据结构》A .pdf（8页珍藏版）》请在得力文库 - 分享文档赚钱的网站上搜索。

1、1 华侨大学数据结构试卷（A）系别：班级：学号：姓名：考试日期：年月日题号一二三四五总分得分一、选择题（每题1.5 分，共 15 分）1、若长度为n 的线性表采用顺序存储结构，删除它的第i 数据元素之前，需要先依次向前移动（）个数据元素。A.n-i B.n+i C.n-i-1 D.n-i+1 2、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（） 。A.顺序表B.用头指针表示的单循环链表C. 用尾指针表示的单循环链表D.单链表3、将一个递归算法改为对应的非递归算法时，通常需要使用（） 。A. 栈B. 队列C. 循环队列D. 优先队列4、设有两个串t 和 p，求 p 在 t 中首

2、次出现的位置的运算叫做（） 。A. 求子串B. 模式匹配C. 串替换D. 串连接5、设有一个二维数组A2030，以行为主序储存，假设A00存放位置在64410，每个元素占据一个储存空间，则A45存储在（）位置。A. 69210B.62610C.76910D. 724106、由权值分别为3,8,6,2,5的叶子结点生成一棵赫夫曼树，它的带权路径长度WPL 为（） 。A. 24 B. 48 C. 72 D. 53 7、 一个无向连通图的生成树是含有该连通图的全部顶点的（） 。A.极小连通子图B.极小子图C.极大连通子图D.极大子图8、具有 n 个顶点的有向完全图可包含（）条有向边。An-1 Bn

3、Cn(n-1) 2 Dn(n-1)9、设有一个用开放定址法的线性探测再散列处理冲突的哈希表如下：0 1 2 3 4 5 6 7 8 9 10 13 25 80 16 17 6 14 哈希函数为H（key）=key%11 ，若要查找关键字14 的记录，所需的探测次数是（） 。A. 3 B. 6 C. 7 D. 9 10、在下列排序方法中，不稳定的排序是（） 。A. 直接插入排序 B. 归并排序C. 快速排序D.冒泡排序名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 1

4、 页，共 8 页 - - - - - - - - - 2 二、填空题（每空1 分，共 10 分）1、数据的逻辑结构被分为集合、和网状结构四种。2、在一个稀疏矩阵中，每个非零元素所对应的三元组包括该元素的、和值三项。3、一棵高度为5 的二叉树中最少含有个结点，最多含有个结点； 一棵高度为5 的完全二叉树中，最少含有个结点，最多含有个结点。4、在线性表中采用折半查找法（二分查找法）查找一个数据元素，线性表中元素应该按值有序，并且采用存储结构。5、若对序列 (49 ， 38，65，97，76，13，27，50) 采用简单选择排序法排序，则第二趟结束后序列的状态是。三、解答题（每题5 分，共 30 分

5、）1、指出下面算法中，带下划线语句的语句频度，并估计该算法的时间复杂度。int Sum_fact(int n) int s=0,m,k,t; for(m=1;m=n;m+) t=1; for(k=1;k=1 & order=Get_length(list) )/ Get_length(list)返回表 list 的长度coutnext; int num=1; while(numnext; cout name ” ,”age ” ,”scoreendl; 2、阅读下面算法，指出该算法的功能。Status fun2(char *str) Stack T; Queue Q; char ch1, ch

6、2; int i ; InitStack （T）; InitQueue(Q); for ( i = 0; stri != 0 ; i+) Push( T, stri ); EnQueue( Q, stri ); for ( i =1; i lchild ！= NULL & T-rchild != NULL ) return 1; else return (fun3( T-lchild) + fun3 ( T-rchild); 五、算法设计题（共30分）（说明：你所设计算法中若需调用基本操作，需给出实现该基本操作的算法）1、 设 L 为带头结点的单链表头指针且链表长度大于2，试设计算法删除链表L

7、 的首结点，并将该结点插入到链表 L 的尾结点之后。 （10 分）2、设二叉排序树bt 以二叉链表为存储结构，试设计算法删除二叉排序树bt 中值最大的结点。 （8 分）3、试设计算法Create_dg(Mgraph g1,Algraph &g2) ，将数组表示的有向图g1，转换成邻接表表示的有向图g2。 （12 分）#define INFINITY INT_MAX #define MAX_NUM 20 /图的数组（邻接矩阵）存储表示：typedef struct ArcCell VRType adj; InfoType *info; ArcCell; typedef struct Vertex

8、Type vexsMAX_NUM ; ArcCell arcsMAX_NUM MAX_NUM; int vexnum , arcnum; MGraph; /图的邻接表存储表示：typedef struct ArcNode int adjvex; struct ArcNode *nextarc; ArcNode; typedef struct VNode VertexType data; ArcNode *firstarc; VNode; typedef struct VNode verticesMAX_NUM; int vexnum , arcnum; ALGraph; 名师归纳总结 精品学习

9、资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 4 页，共 8 页 - - - - - - - - - 5 A 卷 参考答案一、选择题（共15 分，每小题 1.5 分）题号1 2 3 4 5 答案C 题号6 7 8 9 10 答案二、填空题（共10 分，每小题 1 分）1. 2. 3. 4. 5. 三、解答题（共30 分，每小题 5 分）1. t=1; 的语句频度是n-（ 1 分）t*=k; 的语句频度是n(n+1)/2-(2分) 该算法的时间复杂度是O(n(n+1)/2)=O(n2)-

10、(2分) 2. 可以得到D,C,E,B,A的出栈序列，其出栈操作序列是：push,push,push,push,pop,pop,push,pop,pop,pop-（2.5 分）不能得到C,D,A,B,E的出栈序列 , 因为要先得到C,D 的出栈子序列，则A,B 必已进栈。由栈的后进先出特性， B必先于 A出栈，因此不可能得到C,D,A,B,E 的出栈序列。-（2.5 分）3. 该二叉树的后序遍历序列为：DBCAHJKIGFE （2 分） ，中序线索二叉树（不带头结点）为：（3 分）名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料

11、- - - - - - - - - - - - - - - 第 5 页，共 8 页 - - - - - - - - - 6 4.无向图 G的邻接表表示如下:(2分) 从 A出发的 bfs 序列是： A,B,C,E,D,F (1.5分) bfs 生成树是： (1.5分) 5判定树（ 2 分）ASLsucc=141114iiC= 114(1+2*2+3*4+4*7)=4514（1.5 分）1 3 0 2 3 1 2 4 5 0 3 5 A B C D E F 0 1 2 3 4 5 1 2 4 0 3 4 7 3 11 1 5 2 4 6 9 13 8 10 12 14 名师归纳总结 精品学习资料

12、 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 6 页，共 8 页 - - - - - - - - - 7 ASLunsucc=5915150115iic=115(3*1+4*14)=5915（1.5 分）6.快速排序算法进行排序时第一趟快速划分的详细过程如下（5 分）48 70 33 65 24 56 12 92 86 22 22 70 33 65 24 56 12 92 86 22 33 65 24 56 12 92 86 70 22 12 33 65 24 56 92 86 70 22

13、 12 33 24 56 65 92 86 70 22 12 33 24 56 65 92 86 70 22 12 33 24 48 56 65 92 86 70 四、算法阅读题（共15分，每小题 5 分）1. 根据给定的位序order，返回第order 个元素所在位置的指针；若链表中没有第order 个元素，则返回 NULL 。2. 判断字符串是不是回文（对称）。3. 统计二叉树T 中所有结点的个数五、算法设计题（共30分）1void def_f_ins_l(Linklist &l) -1分 /删除首结点，插入在尾结点之后 p = l-next; -1分 while ( p-nexet) p

14、 = p-next; /p指向尾结点-3分 q = l-next; /q指向首结点-1分 l-next = q-next; / 删除-2分 p-next = q; / 插入-1分 q-next = NULL; / 或者 q-next=p-next; p-next = q; -1分/del_f_ins_l 2.Status del_max(BiTree &bt) -1分 /删除二叉排序树bt 中值最大结点 if (!bt) return ERROR; / 空树 p = bt; if (bt-rchild = NULL) /根无右子树-2分bt = bt-lchild; p-lchild = NU

15、LL;/此语句可不要free(p); 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 7 页，共 8 页 - - - - - - - - - 8 else while(p-rchild != NULL)/p移至最右下结点q = p; p = p-rchild; if(p-lchild != NULL)/有左子树-5分q-rchild = p-lchild; else q-rchild = NULL;/无左子树free(p); /del_max 3.Status Cr

16、eate_dg(Mgraph g1.Algraph &g2) -1分/ 将数组表示的有向图g1 转换成邻接表表示的有向图g2 g2.vexnum = g1.vexnum; g2.arcnum = g1.arcnum; -1分for(i=0;ig1.vexnum;+i)/生成 g2 的表头向量-3分g2.verticesi.data = g1.vexsi; g2.verticesi.firstarc = NULL; for(i=0;ig1.vexnum;+i)/遍历 g1 的邻接矩阵-7分for(j=0;jadjvex = j; / 生成表头结点p-nextarc = g2.verticesi.firstarc; / 插入g2.verticesi.firstarc = p; /if /for-i return OK ；Create_dg 名师归纳总结 精品学习资料 - - - - - - - - - - - - - - -精心整理归纳 精选学习资料 - - - - - - - - - - - - - - - 第 8 页，共 8 页 - - - - - - - - -