第一章 数据结构概论 1.1 判断下列叙述的对错。如果正确，在题前打“(”，否则打“(”。 (1) 数据元素是数据的最小单位。 (2) 数据结构是数据对象与对象中数据元素之间关系的集合。 (3) 数据结构是具有结构的数据对象。 (4) 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。 (5) 算法和程序原则上没有区别，在讨论数据结构时二者是通用的。 1.2 判断下列叙述的对错。如果正确，在题前打“(”，否则打“(”。 (1) 所谓数据的逻辑结构是指数据元素之间的逻辑关系。 (2) 同一数据逻辑结构中的所有数据元素都具有相同的特性是指数据元素所包含的数据项的个数都相等。 (3) 数据的逻辑结构与数据元素本身的内容和形式无关。 (4) 数据结构是指相互之间存在一种或多种关系的数据元素的全体。 (5) 从逻辑关系上讲，数据结构主要分为两大类：线性结构和非线性结构。 1.3 填空题 算法是一个有穷的指令集，它为解决某一特定任务规定了一个运算序列。它应当具有输入、输出、( ① )、有穷性和可执行性等特性。 算法效率的度量分为( ② )和( ③ )。( ② )主要通过在算法的某些部位插装时间函数来测定算法完成某一规定功能所需的时间。而( ③ )不实际运行算法，它是分析算法中语句的执行次数来度量算法的时间复杂性。 程序所需的存储空间包含两个部分( ④ )和( ⑤ )。( ④ )空间的大小与输入输出数据的个数多少，数值大小无关；( ⑤ )空间主要包括其大小与问题规模有关的成分变量所占空间，引用变量所占空间，以及递归栈所用的空间，还有在算法运行过程中动态分配和回收的空间。 1.4 设n为正整数, 分析下列各程序段中加下划线的语句的执行次数。 (1) for ( int i = 1; i <= n; i++ ) for ( int j = 1; j <= n; j++ ) { c[i][j]=0.0; for ( int k = 1; k <= n; k++ ) c[i][j] = c[i][j] + a[i][k] * b[k][j]; } (2) x = 0; y = 0; for ( int i = 1; i <= n; i++ ) for ( int j = 1; j <= i; j++ ) for ( int k = 1; k <= j; k++ ) x = x + y; 1.5 试计算以下求和程序中所有语句的总执行次数。 float sum( float a[ ], int n ) { float s = 0.0; for ( int i = 0; i < n; i++ ) s += a[i]; return s; } 1.6 试用大O表示法给出下面程序的时间复杂性。 void out ( float x[ ][ ], int m, int n ) { float sum[ ]; for ( int i = 0; i < m; i++ ) { sum[i] = 0.0; for ( int j = 0; j < n; j++ ) sum[i] = x[i][j]; } for ( int i = 0; i < m; i++ ) cout << "Line: " << i << ":" << sum[i] << endl; } 第二章 数组 2.1 判断下列叙述的对错。如果正确，在题前打“(”，否则打“(”。 (1) 线性表的逻辑顺序与物理顺序总是一致的。 (2) 线性表的顺序存储表示优于链式存储表示。 (3) 线性表若采用链式存储表示时所有存储单元的地址可连续可不连续。 (4) 二维数组是其数组元素为线性表的线性表。 (5) 每种数据结构都应具备三种基本运算：插入、删除和搜索。 2.2 线性结构可用顺序表或链表存储。试问： (1) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？ (2) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？ 2.3 已知整数数组A[ ]中有n个元素，试设计一个算法，求数组中所有元素值的和。 2.4 已知整数数组A[ ]中有n个元素，试设计一个算法，求数组中所有元素值的平均值。 2.5 设有一个线性表 (e0, e1, …, en-2, en-1) 存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个地址的内容置换为 (en-1, en-2, …, e1, e0)。 2.6 假定数组A[arraySize]中有多个零元素, 试写出一个函数, 将A 中所有的非零元素依次移到数组A的前端A[i] (0 ( i < arraySize)。 2.7 已知A[n]为整数数组，试写出实现下列运算的递归算法： (1) 求数组A中的最大整数。 (2) 求n个整数的和。 2.8 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[4][4]在什么位置，下标(10)表示用10进数表示。 2.9 设有上三角矩阵A[n][n]，将其上三角元素逐行存储到一维数组B[m]中，使得B[k] = A[i][j]，且k = f1 (i) + f2 (j) + C。试推导出函数f1 (i)、f2 (j)和常数C，要求f1 (i)和f2 (j)中不包含常数项。 2.10 设A和B均为下三角矩阵，每一个都有n行。因此在下三角区域中各有n(n+1)/2个元素。另设有一个二维数组C，它有n行n+1列。试设计一个方案，将两个矩阵A和B中的下三角区域元素存放于同一个C中。要求将A的下三角区域中的元素存放于C的下三角区域中，B的下三角区域中的元素转置后存放于C的上三角区域中。并给出计算A的矩阵元素aij和B的矩阵元素bij在C中的存放位置下标的公式。 2.11 设有三对角矩阵A[n][n]，将其三条对角线中的元素逐行存储到一维数组B[3n-2 ]中，使得B[k] = A[i][j]。试求： (1) 用i, j表示k的地址转换公式； (2) 用k表示i, j的地址转换公式； 2.12 顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有127个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多少个元素? 2.13 已知一个顺序表中的元素按元素值非递减有序排列，试定义顺序表的存储表示，并编写一个函数，删除表中值相同的多余元素。 2.14 设有两个整数类型的顺序表A（有 m个元素）和B（有n个元素），其元素均以从小到大的升序排列。试编写一个函数，将这两个顺序表合并成一个顺序表C，要求C的元素也以从小到大的升序排列。 第三章 链表 3.1 设单链表中结点的结构为（data, link）。已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作？ (1) s->link = p->link; p->link = s; (2) q->link = s; s->link = p; (3) p->link = s->link; s->link = p; (4) p->link = s; s->link = q; 3.2 设单链表中结点的结构为（data, link）。已知指针p所指结点不是尾结点，若在*p之后插入结点*s，则应执行下列哪一个操作？ (1) s->link = p; p->link = s; (2) s->link = p->link; p->link = s; (3) s->link = p->link; p = s; (4) p->link = s; s->link = p; 3.3 设单链表中结点的结构为（data, link）。若想摘除结点*p的直接后继，则应执行下列哪一个操作？ (1) p->link = p->link->link; (2) p = p->link; p->link = p->link->link; (3) p->link = p->link; (4) p = p->link->link; 3.4 已知head为单链表的表头指针, 链表中存储的都是整型数据，试写出实现下列运算的递归算法： (1) 求链表中的最大整数。 (2) 求链表的结点个数。 3.5 设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。 3.6 设A和B是两个单链表，表中的元素均按结点的值（整数）升序排列。试编写一个函数，将A和B归并成一个按结点的值降序排列的单链表C。要求辅助存储空间为O(1)。 3.7 设单循环链表中结点的结构为（data, link），且rear是指向非空的带表头结点的单循环链表的尾结点的指针。若想删除链表第一个结点，则应执行下列哪一个操作？ s = rear; rear = rear->link; free(s); rear = rear->link; free(rear); rear = rear->link->link; free(rear); (4) s = rear->link->link; rear->link->link = s->link; free(s); 3.8 有一个循环链表，它既没有头指针又没有头结点。只有一个指针p指向表中的某一结点。试编写一个函数，删除指针p所指结点的直接前驱结点。 3.9 判断一个带表头结点的双向循环链表L是否对称相等的算法如下所示，请在算法中的 处填入正确的语句。 int symmetry ( DlinkList L ) { int sym = 1; DlistNode * p = L->next, q = L->prior; while ( ( p != q || p->prior == q ) && ① ) if ( p->data == q->data ) { ② ; ③ ; } else sym = 0; return sym; } 3.10 设双向循环链表中结点的结构为（data, prior, next），且不带表头结点。若想在指针p所指结点之后插入指针s所指结点，则应执行下列哪一个操作？ p->next = s; s->prior = p; p->next->prior = s; s->next = p->next; p->next = s; p->next->prior = s; s->prior = p; s->next = p->next; s->prior = p; s->next = p->next; p->next = s; p->next->prior = s; s->prior = p; s->next = p->next; p->next->prior = s; p->next = s; 3.11 试设计一个实现下述要求的查找运算函数Locate(L, x)。设有一个带表头结点的双向链表L，每个结点有4个数据成员：指向前驱结点的指针prior、指向后继结点的指针next、存放数据的成员data和访问频度freq。所有结点的freq初始时都为0。每当在链表上进行一次Locate (L, x)操作时，令元素值为x的结点的访问频度freq加1，并将该结点前移，链接到与它的访问频度相等的结点后面，使得链表中所有结点保持按访问频度递减的顺序排列，以使频繁访问的结点总是靠近表头。 栈和队列 4.1 试回答下列问题： (1) 设整数1, 2, 3, 4, 5, 6依次进栈，则可能的出栈序列有多少种? (2) 若整数1, 2, 3, 4, 5, 6依次进栈，那么是否能够得到435612, 325641, 154623和135426的出栈序列。 设有一个顺序栈S，元素s1, s2, s3, s4, s5, s6依次进栈，如果6个元素的出栈顺序为s2, s3, s4, s6, s5, s1，则顺序栈的容量至少应为多少？ 4.3 设顺序栈S的元素个数最大为MaxSize。试改写顺序栈的进栈函数Push (S, x)，要求当栈满时执行一个stackFull(S) 操作进行栈满处理。其功能是：动态创建一个比原来的栈元素存放数组大二倍的新数组，代替原来的栈元素存放数组，原来栈元素存放数组中的元素占据新数组的前MaxSize位置。 4.4 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想在链式栈的栈顶插入一个由指针s所指的结点，则应执行下列哪一个操作？ (1) top->link = s; (2) s->link = top->link; top->link = s; (3) s->link = top; top = s; (4) s->link = top; top = top->link; 4.5 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行下列哪一个操作？ x = top->data; top = top->link; (2) top = top->link; x = top->data; (3) x = top; top = top->link; (4) x = top->data; 4.6 假设以数组Q[m]存放循环队列中的元素, 同时以rear和length分别指示循环队列中的队尾位置和队列中所含元素的个数。试给出该循环队列的队空条件和队满条件, 并写出相应的插入(EnQueue)和删除(DlQueue)元素的操作。 4.7 假设以数组Q[m]存放循环队列中的元素, 同时设置一个标志tag，以tag = 0和tag = 1来区别在队头指针(front)和队尾指针(rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插入(EnQueue)和删除(DlQueue)的函数。 4.8 若使用循环链表来表示队列，p是链表中的一个指针(视为队尾指针)。试基于此结构给出队列的插入(EnQueue)和删除(DlQueue)的函数，并给出p为何值时队列空。 第六章 树与森林 6.1 一棵具有n个结点的理想平衡二叉树（即除离根最远的最底层外其他各层都是满的，最底层有若干结点）有多少层？若设根结点在第0层，则树的高度如何用n来表示（注意n可能为0）？ 6.2 n个结点可构造出多少种不同形态的二叉树? 若有3个数据1, 2, 3，输入它们构造出来的中序遍历结果都为1, 2, 3的不同二叉树有哪些? 6.3 假定在一棵二叉树中，度为2 的结点有15个，度为1的结点有20个，试问度为0的结点有多少个？ 6.4 判断下列叙述的对错。如果正确，在题前打“(”，否则打“(”。 (1) 二叉树是树的特殊情形。 (2) 若有一个结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。 (3) 若有一个结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。 (4) 若有一个叶子结点是二叉树中某个子树的中序遍历结果序列的最后一个结点，则它一定是该子树的前序遍历结果序列的最后一个结点。 (5) 若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。 6.5 试分别画出满足以下条件的所有二叉树： (1) 二叉树的前序序列与中序序列相同； (2) 二叉树的中序序列与后序序列相同； (3) 二叉树的前序序列与后序序列相同。 6.6 已知一棵二叉树的前序遍历结果是ABECDFGHIJ, 中序遍历结果是EBCDAFHIGJ, 试画出这棵二叉树。 6.7 若用二叉链表作为二叉树的存储表示，试编写一个递归算法求二叉树中指定结点所在层次。(设二叉树的高度为h，空树时h = -1，只有一个结点的二叉树的高度为h = 0) 6.8 已知一棵完全二叉树存放于一个一维数组T[n]中，T[n]中存放的是各结点的值。试设计一个算法，从T[0]开始顺序读出各结点的值，建立该二叉树的二叉链表表示。 6.9 下面是一个二叉树的前序遍历的递归算法。 void PreOrder ( BinTreeNode *t ) { if ( t != NULL ) { //递归结束条件 cout << t->data; //访问(输出)根结点 PreOrder ( t->leftChild ); //前序遍历左子树 PreOrder ( t->rightChild ); //前序遍历右子树 } } (1) 改写PreOrder算法，消去第二个递归调用PreOrder (t->rightChild ); (3) 利用栈改写PreOrder算法，消去两个递归调用。 6.10 设二叉树采用二叉链表表示，指针root指向根结点，指针p指向二叉树中某一指定结点。试编写一个算法，找出从根结点到结点*p之间的路径。 6.11 从供选择的答案中选择与下面有关二叉树和森林的叙述中各括号相匹配的词句，将其编号填入相应的括号内。 (1) 设二叉树有n个结点且根结点处于第0层，则其高度为（ A ）。 (2) 设高度为h（空二叉树的高度为-1，只有一个结点的二叉树的高度为0）的二叉树只有度为2和度为0的结点，则该二叉树中所含结点至少有（ B ）个。 (3) 设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为n1、n2、n3、n4，当把森林F转换成一棵二叉树后，其根结点的右子树中有（ C ）个结点。 (4) 设森林F中有4棵树，第1、2、3、4棵树的结点个数分别为n1、n2、n3、n4，当把森林F转换成一棵二叉树后，其根结点的左子树中有（ D ）个结点。 (5) 将含有82个结点的完全二叉树从根结点开始顺序编号，根结点为第0号，其他结点自上向下，同一层自左向右连续编号。则第40号结点的双亲结点的编号为（ E ）。 【供选择的答案】 A：① n-1 ② (log2(n+1)( -1 ③ (log2n( +1 ④ 不确定 B：① 2h ② 2h -1 ③ 2h +1 ④ h +1 C~D：① n1-1 ② n1+n2+n3 ③ n2+n3+n4 ④ n1 E：① 20 ② 19 ③ 81 ④ 80 6.12 一棵高度为h的满k叉树有如下性质: 第h层上的结点都是叶结点, 其余各层上每个结点都有k棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问: (1) 各层的结点个数是多少? (2) 编号为i的结点的父结点(若存在)的编号是多少? (3) 编号为i的结点的第m个孩子结点(若存在)的编号是多少? (4) 编号为i的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少? (5) 若结点个数为 n, 则高度h是n 的什么函数关系? 6.13 判断以下序列是否是最小堆? 如果不是, 将它调整为最小堆。 (1) { 100, 86, 48, 73, 35, 39, 42, 57, 66, 21 } (2) { 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } 6.14 给定权值集合{ 15, 03, 14, 02, 06, 09, 16, 17 }, 构造相应的Huffman树, 并计算它的带权外部路径长度。 6.15 假定用于通信的电文仅由8个字母c1, c2, c3, c4, c5, c6, c7, c8组成, 各字母在电文中出现的频率分别为5, 25, 3, 6, 10, 11, 36, 4。试为这8个字母设计不等长Huffman编码, 并给出该电文的总码数。 集合与搜索 7.1 供选择的答案中选择与下面有关搜索算法的叙述中各括号相匹配的词句，将其编号填入相应的括号内。 (1) 对线性表进行折半搜索时，要求线性表必须（ A ）。 (2) 采用顺序搜索算法查找长度为n的线性表时，元素的平均搜索长度为（ B ）。 (3) 采用折半搜索算法查找长度为n的线性表时，元素的平均搜索长度为（ C ）。 (4) 折半搜索与二叉搜索树（即二叉排序树）的时间性能（ D ）。 (5) 顺序搜索算法适合于存储结构为（ E ）的线性表。 【供选择的答案】 A：① 以数组方式存储 ② 以数组方式存储且结点按关键码有序排列 ③ 以链接方式存储 ④ 以链接方式存储且结点按关键码有序排列 B：① n/2 ② n ③ (n+1)/2 ④ (n-1)/2 C：① O(n2) ② O(nlog2n) ③ O(log2n) ④ O(n) D：① 相同 ② 不相同 E：① 散列存储 ② 顺序存储或链接存储 ③ 压缩存储 ④ 索引存储 7.2 设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行顺序搜索时的判定树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 7.3 设有序顺序表中的元素依次为017, 094, 154, 170, 275,503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半搜索时的判定树, 并计算搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 7.4 设有一个关键码序列 {DEC, FEB, NOV, OCT, JUL, SEP, AUG, APR, MAR, MAY, JUN, JAN} (1) 按字母顺序依次插入到一棵初始为空的AVL树中，画出每插入一个关键码后的AVL树，并标明平衡旋转的类型。 (2) 从所建立的AVL树中删除关键码MAY，为保持AVL树的特性，应如何进行删除和调整? 若接着删除关键码FEB，又应如何删除与调整? 7.5 设有一个关键码的输入序列 { 55, 31, 11, 37, 46, 73, 63, 02, 07 }, (1) 从空树开始构造平衡二叉搜索树, 画出每加入一个新结点时二叉树的形态。若发生不平衡, 指明需做的平衡旋转的类型及平衡旋转的结果。 (2) 计算该平衡二叉搜索树在等概率下的查找成功的平均查找长度和查找不成功的平均查找长度。 7.6 对于一个高度为h的AVL树，其最少结点数是多少？反之，对于一个有n个结点的AVL树, 其最大高度是多少? 最小高度是多少? 第八章 图 8.1 判断下列叙述的对错。如果正确，在题前打“(”，否则打“(”。 (1) 用邻接矩阵存储一个图时，在不考虑压缩存储的情况下，所占用的存储空间大小只与图中的顶点个数有关，而与图的边数无关。 (2) 对任何用顶点表示活动的网络(AOV网)进行拓扑排序的结果都是唯一的。 (3) 有回路的有向图不能完成拓扑排序。 (4) 有n (n≥1) 个顶点的无向连通图最少有n-1条边。 (5) 有n (n≥1) 个顶点的有向强连通图最少有n条边。 8.2 从供选择的答案中选择与下面有关图的叙述中各括号相匹配的词句，将其编号填入相应的括号内。 (1) 对于一个具有n个结点和e条边的无向图，若采用邻接表表示，则顶点表的大小为（ A ），所有边链表中边结点的总数为（ B ）。 (2) 采用邻接表存储的图的深度优先遍历算法类似于二叉树的（ C ）。 (3) 采用邻接表存储的图的广度优先遍历算法类似于二叉树的（ D ）。 (4) 判断有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（ E ）。 【供选择的答案】 A：① n ② n+1 ③ n-1 ④ n+e B：① e/2 ② e ③ 2e ④ n+e C~D：① 中序遍历 ② 前序遍历 ③ 后序遍历 ④ 按层次遍历 E：① 求关键路径的方法 ② 求最短路径的Dijkstra方法 ③ 深度优先遍历算法 ④ 广度优先遍历算法 8.3 试利用Dijkstra逐步求解的算法，计算下面带权有向图中从顶点A到其他各顶点的最短路径。 8.4 是否可将表示AOV网的邻接矩阵中所有的非零元素全部集中到矩阵的上三角部分（即矩阵的对角线以上的部分），试举例说明。 8.5 画出下图所示的AOV网的所有拓扑有序序列。 8.6 若用一个连通图来表示一个通信网络, 如图所示。  其中, 顶点表示网络中的通信站点, 边表示网络中的通信线路, 则 (1) 画出从顶点①出发的深度优先生成树; (2) 在原来的图中补充几条边, 使其中某一站点失效时整个通信网络仍然保持畅通。 (3) 指出图中哪几个顶点是关节点(即万一它失效则通信网络将发生故障)。 第九章 排序 9.1 如果只想在一个有n个元素的任意序列中得到其中最小的第k (k远小于n) 个元素之前的部分排序序列, 那么最好采用什么排序方法? 为什么? 例如有这样一个序列: { 503, 017, 512, 908, 170, 897, 275, 653, 612, 154, 509, 612*, 677, 765, 094 }, 要得到其第4个元素之前的部分有序序列: { 017, 094, 154, 170 }, 用所选择的算法实现时, 要执行多少次比较? 9.2 直接选择排序、快速排序和堆排序是不稳定的排序方法, 试举例说明。 9.3 利用插入排序的思想，将一个结点数据类型为int的无序的单链表改造为按结点数据值降序排列的单链表。要求利用原来的结点空间并禁止在结点间传送数据。 9.4 请编写一个算法，在基于单链表表示的待排序排序码序列上进行直接选择排序。 9.5 在已排好序的序列中，一个对象所处的位置取决于具有更小排序码的对象的个数。基于这个思想，可得计数排序方法。该方法在声明对象时为每个对象增加一个计数域count，用于存放在已排好序的序列中该对象前面的对象数目，最后依count域的值，将序列重新排列，就可完成排序。试编写一个算法，实现计数排序。并说明对于一个有n个对象的序列，为确定所有对象的count值，最多需要做n(n-1)/2次排序码比较。 9.6 设有n个待排序元素存放在一个不带表头结点的单链表中, 每个链表结点只存放一个元素, 头指针为first。试设计一个算法, 对其进行二路归并排序, 要求不移动结点中的元素, 只改各链结点中的指针, 排序后first仍指示结果链表的第一个结点。 （提示：先对待排序的单链表进行一次扫描, 将它划分为若干有序的子链表, 其表头指针存放在一个指针队列中。当队列不空时重复执行, 从队列中退出两个有序子链表, 对它们进行二路归并, 结果链表的表头指针存放到队列中。如果队列中退出一个有序子链表后变成空队列, 则算法结束。这个有序子链表即为所求。) 9.7 下列程序是一个两路归并算法merge，只需一个附加存储。设算法中参加归并的两个归并段是A[0] ( A[n-1] 和B[0] ( B[m-1]，归并后结果归并段放在原地。数据结构定义为： typedef float datatype; 算法描述如下： void merge ( datatype& A[ ], datatype& B[ ], int n, int m ) { int i, j; datatype temp; for ( i = 0; i < n; i++ ) { if ( A[i] > B[0] ) { temp = A[n-1]; for ( j = n-2; j >= i; j-- ) A[j+1] = A[j]; A[i] = B[0]; if ( temp <= B[1] ) B[0] = temp; else { for ( j = 1; j < m; j++ ) if ( temp > B[j] ) B[j-1] = B[j]; else { B[j-1] = temp; break; } } } } } (1) 若 A = { 12, 28, 35, 42, 67 }, B = { 9, 31, 70 }。写出每次执行算法最外层循环后各数组的变化。 试就一般情况A[n], B[m]，分析此算法的性能： ① 数据比较次数最少是多少？最多是多少？平均比较次数是多少？ ② 数据移动次数最少是多少？最多是多少？ 第十章 索引与散列 10.1 下图是一个3阶B树。试分别画出在插入65、15、40、30之后B树的变化。  10.2 下图是一个3阶B树。试分别画出在删除50、40之后B树的变化。  10.3 设散列表为HT[13], 待插入的关键码序列为 {12, 23, 45, 57, 20, 03, 78, 31, 15, 36}，散列函数为 H (key) = key %13。现采用线性探查法解决冲突，试画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度和搜索不成功的平均搜索长度。 10.4 设散列表为HT[13], 散列函数为 H (key) = key mod 13。采用双散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。 若设再散列函数为 RH (key) = (7*key) % 10 + 1, 寻找下一个空位的公式为 Hi = (Hi-1 + RH (key)) % 13, H1 = H (key)。画出相应的散列表, 并计算等概率下搜索成功的平均搜索长度。 10.6 判断下列叙述的对错。如果正确，在题前打“(”，否则打“(”。 (1) 在向二叉搜索树（即二叉排序树）中插入新结点时, 新结点必须作为叶结点插入。 (2) 若将一批杂乱无章的数据按堆结构组织起来, 则堆中各数据必然按自小到大的顺序排列起来。 (3) 在散列法中采取开散列（即链地址）法解决冲突时，其装载因子的取值一定在（0, 1）之间。 (4) 在散列法中采取闭散列（即开地址）法解决冲突时，一般不要立刻做物理删除，否则在搜索时会发生错误。 (5) 对于一棵有1999999个关键码的199阶B树，其最大层数为4。 10.7 判断下列叙述的对错。如果正确，在题前打“(”，否则打“(”。 (1) 二叉搜索树的搜索性能与折半搜索的搜索性能相同。 (2) 散列表的搜索效率主要取决于散列表造表时选取的散列函数和处理冲突的方法。 (3) 任何一个二叉搜索树的平均搜索时间都小于把同样的一批数据元素组织成线性表时采用顺序搜索法搜索的平均搜索时间。 (4) 虽然数据元素输入的次序不同，但生成的二叉搜索树都一样。 (5) 采用索引顺序搜索，既能实现线性表所希望的较快的搜索速度，又能适应动态变化的需要。