北航2001数据结构

北京航空航天大学程序设计与数据结构试题
(2001年)

一、        问答题(10’)
一般情况下，线性表可以采用哪几种存储结构？请分别叙述每一种存储结构的构造原理与特点。
二、        (10’)
已知AOE网为G=(V，E)，其中V={v1，v2，v3，v4，v5，v6，v7，v8，v9，v10}，E={a1，a2，a3，a4，a5，a6，a7，a8，a9，a10，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        a10:(v5，v7)2        a11(v6，v10)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与le分别表示事件vi的最早发生时间与最晚发生时间；e与l分别表示活动ai的最早开始时间与最晚开始时间。
三、        (10’)
欲建立一文献库，其正文(文献本身)存放在一个双向循环链表的各个链接点中。
1.为便于链接点的插入、删除操作，以及按题目、发表日期、发表者名称、主题词(假设每文最多给出三个主题词)进行检索，请设计该链表的链接点结构(给出链接点每个域的名称，并说明该域内存放什么信息。注：以下各小题设计链结点结构也这样要求)。画出整个链表结构的示意图。
2.设计一个三级索引结构，其中第三级索引称为题目索引，示按文献题目构造的稠密索引，通过该级索引并根据给定题目可得到每个文献的存放地址；该级索引按文献学科类分类存放。第二级索引称为中类索引，是题目索引的索引，指出同一中类的文献题目索引的存放位置(例如农林类、气象类……，古代史类，近代史类……)。第一级索引称为大类索引，指出同一大类(如：自然科学类、历史类……)的文献的中类索引的存放位置。请设计每一级索引的结点结构，并画出该索引的整体示意图。
3.在设计一种三级索引结构，其中第三级索引仍是题目索引(与2题所述相同)，第二级索引把具有相同主题词的文献题目索引地址组织在一个单链表中。第一级索引称为主题词索引，用文献给出的主题词做关键字组成杂凑表，即该级索引为一个杂凑表，能够指出具有同一主题词的文献题目索引的索引链表的第一个链结点的存储位置。该杂凑表采用链地址法处理冲突。请设计每一级索引的结点结构，并画出该索引的整体示意图。
四、(10’)
已知非空线性链表由list指出，链结点的构造为 ，请写一算法，将链表中数据域值最小的那个链结点移至链表的最前面。要求：不得额外申请新的链接点。
五、(5’+10’)
已知求两个正整数m与n的最大公因子的过程用自然语言可以表述为反复执行如下动作：
第一步：若n等于零，则返回m；
第二步：若m小于n，则m与n相互交换；
否则保存m，然后将n送m，将保存的m除以n的余数送n。
1.将上述过程用递归函数表达出来(设求x除以y的余数可以用x MOD y形式表示)。
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：所要查找的串。
用C语言实现该程序，该程序应具有一定的错误处理能力。(提示：使用命令行参数)
注意：除文件及输入/出操作可使用库函数外，其它不允许使用库函数。