计算机专业基础综合华东理工考研真题集

计算机专业基础综合华东理工考研真题集一、华东理工大学815计算机专业基础综合考试大纲815计算机专业基础综合硕士研究生招生考试包括数据结构、计算机组成原理、操作系统三大块内容，各占1/3。考试大纲：一、数据结构1数据结构的基本概念，算法及其特征，算法的简单分析与时间/空间复杂度。2线性表的概念特征及的实现。3栈和队列的概念特征及实现，递归。4多维数组与存储，特殊矩阵和稀疏矩阵的压缩存储。5二叉树的性质及实现，线索二叉树，二叉排序树，平衡二叉树，哈夫曼树，堆的建立，插入和删除算法的实现。6树与森林的概念，存储及操作算法，B树，B+树的定义及操作的实现。7图的概念，存储表示，操作及应用的实现。8查找的概念及典型查找算法的实现，哈希表。9排序的概念及典型排序算法的实现。二、计算机组成原理1计算机概要与技术：程序概念入门；硬件概念入门；性能和功耗；性能的测试方法，Amdahl定律。2指令：计算机的语言；计算机的操作数，不同的寻址方式；各种指令的基本格式以及原理，计算机硬件对过程的支持；基本的MIPS指令集体系结构。3计算机的算术运算：计算机加减乘除法运算。浮点数表示，正££754标准，浮点运算。4处理器：数据通路的概念以及建立数据通路的思想；流水线概述；流水线数据通路及其控制；结构冒险、数据冒险、控制冒险；数据冒险的转发与阻塞；控制冒险中假设分支不发生、缩短分支的延迟、动态分支预测的思想与实现方法。5存储器的层次结构：大容量存储器的层次结构；cache的基本原理；cache的性能评估与改进。虚拟存储器；集成虚拟存储器、快表和cache。虚拟存储器、cache、内存数据一致性问题。6存储系统和其他I/O主题：可信度、可靠性和可用性；磁盘存储器；flash；处理器、内存及I/O设备的连接；廉价磁盘冗余阵列。三、操作系统1操作系统的概念、特征、功能和提供的服务。2进程与线程，处理机调度，进程同步与互斥（信息、量，经典同步问题），死锁（系统安全状态，银行家算法）。3内存管理（分页管理方式，分段管理方式），虚拟内存管理（请求分页管理方式，页面置换算法）。4文件管理，设备管理，磁盘组织与管理（磁盘调度算法）。二、配套数据结构考研真题解析第一部分考研真题精选一、单项选择题1若元素a,b,c,d,e,f依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不可能得到的出栈序列是（ ）。［计算机统考（408）2010年研］【答案】D@@【解析】4个选项所给序列的进、出栈操作序列分别为：选项A:Push，Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Pop选项B：Push，Push，Push，Pop，Pop，Push，Pop，Pop，Push，Pop，Push，Pop选项C：Push，Push，Pop，Push，Pop，Pop，Push，Push，Pop，Push，Pop，Pop选项D:Push，Pop，Push，Push，Push，Push，Push，Pop，Pop，Pop，Pop，Pop按照题目要求，不允许连续三次进行退栈操作，所以选项D所给序列为不可能得到的出栈顺序。2若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，则根结点的孩子结点（ ）。［计算机统考（408）2012年研］A.只有eB.有e、bC.有e、cD.无法确定【答案】A@@【解析】由题目可知，若一棵二叉树的前序遍历序列为a,e,b,d,c,后序遍历序列为5,。~,6〃，其中a为这棵二叉树的根结点，接下来，在前序遍历的第二个结点为e，而后序遍历的倒数第二个结点为e，说明a的孩子^结点只有e。3循环队列放在一维数组A［0..M-1］中，endl指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是( )。［计算机统考(408)2014年研］A.队空：endl==end2;队满：endl==(end2+1)modMB.队空：end1==end2;队满：end2==(end1+1)mod(M-1)C.队空：end2==(end1+1)modM;队满：end1==(end2+1)modMD.队空：end1==(end2+1)modM;队满：end2==(end1+1)mod(M-1)【答案】A@@【解析】在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等，则队满。而队空的条件还是首尾指针是否相等。

4已知关键字序列5,8,12,19,28,20,15,22是小根堆（最小堆），插入关键字3入关键字3，调整后的小根堆是（）。［计算机统考（408）2009年研］A.3,5,12,8,28,20,15,22,19B.3,5,12,19,20,15,22,8,28C.3,8,12,5,20,15,22,28,19D.3,12,5,8,28,20,15,22,19【答案】A@@【解析】在堆中插入一个元素后，将不再满足堆的性质。为了使其成为新堆，需要重新调整剩余元素的位置。具体过程如图（1）~（5）所示，（1）为原堆，（2）为插入3后，（3）、（4）为调整过程，（5）为调整后的小根堆。

5下列选项中，不能构成折半查找中关键字比较序列的是（ ）。［计算机统考（408）2015年研］A.500,200,450,180B.500,450,200,180C.180,500,200,450D.180,200,500,450【答案】A@@【解析】折半查找也称二分查找（BinarySearch），它是一种效率较高的查找方法。但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。折半查找的过程是：先确定待查找记录所在的范围，然后逐步缩小范围直到找到或找不到该记录为止。折半查找的关键字序列满足：对每一个关键字，其后面的所有关键字序列或者都小于等于该关键字或者都大于等于该关键字。A项错误，第三次上比较的关键字为450，说明待查关键字位于200~450间，所以第四次比较时不会遇到关键字180。6已知字符串S为"abaabaabacacaabaabcc"，模式串t为"abaabc"，采用KMP算法进行匹配，第一次出现“失配"（s[i]!=t[i]）时，闫二5,则下次开始匹配时，i和j的值分别是（ ）。[计算机统考（408）2015年研]A.i=1,j=0B.i=5,j=0C.i=5,j=2D.i=6,j=2【答案】C@@【解析】模式匹配（KMP）算法对普通的暴力匹配的改进在于：每当匹配过程中匹配失败时，主串（本题为S）的指针（i）不需要回溯，而是利用已经得到的“部分匹配”的结果将模式串（t）向右“滑动”尽可能远的一段距离后，继续进行比较。模式串“滑动”的距离是由模式串（t）本身决定的，即t的子串t[0...j-1]中前缀串和后缀串相等的最长长度。本题中第一次失配i=5,字串为匕522匕’，其相等且最长的前后缀为“ab”，一次下一个）二2。7下列关于无向连通图特性的叙述中，正确的是（ ）。［计算机统考（408）2009年研］I.所有的顶点的度之和为偶数口.边数大于顶点个数减1田.至少有一个顶点的度为1A.只有IB.只有口C.I和口D.I和田【答案】A@@【解析】在图中，顶点的度TD（Vi）之和与边的数目满足关系式：2=1其中，n为图的总结点数，e为总边数。因此，1项正确。对于口、皿页中的特性不是一般无向连通图的特性，可以轻松地举出反例。“至少有一个顶点的度为1”的反例如下图（1）所示，“边数大于顶点个数减1”的反例如下图（2）所示。8下列叙述中，不符合m阶B树定义要求的是（ ）。［计算机统考（408）2009年研］A.根结点最多有m棵子树B.所有叶结点都在同一层上C.各结点内关键字均升序或降序排列D.叶结点之间通过指针链接【答案】D@@【解析】B树就是指B-树。根据B-树的定义，m阶B-树中每个结点最多有m个分支，因此，根结点最多有m棵子树，A项正确；B-树中所有叶结点都在最底层，位于同一层，B项正确；结点内各关键字互不相等且有序排列，C项正确。但是，所有叶子结点之间通过指针链接，是B+树的定义，而B-树中没有。因此，D项是错误的。9排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（ ）。［计算机统考（408）