2014年计算机学科专业基础综合试题参考答案一、单项选择题1.C2.9.D10.17.A18.25.D26.33.C34.1.解析：内层循环条件j<=n与外层循环的变量无关，每次循环j自增1,每次内层循环都执行n次。外层循环条件为k<=n,增量定义为k*=2,可知循环次数为2k<=n,即k<=log2n。所以内层循环的时间复杂度是O(n),外层循环的时间复杂度是O(log2n)。对千嵌套循环，根据乘法规则可知，该段程序的时间复杂度T(n)=T1(n)T2(n)=O(n)O(log2n)=O(nlog2n),选C。2.解析：将中缀表达式转换为后缀表达式的算法思想如下：从左向右开始扫描中缀表达式；遇到数字时，加入后缀表达式；遇到运算符时：a.若为＇（＇，入栈；b.若为＇）＇，则依次把栈中的运算符加入后缀表达式中，直到出现＇（＇，从栈中删除＇（＇；C.若为除括号外的其他运算符，当其优先级高于除＇（＇以外的栈顶运算符时，直接入栈；否则从栈顶开始，依次弹出比当前处理的运算符优先级高和优先级相等的运算符，直到一个比它优先级低的或者遇到了一个左括号为止。当扫描的中缀表达式结束时，栈中的所有运算符依次出栈加入后缀表达式。3.11.19.27.35.4.12.20.28.36.5.13.21.29.37.6.14.22.30.38.7.15.23.31.39.DAACBDABAACCDBBDDCCCACCADBBCAB8.16.24.32.40.DDBDD待处理序列栈后缀表达式当前扫描元素动作alb+(c*d-e*f)/gaa加入后缀表达式lb+(c*d-e*t)/ga/／入栈b+(c*d-e*f)/g/abb加入后缀表达式+(c*d-e*f)/gIab+＋优先级低千栈顶的/,弹出／+(c*d-e*f)/gab/+＋入栈(c*d-e*f)/g+ab/(（入栈c*d-e*f)/g+(ab/Cc加入后缀表达式*d-e*f)/g+(able*栈顶为（，＊入栈d-e*t)/g+(*abledd加入后缀表达式-e*f)/g+(*ab/cd－优先级低于栈顶的＊，弹出＊-e*f)/g+(ab/cd*栈顶为（，－入栈（续表）待处理序列栈后缀表达式当前扫描元素动作e*t)/g+(-ab/cd*ee加入后缀表达式*f)/g＋（－ab/cd*e＊＊优先级高于栈顶的－，＊入栈f)/g+(-*ab/cd*eff加入后缀表达式)/g+(-*ab/cd*ef）把栈中（之前的符号加入表达式/1!＋ab/cd*ef"-II优先级高于栈顶的+,I入栈j1;＋／ab/cd*ef*-gg加入后缀表达式十／ab/cd*ef*-g扫描完毕，运算符依次退栈加入表达式ab/cd*ef*-g/+完成由此可知，当扫描到f的时候，栈中的元素依次是＋（－＊，选B。在此，再给出中缀表达式转换为前缀或后缀表达式的手工做法，以上面给出的中缀表达式为例：第一步：按照运算符的优先级对所有的运算单位加括号。式子变成((alb)+(((c*d)-(e*f))/g))。第二步：转换为前缀或后缀表达式。前缀：把运算符号移动到对应的括号前面，则变成+(/(ab)/(-(*(cd)*(ef))g))。把括号去掉：+/ab/-*cd*efg前缀式子出现。后缀：把运算符号移动到对应的括号后面，则变成((ab)/(((cd)*(ef)*)-g)/)+。把括号去掉：ab/cd*ef*-g/+后缀式子出现。当题目要求直接求前缀或后缀表达式时，这种方法会比上一种快捷得多。3.解析：endl指向队头元素，那么可知出队的操作是先从A[endl]读数，然后endl再加1。end.2指向队尾元素的后一个位置，那么可知入队操作是先存数到A[end.2],然后end.2再加1。若把A[O]储存第一个元素，当队列初始时，入队操作是先把数据放到A[O],然后end.2自增，即可知end.2初值为0;endl指向的是队头元素，队头元素的在数组A中的下标为o,所以得知endl初值也为o,可知队空条件为endl=end.2。然后考虑队列满时，因为队列最多能容纳M-1个元素，假设队列存储在下标为0到下标为M-2的M-1个区域队头为A[O];队尾为A[M-2],此时队列满，考虑在这种情况下endl和end.2的状态，endl指向队头元素，可知endl=O,end.2指向队尾元素的后一个位置，可知end.2=M-2+1=M-1,所以可知队满的条件为endl=(end.2+1)modM,选A。注意：考虑这类具体问题时，用一些特殊情况判断往往比直接思考问题能更快地得到答案，并可以画出简单的草图以方便解题。4.解析：线索二叉树的线索实际上指向的是相应遍历序列特定结点的前驱结点和后继结点，所以先写出二叉树的中序遍历序列debxac,中序遍历中在x左边和右边的字符，就是它在中序线索化的左、右线索，即b、a,选D。5.解析：将森林转化为二叉树即相当于用孩子兄弟表示法表示森林。在变化过程中，原森林某结点的第一个孩子结点作为它的左子树...
