數據結構與實訓課后答案全集(已修改)

　

【正文】 第1章 習題答案1. 填空題（1）在計算機中的存儲映像（是邏輯結構在計算機中的實現或存儲表示） 數據元素的表示 元素之間關系的表示 數據元素。（2）已經實現 是一個概念 分離 分離（3）時、空效率 指人對算法閱讀理解的難易程度 對于非法的輸入數據，算法能給出相應的響應，而不是產生不可預料的后果。（4）軟硬件環境 問題規模的 （5）最壞（6）O（n4） O（n2） （7）時間復雜度（8）n O（n2）2. 判斷題（1）（2）（3）√（4）√（5）√（6）√（7）（8）（9）（10）3. 簡答題（1）略（）（2）（a）n1， O（n） （b） n1 , O（n）（c）11* n+1, O（n）（n為初始值100）（d） , O（） （e） n , O（n）第2章 習題及答案填空題（1）address+m*i（2）順序 順序 順序 鏈式存儲 鏈式存儲（3）亦相鄰 不一定（4）ni+1（5） 0≤i≤la的長度 1≤j≤lb的長度1 0≤k≤lc的長度1（6） 插入的位置，節點數n（順序表長度n）（7）其前驅 O(n) O（1）（8）其前驅 O(n) O（1）（9）p→next=p→next →next（10）head→next==Null head==Null head→next==head head==Null（11）head→next=head→next→next head=head→next（12）x=p→prior→data。 p→prior→data=p→next→data。 p→next→data=x。（13）p==head→prior(或p→next==head)2．判斷題（1）（2）√（3）（4）（5）（6）（7）√（8）（9）（10）3．簡答題(1)單向循環鏈表雙向循環鏈表存儲密度高低查找后繼的時間復雜度O(1)O(1)查找前驅的時間復雜度O(n)O(1)（2）在帶頭結點的單鏈表上，查找指針p所指結點的前驅。（3）交換指針p與指針q所指結點的值。4．算法設計題(1)void reverse(SeqList l){ for (i=0。 i=()/2。 i++)[i]—[]。}(2)void delete(SeqList, int i, int k)/*從順序表中刪除自第i個元素開始的k個元素*/{ if (i0 || i|| k0) { printf(“Error”)。return。}if (i+k=) /*表中從i個元素起到最后一個元素有k個元素*/ { for ( j=i+k。 j。 j++) [jk]=[j]。 =。 }else /*表中從i個元素起直到最后一個元素不足k個元素*/ =i。}(3)void insert(LinkList h, ElementType x)/*將x插入到遞增鏈表h中，插入后的鏈表有序性不變*/{ if (h→next==Null) /*空表時*/ { q=(linklist) malloc (sizeof(ListNode))。q→next=Null。q→data=x。h→next =q。}p1=h→next。 p2=h。while (p1→next != Null amp。amp。 p1→datax){ p2=p1。 p1=p1→next。}if ( p1→next==Null amp。amp。 p1→datax){ q=(linklist) malloc (sizeof(ListNode))。 q→next=Null。q→data=x。p1→next=q。} else /* (p1→next==Null amp。amp。 p1→data=x) || (p1→next!=Null amp。amp。 p1→data=x)*/ { q=(LinkList) malloc (sizeof(ListNode)。 q→data=x。p2→next=q。q→next=p1。}}(4)void delete (LinkList p)/*在不帶頭結點且長度大于1的單向循環鏈表中，p指向某結點，刪除p的前驅結點*/{ ppp=p→next。while (ppp→next→next != p)ppp =ppp→next。/*刪除p的前驅結點*/pp=ppp→next。ppp→next=pp→next。free(pp)。}(5) void delete (LinkList h)/*h為帶頭結點的，非降序排列的單鏈表的頭指針，刪除表中值相同的結點，使之只保留一個*/{ p=h→next。if (!p) return。x=p→data。while (p→next)if (x != p→next→data) { x = p→next→data。p = p→next}else{ q=p→next。p→next=p→next→next。free(q)。}}void delete (LinkList h)/*刪除帶頭結點的單鏈表h（指向頭結點）中值為x的結點的前驅結點*/{ if (!(h→next )) return。if (!(h→next→next)) return。p1=h→next→next。 p2=h。while (p1→next amp。amp。 p1→data != x ) { p1=p1→next。p2=p2→next。}if (p1→data == x) { q=p2→next。p2→next=p1。free(q)。}}(7) Linklist subtraction (LinkList la, LinkList lb)/*la,lb分別為表示集合A,B的帶頭結點的單鏈表的頭指針，AB由la鏈表返回*/{ if (!(la→next)) return (la)。else{ pa1=la→next 。 pa2=la。}if (!(lb→next)) return (la)。while (pa1) { pb=lb→next 。 while (pb amp。amp。 pa1→data!=pb→data) pb=pb→next。if (pb) /*pa1→data==pb→data*/{ pa2→next=pa1→next。free(pa1)。pa1=pa2→next。}else{ pa1=pa1→next。pa2=pa2→next。} } return (la)。}（8）LinkList intersection(LinkList la, LinkList lb)/*la,lb,lc分別為表示集合A,B,C的帶頭結點的遞增有序的單鏈表的頭指針，C=A∩B由lc鏈表返回*/ { lc=(LinkList) malloc (sizeof(LinkNode))。 lc→next=null。tail=lc。 /*tail指向lc鏈的尾結點*/if (!(la→next)) return(lc)。else pa=la→next。if (!(lb→next)) return(lc)。while (pa) { pb=lb→next。while (pb amp。amp。 pa→data != pb→data) pb=pb→next。if (pb) insert(lc, tail, pa→data)。pa=pa→next。 }return(lc)。}void insert (LinkList l, LinkList tail, ElemenType x)/*將值x插入到單鏈表l的尾部*/{ p=(LinkList) malloc (sizeof(LinkNode))p→data=x。 p→next=null。tail→next=p。tail=p。}SeqList intersection(SeqList la, SeqList lb)/*集合A,B,C對應的順序遞增表為la,lb,lc，C=A∩B由lc表示*/{ =0。if (==0 || ==0) return(lc)for ( a=0。 a。 a++){ for ( b=0。 b amp。amp。 [b] != [a]。 b++) if (b){ []=[a]。 ++。}}retuen(lc)。}(9)void delete(LinkList h,ElementType min ElementType max)/*h是帶頭結點的無序單鏈表的頭指針，刪除結點值大于min小于max的結點*/{ if (!(h→next)) return。 p1=h→next。p2=h。while (p1) if (p1→datamin amp。amp。 p1→datamax) { p2→next=p1→next。 free(p1)。 p1=p2→next。} else { p1=p1→next。p2=p2→next。}}(10)void separation(LinkList h, LinkList *ph1, LinkList *ph2)/*h為帶頭結點的單鏈表的頭指針，該表中含有兩類字符數據元素：字母與數字，拆分h為兩條帶頭結點的單項循環鏈表*ph*ph2，其中*ph1鏈中存放字母，*ph2鏈中存放數字*/{ if (!(h→next)) return。 p=h→next。 free (h)。*ph1=(LinkList) malloc (sizeof(LinkNode))。(*ph1)→next=*ph1。*ph2=(LinkList) malloc (sizeof(LinkNode))。(*ph2)→next=*ph2。while (p){ h=p。p=p→next。if ( h→data=’0’ amp。amp。 h→data=’9’) /*數字字符插入到*ph2鏈*/{ h→next=(*ph2)→next。(*ph2)→next=h。} else /*字母字符插入到*ph1鏈*/ { h→next=(*ph1)→next。 (*ph1) →next=h。} }}(11)void merge(DoubleList head1, DoubleList head2)/*headhead2分別為兩個帶頭結點的雙向循環鏈表的頭指針，將head1鏈接到head2*/{ if (head1→next == head1) return。 /*head1為空鏈表*/head2→prior→next=head1→next。head1→next→prior=head2→prior。head1→prior→next=head2。head2→prior=head1→prior。free (head1)。}(12)void delete(DoubleList head, DoubleNode *p)/*head為帶頭結點的雙向循環鏈表的頭指針，p指向head鏈中的某一個結點，刪除p的前驅結點*/{ if (p→prior==head) return。 /*p結點無前驅結點*/q=p→prior。 /*q指向p的前驅結點*/p→prior→prior→next=p。p→prior=p→prior→prior。 free (q)。}第3章 習題及答案1．填空題（1）1，3，5 1（2）push, pop, push, push, pop, push, pop, pop（3）棧空 棧滿（4）O(1) O(1)（5）= =+1（6）s（7）空（8）棧底 棧頂（9）隊尾 隊首（頭）（10）是否為空 是否為滿（11）21（12）front→next==rear（13）front==rear (rear+1)%MAX==front rear+MAXfrort2．判斷題（1）√（2）（3）√（4）√（5）（6）√（7）√（8）（9）√（10）√3．簡答題（1）當進行入隊操作時，隊尾指針的值已經到達數組空間的最大下標（MaxSize1），而隊首指針的值卻大于0，這時就產生了假溢出現象。（2）使棧s中的元素順序置逆。（3）借助于另一鏈棧t，使得鏈棧s去掉指定的元素e。4．算法設計題（1）int maxvalue(SeqStack s)/*s是存有整數序列a1,a2,…,an的堆棧，用遞歸求其中的最大值*/{ i