东南大学93考研题
（1） 答卷上需写清题号，不必抄题
（2） 描述可用你熟悉的一种类高级语言，如类Pascal，所用主要数据结构及变量的意义须加以注释。必要时算法中应加注释 。
一、回答下列问题 : (共 35分)
l与链式结构相比，线性表的顺序存贮的一个主要优点和一个主要缺点分别是什么 ? (4分)
2在表达式中，有的运算符要求从右到左计算，如A**B**C的计算次序应为(A**(B**C))，这在由中缀生成后缀的算法中是怎样实现的?(以**为例说明 ) (6分)
3.给出KMP算法中失败函数f的定义，并说明利用f进行串模式匹配的规则，该算法的技术特点是什么？（9分）
4二叉树的中序与后序序列能唯一地定义一棵二叉树吗?这里所指序列中的符号代素树结点中的标识符吗？二叉村的前序与后序序列能唯一地定义一棵二叉树吗?为什么?(8分)
5在什么情况下m阶B树(m>>2)比AVL树有效?
分析
定性数据统计分析pdf销售业绩分析模板建筑结构震害分析销售进度分析表京东商城竞争战略分析
其原因·(8分)
二。将n个队列顺序映射到数组v[l···m]中，每一队列在v中表示为一，循环队列。试画出其示意图并写出对应这种表示的addq和deleteq过程。 (20分)
三、给出中序线索树的结点结构并画出一个具有头结点的中序线索树，使其树结点至少应有6个，写一算法在不使用栈和递归的情况下前序遍历一中序线索树，并分析其时间复杂度，（20分）
四、证明：具有n个点和多于n-1条边的无向连通图G一定不是树（10分）
五、若S是n个元素的集合，则S的幂集P(S)定义为S所有子集的集合。例如，S=(a,b,c),P(S)={() ,(a),(b),(c),(a,b),(a,c),(b,c),(a,b,c)}给定S，写一递归算法求P(S)。（15分）
东南大学一九九四年攻读硕士学位研究生入学考试试题
一: 回答下列问题(共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的邻接多表(Adjacency Multilists),并说明,若已知点i,如何根据邻接多表找到与i相邻的点j?(8分)
3.欲求前k个最大元素,用什么分类(sorting)方法好?为什么?什么是稳定分类?分别指出下列算法是否稳定分类算法,或易于改成稳定分类算法?(a) 插入分类 (b) 快速分类 (c) 合并分类 (d) 堆(heap)分类 (e) 基数分类(radix sort) (8分)
4.构造最佳二叉检索树的前提条件是什么?在动态情况下,一般AVL树的查询性能不如完全二叉检索树的,为什么人们却采用AVL树呢?(8
二:下列算法对一n位二进制数加1,假设无溢出,该算法的最坏时间复杂度是什么?并分析它的平均时间复杂性.(15分)
type Num=array[1..n] of [0..1];
procedure Inc(var A:Num);
var j: integer;
begin i:=n;
while A[i]=1 do
A[i]:=0;i:=i-1;
end;
A[i]:=1;
end Inc;
三:给定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),设计一算法以比O(n*m)小的时间复杂度判定值x是否在A中.(17分)
四:设图G有n个点,利用从某个源点到其余各点最短路径算法思想,设计一产生G的最小生成树的算法.(18分)
五:字符序列的子序列由删除该序列任意位置的任意个元素而得.序列x和y的最长公共子序列记为Lcs(x,y),是x和y的公共子序列,且长度最大.例如,adcbcb是x=abdcbcbb和y=adacbcb的最长公共子序列.设x长度为n,y长度为m,设计一算法计算x和y的最长公共子序列的长度,尽可能改进你的算法,使它的时间复杂性为O(n*m).(18分)
东南大学一九九五年攻读硕士学位研究生入学考试试题
1. 在磁带文件上进行二分查找行吗?为什么?(6分)
2.分析确定下列程序中语句k:=k+1执行次数与n所成的数量级关系(即表示为O(f(n))的形式).(6分)
k:=1; i:=k;
while i
=k;
10 repeat j:=j-1 until list[j].key<=k;
11 if 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的所有活动(用相应边的两端点表示)的关键度(criticality).(10分)
六:给出中序线索树的结点结构,并画出一个具有头结点和六个树结点的中序线索树,试写一算法在不使用栈和递归的情况下前序遍历一中序线索树,并分析它的时间复杂性.(18分)
东南大学一九九九年攻读硕士学位研究生入学考试试题
一:简要回答下列问题(共40分)
1.利用两个栈s1,s2模拟一个队列时,如何用栈的运算实现队列的插入,删除以及判队空运算.请简述算法思想.(7分)
2.二叉树有n个顶点,编号为1,2,3,……n,设:
T中任一顶点V的编号等于左子树中最小编号减一;
T中任一顶点V的右子树中最小编号等于其左子树中最大编号加一;
试描绘该二叉树.(7分)
3.设某文件经内排序后得到100个初始归并段(初始顺串),若使用多路归并排序算法,并要求三趟归并完成排序,归并路数最少为多少?(5
4.若一棵树中有度数为1至m的各种结点数分别为n1,n2,...nm(nm表示度数为m的结点个数),请推导出该树中共有多少个叶结点n0的公式.(8分)
5.试举例分析,堆排序法是否稳定.(5分)
6.试利用KMP算法和改进算法分别求p1='abcabaa'和p2='aabbaab'的NEXT函数和NEXTVAL函数.(8分)
二:
阅读下列算法,指出算法A的功能和时间复杂性.(10分)
procedure A(h,g: pointer);
(h,g分别为单循环链表(single linked circular list)中两个结点指针)
procedure B(s,q: pointer);
var p: pointer;
begin
p:=s;
while p^.next<>q do p:=p^.next;
p^.next:=s;
end; (of B)
begin
B(h,g);B(g,h);
end; (of A)
三:已知无向图采用邻接表存储方式,试写出删除边(i,j)的算法.(10分)
四:线性表中有n个元素,每个元素是一个字符,存在向量R[1..n]中,试写一个算法,使R中的字符按字母字符,数字字符和其它字符的顺序排列.要求利用原空间,且元素移动次数最少.(15分)
五: 四阶B树中(如图所示),插入关键字87,试画出插入调整后树的形状.(10分)
|30 60 80|
/ / \ \
|20 25| |35 50| |60 70 75| |82 85 90|
六:试编写一算法对二叉树按前序线索化.(15分)
东南大学二○○○年攻读硕士学位研究生入学考试试题
一:简要回答下列问题(共40分)
1.假设一棵二叉树的层序序列是ABCDEFGHIJ和中序序列是DBGEHJACIF,请画出该树.(6分)
2.简单比较文件的多重表和倒排表组织方式各自的特点.(6分)
3.画出对算术表达式A-B*C/D+E^F求值时操作数栈和运算符栈的变化过程.(6分)
4.找出所有满足下列条件的二叉树6分)
a)它们在先序遍历和中序遍历时,得到的结点访问序列相同;
b)它们在后序遍历和中序遍历时,得到的结点访问序列相同;
c)它们在先序遍历和后序遍历时,得到的结点访问序列相同.
5.对一个由n个关键字不同的记录构成的序列,能否用比2n-3少的次数选出该序列中关键字取最大值和关键字取最小值的记录?请说明如何实现?在最坏情况下至少进行多少次比较?(8分)
6.已知某文件经过置换选择排序后,得到长度分别为47,9,31,18,4,12,23,7的8个初始归并段.试为3路平衡归并设计读写外存次数最少的归并方案,并求出读写外存的次数.(8分)
二:已知L是无表头结点的单链表,其中P结点既不是首元结点,也不是尾元结点,(10分)
a)在P结点后插入S结点的语句序列是______
b)在P结点前插入S结点的语句序列是______
c)在表首插入S结点的语句序列是______
d)在表尾插入S结点的语句序列是______
(1) P^.next:=S;
(2) P^.next:=P^.next^.next;
(3) P^.next:=S^.next;
(4) S^.next:=P^.next;
(5) S^.next:=L;
(6) S^.next:=NIL;
(7) Q:=P;
(8) WHILE P^.next<>Q DO P:=P^.next;
(9) WHILE P^.next<>NIL DO P:=P^.next;
(10) P:=Q;
(11) P:=L;
(12) L:=S;
(13) L:=P;
三:设计一个符号表的表示方法,编写算法使得在该表中进行查询,插入和删除任何一个标识符X的操作在O(1)的时间内.假设1<=x<=m,n为要插入的个数,所需空间为m+n.(10分)
四:试利用Dijkstra算法求下图中从顶点a到其它各顶点的最短路径,写出执行算法过程中各步的状态.(10分)
____________
/ 4 \
↓ 6 \
b------→e___9 \
15↑ ↑ \ /
/ 2 /8 ↓/
a------→c g (和严蔚敏习题集上题目相同)
\ \4 ↑↑
12↓ 5 ↓ 10/ /
d←------f__/ /
\___________/
3
五:以顺序存储结构表示串,设计算法,求串S中出现的第一个最长重复子串及其位置并分析算法的时间复杂度.(15分)
六:写出按后序序列遍历中序线索树的算法.(15分)
东南大学二○○一年的题目:
一:（共40分）
1．判断下列叙述是否正确：（10分）
①在动态存储管理系统中做空间分配时，最佳适配法与最先适配法相比，前者容易增加闲置空间的碎片。
②从逻辑结构上看，n维数组的每个元素均属于n个向量。
③无向图的邻接矩阵一定是对称矩阵，有向图的邻接矩阵一定是非对称矩阵。
④用邻接矩阵法存储一个图所需的存储单元数目与图的边数有关。
⑤带权的连通无向图的最小代价生成树是唯一的。
⑥中序遍历一棵平衡的二叉排序树，可得到排好序的关键码序列。
⑦树与二叉树是两类不同的树型结构。
⑧完全二叉树中，若一个结点没有左孩了，则它必是树叶。
⑨快速排序总比简单排序快。
⑩对处理大量数据的外存介质而言，索引顺序存取方法（ISAM）是一种方便的文件组织方法。
2．为什么文件的倒排表比多重表组织方式节省空间。（6分）
3.设胜者树(selection tree)由k个记录缓冲区和k-1个非叶结点构成.概念上非叶结点表示其两个子女中关键字较小者,而实际上非叶结点存放的是什么? （6分）
4.给出KMP算法中失败函数f的定义,并说明利用f进行串模式匹配的规则,该算法的技术特点是什么? （6分）
5.是一道关于Huffman树中叶子结点和非叶结点数量关系的计算题,具体题目记不得了. （6分）
6.求有向图中任意一对顶点之间最短路径的弗洛伊德算法(allcosts-Floyd)中,要求有向图满足什么前提条件? （6分）
二:在二叉树的结点结构中增加一个域:leftsize,t^.leftsize表示t结点的左子树中结点的总个数,试编写算法alloc(k),在二叉树中查找中序序号为k的结点,要求时间复杂度为O(log2(n)). （10分）
三:编写算法输出从n个自然数中取k个(k<=n)的所有组合.例如,当n=5,k=3时,你的算法应该输出:543,542,541,532,531,521,432,431,421,321. （12分）
四:设有向图G用邻接表的方式存储,u,v是G中的任意两个结点,写一算法,求出G中从u到v的所有简单路径. （15分）
五:下面是一改进了的快速排序算法,试补充其中的空白语句,并分析该算法所需的最大递归空间是多少? （10分）
procedure qsort1(var list:afile;m,n:integer);
(设list[m].key=k;
repeat j:=j-1 until list[j].key<=k;
if i=j;
interchange(list[m],list[j]);
if n-j>=j-m
then begin qsort1(list,m,___);______;end
else begin qsort1(list,___,n);______;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),设计一算法以O(n+m)的时间复杂度判定值x是否在A中. （13分）
东南大学2002年数据结构考研试题
1、 判断下列叙述是否正确：(10分)
1、 设指针P指向单链表中的一个结点，则语句序列U:=P.next; U:=U.next 将删除一个结点。
2、 栈和队列都是运算受限的线性表。
3、 广义表的长度是广义表中的原子个数。
4、 若某二叉树的叶子结点数为1，则其先序序列和后序序列一定相反。
5、 二叉树在按任一种次序线索化后，都很容易地求出相应地次序下地前驱和后继。
6、 在采用线性探测法处理冲突地散列表中，所有同义词在表中相邻。
7、 对B树中任一非叶子结点中的某关键字K，比K小的最大关键字和比K大的最小关键字一定都在叶子结点中。
8、 在数据表基本有序时，冒泡排序算法的时间复杂度一定接近O（n）。
9、 若从某顶点开始对有向图G进行深度遍历，所得的遍历序列唯一，则可断定其弧度数为n－1。
10、AOE网所表示的工程至少所需的时间等于从源点到汇点的最短路径的长度。
2、 选择题：（10分）
1、 一个栈的输入序列为12345，则不可能的栈的输出序列的是（）
（1）12345
（2）54321
（3）23451
（4）41235
2、一棵左子树为空的二叉树在先序线索化后，其中的空链域的个数为（）
（1）0
（2）1
（3）2
（4）不确定
3、在用邻接表表示图的情况下，拓扑排序算法的时间复杂度为（）
（1）O（n＋e）
（2）O（n2）
（3）O（n*e）
（4）O（n3）
4、下列排序算法中，在每一趟都能选出一个元素放在其最终位置上，并且其时间性能受数据初始特性影响的是（）
（1）直接插入排序
（2）快速排序
（3）直接选择排序
（4）堆排序
5、下列排序算法中，依次将待排序序列中的元素和前面有序序列合并为一个新的有序序列的排序算法是（）
（1）冒泡排序
（2）直接插入排序
（3）直接选择排序
（4）快速排序
三、简要回答下列问题：（30）
1． 一棵二叉树的先序、中序和后序序列如下：其中一部分为标出，请构造出该二叉树(6分)
先序： CDE GHI K
中序：CB FA JKIG
后序： EFDB JIH A
2． 将下面数据表建成一个堆（70，12，20，31，1，5，44，66，61，200，30，80，150，4，28）(6分)
3． 试写出取出广义表A=（（a,x,y,z）,(b,c)）中的c的复合函数(6分)
4． 设目标串为S="abcaabbabcabaacbacba"，模式为P="abcabaa"，手工计算P的nextval值，并写出利用nextval值按KMP算法对目标S进行模式匹配的过程(6分)
5． 已知下面二叉排序树各结点值依次为1-9，请标出各结点的值。(6分)
四、设有3阶B-树，如图所示，分别画出插入关键字20后和删除关键字150后得到的B-树
（10）
五、已知二叉树采用二叉链表存储，设计算法以输出二叉树T中根结点到每个叶子结点的路径（10）
六、试写一个判定所给二叉树是否为二叉排序树的算法。设此二叉树采用二叉链表存储，且树中结点的关键字均不同（10）
七、已知数组A[1..n]中元素类型为integer，设计算法将其调整为左右两部分，左边所有为奇数，右边所有为偶数，并要求算法的时间复杂度为O(n)(10)
八、设计算法求距离顶点V0的最短路径长度（以弧度为单位）为K的所有顶点，要求尽可能节省时间（10）
东南大学2003年数据结构考研试题
一、试用面向对象编程语言（C++或Java）描述单链表类（class List）中的插入和删除操作。（8分）
二、将算术表达式((a+b)+c*(d+e)+f)*(g+h)转化为二叉树。（7分）
三、给出一组关键字Ｔ＝（12，2，16，30，8，28，4，10，20，6，18），写出用下列 算法从小到大排序时第一趟结束时的序列：
（1）希尔排序（第一趟排序的增量为5）（5分） （2）链接基数排序（基数为10）（5分）
四、 在二叉树中查找值为X的结点，试编写算法，打印值为X的结点的所有祖先，假定值为X的结点不多于１个，最后，试分析该算法的时间复杂性。（10分）
五、 从根到叶子的最大距离称为树的半径（radius）。给定一个无向连通图，写一个算法以找出半径最小的生成树。(10分)
东南大学2004年数据结构考研试题
1、 简要回答下列问题（共10分，每题5分）
1、 一棵完全二叉数有500个结点，请问该完全二叉树有多少个叶子结点？有多少个度为1的结点？有多少个度为2的结点？如果完全二叉数有501个结点，结果如何？请写出推导过程。
2、 设模式串为P＝“bookboxlookbood”，手工计算P的失效函数f（j）的值。
2、 外存储索引为什么采用m阶B树（m>>2），而不用AVL树？满二叉检索树符合B树的定义吗？B_树的插入和删除算法适用于满二叉检索树吗？为什么？（5分）
设有3阶B_树，如图所示，分别算出插入关键字20后所得到的B_树，以及在此基础上删除关键字150后得到的B_树。（5分）
3、 设散列表的长度为9（HT[0..8]），散列函数H（x）＝└i/3┘，其中i为键值x中第一个字母在字母表中序号（A，B，C，D，……，Y，Z的序号为1，2，3，4，……25，26），其键值的输入顺序Jan，Feb，Mar，Apr，Jun，Jul，Aug，Sep，Oct，Nov，Dec，用拉链法（链接法）处理冲突，要求：
（1） 构造散列表（5分）
（2） 求出在等概率情况下，查找成功时的平均查找长度。（5分）
4、 已知存储于数组S中长度为n的字符串中含有字母字符、数字字符和空格字符，请使用一种排序方法将所有字母字符移到字符串的前部，将所有空格字符移到字符串的后部。试写出此算法。要求利用字符串的原有空间以及最少的时间代价。（10分）
5、 设计算法求中序线索二叉树中指针P所指结点的前驱结点的指针。（10分）
东南大学2005年数据结构考研试题
一、简要回答下列问题（10分）
①含9个叶子结点的3阶B—树中至少有多少个非叶子结点？
含10个叶子结点的3阶B—树中至多有多少个非叶子结点？
②设目标串为S=“abcaabbabcabaacbacba”，模式为P=“abcabaa”,手工计算P的失败（失效）函数f(j), 并写出利用f(j)值按KMP算法对目标S进行模式匹配的过程。
二、给定输入文件的关键字为（4，6，2，15，9，20，30，5，35，1，7，3，50，10，40）。设K=4，列出用置换-选择算法求初始归并段（顺串）的结果以及主要过程。（10分）
left
data
bf
right
三、设二叉树结点结构为：
定义二叉树结点的平衡因子bf（T）= hL-hR ，写一递归算法；
确定二叉树tree中各结点的平衡因子bf ，同时返回二叉树tree中非叶子结点的个数。（10分）
四、给定nxm矩阵A[a..b, c..d]，并设A[i，j]≤A[i, j +1] (a≤i≤b，c≤j≤d-1）和A[i, j] ≤Aij +1, j] (a≤i≤b-1，c≤j≤d)。设计算法判断X的值是否在A中，要求时间为O(m+n)。(10分)
五、设计算法求距离顶点VO的最短路径长度（以弧数为单位）为K的所有顶点，要求尽可能节省时间。（10分）
180
120�
90
60 70
30 40
150
50 80
100
150
180
120
90
60 70
30 40
50
180
120
90
60 70
30 40
150
50
100
浙公网安备 33021202002483