东师《数据结构16秋在线作业1

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