东师数据结构16秋在线作业.doc

东北师范大学东师数据结构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 18, 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. 顺序文件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. 为了能方便地找到双亲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(n+1)/2 中，则在B中确定aij ( i rtag = = 0B. p-rtag = = 1C. p ! = NULLD. p-lchild ! = NULL正确答案：10. 由3个结点可以构造出多少种不同的二叉树？( )A. 15B. 21C. 30D. 33正确答案：11. 在下述几种排序方法中，不稳定的排序方法是 ()。A. 直接插入排序B. 冒泡排序C. 直接选择排序D. 归并排序正确答案：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*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按行优先顺序将其下三角形的元素（包括主对角线上的所有元素）依次存放于一维数组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的二叉树至多含有的结点数为 ( )。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. 若哈希表(散列表)的负载因子 lchild ! = NULLC. p-ltag = = 0D. p-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 = 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, 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 , 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. 正确正