數(shù)據(jù)結(jié)構(gòu)習題解答

數(shù)據(jù)結(jié)構(gòu)習題解答數(shù)據(jù)結(jié)構(gòu)習題解答數(shù)據(jù)結(jié)構(gòu)習題解答數(shù)據(jù)結(jié)構(gòu)習題解答編制僅供參考審核批準生效日期地址：電話：傳真:郵編:習題一1填空題(1)(數(shù)據(jù)元素、或元素、或結(jié)點、或頂點、或記錄）是數(shù)據(jù)的基本單位，在計算機程序中作為一個整體進行考慮和處理。(2)（數(shù)據(jù)項、或字段）是數(shù)據(jù)的最小單位，（數(shù)據(jù)元素）是討論數(shù)據(jù)結(jié)構(gòu)時涉及的最小數(shù)據(jù)單位。(3)從邏輯關系上講，數(shù)據(jù)結(jié)構(gòu)主要分為(集合)、(線性結(jié)構(gòu))、(樹結(jié)構(gòu))和(圖)。(4)數(shù)據(jù)的存儲結(jié)構(gòu)主要有（順序存儲結(jié)構(gòu)）和（鏈式存儲結(jié)構(gòu)）兩種基本方法，不論哪種存儲結(jié)構(gòu)，都要存儲兩方面的內(nèi)容：（數(shù)據(jù)元素）和（它們之間的關系）。(5)算法具有5個特性，分別是（輸入）、（輸出）、（有窮性）、（確定性）、（可行性）。(6)算法的描述方法通常有(自然語言)、(流程圖)、(程序設計語言)、(偽代碼)4種，其中，(偽代碼)被稱為算法語言。(7)一般情況下，一個算法的時間復雜度是算法（輸入規(guī)模）的函數(shù)。(8)設待處理問題的規(guī)模為n,若一個算法的時間復雜度為一個常數(shù)，則表示成數(shù)量級的形式為(O(1))，若為n*log25n,則表示成數(shù)量級的形式為(O(n*log2n))。2.選擇題:(1)C,D(2)B(3)B(4)A(5)D(6)A(7)C(8)C,E習題二1.填空題(1)在順序表中，等概率情況下，插入和刪除一個元素平均需移動(表長的一半)個元素，具體移動元素的個數(shù)與(表的長度)和(數(shù)據(jù)元素所在的位置)有關。(2)一個順序表的第一個元素的存儲地址是100，每個數(shù)據(jù)元素的長度是2，則第5個數(shù)據(jù)元素的存儲地址是（108）。(3)設單鏈表中指針p指向單鏈表的一個非空結(jié)點A，若要刪除結(jié)點A的直接后繼，則需要修改指針的操作為（p->next=(p->next)->next,或者q=p->next;p->next=q->next）。(4)單鏈表中設置頭結(jié)點的作用是(方便運算,減少程序的復雜性，使得空表和非空表處理統(tǒng)一)。(5)非空的循環(huán)單鏈表由頭指針head指示，則其尾結(jié)點(由指針p所指)滿足(p->next=head)。(6)在有尾指針rear指示的循環(huán)單鏈表中，在表尾插入一個結(jié)點s的操作序列是（s->next=rear->next;rear->next=s;rear=s），刪除開始結(jié)點的操作序列是（q=rear->next->next;rear->next->next=q->next;deleteq;）。注：假設此循環(huán)單鏈表有表頭結(jié)點(7)一個具有n個結(jié)點的單鏈表，在p所指結(jié)點后插入一個新結(jié)點s的時間復雜性為（O(1)）；在給定值x的結(jié)點后插入一個新結(jié)點的時間復雜性為(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)的算法。實現(xiàn)將數(shù)組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++;鏈表的程序如下，設單鏈表有表頭結(jié)點.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)鏈表中，既無頭結(jié)點也無頭指針，s為指向鏈表中某個結(jié)點的指針，試編寫算法刪除結(jié)點s的前驅(qū)結(jié)點。voidLinkList::deleteS(Node<T>*s){p=s;while(p->next->next!=s)p=p->next;{q=p->next;p->next=q->next;deleteq;}(6)已知一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、數(shù)字和其它字符。試編寫算法，構(gòu)造三個循環(huán)鏈表，使每個循環(huán)鏈表中只含同一類字符。算法思想：1）構(gòu)造3個帶表頭結(jié)點的循環(huán)鏈表，分別為zifu，shuzi和qita；2）遍歷單鏈表，按單鏈表中的當前數(shù)據(jù)元素的分類插入相應的鏈表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)串是一種特殊的線性表，其特殊性體現(xiàn)在(數(shù)據(jù)元素的類型為字符型)。(2)兩個串相等的充分必要條件是(它們的長度相等且對應位置的字符相同)。(3)數(shù)組通常只有兩種運算，分別是(存取)和(修改)，這決定了數(shù)組通常采用（順序存儲）結(jié)構(gòu)來實現(xiàn)存儲。(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：附加兩個數(shù)組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)個結(jié)點,一棵有n(n>0)個結(jié)點的滿二叉樹共有((n+1)/2)個葉子結(jié)點和((n-1)/2)個非終端結(jié)點。(4)設高度為h的二叉樹只有度為0的和度為2的結(jié)點，該二叉樹的結(jié)點數(shù)可能達到的最大值是(2h-1),最小值是（2h-1）。(5)深度為k的二叉樹中，所含葉子的個數(shù)最多為(2k-1).(6)具有100個結(jié)點的完全二叉樹的葉子結(jié)點數(shù)為(50)。(7)已知一棵度為3的樹有2個度為1的結(jié)點，3個度為2的結(jié)點，4個度為3的結(jié)點。則該樹有(12)個葉子結(jié)點。(8)某二叉樹的前序遍歷序列是ABCDEFG,中序遍歷序列是CBDAFGE,則其后序遍歷序列是(CDBGFEA)。(9)在具有n個結(jié)點的二叉鏈表中，共有（2n)個指針域，其中(n-1)個指針域用于指向其左右孩子，剩下的(n+1)個指針域則是空的。(10)在有n個葉子的哈夫曼樹中，葉子結(jié)點總數(shù)為(n),分支結(jié)點總數(shù)為（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的結(jié)點，n2個度為2的結(jié)點，…，nm個度為m的結(jié)點，問該樹中共有多少個葉子結(jié)點解：設該樹中共有n0個葉子結(jié)點。則該樹中總結(jié)點個數(shù)為n=n0+n1+…+nm.而分支數(shù)為n-1=n1+2n2+3n3+…+mnm,所以n0=1+n2+2n3+…+(m-1)nm(4)已知一棵二叉樹的中序和后序序列為CBEDAFIGH和CEDBIFHGA,試構(gòu)造該二叉樹。(5)給出葉子結(jié)點的權(quán)值集合為W={5,2,9,11,8,3,7}的哈夫曼樹的構(gòu)造過程。5算法設計(1)設計算法求二叉樹的結(jié)點個數(shù).注：本算法可以用二叉樹遍歷的所有算法，只要把cout語句換成結(jié)點的計數(shù)就可以了，但是要注意遞歸中的計數(shù)變量應該是外部變量。如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)知:任何一棵二叉樹的葉子結(jié)點在前序、中序、后序遍歷序列中的相對次序肯定不發(fā)生改變解法思想:使用任何遍歷算法，把“cout<<rt->data”改成判斷此結(jié)點是否為葉子結(jié)點。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)以二叉鏈表為存儲結(jié)構(gòu)，編寫算法求二叉樹中值x的結(jié)點的雙親.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個結(jié)點的二叉樹采用順序存儲結(jié)構(gòu)，編寫算法對該二叉樹進行前序遍歷.算法思想:套用前序遍歷的原程序，注意查找左右孩子結(jié)點的地址和判別孩子是否存在的方法。注：根結(jié)點的下標是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中頂點數(shù)為ｎ，則圖G至少有（0）條邊，至多有（n(n-1)/2）條邊；若G為有向圖，則至少有（0）條邊，至多有（n(n-1)）條邊。⑵任何連通圖的連通分量只有一個，即是（它本身）。⑶圖的存儲結(jié)構(gòu)主要有兩種，分別是（鄰接矩陣）和（鄰接表）。⑷已知無向圖Ｇ的頂點數(shù)為ｎ，邊數(shù)為ｅ，其鄰接表表示的空間復雜度為（O(n+e)）。⑸已知一個圖的鄰接矩陣表示，計算第ｊ個頂點的入度的方法是（矩陣中第j-1列的非0元素個數(shù)）。⑹有向圖Ｇ用鄰接矩陣Ａ[ｎ][ｎ]存儲，其第ｉ行的所有元素之和等于頂點ｉ的（出度）。⑺圖的深度優(yōu)先遍歷類似于樹的（前序）遍歷，它所用的數(shù)據(jù)結(jié)構(gòu)是（棧）；圖的廣度優(yōu)先遍歷類似于樹的（層序）遍歷，它所用的數(shù)據(jù)結(jié)構(gò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個頂點的無向圖,采用鄰接表存儲,回答下列問題:①圖中有多少條邊答:鄰接表中所有邊表結(jié)點的個數(shù)的一半.②任意兩個頂點i和j是否有邊相連答:查找第i個邊表的結(jié)點中是否有鄰接點域值為j的結(jié)點.如果有,則它們之間有邊;否則,無邊.③任意一個頂點的度是多少答:此頂點對應的邊表中結(jié)點的個數(shù).(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所示是一個無向帶權(quán)圖，請分別用Ｐrim算法和Ｋruscal算法求最小生成樹。習題71.填空題(1)順序查找技術適合于存儲結(jié)構(gòu)為（各種形式）的線性表，而折半查找技術適合于存儲結(jié)構(gòu)為（順序存儲）的線性表，并且表中的元素必須是（有序的）。(2)設有一個已按各元素值排好序的線性表，長度為125，用折半查找法查找與給定值相等的元素，若查找成功，則至少需要比較(1)次，至多需要比較(7)次。(3)對于數(shù)列{25,30,8,5,1,27,24,10,20,21,9,28,7,13,15},假定每個結(jié)點的查找概率相同，若用順序存儲結(jié)構(gòu)組織該數(shù)列，則查找一個數(shù)的平均比較次數(shù)為（8）。若按二叉排序樹組織該數(shù)列，則查找一個數(shù)的平均比較次數(shù)為（59/15）。(4)長度為20的有序表采用折半查找，共有（4）個元素的查找長度為3。(5)假設數(shù)列{25,43,62,31,48,56},采用散列函數(shù)為H(k)=kmod7,則元素48的同義詞是（62）。(6)在散列技術中，處理沖突的主要方法是（開放地址法）和（拉鏈法）。(7)在各種查找方法中，平均查找長度與結(jié)點個數(shù)無關的查找方法是（散列查找）。(8)與其他方法比較，散列查找法的特點是（記錄的存儲位置與關鍵碼之間建立了一個確定的對應關系，平均查找長度與結(jié)點個數(shù)無關）。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的折半查找判定樹，并求出等概率時查找成功和不成功的