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 新的链结点。
五、(本题15分，第1小题5分，第2小题10分)
41
link 请写一算法，将链表中数据域值最小的那个链结点移至链表的最前面。要求：不得额外申请
已知求两个正整数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：所要查找的串。
用C语言实现该程序，该程序应具有一定的错误处理能力。(提示：使用命令行参数) 注意：除文件及输入/出操作可使用库函数外，其他不允许使用库函数。
西安交通大学2001年数据结构试题
一、判断下列叙述是否正确，正确的填√，不正确的填×(10分) 1．数据对象就是一组数据元素的集合。 ( )
2．任何一棵前序线索二叉树，都可以不用栈实现前序遍历。 ( )
3．就平均查找长度而言，分块查找最小，折半查找次之，顺序查找最大。 ( ) 4．用shell方法排序时，若关键字的排列杂乱无序，则效率最高。 ( ) 5．在m阶B-树中，所有非终端结点至少包含?m／2?。 ( ) 二、选择填空题(15分)
1．假设以数组A[m．．n]存放循环队列的元素，其头指针是front，当前队列有k个元素，则队列的尾指针为( )。 A．(front+k)mod(n-m+1) B．(m+k)mod n+front C．(front-m+k)mod(n-m+1)+m D．(front-m+k)mod(n-m+1)
2． 已知二叉树如右图所示，此二叉树的顺 序存储的结点序列是( )。 A．123□45 B．12345
42
C．12□435 D．□24153
3．若用冒泡排序对关键字序列{20，17，11，8，6，2}从小到大进行排序，则需要交换的总次数为( )。
A．3 B．6 C．12 D．15
4．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是( )。 A．head=NULL B．head->next=NULL C．head->next==head D．head!=NULL
5．已知串s=“ABCDEFGH'’，则s的所有不同子串的个数为( )。 A．8 B．9 C．36 D．37 三、填空题(15分)
1．假设一个12阶的上三角矩阵A按行优先顺序压缩存储在一维数组B中，则非零元素a8，9，在B中的存储位置k= 。
2．在拓扑排序中，拓扑序列的第一个顶点必定是 的顶点。
3．由六个分别带权值为5，12，9，30，7，16的叶子结点构造一棵哈夫曼(Huffinan)树，该树的结点个数为 ，树的带权路径长度为 。
4．在 的情况下，链队列的出队操作需要修改尾指针。
5．对表长为n的顺序表进行分块查找，若以顺序查找确定块，且每块长度为s，则在等概率查找的情况下，查找成功时的平均查找长度为 。 四、简答题(50分)
1．(6分)已知广义表L：((a，b)，(c，(d，(e)))，f)。
(1)试利用广义表取表头head(L)和取表尾tail(L)的基本运算，将原子c从下列广义表中分解出来，请写出运算表达式。
(2)请给出下列表达式的运算结果：
①hem(tail(head(tail(L)))) ②tail(tail(head(L))) 2．(10分)已知一个图G=(V，E)，其中：
V={a，b，c，d，e，f}；
E={
(2)根据邻接矩阵，分别同从顶点a出发的深度优先和广度优先遍历序列。 (3)画出由此得到的深度优先和广度优先生成树(或森林)。
3．(6分)已知一个栈s的输入序列为abcd，下面两个序列能否通过栈的PUSH和POP操作输出；如果能，请写出操作序列；如果不能，请说明原因。 ①dbca ②cbda
4．(5分)设模式串t=”abaabacababa”，试求出t的next和nextval函数值。
5．(7分)已知一组关键字K={20，15，4，18，9，6，25，12，3，22}，请判断此序列是否为堆?如果不是，请调整为堆。 6．(8分)对于表达式(a-b+c)*d/(e+f)
43
(1)画出它的中序二叉树，并标出该二叉树的前序线索； (2)给出它的前缀表达式和后缀表达式。
7．(8分)设散列长度为9，散列函数为H(k)=k mod 9，给出关键字序列：23，45，14，17，9，29，37，18，25，41，33，采用链地址法解决冲突。 (1)请画出散列表；
(2)求出查找各关键字的比较次数；
(3)计算在等概率情况下，查找成功的平均查找长度。
五、算法填空(10分)
已知图的邻接表存储结构描述如下： CONST N=图的顶点数： TYPE arcprt=↑arcnode； arcnode=RECORD adjvex：integer； nextarc：acrptr END；
vexnode=RECORD vexdata：char； firstarc：arcptr END；
Graph=ARRAY[1．．N]of vexnode；
下面是一个图的深度优先遍历的非递归算法，请在 处填上适当内容，使其成为一个完整算法。
PROCEDURE traver_dfs(g：graph)；
VAR visited：ARRAY[1．．N] of BOOLEAN； s：STACK；{s为一个栈} p：arcptr： BEGIN
FORi：=1 TO N DO visited[i]：= ① INISTACK(S)； FOR i=1 TO N DO BEGIN ② BEGIN
visited[i]：=true；
visit(i)； //访问第i个顶点 IF g[i].firstarc≠NIL THEN PUSH(d，g[i].firstarc)
44