數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題(4A)

1、數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題第1章 緒論一、單選題（共有題目8題）1.從一維數(shù)組an中順序查找出一個最大值元素的時間復(fù)雜度為（ ）。A. O(1) B. O(n) C. O(n2) D. O(n!)標(biāo)準(zhǔn)答案：B2.輸出一個二維數(shù)組bmn中所有元素值的時間復(fù)雜度為（ ）。A. O(m+n) B. O(mn) C. O(m2) D. O(n2) 標(biāo)準(zhǔn)答案：B3.下面程序段的時間復(fù)雜度是（ ）。for( int i=0;im;i+) for(int j=0;jn;j+)aij=i*j;A. O(m2) B. O(n2) C. O(mn) D. O(m+n)標(biāo)準(zhǔn)答案：C4.分析下面程序段的時間復(fù)雜度是（ ）。int

2、 i=1;while (i=n)i=i*2;A. O(n) B. O(log2n) C. O(n2) D. O(1)標(biāo)準(zhǔn)答案：B5.下面程序段的時間復(fù)雜度是（ ）。int i,j;for(i=1;i=n;i+)for (j=1;j=i;j+)S;A. O(n) B. O(n 2) C. O( log2n) D. O(1)標(biāo)準(zhǔn)答案：B S語句執(zhí)行的次數(shù)為n(n+1)/2。6.下面算法的時間復(fù)雜度為（ ）。int f( int n) if(n=0|n=1) return 1; else return n*f(n-1); A. O(n) B. O(1) C. O(n 2) D. O(n!)標(biāo)準(zhǔn)答案：

3、A7.下面程序段的時間復(fù)雜度是（ ）。int i,j;for( i=0; in; i+) for(j=0; jm;j+) aij=i*j;A. O(n 2) B. O(m 2) C. O(mn) D. O(m+n)標(biāo)準(zhǔn)答案：C二、多選題（共有題目1題） 1.int Prime(int n) int h=n/2;int i;for(i=2;ih) return 1;else return 0;請問該算法的功能是什么？它的時間復(fù)雜度數(shù)量級是哪個？標(biāo)準(zhǔn)答案：判斷整數(shù)n是不是素數(shù)；O(n)三、填空題（共有題目14題）1.在線性結(jié)構(gòu)中，前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)之間存在著1對1(1：1 或 一對一)的聯(lián)系。2.

4、對算法評價一般從正確性、健壯性、可讀性、簡單性、時間復(fù)雜度、空間復(fù)雜度六個方面進(jìn)行的。3.在圖形結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點(diǎn)之間存在著多對多;m：n的聯(lián)系。4.數(shù)據(jù)結(jié)構(gòu)研究的內(nèi)容主要包括數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)的存儲結(jié)構(gòu)（數(shù)據(jù)的物理結(jié)構(gòu)）和數(shù)據(jù)的操作三部分。5.數(shù)據(jù)的物理結(jié)構(gòu)又名存儲結(jié)構(gòu)_，它主要有順序存儲、鏈接存儲、索引和散列4種方式。6.在樹形結(jié)構(gòu)中，前驅(qū)和后繼結(jié)點(diǎn)之間存在著1對多（1：N）聯(lián)系。7.數(shù)據(jù)的邏輯結(jié)構(gòu)被分為集合結(jié)構(gòu)、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖形結(jié)構(gòu)4種。8.算法是指對特定問題求解步驟的一種描述，是一組指令的有限序列；也可以說是解決特定問題的方法步驟。9.在一個算法的程序描述中，不同的語句重

5、復(fù)執(zhí)行的次數(shù)不同，某語句重復(fù)執(zhí)行的次數(shù)稱為該語句的頻度（頻次）。10.記錄（數(shù)據(jù)記錄）是數(shù)據(jù)處理領(lǐng)域組織數(shù)據(jù)的基本單位。11.依據(jù)視點(diǎn)的不同，數(shù)據(jù)結(jié)構(gòu)分為數(shù)據(jù)的邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)是面向問題的，數(shù)據(jù)的物理結(jié)構(gòu)（數(shù)據(jù)的存儲結(jié)構(gòu)）是面向計(jì)算機(jī)的。12.算法應(yīng)具備有窮性、確定性、可行性、輸入和輸出五個特性。13.在下面程序段中，s=s+p語句的執(zhí)行次數(shù)是n，p*=j語句的執(zhí)行次數(shù)是n(n+1)/2，該程序段的時間復(fù)雜度為O(n 2)。int i=0,s=0;while(+i=n) int p=1;for( int j=1;jnext; B. L- next = L- next - ne

6、xt; C. L = L; D. L- next = L;標(biāo)準(zhǔn)答案：B4. 給定有n個元素的數(shù)組，建立一個有序單鏈表的時間復(fù)雜度是（ ）A. O(1) B. O(n) C. O(n2) D. O(nlog2n)標(biāo)準(zhǔn)答案：B5.在一個單鏈表HL中，若要刪除由指針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-next;q-next=p-next; D. q-next=q-next-next;q-next=q;標(biāo)準(zhǔn)答案：C6.在一個長度為n的順序表中刪除第i個元素（0in-1）時，需要從前向后依次前

7、移（ ）個元素。A. n-i B. n-i+1 C. n-i-1 D. i標(biāo)準(zhǔn)答案：C7.若線性表最常用的操作是存取第i個元素及其前驅(qū)的值，則采用( )存儲方式節(jié)省時間。A. 單鏈表 B. 雙鏈表 C. 單循環(huán)鏈表 D. 順序表標(biāo)準(zhǔn)答案：D8.不帶頭結(jié)點(diǎn)的單鏈表first為空的判定條件是（ ）。A. first = NULL; B. first- next = NULL;C. first- next = first; D. first != NULL;標(biāo)準(zhǔn)答案：A9.執(zhí)行下面程序段時，執(zhí)行S語句的次數(shù)為( )。for(int i=1; i=n; i+)for(int j=1; jlink所指向

8、的結(jié)點(diǎn)，則應(yīng)執(zhí)行的操作是（ ）。A. p-link=p-link-link; B. p=p-link; p-link=p-link-link;C. p-link=p; D. p=p-link-link;標(biāo)準(zhǔn)答案：A11. 一個數(shù)組元素ai 與( )的表示等價。A. *(a+i) B. a+i C. *a+i D. &a+i標(biāo)準(zhǔn)答案：A12. 非空的循環(huán)單鏈表head的尾指針p滿足( )。A. p-next=NULL B. p=NULL C. P-next=head D. p=head標(biāo)準(zhǔn)答案：C13.在二維數(shù)組A810中，每一個數(shù)組元素Aij占用3個存儲空間，所有數(shù)組元素相繼存放于一個連續(xù)的存

9、儲空間中，則存放該數(shù)組至少需要的存儲空間是（ ）。A. 80 B. 100 C. 240 D. 270標(biāo)準(zhǔn)答案：C14.在一個長度為n的順序表中順序搜索一個值為x的元素時，在等概率的情況下，搜索成功時的數(shù)據(jù)平均比較次數(shù)為（ ）。A. n B. n/2 C. (n+1)/2 D. (n-1)/2標(biāo)準(zhǔn)答案：C15.帶頭結(jié)點(diǎn)的單鏈表first為空的判定條件是（ ）。A. first=NULL; B. first- next =NULL;C. first- next =first; D. first!=NULL;標(biāo)準(zhǔn)答案：B16. 一個算法的時間復(fù)雜度為(3n2+2nlog2n+4n-7)/(5n)，

10、其數(shù)量級形式的復(fù)雜度表示為( )。A. O(n) B. O(nlog2n) C. O(n2) D. O(log2n)標(biāo)準(zhǔn)答案：A17.某算法僅含程序段1和程序段2，程序段1的執(zhí)行次數(shù)3n2，程序段2的執(zhí)行次數(shù)為0.01n3，則該算法的時間復(fù)雜度為（ ）。A. O(n) B. O(n2) C. O(n3) D. O(1)標(biāo)準(zhǔn)答案：C19.有一個含頭結(jié)點(diǎn)的單鏈表，頭指針為head，則判斷其是否為空的條件為( )。A.head=NULL B. Head-next=NULLC. head-next=head D. Head!=NULL標(biāo)準(zhǔn)答案：B20. 設(shè)有一個nn的對稱矩陣A，將其上三角部分按行存放

11、在一個一維數(shù)組B中，A00存放于B0中，那么第i行的對角元素Aii存放于B中（ ）處。A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/2標(biāo)準(zhǔn)答案：C21.在一個單鏈表中，若q結(jié)點(diǎn)是p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q與p之間插入結(jié)點(diǎn)s，則執(zhí)行（ ）。A. snext = pnext; pnext = s; B. pnext = s; snext = q;C. pnext = snext; snext = p; D. qnext = s; snext = p;標(biāo)準(zhǔn)答案：D22.在一個長度為n的順序存儲的線性表中，刪除第i個元素（1in）時，需要

12、從前向后依次前移（ ）個元素。A. n-i B. n-i+1 C. n-i-1 D. i標(biāo)準(zhǔn)答案：A23.設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data, link）。已知指針q所指結(jié)點(diǎn)是指針p所指結(jié)點(diǎn)的直接前驅(qū)，若在*q與*p之間插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行的操作是（ ）。A. s-link=p-link; p-link=s; B. q-link=s; s-link=p;C. p-link=s-link; s-link=p; D. p-link=s; s-link=q;標(biāo)準(zhǔn)答案：B24.在一個長度為n的有序順序表中搜索值為x元素的時間效率最高的算法的漸進(jìn)時間復(fù)雜度為（ ）。A. O(1) B. O(1) C.

13、O(log2n) D. O(n)標(biāo)準(zhǔn)答案：C25.在一個單鏈表HL中，若要在指針q所指向結(jié)點(diǎn)的后面插入一個由指針p所指向的結(jié)點(diǎn)，則執(zhí)行（ ）。 A. q-next=p-next; p-next=q; B. p-next=q-next; q=p;C. q-next=p-next; q-next=p; D. p-next=q-next; q-next=p;標(biāo)準(zhǔn)答案：D26.已知L是一個不帶表頭的單鏈表，在表首插入結(jié)點(diǎn)*p的操作是（ ）。A. p = L; p- next = L; B. p- next = L; p = L;C. p- next = L; L = p; D. L = p; p- n

14、ext = L;標(biāo)準(zhǔn)答案：C27.設(shè)單循環(huán)鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data, link），且rear是指向非空的帶表頭結(jié)點(diǎn)的單循環(huán)鏈表的尾結(jié)點(diǎn)的指針。若想刪除鏈表第一個結(jié)點(diǎn)，則應(yīng)執(zhí)行的操作是（ ）。A. s = rear; rear = rear-link; delete s;B. rear = rear-link; delete rear;C.rear = rear-link-link; delete rear;D.s = rear-link-link; rear-link-link = s-link; delete s;標(biāo)準(zhǔn)答案：D28.某算法的時間代價為T(n)=100n+10nlog2n+

15、n2+10，其時間復(fù)雜度為（ ）。A. O(n) B. O(nlog2n) C. O(n2) D. O(1)標(biāo)準(zhǔn)答案：C29.在一個長度為n的順序表中向第i個元素（0in-1）位置插入一個新元素時，需要從后向前依次后移（ ）個元素。A. n-i B. n-i+1 C. n-i-1 D. i標(biāo)準(zhǔn)答案：A30.在一個長度為n的順序表的任一位置插入一個新元素的時間復(fù)雜度為（ ）。A. O(n) B. O(n/2) C. O(1) D. O(n2)標(biāo)準(zhǔn)答案：A31.多維數(shù)組實(shí)際上是由嵌套的（ ）實(shí)現(xiàn)的。A. 一維數(shù)組 B. 多項(xiàng)式 C. 三元組表 D. 簡單變量標(biāo)準(zhǔn)答案：A32.設(shè)有一個nn的對稱矩陣

16、A，將其下三角部分按行存放在一個一維數(shù)組B中，A00存放于B0中，那么第i行的對角元素Aii存放于B中（ ）處。A. (i+3)*i/2 B. (i+1)*i/2 C. (2n-i+1)*i/2 D. (2n-i-1)*i/2標(biāo)準(zhǔn)答案：A33.利用雙向鏈表作線性表的存儲結(jié)構(gòu)的優(yōu)點(diǎn)是（ ）。A. 便于單向進(jìn)行插入和刪除的操作 B. 便于雙向進(jìn)行插入和刪除的操作C. 節(jié)省空間 D. 便于銷毀結(jié)構(gòu)釋放空間標(biāo)準(zhǔn)答案：B34.在數(shù)據(jù)結(jié)構(gòu)的討論中把數(shù)據(jù)結(jié)構(gòu)從邏輯上分為（ ）。A. 內(nèi)部結(jié)構(gòu)與外部結(jié)構(gòu) B. 靜態(tài)結(jié)構(gòu)與動態(tài)結(jié)構(gòu)C. 線性結(jié)構(gòu)與非線性結(jié)構(gòu) D. 緊湊結(jié)構(gòu)與非緊湊結(jié)構(gòu)標(biāo)準(zhǔn)答案：C35.單鏈表A長

17、度為m，單鏈表B長度為n，若將B聯(lián)接在A的末尾，其時間復(fù)雜度應(yīng)為（ ）。A. O(1) B. O(m) C. O(n) D. O(m+n)標(biāo)準(zhǔn)答案：B36.帶表頭的雙向循環(huán)鏈表的空表滿足（ ）。A. firstNULL; B. first-rLink=firstC. first-lLink=NULL D. first-rLink=NULL標(biāo)準(zhǔn)答案：B37.一個記錄r理論上占有的存儲空間的大小等于所有域類型長度之和，實(shí)際上占有的存儲空間的大小即記錄長度為( )。A. 所有域長度之和 B. 最大域所占字節(jié)長度C. 任意一個域長度 D. sizeof(r)的值標(biāo)準(zhǔn)答案：D38.采用順序搜索方法查找長

18、度為n的順序表時，搜索成功的平均搜索長度為（ ）。A. n B. n/2 C. (n-1)/2 D. (n+1)/2標(biāo)準(zhǔn)答案：D39.在二維數(shù)組中，每個數(shù)組元素同時處于（ ）個向量中。A. 0個 B. 1個 C. 2個 D. n個標(biāo)準(zhǔn)答案：C40.設(shè)單鏈表中結(jié)點(diǎn)的結(jié)構(gòu)為（data, link）。已知指針p所指結(jié)點(diǎn)不是尾結(jié)點(diǎn)，若在*p之后插入結(jié)點(diǎn)*s，則應(yīng)執(zhí)行的操作是（ ）。A. s-link=p; p-link=s; B. p-link=s; s-link=p;C. s-link=p-link; p=s; D. s-link=p-link; p-link=s;標(biāo)準(zhǔn)答案：D41.非空的循環(huán)單鏈表

19、first的尾結(jié)點(diǎn)（由p所指向）滿足的條件是（ ）。A. p-link=NULL; B. p=NULL; C. p-link=first; D. p=first;標(biāo)準(zhǔn)答案：C42.從一個具有n個結(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時，在查找成功的情況下，需要平均比較的結(jié)點(diǎn)數(shù)是（ ）。A. n B. n/2 C. (n-1)/2 D. (n+1)/2標(biāo)準(zhǔn)答案：D43.采用線性鏈表表示一個向量時，要求占用的存儲空間地址（ ）。A. 必須是連續(xù)的 B. 部分地址必須是連續(xù)的C. 一定是不連續(xù)的 D. 可連續(xù)可不連續(xù) 標(biāo)準(zhǔn)答案：D44.在一個具有n個結(jié)點(diǎn)的有序單鏈表中插入一個新結(jié)點(diǎn)并仍然保持有序的時間復(fù)雜

20、度是（ ）。A. O(1) B. O(n) C. O(n2) D. O(nlog2n)標(biāo)準(zhǔn)答案：B45.在一個長度為n的順序存儲的線性表中，向第i個元素（1in+1）位置插入一個新元素時，需要從后向前依次后移（ ）個元素。A. n-i B. n-i+1 C. n-i-1 D. i標(biāo)準(zhǔn)答案：B46.在一個單鏈表HL中，若要向表頭插入一個由指針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;標(biāo)準(zhǔn)答案：B47.下面程序段的時間復(fù)雜度為( )。 f

21、or(int i=0; im; i+) for(int j=0; jnext=NULL和HL-next=HL。2.線性表的鏈接存儲只能通過鏈接指針順序訪問。3.鏈表是一種采用鏈?zhǔn)剑ɑ蜴溄觃）存儲結(jié)構(gòu)存儲的線性表。4.在線性表的單鏈接存儲結(jié)構(gòu)（結(jié)點(diǎn)）中，若一個元素所在結(jié)點(diǎn)的地址為p，則其后繼結(jié)點(diǎn)的地址為p-next，后繼結(jié)點(diǎn)的值為p-next-data。5.若設(shè)L是指向帶表頭的單鏈表, 語句 L-link=L-link-link的作用是刪除單鏈表中的第一個結(jié)點(diǎn)。6.在單鏈表中除了表頭結(jié)點(diǎn)外，任意結(jié)點(diǎn)的存儲位置由其直接前驅(qū)結(jié)點(diǎn)的指針域的值所指示。7.在雙向鏈表中，每個結(jié)點(diǎn)包含兩個指針域，一個指向其

22、前驅(qū)（雙親、父）結(jié)點(diǎn)，另一個指向其后繼（孩子、子）結(jié)點(diǎn)。8.鏈接存儲表示的結(jié)點(diǎn)存儲空間一般在程序的運(yùn)行過程中進(jìn)行動態(tài)地分配_和釋放。9.在鏈表中進(jìn)行插入和刪除操作的效率比在順序存儲結(jié)構(gòu)中進(jìn)行相同操作的效率高。10.在線性表的單鏈接存儲結(jié)構(gòu)（結(jié)點(diǎn)）中，若一個元素所在結(jié)點(diǎn)的地址為p，p為一個數(shù)組a中的下標(biāo)，則其后繼結(jié)點(diǎn)的地址為&ap.next 或(a+p)-next。11.在線性表的順序存儲結(jié)構(gòu)中，若一個元素的下標(biāo)為i，則它的前驅(qū)元素的下標(biāo)為i-1，后繼元素的下標(biāo)為i+1_。12.單鏈表中邏輯上相鄰的結(jié)點(diǎn)而在物理位置上不一定相鄰。13.鏈表對于數(shù)據(jù)元素的插入和刪除不需要移動結(jié)點(diǎn)，只需要改變相應(yīng)結(jié)點(diǎn)

23、的指針域的值。14.在循環(huán)雙向鏈表中表頭結(jié)點(diǎn)的左指針域指向表尾結(jié)點(diǎn)，最后一個結(jié)點(diǎn)的右指針域指向表頭結(jié)點(diǎn)。15.對于一個單鏈接存儲的線性表，在表頭插入結(jié)點(diǎn)的時間復(fù)雜度為O(1)，在表尾插入元素的時間復(fù)雜度為O(n)。16.在循環(huán)單鏈表中，最后一個結(jié)點(diǎn)的指針域指向表頭_結(jié)點(diǎn)。17.對于一個長度為n的順序存儲的線性表，在表頭插入元素的時間復(fù)雜度為O(n)，在表尾插入元素的時間復(fù)雜度為O(1)。18.鏈表與順序表、索引表、散列表等都是數(shù)據(jù)邏輯結(jié)構(gòu)的存儲表示。19.在線性表的單鏈接存儲結(jié)構(gòu)中，每個結(jié)點(diǎn)包含有兩個域，一個叫數(shù)值域，另一個叫指針域。20.在單鏈表設(shè)置表頭結(jié)點(diǎn)的作用是插入和刪除表中第一個元素時

24、不必對表頭指針進(jìn)行特殊處理。21.在雙向鏈表中， 每個結(jié)點(diǎn)除了數(shù)據(jù)域外, 還有兩個指針域, 它們分別指向前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。22.鏈表只適用于順序查找。23.設(shè)雙向循環(huán)鏈表每個結(jié)點(diǎn)結(jié)構(gòu)為(data,llink,rlink)，則結(jié)點(diǎn)*p的前驅(qū)結(jié)點(diǎn)的地址為p-llink。24.線性表是具有相同屬性_的數(shù)據(jù)元素的一個有限序列。25.邏輯順序與物理順序一致的數(shù)據(jù)結(jié)構(gòu)是_。三、判斷題（共有題目17題）1.數(shù)據(jù)的邏輯結(jié)構(gòu)是指各數(shù)據(jù)元素之間的邏輯關(guān)系，是用戶根據(jù)應(yīng)用需要建立的。對2.多維數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的。對3. 線性表若采用鏈?zhǔn)酱鎯Ρ硎緯r，其存儲結(jié)點(diǎn)的地址

25、可連續(xù)也可不連續(xù)。對4.在順序表中，邏輯上相鄰的元素在物理位置上不一定相鄰。錯5.用字符數(shù)組存儲長度為n的字符串，數(shù)組長度至少為n+1。對 6.數(shù)據(jù)元素是數(shù)據(jù)的最小單位。錯7.在對雙向循環(huán)鏈表做刪除一個結(jié)點(diǎn)操作時，應(yīng)先將被刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)鏈接好再執(zhí)行刪除結(jié)點(diǎn)操作。 對8. 如果采用如下方法定義一維字符數(shù)組： int maxSize = 30; char * a = new charmaxSize; 錯9.線性表若采用鏈?zhǔn)酱鎯Ρ硎? 在刪除時不需要移動元素。對 10.數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)。對11. 如果采用如下方式定義一維字符數(shù)組： const int max

26、Size = 30; char amaxSize; 則這種數(shù)組在程序執(zhí)行過程中不能擴(kuò)充。對 12.算法和程序原則上沒有區(qū)別，在討論數(shù)據(jù)結(jié)構(gòu)時二者是通用的。 錯13. 順序表和一維數(shù)組一樣，都可以按下標(biāo)隨機(jī)（或直接）訪問。對 14.在線性鏈表中刪除中間的結(jié)點(diǎn)時，只需將被刪結(jié)點(diǎn)釋放。 錯四、程序填空題（共有題目3題）1.下面程序段實(shí)現(xiàn)的功能是向單鏈表的表頭插入一個元素X，請補(bǔ)充完整程序。void InsertFirstList(struct sNode *HL,ElemType x) struct sNode *newp;newp=malloc(sizeof(struct sNode); if(n

27、ewp=NULL) printf(內(nèi)存動態(tài)空間用完，退出運(yùn)行！n); exit(1); newp-data=X; newp-next=*HL; *HL=newp;2.下面程序段實(shí)現(xiàn)的功能是向單鏈表的表尾插入一個元素X，請補(bǔ)充完整程序。void InsertLastList(struct sNode *HL,ElemType x) struct sNode *newp;newp=malloc(sizeof(struct sNode); if(newp=NULL) printf(內(nèi)存動態(tài)空間用完，退出運(yùn)行！n);exit(1); newp-data=x;newp-next=NULL或 0;if(*

28、HL=NULL)*HL=newp;Elsestruct sNode *p=*HL; while(p-next!=NULL)p=p-next;p-next=newp;3.欲向線性表L的表頭插入元素X，完成下面程序段中的部分語句：void InsertFirstList( struct List *L,ElemType X)int i;if(_L-size=L-MaxSize)againMalloc(L);for(i=L-size-1;i=0;i-)L-listi+1=L-listi;L-list0=X; L-size+;第3章 稀疏矩陣和廣義表一、單選題（共有題目4題）1.設(shè)一個具有t個非零元素

29、的mn大小的稀疏矩陣采用順序存儲，求其轉(zhuǎn)置矩陣的普通轉(zhuǎn)置算法的時間復(fù)雜度為（ ）。A. O(m) B. O(n) C. O(n+t) D. O(nt)標(biāo)準(zhǔn)答案：D2.在稀疏矩陣的帶行指針向量的鏈接存儲中，每個行單鏈表中的結(jié)點(diǎn)都具有相同的（ ）。A. 行號 B. 列號 C. 元素值 D. 地址標(biāo)準(zhǔn)答案：A3.廣義表( )的表頭是( )。A. ( ) B. 沒有表頭 C. ( ) D. 0標(biāo)準(zhǔn)答案：B4.廣義表( )的表尾是( )。A. 沒有表尾 B. ( ) C. ( ( ) ) D. 0標(biāo)準(zhǔn)答案：A二、填空題（共有題目16題） 1.在一個稀疏矩陣中，每個非零元素所對應(yīng)的三元組包括該元素的行號、

30、列號和元素值3項(xiàng)。2.( ),(e),(a,(b,c,d)的表頭是() 或 空表。3.一個廣義表中的元素分為單（原子）元素和表（子表）元素兩類。4.在廣義表的存儲結(jié)構(gòu)中，單元素結(jié)點(diǎn)與表元素結(jié)點(diǎn)有一個域?qū)?yīng)不同，各自分別為值域和子表指針域。5.一個廣義表的深度等于括號嵌套的最大層次數(shù)。6.稀疏矩陣是一種非零元素的個數(shù)遠(yuǎn)遠(yuǎn)小于零元素的個數(shù)，且非零元素的分布沒有規(guī)律的矩陣。7.廣義表( )的表頭是( ) 或 空表。8.在稀疏矩陣的順序存儲中，利用一個數(shù)組來存儲非零元素，該數(shù)組的長度應(yīng)大于對應(yīng)三元組線性表的長度。9.廣義表(e),(a,(b,c,d)的深度是3。10.廣義表( ( ) )的表尾是( )

31、 或 空表。11.( ),(e),(a,(b,c,d)的表尾是(e),(a,(b,c,d)。12.在一個廣義表的存儲結(jié)構(gòu)中，每個結(jié)點(diǎn)均包含有_3個域。13.廣義表(e),(a,(b,c,d)的長度是2。14.在稀疏矩陣的帶行指針向量的鏈接存儲中，每個結(jié)點(diǎn)包含有4個域，在相應(yīng)的十字鏈接存儲中，每個結(jié)點(diǎn)包含有5個域。15.在稀疏矩陣的十字鏈接存儲中，每個結(jié)點(diǎn)的down指針域指向列號相同的下一個結(jié)點(diǎn)，right指針域指向行號相同的下一個結(jié)點(diǎn)。16.在稀疏矩陣所對應(yīng)的三元組線性表中，每個三元組元素按行號為主序列號為輔序的次序排列。三、判斷題（共有題目1題）1.使用三元組表示稀疏矩陣中的非零元素能節(jié)省存

32、儲空間。對 第4章 棧和隊(duì)列一、單選題（共有題目9題） 1.在一個順序隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的（ ）位置。A. 前一個 B. 后一個 C. 當(dāng)前 D. 后面標(biāo)準(zhǔn)答案：A2.假定利用數(shù)組aN循環(huán)順序存儲一個隊(duì)列，用f和r分別表示隊(duì)首和隊(duì)尾指針，并已知隊(duì)未空，當(dāng)進(jìn)行出隊(duì)并返回隊(duì)首元素時所執(zhí)行的操作為( )。A. return a+r%N; B. return a-r%N; C. return a+f%N; D. return af+%N;標(biāo)準(zhǔn)答案：C3.一個鏈棧的棧頂指針用top表示，當(dāng)進(jìn)行退棧時所進(jìn)行的指針操作為（ ）。A. top-next=top; B. top=top-data;C.

33、 top=top-next; D. top-next=top-next-next;標(biāo)準(zhǔn)答案：C4.一個鏈棧的棧頂指針用top表示，當(dāng)p所指向的結(jié)點(diǎn)進(jìn)棧時，執(zhí)行的操作為（ ）。A. p-next =top; top=top-next; B. top=p; p-next=top; C. p-next=top-next;top-next=p; D. p-next=top;top=p;標(biāo)準(zhǔn)答案：D5.棧的插入和刪除操作在（ ）進(jìn)行。A. 棧頂 B. 棧底 C. 任意位置 D. 指定位置標(biāo)準(zhǔn)答案：A6.當(dāng)利用大小為N的數(shù)組順序存儲一個隊(duì)列時，若沒設(shè)有隊(duì)列長度的變量，則該隊(duì)列的最大長度為（ ）。A. N-

34、2 B. N-1 C. N D. N+1標(biāo)準(zhǔn)答案：B7.若讓元素1、2、3依次進(jìn)棧，則出棧次序不可能出現(xiàn)（ ）情況。A. 3，2，1 B. 2，1，3 C. 3，1，2 D. 1，3，2標(biāo)準(zhǔn)答案：C8.從一個順序隊(duì)列刪除元素時，首先需要（ ）。A. 隊(duì)首指針循環(huán)加1 B. 隊(duì)首指針循環(huán)減1C. 取出隊(duì)首指針?biāo)肝恢蒙系脑?D.取出隊(duì)尾指針?biāo)肝恢蒙系脑貥?biāo)準(zhǔn)答案：A9.假定一個鏈隊(duì)的隊(duì)首和隊(duì)尾指針分別為front和rear，則判斷隊(duì)空的條件為( )。A. front=rear B. front!=NULL C. rear!=NULL D. front=NULL標(biāo)準(zhǔn)答案：D二、填空題（共有題目

35、7題） 1.后綴表達(dá)式“4 5 * 3 2 + -”的值為15。2.棧又稱為后進(jìn)先出表，隊(duì)列又稱為先進(jìn)先出_表。3.隊(duì)列的插入操作在隊(duì)尾進(jìn)行，刪除操作在隊(duì)首進(jìn)行。4.中綴表達(dá)式3*(x+2)-5所對應(yīng)的后綴表達(dá)式為3 x 2 + * 5 -。5.在一個鏈隊(duì)中，若隊(duì)首指針與隊(duì)尾指針的值相同，則表示該隊(duì)為空或該隊(duì)只含有一個結(jié)點(diǎn)。6.在一個不設(shè)隊(duì)列長度變量的順序隊(duì)列Q中，判斷隊(duì)空的條件為Q.front=Q.rear，判斷隊(duì)滿的條件為(Q.rear+1)% Q.MaxSize=Q.front。7.向一個棧頂指針為HS的鏈棧中插入一個新結(jié)點(diǎn)*p時，應(yīng)執(zhí)行p-next=HS和HS=p操作。第5章 樹和二叉

36、樹一、單選題（共有題目17題） 1.在一棵完全二叉樹中，若編號為i 的結(jié)點(diǎn)存在左孩子，則左孩子結(jié)點(diǎn)的編號為（ ）。A. 2i B. 2i-1 C. 2i+1 D. 2i+2標(biāo)準(zhǔn)答案：A2.在一棵樹中，每個結(jié)點(diǎn)最多有（ ）個前驅(qū)結(jié)點(diǎn)。A. 0 B. 1 C. 2 D. 任意多個標(biāo)準(zhǔn)答案：B3.在一棵具有n個結(jié)點(diǎn)的二叉樹的第i層上，最多具有（ ）個結(jié)點(diǎn)。A. 2 i B. 2 i-1 C. 2 i-1 D. 2 n標(biāo)準(zhǔn)答案：C4.在一棵具有35個結(jié)點(diǎn)的完全二叉樹中，該樹的深度為（ ）。 A. 6 B. 7 C. 5 D. 8標(biāo)準(zhǔn)答案：A5.在一棵具有n個結(jié)點(diǎn)的完全二叉樹中，樹枝結(jié)點(diǎn)的最大編號是（

37、）。A. (n+1)/2 B. (n-1)/2 C. n/2-1 D. n/2標(biāo)準(zhǔn)答案：D6.在一棵二叉樹的二叉鏈表中，空指針域數(shù)等于非空指針域數(shù)加（ ）。 A. 2 B. 1 C. 0 D. -1標(biāo)準(zhǔn)答案：A7.在一棵完全二叉樹中，對于編號為i(i1)的結(jié)點(diǎn)，其雙親結(jié)點(diǎn)的編號為（ ）。A. (i+1)/2 B. (i-1)/2 C. i/2 -1 D. i/2標(biāo)準(zhǔn)答案：B、D8.一棵二叉樹的廣義表表示為a(b(c),d(e(,g(h),f)，則該二叉樹的高度為（ ）。A. 3 B. 4 C. 5 D. 6標(biāo)準(zhǔn)答案：C9.一棵樹的廣義表表示為a(b(c),d(e,f(g(h,i),j)，該樹的

38、深度為（ ）。A. 3 B. 4 C. 5 D. 6標(biāo)準(zhǔn)答案：C10.在一棵深度為h的完全二叉樹中，所含結(jié)點(diǎn)個數(shù)不大于（ ）。A. 2 h B. 2 h+1 C. 2 h -1 D. 2 h-1標(biāo)準(zhǔn)答案：C11.樹中所有結(jié)點(diǎn)的度等于所有結(jié)點(diǎn)數(shù)加（ ）。A. 0 B. 1 C. 1 D. 2標(biāo)準(zhǔn)答案：C12.一棵二叉樹的廣義表表示為a(b(c),d(e(,g(h),f)，則該二叉樹所含的單分支結(jié)點(diǎn)數(shù)為（ ）。A. 2 B. 3 C. 4 D. 5標(biāo)準(zhǔn)答案：B13.在一棵完全二叉樹中，若編號為i（1in）的結(jié)點(diǎn)存在右孩子，則右孩子結(jié)點(diǎn)的編號為（ ）。A. 2i B. 2i-1 C. 2i+1 D.

39、 2i+2標(biāo)準(zhǔn)答案：C14.在一棵深度為h的完全二叉樹中，所含結(jié)點(diǎn)個數(shù)不小于（ ）。A. 2 h B. 2 h+1 C. 2 h -1 D. 2 h-1標(biāo)準(zhǔn)答案：D15.對于一棵具有30個結(jié)點(diǎn)的三叉樹，則其最小深度為（ ）。A. 3 B. 4 C. 5 D. 6標(biāo)準(zhǔn)答案：B16.對于一棵深度為4的三叉樹，最多具有（ ）個結(jié)點(diǎn)。A. 30 B. 36 C. 40 D. 54標(biāo)準(zhǔn)答案：C17.在一棵二叉樹中，葉子結(jié)點(diǎn)數(shù)等于雙分支結(jié)點(diǎn)數(shù)加（ ）。A. 0 B. 1 C. 1 D. 2標(biāo)準(zhǔn)答案：B二、填空題（共有題目12題） 1.對于一棵具有n個結(jié)點(diǎn)的樹，則樹中所有結(jié)點(diǎn)的度數(shù)之和為n-1。2.對于一棵

40、含有40個結(jié)點(diǎn)的理想平衡樹，它的高度為6_。3.在一棵二叉樹中，第5層上的結(jié)點(diǎn)數(shù)最多有16個。4.一棵高度為3的四叉樹中，最多含有21_結(jié)點(diǎn)。5.在一棵二叉樹中，若雙分支結(jié)點(diǎn)數(shù)為5個，單分支結(jié)點(diǎn)數(shù)為6個，則葉子結(jié)點(diǎn)數(shù)為6個。6.一棵三叉樹的結(jié)點(diǎn)個數(shù)為50，則它的最小深度為5，最大深度為50。7.在一棵高度為5的理想平衡樹中，最少含有16個結(jié)點(diǎn)，最多含有31個結(jié)點(diǎn)。8.一棵樹的廣義表表示為A(B(C,D(E,F,G),H(I,J)，則結(jié)點(diǎn)H的雙親結(jié)點(diǎn)是B，孩子結(jié)點(diǎn)有I、J。9.一棵二叉樹順序存儲在一維數(shù)組a中，則ai（1in）元素的左孩子元素為a2i，右孩子元素為a2i+1。10.已知一棵二叉樹

41、的先根和中根序列如下：先根序列：A，B，C，D，E，F(xiàn)，G，H，I，J中根序列：C，B，A，E，F(xiàn)，D，I，H，J，G則其后根序列為C B F E I J H G D A。11.在一棵三叉樹中，度為3的結(jié)點(diǎn)數(shù)有2個，度為2的結(jié)點(diǎn)數(shù)有1個，度為1的結(jié)點(diǎn)數(shù)有2個，則度為0的結(jié)點(diǎn)數(shù)有6個。12.一棵深度為5的滿二叉樹中的結(jié)點(diǎn)數(shù)為31個。 第6章 二叉樹的應(yīng)用一、單選題（共有題目10題） 1.對二叉搜索樹進(jìn)行中序遍歷得到的結(jié)點(diǎn)序列一定是一個有序序列。對2.利用n個值作為葉子結(jié)點(diǎn)的權(quán)生成的哈夫曼樹中共包含（ ）結(jié)點(diǎn)。A. n B. n+1 C. 2n D. 2n-1標(biāo)準(zhǔn)答案：D3.有四個帶權(quán)葉子結(jié)點(diǎn)，其

42、權(quán)值分別為2、4、5、9，則由其構(gòu)成的哈夫曼樹的帶權(quán)路徑長度是（ ）。A. 50 B. 40 C. 37 D. 20標(biāo)準(zhǔn)答案：C4.向二叉搜索樹中插入一個元素時，其時間復(fù)雜度大致為（ ）。A. O（1） B. O（Log2n) C. O(n) D. O(nLog2n)標(biāo)準(zhǔn)答案：B5.從二叉搜索樹中查找一個元素時，其時間復(fù)雜度大致為( )。A. O(n) B. O(1) C. O(Log2n) D. O(n2)標(biāo)準(zhǔn)答案：C6.根據(jù)n個元素建立一棵二叉搜索樹時，其時間復(fù)雜度大致為（ ）。A. O（n) B. O(Log2n) C. O(n2) D. O(nLog2n)標(biāo)準(zhǔn)答案：D7.利用n個值作為

43、葉子結(jié)點(diǎn)的權(quán)生成的哈夫曼樹中共包含（ ）個雙分支結(jié)點(diǎn)。A. n B. n-1 C. n+1 D. 2n-1標(biāo)準(zhǔn)答案：B8.從堆中刪除一個元素的時間復(fù)雜度為（ ）。A. O(1) B. O(n) C. O(Log2n) D. O(nLog2n)標(biāo)準(zhǔn)答案：C9.利用3、6、8、12為4個值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹，該樹中所有葉子的最短帶權(quán)路徑長度為（ ）。A. 18 B. 16 C. 12 D. 30標(biāo)準(zhǔn)答案：A10.向堆中插入一個元素的時間復(fù)雜度是（ ）。A. O(1) B. O(Log2n) C. O(n) D. O(nLog2n)標(biāo)準(zhǔn)答案：B二、填空題（共有題目18題） 1.堆的存

44、儲結(jié)構(gòu)適宜采用順序存儲，這樣能夠充分利用存儲空間。2.若有兩棵樹T 1和T 2均為小根堆，當(dāng)以它們作為一棵樹T的左、右子樹，并用一個比這兩棵子樹的根都小的值作為整個樹T的根結(jié)點(diǎn)，則樹T是一個堆;小根堆。3.在一棵非空的二叉搜索樹中，以每個分支結(jié)點(diǎn)為根的子樹都是一棵二叉搜索樹。4.有7個帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為3、7、8、2、6、10、14，若依它們?yōu)槿~子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹，給出其廣義表，并計(jì)算出其帶權(quán)路徑長度WPL134。5.堆是一棵完全二叉樹。6.在一棵樹中，結(jié)點(diǎn)的帶權(quán)路徑長度規(guī)定為從樹根結(jié)點(diǎn)到該結(jié)點(diǎn)之間的路徑長度與該結(jié)點(diǎn)上權(quán)的乘積。7.在一棵二叉搜索樹中，其左子樹上結(jié)點(diǎn)的關(guān)鍵字值小于根結(jié)點(diǎn)

45、的關(guān)鍵字值。8.在一棵樹中，兩個結(jié)點(diǎn)之間如果有路徑的話，路徑的個數(shù)是唯一的。9.在一棵二叉搜索樹中查找一個元素時，若元素的值等于根結(jié)點(diǎn)的值，則表明查找成功；若元素的值小于根結(jié)點(diǎn)的值，則繼續(xù)向左子樹查找；若元素的值大于根結(jié)點(diǎn)的值，則繼續(xù)向右子樹查找。10.當(dāng)向一個小根堆插入一個具有最小值的元素時，該元素需要逐層向上調(diào)整，直到被調(diào)整到堆頂位置為止。11.當(dāng)從一個小根堆中刪除一個元素時，需要把堆尾元素填補(bǔ)到堆頂位置，然后再按條件把它逐層向下調(diào)整。12.二叉搜索樹又名二叉排序樹。13.在一個堆中，除編號為0的堆頂結(jié)點(diǎn)外，對于其他編號為i的結(jié)點(diǎn)，其雙親結(jié)點(diǎn)的編號為。14.在一個堆的順序存儲結(jié)構(gòu)中，堆中結(jié)

46、點(diǎn)的編號是從0開始的，若一個元素的下標(biāo)為i，則它的左孩子元素的下標(biāo)是2i+1，右孩子元素的下標(biāo)是2i+2。15.在一個小根堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的最小值；在一個大根堆中，堆頂結(jié)點(diǎn)的值是所有結(jié)點(diǎn)中的最大值。16.在任何一棵哈夫曼樹中，單支結(jié)點(diǎn)的個數(shù)為0。17.對一棵二叉搜索樹進(jìn)行中序遍歷時，得到的結(jié)點(diǎn)序列是一個有序序列。18.不管一棵哈夫曼樹中有偶數(shù)或奇數(shù)個葉子結(jié)點(diǎn)，則樹中總結(jié)點(diǎn)的個數(shù)必為奇數(shù)個。第7章 圖一、單選題（共有題目18題） 1.對于一個具有n個頂點(diǎn)的無向連通圖，它包含的連通分量的個數(shù)為（ ）。A. 0 B. 1 C. n D. n-1標(biāo)準(zhǔn)答案：B2.已知一個無向圖的邊集為(0

47、,1)3,(0,2)4,(0,3)8,(1,4)10,(2,3)2, (2,4)12,(3,4)8，則利用普里姆算法從頂點(diǎn)0出發(fā)求其最小生成樹的過程中，得到的第條邊是（）。A. (0,1)3 B. (0,2)4 C. (2,3)2 D. (3,4)5標(biāo)準(zhǔn)答案：C3.在一個具有n個頂點(diǎn)和e條邊的無向圖的鄰接表中，邊結(jié)點(diǎn)的個數(shù)為（ ）。 A. n B. e C. n*e D. 2e標(biāo)準(zhǔn)答案：D4.若要把n個頂點(diǎn)連接為一個連通圖，則至少需要（）條邊。A. n B. n+1 C. n-1 D. 2n標(biāo)準(zhǔn)答案：C5.由一個具有n個頂點(diǎn)的連通圖生成的最小生成樹中，具有（）條邊。A. n B. n-1 C. n+1 D. 2n標(biāo)準(zhǔn)答案：B6.若一個圖中包含有k個連通分量，若要按照深度優(yōu)先搜索的方法訪問所有頂