算法与数据结构之集合

骑猪看日落 2022-12-17 07:25 615阅读 0赞

## 重点知识 ##

1. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是**哈希查找**。

2. 动态查找表和静态查找表的重要区别在于前者包含有**插入和删除**运算，而后者不包含这两种运算。

3. 在等概率的情况下，对具有n个元素的顺序表进行顺序查找，查找成功(即表中有关键字等于定值K的记录)的平均查找长度为**(n+1)/2**；查找不成功(即表中无关键字等于给定值K的记录)的平均查找长度为**(n+1)**。

4. 顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为**n**次，当使用监视哨时，若查找失败，则比较关键字的次数为**n+1**。

5. 折半查找要求数据元素**有序**，存储方式采用**顺序存储**。

6. 在n个记录的有序顺序表中进行折半查找，最大的比较次数为**⌊log2^n⌋+1**。

7. 在有序表A\[1，2，3...12\]中，采用二分查找算法查找等于A\[12\]的元素，所比较的元素下标依次为6，9，11，12。

8. 在有序表A\[1...20\]中，按二分查找算法进行查找，查找长度为5的元素个数是**5**。

9. 假定查找有序表A\[1...12\]中的每个元素的概率相等，则进行二分查找时的平均查找长度为**37/12**。

10. 长度为10的按关键字有序的查找表采用顺序存储，若使用折半查找，则在等概率情况下，查找失败时的ASL(平均查找长度)值是**39/11**。

11. 在有序表A\[1...20\]中，按二分查找方法进行查找，查找长度为4的元素的下标是从小到大依次是**1，3，6，8，11，13，16，19**。

12. 已知有序表\{12，18，24，35，47，50，62，83，90，115，134\}，当用二分查找90时，需要**2**次查找成功，查找47时，需要**4**次查找成功，查找100时，需要**3**次查找成功。

13. n个结点的用于折半查找的判定树，表示查找失败的外部结点共有n+1个。

14. 设表长度为1023的有序线性表，查找每个元素的概率相等，采用折半查找方法，查找成功的ASL是**9(1024=2^10)**。

15. 在一个按值有序排列的顺序表中进行折半查找，其查找过程中可以用一棵树称之为"判断树"的二叉树来描述。若顺序表的长度为19，则对应的"判断树"的根结点的左孩子之值(元素在表中的位置)是5（下标从1开始）。

16. 对于具有144个记录的文件，若采用分块查找，且每一块的长度为8，则平均查找长度为14（**计算过程为144/8=18块，索引表顺序查找，故(18+1)/2+(8+1)/2=14**）。

17. 有一个2000项的表，欲采用等分区间顺序查找方法进行查找，则**每块的理想长度为45，分成45块最为理想，平均查找长度为46**。

18. 分块检索中，若索引表和各块内均用顺序查找，则有900个元素的线性表分成**30**块最好；若分成25块，其平均查找长度为**31.5**。

19. 执行顺序查找是，存储方式可以是**顺序存储或链式存储**，二分查找时，要求线性表**顺序存储且有序**，分块查找时要求线性表**块内有序，块间有序**，而散列表的查找，要求线性表的存储方式是**散列存储**。

20. 查找是非数值程序设计的一个重要技术问题，基本上分成**静态查找表**，**动态查找表**和**哈希表**。处理哈希冲突的方法有**开放地址法**，**链地址法**，**再哈希**和**建立公共溢出区**。

21. 如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为**(n+1)/2**。

22. 在含有n个结点的二叉排序树中查找一个关键字，进行关键字比较次数的最大值是**n**。

23. 在二叉排序树上成功地找到一个结点，在平均情况下的时间复杂度是O(logn)，在最坏情况下的时间复杂度为O(n)。

24. AVL树**不一定**是一棵完全二叉树；完全二叉树**一定**是AVL树。AVL是平衡二叉树，各个结点值之间满足确定关系。从树形上看，完全二叉树任意结点左右子树的高度差绝对值不大于1。仅从结点平衡因子角度看，可以说完全二叉树是平衡二叉树。

25. 一棵深度为k的平衡二叉树，其每个非终端结点的平衡因子均为0，则该树共有**(2^k)-1**个结点，即满二叉树。

26. 在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字个数为**m-1**；若在某节点中删除一个关键字而导致结点合并，则该节点中原有的关键字的个数是**⌈m/2⌉-1**。

27. 高度为4的3阶B-树中，最多有26个关键字，即**第四层为叶子结点，1至3层每个结点两个关键字**。

28. 高为4(不含叶子层)的4阶B-树最少有15个关键字（**即同于高度为4的满二叉树**）。

29. 高度为5的平衡二叉树，其结点数最多可以有**31**个；最少可以是**12**个。

30. 一棵含有15个关键字的4阶B树，其非叶子结点数最少不能少于**5**个，最多可以为**15**个。

31. 对于m=4(4阶)的B-树，如果根的层次为第1层，则高度为2的B-树最少要存储**3**个关键字，最多可以保存**15**个关键字。

32. 具有n个关键字的B树的查找路径长度不会大于？。

33. 127阶B-树种每个结点最多有？个关键字，则其叶子结点有？个。

34. 设高为h的m阶B-树上共有k个关键字，则其叶子结点有**(K+1)**个。

35. 高度为h的2-3树种叶子的数目至多为？。

36. 哈希表用**关键字**确定记录的存储位置。

37. 在哈希表中，不同的关键字产生同一个哈希地址的现象，称为**哈希冲突**。

38. 设已知n个关键字具有相同的散列函数，并采用线性探测再散列方法处理冲突，将这n个关键字散列到初始为空的地址空间中，一共发生了n(n-1)/2次散列冲突，即**第1个关键字探测1次，没有发生冲突，第2个关键字探测2次，发生一次冲突，...，第n个关键字探测n次，发生了n-1次冲突**。

算法与数据结构之集合

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关数据结构与算法之算法分析

相关算法与数据结构之集合

相关 JS数据结构与算法入门(五) - 数据结构之“集合”

相关数据结构与算法之排序

相关 04 Javascript数据结构与算法之集合

相关 JavaScript数据结构与算法（3）集合

相关数据结构与算法之BFPRT算法

相关数据结构与算法之Manacher算法

相关数据结构与算法之KMP算法

相关数据结构与算法之栈