1、 第 1次作业 一、单项选择题（本大题共 60分，共 20 小题，每小题 3 分） 1. 将线性表的数据元素进行扩充，允许是带结构的线性表是 ( )。 A. 串 B. 树 C. 广义表 D. 栈 2. 一棵树中，（ ）没有前驱结点。 A. 分支结点 B. 叶结点 C. 树根结点 D. 空结点 3. 孩子兄弟表示法中，若要访问结点 x的第 i个孩子，则要先从 firstchild域找到第 1个孩子结点，然后沿着孩子结点的 nextsibling域连续走（ ）步，便可找到 x的第 i个 孩子。 A. 1 B. 2 C. i-1 D. i 4. 建堆是将所有元素按照初始顺序填充到一个（ ）中。 A.
2、 二叉树 B. 平衡二叉树 C. 红黑树 D. 完全二叉树 5. 若 n个顶点的无向图采用邻接矩阵存储方法，该邻接矩阵为一个什么矩阵？（） A. 对称矩阵 B. 一般矩阵 C. 稀疏矩阵 D. 对角矩阵 6. 由 3个结点所构成的二叉树有（ ）种形态。 A. 3 B. 4 C. 5 D. 6 7. 排序算法的作用是（ ）。 A. 让元素以递增的顺序排列 B. 让元素以递减的顺序排列 C. 让无序的数据组合变成有序的数据组合 D. 以上都不对 8. 下面关于折半查找的叙述正确的是 ( ) 。 A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 B. 表必须有序且表中数据必须是整型，实型或字
3、符型 C. 表必须有序，而且只能从小到大排列 D. 表必须有序，且表只能以顺序方式存储 9. 图中有关路径的定义是（ ）。 A. 由顶点和相邻顶点序偶构成的边所形成的序列 B. 由不同顶点所形成的序列 C. 由不同边所形成的序列 D. 上述定义都不是 10. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的（）。 A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 11. 设有 50行 60列的二维数组 A5060，其元素长度为 4字节，按行优先顺序存储，基地址为 200，则元素 A1825的存储地址为（ ）。 A. 3700 B. 4376 C. 3900 D. 4620 12
4、. 迪杰斯特拉 (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
5、） 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-1 B. n C. n+1 D. n+2 18. 设一个广义表中结点的个数为 n，则求广义表深度算法的时间复杂度为（ ）。 A. O(1) B. O(n) C. O(n2) D. O(l
6、og2n) 19. 设要将序列（ q,h,c,y,p,a,m,s,r,d,f,x）中的关键码按字母升序重新排序，第一次交换位置的是（ ）。 A. a 和 x B. p 和 f C. p 和 d D. y和 r 20. 对于长度为 n的顺序存储的线性表，访问结点和插入、删除结点的平均时间复杂度为（ ）。 A. O(0) B. O(1) C. O(n) D. O(n2) 二、判断题（本大题共 40 分，共 20 小题，每小题 2 分） 1. 任一查找树 (二叉分类树 )的平均查找时间都小于用顺序查找法查找同样结点的线性表的平均查找时间。 2. 对无序表用折半查找比顺序查找快。 3. 对于无向图来说
7、，若深度优先遍历过程中遇到回边（即指向已访问过的顶 点的边），则必定存在环。 4. 对一棵二叉排序树按前序方法遍历得出的结点序列是从小到大的序列。 5. 线性结构中，每一个结点都至少有一个直接前驱和一个直接后继。 6. 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。 7. n个顶点的连通图至少 n-1条边。 8. Dijkstra最短路径算法从源点到其余各顶点的最短路径的路径长度按递增次序依次产生。 9. 二叉排序树删除一个结点后，仍是二叉排序树。 10. 二叉树中每个结点的两棵子树的高度差等于 1。 11. 树中的每个结点有不唯一的一个双亲结点 。 12. 克鲁斯卡尔算法适应范围为稀疏图。 13. 在稀疏矩阵的顺序存储中，利用一个数组来存储非零元素，该数组的长度
