2018上海大学计算机考研832真题回忆版

2018上海大学计算机考研832真题回忆版一．选择（2*30）每一道选择题保证是考察的原题，但是具体的数字可能有出入。对于不能保证数字正确的题目都找到了类似的题目以保证问题与答案的匹配性。1.下列排序算法稳定的是（）A．冒泡排序，直接插入排序B．基数排序，希尔排序C．堆排序，选择排序D．归并排序，快速排序2.下列不同进制数中真值最大的是（）A．00111001（2）B．45（8）C．29（16）D．97（10）3.以下说法正确的是（）A．cache一般采用DRAMB．SRAM不需要刷新C．SRAM比DRAM集成度高D．DRAM是非易失性存储器4.下列操作复杂度为O（1）的是（）A．在顺序表中插入一个元素B．在单链表中访问一个元素C．在单链表中插入一个元素D．在顺序表中访问一个元素5.数组中有100个递增存储的整数，折半查找时查找一个元素的比较次数不可能超过（）A.100B.25C.10D.96.一个完全二叉树共有100个结点，则有共有（）个叶子结点A.26B.33C.44D.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．保持指令字长度不变而增加寻址空间12.下列哪个操作不能由运算器实现（）A．发出“读”信号B．两个整数比较大小C．欢迎补充D．欢迎补充13.存储一个n阶上三角矩阵需要数组的大小是（）A．log2nB．n^2C.n*(n+1)/2D.n*(n-1)/214.对于深度为4的栈，入栈顺序为ABCDEF，则出栈顺序可能是（）A.AFEDCBB.ABDFECC.DFABCED.CEFABD15.下列哪种排序方式，当待排序数列越有序时，排序速度越慢（）A．选择排序B．插入排序C．快速排序D．冒泡排序16.每一个内存块都可以映射到任意一个cache块中，这种映射方式称为（）A．直接映射B．全相连映射C．半相连映射D．组相连映射17.下列说法正确的是（）A．chche的出现是为了解决cpu与主存间容量差异的矛盾B．交叉存储器技术可以使不同存储器部分块同时串行传输数据C．直接寻址方式不需要进行地址的运算D．欢迎补充18.下列哪个不是DMA的工作方式A．多路选择B．周期挪用C．与CPU交替访存D．停止CPU访问内存19.二维数组A[7][9],按行优先顺序存放在首地址是600的地址连续的内存空间内，每个数据占两个字节。则A[6][3]所在的地址是（）A828B814C714D61420.512K*8容量的DRAM，需要的地址线和数据线条数总数是（）A.512B.64C.27D.1021.对有序表（02，16,24,33,48,57,66,71,79,84,86,91）进行折半查找，查找成功的平均查找长度是（）A．37/12B.37/13C.39/13D.49/1222.下列关于二叉树的判断正确的是（）A二叉树的度为2B二叉树中叶子结点的个数是度为二的结点个数加一C对于n个结点的二叉树，叶子结点个数的二倍加上度为一的结点的个数等于n+1D如果二叉树前序和后序遍历序列相反，那么二叉树任一结点都没有做左子树23-30很基础，忘却了。欢迎补充。二．填空（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）分析你设计的算法的复杂度（3）根据下图写出邻接表，并根据你的邻接表给出从结点0出发的深度优先遍历序列（非原图）