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

1、v1.0可編輯可修改習(xí)題一1填空題（1）（數(shù)據(jù)元素、或元素、或結(jié)點(diǎn)、或頂點(diǎn)、或記錄 ）是數(shù)據(jù)的基本單位，在計算機(jī)程序中作為一個整體進(jìn)行考慮和處理。（2）（數(shù)據(jù)項(xiàng)、或字段）是數(shù)據(jù)的最小單位，（數(shù)據(jù)元素）是討論數(shù)據(jù)結(jié)構(gòu)時涉及的最小數(shù)據(jù)單位。（3）從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為（集合）、（線性結(jié)構(gòu)）、（樹結(jié)構(gòu)）和（圖）。數(shù)據(jù)的存儲結(jié)構(gòu)主要有（順序存儲結(jié)構(gòu)）和（鏈?zhǔn)酱鎯Y(jié)構(gòu)）兩種基本方法，不論哪種存儲結(jié)構(gòu)， 都要存儲兩方面的內(nèi)容：（數(shù)據(jù)元素）和（它們之間的關(guān)系）。（5）算法具有5個特性，分別是（輸入）、（輸出）、（有窮性）、（確定性）、（可行性）。（6）算法的描述方法通常有（自然語言）、（流程圖）、

2、（程序設(shè)計語言）、（偽代碼）4種，其中，（偽代 碼）被稱為算法語言。（7） 一般情況下，一個算法的時間復(fù)雜度是算法（ 輸入規(guī)模）的函數(shù)。（8）設(shè)待處理問題的規(guī)模為n,若一個算法的時間復(fù)雜度為一個常數(shù)，則表示成數(shù)量級的形式為（0（1）,若為n*log 25n,則表示成數(shù)量級的形式為（O（n*log 2n）。2.選擇題：（1） C, D （2） B （3） B （4） A （5） D （6） A （7） C （8） C, E習(xí)題二1.填空題（1）在順序表中，等概率情況下，插入和刪除一個元素平均需移動（表長的一半）個元素，具體移動元 素的個數(shù)與（表的長度）和（數(shù)據(jù)元素所在的位置）有關(guān)。（2） 一個順

3、序表的第一個元素的存儲地址是100,每個數(shù)據(jù)元素的長度是2,則第5個數(shù)據(jù)元素的存儲地址是（108）。（3）設(shè)單鏈表中指針p指向單鏈表的一個非空結(jié)點(diǎn) A,若要刪除結(jié)點(diǎn)A的直接后繼，則需要修改指針的操作為（p->next=（p->next）->next, 或者 q=p->next; p->next=q->next ）。（4）單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是（方便運(yùn)算，減少程序的復(fù)雜性，使得空表和非空表處理統(tǒng)一）。（5）非空的循環(huán)單鏈表由頭指針head指示，則其尾結(jié)點(diǎn)（由指針p所指）滿足（p->next=head ）。（6）在有尾指針rear指示的循環(huán)單鏈表中，在

4、表尾插入一個結(jié)點(diǎn)s的操作序列是（s->next=rear->next; rear->next=s; rear=s ）,刪除開始結(jié)點(diǎn)的操作序歹！J是 （q=rear->next->next;rear->next->next=q->next; delete q;注：假設(shè)此循環(huán)單鏈表有表頭結(jié)點(diǎn)(7) 一個具有n個結(jié)點(diǎn)的單鏈表，在p所指結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)s的時間復(fù)雜性為(0(1);在給 定值x的結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)的時間復(fù)雜性為(0(n)。(8)可由一個尾指針惟一確定的鏈表有(循環(huán)鏈表)、(雙鏈表)、(雙循環(huán)鏈表)。2.選擇題：(1) A,B (2)

5、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.算法設(shè)計(1) 設(shè)計一個時間復(fù)雜度為O(n)的算法。實(shí)現(xiàn)將數(shù)組An中所有元素循環(huán)左移k個位置。算法思想：要使 avakak+van -> a k+1 ana1a% 可以先讓 a1akak+1 an->aka1an-ak+1, Bib aka 1anak+1-> a k+1a na1a k ,參見第1章16頁的思想火花算法：void converse" a口，int i, int j)for(s=i; s<

6、=(i+j)/2;s+)解法 1: void tiaozhen(T A口,int n) s=0; t=n-1;while(s<t) while( As%2!=0) s+;鏈表的程序如下，設(shè)單鏈表有表頭結(jié)點(diǎn).void LinkList二converse。 p=first->next;first->next=NULL;while(p)q=p->next; p->next=first->next;first->next=p;p=q;(5)假設(shè)在長度大于1的循環(huán)鏈表中，既無頭結(jié)點(diǎn)也無頭指針，s為指向鏈表中某個結(jié)點(diǎn)的指針，試 編寫算法刪除結(jié)點(diǎn)s的前驅(qū)結(jié)點(diǎn)。voi

7、d LinkList二deleteS(Node<T> *s)p=s； while(p->next->next!=s) p=p->next; q=p->next; p->next=q->next;delete q;(6)已知一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、數(shù)字和其它字符。試編寫算法，構(gòu)造三個循環(huán) 鏈表，使每個循環(huán)鏈表中只含同一類字符。算法思想：1)構(gòu)造3個帶表頭結(jié)點(diǎn)的循環(huán)鏈表，分別為 zifu , shuzi和qita ；2)遍歷單鏈表，按單鏈表中的當(dāng)前數(shù)據(jù)元素的分類插入相應(yīng)的鏈表void fl(Node<T>* zifu, N

8、ode<T> *shuzi, Node<T> *qita) s=new Node<T> s->next=s; zifu=s;s=new Node<T> s->next=s; shuzi=s;s=new Node<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.解答下列問題不可以，因?yàn)橛行蛄蠧, A, B.(2) 可以,push,

9、 push, push, pop, pop, pop, push, pop, push, pop.見書本(4) 棧頂元素是6,棧底元素是1.(5) 隊(duì)尾元素是9,隊(duì)頭元素是5.(6) 合法，不合法.習(xí)題四1 .填空題(1)用是一種特殊的線性表，其特殊性體現(xiàn)在(數(shù)據(jù)元素的類型為字符型)。(2)兩個用相等的充分必要條件是(它們的長度相等且對應(yīng)位置的字符相同)(3)數(shù)組通常只有兩種運(yùn)算，分別是(存取)和(修改)，這決定了數(shù)組通常采用( 順序存儲)結(jié) 構(gòu)來實(shí)現(xiàn)存儲。(4) (1140)(5)設(shè)有一個10階的對稱矩陣A采用壓縮存儲，第一個元素A00的存儲地址為d,每個元素占用1個地址空間，則元素A85的

10、存儲地址為(d+41 )。(6)稀疏矩陣一般壓縮存儲方法有兩種，分別是(三元組順序表)和(十字鏈表)。2 .選擇題：(1) B (2) D, E, K (3) B (4) XXX (5) D (6) C (7) D5(2).設(shè)計一個求矩陣A=(aj)nxm所有鞍點(diǎn)的算法，并分析最壞情況下的時間復(fù)雜度。算法思想2：附加兩個數(shù)組Bn和Cm, Bi用來存第i行的最小值，Cj用來存第j列的最小元素值。如果Aij= Bi=Cj,則A皿一定為馬鞍點(diǎn)。viod maandian2(A ,int m,int n)int Bn,Cm,i,j;for(i=0;i<n;i+)(3) 一棵二叉樹的第i (i &

11、gt;1)層上最多有(2i-1 )個結(jié)點(diǎn)，一棵有n(n>0)個結(jié)點(diǎn)的滿二叉樹共有(n+1)/2 )個葉子結(jié)點(diǎn)和(n-1)/2 )個非終端結(jié)點(diǎn)。(4)設(shè)高度為h的二叉樹只有度為0的和度為2的結(jié)點(diǎn)，該二叉樹的結(jié)點(diǎn)數(shù)可能達(dá)到的最大值是(2h-1 ),最小值是(2 h -1 )。(5)深度為k的二叉樹中，所含葉子的個數(shù)最多為(2k-1).(6)具有100個結(jié)點(diǎn)的完全二叉樹的葉子結(jié)點(diǎn)數(shù)為(50)。(7)已知一棵度為3的樹有2個度為1的結(jié)點(diǎn)，3個度為2的結(jié)點(diǎn)，4個度為3的結(jié)點(diǎn)。則該樹有(12) 個葉子結(jié)點(diǎn)。(8)某二叉樹的前序遍歷序列是 ABCDEF時序遍歷序列是CBDAFG即其后序遍歷序歹是 (C

12、DBGFEA)。 在具有n個結(jié)點(diǎn)的二叉鏈表中，共有( 2n )個指針域，其中(n-1 )個指針域用于指向其左右孩子，剩下的(n+1 )個指針域則是空的。(10)在有n個葉子的哈夫曼樹中，葉子結(jié)點(diǎn)總數(shù)為(n ),分支結(jié)點(diǎn)總數(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的樹中：ni個度為1的結(jié)點(diǎn)，n2個度為2的結(jié)點(diǎn)，nm個度為m的結(jié)點(diǎn)，問該 樹中共有多少個葉子結(jié)點(diǎn)解：設(shè)該樹中共有 防個葉子結(jié)點(diǎn)。

13、則該樹中總結(jié)點(diǎn)個數(shù)為n= n0+ n 1 + + n m.而分支數(shù)為n-1= n 1 +2n2 +3n3 + mnm,所以n 0 =1+n2 +2n3 + (m -1)n m(4)已知一棵二叉樹的中序和后序序列為 CBEDAFIG和CEDBIFHGAS構(gòu)造該二叉樹。(5)給出葉子結(jié)點(diǎn)的權(quán)值集合為 W=5,2,9,11,8,3,71 9j1 ioj7©© 05算法設(shè)計(1)設(shè)計算法求二叉樹的結(jié)點(diǎn)個數(shù).注：本算法可以用二叉樹遍歷的所有算法，只要把遞歸中的計數(shù)變量應(yīng)該是外部變量。如X的哈夫曼樹的構(gòu)造過程。cout語句換成結(jié)點(diǎn)的計數(shù)就可以了，但是要注意int num=0;int B

14、iTree二count(BiNode<T> *rt) countsub(rt); return num;void BiTree二countSub(BiNode<T> *rt) if (rt !=NULL) num+; countSub (rt->lchild); countSub (rt->rchild); 其他解法二：用前序遍歷的非遞歸算法int BiTree二CountPreOrder(BiNode<T> *rt)top= -1; p=rt; num=0;注：其實(shí)按照“選擇題”的(7)知：任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序、后序遍歷序列中的

15、相對 次序肯定不發(fā)生改變解法思想：使用任何遍歷算法，把“ cout<<rt- >data”改成判斷此結(jié)點(diǎn)是否為葉子結(jié)點(diǎn)。void BiTree二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)設(shè)計算法求二叉樹的深度.注：本算法也可以用二叉樹遍歷的所有算法。但是在用前序和中序算法時

16、要注意深度如何來確定。int BiTree二depth(BiNode<T> *rt) if (rt =NULL) return 0;else hl= depth(rt->lchild);hr= depth(rt->rchild);return (hl>hr)hl+1:hr+1;(4)設(shè)計算法：輸出二叉樹后序遍歷的逆序.解法思想：太簡單啦！ ！ ！前序遍歷是先遍歷右子樹即可void BiTree二PostOrder_1(BiNode<T> *rt)if (rt=NULL) return;else cout<<rt->data;PostO

17、rder(rt->rchild);PostOrder(rt->lchild); (5)以二叉鏈表為存儲結(jié)構(gòu)，編寫算法求二叉樹中值x的結(jié)點(diǎn)的雙親.void BiTree:PreOrder_Parent(BiNode<T> *rt)top= -1; p=rt;void BiTree二DeleteX(BiNode<T> *rt, T x) if(rt=NULL) return;if(rt->data=x) Release(rt);elseDeleteX(rt->lchild, x);DeleteX(rt->rchild, x);(7) 一棵具有n

18、個結(jié)點(diǎn)的二叉樹采用順序存儲結(jié)構(gòu)，編寫算法對該二叉樹進(jìn)行前序遍歷.算法思想：套用前序遍歷的原程序，注意查找左右孩子結(jié)點(diǎn)的地址和判別孩子是否存在的方法。注：根結(jié)點(diǎn)的下標(biāo)是1。void BiTree二PreOrder_Seq(int rt)top= -1; p=rt;解法思想：使用任何遍歷算法，把“ cout<<rt- >data”改成左右孩子指針交換即可。void BiTree二PostOrderChange(BiNode<T> *rt)if (rt=NULL) return; else PostOrder(rt->lchild);PostOrder(rt-&g

19、t;rchild);temp=rt->lchild;rt->lchild=rt->rchild;rt->rchild=temp; 習(xí)題61 .填空題設(shè)無向圖G中頂點(diǎn)數(shù)為n,則圖G至少有(0 )條邊，至多有(n(n-1)/2 )條邊；若G為有向圖， 則至少有(0)條邊，至多有(n(n-1)條邊。 任何連通圖的連通分量只有一個，即是(它本身)。圖的存儲結(jié)構(gòu)主要有兩種，分別是(鄰接矩陣)和(鄰接表)。 已知無向圖G的頂點(diǎn)數(shù)為n ,邊數(shù)為e,其鄰接表表示的空間復(fù)雜度為( O(n+e)。 已知一個圖的鄰接矩陣表示，計算第j個頂點(diǎn)的入度的方法是(矩陣中第j-1列的非0元素個數(shù))c

20、有向圖G用鄰接矩陣A n n存儲，其第1行的所有元素之和等于頂點(diǎn)1的(出度)。 圖的深度優(yōu)先遍歷類似于樹的(前序)遍歷，它所用的數(shù)據(jù)結(jié)構(gòu)是(棧)；圖的廣度優(yōu)先遍歷類似于樹的(層序)遍歷，它所用的數(shù)據(jù)結(jié)構(gòu)是(隊(duì)列)。 對于含有n個頂點(diǎn)e條邊的連通圖，利用P rim算法求最小生成樹的時間復(fù)雜度為(O(n2),利用Kruscal算法求最小生成樹的時間復(fù)雜度為(O(elog2e)。 如果一個有向圖不存在(有向回路)，則該圖的全部頂點(diǎn)可以排成一個拓?fù)湫蛄小Ｔ谝粋€有向圖中，若存在弧<Vi ,v j >、<Vj ,v k >、<Vi ,v k > ,則在其拓?fù)湫蛄兄?，頂點(diǎn)

21、 v i ,v j , Vk的相對次序?yàn)?vi ,v j , v k )。2 .選擇題：(1) C (2) A,G (3) C (4) B (5) D (6) C,F B (8) D (9) A (10) A (11) A (12) C (13) A (14) C,C,F (15) B4.解答下列問題(1) n個頂點(diǎn)的無向圖，采用鄰接表存儲，回答下列問題：圖中有多少條邊答：鄰接表中所有邊表結(jié)點(diǎn)的個數(shù)的一半.任意兩個頂點(diǎn)i和j是否有邊相連答：查找第i個邊表的結(jié)點(diǎn)中是否有鄰接點(diǎn)域值為j的結(jié)點(diǎn).如果有，則它們之間有邊；否則，無邊.任意一個頂點(diǎn)的度是多少答：此頂點(diǎn)對應(yīng)的邊表中結(jié)點(diǎn)的個數(shù).(2) n個頂

22、點(diǎn)的無向圖，采用鄰接矩陣存儲，回答下列問題：圖中有多少條邊答：鄰接矩陣中所有元素和的一半.任意兩個頂點(diǎn)i和j是否有邊相連答：如果第i行第j列的元素值為1,則它們之間有邊；否則，無邊.任意一個頂點(diǎn)的度是多少答：此頂點(diǎn)對應(yīng)的行中元素之和.(3)證明：生成樹中最長路徑的起點(diǎn)和終點(diǎn)的度均為1.證明：設(shè)一棵樹的最長路徑 P=viv2 - Vko若V1的度至少為2,不妨設(shè)U(WV2)是它的另外一個鄰點(diǎn)。若 uCVi, V 2,，v k,則此樹中包含圈，矛盾；否則UVWVk是一條更長的路，同樣矛盾。所以V1的度為1.類似可以證明Vk的度為1.(5)圖6-50所示是一個無向帶權(quán)圖，請分別用P rim算法和K

23、ruscal算法求最小生成樹。9v1.0可編輯可修改解:PrimVZiZ習(xí)題71 .填空題(1)順序查找技術(shù)適合于存儲結(jié)構(gòu)為(各種形式)的線性表，而折半查找技術(shù)適合于存儲結(jié)構(gòu)為(順 序存儲)的線性表，并且表中的元素必須是(有序的)。(2)設(shè)有一個已按各元素值排好序的線性表，長度為 125,用折半查找法查找與給定值相等的元素， 若查找成功，則至少需要比較(1 )次，至多需要比較(7)次。(3)對于數(shù)列25, 30, 8, 5, 1,27, 24, 10, 20, 21,9, 28, 7, 13, 15,假定每個結(jié)點(diǎn)的查找概率相同，若用順序存儲結(jié)構(gòu)組織該數(shù)列，則查找一個數(shù)的平均比較次數(shù)為(8 )。

24、若按二叉排序樹組織該數(shù)列，則查找一個數(shù)的平均比較次數(shù)為(59/15)。(4)長度為20的有序表采用折半查找，共有(4)個元素的查找長度為3。(5)假設(shè)數(shù)列25, 43, 62, 31, 48, 56,采用散列函數(shù)為H(k)=k mod7,則元素48的同義詞是(62)(6)在散列技術(shù)中，處理沖突的主要方法是(開放地址法)和(拉鏈法)。(7)在各種查找方法中，平均查找長度與結(jié)點(diǎn)個數(shù)無關(guān)的查找方法是(散列查找)。(8)與其他方法比較，散列查找法的特點(diǎn)是(記錄的存儲位置與關(guān)鍵碼之間建立了一個確定的對應(yīng)關(guān) 系，平均查找長度與結(jié)點(diǎn)個數(shù)無關(guān))。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)中進(jìn)行折半查找關(guān)鍵碼e和g的過程。解：d->f->e 和 d->f->g 10v1.0可編輯可修改12(2) 畫出長度為10的折半查找判定樹，并求出等概率時查找成功和不成功的平均查找長度。cn 回 ElI ED 臼 013Tl b；