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

-数据结构(C语言版)习题解答-第 18 页1.3 设n是正整数。试写出下列程序段中用记号“”标注的语句的频度： (2)i=1; k=0;do k+=10*i;i+;while(i<=n-1)当n=1时，执行1；当n>=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<j) i+; else j+;执行n次；(5)x=n; y=0; /n是不小于1的常数while(x>=(y+1)*(y+1)y+;执行向下取整)(6)x=91; y=100;while ( y>0 )if(x>100) x-=10; y-; else x+ ; If语句执行100次(7)for( i=0; i<n; i+)for( j=i; j<n; j+)for( k=j; k<n; k+)x+=2;过程：第二章2.3已知顺序表La中数据元素按非递减有序排列。试写一个算法，将元素x插到La的合适位置上，保持该表的有序性。思路：先判断线性表的存储空间是否满，若满返回Error；否则从后向前先移动数据，找到合适的位置插入。Status Insert_SqList(SqList &La,int x)/把x 插入递增有序表La 中if(La.length=La.listsize) return ERROR;for(i=La.length-1;La.elemi>x&&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;i<j;i+,j-) /A.elemi<->A.elemj; 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(i<length)for(j=i+1;j<length; j+)if(L.Elemj=L.Elemi)/for(k=j; k<length-1; k+)L.Elemk=L.Elemk+1;length-;j-;/移动元素后，由于少了一个元素，因此要减1/end if If(L.Elemj>L.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变化较快while(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; /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的前驱指针qb=pb;/ 保存pb的前驱指针pa=pa->next;pb=pb->next;A->next=NULL;C=A;while(pa&&pb)if(pa->data<pb->data)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;pb=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->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;L->pre=p; /头结点的pre指向a2结点/Reform第三章 栈和队列3.6 试写一个算法，识别依次读入的一个以为结束符的字符序列是否为形如“序列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 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=' ) ' | *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.遇到数字直接发送 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 suffix,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+;/end whilewhile(!IsEmpty(s) suffixi+=pop(s); suffixi=0;3.10 假设以带头结点的单循环链表表示队列，只设一个尾指针指向队尾元素，不设头指针。试编写相应的队列初始化、入队和出队算法（在出队算法中要传回队头元素的值）要点：定义好数据类型，带头结点的单循环链表，只有尾指针，注意删除元素时只有一个元素的特殊性typedef int DataTypestruct NodeDataType data;Node * next;struct CycleListQueueNode * 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,DataType &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)/带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=Q.basehead;Q.length-;return OK；/DeCyQueue3.12 试写一个算法：判别读入的一个以为结束符的字符序列是否是“回文”（所谓“回文”是指正读和反读都相同的字符序列，如“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中：0123456k4m-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 已知稀疏矩阵A4×5如下：(1)用三元组表作为存储结构，绘出相应的三元组表示意图；(2)用十字链表作为存储结构，绘出相应的十字链表示意图。(1)三元组表：ijv121155212223246424457(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对应的二叉树：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树；10002c3f511G287a1732e606d19b21g4010h (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;/空树，直接返回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 (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 CountLeaves(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;图7-1V5V4V2V3V1V6第七章 图7.1 已知有向图如图7-1所示，请给出该图的 (1)邻接矩阵示意图 (2)邻接表示意图 (3)逆邻接表 (4)所有强连通分量(1) 邻接矩阵（2）邻接表（3）逆邻接表V5V4V2V3V1V6 （4）强连通分量7.2 已知图G的邻接矩阵如图7-2所示。写出该图从顶点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的有序顺序表和无序顺序表分别进行顺序查找，试在下列三种情况下分别讨论两者在等概率时平均查找长度是否相同？（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，Sept，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 已知关键字序列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)