华南理工考研计算机历年真题

. . . .

华南理工大学2004年攻读硕士学位研究生入学考试试卷

（试卷上做答无效，请在答题纸上做答，试后本卷必须与答题纸一同交回） 科目名称：计算机专业综合一(组成原理、数据结构、操作系统)

适用专业：计算机系统结构、计算机应用技术、软件工程、计算机应用技术 I. 计算机组成原理试题 （50分） 一．填空题（共10分）

1．计算机的工作过程主要是周而复始地 A 、 B 和 C 的过程。 2．在浮点运算中，当运算结果阶码大于所能表示的 A 时称为溢出，若阶码用双符号S0′S0的移码表示，则当S0′S0 = B 时为溢出。

3．双端口存储器和多模块交叉存储器属于 A 存储器结构；前者采用 B 并行技术，后者采用 C 并行技术。

4．在微程序控制器中，一般采用较简单的 A 、 B 二级时序体制。 5．CPU响应中断时保护两个关键的硬件状态是 A 和 B 。 二．选择题（共6分）

1．设浮点数的阶为8位（其中1位阶符），用移码表示，尾数为24位（其中1位数符），用原码表示。则它所能表示的最大规格化正数是（ ）。

A．(27-1)×(1-2-23 ) B． ×(1-2-23 ) C． ×(1-2-23 ) D． ×(1-2-22 ) 2．下列说法正确的是（ ）。

A. 微程序控制方式和硬布线方式相比较，前者可以使指令的执行速度更快 B. 若采用微程序控制方式，则可用μPC取代PC C. 控制存储器可以用ROM实现 D. 指令周期也称为CPU周期 3．下列说法正确的是（ ）。

A. 程序中断过程是由硬件和中断服务程序共同完成的

B. 每条指令的执行过程中，每个总线周期要检查一次有无中断请求 C. 检测有无DMA请求，一般安排在一条指令执行过程的末尾 D. 中断服务程序的最后指令是无条件转移指令 三．完成下列各题（共36分）

1．设[A]补＝an-1an-2…a1 a0，式中an-1为补码符号位，求证真值： （8分）

2．假设主存只有a，b，c三个页框，组成a进c出的FIFO队列进程，访问页面的序列是0，1，3，4，3，2，0，2，1，3，2号。若采用：①FIFO算法；②FIFO+LRU算法。用列表法求以上两种策略的命中率。 （12分）

3．某CPU的部分数据通路如图1所示。WA和WB是分别写入寄存器A和B的控制信号。WA和WB能否包含在一条微指令中？为什么？如要将WA和WB包含在一条微指令中，要采取什么措施？（10分）

4．在图2中，当CPU对设备B的中断请求进行服务时，设备A能否提出中断请求？为什么？如果设备B一提出中断请求总能立即得到服务，问怎样调整才能满足此要求？ （10分）

II 数据结构试题 （50分）

? 填空题?（每小题2分，共16分）

资料整理

. . . .

1． 若用两个堆栈实现队列操作，在队中插入或删除一个元素的时间复杂性是__________。

2． 在向量存储的二叉树中，根结点编号为1，则编号为i和j的两个结点处在同一层的条件是 _____________。

3． n个顶点的无向图G每个顶点的度最大可能是__________。 4． 高度为5的3阶B树至少有__________结点。

5． 已知A为n阶（n>=1）的对称矩阵，现将其下三角部分按行优先存放在一维数组B中。矩阵元素Aij (i >=j ) 在B中的下标是__________。

6． 用邻接矩阵求最短路径的Floyd算法的时间复杂性为__________。

7． 若一个无向图有n个顶点，e条边(n>e)，且是一个森林。则它有__________棵树。 8．对n个元素进行归并排序，需要的辅助空间为__________。 二． 解答题（共14分）

1． 一棵树的先序和后序序列分别如下，画出该树。（3分） 先序序列：ABCDEFGHIJKLM 后序序列：CDBEFGJKLMIHA

2． 对下面的递归算法，写出调用f(4)的执行结果。（3分） void f(int k) { if( k>0 )

{ printf(\f(k-1); f(k-1); }

华南理工大学2005年计算机综合431考研试卷

数据结构（75分）

一． 选择题（每题只有一个答案正确，每题2分，共24分） 1. 广义表A=（a,b,c,(d, (e,f))），则下面式子的值为 ；(Head与Tail分别是取表头和表尾的函数)

Head(Tail(Tail(Tail(A)))) A．(d,(e,f)) B. d C.f D.(e,f)

2. 一棵深度为4的完全二叉树，最少有________个结点。 A. 4 B. 8 C. 15 D. 6

3. 稀疏矩阵一般的压缩存储方法有两种，即_______。 A．二维数组和三维数组 B．三元组表和散列 C．三元组表和十字链表 D．散列和十字链表

资料整理

. . . .

4. 下列判断中，______是正确的。

A. 二叉树就是度为2的树 B. 二叉树中不存在度大于2的结点 C. 二叉树是有序树 C. 二叉树的每个结点的度都为2 5. 在构造哈希表方面，下面的说法_________是正确的。 A．链地址法在处理冲突时会产生聚集

B．线性探测再散列在处理冲突时会产生聚集 C．好的哈希函数可以完全避免冲突

D．在哈希表中进行查找是不需要关键字的比较的 6. 以下图的叙述中，正确的是_______。

A．强连通有向图的任何顶点到其它所有顶点都有弧 B．任意图顶点的入度等于出度 C．有向完全图一定是强连通有向图

D. 有向图的边集的子集和顶点集的子集可构成原有向图的子图

7. 一棵共有n个结点的树，其中所有分枝结点的度均为k，则该树中叶子结点的个数为________。

A．n(k-1)/k B．n-k C．(n+1)/k D．(nk-n+1)/k 8. 具有n个顶点的无向图至多有_____条边。 A．n-1 B．n(n-1)/2 C. n(n+1)/2 D. n2/2

9. 深度为4 的101阶B树，最少有______个结点。 A. 154 B. 105 C. 103 D. 151

10. 利用逐点插入法建立序列(60，74，44，99，75，30，36，45，68，9)对应的二叉排序树以后，查找元素75要进行______元素间的比较。 A．4次 B．3次 C. 7次 D．5次

11. 对数据结构，下列结论中不正确的是_____。 A． 相同的逻辑结构，对应的存储结构也必相同

B． 数据结构由逻辑结构、存储结构和基本操作三个方面组成 C． 数据存储结构就是数据逻辑结构的机内的实现 D． 对数据基本操作的实现与存储结构有关

12. 对AOE网的关键路径，下面的说法_______是正确的。

A．提高关键路径上的一个关键活动的速度，必然使整个工程缩短工期 B．完成工程的最短时间是从始点到终点的最短路径的长度 C．一个AOE网的关键路径只有一条，但关键活动可有多个 D．任何一项活动持续时间的改变都可能会影响关键路径的改变 二． 解答题（每题4分，共40分）

1. 设有关键字序列为：{ 50，71，80，60，55，40，25，99 }，用数组存储。请以堆排序方式把数据排列成递增序列。给出建堆和每趟堆调整后的数据序列。 解：建堆后的数据序列 每趟堆调整后的数据序列

2. 画出下列矩阵的三元组表示法和十字链表表示法。 0 0 0 0 0 8 0 1 4 0 0 0 0 0 2 0 0 2 5 0

3. 画出下图的邻接表，并用克鲁斯卡尔算法求其最小生成树。

资料整理

. . . .

4. 有以下算法，分析其时间复杂度。 i=1;

while(i*i*i<=n) i++;

5． 循环队列A[m]中，已知头指针rear、尾指针front与元素个数len中的任意两个，如何求另一个？

6． 某完全二叉树有360个结点，则叶子数有多少？度1结点有多少？ 7． 哪些排序思想或方法在排序过程中产生连续增长的有序子序列？

8． 图的遍历（广度优先或深度优先）生成树是否唯一？与什么因素有关？什么情况下是唯一的？

9． 求在8个结点的有序表中进行二分查找，等概率下查找成功和不成功时的平均查找长度 10．外部排序的时间由什么因素决定？为了减少外部排序时间，有什么方法？ 三．算法设计。做出简要分析并写函数。（共11分）

1． 设一个由字母组成的字符串，编写算法对它们的字母顺序进行调整，使输出时所有大写字母都在小写字母之前，并且同类字母之间的相对位置不变。（5分） 例如，原有字符串为：AbcDEfghiJKlmn 输出序列为： ADEJKbcfghilmn

2． 编写算法，由无向图的邻接表生成邻接矩阵。（6分）

操作系统（75分） 一、名词解释(15分) 1．临界区 2．用户级线程 3．并行交叉存取

二、一个线程是否可被时钟中断抢占？如果是，请说明在什么情况下可被抢占，否则请解释为什么。（5分）

三、UNIX中对信号的处理有哪几种方式？（6分）

四、在非抢占式调度方式中，什么情况下正在运行的进程会放弃CPU？（6分） 五、试说明中断处理的主要过程。（6分）

六、试解释成组链接法是如何管理文件系统中的空闲块的？（10分）

七、在数据传输过程中为什么要进行数字签名？试介绍简单数字签名的过程。简单数字签名能否达到保密的目的？为什么？（12分） 八、设有一进程共有5页（0-4），其中程序占3页（0-2），常数占1页（3），工作单元占1页（4），它们依次存放在外存的第45、46、98、99和100块。现在程序段已分配在内存的第7、10、19页，而常数区和工作区尚未获得内存，请回答下述问题：

1） 页表应包括那些项目？填写此页表。若工作区分配到内存的第9页，则页表应如何变化 2） 在运行中因需要使用常数而发生中断，假定此时内存无空闲页面，需要把第9页淘汰，操作系统应如何处理？页表又发生什么变化？（15分）

华南理工大学2006年计算机专业综合(431)考研试卷

数据结构

资料整理

. . . .

一． 选选择题（每题只有一个答案正确，每题2分，共26分） 1. 以下图的叙述中，正确的是_______。

A．图与树的区别在于图的边数大于或等于顶点数

B．假设有图G=(V, {E}), 顶点集V’íV，E’ íE，则V’和{E’}构成G的子图 C．无向图的连通分量指无向图中的极大连通子图

D. 图的遍历就是从图中某一顶点出发访遍图中其余顶点 2. 下列判断中，______是正确的。

A. 深度为k的二叉树最多有2k-1个结点(k≥1)，最少有k个结点 B. 二叉树中不存在度大于2的结点

C. 对二叉树遍历是指先序、中序或后序遍历中的一种 D. 构造线索二叉树是为能方便找到每个结点的双亲 3. 对各种内部排序方法来说，__________。

A. 快速排序时间性能最佳 B. 基数排序和归并排序是稳定的排序方法 C. 快速排序是一种选择排序 D. 堆排序所用的辅助空间比较大 4. 稀疏矩阵的三元组存储方法_______。

A．实现转置运算很简单，只需将每个三元组中的行标和列标交换 B．是一种链式存储方法

C．矩阵的非零元个数和位置在操作过程中变化不大时较有效 D．比十字链表法更高效

5. 对于二叉排序树，下面的说法_______是正确的。

A．二叉排序树是动态树表，查找不成功时插入新结点时，会引起树的重新分裂和组合 B．对二叉排序树进行层序遍历可得到有序序列

C．用逐点插入法构造二叉排序树时，若先后插入的关键字有序，二叉排序树的深度最大 D．在二叉排序树中进行查找，关键字的比较次数不超过结点数的1/2 6. 在构造哈希表方面，下面的说法_________是正确的。 A．再哈希法在处理冲突时不会产生聚集

B．哈希表的装填因子越大说明空间利用率越好，因此应使装填因子尽量大 C．哈希函数选的好可减少冲突现象

D．对任何具体关键字集都不可能找到不产生冲突的哈希函数

7. 已知广义表(( ),(a), (b, c, (d), ((d, f))))，则以下说法正确的是__________。 A．表长为3，表头为空表，表尾为((a), (b, c, (d), ((d, f)))) B．表长为3，表头为空表，表尾为(b, c, (d), ((d, f))) C．表长为4，表头为空表，表尾为((d, f))

D．表长为3，表头为(())，表尾为((a), (b, c, (d), ((d, f))))

8. 已知一棵5阶B树有53个关键字，并且每个结点的关键字都达到最少状态，则它的深度是________。

A. 3 B. 4 C. 5 D. 6

9. 一个有向图，共有n条弧，则所有顶点的度的总和为_______。 A．2n B. n C. n-1 D. n/2

10. 对邻接表的叙述中，_____是正确的。

A．无向图的邻接表中，第i个顶点的度为第i个链表中结点数的二倍 B．邻接表比邻接矩阵的操作更简便 C．邻接矩阵比邻接表的操作更简便

D．求有向图结点的度，必须遍历整个邻接表

资料整理

本文来源：https://www.bwwdw.com/article/9h3d.html