2006《数据结构》期末试卷 - B

厦门大学《 数据结构 》课程试卷 信息科学与技术学院计算机科学系2004年级＿＿＿专业

主考教师：陈怡疆、庄朝晖、郑旭玲 试卷类型：（B卷） 一、 （本题15分）写一个算法将一带头结点的单链表逆转，要求利用原表结点空间，不

允许申请新的结点空间。

二、 （本题10分）给定广义表（a，（（），ｂ），（（（ｅ）））），完成下列要求：

1）给出广义表的数据结构； 2）画出该广义表的存储结构图；

3）利用取表头和表尾的操分离出原子e（给出GetHead、GetTail的操作序列）。 三、

（本题10分）一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示

出来，试求出空格处的内容，并画出该二叉树。 先序序列：__B__F__ICEH__G； 中序序列：D__KFIA__EJC__ ； 后序序列：__K__FBHJ__G__A。

四、 （本题20分）设一棵二叉树以二叉链表表示，试编写一算法统计二叉树的宽度，即在二叉树的各层上，具有结点数最多的那一层上的结点总数。 typedef struct BiTNode{ TElemType data;

Struct BiTNode *lchild, *rchild; } BiTNode, *BiTree; 五、

（本题10分）设有3阶B－树，如下图所示，分别画出在该树插入关键字20和在原

树删除关键字150得到的B－树。

100 50 80 150 30 40 60 70 90 120 180

1

六、 （本题10分）设待排序的表有8个记录，其关键字分别为：18，2，20，34，12，32，

6，16。写出用2--路归并排序的每趟结果。2-路归并排序是否是稳定的？

七、 （本题20分）若有大写字母、小写字母和数字组成的集合存放在一维数组中，请编

写一个时间复杂度为O(n)的算法，使得数组中的字符按大写字母、数字、小写字母的顺序排列，且辅助空间为O(1)。

[提示]本题只要求对字符按大写字母、数字、小写字母三种分类顺序排列，对同类字符之间的排列顺序并无特定要求。 八、

（本题5分）请谈谈学习《数据结构》课程的心得体会，并以某个算法为例谈谈对该

算法的理解。

2

百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说教育文库2006《数据结构》期末试卷 - B在线全文阅读。