}
return LeafCount(T->lchild)+LeafCount(T->rchild);
模拟试题（三）
一、单项选择题（每小题 2 分，共20分）
（1）对一个算法的评价，不包括如下（ ）方面的内容。
A）健壮性和可读性 B）并行性 C）正确性 D）时空复杂度
（2）在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行（ ）。
A）p->next=HL->next; HL->next=p B）p->next=HL; HL=p C）p->next=HL; p=HL D）HL=p; p->next=HL （3）对线性表，在下列哪种情况下应当采用链表表示？（ ）
A）经常需要随机地存取元素 B）经常需要进行插入和删除操作 C）表中元素需要占据一片连续的存储空间 D）表中元素的个数不变
（4）一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（ ）。
A）2 3 1 B）3 2 1 C）3 1 2 D）1 2 3
（5）每一趟都能选出一个元素放在其最终位置上，并且不稳定的排序算法是（ ）。
A）冒泡排序 B）简单选择排序C）希尔排序 D）直接插入排序 （6）采用开放定址法处理散列表的冲突时，其平均查找长度（ ）。
A）低于链接法处理冲突 B）高于链接法处理冲突 C）与链接法处理冲突相同 D）高于二分查找
（7）若需要利用形参直接访问实参时，应将形参变量说明为（ ）参数。
A）值 B）函数 C）指针 D）引用
（8）在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（ ）。
A）行号 B）列号 C）元素值 D）非零元素个数 （9）快速排序在最坏情况下的时间复杂度为（ ）。
A）O(log2n) B）O(nlog2n) C）O(n) D）O(n2) （10）从二叉搜索树中查找一个元素时，其时间复杂度大致为（ ）。
A）O(n) B）O(1) C）O(log2n) D）O(n2) 二、（本题8分）
已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7};
E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15,(3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 三、（本题8分）
请画出如下图所示的邻接矩阵和邻接表。
四、（每小题4分，共8分）
2，6） 设有如下图所示的AOE网（其中vi（i=l，?，表示事件，弧上表示活动的天数）。
v26v14v48217v311v693v5 （1）找出所有的关键路径。
（2）v3事件的最早开始时间是多少。 五、（本题8分）
如果在1000000个记录中找出两个最小的记录，你认为采用什么样的排序方法所需的关键字比较次数最少？最多比较多少次？
六、（本题8分）
假设把n个元素的序列（a1,a2,…an）满足条件ak 七、（每小题4分，共8分） 设内存有大小为6个记录的缓冲区供内排序使用，文件的关键字序列为｛29,50,70,33,38,60,28,31,43,36,25,9,80,100,57,18,65,2,78,30,14,20,17,99），试列出： （1）用内排序求出初始归并段； （2）用置换一选择排序求初始归并段。 八、（本题8分） H(key)=key MOD 已知一组关键字为（19,14,23,1,68,20,84,27,55,11,10,79），哈希函数： 13，哈希地址空间为0~12，请构造用链地址法处理冲突的哈希表，并求平均查找长度。 九、（本题9分） 已知关键字序列{23，13，5，28，14，25}，试构造二叉排序树。 十、（本题15分） 编写一个算法求二又树的深度。 模拟试题（三）参考答案 一、单项选择题（每小题 2 分，共20分） （1）B （2）A （3）B （4）C （5）B （6）B （7）D （8）A （9）D （10）C 二、（本题8分） 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20 三、（本题8分） 0邻接矩阵：???1?1??1??01110? 0101??1011??0101?1110??邻接表如下图所示： 12345211123323345454∧∧∧∧5∧ 四、（每小题4分，共8分） （1）找出所有的关键路径有：v1→v2→v3→v5→v6，以及v1→v4→v6。 （2）v3事件的最早开始时间是13。 五、（本题8分） 采用树形选择排序方法所需的关键字比较次数最少，最多比较次数=999999+?log21000000?=1000019次。 六、（本题8分） 不对，例如序列｛3、3、4、2、l｝的“逆序元素”个数是2，2和1是“逆序元素”；但是将第二个3和2交换后，成为｛3、2、4、3、l｝，此时“逆序元素”个数是3，2、3和1是“逆序元素”。然而交换后一定减少的是“逆序对”的个数，例如上例中｛3、3、4、2、l｝的逆序对的个数是 7，交换第二个 3和2后，｛3、2、4、3、1｝的逆序对的个数是6。 七、（每小题4分，共8分） （1）用内排序求出初始归并段为： 归并段1：29,33,38,50,60,70: 归并段2：9,25,28,31,36,43 归并段3：2,18,57,65,80,100: 归并段4：14,17,20,30,78,99. （2）用置换一选择排序求初始归并段为： 归并段1：29,33,38,50,60,70,80,100 归并段2：9,18,25,28,31,36,57,65,78,99; 归并段3：2,14,17,20,30. 八、（本题8分） 用链地址法处理冲突的哈希表如下图所示： ASL=1(1*6+2*4+3*1+4*1)=1.75 12九、（本题9分） 构造二叉排序树的过程如下图所示。 构造的二叉排序树如下图所示： 十、（本题15分） 若二叉树为空，深度为0；若二叉树不空，则二叉树的深度为左右子树深度的最大值加1。本题最简单算法是递归算法。 C++语言版测试程序见exam3\\10c++，具体算当如下： template int bitree_depth(const Binary_tree template int aux_bitree_depth(Binary_node C语言版测试程序见exam3\\10c，具体算当如下： int BiTreeDepth(BiTree T) // 求二叉树的深度 { if(T==NULL) return 0; //空二叉树的深度为0 else { int d_lsub,d_rsub; d_lsub=BiTreeDepth(T->lchild); //左子树的深度 d_rsub=BiTreeDepth(T->rchild); //右子树的深度 //返回左右子树的深度最大值加1 return ((d_lsub>d_rsub)?d_lsub:d_rsub)+1; } }