16春地大《数据结构(新)》在线作业二16春地大《数据结构(新)》在线作业二.doc

地大《数据结构(新)》在线作业二 一、单选题（共 25 道试题，共 100 分。） 1. 算法的时间复杂度是指（）。 . 执行算法程序所需要的时间 . 算法程序的长度 . 算法执行过程中所需要的基本运算次数 . 算法程序中的指令条数 正确答案： 2. 对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是（）。 . n . (n-1)(n-1) . n-1 . n*n 正确答案： 3. n个顶点的连通图至少有（）条边。 . n-1 . n . n+1 . 0 正确答案： 4. 按照二叉树的定义，具有3个结点的二叉树有（ ）种。 . 3 . 4 . 5 . 6 正确答案： 5. 邻接表是图的一种（）。 . 顺序存储结构 . 链式存储结构 . 索引存储结构 . 列存储结构 正确答案： 6. 若待排序对象序列在排序前已按其排序码递增顺序排序，则采用（ ）方法比较次数最少。 . 直接插入排序 . 快速排序 . 归并排序 . 直接选择排序 正确答案： 7. 算法分析的两个主要方面是（ ）。 . 空间复杂度和时间复杂度 . 正确性和简明性 . 可读性和文档性 . 数据复杂性和程序复杂性 正确答案： 8. 设有一个二元数组[m][n]，假设[0][0]存放位置在644(10)，[2][2]存放位置在676 (10)，每个元素占一个空间，则[4][5]在（）位置，(10)表明用10进数表示。 . 692(10) . 626(10) . 709(10) . 724(10) 正确答案： 9. 计算机的算法必须具备输入，输出和（）五个特性。 . 可行性，可移植性和可扩充性 . 可行性，确定性和有穷性 . 确定性，有穷性和稳定性 . 易读性，稳定性和安全性 正确答案： 10. 某二叉树结点的前序序列为、、、、、G、F，中序遍历为、、、、、F、G。 该二叉树结点的后序序列为 ()。 . ,,,,F,G, . ,,,F,,G, . ,G,F,,,, . ,G,,,,F, 正确答案： 11. 设在栈中，由顶向下已存放元素、、，在第4个元素入栈之前，栈中元素可以出栈， 试问入栈前后，不可能的出栈序列是()。 . . . . 正确答案： 12. 对下面四个序列用快速排序的方法进行排序，以序列的第一个元素为基础进行划分。 在第一趟划分过程中，元素移动次数最多的序列是 ()。 . 82，75，70，16，10，90，68，23 . 23，10，16，70，82，75，68，90 . 70，75，68，23，10，16，90，82 . 70，75，82，90，23，16，10，68 正确答案： 13. 队列操作的原则是（ ）。 . 先进先出 . 后进先出 . 只能进行插入 . 只能进行删除 正确答案： 14. 无向图的邻接矩阵是一个( )。 . 对称矩阵 . 零矩阵 . 上三角矩阵 . 对角矩阵 正确答案： 15. 链表不具有的特点是（）。 . 不必事先估计存储空间 . 可随机访问任一元素 . 插入删除不需要移动元素 . 所需空间与线性表长度成正比 正确答案： 16. 如果一个树中，结点有3个兄弟，而且为的双亲，则的度为（ ）。 . 1 . 3 . 4 . 5 正确答案： 17. 若给定的关键字集合为{20，15，14，18，21，36，40，10}，一趟快速排序结束时，键值的排列为()。 . 10，15，14，18，20，36，40，21 . 10，15，14，18，20，40，36，21 . 10，15，14，20，18，40，36，21 . 15，10，14，18，20，36，40，21 正确答案： 18. 若某线性表中最常用的操作是取第I个元素和找第I个元素的前趋元素，则采用()存储方式最节省时间。 . 顺序表 . 单链表 . 双链表 . 单循环链表 正确答案： 19. 二叉树上叶结点数等于（ ）。 . 分支结点数加1 . 单分支结点数加1 . 双分支结点数加1 . 双分支结点数减1 正确答案： 20. 对某二叉树进行前序遍历的结果为F，中序遍历的结果为F，则后序遍历的结果为（ ）。 . F . F . F . F 正确答案： 21. 对n个记录的文件进行堆排序，最坏情况下的执行时间为( )。 . O(log2n) . O(nlogn) . O(n) . O(n*n) 正确答案： 22. 每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（ ）排序. . 插入 . 交换 . 选择 . 归并 正确答案： 23. 设有50行60列的二维数组[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素[18][25]的