《东师数据结构16秋在线作业.doc》由会员分享，可在线阅读，更多相关《东师数据结构16秋在线作业.doc（15页珍藏版）》请在三一文库上搜索。
1、东北师范大学东师数据结构16秋在线作业2一、单选题（共 20 道试题，共 60 分。）1. 在下述几种排序方法中，辅助空间需要最多的是 ()。A. 直接插入排序B. 快速排序C. 直接选择排序D. 归并排序正确答案：2. 广义表运算式tail ( ( ( a , b ) , ( c , d ) ) ) 的操作结果是 ()。A. ( c , d )B. c , dC. ( ( c , d ) )D. d正确答案：3. 下列序列中，() 是执行第一趟按递减序快速排序后所得的序列。A. 68, 11 , 18 , 69 70 23 , 93 , 73B. 68 , 11 , 69 , 23 70 1
2、8, 93, 73 C. 93, 73 70 68, 11, 69, 23, 18 D. 68 , 11 , 69, 23, 18 70 93, 73 正确答案：4. 递归过程的实现需用到 ( )。A. 线性表B. 链表C. 栈D. 队列正确答案：5. 数组A6,7 的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5,5 的地址是 ()。A. 1165B. 1170C. 1175D. 1180正确答案：6. AVL树中任一结点的平衡因子的绝对值都应小于等于 ()。A. 0B. 1C. 2D. 3正确答案：7. 下述文件中适合于磁带存储的是 ()。A. 顺序文
3、件B. 索引文件C. 散列文件D. 多关键字文件正确答案：8. 在n个结点的线索二叉树中线索的数目为 ( )。A. n-1B. nC. n+1D. 2n正确答案：9. 一棵左子树为空的二叉树在前序线索化后，其中空的链域的个数是：( )。A. 不确定B. 0C. 1D. 2正确答案：10. 有n个顶点的无向图的边数最多为 ()。A. nB. n(n-1)C. n(n-1)/2D. 2n正确答案：11. 由3个结点可以构造出多少种不同的有向无序树？( )A. 9B. 10C. 11D. 12正确答案：12. 引入线索二叉树的目的是 ( )。A. 加快查找结点的前驱或后继的速度B. 为了能方便地找到
4、双亲C. 为了能在二叉树中方便地进行插入与删除D. 使二叉树的遍历结果唯一正确答案：13. 设有n个结点的最佳二叉排序树，对于成功的查找，最少的比较次数为()。A. ( 1 )B. (log2n)C. (n)D. (nlog2n)正确答案：14. 插入、删除只能在同一端进行的线性表，称为 ( )。A. 队列B. 循环队列C. 栈D. 循环栈正确答案：15. 完全二叉树是下列情况的哪一种 ( )。A. 一定是满二叉树B. 可能是满二叉树C. 一定不是满二叉树D. 不是二叉树正确答案：16. 若对n阶对称矩阵A按行优先顺序将其下三角形的元素（包括主对角线上的所有元素）依次存放于一维数组B 1.n(
5、n+1)/2 中，则在B中确定aij ( i < j）的位置k的关系为 () 。A. i*(i-1)/2+jB. j*(j-1)/2+iC. i*(i+1)/2+jD. j*(j+1)/2+i正确答案：17. 设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为100，每个元素占一个地址空间，则a 85的地址为 ()。A. 112B. 132C. 118D. 140正确答案：18. 存放在外存中的数据的组织结构是 ()。A. 数组B. 表C. 文件D. 链表正确答案：19. 下列描述中正确的是 ( )。A. 线性表的逻辑顺序与存储顺序总是一致的B
6、. 每种数据结构都具备查找、插入和删除三种基本运算C. 数据结构实质上包括逻辑结构和存储结构两方面的内容D. 选择合适的数据结构是解决应用问题的关键步骤正确答案：20. 顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用 () 的方法可降低所需的代价。A. 附加文件B. 按关键字大小排序C. 按记录输入先后排序D. 连续排序正确答案： 数据结构16秋在线作业2二、判断题（共 20 道试题，共 40 分。）1. 所谓取广义表的表尾就是返回广义表中最后一个元素。A. 错误B. 正确正确答案：2. 强连通分量是无向图的极大强连通子图。A. 错误B.
7、正确正确答案：3. 当广义表中的每个元素都是原子时，广义表便成了线性表。A. 错误B. 正确正确答案：4. 需要借助于一个栈来实现DFS算法。A. 错误B. 正确正确答案：5. 通常使用队列来处理函数或过程的调用。A. 错误B. 正确正确答案：6. 稀疏矩阵压缩存储后，必会失去随机存取功能。A. 错误B. 正确正确答案：7. 完全二叉树的存储结构通常采用顺序存储结构。A. 错误B. 正确正确答案：8. 归并排序的辅助存储空间代价为O(1 )。A. 错误B. 正确正确答案：9. 拓扑排序算法仅适用于有向无环图。A. 错误B. 正确正确答案：10. 任何一棵二叉树都可以不用栈实现前序线索二叉树的前
8、序遍历。A. 错误B. 正确正确答案：11. 将一棵树转成二叉树，根结点没有左子树。A. 错误B. 正确正确答案：12. 在图G的最小生成树T中，可能会有某条边的权值超过未选边的权值。A. 错误B. 正确正确答案：13. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。A. 错误B. 正确正确答案：14. 用链表 ( lchild-rchild表示法 ) 存储的包含n个结点的二叉树，结点的2n个指针域中有n + l 个空指针。A. 错误B. 正确正确答案：15. 算法的优劣与算法描述语言无关，但与所用计算机有关。A. 错误B. 正确正确答案：16. 对n个记录的文件进行堆排序，最坏情况下的执行
9、时间是O(nlog2n )。A. 错误B. 正确正确答案：17. 数组是同类型值的集合。A. 错误B. 正确正确答案：18. 哈希表(散列表)的结点中只包含数据元素自身的信息，不包含任何指针。A. 错误B. 正确正确答案：19. 折半插入排序所需比较次数与待排序记录的初始排列状态无关。A. 错误B. 正确正确答案：20. 链接存储结构属动态存储方式。A. 错误B. 正确正确答案： 数据结构16秋在线作业2一、单选题（共 20 道试题，共 60 分。）1. 下列哪一种图的邻接矩阵是对称矩阵？ ()A. 有向图B. 无向图C. AOV 网D. AOE 网正确答案：2. “堆积”问题是由于()引起的
10、。A. 同义词之间发生冲突B. 散列函数C. 不同的同义词子表结合在一起D. 散列表“溢出”正确答案：3. 采用邻接表存储的图的广度优先遍历类似于二叉树的 ()。A. 前序遍历B. 中序遍历C. 后序遍历D. 层次遍历正确答案：4. 下列排序方法中，哪一个是稳定的排序方法？()A. 直接选择排序B. 直接插入排序C. 希尔排序D. 快速排序正确答案：5. 顺序存储结构的优点是( )。A. 存储密度大B. 插入运算方便C. 删除运算方便D. 结构可动态变化正确答案：6. 堆的形状是一棵 ( )。A. 二叉排序树B. 满二叉树C. 完全二叉树D. AVL树正确答案：7. 一个有n个结点的图，连通分
11、量的个数最少为 ()。A. 0B. 1C. n-1D. n正确答案：8. 在栈中存取数据的原则是 ( )。A. 先进先出B. 后进先出C. 后进后出D. 随意进出正确答案：9. 判断线索二叉树中某结点p有右子女的条件是 ( )。A. p->rtag = = 0B. p->rtag = = 1C. p ! = NULLD. p->lchild ! = NULL正确答案：10. 由3个结点可以构造出多少种不同的二叉树？( )A. 15B. 21C. 30D. 33正确答案：11. 在下述几种排序方法中，不稳定的排序方法是 ()。A. 直接插入排序B. 冒泡排序C. 直接选择排序D
12、. 归并排序正确答案：12. 在n个结点的线索二叉树中线索的数目为 ( )。A. n-1B. nC. n+1D. 2n正确答案：13. head指向的非空的单循环链表的尾结点(由p所指向)满足 ( )。A. p->next = = NULLB. p = = NULLC. p->next = = headD. p = = head正确答案：14. 设二维数组A0.m-10.n-1按行优先顺序存储且每个元素占c个单元，则元素Aij的地址为 ()。A. LOC(A00) + (j*m+i)*cB. LOC(A00) + (i*n+j)*cC. LOC(A00) + (j-1)*m+i-1
13、*cD. LOC(A00) + (i-1)*n+j-1*c正确答案：15. 在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点的操作是 ( )。A. r = f->next;B. r = r->next;C. f = f->next;D. f = r->next;正确答案：16. 顺序表中逻辑上相邻的结点其物理位置也 ( )。A. 一定相邻B. 不必相邻C. 按某种规律排列D. 无要求正确答案：17. 下面的排序方法中，辅助空间为O( n ) 的是 ()。A. 希尔排序B. 堆排序C. 选择排序D. 归并排序正确答案：18. 若对n阶对称矩阵A按行优先顺序将其下
14、三角形的元素（包括主对角线上的所有元素）依次存放于一维数组B 1.n(n+1)/2 中，则在B中确定aij ( i < j）的位置k的关系为 () 。A. i*(i-1)/2+jB. j*(j-1)/2+iC. i*(i+1)/2+jD. j*(j+1)/2+i正确答案：19. 下列描述中正确的是 ( )。A. 线性表的逻辑顺序与存储顺序总是一致的B. 每种数据结构都具备查找、插入和删除三种基本运算C. 数据结构实质上包括逻辑结构和存储结构两方面的内容D. 选择合适的数据结构是解决应用问题的关键步骤正确答案：20. 若设根结点的层数为0，则高(或深)度为4的二叉树至多含有的结点数为 (
15、)。A. 10B. 16C. 31D. 32正确答案： 数据结构16秋在线作业2二、判断题（共 20 道试题，共 40 分。）1. 在平衡的二叉排序树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。A. 错误B. 正确正确答案：2. 程序一定是算法。A. 错误B. 正确正确答案：3. 用二叉树的前序遍历和中序遍历可以导出二叉树的后序遍历。A. 错误B. 正确正确答案：4. 在指定结点之前插入新结点时，双链表比单链表更方便。A. 错误B. 正确正确答案：5. 二叉树结点的中序遍历序列与后序遍历序列可以唯一地确定该棵二叉树。A. 错误B. 正确正确答案：6. 若哈希表(散列表)的
16、负载因子 < l，则可避免冲突的产生。A. 错误B. 正确正确答案：7. 对于插入、删除运算来说，链接存储结构一定优于顺序存储结构。A. 错误B. 正确正确答案：8. 在有向图中，度为0的顶点称为终端顶点(或叶子)。A. 错误B. 正确正确答案：9. 空串是由空格构成的串。A. 错误B. 正确正确答案：10. 算法的优劣与算法描述语言无关，但与所用计算机有关。A. 错误B. 正确正确答案：11. 树（森林）的结点的先根遍历和后根遍历分别与它相应二又树的结点前序遍历和后序遍历是一致的。A. 错误B. 正确正确答案：12. 栈和队列都是限制存取点的线性结构。A. 错误B. 正确正确答案：13
17、. 二叉树的叶结点，在前序遍历、中序遍历和后序遍历下皆以相同的相对位置出现。A. 错误B. 正确正确答案：14. 数组是同类型值的集合。A. 错误B. 正确正确答案：15. 若输入序列为1, 2, 3, 4, 5, 6，则通过一个栈可以输出序列1, 5, 4, 6, 2, 3。A. 错误B. 正确正确答案：16. 后序线索二叉树是不完善的，要对它进行遍历，还需要使用栈。A. 错误B. 正确正确答案：17. 一棵哈夫曼树的带权 ( 外部 ) 路径长度等于其中所有分支结点的权值之和。A. 错误B. 正确正确答案：18. 若一个有向图的邻接矩阵对角线以下的元素均为零，则该图的拓扑有序序列必定存在。A
18、. 错误B. 正确正确答案：19. 堆是满二叉树。A. 错误B. 正确正确答案：20. 在待排序记录已经有序时，快速排序算法的时间复杂度为O(nlog2n )。A. 错误B. 正确正确答案： 数据结构16秋在线作业2一、单选题（共 20 道试题，共 60 分。）1. 由3个结点可以构造出多少种不同的有向有序树？( )A. 9B. 10C. 11D. 12正确答案：2. “堆积”问题是由于()引起的。A. 同义词之间发生冲突B. 散列函数C. 不同的同义词子表结合在一起D. 散列表“溢出”正确答案：3. 下列哪项不是利用查找表中数据元素的关系进行查找的方法 ()。A. 有序表的查找B. 二叉排序
19、树的查找C. AVL树D. 散列查找正确答案：4. 一个算法应该是（）。A. 程序B. 问题求解步骤的描述C. 要满足五个基本特性D. A和C正确答案：5. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址 ( )。A. 必须是连续的B. 部分地址必须是连续的C. 一定是不连续的D. 连续或不连续都可以正确答案：6. 下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。( )A. 二叉排序树B. 哈夫曼树C. AVL树D. 堆正确答案：7. 设有两个串s1和s2，求s2在s1中首次出现的位置的运算称为 ( )。A. 求子串B. 求串长C. 联接D.
20、模式匹配正确答案：8. 假定有k个关键字互为同义词，若采用线性探查法把这k个关键字存入散列表中，至少需要进行多少次探测？（）A. k-1次B. k次C. k+1次D. k(k+1)/2次正确答案：9. 最佳二叉排序树属于()的数据结构。A. 动态B. 静态C. 线性D. 无结构正确答案：10. 一个栈的入栈序列是a、b、c，则栈的不可能的输出序列是 ( )。A. acbB. abcC. bcaD. cab正确答案：11. 判断线索二叉树中某结点p有左子女的条件是 ( )。A. p ! = NULLB. p->lchild ! = NULLC. p->ltag = = 0D. p-&
21、gt;ltag = = 1正确答案：12. 相对于顺序存储而言，链接存储的优点是 ( )。A. 随机存取B. 节省空间C. 插入、删除操作方便D. 结点间关系简单正确答案：13. 树最适合用来表示 ( )。A. 有序数据元素B. 无序数据元素C. 元素之间具有分支层次关系的数据D. 元素之间无联系的数据正确答案：14. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行 ( )。A. p->next = s; s->next = q;B. s->next = p->next; p->next = s;C. p->next
22、= s->next; s->next = p;D. q->next = s; s->next = p;正确答案：15. 递归过程的实现需用到 ( )。A. 线性表B. 链表C. 栈D. 队列正确答案：16. 堆的形状是一棵 ( )。A. 二叉排序树B. 满二叉树C. 完全二叉树D. AVL树正确答案：17. 数组A6,7 的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A5,5 的地址是 ()。A. 1165B. 1170C. 1175D. 1180正确答案：18. 下列序列中，() 是执行第一趟按递减序快速排序后所得的序列。A. 68
23、, 11 , 18 , 69 70 23 , 93 , 73B. 68 , 11 , 69 , 23 70 18, 93, 73 C. 93, 73 70 68, 11, 69, 23, 18 D. 68 , 11 , 69, 23, 18 70 93, 73 正确答案：19. 每一个(存储)结点不仅含有一个数据元素，还包含一组指针，该存储方式是 ( )。A. 顺序存储B. 链接存储C. 索引存储D. 散列存储正确答案：20. 对关键码序列 28 , 16 , 32, 12, 60, 2, 5, 72 快速排序 ( 从小到大序 ) , 一次划分的结果为 ()。A. ( 2 , 5 , 12 ,
24、 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 )正确答案： 数据结构16秋在线作业2二、判断题（共 20 道试题，共 40 分。）1. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中的结点个数有关，而与图的边数无关。A. 错误B. 正确正确答案：2. 折半查找法的查找速度一定比顺序查找法快。A. 错误B. 正确正确答案：3. 直接访问文件也能顺序访问，只是一般效率不高。A. 错误B. 正确正确答案：4. 在中序线索二叉树中，每一非空的线索均指向其祖先结点。A. 错误B. 正确正确答案：5. 二叉树中序线索化后，不存在空指针域。A. 错误B. 正确正确答案：6. 链表中的表头结点使得插入、删除操作简单。A. 错误B. 正确15 / 15文档可自由编辑打印