一基础知识题
对含有n个互不相同元素的集合同时找最大元和最小元至少需进行多少次比较?
答我们可以设立两个变量max和min用于存放最大元和最小元(的位置)第一次取两个元素进行比较大的放入max小的放入min从第次开始每次取一个元素先和max比较如果大于max则以它替换max并结束本次比较;若小于max则再与min相比较在最好的情况下一路比较下去都不用和min相比较所以这种情况下至少要进行n次比较就能找到最大元和最小元(顺便说一下最坏情况下要进行n次比较才能得到结果)
若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找试在下述两种情况下分别讨论两者在等概率时的平均查找长度()查找不成功即表中无关键字等于给定值K的记录;()查找成功即表中有关键字等于给定值K的记录
答查找不成功时需进行n+次比较才能确定查找失败因此平均查找长度为n+这时有序表和无序表是一样的
查找成功时平均查找长度为(n+)/有序表和无序表也是一样的因为顺序查找对表的原始序列的有序性不感兴趣
画出对长度为的有序的顺序表进行二分查找的判定树并指出在等概率时查找成功的平均查找长度以及查找失败时所需的最多的关键字比较次数
答请看题图
等概率情况下查找成功的平均查找长度为
ASL=(+*+*+*+*)/=
也可以用公式代大约为ASL=(+)lg(+)/=
查找失败时最多的关键字比较次树不超过判定树的深度此处为如图
为什么有序的单链表不能进行折半查找?
答因为链表无法进行随机访问如果要访问链表的中间结点就必须先从头结点开始进行依次访问这就要浪费很多时间还不如进行顺序查找而且用链存储结构将无法判定二分的过程是否结束因此无法用链表实现二分查找
设有序表为(abcefgijkpq)请分别画出对给定值bg和n进行折半查找的过程
解 b的查找过程如下(其中括号表示当前查找区间圆括号表示当前比较的关键字)
下标
第一次比较 [a b c d e f (g) h i j k p q]
第二次比较 [a b (c)d e f] g h i j k p q
第三次比较 [a(b)]c d e f g h i j k p q
经过三次比较查找成功
g的查找过程如下
[a b c d e f (g) h i j k p q]
一次比较成功
n的查找过程如下
下标
第一次比较 [a b c d e f (g) h i j k p q]
第二次比较 a b c d e f g [h i (j) k p q]
第三次比较 a b c d e f g h i j [k (p) q]
第四次比较 a b c d e f g h i j [k] p q]
经过四次比较查找失败
将(for case while class protected virtual public private do template const if int)中的关键字依次插入初态为空的二叉排序树中请画出所得到的树T然后画出删去for之后的二叉排序树T若再将for 插入T中得到的二叉排序树T是否与T相同?最后给出T的先序中序和后序序列
答见题图:
T的先序序列是do case class const while protected private if for int virtual public template
T的中序序列是case class const do for if int private protected public template virtual while
T的后序序列是const class case for int if private template public virtual protected while do
二叉排序树T如下图
删去for后的二叉排序树如下图圈内的for表示再插入后的结点
对给定的关键字集合以不同的次序插入初始为空的树中是否有可能得到同一棵二叉排序树?
答有可能如有两个序列 和 它们插入空树所得的二叉排序树是相同的
将二叉排序树T的先序序列中的关键字依次插入一空树中所得和二叉排序树T与T是否相同?为什么?
答这两棵二叉树完全相同
设二叉排序树中关键字由至的整数构成现要查找关键字为的结点下述关键字序列哪一个不可能是在二叉排序树上查找到的序列?
(a) ;
(b) ;
(c) ;
(d)
答(c)是不可能查找到的序列我们可以把这四个序列各插入到一个初始为空的二叉排序树中结果可以发现(c)序列所形成的不是一条路径而是有分支的可见它是不可能在查找过程中访问到的序列
设二叉排序树中关键字互不相同则其中最小元必无左孩子最大元必无右孩子此命题是否正确?最小元和最大元一定是叶子吗?一个新结点总是插在二叉排序树的某叶子上吗?
答此命题正确假设最小元有左孩子则根据二叉排序树性质此左孩子应比最小元更小如此一来就产生矛盾了因此最小元不可能有左孩子对于最大元也是这个道理
但最大元和最小元不一定是叶子它也可以是根内部结点(分支结点)等这得根据插入结点时的次序而定如 这个集合根据不同的插入次序可以得到不同的二叉排序树
○
/ \
○ ○
\
○
○
/ \
○ ○
\
○
○
\
○
\
○
\
○
○
/ \
○ ○
/
○
新结点总是插入在二叉排序树的某个叶子上的
在一棵m阶的B树中当将一关键字插入某结点而引起该结点的分裂时此结点原有多少个关键字?若删去某结点中的一个关键字而导致结点合并时该结点中原有几个关键字?
答在此树中若由于一关键字的插入某结点而引起该结点的分裂时则该结点原有m个关键字
若删去某结点中一个关键字而导致结点合并时该结点中原有┌m/┐个关键字
在一棵B树中空指针数总是比关键字数多一个此说法是否正确?请问包含个关键字的阶B树(即树)最多有几个结点?最少有几个结点?画出这两种情况的B树
答这个说法是正确的
包含个关键字的阶B树最多有个结点最少有个结点
见题图:图如下
在含有n个关键字的m阶B树中进行查找至多读盘多少次?完全平衡的二叉排序树的读盘次数大约比它大多少倍?
答在含有n个关键字的m阶B树中进行查找至多读盘次数不超过B树高h即logt((n+)/)+ (注此处t为底值是除根外的每个内部结点的最小度数┌m/┐)
完全平衡的二叉树高为lgn所以它的读盘次数至多也是lgn它与上述B树的读盘次数的比值约为lgt倍(此处底是)
为什么在内存中使用的B树通常是阶的而不使用更高阶的B树?
答因为查找等操作的cpu时间在B树上是O(lgn·(m/lgt))而m/lgt>所以m较大时它所费时间比平衡的二叉排序树上相应操作时间大得多因此仅在内存中使用的B树通常取最小值
为什么二叉排序树长高时新结点总是一个叶子而B树长高时新结点总是根?哪一种长高能保证树平衡?
答因为在二叉排序树中关键字总是作为一个叶子结点插入以原来的树中所以当树增高时新结点总是一个叶子;而B树中关键字插入总是插入到叶子结点内部在叶结点中的关键字数目尚未超过它能够容纳的数目之前是不会增加结点的当关键字数超过结点可容纳的数目时叶结点就会发生分裂产生一个新结点(但不一定引起树增高)并且将其中的中间结点传至上一层只有当这种分裂操作传递至根结点并引起根结点的分裂时才能引起树高增加此时产生一个新的根结点所以说B树长高时新结点总是根
显然后一种长高总能保证树的平衡
已知关键字序列为(PALLAPPAMMAPPATPETSETSATTATBAT)试为它们设计一个散列函数将其映射到区间[n]上要求碰撞尽可能的少这里n=
解我的设计的散列函数是这样的把关键字串中的每一个字符按其所在位置分别将其ASCII值乘以一个不同的数然后把这些值相加的和去对n求余余数即为散列表中的位置函数如下
int Hash (char key[])
{
return (int)(key[]+key[]*+key[]*)%n;
}
我们可以设计一个程序来看看用这个散列函数得到的所有关键字映射到区间的位置
#include
#define n file://先 用来代入我们可以用依次代入验证
int Hash (char key[])
{
return (int)(key[]+key[]*+key[]*)%n;
file://此 处我用了系数和你也可以用其他的数代入看有没有更好的系数
}
void main()
{
char s[][]={PALLAPPAMMAPPATPETSETSATTATBAT};
// 以上用<
