东师数据结构17秋在线作业1（答案）答案
数据结构17秋在线作业1
试卷总分:100 得分:0
一、 单选题 (共 20 道试题,共 60 分)
1. head指向的非空的单循环链表的尾结点(由p所指向)满足 ( )。
正确答案:----
A. p->next = = NULL
B. p = = NULL
C. p->next = = head
D. p = = head
正确答案:----
满分：3 分
2. 从一个栈顶指针top的链栈中删除一个结点时，用x保存被删除的元素，执行 ( )。
A. x = top; top = top->next;
B. top = top->next; x = top->data;
正确选项:----
专业答案:----
C. x = top->data;
D. x = top->data; top = top->next;
专业答案:----
满分：3 分
3. 排序趟数与序列的原始状态有关的排序方法是 () 排序法。
A. 直接插入
B. 直接选择
C. 冒泡
D. 归并
正确选项:----
满分：3 分
4. 判断线索二叉树中某结点p有右子女的条件是 ( )。
A. p->rtag = = 0
B. p->rtag = = 1
C. p ! = NULL
D. p->lchild ! = NULL
正确答案:----
满分：3 分
5. ISAM文件和VSAM文件属于 ()。
A. 索引非顺序文件
B. 索引顺序文件
C. 顺序文件
D. 散列文件
专业答案:----
满分：3 分
6. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是 ()。
A. 直接插入排序
B. 快速排序
C. 直接选择排序
D. 归并排序
正确答案:----
满分：3 分
7. 设有两个串s1和s2，求s2在s1中首次出现的位置的运算称为 ( )。
A. 求子串
B. 求串长
C. 联接
D. 模式匹配
正确选项:----
满分：3 分
8. 算法分析的两个主要方面是 ( )。
A. 正确性与健壮性
B. 可读性与可用性
C. 时间复杂度与空间复杂度
D. 数据复杂性与程序复杂性
专业答案:----
满分：3 分
9. ISAM是索引顺序存取方法，该方法是专为下面的哪一种设备设计的 ()。
A. 磁带
B. 磁盘
C. 光盘
D. 外存储器
专业答案:----
满分：3 分
10. 在k叉树中，结点度数的最大值为 ( )。
A. k-1
B. k
C. k+1
D. k*n
专业答案:----
满分：3 分
11. 有n个顶点的无向图的边数最多为 ()。
A. n
B. n(n-1)
C. n(n-1)/2
D. 2n
专业答案:----
专业答案:----
满分：3 分
12. 用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是 ()。
正确选项:----
A. 逆拓扑有序
B. 拓扑有序
C. 无序的
D. 部分有序的
专业答案:----
满分：3 分
13. 下列说法不正确的是 ()。
A. 图的遍历是从给定的源点出发每个顶点仅被访问一次
B. 遍历的基本方法有两种：深度优先遍历和广度优先遍历
C. 图的深度优先遍历不适用于有向图
D. 图的深度优先遍历是一个递归过程
正确选项:----
满分：3 分
14. 若由森林转化得到的二叉树是非空的二叉树，则二叉树形状是 ( )。
A. 根结点无右子树的二叉树
B. 根结点无左子树的二叉树
C. 根结点可能有左子树和必有右子树
D. 各结点只有一个子女的二叉树
正确答案:----
满分：3 分
15. 一个有n个结点的图，连通分量的个数最少为 ()。
A. 0
B. 1
C. n-1
D. n
专业答案:----
满分：3 分
16. 在一个图中，所有顶点的度数之和等于图的边数的几倍 ()。
A. 1/2
B. 1
C. 2
D. 4
正确答案:----
满分：3 分
17. 广义表运算式tail ( ( ( a , b ) , ( c , d ) ) ) 的操作结果是 ()。
专业答案:----
A. ( c , d )
正确答案:----
B. c , d
C. ( ( c , d ) )
正确答案:----
D. d
专业答案:----
满分：3 分
18. 设有n个结点的最佳二叉排序树，对于成功的查找，最少的比较次数为()。
A. Ο( 1 )
B. Ο(log2n)
C. Ο(n)
D. Ο(nlog2n)
专业答案:----
满分：3 分
19. 设广义表L = ( ( a , b , c ) )，则L的长度和深度分别为 ()。
A. 1和1
B. 1和3
C. 1和2
D. 2和3
正确答案:----
满分：3 分
20. n个结点的线索二叉树上含有的线索数为 ( )。
A. n-1
B. n
C. n +1
D. 2n
满分：3 分
东师数据结构17秋在线作业1（答案）标准满分答案
二、 判断题 (共 20 道试题,共 40 分)1. 对n个记录的文件进行堆排序，最坏情况下的执行时间是O(nlog2n )。
A. 错误
B. 正确
满分：2 分
2. 顺序查找法适用于存储结构为顺序或链接存储的线性表。
A. 错误
B. 正确
满分：2 分
3. 对于插入、删除运算来说，链接存储结构一定优于顺序存储结构。
A. 错误
B. 正确
满分：2 分
4. 直接访问文件也能顺序访问，只是一般效率不高。
A. 错误
B. 正确
满分：2 分
5. 无向图的邻接矩阵可用一维数组存储。
A. 错误
B. 正确
满分：2 分
6. 连通分量是无向图中的极大连通子图。
A. 错误
B. 正确
满分：2 分
7. 对一棵二叉排序树按前序方法遍历得到的结点序列是从小到大的序列。
A. 错误
B. 正确
满分：2 分
8. 存放在磁盘、磁带上的文件，既可以是顺序文件，也可以是索引结构或其他结构类型的文件。
A. 错误
B. 正确
满分：2 分
9. 对于查找运算来说，链接存储结构一定优于顺序存储结构。
A. 错误
B. 正确
满分：2 分
10. 健壮的算法不会因非法的输人数据而出现莫名其妙的状态。
A. 错误
B. 正确
满分：2 分
