北京航空航天大学2001试题(f)问答题（本题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)5a2:(V2,V3)6a3:(V2,V5)3a4:(V3,V4)5a5:(V3,V5)6a6:(V4,V5)3a7:(V4,V7)1a8:(V4,V8)4a9:(V5,V6)4a10:(V5,V7)2a11(V6,V10)4a12:(V7,V9)5a13:(V8,V9)2a14:(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分）欲建立一个文库，其正文（文献本身）存放在一个双向循环链表的每个链结点中。为便于链结点的插入、删除操作，以及按题目、发表日期、发表者名称、主题词（假设每文最多给出三个题目）进行搜索，请设计该链表的链结点结构（给出链结点每个域的名称，并说明该域里存放什么信息。注：以下每小题设计链结点也这样要求）。画出整个链表结构的示意图。设计一个三级搜索结构，其中第三级搜索称为题目索引，是按文献题目构造的稠密索引，通过该级索引并根据给定题目可得到每个文献的存放地址；该级索引按文献学科类分类存放。第二级索引称为中类索引，是题目索引索引，指出同一种的文献题目索引的存放位置（例如农林类、气象类……,古代史类,近代史类……）．第一级索引称为大类索引，指出同一大类（如：自然科学类、历史类……）的文献的中类索引的存放位置。请设计每一级索引的结点结构，并画出该索引的整体示意图。再设计一种三级索引结构，其中第三级索引仍是题目索引（与２题所述相同），第二级索引把具有相同主题词的文献题目索引地址组织在一个单链表中。第一级索引称为主题词索引，用文献给出的主题词作关键字组成杂凑表，既该级索引为一个杂凑表，能够指出具有同一主题词的文献题目索引的索引链表的第一个链接点的存储位置。该杂凑表采用链地址法处理冲突。请设计每一级索引的结点结构，并画出该索引的整体示意图。Datalink四．（本题10分）已知非空线性链表由list指出，链结点的构造请写一算法，将链表中数据域值最小的那个结点移到链表的最前面。要求：不得额外申请新的链接点。五已知求两个正整数m与n的最大公因子的过程用自然语言可以表述为反复执行如下动作：第一步：若n等于零，则返回m；第二步：若m小于n，则m与n互换；否则，保存m，然后将n送m，将保存的m除以n的余数送n。将上述过程用递归函数表示出来（设求x除以y的余数可以用xMODy形式表示）。写出求解该递归函数的非递归算法。六函数voidinsert(char*s,char*t,intpos)将字符串t插入到字符串s中，插入位置为pos。请用c语言实现该函数。假设分配给字符串产生的空间足够让字符串t插入。（说明：不得使用任何库函数）七命令sgrep用来在文件中查找给字串，并输出串所在行及行号。命令格式为：sgrep[-i]filenamesearching其中：-i表示查找时大小写无关，省略时表示大小写相关。Filename:给定文件名。Searching:所要查找的串。用c语言实现该程序，该程序应具有一定的错误处理能力。（提示：使用命令行参数）注意：除文件及输入/出操作可使用库函数外，其他不允许使用库函数。