2018年考研上海大学计算机专业真题回忆.docx
新祥旭考研辅导咨询VX: 135529157131选择(2*30)1.下列排序算法稳定的是()A冒泡排序,直接插入排序B基数排序,希尔排序C堆排序,选择排序D归并排序,快速排序2.下列不同进制数中真值最大的是()A00111001(2)B45(8)C29(16)D97(10)3.以下说法正确的是()Acache一般采用DRAMBSRAM不需要刷新CSRAM比DRAM集成度高DDRAM是非易失性存储器4.下列操作复杂度为O(1)的是()A在顺序表中插入一个元素B在单链表中访问一个元素C在单链表中插入一个元素D在顺序表中访问一个元素5.数组中有100个递增存储的整数,折半查找时查找一个元素的比较次数不可能超过()A.100 B.25 C.10 D.96.一个完全二叉树共有100个结点,则有共有()个叶子结点A.26 B.33 C.44 D.457.一般家用台式电脑是()A微型机B小型机C中型机D大型机8.微程序存储在()A主存储器B程序计数器C控制存储器D指令寄存器9.一地址指令()A可能有一个操作数,也可能有两个操作数B不可能是数据传送指令C不可能是运算指令D以上都对10.决定程序执行顺序的是()A指令寄存器B数据寄存器C程序计数器D控制存储器11. 在指令格式中,采用扩展操作码设计方案的目的是()A减少指令字长度B增加指令字长度C保持指令字长度不变而增加操作指令的数量D保持指令字长度不变而增加寻址空间新祥旭考研辅导咨询VX: 1355291571312.下列哪个操作不能由运算器实现()A发出“读”信号B两个整数比较大小C欢迎补充D欢迎补充13.存储一个n阶上三角矩阵需要数组的大小是()Alog2nBn2C. n*(n+1)/2D. n*(n-1)/214. 对于深度为4的栈,入栈顺序为ABCDEF,则出栈顺序可能是()A.AFEDCB B.ABDFEC C.DFABCE D.CEFABD15.下列哪种排序方式,当待排序数列越有序时,排序速度越慢()A选择排序B插入排序C快速排序D冒泡排序16.每一个内存块都可以映射到任意一个cache块中,这种映射方式称为()A直接映射B全相连映射C半相连映射D组相连映射17.下列说法正确的是()Achche的出现是为了解决cpu与主存间容量差异的矛盾B交叉存储器技术可以使不同存储器部分块同时串行传输数据C直接寻址方式不需要进行地址的运算D欢迎补充18.下列哪个不是DMA的工作方式A多路选择B周期挪用C与CPU交替访存D停止CPU访问内存19.二维数组A79,按行优先顺序存放在首地址是600的地址连续的内存空间内,每个数据占两个字节。则A63所在的地址是()A 828 B 814 C 714 D 61420.512K*8容量的DRAM,需要的地址线和数据线条数总数是()A.512 B.64 C.27 D.1021. 对有序表(02,16,24,33,48,57,66,71,79,84,86,91)进行折半查找,查找成功的平均查找长度是()A37/12 B.37/13 C.39/13 D.49/1222.下列关于二叉树的判断正确的是()A 二叉树的度为2B 二叉树中叶子结点的个数是度为二的结点个数加一C 对于n个结点的二叉树,叶子结点个数的二倍加上度为一的结点的个数等于n+1D 如果二叉树前序和后序遍历序列相反,那么二叉树任一结点都没有做左子树23-30 很基础,忘却了。欢迎补充。新祥旭考研辅导咨询VX: 13552915713二填空(30)31.(1)数据采用奇校验码校验方式,补充空格()0110110;()1011001;()0001101(2)奇校验码能检出()位错,纠正()位错(3)奇校验码的码距是多少?32. 一个直接映射的cache大小为512B,块大小为4B,主存以字节编址。主存地址长16位。问:(1)该机器能寻址多大空间(2)cache共分多少块,内存共分多少块(3)画出主存格式示意图,标好位数(4)给出cache地址的映射函数33.给出一组数据:45,06,15,33,81,02,64,77。(1)写出用冒泡排序算法第一趟排序后的状态。(2)写出用快速排序(选择第一个数为基准)第一趟排序后的状态。34.(1)对于n个结点的二叉树遍历的时间复杂度是?(2)一个二叉树如图,给出二叉树的前序,中序,后序遍历序列。(非原图)三简答题(60)35.操作数a,b已经分别存放在寄存器R2,R3中,补码表示。ALU有+,-,M(传送)三种功能。(1)指出哪些微指令是相容的。(2)将(a+b)*1/2的结果存放到R1中,写出此操作的微指令。(3)采用字段直接译码方式定义微指令集,问需要多少字段?给出理由。36.有8K*8的ROM芯片和8K*4的RAM芯片,组成由16K*8的RAM和8K*8的ROM组成的存储器,其中高地址是ROM。(1)计算各需要多少芯片(2)画出连线图。(必须连的线有地址线,数据线,RD,WE,CS,MERQ)。37(10)(1) 给出单链表定义代码(2) 统计数列中比正整数x小的个数,如12.23.32.45.54.65。x=33。返回3。写出你的算法程序,必要处予以注释(3) 把比正数x大的奇数从单链表中删除,写出你的算法程序,必要处予以注释38 (9)有两个字符串A,B,设计一个算法,判断能否在对A进行若干次循环左移或右移之后出现B是A的子串的情况。如A=ABACA,B=CAA,存在;A=ABCBA,B=BAB,不存在。(1) 写出你的算法思想(3)(2) 写出你的算法程序,必要处予以注释(6)39(11)(1) 写出基于邻接表存储的连通图深度优先遍历算法程序(2) 分析你设计的算法的复杂度