《数据结构习题解答.docx》由会员分享，可在线阅读，更多相关《数据结构习题解答.docx（28页珍藏版）》请在三一办公上搜索。
1、数据结构习题解答1.3 设n是正整数。试写出下列程序段中用记号“”标注的语句的频度： (2) i=1; k=0; do k+=10*i; i+; while(i=2时，执行n-1次； (3) i=1; k=0; do k+ = 10*i; i+; while(i=n); 当n=2时，执行2次； 当n!=2时，执行1次； (4) i=1; j=0; while(i+jn) if(i=(y+1)*(y+1) y+; 向下取整) x=91; y=100; while ( y0 ) if(x100) x-=10; y-; else x+ ; 执行(6) If语句执行100次 (7) for( i=0;
2、 in; i+) for( j=i; jn; j+) for( k=j; kx&i=0;i-) La.elemi+1=La.elemi; La.elemi+1=x; La.length+; return OK; /Insert_SqList 2.5 试写一个算法，实现顺序表的就地逆置，即在原表的存储空间将线性表逆置为(an,an-1, ., a2,a1) /思路就是两个指示变量i，j同时分别从顺序表的开始和结尾处相向改变 void reverse(SqList &A)/顺序表的就地逆置 ElemType p; for(i=1,j=A.length;ij;i+,j-) /A.elemiA.ele
3、mj; p=A.elemi; A.elemi=A.elemj; A.elemj=p; /reverse 2.7 已知线性表L采用顺序存储结构存放，对两种不同情况分别写出算法，删除L中多余的元素，使得L中没有重复元素：L中数据元素无序排列；(2)L中数据元素非递减有序排列。 void Delete_SameElem(SqLink &L, int L.length) /内层循环移动参数，中层循环寻找相同元，外层循环遍历整个表 int i=0; int j=i+1; int length=L.length; while(ilength) for(j=i+1;jlength; j+) if(L.Ele
4、mj=L.Elemi)/ for(k=j; kL.Elemi) break;/第二小问添加此句 /end for /end while /end functoion 2.8 已知线性表L采用链式结构存放。对两种不同情况分别写出算法，删除L中值相同的多余元素，使得L中没有重复元素：(1)L中数据元素无序排列；(2)L中数据元素非递减有序排列。 L中数据元素无序排列； 思路：由于是无序排列，需要线性表中每个元素都要相互进行比较。 Status ListDelete/L是带头结点的线性表 ElemType *p,*q; p=L-next;q=p-next; /设定p变化较慢，q变化较快 while(
5、p-next) while(q) if(p-data!=q-data) q=q-next; else q=q-next; p-next=q; /else /while p=p-next;q=p-next;/开始后一结点的寻找 return OK； /ListDelete (2)L中数据元素非递减有序排列。 思路：由于是有序的，遍历一次线性表就行了 Status ListDelete (LinkList &L) ElemType *p,*q; p=L-next;q=p-next; while(p-next) if (p-data!=q-data) p=p-next; /和第一问不同地方 q=p-
6、next; /if else while(p-data=q-data) q=q-next;/多个连续的重复值 /else p-next=q;p=q;q=p-next;/删除值重复的结点，并修改相应的指针 return OK； /ListDelete 2.9 设有两个非递减有序的单链表A,B。请写出算法，将A和B就地归并成一个按元素值非递增有序的单链表。 / 将合并逆置后的结果放在C表中，并删除B表 Status ListMergeOppose_L(LinkList &A,LinkList &B,LinkList &C) LinkList pa,pb,qa,qb; pa=A; pb=B; qa=
7、pa; / 保存pa的前驱指针 qb=pb; / 保存pb的前驱指针 pa=pa-next; pb=pb-next; A-next=NULL; C=A; while(pa&pb) if(pa-datadata) qa=pa; pa=pa-next; qa-next=A-next; A-next=qa; /将当前最小结点插入A表表头 else qb=pb; pb=pb-next; qb-next=A-next; A-next=qb; /将当前最小结点插入A表表头 while(pa) while(pb) pb=B; free(pb); return OK; qb=pb; pb=pb-next; q
8、b-next=A-next; A-next=qb; qa=pa; pa=pa-next; qa-next=A-next; A-next=qa; 2.13 设以带头结点的双向循环链表表示的线性表L=(a1,a2,a3,.,an)。试写一时间复杂度为O(n)的算法，将L改造为L=(a1,a3,.,an,.,a4,a2)。 void Reform(DuLinkedList &L)/按1,3,5,.4,2 的顺序重排双向循环链表L 中的所有结点 p=L.next; while(p-next!=L&p-next-next!=L) p-next=p-next-next; p=p-next; /p指向最后一
9、个奇数结点 if(p-next=L) /结点个数是奇数，使最后一个奇数结点next指向最后一个偶数结点 p-next=L-pre-pre; else/结点个数是偶数，使最后一个奇数结点next指向最后一个偶数结点 p-next=L-pre; p=p-next; /此时p 指向最后一个偶数结点 while(p-pre-pre!=L) p-next=p-pre-pre; p=p-next; p-next=L;/最后一个结点next指向头结点 /调整了next 链的结构,此时pre 链仍为原状 /调整pre 链的结构 for(p=L;p-next!=L;p=p-next) p-next-pre=p;
10、 L-pre=p; /头结点的pre指向a2结点 /Reform 第三章 栈和队列 3.6 试写一个算法，识别依次读入的一个以为结束符的字符序列是否为形如“序列1&序列2”模式的字符序列。其中，序列1和序列2中都不包含字符&,且序列2是序列1的逆序。例如，“a+b&b+a”是属于该模式的字符序列，而“13&31”则不是。 算法： int SeqReverse/判断输入的字符串中&前和&后部分是否为逆串,是则返回1,否则返回0 InitStack(s); while(e=getchar)!=&) if(e=) return 0;/不允许在&之前出现 push(s,e); /序列1输入完毕 whi
11、le( (e=getchar)!=) if(StackEmpty(s) return 0; pop(s,c); if(e!=c) return 0; if(!StackEmpty(s) return 0;/序列1元素还有剩余 return 1; /IsReverse 3.7 假设一个算术表达式中可以包含三种符号：圆括号“(”和“)”、方括号“”和“”、花括号“”和“”，且这三种括号可按任意次序嵌套使用。编写判别给定表达式中所含的括号是否正确配对的算法。 算法： Status BracketTest(char *str)/判别表达式中三种括号是否匹配 InitStack(s); for(p=st
12、r;*p;p+) if(*p=( | *p= | *p= ) push(s,*p); else if(*p= ) | *p= | *p= ) if(StackEmpty(s) return ERROR; pop(s,c); if(*p=)&c!=() return ERROR; if(*p=&c!=) return ERROR; if(*p=&c!=) return ERROR; /必须与当前栈顶括号匹配 /if /for if(!StackEmpty(s) return ERROR;/进栈的符号还有剩余，Error return OK; /BracketTest 3.8 设表达式由单字母变量
13、、双目运算符和圆括号组成”。试写一个算法，将一个书写正确的表达式转换为逆波兰式。 思路： 1.遇到数字直接发送 2.遇到(直接入栈 3.遇到)则将栈内元素发送直至遇到( 4.栈空则直接入栈 5.栈非空时若优先级大于栈内则入栈，否则栈内元素出栈 int RankOfOperator(char c) switch(c) case #: return -1; case (: return 0; case +: case -: return 1; case *: case /: case ):return 2; int Precede(char c, char ch) return RankOfOpe
14、rator(c)RankOfOperator(ch); void ExpressionTOPolandStyle(char suffix,char *exp) Stack s; InitStack(s,100); int i=0; char c; while(*exp) if(isdigital(*exp) suffixi+=*exp; else switch(*exp) case (: push(s,(); case ): while(c=pops(s)!=() suffixi+=c; break; default: if(IsEmpty(s) push(s,*exp); else suff
15、ixi+=pop(s); exp-; /与后面的exp+相抵消，使得栈内优先级大于等于栈外的都出栈 /end switch /end else exp+; /end while while(!IsEmpty(s) suffixi+=pop(s); suffixi=0; 3.10 假设以带头结点的单循环链表表示队列，只设一个尾指针指向队尾元素，不设头指针。试编写相应的队列初始化、入队和出队算法 要点：定义好数据类型，带头结点的单循环链表，只有尾指针，注意删除元素时只有一个元素的特殊性 typedef int DataType struct Node DataType data; Node * n
16、ext; ; struct CycleListQueue Node * tail; ; void InitCycleListQueue(CycleListQueue&L) L.tail = new Node; L.tail-next = L.tail; void EnterQueue(CycleListQueue&L,DataType value) Node* p = new Node; p-data = value; p-next = L.tail-next; L.tail-next = p; L.tail = p; void DeparQueue(CycleListQueue&L,Data
17、Type &d) if(L.tail-next != L.tail-next-next) Node *p = L.tail-next-next; L.tail-next-next = p-next; d = p-data; if(p=L.tail) L.tail=p-next; delete p; return d; 3.11 假设将循环队列定义为：以rear和length分别指示队尾元素和队列长度。试给出此循环队列的队满条件，并写出相应的入队和出队算法。 此循环队列的队满条件：Q.length=MAXQSIZE; 入队算法： Status EnCyQueue(CyQueue &Q,int x
18、)/带length 域的循环队列入队算法 if(Q.length=MAXSIZE) return OVERFLOW; Q.rear=(Q.rear+1)%MAXSIZE; Q.baseQ.rear=x; /rear指向队尾元素 Q.length+; return OK; /EnCyQueue 出队算法： Status DeCyQueue(CyQueue &Q,int &x)/带length 域的循环队列出队算法，用x返回队头元素的值 if(Q.length=0) return Error;/空队列，错误 head=(Q.rear-Q.length+1)%MAXSIZE; /head指向队头 x
19、=Q.basehead; Q.length-; return OK； /DeCyQueue 3.12 试写一个算法：判别读入的一个以为结束符的字符序列是否是“回文”。 Status Test/判别输入的字符串是否回文序列,是则返回1,否则返回0 InitStack(S); InitQueue(Q); while(c=getchar)!=) Push(S,c); EnQueue(Q,c); /同时使用栈和队列两种结构 while(!StackEmpty(S) Pop(S,a); DeQueue(Q,b); if(a!=b) return ERROR; return OK; / Test 第五章
20、多维数组 5.4 设有一个准对角矩阵 a11a21a12a22a33a43a34a44.a2m-1,2m-1a2m,2m-1 a2m-1,2ma2m,2m按以下方式存于一维数组B4m中： 0 1 2 3 4 5 6 k 4m-2 4m-1 a11 a12 a21 a22 a33 a34 a43 . aij . a2m-1,2m a2m,2m 写出由一对下标(i,j)求k的转换公式。 因为i行前有2(i-1)个元素。现考虑i行情况，当j是奇数，i行有1个元素,k=2(i-1)+1-1=2(i-1)；否则i行有2个元素，k=2(i-1)+2-1=2i-1。故： k= 或若i为奇数，k=2(i-1)
21、+j-i=i+j-2;当i为偶数时，k=2i-(i-j)-1=i+j-1 k=5.5 已知稀疏矩阵A45如下： 02A=0013040000060050 07(1)用三元组表作为存储结构，绘出相应的三元组表示意图； (2)用十字链表作为存储结构，绘出相应的十字链表示意图。 (1)三元组表： i 1 1 2 2 2 4 4 (2)十字链表 j 2 5 1 2 4 2 5 v 1 5 2 3 6 4 7 121155212223246第六章 数和二叉树 6.5 已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，.，nk个度为k的结点，问该树中有多少个叶子结点？ 设叶子结点有x个，则树的
22、结点总数为n1+n2+nk+x; 同时除了根结点外，每个结点都指向一个结点，所有从这个角度考虑树的结点总数为：n1+2n2+knk+1; n1+n2+nk+x= n1+2n2+knk+1,可得x=(i-1)ni+1 i=2k6.8已知一棵树如图6-1所示，画出与该树对应的二叉树，并写出该树的先根遍历序列和后根遍历序列。 424457 A B C D E F G H I J K 图6-1 先根遍历：ABCEIJFGKHD 后根遍历：BIJEFKGHCDA 对应的二叉树： A B C E D I F J G K H 6.9 将如图6-2所示的森林转化为对应的二叉树。 A B I J K M L N
23、 C D E F G H 树对应的二叉树 A B C D E F H G 森林对应的二叉树： 6-2 I J K 图6-2 O L M N O 图 A B C D L E F H G M N O I J K 6.11已知某二叉树的中序序列为DCBGEAHFIJK，后序序列为DCEGBFHKJIA。请画出该二叉树。 A B C D G E I H F J K 6.14 假设某个电文由(a,b,c,d,e,f,g,h)8个字母组成，每个字母在电文中出现的次数分别为(7,19,2,6,32,3,21,10)，试解答下列问题： (1) 画出出huffman树； 1000 60 28 11 G 40 1
24、9b 21g 5 2c 3f 17 6d 7a 10h 32e (2) 写出每个字母的huffman编码； a:1010 b:00 c:10000 d:1001 e:11 f:10001 g:01 h:1011 (3) 在对该电文进行最优二进制编码处理后，电文的二进制位数。 4*7+2*19+5*2+4*6+2*32+5*3+2*21+4*10=261 6.17 写出按层次遍历二叉树的算法。 思路：用队列存储结构，并用递归方法 Status LevelOrderTraverse(BitTree T,Status (*Visit)(TElemType e)/层序遍历二叉树 InitQueue(Q
25、); /初始化队列 if(!T) return Error;/空树，直接返回 EnQueue(Q,T);/根结点入队 BiTNode *p; while(!QueueEmpty(Q) DeQueue(Q,p); Visit(p-data); if(p-lchild) EnQueue(Q,p-lchild); if(p-rchild) EnQueue(Q,p-rchild); /while return Ok; /LevelOrderTraverse 6.19 写出判断两棵给定二叉树是否相似的算法。 (注：两棵二叉树B1和B2相似是指：B1和B2皆空，或者皆不空且B1的左、右子树和B2的左、右子
26、树分别相似。) 思路：采用递归进行比较判断 bool BiTreeSimilar (BiTree T1,BiTree T2) if(T1=Null&T2=Null) return 1; else if(T1=Null | T2=Null) return 0; else return (BiTreeSilimar(T1-lchild,T2-lchild)&BiTreeSimilar(T1-rchild,T2-rchild); 6.21 写出统计树中叶子结点个数的算法，树用孩子兄弟链表表示。 思路：在孩子兄弟链表中，若结点的firstchild为Null，则为叶子结点；采用递归方法。 int Co
27、untLeaves(Tree T，int &num)/num传递的初值为0 if(T-nextsibling!=Null) num+=CountLeaves (T-nextsibling); if(T-firstchild!=Null) num+=CountLeaves(T- firstchild); else num+=1;/firstchild域为空，则为叶子结点 return num; 第七章 图 V1 7.1 已知有向图如图7-1所示， 请给出该图的 (1)邻接矩阵示意图 (2)邻接表示意图 (3)逆邻接表 (4)所有强连通分量 V5 V6 V2 V4 V3 图7-1 (1) 邻接矩阵
28、 010011000000010010001010110000010010邻接表 0v11v22v3345v4v5v635504014210逆邻接表 0v11v22v3345553153421v4v5v632强连通分量 V1 V5 V6 V2 V4 V3 7.2 已知图G的邻接矩阵如图7-2所示。写出该图从顶点1出发的深度优先搜索序列和广度优先搜索序列，并画出相应的深度优先生成树和广度优先生成树。 1 2 3 4 5 6 7 8 9 1 0 0 0 0 0 0 1 0 1 2 0 0 1 0 0 0 1 0 0 3 0 0 0 1 0 0 0 1 0 4 0 0 0 0 1 0 0 0 1 5
29、 0 0 0 0 0 1 0 0 0 6 1 1 0 0 0 0 0 0 0 7 0 0 1 0 0 0 0 0 0 8 1 0 0 1 0 0 0 0 1 9 0 0 0 0 1 0 1 0 0 10 1 0 0 0 0 1 0 0 0 图7-2 深度优先序列：1 7 3 4 5 6 2 10 9 8 17348596102深度优先生成树：广度优先序列：1 7 9 3 10 5 4 8 6 2 17931054862广度优先生成树： 10 0 0 0 0 1 0 1 0 1 0 9.1若对大小均为n的有序顺序表和无序顺序表分别进行顺序查找，试在下列三种情况下分别讨论两者在等概率时平均查找长度
30、是否相同？ 查找不成功，即表中没有关键字等于给定的值K的记录； 查找成功，且表中只有一个关键字等于给定值K的记录； 查找成功，且表中有若干个关键字等于给定值K的记录，要求找出所有这些记录。 解： 对有序顺序表： 1. 1n+21+2+.+(n+1)=2 21n+11+2+.+n= n23. 1n-k+21+2+.+n-(k-1)= 将此K项看作一项 n-(k-1)2对无序顺序表： 1. n 2. 1n+11+2+.+n= n23. ni=(n+k)(n-k+1)2i=k1n+k= 考虑最后一个记录的出现位置 n-k+129.3 画出对长度为17的有序表进行折半查找的判定树，并分别求其等概率时查
31、找长度和查找失败的ASL。 1591?12?23?44?85?2)17 (17176=(4?75?24?75?)2 增加虚结点 ASL1818解：ASL=94132611151357101214168179.4已知如下所示长度为12的表：表中，每一个元素的查找概率分别为： 若对该表进行顺序查找，求查找成功的平均查找长度； 画出从初态为空开始，依次插入结点，生成的二叉排序树； 计算该二叉排序树查找成功的平均查找长度； 将二叉排序树中的结点Mar删除，画出经过删除处理后的二叉排序树。 解： ASL=0.1?10.25?2.+0.07?12 与初始输入序列有关 5.43 JanFebMarAprJu
32、nMayAugJulySepDecOctNov ASL=0.1?10.25?2.+0.07?53.2 找到Mar的直接后继，将Mar的左子树移动到最左孩子的左孩子处，然后用直接后继取代当前结点。 JanFebMayAprJunSepAugJulyOctDecNov9.5 已知关键字序列10，25，33，19，06，49，37，76，60，哈希地址空间为0-10，哈希函数为H(key)=Key%11，求： 用开放定址线性探测法处理冲突，构造哈希表HT1，分别计算在等概率情况下HT1查找成功和查找失败的ASL； 用开放定址二次探测法处理冲突，构造哈希表HT2，计算在等概率下HT2查找成功的ASL；
33、 用拉链法解决冲突，构造哈希表HT3，计算HT3在等概率情况查找成功的ASL。 解： 这9个数的hash值为： 10,3,0,8,6,5,4,10,5 冲突有2个。 0 33 1 76 2 3 25 4 37 5 49 6 06 7 60 8 19 9 10 10 ASL1=11?73?13?1)(913 938 遇到空还没有，则算失败。 11ASL2=(F(0)+F(1)+.+F(10)/11=d=0,1,-1,4,-4 0 33 1 60 2 3 4 25 5 49 6 06 7 8 19 9 76 10 10 ASL=(3) 012345678910151?73?15?1 )(93332537490660191076ASL=11?72?2)(911 9
