合肥工业大学-850-2016-真题.pdf

《合肥工业大学-850-2016-真题.pdf》由会员分享，可在线阅读，更多相关《合肥工业大学-850-2016-真题.pdf（6页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、合肥工业大学合肥工业大学2016年硕士研究生初试专业课笔试试题年硕士研究生初试专业课笔试试题考试科目名称：计算机科学与技术学科专业基础综合（考试科目名称：计算机科学与技术学科专业基础综合（850）【数据结构部分】一选择题：（每小题）【数据结构部分】一选择题：（每小题2分，共分，共10分）在下列备选答案中选出一个正确的，将其号码填在“分）在下列备选答案中选出一个正确的，将其号码填在“”上。”上。1.在分别以下列序列构造平衡二叉树的过程中，用到四种类型的调整操作。A.2,4,3,6,7,5,1B.1,5,2,7,6,4,3C.2,6,7,4,3,5,1D.1,3,5,7,6,2,42.下列排序算法

2、中，能保证在每趟排序中将最大（小）元素放到其最终的位置上。A.冒泡排序B.快速排序C.归并排序D.直接插入排序3.在图采用邻接矩阵存储时，广度遍历算法的时间复杂度为。A.O(n)B.O(n+e)C.O(n2)D.O(n3)4.已知一棵有100个结点的完全二叉树中，其叶子结点数是。A.37B.63C.49D.505.一棵非空的二叉树在先序线索化后，其中空的右链域的个数是。A.0B.1C.2D.不确定二填空（每空二填空（每空3分，共分，共15分）分）1.判断带头结点的单循环链表L中仅有一个元素结点的条件是。2.在双循环链表中由指针P所指示的结点前插入由S所指结点的操作序列是。3.在初始数据表倒序时

3、，冒泡排序算法所需要的交换元素的次数是。4.对有序表A20按二分查找方法查找A8时，依次比较的元素下标是。5.以数据集3,4,5,6,7,8作为叶子结点权值构造的哈夫曼树的带权路径长度是。三解答下列各题（每小题三解答下列各题（每小题5分，共分，共20分）分）1.已知一棵二叉树的先序、中序如下，请构造出该二叉树。先序：ABCDEFGHIJKL中序：CBEFGDAIKJLH各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众

4、号 计算机与软件考研2.算法阅读：对下面算法P和数组A 以及n=13，写出调用P(1)的输出结果。（没有值的数组元素的值记为NULL）012345678910111213AABHCEIDFGJVoid P(int i);If(i=n)P(2*i);If(Ai!=NULL)cout Ai;P(2*i+1);3.以下列数据序列构造二叉排序树，并计算出在等概率情况下的平均查找长度。100，28，9，140，65，80，38，150，110，120，130，76，90，15，2004.对下面数据表执行快速排序，写出每一趟的结果，并标出第一趟排序过程中的元素移动情况。（80，20，40，30，18，35

5、，70，150，60，75，12，23，65，50）各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研四四.算法设计：分别写出求解下列问题的算法。（每小题算法设计：分别写出求解下列问题的算法。（每小题10分，共分，共30分）分）1.假设递增有序的链表L表示一个集合，试设计算法在表中插入一个值为x的元素结点，使其仍保持递增有序。2.设计算法将以二叉链表T存储的二叉树转换为对应的顺序存储结构Amax中。

6、要求：空的元素用NULL表示，并返回所存储的最大的元素下标。3.设计算法以判断无向图G中是否是一棵树，若是，返回true，否则，返回false。（注：本算法中可以调用以下几个函数：firstadj(G,V)返回图G中定点V的第一个邻接点的号码，若不存在，则返回0；nextadj(G,V,W)返回图G中顶点V的邻接点中处于W之后的邻接点的号码，若不存在，则返回0；另外，若用到栈或队列之类的结构，可直接调用有关函数实现运算，不必考虑底层结构和运算的实现。）各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y

7、a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研【计算机组成原理】一选择题（每小题【计算机组成原理】一选择题（每小题2分，共分，共20分）分）1.在冯诺依曼计算机中，CPU区分从存储器中取出的是指令还是数据的方法是的是。A.指令和数据所在的存储单元地址不同B.访问指令和访问数据所处的指令执行阶段不同C.访问指令和访问数据的寻址方式不同D.指令和数据表示方式不同2.假设某个数在计算机内部表示为00110010，则。A.这个数是32B.这个数是正数C.这个数是负数D.以上都不对3.IEEE754标准表示的是一个单精度浮点数编码为C14C000

8、0H，其十进制表示的真值是。A.-0.75B.-5C.-1.275x101D.1.754.假设某计算机按字节编址，采用大端方式，有一个float型的变量i的地址为FFFF0C05H，i的机器数为03150617H，则FFFF 0C06H中存放的内容是。A.15HB.19HC.0619HD.06H5.ALU属于。A.存储器的一种B.组合逻辑电路C.寄存器D.时序逻辑电路6.在循环冗余校验中，生成多项式G（x）应满足的条件不包括。A.用G（x）对余数作模2除，应该能使余数循环B.校验码中任何一位发生错误，在与G（x）作模2除时，都应使余数不为0C.校验码中不同位发生错误时，在与G（x）作模2除时，

9、都应使余数不同D.同一个数据虽然选择了不同的G（x），但是所得到的CRC码的码距应当是相同的7.从总体上看，微程序控制器的速度相比组合逻辑电路要慢，主要原因在于。A.增加了从指令寄存器读取微指令的时间B.增加了从控制存储器读取微指令的时间C.增加了从磁盘储器读取微指令的时间D.增加了从主存储器读取微指令的时间8.采用“周期挪用”方式进行DMA传送时，每传送一个数据需要挪用一个。A.存储周期B.机器周期C.时钟周期D.指令周期9.以下两组指令分别存在、类型的数据相关。（1）I1:STAM(x),R1;(R1)M(x)I2:ADDR1,R2,R3;(R2)+R(3)R1（2）I1:MULR3,R1

10、,R2;(R1)X(R2)R3I2:ADDR3,R4,R5;(R4)+R(5)R3A.RAWWARB.WARRAWC.RAWWAWD.WARWAW10.以下对半导体存储器的叙述正确的是。A.Flash存储器功耗低，集成度高，读写速度一样快，目前得到了广泛使用B.SRAM是易失性半导体存储器，需要刷新，用作cacheC.DRAM集成度高、功耗低、用作主存D.E2PROM是一种需要通过紫外线擦除的存储器各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众

11、号 计算机与软件考研 微信公众号 计算机与软件考研二填空题（每题二填空题（每题2分，共分，共14分）分）1.设机器字长为16位，表示浮点数时，阶符一位，阶码数值部分为5位，数符1位，如果浮点数用补码表示，而且尾数为规格化数，则最大正数是，最大负数是。2.假设机器数为n位，-1.0的补码是。3.在两类微指令的格式中，微指令可以同时执行若干个微操作，因此执行速度更快。4.在组相联映像方式中，如果将Cache字块分为8组，每组包含2个字块，那么主存字块15可以映像到Cache的字块中。5.浮点数表示的数值大小取决于位数。6.超标量流水线是指。三判断题（每题一分，共三判断题（每题一分，共10分）判断下

12、列每个叙述是否正确。如果正确，用“”表示，否则用“”表示。分）判断下列每个叙述是否正确。如果正确，用“”表示，否则用“”表示。1.（）存储子长是指CPU一次能够处理的数据的位数。2.（）指令集体系结构位于计算机软件和硬件的交界面上。3.（）将一个程序在一台计算机上编译成两个不同的目标代码，其中。所生成的指令条数少的代码执行时间短。4.（）汉字内码需要两个字节才能表示。5.（）在主存与cache之间传送数据时，主存块越大，命中率越高。6.（）CPU中的寄存器用户都可以访问，通过合理地使用寄存器，可以提高CPU的执行效率。7.（）同一个总线有可能既采用同步方式又采用异步方式通信。8.（）采用流水线

13、方式可以使一条指令执行时间变短。9.（）在程序查询方式下，外设通过I/O接口直接与CPU交换数据。10.（）在寄存器寻址方式中，指定寄存器中存放的操作数地址。四（四（10分）分）集中式总线仲裁方式有哪几种？请画出其中一种方式的逻辑结构图，并说明其工作原理和特点。各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研五五.（10分）分）某磁盘组的性能参数如下：磁盘平均寻道时间为20s，转速为6000r/m

14、in，每道容量为120KB，假设操作系统采用两种方式访问该磁盘组，第一种方式为每次读取6KB，第二种方式是每次读取12KB，操作系统访问磁盘的额外开销为每次1ms。（1）计算该磁盘组的数据传输率和平均等待时间；（2）如果需要读取一个24KB的磁盘文件，按第一种方式和第二种方式工作所需的时间各是多少。五（五（11分）分）指令字长为16位，每个地址码为5位。采用扩展操作码的方式，设计20条二地址指令，100条一地址指令，30条零地址指令。（1）请画出操作码扩展图。（2）计算操作码平均长度。各个学校计算机/软件专业考研真题 免费分享 h t t p s:/g i t h u b.co m/cs s e k y/cs k a o y a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研