数据结构与算法分析c语言描述中文答案.pdfVIP

数据结构与算法分析 c 语言描述中文答 案 【篇一：数据结构 (c 语言版 )课后习题答案完整版】 选择题： ccbdca 6 ．试分析下面各程序段的时间复杂度。 （1 ）o （1） （2 ）o （m*n ） （3 ）o （n2 ） （4 ）o （log3n ） （5 ）因为 x++ 共执行了 n-1+n-2+?? ＋ 1= n(n-1)/2 ，所以执行时间 为 o （n2 ） （6 ）o(n) 第 2 章 线性表 1 ．选择题 babadbcabdcddac 2 ．算法设计题 （6 ）设计一个算法，通过一趟遍历在单链表中确定值最大的结点。 elemtype max (linklist l ){ if(l-next==null) return null; pmax=l-next; // 假定第一个结点中数据具有最大值 p=l-next-next; while(p != null ){// 如果下一个结点存在 if(p-data pmax-data) pmax=p;p=p-next; } return pmax-data; （7 ）设计一个算法，通过遍历一趟，将链表中所有结点的链接方向 逆转，仍利用原表的存储空间。 void inverse(linklist l) { // 逆置带头结点的单链表 l p=l-next; l- next=null; while ( p) { q=p-next; // q 指向 *p 的后继 p-next=l-next; l-next=p; // *p 插入在头结点之后 p = q; } } （10 ）已知长度为 n 的线性表 a 采用顺序存储结构，请写一时间复 杂度为 o(n) 、空间复杂度为 o(1) 的算法，该算法删除线性表中所有 值为 item 的数据元素。 [ 题目分析 ] 在顺序存储的线性表上删除元素，通常要涉及到一系列 元素的移动（删第 i 个元素，第 i+1 至第 n 个元素要依次前移）。本 题要求删除线性表中所有值为 item 的数据元素，并未要求元素间的 相对位置不变。因此可以考虑设头尾两个指针（ i=1 ，j=n ），从两端 向中间移动，凡遇到值 item 的数据元素时，直接将右端元素左移至 值为 item 的数据元素位置。 void delete （elemtype a[ ] ，int n ） ∥a 是有 n 个元素的一维数组，本算法删除 a 中所有值为 item 的元 素。 {i=1 ；j=n ；∥设置数组低、高端指针（下标）。 while （ij ） {while （ij a[i]!=item ）i++ ；∥若值不为 item ，左移指针。 if （ij ）while （ij a[j]==item ）j-- ；∥若右端元素值为 item ，指针 左移 if （ij ）a[i++]=a[j--] ； } [ 算法讨论 ] 因元素只扫描一趟，算法时间复杂度为 o （n ）。删除元 素未使用其它辅助空间，最后线性表中的元素个数是 j 。 第 3 章 栈和队列 1 ．选择题 ccdaadabcdddbcb 2. 算法设计题 （2 ）回文是指正读反读均相同的 字符序列，如 “abba”和 “