《东北师范数据结构16秋在线作业1》由会员分享，可在线阅读，更多相关《东北师范数据结构16秋在线作业1（27页珍藏版）》请在金锄头文库上搜索。
1、 谋学网 数据结构 16 秋在线作业 1一、单选题（共 20 道试题，共 60 分。 ）1. 倒排文件中倒排表是指 ()。 . 主关键字索引 . 次关键字索引 . 物理顺序与逻辑顺序不一致 . 多关键字索引 正确答案： 2. 某二叉树结点的中序序列为 GHF，后序序列为 GHF，则该二叉树结点的前序序列为 ( )。. HFG . HFG . GFH . GHF 正确答案： 3. 一个有 n 个结点的图，连通分量的个数最少为 ()。. 0 . 1 . n-1 . n 正确答案： 4. 在线索二叉树中，p 所指结点没有左子树的充要条件是 ( )。. p-lhil = = NULL . p-ltg
2、= = 1 . p-ltg = = 1 且 p-lhil = = NULL. p-ltg = = 0 正确答案： 5. 有一个 100*90 的稀疏矩阵，非零元素有 10 个，设每个整型数占 2 字节，则用三元组表 示该矩阵时，所需的字节数是 () 。. 60 . 66 . 18000 . 33 正确答案： 6. 一个队列的入队序列是、 、 、 ，则队列的输出序列是 ( )。. . 谋学网 . . 正确答案： 7. 在排序方法中，从未排序序列中挑选记录，并将其依次放入已排序序列(初始时为空)的 一端的方法，称为 ()。 . 希尔排序 . 插入排序 . 归并排序 . 选择排序 正确答案： 8.
3、在下述几种排序方法中，辅助空间需要最多的是 ()。 . 直接插入排序 . 快速排序 . 直接选择排序 . 归并排序 正确答案： 9. 完全二叉树是下列情况的哪一种 ( )。 . 一定是满二叉树 . 可能是满二叉树 . 一定不是满二叉树 . 不是二叉树 正确答案： 10. 四个元素进入队列 QU 的顺序是 U、V、X、Y，进行 Quu(QU,x)操作后，队头元素是 ( )。. U . V . X . Y 正确答案： 11. 在 k 叉树中，度为 0 的结点称为 ( )。 . 根 . 叶 . 祖先 . 子孙 正确答案： 12. 在下列排序算法中，哪一个算法的时间复杂度与记录初始排列无关 ()。 .
4、 直接插入排序 . 冒泡排序 . 快速排序 . 直接选择排序 正确答案： 13. 由 3 个结点可以构造出多少种不同的二叉树？( ). 15谋学网 . 21 . 30 . 33 正确答案： 14. 对于 3 个结点、 、 ，可构成二叉树的不同形态数为 ( )。. 3 . 4 . 5 . 6 正确答案： 15. 下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受 数据初始特性影响的是 ()。 . 直接插入排序 . 快速排序 . 直接选择排序 . 堆排序 正确答案： 16. ISM 是索引顺序存取方法，该方法是专为下面的哪一种设备设计的 ()。 . 磁带 . 磁盘 . 光盘
5、 . 外存储器 正确答案： 17. 在下面的叙述中，正确的是 ( )。 . 树的先根遍历序列与其对应的二叉树的后序遍历序列相同 . 树的后根遍历序列与其对应的二叉树的前序遍历序列相同 . 树的后根遍历序列与其对应的二叉树的中序遍历序列相同 . 树的后根遍历序列与其对应的二叉树的后序遍历序列相同 正确答案： 18. 广义表 ( , , , ) ) 的表尾是 ()。. . ( ) . ( , , , ) . ( , , ) 正确答案： 19. 设二叉树有 n 个结点且根结点的层数为 0，则二叉树的高度为 ( )。. n-1 . log2(n+1) -1 . ?log2n? . 不确定 正确答案：
6、20. h 指向的带表头结点的单链表为空的判定条件是 ( )。. h = = NULL谋学网 . h-nxt = = h . h ! = NULL . h-nxt = = NULL 正确答案：数据结构 16 秋在线作业 1二、判断题（共 20 道试题，共 40 分。 ）1. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中 的结点个数有关，而与图的边数无关。 . 错误 . 正确 正确答案： 2. 任何一个递归过程都可以转换成非递归过程。 . 错误 . 正确 正确答案： 3. 在任何情况下，归并排序都比直接插入排序快。 . 错误 . 正确 正确答案： 4. 若输入序列
7、为 1, 2, 3, 4, 5, 6，则通过一个栈可以输出序列 1, 5, 4, 6, 2, 3。 . 错误 . 正确 正确答案： 5. 链表的存储密度大于顺序表的存储密度。 . 错误 . 正确 正确答案： 6. 数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。 . 错误 . 正确 正确答案： 7. 哈希表(散列表)的平均查找长度与处理冲突的方法无关。 . 错误 . 正确 正确答案：谋学网 8. 顺序存储结构的主要缺点是不利于插入、删除操作。 . 错误 . 正确 正确答案： 9. 二叉树中序线索化后，不存在空指针域。 . 错误 . 正确 正确答案： 10. 存放在磁盘、磁带
8、上的文件，既可以是顺序文件，也可以是索引结构或其他结构类型 的文件。 . 错误 . 正确 正确答案： 11. 有 n 个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素个数 的一半。 . 错误 . 正确 正确答案： 12. 堆是完全二叉树。 . 错误 . 正确 正确答案： 13. OV 网的含义是以顶点表示活动的网。 . 错误 . 正确 正确答案： 14. 虽然关键字序列的顺序不一样，但依此生成的二叉排序树却是一样的。 . 错误 . 正确 正确答案： 15. 通常使用队列来处理函数或过程的调用。 . 错误 . 正确 正确答案： 16. 在用堆排序算法排序时，如果要进行增序排序，
9、则需要采用“大根堆” 。 . 错误 . 正确 正确答案： 17. 分块查找在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每 块中的元素个数有关。 . 错误 . 正确 正确答案：谋学网 18. 将一棵树转成二叉树，根结点没有左子树。 . 错误 . 正确 正确答案： 19. 链表与顺序存储结构相比，在链表中进行插入、删除操作的效率高。 . 错误 . 正确 正确答案： 20. 将森树转成二叉树，根结点没有右子树。 . 错误 . 正确 正确答案：数据结构 16 秋在线作业 1一、单选题（共 20 道试题，共 60 分。 ）1. 将一个 1.100, 1.100 的三对角矩阵，按行优先
10、次序存入一维数组1.298 中， 中元素 66, 65 在数组中的位置 K 为 () 。. 193 . 195 . 197 . 199 正确答案： 2. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址 ( )。 . 必须是连续的 . 部分地址必须是连续的 . 一定是不连续的 . 连续或不连续都可以 正确答案： 3. 对于二维数组44，数组的起始位置 LO(00)=1000，元素长度为 2，则 LO(33) 为()。. 1000 . 1010 . 1008 . 1020 正确答案： 4. 设有 n 个结点的二叉排序树，对于成功的查找，最少的比较次数为()。谋学网 . ( 1 ) . (
11、log2n) . (n) . (nlog2n) 正确答案： 5. 在 k 叉树中，度为 0 的结点称为 ( )。 . 根 . 叶 . 祖先 . 子孙 正确答案： 6. 相对于顺序存储而言，链接存储的优点是 ( )。 . 随机存取 . 节省空间 . 插入、删除操作方便 . 结点间关系简单 正确答案： 7. 二叉树在中序线索化后，仍不能有效求解的问题是 ( )。 . 求指定结点的前序后继 . 求指定结点的中序前驱 . 求指定结点的中序后继 . 求指定结点的后序后继 正确答案： 8. 求顶点间的最短路径问题，考虑的是下面的哪一种图 ()。 . 无向图 . 有向图 . 带权的无向图 . 带权的有向图
12、正确答案： 9. 下列哪一种图的邻接矩阵是对称矩阵？ () . 有向图 . 无向图 . OV 网 . O 网 正确答案： 10. 插入、删除只能在同一端进行的线性表，称为 ( )。 . 队列 . 循环队列 . 栈 . 循环栈 正确答案： 11. 设根结点的层数为 0，若高度为 h 的二叉树上只有度为 0 和度为 2 的结点，则此二叉 树上所包含的结点数至少为 ( )。谋学网 . h+1 . 2h-1 . 2h . 2h+1 正确答案： 12. 数组6,7 的每个元素占 5 个字节，将其按列优先次序存储在起始地址为 1000 的内存 单元中，则元素5,5 的地址是 ()。. 1165 . 117
13、0 . 1175 . 1180 正确答案： 13. 在对 n 个元素的序列进行排序时，堆排序所需要的附加存储空间是 ()。. O(log2n ) . O( 1 ) . O(n ) . O(nlog2n ) 正确答案： 14. 某二叉树结点的前序序列为，中序序列为，则该二叉树结点的后序序列为 ( )。. . . . 正确答案： 15. 折半查找要求结点 ()。 . 无序、顺序存储 . 无序、链接存储 . 有序、顺序存储 . 有序、链接存储 正确答案： 16. 在待排序的元素序列基本有序的前提下，效率最高的排序方法是 ()。 . 直接插入排序 . 快速排序 . 直接选择排序 . 归并排序 正确答案
14、： 17. 散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值 ()。 . 同等概率 . 最大概率 . 最小概率 . 平均概率 正确答案： 18. 平衡的二叉排序树(VL 树)属于()的数据结构。谋学网 . 动态 . 静态 . 线性 . 无结构 正确答案： 19. 若设根结点的层数为 0，则高(或深)度为 4 的二叉树至多含有的结点数为 ( )。. 10 . 16 . 31 . 32 正确答案： 20. 下列描述中正确的是 ( )。 . 线性表的逻辑顺序与存储顺序总是一致的 . 每种数据结构都具备查找、插入和删除三种基本运算 . 数据结构实质上包括逻辑结构和存储结构两方面的
15、内容 . 选择合适的数据结构是解决应用问题的关键步骤 正确答案：数据结构 16 秋在线作业 1二、判断题（共 20 道试题，共 40 分。 ）1. 归并排序在任何情况下都比所有简单的排序方法速度快。 . 错误 . 正确 正确答案： 2. 哈希函数越复杂越好，因为这样随机性好，冲突概率小。 . 错误 . 正确 正确答案： 3. 连通图的各边权值均不相同，则该图的最小生成树是唯一的。 . 错误 . 正确 正确答案： 4. 一棵哈夫曼树的带权 ( 外部 ) 路径长度等于其中所有分支结点的权值之和。 . 错误 . 正确 正确答案：谋学网 5. 线性表只能用顺序存储结构实现。 . 错误 . 正确 正确答案： 6. 链表中的表头结点使得插入、删除操作简单。 . 错误 . 正确 正确答案： 7. 串是一种数据对象和操作都特殊的线性表。 . 错误 . 正确 正确答案： 8. 二叉树结点的中序遍历序列与前序遍历序列可以唯一地确定该棵二叉树。 . 错误 . 正确 正确答案： 9. 稀疏矩阵压缩存储后，必会失去随机存取功能。 . 错误 . 正确 正确答案： 10. 任何一个递归过程都可以转换成非递归过程。
