1.在多对一的线程模型中，一个多线程中的某个线程执行一个需阻塞的系统调用时，下列选项中正确的是
A整个进程都将被阻塞 B该进程的其他线程仍可继续执行
C该阻塞线程将被撤销 D该阻塞线程将阻塞直到进程退出
2.进程可能发生调度的时机为
Ⅰ.正在执行的进程时间片用完
Ⅱ.正在执行的进程提出I/O请求进入等待
Ⅲ.系统创建新进程
Ⅳ.等待从硬盘中读数据的进程获得了数据
A Ⅰ B Ⅱ Ⅳ C Ⅰ Ⅲ Ⅳ D Ⅰ Ⅱ Ⅲ Ⅳ
3.某分段系统，地址为32位，段号为8位，最大段长为多少位
A 2^8 B 2^16 C 2^24 D 2^32
4.关于临界区，正确的是
A 访问临界资源的那段代码
B 访问共享资源的那段代码
C 用于系统同步的那段代码
D 用于系统互斥的那段代码
5.访问主存的时间为100ns，访问快表的时间为10ns，TLB命中率为0.9，平均访问时间为
A 119ns B 130ns C 120ns D 125ns
7.有一个链接结构的文件，其中被链接的每个物理块存放一个逻辑记录和一个链接指针。目前，该文件中共存放了1、2、3、4、5五个逻辑记录。假设对应于该文件的目录项已经在主存储器中，那么完成删除记录4最少需访问磁盘几次
A 1 B 2 C 3 D 5
连续分配和非连续分配方式中，哪些产生内部碎片哪些产生外部碎片问题
13.通过破坏产生死锁的必要条件之一，可以保证死锁的不发生，资源有序分配破坏的是
A 互斥条件 B 不剥夺条件 C 占有并等待条件 D循环等待条件
14.有关银行家算法正确的描述为
Ⅰ.银行家算法是死锁预防
Ⅱ.银行家算法是死锁避免
Ⅲ.银行家算法中不安全状态，一定会是死锁
Ⅳ.银行家算法中不安全状态，未必是死锁
15.请求分页管理中，逻辑地址为32位，页面大小为8192B，两级页表，每一个页表项2B。则外层页表、内层页表、页内偏移分为占多少位
A 10,10,12 B 6,13,13 C 7,12,13 D 7,13,12
16.有关颠簸的描述正确的有
Ⅰ.颠簸时，CPU利用率迅速下降
Ⅱ.颠簸时，应该增加进程，使CPU利用率提高
Ⅲ.颠簸时，通过挂起进程，可以缓解内存
Ⅳ.可变分配中的局部置换，不会发生颠簸现象
17.一个n个元素的数组，左边全是1右边全是0，没有其他元素，问要找出1的个数，最佳的算法的时间复杂度是
A logn B n C根号n D nlogn
18.a[10][10][15]，每个数组元素占两个主存单元，问a[2][3][5]起始地址
A 710 B 720 C 730 D 740
19.abcde依次入栈，问dc开头的出栈序列共有几个
A 3 B 4 C 5 D 6
20.哈夫曼树，不存在相同数值叶结点，错误的是
A树中不存在度为1的节点
B父层节点的数值不小于下一层节点数值
C这是一颗完全二叉树
D树中权值最小的两个节点一定是兄弟节点
21.下列序列可能是二叉排序树的前序序列的是
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
22.无向图G如下图所示，可能是G的广度优先遍历序列的是
A a,b,e,c,f,d
B a,c,e,b,d,f
C a,c,b,e,f,d
D a,e,b,c,f,d
23.用Prim算法(从顶点V0开始)和Kruskal算法构造下图的最小生成树，最后添加的一条边是
A B C D
24.如果缩短下图中的活动时间从而使整个工程的时间变短，选择哪个最合适
(其他数字记不得了)
A a2 B a5 C a6 D a8
29.下列是计算机组成原理研究范畴的是
A 数据格式的设计 B主存格式的设计 C指令格式的设计 D数据通路的设计
补码加减法
原码补码移码反码，哪个大
小段存储对齐方式，存储字长为8位，则12345678H中，78H可能存放的主存地址为
A 2003 B 2002 C 2001 D 2000
字位扩展法，问最少需要多少个芯片
A小于B的逻辑表达式
以下总线传输的方式中，优先级静态的是
磁盘速率
37.五级流水线
39.I/O的几个方式中，可以在两个指令周期中传输两次数据的有
A DMA与程序中断方式
B DMA与程序查询方式
C DMA与无条件传输方式
D程序中断方式与无条件传输方式
41.
进程调度，单位时间毫秒，优先级数字低的优先级高。
|
进程 |
到达时刻 |
运行时间 |
优先级 |
|
P1 |
0 |
10 |
3 |
|
P2 |
1 |
1 |
1 |
|
P3 |
2 |
2 |
3 |
|
P4 |
3 |
1 |
4 |
|
P5 |
4 |
5 |
2 |
(1)计算采用优先级调度(非抢占)算法的平均周转时间和平均等待时间
(2)计算采用短作业优先调度(抢占)算法的平均周转时间和平均等待时间
42.
假设欲访问的页序列为1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6，给系统配置了3个空页框。
(1)使用FIFO、最优(optimal)、LRU置换算法，页错误分别为多少
(2)以上三种置换算法只有一种是用在现实的系统中的，是哪一种？并解释另外两种置换算法为什么没有被使用。
43.
哲学家进餐问题
semaphore chopstick[5]={1};
pi
{
while(1)
{
wait(chopstick[i]);
wait(chopstick[(i+1)%5]);
eat
signal(chopstick[i]);
signal(chopstick[(i+1)%5]);
think;
}
}
该算法存在问题，可能产生死锁，请说明可能存在的问题，解释原因。
存在某种改进算法，对哲学家添加一些限制条件，请补充123
semaphore chopstick[5]={1};
semaphore istochopstick=___1___;
pi
{
while(1)
{
____2_____;
wait(chopstick[i]);
wait(chopstick[(i+1)%5]);
____3_____;
eat
signal(chopstick[i]);
signal(chopstick[(i+1)%5]);
think;
}
}
(3)2中的算法仍然存在一定的瑕疵，如p1拿起左右的筷子时，不仅限制了相邻哲学家的进餐，与p1不相邻的哲学家也可能会因此饥饿得不到进餐，请说明该算法不完善的地方，说明原理（考虑哲学家进入饥饿状态）
44.
有向图G如图所示
(1)求该有向图的邻接矩阵A
(2)求A²，并说明A²中非零元素代表什么
(3)推广至A的m次方，说明A的m次方中非零元素代表什么
45.写一个算法，统计二叉树中不平衡结点的个数。若一个树的左子树高度和右子树高度之差的绝对值大于1，则表明该结点为不平衡结点。
46.主存地址为32位。Cache的容量为512KB，cache块大小为32B，采用4路组相联，LRU替换算法，写回法写策略。
(1)cache目录表项至少多少位？主存地址为12345678H，且cache号命中，则命中的cache组号是什么？
(2)采用8体存储器，交叉工作方式，总线时钟周期20ns，总线与主存的数据传输一次可为32位，则总线传输一个数据块所用的时间为多少？总线带宽为32位，总线频率为多少？
47.16位的计算机，按字节编址。数据在计算机中以有符号整数补码的形式存放。DE是一个数据扩展器，扩展之后数据真值保持不变。有两种指令格式格式1和格式2，其格式如下表（其中OP1由OP1_1和OP1_2组成，Rs、Rs代表两个寄存器）
|
OP1_1 |
Rs |
Rd |
OP1_2 |
|
4 |
2 |
2 |
8 |
|
OP2 |
Rs |
Rd |
IMME/DISP |
|
4 |
2 |
2 |
8 |
可以进行的操作有
Rd←OP1_1 Rs OP1_2或Rd←Rs OP2 [Rd+IMME]或Rs←Rd OP2 [Rs+DISP]
（题目很长，但是很多都没用）
(1)格式1和格式2中的数据寻址中，都有什么寻址方式？格式2占了4条指令，格式1最多还能有多少条指令？
(2)ALU已经设置了Y，为什么还要设置Z？
(3)写出R2←[(R1)+75H]的微操作步序列
