华南理工大学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．求有向图结点的度，必须遍历整个邻接表
11. 一棵二叉树中序序列为FEABDC，后序序列为FBADCE，则层序序列为_____。 A. ABCDEF B. EFCDBA C. FECDAB D. EFCDAB 12. 以下说法中，________是正确的。
A. 完全二叉树中，叶结点的双亲的左兄弟（如果存在）一定不是叶结点 B. 任何一棵二叉树，终端结点数为度为2的结点数减1
C. 二叉树不适合用顺序结构存储
D. 结点按层序编号的二叉树，第i个结点的左孩子（如果存在）的编号为2i
13. 给定一组关键字{4，26，46，12，9，33}，哈希函数为H(key)=key MOD 6，则用线性探测再散列方法来处理冲突，则构造此哈希表共需要比较关键字____次。 A. 4 B. 5 C. 6 D. 7
二． 解答题（每题4分，共36分） 1. 线性表的双向链表的存储结构为： typedef struct DNode { TElem info; struct DNode *left; struct DNode *right;
};
并假设已建立头指针为head的双向链表，p指向其中某个结点，写一个程序段，从该循环链表中删除p所指向结点的前一个结点(假设该结点存在)。
2. 简述在AOV网中求拓扑排序的过程，并写出下面AOV网中的两个拓扑有序序列 3. 给出下面有向图的邻接矩阵、邻接表及逆邻接表。
4. 假定字符集{a, b, c, d, e, f}中的字符在通信网络中出现的频率见下表，请设计赫夫曼编码。 字符 a b c d e f 频率 0.10 0.23 0.36 0.11 0.15 0.05 5．对n个顶点的无向图G，采用邻接矩阵表示，如何判别下列问题； (1)图中有多少条边？
(2)任意两个结点i和j是否有边相连？
(3)任意一个顶点的度是多少？
6．对下图所示的AOE网，回答：工程完成的最短时间是多少？写出关键路径（不需过程），是否有某些活动提高速度后能导致整个工程缩短工期？
7. 已知Q是一个非空队列
，S是一个空栈。仅用队列和栈的ADT函数，用C语言伪码编写一个算法，将队列Q中的所有元素逆置。 栈的ADT函数有：
makeEmpty(stack s); 置空栈
push(stack s，datatype value); 新元素value进栈 datatype pop(stack s) 出栈，返回栈顶值 boolean isEmpty(stack s) 判栈空否 队列的ADT函数有
enQueue(queue q, datatype value) 元素value进队 datatype deQueue(queue q) 出队列，返回队头值
boolean isEmpty(queue q) 判队列空否
8．你所知道的排序方法有几类？简述各类方法的原理。
9．在为一个实际应用设计数据结构时，主要应考虑哪些方面的内容？
三． 算法设计。做出简要分析并写函数。（共13分）
1. 以二叉链表作存储结构，试编写非递规的前序遍历算法。(5分)
2. 无向图用邻接表存储，写出邻接表定义，给出求图中顶点Vi到 Vj的最短路径的函数。（8分）
操作系统
一、名词解释：（18分） 1． 进程
2． Spooling技术 3． 系统调用 4． 死锁 5． 并发
6． 缺页中断
二、有3个并发进程R、M、P，它们共享同一个缓冲区，假定缓冲区只能存放一条记录。进程R负责从输入设备读信息，每读入一个记录后，就把它放进缓冲区；进程M在缓冲区中加工读入的记录；进程P把加工后的记录打印输出。读入的记录经加工输出后，缓冲区又可以存放下一个记录。试写出他们能够正确执行的并发程序。（10分）
三、在某页式管理系统中，假定主存为64K,分成16块，块号为0，1，2，…，15。设某进程有４页，其页号为0，1，2，3，被分别装入主存的第9、0、1、14块。试问：（10分） １） 该进程的总长度是多大？
２） 写出该进程每一页在主存中的起始地址。
３）若给出逻辑地址［0，0］、［1，72］、［2，1023］、［3，99］，请计算出相应的内存地址。（方括号内的第一个数为页号，第二个数为页内地址，题目中的数字均为10进制）。 四、I/O控制可用哪几种方式，各有什么优缺点？（8分）
五、某软盘有40个磁道，磁头从一个磁道移到另一个磁道需要6ms。文件在磁盘上非连续存放，逻辑上相邻的数据块的平均距离为13个磁道，每块的旋转延迟时间及传输时间分别为100ms和25ms。问：（8分） 1） 读取一个100块的文件需要多少时间？
2） 如果对磁盘进行整理使得同一文件的磁盘块尽可能靠拢，从而使逻辑上相邻的数据块的平均距离降为2个磁道，这时读取100块的文件有需要多少时间？
六、两个进程A和B，每一个进程都需要读取数据库中的记录1、2、3假如这两个进程都以1、2、3的次序请求读取记录，系统将不会发生死锁。但如果A以3、2、1的次序读取记录，B以1、2、3的次序读取记录，则死锁可能会发生。试计算两个进程读取记录的次序如果不确定，那么系统保证不发生死锁的概率是多少？（6分）
七、为什么需要一个打开文件的系统调用？一般来讲打开文件的系统调用主要做了些什么？（7分）
八、试说明UNIX操作系统中文件系统的权限是如何控制的（8分）
华南理工大学2007年计算机专业综合431考研试卷
数据结构
一、 选择题（每小题2分，共20分）
1． 折半查找法的时间复杂度是（ ）。
A、 O(n2) B、O(n) C、O(nlog2n) D、O(log2n)
2． 若一个栈的输入序列是1，2，...，n，输出的第一个元素是n，则第i个输出的元素是（ ）。 A、n-i B、i C、n-i+1 D、n-i-1
3． 如果环形链表结构如图1所示，则表达式p->next->next的值是（ ）。 A、15 B、32 C、78 D、全不是
图1
4． 一个n×n的对称矩阵，如果以行或列为主序放入内存，其容量为（ ）。 A、n*n B、n*n/2 C、(n+1)*n/2 D、(n+1)*(n+1)/2 5． 快速排序在（ ）情况下最不利于发挥其长处。 A、被排序的数据量太大 B、被排序的数据中有大量相同 C、被排序的数据基本有序 D、被排序的数据太分散 6． 具有线性结构的数据结构是（ ）。 A、文件结构 B、树结构 C、图结构 D、广义表 7． 在下列网中，（ ）是边不带权值的图。 A、邮电网 B、AOV网 C、公路网 D、AOE网 8． 线索二叉树中某结点为叶子的条件是（ ）。 A、p->lchild!=NULL||p->rchild!=NULL B、p->ltag==0||p->rtag==0
C、p->lchild!=NULL&&p->rchild!=NULL
D、p->ltag==1 && p->rtag==1
9．给定整数集合{3,5,6,9,12}，与之对应的哈夫曼（Huffman）树是（ ）。
10．图2是一棵( )。 A、4阶B-树 B、4阶B+树 C、3阶B-树 D、3阶B+树
二、 简答题（每小题5分，共30分）
1、 对n个顶点的无向图G，采用邻接矩阵A表示。试问： （1） 图G有多少条边？
（2） 如何判断顶点i、j之间是否有边相连？
（3） 如何计算一个顶点的度？
2、 如果一棵二叉树n个顶点，用递归算法执行中序遍历。最坏情况时处理递归的栈至少要多少个单元？为什么？
3、 设n0为哈夫曼树的叶子结点数目，简要推导该树的结点总数。 4、 设有循环队列存储在结构变量q中，用C/C++编写元素x入队的算法。
5、 设有n个关键字，它们具有相同的哈希函数值。若采用线性探测法将它们存放到某个哈希表中，至少需要进行多少次探测？为什么？
6、“有序链表”是指什么值有序？其有序性在存储结构上用什么方式表示？ 三、 算法设计（25分）
1、 （6分）编写一个函数，从元素类型为int的有序表A中删除所有元素值在（x, y）之间（x≤y，不包括x，y）所有元素。并分析你的算法效率。
2、 （12分）设计算法，将一棵以二叉链表形式存储的二叉树按顺序方式存储到数组A中。
算法由以下几个函数组成：
函数count根据树的形态，返回要求顺序存储的数组长度 函数setAry建立指定长度n的动态数组
函数create把二叉树存放到数组中。其中调用count和setAry函数。
3、 （7分）编写算法，求有向图G中距离顶点v的最短路径长度为len的所有顶点。
操作系统部分
1． 试说明进程在三个基本状态之间转换的典型原因（8分） 2． 试修改下面消费者生产者问题解法中的错误（12分） Producer: begin repeat …
produce an item in nextp; wait(mutex); wait(empty);
buffer(in):=nextp; signal(mutex); until false; end Consumer: begin repeat
wait(mutex); wait(full);
nextc:=buffer(out); out:=out+1; signal(mutex);
consume item in nextc;
until false; end;
3． 什么是抢占式调度，什么是非抢占式调度？（6分）
4． 试说明页面替换算法中的clock算法的基本思想（10分）
5． 在一个请求分页系统中，采用LRU页面置换算法时，假如一个作业的页面走向为：1，3，2，1，1，3，5，1，3，2，1，5，当分配给该作业的物理块数分别为3和4时，试计算在访问过程中所发生的缺页次数和缺页率。（8分）
6． 试说明SPOOLing系统的原理。（8分）
7． 某文件系统采用多级索引的方式组织文件的数据存放，假定在文件的i_node中设有13个地址项，其中直接索引10项，一次间接索引项1项，二次间接索引项1项，三次间接索引项1项。数据块的大小为4k，磁盘地址用4个字节表示，问：（15分） 1） 这个文件系统允许的最大文件长度是多少？
2） 一个2G大小的文件，在这个文件系统中实际占用多少空间？（不包括i_node占用的空间）
8． 什么是对称加密算法和非对称加密算法？（8分）