《數(shù)據(jù)結(jié)構(gòu)與算法》復(fù)習(xí)

數(shù)據(jù)結(jié)構(gòu)是一門研究計(jì)算機(jī)的操作對象以及操作對象之間的關(guān)系和對操作對象實(shí)施的典型操作的學(xué)科第一局部概述研究數(shù)據(jù)結(jié)構(gòu)從三個(gè)方面進(jìn)行：〔1〕邏輯結(jié)構(gòu)〔2〕存儲結(jié)構(gòu)〔3〕操作〔運(yùn)算〕：對數(shù)據(jù)進(jìn)行的處理，定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上具體實(shí)現(xiàn)于數(shù)據(jù)的存儲結(jié)構(gòu)描述數(shù)據(jù)邏輯結(jié)構(gòu)描述數(shù)據(jù)物理結(jié)構(gòu)ADT由三元組構(gòu)成：〔D，S，P〕D數(shù)據(jù)對象S關(guān)系P操作集關(guān)系的表示方法順序映象非順序映象順序存儲結(jié)構(gòu)鏈?zhǔn)酱鎯Y(jié)構(gòu)四種根本的數(shù)據(jù)結(jié)構(gòu)及其特點(diǎn)算法的特征及評價(jià)方法集合線性表樹圖數(shù)據(jù)元素?cái)?shù)據(jù)項(xiàng)數(shù)據(jù)對象時(shí)間復(fù)雜度空間復(fù)雜度第二局部表、棧、隊(duì)列線性表的邏輯結(jié)構(gòu)線性表的物理結(jié)構(gòu)順序表單向鏈表循環(huán)鏈表雙向鏈表靜態(tài)鏈表有序性均勻性位序操作及算法的分析〔順序表、單鏈表〕插入刪除查找建表合并集合運(yùn)算順序表與線性鏈表的比照1.靜態(tài)結(jié)構(gòu)與動態(tài)結(jié)構(gòu)(大小)2.數(shù)據(jù)關(guān)系的表示方法3.操作(插入/刪除、查找)帶頭結(jié)點(diǎn)與不帶頭結(jié)點(diǎn)的比照1.空表與非空表一致性2.不同位置插入、刪除操作的一致性棧和隊(duì)列棧和隊(duì)列的特點(diǎn)：操作受限制棧和隊(duì)列的操作〔建立、入/出〕棧/隊(duì)列的空、滿條件順序鏈棧和隊(duì)列的物理結(jié)構(gòu)棧和隊(duì)列的應(yīng)用特征串的判斷進(jìn)制轉(zhuǎn)換括號匹配逆波蘭表達(dá)式求值∥–––––線性表的動態(tài)分配順序存儲結(jié)構(gòu)–––––#defineLIST_INIT_SIZE100∥線性表存儲空間的初始分配#defineLISTINCREMENT10∥線性表存儲空間的分配增量typedefstruct{ElemType*elem;∥存儲空間基址

intlength;∥當(dāng)前長度

intlistsize;∥當(dāng)前分配的存儲容量}SqList;∥–––––棧的順序存儲表示–––––#defineSTACK_INIT_SIZE100∥存儲空間初始分配#defineSTACKINCREMENT10∥存儲空間分配增量typedefstruct{SElemType*base;SElemType*top;intstacksize;}SqStack;∥–––––循環(huán)隊(duì)列──隊(duì)列的順序存儲結(jié)構(gòu)–––––#defineMAXQSIZE100∥最大隊(duì)列長度typedefstruct{QElemType*base;∥初始化的動態(tài)分配存儲空間intfront;∥頭指針,假設(shè)隊(duì)列不空,指向隊(duì)列頭元素intrear;∥尾指針,假設(shè)隊(duì)列不空,指向隊(duì)列尾元素的下一個(gè)位置}SqQueue;//線性鏈表存儲結(jié)構(gòu)typedefstructLNode{ElemTypedata;structLNode*next;}LNode,*LinkList;LinkListL;∥–––––隊(duì)列的鏈?zhǔn)酱鎯Y(jié)構(gòu)–––––typedefstructQNode{QElemTypedata;StructQNode*next;}QNode,*QueuePtr;//鏈棧存儲結(jié)構(gòu)typedefstructSNode{SElemTypedata;structSNode*next;}SNode,*StackLink;StackLinkS;typedefstruct{QueuePtrfront;∥隊(duì)頭指針

QueuePtrrear;∥隊(duì)尾指針}LinkQueue第三局部串、數(shù)組什么是串空串串長串的物理結(jié)構(gòu)StrAssign(&T,chats)初始化一個(gè)串StrCopy(&T,S)串復(fù)制StrEmpty(S)判斷串是否空串的根本操作StrLength(S)求串長StrCompare(S,T)串的比較Concat(&T,S1,S2)串聯(lián)接Substring(&sub,S,pos,len)求子串StrInsert(&S,pos,T)插入子串StrDelete(&S,pos,len)刪除子串Index(S,T,pos)求子串出現(xiàn)的位置Replace(&S,T,V)串替換數(shù)組的定義數(shù)組元素地址計(jì)算特殊矩陣的壓縮存儲稀疏矩陣的轉(zhuǎn)置運(yùn)算第四局部樹、圖樹的定義度、葉子結(jié)點(diǎn)、終端結(jié)點(diǎn)、非終端結(jié)點(diǎn)、分支結(jié)點(diǎn)、內(nèi)部結(jié)點(diǎn)孩子、祖先、雙親、子孫、兄弟、層次、高度〔深度〕滿二叉樹完全二叉樹二叉樹的定義、形態(tài)、性質(zhì)證明:(1)設(shè)n1為T中度為1的結(jié)點(diǎn)數(shù)由于二叉樹中所有結(jié)點(diǎn)的度均小于等于2那么結(jié)點(diǎn)總數(shù)為n=n0+n1+n2(2)設(shè)B為分支總數(shù)除根外，所有結(jié)點(diǎn)都有一個(gè)分支進(jìn)入故：n=B+1(3)所有分支是由度為1或2的結(jié)點(diǎn)射出因此：B=n1+n2*2(4)n0+n1+n2=n1+n2*2+1n0=n2+1二叉樹的存儲結(jié)構(gòu)二叉樹的遍歷及遍歷的利用二叉樹的建立線索二叉樹typedefstructBiTNode{TElemTypedata;structBiTNode*lchild,*rchild;//左右孩子指針}BiTNode,*BiTree;森林、樹與二叉樹的轉(zhuǎn)換樹和森林的遍歷，與二叉樹遍歷的對應(yīng)關(guān)系Huffman樹的構(gòu)造，WPL圖的定義有向圖和無向圖完全圖子圖度路徑簡單路徑簡單回路連通圖強(qiáng)連通圖圖的存儲結(jié)構(gòu)數(shù)組表示法鄰接表連通分量生成樹生成森林圖的遍歷深度優(yōu)先搜索廣度優(yōu)先搜索最小生成樹普里姆算法〔表〕克魯斯卡爾算法拓?fù)渑判?拓?fù)浯涡?關(guān)鍵路徑〔表〕最短路徑動態(tài)查找表第五局部查找、排序順序查找算法平均比較長度ASL折半查找二叉排序樹平衡二叉樹B-樹靜態(tài)查找表哈希表除數(shù)留余法線性探測再散列二次探測再散列鏈地址法內(nèi)部排序直接插入排序折半插入排序希爾排序起泡排序快速排序簡單項(xiàng)選擇擇排序堆排序歸并排序比較:穩(wěn)定性各種情況下的時(shí)間復(fù)雜性輔助空間的多少關(guān)鍵字比較的次數(shù)與記錄的初始排列次序每趟排序至少能將一個(gè)元素放到其最終位置上1.假設(shè)線性表最常用的操作是存取第i個(gè)元素及其前驅(qū)的值，那么采用

存儲方式最節(jié)省運(yùn)算時(shí)間。A.單鏈表

B.雙鏈表

C.單循環(huán)鏈表

D.順序表2.在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹中結(jié)點(diǎn)總數(shù)為

。A.不確定

B.2n-1

C.2n

D.2n+13.折半查找法要求查找表中各元素的關(guān)鍵字值必須是

。A.遞增或遞減

B.遞增

C.遞減

D.無序4.對于關(guān)鍵字值序列〔11，13，18，60，15，7，19，25，12，80〕，用篩選法建堆，必須從鍵值為

的結(jié)點(diǎn)開始。A.80

B.12

C.60

D.155.設(shè)圖G用鄰接表存儲，那么求每個(gè)頂點(diǎn)入度的時(shí)間復(fù)雜度為

。A.O(n)

B.O(n+e)

C.

O(n*n)

D.O(n*e)6.鏈表不具有的特點(diǎn)是__________。A.不必事先估計(jì)存儲空間

B.可隨機(jī)訪問任一元素C.插入刪除不需要移動元素

D.所需空間與線性表長度成正比7.設(shè)輸入序列為1、2、3、4，那么借助棧所得到的輸出序列不可能是________。A.1、2、3、4

B.4、3、2、1C.1、3、4、2

D.4、1、2、38.在具有n個(gè)結(jié)點(diǎn)的二叉鏈表中，非空的鏈域個(gè)數(shù)為_____。A.n-1

B.2n-1

C.n+1

D.2n+19.在有n個(gè)結(jié)點(diǎn)的二叉排序樹中查找一個(gè)鍵值，其最壞比較次數(shù)的數(shù)量級為___________。A.O(log2n)

B.O(n)

C.O(nlog2n)

D.O(n2)10.以下序列中，____是執(zhí)行第一趟快速排序后得到的序列A.[da,ax,eb,cd,bb]ff[ha,gc]

B.[cd,eb,ax,da]ff[ha,gc,bb]C.[gc,ax,eb,cd,bb]ff[da,ha]

D.[ax,bb,cd,da]ff[eb,gc,ha]11、

對具有n個(gè)元素的有序查找表采用折半查找算法查找一個(gè)鍵值，其最壞比較次數(shù)的數(shù)量級為

。A.O(log2n)

B.O(n)

C.O(nlog2n)

D.O(n2)12、

以下排序算法中，

算法在進(jìn)行一趟相應(yīng)的排序處理結(jié)束后不一定能選出一個(gè)元素放到其最終位置上。。A.直接選擇排序

B.冒泡排序

C.歸并排序

D.堆排序13、

隊(duì)列的操作原那么是

。A.先進(jìn)后出

B.先進(jìn)先出

C.只能進(jìn)行插入

D.只能進(jìn)行刪除14、在以下兩種求圖的最小生成樹的算法中，算法適合于求邊稀疏的網(wǎng)的最小生成樹?！睞〕PRIM〔B〕KRUSKAL判斷以下各題是否正確，假設(shè)正確，在題前的括號內(nèi)填“T”，否那么填“F”。1.對于循環(huán)隊(duì)列，在隊(duì)滿情況下不能作入隊(duì)處理，否那么，將產(chǎn)生“上溢”。2．完全二叉樹的某結(jié)點(diǎn)假設(shè)無左孩子，那么它必是葉結(jié)點(diǎn)。3.一個(gè)有向圖的鄰接表和逆鄰接表中的邊結(jié)點(diǎn)個(gè)數(shù)不一定相等。4.假設(shè)一棵二叉樹的任一非葉子結(jié)點(diǎn)度為2，那么該二叉樹為滿二叉樹。5.在采用線性探測法處理沖突的散列表中所有同義詞在表中相鄰。6.在棧為空的情況下不能作出棧處理，否那么，將產(chǎn)生下溢出。7.如果有向圖G=(V,E)的拓?fù)湫蛄形ㄒ?，那么圖中必定僅有一個(gè)頂點(diǎn)的入度為0、一個(gè)頂點(diǎn)的出度為0。8.在大根堆中,必定滿足每個(gè)結(jié)點(diǎn)的鍵值大于其左右子樹中所有結(jié)點(diǎn)的鍵值。9.中序遍歷一棵二叉排序樹的節(jié)點(diǎn)就可得到排好序的節(jié)點(diǎn)序列。1.

完全二叉樹的第5層有8個(gè)結(jié)點(diǎn)(根結(jié)點(diǎn)在1層)，那么其葉子結(jié)點(diǎn)有_

個(gè)。2.

在單鏈表中，刪除指針P所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的語句是：

。3.

有向圖G用鄰接矩陣A[1..n，1..n]存儲，其第i行的所有非零元素之個(gè)數(shù)等于頂點(diǎn)i的

。4.

平衡二叉樹中每個(gè)結(jié)點(diǎn)的平衡因子定義為

。5.通常象交通、道路問題的數(shù)學(xué)模型是一種稱為

的數(shù)據(jù)結(jié)構(gòu)。6.

對于單鏈表，假設(shè)要在指針P所指結(jié)點(diǎn)之后插入由指針S所指結(jié)點(diǎn)，那么需要執(zhí)行的語句序列為：

。7.在線性表的順序存儲結(jié)構(gòu)中，假設(shè)每一個(gè)元素占h個(gè)存儲單元，那么第I個(gè)元素ai的存儲位置為

LOC(ai)=LOC(a1)+

。8.

設(shè)有數(shù)據(jù)結(jié)構(gòu)〔D,R〕,其中D是數(shù)據(jù)元素的有限集，R是

的有限集。9.深度為k的二叉樹其結(jié)點(diǎn)數(shù)至多有

個(gè)。10.

棧是一種特殊的線性表，它允許在表的一端進(jìn)行

操作。11.

哈希表是一種查找表，可以根據(jù)哈希函數(shù)直接獲得

。1.設(shè)哈希函數(shù)為H(K)=Kmod11，地址空間為0..12，用線性探測法解決沖突。請畫出依