2014年东南大学计算机专业考研真题

本站小编免费考研网/2018-01-06

2014年东南大学计算机专业考研真题

一、选择题(共80分)

1.下面关于进程的描述中，不正确的是

A进程是动态的概念 B进程就是一个独立的程序

C进程可以并发执行 D进程可由程序、数据和进程控制块描述

2.在多对一的线程模型中，一个多线程中的某个线程执行一个需阻塞的系统调用时，下列选项中正确的是

A整个进程都将被阻塞 B该进程的其他线程仍可继续执行

C该阻塞线程将被撤销 D该阻塞线程将阻塞直到进程退出

3.采用多道程序设计技术能提高整个计算机系统的效率，其基本条件是

A硬盘容量大 B处理器执行指令速度快

C外围设备多 D系统具有处理器与外设并行工作的能力

4.下列指令中，不是特权指令的是

A I/O指令 B读取当前时钟

C设置基址寄存器 D关闭中断

5.在存储管理中，外部碎片指的是

A存储分配完成所剩的空闲区 B没有被使用的存储区

C不能被使用的存储区 D未被使用，又暂时不能使用的存储区

6.进程所请求的一次打印输出结束后，进程状态会发生的变化是

A从运行态变成就绪态 B从运行态变成等待态

C从等待态变成就绪态 D从就绪态变成运行态

7.关于Round Robin调度算法，以下说法正确的是

I.同样的情况下，时间片越大，平均周转时间越小

II.FCFS算法是Round Robin算法的一种特殊情况

III.只有实现了定时的机制，才能实现Round Robin算法

IV.Round Robin属于非抢占调度算法

A仅I和II B仅II和III

C仅III和IV D仅I和IV

8.物理内存和虚拟存储空间相比，其大小关系是

A前者比后者大 B前者比后者小

C两者一样大 D不一定

9.临界区指的是

A一段内存共享区域 B一个共享变量

C访问临界资源的一段程序 D一种同步机制

10.为使虚拟存储系统有效发挥其预期作用，所运行的程序应具有的特性是

A程序应比较大 B程序应该具有良好的局部性

C程序应含有多个I/O操作 D程序应含有较多的动态分配内存工作

11.下列说法正确的是

I.当发现系统中存在抖动(Thrashing)时，应更换一块更大的磁盘用于页面置换

II.内存分页管理方式不会产生外部碎片

III.磁盘访问时间主要是由旋转时延和传输时延组成

IV.FCFS算法可用于实现磁盘调度

A仅I和II B仅III和IV

C仅II和IV D仅I和III

12.一个请求分页存储管理系统中，假设分配给某作业的页框(Frame)数为3，该作业的页引用序列为0,2,1,3,0,2,4,0,2,1,3,4，所有的页框初始时都为空，分别采用最近最少次数使用(LRU)和最优(OPT)页面置换算法时，产生页面失效(Page Fault)的次数分别是

A 10和7 B 9和8

C 9和7 D 7和4

13.单处理器系统中有n(n>2)个进程，若进程调度程序当前没有执行，则以下情形不可能发生的是

A有一个运行进程，没有就绪进程，剩下的n-1个进程处于等待状态

B有一个运行进程和一个就绪进程，剩下的n-2个进程处于等待状态

C没有运行进程，有一个就绪进程，剩下的n-1个进程处于等待状态

D有一个运行进程和n-1个就绪进程，没有进程处于等待状态

14.关于短作业优先(SJF)调度算法，下列说法正确的是

I.SJF算法能得到最优的平均等待时间

II.SJF算法能得到最优的平均响应时间

III.SJF算法可能产生”饥饿”(Starvation)现象

IV.SJF算法是一种实际系统中常用的CPU调度算法

A仅I和III B仅II和IV

C仅I和IV D仅II和III

15.下列选项中，不是文件系统应具备的功能的是

A对文件按名存取 B实现对文件的各种操作

C提高磁盘的I/O速度 D访问数据时实现从逻辑结构到物理结构的转换

16.下列文件的物理结构中，可能带来外部碎片问题的是

A连续结构 B链接结构

C索引结构 D Hash结构

17.下列选项中，不属于算法的主要特征的是

A有穷性 B可行性

C确定性 D可读性

18.若一个栈S的入栈序列为0,1,2,3,4,5,6,7,8,9，对于下列序列，S的可能出栈序列是

I.5,6,8,7,2,1,4,3,0,9 II.0,2,1,6,5,8,7,4,3,9

III.2,0,1,4,3,7,8,6,5,9 IV.6,5,7,8,4,3,1,2,9,0

A仅I B仅II

C仅I和III D仅II和IV

19.对任意一个给定的二叉树进行前序、中序和后序遍历可得到三个遍历序列。下列有关这三个遍历序列的叙述中，正确的是

I.叶子结点在三个遍历序列中先后次序是一样的

II.兄弟结点在三个遍历序列中先后次序是一样的

III.父子结点在三个遍历序列中先后次序是一样的

IV.祖先和子孙结点在三个遍历序列中先后次序是一样的

A仅I和II B仅III和IV

C仅I和III D仅II和IV

20.下列选项中，不可能是任何二叉搜索树的前序遍历序列的是

A 4,2,3,5,6,7 B 4,3,2,7,6,5

C 6,5,4,2,3,7 D 6,5,3,4,2,7

21.用n(n大于等于2)个权值均不相同的字符构成哈夫曼树，下列关于该树的叙述中错误的是

A树中一定没有度为1的结点

B该树一定是一棵完全二叉树

C树中两个权值最小的结点一定是兄弟结点

D树中任一非叶子结点的权值一定不小于其任一子节点的权值

22.无向图G如下图所示，下列选项中，不可能是G的广度优先遍历序列的是

A 0,1,2,3,4,5

B 0,2,1,3,4,5

C 0,1,2,3,5,4

D 0,3,2,1,5,4

23.下列关于图的叙述中，正确的是

A强连通有向图的任何顶点到其他所有顶点都有弧

B图与树的区别在于图的边树大于等于顶点数

C有向图的遍历不可采用广度优先遍历方法

D带权无向图G中，若所有边的权值均不相同，则G的最小生成树是唯一的

24.若排序过程中出现这种情况，在最后一遍开始之前，所有元素都不能保证在其最终的位置上，则采用的排序算法是

A冒泡排序 B堆排序

C快速排序 D直接插入排序

25.若对15个元素进行快速排序，则元素的比较次数至少是

A 26 B 34 C 52 D 78

26.对序列14,9,7,10,20,1,5进行排序，若第一趟后的数据排列为5,9,1,10,20,7,14，则采用的排序算法是

A选择排序 B归并排序 C希尔排序 D冒泡排序

27.对一个长度为16的有序表，若采用折半查找法查找一个表中不存在的元素，则比较次数最多的是

A 7 B 6 C 5 D 4

28.在一棵初始为空的AVL树T中依次插入关键码1,2,3,4,5,6,7的结点后，T的根结点的关键码是

A 3 B 4 C 5 D 6

29.冯·诺依曼模型计算机中存放指令地址的寄存器是

A PC B IR C MAR D MDR

30.某计算机中各种指令的CPI平均为8，CPU采用5级流水方式执行指令，流水线每拍为2个时钟周期。执行程序A时，共执行2000条指令，此时流水线的加速比约为

A 4.0 B 5.0 C 8.0 D 10.0

31.下列奇偶校验码中，若有一个存在错误，则它是

A 10001001 B 01001101 C 11010110 D 10000101

32.某16位计算机中，存储器按字节编址，整数用补码表示。数据在存储器中采用小端次序存放，若X,Y,Z为整数，且X=-41，Y=+75，Z=X-Y，Z存放在地址为A和A+1存储单元中，则存储单元A的内容是

A 00H B 74H C 8CH D FFH

33.某CPU中，若进位/借位标志为CF，零标志为ZF，符号标志为SF(0表示正)，溢出标志为OF，uA和uB为无符号整数，则判定uA小于等于uB的条件是

A SF=1 B SF+ZF=1 C CF=1 D CF+ZF=1

34.目前，内存条通常由DDR2 SDRAM或DDR3 SDRAM芯片组成，该芯片为多体存储器，能够在总线时钟上升沿、下降沿都传送数据。相对基本的SDRAM芯片，该类芯片提高性能采用的主要方法是

A增加数据引脚数量 B减小存储元和I/O电路延迟

C交叉编址，并行或交叉存取 D顺序编址，并行或交叉存取

35.下列虚拟存储器的叙述中，错误的是

A虚拟存储器有自己的存储阵列 B虚拟存储器需按程序逻辑地址访问

C虚拟存储的慢表放在主存中 D虚拟存储的快表结构类似于Cache

36.下列选项中，与CPU主时钟周期相同的是

A CPU周期 B机器周期 C节拍周期 D节拍脉冲

37.某同步总线的总线宽度为16位，每次数据传输需2个总线时钟周期，若希望总线带宽达到1064MB/s，则总线时钟的频率至少是

A 133MHz B 266MHz C 532MHz D 1064MHz

38.下列总线仲裁方法中，仲裁过程不需要主设备参与的是

A链式查询 B独立请求 C分布式仲裁 D计数器定时查询

39.某磁盘有1800个磁道，每个磁道有120个扇区，每个扇区可以记录2KB的信息，若磁盘机的转速为5400转/分钟，则该磁盘的最大数据传输率为

A 2.73MB/s B 19.33MB/s C 20.60MB/s D 22.12MB/s

40.Intel 8086 CPU采用向量方式处理中断和异常，支持多个可屏蔽中断向量，可以屏蔽中断请求及响应引脚为INTR及，则CPU采用的可屏蔽中断源识别方法是

A软件查询 B串行判优 C并行判优 D无法确定

二、综合应用题(41~47题，共70分)

41(9分)页式内存管理系统中，逻辑地址为24位，页面大小为512B，采用两极页表结构，页表中的每一项占2B。该系统中访问一次内存的时间为250ns，不考虑其他环节所用的时间。请回答下列问题：

1) 逻辑地址中，用于表示外层页表(outer page table)、页号和页内偏移量的位数分别是多少？

2) 简要描述该页式内存管理系统的逻辑地址到物理地址的转换过程

3) 访问一个逻辑地址需要多长时间

42(9分)一个系统中共存在A、B、C、D四类资源，有P0到P3四个进程，系统在某一时刻的资源分配情况如下表所示：

	Max				Allocation				Available
	A	B	C	D	A	B	C	D	A	B	C	D
P0	6	0	1	2	4	0	0	1	3	2	1	1
P1	1	7	5	0	1	1	0	0
P2	2	3	5	6	1	0	5	4
P3	1	6	5	3	0	6	3	3

请回答下列问题：

1) 死锁产生的四个条件分别是什么？

2) 需求(Need)矩阵的内容是怎样的？

3) 系统是否处于安全状态？为什么？

43(10分)假设缓冲区buf最多可存放n个数据，进程P1往buf中写数据，当buf中数据多于m个时允许进程P2从中取数据，m小于n，均为正数，试用信号量实现P1和P2之间的同步

44(10分)设散列表HT的存储空间是一个从0开始的一位数组，装填(载)因子为0.6，散列函数为H(key)=key MOD 7。现将关键字序列(8,19,12,17,13,20)散列存储到HT中，处理冲突采用线性探测法。回答下列问题：

1) 请画出所构造的散列表

2) 分别计算等概率的情况下，查找成功和查找不成功的平均查找长度

45(11分)令A是具有n个元素的一维数组，x是A中的一个元素，若A中有一半以上的元素与x相同，则称x是A的主元素。例如：若数组A为{‘a’，‘c’，‘a’，‘b’，‘a’，‘d’，‘a’}，则存在主元素a；若数组A为{‘a’，‘d’，‘b’，‘c’，‘b’，‘d’，‘a’}，则A中不存在主元素。试设计算法，判断A中是否存在主元素，若存在则给出其主元素。请简要说明算法的设计思想，用C或C++语言给出算法，并请说明算法的时间、空间复杂度

46(10分)某计算机主存按字节编址、地址空间为32位；Cache数据区容量为1MB，采用4路组相联映射方式、LRU替换算法、写回法写策略，块大小为32B。请回答下列问题：

1) Cache共有多少个组？Cache行(块)包含目录表项及块数据区两部分，Cache行的大小至少为多少位？

2) 若CPU访存地址为00463050H，命中时Cache的组号是多少？命中时Cache行的标记字段的值是多少？(用二进制表示)

3) 某C语言程序段为“int i , A[512]; for (i = 0; i < 512; i+=2); A[i]+=A[i+1];”，若编译时sizeof(int)=4，i分配在寄存器中，A分配在基址为00000060H的连续主存空间中。执行该程序段时，访问数组A共多少次？若仅考虑数组A的访存情况，Cache的命中率是多少？写出计算过程。

47(11分)某8位计算机的存储器按字节编址，地址空间为8位。下图所示的是该机指令系统的指令格式，以及CPU内部与数据通路相关的结构。

指令格式中，格式1指令功能为：Rd←(Rd) OP1 (Rs) 或 Rd←(Rd) OP1 [(Rs)]，Rs、Rd表示寄存器，(Ry)表示寄存器Ry的内容，[x]表示存储单元x的内容，OP1=000、001、010分别表示加法、算术左移、算术右移操作，移位位数放在Rs中。格式2指令为双字长指令，OP2=1000、1001、1010分别表示赋值、取数、存数操作，Rs/Rd表示源或目的寄存器，Imme/Address表示立即数或存储单元结构。

CPU结构中，数据通路为单总线结构，R0~R3为通用寄存器(编号为0~3)，寄存器间的数据传送操作和ALU运算操作均需一个时钟周期，访存操作采用同步控制方式、需2个时钟周期，请回答下列问题：

1) 若(IR)=A8H，写出该指令的操作、源操作数寻址方式

2) 某C语言语句为“y=y*8”，若变量y的存储单元地址为23H，写出实现该语句功能的指令串。(通用寄存器可任意使用)

3) CPU取指并译码后，若IR中指令为：R3←(R3)+[(R2)]，则该指令执行阶段至少需要几个时钟周期？(可以用文字或微操作步序列描述)

答案：（若是发现答案中有错的或者不确定的最好跟其他同学多讨论讨论~）

1-10 B A D B D C B D C B

11-20 C A C A C A D B A D

21-30 B C D D B C C B A A

31-40 B C D C A C D B D B

41.

42.

（1）互斥、循环等待、占有并等待（请求和保持）、非抢占（不剥夺）

（2）Need=Max-Allocation

	Max				Allocation				Need
	A	B	C	D	A	B	C	D	A	B	C	D
P0	6	0	1	2	4	0	0	1	2	0	1	1
P1	1	7	5	0	1	1	0	0	0	6	5	0
P2	2	3	5	6	1	0	5	4	1	3	0	2
P3	1	6	5	3	0	6	3	3	1	0	2	0

（3）不是安全状态，因为找不到安全序列，也就是找不到某种进程推进顺序，使得每个进程都可顺序地完成。

43.

Semaphore empty = n, full = -m, mutex = 1;

44.

装填因子0.6，关键字个数6个，则散列表长度为6/0.6=10，地址为0~9

8%7=1，19%7=5，12%7=5，17%7=3，13%7=6，20%7=6

散列表为：

0	1	2	3	4	5	6	7	8	9
	8		17		19	12	13	20

ASLsucc=(1+1+2+1+2+3)/6=10/6=5/3

ASLunsucc=(1+2+1+2+1+5+4)/7=16/7

45.

char function(char a[],int n)

{

int count = 0;

int mainSub = 0;

char mainElement = a[0];

count++;

for (int i=1;i<n;i++)

{

if (a[i] == mainElement) count++;

else

{

count--;

if (count == 0)

{

mainElement = a[mainSub++];

count++;

}

count = 0;

for (int i=0;i<n;i++)

if (a[i] == mainElement)

count++;

if (count >n/2)

return mainElement;

else

return '\0';

}

46.

（1）Cache地址为：组号13位、组内块号2位、块内地址5位。则Cache有2的13次方个组=8192个组。

主存地址为：区号14位、区内块号13位、块内地址5位。Cache行由目录表项和数据区两部分，目录表项位数为：14+2（LRU位）+1（标记位）+1（写回法脏位）=18位。

数据区为32*8位=256位。则Cache行大小至少有18+256=274位。

（2）0000 0000 0100 0110 0011 0000 0101 0000，则10 0011 0000 010为命中组号，Cache行标记字段的值为0000 0000 0100 01

（3）A[i]+=A[i+1]等价于A[i]=A[i]+A[i+1]，则一次循环需要访问主存三次。for(i=0;i<512;i+=2)可得循环次数为512/2=256次，则该程序段共访存256*3=768次。由sizeof(int)=4，可得存储一个int型数据需要4B。由一个Cache块大小为32B，可得一个Cache块可以存放32/4=8个int型数据。int A[512]定义了512个int型数据，则存储A[512]共需要512/8=64个Cache块。则命中率为1-64/768=704/768=91.7%。

47.

（1）A8H=1010 1000，1010对应为OP2的存数操作，Rs/Rd=10，则源操作数的寻址方式为寄存器寻址。

（2）y=y*8，思路：先将y所在单元存入R0，将R0左移3位，再将R0放入y所在单元

1001 00 00 ；取数操作

0010 0011 ；地址23H，这两步相当于R0←[23H]

1000 01 00 ；赋值操作

0000 0011 ；3，这两步相当于R1←03H

001 0 00 01 ；R0算术左移(R1)位，相当于R0<<(R1)

1010 00 00 ；存数操作

0010 0011 ；地址23H，这两步相当于[23H]←(R0)

（3）

R2→MAR，1→Read 1T

R3→Y， M(MAR)→MDR 2T

MDR→ALU，ADD→ALU，ALU→Z 1T

Z→R3，1→End 1T

总共需要5个时钟周期