...wd......wd......wd...緒論判斷題數(shù)據(jù)的邏輯構(gòu)造與數(shù)據(jù)元素本身的內(nèi)容和形式無關(guān)?！病獭骋粋€(gè)數(shù)據(jù)構(gòu)造是由一個(gè)邏輯構(gòu)造和這個(gè)邏輯構(gòu)造上的一個(gè)基本運(yùn)算集構(gòu)成的整體?！病獭硵?shù)據(jù)元素是數(shù)據(jù)的最小單位。〔×〕數(shù)據(jù)的邏輯構(gòu)造和數(shù)據(jù)的存儲(chǔ)構(gòu)造是一樣的?！病痢吵绦蚝退惴ㄔ敲瓷蠜]有區(qū)別，所以在討論數(shù)據(jù)構(gòu)造時(shí)可以通用。〔×〕從邏輯關(guān)系上講，數(shù)據(jù)構(gòu)造主要分為線性構(gòu)造和非線性構(gòu)造兩類?！病獭硵?shù)據(jù)的存儲(chǔ)構(gòu)造是數(shù)據(jù)的邏輯構(gòu)造的存儲(chǔ)映象?！病獭硵?shù)據(jù)的物理構(gòu)造是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)實(shí)際的存儲(chǔ)形式?！病獭硵?shù)據(jù)的邏輯構(gòu)造是依賴于計(jì)算機(jī)的?！病痢乘惴ㄊ菍?duì)解題方法和步驟的描述?！病獭扯?、填空題數(shù)據(jù)有邏輯構(gòu)造和存儲(chǔ)構(gòu)造兩種構(gòu)造。數(shù)據(jù)邏輯構(gòu)造除了集合以外，還包括線性構(gòu)造、樹形構(gòu)造和圖形構(gòu)造。數(shù)據(jù)構(gòu)造按邏輯構(gòu)造可分為兩大類，它們是線性構(gòu)造和非線性構(gòu)造。樹形構(gòu)造和圖形構(gòu)造合稱為非線性構(gòu)造。在樹形構(gòu)造中，除了樹根結(jié)點(diǎn)以外，其余每個(gè)結(jié)點(diǎn)只有1個(gè)前驅(qū)結(jié)點(diǎn)。在圖形構(gòu)造中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后繼結(jié)點(diǎn)數(shù)可以任意多個(gè)。數(shù)據(jù)的存儲(chǔ)構(gòu)造又叫物理構(gòu)造。數(shù)據(jù)的存儲(chǔ)構(gòu)造形式包括順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列存儲(chǔ)。線性構(gòu)造中的元素之間存在一對(duì)一的關(guān)系。樹形構(gòu)造中的元素之間存在一對(duì)多的關(guān)系。圖形構(gòu)造的元素之間存在多對(duì)多的關(guān)系。數(shù)據(jù)構(gòu)造主要研究數(shù)據(jù)的邏輯構(gòu)造、存儲(chǔ)構(gòu)造和算法〔或運(yùn)算〕3個(gè)方面的內(nèi)容。數(shù)據(jù)構(gòu)造被定義為〔D，R〕，其中D是數(shù)據(jù)的有限集合，R是D上的關(guān)系有限集合。算法是一個(gè)有窮指令的集合。算法效率的度量可以分為事先估算法和事后統(tǒng)計(jì)法。一個(gè)算法的時(shí)間復(fù)雜度是算法輸入規(guī)模的函數(shù)。算法的空間復(fù)雜度是指該算法所消耗的存儲(chǔ)空間，它是該算法求解問題規(guī)模的n的函數(shù)。假設(shè)一個(gè)算法中的語句頻度之和為T(n)=6n+3nlog2n,那么算法的時(shí)間復(fù)雜度為O〔nlog2n〕。假設(shè)一個(gè)算法的語句頻度之和為T(n)=3n+nlog2+n2,那么算法的時(shí)間復(fù)雜度為O〔n2〕。數(shù)據(jù)構(gòu)造是一門研究非數(shù)值計(jì)算的程序問題中計(jì)算機(jī)的操作對(duì)象，以及它們之間的關(guān)系和運(yùn)算的學(xué)科。三、選擇題數(shù)據(jù)構(gòu)造通常是研究數(shù)據(jù)的〔A〕及它們之間的相互關(guān)系。A．存儲(chǔ)構(gòu)造和邏輯構(gòu)造B．存儲(chǔ)和抽象C．聯(lián)系和抽象D．聯(lián)系與邏輯在邏輯上可以把數(shù)據(jù)構(gòu)造分成〔C〕。A．動(dòng)態(tài)構(gòu)造和靜態(tài)構(gòu)造B．緊湊構(gòu)造和非緊湊構(gòu)造C．線性構(gòu)造和非線性構(gòu)造D．內(nèi)部構(gòu)造和外部構(gòu)造。數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)內(nèi)表示時(shí)，物理地址和邏輯地址一樣并且是連續(xù)的，稱之為〔C〕。A．存儲(chǔ)構(gòu)造B．邏輯構(gòu)造C．順序存儲(chǔ)構(gòu)造D．鏈?zhǔn)酱鎯?chǔ)構(gòu)造非線性構(gòu)造中的每個(gè)結(jié)點(diǎn)〔D〕。A．無直接前驅(qū)結(jié)點(diǎn)．B．無直接后繼結(jié)點(diǎn)．C．只有一個(gè)直接前驅(qū)結(jié)點(diǎn)和一個(gè)直接后繼結(jié)點(diǎn)D．可能有多個(gè)直接前驅(qū)結(jié)點(diǎn)和多個(gè)直接后繼結(jié)點(diǎn)鏈?zhǔn)酱鎯?chǔ)構(gòu)造所占存儲(chǔ)空間〔A〕。A．分兩局部，一局部存放結(jié)點(diǎn)的值，另一個(gè)局部存放表示結(jié)點(diǎn)間關(guān)系的指針。B．只有一局部，存放結(jié)點(diǎn)的值。C．只有一局部，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針。D．分兩局部，一局部存放結(jié)點(diǎn)的值，另一局部存放結(jié)點(diǎn)所占單元素算法的計(jì)算量大小稱為算法的〔C〕。A．現(xiàn)實(shí)性B．難度C．時(shí)間復(fù)雜性D．效率數(shù)據(jù)的基本單位〔B〕。A．?dāng)?shù)據(jù)構(gòu)造B．?dāng)?shù)據(jù)元素C．?dāng)?shù)據(jù)項(xiàng)D．文件每個(gè)結(jié)點(diǎn)只含有一個(gè)數(shù)據(jù)元素，所有存儲(chǔ)結(jié)點(diǎn)相繼存放在一個(gè)連續(xù)的存儲(chǔ)空間里，這種存儲(chǔ)構(gòu)造稱為〔A〕構(gòu)造。A．順序構(gòu)造B．鏈?zhǔn)綐?gòu)造C．索引構(gòu)造D．散列構(gòu)造每一個(gè)存儲(chǔ)結(jié)點(diǎn)不僅含有一個(gè)數(shù)據(jù)元素，還包含一組指針，該存儲(chǔ)方式是〔B〕。A．順序B．鏈?zhǔn)紺．索引D．散列以下任何兩個(gè)結(jié)點(diǎn)之間都沒有邏輯關(guān)系的是〔D〕。A．圖形構(gòu)造B．線性構(gòu)造C．樹形構(gòu)造D．集合在數(shù)據(jù)構(gòu)造中，與所使用的計(jì)算機(jī)無關(guān)的是〔C〕。A．物理構(gòu)造B．存儲(chǔ)構(gòu)造C．邏輯構(gòu)造D．邏輯和存儲(chǔ)構(gòu)造以下4種基本邏輯構(gòu)造中，數(shù)據(jù)元素之間關(guān)系最弱的是〔A〕。A．集合B．線性構(gòu)造C．樹形構(gòu)造D．圖形構(gòu)造與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無關(guān)的是數(shù)據(jù)的〔A〕。A．邏輯構(gòu)造B．存儲(chǔ)構(gòu)造C．邏輯實(shí)現(xiàn)D．存儲(chǔ)實(shí)現(xiàn)每一個(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)紺．索引D．散列算法能正確的實(shí)現(xiàn)預(yù)定功能的特性稱為算法的〔A〕。A．正確性B．易讀性C．強(qiáng)健性D．高效性算法在發(fā)生非法操作時(shí)可以作出相應(yīng)處理的特性稱為算法的〔C〕。A．正確性B．易讀性C．強(qiáng)健性D．高效性以下時(shí)間復(fù)雜度中最壞的是〔D〕。A．O〔1〕B.O〔n〕C.O(log2n)D.O(n2)以下算法的時(shí)間復(fù)雜度是〔D〕。for(i=0;i<n;i++)for(j=o;i<n;j++)c[i][j]=i+j;A．O〔1〕B.O〔n〕C.(log2n)D.O(n2)算法分析的兩個(gè)主要方面是〔A〕。A.空間復(fù)雜性和時(shí)間復(fù)雜性B.正確性和簡明性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性計(jì)算機(jī)算法必須具備輸入、輸出和〔C〕。A.計(jì)算方法B.排序方法C.解決問題的有限運(yùn)算步驟D.程序設(shè)計(jì)方法第2章線性表一、判斷題線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造優(yōu)于順序存儲(chǔ)。〔×〕鏈表的每個(gè)結(jié)點(diǎn)都恰好包含一個(gè)指針域?！病痢吃诰€性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定緊鄰?！病獭稠樞虼鎯?chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，插入、刪除效率高。〔×〕線性鏈表的刪除算法簡單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算時(shí)機(jī)自動(dòng)地將后續(xù)的各個(gè)單元向前移動(dòng)?！病痢稠樞虮淼拿總€(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型?！病痢尘€性表鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是可以用一組任意的存儲(chǔ)單元存儲(chǔ)表中的數(shù)據(jù)元素?！病獭尘€性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元?！病獭稠樞虮順?gòu)造適宜進(jìn)展順序存取，而鏈表適宜進(jìn)展隨機(jī)存取?！病痢巢迦牒蛣h除操作是數(shù)據(jù)構(gòu)造中是最基本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用?！病痢扯?、填空題順序表中邏輯上相鄰的元素在物理位置上必須相鄰。線性表中結(jié)點(diǎn)的集合是有限的，結(jié)點(diǎn)間的關(guān)系是一對(duì)一關(guān)系。順序表相對(duì)于鏈表的優(yōu)點(diǎn)是節(jié)省存儲(chǔ)和隨機(jī)存取。鏈表相對(duì)于順序表的優(yōu)點(diǎn)是插入、刪除方便。當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)展插入和刪除操作，但要求以最快速度存取線性表中的元素時(shí)，應(yīng)采用順序存儲(chǔ)構(gòu)造。順序表中訪問任意一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度均為O〔1〕。鏈表相對(duì)于順序表的優(yōu)點(diǎn)是插入、刪除方便；缺點(diǎn)是存儲(chǔ)密度小。在雙向鏈表中要?jiǎng)h除結(jié)點(diǎn)*P，其時(shí)間復(fù)雜度為O〔1〕。在單向鏈表中要在結(jié)點(diǎn)*P之前插入一個(gè)新結(jié)點(diǎn)，需找到*P的直接前驅(qū)結(jié)點(diǎn)的地址，其查找的時(shí)間復(fù)雜度為O(n)。在單向鏈表中需知道頭指針才能遍歷整個(gè)鏈表。線性表中第一個(gè)結(jié)點(diǎn)沒有直接前驅(qū)，稱為開場結(jié)點(diǎn)。在一個(gè)長度為n的順序表中刪除第i個(gè)元素，要移動(dòng)n-i個(gè)元素。在一個(gè)長度為n的順序表中，如果要在第i個(gè)元素前插入一個(gè)元素，要后移n-i+1個(gè)元素。在無頭結(jié)點(diǎn)的單向鏈表中，第一個(gè)結(jié)點(diǎn)的地址存放在頭指針中，而其他結(jié)點(diǎn)的存儲(chǔ)地址存放在前趨結(jié)點(diǎn)的指針域中。線性表的元素總數(shù)不確定，且經(jīng)常需要進(jìn)展插入和刪除操作，應(yīng)采用鏈子存儲(chǔ)構(gòu)造。在線性表中的鏈?zhǔn)酱鎯?chǔ)中，元素之間的邏輯關(guān)系是通過指針決定。在雙向鏈表中，每個(gè)結(jié)點(diǎn)都有兩個(gè)指針域，它們一個(gè)指向其前趨結(jié)點(diǎn)，另一個(gè)指向其后繼結(jié)點(diǎn)。對(duì)一個(gè)需要經(jīng)常進(jìn)展插入和刪除操作的線性表，采用鏈?zhǔn)酱鎯?chǔ)構(gòu)造為宜。雙向鏈表中，設(shè)P是指向其中待刪除的結(jié)點(diǎn)，那么需要執(zhí)行的操作為p->prior->next=p->next；p->next->prior=p->prior在如以下列圖的鏈表中，假設(shè)在指針P所在的結(jié)點(diǎn)之后插入數(shù)據(jù)域值為a和b的兩個(gè)結(jié)點(diǎn)，那么可用語句S->next->next=p->next和P->next=S；來實(shí)現(xiàn)該操作。p∧abs選擇題在具有n個(gè)結(jié)點(diǎn)的單向鏈表中，實(shí)現(xiàn)〔A〕的操作，其算法的時(shí)間復(fù)雜度都是O(n).A.遍歷鏈表或求鏈表的第i個(gè)結(jié)點(diǎn)B.在地址為P的結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)C.刪除開場結(jié)點(diǎn)D.刪除地址為P的結(jié)點(diǎn)的后繼結(jié)點(diǎn)設(shè)a、b、c為3個(gè)結(jié)點(diǎn)，p、10、20分別代表它們的地址，那么如下的存儲(chǔ)構(gòu)造稱為〔B〕。pa10b20c∧A．循環(huán)鏈表B．單向鏈表C．雙向循環(huán)鏈表D．雙向鏈表單向鏈表的存儲(chǔ)密度〔C〕。A.大于1B.等于1C.小于1D.不能確定一個(gè)順序存儲(chǔ)的線性表，設(shè)每個(gè)結(jié)點(diǎn)占m個(gè)存儲(chǔ)單元，假設(shè)第一個(gè)結(jié)點(diǎn)的地址為B，那么第i個(gè)結(jié)點(diǎn)的地址為〔A〕。A.B+(i-1)×mB.B+i×mC.B-i×mD.B+(i+1)×m在有n個(gè)結(jié)點(diǎn)的順序表上做插入、刪除結(jié)點(diǎn)運(yùn)算的時(shí)間復(fù)雜度為〔B〕。A．O〔1〕B.O〔n〕C.O(n2)D.O(log2n)設(shè)front、rear分別為循環(huán)雙向鏈表結(jié)點(diǎn)的左指針和右指針，那么指針P所指的元素是雙循環(huán)鏈表L的尾元素的條件是〔D〕。A.P==LB.P->front==LC.P==NULLD.P->rear==L兩個(gè)指針P和Q，分別指向單向鏈表的兩個(gè)元素，P所指元素是Q所指元素前驅(qū)的條件是〔B〕A．P->next==Q->nextB.P->next==QC.Q->next==PD.P==Q用鏈表存儲(chǔ)的線性表，其優(yōu)點(diǎn)是〔C〕。A．便于隨機(jī)存取B．花費(fèi)的存儲(chǔ)空間比順序表少C．便于插入和刪除D．?dāng)?shù)據(jù)元素的物理順序與邏輯順序一樣在單鏈表中，增加頭結(jié)點(diǎn)的目的是〔C〕。A．使單鏈表至少有一個(gè)結(jié)點(diǎn)B．標(biāo)志表中首結(jié)點(diǎn)的位置C．方便運(yùn)算的實(shí)現(xiàn)D．說明該單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)構(gòu)造下面關(guān)于線性表的表達(dá)中，錯(cuò)誤的選項(xiàng)是〔D〕關(guān)系。A．順序表必須占一片地址連續(xù)的存儲(chǔ)單元B．順序表可以隨機(jī)存取任一元素C．鏈表不必占用一片地址連續(xù)的存儲(chǔ)單元D．鏈表可以隨機(jī)存取任一元素L是線性表，LengthList(L)的值是5，經(jīng)DelList(L，2)運(yùn)算后，LengthList(L)的值是〔C〕。A．2B．3C．4D．5單向鏈表的示意圖如下：LABCD∧PQR指向鏈表Q結(jié)點(diǎn)的前驅(qū)的指針是〔B〕。A．LB．PC．QD．R設(shè)p為指向單循環(huán)鏈表上某結(jié)點(diǎn)的指針，那么*p的直接前驅(qū)〔C〕。A．找不到B．查找時(shí)間復(fù)雜度為O〔1〕C．查找時(shí)間復(fù)雜度為O〔n〕D．查找結(jié)點(diǎn)的次數(shù)約為n等概率情況下，在有n個(gè)結(jié)點(diǎn)的順序表上做插入結(jié)點(diǎn)運(yùn)算，需平均移動(dòng)結(jié)點(diǎn)的數(shù)目為〔8〕。A．nB.(n-1)/2C.n/2D.(n+1)/2在以下鏈表中不能從當(dāng)前結(jié)點(diǎn)出發(fā)訪問到其余各結(jié)點(diǎn)的是〔C〕。A.雙向鏈表B.單循環(huán)鏈表C.單向鏈表D.雙向循環(huán)鏈表在順序表中，只要知道〔D〕，就可以求出任一結(jié)點(diǎn)的存儲(chǔ)地址。A.基地址B.結(jié)點(diǎn)大小C.向量大小D.基地址和結(jié)點(diǎn)大小在雙向鏈表中做插入運(yùn)算的時(shí)間復(fù)雜度為〔A〕。A．O〔1〕B.O〔n〕C.O(n2)D.O(log2n)鏈表不具備的特點(diǎn)是〔A〕。A．隨機(jī)訪問B.不必事先估計(jì)存儲(chǔ)空間C.插入刪除時(shí)不需要移動(dòng)元素D.所需空間與線性表成正比以下關(guān)于線性表的論述，不正確的為〔C〕。A.線性表中的元素可以是數(shù)字、字符、記錄等不同類型B.線性順序表中包含的元素個(gè)數(shù)不是任意的C.線性表中的每個(gè)結(jié)點(diǎn)都有且僅有一個(gè)直接前驅(qū)和一個(gè)直接后繼D.存在這樣的線性表，即表中沒有任何結(jié)點(diǎn)在〔B〕的運(yùn)算中，使用順序表比鏈表好。A.插入B.根據(jù)序號(hào)查找C.刪除D.根據(jù)元素查找第3章棧判斷題棧是運(yùn)算受限制的線性表?！病獭吃跅？盏那闆r下，不能作出棧操作，否那么產(chǎn)生下溢。〔√〕棧一定是順序存儲(chǔ)的線性構(gòu)造。〔×〕棧的特點(diǎn)是“后進(jìn)先出〞?！病獭晨諚＞褪撬性囟紴?的棧?！病痢吃贑〔或C++〕語言中設(shè)順序棧的長度為MAXLEN，那么top=MAXLEN時(shí)表示棧滿。〔×〕鏈棧與順序棧相比，其特點(diǎn)之一是通常不會(huì)出現(xiàn)棧滿的情況?！病獭骋粋€(gè)棧的輸入序列為：A，B，C，D，可以得到輸出序列：C，A，B，D?！病痢尺f歸定義就是循環(huán)定義?！病痢硨⑹M(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)是棧的典型應(yīng)用之一。〔√〕二、填空題在棧構(gòu)造中，允許插入、刪除的一端稱為棧頂。在順序棧中，當(dāng)棧頂指針top=-1時(shí)，表示棧空。在有n個(gè)元素的棧中，進(jìn)棧操作時(shí)間復(fù)雜度為O〔1〕。在棧中，出棧操作時(shí)間復(fù)雜度為O〔1〕。表達(dá)式，求它的后綴表達(dá)式是棧的典型應(yīng)用。在一個(gè)鏈棧中，假設(shè)棧頂指針等于NULL，那么表示棧空。向一個(gè)棧頂指針為top的鏈棧插入一個(gè)新結(jié)點(diǎn)*p時(shí)，應(yīng)執(zhí)行p->next=top;top=p；操作。順序棧S存儲(chǔ)在數(shù)組S->data[0…MAXLEN-1]中，進(jìn)棧操作時(shí)要執(zhí)行的語句有：S->top++。(或S->top+1)S->data[S->top]=x鏈棧LS，指向棧頂元素的指針是LS->next。從一個(gè)棧刪除元素時(shí)，首先取出棧頂元素，然后再移動(dòng)棧頂指針。由于鏈棧的操作只在鏈表的頭部進(jìn)展，所以沒有必要設(shè)置頭結(jié)點(diǎn)。順序棧S，在對(duì)S進(jìn)棧操作之前首先要判斷棧是否滿。順序棧S，在對(duì)S出棧操作之前首先要判斷棧是否空。假設(shè)內(nèi)在空間充足，鏈?？梢圆欢x棧滿運(yùn)算。鏈棧LS為空的條件是LS->next=NULL。鏈棧LS的棧頂元素是鏈表的首元素。同一棧的各元素的類型一樣。假設(shè)進(jìn)棧的次序是A、B、C、D、E，執(zhí)行3次出棧操作以后，棧頂元素為B。A+B/C-D*E的后綴表達(dá)式是ABC/+DE*-。4個(gè)元素A、B、C、D順序進(jìn)S棧，執(zhí)行兩次Pop(S,x)運(yùn)算后，x的值是C。三、選擇題插入和刪除操作只能在一端進(jìn)展的線性表，稱為〔C〕。A．隊(duì)列B．循環(huán)隊(duì)列C．棧D．循環(huán)棧設(shè)有編號(hào)為1，2。3，4的4輛列車，順序進(jìn)入一個(gè)棧構(gòu)造的站臺(tái)，以下不可能的出站順序?yàn)椤睤〕。A．1234B．1243C．1324D．1423如果以鏈表作為棧的存儲(chǔ)構(gòu)造，那么出棧操作時(shí)〔B〕。A．必須判別棧是否滿B．必須判別棧是否為空C．必須判別棧元素類型D．?？刹蛔鋈魏闻袆e元素A、B、C、D依次進(jìn)棧以后，棧頂元素是〔D〕A．AB．BC．CD．D順序棧存儲(chǔ)空間的實(shí)現(xiàn)使用〔B〕存儲(chǔ)元素。A．鏈表B．?dāng)?shù)組C．循環(huán)鏈表D．變量在C〔或C++〕語言中，一個(gè)順序棧一旦被聲明，其占用空間的大小〔A〕。A．已固定B．不固定C．可以改變D．動(dòng)態(tài)變化帶頭結(jié)點(diǎn)的鏈棧LS的示意圖如下，棧頂元素是〔A〕。LSHABCD∧A．AB．BC．CD．D鏈棧與順序棧相比，有一個(gè)比較明顯的優(yōu)點(diǎn)是〔B〕。插入操作更加方便B.通常不會(huì)出現(xiàn)棧滿的情況C.不會(huì)出現(xiàn)?？盏那闆rD.刪除操作更加方便從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪除的結(jié)點(diǎn)，應(yīng)執(zhí)行以下〔d〕命令。A．x=top;top->next;B.top=top->next;x=top->dataC.x=top->data;D.x=top->data;top=top->next在一個(gè)棧頂指針為HS的鏈棧中，將一個(gè)S指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行以下〔B〕命令。A.HS->next=SB.S->next=HS->next;HS->next=S;C.S->next=HS->next;HS=S;D.S->next=HS=HS->next4元素按A、B、C、D順序進(jìn)S棧，執(zhí)行兩次Pop(S，x)運(yùn)算后，棧頂元素的值是〔B〕。A．AB．BC．CD．D元素A、B、C、D依次進(jìn)棧以后，棧底元素是〔A〕。A．AB．BC．CD．D經(jīng)過以下棧的運(yùn)算后，再執(zhí)行ReadTop(s)的值是〔A〕。InitStack(s);Push(s，a);Push(s，b);Pob(s);aB.bC.1D.0經(jīng)過以下棧的運(yùn)算后，x的值是〔B〕。InitStack(s)〔初始化棧〕;Push(s，a);Push(s，b);ReadTop(s)；Pob(s，x);aB.bC.1D.0經(jīng)過以下棧的運(yùn)算后，x的值是〔B〕。InitStack(s)〔初始化?！?Push(s,a);Pob(s，x);Push(s,b);Pob(s，x);A.aB.bC.1D.0經(jīng)過以下棧的運(yùn)算后,SEmpty(s)的值是〔C〕。InitStack(s)〔初始化?！?Push(s,a);Push(s,b);Pob(s，x);Pob(s，x);A.aB.bC.1D.0向順序棧中輸入元素時(shí)〔B〕。A．先存入元素，后移動(dòng)棧頂指針B．先移動(dòng)棧頂指針，后存入元素C．誰先誰后無關(guān)緊要D．同時(shí)進(jìn)展初始化一個(gè)空間大小為5的順序棧S后，S->top的值是〔B〕。A．0B．-1C．不再改變D．動(dòng)態(tài)變化設(shè)有一個(gè)入棧的次序A、B、C、D、E，那么棧不可能的輸出序列是〔C〕。A．EDCBAB．DECBAC．DCEABD．ABCDE設(shè)有一個(gè)順序棧S，元素A、B、C、D、E、F依次進(jìn)棧，如果6個(gè)元素出棧的順序是B、D、C、F、E、A，那么棧的容量至少應(yīng)是〔A〕。A．3B．4C．5D．6第4章隊(duì)列一、判斷題隊(duì)列是限制在兩端進(jìn)展操作的線性表?！病獭撑袛囗樞蜿?duì)列為空的標(biāo)準(zhǔn)是頭指針和尾指針都指向同一個(gè)結(jié)點(diǎn)。〔√〕在鏈隊(duì)列上做出隊(duì)操作時(shí)，會(huì)改變front指針的值?！病痢吃谘h(huán)隊(duì)列中，假設(shè)尾指針rear大于頭指針front，其元素個(gè)數(shù)為rear-front。〔√〕在單向循環(huán)鏈表中，假設(shè)頭指針為h，那么p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是p=h?！病痢虫滉?duì)列在一定范圍內(nèi)不會(huì)出現(xiàn)隊(duì)滿的情況。〔√〕在循環(huán)鏈隊(duì)列中無溢出現(xiàn)象?！病痢硹：完?duì)列都是順序存儲(chǔ)的線性構(gòu)造?！病痢吃陉?duì)列中允許刪除的一端稱為隊(duì)尾?！病痢稠樞蜿?duì)和循環(huán)隊(duì)關(guān)于隊(duì)滿和隊(duì)空的判斷條件是一樣的?！病痢扯?、填空題在隊(duì)列中存取數(shù)據(jù)應(yīng)遵循的原那么是先進(jìn)先出。隊(duì)列是被限定為只能在表的一端進(jìn)展插入運(yùn)算，在表的另一端進(jìn)展刪除運(yùn)算線性表。在隊(duì)列中，允許插入的一端稱為隊(duì)尾。在隊(duì)列中，允許刪除的一端稱為隊(duì)首〔或隊(duì)頭〕。隊(duì)列在進(jìn)展出隊(duì)操作時(shí)，首先要判斷隊(duì)列是否為空。順序隊(duì)列在進(jìn)展入隊(duì)操作時(shí)，首先在判斷隊(duì)列是否為滿。順序隊(duì)列初始化后，初始化后，front=rear=-1。解決順序隊(duì)列“假溢出〞的方法是采用循環(huán)隊(duì)列。循環(huán)隊(duì)列的隊(duì)指針為front，隊(duì)尾指針為rear，那么隊(duì)空的條件為front==rear。鏈隊(duì)列LQ為空時(shí)，LQ->front->next=NULL。設(shè)長度為n的鏈隊(duì)列用單循環(huán)表表示，假設(shè)只設(shè)頭指針，那么入隊(duì)操作的時(shí)間復(fù)雜度為O(n)。設(shè)長度為n的鏈隊(duì)列用單循環(huán)表表示，假設(shè)只設(shè)尾指針，那么入隊(duì)操作的時(shí)間復(fù)雜度為O(1)。在一個(gè)鏈隊(duì)列中，假設(shè)隊(duì)首指針與隊(duì)尾指針的值一樣，那么表示該隊(duì)列為空。設(shè)循環(huán)隊(duì)列的頭指針front指向隊(duì)首元素，尾指針rear指向隊(duì)尾元素后的一個(gè)空閑元素，隊(duì)列的最大空間為MAXLEN，那么隊(duì)滿標(biāo)志為front==(rear+1)%MAXLEN。在一個(gè)鏈隊(duì)列中，假設(shè)隊(duì)首指針為front，隊(duì)尾指針為rear，那么判斷隊(duì)列只有一個(gè)結(jié)點(diǎn)的條件為front==rear或front!。向一個(gè)循環(huán)隊(duì)列中插入元素時(shí)，首先要判斷隊(duì)尾指針，然后再向指針?biāo)傅奈恢脤懭胄碌臄?shù)據(jù)。讀隊(duì)首元素的操作不改變或不影響隊(duì)列元素的個(gè)數(shù)。設(shè)循環(huán)隊(duì)列的容量為40〔序號(hào)0～39〕，現(xiàn)經(jīng)過一系列的入隊(duì)和出隊(duì)的運(yùn)算后，front=11，rear=19，那么循環(huán)隊(duì)列中還有8個(gè)元素。隊(duì)列Q，經(jīng)過以下運(yùn)算：InitQueue(Q)(初始化隊(duì)列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)；ReadFront(Q,x)；QEmpty(Q)；后的值是8。隊(duì)列Q經(jīng)過InitQueue(Q)(初始化隊(duì)列)；InQueue(Q,a)；InQueue(Q,b)；ReadFront(Q,x)后，x的值是a。三、選擇題隊(duì)列是限定在〔D〕進(jìn)展操作的線性表。A．中間者B.隊(duì)首C.隊(duì)尾D.端點(diǎn)隊(duì)列中的元素個(gè)數(shù)是〔B〕。A．不變的B.可變的C.任意的D.0同一隊(duì)列內(nèi)的各元素的類型〔A〕。A.必須一致B.不能一致C.可以不一致D.不限制隊(duì)列是一個(gè)〔C〕線性表構(gòu)造。A.不加限制的B.推廣了的C.加了限制的D.非當(dāng)利用大小為n的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最后一個(gè)元素的下標(biāo)為〔B〕。A.n-2B.n-1C.nD.n+1一個(gè)循環(huán)隊(duì)列一旦說明，其占用空間的大小〔A〕。A.已固定B.可以變動(dòng)C.不能固定D.動(dòng)態(tài)變化循環(huán)隊(duì)列占用的空間〔A〕。A.必須連續(xù)B.不必連續(xù)C.不能連續(xù)D.可以不連續(xù)存放循環(huán)隊(duì)列元素的數(shù)組data有10個(gè)元素，那么data數(shù)組的下標(biāo)范圍是〔B〕。A.0～10B.0～9C.1～9D.1～10假設(shè)進(jìn)隊(duì)的序列為A、B、C、D，那么出隊(duì)的序列是〔C〕。A.B、C、D、AB.A、C、B、DC.A、B、C、DD.C、B、D、A4個(gè)元素按A、B、C、D順序連續(xù)進(jìn)隊(duì)Q，那么隊(duì)尾元素是〔D〕A．AB．BC．CD．D4個(gè)元素按A、B、C、D順序連續(xù)進(jìn)隊(duì)Q，執(zhí)行一次QutQueue(Q)操作后，隊(duì)頭元素是〔B〕。A.AB.BC.CD.D4個(gè)元素按A、B、C、D順序連續(xù)進(jìn)隊(duì)Q，執(zhí)行4次QutQueue(Q)操作后，再執(zhí)行QEmpty(Q)；后的值是〔B〕。A.0B.1C.2D.3隊(duì)列Q，經(jīng)過以下運(yùn)算后，x的值是〔B〕。InitQueue(Q)(初始化隊(duì)列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)；ReadFront(Q,x)；A.aB.bC.0D.1循環(huán)隊(duì)列SQ隊(duì)滿的條件是〔B〕。A.SQ->rear==SQ->frontB.(SQ->rear+1)%MAXLEN==SQ->frontC.SQ->rear==0D.SQ->front==0設(shè)鏈棧中結(jié)點(diǎn)的構(gòu)造：data為數(shù)據(jù)域，next為指針域，且top是棧頂指針，假設(shè)想在鏈棧的棧頂插入一個(gè)由指針s所指的結(jié)點(diǎn)，那么應(yīng)執(zhí)行以下〔A〕操作。A.s->next=top->next;top->next=s;B.top->next=s;C.s->next=top;top->next;D.s->next=top;top=s;帶頭結(jié)點(diǎn)的鏈隊(duì)LQ示意圖如下，鏈隊(duì)列的隊(duì)頭元素是〔A〕。LQ->frontHABCD∧LQ->rearA．AB．BC．CD．D帶頭結(jié)點(diǎn)的鏈隊(duì)列LQ示意圖如下，指向鏈隊(duì)列的隊(duì)頭指針是〔C〕。LQ->frontHABCD∧LQ->rearA.LQ->frontB.LQ->rearC.LQ->front->nextD.LQ->rear->next帶頭結(jié)點(diǎn)的鏈隊(duì)列LQ示意圖如下,在進(jìn)展進(jìn)隊(duì)的運(yùn)算時(shí)指針LQ->frnot(A).LQ->frontHABCD∧LQ->rearA.始終不改變B.有時(shí)改變C.進(jìn)隊(duì)時(shí)改變D.出隊(duì)時(shí)改變19.隊(duì)列Q，經(jīng)過以下運(yùn)算后，再執(zhí)行QEmpty(Q)的值是〔C〕。InitQueue(Q)(初始化隊(duì)列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)；ReadQueue(Q,x)；A.aB.bC.0D.120.假設(shè)用一個(gè)大小為6數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前front和rear的值分別為3和0，當(dāng)從隊(duì)列中刪除一個(gè)元素，再參加兩個(gè)元素后，front和rear的值分別為〔B〕。A.5和1B.4和2C.2和4D.1和5第5章串一、判斷題串是n個(gè)字母的有限序列?！病痢炒臄?shù)據(jù)元素是一個(gè)字符?！病獭炒拈L度是指串中不同字符的個(gè)數(shù)?！病痢橙绻麅蓚€(gè)串含有一樣的字符，那么說明它們相等。〔×〕如果一個(gè)串中所有的字母均在另一個(gè)串中出現(xiàn)，那么說明前者是后者的子串?！病痢炒亩逊峙浯鎯?chǔ)是一種動(dòng)態(tài)存儲(chǔ)構(gòu)造?！病獭场癉T〞是“DATA〞的子串?！病痢炒腥我鈧€(gè)字符組成的子序列稱為該串的子串?！病痢匙哟亩ㄎ贿\(yùn)算稱為模式匹配?！病獭吃阪湸袨榱颂岣叽鎯?chǔ)密度，應(yīng)該增大結(jié)點(diǎn)的大小。〔√〕二、填空題由零個(gè)或多個(gè)字符組成的有限序列稱為字符串〔或串〕。字符串按存儲(chǔ)方式可以分為順序存儲(chǔ)、鏈接存儲(chǔ)和堆分配存儲(chǔ)。串的順序存儲(chǔ)構(gòu)造簡稱為順序串。串順序存儲(chǔ)非緊湊格式的缺點(diǎn)是空間利用率低。串順序存儲(chǔ)緊湊格式的缺點(diǎn)是對(duì)串的字符處理效率低。串鏈接存儲(chǔ)的優(yōu)點(diǎn)是插入、刪除方便，缺點(diǎn)是空間利用率。在C或C++語言中，以字符\0表示串值的終結(jié)。空格串的長度等于空格的個(gè)數(shù)。在空串和空格串中，長度不為0的是空格串。兩個(gè)串相等是指兩個(gè)串長度相等，且對(duì)應(yīng)位置的字符都一樣。設(shè)“S=MyMusic〞，那么LenStr(s)=8。兩個(gè)字符串分別為；S1=〞Todayis〞、S2=〞30July，2005〞，ConcatStr(S1，S2)的結(jié)果是Todayis30July,2005。求子串函數(shù)SubStr(“Todayis30July，2005〞，13，4)的結(jié)果是July。在串的運(yùn)算中，EqualStr(aaa,aab)的返回值<0。在串的運(yùn)算中，EqualStr(aaa,aaa)的返回值0。在子串的定位運(yùn)算中，被匹配的主串稱為目標(biāo)串，子串稱為模式。模式匹配成功的起始位置稱為有效位移。設(shè)S=〞abccdcdccbaa〞，T=〞cdcc〞，那么第6次匹配成功。設(shè)S=〞c:/mydocument/text1.doc〞，T=〞mydont〞，那么字符定位的位置為0。假設(shè)n為主串長度，m為子串長度，n>>m，那么模式匹配算法最壞情況下的時(shí)間復(fù)雜度為(n-m+1)*m。三、選擇題串是和種特殊的線性表，其特殊表達(dá)在〔B〕。A．可能順序存儲(chǔ)B．?dāng)?shù)據(jù)元素是一個(gè)字符C．可以鏈接存儲(chǔ)D．?dāng)?shù)據(jù)元素可以是多個(gè)字符某串的長度小于一常數(shù)，那么采用〔B〕存儲(chǔ)方式最節(jié)省空間。A．鏈?zhǔn)紹．順序C．堆構(gòu)造D．無法確定以下論述正確的選項(xiàng)是〔C〕。A．空串與空格串是一樣的B．〞tel〞是〞Teleptone〞的子串C．空串是零個(gè)字符的串D．空串的長度等于1以下論述正確的選項(xiàng)是〔B〕。A．空串與空格串是一樣的B．〞ton〞是〞Teleptone〞的子串C．空格串是有空格的串D．空串的長度等于1以下論斷正確的選項(xiàng)是〔A〕。A．全部由空格組成的串是空格串B．〞BEUIJING〞是〞BEIJING〞的子串C．〞something〞<〞Something〞D．〞BIT〞=〞BITE〞設(shè)有兩個(gè)串S1和S2，那么EqualStr〔S1，S2〕運(yùn)算稱作〔D〕。A．串連接B．模式匹配C．求子串D．串比較串的模式匹配是指〔D〕。A．判斷兩個(gè)串是否相等B．對(duì)兩個(gè)串比較大小C．找某字符在主串中第一次出現(xiàn)的位置D．找某子串在主串中第一次出現(xiàn)的第一個(gè)字符位置假設(shè)字符串〞ABCDEFG〞采用鏈?zhǔn)酱鎯?chǔ)，假設(shè)每個(gè)字符占用1個(gè)字節(jié)，每個(gè)指針占用2個(gè)字節(jié)。那么該字符串的存儲(chǔ)密度為〔D〕。A．20%B．40%C．50%D．33.3%假設(shè)字符串〞ABCDEFG〞采用鏈?zhǔn)酱鎯?chǔ)，假設(shè)每個(gè)指針占用2個(gè)字節(jié)，假設(shè)希望存儲(chǔ)密度為50%，那么每個(gè)結(jié)點(diǎn)應(yīng)存儲(chǔ)〔A〕個(gè)字符。A.2B.3C.4D.5設(shè)串S1=〞IAM〞，S2=〞ASDUDENT〞，那么ConcatStr(S1，S2)=〔B〕。A．〞IAM〞B.〞IAMASDUDENT〞C.〞IAMASDUDENT〞D.〞ASDUDENT〞設(shè)S=〞〞，那么LenStr(S)=〔A〕。A.0B.1C.2D.3設(shè)目標(biāo)串T=〞AABBCCDDE〞，模式P=〞ABCDE〞，那么該模式匹配的有效位移為〔A〕。A.0B.1C.2D.3設(shè)目標(biāo)串T=〞AABBCCDDEEFF〞，模式P=〞CCD〞，那么該模式匹配的有效位移為〔D〕。A.2B.3C.4D.5設(shè)目標(biāo)串T=〞aabaababaabaa〞，模式P=〞abab〞，模式匹配算法的外層循環(huán)進(jìn)展了〔D〕次。A.1B.9C.4D.5模式匹配算法在最壞情況下的時(shí)間復(fù)雜是〔D〕。A.O(m)B.O(n)C.O(m+n)D.O(m×n)S=〞morning〞,執(zhí)行求子串函數(shù)SubSur(S,2,2)后結(jié)果為〔B〕。A.〞mo〞B.〞or〞C.〞in〞D.〞ng〞S1=〞good〞，S2〞morning〞，執(zhí)行串連接函數(shù)ConcatStr(S1，S2)后結(jié)果為〔A〕。A.〞goodmorning〞B.〞goodmorning〞C.〞GOODMORNING〞D.〞GOODMORNING〞S1=〞good〞,S2=〞morning〞執(zhí)行函數(shù)SubSur(S2,4,LenStr(S1))后的結(jié)果為〔B〕。A.〞good〞B.〞ning〞C.〞go〞D.〞morn〞設(shè)串S1=〞ABCDEFG〞，S2=〞PQRST〞，那么ConcatStr〔SubStr(S1，2，LenStr〔S2〕〕，SubStr(S1，LenStr〔S2〕，2〕〕的結(jié)果串為〔D〕。BCDEFB.BCDEFGC.BCPQRSTD.BCDEFEF假設(shè)串S=〞SOFTWARE〞，其子串的數(shù)目最多是〔C〕。A．35B.36C.37D.38第6章多維數(shù)組和廣義表一、判斷題n維多維數(shù)可以視為n-1維數(shù)組元素組成的線性構(gòu)造?！病獭诚∈杈仃囍蟹橇阍氐膫€(gè)數(shù)遠(yuǎn)小于矩陣元素的總數(shù)?！病獭成先蔷仃囍鲗?duì)角線以上〔不包括主對(duì)角線的元素〕，均為常數(shù)C?！病痢硵?shù)組元素可以由假設(shè)干數(shù)據(jù)項(xiàng)組成?！病獭硵?shù)組的三元組表存儲(chǔ)是對(duì)稀疏矩陣的壓縮存儲(chǔ)?！病獭橙魏尉仃嚩伎梢赃M(jìn)展壓縮存儲(chǔ)?！病痢硰V義表是線性表的推廣，所以廣義表也是線性表。〔×〕廣義表LS=〔a0，a1，……an-1〕，那么an-1是其表尾?！病痢硰V義表〔〔a，b〕a，b〕的表頭和表尾是相等的。〔√〕一個(gè)廣義表的表尾總是一個(gè)廣義表?！病獭扯?、填空題多維數(shù)組的順序存儲(chǔ)方式有按行優(yōu)先順序存儲(chǔ)和按優(yōu)先順序存儲(chǔ)兩種。在多維數(shù)組中，數(shù)據(jù)元素的存放地址可以直接通過地址計(jì)算公式算出，所以多維數(shù)組是一種隨機(jī)存取構(gòu)造。在n維數(shù)組中的每一個(gè)元素最多可以有n個(gè)直接前驅(qū)。輸出二維數(shù)組A[n][m]中所有元素值的時(shí)間復(fù)雜度為n(n*m)。8000000110000000600030070050000000090圖6-19稀疏矩陣A數(shù)組元素a[08000000110000000600030070050000000090圖6-19稀疏矩陣A稀疏矩陣的三元組有3列。稀疏矩陣的三元組中第1列存儲(chǔ)的是數(shù)組中非零元素所在的行數(shù)。n階對(duì)稱矩，如果只存儲(chǔ)下三角元素，只需要n(n-1)/2個(gè)存儲(chǔ)單元。稀疏矩陣A如圖6-19所示，其非零元素存三元組表中，三元組〔4，1，5〕按列優(yōu)先順序存儲(chǔ)在三元組表的第4項(xiàng)。稀疏疏矩陣的壓縮存儲(chǔ)方法通常有三元組表和十字鏈表兩種。任何一個(gè)非空廣義表的表尾必定是廣義表〔或子表〕。tail(head((a，b)(c，d)=b。設(shè)廣義表〔〔a，b，c〕〕那么將c別離出來的運(yùn)算是head(tail(tail(head(L))))。廣義表現(xiàn)出〔〔a，b〕c，d〕，表尾是(c,d)。n階下三角矩陣，因?yàn)閷?duì)角線的上方是同一個(gè)常數(shù)，需要n(n-1)/2+1個(gè)存儲(chǔ)單元。稀疏矩陣中有n個(gè)非零元素，那么三元組有n行。廣義表LS=〔a,〔b〕,〔〔c,〔d〕〕〕〕的長度是3。廣義表LS=〔a,〔b〕,〔〔c,〔d〕〕〕〕的深度是4。廣義表LS=〔〔〕，L〕,那么L的深度是∞。廣義表LS=〔a,〔b〕,〔〔c,〔d〕〕〕〕的表尾是((b),((c,(d))))。三、選擇題在一個(gè)m維數(shù)組中，〔D〕恰好有m個(gè)直接前驅(qū)和m個(gè)直接界后繼。A.開場結(jié)點(diǎn)B.總終端結(jié)點(diǎn)C.邊界結(jié)點(diǎn)D.內(nèi)部結(jié)點(diǎn)對(duì)下述矩陣進(jìn)展壓縮存儲(chǔ)后，失去隨機(jī)存取功能的是〔D〕。A.對(duì)稱矩陣B.三角矩陣C.三對(duì)角矩陣D.稀疏矩陣在按行優(yōu)先順序存儲(chǔ)的三元組表中，下述陳述錯(cuò)誤的選項(xiàng)是〔D〕。A.同一行的非零元素，是按列號(hào)遞增次序存儲(chǔ)的B.同一列的非零元素，是按行號(hào)遞增次序存儲(chǔ)的C.三元組表中三元組行號(hào)是遞增的D.三元組表中三元組列號(hào)是遞增的對(duì)稀疏矩陣進(jìn)展壓縮存儲(chǔ)是為了〔B〕。A.降低運(yùn)算時(shí)間B.節(jié)約存儲(chǔ)空間C.便于矩陣運(yùn)算D.便于輸入和輸出假設(shè)數(shù)組A[0‥m][0‥n]按列優(yōu)先順序存儲(chǔ)，那么aij的地址為〔A〕。A.LOC(a00)+[j×m+i]B.LOC(a00)+[j×n+i]C.LOC(a00)+[(j-1)×n+i-1]D.LOC(a00)+[(j-1)×m+i-1]以下矩陣是一個(gè)〔B〕。對(duì)稱矩陣B．三角矩陣C．稀疏矩陣D．帶狀矩陣10002300456078910在稀疏矩陣的三元組表示法中，每個(gè)三元組表示〔D〕。A．矩陣非零元素的值B．矩陣中數(shù)據(jù)元素的行號(hào)和列號(hào)C．矩陣中數(shù)據(jù)元素的行號(hào)、列號(hào)和值D．矩陣中非零數(shù)據(jù)元素的行號(hào)、列號(hào)和值二維數(shù)組A[6][10]，每個(gè)數(shù)組元素占4個(gè)存儲(chǔ)單元，假設(shè)按行優(yōu)先順序存儲(chǔ)存放數(shù)組元素a[3][5]的存儲(chǔ)地址是1000，那么a[0][0]的存儲(chǔ)地址是〔B〕。A．872B．860C．868D．864廣義表是線性表的推廣，它們之間的區(qū)別于〔A〕。A．能否使用子表B．肥否使用原子項(xiàng)C．是否能為空D．表的長度以下廣義表屬于線性表的是〔B〕。A.E=(a,E)B.E=(a,b,c)C.E=(a,(b,c))D.E=(a,L);L=()廣義表〔〔a,b〕,c,d〕的表尾是〔D〕。A．a(chǎn)B．dC．(a,b)D．(c,d)廣義表A=((x,(a,b)),(x,(a,b),y)),那么運(yùn)算head(head(tail(A)))為〔A〕。xB．(a,b)C．(x,(a,b))D．Atail(head((a,b),c,(c,d)))的結(jié)果是〔B〕。bB．(b)C．(a,b)D．(d)假設(shè)廣義表滿足head(L)=tail(L),那么L的形式是〔B〕。A．空表B．假設(shè)L=〔a1,…,an〕,那么a1=(a2,…,an)C．假設(shè)L=〔a1,…,an〕,那么(a1=a2,=…an)D．((a1)(a1))數(shù)組是一個(gè)〔B〕線性表構(gòu)造。A.非B.推廣了的C.加了限制的D.不加限制的數(shù)組A[0：1，0：1，0：1]共有〔D〕元素。A.4B.5C.6D.8廣義表〔〔a,b〕,c,d〕的表頭是〔C〕。aB.dC.(a,b)D.(c,d)廣義表A=(a),那么表尾為〔C〕。aB.(())C.空表D.(a)以下〔C〕是稀疏矩陣的壓縮存儲(chǔ)方法。A.一維數(shù)組B.二維數(shù)組C.三元數(shù)組D.廣義表設(shè)廣義表D=(a,b,c,d),其深度為〔D〕。A.2B.3C.4D.∞第7章樹和二叉樹一、判斷題樹構(gòu)造中每個(gè)結(jié)點(diǎn)最多只有一個(gè)直接前驅(qū)。〔√〕完全二叉樹一定是滿二叉樹?！病痢吃谥行蚓€索二叉樹中，右線索假設(shè)不為空，那么一定指向其雙親?！病痢骋豢枚鏄渲行虮闅v序列的最后一個(gè)結(jié)點(diǎn)，必定是該二叉樹前序遍歷的最后一個(gè)結(jié)點(diǎn)?！病獭扯鏄涞那靶虮闅v中，任意一個(gè)結(jié)點(diǎn)均處于其子女結(jié)點(diǎn)的前面?！病獭秤啥鏄涞那靶虮闅v序列和中序遍歷序列，可以推導(dǎo)出后序遍歷的序列。〔√〕在完全二叉樹中，假設(shè)一個(gè)結(jié)點(diǎn)沒有左孩子，那么它必然是葉子結(jié)點(diǎn)?！病獭吃诠蚵幋a中，當(dāng)兩個(gè)字符出現(xiàn)的頻率一樣，其編碼也一樣，對(duì)于這種情況應(yīng)該做特殊處理?！病痢澈嘤趦煽脴涞纳洲D(zhuǎn)換的二叉樹，其根結(jié)點(diǎn)一定無右孩子?！病痢尘哂衝個(gè)葉子結(jié)點(diǎn)的哈夫曼樹共有2n-1個(gè)結(jié)點(diǎn)?！病獭扯?、填空題在樹中，一個(gè)結(jié)點(diǎn)所擁有的子樹數(shù)稱為該結(jié)點(diǎn)的度。度為零的結(jié)點(diǎn)稱為葉〔或葉子，或終端〕結(jié)點(diǎn)。樹中結(jié)點(diǎn)的最大層次稱為樹的深度〔或高度〕。對(duì)于二叉樹來說，第i層上至多有2i-1個(gè)結(jié)點(diǎn)。深度為h的二叉樹至多有2h-1個(gè)結(jié)點(diǎn)。由一棵二叉樹的前序序列和中序序列可唯一確定這棵二叉樹。有20個(gè)結(jié)點(diǎn)的完全二叉樹，編號(hào)為10的結(jié)點(diǎn)的父結(jié)點(diǎn)的編號(hào)是5。哈夫曼樹是帶權(quán)路徑長度的最小的二叉樹。由二叉樹的后序和中序遍歷序列，可以唯一確定一棵二叉樹。某二叉樹的中序遍歷序列為：DEBAC，后序遍歷序列為：EBCAD。那么前序遍歷序列為DABEC。設(shè)一棵二叉樹結(jié)點(diǎn)的先序遍歷序歷為：ABDECFGH，中序遍歷序歷為：DEBAFCHG，那么二叉樹中葉結(jié)點(diǎn)是：E、F、H。完全二叉樹的第8層有8個(gè)結(jié)點(diǎn)，那么其葉結(jié)點(diǎn)數(shù)是68。由樹轉(zhuǎn)換二叉樹時(shí)，其根結(jié)點(diǎn)無右子樹。采用二叉鏈表存儲(chǔ)的n個(gè)結(jié)點(diǎn)的二叉樹，一共有2n個(gè)指針域。采用二叉鏈表存儲(chǔ)的n個(gè)結(jié)點(diǎn)的二叉樹，共有空指針n+1個(gè)。前序?yàn)锳，B，C且后序C，B，A的二叉樹共有4種。三個(gè)結(jié)點(diǎn)可以組成2種不同形態(tài)的樹。將一棵完全二叉樹按層次編號(hào)，對(duì)于任意一個(gè)編號(hào)為i的結(jié)點(diǎn)，其左孩子結(jié)點(diǎn)的編號(hào)為：2*i。給定如圖7-36所示的二叉樹，其前序遍歷序列為：ABEFHCG。給定如圖7-37所示的二叉樹，其層次遍歷序列為：ABCEFGH。AABCBCEFG圖7-36二叉樹1EFG圖7-37二叉樹2HDHD三、選擇題樹最適合用來表示〔D〕。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間無聯(lián)系的數(shù)據(jù)D.元素之間有分支的層次關(guān)系前序?yàn)锳，B，C的二叉樹共有〔D〕種。A.2B.3C.4D.5根據(jù)二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有〔C〕種樹型。A.3B.4C.5D.6在一棵具有五層的滿二叉樹中，結(jié)點(diǎn)的點(diǎn)數(shù)為〔B〕。A.16B.31C.32D.33具有64個(gè)結(jié)點(diǎn)的完全二叉樹的深度為〔C〕。A.5B.6C.7D.8任何一棵二叉樹的葉結(jié)點(diǎn)在前序、中序、后序遍歷序列中的相對(duì)次序〔A〕。A.不發(fā)生改變B.發(fā)生改變C.不能確定D.以上都不對(duì)A，B為一棵二叉樹上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，A在B前的條件是〔C〕。A.A和B右方B.A是B祖先C.A和B左方D.A是B子孫以下4棵樹中，〔B〕不是完全二叉樹。AB.AC.AD.ABCBCBCBCDEHDGDEFDED如圖7-38所示的二叉樹，后序遍歷的序列是〔D〕。A.ABCDEFGHIAB.ABDHIECFG圖7-38二叉樹3C.HDIBEAFCGBCD.HIDEBFGCADEFGHI對(duì)于圖7-39所示的二叉樹，其中序序序列為〔A〕。DBEHAFCGB.DBHEAFCGC.ABDEHCFGD.ABCDEFGHABCDEFG圖7-39二叉樹4H某二叉樹的后序遍歷序列為：DABEC，中序遍歷序列為：DEBAC，那么前序遍歷序列為〔D〕。A.ACBEDB.DECABC.DEABCD.CEDBA具有n(n>1)個(gè)結(jié)點(diǎn)的完全二叉樹中，結(jié)點(diǎn)i(2i>n)的左孩子結(jié)點(diǎn)是〔D〕。A.2iB.2i+1C.2i-1D.不存在把一棵樹轉(zhuǎn)換為二叉樹后，這棵二叉樹的形態(tài)是〔A〕。A.唯一的B.有多種C.有多種，但根結(jié)點(diǎn)都沒有左孩子D.有多種，但根結(jié)點(diǎn)都沒有右孩子將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，那么編號(hào)為45的結(jié)點(diǎn)的左孩子編號(hào)為〔B〕。A.46B.47C.90D.91將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹從上到下，從左到右依次對(duì)結(jié)點(diǎn)編號(hào)，根結(jié)點(diǎn)的編號(hào)為1，那么編號(hào)為49的結(jié)點(diǎn)的右孩子編號(hào)為〔B〕。A.98B.99C.50D.100二叉樹按某種順序線索化后，任一結(jié)點(diǎn)均有指向其前驅(qū)和后繼的線索，這種說法〔B〕。A.正確B.錯(cuò)誤C.不確定D.都有可能以下陳述正確的選項(xiàng)是〔D〕。A.二叉樹是度為為2的有序樹B.二叉樹中結(jié)點(diǎn)只有一個(gè)孩子時(shí)無左右之分C.二叉樹必有度為2的結(jié)點(diǎn)D.二叉樹中最多只有兩棵子樹，且有左右子樹之分用5個(gè)權(quán)值{3，2，4，5，1}構(gòu)造的哈夫曼樹的帶權(quán)路徑長度是〔B〕。A.32B.33C.34D.15在樹構(gòu)造中，假設(shè)結(jié)點(diǎn)B有4個(gè)兄弟，A是B的父親結(jié)點(diǎn)，那么A的度為〔C〕。A.3B.4C.5D.6二叉樹的葉結(jié)點(diǎn)個(gè)數(shù)比度為2的結(jié)點(diǎn)的個(gè)數(shù)〔C〕。A.無關(guān)B.相等C.多一個(gè)D.少一個(gè)第8章圖一、判斷題圖可以沒有邊，但不能沒有頂點(diǎn)。〔√〕在無向圖中，(v1，v2)與〔v2，v1〕是兩條不同的邊?！病痢赤徑颖碇荒苡糜谟邢驁D的存儲(chǔ)?！病痢骋粋€(gè)圖的鄰接矩陣表示是唯一的。〔√〕用鄰接矩陣法存儲(chǔ)一個(gè)圖時(shí)，所占用的存儲(chǔ)空間大小與圖中頂點(diǎn)個(gè)數(shù)無關(guān)，而只與圖的邊數(shù)有關(guān)?！病痢秤邢驁D不能進(jìn)展廣度優(yōu)先遍歷?！病痢臣僭O(shè)一個(gè)無向圖以頂點(diǎn)v1為起點(diǎn)進(jìn)展深度優(yōu)先遍歷，所得的遍歷序列唯一，那么可以唯一確定該圖?！病獭炒鎯?chǔ)無向圖的鄰接矩陣是對(duì)稱的，因此只要存儲(chǔ)鄰接矩陣的上三角〔或下三角〕局部就可以了?！病獭秤绵徑颖矸ù鎯?chǔ)圖時(shí)，占用的存儲(chǔ)空間大小只與圖中的邊數(shù)有關(guān)，而與結(jié)點(diǎn)的個(gè)數(shù)無關(guān)。〔×〕假設(shè)從一個(gè)無向圖中任一頂占出發(fā)，進(jìn)展了一次深度優(yōu)先遍歷，就可以訪問圖中所有的頂點(diǎn)，那么該圖一定是連通的?！病獭扯?、填空題圖常用的存儲(chǔ)方式有鄰接矩陣和鄰接表等。圖的遍歷有：深度優(yōu)先搜和廣度優(yōu)先搜等方法。有n條邊的無向圖鄰接矩陣中，1的個(gè)數(shù)是2n。有向圖的邊也稱為弧。圖的鄰接矩陣表示法是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。有向圖G用鄰接矩陣存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的出度。n個(gè)頂占e條邊的圖假設(shè)采用鄰接矩陣存儲(chǔ)，那么空間復(fù)雜度為：On2。n個(gè)頂占e條邊的圖假設(shè)采用鄰接表存儲(chǔ)，那么空間復(fù)雜度為：O(n+e)。設(shè)有一稀疏圖G，那么G采用鄰接表存儲(chǔ)比較節(jié)省空間。設(shè)有一稠密圖G，那么G采用鄰接矩陣存儲(chǔ)比較節(jié)省空間。圖的逆鄰接表存儲(chǔ)構(gòu)造只適用于有向圖。n個(gè)頂點(diǎn)的完全無向圖有n(n-1)/2條邊。有向圖的鄰接矩陣表表示適于求頂點(diǎn)的出度。有向圖的鄰接矩陣表示中，第i列上非0元素的個(gè)數(shù)為頂點(diǎn)vi的入度。對(duì)于具有n個(gè)頂點(diǎn)的圖，其生成樹有且僅有n-1條邊。對(duì)有n個(gè)頂點(diǎn)，e條弧的有向圖，其鄰接表表示中，需要n+e個(gè)結(jié)點(diǎn)。從圖中某一頂點(diǎn)出發(fā)，訪遍歷圖中其余頂點(diǎn)，且使每一頂點(diǎn)僅被訪問一次，稱這一過程為圖的遍歷。無向圖的鄰接矩陣一定是對(duì)稱矩陣。一個(gè)連通網(wǎng)的最小生成樹是該圖所有生成樹中權(quán)最小的生成樹。假設(shè)要求一個(gè)稠密圖G的最小生成樹，最好用Prim算法來求解。三、選擇題在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的〔C〕倍。A.1/2B.1C.2D.4在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的〔B〕倍。A.1/2B.1C.2D.4對(duì)于一個(gè)具有n個(gè)頂點(diǎn)的有向圖的邊數(shù)最多有〔B〕。A.nB.n(n-1)C.n(n-1)/2D.2n在一個(gè)具有n個(gè)頂點(diǎn)的無向圖中，要連通全部頂點(diǎn)至少需要〔C〕條邊。A.nB.n+1C.n-1D.n/2有8個(gè)結(jié)點(diǎn)的有向完全圖有〔C〕條邊。A.14B.28C.56D.112深度優(yōu)先遍歷類似于二叉樹的〔A〕。A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷廣度優(yōu)先遍歷類似于二叉樹的〔D〕。A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷任何一個(gè)無向連通圖的最小生成樹〔A〕。A.只有一棵B.一棵或多棵C.一定有多棵D.可以不存在無向圖頂點(diǎn)v的度是關(guān)聯(lián)于該頂點(diǎn)B〕的數(shù)目。A.頂點(diǎn)B.邊C.序號(hào)D.下標(biāo)有n個(gè)頂點(diǎn)的無向圖的鄰接矩陣是用〔B〕數(shù)組存儲(chǔ)。A.一維B.n行n列C.任意行n列D.n行任意列對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無向圖，采用鄰接表表示，那么表頭向量大小為〔C〕。A.n-1B.n+1C.nD.n+e在圖的表示法中，表示形式唯一的是〔A〕。A.鄰接矩陣表示法B.鄰接表表示法C.逆鄰接表表示法D.鄰接表和逆鄰接表表示法在一個(gè)具有n個(gè)頂點(diǎn)e條邊的圖中，所有頂點(diǎn)的度數(shù)之和等于〔C〕。nB.eC.2nD.2ev11aav2v323bcbceev4v545dfdf圖8-23度為3的結(jié)點(diǎn)圖8-24〔15〕題圖8-25從頂點(diǎn)a出發(fā)圖8-26優(yōu)先遍歷圖8-23中，度為3的結(jié)點(diǎn)是〔B〕。A.V1B.V2C.V3D.V4圖8-24是〔A〕。A.連通圖B.強(qiáng)連通圖C.生成樹D.無環(huán)圖如圖8-25所示，從頂點(diǎn)a出發(fā)，按深度優(yōu)先進(jìn)展遍歷，那么可能得到的一種頂點(diǎn)序列為〔D〕。A.a,b,e,c,d,fB.a,c,f,e,b,dC.a,e,b,c,f,dD.a,e,d,f,c,b如圖8-26所示，從頂點(diǎn)a出發(fā)，按廣度優(yōu)先進(jìn)展遍歷，那么可能得到的一種頂點(diǎn)序列為〔A〕。A.a,b,e,c,d,fB.a,b,e,c,f,dC.a,e,b,c,f,dD.a,e,d,f,c,b最小生成樹的構(gòu)造可使用〔A〕算法。A.Prim算法B.卡爾算法C.哈夫曼算法D.迪杰斯特拉算法下面關(guān)于圖的存儲(chǔ)構(gòu)造的表達(dá)中正確的選項(xiàng)是〔A〕。A.用鄰接矩陣存儲(chǔ)圖，占用空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，而與邊數(shù)無關(guān)B.用鄰接矩陣存儲(chǔ)圖，占用空間大小只與圖中邊數(shù)有關(guān)，而與頂點(diǎn)數(shù)無關(guān)C.用鄰接存儲(chǔ)圖，占用空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，而與邊數(shù)無關(guān)D.用鄰接存儲(chǔ)圖，占用空間大小只與圖中邊數(shù)有關(guān)，而與頂點(diǎn)數(shù)無關(guān)連通分量是〔C〕的極大連通子圖。樹B.圖C.無向圖D.有向圖第9章查找一、判斷題二分查找法要求待查表的關(guān)鍵字值必須有序?！病獭硨?duì)有序表而言采用二分查找總比采用順序查找法速度快?！病痢吃诙媾判驑渲?，根結(jié)點(diǎn)的值都小于孩子的結(jié)點(diǎn)的值?！病痢成⒘写鎯?chǔ)法的基本思想是由關(guān)鍵字的值的決定數(shù)據(jù)的存儲(chǔ)地址?！病獭彻１硎且环N將關(guān)鍵字轉(zhuǎn)換為存儲(chǔ)地址的存儲(chǔ)方法?！病獭尺x擇好的哈希函數(shù)就可以防止沖突的發(fā)生?！病痢吃谟行虻捻樞虮砗陀行虻逆湵砩?，均可以采用二分查找來提高查找速度?！病痢巢捎梅謮K查找，既有實(shí)現(xiàn)線性表所希望的查找速度，又能適應(yīng)動(dòng)態(tài)變化的需要?！病獭彻２檎业男手饕Q于哈希表構(gòu)造時(shí)選取的哈希函數(shù)和處理沖突的方法?！病獭吃诙媾判驑渖蟿h除一個(gè)結(jié)點(diǎn)時(shí)，不必移動(dòng)其他結(jié)點(diǎn)，只要將該結(jié)點(diǎn)的父結(jié)點(diǎn)的相應(yīng)指針域置空即可?！病痢扯?、填空題順序查找法，表中元素可以任意存放。在分塊查找方法中，首先查找索引，然后再查找相應(yīng)的塊。順序查找、二分查找、分塊查找都屬于靜態(tài)查找。靜態(tài)查找表所含元素個(gè)數(shù)在查找階段是固定不變的。對(duì)于長度為n的線性表，假設(shè)進(jìn)展順序查找，那么時(shí)間復(fù)雜度為O(n)。對(duì)于長度為n的線性表，假設(shè)采用二分查找，那么時(shí)間復(fù)雜度為O(log2n)。理想情況下，在散列表中查找一個(gè)元素的時(shí)間復(fù)雜度為：O(1)。在關(guān)鍵字序列〔7，10，12，18，28，36，45，92〕中，用二分查找法查找關(guān)鍵字92，要比較4次才找到。設(shè)有100個(gè)元素，用二分查找法查找時(shí)，最大的比較次數(shù)是7次。對(duì)二叉排序樹進(jìn)展查找的方法是用待查的值與根結(jié)點(diǎn)的鍵值進(jìn)展比較，假設(shè)比根結(jié)點(diǎn)值小，那么繼續(xù)在左子樹中查找。二叉排序樹是一種動(dòng)態(tài)查找表。哈希表是按散列存儲(chǔ)方式構(gòu)造的存儲(chǔ)構(gòu)造。哈希法既是一種存儲(chǔ)方法，又是一種查找方法。散列表的查找效率主要取決于散列表造表時(shí)選取的散列函數(shù)和處理沖突的方法。設(shè)散列函數(shù)H和鍵值k1，k2，假設(shè)k1≠k2，而H〔k2〕H〔k2〕，那么稱這種現(xiàn)象為沖突。處理沖突的兩類主要方法是開放定地址法和拉鏈法〔或鏈地址法〕。散列表〔或散列〕查找法的平均查找長度與元素個(gè)數(shù)n無關(guān)。在哈希函數(shù)H〔key〕=key%P中，P一般應(yīng)取質(zhì)數(shù)。在查找過程中有插入元素或刪除元素操作的，稱為動(dòng)態(tài)查找。各結(jié)點(diǎn)左、右子樹深度之差的絕對(duì)值至多為1的二叉樹稱為平衡二叉樹。三、選擇題查找表以〔A〕為查找構(gòu)造。A.集合B.圖C.樹D.文件順序查找法適合于存儲(chǔ)構(gòu)造為〔B〕的線性表。A.散列存儲(chǔ)B.順序存儲(chǔ)或鏈接存儲(chǔ)C.壓縮存儲(chǔ)D.索引存儲(chǔ)在表長為n的鏈表中進(jìn)展線性查找，它的平均查找長度為〔B〕。A.ASL=nB.ASL=(n+1)/2C.ASL=n+1D.ASL≈log對(duì)線性表進(jìn)展二分查找時(shí)，要求線性表必須〔D〕。A.以順序方式存儲(chǔ)B.以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序C.以鏈接方式存儲(chǔ)D.以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字有序排序衡量查找算法效率的主要標(biāo)準(zhǔn)是〔B〕。A.元素個(gè)數(shù)B.平均查找長度C.所需的存儲(chǔ)量D.算法難易難度如果要求一個(gè)線性表既能較快地查找，又能適應(yīng)動(dòng)態(tài)變化的要求，可以采用〔A〕查找方法。A.分塊B.順序C.二分D.散列鏈表適用于〔A〕查找。A.順序B.二分C.隨機(jī)D.順序或二分一個(gè)有序表為{1，3，9，12，32，41，45，62，75，77，82，95，100}，當(dāng)二分查找值為82的結(jié)點(diǎn)時(shí)，〔C〕次比較后查找成功。A.2B.3C.4D.5二分查找有序表{4，6，10，12，20，30，50，70，88，100}，假設(shè)查找表中元素58，那么它將依次與表中〔B〕比較大小，查找結(jié)果是失敗。A.30，88，70，50B.20，70，30，50C.20，50D.30，88，50對(duì)有14個(gè)元素的有序A[1‥14]作二分查找，查找元素A[4]時(shí)的被比較元素依次為〔C〕A.A[1]，A[2]，A[3]，A[4]B.A[1]，A[14]，A[7]，A[4]C.A[7]，A[3]，A[5]，A[4]D.A[7]，A[5]，A[3]，A[4]有一個(gè)長度為12的有序表，按二分查找法對(duì)其進(jìn)展查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為〔B〕。A.35/12B.37/12C.39/12D.43/12采用分塊查找時(shí)，假設(shè)線性表共有625個(gè)元素，查找生個(gè)元素等概率相等，假設(shè)采用順序查找來確定結(jié)點(diǎn)所在的塊時(shí)，每塊分〔C〕個(gè)結(jié)點(diǎn)最正確。A．6B．10C．25D．625以下〔C〕不是利用查找表中數(shù)據(jù)元素的關(guān)系進(jìn)展查找的方法。A．平衡二叉樹B．有序表的查找C．散列查找D．二叉排序樹的查找設(shè)哈希表長m=14，哈希函數(shù)H(key)=key%11。表中已有4個(gè)結(jié)點(diǎn)：addr(15)=4addr(38)=5addr(61)=6addr(84)=7其余地址為空。如用二次探測再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是〔D〕。A．8B．3C．5D．9對(duì)包含n個(gè)元素的散列表進(jìn)展查找。平均查找長度為〔D〕。A．O(n2)B．O(log2n)C．O(n)D．不直接依賴于n沖突指的是〔C〕。A．兩個(gè)元素具有一樣序號(hào)B．兩個(gè)元素的鍵值不同C．不同鍵值對(duì)應(yīng)一樣的存儲(chǔ)地址D．兩個(gè)元素的鍵值一樣在查找過程中，不做增加、刪除或修改的查找稱為〔A〕。A．靜態(tài)查找B．內(nèi)創(chuàng)造C．動(dòng)態(tài)查找D．處查找8個(gè)元素為{34，76，45，18，26，54，92，65}，按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹，最后兩層上結(jié)點(diǎn)的總數(shù)為〔B〕。A．1B．2C．3D．4不可能生成圖9-17所示的二叉排序樹的關(guān)鍵字的序列是〔A〕。A．45312B．42531C．45213D．4231542513圖9-17二叉樹動(dòng)態(tài)查找包括〔B〕查找。A.順序表B.二叉排序樹C.有序表D.索引順序表第10章排序一、判斷題如果某種排序算法不穩(wěn)定，那么該排序方法就沒有實(shí)用價(jià)值?！病痢诚柵判蚴遣环€(wěn)定的排序?！病獭趁芭菖判蚴遣环€(wěn)定的排序。〔×〕對(duì)n個(gè)記錄的進(jìn)展快速排序，所需要的平均時(shí)間是O〔nlog2n〕?！病獭扯雅判蛩璧臅r(shí)間與待排序的記錄個(gè)數(shù)無關(guān)?！病痢钞?dāng)待排序的元素個(gè)數(shù)很多時(shí)，為了交換元素的位置占用較多的時(shí)間，這是影響時(shí)間復(fù)雜度的主要因素?！病獭晨焖倥判蛟谌魏吻闆r下都比其他排序方法速度快。〔×〕對(duì)快速排序來說，初始序列為正序或反序都是最壞情況?！病獭?/p>