耿国华 - 数据结构 - C语言的描述 - 课后大部分习题答案[1] 下载本文

第一章 三、计算下列程序段中X=X+1 的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; [提示]:

i=1 时: 1 = (1+1)×1/2 = (1+1 )/2 i=2 时: 1+2 = (1+2)×2/2 = (2+22)/2 i=3 时: 1+2+3 = (1+3)×3/2 = (3+32)/2 ?

i=n时: 1+2+3+??+n = (1+n)×n/2 = (n+n )/2

f(n) = [ (1+2+3+……+n) + (1 + 2 + 3 + …… + n ) ] / 2 =[ (1+n)×n/2 + n(n+1)(2n+1)/6 ] / 2 =n(n+1)(n+2)/6 =n /6+n /2+n/3

区分语句频度和算法复杂度: O(f(n)) = O(n )

四、试编写算法求一元多项式Pn(x)=a +a x+a x +a x +?a x 的值P (x ),并确定算法中的每 一语句的执行次数和整个算法的时间复杂度,要求时间复杂度尽可能的小,规定算法中不能 使用求幂函数。注意:本题中的输入a (i=0,1,?,n), x和n,输出为P (x ).通常算法的输入和输出可采用下列两种方式之一:

(1)通过参数表中的参数显式传递; (2 )通过全局变量隐式传递。

试讨论这两种方法的优缺点,并在本题算法中以你认为较好的一种方式实现输入和输出。 [提示]:float PolyValue(float a[ ], float x, int n) {??} 核心语句:

p=1; (x 的零次幂) s=0;

i 从0 到n 循环 s=s+a[i]*p; p=p*x; 或:

p=x; (x 的一次幂) s=a[0];

i 从 1 到n 循环 s=s+a[i]*p; p=p*x;

第二章

2.1 描述以下三个概念的区别:头指针,头结点,首元素结点。 2.2 填空:

(1) 在顺序表中插入或删除一个元素,需要平均移动 一半 元素,具体移动的元素个数与 插入或删除的位置 有关。

(2 ) 在顺序表中,逻辑上相邻的元素,其物理位置 相邻。在单链表中,逻辑上

相邻的元素,其物理位置 相邻。

(3) 在带头结点的非空单链表中,头结点的存储位置由 指示,首元素结点的存储位置由 指示,除首元素结点外,其它任一元素结点的存储位置由 其直接前趋的next 域 指示。

2.3 已知L 是无表头结点的单链表,且P 结点既不是首元素结点,也不是尾元素结点。按要求从下列语句中选择合适的语句序列。

a. 在P结点后插入S结点的语句序列是: (4 )、(1) 。 b. 在P结点前插入S结点的语句序列是: (7)、(11)、(8)、(4 )、(1)。 c. 在表首插入S结点的语句序列是: (5)、(12)。 d. 在表尾插入S结点的语句序列是: (11)、(9)、(1)、(6)。 供选择的语句有: (1)P->next=S;

(2 )P->next= P->next->next; (3)P->next= S->next; (4 )S->next= P->next; (5)S->next= L;

(6)S->next= NULL; (7)Q= P;

(8)while(P->next!=Q) P=P->next; (9)while(P->next!=NULL) P=P->next; (10)P= Q; (11)P= L; (12)L= S; (13)L= P;

2.4 已知线性表L 递增有序。试写一算法,将 X 插入到 L 的适当位置上,以保持线性表L的有序性。

[提示]:void insert(SeqList *L; ElemType x) < 方法 1 >

(1)找出应插入位置i,(2 )移位,(3)?? < 方法2 > 参P. 229

2.5 写一算法,从顺序表中删除自第i 个元素开始的k 个元素。 [提示]:注意检查i 和k 的合法性。(集体搬迁,“新房”、“旧房”) < 方法 1 > 以待移动元素下标m(“旧房号”)为中心,计算应移入位置(“新房号”): for ( m= i -1+k; m<= L->last; m++) L ->elem[ m-k ] = L->elem[ m ];

< 方法2 > 同时以待移动元素下标m 和应移入位置j 为中心: < 方法2 > 以应移入位置j 为中心,计算待移动元素下标:

2.6 已知线性表中的元素(整数)以值递增有序排列,并以单链表作存储结构。试写一高效算法,删除表中所有大于mink 且小于maxk 的元素(若表中存在这样的元素),分析你的算法的时间复杂度(注意:mink 和maxk 是给定的两个参变量,它们的值为任意的整数)。 [提示]:注意检查mink 和maxk 的合法性:mink < maxk不要一个一个的删除(多次修改next 域)。

(1)找到第一个应删结点的前驱pre pre=L; p=L ->next;

while (p!=NULL && p ->data <= mink) { pre=p; p=p ->next; }

(2 )找到最后一个应删结点的后继s,边找边释放应删结点 s=p;

while (s!=NULL && s->data < mink) { t =s; s=s ->next; free(t); } (3)pre ->next = s;

2.7 试分别以不同的存储结构实现线性表的就地逆置算法,即在原表的存储空间将线性表(a1, a ..., a )逆置为(a , a ,..., a )。

(1) 以一维数组作存储结构,设线性表存于a(1:arrsize)的前elenum 个分量中。 (2 ) 以单链表作存储结构。 [方法 1]:在原头结点后重新头插一遍

[方法2]:可设三个同步移动的指针p, q, r,将q 的后继r 改为p

2.8 假设两个按元素值递增有序排列的线性表A 和B,均以单链表作为存储结构,请编写算法,将A 表和B 表归并成一个按元素值递减有序的排列的线性表 C,并要求利用原表(即A 表和B 表的)结点空间存放表 C. [提示]:参P.28 例2-1 < 方法 1 >

void merge(LinkList A; LinkList B; LinkList *C) { ……

pa=A ->next; pb=B->next; *C=A; (*C)->next=NULL; while ( pa!=NULL && pb!=NULL ) { if ( pa ->data <= pb->data ) { smaller=pa; pa=pa->next;

smaller->next = (*C)->next; /* 头插法 */ (*C) ->next = smaller; } else

{ smaller=pb; pb=pb->next; smaller->next = (*C)->next; (*C) ->next = smaller; }

while ( pa!=NULL)

{ smaller=pa; pa=pa->next; smaller ->next = (*C)->next; (*C) ->next = smaller; }

while ( pb!=NULL)

{ smaller=pb; pb=pb->next; smaller ->next = (*C)->next; (*C) ->next = smaller; }

< 方法2 >

LinkList merge(LinkList A; LinkList B) { ……

LinkList C;

pa=A ->next; pb=B->next; C=A; C->next=NULL; ?? ??

return C;

2.9 假设有一个循环链表的长度大于 1,且表中既无头结点也无头指针。已知s为指向链表某个结点的指针,试编写算法在链表中删除指针 s 所指结点的前趋结点。 [提示]:设指针p 指向 s 结点的前趋的前趋,则p 与s 有何关系?

2.10 已知有单链表表示的线性表中含有三类字符的数据元素(如字母字符、数字字符和其它字符),试编写算法来构造三个以循环链表表示的线性表,使每个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间。

2.11 设线性表A=(a, a ,?,a ),B=(b, b ,?,b ),试写一个按下列规则合并A、B为线性表C的算法,使得:

C= (a , b ,?,a , b , b ?,b ) 当m≤n时; 或者 C= (a , b ,?,a , b , a ?,a ) 当m>n时。

线性表 A、B、C 均以单链表作为存储结构,且 C 表利用 A 表和 B 表中的结点空间构成。

注意:单链表的长度值m 和n 均未显式存储。

[提示]:void merge(LinkList A; LinkList B; LinkList *C) 或:LinkList merge(LinkList A; LinkList B)

2.12 将一个用循环链表表示的稀疏多项式分解成两个多项式,使这两个多项式中各自仅含奇次项或偶次项,并要求利用原链表中的结点空间来构成这两个链表。 [提示]:注明用头指针还是尾指针。

2.13 建立一个带头结点的线性链表,用以存放输入的二进制数,链表中每个结点的 data 域存放一个二进制位。并在此链表上实现对二进制数加 1 的运算 。 [提示]:可将低位放在前面。

2.14 设多项式P(x)采用课本中所述链接方法存储。写一算法,对给定的x 值,求P(x)的值。 [提示]:float PolyValue(Polylist p; float x) {??} 第三章

1. 按图3.1(b)所示铁道(两侧铁道均为单向行驶道)进行车厢调度,回答:

⑴ 如进站的车厢序列为 123,则可能得到的出站车厢序列是什么? 123、213、132、231、321 (312)

⑵如进站的车厢序列为 123456,能否得到435612 和 135426 的出站序列,并说明原因。(即 写出以“S”表示进栈、以“X”表示出栈的栈操作序列)。 SXSS XSSX XXSX 或 S1X1S2S3X3S4S5X5X4X2S6X6

2. 设队列中有A、B、C、D、E 这 5 个元素,其中队首元素为A 。如果对这个队列重复执行下列4 步操作:

(1) 输出队首元素;

(2 ) 把队首元素值插入到队尾; (3) 删除队首元素;

(4 ) 再次删除队首元素。

直到队列成为空队列为止,则是否可能得到输出序列:

(1) A、C、E、C、C (2) A、C、E (3) A、C、E、C、C、C (4 ) A、C、E、C [提示]:

A、B、C、D、E (输出队首元素A )

A、B、C、D、E、A (把队首元素A 插入到队尾) B、C、D、E、A (删除队首元素A ) C、D、E、A (再次删除队首元素B) C、D、E、A (输出队首元素C)

C、D、E、A、C (把队首元素C 插入到队尾) D、E、A、C (删除队首元素C) E、A、C (再次删除队首元素D )

3. 给出栈的两种存储结构形式名称,在这两种栈的存储结构中如何判别栈空与栈满? 4. 按照四则运算加、减、乘、除和幂运算(↑)优先关系的惯例,画出对下列算术表达式求值时操作数栈和运算符栈的变化过程: A -B *C/D+E↑F

5. 试写一个算法,判断依次读入的一个以@为结束符的字母序列,是否为形如‘序列1&序列2’模式的字符序列。其中序列1 和序列2 中都不含字符’&’,且序列2 是序列 1的逆序列。例如,‘a+b&b+a’是属该模式的字符序列,而‘1+ 3& 3-1’则不是。 [提示]:

(1) 边读边入栈,直到&

(2 ) 边读边出栈边比较,直到??

6. 假设表达式由单字母变量和双目四则运算算符构成。试写一个算法,将一个通常书写形式(中缀)且书写正确的表达式转换为逆波兰式(后缀)。 [提示]: 例:

中缀表达式:a+b 后缀表达式: ab+

中缀表达式:a+b×c 后缀表达式: abc×+ 中缀表达式:a+b×c-d 后缀表达式: abc×+d- 中缀表达式:a+b×c-d/e 后缀表达式: abc×+de/- 中缀表达式:a+b×(c-d)-e/f 后缀表达式: abcd-×+ef/- ? 后缀表达式的计算过程:(简便) 顺序扫描表达式,

(1) 如果是操作数,直接入栈;

(2 ) 如果是操作符op,则连续退栈两次,得操作数X, Y,计算X op Y,并将结果入栈。

? 如何将中缀表达式转换为后缀表达式? 顺序扫描中缀表达式,

(1)如果是操作数,直接输出;

(2 )如果是操作符op ,则与栈顶操作符op 比较: 如果op > op ,则op 入栈; 如果op = op ,则脱括号; 如果op < op ,则输出op ;

7. 假设以带头结点的循环链表表示队列,并且只设一个指针指向队尾元素结点(注意不设