《西南交通大学数据结构习题解答》由会员分享，可在线阅读，更多相关《西南交通大学数据结构习题解答（25页珍藏版）》请在金锄头文库上搜索。
1、西南交通大学信息科学与技术学院软件工程系-赵宏宇数据结构A 习题讲评1-1习题讲评11. 课程概述-部分习题 2. 线性表-部分习题 3. 栈与队列-部分习题 4.字符串-部分习题 5. 数组与广义表-部分习题西南交通大学信息科学与技术学院软件工程系-赵宏宇数据结构A 习题讲评1-21. 课程概述-部分习题习题集1.8 分析标注语句执行频度 (5) for(i=1; ij) j+; else i+; 解：每循环1次，i+j的值只增加1；第1次循环开始， i+j值为1，最后1次循环开始，i+j值为n，故执行次 数为n。(7) x=n; y=0; while(x=(y+1)*(y+1) y+; 解
2、：令m=y+1，则第1次循环开始，m=1；最后一次循环开始， ， 每循环1次，m值增1，故执行次数为 。西南交通大学信息科学与技术学院软件工程系-赵宏宇数据结构A 习题讲评1-41. 课程概述-部分习题续2习题集1.9 分析时间复杂度及变量count的值 int Time(int n) /* 已知n2 */ count=0; x=2;while(xnext;while(p q=pr;while(p delete pr; q-next=p; 西南交通大学信息科学与技术学院软件工程系-赵宏宇数据结构A 习题讲评1-72. 线性表-部分习题续1习题集2.22 单链表就地逆置。 算法提要：断开头结点，
3、其余结点前插法重构链表。 void reverse(LinkList h) /h为附加头结点地址 p=h-next; /p指向第1数据结点h-next=NULL; /断开头结点while(p) /前插法重构链表 q=p; p=p-next; /结点*q插入至头结点后面q-next=h-next; h-next=q; 西南交通大学信息科学与技术学院软件工程系-赵宏宇数据结构A 习题讲评1-82. 线性表-部分习题续2习题集2.29, 2.30 已知A, B, C三个线性表元素递增有 序。删除A表中即包含于B又包含于C中的元素。 /2.29 用顺序表求解 void f(LinearList ib=
4、ic=0;for(r=0; r0西南交通大学信息科学与技术学院软件工程系-赵宏宇数据结构A 习题讲评1-92. 线性表-部分习题续3if(!isDel) A.dataw+=x; /2.29 用单链表求解 void f(LinkList ha, LinkList hb, LinkList hc) par=ha; pa=ha-next; pbr=hb; pb=hb-next;pcr=hc; pc=hc-next;while(pa) x=pa-data;while(pb 西南交通大学信息科学与技术学院软件工程系-赵宏宇数据结构A 习题讲评1-102. 线性表-部分习题续4完if(pbr!=hb if
5、(pcr!=hdelete pa; pa=par; /why?par=pa;pa=pa-next; /end of while /end of function 时间复杂度：最坏为O(A.length+B.length+C.length)最好为O(A.length)西南交通大学信息科学与技术学院软件工程系-赵宏宇数据结构A 习题讲评1-113. 栈与队列-部分习题习题集3.4 试说明以下算法的功能。 (1) Status algo1(Stack S) int i, n, A255;n=0;while(!StackEmpty(S) n+; Pop(S, An); for(i=1; i0) k=k
6、/2; Push(S, k); r=1; /r=F(0)while(!StackEmpty(S) Pop(S, k); r=k*r; /=左边r为F(k), =右边r为F(k/2)return n*r; F1(n)空间复杂度为O(n/2); F2(n)空间复杂度为O(log2n).西南交通大学信息科学与技术学院软件工程系-赵宏宇数据结构A 习题讲评1-164. 字符串-部分习题习题集4.7 写出子串的next和nextval数组元素值。nextvalnext下标:s=“aaab“-1 -1 -12-10120123nextvalnext下标:-100-1-10000123t=“abcabaa“
7、 112 0 02465西南交通大学信息科学与技术学院软件工程系-赵宏宇数据结构A 习题讲评1-174. 字符串-部分习题续1nextvalnext下标:u=“abcaabbabcabaacbacba“-1 0001120123421100100-1 00 -1 102 -1 00 -1 42110 -1 10 -10123456789 10 11 12 13 14 15 16 17 18 19习题集4.11 编写算法求得所有包含在串s中而不包含在 串t中的字符(s中重复字符只取1个)构成的新串r，以及 r中每个字符在s中第1次出现的位置。 解：int locate(char *s, char
8、 ch) for(i=0; si; i+) if(si=ch) return i;return -1; 西南交通大学信息科学与技术学院软件工程系-赵宏宇数据结构A 习题讲评1-18int f(char *s, char *t, char *r, int p) /* 算法假定r所指空间和p数组空间均大于串s长度;函数返回值为串r的长度。*/ j=0; rj=0; /令串r为空串, j为串r的长度for(i=0; si; i+)if(locate(t, si)=-1 posj=i;r+j=0; return j; 4. 字符串-部分习题续2完西南交通大学信息科学与技术学院软件工程系-赵宏宇数据结构
9、A 习题讲评1-195. 数组和广义表-部分习题习题集5.5 设有上三角矩阵(aij)nn，将其上三角元素逐 行存于数组Bm中(m充分大)，使得Bk=aij且 k=f1(i)+f2(j)+c，试推导出函数f1, f2以及常数c(f1, f2不含 常数)。 解：设数组下标和矩阵下标均从0开始，则矩阵i行之 前共存储了i行元素(行号0i-1)，前i行共有元素故 ， 。又因为上三角ji ，西南交通大学信息科学与技术学院软件工程系-赵宏宇数据结构A 习题讲评1-205. 数组和广义表-部分习题若数组下标和矩阵下标均从1开始，则矩阵i行之前共 存储了i-1行元素(行号1i-1)，前i-1行共有元素故 ，
10、 续1习题集5.7 设有三对角矩阵(aij)nn，将其三条对角线上 的元素逐行存于数组B3n-2中，使得Bk=aij，求： (1) 用i, j表示k的下标变换； (2) 用k表示i, j的下标变换。西南交通大学信息科学与技术学院软件工程系-赵宏宇数据结构A 习题讲评1-215. 数组和广义表-部分习题续2解：设矩阵及数组下标均从0开始，则三对角矩阵如 下所示。 显然，元素总数=3n-2。其中 ，第0行和第n-1行各有2个元 素，其余各行有3个元素。(1) 已知i, j求k 当i=0时，k=j; 当1in-2时，第i行之前的i行共有元素3i-1个，第i行 元素起始列号为i-1, 故其行内元素偏移
11、量为j-(i-1)，因 此，k=3i-1+j-(i-1)=2i+j;西南交通大学信息科学与技术学院软件工程系-赵宏宇数据结构A 习题讲评1-22当i=n-1时，前面n-1行共有元素3(n-1)-1=3n-4个，第n-1 行列下标起始值为n-2，故n-1行的行内元素偏移量为j- (n-2)，因此，k=3n-4+j-(n-2)=2n+j-2; 综上所述，5. 数组和广义表-部分习题续3(2) 已知k求i, j k1, i=0, j=k; 2k3n-5, i=(k-2) div 3+1, j=k-2i; k3n-4, i=n-1, j=k-2n+2 。证明：当2k3n-5， i=(k-2) div
12、3+1。 由(1)得k=3i-1+j-(i-1)， 其中，0j-(i-1)3，于是 有k-2=3i-3+j-(i-1)，即 k-2=3(i-1)+j-(i-1)，必有 i-1=(k-2) div 3，证毕。西南交通大学信息科学与技术学院软件工程系-赵宏宇数据结构A 习题讲评1-23补充题： 某下半三角矩阵(aij)nn采用一维数组b按行顺序存 储。若矩阵及数组下标从0开始，设一维数组元素 bk=aij，试由k求i, j。 解：下半三角第i行之前存储的i行元素数目为5. 数组和广义表-部分习题续4第i行行内元素偏移量为j，故因为下半三角，必有0ji，有(1)西南交通大学信息科学与技术学院软件工程系-赵宏宇数据结构A 习题讲评1-245. 数组和广义表-部分习题续5由得 由得(2)(3)由(2)可得，由(3)可得即令可证明，有西南交通大学信息科学与技术学院软件工程系-赵宏宇数据结构A 习题讲评1-255. 数组和广义表-部分习题续6完由i是非负整数，知例如：a0, 0a1, 0 a1, 1a2, 0 a2, 1 a2, 2a3, 0 a3, 1 a3, 2 a3, 3a4, 0 a4, 1 a4, 2 a4, 3 a4, 4 若k=12，由(4)得(4)将i=4代入(1)，得 j=k-i(i+1)/2=2
