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

1、v1.0可編輯可修改習(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)）和（圖）o（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)系）0（5）算法具有5個(gè)特性，分別是（輸入）、（輸出）、（有窮性）、（確定性）、（可行性）。（6）算法的描述方法通常有（自然語(yǔ)言）、（

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

3、個(gè)數(shù)據(jù)元素的長(zhǎng)度是2，則第5個(gè)數(shù)據(jù)元素的存儲(chǔ)地址是（108） o（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)一 ）。 非空的循環(huán)單鏈表由頭指針head指示，則其尾結(jié)點(diǎn)（由指針p所指）滿足（p->next=head ）。在有尾指針rear指示的循環(huán)單鏈表中，在表尾插入一個(gè)結(jié)點(diǎn)s的操作序列是（s->nex

4、t=rear->next;rear->next=s; rear=s ），刪除開(kāi)始結(jié)點(diǎn)的操作序歹U是 （q=rear->next->next;rear->n ext- >n ext=q->n ext; 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ù)雜性為(0(1);在給 定值x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜性為(0(n)。(8) 可由一個(gè)尾指針惟一確定的鏈表有(循環(huán)鏈表)、(雙鏈表)、(雙循環(huán)鏈表)。2.選擇題： A,B (2) D (3) B A (5) A (6) D (7)

5、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+T-an -> a k+TanaTak,可以先讓 aTakak+T_an->aka1an_ak+1,再讓 aka 1anak+1 -> a k+1ana1ak ,參見(jiàn)第1章16頁(yè)的思想火花算法：void converse(T a, int i, int j)for(s=i; s<=(i+j)/2;s+)解法 1: void tiaozhen(T A,in

6、t n) s=0; t=n-1;while(s<t) while( As%2!=0) s+;鏈表的程序如下，設(shè)單鏈表有表頭結(jié)點(diǎn).void Lin kList:c on verse() p=first- >n ext;first-> next=NULL;while(p)q=p->n ext; p->n ext=first- >n ext;first- >n ext=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 Li nkList:deleteS(Node&

7、lt;T> *s)p=s； while(p->n ext- >n ext!=s) p=p->n ext; q=p->n ext; p->n ext=q->n ext;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> *shu

8、zi, Node<T> *qita) s=new Node<T> s->n ext=s; zifu=s;s=new Node<T> s->n ext=s; shuzi=s;s=new Node<T> s->n ext=s; qita=s;a=zifu; b=shuzi; c=qita;p=first->next;選擇題:(1) C (2) D (3) C B (5) B (6) B (7) D (8) A (9)C4.解答下列問(wèn)題(1) 不可以，因?yàn)橛行蛄蠧, A, B.(2) 可以,push, push, push, p

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

10、一般壓縮存儲(chǔ)方法有兩種，分別是(三元組順序表)和(十字鏈表)。2.選擇題： B D, E, K (3) B XXX (5) D C (7) D5(2).設(shè)計(jì)一個(gè)求矩陣A=j)nXm所有鞍點(diǎn)的算法，并分析最壞情況下的時(shí)間復(fù)雜度。算法思想2：附加兩個(gè)數(shù)組Bn和Cm，Bi用來(lái)存第i行的最小值，Cj用來(lái)存第j列的最小元素值。如果Aij= Bi=Cj ，則Aij一定為馬鞍點(diǎn)。viod maan dia n2(A ,i nt m,i nt n)in t Bn ,Cm,i,j;for(i=0;i< n;i+) 一棵二叉樹(shù)的第i (i > 1)層上最多有(2i-1 )個(gè)結(jié)點(diǎn),一棵有n(n>0

11、)個(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 )。 深度為k的二叉樹(shù)中，所含葉子的個(gè)數(shù)最多為(2k-1).(6)具有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的葉子結(jié)點(diǎn)數(shù)為(50)。 已知一棵度為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中序遍歷序列是CBDAFG測(cè)其后序遍歷序列是 (CDBGFEA)。(9) 在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，共有( 2n )個(gè)

12、指針域，其中(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)題 已知一棵度為m的樹(shù)中：ni個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，nm個(gè)度為m的結(jié)點(diǎn)，問(wèn)該 樹(shù)中共有多少個(gè)葉子結(jié)點(diǎn)解：設(shè)該樹(shù)中共有no個(gè)葉子結(jié)點(diǎn)。則該樹(shù)中總結(jié)點(diǎn)個(gè)數(shù)為n= no+ n 1 + n m.而分支數(shù)為

13、n-仁n 1 +2n2+3n3 + mnm,所以n0 =1+ n2 +2n 3 + (m -1) nm(4)已知一棵二叉樹(shù)的中序和后序序列為 CBEDAFIG和CEDBIFHG/試構(gòu)造該二叉樹(shù)14 給出葉子結(jié)點(diǎn)的權(quán)值集合為 W=5,2,9,11,8,3,7的哈夫曼樹(shù)的構(gòu)造過(guò)程(1)算法設(shè)計(jì)4519 I13)設(shè)計(jì)算法求二叉樹(shù)的結(jié)點(diǎn)個(gè)數(shù).注：本算法可以用二叉樹(shù)遍歷的所有算法，只要把cout語(yǔ)句換成結(jié)點(diǎn)的計(jì)數(shù)就可以了，但是要注意遞歸中的計(jì)數(shù)變量應(yīng)該是外部變量。如int num=O;int BiTree:count(BiNode<T> *rt) countsub(rt); return n

14、um;void BiTree:cou ntSub(BiNode<T> *rt) if (rt !=NULL) num+; countSub (rt->lchild); countSub (rt->rchild); 其他解法二：用前序遍歷的非遞歸算法int BiTree:Cou ntPreOrder(BiNode<T> *rt)top= -1; p=rt; num=0;注:其實(shí)按照“選擇題”的(7)知:任何一棵二叉樹(shù)的葉子結(jié)點(diǎn)在前序、中序、后序遍歷序列中的相對(duì) 次序肯定不發(fā)生改變解法思想：使用任何遍歷算法，把“ cout«rt- >data ”

15、改成判斷此結(jié)點(diǎn)是否為葉子結(jié)點(diǎn)。void BiTree:leaf(BiNode<T> *rt)if (rt=NULL) retur n;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) if (

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

17、鏈表為存儲(chǔ)結(jié)構(gòu)，編寫(xiě)算法求二叉樹(shù)中值x的結(jié)點(diǎn)的雙親.void BiTree:PreOrder_Pare nt(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個(gè)結(jié)點(diǎn)的二叉樹(shù)采用順序存儲(chǔ)結(jié)構(gòu)，編寫(xiě)算法對(duì)該二叉樹(shù)進(jìn)行前序遍歷.算法思想：套用前序遍歷的原程序，注意

18、查找左右孩子結(jié)點(diǎn)的地址和判別孩子是否存在的方法。 注：根結(jié)點(diǎn)的下標(biāo)是1。void BiTree:PreOrder_Seq(i nt rt)top= -1; p=rt;解法思想：使用任何遍歷算法，把“ cout«rt- >data ”改成左右孩子指針交換即可。void BiTree:PostOrderCha nge(BiNode<T> *rt)if (rt=NULL) retur n;else PostOrder(rt->lchild);PostOrder(rt->rchild); temp=rt->lchild; rt->lchild=rt-

19、>rchild; rt->rchild=temp; 4.解答下列問(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ù). n個(gè)頂點(diǎn)的無(wú)向圖，采用鄰接矩陣存儲(chǔ)，回答下列問(wèn)題： 圖中有多少條邊答：鄰接矩陣中所有元素和的一半. 任意兩個(gè)頂點(diǎn)i和j是否有邊相連答：如果第i行第j列的元素值為1,則它們之間有邊；否則,無(wú)邊. 任意一個(gè)頂點(diǎn)的度是多少答：此頂

20、點(diǎn)對(duì)應(yīng)的行中元素之和.(3)證明：生成樹(shù)中最長(zhǎng)路徑的起點(diǎn)和終點(diǎn)的度均為1.證明：設(shè)一棵樹(shù)的最長(zhǎng)路徑 P=vmv。若vi的度至少為2,不妨設(shè)u( Mv)是它的另外一個(gè)鄰點(diǎn)。若 u v 1, v 2,v k,則此樹(shù)中包含圈，矛盾；否則UV1V2Vk是一條更長(zhǎng)的路，同樣矛盾。所以V1的度為1.類(lèi)似可以證明vk的度為1. 圖6-50所示是一個(gè)無(wú)向帶權(quán)圖，請(qǐng)分別用P rim算法和K ruscal算法求最小生成樹(shù)。W： PrimVZiZ(r/.O)(/：2)習(xí)題71. 填空題(1) 順序查找技術(shù)適合于存儲(chǔ)結(jié)構(gòu)為(各種形式)的線性表，而折半查找技術(shù)適合于存儲(chǔ)結(jié)構(gòu)為(順序存儲(chǔ))的線性表，并且表中的元素必須是(

21、有序的)。(2) 設(shè)有一個(gè)已按各元素值排好序的線性表，長(zhǎng)度為 125,用折半查找法查找與給定值相等的元素， 若查找成功，則至少需要比較(1 )次，至多需要比較 次。(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

22、(k)=k mod7,則元素48的同義詞是(62)(6) 在散列技術(shù)中，處理沖突的主要方法是(開(kāi)放地址法)和(拉鏈法)。(7) 在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān)的查找方法是(散列查找)。(8) 與其他方法比較，散列查找法的特點(diǎn)是(記錄的存儲(chǔ)位置與關(guān)鍵碼之間建立了一個(gè)確定的對(duì)應(yīng)關(guān)系，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)無(wú)關(guān))。2. 選擇題：(1) B (2) D,D (3) A,B D (5) A C (7) C (8) B (9) D (10) A (11)C (12) C4 解答下列問(wèn)題(1)分別畫(huà)出在線性表(a,b,c,d,e,f,g)中進(jìn)行折半查找關(guān)鍵碼e和g的過(guò)程。解：d->f-&

23、gt;e 和 d->f->g(2) 畫(huà)出長(zhǎng)度為10的折半查找判定樹(shù)，并求出等概率時(shí)查找成功和不成功的平均查找長(zhǎng)度。cn 自 ElI ED 自 0/ / / H I L I I6-了 血蘭 I 仙I等概率時(shí)查找成功平均查找長(zhǎng)度 =(1*1+2*2+4*3+3*4)/10=29/10等概率時(shí)不成功的平均查找長(zhǎng)度 =(5*4+6*5)/11=50/11 將數(shù)列(24,15,38,27,76,130,121)的各個(gè)元素依次插入一顆初始為空的二叉排序樹(shù)中，請(qǐng)畫(huà)出最后的結(jié)果并求等概率情況下查找成功的平均查找長(zhǎng)度。AVL=(1+2*2+3*3+4+5)/7已知一棵二叉排序樹(shù)的結(jié)構(gòu)如圖7-30所示

24、，結(jié)點(diǎn)的值為18,請(qǐng)標(biāo)出各點(diǎn)的值。答：見(jiàn)題上圖習(xí)題81.填空題(1)排序的主要目的是為了以后對(duì)已排序的數(shù)據(jù)元素進(jìn)行(查找)。 對(duì)n個(gè)元素進(jìn)行起泡排序，在(關(guān)鍵碼有序)的情況下比較的次數(shù)最少，其比較次數(shù)為(0(n)< 在(關(guān)鍵碼逆序)情況下比較次數(shù)最多，其比較次數(shù)為(O(n2)。 對(duì)一組記錄(54,38,96,23,15,72,60,45,83)進(jìn)行直接插入排序，當(dāng)把第 7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需比較(3 )次。 對(duì)一組記錄(54,38,96,23,15,72,60,45,83)進(jìn)行快速排序，在遞歸調(diào)用中使用的棧所能達(dá)到的最大深度為(4 )。 對(duì)n個(gè)待排序記錄序列進(jìn)行快速排序，所需要的最好時(shí)間是(0(nlog2n )，最壞時(shí)間是(0(n?)。(6) 利用簡(jiǎn)單選擇排序?qū)個(gè)記錄進(jìn)行排序，最壞情況下，記錄交換的次數(shù)為(n-1)(7) 如果要將序列(50,16,23,68,94,70,73)建成堆，只需把16與(50 )交換。(8)