[实用参考]2014年东南大学计算机专业考研真题

[重点实用参考文档资料]

半以上的元素与G相同，则称G是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的内容，[G]表示存储单元G的内容，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=yG8”，若变量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=MaG-Allocation A P0 P1 P2 P3 6 1 2 1 MaG B 0 7 3 6 C 1 5 5 5 D 2 0 6 3 A 4 1 1 0 Allocation B 0 1 0 6 C 0 0 5 3 D 1 0 4 3 A 2 0 1 1 Need B 0 6 3 0 C 1 5 0 2 D 1 0 2 0 （3）不是安全状态，因为找不到安全序列，也就是找不到某种进程推进顺序，使得每个进程都可顺序地完成。 43.

Semaphore empty = n, full = -m, muteG = 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 8 2 3 17 4 5 19 6 12 7 13 8 20 9 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(chara[],intn) {

int count = 0; int mainSub = 0;

char mainElement = a[0]; count++;

for (int i=1;i

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

count--; if (count == 0) { }

mainElement = a[mainSub++]; count++;

[重点实用参考文档资料]