2012年全国硕士研究生入学统一考试计算机专业基础综合考试基础.DOC

2012年全国硕士研究生入学统一考试计算机专业基础综合考试 基础阶段测评试卷 /link?url=TN8HXvHeiPv9tdI9gLqL-P5msmEvwh_VIq16B7_b_Ti9-OOMgzWnQ7CSirxUN4aI9iqMiQCPJiddEV6oCSKs5fQ79TmZbXUNbOA6Ob_GJF_ 一、单项选择题：1-40小题，每小题2分，共80分。 下列每题给出的四个选项中，只有一个选项是最符 合题目要求的。 1、用S表示进栈操作，用X表示出栈操作，若元素的进栈顺序是1234，为了得到1342的出栈顺序，相应的操作序列应该是 A．SXSXSSXX B．SSSXXSXX C．SXSSXXSX D．SXSSXSXX 2、设有一个10×10的的对称矩阵A[10][10]，采取按下三角方式压缩存放于一个一维数组B[]中，则A[8][5]再数组B[]中的存储位置是 A．39 B．41 C．43 D．65 3、前序为A、B、C，后序为C、B、A的二叉树共有 A．1 B．2 C．3 D．4 4、一颗二叉树的前序遍历序列为ABDGHCEFI，中序遍历为GDHBAECIF，则这颗二叉树的后序遍历为 A．GHDBEIFCA B．ABCDEFIHG C．DACEHFBGI D．ADCEFGBHI 5、具有5层结点的平衡二叉树，设树的根结点在第一层，则深度最小的叶结点在第几层 A．2 B．5 C．3 D．4 6、有5个字符，根据其使用的频率设计对应的哈夫曼编码，下面哪个是不可能的编码 A．000，001，011，1 B．0000，0001，001，01，1 C．000，001，01，10，11 D．00，100，101，110，111 7、设森林中有三棵树，第一棵，第二棵跟第三棵树中的结点个数分别为m1，m2和m3，那么在由该森林转化成的二叉树中根结点的右子树上的结点数是 A．m1+m2 B．m2+m3 C．m1+m3 D．m1+m2+m3 8、Dijkstra算法是按什么方法求出图中某个顶点到其余各点的最短路径的 A．按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B．按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C．按长深度优先遍历求出图中某顶点到其余顶点的所有路径 D．按广度优先遍历求出图的某项点其余顶点的最短路径 9、设散列地址空间为0~m-1，key为表项的关键字，散列函数采用除留余数法，即Hash(key)=key%p。为了减少发生冲突的频率，一般取p为 A．m B．小于等于m的最大质数 C．大于m的最小质数 D．小于等于m 的最大合数 10、向具有n个结点的堆中插入一个新元素的时间复杂度为 A．O(1) B．O(n) C．O(log2n) D．O(nlog2n) 11、使用递归的快速排序时，为了保证排序过程的时间复杂度不超过O(nlog2n)，必须做到 A．每次序列的划分应该再线性时间内完成 B．每次归并的两个字序列长度接近 C．每次归并在线性时间内完成 D．以上全是 12、冯?诺依曼计算机中指令和数据均以二进制形式存放在存储器中，CPU区分它们的依据是 A．指令操作码的译码结果 B．指令和数据的寻址方式 C．指令周期的不同阶段 D．指令和数据所在的存储单元 13、能发现两位错误并纠正一位错误的编码是 A．CRC码 B．海明码 C．偶校验码 D．奇校验码 14、假定有4个整数用8位补码分别表示r1=FEH，r2=F2H，r3=90H，r4=F8H，若将运算结果存放在一个8位寄存器中，则下列运算会发生益处的是 A．r1 x r2 B．r2 x r3 C．r1 x r4 D．r2 x r4 15、某一SRAM芯片，其容量为1024*8位，除电源跟接地线外，改芯片引脚的最小数目为 A．21 B．22 C．23 D．24 16、采用页式内存管理某存储器，使用LRU页面替换算法，鉴定内存容量为4哥页面，而且开始时是空的，考虑下面的页面访问地址流（每次访问在一个单位时间内完成），1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7， 则页面的命中次数是 A．24 B．14 C．16 D．6 17、关于Cache的3种基本映像方式，下面叙述正确的是 A．Cache的地址映像有全