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)； 二叉树B2 prinft(”%c”，root->data)； traversal(root->rchild)； } }

七、算法设计题(要求：(1)写出所用数据结构的类型定义和变量说明；(2)写出算法，并在相关位置加注释，以提高算法的可读性。)

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．树的后根遍历序列等同于该树对应的二叉树的 。

13

A．先序序列 B．中序序列 C．后序序列 二、填空(8分，每空1分)

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； }

}

2．全国统考答题

设二叉树用二叉链表存储，试编写按层输出二叉树结点的算法。 3．单独考试答题(可在2或3中任选一题做)

试编写在带头结点的单链表中删除(一个)最小值结点的(高效)算法。 void delete(Linklist &L)

北京邮电大学2001年数据结构试题

一、选择题(10分，每题2分)

1．B+树是应用在( )文件系统中。 ①ISAM ②VSAM

2．将一棵树t转换为孩子-兄弟链表表示的二叉树h，则t的后根遍历是h的( )。

14

①前序遍历 ②中序遍历 ③后序遍历

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．特殊矩阵和稀疏矩阵哪种压缩存储后会失去随机存取的功能?为什么? 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)。

0 2 ∞ ∞

∞ 0 1 6 A= 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分)

一般情况下，线性表可以采用哪几种存储结构?请分别叙述每一种存储结构的构造原理与特点。

15

二、(本题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}，其中：

a1：(v1，v2)5 a2：(v1，v3)6 a3：(v2，v5)3 a4：(v3，V4)3 a5：(v3，v5)6 a6：(v4，v5)3 a7：(v4，v7)1 a8：(v4，v8)4 a9：(v5，v6)4 al0：(v5，v7)1 a11：(v6，vl0)4 a12：(v7，v9)5 a13：(v8，v9)2 a14：(v9，v10)2

注：顶点偶对右下角的数字表示边上的权值。

请按下述过程指出所有关键路径：

ee[1:10]:

le[1:10]: e[1:14]: l[1:14]:

其中，ee[i]与le[i]分别表示事件vi的最早发生时间与最晚发生时间；e[i]与l[i]分别表示活动ai的最早开始时间与最晚开始时间。

三、(本题共30分，每小题10分)

欲建立一文献库，其正文(文献本身)存放在一个双向循环链表的各个链结点中。

1．为便于链结点的插入、删除操作，以及按题目、发表日期、发表者名称、主题词(假设每文最多给出三个主题词)进行检索，请设计该链表的链结点结构(给出链结点每个域的名称，并说明该域内存放什么信息。注：以下各小题设计链结点结构也这样要求)。画出整个链表结构的示意图。

2．设计一个三级索引结构，其中第三级索引称为题目索引，是按文献题目构造的稠密索引，通过该级索引并根据给定题目可得到每个文献的存放地址；该级索引按文献学科类分类存放。第二级索引称为中类索引，是题目索引的索引，指出同一中类的文献题目索引的存放位置(例如农林类、气象类??，古代史类、近代史类??)。第一级索引称为大类索引，指出同一大类(如：自然科学类、历史类??)的文献的中类索引的存放位置。请设计每一级索引的结点结构，并画出该索引的整体示意图。

3．再设计一种三级索引结构，其中第三级索引仍是题目索引(与2题所述相同)，第二级索引把具有相同主题词的文献题目索引地址组织在一个单链表中。第一级索引称为主题词索引，用文献给出的主题词作关键字组成杂凑表，即该级索引为一个杂凑表，能够指出具有同一主题词的文献题目索引的索引链表的第一个链结点的存储位置。该杂凑表采用链地址法处理冲突。请设计每一 级索引的结点结构，并画出该索引的整体示意图。

四、(本题10分)

已知非空线性链表由list指出，链结点的构造为

data link 请写一算法，将链表中数据域值最小的那个链结点移至链表的最前面。要求：不得额外申请新的链结点。

五、(本题15分，第1小题5分，第2小题10分)

已知求两个正整数m与n的最大公因子的过程用自然语言可以表述为反复执行如下动作： 第一步：若n等于零，则返回m；

第二步：若m小于n，则m与n相互交换；否则，保存m，然后将n送m，将保存的m除以n的余数送n。

1．将上述过程用递归函数表达出来(设求x除以y的余数可以用xMODy形式表示)。 2．写出求解该递归函数的非递归算法。 六、(本题10分)

函数void insert(char *s，char *t，int pos)将字符串t插入到字符串s中，插入位置为pos。请用C语言实现该函数。假设分配给字符串s的空间足够认字符串t插入。(说明：不得使用任何库函数。) 七、(本题15分) 。

命令sgrep用来在文件中查找给定字符串，并输出串所在行及行号。 命令格式为：sgrep[-i]filename searchstring

其中：-i：表示查找的大小写无关，省略时表示大小写相关。 filename：给定文件名。

searchstring：所要查找的串。

16