东大17秋学期《数据结构Ⅰ》在线作业1答案答案
17秋学期《数据结构Ⅰ》在线作业1
试卷总分:100 得分:0
一、 单选题 (共 20 道试题,共 100 分)
1. 已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于
A. 1.0
B. 2.9
C. 3.4
D. 5.5
正确选项:----
满分：5 分
2. 能进行二分查找的线性表,必须以
A. 顺序方式存储,且元素按关键字有序
B. 链式方式存储,且元素按关键字有序
C. 顺序方式存储,且元素按关键字分块有序
D. 链式方式存储,且元素按关键字分块有序
正确选项:----
满分：5 分
3. 已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有
专业答案:----
A. dacb
正确选项:----
B. cadb
正确答案:----
C. bdac
专业答案:----
D. 以上答案都不对
正确选项:----
满分：5 分
4. 对n个关键字的序列进行快速排序，平均情况下的空间复杂度为
A. O(1)
B. O(logn)
C. O(n)
D. O(n logn)
专业答案:----
满分：5 分
5. 设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是
正确选项:----
A. A，B，C，D
正确答案:----
B. D，C，B，A
正确选项:----
C. A，C，D，B
正确答案:----
D. D，A，B，C
正确选项:----
满分：5 分
6. 连通图是指图中任意两个顶点之间
A. 都连通的无向图
B. 都不连通的无向图
C. 都连通的有向图
D. 都不连通的有向图
正确答案:----
满分：5 分
7. 队列和栈的主要区别是
A. 逻辑结构不同
B. 存储结构不同
C. 所包含的运算个数不同
D. 限定插入和删除的位置不同
正确选项:----
满分：5 分
8. 一棵树高为K的完全二叉树至少的结点是
A. 2k –1
正确选项:----
B. 2k-1 –1
正确答案:----
C. 2k-1
D. 2k
正确答案:----
满分：5 分
9. n个顶点的有向完全图中含有向边的数目最多为
A. n-1
B. n
C. n(n-1)/2
D. n(n-1)
正确答案:----
满分：5 分
10. 设数组A[m]为循环队列Q的存储空间，front为队头指针，rear为队尾指针，则判定Q为空队列的条件是
A. (rear-front)%m= =1
B. front= =rear
C. (rear-front)%m= =m-1
D. front= =(rear+1)%m
正确答案:----
满分：5 分
11. 引入二叉线索树的目的是
A. 加快查找结点的前驱或后继的速度
B. 为了能在二叉树中方便的进行插入与删除
C. 为了能方便的找到双亲
D. 使二叉树的遍历结果唯一
正确答案:----
满分：5 分
12. 一棵左右子树均不空的二叉树在先序线索化后，其中空的链域的个数是
A. 0
B. 1
C. 2
D. 不确定
正确答案:----
满分：5 分
13. 在关键字序列(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
正确选项:----
满分：5 分
14. 下列关键字序列中，构成小根堆的是
A. {84，46，62，41，28，58，15，37}
B. {84，62，58，46，41，37，28，15}
C. {15，28，46，37，84，41，58，62}
D. {15，28，46，37，84，58，62，41}
正确选项:----
满分：5 分
15. 若以1234作为双端队列的输入序列，则既不能由输入受限的双端队列得到，也不能由输出受限的双端队列得
到的输出序列是
A. 1234
B. 4132
C. 4231
D. 4213
正确选项:----
满分：5 分
16. 设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则栈的容量至少应该是
A. 2
B. 3
C. 5
D. 6
正确答案:----
满分：5 分
17. 下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是
A. 分块查找
B. 顺序查找
C. 二分查找
D. 散列查找
专业答案:----
满分：5 分
18. 抽象数据类型的三个组成部分分别为
A. 数据对象、数据关系和基本操作
B. 数据元素、逻辑结构和存储结构
C. 数据项、数据元素和数据类型
D. 数据元素、数据结构和数据类型
正确选项:----
满分：5 分
19. 可有效提高次关键字查找效率的文件是
A. 顺序文件
B. 倒排文件
C. 散列文件
D. VSAM文件
正确答案:----
满分：5 分
20. 设给定权值总数有n 个，其哈夫曼树的结点总数为
A. 不确定
B. 2n
C. 2n+1
D. 2n-1
专业答案:----
满分：5 分
东大17秋学期《数据结构Ⅰ》在线作业1答案历年真题如下：
