快速查题-408计算机专业基础综合试题

20. 单周期处理器中所有指令的指令周期为一个时钟周期。下列关干单周期处理器的叙述中，错误的是
A.可以采用单总线结构数据通路
B.处理器时钟频率较低
C.在指令执行过程中控制信号不变
D.每条指令的CPI为1

41.（15分）已知无向连通图G由顶点集V和边集E组成，IEI>0，当G中度为奇数的顶点个数为不大于2的偶数时，G存在包含所有边且长度为IEI的路径（称为EL路径）。设图G采用邻接矩阵存储，类型定义如下;
typedef struct //图的定义
int numVertices,numEdges;
//图中实际的顶点数和边数
char Vericeslist[ MAXV ];
//顶点表。MAXV为已定义常量
int Edge[ MAXV ][ MAXV];
// 邻接矩阵
|MGraph;
请设计算法∶int IsExistEL（MGraph G），判断 G是否存在 EL 路径，若存在，则返回1，否则，返回 0。要求：
（1）给出算法的基本设计思想。
（2）根据设计思想，，采用C或C++语言描述算法，关键之处给出注释。
（3）说明你所设计算法的时间复杂度和空间复杂度。

21. 下列关于总线设计的叙述中，错误的是
A.并行总线传输比串行总线传输速度快
B.采用信号线复用技术可减少信号线数量
C.采用突发传输方式可提高总线数据传输率
D. 采用分离事务通信方式可提高总线利用率

42.（8分）已知某排序算法如下：
void cmpCountSort(int a[],int b[],int n)
{ int i,j,* Count;
count =(int *)malloc(sizeof( int)* n);
//C++语言∶count = new int[n];
for(i= 0;ifor(i = 0;ifor(j = i+1;jif( a[i]else count[i]++;
for(i = 0;ifree(count); // C++语言∶delete count;
}
请问答下列问题。
（1）若有 int a[]={25，-10，25，10，11，19，b[6];，则调用cmpCountSort（a，b，6）后数组 b中的内容是什么?
（2）若a中含有 n个元素，则算法执行过程中，元素之间的比较次数是多少?
（3）该算法是稳定的吗?若是，则阐述理由;否则，修改为稳定排序算法。

22. 异常是指令执行过程中在处理器内部发生的特殊事件，中断是来自处理器外部的请求事件。下列关于中断或异常情况的叙述中，错误的是
A."访存时缺页"属于中断
B."整数除以0"属于异常
C."'DMA传送结束"属干中断
D."存储保护错"属于异常

43.（15分）假定计算机 M 字长为 16位，按字节编址，连接CPU和主存的系统总线中地址线为 20 位、数据线为8位，采用 16 位定长指令字，指令格式及其说明如下：
其中，op1~op3为操作码，rs、rt 和 rd 为通用寄存器编号，R「r]表示寄存器r的内容，imm 为立即数，target 为转移目标的形式地址。请回答下列问题。
（1）ALU的宽度是多少位? 可寻址主存空间大小为多少字节?指令寄存器、主存地址寄存器（MAR）和主存数据寄存器（MDR）分别应有多少位?
（2）R 型格式最多可定义多少种操作?I型和J型格式总共最多可定义多少种操作?通用寄存器最多有多少个?
（3）假定 opl为0010和 0011时，分别表示带符号整数减法和带符号整数乘法指令，则指令01B2H的功能是什么（参考上述指令功能说明的格式进行描述）?若1、2、3 号通用寄存器当前内 容分别为 B052H、000811、0020H，则 分别执行指令01B2H 和 01B3H后，3号通用寄存器内容各是什么? 各自
结果是否溢出?
（4）若采用1型格式的访存指令中 imm（偏移量）为带符号整数，则地址计算时应对 imm 进行零扩展还是符号扩展?
（5）无条件转移指令可以采用上述哪种指令恪式?

23. 下列关于批处理系统的叙述中，正确的是
Ⅰ.批处理系统允许多个用户与计算机直接交互
Ⅱ.批处理系统分为单道批处理系统和多道批处理系统
Ⅲ.中断技术使得多道批处理系统的I/O设备可与CPU并行工作
A.仅Ⅱ、Ⅲ
B.仅Ⅱ
C.仅Ⅰ、Ⅱ
D.仅Ⅰ、Ⅲ

44.（8分）假设计算机 M的主存地址为24位，按字节编址;采用分页存储管理方式，虚拟地址为 30位，页大小为4 KB;TLB采用 2路组相联方式和 LRU替换策略，共8组。请回答下列问题。
（1）虚拟地址中哪几位表示虚页号?哪几位表示页内地址?
（2）已知访问 TLB 时虚页号高位部分用作 TLB 标记，低位部分用作 TLB 组号，M 的虚拟地址中哪几位是 TLB 标记?哪几位是TLB 组号?
（3）假设 TLB 初始时为空，访问的虚页号依次为 10、12、16、7、26、4、12和 20，在此过程中，哪一个虚页号对应的 TLB表项被誉换? 说明理由。
（4）若将 M 中的虚拟地址位数增加到 32位，则 TLB 表项的位数增加几位?

24.某单CPU系统中有输入和输出设备各1台，现有3个并发执行的作业，每个作业的输入、计算和输出时间均分别为2ms、3ms和4 ms，且都按输入、计算和输出的顺序执行，则执行完3 个作业需要的时间最少是
A. 15 ms
B. 17 ms
C. 22 ms
D.27 ms

45.（7分）下表给出了整型信号量S的 wait（）和 signal（）操作的功能描述，以及采用开/关中断指令实现信号量操作互斥的两种方法。
功能描述
Semaphore S;
wait(S){
while(S<= 0);
S = S-1;
}
方法1
Semaphore S;
wait(S){
关中断;
while(S<= 0);
S = S-1;
开中断;
}
signal(S){
关中断;
S=S+l;
开中断;
}
方法2
Semaphore S;
wait(S){
关中断;
while(S<= 0)}
开中断;
关中断;
{
S=S-1;
开中断;
}
signal(S){
关中断;
S=S+1;
开中断;
}
请回答下列问题。
（1）为什么在 wait（）和 signal（）操作中对信号量S的访问必须互斥执行?
（2）分别说明方法 1 和方法 2是否正确。若不正确，请说明理由。
（3）用户程序能否使用开/关中断指令实现临界区互斥?为什么?