东师-数据结构20春在线作业2答案

1、数据结构19春在线作业2-0001试卷总分:100 得分:100一、单选题 (共 20 道试题,共 60 分)1.算法分析的两个主要方面是 ( )。A.正确性与健壮性B.可读性与可用性C.时间复杂度与空间复杂度D.数据复杂性与程序复杂性答案:C2.在k叉树中，结点度数的最大值为 ( )。A.k-1B.kC.k+1D.k*n答案:B3.倒排文件中倒排表是指 ()。A.主关键字索引B.次关键字索引C.物理顺序与逻辑顺序不一致D.多关键字索引答案:B4.在索引顺序文件中， ()。A.主文件是无序的B.主文件是有序的C.不适宜随机查找D.索引是稠密索引答案:B5.采用邻接表存储的图的深度优先遍历类似于

2、二叉树的 ()。A.前序遍历B.中序遍历C.后序遍历D.层次遍历答案:A6.下列排序方法中，哪一个是稳定的排序方法？()A.直接选择排序B.直接插入排序C.希尔排序D.快速排序答案:B7.一个有向无环图的拓扑排序序列 () 是唯一的。A.一定B.不一定C.可能D.三者均不对答案:B8.顺序查找法适合于存储结构为下列哪一种方式的线性表 ()。A.散列存储B.顺序存储或链接存储C.压缩存储D.索引存储答案:B9.任何一棵二叉树的叶结点在前序、中序和后序遍历序列中的相对次序 ( )。A.不发生改变B.发生改变C.稍有改变D.不能确定答案:A10.( ) 的遍历仍需要栈的支持。A.前序线索二叉树B.中

3、序线索二叉树C.后序线索二叉树D.前三种均需要答案:C11.一个有n个结点的图，连通分量的个数最多为 ()。A.0B.1C.n-1D.n答案:D12.每一个(存储)结点不仅含有一个数据元素，还包含一组指针，该存储方式是 ( )。A.顺序存储B.链接存储C.索引存储D.散列存储答案:B13.空串与空格串是相同的，这种说法 ( ) 。A.正确B.可能正确C.不正确D.可能不正确答案:C14.快速排序算法在下述哪种情况下效率最高 ()。A.被排序的数据已完全有序B.被排序的数据中含有多个相同的排序码C.被排序的数据已基本有序D.被排序的数据完全无序答案:D15.用DFS遍历一个无环有向图，并在DFS

4、算法退栈返回时打印相应的顶点，则输出的顶点序列是 ()。A.逆拓扑有序B.拓扑有序C.无序的D.部分有序的答案:A16.一个队列的入队序列是a、b、c、d，则队列的输出序列是 ( )。A.abcdB.dcbaC.adcbD.cbda答案:A17.head指向的不带表头结点的单链表为空的判定条件是 ( )。A.head = = NULLB.head->next = = headC.head ! = NULLD.head->next = = NULL答案:A18.线性表若采用链式存储结构时，要求内存中可用存储单元的地址 ( )。A.必须是连续的B.部分地址必须是连续的C.一定是不连续的

5、D.连续或不连续都可以答案:D19.在线索二叉树中，p所指结点没有左子树的充要条件是 ( )。A.p->lchild = = NULLB.p->ltag = = 1C.p->ltag = = 1且p->lchild = = NULLD.p->ltag = = 0答案:B20.在排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 ()。A.直接选择排序B.冒泡排序C.直接插入排序D.希尔排序答案:C二、判断题 (共 20 道试题,共 40 分)21.二维以上的数组其实是一种特殊的广义表。答案:正确22.算法

6、可以用不同的语言描述，如果用C语言或 JAVA 语言等高级语言来描述，则算法实际上就是程序了。答案:错误23.堆排序是稳定的排序方法。答案:错误24.二叉树结点的中序遍历序列与前序遍历序列可以唯一地确定该棵二叉树。答案:正确25.完全二叉树肯定是平衡二叉排序树。答案:错误26.给定一棵树，可以找到唯一的一棵二叉树与之对应。答案:正确27.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。答案:错误28.顺序查找法适用于存储结构为顺序或链接存储的线性表。答案:正确29.带权的连通无向图的最小(代价)生成树必是唯一的。答案:错误30.对有序的单链表不能进行折半查找。答案:正确31.必须把一般的树转换成二叉树后才能进行存储。答案:错误32.AOV网的含义是以顶点表示活动的网。答案:正确33.拓扑排序算法仅适用于有向无环图。答案:错误34.对一棵二叉排序树按中序方法遍历得到的结点序列是从小到大的序列。答案:正确35.采用二叉链表作为存储结构，树的先根遍历和其相应的二叉树的前序遍历的结果是一样的。答案:正确36.顺序存储方式只能用于存储线性结构。答案:错误37.对n个记录的文件进行堆排序，最坏情况下的执行时间是O(nlog2n )。答案:正确38.用二叉树的