最新-山大软件数据结构期末试题(真题)回顾资料

2012-2013山大软件数据结构期末试题(真题)回顾 一、简答题。

1.插入排序、选择排序、冒泡排序、基数排序、堆排序的算法中其比较次数与初始数据集顺序无关的是？请说明理由。

2.已知待散列的线性表为（1,8,16,27,25,28等数据），散列用的一维地址空间为11，假定选用的散列函数是H（K）= K mod 11，将其存入线性开型寻址散列和链表结构。

3.给一个树的层序遍历，中序遍历，写出其后序遍历。

4.给出二叉搜索树的层序遍历，问这个二叉搜索树是否是完全二叉树。 5.请说明广度优先搜索和深度优先搜索算法中所使用的堆栈、队列的作用。 二、应用题。

1.有学号1-36名学生，如果i , j两个学生住在同一个宿舍用（i,j）表示，集合S={（1,2），（4,19）......}如何求集合S中包含多少宿舍。

2.构建霍夫曼树，求ABCDEF的霍夫曼代码

3.有20门课程，如果i , j两门课的学习顺序为先学i ,再学j那么用（i , j）表示，集合S={(2,3),(4,6)....}，求至少要安排多少学期.4.给出ABCDE消耗邻接矩阵，求A到个点的最短路径

三、算法程序题。

1.一个递增的链表，编写一个算法去除链表中的重复元素。例如，将（7,12,12,14,23）变为（7,12,14,23），请写出算法思想和算法实现并分析算法的复杂性。

2.编写一个算法如何判断一个用二叉树链表存储的二叉树是否是最大堆，写出算法思想

1 / 2

和算法实现。

2 / 2