《数据结构(马睿、孙丽云)习题答案》由会员分享，可在线阅读，更多相关《数据结构(马睿、孙丽云)习题答案（27页珍藏版）》请在金锄头文库上搜索。
1、 第1章 绪论一、选择题1、C 2、C 3、C 4、D 5、B 6、C二、判断题1 2 3 4 5 6三、简答题（略）四、算法分析题：1.分析下列程序段中带标号“#”语句的执行频度（n为正整数）。（1）频度： n，时间复杂度：O（n）（2）频度： 1，时间复杂度：O（1）（3）频度： n2，时间复杂度：O（n2）（4）频度： n/2-1，时间复杂度：O（n）（5）频度： 11002写出下列各程序段关于n的时间复杂度。（1）O（log3n）（2）O（n2）（3）O（n2）第2章 线性表一、选择题1、A 2.B 3.C 4. D 5. C 6.B 7. A 8.B 9.B 10.C 二、填空题1.
2、、线性表2、前驱，后继3、p-next; s-data; t4、q-next5、head-next = NULL6、p-next, s7、p-next != p8、 O(1), O(n)第3章 栈和队列一、选择题1、C 2.C 3.D 4.C 5.C 6.D 7.C 8.B 9.B 10. D 11.A 12.B二、填空题1.、n-12、O(n)3、135424、2xy+1x-/*5、36、a2, a4, a1, a2, 27、先进后出，加1， 减18、满，空，n9、线性结构10、4三、判断题1.、错2、错3、对4、错5、对6、错7、错四、解答题4、列车进入一个栈式结构的车站，开出车站有 14
3、 可能的顺序：abcd; abdcadcbacdb, acbdbdca,bcda, bcadbacd, badccdba,cbda, cbad,dcba列车进入一个队列式结构的车站，开出车站有 1 可能的顺序：abcd5、6, 247、staxy8、char9、第一个循环：队列Q中的元素依次出队，出队后即进栈S第二个循环：栈S中的元素依次出栈，出栈后即进入队列Q第4章 串一、选择题1、A 2、D 3、C 4、C 5、D二、简答题1、含零个字符的串称为空串，用表示，串的长度为0。而空格串是由一个或多个空格组成的串，串的长度为所含空格的个数。由串中任意连续字符组成的子序列称为该串的子串。包含子串的
4、串相应地被称为主串。假如一个串S=“a0a1a2an-1”(n0)，其中：S为串名，用双引号括起来的内容为串的值，双引号本身不是串的值。2、当且仅当两个串的长度相等并且各个对应位置上的字符都相同时，两个串才相等。3、19，7，good，e，0，3，”I am a good teacher”，”a goodyestea”4、j0123456模式串abcabaanextj-1000121三、算法题1、void Assign(string *s, string t) /s为串指针类型的参数 /将串变量t的值赋给串变量s int i; for(i=0;inext,*p2=t-next,*q,*r;st
5、r_temp=(Lstring*) malloc (sizeof(Lstring);str_temp-next=NULL;r=str_temp;if(poss.curlen) /参数不正确时返回空串 return str_temp; for(k=0;kstr=p1-str; q-next=NULL; r-next=q; r=q; p1=p1-next;while (p2!=NULL) q=(Lstring*) malloc (sizeof(Lstring);q-str=p2-str;q-next=NULL;r-next=q;r=q;p2=p2-next;while (p1!=NULL) /将*
6、p1及其后的结点复制到str_tempq=(Lstring*) malloc (sizeof(Lstring);q-str=p1-str;q-next=NULL;r-next=q;r=q;p1=p1-next;return str_temp;5、Lstring *Delete(Lstring *s, int pos, int len) /从串s中删去从第pos个字符起长度为len的子串 int k; Lstring *str_temp,*p=s-next,*q ,*r; str_temp=(Lstring*) malloc (sizeof(Lstring); str_temp-next=NUL
7、L; r=str_temp; if (poslength(s)-1 | | lenlength(s) return str_temp; /参数不正确时返回空串 for(k=0;kstr=p-str; q-next=NULL; r-next=q; r=q; p=p-next;for(k=0;knext;while(p!=NULL) /将*p及其后的结点复制到str_temp q=(Lstring*) malloc (sizeof(Lstring); q-str=p-str; q-next=NULL; r-next=q; r=q; p=p-next;return str_temp;第5章 数组和广
8、义表一、 选择题1、 C 2、 A 3、A 4、B 5、B 6、C 7、B 8、C 9、C 10、B二、 填空题：1、 线性结构顺序结构2、 以行为主序以列为主序3、（d1-c1+1）*（d2-c2+1）4、326【解析】采用列主序时，LOC（A612）=LOC（A00+（12*10+6）*1=3265、答: 9136、42【解析】A85前有8行，第0行1个元素，第1行2个元素，第7行8个元素，共（1+8）*8/2=36个元素，第8行前有5个元素，所以A85的地址为36+5+1=42。7、答: K=i(i-1)/2+j ,当ij时K=n(n+1)/2+1 ,当ij时8、22109、（x,y,z
9、）10、GetTail(GetTail(GetTail(GetHead(GetTail(LS)11、5 3三、操作题1、设数组元素Aij存放在起始地址为Loc （ i, j ） 的存储单元中。 Loc （ 2, 2 ） = Loc （ 0, 0 ） + 2 * n + 2 = 644 + 2 * n + 2 = 676. n = （ 676 - 2 - 644 ） / 2 = 15 Loc （ 3, 3 ） = Loc （ 0, 0 ） + 3 * 15 + 3 = 644 + 45 + 3 = 692.2、（1） 数组B共有12 + 3 + + n= （ n+1 ）*n / 2个元素。 （2
10、） 只存下三角部分时，若i j，则数组元素Aij前面有i-1行（1i-1，第0行第0列不算），第1行有1个元素，第2行有2个元素，第i-1行有i-1个元素。在第i行中，第j号元素排在第j个元素位置，因此，数组元素Aij在数组B中的存放位置为：1 + 2 + + （i-1） + j = （ i-1）*i / 2 + j若i j，数组元素Aij在数组B中没有存放，可以找它的对称元素Aji。在数组B的第 （j-1）*j / 2 + i位置中找到。如果第0行第0列也计入，数组B从0号位置开始存放，则数组元素Aij在数组B中的存放位置可以改为：当i j时，= i*（i+1） / 2 + j当i j时，=
11、 j*（j+1） / 2 + i 3、（1） Head （Tail （Tail （L1） ） ）（2） Head （Head （Tail （L2） ） ）（3） Head （Head （Tail （Tail （Head （L3） ） ） ） ）（4） Head （Head （Tail （Tail （L4） ） ） ）（5） Head （Tail （Head（L5） ） ）（6） Head （Head （Tail （Head （Tail （L6） ） ） ） ）4、由于线性表中的每个结点对应稀疏矩阵的一个非零元素，其中包括3个字段，分别为该元素的行下标、列下标和值，结点间的次序按矩阵的行优先顺序
12、排列，这个线性表用顺序的方法存储在连续的存储区，则对应的三元组为其十字链表形式为：5、 6、L=(a,(b,c),(d,(e)四、算法题1、【算法分析】从前向后找零元素Ai，从后向前找非零元素Aj，将Ai与Aj交换。【算法源代码】void move(int A,int n)int i=0,j=n-1;int temp;while(ij) while(Ai!=0) i+; while(Aj=0) j-; if(ij) temp=Ai;Ai=Aj;Aj=temp; 2、【算法分析】为保证算法的时间复杂度为O（m+n），即需要对数组A和B的数据元素仅扫描一次就能生成C数组，我们可采用设三个下标指针i,j,k初始时分别指向A数组的最后一个元素（A数组的最大值）、B数组的第一个元素（B数组的最大值）、C数组
