1、耿国华数据结构c语言的描述课后大部分习题答案 第一章 三、计算下列程序段中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
2、= P; 2.4 已知线性表L 递增有序。试写一算法，将 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 为
3、中心： 以应移入位置j 为中心，计算待移动元素下标： 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）pr
4、e next = s; 2.7 试分别以不同的存储结构实现线性表的就地逆置算法，即在原表的存储空间将线性表（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 表的）结点空间
5、存放表 C. 提示：参P.28 例2-1 void 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
6、 = smaller; while ( pa!=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 假设有一个循环链表的长
7、度大于 1，且表中既无头结点也无头指针。已知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 )
8、当mn时；或者 C= (a , b ,a , 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
10、和 135426 的出站序列，并说明原因。（即 写出以“S”表示进栈、以“X”表示出栈的栈操作序列）。 SXSS XSSX XXSX 或 S1X1S2S3X3S4S5X5X4X2S6X6 2. 设队列中有A、B、C、D、E 这 5 个元素，其中队首元素为A 。如果对这个队列重复执行下列4 步操作： （1） 输出队首元素； （2 ） 把队首元素值插入到队尾； （3） 删除队首元素； （4 ） 再次删除队首元素。 直到队列成为空队列为止，则是否可能得到输出序列： （1） A、C、E、C、C （2） A、C、E （3） A、C、E、C、C、C （4 ） A、C、E、C 提示： A、B、C、D、E （
11、输出队首元素A ） A、B、C、D、E、A （把队首元素A 插入到队尾） B、C、D、E、A （删除队首元素A ） C、D、E、A （再次删除队首元素B） C、D、E、A （输出队首元素C） C、D、E、A、C （把队首元素C 插入到队尾） D、E、A、C （删除队首元素C） E、A、C （再次删除队首元素D ） 3. 给出栈的两种存储结构形式名称，在这两种栈的存储结构中如何判别栈空与栈满？ 4. 按照四则运算加、减、乘、除和幂运算（）优先关系的惯例，画出对下列算术表达式求值时操作数栈和运算符栈的变化过程： A B 5. 试写一个算法，判断依次读入的一个以为结束符的字母序列，是否为形如序列1&
12、序列2模式的字符序列。其中序列1 和序列2 中都不含字符&，且序列2 是序列 1的逆序列。例如，a+b&b+a是属该模式的字符序列，而+ & 则不是。 提示： （1） 边读边入栈，直到& （2 ） 边读边出栈边比较，直到 6. 假设表达式由单字母变量和双目四则运算算符构成。试写一个算法，将一个通常书写形式（中缀）且书写正确的表达式转换为逆波兰式（后缀）。 提示： 例： 中缀表达式：a+b 后缀表达式: ab+ 中缀表达式：a+bc 后缀表达式: abc+ 中缀表达式：a+bc-d 后缀表达式: abc+d- 中缀表达式：a+bc-d/e 后缀表达式: abc+de/- 中缀表达式：a+b(c-
13、d)-e/f 后缀表达式: abcd-+ef/- 后缀表达式的计算过程：（简便） 顺序扫描表达式， （1） 如果是操作数，直接入栈； （2 ） 如果是操作符op，则连续退栈两次，得操作数X, Y，计算X op Y，并将结果入栈。 如何将中缀表达式转换为后缀表达式？ 顺序扫描中缀表达式， （1）如果是操作数，直接输出； （2 ）如果是操作符op ，则与栈顶操作符op 比较：如果op op ，则op 入栈；如果op = op ，则脱括号；如果op op ，则输出op ； 7. 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点（注意不设 头指针），试编写相应的队列初始化、入队列和出
14、队列的算法。 提示： 参P.56 P.70 先画图. typedef LinkList CLQueue; int InitQueue(CLQueue * Q) int EnterQueue(CLQueue Q, QueueElementType x) int DeleteQueue(CLQueue Q, QueueElementType *x) 8. 要求循环队列不损失一个空间全部都能得到利用,设置一个标志域tag ,以tag 为0 或 1来区分头尾指针相同时的队列状态的空与满，请编写与此结构相应的入队与出队算法。 提示： 初始状态：front=0, rear=0, tag=0 队空条件：fr
15、ont=rear, tag=0 队满条件：front=rear, tag=1 其它状态：front !=rear, tag=0 （或1、2 ） 入队操作： （入队） if (front=rear) tag=1；（或直接tag=1 ） 出队操作： （出队） tag=0； 问题：如何明确区分队空、队满、非空非满三种情况？ 9. 简述以下算法的功能（其中栈和队列的元素类型均为int）： （1）void proc_1(Stack S) int i, n, A255; n=0; while(!EmptyStack(S) n+; Pop(&S, &An); for(i=1; i=n; i+) Push(&
16、S, Ai); 将栈 S 逆序。 （2 ）void proc_2(Stack S, int e) Stack T; int d; InitStack(&T); while(!EmptyStack(S) Pop(&S, &d); if (d!=e) Push( &T, d); while(!EmptyStack(T) Pop(&T, &d); Push( &S, d); 删除栈 S 中所有等于e 的元素。 （3）void proc_3(Queue *Q) Stack S; int d; InitStack(&S); while(!EmptyQueue(*Q) DeleteQueue(Q, &d)
17、; Push( &S, d); while(!EmptyStack(S) Pop(&S, &d); EnterQueue(Q，d) 将队列 Q 逆序。 第四章 1. 设s=I AM A STUDENT, t=GOOD, q=WORKER。给出下列操作的结果： StrLength(s); SubString(sub1,s,1,7); SubString(sub2,s,7,1); StrIndex(s,A,4); StrReplace(s,STUDENT,q); StrCat(StrCat(sub1,t), StrCat(sub2,q); 参考答案 StrLength(s)=14; sub1= I
18、 AM A_; sub2= _; StrIndex(s,A,4)=6; StrReplace(s,STUDENT,q)= I AM A WORKER; StrCat(StrCat(sub1,t), StrCat(sub2,q)= I AM A GOOD WORKER; 2. 编写算法，实现串的基本操作 StrReplace(S,T,V)。 3. 假设以块链结构表示串，块的大小为 1，且附设头结点。 试编写算法，实现串的下列基本操作： StrAsign(S,chars) ； StrCopy(S,T) ； StrCompare(S,T) ； StrLength(S) ； StrCat(S,T) ；
19、 SubString(Sub,S,pos,len)。 说明：用单链表实现。 4叙述以下每对术语的区别：空串和空格串；串变量和串常量；主串和子串；串变量的名字和串变量的值。 5已知：S=”(xyz)*”,T=”(x+z)*y”。试利用联接、求子串和置换等操作，将 S 转换为T. 6S 和T 是用结点大小为 1 的单链表存储的两个串，设计一个算法将串S 中首次与T匹配的子串逆置。 7S 是用结点大小为4 的单链表存储的串,分别编写算法在第k 个字符后插入串T，及从第k 个字符删除len 个字符。 以下算法用定长顺序串： 8写下列算法： （1） 将顺序串r 中所有值为ch1 的字符换成ch2 的字符
20、。 （2 ）将顺序串r 中所有字符按照相反的次序仍存放在r 中。 （3） 从顺序串r 中删除其值等于ch 的所有字符。 （4 ） 从顺序串r1 中第index个字符起求出首次与串r2 相同的子串的起始位置。 （5） 从顺序串r 中删除所有与串r1 相同的子串。 9写一个函数将顺序串s1 中的第i 个字符到第j 个字符之间的字符用 s2 串替换。 提示：（1）用静态顺序串 （2 ）先移位，后复制 10 写算法，实现顺序串的基本操作 StrCompare(s,t)。 11 写算法，实现顺序串的基本操作 StrReplace(&s,t,v)。 提示： （1） 被替换子串定位（相当于第9 题中i） （
21、2 ） 被替换子串后面的字符左移或右移（为替换子串准备房间） （3） 替换子串入住（复制） （4 ） 重复上述，直到 第五章 1假设有 6 行 8 列的二维数组A，每个元素占用6 个字节，存储器按字节编址。已知A 的基地址为 1000，计算： （1） 数组A 共占用多少字节； （288 ） （2 ） 数组A 的最后一个元素的地址； （1282） （3） 按行存储时，元素A36 的地址； （1126） （4 ） 按列存储时，元素A36 的地址； （1192） 注意：本章自定义数组的下标从1 开始。 2 设有三对角矩阵（a）,将其三条对角线上的元素逐行地存于数组B(1:3n-2)中，使得 ij n
22、n Bk= aij ，求： （1） 用i,j 表示k 的下标变换公式； （2 ） 用k 表示i,j 的下标变换公式。 i = k/3 + 1, j = k%3 + i - 1 = k%3 + k/3 或： i = k/3 + 1, j = k - 2 ( k/3 ) 2假设稀疏矩阵 A 和 B 均以三元组表作为存储结构。试写出矩阵相加的算法，另设三元 组表C 存放结果矩阵。 提示：参考P.28 例、P.47 例。 4在稀疏矩阵的快速转置算法5.2 中，将计算positioncol的方法稍加改动，使算法 只占用一个辅助向量空间。 5写一个在十字链表中删除非零元素aij 的算法。 提示：“删除”两
23、次，释放一次。 6画出下面广义表的两种存储结构图示： (a), b), ( ), d), (e, f) 7求下列广义表运算的结果： （1） HEAD(a,b),(c,d); （2 ） TAIL(a,b),(c,d); （3） TAILHEAD(a,b),(c,d); （4 ） HEADTAILHEAD(a,b),(c,d); b （5） TAILHEADTAIL(a,b),(c,d); (d) 第六章 1试分别画出具有3 个结点的树和 3 个结点的二叉树的所有不同形态。 2对题1 所得各种形态的二叉树，分别写出前序、中序和后序遍历的序列。 3已知一棵度为k的树中有n 个度为 1 的结点，n 个
24、度为2 的结点，n 个度为k的结点，则该树中有多少个叶子结点？ 提示：参考 P.116 性质3 n=n + n + + n B=n + 2n + 3n + + kn n= B + 1 n + n + + n = n + 2n + 3n + + kn + 1 n = n + 2n + + (k-1)n + 1 4.假设一棵二叉树的先序序列为EBADCFHGIKJ，中序序列为ABCDEFGHIJK，请画出该二 叉树。 提示：参考 P.148 6 已知二叉树有50 个叶子结点，则该二叉树的总结点数至少应有多少个？ 提示：一个叶子结点，总结点数至多有多少个？可压缩一度结点。 7 给出满足下列条件的所有二叉树： a) 前序和中序相同 b) 中序和后序相同 c) 前序和后序相同 提示：去异存同。 a) D L R 与L D R 的相同点：D R，如果无 L，则完全相同, 如果无 LR，。 b) L D R 与L R D 的相同点：L D，如果无 R，则完全相同。 c) D L R 与L R D 的相同点：D，如果无 L R，则完全相同。 （如果去D，则为空树） 7 n 个结点的K
