算法与数据结构C语言习题参考答案章.docx

1、算法与数据结构C语言习题参考答案章1.绪 论1将下列复杂度由小到大重新排序：A2n Bn! Cn5 D10 000 En*log2 (n)【答】10 000 n*log2(n) n5 2n n! 2将下列复杂度由小到大重新排序：An*log2(n) Bn + n2 + n3 C24 Dn0.5【答】24 n0.5 n*log2 (n) n + n2 + n33用大“O”表示法描述下列复杂度：A5n5/2 + n2/5 B6*log2(n) + 9nC3n4+ n* log2(n) D5n2 + n3/2【答】A：O (n5/2) B：O (n) C：O (n4) D：O (n2)4按照增长率从

2、低到高的顺序排列以下表达式：4n2 , log3n, 3n , 20n , 2000 , log2n , n2/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次，循环体中第一句printf执行n次，第二句i从1循环到n，共执行n次。所以该程

3、序段总的时间代价为：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(kn = palist- MAXNUM ) /* 溢出 */ printf(“Overflow!n”); return 0; if (ppalist-n-1 ) /* 不存在下标为p的元素 */printf(“Not exist! n”); return 0; for(q=palist-n - 1; q=p+1; q-) /* 插入位置及之后的元素均后移一个位置 */ pali

4、st-elementq+1 = palist-elementq;palist-elementp+1 = x; /* 插入元素x */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;pele

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

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

7、 ( i = 0; i elementi;palist-elementi = palist-elementpalist-n - 1 - i;palist-elementpalist-n - 1 - i = x;代价分析该算法中包含一个for循环，其循环次数为n/2。因此，算法的时间代价为O(n)。4. 已知长度为n的线性表A采用顺序存储结构，请写一算法，找出该线性表中值最小的数据元素。【答】数据结构采用2.1.2节中顺序表定义。思路设置变量min，遍历整个表，不断更新当前已经经历过的元素的最小值即可。为方便起见，事先假设表不为空。算法DataType min_seq(PSeqList pali

8、st) /*求非空顺序表中的最小数据元素*/DataType min;int i;min = palist-element0; /*初始化min*/for ( i = 1; i n; i+) /*min中保存的总是当前的最小数据*/if (min palist-elementi)min = palist-elementi;return min;代价分析该算法访问顺序表中每个元素各一次，时间代价为O(n)。 讨论读者可以试图对上面的算法进行修改，使返回的值不是最小元素的值而是它的下标。5. 已知线性表A的长度为n，并且采用顺序存储结构。写一算法，删除线性表中所有值为x的元素。【答】数据结构采用2

9、.1.2节中顺序表的定义。思路为了减少移动次数，可以采用快速检索的思想，用两个变量i, j记录顺序表中被处理的两端元素的下标，开始时i = 0，j = n-1，边检索第i个元素边增加i，直到找到一个元素值等于x，再边检索第j个元素边减少j，直到找到一个元素值不等于x，把下标为j的元素移到下标为i的位置后重复上述过程，直到i j。另用一变量count记录删除了多少个元素。算法void delx_seq(PSeqList p, DataType x)/*删除顺序表中所有值为x的元素，新顺序表可能不保持原有顺序*/int i = 0, j = p-n - 1, count = 0; /*i定位于顺序

10、表开始处，j定位于顺序表最后*/while ( i elementi = x) /*找到了一个要删除的元素*/while (p-elementj = x) & (i != j) /*从后往前找不会被删除的元素，当i, j相等时退出循环，count记录从后往前找的过程中遇到了多少个要删的元素*/j- -;count+;if ( i = = j) p-n = p-n - count - 1;return;elsep-elementi = p-elementj;count+;j- -;i+;p-n = p-n - count;if (p-elementi = x) p-n- -;代价分析该算法访问顺

11、序表中每个元素各一次，时间代价为O (n)。 讨论这个算法使用了一点技巧使得在中间删除元素时，避免了最后一串元素的移动。但是，它破坏了原来线性表中元素之间的顺序关系。如果需要保持原来的顺序应该怎样做？这里提供一种可行的思路：从前向后遍历表，如果元素不是x，则继续向后；如果元素是x，则寻找其后第一个不是x的元素，将这两个元素互换。具体算法请读者自己实现。6.写一算法，在带头结点的单链表llist中，p所指结点前面插入值为的新结点，并返回插入成功与否的标志。【答】数据结构采用2.1.3节中单链表定义。思想：由于在单链表中，只有指向后继结点的指针，所以只有首先找到p所指结点的前驱结点，然后才能完成插

12、入。而找p所指结点的前驱结点，只能从单链表的第一个结点开始，使用与locate_link 类似的方式进行搜索。算法：int insertPre_link(LinkList llist,PNode p,DataType x) /* 在llist带头结点的单链表中，p所指结点前面插入值为x的新结点 */ PNode p1; if(llist=NULL) return 0; p1=llist; while(p1!=NULL&p1-link!=p)p1=p1-link; /*寻找p所指结点的前驱结点*/ if(p1=NULL) return 0; PNode q=(PNode)malloc(sizeo

13、f(struct Node);/*申请新结点*/ if(q=NULL) printf(“Out of space!n”);return 0; q-info=x; q-link=p1-link; p1-link=q; return 1; 7.写一算法，在带头结点的单链表llist中,删除p所指的结点，并返回删除成功与否的标志。【答】数据结构采用2.1.3节中单链表定义。思想：由于在单链表中，只有指向后继结点的指针，所以只有首先找到p所指结点的前驱结点，然后才能完成删除。而找p所指结点的前驱结点，只能从单链表的第一个结点开始，使用与locate_link 类似的方式进行搜索。int deleteP

14、_link(LinkList llist,PNode p)/* 在llist带头结点的单链表中，删除p所指的结点 */PNode 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节中单链表定义。思路

15、依次遍历表中的每一个结点并计数，到第i+1个结点时实行删除。由于链表是无头结点的，所以在删除第一个结点时要特别注意。算法int deleteindex_link_nohead(LinkList * pllist, int i) /*删除单链表中下标为i的结点。删除成功返回TRUE，否则返回FALSE。*/int j;PNode p, q;if (*pllist) = NULL | i link;free(q);return TRUE;p = (*pllist);j = 0;while (p-link != NULL & j link;j+;if (p-link = NULL) return F

16、ALSE; /*此元素不存在*/q = p-link;p-link = q-link;free(q);return TRUE;代价分析该算法访问单链表中前面i个结点，时间代价为O(i)，最大不超过O(n)。 讨论如果函数参数不是LinkList *类型而是LinkList类型，在删除i=0的结点时，程序不能正确实现，其原因请读者思考（考虑C语言的参数传递方式）。如果单链表带表头结点，重写本题的算法。比较这两个算法，是否能体会到表头结点的作用。9. 已知list是指向无头结点的单链表的指针变量，写出删除该链表中从下标为i的（第i+1个）结点开始的连续k个结点的算法。【答】数据结构采用2.1.3节

17、单链表定义。思路这道题与上题相似，只需要增加计数即可。要注意的是应该判断给出的i和k是否合理，是不是会超出链表长度。算法int del_link_nohead(LinkList * pllist, int i, int k) /*删除单链表中从下标i开始的k个结点。删除成功返回TRUE，否则返回FALSE。*/int j;PNode p, q;if (*pllist) = NULL | i 0 | k = 0) return FALSE;if ( i = = 0) /*如果需要删除从第一个结点开始的k个结点*/for ( j = 0; j link;free(q);return TRUE;p

18、= (*pllist);j = 0;while ( p-link != NULL & j link;j+;if (p-link = NULL) return FALSE; /*第i个结点不存在*/for ( j = 0; j link != NULL; j+) q = p-link;p-link = q-link;free(q);return TRUE;代价分析该算法访问单链表中前面i+k个结点，时间代价为O(i+k)，最大不超过O(n)。13. 请设计一个算法，求出循环表中结点的个数。【答】数据结构采用不带头结点的循环链表。struct Node;typedef struct Node *

19、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; count+;return count;错误：如果clist是一个空表，那么第5行的语句“q = p-link;”是非法的

20、。分析：应把第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 = clist-link;count = 1;while ( q != clist)q = q-link;count+;return count;代价分析该算法访问循环链表中每个结点

21、各一次，时间代价为O(n)。4. 栈与队列1. 写一个递归算法来把整数字符串转换为整数。（例：“43567” 43567。）【答】思路先递归调用本算法转换除去末位外剩余的字符串，结果乘以10。再转换末位。将两结果相加即为所求。算法int stringToInt1(char * s, int start, int end) /*把整数字符串s中从start到end的部分转换为整数*/ if (start end) return -1; /*转换失败*/ if (start = end) return send - 0; /*只有一个字符，直接转换*/ return stringToInt1(s,

22、 start, end - 1) * 10 + send - 0; /*先转换其他位，再转换末位*/int stringToInt(char * s) /*把整数字符串s转换为整数*/ int i = 0; while (si != 0) i+; /*计算字符串的长度*/ return stringToInt1(s, 0, i - 1);代价分析设n为字符串的长度。该算法访问每个字符各一次，时间代价为O(n)，计算字符串的长度的时间代价也为O(n)。故总的时间代价为O(n)。递归算法需要栈的支持，栈的大小与递归调用的深度成正比。所以实际空间开销为O(n)。2. 编写一个算法，对于输入的十进制非

23、负整数，将它的二进制表示打印出来。【答】数据结构采用4.1.2节中栈的顺序表示。思路将输入的十进制数字反复除以2，直到它变为0。将每次的数字模2的余数入栈。栈中存放的就是所要求的二进制表示。再将栈中的元素依次弹出打印即可。算法void print_bin(int dec_number) /*将十进制非负整数转化为二进制数打印出来*/PSeqStack pastack;int temp = dec_number;if (temp 0) push_seq(pastack, temp % 2); temp /= 2;while(!isEmptyStack_seq(pastack) printf(%d

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

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