还剩3页未读,继续阅读
文本内容:
“数据结构基础”知识要点02及答案(最后一页)
一、单选题(每题3分,共45分)
1.下列关于链表说法错误的是()A、顺序表上插入或删除一个元索不必移动其他元素B、单链表上插入或删除一个元素不必移动其他元素C、单链表和顺序表上插入或删除一个元素都不必移动其他元素D、单链表不需要提前定义链表的长度
2.非线性结构中每个结点()A、无直接前驱结点B、只有一个直接前驱和直接后继结点C、无直接后继结点D、可能有多个直接前驱和多个直接后继结点
3.在树中,若结点A有5个兄弟,而且B是A的双亲,则B的度为()A、7B、8C、5D、
6.设一维数组中有n个数组元素,则读取第i个数组元素的平均时间复杂度为()A、OnB、Onlog2n C、01D、On
25.已知串”aaabb’,则串长为(OA、4B、3C、5D、
66.下面说法中正确的是()B、度为2的有序树是二叉树C、子树有严格左右之分的树是二叉树D、子树有严格左右之分,并且度不超过2的树是二叉树.在数据结构中,与所使用的计算机无关的是()A、存储结构B、物理结构C、物理和存储结构D、逻辑结构
7.若一棵完全二叉树中某结点无左孩子,则该结点一定是()A、度为1的结点B、度为2的结点C、分支结点D、叶子结点个元素
8.设顺序线性表中有n个数据元素,则删除表中第j个元素需要移动(个元素C、n-l-jD、j)OC、O(n)D、O(n2)A、n-jB、n+1-j
10.卜.列程序段的时间复杂度为(B、插入删除不需要移动元素i=0,s=0;while(sn){s=s+li++}D、所需空间与线性表长度成正比()OA、O(nl/2)B、O(nl/3)
11.顺序表具有的特点是()B、学校的院系结构A
13、.已可知随串机访S=问/B任eij一ing元F素oreignStudiesUniversity,D、参加某个比赛的学生名单C
1、
3.不已必知事串先S估=/B计ei存jin储gF空or间eignStudiesUniversity,则串长为()
12.树最适合用来下面哪个数据结构A、31B、32C、34D、35A、某个班级的学生成绩单
14.一个栈的出栈序列是a,b,c,d,则栈的入栈序列是()C、城市间的网络结构图
15.下面关于图的说法,不正确的是()AA、、ddeebbaa B、dbea C、abed D、cabdA、图的存储需要实现顶点和边的信息的存储B、在应用中,图的边可以有权重C、图不可以有无向图D、图(Graph)是由非空的顶点集合和一个描述顶点之间关系(边或者弧)的集合组成
二、判断题(每题
2.5分,共25分)
1、遍历图有深度优先遍历、广度优先遍历等方法()
2、线性结构中元素之间存在一对多关系,树形结构中元素之间存在一对一关系,图形结构中元素之间存在多对多关系()
3、设栈s和队列q均为空,先将a,b,c,d,e依次进队列q,再将队列q中顺次出队的元素进栈S,直至队空再将栈s中的元素逐个出栈,并将出栈元素顺次进队列q,则队列q的状态是edcba()
4、两个串相等的充分必要条件是两个串的长度相等且对应位置字符相同()
5、树内各结点度的最小值称为树的度()
6、队列是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性表()
7、在树形结构中,树根结点没有前驱结点,其余每个结点有旦只有1个前驱结点()
8、在图形结构中,每个结点的前驱结点数和后续结点数有且只有1个()
9、设栈s和队列q均为空,先将a,b,c,d依次进栈s,再将栈s中的元素逐个出栈,并将出栈元素顺次进队列q,则队列q的状态是dcba()
10、设循环队列的容量为70,现经过一系列的入队和出队操作后,front为30,rear为11,则队列中元素的个数为52()
三、计算题(每题15分,共30分)语句频度是多少?每个算法的最大频度语句是哪句?x=0;fori=l;-in;i++“for力=1;j=n-i;j++x++;i=l;1while i=ni=i*2;
2、某不带权有向图如右图所示:
(1)给出其邻接矩阵
(2)该图的出度是多少?
(3)该图的入度是多少?
(4)节点5的出度是多少?“数据结构基础”知识要点02答案
一、单选题(每题3分,共45分)
1、B
2、D
3、D
4、C
5、C
6、D
7、D
8、D
9、A
10、C
11、A
12、B
13、C
14、A
15、C(每题
2.5
二、判断题分,共25分)
1、T
2、F
3、T
4、T
5、F
6、T
7、T
8、F
9、T
10、F
1、
(1)算法是两个for循环,循环次数分别是n和n-i,因此时间复杂度是0(M)(3分);最大频度的语句是x++语句(3分),最大语句频度是0(M)(2分).
(2)算法是1个while循环,循环次数分别是n,但是i以每2倍的速度增长,因此时间复杂度是O(log2n)(3分)最大频度的语句是i=i*2语句(3分),最大语句频度是O(log2n)(1分)
2、
(1)该图的邻接矩阵是(7分,每行
1.5分)-o1o1r00100000010()10100000
(2)该图的出度是7;(3分)
(3)改图的入度也是7;(3分)
(4)节点5的出度是
0.(2分)。