晕 有题无图 图怎么不能复制啊！~~~
想看的还是上
WWW.TOPKAOYAN.NET去看看吧 有些
试题是图片形式的 无法复制啊！~~~~
1992- 2003的都有~~~~
下面仅仅帖几个题 但是没有图还是看不好的！！~~~
北京邮电大学2003年
数据结构考研试题
WWW.TOPKAOYAN.NET作者:[Admin] 来自:[TOP真题库] 文章类型:[北京邮电大学] 时间:[2005年10月30日16:35]
北京邮电大学2003年硕士研究生入学考试试题
一、 填空（20分，每空2分）:
1、5 个圆盘的Hanoi 塔，次小圆盘移到位时的步骤是第( )步；
A. 16 B. 30 C. 31 D. 32
2、中缀表达式A*（B+C）/（D-E+F）的后缀表达式是( ) ；
A. A*B+C/D-E+F B. AB*C+D/E-F+
C. ABC+*DE-+/ D . ABCDEF*+/-+
3、广义表G=（a,b,(c,d,(e,f)),G）的长度为( ) ；
A. 3 B. 4 C. 7 D. ∞
4、对于有n个顶点e条边的连通图，其生成子图顶点和边的最小数目分别为_______ 和_________;
A. 0 B. n C. n-1 D. e
5、含有4个元素值均不相同的结点的二叉排序树有_______ 种；
A. 4 B. 6 C. 10 D. 14
6、有345个元素的有序表，等概率顺序查找成功的平均查找长度为________；
A. 86 B. 172 C. 173 D. 345
7、一棵m阶非空B-树，每个结点最多有________棵子树；除根结点外，所有非终端结点最少有__________棵子树；
A.┌m/2┐ B. m-1 C. m D. m +1
8、就平均时间而言，下列排序方法中_________最好。
A. 直接插入排序 B. 快速排序 C. 堆排序 D. 归并排序
二、 判断对错（10分，每题1分）:
1、 数据的逻辑结构与数据元素本身的形式和内容无关；
2、 线性表的逻辑顺序总与其
物理顺序一致；
3、 字符串‘ababaab’的改进的失败函数nextval的值是‘0101011’；
4、 （10，21，43，39，22，45，48，201，49,46，99）是堆；
5、 任何一个关键活动提前完成，则整个工程也会提前完成；
6、 霍夫曼树的所有子树也均是霍夫曼树；
7、 平衡二叉树（AVL树）的中序遍历值是递增的；
8、 折半查找适用于所有的有序表；
9、 理想情况下散列表等概率查找成功的平均查找长度是O（1）；
10、 求n个数中最大的k（k<<n）个数，起泡排序比直接选择排序要好。
三、 以下表顺序建立平衡二叉排序树，并求在等概率情况下查找成功的平均查找长度。（10分）
(90,60,20,50,40,30,10,110,100,70,120,80)
四、 用迪杰斯特拉（Dijkstra）算法求下图中V1顶点到其它各顶点的最短距离和最短路径，请写出求解过程。（5分）
五、 算法（30分，每题10分）:
1、 现有算法如下，求给定输入时的输出:
TYPE list=↑node;
node=Record
data :integer;
next:list
End;
PROC RDWRT;
H:=nil; Read(a);
While a>0 Do
Begin
New(P);
P↑.data:=a;
P↑.next:=H;
H:=P;
Read(a)
End;
Q:= P↑.next;
While Q≠nil Do
Begin
R:=Q↑.next;
IF R≠nil Then
Begin
Q↑.next:= R↑.next;
R↑.next:=Q;
P↑.next:=R;
P:=Q;
Q:= P↑.next;
End Else Q:=nil
End;
P:=H;
While P≠nil Do
Begin
Write(P↑.data,’ ’);
P:=P↑.next
End
Endp;
输入为:1 2 3 4 5 6 7 8 9 10 0
2、已知以二叉链表表示的二叉树中有值为e、e1、e2的三个结点，下面的算法是判断e是否为e1和e2的共同祖先，请在空格处填上相应的语句或表达式。
TYPE biptr=↑node;
node=Record
data :datatype;
lc，rc:biptr
End;
FUNC Forefather(t:biptr: e,e1,e2:integer):boolean;
f:=p1:=p2:=nil;
End
ENDP;
3、求以二叉链表表示的二叉树中叶子结点的个数，在求值过程中，将树中所有结点的左右子树重新调换:结点值大的子树作为右子树，空结点值最小，试写出算法。
北京邮电大学2002考研题
注意事项:
1.答案一律写在答题纸上；
2.答案应字迹清楚语义贴切 ；
3 .算法应说明基本思路，应对主要数据类型, 变量出说明，所写算法应思路清晰简明易懂，应加必要注释。
4.算法可用pascal语言,c语言等你所熟悉的高级语言编写，但要注明语种。
一、 判断对错（10分，每题1分）
1. 数据的逻辑结构是数据的各数据项之间的逻辑关系；
2. 顺序存储方式插入和删除时效率太低，因此不如链式存储方式好；
3. 栈和队列都是线性表，只是在插入和删除时受到了一些限制；
4. KMP算法的特点是在模式匹配时指示主串的指针不会变小；
5. 二维以上的数组其实是一种特殊的广义表；
6. 二叉树是树的特殊情形；
7. 强连通分量是无向图的极大强连通子图；
8. 查找相同结点的效率折半查找]总比顺序查找高；
9. 归并排序在任何情况下都比所有简单排序速度快；
10. 直接访问文件也能顺序访问，只是一般效率不高。
二、 简答（10分，每题5分）
1. 现有12个初始归并段，其记录数分别为:{30，44，8，6，3，20，60，18，9，62，68，85}，现用3路平衡归并，画出最佳归并树；
2. 长度为12的表{Jan,Feb,Mar,Apr,May,Jun,Jul,Aug,Sep,Oxt,Nov,Dec}，按此顺序建立一阶B_树，画出此B_树;
三、 证明（10分）
对有向图的顶点适当的编号，可使其邻接矩阵为下三角形且组对角线为全0的充要条件使该图是无环图。
四、 应用（2分，每题10）
1. 已知一有向网的邻接矩阵如下，如需在其中一个结点建立娱乐中心，要求该结点距其它各结点的最长往返路程最短，相同条件下总的往返路程越短越好，问娱乐中心应选址何处？给出解题过程；
v1 0 2 ∞ ∞ ∞ 3
v2 ∞ 0 3 2 ∞ ∞
v3 4 ∞ 0 ∞ 4 ∞
v4 1 ∞ ∞ 0 1 ∞
v5 ∞ 1 ∞ ∞ 0 3
v6 ∞ ∞ 2 5 ∞ 0
2. 有一组关键字序列{15,92,124,5,27,28,18,6,36,34,30,26,32,259},将它们用散列函数H(key)=key mod 10 按顺序散列到哈希表HT(0:9)中，用链地址法解决冲突，画出最终的哈希表，并求在等概率情况下查找成功和不成功时的平均查找长度。
五、 算法（50分，前两题各10分，后两题各15分）
1. 现有算法及整数n和数组A如下，求数组C的值；
Var
A,B,C:Array[1..100] of integer;
FUNC AAA(s,t:integer):integer;
If s=t Then If B[s]=0 Then AAA:=r;Else AAA:=-s Else
Begin
L :=AAA(s,(s+t) Div 2);
R:=AAA((s+t) Div 2+1,t);
If i>0 Rhen AAA:=l Else AAA:=r;
If (r>0) And (A[l]>A[r]) Then AAA:=r
END
ENDF;
PROC BBB;
For I:=1 To n Do B
:=0;
For I:=1 To n Do B[AAA(1,n)]:=i;
For I:=1 To n Do C[B]:=A;
ENDP;
初始值:n=10,A={121,22,323,212,636,939,828,424,55,262};
2. 请在下面求拓扑排序算法中的空格处填上相应表达式，使算法完整:
FUNCTopoSirt(VAR G:Graph;n:integer):Boolean;
Cala(G);{计算各顶点入度}
Init(Q);{定义队列}
M:=0;
End
ENDP;
3. 若待排序列是由带头结点的双向链表存储，试给出对其进行简单选择排序的算法；
4. 若二叉树用以下存储结构表示，试给出求前序遍历的算法:
TYPE
Tree:=Array[1..max] of Record
Data:char;
Parent:integer;
End;
北邮2001年硕士研究生考试题(f)
二.填空（20分，每空2分）:
1.数据的逻辑结构是指:__________________；
2.区分循环队列的满与空，只有两种方法，它们是__________和___________;
3. 用一维数组B与列优先存放带状矩阵A中的非零元素A[i,j] (1≤i≤n,i-2≤j≤i+2),B中的第8个元素是A 中的第_____行，第_____列的元素。
4.字符串‘ababaaab’的nextval函数值为__________；
5.右图中的强连通分量的个数为___________个；
6.外部排序的基本方法是归并排序，但在之前必须先生成___________；
7.若不考虑基数排序，则在排序过程中，组要进行的两种基本操作是关键字的________和记录的_________；
三，简答（15分，每题5分）；
1， 特殊矩阵和系数矩阵哪一种压缩穿促后失去随机存取的功能？ 为什么？
2， 试问线索二叉树的目的何在？
3， 在多关键字排序时，LSD和MSD两种方法的特点是什么？
四,应用（25分，每题5分）；
1，画出按下表中元素的顺序构造的平衡二叉排序树，并求其在等概率的情况下查找成功下的平均查找长度。（15， 12 ，24， 3， 27， 21， 18， 6，36，33，30，26，32）；
2，假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成。它们在电文中出现的幅度分别为{0.31,0.16,0.10,0.08,0.11,,0.20,0.04},
(1),为这7个字母统计哈夫曼编码；
（2）为这7个字母进行等长编码，至少需要几位二进制数？哈夫曼编码比等长编码使电文总长压缩多少？
3，试推导出总盘数为n的Hanoi塔的移动次数。
4，一棵满k叉树，按层次遍历存储在一维数组中，试计算结点下标的u的结点的第一个孩子的下标以及结点为v的结点的父母结点的下标；
5，有一图的邻接矩阵如下，试给出用弗洛伊德算法求各
五，算法（30分，每题10分）；
1， 在单链表中，每个结点含有5 个正整型的 数据元素（最后一个结点的数据元素不满5个，以值0充），试编写一算法查找值为n（n>0）的数据元素所在的结点指针以及在该结点中的序号，落链表中不存在该数据元素则还回空指针；
2， 将一组数据元素按哈希函数H（key）散列到哈希表HT（0:m）中，用线形探测法处理冲突（H（key+1，H（key）+2…H（key）-1），假设空单元用EMPTY表示，删除操作是将哈希表中结点标志位从INUSE标记为DELETED，试写出该散列表的查找，INSERT，和删除三个基本操作算法；
3， 给出算法将二叉树表示的表达式二叉树按 中缀表达式输出，并加上相应的括号。
北京邮电大学2000考研题
注意事项:
1.答案一律写在答题纸上；
2.答案应字迹清楚语义贴切 ；
3 .算法应说明基本思路，应对主要数据类型, 变量出说明，所写算法应思路清晰简明易懂，应加必要注释。
4.算法可用pascal语言,c语言等你所熟悉的高级语言编写，但要注明语种
一、 判断对错（10分，每题1分）
1. 任何无向图都存在生成树。
2. 采用二叉链表作存储结构，树的前序遍历和其相应的二叉树的前序遍历的结果是一样的。
3. 强连通图的各顶点均可达。
4. 在任何情况下，归并排序都比简单插入排序快。
5. 在二叉树中插入结点，则此二叉树便不再是二叉树了。
6. 霍夫曼树的结点个数不能是偶数。
7. 抽象数据类型只是用来描述一些抽象的事。
8. 在伙伴系统中的伙伴是指任意两块大小相同、位置相邻的内存块。
9. 二叉树是一般树的特殊情形。
10. 文件系统采用索引结构是为了节省存储空间。
二、 选择填空（20分）
1. 栈和数组分别是线性表的_______和________结构。
A. 物理B.插入限制C.删除限制D.逻辑
2. M阶B-树是一棵________
A. m叉排序树B.m叉平衡排序树C.m-1平衡排序树D.m+1平衡排序树
3. 算法的计算量的大小称为计算的________。
A. 效率B.复杂性C.现实性D.难度
4. 设有两个串p和q，其中q是p的子串，求q在p中首次出现的位置的算法称为:_______
A. 求子串B.联接C.匹配D.求串长
5. 一个有n个结点的图，最少有_____个连通分量，最多有________个连通分量。
A.0 B.1 C.n-1 D.n
6. 在排序算法中每一项都与其它项进行比较，计算出小于该项的个数，已确定该项的位置叫:________
A. 插入排序B.枚举排序C.选择排序D.交换排序
7. 对图中每个结点都按以该结点为弧头的邻接点建立一个单链表的存储结构称为____
A. 邻接矩阵B.邻接表C.关联矩阵D.逆邻接矩阵
8. 顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用______的方法可降低所需的代价。
A. 附加文件B.按关键字大小排序C.按记录输入先后排序D.连续排序
三、 简要计算（10分）
1. 给出字符串‘abacabaaad’在KMP算法中的next和nextval数组。
2. banana H()—Head()、T()—Tail()从L中取出。
L=(apple,(orange,(strawberry,(banana)),peach),pear)
四、 有一组关键字（8，20，35，12，39，10，16，19，15），给出下面再等概率情况下查找成功的平均查找长度（10分）
1. 按顺序建立一棵二叉排序数，画出该二叉排序树；
2. 按顺序建立一棵平衡二叉排序数，画出该平衡二叉排序树。
五、 已知一图如右图所示（15分）
1. 写出该图的邻接矩阵；
2. 写出全部拓扑排序
3. 以v1为源点,以v8为终点，给出所有事件允许发生的最早时间和最晚时间，并给出关键路径；
4.求结点到各点的最短距离。
六、 优两个长度相同的栈S1,S2，已知以下入栈、出栈、判栈满和判栈空操作:
Procedure Push(Stack:Stacktype;x
atatype);
Function Pop(Stack:Stacktype )atatype;
Function Full (Stack:Stacktype):Boolean;
现用此二栈构成一个队列，试写出下面入队列、出队列操作算法:
Procedure EnQueue(xatatype);
Function DeQueue: Datatype;(10分)
七、 若待排序列用单链表存储，试给出其快速排序算法。（15分）
八、 已知二叉树的数据结构定义如下:
试给出在不使用堆栈（也不使用递归）、不需保留原树的情况下后序遍历一棵二叉树的算法（10分）
北京邮电大学1999年数据结构考研试题
WWW.TOPKAOYAN.NET作者:[Admin] 来自:[TOP真题库] 文章类型:[北京邮电大学] 时间:[2005年10月30日16:22]
北京邮电大学99考研题
注意事项:
1.答案一律写在答题纸上；
2.答案应字迹清楚语义贴切 ；
3 .算法应说明基本思路，应对主要数据类型, 变量出说明，所写算法应思路清晰简明易懂，应加必要注释。
4.算法可用pascal语言,c语言等你所熟悉的高级语言编写，但要注明语种。
一、选择填空。
1字符串‘ababaabab’ 的nextval 为（ ）；
a(0,1,0,1,04,1,0,1) b(0,1,01,0,2,1,0,1)
c(0,1,0,1,0,0,0,1,1) d (0,1,0,1,0,1,1,1 )
2广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（ ）；
head(tail(head(tail(tail(A)))))
a(g) b(d) c.c d.d
3输入序列为（A,B,C,D ）,则不可能得到的输出序列有（ ）；
a(A,B,C,D) b(D,C,B,A) c(A,C,D,B) d(C,A,D,B )
4散列函数有一个共同性质即函数值应按（ ） 取其值域的每一个值；
a 最大概率 b最小概率 c 同等概率 d 平均概率
5 直接插入序列在最好情况下时间复杂度为（ ）；
a O(logn) b O(n) c O(n*logn) d(n2)
二、判断是否正确。（10分）
1（101，88，46，70，34，45，58，66，10）是堆；
2 将一棵树转成二叉树，根结点没有左子树；
3 用树的前序遍历和中序遍历可以导出树的后序遍历；
4 即使不含相同元素的同一输入序列进行两组不同的合法的入栈和出栈组合操作，所得的输出序列也应一定相同；
5 哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
三、有一个高个比他人至少高一头，找他的人都说根本不用和别人比较，一眼就能看到他。你认为此话正确吗？为什么？请简要描述两种求个数中最大值的方法，并给出所须的最少比较次数。(10分)
四、下面是邻接表的存储图，画出此图，比写出从点c开始按优先深度遍历该图的结果。(10分)
五、下面是求无向连通图最小生成树的一种方法；
将图中所有有向边按权重从大到小排序为（e1,e2,……em）
i:=1
while (所剩边书 >=顶点树)
begin
从图中删去 ei
若图不再连通，则恢复ei
i:=i+1
end.
试证明这个算法生成的图是原图的最小代价生成树。
六、已知无向图G和G’互为补图（结点相同，边不重叠，两图合并是完整图），试证明G或G’是连通的.(10)
七、用序列(46,88,45,39,70,58,101,10,66,34)建一个排序二叉树，画出该树，并在等概率下查找成功的平均查找长度.(10)
八、写出下面程序片段的结果(10)。
program ex (input,output);
type
ttt=Array[1..20] of integer;
var
l,j,k,l,n:integer;
a:ttt;
FUNCTION P（VAR a:ttt；var m，n:integer）:integer；
VAR x，y，z:integer；
begin
if n=1
then begin
m:=1; p:=a[1];
end
else begin
x:=n;n:=n-1;y:=P(a,z,n);n:=x
if a[n]>=y then begin
m:=n;P:=a[n]
end
else begin
m:=z;P:=y
end
end
end
end;
begin
readln(n);
for i:=1 to n do
l:=n;
for i:=1 to l do
begin
k:=P(a,j,n);
a[j]:=a[n];
a[n]:=k;
n:=n-1
end;
for i:=1 to l do
write (A[I]:3);
writeln
end.
输入数据:8
6,1,8,4,3,5,2,7
九、已知二叉树用下面的顺序存储结构，写出中序遍历该二叉树的算法。
type
Array [1..maxlen] of
record
data:char; //存储结点值
Lc,Rc;integer; //存左孩子右孩子的下标，0表示无左孩子右孩子。
end;（10分）
如树 T=A（B（D，E），C（#，F（H，I）））存储为
十、试写出一带头结点单链表为存储结构实现简单选择排序的算法。（10分）
