數(shù)據(jù)結(jié)一、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中計(jì)算機(jī)的 操作對(duì)象 數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R，其中D是 是D上的 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的邏輯結(jié)構(gòu) 、數(shù)據(jù)的結(jié)構(gòu) 和數(shù)據(jù)的 運(yùn)算 線性結(jié)構(gòu)中元間存在一對(duì)一關(guān)系，樹形結(jié)構(gòu)中元間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元間存在多對(duì)多關(guān)系。性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)最后一個(gè)結(jié)點(diǎn)沒(méi)有 后續(xù)結(jié)點(diǎn)其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn)葉子結(jié)點(diǎn)沒(méi)有后續(xù) 結(jié)點(diǎn)其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以任意個(gè) 。在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以任意多 數(shù)據(jù)的結(jié)構(gòu)可用四種基本的方法表示它們分別是順序、鏈?zhǔn)健⑺饕蜕⒘?。?shù)據(jù)的運(yùn)算最常用的有5、刪除、修改、查找、排序一個(gè)算法的效率可分為時(shí) 效率 空 效率在順序表中插入或刪除一個(gè)元素，需要平均移動(dòng)表中一半元素，具體移動(dòng)的元素個(gè)數(shù)與表長(zhǎng)和該元素在表中的位置有關(guān)。線性表中結(jié)點(diǎn)的集合是有 的，結(jié)點(diǎn)間的關(guān)系 一對(duì) 的向一個(gè)長(zhǎng)度為n的向量的第i個(gè)元素(1≤i≤n+1)之前插入一個(gè)元素時(shí)，需向后移動(dòng)n-i+1個(gè)元素。n刪除第i元素(1≤i≤nn-i個(gè)在順序表中任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O(1)，因此，順序表也稱為隨機(jī)存取的數(shù)據(jù)結(jié)構(gòu)。順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置不一定相鄰。在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的位置由其直接前驅(qū)結(jié)點(diǎn)的鏈域的值指示。在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p，需找到它的前驅(qū)結(jié)點(diǎn)的地址，其時(shí)間復(fù)雜度為O（n。向量、棧和隊(duì)列都是線性結(jié)構(gòu)，可以在向量的任何位置插入和刪能在隊(duì)尾插入和隊(duì)首刪除元素。棧是一種特殊的線性表，允許插入和刪除運(yùn)算的一端稱為棧頂。不允許插入和刪除運(yùn)算的一端稱為棧底。隊(duì)列是被限定為只能在表的一端進(jìn)行插入運(yùn)算，在表的另一端進(jìn)行刪除不包含任何字符（長(zhǎng)度為0）的串稱為空串；由一個(gè)或多個(gè)空格（由空格符）組成的 稱為空白串子串的定位運(yùn)算稱為串的模式匹配；被匹配的主串 稱為目標(biāo)串，子串假設(shè)有二維數(shù)組A6×8，每個(gè)元素用相鄰的6個(gè)字節(jié)，器按字節(jié)編址。已知A的起始位置（址為1000，則數(shù)組A的體積（量 ；末尾元素A57的第一個(gè)字節(jié)地址為 ；若按行時(shí)，元素A14的第一個(gè)字節(jié)地址為(8+4)×6 ；若按列時(shí)，元素A47的第一個(gè)字節(jié)地址為(6×7＋4)×6＋1000）＝1276 由３個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹 5種形態(tài) 6n+n0+nn1=31 個(gè)葉子注：滿二叉樹沒(méi)有度為1的結(jié)點(diǎn)，所以分支結(jié)點(diǎn)數(shù)就是二度結(jié)點(diǎn)數(shù)一棵具有２５７個(gè)結(jié)點(diǎn)的完全二叉樹，它的深度 （log2(n)+1=8.xx設(shè)一棵完全二叉樹有700350個(gè)葉子結(jié)點(diǎn)。設(shè)一棵完全二叉樹具有1000結(jié)500有499個(gè)度為2的結(jié)點(diǎn)，有1個(gè)結(jié)點(diǎn)只有非空左，有0個(gè)結(jié)點(diǎn)答：最快方法：用葉子數(shù)＝[n/2]＝500，n2=n0-1=499。另外，最后一結(jié)點(diǎn)為2i屬于左葉子，右葉子是空的，所以有1個(gè)非空左。完全二叉樹的特點(diǎn)決定不可在數(shù)據(jù)的存放無(wú)規(guī)律而言的線性表中進(jìn)行檢索的最佳方法是順序查找（查找）線性有序表（a1，a2，a3，…，a256)是從小到大排列的，對(duì)一個(gè)給定的值k，用二分法檢索表中與k相等的元素在查找不成功的情況下最多需要檢索8 設(shè)有100個(gè)結(jié)點(diǎn)，用二分法查找時(shí)，最大比較次數(shù)是7 假設(shè)在有序線性表a[20]上進(jìn)行折半查找，則比較一次查找成功的結(jié)點(diǎn)數(shù)為1；比較兩次查找成功的結(jié)點(diǎn)數(shù)為2 ；比較四次查找成功的結(jié)點(diǎn)數(shù)為8 查找長(zhǎng)度 3.72解：顯然，平均查找長(zhǎng)度＝O（logn）<5（25。但具體是多少次，則不應(yīng)當(dāng)按照2nn＝2m-1的情況下推導(dǎo)出來(lái)的公式。應(yīng)當(dāng)用窮舉法羅列全部元素的查找次數(shù)為＝（122438455）＝74ASL74/20=3.7折半查找有序表（46122028385070，88100，若查找表中元素20，它將依次與表中元素 28，6，12，20 比較大小。在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是散列查 散列法的基本思想是由關(guān)鍵字的值 （）1.表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針的結(jié)點(diǎn)可以含有兩個(gè)指針域，分別存放指向其直接前趨和直接后繼結(jié)點(diǎn)的指針。（×）2.鏈表的物理結(jié)構(gòu)具有同鏈表一樣的順序。錯(cuò)，鏈表的結(jié)構(gòu)特（×）3.表的刪除算法很簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)（×）4.性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一錯(cuò)，了邏輯結(jié)構(gòu)與物理結(jié)構(gòu)，鏈表也是線性表！且即使是順序表，也能存放記錄型數(shù)據(jù)。（×）5.序表結(jié)構(gòu)適宜于進(jìn)行順序存取，而鏈表適宜于進(jìn)行隨機(jī)存取。（×）6.順序方式的優(yōu)點(diǎn)是密度大，且插入、刪除運(yùn)算效率高錯(cuò)，前一半正確，但后一半說(shuō)法錯(cuò)誤，那是鏈?zhǔn)降膬?yōu)點(diǎn)。順序方式插入、刪除運(yùn)算效率較低，在表長(zhǎng)為n動(dòng)表長(zhǎng)一半個(gè)數(shù)的數(shù)據(jù)元素。（×）7.線性表在物理空間中也一定是連續(xù)的錯(cuò)，線性表有兩種方式，順序和鏈?zhǔn)?。后者不要求連續(xù)存放（×）8.線性表在順序時(shí)，邏輯上相鄰的元素未必在的物理位置次序錯(cuò)誤。線性表有兩種方式，在順序時(shí)，邏輯上相鄰的元素在的物理位置次序上也相鄰。（×）9.順序方式只能用于線性結(jié)構(gòu) （×）10.線性表的邏輯順序與順序總是一致的。錯(cuò)，理由同7。鏈?zhǔn)骄蜔o(wú)需一致。（×）11.線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是錯(cuò)，線性表是邏輯結(jié)構(gòu)概念，可以順序或鏈?zhǔn)剑c元素?cái)?shù)據(jù)類型無(wú)關(guān)（×）12.表結(jié)構(gòu)中最常用的是線性表，棧和隊(duì)列不太常用。錯(cuò)，不一定吧？調(diào)用子程序或函數(shù)常用，CPU也用隊(duì)列。（√）13.棧是一種對(duì)所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是（√）14.對(duì)于不同的使用者，一個(gè)表結(jié)構(gòu)既可以是棧，也可以是隊(duì)列，也可而已。（×）15.和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)錯(cuò)，棧是邏輯結(jié)構(gòu)的概念，是特殊殊線性表，而鏈表是結(jié)構(gòu)概念，二者不是類項(xiàng)。（×）16.和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)同而已。（√）17.棧和隊(duì)列的方式既可是順序方式，也可是方式（√）18.兩個(gè)棧共片連續(xù)內(nèi)存空間時(shí)，為提高內(nèi)存利用率，減少溢出機(jī)（×）19.隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)錯(cuò)，后半句不對(duì)（×）20.個(gè)棧的輸入序列是12345，則棧的輸出序列不可能是12345。（）21.二叉樹用二叉鏈表作存貯結(jié)構(gòu)，則在n結(jié)點(diǎn)的二叉樹鏈表中只n—1個(gè)非空指針域（×）22.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵的高度差等于1（√）23.二叉樹中每個(gè)結(jié)點(diǎn)的兩棵是有序的（×）24.二叉樹中每個(gè)結(jié)點(diǎn)有兩棵非空或有兩棵空（（×）25.二叉樹中每個(gè)結(jié)點(diǎn)的關(guān)鍵字值大于其左非空若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值，且小于其右非空（若存在的話）所有結(jié)點(diǎn)的關(guān)鍵字值。（應(yīng)（（×）26.二叉樹中所有結(jié)點(diǎn)個(gè)數(shù)是2k-1-1，其中k是樹的深（應(yīng)2i-（×）27.二叉樹中所有結(jié)點(diǎn)，如果不存在非空左，則不存在非空右2i—1結(jié)點(diǎn)（應(yīng)2i-1）（√）29.用二叉鏈表法（link-rlink）包含n個(gè)結(jié)點(diǎn)的二叉樹，結(jié)點(diǎn)的個(gè)指針區(qū)域中有n+1個(gè)為空指針（）30.具有12結(jié)點(diǎn)的完全二叉樹有5度為2結(jié)點(diǎn)。（B）1.非線性結(jié)構(gòu)是數(shù)據(jù)元間存在一種A）一對(duì)多關(guān)系B）多對(duì)多關(guān)系C）多對(duì)一關(guān)系D）一對(duì)一（C）2.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的結(jié)構(gòu)A)B)物 C)邏 D)物理（C）3.的目A)找出數(shù)據(jù)結(jié)構(gòu)的合理 B)研究算法中的輸入和輸出的關(guān)C)分析算法的效率以求改 D)分析算法的易懂性和（A）4.的兩A)空間復(fù)雜性和時(shí)間復(fù)雜 B)正確性和簡(jiǎn)明C)可讀性和文D)數(shù)據(jù)復(fù)雜性和程序復(fù)雜（C）5.法指A)計(jì)算方法 B)排序方法C)解決問(wèn)題的有限運(yùn)算序列 D)調(diào)度方（B）6.計(jì)算機(jī)算法必須具備輸入、輸出 等5個(gè)特性A)可行性、可移植性和可擴(kuò)充 B)可行性、確定性和有窮C)確定性、有窮性和穩(wěn)定 D)易讀性、穩(wěn)定性和安全（C）7．?dāng)?shù)據(jù)在計(jì)算機(jī)器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù) （B）8.一個(gè)向量第一個(gè)元素的地址是100，每個(gè)元素的長(zhǎng)度為2，則第個(gè)元 （A）9.n結(jié)點(diǎn)的順序表中，算法O（1）的操作是 第i個(gè)結(jié)點(diǎn)（1≤i≤n）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)刪除第in個(gè)結(jié)點(diǎn)從小到大排（B）10個(gè)有127素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)個(gè)元素 （A）11.的結(jié)構(gòu)所占空間分兩部分，一部分存放結(jié)點(diǎn)值，另一只有一部分，存放結(jié)點(diǎn)(C）只有一部分，表示結(jié)點(diǎn)間關(guān)系的指（D）分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元（B）12.鏈表是一種采 結(jié)構(gòu)的線性表（A）順 （B）鏈 （C）星 （D）網(wǎng)（D）13.線性表若采用鏈?zhǔn)浇Y(jié)構(gòu)時(shí)，要求內(nèi)存中可用單元的地址（A）必須是連續(xù) （B）部分地址必須是連續(xù)（C）一定是不連續(xù) （D）連續(xù)或不連續(xù)都可（B）14．線性表Ｌ 情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)（Ａ）需經(jīng)常修改Ｌ中的結(jié)點(diǎn) （Ｂ）需不斷對(duì)Ｌ進(jìn)行刪除插（Ｃ）Ｌ中的結(jié) （Ｄ）Ｌ中結(jié)點(diǎn)結(jié)構(gòu)復(fù)（B）15.棧中元素的進(jìn)出原則Ａ．先進(jìn)先 Ｂ．后進(jìn)先 Ｃ．?？談t Ｄ．棧滿則（C）16.棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi Ｃ．n- （B）17一個(gè)棧ST（最多元m0）為空的條件Ａ．ST- Ｂ．ST- Ｃ．ST-Ｄ．ST-（C）18.在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù) 倍 B. C. D.（B）19.在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的 B. C. D.（B）20.有8個(gè)結(jié)點(diǎn)的無(wú)向圖最多 條邊 B. C. （C）21.有8個(gè)結(jié)點(diǎn)的有向完全圖 條邊 B. C. （B）22．在表長(zhǎng)為ｎ的鏈表中進(jìn)行線性查找，它的平均查找長(zhǎng)度為Ａ.ＡＳＬ＝ｎ; Ｂ.ＡＳＬ＝（ｎ＋１）／２;nＣ. Ｄ.n（A）23．折半查找有序表（4，6，10，12，20，30，50，70，88，100。若查找表中元素58，則它將依次與表中 （C）24．對(duì)22個(gè)記錄的有序表作折半查找，當(dāng)查找失敗時(shí)，至少需要次關(guān)D．（A查A．順 B．二分 C．順序，也能二分 D．隨《數(shù)據(jù)結(jié)構(gòu)與算法》一、選擇題 2．?dāng)?shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是指A 在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù) 結(jié)構(gòu)邏 B．C．邏輯和D．物在數(shù)據(jù)時(shí)，通常不僅要各數(shù)據(jù)元素的值，而且還要 C．?dāng)?shù)據(jù)元間的關(guān) D．?dāng)?shù)據(jù)的方在決定選取何種結(jié)構(gòu)時(shí)，一般不考 各結(jié)點(diǎn)的值如 B．結(jié)點(diǎn)個(gè)數(shù)的多C．對(duì)數(shù)據(jù)有哪些運(yùn) D．所用的編程語(yǔ)言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便以下說(shuō)法正確的是 D．一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)算法分析的目的是 ，算法分析的兩個(gè)主要方面是 （2）A．空間復(fù)雜度和時(shí)間復(fù)雜 B．正確性和簡(jiǎn)明C．可讀性和文D．?dāng)?shù)據(jù)復(fù)雜性和程序復(fù)雜下面程序段的時(shí)間復(fù)雜度是 sfor(I=0;i<n;s+=B[i][j];sum=s下面程序段的時(shí)間復(fù)雜度是 for(i=0;i<n;A[i][j]＝0;下面程序段的時(shí)間復(fù)雜度是 i＝0；i=i* D．隊(duì)列的操作方式是先進(jìn)后通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著B數(shù)據(jù)元素具有同一D．?dāng)?shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)鏈表不具備的特點(diǎn) C．不必事先估計(jì)空 D．所需空間與其長(zhǎng)度成正不結(jié)點(diǎn)的單鏈表head為空的判定條件 A．head== Bhead->nextC．head->next D結(jié)點(diǎn)的單鏈表head為空的判定條件是 A．head==NULL Bhead->next==NULLC．head->next==head Dhead!=NULL 方式最節(jié)省運(yùn)算時(shí)間 需要分配較大空間，插入和刪除不需要移動(dòng)元素的線性表，其結(jié)構(gòu) A．單鏈 B．靜態(tài)鏈 C．線性鏈 D．順序結(jié)非空的循環(huán)單鏈表head的尾結(jié)點(diǎn)（由p所指向）滿足 A．p->next==NULL B．p==NULLC．p->next==head D．p==head在循環(huán)雙鏈表的p所指的結(jié)點(diǎn)之前插入s所指結(jié)點(diǎn)的操作是 A．p->prior=s；s->next=p；p->prior->next=s；s->prior=p->priorB．p->prior=s；p->prior->next=s；s->next=p；s->prior=p-C．s->next=p；s->prior=p->prior；p->prior=s；p->prior->next=sD．s->next=p；s->prior=p->prior；p->prior->next=s；p->prior=如果最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū)則采用D方式最節(jié)省時(shí)間單鏈 B．雙鏈 C．單循環(huán)鏈 D．順序在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)并仍然保持有序的時(shí)間復(fù)雜度是B。 在一個(gè)長(zhǎng)度為n（n>1）的單鏈表上，設(shè)有頭和尾兩個(gè)指針，執(zhí)行 B操作與與單鏈表相比，雙鏈表的優(yōu)點(diǎn)之一是D 入新元素，則最好使用B。D．循環(huán)雙鏈≤n+1， A．n–i+ B．n– D．i–對(duì)于只在表的首尾兩端進(jìn)行插入操作的線性表宜采用的結(jié)構(gòu) 順序 B．用頭指針表示的循環(huán)單鏈C．用尾指針表示的循環(huán)單鏈 D．單鏈下述哪一條是順序結(jié)構(gòu)的優(yōu)點(diǎn) A插入運(yùn)算方 B可方便地用于各種邏輯結(jié)構(gòu)的表C密度 D刪除運(yùn)算方下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè) A線性表采用順序，必須占用一片連續(xù)的單B線性表采用順序，便于進(jìn)行插入和刪除操作C線性表采用鏈?zhǔn)?，不必占用一片連續(xù)的單D線性表采用鏈 ，便于進(jìn)行插入和刪除操作線性表是具有n 的有限序列字 B．?dāng)?shù)據(jù)元 C．?dāng)?shù)據(jù) D．表元在n個(gè)結(jié)點(diǎn)的線性表的數(shù)組實(shí)現(xiàn)中算法的時(shí)間復(fù)雜度是（1的操作 第i（1<=i<=n）個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)在第i（1<=i<=n）個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)若長(zhǎng)度為n的線性表采用順序結(jié)構(gòu)，在其第i個(gè)位置插入一個(gè)新元素的算 C。 ，對(duì)于順序的線性表結(jié)點(diǎn)和增加、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度 ，A．O(n) B．O(n) C．O(1) D．O(1)線性表（a1,a2,…,an）以鏈?zhǔn)椒绞?，第i位置元素的時(shí)間復(fù)雜度 單鏈表中，增加一個(gè)頭結(jié)點(diǎn)的目的是為了 使單鏈表至少有一個(gè)結(jié) B．標(biāo)識(shí)表結(jié)點(diǎn)中首結(jié)點(diǎn)的位C．方面運(yùn)算的實(shí) D．說(shuō)明單鏈表是線性表的鏈在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是 B．s->next=p->next；p->next=s; 線性表的順序結(jié)構(gòu)是一種 隨機(jī)存取的結(jié) B．順序存取的結(jié)C．索引存取的結(jié) D．Hash存取的結(jié)棧的特點(diǎn) ，隊(duì)列的特點(diǎn)是 先進(jìn)先 B．先進(jìn)后棧和隊(duì)列的共同點(diǎn)是 一個(gè)棧的進(jìn)棧序列是a，b，c，d，e，則棧的不可能的輸出序列 設(shè)有一個(gè)棧，元素依次進(jìn)棧的順序?yàn)锳、B、C、D、E。下列 以 不是隊(duì)列的基本運(yùn)算從隊(duì)入一個(gè)新元 B．從隊(duì)列中刪除第i個(gè)元C．判斷一個(gè)隊(duì)列是否為 D．隊(duì)頭元素的若已知一個(gè)棧的進(jìn)棧序列是1，2，3，n，其輸出序列為p1，p2，p3，…，pn，若p1＝n，則pi為 D．不確判定一個(gè)順序棧st（最多元素為MaxSize）為空的條件是 st->top!=- B．st->top==-C．st->top!= D．st->top==判定一個(gè)順序棧st（最多元素為MaxSize）為滿的條件是 st->top!=- B．st->top==-C．st->top!= D．st->top==一個(gè)隊(duì)列的入隊(duì)序列是1，2，3，4，則隊(duì)列的輸出序列是 判定一個(gè)循環(huán)隊(duì)列qu（最多元素為MaxSize）為空的條件是 qu->rear–qu->front B．qu->rear–qu--C．qu->rear==qu- D．qu->rear=qu->front-在循環(huán)隊(duì)列中，若front與rear分別表示對(duì)頭元素和隊(duì)尾元素的位置，則判 向一個(gè)棧頂指針為h的結(jié)點(diǎn)的鏈棧中插入指針s所指的結(jié)點(diǎn)時(shí)應(yīng)執(zhí)行操作A．h->next=s B．s->next=hC．s->next=h;h=s D．s->next=h->next;h->next=s輸入序列為ABC，可以變?yōu)镃BA時(shí)，經(jīng)過(guò)的棧操作為 B。 C．push，push，pop， D．push，pop，push，push，pop，若棧采用順序方式，現(xiàn)兩棧共享空間V[1m]，top[1]、top[2]分別B。A．|top[2]-top[1]|=0 B．top[1]+1=top[2] 設(shè)計(jì)一個(gè)判別表達(dá)式中左、右括號(hào)是否配對(duì)出現(xiàn)的算法，采用 數(shù)據(jù)結(jié)最佳線性表的順序結(jié) C．線性表的鏈?zhǔn)浇Y(jié) 允許對(duì)隊(duì)列進(jìn)行的操作有 對(duì)于循環(huán)隊(duì) 若用一個(gè)大小為6的數(shù)值來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為B。和 B．2和 C．4和 D．5和隊(duì)列的“先進(jìn)先出”特性是 最早插入隊(duì)列中的元素總是最后D．每次從隊(duì)列中刪除的總是最早插入的元和順序棧相比，鏈棧有一個(gè)比較明顯的優(yōu)勢(shì)是 通常不會(huì)出現(xiàn)棧滿的情 B．通常不會(huì)出現(xiàn)?？盏那镃．插入操作更容易實(shí) D．刪除操作更容易實(shí)用不結(jié)點(diǎn)的單鏈表隊(duì)列，其頭指針指向隊(duì)頭結(jié)點(diǎn)，尾指針指向隊(duì)尾結(jié)點(diǎn)，則在進(jìn)行出隊(duì)操作時(shí) C 。僅修改隊(duì)頭指 B．僅修改隊(duì)尾指C．隊(duì)頭、隊(duì)尾指針都可能要修 D．隊(duì)頭、隊(duì)尾指針都要修若串S=‘software，其子串的數(shù)目 串的長(zhǎng)度是 串是一種特殊的線性表，其特殊性體現(xiàn)在 可以順序B．?dāng)?shù)據(jù)元素是一個(gè)字C．可以鏈?zhǔn)紻．?dāng)?shù)據(jù)元素可以是多個(gè)字設(shè)有兩個(gè)串p和q，求q在p中首次出現(xiàn)的位置的運(yùn)算稱為 連 B．模式匹 C．求子 D．求串?dāng)?shù)組A中，每個(gè)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)i18，列下標(biāo)j110，從首地址SA開(kāi)始連續(xù)存放的器內(nèi)，該數(shù)組按行存放，元素A[8][5]的起始 C。A．SA＋141B． 數(shù)組A每個(gè)元素的長(zhǎng)度為3字節(jié)，行下標(biāo)i18，列下標(biāo)j110，從首地址SA開(kāi)始連續(xù)存放的器內(nèi)，該數(shù)組按行存放，元素A[5][8]的起始 A．SA＋141B． 若一個(gè)浮點(diǎn)數(shù)數(shù)組如下：froataverage[]=new假設(shè)該數(shù)組的內(nèi)存起始位置為200，average[15]的內(nèi)存地址是 設(shè)二維數(shù)組A[1…m,1…n]按行在數(shù)組B中則二維數(shù)組元素A[i,j]在一維數(shù)組B中的下標(biāo)為 n*(i-1)+jB．n*(i-1)+j- C．i*(j- D．j*m+i-有一個(gè)100×90的稀疏矩陣，非0元素有10，設(shè)每個(gè)整型數(shù)占2個(gè)字節(jié)，則 B． C．18 數(shù)組A[0…4，-1…-3，5…7]中含有的元素個(gè)數(shù)是 B． 對(duì)矩陣進(jìn)行壓縮是為 方便運(yùn)算B．方便C．提高運(yùn)算速 D．減少空設(shè)有一個(gè)10階的對(duì)稱矩陣A，采用壓縮方式，以行序?yàn)橹鳎琣1，1為第一個(gè)元素，其地址為1，每個(gè)元素占1個(gè)地址空間，則a8，5的地址為B。A．13B． 稀疏矩陣一般的壓縮方式有兩種，即C B．三元組和散列 D．散列和十字鏈表樹最適合用來(lái)表 C 深度為5的二叉樹至多 個(gè)結(jié)點(diǎn) B． C． 對(duì)一個(gè)滿二叉樹，m個(gè)葉子，n個(gè)結(jié)點(diǎn)，深度為h，則 A．n= Bh+m= Cm=h- Dn=2h-任何一棵二叉樹的葉子結(jié) 序中序和后序遍歷序列中的相對(duì)次 不發(fā)生改 B．發(fā)生改 C．不能確 D．以上都不索化樹中，每個(gè)結(jié)點(diǎn)必須設(shè)置一個(gè)標(biāo)志來(lái)說(shuō)明它的左、右鏈指向的是樹結(jié)構(gòu)信息，還是線索化信息，若0標(biāo)識(shí)樹結(jié)構(gòu)信息，1右鏈域，應(yīng)標(biāo)識(shí)為D。 在下述論述中，正確的 ①只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0；②二叉樹的度為2；③二叉樹的左右可任意④深度為K的順序二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉 設(shè)森林F對(duì)應(yīng)的二叉樹為B，它有m個(gè)結(jié)點(diǎn)，B的根為p，p的右的結(jié)點(diǎn)個(gè)數(shù)為n，森林F中第一棵樹的結(jié)點(diǎn)的個(gè)數(shù)是 A．m- B．m-n- D．不能若一棵二叉樹具有10度為25度為1則度為0的個(gè)數(shù)是B。 D．不能確具有10個(gè)葉子結(jié)點(diǎn)的二叉樹中 個(gè)度為2的結(jié)點(diǎn) 在一個(gè)無(wú)向圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的C倍 B C D在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的B倍 B C D某二叉樹結(jié)點(diǎn)的中序序列為ABCDEFG，后序序列為BDCAFGE，則其左中結(jié) 已知一算術(shù)表達(dá)式的中綴形式為A＋B*C–D/E，后綴形式為ABC*+DE/–，其 A．– B．– C 已知一個(gè)圖，如圖所示，若從頂點(diǎn)a出發(fā)按深度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為D；按廣度搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為A；abecdabecdf②A．a(chǎn)，b，c，e，d，fB．a(chǎn)，b，c，e，f，dC．a(chǎn)，e，b，c，f，d，采用鄰接表的圖的深度優(yōu)先遍歷算法類似于二叉樹的 先序遍 B．中序遍 C．后序遍 D．按層遍采用鄰接表的圖的廣度優(yōu)先遍歷算法類似于二叉樹的 先序遍 B．中序遍 C．后序遍 D．按層遍具有n個(gè)結(jié)點(diǎn)的連通圖至少 條邊n- B． C．n(n- D．廣義表（a，a）的表C，表尾是C。 B C D廣義表（a）的表頭是C，表尾是B B C D順序查找法適合于結(jié)構(gòu) B的線性表A散列B順序或鏈?zhǔn)紺壓縮D索對(duì)線性表進(jìn)行折半查找時(shí)，要求線性表必須 A以順序方式B以順序方式，且結(jié)點(diǎn)按關(guān)鍵字有序排C以鏈?zhǔn)椒绞紻以鏈?zhǔn)椒绞?，且結(jié)點(diǎn)按關(guān)鍵字有序排采用折半查找法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)度為D。ABCD有一個(gè)有序表｛139123241456275778295100當(dāng)折半查找值為82的結(jié)點(diǎn)時(shí)，C 次比較后查找成功。 B 二叉樹為二叉排序樹的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值小于其右孩子的值。這種說(shuō)法 B 。 正 錯(cuò)下面關(guān)于B樹和B+樹的敘述中，不正確的結(jié)論 AB樹和B+樹都能有效的支持順序查找 BB樹和B+樹都能有效的支持隨機(jī)CB樹和B+樹都是平衡的多叉樹 DB樹和B+樹都可用于文件索引結(jié)以下說(shuō)法錯(cuò)誤的 散列法的思想是由關(guān)鍵字值決定數(shù)據(jù)的地D．散列表的查找效率主要取決于散列表構(gòu)造時(shí)選取的散列函數(shù)和處 的方法查找效率最高的二叉排序樹是 所有結(jié)點(diǎn)的左都為空的二叉排序樹所有結(jié)點(diǎn)的右都為空的二叉排序樹排序方法中，從未排序序列中依次取出元素與已排序序列中的元素進(jìn)行比較將其放入已排序序列的正確位置上的方法，稱為 C 。希爾排 B。冒泡排 C插入排 D。選擇排在所有的排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是 A．希爾排 B．冒泡排 C．直接插入排 D．直接選擇排堆是一種有用的數(shù)據(jù)結(jié)構(gòu)。下列關(guān)鍵碼序 是一個(gè)堆 堆排序是一 排序插 B．選 C．交 D．歸 在鏈表中進(jìn)行操作比在順序表中進(jìn)行操作效率順序查 B．折半查 C．分塊查 D．插直接選擇排序的時(shí)間復(fù)雜度 （n為元素個(gè)數(shù) B．O(log C．O(nlog D． 二、填空題數(shù)據(jù)邏輯結(jié)構(gòu)包括線性結(jié)構(gòu) 、樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)三種類型，樹形結(jié)構(gòu)和圖狀結(jié)構(gòu)合稱非線性結(jié)構(gòu) 數(shù)據(jù)的邏輯結(jié)構(gòu)分 集 、線性結(jié) 、樹形結(jié)構(gòu)和圖狀結(jié)4種．3性結(jié)構(gòu)中，第一個(gè)結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū)結(jié)點(diǎn)；最后一個(gè)結(jié)點(diǎn)后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)．線性結(jié)構(gòu)中元間存在一對(duì)一關(guān)系樹形結(jié)構(gòu)中元間存在一對(duì)多關(guān)系，圖形結(jié)構(gòu)中元間存在多對(duì)多關(guān)系。在樹形結(jié)構(gòu)中，樹根結(jié)點(diǎn)沒(méi)有前驅(qū)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)前驅(qū) 后續(xù)結(jié)點(diǎn)，其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)可以任意多個(gè)。數(shù)據(jù)結(jié)構(gòu)的基本方法是順序、鏈?zhǔn)?索引 散列衡量一個(gè)算法的優(yōu)劣主要考慮正確性、可讀性、健壯性和間復(fù)間復(fù)雜度。評(píng)估一個(gè)算法的優(yōu)劣，通常從時(shí)間復(fù)雜 和空間復(fù)雜 兩個(gè)方面察算法的5要特性是有窮性、確定性、可行性、輸入和輸在一個(gè)長(zhǎng)度為n順序表中刪除第i元素時(shí)，需向前移動(dòng)n-i-1個(gè)元素在單鏈表中，要?jiǎng)h除某一指定的結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的前驅(qū)在雙鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向點(diǎn)，另一個(gè)繼結(jié)點(diǎn)。在順序表中插入或刪除一個(gè)數(shù)據(jù)元素，需要平均移動(dòng)n個(gè)數(shù)據(jù)元素，移動(dòng)數(shù)據(jù)元素的個(gè)數(shù)與位置有關(guān)。當(dāng)線性表的元素總數(shù)基本穩(wěn)定且很少進(jìn)行插入和刪除操作但要求以最快的速度存取線性表的元素是，應(yīng)采用順序 結(jié)構(gòu)。15．根據(jù)線性表的鏈?zhǔn)浇Y(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線性鏈表分成單鏈表 和雙鏈表。16順序結(jié)構(gòu)是通過(guò)下標(biāo) 表示元間的關(guān)系的鏈?zhǔn)浇Y(jié)構(gòu)是通過(guò)指針表示元間的關(guān)系的。17．結(jié)點(diǎn)的循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是L->next- 棧是限定僅在表尾進(jìn)行插入或刪除操作的線性表，其運(yùn)算遵循后進(jìn)先出字符的串，其長(zhǎng)。空白串是由一個(gè)或多個(gè)空格字符組組成串的數(shù)據(jù)元素只能是個(gè)字符一個(gè)字符個(gè)連續(xù)字符構(gòu)成的部分為該串的子子串”strdatastructure的位置是5二維數(shù)組M的每6組成的串，行i08，列下j的范圍從110則存放M540M的第8列和第5108稀疏矩陣一般的壓縮方法有兩種，即元組表和十字廣義表（a（b，c（d）的長(zhǎng)度是3，深度是4在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n0，2結(jié)點(diǎn)的個(gè)n2，則n0＝n2+1在有n個(gè)結(jié)點(diǎn)的二叉鏈表中，空鏈域的個(gè)數(shù)為 一棵有n葉子結(jié)點(diǎn)的哈夫曼樹共有2n-1_個(gè)結(jié)深度為5的二叉樹至多有 個(gè)結(jié)點(diǎn)若某二叉樹有20個(gè)葉子結(jié)點(diǎn)，有30個(gè)結(jié)點(diǎn)僅有一個(gè)孩子，則該二叉樹的總點(diǎn)個(gè)數(shù) 某二叉樹的前序遍歷序abdgcefh，中序序列是dgbaechf，其后序序列為gdbehfca。線索二叉樹的左線索指向其遍歷序列中的前驅(qū) 列中的后繼。在各種查找方法中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查找方法是散列查找 在分塊索引查找方法中首先查 索引 然后查找相應(yīng)的塊表一個(gè)無(wú)序序列可以通過(guò)構(gòu)造一棵二叉排序樹而變成一個(gè)有序具有10個(gè)頂點(diǎn)的無(wú)向圖