《数据结构(c语言版)清华大学出版社 课后题1-5章答案.doc》由会员分享，可在线阅读，更多相关《数据结构(c语言版)清华大学出版社 课后题1-5章答案.doc（8页珍藏版）》请在金锄头文库上搜索。
1、第一章选择题 1.A 2.B 3.C 4.D 5.B 6.C第二章选择题 1.A 2.D 3.D 4.C 5.A 6.C 7.B 8.B 9.D 10.D应用题1应该选用链接存储表示。如果才用顺序表示法，必须在一个连续的可用空间中为这N个表分配空间。初始时候因为不知道哪个表增长得快，必须平均分配空间。在程序运行过程中，有的表占用的空间增长得快，有的表占用空间增长得慢，有的表很快就使用完了分配给它的空间，有的表才占用了少许空间，在进行元素的插入时候就必须成片的移动其他表的空间，以空出位置进行插入；在元素删除时为填补空白，也可能移动许多元素。这个处理过程及其繁琐和低效。如果采用链接存储，一个表的空
2、间可以连续也可以不连续。表的增长通过动态分配内存得以解决，只要存储器未满，就不会发生表溢出；表的收缩可以通过动态存储释放实现，释放的空间还可以在以后动态分配给其他的存储需求，非常灵活方便。对于N个表（包括表的总数可能变化）共存的情形，处理十分简单快捷，插入、删除时间复杂度为O（1）。所以才用链接存储表示较好。2一般来说，链式存储结构克服了顺序存储结构的三个缺点。首先，插入、删除操作不需要移动元素，只修改指针；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受到内存空间的限制。其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储的缺点。3.顺序结构时ai与ai+1的
3、物理位置相邻，链表结构时两者的位置不要求一定相邻。7.在顺序表中插入和删除一个节点需平均移动全表一半的节点。具体的移动次数取决于所插入和删除的节点的位置i和全表的长度n这两个因素。算法设计题1. 分析：遍历整个顺序表，用k记录在xy之间元素的个数，k的初始值为0。对于当前遍历到的元素，若其值在xy之间，则前移k个位置；否则执行+k。这样每个不在xy之间的元素仅仅移动一次，所以效率较高。void Delete_xy( SeqList *A,int x,int y )int k;k = 0;for( i=0;ilength;+i )if( A-dataix & A-dataidatai-k = A
4、-datai; /* 当前元素前移k个位置 */A-length = A-length - k; /* 线性表长度减小 */2.设集合A和B分别用两个递增有序的单链表表示，其中他们的头指针是pa和pb。求A交B的操作就是对A扫描，如果当前的扫描到的元素在B中出现则保留，否则删除。LinkList AbingB( LinkList A,LinkList B )LinkList pa,pb,pre;pa = A-next;pb = B-next;pre = A;while( pa&pb )if( pa-datadata )/* 若大于，则pb指针后移 */q = pa;pa = pa-next;p
5、re-next = pa;free(q);else/*相等，保留，pa、pb指针后移*/pre = pa;pa = pa-next;pb = pb-next;while( pa )/* 若单链表没有遍历完，则将剩余节点删除 */q = pa;pa = pa-next;free(q);pre-next = NULL;return (A);本算法的时间开销主要是遍历，故时间复杂度为O(n)3. 分析：依次遍历访问单链表的节点，用冒泡排序的思想将该链表整理成有序。冒泡排序算法的基本思想比较简单：两两比较元素，值域小的元素前置，直到不再发生交换。LinkList Sort_LinkList( Link
6、List L )int x,noswap;LinkList pa,pb;pa = L-next;noswap = 1;if( pa )while( noswap )noswap = 0;pb = pa-next;while( pb&(pb-next!=NULL) )if( pb-datanext-data )x = pb-data;pb-data = pb-next-data;pb-next-data = x;noswap = 1;pb = pb-next;本算法的时间效率是O(n2)，效率相对较低，本题其他高效求解算法可参见第9章中介绍的其他排序算法。另外本题中交换节点才用交换值域，另一种方
7、法是交换指针，这样做比较复杂，读者可以尝试编程解决。第三章选择题 1.C 2.C 3.D 4.C 6.D 7.D 8.D 9.A 10.D 11.D 12.C 13.C应用题 1. 答案无2. 答案无3. 该问题必须可以分解为和该问题具有相同逻辑结构的子问题，即具有递归性质。书写递归程序的要点如下：（1） 问题与自身的子问题具有相同的性质，被定义项在定义中的应用具有更小的尺度。（2） 被定义项在最小尺度上有直接解。递归算法设计的原则是用自身的简单情况来定义自身，一步一步比更简单，确定递归的控制条件非常重要。设计递归算法的方法如下：（1） 寻找方法，将问题化为原问题的子问题求解（ 例如 n! =
8、 n*(n-1)! ）。（2） 设计递归出口，确定递归的终止条件（ 例如求解n!时，当n=1时，n! = 1 ）5. 答案无6. 将队列的数据区域data0.MAXSIZE-1看成头尾相接的循环结构，头尾指针的关系不变，将其称为“循环队列”。具体结构参见第3.1节中对循环队列的数据结构定义。初始状态front=0；rear=0；队空时front=rear；队满时(rear+1)%MAXSIZE=front。9. 链队列队头指向单链表的首节点，而队尾则是指向单链表的最后一个节点。不能够反过来，因为在队尾进行删除删除操作时，需要遍历单链表找到队尾所指向节点的前继，这样处理影响效率。算法设计题1.
9、提示：将字符序列分别输入一个栈和一个队列，然后分别执行出栈和出队操作，并比较输出的字符，如果直到栈空并且队空时，输出的字符都相同，则是回文，否则不是。参考3.2节算法设计题中的第2题。2. 提示：在入队时首先要判断队是否满，在出队时首先要判断队是否为空。所以要正确写出循环队列的队满和队空的条件。在队首指针加1和队尾指针加1时，要做模MAXSIZE运算。4.分析：由于不设置头指针，所以要设法确定队头的位置。由于有队尾指针rear，所以要根据循环链表的结构，队头指针front = rear-next-next。队空时，rear=rear-next。#define DataType inttyped
10、ef struct nodeDataType data; /*每个元素数据信息*/struct node *next;/* 存放后继元素的地址 */LNode,*Quenue;void SetEmpty( Quenue * rear ) /* 置队列为空，队列的尾指反生变化，要用指针的指针；注意，rear前部有星号 */LNode * h,*front;h = (*rear)-next;while( h!=*rear )front = h-next;h-next= front-next;/* 队列中只有一个节点，释放后队列为空，所以让队尾指针指向头结点 */if( front = *rear
11、)*rear = h;free(front); void InQuenue( Quenue * rear,DataType x )/* 数据data入队列，队列的尾指针发生变化，要用指针的指针；注意rear前有*号 */LNode *p; p = (LNode *)malloc(sizeof(LNode); p-data = x; p-next = (*rear)-next;/* 在rear后插入新节点 */ (*rear)-next = p; (*rear) = p;int OutQuenue( Quenue * rear,DataType * x )/* 队列的尾指针可能发生变化，要用指针
12、的指针；注意rear前有*号 */LNode *head ,*front;head = *rear-next;if( head = *rear )/* 队列为空，出队操作失败 */return 0;front = head-next;*x = front-data;head-next = front-next;if( front = *rear )/* 队列中只有一个节点，释放后将为空，所以让队尾指针指向头节点 */*rear = head;free(front);/* 释放队列头结点 */return 1;5.分析：该题目主要考察栈的应用。假定表达式存放在字符串数组str中，对表达式字符进行
13、扫描，遇到做括号则进栈，遇到右括号则判栈是否为空；若为空，说明圆括号不配对；若不空则出栈，最后，若栈为空，说明圆括号配对，否则不配对。算法描述如下：void pair( char str )PSeqStack S;char ch,ch1;int k = 0;S = Init_SeqStack();while( (ch=strk)!=0 )/*扫描表达式*/if( ch = ( ) Push_SeqStack(S,ch);elseif( ch = ) )if( Empty_SeqStack(S,ch) )printf(原括号不匹配);return ;elsePop_SeqStack(S,&ch1);/* 栈顶的左括号出栈 */+k;if( Empty_SeqStack(S) ) printf(圆括号配对);else printf(原括号不配对); 第四章选择题 1.A 2.C 3.C 4. D 5.B 6.C 7.D 8.D应用题1. 空串是指不包含任何字符的串，它的长度为零；空白串是指包含一个或多个空格的串，空格也是字符。字符串的空格可以将各个单词分割。2. 串的存储结构有两种，顺序存储结构和链式存储结构。3. 要比较30次4. 要比较19次算法设计题
