合肥工业大学-850-2017-真题.pdf
合肥工业大学合肥工业大学2017年硕士研究生初试专业课笔试试题年硕士研究生初试专业课笔试试题考试科目名称：计算机科学与技术学科专业基础综合（考试科目名称：计算机科学与技术学科专业基础综合（850）【数据结构】一选择题：（每小题）【数据结构】一选择题：（每小题2分，共分，共10分）在下列备选答案中选出一个正确的，将其号码填在“分）在下列备选答案中选出一个正确的，将其号码填在“”上。”上。1.在分别以下列序列构造平衡二叉树的过程中，用到四种类型的调整操作。A.2,4,3,8,9,5,1B.1,5,2,9,8,4,3C.2,8,9,4,3,5,1D.1,3,5,9,8,2,42.下列排序算法中，能保证在每趟排序中将第一个元素放到其最终的位置上。A.希尔排序B.快速排序C.归并排序D.直接插入排序3.在图采用邻接表存储时，深度遍历算法的时间复杂度为。A.O(n)B.O(n+e)C.O(n2)D.O(n3)4.已知一棵完全二叉树的第七层有8个叶子结点，则二叉树中的叶子结点数是。A.37B.117C.118D.不确定5.一棵左右子树均不为空的二叉树在后序线索化后，其中空的右链域的个数是。A.0B.1C.2D.不确定二填空（每空二填空（每空3分，共分，共15分）分）1.判断单链表中由指针仅P所指结点为尾结点的条件是。2.删除双循环链表中的由指针P所指示的结点的操作序列是。3.在数组元素A0为最大元素时，冒泡排序算法所需要的比较元素的次数是。4.对有序表A22按二分查找方法查找A9时，依次比较的元素下标是。5.以数据集3,6,8,9,10,12作为叶子结点权值构造的哈夫曼树的带权路径长度是。三解答下列各题（每小题三解答下列各题（每小题5分，共分，共20分）分）1.已知一棵二叉树的先序、中序如下，请构造出该二叉树。先序：ABCDEFGHIJ中序：BDCEAGIJHF各个学校计算机/软件专业考研真题 免费分享 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获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研2.算法阅读：算法Print及所引用的数组T的值如右所示，写出调用Print(1)的运行结果。Void Print(int i);If(i!=0)CoutTi.data;/输出Print(Ti.S);Print(Ti.B);3.设散列表长度为11，散列函数H(K)=K%11，采用线性探查法处理冲突，若输入序列为(10,80,12,60,78,35,42,31,15)，要求构造出散列表，并求出在等概率情况下查找成功的平均查找长度。0123456789104.对下面数据表执行快速排序，写出每一趟的结果，并标出第一趟排序过程中的元素移动情况。（75，20，50，30，18，35，70，150，60，80，12，23，65，45）序号dataSB1A272B353C044D005E606F007G808H099I10010J00各个学校计算机/软件专业考研真题 免费分享 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倒置（也就是将每个结点的后继指针改为指向前驱，并让头指针改为指向原来的尾结点）。2.设计算法以递增有序数组intA中元素为输入数据，构造一颗平衡的二叉排序树。3.设计算法以判断有向图G中是否存在一条从顶点v0到vi路径，若存在，返回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 a n获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研【计算机组成原理】一单项选择题（每小题【计算机组成原理】一单项选择题（每小题2分，共分，共20分）在每个小题的四个备选答案中选择一个正确的答案。分）在每个小题的四个备选答案中选择一个正确的答案。1.以下关于“神威太湖之光”超级计算机的描述中，错误的是。A.它在2016年6月TOP500超级计算机系统排名中位于榜首B.是世界上首台运算速度超过十亿次的超级计算机C.它全部采用国产处理器构建D.其峰值性能位于世界第一，性能功耗比位于世界第二2.如果某个基准测试程序在计算机A上运行需要9s，而在计算机B上运行需要6s，那么下列结论中正确的是。A.计算机B的时钟频率是计算机A的2倍B.计算机B的时钟频率是计算机A的1.5倍C.该程序在计算机B上的执行速度是计算机A的1.5倍D.在计算机A中执行一条指令所需的时钟周期数是计算机B的1.5倍3.以下有关计算机性能指标MIPS的描述中，错误的是。A.MIPS是指平均每秒执行的百万条指令数B.MIPS越大说明机器性能一定越好C.用MIPS对不同机器进行性能比较不太客观D.MIPS反映的是机器执行定点指令的速度4.采用计数器定时查询的总线判优方式，如果每次计数器都从“0”开始计数，那么。A.设备号小的设备优先级高B.设备号小的设备优先级低C.每个设备的优先级轮流最高D.每个设备的优先级相等5.以下对于存储器刷新操作的描述中，正确的是。A.动态和静态RAM都需要刷新B.刷新是按行进行的C.刷新是按一个芯片接着一个芯片的顺序进行的D.所有的刷新方式都存在“死区”6.以下由磁性材料构成的存储器中，不属于辅助存储器。A.磁盘B.磁带C.磁芯D.磁光盘7.如果cache与竹村之间采用的是组相联映射方式，那么以下说法正确的是。A.如果替换策略采用LRU算法，那么cache组内的行数越多则命中率越高B.如果替换策略采用FIFO算法，那么cache组内的行数越多则命中率越高C.cache组的大小与命中率没有关系D.无论采用哪种算法，cache的组越大则命中率越高8.中断向量给出的是。A.程序断点B.中断码C.中断屏蔽码D.中断服务程序的入口地址9.不符合RISC的主要特征的有。A.CPU中配置了大量通用寄存器C.控制器采用微程序设计D.采用流水线方式执行指令E.指令长度一致各个学校计算机/软件专业考研真题 免费分享 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.假设指令流经某五级流水线的五个功能短的时间一次是80ns，80ns，70ns，90ns和50ns，那么流水线的时钟周期至少是。A.90nsB.80nsC.70nsD.50ns二填空题（每题二填空题（每题2分，共分，共14分）分）1.已知字符“A”的ASCII编码为100 0001，那么在字符“F”的ASCII码最前面添加一位奇校检位后的8位编码为。2.采用循环冗余校检码（CRC）进行译码和纠错的依据是。3.常用的两种指令寻址方式是。4.如果把数值-128以移码形式存放在某个8位寄存器中，那么该寄存器中实际存放的内容是。5.常见的两种微指令格式是。6.假设某计算机的主存容量为64KB。按照字节编址，并且0000H7FFFH为系统程序区，剩余地址空间为用户程序区，那么如果采用4KX8位的RAM芯片来构建用户程序区，那么需要片这样的RAM芯片。7.请写出取址周期的全部微操作：。三判断题（每题三判断题（每题1分，共分，共10分）判断下列每个叙述是否正确。如果正确，用“”表示，否则用“”表示。分）判断下列每个叙述是否正确。如果正确，用“”表示，否则用“”表示。1.（）固件是具有软件特点的硬件。2.（）在计算机中，数值数据只能以二进制形式表示，并且只能运行二进制运算，不能以十进制表示数据进行十进制运算。3.（）在异步通信中，由于采用了应答方式，因而允许参与通信的模块速度不一致。4.（）采用Flash进行读和写的速度一样快，与DRAM读写速度接近。5.（）CPU对DMA请求和中断请求的响应时间是不一样的。6.（）通常机器字长越长，数的表示范围越大，精度也越高。7.（）当一个磁道存满后，新的信息会在同一个柱面的下一个盘面存放。8.（）cache与主存采用统一编址，根据地址不同判断访问cache还是主存。9.（）在中断方式下，外设任何时候都可以发出中断请求，而且能得到CPU的立即响应，因此对于硬件故障可以采取强迫中断的方式。10.（）采用流水线方式不能缩短某一条指令的执行时间，只可能会延长。四请简要回答以下问题（四请简要回答以下问题（10分）分）1.单周期处理器的CPI是多少？（2分）2.对于单周期处理器，其时钟周期在设计中如何确定的？（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获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研3.单周期处理器中的部件在一个指令周期内能否被重复使用？请解释原因。（3分）4.多周期CPU的设计思想是什么？（3分）五（五（10分）分）某一个8位的计算机，数据以补码形式表示，并且机器数含1位符号位，现有整数x、y、z，其中x补=36H，y补=54H，z补=D5H，请分别求x-2y的机器数和x/4+2z的机器数，并指明计算结束后溢出标志OF的值。六（六（11分）分）假定在一个程序中定义了变量a和b，其中a是float型变量（用32位的IEEE754单精度浮点数表示），b是16位short型变量（用补码表示）。程序执行的某一时刻，如果a=-19，b=120，并且a和b都被写到了主存中（按字节编址），其地址分别是100和110。请分别画出在大端机器和小端机器上变量a和b在内存中是如何存放的。各个学校计算机/软件专业考研真题 免费分享 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获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 微信公众号 计算机与软件考研
