2001年中国地质大学地信专业考研试题数据结构

一、简答（20分）

1、若用二元组DS=(D，S)形式说明线性表L，应如何表示L中数据元素集D和关系集S？

2、有五个数据依次进栈：A,B,C,D,E,在各种出栈的序列中，以B,D先出栈的序列有哪几个？（B在D之前出栈）

3、简述循环队列的实现方法，并用图示予以说明，设h和t分别为循环队列Q[0..m]的头指针和尾指针，试给出求当前Q中元素个数的公式。

4、文件的基本组织方式有哪几种？

二、将6个数1，2，3，4，5，6，填入如图所示的二叉树的节点中，使之成为一颗二叉排序树。若把数3.5放入此树并使该树保持性质不变，增加一个节点可放在什么位置？画出两种可能的放置方案（6分）

三、设某通讯电文由A,B,C,D,E,F,G七个字符组成，它们在电文中出现的次数分别是9，5，4，6，2，8，1，试为这七个字符设计Huffman编码 （8分）

四、已知一棵二叉树B的中序遍历序列为DBHEAFJICG，后序遍历序列为DHEBJIFGCA，完成下列各题：（14分）

1、构造该二叉树B

2、写出按先序遍历B

3、画出B的后续前驱线索

五、已知带权的无向图G如下：(16分)

1、画出G的邻接多重表结构以及G的一棵最小生成树

2、写出从顶点V1出发，按深度优先和广度优先搜索G所得到的顶点序列

3、利用Dijkstra算法，求出从顶点V1到其余各顶点的最短路径，要求写出执行算法过程中各步的状态。

六、对长度为n的有序表进行折半查找，指出其平均查找长度，并证明之。（8分）

七、某整型数组A中的9个元素值依次为：

18，10，35，6，27，3，44，30，12

将A中元素按从小到大排序：（不用写算法）（16分）

1、第一个元素值18作为分割数，试写出用“快速排序”对A进行排序的第一趟过程。

2、用“堆排序”，试写出建立初始堆的过程，以及将第一个选出的元素放在A的最后位置上，将A调整为堆后的A中结果。

八、请用PASCAL或C语言设计以下算法 （12分）

1、若以二叉链表作为二叉树B的存储结构，t为指向根节点的指针变量，试编写出B中节点的数目的非递归算法。

2、已知哈希表HT[m]，哈希函数为f(x)，用链地址法处理冲突（同一线性链表中的记录按关键字递减有序, 排列, ），试编写算法；在表中插入关键字值为K的一项。