数据结构折半查找

#include

#include

#define OK 1

#define ERROR 0

int Search_Bin(int score[],int length,int key)

{

int low,high,mid;

low=1;

high=length;

while(low<=high)

{

mid=(low+high)/2;

if(score[mid]==key)

return mid;

else if(key

high=mid-1;

else if(key>score[mid])

low=mid+1;

}

return ERROR;

}

int main()

{

int score[11];

int length=10;

int key,index;

printf("创建查找表:\n");

for(int i=1;i<=length;i++)

{

scanf("%d",&score[i]);

}

printf("\n输入要查找的关键字\n");

scanf("%d",&key);

if(Search_Bin(score,length,key))

{

index=Search_Bin(score,length,key);

printf("\n要查找的%d 在表中的位置是%d \n",key,index);

}

else

printf("\n未查找到%d\n",key);

return OK;

}

《数据结构》数据结构查找

实验十数据结构查找 一、实验目的 1、掌握查找表、动态查找表、静态查找表和平均查找长度的概念。 2、掌握线性表中顺序查找和折半查找的方法。 3、学会哈希函数的构造方法，处理冲突的机制以及哈希表的查找。 二、实验预习 说明以下概念 1、顺序查找： 2、折半查找： 3、哈希函数： 4、冲突及处理： 三、实验内容和要求 1. 静态查找表技术 依据顺序查找算法和折半查找算法的特点，对下面的两个查找表选择一个合适的算法，设计出完整的C源程序。并完成问题： 查找表1 ： { 8 ，15 ，19 ，26 ，33 ，41 ，47 ，52 ，64 ，90 } ，查找key = 41 查找表2 ： {12 ， 67 ，29 ，15 ，62 ，35 ，33 ，89 ，48 ，20 } ，查找key =35 查找key=41的算法：顺序查找比较次数：5 查找key=35的算法：折半查找比较次数：5 ●顺序查找算法算法实现代码 ●#include ●#define N 10 ●int array[N]={12,76,29,15,62,35,33,89,48,20}; ●int search(int array[],int key) ●{ ● for(int i=0;i

数据结构实验——查找算法的实现

实验五 查找算法实现

1、实验目的 熟练掌握顺序查找、折半查找及二叉排序树、平衡二叉树上的查找、插入和删除的方法，比较它们的平均查找长度。 2、问题描述 查找表是数据处理的重要操作，试建立有100个结点的二叉排序树进行查找，然后用原数据建立AVL树，并比较两者的平均查找长度。 3、基本要求 （1）以链表作为存储结构，实现二叉排序树的建立、查找和删除。 （2）根据给定的数据建立平衡二叉树。 4、测试数据 随即生成 5、源程序 #include<> #include<> #include<> #define EQ(a,b) ((a)==(b)) #define LT(a,b) ((a)<(b)) #define LQ(a,b) ((a)>(b)) typedef int Keytype; typedef struct { Keytype key; //关键字域 }ElemType; typedef struct BSTnode { ElemType data; int bf; struct BSTnode *lchild,*rchild; }BSTnode,*BSTree; void InitBSTree(BSTree &T) {T=NULL; } void R_Rotate(BSTree &p) {BSTnode *lc; lc=p->lchild; p->lchild=lc->rchild; lc->rchild=p; p=lc; } void L_Rotate(BSTree &p) {BSTnode *rc; rc=p->rchild; p->rchild=rc->lchild;

数据结构实验七 查找

实验七查找 一、实验目的 1. 掌握查找的不同方法，并能用高级语言实现查找算法； 2. 熟练掌握二叉排序树的构造和查找方法。 3. 熟练掌握静态查找表及哈希表查找方法。 二、实验内容 设计一个读入一串整数，然后构造二叉排序树，进行查找。 三、实验步骤 1. 从空的二叉树开始，每输入一个结点数据，就建立一个新结点插入到当前已生成的二叉排序树中。 2. 在二叉排序树中查找某一结点。 3.用其它查找算法进行排序（课后自己做）。 四、实现提示 1. 定义结构 typedef struct node { int key; int other; struct node *lchild, *rchild; } bstnode; void inorder ( t ) { if (t!=Null) { inorder(t→lchild); printf(“%4d”, t→key); inorder(t→rchild); } } bstnode *insertbst(t, s) bstnode *s, *t; { bstnode *f, *p; p=t;

while(p!=Null) { f=p; if (s→key= =p→key) return t; if (s→key

二叉排序树 折半查找 顺序查找 数据结构

二叉排序树 #include "c1.h" #include "stdio.h" #include "stdlib.h" typedef int KeyType; typedef struct node{ KeyType key; struct node *lchild,*rchild; }BiTNode,*BiTree; void InsertBST(BiTree &bst,KeyType key) { BiTNode *t; if(bst==NULL) { t=(BiTree)malloc(sizeof(BiTNode)); t->key=key; t->lchild=NULL; t->rchild=NULL; bst=t; } else if(keykey) InsertBST(bst->lchild,key); else if(key>bst->key) InsertBST(bst->rchild,key); } void CreateBST(BiTree &bst) { int i; int n; KeyType key=0; bst=NULL; printf("请输入二叉排序树中元素的个数："); scanf("%d",&n); for(i=1;i<=n;i++) { printf("请输入二叉排序数中的第%d个元素：",i); scanf("%d",&key); InsertBST(bst,key); }

} BiTree SearchBST(BiTree bst,KeyType key) { if(!bst) return NULL; else if(bst->key==key) return bst; else if(keykey) return SearchBST(bst->lchild,key); else return SearchBST(bst->rchild,key); } int main() { BiTree bst; CreateBST(bst); KeyType temp; printf("请输入你要查找的元素："); scanf("%d",&temp); BiTree T; T=SearchBST(bst,temp); if(T==NULL) printf("\n\n查找失败\n"); else { printf("\n\n查找成功\n"); printf("二叉排序树中查到的元素为：%d\n",T->key); } } 折半查找和顺序查找 #include "stdio.h" #include "stdlib.h" #include "c1.h" #define N 20

数据结构查找习题及答案

第九章查找 一、选择题 1.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 2. 下面关于二分查找的叙述正确的是 ( ) A. 表必须有序，表可以顺序方式存储，也可以链表方式存储 C. 表必须有序，而且只能从小到大排列 B. 表必须有序且表中数据必须是整型，实型或字符型 D. 表必须有序，且表只能以顺序方式存储 3. 用二分（对半）查找表的元素的速度比用顺序法( ) A．必然快 B. 必然慢 C. 相等 D. 不能确定 4. 具有12个关键字的有序表，折半查找的平均查找长度（） A. 3.1 B. 4 C. 2.5 D. 5 5．当采用分块查找时，数据的组织方式为 ( ) A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 6. 二叉查找树的查找效率与二叉树的( （1）)有关, 在 (（2）)时其查找效率最低 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 7. 对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找失 败,它们的平均查找长度是((1)) ,对于查找成功,他们的平均查找长度是((2))供选择的答案: A. 相同的 B.不同的 9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( ) A．（100，80， 90， 60， 120，110，130） B.（100，120，110，130，80， 60， 90） C.（100，60， 80， 90， 120，110，130） D. (100，80， 60， 90， 120，130，110) 10. 在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A,并已知A的左孩子的平衡因子为0右孩子的平衡因子为1,则应作( ) 型调整以使其平衡。 A. LL B. LR C. RL D. RR 11. 下面关于m阶B-树说法正确的是( ) ①每个结点至少有两棵非空子树；②树中每个结点至多有m一1个关键字; ③所有叶子在同一层上; ④当插入一个数据项引起B树结点分裂后，树长高一层。 A．①②③ B. ②③ C. ②③④ D. ③ 12. m阶B-树是一棵( ) A. m叉排序树 B. m叉平衡排序树 C. m-1叉平衡排序树 D. m+1叉平衡排序树 15. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链 地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（）个记录。 A．1 B. 2 C. 3 D. 4 16. 关于哈希查找说法不正确的有几个( ) （1）采用链地址法解决冲突时，查找一个元素的时间是相同的 （2）采用链地址法解决冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的 （3）用链地址法解决冲突易引起聚集现象 （4）再哈希法不易产生聚集

数据结构查找实验心得体会

数据结构查找实验心得体会篇一：数据结构实训心得体会 这次课程设计的心得体会通过实习我的收获如下1、巩固和加深了对数据结构的理解，提高 综合运用本课程所学知识的能力。2、培养了我选用参考书，查阅手册及文献资料的能力。培 养独立思考，深入研究，分析问题、解决问题的能力。 3、通过实际编译系统的分析设计、编 程调试，掌握应用软件的分析方法和工程设计方法。4、通过课程设计，培养了我严肃认真的 工作作风，逐步建立正确的生产观念、经济观念和全局观念。从刚开始得觉得很难，到最后 把这个做出来，付出了很多，也得到了很多，以前总以为自己对编程的地方还不行，现在， 才发现只要认真做，没有什么不可能。编程时要认真仔细，出现错误要及时找出并改正，（其中对英语的要求也体现出来了，因 为它说明错误的时候都是英语）遇到问题要去查相关的资料。反复的调试程序，最好是多找 几个同学来对你的程序进行调试并听其对你的程序的建议，在他们不知道程序怎么写的时候 完全以一个用户的身份来用对你的用户界面做一些建

议，正所谓当局者迷旁观者清，把各个 注意的问题要想到；同时要形成自己的编写程序与调试程序的风格，从每个细节出发，不放 过每个知识点，注意与理论的联系和理论与实践的差别。另外，要注意符号的使用，注意对 字符处理，特别是对指针的使用很容易出错且调试过程是不会报错的，那么我们要始终注意 指针的初始化不管它怎么用以免不必要麻烦。通过近两周的学习与实践，体验了一下离开课堂的学习，也可以理解为一次实践与理论 的很好的连接。特别是本组所做的题目都是课堂上所讲的例子，在实行之的过程中并不是那 么容易事让人有一种纸上谈兵的体会，正所谓纸上得来终觉浅绝知此事要躬行。实训过程中 让我们对懂得的知识做了进一步深入了解，让我们的理解与记忆更深刻，对不懂的知识与不 清楚的东西也做了一定的了解，也形成了一定的个人做事风格。通过这次课程设计，让我对一个程序的数据结构有更全面更进一步的认识，根据不同的 需求，采用不同的数据存储方式，不一定要用栈，二叉树等高级类型，有时用基本的一维数 组，只要运用得当，也能达到相同的效果，甚至更佳，

数据结构 第九章 查找 作业及答案

第九章查找 一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是。 2. 线性有序表（a 1，a 2 ，a 3 ，…，a 256 )是从小到大排列的，对一个给定的值k，用二分法检索 表中与k相等的元素，在查找不成功的情况下，最多需要检索次。设有100个结点，用二分法查找时，最大比较次数是。 3. 假设在有序线性表a[1..20]上进行折半查找，则比较一次查找成功的结点数为1；比较两 次查找成功的结点数为 2 ；比较四次查找成功的结点数为 ,其下标从小到大依次是 ____，平均查找长度为。 4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素比较大小。 5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。 6. 散列法存储的基本思想是由决定数据的存储地址。 7. 有一个表长为m的散列表，初始状态为空，现将n（n

数据结构实验五-查找与排序的实现

实验报告 课程名称数据结构实验名称查找与排序的实现 系别专业班级指导教师11 学号姓名实验日期实验成绩 一、实验目的 (1)掌握交换排序算法（冒泡排序）的基本思想； (2)掌握交换排序算法（冒泡排序）的实现方法； (3)掌握折半查找算法的基本思想； (4)掌握折半查找算法的实现方法； 二、实验内容 1.对同一组数据分别进行冒泡排序，输出排序结果。要求： 1)设计三种输入数据序列：正序、反序、无序 2)修改程序： a)将序列采用手工输入的方式输入 b)增加记录比较次数、移动次数的变量并输出其值，分析三种序列状态的算法时间复杂 性 2.对给定的有序查找集合，通过折半查找与给定值k相等的元素。 3.在冒泡算法中若设置一个变量lastExchangeIndex来标记每趟排序时经过交换的最后位置， 算法如何改进？ 三、设计与编码 1.本实验用到的理论知识 2.算法设计

3.编码 package sort_search;

import java.util.Scanner; public class Sort_Search { //冒泡排序算法 public void BubbleSort(int r[]){ int temp; int count=0,move=0; boolean flag=true; for(int i=1;ir[j+1]){ temp=r[j]; r[j]=r[j+1]; r[j+1]=temp; move++; flag=true; } } } System.out.println("排序后的数组为："); for(int i=0;ikey){

数据结构查找习题及答案

第9章查找 一、单选题 1.对一棵二叉搜索树按（）遍历，可得到结点值从小到大的排列序列。 A. 先序 B. 中序 C. 后序 D. 层次 2.从具有n个结点的二叉搜索树中查找一个元素时，在平均情况下的时间复杂度大致为（）。 A. O(n) B. O(1) C. O(logn) D. O(n2) 3.从具有n个结点的二叉搜索树中查找一个元素时，在最坏情况下的时间复杂度为（）。 A. O(n) B. O(1) C. O(logn) D. O(n2) 4.在二叉搜索树中插入一个结点的时间复杂度为（）。 A. O(1) B. O(n) C. O(logn) D. O(n2) 5.分别以下列序列构造二叉搜索树，与用其它三个序列所构造的结果不同的是（）。 A．（100，80，90，60，120，110，130） B.（100，120，110，130，80，60，90） C.（100，60，80，90，120，110，130） D.（100，80，60，90，120，130，110） 6.在一棵AVL树中，每个结点的平衡因子的取值范围是（）。 A. -1~1 B. -2~2 C. 1~2 D. 0~1 7.根据一组关键字（56，42，50，64，48）依次插入结点生成一棵A VL树，当插入到值 为（）的结点时需要进行旋转调整。 A. 42 B. 50 C. 64 D. 48 8.深度为4的A VL树至少有（）个结点。 A．9 B.8 C.7 D.6 9.一棵深度为k的A VL树，其每个分支结点的平衡因子均为0，则该平衡二叉树共有（） 个结点。 A.2k-1-1 B.2k-1+1 C.2k-1 D.2k 10.在A VL树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左 孩子的平衡因子为0，右孩子的平衡因子为1，则应作（）型调整以使其平衡。 A. LL B. LR C. RL D. RR 二、判断题

数据结构查找算法课程设计

存档编号： 西安******** 课程设计说明书 设计题目： 查找算法性能分析 系别：计算机学院 专业：计算机科学 班级：计科*** 姓名：王*** （共页） 2015年01月07 日

***** 计算机科学专业课程设计任务书 姓名：*** 班级：计科**** 学号：**** 指导教师：**** 发题日期：2015-01-05 完成日期：2015-01-09 一需求分析

1.1问题描述 查找又称检索，是指在某种数据结构中找出满足给定条件的元素。查找是一种十分有用的操作。而查找也有内外之分，若整个查找过程只在内存中进行称为内查找；若查找过程中需要访问外存，则称为外查找，若在查找的同时对表做修改运算（插入或删除），则相应的表成为动态查找表，反之称为静态查找表。 由于查找运算的主要运算是关键字的比较，所以通常把查找过程中对关键字的平均比较次数（也叫平均查找长度）作为一个查找算法效率优劣的标准。 平均查找程度ASL定义为： ASL=∑PiCi（i从1到n） 其中Pi代表查找第i个元素的概率，一般认为每个元素的查找概率相等，Ci代表找到第i个元素所需要比较的次数。 查找算法有顺序查找、折半查找、索引查找、二叉树查找和散列查找（又叫哈希查找），它们的性能各有千秋，对数据的存储结构要求也不同，譬如在顺序查找中对表的结果没有严格的要求，无论用顺序表或链式表存储元素都可以查找成功；折半查找要求则是需要顺序表；索引表则需要建立索引表；动态查找需要的树表查找则需要建立建立相应的二叉树链表；哈希查找相应的需要建立一个哈希表。 1.2基本要求 （1）输入的形式和输入值的范围； 在设计查找算法性能分析的过程中，我们调用产生随机数函数： srand((int)time(0)); 产生N个随机数。 注：折半查找中需要对产生的随机数进行排序，需要进行排序后再进行输入，N<50; （2）输出形式； 查找算法分析过程中，只要对查找算法稍作修改就可以利用平均查找

数据结构实验报告七查找、

云南大学软件学院数据结构实验报告 （本实验项目方案受“教育部人才培养模式创新实验区（X3108005）”项目资助）实验难度： A □ B □ C □ 学期：2010秋季学期 任课教师: 实验题目: 查找算法设计与实现 姓名: 王辉 学号: 20091120154 电子邮件: 完成提交时间： 2010 年 12 月 27 日

云南大学软件学院2010学年秋季学期 《数据结构实验》成绩考核表 学号：姓名：本人承担角色： 综合得分：（满分100分） 指导教师：年月日（注：此表在难度为C时使用，每个成员一份。）

（下面的内容由学生填写，格式统一为，字体: 楷体, 行距: 固定行距18，字号: 小四，个人报告按下面每一项的百分比打分。难度A满分70分，难度B满分90分）一、【实验构思（Conceive）】(10%) 1 哈希表查找。根据全年级学生的姓名，构造一个哈希表，选择适当的哈希函数和解决冲突的方法，设计并实现插入、删除和查找算法。 熟悉各种查找算法的思想。 2、掌握查找的实现过程。 3、学会在不同情况下运用不同结构和算法求解问题。 4 把每个学生的信息放在结构体中： typedef struct //记录 { NA name; NA tel; NA add; }Record; 5 void getin(Record* a)函数依次输入学生信息 6 人名折叠处理，先将用户名进行折叠处理折叠处理后的数，用除留余数法构造哈希函数，并返回模值。并采用二次探测再散列法解决冲突。 7姓名以汉语拼音形式，待填入哈希表的人名约30个，自行设计哈希函数，用线性探测再散列法或链地址法处理冲突；在查找的过程中给出比较的次数。完成按姓名查询的操作。将初始班级的通讯录信息存入文件。 二、【实验设计(Design)】(20%) （本部分应包括：抽象数据类型的功能规格说明、主程序模块、各子程序模块的伪码说明，主程序模块与各子程序模块间的调用关系） 1抽象数据类型的功能规格说明和结构体： #include

数据结构——查找,顺序查找,折半查找

实验五查找的应用 一、实验目的： 1、掌握各种查找方法及适用场合，并能在解决实际问题时灵活应用。 2、增强上机编程调试能力。 二、问题描述 1.分别利用顺序查找和折半查找方法完成查找。 有序表（3,4,5,7,24,30,42,54,63,72,87,95） 输入示例： 请输入查找元素：52 输出示例： 顺序查找： 第一次比较元素95 第二次比较元素87 …….. 查找成功，i=**/查找失败 折半查找： 第一次比较元素30 第二次比较元素63 ….. 2.利用序列（12,7,17,11,16,2,13,9,21,4）建立二叉排序树，并完成指定元素的查 询。 输入输出示例同题1的要求。 三、数据结构设计（选用的数据逻辑结构和存储结构实现形式说明） （1）逻辑结构设计 顺序查找和折半查找采用线性表的结构，二叉排序树的查找则是建立一棵二叉树，采用的非线性逻辑结构。 （2）存储结构设计 采用顺序存储的结构，开辟一块空间用于存放元素。

（3）存储结构形式说明 分别建立查找关键字，顺序表数据和二叉树数据的结构体进行存储数据 四、算法设计 （1）算法列表（说明各个函数的名称，作用，完成什么操作） 序号 名称 函数表示符 操作说明 1 顺序查找 Search_Seq 在顺序表中顺序查找关键字的数据元素 2 折半查找 Search_Bin 在顺序表中折半查找关键字的数据元素 3 初始化 Init 对顺序表进行初始化，并输入元素 4 树初始化 CreateBST 创建一棵二叉排序树 5 插入 InsertBST 将输入元素插入到二叉排序树中 6 查找 SearchBST 在根指针所指二叉排序树中递归查找关键字 数据元素 （2）各函数间调用关系（画出函数之间调用关系） typedef struct { ElemType *R; int length; }SSTable; typedef struct BSTNode{ Elem data; //结点数据域 BSTNode *lchild,*rchild; //左右孩子指针 }BSTNode,*BSTree; typedef struct Elem{ int key; }Elem; typedef struct { int key;//关键字域 }ElemType;

数据结构经典算法 C语言版

//插入排序法 void InsertSort() { int s[100]; int n,m,j,i=0,temp1,temp2; printf("请输入待排序的元素个数："); scanf("%d",&n); printf("请输入原序列："); for (i=0; is[n-1]); s[n]=m; for (i=0; im) { temp1=s[i]; s[i]=m; for (j=i+1; j

//堆排序 static a[8] = {0,25,4,36,1,60,10,58,}; int count=1; void adjust(int i,int n) { int j,k,r,done=0; k = r = a[i]; j = 2*i; while((j<=n)&&(done==0)) { if(j=a[j]) done = 1; else { a[j/2] = a[j]; j = 2* j; } } a[j/2] = r; } void heap(int n) { int i,j,t; for(i =n/2;i>0;i--) adjust(i,n); printf("\n初始化成堆===> "); for(i = 1;i < 8;i++) printf("%5d",a[i]); for(i = n-1;i>0;i--) { t = a[i+1]; a[i+1] = a[1]; a[1] = t; adjust(1,i); printf("\n第%2d步操作结果===>",count++); for(j = 1;j<8;j++) printf("%5d",a[j]); } }

数据结构——折半查找源代码

数据结构折半查找源代码 源代码： 折半查找： #include//cout,cin #include"process.h"//exit() #include"stdio.h"//EOF,NULL typedef int T; //定义关键字的类型,这里就以整形来处理 //查找表类定义 template struct Node { T key; //关键字域 /* ........ //其他域,可以自己根据需要添加 */ }; template class SSearch { private: Node *ST; int len;//表长 public: SSearch();// ~SSearch();//析构函数，删除表空间 void Create(int n); //创建时根据用户实际需求,再为相应的数据元素赋值void Display(); //输出静态表中的数据元素 int SeSearch(T key); //从表中最后一个元素开始顺序查找 void Ascendsort(); //升序排列 int BiSearch_1(T key);//折半查找，非递归算法 int BiSearch_2(T key);//折半查找，递归算法 int BiSearch2(int x,int y,T key); }; template SSearch::SSearch() {// ST=NULL; len=0;

} template SSearch::~SSearch() {//释放表空间 delete [] ST; len=0; } template void SSearch::Create(int n) { len=n; ST=new Node[len]; Node e; int i=0; cout<<"输入"<>e.key; ST[i]=e; i++; } } template int SSearch::SeSearch(T key) {//从表中最后一个元素开始顺序查找，若找到，返回位序，否则，返回-1 for(int i=len-1;i>=0;i--) if(ST[i].key==key) { cout<<"查找成功!位居第"< void SSearch::Ascendsort() { T t;

数据结构-查找介绍

第八章查找一、填空题 1.线性有序表（a 1，a 2 ，a 3 ，…，a 256 )是从小到大排列的，对一个给定的值k，用二分法检索 表中与k相等的元素，在查找不成功的情况下，最多需要检索次。 设有100个结点，用二分法查找时，最大比较次数是。 2．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素比较大小。 3. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。 4、对线性表进行二分查找时，要求线性表必须以方式存储，且结点按关键字 排列。 5．顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为_ __次；当使用监视哨时，若查找失败，则比较关键字的次数为__ 。 6．在有序表A[1..12]中，采用二分查找算法查等于A[12]的元素，所比较的元素下标依次为____ _____。 7. 在有序表A[1..20]中，按二分查找方法进行查找，查找长度为5的元素个数是_ 8. 已知二叉排序树的左右子树均不为空，则_______上所有结点的值均小于它的根结点值，________上所有结点的值均大于它的根结点的值。 9、中序遍历二叉排序树得到的序列是序列（填有序或无序）。 10、从有序表(10，16，25，40，61，28，80，93)中依次二分查找40和61元素时，其查找长度分别为和。

二、单项选择题 （）1．在表长为ｎ的链表中进行顺序查找，它的平均查找长度为 Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２; （ｎ＋１）－１ Ｃ. ＡＳＬ＝n＋１; Ｄ. ＡＳＬ≈ｌｏｇ ２ （）2．折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中比较大小，查找结果是失败。 A．20，70，30，50 B．30，88，70，50 C．20，50 D．30，88，50 （）3．对22个记录的有序表作折半查找，当查找失败时，至少需要比较次关键字。 A．3 B．4 C．5 D． 6 （）4. 链表适用于查找 A．顺序 B．二分法 C．顺序，也能二分法 D．随机 （）5. 折半搜索与二叉搜索树的时间性能。 A. 相同 B. 完全不同 n） C. 有时不相同 D. 数量级都是O（log 2 （）6．散列表的地址区间为0-17,散列函数为H(K)=K mod 17。采用线性探测法处理冲突，并将关键字序列26，25，72，38，8，18，59依次存储到散列表中。元素59存放在散列表中的地址是。 A． 8 B. 9 C. 10 D. 11 ( )7. 当采用分快查找时，数据的组织方式为 A．数据分成若干块，每块内数据有序

《数据结构》实验报告查找

实验四——查找 一、实验目的 1.掌握顺序表的查找方法，尤其是折半查找方法； 2.掌握二叉排序树的查找算法。 二、实验内容 1.建立一个顺序表，用顺序查找的方法对其实施查找； 2.建立一个有序表，用折半查找的方法对其实施查找； 3.建立一个二叉排序树，根据给定值对其实施查找； 4.对同一组数据，试用三种方法查找某一相同数据，并尝试进行性能分析。 三、实验预习内容 实验一包括的函数有：typedef struct ，创建函数void create(seqlist & L)，输出函数void print(seqlist L)，顺序查找int find(seqlist L,int number)，折半查找int halffind(seqlist L,int number) 主函数main(). 实验二包括的函数有：结构体typedef struct，插入函数void insert(bnode * & T,bnode * S)，void insert1(bnode * & T)，创建函数void create(bnode * & T)，查找函数bnode * search(bnode * T,int number)，主函数main(). 四、上机实验 实验一： 1.实验源程序。 #include<> #define N 80 typedef struct { int number; umber; for(i=1;[i].number!=0;) { cin>>[i].name>>[i].sex>>[i].age; ++; cout<>[++i].number; } } umber<<"\t"<<[i].name<<"\t"<<[i].sex<<"\t"<<[i].age<

数据结构折半查找算法

#include #include #define MAX_LENGTH 100 typedef int KeyType; typedef struct { int key; }ElemType; typedef struct { ElemType elem[MAX_LENGTH]; // 0号单元空出int length; }SSTable; int Search_Bin(SSTable ST,KeyType key) { int low,high,mid; low = 1;high = ST.length; while(low <=high) { mid = (low+high)/2; if(key ==ST.elem[mid].key) return mid; else if(key

for(i=1;i<=ST.length;i++) { printf("please input ST.elem:"); scanf("%d",&ST.elem[i]); } printf("please input keyword:"); scanf("%d",&key); result=Search_Bin(ST,key); if(result==0) printf("Don't find\n"); else printf("Find the key,the position is %d\n",result); }

大数据结构-实验8查找地算法

8.1 实现顺序查找的算法 一，实验目的 1.熟悉掌握各种查找方法，深刻理解各种查找算法及其执行的过程； 2.学会分析各种查找算法的性能。 二，实验内容 8.1 实现顺序查找的算法 编写一个程序，输出在顺序表{3,6,2,10,1,8,5,7,4,9}中采用顺序查找法查找 关键字5的结果。 8.2 实现折半查找算法 编写一个程序，输出在顺序表{1,2,3,4,5,6,7,8,9,10}中采用折半查找方法查 找关键字9的结果。要求：（1）用非递归方法；（2）用递归方法。 8.3 实现二叉排序树的基本运算 编写一个程序实现二叉排序树的基本运算，并在此基础上完成如下功能： （1）由{4,9,0,1,8，6,3,5,2,7}创建一个二叉排序树bt； （2）判断bt是否为一棵二叉排序树（提示：在遍历过程中检查是否符合二叉 排序树定义）； （3）采用非递归方法查找关键字为6的结点，并输出其查找路径（提示：查找过程中保留经过的结点信息，找到后顺序输出之）。 8.4 实现哈希表的相关运算 编写一个程序，实现哈希表的相关运算，并在此基础上完成如下功能： （1）建立{16,74,60,43,54,90,46,31,29,88,77}哈希表A[0…12]，哈希函数为H(k)=key % 11，并采用线性探测法解决冲突。输出哈希表； （2）在上述哈希表中查找关键字为29的记录； （3）在上述哈希表中删除关键字为77的记录，再将其插入，然后输出哈希表。 要求：输出格式 哈希地址：0 1 2 (12) 关键字值：…………………… 三，源代码及结果截图 8.1 //实现顺序查找的算法 #include #define MAXL 100 //定义表中最多记录个数 typedef int KeyType; typedef int InfoType; typedef struct { KeyType key; //KeyType为关键字的数据类型 InfoType data; //其他数据 } NodeType;

数据结构实验一 实验报告

班级: 姓名: 学号: 实验一线性表的基本操作 一、实验目的 1、掌握线性表的定义; 2、掌握线性表的基本操作,如建立、查找、插入与删除等。 二、实验内容 定义一个包含学生信息(学号,姓名,成绩)的顺序表与链表(二选一),使其具有如下功能: (1) 根据指定学生个数,逐个输入学生信息; (2) 逐个显示学生表中所有学生的相关信息; (3) 根据姓名进行查找,返回此学生的学号与成绩; (4) 根据指定的位置可返回相应的学生信息(学号,姓名,成绩); (5) 给定一个学生信息,插入到表中指定的位置; (6) 删除指定位置的学生记录; (7) 统计表中学生个数。 三、实验环境 Visual C++ 四、程序分析与实验结果 #include #include #include #include #define OK 1 #define ERROR 0 #define OVERFLOW -2 typedef int Status; // 定义函数返回值类型 typedef struct

{ char num[10]; // 学号 char name[20]; // 姓名 double grade; // 成绩 }student; typedef student ElemType; typedef struct LNode { ElemType data; // 数据域 struct LNode *next; //指针域 }LNode,*LinkList; Status InitList(LinkList &L) // 构造空链表L { L=(struct LNode*)malloc(sizeof(struct LNode)); L->next=NULL; return OK; } Status GetElem(LinkList L,int i,ElemType &e) // 访问链表,找到i位置的数据域,返回给 e { LinkList p; p=L->next;