数据结构课后习题

1、第一章3. (1) A (2) C ( 3) D5计算下列程序中x=x+1的语句频度for(i=1;i<=n ;i+)for(j=1;j<=i;j+) for(k=1;k<=j;k+) x=x+1;【解答】x=x+1的语句频度为：T(n )=1+(1+2)+( 1+2+3) +(1+2+ +n=n(n+1)( n+2)/66编写算法，求一元多项式pn(x)=ao+a1X+a2X2+ .+an的值Pn(xo)，并确定算法中每一语句的 执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幕函数。注意：本题中的输入为 ai(i=0,1,n)和n,输出为Pn(

2、xo)。算法的输入和输出采用下列 方法(1 )通过参数表中的参数显式传递(2 )通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实 现输入输出。【解答】(1 )通过参数表中的参数显式传递优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通 用性强，移置性强。缺点：形参须与实参对应，且返回值数量有限。(2) 通过全局变量隐式传递优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数PolyValue() int i,n;float x,a,p;printf( nn= ”

3、);scanf( “ f”，&n);printf( nx= ” );scanf( “ f”，&x);for(i=0;i< n; i+)scanf( “ f ”，&ai)/* 执行次数：n 次 */p=a0;for(i=1;i<=n ;i+) p=p+ai*x;/* 执行次数：n 次 */x=x*x;printf( “ f” ,p);算法的时间复杂度：T( n)=0( n)通过参数表中的参数显式传递float PolyValue(float a , float x, int n)float p,s;int i;p=x;s=a0;for(i=1;i<=n

4、;i+)s=s+ai*p;/* 执行次数：n 次*/P=P*x;return(p);算法的时间复杂度：T( n)=0( n)第二章1. 填空:(1) 在顺序表中插入或删除一个元素，需要平均移动一半元素，具体移动的元素个数与插入或删除的位置有关。(2) 线性表有顺序和链式两种存储结构。在顺序表中，线性表的长度在数组定义时就已经确定，是静态保存，在链式表中，整个链表由头指针”来表示，单链表的长度是 动态保存。(3) 在顺序表中，逻辑上相邻的元素，其物理位置二定相邻。在单链表中，逻辑上相邻的元素，其物理位置不一定相邻。(4) 在带头结点的非空单链表中，头结点的存储位置由头指针指示，首元素结点的存储位

5、置由头结点指示，除首元素结点外，其它任一元素结点的存储位置由其直接前趋的next域指示。2. 选择题(1) A 已知L是无表头结点的单链表，且P结点既不是首元素结点，也不是尾元素结点。按要求从下列语句中选择合适的语句序列。a. 在P结点后插入S结点的语句序列是：D、A。b. 在P结点前插入S结点的语句序列是：G、K、H、D、Aoc. 在表首插入S结点的语句序列是：E、Lod. 在表尾插入S结点的语句序列是：(K)、I、A、Fo 供选择的语句有：A P-> next=S;B P->n ext= P->n ext->n ext;C P-> next= S-> n

6、ext;D S-> next= P-> next;E S-> next= L;F S-> next= NULL;G Q= P;H while (P-> next!=Q) P=P-> next;I while (P-> next!=NULL) P=P-> next;J P= Q;K P= L;L L= S;M L= P;DDD4. 已知顺序表L递增有序，编写一个算法，将 X插入到线性表的适当位置上，以保持线性 表的有序性。void inserX(Seqlist *L,Elemtype x) int i;i=L->le ngth -1;whil

7、e(i >=0 && x<L-> elem i)L->elem i +1= L->elem i;i-；L->le ngth +;7试分别以不同的存储结构实现线性表的就地逆值的算法，即在原表的存储空间中将线性 表 (a1,a2,an 逆置为(an,an-1,a1。(1)以顺序表作存储结构，设线性表存于a1:arrsize啲前elenum个分量中。void reverseqlist (Seqlist * L)int i;int temp ;for(i=0;i<L->length / 2;i+) temp =L->elem i ;

8、L->elemi= L->elem L->length -i-1;L->elem L->length -i- 1=temp;(2 )以单链表作存储结构。void reverselinklist (linklist * head) Li nklist * p ,* q;p=head ->n ext; head ->n ext =NULL;while(p->next !=NULL) q=p- >n ext;p->n ext =head ->n ext;head ->n ext =p;p=q;11将线性表 A=(a1,a2,am

9、), B=(b1,b2,合并成线性表 C,C=(a1,b1, am,bm,bm+1,nbn=n,或C=(a1,b1, an,bn,an+1, mmn,线性表A、B、C以单链表作为存储结构，且C表利用A表和B表中的结点空间构成。注意：单链表的长度值m和n均未显式存储。【解答】算法如下：LinkList merge (LinkList A, LinkList B LinkList C)Node * pa, *qa, *pb, * qb, * p;pa=A-> next;/*pa表示A的当前结点*/pb =B->n ext;p=A; / *利用p来指向新连接的表的表尾，初始值指向表 A的

10、头结点*/ while(pa!=NULL && pb!=NULL) /*利用尾插法建立连接之后的链表 */ qa=pa- >next;qb=qb ->n ext;p->next=pa;/*交替选择表A和表B中的结点连接到新链表中；*/p=pa;p->n ext=pb;p=pb;pa=qa;pb=qb;if(pa!=NULL p->next =pa;/*A 的长度大于 B 的长度 */if(pb!=NULL p->next =pb;/*B 的长度大于 A 的长度 */C=A;Return (C);第三章1 B2 C3 C8假设表达式由单字母变量

11、和双目四则运算构成。试写一个算法，将一个通常书写形式且书 写正确的表达式转为逆波兰式。【分析】算法的思想：所有的变量在逆波兰式中出现的先后顺序和在原表达式中出现的相同，因此只需要设立一个 "栈"，根据操作符的”优先级”调整它们在逆波兰式中出现的顺序。#i nclude <stdio.h>#i nclude <malloc.h>#defi ne STACK_INIT_SIZE 100#defi ne STACK_INCREAMENT 10typedef struct / 栈char *base;char *top;int stackSize; Stac

12、k;void initStack(Stack &stack) / 初始化栈stack.base = stack.top = (char *)malloc(sizeof(char) * STACK_INIT_SIZE);stack.stackSize = STACK_INIT_SIZE;void push(Stack &S, char p) / 入栈if(S.top - S.base >= S.stackSize) S.base=(char*)realloc(S.base,(S.stackSize+STACK_INCREAMENT)*sizeof(char);S.top =

13、 S.stackSize + S.base;S.stackSize += STACK_INCREAMENT;*S.top+ = p;void pop(Stack &stack, char &p) / 出栈if(stack.base = stack.top) p = NULL; return ;p = *-stack.top;char getTop(Stack stack) / 获得栈顶元素if(stack.base = stack.top) retur n NULL;return *(stack.top - 1);bool isAlpha(char p) /判断是不是字母ret

14、urn (p >= 'a' && p <= 'z') | (p >= 'A' && p <= 'Z') ? true : false;int precede(char a, char b) switch (a) case '/':case '*' : retur n 1; break;case '+':case '-':switch(b) case '/':case '*' : r

15、etur n -1; break;default : return 1;break;default :switch(b) case '#' : retur n 0; break;default : return -1;void NiBoLa n( char *str, char *n ewStr) / 转换成逆波兰式Stack stack;in itStack(stack);char *p, *q, c;p = str; q = n ewStr; push(stack, '#');while(*p) if(isAlpha(*p) *q+ = *p;else c

16、= getTop(stack);if(precede(*p, c) > 0) push(stack, *p);else while(precede(getTop(stack), *p) >= 0 && *p) pop(stack, c);*q+ = c;push(stack, *p);p +;void mai n() char str1OO;char newStr100;int i;for(i=0; i<100; i+) stri = newStri = '0'printf("请输入表达式：n");scanf("%

17、s", str);NiBoLa n(str, newStr);printf("其对应的逆波兰式为：sn", newStr);"语言程序谟计Stack-转换为逆波兰式诒输入表达式；a+bc«d-e#其对应的也波兰式为；abcd«-+e-#Press an 1/ kuy to con七:inuiE 搜狗拼音半：10要求循环队列不损失一个空间全部都能得到利用，设置一个标志tag,以tag为0或1来区分头尾指针相同时的队列状态的空与满，请编写与此相应的入队与出队算法。入队算法:intEnterQueue (SeqQueue* Q,QueueE

18、leme ntType x)1/*将元素x入队*/if(Q->fro nt =Q->fro nt&&tag=1)/*队满*/return( FALSE；if(Q->fro nt =Q->fro nt&&tag=0)/*x入队前队空，x入队后重新设置标志*/tag=1;Q->elememt Q->rear=x;Q->rear=(Q->rear+1)%MAXSIZE；/* 设置队尾指针 */Retur n (TRUE;岀队算法：int DeleteQueue ( SeqQueue * Q , QueueEleme nt

19、Type * x)/*删除队头元素，用x返回其值*/if(Q->front =Q->rear && tag=0)/* 队空 */return( FALSE；*x =Q->element Q->front ;Q->front =(Q->front + 1)%MAXSIZE/* 重新设置队头指针 */if(Q->fro nt =Q->rear)tag=0;/*队头元素岀队后队列为空，重新设置标志域*/Retur n (TUUE);15(1)功能：将栈中元素倒置。(2)功能：删除栈中的 e元素。(3 )功能：将队列中的元素倒置。第四章1

20、.设 s=' I AM A STUDENTt= ' GOO,D q=' 【解答】StrLe ngth(s)=14;SubStri ng(sub1,s,1,7)SubStri ng(sub2,s,7,1)StrIndex(s,4,A' )=6;WORKER给出下列操作的结果:sub仁'I AM A ' sub2=''；s= ' I AM A WORKERStrCat(StrCat(sub1,t),StrCat(sub2,q)sub1= ' I AM A GOOD WORKER'StrReplace(s, &#

21、39; STUDENT ,q);4.叙述以下每对术语的区别：空串和空格串；串常量与串变量；主串和子串；串变量的名字和串变量的值。【解答】 不含任何字符的串称为空串，其长度为0。仅含有空格字符的串称为空格串，其长度为串中空格字符的个数。 空格符可用来分割一般的字符，便于人们识别和阅读， 但计算串长时应包括这些空格符。空串在串处理中可作为任意串的子串。用引号(数据结构教学中通常用单引号，而C语言中用双引号)括起来的字符序列称为串常 量，串值可以变化的量称为串变量。串中任意个连续的字符组成的子序列被称为该串的子串。包含子串的串又被称为该子串的主 串。子串在主串中第一次出现的第一个字符的位置称子串在主

22、串中的位置。串变量的与其它变量一样， 要用名字引用其值， 串变量的名字也是标识符，串变量的值可以修改。5.已知：s = " (xyz)+ *" , t = " (x+ z)*y"。试利用联结、求子串和置换等基本运算，将s转化为t。【答案】本题有多种解法，下面是其中的一种:(1)s1=substr( s,3,1)/*取出子串："y"(2)s2=substr( s,6,1)/*取出子串："+"(3)s3=substr( s,1,5)/*取出子串："(xyz)"(4)s4=substr( s,7,1)

23、/*取出子串：(5)s5=replace ( s3,3,1,s2)/*形成部分串：” (x+z)"(6)s=s5*s4/*s1/*形成串t 即 ” (x+z)*y"【解析】题中所给操作的含义如下：/* :连接函数，将两个串连接成一个串substr(s,i,j)：取子串函数，从串s的第i个字符开始，取连续j个字符形成子串replace ( s1,i,j,s2)：置换函数，用s2串替换si串中从第i个字符开始的连续j个字符 8编写下列算法：(1)将顺序串r中所有值为chi的字符换成ch2的字符。(2)将顺序串r中所有字符按照相反的次序仍存放在r中。(3)从顺序串r中删除其值等于

24、ch的所有字符。(4)从顺序串r1中第index个字符起求出首次与串r2相冋的子串的起始位置(5)从顺序串r中删除所有与串ri相冋的子串。【解答】(1)Void replace (Str *r, char ch1,char ch2) /将串r中所有值为 chi的字符换成 ch2的字符 for(i nt i=0;i<r->le n;i+)if (r->veci=ch1) r->veci=ch2;return;Void converse(str *r) /将串r中所有字符按照相反的次序存放在r中for(int i=0;i<(r->len/ 2);i+)Char

25、ch=r->veci;r->veci=r->vecr->le n_1_i;r->vecr->le n-1-i=ch;Return;Void delete(str *r,char ch) /从串r中删除其值等于 ch的所有字符int i=0; in t le n=ren;While (i<le n)if (r->veci=ch for(j=i; j<le n-1; j+)r->vecj=r-vec|j+1;len-;elsei+；return;int positi on( str r1,i nt in dex,char r2)/从串r1

26、中第index个字符起求出首次与字符r2相同的子串的起始位置if (index<1|index>r.len) return ERROR;int i=in dex;while (r,veci!=r2 &&i<r.le n) i+;if (i=r.len)cout<< 不存在” 丁eturn; return i+1;int DelSub(SStri ng *r,SStri ng r1)int i,j,t;if(r->le n<r1.len) retur n( 0);for(i=0;i<r->le n-r1.le n;)j=i;f

27、or(t=0;t<r1.le n;t+)if(r->chj+!=r1.cht) break;if(t=r1.le n)for(j=i;j+r1en< r->le n;j+)r->chj=r->chj+r1 .len;r->le n-=r1.len;if(t!=r1.len) i+;return(1);® ® ® ®课本119页8_1题.c 课本119页8_2题.c 课本119页8_3题.c 课本119页8_4题.c课本119页8_5题.c第五章1.假设有6行8列的二维数组 A,每个元素占用6个字节，存储器按字节编

28、址。已知A的基地址为1000，计算：(1)数组A共占用多少字节；(288)(2)数组A的最后一个兀素的地址；(1282)(3)按行存储时，兀素A36的地址；(1126)(4)按列存储时，兀素A36的地址；(1192)3.设有一个上三角矩阵A,将其上三角中的元素逐列压缩存储到一个n(n+1)/2的一维数组C(下标从1开始)，请给出计算上三角矩阵中任意元素 aj( i< j )在一维数 组C中位置的公式。K=n+n-(i-2)*(i-1)/ 2+j-(i-1)=(2n-i+2)*(i-1)/ 2+(j-i+1) i<=j4设有三对角矩阵 Anxn将其三条对角线上的元素逐行的存于数组B1

29、.3n-2中，使得Bk=aj,求：(1 )用i,j表示k的下标变换公式；(2)用k表示i、j的下标变换公式。【解答】(1) k=2(i-1)+j i=k/3+1, j=k/3+k%3(取整，取余)7编写一个在十字链表按三元组表的形式打印输出。解：矩阵相加就是将两个矩阵中同一位置的元素值相加。由于两个稀疏矩阵的非零元素按三元组表形式存放，在建立新的三元组表C时，为了使三元组元素仍按行优先排列，所以每次插入的三元组不一定是A的，按照矩阵元素的行列去找A中的三元组，若有，则加入C,同时，这个元素如果在 B中也有，则加上B的这个元素值，否则这个值就不变；如果A中没有， 则找B,有则插入C,无则查找下一

30、个矩阵元素。#defineMaxSize 10/ 用户自定义typedefint DataType; / 用户自定义typedef struct/定义三元组int i,j;DataType v;TriTupleNode;typedef struct/定义三元组表TriTupleNode dataMaxSize;intm,n,t;矩阵行，列及三元组表长度TriTupleTable;/以下为矩阵加算法void AddTriTuple( TriTupleTable *A, TriTupleTable *B, TriTupleTable *C)/三元组表表示的稀疏矩阵A,B相加int k,l;Data

31、Type temp;C-> m=A-> m;/矩阵行数C-> n=A-> n;矩阵列数C-> t=0;/三元组表长度k=0;1=0;while (k <A-> t&&l <B-> t)if(A-> datak.i=B-> datal.i) &&(A-> datak.j=B-> datal.j) temp=A-> datak.v+B-> datal.v;if(!temp)相加不为零，加入CC-> datac-> t.i=A-> datak.i;C->

32、datac-> t.j=A-> datak.j;C-> datac-> t+.v=temp; k+;l+;if (A-> datak.i=B-> datal.i)&&(A-> datak.j <B-> datal.j) |(A-> datak.i <B-> datal.i) 将 A 中三元组加入 C C-> datac-> t.i=A-> datak.i;C-> datac-> t.j=A-> datak.j;C-> datac-> t+.v=A-> d

33、atak.v;k+;if (A-> datak.i=B-> datal.i)&&(A-> datak.j> B-> datal.j) |(A-> datak.i> B-> datal.i) 将 B 中三元组加入 C C-> datac-> t.i=B-> datal.i;C-> datac-> t.j=B-> datal.j;C-> datac-> t+.v=B-> datal.v;l+;while (k <A-> t)/将A中剩余三元组加入 CC-> dat

34、ac-> t.i=A-> datak.i;C-> datac-> t.j=A-> datak.j;C-> datac-> t+.v=A-> datak.v;k+;while (l <B-> t)/将B中剩余三元组加入 CC-> datac-> t.i=B-> datal.i;C-> datac-> t.j=B-> datal.j;C-> datac-> t+.v=B-> datal.v;l+;9.求下列广义表运算的结果。(1) HEAD(a,b),(c,d)(2) TAIL(a,b

35、),(c,d)(3) TAILHEAD(a,b),(c,d)(4) HEADTAILHEAD(a,b),(c,d)(5) TAILHEADTAIL(a,b),(c,d) 解答：(1) (a,b) (2) (c,d) (3) (b) (4) b (5) (d)第六章6.1分别画出具有3个结点的树和 【解答】具有3个结点的树3个结点的二叉树的所有不同形态。具有3个结点的二叉树6.4假设一棵二叉树的先序排列为EBADCFHGIKJ中序序列为 ABCDEFGHIJK请画出该二叉树。6.5已知二叉树有50个叶子结点，则该二叉树的总结点数至少应有多少个？【解答】no表示叶子结点数，n2表示度为2的结点数，则no = n2+1 所以n2= no -1=49，当二叉树中没有度为 1的结点时，总结点数 n=no+n2=996.8画出与下列已知序列对应的树T:树的先根次序访问序列为 GFKDAIEBCHJ;树的后根次序访问序列为 DIAEKFCJHBG.解答：树的后根遍历相当于二叉树的中序遍历。先转换为二叉树，在根据左孩子右兄弟的规则转换为数。6.9假设通讯的电文仅由