报告人：陈思同 cst@mail.ustc.edu.cn 数据结构与数据库习题课 报告人：陈思同 cst@mail.ustc.edu.cn

Chapter9 查找 9.1 对大小均为n的有序顺序表和无序顺序表，平均查找长度是否相同 1查找不成功，没有关键字等于K 平均下（2+3+…+N+1)/N = (N+3)/2 不考虑哨兵，N，(N+1)/2

Chapter9 查找 9.1 对大小均为n的有序顺序表和无序顺序表，平均查找长度是否相同 2查找成功，仅有一个 相同 （1+2+3+…+N)/N = (1+N)/2

Chapter9 查找 9.1 对大小均为n的有序顺序表和无序顺序表，平均查找长度是否相同 3查找成功，有若干个 对有序：假定第一个出现在第k个位置，找到第一个k+1,(k<=N)，再加上可能出现p个关键字，(1+k)+p-1+1=(1+k)+p 其中，k<=N, p<=N-k

Chapter9 查找 9.1 对大小均为n的有序顺序表和无序顺序表，平均查找长度是否相同 3查找成功，有若干个（p)相同 (1+k)+p-1+1=(1+k)+p 其中，k<=N, p<=N-k 求平均：k随机分布至n,k=(1+n)/2； p可能终止于(1+n)/2至n任一点,p=(n-1)/4， 所以1+k+p=(3n+5)/4

Chapter9 查找 9.2 （a,b,c,d,e,f,g) 折半查找 E: d->f->e F: d->f G: d->f->g

Chapter9 查找 9.3 画出对长度为17的有序表进行折半查找的判定树，并分别求成功和失败的ASL {1 2 3 4 5 6 7 8 }9 {11 12 13 14 15 16 17}

Chapter9 查找 9.3 画出对长度为17的有序表进行折半查找的判定树，并分别求成功和失败的ASL

Chapter9 查找 9.4已知如下所示长度为12的表： (Jan, Feb, Mar, Apr, May, Jun, July, Aug, Sep, Oct, Nov, Dec) 表中，每个元素的查找概率分别为： (0.1,0.25,0.05,0.13,0.01,0.06,0.11,0.07,0.02,0.03,0.1,0.07) (1)若对该表进行顺序查找，求查找成功的平均查找长度； (2)画出从初态为空开始，依次插入结点，生成的二叉排序树； (3)计算该二叉排序树查找成功的平均查找长度； (4)将二叉排序树中的结点Mar删除，画出经过删除处理后的二叉排序树 (1) ASL = 0.1*1+0.25*2 +0.05*3+…+0.07*12 = 5.43 或 ASL = 0.1*12+0.25*11+0.05* 10 +…+0.07*1 = 7.57

Chapter9 查找 (2)排序方式：ASCII码 9.4已知如下所示长度为12的表： (Jan, Feb, Mar, Apr, May, Jun, July, Aug, Sep, Oct, Nov, Dec) 表中，每个元素的查找概率分别为： (0.1,0.25,0.05,0.13,0.01,0.06,0.11,0.07,0.02,0.03,0.1,0.07) (1)若对该表进行顺序查找，求查找成功的平均查找长度； (2)画出从初态为空开始，依次插入结点，生成的二叉排序树； (3)计算该二叉排序树查找成功的平均查找长度； (2)排序方式：ASCII码 (3)ASL= 0.1*1+（0.25 + 0.05)*2+(0.13+0.06+0.01)*3+… = 3.2

Chapter9 查找 9.4已知如下所示长度为12的表： (Jan, Feb, Mar, Apr, May, Jun, July, Aug, Sep, Oct, Nov, Dec) 表中，每个元素的查找概率分别为： (0.1,0.25,0.05,0.13,0.01,0.06,0.11,0.07,0.02,0.03,0.1,0.07) (4)将二叉排序树中的结点Mar删除，画出经过删除处理后的二叉排序树

Chapter9 查找 9.4 (4)将二叉排序树中的结点Mar删除，画出经过删除处理后的二叉排序树 方法一：首先找到P(Mar)在中序下直接前驱S(Jun),P的右子树(Jun July)改为F(Jan)的右子树，P的右子树改为S(Jun)的右子树，

Chapter9 查找 注：

Chapter9 查找 成功：ASL = (1*7+3+3)/9=13/9 9.5 {10，25，33，19，06，49，37，76，60}，哈希地址空间0—10，哈希函数H(key)=key % 11 (1)开放定址线性探测法 成功：ASL = (1*7+3+3)/9=13/9 失败：ASL =(3+2+1+7+6+5+4+3+2+1+4]=38/11

Chapter9 查找 成功：ASL = (1*7+2+4)/9=13/9 (先-后+) 9.5 {10，25，33，19，06，49，37，76，60}，哈希地址空间0—10，哈希函数H(key)=key % 11 (2)开放定址二次探测法,错误方法（±1，±2） 成功：ASL = (1*7+2+4)/9=13/9 (先-后+) 或：ASL = (1*7+3+3)/9=13/9(先+后-)

Chapter9 查找 成功：ASL = (1*7+2+4)/9=13/9 (先-后+) 9.5 {10，25，33，19，06，49，37，76，60}，哈希地址空间0—10，哈希函数H(key)=key % 11 (2)开放定址二次探测法,正确方法（±1^2，±2^2） 成功：ASL = (1*7+2+4)/9=13/9 (先-后+) 或：ASL = (1*7+3+5)/9=15/9(先+后-)

Chapter9 查找 成功：ASL = (1*7+2+2)/9=11/9 9.5 {10，25，33，19，06，49，37，76，60}，哈希地址空间0—10，哈希函数H(key)=key % 11 (3)拉链法 成功：ASL = (1*7+2+2)/9=11/9

Chapter9 查找 9.6 折半查找的递归算法 int binary_search(SSTable ST, KeyType key, int low, int high) { if (high < low) // test if array is empty return KEY_NOT_FOUND; //return 0; else { int mid = (low + high)/2 ; if (ST.elem[mid] > key) // key is in lower subset return binary_search(ST, key, low, mid-1); else if (ST.elem[mid] < key) // key is in upper subset return binary_search(ST, key, mid+1, high); else return mid; // key has been found }

Chapter10 排序 10.1 {5，1，6，0，9，2，8，3，7，4} 各种排序 (1)直接插入 5… 15… 156… 0156… 01569… 0123456789

Chapter10 排序 10.1 {5，1，6，0，9，2，8，3，7，4} (2)希尔排序（5，3，1增量） 5,1,6,0,9,2,8,3,7,4 d1=5: 2,1,3,0,4,5,8,6,7,9 d2=3: 0,1,3,2,4,5,8,6,7,9 d3=1: 0,1,2,3,4,5,6,7,8,9

Chapter10 排序 10.1 {5，1，6，0，9，2，8，3，7，4} (3)快速排序 5,1,6,0,9,2,8,3,7,4 1: {4,1,3,0,2}5{8,9,7,6} 2: {{2,1,3,0}4}5{{6,7},8,{9}} 3: {0,1,2,3}4,5,6,7,8,9

Chapter10 排序 10.1 {5，1，6，0，9，2，8，3，7，4} (4)冒泡排序(升序) 5,1,6,0,9,2,8,3,7,4 1,5,0,6,2,8,3,7,4,9 1,0,5,2,6,3,7,4,8,9 0,1,2,5,3,6,4,7,8,9 0,1,2,3,5,6,4,7,8,9 0,1,2,3,4,5,6,7,8,9

Chapter10 排序 10.1 {5，1，6，0，9，2，8，3，7，4} (4)冒泡排序(降序) 5,1,6,0,9,2,8,3,7,4 5,6,1,9,2,8,3,7,4,0 6,5,9,2,8,3,7,4,1,0 6,9,5,8,3,7,4,2,1,0 9,6,8,5,7,4,3,2,1,0 9,8,6,7,5,4,3,2,1,0 9,8,7,6,5,4,3,2,1,0

Chapter10 排序 10.1 {5，1，6，0，9，2，8，3，7，4} (5)归并排序 [5,1],[6,0],[9,2],[8,3],[7,4] 1: [1,5,0,6],[2,9,3,8],[4,7] 2: [0,1,5,6 2,3,8,9],[4,7] 3: [0,1,2,3,5,6,8,9,4,7] 4: 0,1,2,3,4,5,6,7,8,9

Chapter10 排序 10.1 {5，1，6，0，9，2，8，3，7，4} (6)堆排序 得到0

Chapter10 排序 10.1 {5，1，6，0，9，2，8，3，7，4} (6)堆排序 得到0,1

Chapter10 排序 10.1 {5，1，6，0，9，2，8，3，7，4} (6)堆排序 0,|1,2,3,4,6,8,5,7,9 0,1,|3,2,5,4,6,8,9,7 0,1,2,|3,6,5,4,7,8,9 0,1,2,3,|4,6,5,9,7,8 0,1,2,3,4,|5,6,8,9,7 0,1,2,3,4,5,|7,6,8,9 …

Chapter10 排序 10.2 稳定：直接插入、冒泡、归并 不稳定：希尔、快排、堆

Chapter10 排序 10.3 (96,86,48,73,35,39,42,57,66,21) 是大顶堆

Chapter10 排序 10.3 (12,70,33,65,24,56,48,92,86,33) 不是堆，调整成小顶堆

Chapter10 排序 10.4 双向起泡法

Chapter10 排序 10.5 单链表实现选择排序算法

Chapter DB1 7. 实体（Entity）：客观存在并可互相区别的事物 属性（Attribute）：实体所具有的某一特性 码（Key）：唯一标识实体的属性集（关键属性） 域（Domain）：属性的取值范围 实体型（Entity Type）：用实体名及其属性集合来抽象和刻画同类实体 实体集（Entity Set）：同型实体的集合

Chapter DB1 7. 实体（Entity）：客观存在并可互相区别的事物 属性（Attribute）：实体所具有的某一特性 码（Key）：唯一标识实体的属性集（关键属性） 域（Domain）：属性的取值范围 实体型（Entity Type）：用实体名及其属性集合来抽象和刻画同类实体 实体集（Entity Set）：同型实体的集合

Chapter DB1 9.学校 E-R概念模型

Chapter DB1 13.关系模型实例 商店（商店编号，商店名，地址） 职工（职工编号，姓名，性别，业绩，商店编号，聘期，月薪） 商品（商品号，商品名，规格，单价） 销售（商店编号，商品号，月销售量

Chapter DB1 15.试述数据库三级模式结构，并说明优缺点 外模式（用户模式） 概念模式 内模式（存储模式） 优点：简化用户接口；有利于数据共享，减少冗余；有利于数据安全等 缺点：在传输数据时需要通过映射逐级传输，一定程度上降低了系统效率

谢谢大家！