若对大小均为n的有序顺序表和无序顺序表分别进行顺序查

第九章 查找

9.1 若对大小均为n的有序顺序表和无序顺序表分别进行顺序查找,试在下列三种情况下分别讨论两者在等概率时平均查找长度是否相同?

(1)查找不成功,即表中没有关键字等于给的值K的记录;

(2)查找成功,且表中只有一个关键字等于给定值K的记录;

(3)查找成功,且表中有若干关键字等于给定值K的记录,要求找出所有这些记录。 答:(1)相同,有序n+1; 无序n+1

(2)相同,有序n1n1;无序 22

(3)不相同,对于有序表,找到了第一个与K相同的元素后,只要再找到与K不同的元素,即可停止查找;对于无序表,则要一直查找到最后一个元素。

9.3 画出对长度为13的有序表进行折半查找的判定树,并分别求其等概率时查找成功和查找不成功的ASL。 141(11223446) 1313

2615查找失败:ASL*3*4(P220:查找不成功的过程就是走了一条从根节点到14147答:查找成功:ASL

外部节点的路径,和给定值进行比较的关键字个数等于该路径上内部结点个数)

注:在折半查找判定树中,查找不成功时的比较次数即是查找相应外结点时与内结点的比较次数。整个判定树代表的有序表在查找失败时的平均查找长度即为查找每个外结点的比较次数之和除以外结点的个数。例如,长度为10的有序表在查找失败时的平均查找长度为:

ASL=(3×5+4×6)/11=39/11

第二次作业

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)ASLPCii,Pi为查找表中第i个记录的概率,Pi1

i1i1nn

ASL=0.1+0.25*2+3*0.05+4*0.13+5*0.01+6*0.06+7*0.11+8*0.07+9*0.02+10*0.03+11*0.1+12*0.07=5.43

或者

ASL=12*0.1+11*0.25+10*0.05+9*0.13+8*0.01+7*0.06+6*0.11+5*0.07+4*0.02+3*0.03+0.1*2+0.07=7.57

(2)画出初始为空,依次插入结点,生成的二叉排序树

(3)该二叉排序树查找成功的平均查找长度。

ASL=0.1+2*(0.25+0.05)+3*(0.13+0.01+0.06)+4*(0.11+0.07+0.02)+(0.03+0.07)*5+6*0.1=3.2

(4)将二叉排序树中的结点Mar删除,画出经过删除处理后的二叉排序树 方法(1)

方法(2)

9.5在地址空间为0~16的散列区中,对以下关键字序列构造两个哈希表:(Jan,Feb,Mar,Apr,May,Jun,July,Aug,Sep,Oct,Nov,Dec)

(1)用线性探测开放定址法处理冲突;

(2)用链地址法处理。

分别求这两个哈希表在等概率情况下查找成功和不成功时的平均查找长度。设哈希表函数为H(x)=︱i/2 ︳,其中i为关键字中第一个字母在字母表中的序号。

(1)线性探测法

当发生冲突时,线性探测法从冲突位置的下一个位置起,依次寻找空的散列地址,即: Hi=(H(key)+di) % m (di=1,2,…,m-1)。

等概率情况查找成功的ASL=(5*1+3*2+5+4+6+3)/12=29/12

查找不成功的ASL定义:查找不成功是需和给定值进行比较的关键字个数的期望值。 等概率情况查找不成功的ASL=(13+12+…+1+4*1)/17=95/17

(2)拉链法(链地址法)

用拉链法处理冲突构造的散列表叫做开散列表

[***********]41516

等概率情况查找成功的ASL=(7*1+3*2+2*3)/12=19/12

等概率情况查找不成功的ASL=(10*1+4*2+1*3+2*4)/17=29/17

9.7写出判断一棵二叉树是否是二叉排序树的算法,设二叉排序树中不存在关键字值相同的结点

二叉排序树定义如下,二叉排序树或者是一棵空树;或者是具有下列性质的树。 1,若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值 2,若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值 3,它的左右子树也分别为二叉排序树

int last=0,flag=1;

int Is_BSTree(Bitree T)//判断二叉树T是否二叉排序树,是则返回1,否则返回0 {

if(T->lchild&&flag) Is_BSTree(T->lchild);

if(T->data

last=T->data;

if(T->rchild&&flag) Is_BSTree(T->rchild);

return flag;

}//Is_BSTree

根据递规定义,如下的递规算法:

typedef struct node

{

datatype data;

struct node left,right;

}NODE,*TREE;

int IsBST0(TREE t, int *pmax, int *pmin) { int max, min;

if(!t->left) *pmin=t->data;

else{

if(!IsBST0(t->left,&max,&min) return 0;

if(max>t->data) return 0; *pmin=min;

}

if(!t->right) *pmax=t->data; else{

if(!IsBST0(t->right,&max,&min) return 0;

if(min>t->data) return 0; *pmax=max;

}

return -1;

}

int IsBST(TREE)

{

int max,min;

if(!t)

return -1;

else

return IsBST0(t,&max,&min);

}

第九章 查找

9.1 若对大小均为n的有序顺序表和无序顺序表分别进行顺序查找,试在下列三种情况下分别讨论两者在等概率时平均查找长度是否相同?

(1)查找不成功,即表中没有关键字等于给的值K的记录;

(2)查找成功,且表中只有一个关键字等于给定值K的记录;

(3)查找成功,且表中有若干关键字等于给定值K的记录,要求找出所有这些记录。 答:(1)相同,有序n+1; 无序n+1

(2)相同,有序n1n1;无序 22

(3)不相同,对于有序表,找到了第一个与K相同的元素后,只要再找到与K不同的元素,即可停止查找;对于无序表,则要一直查找到最后一个元素。

9.3 画出对长度为13的有序表进行折半查找的判定树,并分别求其等概率时查找成功和查找不成功的ASL。 141(11223446) 1313

2615查找失败:ASL*3*4(P220:查找不成功的过程就是走了一条从根节点到14147答:查找成功:ASL

外部节点的路径,和给定值进行比较的关键字个数等于该路径上内部结点个数)

注:在折半查找判定树中,查找不成功时的比较次数即是查找相应外结点时与内结点的比较次数。整个判定树代表的有序表在查找失败时的平均查找长度即为查找每个外结点的比较次数之和除以外结点的个数。例如,长度为10的有序表在查找失败时的平均查找长度为:

ASL=(3×5+4×6)/11=39/11

第二次作业

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)ASLPCii,Pi为查找表中第i个记录的概率,Pi1

i1i1nn

ASL=0.1+0.25*2+3*0.05+4*0.13+5*0.01+6*0.06+7*0.11+8*0.07+9*0.02+10*0.03+11*0.1+12*0.07=5.43

或者

ASL=12*0.1+11*0.25+10*0.05+9*0.13+8*0.01+7*0.06+6*0.11+5*0.07+4*0.02+3*0.03+0.1*2+0.07=7.57

(2)画出初始为空,依次插入结点,生成的二叉排序树

(3)该二叉排序树查找成功的平均查找长度。

ASL=0.1+2*(0.25+0.05)+3*(0.13+0.01+0.06)+4*(0.11+0.07+0.02)+(0.03+0.07)*5+6*0.1=3.2

(4)将二叉排序树中的结点Mar删除,画出经过删除处理后的二叉排序树 方法(1)

方法(2)

9.5在地址空间为0~16的散列区中,对以下关键字序列构造两个哈希表:(Jan,Feb,Mar,Apr,May,Jun,July,Aug,Sep,Oct,Nov,Dec)

(1)用线性探测开放定址法处理冲突;

(2)用链地址法处理。

分别求这两个哈希表在等概率情况下查找成功和不成功时的平均查找长度。设哈希表函数为H(x)=︱i/2 ︳,其中i为关键字中第一个字母在字母表中的序号。

(1)线性探测法

当发生冲突时,线性探测法从冲突位置的下一个位置起,依次寻找空的散列地址,即: Hi=(H(key)+di) % m (di=1,2,…,m-1)。

等概率情况查找成功的ASL=(5*1+3*2+5+4+6+3)/12=29/12

查找不成功的ASL定义:查找不成功是需和给定值进行比较的关键字个数的期望值。 等概率情况查找不成功的ASL=(13+12+…+1+4*1)/17=95/17

(2)拉链法(链地址法)

用拉链法处理冲突构造的散列表叫做开散列表

[***********]41516

等概率情况查找成功的ASL=(7*1+3*2+2*3)/12=19/12

等概率情况查找不成功的ASL=(10*1+4*2+1*3+2*4)/17=29/17

9.7写出判断一棵二叉树是否是二叉排序树的算法,设二叉排序树中不存在关键字值相同的结点

二叉排序树定义如下,二叉排序树或者是一棵空树;或者是具有下列性质的树。 1,若它的左子树不空,则左子树上所有结点的值均小于它的根结点的值 2,若它的右子树不空,则右子树上所有结点的值均大于它的根结点的值 3,它的左右子树也分别为二叉排序树

int last=0,flag=1;

int Is_BSTree(Bitree T)//判断二叉树T是否二叉排序树,是则返回1,否则返回0 {

if(T->lchild&&flag) Is_BSTree(T->lchild);

if(T->data

last=T->data;

if(T->rchild&&flag) Is_BSTree(T->rchild);

return flag;

}//Is_BSTree

根据递规定义,如下的递规算法:

typedef struct node

{

datatype data;

struct node left,right;

}NODE,*TREE;

int IsBST0(TREE t, int *pmax, int *pmin) { int max, min;

if(!t->left) *pmin=t->data;

else{

if(!IsBST0(t->left,&max,&min) return 0;

if(max>t->data) return 0; *pmin=min;

}

if(!t->right) *pmax=t->data; else{

if(!IsBST0(t->right,&max,&min) return 0;

if(min>t->data) return 0; *pmax=max;

}

return -1;

}

int IsBST(TREE)

{

int max,min;

if(!t)

return -1;

else

return IsBST0(t,&max,&min);

}


相关文章

  • C语言冒泡.插入法.选择排序算法
  • C 语言中三种常见排序算法分析 一.冒泡法(起泡法) 算法要求:用起泡法对10个整数按升序排序. 算法分析:如果有n 个数,则要进行n-1趟比较.在第1趟比较中要进行n-1次相邻元素的两两比较,在第j 趟比较中要进行n-j 次两两比较.比较 ...查看


  • 护理学研究自考名词解释2012
  • 实验:是指用物质手段主动控制和改造研究对象,从而获得有关研究对象的本质规律的知识. 研究:是通过系统地.有控制地收集资料,反复地探索未知,客观地认识各种自然现象和社会现象的活动.是一种系统地探索和解决问题的活动,并能从中获得客观规律和产生新 ...查看


  • 山东大学[卫生统计学]网上教案3
  • 第八章 2检 验 学时分配:6学时 掌握内容: 1.2检验的基本思想和用途 2.成组设计四格表资料2检验的计算及应用条件 3.配对设计四格表资料2检验 4.四格表资料的Fisher精确概率法的基本思想与检验步骤 5.行列表资料2 ...查看


  • 计数原理与排列组合
  • 11.1分类加法计数原理与分步乘法计数原理 考情分析 两个原理是解决排列.组合和概率的基础,贯穿始终,在高考中一般不单独考察,而是作为一种思想方法用在排列组合问题中.在本部分要注意分类讨论思想和补集思想. 基础知识 1.分类计数原理 完成一 ...查看


  • 数据结构填空题题库
  • 1. 线性结构中元素之间存在着(一对一)关系,树型结构中元素之间存在着(一对多)关系. 2. 评价数据结构的两条基本标准是:(存储需要量)和(运算的时间效率). 3. 算法的五个特性是指(有穷性/确定性.可行性.输入和输出). 4. 数据的 ...查看


  • 用一一列举的策略解决问题实录
  • "用一一列举的策略解决问题"教学设计 合肥市西园新村小学南区 汪小慧 教学内容:苏教版五上63-64页例1.例2.练一练,练习十一1-3题. 教学目标: 1.知识与能力目标:使学生能够根据解决问题的需要,运用" ...查看


  • 数据结构内容整理
  • 第一章 绪论 1. 数据结构:主要研究非数值计算问题中计算机的操作对象有哪些结构(逻辑结构) .这些结构在计算机中的表示及 其操作的定义和实现问题. 2. 逻辑结构:不考虑实现,仅看问题域中数据元素根据相互间的逻辑关系形成的结构称为数据结构 ...查看


  • HTML网页制作基础
  • HTML 网页制作基础 HTML 文档的结构 示例: 标题部分 我的第一个html 页面 元素出现在文档的开头部分.与之间的内容不会在浏览器的文档窗口中显示,但是其之间可以嵌入javascript 和css 样式等丰富网页的内容. 用来标记 ...查看


  • 高中数学二分法查找教案
  • 二分法查找教学设计 江苏省东台中学 朱世华 一.教学课题 第三章第三节<二分法查找>--算法与程序设计(新课标教科书:教育科学出版社) 二.教材及学者分析 <二分法查找>这部分知识在新课程数学必修1中已经涉及到,在前 ...查看


热门内容