新祥旭考研辅导咨询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） 分析你设计的算法的复杂度