BUAA高工20级数据结构考题回忆版

判断(2分一题)

1.N个结点的树分有N-1条边

2.Python向下兼容性很好

3.兄弟伙伴算法分配内存速度很快

4.冒泡排序不稳定，快速排序稳定

5.一个字符串字母出现次数全不相同，字母的哈夫曼编码唯一

6.树的后序遍历和转化成二叉树的中序遍历结果相同

(只记得6道了，但其他应该很简单，秒选那种，所以没啥印象)

问答

数据结构常见的操作（5分

给稀疏矩阵，画三元组存储结构和十字链表存储结构（8

给中序后序遍历序列，画中序后序线索二叉树

详细说明并举例B_树插入删除

代码

详细说明LL LR失衡原因并给出LL LR旋转代码(20)

非递归堆排序代码，可以用sstack类(20)

(做梦也没想到会考这个，还好我记得)

总结

数据结构考试整份卷子一个图的算法都没有，考得又偏又怪。想拿到好成绩唯一办法就是把老师所有PPT背一遍，建议不要面向往年题复习，题目方向差异较大(19年考了KMP 最小生成树 AOE，而20年完全没有涉及图)