南京理工大学计算机科学与工程学院824计算机专业基础A历年考研真题汇编

南京理工大学计算机科学与工程学院

824计算机专业基础A历年考研真题汇编

THROUGHTRR/N

最新资料，WORD格式，可编辑修改!

第1页

目录

2012年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题................3

2011年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题..............13

2010年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题..............22

2009年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题..............31

2008年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题..............39

2007年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题..............50

2006年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题..............60

2005年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题..............70

2004年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题..............78

2003年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题..............86

第2页

2012年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题

南京理工大学

2012年硕士学位研究生入学考试试题

科目代码：824科目名称：计算机专业基础（A）满分：150分

注意:①认真阅读答题纸上的注意事项；②所有答案必须写在谑鼻匕写在本

试题纸或草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！

第一部分离散数学（50分）

1.已知及是4上的自反和对称的二元关系，试证明：（8分）

（1）对于任意的neN,具有对称性：

（2）«尺）为4上的等价关系.

2.已知48,C,。为四个集合，/为4到8的满射，g为C到。的满射，且

/cC=3cO=。.h为4uC至BuD的映射，且对于

Vxe71uC.A（r）=fk；:,试证明方为彳uC到的满射。（6分）

g（x）当xeC

3.4为一个集合，试证明（6分）

4.G=（匕E）是一个简单无向平面图，若|E[<30,则G中至少有一个顶点的度

数小于等于4.（6分）

第3页

5.G=(匕心是一个连通且无圈的图。若G中仅有两个1度顶点，则G可以画

成一条直线。(6分)

6.设/和g都是群(4。)到群(8J)的同态映射，证明(C,。)是(40)的一个子群,

其中。={*|》€/且/(x)=g(x)}(6分)

7.把下列语句翻译为谓词演算公式(每小题3分，共6分)

(1)任何•个集合总存在一个集合方，使得8的基数比彳的基数要大:

(2)有些大学生喜欢所有的网络游戏.

8.已知知识的表示如下；

(1)Vx(P(x)->(X(x)vB(x)))

(2)VrM(x)->e(x))

(3)T/x(P(x)f0(x))

824计算机专业恭础(A)第ISt共6次

第4页

结论：出伊(x)人8(x)),试用归结原理证明之“《6分)

第二部分数据结构(共50分)

一、澧空(每个空格1分，共15分)

LAOE网中的关键路先是⑴,

2.与线性次的，链接存贮方式相比较，畿性表的顺序存储方式的优点是

⑵缺一是一⑶°

3..二叉树的先序和中序遍历序列分别是ABCDEFG,CDBAFEG,则后序遮

历序列是⑷。

4.有向图G=(V,A),其中V={ahcde},

A={<a,b>,<a、c>><d,c>,<d,e>,vb,e>,<c,e>,<c,b>},清给出的一个拓扑序列：

⑸。

5.在一个东头结点的循环链队列中，结点的结构为(daanexO,有指针p指

向队列最后一个元素.若第一个元素出队列，则应执行的操作为：

S=p->next->next；(6).；Irec(s)(free(s)也可以用deletes

6.一棵二叉树中叶子结点数n0和度为2的结点数n2之间满足以下关系：

no=n2+l：一棵满k又树上的叶子结点数如和非叶结点数川之昵满足一

⑺关系。

7.一个深度为k的，具有最少结点数的完全二叉树按层次，(同层次从左向岩)

用自然数依此对结点骗号，则编号最小的叶子的序号是一W_:编号

是i的结点所在的层次号是(9)(根所在的层次号规定为1层)，

8.有关键字序列为：(20,11,12,%23、42,44,36)虻对应的大顶堆为：(10).；

一趟冒泡排序后的序列为：_on_；相序列中的关键字看作权值，构造

哈夫曼树，其带全路径长度为：(⑵。

第5页

9.若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的

结点数是（13）,

10.在无序线索二叉树中，若P炉指结点的右孩子域为孩子指针，则P的后继

结点是-（14）.

11.在B-树中刑除关键字K,若Ki为芾终端结点中的关诞字，则以（,⑸代

替心

二、（15分）笥答题：

设关解字的输入序列为{55,31,11,37,46,39}

1.（5分）从交树开始构造平衡二叉树，画出每加入一个新结点时二叉树

的形态，若发生不平衡，指明需做的平衡旋转类型及平衡旋转的结果，

2.〈4分）画出1.中二叉树的二叉疑表存储结构，并给出对该二叉树进

行中序遍历的婕出序列.

3.《2分）构造一棵二叉排序槌.

4.（4分）画出在2,中的二叉排序树断除31后的二叉排序树，接着再删

824计禄机4・叱用地（A）第2页共6页

除55后的二叉排序树。

三、（10分）对给定的有6个顶点的无向图的邻接矩阵如卜：

1.（3分）画出邻接表存储结构；

2.（2分）画出该无向图；

3.（3分）画出该图的最小生成树：

4.（2分）给出从V,出发的深度优先遍历序列和广度优先遍历序列：

00726oo00

700600400

268665

600600003

QO46oo007

00co537oo

四、（10分）用类-C（类-C++）写出如下算法：

1.（4分）已知源二叉树s,将其复制成另一棵二叉树t.

voidCopyTree（BiTNodes,BiTNodet）

二叉树用二叉锥表存储，存储结构定义为：

typedefstructBiTNode{

Elemtypedata;

structBiTNode*Ichild,*rchild;

}BiTNode/BiTree;

第6页

2.（6分）线性表用单锥表存储，使用尽可能少的存储空间将其元素全部颠

踮倒。statusTum（Linklisl表有头结点

单能表的存储结构定义为：

typedefstructLNode{

ElemTypedata;

structLNode*next;

}LNode,*LinkLisl;

第三部分操作系统（50分）

一.单项选择题（每题1分，共20分）

1.当讣算机区分了管态（系统态）和目态（用户态）指令之后，从管态到目态

的转换是由操作系统程序执行后完成的，而目态到管态的转换号】是由

完成的，

A.硬件B.管态程序

C.用户程序D.中断处理程序

2.作业在执行中发生了缺页中断.经操作系统处理后，应让其执行

指令。

A.被中断的前一条B.被中断的后一条

C..作业的第一条D.作业的最后一条

3.在用户程序中将一个字符送到显示器上显示，使用的是操作系统提供的

接口.

A.系统调用B.库函数C,原语D.例程

824计算机专业基理＜A）第3页共6页

第7页

4.在文件系统中引入“当前目录”的主要目的是

A.方便用户B.提高系统性能C.增强系统安全性D.支持共享访问

5.为了便于上层软件的编制，设备通常需要提供是

A.控制寄存器、状态寄存器和控制命令

B.1/0地址寄存器、工作方式状态寄存得和控制命令

C.中断寄存器、控制寄存器和控制命令

D.控制寄存器、褊程空间和控制违辑寄存器

6.在批处理操作系统控制下实现多道程序并行工作，从系统的角度，主要希望

进入“输入井”的作业能够•

A.响应时间短B,平均周转时间短

oC.服务费用低D.长作业优先得到■务

7.并发进程中与共享变以有关的程序段被称为隘界区.因此这姐并发进程

A.相互间是有交互的B.拥有一个共同的临界区

C.不能修改共享变fit的值D.执行结果不受执行速度的影响

8.采用静态分配赞源策略可以防止死被，这是因为

A.破坏了互斥使用资源的条件B.系统不会出现裾环等待资源的现象

C.提高了资源利用率D.能随时检测资源的使用情况

9.用户“实现按名存取“属于操作系统中的

A.处理器管理B.存储管理

C.文件管理D.设务管理

10.进程的并发性是指

A.一组进程可同时执行

B.每个进程的执行结果不受其它进程的影响

C.每个进程的执行都是可再现的

D.通过一个进程创建出多个进程

II.在下列选项中，不属于造成某进程状态从等待态到就绪态变化的原因是一

A.有更高优先级的进程要运行B.该进程占用的外国设番工作结束

C.该进程等待的货源得到满足D.谈进程等待干预的故障被排除

12.某文件共有4个记录IbL3,采月供接存储结构，每个记录及链接指针占用

一个磁盘块，主存储器中的磁盘馈冲区的大小与磁盘块的大小相等・为了在

Lz和L,之间插入个记录(已经在内存中)，需要进行的磁盘操作有一

A.4次读盘和2次写盘B.4次读盘和1次写盘

C.3次读盘和2次写盘D.3次读盘和1次写盘

13.采用银行家算法可避免死锁的发生，这是因为该算法

A.可抢夺已分配的资源

B.能及时为各进程分配资源

C.任何时刻都能保证每个进程得到所需的货源

D.任何时刻都能保证至少有•个进程可得到所需的全部资源

14.假定一个分时系统允许20个终端用户同时工作•若分配给每个终端用户的

时间片为50亳秒，而对终端用户的每个请求需处理200亳秒给出应答，那

么终端的最长响应时fHl为秒

A.1B.2C.3D.4

15.页式存储管理中，作业运行时，该作业的页表是放在______

R24己■机专业呆此(A)第4页共6页

第8页

o

A.磁盘B.主存系统区C.主存用户区D.用户程序

16.为实现磁盘空间的分配与回收，UNIX采用的是

A.位示图法B.单块链接法C.成组链接法D.索引链接法

17.假设每条磁道被分为8个扇区，每个扇区存放一个记录，处理程序顺序处理

这8个记录L，L2,Lg.每次请求从磁盘上读一个记录，然后对读出的

记录花1ms的时间进行处理，以后再读下一个记录进行处理。磁盘旋转一

周花费16ms（即每读一个扇区需2ms）.若将这8个记录在条磁道上进行优

化分布，则全部处理完这8个记录至少需要ms

A.31B.32C.33D.34

18.虚拟页式存储管理中页表有若干项，当内存中某一页面被淘汰时，可根据其

中哪一项决定是否将该页写回外存.

A.是否在内存标志B.外存地址C.修改标志D.访问标志

19.有一磁盘，共有10个柱面，每个柱面20个磁道，每个盘面分成16个扇区.

采用位示图对其存储空间进行管理.如果字长是16个二进制位，那么位示

图共需字.

A.200B.128C.256D.100

20.校友会的文件系统磁盘库中，“毕业生档案”文件的记录包含的数据项是毕业

年份、身份证号和在校时档案材料.由于各人的档案信息量不同，记录的长

度因人而异，但记录总是先按照毕业年份，然后按身份证序号在磁盘中顺序

存放.使用这个文件的方式是按毕业年份和身份证号快速查出此人的档案材

料.适合这个文件的逻辑结构是

A.顺序结构B.链接结构C.索引结构D.索引顺序结构

第9页

二.解答题（1-5题每空1分，6题每空2分，共20分）

1.在具有N个进程的系统中，允许M个进程（NNMNl）同时进入它们的共享区，

其信号量s的值的变化范围是,处于等待状态的进程数最多是3个.

2.假设某操作系统采用时间片轮转调度策略，时间片大小为100ms,就绪进程

&列的平均长度为5,如果在系统中运行一个需要在CPU上执行0.8s时间的程

序，则该程序的平均周转时间是（3）.平均等待时间是（4）.（不考

虐10情况）

3.在页式虚存管理系统中，设页面大小为26,页表内容如"现访问虚地址：

（233）8«则将虚地址（233）1t变换成物理地址是（5）。

页表：（表中的数均为八进制）_________

页号有效位页帧号辅存块号

0010040

115177

21206

30

4.假定在某动臂磁盘匕刚处理了访问75号柱面的请求，目前正在74号柱面

上读信息，且有如下请求序列在等待访问磁盘;_____________________

请求序列12345678

欲访问柱面号22481931889278156101

写出电梯调屋算法处理时的序列次序（6），写出最短寻找时间优先算法时

处理的时管的移动方向改变了（7）次.

5.假定在一个请求页式存储管埋系统中，某作业J所涉及的页面依次为页面访

824it•算机专业基ili（A）第5页共6次

第10页

问序列：2,3,2,1,5,2,4,5,325,2c分配内存块：3块，采用页面调度算法LRU产

生缺页中断的的数数岱)，采用FIFO产生缺页中断的次数是(9),采用

Clock算法产生缺页中断的次数是J10)c

6.战地指挥官通过无线电不断地向他的两个士兵下达作战指令，但是他必须在

得到所有士兵对前一条指令的“确认”之后才能下达新的指令。使用1\V操作

完成指挥官和士兵之间的协同管理。

structsemaphoreSl=(11)>S2=l;

cobegin

process指挥官：

begin

while<tme){

(⑵：

“⑶；

向上兵1发送指令；

O向士兵2发送指令；

}

end；

process士兵】

begin・.

while(true){

接收指挥官的指令；

(14);

)

end；

process士兵2

begin

while(true){

接收指挥官的指令：

(15);

第11页

Dend：

coend

三.简答题（每题5分，共10分）

1.什么是进程和线程？应用程序可以采用多进程实现，也可以采用多线程实现,

试分析这两种实现方法对应用程序的运行有什么影响？

2.什么是设备无关性？

K，4计mr机专业战砧（A）第6页共6次

第12页

2011年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题

第13页

南京理工大学

2011年硕士学位研究生入学考试试题

科目代码：824科目名称：计算机专业基础(A)满分：150分

注意：①认真阅读答题纸上的注意事项：②所有答案必须写在］答题纸|上,写在本试题纸或

草稿纸上均无效；③本试题纸须随答题纸一起装入试题袋中交回！

数据结构(共50分)

一、填空(每个空格1.5分，共15分)

1.线性表的两种存储方式是(1)和(2).

2.用邻接表表示图时，顶点数为n,边数为e,在邻接表上执行图的深度优先遍历操作时，

时间复杂性(3)

3.对二叉排序树树进行(4)遍历，可以得到树中数据元素的有序序列.

4.由带权为3、9、6、2、5的5个叶子结点构成一棵哈夫曼树，则带权路径长度为

(5).

5.一株二叉树中，度为2的结点有15个，度为I的有30个，则叶子数有(6)个。

6.设待排序的序列为｛48,35,60,13,75,80,26,49｝下面是排序过程：

(1)(48)35601375802649

(2)(3548)601375802649

(3)(354860)1375802649

(4)这一趟排序的序列为(7)。

7.单链表的存储结构定义为：

typedefstructLNode(

ElemTypedata;

structLNode*next:

)LNode,*|JnkList;

下面是单链表的插入和法，请在空格处填入正确的语句。

StatusInsertnode(Linklist&L,inti,ElemTypee)(

//L为无头结点的链表,在第i个元素结点前面插入元素e；

s=(LinkList)malloc(sizeof(LNode));//分配新结点

824计算机专业基础A第I员共7页

第14页

s->data=e;

if(⑻)ls->next=L:L=s：returnOK：}

P=L;j=0；

while((9)>{p=p-〉next;++j;)〃寻找第iT个元素结点

if((10))returnERROR;//i小于1或者大于表长

s->next-p->next;p->next=s:〃插入新结点

returnOK;

"/LinstInsert，

二、简答题(15分)

I.分别画出右图所示二叉树的存储表示：(3分)

(1)顺序表示；

(2)二叉链表表示法；

(3)静态链表表示。

2.对于下图的AOE网(12分)

(1)填写下面的2个表(各2分);

(2)

事件vlv2v3v4v5v6v7

最早发生时间

最迟发生时间

824计算机专业基础A第2页共7页

活动ala2a3a4a5a6a7a8a9alO

最早发生时间

最迟发生时间

（2）列出关键活动（2分）；

（3）忽略图中的权值，将图看成AOE网，写出图的3个拓扑序列（3分）；

（4）将图看成无向图（将图中的有向边看成无向边），画出最小生成树（3分）；

三、（每题5分，共10分）设有一个输入数据的序列是{46,25,78,62,12,37,

70,29},

1.逐个输入各个数据生成的3阶B-树，画出过程；

2.设Hash表表长m:13,选取Hash函数为H（key）=keyMOD11,处理冲突的方法为

“线性探测再散列”，请对输入序列构造Hash表.

四、算法（10分）

二叉树的存储结构如下：

typcdefstructBitNode{

TelemTypedata:

structBitnode*lchild,*rchild;

JBitNode,*Bitree;

用类C写出二叉树中序遍历的非递归算法。

注：算法中可能用到的栈的操作

InitStack（s）：初始一个化栈s

Push（s.p）：将所指向的结点进s栈

Pop（s,p）：S栈顶元素出栈

gettop（s,p）：取s栈顶元素

stackenipty（s）：判栈s是否为空

824计算机专业基础A第3页共7页

第16页

操作系统（共50分）

一、选择题（每题1分，共20分）

1、为了实现多道程序设计，计算机需要有.

A）更大的内存B）更快的外部设备C）更快的CPUD）更先进的终端

2.、进程的—和并发性是两个很重要的属性.

A）动态性B）静态性C）易用性D）顺序性

3、P、V操作是.

A）两条低级进程通信原语B）两条高级进程通信原语

C）两条系统调用命令D）两条特权指令

4、在下列操作系统的各个功能组成部分中，_不需要硬件的支持。

A）进程调度B）时钟管理C）地址映射D）中断系统

5,关于处理机调度，以下说法错误的是—。

A）衡量调度策略的主要指标有：周转时间、吞吐率、响应时间和设备利用率

B）处理机调度可以分为4级：作业调度、交换调度、进程调度和线程调度

C）作业调度时，先来先服务法不利于长作业，最短作业优先法不利于短作业

D）进程调度的算法有：轮转法、先来先服务法、优先级法

6、分段管理提供—维的地址结构.

A）1B）2C）3D）4

7、若一个系统内存有64MB,处理器是32位地址，则它的虚拟地址空间为一字节.

A）2GBB）4GBC）100KBD）64MB

8、操作系统中的工作集模型与—有关。

A）合并存储区中的空白块B）将CPU分配给进程

C）•个进程访问的页面集合D）为进程分配I/O资源

9、成组链法是用于—.

A）文件的逻辑组织B）文件的物理组织

0）文件存储器空闲空间的组织D）文件的目录组织

10、虚拟页式存储管理中页表有若干项，当内存中某一应面被淘汰时，可根据其中哪

决定是否将该页写回外存一=

A）是否在内存标志B）外存地址

C）修改标志D）访问标志

11、有一磁盘，共有10个柱面，每个柱面2（）个磁道，每个盘面分成16个扇区.采用位

824计算机专业基础A笫4贝共7页

图对其存储空间进行管理。如果字长是16个二进制位，那么位示图共需_字。

A）200B）128C）256D）100

12,设备的打开、关闭、读、写等操作是由_完成的。

A）用户程序B）编译程序C）设备分配程序D）设备驱动程序

13-14、静态重定位是在作业的—中进行的，动态重定位是在作业的—中进行的。

A）编译过程B）装入过程C）修改过程D）执行过程

15、如果允许不同用户的文件可以具有相同的文件名，通甯采用—来保证按名存取的安

全.

A）重名翻译机构B）建立索引表C）建立指针D）多级目录结构

16、_是直接存取的存储设备。

A）磁盘B）磁带C）打印机D）键盘、显示终端

17、•个进程被唤醒，意味着该进程—.

A）重新占有CPUB）优先级变为最大

C）移至需待队列之首D）变为就绪状态

18、通道是一种.

A）I/O端口B）数据通道C）I/O专用处理机D）软件工具

19,SPOOLing技术利用于_.

A）外设概念B）虚拟设备概念C）磁带概念D）存储概念

20.从用户的观点看，操作系统是一

A）用户与计算机之间的接口

B）控制和管理计算机资源的软件

C）合理地组织计算机工作流程的软件

D）由若干层次的程序按•定的结构组成的有机体

二、填空题（每空1分，共5分）

I、操作系统提供给编程人员的唯一接口是（1）.

2、将主存空闲区按地址顺序从小到登记在空闲区表中，每次分配时总是顺序吉找空闲区表,

直到找到一个能满足其大小要求的空闲区为止，此种算法称为（2）算也.

3、在页式虚拟存储系统中，选择页面调度算法时应尽最注意减少或避免（3）现象的发生。。

4、页是信息的（4）单位,进行分页是出于系统管理的需要；段是信息的工生单位，分段

是出「用户的需要

三、填空题（共15分，每题I分）

824计算机专业基拙A笫5页共7页

I、请你写出请求页式管理中缺页中断处理时的2种不同的淘汰算法的名称；（1）、（2）。

2.系统为一个有6页的进程分配4个物理块，其页表如下所示（时间单位：滴答），页的大

小为1K,请计算逻辑地址为0X17C8的物理地址.按CLOCK算法为@:按FIFO算法为

（4）；

页号块号装入时间上次引用时间R(读)M（修改）

0712627900

1423026010

2212027211

3916028011

3、若F个等待访问磁盘者依次要访问的磁道为20,44,40,4,80,12,76,移动臂当前

位于40号柱面，则先来先服务算法的平均寻道长度为一®；最短寻道时间优先算法

的平均寻道长度为-

4、在采用分页存贮管理系统中，地址结构长度为18位，其中11至17位表示页号，0至

10位表示页内位移量。主存容量最大可为每块有（8）K。

5、有一个恐龙博物馆和个公园.有m个旅客和n辆车,每辆车只能容纳一个旅客。旅客在

博物馆逛了一会儿，然后排队乘坐旅行车。当一辆车可用时，它我入一个旅客，然后绕公

园行驶任意长的时间。如果n辆车都已被旅客乘坐游玩，则想坐车的旅客需要等待；如果

一辆车己经就绪，但没有旅客等待，那么这辆车等待。使用信号量同步m个旅客和n辆车

的进程.

（1）完善如下程序，在下列（9）-（12）四处填入有关语句

（2）说明每个信号量的物理意义。

visilors=m;cars=n;muiex^l;

pvi()pci()

{repeat{repeat

⑼；p(visitors);

p(mutex);(⑵

geton;start;

travell;run;

getoff;stop;

_____(JO)_____;v(visitors):

(11)；v(mulex);

untilfalse;untilfalse;

)

824计算机专业基础A笫6页共7页

visitors的含义（13）;cars的含义（14）n;mutex的含义（15）

四、简答题（每题5分，共10分）

1、可以通过哪些途径来提高内存的利用率？

2、为什么位示图法适用于分页式存储管理和对磁盘存储空间的管理？如果在存储管理中采

用可变分区存储管理方案，也能采用位示图法来管理空闲区吗？为什么？

离散数学（共50分）

1.（4分）已知集合/={{©},⑴},8={{叫,试求（1）2"：（2）8x2“

2.（6分）把下列语句翻译为谓词演算公式

（1）鱼我所欲，熊掌亦我所欲：

（2）并非所有人均喜欢电脑游戏；

3.（6分）已知A是集合{上的自反和对称关系，试证明，（幻为彳上的等价关系。

4.（6分）7=（匕国是一棵树。试证明（1）7•为二部图；（2）若{匕，匕}是二部图7■的顶点

二分类，且|L|="JE|=m,试证明，"V°。

4

5.（6分）设G=（匕E）是一个简单无向图，|了|=",〃23,若对于任何两个不相邻的顶点

W,VGV,d{u）+d（y）>n.试证明G是连通图。

6.（4分）证明：在一个有限群中，阶大于2的元素个数一定是偶数。

7.（6分）已知一{0},。是有理数集，Vm,neQ'.nAm=-mn,证明（0、A）为群.

6

8.（6分）已知知识的符号表示

（1）3x（尸（x）A^y（D（y）fA（x/）））

（2）Wx（尸（x）->Vy（C（y）->ry）））

结论：Vx（C（x）frQ（x））

试用HORN子句逻辑程序证明之。

9.（6分）已知G=亿E）是一个简单平面图，Il|E|<30.试证明至少有一个顶点的度数小

于或等于4。

824计算机专业基础A第7央於7页

第21页

2010年南京理工大学计算机科学与工程学院824计算机专业基础A考研真题

第22页

南京理工大学

2010年硕士学位入学考试试题

试题编号：2010006020

考试科目：计算机专业基础(满分150分)

(AJ

考生注意：

(1).所有答案(包括填空题)按试题序号写在答题纸上，写在试卷上不给分

(2).本试卷共有三部分组成，其中第一部分为“为据结构”，第二部分为“操作系统”,

第三部分为“离散数学”,每部分各50分.

第一部分数据结构(共50分)

一、填空(每个空格1.5分，共15分).

1.已知一个带头结点的单链表L,其存储结构为：

typedefstructLNode{

ElemTypedata;

structLNode*next;

}LNode,*LinkList;

下面的算法是在L中删除其最大值结点(表中有唯一的最大值)的算法，请

在空格处填入正确的语句。

voidDeleteMaxNode(LinkList&L){

pre=L,p=pre->next,maxp=p,maxpre=pre;

whilef(1)){

if(⑵)

{maxp=p;

maxpre=pre;

}

pre=p;

(3):

}//while

⑷：

free(maxp)：

}//DeleteMaxNode

2.设哈希表长为14,哈希函数是H(key)=key%ll,表中已有数据的关键字为

16,28,40,52共四个，现要将关键字为61的结点加到表中，用二次探测再

散列法解决冲突，则放入的位置是(5):用线性探测再散列法解决冲突，

则放入的位置是(6).

3.在一棵二叉树中，度为1的结点有40个，总的结点数为99,则二叉树中叶

子结点数共有(7).

4.有序表为{2,5,9,12,16,20,26,28,32,36,40,43,45),在该表中用二分法查

找值为37的数据，比较(8)次,可以确定查找失败。

-共7页第1页

第23页

5.对序列{50,37,66,98,75,12,26,49}进行树型选择排序，选出12的二

叉树为⑼，接着再选出26的二叉树为（10）.

二、简答题（23分）

1.己知有向图G有6个顶点（顶点号从1计），弧集E如下：（其中弧后面冒号

后数表示弧上的权）

E={<1,2>:12,<1,4>:15,<1,5>:8,<2,3>:13,<4,3>:25,<4,6>:5,<5,4>:5,

<5,6>:20,<6,3>:2}

请回答下面的问题：

（1）（3分）画出该有向图。•

（2）（3分）画出该图邻接表存储结构.

（3）（3分）按Dijkstra算法，给出从顶点1到其余顶点的最短路

径及路径长度。

（4）（3分）将图看成无向图（将图中方向去掉），画出该无向图的最

小生成树。

2.已知关键字的集合（46,55,13,42,94,5,17,70）

（1）（3分）请按给出的序列构造一棵二叉排序树（不要构造过程），

■并给出该二叉树排序树的深度；

（2）（3分）请对（1）中的二叉树进行先、中、后序遍历，分别给

出遍历结果；

（3）（3分）请给出该关键字集合的大顶堆；

（4）（2分）如果对该关键字集合进行起泡排序，请给出第一趟排

序后关键字的序列.

三、算法（共12分）

二叉树的存储结构如下：

typedefstructBitnode{

TelemTypedata;

structBitnode*lchild,*rchild;

}Bitnode,*Bitiee;

请编写按层次顺序（同一层自左至右）遍历二叉树的算法（6分）

voidLayerOrder（Bitree,T）。所用队列操作如下：

InitQueue（Q）〃队列初始化

EnQueue（Q,T）//T入队列，将T插入到队尾

QueueEmpty（Q）//队列判空操作

DeQueue（Q,p）〃出队列，将队头元素赋值给p

如果队列用循环队列实现，其存储结构为：

#defineMAXQSIZE100

typedefstruct{

共7页第2页

第24页

QelemType+base;

intfront;

intrear;

}SqQueue;

请实现函数EnQueue(Q,T)(3分)和DeQueue(Q,p)(3各)

第二部分操作系统（共50分）

一、单项选择题（每小题1分，共20分）

1.关于多道程序设计的论述中不正确的是（）

A）.能提高资源使用效率

B）能增加单位时间的算题量

0对每个计算问题的计算时间可能要延长

D）对每个计算问题的计算时间不会延长

2.当一个进程独占处理器顺序执行时，具有两个特性（）

A）封闭性和可再现性B）实时性和可靠性

0交互性和可再现性D）封闭性和实时性

3.某系统中，每个进程在I/O阻塞之前的运行时间为T,一次进程切换的系统开

销时间为S,若采用时间片长度为Q的时间片轮转法，并且S<Q<T,则CPU的利

用率是（）

A）T/（T+S）B）Q/（Q+S）C）50%D)Q/(T+S)

4.把并发进程中与共享变量有关的程序段称为（）

A）共享数据区B）临界区

C）公共子程序D）共享程序

5.有关并发进程的阐述中，下正确的说法是（）

A）进程的执行速度不能由,进•程,自己来控制

B）进程的执行速度与进程能占用处理器的时间有关

0进程的执行速度与是否出现中断事件有关

D）任何两个并发进程之间均存在着相互制约关系

6.有n个进程竞争某共享资源，系统允许每次最多m个进程同时使用该资源,

若用PV操作管理时信号量的变化范围为（）

A）[m,（m+n）]B）[n,（m+n）]

C）（（m-n），m]D）[（m-n）,n]

7.特权指令（）执行.

A）只能在目态下B）只能在管态下

0可在管态也可在目态下D）从目态变为管态时

8.造成某进程状态从运行态到等待态的变化原因不可能是（）

A）该进程运行中请求启动了外围设备

B）该进程在运行中申请资源得不到满足

共7州第3页

第25页

C）分配给该进程的处理器时间用完

D）该进程在运行中出现了程序错误故障

9.在五个哲学家就餐问题中，为保证其不发生死锁，可限定同时要求就餐的人数

最多下单耳：（）

A）24B）3个C）4个D）5个

10.已知作业的周转时间=作业完成时间一作业的到达时间。现有三个同时到达的

作业JI,J2和J3,它们的执行时间分别是TLT2和T3,且TKT2VT3。系

统按单道方式运行且采用短作业优先算法，则平均周转时间是（）.

A）T1+T2+T3B）（T1+T2+T3）/3

C)Tl+2*T2/3+T3/3D)Tl/3+2*T2/3+T3

11.作业8：00到达系统，估计运行时间为1小时，若10：00开始执行该作业,

其响应比是（）

A)2B)103D)0.5

12.让多个用户作业轮流进入内存执行的技术称为（）

A）覆盖技术B）对换技术C）移动技术D）虚存技术

13.可以采用静态重定位方式转换地址的管理内存方案是（）

A）页式管理B）页式虚拟管理

0可变分区管理D）固定分区管理

14.在以下存贮管理方案中，不适用于多道程序设计系统的是（）

A）单用户连续分配B）固定式分区分配

0可变式分区分配D）页式存贮管理

15.现有如下请求队列：8,18,27,129,110,186,78,147,41,10,64,12：

用最短寻道时间优先算法处理所有请求，移动的总柱面数（）。,假设磁

头当前位置在100。

A）263B）264C）265D）266

16.在页式虚存管理中，（）有一个页表.

A）整个主存空间B）整个虚存空间

0每个作业D）每个用户文件

17.在页式存储管理中，假定访问主存的时间为200毫微秒，访问高速缓冲存储

器的时间为40亳微秒,高速缓冲存储器为16个单元,查快表的命中率为90%,

则按逻辑地址转换成绝对地址进行存取的平均时间为（