201309学期算法与数据结构作业4

算法与数据结构试题与答案简介算法与数据结构是计算机科学中最重要的基础课程之一。

本文档将提供一系列常见的算法与数据结构试题，并附上答案进行解析。

这些试题适用于计算机科学、软件工程、数据科学等专业的学生，也适用于在求职面试中涉及到算法与数据结构的岗位。

算法1. 寻找最小值请编写一个函数，接收一个整数数组作为参数，返回数组中的最小值。

解答function findMin(arr) {let min = arr[0];for (let i = 1; i < arr.length; i++) {if (arr[i] < min) {min = arr[i];}}return min;}// 测试样例let arr = [8, 6, 7, 5, 3, 0, 9];console.log(findMin(arr)); // 02. 冒泡排序请编写一个函数，接收一个整数数组作为参数，实现冒泡排序算法，并返回排序后的数组。

冒泡排序的基本思想是从头到尾比较相邻两个元素的大小，并交换它们的位置，直到整个数组有序为止。

解答function bubbleSort(arr) {for (let i = 0; i < arr.length - 1; i++) {for (let j = 0; j < arr.length - i - 1; j++) {if (arr[j] > arr[j + 1]) {let temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}return arr;}// 测试样例let arr = [8, 6, 7, 5, 3, 0, 9];console.log(bubbleSort(arr)); // [0, 3, 5, 6, 7, 8, 9]3. 快速排序请编写一个函数，接收一个整数数组作为参数，实现快速排序算法，并返回排序后的数组。

习题答案1.填空题（1）非线性、一对多（2）前驱（3）叶结点（叶子结点）（4）度数（5）两（6）满二叉（7）从根结点到该结点之间的路径长度与该结点的权值的乘积（8）树中所有叶结点的带权路径长度之和（9）递增（10）平衡因子（11）B树的阶2.选择题（1）B （2）D （3）A （4）C （5）B （6）A （7）D （8）D3.思考题（1）如果i=1，则结点i无双亲，为根结点。

如果i>1，则结点i的双亲结点是结点i/2。

如果2i≤n，则结点i的左孩子是结点2i，否则结点i为叶结点。

如果2i+1≤n，则结点i的右孩子是结点2i+1，否则结点i无右孩子。

（2）非叶结点最多只有M个孩子，且M>2。

除根结点以外的非叶结点都有k个孩子和k-1个数据元素，k值满足[M/2]≤k≤M。

每一个叶结点都有k-1个数据元素，k值满足[M/2]≤k≤M。

所有叶结点都在同一层次。

所有分支结点的信息数据一致（n,A0,K1,A1,K2,A2……K n,A n），其中：K i（i=1,2……n）为关键字，且K i<K i+1（i=1,2……n-1）；A i为指向孩子结点的指针，且指针A i−1指向子树中的所有结点均小于K i，A n所指子树中的所有结点的关键字均大于K n；n为关键字的个数（[M/2]-1≤n≤M-1）。

（3）B+树是B树的升级版，区别在于叶结点在B+树的最底层（所有叶结点都在同一层），叶结点中存放索引值、指向记录的指针、指向下一个叶结点的指针。

叶结点按照关键字的大小，从小到大顺序链接。

分支结点不保存数据，只用来作索引，所有数据都保存在叶结点。

B*树是B+树的变体，B*树不同于B+树的是：其非根和非叶子结点上增加了指向兄弟结点的指针。

4.编程题（1）1//参数1为树的结点个数，参数2起始结点编号2btree_t *btree_create(int n, int i){3 btree_t *t;4 //使用malloc函数为结点申请内存空间5 t = (btree_t *)malloc(sizeof(btree_t));6 //将结点编号作为数据，保存至data中7 t->data = i;89 if(2 * i <= n){ //满足条件，说明结点有左孩子，编号为2i10 //递归调用，为左孩子的创建申请空间11 t->lchild = btree_create(n, 2 * i);12 }13 else{ //不满足条件，则没有左孩子14 t->lchild = NULL;15 }1617 if(2 * i + 1 <= n){ //满足条件，说明结点有右孩子，编号为2i+118 //递归调用，为右孩子的创建申请空间19 t->rchild = btree_create(n, 2 * i + 1);20 }21 else{ //不满足条件，则没有右孩子22 t->rchild = NULL;23 }2425 return t;26}。

一、填空题（每小题2分，共18分）1、数据的逻辑结构在计算机中的基本存储结构有和。

2、算法的时间复杂度取决于。

3、队列是的线性表，其操作数据的基本原则是。

4、设有一个二维数组A[0…9][0…9]，若每个元素占2个基本存储单元，A[0][0]的地址是200，若按列优先（以列为主）顺序存储，则A[6][6]的存储地址是。

5、在高度为h的二叉树的中只有度为0和度为2的结点，则该类二叉树中所包含的结点数至少为。

6、对于一个有n个顶点和e条弧的有向图，若采用正邻接链表存储，则表头向量的大小为，邻接表中的结点总数为。

7、若采用分块查找，要求线性表块内，块间。

8、对于文件，按其记录的类型可将文件分为文件、文件。

9、外部排序的最基本方法是，其主要时间花费在方面。

二、单项选择题（请将答案写在题目后的括号中。

每题2分，共18分）1、下面程序段的时间复杂度是（）。

for (i=1；i<=m；i++)for (j=1；j<=n；j++) A[i][j]=i+j;（A）O(m+n) （B）O(m) （C）O(n) （D）O(m*n)2、判断一个循环队列Q（最多元素个数为m）为满队列的条件是（）。

（A）Q.front==Q.rear ；（B）Q.front!=Q.rear ；（C）Q.front==(Q.rear+1)%m；（D）Q.front!=(Q.rear+1)%m；3、设有一个栈顶指针为top的顺序栈S，则将元素p压入栈S中的操作是（）。

（A）S[top++] =p；（B）S[++top] =p；（C）S[top--] =p；（D）S[--top] = p；4、广义表((a),((b),c),(((d))))的长度是，深度是。

（）（A）3, 4 （B）3, 3 （C）4, 3 （D）4, 45、在二叉树中，指针P所指的结点是叶子结点的条件是（）。

（A）P->Lchild !=NULL&& P->Rchild !=NULL ；（B）P->Lchild !=NULL&& P->Rchild ==NULL ；（C）P->Lchild ==NULL&& P->Rchild !=NULL ；（D）P->Lchild ==NULL&& P->Rchild ==NULL ；6、一棵二叉树，其先序遍历序列是abdghcefi，中序遍历序列是bgdhaecfi，则其后序遍历序列是( )。

作业4单项选择题第1题假设有对角矩阵a[n][n]，我们可以按行序为主将对角矩阵A的非零元素存入一个一维数组B[K]中。

给出二维数组的任一元素a[i][j]与一维数组B[K]对应的下标m的关系：（）。

A、k = 2*i + jB、k = 2 * j + iC、k = 3* (i + j )D、k = i + j答案：A第2题假设有对称矩阵a[n][n]，我们可以按行序为主将对称矩阵Ａ的下三角中的元素存入一个一维数组Ｂ［Ｋ］（Ｋ＝ｎ（ｎ＋１）／２）中。

给出二维数组的任一元素a[i][j]与一维数组B[K]对应的下标m的关系：（）。

A、(i-1)*(j+1)=kB、(i+1)*(j+1)=kC、(i-1)*j=kD、i*(j+1)=k答案：A第3题假定M行N列的数组a是行优先存贮的，L是元素a[0][0]的存贮地址，每个元素占K个存贮单元，元素a[I][j]的地址是：（）。

A、L + (I –1)* N * K +j*KB、L +( I * N +j)*KC、( I * N * K + (J –1) *KD、L +( I * M +j) * K答案：B第4题对给定的图，Prim方法与Kruskal方法都能给出最小代价生成树，针对最小代价生成树的算法，下面的说法哪一个是正确的：（）。

A、Prim方法与Kruskal方法均不需要进行圈的判断B、Prim方法与Kruskal方法都需要进行圈的判断C、Prim方法需要进行圈的判断，Kruskal方法不需要进行圈的判断D、Prim方法不需要进行圈的判断，Kruskal方法需要进行圈的判断答案：D多项选择题第5题假定以单向链表方式存贮堆栈，栈顶指针变量为p，表示栈空时，下面的说法哪一个是正确的():A、p==-1B、p==0C、p==NULLD、p != NULL答案：B|C第6题下述陈述中哪一项是正确的():A、文件中能唯一标识一个记录的数据项称之为主关键字B、文件中能唯一标识一个记录的数据项组合称之为主关键字C、文件中能标识一个记录的数据项称之为主关键字D、文件中能标识一个记录的数据项组合称之为主关键字答案：A|B第7题常用的线性表存贮结构有():A、顺序存贮结构B、链表存贮结构C、队列存贮结构D、堆栈存贮结构E、顺序存贮与链表存贮混合结构答案：A|B|E第8题常用的堆栈存贮结构有():A、顺序存贮结构B、链表存贮结构C、顺序存贮与链表存贮混合结构D、指针存贮结构答案：A|B判断题第9题空串是打印后不出现任何字符的字符器。

算法与数据结构习题及参考答案一、选择题1. 在算法分析中，时间复杂度表示的是：A. 算法执行的时间B. 算法的运行速度C. 算法执行所需的操作次数D. 算法的内存消耗答案：C2. 哪种数据结构可以在常数时间内完成插入和删除操作？A. 数组B. 栈C. 队列D. 链表答案：B3. 单链表的逆置可以使用哪种算法实现？A. 冒泡排序B. 归并排序C. 快速排序D. 双指针法答案：D4. 常用的查找算法中，哪种算法的时间复杂度始终为O(log n)？A. 顺序查找B. 二分查找C. 广度优先搜索D. 深度优先搜索答案：B5. 哪种排序算法的时间复杂度最坏情况下仍为O(n log n)？A. 冒泡排序B. 插入排序C. 快速排序D. 堆排序答案：C二、填空题1. 下面哪个数据结构先进先出？A. 栈B. 队列C. 堆D. 链表答案：B2. 在快速排序的基本步骤中，需要选取一个元素作为________。

答案：枢纽元素3. 广度优先搜索使用的数据结构是________。

答案：队列4. 二分查找是基于_________的。

答案：有序数组5. 哈希表的查找时间复杂度为_________。

答案：O(1)三、解答题1. 请简要说明冒泡排序算法的原理及时间复杂度。

答：冒泡排序是一种简单直观的排序算法。

它的基本思想是通过相邻元素之间的比较和交换来将最大（或最小）的元素逐渐“冒泡”到数列的一端。

冒泡排序的过程如下：1）比较相邻的元素，如果前面的元素大于后面的元素，则交换它们的位置；2）对每一对相邻元素重复进行比较和交换，直到最后一对元素；3）针对剩下的元素重复上述步骤，直到整个数列有序。

冒泡排序的时间复杂度为O(n^2)，其中n为待排序数列的长度。

在最坏情况下，冒泡排序需要进行n-1次比较和交换操作，因此时间复杂度为O(n^2)。

在最好情况下，如果待排序数列已经有序，冒泡排序只需进行n-1次比较，没有交换操作，时间复杂度为O(n)。

5.9 已知A为稀疏矩阵，试从空间和时间角度比较采用两种不同的存
储结构（二维数组和三元组表）完成求∑
=
n
i
ii
a
1运算的优缺点。

5.21 假设稀疏矩阵A和B均已三元数组顺序表作为存储结构。

试写出矩阵相加的算法，另设三元组表C存放结果矩阵。

5.30 试按表头，表尾的分析方法重写求广义表的深度的递归算法。

6.1 已知一棵树边集合为{ <I,M>, <I,N>, <E,I>, <B,E>, <B,D>, <A,B>, <G,J>, <G,K>, <C,G>, <C,F>, <H,L>, <C,H>, <A,C> },请画出这棵树，并回答下列问题：
（1)那个是根结点？
（2)那些是叶子结点？
（3)那些是结点G的双亲？
（4)那些是结点G的祖先？
（5)那些是结点G的孩子？
（6)那些是结点E的子孙？
（7)那些是结点E的兄弟？那些是结点F的兄弟？
（8)结点H和N的层次分别是什么？
（9)树的深度是多少？
（10)以结点C为根的子树的深度是多少？。

数据结构与算法第4次_答案1.树最适合用来表示_____A 有序数据元素B 无序数据元素C 元素之间具有分支层次关系的数据D 元素之间无联系的数据正确答案:C2.除根结点外，树上每个结点____A 可有任意多个孩子、任意多个双亲B 可有任意多个孩子、一个双亲C 可有一个孩子、任意多个双亲D 只有一个孩子、一个双亲正确答案:B3.在一棵二叉树中，第5层上的结点数最多有____A 10B 15C 16D 32正确答案:C4.设深度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至多为_____(注意h是指数)A 2h-1B 2(h-1)C 2*h-1D 2*h正确答案:A5.在有n个结点的二叉链表中，值为空的链指针共有_____A n+1B n-1C nD 2n正确答案:A6.具有100个结点的二叉树中，若用二叉链表存储，其指针域部分用来指向结点的左、右孩子，其余____个指针域为空A 50B 99C 100D 101正确答案:D7.设二叉树根结点的层次为1，所有含有15个结点的二叉树中，最小高度是_____A 6B 5C 4D 3正确答案:C8.如果某二叉树的先序遍历序列是abdcef，中序遍历序列是dbaefc，则其后序遍历序列是____A dbafecB fecdbaC efcdbaD dbfeca正确答案:D9.设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是____A a是b祖先B a是b子孙C a在b左方D a在b右方正确答案:C10.已知某二叉树的后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是____A acbedB decabC deabcD cedba正确答案:D11.在n个结点的二叉链表中，值为非空的指针域的个数是______A 2nB 2n+1C 2(n-1)D n-1正确答案:D12.树的基本遍历策略可分为先根遍历和后根遍历；二叉树的基本遍历策略可分为先序遍历、中序遍历和后序遍历。

第四次作业一、选择题1、具有n(n>1)个结点的完全二叉树中，结点i(2i>n)的左孩子结点是 D 。

A. 2iB. 2i+1C. 2i-1D. 不存在2、将一颗有100个结点的完全二叉树从上到下、从左到右一次对结点进行编号，根结点的编号为1，则编号为45的结点的右孩子的编号为 D 。

A. 46B. 47C. 90D. 913、在结点数为n的堆中插入一个结点时，复杂度为C。

A. O(n)B. O(n2)C. O(log2n)D. O(log n2)4、两个二叉树是等价的，则它们满足 D 。

A. 它们都为空B. 它们的左右子树都具有相同的结构C. 它们对应的结点包含相同的信息D. A、B和C5、包含n个元素的堆的高度为C。

（符号「a表示取不小a最小整数）A. nB. 「log2nC. 「log2(n+1)D. n+16、以下说法错误的是 BA. 存在这样的二叉树，对其采用任何次序的遍历其结点访问序列均相同B. 二叉树是树的特殊情形C. 由树转换成二叉树，其根结点的右子树总是空的D. 在二叉树中只有一棵子树的情形下，也要指出是左子树还是右子树7、设F是一个森林，B是由F变换得到的二叉树。

若F中有n个非终端结点，则B中没有右孩子的结点有 C 个。

A. n-1B. nC. n+1D. n+28、将一棵树T转换为二叉树B，则T的后根序列是B的 B 。

A. 先根序列B. 中根序列C. 后根序列D. 层次序列9、设树T的度为4，其中度为1, 2, 3, 4的结点个数分别为4, 2, 1, 1，则T中的叶结点的个数为 D 。

A. 5B. 6C. 7D. 810、设森林F中有三棵树，第一、第二、第三棵树的结点个数分别为M1, M2, M3。

与森林F对应的二叉树根结点的右子树上的结点个数为D。

A. M1-1B. M1+M2C. M2D. M2+M311、若以二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是 C 。

算法与数据结构试题及答案一、算法试题1. 请解释什么是算法？算法是一系列确定的步骤，用于解决问题或执行特定任务的方法。

2. 请列举几种常见的算法分类。

- 搜索算法：如二分搜索、广度优先搜索、深度优先搜索。

- 排序算法：如冒泡排序、插入排序、快速排序。

- 图算法：如最短路径算法、最小生成树算法。

- 字符串匹配算法：如KMP算法、Boyer-Moore算法。

3. 请描述递归算法的特点及适用场景。

递归算法是指在解决问题时，将大问题划分成一个或多个与原问题类似但规模减小的子问题，并通过递归调用这些子问题来解决原问题。

递归算法的特点包括简洁，易于理解和实现，但可能存在性能上的问题。

适用场景包括树结构的问题、分治算法等。

4. 请解释时间复杂度和空间复杂度的概念。

- 时间复杂度是指算法执行所需要的时间，通常用大O符号表示。

表示算法运行时间与问题规模的增长率之间的关系。

- 空间复杂度是指算法在执行过程中所需的额外空间，通常也用大O符号表示。

表示算法所需的空间与问题规模的增长率之间的关系。

二、数据结构试题1. 请解释什么是数据结构？数据结构是指为组织和存储数据而设计的一种特定方式。

它定义了数据的逻辑关系和操作方法。

2. 请列举几种常见的数据结构。

- 数组：一种连续存储数据的线性数据结构。

- 栈：一种具有后进先出（LIFO）特性的线性数据结构。

- 队列：一种具有先进先出（FIFO）特性的线性数据结构。

- 链表：一种通过指针连接各个节点的数据结构。

- 树：一种由节点和边组成的非线性数据结构。

3. 请解释树的常见术语：节点、根节点、叶子节点、父节点、子节点、深度、高度。

- 节点：树中的基本元素，包含数据和指向其他节点的指针。

- 根节点：树的顶部节点，没有父节点。

- 叶子节点：没有子节点的节点。

- 父节点：有子节点的节点。

- 子节点：一个节点的直接后继节点。

- 深度：从根节点到当前节点所经过的边的数量。

- 高度：树中任意节点最大深度的值。

1、算法的时间复杂度是指（）。

A.算法执行过程中所需要的基本运算次数B.执行算法程序所需要的时间C.算法程序的长度D.算法程序中的指令条数正确答案：A2、算法的空间复杂度是指（）。

）A.算法程序的长度B.算法程序所占的存储空间C.算法执行过程中所需要的存储空间D.算法程序中的指令条数正确答案：C3、线性表采用链式存储的优点是（）。

A.花费的存储空间较顺序储存少B.数据元素的物理顺序与逻辑顺序相同~C.便于随机存取D.便于插入和删除操作正确答案：D4、下列叙述中正确的是（）。

A.二叉树是线性结构B.线性链表是非线性结构C.线性表是线性结构D.栈与队列是非线性结构$正确答案：C5、数据结构中，与所使用的计算机无关的是数据的（）。

B.物理结构C.物理和存储结构D.存储结构正确答案：A6、存储结构是指（）。

,A.逻辑结构在计算机中的表示B.数据所占的存储空间量C.存储在外存中的数据D.数据在计算机中的顺序存储方式正确答案：A7、下列关于队列的叙述中，正确的是（）。

A.队列是先进后出B.队列是先进先出;C.在队列中只能插入数据D.在队列中只能删除数据正确答案：B8、下列关于栈的叙述中，正确的是（）。

A.栈只能采用顺序存储B.栈可以采用链式存储，采用链式存储时不会产生栈溢出现象。

C.在栈中只能删除数据D.在栈中只能插入数据；正确答案：B9、对长度为n的线性表进行顺序查找，查找成功时，最坏情况下所需要的比较次数为（）。

2+l正确答案：D10、下列叙述中，正确的是（）。

^A.以上三种说法都不对B.算法就是程序C.设计算法时只需要考虑结果的可靠性D.设计算法时只需要考虑数据结构的设计正确答案：A二、多选题1、如果进栈的顺序为e1,e2,e3,e4，则可能的出栈序列是（）。

,e1,e4,e2）,e3,e2,e1,e2,e3,e4,e4,e3,e1正确答案：B、C、D2、已知二叉树后序编历序列是dabec，中续遍历序列是debac，不是其前序编历序列是（）。

《算法与数据结构》模拟试题4(参考答案)一、填空题（每小题2分，共18分）1、线性结构树形结构图（或网）状结构2、表的一端表的另一端3、数据元素是一个字符4、 2005、2h-16、 n 2e7、以顺序方式存储结点按关键字有序8、索引散列9、归并内、外存之间的数据交换二、单项选择题（请将答案写在题目后的括号中。

每题2分，共18分）三、分析题（每题6分，共30分）1、解：依题意对应的Huffman树如下图所示。

WPL=(2+3)×4+(4+6+7)×3+(8+9)×2=1052、 解：该网的邻接链表如下图所示： 从顶点V 3出发的深度优先搜索的顶点序列是3→2→1→4，相应的生成树如下：3、 解：将关键字序列（14，19，16，7，4，13，25，9，18，12）依此插入到初态为空的二叉排序树中所得到的二叉排序树T 如图(a)所示；删除13之后的二叉排序树T1如图(b)所示；最后再插入13之后的二叉排序树T2。

从顶点V 3出发深度优先搜索生成树图(b) 删除13的二叉排序树图(c) 插入13的二叉排序树4、解：根据所给定的散列函数和处理冲突方法，其地址计算过程如下：H(31)=31 MOD 11=9 H(25)=25 MOD 11=3 H(18)=18 MOD 11=7H(19)=19 MOD 11=8 H(42)=42 MOD 11=9 冲突H(42)=(9+1) MOD 11=10 H(67)=67 MOD 11=1 H(15)=15 MOD 11=4 H(33)=33 MOD 11=0H(17)=17 MOD 11=6H(36)=36 MOD 11=3 冲突H(36)=(3+1) MOD 11=4 冲突H(36)=(4+1) MOD 11=5H(46)=46 MOD 11=2得到的散列表结构如下：5、解：做非递减排序时的每一趟结果如下：初始关键字：35，29，22，16，17，9，38，27，13，45第一趟：9，29，22，13，17，35，38，27，16，45第二趟：9，17，16，13，27，22，38，29，35，45第三趟：9，13，16，17，22，27，29，35，38，45第三趟归并完毕，排序结束。

数据结构与算法练习试卷4(题后含答案及解析) 全部题型 2. 填空题填空题（每空2分，共40分）请将每一个空的正确答案写在答题卡上。

1．设只包含根节点的二叉树的高度为0，则高度为k的二叉树的最小节点数为_____。

正确答案：k+1 涉及知识点：数据结构与算法2．在完全二叉树的顺序存储中，若节点i有左子女，则其左子女是节点_____。

正确答案：2i 涉及知识点：数据结构与算法3．二叉树是节点的有限集合，这个有限集合或者为_____，或者由一个根节点及两棵不相交的，分别称作为根的左子树和右子树的二叉树组成。

正确答案：空集涉及知识点：数据结构与算法4．m阶B树的根节点若不是叶节点，那么它至多有m棵子树，至少有_____棵子树。

正确答案：2 涉及知识点：数据结构与算法5．对于关键码序列18，30，35，10，46，38，5，40进行堆排序(假定堆的根节点为最小关键码)，在初始建堆过程中需进行的关键码交换次数为_____。

正确答案：3 涉及知识点：数据结构与算法6．在有n个节点的二叉树的llink-rlink法存储表示中，n个节点所含有的2n个指针中，必有_____个为空指针。

正确答案：n+1 涉及知识点：数据结构与算法7．对于给出的一组权w={5，6，8，12}，通过霍夫曼算法求出的扩充二叉树的带权外部路径长度为_____。

正确答案：61 涉及知识点：数据结构与算法8．对n个记录的文件进行快速排序，最坏情况下的执行时间为_____。

正确答案：O(n2) 涉及知识点：数据结构与算法9．散列法存储中处理碰撞的方法主要有两类：拉链法和_____。

正确答案：开放定址法涉及知识点：数据结构与算法10．某二叉树节点的对称序序列为A、B、C、D、E、F、G，后序序列为B、D、C、A、F、G、E。

则该二叉树对应的树林包括_____棵树。

正确答案：2 涉及知识点：数据结构与算法11．对线性表进行二分法检索，其前提条件是：线性表以_____方式存储，并且按关键码值排好序。

一、单项选择题（每小题2分，共42分）题目1对线性表进行二分查找时，要求线性表必须（）。

选择一项：A. 以链接存储方式，且数据元素有序B. 以顺序存储方式，且数据元素有序C. 以链接存储方式D. 以顺序存储方式题目2采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为（）。

选择一项：A. (n-1)/2B. nC. (n+1)/2D. n/2题目3有一个长度为10的有序表，按折半查找对该表进行查找，在等概率情况下查找成功的平均比较次数为（）。

选择一项：A. 29/9B. 26/10C. 31/10D. 29/10题目4已知一个有序表为{11,22,33,44,55,66,77,88,99}，则顺序查找元素55需要比较（）次。

选择一项：A. 5B. 4C. 3D. 6题目5有数据{53,30,37,12,45,24,96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，应该选择的序列是（）。

选择一项：A. 12,24,30,37,45,53,96B. 37,24,12,30,53,45,96C. 30,24,12,37,45,96,53D. 45,24,53,12,37,96,30题目6对于顺序存储的有序表{5,12,20,26,37,42,46,50,64}，若采用折半查找，则查找元素26的比较次数是（）。

选择一项：A. 4B. 5C. 6D. 3题目7在所有的排序方法中，关键字比较的次数与记录初始排列秩序无关的是（）。

选择一项：A. 希尔排序B. 直接选择排序C. 直接插入排序D. 冒泡排序题目8从未排序序列中依次取出元素与已经排好序的序列中的元素作比较。

将其放入已排序序列的正确的位置上，此方法称为（）。

选择一项：A. 交换排序B. 归并排序C. 插入排序D. 选择排序题目9依次将每两个相邻的有序表合并成一个有序表的排序方法称为（）。

选择一项：A. 归并排序B. 选择排序C. 交换排序D. 插入排序题目10当两个元素出现逆序的时候就交换位置，这种排序方法称为（）。

第 4 章 树结构1.选择题（1）C （2）C （3）B （4）B （5）B （6）C （7）C （8）D （9）A （10）D （11）D （12）B （13）B （14）D （15）B2.判断题（1）√（2）√ （3）Ⅹ （4）Ⅹ（5）√ （6）Ⅹ（7）√ （8）√（9）√（10）Ⅹ （11）Ⅹ（12）Ⅹ（13）√（14）Ⅹ（15）Ⅹ（16）Ⅹ（17）√（18）Ⅹ（19）Ⅹ（20）√3.简答题（1）一棵度为 2 的树与一棵二叉树有何区别？树与二叉树之间有何区别？【解答】①二叉树是有序树，度为 2 的树是无序树，二叉树的度不一定是 2。

②二叉树是有序树，每个结点最多有两棵子树，树是无序树，且每个结点可以有多棵子树。

A（2）对于图 4-37 所示二叉树，试给出： 1）它的顺序存储结构示意图；BC2）它的二叉链表存储结构示意图； 3）它的三叉链表存储结构示意图。

DEF【解答】 1）顺序存储结构示意图：AB CDEF ^ ^ ^ G^ ^ HGH(图 4-37)2）二叉链表存储结构示意图：3）三叉链表存储结构示意图：ABC^^D^E^ ^ F^G^^H^A^BC^^ D^E^^F^ G^^ H^（3）对于图 4-38 所示的树，试给出： 1）双亲数组表示法示意图； 2）孩子链表表示法示意图； 3）孩子兄弟链表表示法示意图。

ABCGFEDIHJKMN(图 4-38)【解答】 1）双亲数组表示法示意图：2）孩子链表表示法示意图：0 A -1 1 B0 2 C0 3 D2 4 E2 5F1 6 G1 7 H5 8I 2 9J 4 10 K 4 11 M 3 12 N 83）孩子兄弟链表表示法示意图：0A 1B 2C 3D 4E 5F 6G 7H 8I 9J 10 K 11 M 12 N12^56^348^11 ^ 910 ^7^12 ^ABC^^GFEDI^^ H^^J^ K^ ^ M^ ^ N^（4）画出图 4-39 所示的森林经转换后所对应的二叉树，并指出森林中满足什么条件的 结点在二叉树中是叶子。