华南理工考研计算机历年真题.docx
- 文档编号:692518
- 上传时间:2023-04-29
- 格式:DOCX
- 页数:13
- 大小:26.71KB
华南理工考研计算机历年真题.docx
《华南理工考研计算机历年真题.docx》由会员分享,可在线阅读,更多相关《华南理工考研计算机历年真题.docx(13页珍藏版)》请在冰点文库上搜索。
华南理工考研计算机历年真题
华南理工大学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。
2.选择题(共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…a1a0,式中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分)
voidf(intk)
{if(k>0)
{printf("%d",k);
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.dC.fD.(e,f)
2.一棵深度为4的完全二叉树,最少有________个结点。
A.4B.8C.15D.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)/kB.n-kC.(n+1)/kD.(nk-n+1)/k
8.具有n个顶点的无向图至多有_____条边。
A.n-1B.n(n-1)/2C.n(n+1)/2D.n2/2
9.深度为4的101阶B树,最少有______个结点。
A.154B.105C.103D.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.画出下列矩阵的三元组表示法和十字链表表示法。
00000
80140
00002
00250
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.3B.4C.5D.6
9.一个有向图,共有n条弧,则所有顶点的度的总和为_______。
A.2nB.nC.n-1D.n/2
10.对邻接表的叙述中,_____是正确的。
A.无向图的邻接表中,第i个顶点的度为第i个链表中结点数的二倍
B.邻接表比邻接矩阵的操作更简便
C.邻接矩阵比邻接表的操作更简便
D.求有向图结点的度,必须遍历整个邻接表
11.一棵二叉树中序序列为FEABDC,后序序列为FBADCE,则层序序列为_____。
A.ABCDEFB.EFCDBAC.FECDABD.EFCDAB
12.以下说法中,________是正确的。
A.完全二叉树中,叶结点的双亲的左兄弟(如果存在)一定不是叶结点
B.任何一棵二叉树,终端结点数为度为2的结点数减1
C.二叉树不适合用顺序结构存储
D.结点按层序编号的二叉树,第i个结点的左孩子(如果存在)的编号为2i
13.给定一组关键字{4,26,46,12,9,33},哈希函数为H(key)=keyMOD6,则用线性探测再散列方法来处理冲突,则构造此哈希表共需要比较关键字____次。
A.4B.5C.6D.7
二.解答题(每题4分,共36分)
1.线性表的双向链表的存储结构为:
typedefstructDNode{
TEleminfo;
structDNode*left;
structDNode*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(stacks);置空栈
push(stacks,datatypevalue);新元素value进栈
datatypepop(stacks)出栈,返回栈顶值
booleanisEmpty(stacks)判栈空否
队列的ADT函数有
enQueue(queueq,datatypevalue)元素value进队
datatypedeQueue(queueq)出队列,返回队头值
booleanisEmpty(queueq)判队列空否
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。
设某进程有4页,其页号为0,1,2,3,被分别装入主存的第9、0、1、14块。
试问:
(10分)
1)该进程的总长度是多大?
2)写出该进程每一页在主存中的起始地址。
3)若给出逻辑地址[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-iB、iC、n-i+1D、n-i-1
3.如果环形链表结构如图1所示,则表达式p->next->next的值是()。
A、15B、32C、78D、全不是
图1
4.一个n×n的对称矩阵,如果以行或列为主序放入内存,其容量为()。
A、n*nB、n*n/2C、(n+1)*n/2D、(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
…
produceaniteminnextp;
wait(mutex);
wait(empty);
buffer(in):
=nextp;
signal(mutex);
untilfalse;
end
Consumer:
begin
repeat
wait(mutex);
wait(full);
nextc:
=buffer(out);
out:
=out+1;
signal(mutex);
consumeiteminnextc;
untilfalse;
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分)
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 华南理工 考研 计算机 历年