武汉大学核算机学院核算机基础历年考研真题汇编(武汉大学计算机研究生学院)

1、2014年武汉大学核算机学院933核算机基础历年考研真题 22007年武汉大学核算机学院828核算机基础历年考研真题 122006年武汉大学核算机学院832核算机基础历年考研真题 182005年武汉大学核算机学院855核算机基础历年考研真题 222014年武汉大学核算机学院933核算机基础历年考研真题盛飞 $人，/产2014年攻读硕士学位研讨生入学考试试题（满分值15u分）类别称号；核算机基础d类别代建933留心:一切答题内容有必要写在答题纸上，凡写在试题或草稿纸的二三府,逐个数据规划有些（45分）一、单项选择题（每小邈2分，共22分）k以下归于逻辑规划是（）.a.唳序表哈希表 c.有序表 d.

2、单链表ii2、在长度为h5）1）的年空双箍液l中，删去p所指结点的前趋结点.（嫌头结点）的时刻凌乱度为（）*，a 0（1）b.o cq。）dqo中冷 .iv3、由两个栈同享一个数组空间的优点是（）0a.削减存取时刻，降低上溢 生的机率b.节约存储堂间，降低上溢 生的机率c.削减存取时刻,降低下溢 生的机率d.节约存储空间，降低下溢 生的机率 i4、当用一个数组而回0.用-1存放栈中元素时，栈底最佳（）。a.设置在d砌0处b改苴在datatt-jitc.设置在data成由应1处d.设置在data数组的任何方位i-_5、若用一个巨细为n的数组来完成循环队到初始时队法fmn年i队尾指处羹或均

3、为 21一 i – – ,二 i 1. 一其i。页第;1页 .布1-6的6个兀素进联，然后出队8次，发现正本存放元素4的方位变为队头，则方为().a.5. b.4c.8d.106、设c/ci二维数组a10j20j选用次序存储方法，每个数组元素占用1个存储单元,dojlo 的存储地址为200,近62的存储地址是226,则该数组(),a.只能按行优先存储b.只能按列优先存储c.按行优先存储或接列优先存储均可d.以上都不对.,7、若一裸放为闭的哈夫能树有个结点，则叶子结点的个数是().a. l(/(wl)+!)j .*b. i (w-1 )/rnjc. l(t 1 y(w- !)jd.! )j 18

4、、用prim算法求一个连通的带权图的母小代阶生成机 在算法实施的某时刻，己选择的项 点集结u = 1,2,3),边的集结te=(1,2), (2,3),要选择下一条权值最小的边,应当从() 组中选择。a.(1,4), (3.4). (3,5), (2,5)b.(4,5). (1,3), (3,5)c.(1,2) (2,3). (3,5). d.0,4),(4f), (1,4)9、若将要害词1, 2, 3, 4, 5, 6, 7顺次刺进到初始为空的平衡二叉树t中，则t中平衡 因子为0的分支结点的个数是().a.ob.lc.2d.310；.序列3,241,5,6,8,7)超桀一趟递加排片后的成果，

5、.则选用的排序办法可所以().a.快速排序b.用泡持序c.堆排序d.简略选择排序 c11、以下关于堆的叙说中正确的是()i .在一个大根堆中，最小要害词的记载必定归于最低层的叶子结点层ii .在一个小根堆中，从根结点到某个叶子结点所经途径上的结点构成一个递加有序序列 皿.堆必定是一棵完全二叉粉二庄列规划的一根完全二叉川经过一次选择便可以变成一个摊 共10灰a、仅i、mb.反ii、m – c.仅in、iv靛丁、一n、川 一二、使用题（共2小题，共23分）1、（13分）有2”支足球队（球队编号为12”）进行竞赛，选用选择制，两支 球队的胜者进入下一轮竞赛，最终发生冠军，如图1所示的是8支球队的竞赛

6、过 程，最终编号为7的球队获得冠军假定竞赛进程构成的一叉端果用二叉链存储规划，其结点类型如下:图i. 8支球队的比奏进程typedef struct node int no;球队编号struct node !child,*rchild; 左、右核子结点指针 btnode;关于给定的根结点指针为b的竞赛.又树，议计一个算法输出一切与编号为x的球队进行过 竞赛的球队端号。算法中给出必要的注糅q2、（1。分）关于一个权值大于。的弟权有向图，选用dijkstra算法求源点y出 发的最短途径，答复以下疑问:.（i） s中存放已求出最短途径的极点序列（依先后次序），若s的极点序列为 vi.w、以，则从丫到

7、力的途径k度老是大于从丫到90力的途径长度吗？（3 分）,（2）对dijkstm算法做这样的改动:每次都选择最远途径的极点，其他不变, 则这样改动后的算法能求从源点v到其他一切极点的最远程径吗？（3分）（3）假定带权有向图中存在负权，选用dijkstra算法能求出从源点p到其他项点的最短途径吗？假定能求，请予以证明，假定不能求，请给出一个反例。（4分）核算机构成原理有些（45分）一、单项选择题（低矮题2分，共22分）1、在cacho-主存体系中，块冲突概率最高的地址映像方法是a.全相联映像b.直接映像 c.卯相联映像d.段相联映像2、在很大都据传送中常用的且有用的查验法是 0a. crc码 “

8、b.海明码 c.偶校验码 d.奇校验码 13、指令体系中选用不一样寻址方法的意图首要是。a.完成存储程序和程序捽制.b.供给拓宽操作码并降低指令译码难度， c.可直接造访外存 d.缩短指令长度，扩展寻址空间，前进编程活络性 4、以下论说正确的是。a. cpu呼应中止时刻仍实施原程序。b.在中止晌应中，维护断点是由中止呼应主动结束的。c.在中止呼应中，维护断点、维护现场应由用户编程结束。d.在中止进程中，若又有中止源提出中止，cpu当即呼应。5、核算机的存储器选用分级方法是为了。a.削减主机箱的体积13.处置容量、价格、速度三者之间的敌对c.为便利保存很大都据d.操作起.来更便利6、构成个运算器需

9、要多个部件，但下面所列 缺乏构成运算器的部件。a.状况存放器b.数据总线c. alu d.数据存放器7、相联存储器是按 进行寻址的存储器。a.地址指定方法b.仓库指定方法c.内容指定方法d.地址指定方法与堆柱存储方法联系8、16个汉字的机内码需要 a. 8字节 b, 64字节 c. 32字节 ,d. 16字节外直接转移指令的功用是将指令中的地址代码送入 07%贫 而海a.微程序计数器 b,地加存放器c.程序计数器d.存储器10、在i/o接口中设置中止触发器保存外设提出的中止恳求,是因为。a.中止不需要当即处置。b.中止设备与cpu不一样步。c. cpu无法对发生的中止恳求当即进行处置“ d.可以

10、有多个中止一起发生。11不是构成流水线堵塞的要素是 oa.数据有关b.程序转移 c.指令太长d.指令预取.二、某核算机的cpu内部为双总线规划，一切数据传送都经过alu, alu具有 下列功用:f=1 ； f=r ； f=a+1 ； f=b+i； f=/b, cpu 规划如下图，图 中y为暂存毋，pc为程序计数罂，mar和mdr别离为存储器地址与数据存放 器，ir为指令存放器。（1）方案三条机器指令完成一条java语句:i=i4j的功用.（6分）（2）别离写出三条机器指令的微操作序列.。分）三、某核算机选用页式虚拟存储器，每页巨细为512b或许1024bo 一段程序由 1200条指令构成，每条

11、指令的字长均为4b,在这台核算机上循环实施5遍，选用 lru替换算法。假定实施之出息序一切页面都在外存。（1）当页的巨细为1024b时，假定物理内存有接连的4096b剩下空间,核算主存的射中率。（4分）（2）当页的巨细为512b时，假定物理内存有接连的5120b剩下空间，核算主存 的射中率。（4分）（3）假定内存有满足空间满足程序调入，页的巨细为多少时，浪费的内存最少？ （2分）操作体系有些（35分）一，单项选择题（共10小题，每小题2分，共20分）l可以及时处置由进程控制反应的数据并做出呼应的操作体系是a.分时体系b.实时体系c.网络体系d.批处置体系2 .操作体系中引入多道程序方案技能的好

12、处是 0；简化操作体系的完成, b.便于施行存储维护! c.使并发实施变成可以d.削减对内存容是的需要i| 3.使核算机体系能并发实施的硬件撑持是。|a.多处置器技能b.大规划集成电路，c.高速内存d.中止机构 4.在单处置机体系中处于运转状况的进程。a.最多只需一个b.可以有多个c.不能被挂起d.有必要实施完才干被撤下5 .会发生belady异常表象的页面置换算法是一.a.最佳页面置换算法b. 先出页面置换算法c.迩来最久未运用置换算法d.最少运用页面置换算法6 .在供给虚拟存储的体系中，用户的逻辑地址空间首要受一和外存巨细的捆绑a.内存空闲块的巨细b,内存空间的巨细c.指令地址规划d.页表

13、巨细7 .分页体系中的页面是。a.操作体系感知的b.用户感知的c.编译程序感知的d.联接设备程序感知的8,体系使用spooling技能完成.；。”a.虚拟设备b.虚拟存储c.缓冲区d.对换办法9 . cpu与通道可以并行实施，并经过 完成彼此之间的通讯和同步.a. i/o指令b. i/o中止c.操作员d. i/o指令和i/o中止10 .鄙人列叙说中，偌误的一条是。a.进程被撤消时，只需开释该进程的fcb就可以了，因为pcb是进程存在的 仅有标志8 .进程的互斥和同步都能用p/v原语完成c用户程序中实施体系调用指令时，处置机的状况字将发生改动d.设备独立性是指用户在编程时，所运用的设备与实践设备

14、无关二、使用题（共2小题，共15分）1一个快餐厅有4类职工:（1）工头:承受顾客点菜；（2）国师:预备顾客 的饭菜:（3）打包工:将做好的饭菜打包；（4）出纳员:收款并提交食物。每个 职工可被看作一个进程，试用种同步机制写出能让四类职工正确并发运转的程 序。（9分）9 .在个实践的核算机体系中，本钱可以更新和增减，进程可以创建和撤用。 假定体系选用银行家算法处置死锁，当体系处于平安状况时,在啥情况下,下列 改动可以平安地进行而不会致使死锁发生？（6分）（1）添加available （添加新本钱）,（2）削减available（本钱耐久性地从体系中删去）；（3）增大max（对一进程而言，它可以

15、需要更多本钱）；（4）削减max（一进程抉择不需要那么多本钱）；（5）添加进程数；削减进程数。核算机网格有些（25分）一、单项选择题（共8小题，每小题2分，共的分）33.以卜说法中，关于核算机网络体系规划中n层pdu和nil层sdu的联络正确的是一个n+1层的sdu可封装在一个n层的pdu中 多个n+1层的sdu可封装在一个n发泡pdu中一个n层的sdu可分片封裟在多个代层的! du中a b. c. 3d.（d 34五颜六色电视图像每帧含】。6个像素，每个像素有？6个等慨率呈现的颜色，若需求每秒传送30帧图像，设信道输出信噪比为30db,则传输此电视信号所需的最小带宽约为a. 24mhzb.48m

16、hzc 768mhzd. 1536mhz ，35 .分组交流技能具有的特征是a.萄个分级独立的寻找途径b.分组顺次抵达c.动态分配传输带宽d,比电路交流时延小36 .以下关于局域网的说法正确的是a.在以太网中，节点实施二进制指数退避算法推迟一段时刻后重传来保证数据的正确传送37 在某些条件下，以太网可以不运用csma/cd协议c. vpn是局域网供给的一种效能d. csma/cd是无线局域网的标准，可以避免冲突发生37.主机a和主机b之间选用hdlc协议通讯，当主机a向主机b发送了序号为2的4个 数据帧后，主机b向主机a发送了 rr2,此时主机r止确接收的帧最多是a.1个b.2个c3个d.4个

17、 38长度为2000字节的使用层数据顺次封装成tcp报文段、1p数据报和以太网的假后传送出 . 去，则数据的戢商传输功率为a.97.28%b.97.19%c.96.34%d.95.42%39 .主机a和主机b刚树立完tcp联接时，妁定最大的报文段为2千字节，主机b的接收窗口为20千字节，ssthresh为16千字节，加果双向传愉时刻为10ms,发送时延忽略不计，接连稀有据发送且无拥塞发生，则经过ms主机a的发送窗口初度为20千字节.a.40b.50c.60d.7040 .在dns体系中，选用迭代查询时宣告域名查询恳求最多的效能器是a.本地域名效能器b.权限域名效能器c.顶级域名效能器d.根域

18、名效能器 二、问答题（9分）. 在一个自治体系中选用间隔向量算法核算路由，最短间隔选用推迟时刻。（1） 路由器a测得到相邻路由疆r和路由器c的延时别离为6ms和10ms,路由器a的路 *由表如下表所示.网络地址.子网掩码间隔下一跳.57.0.0.0255.0.0.015190.252.7.4190250.0.0255.255.0.00. *190.252.0.0255.255.0.00一 .200.50.6.0255.255.255.00 200.149.4.0255.255.255.030200.50.6.7此时路由器a收到路由转b和路由器c泊路由表,. 路由去内容是怎样的？.,路由器b (

19、地址1s0.25274)有些内容如下衣所示，路由相人更新后的. .4网络地址子网掩码，间隔 57.0.0.0255.0.0.010190.250.0.0255.255.0.00190.252.0.0:25f255.0.00 200.149.4.0255.255.255.02。、路由繇c（地址190.250.80.7）网络地址:子网掩码,距禹57.0.0.0255.0.0.09190.250.0.0255.255.0.00190.252.0.0255.255.0.00200.149.4,0255.255.255.014(2)路由器a的端口 1分配的ip地址和子网掩码别离为200.50,6.8和2

20、55.255.255.0, 该端口地址的网络要区别为3个子网，子网1有100台核算机，子网2和子网3均匀分配剩 下的卬地址，给出ip地址分配方案，包括每个子网的子网号、子网掩码和可分配的地址规模.共】。页第io页2007年武汉大学核算机学院828核算机基础历年考研真题武汉大学2007年攻读硕士学位研讨生入学考试试题类别称号:核算机基础类别代码，828留心一切的答案内容必续写在答题纸上，凡写在试题或草稿纸上的一概无效.核算机构成原理有些（共75分j一.单项选择题（共15题，每题1分，共15分）k定点数运算发生溢出时大约*a.输出差错信息b,舍入处置c.向左标准化d.向右标准化2,尾数选用补码的浮

21、点数运算中,呈现 情况大约进行标准化处置.a,符号位与最高数值位不一样b,符号位与最高敷值位相同u符号位与最低数值位不一样ix符号位与最低数值位相同3. sram写入数据的条件是,a. ah有用比r/w#=0早抵达 r. ab有用与r/w#=o一起抵达c. ab有用比r/w#=0迟抵达 d, ab有用与ads#=0一起抵达4、dram地址分两次摘入（行选通ras队 列选通cas#）的意图是 *a,前进速度b,削减芯片引出线 c.改写 d.电平需要5半导体存储器速度最快的是 a, eprom b- dram c sram d- flash memory6、多体穿插存储器首要处置的疑问是 .a.扩展主

22、存储器的容量b.前进主存储器数据传输率c,削减主存储器芯片数献d.简化线路规划7、一主机的cadw容量是256块，选用直接映像方法，主存中的第i块将会映f 到cache的第 块中.a. 256 b. i（mod256） c. i d, i+1s.在磁盘存储器中，以下正确的描绘是*a.各磁道的位密度相等b,内圈磁道的位密度较大c,外圈磁道的位密度较大d.表里膜磁道的位密相等% fm的编码功率是-a. 50% b. 25%c, 75% d, 100%核算机基对 f计甘机世成原理、数据皓构）第1支我6或10、dll磁记载方法的利益是a.自同步才能强b.抗烦扰才能强且存储密度高c.读写电路简略d.可以

23、前进磁盘传输率11、选用断定方法的微指令中，下一条微指令的地址 qa.在微指令计数器中c.在程序计数器中12、控制存储器用来存储 a.机器指令和数据c.机器指令和微程序13、通用微机体系的规划展于b.在微指令存放器中d.在本条微指令的次序控制字段中b.微程序和数据d.微程序核算机m础）（核算机构成收理、数据规划）第3页共8页a.以mem为中心的单总线规划 b.以mem为中心的双总线规划c.以cpu为中心的双总线规划 d.单总线规划14、总线方案中选用复合传输方法的意图在于 ea.前进总线的传输带宽b.削减总线中信号线的数豉c.添加总线的功用d.简化总线协议15、在共同编址的方案办法中进行i/o

24、操作的指令是 。a.控制指令b,运算指令 c.访存指令d. i/o指令二、运算办法与运算器分析题（共15题）1、（7分）图是一个（7, 4）循环海明码编码器的原理图，该码的生成多 项式是g（x）f、x+1,它由三个推迟电路d和两个异或门构成.假定输入的信息 码为1001,分析该电路的编码输出，写出编码进程和输出信息。看入输出图一 （7, 4）编码器原理图2、（8分）在定点补码加法运算中，发生溢出的条件是啥？写出两种溢出 判别办法，并分析判别溢出的进程.三、存储规划与存储体系分析题（共15题）某一核算机体系选用段页式虚拟存储器方法，已知虚拟地址有32位，按字编 址每个字段最多可以有1k字，每页

25、16k字，主存储器容量64m字。1 （5分）核算出虚拟存储器的容量。2、（5分）分析逻辑地址和物理地址的格局。3、（5分）核算出段表和页表的长度。、指令体系与控制器方案题（共15题）1、（共10分）某一单流水线处置机，包括取指、译码、实施3个功用段。取指、译码各需1t:在实施段，mov操作需2t, add操作需3t, mul操作需4t；各操作在it内取数,流水线的功用。k； movk+1: mulk+2: addri风ro,r2,riroj2,ri在最终it写成果。实施下面程序后按需求分析指令;r）（ro）:ro（ri）-（rc）:rdrz）hr3）1） （2分）方案并画出流水线功用段的规划图

26、。2） （5分）思考指令数据有关性，方案并画出指令实施进程流水线的时空图。3） （3分）为了加速速度，可以采纳那些改进办法。2、（5分）假定某一微处置器的控制器结束每条指令功用的时刻为5个机器 周期（mi、m2、m3、m、m5）,方案可以发生5个机器周期的时序电路，并网 出时序图。五、体系总线与i/o调度方案题（共15题）1、（7分）用异步串行传输方法发送十六进制数3bh,数据位为8位，奇偶 校验位为一位，结束位为一位。方案并画出该数据串行传输波形图。2、（8分）某一核算机体系方案为5级中止体系，硬件中止呼应从高到低的 优先次序是1-23 4-5,假定设置中止屏蔽位使中止处置次序改为12一4

27、一3 – 5,当cpu实施程序时有2、3、4和5级的中止恳求一起抵达，cpu在按 优先次序处置第3个中止进程中又有1个1级中止恳求到来方案并湎出cpu 处置这些中止进程的示意图。数据规划有些(共75分)单项选择题(2×10分，共20分)1、在方案存储规划时，一般不只需存储各数据元素的值，而且还要存储一。a.数据的处置办法b.数据元素的类型c.数据元素之间的联络d.数据的存储办法2、若已知一个栈的进栈序列小，m，p3pn.输出序列是1，2, 3若 pn=l,则 pi (1in) %oa. ni+l b. n-i c. id.有多种可以3、a*(b+c)刁的后缀表达式是一a. abcd*+b. a

28、bc+*d-c. abc*+d*d. +*abcd4、一个n*n的对称矩阵，假定选用乐缩存储放入内存，则容量为.a. n2b. n2/2c. n*(n+l)/2 d. (n+l/25、在一棵非空二叉树的中序遍历序列中，根结点的右边 oa.只需右子树上的一切结点b.只需右子树上的有些结点c.只需左子树上的有些结点d.只需左子树上的一切结点6、一个图中包括k个连通分量，若按深度优先查找办法造访一切结点，则有必要 调用 次深度优先遍历算法.a. kb. 1c. k-1 d. k+17、已知一个有向图的邻接表存储规划如图1所示。根据有向图的深度优先遍历 算法，从极点1 ，所得到的极点序列是一oa. 1

29、、2,3,5,4 b. 1,2,3,45 c. 1,3,45,2 d. 1,4,3,5,2图1有向图的邻接表存储规划8、对有18个元素的有序表ru.18进行二分查找，则查找r3的比照序列的下 标为a. 1、 2、 3 b. 9、 5、 2、 3 c. 9、 5、 3 d. 9、 4、 2、 39、鄙人列排序算法中，可以呈现下列情况:在城后一趟初步之前，一切的元素都不必定在其究竟的方位上.a.堆排序b.冒泡排序c.刺进排序d.快速排序10、下述几种排序办法中，需求内存量最大的是。a.刺进排序b.选择排序c.快速排序d.归并排序二.问答题（共30分）1、（8分）假定对长度为n的线性表的运算只需4种

30、，即删去第个元素，删去 最终一个元素，在第一个元素前刺进新元素，在最终一个元素后刺进新元素， 现有以下4种存储规划:a.只需表尾指针没有表头指针的循环单链表b.只需表尾指针没有表头指针的非循环双链表c.只需表头指针没有表尾指针的循环双锥表d.既有表头指针也有表尾指针的循环单链表请填表给出在每一种存储规划下答运算算法的时刻凌乱度。.存储结删去第一个元素酬除品后一个元素第一个元素葩刺进 元素最终一个元素后描入后塞 _ abcd2、（5分）若一棵哈夫曼树的叶子结点个数为5,则该树的总结点个数为多少？（需求写出求解进程）3、（5分）在有n个极点的有向图中，每个极点的度最大可达多少？4、（7分）对给定的

31、数列r:（7,16, 4, 8, 20, 9, 6, 18,5,规划一棵二叉排序树， 而且:1）给出按中序遍历得到的数列r1;2）给出按后序遍历得到的数列r2:5、（5分）在直接刺进排序、希尔排序、目泡排序、直接选择排序、快速排序、堆排序和基数排序办法中.1）不需要进行要害词比照的是哪些？2）要害词比照的次数与记载的初始摆放次序无关的是哪些？三.算法方案题（共25分）1、（10分）设有一个带头结点的单链表he,其结点值序列为,*包,儿,， ab）且a、b应对呈现）,核算机基础（计尊机构成原理.数据规划）第5页共6页方案一个算法 void split （linklist *hc, linklis

32、t *&ha, linklist *&hb）, 将he拆分红两个带头结点的单链表ha和hb,其间ha的结点值序列为 （a1g ,aj, hb的结点值序列为（b“ k,bj,需求ha使用原he的头 结点，算法的空间凌乱度为0（1）.2、（15分）假定一棵二叉树选用二叉链存储规划进行存储，结点类型为nodetype, nodetype的界说如下:typedef struct node（char name10;/*存放名字*/int val;/*每放数量*/struct node *lchild, rchild;右孩子结点指针*/ nodetype;现给定的二叉树中，每个结点都有name值（假定一切

33、结点的name值均不相 同），但只需叶子结点供给了 val值，其他各分支结点的val为0,每个分 支结点的val值应等于它的孩子结点的val值之和。需求:1 ） （7分）方案查找指定name值na的结点指针的算法nodetype *find（nodetype *bt, char na口）若找到这样的结点,回来其结点指针,否 则回来null；2 ） （8分）方案计算指定结点（其结点指针为p）的val值的算法int getval （ncdetype *p）,例如，关于图2所示的二叉树，求得的各分支结点的 val值如下:nil: 7nl21: 5n12: 5nl: 128-nl2h.5图2 一棵二又

34、树（计赛机基础（核算机构成原理 数据规划）第6发共6页2006年武汉大学核算机学院832核算机基础历年考研真题武汉大学2005年攻读硕士学位研讨生入学考试试题 .考试类别二核算机基础类别代码:832k的i收&局辽例上核算机构成原理有些一、单项选择蹦（共15箱，每期1分,共15分）1. 口位定康补码标明的最大伯是-a. 2*h. :t-lc. 2td. 22. f 门的i进制第粒为k=xhmxw k移码数值的取值范用是.c -2 x2nd t 外d位符号位，其定点3. 机一字长机惘 淳。示时.阶吗为，位.尼数位24位落占 小数标明的葩国她一人1127c（lt 1*2%一机内码为80h,所标明的良

35、他是一127，则它是。d.移研a.补吗b,原码c,反码5.在定点位补码乘注中.a,符号位参加运算 b.符号位不参揄运算c.符号位参加运葬.并根据成果改动成果的符号位d.符号位不参加运需,并根需站里断定成果的符号忖 6定点加法运算中，时标明数据发生渣出.0.眄位数相加a.双符号位相同b. .双符号何不一样c.网1e数相加7.初态ram的改写是认为单仰进行的。a.存储单元b,字节c行8,在虚拟存储器中,，主存的射中率越高a.页面越大b,辆在容量越人c.优胜长 d. 1q,访向相联存储器时.大约访m.a*根据地讣 b,根甥内容 c.根据地址和内容 11不必地址和内容 指令体系中选用不一样的寻址方法的工翌

36、口的是 oi a.添加内存容最b.前进济存速度c.简化指令译码 d.编程便利11 .格最低字节存储在最小地加密置的存储方法称为 方法a.大数谓存储凡小数端存林 c.对齐存储 d,对齐存储12 .在选用忧程序控制器的核算机中，条机器指令案由 来实施的。a. 一条微指令 r 条机器指令 c 段微程序d一条也指令和机器指令13 . cpu的方案中,不需要一d.地址存放器d.水平微程序d.数据运算a.指令存放器 b.指令译码器c.数据存放器14 .将微程序存储在ram中的控制器 控制器。a.动态微程序h.静态微程序c. ,皂微程序15 .通道处置器不具有 功用.a.中止b.dmac.程序控制二,运算方

37、法与数据校险分析题（共15分）1. （7分）原刊一位除法运算可以来用恢复余数办法和小恢复余数办法（加减替换法），比 较分析两种办法的不一样之处,曲山不恢及余数办法的具体控制流程图。2. （8分）某 机器16位字长的字为dd产1111000010101110,参加5位校验位后的21 位海明码为hi.h2i=001011100000101101110.假定该字的第5位因为电源颤动曲犯错变成 01001100000101101110,用偶校验，分析海明码的检错和纠错失程。三、存储体系与存储规划分析题（共15分）某一核算机体系选用“ l一cache”存储层次规划，主存容量有8个块，cache容最有4 个

38、块，选用直接地址映像。1. （8分）假定主存块地址流为0，i，2, 5. 4, 6, 4, 7, 1, 2. 4, h 3, 7, 2,主存 内容一初步未装入cache中，列出每次造访后cache中各块的分配情况2. （4分）指出块射中的时刻.3. （3分）求出此时刻cache的射中率.、指令体系与控制器方案题（共15分）式-核算机体系果用微程序栉制溺方案方案，假定选用水平型百接控制微指令格局，断定方法。假定核算机指令体系共有微指令20个，可断定的外部条件有4个，控制存储器容串为128×30.1 . （7分）方案出该控制器微指令的久体魄式.并给予阐明。2 .（8分）画出该微程序控制器规划框图，

39、五、0体系与0调度方案题（共15分）在个多重中止体系中，需求使件中止呼应从高到低优先次序是: 设器 1设备2设备:一1. （10分）用简略门电路方案出该多英中止排队电路的前三级电路。2. （5分）并分析其排队进程e数据规划有些一、单项选择题（共10小题，每题2? 共20分）1 .某算法的时刻凌乱度为。（舟,丧明力立法的a.疑问规划是/ . .b.实施附间等于c.实施时刻与n?成正比d.疑问规划与云成正比2 .设线性表有n个元素，以卜糅件中,在次序发上完成比在链表上完成功率更高.a.输出第i（li经n）个元素值、.8 .交流第1个元素与第2个元素的值c.次序输出这n个元素的值d.输出与给定值x相

40、等的元素在线性表中的序号9 .设n个元素进栈序列定1, 2, 3 n,其墉出序列是pp pa p.若小=3,则6的值为一0a,必定是2b.必定是ic.不可以能是1d.以上都不对4 .设循环行列中数外的下标是0n1,其头尾指针别离为f （指向队头元素的前一方位） 和r （指向队尾元素的方位），则其元素个数为一-a.r-fb.r-fuc.（m）%n+id.（r-*n）%n5,若小s=2bcdefgh其子串（不含门身）的个数是a.8b.37c.36d.96 .若将n阶上三角矩际a按列优先版序紧缩存放在一维数组bl.吗辿中,第 个作等 元索aii存下b0中,则应存放到bk中的#零元素ml&iwn, ij

41、wi）的卜标i，j与k的对 应联络是一oa.乎jc.四,i 27 .设高度为h （根结点为第i层）的一义树上只仃度为0和度为2的结点，则此类,又找 中所包括的结点数至少为。a.2hb. 2h-lc. 2h+1d. h+1b.零矩阵d.对角矩阵8 .无向图的邻接矩阵是一个a.对称矩阵c.上二角矩阵9 .对线性表进行二分备找时，需求线性表必维。a.以峻序方法存储b.以联接方法存储c.以次序方法存储，且结点按要害词有序排序.d.以跳衣方法存储,且结点按要害词仃序排序10 .以下排序算法中，不能保mju施揖序至少能将一个元素放到其究竟方位上a.快速排序b.希尔排序 c.堆排芹d.冒泡排序二、问答蹈.（

42、共30分）.l （8分）有5个字符，根据尺运用嫉率改计对应的哈夫曼编码，以卜.哪心是可以的哈夫 曼编码.|（!） 000,001,010,011,1（2 ） 0000,0001.001.01,1（3） 000,001,01,10,11（4 ） 00,100,101,1 10,1112. （5分）一个有向四g的邻接我存储如图1所示现拉深度优先查找遍历，从极点出 发，所得到的极点序列站啥？图i一个有网图g的锚接入（第2芯图）3. （8分）已知 个有序&为（12,18,2。,25.29.3240.62.83.9095.98）,当二分查找值为29和| 冲的兀素时,别离需要多少次比照才干香找成功?若采

43、用次序直找时,别离需要多少次比照小 能香我成功？4. （9分）按13、24、37、90、53的次序构成二叉平衡用，问答以f疑问:（1）该二义平衡树的高度是多少？（2）其根结点是谁？（3）左子树中的数据是啥？（4）仙子树中的数据是啥？三、算法方案题（共25分）1 . （10分）方案 个算法int increase,linklist *l）,断定带头结点单琏表l是不是是递减的, 如果回来i,否则回来0.2 .（15分）假定一义树选用一义铤存储规划存储试谀计个算法，输出该一义树中第一 条最长的途径长度，并输出此途径上各结点的值2005年武汉大学核算机学院855核算机基础历年考研真题一就汉大学:20

44、05年攻读硕士学位研讨生入学考试试题考试类别；计鼻机矗献类别代网:的5壬疝1一-x内容有必要否在m萩务上；凡善在试整之上的一概无效.数据规划有些一.单再选择茶交曝 二xi。分)i-翼片的叶间凌乱度与 有关.r.求解何魂的胡瑛和地址理数据枭的初始状忍:3.办法本身的雄度靶实施算法所住分的白喏空闺；、c.求弱讨我的蝶曜和实施三法所就强的存错空间、d-尊法本界防雄及和地址差毂据堪的初始状袤工总中潸环辿语支袅示的行列乩直为叫著只设头指计、融入队操作蚪”间复余震为.ahb.nco(!)o. o(n)3-为了中押内存空间的利闱辜和削减发生上溢的可膻性，也两个校共拿一片遑续的内存空间时，则 皮塔西栈蚪横底设在

45、这片同享内存空间的a.用端意与闾日*未是邦中向 j痛端d.任一位理4,日印一个稽逾部阵前二元限表如下；口二？),！工1/33二】)* 4,5.4. f5,l-31则其再置笔簿的三元筑表中第3个元素为.a. (2.1j) b. (33,5) c. qr2.-1) d. (2t3t4)5 , 一维教捐与线性表的网期是.a.两身为长度不相等b.后者的长度或定，席希的壬度可变c.商老的总度均可交 口.前者的长度用走r后者的长度可变6 . 一谏深度为k的华街二叉物，其每个尊终端(非叶子)结点的迎面因子为为b则嗨一支嘴共有个结点.a,卢4h. 卢c. 2人1d, 217 .在可n个叶子结点的哈夫曼叫中，其

46、结点息瞰为.a. 2(n-l)b. 2nc. 2n-1d, 2n*l8 .完成图的深度优先殂历算法时.*af要运用栈,。需要运用行列c潇要运用燧序且。不需要运用任何龛据需相轨当产列中的元素是逆序时r失速排序比 的功能差.山港排序 氐胃泡排序c,维入排序选押排序忖 设关阻字序列为广力总9区1452进行柞序的景中交流次效为6次，所来用的持序办法是,、结人绯序 日选择悻序c怏速博序6城撑序二.问卷题c共翁分l s分) 假定一摄富含n个结点的二叉轲氏至二叉排序斜乂是小根堆.那幺它可疑具有的鼠. 结点数是多少(不答应直复值)？弁阐明理由.口0分)试阐明若9为耨数时，则喳冷函数h(k)-k % p无法运用

47、.若p为俗数时情况有改变没有？为啥？计m矶兼他共3不第1天3.12分时要害码集结k53, 30. 37. 12. 45. 24. 961.从交二义博序树初步逐个刺进年个 要害码树立与集结k相对应的一叉挂序树又称二义查找树）bst,若冷望存到的bst高度 最小.（1） （2分）应选择下面的哪个作为谕入序列？a. 45, 24. 53, 12, 37. 96. 30b. 37. 24. 12, 30, 53. 45. 96c. 12, 24, 30, 37, 45. 53. %d. 30, 24. 12. 37. 45. 96. 53（2） （5分）查出相应的二叉排产树.（3） （5分）核算在等

48、赧率情况f成功均匀方找，叟三.界法方案垣17法需求用高堀港官描绘，扶26分）.l（14分）若一个数列中的任意一段（至稀有两个元集）3个元素的值均相同，咱们称之为等值 数列段，等值数列段中元素的个包加做数列段的长曳，阚有由n个元索构成的登数数列求 a中长度聂大的等值也列段的起址司末址,假定没有写道我先段.则埃出衿殊标忑.） （12分:工编写判别一个有向民罡有是 棵火的贯法.核算机原理有些一、单项选择震（鄙人列四个选项中迸卑一个正确香宴.柒小题i分.共15分）1. 一个16位无符号二进制数的扮演示围是，d. 一3二768戛768教据隼打点体系数据启线和仪末逻辑部件a. 065536 b. 0-65

49、535 c. -3268-32767:.可计汽机的软、硬件本钱进行打点是日,）先成的；a.用户程序b.沿言处置程序c.堆作体系d.3 .运算器&由多个部件构成的坦工的中心部件是（）.a.存放器b.数缗总线c.多益开关d.4 .在补码一位除法运算中，下列叙说正礴的悬（）.a.符号位和数据位一同参加运算b.符号位不好数据位一同参e运算c.符号位单独处置d.数据位单独处置5 .指令中给出的存放器中的内容是受作数的池址，此种方法称为（）寻址方法.a.当即b.存放器c.互接d.存放器直接6 .鄙人列的选项中,不属f cpu内部的篦件是（）.a. pswb.存放器c.控制存储器 d. alu7 .影前al

50、u运算速度的关费是（）a.进位的速度 b.选用的门里路c,计霓机的频灌d.核算的凌乱性8 .在计息机中，存放假指令的控制有铝器求虞于（）.a.内存0.外存 c. jche d. cpu9 .假定用16kx8的存偌器芯片构或128kxi6的存催器需要该芯片（）.a. 8 片b.16 片c.32 片d.64 片10 .设存储器的容量为128kx 8若按字（16位）堀址，则该存储器的地址空间是（）.a. 32kwb.64kwc.128kwd.256kw11 .盛欲4储器的记载方法一般选用（）.a.归零制b.不归零制c.调相制d.改进的调频制12 .选择通道上可以联接若干个设各，其数据传送是以（）为单

51、位进行的.a.位 b.字节 c.字d,数据块13 . cpu呼应dma恳求的条件是其时（）实施完.a.时钟周期b.总线周明 c.指令周期d.程序14 .中止系共同般是由相应的（）构成的.a.硬件b.软件c.硬件和软件 d.固件15 .在pc核算机中的数据总线信号状况是（）a.幽向双态的 b.双向双态的 c.单向三态的 d.双向三态的二、填空题（每空1分，共15分）i.计识趣硬件体系包括cpu、（）和输入.端出及各.而cpu包括运琳器和（）,2 .假定浮点数运算成果尾数有些呈现il1xx时需要进行（）,呈现olxx时需要进行（）3 .控制若根据方案办法的不一样可以分为（）拄制器和 （）控制器和pl

52、a控制器，4 .核算机构存储系共同段分为三层:（）、（）和外存，5 .需要费新的存储器是动态存储器.一股动态存储得改写的周期大约小丁（） ms.6 .虚接存储器在运转时.cpu根据指令生成的地址是（）地址,该地址经过转涣后构成（）地址.7 .磁盘格局化就是在磁盘上构成（和扇区的进程.8 .核算机中数据传送控物方法有查洵方法、中新方法、dma方法、（）和外闱处岂机方法.9 . cpu呼应外设的中止恳求条件爰:中止未屏牧.（）和其时指令实施完.10 .接标语存券的遍址办法有独立编址法和（）编址法，三、运良办法翦（计完旭需求写出核算进程.共15分）l（5分）设浮点数的阶码为4位（含|位阶符，补回标明

53、），是数为s位，含i位尾数行号）.若xyxoioii（xh, y=24xo.hooioo,按浮点运算进程核算x + yc2. （10分）设定点数的宽曳为n位（不包括符号位），试画出补码一位乘法（x） （y） -a的操 作流程图.四、方案鞭（共15分）设ram存储器芯片的容为16kx8, rom存储器芯片的容量为32kxb.若用这两种芯片内成 k8kxi6的存储器，其间ram为64kxi6,开始地址为ooooh,问；1 .（2分）至少需要多少位地址线？2 . （2分）rom芯片和ram芯片各需多少片？3 .（3分）若存储器的地址是按字接连编址的，rom的开始地址是多少？4 . （8分）且出存储器

54、与cpu的联接示意图.五，分析题（共15分）有5个中新源di、d2、d3、d4和d5,初步的中止优先等级从高就任别离是i级、2级、3级、4级和5级.假定每个中止源有5位中止.屏蔽玛，用“0”质示中止源翻开，”标明中浙源屏蔽, 可以经过设置屏蔽码改动中止源的优先等级.改动后的中止源从高到低的中止优先级为d3、d4、 d2 dl d5.假定5个中止源一起发生中止，问:i.62分）没有改动中止屏蔽码时中止处置的次泮是啥？2. （5分）写出改动后的中止屏蔽码。3. （3分）改动中止屏蔽码后的中止处置的次序是啥？4. （5分）画出处置机呼应中止恳求和实践实施中止效能程序进程的示意图.核算机法础共3页加3页核算机基础共3页第2页