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