1、东北师范数据结构16秋在线作业2数据结构16秋在线作业2一、单选题（共 20 道试题，共 60 分。）1. 在下述几种排序方法中，辅助空间需要最多的是 ()。. 直接插入排序. 快速排序. 直接选择排序. 归并排序正确答案：2. 广义表运算式til ( ( ( , ) , ( , ) ) ) 的操作结果是 ()。. ( , ). , . ( ( , ) ). 正确答案：3. 下列序列中，() 是执行第一趟按递减序快速排序后所得的序列。. 68, 11 , 18 , 69 70 23 , 93 , 73. 68 , 11 , 69 , 23 70 18, 93, 73 . 93, 73 70 6
2、8, 11, 69, 23, 18 . 68 , 11 , 69, 23, 18 70 93, 73 正确答案：4. 递归过程的实现需用到 ( )。. 线性表. 链表. 栈. 队列正确答案：5. 数组6,7 的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素5,5 的地址是 ()。. 1165. 1170. 1175. 1180正确答案：6. VL树中任一结点的平衡因子的绝对值都应小于等于 ()。. 0. 1. 2. 3正确答案：7. 下述文件中适合于磁带存储的是 ()。. 顺序文件. 索引文件. 散列文件. 多关键字文件正确答案：8. 在n个结点的线索二叉树中
3、线索的数目为 ( )。. n-1. n. n+1. 2n正确答案：9. 一棵左子树为空的二叉树在前序线索化后，其中空的链域的个数是：( )。. 不确定. 0. 1. 2正确答案：10. 有n个顶点的无向图的边数最多为 ()。. n. n(n-1). n(n-1)/2. 2n正确答案：11. 由3个结点可以构造出多少种不同的有向无序树？( ). 9. 10. 11. 12正确答案：12. 引入线索二叉树的目的是 ( )。. 加快查找结点的前驱或后继的速度. 为了能方便地找到双亲. 为了能在二叉树中方便地进行插入与删除. 使二叉树的遍历结果唯一正确答案：13. 设有n个结点的最佳二叉排序树，对于成
4、功的查找，最少的比较次数为()。. ( 1 ). (log2n). (n). (nlog2n)正确答案：14. 插入、删除只能在同一端进行的线性表，称为 ( )。. 队列. 循环队列. 栈. 循环栈正确答案：15. 完全二叉树是下列情况的哪一种 ( )。. 一定是满二叉树. 可能是满二叉树. 一定不是满二叉树. 不是二叉树正确答案：16. 若对n阶对称矩阵按行优先顺序将其下三角形的元素（包括主对角线上的所有元素）依次存放于一维数组 1.n(n+1)/2 中，则在中确定ij ( i rtg = = 0. p-rtg = = 1. p ! = NULL. p-lhil ! = NULL正确答案：1
5、0. 由3个结点可以构造出多少种不同的二叉树？( ). 15. 21. 30. 33正确答案：11. 在下述几种排序方法中，不稳定的排序方法是 ()。. 直接插入排序. 冒泡排序. 直接选择排序. 归并排序正确答案：12. 在n个结点的线索二叉树中线索的数目为 ( )。. n-1. n. n+1. 2n正确答案：13. h指向的非空的单循环链表的尾结点(由p所指向)满足 ( )。. p-nxt = = NULL. p = = NULL. p-nxt = = h. p = = h正确答案：14. 设二维数组0.m-10.n-1按行优先顺序存储且每个元素占个单元，则元素ij的地址为 ()。. LO
6、(00) + (j*m+i)*. LO(00) + (i*n+j)*. LO(00) + (j-1)*m+i-1*. LO(00) + (i-1)*n+j-1*正确答案：15. 在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点的操作是 ( )。. r = f-nxt;. r = r-nxt;. f = f-nxt;. f = r-nxt;正确答案：16. 顺序表中逻辑上相邻的结点其物理位置也 ( )。. 一定相邻. 不必相邻. 按某种规律排列. 无要求正确答案：17. 下面的排序方法中，辅助空间为O( n ) 的是 ()。. 希尔排序. 堆排序. 选择排序. 归并排序正确答案：18.
7、 若对n阶对称矩阵按行优先顺序将其下三角形的元素（包括主对角线上的所有元素）依次存放于一维数组 1.n(n+1)/2 中，则在中确定ij ( i j）的位置k的关系为 () 。. i*(i-1)/2+j. j*(j-1)/2+i. i*(i+1)/2+j. j*(j+1)/2+i正确答案：19. 下列描述中正确的是 ( )。. 线性表的逻辑顺序与存储顺序总是一致的. 每种数据结构都具备查找、插入和删除三种基本运算. 数据结构实质上包括逻辑结构和存储结构两方面的内容. 选择合适的数据结构是解决应用问题的关键步骤正确答案：20. 若设根结点的层数为0，则高(或深)度为4的二叉树至多含有的结点数为
8、( )。. 10. 16. 31. 32正确答案： 数据结构16秋在线作业2二、判断题（共 20 道试题，共 40 分。）1. 在平衡的二叉排序树中，向某个平衡因子不为零的结点的树中插入一新结点，必引起平衡旋转。. 错误. 正确正确答案：2. 程序一定是算法。. 错误. 正确正确答案：3. 用二叉树的前序遍历和中序遍历可以导出二叉树的后序遍历。. 错误. 正确正确答案：4. 在指定结点之前插入新结点时，双链表比单链表更方便。. 错误. 正确正确答案：5. 二叉树结点的中序遍历序列与后序遍历序列可以唯一地确定该棵二叉树。. 错误. 正确正确答案：6. 若哈希表(散列表)的负载因子 lhil !
9、= NULL. p-ltg = = 0. p-ltg = = 1正确答案：12. 相对于顺序存储而言，链接存储的优点是 ( )。. 随机存取. 节省空间. 插入、删除操作方便. 结点间关系简单正确答案：13. 树最适合用来表示 ( )。. 有序数据元素. 无序数据元素. 元素之间具有分支层次关系的数据. 元素之间无联系的数据正确答案：14. 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行 ( )。. p-nxt = s; s-nxt = q;. s-nxt = p-nxt; p-nxt = s;. p-nxt = s-nxt; s-nxt = p;. q
10、-nxt = s; s-nxt = p;正确答案：15. 递归过程的实现需用到 ( )。. 线性表. 链表. 栈. 队列正确答案：16. 堆的形状是一棵 ( )。. 二叉排序树. 满二叉树. 完全二叉树. VL树正确答案：17. 数组6,7 的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素5,5 的地址是 ()。. 1165. 1170. 1175. 1180正确答案：18. 下列序列中，() 是执行第一趟按递减序快速排序后所得的序列。. 68, 11 , 18 , 69 70 23 , 93 , 73. 68 , 11 , 69 , 23 70 18, 93
11、, 73 . 93, 73 70 68, 11, 69, 23, 18 . 68 , 11 , 69, 23, 18 70 93, 73 正确答案：19. 每一个(存储)结点不仅含有一个数据元素，还包含一组指针，该存储方式是 ( )。. 顺序存储. 链接存储. 索引存储. 散列存储正确答案：20. 对关键码序列 28 , 16 , 32, 12, 60, 2, 5, 72 快速排序 ( 从小到大序 ) , 一次划分的结果为 ()。. ( 2 , 5 , 12 , 16 ) 28 ( 60 , 32 , 72 ). ( 5 , 16 , 2 , 12 ) 28 ( 60 , 32 , 72 ).
12、 ( 2 , 16 , 12 , 5 ) 28 ( 60 , 32 , 72 ). ( 5 , 16 , 2 , 12 ) 28 ( 32 , 60 , 72 )正确答案： 数据结构16秋在线作业2二、判断题（共 20 道试题，共 40 分。）1. 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小与图中的结点个数有关，而与图的边数无关。. 错误. 正确正确答案：2. 折半查找法的查找速度一定比顺序查找法快。. 错误. 正确正确答案：3. 直接访问文件也能顺序访问，只是一般效率不高。. 错误. 正确正确答案：4. 在中序线索二叉树中，每一非空的线索均指向其祖先结点。. 错误
13、. 正确正确答案：5. 二叉树中序线索化后，不存在空指针域。. 错误. 正确正确答案：6. 链表中的表头结点使得插入、删除操作简单。. 错误. 正确正确答案：7. 将一棵树转成二叉树，根结点没有左子树。. 错误. 正确正确答案：8. 内部排序要求数据一定要以顺序方式进行存储。. 错误. 正确正确答案：9. 堆排序是稳定的排序方法。. 错误. 正确正确答案：10. 有n个顶点的无向图，采用邻接矩阵表示，图中的边数等于邻接矩阵中非零元素个数的一半。. 错误. 正确正确答案：11. 二叉树结点的中序遍历序列与前序遍历序列可以唯一地确定该棵二叉树。. 错误. 正确正确答案：12. 快速排序总比简单的排
14、序方法快。. 错误. 正确正确答案：13. 在待排数据基本有序的情况下，快速排序效果最好。. 错误. 正确正确答案：14. 数据对象是具有相同性质的数据元素的集合。. 错误. 正确正确答案：15. 空串是由空格构成的串。. 错误. 正确正确答案：16. 在二叉树中插入结点，则此二叉树便不再是二叉树了。. 错误. 正确正确答案：17. 在图G的最小生成树T中，可能会有某条边的权值超过未选边的权值。. 错误. 正确正确答案：18. 从逻辑结构上看，n维数组的每个元素均属于n个向量。. 错误. 正确正确答案：19. 必须把一般的树转换成二叉树后才能进行存储。. 错误. 正确正确答案：20. 任何二叉
15、树的后序线索树进行后序遍历时都必须用栈。. 错误. 正确正确答案： 数据结构16秋在线作业2一、单选题（共 20 道试题，共 60 分。）1. 下面的排序方法中，辅助空间为O( n ) 的是 ()。. 希尔排序. 堆排序. 选择排序. 归并排序正确答案：2. 线索二叉树是一种 ( ) 结构。. 逻辑. 物理. 逻辑和存储. 线性正确答案：3. 判断线索二叉树中某结点p有右子女的条件是 ( )。. p-rtg = = 0. p-rtg = = 1. p ! = NULL. p-lhil ! = NULL正确答案：4. 若由树转化得到的二叉树是非空的二叉树，则二叉树形状是 ( )。. 根结点无右子
16、树的二叉树. 根结点无左子树的二叉树. 根结点可能有左子树和右子树. 各结点只有一个子女的二叉树正确答案：5. 对于二维数组44，数组的起始位置LO(00)=1000，元素长度为2，则LO(33)为()。. 1000. 1010. 1008. 1020正确答案：6. 设散列地址空间为0m-1，ky为关键字，用p去除ky，将得到的余数作为ky的散列地址，即h(ky) = ky % p。为了减少发生冲突的频率，一般取p为 ()。. 小于等于m的最大奇数. 小于等于m的最大偶数. 小于等于m的最大素数. 小于等于m的最大合数正确答案：7. 下面说法不正确的是 ()。. 广义表的表头总是一个广义表.
17、广义表的表尾总是一个广义表. 广义表常采用链接存储结构. 广义表可以是一个多层次的结构正确答案：8. 在有向图G的拓扑序列中，若顶点Vi在Vj之前，则下列情形不可能出现的是 () 。. G中有弧Vi , Vj . G中有一条从Vi到Vj 的路径. G中没有弧Vi , Vj . G中有一条从Vj到Vi 的路径正确答案：9. “堆积”问题是由于()引起的。. 同义词之间发生冲突. 散列函数. 不同的同义词子表结合在一起. 散列表“溢出”正确答案：10. 设有n个结点的二叉排序树，对于成功的查找，最多的比较次数为()。. ( 1 ). (log2n). (n). (nlog2n)正确答案：11. 就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是 () 。. 堆排序快速排序归并排序. 堆排序归并排序快速排序. 堆排序归并排序快速排序. 堆排序快速排序归并排序正确答案：12. 若X是中序线索二叉树中一个有右子女的结点，且X不为根，则X的中序后继为 ( )。. X的双亲. X的右子树中最左下的结点. X的左子树中最右下的结点.
