}
}
for(int j=0;j
if(j
C语言版测试程序见exam6\\10c，具体算当如下：
void interaction(LinkList la,LinkList lb,LinkList &lc)
// 将链表la与lb中共同出现的元素插入到链表lc中 { LinkList pa,pb,pc; lc=new LNode; //生成lc的头结点 pc=lc; //pc永远指向lc的尾结点 pa=la->next; //pa指向la的第一个元素 while(pa) { pb=lb->next; while(pb&&pb->data!=pa->data) pb=pb->next; //在pb中定位pa->data if(pb) //定位成功 { pc->next=new LNode; //生成lc新的尾结点 pc=pc->next; //pc指向新的尾结点 pc->data=pa->data; //将pa->data复制到pc中 } pa=pa->next; } pc->next=NULL; //pc为尾结点，其后继为空 }
*模拟试题（七）
注：本套试题选作
一、单项选择题（每小题 2 分，共20分）
（1）若以1234作为双端队列的输入序列，则既不能由输入受限双端队列得到，也不能由输出受限双端队列得到的输出序列是（ ）。
A）1234 B）4132 C）4231 D）4213 （2）将一个A[1..100,1..100]的三对角矩阵，按行优先存入一维数组B[298]中，A中元
素a66,65（即该元素下标）在B数组中的位置k为（ ）（假设B[0]的位置是1）。 A）198 B）195 C）197 D）198
【分析】如下所示，三对角矩阵第1行和最后1行非零元素个数为2个，其余各行的非零元素个数是3个，所知a66,65前面共有2+3*64＝194个非零元素，a66,65本身是第 195个非零元。
?a11?a?21??A???????a12a22a32a23a33?a34?an?2,n?1?an?2,n?2an?1,nan?2,n?1an?1,n?1an,n?1?n??1 ??m??n?1? ??m?1??????? ??an?1,n?ann???n??1 ??m?1? （3）若度为m的哈夫曼树中，其叶结点个数为n，则非叶结点的个数为（ ）。
A）n-1
B）?C）?D）?（4）若一个有向图具有拓扑排序序列，并且顶点按拓扑排序序列编号，那么它的邻
接矩阵必定为（ ）。
A）对称矩阵 B）稀疏矩阵 C）三角矩阵 D）一般矩阵
（5）设森林 F对应的二叉树为有 m个结点，此二叉树根的左子树的结点个数为k，则另一棵子树的结点个数为（ ）。
A）m-k+1 B）k+1 C）m-k-1 D）m-k （6）假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行（ ）次探测。
A）K-1次 B）K次 C）K＋l次 D）K(K+1)/2次 （7）一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有（ ）个结点。
A）2k-1-1 B）2k-1 C）2k-1+1 D）2k-1
（8）如表r有100000个元素，前99999个元素递增有序，则采用（ ）方法比较次数较少。
A）直接插入排序 B）快速排序 C）归并排序 D）选择排序 （9）如果只考虑有序树的情形，那么具有7个结点的不同形态的树共有（ ）棵。
A）132 B）154 C）429 D）前面均不正确
（10）对ISAM
文件的删除记录时，一般(
B）需移动记录
)
A）只需做删除标
C）需改变指针 D）一旦删除就要做整理
二、（本题8分）
斐波那契数列Fn定义如下：
F0=0，F1=1，Fn=Fn-1+Fn-2
请就此斐波那契数列，回答下列问题：
（1）在递归计算Fn的时候，需要对较小的Fn-1，Fn-2，?，F1，F0精确计算多少次？ （2）若用有关大O表示法，试给出递归计算Fn时递归函数的时间复杂度是多少？ 三、（本题8分） 证明：如果一棵二叉树的后序序列是u1,u2,?,un，中序序列是up,up,?,up，则由
12n序列1,2,?,n可通过一个栈得到序列p1,p2,?,pn。
四、（本题8分）
如下图所示为5个乡镇之间的交通图，乡镇之间道路的长度如图中边上所注。现在要在这5个乡镇中选择一个乡镇建立一个消防站，问这个消防站应建在哪个乡镇，才能使离消防站最远的乡镇到消防站的路程最短。试回答解决上述问题应采用什么算法，并写出应用该算法解答上述问题的每一步计算结果。
图 乡镇交通图
五、（本题8分）
证明一个深度为n的AVL树中的最少结点数为：Nn=Fn+2-1 (n≥0) 其中，Fi为Fibonacci数列的第i项。 六、（本题8分）
简单回答有关AVL树的问题：（北方名校经典试题）
（1）在有 n个结点的AVL树中，为结点增加一个存放结点高度的数据成员，那么每一个结点需要增加多少个字位（bit）？
（2）若每一个结点中的高度计数器有8bit，那么这样的AVL树可以有多少层？最少有多少个关键码？
七、（本题8分）
设有12个数据 {25，40，33，47，12，66，72，87，94，22，5，58}，它们存储在散列表中，利用线性探测再散列解决冲突，要求插入新数据的平均查找次数不超过3次。
（1）该散列表的大小m应设计多大？ （2）试为该散列表设计相应的散列函数。
（3）顺次将各个数据散列到表中。 （4）计算查找成功的平均查找次数。 八、（本题8分）
已知某电文中共出现了10种不同的字母，每个字母出现的频率分别为A：8，B：5，C：3，D：2，E：7，F：23，G：9，H：11，I：2，J：35，现在对这段电文用三进制进行编码（即码字由0，l，2组成），问电文编码总长度至少有多少位？请画出相应的图。
九、（本题9分）
N2个度为2的结点，Nm个度为m已知一棵度为m的树中有N1个度为1的结点，?，
的结点。试问该树中有多少个叶子结点？（北方名校经典试题）
十、（本题15分）
试用递归法编写输出从n个数中挑选 k个进行排列所得序列的算法。
模拟试题（七）参考答案
一、单项选择题（每小题 2 分，共20分） （1）参考答案：C）
（2）【分析】如下所示，三对角矩阵第1行和最后1行非零元素个数为2个，其余各行的非零元素个数是3个，所知a66,65前面共有2+3*64＝194个非零元素，a66,65本身是第 195个非零元。
?a11?a?21??A???????a12a22a32a23a33?a34?an?2,n?1?an?2,n?2an?1,nan?2,n?1an?1,n?1an,n?1?????? ??an?1,n?ann??参考答案：B）
（3）【分析】在哈夫曼树的非叶结点中最多只有1个结点的度不为m，设非叶结点的个数为k，则其中有k-1个结点的度为m，设另1个结点的度为u，则2≤u≤m，设结点总数为n总，则有如下关系：
n总-1=m(k-1)+u ① n总=k+n ②
将②代入①可得：k+n-1= m(k-1)+u，解得：k?(n?1)?(m?u)，由于2≤u≤m，
m?1
所以可得0≤m-u＜m-1，所以可得：
n?1n?1?n?1?+1，可知k??≤k＜。 ?m?1m?1m?1??参考答案：C）
（4）【分析】设顶点按拓扑排序序列为：v0,v1,…,vn-1，则对于邻接矩阵A，只有当i
参考答案：C）
（5）【分析】设另一棵子树的结点个数为n，所以有 m=n+k+1，可知n= m-k-l。 参考答案：C）
（6）【分析】因为K个关键字互为同义词，只有在存入第一个关键字的情况下不发生冲突，所以至少需进行1+2+?+K=K(K+1)/2次探测。
参考答案：D）
（7）【分析】由于每个非终端结点的平衡因子均为0，所以每个非终端结点必有左右两个孩子，且左子树的高度和右子树的高度相同，这样AVL树是满二叉树。高度为k的
k
满二叉树的结点数为2-l。
参考答案：D） （8）【分析】本题中只有直接插入排序利用前面有序的子序列这个性质，如用直接插入排序对本题只需将最后一个元素插入到前面99999个元素的有序子序列中即可，显然比较次数较少。
参考答案：A）
（9）【分析】具有n个结点有不同形态的树的数目和具有n-l个结点互不相似的二叉树的数目相同（将树转化为二叉树时，根结点右子树为空，所以除根结点而外只有左子树，其不相似的二叉树的等价于不相似的左子树）。具有n个结点互不相似的二又树的数目为
11n6C2C12?132。 n，本题中应为n?16?1参考答案：A）
（9）参考答案：A）
二、（本题8分）
【解答】
（1）设在计算Fn时，由Fn-1+Fn-2可知Fn-1要精确计算1次； 由Fn-1=Fn-2+Fn-3可知Fn=2Fn-2+Fn-3，Fn-2要精确计算2次；
由Fn-2=Fn-3+Fn-4可知Fn=3Fn-3+2Fn-4，Fn-3要精确计算3次，Fn=3Fn-3+2Fn-4公式中Fn-3
的系数为Fn-3要精确计算次数，而Fn-4的系数为Fn-2要精确计算次数，以此类推，设Fn-j的精确计算次为aj，则有：Fn=aj*Fn-j+aj-1*Fn-j-1。
Fn-j-1的精确计算次数为aj+1， 由Fn-j=Fn-j-1+Fn-j-2可知Fn=(aj+ aj-1)*Fn-j-1+aj*Fn-j-2 ，所以有：
aj+1=aj+aj-1