第 1 次作业一、单项选择题（本大题共 60 分，共 20 小题，每小题 3 分）1. 说明单链表是线性表的链式存储A. 顺序存取B. 链式存取C. 随机存取D. 散列存取2. 堆排序的辅助空间为（ ）。A. O(logn) B. O(n)C. O(nlogn) D. O(1)3. 将线性表的数据元素进行扩充，允许是带结构的线性表是( )。A. 串 3320. 对 n 个节点，e 条边的图，按克鲁斯卡尔算法建最小生成树的时间复杂度为（ ）。A. O(nloge)B. O(eloge)C. O(nlogn)D. O(n2)二、判断题（本大题共 40 分，共 20 小题，每小题 2 分）1. 二叉树中除叶结点外, 任一结点 X，其左子树根结点的值小于该结点（X）的值；其右子树根结点的值≥该结点（X）的值,则此二叉树一定是二叉排序树。2. 对无序表用折半查找比顺序查找快。3. 二叉树中每个结点的两棵子树是有序的。4. 查找表由同一类型的数据元素构成的集合。5. 考虑到交通网的有向性，直接讨论的是带权有向图的最短路径问题，但解决问题的算法也适用于无向图。6. 排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。7. n 个顶点的连通图至少 n-1 条边。8. Dijkstra 最短路径算法从源点到其余各顶点的最短路径的路径长度按递增次序依次产生。9. 树的存储有多种方式，既可以采用顺序存储结构，也可以采用链式存储结构。10. 数组是同类型值的集合。11. 邻接多重表每一条边用一个结点表示，6 个域组成。12. 双亲法表示树结构，若求某结点的孩子结点时，则需要查询整个数组。13. 哈希函数的选取平方取中法最好。14. 克鲁斯卡尔算法适应范围为稀疏图。15. 稀疏矩阵的压缩存储可以用一个三元组表来表示稀疏矩阵中的非 0 元素。 16. 在有 n 个顶点的有向图中，若要使任意两点间可以互相到达，则至少需要n 条弧。17. 已知单链表中某一结点由 p 指向，求此后继结点存储地址的操作为 p=p->next。18. 在 AOE 网中，从源点到汇点路径上各活动时间总和最短的路径称为关键路径。19. 在广义表的存储结构中，每个结点均包含有 3 个域。20. 用顺序方法存储一般的二叉树,若在树中需要经常插入和删除结点时，有大量的移动结点。答案：一、单项选择题（60 分，共 20 题，每小题 3 分）1. A 2. D 3. C 4. C 5. D 6. D 7. D 8. C 9. D 10. C 11. C 12. C 13. B 14. B 15. B 16. B 17. C 18. A 19. B 20. B 二、判断题（40 分，共 20 题，每小题 2 分）1. × 2. × 3. √ 4. √ 5. √ 6. × 7. √ 8. √ 9. √ 10. × 11. √ 12. √ 13. × 14. √ 15. √ 16. √ 17. √ 18. × 19. √ 20. √ B. 树 C. 广义表D. 栈4. 一棵树中，（ ）没有前驱结点。A. 分支结点B. 叶结点C. 树根结点D. 空结点5. 设给定权值总数有 n 个，其赫夫曼树的结点总数为( )。 A. 不确定 B. 2n C. 2n+1 D. 2n-16. 已知一个图如图所示，若从顶点 a 出发按深度搜索法进行遍历，则可得到顶点序列为（）。A. abecdfB. acfebdC. aebcfdD. aedfcb7. 适用于折半查找的表的存储方式及元素排列要求为( )。A. 链接方式存储，元素无序B. 链接方式存储，元素有序C. 顺序方式存储，元素无序 D. 顺序方式存储，元素有序8. 稀疏矩阵一般的压缩存储方法有两种，即( )。A. 二维数组和三维数组 B. 三元组和散列 C. 三元组和十字链表 D. 散列和十字链表9. 直接插入排序在最坏情况下的时间复杂度为（ ）。A. O(logn) B. O(n) C. O(n*logn) D. O(n2)10. 由 3 个结点所构成的二叉树有（ ）种形态。A. 3B. 4C. 5D. 611. 对数据元素序列（49，72，68，13，38，50，97，27）进行排序，如果采用起泡排序方法，则第二趟排序结果是( ）。A. 49，68，13，38，50，72，27，97B. 13，38，49，50，27，68，72，97C. 49，13，38，50，68，27，72，97 D. 13，38，49，27，50，68，72，9712. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为 A,并已知 A 的左孩子的平衡因子为 0 右孩子的平衡因子为 1，则应作( ) 型调整以使其平衡。A. LL B. LR C. RLD. RR13. 基数排序需要以下数据结构的辅助（ ）。A. 栈 B. 队列 C. 树D. 森林 14. 已知一个图如图所示，若从顶点 a 出发按深度搜索法进行遍历，按广度搜索法进行遍历，则可得到顶点序列为（ ）。A. abcedf　B. abcefdC. aebcfdD. acfdeb15. 简单选择排序进行移动操作的时间复杂度是（ ）。A. O(logn) B. O(n) C. O(n*logn) D. O(n2)16. 对于一个具有 n 个结点的单链表，在已知的结点*p 后插入一个新结点的时间复杂度为（ ）。A. O(0) B. O(1) C. O(n) D. O(n2)17. 分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ）。 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)18. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A. 顺序表B. 双链表C. 带头结点的双循环链表D. 单循环链表19. 有一个 100*90 的稀疏矩阵，非 0 元素有 10 个，设每个整型数占 2 字节，则用三元组表示该矩阵时，所需的字节数是（ ）。A. 60 B. 66C. 18000 D.