东南大学数据结构考研题

1993年考研题

一、回答下列问题 (共 35分):

1. 与链式结构相比，线性表的顺序存贮的一个主要优点和一个主要缺点分别是什么? (4分)

2. 在表达式中，有的运算符要求从右到左计算，如A**B**C的计算次序应为(A**(B**C))，这在由中

缀生成后缀的算法中是怎样实现的?(以**为例说明 ) (6分)

3. 给出KMP 算法中失败函数f 的定义，并说明利用f 进行串模式匹配的规则，该算法的技术特点是什

么？（9分）

4. 二叉树的中序与后序序列能唯一地定义一棵二叉树吗? 这里所指序列中的符号代素树结点中的标识

符吗？二叉村的前序与后序序列能唯一地定义一棵二叉树吗? 为什么?(8分)

5. 在什么情况下m 阶B 树(m>>2)比AVL 树有效? 分析其原因·(8分)

二、将n 个队列顺序映射到数组v[l···m]中，每一队列在v 中表示为一，循环队列。试画出其示意图并

写出对应这种表示的addq 和deleteq 过程。 (20分)

三、给出中序线索树的结点结构并画出一个具有头结点的中序线索树，使其树结点至少应有6个，写一算

法在不使用栈和递归的情况下前序遍历一中序线索树，并分析其时间复杂度，（20分）

四、证明：具有n 个点和多于n-1条边的无向连通图G 一定不是树（10分）

五、若S 是n 个元素的集合，则S 的幂集P(S)定义为S 所有子集的集合（15分）。

例如，S=(a,b,c),P(S)={() ,(a),(b),(c),(a,b),(a,c),(b,c),(a,b,c)}

给定S ，写一递归算法求P(S)。

1994年考研题

一、回答下列问题：（共32分）

1. 最近最少使用（Least-Recently-Used ） 页替换是虚拟存储系统中常用的策略。试说明如何利用一页

联接表时刻跟踪最近最少使用页？（8分）

2. 已知无向图G ，V （G ）={1，2，3，4}，E （G ）={（1，2），（1，3）（2，3）（2，4）（3，4）}试画

出G 的临接多表，并说明，若已知点I ，如何根据临接多表找到与I 相临的点j ？（8分）

3. 欲求前k 个最大元素，用什末分类方法好？为什末？什末是稳定分类？分别指出下列算法是否稳定

算法，或易于改成稳定分类算法？（8分）

（a ）插入分类 （b ）快速分类 （c ）合并分类 （d ）堆分类 （e ）基数分类

4. 构造最佳二叉树检琐树的前提条件是什末？在动态情况下，一般A VL 树的查询性能不如完全二叉检

索树的，为什末人们却采用A VL 树呢？（8分）

二、下列算法对一n 位二进制数加I ，假如无溢出，该算法的最坏时间复杂性是什末？并分析它的平均时

间复杂性。（15分）

type num=array [1。。n] of [0。。1]；

procedure lnc （var A：Num ）；

var i ：integer ；

begin i ：=n；

while a[i]=I do

a[i]：=0； i ：=i-1；

end ；

a[i]：=i；

end lnc ；

三、给定nxm 矩阵A[a。。b ，c 。。d]，并设A[i，j]〈=A[i，j+1]（a 〈=i〈=b，c 〈=j〈=d-1〉

已知A[i+1，j]（a 〈=i〈=b-1，c 〈=j〈=d〉。

设计一算法以比o （n ，m ）小的最坏时间复杂性判定值x 是否在A 中。（17分）

四、设图G 有n 个点，利用从某个源点到其余各点最短路径算法思想，设计一产生G 的最小生成树的算

法。（18分）

字符序列的子序列由删除该序列任意位置的任何元素而得。序列x 和y 的最长公共子序列，记为Lcs

（x ，y ），是x 和y 的公共子序列，且长度最大，

例如，adcbb 和 adbcb 是x=abdcbcbb和y=adacbcb的最长公共子序列，设x 长度为n ，y 长度为m ，

设计一算法计算x 和y 的最长公共子序列的长度，尽可能改进你的算法，使它的时间复杂性为

o （n 、m ）。（18分）

五、字符序列的子序列有删除该序列任意位置的任何个元素而得序列x 和y 得最长公共子序列，记为

lcs(x,y)，是x 和y 的公共子序列，且长度最大。例如，adcbb 和adbcb 是x=abdcbcdd和y=adacbcb的

最长公共子序列，设x 长度为n ，y 长度为m ，设计一算法计算x 和y 得最长公共子序列，尽可能改

进你的算法，是它的时间复杂性为O(n•m) 。 （18分）

1995年考研题

一、在磁带文件上进行二分文件查找行吗？为什么？（6分）

二、分析确定下列程序段中带底画线语句执行次数与n 所成数量基关系（即表示为o （f （n ））。

K ：=1；I ：=K；

While I〈n DO

Begin K：=K+1；I ：=I+K END；

三、外排序中为何采用k--路（k ）2）合并而不用2--路合并？这种技术用与内排序有用吗？为什么？

（8分）

四、索引顺序存取方法（ISAM ）中，主文件已按关键字排序，为何还需要主关键字索引？

五、满二叉检索树符合B 树定义吗？B 树的插入和删除算法适用于满二叉检索树吗？为何？

六、设无向图G 有n 个点e 条边，写一算法建立G 的邻接多表，要求该算法时间复杂性为o （n+e），且除

邻接多表本身所占空间之外只用o （i ）辅助空间。（16分）

七、写一改进的递归快速排序办法，要求对于n 个记录该算法的递归深度《=1+log2n，并说明你的算法满

足这一要求。（1 7分）

八、定义前序排列为1，2，、、、，n 的全部二叉树的中序排列集合为IP ；再定义将1，2，、、n 从右到左经过

一个栈可得到全部排列集合SP 。例如，当n=3，SP={1 2 3，1 3 2 ，2 1 3 ，2 3 1，3 2 1}问IP

是集合SP 的真子集成立否？证明你的结论。

九、设记录R[i]的关键字为R[i]。KEY （1《=i〈=K-1〉指向败者记录，T[O]为全胜记录下标。写一算法

产生对应上述R[i]（1〈=i〈=k〉的败者树，要求除R[1、、k]和T[0、、k-1]以外，只用O （1）辅助

空间。（15分）

东南大学

1996年考研题

一、回答下列问题：

1. 线性表（a1，a2，、、、、、、，an ）用顺序映射表示时，ai 和ai+1（1〈=i〈n 〉的物理位置相临吗？链接表示时呢？（5分）

2. 一棵前序序列为1，2，3，4，的二叉树，其中序序列可能是4，1，2，3吗？设一棵二叉树的前序序列为1，2，3，4，5，6，7，8，9，其中序序列为2，3，1，5，4，7，8，6，9，试画出该二叉树。（7分）

3. 在模试匹配KMP 算法中缩用失败函数f 的定义中，为何要求p1p2、、、、pf （i ）为p1p2、、、、pj 两头匹配的真子串？且为最大真子串？

4. 在union-find 问题中，控制union 操作的权重规则是何含义，有何效果？控制 find操作的倒塌规则是何含义？有何效果？

5. 堆排序是稳定排序吗？举例说明（6分）

6. 给定输入文件：101，48，19，65，3，74，33，17，21，20，99，53，21，并设记录缓冲区个数k=4，写出基于败者树的外排序顺串生成算法runs 输出的顺串。（6分）

7.m 阶B 树中，m 的大小的确定于何因素有关？（8分）

data Link

二、设结点结构为上图:试用一个全局指针p 和某种超级链接结构实现一个队列, 画出示意图, 并给出入队和出队过程, 要求他们的时 间复杂性是O(l)(10分)

三、设有向G 图有n 个点(用1,2, ……表示),e 条边, 写一算法根据其邻接表生成其反向邻接表, 要其算法复杂性为O(n+e).(13分)

四、设二叉树结点结构为: left Data bf Right

定义二叉树结点T 的平衡因子bf(T)=hl-hr,写一递归算法确定二叉树中各结点的平衡因子bf, 同时返回二叉树中非叶结点个数. (15分)

五、设符号表中的标示符满足:1

东南大学

1997年考研题

一、简要回答下列问题：（共32分）

⒈在表达式中，有的运算符要求从左到右计算，如A**B**C的计算次序应为（A**(B**C)）, 这在由中缀生成后缀的算法中是怎样实现的？ （8分）

⒉给出KMP 算法中失败函数f 的定义，并说明利用函数f 进行串模式匹配的规则，该算法的技术特点是什么？（8分）

⒊Fibouacci 查找算法（fibsrch ）中为什么要求m

⒋为什么在倒排文件(inverted files)组织中，实际记录中的关键字域(key fields)可删除以节约空间？而在多表(multilists)结构中这样做为什么要牺牲性能？ （8分）

二、试写一个算法，建立无向图G 的邻接多表（adjacencyb multilists）, 要求说明算法中主要数据结构和变量的意义。（15分）

三、给出中序线索数的结点结构并画出一个具有头结点的中序线索数， 使其数结点至少应有6个。写一算法在不使用栈和递归的情况下前序遍历一中序线索树，并分析其时间复杂性。 （18分）

四、若S 是n 个元素的集合，则S 的幂集P(s)定义为S 所有子集的集合。例如，

S=(a,b,c),P(s)={( ),(a),(b),(c),(a,b),(b,c),(a,b,c)},给定S, 写一递归算法求P(s).(15分)

五、已知在llink-rlink 存储法表示的二叉数中，指针t 指向该二叉树的根结点，指针p,q 分别指向树中的二个结点。试写一算法，就距离这两个结点最近的公共的祖先结点。（20分）

东南大学

1998年考研题

一、简要回答下列问题。

1. 设胜者树由k 各记录缓冲区和k-1个非叶结点构成，概念上非叶结点表示两个子女中

观键字较小者，而实际上非叶结点存放的是什末？

2. 索引顺序存储方法中，主文件已按关键字排序，为何还需要主关键字索引？

3. 一棵前序序列为1，2，3，4的二叉树，其中序序列可能是4，1，2，3吗？设一棵二叉树的中序序列为1，2，3，4，5，6，7，8，9。其中序序列为2，3，1，5，4，7，8，6，9，试画出该树。

4. 构造最佳二叉检索树的条件是何？再动态情况下，一般 AVL 树的查询性能不如完全二叉检索树的，为何人却采用AVL 树呢？

5. 将两个栈存入数组V[1。。。m]应如何安排最好？这时栈空栈满的条件是何？

6. 已知无向图G ，V （G ）={1，2，3，4}，E （G ）={（1，2），（1，3）（2，3），（2，4），（3，4）}试画出G 的邻接多表，并说明，若已知点i ，与和根据邻接多表找到与i 相临的点j ？

二、写出用堆排序算法对文件F=（12，3，15，30，9，28）进行排序是，初始堆及以后每挑好一个元素重新调整后堆的状态，并指出这里的堆和败者树的一个重要区别。

三、设组A 存放一位二进制数，试说明下列算法X 的功能，假设无溢出，算法的X 最坏时间复杂性是何？分析她的平均时间复杂性。 （8分）

type Num-array[1..n] of [0..1];

procedure x (var a:num);

var i:integer;

begin

i:=n;

while A[i]=1 do

begin A[i]:=0; i:=i-1;

end; A[i]:=1;

end;

四、下面是一改进了的快速分类算法

1.procedure qsort1(var list:afile;m,n:integer);

2(设list[m].keky

3var i,j,k:integer;

4 begin

5 while m

6 begin

7 i:=m;j:=n+1; k:=list[m].key;

8 repeat

9 repeat i:=i+1 until list[i].key>=k;

10 repeat j:=j-1 until list[j].key

11 if i

12 until i>=j;

13 interchange( list[m],list[j]);

14 if n-j>=j-m

15 then begin qsort1(list.m.j+1);m:=j+1;end

16 else begin qsort1(list.j+1.n);n:=j-1;end

17 end;(of while)

18 end.

问： (共 20分)

1. 将第9.10行中的＞=，＜=分别改成＞＜行吗？为什么？ （5分）

2. 该排序算法稳定否，举例说明 （5分）

3. 对输入文件（22，3，30，4，60，11，58，18，40，16）列表表示该文件再每次调用qsort1时的状态及相应m 〈n 值 （5分）

4. 若输入文件有n 个记录，简要说明支持qsort1递归所需最大栈空间用量设一曾递归用一个单位栈空间）。（5分）

五、给定AOE 网络各事件的（标号1.. n）ee ，le 值和邻接表，写一算法求该AOE 的所有活动和关键度

（用相应边的两端点表示）的关键度（10分）

六、给出中序线索树的结点结构，并画出一个具有头结点和6各树结点的中序线索树的结构试写一算法

在不使用栈和递归情况下前序遍历一中序线索树，并分析它的时间复杂性

东南大学

1999年考研题

一、简要回答下列问题 （共40分）

1. 利用两个栈s1，s2模拟一个时，如何用栈的运算实现队列的插入删除及判队空算法。请简述算法思想。（7分）

2. 二叉树有n 个顶点，编号为1，2，3，、、、、、n 设：

*T中任一定点V 的编号等于左子树中最小编号减1；

*T中任一顶点V 的右子树中的最小编号等于其左子树中的最大编号加1；

试描绘该二叉树。（7分）

3. 设某文件经内排序后得到100个初始归并段，若使用多路归并排序算法，并要求三趟归并完成排序，归并路数最少为多少？ （5分）

4. 若一棵树中有度数为1至m 的各种结点数分别为n1，n2、、、、nm （nm 表示度数n 为的结点个数，试推导出该树中共有多少个叶结点n0的公式。 （8分）

5. 试举例分析堆排序法是否稳定 （5分）

6. 试利用KMP 算法和改进算法分别求p1=‘abaabaa ’和p2=‘aabbaab ’的NEXT 函数和NEXTVAL 函数。

（ 8分）

二、阅读下列算法，指出算法的功能和时间复杂性（10分）

procedure A(h,g:pointer);

(h,g分别为单循还列表中两个结点指针)

procedure B(s,q:pointer)

var p:pointer;

begin

p:=s;

while p^.nextq do p:=p^.next;

p^.next:=s;

end;

begin

B(h,g); B(g,h);

End;

三、已知无向图采用邻接表存储方式，试写出删除边（ i，j ）的算法。 （10分）

四、线性表中有个n 元素，每个元素是一个字符，存在向量R[1。。。n]中，试一写算法，使其中的字符按字母字符，数字字符和其字符的顺序排列，要求利用原空间。且元素移动的次数最少。（15分）

五、四阶B 树中（如图所述），插入关键字87，试画出插入调整 后树的形状

六、试编写一算法对二叉树按前序线索化 （15分）

东南大学2000年考研题

一、简要回答下列问题（共40分）

1. 假设一棵二叉树的层序序列是ABCDEFGHIJ 和中序序列是DBGEHJACIF ，请画出该树。

2. 简单比较文件的多重表和倒排表组织方式各自特点。

3. 画出对算术表达式A-B*C/D-E↑F 求值时操作数栈和运算符栈的变化过程。

4. 找出所有满足下列条件的二叉树：

（1）它们在先序遍历和中序遍历时，得到的结点访问序列相同；

（2）它们在后序遍历和中序遍历时，得到的结点访问序列相同；

（3）它们在先序遍历和后序遍历时，得到的结点访问序列相同；

5. 对一个由n 个关键字不同的记录构成的序列，能否用比2n-3少的次数选出该序列中关键字取最大值和关键字取最小值的记录？请说明如何实现？在最坏的情况下至少进行多少次比较？

6. 已知某文件经过置换选择排序后，得到长度分别为47，9，31，18，4，12，23，7的8个初始归并段。试为3路平衡归并设计读写外存次数最少的归并方案，并求出读写外存的次数。

二、已知L 是无表头结点的单链表，其中P 结点既不是首元结点，也不是尾元结点

1. 在P 结点后插入S 结点的语句序列是___________________

2. 在P 结点前插入S 结点的语句序列是_____________________

3. 在表首插入S 结点的语句序列是_____________________

4. 在表尾插入S 结点的语句序列是_____________________

⑴P^.next:=S;

⑵P^.next:=P^.next^.next;

⑶P^.next:=S^.next;

⑷S^.next:=P^.next;

⑸S^.next:=L;

⑹S^.next:=NIL;

⑺Q:=P;

⑻WHILE P^.nextQ DO P:=P^.next

⑼WHILE P^.nextNIL DO P:=P^.next;

⑽P:=Q;

⑾P:=L;

⑿L:=S;

⒀L:=P;

三、设计一个符号表的表示方法, 编写算法使得在该表中进行查询, 插入和删除任何一个标志符X 的操作在O(1)的时间内. 假设1

四、试利用

，写出执行算法过程中各步的状态。

五、以顺序存储结构表示串，设计算法。求串S 中出现的第一个最长重复子串及其位置并分析算法的时间复杂度。

六、写出按后序序列遍历中序线索树的算法。

东南大学

2001年考研题

一、简要回答下列问题

1. 判断下列问题是否正确：

（1) 在动态存储管理系统中作空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。

（2) 从逻辑结构上看，N 维数组的每个元素均属于N 个向量。

（3) 无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。

（4) 用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。

（5) 带权的连通无向图的最小代价生成树是唯一的。

（6) 中序遍历一棵平衡的二叉排序树，可得到排好序的关键码序列。

（7) 树与二叉树是两种不同的树型结构。

（8) 完全二叉树中，若一个结点没有左孩子则它必是树叶。

（9) 快速排序总比简单排序快。

（10) 对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方

法。

2. 为什么文件的倒排表比多重表组织方式节省空间？（6分）

3. 设胜者树由K 个记录缓冲区和K-1个非叶子结点组成组成。概念上非叶子结点表示其两个子女中关键字较小者，而实际上非叶子结点中存放的是什么？（6分）图

4. 在求每两个顶点间的最短路径的ALLCOSTS （FLOYD ）算法中有什么要求？为什么？ （6分）

5. 证明具有N0 个叶结点的哈夫曼树共有2N0个结点（6分）

6. 给出（KMP ）算法中失败函数F 的定义，并说明利用T 进行模式匹配的规则及该算法的技术特点。（6分）

二、假设在A VL 树L 的每个结点中有一个域lside 。任意结点a ，a^.lise 表示该结点的左子树中结点的个数试编写程序avlfind （f ，k ）找到第K 个追小的标志符。（该树L 中有N 个结点，要求所花费的时间是O （logn ））（10分）

三、设整数x1，x2，…，xn 已存放在数组A 中，试编写递归程序，输出从这n 个数中取出所有k 个数的所有组合（k

例如：A 中存放的数是1，2，3，4，5，k=3，则输出结果为：

543，542，541，532，531，432，431，421，321

四、已知有向图和图中的两个结点u 和v ，试编写算法求有向图中从u 到v 的所有简单路径。（15分）

五、下面是一改进了的快速排序算法，请填空并简要说明支持improveqsort 递归所需要的最大栈空间用量。（10分）

procedure inproveqsort(var list:afile;m,n:integer);

{设list[m].key

var i,j,k:integer;

begin

while m

begin

i:=m; j:=n+1; k:=list[m].key;

repeat

repeat i:=i+1 until list[i].key>=k;

repeat j:=j+1 until list[j].key

if i

until i>=j;

interchange(list[m],list[j]);

if n-j>=j-m

then begin

improveqsort(list,______________);

_____________________________;

end

else begin

improveqsort(list,_______________);

______________________________;

end

end; {of while};

end;

六、给定n ╳m 矩阵A[a..b,c..d],

并设 A[i,j] ≤A[i,j+1](a≤i ≤b,c ≤j ≤d-1)

和 A[i,j] ≤A[i+1,j](a≤i ≤b-1,c ≤j ≤d).

设计一算法判定X 的值是否在A 中, 要求时间复杂度为O(m+n).(13分)

东南大学

2002年考研题

一、简要回答下列问题：（30）

1. 一棵二叉树的先序、中序和后序序列如下：其中一部分为标出，请构造出该二叉树

先序： CDE GHI K

中序：CB FA JKIG

后序： EFDB JIH A

2. 将下面数据表建成一个堆（70，12，20，31，1，5，44，66，61，200，30，80，1 50，4，28）

3. 试写出取出广义表A=（（a,x,y,z ）,(b,c)）中的c 的复合函数

4. 设目标串为S="abcaabbabcabaacbacba"，模式为P="abcabaa"，手工计算P 的nextva l值，并写出利用nextval 值按KMP 算法对目标S 进行模式匹配的过程

5. 已知下面二叉排序树各结点值依次为1-9，请标出各结点的值。

二、设有3阶B-树，如图所示，分别画出插入关键字20后和删除关键字150后得到的B-树（10）

三、已知二叉树采用二叉链表存储，设计算法以输出二叉树T 中根结点到每个叶子结点的路径（10）

四、试写一个判定所给二叉树是否为二叉排序树的算法。设此二叉树采用二叉链表存储，且树中结点的关键字均不同（10）

五、已知数组A[1..n]中元素类型为integer ，设计算法将其调整为左右两部分，左边所有为奇数，右边所有为偶数，并要求算法的时间复杂度为O(n)(10)

六、设计算法求距离顶点V0的最短路径长度（以弧度为单位）为K 的所有顶点，要求尽可能节省时间（10）