各章習(xí)題匯總

1、數(shù)據(jù)結(jié)構(gòu)習(xí)題匯總 第 一 章 1、下面程序段的時間復(fù)雜度為_。 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í)行下面程序段時，執(zhí)行S語句的次數(shù)為_。 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若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（ a ）存儲方式最節(jié)省時間。 A順序表 B雙鏈表 C帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 D單循環(huán)鏈表 5、某線性表中

2、最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ d ）存儲方式最節(jié)省運(yùn)算時間。 A單鏈表 B僅有頭指針的單循環(huán)鏈表 C雙鏈表 D僅有尾指針的單循環(huán)鏈表 6、在雙向鏈表指針p的結(jié)點(diǎn)前插入一個指針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、對于一個頭指針為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í)行以下語句:_； 2在一個長度為n的順序表中第i個元素（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) 處理原序號為偶數(shù)的鏈表結(jié)點(diǎn)。p-next=rb-next;在B表尾插入新結(jié)點(diǎn)； rb-next=p; rb=p;rb指向新的尾結(jié)點(diǎn)； else處理原序號為奇數(shù)的結(jié)點(diǎn)。 p-next=ra-next; ra-next=p; ra=p; p=r; 將p恢復(fù)為指向新的待處理結(jié)點(diǎn)。 用類用類c的語言寫出鏈?zhǔn)酱鎯l件下，刪除的語言寫出鏈?zhǔn)酱鎯l件下，刪除單鏈表單鏈表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、對于棧操作數(shù)據(jù)的原則是（ ）. A. 先進(jìn)先出 B. 后進(jìn)先出 C. 后進(jìn)后出 D. 不分順序 2. 在作進(jìn)棧運(yùn)算時,應(yīng)先判別棧是否( ),在作退棧運(yùn)算時應(yīng)先判別棧是否( )。當(dāng)棧中元素為n個,作進(jìn)棧運(yùn)算時發(fā)生上溢,則說明該棧的最大容量為( )。 , : A.

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

7、下列算法的 功能：功能： algo(Stack S) int i,n,a255; n0; while(!StackEmpty(S)n+;Pop(S,an); For(i=1;idata); /出隊(duì),訪問結(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)的個數(shù) 假設(shè)二叉樹采用二叉鏈表存儲結(jié)構(gòu)

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

9、叉樹的方法，使用一個隊(duì)列列qu和一個整數(shù)數(shù)組和一個整數(shù)數(shù)組level，它們使用相，它們使用相同的下標(biāo)，后者存儲對應(yīng)結(jié)點(diǎn)在二叉樹中同的下標(biāo)，后者存儲對應(yīng)結(jié)點(diǎn)在二叉樹中的層次。最大的層次就是二叉樹的深度。的層次。最大的層次就是二叉樹的深度。 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)%maxsize

10、;/出隊(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、圖G，并寫出其鄰，并寫出其鄰接矩陣和鄰接表表示接矩陣和鄰接表表示. 2、已知無向圖的鄰接表如下圖：、已知無向圖的鄰接表如下圖： 畫出該無向圖。畫出該無向圖。 根據(jù)鄰接表分別寫出用根據(jù)鄰接表分別寫出用DFS和和BFS算算 法從頂點(diǎn)法從頂點(diǎn)v0開始遍歷該圖后得到的遍歷開始遍歷該圖后得到的遍歷 序列。序列。 2、 2、作業(yè)作業(yè) 畫出下圖的拓?fù)渑判蛐蛄校寒嫵鱿聢D的拓?fù)渑判蛐蛄校篴hkahkcdefcfed 對于下面的對于下面的AOE網(wǎng)：網(wǎng)： 1、求出各個事件的最早發(fā)生時間和最晚、求出各個事件的最早發(fā)生時間和最晚發(fā)生時間，并回答完成整個工程最少需發(fā)生時間，并回答完成整個工程最少需要多少時間？要多少時間？

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

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

14、所示長度為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)試按表中元素的順序依次插入一棵初試按表中元素的順序依次插入一棵初始為空的二叉排序樹始為空的二叉排序樹, ,請畫出插入完成后請畫出插入完成后的二叉排序樹的二叉排序樹. . (2)(2)若對表中元素先進(jìn)行排序構(gòu)成有序表若對表中元素先進(jìn)行排序構(gòu)成有序表, ,求在等概率情況下對此表進(jìn)行折半查找求在等概率情況下對此表進(jìn)行折半查找成功的平均查找長度成功的平均查找

15、長度. . 4.4.線性表的關(guā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個元素個元素, ,已知散列函數(shù)為已知散列函數(shù)為H(k)=k%12,H(k)=k%12,采用鏈地址法處理沖突采用鏈地址法處理沖突, ,試在試在0 01111的散列空間中對該關(guān)鍵字序列構(gòu)造的散列空間中對該關(guān)鍵字序列構(gòu)造哈希表哈希表第 十 章 設(shè)用希爾排序?qū)?shù)組98，36，-9，0，47，23，1，8，10，7進(jìn)行排序，給出的步長（也稱增量序列）依次是4，2，1則排序需_趟，寫出

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

17、的排列結(jié)果，并畫出初始堆所對應(yīng)的完全二叉樹。 (3) 利用快速排序的方法寫出每一層劃分后的排列結(jié)果。 (4) 利用歸并排序的方法寫出每一趟二路歸并排序后的結(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 65