数据结构练习题答案

数据结构练习题答案（仅供参考，如有问题讲解时再更正）第一章绪论一、单选题1.C2.D3.B二、填空题1.集合结构、线性结构、树型结构、图形结构2.1:1、1:N、M:N3.O(n)、O(m*n)4.n、n(n+1)/2、O(n2)5.O(n)第二章线性表一、单选题1.B2.A3.C4.B5.D6.C二、填空题1.数据、指针2.(38,56,25,60,42,74)3.O(n)、O(1)4.O(1)、O(n)5.i-1、i+16.p-next、a[p].next7.表头8.前驱、后继9.表尾、表头10．HL-next==NULL、HL-next==HL三、应用题1．#defineElemTypeint#defineMaxsize100Typedefstruct{ElemType*list;intsize;}List;(1)ElemTypeDMValue(List&L){ElemTypex;x=L.list[0];//x存放最小元素intk=0,i;//k存放最小元素的下标if(ListEmpty(L))//判断是否为空线性表{printf(”ListisEmpty!”);exit(1);}for(i=1;iL.size;i++)//查找最小元素if(L.list[i]x){x=L.list[i];k=i;}L.list[k]=L.list[L.size-1];//最后一个元素填补最小元素位置L.size--;//线性表长度减1returnx;//返回最小元素}(2)ElemTypeDelete(List&L,inti){ElemTypex;intj;if(i1||iL.size){//判断i的合法性printf(”Indexisoutrange!”);exit(1);}x=L.list[i-1];//保存被删除元素for(j=i-1;jL.size-1;j++)//元素向前移动L.list[j]=L.list[j+1];L.size--;//长度减1returnx;//返回被删元素}(3)voidInsert(List&L,inti,ElemTypex){intj;if(i1||iL.size+1){//判断i的合法性printf(”Indexisoutrange!”);exit(1);}if(L.size==MaxSize){//判断线性表满printf(””Listoverflow!”);exit(1);}for(j=L.size-1;j=i-1;j--)//元素后移，产生插入位置L.list[j+1]=L.list[j];L.list[i-1]=x;//元素插入L.size++;//长度加1}(4)voidDelete(List&L,ElemTypex){inti=0;while(iL.size)if(L.list[i]==x){//删除x元素for(intj=i+1;jL.size;j++)L.list[j-1]=L.list[j];L.size--;}elsei++;//寻找下一个x元素的位置}2．TypedefstructLnode{ElemTypedata;LNode*next;}(1)voidDelete(LNode*HL,inti){LNode*ap,*cp;intj=1;if(i1||HL==NULL){//判断i的合法性或空链表printf(”Indexisoutrange!”);exit(1);}ap=NULL;cp=HL;//cp指向当前结点，ap指向其前驱结点while(cp!=NULL)//查找第i个结点{if(j==i)//找到第i个结点break;//cp指向的结点即为第i个结点else{//继续向后寻找ap=cp;cp=cp-next;j++;}}if(cp==NULL){//没有找到第i个结点printf(”Indexisoutrange!”);exit(1);if(ap==NULL)//删除第1个结点（即i=1）HL=HL-nextelseap-next=cp-next;//删除第i个结点free(cp);//释放被删除结点的空间}(2)voidInsert(LNode*HL,ElemTypex){LNodeS=(LNode*)malloc(sizeof*(LNode));//申请一个新结点if(S==NULL){//分配失败printf(”Memoryallocationfail!”);exit(1);}S-data=x;if(HL==NULL||xHL-data){//空表或x小于表头结点，S-next=HL;//作为新表头结点插入HL=S;return;}//查找插入位置LNode*cp=HL-next;//用cp指向当前结点（即待查结点）LNode*ap=HL;//用ap作为指向当前结点的前驱结点指针while(cp!=NULL)if(xcp-data)break;//找到插入位置else{ap=cp;cp=cp-next;}//继续查找插入位置S-next=cp;ap-next=S;//插入新结点}(2)ElemTypeMaxValue(LNode*HL){ElemTypemax;if(HL==NULL){//空表printf(”Linkedlistisempty!”);exit(1);}max=HL-data;LNode*p=HL-next;while(p!=NULL){//寻找最大值if(maxp-data)max=p-data;p=p-next;}returnmax;}(3)intCount(LNode*HL,ElemTypex){intn=0;LNode*p=HL;while(p!=NULL){if(p-data==x)n++;p=p-next;}returnn;}第三章栈和队列一、单选题1.A2.B3.C4.A5.B6.B7.D8.D二、填空题1.队尾、队首2.后进先出(LIFO)、先进先出(FIFO)3.栈顶指针、存储4.栈顶元素、栈顶指针5.front==rear、(rear+1)%QueueMaxSize==front6.–1、StackMaxSize-17.栈空、空队、队列只有一个元素8.新结点的指针域、栈顶指针9.指针域、栈顶指针10.队尾指针、存储11.top==012.p-next=HS、HS=p13.HS=HS-next14.(front==rear)&&(front!=NULL)三、编程题递归算法：longFib(intn){if(n==1||n==2)//终止递归条件return1;elsereturnFib(n-1)+Fib(n-2);}非递归算法：longFib(intn){inta,b,c;//c代表当前项，a和b分别代表当前项前面的第2项和第1项a=b=1;if(n==1||n==2)return1;elsefor(inti=3;i=n;i++){c=a+b;//求当前项a=b;//产生第2项b=c;//产生第1项}returnc;//返回所求的第n项}递归算法的时间复杂度为O(2n)，空间复杂度为O(n)；非递归算法的时间复杂度为O(n)，空间复杂度为O(1)。第六章1树和二叉树一、填空题1.n-12.5、53.64.31、135.10、4、36.2、1、1、67.B、I和J8.69.2i、2i+1、i/210.1611.5、1812.a、f、空结点(即无右孩子结点)13.4、2、314.a[2*i]、a[2*i+1]、a[i/2]15.2i-1、2j+116.A[2*i+1]、a[2*i+2]、a[i/2]17.2n、n-1、n+118.10、519.abcdef、cbaedf、cbefda、abdcef20.abecfhijgd、abcdefghij二、应用题1．voidRequest(intA[],intn,inti){intj;if(in){printf(”编号为%d的结点不存在！”,i);exit(1);}Printf(”当前结点为%d”,A[i]);j=i/2;//下标为j的结点是下标为i结点的双亲if(j0)printf(”双亲：%d”,A[j]);elseprintf(”树根没有双亲结点！”);if(2*in){printf(”左孩子：%d”,A[2*i]);printf(”左孩子：%d”,A[2*i+1]);}elseif(2*i==n){printf(”左孩子：%d”,A[2*i]);printf(”无右孩子！”);}elseprintf(”无孩子！”);}2．voidCount(BTreeNode*BT,int&C1,int&C2){if(BT!=NULL){C1++;//统计所有结点数if(BT-left==NULL&&BT-right==NULL)C2++;//统计叶子结点数Count(BT-left,C1,C2);Count(BT-right,C1,C2);}}3．(1)abecfgkdhilmj(2)abcdefghijklmljihdkgfcebam∧ab∧e∧cf∧∧d∧g∧k∧h∧i∧j∧l∧∧m∧ljihdkgfcebam∧ab∧e∧cf∧∧d∧g∧k∧h∧i∧j∧l∧∧m∧第六章2二叉树的应用一、一、单选题1.C2.B3.D4.C5.A6.D二、填空题1.小于、大于等于2.按升序排列的有序序列3.找到、左子树、右子树4.2i+1、2i+25.最小值、最大值6.堆尾、堆顶、向下三、应用题1.462578623712702946257862371270292.初态堆：(12,15,40,38,26,52,48,64)删除第1个元素后堆：(15,26,40,38,64,52,48)删除第2个元素后堆：(26,38,40,48,64,52)删除第3个元素后堆：(38,48,40,52,64)删除第4个元素后堆：(40,48,64,52)121540522638486415264052643848初态删除第1个元素后263840526448删除第2个元素后删除第3个元素后删除第4个元素后384840645240486452121540522638486415264052643848初态删除第1个元素后263840526448删除第2个元素后删除第3个元素后删除第4个元素后3848406452404864523.哈夫曼树：a:1010b:001c:000d:1011e:100f:11g:01WPL=6*4+4*4+14*3+16*3++12*3+20*2+28*2=262编码平均长度为：(4*2+3*3+2*2)/7=3四、算法设计1．boolFind(BTreeNode*BST,ElemType&item){while(BST!=NULL){if(item==BT-data){//找到item=BST-data;returntrue;}elseif(itemBST-data)BST=BST-left;//转左子树查找elseBST=BST-right;//gecba29211050115662157814584210022101243014162820fd转右子树查找}returnfalse;//没有找到}2．(i-1)/2HBT.heap[i]=HBT.heap[j]i=j第七章图一、填空题1、22、n(n-1)/2、n(n-1)3、n-14、邻接矩阵、邻接表、十字链表和邻接多重表5、n*n(或n行n列)6、e、2e7、出边、入边8、e、e9、O(n)、O(e)、O(e)10、O(n2)、O(n)+O(e)、O(e)+O(n)11、O（n2）、O（e）12、014253、01234513、ABCDE、ABCED14、2015、(0,1)5，(1,3)3，(3,2)6，(1,4)816、(1,3)3，(0,1)5，(3,2)6，(1,4)817、链栈18、n、n-1二、应用题1．(1)采