答案 东大 20年7月 数据结构II A卷 孟凡荣.docx
《答案 东大 20年7月 数据结构II A卷 孟凡荣.docx》由会员分享,可在线阅读,更多相关《答案 东大 20年7月 数据结构II A卷 孟凡荣.docx(7页珍藏版)》请在冰点文库上搜索。
东北大学继续教育学院
数据结构II试卷(作业考核线上1) A 卷
学习中心:
院校学号:
姓名
总分 题号
一
二
三
四
五
六
七
八
九
十
得分
(共 6 页)
一、单选题(共30题,每题2分)
[A]1.抽象数据类型的三个组成部分分别为A.数据对象、数据关系和基本操作B.数据元素、逻辑结构和存储结构C.数据项、数据元素和数据类型D.数据元素、数据结构和数据类型
[B]2.要求相同逻辑结构的数据元素具有相同的特性,其含义为
A.数据元素具有同一的特点
B.不仅数据元素包含的数据项的个数相同,而且其对应数据项的类型要一致
C.每个数据元素都一样
D.仅需要数据元素包含的数据项的个数相同
[D]3.下列各式中,按增长率由小至大的顺序正确排列的是A.n,n!
,2n,n3/2
B.n3/2,2n,nlogn,2100
C.2n,logn,nlogn,n3/2D.2100,logn,2n,nn
[B]4.在下列哪种情况下,线性表应当采用链表表示为宜
A.经常需要随机地存取元素
B.经常需要进行插入和删除操作
C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变
[C]5.设指针p指向双链表的某一结点,则双链表结构的对称性是
A.p->prior->next=p->next->next;
B.p->prior->prior=p->next->prior;
C.p->prior->next=p->next->prior;
D.p->next->next=p->prior->prior;
课程名称:
数据结构II
7
[D]6.已知指针p和q分别指向某带头结点的单链表中第一个结点和最后一个结点。
假设指针s指向另一个单链表中某个结点,则在s所指结点之后插入上述链表应执行的语句为
A.s->next=q;p->next=s->next;
B.s->next=p;q->next=s->next;
C.p->next=s->next;s->next=q;
D.q->next=s->next;s->next=p;[A]7.栈和队列的共同特点是
A.只允许在端点处插入和删除元素B.都是先进后出
C.都是先进先出D.没有共同点
[D]8.对于链队列,在进行插入运算时.
A.仅修改头指针
B.头、尾指针都要修改
C.仅修改尾指针
D.头、尾指针可能都要修改
[B]9.设有一个顺序栈的入栈序列是1、2、3,则3个元素都出栈的不同排列个数为
A.4 B.5 C.6 D.7
[D]10.设一个栈的输入序列为A,B,C,D,则借助一个栈所得到的输出序列不可能是A.A,B,C,D B.D,C,B,A
C.A,C,D,B D.D,A,B,C[C]11.表达式a*(b+c)-d的后缀表达式是
A.abcd*+- B.abc*+d- C.abc+*d- D.-+*abcd
[B]12.某二叉树的先序序列和后序序列正好相反,则该二叉树的特点一定是
A.空或只有一个结点 B.高度等于其结点数
C.任一结点无左孩子 D.任一结点无右孩子[B]13.下面的说法中正确的是
(1)任何一棵二叉树的叶子结点在种遍历中的相对次序不变。
(2)按二叉树定义,具有三个结点的二叉树共有6种。
A.
(1),
(2) B.
(1)
C.
(2) D.
(1),
(2)都错
[B]14.树有先序遍历和后序遍历,树可以转化为对应的二叉树。
下面的说法正确的是
A.树的后序遍历与其对应的二叉树的先序遍历相同B.树的后序遍历与其对应的二叉树的中序遍历相同C.树的先序序遍历与其对应的二叉树的中序遍历相同D.以上都不对
[D]15.下列说法正确的是
(1)二又树按某种方式线索化后,任一结点均有前趋和后继的线索
(2)二叉树的先序遍历序列中,任意一个结点均处于其子孙结点前(3)二叉排序树中任一结点的值大于其左孩子的值,小于右孩子的值
A.
(1)
(2)(3) B.
(1)
(2)
C.
(1)(3) D.都不对
[D]16.二叉树的第k层的结点数最多为
A.2k-1 B.2K+1
C.2K-1 D.2k-1
[D]17.以下说法不正确的是A.无向图中的极大连通子图称为连通分量B.连通图的广度优先搜索中一般采用队列来暂存刚访问过的顶点C.图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点D.有向图的遍历不可采用广度优先搜索
[B]18.有向图G用邻接矩阵A存储,则顶点i的入度等于A中
A.第i行1的元素之和 B.第i列1的元素之和
C.第i行0的元素个数 D.第i列非0的元素个数
[A]19.设有6个结点的无向图,该图确保是一个连通图的有效边条数至少应是
A.5 B.6 C.7 D.8
[D]20..下图的邻接表中,从顶点V1出发采用深度优先搜索法遍历该图,则可能的顶点序列是
A.V1V2V3V4V5 B.V1V2V3V5V4
C.V1V4V3V5V2 D.V1V3V4V5V2[A]21.关键路径是事件结点网络中
A.从源点到汇点的最长路径 B.从源点到汇点的最短路径
C.最长的回路 D.最短的回路
[A]22.设哈希表长为14,哈希函数H(key)=key%11,表中已有数据的关键字为15,38,61,84,四个,现将关键字为49的结点加到表中,用二次探测再散列法解决冲突,则放入的位置是
A.8 B.3 C.5 D.9
[C]23..在平衡二叉树中插入一个结点后造成了不平衡,设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0,右孩子的平衡因子为1,则应调整以使其平衡,所作的平衡旋转是
A.LL型 B.LR型 C.RL型 D.RR型
[A]24.下列排序算法中,在待排序数据已基本有序时,效率最高的排序方法是A.插入排序 B.选择排序
C.快速排序 D.堆排序
[A]25.下列排序算法中,时间复杂度不受数据初始状态影响,恒为0(nlog2n)是
A.堆排序 B.冒泡排序
C.直接选择排序 D.快速排序
[B]26.有一程序段:
i=1;WHILE(iA.O(n) B.O(log2n)
C.O(nlog2n) D.O(n2)
[C]27.无头结点的链队列Q为空的条件是
A.Q->front->next==Q->real=NULL
B.Q->front==Q->real<>NULL
C.Q->real==Q->front=NULL
D.Q->real->next==Q->front<>NULL[A]28.有向图G可拓扑排序的判别条件是
A.不存在环 B.存在环
C.存在入度为零的结点 D.存在出度为零的结点
[C]29.对n个记录的文件进行快速排序,所需要的辅助存储空间
A.O
(1) B.O(n) C.O(1og2n) D.O(n2)
[A]30.下列排序算法中,在待排序数据已基本有序时,效率最高的排序方法是
A.插入排序 B.选择排序
C.快速排序 D.堆排序二、综合题(共4题,每题10分)
31、阅读算法,在横线处填入语句或注释。
voidexchange_L(Linklist&L,intm){
//带头结点的单链表中前m个结点和后n个结点的整体互换
if(m&&L->next){//链表非空
p=L->next;
(1)//k取值
while(k(2)p=p->next;++k;
}//while
if(p&&(3)){//n!
=0时才需要修改指针
ha=L->next; // 以指针ha记a1结点的位置L->next=p->next;//将b1结点链接在头结点后p->next=(4); //设am的后继
q=L->next;//令q指向b1结点
while(q->next)
q=q->next;//查找bn结点
q->next=(5)//将第a1结点链接到bn结点之后
}//if(p)
}//if(m)
}//exchange_L
答案
(1)k=1;
(2)查找第am个结点
(3)p->next
(4)L->next
(5)将第a1结点链接到bn结点之后
32.一个仅包含二元运算符的算术表达式,以二叉链表形式存储在二叉树T中,设计算法F1
实现求值,并指出遍历的方式。
解:
int F1(BiTrecT){
if(!
T) return0;
if(!
T→lchild&&!
T→rchild)//
(1)判断是否为叶子结点return(T→data);
Lv=F1(T→lchild);Rv=F1(T→rchild);switch(T→data){//
(2)运算
case’+’:
V=Lv+Rv; break;case’-’:
V=Lv-Rv; break;case’*’:
V=Lv*Rv; break;case’/’:
V=lv/Rv; break;
}//switch
returnV;//(3)返回结果
}//F1
算法功能:
后序遍历二叉树,求算术表达式的值。
33.设计算法实现以逆邻接表为存储结构的有向图的拓扑排序。
逆邻接表存储结构定义如下:
vexdata firstin
adjvex nfo firstarc
顶点结构 表结点结构
34.设哈希表长为13,采用线性探测法解决冲突,哈希函数定义为:
H(key)=key%13。
试求:
(1)填上依次插入关键字25,20,36,15,41,52,29,72,67后的哈希表。
(2)计算等概率情况下,查找成功的平均查找长度。