數(shù)據(jù)結(jié)構(gòu)填空選擇

數(shù)據(jù)結(jié)構(gòu)填空選擇數(shù)據(jù)的物理結(jié)構(gòu)包括數(shù)據(jù)元素的表示和數(shù)據(jù)元素關(guān)系的表示。對于給定的n個元素，可以構(gòu)造出的邏輯結(jié)構(gòu)有集合，線性結(jié)構(gòu)，樹形結(jié)構(gòu)，—圖狀結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)—四種。數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的組織形式，即數(shù)據(jù)元素之間邏輯關(guān)系的總體。而邏輯關(guān)系是指數(shù)據(jù)元素之間的關(guān)聯(lián)方式或稱“鄰接關(guān)系”一個數(shù)據(jù)結(jié)構(gòu)在計算機(jī)中的表示（或稱映像）稱為存儲結(jié)構(gòu)（又?jǐn)?shù)據(jù)的物理結(jié)構(gòu)）。抽象數(shù)據(jù)類型的定義僅取決于它的一組—邏輯特性—，而與_在計算機(jī)內(nèi)部如何表示和實(shí)現(xiàn)—無關(guān)，即不論其內(nèi)部結(jié)構(gòu)如何變化，只要它的—數(shù)學(xué)特性—不變，都不影響其外部使用。6.數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標(biāo)是算法的時間復(fù)雜度和空間復(fù)雜度數(shù)據(jù)結(jié)構(gòu)是研討數(shù)據(jù)的—邏輯結(jié)構(gòu)—和—物理結(jié)構(gòu)_，以及它們之間的相互關(guān)系，并對與這種結(jié)構(gòu)定義相應(yīng)的—操作（運(yùn)算）_，設(shè)計出相應(yīng)的—算法。一個算法具有5個特性:有窮性、確定性、可行性，有零個或多個輸入、有一個或多個輸出從一個具有n個結(jié)點(diǎn)的單鏈表中查找其值等于某的結(jié)點(diǎn)時，在查找成功的情況下，需平均比較―C—個元素結(jié)點(diǎn)。A.n/2B.nC.（n+1）/2D.（n-1）/210.線性表的順序存儲結(jié)構(gòu)是一種A的存儲結(jié)構(gòu)。A.隨機(jī)存取B.順序存取C.索引存取D.散列存取17.向一個棧頂指針為h的鏈棧中插入一個結(jié)點(diǎn)時，應(yīng)執(zhí)行B。A.h->ne某t=;B.->ne某t=h;h=;C.->ne某t=h->ne某t;h->ne某t=;D.->ne某t=h;h=h->ne某t;線性表是一種典型的線性—結(jié)構(gòu)。4.要從一個順序表刪除一個元素時，被刪除元素之后的所有元素均需―前移一個位置，移動過程是從前向后依次移動每一個元素。在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過—物理存儲位置決定的；在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過—鏈域的指針值決定的。根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中每個結(jié)點(diǎn)所含指針的個數(shù)，鏈表可分為單鏈表和―雙鏈表;而根據(jù)指針的聯(lián)接方式，鏈表又可分為―非循環(huán)鏈表和循環(huán)鏈表。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是J吏空表和非空表統(tǒng)一；算法處理一致對于一個具有n個結(jié)點(diǎn)的單鏈表，在已知的結(jié)點(diǎn)p后插入一個新結(jié)點(diǎn)的時間復(fù)雜度為__O(1)，在給定值為某的結(jié)點(diǎn)后插入一個新結(jié)點(diǎn)的時間復(fù)雜度為O(n)。對于一個棧作進(jìn)棧運(yùn)算時，應(yīng)先判別棧是否為，作退棧運(yùn)算時，應(yīng)先判別棧是否為，當(dāng)棧中元素為m時，作進(jìn)棧運(yùn)算時發(fā)生上溢，則說明棧的可用最大容量為。為了增加內(nèi)存空間的利用率和減少發(fā)生上溢的可能性，由兩個棧共享一片連續(xù)的內(nèi)存空間時，應(yīng)將兩棧的分別設(shè)在這片內(nèi)存空間的兩端，這樣只有當(dāng)時才產(chǎn)生上溢。棧滿，?？眨琺，棧底，兩個棧的棧頂在?？臻g的某一位置相遇空串與空格字符組成的串的區(qū)別在于（B）。A.沒有區(qū)別B.兩串的長度不相等C.兩串的長度相等D.兩串包含的字符不相同2.一個子串在包含它的主串中的位置是指（D）。子串的最后那個字符在主串中的位置子串的最后那個字符在主串中首次出現(xiàn)的位置C.子串的第一個字符在主串中的位置D.子串的第一個字符在主串中首次出現(xiàn)的位置若REPLACE（S，S1，S2）表示用字符串S2替換字符串S中的子串S1的操作，則對于S="Beijing&Nanjing”，S1="Beijing”，S2二“Shanghai”，REPLACE（S，S1，S2）=（D）。A.“Nanjing&Shanghai”B."Nanjing&Nanjing”C."ShanghaiNanjing”D."Shanghai&Nanjing”計算機(jī)軟件系統(tǒng)中，有兩種處理字符串長度的方法：一種是，第二種是。兩個字符串相等的充要條件是和。3.設(shè)字符串S1二“ABCDEF”，S2二“PQRS”，則運(yùn)算S=CONCAT(SUB(S1,2,LEN(S2)),SUB(S1,LEN(S2),2))后的串值為。串是指o空串是指，空格串是指1.固定長度，設(shè)置長度指針兩個串的長度相等，對應(yīng)位置的字符相等3.“BCDEDE”含n個字符的有限序列(nN0)不含任何字符的串，僅含空格字符的字符串在一個具有n個頂點(diǎn)和e條邊的無向圖的鄰接矩陣中，表示邊存在的元素(又稱為有效元素)的個數(shù)為(D)。A.nB.neC.eD.2e在一個具有n個頂點(diǎn)和e條邊的有向圖的鄰接矩陣中，表示邊存在的元素個數(shù)為(C)。A.nB.neC.eD.2e在一個無權(quán)圖的鄰接表表示中，每個邊結(jié)點(diǎn)至少包含(B)域。A.1B.2C.3D.4若一個圖的頂點(diǎn)集為｛a,b,c,d,e,f｝，邊集為｛(a,b),(a,c),(b,c),(d,e)｝，則該圖含有3個連通分量。對于一個具有n個頂點(diǎn)和e條邊的無向圖，當(dāng)分別采用鄰接矩陣和鄰接表表示時，求任一頂點(diǎn)度數(shù)的時間復(fù)雜度分別為和。12.0（n）,O（e/n）3.假定一棵三叉樹的結(jié)點(diǎn)數(shù)為50，則它的最小高度為（C）。A.3B.4C.5D.67.線索二叉樹是一種（C）結(jié)構(gòu)。A.邏輯B.邏輯和存儲C.物理D.線性8.線索二叉樹中，結(jié)點(diǎn)p沒有左子樹的充要條件是（B）。A.p->lc=NULLB.p->ltag=1C.p->ltag=1且p->lc=NULLD.以上都不對11.欲實(shí)現(xiàn)任意二叉樹的后序遍歷的非遞歸算法而不必使用棧，最佳方案是二叉樹采用（A）存儲結(jié)構(gòu)。三叉鏈表B.廣義表C.二叉鏈表D.順序12.下面敘述正確的是（D）。A.二叉樹是特殊的樹二叉樹等價于度為2的樹C.完全二叉樹必為滿二叉樹。.二叉樹的左右子樹有次序之分任何一棵二叉樹的葉子結(jié)點(diǎn)在先序、中序和后序遍歷序列中的相對次序（A）。A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對設(shè)F是一個森林，B是由F轉(zhuǎn)換得到的二叉樹，F(xiàn)中有n個非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有個。在一棵二叉排序樹上按遍歷得到的結(jié)點(diǎn)序列是一個有序序列。對于一棵具有n個結(jié)點(diǎn)的二叉樹，當(dāng)進(jìn)行鏈接存儲時，其二叉鏈表中的指針域的總數(shù)為個，其中個用于鏈接孩子結(jié)點(diǎn)，個空閑著。11.一棵含有n個結(jié)點(diǎn)的k叉樹，形態(tài)達(dá)到最大深度，—形態(tài)達(dá)到最小深度。13.對于一棵具有n個結(jié)點(diǎn)的二叉樹，采用二叉鏈表存儲時，鏈表中指針域的總數(shù)為個，其中個用于鏈接孩子結(jié)點(diǎn)，個空閑著。哈夫曼樹是指 的二叉樹。15.空樹是指，最小的樹是指。16.二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)有和兩種。17.三叉鏈表比二叉鏈表多一個指向的指針域。18.線索是指線索鏈表中的rtag域值為時，表示該結(jié)點(diǎn)無右孩子，此時域?yàn)橹赶蛟摻Y(jié)點(diǎn)后繼線索的指針。本節(jié)中我們學(xué)習(xí)的樹的存儲