《耿国华数据结构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
