文档介绍：Prepared on 21 November 2021
数据结构期末试卷B
厦门大学《＿数据结构＿》课程期末试卷
信息科学与技术学院计算机科学系2007年级＿＿＿专业
主考教师：＿陈怡疆庄朝晖＿试卷类型：Prepared on 21 November 2021
数据结构期末试卷B
厦门大学《＿数据结构＿》课程期末试卷
信息科学与技术学院计算机科学系2007年级＿＿＿专业
主考教师：＿陈怡疆庄朝晖＿试卷类型：（B卷）
一、（本题16分）回答下列问题，同时举例说明之：
（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系
（2）若逻辑结构相同但存储结构不同，则为不同的数据结构。这样的说法对吗
（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗
二、（本题10分）设有3阶B－树，如下图所示，分别画出在该树插入关键字20和在原树删除关键字150得到的B－树。
100
50　80
150
30　40
60　70
90
120
180
三、（本题15分）已知键值序列为｛45,56,83,31,72,35,14,47,89,19｝，要求给出：
按键值排列次序构造一棵二叉排序树。
在等概率的情况下，该二叉排序树查找成功的平均查找长度。
针对上述10个键值，在不同的排列次序下所构造出的不同形态的二叉排序树中，在最坏和最好情况下，二叉排序树的高度各是多少
四、（本题14分）对关键字序列：49，38，66，80，70，15，22进行从小到大的排序