《东北大学 数据结构II 试卷(作业考核 线上1)A 卷 孟凡荣.doc》由会员分享，可在线阅读，更多相关《东北大学 数据结构II 试卷(作业考核 线上1)A 卷 孟凡荣.doc（5页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、东北 大学 继 续 教 育 学院 数据结构II 试卷(作业考核 线上1） A 卷学习中心： 院校学号: 姓名 (共 页) 总分题号一二三四五六七八九十得分一、单选题（共30题,每题2分）A 1.抽象数据类型的三个组成部分分别为A.数据对象、数据关系和基本操作 B数据元素、逻辑结构和存储结构 C数据项、数据元素和数据类型 D.数据元素、数据结构和数据类型B要求相同逻辑结构的数据元素具有相同的特性，其含义为A.数据元素具有同一的特点B.不仅数据元素包含的数据项的个数相同,而且其对应数据项的类型要一致C. 每个数据元素都一样D.仅需要数据元素包含的数据项的个数相同3下列各式中，按增长率由小至大的顺序
2、正确排列的是A，n！,2n ，n3/2 B.n3/2,n，nlog，100 C.2n,log n,lgn,n3/2 D0,lon,n，nn 4在下列哪种情况下，线性表应当采用链表表示为宜 A经常需要随机地存取元素 B.经常需要进行插入和删除操作 表中元素需要占据一片连续的存储空间 D.表中元素的个数不变C5设指针p指向双链表的某一结点，则双链表结构的对称性是A. -pir-nex=pet-nex; . prior-prior=pnet-pr；C. p-prir-exp- nex-ror; D. p-ext-net prio-prior; D6. 已知指针p和q分别指向某带头结点的单链表中第一个
3、结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为 -xt=q;next-xt； . s-tp；-next=s-nxt;. p-ext=snext；snext=q；. q-nxts-next；next=p；A 7. 栈和队列的共同特点是.只允许在端点处插入和删除元素B.都是先进后出 .都是先进先出D.没有共同点 8. 对于链队列，在进行插入运算时. . 仅修改头指针 B.头、尾指针都要修改 C. 仅修改尾指针 .头、尾指针可能都要修改B 9.设有一个顺序栈的入栈序列是、3,则3个元素都出栈的不同排列个数为 A4 .5 C. 6 D. 7D 1
4、.设一个栈的输入序列为A,B,C，D,则借助一个栈所得到的输出序列不可能是AA，B,C,D .，B,A C. ,C,D，B D，A，,CC 11表达式*(b+c)-d的后缀表达式是 A.abcd*- .c+d- Cac+*- D-+*abcdB12某二叉树的先序序列和后序序列正好相反,则该二叉树的特点一定是A 空或只有一个结点 .高度等于其结点数. 任一结点无左孩子 D任一结点无右孩子B13.下面的说法中正确的是 (1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。 (2)按二叉树定义,具有三个结点的二叉树共有6种。A.(1),() B() C() D.（1)，(2)都错B 14树有先序遍
5、历和后序遍历,树可以转化为对应的二叉树。下面的说法正确的是 A.树的后序遍历与其对应的二叉树的先序遍历相同 B树的后序遍历与其对应的二叉树的中序遍历相同C树的先序序遍历与其对应的二叉树的中序遍历相同 D以上都不对D 5.下列说法正确的是 (1)二又树按某种方式线索化后，任一结点均有前趋和后继的线索 (2)二叉树的先序遍历序列中,任意一个结点均处于其子孙结点前 （3)二叉排序树中任一结点的值大于其左孩子的值，小于右孩子的值A.（1)(2)(3) .(1)(） （1)(3) D.都不对D 16.二叉树的第k层的结点数最多为 A.k-1 B2 C.2K-1 D.2-1D 1以下说法不正确的是 A无向
6、图中的极大连通子图称为连通分量 .连通图的广度优先搜索中一般采用队列来暂存刚访问过的顶点 C图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D有向图的遍历不可采用广度优先搜索B18有向图用邻接矩阵存储,则顶点i的入度等于A中A. 第i行的元素之和 B. 第i列1的元素之和C 第i行0的元素个数 第列非0的元素个数19设有6个结点的无向图,该图确保是一个连通图的有效边条数至少应是.5 6 C.7 D.8 D 20.下图的邻接表中，从顶点V1出发采用深度优先搜索法遍历该图,则可能的顶点序列是A 1V2V45 B 1VV3VV4C. V1V43V5V D.V1V3VV5V2 A 2.关键路径是事
7、件结点网络中 A.从源点到汇点的最长路径 B.从源点到汇点的最短路径 C最长的回路 最短的回路 22设哈希表长为4，哈希函数H(y）=k%11,表中已有数据的关键字为15，38，61，84，四个，现将关键字为9的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是 A.8 B 5 9D 23在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0,右孩子的平衡因子为1,则应调整以使其平衡,所作的平衡旋转是A. LL型 .LR型 .RL型 D. R型B 24.下列排序算法中,在待排序数据已基本有序时,效率最高的排序方法是 A插入排序 B选择排序 C.快
8、速排序 .堆排序A 25.下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlog2n)是A. 堆排序 B 冒泡排序 C. 直接选择排序 D. 快速排序26.有一程序段：i1;WILE（ifront-xt=Q-al=NUL B Q-rn=QrealNL C. Qreal=Q-frnt=NULL DQrealnext-rontNULL 28. 有向图可拓扑排序的判别条件是A. 不存在环 B. 存在环 C. 存在入度为零的结点 D. 存在出度为零的结点 2 对n个记录的文件进行快速排序,所需要的辅助存储空间 .（1） B. (n） . (1ogn） D. O(2)B30. 下列排序算法中，
9、在待排序数据已基本有序时，效率最高的排序方法是 插入排序 .选择排序 C快速排序 D.堆排序二、综合题(共4题,每题1分)31、阅读算法，在横线处填入语句或注释。oi echange( Linlist &L，int ) / 带头结点的单链表中前m个结点和后n个结点的整体互换 f ( m &L-nex ） / 链表非空 p =-next; （）/ 取值 whil（ k & p ) /(2) p= -next；+k; / wile if （p & (3)） / ！=时才需要修改指针 h= L-next; / 以指针 ha 记a结点的位置 L-nex= p-next;/ 将 b1 结点链接在头结点后
10、 pext =（4); / 设am的后继 q = L-next; / 令 指向 1结点 whil (-next) = -next； / 查找 n 结点 q-next=（5)/将第a1 结点链接到n结点之后 /if(p) / f(m) / echange_L 答案：（1)kl;(2)查找第am个结点(3) nex() L- ext(）将第a结点链接到bn结点之后2.一个仅包含二元运算符的算术表达式,以二叉链表形式存储在二叉树中,设计算法F1实现求值，并指出遍历的方式。33.设计算法实现以逆邻接表为存储结构的有向图的拓扑排序。逆邻接表存储结构定义如下：顶点结构 表结点结构vedaafsn adje
11、xnfofirstarc答案：解:算法设计Int toposort (Arap G,int pv) 以逆邻接表为存储结构的有向图的拓扑排序op0；fo(i0;iGxnu；i+) r（p=G.adlisti.firstede；p;pext)finodegre(，oudegre); / 对各顶点求出度outdegreepadjvex+； niSac（S); /初始化栈for（i0；iG.Vexnm;i+）if(outderee=0) Psh(&S,）;/出度为零的顶点入栈while(!Stac(S)）o(,i);printf(adjlisti.vtex）;pvtop+i;(palsti.frste
12、de；;p next)j=padjex; udereej-;if(!oereej)Psh(&Sj); /出度为零的顶点入栈/fohileif(toG.vexu)eturn 0; /无环else /输出顶点拓扑排序序列for（i=;j=top1; Gexu2；i+j-）/ 置逆输出emp=tpvi；tpvi=pvj;tpvj=em; /for etur 1；/else/topsort. 设哈希表长为13，采用线性探测法解决冲突,哈希函数定义为:（y)ke13。试求：（1）填上依次插入关键字25，20,3,15，41,52，2,72，67后的哈希表。(2）计算等概率情况下，查找成功的平均查找长度。答案：(1）hsh表下标（地址)12356780112hsh表元素52154126720723625解决冲突过程 33 42 3 4578查找次数1124211（）查找成功的平均查找长度：(1*5 2 +*)/9 =15/9=1.5课程名称: 数据结构II