![东大21秋学期《数据结构Ⅱ》在线平时作业3[答案]](/uploads/allimg/240109/94204a9d24af566b65f471f77a58ebee.jpg)
东大21秋学期《数据结构Ⅱ》在线平时作业3[答案]答案
C.O(n+e)
D.O(n2)
正确答案:-----
2.索引非顺序文件的特点是
A.主文件无序，索引表有序
B.主文件有序，索引表无序
C.主文件有序，索引表有序
D.主文件无序，索引表无序
正确答案:-----
3.二维数组A按行优先顺序存储，其中每个元素占1个存储单元。若A［1］［1］的存储地址为420，A［3］［3］的存储地址为446，则A［5］［5］的存储地址为
A.470
B.471
C.472
D.473
正确答案:-----
4.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是
正确答案:-----
A.p=p->next;
B.p->next=p->next->next;
C.p->next=p;
D.p=p->next->next;
正确答案:-----
5.引入二叉线索树的目的是
A.加快查找结点的前驱或后继的速度
B.为了能在二叉树中方便的进行插入与删除
C.为了能方便的找到双亲
D.使二叉树的遍历结果唯一
正确答案:-----
6.一棵树高为K的完全二叉树至少的结点是
A.2k –1
正确答案:-----
正确答案:-----
B.2k-1 –1
C.2k-1
D.2k
正确答案:-----
7.下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是
A.分块查找
B.顺序查找
C.二分查找
D.散列查找
正确答案:-----
8.某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则该二叉树对应的森林包括的树的棵树是
正确答案:-----
A.1
B.2
C.3
D.4
正确答案:-----
9.已知循环队列的存储空间为数组data[21]，且当前队列的头指针和尾指针的值分别为8和3，则该队列的当前长度为
正确答案:-----
A.5
B.6
C.16
D.17
正确答案:-----
10.在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为
A.n-i+1
B.i
C.i+1
D.n-i
正确答案:-----
11.从逻辑上可以把数据结构分为两大类，即
A.动态结构、静态结构
B.顺序结构、链式结构
C.线性结构、非线性结构
D.初等结构、构造型结构
正确答案:-----
12.如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
A.深度优先搜索算法
B.广度优先搜索算法
C.求最小生成树的prim算法
D.拓扑排序算法
正确答案:-----
正确答案:-----
13.为便于判别有向图中是否存在回路，可借助于
A.广度优先搜索算法
B.最小生成树算法
C.最短路径算法
D.拓扑排序算法
14.队列和栈的主要区别是
A.逻辑结构不同
B.存储结构不同
C.所包含的运算个数不同
D.限定插入和删除的位置不同
正确答案:-----
15.在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=
正确答案:-----
head,则
正确答案:-----
A.p指向头结点
B.p指向尾结点
C.p的直接后继是头结点
D.P的直接后继是尾结点
正确答案:-----
16.若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上
A.操作的有限集合
B.映象的有限集合
C.类型的有限集合
D.关系的有限集合
正确答案:-----
17.通常将链串的结点大小设置为大于1是为了
A.提高串匹配效率
B.提高存储密度
C.便于插入操作
D.便于删除操作
正确答案:-----
21.对长度为n的关键字序列进行堆排序的空间复杂度为
A.O（log2n）
B.O（1）
C.O（n）
D.O（n*log2n）
正确答案:-----
19.在一个带权连通图G中，权值最小的边一定包含在G的
A.最小生成树中
B.深度优先生成树中
C.广度优先生成树中
D.深度优先生成森林中
正确答案:-----
20.假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为
A.(rear-length+m+1)％m
B.(rear-length+m)％m
C.(rear-length+m-1)％m
东大21秋学期《数据结构Ⅱ》在线平时作业3[答案]历年参考题目如下：
18秋学期《数据结构Ⅱ》在线作业3-0001
试卷总分:100 得分:0
一、 单选题 (共 20 道试题,共 100 分)
1. 下面的说法中正确的是
(1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。
(2)按二叉树定义，具有三个节点的二叉树共有6种。
A.(1)，(2)
B.(1)
C.(2)
D.(1)，(2)都错
2. n个顶点的有向完全图中含有向边的数目最多为
A.n-1
B.n
C.n(n-1)/2
D.n(n-1)
3. 深度为h的满m叉树的第k层的结点(1=<k=<h)数有
A.mk-1
B.mk-1
C.mh-1
D.mh-1
4. 下面关于线性表的叙述中，错误的是
A.线性表采用顺序存储，必须占用一片连续的存储单元。
B.线性表采用顺序存储，便于进行插入和删除操作。
C.线性表采用链接存储，不必占用一片连续的存储单元。
D.线性表采用链接存储，便于插入和删除操作。
5. 在计算机内实现递归算法时所需的辅助数据结构是
A.栈
B.队列
C.树
D.图
6. 在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是
A.1
B.2
C.3
D.5
7. 设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
A.2
B.3
C.5
D.6
8. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为
A.O(0)
B.O(1)
C.O(n)
D.O(n2)
9. 若采用孩子兄弟链表作为树的存储结构，则树的后序遍历应采用二叉树的
A.层次遍历算法
B.前序遍历算法
C.中序遍历算法
D.后序遍历算法
10. 一棵树高为K的完全二叉树至少的结点是
A.2k –1
B.2k-1 –1
C.2k-1
D.2k
11. 一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为
A.O(n)
B.O(e)
C.O(n+e)
D.O(n2)
12. for（i=0；i<m；i++）
for（j=0；j<t；j++）
c［i］［j］=0；
for（i=0；i<m；i++）
for（j=0；j<t；j++）
for（k=0；k<n；k++）
c［i］［j］=c［i］［j］+a［i］［k］*b［k］［j］；
上列程序的时间复杂度为
A.O（m+n×t）
B.O（m+n+t）
C.O（m×n×t）
D.O（m×t+n）
13. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为
A.4
B.5
C.8
D.9
14. 对于哈希函数H(key)=key%13,被称为同义词的关键字是
A.35和41
B.23和39
C.15和44
D.25和51
15. 已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是
A..{25,36,48,72,23,40,79,82,16,35}
B..{25,36,48,72,16,23,40,79,82,35}
C..{25,36,48,72,16,23,35,40,79,82}
D..{16,23,25,35,36,40,48,72,79,82}
16. 含n个关键字的二叉排序树的平均查找长度主要取决于
A.关键字的个数
B.树的形态
C.关键字的取值范围
D.关键字的数据类型
17. ．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是
A.逆拓扑有序
B.拓扑有序
C.无序的
D.A和B
18. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为
A.5
B.6
C.7
D.8
19. 某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是
A.空或只有一个结点
B.高度等于其结点数
C.任一结点无左孩子
D.任一结点无右孩子
20. 无向图中一个顶点的度是指图中
A.通过该顶点的简单路径数
B.与该顶点相邻接的顶点数
C.通过该顶点的回路数
D.与该顶点连通的顶点数
