第 1 次作业一、单项选择题（本大题共 60 分，共 20 小题，每小题 3 分）1. 将线性表的数据元素进行扩充，允许是带结构的线性表是( )。A. 串B. 树 C. 广义表D. 栈2. 一棵树中，（ ）没有前驱结点。A. 分支结点B. 叶结点C. 树根结点D. 空结点 C. O(n) D. O(n2)二、判断题（本大题共 40 分，共 20 小题，每小题 2 分）1. 任一查找树(二叉分类树)的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间。2. 对无序表用折半查找比顺序查找快。3. 对于无向图来说，若深度优先遍历过程中遇到回边（即指向已访问过的顶点的边），则必定存在环。4. 对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。5. 线性结构中，每一个结点都至少有一个直接前驱和一个直接后继。6. 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。7. n 个顶点的连通图至少 n-1 条边。8. Dijkstra 最短路径算法从源点到其余各顶点的最短路径的路径长度按递增次序依次产生。9. 二叉排序树删除一个结点后，仍是二叉排序树。10. 二叉树中每个结点的两棵子树的高度差等于 1。11. 树中的每个结点有不唯一的一个双亲结点。12. 克鲁斯卡尔算法适应范围为稀疏图。13. 在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度应等于对应三元组线性表的长度。14. 在有 n 个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要n 条弧。15. 图的遍历算法有深度优先搜索算法和广度优先搜索算法。16. 已知单链表中某一结点由 p 指向，求此后继结点存储地址的操作为 p=p->next。17. 在散列检索中，“比较”操作一般也是不可避免的。18. 在广义表的存储结构中，每个结点均包含有 3 个域。19. 求有向图 G=(V，E)中每一对顶点间的最短路径，用 Dijkstra 算法和弗罗伊德算法，时间复杂度都是 O(n3) 。20. 用顺序方法存储一般的二叉树,若在树中需要经常插入和删除结点时，有大量的移动结点。 答案：一、单项选择题（60 分，共 20 题，每小题 3 分）1. C 2. C 3. C 4. D 5. A 6. C 7. C 8. D 9. A 10. A 11. D 12. C 13. B 14. C 15. B 16. A 17. C 18. B 19. C 20. C 二、判断题（40 分，共 20 题，每小题 2 分）1. × 2. × 3. √ 4. × 5. × 6. × 7. √ 8. √ 9. √ 10. × 11. × 12. √ 13. √ 14.√ 15. √ 16. √ 17. √ 18. √ 19. √ 20. √ 3. 孩子兄弟表示法中，若要访问结点 x 的第 i 个孩子，则要先从 rstchild 域找到第 1 个孩子结点，然后沿着孩子结点的 nextsibling 域连续走（ ）步，便可找到 x 的第 i 个孩子。A. 1B. 2C. i-1D. i4. 建堆是将所有元素按照初始顺序填充到一个（ ）中。A. 二叉树 B. 平衡二叉树C. 红黑树D. 完全二叉树5. 若 n 个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵为一个什么矩阵？（）A. 对称矩阵 B. 一般矩阵C. 稀疏矩阵D. 对角矩阵6. 由 3 个结点所构成的二叉树有（ ）种形态。A. 3B. 4C. 5D. 67. 排序算法的作用是（ ）。A. 让元素以递增的顺序排列B. 让元素以递减的顺序排列 C. 让无序的数据组合变成有序的数据组合 D. 以上都不对8. 下面关于折半查找的叙述正确的是 ( ) 。 A. 表必须有序，表可以顺序方式存储，也可以链表方式存储B. 表必须有序且表中数据必须是整型，实型或字符型 C. 表必须有序，而且只能从小到大排列D. 表必须有序，且表只能以顺序方式存储9. 图中有关路径的定义是（ ）。A. 由顶点和相邻顶点序偶构成的边所形成的序列B. 由不同顶点所形成的序列C. 由不同边所形成的序列 D. 上述定义都不是10. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。A. 先序遍历　B. 中序遍历　C. 后序遍历D. 按层遍历11. 设有 50 行 60 列的二维数组 A[50][60]，其元素长度为 4 字节，按行优先顺序存储，基地址为 200，则元素 A[18][25]的存储地址为（ ）。A. 3700 B. 4376 C. 3900D. 4620 12. 迪杰斯特拉(Dijkstra)算法用于求解图上的单源点最短路径。本质上说，该算法是一种基于（ ）策略的算法。A. 分治B. 动态规划C. 贪心 D. 回溯13. 简单选择排序是一种（ ）。A. 稳定的排序算法 B. 不稳定的排序算法C. 无法确定其是否稳定D. 以上都不对14. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ）。 A. （100，80， 90， 60， 120，110，130）B. （100，120，110，130，80， 60， 90）C. （100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110)15. 任何一个带权的无向连通图的最小生成树（ ）。A. 只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在16. 弗罗伊德(Floyd)算法时间复杂度是（ ）。A. B. C. D. 17. 设 F 是一个森林，B 是由 F 转换得到的二叉树，F 中有 n 个非叶结点，则 B中右指针域为空的结点有（ ）个。A. n-1B. nC. n+1D. n+218. 设一个广义表中结点的个数为 n，则求广义表深度算法的时间复杂度为（ ）。A. O(1) B. O(n) C. O(n2) D. O(log2n)19. 设要将序列（q,h,c,y,p,a,m,s,r,d,f,x）中的关键码按字母升序重新排序，第一次交换位置的是（ ）。A. a 和 xB. p 和 fC. p 和 dD. y 和 r20. 对于长度为 n 的顺序存储的线性表，访问结点和插入、删除结点的平均时间复杂度为（ ）。A. O(0) B. O(1)