算法与数据结构C语言习题参考答案5章汇编

1、学习 好资料1. 绪 论1将下列复杂度由小到大重新排序：A 2nBn!Cn5【答】10 000< n*log 2(n)< n5< 2n < n!D 10 000E. n*log 2 (n)2将下列复杂度由小到大重新排序：23A n*log 2(n)B n + n + nC.240.5D. n【答】 24< n0.5< n*log 2 (n) < n + n2 + n33 用大“ 0”表示法描述下列复杂度：5/2 2/5A 5n + nB.6*log 2(n) + 9n4C 3n + n* log 2(n)D.5n2 + n3/2【答】A : 0 (n5

2、/2)B : 0 (n)C：0 (n4)2D： 0 (n2)4按照增长率从低到高的顺序排列以下表达式：4n2 , log3n, 3n , 20n , 2000 , log2nn2/3。又n!应排在第几位？【答】按照增长率从低到高依次为：2000, log3n, log2n , n2/3 , 20n , 4n2 , 3n。n!的增长率比它们中的每一个都要大，应排在最后一位。5. 计算下列程序片断的时间代价：int i=1;while(i<=n)printf( “i=%dn ”,i);i=i+1;【答】循环控制变量i从1增加到n,循环体执行n次，第一句i的初始化执行次数为1，第二 句执行n次

3、，循环体中第一句 printf执行n次，第二句i从1循环到n，共执行n次。所以该程 序段总的时间代价为：T(n) = 1 + n + 2n = 3n+ 1 = O(n)6. 计算下列程序片断的时间代价：int i=1;while(i<=n)int j=1;while(j<=n)int k=1;while(k<=n)printf( “i=%d,j=%d,k=%dn ”,I,j,k);k=k+1;j=j+1;i=i+1;【答】循环控制变量i从1增加到n,最外层循环体执行 n次，循环控制变量j从1增加到n, 中间层循环体执行n次，循环控制变量k从1增加到n,最内层循环体执行n次，所

4、以该程序段 总的时间代价为：T(n) = 1 + n + n 1 + n + n1 + n + 2n +1 +1 +1 + 132= 3n + 3n +4n +2= O(n3)更多精品文档学习-好资料2.线性表1.试写一个插入算法intinsertPost_seq(palist, p, x )，在palist所指顺序表中，下标为p的元素之后，插入一个值为x的元素，返回插入成功与否的标志。【答】数据结构采用2.1.2节中顺序表定义。int insertPost_seq(PseqList palist, int p, DataType x )/*在palist所指顺序表中下标为p的元素之后插入元素

5、 x */int q；if ( palist->n >= palist-> MAXNUM ) /* 溢出 */printf( “n”)；return 0;if (p<0| p>palist->n-1 ) /* 不存在下标为 p 的元素 */printf( “Nn”； return 0;for(q=palist->n - 1; q>=p+1; q-)/*插入位置及之后的元素均后移一个位置*/palist->elementq+1 = palist->elementq;palist->elementp+1 = x;/* 插入元素 x

6、*/palist->n = palist->n + 1;/* 元素个数加 1 */return 1;2试写一个删除算法deleteV_seq(palist, x )，在palist所指顺序表中，删除一个值为 x的元素，返回删除成功与否的标志。【答】数据结构采用2.1.2节中顺序表定义。int deleteV_seq(PseqList palist, p, DataType x ) /*在palist所指顺序表中删除值为x的元素*/int p,q;for(p=0;p<n;p+)/*查找值为x的元素的下标*/if(x=palist->elementp)for(q=p; q&

7、lt;palist->n-1; q+) /*被删除元素之后的元素均前移一个位置*/palist->elementq = palist->elementq+1;/*元素个数减1 */palist->n = palist->n - 1; return 1 ;return 0;3.设有一线性表e =(eo,ei, e2,，en j )，其逆线性表定义为e = (en_i ,，e2,ei,eo)。请设计一个算法，将用顺序表表示的线性表置逆，要求逆线性表仍占用原线性表的 空间。【答】数据结构 采用2.1.2节中顺序表的定义。思路考虑对数组element进行置逆，即把第一个元

8、素和最后一个元素换位置，把第二个 元素和倒数第二个元素换位置。注意这种调换的工作只需对数组的前一半元素进行，所以设置整数变量 count用于存放数组长度的一半的值。大家可以考虑一下：为什么不能对整个数组进行如上的对元素“换位置”的工 作？(提示：这样会将本来已经置逆的线性表又置逆回来，即又变成了原来的表。)顺序表的置逆算法void rev_seq(PSeqList palist)DataType x;int count, i;if (palist->n = 0 | palist->n = 1) return;/* 空表或只有一个元素，直接返回*/count = palist->

9、;n / 2;for ( i = 0; i < count; i+)/*只需调换半个表的元素 */x = palist->elementi;palist->elementi = palist->elementpalist->n 一 1 - i;palist->elementpalist->n 1 - i = x;代价分析该算法中包含一个for循环，其循环次数为 n/2。因此，算法的时间代价为 0(n)。4. 已知长度为n的线性表A采用顺序存储结构，请写一算法，找出该线性表中值最小 的数据元素。【答】数据结构采用2.1.2节中顺序表定义。思路设置变量mi

10、n，遍历整个表，不断更新当前已经经历过的元素的最小值即可。为方便起见，事先假设表不为空。 算法DataType min_seq(PSeqList palist)DataType min;int i;min = palist->elementO;for ( i = 1; i < palist->n; i+)if (min > palist->elementi) min = palist->elementi;return min;代价分析该算法访问顺序表中每个元素各一次, 讨论读者可以试图对上面的算法进行修改,/*求非空顺序表中的最小数据元素*/*初始化min*

11、/*min中保存的总是当前的最小数据 */时间代价为 0( n)。使返回的值不是最小元素的值而是它的下标。5. 已知线性表A的长度为n,并且采用顺序存储结构。写一算法，删除线性表中所有值为x的元素。【答】数据结构采用2.1.2节中顺序表的定义。思路为了减少移动次数，可以采用快速检索的思想，用两个变量i, j记录顺序表中被处理的两端元素的下标，开始时 i = 0，j = n-1,边检索第i个元素边增加i，直到找到一个元素 值等于x，再边检索第j个元素边减少j，直到找到一个元素值不等于X，把下标为j的元素移到下标为i的位置后重复上述过程，直到i >j。另用一变量count记录删除了多少个元素

12、。算法void delx_seq(PSeqList p, DataType x)/*删除顺序表中所有值为 x的元素，新顺序表可能不保持原有顺序*/int i = 0, j = p->n -1, count = 0;/* i定位于顺序表开始处，j定位于顺序表最后*/while ( i < j) if (p->elemen ti = x) /*找到了一个要删除的元素*/while (p->elementj = x) && (i != j) /*从后往前找不会被删除的元素，当i, j相等时退岀循环，count记录从后往前找的过程中遇到了多少个要删的元素*/j-

13、count+;if ( i = = j) p->n = p->n count .1;return;elsep->elementi = p->elementj;count+;j - ri+;p->n = p->n - count;if (p->elementi = x) p ->n _ 一；代价分析该算法访问顺序表中每个元素各一次，时间代价为0(n)。二讨论这个算法使用了一点技巧使得在中间删除元素时，避免了最后一串元素的移动。但 是，它破坏了原来线性表中元素之间的顺序关系。如果需要保持原来的顺序应该怎样做？这里提供一种可行的思路：从前向后遍历表，如

14、果元素不是X,则继续向后；如果元素是X,则寻找其后第一个不是x的元素，将这两个元素互换。具体算法请读者自己实现。6写一算法，在带头结点的单链表 llist中，p所指结点前面插入值为x的新结点，并返 回插入成功与否的标志。【答】数据结构采用2.1.3节中单链表定义。思想：由于在单链表中，只有指向后继结点的指针，所以只有首先找到p所指结点的前驱结点，然后才能完成插入。而找p所指结点的前驱结点，只能从单链表的第一个结点开始，使用与locatenk类似的方式进行搜索。算法：int insertPre_link(LinkList llist,PNode p,DataType x)/*在llist带头结点

15、的单链表中，p所指结点前面插入值为x的新结点*/PNode p1;if(llist=NULL) return 0;p1=llist;while(p1!=NULL&&p1->link!=p)p仁p1->link; /*寻找 p 所指结点的前驱结点 */if(p1=NULL) return 0;PNode q=(PNode)malloc(sizeof(struct Node);/* 申请新结点 */if(q=NULL) printf( Out of space!n ”return 0; q->info=x;更多精品文档学习-好资料q->link=p1->

16、;link;p1->link=q; return 1;7. 写一算法， 在带头结点的单链表 llist 中,删除 p 所指的结点， 并返回删除成功与否的标 志。【答】数据结构 采用 2.1.3 节中单链表定义。思想：由于在单链表中， 只有指向后继结点的指针， 所以只有首先找到 p 所指结点的前驱结点， 然 后才能完成删除。而找 p 所指结点的前驱结点，只能从单链表的第一个结点开始，使用与 locate_link 类似的方式进行搜索。int deleteP_link(LinkList llist,PNode p)/* 在 llist 带头结点的单链表中，删除 p 所指的结点 */PNode

17、 p1;if(llist=NULL)return Null;p1=llist; while(p1!=NULL&&p1->link!=p)p1=p1->link; /* 寻找 p 所指结点的前驱结点 */ if(p1=NULL)return 0;p1->link=p->link;free(p); /* 删除结点 p */return 1;8. 已知 list 是指向无头结点的单链表的指针变量，写出删除该链表下标为 i 的(第 i+1 个)结点的算法。【答】数据结构采用 2.1.3 节中单链表定义。思路依次遍历表中的每一个结点并计数， 到第 i+1 个结点时

18、实行删除。 由于链表是无头结 点的，所以在删除第一个结点时要特别注意。算法int deleteindex_link_nohead(LinkList * pllist, int i) /*删除单链表中下标为 i 的结点。删除成功返回 TRUE ，否则返回 FALSE。*/ int j;PNode p, q;if (*pllist) = NULL | i < 0) return FALSE;if ( i = = 0) /* 如果需要删除第一个结点 */q = (*pllist);(*pllist) = (*pllist)->link;free(q); return TRUE;p = (

19、*pllist);j = 0;while (p->link != NULL && j < i 1) /*寻找下标为 i _1 的结点的地址 */p = p->link;j+;if (p->link = NULL) return FALSE;/* 此元素不存在 */q = p->link;p->link = q->link;free(q); return TRUE;代价分析该算法访问单链表中前面i个结点，时间代价为 0(i)，最大不超过 0(n)。二讨论如果函数参数不是LinkList *类型而是LinkList类型，在删除i=0的结点时

20、，程序不能正确实现，其原因请读者思考(考虑 C语言的参数传递方式)。如果单链表带表头结点，重写本题的算法。比较这两个算法，是否能体会到表头结 点的作用。9. 已知list是指向无头结点的单链表的指针变量，写出删除该链表中从下标为i的(第i+1个)结点开始的连续 k个结点的算法。【答】数据结构采用2.1.3节单链表定义。思路这道题与上题相似，只需要增加计数即可。要注意的是应该判断给出的i和k是否合理，是不是会超出链表长度。算法int del_link_nohead(LinkList * pllist, int i, int k) /*删除单链表中从下标i开始的k个结点。删除成功返回 TRUE，否

21、则返回FALSE。*/int j;PNode p, q;if (*pllist) = NULL | i < 0 | k <= 0) return FALSE;if ( i = = 0) /*如果需要删除从第一个结点开始的k个结点*/for ( j = 0; j < k && (*pllist) != NULL; j+) q = (*pllist);(*pllist) = (*pllist)->link;free(q);更多精品文档学习-好资料更多精品文档return TRUE;p = (*pllist);j = 0;while ( p->link

22、!= NULL && j < i -1) /*寻找下标为i _1的结点的地址*/p = p_>link;j+；if (p->link = NULL) return FALSE;/*第i个结点不存在*/for ( j = 0; j < k && p->link != NULL; j+) q = p->link;p->link = q->link;free(q);return TRUE;代价分析该算法访问单链表中前面i + k个结点，时间代价为 O(i+k)，最大不超过 0(n)。13请设计一个算法，求出循环表中结点的

23、个数。【答】数据结构采用不带头结点的循环链表。struct Node;typedef struct Node * PNode;struct NodeDataType info;PNode link;typedef struct Node * LinkList;思路遍历整个循环链表，同时计数即可。二错误算法int count(LinkList clist)int count;PNode p, q; p = clist;q = p->link;if (clist = NULL) return 0;/*如果是空表*/count = 1;while ( q != p)q = q->link

24、;count+;return count;错误：如果clist是一个空表，那么第 5行的语句"q = p->link; ”是非法的。分析：应把第 6行语句(用下划线表示)提前 1行或 2行。一定要放在语句“ q = p->link; ”之、八前。缺点：增加局部变量p。分析：这样做没有必要，因为p的初值置为clist，在程序中并没有对p做其他修改，所以程序中不需要引入 p 而直接使用 clist 即可。算法int count(LinkList clist)int count;PNode q;if (clist = NULL) return 0;/* 如果是空表 */q =

25、clist->link;count = 1;while ( q != clist)q = q->link;count+;return count;代价分析该算法访问循环链表中每个结点各一次，时间代价为O(n)。4. 栈与队列1. 写一个递归算法来把整数字符串转换为整数。(例：“4356743567。)【答】思路先递归调用本算法转换除去末位外剩余的字符串，结果乘以10。再转换末位。将两结果相加即为所求。算法int stringTolnt1(char * s, int start, int end) /*把整数字符串s中从start到end的部分转换为整数*/if (start >

26、; end) return V;/* 转换失败 */if (start = end) return send 一'O'/* 只有一个字符，直接转换*/return stringToInt1(s, start, end -1) * 10 + send - 'O'/* 先转换其他位，再转换末位*/int stringToInt(char * s) /*把整数字符串 s转换为整数*/int i = 0;while (si != '0') i+;/* 计算字符串的长度 */return stringTolnt1(s, 0, i 1);代价分析设n为字符串

27、的长度。该算法访问每个字符各一次，时间代价为0(n)，计算字符串的长度的时间代价也为0(n)。故总的时间代价为0(n)。递归算法需要栈的支持，栈的大小与递归调用的深度成正比。所以实际空间开销为0(n)。2. 编写一个算法，对于输入的十进制非负整数，将它的二进制表示打印出来。【答】数据结构采用4.1.2节中栈的顺序表示。思路将输入的十进制数字反复除以2,直到它变为0。将每次的数字模2的余数入栈。栈中存放的就是所要求的二进制表示。再将栈中的元素依次弹出打印即可。算法void print_bin(int dec_number) /* 将十进制非负整数转化为二进制数打印出来*/PSeqStack pa

28、stack;int temp = dec_number; if (temp < 0) printf("Error!n"); return;pastack = createEmptyStack_seq();/* 建立一个空栈 */if (pastack = NULL) return;while (temp > 0) push_seq(pastack, temp % 2);temp /= 2; while(!isEmptyStack_seq(pastack) printf("%d", top_seq(pastack); pop_seq(pasta

29、ck); free(pastack);代价分析设输入的十进制数字为n,则算法的时间代价为 O(log2 n)。空间代价主要是栈的大小，为O( log 2 n)。3写一个算法： PSeqStack createEmptyStack_seq( int m ) 创建一个空栈。 数据结构采用 4.1.2 节中栈的顺序表示。PSegStack createEmptyStack_seq(int m)/* 创建一个空栈 */PSeqStack pastack = (PSeqStack)malloc(sizeof(struct SeqStack); if (pastack!=NULL) pastack -&g

30、t;s = (DataType*)malloc(sizeof(DataType)*m);if (pastack ->s)pastack ->MAXNUM=m;pastack ->t= -1;/* 栈顶变量赋值为 -1 */return (pastack );else free pastack;printf( “n”);/* 存储分配失败 */return NULL;4,写一个算法：int isEmptyStack_seq( PSeqStack pastack )判断 pastack所指的栈是否 为空栈。数据结构采用4.1.2节中栈的顺序表示。int isEmptyStack_

31、seq(PSeqStack pastack)/*判断pastack所指的栈是否为空栈 */if(pastack->t = -1) return 1;else return 0;8假设以循环链表表示队列，并且只设一个指针指向队尾元素结点(注意不设队头指 针)，试编写相应的创建空队列、入队列和出队列的算法。【答】数据结构 采用不带头结点的循环链表表示队列。struct Node;typedef struct Node * PNode; struct Node DataType info;PNode link;/*循环链表表示的队列类型*/*尾指针*/struct ClinkQueue PNo

32、de r;typedef struct ClinkQueue * PClinkQueue;/*指向循环链表表示的队列的指针类型*/认列的需坏链我投示思路与队列的单链表表示相似，但节省了指向队头的指针变量，所以在需要找表头结点时必须通过表尾指针进行。算法PClinkQueue createEmptyQueue_clink() /*创建空队列 */PClinkQueue pcqu = (PCIinkQueue)malloc(sizeof(struct ClinkQueue); pcqu->r = NULL;学习-好资料return pcqu;void enQueue_clink(PCIink

33、Queue pcqu, DataType x) /* 进队列 */PNode p;p = (PNode)malloc(sizeof(struct Node);p->info = x;if (pcqu->r = NULL) pcqu->r = p;p->link = p;return;p->link = pcqu->r->link;pcqu->r->link = p;pcqu->r = p;void deQueue_clink(PClinkQueue pcqu) PNode p;if (pcqu->r = NULL) printf

34、("Underflow!n"); return;if (pcqu->r->link = pcqu->r) free(pcqu->r); pcqu->r = NULL;return;p = pcqu->r->link;pcqu->r->link = p->link; free(p);代价分析上述几个算法都不包含循环，只有常数条语句,二讨论本题可以看成队列的循环表实现。/*进空队列，即往空队列中加入第一个结点*/*出队列*/*是空队列*/*只有一个元素的队列*/*指向队头*/因此每个算法的时间代价均为0(1)。5. 二

35、叉树与树1.写一个算法来计算给定二叉树的叶结点数。【答】数据结构采用5.1.3节中二叉树的链接表示。算法int num_of_leaves(BinTree t) /* 计算二叉树的叶结点个数 */if (t = = NULL) return 0;/*空树，返回 0*/if (t->llink = = NULL && t->rlink = = NULL) return 1;/* 根结点是树叶，返回 1*/return num_of_leaves(t->llink) + num_of_leaves(t->rlink);/*返回“左子树的叶结点数+右子树的叶结

36、点数"*/代价分析该算法访问每个结点各一次，时间代价为0(n)。空间代价为 0(h)。2假设二叉树采用链接方法存储，编写一个计算一棵二叉树t的高度的函数。【答】数据结构采用5.1.3节中二叉树的链接表示。思路对一棵二叉树t，考察它左右子树的高度，取其中大的一个，再加1即为t的高度。算法int depth(BinTree t)PBinTreeNode pbtree;int dl, dr;pbtree = t;if (pbtree = = NULL)return -1;dl = depth(pbtree->llink);dr = depth(pbtree->rlink);re

37、turn (dl > dr ? dl : dr) + 1;代价分析设树中的结点个数为n,递归访问次数只可能是n。所以，时间代价为 0(n)。空间代价为0(h)。h为二叉树的高度。6. 设计一个程序，根据二叉树的先根序列和对称序序列创建一棵用左右指针表示的二 叉树。【答】数据结构采用5.1.3节中二叉树的链接表示。思路二叉树的先根序列和对称序序列，用两个数组preorder和in order存放。先根序列的第一个元素的值preorder0应为二叉树的根上的元素值，在另一个数组中查到此值，设为inorderk。此时，数组 preorder中从preorder1到preorder k的序列(长

38、度为 k)和数组in order中从inorder0到inorderk_1(长度为k)的序列，恰好分别是根结点左子树( k个结点)的先根序列和对称序序列。数组preorder中从preorderk+1到preordern-1的序列(长度为n-k-1) 和数组in order中从in orderk+1到inordern-1(长度为n-k-1)的序列，恰好分别是根结点左子树(n*-1个结点)的先根序列和对称序序列。根据上述分析，算法先创建根结点，再递归调用自己两次来分别创建左右子树。算法int create_BTree(PBinTree pbtree, DataType * preorder, D

39、ataType * inorder, int n)/*根据先根序列 preorder和对称序序列inorder (长度为n)创建二叉树 pbtree。对于正确的先根 序列和对称序序列，算法返回TRUE，否则返回FALSE。*/int i, k;int tag1, tag2;if (n = = 0) *pbtree = NULL;return TRUE;for (i = 0; i < n; i+)if (inorderi = = preorder0)break;if (i = = n) *pbtree = NULL;return FALSE;/*输入的先根序列或对称序序列有误，创建失败*/

40、k = i;*pbtree = (PBinTreeNode)malloc(sizeof(struct BinTreeNode);(*pbtree)->i nfo = preorder0;tagl = create_BTree(&(*pbtree)->llink, preorder + 1, inorder, k);/*递归调用本算法创建左子树*/tag2 = create_BTree (&(*pbtree)->rlink, preorder + k + 1, inorder + k + 1, nk 1);/*递归调用本算法创建右子树*/if (tag1 = =

41、 TRUE && tag2 = = TRUE) return TRUE;return FALSE;/*二叉树创建成功当且仅当其左右子树都创建成功*/代价分析最坏的情况是，每个非叶结点只有左子树。这时两个数组之间需要比较n+(n-1)+ +1=0( n2)次。所以，该算法的时间代价为O(n2)。空间代价主要包括：存放二叉树的空间O( n)和用于递归调用的栈空间(不超过O(n )。并给出在这种表示基础上主要运算的实现算法。7试设计树的子表表示法的存储结构,【答】数据结构/*边表中结点的定义*/*子结点位置*/*下一个边的指针*/*结点的定义*/*结点本身信息*/*到子结点的边表*/

42、*树的定义*/*结点表*/*根的位置*/*结点的个数*/struct EdgeNodeint nodeposition;struct EdgeNode * link;struct ChiTreeNodeDataType info;struct EdgeNode * children;struct ChiTree struct ChiTreeNode nodelistMAXNUM;int root;int n;typedef struct ChiTree * PChiTree;算法创建空树PChiTree CreateNullTree_chitree(void)PChiTree p;p = (P

43、ChiTree)malloc(sizeof(struct ChiTree);if (p = = NULL)printf("Out of space!n");elsep_>n=O;p->root = -1; return p;判断树是否为空int isNull_chitree (PChiTree t)return t->n = = 0;返回非空树的根结点的下标DataType root_chitree (PChiTree t)return t->root;返回下标为p的结点的父结点的下标int parent_chitree (PChiTree t, i

44、nt p)int i;struct EdgeNode * v;if (p < 0 | p >= t->n) return -1; for (i = 0; i < t->n; i+)v = t->nodelisti.children; while (v != NULL)if (v->nodeposition = = p) return i;elsev = v->link;return J;返回下标为p的结点的最左子结点的下标int leftChild_chitree(PParTree t, int p)struct EdgeNode * v;if

45、(p < 0 | p >= t->n) return -1;v = t->nodelisti.children; if (v = = NULL) return_1;return v->nodeposition;返回下标为p的结点的右兄弟结点的下标int rightSibling_chitree(PParTree t, int p) int i;struct EdgeNode * v;if (p < 0 | p >= t->n) return -1;for (i = 0; i < t->n; i+)v = t->nodelisti

46、.children; while (v != NULL)if (v->nodeposition = = p) if(v->link = = NULL) return -1;elsereturn v->link->nodeposition;/*没有下标为p的结点*/*for循环每次检查结点下标中一个元素*/*每次循环检查结点i的边表中的一个元素*/*没有右兄弟结点*/*返回右兄弟结点在结点表中的位置*/elsev=v->link;return 4;/*没有右兄弟结点*/代价分析这是一个两重循环程序，外层循环最多执行n次，内层循环对每个结点的子结点进行检查,子结点的个数最大可能与 n接近，所以表面看来这是一个n2阶的时间代价；但是，仔细分析内层的循环体，可以看出内层循环最多对树中的每条边执行一次，由于树中边的个数与