數(shù)據(jù)結(jié)構(gòu)與算法1-5單元練習(xí)題及答案

1、 單元練習(xí)1 判斷題(下列各題，正確的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打V;錯(cuò)誤的打X) (V) (1)數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)。 (V) (2) 一個(gè)數(shù)據(jù)結(jié)構(gòu)是由一個(gè)邏輯結(jié)構(gòu)和這個(gè)邏輯結(jié)構(gòu)上的一個(gè)基本運(yùn)算集構(gòu)成的整體。 (X) ( 3 )數(shù)據(jù)元素是數(shù)據(jù)的最小單位。 (X) (4)數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是相同的。 (X) ( 5)程序和算法原則上沒(méi)有區(qū)別，所以在討論數(shù)據(jù)結(jié)構(gòu)時(shí)可以通用。 (V) (6 )從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。 (V) ( 7)數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲(chǔ)映像。 (V) ( 8)數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)實(shí)際的存儲(chǔ)形式

2、。 (X) ( 9)數(shù)據(jù)的邏輯結(jié)構(gòu)是依賴于計(jì)算機(jī)的。 (V) (10)算法是對(duì)解題方法和步驟的描述。 數(shù)據(jù)有邏輯結(jié)構(gòu)和 存儲(chǔ)結(jié)構(gòu)兩種結(jié)構(gòu)。 (1) (2) (3) (4) (5) (6) 二填空題 數(shù)據(jù)邏輯結(jié)構(gòu)除了集合以外，還包括：線性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖形結(jié)構(gòu) 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們是線性結(jié)構(gòu)和非線性結(jié)構(gòu) 在樹(shù)形結(jié)構(gòu)中，除了樹(shù)根結(jié)點(diǎn)以外，其余每個(gè)結(jié)點(diǎn)只有 1個(gè)前趨結(jié)點(diǎn)。 樹(shù)形結(jié)構(gòu)和 圖形結(jié)構(gòu)合稱為非線性結(jié)構(gòu)。 在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前趨結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè) (7) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)又叫物理結(jié)構(gòu) (8) 數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)形式包括：順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列存儲(chǔ) (9

3、) 線性結(jié)構(gòu)中的元素之間存在一對(duì)一的關(guān)系。 (10) 樹(shù)形結(jié)構(gòu)結(jié)構(gòu)中的元素之間存在一對(duì)多的關(guān)系, (11) 圖形結(jié)構(gòu)的元素之間存在多對(duì)多 的關(guān)系。 (12) 數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和算法(或運(yùn)算)三個(gè)方面的內(nèi)容。 (13) 數(shù)據(jù)結(jié)構(gòu)被定義為(D，R)，其中D是數(shù)據(jù)的有限集合，R是D上的 關(guān)系的有限集合。 (14) 算法是一個(gè)有窮指令的集合。 (15) 算法效率的度量可以分為事先估算法和事后統(tǒng)計(jì)法。 (16) 一個(gè)算法的時(shí)間復(fù)雜性是算法輸入規(guī)模的函數(shù)。 (17) 算法的空間復(fù)雜度是指該算法所耗費(fèi)的存儲(chǔ)空間，它是該算法求解問(wèn)題規(guī)模n的函數(shù)。 (18) 若一個(gè)算法中的語(yǔ)句頻度之和為

4、T(n)=6n+3nlog 2n，則算法的時(shí)間復(fù)雜度為0 (nlog 2n)。 (19) 若一個(gè)算法中的語(yǔ)句頻度之和為T(n)=3n+nlog 2n+n2，則算法的時(shí)間復(fù)雜度為 0 (n2)。 (20) 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的操作對(duì)象，以及它們之間的關(guān)系和 運(yùn)算的學(xué)科。 三選擇題 (1)數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的( A )及它們之間的相互聯(lián)系。 A. 存儲(chǔ)結(jié)構(gòu)和邏輯結(jié)構(gòu)B.存儲(chǔ)和抽象 C.聯(lián)系和抽象D.聯(lián)系與邏輯 (2)在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成：(C )。 A. 動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B.緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C.線性結(jié)構(gòu)和非線性結(jié)構(gòu)D.內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu) (3 )數(shù)

5、據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址和邏輯地址相同并且是連續(xù)的，稱之為(C )。 A.存儲(chǔ)結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.順序存儲(chǔ)結(jié)構(gòu)D.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) (4)非線性結(jié)構(gòu)中的每個(gè)結(jié)點(diǎn)( D )。 A. 無(wú)直接前趨結(jié)點(diǎn) B. 無(wú)直接后繼結(jié)點(diǎn) C. 只有一個(gè)直接前趨結(jié)點(diǎn)和一個(gè)直接后繼結(jié)點(diǎn) D. 可能有多個(gè)直接前趨結(jié)點(diǎn)和多個(gè)直接后繼結(jié)點(diǎn) (5)鏈?zhǔn)酱鎯?chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間( A )。 A.順序存儲(chǔ) B. 鏈?zhǔn)酱鎯?chǔ) C. 索引存儲(chǔ) D. 散列存儲(chǔ) A 分兩部分，一部分存放結(jié)點(diǎn)的值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針 B 只有一部分，存放結(jié)點(diǎn)的值 C 只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針 D 分兩部分，一部分存放結(jié)點(diǎn)的

6、值，另一部分存放結(jié)點(diǎn)所占單元素 (6)算法的計(jì)算量大小稱為算法的(C )。 A.現(xiàn)實(shí)性 B. 難度 C.時(shí)間復(fù)雜性 D.效率 (7) 數(shù)據(jù)的基本單位是( B )。 A.數(shù)據(jù)結(jié)構(gòu) B. 數(shù)據(jù)兀素 C.數(shù)據(jù)項(xiàng) D.文件 (8)每個(gè)結(jié)點(diǎn)只含有一個(gè)數(shù)據(jù)元素， 所有存儲(chǔ)結(jié)點(diǎn)相繼存放在一個(gè)連續(xù)的存儲(chǔ)區(qū)里，這種存儲(chǔ)結(jié)構(gòu)稱為(A ) 結(jié)構(gòu)。 A.順序 B.鏈?zhǔn)?C. 索引 D.散列 (10)以下任何兩個(gè)結(jié)點(diǎn)之間都沒(méi)有邏輯關(guān)系的是( D )。 A.圖形結(jié)構(gòu) B.線性結(jié)構(gòu) C. 樹(shù)形結(jié)構(gòu) D. 集合 (11)在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是( C )。 A.物理結(jié)構(gòu) B.存儲(chǔ)結(jié)構(gòu) C. 邏輯結(jié)構(gòu) D. 邏輯

7、和存儲(chǔ)結(jié)構(gòu) (12)下列四種基本邏輯結(jié)構(gòu)中，數(shù)據(jù)兀素之間關(guān)系最弱的是( A ) 。 A.集合 B.線性結(jié)構(gòu) C. 樹(shù)形結(jié)構(gòu) D. 圖形結(jié)構(gòu) (13)與數(shù)據(jù)元素本身的形式、 內(nèi)容、相對(duì)位置、個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的( A )。 A.邏輯結(jié)構(gòu) B.存儲(chǔ)結(jié)構(gòu) C. 邏輯實(shí)現(xiàn) D. 存儲(chǔ)實(shí)現(xiàn) (14)每一個(gè)存儲(chǔ)結(jié)點(diǎn)只含有 個(gè)數(shù)據(jù)兀素，存儲(chǔ)結(jié)點(diǎn)存放在連續(xù)的存儲(chǔ)空間， 另外有 組指明結(jié)點(diǎn)存儲(chǔ)位置 的表，該存儲(chǔ)方式是(C )存儲(chǔ)方式。 A.順序 B.鏈?zhǔn)?C. 索引 D. 散列 (15)算法能正確的實(shí)現(xiàn)預(yù)定功能的特性稱為算法的 ( A )。 A.正確性 B.易讀性 C. 健壯性 D. 咼效性 (16)算法在發(fā)生非

8、法操作時(shí)可以作出處理的特性稱為算法的( C ) 。 A.正確性 B.易讀性 C. 健壯性 D. 咼效性 (17)下列時(shí)間復(fù)雜度中最壞的是(D )。 A. O (1) B. O ( n) C. O (log2n) D. O (n2) (9)每一個(gè)存儲(chǔ)結(jié)點(diǎn)不僅含有一個(gè)數(shù)據(jù)元素，還包含一組指針，該存儲(chǔ)方式是( B )存儲(chǔ)方式。 (18)下列算法的時(shí)間復(fù)雜度是( D )。 for (i=0;i n;i+) for (j=0;i n;j+) cij=i+j； A. O (1)B. O ( n) (19) 算法分析的兩個(gè)主要方面是( A )。 A.空間復(fù)雜性和時(shí)間復(fù)雜性 C.可讀性和文檔性 (20) 計(jì)算

9、機(jī)算法必須具備輸入、輸出和( A.計(jì)算方法 C.解決問(wèn)題的有限運(yùn)算步驟 四分析下面各程序段的時(shí)間復(fù)雜度 2 C. O (log2n)D. O (n ) B.正確性和簡(jiǎn)明性 D. 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 C )。 B.排序方法 D.程序設(shè)計(jì)方法 (1) for (i=0;i n;i+) for (j=0;jm;j+) Aij 解：0( n*m) (2)s=0; for (i=0;i n;i+) for (j=0;j n;j+) s+=Bij; sum=s; 解：0( n2) (3) T=A; A=B; B=T; 解：0(1) (4) s1(i nt n) int p=1,s=0; for (i=

10、1;i=n ;i+) p*=i;s+=p; return(s); O(n) (5) s2(i nt n) x=0; y=0; for (k=1;k=n; k+) x+; for (i=1;i=n ;i+) for (j=1;j=n ;j+) y+; 解：O(n2) 五.根據(jù)二元組關(guān)系，畫出對(duì)應(yīng)邏輯圖形的草圖，指出它們屬于何種數(shù)據(jù)結(jié)構(gòu) 1 . A=( D，R)，其中： D=a，b，c，d，e， R= 解： a O b O c de O 0O 屬于集合 2. B= (D， R)， 其中： D=a，b，c，d，e，f，R=r R=，(尖括號(hào)表示結(jié)點(diǎn)之間關(guān)系是有向的) 解： 屬于線性結(jié)構(gòu)。 3 根據(jù)二

11、元組關(guān)系畫出邏輯圖形，并指出它們屬于何種數(shù)據(jù)結(jié)構(gòu)。 F= (D，R)，其中： D=50 ， 25， 64， 57， 82， 36， 75， 55， R=, , 解: 根據(jù)二元組關(guān)系畫出邏輯圖形，并指出它們屬于何種數(shù)據(jù)結(jié)構(gòu)。 C= ( D，R)，其中： D=1，2，3，4, 5, 6， R= ( 1,2) , (2,3) , (2,4) , (3,4) , (3,5) , (3,6) , (4,5) , (4,6) (園括號(hào)表示結(jié)點(diǎn)之間關(guān)系是有向的) 解: 屬于圖結(jié)構(gòu) 5 根據(jù)二元組關(guān)系畫出邏輯圖形，并指出它們屬于何種數(shù)據(jù)結(jié)構(gòu)。 E=( D，R),其中： D=a，b，c, d, e, f，g，h

12、， R=d,b，d,g，d,a，b,c，g,e，g,h，e,f 解： 屬于樹(shù)結(jié)構(gòu)。 模擬考題 1 根據(jù)二元組關(guān)系畫出邏輯圖形，并指出它們屬于何種數(shù)據(jù)結(jié)構(gòu)。 A= ( D , R),其中： D=1 , 2, 3, 4, 5, 6, R= (1,2) , (1,6) , ( 2,3) , ( 2,4), 2 根據(jù)二元組關(guān)系畫出邏輯圖形，并指出它們屬于何種數(shù)據(jù)結(jié)構(gòu)。 B= (D , R),其中： D=40 , 30 , 20 , 60 , 50 , 80 , 70 , 10, R=, , 解: 30 20 40 屬于樹(shù)結(jié)構(gòu) 60 50 10 80 70 3.根據(jù)二元組關(guān)系畫出邏輯圖形，并指出它們屬于

13、何種數(shù)據(jù)結(jié)構(gòu)。 C=( D，R),其中: D=1，2，3，4, 5, 6， R=（ 1,2）,（2,3） ,（ 2,4） ,（ 3,4） （3,5）,（ 3,6）,（ 4,5）,（ 4,6） 解: 屬于圖結(jié)構(gòu) 4 .根據(jù)二元組關(guān)系畫出邏輯圖形，并指出它們屬于何種數(shù)據(jù)結(jié)構(gòu)。 E= (D, R),其中： D=a , b, c, d, e, f, g, h, R=, , 解: 屬于樹(shù)結(jié)構(gòu) 單元練習(xí)2 一判斷題(下列各題，正確的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打V;錯(cuò)誤的打 X ) (X) (1)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)。 (X) (2)鏈表的每個(gè)結(jié)點(diǎn)都恰好包含一個(gè)指針域。 (V) (3)在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)

14、構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定緊鄰。 (X) (4)順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，插入、刪除效率高。 (X) (5)線性鏈表的刪除算法簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)的各個(gè)單元向前移 動(dòng)。 (X) (6)順序表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。 (V) ( 7)線性表鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是可以用一組任意的存儲(chǔ)單元存儲(chǔ)表中的數(shù)據(jù)元素。 (V) ( 8)線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。 (X) (9)順序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。 (X) (10)插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最基本的兩種操作，所

15、以這兩種操作在數(shù)組中也經(jīng)常使用。 二填空題 (1) 順序表中邏輯上相鄰的元素在物理位置上必須 相連。 (2) 線性表中結(jié)點(diǎn)的集合是有限的，結(jié)點(diǎn)間的關(guān)系是一對(duì)一 關(guān)系。 (3) 順序表相對(duì)于鏈表的優(yōu)點(diǎn)是：節(jié)省存儲(chǔ)和隨機(jī)存取。 (4) 鏈表相對(duì)于順序表的優(yōu)點(diǎn)是：插入、刪除方便。 (5) 采用 順序存儲(chǔ)結(jié)構(gòu)的線性表叫順序表。 (6) 順序表中訪問(wèn)任意一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度均為0(1)。 (7) 鏈表相對(duì)于順序表的優(yōu)點(diǎn)是插入、刪除方便；缺點(diǎn)是存儲(chǔ)密度小 。 (8) 在雙鏈表中要?jiǎng)h除已知結(jié)點(diǎn) *P，其時(shí)間復(fù)雜度為0(1)。 (9) 在單鏈表中要在已知結(jié)點(diǎn) *P之前插入一個(gè)新結(jié)點(diǎn)， 需找到*P的直接前趨結(jié)點(diǎn)

16、的地址，其查找的時(shí)間復(fù) 雜度為 0( n) 。 (10) 單鏈表中需知道 頭指針才能遍歷整個(gè)鏈表。 (11) 性表中第一個(gè)結(jié)點(diǎn)沒(méi)有直接前趨，稱為開(kāi)始 結(jié)點(diǎn)。 (12) 在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素，要移動(dòng)n-i個(gè)元素。 (13) 在一個(gè)長(zhǎng)度為n的順序表中，如果要在第i個(gè)元素前插入一個(gè)元素，要后移 n-i +1 個(gè)元素。 (14) 在無(wú)頭結(jié)點(diǎn)的單鏈表中，第一個(gè)結(jié)點(diǎn)的地址存放在頭指針中，而其它結(jié)點(diǎn)的存儲(chǔ)地址存放在前 結(jié) 點(diǎn)的指針域中。 (15) 當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快速度存取線性表中的元素 時(shí)，應(yīng)采用 順序存儲(chǔ)結(jié)構(gòu)。 (16) 在線性表的鏈?zhǔn)酱?/p>

17、儲(chǔ)中，元素之間的邏輯關(guān)系是通過(guò)指針 決定的。 (17) 在雙向鏈表中，每個(gè)結(jié)點(diǎn)都有兩個(gè)指針域，它們一個(gè)指向其前趨 結(jié)點(diǎn)，另一個(gè)指向其 _后繼結(jié) 點(diǎn)。 (18) 對(duì)一個(gè)需要經(jīng)常進(jìn)行插入和刪除操作的線性表，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)為宜。 (19) 雙鏈表中，設(shè)p是指向其中待刪除的結(jié)點(diǎn)，則需要執(zhí)行的操作為：p-prior- next=p- next。 (20) 在如圖所示的鏈表中，若在指針 P所在的結(jié)點(diǎn)之后插入數(shù)據(jù)域值為a和b的兩個(gè)結(jié)點(diǎn)，則可用 下列兩個(gè) 語(yǔ)句：S-next-next=P-next;和P-next=S; 來(lái) 實(shí)現(xiàn)該 操作。 三.選擇題 (1)在具有n個(gè)結(jié)點(diǎn)的單鏈表中，實(shí)現(xiàn)( )的操作，其算法

18、的時(shí)間復(fù)雜度都是 O (n)。 A .遍歷鏈表或求鏈表的第i個(gè)結(jié)點(diǎn) B .在地址為P的結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn) D 刪除地址為P的結(jié)點(diǎn)的后繼結(jié)點(diǎn) C.刪除開(kāi)始結(jié)點(diǎn) (2) 設(shè)a、b、c為三個(gè)結(jié)點(diǎn)，p、10、20分別代表它們的地址，則如下的存儲(chǔ)結(jié)構(gòu)稱為( 10 20 A.循環(huán)鏈表 B .單鏈表 C .雙向循環(huán)鏈表 D.雙向鏈表 (3) 單鏈表的存儲(chǔ)密度( C )o A .大于1B .等于1 C .小于1 D.不能確定 (4)已知一個(gè)順序存儲(chǔ)的線性表，設(shè)每個(gè)結(jié)點(diǎn)占 地址為(A ) o m個(gè)存儲(chǔ)單元, 若第一個(gè)結(jié)點(diǎn)的地址為B,則第 i個(gè)結(jié)點(diǎn)的 B . B+i*m C. B-i*m A.B+(i-1)*m

19、 (5) 在有n個(gè)結(jié)點(diǎn)的順序表上做插入、刪除結(jié)點(diǎn)運(yùn)算的時(shí)間復(fù)雜度為 A. 0( 1)B. 0( n)C. O (n2) (6) 設(shè)Llink、Rlink分別為循環(huán)雙鏈表結(jié)點(diǎn)的左指針和右指針， .B+(i+1)*m .O (log 2n) 則指針P所指的元素是雙循環(huán)鏈表 L的尾元 素的條件是(D )。 A. P= LB . P-Llink= L (7) 兩個(gè)指針P和Q,分別指向單鏈表的兩個(gè)元素, A. P-next=Q-next B . P-next= Q P= NULL D .P-Rl in k=L P所指元素是 Q所指兀素前驅(qū)的條件是( B ) Q_n ext= P D .P= Q C. C

20、. (8) 用鏈表存儲(chǔ)的線性表，其優(yōu)點(diǎn)是( C A.便于隨機(jī)存取 C.便于插入和刪除 (9) 在單鏈表中，增加頭結(jié)點(diǎn)的目的是(C A .使單鏈表至少有一個(gè)結(jié)點(diǎn) C.方便運(yùn)算的實(shí)現(xiàn) (10) 下面關(guān)于線性表的敘述中，錯(cuò)誤的是( A .順序表必須占一片地址連續(xù)的存儲(chǔ)單元 C.鏈表不必占用一片地址連續(xù)的存儲(chǔ)單元 )。 B .花費(fèi)的存儲(chǔ)空間比順序表少 D .數(shù)據(jù)元素的物理順序與邏輯順序相同 ) B .標(biāo)志表中首結(jié)點(diǎn)的位置 D .說(shuō)明該單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) D )關(guān)系。 B .順序表可以隨機(jī)存取任- 元素 D .鏈表可以隨機(jī)存取任- 元素 (11) L是線性表, 已知LengthList ( L

21、)的值是 5,經(jīng) DelList (L, 2)運(yùn)算后, LengthList ( L)的值是( C ) A . 2B. 3C. 4D. 5 (12) 單鏈表的示意圖如下： L 指向鏈表Q結(jié)點(diǎn)的前趨的指針是( B ) A. LB . PC . QD. R (13) 設(shè)p為指向單循環(huán)鏈表上某結(jié)點(diǎn)的指針，則*p的直接前驅(qū)( C ) A.找不到 B.查找時(shí)間復(fù)雜度為 0( 1) C.查找時(shí)間復(fù)雜度為O(n) D .查找結(jié)點(diǎn)的次數(shù)約為 n (14) 等概率情況下，在有 n個(gè)結(jié)點(diǎn)的順序表上做插入結(jié)點(diǎn)運(yùn)算，需平均移動(dòng)結(jié)點(diǎn)的數(shù)目為(C ) A. nB . (n-1)/2C. n/2D. (n+1)/2 (15

22、) 在下列鏈表中不能從當(dāng)前結(jié)點(diǎn)出發(fā)訪問(wèn)到其余各結(jié)點(diǎn)的是(C ) A.雙向鏈表B .單循環(huán)鏈表C .單鏈表D .雙向循環(huán)鏈表 (16) 在順序表中，只要知道( D ),就可以求出任一結(jié)點(diǎn)的存儲(chǔ)地址。 .向量大小 D A ) .O(n2)D .基地址和結(jié)點(diǎn)大小 .O (log 2n) A.基地址B.結(jié)點(diǎn)大小C (17) 在雙鏈表中做插入運(yùn)算的時(shí)間復(fù)雜度為( A. O (1)B . O (n)C (18) 鏈表不具備的特點(diǎn)是( A ) A .隨機(jī)訪問(wèn) C.插入刪除時(shí)不需移動(dòng)元素 B .不必事先估計(jì)存儲(chǔ)空間 D .所需空間與線性表成正比 A 線性表中的元素可以是數(shù)字、字符、記錄等不同類型 B .線性順

23、序表中包含的元素個(gè)數(shù)不是任意的 C .線性表中的每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)直接前趨和一個(gè)直接后繼 D .存在這樣的線性表，即表中沒(méi)有任何結(jié)點(diǎn) (20)在(B )的運(yùn)算中，使用順序表比鏈表好。 A .插入B .根據(jù)序號(hào)查找C.刪除D .根據(jù)元素查找 四.程序填空 1. 已知線性表中的元素是無(wú)序的，并以帶表頭結(jié)點(diǎn)的單鏈表作存儲(chǔ)。試寫一算法，刪除表中所有大于min , 小于max的元素，試完成下列程序填空。 Void delete (Iklist head; datatype min, max) q=head-n ext; while (p!=NULL) if(p-datadata=max ) q=p;

24、 p= p- next ; else q_n ext=p_n ext ; delete (p); p= q_next ; 2. 在帶頭結(jié)點(diǎn)head的單鏈表的結(jié)點(diǎn)a之后插入新元素x，試完成下列程序填空。 struct node elemtype data; node *n ext; ; void lk in sert (node *head, elemtype x) node *s, * p; s= new node; s-data= x; p=head-n ext; while (p!=NULL) if (p=NULL) coutnext=p-next p-n ext=s 模擬考題 1 .在順

25、序存儲(chǔ)的線性表第 i個(gè)位置插入新結(jié)點(diǎn) x,試兀成下列程序填空。 typedef struct/ datatype dataMAXLEN;/ MAXLEN int last; SeqList; int In sList(SeqList *L,i nt i,datatype x) int j; if (L-last= =MAXLEN-1) 將data和last圭寸裝在一個(gè)結(jié)構(gòu)體 為線性表的最大長(zhǎng)度 cout 順序表已滿！ ;return(-1); if( iL-last+2 ) / coutlast; j=i-1; j- -)/ L-dataj+1=L-dataj L-Latai-1= =x; /

26、 L-last +; / 插入結(jié)點(diǎn)函數(shù) 檢查插入位置的正確性 結(jié)點(diǎn)移動(dòng) 新結(jié)點(diǎn)插入 (或 L-last= L-last +1 ) return(1); 2 一個(gè)帶頭指針的單鏈表，寫出在值為x的結(jié)點(diǎn)之后插入 m個(gè)結(jié)點(diǎn)的算法。 void in sertm (lklist head; int m) p=head-n ext; while (p!=NULL) if ( p-data=x ) q=p-n ext; for ( i=0; im ; i+ )/找到x,在其后插入 m個(gè)結(jié)點(diǎn) s=new (no de); cindata=a ; p_n ext=s; p=s; p_n ext=q; 3.有兩個(gè)循

27、環(huán)單鏈表，頭指針?lè)謩e為headl和head2,下列函數(shù)是將鏈表 headl鏈接到鏈表head2，鏈接后 的鏈表仍然是循環(huán)鏈表，試完成下列程序填空。 (提示：先找到兩鏈表的尾指針，再將第一個(gè)鏈表的尾指針與第二個(gè)鏈表的頭結(jié)點(diǎn)鏈接起來(lái)) node *link (node *head1, node *head2) node *p, *q; p=head1; while (p-n ext!=head1) p= p_next ; q= head2 ; while (q-n ext!=head2 ) q=q_n ext; p-n ext=head2; q-n ext=head1; return (head1

28、); 單元練習(xí)3 判斷題(下列各題，正確的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打V;錯(cuò)誤的打X ) (V) (1)棧是運(yùn)算受限制的線 性表。 (V) (2)在?？盏那?況下，不 能作出 棧操作，否則產(chǎn) 生下溢 出。 (X) (3)棧一定是順序存儲(chǔ)的線性結(jié)構(gòu)。 (V) (4)棧的特點(diǎn)是 “后進(jìn)先 出”。 (X) ( 5)空棧就是所有元素都為0的棧。 (X) (6)在C或C+語(yǔ)言中設(shè)順序棧的長(zhǎng)度為MAXLEN，則top=MAXLEN 時(shí)表示隊(duì)滿。 (V) (7)鏈棧與順序 棧相比， 其特點(diǎn) 之一是 通常不會(huì) 出現(xiàn)棧 滿的情 況。 (X) ( 8)一個(gè)棧的輸入序列為：A，B，C，D，可以得到輸出序列：C，A，B，D。

29、(X) ( 9)遞歸定義就 是循環(huán)定 義。 (V) (10 )將十進(jìn)制 數(shù)轉(zhuǎn)換為二 進(jìn)制數(shù) 是棧的 典型應(yīng)用 之一。 二.填空題 (1 )在 棧結(jié)構(gòu) 中，允 許插入、刪除的一端稱 為 棧頂 。 (2 )在順序棧中，當(dāng)棧頂指針top =-1時(shí)，表示 ?？?。 (3) 在 有n個(gè)元 素的棧 中，進(jìn)棧 操作的 時(shí)間復(fù) 雜度為 0(1)。 (4) 在棧中，出棧操作的時(shí)間 復(fù)雜度為： O(1)。 (5) 已知表達(dá)式，求它的后綴表達(dá)式是棧 的典型應(yīng)用。 (6) 在一個(gè)鏈棧中，若棧頂指針等于NULL，則表示 棧空。 (7) 向一個(gè)棧頂指針為top的鏈棧插入一個(gè)新結(jié)點(diǎn)*p時(shí)，應(yīng)執(zhí)行p-next=top :和t

30、op=p ; 操 作。 (8) 順序棧S存儲(chǔ)在數(shù)組 S-data0.MAXLEN-1中，進(jìn)棧操作時(shí)要執(zhí)行的語(yǔ)句有: S-top +。(或=S- top+1) (9) 鏈棧LS，指向棧頂元素的指針是LS-next。 (10) 從一個(gè)棧刪除元素時(shí)，首先取出棧頂元素，然后再移動(dòng)棧頂指針。 (11) 由于鏈棧的操作只在鏈表的頭部進(jìn)行，所以沒(méi)有必要設(shè)置頭結(jié)點(diǎn)。 (12) 已知順序棧S,在對(duì)S進(jìn)行進(jìn)棧操作之前首先要判斷棧是否滿。 (13) 已知順序棧S,在對(duì)S進(jìn)行出棧操作之前首先要判斷棧是否空。 (14) 若內(nèi)存空間充足，鏈?？梢圆欢x棧滿運(yùn)算。 (15 )鏈棧LS是空的條件是LS-next=NULL。

31、(16 )鏈棧LS的棧頂元素是鏈表的首 元素。 (17 )同一棧的各元素的類型相同 (18)若進(jìn)棧的次序是 A、B、C、D、E,執(zhí)行三次出棧操作以后，棧頂元素為_(kāi)B (19) A+B/C-D*E 的后綴表達(dá)式是：ABC/+DE*- (20 )四 個(gè)元素 按A、B、C、D順序進(jìn)S棧，執(zhí) 行兩次Pop( S，x )運(yùn) 算后，x的值是 C 三選擇題 H A B C D A (1 )插 入和刪 除只能 在一端進(jìn) 行的線 性表，稱為(C )。 A . 隊(duì)列B . 循環(huán)隊(duì)列 C .棧D .循環(huán)棧 (2) 設(shè)有編號(hào)為1 , 2, 3, 4的四輛列車，順序進(jìn)入一 個(gè)棧結(jié)構(gòu)的站臺(tái)，下列不可能的出站順 序?yàn)?(D

32、 ) A .1234B . 1243 C . 1324D .1423 (3) 如果以鏈表作為 棧的存儲(chǔ) 結(jié)構(gòu)，則出棧操作時(shí)( B ) A .必須判別棧是 否滿 B .必須判別棧是 否空 C .必須判別棧元 素類型 D .隊(duì)?？刹蛔鋈魏闻袆e (4) 元素A,B,C,D依次進(jìn)棧以后 ，棧頂兀素是 (D ) A .AB .B C . C D . D (5) 順序棧存儲(chǔ)空間 的實(shí)現(xiàn)使 用(B)存儲(chǔ)棧元素 橐。 A .鏈表B .數(shù)組 C .循環(huán)鏈表 D.變量 (6) 在C或 C+語(yǔ)言中 ，一個(gè)順 序棧一旦被聲明，其占 用空間的大小 (A )。 A .已固定B .不固定 C .可以改變 D.動(dòng)態(tài)變化 (7

33、) 帶頭結(jié)點(diǎn)的鏈棧 LS的示意 圖如下，棧頂 兀素是( A ) LS (8)鏈 棧與順 序棧相 比，有一 個(gè)比較 明顯的 優(yōu)點(diǎn)是( B ) A.插入 操作更 加方便B 通常 不會(huì)出現(xiàn)棧 滿的情 況。 C.不會(huì) 出現(xiàn)棧 空的情 況D .刪除 操作根加方 便 (9)從一個(gè) 棧頂指 針為top的鏈 棧中刪 除一個(gè) 結(jié)點(diǎn)時(shí)，用x保存被 刪除的結(jié)點(diǎn)，應(yīng)執(zhí) 行下列(D ) 命令。 x=top;top=top-n ext; B. top=top-next;x=top-data; (10) x=top-data;D. x=top-data;top=top-next; 在一個(gè)棧頂指針為HS的鏈棧中，將一個(gè)S指針

34、所指的結(jié)點(diǎn)入棧，應(yīng)執(zhí)行下列(B ) HS-next=S;B. S-next=HS-next;HS-next=S; 命令。 (11 ) S- next=HS- next;HS=S; 四個(gè)元素按A、B、C D順序進(jìn)S棧，執(zhí)行兩次 D. S-next=HS;HS=HS-next; Pop ( S, x)運(yùn)算后 ，棧頂元素的值是( B )。 B. B C. C D. D (12) 元素A,B,C,D依次進(jìn)棧以 后，棧底元素是( A )。 B. B C. C D. (13) 經(jīng)過(guò)下列 In itStack(s) 棧的運(yùn)算后，再 (初始化棧) 執(zhí)行ReadTop(s)的值是 ( )。 A. a B. b

35、;Push(s,a);Push(s,b); Pop(s) C. 1 D. (14 )經(jīng)過(guò)下列 In itStack(s) A. a 棧的運(yùn)算后，x的值是 (B (初始化棧)；Push(s,a);Push(s,b); ReadTop(s);Pop(s,x); C. 1 B. b )。 D. 0 (15 )經(jīng)過(guò)下列 In itStack(s) A. a (16 )經(jīng)過(guò)下列 In itStack(s) A. a 棧的運(yùn)算后，x的值是(B (初始化棧)；Push(s,a);Pop(s,x);Push(s,b);Pop(s,x); B. bC. 1 棧的運(yùn)算后，SEmpty(s)的值是(C )。 (初始

36、化棧) )。 D. 0 B. b ;Push(s,a); Push(s,b);Pop(s,x); Pop(s,x); C. 1D. 0 中壓入元素時(shí), 素，后移動(dòng)棧 (17 )向順序棧 A.先存入元 C.誰(shuí)先誰(shuí)后無(wú)關(guān)緊要 (B 頂指針 (18) 初始化一 個(gè)空間大小為 5的順序 B . -1 )。 B .先移動(dòng)棧頂指針, D .同時(shí)進(jìn)行 棧 S后，S-top C .不再改變 的值是( 后存入 兀素 )。 D.動(dòng)態(tài)變化 (19) 個(gè)棧的 入棧次序ABCDE則棧 的不可能的輸出 序列是 EDCBA B . DECBA DCEAB (C )。 .ABCDE 設(shè)有一個(gè)順序棧S,元素A,B,C,D,E,

37、F, (20) A,則棧 的容量至少應(yīng)是(A )。 依次進(jìn)棧 ，如果六個(gè)元素出棧的順序是B, D, C, F, E, A . 3B . 4C . 四.設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)椋?作，寫出下列出棧的操作序列。 A, B, C, D .6 D, E,用I表示進(jìn)棧操作， O表示出棧操 (1 )C,B,A,D,E (2)A,C,B,E,D 解：(1) 1110001010 (2) I0II00II00 五求后綴表達(dá)式 (1) AABAC/D (2) -A+B*C+D/E (3) A*(B+C)*D-E (4) (A+B)*C-E/(F+G/H)-D (5) 8/(5+2)-6 解: (1) A B

38、 A C A D / (2) 0 A B C * + D E / + (3) A B C + * d * E - (4) A B + C * E F G H / + / - D (5) 8 5 2 + / 6 - 模擬考題 求后綴表達(dá)式 1 .求下列表達(dá)式：A/B卜 C+D*E-A*C的后綴表達(dá)式。 解： A B C 人 / D E * + A C * - 2 .求下列表達(dá)式：A/B-C+D*E-F 的后綴表達(dá)式。 解： A B/ C - D E * +F - 寫出運(yùn)行下列程序段的輸出結(jié)果 void mai n() Stack S; char x,y; Ini tStack(S);/初始化棧

39、x= c ; y= k ; Push(S,x); Push(S, a ); Push(S,y); Pop(S,x); Push(S, t ); Push(S,x); Pop(S,x); Push(S, s ); While (!SEmpty(S) Pop(S,y);couty; ; coutx; 答：stack 程序填空 1.下列程序是判別一個(gè)算術(shù)表達(dá)式(存在字符數(shù)組 int correct(char a) stack s ; In itStack(s); for (i=0; istrle n( a); i+) if (ai=() Push ( s,(); else if (ai=) if S

40、Empty (s) return 0; else Pop(s); if (SEmpty(s) cout 配對(duì)正確！ ”; a中) / / 的圓括號(hào)配對(duì)是否正確？試填空完成下列程序。 初始化棧 若棧為空返回0;否則出棧 / printf (” 配對(duì)正確！ ”); else coutfront-next= NULL 設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)頭指針， 設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)鏈表表示，若只設(shè)尾指針， 則入隊(duì)操作的時(shí)間復(fù)雜度為 O ( n )。 則出隊(duì)操作的時(shí)間復(fù)雜度為 (13 ) (14 ) (15 ) 在一個(gè)鏈隊(duì)列中，若隊(duì)首指針與隊(duì)尾指針的值相同，則表示該隊(duì)列為 設(shè)循環(huán)隊(duì)列的頭

41、指針 front指向隊(duì)首元素，尾指針rear指向隊(duì)尾元素后的一個(gè)空閑元素，隊(duì)列 的最大空間為 MAXLEN則隊(duì)滿標(biāo)志為： 在一個(gè)鏈隊(duì)列中，若隊(duì)首指針為 為： fron t=rear OutQueue(Q,x); ReadFront(Q,x);QEmpty(Q);后的值是 _0 (20)隊(duì)列 Q經(jīng)過(guò) InitQueue(Q)(初始化隊(duì)列);lnQueue(Q,a);lnQueue(Q,b); ReadFront(Q,x) 三選擇題 （1 ）隊(duì)列是限定在（ D ）進(jìn)行操作的線性表。 A . 中間 B . 隊(duì)首 C .隊(duì)尾 D . 端點(diǎn) (2) 隊(duì)列中的 兀素個(gè) 數(shù)是 (B )。 A . 不變的 B

42、 . 可變的 C .任意的 D . 0 (3) 同一隊(duì)列 內(nèi)各元 素的類型（A ）。 A . 必須一致 B . 不能一致 C .可以不一 致D . 不限制 (4) 隊(duì)列是一 個(gè)（C ） 線性表結(jié)構(gòu) 。 A . 不加限制的 B . 推廣了的 C .力口 了限制 的D . 非 (5) 當(dāng)利用大小為 n 的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)， 該隊(duì)列的最后 一個(gè)兀素的下標(biāo)為（ A . n-2 B . n-1 C .n D .n+1 (6) 一個(gè)循環(huán) 隊(duì)列一 旦說(shuō)明，其占用 空間的 大?。ˋ ）。 A . 已固定 B. 可以變動(dòng) C .不能固定 D . 動(dòng)態(tài)變 );ln Queue(Q,a); 后，x的值是 ）。

43、 化 (13)隊(duì)列Q,經(jīng)過(guò)下列運(yùn)算后， InitQueue(Q)(初始化隊(duì)列 A. C. 0 D. 1 (14) 循環(huán)隊(duì)列SQ隊(duì)滿的條件是 SQ-rear=SQ-fro nt B . (SQ-rear+1)% MAXLEN =SQ-front C. SQ-rear=0 (15 )設(shè)鏈棧中結(jié)點(diǎn)的結(jié)構(gòu)：data為數(shù)據(jù)域, 插入一個(gè)由指針s所指的結(jié)點(diǎn)，則應(yīng)執(zhí)行下列( A . s-next=top-next ;top-next=s C . s-next=top ； top=top-next； (16 )帶頭結(jié)點(diǎn)的鏈隊(duì)列LQ示意圖如下 n ext 為指針域，且 A )操作。 B . top-n ext=

44、s D . s-n ext=top .SQ-front=O top是棧頂指針。若想在鏈棧的棧頂 ；top=s ，鏈隊(duì)列的隊(duì)頭元素是 LQ-fro nt LQ-rear A. AB . BC . CD. D (17 )帶頭結(jié)點(diǎn)的鏈隊(duì)列LQ示意圖如下，指向鏈隊(duì)列的 隊(duì)頭指針是(C ) (7)循環(huán)隊(duì)列占用的空 間(A )。 A . 必須連續(xù) B . 不必連續(xù) C .不能連續(xù)D .可以不 連續(xù) (8)存放循環(huán)隊(duì)列兀素 的數(shù)組 data有10個(gè)兀素 ，則 data 數(shù)組的下標(biāo)范圍是( B ) o A . 0.10 B . 0.9 C . 1.9 D . 1.10 (9): 若進(jìn)隊(duì)的序列為： A, B,

45、C, D,則出隊(duì)的序列是( C)o A . B, C, D, A B .A, G B, D C . A, B, C, D D .C, B, D, A (10 ) 四個(gè)兀素按： A, B, C, D順序連續(xù)進(jìn)隊(duì) Q,則隊(duì)尾兀素是(D)o A . A B . B C . C D . D (11 ) 四個(gè)兀素按：A, 1 B C, D順序連續(xù)進(jìn)隊(duì)Q, 執(zhí)行一次 OutQueue(Q)操作后， 隊(duì)頭兀素是 A . A B. B C . C D . D (12) 四個(gè)兀素按： A, B, C, D順序連續(xù)進(jìn)隊(duì) Q,執(zhí)行 四次OutQueue(Q)操作后，再執(zhí) 后的值是(B)。 A . 0 B. 1 C

46、.2 D.3 )。 行 QEmpty(Q); (B x的值是(B );ln Queue(Q,a); I nQueue(Q,b);OutQueue(Q,x); ReadFro nt (Q,x); LQ-fro nt A. LQ-front B. LQ-rear C. LQ-front-nextD. LQ-rear-next (18 )帶頭結(jié)點(diǎn)的鏈隊(duì)列LQ示意圖如下，在進(jìn)行進(jìn)隊(duì)運(yùn)算時(shí)指針LQ-front ( A ) LQ-fro nt LQ-rear A.始終不改變 B .有時(shí)改變 C .進(jìn)隊(duì)時(shí)改變D .出隊(duì)時(shí)改變 (19) 隊(duì)列Q經(jīng)過(guò)下列運(yùn)算后，再執(zhí)行 QEmpty(Q)的值是(C )。 Ini

47、tQueue(Q)(初始化隊(duì)列);lnQueue(Q,a); InQueue(Q,b);OutQueue(Q,x); ReadQueue(Q,x); A. aB . bC. 0D . 1 (20) 若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前 front和rear的值分別為3和0,當(dāng)從隊(duì)列中刪除 個(gè)元素， 再加入 兩個(gè)元 素后，front和rear的值分別為(c )。 A . 5 和 1B . 4 和 2C . 2 和 4D. 1 和 5 四.寫出程序運(yùn)行的結(jié)果 寫出下列程序段的輸出結(jié)果(隊(duì)列中的元素類型為char)。 void mai n() Queue Q; InitQueue (Q);

48、初始化隊(duì)列 char x=E; y=C; In Queue (Q, H); In Queue (Q, R); In Queue (Q, y); OutQueue (Q,x); I nQueue (Q,x); OutQueue (Q,x); InQueue (Q, A); while (!QEmpty(Q) OutQueue (Q,y); prin tf(y); ; prin tf(x); 答：輸出為“ CHAR。 單元練習(xí)5 判斷題(下列各題，正確的請(qǐng)?jiān)谇懊娴睦ㄌ?hào)內(nèi)打V;錯(cuò)誤的打X ) (乂)(1)串是n個(gè)字母的有限序列。 (V) (2)串的數(shù)據(jù)元素是一個(gè)字符。 (X) (3 )串的長(zhǎng)度是指串

49、中不同字符的個(gè)數(shù)。 (X) (4)如果兩個(gè)串含有相同的字符，則說(shuō)明它們相等。 (X) (5)如果一個(gè)串中所有的字母均在另一個(gè)串中出現(xiàn)，則說(shuō)明前者是后者的子串。 (V) (6)串的堆分配存儲(chǔ)是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)。 (X) ( 7) “DT ”是“ DATA ”的子串。 (X) ( 8)串中任意個(gè)字符組成的子序列稱為該串的子串。 (V) (9)子串的定位運(yùn)算稱為模式匹配。 (V) (10)在鏈串中為了提高存儲(chǔ)密度，應(yīng)該增大結(jié)點(diǎn)的大小。 二填空題 (1) 由零個(gè)或多個(gè)字符組成的有限序列稱為 字符串(或串) 。 (2) 字符串按存儲(chǔ)方式可以分為：順序存儲(chǔ)、鏈接存儲(chǔ)和堆分配存儲(chǔ) (3) 串的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)

50、稱為 順序串 。 (4) 串順序存儲(chǔ)非緊湊格式的缺點(diǎn)是： 空間利用率低 。 (5) 串順序存儲(chǔ)緊湊格式的缺點(diǎn)是對(duì)串的字符處理 效率低 。 (6) 串鏈接存儲(chǔ)的優(yōu)點(diǎn)是插入、刪除方便，缺點(diǎn)的 空間利用率低 (7) 在C或C+語(yǔ)言中，以字符0 表示串值的終結(jié)。 (8) 空格串的長(zhǎng)度等于空格的個(gè)數(shù) 。 (9) 在空串和空格串中，長(zhǎng)度不為0的是 空格串 。 (10 )兩個(gè)串相等是指兩個(gè)串相長(zhǎng)度等，且對(duì)應(yīng)位置的字符都相同 (11 )設(shè) S=My Music，貝U LenStr(s)= _ 8。 的結(jié)果 (12 )兩個(gè)字符串分別為：S仁Today is ，S2=30 July,2005,ConcatStr(

51、S1,S2) 是:Today is 30 July,2005。 (13 )求子 串函數(shù) SubStr(Today is 30 July,2005,13,4)的結(jié)果是：July (14 )在 串的運(yùn)算中，EqualStr(aaa,aab) 的返 回值為 m，則模式匹配算法最壞情況下的時(shí)間復(fù)雜度為: (n-m+1)*m。 三選擇題 (1)串是一種特殊的線性表，其特殊性體現(xiàn)在(B ) A . 20 % B .40 % C . 50 %D .33 . 3 % (9)若字符串 ABCDEFG采用鏈?zhǔn)酱鎯?chǔ)， 假設(shè)每個(gè)指針占用 2個(gè)字節(jié)，若希望存儲(chǔ)密度 個(gè)結(jié)點(diǎn)應(yīng)存儲(chǔ) (A ) 個(gè)字符。 A . 2 B .3

52、 C . 4 D . 5 (10 ) 設(shè)串S1 =I AM ,S2=A SDUDENT, 則 ConcatStr(S1,S2)=(B ) o A . I AM B . I AM A SDUDENT (8 )若字符串ABCDEFG采用鏈?zhǔn)酱鎯?chǔ)，假設(shè)每個(gè)字符占用 字符串的存儲(chǔ)密度為(D) o 1個(gè)字節(jié)，每個(gè)指針占用2個(gè)字節(jié)。則該 50 %，則每 A.可以順序存儲(chǔ)B.數(shù)據(jù)元素是一個(gè)字符 C.可以鏈接存儲(chǔ)D.數(shù)據(jù)元素可以是多個(gè)字符 (2) 某串的長(zhǎng)度小于一個(gè)常數(shù)，則采用(B )存儲(chǔ)方式最節(jié)省空間。 A .鏈?zhǔn)?B .順序C .堆結(jié)構(gòu)D.無(wú)法確定 (3) 以下論述正確的是(C ) o A .空串與空格串

53、是相同的 B . tel是Teleptone 的子串 C .空串是零個(gè)字符的串 D. 空串的長(zhǎng)度等于1 (4) 以下論述正確的是(B ) o A .空串與空格串是相同的 B . ton是Teleptone 的子串 C .空格串是有空格的串 D. 空串的長(zhǎng)度等于1 (5) 以下論斷正確的是(A)o A . 是空串，”空格串 B . BEIJING是BEI JING的子串 C . somethi ngSomethig D . BIT=BITE (6) 設(shè)有 兩個(gè)串S1和S2 ,則EqualStr(S1,S2) 運(yùn)算稱作(D )o A. 串連接 B. 模式匹配 C. .求子串 D. 串比較 (7)串

54、的模式匹配是指( D )o A. 判斷兩個(gè)串是否相等C.找某字符在主串中第一次出現(xiàn)的位置 B. 對(duì)兩個(gè)串比較大小D.找某子串在主串中第一次出現(xiàn)的第一個(gè)字符位置 C . IAMASDUDENT D. A SDUDENT (11 )設(shè) S=,則 LenStr (S): =(A )。 A. 0B . 1 C . 2D .3 (12 )設(shè)目標(biāo)串T=AABBCCDDE,模式P=ABCDE,則該模式匹配的有效位移為( A ) o A. 0 B . 1C . 2 D. 3 (13 )設(shè) 目標(biāo)串 T=AABBCCDDEEFF,模式 P=CCD, ) 則該模式匹配的有效位移為(D A. 2 B. 3 C. 4

55、D. 5 (14 )設(shè)目標(biāo)串 T=aabaababaabaa ，模式 P=abab, 樸素匹配算法的外層循環(huán)進(jìn)行了 ( D )次。 A. 1 B. 9 C. 4 D. 5 (15 )樸素模式匹配算法在最壞情況下的時(shí)間復(fù)雜度是 A . 0( m)B . 0( n)C . 0 ( m+n) S=morning,執(zhí)行求子 串函數(shù) SubStr(S,2,2) (16 ) D . 0 ( m*n) 后的結(jié)果為( A. mo B . or C. in (17 ) S1=good , S2=morning D. ng ,執(zhí) 行串連 接函數(shù)ConcatStr(S1,S2) II: 后的結(jié)果為( A. good

56、morni ng B. good morning C. GOODMORNING D. GOOD MORNING (18 ) S1=good , S2=morning ,執(zhí)行函數(shù) SubStr(S2,4,LenStr(S1) 后的結(jié)果為( A. good B. ning C. D. morn go 設(shè)串 S仁ABCDEFG , S2=PQRST, 則 ConcatStr(SubStr(S1,2,LenStr(S2),SubStr(S1 ,LenStr(S2),2) (19 ) 的結(jié)果串為( A. BCDEFB. BCDEFGC. BCPQRST (20)若串S=SOFTWARE,其子串的數(shù)目最多

57、是：( D. BCDEFEF ) A . 35 B. 36 C (8+7+6+5+4+3+2+1+仁37) .37 .38 其他 假設(shè)在樹(shù)中， 結(jié)點(diǎn)x是結(jié)點(diǎn)y的雙親時(shí)， (e,i), (b,e), (b,d), (a,b), (g,j), (c,g), (c,f), (h,l), (c,h), (a,c) 法表示該樹(shù)，并回答下列問(wèn)題： 用(x,y) 來(lái)表示樹(shù)邊。已知一棵樹(shù)的樹(shù)邊集合為 ,用樹(shù)型表示 哪個(gè)是根結(jié)點(diǎn)？哪些是葉子結(jié)點(diǎn)？哪個(gè)是g的雙親？哪些是g的祖先？哪些是g的孩 子？那些是e的子孫？哪些是e的兄弟？哪些是f的兄弟？ b和n的層次各是多少？樹(shù)的深度是多少？以結(jié)點(diǎn)c為根的子樹(shù)的深度是多少

58、？ 一棵深度為h的滿k叉樹(shù)有如下性質(zhì)： 第h層上的結(jié)點(diǎn)都是葉子結(jié)點(diǎn)，其余各層上每個(gè)結(jié) 點(diǎn)都有k棵非空子樹(shù)。 如果按層次順序(同層自左至右)從1開(kāi)始對(duì)全部結(jié)點(diǎn)編號(hào)，問(wèn)： 各層的結(jié)點(diǎn)數(shù)是多少？ 編號(hào)為i的結(jié)點(diǎn)的雙親結(jié)點(diǎn)(若存在)的編號(hào)是多少？ 編號(hào)為i的結(jié)點(diǎn)的第j個(gè)孩子結(jié)點(diǎn)(若存在)的編號(hào)是多少？ 編號(hào)為i的結(jié)點(diǎn)的有右兄弟的條件是什么？其右兄弟的編號(hào)是多少？ 設(shè)有如圖6-27所示的二叉樹(shù)。 分別用順序存儲(chǔ)方法和鏈接存儲(chǔ)方法畫出該二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)。 寫出該二叉樹(shù)的先序、中序、后序遍歷序列。 已知一棵二叉樹(shù)的先序遍歷序列和中序遍歷序列分別為ABDGHCEFI和GDHBAECIF,請(qǐng)畫出這棵 二叉樹(shù)，然后給出該樹(shù)的后序遍歷序列。 圖心17二叉樹(shù) 設(shè)圖6-27所示的二叉樹(shù)是森林F所對(duì)應(yīng)的二叉樹(shù)，請(qǐng)畫出森林F。 設(shè)有一棵樹(shù)，如圖6-28所示。 請(qǐng)分別用雙親表示法、孩子表示法、孩