数据结构(C语言版)习题解答参考范本

精品精品感谢下载载感谢下载载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+j {△ if(i<j)i++;elsej++;}执行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++)过程：

n1ni0ji

△ x+=2;(n j) n(n 1)(n 2)6第二章2.3已知顺序表La中数据元素按非递减有序排列。试写一个算法，将元素 x到La的合适位置上，保持该表的有序性。思路：先判断线性表的存储空间是否满，若满返回 Error；否则从后向前先移数据，找到合适的位置插入。StatusInsert_SqList(SqList&La,intx)// 把x插入递增有序表 La 中{if(La.length==La.listsize)returnERROR;for(i=La.length-1;La.elem[i]>x&&i>=0;i--)La.elem[i+1]=La.elem[i];La.elem[i+1]=x;La.length++;returnOK;}//Insert_SqList2.5试写一个算法，实现顺序表的就地逆置，即在原表的存储空间将线性表（,a2,...,an-1,an）(an,an-1,...,a2,a1)//思路就是两个指示变量 i，j同时分别从顺序表的开始和结尾处相向改voidreverse(SqList&A)// 顺序表的就地逆置{ElemTypep;for(i=1,j=A.length;i<j;i++,j--){//A.elem[i]<->A.elem[j];p=A.elem[i];A.elem[i[=A.elem[j];A.elem[j]=p;}}//reverse已知线性表L采用顺序存储结构存放，对两种不同情况分别写出算法，删除L中多余的元素，使得L中没有重复元素：（1）L中数据元素无序排列；(2)L数据元素非递减有序排列。voidDelete_SameElem(SqLink&L,intL.length){//内层循环移动参数，中层循环寻找相同元，外层循环遍历整个表inti=0;intj=i+1;intlength=L.length;while(i<length){for(j=i+1;j<length;j++){if(L.Elem[j]==L.Elem[i]){//for(k=j;k<length-1;k++){L.Elem[k]=L.Elem[k+1];length--;j--;// 移动元素后，由于少了一个元素，因此要减 1}}//endifIf(L.Elem[j]>L.Elem[i])break;// 第二小问添加此句}//endfor}//endwhile}//endfunctoion已知线性表L采用链式结构存放。对两种不同情况分别写出算法，删除L值相同的多余元素，使得L中没有重复元素：(1)L中数据元素无序排列；(2)L中数据元素非递减有序排列。（1）L中数据元素无序排列；思路：由于是无序排列，需要线性表中每个元素都要相互进行比较。StatusListDelete （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;// 开始后一结点的寻找returnOK ；}//ListDelete(2)L中数据元素非递减有序排列。思路：由于是有序的，遍历一次线性表就行了StatusListDelete(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;}//ifelse{while(p->data==q->data)q=q->next;// 多个连续的重复值}//elsep->next=q;p=q;q=p->next;// 删除值重复的结点，并修改相应的指针returnOK ；}//ListDelete设有两个非递减有序的单链表 A,B请写出算法，将A和B就地归并成一按元素值非递增有序的单链表。// 将合并逆置后的结果放在 C表中，并删除 B表StatusListMergeOppose_L(LinkList&A,LinkList&B,LinkList&C){LinkListpa,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;}else{qb=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);returnOK;}2.13 设以带头结点的双向循环链表表示的线性表 L=(a1,a2,a3)。试写一间复杂度为O(n)的算法，将L改造为L=(a1,a3,a2)。voidReform(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// 头结点的prea2结点}//Reform第三章 栈和队列试写一个算法，识别依次读入的一个以 @为结束符的字符序列是否为形如“序列1&序列模式的字符序列。其中序列1和序列2中都不包含字符‘&且序列2是序列1的逆序。例如“a ”是属于该模式的字符序列，“13&31算法：intSeqReverse()// 判断输入的字符串中 '&'前和'&'后部分是否为逆串 ,是则返回1,否则返回0{InitStack(s);while((e=getchar())!='&'){= @)return/ 不允许在&@’push(s,e);}//序列1输入完毕while((e=getchar())!='@'){if(StackEmpty(s))return0;pop(s,c);if(e!=c)return0;}if(!StackEmpty(s))return0;// 1return1;}//IsReverse假设一个算术表达式中可以包含三种符号：圆括号“ (”和“)、方括号“和“]、花括号“{”和“，且这三种括号可按任意次序嵌套使用。编写判别给定表达式中所含的括号是否正确配对的算法 （已知表达式已存入数据元素为字的顺序表中。算法：StatusBracketTest(char*str)// 判别表达式中三种括号是否匹配{InitStack(s);for(p=str;*p;p++){if(*p=='('||*p=='['||*p=='{')push(s,*p);elseif(*p==')'||*p==']'||*p=='}'){if(StackEmpty(s))returnERROR;pop(s,c);if(*p==')'&&c!='(')returnERROR;if(*p==']'&&c!='[')if(*p=='}'&&c!='{')returnERROR;returnERROR;//必须与当前栈顶括号匹配}//if}//forif(!StackEmpty(s))returnERROR;//进栈的符号还有剩余， ErrorreturnOK;}//BracketTest设表达式由单字母变量、双目运算符和圆括号组成（如 试写一个算法，将一个书写正确的表达式转换为逆波兰式。思路：遇到数字直接发送 .遇到(直接入栈 .遇到)则将栈内元素发送直至遇到 (.栈则直接入栈 5.栈非空时若优先级大于栈内则入栈，否则栈内元素出栈intRankOfOperator(charc){switch(c){case'#':return-1;case'(':return0;case'+':case'-':return1;case'*':case'/':case')':return2;}}intPrecede(charc,charch){returnRankOfOperator(c)>RankOfOperator(ch);}voidExpressionTOPolandStyle(charsuffix[],char*exp){Stacks;InitStack(s,100);inti=0;charc;while(*exp){if(isdigital(*exp))suffix[i++]=*exp;else{switch(*exp){case'(':push(s,'(');case')':while((c=pops(s))!='(')suffix[i++]=c;break;default:if(IsEmpty(s))push(s,*exp);else{suffix[i++]=pop(s);exp--;//与后面的exp++相抵消，使得栈内优先级大于等于栈外的都出栈}}//endswitch}//endexp++;}//endwhilewhile(!IsEmpty(s))suffix[i++]=pop(s);suffix[i]=0;}假设以带头结点的单循环链表表示队列，只设一个尾指针指向队尾元素，不设头指针。试编写相应的队列初始化、 入队和出队算法（在出队算法中要传队头元素的值）要点：定义好数据类型，带头结点的单循环链表，只有尾指针，注意删除元素时只有一个元素的特殊性typedefintDataTypestructNode{DataTypedata;Node*next;};structCycleListQueue{Node*tail;};voidInitCycleListQueue(CycleListQueue&L){L.tail=newNode;L.tail->next=L.tail;}voidEnterQueue(CycleListQueue&L,DataTypevalue){Node*p=newNode;p->data=value;p->next=L.tail->next;L.tail->next=p;L.tail=p;}voidDeparQueue(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;deletep;returnd;}}rearlength分别指示队尾元素和队列长度。试给出此循环队列的队满条件，并写出相应的入队和出队算法（在出队算法中要传递回队头元素的值）此循环队列的队满条件： Q.length==MAXQSIZE;入队算法：StatusEnCyQueue(CyQueue&Q,intx)// 带length 域的循环队列入队算法{if(Q.length==MAXSIZE) returnOVERFLOW;Q.rear=(Q.rear+1)%MAXSIZE;Q.base[Q.rear]=x;//rear 指向队尾元素Q.length++;returnOK;}//EnCyQueue出队算法：StatusDeCyQueue(CyQueue&Q,int&x)// 带length 域的循环队列出队算法，用 x返回队元素的值{if(Q.length==0) returnError;// 空队列，错误head=(Q.rear-Q.length+1)%MAXSIZE;//head 指向队x=Q.base[head];Q.length--;returnOK }//DeCyQueue试写一个算法：判别读入的一个以‘ @’为结束符的字符序列是否是“回文所谓“回文”是指正读和反读都相同的字符序列，如“ xxyzyxx”是回文而“abcab”则不是回文）。StatusTest()// 判别输入的字符串是否回文序列 是则返回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) returnERROR;}returnOK;}//Test第五章 多维数组设有一个准对角矩阵a21

a12a22

a33a43

a34a44

......

......

a2m

1,2m

a2m

1,2ma2m,2m1 a2m,2m按以下方式存于一维数组 B[4m]中：0 1 2 3 4 5 6 k 4m-2 4m-1a11 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)+j-i=i+j-2; 当i为偶数时，k=2i-(i-j)-1=i+j-1k=已知稀疏矩阵A4×5如下：0101005230600000004007用三元组表作为存储结构，绘出相应的三元组表示意图；用十字链表作为存储结构，绘出相应的十字链表示意图。三元组表：i j v1 2 11 5 52 1 22 2 32 4 6感谢下载载精品4 2 44 5 7十字链表<1 2 1

1 5 5<2 1 2 2 2 3 2 4 6< < <<4 2 4 4 5 7< < <第六章 数和二叉树6.5 已知一棵度为 k的树中有n1个度为1的结点，n2个度为2的结点，nk个度为k的结点，问该树中有多少个叶子结点？设叶子结点有x个，则树的结点总数为n1+n2+ 同时除了根结点外，每个结点都指向一个结点，所有从这个角度考虑树的结点总数为：n1+2?n2+⋯k?nk+1;n1+n2+ n1+2 +,可得x=

k(i 1)?ni 1i2已知一棵树如图6-1历序列和后根遍历序列。感谢下载载精品AB C DE F G HI J K图6-1先根遍历：ABCEIJFGKHD后根遍历：BIJEFKGHCDA对应的二叉树：感谢下载载精品ABCE DIFJGK H6-2所示的森林转化为对应的二叉树。I K LJ M ND E OF GH图6-2树对应的二叉树感谢下载载精品I LKJ MNDOEF 6-2H G森林对应的二叉树：AIBJCKDLEMFH G NO感谢下载载精品精品感谢下载载感谢下载载6.11已知某二叉树的中序序列为 DCBGEAHFIJK，后序序列为DCEGBFHKJIA。请画出该二叉树。AB IC G H JKE F6.14 假设某个电文由(a,b,c,d,e,f,g,h)8 个字母组成，每个字母在电文中出现次数分别为(7,19,2,6,32,3,21,10) ，试解答下列问题：画出出huffman 树；100060284019b 21g

11G52c 3f

176d 7a

10h

32e写出每个字母的 huffman 编码；a:1010b:00c:10000d:1001e:11f:10001g:01h:1011在对该电文进行最优二进制编码处理后，电文的二进制位数。4*7+2*19+5*2+4*6+2*32+5*3+2*21+4*10=2616.17 写出按层次遍历二叉树的算法。StatusLevelOrderTraverse(BitTreeT,Status(*Visit)(TElemTypee)// 层序遍历二叉树{InitQueue(Q);// 初始化队列if(!T) returnError;// 空树，直接返EnQueue(Q,T);// 根结点入队BiTNode*p;while(!QueueEmpty(Q)){DeQueue(Q,p);Visit(p->data);if(p->lchild) EnQueue(Q,p->lchild);if(p->rchild) }//whilereturnOk;}//LevelOrderTraverse6.19 写出判断两棵给定二叉树是否相似的算法。(注：两棵二叉树 B1和B2相似是指：B1和B2皆空，或者皆不空且 B1的左右子树和B2的左、右子树分别相似。 )思路：采用递归进行比较判断boolBiTreeSimilar(BiTreeT1,BiTreeT2){if(T1==Null&&T2==Null)return1;elseif(T1==Null||T2==Null)return0;elsereturn(BiTreeSilimar(T1->lchild,T2->lchild)&&BiTreeSimilar(T1->rchild,T2->rchild));}6.21 写出统计树中叶子结点个数的算法，树用孩子兄弟链表表示。思路：在孩子兄弟链表中，若结点的 firstchild 为Null，则为叶子结点；采用递归方法。intCountLeaves(TreeT ，int&num)//num 传递的初值为 0{if(T->nextsibling!=Null)num+=CountLeaves(T->nextsibling);if(T->firstchild!=Null)num+=CountLeaves(T->firstchild);elsenum+=1;//firstchild 域为空，则为叶子结点returnnum;}V1V5V1V5V6V2V4V37-1已知有向图如图 7-1所示请给出该图的邻接矩阵示意图邻接表示意图逆邻接表所有强连通分量(1) 邻接矩阵000000100100010001001011100000110010（2）邻接表0 v1 <1 v2 3 0 <2 v3 5 1 <v4v5v6

5 4 2 <0 <4 1 0 <（3）逆邻接表0 v1 <v2v3v4v5v6

5 4 1 <5 2 <3 <1 <5 3 <3 2 <（4）强连通分量

V1 V5V6V2 V3已知图G的邻接矩阵如图 7-2所示。写出该图从顶点 1出发的深度优先索序列和广度优先搜索序列，并画出相应的深度优先生成树和广度优先生成树。112345678910100000010102001000100030001000100400001000105000001000161100000000700100000018100100001090000101001101000010000图7-2深度优先序列： 173456210981734 85 96 102深度优先生成树：广度优先序列： 1793105486217 93 10 54 8 62广度优先生成树：9.1若对大小均为 n的有序顺序表和无序顺序表分别进行顺序查找， 试在下列三种情况下别讨论两者在等概率时平均查找长度是否相同？（1）查找不成功，即表中没有关键字等于给定的值 K的记录；（2）查找成功，且表中只有一个关键字等于给定值 K的记录；（3）查找成功，且表中有若干个关键字等于给定值 K的记录，要求找出所有这些记录解：对有序顺序表：1

n+21. n+1[1+2+...+(n+1)]= 2

（将该项看作一项混入原有序列中，问题转变成 n+1个元素序列的成功查找问题）n2．1[1+2+...+n

n+123. 1

+2+...+n

(k-

n-1)]=

k+2

将此K项看作一项n-(k-1) 2对无序顺序表：1. n1

n+12. n[1+2+...+= 2n3.

i=(n+k)(n-k+1)g 1

n+k=

考虑最后一个记录的出现位置i=k

2 n

k2画出对长度为 17的有序表进行折半查找的判定树，并分别求其等概率时查找长度和找失败的ASL。1 59解：ASL=171 2?2 4 4?8 5?2) 171 76ASL18(47 ?2 47 52) 18 增加虚结点94 132 6 11 151 3 5 7 10 12 14 168 17已知如下所示长度为 12的表Jan，Feb，Apr，May，Jun，July，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）

ASL=1 0.25?2 ...+0.07?12 5.43（2）与初始输入序列有关JanJanFebMarAprJunMayAugJulySepDecOctNov（3）ASL=1 2 ...+0.07?5 3.2（4）找到Mar 的直接后继，将Mar 的左子树移动到最左孩子的左孩子处，然后用直后继取代当前结点。JanFeb MayApr

Jun

SepAug

July

OctDec

Nov9.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

17 3?1 3?139 9=(F

+F(1)+...+F(10))/11=3811

遇到空还没有，则算失败。（2）d=0,1,-1,4,-4 ⋯⋯01234567891033602549061976101 5ASL

97 1 5?3(3)033123254375496060678199101076ASL

17 2?119 9精品精品感谢下载载感谢下载载1 总则1.1 为了加强公司的环境卫生管理，创造一个整洁、文明、温馨的购物、办公环境，根据《公共场所卫生管理条例》的要求，特制定本制度。1.2 集团公司的卫生管理部门设在企管部，并负责将集团公司的卫生区域详细划分到各部室，各分公司所辖区域卫生由分公司客服部负责划分，确保无遗漏。2 卫生标准2.1 室内卫生标准2.1.1 地面、墙面：无灰尘、无纸屑、无痰迹、无泡泡糖等粘合物、无积水，墙角无灰吊、无蜘蛛网。2.1.2 门、窗、玻璃、镜子、柱子、电梯、楼梯、灯具等，做到明亮、无灰尘、无污迹、无粘合物，特别是玻璃，要求两面明亮。2.1.3 柜台、货架：清洁干净，货架、柜台底层及周围无乱堆乱放现象、无灰尘、无粘合物，货架顶部、背部和底部干净，不存放杂物和私人物品。2.1.4 购物车（筐）、直接接触食品的售货工具（包括刀、叉等）：做到内外洁净，无污垢和粘合物等。购物车（筐）要求每天营业前简单清理，周五全面清理消毒；售货工具要求每天消毒，并做好记录。2.1.5 商品及包装：商品及外包装清洁无灰尘（外包装破损的或破旧的不得陈列）。2.1.6 收款台、服务台、办公橱、存包柜：保持清洁、无灰尘，台面和侧面无灰尘、无灰吊和蜘蛛网。桌面上不得乱贴、乱画、乱堆放物品，用具摆放有序且干净，除当班的购物小票收款联外，其它单据不得存放在桌面上。2.1.7 垃圾桶：桶内外干净，要求营业时间随时清理，不得溢出，每天下班前彻底清理，不得留有垃圾过夜。2.1.8 窗帘：定期进行清理，要求干净、无污渍。2.1.9 吊饰：屋顶的吊饰要求无灰尘、无蜘蛛网，短期内不适用的吊饰及时清理彻底。2.1.10 内、外仓库：半年彻底清理一次，无垃圾、无积尘、无蜘蛛网等。2.1.11 室内其他附属物及工作用具均以整洁为准，要求无灰尘、无粘合物等污垢。2.2 室外卫生标准2.2.1 门前卫生：地面每天班前清理，平时每一小时清理一次，每周四营业结束后有条件的用水冲洗地面（冬季可根据情况适当清理），墙面干净且无乱贴乱画。2.2.2 院落卫生：院内地面卫生全天保洁，果皮箱、消防器械、护栏及配电箱等设施每周清理干净。垃圾池周边卫生清理彻底，不得有垃圾溢出。2.2.3 绿化区卫生：做到无杂物、无纸屑、无塑料袋等垃圾。3 清理程序3.1 室内和门前院落等区域卫生：每天营业前提前10分钟把所管辖区域内卫生清理完毕，营业期间随时保洁。下班后5-10分钟清理桌面及卫生区域。3.2 绿化区卫生：每周彻底清理一遍，随时保持清洁无垃圾。4 管理考核4.1 实行百分制考核，每月一次（四个分公司由客服部分别考核、集团职4.2 集团坚持定期检查和不定期抽查的方式监督各分公司、部门的卫生工作。每周五为卫生检查日，集团检查结果考核至各分公司，各分公司客服部的检查结果考核至各部门。4.3 集团公司每年不定期组织卫生大检查活动，活动期间的考核以通知为准。5 监督考核部门：企管部、分公司客服部。!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+j {△ if(i<j)i++;elsej++;}执行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++)过程：

n1ni0ji

△ x+=2;(n j) n(n 1)(n 2)6第二章2.3已知顺序表La中数据元素按非递减有序排列。试写一个算法，将元素 x到La的合适位置上，保持该表的有序性。思路：先判断线性表的存储空间是否满，若满返回 Error；否则从后向前先移数据，找到合适的位置插入。StatusInsert_SqList(SqList&La,intx)// 把x插入递增有序表 La 中{if(La.length==La.listsize)returnERROR;for(i=La.length-1;La.elem[i]>x&&i>=0;i--)La.elem[i+1]=La.elem[i];La.elem[i+1]=x;La.length++;returnOK;}//Insert_SqList2.5试写一个算法，实现顺序表的就地逆置，即在原表的存储空间将线性表（,a2,...,an-1,an）(an,an-1,...,a2,a1)//思路就是两个指示变量 i，j同时分别从顺序表的开始和结尾处相向改voidreverse(SqList&A)// 顺序表的就地逆置{ElemTypep;for(i=1,j=A.length;i<j;i++,j--){//A.elem[i]<->A.elem[j];p=A.elem[i];A.elem[i[=A.elem[j];A.elem[j]=p;}}//reverse已知线性表L采用顺序存储结构存放，对两种不同情况分别写出算法，删除L中多余的元素，使得L中没有重复元素：（1）L中数据元素无序排列；(2)L数据元素非递减有序排列。voidDelete_SameElem(SqLink&L,intL.length){//内层循环移动参数，中层循环寻找相同元，外层循环遍历整个表inti=0;intj=i+1;intlength=L.length;while(i<length){for(j=i+1;j<length;j++){if(L.Elem[j]==L.Elem[i]){//for(k=j;k<length-1;k++){L.Elem[k]=L.Elem[k+1];length--;j--;// 移动元素后，由于少了一个元素，因此要减 1}}//endifIf(L.Elem[j]>L.Elem[i])break;// 第二小问添加此句}//endfor}//endwhile}//endfunctoion已知线性表L采用链式结构存放。对两种不同情况分别写出算法，删除L值相同的多余元素，使得L中没有重复元素：(1)L中数据元素无序排列；(2)L中数据元素非递减有序排列。（1）L中数据元素无序排列；思路：由于是无序排列，需要线性表中每个元素都要相互进行比较。StatusListDelete （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;// 开始后一结点的寻找returnOK ；}//ListDelete(2)L中数据元素非递减有序排列。思路：由于是有序的，遍历一次线性表就行了StatusListDelete(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;}//ifelse{while(p->data==q->data)q=q->next;// 多个连续的重复值}//elsep->next=q;p=q;q=p->next;// 删除值重复的结点，并修改相应的指针returnOK ；}//ListDelete设有两个非递减有序的单链表 A,B请写出算法，将A和B就地归并成一按元素值非递增有序的单链表。// 将合并逆置后的结果放在 C表中，并删除 B表StatusListMergeOppose_L(LinkList&A,LinkList&B,LinkList&C){LinkListpa,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;}else{qb=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);returnOK;}2.13 设以带头结点的双向循环链表表示的线性表 L=(a1,a2,a3)。试写一间复杂度为O(n)的算法，将L改造为L=(a1,a3,a2)。voidReform(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// 头结点的prea2结点}//Reform第三章 栈和队列试写一个算法，识别依次读入的一个以 @为结束符的字符序列是否为形如“序列1&序列模式的字符序列。其中序列1和序列2中都不包含字符‘&且序列2是序列1的逆序。例如“a ”是属于该模式的字符序列，“13&31算法：intSeqReverse()// 判断输入的字符串中 '&'前和'&'后部分是否为逆串 ,是则返回1,否则返回0{InitStack(s);while((e=getchar())!='&'){= @)return/ 不允许在&@’push(s,e);}//序列1输入完毕while((e=getchar())!='@'){if(StackEmpty(s))return0;pop(s,c);if(e!=c)return0;}if(!StackEmpty(s))return0;// 1return1;}//IsReverse假设一个算术表达式中可以包含三种符号：圆括号“ (”和“)、方括号“和“]、花括号“{”和“，且这三种括号可按任意次序嵌套使用。编写判别给定表达式中所含的括号是否正确配对的算法 （已知表达式已存入数据元素为字的顺序表中。算法：StatusBracketTest(char*str)// 判别表达式中三种括号是否匹配{InitStack(s);for(p=str;*p;p++){if(*p=='('||*p=='['||*p=='{')push(s,*p);elseif(*p==')'||*p==']'||*p=='}'){if(StackEmpty(s))returnERROR;pop(s,c);if(*p==')'&&c!='(')returnERROR;if(*p==']'&&c!='[')if(*p=='}'&&c!='{')returnERROR;returnERROR;//必须与当前栈顶括号匹配}//if}//forif(!StackEmpty(s))returnERROR;//进栈的符号还有剩余， ErrorreturnOK;}//BracketTest设表达式由单字母变量、双目运算符和圆括号组成（如 试写一个算法，将一个书写正确的表达式转换为逆波兰式。思路：遇到数字直接发送 .遇到(直接入栈 .遇到)则将栈内元素发送直至遇到 (.栈则直接入栈 5.栈非空时若优先级大于栈内则入栈，否则栈内元素出栈intRankOfOperator(charc){switch(c){case'#':return-1;case'(':return0;case'+':case'-':return1;case'*':case'/':case')':return2;}}intPrecede(charc,charch){returnRankOfOperator(c)>RankOfOperator(ch);}voidExpressionTOPolandStyle(charsuffix[],char*exp){Stacks;InitStack(s,100);inti=0;charc;while(*exp){if(isdigital(*exp))suffix[i++]=*exp;else{switch(*exp){case'(':push(s,'(');case')':while((c=pops(s))!='(')suffix[i++]=c;break;default:if(IsEmpty(s))push(s,*exp);else{suffix[i++]=pop(s);exp--;//与后面的exp++相抵消，使得栈内优先级大于等于栈外的都出栈}}//endswitch}//endexp++;}//endwhilewhile(!IsEmpty(s))suffix[i++]=pop(s);suffix[i]=0;}假设以带头结点的单循环链表表示队列，只设一个尾指针指向队尾元素，不设头指针。试编写相应的队列初始化、 入队和出队算法（在出队算法中要传队头元素的值）要点：定义好数据类型，带头结点的单循环链表，只有尾指针，注意删除元素时只有一个元素的特殊性typedefintDataTypestructNode{DataTypedata;Node*next;};structCycleListQueue{Node*tail;};voidInitCycleListQueue(CycleListQueue&L){L.tail=newNode;L.tail->next=L.tail;}voidEnterQueue(CycleListQueue&L,DataTypevalue){Node*p=newNode;p->data=value;p->next=L.tail->next;L.tail->next=p;L.tail=p;}voidDeparQueue(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;deletep;returnd;}}rearlength分别指示队尾元素和队列长度。试给出此循环队列的队满条件，并写出相应的入队和出队算法（在出队算法中要传递回队头元素的值）此循环队列的队满条件： Q.length==MAXQSIZE;入队算法：StatusEnCyQueue(CyQueue&Q,intx)// 带length 域的循环队列入队算法{if(Q.length==MAXSIZE) returnOVERFLOW;Q.rear=(Q.rear+1)%MAXSIZE;Q.base[Q.rear]=x;//rear 指向队尾元素Q.length++;returnOK;}//EnCyQueue出队算法：StatusDeCyQueue(CyQueue&Q,int&x)// 带length 域的循环队列出队算法，用 x返回队元素的值{if(Q.length==0) returnError;// 空队列，错误head=(Q.rear-Q.length+1)%MAXSIZE;//head 指向队x=Q.base[head];Q.length--;returnOK }//DeCyQueue试写一个算法：判别读入的一个以‘ @’为结束符的字符序列是否是“回文所谓“回文”是指正读和反读都相同的字符序列，如“ xxyzyxx”是回文而“abcab”则不是回文）。StatusTest()// 判别输入的字符串是否回文序列 是则返回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) returnERROR;}returnOK;}//Test第五章 多维数组设有一个准对角矩阵a21

a12a22

a33a43

a34a44

......

......

a2m

1,2m

a2m

1,2ma2m,2m1 a2m,2m按以下方式存于一维数组 B[4m]中：0 1 2 3 4 5 6 k 4m-2 4m-1a11 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)+j-i=i+j-2; 当i为偶数时，k=2i-(i-j)-1=i+j-1k=已知稀疏矩阵A4×5如下：0101005230600000004007用三元组表作为存储结构，绘出相应的三元组表示意图；用十字链表作为存储结构，绘出相应的十字链表示意图。三元组表：i j v1 2 11 5 52 1 22 2 32 4 6感谢下载载精品4 2 44 5 7十字链表<1 2 1

1 5 5<2 1 2 2 2 3 2 4 6< < <<4 2 4 4 5 7< < <第六章 数和二叉树6.5 已知一棵度为 k的树中有n1个度为1的结点，n2个度为2的结点，nk个度为k的结点，问该树中有多少个叶子结点？设叶子结点有x个，则树的结点总数为n1+n2+ 同时除了根结点外，每个结点都指向一个结点，所有从这个角度考虑树的结点总数为：n1+2?n2+⋯k?nk+1;n1+n2+ n1+2 +,可得x=

k(i 1)?ni 1i2已知一棵树如图6-1历序列和后根遍历序列。感谢下载载精品AB C DE F G HI J K图6-1先根遍历：ABCEIJFGKHD后根遍历：BIJEFKGHCDA对应的二叉树：感谢下载载精品ABCE DIFJGK H6-2所示的森林转化为对应的二叉树。I K LJ M ND E OF GH图6-2树对应的二叉树感谢下载载精品I LKJ MNDOEF 6-2H G森林对应的二叉树：AIBJCKDLEMFH G NO感谢下载载精品精品感谢下载载感谢下载载6.11已知某二叉树的中序序列为 DCBGEAHFIJK，后序序列为DCEGBFHKJIA。请画出该二叉树。AB IC G H JKE F6.14 假设某个电文由(a,b,c,d,e,f,g,h)8 个字母组成，每个字母在电文中出现次数分别为(7,19,2,6,32,3,21,10) ，试解答下列问题：画出出huffman 树；100060284019b 21g

11G52c 3f

176d 7a

10h

32e写出每个字母的 huffman 编码；a:1010b:00c:10000d:1001e:11f:10001g:01h:1011在对该电文进行最优二进制编码处理后，电文的二进制位数。4*7+2*19+5*2+4*6+2*32+5*3+2*21+4*10=2616.17 写出按层次遍历二叉树的算法。StatusLevelOrderTraverse(BitTreeT,Status(*Visit)(TElemTypee)// 层序遍历二叉树{InitQueue(Q);// 初始化队列if(!T) returnError;// 空树，直接返EnQueue(Q,T);// 根结点入队BiTNode*p;while(!QueueEmpty(Q)){DeQueue(Q,p);Visit(p->data);if(p->lchild) EnQueue(Q,p->lchild);if(p->rchild) }//whilereturnOk;}//LevelOrderTraverse6.19 写出判断两棵给定二叉树是否相似的算法。(注：两棵二叉树 B1和B2相似是指：B1和B2皆空，或者皆不空且 B1的左右子树和B2的左、右子树分别相似。 )思路：采用递归进行比较判断boolBiTreeSimilar(BiTreeT1,BiTreeT2){if(T1==Null&&T2==Null)return1;elseif(T1==Null||T2==Null)return0;elsereturn(BiTreeSilimar(T1->lchild,T2->lchild)&&BiTreeSimilar(T1->rchild,T2->rchild));}6.21 写出统计树中叶子结点个数的算法，树用孩子兄弟链表表示。思路：在孩子兄弟链表中，若结点的 firstchild 为Null，则为叶子结点；采用递归方法。intCountLeaves(TreeT ，int&num)//num 传递的初值为 0{if(T->nextsibling!=Null)num+=CountLeaves(T->nextsibling);if(T->firstchild!=Null)num+=CountLeaves(T->firstchild);elsenum+=1;//firstchild 域为空，则为叶子结点returnnum;}V1V5V1V5V6V2V4V37-1已知有向图如图 7-1所示请给出该图的邻接矩阵示意图邻接表示意图逆邻接表所有强连通分量(1) 邻接矩阵000000100100010001001011100000110010（2）邻接表0 v1 <1 v2 3 0 <2 v3 5 1