上海交通大学数据结构1996-2004年考研试题及答案（转贴）
[b]上海交通大学数据结构1996-2004年考研试题及答案[/b]2004年研究生数据结构试题(70分)上海共享网
一、 已知一棵中序线索二*树的结点结构为：上海共享网
上海共享网
left ltag data rtag right上海共享网
上海共享网
上海共享网
其中：data 域的类型为int。上海共享网
ltag=0,那么left域中存放的是该结点的左儿子结点的地址。上海共享网
ltag=1,那么left域中存放的是该结点的按中序周游次序的前驱结点的地址。上海共享网
rtag=0,那么right域中存放的是该结点的右儿子结点的地址。上海共享网
rtag=1,那么right域中存放的是该结点的按中序周游次序的后继结点地址。上海共享网
现已知该中序线索树中，按照中序遍历次序的第一个结点的地址为first，以及某一整数值为key。请写一个函数，输出结点的data之值为key 的结点，并仍保持中序线索树的性质不变。注意：不准使用递归，额外空间不得大于O(1)。(本题 25 分)上海共享网
要点：1、注意，题目给出的是按照中序遍历次序的第一个结点的地址first，因此必须从first开始查找data之值为key 的结点p及其父结点q，而不能从根结点开始进行寻找。上海共享网
2、若结点p是q的右儿子，可分四种情况进行讨论：上海共享网
A、 结点p是叶子。上海共享网
B、 结点p无左儿子，但有叶印?BR>C、 结点p有左儿子，但无右儿子。上海共享网
D、 结点p既有左儿子，同样也有右儿子。上海共享网
在进行调整后，注意保持调整后的中序穿线树的结点的中序遍历次序不变。上海共享网
3、若结点p是q的左儿子，同样有四种情况必须讨论，同2。上海共享网
上海共享网
二、已知一棵二*树是以二*链表的形式存储的，且结点的数据场的类型为int。现已知该二*树的根结点的地址为root。请写一个非递归的函数(使用的额外空间不得大于O(1))，给出按后序遍历次序的第一个结点的数据场之值。(本题10分)上海共享网
要点：根据后序周游的定义：LRN 可知第一个被访问的结点将是二*树中的最左方的叶子，设p=root，若p 为空，则无解返回，否则有三种情况。上海共享网
1。若有左儿子，则p=p->left;上海共享网
2。若无左儿子，但有右儿子，则p=p->right; 上海共享网
3。若既没有左儿子，也没有右儿子，则p即为所求。上海共享网
上海共享网
三、已知一棵二*树是以二*链表的形式存储的，其结点结构说明如下：（本题10 分。）上海共享网
struct node { int data; // 结点的数据场。上海共享网
struct node *left; // 给出结点的左儿子的地址。上海共享网
struct node * right; // 给出结点的右儿子的地址。上海共享网
}；上海共享网
请在1、2二题的 [ ] 处进行填空，完成题目要求的功能。注意，每空只能填一个语句，多填为 0 分。上海共享网
1、 求出以T 为根的二*树或子树的结点个数。上海共享网
int size (struct node * T ) {上海共享网
if ( [ T == NULL ] ) return 0;上海共享网
else [ return 1 +size(T->left) + size(T->right) ];上海共享网
}上海共享网
2、 求出以T为根的二*树或子树的高度。注：高度定义为树的总的层次数。上海共享网
int height(struct node * T ) {上海共享网
if ( T == NULL ) [ return 0 ];上海共享网
else [ return 1 +( ( height(T->left) > height(T->right))? height(T->left): height(T->right) ) ];上海共享网
}上海共享网
上海共享网
四、设结点个数为n，请问采用堆排序法进行排序，其时间复杂性是多少？请以大O形式给出，并给出证明。(本题10分)上海共享网
要点： 1、建堆的时间代价：O(n)上海共享网
2、 排序且进行调整的时间代价：log(n-1)+ log(n-2)+……+ log3+ log2 = O(nlogn)上海共享网
证明的详细过程略。上海共享网
上海共享网
五、填空：(本题15分)上海共享网
1、在二*排序树上成功地找到一个结点，在平均情况下的时间复杂性是 [ O(logn) ], 在最坏情况下的时间复杂性是 [ O(n) ]。设结点个数为 n，以大O形式给出时间复杂性。上海共享网
2、在二*平衡排序树上成功地找到一个结点，在平均情况下的时间复杂性是 [ O(logn) ], 在最坏情况下的时间复杂性是 [O(logn) ]。设结点个数为 n，以大O形式给出时间复杂性。上海共享网
3、设工作区的容量为W，则置换选择排序法所得到的初始归并段长度的期望值为[ 2w ]。上海共享网
4、设主串和模式的字符个数分别为m和 n，则在最坏情况下，KMP 算法的时间复杂性为 [ O( m+n) ]。上海共享网 2003年研究生入学试题的简单分析和答案上海共享网
一． 已知一棵度为12 的树，它的根结点的地址为 root。该树是用顺序存储方式存储的，说明如下：上海共享网
struct node { int data;// 树中结点的数据场。上海共享网
int son[12]; //给出结点的第一个、第二个……第12个儿子结点上海共享网
//地址。上海共享网
}tnode[M]; //注意：M是一个常量。上海共享网
请设计一个非递归的程序，按前序遍历该树，打印每个结点的的数据场之值，注意：如用递归程序实现，作零分处怼＃ū咎?5 分。）上海共享网
上海共享网
二． 从键盘上输入一串正整数，最后输入－1作为结束标志。如：8,7,1,22,98,46,……,75,-1。请设计一个非递归程序，创建一棵二*排序树，并且该二*排序树业必须是中序线索二*树。设该二*排序树上的结点结构为：上海共享网
left ltag data rtag right上海共享网
上海共享网
其中：data 域为结点的数据场。上海共享网
ltag=0,那么left域中存放的是该结点的左儿子结点的地址。上海共享网
ltag=1,那么left域中存放的是该结点的按中序周游次序的前驱结点的地址。上海共享网
rtag=0,那么right域中存放的是该结点的右儿子结点的地址。上海共享网
rtag=1,那么right域中存放的是该结点的按中序周游次序的后继结点地址。上海共享网
（本题20 分。）上海共享网
上海共享网
三．已知中序线索二*树的某结点的地址为P请设计一个程序给出地址为P 的结点的按前序周游次序的后继结点的地址q。注意：本程序要求辅助空间只能为O(1)，否则作零分处理。另外，结点形式可参考第2 题。（本题15 分。）上海共享网
上海共享网
四．已知某有向图用邻接表表示。该邻接表的结点及边表说明如下：上海共享网
#define TOTAL 1000上海共享网
struct arcnode { int adjvex; // 该边所指向的结点的下标地址。上海共享网
struct arcnode *nextarc; // 给出下一条边的边结点的地址。上海共享网
} arcnode ; // 边结点说明。上海共享网
struct vnode { int data; // 结点数据场，其值为整数。上海共享网
arcnode * firstarc; //指向离开本结点的第一条边的边结点。上海共享网
} vnode, vlist[TOTAL] ; // 图中结点和结点数组说明。上海共享网
设该有向图中必须删除数据场之值为key的结点，请设计一个程序加以实现。上海共享网
（本题15 分。）上海共享网
上海共享网
五．在某二*树上进行前序、中序遍历后发现该二*树的前序序列的最后一个结点和中序序列的最后一个结点是同一个结点。请问该结点具有何种性质？为什么？（本题10 分。）上海共享网
上海共享网
六．在二*树上进行前序遍历时，结点A在结点B之前。而在进行后序遍历时，结点A在结点B之后。那么，结点A是结点B 的足祖先，对吗？为什么？（本题10 分）上海共享网
上海共享网
上海共享网
七．采用比较的办法，从具有n个元素集合中找出最大和次最大的元素，需要的最少比较次数和为多少？说明理由和实现的方法。注意，不必些程序。（本题10 分）上海共享网
上海共享网
八. 在求AOE网络的关键路径时，通常先借助于事件结点的拓扑排序序列求出事件结点的最早发生时间。然后，再求出事件结点的最迟发生时间。在求事件结点的最迟发生时间时，可以利用逆拓扑排序序列进行。请问，如何使用逆拓扑排序序列求事件结点的最迟发生时间？为什麽这样做，是正确的？（本题10 分）上海共享网
上海共享网
九．设外部文件的记录总数为 N ，初始归并段数为M。在进行K-路平衡归并并最终生成一个有序文件时，如采用败者树，那么在内存中进行比较的总的次数为多少？并简单证明一下，你的结论是正确的。（本题10 分）快速排序在平均情况下的时间复杂性是什么？上海共享网
上海共享网
十．在使用K－路平衡归并法，对外部文件进行排序时，K是否越大越好？为什麽？（本题10 分。）上海共享网
上海共享网
十一．图的存储结构，计有：邻接矩阵、邻接边、十字链表和邻接多重表。请分析这四种存储结构的优缺点以及在何种情况下，使用它们最合适。（本题10 分。）上海共享网
上海共享网
十二．设模式T＝“abcabaabc”, 求它的next函数的修正值nextval。下面的函数用于求模式T 的nextval之值。其中，T[0]用于保存模式T 的字符个数，而T[1], T[2],……, T[M] 依次保存模式T 的各个字符。请在该函数的中的 [A]、[b] 处个填如一个赋值表达式，使得数组nextval 能够给出模式T的next 函数的修正值nextval。（本题10 分。）上海共享网
上海共享网
void get_nextval(sstring T, int & nextval [ ] )上海共享网
{ i = 1; nextval[1] = 0; j=0;上海共享网
while ( i < T[0] )上海共享网
{ if ( j== || T[i] == T[j] )上海共享网
{ ++i; ++j;上海共享网
if ( T[i] != T[j] ) nextval[i] = j;上海共享网
else [ A ];上海共享网
}上海共享网
else [ B ];上海共享网
} // while end 上海共享网
} // get_nextval。注意：类型sstring 是字符数组，0号单元存串长度[/i][/i][/i] [/b] 2002年研究生入学试题
一． 从键盘上输入若干个数对，如：( I1，W1)，( I2，W2)，……，( Im，Wm)；其中I1，I2，……， Im 是本结点的层号。注意：根结点的层号为1，其他各层上的结点的层号依次比上一层的结点的层号大 1。另外：W1，W2，……，Wm 是结点的前序(即先根次序)序列。这是用层号＋前序表示树的一种方法。请编写一段程序，存储这棵树。为了简单起见，设这棵树上的结点的度数最大为3，结点的存储形式为：
data parent son1 son2 son3
其中：data 域为结点的数据场，parent 域为结点的双亲结点的地址，son1，son2，son3分别给出结点的三个儿子的地址。
二．已知整数数组 int a[n]。其中，a[1]，a[2]， ……a[n-2]，a[n－1] 已被整理为最小化堆。在将a[1]，a[2]， ……a[n-1]，a[n] 整理成最小堆时，可分两步进行：1、先找出a[n]
之值的插入位置； 2、再进行适当的设计移动即可。现仅仅考虑第一步，找出a[n]之值的插入位置。请设计一个程序加以完成。注意该程序的时间复杂性必须为O(loglogn)，并加以证明。
三．已知一棵排序二*树，树中结点的形式为：
data info left right
其中，data 给出结点的数据场，info 给出本结点的左子树中的结点总数，left和 right 分别给出本结点的左儿子和右儿子的地址。又已知该二*排序树的根结点的地址为 root。请设计二个函数，分别实现下述功能：
1． 按递增序找出该二*排序树中的第 i 个结点。
2． 插入数据场之值为 x 的结点。
四．已知整数数组 int a[n]。其中，a[1]，a[2]， ……a[n-1]，a[n] 已被整理为最小化堆。请设计一个程序，在最短的时间内，找出a[1]，a[2]， ……a[n-1]，a[n]中的最大元素的下标。并且简单证明一下你的程序的代价符合要求。
五．请问折半查找法，在最坏情况下和给定值进行比较的关键字个数（或查找长度）为多少？并请加以证明。
六．填充：
1． 在随机生成二*排序树的情况下的平均查找长度是：1.465log n 或 O(log n)
2． 用 n 个结点构造一棵二*排序树，它的层次至少为： log n」+ 1
3． 在含有n 个结点的树中，若只有两种结点，度为零的叶子结点和度为 k 的其他结点，那么叶子结点的总数为：((k-1)n+1)/k
4． 有 n 个数，如1，2，…… n 依次进栈，并以各种可能的顺序出栈，则出栈后，这n 个
－
数的序列，有 种不同的情况。
5． 在顺序查找时，设成功和失败的概率的可能性相同，又设结点的查找概率也相同。则在考虑成功和失败两种情况下，顺序查找的平均查找长度是：3(n+1)/4 ,设结点的总数为 n 。
七. 已知某通信用电文仅由 A、B、C、D、E、F 六个字符构成，其出现的频率分别为23，
5，14，8，25，7 请给出它们的哈夫曼编码和求解过程。
八．快速排序在平均情况下的时间复杂性是什么？并请给出证明。在算法中如何进行处理，才能使得所使用的额外的堆栈的最大深度下降为O(log n)？其中，n 为结点的总数。为什么？请给出证明。
A
A
九.下列的两棵二*树是完全一致的吗？为什么？如果把它们看作为两棵树呢？讲明你的理由。
B
C
D
B
C
D
十．对一棵树进行广度优先遍历时(从根开始)，得到的序列为：ABCDEFGHIJ
而对它进行后序遍历时得到的序列是：JHIEFBGCDA。请画出它的树形，并给出前序序列。
2002年研究生入学试题的简单分析和答案
一． 从键盘上输入若干个数对，如：( I1，W1)，( I2，W2)，……，( Im，Wm)；其中I1，I2，……， Im 是本结点的层号。注意：根结点的层号为1，其他各层上的结点的层号依次比上一层的结点的层号大 1。另外：W1，W2，……，Wm 是结点的前序(即先根次序)序列。这是用层号＋前序表示树的一种方法。请编写一段程序，存储这棵树。为了简单起见，设这棵树上的结点的度数最大为3，结点的存储形式为：
data parent son1 son2 son3
其中：data 域为结点的数据场，parent 域为结点的双亲结点的地址，son1，son2，son3分别给出结点的三个儿子的地址。
分析：先看一个例子：如：1A, 2B, 2C, 3E, 4G, 3F, 2D, 3X, 3Y, 3Z；它所表示的树为：
由于从键盘上输入的数对是连续的，因此必须分析清楚相邻结点之间的关系：
·第一个输入的结点为根结点，如1A，生成根结点，数据场data为 A ，parent为
空 son1，son2，son3 也为空。
·若新输入的结点比在它之前输入的结点层号大，那么：
新输入的该结点是在它之前输入的结点的儿子结点，因此它的数据场和指针场容易确定。如：1A, 2B以及 3E, 4G 和 2D, 3X,之间的关系。
·若新输入的结点和在它之前输入的结点层号等，那么：
寻找在新输入的结点之前输入的结点，那个结点的层号比新输入的结点的层号小。那么，那个结点即为新输入的结点的父结点，至于新输入的结点是该父结点的第几个儿子，可以查看该父结点的son1，son2，son3 指针场得到。如：2C 和 3Y以及3Z 都是这种情况。
·若新输入的结点比在它之前输入的结点层号小，那么：
寻找在新输入的结点之前输入的结点，哪个结点的层号比新输入的结点的层号小。那么，那个结点即为新输入的结点的父结点，至于新输入的结点是该父结点的第几个儿子，可以查看该父结点的son1，son2，son3 指针场得到。如：3F 和 2D 都是这种情况。
这样分析之后，编写一个程序将是非常容易：设立一个堆栈追踪二*树的变化即可。在堆栈中，只保留层号顺次大 1 的结点，因此堆栈的深度和树的层数成正比。
如上例：堆栈的变化为：
3 E
2 B 2 C 2 C
1 A 1 A 1 A 1 A
层号I 前序序W
4 G
3 E 3 F 3 X
2 C 2 C 2 D 2 D
1 A 1 A 1 A 1 A
前序的层号大1确定了结点的大儿子，第二个和第三个儿子的层号比父结点的层号大且在层号＋前序序列中*近父结点。
二．已知整数数组 int a[n]。其中，a[1]，a[2]， ……a[n-2]，a[n－1] 已被整理为最小化堆。在将a[1]，a[2]， ……a[n-1]，a[n] 整理成最小堆时，可分两步进行：1、先找出a[n]
之值的插入位置； 2、再进行适当的设计移动即可。现仅仅考虑第一步，找出a[n]之值的插入位置。请设计一个程序加以完成。注意该程序的时间复杂性必须为O(loglogn)，并加以证明。
分析：
设a[1] 至a[10]已经整理为最大化堆，现在要将a[1] 至a[11]整理为最大化堆，通过找到a[11]的位置来作到。方法有两种：
1． 新创建一个数组，它的维数为该最小化堆的层数。即：
1 2 3 4
a[1]之值 a[2]之值 a[5]之值 a[11]之值
a[1]之下标1 a[2]之下标2 a[5]之下标5 a[11]之下标11
由于该新创建的数组的前三项，是递增序，所以可用两分查找法找到a[11]之值的插入位置。随之，可确定如何进行数据移动。如：a[11]之值应放在a[2] 的位置。那么，进行如下移动即可：原a[5]之值移到a[11]，原a[2]之值移到a[5]，最后将原a[11] 之值赋值到 a[2]即可。
2． 直接写一段程序，注意到儿子结点的下标除2，即可得到父亲结点的下标。
int K = log n」；int lo = 0; int hi = k-1;
while (lo < hi )
{ int mid = (lo + hi )/2;
if (a[n] < a[n >> ( k-mid)] ) hi = mid;
else lo = mid + 1;
}
所求的 lo 就是 a[11] 之值应插入的位置下标。注意到上例中，第一次比较的中点为 n>>(k-1) 即 11/2/2=2, 若a[11] 小于中点之值，则hi =1。下一次mid =0，比较的中点为 n>>(k-0) 即 11/2/2/2=1,其余依次类推。
三．已知一棵排序二*树，树中结点的形式为：
data info left right
其中，data 给出结点的数据场，info 给出本结点的左子树中的结点总数，left和 right 分别给出本结点的左儿子和右儿子的地址。又已知该二*排序树的根结点的地址为 root。请设计二个函数，分别实现下述功能：
1． 按递增序找出该二*排序树中的第 i 个结点。
2． 插入数据场之值为 x 的结点。
1. 分析：参见下图可知：
若所求的结点的序号 i－1 等于根结点的 info， 那么根结点为所求。若所求的结点的序号 i－1小于根结点的 info，则下一次考察左儿子。若所求的结点的序号 i－1大于根结点的 info，则下一次考察右儿子，此时i = i - ( info+1 )。因此，可写一段很简单的程序实现。如：
int j = i; p = root;
if ( p == NULL ) return ERROR;
else { while( j-1 != p->info)
if ( p->info > j-1 ) p=p->left;
else { j = j - p->info -1; p=p->right ;}
}
print('This is ith node', p->data )
2. 在排序二*树中插入结点，可参考严蔚敏的“数据结构”一书 NO.228。
四．已知整数数组 int a[n]。其中，a[1]，a[2]， ……a[n-1]，a[n] 已被整理为最小化堆。请设计一个程序，在最短的时间内，找出a[1]，a[2]， ……a[n-1]，a[n]中的最大元素的下标。并且简单证明一下你的程序的代价符合要求。
分析：对于最小化对来讲，叶子上的结点之值大于等于内部结点之值。因此，挑选最大结点只需在叶子上挑选一个最大的即可。即：从下标为 n」+ 1 到下标为 n 的结点，进行一次比较。
在 m 个树中，挑选一个最大元，必有判断出m-1 个元素不是最大元，而一次判断至少对应着一次比较。所以，上述算法是最优的。
五．请问折半查找法，在最坏情况下和给定值进行比较的关键字个数（或查找长度）为多少？并请加以证明。
证：设顺序有序表的长度为n,则最坏情况下比较的关键字个数为 log n」+ 1.
1
S（n）=
1 + S（ n/2」）
由于比较一次之后，形成左右两段。它们的长度分别为：若n是奇数，则左右两段长度都为（n-1）/2, 若n是偶数，则右段长 n/2，左段为n/2 -1。由于要求最坏情况下的查找代价，所以应在最长的一段，继续进行查找。而最长的一段都可用n/2」来表示。
S（n）= 1 + S（ n/2」）= 1 + 1 + S（ n/4」）= 1+1+……+1+ S( n/2k」）
= k + S( n/2k」） k个1
当 1 =< n/2k =< 2 时，S( n/2k」）＝1
所以，2k =< n =< 2k＋1 k =< logn =< k+1 故：k = logn」
六．填充：
1． 在随机生成二*排序树的情况下的平均查找长度是：1.465log n 或 O(log n)
2． 用 n 个结点构造一棵二*排序树，它的层次至少为： log n」+ 1
3． 在含有n 个结点的树中，若只有两种结点，度为零的叶子结点和度为 k 的其他结点，那么叶子结点的总数为：((k-1)n+1)/k
4． 有 n 个数，如1，2，…… n 依次进栈，并以各种可能的顺序出栈，则出栈后，这n 个
数的序列，有 种不同的情况。
5． 在顺序查找时，设成功和失败的概率的可能性相同，又设结点的查找概率也相同。则在考虑成功和失败两种情况下，顺序查找的平均查找长度是：3(n+1)/4 ,设结点的总数为 n 。
七. 已知某通信用电文仅由 A、B、C、D、E、F 六个字符构成，其出现的频率分别为23，
5，14，8，25，7 请给出它们的哈夫曼编码和求解过程。
解：
八．快速排序在平均情况下的时间复杂性是什么？并请给出证明。在算法中如何进行处理，才能使得所使用的额外的堆栈的最大深度下降为O(log n)？其中，n 为结点的总数。为什么？请给出证明。
请参照严蔚敏一书 NO 276
九.下列的两棵二*树是完全一致的吗？为什么？如果把它们看作为两棵树呢？讲明你的理由。
解：两棵二*树不是一致的。如果把它们看作为两棵树，则是完全一致的。因为，对于树来讲，空不可能作为 某结点的子树，如上述两图中：A、B、C分别都有一个儿子，无论这两棵树作为有向树还是无向树，组成都是完全一样的。但作为二*树来讲，是完全不一样的，如：左图中，A 的左儿子为空，而右图中，A 的左儿子为B。
十．对一棵树进行广度优先遍历时(从根开始)，得到的序列为：ABCDEFGHIJ
而对它进行后序遍历时得到的序列是：JHIEFBGCDA。请画出它的树形，并给出前序序列。
解：树形：
分析：定根 A，由后序可知 D 是 A 的最小的儿子，故 BCD 分别是 A 的三个儿子。
同理：由后序可知 F 是 B 的最小的儿子，故 EF 分别是 B 的二个儿子。其余，同理 可得。。。。。。。
前序：ABEHJIF 2001
一、参见右图，该有向图是AOE网络。该图上已标出了源点及汇点，并给出了活动（边）的权值。请求出该AOE网络的关键路径、以及事件（结点）的最早发生时间及最迟发生时间。（本题8分）
4
1 2 1
源点 6 3 汇点
3 5
2 2
5 3
二、已知某二*树的每个结点，要么其左、右子树皆为空，要么其左、右子树皆不空。又知该二*树的前序序列为（即先根次序）：J、F、D、B、A、C、E、H、X、I、K；后序序列为（即后根次序）：A、C、B、E、D、X、I、H、F、K、J。请给出该二*树的中序序列（即中根次序），并画出相应的二*树树形。（本题8分）
三、回答下列问题：（本题10分）
（1）具有N个结点且互不相似的二*树的总数是多少？
（2）具有N个结点且不同形态的树的总数是多少？
（3）对二*树而言，如果它的叶子结点总数为N0，设为2的结点的总数为N2，则N0和N2之间的关系如何？
（4）二*树是否是结点的度最多为2的树？请说明理由。
（5）具有n片叶子的哈夫曼树（即赫夫曼树）中，结点总数为多少？
四、在外部分类时，为了减少读、写的次数，可以采用k路平衡归并的最佳归并模式。当初
始归并段的总数不足时，可以增加长度为零的“虚段”。请问增加的“虚段”的数目为
多少？请推导之。设初始归并段为m。（本题8分）
五、对平衡的排序二*树进行删除结点的操作，必须保证删除之后平衡树中的每个结点的平衡因子是+1，-1，0三种情况之一，且该树仍然是排序二*树。现假定删除操作是在p结点的左子树上进行的，且该左子树原来的长度为h-1，现即将改变为h-2。因此，必须从p的左子树沿着到根的方向回溯调整结点的平衡因子，并进行树形的调整。设p是调整时遇到的第一个平衡因子力图由-1变成-2的最年轻的“前辈结点”。我们知道，以p为根的子树经调整后，高度有可能减少1。试用图形把调整前及调整后的相关结点的平衡因子、树形表示出来；仅仅针对调整后子树的高度减少1的情况即可。注意，罗列出所有可能的情况。下图可供参考用。（本题10分）
六、某算法由下述方程表示。请求出该算法的时间复杂度的级别（以大O形式表示）。注意n为求解问题的规模，设n是3的正整数幂。（本题8分）
1 如果n=1
T（n）=
5 T（n/3）+n 如果n>1
七、如图所示，该二*树是某棵有序树变换成的相对应的二*树。试给出原来的有序树的树的形状。并回答以下问题：
（1）原有序树是度为多少的树？
（2）原有序树的叶子结点有哪几个？
（3）是否所有的二*树都可以找到相对应的有序树？必须满足什么条件？
（本题5分）
八、在排序二*树上进行查找操作时，设对树中的每个结点查找概率相同。设由n个结点构成的序列生成的排序二*树是“随机”的。试求出在成功查找的情况下，平均查找长度是多少？为了简单起见，最后得到的递推式可不予求解。（本题8分）
九、设从键盘上每次输入两个字符。如A、B，则表示存在着一条由数据场之值为字符A的结点到数据之值为字符B的结点的有向边。依次输入这些有向边，直至出现字符！为止。试设计一个程序，生成该有向图的邻接表及逆邻接表。必须交待所有的结构、变量、加以适当注解。（本题20分）
十、设二*树中结点的数据场之值为一字符。采用二*链表的方式存储该二*树中的所有结点，设p为指向树根结点的指针。设计一个程序在该二*树中寻找数据场之值为key（key为一变量，变量内容为一字符）的那个结点的所有祖先。设二*树结点数据场之值互不重复。（本题15分）
注意：有些书上将二*树的二*链表存储形式称之为标准存储形式。 2001年试题答案：
1．
关键路径： A B D C F E G
最早发生时间：0 1 3 5 10 13 14
最迟发生时间=最早发生时间：
2．
中序遍历序列：ABCDEFXHIJK
3．
1）C2nn/（n+1）
2）C2（n-1）n-1/n 指有序树
3）N0=N2+1
4）不是，因为二*树不是树的特例。
5）2n-1
4．k-1-（m-1） mod （k-1）
推导参见严蔚敏《数据结构》（C语言版）p.305
5．
6． O (n log35 )
7．
1） 3
2） C D E G H
3） 不是，满足非空且无右子树的二*树。
8．
O （log2 n）
证明参见严蔚敏《数据结构》（C语言版）p.232
9.
略
10.
可以用非递归的后序遍历求解，
当遍历到值为key的结点时，栈中所有结点就是它的所有祖先。 上海交通大学一九九九年硕士生入学考试试题
试题序号：19
试题名称：数据结构及程序设计技术
说明：试卷共十题，第1-5题只需写出实现算法的函数或过程即可，不必写出整个程序，只准使用pascal或C编写（类 pascal和类C均可），必须写清楚算法设计思想及所用的数据结构，对程序要加以适当的注解，程序应有良好的结构，不得使用goto语句，第6-10题直接写出答案即可。
１、 假设有两个按元素值递增有序排列的线性表A和B，均以单链表作存储结构，请编写算法将表A和表B归并成一个按元素非递减有序（允许值相同）排列的线性表C，并要求利用原表（即表A和表B）的结点空间存放表C。（12分）
２、 利用两个栈S1和S2模拟一个队列，写出入队和出队的算法（可用栈的基本操作）。（12分）
３、 试以二*链表作存储结构，编写按层次顺序遍历二*树的算法。（12分）
４、 已知一棵二*树的先序遍历和中序遍历序列分别在于两个一维数组中，试编写算法建立二*树的二*链表。（12分）
５、 写出从哈希表中删除关键字为Ｋ的一个记录的算法，设哈希函数为h,解决冲突的方法为链地址法。（１２分）
６、 考虑下图：（１２分）
１） 从顶点Ａ出发，求它的深度优先生成树。
２） 从顶点Ｅ出发，求它的广度优先生成树。
３） 根据普里姆（Ｐrim）算法，求它的最小生成树。
5 A 2
Ｂ ６ ４ Ｄ
１ C
３ E 5 3
Ｇ １
Ｆ
７、 试求按关键字序列（１２，１，４，３，７，８，１０，２）插入生成的二*排序树和平衡二*树。（７分）
８、 给出一组关键字Ｔ＝（１２，２，１６，３０，８，２８，４，１０，２０，６，１８），写出用下列算法从小到大排序时第一趟结束时的序列：（９分）
１） 希 尔排序（第一趟排序的增量为５）
２） 快速排序（选第一个记录为枢轴（分隔））
３） 链接基数排序（基数为１０）
９、 判别序列（１２，７０，３３，６５，２４，５６，４８，９２，８６，３３）是否为堆，如果不是， 则把它调整为堆。试给出堆排序方法在平均时间性能、最坏情况下的时间性能和辅助存储量，并与快速排序方法在以上三方面进行比较。（８分）
１０、 给出一组关键字Ｔ＝（１２，２，１６，３０，８，２８，４，１０，２０，６，１８），设内存工作区可容纳４个记录，写出用置换－选择排序得到的全部初始归并段。（４分）
1999年试题答案：
1．
void MergeList_L(LinkList &La, LinkList &Lb,LinkList &Lc)
//已知单链线性表La和Lb的元素按值非递减排列。
//归并La和Lb得到新的单链线性表Lc，Lc的元素也按值非递减排列。
{
pa=La->next;pb=Lb->next;
Lc=pc=La; //用La的头结点作为Lc的头结点
while(pa&&pb)
{
if(pa->data<=pb->data)
{ pc->next=pa; pc=pa;pa=pa->next;}
else {pc->next=pb;pc=pb;pb=pb->next;}
}
pc->next=pa?pa:pb; //插入剩余段
free(Lb); //释放Lb的头结点
}//MergeList_L
2．
Void enqueue(Dual Stack Q, DataType a )
{
if(!Q.StackFull(1)) Q.push(a,1);
else return("overflow");
}
DataType dlqueue(DualStack Q)
DataType a;
{if(!(Q.StackEmpty(1)& &Q.StackEmpty(2)))
{if(!Q.StackEmpty(2)) a=Q.pop(2);
else {while(!Q.StackEmpty(1)) Q.push(Q.pop(1),2);
a=Q.pop(2);
}
return(a);
}
else return("Infeasible");
}
3．
void Traverse_level(Bitree bt)
{Initqueue(Q);
Enqueue(Q,bt);
while (!QueueEmpty(Q))
{v=Dlqueue(Q);
visit(Q);
if(!v->lchild)Enqueue(Q,v->lchild);
if(!v->rchild)Enqueue(Q,v->rchild);
}
}
4．
main()
{Datatype preorder[n],inorder[n];
Struct link *BT;
If (n>0)
BT=creat(0,n-1,0,n-1);
Return(BT);
}
struct link * creatBT(int prestart, int preend, int instart, int inend)
{p=(struct link *)malloc(sizeof(struct link));
p->lchild=null;p->rchild=null;
p->data=preorder[prestart];
if (prestart<preend)
{for (i=instart;inorder[i]==preorder[start];i++);
if(i>instart)
p->lchild=creatBT(prestart+1,prestart-instart+i,instart,i-1);
if (i<inend)
p->rchild=creatBT(prestart-instart+i+1,preend,i+1,inend);
}
return(p);
}
5．
hashtable del_hashtable (hashtable &hash, keytype K)
{t=h(k);
if ( hash[t]= = null) return (“infeasible”);
else if (hash[t]= =K) hash[t]=hash[t]->next;
else { found=0;
q=hash[t];
p=hash[t]->next;
while ((!found)&&(p<> null))
if ( p->key= =K)
{found=1;
q->next=p->next;
}
else{q=p; p=p->next;}
if(!found) return (“infeasible”);
}
return(hash);
}
6．
1）（有多种答案）
2）（有多种答案）
3）
7．
二*排序树：
平衡二*树：
8
1) 12 2 10 20 6 18 4 16 30 8 28
2) 6 2 10 4 8 12 28 30 20 16 18
3) 30 10 20 12 2 4 16 6 8 28 18
9.
不是堆,
极小化堆为 12 24 33 65 33 56 48 92 86 70
平均时间 最坏情况 辅助存储
堆排序 O(n log n) O(n log n) O(1)
快速排序 O(n log n) O(n2) O(log n)
10.
2 8 12 16 28 30
4 6 10 18 20
[/i] 上海交通大学一九九八年硕士研究生入学考试试题
试题名称：数据结构和程序设计技术
试题编号：１９
题一（２０分）判断题：若认为下列命题正确，打“a“，反之打“r“
１、 数据元素是数据的最小单位（ ）
２、 队列逻辑上是一个下端口和上端能增加又能减少的线性表（ ）
３、 任何一个递归过程都可以转换成非递归过程。（ ）
４、 只有那种使用了局部变量的递归过程在转换成非递归过程时才必须使用栈（ ）
５、 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入、删除等操作。（ ）
６、 两*树是树的一种特殊情况（ ）
７、 在树中，如果从结点K出发，存在两条分别到达K’，K”的长度相等的路径，由结点K’和k”互为兄弟（ ）
８、 线索两*树的优点是便于在中序遍历下，查找前趋和后继结点（ ）
９、 n个结点的两*树有多种，其中树高最小的两*树排序树是最佳的（ ）
１０、 最佳两*排序树的任何子树都是最佳的（ ）
１１、 设T为一棵平衡树，在其中插入一个结点N，然后立即删除该结点得到T1，T与T1必定相同（ ）
１２、 一个有向图的邻接表和逆邻接表中结点的个数可能不等。（ ）
１３、 任何有向图的结点都可以排成拓扑排序，而且拓扑排序不唯一（ ）
１４、 当改变网上某一关键路上任一关键活动后，必将产生不同的关键路径（ ）
１５、 两分法插入排序所需比较次数与待排序记录的初始排列状态相关（ ）
１６、 当待排序记录已经从小到大排序或者已经从大到小排序时，快速排序的执行时间最省( )
１７、 在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关（ ）
１８、 在执行某个排序算法过程中，出现了排序码朝着最终排序序列相反方向移动，则该算法是不稳定的（ ）
１９、 堆排序是稳定的排序方法（ ）
２０、 在分配排序时，最高位优先分配法比最低位优先分配法简单（ ）
题二、（１５分）试证明：若借助栈由输入序列1,2,…n得到输出序列为p1,p2,…pn,（它是输入序列的一个排序），则在输出序列中不可能出现这样的情形：存在着I<j<k,使pj<pk<pi。
题三、（１２分）假定有下列n*n矩阵（n为奇数） a11 0 …. 0 a1n
0 a22….a2,n-1 0
Ａ＝ . .
. .
. .
an1 0…. 0 ann
如果用一维数组Ｂ按行主次序存储Ａ的非零元素，问 １）Ａ中非零元素的行下标与列下标的关系；
２）给出Ａ中非零元素aij的下标（i,j）与Ｂ中的下标Ｒ的关系；
３）假定矩阵中每个元素占一个存储单元，且Ｂ的起始地址为Ａ０，给出利用aij的下标（i,j）定位在Ｂ中的位置公式。
题四（８分）试找出分别满足下面条件的所有二*树：
１） 前序序列和中序序列相同；
２） 中序序列和后序序列相同；
３） 前序序列和后序序列相同。
题五（１５分）在二*树中查找值为X的结点，试编写算法（用Ｃ语言）打印值为X的结点的所有祖先，假定值为X的结点不多于１个，最后，试分析该算法的时间复杂性。（若不加分析，直接写出结果，按零分算）
题六（１０分）设如下带权有向图，试利用求每对顶点之间最短路径的 Floyd算法，给出代价邻接矩阵，矩阵序列Ａ（i）(i=1,2,3)以及最短路径 PATH<i,j> (1<=i,j<=3)
6 Á
4 2
À
3
11
Â
题七(12分)已知a数组元素共５个，依次为12,10,5,3,1;b数组元素共４个，依次为4,6,8,15，则执行如下所示的过15,12,10,8,6,5,4,3,1，数组a,b,c的长度分别为l=5,m=4,n=9，请在程序中方框内填入正确的成份，以完成上述要求。
Procedure Sort
Var i,j,k,x:integer:
d:array[1..m] of integer;
begin
for i:=1 to m do d[i]:=
i:=1;j:=1;k:=1;
while(i<=l) and (j<=m) do
begin
if a[i]>d[i]
then begin
end;
else begin
end;
c[k]:=x;
end;
while do
begin
c[k]:=a[i]; k:=k+1;i:=i+1
end;
while do
begin
c[k]:=d[j]; k:=k+1;j:=j+1
end;
end;{sort}
题八（８分）已知如下一棵三阶Ｂ＿树，试画出插入关键字B,L,P,Q,R以后的树形。
[/i][/i][/i][/i]
页:
[1]