《东北大学 数据结构II 试卷(作业考核 线上1)A 卷 孟凡荣》由会员分享，可在线阅读，更多相关《东北大学 数据结构II 试卷(作业考核 线上1)A 卷 孟凡荣（5页珍藏版）》请在金锄头文库上搜索。
1、东 北 大学 继 续 教 育 学 院 数据结构II 试 卷(作业考核 线上1) A卷学习中心： 院校学号： 姓名 （共 6 页) 总分题号一二三四五六七八九十得分一、单选题(共30题,每题2分)A1抽象数据类型的三个组成部分分别为A数据对象、数据关系和基本操作 B数据元素、逻辑结构和存储结构 C数据项、数据元素和数据类型 D数据元素、数据结构和数据类型B2.要求相同逻辑结构的数据元素具有相同的特性,其含义为A 数据元素具有同一的特点. 不仅数据元素包含的数据项的个数相同,而且其对应数据项的类型要一致. 每个数据元素都一样 仅需要数据元素包含的数据项的个数相同 3.下列各式中，按增长率由小至大的
2、顺序正确排列的是,！,2n ,n3/2 n,2n，nlog，210 C.2n,log n，nogn,n/2 D210,logn,2n,nnB4. 在下列哪种情况下，线性表应当采用链表表示为宜 A.经常需要随机地存取元素 B经常需要进行插入和删除操作 .表中元素需要占据一片连续的存储空间 D.表中元素的个数不变C 设指针p指向双链表的某一结点，则双链表结构的对称性是A.p-rior-ext=p-nex-next; B. ppr-pror=p-nxt-po；C. p-prior-next=- ext-pr; D pnetnext=p-proprior; 6 已知指针p和q分别指向某带头结点的单链表
3、中第一个结点和最后一个结点。假设指针s指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为 snext=q；p-nex=s-next; B s-ext=；q-nes-next；C. pnext=-ex；snex=q;. qetsnet;s-net=；A7 栈和队列的共同特点是.只允许在端点处插入和删除元素B都是先进后出 C.都是先进先出.没有共同点 D 8.对于链队列,在进行插入运算时 A. 仅修改头指针 . 头、尾指针都要修改 .仅修改尾指针 D头、尾指针可能都要修改B 9.设有一个顺序栈的入栈序列是1、2、3,则3个元素都出栈的不同排列个数为 A 5 C. 6 .D 1
4、0.设一个栈的输入序列为，D，则借助一个栈所得到的输出序列不可能是A.，C,D B,C,AC. ,C，B . D，,B,C 1.表达式*(+)-d的后缀表达式是 A.acd+- B.bc*+d c+*d- D.-*acdB 12某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是A空或只有一个结点 .高度等于其结点数 任一结点无左孩子 .任一结点无右孩子B13下面的说法中正确的是 (1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。 ()按二叉树定义,具有三个结点的二叉树共有6种。A(1），（2） B.() C.(2) D（），（2)都错B 1树有先序遍历和后序遍历,树可以转化为对
5、应的二叉树。下面的说法正确的是 A树的后序遍历与其对应的二叉树的先序遍历相同 B树的后序遍历与其对应的二叉树的中序遍历相同C.树的先序序遍历与其对应的二叉树的中序遍历相同 D以上都不对D 15下列说法正确的是 (1)二又树按某种方式线索化后,任一结点均有前趋和后继的线索 (2)二叉树的先序遍历序列中,任意一个结点均处于其子孙结点前 （3)二叉排序树中任一结点的值大于其左孩子的值，小于右孩子的值A.(1）()(3) B.(1）(2) (1)() D都不对D 16. 二叉树的第k层的结点数最多为 A.-1 B.2K+1 C.2K-1 . 2-1D 17.以下说法不正确的是 A.无向图中的极大连通子
6、图称为连通分量 .连通图的广度优先搜索中一般采用队列来暂存刚访问过的顶点 C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D.有向图的遍历不可采用广度优先搜索B18有向图G用邻接矩阵A存储，则顶点i的入度等于A中A.第i行1的元素之和 B. 第i列1的元素之和C第行0的元素个数 D. 第i列非0的元素个数 19 设有6个结点的无向图，该图确保是一个连通图的有效边条数至少应是5 .6 C. D.8 20.下图的邻接表中，从顶点V1出发采用深度优先搜索法遍历该图，则可能的顶点序列是A. V1V2V3V4V5 BV1V2V3V5V4C. VV43VV2 D.V1V3V4V5V2 2.关键路径
7、是事件结点网络中 A从源点到汇点的最长路径 .从源点到汇点的最短路径 C最长的回路 D最短的回路A 22设哈希表长为1,哈希函数H(key)=ke11,表中已有数据的关键字为15,8，1，8，四个，现将关键字为4的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是 A.8 3 C5 9D 23.在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为,并已知A的左孩子的平衡因子为0,右孩子的平衡因子为，则应调整以使其平衡,所作的平衡旋转是A. L型 B. LR型 C. RL型 .R型 2下列排序算法中,在待排序数据已基本有序时,效率最高的排序方法是 插入排序 B选择排序 C快速排序
8、 .堆排序A 2.下列排序算法中，时间复杂度不受数据初始状态影响,恒为0(nlog2)是A.堆排序 . 冒泡排序 C. 直接选择排序 快速排序B 6 有一程序段:i=;WHILE(ifon-nex=QraNULL B. Q-ront=ralNUL C.Q-real=Qfont=U D. Q-a-next=fronN A2 有向图G可拓扑排序的判别条件是A. 不存在环 . 存在环 C.存在入度为零的结点 D. 存在出度为零的结点 C 2 对个记录的文件进行快速排序，所需要的辅助存储空间 A. （） B. O（n) . (1og2n) . O（n2） 30 下列排序算法中，在待排序数据已基本有序时
9、，效率最高的排序方法是 A插入排序 选择排序 .快速排序 .堆排序二、综合题(共4题，每题10分)1、阅读算法，在横线处填入语句或注释。oid xchne_L(Linlit L，intm) / 带头结点的单链表中前m个结点和后n个结点的整体互换 i (m & L-next ) / 链表非空 -nxt； (1）/ k取值 whil(k & p) /(2) = -next；; /wile if （p& （3） / !=0 时才需要修改指针 h = -next; / 以指针 ha记a1结点的位置 next= p-ext; / 将 b1 结点链接在头结点后 p-next （4）; / 设am的后继 q = Lnex; / 令q指向 b1结点 while (q-ne） = qext; / 查找b 结点 q-ext (5）/将第 a1 结点链接到 bn 结点之后 / f(p) / (m) / exchge 答案：()k=l；(2）查找第a个结点
