16春季福师《数据结构概论》在线作业一.doc

谋学网福师数据结构概论在线作业一一、单选题（共 25 道试题，共 50 分。）1. 具有10个叶结点的二叉树中有（ ）个度为2的结点，. 8. 9. 10. ll正确答案：2. 若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ ）. 9. 11. 15. 不确定正确答案：3. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度（ ）(1=i=n+1)。. O(0). O(1). O(n). O(n2)正确答案：4. 对N个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（ ）. （N+1）/2. N/2. N. （1+N）*N /2正确答案：5. 连续存储设计时，存储单元的地址（ ）。. 一定连续. 一定不连续. 不一定连续. 部分连续，部分不连续正确答案：6. 表达式*(+)-的后缀表达式是( )。. *+-. +*-. *+-. -+*正确答案：7. 动态存储管理系统中，通常可有（ ）种不同的分配策略。. 1. 2. 3. 4正确答案：8. 要连通具有n个顶点的有向图，至少需要（ ）条边。. n-l. n. n+l. 2n正确答案：9. 在完全二叉树中，若一个结点是叶结点，则它没（ ）。. 左子结点. 右子结点. 左子结点和右子结点. 左子结点，右子结点和兄弟结点正确答案：10. 下列排序算法中（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。. 堆排序. 冒泡排序. 快速排序. 插入排序正确答案：11. 下面有关算法说法错误的是（ ）. 算法最终必须由计算机程序实现. 为解决某问题的算法同为该问题编写的程序含义是相同的. 算法的可行性是指指令不能有二义性. 以上几个都是错误的正确答案：12. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( )排序法。. 插入. 选择. 希尔. 二路归并正确答案：13. 下列排序算法中，（ ）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。. 堆排序. 冒泡排序. 快速排序. 插入排序正确答案：14. 在一棵二叉树上第5层的结点数最多是（ ）. 8. 16. 32. 15正确答案：15. 数组0.4,-1.-3,5.7中含有元素的个数（ ）。. 55. 45. 36. 16正确答案：16. 已知串S=,其Nxt数组值为（ ）。. 0123. 1123. 1231. 1211正确答案：17. 下面给出的四种排序方法中，排序过程中的比较次数与排序方法无关的是。( ). 选择排序法. 插入排序法. 快速排序法. 堆积排序法正确答案：18. 图中有关路径的定义是（ ）. 由顶点和相邻顶点序偶构成的边所形成的序列. 由不同顶点所形成的序列. 由不同边所形成的序列. 上述定义都不是正确答案：19. n个结点的线索二叉树上含有的线索数为（ ）. 2n. nl. nl. n正确答案：20. 一个栈的输入序列为123n，若输出序列的第一个元素是n，输出第i（1=i=n）个元素是（ ）。. 不确定. n-i+1. i. n-i正确答案：21. 以下数据结构中，（ ）是非线性数据结构. 树. 字符串. 队. 栈正确答案：22. 设给定权值总数有n 个，其哈夫曼树的结点总数为( ). 不确定. 2n. 2n+1. 2n-1正确答案：23. 对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（ ）. (2,5,12,16)26(60,32,72). (5,16,2,12)28(60,32,72). (2,16,12,5)28(60,32,72). (5,16,2,12)28(32,60,72)正确答案：24. 一棵二叉树的前序遍历序列为FG，它的中序遍历序列可能是（ ）. FG. FG. FG. FG正确答案：25. 设有一个10阶的对称矩阵，采用压缩存储方式，以行序为主存储，11为第一元素，其存储地址为1，每个元素占一个地址空间，则85的地址为（ ）。. 13. 33. 18. 40正确答案： 福师数据结构概论在线作业一二、判断题（共 20 道试题，共 40 分。）1. 队列和栈都是运算受限的线性表，只允许在表的两端进行运算。. 错误. 正确正确答案：2. 内排序要求数据一定要以顺序方式存储。. 错误. 正确正确答案：3. 若一个广义表的表头为空表，则此广义表亦为空表（ ）. 错误. 正确正确答案：4. 直接选择排序算法在最好情况下的时间复杂度为O（N）（ ）. 错误. 正确正确答案：5. 栈与队列是一种特殊操作的线性表（ ）. 错误. 正确正确答案：6. 链表中的头结点仅起到标识的作用（ ）. 错误. 正确正确答案：7. 当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省。. 错误. 正确正确答案：8. 栈是实现过程和函数等子程序所必需的结构（ ）. 错误. 正确正确答案：9. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表（ ）. 错误. 正确正确答案：10. 二叉树是度为2的有序树（ ）. 错误. 正确正确答案：11. 完全二叉树一定存在度为1的结点（ ）. 错误. 正确正确答案：12. 线性表的特点是每个元素都有一个前驱和一个后继（ ）. 错误. 正确正确答案：13. 采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。. 错误. 正确正确答案：14. 一棵一般树的结点的前序遍历和后序遍历分别与它相应二叉树的结点前序遍历和后序遍历是一致的。. 错误. 正确正确答案：15. 栈是实现过程和函数等子程序所必需的结构。. 错误. 正确正确答案：16. 用树的前序遍历和中序遍历可以导出树的后序遍历（ ）. 错误. 正确正确答案：17. 数据元素是数据的最小单位。. 错误. 正确正确答案：18. 算法的优劣与算法描述语言无关，但与所用计算机有关。. 错误. 正确正确答案：19. 算法的优劣与算法描述语言无关，但与所用计算机有关（ ）. 错误. 正确正确答案：20. 队列和栈都是运算受限的线性表，只允许在表的两端进行运算（ ）。. 错误. 正确正确答案： 福师数据结构概论在线作业一三、多选题（共 5 道试题，共 10 分。）1. 某堆栈的输入序列为, ， ，,下面的四个序列中，可能是它的输出序列的是（ ）. ，. , ，. , ，, . , ，正确答案：2. 有关二叉树下列说法不正确的是（ ）. 二叉树的度为2. 一棵二叉树的度可以小于2. 二叉树中至少有一个结点的度为2. 二叉树中任何一个结点的度都为2正确答案：3. 下面说法正确的是( )。. 广义表的表头总是一个广义表. 广义表的表尾总是一个广义表. 广义表难以用顺序存储结构.