春季福师数据结构概论在线作业一.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 . n－l . n＋l . n 正确答案： 20. 一个栈的输入序列为123…n，若输出序列的第一个元素是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. 队列和栈都是运算受限的线性表