《东北大学-数据结构II-试卷(作业考核-线上1)A-卷-孟凡荣.doc》由会员分享，可在线阅读，更多相关《东北大学-数据结构II-试卷(作业考核-线上1)A-卷-孟凡荣.doc（6页珍藏版）》请在金锄头文库上搜索。
1、东 北 大 学 继 续 教 育学 院数据结构试卷(作业考核 线上1）A卷学习中心:院校学号:姓名 （共 6 页) 总分题号一二三四五六七八九十得分一、单选题（共0题，每题2分) 1.抽象数据类型的三个组成部分分别为.数据对象、数据关系和基本操作 B数据元素、逻辑结构和存储结构 C.数据项、数据元素和数据类型 数据元素、数据结构和数据类型 2.要求相同逻辑结构的数据元素具有相同的特性，其含义为A 数据元素具有同一的特点B.不仅数据元素包含的数据项的个数相同，而且其对应数据项的类型要一致. 每个数据元素都一样D. 仅需要数据元素包含的数据项的个数相同D3.下列各式中，按增长率由小至大的顺序正确排列
2、的是A.,n！,n,n/2B.n32,2n,nlon,210 ，gn,ngn,n3/2D20，logn, 2n, nB 4. 在下列哪种情况下,线性表应当采用链表表示为宜 A经常需要随机地存取元素.经常需要进行插入和删除操作 C表中元素需要占据一片连续的存储空间D.表中元素的个数不变 5设指针p指向双链表的某一结点，则双链表结构的对称性是A p-prorex=pnext-next； B. -pior-prior-nextprir;C. -prr-nextp nex-pror; D. pex- p-pir-pror; D6.已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。假设
3、指针指向另一个单链表中某个结点，则在s所指结点之后插入上述链表应执行的语句为A.-ext=；p-net=s-next;B.s-ex=p；q-next=-net；Cp-nexts-next;s-n=；D-next=s-e;-ext=p；A7. 栈和队列的共同特点是A.只允许在端点处插入和删除元素B.都是先进后出都是先进先出D.没有共同点D 8. 对于链队列，在进行插入运算时. A. 仅修改头指针B. 头、尾指针都要修改 C. 仅修改尾指针D头、尾指针可能都要修改B 9设有一个顺序栈的入栈序列是、2、3,则3个元素都出栈的不同排列个数为.B5 C. 6 D71设一个栈的输入序列为A,B，C,D,则
4、借助一个栈所得到的输出序列不可能是A.A，B,C，D B.D，C，B，A C. A，C,D，B . D，A,B,CC 11.表达式a*（b+c)-d的后缀表达式是A.abcd*+-abc*d Cac+*d-D.*abdB 2.某二叉树的先序序列和后序序列正好相反,则该二叉树的特点一定是A. 空或只有一个结点 B.高度等于其结点数 C. 任一结点无左孩子 D.任一结点无右孩子B 13.下面的说法中正确的是 (1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。 ()按二叉树定义，具有三个结点的二叉树共有6种。.(1),(2) B() （2)（1),（2)都错B 1树有先序遍历和后序遍历,树可以
5、转化为对应的二叉树。下面的说法正确的是A树的后序遍历与其对应的二叉树的先序遍历相同 B树的后序遍历与其对应的二叉树的中序遍历相同C树的先序序遍历与其对应的二叉树的中序遍历相同D以上都不对D15.下列说法正确的是 (1）二又树按某种方式线索化后,任一结点均有前趋和后继的线索 (2)二叉树的先序遍历序列中,任意一个结点均处于其子孙结点前 (3)二叉排序树中任一结点的值大于其左孩子的值，小于右孩子的值A.（1)（2)（) (1）（2) ()()D.都不对 16 二叉树的第层的结点数最多为 k- B.2K+1 .2 D. 2-1D 7.以下说法不正确的是A.无向图中的极大连通子图称为连通分量 B连通图
6、的广度优先搜索中一般采用队列来暂存刚访问过的顶点 C图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D有向图的遍历不可采用广度优先搜索B 1有向图G用邻接矩阵A存储，则顶点i的入度等于A中A. 第行1的元素之和 B. 第i列1的元素之和C.第i行的元素个数 . 第i列非0的元素个数9. 设有6个结点的无向图,该图确保是一个连通图的有效边条数至少应是A5 B6 7 D.8 D 20.下图的邻接表中，从顶点V1 出发采用深度优先搜索法遍历该图，则可能的顶点序列是.V1V2VVV5B.V1V2V5VC.V143V52D.V1V4V5 A21.关键路径是事件结点网络中 A.从源点到汇点的最长路径 .
7、从源点到汇点的最短路径最长的回路 D最短的回路A22设哈希表长为14,哈希函数H(ke)key11，表中已有数据的关键字为1,3，61,8,四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是A.8 3 C.5 D.9D 23.在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知的左孩子的平衡因子为，右孩子的平衡因子为,则应调整以使其平衡，所作的平衡旋转是A LL型B. L型C.L型 D.R型 24下列排序算法中,在待排序数据已基本有序时,效率最高的排序方法是A插入排序 B.选择排序 C快速排序 D.堆排序A25下列排序算法中，时间复杂度不受数据
8、初始状态影响，恒为0(nlgn）是A 堆排序 B. 冒泡排序 C. 直接选择排序 . 快速排序 6. 有一程序段:i1;HILE(iront-nt=Qal=NULBQfrotrealNULC. -real=-fron=LL Q-ral-nxt=Q-rontNULL A28.有向图G可拓扑排序的判别条件是. 不存在环 B存在环C. 存在入度为零的结点 D. 存在出度为零的结点 C 29 对个记录的文件进行快速排序,所需要的辅助存储空间A. O(1) B. O（n) C. O(og2） D. （2）B 3.下列排序算法中，在待排序数据已基本有序时,效率最高的排序方法是A.插入排序 B选择排序 C.
9、快速排序 D堆排序二、综合题(共题，每题10分）31、阅读算法，在横线处填入语句或注释。void xcnge_L( Linl L，in ) /带头结点的单链表中前个结点和后n个结点的整体互换f ( &Lnext ) / 链表非空p =L-ext; （1)/ k取值whle（ knext;+k； / while i( & （)/ n！=0 时才需要修改指针ha = next; /以指针 ha 记a1结点的位置 -nxt=p-nxt；/ 将 b结点链接在头结点后p-ext =(4)； / 设的后继q L-nex;/ 令q 指向 b1结点hle （qnxt） q = q-next; /查找 bn结点
10、 qe （5）/将第a1结点链接到bn结点之后 / f() / if(m) exhaneL 答案:(1)kl；(2)查找第m个结点(3) p- n（4)- ext(5）将第al结点链接到bn结点之后.一个仅包含二元运算符的算术表达式，以二叉链表形式存储在二叉树T中，设计算法F实现求值,并指出遍历的方式。33.设计算法实现以逆邻接表为存储结构的有向图的拓扑排序。逆邻接表存储结构定义如下：顶点结构 表结点结构vetafirst aexnffirstarc答案:解:算法设计Ittopos(AGrG,ttp)/以逆邻接表为存储结构的有向图的拓扑排序op=;fr(=0;iGvnum；i+) for（p=
11、G.adistifirstedge;p;pnext)idutderee（，outdegree);/ 对各顶点求出度outdegreepdjex+； Inittack(S）；/初始化栈for(=0;i.Vnum；i+)if(utreei=0)ush(&S,i); /出度为零的顶点入栈while(!Stc(S)Pop(&,i）；rintf(Gdjlisivetx)；tvt+=i;for(p=djisti.firsedg；p;p next)jp jvex;otdgreej-; if(！outdegrej) Push(&j);/出度为零的顶点入栈/for/hilef(tpG.vnm）retrn0;/无环ee输出顶点拓扑排序序列for(i=0；j=tp-1；iG.vexnu/;i+-)/置逆输出em=tpvi;pv=tpvj;tp=tmp;/fretur 1；/leosr34 设哈希表长为13，采用线性探测法解决冲突,哈希函数定义为：H（key）=key13。试求：
