數據結構習題解答

數據結構習題解答數據結構習題解答數據結構習題解答數據結構習題解答編制僅供參考審核批準生效日期地址：電話：傳真:郵編:習題一1填空題(1)(數據元素、或元素、或結點、或頂點、或記錄）是數據的基本單位，在計算機程序中作為一個整體進行考慮和處理。(2)（數據項、或字段）是數據的最小單位，（數據元素）是討論數據結構時涉及的最小數據單位。(3)從邏輯關系上講，數據結構主要分為(集合)、(線性結構)、(樹結構)和(圖)。(4)數據的存儲結構主要有（順序存儲結構）和（鏈式存儲結構）兩種基本方法，不論哪種存儲結構，都要存儲兩方面的內容：（數據元素）和（它們之間的關系）。(5)算法具有5個特性，分別是（輸入）、（輸出）、（有窮性）、（確定性）、（可行性）。(6)算法的描述方法通常有(自然語言)、(流程圖)、(程序設計語言)、(偽代碼)4種，其中，(偽代碼)被稱為算法語言。(7)一般情況下，一個算法的時間復雜度是算法（輸入規(guī)模）的函數。(8)設待處理問題的規(guī)模為n,若一個算法的時間復雜度為一個常數，則表示成數量級的形式為(O(1))，若為n*log25n,則表示成數量級的形式為(O(n*log2n))。2.選擇題:(1)C,D(2)B(3)B(4)A(5)D(6)A(7)C(8)C,E習題二1.填空題(1)在順序表中，等概率情況下，插入和刪除一個元素平均需移動(表長的一半)個元素，具體移動元素的個數與(表的長度)和(數據元素所在的位置)有關。(2)一個順序表的第一個元素的存儲地址是100，每個數據元素的長度是2，則第5個數據元素的存儲地址是（108）。(3)設單鏈表中指針p指向單鏈表的一個非空結點A，若要刪除結點A的直接后繼，則需要修改指針的操作為（p->next=(p->next)->next,或者q=p->next;p->next=q->next）。(4)單鏈表中設置頭結點的作用是(方便運算,減少程序的復雜性，使得空表和非空表處理統(tǒng)一)。(5)非空的循環(huán)單鏈表由頭指針head指示，則其尾結點(由指針p所指)滿足(p->next=head)。(6)在有尾指針rear指示的循環(huán)單鏈表中，在表尾插入一個結點s的操作序列是（s->next=rear->next;rear->next=s;rear=s），刪除開始結點的操作序列是（q=rear->next->next;rear->next->next=q->next;deleteq;）。注：假設此循環(huán)單鏈表有表頭結點(7)一個具有n個結點的單鏈表，在p所指結點后插入一個新結點s的時間復雜性為（O(1)）；在給定值x的結點后插入一個新結點的時間復雜性為(O(n)）。(8)可由一個尾指針惟一確定的鏈表有(循環(huán)鏈表)、(雙鏈表)、(雙循環(huán)鏈表)。2.選擇題:(1)A,B(2)D(3)B(4)A(5)A(6)D(7)B(8)B(9)C(10)B(11)B(12)D(13)A(14)A5.算法設計設計一個時間復雜度為O(n)的算法。實現將數組A[n]中所有元素循環(huán)左移k個位置。算法思想：要使a1…akak+1…an->ak+1…ana1…ak,可以先讓a1…akak+1…an->ak…a1an…ak+1,再讓ak…a1an…ak+1->ak+1…ana1…ak，參見第1章16頁的思想火花算法：voidconverse(Ta[],inti,intj){for(s=i;s<=(i+j)/2;s++)解法1：voidtiaozhen(TA[],intn){s=0;t=n-1;while(s<t){while(A[s]%2!=0)s++;鏈表的程序如下，設單鏈表有表頭結點.voidLinkList::converse(){p=first->next;first->next=NULL;while(p){q=p->next;p->next=first->next;first->next=p;p=q;}}(5)假設在長度大于1的循環(huán)鏈表中，既無頭結點也無頭指針，s為指向鏈表中某個結點的指針，試編寫算法刪除結點s的前驅結點。voidLinkList::deleteS(Node<T>*s){p=s;while(p->next->next!=s)p=p->next;{q=p->next;p->next=q->next;deleteq;}(6)已知一單鏈表中的數據元素含有三類字符：字母、數字和其它字符。試編寫算法，構造三個循環(huán)鏈表，使每個循環(huán)鏈表中只含同一類字符。算法思想：1）構造3個帶表頭結點的循環(huán)鏈表，分別為zifu，shuzi和qita；2）遍歷單鏈表，按單鏈表中的當前數據元素的分類插入相應的鏈表voidfl(Node<T>*zifu,Node<T>*shuzi,Node<T>*qita){s=newNode<T>;s->next=s;zifu=s;s=newNode<T>;s->next=s;shuzi=s;s=newNode<T>;s->next=s;qita=s;a=zifu;b=shuzi;c=qita;p=first->next;選擇題:(1)C(2)D(3)C(4)B(5)B(6)B(7)D(8)A(9)C4.解答下列問題①不可以,因為有序列C,A,B.

②可以,push,push,push,pop,pop,pop,push,pop,push,pop.見書本棧頂元素是6,棧底元素是1.隊尾元素是9,隊頭元素是5.①③④合法,②不合法.習題四1.填空題(1)串是一種特殊的線性表，其特殊性體現在(數據元素的類型為字符型)。(2)兩個串相等的充分必要條件是(它們的長度相等且對應位置的字符相同)。(3)數組通常只有兩種運算，分別是(存取)和(修改)，這決定了數組通常采用（順序存儲）結構來實現存儲。(4)(1140)(5)設有一個10階的對稱矩陣A采用壓縮存儲，第一個元素A[0][0]的存儲地址為d，每個元素占用1個地址空間，則元素A[8][5]的存儲地址為(d+41)。(6)稀疏矩陣一般壓縮存儲方法有兩種，分別是(三元組順序表)和(十字鏈表)。2.選擇題:(1)B(2)D,E,K(3)B(4)XXX(5)D(6)C(7)D5(2).設計一個求矩陣A=(aij)nXm所有鞍點的算法，并分析最壞情況下的時間復雜度。算法思想2：附加兩個數組B[n]和C[m]，B[i]用來存第i行的最小值，C[j]用來存第j列的最小元素值。如果A[i][j]=B[i]=C[j]，則A[i][j]一定為馬鞍點。viodmaandian2(A[][],intm,intn){intB[n],C[m],i,j;for(i=0;i<n;i++){(3)一棵二叉樹的第i（i≥1）層上最多有(2i-1)個結點,一棵有n(n>0)個結點的滿二叉樹共有((n+1)/2)個葉子結點和((n-1)/2)個非終端結點。(4)設高度為h的二叉樹只有度為0的和度為2的結點，該二叉樹的結點數可能達到的最大值是(2h-1),最小值是（2h-1）。(5)深度為k的二叉樹中，所含葉子的個數最多為(2k-1).(6)具有100個結點的完全二叉樹的葉子結點數為(50)。(7)已知一棵度為3的樹有2個度為1的結點，3個度為2的結點，4個度為3的結點。則該樹有(12)個葉子結點。(8)某二叉樹的前序遍歷序列是ABCDEFG,中序遍歷序列是CBDAFGE,則其后序遍歷序列是(CDBGFEA)。(9)在具有n個結點的二叉鏈表中，共有（2n)個指針域，其中(n-1)個指針域用于指向其左右孩子，剩下的(n+1)個指針域則是空的。(10)在有n個葉子的哈夫曼樹中，葉子結點總數為(n),分支結點總數為（n-1）。2.選擇題:(1)D(2)D(3)B(4)C(5)B,C(6)D(7)A(8)A,B(9)D,A(10)B(11)B(12)C(13)D(14)C4.解答下列問題(3)已知一棵度為m的樹中：n1個度為1的結點，n2個度為2的結點，…，nm個度為m的結點，問該樹中共有多少個葉子結點解：設該樹中共有n0個葉子結點。則該樹中總結點個數為n=n0+n1+…+nm.而分支數為n-1=n1+2n2+3n3+…+mnm,所以n0=1+n2+2n3+…+(m-1)nm(4)已知一棵二叉樹的中序和后序序列為CBEDAFIGH和CEDBIFHGA,試構造該二叉樹。(5)給出葉子結點的權值集合為W={5,2,9,11,8,3,7}的哈夫曼樹的構造過程。5算法設計(1)設計算法求二叉樹的結點個數.注：本算法可以用二叉樹遍歷的所有算法，只要把cout語句換成結點的計數就可以了，但是要注意遞歸中的計數變量應該是外部變量。如intnum=0;intBiTree::count(BiNode<T>*rt){countsub(rt);returnnum;}voidBiTree::countSub(BiNode<T>*rt){if(rt!=NULL){num++;countSub(rt->lchild);countSub(rt->rchild);}}其他解法二：用前序遍歷的非遞歸算法intBiTree::CountPreOrder(BiNode<T>*rt){top=-1;p=rt;num=0;注:其實按照“選擇題”的(7)知:任何一棵二叉樹的葉子結點在前序、中序、后序遍歷序列中的相對次序肯定不發(fā)生改變解法思想:使用任何遍歷算法，把“cout<<rt->data”改成判斷此結點是否為葉子結點。voidBiTree::leaf(BiNode<T>*rt){if(rt==NULL)return;else{if(rt->lchild==NULL&&!rt->rchild)cout<<rt->data;PostOrder(rt->lchild);PostOrder(rt->rchild);}}(3)設計算法求二叉樹的深度.注：本算法也可以用二叉樹遍歷的所有算法。但是在用前序和中序算法時要注意深度如何來確定。intBiTree::depth(BiNode<T>*rt){if(rt==NULL)return0;else{hl=depth(rt->lchild);hr=depth(rt->rchild);return(hl>hr)hl+1:hr+1;}(4)設計算法:輸出二叉樹后序遍歷的逆序.解法思想:太簡單啦！??！前序遍歷是先遍歷右子樹即可.voidBiTree::PostOrder_1(BiNode<T>*rt){if(rt==NULL)return;else{cout<<rt->data;PostOrder(rt->rchild);PostOrder(rt->lchild);}}(5)以二叉鏈表為存儲結構，編寫算法求二叉樹中值x的結點的雙親.voidBiTree::PreOrder_Parent(BiNode<T>*rt){{top=-1;p=rt;voidBiTree::DeleteX(BiNode<T>*rt,Tx){if(rt==NULL)return;if(rt->data==x){Release(rt);}else{DeleteX(rt->lchild,x);DeleteX(rt->rchild,x);}}(7)一棵具有n個結點的二叉樹采用順序存儲結構，編寫算法對該二叉樹進行前序遍歷.算法思想:套用前序遍歷的原程序，注意查找左右孩子結點的地址和判別孩子是否存在的方法。注：根結點的下標是1。voidBiTree::PreOrder_Seq(intrt){top=-1;p=rt;解法思想:使用任何遍歷算法，把“cout<<rt->data”改成左右孩子指針交換即可。voidBiTree::PostOrderChange(BiNode<T>*rt){if(rt==NULL)return;else{PostOrder(rt->lchild);PostOrder(rt->rchild);temp=rt->lchild;rt->lchild=rt->rchild;rt->rchild=temp;}}習題61.填空題⑴設無向圖G中頂點數為ｎ，則圖G至少有（0）條邊，至多有（n(n-1)/2）條邊；若G為有向圖，則至少有（0）條邊，至多有（n(n-1)）條邊。⑵任何連通圖的連通分量只有一個，即是（它本身）。⑶圖的存儲結構主要有兩種，分別是（鄰接矩陣）和（鄰接表）。⑷已知無向圖Ｇ的頂點數為ｎ，邊數為ｅ，其鄰接表表示的空間復雜度為（O(n+e)）。⑸已知一個圖的鄰接矩陣表示，計算第ｊ個頂點的入度的方法是（矩陣中第j-1列的非0元素個數）。⑹有向圖Ｇ用鄰接矩陣Ａ[ｎ][ｎ]存儲，其第ｉ行的所有元素之和等于頂點ｉ的（出度）。⑺圖的深度優(yōu)先遍歷類似于樹的（前序）遍歷，它所用的數據結構是（棧）；圖的廣度優(yōu)先遍歷類似于樹的（層序）遍歷，它所用的數據結構是（隊列）。⑻對于含有ｎ個頂點ｅ條邊的連通圖，利用Ｐrim算法求最小生成樹的時間復雜度為（O(n2)），利用Kruscal算法求最小生成樹的時間復雜度為（O(elog2e)）。⑼如果一個有向圖不存在（有向回路），則該圖的全部頂點可以排成一個拓撲序列。⑽在一個有向圖中，若存在弧<vi,vj>、<vj,vk>、<vi,vk>，則在其拓撲序列中，頂點vi,vj,vk的相對次序為（vi,vj,vk）。2.選擇題:(1)C(2)A,G(3)C(4)B(5)D(6)C,F(7)B(8)D(9)A(10)A(11)A(12)C(13)A(14)C,C,F(15)B4.解答下列問題(1)n個頂點的無向圖,采用鄰接表存儲,回答下列問題:①圖中有多少條邊答:鄰接表中所有邊表結點的個數的一半.②任意兩個頂點i和j是否有邊相連答:查找第i個邊表的結點中是否有鄰接點域值為j的結點.如果有,則它們之間有邊;否則,無邊.③任意一個頂點的度是多少答:此頂點對應的邊表中結點的個數.(2)n個頂點的無向圖,采用鄰接矩陣存儲,回答下列問題:①圖中有多少條邊答:鄰接矩陣中所有元素和的一半.②任意兩個頂點i和j是否有邊相連答:如果第i行第j列的元素值為1,則它們之間有邊;否則,無邊.③任意一個頂點的度是多少答:此頂點對應的行中元素之和.(3)證明：生成樹中最長路徑的起點和終點的度均為1.證明：設一棵樹的最長路徑P=v1v2…vk。若v1的度至少為2，不妨設u(≠v2)是它的另外一個鄰點。若u∈{v1,v2,…,vk},則此樹中包含圈，矛盾；否則uv1v2…vk是一條更長的路，同樣矛盾。所以v1的度為1.類似可以證明vk的度為1.(5)圖6-50所示是一個無向帶權圖，請分別用Ｐrim算法和Ｋruscal算法求最小生成樹。習題71.填空題(1)順序查找技術適合于存儲結構為（各種形式）的線性表，而折半查找技術適合于存儲結構為（順序存儲）的線性表，并且表中的元素必須是（有序的）。(2)設有一個已按各元素值排好序的線性表，長度為125，用折半查找法查找與給定值相等的元素，若查找成功，則至少需要比較(1)次，至多需要比較(7)次。(3)對于數列{25,30,8,5,1,27,24,10,20,21,9,28,7,13,15},假定每個結點的查找概率相同，若用順序存儲結構組織該數列，則查找一個數的平均比較次數為（8）。若按二叉排序樹組織該數列，則查找一個數的平均比較次數為（59/15）。(4)長度為20的有序表采用折半查找，共有（4）個元素的查找長度為3。(5)假設數列{25,43,62,31,48,56},采用散列函數為H(k)=kmod7,則元素48的同義詞是（62）。(6)在散列技術中，處理沖突的主要方法是（開放地址法）和（拉鏈法）。(7)在各種查找方法中，平均查找長度與結點個數無關的查找方法是（散列查找）。(8)與其他方法比較，散列查找法的特點是（記錄的存儲位置與關鍵碼之間建立了一個確定的對應關系，平均查找長度與結點個數無關）。2.選擇題:(1)B(2)D,D(3)A,B(4)D(5)A(6)C(7)C(8)B(9)D(10)A(11)C(12)C4．解答下列問題(1)分別畫出在線性表(a,b,c,d,e,f,g)中進行折半查找關鍵碼e和g的過程。解：d->f->e和d->f->g(2)畫出長度為10的折半查找判定樹，并求出等概率時查找成功和不成功的