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一般采用DRAM
B．SRAM不需要刷新
C．SRAM比DRAM集成度高
D．DRAM是非易失性存储器
4.下列操作复杂度为O（1）的是（）
A．在顺序表中插入一个元素
B．在单链表中访问一个元素
C．在单链表中插入一个元素
D．在顺序表中访问一个元素
5.数组中有100个递增存储的整数，折半查找时查找一个元素的比较次数不可能超过（）
A.100 B.25 C.10 D.9
6.一个完全二叉树共有100个结点，则有共有（）个叶子结点
A.26 B.33 C.44 D.45
7.一般家用台式电脑是（）
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．log2n
B．n^2
C. n*(n+1)/2
D. n*(n-1)/2
14. 对于深度为4的栈，入栈顺序为ABCDEF，则出栈顺序可能是（）
A.AFEDCB B.ABDFEC C.DFABCE D.CEFABD
15.下列哪种排序方式，当待排序数列越有序时，排序速度越慢（）
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]所在的地址是（）
A 828 B 814 C 714 D 614
20.512K*8容量的DRAM，需要的地址线和数据线条数总数是（）
A.512 B.64 C.27 D.10
21. 对有序表（02，16,24,33,48,57,66,71,79,84,86,91）进行折半查找，查找成功的平均查找长度是（）
A．37/12 B.37/13 C.39/13 D.49/12
22.下列关于二叉树的判断正确的是（）
A 二叉树的度为2
B 二叉树中叶子结点的个数是度为二的结点个数加一
C 对于n个结点的二叉树，叶子结点个数的二倍加上度为一的结点的个数等于n+1
D 如果二叉树前序和后序遍历序列相反，那么二叉树任一结点都没有做左子树
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出发的深度优先遍历序列（非原图）
发表于 2017-12-26 01:46
收藏
分享
支持
反对
楼主
