数据结构-查找2(详解)

这篇具有很好参考价值的文章主要介绍了数据结构-查找2(详解)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

1.在一棵由包含 4、5、6 等等一系列整数结点构成的二叉搜索树中,如果结点 4 和 6 在树的同一层,那么可以断定结点 5 一定是结点 4 和 6 的父亲结点。 
错    解析:
        反例
设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

 2.二叉搜索树的查找和折半查找的时间复杂度相同。

错   解析:不一定相同。二叉排序树不一定是平衡树,它是只要求了左右子树与根结点存在大小关系,但是对左右子树之间没有层次差异的约束,因此通过二叉排序树进行查找不一定能够满足logn的,例如一棵只有多层左子树的二叉排序树。只有是一棵平衡的二叉排序树时,其查找时间性能才和折半查找类似。
 

3.把数组中元素按某种顺序排列的过程叫做查找 。
错  解析:把数组中元素按某种顺序排列的过程叫做排序;

4.将 N 个数据按照从小到大顺序组织存放在一个单向链表中。如果采用二分查找,那么查找的平均时间复杂度是 O(logN)。
错  解析:数组二分查找的平均复杂度是O(logN)没有错,但是二分查找是不可以用链表存储的。因为数据在链表中的位置只能通过从头到尾的顺序检索得到,即使是有序的,要操作其中的某个数据也必须从头开始。这和数组有本质的不同。数组中的元素是通过下标来确定的,只要你知道了下标,就可以直接存储整个元素,比如a[5],是直接的。链表没有这个,所以,折半查找只能在数组上进行。
5.由顺序表和单链表表示的有序表均可使用二分查找法来提高查找速度。
错  解析:二分查找是不可以用链表存储;

6.将元素序列{18,23,11,20,2,7,27,33,42,15}按顺序插入一个初始为空的、大小为11的散列表中。散列函数为:H(Key)=Key%11,采用线性探测法处理冲突。问:当第一次发现有冲突时,散列表的装填因子大约是多少?
A. 0.27
B. 0.45
C. 0.64
D. 0.73
答案 B 解析:
18%11=7
23%11=1
11%11=0
20%11=9
2%11=2
7%11=7+1=8(第一次冲突)
装填因子=5/11=0.45(装填因子=表中填入的记录数/散列表的长度)

7.给定散列表大小为 11,散列函数为 H(Key)=Key%11。采用平方探测法处理冲突:设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法, 将关键字序列{ 6,25,39,61 }依次插入到散列表中。那么元素 61 存放在散列表中的位置是:
A. 5
B. 6
C. 7
D. 8
答案 A 解析:
6%11=6
25%11=3
39%11=6,(6+1)%11=7
61%11=6  (6+1)%11=7  (6-1)%11=5

 设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

8.现有长度为 7、初始为空的散列表 HT,散列函数 H(k)=k%7,用线性探测再散列法解决冲突。将关键字 22, 43, 15 依次插入到 HT 后,查找成功的平均查找长度是:
B. 1.6
C. 2
D. 3
答案 C 解析:

0    1    2    3    4    5    6
     22  43  15            
查找22,(探测次数)长度为1;
查找43,(探测次数)长度为2;
查找15,(探测次数)长度为3;
总长度(3个关键字)为3;平均查找长度=(3+2+1)/3=2;

9.给定散列表大小为11,散列函数为H(Key)=Key%11。按照线性探测冲突解决策略连续插入散列值相同的4个元素。问:此时该散列表的平均不成功查找次数是多少?
A.1
B.4/11
C.21/11
D.不确定

答案:C

分析:
区别概念平均成功查找次数和平均不成功查找次数。
平均成功查找次数=每个关键词比较次数之和÷关键词的个数
平均不成功查找次数=每个位置不成功时的比较次数之和÷表长
(所谓每个位置不成功时的比较次数就是在除余位置内,每个位置到第一个为空的比较次数,比如此题表长为11,散列函数为Key%11,除余的是11,那么除余位置就是0—10;如果表长为15,但散列函数为Key%13,那么除余位置就是0—12)
明确概念后做题:
连续插入散列值相同的4个元素,我们就假设它的散列值都为0,那么插入后的位置:

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法其中位置0到第一个为空的位置4的比较次数为5,其余的位置以此类推。
平均不成功查找次数=(5+4+3+2+1+1+1+1+1+1+1)÷ 11 = 21/11
故选C

10. 给定散列表大小为 11,散列函数为 H(Key)=Key%11。按照线性探测冲突解决策略连续插入散列值相同的 5 个元素。问:此时该散列表的平均不成功查找次数是多少?(A)
A. 26/11
B. 5/11
C. 1
D. 不确定
答案 A 解析:
(6+6+5+4+3+2)/11=26/11  (同上题)

11.采用线性探测法解决冲突时所产生的一系列后继散列地址:
A. 必须大于等于原散列地址
B. 必须小于等于原散列地址
C. 可以大于或小于但不等于原散列地址
D. 对地址在何处没有限制
答案 C 解析:循环后会在原散列地址前。

12.已知一个长度为 16 的顺序表 L,其元素按关键字有序排列。若采用二分查找法查找一个 L中不存在的元素,则关键字的比较次数最多是:
A. 4
B. 5
C. 6
D. 7

答案 B (公式直接得到)

13.下列二叉树中,可能成为折半查找判定树(不含外部结点)的是: (A)

A设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

B设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法


C设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

D设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法
答案 A 解析:
折半查找树的特点就在于其中序遍历是一个升序序列,因此相比于在以往的序列中进行二分查找,折半查找二叉树的优点在于不用自己去找中点,而是直接将要查找的关键字与根节点相比,小的话再和根节点的左子节点比较,大的话则是和根节点的右子节点比较。
而对于这道题的解题思路就在于向上或向下取整的问题,也就是说如果升序序列是偶数个,那么中点应该偏左多右少还是左少右多。但是很显然应该进行一个统一,
像B和C选项中间的对称部分明显就是选择了不同的策略。D则由根节点左子树4个节点而点右子树5个节点可以确定用的是向下取整策略,但是我们再看它的左子节点在左子树中对应的中点左边2个数,右边一个数,明显是向上取整策略,策略没有统一,所以是错的。

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

针对偶数要采用向上向下,而是奇数时则不用 奇数就满足了,因为如(1+3)/2=2可以除整

14.设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与 K 相等的元素,比较的次数分别是 S 和 B,在查找不成功的情况下,S 和 B 的关系是 。
A. S = B
B. S < B
C. S > B
D. S >= B
答案 D 解析:
设线性表长度为N
S=N;
设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法
当N=2时,S=B;
当N>2时,S>B;

15.在有 n(n>1000)个元素的升序数组 A 中查找关键字 x。查找算法的伪代码如下所示:

k = 0;
while ( k<n 且 A[k]<x ) k = k+3;
if ( k<n 且 A[k]==x ) 查找成功;
else if ( k-1<n 且 A[k-1]==x ) 查找成功;
 else if ( k-2<n 且 A[k-2]==x ) 查找成功;
 else 查找失败;


本算法与二分查找(折半查找)算法相比,有可能具有更少比较次数的情形是
A. 当 x 不在数组中
B. 当 x 接近数组开头处
C. 当 x 接近数组结尾处
D. 当 x 位于数组中间位置

答案 B  这就是顺序查找,肯定如果x比较靠前的话效率可能比较高

填空题


1.     法构造的哈希函数肯定不会发生冲突。

【答案】直接定址法。(H(key)=key或H(key)=a*key+b  

2. 高度为 8 的平衡二叉树的结点数至少有              个 。

【答案】54。高度为1的平衡二叉树的结点数至少有​​​​​​1个 ;高度为2的平衡二叉树的结点数至少有​​​​​​2个 ;高度为3的平衡二叉树的结点数至少有​​​​​​4个 ;高度为4的平衡二叉树的结点数至少有​​​​​​7个 ;高度为5的平衡二叉树的结点数至少有​​​​​​12个 ;高度为6的平衡二叉树的结点数至少有​​​​​​20个 ...规律为A(n)+A(n+1)+1=A(n+2),因此高度为8的平衡二叉树的结点至少有54个。

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

 高为8,只要算到h为7即可

3.查找是非数值程序设计的一个重要技术问题,基本上分成_____,_____和_____。处理哈希冲突的方法有_____ 、_____ 、_____和_____。

【答案】顺序表查找;树表查找;哈希表查找;开放定址方法;链地址方法;再哈希法;建立公共溢出区。
 

综合应用题

1. 假定对有序表: ( 3, 4, 5, 7, 24, 30, 42 , 54, 63 , 72 , 87, 95)进行折半查找,试回答下列问题:

    ① 画出描述折半查找过程的判定树;

    ② 若查找元素 54 ,需依次与哪些元素比较?

    ③ 若查找元素 90 ,需依次与哪些元素比较?

    ④ 假定每个元素的查找概率相等,求查找成功时的平均查找长度。

【答案】① 先画出判定树如下(注: mid= (1+12)/2 =6)//这里标注这个是为了证明是向下取整

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

 

    ② 查找元素 54 ,需依次与 30, 63, 42, 54 元素比较;

    ③ 查找元素 90 ,需依次与 30, 63,87, 95 元素比较;

    ④ 求 ASL 之前,需要统计每个元素的查找次数。判定树的前 3 层共查找1+2×2+4×3=17 次;但最后一层未满,不能用8×4,只能用5×4=20 次,所以 ASL=1/12 (17+20)= 37/12 ≈ 3.08
 

2. 对图所示的 3 阶 B- 树,依次执行下列操作,画出各步操作的结果。//3阶B- 树,所以结点数要求1~3,但是关键字个数需1=<m=<2

    ① 插入 90; ② 插入 25 ;③ 插入 45 ;④ 删除 60;⑤删除80。

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

【答案】①该树为3阶B-树,所以每个结点中最多有2个关键字,90可直接插入100所在的结点中,如图:

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

    ②3阶B-树最多有3个结点,而20<25<30,所以将25插入8与20所在结点。但此时关键字字数>2,需要中间值上提至上一层,中间值左右两边分裂,如图:

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

    ③因40<45<50,所以将45插入35与40所在结点。但此时关键字字数>2,需要中间值上提至上一层,中间值左右两边分裂,结果为:

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

    但此时第二层的关键字个数>2,因此中间值30需要向上提,如图:

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

    ④删除60后,60所在结点个数<1,同时60的兄弟结点个数≥2,其兄弟结点90上移至上一层,同时80下移作为第三层结点,结果如图:

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

    ⑤删除80后,80所在结点个数<1,同时80的兄弟结点个数=1,将上层结点拉下来与兄弟结点合并,结果如图:

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

无论增加还是删除,除了根节点,其余节点都会满足对应的结点数,如1个关键字就有左右两个孩子结点,2个关键字就有3个孩子结点

3. 设哈希表的地址范围为 0~ 17,哈希函数为: H( key )=key%16 。用线性探测法处理冲突,输入关键字序列:( 10, 24,32 ,17, 31, 30, 46 ,47, 40, 63,49),构造哈希表,试回答下列问题:

    ① 画出哈希表的示意图;

    ② 若查找关键字 63,需要依次与哪些关键字进行比较?

    ③ 若查找关键字 60,需要依次与哪些关键字比较?

    ④ 假定每个关键字的查找概率相等,求查找成功时的平均查找长度。

【答案】① 画表如下:

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法 (解析)

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

    ② 查找 63, 首先要与 H(63)=63%16=15 号单元内容比较,即 63 与 31 比较 , 不匹配 ; 然后顺移,与 46,47,32,17,63 相比,一共比较了 6 次!

    ③ 查找 60, 首先要与 H(60)=60%16=12 号单元内容比较,但因为 12 号单元为空(应当有空标记) ,所以应当只比较这一次即可。

    ④ 有6个数各比较 1 次;共 6 次; “ 63 ”需要 6 次,“ 49”需要 3 次,“ 40”需要 2 次,“ 46 ”需要 3 次,“ 47 ”需要 3 次,所以 ASL=1/11 ( 6+2+3×3+6 )= 23/11。
 

4. 设有一组关键字 ( 9,01,23 ,14 ,55,20,84,27),采用哈希函数: H( key )=key %7 ,表长为 10,用开放地址法的二次探测法处理冲突。要求:对该关键字序列构造哈希表,并计算查找成功的平均查找长度。

【答案】构造哈希表如下所示:

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

    平均查找长度: ASLsucc =( 1+1+1+2+3+4+1+2 ) /8=15/8。

解析 设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法 

5.将关键字序列(7、8、30、11、18、9、14)散列存储到散列列表中,散列表的存储空间是一个下标从0开始的一个一维数组,散列函数为:H(key)=(key×3)MOD 7,处理冲突采用线性探测再散列法,要求装填(载)因子为0.7。
问题:
1)请画出所构造的散列表
2)分别计算等概率情况下,查找成功和查找不成功的平均查找长度
 

1)装填因子为0.7,数据总数7个,所以存储空间长度为10,所以,构造的数列表的哈希地址为:
H(7)=(7×3)MOD 7=0
H(8)=(8×3)MOD 7=3
H(30)=(30×3)MOD 7=6
H(11)=(11×3)MOD 7=5
H(18)=(18×3)MOD 7=5  H(18)=(5+1)MOD 10=6 H(18)=(5+2)MOD 10=7
H(9)=(9×3)MOD 7=6   H(9)=(6+1)MOD 10=7  H(9)=(6+2)MOD 10=8
H(14)=(14×3)MOD 7=0  H(14)=(0+1)MOD 10=1

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

 2)平均查找长度
查找成功的平均查找长度A S L 成 功 ASL =(1+1+1+1+3+3+2)/ 7 = 12 / 7
查找不成功的平均查找长度不 成 功 ASL=(3+2+1+2+1+5+4) / 7 = 18 / 7

    解析   这里要特别防止惯性思维。查找失败时,是根据查找失败位置计算平均次数,根据散列函数mod 7,初始只可能在0~6的位置。等概率情况下,查找0~6位置查找失败的查找次数见表B-6。设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

 可理解为根据散列函数mod 7,初始只可能在0~6的位置。

在0处探测失败了,到下一个空位处(2处)需要探测3次,

在1处探测失败了,到下一个空位处(2处)需要探测2次,

在2处可直接成功为1次, 在3处探测失败了,到下一个空位处(4处)需要探测2次,

在4处可直接成功为1次, 在5处探测失败了,到下一个空位处(9处)需要探测5次,

 在6处探测失败了,到下一个空位处(9处)需要探测4次,结束,共探测3+2+1+2+1+5+4=18次

5.已知如下所示长度为12 的表:( Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct,Nov, Dec )
试按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成之后的二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。

解析(根据比较首字母大小,首字母相同,再比较第二字母大小,以此类推)然后排好序后按照表中元素的顺序依次插入 

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法
②若对表中元素先进行排序构成有序表,求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法
③按表中元素顺序构造一棵平衡二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。

 设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

7. 设哈希函数H( K) =3 K mod 11 ,哈希地址空间为0~ 10 ,对关键字序列( 32 , 13,49 , 24 , 38, 21, 4, 12 ),按下述两种解决冲突的方法构造哈希表,并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc 和ASLunsucc 。
①线性探测法;

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法
②链地址法。

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

 这里不成功次数跟王道有点出入,用王道的方法是(0+1+0+1+2+0+2+0+2+0+0)/11=8/11

个人感觉用上面一种应该对的 ,因为毕竟是真题答案!

8.构造平衡二叉树(AVL)

例题1:输入关键字序列为 { 16, 3, 7, 11, 9, 26, 18, 14, 15 },构成一棵平衡二叉排序树。

①插入16                       ②插入3                        ③插入7   ----->          LR双旋                 

  设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法   设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法     设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

 ④插入11                                         ⑤插入9       -------->   LL单旋

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法                      设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法 设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

⑥插入26                            -------->      RR单旋

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

 ⑦插入18                                         -------->        RL双旋

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

 ⑧插入14                                                ⑨插入15                -------->        LR双旋

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

9.给出如下平衡树,平衡二叉树中删除结点22,展示输出后的结果。

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法

 答案:

设有一个已排序的线性表(长度>=2),分别用顺序查找法和二分查找法找一个与k相等的,数据结构习题大全,数据结构,算法文章来源地址https://www.toymoban.com/news/detail-784608.html

到了这里,关于数据结构-查找2(详解)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 二叉排序树的创建、插入、查找和删除【数据结构】

    若它的左子树不空,则左子树上所有结点的值均小于它根结点的值。 若它的右子树不空,则右子树上所有结点的值均大于它根结点的值。 它的左、右树又分为⼆叉排序树 二叉排序树也叫二叉查找树、二叉搜索树 题目描述 给出一个数据序列,建立二叉排序树,并实现插入功

    2024年01月24日
    浏览(44)
  • 数据结构07:查找[C++][平衡二叉排序树AVL]

    图源:文心一言 考研笔记整理1w+字,小白友好、代码可跑,请小伙伴放心食用~~🥝🥝 第1版:查资料、写BUG、画导图、画配图~🧩🧩 参考用书: 王道考研《2024年 数据结构考研复习指导》 参考用书配套视频: 7.3_2 平衡二叉树_哔哩哔哩_bilibili 特别感谢:  Chat GPT老师、文心

    2024年02月11日
    浏览(48)
  • 数据结构07:查找[C++][朴素二叉排序树BST]

    图源:文心一言 考研笔记整理 8k+ 字,小白友好、代码可跑,请小伙伴放心食用~~🥝🥝 第1版:查资料、写BUG、画导图、画配图~🧩🧩 参考用书: 王道考研《2024年 数据结构考研复习指导》 参考用书配套视频: 7.3_1 二叉排序树_哔哩哔哩_bilibili 特别感谢:  Chat GPT老师、文心

    2024年02月10日
    浏览(40)
  • 二叉排序树的插入删除和查找(数据结构实训)(难度系数100)

    二叉排序树的插入删除和查找 pre: 前序遍历 in: 中序遍历 post:后序遍历 insert: 插入,本题中不会出现相同的元素 delete: 删除,删除成功输出TRUE,没有该元素则输出FALSE,删除的方法是如果有左子树,以左子树中最大值作为新的树根,否则,以右子树最小值作为树根。 search:

    2024年01月25日
    浏览(51)
  • 合肥工业大学 宣城校区 数据结构与算法实验 队列、二叉树、查找和排序

    1.实验目标 熟练掌握队列的顺序存储结构和链式存储结构。 熟练掌握队列的有关算法设计,并在循环顺序队列和链队列上实现。 根据具体给定的需求,合理设计并实现相关结构和算法。 2.实验内容和要求 循环顺序队列的实验要求 循环顺序队列结构和运算定义,算法的实现以

    2024年02月11日
    浏览(49)
  • 数据结构之查找详解

    1.1 定义 查找表是由同一类型的数据元素构成的集合。 例如电话号码簿和字典都可以看作是一张查找表。 1.2 查找表的几种操作: 1)在查找表中查找某个具体的数据元素; 2)在查找表中插入数据元素; 3)从查找表中删除数据元素; 1.3 静态查找表和动态查找表 在查找表中

    2024年01月16日
    浏览(33)
  • 数据结构-查找2(详解)

    1 .在一棵由包含 4、5、6 等等一系列整数结点构成的二叉搜索树中,如果结点 4 和 6 在树的同一层,那么可以断定结点 5 一定是结点 4 和 6 的父亲结点。  错    解析:         反例  2.二叉搜索树的查找和折半查找的时间复杂度相同。 错   解析:不一定相同。二叉排序树

    2024年02月02日
    浏览(36)
  • C语言数据结构二叉排序树的建立、插入、删除、查找操作(原理+完整代码)

    1、若左子树不为空,左子树上所有节点值小于 它根节点的值 2、若右子树不为空,右子树上所有节点值大于 它根节点的值 3、每个节点的左右子树也是二叉排序树 目的:提高查找、插入、删除的速度(不是为了排序) 时间复杂度:由于查找性能取决于树的形态,所以

    2024年02月09日
    浏览(49)
  • 【数据结构与算法】查找(Search)【详解】

    【知识框架】 查找(Searching) :就是根据给定的某个值,在查找表中确定一个其等于给定值的数据元素( 或记录)。 查找表(Search Table) :是由同一类型的数据元素(或记录)构成的集合。 (Key):数据元素中唯一标识该元素的某个数据项的值,使用基于的查找,查

    2024年02月02日
    浏览(49)
  • 【排序算法】数据结构排序详解

    前言: 今天我们将讲解我们数据结构初阶的最后一部分知识的学习,也是最为“炸裂”的知识---------排序算法的讲解!!!! 排序 :所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作。 稳定性 :假定在待排序的记录序列中,

    2023年04月08日
    浏览(50)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包