10. 向一棵B_树插入元素的过程中 ， 若最终引起树根结点的分裂 ， 则新树比原树的高度___________ 。
11 。
。

8、 在堆排序的过程中 ， 对任一分支结点进行筛运算的时间复杂度为________ ， 整个堆排序过程的时间复杂度为________ 。
12 。
在快速排序、堆排序、归并排序中 ， _________排序是稳定的.三、 运算题（每题 6 分 ， 共24分）1. 在如下数组A中链接存储了一个线性表,表头指针为A 0.next ， 试写出该线性表 。
A 0 1 2 3 4 5 6 7 data605078903440next35720412 。
请画出图10的邻接矩阵和邻接表 。
图103.已知一个图的顶点集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) 。

9、6 ， （3 ， 4)15,（3,5)12 ， （3,6)9 ， （4,6）4 ， （4,7)20 ， (5,6)18, (6 ， 7)25；用克鲁斯卡尔算法得到最小生成树,试写出在最小生成树中依次得到的各条边.4. 画出向小根堆中加入数据4, 2 ，5, 8 ，3时 ， 每加入一个数据后堆的变化 。
四、 阅读算法（每题7分 ， 共14分）1. LinkList mynote（LinkList L）/L是不带头结点的单链表的头指针if（L&L-next)q=L；L=Lnext；p=L；S1： while（pnext） p=pnext；S2： pnext=q；qnext=NULL；return L；请回答下列问题:(1)说明语句S1 。

10、的功能；（2)说明语句组S2的功能；（3）设链表表示的线性表为（a1,a2,， an),写出算法执行后的返回值所表示的线性表.2. void ABC(BTNode * BT)if BT ABC （BT-left）;
ABC (BT-right);
coutdata)item=BSTdata;
/查找成功return ___________；else if（itemdata)return Find（______________,item)；else return Find（_______________,item)；/if六、 编写算法（共8分）统计出单链表HL中结点的值等于给定值X的结点数.int。

11、CountX（LNode HL,ElemType x）试题1答案一、 单选题（每题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 34. -1 3 4 X * + 2 Y * 3 / 5. 2n n1 n+16 。
e 2e7 。
有向无回路8. n（n1）/2 n(n-1）9. （12 ， 40） ( ） （74） （23 ， 55 ， 63）10. 增加111 。
O(log2n） O（nlog2n）12. 归并三、 运算题（每题6分 ， 共24分)1 。
线性表为：（ 。

12、78 ， 50,40 ， 60 ， 34 ， 90）2 。
邻接矩阵：邻接表如图11所示：图113 。
用克鲁斯卡尔算法得到的最小生成树为： (1,2)3 ，(4 ， 6)4 ，(1 ， 3）5 ，（1 ， 4)8 ，(2 ， 5)10 ，（4,7）204. 见图124444422255285283452843图12四、 阅读算法（每题7分 ， 共14分）1. (1）查询链表的尾结点（2）将第一个结点链接到链表的尾部 ， 作为新的尾结点(3）返回的线性表为(a2,a3 ， an,a1) 2 。
递归地后序遍历链式存储的二叉树 。
五、 算法填空（每空2分,共8 分）true BST-left BSTright 六、 编写算法（8分)int Cou 。

13、ntX(LNode HL ， ElemType x) int i=0;
LNode p=HL;
/i为计数器 while（p！=NULL) if （P-data=https://www.renrendoc.com/paper/x） i+;
p=pnext；/while ，出循环时i中的值即为x结点个数return i；/CountX数据结构期末考试试题及答案 2一、 单选题（每小题2分,共8分）1、在一个长度为n的顺序线性表中顺序查找值为x的元素时 ， 查找成功时的平均查找长度（即x与元素的平均比较次数 ， 假定查找每个元素的概率都相等）为 ( ） 。
A n B n/2 C （n+1)/2 D (n-1)/22、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p 。

14、之间插入一个s所指的结点 ， 则执行( ） 。
A slink=plink;
plink=s； B plink=s； slink=q；C plink=slink； slink=p;
D q link=s;
slink =p；3、 栈的插入和删除操作在（ ）进行 。
A 栈顶 B 栈底 C 任意位置 D 指定位置4、 由权值分别为11 ， 8,6 ， 2 ， 5的叶子结点生成一棵哈夫曼树 ， 它的带权路径长度为（ ）A 24 B 71 C 48 D 53二、 填空题（每空1分 ， 共32分）1、数据的逻辑结构被分为__________、 ___________ 、________和________四种 。
2、一种抽象数据类型包括 。

15、______________和_____________两个部分 。
3、在下面的数组a中链接存储着一个线性表 ， 表头指针为ao 。
next ， 则该线性表为_________________________________________________ 。
0 1 2 3 4 5 6 7 8 6056423874254376201datanext4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中 ， 判断链表为空的条件分别为________________和____________________ 。
5、用具有n个元素的一维数组存储一个循环队列 ， 则其队首指针总是指向队首元素的___________ ， 该 。

来源：(未知)

【学习资料】网址：/a/2021/0321/0021738320.html

标题：数据结构|(完整word版)2017《数据结构》期末考试试题及答案( 二 )