2018上海大学计算机考研专业课832真题回忆版.docx
2018 上海大学计算机考研专业课 832 真题回忆版一选择(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保持指令字长度不变而增加寻址空间12.下列哪个操作不能由运算器实现()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 很基础,忘却了。欢迎补充。二填空(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 出发的深度优先遍历序列(非原图)