东师数据结构18春在线作业1答案满分答案
数据结构18春在线作业1-0003
试卷总分:100 得分:0
一、 单选题 (共 20 道试题,共 60 分)
1.设有2500个无序的记录，希望以最快的速度挑选出其中前10个排序码最大的记录，最好选用的排序方法是 ()。
A.直接插入排序
B.堆排序
C.冒泡排序
D.快速排序
正确选项:----
2.对关键码序列 28 , 16 , 32, 12, 60, 2, 5, 72 快速排序 ( 从小到大序 ) , 一次划分的结果为 ()。
A.( 2 , 5 , 12 , 16 ) 28 ( 60 , 32 , 72 )
B.( 5 , 16 , 2 , 12 ) 28 ( 60 , 32 , 72 )
C.( 2 , 16 , 12 , 5 ) 28 ( 60 , 32 , 72 )
D.( 5 , 16 , 2 , 12 ) 28 ( 32 , 60 , 72 )
专业答案:----
3.有n个顶点的无向图的边数最多为 ()。
A.n
B.n(n-1)
C.n(n-1)/2
D.2n
正确选项:----
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.用DFS遍历一个无环有向图，并在DFS算法退栈返回时打印相应的顶点，则输出的顶点序列是 ()。
正确答案:----
A.逆拓扑有序
B.拓扑有序
C.无序的
D.部分有序的
专业答案:----
10.散列文件使用哈希函数将记录的关键字值计算转化为记录的存储地址，因为哈希函数是一对一的关系，则选择好的 () 方法是散列文件的关键。
A.哈希函数
B.除余法中的质数
C.冲突处理
D.哈希函数和冲突处理
专业答案:----
11.非线性结构的逻辑特征是一个结构可能有 ( )。
A.一个前驱和一个后继
B.多个前驱和一个后继
C.一个前驱和多个后继
D.多个前驱和多个后继
专业答案:----
12.完全二叉树是下列情况的哪一种 ( )。
A.一定是满二叉树
B.可能是满二叉树
C.一定不是满二叉树
D.不是二叉树
正确选项:----
13.相对于顺序存储而言，链接存储的优点是 ( )。
A.随机存取
B.节省空间
C.插入、删除操作方便
D.结点间关系简单
专业答案:----
14.下列排序算法中，其中 () 是稳定的。
A.堆排序，起泡排序
B.快速排序，堆排序
C.归并排序，起泡排序
D.直接选择排序，归并排序
专业答案:----
15.在下述几种排序方法中，不稳定的排序方法是 ()。
A.直接插入排序
B.冒泡排序
C.直接选择排序
D.归并排序
正确选项:----
16.head指向的带表头结点的单链表为空的判定条件是 ( )。
正确选项:----
A.head = = NULL
专业答案:----
B.head->next = = head
正确选项:----
C.head ! = NULL
专业答案:----
D.head->next = = NULL
专业答案:----
17.四个元素进入队列QU的顺序是U、V、X、Y，进行DeQueue(QU,x)操作后，队头元素是 ( )。
正确选项:----
A.U
B.V
C.X
D.Y
正确答案:----
18.如果要求一个线性表既能较快地查找、又能适应动态变化的要求，则可采用的查找方法是 ()。
A.顺序查找
B.折半查找
C.分块查找
D.基于属性的查找
正确选项:----
19.引入线索二叉树的目的是 ( )。
A.加快查找结点的前驱或后继的速度
B.为了能方便地找到双亲
C.为了能在二叉树中方便地进行插入与删除
D.使二叉树的遍历结果唯一
正确答案:----
20.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行 ( )。
A.p->next = s; s->next = q;
B.s->next = p->next; p->next = s;
C.p->next = s->next; s->next = p;
D.q->next = s; s->next = p;
专业答案:----
东师数据结构18春在线作业1答案多选题答案
二、 判断题 (共 20 道试题,共 40 分)
1.在图G的最小生成树T中，可能会有某条边的权值超过未选边的权值。
A.错误
B.正确
2.程序一定是算法。
A.错误
B.正确
3.线性表只能用顺序存储结构实现。
A.错误
B.正确
4.树与二叉树是两种不同的树形结构。
A.错误
B.正确
5.链表与顺序存储结构相比，在链表中进行插入、删除操作的效率高。
A.错误
B.正确
6.完全二叉树一定存在度为1的结点。
A.错误
B.正确
7.完全二叉树肯定是平衡二叉排序树。
A.错误
B.正确
8.一个有向图的邻接表和逆邻接表中结点的个数可能不等。
A.错误
B.正确
9.二叉树结点的中序遍历序列与后序遍历序列可以唯一地确定该棵二叉树。
A.错误
B.正确
10.哈夫曼树是带权 ( 外部 ) 路径长度最短的树，路径上权值较大的结点离根较近。
A.错误
B.正确
11.链接存储结构属动态存储方式。
A.错误
B.正确
12.二叉排序树删除一个结点后，仍是二叉排序树。
A.错误
B.正确
13.分块查找在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中的元素个数有关。
A.错误
B.正确
14.任何一棵二叉树都可以不用栈实现前序线索二叉树的前序遍历。
A.错误
B.正确
15.用二叉树的前序遍历和中序遍历可以导出二叉树的后序遍历。
A.错误
B.正确
16.对n个记录的文件进行堆排序，最坏情况下的执行时间是O(nlog2n )。
A.错误
B.正确
17.用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中的结点个数有关，而与图的边数无关。
A.错误
B.正确
18.在指定结点之后插入新结点时，双链表比单链表更方便。
A.错误
B.正确
19.负载因子（装填因子）是哈希表(散列表)的一个重要参数，它反映哈希表的填满程度。
A.错误
B.正确
东师数据结构18春在线作业1答案历年参考题目如下：
