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

福建省2011年专升本数据结构复习资料，仅供内部交流。若有错误敬请指正13774551651邮箱[e-mail]吴国祥整理课程同步免费辅导答疑网址hi.baidu.com/lzxiangz1习题答案1.11.C,A2.B,D3.C4.C,A5.C,B6-10CDCBC11-13DA1.21.线性结构、树形结构、图形结构，非线性结构2.没有、1、没有、13.前驱、1、后续、任意多个4.任意多个5.一对一、一对多、多对多6.有穷性、确定性、可行性、输入、输出7.时间复杂度：.O(n2)8.时间复杂度：.O(n2)9.时间复杂度：.O(n3)10.时间复杂度：.O(n12)11.时间复杂度：.O(log2n)数据是信息的载体，是描述客观事物的数、字符、以及所有能输入到计算机中，被计算机程序识别和处理的符号的集合。数据元素是数据的基本单位。数据对象是具有相同性质的数据元素的集合。数据结构指某一数据对象及该对象中所有数据成员之间的关系。数据的逻辑结构从逻辑关系上描述数据，与数据的存储无关；数据的逻辑结构是指反映数据元素之间逻辑关系的数据结构05习题答案2.11.B2.A,C3.B4.D5.C6.A7.A8.B9.C10.D11.C12.B13.A14.D15.B16.A2.21.线性表2.前驱结点、后继结点3.s,p4.q-next,q5.p-next,s6.O(1),O(n)福建省2011年专升本数据结构复习资料，仅供内部交流。若有错误敬请指正13774551651邮箱[e-mail]吴国祥整理课程同步免费辅导答疑网址hi.baidu.com/lzxiangz2习题答案3.11.C2.C3.A4.B5.D6.BA7.C8.B9.C10.C11.A12.A13.C14.B15.C16C17D3.21.线性、任何、栈顶、队尾、队首2.n-i+13.n-i4.先移动栈顶指针，后存入元素5.先取出元素，后移动栈顶指针6.前一个位置7.先移动队首元素，后取出元素8.n-19.不可能的10.可能的习题答案4.11.A2.B3.C4.D5.C6.B7.D8.A9.C10.A11.D2.A13.B14.B15.B16.D17.C18.C19.A20.(A,D)21.C22.B23.C24.A25.A26-30DCBA4.21.⑴k1⑵k2,k5,k7,k4⑶2⑷3⑸4⑹k5,k6⑺k12.树的结点个数至少为1(不同教材规定不同)，而二叉树的结点个数可以为0；树中结点的最大度数没有限制，而二叉树结点的最大度数为2；树的结点无左、右之分，而二叉树的结点有左、右之分；3.树可采用孩子-兄弟链表（二叉链表）做存储结构，目的并利用二叉树的已有算法解决树的有关问题。4.如图4.9所示5.2k-1、2k-1、2k-2+16.n2+17.2i-18.只有一个结点的树；空的二叉树9.5；如图4.10所示10.dgbaechif、abdgcefhi、gdbeihfca、4.31.5种,图4.11a图4.10树形5种aaacacccccbbbbbbeaEfjcdlghb图4.9福建省2011年专升本数据结构复习资料，仅供内部交流。若有错误敬请指正13774551651邮箱[e-mail]吴国祥整理课程同步免费辅导答疑网址hi.baidu.com/lzxiangz3EBEFAECDKGHIJ图4.12a11dhjbkc图4.14对应的森林iefabcedig图4.15一棵树的孩子兄弟表示2.二叉树如图4.12所示。3.该二叉树转换后的的森林如图6.14所示。4.图4.8的树转化为一棵二叉树如下，图4.15：5.画出构造Huffman树如图4.16所示，计算其带权路径长度为。习题答案5.11.C2.B3.B4.C5.A6.A7.C8.D9.AC10.DB11.CB12.A13.D14.B15.B16-20ABADC623725191813121096745图4.16Huffman树图4.11树形5种福建省2011年专升本数据结构复习资料，仅供内部交流。若有错误敬请指正13774551651邮箱[e-mail]吴国祥整理课程同步免费辅导答疑网址hi.baidu.com/lzxiangz421-25DCDAC26-30ABBBD31-34ACAA5.21.n-12.1;03.14.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．一个结点可能有若干个前驱，也可能有若干个后继12．213．唯一5.31.2.(1)．（2）156243badce1115131412f612495106154372福建省2011年专升本数据结构复习资料，仅供内部交流。若有错误敬请指正13774551651邮箱[e-mail]吴国祥整理课程同步免费辅导答疑网址hi.baidu.com/lzxiangz53．1523641526341562345612345162345126345123644．n个顶点的连通网络的生成树有n个顶点、n-1条边。在无向图中,统计第i行(列)1的个数可得顶点i的度。在有向图中,统计第i行1的个数可得顶点i的出度，统计第j列1的个数可得顶点j的入度。习题答案6.11．B2．C3．C4．D5．B6．C7．D8．B9．C10．D11．C12．B13．C14.A15.D16.D6.21.O（n）、O(log2n)2.2、4、33.顺序存储结构、有序的4.1、2、4、8、5、3．7（依题意，构造一棵有序二叉树，共12个结点，第一层1个结点，第二层2个结点，第三层4个结点，第四层5个结点，则：ASL=（1*1+2*2+3*4+4*5）/12=37/12）5.存取元素时发生冲突的可能性就越大、存取元素时发生冲突的可能性就越小6．素数7．结点个数n、生成过程7.11.D2.C3.A4.B5.C6.A7.C8.D9.D10.C11.D12.C13A14D15B16CW=3W=7W=9W=6W=543233abdfce福建省2011年专升本数据结构复习资料，仅供内部交流。若有错误敬请指正13774551651邮箱[e-mail]吴国祥整理课程同步免费辅导答疑网址hi.baidu.com/lzxiangz6