数据结构(C语言版)习题解答(18页).doc

《数据结构(C语言版)习题解答(18页).doc》由会员分享，可在线阅读，更多相关《数据结构(C语言版)习题解答(18页).doc（18页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、-数据结构(C语言版)习题解答-第 18 页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+;执行向下取整)(6)x=91; y=100;while ( y0 )if(x100) x-=10; y-; else x+ ; If语句执行100次(7)for( i=0; in;

2、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_SqList2.5试写一个算法，实现顺序表的就地逆置，即在原表的存储空间将线性表（a1,a2, ., an-1,an）逆置为(an,an-1, ., a2,a1)/思路就是两个指示变量i，j同时分别从顺序表的开始和结尾处相向改变void reverse(SqList &A)/顺序表的就地逆置ElemType p;for(i=1,j=A.length;ij;i+,j-) /A.elemiA.el

3、emj; p=A.elemi; A.elemi=A.elemj; A.elemj=p;/reverse2.7 已知线性表L采用顺序存储结构存放，对两种不同情况分别写出算法，删除L中多余的元素，使得L中没有重复元素：（1）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.Elemj=L

4、.Elemi)/for(k=j; kL.Elemi) break;/第二小问添加此句/end for/end while/end functoion2.8已知线性表L采用链式结构存放。对两种不同情况分别写出算法，删除L中值相同的多余元素，使得L中没有重复元素：(1)L中数据元素无序排列；(2)L中数据元素非递减有序排列。（1）L中数据元素无序排列；思路：由于是无序排列，需要线性表中每个元素都要相互进行比较。Status ListDelete（Linklist &L）/L是带头结点的线性表 ElemType *p,*q; p=L-next;q=p-next; /设定p变化较慢，q变化较快whil

5、e(p-next) while(q) if(p-data!=q-data) q=q-next;else q=q-next; p-next=q; /else/whilep=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-next;

6、/if else while(p-data=q-data) q=q-next;/多个连续的重复值 /else p-next=q;p=q;q=p-next;/删除值重复的结点，并修改相应的指针return OK；/ListDelete2.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=pa;/ 保存pa的前驱指针q

7、b=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表表头A-next=qa;elseqb=pb;pb=pb-next;qb-next=A-next;/将当前最小结点插入A表表头A-next=qb;while(pa)qa=pa;pa=pa-next;qa-next=A-next;A-next=qa;while(pb)qb=pb;pb=pb-next;qb-next=A-next;A-next=qb;p

8、b=B;free(pb);return OK;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指向最后一个奇数结点if(p-next=L) /结点个数是奇数，使最后一个奇数结点next指向最后一个偶数结点 p-n

9、ext=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;L-pre=p; /头结点的pre指向a2结点/Reform第三章 栈和队列3.6 试写一个算法，识别依次读入的一个以为结

10、束符的字符序列是否为形如“序列1&序列2”模式的字符序列。其中，序列1和序列2中都不包含字符&,且序列2是序列1的逆序。例如，“a+b&b+a”是属于该模式的字符序列，而“13&31”则不是。算法：int SeqReverse()/判断输入的字符串中&前和&后部分是否为逆串,是则返回1,否则返回0InitStack(s);while(e=getchar()!=&)if(e=) return 0;/不允许在&之前出现push(s,e);/序列1输入完毕while( (e=getchar()!=)if(StackEmpty(s) return 0;pop(s,c);if(e!=c) return

11、0;if(!StackEmpty(s) return 0;/序列1元素还有剩余return 1;/IsReverse3.7 假设一个算术表达式中可以包含三种符号：圆括号“(”和“)”、方括号“”和“”、花括号“”和“”，且这三种括号可按任意次序嵌套使用。编写判别给定表达式中所含的括号是否正确配对的算法（已知表达式已存入数据元素为字符的顺序表中）。算法：Status BracketTest(char *str)/判别表达式中三种括号是否匹配InitStack(s);for(p=str;*p;p+)if(*p=( | *p= | *p= ) push(s,*p);else if(*p= ) | *

12、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/forif(!StackEmpty(s) return ERROR;/进栈的符号还有剩余，Errorreturn OK;/BracketTest3.8 设表达式由单字母变量、双目运算符和圆括号组成（如:“(a*(b+c)-d)/e）”。试写一个算法，将一个书写正确的表达式转换为逆波兰式。思路：1.遇到数字直接发

13、送 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 RankOfOperator(c)RankOfOperator(ch);void ExpressionTOPolandStyle(char suff

14、ix,char *exp)Stack s; InitStack(s,100); int i=0; char c;while(*exp)if(isdigital(*exp)suffixi+=*exp;elseswitch(*exp)case (: push(s,();case ): while(c=pops(s)!=() suffixi+=c;break;default: if(IsEmpty(s) push(s,*exp); else suffixi+=pop(s); exp-; /与后面的exp+相抵消，使得栈内优先级大于等于栈外的都出栈/end switch/end elseexp+;/e

15、nd whilewhile(!IsEmpty(s) suffixi+=pop(s); suffixi=0;3.10 假设以带头结点的单循环链表表示队列，只设一个尾指针指向队尾元素，不设头指针。试编写相应的队列初始化、入队和出队算法（在出队算法中要传回队头元素的值）要点：定义好数据类型，带头结点的单循环链表，只有尾指针，注意删除元素时只有一个元素的特殊性typedef int DataTypestruct NodeDataType data;Node * next;struct CycleListQueueNode * tail;void InitCycleListQueue(CycleList

16、Queue&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,DataType &d)if(L.tail-next != L.tail-next-next)Node *p = L.tail-next-next;L.tail-next-ne

17、xt = 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)/带length 域的循环队列入队算法if(Q.length=MAXSIZE) return OVERFLOW;Q.rear=(Q.rear+1)%MA

18、XSIZE; 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=Q.basehead;Q.length-;return OK；/DeCyQueue3.12 试写一个算法：判别读入的一个以为结束符的字符序列是否是“回文”（所谓“回文”是指

19、正读和反读都相同的字符序列，如“xxyzyxx”是回文，而“abcab”则不是回文）。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第五章 多维数组5.4 设有一个准对角矩阵按以下方式存于一维数组B4m中：0123456k

20、4m-24m-1a11a12a21a22a33a34a43.aij.a2m-1,2ma2m,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)+j-i=i+j-2;当i为偶数时，k=2i-(i-j)-1=i+j-1k=5.5 已知稀疏矩阵A45如下：(1)用三元组表作为存储结构，绘出相应的三元组表示意图；(2)用十字链表作为存储结构，绘出相应的十字链表示意图。(1)三元组表：ijv121155

21、212223246424457(2)十字链表第六章 数和二叉树6.5 已知一棵度为k的树中有n1个度为1的结点，n2个度为2的结点，.，nk个度为k的结点，问该树中有多少个叶子结点？设叶子结点有x个，则树的结点总数为n1+n2+nk+x;同时除了根结点外，每个结点都指向一个结点，所有从这个角度考虑树的结点总数为：n1+2n2+knk+1;n1+n2+nk+x= n1+2n2+knk+1,可得x=6.8已知一棵树如图6-1所示，画出与该树对应的二叉树，并写出该树的先根遍历序列和后根遍历序列。ABCDEFGHKIJ图6-1先根遍历：ABCEIJFGKHD后根遍历：BIJEFKGHCDA对应的二叉树

22、：ABCDEFGHKIJ6.9 将如图6-2所示的森林转化为对应的二叉树。K图6-2ACDEBFGHJILMNO树对应的二叉树K图6-2ACDEBFGHJILMNO 森林对应的二叉树：KACDEBFGHJILMNO6.11已知某二叉树的中序序列为DCBGEAHFIJK，后序序列为DCEGBFHKJIA。请画出该二叉树。KACDEBFGHJI6.14 假设某个电文由(a,b,c,d,e,f,g,h)8个字母组成，每个字母在电文中出现的次数分别为(7,19,2,6,32,3,21,10)，试解答下列问题： (1) 画出出huffman树；10002c3f511G287a1732e606d19b21

23、g4010h (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=2616.17 写出按层次遍历二叉树的算法。思路：用队列存储结构，并用递归方法Status LevelOrderTraverse(BitTree T,Status (*Visit)(TElemType e)/层序遍历二叉树InitQueue(Q); /初始化队列if(!T) return Error;

24、/空树，直接返回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);/whilereturn Ok;/LevelOrderTraverse6.19 写出判断两棵给定二叉树是否相似的算法。(注：两棵二叉树B1和B2相似是指：B1和B2皆空，或者皆不空且B1的左、右子树和B2的左、右子树分别相似。)思路：采用递归进行比较判断bool BiTreeSimilar (Bi

25、Tree 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 CountLeaves(Tree T，int &num)/num传递的初值为0 if(T-next

26、sibling!=Null) num+=CountLeaves (T-nextsibling); if(T-firstchild!=Null) num+=CountLeaves(T- firstchild); else num+=1;/firstchild域为空，则为叶子结点return num;图7-1V5V4V2V3V1V6第七章 图7.1 已知有向图如图7-1所示，请给出该图的 (1)邻接矩阵示意图 (2)邻接表示意图 (3)逆邻接表 (4)所有强连通分量(1) 邻接矩阵（2）邻接表（3）逆邻接表V5V4V2V3V1V6 （4）强连通分量7.2 已知图G的邻接矩阵如图7-2所示。写出该图

27、从顶点1出发的深度优先搜索序列和广度优先搜索序列，并画出相应的深度优先生成树和广度优先生成树。12345678910100000010102001000100030001000100400001000105000001000161100000000700100000018100100001090000101001101000010000图7-2深度优先序列：1 7 3 4 5 6 2 10 9 8深度优先生成树：广度优先序列：1 7 9 3 10 5 4 8 6 2广度优先生成树：9.1若对大小均为n的有序顺序表和无序顺序表分别进行顺序查找，试在下列三种情况下分别讨论两者在等概率时平均查找长度

28、是否相同？（1）查找不成功，即表中没有关键字等于给定的值K的记录；（2）查找成功，且表中只有一个关键字等于给定值K的记录；（3）查找成功，且表中有若干个关键字等于给定值K的记录，要求找出所有这些记录。解：对有序顺序表：1. （将该项看作一项混入原有序列中，问题转变成 n+1个元素序列的成功查找问题）2 3. 将此K项看作一项对无序顺序表：1. n2. 考虑最后一个记录的出现位置9.3 画出对长度为17的有序表进行折半查找的判定树，并分别求其等概率时查找长度和查找失败的ASL。解： 增加虚结点9.4已知如下所示长度为12的表：（Jan，Feb，Mar，Apr，May，Jun，July，Aug，S

29、ept，Oct，Nov，Dec）表中，每一个元素的查找概率分别为：（0.1, 0.25, 0.05, 0.13, 0.01, 0.06, 0.11, 0.07, 0.02, 0.03, 0.1, 0.07）（1）若对该表进行顺序查找，求查找成功的平均查找长度；（2）画出从初态为空开始，依次插入结点，生成的二叉排序树；（3）计算该二叉排序树查找成功的平均查找长度；（4）将二叉排序树中的结点Mar删除，画出经过删除处理后的二叉排序树。解：（1） （2）与初始输入序列有关 （3） （4）找到Mar的直接后继，将Mar的左子树移动到最左孩子的左孩子处，然后用直接后继取代当前结点。9.5 已知关键字序列

30、10，25，33，19，06，49，37，76，60，哈希地址空间为0-10，哈希函数为H(key)=Key%11，求：（1）用开放定址线性探测法处理冲突，构造哈希表HT1，分别计算在等概率情况下HT1查找成功和查找失败的ASL；（2）用开放定址二次探测法处理冲突，构造哈希表HT2，计算在等概率下HT2查找成功的ASL；（3）用拉链法解决冲突，构造哈希表HT3，计算HT3在等概率情况查找成功的ASL。解：这9个数的hash值为： 10,3,0,8,6,5,4,10,5冲突有2个。012345678910337625374906601910 遇到空还没有，则算失败。（2）d=0,1,-1,4,-40123456789103360254906197610(3)