數(shù)據(jù)結(jié)構(gòu)(陳元春張亮王勇編著)(鐵道出版社第二版)練習(xí)題及答案

緒論判斷題數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的內(nèi)容和形式無(wú)關(guān)。（√）一個(gè)數(shù)據(jù)結(jié)構(gòu)是由一個(gè)邏輯結(jié)構(gòu)和這個(gè)邏輯結(jié)構(gòu)上的一個(gè)基本運(yùn)算集構(gòu)成的整體。（√）數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（×）數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是相同的。（×）程序和算法原則上沒有區(qū)別，所以在討論數(shù)據(jù)結(jié)構(gòu)時(shí)可以通用。（×）從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。（√）數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲(chǔ)映象。（√）數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)實(shí)際的存儲(chǔ)形式。（√）數(shù)據(jù)的邏輯結(jié)構(gòu)是依賴于計(jì)算機(jī)的。（×）算法是對(duì)解題方法和步驟的描述。（√）二、填空題數(shù)據(jù)有邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩種結(jié)構(gòu)。數(shù)據(jù)邏輯結(jié)構(gòu)除了集合以外，還包括線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們是線性結(jié)構(gòu)和非線性結(jié)構(gòu)。樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為非線性結(jié)構(gòu)。在樹形結(jié)構(gòu)中，除了樹根結(jié)點(diǎn)以外，其余每個(gè)結(jié)點(diǎn)只有1個(gè)前驅(qū)結(jié)點(diǎn)。在圖形結(jié)構(gòu)中，每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后繼結(jié)點(diǎn)數(shù)可以任意多個(gè)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)又叫物理結(jié)構(gòu)。數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)形式包括順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、索引存儲(chǔ)和散列存儲(chǔ)。線性結(jié)構(gòu)中的元素之間存在一對(duì)一的關(guān)系。樹形結(jié)構(gòu)中的元素之間存在一對(duì)多的關(guān)系。圖形結(jié)構(gòu)的元素之間存在多對(duì)多的關(guān)系。數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和算法（或運(yùn)算）3個(gè)方面的內(nèi)容。數(shù)據(jù)結(jié)構(gòu)被定義為（D，R），其中D是數(shù)據(jù)的有限集合，R是D上的關(guān)系有限集合。算法是一個(gè)有窮指令的集合。算法效率的度量可以分為事先估算法和事后統(tǒng)計(jì)法。一個(gè)算法的時(shí)間復(fù)雜度是算法輸入規(guī)模的函數(shù)。算法的空間復(fù)雜度是指該算法所耗費(fèi)的存儲(chǔ)空間，它是該算法求解問(wèn)題規(guī)模的n的函數(shù)。若一個(gè)算法中的語(yǔ)句頻度之和為T(n)=6n+3nlog2n,則算法的時(shí)間復(fù)雜度為O（nlog2n）。若一個(gè)算法的語(yǔ)句頻度之和為T(n)=3n+nlog2+n2,則算法的時(shí)間復(fù)雜度為O（n2）。數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序問(wèn)題中計(jì)算機(jī)的操作對(duì)象，以及它們之間的關(guān)系和運(yùn)算的學(xué)科。三、選擇題數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的（A）及它們之間的相互關(guān)系。A．存儲(chǔ)結(jié)構(gòu)和邏輯結(jié)構(gòu)B．存儲(chǔ)和抽象C．聯(lián)系和抽象D．聯(lián)系與邏輯在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（C）。A．動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C．線性結(jié)構(gòu)和非線性結(jié)構(gòu)D．內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)。數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)內(nèi)表示時(shí)，物理地址和邏輯地址相同并且是連續(xù)的，稱之為（C）。A．存儲(chǔ)結(jié)構(gòu)B．邏輯結(jié)構(gòu)C．順序存儲(chǔ)結(jié)構(gòu)D．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)非線性結(jié)構(gòu)中的每個(gè)結(jié)點(diǎn)（D）。A．無(wú)直接前驅(qū)結(jié)點(diǎn)．B．無(wú)直接后繼結(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ǔ)結(jié)構(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ù)結(jié)構(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ǔ)結(jié)構(gòu)稱為（A）結(jié)構(gòu)。A．順序結(jié)構(gòu)B．鏈?zhǔn)浇Y(jié)構(gòu)C．索引結(jié)構(gòu)D．散列結(jié)構(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．圖形結(jié)構(gòu)B．線性結(jié)構(gòu)C．樹形結(jié)構(gòu)D．集合在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是（C）。A．物理結(jié)構(gòu)B．存儲(chǔ)結(jié)構(gòu)C．邏輯結(jié)構(gòu)D．邏輯和存儲(chǔ)結(jié)構(gòu)下列4種基本邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是（A）。A．集合B．線性結(jié)構(gòu)C．樹形結(jié)構(gòu)D．圖形結(jié)構(gòu)與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的（A）。A．邏輯結(jié)構(gòu)B．存儲(chǔ)結(jié)構(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．健壯性D．高效性算法在發(fā)生非法操作時(shí)可以作出相應(yīng)處理的特性稱為算法的（C）。A．正確性B．易讀性C．健壯性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.正確性和簡(jiǎn)明性C.可讀性和文檔性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性計(jì)算機(jī)算法必須具備輸入、輸出和（C）。A.計(jì)算方法B.排序方法C.解決問(wèn)題的有限運(yùn)算步驟D.程序設(shè)計(jì)方法第2章線性表一、判斷題線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)。（×）鏈表的每個(gè)結(jié)點(diǎn)都恰好包含一個(gè)指針域。（×）在線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，邏輯上相鄰的兩個(gè)元素在物理位置上并不一定緊鄰。（√）順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，插入、刪除效率高。（×）線性鏈表的刪除算法簡(jiǎn)單，因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后，計(jì)算機(jī)會(huì)自動(dòng)地將后續(xù)的各個(gè)單元向前移動(dòng)。（×）順序表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡(jiǎn)單類型，而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。（×）線性表鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是可以用一組任意的存儲(chǔ)單元存儲(chǔ)表中的數(shù)據(jù)元素。（√）線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元。（√）順序表結(jié)構(gòu)適宜進(jìn)行順序存取，而鏈表適宜進(jìn)行隨機(jī)存取。（×）插入和刪除操作是數(shù)據(jù)結(jié)構(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ǔ)結(jié)構(gòu)。順序表中訪問(wèn)任意一個(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è)長(zhǎng)度為n的順序表中刪除第i個(gè)元素，要移動(dòng)n-i個(gè)元素。在一個(gè)長(zhǎng)度為n的順序表中，如果要在第i個(gè)元素前插入一個(gè)元素，要后移n-i+1個(gè)元素。在無(wú)頭結(jié)點(diǎn)的單向鏈表中，第一個(gè)結(jié)點(diǎn)的地址存放在頭指針中，而其他結(jié)點(diǎn)的存儲(chǔ)地址存放在前趨結(jié)點(diǎn)的指針域中。線性表的元素總數(shù)不確定，且經(jīng)常需要進(jìn)行插入和刪除操作，應(yīng)采用鏈子存儲(chǔ)結(jié)構(gòu)。在線性表中的鏈?zhǔn)酱鎯?chǔ)中，元素之間的邏輯關(guān)系是通過(guò)指針決定。在雙向鏈表中，每個(gè)結(jié)點(diǎn)都有兩個(gè)指針域，它們一個(gè)指向其前趨結(jié)點(diǎn)，另一個(gè)指向其后繼結(jié)點(diǎn)。對(duì)一個(gè)需要經(jīng)常進(jìn)行插入和刪除操作的線性表，采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)為宜。雙向鏈表中，設(shè)P是指向其中待刪除的結(jié)點(diǎn)，則需要執(zhí)行的操作為p->prior->next=p->next；p->next->prior=p->prior在如圖所示的鏈表中，若在指針P所在的結(jié)點(diǎn)之后插入數(shù)據(jù)域值為a和b的兩個(gè)結(jié)點(diǎn)，則可用語(yǔ)句S->next->next=p->next和P->next=S；來(lái)實(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ǔ)結(jié)構(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ǔ)單元，若第一個(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．說(shuō)明該單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)下面關(guān)于線性表的敘述中，錯(cuò)誤的是（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ā)訪問(wèn)到其余各結(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ī)訪問(wèn)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ǔ)的線性結(jié)構(gòu)。（×）棧的特點(diǎn)是“后進(jìn)先出”。（√）空棧就是所有元素都為0的棧。（×）在C（或C++）語(yǔ)言中設(shè)順序棧的長(zhǎng)度為MAXLEN，則top=MAXLEN時(shí)表示棧滿。（×）鏈棧與順序棧相比，其特點(diǎn)之一是通常不會(huì)出現(xiàn)棧滿的情況。（√）一個(gè)棧的輸入序列為：A，B，C，D，可以得到輸出序列：C，A，B，D。（×）遞歸定義就是循環(huán)定義。（×）將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)是棧的典型應(yīng)用之一。（√）二、填空題在棧結(jié)構(gòu)中，允許插入、刪除的一端稱為棧頂。在順序棧中，當(dāng)棧頂指針top=-1時(shí)，表示棧空。在有n個(gè)元素的棧中，進(jìn)棧操作時(shí)間復(fù)雜度為O（1）。在棧中，出棧操作時(shí)間復(fù)雜度為O（1）。已知表達(dá)式，求它的后綴表達(dá)式是棧的典型應(yīng)用。在一個(gè)鏈棧中，若棧頂指針等于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í)行的語(yǔ)句有：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出棧操作之前首先要判斷棧是否空。若內(nèi)在空間充足，鏈?？梢圆欢x棧滿運(yùn)算。鏈棧LS為空的條件是LS->next=NULL。鏈棧LS的棧頂元素是鏈表的首元素。同一棧的各元素的類型相同。若進(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è)棧結(jié)構(gòu)的站臺(tái)，下列不可能的出站順序?yàn)椋―）。A．1234B．1243C．1324D．1423如果以鏈表作為棧的存儲(chǔ)結(jié)構(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++）語(yǔ)言中，一個(gè)順序棧一旦被聲明，其占用空間的大?。ˋ）。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)過(guò)下列棧的運(yùn)算后，再執(zhí)行ReadTop(s)的值是（A）。InitStack(s);Push(s，a);Push(s，b);Pob(s);aB.bC.1D.0經(jīng)過(guò)下列棧的運(yùn)算后，x的值是（B）。InitStack(s)（初始化棧）;Push(s，a);Push(s，b);ReadTop(s)；Pob(s，x);aB.bC.1D.0經(jīng)過(guò)下列棧的運(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)過(guò)下列棧的運(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．誰(shuí)先誰(shuí)后無(wú)關(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指針的值。（×）在循環(huán)隊(duì)列中，若尾指針rear大于頭指針front，其元素個(gè)數(shù)為rear-front。（√）在單向循環(huán)鏈表中，若頭指針為h，那么p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是p=h。（×）鏈隊(duì)列在一定范圍內(nèi)不會(huì)出現(xiàn)隊(duì)滿的情況。（√）在循環(huán)鏈隊(duì)列中無(wú)溢出現(xiàn)象。（×）棧和隊(duì)列都是順序存儲(chǔ)的線性結(jié)構(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è)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)表表示，若只設(shè)頭指針，則入隊(duì)操作的時(shí)間復(fù)雜度為O(n)。設(shè)長(zhǎng)度為n的鏈隊(duì)列用單循環(huán)表表示，若只設(shè)尾指針，則入隊(duì)操作的時(shí)間復(fù)雜度為O(1)。在一個(gè)鏈隊(duì)列中，若隊(duì)首指針與隊(duì)尾指針的值相同，則表示該隊(duì)列為空。設(shè)循環(huán)隊(duì)列的頭指針front指向隊(duì)首元素，尾指針rear指向隊(duì)尾元素后的一個(gè)空閑元素，隊(duì)列的最大空間為MAXLEN，則隊(duì)滿標(biāo)志為front==(rear+1)%MAXLEN。在一個(gè)鏈隊(duì)列中，若隊(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)過(guò)一系列的入隊(duì)和出隊(duì)的運(yùn)算后，front=11，rear=19，則循環(huán)隊(duì)列中還有8個(gè)元素。隊(duì)列Q，經(jīng)過(guò)下列運(yùn)算：InitQueue(Q)(初始化隊(duì)列)；InQueue(Q,a)；InQueue(Q,b)；OutQueue(Q,x)；ReadFront(Q,x)；QEmpty(Q)；后的值是8。隊(duì)列Q經(jīng)過(guò)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）線性表結(jié)構(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ì)列一旦說(shuō)明，其占用空間的大?。ˋ）。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若進(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)過(guò)下列運(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)的結(jié)構(gòu)：data為數(shù)據(jù)域，next為指針域，且top是棧頂指針，若想在鏈棧的棧頂插入一個(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)過(guò)下列運(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.若用一個(gè)大小為6數(shù)組來(lái)實(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è)字符。（√）串的長(zhǎng)度是指串中不同字符的個(gè)數(shù)。（×）如果兩個(gè)串含有相同的字符，則說(shuō)明它們相等。（×）如果一個(gè)串中所有的字母均在另一個(gè)串中出現(xiàn)，則說(shuō)明前者是后者的子串。（×）串的堆分配存儲(chǔ)是一種動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)。（√）“DT”是“DATA”的子串。（×）串中任意個(gè)字符組成的子序列稱為該串的子串。（×）子串的定位運(yùn)算稱為模式匹配。（√）在鏈串中為了提高存儲(chǔ)密度，應(yīng)該增大結(jié)點(diǎn)的大小。（√）二、填空題由零個(gè)或多個(gè)字符組成的有限序列稱為字符串（或串）。字符串按存儲(chǔ)方式可以分為順序存儲(chǔ)、鏈接存儲(chǔ)和堆分配存儲(chǔ)。串的順序存儲(chǔ)結(jié)構(gòu)簡(jiǎn)稱為順序串。串順序存儲(chǔ)非緊湊格式的缺點(diǎn)是空間利用率低。串順序存儲(chǔ)緊湊格式的缺點(diǎn)是對(duì)串的字符處理效率低。串鏈接存儲(chǔ)的優(yōu)點(diǎn)是插入、刪除方便，缺點(diǎn)是空間利用率。在C或C++語(yǔ)言中，以字符\0表示串值的終結(jié)?？崭翊拈L(zhǎng)度等于空格的個(gè)數(shù)。在空串和空格串中，長(zhǎng)度不為0的是空格串。兩個(gè)串相等是指兩個(gè)串長(zhǎng)度相等，且對(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。若n為主串長(zhǎng)度，m為子串長(zhǎng)度，n>>m，則模式匹配算法最壞情況下的時(shí)間復(fù)雜度為(n-m+1)*m。三、選擇題串是和種特殊的線性表，其特殊體現(xiàn)在（B）。A．可能順序存儲(chǔ)B．?dāng)?shù)據(jù)元素是一個(gè)字符C．可以鏈接存儲(chǔ)D．?dāng)?shù)據(jù)元素可以是多個(gè)字符某串的長(zhǎng)度小于一常數(shù)，則采用（B）存儲(chǔ)方式最節(jié)省空間。A．鏈?zhǔn)紹．順序C．堆結(jié)構(gòu)D．無(wú)法確定以下論述正確的是（C）。A．空串與空格串是相同的B．”tel”是”Teleptone”的子串C．空串是零個(gè)字符的串D．空串的長(zhǎng)度等于1以下論述正確的是（B）。A．空串與空格串是相同的B．”ton”是”Teleptone”的子串C．空格串是有空格的串D．空串的長(zhǎng)度等于1以下論斷正確的是（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è)字符位置若字符串”ABCDEFG”采用鏈?zhǔn)酱鎯?chǔ)，假設(shè)每個(gè)字符占用1個(gè)字節(jié)，每個(gè)指針占用2個(gè)字節(jié)。則該字符串的存儲(chǔ)密度為（D）。A．20%B．40%C．50%D．33.3%若字符串”ABCDEFG”采用鏈?zhǔn)酱鎯?chǔ)，假設(shè)每個(gè)指針占用2個(gè)字節(jié)，若希望存儲(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若串S=”SOFTWARE”，其子串的數(shù)目最多是（C）。A．35B.36C.37D.38第6章多維數(shù)組和廣義表一、判斷題n維多維數(shù)可以視為n-1維數(shù)組元素組成的線性結(jié)構(gòu)。（√）稀疏矩陣中非零元素的個(gè)數(shù)遠(yuǎn)小于矩陣元素的總數(shù)。（√）上三角矩陣主對(duì)角線以上（不包括主對(duì)角線的元素），均為常數(shù)C。（×）數(shù)組元素可以由若干數(shù)據(jù)項(xiàng)組成。（√）數(shù)組的三元組表存儲(chǔ)是對(duì)稀疏矩陣的壓縮存儲(chǔ)。（√）任何矩陣都可以進(jìn)行壓縮存儲(chǔ)。（×）廣義表是線性表的推廣，所以廣義表也是線性表。（×）廣義表LS=（a0，a1，……an-1），則an-1是其表尾。（×）廣義表（（a，b）a，b）的表頭和表尾是相等的。（√）一個(gè)廣義表的表尾總是一個(gè)廣義表。（√）二、填空題多維數(shù)組的順序存儲(chǔ)方式有按行優(yōu)先順序存儲(chǔ)和按優(yōu)先順序存儲(chǔ)兩種。在多維數(shù)組中，數(shù)據(jù)元素的存放地址可以直接通過(guò)地址計(jì)算公式算出，所以多維數(shù)組是一種隨機(jī)存取結(jié)構(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分離出來(lái)的運(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））））的長(zhǎng)度是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ò)誤的是（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.便于輸入和輸出若對(duì)稱數(shù)組A[1‥10][1‥10]按行優(yōu)先順序存儲(chǔ)，只存下三角到B數(shù)組中，一個(gè)元素占一個(gè)字節(jié)，B也從1開始，則a53的地址為（B[13]）。5若數(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ǔ)單元，若按行優(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．表的長(zhǎng)度下列廣義表屬于線性表的是（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)若廣義表滿足head(L)=tail(L),則L的形式是（B）。A．空表B．若L=（a1,…,an）,則a1=(a2,…,an)C．若L=（a1,…,an）,則(a1=a2,=…an)D．((a1)(a1))數(shù)組是一個(gè)（B）線性表結(jié)構(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.1第7章樹和二叉樹一、判斷題樹結(jié)構(gòu)中每個(gè)結(jié)點(diǎn)最多只有一個(gè)直接前驅(qū)。（√）完全二叉樹一定是滿二叉樹。（×）在中序線索二叉樹中，右線索若不為空，則一定指向其雙親。（×）一棵二叉樹中序遍歷序列的最后一個(gè)結(jié)點(diǎn)，必定是該二叉樹前序遍歷的最后一個(gè)結(jié)點(diǎn)。（√）二叉樹的前序遍歷中，任意一個(gè)結(jié)點(diǎn)均處于其子女結(jié)點(diǎn)的前面。（√）由二叉樹的前序遍歷序列和中序遍歷序列，可以推導(dǎo)出后序遍歷的序列。（√）在完全二叉樹中，若一個(gè)結(jié)點(diǎn)沒有左孩子，則它必然是葉子結(jié)點(diǎn)。（√）在哈夫曼編碼中，當(dāng)兩個(gè)字符出現(xiàn)的頻率相同，其編碼也相同，對(duì)于這種情況應(yīng)該做特殊處理。（×）含多于兩棵樹的森林轉(zhuǎn)換的二叉樹，其根結(jié)點(diǎn)一定無(wú)右孩子。（×）具有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ì)于二叉樹來(lái)說(shuō)，第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)路徑長(zhǎng)度的最小的二叉樹。由二叉樹的后序和中序遍歷序列，可以唯一確定一棵二叉樹。某二叉樹的中序遍歷序列為：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)無(wú)右子樹。采用二叉鏈表存儲(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二叉樹2HDHD21．一棵哈夫曼樹有10個(gè)非終端結(jié)點(diǎn)，該樹共有多少個(gè)結(jié)點(diǎn)。n0+n2=n2+1+n2=21三、選擇題樹最適合用來(lái)表示（D）。A.有序數(shù)據(jù)元素B.無(wú)序數(shù)據(jù)元素C.元素之間無(wú)聯(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ū)和后繼的線索，這種說(shuō)法（B）。A.正確B.錯(cuò)誤C.不確定D.都有可能下列陳述正確的是（D）。A.二叉樹是度為為2的有序樹B.二叉樹中結(jié)點(diǎn)只有一個(gè)孩子時(shí)無(wú)左右之分C.二叉樹必有度為2的結(jié)點(diǎn)D.二叉樹中最多只有兩棵子樹，且有左右子樹之分用5個(gè)權(quán)值{3，2，4，5，1}構(gòu)造的哈夫曼樹的帶權(quán)路徑長(zhǎng)度是（B）。A.32B.33C.34D.15在樹結(jié)構(gòu)中，若結(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.無(wú)關(guān)B.相等C.多一個(gè)D.少一個(gè)第8章圖一、判斷題圖可以沒有邊，但不能沒有頂點(diǎn)。（√）在無(wú)向圖中，(v1，v2)與（v2，v1）是兩條不同的邊。（×）鄰接表只能用于有向圖的存儲(chǔ)。（×）一個(gè)圖的鄰接矩陣表示是唯一的。（√）用鄰接矩陣法存儲(chǔ)一個(gè)圖時(shí)，所占用的存儲(chǔ)空間大小與圖中頂點(diǎn)個(gè)數(shù)無(wú)關(guān)，而只與圖的邊數(shù)有關(guān)。（×）有向圖不能進(jìn)行廣度優(yōu)先遍歷。（×）若一個(gè)無(wú)向圖以頂點(diǎn)v1為起點(diǎn)進(jìn)行深度優(yōu)先遍歷，所得的遍歷序列唯一，則可以唯一確定該圖。（√）存儲(chǔ)無(wú)向圖的鄰接矩陣是對(duì)稱的，因此只要存儲(chǔ)鄰接矩陣的上三角（或下三角）部分就可以了。（√）用鄰接表法存儲(chǔ)圖時(shí)，占用的存儲(chǔ)空間大小只與圖中的邊數(shù)有關(guān)，而與結(jié)點(diǎn)的個(gè)數(shù)無(wú)關(guān)。（×）若從一個(gè)無(wú)向圖中任一頂占出發(fā)，進(jìn)行了一次深度優(yōu)先遍歷，就可以訪問(wèn)圖中所有的頂點(diǎn)，則該圖一定是連通的。（√）二、填空題圖常用的存儲(chǔ)方式有鄰接矩陣和鄰接表等。圖的遍歷有：深度優(yōu)先搜和廣度優(yōu)先搜等方法。有n條邊的無(wú)向圖鄰接矩陣中，1的個(gè)數(shù)是2n。有向圖的邊也稱為弧。圖的鄰接矩陣表示法是表示頂點(diǎn)之間相鄰關(guān)系的矩陣。有向圖G用鄰接矩陣存儲(chǔ)，其第i行的所有元素之和等于頂點(diǎn)i的出度。n個(gè)頂占e條邊的圖若采用鄰接矩陣存儲(chǔ)，則空間復(fù)雜度為：On2。n個(gè)頂占e條邊的圖若采用鄰接表存儲(chǔ)，則空間復(fù)雜度為：O(n+e)。設(shè)有一稀疏圖G，則G采用鄰接表存儲(chǔ)比較節(jié)省空間。設(shè)有一稠密圖G，則G采用鄰接矩陣存儲(chǔ)比較節(jié)省空間。圖的逆鄰接表存儲(chǔ)結(jié)構(gòu)只適用于有向圖。n個(gè)頂點(diǎn)的完全無(wú)向圖有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)僅被訪問(wèn)一次，稱這一過(guò)程為圖的遍歷。無(wú)向圖的鄰接矩陣一定是對(duì)稱矩陣。一個(gè)連通網(wǎng)的最小生成樹是該圖所有生成樹中權(quán)最小的生成樹。若要求一個(gè)稠密圖G的最小生成樹，最好用Prim算法來(lái)求解。三、選擇題在一個(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)的無(wú)向圖中，要連通全部頂點(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è)無(wú)向連通圖的最小生成樹（A）。A.只有一棵B.一棵或多棵C.一定有多棵D.可以不存在無(wú)向圖頂點(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)的無(wú)向圖的鄰接矩陣是用（B）數(shù)組存儲(chǔ)。A.一維B.n行n列C.任意行n列D.n行任意列對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，采用鄰接表表示，則表頭向量大小為（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.無(wú)環(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ǔ)結(jié)構(gòu)的敘述中正確的是（A）。A.用鄰接矩陣存儲(chǔ)圖，占用空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)B.用鄰接矩陣存儲(chǔ)圖，占用空間大小只與圖中邊數(shù)有關(guān)，而與頂點(diǎn)數(shù)無(wú)關(guān)C.用鄰接存儲(chǔ)圖，占用空間大小只與圖中頂點(diǎn)數(shù)有關(guān)，而與邊數(shù)無(wú)關(guān)D.用鄰接存儲(chǔ)圖，占用空間大小只與圖中邊數(shù)有關(guān)，而與頂點(diǎn)數(shù)無(wú)關(guān)連通分量是（C）的極大連通子圖。樹B.圖C.無(wú)向圖D.有向圖第9章查找一、判斷題二分查找法要求待查表的關(guān)鍵字值必須有序。（√）對(duì)有序表而言采用二分查找總比采用順序查找法速度快。（×）在二叉排序樹中，根結(jié)點(diǎn)的值都小于孩子的結(jié)點(diǎn)的值。（×）散列存儲(chǔ)法的基本思想是由關(guān)鍵字的值的決定數(shù)據(jù)的存儲(chǔ)地址。（√）哈希表是一種將關(guān)鍵字轉(zhuǎn)換為存儲(chǔ)地址的存儲(chǔ)方法。（√）選擇好的哈希函數(shù)就可以避免沖突的發(fā)生。（×）在有序的順序表和有序的鏈表上，均可以采用二分查找來(lái)提高查找速度。（×）采用分塊查找，既有實(shí)現(xiàn)線性表所希望的查找速度，又能適應(yīng)動(dòng)態(tài)變化的需要。（√）哈希查找的效率主要取決于哈希表構(gòu)造時(shí)選取的哈希函數(shù)和處理沖突的方法。（√）在二叉排序樹上刪除一個(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ì)于長(zhǎng)度為n的線性表，若進(jìn)行順序查找，則時(shí)間復(fù)雜度為O(n)。對(duì)于長(zhǎng)度為n的線性表，若采用二分查找，則時(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)行比較，若比根結(jié)點(diǎn)值小，則繼續(xù)在左子樹中查找。二叉排序樹是一種動(dòng)態(tài)查找表。哈希表是按散列存儲(chǔ)方式構(gòu)造的存儲(chǔ)結(jié)構(gòu)。哈希法既是一種存儲(chǔ)方法，又是一種查找方法。散列表的查找效率主要取決于散列表造表時(shí)選取的散列函數(shù)和處理沖突的方法。設(shè)散列函數(shù)H和鍵值k1，k2，若k1≠k2，而H（k2）H（k2），則稱這種現(xiàn)象為沖突。處理沖突的兩類主要方法是開放定地址法和拉鏈法（或鏈地址法）。散列表（或散列）查找法的平均查找長(zhǎng)度與元素個(gè)數(shù)n無(wú)關(guān)。在哈希函數(shù)H（key）=key%P中，P一般應(yīng)取質(zhì)數(shù)。在查找過(guò)程中有插入元素或刪除元素操作的，稱為動(dòng)態(tài)查找。各結(jié)點(diǎn)左、右子樹深度之差的絕對(duì)值至多為1的二叉樹稱為平衡二叉樹。三、選擇題查找表以（A）為查找結(jié)構(gòu)。A.集合B.圖C.樹D.文件順序查找法適合于存儲(chǔ)結(jié)構(gòu)為（B）的線性表。A.散列存儲(chǔ)B.順序存儲(chǔ)或鏈接存儲(chǔ)C.壓縮存儲(chǔ)D.索引存儲(chǔ)在表長(zhǎng)為n的鏈表中進(jìn)行線性查找，它的平均查找長(zhǎng)度為（B）。A.ASL=nB.ASL=(n+1)/2C.ASL=n+1D.ASL≈log2n對(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.平均查找長(zhǎng)度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}，若查找表中元素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è)長(zhǎng)度為12的有序表，按二分查找法對(duì)其進(jìn)行查找，在表內(nèi)各元素等概率情況下查找成功所需的平均比較次數(shù)為（B）。A.35/12B.37/12C.39/12D.43/12采用分塊查找時(shí)，若線性表共有625個(gè)元素，查找生個(gè)元素等概率相等，假設(shè)采用順序查找來(lái)確定結(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è)哈希表長(zhǎng)m=14，哈希函數(shù)H(key)=key%11。表中已有4個(gè)結(jié)點(diǎn)：addr(15)=4addr(38)=5addr(61)=6addr(84)=7其余地址為空。如用二次探測(cè)再散列處理沖突，關(guān)鍵字為49的結(jié)點(diǎn)的地址是（D）。A．8B．3C．5D．9對(duì)包含n個(gè)元素的散列表進(jìn)行查找。平均查找長(zhǎng)度為（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è)元素的鍵值相同在查找過(guò)程中，不做增加、刪除或修改的查找稱為（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）。（√）堆排序所需的時(shí)間與待排序的記錄個(gè)數(shù)無(wú)關(guān)。（×）當(dāng)待排序的元素個(gè)數(shù)很多時(shí)，為了交換元素的位置占用較多的時(shí)間，這是影響時(shí)間復(fù)雜度的主要因素。√）快速排序在任何情況下都比其他排序方法速度快。（×）對(duì)快速排序來(lái)說(shuō)，初始序列為正序或反序都是最壞情況。（√）采用歸并排序可以實(shí)現(xiàn)外排序。（√）采用希爾排序時(shí)，若原始關(guān)鍵字的排列雜亂無(wú)序，則效率最高。（√）二、填空題大多數(shù)排序算法都有兩個(gè)基本的操作：比較和移動(dòng)。評(píng)價(jià)排序算法優(yōu)劣的主要標(biāo)準(zhǔn)是時(shí)間復(fù)雜度和算法所需的附加空間。根據(jù)被處理的數(shù)據(jù)在計(jì)算機(jī)中使用不同的存儲(chǔ)設(shè)備，排序可分為內(nèi)排序和外排序。外排序是指在排序過(guò)程中，數(shù)據(jù)的主要部分存在計(jì)算機(jī)的外存中。對(duì)n個(gè)關(guān)鍵字進(jìn)行冒泡排序，其可能的最小比較次數(shù)為