东师数据结构20秋在线作业2[答案]满分答案
东师数据结构20秋在线作业2
试卷总分:100 得分:100
一、单选题 (共 20 道试题,共 60 分)
1.算法分析的两个主要方面是 ( )。
A.正确性与健壮性
B.可读性与可用性
C.时间复杂度与空间复杂度
D.数据复杂性与程序复杂性
2.在k叉树中，结点度数的最大值为 ( )。
A.k-1
B.k
C.k+1
D.k*n
3.倒排文件中倒排表是指 ()。
A.主关键字索引
B.次关键字索引
C.物理顺序与逻辑顺序不一致
D.多关键字索引
4.在索引顺序文件中， ()。
A.主文件是无序的
B.主文件是有序的
C.不适宜随机查找
D.索引是稠密索引
5.采用邻接表存储的图的深度优先遍历类似于二叉树的 ()。
A.前序遍历
B.中序遍历
C.后序遍历
D.层次遍历
6.下列排序方法中，哪一个是稳定的排序方法？()
A.直接选择排序
B.直接插入排序
C.希尔排序
D.快速排序
7.一个有向无环图的拓扑排序序列 () 是唯一的。
A.一定
B.不一定
C.可能
D.三者均不对
8.顺序查找法适合于存储结构为下列哪一种方式的线性表 ()。
A.散列存储
B.顺序存储或链接存储
C.压缩存储
D.索引存储
9.任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序 ( )。
A.不发生改变
B.发生改变
C.稍有改变
D.不能确定
10.( ) 的遍历仍需要栈的支持。
A.前序线索二叉树
B.中序线索二叉树
C.后序线索二叉树
D.前三种均需要
11.一个有n个结点的图，连通分量的个数最多为 ()。
A.0
B.1
C.n-1
D.n
12.每一个(存储)结点不仅含有一个数据元素，还包含一组指针，该存储方式是 ( )。
A.顺序存储
B.链接存储
C.索引存储
D.散列存储
13.空串与空格串是相同的，这种说法 ( ) 。
A.正确
B.可能正确
C.不正确
D.可能不正确
14.快速排序算法在下述哪种情况下效率最高 ()。
A.被排序的数据已完全有序
B.被排序的数据中含有多个相同的排序码
C.被排序的数据已基本有序
D.被排序的数据完全无序
15.用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是 ()。
A.逆拓扑有序
B.拓扑有序
C.无序的
D.部分有序的
16.一个队列的入队序列是a、b、c、d，则队列的输出序列是 ( )。
A.abcd
B.dcba
C.adcb
D.cbda
17.head指向的不带表头结点的单链表为空的判定条件是 ( )。
A.head = = NULL
B.head->next = = head
C.head ! = NULL
D.head->next = = NULL
18.线性表若采用链式存储结构时，要求内存中可用存储单元的地址 ( )。
A.必须是连续的
B.部分地址必须是连续的
C.一定是不连续的
D.连续或不连续都可以
19.在线索二叉树中，p所指结点没有左子树的充要条件是 ( )。
A.p->lchild = = NULL
B.p->ltag = = 1
C.p->ltag = = 1且p->lchild = = NULL
D.p->ltag = = 0
20.在排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 ()。
A.直接选择排序
B.冒泡排序
C.直接插入排序
D.希尔排序
东师数据结构20秋在线作业2[答案]多选题答案
二、判断题 (共 20 道试题,共 40 分)
21.二维以上的数组其实是一种特殊的广义表。
22.算法可以用不同的语言描述，如果用C语言或 JAVA 语言等高级语言来描述，则算法实际上就是程序了。
23.堆排序是稳定的排序方法。
24.二叉树结点的中序遍历序列与前序遍历序列可以唯一地确定该棵二叉树。
25.完全二叉树肯定是平衡二叉排序树。
26.给定一棵树，可以找到唯一的一棵二叉树与之对应。
27.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。
28.顺序查找法适用于存储结构为顺序或链接存储的线性表。
29.带权的连通无向图的最小(代价)生成树必是唯一的。
30.对有序的单链表不能进行折半查找。
31.必须把一般的树转换成二叉树后才能进行存储。
32.AOV网的含义是以顶点表示活动的网。
33.拓扑排序算法仅适用于有向无环图。
34.对一棵二叉排序树按中序方法遍历得到的结点序列是从小到大的序列。
35.采用二叉链表作为存储结构，树的先根遍历和其相应的二叉树的前序遍历的结果是一样的。
36.顺序存储方式只能用于存储线性结构。
37.对n个记录的文件进行堆排序，最坏情况下的执行时间是O(nlog2n )。
38.用二叉树的前序遍历和中序遍历可以导出二叉树的后序遍历。
39.二叉树结点的中序遍历序列与后序遍历序列可以唯一地确定该棵二叉树。
40.二叉树结点的前序遍历序列与后序遍历序列可以唯一地确定该棵二叉树。
东师数据结构20秋在线作业2[答案]历年参考题目如下：
