东大20春学期《数据结构Ⅱ》在线平时作业3[答案]满分答案
20春学期《数据结构Ⅱ》在线平时作业3
试卷总分:100 得分:100
一、单选题 (共 20 道试题,共 100 分)
1.已知二叉树的先序序列为ABDECF，中序序列为DBEAFC，则后序序列为
A.DEFBCA
B.DEBFCA
C.DEBCFA
D.DEBAFC
2.下述哪一条是顺序存储结构的优点
A.插入运算方便
B.存储密度大
C.可方便地用于各种逻辑结构的存储表示
D.删除运算方便
3.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为
A.n-i+1
B.n-i
C.i-1
D.i
4.在线性表的下列运算中，不改变数据元素之间结构关系的运算是
A.查找
B.插入
C.排序
D.删除
5.引入二叉线索树的目的是
A.加快查找结点的前驱或后继的速度
B.使二叉树的遍历结果唯一
C.为了能方便的找到双亲
D.为了能在二叉树中方便的进行插入与删除
6.快速排序在最坏情况下的时间复杂度是
A.O(nlog2n)
B.O(n2log2n)
C.O(n2)
D.O(log2n)
7.在计算机内实现递归算法时所需的辅助数据结构是
A.队列
B.树
C.栈
D.图
8.在一个带权连通图G中，权值最小的边一定包含在G的
A.深度优先生成森林中
B.深度优先生成树中
C.最小生成树中
D.广度优先生成树中
9.对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为
A.(23，56，78，66，88，92，19，34)
B.(19，23，67，56，34，78，92，88)
C.(19，23，56，34，78，67，88，92)
D.(19，23，34，56，67，78，88，92)
10.一棵左子树为空的二叉树在先序线索化后，其中空的链域的个数是
A.不确定
B.2
C.1
D.0
11.已知含6个顶点(v0，v1，v2，v3，v4，v5)的无向图的邻接矩阵如图所示，则从顶点v0出发进行深度优先遍历可能得到的顶点访问序列为
A.(v0，v1，v5，v2，v3，v4)
B..(v0，v1，v4，v5，v2，v3)
C..(v0，v1，v2，v5，v4，v3)
D.(v0，v1，v2，v3，v4，v5)
12.下列关键字序列中，构成小根堆的是
A.{84，62，58，46，41，37，28，15}
B.{84，46，62，41，28，58，15，37}
C.{15，28，46，37，84，58，62，41}
D.{15，28，46，37，84，41，58，62}
13.队列和栈的主要区别是
A.限定插入和删除的位置不同
B.逻辑结构不同
C.所包含的运算个数不同
D.存储结构不同
14.对关键字序列（5，1，4，3，7，2，8，6）进行快速排序时，以第一个元素5为基准的一次划分的结果为
A.（8，7，6，5，4，3，2，1）
B.（2，1，4，3，5，7，8，6）
C.（1，4，3，2，5，7，8，6）
D.（1，2，3，4，5，6，7，8）
15.下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是
A.顺序查找
B.散列查找
C.分块查找
D.二分查找
16.如果将矩阵An×n的每一列看成一个子表，整个矩阵看成是一个广义表L，即L=((a11,a21,…,an1),
( a12,a22,…,an2),…，（a1n,a2n,…,ann）),并且可以通过求表头head和求表尾tail的运算求
取矩阵中的每一个元素，则求得a21的运算是
A.tail (head (tail (L)))
B.head (tail (head (L)))
C.head (head (tail (L)))
D.head (head(head(L)))
17.上溢现象通常出现在
A.顺序栈的出栈操作过程中
B.顺序栈的入栈操作过程中
C.链栈的出栈操作过程中
D.链栈的入栈操作过程中
18.一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少的结点数有
A.h+1
B.2h-1
C.2h+1
D.2h
19.下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlog2n)的是
A.直接选择排序
B.快速排序
C.堆排序
D.冒泡排序
20.对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用遍历方式是
A.后序
B.先序
C.从根开始的层次遍历
D.中序
东大20春学期《数据结构Ⅱ》在线平时作业3[答案]历年参考题目如下：
