单选

在长度为n的线性表中顺序查找时，不成功情况下平均比较次数是______。

单选

在长度为n的线性表中顺序查找时，成功情况下最多的比较次数是______。

单选

对长度为3的顺序表进行顺序查找，若查找第1个元素的概率是1/2，查找第2个元素的概率是1/3，查找第3个元素的概率是1/6，则成功查找表中任一元素的平均查找长度是______。

单选

对线性表进行折半查找时，要求线性表必须______。

单选

折半查找对应的判定树中，外部结点是______。

单选

已知一个长度为16的有序顺序表R[1..16]，采用折半查找方法查找一个存在的元素，则比较的次数最多是______。

单选

设有100个元素的有序顺序表，采用折半查找方法，不成功时最大的比较次数是______。

单选

有一个长度为12的有序表R[0..11]，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为______。

单选

有一个长度为12的有序表R[0..11]，按折半查找法对该表进行查找，在表内各元素等概率情况下查找不成功所需的平均比较次数为______。

单选

10.有一个有序表为（1，3，9，12，32，41，45，62，75，77，82，95，99），当采用折半查找法查找关键字为82的元素时，______ 次比较后查找成功。

单选

有一个长度为n的有序顺序表，采用折半查找，经过i次比较成功找到的最多元素个数是______。

单选

当采用分块查找时，数据的组织方式为______。

单选

对含有3600个元素的顺序表进行分块查找，若索引表和方块均采用顺序查找方法，最理想的块长是______。

单选

设待查关键字为47，且已存入变量k中，如果在查找过程中，和k进行比较的元素依次是47、32、46、25、47，则所采用的查找方法______。

单选

设待查关键字为47，且已存入变量k中，如果在查找过程中，和k进行比较的元素依次是27、72、16、84、47，则所采用的查找方法是______。

单选

从19个元素的序列中查找其中某个元素，如果最多进行5次元素之间的比较，则采用的查找方法只可能是______。

单选

以下关于二叉排序树的叙述中正确的是______。

单选

由一个关键字序列建立一棵二叉排序树，该二叉排序树的形状取决于______。

单选

在任意一棵非空二叉排序树T1中，删除某结点v之后形成二叉排序树T2，再将v 插入T2形成二叉排序树T3。下列关于T1与T3的叙述中，正确的是______。 I. 若v是T1的叶子结点，则T1与T3不同 II. 若v是T1的叶子结点，则T1与T3相同 III. 若v不是T1的叶子结点，则T1与T3不同 IV. 若v不是T1的叶子结点，则T1与T3相同

单选

20. 对于下列关键字序列，不可能构成某二叉排序树中一条查找路径是______。  

单选

一棵二叉排序树是由关键字集合{18，43，27，44，36，39}中的某个关键字序列构建的，其中序遍历序列是______。

单选

以下查找方法中速度最快的是______。

单选

含有20个结点的AVL树的最大高度是______。

单选

含有20个结点的AVL树的最小高度是______。

单选

若AVL树的高度为6，且所有非叶结点的平衡因子均为1，则该AVL树的结点总数为______。

单选

若将关键字1，2，3，4，5，6，7依次插入到初始为空的平衡二叉树T中，则T中平衡因子为0的分支结点的个数是______。

单选

以下关于m阶B-树的叙述中正确的是______。

单选

一棵3阶B-树中含有2047个关键字，不计外部结点层，该树的最大高度为______。

单选

下面关于B-树和B+树的叙述中，不正确的是______。

单选

30. 下面有关哈希表的叙述中，正确的是______。  

单选

在哈希查找过程中，可用______ 来处理冲突。

单选

哈希表中出现同义词冲突是指______。

单选

为提高哈希（Hash）表的查找效率，可以采取的正确措施是______。 Ⅰ.增大装填因子 Ⅱ.设计冲突少的哈希函数 Ⅲ.处理冲突时避免产生堆积现象

单选

采用线性探查法解决冲突的哈希表中，引起的堆积现象的原因是______。

单选

假设有k个关键字互为同义词，若用线性探测法把这k个关键字插入到哈希表中，至少要进行______ 次探测。

单选

哈希查找方法一般适用于（ ）情况下的查找。

单选

哈希查找的基本思想是根据（ ）来决定元素的存储地址。

单选

计算出地址分布最均匀的哈希函数是（ ）。

单选

将10个元素散列到大小为10000的哈希表中，（ ）产生冲突。

单选

以下关于哈希查找的叙述中错误的是（ ）。

单选

在含有n个结点的二叉排序树中查找某关键字的结点时，最多进行（ ）次比较。

单选

用n个关键字构造的一棵二叉排序树，其最低高度为（ ）。

单选

用n个关键字构造的一棵二叉排序树，经过i次关键字比较成功找到的元素个数最多为（ ）。

单选

二叉排序中，最小关键字结点的（ ）。

单选

二叉排序中，最大关键字结点的（ ）。

单选

静态查找表和动态查找表的区别是( )。

单选

查找效率低的数据结构是( )。

单选

如果一个表既能较快地查找，又能适应动态变化的要求，则可采用( )。

单选

顺序查找法适合于存储结构为( )的线性表。

单选

采用顺序查找方法查找长度为n的线性表时，成功查找的平均查找长度为( )。

判断

51.哈希表既是一种查找方法，也是一种存储方法。

判断

52.哈希存储方法只能存储数据元素的值，不能存储数据元素之间的关系。

判断

53.哈希冲突是指同一个关键字对应多个不同的哈希地址。

判断

54.哈希表中所有的哈希地址是连续的。

判断

55.哈希表发生冲突是由于选取的解决冲突的方法不当造成的。

判断

56.二叉排序树可以是一棵空树。

判断

57.二叉排序树是用来进行排序的。

判断

58.在二叉排序树中，每个结点的关键字都比左孩子关键字大，比右孩子关键字小。

判断

59.二叉排序树的任意一棵子树中，关键字最小的结点必无左孩子，关键字最大的结点必无右孩子。

判断

60.每个结点的关键字都比左孩子关键字大，比右孩子关键字小，这样的二叉树一定是二叉排序树。

判断

61.对于不同的存储结构，应采用不同的查找方法。

判断

62.对于满足折半查找和分块查找条件的文件而言，无论该文件存放在任何介质上，均能进行顺序查找、折半查找和分块查找。

判断

63.顺序查找法适用于存储结构为顺序或链式存储的线性表。

判断

64.顺序查找方法只能在顺序存储结构上进行。

判断

65.顺序查找方法只能从顺序表的前端向后端查找。

填空

在各种查找方法中，其成功和不成功情况下的平均查找长度与元素个数n无关的查找方法是___。

填空

哈希表是通过___将某关键字的记录映射到哈希表中，当发生冲突时，选择某种___再找新的存放位置。

填空

哈希表中，哈希地址空间是指___。

填空

评价哈希函数好坏的标准是___。

填空

构建哈希表的关键是___和___。

填空

二叉排序树的性质是指___。

填空

在二叉排序树中，关键字最小的结点是根结点的___。

填空

在二叉排序树中，关键字最大的结点是根结点的___。

填空

对二叉排序树进行___遍历，可以得到接关键字从小到大排列的结点序列。

填空

对一棵二叉排序树进行这样的遍历：遍历右子树、访问根结点、遍历左子树，则得到的遍历序列是___。

填空

顺序查找方法适用于存储结构为___的线性表，而使用折半查找方法的条件是___。

填空

顺序查找算法的时间复杂度为___。

填空

和顺序查找方法相比，折半查找的主要缺点是___。

填空

采用顺序查找方法查找含n个元素的顺序表，最好情况下的关键字比较次数是___。

填空

采用顺序查找方法查找含n个元素的顺序表，若查找成功，则比较关键字的次数最多为___次；若查找不成功，则比较关键字的次数为___ 次。

简答

HDU3791—二叉排序树问题 时间限制：2000ms，空间限制：32768K。 问题描述：判断两序列是否为同一二叉搜索树序列 输入格式：开始一个数n（1≤n≤20) 表示有n个需要判断，n=0的时候输入结束。接下去一行是一个序列，序列长度小于10，包含0~9的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。 输出格式：如果序列相同则输出YES，否则输出NO 问题描述：判断两序列是否为同一二叉搜索树序列 输入格式：开始一个数n（1≤n≤20) 表示有n个需要判断，n=0的时候输入结束。接下去一行是一个序列，序列长度小于10，包含0~9的数字，没有重复数字，根据这个序列可以构造出一颗二叉搜索树。接下去的n行有n个序列，每个序列格式跟第一个序列一样，请判断这两个序列是否能组成同一颗二叉搜索树。 输出格式：如果序列相同则输出YES，否则输出NO

简答

简述哈希表查找的基本思想。列举常用的哈希函数的构造方法。

简答

哈希表是一种查找方法，为什么说它是一种存储结构？

简答

哈希表查找的时间性能可以达到O(1)，为什么在查找时不总是使用哈希表查找？

简答

什么是哈希冲突？处理冲突的方法是什么？

简答

为什么哈希表不支持元素之间的顺序查找？

简答

和折半查找相比，二叉排序树查找的优缺点各是什么？

简答

有一棵二叉排序树按先序遍历得到的序列为：(50,38,30,45,40,48,70,60,75,80)。回答以下问题： （1）画出该二叉排序树。 （2）在等概率下，求查找成功的平均查找长度和查找不成功的平均查找长度。

简答

将二叉排序树T的先序序列中的关键字依次插入到一棵空的二叉排序树中，所得到的二叉排序树T'与T是否相同？为什么？

简答

证明一棵非空二叉排序树的中序遍历序列是从小到大有序的。

简答

证明如果一棵非空二叉树的中序遍历序列是从小到大有序的，则该二叉树是一棵二叉排序树。

简答

简述静态查找表和动态查找表的异同。

简答

设有5个数据do、for、if、repeat、while，它们排在一个有序表中，其查找概率分别是p1=0.2，p2=0.15，p3=0.1，p4=0.03，p5=0.01。而查找它们之间不存在数据的概率分别为q0=0.2，q1=0.15，q2=0.1，q3=0.03，q4=0.02，q5=0.01，如下图所示： （1）试画出对该有序表分别采用顺序查找和折半查找时的判定树。 （2）分别计算顺序查找的查找成功和不成功的平均查找长度。 （3）分别计算折半查找的查找成功和不成功的平均查找长度。

简答

折半查找对查找的数据有什么要求？

简答

HDU2025—查找最大元素 时间限制：2000ms，空间限制：65536K。 问题描述：对于输入的每个字符串，查找其中的最大字母，在该字母后面插入字符串“(max)”。 输入格式：输入数据包括多个测试实例，每个实例由一行长度不超过100的字符串组成，字符串仅由大小写字母构成。 输出格式：对于每个测试实例输出一行字符串，输出的结果是插入字符串“(max)”后的结果，如果存在多个最大的字母，就在每一个最大字母后面都插入"(max)"。 输入示例： Abcdefgfedcba xxxxx 输出示例： Abcdefg(max)fedcba x(max)x(max)x(max)x(max)x(max)

简答

POJ2785—总和为零的四元组数 时间限制：15000ms，空间限制：228000K。 问题描述：SUM问题是，给定4个整数列表A、B、C和D，计算多少个四元组（a，b，c，d）∈A×B×C×D满足a+b+c+d=0。在下文中，我们假设所有列表都具有相同的大小n。 输入格式：输入文件的第一行包含列表的大小n（此值可以大到4000）。 然后有n行每行包含四个整数值（绝对值大到2^28），它们分别属于A、B、C和D。 输出格式：对于每个输入文件，输出总和为零的四元组数。 输入示例：6 -45 22 42 -16 -41 -27 56 30 -36 53 -37 77 -36 30 -75 -46 26 -38 -10 62 -32 -54 -6 45输出示例：5

简答

POJ2418—硬木种类 时间限制：10000ms，空间限制：65536K。 问题描述：硬木是植物树群，有宽阔的叶子，产生水果或坚果，并且通常在冬天休眠。美国的温带气候产生了数百种硬木树种，例如橡树、枫树和樱桃都是硬木树种，它们是不同的物种。所有硬木树种共同占美国树木的40%。 利用卫星成像技术，自然资源部编制了一份特定日期的每棵树的清单。你需要计算每个树种的百分比。 输入格式：输入包括卫星观测到的每棵树的树种清单。每行表示一棵树的树种，树种名称不超过30个字符。所有树种不超过10,000种，不超过1,000,000棵树。 输出格式：按字母顺序输出每个树种的名称，以及对应的百分比，百分比精确到第4个小数位。 输入示例： Red Alder Ash Aspen Basswood Ash Beech Yellow Birch Ash Cherry Cottonwood Ash Cypress Red Elm Gum Hackberry White Oak Hickory Pecan Hard Maple White Oak Soft Maple Red Oak Red Oak White Oak Poplan Sassafras Sycamore Black Walnut Willow 输出示例： Ash 13.7931 Aspen 3.4483 Basswood 3.4483 Beech 3.4483 Black Walnut 3.4483 Cherry 3.4483 Cottonwood 3.4483 Cypress 3.4483 Gum 3.4483 Hackberry 3.4483 Hard Maple 3.4483 Hickory 3.4483 Pecan 3.4483 Poplan 3.4483 Red Alder 3.4483 Red Elm 3.4483 Red Oak 6.8966 Sassafras 3.4483 Soft Maple 3.4483 Sycamore 3.4483 White Oak 10.3448 Willow 3.4483 Yellow Birch 3.4483

简答

HDU1263—水果问题 时间限制：2000ms，空间限制：65536K。 问题概述：夏天来了，Joe经营着一个不大的水果店，他认为生存之道就是经营最受顾客欢迎的水果，现在他想要一份水果销售情况的明细表，这样Joe就可以很容易掌握所有水果的销售情况了。 输入格式：第一行正整数n（0<n≤10）表示有n组测试数据。每组测试数据的第一行是一个整数m（0<m≤100），表示共有m次成功的交易。其后有m行数据，每行表示一次交易，由水果名称（小写字母组成，长度不超过80），水果产地（小写字母组成，长度不超过80）和交易的水果数目（正整数，不超过100）组成。< p="" style="box-sizing: border-box; margin: 0px; padding: 0px; user-select: text !important;"></n≤10）表示有n组测试数据。每组测试数据的第一行是一个整数m（0<m≤100），表示共有m次成功的交易。其后有m行数据，每行表示一次交易，由水果名称（小写字母组成，长度不超过80），水果产地（小写字母组成，长度不超过80）和交易的水果数目（正整数，不超过100）组成。<> 输出格式：对于每一组测试数据，请你输出一份排版格式正确（请分析样本输出）的水果销售情况明细表。这份明细表包括所有水果的产地、名称和销售数目的信息，水果先按产地分类，产地按字母顺序排列，同一产地的水果按照名称排序，名称按字母顺序排序。两组测试数据之间有一个空行，最后一组测试数据之后没有空行。 输入示例：1 5 apple shandong 3 pineapple guangdong 1 sugarcane guangdong 1 pineapple guangdong 3 pineapple guangdong 1 输出示例： Guangdong |----pineapple(5) |----sugarcane(1) shandong |----apple(3)