清华2018-21
需积分: 0 85 浏览量
2022-08-04
11:35:45
上传
评论
收藏 368KB PDF 举报
数据结构：
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 个元素，问此时最多有()个懒惰删除的
桶单元
A.8 B.9 C. D.
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)
酌情给分。
评论0