數(shù)據(jù)結(jié)構(gòu)期末考試(題集)

1、數(shù)據(jù)結(jié)構(gòu)的基本概念選擇題（1） 順序存儲(chǔ)結(jié)構(gòu)中數(shù)據(jù)元素之間的邏輯關(guān)系是由（）表示的，鏈接存儲(chǔ)結(jié)構(gòu)中的數(shù)據(jù)元素之間的邏輯關(guān)系是由（ ）表示的。A.線性結(jié)構(gòu)B.非線性結(jié)構(gòu)C.存儲(chǔ)位置D .指針（2） 假設(shè)有如下遺產(chǎn)繼承規(guī)則： 丈夫和妻子可以相互繼承遺產(chǎn)，子女可以繼承父親或母親的遺產(chǎn)；子女間不能相互繼承， 則表示該遺產(chǎn)繼承關(guān)系的最合適的數(shù)據(jù)結(jié)構(gòu) 應(yīng)該是（）。A.樹B.圖C.線性表D.集合（3） 計(jì)算機(jī)所處理的數(shù)據(jù)一般具有某種內(nèi)在聯(lián)系，這是指（）。A.數(shù)據(jù)和數(shù)據(jù)之間存在某種關(guān)系B.元素和元素之間存在某種關(guān)系C.元素內(nèi)部具有某種結(jié)構(gòu)D.數(shù)據(jù)項(xiàng)和數(shù)據(jù)項(xiàng)之間存在某種關(guān)系（4） 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)

2、無關(guān)的是數(shù)據(jù)的（）。A.樹B.圖C.線性表 D.集合（5） 在存儲(chǔ)數(shù)據(jù)時(shí)，通常不僅要存儲(chǔ)各數(shù)據(jù)元素的值，還要存儲(chǔ)（）。A.數(shù)據(jù)的處理方法B.數(shù)據(jù)元素的類型C.數(shù)據(jù)元素之間的關(guān)系D.數(shù)據(jù)的存儲(chǔ)方法（6） 在鏈接存儲(chǔ)結(jié)構(gòu)中，要求（ A.每個(gè)結(jié)點(diǎn)占用一片連續(xù)的存儲(chǔ)區(qū)域C.結(jié)點(diǎn)的最后一個(gè)域是指針類型（7） 下列說法不正確的是（）。A.數(shù)據(jù)元素是數(shù)據(jù)的基本單位C.數(shù)據(jù)可由若干個(gè)數(shù)據(jù)項(xiàng)構(gòu)成）。B.所有結(jié)點(diǎn)占用一片連續(xù)的存儲(chǔ)區(qū)域D.每個(gè)結(jié)點(diǎn)有多少個(gè)后繼就設(shè)多少個(gè)指針B.數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小單位D.數(shù)據(jù)元素可由若干個(gè)數(shù)據(jù)項(xiàng)構(gòu)成歡迎下載（8） 以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無關(guān)的術(shù)語(yǔ)是（）。A.循環(huán)隊(duì)列B.鏈表C

3、.散列表D.棧（9） 以下術(shù)語(yǔ)屬于邏輯結(jié)構(gòu)的是（）。A.順序表B.哈希表C.有序表D.單鏈表（10） 可以用（）定義一個(gè)完整的數(shù)據(jù)結(jié)構(gòu)。D.抽象數(shù)據(jù)類型A.數(shù)據(jù)元素B.數(shù)據(jù)對(duì)象C.數(shù)據(jù)關(guān)系（11） 對(duì)于數(shù)據(jù)結(jié)構(gòu)的描述，下列說法中不正確的是（）。A .相同的邏輯結(jié)構(gòu)對(duì)應(yīng)的存儲(chǔ)結(jié)構(gòu)也必相同B.數(shù)據(jù)結(jié)構(gòu)由邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和基本操作三方面組成C.數(shù)據(jù)結(jié)構(gòu)基本操作的實(shí)現(xiàn)與存儲(chǔ)結(jié)構(gòu)有關(guān)D.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的機(jī)內(nèi)實(shí)現(xiàn)(12) 以下關(guān)于鏈接存儲(chǔ)結(jié)構(gòu)的敘述中，()是不正確的。A.結(jié)點(diǎn)除數(shù)據(jù)信息外還包括指針域，因此存儲(chǔ)密度小于順序存儲(chǔ)結(jié)構(gòu)B.邏輯上相鄰的結(jié)點(diǎn)物理上不一定相鄰C.可以通過計(jì)算得到第i

4、個(gè)結(jié)點(diǎn)的存儲(chǔ)地址D.插入和刪除操作方便，不必移動(dòng)結(jié)點(diǎn)(13) 可以用()、數(shù)據(jù)關(guān)系和基本操作定義一個(gè)完整的抽象數(shù)據(jù)類型。A.數(shù)據(jù)元素B.數(shù)據(jù)對(duì)象C.原子類型D.存儲(chǔ)結(jié)構(gòu)應(yīng)用題(14) 設(shè)有數(shù)據(jù)結(jié)構(gòu)(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)圖并指出屬 于何種結(jié)構(gòu)。(15) 試描述數(shù)據(jù)結(jié)構(gòu)和抽象數(shù)據(jù)類型的概念與程序設(shè)計(jì)語(yǔ)言中數(shù)據(jù)類型概念的區(qū)另I。(16) 說明數(shù)據(jù)的邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)之間的關(guān)系。(17) 抽象數(shù)據(jù)類型的主要特點(diǎn)是什么？

5、數(shù)據(jù)類型和抽象數(shù)據(jù)類型的關(guān)系如何？使用抽象數(shù)據(jù)類型的主要好處是什么？1算法和算法分析選擇題（1）算法指的是（）。A.對(duì)特定問題求解步驟的一種描述，是指令的有限序列B.計(jì)算機(jī)程序C.解決問題的計(jì)算方法D.數(shù)據(jù)處理（2）下面（）不是算法所必須具備的特性。A.有窮性 B.確切性（3）算法必須具備輸入、輸出和（A.可行性、可移植性和可擴(kuò)充性C.確定性、穩(wěn)定性和有窮性C.高效性 D.可行性）等特性。B.可行性、確定性和有窮性D.易讀性、穩(wěn)定性和健壯性（4）算法應(yīng)該具有確定性、可行性和有窮性，其中有窮性是指（）。A.算法在有窮的時(shí)間內(nèi)終止B.輸入是有窮的C.輸出是有窮的D .描述步驟是有窮的（5）當(dāng)輸入非

6、法錯(cuò)誤時(shí)， 一個(gè)“好”的算法會(huì)進(jìn)行適當(dāng)處理，而不會(huì)產(chǎn)生難以理解的輸出結(jié)果，這稱為算法的（）。A.可讀性 B.健壯性C.正確性 D,有窮性（6） 算法分析的目的是（A.找出數(shù)據(jù)結(jié)構(gòu)的合理性C.分析算法的效率以求改進(jìn)E.空間性能和時(shí)間性能G.可讀性和文檔性（7） 算法的時(shí)間復(fù)雜度與（A.問題規(guī)模C.編譯程序的質(zhì)量）,算法分析的兩個(gè)主要方面是（）。B.研究算法中輸入和輸出的關(guān)系D.分析算法的易讀性和文檔性F.正確性和簡(jiǎn)明性H.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性）有關(guān)。B.計(jì)算機(jī)硬件性能D.程序設(shè)計(jì)語(yǔ)言（8）算法的時(shí)間復(fù)雜度與（A.問題規(guī)模C.算法的易讀性）有關(guān)。B.待處理數(shù)據(jù)的初態(tài)D. A 和 B（9）某算法的

7、時(shí)間復(fù)雜度是。（n2）,表明該算法（ ）。A.問題規(guī)模是n2B.執(zhí)行時(shí)間等于n2C.執(zhí)行時(shí)間與n2成正比D.問題規(guī)模與n2成正比（10）下面說法錯(cuò)誤的是（ ）。算法原地工作的含義是指示不需要如何額外的輔助空間在相同的規(guī)模n下，復(fù)雜度。(n)的算法在時(shí)間上總是優(yōu)于復(fù)雜度。(2n)的算法所謂時(shí)間復(fù)雜度是指最壞情況下，估算算法執(zhí)行時(shí)間的一個(gè)上界同一個(gè)算法，實(shí)現(xiàn)語(yǔ)言的級(jí)別越高，執(zhí)行效率就越低(11) 算法for (i=n-1; i>=1; i-)for (j=1; j<=i; j+)if (aj>aj+1) aj與 aj+1交換；其中n為正整數(shù)，則最后一行語(yǔ)句的頻度(執(zhí)行次數(shù))在最壞

8、情況下是()。A . O (n)B. O (nlog2n)C. O (n3)D. O (n2)(12) 算法的時(shí)間復(fù)雜度屬于一種()。A.事前統(tǒng)計(jì)的方法B.事先分析估算的方法C.事后統(tǒng)計(jì)的方法D.事后分析估算的方法(13) 設(shè)某算法完成對(duì)n個(gè)元素進(jìn)行處理，所需的時(shí)間是T(n)=100 nlog 2n+200n+500 ,則該算法的時(shí)間復(fù)雜度是()。A. O (1)B . O (n)C. O(nlog2n) D. O (nlog2n+n)(14) 假設(shè)時(shí)間復(fù)雜度為。(n2)的算法在有200個(gè)元素的數(shù)組上運(yùn)行需要3.1ms,則在有400個(gè)元素的數(shù)組上運(yùn)行需要() ms。A. 3.1B. 6.2C.

9、 12.4D. x (無法確定)(15) 下列程序段加下劃線的語(yǔ)句執(zhí)行()、次。for (m=0,i=1; i<=1; i+)for (j=1; j<=2*i; j+)m=m+1 ;A. n2B. 3nC. n(n+1)D, n3應(yīng)用題(16) 將下列函數(shù)按它們的n-8時(shí)的無窮大階數(shù)，從小到大排列。n, n-n3-7n5, nlog2n, 2n/2, n3, log2n, n1/2+log2n, (3/2)n, n!, n2+log2n(17) 分析以下程序段，并用大。記號(hào)表示其執(zhí)行時(shí)間。 i=1;k=0;while (i<n-1)k=k+10*i; i+; i=1;j=0;

10、while (i+j<=n)if (i>j) j+;else i+; for (i=1;i<=n;i+)for (j=1;j<=i;j+)for (k=1;k<=j;k+)x+; i=1;k=0;dok=k+10*i;i+； while (i<=n) y=0;while (y+1)*(y+1)<=n)y=y+1 for (i=0;i<n;i+)for (j=0；j<m；j+)a皿=0；(18) 有實(shí)現(xiàn)同一功能的兩個(gè)算法 A1和A2,其中A1的時(shí)間復(fù)雜度為 Ti=O(2n), A2的時(shí)間復(fù)雜度為T2=O(n2),僅就時(shí)間復(fù)雜度而言，請(qǐng)具體分析

11、這兩個(gè)算法哪一 個(gè)好。綜合應(yīng)用題(19) 設(shè)n是偶數(shù)，且有程序段：for (i=1;i<=n;i+)if (2*i<=n)for (j=2*I;j<=n;j+)y=y+i*j;則語(yǔ)句y=y+i*j的執(zhí)行次數(shù)是多少？要求列出計(jì)算公式。(20) 斐波那契數(shù)列Fn定義如下：F0=0, F1=1 ,，F(xiàn)n=Fn-1+Fn-2n=2, 3,請(qǐng)就此斐波那契數(shù)列，回答下列問題。 在遞歸計(jì)算Fn的時(shí)候，需要對(duì)較小的Fn-1, Fn-2,，F(xiàn)1 , Fo精確計(jì)算多少次？ 用大。表示法給出遞歸計(jì)算時(shí)遞歸函數(shù)的時(shí)間復(fù)雜度是多少？(21) 運(yùn)算是數(shù)據(jù)結(jié)構(gòu)的一個(gè)重要方面。舉例說明兩個(gè)數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)

12、和存儲(chǔ)方式完全相同，只是對(duì)于運(yùn)算的定義不同，因而具有不同的特性，則這兩個(gè)數(shù)據(jù)結(jié)構(gòu)是不同的。(22) 針對(duì)給定的實(shí)際問題建立數(shù)據(jù)結(jié)構(gòu)時(shí)，應(yīng)從哪些方面考慮。2線性表的邏輯結(jié)構(gòu)選擇題)的有限序列。C.數(shù)據(jù)元素D.數(shù)據(jù)項(xiàng)(1) 線性表是具有n個(gè)(A.數(shù)據(jù)B.字符(2) 線性表是(A. 一個(gè)有限序列，可以為空C. 一個(gè)無限序列，可以為空B. 一個(gè)有限序列，不能為空D. 一個(gè)無限序列，不能為空(3) 關(guān)于線性表，下列說法中正確的是()。A.線性表中每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B.線性表中的數(shù)據(jù)元素可以具有不同的數(shù)據(jù)類型C.線性表中數(shù)據(jù)元素的類型是確定的D.線性表中任意一對(duì)相鄰的數(shù)據(jù)元素之間存在序

13、偶關(guān)系(4) ()是一個(gè)線性表。B.由所有實(shí)數(shù)組成的集合D.由n個(gè)字符組成的序列A.由n個(gè)實(shí)數(shù)組成的集合C.由所有整數(shù)組成的序列3順序線性表選擇題(1) 已知一維數(shù)組 A采用順序存儲(chǔ)結(jié)構(gòu)，每個(gè)元素占用 4個(gè)存儲(chǔ)單元，第9個(gè)元素的地址為144,則第一個(gè)元素的地址是()。A. 108B. 180C. 176D. 112x的數(shù)據(jù)元素的時(shí)間復(fù)雜度為(C. O(n)D.O(n2)(2) 在長(zhǎng)度為n的線性表中查找值為A. 0(0)B. 0(1)(3) 在一個(gè)長(zhǎng)度為 n的線性表的第i (1Wi wn+1)個(gè)元素之前插入一個(gè)元素，需向后移動(dòng)()個(gè)元素，刪除第i (1wi wn)個(gè)元素時(shí)，需向前移動(dòng)()個(gè)A.

14、n-iB. n-i+1C. n-iD. n-i+1(4)線性表的順序存儲(chǔ)結(jié)構(gòu)是一種()的存儲(chǔ)結(jié)構(gòu)。A.隨機(jī)存取 B.順序存取C.索引存取D,散列存取(5)順序存儲(chǔ)結(jié)構(gòu)的優(yōu)點(diǎn)是(A.存儲(chǔ)密度大C.刪除運(yùn)算方便)。B.插入運(yùn)算方便D.可方便地用于各種邏輯結(jié)構(gòu)的存儲(chǔ)表示(6) n個(gè)結(jié)點(diǎn)的線性表采用數(shù)組實(shí)現(xiàn)，算法的時(shí)間復(fù)雜度是。(1)的操作是()。A.訪問第i個(gè)結(jié)點(diǎn)(1Wi wn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)(2Wi wn)B.在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)(1 w i w n)C.刪除第i個(gè)結(jié)點(diǎn)(1Wi wn)D.以上都不對(duì)(7) 對(duì)于順序存儲(chǔ)的線性表，訪問某個(gè)元素和增加一個(gè)元素的時(shí)間復(fù)雜度為()。A.。

15、、O(n) B. O(n)、0(1) C.。(1)、O (n) D.。(1)、0(1)(8) 順序表的插入算法中，當(dāng) n個(gè)空間已滿時(shí)，可再申請(qǐng)?jiān)黾臃峙?m個(gè)空間，若申請(qǐng)失敗，則說明系統(tǒng)沒有()可分配的存儲(chǔ)空間。A. m個(gè)B . m個(gè)連續(xù)的C. n+m個(gè) D. n+m個(gè)連續(xù)的應(yīng)用題(9) 設(shè)A是一個(gè)線性表(a1，a2,，an),采用順序存儲(chǔ)結(jié)構(gòu)，則在等概論的前提下，平均每插入一個(gè)元素需要移動(dòng)的元素個(gè)數(shù)為多少？若元素插在ai與ai+1之間(1wiwn)的概率為(n-i) / (n (n-1) /2),則平均每插入一個(gè)元素所移動(dòng)的元素個(gè) 數(shù)是多少？(10) 設(shè)n表示線性表中的元素個(gè)數(shù)，E表示存儲(chǔ)數(shù)據(jù)

16、元素所需要的存儲(chǔ)單元大小，D表示可以在數(shù)組中存儲(chǔ)線性表的最大元素個(gè)數(shù)(D> n),則使用順序存儲(chǔ)方式存儲(chǔ)線性表需要多少存儲(chǔ)空間？(11) 在什么情況下線性表使用順序存儲(chǔ)比較好？算法設(shè)計(jì)題(12) 試以順序表作存儲(chǔ)結(jié)構(gòu)，實(shí)現(xiàn)線性表就地逆置。(13) 設(shè)計(jì)算法判斷給定字符串是否是回文。所謂回文是正讀和反讀均相同的字符串，例如abcba或abba是回文，而 abcda不是回文。(14) 設(shè)計(jì)一個(gè)時(shí)間復(fù)雜度為。 (n)的算法，實(shí)現(xiàn)將數(shù)組 An中所有元素循環(huán)左移 k 個(gè)位置。(15) 已知數(shù)組 An中的元素為整型，設(shè)計(jì)算法將其調(diào)整為左右兩部分，左邊所有元素為奇數(shù)，右邊所有元素為偶數(shù)，并要求算法的時(shí)

17、間復(fù)雜度為。(n)。(16) 假定數(shù)組中有多個(gè)零元素，設(shè)計(jì)算法將數(shù)組中所有非零元素移到數(shù)組的前端。(17) 順序存儲(chǔ)的線性表 A ,其數(shù)據(jù)元素為整型， 設(shè)計(jì)算法將A拆成B和C兩個(gè)表，使A中值大于0的元素存入表B,值小于0的元素存入表C,要求B和C不另外 設(shè)置存儲(chǔ)空間而利用 A的空間。(18) 已知順序表L中的元素遞增有序排列，設(shè)計(jì)算法將元素x插入到表L中并保持表L仍遞增有序。(19) 設(shè)計(jì)一個(gè)高效算法，在順序表中刪除所有元素值為x的元素，要求空間復(fù)雜度為。(1)。(20) 設(shè)計(jì)算法實(shí)現(xiàn)從順序表 L中刪除所有值在 x和y之間的所有元素，要求時(shí)間性能復(fù)雜度為。(n),空間性能為。(1)。(21)

18、設(shè)計(jì)算法刪除順序表中重復(fù)的元素，要求算法移動(dòng)元素的次數(shù)較少并使剩余元素間的相對(duì)次序保持不變。(22) 給定n個(gè)記錄的有序序列 An和m個(gè)記錄的有序序列 Bm,將它們歸并為一 個(gè)有序序列，存放在Cn+m中，試寫出這一算法(假設(shè)A、B和C均為升序序列)。4線性鏈表選擇題(23) 線性表的鏈接存儲(chǔ)結(jié)構(gòu)是一種A.隨機(jī)存取B.順序存取(24) 線性表采用鏈接存儲(chǔ)時(shí)，其(A.地址必須是連續(xù)的C.地址一定是不連續(xù)的(25) 鏈表不具有的特點(diǎn)是( A.可隨機(jī)訪問任一元素C.不必事先估計(jì)存儲(chǔ)空間()的存儲(chǔ)結(jié)構(gòu)。C.索引存取D.散列存取) 0B.部分地址必須是連續(xù)的D.地址連續(xù)與否均可以)。B.插入、刪除不需要移

19、動(dòng)元素D.所需空間與線性表長(zhǎng)度成正比(26) 在具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然有序的時(shí)間復(fù)雜度是()。A. 0(1)B. O(n)C. O(n2)D.O(nlog2n1)(27) 對(duì)于n個(gè)元素組成的線性表，建立一個(gè)單鏈表的時(shí)間復(fù)雜度是()。A. 0(1)B. O(n)C. O(n2)D.O(nlog2n1)(28) 對(duì)于n個(gè)元素組成的線性表，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是()。A. 0(1)B. O(n)C. O(n2)D.O(nlog2n1)(29) 在單鏈表中刪除指針 p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則執(zhí)行()。A . p->next=p->next->nextB

20、. p->next=p->nextC. p=p->next->nextD. p=p->next; p->next=p->next->next(30) 在一個(gè)單鏈表中，已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接前驅(qū)，若在q和p之間插入s所指結(jié)點(diǎn)，則執(zhí)行()操作。A . s->next=p->next; p->next=s;B. q->next=s; s->next=p;C. p->next=s->next; s->next=p;D. p->next=s; s->next=q(31) 在一個(gè)長(zhǎng)度為n

21、(n>1)的帶頭結(jié)點(diǎn)的單鏈表 h上，另設(shè)有尾指針r指向尾結(jié)點(diǎn)，執(zhí)行( )操作與鏈表的長(zhǎng)度有關(guān)。A.刪除單鏈表中的第一個(gè)元素B.刪除單鏈表中的最后一個(gè)元素C.在單鏈表第一個(gè)元素前插入一個(gè)新元素D.在單鏈表的最后一個(gè)元素后插入一個(gè)新元素(32) 在單鏈表中附加頭結(jié)點(diǎn)的目的是為了()。A .保證單鏈表中至少有一個(gè)結(jié)點(diǎn)B.標(biāo)識(shí)單鏈表中首結(jié)點(diǎn)的位置C.方便運(yùn)算的實(shí)現(xiàn)D.說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)(33) 將長(zhǎng)度為n個(gè)單鏈表鏈接在長(zhǎng)度為m的單鏈表之后的算法，其時(shí)間復(fù)雜度是A. 0(1)B. O(n)C. O(m)D. O (n+m)(34) 循環(huán)單鏈表的主要優(yōu)點(diǎn)是（）。A.不再需要頭指針了B.從表

22、中任一結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表C.已知某個(gè)結(jié)點(diǎn)的位置后，能夠容易找到它的直接前驅(qū)D.在進(jìn)行插入、刪除操作時(shí)，能更好地保證鏈表不斷開(35) 將線性表（32,，an）組織為一個(gè)帶頭結(jié)點(diǎn)的循環(huán)單鏈表，設(shè) H為鏈表的頭指針，則鏈表中最后一個(gè)結(jié)點(diǎn)的指針域中存放的是（）。A.變量H的地址B.變量H的值C.元素a1的地址D.空指針(36) 非空的循環(huán)單鏈表 L的尾結(jié)點(diǎn)p滿足（）。A. p=NULL B. p->next=NULL C. p->next=L D. p=L(37) 若要在。（1）的時(shí)間內(nèi)實(shí)現(xiàn)兩個(gè)循環(huán)單鏈表的首尾相接，則兩個(gè)循環(huán)單鏈表應(yīng)各設(shè)一個(gè)指針，分別指向（）。A.各自的頭結(jié)點(diǎn)B

23、.各自的尾結(jié)點(diǎn)C.各自的第一個(gè)元素結(jié)點(diǎn)D. 一個(gè)表的頭結(jié)點(diǎn)，一個(gè)表的尾結(jié)點(diǎn)(38) 設(shè)線性表非空，（）可以在。（1）的時(shí)間內(nèi)在表尾插入一個(gè)新結(jié)點(diǎn)。A.帶頭結(jié)點(diǎn)的單鏈表，有一個(gè)鏈表指針指向頭結(jié)點(diǎn)B.帶頭結(jié)點(diǎn)的循環(huán)單鏈表，有一個(gè)鏈表指針指向頭結(jié)點(diǎn)C.不帶頭結(jié)點(diǎn)的單鏈表，有一個(gè)鏈表指針指向表的第一個(gè)結(jié)點(diǎn)D.不帶頭結(jié)點(diǎn)的循環(huán)單鏈表，有一個(gè)鏈表指針指向表中某個(gè)結(jié)點(diǎn)（除第一個(gè)結(jié)點(diǎn)外）(39) 設(shè)指針rear指向帶頭結(jié)點(diǎn)的循環(huán)單鏈表的尾指針，若要?jiǎng)h除鏈表的第一個(gè)元素結(jié)點(diǎn)，正確的操作是（ ）。A. s=rear; rear=rear->next;B. rear=rear->next;C. rear

24、=rear->next->next;D. s=rear->next->next; rear->next->next=s->next;(40) 設(shè)有兩個(gè)長(zhǎng)度為n個(gè)單鏈表，以h1為頭指針的鏈表是非循環(huán)的，以h2為尾指針的鏈表是循環(huán)的，則（ ）。A.在兩個(gè)鏈表上刪除第一個(gè)結(jié)點(diǎn)的操作，其時(shí)間復(fù)雜度均為。（1）B.在兩個(gè)鏈表的表尾插入一個(gè)結(jié)點(diǎn)的操作，其時(shí)間復(fù)雜度均為。 （n）C.循環(huán)鏈表要比非循環(huán)鏈表占用更多的存儲(chǔ)空間D.循環(huán)鏈表要比非循環(huán)鏈表占用更少的存儲(chǔ)空間(41) 使用雙鏈表存儲(chǔ)線性表，其優(yōu)點(diǎn)是可以（）。A.提高查找速度C.節(jié)約存儲(chǔ)空間B.更方便數(shù)據(jù)的插入

25、和刪除D.很快回收存儲(chǔ)空間(20) 與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是A .插入和刪除操作更簡(jiǎn)單C.可以省略表頭指針或表尾指針(21) 帶頭結(jié)點(diǎn)的循環(huán)雙鏈表A. L->next->prior=NULL C. L->next=L)。B.可以進(jìn)行隨機(jī)訪問D.訪問其后相鄰結(jié)點(diǎn)更靈活L為空表的條件是()。B. L->prior=LD. B和C者B對(duì)(22) 在循環(huán)雙鏈表的p所指結(jié)點(diǎn)后插入s所指結(jié)點(diǎn)的操作是( )。A . p->next=s; s->prior=p; p->next->prior=s; s->next=p->next;B. p-&

26、gt;next=s; p->next->prior=s; s->prior=p; s->next=p->next;C. s->prior=p; s->next=p->next; p->next=s; p->next->prior=s;D. s->prior=p; s->next=p->next; p->next->prior=s; p->next=s;(23) 在雙鏈表中指針pa所指結(jié)點(diǎn)后面插入 pb所指結(jié)點(diǎn)，執(zhí)行的語(yǔ)句序列是()。 pb->next=pa->next; pb-&g

27、t;prior=pa; pa->next=pb; pa->next->prior=pb;A. B.C.D.(24) 在一個(gè)雙鏈表中，刪除結(jié)點(diǎn)p的操作是()。A. p->prior->next=p->next; p->next->prior=p->prior;B. p->prior=p->prior->prior; p->prior->prior=p;C. p->next->prior=p; p->next=p->next->next;D. p->next=p->prio

28、r->prior; p->prior=p->prior->prior;應(yīng)用題(25) 單鏈表設(shè)置頭結(jié)點(diǎn)的作用是什么?(26) 線性表的順序存儲(chǔ)結(jié)構(gòu)具有三個(gè)弱點(diǎn)：其一，插入或刪除操作需要移動(dòng)大量元素；其二，由于難以估計(jì)，必須預(yù)先分配較大的空間，往往使存儲(chǔ)空間不能得到充 分利用；其三，表的容量難以擴(kuò)充。 試問，線性表的鏈接存儲(chǔ)結(jié)構(gòu)是否能夠克服上 述三個(gè)弱點(diǎn)？(27) 若頻繁地對(duì)一個(gè)線性表進(jìn)行插入和刪除操作，該線性表采用什么存儲(chǔ)結(jié)構(gòu)比較好？(28) 設(shè)n表示線性表中的元素個(gè)數(shù)，P表示指針?biāo)璧拇鎯?chǔ)單元大小，E表示存儲(chǔ)數(shù)據(jù)元素所需的存儲(chǔ)單元大小，則使用單鏈表存儲(chǔ)方式存儲(chǔ)該線性表

29、需要多少存儲(chǔ) 空間(不考慮頭結(jié)點(diǎn))？算法設(shè)計(jì)題(29) 設(shè)計(jì)算法依次打印單鏈表中每個(gè)結(jié)點(diǎn)的數(shù)據(jù)信息。(30) 求單鏈表的長(zhǎng)度。(31) 設(shè)計(jì)算法將值為x的結(jié)點(diǎn)插入到不帶頭結(jié)點(diǎn)的單鏈表L中值為k的結(jié)點(diǎn)之前，若找不到值為k的結(jié)點(diǎn)，則將x插入到鏈表的末尾。(32) 判斷非空單鏈表是否遞增有序。(33) 已知非空線性鏈表由list指出，結(jié)點(diǎn)結(jié)構(gòu)為(data, link)。請(qǐng)編寫算法，將鏈表中數(shù)據(jù)域最小的結(jié)點(diǎn)移到鏈表的最前面。要求：不得額外申請(qǐng)新的結(jié)點(diǎn)。(34) 給定一個(gè)帶頭結(jié)點(diǎn)的單鏈表，設(shè) head為頭指針，設(shè)計(jì)算法按遞增次序輸出單鏈表中各結(jié)點(diǎn)的數(shù)據(jù)元素，并釋放結(jié)點(diǎn)所占的存儲(chǔ)空間(要求：不允許使用數(shù)組

30、作輔助空間)。(35) 已知非空線性鏈表由list指出，設(shè)計(jì)算法交換p所指結(jié)點(diǎn)與其后續(xù)結(jié)點(diǎn)在鏈表中的位置(設(shè)p所指結(jié)點(diǎn)不是鏈表的最后一個(gè)結(jié)點(diǎn))。(36) 設(shè)計(jì)算法實(shí)現(xiàn)將單鏈表就地逆置。(37) 頭插法建立單鏈表。(38) 尾插法建立單鏈表(39) 復(fù)制一個(gè)單鏈表。(40) 設(shè)計(jì)算法實(shí)現(xiàn)將單鏈表就地逆置。(41) 在一個(gè)有序單鏈表(假設(shè)從小到大排列)中插入一個(gè)元素值為 x的結(jié)點(diǎn)，使得插入后單鏈表仍然有序。(42) 設(shè)單鏈表以非遞減有序排列，設(shè)計(jì)算法實(shí)現(xiàn)在單鏈表中刪去值相同的多余結(jié)點(diǎn)。(43) 已知單鏈表中各結(jié)點(diǎn)的元素值為整型且遞增有序，設(shè)計(jì)算法刪除表中大于mink且小于maxk的所有元素，并釋放

31、被刪結(jié)點(diǎn)的存儲(chǔ)空間。(44) 有兩個(gè)整數(shù)序列 A=(a1，a2,，am)和B=(b 1, b2,，bn)已經(jīng)存入兩個(gè)單鏈表中，設(shè)計(jì)算法判斷序列 B是否是序列A的子序列。(45) 設(shè)線性表C=(a1，b1, 32, b2,，an, bn)采用帶頭結(jié)點(diǎn)的單鏈表存儲(chǔ)，設(shè)計(jì)算法將表C拆分為兩個(gè)線性表 A和B,使得A=(a 1,科 ，an), B=(b1，b2,， bn)。(46) 有兩個(gè)遞增有序的單鏈表la和lb,設(shè)計(jì)算法將這兩個(gè)單鏈表合并為一個(gè)有序鏈表。(47) 有兩個(gè)有序的單鏈表， 一個(gè)表為升序，另一個(gè)表為降序，設(shè)計(jì)算法將這兩個(gè)鏈 表合并為一個(gè)有序鏈表。(48) 已知單鏈表 A和B的數(shù)據(jù)(設(shè)為整型

32、)遞增有序，設(shè)計(jì)算法利用原有結(jié)點(diǎn)， 將表A中與表B具有相同值的結(jié)點(diǎn)刪除， 將表B中與原表A不同值的結(jié)點(diǎn)存入表 A中，并保持表A的遞增有序。(49) 設(shè)計(jì)算法將循環(huán)單鏈表就地逆置。(50) 已知L為單鏈表的頭結(jié)點(diǎn)地址， 表中共有m (m> 3)個(gè)結(jié)點(diǎn)，從表中第i個(gè)(1 <i <m)結(jié)點(diǎn)起到第 m個(gè)結(jié)點(diǎn)構(gòu)成一個(gè)部分循環(huán)鏈表。設(shè)計(jì)算法將這部分循環(huán)鏈 表中所有結(jié)點(diǎn)順序完全倒置。(51) 假設(shè)在長(zhǎng)度大于1的循環(huán)單鏈表中，即無頭結(jié)點(diǎn)也無頭指針，s為指向鏈表中某個(gè)結(jié)點(diǎn)的指針，試編寫算法刪除結(jié)點(diǎn)s的前驅(qū)結(jié)點(diǎn)。(52) 設(shè)循環(huán)單鏈表 L1,對(duì)其遍歷的結(jié)果是：X1, X2, X3,，xn-1,

33、xn。請(qǐng)將該循 環(huán)鏈表拆成兩個(gè)循環(huán)單鏈表L1和L2 ,使得L1中含有原L1表中序號(hào)為奇數(shù)的結(jié)點(diǎn)且遍歷結(jié)果為：X1,X3,；L2中含有原L1表中序號(hào)為偶數(shù)的結(jié)且遍歷結(jié)果為：X4 , X2。(53) 已知一單鏈表中的數(shù)據(jù)元素含有三類字符：字母、數(shù)字和其他字符。試編寫算法，構(gòu)造三個(gè)循環(huán)單鏈表，使每個(gè)循環(huán)鏈表中只含同一類字符。(54) 有兩個(gè)循環(huán)鏈表tail1和tail2 (tail1和tail2分別指向循環(huán)鏈表的尾指針)，編寫算法將循環(huán)鏈表tail2鏈接到循環(huán)鏈表tail1之后，并使鏈接后的鏈表仍是循環(huán)鏈(55) 已知p指向循環(huán)單鏈表最后一個(gè)結(jié)點(diǎn)的指針，試編寫只包含一個(gè)循環(huán)的算法，將線性表(a1，a

34、2,，an-1,an,)改造成(a1，a2,，an-1,an,an-1,，a2,a1)。(56) 判斷帶頭結(jié)點(diǎn)的循環(huán)雙鏈表是否對(duì)稱。(57) 設(shè)計(jì)算法實(shí)現(xiàn)雙鏈表中第i個(gè)結(jié)點(diǎn)的前面插入一個(gè)值為X的結(jié)點(diǎn)。(58) 已知非空循環(huán)雙鏈表head的存儲(chǔ)結(jié)構(gòu)為：Struct DNode TElem info;Struct DNode *left;Struct DNode *right;設(shè)計(jì)算法實(shí)現(xiàn)從鏈表中刪除指針p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)(假設(shè)該結(jié)點(diǎn)存在)(59) 已知非空雙鏈表由d指出，結(jié)點(diǎn)結(jié)構(gòu)為(priordatanext),請(qǐng)?jiān)O(shè)計(jì)算法將鏈表中數(shù)據(jù)值最大(假定唯一)的那個(gè)結(jié)點(diǎn)移至鏈表的最前面。要求不得額外申

35、請(qǐng)新的雙 鏈表結(jié)點(diǎn)。(60) 設(shè)計(jì)算法實(shí)現(xiàn)將雙鏈表中結(jié)點(diǎn)p與其后繼結(jié)點(diǎn)互換位置。(61) 設(shè)有一個(gè)雙鏈表，每個(gè)結(jié)點(diǎn)中除了有prior、data和next三個(gè)域外，還有一個(gè)訪問頻度域freq,在鏈表被起用之前，其值均初始化為零，每當(dāng)在雙鏈表上進(jìn)行一 次LOCATE運(yùn)算時(shí)，令元素值為 x的結(jié)點(diǎn)中freq域的值增1,并使此鏈表中結(jié)點(diǎn) 保持頻度遞減的順序排列，以便使頻繁訪問的結(jié)點(diǎn)總是靠近表頭。編寫算法實(shí)現(xiàn)符合上述要求的LOCATE算法。5靜態(tài)鏈表選擇題(1) 靜態(tài)鏈表中指針表示的是()。A.下一結(jié)點(diǎn)在內(nèi)存中的地址B.下一元素在數(shù)組中的下標(biāo)C.左、右孩子的存儲(chǔ)位置D.左、右孩子的地址(2) 以下說法錯(cuò)誤

36、的是( )。靜態(tài)鏈表既有順序存儲(chǔ)的優(yōu)點(diǎn)又有動(dòng)態(tài)鏈表的優(yōu)點(diǎn)。所以，它存取表中第i個(gè)元素的時(shí)間與i無關(guān)靜態(tài)鏈表中能容納的元素個(gè)數(shù)在定義表時(shí)必須是確定的靜態(tài)鏈表與動(dòng)態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動(dòng)A.，B.C.， D.(3) 用數(shù)組r存儲(chǔ)靜態(tài)鏈表，結(jié)點(diǎn)的next域指向后繼，工作指針j指向鏈中某結(jié)點(diǎn)， 使j沿鏈移動(dòng)的操作為()。A . j=rj.nextB. j=j+1C. j=j->nextD. j=rj->next(4) 線性表的靜態(tài)鏈表存儲(chǔ)與順序存儲(chǔ)相比，優(yōu)點(diǎn)是()。A.所有基本操作的算法實(shí)現(xiàn)簡(jiǎn)單B.便于隨機(jī)存取C.便于插入和刪除D.便于利用零散的存儲(chǔ)空間a0.lin

37、k ,則(5) 下圖所示數(shù)組中以靜態(tài)鏈表形式存儲(chǔ)了一個(gè)線性表，設(shè)頭指針為該線性表的元素依次為()。6063404574254376201012345678下標(biāo)datalinkA. 60, 63,40,45, 74, 25B. 45, 63,25,60,40,74C. 74, 25,45,60, 40, 63D, 25, 45,60,40,63,746線性表綜合選擇題(1) 下面關(guān)于線性表的敘述中，錯(cuò)誤的是()。A.線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B.線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作C.線性表采用鏈接存儲(chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D.線性表采用鏈接存儲(chǔ)，便于插入和刪除操

38、作(2) 若某線性表中最常用的操作是取第i個(gè)元素和找第i個(gè)元素的前驅(qū)，則采用()存儲(chǔ)方法最節(jié)約時(shí)間。A.順序表 B.單鏈表C.雙鏈表 D,循環(huán)單鏈表(3) 若鏈表中最常用的操作是在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除第一個(gè)結(jié)點(diǎn)，則采用( )存儲(chǔ)方法最節(jié)約時(shí)間。A.單鏈表B.循環(huán)雙鏈表C.循環(huán)單鏈表D.帶尾指針的循環(huán)單鏈表(4) 設(shè)線性表有n個(gè)元素，以下操作中，()在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)的效率更高。A.輸出第i (iwi wn)個(gè)元素值B.交換第1個(gè)和第2個(gè)元素的值C.順序輸出所有n個(gè)元素D.查找與給定值x相等的元素在線性表中的序號(hào)(5) 如果對(duì)于具有n(n> 1)個(gè)元素的線性表的基本

39、操作有 4種：刪除第一個(gè)元素；刪除最后一個(gè)元素；在第一個(gè)元素前插入新元素；在最后一個(gè)元素的后面插入新元素。則最好使用()。A.只設(shè)尾指針的循環(huán)單鏈表B.只設(shè)尾指針的非循環(huán)單鏈表C.只設(shè)頭指針的循環(huán)雙鏈表D.同時(shí)設(shè)置頭指針和尾指針的循環(huán)單鏈表應(yīng)用題(6) 請(qǐng)比較線性表的兩種基本的存儲(chǔ)結(jié)構(gòu)一一順序表和單鏈表。(7) 舉例說明對(duì)相同的邏輯結(jié)構(gòu)，同一種運(yùn)算在不同的存儲(chǔ)方式下實(shí)現(xiàn)，算法的效率不同。(8) 如果某線性表中數(shù)據(jù)元素的類型不一致，但是希望能根據(jù)下標(biāo)隨機(jī)存取每個(gè)元素，請(qǐng)為這個(gè)線性表設(shè)計(jì)一個(gè)合適的存儲(chǔ)結(jié)構(gòu)。(9) 線性鏈表有哪幾種常見的變形？各有何特點(diǎn)？算法設(shè)計(jì)題(10) 用順序表表示集合，設(shè)計(jì)算

40、法實(shí)現(xiàn)集合的求交集運(yùn)算。(11) 用順序表表示集合，設(shè)計(jì)算法實(shí)現(xiàn)集合的求并集運(yùn)算。(12) 用順序表表示集合，設(shè)計(jì)算法實(shí)現(xiàn)集合的求差集運(yùn)算，要求不另外開辟空間。(13) 假定以有序表表示集合，設(shè)計(jì)算法判斷兩個(gè)給定集合是否相等。(14) 設(shè)兩個(gè)單鏈表L1和L2分別表示兩個(gè)集合，設(shè)計(jì)算法判斷L1是否是L2的子(15) 已知兩個(gè)不帶頭結(jié)點(diǎn)的單鏈表A和B分別表示兩個(gè)集合，并且其元素值遞增有序，求A、B的交集C,并以同樣的遞增形式存儲(chǔ)，要求盡可能節(jié)省時(shí)間。(16) 在某商店的倉(cāng)庫(kù)中，對(duì)電視機(jī)按其價(jià)格從低到高建立一個(gè)單鏈表，鏈表的每個(gè)結(jié)點(diǎn)指出同樣價(jià)格的電視機(jī)的臺(tái)數(shù)。現(xiàn)有m臺(tái)價(jià)格為n元的電視機(jī)入庫(kù)，請(qǐng)編寫算

41、法完成倉(cāng)庫(kù)的進(jìn)貨管理。(17) 從鍵盤輸入n個(gè)英語(yǔ)單詞，輸入格式為n,W1,w2,，wn,其中n表示隨后輸入英語(yǔ)單詞個(gè)數(shù)，試編寫算法建立一個(gè)單鏈表，要求：如果單詞重復(fù)出現(xiàn)，則只在鏈表上只保留一個(gè)；統(tǒng)計(jì)單詞重復(fù)出現(xiàn)的次數(shù)，然后輸出次數(shù)最多的前k (kvn)個(gè)單詞。(18) 一元稀疏多項(xiàng)式可以采用單鏈表形式存儲(chǔ)，設(shè)計(jì)算法完成A(x)+B(x),其中A(x)和B(x)均為稀疏的一元多項(xiàng)式，要求利用原表的存儲(chǔ)空間。(19) 假設(shè)用不帶頭結(jié)點(diǎn)的單鏈表表示八進(jìn)制數(shù)，例如，八進(jìn)制數(shù)536可以表示成三個(gè)結(jié)點(diǎn)的鏈表。要求寫一個(gè)函數(shù) Add,該函數(shù)有兩個(gè)參數(shù) P和Q,分別指向表示八 進(jìn)制數(shù)的鏈表，執(zhí)行函數(shù)調(diào)用Ad

42、d(P,Q)后，將返回表示八進(jìn)制數(shù)P加八進(jìn)制數(shù) Q所得結(jié)果數(shù)的鏈表。(20) 約瑟夫環(huán)問題：設(shè)有編號(hào)為1, 2,，n的n (n>0)個(gè)人圍成一個(gè)圈，每個(gè)人持有一個(gè)密碼 m (m甘1),從第1個(gè)人開始報(bào)數(shù)，報(bào)到 m時(shí)停止報(bào)數(shù)，報(bào) m的 人出圈，再?gòu)乃南乱粋€(gè)人起重新報(bào)數(shù)，報(bào)到 m時(shí)停止報(bào)數(shù)，報(bào) m的出圈， 如此下去，直到所有人全部出圈為止。當(dāng)任意給定n和m后，設(shè)計(jì)算法求n個(gè)人出圈的次序。(21) 編寫算法，完成下述要求：建立一個(gè)鏈表用于存放輸入的二進(jìn)制數(shù)，鏈表中的每個(gè)結(jié)點(diǎn)的data域存放一個(gè)二進(jìn)制位。在此鏈表上實(shí)現(xiàn)對(duì)二進(jìn)制數(shù)加1的運(yùn)算，并輸出運(yùn)算結(jié)果。(22) 有一個(gè)不帶頭結(jié)點(diǎn)的單鏈表 h

43、,通過遍歷鏈表將鏈表中所有的鏈接方向逆轉(zhuǎn)，算法如下，請(qǐng)?jiān)诳崭裉幪顚懻_的語(yǔ)句。 void Inverse(&h) if ()return;p=h->next; pr=NULL; while ()h->next=pr;pr=h; h=p; (23) 設(shè)兩個(gè)帶頭結(jié)點(diǎn)的單鏈表 A和B,表中結(jié)點(diǎn)的數(shù)據(jù)為整型， 下面算法產(chǎn)生表 A 和表B的并集并以表C存儲(chǔ)，請(qǐng)?zhí)顚懰惴ㄖ锌瞻滋幍恼Z(yǔ)句，完成其功能。7棧的基本概念選擇題(1) 經(jīng)過以下棧運(yùn)算后，x的值是()。InitStack(s) , Push(s,a), Push(s,b), Pop(s,x), GetTop(s,x)A. aB. b

44、C. 1D. 0(2) 經(jīng)過以下棧運(yùn)算后，StackEmpty(s)的值是()。InitStack(s) , Push(s,a), Push(s,b), Pop(s,x), Pop(s,y)A. aB. bC. 1D. 0(3) ()不是棧的基本運(yùn)算。A.刪除棧頂元素B.刪除棧底元素C.判斷棧是否為空D.將棧置為空棧(4) 設(shè)有一個(gè)空棧，棧頂指針為 1000H (十六進(jìn)制，下同)，每個(gè)元素需要1個(gè)單位的存儲(chǔ)空間，貝U執(zhí)行 PUSH, PUSH, POP, PUSH, POP, PUSH, POP, PUSH 操作后，棧頂指針值為()。A. 1002H B. 1003HC. 1004HD. 10

45、05H(5) 一個(gè)棧的入棧序列是1 , 2, 3A. 5, 4, 3, 2, 1C. 4 , 3, 5, 1, 2(6)若一個(gè)棧的輸入序列是1, 2,個(gè)輸出元素是()。A .不確定 B . n-i,4, 5,則棧的不可能的輸出序列是()。B. 4, 5, 3, 2, 1D. 1 , 2, 3, 4, 53,，n,輸出序列的第一個(gè)元素是n,則第i(7) 若一個(gè)棧的輸入序列是 p1=3,貝U p2 的值()。A. 一定是2 B, 一定是1(8) 若一個(gè)棧的輸入序列是p3 = 1 ,貝U p1 的值()。A.可能是2 B, 一定是2C. n-i-1D. n-i+1 1, 2, 3,，n,其輸出序列是

46、 pi, p2,，pn,若C.不可能是1 D.以上都不對(duì)n,右Pi, p2,，pn,其輸出序列是 1, 2, 3,C.不可能是2 D.不可能是33且可用作C語(yǔ)言標(biāo)識(shí)符的序列有D. 6個(gè)(9) 當(dāng)字符序列t3_依次通過棧，輸出長(zhǎng)度為()。A. 4個(gè)B. 5個(gè)C. 3個(gè)應(yīng)用題(10) 設(shè)有一個(gè)棧，元素進(jìn)棧的次序?yàn)锳, B, C, D, E,能否得到如下出棧序歹U,若能，請(qǐng)寫出操作序列，若不能，請(qǐng)說明原因。C, E, A, B, DC, B, A, D, E(11) 在操作序列 push、push(2)、pop、push(5)、push(7)、pop、push(6)之后，棧頂元素和棧底元素分別是什么

47、？(push(k)表示整數(shù)k入棧，pop表示棧頂元素出棧。)(12) 設(shè)元素1、2、3、P、A依次經(jīng)過一個(gè)棧，進(jìn)棧次序?yàn)?123PA,在棧的輸出序列中，有哪些序列可作為C+程序設(shè)計(jì)語(yǔ)言的變量名。(13) 如果進(jìn)棧序列為 A、B、C、D,則可能的出棧序列是什么？算法設(shè)計(jì)題(14) 假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出 棧的操作序列可表示為僅由 I和O組成的序列，稱可以操作的序列為合法序列， 否則稱為非法序列。 下面所示的序列中哪些是合法的？A. IOIIOIOO B. IOOIOIIOC. IIIOIOIO D. IIIOOIOO通過對(duì)的分析，寫出一個(gè)算法，判定所給

48、的操作序列是否合法。若合法，返回true, 否則返回false (假定被判定的操作序列已存入一維數(shù)組中)。8順序棧選擇題(1) 在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端(即下標(biāo)為0的單元)作為棧底，以top作為棧頂指針，當(dāng)出棧時(shí)，top的變化為()。A.不變B. top=0C. top-1D. top=top+1(2) 設(shè)數(shù)組Sn作為兩個(gè)棧S1和S2的存儲(chǔ)空間，對(duì)任何一個(gè)棧只有當(dāng)Sn全滿時(shí)才不能進(jìn)行進(jìn)棧操作。為這兩個(gè)棧分配空間的最佳方案是()。A . S1的棧底位置為B. S1的棧底位置為C. S1的棧底位置為0, S2的棧底位置為0, S2的棧底位置為0, S2的棧底位置為n-1 n/2

49、 nD. S1的棧底位置為0, S2的棧底位置為1(3) 為了增加內(nèi)存空間的利用率和減少溢出的可能性，兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí)，應(yīng)將兩棧的棧底分別設(shè)在這片內(nèi)存空間的兩端，這樣，當(dāng)()時(shí)才產(chǎn)生上溢。A.兩個(gè)棧的棧頂同時(shí)到達(dá)?？臻g的中心點(diǎn)B.其中一個(gè)棧的棧頂?shù)竭_(dá)?？臻g的中心點(diǎn)C.兩個(gè)棧的棧頂在?？臻g的某一位置相遇D.兩個(gè)棧均不空，且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底(4) 兩個(gè)棧共享一個(gè)數(shù)組空間的好處是()。A.減少存取時(shí)間，降低發(fā)生上溢的可能性B.節(jié)省存儲(chǔ)空間，降低發(fā)生上溢的可能性C.減少存取時(shí)間，降低發(fā)生下溢的可能性D.節(jié)省存儲(chǔ)空間，降低發(fā)生下溢的可能性算法設(shè)計(jì)題(5) 假設(shè)以I和O分別表示

50、入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅有I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非合法序列。下面所示的序列中哪些是合法的？通過對(duì)的分析，寫出一個(gè)算法，判定所給的操作序列是否合法。若合法，返回true, 否則返回false (假定被判定的操作序列已存入一維數(shù)組中)。(6) 下面的算法將一個(gè)整數(shù) e壓入到堆棧S,請(qǐng)?jiān)诳崭裉幪钌线m當(dāng)?shù)恼Z(yǔ)句實(shí)現(xiàn)該操作。Typedef struct int *base; int top;int stacksize;SqStack;歡迎下載int Push(SqStack S,int e) if () S.base=(int *

51、)realloc(S.base,(S.stacksize+1)*sizeof(int); if () printf ( Not Enough Memory!n ");retuan 0;S.top=®S.stacksize=®®retuan 1;歡迎下載9鏈棧選擇題(1) 向一個(gè)棧頂指針為 h的帶頭結(jié)點(diǎn)的鏈棧中插入指針s所指的結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行()。A. h->next=s;B. s->next=h;C. s->next=h; h->next=s;D. s->next=h->next; h->next=s;(2) 從棧

52、頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)，用x保存被刪除結(jié)點(diǎn)的值，則執(zhí)行()。A . x=top; top=top->next;B. x=top->data;C. top=top->next; x=top->data;D. x=top->data; top=top->next;歡迎下載10隊(duì)列的基本概念選擇題(1) 隊(duì)列的“先進(jìn)先出”特性是指( )。A.最后插入隊(duì)列中的元素總是最后被刪除B.當(dāng)同時(shí)進(jìn)行插入、刪除操作時(shí)，總是插入操作優(yōu)先C.每當(dāng)有刪除操作時(shí)，總要先做一次插入操作D.每次從隊(duì)列中刪除的總是最早插入的元素)。B.取出最近入隊(duì)的元素D.刪除隊(duì)頭元素(2)

53、允許對(duì)隊(duì)列進(jìn)行的操作有(A.對(duì)隊(duì)列中的元素排序C.在隊(duì)頭元素之前插入元素(3) 一個(gè)隊(duì)列的入隊(duì)順序是1、2、3、4,則隊(duì)列的輸出順序是()。A. 4321B. 1234C. 1432D, 3241歡迎下載11順序隊(duì)列選擇題(1) 循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A0m中，則入隊(duì)時(shí)的操作為()。A. rear=rear+1B. rear=(rear+1) mod (m-1)C. rear=(rear+1) mod mD. rear=(rear+1) mod (m+1)(2) 若用一個(gè)長(zhǎng)度為 6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前 rear和front的值分別為0和3,則從隊(duì)列中刪除一個(gè)元素，再增加兩個(gè)元素后，rear

54、和front的值分別為()。A. 1和 5B. 2和 4C. 4和 2D. 5和 1(3) 已知循環(huán)隊(duì)列的存儲(chǔ)空間為數(shù)組A21 , front指向隊(duì)頭元素的前一個(gè)位置，rear指向隊(duì)尾元素，假設(shè)當(dāng)前front和rear的值分別是8和3,則該隊(duì)列的長(zhǎng)度為( )。A. 5B. 6C. 16D. 17(4) 如圖所示為一個(gè)元素類型為字符型的環(huán)形隊(duì)列，如果 front指向隊(duì)頭元素的前一個(gè)位置，rear指向隊(duì)尾元素，則所表示的隊(duì)列為()。012 3 4 5678 9101112131415 16171819 20 2122A. The fB . beautiful The fC. flower isD. eautiful The fThefloweRIsbeauTifulT rearT front應(yīng)用題(5) 舉例說明順序隊(duì)