算法与数据结构C语言习题参考答案15章.docx
《算法与数据结构C语言习题参考答案15章.docx》由会员分享,可在线阅读,更多相关《算法与数据结构C语言习题参考答案15章.docx(26页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、1. 绪 论1将以下困难度由小到大重新排序:A2nBn!Cn5D10 000En*2 (n)【答】10 000 n*2(n) n5 2n n! 2将以下困难度由小到大重新排序:An*2(n)Bn + n2 + n3C24Dn【答】24 n n*2 (n) n + n2 + n33用大“O表示法描述以下困难度:A5n5/2 + n2/5B6*2(n) + 9nC3n4+ n* 2(n)D5n2 + n3/2【答】A:O (n5/2)B:O (n)C:O (n4)D:O (n2)4依据增长率从低到高的依次排列以下表达式:4n2 , 3n, 3n , 20n , 2000 , 2n , n2/3。又
2、n!应排在第几位?【答】依据增长率从低到高依次为:2000, 3n, 2n , n2/3 , 20n , 4n2 , 3n。n!的增长率比它们中的每一个都要大,应排在最终一位。5. 计算以下程序片断的时间代价: 1;(i)(“n);1;【答】循环限制变量i从1增加到n,循环体执行n次,第一句i的初始化执行次数为1,第二句执行n次,循环体中第一句执行n次,第二句i从1循环到n,共执行n次。所以该程序段总的时间代价为:T(n) = 1 + n + 2n = 3 1 = O(n)6. 计算以下程序片断的时间代价: 1;(i) 1;(j) 1;(kn = ) /* 溢出 */ (“!n); 0; (p
3、1 ) /* 不存在下标为p的元素 */(“ ! n); 0; (n - 1; q1; ) /* 插入位置及之后的元素均后移一个位置 */ 1 = q;1 = x;/* 插入元素x */n = n + 1;/* 元素个数加1 */ 1;2试写一个删除算法(, x ),在所指依次表中,删除一个值为x的元素,返回删除胜利及否的标记。【答】数据构造采纳2.1.2节中依次表定义。 ( , p, x ) /* 在所指依次表中删除值为x的元素 */ ;(0p) (; q1; ) /* 被删除元素之后的元素均前移一个位置 */ q = 1; n = n - 1;/* 元素个数减1 */ 1 ; 0;3. 设
4、有一线性表e = (e0, e1 , e2 , , -1 ),其逆线性表定义为e= (-1 , , e2 , e1 0)。请设计一个算法,将用依次表表示的线性表置逆,要求逆线性表仍占用原线性表的空间。【答】数据构造采纳节中依次表的定义。思路考虑对数组 进展置逆,即把第一个元素和最终一个元素换位置,把第二个元素和倒数第二个元素换位置。A 留意这种调换的工作只需对数组的前一半元素进展,所以设置整数变量用于存放数组长度的一半的值。大家可以考虑一下:为什么不能对整个数组进展如上的对元素“换位置的工作?提示:这样会将原来已经置逆的线性表又置逆回来,即又变成了原来的表。依次表的置逆算法 ( ) x; ,
5、i; (n 0 n 1) ;/*空表或只有一个元素,干脆返回*/ = n / 2; ( i = 0; i i;i = n - 1 - i;n - 1 - i = x;代价分析该算法中包含一个循环,其循环次数为2。因此,算法的时间代价为O(n)。4. 长度为n的线性表A采纳依次存储构造,请写一算法,找出该线性表中值最小的数据元素。【答】数据构造采纳节中依次表定义。思路设置变量,遍历整个表,不断更新当前已经经验过的元素的最小值即可。为便利起见,事先假设表不为空。算法 ( )/*求非空依次表中的最小数据元素*/ ; i; = 0; /*初始化*/ ( i = 1; i n; ) /*中保存的总是当前
6、的最小数据*/ ( i) = i; ;代价分析该算法访问依次表中每个元素各一次,时间代价为O(n)。A 探讨读者可以试图对上面的算法进展修改,使返回的值不是最小元素的值而是它的下标。5. 线性表A的长度为n,并且采纳依次存储构造。写一算法,删除线性表中全部值为x的元素。【答】数据构造采纳节中依次表的定义。思路为了削减移动次数,可以采纳快速检索的思想,用两个变量i, j记录依次表中被处理的两端元素的下标,开场时i = 0,j = n-1,边检索第i个元素边增加i,直到找到一个元素值等于x,再边检索第j个元素边削减j,直到找到一个元素值不等于x,把下标为j的元素移到下标为i的位置后重复上述过程,直
7、到i j。另用一变量记录删除了多少个元素。算法 ( p, x)/*删除依次表中全部值为x的元素,新依次表可能不保持原有依次*/ i = 0, j = n - 1, = 0;/*i定位于依次表开场处,j定位于依次表最终*/ ( i i x) /*找到了一个要删除的元素*/ (j x) (i j) /*从后往前找不会被删除的元素,当i, j相等时退出循环,记录从后往前找的过程中遇到了多少个要删的元素*/j- -; ( i = = j) n = n - - 1;i = j;j- -;n = n - ; (i x) p-n- -;代价分析该算法访问依次表中每个元素各一次,时间代价为O (n)。A 探讨
8、这个算法运用了一点技巧使得在中间删除元素时,防止了最终一串元素的移动。但是,它破坏了原来线性表中元素之间的依次关系。假如须要保持原来的依次应当怎样做?这里供应一种可行的思路:从前向后遍历表,假如元素不是x,那么接着向后;假如元素是x,那么找寻其后第一个不是x的元素,将这两个元素互换。详细算法请读者自己实现。6.写一算法,在带头结点的单链表中,p所指结点前面插入值为的新结点,并返回插入胜利及否的标记。【答】数据构造采纳2.1.3节中单链表定义。思想:由于在单链表中,只有指向后继结点的指针,所以只有首先找到p所指结点的前驱结点,然后才能完成插入。而找p所指结点的前驱结点,只能从单链表的第一个结点开
9、场,运用及 类似的方式进展搜寻。算法: ( x) /* 在带头结点的单链表中,p所指结点前面插入值为x的新结点 */ p1; () 0; p1; (p11-)p11-; /*找寻p所指结点的前驱结点*/ (p1) 0; ()( )*申请新结点*/ () (“ !n) 0; ; 1-; p1-; 1; 7.写一算法,在带头结点的单链表中,删除p所指的结点,并返回删除胜利及否的标记。【答】数据构造采纳2.1.3节中单链表定义。思想:由于在单链表中,只有指向后继结点的指针,所以只有首先找到p所指结点的前驱结点,然后才能完成删除。而找p所指结点的前驱结点,只能从单链表的第一个结点开场,运用及 类似的方
10、式进展搜寻。 ( p)/* 在带头结点的单链表中,删除p所指的结点 */ p1;() ; p1;(p11-)p11-; /*找寻p所指结点的前驱结点*/(p1) 0; p1-; (p); /* 删除结点p */ 1;8. 是指向无头结点的单链表的指针变量,写出删除该链表下标为i的第1个结点的算法。【答】数据构造采纳节中单链表定义。思路依次遍历表中的每一个结点并计数,到第1个结点时实行删除。由于链表是无头结点的,所以在删除第一个结点时要特殊留意。算法 ( * , i) /*删除单链表中下标为i的结点。删除胜利返回,否那么返回。*/ j; p, q; (*) i ;(q); ;p = (*);j
11、= 0; ( j ; ( ) ;/*此元素不存在*/q = ; = ;(q); ;代价分析该算法访问单链表中前面i个结点,时间代价为O(i),最大不超过O(n)。A 探讨假如函数参数不是 *类型而是类型,在删除0的结点时,程序不能正的确现,其缘由请读者思索考虑C语言的参数传递方式。假如单链表带表头结点,重写此题的算法。比拟这两个算法,是否能体会到表头结点的作用。9. 是指向无头结点的单链表的指针变量,写出删除该链表中从下标为i的第1个结点开场的连续k个结点的算法。【答】数据构造采纳节单链表定义。思路这道题及上题相像,只须要增加计数即可。要留意的是应当推断给出的i和k是否合理,是不是会超出链表长
12、度。算法 ( * , i, k) /*删除单链表中从下标i开场的k个结点。删除胜利返回,否那么返回。*/ j; p, q; (*) i 0 k = 0) ; ( i = = 0) /*假如须要删除从第一个结点开场的k个结点*/ ( j = 0; j ;(q); ;p = (*);j = 0; ( j ; ( ) ;/*第i个结点不存在*/ ( j = 0; j ; ) q = ; = ;(q); ;代价分析该算法访问单链表中前面个结点,时间代价为O(),最大不超过O(n)。13. 请设计一个算法,求出循环表中结点的个数。【答】数据构造采纳不带头结点的循环链表。 ; * ; ; ; * ;思路遍
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 算法 数据结构 语言 习题 参考答案 15
限制150内