《數據結構與算法》復習

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

intlength;∥當前長度

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

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

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

B.雙鏈表

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

D.順序表2.在有n個葉子結點的哈夫曼樹中結點總數為

。A.不確定

B.2n-1

C.2n

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

。A.遞增或遞減

B.遞增

C.遞減

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

的結點開始。A.80

B.12

C.60

D.155.設圖G用鄰接表存儲，那么求每個頂點入度的時間復雜度為

。A.O(n)

B.O(n+e)

C.

O(n*n)

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

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

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

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

D.4、1、2、38.在具有n個結點的二叉鏈表中，非空的鏈域個數為_____。A.n-1

B.2n-1

C.n+1

D.2n+19.在有n個結點的二叉排序樹中查找一個鍵值，其最壞比較次數的數量級為___________。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個元素的有序查找表采用折半查找算法查找一個鍵值，其最壞比較次數的數量級為

。A.O(log2n)

B.O(n)

C.O(nlog2n)

D.O(n2)12、

以下排序算法中，

算法在進行一趟相應的排序處理結束后不一定能選出一個元素放到其最終位置上。。A.直接選擇排序

B.冒泡排序

C.歸并排序

D.堆排序13、

隊列的操作原那么是

。A.先進后出

B.先進先出

C.只能進行插入

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

完全二叉樹的第5層有8個結點(根結點在1層)，那么其葉子結點有_

個。2.

在單鏈表中，刪除指針P所指結點的后繼結點的語句是：

。3.

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

。4.

平衡二叉樹中每個結點的平衡因子定義為

。5.通常象交通、道路問題的數學模型是一種稱為

的數據結構。6.

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

。7.在線性表的順序存儲結構中，假設每一個元素占h個存儲單元，那么第I個元素ai的存儲位置為

LOC(ai)=LOC(a1)+

。8.

設有數據結構〔D,R〕,其中D是數據元素的有限集，R是

的有限集。9.深度為k的二叉樹其結點數至多有

個。10.

棧是一種特殊的線性表，它允許在表的一端進行

操作。11.

哈希表是一種查找表，可以根據哈希函數直接獲得

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