全国名校计算机基础综合考研真题汇编

TOC\o"1-5"\h\z1,首都加范大学计4机学科琮合历年考研真题 52014年首都师范大学90X计算机学科综合考研真题 52013年苜都师范大学908计算机学科综合考研亮题 142.浙江工商大学计算机柒础综合历年考研支鹿 222015年浙江工商大学845计R机基础综合考研真题 222014年浙江工商大学845计算机基础综合考研真题 242013年浙江工商大学845计匏机基础综合考研真题 273,江苏科技大学计党机基础综合历年号研其鹿 292014年江苏科技大学845计算机基础综合考研真题 292013年江苏科技大学845计算机燧础琼合考研「题 35.汕头大学计算机基础综合历年考研真题 482014年汕头大学830计停机基础综合考研真题 482013年汕头大学830计算机基础综合考研或麴 54.重庆理工大学计算机学科〃业盛础综合历年考研真题 602014年前庆理匚大学810计算机学科专业基础琮介考研典典 602013年正庆理工大学809计算机学科专业施础琮合考研真题 656,沈阳*P范大学计甄机学科专业基础标合历年考研真题 702014年沈阳师范大学868计算机学科专业基础综合考研真题 702013年沈阳师范大学868计算机学科专业基础综合与研自腮 74.东北财经大学计算机综合历年考研真题 782014年东北财经大学809计算机综合考研真鹿 782013年东北财经大学809计算机琮合考研真题 86.全国硕士研究生入学统一考试408计算机学科专业基础绘合历年考研五密及详解 922012年全国硕士研究生入学统一考试408计算机学科。业基础踪合真题 922012年全国独士研究生入学统•芍试408计W机学科专业基础综合真题及详解 1012011年全国硕士研究生入学统考试408计算机学科专业植础综合真题 1192011年全国硕士研究生入学统一考试408计区机学科专业基础综合真盟及详解 128.其他名校计算机综合历年考研真题 1462014年中国科学技术大学408计算机学科专业雁础综合考研出超 146说明:精选了18套名校计算机够合历年考研真题.1.首都师葩大学计算机学科综合历年考研真践2014年首都抑范大学908计算机学科综合考研真腌首都师范大学2014年攻读硕士学位研究生入学考试试卷考试科目代码；908 考试科目名称t计耳机学科综合请将答案注明题号写在答题纸上，试题纸上做告无效。第一部分数据结构(共75分)一、单项选择题(集题1分,共25分).算法是解决某一问题的有限运算序列,它必须具各输入、输出、_①可行性 ②可移植性 ③有穷性 ④确定性 一⑤稳定性(A)①©③ (B)①®® (C)①©⑤ (D)级泡.设rear是指向非空的带头结点的单循环箧表健尾结点的指针,若要副山链表第一个结点,则应该执行.s=rear：rear=rear->next;free(s);rear=rear-〉next：free(rear);rear=rear->next->next;free(rear)：s=rear->next->nMt;rear->next->next=s->next;frre(s);.长度为n(n〉D的单磕表上,在值为*的结点后面插入一个新结点的算法的时间发杂度为 ・(A)0(n) (B)0(1) (C)0(n1) (D)o(nlogn).利斯一个表达式中左右括号是否或对出现的算法，采用—这肿拔■雄构.好.(A) (B)<- 7 ))域队.修序槿S中元素个数是(A)S.lop-i-S.base...• (B)o..r.ja.(C)S.top+S.base (D)S.top-S.base.若循环队列的存"空间大小为6,当前front和rear的值分别为】和4,生疗两次Engeue和一次DeQueue后，front和rear的值分别是.(A)铀0 (B)2和6 (C)3和5 (D)o和2.一棵度为4的M中，度为1、2、3、4的结点个数分别为4、2、1、1,则读树叶子她用的个数是.(A)5 (B)6 (C)7 (D)8.任何一朦荐交二叉树中，•.丁一•：： 历中的相对位置 .(A)都会发生改变 (B)不会发生改变(C)有可能会发生改受 (D)部分会发生改变考试科目代码：908.在一棵先序线索二叉树中,结点*p的前驱可能是(A)与的左核子(B)”的右孩子 (C)与的双亲 (D)*p的右孩子的右孩子.具有n个顶点的连通图的生成树一定有条边.(A)n-1 (B)n (C)n+1 (D)2n.如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是(A)完全图 (B)连通图《C)有回路 (D)一棵树.用DFS遍历一个有向无环图，并在退出DFS时打印相应的顶点，则输出的顶点序列是.(A)拓扑有序(B)逆拓扑有序《C》顶点值有序 (D)无序.在具有n个连埃存储单元的循环队列中，队满时共有 个元素。(A)n+2 (B)n+1 (C)n (D)n-1.将10个元素散列到100000个单元的哈希表,M产生冲突.(A)一定会 《B》一定不会 (C)仍可能会 (D)以上都不对.若特排序数据已经有序，排序算法花费的时间反而♦多.(A)起泡 (B)希尔 (C)快速 (D)堆.若有100000个数据，只想找出从小到大序列中前10个数据，用方法最快.(A)堆排序 (B)希尔 (C)快速 (D)面单选择.如果对含有n(n>l>个元素的线性表的运算只有4种：删除第一个元素：删除最后一个元素；在第一个元素前面插入新元素；在♦后一个元素的后面插入新元素，则♦好使用«(A)只有尾结点指针没有头结点指针的循环单域表(B)只有尾结点指针没有头结点的非循环单集表(C)只有头结点指针没有尾结点指针的循环双镰表(D)既有头结点指针也有尾结点指针的循环单链表.关于哈希查找，错误的说法是.(A)不存在量好和最坏的哈希函数，需视具体情况选择(B)用能地址法解决冲突时，杳找任一元素的时间是相同的(C)用链地址法解决冲突时，同义词在同一个惬表中(D)哈希表的平均查找长度与处理冲突的方法有关.数组的物理结构,需要存储以下内容：①起始地址②每一维的维界③地址计算所甯要的常数④下标 ⑤数蛆大小(A)①©③ . (B)③© (C)①@⑤ (D)③®⑤.已知一个栈的进栈序列是ABC,出校序列是BCA,实施的栈操作是(A)push.pop.push,pop.push,pop (B)push.push.pop.push,pop,pop(C)push,pushtpop.pop.push,pop (D)push,pop.push.push.pop.pop21.对于链队，在进行11除操作时.(A)仅修改头指针•(B)仅修改尾指针(C)头、尾指针都要修改(D)头、尾指针可能都要修改22.线僵二叉轲是一种 结构(A)逻辑 (B)线性(C)物理 (D)履序23.哈夫曼树不具有的特点是 (A)帝权路径长度♦小的树(B)有度为0的结点(C)有度为1的结点(D)有度为2的结点24. 不能判断一个有向图是否存在回路.①拓扑排序 ②深度优先遍历③找♦短路径 ④找关倭路径(A)(D® (B)②®(C) (D)(D©25.有一个有序表为｛1.3.9,12,32.41.45.62.75,77,82.95.99|,当采用折半杳找法查找关键字为3的元素时，次比较后者找成功.(A)1 (B)2 (C)3 (D)4二、填空题(每空1分,共10分).然性表L=(al,a2an)用数组裹示，假设删除表中任一元素的可能性相同，则删除一个元素平均需要移动个元素..在单健表I,中，表示指针p所指结点有后继结点..由3个结点可以构造出 榇不同的二叉相(不考虑结点的值)..T和P是两个字符串，在T中查找等于P的子串的过程称为..采用数姐tree[1..18]存放一棵完全二叉树,则结点tree[7]的右段子是..采用二叉废表结构存储二叉树，若要交换所有分支结点的左右孩子，应利用 遍历方法♦合适..iTn个顶点的有向图,至少有一条弧才可能是连通的..数组(98,36.-10,2,40.20,7,12.24),按步快3进行一超希尔排序的结果序列为一..假设有k个关候字互为同义词，若用线性探测再散列的方法处理冲突，至少要进行次探测..按一遍历二叉排序树,可以得到按值递增的关键码序列..f三；筒答题(共21分).设计一种数据结构，用来表示学生的基本信息：学号、姓名、出生年月日、班级、专业、爱好.请说明设计理由.(3分).什么是排序算法的稳定性？请举例说明.(3分).一个8行6列稀疏矩阵的三元Sfi表为：(1.3,5)⑵6,8)(4,3,15)(4.1,21)(5,3,567)(7,1,4)(8,6,3).(1,3,5)为第1个三元组，请同转置后(3,1.5)是第几个三元蛆，请说明原因.(3分).分析下列程序段的时间复杂性.(3分)voidunion(List&La,ListLb){La_len=ListLength(La); 〃计算表La的长度，假设值为naLb_len=ListLength(Lb); 〃计算表Lb的长度,假设值为nbfor(i=l;i<=Lb_len;i*+)(GetElen(Lb,i,e);if(iLocateElenda,e,equal))ListInsert(La,++La_len,e)：)}.如何定义循环队列的物理结构？清根据你的定义说明如何计算队列中有多少个元素.(3分).依次*入以下关键字t5.36.24,73,8.20,66,94,1,18.构造3阶、轲.(3分).按层序给一榇完全二叉轲中所有结点樵号，举例说明如何找到第i个结点和第j个结点♦近的共同祖先.(3分)四、请判断下列说法是否正确，正确回答“是"，不正确回答“否”(每廖1分，共10分).■序表在♦序存催方式下插入和删除效率太低，因此不如镰式存储方式好.为提高内存利用率，两个栈共用一段连续的存储空间.为减少溢出机会，应把两个税的枝底分别设在这段存储空间的两娴.由二叉树的先序序列和后序序列可以惟一地确定一棵二叉树.下三角矩阵压缩存储后仍可以实现随机存取.串“abc”共有6个子串.数据结构的抽象数据类型操作的定义与数据的物理结构有关.寻找关曼路径是在拓扑排序的基础上完成的.♦短路径一定是面单路径.(100.85.98.82.80.77,66,60.40,20,10}是一个堆.二叉排序树的查找效率和二叉排序树的高度有关五、嫌合运用题（9分.选做其中一H）.数组child[n+l]中依次存放了具有n个结点的二叉树T层序遍历时输出的诲个结点的子轲个数，child（O）没有意义.请写一个算法判断该二叉料是否是完全二叉树.（9分）.无向图G的存储结构为邻接表.请写出判断图G中顶点u与顶点v之间是否有路径的算法.（9分）邻接衰定义为：typedefstructArcNode（intadjvex; 〃邻接顶点structArcNode*nextarc;//指向下一条列的指针）ArcNode：typedefstructVNode（char data[5]： //顶点信息ArcNode♦firstarc://指向第一条依附顶点的弧的指计IVNode,AdjList[MAX_VERTEX_NIM];typedefstruct{AdjListvertices;intvexnum.arcnua;//图的当前顶点数和弧数）ALGraph;第二部分计算机组成原理（共75分）一、选择鹿（每题1分，共15分）.冯•诺依曼机工作的基本特点是,（A）多指令流单数据流 （B）按地址访问并顺序执行指令（C）堆栈操作 （D）存贮器按内容选择地址.计对8位二进制数，下列说法中正确的是.（A>-127的孙玛为10000000 （B）-127的反码等于0的移码（C）+1的移码等于T27的反码 （D）。的补码等于-1的反码.运算翳虽然由许多部件蛆成，但其核心部件是.（A）数据总线 （B）算术iS辑单元（C）多路开关 （D）累加寄存卷.在定点二进制运算器中，减法运算一般通过来实现.（A）原码运算的二进制减法器 （B）补码运算的二进制减法卷•（C）补码运算的十进制加法舞 （D）补码运算的二进制加法器.若浮点数用补码衰示，则判断运算结果是否为规格化数的方法是.(A)阶符与数符相同为规格化数(B)阶符与数符相异为规格化数(C)数符与尾数小数点后第一位数字相异为规格化数(D)数符与尾数小数点后第一位数字相同为规格化数.下面浮点运算器的描述中正确的句子是 .(A)阶码部件可实现加、减、乘、除四种运N(B)阶码部件只进行阶码相加、相减和比较操作(C)尾数部件只进行加法和减法运算(D)尾数部件只进行乘法和减法运算.假定用若干个2kx4位芯片组成一个8k*8位存储器，则地址OBIFH所在芯片的最小地址是・(A)OOOOH (B)0600H(C)0700H (D)0800H.存贮单元是指.(A)存放一个二进制信息位的存贮元<B)存放一个机II字的所有存七元集合(C)存放一个字节的所有存贮元集合(D)存放两个字节的所有存贮元集合.动毒存储卷(DRAM)依靠存储信息.(A)门电路 (B)触发器(C)多路开关 (D)电容电荷.下列因素下，与Cache的命中率无关的是.(A)主存的存取时间 (B)块的大小Cache的蛆织方式 (D)Cache的容量.程序控制类指令的功能是・(A)进行算术运算和逻,运算(B)进行主存与CPU之间的数据传送(C)进行CPU和I/O设备之间的数据传送(D)改变程序执行的♦序.指令系统采用不同寻址方式的目的是,(A)实现存贮程序和程序控制(B)缩短指令长度.扩大寻址空间，提高馆程灵活性(C)可直接访问外存(D)提供扩展掾作码的可能弁降低指令译码的难度.在CPU中跟踪指令后继地址的寄存器是.(A)主存地址寄存卷 (B)程序计数器(C)指令寄存器 (D)状态条件寄存器.减少指令中地址个数的办法是采用.(A)寄存器寻址 (B)寄存器同址(C)变址导址 (D)隐含寻址.微程序控制器中,机器指令与做指令的关系是・(A)每一条机器指令由一条微指令来执行(B)诲一条机器指令由一段做指令编写的减程序来解稀执行(C)每一条机器指令组成的程序可由一条猫指令来执行一条微指令由若干条机修指令组成二、尚答同(每题5分，共20分).在浮点数的IEEE754格式中，其尾数部分的表示采用隐蔽位技术,请解释何为除蔽位？其目的是什么？.DRAM存储器为什么要刷新？刷新方式有哪几种？.为什么多体低位交叉结构存储器可以提高访存速度？.与组合逻辑控制器相比，境程序控制舞有何优缺点？三、分析计算题(每息5分，共2吩).设十进制数尸(-12S.75)Ml-10,调回答：(1)写出x的16位补码的机内定点数表示；(2)写出x的IEEE短浮点数格式..设计算机的主存储器为64Kxi6位，采用直接映像方式的高速缓存容量为】KT6位，穿埃大小为4字.(1)主存储器的地址分为唱几个字段？每个字段的位数是多少？(2)高速依存地址的标志字段、块号和块内地址字段分别有多少位？(3)高速缓存中可装入多少块数据？.假设CPU执行某段程序时，访问CMheSlOO次，访问主存900次，已如Cache存取周期为。ns,主春的存取周期为250ns.求Cache的命中率和平均访问时间.4,假定一个32位的微处理器，指令字长32位，每条指令由两部分组成，其中第一个字节为操作码，剩余的为立即数或操作数地址.(1)可直接访问的最大主存空间是多少？(2)程序计数器和指令寄存器各需要多少位？(3)该微处理器运算电路是多少位？四、除合应用息《每题10分，任选2题，共2诩).设某机配有基址寄存器和变址寄存器，采用一地址格式的指令系统，允许直接和间接寻址，且指令字长、机器字长和存储字长均为16位.(1)若采用单字长指令，共能完成】05种操作，则指令可直接寻址的范围是多少？一次间址的寻址范围是多少？画出其指令格式并说明各字段的含义.(2)若存储字长不变，可采用什么方法直接访问容量为16MB的主存？画出其指令格式并说明各字段的含义..设某机为定长指令字结构.指令长度12位，每个地址码占3位.(1)请提出一种方案，使谟系统包含4条三地址指令,8条二地址指令，180条单地址指令.<2>能否构成三地址指令4条，单地址指令255条，华地址指令64条呢？.已知某CPU和存储芯片组成的系统框图如下，其中A15〜A0为地址总线,D7〜D0为数据总线，请看图回答以下问题.(1)图中ROM存贮芯片的容量为RAM存贮芯片的容量为(2)现已实现扩展的存贮容量为(3)片选逐辑CS1的逆管表达式为片选运螭CS2的逻■表达式为(4)写出每组石片的地址范围(16进制表示)起始地址 终止地址第一蛆： 第二蛆， (5)该系统的片选控制采用的是译码方式.首都师范大学2013年攻读硕士学位研究生入学考试试卷考试科目代码：908 考试科目名称：计)1机学科综合 满分150分请将答案注明题号写在答题纸上.试题纸上做答无效第一部分数据结构(共75分)-.单项逸打18每分，共20分).下列关于数据的逻辑结构的表述中.是错误的.①数据的逻辑结构与各数据元素在计算机中如何存储有关②逻辑结构相同的数据,可以采用多种不同的存储方法③定义逻辑结构时需要为虑物理结构(A)(D® (B)@@> (C)— (D)®.一个具有515个结点的二叉树的高h为.(A)9 (B)10 (C)10—515 (D)11—5153.设极S的初始状态为空,元素I、2.3.4.5.6.7依次入枝.出枝髓序为4、3.5.2.7.1.在搽作过程中.段中元素通多时有t.(A)4 (B)5 (C)6 CD)7.循环队列qu的队满条件是.(qu.rear«l)%MAXSIZE-(qu.front*I)%MAXSIZE(qu.rear*l)%MAXSIZE=qu.front*I(qu.rear^i)、HAXS1ZE=qu.frontqu.rear-qu.front.两个串相却必有串长度相等且(A)串的各位置字符任意 (B)阜中方仅置字符均对应相希(C)两个串含有相同的字符 (D)两个事所含字符任意.以卜数据结构中.是M0性结构.(A)线性衰(B)图 (C)数m(D)栈.根据使用频率为5个字符设计的哈夫曼编码不可能是.(A)000.001,010.Oil.I (B)0000.0001,001.01.1(C)000.001.01.10.Il (D)00.100.101.110.111.在表示乘车线路的有向图中,可以通过以下搜索方法找到换乘次数最少秉车方案.(A)深度优先搜索 (B)广度优先搜索(C)先序搜索 (D)后序搜索.棵—k的中曲一叉机若饵个/叶子蟀点.的平曲因子均为0.则诬柯其玉_个结由.(A)2*-1 (B>2*' (02'-1UH2lI。.以卜解作的W法时间爱杂性不是0《向的是.(A>&；1有n个站立的有序单也表中插入一个新的结点并使能表仍惘有序(B)逆位停建，,有n个结点的隼斑表(C)在K/.Q为n(nI)只有尾结点指针r的不带头结点的惆环单城表上,那除最后个元索(P)在有n个元素的循环队列中取以尾元素的值.三维数组A的每个元素占5个字节,元素a,仆的下标i*j.k的范南分别是。到4.0M5.0到7.以行序为土序顺序存储在1000开始的存体维元中.元素Af'的地址是・(A)1825 (B)1535 (C)1620 (D)2110.图中所有项点的废敷之和尊于所有边敷的—J8.(A)12 (B)1 (C)2 (D)413,已知某有向图GMV.A).其中V=fvl.v2,v3.v4.v5,v6|.A=«vl.v2>.<vl.v4>.<v2,<v3.vl\v3,“.、v4.v5>.<v5.v2Xv5,v6»,G的拓扑序列是.(A】v3,vl,v-l,v5,v2,v6 ，B)v3,v4.v1,v5,v2,vfi(C)vl,v3.v4.v5,v2,v6 (D)vl,v4,v3,v5.v2,v6M.个有向伯如图所示，则从顶点a出发进行深度优先渴历不可能得利的DFS序列为(A)mibcfc(8)adcefb (C)adcbfe(D)adefcb15.对线性表进行折军音找时，要求线性表必须.(A)以廓序方式存储 (B)以顺序方式存储,且结点按关a?字有序抵列(C)以链我方式存M (D)以镰表方式存健，且结立筱美堪字有序揖例16.5列排序方法中.在一趟排序结束后不定能选出一个元素放在其最终位置上.(A)良接选抨抵序(B)皆泡扑序(C)归件抵序(D)用排序17.记录的关撰字为{46.79,56.38.40.841.进行快速柞序.“第一个记录为星处得到的第一次划分结果为.(A)(38,40.46.56,79,841 (B){40,38,46.79,56,84)(C)|40,M46.56.79,84[ (D)!40,38,46,56,84.79}.设图中有n个顶点e条边,栗用邻接表表示图，遍历图所需要的时间为――..(A)0(n*) (B)0(n*e) (C)O(nXe)(D)0(n).以F序列不是塔的是.HOG,85.98.77.80,60,82,40,20,10.66)（100.98.85,82.80.77.66.60.10.20.10110.20.40.60.6fi.77.80.82.85.98.IO<»i（I））1100.85.40.77.80.60.66.98.82.10.20.当采用分块齐扰时.数抠的空猊方式为（A）数据分成若干块.一块内做据有成（B）敷据分成若干块,每块内数据不必有序.但块闾必力行FT.肉块内始人（成母小）的代据组成索引块（C）数据分成若干块.每块内数据仃序,肉块内最人（蜕般小）的依据组成东引块（0）数据分成若干块，每块（曲:最后一块外）中的数据个数需相同—.填空胭每空1分，共10分）.若果用潮序春储结构,在长度为旧的N空投性衰的的第i个元靠前插入一个数加元案，i的取值范围是..已如二叉树的层的两近遍列为AHJCEFG.中序中历序列/0BCAFEG,其后序电历序列为3,若将n阶上三箱矩阵A按列优先腐序压制存放在维数组中,第一个非零元素当存于Ml］中，则於。故到Mk】中的非零兀素“jWn.iWj）的卜标I、j与k的对应关系是.4.嗫优一叉树（编夫曼树）中共（H7个结点.则一叉树上有 个叶子结点.5,对棵完全文树所有结点从上到卜从左到4编号.摭号】和编切的两个结点处于同层的条件是..已知按后序遍历一义将的结果为ABCD.有搐不同的一叉树可以得到这遍历结果..一憬m阶的B树中,通入个新关设字时若产生结点分裂.刚读结点原有个关犍字..若个非逆通的无向图被多有28条边，则该无向图至少在一个球点...图的广度优先遍历需要利用这种数据结构来实现..利用大小为MAXSTACKSIZE的数组百篇一个栈时,若tap也表不机空，条料表示栈源二、商答小（共20分）比较顺序表和鞋表的特点.（3分）2,假设CPU每眇处理10’个指令.对于输入规校为10•的问题,时间代价T（n）=2n：的算法要运行多少小时？<3分）3.将关键字序列（7、8.30.II.18,9.14）敢列存储到敢列表中，般列表的存储空间是个下标从0开始的长度为10的维数组.散列函数为H（key）（keyx3）MOD10.处理冲突采用线性探测再散列法.（3分）请将答案注明题号写在答题纸上，试题纸上做答无效4. 画出FIS对胸外邻接女.（2分）（2）什么是最，NI成树？根据你的都接我.找出该图的一探最小生成树“（5分）5,依次输入序列（62,68.30.61.25.M.53.47,90.84）中元素,生成-梅中荷义排序树,并计算杳找成功时的平均有我氏度ASL（4分）四.，「廉卜刘说法,1确,正瑞回务“是不正确回省“否”每魄I分,共10分，!在边々示活动（A0Q网中,任何一个关键活动的延期先成，郎会’?以整个1!丫蚪延购完成.4侬E衣小活动的有向图中,通过快速州序的方法可以确定哪个活动先做.消除通仃不定要用枝.只在能够用程序设计语声描述的算法是仃效。法.矩辉压缩存储是为了节省空间,可能需要付出时间代价.堆是一株平衡-XW.数据的物理结构是指数据在内存的存储方式.在完全一义树中,左仃右孩子的结点.一定是叶结点.义树是度为2的4件树.数据结构研究散据的逻辑结构.物理一陶和县本黑作五,琮台北用做（共15分,请先写出存储结构）n（Jn个始点的完全一义树存放在ft数组中（上标为。的单元不用）,1讪找中冷两历过程中结点V后继结点的算法.（7分）.循环队列的存储空间若发生以下变化：队满并需要插入新元素时存储空间犷大一倍，哨曲写入队操作；StatusEnUueue（SqQueue&Q,QEIeaTypee）（8分）第二部分计算机组成原理(共75分).单沌选杼之每独2分,共30分).某机字长32何.其中I位符号位.31仿故值机若用定卢.小数表示.喇展大正小热为(A)♦(1-2、) ⑻+(C)2U (D)2"2.float型数据通常用IEEE751单精度浮点效格式表示,若编译器将Coal型变Tx分配在一个32位浮点寄存SSFR1中,且x=T2.25,则FRI的内容足.(A)C1440000H (B)C2040000H(C)C184OOOOH (D)CIC20000H.如果浮点数的能数用补码表示，则下列中的尾数是规格化数形式.(a)I.noon (B)o.ouio(C)0.01010 (D) 1.00010.在浮点加减运算中，对附的原则是<A)人阶向小阶对齐 (B)被加数向加数对齐(C)小阶向大阶对齐 (D)加数向被加数对齐.若特发送的信息码字为U10QQ11,生成多曲式G(x)=X,+x'+X+I•则什口出的CRC校装码为.(A)1110001101101 (B、HlOOOlHiOlO(C)11100011001101 (D)111000110011010.动态RAM的刷新是以为单位进行的.(A)存储单元 (B)存储矩阵行(C)存储矩阵列 (D)存储位.假定用若干个2kx4位的芯片组成一个8kX8位的存储器系统.则地址0B1FH所在芯片的最小胞母是.(A)0000H (B)0600H(C)0700H (D)0800H.下例说法中不正确的是.(A)多体交叉存储器结构是为了扩人存储器的容，(B)主存'Cache之间信息交换的单何是数据块(C)高速接存八有较高命中率是利用了程序的局部性质理(D)在Cache的全相联映象方式中,Cache块的标记字段记录的是调入的主存块号.卜列因者中,'jChcM的命中军无美的是.”）上存的存取时间 （B）块的大小Cath。的繁象方式 （D）Cachi•的容V0.指令后就中果用不同寻知方式的口的主要是 .（A）可良接访闷本存＜B）找展操作码Jt博依指令译码的速度（C）实现科'华存储和程序控制⑺）缩加指令长度，扩大寻址空间，提高编程灵活性H.偏移寻址通过将某个新存IS内容5个形式地址相加而生成有效地址.下列寻址方式中,不雇于偏折寻址方式的是.（A）间接寻址 《B》基址寻址（O相对寻址 . （D）变址寻址12..邺时序系统提供的三糕时序信号空.IA）—期.机圈周期,除冲（K）指令周期.机器周IW.时许做明（C）指令阉知，节拍.脉冲（D）指令冏期.微指令周期.时钟周明.微理序控制器中,机器指令％微指令的关系是.（A）句条机器指令由条微指令来执行（B）句条机黯指令由段做指令褊成的微程序来物料执行U）段机器指令组成的程序可由一条微指令来执行（0）一条很指令由若干条机罂指令组成.假定不采用Cache和指令预取技术,则在卜列有关指令执行的叙述中,甘I误的足.（A）每个指令周期中CFU都至少访问内存一次（B）拉个指令周期一定大于或等于一个CPU时钟周期f＜：＞空微件指令的指令周期中任何寄存器的内容都不会被改变ID）当前并序在屋条指令执行结束时都可能被外部中勘打断.卜列说法中止确的是.1A）做程序控制方式和组合逻辑控制方式相比.前者可以任指令的执行速度更快（B）若采用微科序控制方式,则可用uPC取代PC（C）水平型微指令采用分段班码的格式是为了缩短微指令的K度（D）指令周凯也称为CPU周期..■答胭（每月3分,共15分）I，计一机中所表示的数有时会发生0出.其根本原因足什么？对干双苻号如何切断溢出？.存储器系统采用层次结内就次什么问也？实现存储器层次结构的先决条仃是什么？用什么来度・其效率？.为什么多体低位交叉结构存储器可以提高访存速M?1.指令和数据都存放在土存储港中,如何识别从主存中取出的的指令还比数据？5.与城合逻期控制器相比,曲柝序按制器有何优缺点？3.琼合应用股，每收10分,共30分）I.有两个辩敷x和y.x=-66.尸-80.采用补码形式（含的符号何）表示,x和y分别存放在寄存器R。和R1中.另外,汪。两个寄。器R2和R3.RO.RL心和R3都是8位的寄存器.请何答下列同胭：（薯求出算用上六进制在示进制序列）（1）寄存嚼R0和R1中的内容分别居什么？（2）x和y相加后的结果存放在R2寄存器中,寄存器虺中的内容是什么？此时,湛出标志付阱是什么？符号标志位SF是什么？进位标志位CF是什么？（3）x和y相减后的结果存放在R3寄存器中.寄存器R3中的内容是什么？此时,温出标志位0F是什么？符号标志位SF是什么？进位标志位CF是什么？.箱令字长为12位.每个地址码为3位.采用犷履操作码的方式.设计4条地址指令.16条二地址指令、64条一地址指令和16条《地址指令.（I）给出一种微作码的犷展方案（2）画出指令译码逻辑.（3）计党操作码的平均氏度..CPU结构如图所示,包含一个累加寄存器AC.一个状态寄存器以及分别用a,b、c和件示的其它四个寄存器,各部分之间的连坡表示数据通路.清头表示信息传送方向.（1）标明图中a、b、c,。四个寄有餐的名称.（2）简述指令从主存取到控制器的数据通路.（3）简述数据在运算照和主存之间进行存/取访问的数据通路.

2015年浙江工商大学845计算机基浙江工商大学2015年全国硕士研究生考试试卷（A）卷专法科EL845考洪对同：3小时计算机基地疗合（敷脚结构5s.也护系统5G）专法科EL845考洪对同：3小时第一部分St据结构（75分）算法皿用基：（共4小国，父小•10分,共40分）（10分）已知二JC*的光（的）序龙历序列为ABCDEFCK,中序遴历序列为CBEDFAGH.1S山此一文«•k蛤出其好序■历序列.（10分）对关H干序列（712.817.611.213.904.106.45.598）进行城柞序♦济给出调整后峭初始餐小城."0分）武用权集合！12,4,5,6,1,2）构造哈夫曼树.并计算哈大如期的用权路冷K度.（10分）ACE同如卜所示，未关区路桥.-.算法设计题：〈共35分）1、（10分）Q-榇—义设为在幢悄内，结点结构为Jchild|（tesirchiid.2计个算法.前（先）序序列中处于第k个府亶的结点.（10分,已如我性口中的元素以值遹书有序拎制，片以*®&<r存住结构.求耳一算法,副除表中所有人丁x且小Ty的元第（著表中不在这株的元本）网时杆放横射除结点空间.（15分）国设计•一个算法,求山给定字符串中的•对体字符！T.«*."efghiihgfabc-.最KF标字符率,fghiihgT.•opqrslww".UK?对称字符本•是-abcdefghijk,.无•时焦字灯事、第二部分操作系统（75分）--以交公（每空2分.共20分）.从向I种上看.每个进程由二部分融成，它力让 .和..嘉蜕中存在多个班这些班以对共事修*的使用存在事不同的相4制的美系.一“雄 一一关系,另一种地 关系.3、地如欢财必指将脚序中的城址》｛帙内内存中的地计.在分更胃理最蜕中.为实现地给转换口工了控制寄存给,其中存放的缎 在内存中的起始墟址.1/0Q&技信息存取的♦付进行分类,可分成决和字符做备.磁你同丁校瞽.Kl/Ctam主要采用控制方式.

（共3小题.w小-5分15分）（5分）在创建一个进程，件系统需要完成的士蜜1件给什么？（5分）操作系蜿中存在晴厘二级湾度.它们各有何作用？（5分）文件物■结构中存在嘟二即站构？着有何优劣？Z.蚌合H（共3小国.乂加分）h（15分）若某务收果同分页式存怯管理方式.页表放仓内衣中,系统中流有怏*（TLB）.（I）油出谖内在管理系统的逻•地址到物现地H的替换示意用.（2）页面大小为4KB.建堂地批空间为24KB,页表的内弁女卜衰,r・一一一—一r甲帧弓］。1A50010002B10005C|3 0006AJ40008F1I5,-3FD00]划邃《1地卅0x3005济换成物理皿为多少？恰比计算过界（01发示十六遗整数,初珂地处怯枭4求也以十六进制我示）.（3）S果访向一次内。妥I5n*.快收拘命中率为85、.并找快发的时闾为0.5ns.计霓谍系统的有成功问时间.（15分）破疝共。200个料面<0'199）,它刚刚从92号修造修刎98，）他10完成*假设此时系统中*侍5问磁型的出道序列为，190.97. 90. 45. 1S0, 32. 162. 108, 112. 80.试给出果用卜列畀法后破头楼动的■了.并计算difiifc*.I）FCFS算法:2>SSTF算法;3）SCAN算法;4）C-SCA'X法;5）100K算法（10分）现有赣人进NPA.计算进NPB,*出班内PC广发执行.三个选同共享两个螳冲区.如出所不：BuRcrl BufTcrlBuRcrl BufTcrlPAR次*入一个敢据.放入到Buffed中,Buffer1人小为N1.PB15次从Buffe”中拿山一个依据计算,然后将妖果收入Buff”2中，Buffer人小为N2.PC毋次从BMm2中拿出一个敢再道行*山・要求果用wartagn«l（成P.V）排作.设或合适的P!步机*.保证这二个进出的对步执行.对Buffed.Buffer2要求立斥必修・

浙江工商大学2014年硕士研究生入学考试试卷（A）卷考试科日：845计怵机基磁烧令 总分।（150分）考试时Wh3小时第一■分或据结构（76分＞海齿及（共5个小■,冤小员6分,共30分）I.分析卜面代码段的St杂度.sSIM«0：vhile（hub＜n）Ii":sunri;I.若a.b.c依次压入堆枚.UPS出所有可倦的出Ift序列.3.已知一个义料的中序遑历站乘她TFXIRAMLPK.后序遑历姑果姑TXFUU0CPR.请画出央二义村.4,请府述数列成数中M次冲突的常用方法.5,请耳出卜面无向图的转接矩阵和郛接我.二.蹿合分析同（共3个小题,年题15分，扰45分）.请役计一个由数intIsMatcMchar*expr）.来判别表达式中括］I（超括IN括仪,。，、方括级'口'、花招冕'（卜3#＞舱否正瑜配对.若正确此时.■出I.否购■出0・.璃改计一个库法内定两履二义鞫是否相似,两棵一又树相似.»£＞（1）如果它旬岳为空或糊只有一个节点।（2）切果它的左子材相螟井且右干树相似..一物很公司设在不钝城市的中特站之间的拓扑结构可用图来我示.假定出用匏推矩阵表示,谪设计一个算法，■出中转站Si到中转站SJ的所存筒单隔及（蔺单路柱是指路柱上的跖点不*量）.

第二修分掾作系统（76分）一、筒答霆（共4个小d.年小■5分,共20分）.商述！》作系统中进程的构成,它与程序的区别？.死政发生的四个必要条件是什么？.筒述文件在物理介质上的三师存放方式.并分析它。］的优点及缺点..简迷CPU0度中可能出现的护航效应.维合分析H（兴4个小d.共55分）U0分）若干个等符功何娥fit者依次要切向的磴道为20.M.«.4.80.12.76.但设每移动一个磁道需要3修秒时间,移动曾当前位于41号磁道.请按下列算法分别写出坊向序列，并计算为完成上述各次访问总共花将的寻道时阍.（城道筑号从I到100）（I）先来先事务算法；（2）■蚯寻道时间优先算法.（3）扫描算法（当前磁头移动的方向为依遨通用）（15分）一个耳序具育460个字节,它的内存访问序列如卜,101110417073309185245246434458364（1）若页面大小为100字节.请给出正■的页号访问序列.（2）若物理内存A有200字方的有效空间.果用FIR）页面置换算法•谛计克软页次IL并输出计JI过程.（3）若物理内存M有200字节的有效空间.果用LRU宽面置换算法.谛计算软页次数，并给出计算过程.3.（15分）考虑系统中一tfl进程，它们的CPV执行时间（CPU-burstti»e*位：5»«s>和优先级(Priority)®F：ProcessBurstTiaPriorityPl83P211P323P424PS52假定。时刻进程按Pl.P2.P3.P4.P5的次序到达：（!）分别击出进程采用FCTS.SJF（最短作业时间优先）.等拉占优先舞（小的优先级故衣示具有育的优先版》,和醺（roundrobin.qstg=2«）调度靠法的甘特HL（2）计茸那个进程在（1）中善神调度京法的图相时间.（3）计算每个进程在（1）中善神调度算法的等行时间.（4）比较羯个进程在（D中善种四度11法中的平均周转时间，・聆调度算法最小？答案写在杏通《£答案写在杏通《£上.可在试卷上无依第2页（共3页）4.“5分）卜图是一个从检盘■人到打卬机，出的数据处理at程图,其中便盘*入送界pi通过慑冲区bun（大小为・）把•入数据传送给计算进程.计算进程间把处理结果通过馒冲buf2（大小为n）传送给打印进程P3.若touf2已装满数据.则计算进程丢弃新生成的数需.bufl和buf2为险界侪源，试耳山■盘输入进程.计算进程及打印进程间的同步咽崎入速程—bufl-计算进程-buf2-打印迸理谷案写在答府抵匕弓在武卷上无效加3页（共3页）浙江工商大学2013年硕I:研究生入学考试试卷 （A）卷考试科th845计翼机基础综合 总分：150分 考试时间：3小时数据结构（共60分）（12分）已知一个：叉树的中序遍历结果是12543,后序遍历结果是12345.请画出这课：叉树.（12分）从结节点1开始，用Prim峰法时出下图的最小生成树的过程.（12分）已知•个电报包含的字符为"a".一"，"c","d"和它们出现的频率次数分别为｛25.9,12.8.11）.请给出字符的Huffman编码.（12分）已知一个整数序列12017221260321615）,清幽出快速排序的过程和最后的结果.（12分）请构造函数inifulKblrcc*bt）,判断颗：叉树是否为满：叉树.是返回I,否返回0・二、计算机组成（共45分）I.（9分）画出卿型的冯•诺依登计算机硬件系统组成框图,并简述各功能部件的作用.（9分）某机器字长为16位.请写出下列各种情况下它能衣示的『进制数的能用（采用1位符号位）：（1）无符号整数：（2）用补码表示的定点整数：（3）用5位阶码（含I位阶符八11位尾码（含1位数符）表示的规格化浮点数.（9分）己知Cache存取周期为30ns.主存存取冏期为120ns,执行某段程序共访问Cache5000次，访问主存200次.求：（I）Cache命中率：（2）平均内存访问时间.（9分）举例说明中断处理流程.（9分）某机舞中采用RAM芯片8KX8银成16KX8的RAM区域,起始地址为8000H.假设RAM芯片有CS和WE信号控制端,CPU的地址总线为AA”数据总找D.D.控制fj号为RW.MREQ.（I）请设计地址译码方案：（2）廊出RAM和CPU连接图.三'操作系统（共45分）（8分）描述进程的三个法本状态以及它们之间转换的典型傲因,（9分）在单道程序环境下若仃四道作业，具进入系统及所需的执行时间如下表所示：表1四道作业的进入和执行时间答案丐在答题纸上.”在试卷上无效第答案丐在答题纸上.”在试卷上无效第1页（共2页）作业进入时间（小时）执行时间（小时）18228.50.53分别按先进先出以法、短作业优先算法、响应比高存优先的调度算法调度,则其平均周转时间分别为多少（上述二种办法均为II抢占方式）？（10分）有一个阅览室,读者进入时必须先在一张登记表上进行修记,该表为内£一座位列一表目,包括座号和姓名，读齐离开时要撤消登记自息：阅览室共有100个座位.节阅览室满员后,读者不得进入,只能在室外等待.试用P,V操作写出上述问题的同步算法.（动作部分可用文字描述）假定某时刻用户贞衣中（9分）某虚拟存七器的用户编程空间共32个页面,每页IKB,主存为16KB.已调入在存的页面的页号和物理块号（页架号）对照衣为：假定某时刻用户贞衣中同：（同：（1）虚拟存IT器的功能是怎么实用用?虚页号物理页号051102137（2）逻辑地址0A5c（H）、1A5C（H）对应的物理地址分别为多少？（如果主存中找不到,即为更失效）（9分）假定系统中有五个进程（P0.Pl.P2.P3,P4）和三种类型的资源（A.B.C.D；.按银行家算法中.若出现卜述的资源分配情况（在T0时刻的资源分配情况如卜图所示）；最大需求己分配尚需求剩余进程ABCDABCDABCDABCDP0001400320012Ih21P1275010001750P236101013542356P?098403320652图T0时刻的资源分配图问：⑴TO时刻系统安全吗？（2）如果此时进程P2提出请求Requcsl（I.2,2.2）后，系统能否招资源分配给它？答案写住答题纸匕写在试卷上无效第2页（共2页）3.江苏科技大学计算机摄础综合历年考研真题2014年江苏科技大学2014年江苏科技大学845计算机基告考研真题江苏科技大学2014年硕士研究生入学考试初试试题弋MS科H名4： 计算机U峰合 4分：»注意：3认4他・冬・级上的连叁事事;6所方吝霰必用写桃旦眄上.・械*＞草稿*.**«：③*■通4银发僭军鼻锻一起，入“堂，文W;④本科R考试为(1)IUK姑构(2)计H叙■姐*原*,(1)数据结构试题一、选择题(每小HI2分,共15小E,小计30分).・序存储，■构中敷据无H之何的爱辄大瓜是由( )出示的.A.纹件纳构 B.UH性体构 C.3W0.ffilt.卜面《 )不是才格所必飨R善的行性.A.TT分性 B.畸定性C.高效性 D.ajfjft.若找性表J»*用般今舱在就一个元1｛之后播入十元型"射除■n一个元素.购果用( )〃41方法・》营时间.A.*HA B.带星指针的*幅坏fit表C.Ml坏刈随& D.电头蛇r竹的小循环做表4.4nrrn个精点仃序me*中始人一个新站点力使之仍然疔序的打闿赞杂度修().A.0(1)B.O(ii) C.娱)D.O(nlo«,i()TOC\o"1-5"\h\z0梅S和队钝Q的初始状态为主.元Itrhe2.e3.f*e5.eti依次通过枝S.耀个元素必加先入校痔出帙，Hi惶后同送入队列Q.打6个元,出队列的・序星”2.Z.e3.c6.eS.el.凰&S的\片至少应逢金( ).A.6 B.4 C.3 D.2 .6.小大81配的KMPW法中士巾翱足式的，jfHk什分例为i|Wj.。打福利的冬同?拘不相WM.( ).4.iPKjwab.仅jpiaic. d.；不问那.j不网霸.( )不俄幅为特媒融环.A.挹状短阵 B上或产三角亚陶 C.财炼曲阵D.0以建限. 个同修为k的蠲一X科乂"n个储点.K中有z个时干站.点.内。( ).A-n=k4«uB.2nak-n.C.n«3k-|D.n*2m-lM［页共6jfiTOC\o"1-5"\h\z.由.5.7分别什为叫结点权值为透哈人什科,黯权路冷K度为（ ）.A.58 B.68 C.48 D.74.GM个1»1通无向阳,共杳18条地.刹津出至少仃（ >个烦*.A.1 B.5 G6 D.8.&010000个元素.衲SI用餐快速反挑通山前10个鼻N的.果用（ >力法Ulf.1快速推序 B.城得序C.啊橙场扑抻序D.门片H序.已知8个码值为：42.26.18.37.64.78.58.44.36.技制依次扫播插入一收从空开妁的一叉痔序一的方法健。二叉，♦序树，在找值为5«的结点所需比依次的为（ ）.A.2 B.3 C4 D.S11采用分块内推时.t；纹性收中共有225个元素.科找每个兀事的依率相同.代&采用娱序在找来确定站力.所a的续时.年块应分别含（ ）个纳点最值.A.12 B.10 C.15 D.25.在一个7册的B样上.除根外的鼻个曾外结点所含的f归数最少为（ ）.M3 B.3 C.4 0.5.适合！茁于比较大H码的动金什提方法是（ ）.A.履印0故 B.改则在找C.*引，序齐找 D.折t声找二、填空题（每小•2分,共12小■.小计24分）.故榭的《本小位是.在数盘结构中遍*竹为个数据十位进打处瑁.,■萍我的第一个元素的存健地却此50.抵个元H的检度为5个十的.则就20个元素的〃储地卅4 .3段的・人操ft特性总际龙先出UFO.从列的疑人报件特性是..维敏组A中打的卜林从5到8.的的卜&从4妁15,技行优先存储.m个兀家占5个存储单元•N5][4]的〃储地址是500・则元宗A网（口1的存储地址抡.. 脖。蛛的煌11次.其13株竹体现在..某叉树的先序0历序列让ABDECFG.中序•历序列是DBEAFGC.则4无序■历序例始*个具有。个顶点e条做的有向图的拓扑冲网的W法.凡时间包杂度为.8号将大蹲亨犷例：15.19.73.61.82.24.47.窿成小楸地.只需m73、 交换..快速抖序在n个收必丫现为时,W法效率反而降为O（n2）..对8个码值所构魂的一叉排序椅,为找一个码值的平均比较次数为.11给定一个键值序列：25.43,62.31.48.56,枭用散列函数川k）=kmod7,则元素48的同义词是.12.在一株5阶B件中.除根结点和外结点外，句个结点的子树数目最多为.三、计算题（共12分）（6分）给定权值集IL4.7.10,6,8）.试分别以它们每一个作为叶结在的权值构造相应的哈大曼树.力il京式带权路程K度.（6分）已知一批关健字为：26.36,41.38.44.15.68.12.6.51.25,22.要求装境囚子为0.8.选用除由余法IMKeyMKcy、p作散列函数，p=13,用线性探作法婚决冲突.构造闭侬舛衰.并计算存找成功卜的干均住找长度.四、算法设计题（总计9分）.（4分）设有一个整数颂序丧.反计算法将其调帙为前部为令数.，后睇为偶数，11时间复杂改为0（n）,空间复杂度为0（1）..（5分）嫔丐算法.求给定关憎码在一义挣序树中所在的£效.(2)计算机组成原理试题一、单项选择JS小端i分,共10分).卜列数中餐小的数是( ).A.(100101)>B.(50).C.(100010)«D.(625)».( ，泉示法主要用丁我示存点数中的册码.A.原码 B.料码C.反码 D.蜂码1在机得效( )中,写的表示形式地唯一的.A.季码 B.热码C.移码11反码.冯•4依曼机1作方式的*本特点C).A.%指令薄♦数据渣 B.按地址访问井看序执行指令C.应槿！ttr D.存贮器按内齐选产地计.在定点一或制运为器中.城法地U股也过( )来实现.A.厥码玷尊的一遗制城法81 B.於码匕K的一道制减法器C.原网运算的卜堪加那法赛 0.计码达11的：遗制加法器.寄存器方按4址方式中.推件敢住( ).A.需存81Bt存餐无C.堆栈 D.科'序计数需7,微积序控制5中.机器指令，WU&令的关系是( ).a.n条机器指令由条做指令未执行一段机器指令皿成的理序可由一条6指今执上一条。指令由若干条机1S指。物成D.句一条机器题令由段用他指令0成的6程疗求执行.在♦绥中斯系统中.CPU一口旧咫中*.则立即大闭( )林A.以防4次中断股务站取的同级的R他中斯源产生另一次中断堪打1扰.丸中货允胃&中断请求 C.中曲屏4r I).中断保护UitWtflTK32O.其存储界俄为1MB.心楂T字蛔卅.它的WE范因丛( ).配4MR 区2MB C2)1 D.IM.EPR（N是指（ ）.A,注弓存储器&只it有储4 C,闪速存他舞D.紫外光擦除可*界只“〃储我二.填空题（年小』2分,共10分）.在计W机传统术论中,将和合在一起称为CPU.前将CPU灯仓在一起陈为主机..形成指令他卅的方式.喙为方式.盯喷序3址和♦址两a.使用 来跟蹲..RISC指令系统的量入特点是，.冏定.的类少..假品总线中传送的信息神类不同.计尊机系统总货可分为三纲.分别为总线、.总线和总线.s在一个CPU周期中. 次健定义并执行多个并行梅仙盘命令的Hk疥令叫.4个CPU周期中,栗用操作码方式.次只能控制信息从某个源解料到霞个日林IK竹拉”过料的微指一叫•后者实现条机淳指令的依用序■比侑看归耳的e程序.三、综合题（共55分）（7分）已知x3OlOOl.0.1100采用双符号律求[*♦/・=?.ixy}・=?.并指出让便结果是否泡出.（10分）没有浮点效X-2X0.0110011.y-2'x（-O.”10010）.附码用4位移码衰示.屋敷《北符号传）用8位补码费小.求flXy]„.R未门接用补叫完成屋数修法ifill.匕算的枭尾数仍保留867（含符号位）,并用尾依之后的4位值处理有入摊件.（10分）IIOlWy=-O.1011.用比收法讣码f>金法<H'l&xrth公式.）求x•尸？4.110分）St机赛的指令格式如卜图所示，0PXD15 109 87 0阳中X为4U-特征僮，H.X=0B4,不费址1X=1时,阴受时寄存JSXiig行变址：X=2时.阳曼0市存舞X,«Hj关址tX=3时.相对寻址.设（PC）M234H.（X,）MJO37H.（W-I122H.谊■定卜州指令的白效地址（均用十六进般入示.H表示卜六遏制）.(D4420H (2)2244H ⑶1322H (4)352IK⑸6723H(10分)累计IT机系统的内存由cache构成,cuehe的存取冏财为45m.上。的4取周期为200n,.已如在段给定的时何内.CPI共访日内44500次.耳中M0次优问士存.M>cache的命中率是多少？E坊网内存的平均时画是多少n»?Cwhe•土存事统的效率是衣少7(8分)阴RXX8位的RAM芯片iill«一个32KX8位的WiB.RAM芯片有四个输入・h、衣彳效时.馍片透中.当府/m=1时.执行准揖件：当R/mmO时,执行与舞行.C求赤山此春UtM蛆成结构图(包括。E的连接).江苏科技大学2013年硕士研究生入学考试初试试题（A卷）H日代竭； 845“同名低： 计算如♦-J鼻合（B&二） 晨价.ISO»注意《认真回读*星城上的逵童事项：②所需各索必短耳电迥上,¥和半试盘或生草修弧士政；Q本认釐圾境随¥4统一**人迷・11中文・；④本科耳才达为可选二，才叟从如t”b（221V-（，）卅日中速#26flAMWg. HU._（1）计算机组成原理试题一、单项选择题'脩小■1分.共10分）I.洛•诺依生机I件方式的M本朽点足（ ）.*.多指令流单数抠潦 B.懂地加访问力■序执行指令C雄栈柒4 D.右七方核内力总界域用2.4机器般（ ）中.专的&示杉式是唯的.”码 B.林码G幡码D,反码.在宅点一送制也的器中.M法玷M般通过（ ）条实一.A.原蚂运H的—遇耕减法IS B.朴码运的的_进制破法器C.用码也W的I班曲加法X I）.孙码造M的一进制加法2XTOC\o"1-5"\h\z.其计算机字及32位,其"储齐0为4MB.号按丫字竭址.它的♦址范国坦（ ）.-1MB B.泗 C.2H D.!MEPROM是指（ ）.A.潘干存储黔B.只读〃依58 C.闪速〃昧器D.萦外光捧除用炮程只读行口器1/ZU2SWCW之间:DMcache的臼的是（ ）.A.皖决CH和主存之间的速仪匹配M国B.犷人士存贮I#容量C.犷人E中的刖芍存U的数HD.既犷人上存r•舞容量,乂扩大CH中通用而存M的数W.指令的寻址方式右眼序和跳跳向科方长.采用跳跃寻址方式,可以实现（ ）.A堆极寻址 B程序的条件转修C.程序的无条件转移 D.程序的条件转移或无条件M移由fCPU内部的掾作速度较快.向CPU坊向一次主存所注的时间较长*因此机舞周.期通常用（ ）宋规定.A./件中读JR一个指令？的U知时间 B主行中读取个散燃字的修长时间C主件中写入一个数小字的平均时间 0主存中取个效蛔字的平均时间.系绩总线中地址线的功能足（ ）.A选择主存单元地址 B.填择遥行信息传输的粒冬C.选持外存地址 0指定主件和I/O设善接口电路的地址.在舱级中断累惊中，CPU口用应中断,画上抑大角< ）标上,以防本次中断明芬精火前同1»的JC他中新潭产生另一次中断进M干扰.A.中新允许U.中断请求 C.中断解触 D.中卧保护二.填空题,每小婚2分,共10分）.移科&示法_L瞿用「我示 敢的阶网E,以便］•比收两个 的人小M. 惬件..存储册的技术指标。.....在一个CPU网期中.一次能定义并执行多个井仃株什诜命令的指指令叫 -右tCRU它用爆竹码方A，一次月偏拄酬信息从某个海都修刎某个口心酸。热h1"的微指令叫.后方实现一条机器所令的布用字曼比福褥偏弓的BHY序 ..RlSClfi。系维的・人特色.冏定.牌矣少..在罐布缜拄制器中,杷投做探代右情为产什力门冏定时序拉M伍q的建银电跳.liHSW电路站热曲知构成的H杂帜比网络.为执行不同的指令时.通过&活一摹列坡此微不相同的火未一对指令的婚tth三、综合黑（共58分）.（10分）*“博机杀父的内存储网由cache⑷t〃幢质.owhe的。地瑜删为451H.tU的存取周期为200m.已却在一段铮定的时间内，CR共防何内。450）次.X中340次访向上存.Micache的命中率虺多少7 .CH：坊向内存的平均时间站多少n$?C3）Cache-主存系&的效率蚪多少？ 、.（10分）已他「S.|闻他广0.1011.用比我法扑码傅乘法，的800th公式.）^»•>?18分）用8KX8俏的RAM芯片评J&>32KXH位的。“篇.RAM芯片《网个・入”:》序“欢时.该片迭中."月，'m=1财.执，ii*柒件।当什/诉±0时.执行”热仲.要求谖出此存MUS饵成标构用（色拈。CHttiilt）.•出切步g山&喝k•明崎坳*anvwmwu国蚓图w*皿4嫡w婢用'i%同/国土身*明”呢。【叫|13靖阴女与««>«<!<2•1#"**□’3-8-VSi^hlVtPBUWW*WJI山〈的。rW”93(«£)9HEKZ4KS)HIZS£(t->HSZEl(E) HV»-2Z(Z)KO^KD—'/4冬等H•坐*腌下*IIM峪)西琳裆空处专身网43”生WII«(T0也£00=(K)'UKol=CM)枳•—旧册•/£=X茶US?*整方朱祖基出•收Z-X”"为9第3痛以副/苓出*收CX।神芟+'WO=XK.川利，，稗3MX6国0 28 601 S1aXdo‘生妁SH叫第做心果端SRWK（好01）巧•M&Y串苗隔切々，柒UN碍由卅M"（06取号）NB裾由出修物SfWli硒•总邱十步通声M¥G，#仲岩。/诿,*[*x«J*的#图8M（可白狼tWM^rWlOOIHO）x,Z^ttOOIIOOx,^J«lBVi（tt®<^«）»(2)数据结构试题一、填空题(每题i分,共10分).你法nrr五个符性.分域是仃零个或玄上♦入，n个或u外输出.有列件,偷止性和()..俄有一个I。阶的对秣W阵A采用X，解〃储.A[0][0]为筠一个兀茶.其白楠康卅为d.何个元KAI个存球中山.则兀KAl6H7的存卜为().XdfoJ义加1f"n.(h.tc.di),e),用llead和TM1咕数取出15中原子d的的管«()..图的♦山优先西历所用刻的我也结构足<>>.MT .L25,22.10.29,.13.11).一定怅有了点的二投镇琳利同，？；按二叉撑序网的锹读数列.M1件找个数的平均比校次数为<1..K取为25的有字表未用折子15拉,共为()个；iik的齐推长度XH..IS定常,死⑵M5.剑.果阳的改列的故为H(k)d・odII.剧元「61的同义词见<)..对刊记录<H.IR.16.IX15.22.17,团63)理行八接垢入样序,与把工7个记录17必入依仃序々时,为寻找插人竹置W比校:)次..在7阶B樽中网站点所值M的犬德玛个数从匕林的少分别为(.>..即树的所有叫纳点移该<)在一个能中.二、选择题(每181分,就20分)I.假收行如卜遗尸缗女爱刷：士人和去「可以村”群长遗产；子女可以施承父家或母♦的笳产if女间小酷《111维次.树&r读遍/事承大系的母介活的数据情构曲渣林( ).A.H B.图 C.相性化 D. 4畲2•卜而( )不是算泣所必须I]瞽的折性.A.仃列性 B.虢切性 C.。救性 D. 41jtl3.若情表中的常用的预作是4与后个结点之冗拙人个站点和划欧个站点.Wl«UI( )存碱〃法第节看泡》时间.A.甲附表H.循环“触表C.单附环镇&D.书屋街「的中改.对丁n个元泰就成的或性表,建立个行力中型表的时间U架屋足( ).A.0(1)B.0(n)C.Otn1) 0.OlnloHrfil5.A殆耳久健求的p即指玷/与始人s所指川口的嫩竹姑( ).4p--*neMi^s.4-"zim-p.r>->neil->prior»fi；5-.ncMi^p，nc*t;

p-/ncxl3s:'ncxL/pricf;s->|inor-n.s-next-p-ncit,s->prior^p.xnex«-p'next;pnext-8;pnextpriorFs*prior®p,sncit^p-zncut;p-iM-xt->prhn-s:p-Xwxtr.设US加队列Q的切她状6为中,JcKrl.c2.e：».Mel桢依次通戌栈$.一个儿表山枝后即进入队列Q./6个几薇山队的哦用比*J.M.e5、el.rt.el.则枝卜的力讨至少就读是( ).. 决计算机L机,“I印机之沏速应不M；配问题时逋常小—个"印馈冲。藻嫂冲|«川谓是个( )雄札A,故 B,队列C.M.梅鼓物称为附机存取地检是内力( >.A.数粗儿靠型烟机的 K对数州仟兀*的存取时间是相等的G劭时可以对敏利进打访向 D.毂用的存体结构足不定.卜面( )不思丁为憬址M.A.妙韵规辑B.三角如阳 C.林遮规30.对称地阵.若「义衣A调足llo«d<A)=Trtll(AJ.)MAA( >.A.()B.(())C.(().())y.((),<).())ILiQ义利白二个彷力.的K汉仅为( )C.[log3nj+lD.不附恻定个局也为h的漏又网共行“个品点.K中百i«个叫广姑巾,则"( >成立.A.n-h*«H.h*«-2nC.»=hI I)."2«-|IXUh*林中右4爆树,将中格力的个数依次为n】.“2.g.rtl.M把A林找整版XAH.H根结.&.的。子树L。( )个百点.A.iil-1B.nlC.nl，n21n3 l>.n2，n：“n1M.GM 通无向图.具仃布条妆.则谈图十少。< )个偷点.A.8 氏9 C.10 0.H.堆的筋状是W(A.二叉井序树B.i聋一义帜C.充上二义树D.刑定树.QOlCtOfK)个兀本,礼室用AJ快的速值搞选出优1期)个助人的.XMJ< )方法蝌”A.快速推序B.堆井序C.楮尔带序 D.m井扑序.( )方法从从k椁序昨列中挑选兀卡.丹利此放入仁州庄序列的一端.A.IH井柞序B.插入椁件 C.快避排步 P.以界拉中.卜例序列中.( )足拘仃笫一售快速扑用的钻农. 、A.[dn«aiteh.de.bb]ff[hn>gcIA.[dn«aiteh.de.bb]ff[hn>gcIC(«t-n«.rb.«'(l,hh1ft\!n.ha19.( )作中4泣出小班定的.A.fttflM H.“按插入20.( )可能是甲劭X«,.-A.完全一叉树 B.满XMB.cd.cb,hx.du]ff(hn>gc<hb]D.»*<.hb.<<1,rt/i]nvh.«c.h"|C.”整透杆D.起泡三、判断题(正■的打精课的打“XL毋BH分.共10分)TOC\o"1-5"\h\z所调敷网的邃料站构指的是数榭之时的也软欠嘉- I >0(nlogn)<C(n). ( )iQp(q'指thiSrpy.厕*严*<j. ( >t有n个元素依次进枝.划出梗序列在OrD2机.< >.在福环队列中,from。,向队头兀*的前个位雷.re“r指向队昆兀氏的伸司•则队血的条II%fronsreftr. C ).使用一兀川&行此称蹙城阵的元本.有时并不慌存禽史陶< >.二文材足值为21n村. < )&时任一酒叉啊.其分低敷R=2(nOI).式中.nO为蜂悯州点数•( )9时任宽个旭，从某净点小发!£，；次深度优尢或！比优比遍历，可廿同图的所。限点•( )10.&个仃向阍的拓扑序列，”."艮加日在顶点b之四.■图中心力条从「巾点”到M点h的克. ( > •四、计算题(共19分).(8分)已知上18码序列为(.Inn,leb.Mar,Apr.May.Jun.Jul.Aug.Sep.Oct,Sov,Dec).敢轲殳的地出土间为016.设收剂示数为H(x”[//2j.IC中，为大H码中，个享用他字母表中的序。.采府线性报界1法》铤堆址法处理冲突.试分别构造敢例&,并求等播率情况卜育找成功的1F均为找K4..(4分)及有纲结点.4权值*J{1.1,5.16.25.1.10J.1S出由这些”点后构或的哈大世旭,力计算忖的带权踣径K/S..(4分)对数«C：I.5.3.6.8.11.J0,技此进入的次序.U"慢平伫_.义利,.13分)计舞卜列枚式小的AJ丁字符地火牧由败值(最小值为。).BAhcaabcaaab五、算法编写想(共16分) '(9分)设A*IB分别为两个偃力.H均由箭表触F”&示(冷乂中无未仅为静数.掩值从小到