南师大数学与计算机学院
计算机专业《数据结构》试题（A卷）2007.7.8
班级学号姓名
一、简要回答下列问题（共52分）
1．算法与程序有何区别和联系？（6分）
2．树的存储方法主要有哪些？任你画一个树举例说明具体存储结构。

（6分）3．设有序表的长度为10，用二分查找方法进行查找，试计算查找成功情况下的平均查找长度（6分）
4．图的遍历方法主要有哪些？任你画一个图举例具体说明。

（6分）
5．画出广义表D=(( )，x，(a，(b，c)))的存储结构，并写出广义表类型定义。

（6分）
6. 分别画出一个B树和B+树的例子，并指出它们之间的区别。

（6分）
7.你知道有哪些排序算法？试比较各种排序算法的性能。

（8分）
8．设一组关键字为（7，15，20，31，48，53，64，76，82，99），Hash函数H（key）= key % 11，Hash表表长m=11，用线性探测法解决冲突，试构造Hash表，并分别计算查找成功和查找失败情况下的平均查找长度。

（8分）
二、简述利用Dijkstra算法求解从某顶点到其余各顶点最短路径的步骤。

（12分）
三、试编写归并排序算法。

（12分）
四、试编写一个算法将线性表L中的数据建立一棵二叉排序树。

（12分）
五、设单链表L中的结点按data域数值递减排列，试设计一个算法将L中的结点按data域数值递增加排列，要求算法的时间复杂性为O（n）。

（12分）。