数据结构与算法¶

这是中国科学院大学人工智能专业本科生课程《数据结构与算法》的考前重点和题库答案解析（原创）。笔者该门课程取得满绩。

考前重点¶

fibsearch：每次选择mi时，mi-lo为fib-1,且mi达到最大
插值查找平均时间复杂度：O(loglogn)
插值排序时，解出来mi要向下取整
向量中search约定相同返回秩最大的
归并排序的最优、最坏、平均时间复杂度都是nlogn
如果一个列表的 visible list 部分长度为 n，则头、首、末、尾节点的秩分别为 -1, 0, n-1, n
列表的selectsort，在遇到相同的时候，选出最后一个的放到最后
insertionsort最好O(n)，平均和最坏时$O(n^{2})$
向量归并排序时间复杂度为$O(nlog_{2}(n)),列表为O(n^{2})$

题库答案¶

重点：6，9，10，12，14，20，25，27，33，37，

易错问题：1，2，3，4，6，10，14，15，17,18，19，29,30

C (尽管有程序，但是程序不等于算法。该问题目前还没有结论。)
D（易错，答案是效率，而不是正确）
A（图灵机组件：无限长纸带、有限字母表、读写头、有限种状态）
B（RAM为random access machine，拥有无限存储，而图灵机也有无限存储。它们区别在于可以RAM可以通过编号直接访问任意位置元素）
B（定义）
D (C选项可以使用斯特林公式)
B （一个平凡；另一个规模更小即可，不要求平凡）
B（都是O(n)）
B(复杂度为$\theta (1+2+4+……+2^{n-2})=\theta (2^{n-1})=O(2^{n})$)
D（普通计算机的速度：）
D(递推，空间只需要两个变量)
C（A错在哪，）
C(注意下标从0开始，且insert时如果当前位置有元素了，需要把它也后移)
B（最后为71，装填因子为实际/总空间）
A(hi是最后一个元素的后一个位置，lo是第一个元素的位置，左闭右开)
B（总时间复杂度 $O(n^{2})$，分摊时间复杂度 $O(n)$）
A （内存翻倍总量 $O(1+2+...+2^{m-1})=O(2^{m})=O(n)）
C（没有大小关系）
B（定义）
B（算法定义）
A（uniquify：唯一化）
C（有序，所以一定紧邻）
A（哨位在-1）
D（search返回不大于的最后一个元素）
A(hi是最后一个元素后一个，lo是第一个元素)
C(右移的定义)
B（和7两次，然后和13两次，然后和17一次）
A（只和相对大小有关）
C（D选项渐进复杂度都是O(logn)）
D（每次选择mi时，mi-lo为fib-1,且mi达到最大）
C (插值查找 = 在字长意义上的折半查找，二分查找 = 在字长意义上的顺序查找)
1（向下取整）
D（版本A可能一次就找到了，B和C都需要做到底）
A（search约定）
D（算法定义）
C（模拟）
B（有一次什么都没交换）
C（稳定不会改变上一次的排序结果）
A（模拟）
B（归并排序的最优、最坏、平均时间复杂度都是nlogn）
A（列表用指针实现）
C（C选项，分别为-1,0,n-1,n）
C（模拟）
D（O(n/2)=O(n)）
A（反复判断相邻两个是否相等，如果相等就直接删除后者）
C（只能扫一遍）
C（每次选最大的，所以是降序）
A（采用比较器!lt()或ge()，从而等效于后者优先，选出最靠后的移到最右边）
C（最坏都是平方）
C（倒序）
B（最好是O(n)，因为search是从后往前search，所以如果已经有序的话每次search都只要一次）
C（在时刻k始终保证前k个有序且元素不变，后k个无序且元素不变，A是选择排序）
C（每次迭代多一个元素有序）
C（定义）
B（这种题模拟即可）
B（无法随机访问，只能顺序查找）
C（每次找最大的）
A（最小的移到前面选最前面的，最大的移到后面选最后面的）
C（同52）
B（插入排序保证前r个元素不变且有序）
（答案B）
B($O(k^{2}*\frac{n}{k})=O(nk)$)
C（模拟）
B（左括号进栈，右括号出栈）
B（312型不是栈混洗，或直接模拟）
14（长度为n的序列的栈混洗数为第n个卡特兰数，$C_{4}$=14）
D（两个栈，遇到操作数压入操作数栈，遇到操作符如果比操作符栈顶高就压入操作符栈，否则弹出两个操作数进行运算再压入操作数栈，最后处理剩余）
B（逆波兰：后缀；波兰：前缀。后缀遇到操作符就弹出两个数）
B（画树）
A（模拟）
A（短除法）
D（模拟）
C（312型不是）
B（卡特兰数问题：网格计数、01序列、栈混洗（312排列）、不相交弦问题、二叉搜索树总数；卡特兰数通项$h(n)= \frac{1}{n+1} \binom{2n}{n}$）
C（左括号小于一切，右括号大于一切）
123!x+45x7-/
C（不用有向）
A（高度不一定差1）
B（O(3n)=O(n)）
D（真二叉树：所有度数要么0要么2）
B
C
（答案D）
C（模拟）
D（模拟）
C（层次遍历概念）
B（左节点）
B（层次遍历每层依次扩展）
A（后序遍历概念）
D（C添加节点就不会）
D（深度从上往下，高度从下往上。根节点深度0，叶子结点高度0。空树高度-1。高度定义为子节点最大高度+1）
C（右子树为空时是祖先）
D（模拟）
C（模拟）
D（只有先后不能推中，两个节点的二叉树（左右节点互换）就是最简单的反例）
D（高度父子可能不相差1）
A（A最对，B也对）
B（定义）
C（链）
C（模拟）
B（插入操作的定义）
C（重点，细看。先交换再删除）
B（中序遍历不变）
C（插入节点，从祖父开始往上，所有祖先都有可能失衡，O(logn)）
A（删除节点，从父亲开始往上，所有祖先都有可能失衡，但是只可能失衡一个，O(1)）
（答案B）A（既然已经失衡了，那么调整后就一定会减小1）
B（中序遍历不变）
D（旋转后原来最高的那个没变）
14（卡特兰数）
11（模拟）
D（模拟）
C（最坏单链）
B（保证中序遍历不变）
B（局部性：刚被访问过的数据，极有可能很快地再次被访问）
C（每次移到根）
B（每两层）
B（两层一半）
B（分摊复杂度logn）
A（zig-zag和zag-zig是一样的，关键在于子孙同侧的情况）
错（依然有可能退化成链）
D（zag左旋，zig右旋）
A（局部性强、缓存命中率极高时，分摊每一次操作O(logk)）
对（退化）
B（尽量矮胖）
A（每一层IO一次）
C（分支 $[\lceil \frac{m}{2} \rceil , m]$ ，元素 $[\lceil \frac{m}{2}-1 \rceil , m-1]$）
A（查找O(logn)，但这题问的是单个节点上的查找）
B（返回NULL代表失败）
B（相对于BBST，降低为 $\frac{1}{log_{2}m}-1$ ）
B（插入后超过最大可容纳）
C（为什么不是B？）
C（删除后小于 $\lceil \frac{m}{2} \rceil$ 了）
A（合并不是被旋转）
（答案错）
错（说的是B数）
错（伸展树无需记录高度或平衡因子，编程实现简单，优于AVL树）
错（伸展树分摊复杂度O(logn)，与AVL树相当）
对（伸展树会退化为链，AVL不会）
B（一次旋转）
A（中间节点选择 $\lfloor \frac{m}{2} \rfloor$，从0编号）
C（高度减半且1在根）
D（zigzig）
A(都余5)
B（必定冲突）
B（如果是单射就不满足不等式）
3（0,8,4）；9（0,8,5,2,10,7,4,1,9）
B（A指针不在桶内部，B正确，C仍然存放在桶里，D存疑）
D（计算）
A（模拟）
（完全平方数mod一个素数，最多的可能取值有p/2向下取整+1（或者p/2上取整）种可能，答案0.5）
D（画图）
C（都要把所有的遍历一遍）
D（一列+一行）
D（概念）
A（模拟）
C（每个定点、每条边遍历一次）
B（模拟）
B
C（都是n-1）
B（有向图）
190 19
7
A
D
（答案B）
（答案C）
（答案2,65,7）
（答案3,14,7,12）
对
对
D（拓扑不唯一）
A（拓扑不唯一）
C（遍历一遍）
C（模拟）
对（prim：染色）
B（单源最短路径）
B（无向图没有强联通）
B（算法定义）
正确（算法定义）
对（算法定义）
（答案A）
A
C
A（只能删最大的）
C
A
A
B
A
C
D
EACBD
B

213.

C