重庆大学917计算机专业基础综合考研真题试题2014年

计算机学科专业基础综合真题2014年(总分：137.00，做题时间：90分钟)一、{{B}}单项选择题{{/B}}(总题数：40，分数：80.00)1.下列程序段的时间复杂度是count=0;for(k=1; k＜=n; k*=2)for(j=1; j＜=n; j++)count++;∙ A.O(log2n)∙ B.O(n)∙ C.O(nlog2n)∙ D.O(n2)（分数：2.00）A.B.C. √D.解析：[解析] 题目中给出了一个2层的嵌套循环，里层循环的时间复杂度是O(n)，外层循环的时间复杂度是O(log2n)。

对于嵌套循环，其整体复杂度是两层循环的复杂度的乘积，因此总体的时间复杂度是D(nlog2n)。

2.假设栈初始为空，将中缀表达式a/b+(c*d-e*f)/g转换为等价的后缀表达式的过程中，当扫描到f时，栈中的元素依次是∙ A.+(*-∙ B.+(-*∙ C./+(*-*∙ D./+-*（分数：2.00）A.B. √C.D.解析：[解析] 后缀表达式为ab/cd*ef*-g/+。

根据中缀表达式a/b+(c*d-e*f)/g转换为等价的后缀表达式的过程，字母不需要入栈，只有扫描到符号时才需要入栈。

最先入栈的是“/”，当扫描完b时出栈。

接下来入栈的是“+”和“(”，然后扫描c，后面的“*”要入栈，再扫描d，然后“*”出栈。

接下来“-”入栈，扫描e，接下来的“*”入栈，接下来就扫描到f了。

此时没有出栈的有“+，(，-，*”。

3.循环队列存放在一维数组A[0..M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行人队和出队操作，队列中最多能容纳M-1个元素，初始时为空。

下列判断队空和队满的条件中，正确的是∙ A.队空：end1==end2；队满：end1==(end2+1)mod M∙ B.队空：end1==end2；队满：end2==(end1+1)mod(M-1)∙ C.队空：end2==(end1+1)mod M；队满：end1==(end2+1)mod M∙ D.队空：end1=(end2+1)mod M；队满：end2==(end1+1)mod(M-1)（分数：2.00）A. √B.C.D.解析：[解析] 对于循环链表来说，队列空的条件是队头指针和队尾指针指向同一个位置，即end1==end2；队列满的条件是队尾指针指向队头指针的前一个位置，即end1==(end2+1)mod M。

《计算机学科专业基础综合》考试大纲及参考书目（2014年版）重庆大学考试科目代码：917试卷内容结构数据结构45分计算机组成原理45分操作系统35分计算机网络25分四、试卷题型结构单项选择题80分（40小题，每小题2分）综合应用题70分参考书目数据结构（C语言版本）.严蔚敏吴伟民.清华大学出版社.1997.4第一版2004.11第28次印刷.计算机组成和设计：硬件/软件接口.David A.Patterson. John L.Hennessy.机械工业出版社.2012年1月1日.操作系统：精髓与设计原理（原书第6版）.斯托林斯(William Stallings)著,陈向群,陈渝译.机械工业出版社,2010-09-01.计算机网络（第五版，简体中文）.Andrew S.Tanenbaum.David J.Wetherall.清华大学出版社.2012年3月.数据结构【考查目标】掌握数据结构的基本概念、基本原理和基本方法。

掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。

能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。

一、线性表（一）线性表的定义和基本操作（二）线性表的实现顺序存储链式存储线性表的应用二、栈、队列和数组（一）栈和队列的基本概念（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用（五）特殊矩阵的压缩存储三、树与二叉树（一）树的基本概念（二）二叉树二叉树的定义及其主要特性二叉树的顺序存储结构和链式存储结构二叉树的遍历线索二叉树的基本概念和构造（三）树、森林树的存储结构森林与二叉树的转换树和森林的遍历（四）树与二叉树的应用二叉排序树平衡二叉树哈夫曼（Huffman）树和哈夫曼编码四、图（一）图的基本概念（二）图的存储及基本操作邻接矩阵法邻接表法邻接多重表、十字链表（三）图的遍历深度优先搜索广度优先搜索（四）图的基本应用最小（代价）生成树最短路径拓扑排序关键路径五、查找（一）查找的基本概念（二）顺序查找法（三）分块查找法（四）折半查找法（五）B树及其基本操作、B+树的基本概念（六）散列（Hash）表（七）字符串模式匹配（八）查找算法的分析及应用六、排序（一）排序的基本概念（二）插入排序直接插入排序折半插入排序（三）起泡排序（BubbleSort）（四）简单选择排序（五）希尔排序（ShellSort）（六）快速排序（七）堆排序（八）二路归并排序（MergeSort）（九）基数排序（十）各种内部排序算法的比较（十一）排序算法的应用计算机组成原理【考查目标】理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式，具有完整的计算机系统的整机概念。

《计算机学科专业基础综合》考试大纲及参考书目（2014年版）重庆大学考试科目代码：917试卷内容结构数据结构45分计算机组成原理45分操作系统35分计算机网络25分四、试卷题型结构单项选择题80分（40小题，每小题2分）综合应用题70分参考书目数据结构（C语言版本）.严蔚敏吴伟民.清华大学出版社.1997.4第一版2004.11第28次印刷.计算机组成和设计：硬件/软件接口.David A.Patterson. John L.Hennessy.机械工业出版社.2012年1月1日.操作系统：精髓与设计原理（原书第6版）.斯托林斯(William Stallings)著,陈向群,陈渝译.机械工业出版社,2010-09-01.计算机网络（第五版，简体中文）.Andrew S.Tanenbaum.David J.Wetherall.清华大学出版社.2012年3月.数据结构【考查目标】掌握数据结构的基本概念、基本原理和基本方法。

掌握数据的逻辑结构、存储结构及基本操作的实现，能够对算法进行基本的时间复杂度与空间复杂度的分析。

能够运用数据结构的基本原理和方法进行问题的分析与求解，具备采用C或C++语言设计与实现算法的能力。

一、线性表（一）线性表的定义和基本操作（二）线性表的实现顺序存储链式存储线性表的应用二、栈、队列和数组（一）栈和队列的基本概念（二）栈和队列的顺序存储结构（三）栈和队列的链式存储结构（四）栈和队列的应用（五）特殊矩阵的压缩存储三、树与二叉树（一）树的基本概念（二）二叉树二叉树的定义及其主要特性二叉树的顺序存储结构和链式存储结构二叉树的遍历线索二叉树的基本概念和构造（三）树、森林树的存储结构森林与二叉树的转换树和森林的遍历（四）树与二叉树的应用二叉排序树平衡二叉树哈夫曼（Huffman）树和哈夫曼编码四、图（一）图的基本概念（二）图的存储及基本操作邻接矩阵法邻接表法邻接多重表、十字链表（三）图的遍历深度优先搜索广度优先搜索（四）图的基本应用最小（代价）生成树最短路径拓扑排序关键路径五、查找（一）查找的基本概念（二）顺序查找法（三）分块查找法（四）折半查找法（五）B树及其基本操作、B+树的基本概念（六）散列（Hash）表（七）字符串模式匹配（八）查找算法的分析及应用六、排序（一）排序的基本概念（二）插入排序直接插入排序折半插入排序（三）起泡排序（BubbleSort）（四）简单选择排序（五）希尔排序（ShellSort）（六）快速排序（七）堆排序（八）二路归并排序（MergeSort）（九）基数排序（十）各种内部排序算法的比较（十一）排序算法的应用计算机组成原理【考查目标】理解单处理器计算机系统中各部件的内部工作原理、组成结构以及相互连接方式，具有完整的计算机系统的整机概念。

2014考研统考计算机基础综合真题解析一、单项选择题：第1～40小题，每小题2分，共80分。

下列每题给出的四个选项中，只有一个选项是最符合题目要求的。

2、假设栈初始为空，将中缀表达式a/b-(c*d+e*f)/g 转化为等价后缀表达式过程中，当扫描到f 时，栈中的元素依次为：A 、+（*-B 、+（-*C 、/+(*-*D 、/+-*涉及考点：考察中缀和后缀表达式的转化，并考察栈这种数据结构4、如下图二叉树进行中序线索化，则元素X 的左、右线索指向的元素为A 、 ecB 、 eaC 、 dcD 、 ba涉及考点：中序线索化二叉树，找出左右线索5、森林F 转化为对应二叉树T ，则F 的叶结点个数是（）A 、T 的叶结点个数B 、T 中度为1的结点个数C 、T 的左孩子指向为空的个数D 、T 的右孩子指向为空的个数涉及考点：森林转化为二叉树做法：第一，断开除最左孩子的孩子节点，第二，连接孩子节点中各兄弟节点，第三，将树顺时针旋转45度第四，同理处理其他树。

第五，将所有树按照先后顺序依次作为右子树连接。

6、5个元素有4种编码方案，下列不是前缀编码的是A 、01,0000,0001,001,1B 、011,000,001,010,1 ac bdx eC、000,001,010,011,100D、0,100,110,1110,1100涉及考点：字符的前缀编码8、用哈希（散列）方法处理冲突（碰撞）时可能发生堆积（聚集)现象，则下列会直接受到堆积现象影响的是A、存储效率B、散列函数C、载运因子D、平均查找长度涉及考点：哈希（三列）方法处理冲突堆积现象影响的因素9、存一棵具有15个关键词的4阶B树，则含有关键词的结点可能有A、5B、6C、10D、15涉及考点：B树10、用希尔排序法，对一列数据序列排序时，若第一次排序结果为：9,1,4,13,7,8,20,23,15，则该排序可能的间隔是：A、2B、3C、4D、5涉及考点：希尔排序法中的间隔11、下列最不可能是快速排序第二轮的结果是A、2,3,5,4,6,7,9B、2,7,5,6,4,3,9C、3,2,5,4,7,6,9D、4,2,3,5,7,6,9涉及考点：快速排序法12、程序P在装置M执行时间为20秒，编译优化后，P执行的指令数是以前的70%，但CPI 为以前的1.2倍，则现在P在M上的执行时间为A、8.4秒B、11.7秒C、14.0秒D、16.8秒涉及考点：cpu计算时间的计算方法。

计算机学科专业基础综合真题2014年一、单项选择题1. 下列程序段的时间复杂度是count=0;for(k=1; k＜=n; k*=2)for(j=1; j＜=n; j++)count++;A.O(log2n)B.O(n)C.O(nlog2n)D.O(n2)答案：C[解答] 题目中给出了一个2层的嵌套循环，里层循环的时间复杂度是O(n)，外层循环的时间复杂度是O(log2n)。

对于嵌套循环，其整体复杂度是两层循环的复杂度的乘积，因此总体的时间复杂度是D(nlog2n)。

2. 假设栈初始为空，将中缀表达式a/b+(c*d-e*f)/g转换为等价的后缀表达式的过程中，当扫描到f时，栈中的元素依次是A.+(*-B.+(-*C./+(*-*D./+-*答案：B[解答] 后缀表达式为ab/cd*ef*-g/+。

根据中缀表达式a/b+(c*d-e*f)/g转换为等价的后缀表达式的过程，字母不需要入栈，只有扫描到符号时才需要入栈。

最先入栈的是“/”，当扫描完b时出栈。

接下来入栈的是“+”和“(”，然后扫描c，后面的“*”要入栈，再扫描d，然后“*”出栈。

接下来“-”入栈，扫描e，接下来的“*”入栈，接下来就扫描到f了。

此时没有出栈的有“+，(，-，*”。

3. 循环队列存放在一维数组A[0..M-1]中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行人队和出队操作，队列中最多能容纳M-1个元素，初始时为空。

下列判断队空和队满的条件中，正确的是A.队空：end1==end2；队满：end1==(end2+1)mod MB.队空：end1==end2；队满：end2==(end1+1)mod(M-1)C.队空：end2==(end1+1)mod M；队满：end1==(end2+1)mod MD.队空：end1=(end2+1)mod M；队满：end2==(end1+1)mod(M-1)答案：A[解答] 对于循环链表来说，队列空的条件是队头指针和队尾指针指向同一个位置，即end1==end2；队列满的条件是队尾指针指向队头指针的前一个位置，即end1==(end2+1)mod M。