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

1、習(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))、(樹結(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) 算法的描述方法通常有(自然語言)、(流程圖)、

2、(程序設(shè)計(jì)語言)、(偽代碼)4種，其中，(偽代 碼)被稱為算法語言。(7) 一般情況下，一個(gè)算法的時(shí)間復(fù)雜度是算法(輸入規(guī)模)的函數(shù)。(8) 設(shè)待處理問題的規(guī)模為n,假設(shè)一個(gè)算法的時(shí)間復(fù)雜度為一個(gè)常數(shù)，那么表示成數(shù)量級(jí)的形式為(0(1)，假設(shè)為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)(表長的一半)個(gè)元素，具體移動(dòng)元 素的個(gè)數(shù)與(表的長度)和(數(shù)據(jù)元素所在的位置)有關(guān)。(2) 一個(gè)順序表的第一個(gè)元素的存儲(chǔ)地址是1

3、00，每個(gè)數(shù)據(jù)元素的長度是2，那么第5個(gè)數(shù)據(jù)元素的存儲(chǔ)地址是(108) o(3) 設(shè)單鏈表中指針p指向單鏈表的一個(gè)非空結(jié)點(diǎn)A,假設(shè)要?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-next=rear-next;rear-next=s

4、; rear=s )，刪除開始結(jié)點(diǎn)的操作序歹U是 (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) )o(8) 可由一個(gè)尾指針惟一確定的鏈表有(循環(huán)鏈表)、(雙鏈表)、(雙循環(huán)鏈表)。2. 選擇題： A,B (2) D (3) B A (5) A (6) D (7) B (8) B (9) C (10) B (11)B (12) D (13) A (14) A5.

5、算法設(shè)計(jì)(1) 設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為O(n)的算法。實(shí)現(xiàn)將數(shù)組An中所有元素循環(huán)左移k個(gè)位置。算法思想：要使 a1akak+1an - a k+1aaak,可以先讓 a1akak+1an-aka1anak+1,再讓 aka 1 anak+1 - a k+1ana1ak ，參見第1章16頁的思想火花算法：void converse(T a, int i, int j)for(s=i; s=(i+j)/2;s+)解法 1: void tiaozhen(T A,int n) s=0; t=n-1;while(sn ext;first-next=NULL;while(p)q=p-n ext; p-n

6、ext=first- n ext;first- n ext=p;p=q;(5) 假設(shè)在長度大于1的循環(huán)鏈表中，既無頭結(jié)點(diǎn)也無頭指針，s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試 編寫算法刪除結(jié)點(diǎn)s的前驅(qū)結(jié)點(diǎn)。void Li nkList:deleteS(Node *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ù)元素含有三類字符：字母、數(shù)字和其它字符。試編寫算法，構(gòu)造三個(gè)循環(huán) 鏈表，使每個(gè)循環(huán)鏈表中只含同一類字符。算法思想：1)構(gòu)造3個(gè)帶表頭結(jié)點(diǎn)的循環(huán)鏈表，分別為 zifu

7、，shuzi和qita ；2)遍歷單鏈表，按單鏈表中的當(dāng)前數(shù)據(jù)元素的分類插入相應(yīng)的鏈表void fl(Node* zifu, Node *shuzi, Node *qita) s=new Node; s-n ext=s; zifu=s;s=new Node; s-n ext=s; shuzi=s;s=new Node; 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.解答以下問題(1) 不可以，因?yàn)橛行蛄蠧, A, B. 可以

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

9、元素A85的存儲(chǔ)地址為(d+41)。(6) 稀疏矩陣一般壓縮存儲(chǔ)方法有兩種，分別是(三元組順序表)和(十字鏈表)。2. 選擇題：(1) B D, E, K (3) B XXX (5) D C (7) D5(2).設(shè)計(jì)一個(gè)求矩陣A=(aj) nXm所有鞍點(diǎn)的算法，并分析最壞情況下的時(shí)間復(fù)雜度。算法思想2：附加兩個(gè)數(shù)組Bn和Cm，Bi用來存第i行的最小值，Cj用來存第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 1)層上最多有(2i-1 )個(gè)結(jié)點(diǎn)，一棵有

10、n(n0)個(gè)結(jié)點(diǎn)的滿二叉樹共有(n+1)/2 )個(gè)葉子結(jié)點(diǎn)和(n-1)/2)個(gè)非終端結(jié)點(diǎn)。(4) 設(shè)高度為h的二叉樹只有度為0的和度為2的結(jié)點(diǎn)，該二叉樹的結(jié)點(diǎn)數(shù)可能到達(dá)的最大值是(2h-1 ),最小值是(2 h -1 )。 深度為k的二叉樹中，所含葉子的個(gè)數(shù)最多為(2k-1).(6)具有100個(gè)結(jié)點(diǎn)的完全二叉樹的葉子結(jié)點(diǎn)數(shù)為(50)。 一棵度為3的樹有2個(gè)度為1的結(jié)點(diǎn)，3個(gè)度為2的結(jié)點(diǎn)，4個(gè)度為3的結(jié)點(diǎn)。那么該樹有(12) 個(gè)葉子結(jié)點(diǎn)。(8) 某二叉樹的前序遍歷序列是ABCDEFG中序遍歷序列是CBDAFGBW其后序遍歷序列是 (CDBGFEA)。(9) 在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，共有( 2

11、n )個(gè)指針域，其中(n-1 )個(gè)指針域用于指向其左 右孩子，剩下的(n+1 )個(gè)指針域那么是空的。(10) 在有n個(gè)葉子的哈夫曼樹中，葉子結(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.解答以下問題 一棵度為m的樹中：m個(gè)度為1的結(jié)點(diǎn)，n2個(gè)度為2的結(jié)點(diǎn)，nm個(gè)度為m的結(jié)點(diǎn)，問該 樹中共有多少個(gè)葉子結(jié)點(diǎn)？解：設(shè)該樹中共有n。個(gè)葉子結(jié)點(diǎn)。那么該樹中總結(jié)點(diǎn)個(gè)數(shù)為n= n。+ n 1 + n m.

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

13、Tree:cou ntSub(BiNode *rt) if (rt !=NULL) num+; countSub (rt-lchild); countSub (rt-rchild); 其他解法二：用前序遍歷的非遞歸算法int BiTree:CountPreOrder(BiNode *rt)top= -1; p=rt; num=0;注:其實(shí)按照“選擇題的 (7) 知:任何一棵二叉樹的葉子結(jié)點(diǎn)在前序、中序、后序遍歷序列中的相對(duì) 次序肯定不發(fā)生改變解法思想 : 使用任何遍歷算法，把“ coutdata 改成判斷此結(jié)點(diǎn)是否為葉子結(jié)點(diǎn)。 void BiTree:leaf(BiNode *rt)if (r

14、t=NULL) return;else if(rt-lchild=NULL &!rt-rchild) coutdata;PostOrder(rt-lchild);PostOrder(rt-rchild); (3) 設(shè)計(jì)算法求二叉樹的深度 . 注：本算法也可以用二叉樹遍歷的所有算法。但是在用前序和中序算法時(shí)要注意深度如何來確定。 int BiTree:depth(BiNode *rt) if (rt =NULL) return 0;else hl= depth(rt-lchild);hr= depth(rt-rchild);return (hlhr)?hl+1:hr+1;(4) 設(shè)計(jì)算法 :輸出

15、二叉樹后序遍歷的逆序 . 解法思想 : 太簡單啦！ 前序遍歷是先遍歷右子樹即可 .void BiTree:PostOrder_1(BiNode *rt)if (rt=NULL) return;else coutdata;PostOrder(rt-rchild);PostOrder(rt-lchild); (5) 以二叉鏈表為存儲(chǔ)結(jié)構(gòu)，編寫算法求二叉樹中值 x 的結(jié)點(diǎn)的雙親 .void BiTree:PreOrder_Parent(BiNode *rt)top= -1; p=rt;void BiTree:DeleteX(BiNode *rt, T x) if(rt=NULL) return;if

16、(rt-data=x) Release(rt);elseDeleteX(rt-lchild, x);DeleteX(rt-rchild, x); (7) 一棵具有 n 個(gè)結(jié)點(diǎn)的二叉樹采用順序存儲(chǔ)結(jié)構(gòu)，編寫算法對(duì)該二叉樹進(jìn)行前序遍歷 . 算法思想 : 套用前序遍歷的原程序，注意查找左右孩子結(jié)點(diǎn)的地址和判別孩子是否存在的方法。 注：根結(jié)點(diǎn)的下標(biāo)是 1。void BiTree:PreOrder_Seq(int rt)top= -1; p=rt;解法思想 : 使用任何遍歷算法，把“ coutdata 改成左右孩子指針交換即可。void BiTree:PostOrderCha nge(BiNode *r

17、t)if (rt=NULL) retur n;else PostOrder(rt-lchild);PostOrder(rt-rchild);temp=rt-lchild;rt-lchild=rt-rchild;rt-rchild=temp; W： Prim算法(rrO) G30(況1)a 5)習(xí)題71. 填空題(1) 順序查找技術(shù)適合于存儲(chǔ)結(jié)構(gòu)為(各種形式)的線性表，而折半查找技術(shù)適合于存儲(chǔ)結(jié)構(gòu)為(順 序存儲(chǔ))的線性表，并且表中的元素必須是(有序的)。(2) 設(shè)有一個(gè)已按各元素值排好序的線性表，長度為 125,用折半查找法查找與給定值相等的元素， 假設(shè)查找成功，那么至少需要比擬(1 )次，至多

18、需要比擬 次。(3) 對(duì)于數(shù)列25, 30, 8, 5, 1,27, 24, 10, 20, 21,9, 28, 7, 13, 15,假定每個(gè)結(jié)點(diǎn)的查找概率相同，假設(shè)用順序存儲(chǔ)結(jié)構(gòu)組織該數(shù)列，那么查找一個(gè)數(shù)的平均比擬次數(shù)為(8 )。假設(shè)按二叉排序樹組織該數(shù)列，那么查找一個(gè)數(shù)的平均比擬次數(shù)為(59/15 )。(4) 長度為20的有序表采用折半查找，共有(4)個(gè)元素的查找長度為3。(5) 假設(shè)數(shù)列25, 43, 62, 31, 48, 56,采用散列函數(shù)為H(k)=k mod7,那么元素48的同義詞是(62)(6) 在散列技術(shù)中，處理沖突的主要方法是(開放地址法)和(拉鏈法) 。(7) 在各種查找

19、方法中，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)無關(guān)的查找方法是(散列查找) 。(8) 與其他方法比擬，散列查找法的特點(diǎn)是(記錄的存儲(chǔ)位置與關(guān)鍵碼之間建立了一個(gè)確定的對(duì)應(yīng)關(guān) 系，平均查找長度與結(jié)點(diǎn)個(gè)數(shù)無關(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 解答以下問題(1) 分別畫出在線性表(a,b,c,d,e,f,g)中進(jìn)行折半查找關(guān)鍵碼e和g的過程。解：d-f-e 和 d-f-g(2) 畫出長度為10的折半查找判定樹，并求出等概率時(shí)查找成功和不成功的平均查找長度。-7 Eil 也 ElD 等概率時(shí)查找

20、成功平均查找長度 =(1*1+2*2+4*3+3*4)/10=29/10等概率時(shí)不成功的平均查找長度 =(5*4+6*5)/11=50/11 將數(shù)列(24,15,38,27,76,130,121)的各個(gè)元素依次插入一顆初始為空的二叉排序樹中，請(qǐng)畫出最后的結(jié)果并求等概率情況下查找成功的平均查找長度。AVL=(1+2*2+3*3+4+5)/7一棵二叉排序樹的結(jié)構(gòu)如圖7-30所示，結(jié)點(diǎn)的值為18,請(qǐng)標(biāo)出各點(diǎn)的值。答：見題上圖 習(xí)題81. 填空題(1)排序的主要目的是為了以后對(duì)已排序的數(shù)據(jù)元素進(jìn)行(查找)。 對(duì)n個(gè)元素進(jìn)行起泡排序，在(關(guān)鍵碼有序)的情況下比擬的次數(shù)最少，其比擬次數(shù)為(0(n)。 在(

21、關(guān)鍵碼逆序)情況下比擬次數(shù)最多，其比擬次數(shù)為(0而)。 對(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í)間是(O(nlog2n )，最壞時(shí)間是(0(n?)。(6) 利用簡單項(xiàng)選擇擇排序?qū)個(gè)記錄進(jìn)行排序，最壞情況下，記錄交換的次數(shù)為 (n-1)(7) 如果要將序列(50,16,23,68,94,70,73) 建成

22、堆，只需把16與(50 )交換。(8) 對(duì)于鍵值序列(12,13,11,18,60,15,7,18, 25, 100)，用篩選法建堆，必須從鍵值為(60 )的結(jié)點(diǎn)開始。2. 選擇題：(1) C (2) C (3) C (4) B (5) A (6) A (7) B,D,B (8) C (9) D (10) A,D (11) B (12) D,B,E,A,C (13) C (14) D (15) C習(xí)題61.填空題設(shè)無向圖G中頂點(diǎn)數(shù)為n,那么圖G至少有(0 )條邊，至多有(n(n-1)/2)條邊；假設(shè)G為有向圖，那么至少有(0 )條邊，至多有(n(n-1)條邊。 任何連通圖的連通分量只有一個(gè)，即是(它本身)。圖的存儲(chǔ)結(jié)構(gòu)主要有兩種，分別是(鄰接矩陣)和(鄰接表)。 無向圖G的頂點(diǎn)數(shù)為n,邊數(shù)為e,其鄰接表表示的空間復(fù)雜度為(O(n+e)。一個(gè)圖的鄰接矩陣表示，計(jì)算第j個(gè)頂點(diǎn)的入度的方法是(矩陣中第j-1列的非0元素個(gè)數(shù))。 有向圖G用鄰接矩陣A n n 存儲(chǔ)，其第1行的所有元素之和等于頂點(diǎn)1的(出度)。 圖的深度優(yōu)先遍歷類似于樹的(前序)遍歷，它所用的數(shù)據(jù)結(jié)構(gòu)是(棧)；圖的廣度優(yōu)先遍歷類似