清华大学-912-2018-真题版.pdfVIP

各个学校计算机/软件专业考研真题 免费分享 /csseky/cskaoyan 清华大学 912 真题 2018 年回忆版 数据结构： 1.判断(10*2’)： 1)T(n)=a，无论常数a 多大，时间复杂度为T(N)=T(n/2)+O(1)的解总是O(logn) 2)基于CBA 的算法对所有大小为n 的数组时间复杂度是Ω(nlongn) 3)基数排序的底层排序算法一定是稳定的 4)输入随机的情况下完全二叉堆的插入平均时间是常数 5)伸展树插入操作的分摊时间复杂度O(logn) 6)对长度为m=4k+3 素数的散列表双平方探测一定能访问其全部元素 7)没改进的next 算法时间复杂度也是O(n) 8)Fib 查找时以前后黄金分割点作为轴点的常系数相同 9)PFC(最优前缀编码)互换不同深度节点位置一定会破坏其性质 微 10)任何情况下折半查找都比顺序查找快 2.选择(8*3’) ： 信 公 1)就地算法的空间复杂度是 A.O(1) B. C. D. 2)后缀表达式扣去一个符号来猜扣去的是什么，跟去年的类似 众 3)一个非法表达式，问强行求解的值是多少 号 4)7 阶B-树根节点常驻内存，则对规模为2017 的B-树最多需要几次访问？ A. B. C. D. 计 5)散列长为 2017，采用单平方探测，已经存入 1000 个元素，问此时最多有()个懒惰删除的 桶单元9 C. D. 算 A.8 B. 机 6)分别按照递增和递减的顺序依次向平衡二叉树插入元素，则存在常数k 使n=2^k-1 是二者 生成的平衡二叉树相等的 与 A.充要条件 B.必要不充分 软 条件 C.充分不必要条件 D.不充分不必要条件 7)左式堆最右侧链长度为k，则左式堆__含有__个元素。 件 A.最少 2^k B.最少 2^k-1 C.最多 ** D.最多 ** 考 8)gs[0]=1 的概率是 研 A.1/m B.1/2^(m-1) C.1/2^m D.1/2^(m+1) 3.单峰向量(13’) 已知A[0,n ), A[0~k)严格单调递增，A[k~n)严格单调递减，设计一个O(logn)算法找出k 1)伪代码描述算法 2)说明算法正确性 3)证明最坏情况下时间复杂度也是O(logn) 4.最大和区间(13’) 给定一个整数序列，求出连续子序列和的最大值 1)说明算法思路 2)伪代码描述算法 3)说明时间复杂度和空间复杂度 题注(大致意思)：蛮力算法就不要用啦，是O(n^3),只有设计出O(n)算法才有可能满分，O(n^2) 获取 考研经验/复试资料/考研资讯 关注微信公众号 计算机与软件考研 各个学校计算机/软件专业考研真题 免费分享 /csseky/cskaoyan 酌情给分。 计算机原理： 1.判断 1)提高cpu 主频可以加快程序执行速度 2)raid6 坏两个磁盘也可以工作 3)c 语言若int x,y 若xy，则-x-y 2.填空 1)-2017 的32 位补码表示__(16 进制或2 进制)。 2)-2017 的IEEE 单精度浮点表示__ 。 3)高速缓存器的几种映射方式__ 、__ 、__ 。 微 4)处理机__逻辑电路进行算术运算，__逻辑电路用于数据暂存，__逻辑电路用于分支选择。 3.选择 信 公 1) 以下关于五段流水线的处理机说法错误的是 A.多个处理器不会发生结构冲突 B.每个周期执行一个功能 众 号 C.可以采用微程序或者硬连线设计 D.不同的指令执行时间相同 计 2) 以