《数据结构II试卷B20)》由会员分享，可在线阅读，更多相关《数据结构II试卷B20)（13页珍藏版）》请在金锄头文库上搜索。
1、东北大学继续教育学院数据结构II试 卷（作业考核 线上）B_卷学习中心:院校学号：姓名（共页）总分题号一二三四五六七得分一、单选题（每小题2分，共10小题，20分）A 1 .抽象数据类型的三个组成部分分别为A 数据对象、数据关系和基本操作B .数据元素、逻辑结构和存储结构C .数据项、数据元素和数据类型D .数据元素、数据结构和数据类型D 2 .下列各式中，按增长率由小至大的顺序正确排列的是A . Vn , n ! , 2n , n3/2B. n3/2 , 2n, nlogn , 2100C. 2n, log n , nlogn , n3/2D . 2100, logn, 2 n, nnA 3
2、.已知指针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. 374B.576C. 378D.580B 5 .设有一个顺序栈的入栈序列是 a、b、c,则3个元
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 .有向图的遍历不可采用广度优先搜索B 8假设在构建散列表时，采用线性探测解决冲突。若连续插入的n个关键字都是同义词， 则查找其中最后插入的关键字时，所需进行的比较次数为A. n-1B. nC. n+lD
4、. n+2B 9 .设置溢出区的文件是A 索引非顺序文件B. ISAM文件C . VSAM文件D 顺序文件A 10.已知一组关键字为25,48,36,72,79,82,23,40,16,35，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是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,79,82二、填空题（每小题1分，共10小题，10分）11.下面程序段中带下划线的语句的执行次数的
5、数量级是（log 2n）。i=1 ； WHILE（inest=L-next-next； L-next-next =S ）。13 .无表头结点的链队列 Q为空的条件是（Q-real=Q-front=NULL ）。14 .设Q0.N-1为循环队列，其头、尾指针分别为P和R,则队Q中当前所含元素个数为（R-P+N ） % N ）。15 .一棵含999个结点的完全二叉树的深度为（10）。16. 在AOV网中，存在环意味着某项活动以自己为先决条件；对程序的数据流图来说，它 表明存在（死循环）。17. 有向图G可拓扑排序的判别条件是（不存在环 ）。18 .如果结点A有3个兄弟，而且B是A的双亲，贝U B的
6、度是（4）。19 .应用回溯与分支限界法解决实际问题时，在搜索过程中利用判定函数，也称为（.限界函数 ）。20.若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得到的输出序列是(4231)三、应用题(每小题6分，共5小题，30分)21 .比较线性表和栈的基本操作的不同点。主要区别是对插入和删除操作的限制。如线性表允许在表内任一位置进行插入和删除；而队列只允许在表尾一端进行插入，在表头一端进行删除；所以也称队列为受限的线性表。表头为队列头；表尾为队列尾。插入删除线性表In sert(L,i,x)Delete(L,i)(1 i wn+1)(1 i n
7、)队列In sert(L ,n+1,x)Delete(L,1)22 .有一个二叉树按层次顺序存放在一维数组中，如下图所示: 试求：(1 )该树的后序遍历序列。(2) 画出该树的后序线索树。1234567891011ACBED(1) 后序遍历序列 C E D B A(2) 后序线索树A23 分析顺序查找算法的“监视哨”设置作用为了考虑查找不成功的情况，在每次进行关键字的比较前，首先要判断循环变量i是否数组越界，这对算法来说是必要的。如果每步省略数组下标是否越界的判断，则可以 大大提高算法运行的效率。为此，可以利用预留的0号单元，作为所设的“监视哨”控制循环变量i的出界。假设数据从后向前比较，监视
8、哨设在数组低端L.elem 0 = k将算法中的判断语句while (i next) /链表不空且p = L-n ext;(1)while( kn ext; +k; / whileif (p &(3) ) / n!=0时才需要修改指针ha = L-next;/ 以指针ha记ai结点的位置(4) = p-next; /将b1结点链接在头结点之后p-next = NULL;/设am的后继为空q = L-next; /令q指向b1结点while (q-n ext)q = q-next; /查找 bn 结点q-n ext = ha; /(5) / if(p) / if(m) / excha nge_L
9、答：(1)k = 1;(2) 查找第am个结点(3) p-next(4) L-next(5) 将第a1结点链接到bn结点之后五、算法阅读题(本题10分)27 设任意n个整数存放于数组A(1:n)中，阅读算法，指出功能及分析指针i和j的作用void Arran ge(i nt A,i nt n) / n个整数存于数组A中int i=0,j=n-1,x;/数组下标从0开始while(ij)while(i0)i+;while(ij & Aj0)j-;if(ij) / 交换 Ai与 Ajx=Ai; Ai+=Aj; Aj-=x;/ if/ while/Arra nge(1) 功能:(2) 指针i和j的作
10、用:六、算法设计题(本题10分)28 设计算法purge_Sq实现删除顺序表SqList中重复元素，指出其算法的时间复杂度void purge_Sq( SqList &L ) /删除顺序表L中的重复元素k = -1;/ k 指示新表的表尾for (i=0; ivL.le ngth; +i) /顺序考察表中每个元素j=0；while(jk )/ k=-1表明当前考察的是第一个元素L.elem+k = L.elemi; / forL.le ngth = k+1;/修改表长 / purge_Sq此算法的时间复杂度为0 (L.length 2 )。七、算法设计题(本题10分)29 设计算法从图的邻接表结构转换成邻接矩阵结构的算法。答：1.#include 2.#include 3.#include 4.5.int a100100; /
