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

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