计算机专业基础综合华东理工考研真题集Word文档下载推荐.docx

计算机专业基础综合华东理工考研真题集Word文档下载推荐.docx

《计算机专业基础综合华东理工考研真题集Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《计算机专业基础综合华东理工考研真题集Word文档下载推荐.docx（7页珍藏版）》请在冰点文库上搜索。

程序概念入门；

硬件概念入门；

性能和功耗；

性能的测试方法，Amdahl定律。

2指令：

计算机的语言；

计算机的操作数，不同的寻址方式；

各种指令的基本格式以及原理，计算机硬件对过程的支持；

基本的MIPS指令集体系结构。

3计算机的算术运算：

计算机加减乘除法运算。

浮点数表示，IEEE754标准，浮点运算。

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．只有e

B．有e、b

C．有e、c

D．无法确定

【答案】A@@

【解析】由题目可知，若一棵二叉树的前序遍历序列为a，e，b，d，c，后序遍历序列为b，c，d，e，a，其中a为这棵二叉树的根结点，接下来，在前序遍历的第二个结点为e，而后序遍历的倒数第二个结点为e，说明a的孩子结点只有e。

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

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。

初始时为空，下列判断队空和队满的条件中，正确的是（　　）。

[计算机统考（408）2014年研]

A．队空：

end1＝＝end2；

队满：

end1＝＝（end2＋1）modM

B．队空：

end2＝＝（end1＋1）mod（M－1）

C．队空：

end2＝＝（end1＋1）modM；

end1＝＝（end2＋1）modM

D．队空：

end1＝＝（end2＋1）modM；

end2＝＝（end1＋1）mod（M－1）

【解析】在循环队列中，在少用一个元素空间的前提下，可约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等，则队满。

而队空的条件还是首尾指针是否相等。

4已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（　　）。

[计算机统考（408）2009年研]

A．3，5，12，8，28，20，15，22，19

B．3，5，12，19，20，15，22，8，28

C．3，8，12，5，20，15，22，28，19

D．3，12，5，8，28，20，15，22，19

【解析】在堆中插入一个元素后，将不再满足堆的性质。

为了使其成为新堆，需要重新调整剩余元素的位置。

具体过程如图

（1）～（5）所示，

（1）为原堆，

（2）为插入3后，（3）、（4）为调整过程，（5）为调整后的小根堆。

5下列选项中，不能构成折半查找中关键字比较序列的是（　　）。

[计算机统考（408）2015年研]

A．500，200，450，180

B．500，450，200，180

C．180，500，200，450

D．180，200，500，450

【解析】折半查找也称二分查找（BinarySearch），它是一种效率较高的查找方法。

但是，折半查找要求线性表必须采用顺序存储结构，而且表中元素按关键字有序排列。

折半查找的过程是：

先确定待查找记录所在的范围，然后逐步缩小范围直到找到或找不到该记录为止。

折半查找的关键字序列满足：

对每一个关键字，其后面的所有关键字序列或者都小于等于该关键字或者都大于等于该关键字。

A项错误，第三次比较的关键字为450，说明待查关键字位于200～450间，所以第四次比较时不会遇到关键字180。

6已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s[i]!

＝t[i]）时，i＝j＝5，则下次开始匹配时，i和j的值分别是（　　）。

A．i＝1，j＝0

B．i＝5，j＝0

C．i＝5，j＝2

D．i＝6，j＝2

【答案】C@@

【解析】模式匹配（KMP）算法对普通的暴力匹配的改进在于：

每当匹配过程中匹配失败时，主串（本题为S）的指针（i）不需要回溯，而是利用已经得到的“部分匹配”的结果将模式串（t）向右“滑动”尽可能远的一段距离后，继续进行比较。

模式串“滑动”的距离是由模式串（t）本身决定的，即t的子串t[0…j－1]中前缀串和后缀串相等的最长长度。

本题中第一次失配i＝5，字串为“abaab”，其相等且最长的前后缀为“ab”，一次下一个j＝2。

7下列关于无向连通图特性的叙述中，正确的是（　　）。

Ⅰ．所有的顶点的度之和为偶数

Ⅱ．边数大于顶点个数减1

Ⅲ．至少有一个顶点的度为1

A．只有Ⅰ

B．只有Ⅱ

C．Ⅰ和Ⅱ

D．Ⅰ和Ⅲ

【解析】在图中，顶点的度TD（Vi）之和与边的数目满足关系式：

其中，n为图的总结点数，e为总边数。

因此，Ⅰ项正确。

对于Ⅱ、Ⅲ项中的特性不是一般无向连通图的特性，可以轻松地举出反例。

“至少有一个顶点的度为1”的反例如下图

（1）所示，“边数大于顶点个数减1”的反例如下图

（2）所示。

8下列叙述中，不符合m阶B树定义要求的是（　　）。

A．根结点最多有m棵子树

B．所有叶结点都在同一层上

C．各结点内关键字均升序或降序排列

D．叶结点之间通过指针链接

【解析】B树就是指B－树。

根据B－树的定义，m阶B－树中每个结点最多有m个分支，因此，根结点最多有m棵子树，A项正确；

B－树中所有叶结点都在最底层，位于同一层，B项正确；

结点内各关键字互不相等且有序排列，C项正确。

但是，所有叶子结点之间通过指针链接，是B＋树的定义，而B－树中没有。

因此，D项是错误的。

9排序过程中，对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。

下列排序方法中，每一趟排序结束时都至少能够确定一个元素最终位置的方法是（　　）。

Ⅰ．简单选择排序

Ⅱ．希尔排序

Ⅲ．快速排序

Ⅳ．堆排

Ⅴ．二路归并排序

A．仅Ⅰ、Ⅲ、Ⅳ

B．仅Ⅰ、Ⅱ、Ⅲ

C．仅Ⅱ、Ⅲ、Ⅳ

D．仅Ⅲ、Ⅳ、Ⅴ

【解析】其中简单选择排序、堆排序属于选择类排序，每一趟排序结束时将确定最大（或最小）关键字所在的位置。

快速排序每一趟排序结束时将确定基准关键字所在的位置。

希尔排序、二路归并排序每一趟排序结束时不一定能确定一个元素的最终位置。