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

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

2、方法通常有(自然語(yǔ)言)、(流程圖)、(程序設(shè)計(jì)語(yǔ)言)、(偽代碼)4種，其中，(偽代碼)被稱為算法語(yǔ)言。(7) 一般情況下，一個(gè)算法的時(shí)間復(fù)雜度是算法（輸入規(guī)模）的函數(shù)。(8) 設(shè)待處理問(wèn)題的規(guī)模為n,若一個(gè)算法的時(shí)間復(fù)雜度為一個(gè)常數(shù)，則表示成數(shù)量級(jí)的形式為(O(1)，若為n*log25n, 則表示成數(shù)量級(jí)的形式為(O(n*log2n)。2. 選擇題: (1) C, D (2) B (3) B (4) A (5) D (6) A (7) C (8) C, E 習(xí)題二1. 填空題(1) 在順序表中，等概率情況下，插入和刪除一個(gè)元素平均需移動(dòng)(表長(zhǎng)的一半)個(gè)元素，具體移動(dòng)元素的個(gè)數(shù)與(表的長(zhǎng)度)和(

3、數(shù)據(jù)元素所在的位置)有關(guān)。(2) 一個(gè)順序表的第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)數(shù)據(jù)元素的長(zhǎng)度是2，則第5個(gè)數(shù)據(jù)元素的存儲(chǔ)地址是（108）。 (3) 設(shè)單鏈表中指針p指向單鏈表的一個(gè)非空結(jié)點(diǎn)A，若要?jiǎng)h除結(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)。(

4、6) 在有尾指針rear指示的循環(huán)單鏈表中，在表尾插入一個(gè)結(jié)點(diǎn)s的操作序列是（s->next=rear->next; rear->next=s; rear=s），刪除開(kāi)始結(jié)點(diǎn)的操作序列是（q=rear->next->next; rear->next->next=q->next; delete q;）。 注：假設(shè)此循環(huán)單鏈表有表頭結(jié)點(diǎn)(7) 一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表，在p所指結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)s的時(shí)間復(fù)雜性為（ O(1)）；在給定值x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜性為( O(n) ）。(8) 可由一個(gè)尾指針惟一確定的鏈表有(循環(huán)鏈表)、(雙鏈表

5、)、(雙循環(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. 算法設(shè)計(jì)(1) 設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為O(n)的算法。實(shí)現(xiàn)將數(shù)組An中所有元素循環(huán)左移k個(gè)位置。算法思想：要使a1akak+1an -> ak+1ana1ak,可以先讓a1akak+1an->aka1anak+1,再讓ak a1 anak+1 -> ak+1ana1ak ，參見(jiàn)第1章16頁(yè)的思想火花算法：void converse(T a, int i, in

6、t j) for(s=i; s<=(i+j)/2;s+) /將數(shù)組a中從i到j(luò)中的元素倒置 temp=as;as=aj-s+i;aj-s+i=temp; void move(T a , k) converse(a,0,k-1);/3次調(diào)用函數(shù)converse converse(a,k,n-1); converse(a,0,n-1);11 / 15 (2) 已知數(shù)組An中的元素為整型，設(shè)計(jì)算法將其調(diào)整為左右兩部分，左邊所有元素為奇數(shù)，右邊所有元素為偶數(shù)，并要求算法的時(shí)間復(fù)雜度為O(n).解法1：void tiaozhen(T A,int n) s=0; t=n-1; while(s<

7、t) while( As%2!=0) s+;/s=s+1 while ( At%2=0) t-; if(s<t) temp=As;As=At;At=temp; 或 void tiaozhen(T A,int n) s=0; t=n-1; while(s<t) if(As%2!=0) s+;/s=s+1 else if(At%2=0) t-; else temp=As;As=At;At=temp; s+;t-; (3) 試編寫(xiě)在無(wú)頭結(jié)點(diǎn)的單鏈表上實(shí)現(xiàn)線性表的插入操作的算法,并和帶頭結(jié)點(diǎn)的單鏈表上的插入操作的實(shí)現(xiàn)進(jìn)行比較void LinkList_1:Insert(int i, T x

8、) if(i<=0) throw "輸入的插入位置值小于1" if(i=1)s=new Node<T> s->data=x; s->next=first; first=s; else p=first ; j=0; while (p && j<i-1) p=p->next; j+; if (!p) throw “插入位置值太大" else s=new Node<T> s->data=x; s->next=p->next; p->next=s; (4) 試分別以順序表和單鏈表

9、作存儲(chǔ)結(jié)構(gòu)，各寫(xiě)一實(shí)現(xiàn)線性表就地逆置的算法。算法思想：順序表的程序參見(jiàn)題（1）的converse.單鏈表的程序如下，設(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è)在長(zhǎng)度大于1的循環(huán)鏈表中，既無(wú)頭結(jié)點(diǎn)也無(wú)頭指針，s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫(xiě)算法刪除結(jié)點(diǎn)s的前驅(qū)結(jié)點(diǎn)。 void LinkList:deleteS(Node<T>

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

11、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; /設(shè)單鏈表帶頭結(jié)點(diǎn) while(p) q=p; p=p->next; if(q->data>='a'&&q->data<='z') |(q->data>

12、;='A'&& q->data<='A') q->next=a->next; a->next=q; a=q; else if(q->data>='0' && q->data<='9') q->next=b->next; b->next=q; b=q; else q->next=c->next; c->next=q; c=q; delete first;(7) 設(shè)單鏈表以非遞減有序排列，設(shè)計(jì)算法實(shí)現(xiàn)在單鏈表中刪除

13、相同的多余結(jié)點(diǎn)。解： void LinkList:deleteALL() p=first->next; /假設(shè)單鏈表帶表頭結(jié)點(diǎn)。 while(p) if(p->next!=NULL && p->next->data=p->data) q=p->next; p->next=q->next; delete q; else p=p->next; (8) 判斷帶頭結(jié)點(diǎn)的雙循環(huán)鏈表是否對(duì)稱。解 bool LinkList:equal(DulNode<T> *first) p=first->next; q=first-

14、>prior; while(p!=q&&p->prior!=q) if(p->data=q->data) p=p->next; q=q->prior; else return 0; return 1; -習(xí)題三1 填空題(1) 設(shè)有一個(gè)空棧，棧頂指針為1000H，經(jīng)過(guò)push、push、pop、push、pop、push、push后，棧頂指針為(1003H)。(2) 棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是(順序存儲(chǔ)結(jié)構(gòu)和鏈接存儲(chǔ)結(jié)構(gòu)順序棧和鏈棧)，其判定?？盏臈l件分別是(top=-1, top=NULL), 判斷棧滿的條件分別是(top=MaxSiz

15、e-1, 內(nèi)存滿/內(nèi)存無(wú)可用空間)。(3) (棧)可作為實(shí)現(xiàn)遞歸函數(shù)調(diào)用的一種數(shù)據(jù)結(jié)構(gòu)。(4) 表達(dá)式a*(b+c)-d的后綴表達(dá)式是(abc+*d-)。(5) 棧和隊(duì)列是兩種特殊的線性表，棧的操作特性是(后進(jìn)先出)，隊(duì)列的操作特性是(先進(jìn)先出)，棧和隊(duì)列的主要區(qū)別在于(插入、刪除運(yùn)算的限定不一樣 )。(6) 循環(huán)隊(duì)列的引入是為了克服( 假溢出 )。(7) 一維數(shù)組Datan用來(lái)表示循環(huán)隊(duì)，隊(duì)頭指針front和隊(duì)尾指針rear定義為整型變量，計(jì)算隊(duì)中元素個(gè)數(shù)的公式是( (rear-front+n)%n )。 (8) 用循環(huán)鏈表表示的隊(duì)列長(zhǎng)度為n，若只設(shè)頭指針，則出隊(duì)和入隊(duì)的時(shí)間復(fù)雜度分別是(

16、O(1) )和( O(n) )。2. 選擇題: (1) C (2) D (3) C (4) B (5) B (6) B (7) D (8) A (9) C 4.解答下列問(wèn)題(1) 不可以, 因?yàn)橛行蛄蠧, A, B. 可以, push, push, push, pop, pop, pop, push, pop, push, pop.(2) 見(jiàn)書(shū)本 (3) 棧頂元素是6, 棧底元素是1.(4) 隊(duì)尾元素是9, 隊(duì)頭元素是5. (5) 合法, 不合法.習(xí)題四1. 填空題(1) 串是一種特殊的線性表，其特殊性體現(xiàn)在( 數(shù)據(jù)元素的類(lèi)型為字符型 )。(2) 兩個(gè)串相等的充分必要條件是( 它們的長(zhǎng)度相等且

17、對(duì)應(yīng)位置的字符相同 )。 (3) 數(shù)組通常只有兩種運(yùn)算，分別是( 存取 )和( 修改 )，這決定了數(shù)組通常采用（ 順序存儲(chǔ)）結(jié)構(gòu)來(lái)實(shí)現(xiàn)存儲(chǔ)。(4) (1140)(5)設(shè)有一個(gè)10階的對(duì)稱矩陣A采用壓縮存儲(chǔ)，第一個(gè)元素A00的存儲(chǔ)地址為d， 每個(gè)元素占用1個(gè)地址空間，則元素A85的存儲(chǔ)地址為( d+41 )。 (6) 稀疏矩陣一般壓縮存儲(chǔ)方法有兩種，分別是( 三元組順序表 )和( 十字鏈表 )。 2. 選擇題: (1) B (2) D, E, K (3) B (4) XXX (5) D (6) C (7) D5(2). 設(shè)計(jì)一個(gè)求矩陣A=(aij)nXm所有鞍點(diǎn)的算法，并分析最壞情況下的時(shí)間復(fù)雜

18、度。 算法思想2：附加兩個(gè)數(shù)組Bn和Cm，Bi用來(lái)存第i行的最小值，Cj用來(lái)存第j列的最小元素值。如果Aij= Bi=Cj，則Aij一定為馬鞍點(diǎn)。viod maandian2(A ,int m,int n)int Bn,Cm,i,j;for(i=0;i<n;i+) /求第i行的最小值, 記入Bi Bi=Ai0; for(j=1;j<m;j+) if(Bi>Aij) Bi=Aij;for(j=0;j<m;j+) /求第j列的最大值, 記入Cj Cj=A0j; for(i=1;i<n;i+) if(Cj<Aij) Cj=Aij;for(i=0;i<n;i+

19、) /求馬鞍點(diǎn)for(j=0;j<m;j+) if (Bi=Aij&&Cj=Aij) cout<<i<<j<<Aij;算法復(fù)雜度：O(mn)。從時(shí)間復(fù)雜度的冪的角度來(lái)說(shuō)這個(gè)算法是最好的，因?yàn)槟闱篑R鞍點(diǎn)必須要搜索所有的Aij。 習(xí)題五1 填空題(1)樹(shù)是n（n0）個(gè)結(jié)點(diǎn)的有限集合。在一棵非空樹(shù)中，有（且僅有一個(gè)）根結(jié)點(diǎn)，其余結(jié)點(diǎn)分成m（m>=0）個(gè)(互不相交)的有限集合，每個(gè)集合又是一棵樹(shù)。(2) 樹(shù)中某結(jié)點(diǎn)的子樹(shù)的個(gè)數(shù)稱為該結(jié)點(diǎn)的（ 度 ），子樹(shù)的根結(jié)點(diǎn)稱為這個(gè)結(jié)點(diǎn)的( 孩子結(jié)點(diǎn) ),該結(jié)點(diǎn)稱為其子樹(shù)根結(jié)點(diǎn)的（雙親結(jié)點(diǎn)）. (3)

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

21、歷序列是CBDAFGE,則其后序遍歷序列是( CDBGFEA )。 (9)在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，共有（ 2n )個(gè)指針域，其中( n-1 )個(gè)指針域用于指向其左右孩子，剩下的( n+1 )個(gè)指針域則是空的。 (10)在有n個(gè)葉子的哈夫曼樹(shù)中，葉子結(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. 解答下列問(wèn)題(3) 已知一棵度為m的樹(shù)中：n1個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，n

22、m個(gè)度為m的結(jié)點(diǎn)，問(wèn)該樹(shù)中共有多少個(gè)葉子結(jié)點(diǎn)？解：設(shè)該樹(shù)中共有n0個(gè)葉子結(jié)點(diǎn)。則該樹(shù)中總結(jié)點(diǎn)個(gè)數(shù)為 n= n0+ n1 + nm.而分支數(shù)為n-1= n1 +2n2 +3n3 + mnm,所以 n0 =1+n2 +2n3 + (m-1)nm (4) 已知一棵二叉樹(shù)的中序和后序序列為CBEDAFIGH和CEDBIFHGA,試構(gòu)造該二叉樹(shù)。(5) 給出葉子結(jié)點(diǎn)的權(quán)值集合為W=5,2,9,11, 8,3,7的哈夫曼樹(shù)的構(gòu)造過(guò)程。 5 算法設(shè)計(jì)(1) 設(shè)計(jì)算法求二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù). 注：本算法可以用二叉樹(shù)遍歷的所有算法，只要把cout語(yǔ)句換成結(jié)點(diǎn)的計(jì)數(shù)就可以了，但是要注意遞歸中的計(jì)數(shù)變量應(yīng)該是外部變量。

23、如 int num=0;int BiTree: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;/采用順序棧s，并假定不會(huì)發(fā)生上溢 while (

24、p!=NULL | | top!= -1) while (p!= NULL) /找此結(jié)點(diǎn)的最左邊的后代 num+; /訪問(wèn) s+top=p; /此結(jié)點(diǎn)進(jìn)棧 p=p->lchild; /轉(zhuǎn)移到左兒子子樹(shù) if (top!= -1) p=stop-; p=p->rchild; return num; / cout<<num(2) 設(shè)計(jì)算法按照前序次序打印二叉樹(shù)中的葉子結(jié)點(diǎn). 注:其實(shí)按照“選擇題”的(7)知:任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在前序、中序、后序遍歷序列中的相對(duì)次序肯定不發(fā)生改變 解法思想: 使用任何遍歷算法，把“cout<<rt->data”改成判斷

25、此結(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è)計(jì)算法求二叉樹(shù)的深度. 注：本算法也可以用二叉樹(shù)遍歷的所有算法。但是在用前序和中序算法時(shí)要注意深度如何來(lái)確定。 int BiTree:depth(BiNode<T> *rt)

26、if (rt =NULL) return 0; else hl= depth(rt->lchild); hr= depth(rt->rchild); return (hl>hr)?hl+1:hr+1; (4) 設(shè)計(jì)算法:輸出二叉樹(shù)后序遍歷的逆序. 解法思想: 太簡(jiǎn)單啦！ 前序遍歷是先遍歷右子樹(shù)即可.void BiTree:PostOrder_1(BiNode<T> *rt) if (rt=NULL) return; else cout<<rt->data; PostOrder(rt->rchild); PostOrder(rt->lc

27、hild); (5) 以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，編寫(xiě)算法求二叉樹(shù)中值x的結(jié)點(diǎn)的雙親. void BiTree:PreOrder_Parent(BiNode<T> *rt) top= -1; p=rt;/采用順序棧s，并假定不會(huì)發(fā)生上溢 while (p!=NULL | | top!= -1) while (p!= NULL) if(rt->lchild!=NULL &&rt->lchild->data=x) cout<<rt->data; if(rt->rchild!=NULL &&rt->rchild-&

28、gt;data=x) cout<<rt->data; s+top=p; /此結(jié)點(diǎn)進(jìn)棧 p=p->lchild; /轉(zhuǎn)移到左兒子子樹(shù) if (top!= -1) p=stop-; p=p->rchild; (6) 以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，在二叉樹(shù)中刪除以值x為根結(jié)點(diǎn)的子樹(shù). void BiTree:DeleteX(BiNode<T> *rt, T x) if(rt=NULL) return; if(rt->data=x) Release(rt); else DeleteX(rt->lchild, x); DeleteX(rt->rchil

29、d, x); (7) 一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)，編寫(xiě)算法對(duì)該二叉樹(shù)進(jìn)行前序遍歷. 算法思想: 套用前序遍歷的原程序，注意查找左右孩子結(jié)點(diǎn)的地址和判別孩子是否存在的方法。注：根結(jié)點(diǎn)的下標(biāo)是1。 void BiTree:PreOrder_Seq(int rt) top= -1; p=rt; /采用順序棧s，并假定不會(huì)發(fā)生上溢 while (p<=length)&&(Ap!=“ ”) | | top!= -1) while (p<=length)&&( Ap!=“ ”) /找此結(jié)點(diǎn)的最左邊的后代 cout<<Ap; /訪問(wèn) s+

30、top=p; /此結(jié)點(diǎn)進(jìn)棧 p=2*p; /轉(zhuǎn)移到左兒子子樹(shù) if (top!= -1) p=stop-; p=2*p+1; (8) 編寫(xiě)算法交換二叉樹(shù)中所有結(jié)點(diǎn)的左右子樹(shù). 解法思想: 使用任何遍歷算法，把“cout<<rt->data”改成左右孩子指針交換即可。 void BiTree:PostOrderChange(BiNode<T> *rt) if (rt=NULL) return; else PostOrder(rt->lchild); PostOrder(rt->rchild); temp=rt->lchild; rt->lch

31、ild=rt->rchild; rt->rchild=temp; 習(xí)題6 1.填空題設(shè)無(wú)向圖G中頂點(diǎn)數(shù)為，則圖G至少有（0 ）條邊，至多有（ n(n-1)/2）條邊；若G為有向圖，則至少有（ 0）條邊，至多有（ n(n-1)）條邊。 任何連通圖的連通分量只有一個(gè)，即是（它本身）。 圖的存儲(chǔ)結(jié)構(gòu)主要有兩種，分別是（鄰接矩陣）和（鄰接表）。 已知無(wú)向圖的頂點(diǎn)數(shù)為，邊數(shù)為，其鄰接表表示的空間復(fù)雜度為（O(n+e)）。 已知一個(gè)圖的鄰接矩陣表示，計(jì)算第個(gè)頂點(diǎn)的入度的方法是（矩陣中第j-1列的非0元素個(gè)數(shù)）。 有向圖用鄰接矩陣存儲(chǔ)，其第行的所有元素之和等于頂點(diǎn)的（出度）。 圖的深度優(yōu)先遍歷類(lèi)

32、似于樹(shù)的（前序）遍歷，它所用的數(shù)據(jù)結(jié)構(gòu)是（棧）；圖的廣度優(yōu)先遍歷類(lèi)似于樹(shù)的（層序）遍歷，它所用的數(shù)據(jù)結(jié)構(gòu)是（隊(duì)列）。 對(duì)于含有個(gè)頂點(diǎn)條邊的連通圖，利用rim算法求最小生成樹(shù)的時(shí)間復(fù)雜度為（O(n2)），利用Kruscal算法求最小生成樹(shù)的時(shí)間復(fù)雜度為（O(elog2e)）。 如果一個(gè)有向圖不存在（有向回路），則該圖的全部頂點(diǎn)可以排成一個(gè)拓?fù)湫蛄小?在一個(gè)有向圖中，若存在弧<vi ,vj >、<vj ,vk >、<vi ,vk >，則在其拓?fù)湫蛄兄校旤c(diǎn) vi ,vj , vk 的相對(duì)次序?yàn)椋╲i ,vj , vk ）。 2. 選擇題: (1) C (2) A

33、,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. 解答下列問(wèn)題 (1) n個(gè)頂點(diǎn)的無(wú)向圖,采用鄰接表存儲(chǔ),回答下列問(wèn)題: 圖中有多少條邊?答: 鄰接表中所有邊表結(jié)點(diǎn)的個(gè)數(shù)的一半. 任意兩個(gè)頂點(diǎn)i和j是否有邊相連?答: 查找第i個(gè)邊表的結(jié)點(diǎn)中是否有鄰接點(diǎn)域值為j的結(jié)點(diǎn). 如果有,則它們之間有邊;否則,無(wú)邊. 任意一個(gè)頂點(diǎn)的度是多少?答: 此頂點(diǎn)對(duì)應(yīng)的邊表中結(jié)點(diǎn)的個(gè)數(shù). (2) n個(gè)頂點(diǎn)的無(wú)向圖,采用鄰接矩陣存儲(chǔ),回答下列問(wèn)題: 圖中有多少條邊?答: 鄰接矩陣

34、中所有元素和的一半. 任意兩個(gè)頂點(diǎn)i和j是否有邊相連?答: 如果第i行第j列的元素值為1,則它們之間有邊;否則,無(wú)邊. 任意一個(gè)頂點(diǎn)的度是多少?答: 此頂點(diǎn)對(duì)應(yīng)的行中元素之和. (3) 證明：生成樹(shù)中最長(zhǎng)路徑的起點(diǎn)和終點(diǎn)的度均為1.證明：設(shè)一棵樹(shù)的最長(zhǎng)路徑P=v1v2vk。若v1的度至少為2，不妨設(shè)u(v2)是它的另外一個(gè)鄰點(diǎn)。若uv1, v2, , vk, 則此樹(shù)中包含圈，矛盾；否則uv1v2vk是一條更長(zhǎng)的路，同樣矛盾。所以v1的度為1. 類(lèi)似可以證明vk的度為1. (5) 圖6-50所示是一個(gè)無(wú)向帶權(quán)圖，請(qǐng)分別用rim算法和ruscal算法求最小生成樹(shù)。 習(xí)題71. 填空題 (1) 順序

35、查找技術(shù)適合于存儲(chǔ)結(jié)構(gòu)為（各種形式）的線性表，而折半查找技術(shù)適合于存儲(chǔ)結(jié)構(gòu)為（順序存儲(chǔ)）的線性表，并且表中的元素必須是（有序的）。(2) 設(shè)有一個(gè)已按各元素值排好序的線性表，長(zhǎng)度為125，用折半查找法查找與給定值相等的元素，若查找成功，則至少需要比較(1 )次，至多需要比較(7)次。(3) 對(duì)于數(shù)列25, 30, 8, 5, 1, 27, 24, 10, 20, 21, 9, 28, 7, 13, 15,假定每個(gè)結(jié)點(diǎn)的查找概率相同，若用順序存儲(chǔ)結(jié)構(gòu)組織該數(shù)列，則查找一個(gè)數(shù)的平均比較次數(shù)為（8 ）。若按二叉排序樹(shù)組織該數(shù)列，則查找一個(gè)數(shù)的平均比較次數(shù)為（59/15）。(4) 長(zhǎng)度為20的有序表采用折半查找，共有（4）個(gè)元素的查找長(zhǎng)度為3。(5) 假設(shè)數(shù)列25, 43, 62, 31, 48, 56,采用散列函數(shù)為H(k)=k mod 7, 則元素48的同義詞是（62）。(6) 在散列技術(shù)中，處理沖突的主要方法是（開(kāi)放