内容发布更新时间 : 2024/12/25 13:44:09星期一 下面是文章的全部内容请认真阅读。

六、 编写算法（共8分）

统计出单链表HL中结点的值等于给定值X的结点数。 int CountX(LNode* HL,ElemType x)

参考答案

一、 单选题（每题2分，共20分）

1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A 二、 填空题（每空1分，共26分）

1. 正确性 易读性 强壮性 高效率 2. O(n)

3. 9 3 3

4. -1 3 4 X * + 2 Y * 3 / - 5. 2n n-1 n+1 6. e 2e 7. 有向无回路

8. n(n-1)/2 n(n-1)

9. （12，40） （ ） （74） （23,55，63） 10. 增加1

11. O(log2n) O(nlog2n) 12. 归并

三、 运算题（每题6分，共24分）

1. 线性表为：（78，50，40，60，34，90）

?0?1??1??1?2. 邻接矩阵：?01110?0101??1011??0101?1110??

邻接表如图11所示：

图11

3. 用克鲁斯卡尔算法得到的最小生成树为： (1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20

4. 见图12

4 4 2 2

2 2 5 4 8 2 4 4 5 4 8 3 5 2

图12

四、 阅读算法（每题7分，共14分） 1. （1）查询链表的尾结点

（2）将第一个结点链接到链表的尾部，作为新的尾结点 （3）返回的线性表为（a2,a3,?,an,a1） 2. 递归地后序遍历链式存储的二叉树。

五、 算法填空（每空2分，共8 分） true BST->left BST->right 六、 编写算法（8分） int CountX(LNode* HL,ElemType x)

{ int i=0; LNode* p=HL;//i为计数器 while(p!=NULL)

{ if (P->data==x) i++; p=p->next;

}//while, 出循环时i中的值即为x结点个数 return i; }//CountX

一、 单选题（每小题2分，共8分）

1、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为 ( )。

A n B n/2 C (n+1)/2 D (n-1)/2 2、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行( )。

A s→link=p→link; p→link=s; B p→link=s; s→link=q; C p→link=s→link; s→link=p; D q →link=s; s→link =p; 3、 栈的插入和删除操作在（ ）进行。

A 栈顶 B 栈底 C 任意位置 D 指定位置

4、 由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）

A 24 B 71 C 48 D 53 二、 填空题（每空1分，共32分）

1、数据的逻辑结构被分为__________、 ___________ 、________和________四种。

2、一种抽象数据类型包括______________和_____________两个部分。 3、在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则该线性表为_________________________________________________。

a 0 1 2 3 4 5 6 7 8

data

60 56 42 38 74 25 next

4 3 7 6 2 0 1

4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为________________和____________________。

5、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的___________，该循环队列的最大长度为__________。

6、当堆栈采用顺序存储结构时，栈顶元素的值可用———————表示；

当堆栈采用链接存储结构时，栈顶元素的值可用_______________表示。 7、一棵高度为5的二叉树中最少含有_________个结点，最多含有________个结点；

一棵高度为5的理想平衡树中，最少含有_________个结点，最多含有_________个结点。

8、在图的邻接表中，每个结点被称为____________，通常它包含三个域：一是_____________；二是___________；三是_____________。

9、在一个索引文件的索引表中，每个索引项包含对应记录的_________和

___________两项数据。

10、 假定一棵树的广义表表示为A（B（C，D（E，F，G），H（I，J））），则树中所含的结点数为_________个，树的深度为_________,树的度为________, 结点H的双亲结点为________,孩子结点为_______________ 。 11、 在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为_________,整个堆排序过程的时间复杂度为________________。

12、 在对m阶的B_树插入元素的过程中，每向一个结点插入一个索引项（叶子结点中的索引项为关键字和空指针）后，若该结点的索引项数等于______个，则必须把它分裂为_______个结点。

三、 运算题（每小题6分，共24分）

1、已知一组记录的排序码为（46，79，56，38，40，80, 95，24），写出对其进行快速排序的每一次划分结果。

2、一个线性表为B=（12，23，45，57，20，03，78，31，15，36），设散列表为HT[0..12]，散列函数为H（key）= key % 13并用线性探查法解决冲突，请画出散列表，并计算等概率情况下查找成功的平均查找长度。

3、已知一棵二叉树的前序遍历的结果序列是ABECKFGHIJ，中序遍历的结果是EBCDAFHIGJ，试写出这棵二叉树的后序遍历结果。

4、已知一个图的顶点集V各边集G如下：

V = {0，1，2，3，4，5，6，7，8，9}；

E = {（0，1），（0，4），（1，2），（1，7），（2，8），（3，4），（3 ，8），（5，6），（5，8），（5，9），（6，7），（7，8），（8，9）}

当它用邻接矩阵表示和邻接表表示时，分别写出从顶点V0出发按深度优先搜索遍历得到的顶点序列和按广度优先搜索遍历等到的顶点序列。 假定每个顶点邻接表中的结点是按顶点序号从大到小的次序链接的。 图 深度优先序列 广度优先序列

邻接矩阵表示时 邻接表表示时

四、 阅读算法，回答问题（每小题8分，共16分）