江蘇師范大學(xué)數(shù)據(jù)結(jié)構(gòu)總復(fù)習(xí)總結(jié)

復(fù)習(xí)第一章緒論本章要點(diǎn)：（1）有關(guān)數(shù)據(jù)結(jié)構(gòu)的基本概念，包括：數(shù)據(jù)、數(shù)據(jù)對(duì)象、數(shù)據(jù)元素或者數(shù)據(jù)成員、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)類(lèi)型等；數(shù)據(jù)抽象、抽象數(shù)據(jù)類(lèi)型、數(shù)據(jù)結(jié)構(gòu)的抽象層次等。（2）算法設(shè)計(jì)與分析：算法的定義和算法的特性算法的設(shè)計(jì)方法：包括問(wèn)題解決的基本思路、算法設(shè)計(jì)的基本步驟、算法的實(shí)現(xiàn)算法的性能分析：包括算法的性能標(biāo)準(zhǔn)，算法的后期測(cè)試；算法的事情估計(jì)；空間復(fù)雜度度量；時(shí)間復(fù)雜度度量；時(shí)間復(fù)雜度的漸進(jìn)表示法1、順序存儲(chǔ)結(jié)構(gòu)中數(shù)據(jù)元素間的邏輯結(jié)構(gòu)是由（）來(lái)表示的，鏈接存儲(chǔ)結(jié)構(gòu)中數(shù)據(jù)元素間的邏輯關(guān)系是由（）表示。A指針B邏輯順序C存儲(chǔ)位置D問(wèn)題上下文2、算法的時(shí)間復(fù)雜度與（）有關(guān)。A問(wèn)題規(guī)模B計(jì)算機(jī)硬件的運(yùn)行速度C源程序的長(zhǎng)度D編譯后執(zhí)行程序的質(zhì)量3、某算法的時(shí)間復(fù)雜度為O(n2)，表明該算法（）A問(wèn)題規(guī)模是n2B問(wèn)題規(guī)模與n2成正比C執(zhí)行時(shí)間等于n2D執(zhí)行時(shí)間與n2成正比CAAD4、算法是一個(gè)有窮的指令集，它為解決某一特定任務(wù)規(guī)定了一個(gè)運(yùn)算序列。它應(yīng)當(dāng)具有輸入、輸出、（）、有窮和可行性等特性。5、算法效率的度量分為（）和（）。前者主要通過(guò)在算法的某些部位插裝時(shí)間函數(shù)來(lái)測(cè)定算法完成某一個(gè)規(guī)定功能所需要的時(shí)間。而后者不實(shí)際運(yùn)行算法，它是分析算法中語(yǔ)句的執(zhí)行次數(shù)來(lái)度量算法的時(shí)間復(fù)雜度。6、程序所需要的存儲(chǔ)空間包含兩個(gè)部分（）和（）。前者空間的大小與輸入輸出數(shù)據(jù)的個(gè)數(shù)多少，數(shù)值大小無(wú)關(guān)。后者空間主要包括其大小與問(wèn)題規(guī)模有關(guān)的成分變量所占空間等等。確定性事后測(cè)量事前估計(jì)固定部分可變部分7、有實(shí)現(xiàn)同一功能的兩個(gè)算法A1和A2，其中A1的漸進(jìn)時(shí)間復(fù)雜度是，A2的漸進(jìn)時(shí)間復(fù)雜度為。僅就時(shí)間復(fù)雜度而言，具體分析這兩個(gè)算法哪個(gè)好。比較算法好壞，需要比較兩個(gè)函數(shù)2n和n2當(dāng)n=1時(shí)，21>12，算法A2好于A1當(dāng)n=2時(shí)，22=22，算法A2與A1相當(dāng)當(dāng)n=3時(shí)，23<32，算法A1好于A2當(dāng)n=4時(shí)，24>42，算法A2好于A1當(dāng)n>4時(shí)，24>n2，算法A2好于A1當(dāng)n→

時(shí)，算法A2在時(shí)間上好于A1第二章線性表本章要點(diǎn)：（1）線性表的定義和特點(diǎn)，包括：線性表的定義，注意幾個(gè)關(guān)鍵詞：有窮、序列、數(shù)據(jù)元素；線性表特點(diǎn)：唯一前驅(qū)和唯一后繼。③線性表元素類(lèi)型④線性表與向量（一維數(shù)組）的關(guān)系，注意它們間的異同⑤線性表的操作歸類(lèi)：包括訪問(wèn)操作（搜索，遍歷）、維護(hù)操作（插入、刪除），設(shè)置操作（初始化或者置空），判斷操作（判空、判滿(mǎn)）、游標(biāo)操作（前驅(qū)、后繼）第二章線性表本章要點(diǎn)：（2）線性表的順序存儲(chǔ)表示：順序表的靜態(tài)和動(dòng)態(tài)的C結(jié)構(gòu)定義，以及C++類(lèi)定義順序表的特點(diǎn)：即元素的邏輯順序和物理順序的一致性順序表的主要操作，如插入、刪除、搜索等的實(shí)現(xiàn)算法④掌握主要功能的關(guān)鍵語(yǔ)句：如遍歷整個(gè)順序表、遍歷到指定節(jié)點(diǎn)的語(yǔ)句；插入、刪除時(shí)成片移動(dòng)元素的語(yǔ)句等⑤掌握簡(jiǎn)單的效率分析，包括搜索算法中數(shù)據(jù)比較次數(shù)的計(jì)算，插入、刪除的數(shù)據(jù)移動(dòng)次數(shù)的計(jì)算第二章線性表本章要點(diǎn)：（3）線性表的鏈接存儲(chǔ)表示：?jiǎn)捂湵淼腃結(jié)構(gòu)定義，以及C++類(lèi)定義單鏈表的特點(diǎn)：即元素的邏輯順序和物理順序的不一致性單鏈表的主要操作，如插入、刪除、搜索等的實(shí)現(xiàn)算法。注意無(wú)附加頭結(jié)點(diǎn)和帶附加頭結(jié)點(diǎn)的單鏈表上操作實(shí)現(xiàn)的差異④掌握主要功能的關(guān)鍵語(yǔ)句：如遍歷整個(gè)順序表、遍歷到指定節(jié)點(diǎn)的語(yǔ)句；無(wú)頭結(jié)點(diǎn)單鏈表的表頭插入、刪除；帶頭結(jié)點(diǎn)單鏈表的搜索操作；帶頭結(jié)點(diǎn)單鏈表的插入、刪除運(yùn)算以及單鏈表的創(chuàng)建、釋放、逆置、分裂、合并等運(yùn)算⑤有序單鏈表的主要操作：如搜索、插入、刪除等，以及分裂，合并，剔除重復(fù)元素等運(yùn)算1、在下列關(guān)于線性表的敘述中正確的是（）

A線性表的邏輯順序和物理順序總是一致的

B線性表的順序存儲(chǔ)表示優(yōu)于鏈?zhǔn)酱鎯?chǔ)表示

C線性表若采用鏈?zhǔn)酱鎯?chǔ)表示時(shí)，所有存儲(chǔ)單元的地址可連續(xù)或者可不連續(xù)

D每種數(shù)據(jù)結(jié)構(gòu)都應(yīng)具備三種基本運(yùn)算——插入、刪除和查找2、若長(zhǎng)度為n的非空線性表采用順序存儲(chǔ)結(jié)構(gòu)，在表的i個(gè)位置插入一個(gè)數(shù)據(jù)元素，i的合法值應(yīng)該是（）

Ai>0B1<=i<=nC0<=i<=n-1D0<=i<=n3、對(duì)于順序存儲(chǔ)的線性表，其算法的時(shí)間復(fù)雜度為O(1)的運(yùn)算應(yīng)（）

A將n個(gè)元素從小到大排序

B從線性表中刪除第i個(gè)元素（1<=i<=n）

C查找第i個(gè)元素（1<=i<=n）

D在第i個(gè)元素（1<=i<=n）后插入一個(gè)新元素4、若長(zhǎng)度為n的順序表的表尾插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為（）

AO(n)BO(1)CO(n2)DO(log2n)5、已知L是帶表頭的單鏈表，L是表頭指針，則摘除首元結(jié)點(diǎn)的語(yǔ)句是（）

AL=L->linkBL->link=L->link->linkCL=L->link->linkDL->link=L6、已知單鏈表A長(zhǎng)度為m，單鏈表B長(zhǎng)度為n，若將B接在A的末尾，在沒(méi)有鏈尾指針的情形下，算法的時(shí)間復(fù)雜度應(yīng)為（）

AO(1)BO(m)CO(n)DO(m+n)7、從一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中查找其值等于x的結(jié)點(diǎn)時(shí)，在查找成功的情況下，平均需要比較（）個(gè)結(jié)點(diǎn)。

AnBn/2C(n-1)/2D(n+1)/28、在一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表中插入一個(gè)新結(jié)點(diǎn)，并可以不保持原有順序的算法的時(shí)間復(fù)雜度是（）

AO(1)BO(n)CO(n2)DO(nlog2n)9、給定有n個(gè)元素的一維數(shù)組，建立一個(gè)有序單鏈表的時(shí)間復(fù)雜度是（）。

AO(1)BO(n)CO(n2)DO(nlog2n)判斷一個(gè)帶附加頭結(jié)點(diǎn)的雙向循環(huán)鏈表L是否對(duì)稱(chēng)相等的算法如下所示，請(qǐng)?jiān)谒惴ㄖ械腳_____中填入正確的語(yǔ)句boolsymmetry(DblListDL){ boolsym=true; DblNode*p=DL->rLink,*q=DL->lLink; while(p!=q||p->lLink!=q||

) if(p->data==q->data){______________________________ } else sym=false; returnsym;}sym=truep=p->rLinkq=q->lLink第三章棧和隊(duì)列本章要點(diǎn)：（1）棧的隊(duì)列定義和特點(diǎn)，包括：棧的定義，注意棧頂進(jìn)出、棧底不能進(jìn)出，順序存取的概念，棧的先進(jìn)后出的特點(diǎn)隊(duì)列的定義，注意隊(duì)頭出、隊(duì)尾進(jìn)、順序存取的概念，隊(duì)列的先進(jìn)先出的特點(diǎn)③注意區(qū)分棧、隊(duì)列、向量。棧的隊(duì)列是順序存取，向量是直接存?、苓M(jìn)棧、出棧、判空、置空操作的使用⑤?？?、隊(duì)空在實(shí)際使用時(shí)不算出錯(cuò)，它標(biāo)志某種處理的結(jié)束⑥棧滿(mǎn)、隊(duì)滿(mǎn)在實(shí)際使用時(shí)用力判斷可能的出錯(cuò)第二章線性表（2）棧的存儲(chǔ)表示及其基本運(yùn)算的實(shí)現(xiàn)：順序棧的類(lèi)結(jié)構(gòu)定義順序棧的棧頂指針實(shí)際指示的位置，以及如何用棧頂指針表示順序棧的棧空、棧滿(mǎn)條件順序棧的進(jìn)棧、出棧運(yùn)算的實(shí)現(xiàn)。注意操作的前置條件和后置條件，以及在參數(shù)表中應(yīng)用參數(shù)的作用④雙棧共用一個(gè)數(shù)組的進(jìn)棧、退棧、置空棧、判?？账惴ㄒ约皸M(mǎn)、?？諚l件⑤鏈?zhǔn)綏５慕Y(jié)構(gòu)定義，注意鏈?zhǔn)綏５臈ｍ斨羔槍?shí)際指示的位置⑥鏈?zhǔn)綏５倪M(jìn)棧、出棧運(yùn)算的實(shí)現(xiàn)，注意鏈?zhǔn)綏５臈？諚l件⑦棧滿(mǎn)時(shí)的擴(kuò)充算法第二章線性表（3）隊(duì)列的存儲(chǔ)表示及其基本運(yùn)算的實(shí)現(xiàn)循環(huán)隊(duì)列的雷結(jié)果定義，注意對(duì)頭指針和隊(duì)尾指針進(jìn)退的方向，以及如何用這兩個(gè)指針判對(duì)空和隊(duì)列滿(mǎn)循環(huán)隊(duì)列的進(jìn)隊(duì)、出隊(duì)的取模操作的實(shí)現(xiàn)使用對(duì)頭指針front和隊(duì)列長(zhǎng)度length實(shí)現(xiàn)循環(huán)隊(duì)列時(shí)進(jìn)隊(duì)列和出隊(duì)列的操作④鏈?zhǔn)疥?duì)列的類(lèi)結(jié)構(gòu)定義⑤鏈?zhǔn)疥?duì)列的進(jìn)隊(duì)和出隊(duì)列操作的實(shí)現(xiàn)⑥

雙端隊(duì)列的進(jìn)隊(duì)、出隊(duì)運(yùn)算的實(shí)現(xiàn)⑦優(yōu)先級(jí)隊(duì)列的存儲(chǔ)結(jié)構(gòu)第二章線性表（4）棧的應(yīng)用1、已知一個(gè)棧的進(jìn)棧序列為1,2,3，…,n，其輸出序列的第一個(gè)元素是i，則第j個(gè)出戰(zhàn)元素是（）

Aj-iBn-iCj-i+1D不確定2、已知一個(gè)棧的進(jìn)棧序列為1,2,3，…,n，其輸出序列是p1,p2,p3,…,pn。若p1=n，則pi的值是（）

AiBn-iCn-i+1D不確定3、已知一個(gè)棧的進(jìn)棧序列為1,2,3，…,n，其輸出序列是p1,p2,p3,…,pn。若p1=3，則p2的值是（）

A一定是2B一定是1C可能是1D可能是24、將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)的非遞歸算法時(shí)，除了單向遞歸和尾遞歸的情況外，通常需要使用（）保存中間結(jié)果

A鏈表B棧C隊(duì)列D順序表5、設(shè)求解某問(wèn)題的遞歸算法如下voidF(intn){ if(n==1)Move(1); else{ F(n-1); Move(n); F(n-1); }};求解算法的計(jì)算時(shí)間，僅考慮算法move所作的計(jì)算，且move為常數(shù)級(jí)算法。則算法F的計(jì)算時(shí)間T(n)的遞推關(guān)系為（）AT(n)=T(n-1)+1BT(n)=2T(n-1)

CT(n)=2T(n-1)+1DT(n)=2T(n+1)+16、一個(gè)隊(duì)列的進(jìn)隊(duì)順序是1,2,3,4，則該隊(duì)可能的輸出序列是（）

A1,2,3,4B1,3,2,4C1,4,2,3D4,3,2,17、犧牲一個(gè)單元區(qū)分隊(duì)空、隊(duì)滿(mǎn)條件的循環(huán)隊(duì)列的隊(duì)滿(mǎn)條件是（）

A(q.rear+1)%maxSize==(q.front+1)%maxSize

B(q.front+1)%maxSize==q.rearC(q.rear+1)%maxSize==q.frontDq.frong==q.rear8、設(shè)循環(huán)隊(duì)列存儲(chǔ)數(shù)組的下標(biāo)是0～maxSize-1，其隊(duì)尾指針和隊(duì)頭指針?lè)謩e為rear和front，則隊(duì)列中的元素個(gè)數(shù)為（）

Aq.rear-q.front

Bq.rear-q.front+1C(q.rear-q.front)%maxSize+1Dq.rear-q.front+maxSize)%maxSize9、設(shè)棧S的隊(duì)列Q的初始狀態(tài)為空，元素a,b,c,d,e,f,g依次進(jìn)棧棧S。如果每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出隊(duì)的順序?yàn)閎,d,e,f,e,a,g，則棧S的容量至少是（）

A1B2C3D4第四章：數(shù)組和廣義表1要點(diǎn)：

確定數(shù)組元素的三要素：行號(hào)、列號(hào)、元素值

數(shù)組元素的存放地址計(jì)算2、順序表：順序表的定義、搜索、插入與刪除要點(diǎn)：

順序表搜索算法、平均比較次數(shù)的計(jì)算

插入與刪除算法、平均移動(dòng)次數(shù)的計(jì)算3、字符串：字符串的定義及其操作的實(shí)現(xiàn)要點(diǎn)：

串重載操作的定義與實(shí)現(xiàn)4.廣義表：廣義表定義、長(zhǎng)度、深度、表頭、表尾1、設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A，采用下三角陣壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第1個(gè)元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為（）。

A.13B.33C.18D.402.將一個(gè)n*n的對(duì)稱(chēng)矩陣A的下三角部分（包括對(duì)角線）以行序存儲(chǔ)到一維數(shù)組T中，A[0][0]存放于T[0]中，則對(duì)任一上三角元素A[i][j]對(duì)應(yīng)T[k]的下標(biāo)k是（）。

A.i（i+1）/2+jB.j（j+1）/2+iC.i（j-i）/2+1D.j（i-1）/2+13．若廣義表L=(a,(b,c,d))，則GetHead（L）=

，GetTail（L）=第5章樹(shù)1、樹(shù)：樹(shù)的定義、樹(shù)的基本運(yùn)算要點(diǎn)：

樹(shù)的分層定義是遞歸的

樹(shù)中結(jié)點(diǎn)個(gè)數(shù)與高度的關(guān)系2、二叉樹(shù)：二叉樹(shù)定義、二叉樹(shù)的基本運(yùn)算要點(diǎn)：

二叉樹(shù)性質(zhì)、二叉樹(shù)中結(jié)點(diǎn)個(gè)數(shù)與高度的關(guān)系、不同種類(lèi)的二叉樹(shù)棵數(shù)、完全二叉樹(shù)的順序存儲(chǔ)、完全二叉樹(shù)的雙親、子女和兄弟的位置，二叉樹(shù)的前序·中序·后序遍歷的遞歸算法和使用棧的非遞歸算法二叉樹(shù)的層次遍歷算法

中序線索化二叉樹(shù)、前驅(qū)與后繼的查找方法、建立中序線索化二叉樹(shù)的算法3、霍夫曼樹(shù)：霍夫曼樹(shù)的構(gòu)造方法、霍夫曼編碼、帶權(quán)路徑長(zhǎng)度的計(jì)算4、樹(shù)與森林要點(diǎn)：

樹(shù)的廣義表表示、樹(shù)的雙親表示、樹(shù)的左子女-右兄弟表示

樹(shù)、森林與二叉樹(shù)的對(duì)應(yīng)關(guān)系

樹(shù)的先根·后根·層次遍歷算法 1、用順序存儲(chǔ)的方法，將有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中所有結(jié)點(diǎn)按層逐個(gè)順序存放在一維數(shù)組R[n]中，若結(jié)點(diǎn)R[i]有左子女，則其左子女是（）；若結(jié)點(diǎn)R[i]有右子女，則其右子女是（）。

AR[2i-1]BR[2i] CR[2i+1] DR[2i+2]CD2、用順序存儲(chǔ)的方法，將有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)中所有結(jié)點(diǎn)按層逐個(gè)順序存放在一維數(shù)組R[n]中，若結(jié)點(diǎn)R[i]有雙親（即父結(jié)點(diǎn)），則其雙親是（）；該樹(shù)中編號(hào)最大的非葉結(jié)點(diǎn)是（）。

AR[(i-1)/2]BR[i/2] CR[n/2-1] DR[n/2]AC3、一個(gè)深度為k且只有k個(gè)結(jié)點(diǎn)的二叉樹(shù)按照完全二叉樹(shù)順序存儲(chǔ)的方式存放于一個(gè)一維數(shù)組R[n]中，那么n最大為（）。

A2kB2k+1 C2k-1 D2kC4、在一棵二叉樹(shù)的二叉鏈表中，空指針數(shù)等于非空指針數(shù)加（）。

A2B1 C0 D-1A5、二叉樹(shù)的葉結(jié)點(diǎn)在前序、中序和后序遍歷過(guò)程中的相對(duì)順序（）。

A發(fā)生改變B不發(fā)生改變

C無(wú)法確定 D以上均不正確B6、給定二叉樹(shù)如圖所示。設(shè)V代表二叉樹(shù)的根，L代表根結(jié)點(diǎn)的左子樹(shù)，R代表根結(jié)點(diǎn)的右子樹(shù)。若遍歷后的結(jié)點(diǎn)序列為3175624，則其遍歷方式為（）

ALRVBVRL CRLV DRVLC7、設(shè)n/m為一棵二叉樹(shù)上的兩個(gè)結(jié)點(diǎn)，在中序遍歷時(shí)，n在m前的條件是（）。

An在m的右方Bn是m的祖先

Cn在m左方 Dn是m的子孫C12345678、在二叉樹(shù)中有兩個(gè)結(jié)點(diǎn)m和n，如果m是n的祖先，使用（）可以找到從m到n的路經(jīng)。

A前序遍歷B中序遍歷

C后序遍歷 D層次序遍歷C9、設(shè)一棵二叉樹(shù)的前序序列為abdec，中序遍歷為dbeac，則該二叉樹(shù)的后序遍歷序列為（）。

AabdecBdebac Cdebca DabedcC10、設(shè)結(jié)點(diǎn)x和y是二叉樹(shù)中任意的兩個(gè)結(jié)點(diǎn)。在該二叉樹(shù)的前序序列中x在y之前，在其后序序列中x在y之后，則x和y的關(guān)系式（）。

Ax是y的左兄弟Bx是y的右兄弟

Cx是y的祖先 Dx是y的子孫C11、線索二叉樹(shù)是一種（）結(jié)構(gòu)。

A邏輯B邏輯和存儲(chǔ)C物理 D線性C12、n個(gè)結(jié)點(diǎn)的線索二叉樹(shù)中，線索的數(shù)目是（）。

An-1Bn+1 C2n D2n-1B13、在線索二叉樹(shù)中，指針t所指結(jié)點(diǎn)的左子樹(shù)為空的充要條件是（）。

At->leftChild==NULLBt->ltag==1 Ct->ltag==1&&t->leftChild==NULLD以上都不對(duì)C11、線索二叉樹(shù)是一種（）結(jié)構(gòu)。

A邏輯B邏輯和存儲(chǔ)C物理 D線性C12、n個(gè)結(jié)點(diǎn)的線索二叉樹(shù)中，線索的數(shù)目是（）。

An-1Bn+1 C2n D2n-1B13、在線索二叉樹(shù)中，指針t所指結(jié)點(diǎn)的左子樹(shù)為空的充要條件是（）。

At->leftChild==NULLBt->ltag==1 Ct->ltag==1&&t->leftChild==NULLD以上都不對(duì)C14、將下圖中的二叉樹(shù)按中序線索化，結(jié)點(diǎn)e的右指針和結(jié)點(diǎn)g的左指針?lè)謩e指向（）

Aa,dBb,c Cd,a Dc,aD15、在一非空二叉樹(shù)的中序序列中，根結(jié)點(diǎn)的右邊（）。

A只有右子樹(shù)上的所有結(jié)點(diǎn)

B只有右子樹(shù)的部分結(jié)點(diǎn)

C只有左子樹(shù)上的所有結(jié)點(diǎn)

D只有左子樹(shù)上的部分結(jié)點(diǎn)Aabcdegf16、設(shè)一棵具有n個(gè)結(jié)點(diǎn)，則它所有結(jié)點(diǎn)的度數(shù)之和是（）。

A2nB2n-1Cn+1 Dn-1D17、設(shè)一棵樹(shù)中只有度0和度為3的結(jié)點(diǎn)，則該樹(shù)的第i層(i≥1)的結(jié)點(diǎn)個(gè)數(shù)最多為（）。

A3i-1-1B3i-1 C3i-1 D3iC18、設(shè)森林F對(duì)應(yīng)的二叉樹(shù)為B，它有m個(gè)結(jié)點(diǎn)。B的根為p，p的右子樹(shù)中結(jié)點(diǎn)個(gè)數(shù)為n，則森林F中第一棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)是（）。

Am-nBm-n-1Cn+1D無(wú)法確定A19、如果T2是由有序樹(shù)T轉(zhuǎn)換成的二叉樹(shù)，那么T中結(jié)點(diǎn)的先根遍歷順序?qū)?yīng)T2中的結(jié)點(diǎn)的（）遍歷順序。

A前序B中序C后序 D層次序A20、設(shè)森林中有三棵樹(shù)，第1,2,3棵樹(shù)中的結(jié)點(diǎn)個(gè)數(shù)分別為m1,m2和m3。那么在由森林轉(zhuǎn)化成的二叉樹(shù)中根結(jié)點(diǎn)的右子樹(shù)上有（）個(gè)結(jié)點(diǎn)。

Am1+m2Bm2+m3Cm3+m1 Dm1+m2+m3B21、將森林轉(zhuǎn)化為對(duì)應(yīng)的二叉樹(shù)，若在二叉樹(shù)中，結(jié)點(diǎn)u是結(jié)點(diǎn)v的雙親結(jié)點(diǎn)的雙親結(jié)點(diǎn)，則在原來(lái)的森林中，u和v可能具有的關(guān)系是（）。

Ⅰ父子關(guān)系Ⅱ兄弟關(guān)系

Ⅲu的雙親結(jié)點(diǎn)與v的雙親結(jié)點(diǎn)是兄弟關(guān)系

A只有ⅠBⅠ和ⅡCⅠ和Ⅲ D全部都有B523417869uvuvuv22、設(shè)一棵樹(shù)的廣義表表示為A(B(E),C(F(H,I,J),G),D)，則該樹(shù)的度為（），樹(shù)的深度為（），葉節(jié)點(diǎn)個(gè)數(shù)為（）。

A3B4C5 D6A21、設(shè)F是一個(gè)森林，B是由F轉(zhuǎn)換得到的二叉樹(shù)，F(xiàn)中有n個(gè)非葉結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（）個(gè)。

An-1BnCn+1 Dn+2CBD六七八章復(fù)習(xí)第六章有關(guān)散列的知識(shí)：散列方法的實(shí)質(zhì)散列函數(shù)的構(gòu)造方法出現(xiàn)沖突的解決方法1、散列法存儲(chǔ)的基本思想是根據(jù)（）來(lái)決定元素的存儲(chǔ)地址的。

A元素的序號(hào) B元素個(gè)數(shù)

C關(guān)鍵碼值 D非碼屬性2、設(shè)一個(gè)散列表中有n個(gè)元素，用散列法進(jìn)行搜索的平均搜索長(zhǎng)度是（）

AO(1)BO(n) CO(log2n) DO(n2)3、使用散列函數(shù)將元素的關(guān)鍵碼值映射為散列地址時(shí)，常會(huì)發(fā)生沖突。此時(shí)的沖突是指（）。

A兩個(gè)元素具有相同的序號(hào)

B兩個(gè)元素的關(guān)鍵碼值不同，而非關(guān)鍵碼值相同

C不同關(guān)鍵碼值對(duì)應(yīng)到相同的存儲(chǔ)地址

D裝載因子過(guò)大，數(shù)據(jù)元素過(guò)多CAC4、計(jì)算出的地址分布最均勻的散列函數(shù)是（）

A數(shù)字分析法 B除留余數(shù)法

C平方取中法 D折疊法5、除留余數(shù)法的基本思路是：設(shè)散列表的地址空間為0～m-1，元素的關(guān)鍵碼值為k，用p去除k，將余數(shù)作為元素的散列地址，即h(k)=k%p，為了減少發(fā)生沖突的可能性，一般取p為（）

Am B小于或等于m的最大素?cái)?shù)

C大于m的最小素?cái)?shù) D小于或等于m的最大合數(shù)6、已知一個(gè)線性序列{38,25,74,63,52,48}，假定采用散列函數(shù)h(key)=key%7計(jì)算散列地址，并散列存儲(chǔ)在散列表A[10]中，若采用線性探查法解決沖突，則在該散列表上進(jìn)行等概率成功搜索的評(píng)價(jià)搜索長(zhǎng)度為（）。

A1.5B1.67 C1.83 D2.24BBC7、假設(shè)有k個(gè)關(guān)鍵碼值互為同義詞，若用線性探查法把這k個(gè)關(guān)鍵碼值存入散列表，至少要進(jìn)行（）次探查。

Ak-1

Bk

Ck+1

Dk(k+1)/25、設(shè)散列表長(zhǎng)m=14，散列函數(shù)H(key)=key%11,。表中已經(jīng)有4個(gè)節(jié)點(diǎn)，地址分別為addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7，其余地址為空。如用二次探查法解決沖突，關(guān)鍵碼值為49的散列地址為（）

A8 B3

C5

D9DD6、設(shè)散列表為HT[0..12]，即表的大小為m=13?，F(xiàn)采用雙散列法解決沖突。散列函數(shù)和再散列函數(shù)分別為：H0(key)=key%13Hi=(Hi-1+Rev(key+1)%11+1)%13其中函數(shù)Rev(x)表示顛倒10進(jìn)行x的各位，如Rev(37)=73,Rev(7)=7。若插入的關(guān)鍵碼值序列為{2,8,31,20,70,59,25,28}。

（1）試畫(huà)出插入這8個(gè)關(guān)鍵碼值后的散列表（2）計(jì)算搜索成功的評(píng)價(jià)搜索長(zhǎng)度ASLsucc2023/10/20講授目錄7.1靜態(tài)搜索結(jié)構(gòu)7.2二叉搜索樹(shù)7.3AVL樹(shù)7.4伸展樹(shù)7.5紅黑樹(shù)1、在順序存儲(chǔ)的線性表R[30]上進(jìn)行順序搜索的平均搜索長(zhǎng)度為（）。

A15

B15.5

C16

D202、在對(duì)長(zhǎng)度為n的順序存儲(chǔ)的有序表進(jìn)行折半搜索，對(duì)應(yīng)的折半搜索判定樹(shù)的高度為（）AnB

log2n

C

log2(n+1)

D

log2(n+1)

3、已知有序順序表(13,18,24,35,47,50,62,83,90,115,134)，當(dāng)用順序搜索法搜索值為83的元素時(shí)，搜索成功的數(shù)據(jù)比較次數(shù)為（）。

A5

B6

C7

D84、利用逐個(gè)數(shù)據(jù)插入的方法建立序列{35,45,25,55,50,10,15,30,40,20}對(duì)應(yīng)的二叉搜索樹(shù)后，搜索元素20需要進(jìn)行（）次元素之間的比較。A5

B4

C7

D10BDDA5、如圖所示的AVL樹(shù)中插入關(guān)鍵碼48，得到一棵新的AVL樹(shù)，在這C新的AVL樹(shù)中，關(guān)鍵碼37所在節(jié)點(diǎn)的左右子女節(jié)點(diǎn)中保存的關(guān)鍵碼分別是（）。

A13,48

B24,48

C24,53 D24,906、將關(guān)鍵碼DEC,FEB,NOV,OCT,JUL,SEP,AUG,APR,MAR,MAY,JUN,JAN依次插入一棵初始為空的AVL樹(shù)中，畫(huà)出每插入一個(gè)關(guān)鍵碼值后的AVL樹(shù)，并標(biāo)明平衡旋轉(zhuǎn)的類(lèi)型。并給出等概率時(shí)搜索成功的平均搜索長(zhǎng)度和搜索不成功時(shí)的平均搜索長(zhǎng)度。C241353379048講授內(nèi)容8.1圖的基本概念8.2圖的存儲(chǔ)結(jié)構(gòu)8.3圖的遍歷8.4最小生成樹(shù)8.5最短路徑8.6用頂點(diǎn)表示活動(dòng)的網(wǎng)絡(luò)（AOV網(wǎng)絡(luò)）8.7用邊表示活動(dòng)的網(wǎng)絡(luò)（AOE網(wǎng)絡(luò)）教學(xué)目標(biāo)：⒈了解圖的定義及其存儲(chǔ)結(jié)構(gòu)。⒉掌握?qǐng)D的深度優(yōu)先遍歷算法和廣度優(yōu)先遍歷算法。⒊掌握求最小生成樹(shù)的普里姆算法和克魯斯卡爾算法，并能運(yùn)用這些算法解決綜合問(wèn)題。⒋理解圖的最短路徑算法。8.1.1與圖有關(guān)的若干概念8.1.2圖的抽象數(shù)據(jù)類(lèi)型1、具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有（）條邊才能確保是一個(gè)連通圖。

A5

B6

C7

D82、設(shè)G是一個(gè)非連通的無(wú)向圖，有15條邊，則該圖至少有（）個(gè)頂點(diǎn)A5

B6

C7

D83、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)和e條邊的無(wú)向圖，若采用鄰接矩陣表示，則該矩陣的大小是（），矩陣中非零元的個(gè)數(shù)為（）。

An

B(n-1)

2

Cn-1

Dn2Ee F2e Ge2 Hn2ACDF4、假設(shè)有一個(gè)有向圖具有n個(gè)頂點(diǎn)和e條邊，若該有向圖采用鄰接矩陣存儲(chǔ)，則刪除與頂點(diǎn)i相關(guān)聯(lián)的所有邊的時(shí)間復(fù)雜度是（），若該有向圖采用鄰接表存儲(chǔ)，則刪除與該頂點(diǎn)i相關(guān)聯(lián)的所有邊的時(shí)間復(fù)雜度是（）

AO(n)

BO(e) CO(n+e) DO(n2)5、對(duì)如圖所有的無(wú)向圖，從頂點(diǎn)a開(kāi)始進(jìn)行深度優(yōu)先搜索，可得到頂點(diǎn)訪問(wèn)序列（），從頂點(diǎn)a開(kāi)始進(jìn)行廣度優(yōu)先搜索，可得到頂點(diǎn)訪問(wèn)序列（）。Aabdecgf

Babdegfc Cabdefcg

DabcdegfEabcdefg Fabdcefg Gabcdegf HbeadgcfABEBabcdefg6、任何一個(gè)連通圖的最小生成樹(shù)（）

A只有一棵 B有一棵或者多棵

C一定有多棵 D可能不存在7、一個(gè)具有n個(gè)頂點(diǎn)和e條邊的連通圖的生成樹(shù)具有（）條邊An

Be

Cn-1

Dn+18、如果具有n個(gè)頂點(diǎn)的圖是一個(gè)環(huán)，則它有（）棵生成樹(shù)。

An

B2n

Cn-1

Dn+19、已知一個(gè)帶權(quán)連通圖如圖所示，在該圖的最小生成樹(shù)中各條邊上權(quán)值之和為（），在該圖的最小生成樹(shù)中，從頂點(diǎn)1到6的路徑為（）。A31

B38

C36

D43E136 F146G1546 H1436BCBCG10、在用Dijkstra算法求解帶權(quán)有向圖的最短路徑問(wèn)題時(shí)，要求圖中每條邊所帶權(quán)值必須是（）。對(duì)于如圖所示的帶權(quán)有向圖，從頂點(diǎn)1到頂點(diǎn)5的最短路徑為（）

A非零 B非整 C非負(fù) D非正

E145 F1235 G1435 H12435CH11、已知一個(gè)圖如圖所示，依據(jù)Dijkstra算法求從頂點(diǎn)1到其余各個(gè)頂點(diǎn)的最短路徑的順序應(yīng)是（）

A25463B25436 C23546 D54632

B第九章排序

1、基本概念：關(guān)鍵碼、初始關(guān)鍵碼排列、關(guān)鍵碼比較次數(shù)、數(shù)據(jù)移動(dòng)次數(shù)、穩(wěn)定性、附加存儲(chǔ)、內(nèi)部排序、外部排序2、插入排序要點(diǎn)：

當(dāng)待排序的關(guān)鍵碼序列已經(jīng)基本有序時(shí)，用直接插入排序最快3、選擇排序要點(diǎn)：

用直接選擇排序在一個(gè)待排序區(qū)間中選出最小的數(shù)據(jù)時(shí)，與區(qū)間第一個(gè)數(shù)據(jù)對(duì)調(diào)，而不是順次后移。這導(dǎo)致方法不穩(wěn)定。

在堆排序中將待排序的數(shù)據(jù)組織成完全二叉樹(shù)的順序存儲(chǔ)。4、交換排序要點(diǎn)：

快速排序是一個(gè)遞歸的排序方法

當(dāng)待排序關(guān)鍵碼序列已經(jīng)基本有序時(shí)，快速排序顯著變慢。5、二路歸并排序要點(diǎn)：

歸并排序可以遞歸執(zhí)行歸并排序需要較多的附加存儲(chǔ)。

歸并排序?qū)Υ判蜿P(guān)鍵碼的初始排列不敏感，排序速度較穩(wěn)定1．給出一組關(guān)鍵字T=（30，8，16，12，2，28），寫(xiě)出用希爾排序從小到大排序時(shí)第一趟（gap=3）結(jié)束時(shí)的序列

12，2，16，30，8，28

。2．對(duì)一組記錄（54，38，96，23，15，72，60，45，83）進(jìn)行直接插入排序，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需要比較____3____次。3.已知一個(gè)數(shù)據(jù)表為{36,25,25*,62,40,53}，請(qǐng)寫(xiě)出在進(jìn)行快速排序的過(guò)程中每次劃分后數(shù)據(jù)表的變化。(0)[362525*624053](1)[25*25]36[624053]

(2)25*2536[5340]62(3)25*2536405362(1)每次從無(wú)序表中取出一個(gè)元素，把它插入到有序表中的適當(dāng)位置，此種排序方法叫做_______排序；每次從無(wú)序表中挑選出一個(gè)最小或最大元素，把它交換到有序表的一端，此種排序方法叫做________排序。(2)每次直接或通過(guò)基準(zhǔn)元素間接比較兩個(gè)元素，若出現(xiàn)逆序排列時(shí)就交換它們的位置，此種排序方法叫做________排序；(3)在直接選擇排序中，記錄比較次數(shù)的時(shí)間復(fù)雜度為_(kāi)__O(n2)_____，記錄移動(dòng)次數(shù)的時(shí)間復(fù)雜度為_(kāi)___O(n)____。(4)在堆排序的過(guò)程中，對(duì)n個(gè)記錄建立初始堆需要進(jìn)行________次調(diào)整運(yùn)算，由初始堆到堆排序結(jié)束，需要對(duì)樹(shù)根結(jié)點(diǎn)進(jìn)行________次調(diào)整運(yùn)算。(5)在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行調(diào)整運(yùn)算的時(shí)間復(fù)雜度為_(kāi)_______，整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜度為_(kāi)_______。(6)假定一組記錄的排序碼為(46,79,56,38,40,84)，則利用堆排序方法建立的初始堆為_(kāi)_______。(4)在堆排序的過(guò)程中，對(duì)n個(gè)記錄建立初始堆需要進(jìn)行___

n/2

_次調(diào)整運(yùn)算，由初始堆到堆排序結(jié)束，需要對(duì)樹(shù)根結(jié)點(diǎn)進(jìn)行___n-1__次調(diào)整運(yùn)算。(5)在堆排序的過(guò)程中，對(duì)任一分支結(jié)點(diǎn)進(jìn)行調(diào)整運(yùn)算的時(shí)間復(fù)雜度為_(kāi)_O(log2n）_，整個(gè)堆排序過(guò)程的時(shí)間復(fù)雜度為_(kāi)O(nlog2n)_。(6)假定一組記錄的排序碼為(46,79,56,38,40,84)，則利用堆排序方法建立的初始堆為_(kāi)(84,79,56,38,40,46)_______。(7)快速排序在平均情況下的時(shí)間復(fù)雜度為_(kāi)_______，在最壞情況下的時(shí)間復(fù)雜度為_(kāi)_____。(8)快速排序在平均情況下的空間復(fù)雜度為_(kāi)_______，在最壞情況下的空間復(fù)雜度為_(kāi)_____。(9)在快速排序方法中，進(jìn)行每次劃分時(shí)，是從當(dāng)前待排序區(qū)間的________向________依次查找出處于逆序的元素并交換之，最后將基準(zhǔn)元素交換到一個(gè)確定位置，從而以該位置把當(dāng)前區(qū)間劃分為前后兩個(gè)子區(qū)間。(10)假定一組記錄的排序碼為(46,79,56,38,40,80)，對(duì)其進(jìn)行快速排序的一次劃分的結(jié)果為_(kāi)_______。(7)快速排序在平均情況下的時(shí)間復(fù)雜度為_(kāi)_______，在最壞情況下的時(shí)間復(fù)雜度為_(kāi)_______。(8)快速排序在平均情況下的空間復(fù)雜度為_(kāi)_______，在最壞情況下的空間復(fù)雜度為_(kāi)_______。(9)在快速排序方法中，進(jìn)行每次劃分時(shí)，是從當(dāng)前待排序區(qū)間的兩端（低端）向中間（高端）依次查找出處于逆序的元素并交換之，最后將基準(zhǔn)元素交換到一個(gè)確定位置，從而以該位置把當(dāng)前區(qū)間劃分為前后兩個(gè)子區(qū)間。(10)假定一組記錄的排序碼為(46,79,56,38,40,80)，對(duì)其進(jìn)行快速排序的一次劃分的結(jié)果為_(kāi)[4038]46[567980]或[4038]46[795680]

_______。1.已知序列{17，25，55，43，3，32，78，67，91}，請(qǐng)給出采用冒泡排序法對(duì)該序列作遞增排序時(shí)每一趟的結(jié)果。2.已知序列{491，77，572，16，996，101，863，258，689，325}，請(qǐng)給出快速排序時(shí)每一趟的結(jié)果。3.已知序列{86，94，138，62，41，54，18，32}，請(qǐng)給出采用插入排序法對(duì)該序列作遞增排序時(shí)，每一趟的結(jié)果。4.已知序列{27，35，11，9，18，30，3，23，35，20}，請(qǐng)給出采用歸并排序法對(duì)該序列作遞增排序時(shí)的每一趟的結(jié)果。這就是為什么我們彼此喜歡卻不能在一起的原因。在兩人除去性愛(ài)更為廣泛的圈子里，你找不到我，我也找不到你，夜晚短暫的愛(ài)只適合埋藏在不知哪一天你會(huì)出現(xiàn)在我眼前的等待里。我告訴自己，我應(yīng)該是一個(gè)人，一個(gè)完整卻如篩漏的女人，那