《耿国华数据结构C语言的描述课后大部分习题答案》由会员分享,可在线阅读,更多相关《耿国华数据结构C语言的描述课后大部分习题答案(39页珍藏版)》请在金锄头文库上搜索。
1、 第一章 三、计算下列程序段中X=X+1 的语句频度 for(i=1;i=n;i+) for(j=1;j=i;j+) for(k=1;knext=S; (2 )P-next= P-next-next; (3)P-next= S-next; (4 )S-next= P-next; (5)S-next= L; (6)S-next= NULL; (7)Q= P; (8)while(P-next!=Q) P=P-next; (9)while(P-next!=NULL) P=P-next; (10)P= Q; (11)P= L; (12)L= S; (13)L= P; 2.4 已知线性表L 递增有序。试
2、写一算法,将 X 插入到 L 的适当位置上,以保持线性表L的有序性。 提示:void insert(SeqList *L; ElemType x) (1)找出应插入位置i,(2 )移位,(3) 参P. 229 2.5 写一算法,从顺序表中删除自第i 个元素开始的k 个元素。 提示:注意检查i 和k 的合法性。(集体搬迁,“新房”、“旧房”) 以待移动元素下标m(“旧房号”)为中心,计算应移入位置(“新房号”): for ( m= i 1+k; mlast; m+) L elem mk = Lelem m ; 同时以待移动元素下标m 和应移入位置j 为中心: 以应移入位置j 为中心,计算待移动元
3、素下标: 2.6 已知线性表中的元素(整数)以值递增有序排列,并以单链表作存储结构。试写一高效算法,删除表中所有大于mink 且小于maxk 的元素(若表中存在这样的元素),分析你的算法的时间复杂度(注意:mink 和maxk 是给定的两个参变量,它们的值为任意的整数)。 提示:注意检查mink 和maxk 的合法性:mink next; while (p!=NULL & p data next; (2 )找到最后一个应删结点的后继s,边找边释放应删结点 s=p; while (s!=NULL & sdata next; free(t); (3)pre next = s; 2.7 试分别以不同
4、的存储结构实现线性表的就地逆置算法,即在原表的存储空间将线性表(a1, a ., a )逆置为(a , a ,., a )。 (1) 以一维数组作存储结构,设线性表存于a(1:arrsize)的前elenum 个分量中。 (2 ) 以单链表作存储结构。 方法 1:在原头结点后重新头插一遍 方法2:可设三个同步移动的指针p, q, r,将q 的后继r 改为p 2.8 假设两个按元素值递增有序排列的线性表A 和B,均以单链表作为存储结构,请编写算法,将A 表和B 表归并成一个按元素值递减有序的排列的线性表 C,并要求利用原表(即A 表和B 表的)结点空间存放表 C. 提示:参P.28 例2-1 v
5、oid merge(LinkList A; LinkList B; LinkList *C) pa=A next; pb=Bnext; *C=A; (*C)next=NULL; while ( pa!=NULL & pb!=NULL ) if ( pa data data ) smaller=pa; pa=panext; smallernext = (*C)next; /* 头插法 */ (*C) next = smaller; else smaller=pb; pb=pbnext; smallernext = (*C)next; (*C) next = smaller; while ( pa
6、!=NULL) smaller=pa; pa=panext; smaller next = (*C)next; (*C) next = smaller; while ( pb!=NULL) smaller=pb; pb=pbnext; smaller next = (*C)next; (*C) next = smaller; LinkList merge(LinkList A; LinkList B) LinkList C; pa=A next; pb=Bnext; C=A; Cnext=NULL; return C; 2.9 假设有一个循环链表的长度大于 1,且表中既无头结点也无头指针。已知
7、s为指向链表某个结点的指针,试编写算法在链表中删除指针 s 所指结点的前趋结点。 提示:设指针p 指向 s 结点的前趋的前趋,则p 与s 有何关系? 2.10 已知有单链表表示的线性表中含有三类字符的数据元素(如字母字符、数字字符和其它字符),试编写算法来构造三个以循环链表表示的线性表,使每个表中只含同一类的字符,且利用原表中的结点空间作为这三个表的结点空间,头结点可另辟空间。2.11 设线性表A=(a, a ,a ),B=(b, b ,b ),试写一个按下列规则合并A、B为线性表C的算法,使得: C= (a , b ,a , b , b ,b ) 当mn时;或者 C= (a , b ,a ,
8、 b , a ,a ) 当mn时。线性表 A、B、C 均以单链表作为存储结构,且 C 表利用 A 表和 B 表中的结点空间构成。 注意:单链表的长度值m 和n 均未显式存储。 提示:void merge(LinkList A; LinkList B; LinkList *C) 或:LinkList merge(LinkList A; LinkList B) 2.12 将一个用循环链表表示的稀疏多项式分解成两个多项式,使这两个多项式中各自仅含奇次项或偶次项,并要求利用原链表中的结点空间来构成这两个链表。 提示:注明用头指针还是尾指针。 2.13 建立一个带头结点的线性链表,用以存放输入的二进制数
9、,链表中每个结点的 data 域存放一个二进制位。并在此链表上实现对二进制数加 1 的运算 。 提示:可将低位放在前面。 2.14 设多项式P(x)采用课本中所述链接方法存储。写一算法,对给定的x 值,求P(x)的值。 提示:float PolyValue(Polylist p; float x) 第三章 1. 按图3.1(b)所示铁道(两侧铁道均为单向行驶道)进行车厢调度,回答: 如进站的车厢序列为 123,则可能得到的出站车厢序列是什么? 123、213、132、231、321 (312) 如进站的车厢序列为 123456,能否得到435612 和 135426 的出站序列,并说明原因。(即 写出以“S”表示进栈、以“X”表示出栈的栈操作序列)。 SXSS XSSX XXSX 或 S1X1S2