2015年计算机学科专业基础综合试题参考答案一、单项选择题1.A2.9.C10.17.B18.25.D26.33.D34.1.解析：递归调用函数时，在系统栈里保存的函数信息需满足先进后出的特点，依次调用了main(),S(l),S(O),故栈底到栈顶的信息依次是main(),S(1),S(O)。2.解析：根据二叉树前序遍历和中序遍历的递归算法中递归工作栈的状态变化得出：前序序列和中序序列的关系相当于以前序序列为入栈次序，以中序序列为出栈次序。因为前序序列和中序序列可以唯一地确定一棵二叉树，所以题意相当千“以序列a,b,c,d为入栈次序，则出栈序列的个数为多少“，对于n个不同元素进栈，出栈序列的个数为—-c;n=14。n+l3.11.19.27.35.4.12.20.28.36.CBCCCACBCACDDCCDBBBADABABDACABBCDBA5.13.21.29.37.6.14.22.30.38.7.15.23.31.39.8.16.24.32.40.3.解析：在哈夫曼树中，左右孩子权值之和为父结点权值。仅以分析选项A为例：若两个10分别属千两棵不同的子树，根的权值不等于其孩子的权值和，不符；若两个10属于同棵子树，其权值不等千其两个孩子（叶结点）的权值和，不符。B、C选项的排除方法一样。4.解析：只有两个结点的平衡二叉树的根结点的度为1,A错误。中序遍历后可以得到一个降序序列，树中最大元素一定无左子树（可能有右子树），因此不一定是叶结点，B错误。最后插入的结点可能会导致平衡调整，而不一定是叶结点，C错误。5.解析：画出该有向图图形如下。采用图的深度优先遍历，共5种可能：,,,,,选D。6.解析：从V4开始，Kruskal算法选中的第一条边一定是权值最小的(V1,V4),B错误。由于V1和V4已经可达，第二条边含有V1和V4的权值为8的一定符合Prim算法，排除A、D。7.解析：画出查找路径图，因为折半查找的判定树是一棵二叉排序树，看其是否满足二叉排序树的要求。＾500180450450显然，选项A的查找路径不满足。8.解析：由题中“失配s[i]:/;玵］时，i=j=S",可知题中的主串和模式串的位序都是从0开始的（要注意灵活应变）。按照next数组生成算法，对于t有编号t。2345aanext一11-b-oa-0b一1c-2依据KMP算法”当失配时，i不变，j回退到next[j]的位置并重新比较”，当失配s[i]f;t[j]时，i=j=5,由上表不难得出next[j]=next[5]=2(位序从0开始）。从而最后结果应为i=5(i保持不变），j=2。9.解析：基数排序的元素移动次数与关键字的初始排列次序无关，而其他三种排序都是与关键字的初始排列明显相关的。10.解析：删除8后，将12移动到堆顶，第一次是15和10比较，第二次是10和12比较并交换，第三次还需比较12和16,故比较次数为3次。,/\�I\/\j�;i�气芒＼、巴，矗全、(10)夕－／气、一--�---(15)i'12£-\.--<(21-,'.34iv:16),__j\�i--、(12J--、／、��---!15)(10;--\.,.1-·(21,，＼)(34)(16)、、j,__令11.解析：希尔排序的思想是：先将待排元素序列分割成若干子序列（由相隔某个“增量”的元素组成），分别进行直接插入排序，然后依次缩减增量再进行排序，待整个序列中的元素基本有序（增量足够小）时，再对全体元素进行一次直接插入排序。12.解析：硬件能直接执行的只能是机器语言（二进制编码），汇编语言是为了增强机器语言的可诙性和记忆性的语言，经过汇编后才能被执行。13.解析：补码整数表示时，负数的符号位为I,数值位按位取反，末位加I,因此剩下的2个"I"在最低位时，表示的是最小整数，为10000011,转换成真值为-125。14.解析：对阶是较小的阶码对齐至较大的阶码，I正确。右规和尾数舍入过程，阶码加1而可能上溢，II正确，同理III也正确。尾数溢出时可能仅产生误差，结果不一定溢出，IV正确。15..解析：直接映射的地址结构如下：I主存字块标记ICache字块标记1字块内地址按字节编址，块大小为4x32bit=16B=24B,则“字块内地址”占4位；“能存放4K字数据的Cache"即Cache的存储容量为4K字（注意单位），则Cache共有IK=210个Cache行，Cache字块标记占10位；主存字块标记占32-10-4=18位。Cache的总容量包括：存储容量和标记阵列容量（有效位、标记位、一致性维护位和替换算法控制位）。标记阵列中的有效位和标记位是一定有的，而一致性维护位（脏位）...
