东大20秋学期《数据结构Ⅱ》在线平时作业2[答案]答案
20秋学期《数据结构Ⅱ》在线平时作业2
试卷总分:100 得分:0
一、单选题 (共 20 道试题,共 100 分)
1.．用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是
A.逆拓扑有序
B.拓扑有序
C.无序的
D.A和B
2.某二叉树中序序列为A,B,C,D,E,F,G，后序序列为B,D,C,A,F,G,E 则该二叉树对应的森林包括的树的棵树是
A.1
B.2
C.3
D.4
3.一个具有1025个结点的二叉树的高h为
A.11
B.10
C.11至1025之间
D.10至1024之间
4.连通网的最小生成树是其所有生成树中
A.顶点集最小的生成树
B.边集最小的生成树
C.顶点权值之和最小的生成树
D.边的权值之和最小的生成树
5.若允许表达式内多种括号混合嵌套，则为检查表达式中括号是否正确配对的算法，通常选用的辅助结构是
A.栈
B.线性表
C.队列
D.二叉排序树
6.在关键字序列(12，23，34，45，56，67，78，89，91)中二分查找关键字为45、89和12的结点时，所需进行的比较次数分别为
A.4，4，3
B.4，3，3
C.3，4，4
D.．3，3，4
7.栈的两种常用存储结构分别为
A.顺序存储结构和链式存储结构
B.顺序存储结构和散列存储结构
C.链式存储结构和索引存储结构
D.链式存储结构和散列存储结构
8.在长度为n的顺序表的第i(1≤i≤n+1)个位置上插入一个元素，元素的移动次数为
A.n-i+1
B.n-i
C.i
D.i-1
9.已知一组关键字为{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}
10.已知一个有向图如右所示，则从顶点a出发进行深度优先偏历，不可能得到的DFS序列为
A.a d b e f c
B.a d c e f b
C.a d c b f e
D.a d e f c b
11.下列说法正确的是
(1)二又树按某种方式线索化后，任一节点均有指向前趋和后继的线索
(2)二叉树的前序遍历序列中，任意一个节点均处于在子孙节点前
(3)二叉排序树中任一节点的值大于其左孩子的值，小于右孩子的值
A.(1)(2)(3)
B.(1)(2)
C.(1)(3)
D.前面的可选答案都不对
12.树有先根遍历和后根遍历，树可以转化为对应的二叉树。下面的说法正确的是
A.树的后根遍历与其对应的二叉树的后根遍历相同
B.树的后根遍历与其对应的二叉树的中根遍历相同
C.树的先根遍历与其对应的二叉树的中根遍历相同
D.以上都不对
13.下列数据结构中，属于非线性数据结构的是
A.栈
B.队列
C.完全二叉树
D.堆
14.设一个栈的输入序列为12345，则借助一个栈所得到的输出序列不可能是
A.23415
B.54132
C.23145
D.15432
15.下列编码中属于前缀编码的是
A.{1,01,000,001}
B.{1,01,011,010}
C.{0,10,110,11}
D.{0,1,00,11}
16.数据的不可分割的最小标识单位是
A.数据项
B.数据记录
C.数据元素
D.数据变量
17.数组A[1..5，1..6]的每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5，5]的地址为
A.1140
B.1145
C.1120
D.1125
18.能进行二分查找的线性表,必须以
A.顺序方式存储,且元素按关键字有序
B.链式方式存储,且元素按关键字有序
C.顺序方式存储,且元素按关键字分块有序
D.链式方式存储,且元素按关键字分块有序
19.ISAM文件的周期性整理是为了空出
A.磁道索引
B.柱面索引
C.柱面基本区
D.柱面溢出区
20.判断两个串大小的基本准则是
A.两个串长度的大小
B.两个串中首字符的大小
C.两个串中大写字母的多少
D.对应的第一个不等字符的大小
东大20秋学期《数据结构Ⅱ》在线平时作业2[答案]历年真题如下：
