2013年计算机学科专业基础综合试题参考答案一、单项选择题D2.C10.D18.C26.B34.1.解析：两个升序链表合并，两两比较表中元素，每比较一次确定一个元素的链接位置（取较小元素，头插法）。当一个链表比较结束后，将另一个链表的剩余元素插入即可。最坏的情况是两个链表中的元素依次进行比较，直到两个链表都到表尾，即每个元素都经过比较，时间复杂度为O(m+n)=O(max(m,n))。2.解析：显然，3之后的4,5,…，n都是p3可取的数（一直进栈直到该数入栈后马上出栈）。接下来分析1和2:Pt只能是3之前入栈的数（可能是1或2),当P1=1时，p3可取2;当P1=2时，p3可取1,故p3可能取除3之外的所有数，个数为n-1。3.解析：利用7个关键字构建平衡二叉树T,平衡因子为0的分支结点个数为3,构建的平衡二叉树如下图所示。构造及调整的过程如下：1.9.17.25.33.3.11.19.27.35.DCBCD4.12.20.28.36.DAABACCABBCADBBAABDABCBBBCACAA5.13.21.29.37.6.14.22.30.38.7.15.23.31.39.8.16.24.32.40.r-----------,。飞：［｀L___________』,-----------------了,RR,4.解析：将哈夫曼树的思想推广到三叉树的情形。为了构成严格的三叉树，需添加权为0的虚叶结点，对于严格的三叉树(n。-1)%(3-1)=u=1-to,需要添加m-u-1=3-1-1个叶结点，说明7个叶结点刚好可以构成一个严格的三叉树。按照哈夫曼树的原则，权为0的叶结点应离树根最远，构造最小带权生成树的过程如下：。｀妙0©05)©0乙7最小的带权路径长度为(2+3)x3+(4+5)x2+(6+7)x1=46。5.解析：根据后序线索二叉树的定义，X结点为叶子结点且有左兄弟，那么这个结点为右孩子结点，利用后序遍历的方式可知X结点的后序后继是其父结点，即其右线索指向的是父结点。为了更加形象，在解题的过程中可以画出如下草图。三6.解析：在一棵二叉排序树中删除一个结点后再将此结点插入到二叉排序树中，如果删除的结点是叶子结点，那么在插入结点后，后来的二叉排序树与删除结点之前相同。如果删除的结点不是叶子结点，那么再插入这个结点后，后来的二叉树会发生变化，不完全相同。7.解析：邻接矩阵A为非对称矩阵，说明图是有向图，度为入度加出度之和。各顶点的度是矩阵中此结点对应的行（对应出度）和列（对应入度）的非零元素之和。8.解析：此题为送分题。只要掌握DFS和BFS的遍历过程，便能轻易解决。逐个代入，手工模拟，选项D是深度优先遍历，而不是广度优先遍历。f){g9.解析：找出AOE网的全部关键路径为(b,d,c,g)、(b,d,e,h)和(b,f,h)。根据定义，只有关键路径上的活动时间同时减少时，才能缩短工期，即正确选项中的两条路径必须涵盖在所有关键路径之中。利用关键路径算法可求出图中的关键路径共有三条：(b,d,c,g)、(b,d,e,h)和(b,f,h)。由此可知，选项A和B中并不能包含(b,f,h)这条路径，选项C中，并不能包含(b,d,c,g)和(b,d,e,h)这两条路径，只有C包含了所有的关键路径，因此只有加快f和d的进度才能缩短工期（建淘宝店铺：光速考研工作室议考生在图中检验）。10.解析：对于5阶B树，根结点只有达到5个关键字时才能产生分裂，成为高度为2的B树，因此高度为2的5阶B树所含关键字的个数最少是5。11.解析：基数排序的第l趟排序是按照个位数字的大小来排序的，第2趟排序是按照十位数字的大小进行排序的，排序的过程如下图所示。e[O]e[I]e[2]e[3]e[4]e[5]e[6)e[7]e[8]e[9]沪120卤'卤+'由'卤分配：收集：e[O]e[I]e[2]e[3]e[4]e[5]e[6)e[7]e[8]e[9]�'��'�+芦盓盄分配：收集：12.解析：基准程序的CPI=2x0.5+3x0.2+4xO.l+Sx0.2=3。计算机的主频为1.2GHz,即1200MHz,故该机器的MIPS=1200/3=400。13.解析：IEEE754单精度浮点数格式为C640OOOOH,二进制格式为11000110010000000000000000000000,转换为标准的格式为s阶码10001100尾数10000000000000000000000数符=I表示负数；阶码值为10001100-01111111=00001101=13;尾数值为1.5(注意其有隐含位，要加1)。因此，浮点数的值为-l,5xi314.解析：x*2,将x算术左移一位为11101000;y/2,将y算术右移一位为11011000,均无溢出或丢失精度。补码相加为11101000+11011000=11000000,亦无溢出。15.解析：设校验位的位数为k,数据位的位数为n,海明码能纠正一位错应满足...
