数据结构与算法上机作业
第五章 查找
一、选择题
1、若构造一棵具有n个结点的二叉排序树，在最坏情况下，其高度不超过 B 。
A. n/2 B. n C. (n+1)/2 D. n+1
2、分别以下列序列构造二叉排序数（二叉查找树），与用其他3个序列所构造的结果不同的是 C ：
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)
3、不可能生成下图所示的二叉排序树的关键字的序列是 A 。
A. 4 5 3 1 2 B. 4 2 5 3 1 C. 4 5 2 1 3 D. 4 2 3 1 5
42513
4、在二叉平衡树中插入一个结点造成了不平衡，设最低的不平衡点为A，并已知A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应作 C 型调整使其平衡。
A. LL B. LR C. RL
D. RR
5、一棵高度为k的二叉平衡树，其每个非叶结点的平衡因子均为0，则该树共有 C 个结点。
A. 2k-1-1 B. 2k-1+1 C. 2k-1 D. 2k+1
6、具有5层结点的平衡二叉树至少有 A 个结点。
A. 12 B. 11
C. 10 D. 9
7、下面关于B-和B+树的叙述中，不正确的是 C 。
A. B-树和B+树都是平衡的多叉树
B. B-树和B+树都可用于文件的索引结构
C. B-树和B+树都能有效地支持顺序检索 D. B-树和B+树都能有效地支持随机检索
8、下列关于m阶B-树的说法错误的是 D 。
数据库技术知识数据结构的算法
对于将要参加计算机等级考试的考生来说，计算机等级考试的知识点辅导是非常重要的复习资料。以下是收集的数据库技术知识数据结构的算法，希望大家认真阅读!
1、数据：数据的基本单位是数据元素。数据元素可由一个或多个数据项组成。数据项是数据的不可分割的最小单位
2、数据结构：数据的逻辑结构、数据的存储结构、数据的运算
3、主要的数据存储方式：顺序存储结构(逻辑和物理相邻，存储密度大)和链式存储结构
顺序存储结构：
顺序存储计算公式Li=L0+(i-1)×K顺序结构可以进行随机存取;插人、删除运算会引起相应节点的大量移动
链式存储结构：a、指针域可以有多个，可以指向空，比比顺序存储结构的存储密度小
b、逻辑上相邻的节点物理上不一定相邻。c、插人、删除等不需要大量移动节点
4、顺序表：一般情况下，若长度为n的顺序表，在任何位置插入或删除的概率相等，元素移动的平均次数为n/2(插入)和(n-1)/2(删除)。
5、链表：线性链表(单链表和双向链表等等)和非线性链表 线性链表也称为单链表，其每个一节点中只包含一个指针域，双链表中，每个节点中设置有两个指针域。(注意结点的插入和删除操作)
6、栈：“后进先出”(LIFO)表。栈的应用：表达式求解、二叉树对称序周游、快速排序算法、递归过程的实现等
7、队列：“先进先出”线性表。应用：树的层次遍历
8、串：由零个或多个字符组成的有限序列。
9、多维数组的顺序存储：
10、稀疏矩阵的存储：下三角矩阵顺序存储
其他常见的存储方法还有三元组法和十字链表法
11、广义表：由零个或多个单元素或子表所组成的有限序列。广义表的元素可以是子表，而子表的元素还可以是子表
12、树型结构：非线性结构。常用的树型结构有树和二叉树。
二叉树与树的区别：二叉树不是树的特殊情况，树和二叉树之间最主要的区别是：二叉树的节点的子树要区分左子树和右子树，即使在节点只有一棵子树的情况下也要明确指出该子树是左子树还是右子树。
1 第9章 查找答案
一、填空题
1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。
2. 线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索 9 次。设有100个结点，用二分法查找时，最大比较次数是 7 。
3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。
解：显然，平均查找长度＝O（log2n）<5次（25）。但具体是多少次，则不应当按照公式
)1(log12nnnASL来计算（即（21×log221）/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
二、单项选择题
（ B ）1．在表长为ｎ的链表中进行线性查找，它的平均查找长度为
Ａ. ＡＳＬ＝ｎ; Ｂ. ＡＳＬ＝（ｎ＋１）／２;
Ｃ. ＡＳＬ＝n＋１; Ｄ. ＡＳＬ≈ｌｏｇ２（ｎ＋１）－１
（ A ）2. 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中 比较大小，查找结果是失败。
数据结构练习第⼋章查找
数据结构练习第⼋章查找1.若有18个元素的有序表存放在⼀维数组A[19]中，第⼀个元素放A[1]中，现进⾏⼆分查找，则查找A［3］的⽐较序列的下标依次为( )A. 1，2，3
B. 9，5，2，3
C. 9，5，3
D. 9，4，2，3
2．设⼆叉排序树中有n个结点，则在⼆叉排序树的平均平均查找长度为（）。
A. O(1)
B. O(log2n)
C. O(n)
D. O(n2)
3．在⼆叉排序树中插⼊⼀个结点的时间复杂度为（）。
A. O(1)
B. O(n)
C. O(log2n)
D. O(n2)
4．设有序顺序表中有n个数据元素，则利⽤⼆分查找法查找数据元素X的最多⽐较次数不超过（）。
A. log2n+1
B. log2n-1
C. log2n
D. log2(n+1) 5．设有序表中有1000个元素，则⽤⼆分查找查找元素X最多需要⽐较（）次。
A. 25
B. 10
C. 7
D. 1
6．顺序查找不论在顺序线性表中还是在链式线性表中的时间复杂度为（）。
A. O(n)
B. O(n2)
C. O(n1/2)
D. O(1og2n) 7．设⼆叉排序树上有n个结点，则在⼆叉排序树上查找结点的平均时间复杂度为（）。
A. O(n)
B. O(n2)
C. O(nlog2n)D. O(1og2n) 8．（）⼆叉排序树可以得到⼀个从⼩到⼤的有序序列。
A. 先序遍历
B.中序遍历
C. 后序遍历
D. 层次遍历
9．设⼀组初始记录关键字序列为(13，18，24，35，47，50，62，83，90，115，134),则利⽤⼆分法查找关键字90需要⽐较的关键字个数为（）。A. 1
B. 2
C. 3
D. 4
10．设某散列表的长度为100，散列函数H(k)=k % P，则P通常情况下最好选择（）。
A. 99
B. 97
C. 91
D. 93
11．在⼆叉排序树中插⼊⼀个关键字值的平均时间复杂度为（）。
A. O(n)
B. O(1og2n)
C. O(nlog2n)
