各章習(xí)題匯總

1、數(shù)據(jù)結(jié)構(gòu)習(xí)題匯總 第 一 章 1、下面程序段的時(shí)間復(fù)雜度為_(kāi)。 for(int i=0; im; i+) for(int j=0; jn; j+) aij=i*j; A、 O(m2) B、 O(n2) C、 O(m*n) D、 O(m+n) 執(zhí)行下面程序段時(shí)，執(zhí)行S語(yǔ)句的次數(shù)為_(kāi)。 for(int i=1; i=n; i+) for(int j=1; j0）。 A表元素 B字符 C數(shù)據(jù)元素 D數(shù)據(jù)項(xiàng) E信息項(xiàng) 4若某線(xiàn)性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（ a ）存儲(chǔ)方式最節(jié)省時(shí)間。 A順序表 B雙鏈表 C帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D單循環(huán)鏈表 5、某線(xiàn)性表中

2、最常用的操作是在最后一個(gè)元素之后插入一個(gè)元素和刪除第一個(gè)元素，則采用（ d ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。 A單鏈表 B僅有頭指針的單循環(huán)鏈表 C雙鏈表 D僅有尾指針的單循環(huán)鏈表 6、在雙向鏈表指針p的結(jié)點(diǎn)前插入一個(gè)指針q的結(jié)點(diǎn)操作是（ ）。 A. p-Llink=q;q-Rlink=p;p-Llink-Rlink=q;q-Llink=q； B. p-Llink=q;p-Llink-Rlink=q;q-Rlink=p;q-Llink=p-Llink; C. q-Rlink=p;q-Llink=p-Llink;p-Llink-Rlink=q;p-Llink=q; D. q-Llink=p-Llink

3、;q-Rlink=q;p-Llink=q;p-Llink=q; 7、對(duì)于一個(gè)頭指針為head的帶頭結(jié)點(diǎn)的單鏈表，判定該表為空表的條件是（ ） Ahead=NULL Bheadnext=NULL Cheadnext=head Dhead!=NULL 1、設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點(diǎn)，指針py指向data為y的新結(jié)點(diǎn) , 若將結(jié)點(diǎn)y插入結(jié)點(diǎn)x之后，則需要執(zhí)行以下語(yǔ)句:_； 2在一個(gè)長(zhǎng)度為n的順序表中第i個(gè)元素（1=inext=null; B表的初始化。 LinkedList ra,rb;ra和rb將分別指向?qū)?chuàng)建的A表和B

4、表的尾結(jié)點(diǎn)。 ra=A;rb=B;p=A-next; p為鏈表工作指針，指向待分解的結(jié)點(diǎn)。A-next=null; 置空新的A表while(p!=null) r=p-next; 暫存p的后繼。 i+; if(i%2=0) 處理原序號(hào)為偶數(shù)的鏈表結(jié)點(diǎn)。p-next=rb-next;在B表尾插入新結(jié)點(diǎn)； rb-next=p; rb=p;rb指向新的尾結(jié)點(diǎn)； else處理原序號(hào)為奇數(shù)的結(jié)點(diǎn)。 p-next=ra-next; ra-next=p; ra=p; p=r; 將p恢復(fù)為指向新的待處理結(jié)點(diǎn)。 用類(lèi)用類(lèi)c的語(yǔ)言寫(xiě)出鏈?zhǔn)酱鎯?chǔ)條件下，刪除的語(yǔ)言寫(xiě)出鏈?zhǔn)酱鎯?chǔ)條件下，刪除單鏈表單鏈表L中值大于中值大于m

5、ax小于小于min的算法：的算法：Delete(L,max,min)Delete(L,max,min) p1=L; p2=p1-next; while(p2) if(p2-datamax|p2-datanext=p2-next; free(p2); p2=p1-next; else p1=p2; p2=p2-next; 第 三 章 1、對(duì)于棧操作數(shù)據(jù)的原則是（ ）. A. 先進(jìn)先出 B. 后進(jìn)先出 C. 后進(jìn)后出 D. 不分順序 2. 在作進(jìn)棧運(yùn)算時(shí),應(yīng)先判別棧是否( ),在作退棧運(yùn)算時(shí)應(yīng)先判別棧是否( )。當(dāng)棧中元素為n個(gè),作進(jìn)棧運(yùn)算時(shí)發(fā)生上溢,則說(shuō)明該棧的最大容量為( )。 , : A.

6、空 B. 滿(mǎn) C. 上溢 D. 下溢 : A. n-1 B. n C. n+1 D. n/2 3. 一個(gè)棧的輸入序列為123n，若輸出序列的第一個(gè)元素是n，輸出第i（1=i=n）個(gè)元素是（ ）。 A. 不確定 B. n-i+1 C. i D. n-i 4. 若一個(gè)棧的輸入序列為1,2,3,n，輸出序列的第一個(gè)元素是i，則第j個(gè)輸出元素是（ ）。 A. i-j-1 B. i-j C. j-i+1 D. 不確定的 5. 若已知一個(gè)棧的入棧序列是1,2,3,n，其輸出序列為p1,p2,p3，pN,若pN是n，則pi是( )。 A. i B. n-i C. n-i+1 D. 不確定 簡(jiǎn)述下列算法的簡(jiǎn)述

7、下列算法的 功能：功能： algo(Stack S) int i,n,a255; n0; while(!StackEmpty(S)n+;Pop(S,an); For(i=1;idata); /出隊(duì),訪問(wèn)結(jié)點(diǎn) if(p-lchild & !p-rchild |!p-lchild & p-rchild) num+; /度為1的結(jié)點(diǎn) if(p-lchild) QueueIn(Q,p-lchild); /非空左子女入隊(duì) if(p-rchild) QueueIn(Q,p-rchild); /非空右子女入隊(duì) /if(bt) return(num); /返回度為1的結(jié)點(diǎn)的個(gè)數(shù) 假設(shè)二叉樹(shù)采用

8、二叉鏈表存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)非假設(shè)二叉樹(shù)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)一個(gè)非遞歸算法求二叉樹(shù)的高度。遞歸算法求二叉樹(shù)的高度。 int Depth (BiTree T ) / 返回二叉樹(shù)的深度 if ( !T ) depthval = 0; else depthLeft = Depth( T-lchild ); depthRight= Depth( T-rchild ); depthval = 1 + (depthLeft depthRight ? depthLeft : depthRight); return depthval; 非遞歸算法的思想非遞歸算法的思想： 采用分層遍歷二叉樹(shù)的方法，使用一個(gè)

9、隊(duì)采用分層遍歷二叉樹(shù)的方法，使用一個(gè)隊(duì)列列qu和一個(gè)整數(shù)數(shù)組和一個(gè)整數(shù)數(shù)組level，它們使用相，它們使用相同的下標(biāo)，后者存儲(chǔ)對(duì)應(yīng)結(jié)點(diǎn)在二叉樹(shù)中同的下標(biāo)，后者存儲(chǔ)對(duì)應(yīng)結(jié)點(diǎn)在二叉樹(shù)中的層次。最大的層次就是二叉樹(shù)的深度。的層次。最大的層次就是二叉樹(shù)的深度。 Int Depth(BTree *T) int m,max,rear,front,levelMaxSize; BTree *quMaxSize ,*p; /循環(huán)隊(duì)列 max=0;rear=0;front=0; rear+;qurear=T;levelrear=1;/根結(jié)點(diǎn)入隊(duì) while(front!=rear) front=(front+1)

10、%maxsize;/出隊(duì)列 p=qufront;m=levelfront; if(mmax) max=m; if(p-lchild!=NULL) rear=(rear+1)%Maxsize； /左孩子入隊(duì) qurear=p-lchild; levelrear=m+1;/子女層次加1 if(p-rchild!=NULL) rear=(rear+1)%Maxsize； /右孩子入隊(duì) qurear=p-rchild; levelrear=m+1;/子女層次加1 return max; 第 七 章習(xí)題習(xí)題 1、已知圖、已知圖G（V，E），其中），其中Va，b，c，d，e，f，g，E, , , , ,，

11、請(qǐng)畫(huà)出圖，請(qǐng)畫(huà)出圖G，并寫(xiě)出其鄰，并寫(xiě)出其鄰接矩陣和鄰接表表示接矩陣和鄰接表表示. 2、已知無(wú)向圖的鄰接表如下圖：、已知無(wú)向圖的鄰接表如下圖： 畫(huà)出該無(wú)向圖。畫(huà)出該無(wú)向圖。 根據(jù)鄰接表分別寫(xiě)出用根據(jù)鄰接表分別寫(xiě)出用DFS和和BFS算算 法從頂點(diǎn)法從頂點(diǎn)v0開(kāi)始遍歷該圖后得到的遍歷開(kāi)始遍歷該圖后得到的遍歷 序列。序列。 2、 2、作業(yè)作業(yè) 畫(huà)出下圖的拓?fù)渑判蛐蛄校寒?huà)出下圖的拓?fù)渑判蛐蛄校篴hkahkcdefcfed 對(duì)于下面的對(duì)于下面的AOE網(wǎng)：網(wǎng)： 1、求出各個(gè)事件的最早發(fā)生時(shí)間和最晚、求出各個(gè)事件的最早發(fā)生時(shí)間和最晚發(fā)生時(shí)間，并回答完成整個(gè)工程最少需發(fā)生時(shí)間，并回答完成整個(gè)工程最少需要多少時(shí)

12、間？要多少時(shí)間？ 2、計(jì)算各個(gè)活動(dòng)的最早開(kāi)始時(shí)間和最遲、計(jì)算各個(gè)活動(dòng)的最早開(kāi)始時(shí)間和最遲開(kāi)始時(shí)間，并找出所有的關(guān)鍵活動(dòng)和關(guān)開(kāi)始時(shí)間，并找出所有的關(guān)鍵活動(dòng)和關(guān)鍵路徑。鍵路徑。v0v1v3v2v4v5v6v7v8v93585644 27365893第 九 章 1以順序查找方法從長(zhǎng)度為n的線(xiàn)性表中查找一個(gè)元素時(shí)，平均查找長(zhǎng)度為_(kāi)，時(shí)間復(fù)雜度為_(kāi)。 2以二分查找方法查找一個(gè)線(xiàn)性表時(shí)，此線(xiàn)性表必須是_存儲(chǔ)的_表。 5從有序表(12,18,30,43,56,78,82,95)中依次二分查找43和56元素時(shí)，其查找長(zhǎng)度分別為_(kāi)和_。 7假定對(duì)長(zhǎng)度n=50的有序表進(jìn)行二分查找，則對(duì)應(yīng)的判定樹(shù)高度為_(kāi)，判定樹(shù)中

13、前5層的結(jié)點(diǎn)數(shù)為_(kāi)，最后一層的結(jié)點(diǎn)數(shù)為_(kāi)。 8在索引表中，每個(gè)索引項(xiàng)至少包含有_域和_域這兩項(xiàng)。 作業(yè)作業(yè) 、在關(guān)鍵字序列、在關(guān)鍵字序列(07，12，15，18，27，32，41，92)中用二分查找法查找和給定值中用二分查找法查找和給定值92相等的關(guān)鍵字，請(qǐng)寫(xiě)出查找過(guò)程中依次相等的關(guān)鍵字，請(qǐng)寫(xiě)出查找過(guò)程中依次和給定值和給定值“92”比較的關(guān)鍵字（以圖示標(biāo)明比較的關(guān)鍵字（以圖示標(biāo)明）。）。 作業(yè)作業(yè) 2、畫(huà)出對(duì)長(zhǎng)度為的有序表進(jìn)行折半查、畫(huà)出對(duì)長(zhǎng)度為的有序表進(jìn)行折半查找的一棵判定樹(shù)，并求其等概率查找時(shí)查找的一棵判定樹(shù)，并求其等概率查找時(shí)查找成功的平均查找長(zhǎng)度找成功的平均查找長(zhǎng)度 3.3.已知如下所

14、示長(zhǎng)度為已知如下所示長(zhǎng)度為1212的列表的列表(Jan,Feb,Mar,Apr,May,June,July,Aug,(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)Sep,Oct,Nov,Dec) (1)(1)試按表中元素的順序依次插入一棵初試按表中元素的順序依次插入一棵初始為空的二叉排序樹(shù)始為空的二叉排序樹(shù), ,請(qǐng)畫(huà)出插入完成后請(qǐng)畫(huà)出插入完成后的二叉排序樹(shù)的二叉排序樹(shù). . (2)(2)若對(duì)表中元素先進(jìn)行排序構(gòu)成有序表若對(duì)表中元素先進(jìn)行排序構(gòu)成有序表, ,求在等概率情況下對(duì)此表進(jìn)行折半查找求在等概率情況下對(duì)此表進(jìn)行折半查找成功的平均查找長(zhǎng)

15、度成功的平均查找長(zhǎng)度. . 4.4.線(xiàn)性表的關(guān)鍵字集合為線(xiàn)性表的關(guān)鍵字集合為78,25,13,80,72,140,68,59,123,7,36,78,25,13,80,72,140,68,59,123,7,36,74,74,共有共有1212個(gè)元素個(gè)元素, ,已知散列函數(shù)為已知散列函數(shù)為H(k)=k%12,H(k)=k%12,采用鏈地址法處理沖突采用鏈地址法處理沖突, ,試在試在0 01111的散列空間中對(duì)該關(guān)鍵字序列構(gòu)造的散列空間中對(duì)該關(guān)鍵字序列構(gòu)造哈希表哈希表第 十 章 設(shè)用希爾排序?qū)?shù)組98，36，-9，0，47，23，1，8，10，7進(jìn)行排序，給出的步長(zhǎng)（也稱(chēng)增量序列）依次是4，2，1則

16、排序需_趟，寫(xiě)出第一趟結(jié)束后，數(shù)組中數(shù)據(jù)的排列次序_。 對(duì)關(guān)鍵字序列對(duì)關(guān)鍵字序列(52，80，63，44，48，91)進(jìn)行一趟快速排序之后得到的結(jié)果為進(jìn)行一趟快速排序之后得到的結(jié)果為_(kāi)。 對(duì)于以下關(guān)鍵字序列（對(duì)于以下關(guān)鍵字序列（52, 49, 80, 36, 14, 58, 61, 97, 23, 75）寫(xiě)出進(jìn)行一趟快速排序）寫(xiě)出進(jìn)行一趟快速排序的過(guò)程（寫(xiě)明步驟）。的過(guò)程（寫(xiě)明步驟）。 已知一組元素的排序碼為(49，38，65，97，76，13，27，49) (1) 利用直接插入排序的方法寫(xiě)出每次向前面有序表插入一個(gè)元素后的排列結(jié)果。 (2) 利用堆排序的方法寫(xiě)出在構(gòu)成初始堆和利用堆排序的過(guò)程

17、中，每次篩運(yùn)算后的排列結(jié)果，并畫(huà)出初始堆所對(duì)應(yīng)的完全二叉樹(shù)。 (3) 利用快速排序的方法寫(xiě)出每一層劃分后的排列結(jié)果。 (4) 利用歸并排序的方法寫(xiě)出每一趟二路歸并排序后的結(jié)果。 （1） （49）38 65 97 76 13 27 49 38（38 49）65 97 76 13 27 49 38（38 49 65）97 76 13 27 49 38（38 49 65 97）76 13 27 49 76（38 49 65 76 97）13 27 49 13（13 38 49 65 76 97）27 49 27（13 27 38 49 65 76 97）49 49（13 27 38 49 49 65 76 97） （2） 97 76 65 49 49 13 27 38 76 49 65 38 49 13 27 97 65 49 27 38 49 13 76 97 49 49 27 38 13 65 76 97 49 38 27 13 49 65 76 97 38 13 27 49 49 6