数据结构II试卷B(孟凡荣)20)

1、实用标准文案东北大学继续教育学院数据结构II 试 卷（作业考核 线上） B 卷学习中心：院校学号：姓名（共页）总分题号一二三四五六七得分一、单选题（每小题2分，共10小题，20分）A 1 .抽象数据类型的三个组成部分分别为A .数据对象、数据关系和基本操作B .数据元素、逻辑结构和存储结构C .数据项、数据元素和数据类型D .数据元素、数据结构和数据类型D 2 ,下列各式中，按增长率由小至大的顺序正确排列的是A,石，n!, 2n, n3/2B.n3/2,2n, nlogn, 2100C.2n, log n , nogn, n3/2D.21°°,logn, 2n, n nA

2、3.已知指针p和q分别指向某单链表中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在 s所指结点之后插入上述链表应执行的语句为A. q->next=s->next； s->next=p ；B. s->next=p； q->next=s->next ；C. p->next=s->next； s->next=q ；D. s->next=q； p->next=s->next ；C 4 ,二维数组A2010采用行优先的存储方法，若每个元素占2个存储单元，且第1个元素的首地址为200,则元素A89的存储地址为A.

3、 374B. 576C. 378D. 580B 5 .设有一个顺序栈的入栈序列是 a、b、c,则3个元素都出栈的可能不同排列个数为A . 4B. 5C. 6D. 7D 6.设树T的度为4,其中度为1, 2, 3和4的结点个数分别为4, 2, 1, 1则T中的叶精彩文档子数为A . 5B.6C . 7D.8C 7 .以下说法不正确的是A .无向图中的极大连通子图称为连通分量B .连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点C .图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D .有向图的遍历不可采用广度优先搜索8 8.假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键

4、字都是同义词， 则查找其中最后插入的关键字时，所需进行的比较次数为A. n-1B. nC. n+lD. n+2B 9 .设置溢出区的文件是A .索引非顺序文件B. ISAM文件C . VSAMC件D.顺序文件A 10.已知一组关键字为25,48,36,72,79,82,23,40,16,35,其中每相邻两个为有序子序歹I。对这些子序列进行一趟两两归并的结果是A.25,36,48,72,23,40,79,82,16,35B.25,36,48,72,16,23,40,79,82,35C.25,36,48,72,16,23,35,40,79,82D.16,23,25,35,36,40,48,72,7

5、9,82二、填空题（每小题1分，共10小题，10分）11 .下面程序段中带下划线的语句的执行次数的数量级是（log 2n）。i=1 ； WHILE（i<n） i=i*212 .假设带头结点的非空单循环链表中仅设尾指针L,则在第1个结点之前插入指针s所指结点的语句依次是 （s->nest=L->next->next ； L->next->next =S ）。13 .无表头结点的链队列 Q为空的条件是（Q->real=Q->front=NULL ）。14 .设Q0.N-1为循环队列，其头、尾指针分别为 P和R,则队Q中当前所含元素个数为 （R-P+N

6、） % N）。15 . 一棵含999个结点的完全二叉树的深度为（10）。16 .在AOV网中，存在环意味着某项活动以自己为先决条件；对程序的数据流图来说，它表明存在（死循环）。17 .有向图G可拓扑排序的判别条件是（不存在环）。18 .如果结点A有3个兄弟，而且B是A的双亲，则B的度是（4）。19 .应用回溯与分支限界法解决实际问题时，在搜索过程中利用判定函数，也称为（.限界函数 ）。20 .若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是（4231 ）。三、应用题（每小题6分，共5小题，30分）21 .比较线性表和栈的基本操作的

7、不同点。主要区别是对插入和删除操作的限制。如线性表允许在表内任一位置进行插入和删除；而队列只允许在表尾一端进行插入，在 表头一端进行删除；所以也称队列为受限的线性表。表头为队列头；表尾为队列尾。插入删除线性表 Insert(L,i,x)Delete(L,i)(1 <i <n+1)(1 <i <n)队列 Insert(L,n+1,x) Delete(L,1)22 .有一个二叉树按层次顺序存放在一维数组中，如下图所示: 试求：(1)该树的后序遍历序列。(2)画出该树的后序线索树。1 2 3 4 5 6 7 8 9 10 11ACBED(1)后序遍历序列C E D B A(2

8、)后序线索树23 .分析顺序查找算法的“监视哨”设置作用为了考虑查找不成功的情况，在每次进行关键字的比较前，首先要判断循环变量 i是 否数组越界，这对算法来说是必要的。如果每步省略数组下标是否越界的判断，则可以 大大提高算法运行的效率。为此，可以利用预留的0号单元，作为所设的“监视哨”控制循环变量i的出界。假设数据从后向前比较，监视哨设在数组低端L.elem 0 = k将算法中的判断语句while (i <= L.length &&L.elem i != k) +i;改为 while (L.elem i != k) -i;这样，当在查找表中不存在其关键字等于给定值的数据元

9、素时，i必等于0,并且这样的处理并不影响查找成功的情况。24 .又t n个整数的序列进行直接选择排序。(1)算法描述。(2)并给出实例(52 49 80 36 14 58 61 23)的排序过程。答：(1)直接选择算法描述：1 第1趟，从n个记录中，经过比较选出关键字值为最小的记录，并与第 1个记录交精彩文档实用标准文案换位置。2 第2趟，从余下的n-1个记录中选择出当前关键字最小的排序，并与第 2个记录 交换位置。3 第i趟，在无序的第i个到第n个的n-i+1个记录中选出关键字最小的记录，与 第i个记录进行互换。4 以此类推，直至第n-1趟排序结束。(2)初始状态52 49 80 36 14

10、 58 61 23i=114 498036525861 23_i=214 238036525861 49_i=314 23368052586£ 49i=41423364952 586180_i=51423364952 586180i=61423364952 586180i=71423364952 586180排序结果14 23 36 49 52 58 61 80 25 .已知有一个10个顶点的连通图，顶点编号为1至10,其边的关系集合表示为(1,2)(1, 3), (1, 8), (2, 4),试求：画出该连通图及以顶点(3, 9), (3, 10), (5, 7), (6, 7),

11、 (7, 8), (8, 9) , 1为根的深度优先生成树。四、算法阅读题(本题10分)26 .设计算法实现以链表作存储结构，将线性表中前m个元素和后n个元素进行整体互换，即(ai,a m,b 1,b n)改变成(b i,bn,a 1,am)。阅读算法，在横线处填入语句或注释。void exchange_L( Linklist &L/本算法实现单链表中前if ( m && L->next ) /p = L->next;(1)while( k< m && p ) / p = p->next; +k; / while,int m )

12、m个结点和后n个结点的整体互换 链表不空且(2)精彩文档if (p &&(3) ) / n!=0时才需要修改指针ha = L->next; /以指针ha记a1结点的位置(4) = p->next; / p->next = NULL; / q = L->next; / while (q->next)q = q->next; / q->next = ha; / / if(p) / if(m) / exchange，将b1结点链接在头结点之后设am的后继为空令q指向b结点查找bn结点(5)答：(1) k = 1;(2)查找第am个结点(3)

13、p->next(4) L->next(5)将第a1结点链接到bn结点之后五、算法阅读题(本题10分)27 .设任意n个整数存放于数组A(1:n)中，阅读算法，指出功能及分析指针i和j的作用 void Arrange(int A口,int n) / n个整数存于数组A中int i=0,j=n-1,x; /数组下标从0开始while(i<j)while(i<j && Ai>0) i+;while(i<j && Aj<0) j-;if(i<j) 交换 Ai 与 Ajx=Ai; Ai+=Aj; A-=x;/ if/ whi

14、le/Arrange(1)功能：(2)指针i和j的作用：六、算法设计题（本题10分）28 .设计算法purge_Sq实现删除顺序表SqList中重复元素，指出其算法的时间复杂度void purge_Sq( SqList &L ) /删除顺序表L中的重复元素k = -1;/ k指示新表的表尾for (i=0; i<L.length; +i) /顺序考察表中每个元素j=0;while(j<=k && L.elemj!=L.elemi)+j; /在新表中查询是否存在和L.elemi相同的元素if ( k=-1 | j>k )/ k=-1表明当前考察的是第一个

15、元素L.elem+k = L.elemi; / forL.length = k+1;/修改表长 / purge_Sq此算丽时间复杂度为O (L.length 2 )。七、算法设计题（本题10分）29.设计算法从图的邻接表结构转换成邻接矩阵结构的算法 答：1.#include<stdio.h>2.#include<string.h>3.#include<stdlib.h>4.5.int a100100;/邻接矩阵的载体6.7.typedef structArcN adjvex;9.struct ArcNode *nextarc;10. ArcN

16、ode; / 表结点11.12. typedef struct VNode13. char data;14. ArcNode *firstarc;15. VNode,AdjList20; / 头结点16.17. typedef struct 18. AdjList vertices;19. int vexnum,arcnum;20. ALGraph; / 邻接表21.22. int LocateVex(ALGraph G,char e)23. 0.31.32.int i;for (i=0;i<G.vexnum;i+)if (G.verticesi.d

17、ata=e) return i; / 找到后return -1;33. 34.35. void CreatAdList(ALGraph &G)36. /根据输入的有向图 G的顶点数及边数，建立图37. int i,j,k;38. char v1,v2;39. ArcNode *s,*p;40.G的邻接表3.54.55.scanf( "%d%d"&G.vexnum,&G.arcnum); getchar();for (i=0;i<G.vexnum;i+) / 初始化头结点

18、scanf( "%c" ,&G.verticesi.data);getchar();G.verticesi.firstarc=NULL;for (i=0;i<G.vexnum;i+) / 输出一遍这些头 printf( "%c " ,G.verticesi.data);printf( "n");for (k=0;k<G.arcnum;k+)/输入边4.95.96. 97.56.scanf( "%c %c",&v1,&v2);57.getchar();58.i=LocateVex(G,v1);59.j=LocateVex(G,v2);60.s= (ArcNode *)malloc( sizeof (ArcNode);61.s->adjvex=j;62.s->nextarc=NULL;63.p=G.verticesi.firstarc;64.if (!p)65.66.G.verticesi.firstarc= s;67.68.else69. 70. while (p->nextarc)71. p=p->