没有合适的资源?快使用搜索试试~ 我知道了~
资源详情
资源评论
资源推荐
数据结构
1.判断(2’*10=20’)
1)若 T(n)=a>0,对于
,则不管 a 多大,总有
。
2)基于 CBA 的算法对所有大小为 n 的数组时间复杂度是 Ω(nlogn)
3)基数排序的底层排序算法一定是稳定的
4)输入随机的情况下完全二叉堆的插入平均时间复杂度是 O(1),虽然最坏是 O(n)
5)对于任一有序列表,即使在最坏的情况下,折半查找的效率也不会低于顺序查找。
6)即使不优化 next[]数组,KMP 算法的复杂度也可以达到线性。
7)fibsearch()时以前后黄金分割点作为轴点的常系数相同
8)即使对理想随机的访问序列,二叉伸展树也能达到均摊 O(logn)的访问时间。
9)PFC(最优前缀编码)互换不同深度节点位置一定不会是 pfc
10)对长度为 m=4k+3 素数的散列表双平方探测一定能访问其全部元素
2.选择(3’*8=24’)
1)就地算法是指空间 T(n)=( )
A.O(1) B.O(n) C.
D.
2)对于逆波兰式 0!1+23!4+^*56!7*8!?/-9+的值等于 2017,则?处的运算符为
A.加号 B.减号 C.乘号 D.除号 E.乘方 F.阶乘
3) 对于长度为 m 的随机 0-1 串进行串匹配时好后缀数组中 gs[0]=1 的概率为
A.
B.
C.
D.
4) 一个右侧路径长度为 k 的左式堆,其顶点数量( )为( )
A.至少;
B.至少;
C.至多;
D.至多;
5) 对于同一个长度为 n 的序列分别按照递增和递减的顺序构造 AVL 树,那么“存在正整数
k,使
”是“两次构造的堆相同”的( )
A.充分不必要条件 B. 必要不充分条件 C. 充分必要条件 D. 既不充分也不必要条件
6) 一个具有 2017 个节点的 7 阶 B 树,若根节点常驻内存,则一次查找最多进行( )次
I/O 操作
A.7 B.6 C.5 D.4
7) 散列长为 2017,采用单平方探测,已经存入 1000 个元素,问此时最多有()个懒惰删除的
桶单元
A.8 B.9 C.1016 D.1017
8) 非法表达式(12)3+!4*+5,执行 evaluate 算法后的结果
A.99 B.89 C.88 D. 98
3. 单峰向量(好像是 16’)
单峰向量定义为 A[0, n),其中前缀{a
0
, a
1
, …, a
k
}严格递增,后缀{a
k+1
, a
k+2
, …, a
n-1
}严格递减。
1) 设计算法在 O(logn)的时间内找到最大值所在位置 k。
2) 证明你算法的正确性。
3) 证明即使在最坏的情况下,你的算法复杂度也不会超过 O(logn)。
XU美伢
- 粉丝: 23
- 资源: 341
上传资源 快速赚钱
- 我的内容管理 展开
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功
评论0