同济大学2008年数据结构试题 回忆

今年的数据结构难度中等。应该说，覆盖面还是相当全的。重点仍然在树和图，尤其是二叉树。

填空和选择15道，都是相当概念性的东西

接下来的算法设计具体题目记不清了，只记得考到了Hash，邻接矩阵，深度和广度优先遍历，哈夫曼编码。
排序算法涉及到了四种：希尔，冒泡，简单排序（还有一个忘了……）。都是要写出两趟排序的结果。


记得比较清楚的是第四大题的程序设计，共四道题

第一题是一道小顶堆元素插入，同时保证不破坏堆结构。15分
相当基本的东西，要求是设计一个函数，堆的数据结构定义已给出


第二题 汉诺塔问题。5分
经典的递归调用问题，要求完成一个函数，输入参数为盘子数、起始柱子、目标柱子和临时柱子。
分很少，如果对递归思想熟悉的话，一两分钟就能做完。
如果不熟悉的话要当场设计一个算法还是有点挑战性的……


第三题 字符串逆向打印。15分（还是10分？不记得了）
给你一个给定字符串，要求利用栈来实现反顺序输出。送分题


第四题 设计一个程序。15分
要求是给你一个一组整数元素，让你来构建一个二叉排序树。
元素插入部分要求使用一个void返回值的insert 函数，接受一个树结点指针和一个数值来完成插入操作。
另外要求实现一个find 函数，找出树中是否存在该元素。
若不存在则输出不存在信息，若存在则输出存在信息以及该元素在树中所处的层数。

综合性的题目，还是二叉树的问题，解法不止一种。虽然不是很难但是也不能掉以轻心。
插入一个元素时可以利用find的结果来快速判定位置，不过两个函数都指定是void返回值因此不能利用返回值来传递结果……


---------------------------------------------------

以上就是我记起来的部分，欢迎各位补充~~