数据结构(马睿、孙丽云)习题答案.doc

第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、前驱，后继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 可能的顺序：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。而空格串是由一个或多个空格组成的串，串的长度为所含空格的个数。由串中任意连续字符组成的子序列称为该串的子串。包含子串的串相应地被称为主串。假如一个串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;str_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) /将*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=NULL; 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章 数组和广义表一、 选择题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）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） 只存下三角部分时，若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时，= 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个字段，分别为该元素的行下标、列下标和值，结点间的次序按矩阵的行优先顺序排列，这个线性表用顺序的方法存储在连续的存储区，则对应的三元组为其十字链表形式为：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(i=0)&(jBj) Ck=Ai; i-; else Ck=Bj; j+; k-; while(i=0)Ck=Ai;i-;k-; while(jmu=A.nu;B-nu=A.mu;B-tu=A.tu;if(B-tu0) j=1; for(k=1;k=A.nu;k+) for(i=1;idataj.row=A.datai.col; B-dataj.col=A.datai.row; B-dataj.e=A.datai.e; j+; 4、【算法分析】在求广义表深度的递归算法中，若结点为原子则深度为0，若是空表深度为1，否则返回头指针与尾指针所指广义表的深度最大值。【算法源代码】int Glist_Getdeph(Glist L)int m,n; if(!L-tag) return 0; else if(!L) return 1; m=Glist_Getdeph(L-ptr.hp)+1; n=Glist_Getdeph(L-ptr.tp); return mn?n:n; 第6章树一选择题1、B 2、A 3、B 4、A 5、C 6、C A 7、B 8、B 9、D 10、B11、B 12、B 13、B 14、A 15、C 16、D 17、A 18、A 19、C 20、D二填空题1 1 前驱 2 一个前驱结点 3 后继 4 后继2. n-1 3. n0=n2 +1 4. 1 2 2 10 3 11 5. 1 A 2 D G F 3 B E 4 A C 5 B 6 A C E 7 右 8 左 9 2 10 46. 2507. 18. 2n0-19. 1 D 2 F10. 1 GEACBDF 2 111. 1 InOrderTraverse (T-left) 2 printf(T-data) 3 InOrderTraverse (T-right) 12. 。三判断题1 2 3 4 5 6 7 8 9 10四操作题1(1) (2) GCABFED(3)(4) (5) (6)23(1)所有结点均没有左孩子的二叉树。 (2)所有结点均没有右孩子的二叉树 (3)只有一个根结点的二叉树4 证明： 当n=1时，前序序列和中序序列均只有一个元素且相同，即为根，由此唯一地确定了这颗二叉树。 假设nlchild=NULL ) & (bt-rchild=NULL )return 0; /*只有根节点时，结点数为0*/else if (bt-lchild=NULL ) | (bt-rchild=NULL ) return (1+Nodes(bt-lchild)+Nodes(bt-rchild); /*返回当前根节点和左或右子树中满足条件的节点数目*/else return (Nodes(bt-lchild)+Nodes(bt-rchild);/*返回左右子树中满足条件的节点数目*/Nodes 2void LeafPath(BiTree T, int num)/*求二叉树根结点T到所有叶子结点的路径*/*用数组path存储路径（不包括T在内），其中已有的元素个数为num，其初值为0*/ BiTree p; int top,i;if (T=NULL) /*如果二叉树为空，则给出相应信息，算法结束*/printf(二叉树为空!); return;if (T-lchild=NULL & T-rchild=NULL) printpath(path,T,num);/*输出路径*/ else pathnum+1=T; /*将T放到路径中*/ LeafPath(T-lchild,num+1); LeafPath(T-rchild,num+1);其中printpath函数代码如下：void printpath(BiTNode *path, BiTree T, int num) printf(%c：,T-data); for(int i=1;idata); printf(%cn,T-data);3void PreOrderTraverse(BiTree T, int high )/*设二叉树的根指针为T，T所指结点的层次为high */ if(T) printf(%c, %d),T-data,high); PreOrderTraverse(T-lchild, high+1); PreOrderTraverse(T-rchild, high+1);4BiTree change(BiTree T)/*二叉树左右子树交换递归算法*/BiTree p;if(T!=NULL)if(T-lchild!=NULL|T-rchild!=NULL)p=(BiTree)malloc(sizeof(BiTNode);p-data=T-data;p-rchild=NULL;p-lchild=T-lchild;T-lchild=T-rchild; T-rchild=p-lchild;T-lchild=change(T-lchild);T-rchild=change(T-rchild);return T;5BiTNode *Node(BiTree bt)/*求二叉树T的后序序列的第一个结点的指针，采用非递归算法*/StackElemType stackBiTree_Max_Size; /*定义顺序栈*/ BiTree p; int top; top = -1; /*栈初始化*/ p=bt; while(p) /*二叉树非空，根结点及其tag标记0一同入栈，然后遍历其左子树*/ top+; stacktop.T=p; p=p-lchild; if(top != -1) return stacktop.T;else return NULL;6BiThrNode *PreOrder_Next(BiThrNode *p) /在先序后继线索二叉树中查找结点p的先序后继，并返回指针if(p-Ltag=0) return p-lchild; else return p-rchild;/PreOrder_Nextvoid PreOrderTraverse_Thr(BiThrTree T)BiThrNode *p;p=T;while(p!=NULL) Visit(p-data); p=PreOrder_Next(T); 7typedef char TElemType;/-二叉树的二叉链表存储表示-typedef struct BiTNodeTElemType data;struct BiTNode *lchild,*rchild;*BiTree;typedef struct qnode BiTree T; struct qnode *next;LINKQLIST;typedef struct LINKQLIST *front,*rear;LINKQUEUE;void initlinkqueue(LINKQUEUE *q)/初始化广度优先遍历算法中用到的链队列q-front=malloc(sizeof(LINKQLIST);(q-front)-next=NULL;q-rear=q-front;int emptylinkqueue(LINKQUEUE *q) /判队空？ int v;if(q-front=q-rear) v=1; else v=0;return v;void enlinkqueue(LINKQUEUE *q,BiTree t) /元素入队列 (q-rear)-next=malloc(sizeof(LINKQLIST); q-rear=(q-rear)-next;(q-rear)-T=t;(q-rear)-next=NULL;BiTree dellinkqueue(LINKQUEUE *q) /删除队头元素 LINKQLIST *p;BiTree v;if(emptylinkqueue(q)printf(队列空.n);v=0; elsep=(q-front)-next;(q-front)-next=p-next;if(p-next=NULL) q-rear=q-front;v=p-T;free(p);return v;void visite(LINKQUEUE *q, BiTree p)if(p!=NULL)printf(%c ,p-data);enlinkqueue(q,p);void Level_Traverse(BiTree T)/*按层次遍历二叉树*/LINKQUEUE Que,*Q;BiTree p;Q=&Que;initlinkqueue(Q);if(T!=NULL)visite(Q,T);while(!emptylinkqueue(Q)p=dellinkqueue(Q);visite(Q,p-lchild);visite(Q,p-rchild); printf(The pointer which points at the last Node is %xn,p);/*给出离根结点最远的一个结点（即最后一个出队的结点）的指针*/8int Node(BiTree T) /*求以孩子兄弟链表存储的树或森林T中的结点数，并通过函数值返回*/ int count; BiTree T1;if(T =NULL) return 0; /*bt为空时，结点数为0*/ else if(T-firstchild =NULL) return 1;else count=0; T1=T-firstchild; while(T1) count=cout+Node(T1);T1=T1-nextsibling; return count;9int High(BiTree T) /*求以孩子兄弟链表存储的树或森林T的高度，并通过函数值返回*/ int h1,h2; BiTree T1;if(T =NULL) return 0; /*bt为空时，结点数为0*/else h1=High(T-firstchild)+1;h2=High(T-nextsibling);return h1h2? h1:h2;10char Pred,Midd; /前序序列和中序序列已经分别储存在数组Pre和Mid中Bitree Build_Sub(int Pre_Start,int Pre_End,int Mid_Start,int Mid_End)/由子树的前序和中序序列建立其二叉链表 BiTree sroot,lroot,rroot; sroot=(BiTNode*)malloc(sizeof(BiTNode); /建根 sroot-data=PrePre_Start; for(i=Mid_Start;Midi!=sroot-data;i+); /在中序序列中查找子树根 leftlen=i-Mid_Start; rightlen=Mid_End-i; /计算左右子树的大小 if(leftlen) lroot=Build_Sub(Pre_Start+1,Pre_Start+leftlen,Mid_Start,Mid_Start+leftlen-1); sroot-lchild=lroot; /建左子树,注意参数表的计算 if(rightlen) rroot=Build_Sub(Pre_End-rightlen+1,Pre_End,Mid_End-rightlen+1,Mid_End); sroot-rchild=rroot; /建右子树,注意参数表的计算 return sroot; /返回子树根/Build_Sub main() . Build_Sub(1,n,1,n); /初始调用参数,n为树结点总数 .分析:本算法利用了这样一个性质,即一棵子树在前序和中序序列中所占的位置总是连续的.因此,就可以用起始下标和终止下标来确定一棵子树.Pre_Start,Pre_End,Mid_Start和Mid_End分别指示子树在前序子序列里的起始下标,终止下标,和在中序子序列里的起始和终止下标.第7章 图一、选择题1B 2B 3B和C 4D和E 5 C 6D 7A 8A 9D 10B二、填空题1. 1 n(n-1) 2 n(n-2)/2 3 n-12. 1 ABCDFE 2 ABCEFD3. 1 按深度 2按广度4极大5.图本身6.主对角线7.1 i 2 j 8. 1 n-1 2 大于 n-1 3 小于n-19. 20 10. 1 n+2e 2 2e 3 n11. 1 n+e 2 e 3 n12.无环三、判断题1 2 3 4 5 678四、（略）五、（略）第8章 查找一、选择题1、C 2、B 3、A 4 、C 5、C 6、D 7、B 8、B 9、B 10、D11、C 12、C 13、D 14、D 15、D 16、C 17、A 18、B 19、D 20、B二、判断题1 【答案】错误【分析】顺序查找并没有假设数有序或者无序，因此有序或无序对平均查找长度没有影响。2【答案】错误3【答案】正确4【答案】错误【分析】链表表示的有序表不能用折半查找法查找。5【答案】错误6【答案】错误【分析】最优二叉树是静态树表，AVL是动态树表，二者范围不同。7【答案】正确8【答案】正确9【答案】正确10【答案】正确11【答案】错误【分析】除非被删除的结点是叶子结点，否则删除后再插入同一结点得到的二叉排序树与原来的二叉排序树不同。12【答案】错误13【答案】错误14【答案】错误15【答案】正确16【答案】正确17【答案】错误【分析】越小，只能说发生冲突的可能性越小，但依然有可能发生冲突。18【答案】正确19【答案】正确20【答案】正确三、填空题1【分析】最优二叉树是对叶子结点带权平均查找路径长度最小的树，最优查找树是对所有结点带权查找路径长度最小的树，构造这两种树均需要知道关键字的查找概率。【解答】叶子结点数 结点数 需要n个关键字的查找概率表2【分析】折半查找法在查找成功与不成功时进行比较的关键字个数最多不超过树的深度，而具有n个结点的判定树的深度为log2n+1，所以，最大比较次数为log2n+1。【答案】log2n+1 3【分析】平均检索长度ASLss=(s+n/s)/2+1，所以当S=时，ASLss取得最小值+1。【解答】16 17 214【分析】第4层是叶子结点，每个结点两个关键字，21231232=26。【答案】26四、简答题1【解答】判定树如下所示：75321468910等概率查找时成功的平均查找长度为ASLsucc=(11+22+34+43)=2.92【解答】（1）按关键字的顺序构造的二叉排序树：OctNovDecJulyAugSepAprMayJunJanFebMar（2）根据构造的二叉排序树，求查找成功时的平均查找长度：ASLSUCC=(1*1+2*2+3*3+4*3+5*2+6*1)/12=3.5（3）若对表中元素先进行排序构成有序表再构造二叉排序树，则构造的二叉排序树是一棵单支树，在等概率的情况下查找成功的平均查找长度则为：ASLSUCC=(1+2+12)/12=6.5这种情况就退化成为顺序查找。350 100150804060 7090120180203030 4050 70901206080100180插入20删除150【解答】4 8392620108392620插入6插入10【解答】8392620108392620插入6插入105【解答】令Fk表示含有最少结点的深度为k的平衡二叉树的结点数目。那么,可知道F1=1,F2=2,.Fn=Fn-2+Fn-1+1.含有12个结点的平衡二叉树的最大深度为例如：ABCDEHFGJKIL6【解答】4个、7个。7【解答】526860030502070706052 6820 305220 3060 708【分析】主要考察用线性探测再散列法和链地址法构造哈希表。哈希表的装填因子定义为：=表中添入的记录数/哈希表的长度 【解答】使用线性探测再散列法来构造哈希表见下表：地址0 1 2 3 4 5 6 7 8 9 10数据33 1 13 12 34 38 27 22hashf1(1)=1hashf1(13)=2hashf1(12)=1 hashf2(12)(1+1)%11=2 hashf3(12)= (1+2)%11=3hashf1(34)=3 hashf2(34)=(3+1)%11=4hashf1(38)=5hashf1(33)=0hashf1(27)=5 hashf2(27)=(5+1)%11=6hashf1(22)=0 hashf2(22)=(0+1)%11=1 hashf3(22)=2 hashf4(22)=3hashf5(22)=4 hashf6(22)=5 hashf7(22)=6 hashf8(22)=7装填因子a8/11查找成功所需的平均查找次数：(1+1+3+2+1+1+2+8)/8=19/8使用链地址法来构造哈希表如下图所示：012345678 9103311322123427查找成功所需的平均查找次数：(1*3+2*3+3*1)/8=3/29【解答】（1）012345678910111213141516AprAugDecFebJanMarMayJuneJulySepOctNov平均查找长度为:31/12Aug AprDec Feb JanJuly JuneMarMay OctNov Sep （2）012345678910111213141516平均查找长度为:3/2五、算法设计题1【分析】算法思想：先遍历右子树后遍历左子树。【解答】算法如下：Inorder(BiSTree bt, datatype X) if (bt) Inorder(bt-rchild，X);if(bt-data=X) printf(“%c”，bt-data); Inorder(bt-lchild，X); 2【分析】在合并过程中，并不释放或新建任何结点，而是采取修改指针的方式来完成合并，这样，就必须按照后序序列把一棵树中元素逐个连接到另一棵树上，否则将会导致树的结构的混乱。【解答】算法如下：void BiTMerge(BiSTree *T, BiSTree *S) /*把二叉排序树合并到T中*/ if(S-lchild) BiTMerge (T，S-lchild); if(S-rchild) BiTMerge (T，S-rchild) /*合并子树*/ Insert_Node(T，S);void Insert (BiSTree *T，BiSTNode *S) /*把树结点S插入到T的合适位置*/ if(S-dataT-data) if (!T-rchild) T-rchild=S; else Insert (T-rchild，S);else if(S-datadata) if (!T-lchild) T-lchild=S; else Insert (T-lchild，S);S-lchild=NULL; /*插入的新结点必须和原来的左右子树断绝关系*/S-rchild=NULL;/*否则会导致树结构的混乱*/ 3【分析】算法思想；以x为分界点遍历原二叉树并构造两棵新的二叉排序树。【解答】算法如下: void BiTSplit(BiSTree *T, BiSTree *A, BiSTree *B，int x) /*把二叉排序树T分裂为两棵二叉排序树A和B，其中A的元素全部小于等于x，B的元素全部大于x*/ if (T-lchild) BiTSplit(T-lchild，A，B，x); if (T-rchild) BiTSplit(T-rchild，A，B，x);/*分裂左右子树*/ if (T-datadataT-rchild) if (!T-rchild) T-rchild=S; else Insert (T-rchild.S); else if(S