1. 二分法查找适用于何种存储方式的有序表
二分法查找是一种效率比较高的查找方法，在进行二分法查找时，线性表节点必须按关键码值排序，且 线性表是以顺序存储方式存储的。
二分法查找的优点是比较次数少，查找速度快，平均检索长度小，经过｛＿loge n次比较就可以完成查找过程。缺点是在查找之前要为建立有序表付出代价，同时对有序表的插人和删除都需要平均比较和移动表中 的一半元素。一般情况下，二分查找适应于数据相对固定的情况，且二分法查找只适用于线性表的顺序存储。
2. 数据的储存结构主要有哪两种有什么主要区别
数据的储存结构主要有：顺序存储结构和链式存储结构。
主要区别
一、存储单元的连续性不同
链式存储结在构计算机中用一组任意的存储单元存储线性表的数据元素(这组存储单元可以是连续的,也可以是不连续的)。
顺序存储结构在计算机中用一组地址连续的存储单元依次存储线性表的各个数据元素。
二、优缺点不同
空间上
顺序比链式节约空间。是因为链式结构每一个节点都有一个指针存储域。
存储操作上：
顺序支持随机存取，方便操作
插入和删除上：
链式的要比顺序的方便（因为插入的话顺序表也很方便，问题是顺序表的插入要执行更大的空间复杂度，包括一个从表头索引以及索引后的元素后移，而链表是索引后，插入就完成了）
三、适用方向不同
链式存储适用于在较频繁地插入、删除、更新元素时，而顺序存储结构适用于频繁查询时使用。
3. C语言数据结构考试题求各位大哥给答案!!!!!
1、
2、B
3、D
4、C
5、C
6、B
7、D
8、A
9、A
10、
11、c
12、
4. 什么是折半查找法
折半查找法是效率较高的一种查找方法，假设有已经按照从小到大的顺序排列好的五个整数a0~a4，要查找的数是X，其基本思想是：
设查找数据的范围下限为l=0，上限为h=4，求中点m=（l+h）/2，用X与中点元素am比较，若X等于am，即找到，停止查找。
否则，若X大于am，替换下限l=m+1，到下半段继续查找。
若X小于am，换上限h=m-1，到上半段继续查找，如此重复前面的过程直到找到或者l>h为止。
如果l>h，说明没有此数，打印找不到信息，程序结束。
该方法是查找的范围不断缩小一半，所以查找效率较高。
(4)分块查找适用的存储结构扩展阅读
折半查找法优缺点
Bentley在自己的着作《Writing Correct Programs》中写道，90%的计算机专家不能在2小时内写出完全正确的二分搜索算法。
问题的关键在于准确地制定各次查找范围的边界以及终止条件的确定，正确地归纳奇偶数的各种情况，其实整理后可以发现它的具体算法是很直观的。
折半查找法的优点是比较次数少，查找速度快，平均性能好。
其缺点是要求待查表为有序表，且插入删除困难，因此折半查找方法适用于不经常变动而查找频繁的有序列表。
5. 长度为10的表，采用顺序查找法，平均查找长度ASL是 紧急，在线等
1 查找的基本概念
查找 就是在给定的DS中找出满足某种条件的结点；若存在这样的结点，查找成功；否则，查找失败。
查找表 是一组待查数据元素的集合。
静态查找 是仅仅进行查询和检索操作，不改变查找表中数据元素间的逻辑关系的查找。
动态查找 是除了进行查询和检索操作外，还对查找表进行插入、删除操作的查找，动态地改变查找表中数据元素之间的逻辑关系。
平均查找长度 （ASL-Average Search Length）：在查找过程中，对每个结点记录中的关键字要进行反复比较，以确定其位置。因此，与关键字进行比较的平均次数，就成为平均查找长度。它是用来评价一个算法好坏的一个依据。
对含有n个数据元素的查找表，查找成功时的平均查找长度为：
，其中，n是结点的个数；pi是查找第i个结点的概率；ci是找到第i个结点所需比较的次数。
2 线性表的查找
就介绍三种在线性表中进行查找的方法：顺序查找、折半查找和分块查找。
2.1 顺序查找
算法思想：又称线性查找，是一种最简单的查找方法。从第1个元素到最后1个元素，逐个进行比较，直至找到为止。
查找表的存储结构：既适用于顺序存储结构，也适用于链式存储结构。
例，对关键字序列{26，5，37，1，61，11，59，15，48，19}，希望查找关键字：37
顺序查找算法框图：
在等概率情况下，顺序查找成功的平均查找长度为：
顺序查找算法简单，但查找效率低。
2.2 折半查找(又称二分查找)
是查找一个已排好序的表的最好方法。算法思想：
将有序数列的中点设置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。即通过一次比较，将查找区间缩小一半。
二分查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，二分查找的先决条件是查找表中的数据元素必须有序。
算法步骤：
step1 首先确定整个查找区间的中间位置，mid = （ left + right ）/ 2；
step2 用待查关键字值与中间位置的关键字值进行比较：若相等，则查找成功；若大于，则在后半区域继续进行二分查找；若小于，则在前半区域继续进行二分查找。
Step3 对确定的缩小区域再按二分公式，重复上述步骤；
最后 得到结果：要么，查找成功，要么，查找失败。
存储结构：用一维数组存放。
例，对有序表关键字序列{5，10，19，21，31，37，42，48，50，52}，查找k为19及66的记录。
算法描述：
折半查找中查到每一个记录的比较次数可通过二叉树来描述。
因此折半查找成功时进行的比较次数最多不超过树的深度。等概率时，折半查找的平均长度为：
当n很大时，ASLbin = log2(n+1)-1。
2.3 分块查找(又称索引顺序查找)
是顺序查找和折半查找的折中改进方法。
方法描述：将n个数据元素“按块有序”划分为m块（m £ n）。每一块中的结点不必有序，但块与块之间必须“按块有序”，即第1快中任一元素的关键字都必须小于第2块中任一元素的关键字；而第2块中任一元素又都必须小于第3块中的任一元素，……。每个块中元素不一定是有序的。
算法描述：
step1 先选取各块中的最大关键字构成一个索引表；
step2 查找分两个部分：先对索引表进行二分查找或顺序查找，以确定待查记录在哪一块中；在已确定的块中用顺序法进行查找。
例
分块查找的平均查找长度为：
ASLbs = Lb + Lw
3 二叉排序树的查找
前三种查找方法各有千秋。二分法查找效率高，顺序法可以采用链表存储结构，操作灵活。但最好是既有二分法的高效率，又有链表灵活性的查找方法。二叉排序树实际上就是将数据元素组织成二叉树形式，以达到与二分法相同的查找效率，而又具有链表的插入、删除操作的灵活性。
二叉排序树查找步骤：
step1 首先建立起二叉排序树。
step2 将待查关键字值与树根结点进行比较，若相等，查找成功；
step3 否则根据比较结果确定查找路径：若小于根结点的关键字值，则与左子树的根结点的关键字值进行比较；若大于等于根结点的关键字值，则与右子树的根结点的关键字值进行比较。
step4 重复上述步骤，直到要么找到，查找成功；要么找不到，查找失败。
显然，类同折半查找，与关键字最大比较次数为树的深度。因此，二叉树的构造对二叉树的查找效率有很大的影响。
例，若按关键字序列{45，24，55，12，37，53，60，28，40，70}构造二叉树，则
若按关键字序列{12，24，28，37，40，45，53，55，60，70}构造二叉树，则
两棵二叉树的深度分别为4和10。
二叉排序树的平均查找长度为O(log2n)。
4 散列表的查找
前面讨论的查找方法中，结点在表中的位置是随机的，其位置与关键字之间不存在对应关系。因此在查找时，总是进行一系列的和关键字的比较，查找的效率与查找过程中进行比较的次数有关。散列表的查找则是一种不用比较而直接计算出记录所在地址，直接进行查找的方法。散列查找也称为哈希查找(Hashing)。
4.1 散列表的概念
散列表 由散列函数的值组成的表。散列查找是建立在散列表的基础上，它是线性表的一种重要存储方式和检索方法。在散列表中可以实现对数据元素的快速检索。
散列函数 散列表中元素是由散列函数确定的。将数据元素的关键字K作为自变量，通过一定的函数关系（称为散列函数），计算出的值，即为该元素的存储地址。表示为：
Addr = H（key）
例：以学生的学号作为学生记录的关键字，取学号的后两位作为散列后的地址，则可以得到下列这个关键字和地址的散列表：
显然，采用的散列函数为 H(k)=k-525000。
通常关键字集合比地址集合大得多，散列函数是个压缩函数，这样就会产生不同的关键字映射到同一散列地址的情况。如：
可见，三个不同的学号关键字，散列到同一地址79上。这种现象叫冲突。为了不产生冲突现象就要求使用均匀的散列函数，即散列地址是均匀分布的。但由于关键字集合比地址集合大得多，不可能完全避免冲突，因此在冲突出现时就要有解决办法。
4.2 散列函数的构造
散列函数是一个映射，它的设置很灵活，只要使得任何关键字由此所得的散列函数值都出现在表长允许的范围内即可。建立散列函数的原则:
(1) 均匀性: H（key）的值均匀分布在散列表中；
(2) 简单性: 以提高地址计算的速度。
散列函数常用的构造方法：
数字选择法
平方取中法
折叠法
除留余数法（求模取余法）
基数转换法
随机数法
4.2.1 数字选择法
若事先知道关键字集合，当关键字的位数比散列表地址位数多时，则可选取数字分布比较均匀的若干位组成散列地址。
选取的原则：尽量避免计算出的地址有冲突。
例： 有一组由8位数字组成的关键字，如表15.2左边一列所示。
分析这6个关键字可发现，前3位是相同的，第五位也只取2、7两个值，分布不均匀。第4、6、7、8位数字则分布较为均匀，因此，可根据散列表的长度取其中几位或它们的组合作为散列地址。例如，若表长为1000（地址为0～999），则可取4、6、7位的三位数字作为散列地址；若表长为100（地址为0～99），则可取4、6与7、8位之和并舍去进位作为散列地址。
这种方法的前提是：必须能预先估计到所有关键字的每一位上各中数字的分布情况。
4.2.2 平方取中法
通过关键字的平方值扩大差别，取关键字平方后的中间几位或其组合作为散列地址。因为乘积的中间几位数和乘数的每一位都相关，故由此产生的散列地址也较均匀，所取位数由散列表的表长决定。这是一种较常用的构造散列函数的方法。通常在选定散列函数时不知道关键字的全部情况，取其中的哪几位也不一定合适，在这种情况下，取一个数平方后的中间几位数作散列地址。
例： 关键字为 （0100，0110，1010，1001，0111）
关键字的平方结果（0010000，0012100，1020100，1002001，0012321）
若表长为1000，则可取其中间三位作为散列地址集，即
（100，121，201，020，123）
4.2.3 折叠法
若关键字位数很多，可将关键字分割成位数相同的几部分（最后一部分的位数可以不同），然后取这几部分的叠加和（舍去进位）作为散列地址。折叠法又分移位叠加和边界叠加两种。移位叠加是将各段最低位对齐，然后相加；边界叠加则是两个相邻的段沿边界来回折叠，然后对齐相加。
例如：某资料室藏书近万册。采用国际标准图书编号（ISBN），每个编号10位十进制数字。可用折叠法构造一个4位数的哈希函数。
例： 关键字 key=58242324169，取散列表长度为1000，则
4.2.4 除留余数法
取关键字被某个不大于散列表表长m的数p除后所得余数为散列地址。
H（key） = key % p
这是一种最简单，也是最常用的构造散列函数的方法。
例：关键字 32834872 ，散列表长为4位十进制数。
p值可取小于9999的数，例如，取5000；
H（key）= 32834872 % 5000 = 4872
由经验得知：通常选p为小于散列表长的最大素数。
4.2.5 基数转换法
把关键字看成是另一个进制上的数后，再把它转换成原来进制上的数，取其中的若干位作为散列地址。一般取大于原来基数的数作为转换的基数，并且两个基数要互素。
4.2.6 随机数法
选取一个随机函数，取关键字的随机函数值作为它的散列地址，即
H(key)=random(key)
其中random为随机函数。
通常，当关键字长度不等时采用此法构造散列地址较适当。
我自己家的电脑有点问题，不能算出来啦，你自己参考一下吧
6. 二分法查找为什么只适用于顺序存储
举个例子，在1 2 6 4 5 7 8 9 10中，你要用二分法查找6，你得先把6跟中间的5比较，6很明显大于5，所以就只能在5 7 8 9 10中查找，这样很明显找不到，所以二分法必须要求用于顺序排列的数，如果不是顺序排列的，二分法就完全没有意义
7. 什么是查找法
算法思想：
将数列按有序化(递增或递减)排列，查找过程中采用跳跃式方式查找，即先以有序数列的中点位置为比较对象，如果要找的元素值小于该中点元素，则将待查序列缩小为左半部分，否则为右半部分。通过一次比较，将查找区间缩小一半。
折半查找是一种高效的查找方法。它可以明显减少比较次数，提高查找效率。但是，折半查找的先决条件是查找表中的数据元素必须有序。
算法步骤描述：
step1 首先确定整个查找区间的中间位置
mid = （ left + right ）/ 2
step2 用待查关键字值与中间位置的关键字值进行比较；
若相等，则查找成功
若大于，则在后（右）半个区域继续进行折半查找
若小于，则在前（左）半个区域继续进行折半查找
Step3 对确定的缩小区域再按折半公式，重复上述步骤。最后，得到结果：要么查找成功， 要么查找失败。
折半查找的存储结构采用一维数组存放。
折半查找算法举例
对给定数列（有序）{ 3，5，11，17，21，23，28，30，32，50}，按折半查找算法，查找关键字值为30的数据元素。
折半查找的算法讨论：
优点: ASL≤log2n，即每经过一次比较,查找范围就缩小一半。经log2n 次计较就可以完成查找过程。
缺点：因要求有序，所以要求查找数列必须有序，而对所有数据元素按大小排序是非常费时的操作。另外，顺序存储结构的插入、删除操作不便利。
考虑：能否通过一次比较抛弃更多的部分（即经过一次比较，使查找范围缩得更小），以达到提高效率的目的。……？
可以考虑把两种方法（顺序查找和折半查找）结合起来，即取顺序查找简单和折半查找高效之所长，来达到提高效率的目的？实际上这就是分块查找的算法思想。
例如：[问题分析] 由于数据按升序排列,故用折半查找最快捷.
program binsearch;
const max=10;
var num:array[1..max] of integer;
i,n:integer;
procere search(x,a,b:integer);
var mid:integer;
begin
if a=b then
if x=num[a] then writeln('Found:',a) else writeln('Number not found')
else begin
mid:=(a+b) div 2;
if x>num[mid] then search(x,mid,b);
if x<num[mid] then search(x,a,mid);
if x=num[mid] then writeln('Found:',mid);
end;
end;
begin
write('Please input 10 numbers in order:');
for i:=1 to max do read(num);
write('Please input the number to search:');
readln(n);
search(n,1,max);
end.
Java风格的代码举例：
//使用折半法进行查找
int getIndex(int[] nList, int nCount, int nCode) {
int nIndex = -1;
int jMin = 0;
int jMax = nCount - 1;
int jCur = (jMin+jMax)/2;
do
{
if(nList[jCur] > nCode) {
jMax--;
} else if(nList[jCur] < nCode) {
jMin++;
} else if(nList[jCur] == nCode) {
nIndex = jCur;
break;
}
jCur = (jMin + jMax)/2;
} while(jMin < jMax);
return nIndex;
}
二分查找的性能说明
虽然二分查找的效率高，但是要将表按关键字排序。而排序本身是一种很费时的运算。既使采用高效率的排序方法也要花费 O(n lg n) 的时间。
二分查找只适用顺序存储结构。为保持表的有序性，在顺序结构里插入和删除都必须移动大量的结点。因此，二分查找特别适用于那种一经建立就很少改动、而又经常需要查找的线性表。
对那些查找少而又经常需要改动的线性表，可采用链表作存储结构，进行顺序查找。链表上无法实现二分查找
二分查找的C#实现代码：
using System;
using System.Collections.Generic;
using System.Text;
namespace BinschDemo
{
public class BinschDemo
{
public static int Binsch(int[] a, int key)
{
int low = 1;
int high = a.Length;
while (low <= high)
{
int mid = (low + high) / 2;
if (key == a[mid])
{
return mid; //返回找到的索引值
}
else
{
if (key < a[mid])
high = mid - 1;
else
low = mid + 1;
}
}
return -1; //查找失败
}
static void Main(string[] args)
{
Console.WriteLine("请输入10个递增数字: ");
int[] list = new int[10];
for (int i = 0; i < 10; i++)
{
Console.Write("数字 : ", i);
list = Convert.ToInt32(Console.ReadLine());
}
Console.Write("请输入一个你要查找的数字:");
int find = Convert.ToInt32(Console.ReadLine());
int result = Binsch(list, find);
Console.WriteLine(result);
}
}
}
分块查找又索引查找，它主要用于“分块有序”表的查找。所谓“分块有序”是指将线性表L（一维数组）分成m个子表（要求每个子表的长度相等），且第i+1个子表中的每一个项目均大于第i个子表中的所有项目。“分块有序”表应该包括线性表L本身和分块的索引表A。因此，分块查找的关键在于建立索引表A。
（1）建立索引表A（二维数组）
索引表包括两部分：关键字项（子表中的最大值）和指针项（子表的第一项在线性表L中位置）
索引表按关键字有序的。
例如：线性表L（有序）为：1 2 3 4 5 6 7 8 9 10 11 12
分成m=3个子表：{1 2 3 4} {5 6 7 8} {9 10 11 12}
索引表A：二维数组：第一列为每个子表的最大值 ，第二列为每个子表的起始地址
即： 4 0
8 4
12 8
（2）利用索引表A，确定待查项X所在的子表（块）。
（3）在所确定的子表中可以用“折半查找”法搜索待查项X；若找到则输出X；否则输出未找到信息。
8. 数据结构的题，帮忙一下，是一小套题
1. 数据的逻辑结构指的是数据元素之间的 。
2. .线性结构的基本特征是：若至少含有一个结点，则除起始节点没有直接 前驱 外，其他结点有且仅有一个直接 前驱 ；除终端结点没有直接 后继 外，其他结点有且仅有一个直接 后继 。
3. .假设以S和X分别表示入栈和出栈的操作，则对输入序列a,b,c,d,e进行一系列栈操作SSXSXSSXXX后，得到的输出序列为 bceda 。
4. .设S=’I AM A TEACHER’,其长度是 。
5. 若顶点的偶对是有序的，此图为___有向图_____图，有序偶对用________括号括起来；若顶点偶对是无序的，此图为____无向图____图，无序偶对用________括号括起来。
6. 遍历图的基本方法有__深度______优先搜索和 广度________优先搜索两种。
7. 长度为255的表，采用分块查找法，每块的最佳长度是 255/2 。
8. 在对一组记录（4，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第七个记录60插入到有序表时，为寻找插入位置需比较 1 次。
9 数据的逻辑结构是从逻辑关系上描述数据，它与数据的 具体实现 无关，是独立于计算机的。
10.在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head= 。
11.栈顶的位置是随着 进栈和出栈 操作而变化的。
12.在串S="structure"中，以t为首字符的子串有 12 个。
13.已知一棵完全二叉树中共有768结点，则该树中共有 384 个叶子结点。
14．在有序表（12，24，36，48，60，72，84）中二分查找关键字72时所需进行的关键字比较次数2为 。
15.在一个长度为n的顺序表中第i个元素（1<=i<=n）之前插入一个元素时，需向后移动______n-i+1__个元素。
16.在单链表中设置头结点的作用是__使head指向不为空______。
二，选择题
1. 以下说法错误的是( c )
A哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。
B若一个二叉树的树叶是某子树的中序遍历序列中的第一个结点，则它必是该子树的后序遍历序列中的第一个结点。
C已知二叉树的前序遍历和后序遍历序列并不能惟一地确定这棵树，因为不知道树的根结点是哪一个。
D在前序遍历二叉树的序列中，任何结点的子树的所有结点都是直接跟在该结点的之后。
2. 在无向图中，所有顶点的度数之和是所有边数的（ c ）倍。
A 0.5 B 1 C 2 D 4
3. 设有6个结点的无向图，该图至少应有（ A ）条边能确保是一个连通图。
A. 5 B. 6 C. 7 D. 8
4. 以下那一个术语与数据的存储结构无关？（ B ）
A．栈 B. 哈希表 C. 线索树 D. 双向链表
5，顺序查找法适合于存储结构为（ B ）的线性表。
A. 散列存储 B. 顺序存储或链接存储 c. 压缩存储 D. 索引存储
6．有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值为82的结点时，（ B ）次比较后的查找成功。
A. 1 B. 2 C. 4 D. 8
7.排序方法中，从未排序序列中挑选元素并将其依次放入已排序序列（初始为空）的一端的方法，称为（ B ）
A. 希尔排序 B. 归并排序 C 插入排序 D 选择排序
8.算法指的是（D ）
A．计算机程序 B．解决问题的计算方法
C．排序算法 D．解决问题的有限运算序列
9. 二分查找法只适用什么存储结构的线性表,且数据元素必须为什么
说”二分查找法只适用于顺序存储的有序表“是正确的。
说”指线性表中的元素按值非递减排列（即从小到大,但允许相邻元素值相等）“是为了程序的确定性，实际上只要有序就可以，按递减排序也可以用二分法。