研究生入学考试试题A.doc

研究生入学考试试题A

资料仅供参考

研究生入学考试试题(A)
考试科目：计算机软件技术基础 报考学科、专业：计算机应用技术
请注意:全部答案必须写在答题纸上，否则不给分。
一、名词解释（第1~4题，每题3分，第5、6题要求先写出英文全称，再用中文简要解释其含义，每题4分，共20分）
1、 数据类型 2、线程
3、 原语 4、虚拟设备
5、 WPL 6、DMA
二、填空题（每题2分，共20分）

1、假设B =（K， R）是一个逻辑结构，r是一个K到K的1 ：1关系，r∈R，若k，k’∈K，且< k，k’>∈r，则称k’是k的 ① ，k是k’的 ② 。
2、设循环队列中数组的下标范围是0～n-1，其头尾指针分别为f和r，则该循环队列中数据元素的个数为 。
3、设有一个三对角矩阵An*n，将其三条对角线上的元素逐行地存储到向量B[0..3n-3]中，则元素A[5,6]的存储单元下标为 。（假设下标都从0开始）
4、可采用折半查找法进行查找的数据表一般应满足的条件为 ① 和 ② 。
5、操作系统具备处理并发任务的能力，其最重要的硬件支持是 。
6、每个信箱能够由 ① 和 ② 两部分组成。
7、死锁产生的根本原因是 ① 和 ② 。
8、文件包括 ① 和 ② 两种，前者是指文件内的信息不再划分独立的单位，整个文件是由一串信息组成，后者是指文件内的信息按逻辑上独立的含义划分信息单位。
9、通道在执行通道程序的过程中，需要访问内存中的两个固定单元， ① 和 ② 。
10、UNIX操作系统的第一个版本Versional是 ① 公司下属的Bell实验室的两个程序员Ken Thompson和Dennis Ritchie于 ② 年在PDP11机器上开发实现的。
三、简答题（每题5分，共30分）
1、 设多项式P(x)＝5x6＋3x4－4x3＋x－12，请用两种不同的线性存储结构表示该多项式，画出它们的存储映像图。
2、 设一棵二叉树的前序遍历序列为B A L F E C D H G， 后序遍历序列为L F A D H C G E B，请画出该二叉树，并分别给出该二叉树的中序遍历序列和按层次遍历序列。
第 1 页，共 5 页

研究生入学考试试题
考试科目：计算机软件技术基础 报考学科、专业：计算机应用技术
请注意:全部答案必须写在答题纸上，否则不给分。
3、 铁路进行列车调度时, 常把站台设计成栈式结构，试问：
（1）设有编号为1，2，3，4的四辆列车, 顺序开入站台, 则可能的出站序列有多少种？
（2）若进站五辆列车，其顺序为1，2，3，4，5, 那么是否能够得到4，5，2，1，3和3，4，2，5，1这样的出站序列？请说明原因或给出得到该序列的列车进站、出站过程。
4、 假设Hash函数为：H（key）= 3*key % 11 （其中 * 为乘法、 % 为取余运算，下同）
并采用开放地址法处理冲突，其求下一地址的函数为：
D1 = H（key）；
Di = （Di-1+（7*key））% 11 （ i = 2，3，… ）
试在0~10的散列地址空间中对关键字序列（22，41，53，46，30，13，01，67）构造Hash表，并求出在等概率情况下查找成功的平均查找长度。
5、 什么叫抢占式处理机调度和非抢占式处理机调度？先来先服务（FCFS）、优先数法各属于哪种调度方式？
6、 某系统采用请求分页存储管理方案，其逻辑地址有32 bits，页内地址占12 bits。有一个4页的作业，其逻辑页号为0，1，2，3分别装入内存空间的7，8，16，19块。试问：
（1） 作业的虚存空间有多大？
（2） 系统的页面大小为多少？
（3） 逻辑地址5000对应的物理地址是多少？
四、程序理解、填空题（第1题4分，第2题16分，第3题8分，共28分）
1、 void p ( int n )
{ if ( n > 0 )
{ p ( n-1 ) ；
printf ( “ %d ”, &n ) ；
p ( n-1 ) ；
printf ( “ %d ”, &n ) ；
}
}
当调用 p ( 4 ) 时，其完整的输出结果为：
第 2 页，共 5 页

研究生入学考试试题
考试科目：计算机软件技术基础 报考学科、专业：计算机应用技术
请注意:全部答案必须写在答题纸上，否则不给分。
2、 以下算法的功能是利用堆进行排序，请在空白处填上合适语句以完成该算法。
void sift (RecType R[ ]，int k，int m )
{ int i，j，x；
RecType temp；
int finished = 0；
i = k ；
① ；
x = R[ i ]. key；
temp = R[ k ]；
while ( j < m && ! finished )
{ if ( j < m && ② ) j + +；
if ( x >= R[ j ]. Key ) finished = 1；
else
{ ③ ；
④ ；
⑤ ；
}
}
⑥ ；
}
void heapsort ( RecType R[ ]， int n )
{ int i ；
RecType x ；
for ( i = n/2； i >= 1； i - - ) ⑦ ；
for ( i = n； i >= 2； i - - )
{ x = R[ 1 ]；
R[ 1 ] = R[ i ] ；
R[ i ] = x ；
⑧ ；
}
}
第 3 页，共 5 页

研究生入学考试试题
考试科目：计算机软件技术基础 报考学科、专业：计算机应用技术
请注意:全部答案必须写在答题纸上，否则不给分。
3、 阅读如下函数，请在空格处填上恰当的注释，并说明该函数的功能。
typedef struct node {
datatype data[ ] ；
int len ；
} Lnode ；
void mystery ( Lnode &A，Lnode B，Lnode C )
{ int i，jk，s，f ；
i = 0； j = 0；
while ( i <= A.len ) && ( j <= B.len )
{ if ( A.data [ i ] = = B.data [ j ] ) // ①
{ f = 0 ；
for ( k = 0； k <= C.len； k + + )
if ( A.data [ i ] = = C.data [ k ] ) f = 1；
if ( f = = 0 ) // ②
{ - - A.len ；
for ( s = i ； s <= A.len ； s + + )
A.data [ s ] = A.data [ s+1 ] ；
}
else
i + + ；
}
else // ③
{ if ( A.data [ i ] > B.data [ j ] ) j + + ；
if ( A.data [ i ] < B.data [ j ]) i + + ；
}
}
}
功能为： ④
第 4 页，共 5 页

研究生入学考试试题
考试科目：计算机软件技术基础 报考学科、专业：计算机应用技术
请注意:全部答案必须写在答题纸上，否则不给分。
五、综合应用题（第1题12分第2题15分，共27分）
1、 在一个漆黑的夜晚，一伙旅行者需要经过一座横跨于深谷间的小桥，她们只有一盏老式的油灯作照明。要想成功过桥，灯光是必须的，另外因为桥很窄，最多仅容两人同时过桥，更糟糕的是油灯里的油量有限，要尽可能快地过桥。而且由于过桥需要照明，因此任何两个人一起过桥时，都得由走得慢的人决定过桥时间。则：
（1） 假设A、B、C、D四个人，A过桥需要1分钟，B过桥需要2分钟，C过桥需要5分钟，D过桥需要10分钟，请安排她们的过桥次序使其总的过桥时间最短，并算出其过桥时间。
（2） 针对n个人，她们的过桥时间分别为数组T[ n ]，试说明一个能够满足以上需求的安排她们过桥次序的算法思想（或算法）。
2、 有个寺庙，庙中有小和尚、老和尚若干人，庙里有一只水缸，由小和尚提水入缸给老和尚饮用，每次只能入缸1桶水或取缸中1桶水。水缸可容10桶水，水取自同一口井中。水井径窄，每次仅能容一只水桶取水，水桶总数为3个。试用同步工具写出小和尚、老和尚取水、用水的活动过程。
六、算法设计分析题（第1题12分，第2题13分，共25分）
1、设二叉树以二叉链表为存储结构，首先定义该二叉树的数据结构，然后针对二叉树中一个结点（由指针p所指），设计一个求p的兄弟结点的算法（若p没有兄弟，则返回空指针）。
2、设有向图的邻接表表示结构如下：
#define MaxVexNum 30 //最大顶点数
typedef struct ArcNode {
int adjvex ； //该弧弧头所指向的顶点下标
struct ArcNode * nextarc ； //指向下一条弧的指针
InfoType * info ； //与该弧相关的其它信息
} ArcNode ；
typedef struct VNode {
VertexType data ； //顶点信息
ArcNode * firstarc ； //指向出自该顶点的第一条弧的指针
} VNode，AdjList [ MaxVexNum ] ；
tyoedef struct {
int vexnum，arcnum ；//分别存放图中顶点、弧的数目
AdjList vertices ； //邻接表
} ALGraph ；
请编写算法，分别求图G中一个顶点v的入度和出度的算法Indegrees( ALGraph G，int v )，Outdegree(ALGraph G，int v )，并分析它们的时间复杂度。(其中v表示顶点在AdjList中的下标，下标均从0开始计)
第 5 页，共 5 页