二、简答题(第一题6分，第二题8分，第三题9分
1、一颗空AVL树中，顺序插入{5942138}
(1)、严格遵循AⅥL操作，画出插入后的AⅥL树(画出每一步)
(2)、全部插入后，求等概率下的查找成功的平均检索长度。
2、二叉树的内部路径长度
假设N个互不相同的随机元素插入一棵空二叉搜索树，证明得到的二叉搜索树的内部路径长度期望为O( NlogN)
3、给定一个长度为N的数组，保证其中至多存在C个极值点(ai为极值点，则满足
1<< span="">i
间复杂度尽可能低的算法对N排序
算机组成原理
选择题(1-II题为单选题，每小题2分)
1。给出一串16进制数0x1234567890，问用大端法和小端法储存分别是多少?
A。小端从地址小到大1234567890从地址小到大大端9078563412
B. ??
C. ??
D. ??
2.3.14的16进制数是XXXX，问它的阶码用二进制表示是多少?
A.??
B.10000000
C.??
D.??
3。问下列几个哪个不是冯诺依曼结构的基础部件?
A.CPUB内存
C.硬盘
D打印机
4。实现了5级流水线，每个阶段的运行时长为如(3ms5ms2ms6ms4ms)，问主频为多少?
A .166MHZ
B .248MHZ
C .333MHZ
D.??
5、行波进位和超前进位的概念题
<真题>考虑到电路的复杂性与延迟，ALU的加法器实现通常是由：
A。多个小规模超前进位加法器拼接而成
B。多个小规模超前进位加法器和行波进位加法器级联而成
C。大规模行波进位加法器组成
D。大规模超前进位加法器组成
6。程序查询、中断、DMA三种方式的概念题?
下列关于程序查询、中断、DMA的三种方说法正确的是
A。DMA对外部输入输出的响应实时性最高；
B。中断仍需要经过CPU寄存器传输数据
C。除程序査询方式外，中断和DMA都不再需要编写程序执行
D。DMA总是性能最高
7。中断向量表存储的是?
A。中断服务程序的入口地址
B。中断号??
C。中断状态字
D.??
8。路组相联的一个计算
<真题> Cache采用4路组相联每块32B16组(编号0-15)，请问 OXDEADBEEF映射到
A. Set7
B. Set11
C. set13
D. set 15
9。流水I线的相关概念题
<真题>下面关于流水线说法正确的是()
A。通过不断加深流水线的级数，流水线的效率可以不断提高
B。流水段的平均延迟影响了流水线的最高频率?
C。流水线中的冒险都可以通过插入流水线停顿来解决
D.??
10。磁盘的转速为7200RPM，寻道时间为9ms每个磁道有400个扇区，数据分布均匀，问读取一个扇区的平均时间( )
A.4.7ms
B.9.20ms
C.7.56ms
D.5.74ms
11。关于硬布线控制器和微指令控制器的对比，下列说法正确的是()
A。微指令控制器执行效率更高
B。硬布线控制器电路组织更简单
C.硬布线控制器指令执行效率更高
D。硬布线易于扩展和修改功能
二、解答题(第一题9分，第二题14分)
1。(1)给出了一个未优化的乘法器的线路图，请描述乘法器的运行步骤，请用流程图和文
宇描述其工作过程
(2)该乘法器还可以优化，请画出优化后的乘法器的线路图，并描述做了哪些优化。
2、（1）将MIPS指令集精简为MIPSLite指令集包括ADDU、SUBU、ORI、LW、SW、BEQ。
CPU数据通路图如下：
（2）分析指令需求以集成控制信号，请填写下列表格。
（3）若将如上单周期处理器改造成为流水线处理器，拥有五个流水段F（取值）、D（译码）、E（执行）、M（访存）、W（写回），那么流水线会产生哪些毛线？举例说明
针对以上冒险，若要优化流水线，应该增加什么部件或者怎样修改部件，请用文字描述。
操作系统
一、选择题（1-9题为单选题，每题2分）
二、1、根据操作系统进程五状态图（图*），判断进程状态哪个对？
A、1->创建态
B、2->新建
C、3->就绪
D、4->阻塞
2。问什么时候不一定会发生进程切换?
A。进程时间片用完
B。当进程创建了一个子进程之后
C。进行读盘操作
D。进程运行过程中产生了异常
3。安全状态和死锁的关系？
<模拟题>类似题：关于死锁状态与不安全状态的关系，下列描述正确的有：()
A。死锁是一种不安全状态
B。系统处于不安全状态，一定产生了死锁
C。不安全状态是死锁的必要条件
D。不安全状态是死锁的充分条件
4。使用LRU，问哪个被换出?<< span="">给了一个表格以及一些参数>
题日给出了页号，页框号，修改位，访问位，T时间内访问的次数
A. ?? B.?? C.?? D.??
5、给了信号量的定义，问N个进程竟争一个资源，需要几个信号量?
给出P(S)V(S)的实现代码
A.1 B.N C. N-1 D.N+1
1、给定页表大小为512字，指令存了2页，数据存1页，然后给了一段程序要初始化一个
1024*1024的矩阵，问缺页多少次?(其中数组A[1024][1024]为 INTERGER类型页表大小为
512字,A[i,j]=0)
A.1024*1024
B.1024*512
C.1024*1
D.1024*2
6。关于FAT文件系统下列说法不正确的是()
A。FAT文件系统文件名区分大小写
B。FAT文件系统文件的物理结构是链式组织
C。FAT文件系统为了提高效率，采用了目录项分解的方法
D.??
11。问下列哪些操作不是为了提升文件系统性能(目录项分解等)?
A。目录项分解
B。文件高速缓存
C。磁盘调度算法
D.异步I/O
9。下列关于死锁的选项，哪一个是不正确的()
A、安全状态一定不会发生死锁；
B、不安全状态一定会发生死锁
C、不安全状态就是死锁
D、??
<模拟题>：下列关于死锁与安全状态的叙述中，哪一个是正确的?
A。死锁状态一定是不安全状态
<span s
电话咨询
微信咨询
在线咨询