数据结构查找作业
- 格式:doc
- 大小:18.50 KB
- 文档页数:2
《二分查找》作业一、选择题1. 二分查找算法要求待查找的数组必须是()。
A. 无序的B. 有序的C. 循环的D. 不确定答案:B解析:二分查找算法基于有序数组进行操作。
它通过不断将查找范围减半来定位目标元素,这要求数组必须是有序的。
2. 在二分查找中,如果查找的元素不存在于数组中,算法会返回()。
A. 第一个大于目标元素的值的位置B. 最后一个小于目标元素的值的位置C. -1或类似的标识符D. 数组的长度答案:C解析:当二分查找无法找到目标元素时,通常会返回一个特殊值(如-1)来表示查找失败。
这是因为二分查找算法无法确定目标元素应该插入的位置。
3. 二分查找的时间复杂度是()。
A. O(1)B. O(log n)C. O(n)D. O(n^2)答案:B解析:二分查找算法每次将查找范围减半,因此其时间复杂度是对数级别的,即O(log n)。
4. 对于长度为n的有序数组,二分查找最坏情况下的比较次数大约是()。
A. log₂(n)B. n/2C. nD. 2n答案:A解析:在最坏情况下,二分查找需要比较log₂(n)次才能找到目标元素或确定目标元素不存在。
这是因为每次比较都将查找范围减半。
5. 如果一个有序数组是升序排列的,使用二分查找算法来查找一个不存在的元素,比较次数可能会()。
A. 减少B. 不变C. 增加D. 不确定答案:A解析:虽然二分查找算法不直接利用数组的升序或降序排列特性,但在查找不存在的元素时,由于数组是有序的,一旦某个区间内的所有元素都大于或小于目标元素,就可以立即排除该区间,从而减少比较次数。
6. 在二分查找算法中,如果数组中存在多个相同的目标元素,那么()。
A. 只能找到一个目标元素B. 可以找到所有目标元素的位置C. 只能找到第一个目标元素的位置D. 只能找到最后一个目标元素的位置答案:C解析:二分查找算法在找到目标元素后会停止搜索,并返回该元素的位置。
如果数组中存在多个相同的目标元素,算法只会返回第一个找到的元素的位置。
题目:有一个长度为10的有序表,按折半查找对该表进行查找,在等概率情况下查找成功的平均比较次数为()。
选项A:26/10选项B:29/10选项C:29/9选项D:31/10答案:29/10题目:已知一个有序表为{11,22,33,44,55,66,77,88,99},则顺序查找元素55需要比较()次。
选项A:3选项B:6选项C:5选项D:4答案:5题目:有数据{53,30,37,12,45,24,96},从空二叉树开始逐个插入数据来形成二叉排序树,若希望高度最小,应该选择的序列是()。
选项A:45,24,53,12,37,96,30选项B:37,24,12,30,53,45,96选项C:30,24,12,37,45,96,53选项D:12,24,30,37,45,53,96答案:37,24,12,30,53,45,96题目:对于顺序存储的有序表{5,12,20,26,37,42,46,50,64},若采用折半查找,则查找元素26的比较次数是()。
选项A:5选项B:3选项C:6选项D:4答案:4题目:在所有的排序方法中,关键字比较的次数与记录初始排列秩序无关的是()。
选项A:直接插入排序选项B:希尔排序选项C:冒泡排序选项D:直接选择排序答案:直接选择排序题目:对线性表进行二分查找时,要求线性表必须()。
选项A:以顺序存储方式,且数据元素有序选项B:以链接存储方式选项C:以顺序存储方式选项D:以链接存储方式,且数据元素有序答案:以顺序存储方式,且数据元素有序题目:采用顺序查找方法查找长度为n的线性表时,每个元素的平均查找长度为()。
选项A:(n+1)/2选项B:n/2选项C:(n-1)/2选项D:n答案:(n+1)/2题目:从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。
将其放入已排序序列的正确的位置上,此方法称为()。
选项A:交换排序选项B:归并排序选项C:选择排序选项D:插入排序答案:插入排序题目:依次将每两个相邻的有序表合并成一个有序表的排序方法称为()。
第9章 查找答案一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找(线性查找) 。
2. 线性有序表(a 1,a 2,a 3,…,a 256)是从小到大排列的,对一个给定的值k ,用二分法检索表中与k 相等的元素,在查找不成功的情况下,最多需要检索 9 次。
设有100个结点,用二分法查找时,最大比较次数是 7 。
3. 假设在有序线性表a[20]上进行折半查找,则比较一次查找成功的结点数为1;比较两次查找成功的结点数为 2 ;比较四次查找成功的结点数为 8 ;平均查找长度为 3.7 。
解:显然,平均查找长度=O (log 2n )<5次(25)。
但具体是多少次,则不应当按照公式)1(log 12++=n nn ASL 来计算(即(21×log 221)/20=4.6次并不正确!)。
因为这是在假设n =2m-1的情况下推导出来的公式。
应当用穷举法罗列:全部元素的查找次数为=(1+2×2+4×3+8×4+5×5)=74; ASL =74/20=3.7 !!!4.折半查找有序表(4,6,12,20,28,38,50,70,88,100),若查找表中元素20,它将依次与表中元素 28,6,12,20 比较大小。
5. 在各种查找方法中,平均查找长度与结点个数n 无关的查找方法是 散列查找 。
6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。
7. 有一个表长为m 的散列表,初始状态为空,现将n (n<m )个不同的关键码插入到散列表中,解决冲突的方法是用线性探测法。
如果这n 个关键码的散列地址都相同,则探测的总次数是 n(n-1)/2=( 1+2+…+n-1) 。
(而任一元素查找次数 ≤n-1)二、单项选择题( B )1.在表长为n的链表中进行线性查找,它的平均查找长度为A. ASL=n; B. ASL=(n+1)/2;C. ASL=n +1; D. ASL≈log2(n+1)-1( A )2. 折半查找有序表(4,6,10,12,20,30,50,70,88,100)。
《数据结构》大作业
数据结构是计算机科学中构建可靠计算机系统所必需的基础知识。
它主要是用来处理
非常大的量级的数据,并为用户快速访问,高效的解决计算机问题。
由于中央处理机的特
点是高速而有效,起到了极大的性能提升。
数据结构有很多不同的结构,其中最重要的是线性结构和非线性结构。
线性结构又可
以分为数组、单向链表、双向链表和循环链表;非线性结构可以分为二叉树、二叉搜索树、B树、堆、红黑树和图。
在实际计算机程序中,数据结构一般被用来搜索和排序存储的数据,这些操作有助于
提高计算机的运行效率。
如果用户想要查找某一个数据,可以在合适的存储结构中找到它;如果用户希望把一系列数据按照某种顺序排列起来,也可以使用数据结构进行排序。
同时数据结构还可以用于实现数据结构间的转换,使得用户可以较为方便的获得数据。
它的运用,更加方便了计算机的工作,更加提高了计算机的性能。
总之,数据结构是计算机科学中重要的组成部分,它为计算机的工作提供了重要的基础,更加方便了用户的操作,也帮助用户更好地完成计算机系统中的各种工作和解决方案。
作业1. 线性表编程作业:1.将顺序表逆置,要求用最少的附加空间。
参考答案#include <>#include <>#include <>#define LIST_INIT_SIZE 100#define LISTINCREMENT 10#define TRUE 1#define FALSE 0#define OK 1#define ERROR 0#define INFEASIBLE -1#define OVERFLOW -2typedef int Status;typedef int ElemType;typedef struct{ ElemType *elem;int length;int listsize;}SqList;立单链表 ");printf("2.取元素值 ");printf("3.查找 \n");printf("4.插入 ");printf("5.删除 ");printf("6.显示\n");printf("7.删除大于mink且小于maxk的元素值 ");printf("8.就地升序排序\n");printf("9.就地逆置 ");printf("a.有序表插入 ");printf("q.退出\n");printf("\n请选择操作:");fflush(stdin);scanf("%c",&choice);switch(choice){case '1': printf("请输入单链表中结点个数:");scanf("%d",&n);Create_L2(L,n);break;case '2': printf("请输入元素位序:");scanf("%d",&i);GetElem_L(L,i,e);printf("元素值为:%d\n",e);break;case '3': printf("请输入要查找的元素:");scanf("%d",&e);if(dlbcz(L,e))printf("查找成功!");elseprintf("查找失败。
第九章 查找一、填空题1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找(线性查找) 。
2. 线性有序表(a 1,a 2,a 3,…,a 256)是从小到大排列的,对一个给定的值k ,用二分法检索表中与k 相等的元素,在查找不成功的情况下,最多需要检索 8 次。
设有100个结点,用二分法查找时,最大比较次数是 7 。
3. 假设在有序线性表a[1..20]上进行折半查找,则比较一次查找成功的结点数为1;比较两次查找成功的结点数为 2 ;比较四次查找成功的结点数为 8 ,其下标从小到大依次是1,3,6,8,11,13,16,19______,平均查找长度为 3.7 。
解:显然,平均查找长度=O (log 2n )<5次(25)。
但具体是多少次,则不应当按照公式)1(log 12++=n nn ASL 来计算(即(21×log 221)/20=4.6次并不正确!)。
因为这是在假设n =2m -1的情况下推导出来的公式。
应当用穷举法罗列:全部元素的查找次数为=(1+2×2+4×3+8×4+5×5)=74; ASL =74/20=3.7 !!! 4.折半查找有序表(4,6,12,20,28,38,50,70,88,100),若查找表中元素20,它将依次与表中元素 28,6,12,20 比较大小。
5. 在各种查找方法中,平均查找长度与结点个数n 无关的查找方法是 散列查找 。
6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。
7. 有一个表长为m 的散列表,初始状态为空,现将n (n<m )个不同的关键码插入到散列表中,解决冲突的方法是用线性探测法。
如果这n 个关键码的散列地址都相同,则探测的总次数是 n(n-1)/2=( 1+2+…+n-1) 。
(而任一元素查找次数 ≤n-1)8、设一哈希表表长M 为100 ,用除留余数法构造哈希函数,即H (K )=K MOD P (P<=M ), 为使函数具有较好性能,P 应选( 97 )9、在各种查找方法中,平均查找长度与结点个数无关的是哈希查找法 10、对线性表进行二分查找时,要求线性表必须以 顺序 方式存储,且结点按关键字有序排列。
数据结构作业——分块查找算法分块查找算法(Block Search Algorithm)是一种基于数据分块的查找算法,用于在一个有序数据集合中进行查找。
该算法把数据集合划分为若干个块(block),每个块中的数据是有序的。
通常情况下,每个块的数据量较小,比如每个块只包含100个数据。
块之间的数据是无序的。
在进行查找操作时,首先确定目标数据所在的块。
然后在确定的块中使用二分查找等方法进行查找。
这样一来,通过一次定位和一次块内查找操作,就可以实现整个数据集合的查找。
与传统的二分查找相比,分块查找的优势在于它减少了查找的次数。
首先,通过确定目标数据所在的块,剔除了绝大部分数据。
接下来,只需要在确定的块中进行查找,而不需要遍历整个数据集合。
因此,分块查找的时间复杂度较低。
在使用分块查找算法时,需要根据实际情况选择合适的块大小。
如果每个块的数据量过大,会导致块内查找的时间复杂度增加;如果每个块的数据量过小,可能会增加块定位的时间。
因此,需要权衡块内查找和块定位的效率,选择一个合适的块大小。
此外,分块查找还可以通过建立辅助索引来优化查找效率。
例如,可以在数据集合的每个块中保存一个最小值和一个最大值,作为块的索引。
这样,在进行查找时,可以先通过辅助索引定位到合适的块,再进行块内查找,进一步提高查找的效率。
总的来说,分块查找算法通过对数据进行分块,结合块定位和块内查找,实现了高效的查找操作。
它是一种满足实际应用需求的查找算法,常被用于静态和动态数据集合的查找任务。
同时,分块查找也为其他高级查找算法(如B树)提供了一种重要的基础。
1.设有序表为(1、23、34、55、56、57、77、87、99)请分别画出对给定值23,56,98进行折半查找的过程。
(并注明每次循环的各参数变量的结果)23的查找过程如下(其中括号表示当前查找区间,圆括号表示当前比较的关键字)
下标: 1 2 3 4 5 6 7 8 9
第一次比较:[ 1 23 34 55(56)57 77 87 99]
low=1
high=9
mid=5
第二次比较:[ 1(23)34 55] 56 57 77 87 99]
low=1
high=4
mid=2
56的查找过程如下(其中括号表示当前查找区间,圆括号表示当前比较的关键字)
下标: 1 2 3 4 5 6 7 8 9
第一次比较:[ 1 23 34 55(56)57 77 87 99]
low=1
high=9
mid=5
98的查找过程如下(其中括号表示当前查找区间,圆括号表示当前比较的关键字)
下标: 1 2 3 4 5 6 7 8 9
第一次比较:[ 1 23 34 55(56)57 77 87 99]
low=1
high=9
mid=5
第二次比较: 1 23 34 55 56 [57 (77) 87 99]
low=6
high=9
mid=7
第三次比较: 1 23 34 55 56 57 77[(87) 99]
low=8
high=9
mid=8
第四次比较: 1 23 34 55 56 57 77 87[(99)]
low=9
high=9
mid=9
第五次比较: 1 23 34 55 56 57 77 87 99
low=9
high=8
low>high 查找不成功。
2
设有一组关键字{19,01,23,14,55,20,84,27,68,11,10,77},采用哈希函数
H(key)=key % 13,采用开放地址法(开放定址法)的二次探测再散列方法解决冲突,试在0~18的散列地址空间中对该关键字序列构造哈希表。
解:依题意,n=19,二次探测再散列的下一地址计算公式为:其计算如下:
H(19)=19 % 13 =6 H(01)=01 % 13 =1 H(23)=23 % 13 =10 H(14)=14 % 13
=1(冲突) H(14)=(1+1*1) % 19 =2 H(55)=55 % 13 =3 H(20)=20 % 13 =7 H(84)=84 % 13 =6(冲突) H(84)=(6 + 1*1) % 19 =7(仍冲突) H(84)=(6 -
1*1) % 19 =5 H(27)=27 % 13 =1(冲突) H(27)=(1+1*1) % 19 =2(冲突) H(27)=(1-1*1) % 19 =0 H(68)=68 %13 =3(冲突) H(68)=(3+1*1) %19 =4 H(11)=11 % 13 =11 H(10)=10 % 13 =10(冲突) H(10)=(10+1*1) % 19 =11(仍
冲突) H(10)=(10-1*1)%19=9 H(77)=77 %13 =12 因此:各关键字的记录对应的地址分配如下:addr(27) = 0addr(01) = 1addr(14)
= 2addr(55) = 3addr(68) = 4addr(84) = 5addr(19) = 6addr(20) = 7addr(10)
= 9addr(23) = 10addr(11) = 11addr(77) = 12其他地址为空。