數(shù)據(jù)結(jié)構(gòu)C語言章節(jié)練習(xí)題章

1、數(shù)據(jù)結(jié)構(gòu)章節(jié)練習(xí)題第一章 緒 論一、單選題1.一個(gè)數(shù)組元素ai與_的表示等價(jià)。 A、 *(a+i) B、 a+i C、 *a+i D、 &a+i 2.下面程序段的時(shí)間復(fù)雜度為_。 for(int i=0; i<m; i+) for(int j=0; j<n; j+) aij=i*j; A、 O(m2) B、 O(n2) C、 O(m*n) D、 O(m+n)3.執(zhí)行下面程序段時(shí)，執(zhí)行S語句的次數(shù)為_。 for(int i=1; i<=n; i+) for(int j=1; j<=i; j+) S; A、 n2 B、 n2/2 C、 n(n+1) D、 n(n+1

2、)/24.下面算法的時(shí)間復(fù)雜度為_。 int f( unsigned int n ) if ( n=0 | n=1 ) return 1; else return n*f(n-1); A、 O(1) B、 O(n) C、 O(n2) D、 O(n!)二、填空題1.數(shù)據(jù)的邏輯結(jié)構(gòu)被分為_、_、_和_四種。2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)被分為_、和_兩種。3.在線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點(diǎn)之間分別存在著_、_和_的聯(lián)系。4.一種抽象數(shù)據(jù)類型包括_和_兩個(gè)部分。5.當(dāng)一個(gè)形參類型的長(zhǎng)度較大時(shí)，應(yīng)最好說明為_，以節(jié)省參數(shù)值的傳輸時(shí)間和存儲(chǔ)參數(shù)的空間。6.當(dāng)需要用一個(gè)形參訪問對(duì)應(yīng)的實(shí)參時(shí)，則該形參

3、應(yīng)說明為_。7.在函數(shù)中對(duì)引用形參的修改就是對(duì)相應(yīng)_的修改，對(duì)_形參的修改只局限在該函數(shù)的內(nèi)部，不會(huì)反映到對(duì)應(yīng)的實(shí)參上。8.當(dāng)需要進(jìn)行標(biāo)準(zhǔn)I/O操作時(shí)，則應(yīng)在程序文件中包含_頭文件，當(dāng)需要進(jìn)行文件I/O操作時(shí)，則應(yīng)在程序文件中包含_頭文件。9.在包含有_頭文件的程序文件中，使用_能夠產(chǎn)生出020之間的一個(gè)隨機(jī)整數(shù)。10.一個(gè)數(shù)組a所占有的存儲(chǔ)空間的大小即數(shù)組長(zhǎng)度為_，下標(biāo)為i的元素ai的存儲(chǔ)地址為_，或者為_。14.從一維數(shù)組an中順序查找出一個(gè)最大值元素的時(shí)間復(fù)雜度為_，輸出一個(gè)二維數(shù)組bmn中所有元素值的時(shí)間復(fù)雜度為_。15.在下面程序段中，s=s+p語句的執(zhí)行次數(shù)為_，p*=j語句的執(zhí)行

4、次數(shù)為_，該程序段的時(shí)間復(fù)雜度為_。 int i=0,s=0; while(+i<=n) int p=1; for(int j=1;j<=i;j+) p*=j; s=s+p; 16.一個(gè)算法的時(shí)間復(fù)雜度為(3n2+2nlog2n+4n-7)/(5n)，其數(shù)量級(jí)表示為_。第二章 線性表一、單選題1在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)線性表中，向第i個(gè)元素(1in+1)之前插入一個(gè)新元素時(shí)，需要從后向前依次后移 個(gè)元素。A、n-i B、n-i+1 C、n-i-1 D、i2在一個(gè)長(zhǎng)度為n的順序存儲(chǔ)線性表中，刪除第i個(gè)元素(1in+1)時(shí)，需要從前向后依次前移 元素。 A、n-i B、n-i+1 C、

5、n-i-1 D、i3在一個(gè)長(zhǎng)度為n的線性表中順序查找值為x的元素時(shí)，查找時(shí)的平均查找長(zhǎng)度（即x同元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等）為 。 A、n B、n/2 C、(n+1)/2 D、(n-1)/24在一個(gè)單鏈表HL中，若要向表頭插入一個(gè)由指針p指向的結(jié)點(diǎn)，則執(zhí)行 。 A、HL = p; p->next = HL; B、p->next = HL; HL = p; C、p->next = HL; p = HL; D、p->next = HL->next; HL->next = p;5在一個(gè)單鏈表HL中，若要在指針q所指的結(jié)點(diǎn)的后面插入一個(gè)由指針p

6、所指的結(jié)點(diǎn)，則執(zhí)行 。 A、q->next = p->next ; p->next = q; B、p->next = q->next; q = p; C、q->next = p->next; p->next = q; D、p->next = q->next ; q->next = p;6在一個(gè)單鏈表HL中，若要?jiǎng)h除由指針q所指向結(jié)點(diǎn)的后繼結(jié)點(diǎn)，則執(zhí)行 。 A、p = q->next ; p->next = q->next; B、p = q->next ; q->next = p; C、p = q-&

7、gt;next ; q->next = p->next; D、q->next = q->next->next; q->next = q;二、填空題1在線性表的單鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)包含有兩個(gè)域，一個(gè)叫_域，另一個(gè)叫_域。2在下面數(shù)組a中鏈?zhǔn)酱鎯?chǔ)著一個(gè)線性表，表頭指針為a0.next，則該線性表為_。3對(duì)于一個(gè)長(zhǎng)度為n的順序存儲(chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為_，在表尾插入元素的時(shí)間復(fù)雜度為_。4對(duì)于一個(gè)長(zhǎng)度為n的單鏈?zhǔn)酱鎯?chǔ)的線性表，在表頭插入元素的時(shí)間復(fù)雜度為_，在表尾插入元素的時(shí)間復(fù)雜度為_。5在線性表的順序存儲(chǔ)中，若一個(gè)元素的下標(biāo)為i，則它的前

8、驅(qū)元素的下標(biāo)為_，后繼元素的下標(biāo)為_。6在線性表的單鏈?zhǔn)酱鎯?chǔ)中，若一個(gè)元素所在結(jié)點(diǎn)的地址為p，則其后繼結(jié)點(diǎn)的地址為_，若假定p為一個(gè)數(shù)組a中的下標(biāo)，則其后繼結(jié)點(diǎn)的下標(biāo)為_。7在循環(huán)單鏈表中，最后一個(gè)結(jié)點(diǎn)的指針指向_結(jié)點(diǎn)。8在雙向鏈表中每個(gè)結(jié)點(diǎn)包含有兩個(gè)指針域，一個(gè)指向其_結(jié)點(diǎn)，另一個(gè)指向其_結(jié)點(diǎn)。9在循環(huán)雙向鏈表中表頭結(jié)點(diǎn)的左指針域指向_結(jié)點(diǎn)，最后一個(gè)結(jié)點(diǎn)的右指針域指向_結(jié)點(diǎn)。10在以HL為表頭指針的帶表頭結(jié)點(diǎn)的單鏈表和循環(huán)單鏈表中，鏈表為空的條件分別為_和_。三、應(yīng)用題1在下面的每個(gè)程序段中，假定線性表La的類型為L(zhǎng)ist，元素類型ElemType為int，并假定每個(gè)程序段是連續(xù)執(zhí)行的，試寫

9、出每個(gè)程序段執(zhí)行后所得到的線性表La。 (1) InitList(La); int a=48,26,57,34,62,79; for(i=0; i<6; i+) InsertFront(La,ai); TraverseList(La); (2) InitList(La); for(i=0; i<6; i+) Insert(La,ai); TraverseList(La);(3) ClearList(La); for(i=0; i<6; i+) InsertRear(La,ai); Delete(La, a5); Sort(La); Insert(La,a5/2); Trave

10、rseList(La);3對(duì)于List類型的線性表，編寫出下列每個(gè)算法。(1)從線性表中刪除具有最小值的元素并由函數(shù)返回，空出的位置由最后一個(gè)元素填補(bǔ)，若線性表為空則顯示出錯(cuò)信息并退出運(yùn)行。(2)從線性表中刪除第i個(gè)元素并由函數(shù)返回。(3)向線性表中第i個(gè)元素位置插入一個(gè)元素。(4)從線性表中刪除具有給定值x的所有元素。4對(duì)于結(jié)點(diǎn)類型為L(zhǎng)Node的單鏈表，編寫出下列每個(gè)算法。(1)刪除單鏈表中的第i個(gè)結(jié)點(diǎn)。(2)在有序單鏈表中插入一個(gè)元素x的結(jié)點(diǎn)。 (3)從單鏈表中查找出所有元素的最大值，該值由函數(shù)返回，若單鏈表為空，則顯示出錯(cuò)信息并停止運(yùn)行。(4)統(tǒng)計(jì)出單鏈表中結(jié)點(diǎn)的值等于給定值x的結(jié)點(diǎn)數(shù)。

11、第三章 棧和隊(duì)列一、單選題1棧的插入與刪除操作在 進(jìn)行。 A、棧頂 B、棧底 C、任意位置 D、指定位置2當(dāng)利用大小為N的一維數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top=0表示?？眨瑒t向這個(gè)棧插入一個(gè)元素時(shí)，需要執(zhí)行 語句修改top指針。 A、top+ B、top- C、top=0 D、top3若讓元素1，2，3依次進(jìn)棧，則出棧次序不可能出現(xiàn) 種情況。 A、3，2，1 B、2，1，3 C、3，1，2 D、1，3，24在一個(gè)循環(huán)順序隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的 位置。 A、前一個(gè) B、后一個(gè) C、當(dāng)前 D、后面5當(dāng)利用大小為N的一維數(shù)組順序存儲(chǔ)一個(gè)循環(huán)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度為 。 A、N-2 B、N

12、-1 C、N D、N+16從一個(gè)循環(huán)順序隊(duì)列刪除元素時(shí)，首先需要 。 A、前移一位隊(duì)首指針 B、后移一位隊(duì)首指針 C、取出隊(duì)首指針?biāo)肝恢蒙系脑?D、取出隊(duì)尾指針?biāo)肝恢蒙系脑?假定一個(gè)循環(huán)順序隊(duì)列的隊(duì)首和隊(duì)尾指針分別為f和r，則判斷隊(duì)空的條件是 。 A、f+1=r B、r+1=f C、f=0 D、f=r8假定一個(gè)鏈隊(duì)的隊(duì)首和隊(duì)尾指針分別為front和rear，則判斷隊(duì)空的條件是 。 A、front=rear B、front!=NULL C、rear!=NULL D、front=NULL二、填空題1隊(duì)列的插入操作在_進(jìn)行，刪除操作在_進(jìn)行。2棧又稱為_表，隊(duì)列又稱為_表。3向一個(gè)順序棧插入

13、一個(gè)元素時(shí)，首先把待插入元素_到這個(gè)位置上然后，使_后移一個(gè)位置。4從一個(gè)棧中刪除元素時(shí)，首先前移一位_，然后再取出_。5在一個(gè)循環(huán)順序隊(duì)列Q中，判斷隊(duì)空的條件為_，判斷隊(duì)滿的條件為_。6在一個(gè)順序棧中，若棧頂指針等于_，則為空棧；若棧頂指針等于_，則為滿棧。7在一個(gè)鏈棧中，若棧頂指針等于NULL，則為_；在一個(gè)鏈隊(duì)中，若隊(duì)首指針與隊(duì)尾指針的值相同，則表示該隊(duì)列為_。8向一個(gè)鏈棧插入一個(gè)新結(jié)點(diǎn)時(shí)，首先把新結(jié)點(diǎn)的存儲(chǔ)位置賦給_，然后把棧頂指針指向_。9從一個(gè)鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，需要把棧頂結(jié)點(diǎn)_的值賦給_。10向一個(gè)順序隊(duì)列插入元素時(shí)，需要首先向_插入新元素，然后再移動(dòng)_。11當(dāng)用長(zhǎng)度為N的一維

14、數(shù)組順序存儲(chǔ)一個(gè)棧時(shí)，假定用top=0表示?？眨瑒t表示棧滿的條件為_。12向一個(gè)棧頂指針為HS的鏈棧中插入一個(gè)新結(jié)點(diǎn)*P果，應(yīng)執(zhí)行_和_操作。13從一個(gè)棧頂指針為HS的非空鏈棧中刪除結(jié)點(diǎn)并不需要返回棧頂結(jié)點(diǎn)的值和回收結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行_操作。14假定front和rear分別為一個(gè)鏈隊(duì)的隊(duì)首和隊(duì)尾指針，則該鏈隊(duì)中只有一個(gè)結(jié)點(diǎn)的條件為_。三、應(yīng)用題執(zhí)行下面函數(shù)調(diào)用后得到的輸出結(jié)果是什么？void AF(Queue & Q) InitQueue(Q); int a4 = 5,8,12,15 ; for ( int i=0; i<4; i+ ) QInsert(Q,ai); QInsert(

15、Q,QDelete(Q); QInsert(Q,30); QInsert(Q,QDelete(Q)+10); while (!QueueEmpty(Q) printf ( “%d ”,QDelete(Q); 第四章 稀疏矩陣和廣義表一、單選題1.在稀疏矩陣的帶行指針向量的鏈接存儲(chǔ)中，每個(gè)行單鏈表中的結(jié)點(diǎn)都具有相同的_。 A、 行號(hào) B、 列號(hào) C、 元素值 D、 地址二、填空題1.在一個(gè)稀疏矩陣中，每個(gè)非零元素所對(duì)應(yīng)的三元組包括該元素的_、_和_三項(xiàng)。2.在稀疏矩陣所對(duì)應(yīng)的三元組線性表中，每個(gè)三元組元素按_為主序、_為輔序的次序排列。3.在初始化一個(gè)稀疏矩陣的函數(shù)定義中，矩陣形參應(yīng)說明為_參數(shù)

16、。4.在稀疏矩陣的順序存儲(chǔ)中，利用一個(gè)數(shù)組來存儲(chǔ)非零元素，該數(shù)組的長(zhǎng)度應(yīng)_對(duì)應(yīng)三元組線性表的長(zhǎng)度。第五章 樹和二叉樹（一）一、填空題1對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的樹，該樹中所有結(jié)點(diǎn)的度數(shù)之和為_。2假定一棵三叉樹的結(jié)點(diǎn)個(gè)數(shù)為50，則它的最小深度為_，最大深度為_。3在一棵三叉樹中，度為3的結(jié)點(diǎn)數(shù)有2個(gè)，度為2的結(jié)點(diǎn)數(shù)有1個(gè)，度為1的結(jié)點(diǎn)數(shù)為2個(gè)，那么度為0的結(jié)點(diǎn)數(shù)有_個(gè)。4一棵深度為5的滿二叉樹中的結(jié)點(diǎn)數(shù)為_個(gè)，一棵深度為3的滿三叉樹中的結(jié)點(diǎn)數(shù)為_個(gè)。5假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)，則樹中所含的結(jié)點(diǎn)數(shù)為_個(gè)，樹的深度為_，樹的度為_。6假定一棵樹的廣義表表示為A

17、(B(C,D(E,F,G),H(I,J)，則度為3、2、1、0的結(jié)點(diǎn)數(shù)分別為_、_、_和_個(gè)。7假定一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)，則結(jié)點(diǎn)H的雙親結(jié)點(diǎn)為_，孩子結(jié)點(diǎn)為_。8在一棵二叉樹中，假定雙分支結(jié)點(diǎn)數(shù)為5個(gè)，單分支結(jié)點(diǎn)數(shù)為6個(gè)，則葉子結(jié)點(diǎn)數(shù)為_個(gè)。9對(duì)于一棵二叉樹，若一個(gè)結(jié)點(diǎn)的編號(hào)為i，則它的左孩子結(jié)點(diǎn)的編號(hào)為_，右孩子結(jié)點(diǎn)的編號(hào)為_，雙親結(jié)點(diǎn)的編號(hào)為_。10在一棵二叉樹中，第5層上的結(jié)點(diǎn)數(shù)最多為_。11假定一棵二叉樹的結(jié)點(diǎn)數(shù)為18，則它的最小深度為_，最大深度為_。12一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g)，則e結(jié)點(diǎn)的雙親結(jié)點(diǎn)為_，左孩子

18、結(jié)點(diǎn)為_，右孩子結(jié)點(diǎn)為_。13一棵二叉樹的廣義表表示為a(b(c,d),e(f(,g)，它含有雙親結(jié)點(diǎn)_個(gè)，單分支結(jié)點(diǎn)_個(gè)，葉子結(jié)點(diǎn)_個(gè)。14假定一棵二叉樹順序存儲(chǔ)在一維數(shù)組a中，則ai元素的左孩子元素為_，右孩子元素為_，雙親元素(i>1)為_。15假定一棵二叉樹順序存儲(chǔ)在一維數(shù)組a中，但讓編號(hào)為1的結(jié)點(diǎn)存入a0元素中，讓編號(hào)為2的結(jié)點(diǎn)存入a1元素中，其余類推，則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)對(duì)應(yīng)的存儲(chǔ)位置為_，若編號(hào)為i結(jié)點(diǎn)的存儲(chǔ)位置用j表示，則其左孩子結(jié)點(diǎn)對(duì)應(yīng)的存儲(chǔ)位置為_。16若對(duì)一棵二叉樹從0開始進(jìn)行結(jié)點(diǎn)編號(hào)，并按此編號(hào)把它順序存儲(chǔ)到一維數(shù)組a中，即編號(hào)為0的結(jié)點(diǎn)存儲(chǔ)到a0中，其余類

19、推，則ai元素的左孩子元素為_，右孩子元素為_，雙親元素(i>0)為_。17對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹，對(duì)應(yīng)二叉鏈表中指針總數(shù)為_個(gè)，其中_個(gè)用于指向孩子結(jié)點(diǎn)，_個(gè)指針空閑著。18一棵二叉樹廣義表表示為a(b(d(,h),c(e,f(g,i(k)，該樹的結(jié)點(diǎn)數(shù)為_個(gè)，深度為_。19假定一棵二叉樹廣義表表示為a(b(c),d(e,f)，則對(duì)它進(jìn)行的先序遍歷結(jié)果為_，中序遍歷結(jié)果為_，后序遍歷結(jié)果為_，按層遍歷結(jié)果為_。20假定一棵普通樹的廣義表表示為a(b(e),c(f(h,i,j),g),d)，則先根遍歷結(jié)果為_，按層遍歷結(jié)果為_。二、應(yīng)用題1已知一棵具有n個(gè)結(jié)點(diǎn)的完全二叉樹被順序存儲(chǔ)

20、于一維數(shù)組的A1An元素中，試編寫一個(gè)算法打印出編號(hào)為i的結(jié)點(diǎn)的雙親和所有孩子。2編寫一算法，求出一棵二叉樹中所有結(jié)點(diǎn)數(shù)和葉子結(jié)點(diǎn)數(shù)，假定分別用變參C1和C2統(tǒng)計(jì)所有結(jié)點(diǎn)數(shù)和葉子結(jié)點(diǎn)數(shù)，初值均為0。第六章 二叉樹的應(yīng)用（二）一、單選題1. 從二叉搜索樹中查找一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為_。A、 O(n) B、 O(1) C、 O(log2n) D、 O(n2)2. 向二叉搜索樹中插入一個(gè)元素時(shí)，其時(shí)間復(fù)雜度大致為_。 A、 O(1) B、 O(log2n ) C、 O(n) D、 O(nlog2n)3. 根據(jù)n個(gè)元素建立一棵二叉搜索樹時(shí)，其時(shí)間復(fù)雜度大致為_。 A、 O(n) B、 O(lo

21、g2n ) C、 O(n2) D、 O(nlog2n)4. 從堆中刪除一個(gè)元素的時(shí)間復(fù)雜度為_。 A、 O(1) B、 O(n) C、 O(log2n) D、 O(nlog2n)5. 向堆中插入一個(gè)元素的時(shí)間復(fù)雜度為_。 A、 O(log2n) B、 O(n) C、 O(1) D、 O(nlog2n)6. 由權(quán)值分別為3,8,6,2,5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長(zhǎng)度為_。 A、 24 B、 48 C、 72 D、 53二、填空題 1. 在一棵二叉搜索樹中，每個(gè)分支結(jié)點(diǎn)的左子樹上所有結(jié)點(diǎn)的值一定_該結(jié)點(diǎn)的值，右子樹上所有結(jié)點(diǎn)的值一定_該結(jié)點(diǎn)的值。2對(duì)一棵二叉搜索樹進(jìn)行中序遍歷時(shí)，得

22、到的結(jié)點(diǎn)序列是一個(gè)_。3從一棵二叉搜索樹中查找一個(gè)元素時(shí)，若元素的值等于根結(jié)點(diǎn)的值，則表明_，若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向_查找，若元素的大于根結(jié)點(diǎn)的值，則繼續(xù)向_查找。4在一個(gè)堆的順序存儲(chǔ)中，若一個(gè)元素的下標(biāo)為i，則它的左孩子元素的下標(biāo)為_，右孩子元素的下標(biāo)為_。5. 在一個(gè)小根堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的_，在一個(gè)大根堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的_。6當(dāng)從一個(gè)小根堆中刪除一個(gè)元素時(shí)，需要把_元素填補(bǔ)到_位置，然后再按條件把它逐層_調(diào)整。三、應(yīng)用題1. 已知一組元素為(46,25,78,62,12,37,70,29)，畫出按元素排列順序輸入生成的一棵二叉搜索樹。2. 空堆開始依

23、次向堆中插入線性表（38,64,52,15,73,40,48,55,26,12）中的每個(gè)元素，請(qǐng)以線性表的形式給出每插入一個(gè)元素后堆的狀態(tài)。3. 已知一個(gè)堆為（12,15,40,38,26,52,48,64），若需要從堆中依次刪除四個(gè)元素，請(qǐng)給出每刪除一個(gè)元素后堆的狀態(tài)。4. 有七個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為3,7,8,2,6,10,14，試以它們?yōu)槿~子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，并計(jì)算出帶權(quán)路徑長(zhǎng)度WPL。數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)練習(xí)題答案（僅供參考）第一章 緒 論一、單選題1. A 2. C 3. B 4. C 5. D 6. B 二、填空題1. 集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹型結(jié)構(gòu)、圖形結(jié)構(gòu) 2.順序、鏈?zhǔn)?3.

24、 1:1、1:N、M:N 4.數(shù)據(jù)定義、操作聲明 5.引用形參(或指針形參 ) 6.引用類型 ( 或 指針類型 ) 7.實(shí)參、值 8.stdio.h、file.h 9.stdlib.h、rand( ) %21 10. sizeof(a)、a+i*sizeof(a0)、a+i11. 參數(shù)類型、數(shù)量、次序 12. 2、用戶自定義 13. = = 、ra 、rb 14. O(n)、O(m*n)15. n、n(n+1)/2、O(n2) 16. O(n)第二章 線性表 一、單選題1. B 2. A 3. C 4. B 5. D 6. C二、填空題1.元素值、指針 2.( 38,56,25,60,42,7

25、4) 3. O(n)、O(1) 4.(1)、O(n) 5.i-1、i+1p->next 、ap.next 7.表頭 8.前驅(qū)、后繼 9.表尾、表頭 10HL->next = = NULL 、HL->next = = HL三、應(yīng)用題1.(1) ( 79 , 62 , 34 , 57 , 26 , 48 ) (2) ( 26 , 34 , 48 , 57 , 62 , 79 ) (3) ( 26, 34 , 39 , 48 , 57 , 62 )212，26，9，8，15，30，50）3(1) ElemType DMValue( List & L ) if ( ListE

26、mpty(L) ) / 空線性表 cerr <<"List is Empty!"<<endl; exit(1);ElemType x; / x存放最小元素x = L.list0;int k = 0; / k存放最小元素的下標(biāo)for ( int i = 1; i<L.size; i+ ) / 查找最小元素 if ( L.listi < x ) x = L.listi ; k = i; L.listk = L.listL.size-1; / 最后一個(gè)元素填補(bǔ)最小元素位置L.size-; / 線性表長(zhǎng)度減1return x; / 返回最小元素

27、2)ElemType Delete( List & L, int i ) if ( i<1 | i>L.size ) / 判斷i的合法性printf("Index is out range!n”);exit(1); ElemType x = L.listi-1; / 保存被刪除元素 for ( int j = i-1; j<L.size-1; j+ ) / 元素向前移動(dòng) L.listj = L.listj+1; L.size-; / 長(zhǎng)度減1 return x; / 返回被刪元素 (3)void Insert( List & L, int i, El

28、emType x ) if ( i<1 | i>L.size+1 ) / 判斷i的合法性printf("Index is out range!n");exit(1); if ( L.size = MaxSize ) / 判斷線性表滿 printf("List overflow!n");exit(1); for ( int j = L.size-1 ; j>=i-1 ; j- ) / 元素后移，產(chǎn)生插入位置L.listj+1 = L.listj; L.listi-1 = x; / 元素插入 L.size+; / 長(zhǎng)度加1 (4) void

29、 Delete( List & L, ElemType x ) int i = 0; while ( i<L.size ) if ( L.listi = x ) / 刪除x元素for ( int j = i+1; j<L.size; j+ ) L.listj-1 = L.listj;L.size-; else i+; / 尋找下一個(gè)x元素的位置 4(1)void Delete( LNode * & HL, int i ) if ( i<1 | HL=NULL ) / 判斷i的合法性或空鏈表cerr <<"index is out rang

30、e!"<<endl;exit(1); LNode * ap , * cp; ap = NULL ; cp = HL ; / cp指向當(dāng)前結(jié)點(diǎn)，ap指向其前驅(qū)結(jié)點(diǎn) int j = 1; while ( cp != NULL ) / 查找第i個(gè)結(jié)點(diǎn) if ( j = i ) / 找到第i個(gè)結(jié)點(diǎn)break; / cp指向的結(jié)點(diǎn)即為第i個(gè)結(jié)點(diǎn) else / 繼續(xù)向后尋找ap = cp;cp = cp->next;j+; if ( cp = NULL ) / 沒有找到第i個(gè)結(jié)點(diǎn)cerr <<"Index is out range!"<&l

31、t;endl;exit(1); if ( ap = NULL ) / 刪除第1個(gè)結(jié)點(diǎn)（即i=1） HL = HL->nextl else ap->next = cp->next; / 刪除第i個(gè)結(jié)點(diǎn) delete cp; / 釋放被刪除結(jié)點(diǎn)的空間 (2)void Insert( LNode * & HL, const ElemType & x ) LNode * newptr = new LNode; / 申請(qǐng)一個(gè)新結(jié)點(diǎn) if ( newptr = NULL ) / 分配失敗cerr <<"Memory allocation failar

32、e!"<<endl;exit(1); newptr->data = x; if ( HL = NULL | x<HL->data ) / 空表 或 x小于表頭結(jié)點(diǎn)，newptr->next = HL; / 作為新表頭結(jié)點(diǎn)插入HL = newptr;return; / 查找插入位置 LNode * cp = HL->next; / 用cp指向當(dāng)前結(jié)點(diǎn)（即待查結(jié)點(diǎn)） LNode * ap = HL; / 用ap作為指向當(dāng)前結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)指針 while ( cp != NULL ) if ( x<cp->data) break; /

33、找到插入位置 else ap = cp; cp = cp->next; / 繼續(xù)查找插入位置 newptr->next = cp; ap->next = newptr; / 插入新結(jié)點(diǎn) (3)ElemType MaxValue( LNode * HL ) if ( HL = NULL ) / 空表 cerr <<"Linked list is empty!"<<endl; exit(1);ElemType max = HL->data;LNode * p = HL->next;while ( p != NULL ) /

34、尋找最大值 if ( max < p->data ) max = p->data; p = p->next;return max; (4)int Count( LNode * HL , ElemType x ) int n = 0; LNode * p = HL; while ( p != NULL ) if ( p->data = x ) n+; p = p->next; return n; 第三章 稀疏矩陣和廣義表 一、單選題1. A 2. B二、填空題1.行號(hào)、列號(hào)、元素值 2.行號(hào)、列號(hào) 3.引用 (或指針) 4.等于 5.4 、5 6.列號(hào)、行號(hào)

35、7. 單、表 8. 括號(hào) 9. 3 10. 元素值、子表指針 11. true、NULL三、應(yīng)用題1(1) ( (1,2,4),(2,4,-3),(2,7,1),(3,1,8),(4,4,5),(5,2,-7),(5,6,2),(6,4,6) )12234556247142644-3185-726 (2) (3) (1,3,8),(2,1,4),(2,5,-7),(4,2,-3),(4,4,5), (4,6,6),(6,5, 2),(7,2,1)122444673152465284-7-356212(1) A：長(zhǎng)度：1 深度：2 (2) B：長(zhǎng)度：3 深度：1 (3) C：長(zhǎng)度：2 深度：3

36、(4) D：長(zhǎng)度：2 深度：2 (5) E：長(zhǎng)度：3 深度：3 (6) F：長(zhǎng)度：1 深度：4第四章 棧和隊(duì)列 一、單選題1. A 2. B 3. C 4. A 5. B 6. B 7. D 8. D二、填空題1.隊(duì)尾、隊(duì)首 2.后進(jìn)先出(LIFO)、先進(jìn)先出(FIFO) 3.棧頂指針、存儲(chǔ) 4.棧頂元素、棧頂指針5. front = = rear 、(rear+1)%QueueMaxSize = = front 6. -1 、StackMaxSize-17. ?？?、空隊(duì)、隊(duì)列只有一個(gè)元素 8.新結(jié)點(diǎn)的指針域、棧頂指針 9.指針域、棧頂指針 10.隊(duì)尾指針、存儲(chǔ) 11.top = = 0 12

37、.p->next = HS 、HS = p 13. HS = HS->next14. ( front = = rear ) && ( front <>NULL ) 15. 3 4 25 6 15 + - / 8 * +16. (24+8)*3/(4*(10-7) 、8三、應(yīng)用題 12 15 5 30 18四、編程題遞歸算法：long Fib( int n ) if ( n=1 | n=2 ) / 終止遞歸條件 return 1;else return Fib(n-1)+Fib(n-2);非遞歸算法：long Fib( int n ) int a , b

38、, c; / c代表當(dāng)前項(xiàng)，a和b分別代表當(dāng)前項(xiàng)前面的第2項(xiàng)和第1項(xiàng)a = b = 1;if ( n = 1 | n = 2 ) return 1;else for ( int i = 3 ; i<=n ; i+ ) c = a+b; / 求當(dāng)前項(xiàng) a = b; / 產(chǎn)生第2項(xiàng) b = c; / 產(chǎn)生第1項(xiàng) return c; / 返回所求的第n項(xiàng) 遞歸算法的時(shí)間復(fù)雜度為 O(2n)，空間復(fù)雜度為 O(n)；非遞歸算法的時(shí)間復(fù)雜度為 O(n)，空間復(fù)雜度為 O(1)。第五章 樹和二叉樹一、填空題1.n-1 2.5 、50 3. 6 4.31、21 5.10、4、3 6.2、1、1、6 7

39、.B、I和J 8.6 9. 2i、2i+1、? i/2? 10.16 11.5、18 12.a、f、空結(jié)點(diǎn)(即無右孩子結(jié)點(diǎn)) 13. 4、2、314. a2*i、a2*i+1、ai/2 15. 2i-1、2j+1 16. A2*i+1、a2*i+2、ai/2 17.2n、n-1、n+1 18.10、5 19. abcdef、cbaedf、cbefda、abdcef 20. abecfhijgd、abcdefghij二、應(yīng)用題1void Request( int A , int n , int i ) if ( i>n ) cerr <<"編號(hào)為"<<i<<"的結(jié)點(diǎn)不存在！"<<endl; exit(1);cout <<"當(dāng)前結(jié)點(diǎn)為"<<Ai<<endl;int j = i/2; / 下標(biāo)為j的結(jié)點(diǎn)是下標(biāo)為i結(jié)點(diǎn)的雙親if ( j>0 ) cout <<"雙親："<<Aj<<endl;else cout <<"樹根沒有雙親結(jié)點(diǎn)！"