while(pa)
{pc=hc； qc=hc->next； search= ； while(qc&&search) {if(pa->data<=qc->data) ； else { pc=qc； qc= ； } }
fa= ； pa= ； fa->next= ； ； } }
六、设下图二叉树B2的存储结构为二叉链表，root为根指针，结点结构为：(1child，data，rchild)其中：lchild，rchild分别为指向左右孩子的指针，data为字符型。(共10分)
1． 对下列二叉树B2，执行下列算法traversel(root)，试指出其输出结果；
2．假定二叉树B2共有n个结点，试分析算法traversal的时间复杂度。结点类型定义如下：
struct node { chardata；
struct node *lchild，*rchild；
}； 算法如下：
void traversal(struct node *root) { if(root)
{ prinft(“%c”，root->data)； traversal(root->lchild)； prinft(”%c”，root->data)； traversal(root->rchild)； } }
七、算法设计题(要求：(1)写出所用数据结构的类型定义和变量说明；(2)写出算法，并在相关位置加注释，以提高算法的可读性。)
36
二叉树B2
1．试设计一算法：输入一个有m行n列的整数矩阵，然后将每一行的元素按非减次序输出。例如，若输入：
4，3，5，6，2 9，8，1，2，8 7，1，2，3，8 则输出如下结果： 2，3，4，5，6 1，2，8，8，9 1，2，3，7，8
2．如果字符串的一个子串(其长度大于1)的各个字符均相同，则称之为等值子串。试设计一算法：输入字符串S，以’!’为结束标志，如果串S中不存在等值子串，则输出信息：”无等值子串”，否则求出(输出)一个长度最大的等值子串。 例如，若S=”abcl23abcl23！”，则输出：”无等值子串”；
又如，若S=”abcaabcccdddddaaadd!”，则输出等值子串：”ddddd”。(共20分)
北京理工大学2001年程序设计(含数据结构)试题
第二部分 数据结构(共50分)
一、选择题(12分，每题2分)
1．下列数据中哪些是非线性数据结构 。
A．栈 B．队列 C．完全二叉树 D．堆 2．静态链表中指针表示的是 。 A．内存地址 B．数组下标 C．下一元素地址 D．左、右孩子地址
3．用不带头结点的单链表存储队列时，其队头指针指向队头结点，其队尾指针指向队尾结点，则在进行删除操作时 。 A．仅修改队头指针 B．仅修改队尾指针 C．队头，队尾指针都要修改 D．队头，队尾指针都可能要修改
4．在下列排序算法中，哪一个算法的时间复杂度与初始排列无关 。 A．直接插入排序 B．起泡排序 C．快速排序 D．直接选择排序
5．二叉树第i层结点的结点个数最多是(设根的层数为1) 。 A．2i-1 B．2i-1 C．2i D．2i-1 6．树的后根遍历序列等同于该树对应的二叉树的 。 A．先序序列 B．中序序列 C．后序序列 二、填空(8分，每空1分)
37
1．数据结构中评价算法的两个重要指标是——。
2．顺序存储结构是通过 表示元素之间的关系的。链式存储结构是通过 表示元素之间的关系的。
3．AOV网中，结点表示 ，边表示 。AOE网中，结点表示 ，边表示 。 4．哈夫曼树是 。
三、求解下列问题(25分，每题5分) 1．请用C语言给出线性链表的类型定义。
2．已知二叉树的先序序列：CBHEGAF，中序序列：HBGEACF，试构造该二叉树。 3．设散列表的地址空间为0到12的存储单元，散列函数为：h(key)=key mod 13，用链地址法解决冲突，初始时散列表为空。现依次将关键字25，33，48，25，43，38，39插入散列表，试画出完成上述所有插入操作后散列表的状态，并计算在等概率的情况下，在该表中查找成功的平均查找长度。 4．给出如下图所示的图形。 1)试写出该图的邻接表；
2)试写出该图从结点0出发的深度优先遍历序列和广度优先遍历序列，并画出遍历过程中所经的路径。
5．全国统考答题
对上图，按迪杰斯特拉算法求出从结点0到其余各点的最短路径，并给出在求解过程中数组distance的变化状态。
6．单独考试答题(可在5或6中任选一题做)
给出关键字序列27，18，21，77，26，45，66，34试写出快速排序的过程。 四、算法题(12分)(请在算法的主要步骤上加注释)
1．下面是用C语言编写的对不带头结点的单链表进行就地置逆的算法，该算法用L返回置逆后链表的头指针。试在空缺处填入适当的语句。 void reverse(1inklist&L) { p=NULL；q=L； while(q!=NULL)
{
q->next=p； p=q；
38
} }
2．全国统考答题
设二叉树用二叉链表存储，试编写按层输出二叉树结点的算法。 3．单独考试答题(可在2或3中任选一题做)
试编写在带头结点的单链表中删除(一个)最小值结点的(高效)算法。 void delete(Linklist &L)
北京邮电大学2001年数据结构试题
一、选择题(10分，每题2分) 1．B+树是应用在( )文件系统中。 ①ISAM ②VSAM
2．将一棵树t转换为孩子-兄弟链表表示的二叉树h，则t的后根遍历是h的( )。 ①前序遍历 ②中序遍历 ③后序遍历
3．一个有向无环图的拓扑排序序列( )是惟一的。 ①一定 ②不一定
4．将10个元素散列到100000个单元的哈希表中，则( )产生冲突。 ①一定会 ②一定不会 ③仍可能会
5．若要求尽可能快地对序列进行稳定的排序，则应选( )。 ①快速排序 ②归并排序 ③冒泡排序 二、填空题(20分，每空2分) 1．数据的逻辑结构是指 。
2．区分循环队列的满与空，只有两类办法，它们是 和 。
3．用一维数组B以列优先存放带状矩阵A中的非零元素A[i，j](1≤i≤n，i-2≤j≤i+2)，B中的第8个元素是A中第 行、第 列的元素。 4．字符串’ababaaab’的nextval函数值为——。
5．下图中的强连通分量的个数为 个。
6．外部排序的基本方法是归并排序，但在之前必须先生成 。
7．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的 和记录的
三、简答题(15分，每题5分)
1．特殊矩阵和稀疏矩阵哪种压缩存储后会失去随机存取的功能?为什么?
39
2．试问线索二叉树的目的何在?
3．在多关键字排序时，LSD和MSD两种方法的特点是什么? 四、应用题(25分，每题5分)
1．画出按下表中元素的顺序构造的平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。
{15，12，24，3，27，21，18，6，36，33，30，26，3}
2．假设用于通信的电文由字符集{a，b，c，d，e，f，g}中的字母构成，它们在电文中出现的频率分别为{0.31，0.16，0.10，0.08，0.11，0.20，0.04}。 (1)为这7个字母设计哈夫曼编码；
(2)对这7个字母进行等长编码，至少需要几位二进制数?哈夫曼编码比等长编码使电文总长压缩多少?
3．试推导当总盘数为n时的Hanoi塔的移动次数。
4．一棵满k叉树，按层次遍历存储在一维数组中，试计算结点下标为u的结点的第i个孩子的下标以及结点下标为v的结点的父母结点的下标。
5．有一图的邻接矩阵如下，试给出用弗洛伊德算法求各点间最短距离的矩阵序列A(1)、A(2)、A(3)和A(4)。
A= 0 2 ∞ ∞ ∞ 0 1 6 5 ∞ 0 4 3 ∞ ∞ 0 五、算法(30分，每题10分)
1．在单链表中，每个结点含有5个正整型的数据元素(若最后一个结点的数据元素不满5个，以值0填充)，试编写一算法查找值为n(n>0)的数据元素所在的结点指针以及在该结点中的序号，若链表中不存在该数据元素则返回空指针。
2．将一组数据元素按哈希函数H(key)散列到哈希表m(0．．m)中，用线性探测法处理冲突(H(key)+1、H(key)+2、?、H(key)-1，假设空单元用EMPTY表示，删除操作是将哈希表中结点标志位从INUSE标记为DELETED，试写出该散列表的查找、插入和删除三个基本操作算法。
3．给出算法将二叉链表表示的表达式二叉树按中缀表达式输出，并加上相应的括号。
北京航空航天大学2001年 数据结构与程序设计试题
一、问答题(本题10分)
一般情况下，线性表可以采用哪几种存储结构?请分别叙述每一种存储结构的构造原理与特点。
二、(本题10分)
已知AOE网为G=(V，E)，V={v1，v2，v3，v4，v5，v6，v7，v8，V9，vl0}，E={a1，a2，a3，a4，a5，a6，a7，a8，a9，al0，a11，a12，a13，a14}，其中：
40