计算机软件基础习题及答案

更新时间：2023-10-23 08:52:01 阅读量：综合文库文档下载

说明：文章内容仅供预览，部分内容可能不全。下载后的文档，内容与下面显示的完全一致。下载之前请确认下面内容是否您想要的，是否完整无缺。

习题一

1.什么是数据结构，数据的逻辑结构，数据的存储结构？数据结构对算法有什么影响？请举例说明。

2.数据结构的存储方式主要有哪两种？它们之间的本质区别是什么？

3.设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; (3) int i = 1, j = 1; while (i<=n && j<=n) {

i = i + 1; j = j + i; } *(4) int i =1; do{

for (int j = 1; j <= n; j++) i = i + j; }while(i<100 + n);

4.试编写一个函数计算n!*2的值，结果存放于数组A[arraySize]的第n个数组元素中，0 ? n ? arraySize。若设计算机中允许的整数的最大值为maxInt，则当n>arraySize或者对于

某一个k (0 ? k ? n)，使得k!*2 > maxInt时，应按出错处理。可有如下三种不同的出错处理方式：

(1) 用printf显示错误信息及exit(1)语句来终止执行并报告错误；

(2) 用返回整数函数值0, 1来实现算法，以区别是正常返回还是错误返回；

(3) 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。

5.设有一个线性表 (a0, a1, …, an-2, an-1) 存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为 (an-1, an-2, …, a1, a0)。最后分析此算法的时间复杂度及空间复杂度。

6.顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有127个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多

少个元素?

7.利用顺序表的操作，实现以下的函数。并分析你所编制的函数的时间复杂度，并分析(2)与(3)的时间复杂度出现差异的原因。

(1) 从顺序表中删除具有给定值x的所有元素。

(2) 从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。 (3) 从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。 (4) 将两个有序顺序表la,lb合并成一个新的有序顺序表lc。

(5) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。

8.线性表可用顺序表或链表存储。试问： (1) 两种存储表示各有哪些主要优缺点? (2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用哪种存储表示？为什么？ (3) 若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时，应采用哪种存储表示？为什么？

9.试写出计算线性链表长度的算法。

10.设有一个表头指针为h的单链表。试设计一个算法，通过遍历一趟链表，将链表中所有结点的链接方向逆转，如下图所示。要求逆转结果链表的表头指针h指向原链表的最后一个结点。

11.设有一线性链表，其结点值均为整数。试将该线性链表分解为两个线性链表，其中一链表中的结点值均为负整数，而另一链表中结点的值均为正整数，并删除结点值为零的结点。

12．设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递减有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。

13．设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。

14.在一个循环链表中寻找值为x的结点，并将该结点移到第一个结点之前。

15.对于下面的每一步，画出栈元素和栈顶指针的示意图：（1）栈初始化；（2）元素x入栈；（3）元素y入栈；（4）出栈

（5）栈初始化（6）元素z入栈

16.铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问：

(1) 设有编号为1,2,3,4,5,6的六辆列车, 顺序开入栈式结构的站台, 则可能的出栈序列有多少种?

(2) 若进站的六辆列车顺序如上所述, 那么是否能够得到

435612, 325641, 154623和135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出\进栈\或\出栈\的序列)。

17.试证明：若借助栈可由输入序列1, 2, 3, …, n得到一个输出序列p1, p2, p3, …, pn (它是输入序列的某一种排列)，则在输出序列中不可能出现以下情况，即存在i < j < k，使得pj < pk < pi。(提示：用反证法)

18.将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时该栈为空，当第1号栈的栈顶指针top[1]等于m时该栈为空。两个栈均从两端向中间增长。当向第0号栈插入一个新元素时，使top[0]增1得到新的栈顶位置，当向第1号栈插入一个新元素时，使top[1]减1得到新的栈顶位置。当top[0]+1 == top[1]时或top[0] == top[1]-1时，栈空间满，此时不能再向任一栈加入新的元素。试定义这种双栈(Double Stack)结构的类定义，并实现判栈空、判栈满、插入、删除算法。

19.改写顺序栈的进栈成员函数Push(x)，要求当栈满时执行一个stackFull( )操作进行栈满处理。其功能是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前MaxSize位置。

20.根据教案中给出的优先级，回答以下问题： (1) 在表达式求值的过程中，如果表达式e含有n个运算符和分界符，问操作数栈(NS)中最多可存入多少个元素？

(2) 如果表达式e含有n个运算符，且括号嵌套的最大深度为6层，问栈中最多可存入多少个元素？

21.表达式的中缀表示为a * x - b / x^2，试利用栈将它改为后缀表示ax * bx2^/ -。写出转换过程中栈的变化。(^表示乘方运算)

22.设循环队列的容量为70（序号从1到70），经过一系列入队和退队运算后，有：（1）front=15，rear=46；（2）front=45，rear=10

问在上述两种情况下，循环队列中各有多少个元素？

23.设用链表表示一个双端队列，要求可在表的两端插入，但限制只能在表的一端删除。试编写基于此结构的队列的插入(enqueue)和删除(dequeue)算法，并给出队列空和队列满的条件。

习题2

1．列出右图所示二叉树的叶结点、分支结点和每个结点的层次。

2．使用 (1) 顺序表示和 (2) 二叉链表表示法，分别画出上图所示二叉树的存储表示。 3．在结点个数为n (n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？ 4．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。

5．如果一棵树有n1个度为1的结点, 有n2个度为2的结点, … , nm个度为m的结点, 试问有多少个度为0的结点? 试推导之。

6．若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法： (1) 统计二叉树中叶结点的个数。

(2) 以二叉树为参数，交换每个结点的左子女和右子女。 (3) 求二叉树的深度。

7．一棵高度为h的满k叉树有如下性质: 第h层上的结点都是叶结点, 其余各层上每个结点都有k棵非空子树, 如果按层次自顶向下, 同一层自左向右, 顺序从1开始对全部结点进行编号, 试问:

(1) 各层的结点个数是多少?

(2) 编号为i的结点的父结点(若存在)的编号是多少?

(3) 编号为i的结点的第m个孩子结点(若存在)的编号是多少?

(4) 编号为i的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少? (5) 若结点个数为 n, 则高度h是n 的什么函数关系? 8．请画出下图所示的树所对应的二叉树。

1 2 3 4 6 8 5 7 9．已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。

10．给定权值集合{15, 03, 14, 02, 06, 09, 16, 17}, 构造相应的霍夫曼树, 并计算它的带权路径长度。

习题三

1. 设有序顺序表中的元素依次为017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半查找时的二叉查找树, 并计算查找成功的平均查找长度和查找不成功的平均查找长度。

2. 若对有n个元素的有序顺序表和无序顺序表进行顺序查找, 试就下列三种情况分别讨论两者在等查找概率时的平均查找长度是否相同?

(1) 查找失败;

(2) 查找成功, 且表中只有一个关键码等于给定值k的对象;

(3) 查找成功, 且表中有若干个关键码等于给定值k的对象, 要求一次查找找出所有对象。

3. 设有10000个记录对象, 通过分块划分为若干子表并建立索引, 那么为了提高查找效率, 每一个子表的大小应设计为多大?

4. 设散列表为HT[13], 散列函数为 H (key) = key 。用闭散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。

(1) 采用线性探测法寻找下一个空位, 画出相应的散列表, 并计算等概率下查找成功的平均查找长度和查找不成功的平均查找长度。

(2) 采用随机探测法寻找下一个空位, 随机数序列为：5，4，2，7，3，6，…。画出相应的散列表, 并计算等概率下查找成功的平均查找长度。

5. 设有150个记录要存储到散列表中, 要求利用线性探查法解决冲突, 同时要求找到所需记录的平均比较次数不超过2次。试问散列表需要设计多大？设?是散列表的装载因子，则有

11 ASLsucc?(1?)

21??

6. 设有15000个记录需放在散列文件中，文件中每个桶内各页块采用链接方式连结，每个页块可存放30个记录。若采用按桶散列，且要求查找到一个已有记录的平均读盘时间不超过1.5次，则该文件应设置多少个桶？已知，链地址法的平均查找长度ASL=1+α/2

7. 设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。

(1) 直接插入排序 (2) 希尔排序(增量为5,2,1) (3) 冒泡排序 (4) 快速排序 (5) 直接选择排序 (6) 堆排序 (7) 二路归并排序

8. 在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在快速排序过程中有这种现象吗？

9. 试设计一个算法, 使得在O(n)的时间内重排数组, 将所有取负值的排序码排在所有取正值(非负值)的排序码之前。

提示：对比快速排序的第一趟排序，此处，以0为控制关键字。 10. 手工跟踪对以下各序列进行堆排序的过程。给出形成初始堆及每选出一个排序码后堆的变化。

(1) 按字母顺序排序：Tim, Dot, Eva, Rom, Kim, Guy, Ann, Jim, Kay, Ron, Jan (2) 按数值递增顺序排序：26, 33, 35, 29, 19, 12, 22

(3) 同样7个数字，换一个初始排列，再按数值的递增顺序排序：12, 19, 33, 26, 29, 35, 22

11. 希尔排序、简单选择排序、快速排序和堆排序是不稳定的排序方法, 试举例说明。

12. 在已排好序的序列中，一个对象所处的位置取决于具有更小排序码的对象的个数。基于这个思想，可得计数排序方法。该方法在声明对象时为每个对象增加一个计数域count，用于存放在已排好序的序列中该对象前面的对象数目，最后依count域的值，将序列重新排列，就可完成排序。试编写一个算法，实现计数排序。并说明对于一个有n个对象的序列，为确定所有对象的count值，最多需要做n(n-1)/2次排序码比较。

习题解答

3.设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; (3) int i = 1, j = 1; while (i<=n && j<=n) {

i = i + 1; j = j + i; } *(4) int i =1; do{

for (int j = 1; j <= n; j++) i = i + j; }while(i<100 + n); 【解答】

nnn (1) 1?n3 i?1j?1k?1nin (2) nij?i(i?1)?1n21n1?j??i?i??? 2?2i?12i?1i?1j?1k?1i?1j?1i?1?

1n(n?1)(2n?1)1n(n?1)n(n?1)(n?2) ???

26226

(3)i = 1时，i = 2，j = j + i = 1 + 2 = 2 + 1，

i = 2时，i = 3，j = j + i = ( 2 + 1 ) + 3 = 3 + 1 + 2，

i = 3时，i = 4，j = j + i = ( 3 + 1 + 2 ) + 4 = 4 + 1 + 2 + 3，

i = 4时，i = 5，j = j + i = ( 4 + 1 + 2 + 3 ) + 5 = 5 + 1 + 2 + 3 + 4， ……

i = k时，i = k + 1，j = j + i = ( k + 1 ) + ( 1 + 2 + 3 + 4 + … + k )，

????????????j??k?1???i?ni?1kk?k?1?k2?3k?3??k?1????n22解出满足上述不等式的k值，即为语句i = i + 1的程序步数。

(4) for语句每执行一次，语句i=i+j将执行n次，而i的值会增加因此，当for语句执行k次后，i的值将变为

n(n?1) 21?k故最终for语句的执行次数k为满足

n(n?1) 21?kn(n?1)?100?n 2的最小整数k，语句i = i + j的程序步数为n*k。

某一个k (0 ? k ? n)，使得k!*2 > maxInt时，应按出错处理。可有如下三种不同的出错处理方式：

(1) 用printf显示错误信息及exit(1)语句来终止执行并报告错误；

(2) 用返回整数函数值0, 1来实现算法，以区别是正常返回还是错误返回；

(3) 在函数的参数表设置一个引用型的整型变量来区别是正常返回还是某种错误返回。试讨论这三种方法各自的优缺点，并以你认为是最好的方式实现它。【解答】

#include

const int arraySize = 100; const int MaxInt = 0x7fffffff; int calc( int T[ ], int n ) { int i, value = 1; if ( n != 0 ) {

int edge = MaxInt / n / 2; for ( i = 1; i < n; i++ ) { value *= i*2;

if ( value > edge ) return 0; }

value *= n * 2; }

T[n] = value;

printf(\n”,n,T[n]); return 1; }

void main ( ) {

int A[arraySize]; int i;

for ( i = 0; i < arraySize; i++ ) if ( !calc ( A, i ) ) {

printf(\ break; }

}

/*---------顺序表结构的定义.为简化起见，表元素我们使用整型数据----------- -----------数据元素从data[0]处开始存储---------------------------------*/ typedef struct /*注意typedef的使用*/ {

int data[MAXSIZE]; /*数据域*/ int length; /*表长*/ }listtype;

5.设有一个线性表 (a0, a1, …, an-2, an-1) 存放在一个一维数组A[arraySize]中的前n个数组元素位置。请编写一个函数将这个线性表原地逆置，即将数组的前n个原址内容置换为 (an-1, an-2, …, a1, a0)。最后分析此算法的时间复杂度及空间复杂度。【解答】

void inverse (listtype * A) { int tmp;

int n= A->length;

for( int i = 0; i <= ( n-1 ) / 2; i++ ){ tmp = A->data[i]; A->data[i] = A->data[n-i-1]; A->data[n-i-1] = tmp; } }

时间复杂度：需进行n/2次循环，因此时间复杂度为O(n)；

空间复杂度：使用一个整形辅助存储单元tmp，因此空间复杂度为O(1)。

6.顺序表的插入和删除要求仍然保持各个元素原来的次序。设在等概率情形下, 对有127个元素的顺序表进行插入, 平均需要移动多少个元素? 删除一个元素, 又平均需要移动多少个元素?

【解答】

若设顺序表中已有n个元素。又设插入或删除表中各个元素的概率相等，则在插入时因有n+1个插入位置(可以在表中最后一个表项后面追加)，每个元素位置插入的概率为1/(n+1)，但在删除时只能在已有n个表项范围内删除，所以每个元素位置删除的概率为1/n。插入时平均移动元素个数AMN(Averagy Moving Number )为

n1?n?i??1(n?(n?1)???1?0)?1n(n?1)?n?63.5AMN??n?1i?0n?1n?122

删除时平均移动元素个数AMN为

1n?111(n?1)nn?1 AMN??(n?i?1)?((n?1)?(n?2)???1?0)???63

ni?0nn22

7.利用顺序表的操作，实现以下的函数。并分析你所编制的函数的时间复杂度，并分析(2)与(3)的时间复杂度出现差异的原因。

(1) 从顺序表中删除具有给定值x的所有元素。

(2) 从顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。 (3) 从有序顺序表中删除其值在给定值s与t之间（要求s小于t）的所有元素。

(4) 将两个有序顺序表la,lb合并成一个新的有序顺序表lc。

(5) 从顺序表中删除所有其值重复的元素，使表中所有元素的值均不相同。

【解答】

(1) 从顺序表中删除具有给定值x的所有元素。 void DelValue(listtype * L, int x ){

int i = 0, j;

while ( i < L->length ) /*循环, 寻找具有值x的元素并删除它*/ if (L->data[i] == x ) { /*删除具有值x的元素, 后续元素前移*/

for (j = i;j < L->length-1; j++ ) L->data[j] = L->data[j+1]; L-length--; /*表长减1*/ }

else i++; }

(2) 实现删除其值在给定值s与t之间（要求s小于t）的所有元素的函数如下： void DelValue_s_to_t (listtype *L,int s, int t){ int i,j;

if ( L->length == 0 || s >= t ) {

printf(“List is empty or parameters are illegal!\\n”); exit(1); } i = 0;

while ( i < L->length) /*循环, 寻找具有值x的元素并删除它*/

if (L->data[i]>=s &&L->data[i]<= t){

/*删除满足条件的元素, 后续元素前移*/

for ( j = i; j < L->length-1; j++ ) L->data[j] = L->data[j+1]; L->length--; /*表长减1*/

}

else i++; }

(3) 实现从有序顺序表中删除其值在给定值s与t之间的所有元素的函数如下： void DelValue_s_to_t_1 (listtype *L,int s int t){ int i,j,k;

if ( L->length == 0 || s >= t ){

printf(“List is empty or parameters are illegal!\\n”); exit(1); }

for (i = 0; i < L->length; i++ ) /*循环, 寻找值 ≥s 的第一个元素*/

if ( L->data[i] >= s ) break; /*退出循环时, i指向该元素*/ if ( i < L->length ) {

for (j = 1; i + j < L->length; j++ )/*循环, 寻找值 > t 的第一个元素*/ if (L->data[i+j] > t ) break; /*退出循环时, i+j指向该元素*/

for (k = i+j; k < L->length; k++ ) /*删除满足条件的元素, 后续元素前移*/

L->data[k-j] = L->data[k];

L->length-= j; /*表长减j*/

} }

(4) 实现将两个有序顺序表合并成一个新的有序顺序表的函数如下：

listtype * Merge(listtype *LA,listtype *LB ){

/*合并有序顺序表LA与LB成为一个新的有序顺序表并由函数返回 listtype *LC;

int value1,value2; int i,j,k;

initiatelist(LC);

if (LA->length + LB->length > MAXSIZE) {

printf(“表上溢/n”; exit(1); }

i = 0, j = 0, k = 0; value1 = LA->data[i]; value2 = LB->data[j];

while (i < LA->length && j < LB->length ) {

/*循环, 两两比较, 小者存入结果表*/ if (value1 <= value2){

LC->data[k] = value1; i++; value1=LA->data[i];} else {

LC->data[k] = value2; j++; value2=LB->data[j];} k++; }

while( i < LA->length){ /*当LA表未检测完, 继续向结果表传送*/

LC->data[k] = value1; i++; k++; value1 = LA->data[i]; }

while( j < LB->length){ /*当LB表未检测完, 继续向结果表传送*/

LC->data[k] = value2; j++; k++; value2 = LB->data[j]; }

LC->length = k;

return LC; }

(5) 实现从表中删除所有其值重复的元素的函数如下： void DelDouble(listtype *L){

int i,j,k; int tmp;

if(L->length == 0 ){

printf(“表空\\n”; exit(1); } i=0;

while ( i < L->length ) { /*循环检测*/

j = i + 1;

tmp = L->data[i];

while( j < L->length ) { /*对于每一个i, 重复检测一遍后续元素*/

if( tmp == L->data[j]) { /*如果相等,删除此结点，后续元素前移*/

for( k = j+1; k < L->length; k++ ) L->data[k-1] = L->data[k];

L->length--; /*表最后元素位置减1*/

}

else j++;

/*检测完L->data[i], 检测下一个*/

} }

(1) 顺序存储表示是将数据元素存放于一个连续的存储空间中，实现顺序存取或(按下标)直接存取。它的存储效率高，存取速度快。但它的空间大小一经定义，在程序整个运行期间不会发生改变，因此，不易扩充。同时，由于在插入或删除时，为保持原有次序，平均需要移动一半(或近一半)元素，修改效率不高。

链接存储表示的存储空间一般在程序的运行过程中动态分配和释放，且只要存储器中还有空间，就不会产生存储溢出的问题。同时在插入和删除时不需要保持数据元素原来的物理顺序，只需要保持原来的逻辑顺序，因此不必移动数据，只需修改它们的链接指针，修改效率较高。但存取表中的数据元素时，只能循链顺序访问，因此存取效率不高。 (2) 如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表的总数也可能自动改变、在此情况下，应选用链接存储表示。如果采用顺序存储表示，必须在一个连续的可用空间中为这n个表分配空间。初始时因不知道哪个表增长得快，必须平均分配空间。在程序运行过程中，有的表占用的空间增长得快，有的表占用的空间增长得慢；有的表很快就用完了分配给它的空间，有的表才用了少量的空间，在进行元素的插入时就必须成片地移动其他的表的空间，以空出位置进行插入；在元素删除时，为填补空白，也可能移动许多元素。这个处理过程极其繁琐和低效。

如果采用链接存储表示，一个表的存储空间可以连续，可以不连续。表的增长通过动态存储分配解决，只要存储器未满，就不会有表溢出的问题；表的收缩可以通过动态存储释放实现，释放的空间还可以在以后动态分配给其他的存储申请要求，非常灵活方便。对于n个表(包括表的总数可能变化)共存的情形，处理十分简便和快捷。所以选用链接存储表示较好。 (3) 应采用顺序存储表示。因为顺序存储表示的存取速度快，但修改效率低。若表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取表中的元素，这时采用顺序存储表示较好。

}

i++;

/*---------链表结构的定义.为简化起见，表元素我们使用整型数据----------- -----------此链表带头结点--------------------------------------------*/ typedef struct mynode{

int data; /*数据域：整型*/ struct mynode *next; /*指针域*/ } node, linklisttype;

9.试写出计算线性链表长度的算法。 int lengthsl(linklisttype *L){ linklisttype * p; int len;

if(L == NULL){return –1;}

p = L->next; /* p指向链表L的头结点*/ len = 0;

while(p != NULL){ len++;

p = p->next;

}

return len; }

【解答】

void LinkListInverse(linklisttype *L){ linklisttype *p, *pre, *next;

if(L == NULL || L->next == NULL ) return; /*表未初始化，或为空表*/ p = L->next;

pre = L;

while( p != NULL ) { /*循环修改链表中所有结点的后继指针的指向*/ next = p->next; /*取当前结点的后继指针*/

p->next = pre; /*当前结点的后继改为指向其原来的前驱*/ pre = p , p=next; /*指针后移*/

}

L->next->next = NULL; /*原第一个结点改为最后一个结点*/ L->next = pre; /*链表的头结点指向原最后一个结点*/ }

11.设有一线性链表，其结点值均为整数。试将该线性链表分解为两个线性链表，其中一链

表中的结点值均为负整数，而另一链表中结点的值均为正整数，并删除结点值为零的结点。【解答】

void LinkListDispose(linklisttype * L,linklisttype * LA,linklisttype * LB){ /*

将链表L分解为LA、LB两个链表，其中LA中结点值均为正，LB中结点值均为负，并删除结点值为零的结点,最后释放L的头结点。 */

linklisttype *p , *pt , *pa, * pb;

LA = initiatesl();

pa = LA; /*指向LA中的最后一个结点*/ LB = initiatesl();

pb = LB; /*指向LB中的最后一个结点*/

If(L == NULL || L->next == NUUL) return; /*L为空指针或L为空表*/

p = L->next; /*p指向链表L的第一个结点*/ while(p != NULL) /*遍历链表L*/

if(p->data > 0){ /*将p链入链表LA的pa后*/ pa->next = p; pa = p;

p = p->next;

}

elseif(p->data < 0){ /*将p链入链表LB的pb后*/

pb->next = p; pb = p;

p = p->next;

}

else{ /*删除值为0的结点*/

pt = p->next; /*记录当前结点的后继，以便删除当前结点*/ free(p); p = pt;

}

pa->next = NULL; pb->next = NULL; free(L); }

12．设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递减有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。【解答】

void linklistMerge(linklisttype *LA,linklisttype *LB ){ /*合并有序链表LA与LB,结果存入LA中，并释放LB的头结点 */ linklisttype *pa, *pb , *pre ,*pn;

if(LA == NULL || LB == NULL ||) return;

if(LA->next == NULL){ /*LA为空表，则直接将LB链入LA即可*/ LA->next = LB->next; free(LB); retrun; }

if(LB->next == NULL) return; /*LB为空表，则直接返回即可*/ pa = LA->next, pb = LB->next ,pre=LA;

while (pa != NULL && pb != NULL) /*循环, 两两比较, 小者存入结果表*/

if(pa->data > pb->next){ /*将pb链入LA，然后pb指针后移*/

pre->next = pb;

pn = pb->next; pb->next = pa; pb = pn;

pre = pre->next }

else{ /*pa指针后移*/ pa = pa->next; pre = pre->next; }

if(pb != NULL) /*将pb剩余结点链入LA*/ pre->next = pb; free(LB); }

13．设ha和hb分别是两个带表头结点的非递减有序单链表的表头指针, 试设计一个算法, 将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间, 不另外占用其它的存储空间。表中允许有重复的数据。【解答】

Linklisttype * linklistMerge_inverse(linklisttype *LA,linklisttype *LB ){ /*合并有序链表LA与LB,结果存入LC中，并释放LA、LB的头结点 ,函数返回LC*/ linklisttype *pa, *pb , *p;

if(LA == NULL || LB == NULL ||) return;

LC = initiatesl();

pa = LA->next, pb = LB->next;

while (pa != NULL && pb != NULL) /*循环, 两两比较, 大者存入LC*/

if(pa->data > pb->next){ /*将pa链为LC的第一个结点*/

p = pa->next;

pa->next = LC->next; LC->next = pa; pa = p; }

else{ /*将pa链为LC的第一个结点*/

p = pb->next;

pb->next = LC->next;

LC->next = pb; pb = p;

}

while(pa != NULL){

p = pa->next;

pa->next = LC->next; LC->next = pa; pa = p; }

while(pb != NULL){

p = pb->next;

pb->next = LC->next; LC->next = pb; pb = p; }

free(LA); free(LB);

/*将pa剩余结点链入LC*/

/*将pb剩余结点链入LC*/

}

14.在一个循环链表中寻找值为x的结点，并将该结点移到第一个结点之前。【解答】设此循环链表为单链表，则其类型定义与一般单链表相同 typedef struct mynode cyclelisttype;

void search_movefirst(cyclelisttype *CL, int x){ cyclelisttype * p , *pre; if(CL == NULL) return; p = CL->next; pre = CL;

while(p != CL)

/*查找x，注意与普通单链表在判断是否到表尾上的不同*/ if(p->data == x) break; else{

pre = p; p = p->next; }

if(p != CL){ /*查找成功*/

per->next = p->next; /*在原来位置删除p*/ p->next = CL->next; /*p插入到CL后*/ CL->next = p; }

16.铁路进行列车调度时, 常把站台设计成栈式结构的站台，如右图所示。试问：

(1) 设有编号为1,2,3,4,5,6的六辆列车, 顺序开入栈式

结构的站台, 则可能的出栈序列有多少种?

(2) 若进站的六辆列车顺序如上所述, 那么是否能够得到435612, 325641, 154623和135426的出站序列, 如果不能, 说明为什么不能; 如果能, 说明如何得到(即写出\进栈\或\出栈\的序列)。

【解答】

6 (1) 可能的不同出栈序列有 ?1/(6?1)??C12?132种。

(2) 不能得到435612和154623这样的出栈序列。因为若在4, 3, 5, 6之后再将1, 2出栈，则1, 2必须一直在栈中，此时1先进栈，2后进栈，2应压在1上面，不可能1先于2出栈。154623也是这种情况。出栈序列325641和135426可以得到。

3 2 1

5 4 1

6 4 1

2 1

4 1

1 1

3 32 32 325 325 3256 32564 325641

5 4 2

3 2

4 2

1 2 6

1 1 13 135 1354 13542 13542 135426

【解答】

因为借助栈由输入序列1, 2, 3, …, n，可得到输出序列p1, p2, p3, …, pn ，如果存在下标i, j, k，满足i < j < k，那么在输出序列中，可能出现如下5种情况：

① i进栈，i出栈，j进栈，j出栈，k进栈，k出栈。此时具有最小值的排在最前面pi位置，具有中间值的排在其后pj位置，具有最大值的排在pk位置，有pi < pj < pk, 不可能出现pj < pk < pi的情形；

② i进栈，i出栈，j进栈，k进栈，k出栈，j出栈。此时具有最小值的排在最前面pi位置，具有最大值的排在pj位置，具有中间值的排在最后pk位置，有pi < pk < pj , 不可能出现pj < pk < pi的情形；

③ i进栈，j进栈，j出栈，i出栈，k进栈，k出栈。此时具有中间值的排在最前面pi位置，具有最小值的排在其后pj位置，有pj < pi < pk, 不可能出现pj < pk < pi的情形；

④ i进栈，j进栈，j出栈，k进栈，k出栈，i出栈。此时具有中间值的排在最前面pi 位置，具有最大值的排在其后pj位置，具有最小值的排在pk位置，有pk < pi < pj, 也不可能出现pj < pk < pi的情形；

⑤ i进栈，j进栈，k进栈，k出栈，j出栈，i出栈。此时具有最大值的排在最前面pi 位置，具有中间值的排在其后pj位置，具有最小值的排在pk位置，有pk < pj < pi, 也不可能出现pj < pk < pi的情形；

【解答】

bot[0] top[0] top[1] bot[1]

双栈的类型定义如下： typedef struct{ int top0,top1;

elemtype data[MAXSIZE]; }DoubleStack;

判栈空

int DoubleStackEmpty(DoubleStack * DS,int StackNo){

/*DS：指向双栈的指针，StackNo:0或1，指定要判断的是第0栈，还是第一栈 if(StackNo==0)

return(DS->top0 < 0); else

retrun(DS->top1 >= MAXSIZE); }

判栈满

int DoubleStackFull(DoubleStack * DS){ return(DS->top1-DS->top0==1); } 入栈

int PopDoubleStack(DoubleStack * DS,int StackNo,elemtype x){ /*将数据元素x插入到栈StackNo中*/

if(DoubleStackFull(DS)) return(FALSE);/*栈满溢出*/ if(StackNo==0){/*对第0栈插入*/ DS->top0++;

DS->data[top0]=x; }

else{/*对第1栈插入*/ DS->top1--;

DS->data[top1]=x;

}

return(TRUE); }

删除算法

elemtype PushDoubleStack(DoubleStack * DS,int StackNo){ /*从StackNo栈中删除并返回一个元素，若栈空，则返回NULL*/ if(DoubleStackEmpty(DS,StackNo)) return(NULL); if(StackNo==0){/*对0号栈进行操作*/ DS->top0--;

return(DS->data[DS->top0+1]); } else{

DS->top1++;

return(DS->data[DS->top1-1]); } }

19.改写顺序栈的进栈成员函数Push(x)，要求当栈满时执行一个stackFull( )操作进行栈满处理。其功能是：动态创建一个比原来的栈数组大二倍的新数组，代替原来的栈数组，原来栈数组中的元素占据新数组的前MaxSize位置。【解答】

void push(stack * S,elemtype x) {

if(StackEmpty(S)) stackFull(S); //栈满，做溢出处理 S->top ++;

S->data[S->top] = x; //进栈 }

void stackFull(stack *S){

elemtype *temp;

temp=calloc(3*MAXSIZE,sizeof(elemtype)); //创建体积大二倍的数组 for ( int i = 0; i <= S->top; i++ ) //传送原数组的数据

temp[i] = S->data[i];

free(S->data); //删去原数组

MAXSIZE *= 3; //数组最大体积增长二倍 S->data = temp; //新数组成为栈的数组空间 }

(2) 如果表达式e含有n个运算符，且括号嵌套的最大深度为6层，问栈中最多可存入多少个元素？【解答】

(1) 如果表达式e含有n个运算符和分界符，则可能的运算对象有n+1个。因此在利用后缀表达式求值时所用到的运算对象栈中最多可存入n+1个元素。

(2) 同上。

21.表达式的中缀表示为a * x - b / x^2，试利用栈将它改为后缀表示ax * bx2^/ -。写出转换过程中栈的变化。(^表示乘方运算) 【解答】

若设当前扫描到的运算符ch的优先级为icp(ch)，该运算符进栈后的优先级为isp(ch)，则可规定各个算术运算符的优先级如下表所示。

运算符 ; ( ^ *,/, % isp icp 0 1 7 5 0 8 6 4 +, - 3 2 ) 8 1 isp也叫做栈内(in stack priority)优先数，icp也叫做栈外(in coming priority)优先数。当刚扫描到的运算符ch的icp(ch)大于isp(stack)时，则ch进栈；当刚扫描到的运算符ch的icp(ch)小于isp(stack)时，则位于栈顶的运算符退栈并输出。从表中可知，icp(“(”)最高，但当“(”进栈后，isp(“(”)变得极低。其它运算符进入栈中后优先数都升1，这样可体现在中缀表达式中相同优先级的运算符自左向右计算的要求。运算符优先数相等的情况只出现在括号配对“)”或栈底的“;”号与输入流最后的“;”号配对时。前者将连续退出位于栈顶的运算符，直到遇到“(”为止。然后将“(”退栈以对消括号，后者将结束算法。

步序 0 1 2 3 4 5 6 7 8 9 10

扫描项 a * x b / x ^ 2 ;

项类型

动作

栈的变化 ; ; ; * ; * ; ; - ; - ; -/ ; -/^ ; -/^ ; -/ ; - ;

输出

操作数操作符操作数操作数操作符操作数操作符操作数操作符

? ';' 进栈, 读下一符号 ? 直接输出, 读下一符号

? isp ( ' ; ' ) < icp ( ' * ' ), 进栈, 读下一符号 ? 直接输出, 读下一符号 ? isp ( ' * ' ) > icp ( ' - ' ), 退栈输出 ? isp ( ' ; ' ) < icp ( ' - ' ), 进栈, 读下一符号 ? 直接输出, 读下一符号 ? 直接输出, 读下一符号

? isp ( ' / ' ) < icp ( '^' ), 进栈, 读下一符号 ? 直接输出, 读下一符号 ? isp ( '↑' ) > icp ( ' ; ' ), 退栈输出 ? isp ( ' / ' ) > icp ( ' ; ' ), 退栈输出 ? isp ( ' - ' ) > icp ( ' ; ' ), 退栈输出 ? 结束

A A a x a x * a x * a x * b a x * b a x * b x a x * b x a x * b x 2 a x * b x 2^ a x * b x 2^/ a x * b x 2^/ -

- 操作符

? isp ( ' - ' ) < icp ( '/' ), 进栈, 读下一符号 ; -/

22.设循环队列的容量为70（序号从1到70），经过一系列入队和退队运算后，有：（1）front=15，rear=46；（2）front=45，rear=10

于存放在已排好序的序列中该对象前面的对象数目，最后依count域的值，将序列重新排列，就可完成排序。试编写一个算法，实现计数排序。并说明对于一个有n个对象的序列，为确定所有对象的count值，最多需要做n(n-1)/2次排序码比较。【解答】待排序的表 35 66 14 28

0 0 2

1 3 0 0 0 0 0 0 0 1 初始状态第1趟排序结果第2趟排序结果第3趟排序结果 14 28 35 66 存放结果的表

void count_sort (RECORDNODE a[],int n ) { int i, j;

RECORDNODE c[n]; // c是存放计数排序结果的临时表 for ( i = 0; i

for ( j = i+1; j < n; j++ )

if ( a[j].key < a[i].key ) a[i].count++;

else a[j].count++; //统计

for ( i = 0; i < n; i++ ) //在c [ ]中各就各位

c[a[i].count] = a[i];

for ( i = 0; i < n; i++ ) a[i] = c[i]; //结果复制回当前表对象中 delete c; }

问在上述两种情况下，循环队列中各有多少个元素？【解答】

(1) 队列中元素的个数为(MAXSIZE+rear-front) %MAXSIZE = (70+46-15)p=31 (2) 队列中元素的个数为(MAXSIZE+rear-front) %MAXSIZE = (70+10-45)p=35

23.设用链表表示一个双端队列，要求可在表的两端插入，但限制只能在表的一端删除。试编写基于此结构的队列的插入(enqueue)和删除(dequeue)算法，并给出队列空和队列满的条件。设此队列含头结点，队头指针front指向头结点，限定在表头端删除队列空：队尾指针指向头结点，即rear=front时，队空

队列满：因为是链表，所以，只有内存空间不足时才会有队满的问题。 void insertqueue(queuetype *Q,int location,elemtype x){

/*Q:指向队列的指针；location:插入位置，0表示队头，1表示队尾；x:数据元素*/ node *p;

p=(node *)malloc(sizeof(node)); p->data = x;

if(location==0){/*在队头处插入*/ p->next = Q->front->next; Q->front->next = p;

if(Q->rear==Q->front) Q->rear = p;/*对空表插入*/ }

else{/*在队尾处插入*/ p->next = NULL; Q->rear->next = p; Q->rear = p; } }

elemtype deletequeue(queuetype *Q){ elemtype x; node * p;

if(Q->rear == Q->front) return(NULL); /*空队列*/ p = Q->front->next; x = p->data;

Q->front->next = p->next;

if(Q->rear == p) Q->rear = Q->front /*对只有一个元素的队列进行删除*/ free(p); return(x); }

24.所谓回文，是指从前向后顺读和从后向前倒读都一样的不含空白字符的串。例如did，madamimadam，pop即是回文。试编写一个算法，以判断一个串是否是回文。【解答1】

将字符串中全部字符进栈，然后将栈中的字符逐个与原字符串中的字符进行比较。算法

如下：

int palindrome (string S) {

stacktype * st; int yes = 1, i = 0; while(S[i] != “\\0”){

push (st,S[i]); i++; /*扫描字符串，所有字符进栈*/ } i = 0;

while(S[i] != “\\0” ) /*比较字符串*/ if(S[i] == st.GetTop( )){pop(st); i++; } else {yes = 0; break; } return(yes); }

【解答2】

采用递归算法，判断从s到e中的字符串是否回文，通过函数返回是或不是。

int palindrome(char A[ ], int start, int end) { if (A[start] != A[end] ) return 0; else if ( s > e ) return 1;

else palindrome ( A, start+1, end-1 ); }

25.设A[n][n]为一个上三角矩阵，将A中所有非零元素按列序顺次存入一维数组B中，则A与B元素的对应关系是什么？【解答】上三角矩阵如下所示

?a11?0??0?????0a12a220?0a13a23a33?0?????a1n?a2n??a3n?

???ann??其数据元素满足Aij=0，对所有的i>j

上三角矩阵正好是一个下三角矩阵的转秩，我们知道，一个下三角矩阵按行压缩存储时，矩阵元素与一维数组的对应关系为

A[i][j]?B[i*(i+1)/2+j]，对所有的i>j；

因此，下三角矩阵按列序存储在一维数组中的元素对应关系为

A[i][j]?B[j*(j+1)/2+i]，对所有的i

26.编写串的替换函数Replace(str,str1,str2)，将主串str中所有子串str1替换为str2。【解答】见书p58

1．列出右图所示二叉树的叶结点、分支结点和每个结点的层次。

【解答】

二叉树的叶结点有⑥、⑧、⑨。分支结点有①、②、③、④、⑤、⑦。结点①的层次为0；结点②、③的层次为1；结点④、⑤、⑥的层次为2；结点⑦、⑧的层次为3；结点⑨的层次为4。

2．使用 (1) 顺序表示和 (2) 二叉链表表示法，分别画出上图所示二叉树的存储表示。【解答】

① 0 1 2 3 4 5 6 7 8 9

① ② ③ ④ ⑤ ⑥ ⑦ ② ∧ ③ 10 11 12 13 14 15 16 17 ∧ ④ ∧ ⑤ ∧ ⑥ ∧ 18 ⑧ ⑨

⑦ ∧ ∧ ⑧ ∧

顺序表示 ∧ ⑨ ∧ 二叉链表表示

3．在结点个数为n (n>1)的各棵树中，高度最小的树的高度是多少？它有多少个叶结点？多少个分支结点？高度最大的树的高度是多少？它有多少个叶结点？多少个分支结点？【解答】

结点个数为n时，高度最小的树的高度为1，有2层；它有n-1个叶结点，1个分支结点；高度最大的树的高度为n-1，有n层；它有1个叶结点，n-1个分支结点。

4．试分别画出具有3个结点的树和3个结点的二叉树的所有不同形态。【解答】

具有3个结点的树具有3个结点的二叉树

5．如果一棵树有n1个度为1的结点, 有n2个度为2的结点, … , nm个度为m的结点, 试问有多少个度为0的结点? 试推导之。【解答】

总结点数 n = n0 + n1 + n2 + … + nm

总分支数 e = n-1 = n0 + n1 + n2 + … + nm-1 = m*nm + (m-1)*nm-1 + … + 2*n2 + n1

m? 则有 n0????(i?1)ni??1

?i?2?6．若用二叉链表作为二叉树的存储表示，试针对以下问题编写递归算法：

(1) 统计二叉树中叶结点的个数。

(2) 以二叉树为参数，交换每个结点的左子女和右子女。 (3) 求二叉树的深度。【解答】

(1) 统计二叉树中叶结点个数 int leaf(BTNode * ptr){

if(ptr == NULL )return(0);

else if(ptr->lchild == NULL && ptr->rchild == NULL ) return 1; else return leaf(ptr->lchild ) + leaf(ptr->rchild ); }

(2) 交换每个结点的左子女和右子女 void exchange (BTNode * ptr ){ BTNode *temp;

if(ptr->lchild != NULL || ptr->rchild != NULL ) { temp = ptr->lchild;

ptr->lchild = ptr->rchild;

ptr->rchild = temp; exchange(ptr->lchild ); exchange(ptr->rchild ); } }

(3) 求二叉树的深度

void depth(BRNode *ptr){

if(ptr == NULL) return(0);

return(max(depth(ptr->lchild),depth(ptr->rchild))); }

(1) 各层的结点个数是多少?

(2) 编号为i的结点的父结点(若存在)的编号是多少?

(3) 编号为i的结点的第m个孩子结点(若存在)的编号是多少?

(4) 编号为i的结点有右兄弟的条件是什么? 其右兄弟结点的编号是多少? (5) 若结点个数为 n, 则高度h是n 的什么函数关系? 【解答】

(1) k ( i = 0, 1, ……, h )

i?k?2? (2) ?

??k??

(3) ( i-1)*k + m + 1

i?k?2?(4) ( i-1 ) % k ? 0 或 i?? 时有右兄弟，右兄弟为i + 1。

??*kk??(5) h = logk (n*(k-1)+1)-1 (n = 0时h = -1 ) 8．请画出下图所示的树所对应的二叉树。

【解答】 1 1 2 2 3 对应二叉树

4 3 4 5 5 6 7 6 8 7 8 9．已知一棵二叉树的前序遍历的结果是ABECDFGHIJ, 中序遍历的结果是EBCDAFHIGJ, 试画出这棵二叉树。【解答】

当前序序列为ABECDFGHIJ，中序序列为EBCDAFHIGJ时，逐步形成二叉树的过程如下图所示： A A A A B F B F B F FHIGJ EBCD E HIGJ E C G E C G CD

D HI J D H J

10．给定权值集合{15, 03, 14, 02, 06, 09, 16, 17}, 构造相应的霍夫曼树, 并计算它的带权路径长度。【解答】

F： 15 03 14 02 06 09 16 17 (Ⅰ) 15 14 06 09 16 17 05

02 03 (Ⅱ) 15 14 09 16 17 11 (Ⅲ) 15 14 16 17 20 05 06

09 11 02 03 05 06 (Ⅳ) 16 17 20 29 (Ⅴ) 20 29 33

02 03 09 11 14 15 09 11 14 15 16 17 05 06 05 06

02 03 02 03

82 (Ⅵ) 33 49 (Ⅶ) 33 49 16 17 20 29 16 17

20 29

09 11 14 15 09 11 14 15 05 06 05 06

02 03 02 03 此树的带权路径长度WPL = 229。

1. 设有序顺序表中的元素依次为017, 094, 154, 170, 275, 503, 509, 512, 553, 612, 677, 765, 897, 908。试画出对其进行折半查找时的二叉查找树, 并计算查找成功的平均查找长度和查找不成功的平均查找长度。【解答】

509

154 677

553 897 017 275

094 170 503 512 612 765 908

ASLsucc114145??Ci?(1?2*2?3*4?4*7)?14i?11414115'159?C?(3*1?4*14)??i1515i?015ASLunsucc

2. 若对有n个元素的有序顺序表和无序顺序表进行顺序查找, 试就下列三种情况分别讨论两者在等查找概率时的平均查找长度是否相同?

(1) 查找失败;

(2) 查找成功, 且表中只有一个关键码等于给定值k的对象;

(3) 查找成功, 且表中有若干个关键码等于给定值k的对象, 要求一次查找找出所有对象。【解答】

(1) 不同。因为有序顺序表查找到其关键码比要查找值大的对象时就停止查找，报告失败信息，不必查找到表尾；而无序顺序表必须查找到表尾才能断定查找失败。

(2) 相同。查找到表中对象的关键码等于给定值时就停止查找，报告成功信息。 (3) 不同。有序顺序表中关键码相等的对象相继排列在一起，只要查找到第一个就可以连续查找到其它关键码相同的对象。而无序顺序表必须查找全部表中对象才能确定相同关键码的对象都找了出来，所需时间就不相同了。

前两问可做定量分析。第三问推导出的公式比较复杂，不再进一步讨论。

3. 设有10000个记录对象, 通过分块划分为若干子表并建立索引, 那么为了提高查找效率, 每一个子表的大小应设计为多大? 【解答】

每个子表的大小 n?10000?100个记录对象。

4. 设散列表为HT[13], 散列函数为 H (key) = key 。用闭散列法解决冲突, 对下列关键码序列 12, 23, 45, 57, 20, 03, 78, 31, 15, 36 造表。

(1) 采用线性探测法寻找下一个空位, 画出相应的散列表, 并计算等概率下查找成功的平均查找长度和查找不成功的平均查找长度。

(2) 采用随机探测法寻找下一个空位, 随机数序列为：5，4，2，7，3，6，…。画出相应的散列表, 并计算等概率下查找成功的平均查找长度。

【解答】

使用散列函数 H(key) = key mod 13，有

H(12) = 12, H(23) = 10, H(45) = 6, H(20) = 7, H(03) = 3, H(78) = 0, H(15) = 2, H(36) = 10.

(1) 利用线性探测法造表：

0 1 2 3 4 5 6 7 8

15 03 (1) (1) (1) 查找成功的平均查找长度为

H(57) = 5, H(31) = 5,

9 10 11 12 23 36 12 (1) (2) (1)

57 45 20 31 (1) (1) (1) (4)

ASLsucc = 1(1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 2 + 1) = 14

1010ASLunsucc = 1(2 + 1 + 3 + 2 + 1 + 5 + 4 + 3 + 2 + 1 + 5 + 4 + 3) = 36 1313查找不成功的平均查找长度为

(2) 利用随机探测法造表：

Hi = (Hi-1 + R[i-1]) % 13, H1 = H (key) 0 1 2 3 4 5 6 7 78 31 15 03 (1) (3) (1) (1) 查找成功的平均查找长度为

8 9 10 11 12 23 (1)

12 (1)

57 45 20 36 (1) (1) (1) (4)

ASLsucc = 1(1 + 1 + 1 + 1 + 1 + 1 + 4 + 1 + 3 + 1) = 15

1010ASLunsucc = 1(3 + 6 + 3 + 6 + 1 + 7 + 2 + 9 + 3 + 1 + 7 + 1 + 2) = 51 1313查找不成功的平均查找长度为

11 ASLsucc?(1?)

21??【解答】

已知要存储的记录数为n = 150，查找成功的平均查找长度为ASLsucc ? 2，则有ASLsucc =1?1?? 2，解得 ? ?2。又有? = n150? 2，则 m ? 225。

??1??3mm32?1???

6. 设有15000个记录需放在散列文件中，文件中每个桶内各页块采用链接方式连结，每个页块可存放30个记录。若采用按桶散列，且要求查找到一个已有记录的平均读盘时间不超过1.5次，则该文件应设置多少个桶？已知，链地址法的平均查找长度ASL=1+α/2 【解答】

已知用链地址法（开散列）解决冲突，查找成功的平均查找长度为1+α/2≤1.5，解出α≤1，又α= n / m = 15000 / 30 / m = 500 / m ≤1，m≥500。由此可知，该文件至少应设置500个桶。

7. 设待排序的排序码序列为{12, 2, 16, 30, 28, 10, 16*, 20, 6, 18}, 试分别写出使用以下排序方法每趟排序后的结果。并说明做了多少次排序码比较。

(1) 直接插入排序 (2) 希尔排序(增量为5,2,1) (3) 冒泡排序 (4) 快速排序 (5) 直接选择排序 (6) 堆排序 (7) 二路归并排序【解答】

(1) 直接插入排序

初始排列 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8 i = 9

[ 12 ] [ 2 [ 2 [ 2 [ 2 [ 2 [ 2 [ 2 [ 2 [ 2

1 2 12 ] 12 12 12 10 10 10 6 6

2 16 16 16 ] 16 16 12 12 12 10 10

3 30 30 30 30 ] 28 16 16 16 12 12

4 28 28 28 28 30 ] 28 16* 16* 16 16

5 10 10 10 10 10 30 ] 28 20 16* 16*

6 16* 16* 16* 16* 16* 16* 30 ] 28 20 18

7 20 20 20 20 20 20 20 30 ] 28 20

8 6 6 6 6 6 6 6 6 30 ] 28 9 18 18 18 18 18 18 18 18 18 30 ] 排序码比较次数 1 1 1 2 5 3 3 3 8

(2) 希尔排序(增量为5,2,1)

初始排列 0 d = 5 d = 2 d = 1

12 10 10 2

1 2 2 2 6

2 16 16 16 10

3 30 6 6 12

4 28 18 16* 16

5 10 12 12 16*

6 16* 16* 18 18

7 20 20 20 20

8 6 30 30 28

9 18 28 28 30

排序码比较次数 1+1+1+1+1 = 5 (1+1+2+1) + (1+1 +1+1) = 9

1+1+3+1+3+1+1 +1+2 = 14

希尔(shell)本人采取的增量序列为 ?n/2?, ??n/2?/2?, ??n/2?/2?/2?, …,1。一般地，增量序列可采用?nα?, ??nα?α?, ??nα?α?α?, …, 1。大量实验表明，取α=0.45454的增量序列比取其他的增量序列的优越性更显著。计算 ?0.45454n? 的一个简单方法是用整数算术计算(5*n-1)/11。需要注意，当?< 1/2时，增量序列可能不以1结束，需要加以判断和调整。

(3) 冒泡排序

初始排列 0

排序码比较次数

i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6

[ 12 2 2 2 2 2 2 2

2 [ 12 6 6 6 6 6 6

16 6 [ 12 10 10 10 10 10

30 16 10 [ 12 12 12 12 12

28 30 16 16 [ 16 16 16 16

10 28 30 16* 16* [ 16* 16* 16*

16* 10 28 30 18 18 [ 18 18

20 16* 16* 28 30 20 20 20

6 20 18 18 28 30 28 28

18 ] 9

18 ] 8 20 ] 7 20 ] 6 20 ] 28 ] 30 ] 30

5 4 3

(4) 快速排序

Pivot Pvtpos 12 6 28 18 16*

0,1,2,3 0,1 4,5,6,7,8 4,5,6 4

0 [ 12 [ 6

1 2

2 16

3 30

4 28

5 10 16

6 16* 16*

7 20 20

8 6 30

9 18 ]

排序码比较次数 9

pos pos pos pos 2 10 ]

12 [ 28 12 12 12

18 ] 2

pos pos 2 2 2

[ 2 ] 6 [ 10 ] 12

6 10 6 10

[ 28 16 16* 20 30 18 ] 5

pos pos pos pos pos [ 18

16* 18 18

20 ]

[ 30 ] 30 30

3 1

pos pos pos

[ 1616 ] *

pos 16*

[ 16 ]

[ 20 ] 28 20

6 10

左子序列递归深度为1，右子序列递归深度为3。 (5) 直接选择排序

初始排列 0 1 i = 0 i = 1 i = 2 i = 3 i = 4 i = 5 i = 6 i = 7 i = 8

[ 12 2 2 2 2 2 2 2 2

2 [ 12 6 6 6 6

2 16 16 10 10 10 10

3 30 30 30 12 12 12 12

4 28 28 28 [ 28 16 16 16 16

5 10 10 10 16 16 [ 28 16* 16* 16*

6 16* 16* 16* 16* 16* 16* [ 28 18 16

7 20 20 20 20 20 20 20 [ 20 20

8 6 6 12 12 30 30 30 30 [ 30

9 18 ] 18 ] 18 ] 18 ] 18 ] 18 ] 18 ] 28 ] 28 ]

排序码比较次数 9 8 7 6 5 4 3 2 1

6 [ 16

6 10 [ 30 28 6 10 12

16*

[ 30 ]

12 30 12

2 16 28 16 28 16

30 28 10 16* 20 18 10 16* 20 18 10 16*

20 6 18 2 6 12 2 6 30

初始排列，不是最大堆形成初始最大堆交换0 与9对象 20 28 6 18 16 20 16 20 16 12 6 10 16* 12 18 10 16* 12 18 10 16* 2 28 30 2 6 30 2 28 30 从0# 到8# 重新形成堆交换0# 与8# 对象从0# 到 7# 重新形成堆

16* 18 2 12 16 18 16 12 16

2 6 10 18 12 6 10 16* 2 6 10 16* 20 28 30 20 28 30 20 28 30

交换0# 与7# 对象从0# 到6# 重新形成堆交换0# 与6# 对象

16* 10 16

12 16 12 16 12 10

2 6 2 6 16* 18 2 6 16* 18 10 18

20 28 30 20 28 30 20 28 30

从0# 到5# 重新形成堆交换0# 与5# 对象从0# 到4# 重新形成堆

2 6 12

6 10 12 10 6 10

12 16 16* 18 2 16 16* 18 2 16 16* 18

20 28 30 20 28 30 20 28 30 (6) 堆排序

第一步，形成初始的最大堆 (略)，第二步，做堆排序。

交换0# 与4# 对象从0# 到3# 重新形成堆交换0# 与3# 对象

2 6 10

6 10 2 10 6 2

12 16 12 16 12 16 16* 18 16* 18 16* 18

20 28 30 20 28 30 20 28 30

从0# 到2# 重新形成堆交换0# 与2# 对象从0# 到1# 重新形成堆

2 2

6 10 6 10 12 16 12 16 16* 18 16* 18

20 28 30 20 28 30 交换0# 与1# 对象从0# 到1# 重新形成堆，得到结果

(7) 二路归并排序

采用迭代的方法进行归并排序。设待排序的数据对象有n个。首先把每一个待排序的数据对象看作是长度为的初始归并项，然后进行两两归并，形成长度为2的归并项，再对它们两两归并，形成长度为4的归并项，如此一趟一趟做下去，最后得到长度为n的归并结果。

12 2 16 30 28 10 16* 20 6 18

排序码比较5次

2 12 16 30 10 28 6 18 16* 20 12 排序码比较6次

*2 12 16 30 10 16 20 28 6 18

排序码比较7次

* 2 10 12 16 16 20 28 30 6 18 排序码比较9次

*2 6 10 12 16 16 18 20 28 30

8. 在起泡排序过程中，什么情况下排序码会朝向与排序相反的方向移动，试举例说明。在快速排序过程中有这种现象吗？【解答】

如果在待排序序列的后面的若干排序码比前面的排序码小，则在起泡排序的过程中，排序码可能向与最终它应移向的位置相反的方向移动。例如，

57 40 38 11 13 34 48 75 6 19 9 7 如9向相反方向移动 6 57 40 38 11 13 34 48 75 7 19 9 如19向相反方向移动 6 7 57 40 38 11 13 34 48 75 9 19 如9向最终方向移动 6 7 9 57 40 38 11 13 34 48 75 19 如13向相反方向移动 6 7 9 11 57 40 38 13 19 34 48 75 如13向最终方向移动 6 7 9 11 13 57 40 38 19 34 48 75 如34向相反方向移动 6 7 9 11 13 19 57 40 38 34 48 75 6 7 9 11 13 19 34 57 40 38 48 75

9. 试设计一个算法, 使得在O(n)的时间内重排数组, 将所有取负值的排序码排在所有取正值(非负值)的排序码之前。【解答】

void reArrange( RECORDNODE a[],int n ) {

/*对数组a[0:n-1]执行此操作*/ int i = 0,j=n-1; while ( i != j ) {

while ( a[i].key < 0 ) i++; while ( a[j].key >= 0 ) j--; swap ( a[i], a[j] ); i++; j--; } }

10. 手工跟踪对以下各序列进行堆排序的过程。给出形成初始堆及每选出一个排序码后堆的变化。

(1) 按字母顺序排序：Tim, Dot, Eva, Rom, Kim, Guy, Ann, Jim, Kay, Ron, Jan (2) 按数值递增顺序排序：26, 33, 35, 29, 19, 12, 22

(3) 同样7个数字，换一个初始排列，再按数值的递增顺序排序：12, 19, 33, 26, 29, 35, 22

【解答】为节省篇幅，将用数组方式给出形成初始堆和进行堆排序的变化结果。阴影部分表示参与比较的排序码。请大家按照完全二叉树的顺序存储表示画出堆的树形表示。 (1) 按字母顺序排序形成初始堆（按最大堆）

i=4 i=3 i=2 i=1 i=0

0 Tim Tim Tim Tim Tim [ Tim

1 Dot Dot Dot Dot [ Ron Ron

2 Eva Eva Eva [ Guy Guy Guy

3 Rom Rom [ Rom Rom Rom Rom

4 Kim [ Ron Ron Ron Kim Kim

5 Guy Guy Guy Eva Eva Eva

6 Ann Ann Ann Ann Ann Ann

7 Jim Jim Jim Jim Jim Jim

8 Kay Kay Kay Kay Kay Kay

9 Ron Kim Kim Kim Dot Dot

10 Jan Jan ] Jan ] Jan ] Jan ] Jan ]

堆排序

j=10

0 [ Jan

1 Ron

2 Guy

3 Rom

4 Kim

5 Eva

6 Ann

7 Jim

8 Kay

9 Dot

Tim ] 交换

j=9 j=8 [ Ron [ Dot [ Rom [ Jan Rom Rom Kim Kim Guy Guy Guy Guy Kay Kay Kay Kay Kim Kim Dot Dot Eva Eva Eva Eva Ann Ann Ann Ann Jim Jim Jim Jim Jan Jan Jan ] Rom ] Dot ] Ron ] Ron Ron Tim Tim Tim Tim 调整交换调整交换 [ Kim Kay Guy Jim Dot Eva Ann Jan ] Rom j=7 [ Jan Kay Guy Jim Dot Eva Ann Kim ] Rom [ Kay Jim Guy Jan Dot Eva Ann ] Kim Rom j=6 [ Ann Jim Guy Jan Dot Eva Kay ] Kim Rom [ Jim Jan Guy Ann Dot Eva ] Kay Kim

Rom j=5 [ Eva Jan Guy Ann Dot Jim ] Kay Kim Rom [ Jan Eva Guy Ann Dot ] Jim Kay Kim Rom j=4 [ Dot Eva Guy Ann Jan ] Jim Kay Kim Rom [ Guy Eva Dot Ann ] Jan Jim Kay Kim Rom j=3 [ Ann Eva Dot Guy ] Jan Jim Kay Kim Rom [ Eva Ann Dot ] Guy Jan Jim Kay Kim Rom j=2 [ Dot Ann Eva ] Guy Jan Jim Kay Kim Rom [ Dot Ann ] Eva Guy Jan Jim Kay Kim Rom j=1 [ Dot Ann ] Eva Guy Jan Jim Kay Kim Rom

[ Ann ]

Dot

Eva

Guy

Jan

Jim

Kay

Kim

Rom

(2) 按数值递增顺序排序形成初始堆 (按最大堆)

0 1 2 3 4 5 6 26 33 35 29 19 12 22 i=2 26 33 [ 35 29 19 12 22 ] i=0 26 [ 33 35 29 19 12 22 ] i=1

[ 35

22 ]

堆排序

0 1 2 3 4 5 6 j=6 [ 22 33 26 29 19 12 35 ] 交换 [ 33 29 26 22 19 12 ] 35 调整为堆 j=5 [ 12 29 26 22 19 33 ] 35 交换 [ 29 22 26 12 19 ] 33 35 调整为堆 j=4 [ 19 22 26 12 29 ] 33 35 交换 [ 26 22 19 12 ] 29 33 35 调整为堆 j=3 [ 12 22 19 26 ] 29 33 35 交换 [ 22 12 19 ] 26 29 33 35 调整为堆 j=2 [ 19 12 22 ] 26 29 33 35 交换 [ 19 12 ] 22 26 29 33 35 调整为堆 j=1 [ 12 19 ] 22 26 29 33 35 交换

[ 12 ]

调整为堆

(3) 同样7个数字，换一个初始排列，再按数值的递增顺序排序

Ron Tim Ron Tim Ron Tim Ron Tim Ron Tim Ron Tim Ron Tim Ron Tim Ron Tim Ron Tim Ron Tim Ron Tim Ron Tim Ron Tim Ron

Tim

调整交换调整交换调整交换调整交换调整交换调整交换调整交换调整

形成初始堆 (按最大堆)

i=2 i=0 i=1

0 12 12 12 [ 35

1 19 19 [ 29 29

2 33 [ 35 35 33

3 26 26 26 26