福建省计算机专升本数据结构习题答案.doc

福建省2011年专升本数据结构复习资料，仅供内部交流。若有错误敬请指正邮箱 571056735 吴国祥 整理 课程同步免费辅导答疑网址 /lzxiangz习题答案1.1 1. C , A 2. B,D 3. C 4. C, A 5. C,B 6-10 C D C B C 11-13 D A 1.2 1. 线性结构、树形结构、图形结构，非线性结构 2. 没有、1、没有、1 3. 前驱、1、后续、任意多个 4. 任意多个 5. 一对一、一对多、多对多 6. 有穷性、确定性、可行性、输入、输出 7. 时间复杂度：. O (n2) 8. 时间复杂度：. O (n2) 9. 时间复杂度：. O (n3)10. 时间复杂度：. O (n) 11. 时间复杂度：. O (log2n )数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数据元素是数据的基本单位。数据对象是具有相同性质的数据元素的集合。 数据结构 指某一数据对象及该对象中所有数据成员之间的关系。数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关；数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构 05习题答案 2.1 1. B 2. A, C 3. B 4. D 5. C 6. A 7. A 8. B 9. C 10. D 11.C 12.B 13.A 14.D 15.B 16. A 2.2 1. 线性表 2. 前驱结点、后继结点 3. s, p 4. q-next, q 5. p-next, s 6. O (1) , O (n)习题答案3.1 1. C 2. C 3. A 4. B 5.D 6. B A 7.C 8. B 9. C 10. C 11. A 12. A 13.C 14. B 15.C 16 C 17 D 3.2 1. 线性、任何、栈顶、队尾、队首 2. n-i+1 3. n-i 4.先移动栈顶指针，后存入元素 5. 先取出元素，后移动栈顶指针 6.前一个位置 7. 先移动队首元素，后取出元素 8. n-1 9. 不可能的 10. 可能的习题答案4.1 1. A 2. B 3. C 4. D 5. C 6. B 7. D 8. A 9. C 10. A11. D 2. A 13. B 14. B 15. B 16. D 17. C 18. C 19. A 20. (A,D) 21. C 22. B 23. C 24. A 25. A 26-30 D C B A 4.2 1. k1 k2,k5,k7,k4 2 3 4 k5,k6 k1 eaEfjcdlghb图4.92. 树的结点个数至少为1(不同教材规定不同)，而二叉树的结点个数可以为0；树中结点的最大度数没有限制，而二叉树结点的最大度数为2；树的结点无左、右之分，而二叉树的结点有左、右之分；3. 树可采用孩子-兄弟链表（二叉链表）做存储结构，目的并利用二叉树的已有算法解决树的有关问题。4. 如图4.9所示 5. 2 k-1 、 2 k-1 、 2 k-2+1 6. n2+1 7. 2 i-1 8. 只有一个结点的树；空的二叉树9. 5；如图4.10所示a图4.10 树形5种aaaacccccbbbbbb10. dgbaechif 、abdgcefhi 、gdbeihfca 、4.3 1. 5种, 图4.11EBEFAECDKGHIJ图4.12图4.11 树形5种2. 二叉树如图4.12所示。3. 该二叉树转换后的的森林如图6.14所示。a 11dhjbkc 图 4.14 对应的森林iefabcedig图 4.15 一棵树的孩子兄弟表示4. 图4.8的树转化为一棵二叉树如下，图4.15：623725191813121096745图4.16 Huffman树5. 画出构造Huffman树如图4.16所示，计算其带权路径长度为 。 习题答案 5.1 1. C2.B3.B4. C5. A6. A7.C8.D9. AC10.DB 11. CB12. A13. D 14. B15. B16-20 A B A D C 21-25 D C D A C 26-30 A B B B D 31-34 A C A A 5.2 1.n-1 2. 1;0 3. 1 4.v1,v2,v3,v6,v5, v4；v1,v2,v5,v4,v3, v65.求矩阵第i列非零元素之和 6. 将矩阵第i行全部置为零7.n8.99.对每个顶点查找其邻接点的过程；O（e）（e为图中的边数）；O（e）；遍历图的顺序不同；DFS采用栈存储访问过的结点，BFS采用队列存储访问过的结点。10邻接矩阵 邻接表11一个结点可能有若干个前驱，也可能有若干个后继12213唯一1562435.3 1.2.badce1115131412f (1)612495106154372（2） 3152364152634156234561234516234512634512364W=3W=7W=9W=6W=543233abdfce4n n 个顶点的连通网络的生成树有 n 个顶点、n-1 条边。n 在无向图中, 统计第 i 行 (列) 1 的个数可得顶点i 的度。n 在有向图中, 统计第 i 行 1 的个数可得顶点 i 的出度，统计第 j 列 1 的个数可得顶点 j 的入度。习题答案6.1 1B 2C 3C 4D 5B 6C 7D 8B 9C 10D 11C 12B 13C 14. A 15. D 16.D6.2 1.O（n）、O(log2n) 2. 2、4、3 3. 顺序存储结构、有序的 4. 1、2、4、8、5、37（依题意，构造一棵有序二叉树，共12个结点，第一层1个结点，第二层2个结点，第三层4个结点，第四层5个结点，则：ASL=（1*1+2*2+3*4+4*5）/12=37/12） 5. 存取元素时发