数据结构C语言版第八章 查找

第八章查找

重点难点

要求理解"查找表"的结构特点以及各种表示方法的适用性；熟练掌握顺序查找和折半查找的方法；熟悉描述折半查找过程的判定树的构造方法；熟练掌握二叉排序树的构造和查找方法；理解二叉平衡树的构造过程；理解B-和B+树的特点、基本操作和二者的区别。熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；掌握各种不同查找方法之间的区别和各自的适用情况，能按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。

典型例题

1.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度：

(1)查找不成功，即表中无关键字等于给定值K的记录；

(2)查找成功，即表中有关键字等于给定值K的记录。

【解】查找不成功时，需进行n+1次比较才能确定查找失败。因此平均查找长度为n+1，这时有序表和无序表是一样的。

查找成功时，平均查找长度为(n+1)/2,有序表和无序表也是一样的。因为顺序查找与表的初始序列状态无关。

2.画出对长度为18的有序的顺序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。

【解】

等概率情况下，查找成功的平均查找长度为：

ASL=(1+2*2+3*4+4*8+5*3)/18=3.556

查找失败时，最多的关键字比较次树不超过判定树的深度，此处为5.

3.为什么有序的单链表不能进行折半查找?

【解】因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。

4.设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。此命题是否正确?最小元和最大元一定是叶子吗?一个新结点总是插在二叉排序树的某叶子上吗?

【解】此命题正确。假设最小元有左孩子，则根据二叉排序树性质，此左孩子应比最小元更小，如此一来就产生矛盾了，因此最小元不可能有左孩子，对于最大元也是这个道理。

但最大元和最小元不一定是叶子，它也可以是根、内部结点(分支结点)等，这得根据插入结点时的次序而定。

新结点总是作为叶子插入在二叉排序树中的。

5.在一棵m阶的B-树中，当将一关键字插入某结点而引起该结点的分裂时，此结点原有多少个关键字?若删去某结点中的一个关键字，而导致结点合并时，该结点中原有几个关键字?

【解】在一棵m阶的B-树中，若由于一关键字的插入某结点而引起该结点的分裂时，则该结点原有m-1个关键字。

若删去某结点中一个关键字而导致结点合并时，该结点中原有┌m/2┐-1个关键字。6.设散列表长度为11，散列函数h(x)=x%11,给定的关键字序列为：1，13，13，34，38，33，27，22.试画出分别用拉链法和线性探查法解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功和失败时的平均查找长度。请问装填因子的值是什么?

答：

(1)拉链法如下图：

T[0..10]

┌──┐

0││→ 33 → 22 →∧

├──┤

1││→ 1 → 12 →34→ ∧

├──┤

2││→ 13 →∧

├──┤

3│ ∧ │

├──┤

4│ ∧ │

├──┤

5││→ 38 → 27 →∧

├──┤

6│ ∧ │

├──┤

7│∧ │

├──┤

8│ ∧ │

├──┤

9│ ∧ │

├──┤

10│ ∧ │

└──┘

(2)线性探查法如下图：

下

标 0 1 2 3 4 5 6 7 8 9 10

┌─┬─┬─┬─┬─┬─┬─┬─┬─┬─┬─┐T[0..10]│33│1 │13│12│34│38│27│22││││

└─┴─┴─┴─┴─┴─┴─┴─┴─┴─┴─┘探查次数 1 1 1 3 4 1 7 8

用拉链法的查找成功平均查找长度为：

ASLsucc=(1*4+2*3+3*1)/8=1.625

查找失败时平均查找长度为：

ASLunsucc=(2+3+1+0+0+0+2+0+0+0+0)/11=0.73

用线性探查法查找成功时平均查找长度为：

ASLsucc=(1+1+1+3+4+1+7+8)/8=3.25

查找失败时平均查找长度为：

ASLunsucc=(9+8+7+6+5+4+3+2+1+1+1)/11=4.3

装填因子α拉链=4/11=0.36 α线性探查=8/11=0.73

7.试写一算法判别给定的二叉树是否为二叉排序树，设此二叉树以二叉链表为存储结构，且树中结点的关键字均不相同。

【解】由二叉排序树的定义可得：二叉排序树中左子树的所有结点的值都小于根结点的值，所有右子树中结点的值都大于根结点的值。那么只要对待判定的二叉树中的结点按层遍历并判断即可。在该算法中要用到队列保存已遍历的结点指针。

typedef BinTNode *DataType;//循环队列中元素为二叉树结点指针

int BinSortStree(BinTree T)

{

CirQueue Q;

BinTNode *p;

if (!T) return 1;//空树为二叉排序树

InitQueue(&Q);

EnQueue(&Q,T);

while(!QueueEmpty(&Q))

{

p=DeQueue(&Q);

if (p->lchild)

if (p->datalchild->data) return -1;//不是二叉排序树

else EnQueue(&Q,p->lchild);

if (p->rchild)

if (p->data>p->rchild->data) return -1;//不是二叉排序树

else EnQueue(&Q,p->rchild);

}

return 1;//是二叉排序树

}

8.试写一递归算法，从大到小输出二叉排序树中所有其值不小于x的关键字。要求算法的时间为O(lgn+m)，n为树中结点数，m为输出关键字个数(提示：先遍历右子树，后遍历左子树)。

typedef int KeyType； //假定关键字类型为整数

typedef struct node { //结点类型

KeyType key； //关键字项

InfoType otherinfo； //其它数据域，InfoType视应用情况而定，下面不处理它struct node *lchild，*rchild； //左右孩子指针

} BSTNode；

typedef BSTNode *BSTree；

void OUTPUTNODE(BSTree T,KeyType x)

{//从大到小输出二叉排序树中所有其值不小于x的关键字

if (T)

{

OUTPUTNODE( T->rchild,x);

if (T->key>=x) printf("%d",T->key);

OUTPUTNODE( T->Lchild,x);

}

}

习题精选

1．选择题

（1）对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长度为（）。

A．(n-1)/2 B．n/2 C．(n+1)/2D．n

（2）适用于折半查找的表的存储方式及元素排列要求为（）。

A．链接方式存储，元素无序B．链接方式存储，元素有序

C．顺序方式存储，元素无序D．顺序方式存储，元素有序（3）当在一个有序的顺序表上查找一个数据时，既可用折半查找，也可用顺序查找，但前者比后者的查找速度（）。

A．必定快B．不一定

C．在大部分情况下要快D．取决于表递增还是递减（4）折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中（）比较大小，查找结果是失败。

A．20，70，30，50 B．30，88，70，50

C．20，50 D．30，88，50

（5）对22个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。

A．3 B．4 C．5 D．6

（6）折半搜索与二叉排序树的时间性能（）。

A．相同B．完全不同

C．有时不相同D．数量级都是O(log2n) （7）分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是（）。

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)

（8）在平衡二叉树中插入一个结点后造成了不平衡，设最低的不平衡结点为A，并已知A的左孩子的平衡因子为0右孩子的平衡因子为1，则应作（）型调整以使其平衡。

A．LL B．LR C．RL D．RR

（9）下列关于m阶B-树的说法错误的是（）。

A．根结点至多有m棵子树

B．所有叶子都在同一层次上

C．非叶结点至少有m/2 (m为偶数)或m/2+1（m为奇数）棵子树

D．根结点中的数据是有序的

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

A．B-树和B+树都是平衡的多叉树B．B-树和B+树都可用于文件的索引结构C．B-树和B+树都能有效地支持顺序检索D．B-树和B+树都能有效地支持随机检索（11）m阶B-树是一棵（）。

A．m叉排序树B．m叉平衡排序树

C．m-1叉平衡排序树D．m+1叉平衡排序树

（12）下面关于哈希查找的说法，正确的是（）。

A．哈希函数构造的越复杂越好，因为这样随机性好，冲突小

B．除留余数法是所有哈希函数中最好的

C．不存在特别好与坏的哈希函数，要视情况而定

D．哈希表的平均查找长度有时也和记录总数有关

（13）下面关于哈希查找的说法，不正确的是（）。

A．采用链地址法处理冲突时，查找一个元素的时间是相同的

B．采用链地址法处理冲突时，若插入规定总是在链首，则插入任一个元素的时间是相同的

C．用链地址法处理冲突，不会引起二次聚集现象

D．用链地址法处理冲突，适合表长不确定的情况

（14）设哈希表长为14，哈希函数是H(key)=key%11，表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的元素加到表中，用二次探测法解决冲突，则放入的位置是（）。

A．8 B．3 C．5 D．9 （15）采用线性探测法处理冲突，可能要探测多个位置，在查找成功的情况下，所探测的这些位置上的关键字( )。

A．不一定都是同义词B．一定都是同义词

C．一定都不是同义词D．都相同

2．应用题

（1）假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：

①画出描述折半查找过程的判定树；

②若查找元素54，需依次与哪些元素比较？

③若查找元素90，需依次与哪些元素比较？

④假定每个元素的查找概率相等，求查找成功时的平均查找长度。

①先画出判定树如下（注：mid=?(1+12)/2?=6）：

30

5 63

3 7 42 87

4 24 54 72 95

②查找元素54，需依次与30, 63, 42, 54 元素比较；

③查找元素90，需依次与30, 63,87, 95元素比较；

④求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；

但最后一层未满，不能用8×4，只能用5×4=20次，

所以ASL＝1/12（17＋20）＝37/12≈3.08

（2）在一棵空的二叉排序树中依次插入关键字序列为12，7，17，11，16，2，13，9，21，4，请画出所得到的二叉排序树。

12

717

2 11 16 21

4 9 13

验算方法：用中序遍历应得到排序结果：2,4,7,9,11,12,13,16,17，21

（3）已知如下所示长度为12的表：（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）

①试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

②若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。

③按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

解：

①插入90 ②插入25 ③插入45 ④删除60

（5）设哈希表的地址范围为0～17，哈希函数为：H（key）=key%16。用线性探测法处理冲突，输入关键字序列：（10，24，32，17，31，30，46，47，40，63，49），构造哈希表，试回答下列问题：

①画出哈希表的示意图；

②若查找关键字63，需要依次与哪些关键字进行比较？

③若查找关键字60，需要依次与哪些关键字比较？

④假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

①画表如下：

查找63,首先要与H(63)=63%16=15号单元内容比较，即63 vs 31 ,no;

然后顺移，与46,47,32,17,63相比，一共比较了6次！

③查找60,首先要与H(60)=60%16=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。

④对于黑色数据元素，各比较1次；共6次；

对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，

所以ASL=1/11（6＋2＋3×3+6）＝23/11

（6）设有一组关键字（9，01，23，14，55，20，84，27），采用哈希函数：H（key）=key %7 ，表长为10，用开放地址法的二次探测法处理冲突。要求：对该关键字序列构造哈希表，并计算查找成功的平均查找长度。

succ

以关键字27为例：H（27）=27%7=6（冲突） H1=（6+1）%10=7（冲突）

H2=（6+22）%10=0（冲突） H3=（6+33）%10=5 所以比较了4次。

（7）设哈希函数H（K）=3 K mod 11，哈希地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，12），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASL succ和ASL unsucc。

①线性探测法；

②链地址法。

①

succ

ASL unsucc=（1+2+1+8+7+6+5+4+3+2+1）/11=40/11

②

ASL succ =（1*5+2*3）/8=11/8

ASL unsucc=（1+2+1+2+3+1+3+1+3+1+1）/11=19/11

数据结构C语言版期末考试试题(有答案)

“数据结构”期末考试试题 一、单选题(每小题2分，共12分) 1．在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。 A． HL＝ps p一>next＝HL B． p一>next＝HL；HL＝p3 C． p一>next＝Hl；p＝HL； D． p一>next＝HL一>next;HL一>next＝p； 2．n个顶点的强连通图中至少含有( )。 A.n—l条有向边 B.n条有向边 C.n(n—1)／2条有向边 D.n(n一1)条有向边 3.从一棵二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A.O(1) B.O(n) C.O(1Ogzn) D.O(n2) 4．由权值分别为3，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 A．24 B．48 C． 72 D． 53 5．当一个作为实际传递的对象占用的存储空间较大并可能需要修改时，应最好把它说明为( )参数，以节省参数值的传输时间和存储参数的空间。 A.整形 B.引用型 C.指针型 D.常值引用型· 6．向一个长度为n的顺序表中插人一个新元素的平均时间复杂度为( )。 A．O(n) B．O(1) C．O(n2) D．O(10g2n) 二、填空题(每空1分，共28分) 1．数据的存储结构被分为——、——、——和——四种。 2．在广义表的存储结构中，单元素结点与表元素结点有一个域对应不同，各自分别为——域和——域。 3．——中缀表达式 3十x*(2.4／5—6)所对应的后缀表达式为————。 4．在一棵高度为h的3叉树中，最多含有——结点。 5．假定一棵二叉树的结点数为18，则它的最小深度为——，最大深度为——· 6．在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定——该结点的值，右子树上所有结点的值一定——该结点的值。 7．当向一个小根堆插入一个具有最小值的元素时，该元素需要逐层——调整，直到被调整到——位置为止。 8．表示图的三种存储结构为——、——和———。 9．对用邻接矩阵表示的具有n个顶点和e条边的图进行任一种遍历时，其时间复杂度为——，对用邻接表表示的图进行任一种遍历时，其时间复杂度为——。 10．从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为——和——· 11．假定对长度n＝144的线性表进行索引顺序查找，并假定每个子表的长度均

数据结构c语言版期末考试复习试题

《数据结构与算法》复习题 一、选择题。 1在数据结构中，从逻辑上可以把数据结构分为 C 。 A ?动态结构和静态结构B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 2?数据结构在计算机内存中的表示是指_A_。 A .数据的存储结构B.数据结构 C .数据的逻辑结构 D .数据元素之间的关系 3.在数据结构中，与所使用的计算机无关的是数据的A结构。 A .逻辑 B .存储C.逻辑和存储 D .物理 4.在存储数据时，通常不仅要存储各数据元素的值，而且还要存储_C A .数据的处理方法 B .数据元素的类型 C.数据元素之间的关系 D .数据的存储方法 5.在决定选取何种存储结构时，一般不考虑A A .各结点的值如何C.对数据有哪些运算 B .结点个数的多少 D .所用的编程语言实现这种结构是否方 6.以下说法正确的是D A .数据项是数据的基本单位 B .数据元素是数据的最小单位 C.数据结构是带结构的数据项的集合 D .一些表面上很不相同的数据可以有相同的逻辑结构 7.算法分析的目的是 C ，算法分析的两个主要方面是 A 。 (1) A .找出数据结构的合理性B.研究算法中的输入和输出的关系 C .分析算法的效率以求改进C.分析算法的易读性和文档性 (2) A .空间复杂度和时间复杂度B.正确性和简明性 &下面程序段的时间复杂度是0( n2) s =0; for( I =0; i

数据结构(c语言版)期末考试复习试题

《数据结构与算法》（c语言版）期末考复习题 一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位

B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。（1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i

数据结构(C语言版)期末复习

数据结构（C语言版）期末复习汇总 第一章绪论 数据结构：是一门研究非数值计算程序设计中的操作对象，以及这些对象之间的关系和操作的学科。 数据结构分为：逻辑结构、物理结构、操作三部分 逻辑结构：集合、线性结构、树形结构、图（网）状结构 物理结构（存储结构）：顺序存储结构、链式存储结构 算法：是为了解决某类问题而规定的一个有限长的操作序列。 算法五个特性：有穷性、确定性、可行性、输入、输出 评价算法优劣的基本标准（4个）：正确性、可读性、健壮性、高效性及低存储量 语句频度的计算。 算法的时间复杂度： 常见有：O(1)，O(n)，O(n2)，O(log2n)，O(nlog2n)，O(2n) 第二章线性表 线性表的定义和特点： 线性表：由n(n≥0)个数据特性相同的元素构成的有限序列。线性表中元素个数n(n≥0)定义为线性表的长度，n=0时称为空表。 非空线性表或线性结构，其特点： （1）存在唯一的一个被称作“第一个”的数据元素； （2）存在唯一的一个被称作“最有一个”的数据元素； （3）除第一个之外，结构中的每个数据元素均只有一个前驱； （4）除最后一个之外，结构中的每个数据元素均只有一个后继。 顺序表的插入：共计n个元素，在第i位插入，应移动（n-i+1）位元素。 顺序表的删除：共计n个元素，删除第i位，应移动（n-i）位元素。 线性表的两种存储方式：顺序存储、链式存储。 顺序存储 概念：以一组连续的存储空间存放线性表； 优点：逻辑相邻，物理相邻；可随机存取任一元素；存储空间使用紧凑； 缺点：插入、删除操作需要移动大量的元素；预先分配空间需按最大空间分配，利用不充分；表容量难以扩充； 操作：查找、插入、删除等 查找： ListSearch(SqlList L,ElemType x,int n) { int i; for (i=0;i

《数据结构》习题汇编08_第八章_查找_试题

数据结构课程（本科）第七章试题 一、单项选择题 1.若搜索每一个元素的概率相等，则在长度为n的顺序表上搜索到表中任一元素的平均搜索长度为 （）。 A. n B. n+1 C. (n-1)/2 D. (n+1)/2 2.对长度为10的顺序表进行搜索，若搜索前面5个元素的概率相同，均为1/8，搜索后面5个元素的概 率相同，均为3/40，则搜索到表中任一元素的平均搜索长度为（）。 A. 5.5 B. 5 C. 39/8 D. 19/4 3.对长度为3的顺序表进行搜索，若搜索第一个元素的概率为1/2，搜索第二个元素的概率为1/3，搜索 第三个元素的概率为1/6，则搜索到表中任一元素的平均搜索长度为（）。 A. 5/3 B. 2 C. 7/3 D. 4/3 4.对长度为n的有序单链表，若搜索每个元素的概率相等，则顺序搜索到表中任一元素的平均搜索长度 为（）。 A. n/2 B. (n+1)/2 C. (n-1)/2 D. n/4 5.对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（）的值 的向上取整。 A. log2(n+1) B. log2n C. n/2 D. (n+1)/2 6.对于长度为n的有序顺序表，若采用折半搜索，则对所有元素的搜索长度中最大的为（）的值 的向下取整加一。 A. log2(n+1) B. log2n C. n/2 D. (n+1)/2 7.对于长度为9的有序顺序表，若采用折半搜索，在等概率情况下搜索成功的平均搜索长度为（） 的值除以9。 A. 20 B. 18 C. 25 D. 22 8.对于长度为18的有序顺序表，若采用折半搜索，则搜索第15个元素的搜索长度为（）。 A. 3 B. 4 C. 5 D. 6 9.对具有n个元素的有序顺序表进行折半搜索，则搜索任一元素的时间复杂度为（）。 A. O(n) B. O(n2) C. O(1) D. O(log2n) 10.在一棵高度为h的具有n个元素的二叉搜索树中，搜索所有元素的搜索长度中最大的为（）。 A. n B. log2n C. (h+1)/2 D. h+1 11.从具有n个结点的二叉搜索树中搜索一个元素时，在等概率情况下进行成功搜索的时间复杂度大致为 （）。 A. O(n) B. O(1) C. O(log2n) D. O(n2)

数据结构第八章习题及答案

习题八查找 一、单项选择题 1．顺序查找法适合于存储结构为（）的线性表。 A．散列存储 B. 顺序存储或链式存储 C. 压缩存储 D. 索引存储 2.若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为( )。 A． (n-1)/2 B. n/2 C. (n+1)/2 D. n 3．适用于折半查找的表的存储方式及元素排列要求为( ) A．链接方式存储，元素无序 B．链接方式存储，元素有序 C．顺序方式存储，元素无序 D．顺序方式存储，元素有序 4．当在一个有序的顺序存储表上查找一个数据时，即可用折半查找，也可用顺序查找，但前者比后者的查找速度( ) A．必定快 B.不一定 C. 在大部分情况下要快 D. 取决于表递增还是递减5．当采用分块查找时，数据的组织方式为 ( ) A．数据分成若干块，每块内数据有序 B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块 C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块 D. 数据分成若干块，每块（除最后一块外）中数据个数需相同 6．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。这种说法（）。 A．正确 B. 错误 7. 二叉查找树的查找效率与二叉树的(（1） )有关, 在 (（2） )时其查找效率最低。 (1): A. 高度 B. 结点的多少 C. 树型 D. 结点的位置 (2): A. 结点太多 B. 完全二叉树 C. 呈单枝树 D. 结点太复杂。 8．如果要求一个线性表既能较快的查找，又能适应动态变化的要求，则可采用( )查找法。 A. 分快查找 B. 顺序查找 C. 折半查找 D. 基于属性 9．分别以下列序列构造二叉排序树，与用其它三个序列所构造的结果不同的是( )。 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) 10．下图所示的4棵二叉树,( )是平衡二叉树。 （A）（B）（C）（D） 11．散列表的平均查找长度（）。 A．与处理冲突方法有关而与表的长度无关 B．与处理冲突方法无关而与表的长度有关 C．与处理冲突方法有关且与表的长度有关 D．与处理冲突方法无关且与表的长度无关 12. 设有一组记录的关键字为{19，14，23，1，68，20，84，27，55，11，10，79}，用链地址法构造散列表，散列函数为H（key）=key MOD 13,散列地址为1的链中有（）个

数据结构C语言版第八章 查找

第八章查找 重点难点 要求理解"查找表"的结构特点以及各种表示方法的适用性；熟练掌握顺序查找和折半查找的方法；熟悉描述折半查找过程的判定树的构造方法；熟练掌握二叉排序树的构造和查找方法；理解二叉平衡树的构造过程；理解B-和B+树的特点、基本操作和二者的区别。熟练掌握哈希表的构造方法，深刻理解哈希表与其它结构的表的实质性的差别；掌握各种不同查找方法之间的区别和各自的适用情况，能按定义计算各种查找方法在等概率情况下查找成功时的平均查找长度。 典型例题 1.若对具有n个元素的有序的顺序表和无序的顺序表分别进行顺序查找，试在下述两种情况下分别讨论两者在等概率时的平均查找长度： (1)查找不成功，即表中无关键字等于给定值K的记录； (2)查找成功，即表中有关键字等于给定值K的记录。 【解】查找不成功时，需进行n+1次比较才能确定查找失败。因此平均查找长度为n+1，这时有序表和无序表是一样的。 查找成功时，平均查找长度为(n+1)/2,有序表和无序表也是一样的。因为顺序查找与表的初始序列状态无关。 2.画出对长度为18的有序的顺序表进行二分查找的判定树，并指出在等概率时查找成功的平均查找长度，以及查找失败时所需的最多的关键字比较次数。 【解】 等概率情况下，查找成功的平均查找长度为： ASL=(1+2*2+3*4+4*8+5*3)/18=3.556 查找失败时，最多的关键字比较次树不超过判定树的深度，此处为5. 3.为什么有序的单链表不能进行折半查找?

【解】因为链表无法进行随机访问，如果要访问链表的中间结点，就必须先从头结点开始进行依次访问，这就要浪费很多时间，还不如进行顺序查找，而且，用链存储结构将无法判定二分的过程是否结束，因此无法用链表实现二分查找。 4.设二叉排序树中关键字互不相同，则其中最小元必无左孩子，最大元必无右孩子。此命题是否正确?最小元和最大元一定是叶子吗?一个新结点总是插在二叉排序树的某叶子上吗? 【解】此命题正确。假设最小元有左孩子，则根据二叉排序树性质，此左孩子应比最小元更小，如此一来就产生矛盾了，因此最小元不可能有左孩子，对于最大元也是这个道理。 但最大元和最小元不一定是叶子，它也可以是根、内部结点(分支结点)等，这得根据插入结点时的次序而定。 新结点总是作为叶子插入在二叉排序树中的。 5.在一棵m阶的B-树中，当将一关键字插入某结点而引起该结点的分裂时，此结点原有多少个关键字?若删去某结点中的一个关键字，而导致结点合并时，该结点中原有几个关键字? 【解】在一棵m阶的B-树中，若由于一关键字的插入某结点而引起该结点的分裂时，则该结点原有m-1个关键字。 若删去某结点中一个关键字而导致结点合并时，该结点中原有┌m/2┐-1个关键字。6.设散列表长度为11，散列函数h(x)=x%11,给定的关键字序列为：1，13，13，34，38，33，27，22.试画出分别用拉链法和线性探查法解决冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功和失败时的平均查找长度。请问装填因子的值是什么? 答： (1)拉链法如下图： T[0..10] ┌──┐ 0││→ 33 → 22 →∧ ├──┤ 1││→ 1 → 12 →34→ ∧ ├──┤ 2││→ 13 →∧ ├──┤ 3│ ∧ │ ├──┤ 4│ ∧ │ ├──┤ 5││→ 38 → 27 →∧ ├──┤ 6│ ∧ │ ├──┤ 7│∧ │

数据结构练习第八章-查找

数据结构练习第八章查找 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(log 2 n) C. O(n) D. O(n2) 3．在二叉排序树中插入一个结点的时间复杂度为（）。 A. O(1) B. O(n) C. O(log 2 n) D. O(n2) 4．设有序顺序表中有n个数据元素，则利用二分查找法查找数据元素X的最多比较次数不超过（）。 A. log 2n+1 B. log 2 n-1 C. log 2 n D. log 2 (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(1og 2 n) 7．设二叉排序树上有n个结点，则在二叉排序树上查找结点的平均时间复杂度为（）。 A. O(n) B. O(n2) C. O(nlog 2n) D. O(1og 2 n) 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(1og 2n) C. O(nlog 2 n) D. O(n2) 12．设一个顺序有序表A[1:14]中有14个元素，则采用二分法查找元素A[4]的过程中比较元素的顺序为( )。 A. A[1]，A[2]，A[3]，A[4] B.A[1]，A[14]，A[7]，A[4] C.A[7]，A[3]，A[5]，A[4] D. A[7]，A[5] ，A[3]，A[4] 13．设散列表中有m个存储单元，散列函数H(key)= key % p，则p最好选择（）。 A. 小于等于m的最大奇数 B.小于等于m的最大素数 C. 小于等于m的最大偶数 D. 小于等于m的最大合数 14．设顺序表的长度为n，则顺序查找的平均比较次数为（）。 A. n B. n/2 C. (n+1)/2 D. (n-1)/2 15．设有序表中的元素为(13，18，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。 A. 1 B. 2 C. 3 D. 4

数据结构 第八章 查找自测题

第9章查找自测卷姓名班级 一、填空题（每空1分，共10分） 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是。 2. 线性有序表（a1，a2，a3，…，a256）是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索次。设有100个结点，用二分法查找时，最大比较次数是。 3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结 点数为；比较四次查找成功的结点数为；平均查找长度为。 4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素比较大小。 5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。 6. 散列法存储的基本思想是由决定数据的存储地址。 7. 有一个表长为m的散列表，初始状态为空，现将n（n

《数据结构(C语言描述)》期末试卷要点

专业 《数据结构（C 语言描述）》期末试卷 （ — 学年 第 学期） 一、填空(10分) 1、一个m 阶B-树中，每个结点最少有( ceil(m/2) )个儿子结点,m 阶B+树中每个结点(除根外)最多有( m )个儿子结点. 2、n(n>0)个结点构成的二叉树，叶结点最多有( floor((n+1)/2) )个，最少有( 1 )个。若二叉树有m 个叶结点，则度为2的结点有( m-1 )个。 3、顺序查找方法适用于存储结构为( 顺序表和线性链表 )的线性表，使用折半查找方法的条件是(查找表为顺序存贮的有序表 ) 4、广义表A=(( )，(a ，(b ，c))，d)的表尾Gettail(A)为( ((a,(b,c)),d) ) 5、直接插入排序，起泡排序和快速排序三种方法中，( 快速排序 )所需的平均执行时间最小；( 快速排序 )所需附加空间最大。 二、选择(10分) 1、倒排文件的主要优点是：( C ) A 、便于进行插入和删除 B 、便于进行文件的合并 C 、能大大提高基于非主关键字数据项的查找速度 D 、易于针对主关键字的逆向检索 2 下面程序段的时间复杂性为( C ) y=0; while(n>=(y+1)*(y+1)) { y++; } A 、O(n) B 、O(n 2) C 、 O(sqrt(n)) D 、 O(1) 3、若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是( C ) A 、二叉排序树 B 、哈夫曼树 C 、堆 D 、AVL 树 4、栈和队列都是（ B ） A 、顺序存储的线性结构 B 、限制存取点的线性结构 C 、链式存储的线性结构 D 、限制存取点的非线性结构 5、用顺序查找方法查找长度为n 的线性表时，在等概率情况下的平均查找长度为（ D ） A 、n B 、n/2 C 、(n-1)/2 D 、(n+1)/2 三、简答（30分） 1、已知一棵二叉树的前序扫描序列和中序扫描序列分别为ABCDEFGHIJ 和BCDAFEHJIG ，试给出该二叉树的后序序列并绘出该二叉树对应的森林。 院（系） 班级 姓名 学号 ……………………………………………装…………………………订………………………线……………………………………………

数据结构(c语言版)复习资料

数据结构复习资料 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有 1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 11. 一个算法的效率可分为时间效率和空间效率。

12. 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。 13. 线性表中结点的集合是有限的，结点间的关系是一对一的。 14. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。 15. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。 16. 在顺序表中访问任意一结点的时间复杂度均为 O(1)，因此，顺序表也称为随机存取的数据结构。 17. 顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。 18．在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。 19．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。 20. 向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 21. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。 22. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 23. 不包含任何字符（长度为0）的串称为空串；由一个或多个空格（仅由空格符）组成的串称为空白串。 24. 子串的定位运算称为串的模式匹配；被匹配的主串称为目标串，子串称为模式。

数据结构c语言版期末考试复习试题

《数据结构与算法》复习题一、选择题。 1．在数据结构中，从逻辑上可以把数据结构分为 C 。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指 A 。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C 。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑 A 。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是 D 。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是 C ，算法分析的两个主要方面是 A 。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O(n2) 。 s =0; for( I =0; i

数据结构第8章 查找 答案

第8章 查找 测试题 及答案 一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是 顺序查找（线性查找） 。 2. 线性有序表（a 1，a 2，a 3，…，a 256)是从小到大排列的，对一个给定的值k ，用二分法检索表中与k 相等的元素，在查找不成功的情况下，最多需要检索 8 次。设有100个结点，用二分法查找时，最大比较次数是 7 。 3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为 2 ；比较四次查找成功的结点数为 8 ；平均查找长度为 3.7 。 解：显然，平均查找长度＝O （log 2n ）<5次（25）。但具体是多少次，则不应当按照公式 )1(log 12++=n n n ASL 来计算（即（21×log 221）/20＝4.6次并不正确！）。因为这是在假设n ＝2m -1的情况下推导出来的公式。应当用穷举法罗列： 全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL ＝74/20=3.7 ！！！ 4．【计研题2000】折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。 5. 在各种查找方法中，平均查找长度与结点个数n 无关的查找方法是 散列查找 。 6. 散列法存储的基本思想是由 关键字的值 决定数据的存储地址。 7. 有一个表长为m 的散列表，初始状态为空，现将n （n

数据结构教案C语言版

数据结构教案C语言版 Last updated on the afternoon of January 3, 2021

课程教案 课程名称：数据结构 授课教师： 学习对象： 任课时间： 一、学生情况分析 数据结构是计算机专业的一门核心专业课程。学生在前期的学习中已经学习了C语言程序设计课程。通过本课程学习使学生对提高编写程序的能力以及解决实际问题的能力。 二、课程教学目标 《数据结构》是计算机学科中一门核心专业基础课。主要介绍如何合理地组织数据、有效地存储和处理数据，正确地设计算法以及对算法的分析和评价。通过本课程的学习，使学生深透地理解数据结构的逻辑结构和物理结构的基本概念以及有关算法，培养基本的、良好的程序设计技能，编制高效可靠的程序，为学习操作系统、编译原理和数据库等课程奠定基础。 三、课程教学内容 第一章绪论 教学内容： 1）什么是数据结构

2）抽象数据类型概念；数据类型；数据抽象与抽象数据类型；用于描述数据结构的语言 3）数据结构的抽象层次 4）算法定义 5）性能分析与度量；算法的性能标准；算法的后期测试；算法的事前估计；空间复杂度度量；时间复杂度度量；时间复杂度的渐进表示法； 教学要求： 了解：数据结构基本概念及数据结构的抽象层次 了解：抽象数据类型概念 了解：算法的定义及算法特性 掌握：算法的性能分析与度量方法 第二章线性表 教学内容： 1）线性表的定义和特点 2）线性表的顺序存储及查找、插入和删除操作 3）线性表的链式存储及查找、插入和删除操作 4）使用线性表的实例 教学要求： 了解：线性表的定义和特点 熟练掌握：线性表的顺序存储结构的查找、插入和删除等基本操作 熟练掌握：单链表、循环链表及双向链表的定义及实现 掌握：熟练掌握单链表的应用方法

数据结构练习8

第八章查找 习题 9．1 判断题(在你认为正确的题后的括号中打√，否则打X)。 (1)用来惟一区分文件中不同记录的属性或属性组称为主关键字。( ) (2)查找成功与否的关键在于是否按主关键字查找。( ) (3)顺序文件必须用一片地址连续的存储空间来存放。( ) (4)只有在顺序存储结构上才能采用顺序查找方法。( ) (7)只要按值有序排列的线性表采用顺序存储结构就可以采用折半查找方法。( ) (8)建立稠密索引的优点是节省存储空间。( ) (9)分块查找的效率与文件中的记录被分成多少块有关。( ) (10)分块查找过程是首先查找索引表，然后再到相应的块中具体查找记录。( ) (11)B-树和B十树都是用来实现动态索引的。( ) (12)在B-树上可以进行顺序查找。( 1 (13)在B+树上可以进行顺序查找。／ 1 (14)采用散列方法存储线性表，不能存储数据元素之间的关系。( ) (15)在散列文件中进行查找不涉及关键字的比较。( ) (16)散列冲突是指同一个关键字对应了多个不同的散列地址。( ) (17)散列表的负载因子等于存人散列表中的关键字的个数。( ) (18)在散列表的查找过程中，关键字的比较次数与表中关键字的数目直接相关。( ) (19)在利用线性探测法处理冲突的散列表中，散列函数值相同的关键字总是存放在一片地址连续的存储单元中。 (20)在采用链地址法处理冲突的散列表中，散列函数值相同的关键字是链接在同一个链表中的。( ) 9．2单项选择题。 (1)衡量查找算法性能好坏的主要标准是。 A．参加比较的关键字值的多少 B．被查找的关键字值在关键字序列中的位置 C.关键字序列中是否存在被查找关键字值 D．关键字值的平均比较次数的多少 (2)顺序查找方法的优点之一是—。· A．对于被查找对象几乎没有限制B．适合排序连续顺序文件的查找 C.适合链接顺序文件的查找D．查找时间效率高 (3)对线性表采用折半查找，该线性表必须。 A．元素按值有序排列B．采用顺序结构 C．元素按值有序排列，并且采用顺序存储结构 n元素按值有序排列，并且采用链式存储结构 (4)下面的说法中，不正确的是——。 A．折半查找方法不适用于按值有序链接的链表的查找 B．折半查找方法适用于按值有序的顺序表的查找 C.折半查找方法适用于按关键字值大小有序排列的顺序文件的查找 D．折半查找方法适用于排序连续顺序文件的查找 (5)在有序表(k1，k2，…，k9，)中采用折半查找方法查找99次，其中，至少有一个元素被比较了99次，该元素是——。

数据结构第8章 查找 答案

第8章查找测试题及答案一、填空题 1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是顺序查找（线性查找）。 2. 线性有序表（a，a，a，…，a)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相123256等的元素，在 查找不成功的情况下，最多需要检索8 次。设有100个结点，用二分法查找时，最大比较次 数是7。 3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1； 比较两次查找成功的结点数为 2；比较四次查找成功的结点数为 8；平均查找长度为 3.7。 5解：显然，平均查找长度＝O（logn）<5次（2）。但具体是多少次，则不应当按照公式2m来计算（即 （21×log21）/20＝4.6次并不正确！）。因为这是在假设n＝2-1的情况下22n推导出来的公式。应当用穷举法罗列：全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7 ！！！4．【计研 题2000】折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20， 它将依次与表中元素 28，6，12，20比较大小。 5. 在各种查找方法中，平均查找长度与结 点个数n无关的查找方法是散列查找。 6. 散列法存储的基本思想是由关键字的值决定数 据的存储地址。 7. 有一个表长为m的散列表，初始状态为空，现将n（n

数据结构第8章查找练习题

一、单选题 1．下列查找方法中，不属于动态的查找方法是( )。 A ．二叉排序树法 B ．平衡树法 C ．散列法 D ．二分查找法 2．适用于静态的查找方法为( )。 A ．二分查找、二叉排序树查找 B ．二分查找、索引顺序表查找 C ．二叉排序树查找、索引顺序表查找 D ．二叉排序树查找、散列法查找 3．静态查找表与动态查找表二者的根本差别在于( )。 A ．它们的逻辑结构不一样 B ．施加在其上的操作不同 C ．所包含的数据元素的类型不一样 D ．存储实现不一样 4．对长度为10的顺序表进行查找，若查找前面5个元素的概率相同，均为1/8，查找后面5个元素的概率相同，均为3/40，则查找任一元素的平均查找长度为( )。 A ．5.5 B ．5 C ．39/8 D ．19/4 5．( )存储方式适用于折半查找。 A ．键值有序的单链表 B ．键值有序的顺序表 C ．键值有序的双链表 D ．键值无序的顺序表 6．对线性表进行二分查找时，要求线性表必须( )。 A ．以顺序方式存储 B ．以链接方式存储 C ．顺序存储，且结点按关键字有序排序 D ．链式存储，且结点按关键字有序排序 7．在索引顺序表中查找一个元素，可用的且最快的方法是( )。 A ．用顺序查找法确定元素所在块，再用顺序查找法在相应块中查找 B ．用顺序查找法确定元素所在块，再用二分查找法在相应块中查找 C ．用二分查找法确定元素所在块，再用顺序查找法在相应块中查找 D ．用二分查找法确定元素所在块，再用二分查找法在相应块中查找 8．在索引查找中，若主表长度为144，它被均分为12子表，每个子表的长度均为12，则索引查找的平均查找长度为( )。 A ．13 B ．24 C ．12 D ．79 9．由同一关键字集合构造的各棵二叉排序树( )。 A ．形态和平均查找长度都不一定相同 B ．形态不一定相同，但平均查找长度相同 C ．形态和平均查找长度都相同 D ．形态相同，但平均查找长度不一定相同 10．对二叉排序树进行( )，可以得到各结点键值的递增序列。 A ．先根遍历 B ．中根遍历 C ．层次遍历 D ．后根遍历 11．下述序列中，哪个可能是在二叉排序树上查找35时所比较过的关键字序列？ A ．2，25，40，39，53，34，35 B ．25，39，2，40，53，34，35 C ．53，40，2，25，34，39，35 D ．39，25，40，53，34，2，35 12．在A VL 树中，每个结点的平衡因子的取值范围是( )。 A ．-1~1 B ．-2~2 C ．1~2 D ．0~1 13．在AVL 树中，任一结点的( )。 A ．左、右子树的高度均相同 B ．左、右子树高度差的绝对值不超过1 C ．左、右子树的结点数均相同 D ．左、右子树结点数差的绝对值不超过1 14．下面关于B 树和B +树的叙述中，不正确的是 A ．都是平衡的多叉树 B ．都是可用于文件的索引结构 C ．都能有效地支持顺序检索 D ．都能有效地支持随机检索 15．右图是一棵( )。 2822221915100528 2610

严蔚敏数据结构题集C语言版完整答案

严蔚敏 数据结构C 语言版答案详解 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解：抽象数据类型包含一般数据类型的概念，但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义，直接提供给编程者定义用户数据，因此称它们为预定义数据类型。抽象数据类型通常由编程者定义，包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时，要求只定义到数据的逻辑结构和操作说明，不考虑数据的存储结构和操作的具体实现，这样抽象层次更高，更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R)，其中 {}4,3,2,1d d d d D =，{}r R =，()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解： 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义（有理数是其分子、分母均为自然数且分母不为零的分数）。 解： ADT Complex{ 数据对象：D={r,i|r,i 为实数} 数据关系：R={} 基本操作： InitComplex(&C,re,im) 操作结果：构造一个复数C ，其实部和虚部分别为re 和im DestroyCmoplex(&C) 操作结果：销毁复数C Get(C,k,&e) 操作结果：用e 返回复数C 的第k 元的值 Put(&C,k,e) 操作结果：改变复数C 的第k 元的值为e