廣東專升本數(shù)據(jù)結(jié)構(gòu)知識點總結(jié)

廣東專升本數(shù)據(jù)結(jié)構(gòu)知識點總結(jié)

①數(shù)據(jù)結(jié)構(gòu)（邏輯結(jié)構(gòu)）其4類基本結(jié)構(gòu)：集合、線性結(jié)構(gòu)、樹形結(jié)構(gòu)、圖

狀結(jié)構(gòu)和網(wǎng)狀結(jié)構(gòu)。

②物理結(jié)構(gòu)（存儲結(jié)構(gòu)）其4種存儲結(jié)構(gòu)：順序存儲結(jié)構(gòu)、鏈式存儲結(jié)構(gòu)、

索引存儲結(jié)構(gòu)和散列存儲結(jié)構(gòu)。

③算法5個重要特性：有窮性、確定性、可行性、輸入和輸出。

通常從四個方面評價算法的質(zhì)量：正確性、易讀性、強壯性和高效

率。

④線性表是由n20個數(shù)據(jù)元素組成的有限序列。其特點為邏輯關(guān)系上相

鄰的兩個元素在物理位置上也相鄰。

⑤在順序表中實現(xiàn)的基本運算：

插入：平均移動結(jié)點次數(shù)為n/2;平均時間復雜度均為。（n工

刪除：平均移動結(jié)點次數(shù)為（n-1）/2;平均時間復雜度均為O（nX

⑥存儲位置計算：每個元素需占用L個存儲單元第一個單元的存儲地址作

為數(shù)據(jù)元素的存儲位置線性表的第i個數(shù)據(jù)元素ai的存儲位置為

LOC（ai）=LOC（al）+（i-l）*L,al的存儲位置，通常稱做線性表的起始位置或基

地址。

⑦線性表的鏈式存儲結(jié)構(gòu):數(shù)據(jù)元素ai的存儲映像稱為結(jié)點，包括2個域:

存數(shù)據(jù)的數(shù)據(jù)域、存后繼存儲位置的指針域。

⑧線性鏈表（單鏈表）特點：每個結(jié)點只包含1個指針域。在單鏈表的第一

個結(jié)點之前附設(shè)的一個結(jié)點，稱之為頭結(jié)點。

⑨假設(shè)L是LinkList型變量，則L為單鏈表的頭指針，它指向表中第一個

結(jié)點。

L->next為第一個結(jié)點地址，L->next=NULL為空表。

回收結(jié)點：free(q)。

⑩棧：是限定僅在棧頂(表尾)進行插入或刪除操作的線性表。表頭端稱

為棧底，不含有元素的空表稱為空棧；棧又稱為后進先出的線性表。

?隊列：是一種先進先出的線性表，它只允許在表的一端進行插入，而

另一端刪除元素。允許插入的一端叫做隊尾，允許刪除的一端則稱為隊頭。

?鏈隊列：用鏈表示的隊列。一個隊列需要頭指針和尾指針才能確定唯一。

⑩棧：是限定僅在棧頂(表尾)進行插入或刪除操作的線性表。表頭端稱

為棧底，不含有元素的空表稱為空棧；棧又稱為后進先出的線性表。

?隊列：是一種先進先出的線性表，它只允許在表的一端進行插入，而

另一端刪除元素。允許插入的一端叫做隊尾，允許刪除的一端則稱為隊頭。

?鏈隊列：用鏈表示的隊列。一個隊列需要頭指針和尾指針才能確定唯一。

?循環(huán)隊列：兩個指針front指示隊列頭元素和rear指示隊列尾元素的位

置。初始化建空隊列時，令front=rear=0,每當插入新的隊列尾元素時，"尾

指針增1";每當刪除隊列頭元素時，"頭指針增1"o

?串：是由零個或多個字符組成的有限序列。

?數(shù)組的存儲位置計算：假設(shè)每個數(shù)據(jù)元素需占用L個存儲單元，則二維

數(shù)組A中任一元素A[ij]的存儲位置可由下式確定：

以行序為主序的存儲結(jié)構(gòu)：LOC(i,j)=LOC(OQ)+(n*i+j)*L;(n為行數(shù))

以列序為主序的存儲結(jié)構(gòu):LOC(i,j)=LOC(0,0)+(n*j+i)*L;(n為列數(shù))

?廣義表：是線性表的推廣，在廣義表的定義中，ai可以是單個元素，也

可以是廣義表，分別稱為廣義表LS的原子和子表。

?二叉樹的性質(zhì)：

性質(zhì)1:在二叉樹的第K層上至多有2k-l個結(jié)點(K之1)。

性質(zhì)2:深度為k的二叉樹至多2k-l個結(jié)點(kN1)。

深度為k的二叉樹至少有k個結(jié)點(k?l)。

深度為k的完全二叉樹至少有2k-l個結(jié)點(kNl)。

性質(zhì)3:對任何一棵二叉樹T,如果其終端結(jié)點數(shù)為NO,度為2的結(jié)

點數(shù)為N2,則N0=N2+l?？偨Y(jié)點個數(shù)N=N0+Nl+N2o

性質(zhì)4:具有n個結(jié)點的完全二叉樹的深度為[Iog2n]+1。

?滿二叉樹：一顆深度為k且有2的k次方減1個結(jié)點的二叉樹。

?完全二叉樹：深度為k的，有n個結(jié)點的二叉樹，當且僅當其每一個結(jié)

點都與深度為k的滿二叉樹中編號從1至n的結(jié)點——對應。

?樹轉(zhuǎn)換成二叉樹：連兄弟，留長子，刪孩子。

注意：由于樹根沒有兄弟結(jié)點，固樹轉(zhuǎn)換為二叉樹后，二叉樹根結(jié)點的

右子樹必為空。

①森林轉(zhuǎn)換成二叉樹：連樹根及兄弟，留長子，刪孩子。

②二叉樹轉(zhuǎn)換成樹：連左孩子的右孩子及其右孩子…，刪原樹右孩子。

③赫夫曼樹：又稱最優(yōu)樹，是一類帶權(quán)路徑長度最短的樹。

WPL=23+43+52+71=35

④赫夫曼編碼：在赫夫曼樹上，左分支代表0,右分支代表L由根結(jié)點

到指定結(jié)點的路徑(從上到下把0、1連起來)，就是該結(jié)點的赫夫曼編碼；如上

圖(d)中a為0,b為10,c為110,d為111。

⑤無向完全圖：有n(n-l)/2條邊的無向圖。

有向完全圖：有n(n-l)條邊的有向圖。

⑥鄰接矩陣：無向圖的鄰接矩陣關(guān)于主對角線對稱，在整個矩陣中非零元素

的個數(shù)等于邊個數(shù)的2倍，第i行和第i列中非零元素的個數(shù)等于該結(jié)點的度。

⑦鄰接表：無向圖的鄰接矩陣關(guān)于主對角線對稱，在整個矩陣中非零元素

的個數(shù)等于邊個數(shù)的2倍，第i行和第i列中非零元素的個數(shù)等于該結(jié)點的度。

⑧深度優(yōu)先遍歷：

⑨廣度優(yōu)先遍歷：

⑩最小生成樹：

普里姆算法(Prim):連相鄰權(quán)值最小的。

克魯斯卡爾算法(Kruskal):先連權(quán)值最小的，再依次連。

@拓撲排序：由某個集合上的一個偏序得到該集合上的一個全序的操作。

順序查找法平均查找長度：

?ASL=(n+l)/2o

折半查找法(二分查找法)平均查找長度：ASL=(n+l)/n*log2(n+l)-l

索引順序表查找法(分塊查找法評均查找長度:ASLMog2(n/s+l)+s/2。

?直接插入排序：將一個記錄插入到已排好序的有序表中，從而得到一個

新的、記錄數(shù)增1的有序表。

?冒泡排序：首先將一個記錄的關(guān)鍵字和第二個記錄的關(guān)鍵字進行比較，

若為逆序(即L.r[l].key>L.r[2].key),則將兩個記錄交換之，然后比較第二個記

錄和第三個記錄的關(guān)鍵字。以此類推，直至第n-1個記錄和第n個記錄的關(guān)鍵

字進行過比較為止。

?快速排序：通過一趟排序?qū)⒋庞涗浄指畛瑟毩⒌膬刹糠?，其中一部?/p>

記錄的關(guān)鍵字均比另一部分記錄的關(guān)鍵字小，則可分別對這兩部分記錄繼續(xù)進行

排序，以達到整個序列有序。

①巾頁序表是隨機存儲結(jié)構(gòu)，當線性表的操作主要是查找時，宜采用以插入

和刪除操作為主的線性表宜采用鏈表做存儲結(jié)構(gòu)。若插入和刪除主要發(fā)生在

表的首尾兩端，則宜采用尾指針表示的單循環(huán)鏈表。

②在順序棧中有"上溢"和"下溢"的現(xiàn)象，"上溢"是棧頂指針指出棧的

外面是出錯狀態(tài)，"下溢"可以表示棧為空棧，因此用來作為控制轉(zhuǎn)移的條件。

③隊列是一種運算受限的線性表，允許刪除的一端稱為隊頭（front）,允

許插入的一端稱為隊尾（rear）,隊列的操作原則是先進先出的，又稱作FIFO

表。隊列也有順序存儲和鏈式存儲兩種存儲結(jié)構(gòu)。

④循環(huán)隊列：判定循環(huán)隊列是空還是滿，方法有三種：

一種是另設(shè)一個布爾變量來判斷；

第二種是少用一個元素空間，入隊時先測試（（rear+1）%m=front）?

滿：空；

第三種就是用一個計數(shù)器記錄隊列中的元素的總數(shù)。

⑤隊列的鏈式存儲結(jié)構(gòu)稱為鏈隊列，為了便于在表尾進行插入（入隊）的

操作，在表尾增加一個尾指針，一個鏈隊列就由一個頭指針和一個尾指針唯一地

確定。鏈隊列不存在隊滿和上溢的問題。

在鏈隊列的出隊算法中，要注意當原隊中只有一個結(jié)點時，出隊后要同進修

改頭尾指針并使隊列變空。

⑥串是零個或多個字符組成的有限序列。

空串：是指長度為零的串，也就是串中不包含任何字符（結(jié)點）

空白串：指串中包含一個或多個空格字符的串。

⑦子串在主串中的序號就是指子串在主串中首次出現(xiàn)的位置。空串是任意

串的子串，任意串是自身的子串。

⑧串的基本運算有：

求串長strlen(char*s)串復制strcpy(char*to,char*from)

字符定位strchr(char*s,chare)串聯(lián)接strcat(char*to,char*from)

串比較charcmp(char*sl,char*s2)

⑨地址的計算方法：

按行優(yōu)先順序排列的數(shù)組：LOCa(ij)=LOCa(ll)+((i-1)*n+(j-l))

*d

按列優(yōu)先順序排列的數(shù)組：LOCa(ij)=LOCa(ll)+((j-l)*n+(i-l))

*d

⑩圖的存儲結(jié)構(gòu)：

鄰接矩陣表示法：用一個n階方陣來表示圖的結(jié)構(gòu)是唯一的；無向圖中

鄰接矩陣是對稱的；有向圖中行是出度，列是入度。

鄰接表表示法：用頂點表和鄰接表構(gòu)成不是唯一的；頂點表結(jié)構(gòu)vertex|

firstedge，指針域存放鄰接表頭指針；鄰接表是用頭指針確定。

?圖的遍歷：

深度優(yōu)先遍歷：借助于鄰接矩陣的列。使用棧保存已訪問結(jié)點。

廣度優(yōu)先遍歷：借助于鄰接矩陣的行。使用隊列保存已訪問結(jié)點。

?直接插入排序：

?直接選擇排序：

?冒泡排序：

?快速排序：

①n個結(jié)點的二叉樹共有2n個指針域，其中有n-1個指針域是存放了

地址，有n+1個指針是空指針。

②在一個具有n個頂點的無向完全圖中，包含有e條邊，在一個具有n

個頂點的有向完全圖中，包含有2e條邊。

③在堆排序的過程中，對任一分支結(jié)點進行篩運算的時間復雜度為

O(log2n),整個堆排序過程的時間復雜度為O(nlog2n)0

④AOV網(wǎng)是一種有向無回路的圖。

⑤設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m,若用二叉鏈表作為存儲結(jié)構(gòu)，則該

哈夫曼樹中總共有2m個空指針域。(m個葉子節(jié)點的哈夫曼樹總共有2m-l

個節(jié)點)

⑥設(shè)順序循環(huán)隊列Q[0:M-1]的頭指針和尾指針分別為F和R,頭指針F

總是指向隊頭元素的前一位置，尾指針R總是指向隊尾元素的當前位置，則該

循環(huán)隊列中的元素個數(shù)為(R-F+M)%M。

⑦快速排序的最壞時間復雜度為0(n2),平均時間復雜度為O(nlog2n)。

⑧數(shù)據(jù)的物理結(jié)構(gòu)主要包括順序存儲結(jié)構(gòu)和鏈式存儲結(jié)構(gòu)兩種情況。

⑨二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。

在有序表上進行二分查找時的查找長度不超過二叉判定樹的高度1+Iog2n。

⑩設(shè)有n個無序的記錄關(guān)鍵字，則直接插入排序的時間復雜度為0(n2),

快速排序的平均時間復雜度為O(nlog2n)o

?設(shè)指針變量p指向雙向循環(huán)鏈表中的結(jié)點X，則刪除結(jié)點X需要執(zhí)行的

語句序列為p>llink->rlink=p->rlink;p->rlink->llink=p->rlink(設(shè)結(jié)點中的

兩個指針域分別為llink和rlinkX

?設(shè)有一個順序循環(huán)隊列中有M個存儲單元，則該循環(huán)隊列中最多能夠

存儲m-1個隊列元素；當前實際存儲(R-F+M)%M個隊列元素(設(shè)頭指針F

指向當前隊頭元素的前一個位置，尾指針指向當前隊尾元素的位置X

?設(shè)某無向圖G中有n個頂點，用鄰接矩陣A作為該圖的存儲結(jié)構(gòu)，則

頂點i和頂點j互為鄰接點的條件是A[i][j]=lo

?數(shù)據(jù)項是不可分割的構(gòu)成數(shù)據(jù)元素的最小單位；數(shù)據(jù)元素是數(shù)據(jù)的基本

單位。

?設(shè)一個有序的單鏈表中有n個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單鏈

表仍然保持有序，則該操作的時間復雜度為O(n)o

兩方面：一是插入時間復雜度。(1)；二是保持有序時間復雜度0(n)

?設(shè)一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為NO度數(shù)為1的結(jié)點數(shù)為NI〃.?…，

度數(shù)為m的結(jié)點數(shù)為Nm,則N0=I+N2+2N3+3N4+……+(m-l)Nm0

【注解】由2叉樹的性質(zhì)引申出，對于任何一顆樹T,如果其終端結(jié)點樹為

nO度為i的結(jié)點數(shù)為ni,則n0=l+n2+2n3+-+(i-l)ni

?設(shè)有一個順序共享棧S[0:n-l]其中第一個棧項指針topi的初值為-1,

第二個棧頂指針top2的初值為n,則判斷共享棧滿的條件是topl+l=top2o

?在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點的優(yōu)點是可以隨機訪問

到任一個頂點的簡單鏈表。

?設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點，則其判空條件

是head==0o

不帶頭結(jié)點是head==NULL,帶頭結(jié)點是head->next==NULL

設(shè)帶有頭結(jié)點的單向循環(huán)鏈表的頭指針變量為head,則其判空條件是

head->next==heado

?設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的

條件是只有一個孩子節(jié)點（或高度等于其結(jié)點數(shù)）。

①設(shè)指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊

列的隊尾指針，指針變量s指向?qū)⒁腙犃械慕Y(jié)點X,則入隊列的操作序列為

（注意：入隊要從隊尾入）

rear->next=s;rear=so

②設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的新結(jié)點X,

則進行插入操作的語句序列為s->next=p->next;p->next=s（設(shè)結(jié)點的指針

域為nextX

③設(shè)F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列

為空的條件為F==R

④設(shè)二叉樹中結(jié)點的兩個指針域分別為Ichild和rchild,則判斷指針變量

P所指向的結(jié)點為葉子結(jié)點的條件是

p->lchild==NULL&&p->rchild==NULLo

⑤散列表中解決沖突的兩種方法是開放定址法和鏈地址法。

⑥設(shè)指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列為

top=top->next;

若指針變量top指向當前順序棧的棧頂，則刪除棧頂元素的操作序列為

top=top-l

⑦設(shè)指針變量p指向雙向鏈表中的結(jié)點A,指針變量s指向被插入的結(jié)點

X,則在結(jié)點A的后面插入結(jié)點X的操作序列為

s->left=p;s->right=p->right;p->right=s;p->right->left=s;

(設(shè)結(jié)點中的兩個指針域分別為left和right'

⑧解決散列表沖突的兩種方法是開放定址法和鏈地址法。

⑨設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的結(jié)點X,

則在結(jié)點A的后面插入結(jié)點X需要執(zhí)行的語句序列：s->next=p->next;

p->next=s。

⑩設(shè)指針變量head指向雙向鏈表中的頭結(jié)點，指針變量p指向雙向鏈表

中的第一個結(jié)點則指針變量p和指針變量head之間的關(guān)系是p-head->rlink

和head=p->llink(設(shè)結(jié)點中的兩個指針域分別為llink和rlinkX

?設(shè)指針變量p指向雙向鏈表中結(jié)點A指針變量s指向被插入的結(jié)點X,

則在結(jié)點A的后面插入結(jié)點X的操作序列為

s->left=p;s->right=p->right;p->right->left=s;p->right=s;o

?設(shè)散列表中有m個存儲單元，散列函數(shù)H(key)=key%p,則p最好

選擇小于等于m的最大素數(shù)。

?設(shè)順序線性表的長度為30,分成5塊，每塊6個元素，如果采用分塊查

找，則其平均查找長度為6.5。

設(shè)分塊查找中將長為n的表分成均等的b個塊，每塊s個元素，則b=

(n/s)上取整。

如果索引表中采用順序查找，則ASL=(b+1)/2+(s+1)/2;

如果索引表中采用折半查找，則ASL=(s+l)/2+log2(b+l)-l;

?設(shè)指針p指向單鏈表中結(jié)點A,指針s指向被插入的結(jié)點X,則在結(jié)點

A的前面插入結(jié)點X時的操作序列為：

s->next=p->next;2)p->next=s;3)t=p->data;

p->data=s->data;5)s->data=t;

?設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列

雙向循環(huán)鏈表存儲方式最節(jié)省運算時間。

如果只是插入元素，單向循環(huán)列表就可以了；

如果還需要刪除元素，就要雙向循環(huán)列表，可以最快的找到尾節(jié)點的前一

個節(jié)點。

?有N個關(guān)鍵字排序，各排序最大最小情況如下：

?快速排序算法的平均時間復雜度為O(nlog2n)直接插入排序算法的平

均時間復雜度為。6人2)。

?設(shè)一棵m叉樹脂的結(jié)點數(shù)為n,用多重鏈表表示其存儲結(jié)構(gòu)，則該樹中

有n(m-l)+l個空指針域。

【注解】m叉樹n個結(jié)點，得出總的指針域為m*n,不為空的指針域就等

于分枝數(shù)，根結(jié)點沒有分支指向它，推出非空指針域為n-1，總指針域減非空指

針域就等于空的指針域即m*n-(n-1)

?設(shè)指針變量p指向單鏈表中結(jié)點A,則刪除結(jié)點A的語句序列為：

q=p->next;p->data=q->data;p->next=q->next;feee(q);

①數(shù)據(jù)結(jié)構(gòu)從邏輯上劃分為三種基本類型：線性結(jié)構(gòu)，樹型結(jié)構(gòu)和圖型

結(jié)構(gòu)。

②設(shè)無向圖G中有n個頂點e條邊：則用鄰接矩陣作為圖的存儲結(jié)構(gòu)進行

深度優(yōu)先或廣度優(yōu)先遍歷時的時間復雜度為0(nA2);

用鄰接表作為圖的存儲結(jié)構(gòu)進行深度優(yōu)先或廣度優(yōu)先遍歷的時間復雜度

為O(n+e)o

③鄰接表是圖的一種鏈式存儲結(jié)構(gòu)。

④樹最適合用來表示元素之間具有分支層次關(guān)系的數(shù)據(jù)。

⑤在一個單鏈表中，若要刪除由指針q所指向結(jié)點的后繼結(jié)點(若存在),

則執(zhí)行p=q->next;q->next=p->next操作。

⑥常對數(shù)組進行的兩種基本操作是索引和修改。

⑦在一個單鏈表中，已知q所指結(jié)點是p所指結(jié)點的直接前驅(qū)，若在q和

p之間插入s所指結(jié)點，則執(zhí)行q->next=s;s->next=p操作。

⑧設(shè)有兩個串p和q,求q在p中首次出現(xiàn)的位置的運算稱作模式匹配。

⑨一個高度為h的滿二叉樹共有n個結(jié)點，其中有m個葉子結(jié)點，則有

n=2m-l成立。

⑩實現(xiàn)圖的廣度優(yōu)先搜索遍歷算法需要使用隊列，深度優(yōu)先搜索遍歷算法

需要使用棧。

?順序表中邏輯上相鄰的元素的物理位置必定相鄰。單鏈表中邏輯上相鄰

的元素的物理位置不一定相鄰。

?樹的先序?qū)鏄涞南刃?，樹的后序?qū)鏄涞闹行颉?/p>

?在n(n>0)個元素的順序棧中刪除1個元素的時間復雜度為：0(1)。

?設(shè)SQ為循環(huán)隊列，存儲在數(shù)組d[m]中，則SQ出隊操作對其隊頭

指針front的修改是front=(front+l)%m。

對于一個以順序?qū)崿F(xiàn)的循環(huán)隊列,隊頭、隊尾指針分別為f、

,其判空的條件是判滿的條件是

rr=f,(r+l)%m=fo

①設(shè)計一個判別表達式中括號是否匹配出現(xiàn)的算法，采用棧的數(shù)據(jù)結(jié)構(gòu)

最佳。

②設(shè)廣義表L=((a,b,c)),則L的長度為1,深度為2。

③衡量查找算法效率的主要標準是平均查找長度。

④棧和隊列都是限制存取點的線性結(jié)構(gòu)。

⑤在稀疏矩陣的三元組M序表中，每個三元組表示矩陣中非零元素的行號、

列號和數(shù)據(jù)值。

⑥順序結(jié)構(gòu)邏輯上相鄰的結(jié)點物理上也是相鄰的。因此，其存儲密度大，

存儲空間利用串高。

⑦含有n個結(jié)點的二叉樹采用二叉鏈表存儲時，空指針域的個數(shù)為n+1,

非空指針個數(shù)為

n-lo

⑧在數(shù)據(jù)結(jié)構(gòu)中，從存儲結(jié)構(gòu)上可以將之分為順序存儲和非順序存儲；從

邏輯結(jié)構(gòu)上可以將之分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)。

⑨深度優(yōu)先遍歷類似二叉樹的先序遍歷；廣度優(yōu)先遍歷類似二叉樹的層

次遍歷。

⑩n個頂點的有向圖最多有n(n-l)條邊;無向圖最多有n(n-l)/2條邊。

?如果要求用線性表既能較快地查找，又能適應動態(tài)變化的要求，則可采用

分塊查找。

?任意一棵二叉樹的葉子結(jié)點在其先序、中序和后序序列中的相對位置

不發(fā)生變化。

?在單鏈表指針為p的結(jié)點之后插入指針為s的結(jié)點，正確的操作是

s->next=p->next;p->next=so

?某算法的時間復雜度是0(n人2),表明該算法的執(zhí)行時間與r?A2成正

比。

?對于一個具有n個頂點和e條邊的無向圖，若采用鄰接表表示，則表頭

向量的大小為n,占用的存儲空間為2eo

?對于順序表，訪問某結(jié)點的時間復雜度為0(1),刪除某結(jié)點的時間復

雜度為0(n)。

?以數(shù)據(jù)集｛4,5,6,7,10,12,18｝為結(jié)點權(quán)值，畫出構(gòu)造的哈弗曼樹，并計算

其帶權(quán)路徑長度。

?廣義表(a,(b,c),d,e)的表頭為ao

已知廣義表L=(a,(b,(c,(d)),e),f),則：

Ll=Tail(L)=((b,(c,(d)),e),f)

L2=Head(Ll)=(b,(c,(d)),e)

L3=Tail(L2)=((c,(d)),e)

L4=Head(L3)=(c,(d))

L5=Head(L4)=c

?樹最適合用來表示的結(jié)構(gòu)是元素間具有分支層次關(guān)系的結(jié)構(gòu)。

?圖G是一個非連通無向圖，共有28條邊，則該圖至少有9個頂點。

①棧的特點是一個線性結(jié)構(gòu)，數(shù)據(jù)先進后出，且只能在棧頂進行增刪操作。

②與數(shù)據(jù)元素本身的形式、內(nèi)容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的邏輯結(jié)

構(gòu)。

③數(shù)據(jù)結(jié)構(gòu)被形式定義為(D,R),其中D是數(shù)據(jù)元素的有限集合，R是

D上的關(guān)系有限集合。

④當利用大小為N的數(shù)組順序存儲一個棧時，假定用top==N表示?？?

則向這個棧插入一個元素時，首先應執(zhí)行top一語句修改top指針。

⑤設(shè)有一個字符串S="abcdefgh",問該串的最大子串個數(shù)為37。

⑥若StrIndex(S,T)表示求T在S中的位置的操作則對于S="Beijingand

Nanjing",T="jing",StrIndex(S,T)的結(jié)果為4。

⑦字符串按存儲方式可以分為：順序存儲、鏈接存儲和堆分配存儲。

⑧在C語言中，以字符\0表示串值的終結(jié)。

⑨A[N,N]是對稱矩陣，將下三角(含對角線)以行序存儲到一維數(shù)組

arr[N(N+l)/2]中,則對任一上三角元素arr[i,j]對應arr[k]的下標k是：解析如

下

⑩有一個100*90的稀疏矩陣，非零元素有10個，設(shè)每個整型數(shù)占2個

字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是66。

?已知廣義表LS=((a,b,c),(d,e,f)),對其運用Head和Tail運算，

取出其中原子e的運算是Head(Tail(Head(Tail(LS))))

?畫出廣義表((((a),b)),(((),d),(e,f)))的鏈式存儲結(jié)構(gòu)圖示。

?引入二叉線索樹的目的是加快查找結(jié)點的前驅(qū)或后繼的速度。

?利用二叉鏈表存儲一般樹，則根結(jié)點的右指針是空；因為左孩子右兄

弟，根節(jié)點無兄弟。

?深度優(yōu)先遍歷類似于二叉樹的先序遍歷；廣度優(yōu)先遍歷類似于二叉樹

的層次遍歷。

?用鄰接表表示圖進行廣度優(yōu)先遍歷時，通常借助隊列來實現(xiàn)算法。

用鄰接表表示圖進行深度優(yōu)先遍歷時，通常借助棧來實現(xiàn)算法。

?拓撲排序方法可以判斷出一個有向圖是否有環(huán)。

?圖中的一條路徑長度為k,該路徑所含的頂點數(shù)為K+1。

?數(shù)據(jù)的最小單位是數(shù)據(jù)項。

?設(shè)一個有序的單鏈表中有n個結(jié)點，現(xiàn)要求插入一個新結(jié)點后使得單

鏈表仍然保持有序，則該操作的時間復雜度為

O(n)o

①在圖的鄰接表中用順序存儲結(jié)構(gòu)存儲表頭結(jié)點的優(yōu)點是可以隨機訪問

到任意點的簡單鏈表。

②設(shè)一棵m叉樹中度數(shù)為0的結(jié)點數(shù)為NO,度數(shù)為1的結(jié)點數(shù)為

NI.........度數(shù)為m的結(jié)點數(shù)為Nm,則N0=l+N2+2N3+3N4+......

+(m-l)Nm?

③設(shè)有一個n階的下三角矩陣A,如果按照行的順序?qū)⑾氯蔷仃囍械?/p>

元素(包括對角線上元素)存放在n(n+l)個連續(xù)的存儲單元中，則A[i][j]與

A[0][0]之間有i*(i+l)/2+j-l或i*(i+l)/2+i個數(shù)據(jù)元素。

④設(shè)一條單鏈表的頭指針變量為head且該鏈表沒有頭結(jié)點，則其判空條

件是

head==0o

head為指向表頭結(jié)點的指針，分別寫出帶有頭結(jié)點的單鏈表、單項循環(huán)鏈

表和雙向循環(huán)鏈表判空的條件：

單鏈表NULL==head->next

單向循環(huán)head==head->next

雙向循環(huán)head==head->next&&head==head->prior

⑤head為指向表頭結(jié)點的指針，分別寫出不帶有頭結(jié)點的單鏈表、單項

循環(huán)鏈表和雙向循環(huán)鏈表判空的條件：

單鏈表NULL==head

單向循環(huán)head==head->next

雙向循環(huán)head==head->next&&head==head->prior

⑥設(shè)F和R分別表示順序循環(huán)隊列的頭指針和尾指針，則判斷該循環(huán)隊列

為空的條件為F==R。

⑦散列表中解決沖突的兩種方法是開放地址法和鏈接法。

⑧設(shè)指針變量top指向當前鏈式棧的棧頂，則刪除棧頂元素的操作序列

為

top=top->nexto

⑨設(shè)關(guān)鍵字序列為(KI,K2,Kn),則用篩選法建初始堆必須從第n/2

個元素開始進行篩選。

⑩建立一個長度為的有序單鏈表的時間復雜度為A

nO(n2)o

設(shè)順序表的長度為則順序查找的平均比較次數(shù)為

?n,(n+l)/2o

?設(shè)順序線性表的長度為30,分成5塊，每塊6個元素，如果采用分

塊查找，則其平均查找長度為6.5。

?在堆排序中，對n個記錄建立初始堆需要調(diào)用n/2次調(diào)整算法。

?已知一棵完全二叉樹中共有768結(jié)點則該樹中共有384個葉子結(jié)點。

?一個一維數(shù)組a[10]中存儲著有序表(15,26,34,39,45,56,58,63,74,76),

根據(jù)折半搜索所對應的判定樹，寫出該判定樹中度為1的結(jié)點個數(shù)，并求出在等

概率情況下進行成功搜索時的平均搜索長度。度為1的結(jié)點個數(shù)：3;平均搜索

長度:29/10.

?一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復雜度

為

O(l)o

解析：數(shù)組是隨機訪問的數(shù)據(jù)結(jié)構(gòu)，平均時間復雜度為。(1)

?含n個頂點的無向連通圖中至少含有n-1條邊。

?順序表中，邏輯上相鄰的元素，其物理位置也相鄰，在鏈表中，邏輯上相鄰

的元素，其物理位置不一定相鄰。

?利用三元組表存放稀疏矩陣中的非零元素，則在三元組表中每個三元組

元素對應一個非零元素的行號、列號和值。

?數(shù)據(jù)的邏輯結(jié)構(gòu)是從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(或存儲結(jié)

構(gòu))無關(guān)，是獨立于計算機的。

①區(qū)分循環(huán)隊列的滿與空，有三種方法，它們是少用一個存儲單元、設(shè)置

一個標志位和設(shè)置一個計數(shù)器。

②根據(jù)線性表的鏈式存儲結(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù)，將線性鏈表

分成單鏈表和雙鏈表。

③數(shù)據(jù)結(jié)構(gòu)中評價算法的兩個重要指標是時間復雜度和空間復雜度。

④最大容量為n的循環(huán)隊列，隊尾指針是rear,隊頭是front,則隊空的

條件是rear==front;隊滿條件是(rear+1)%n==front;當前隊列中的元

素個數(shù)為

(rear-front+n)%no

⑤一個遞歸算法必須包括終止條件和遞歸部分。

⑥循環(huán)隊列存儲在數(shù)組中，則入隊時的操作為rear=(rear+l)

mod(m+l)o

⑦設(shè)計一個判別表達式中左，右括號是否配對出現(xiàn)的算法，采用棧數(shù)據(jù)

結(jié)構(gòu)最佳。

⑧元素的移動次數(shù)與關(guān)鍵字的初始排列次序無關(guān)的是：基數(shù)排序

元素的比較次數(shù)與初始序列無關(guān)是：選擇排序

算法的時間復雜度與初始序列無關(guān)的是：直接選擇排序

⑨若一個棧以向量V[1…n]存儲，初始棧頂指針top為n+l,則下面x進

棧的正確操作是：

top=top-l;V[top]=xo

⑩利用帶頭結(jié)點的二叉鏈表存儲樹，則根結(jié)點的右指針是空。二叉鏈表：

左孩子右兄弟，根節(jié)點沒有兄弟，所以為空。

?設(shè)二叉排序樹的高度為h,則在該樹中查找關(guān)鍵字key最多需要比較h

次。

?入棧操作和入隊列操作在鏈式存儲結(jié)構(gòu)上實現(xiàn)時不需要考慮棧溢出的

情況。正確，鏈式存儲結(jié)構(gòu)是動態(tài)分配空間的。

?用鄰接矩陣作為圖的存儲結(jié)構(gòu)時，則其所占用的存儲空間與圖中頂點數(shù)

有關(guān)。圖的鄰接矩陣存儲所占用空間大小只與頂點個數(shù)有關(guān)，更準確地說，設(shè)頂

點n個，則與rT2成正比

?設(shè)一維數(shù)組中有n個數(shù)組元素，則讀取第i個數(shù)組元素的平均時間復雜

度為0(1).

?堆是完全二叉樹，完全二叉樹不一定是堆。

?不論線性表采用順序存儲結(jié)構(gòu)還是鏈式存儲結(jié)構(gòu)，刪除值為X的結(jié)點的

時間復雜度均為0(n)。

?設(shè)一組初始記錄關(guān)鍵字序列(kl,k2.........kn)是堆，則對i=l,2，…，

而言滿足的條件為

n/2ki<=k2i&&ki<=k2i+lo

?設(shè)一組初始記錄關(guān)鍵字序列為(345,253,674,924,627),則用基

數(shù)排序需要進行3趟的分配和回收才能使得初始關(guān)鍵字序列變成有序序列。

?設(shè)有序順序表中有n個數(shù)據(jù)元素，則利用二分查找法查找數(shù)據(jù)元素X的

最多比較次數(shù)不超過Iog2n+lo

?畫出廣義表LS=((),(e)z(a,(b,c,d)))的頭尾鏈表存儲結(jié)構(gòu)。

21設(shè)散列表的地址范圍是［0...9］,散列函數(shù)為H(key)=(key2+2)

MOD9,并采用鏈表處理沖突，請畫出元素7、4、5、3、6、2、8、9依次插入

散列表的存儲結(jié)構(gòu)。

H(4)=H(5)=0,H(3)=H(6)=H(9)=2,H(8)=3,H(2)=Hf7)=6

①二分查找的過程可以用一棵二叉樹來描述，該二叉樹稱為二叉判定樹。

在有序表上進行二分杳找時的查找長度不超過二叉判定樹的高度1+Iog2n。

②設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，則選用下列

雙向循環(huán)鏈表存儲方式最節(jié)省運算時間。

③將兩個各有n個元素的有序表歸并成一個有序表，其最少的比較次數(shù)是

n次，最多2n-l次。

④循環(huán)隊列存儲在數(shù)組中，則入隊時的操作為

rear=(rear+l)%(m+l)o

入隊是：rear=(rear+l)%(m+l)〃m+l代表有m+1個空間它是0

到m的數(shù)組

出隊是：front=(front+1)%(m+1)

⑤循環(huán)隊列放在一維數(shù)組AO..M-1］中，endl指向隊頭元素，end2指向

隊尾元素的后一個位置。假設(shè)隊列兩端均可進行入隊和出隊操作，隊列中最多能

容納M-1個元素。初始時為空。則隊空：endl==end2;隊滿:

endl==(end2+l)modM

⑥一個棧的入棧序列為1,2,3，…，n,其出棧序列是pl,p2,p3...,

若則可能取值的個數(shù)是

pnop2=3,p3n-1;

⑦圖的BFS生成樹的樹高小或相等DFS生成樹的樹高。

【例題】線性表(al,a2,..?an)采用順序存儲結(jié)構(gòu)。試問：

(1)在等概率的前提下，平均每插入一個元素需要移動的元

素個數(shù)為多少？

(2)若元素插在ai與ai+1之間(04isn-1)的概率為，

則平均每插入一個元素所要移動的元素個數(shù)又是多少？

①線性表的順序存儲結(jié)構(gòu)是一種隨機存取的存儲結(jié)構(gòu)，線性結(jié)構(gòu)的鏈式

存儲是一種順序存取的存儲結(jié)構(gòu)。

②數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的操作對象以及它們之間的關(guān)系和

運算等的學科。

③一個數(shù)據(jù)結(jié)構(gòu)在計算機存儲器內(nèi)的表示稱為存儲結(jié)構(gòu)。

④鏈棧和順序棧相比較，有一個較為明顯的優(yōu)點是通常不會出現(xiàn)棧滿的情

況。

⑤引入循環(huán)隊列的目的是為了克服"假溢出"現(xiàn)象。

⑥區(qū)分循環(huán)隊列的滿與空，只有兩種方法，它們是犧牲一個存儲單元和

設(shè)標記。

⑦設(shè)循環(huán)隊列存放在向量data[O…M]中，則隊頭指針front在循環(huán)意義下

的出隊操作可表示為front=(front+l)%(M+l),若用犧牲一個單元的辦法來區(qū)

分隊滿和隊空(設(shè)隊尾指針則隊滿的條件為

rear),front==(rear+l)%(M+l)o

⑧對于長度為n且順序存儲的線性表，在任何位置上操作都是等概率的情

況下，插入一個元素需要平均移動表中的元素個數(shù)；刪除一個元素平均需要移

動表中元素。

⑨在一個不帶頭結(jié)點的單鏈表中，在表頭插入或刪除與在其他位置上插入

或刪除其操作過程不相同。

⑩在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過存儲位置決定的；

在線性表的鏈式存儲中，元素之間的邏輯關(guān)系是通過指針決定的。

?單鏈表表示法的基本思想是用指針表示結(jié)點的邏輯關(guān)系。

?數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)元素間的邏輯關(guān)系，數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)在

計算機中的表示(又稱映像)方法，是數(shù)據(jù)的邏輯結(jié)構(gòu)在計算機中的存儲實現(xiàn)。

?數(shù)據(jù)的物理結(jié)構(gòu)包括數(shù)據(jù)元素的表示和數(shù)據(jù)元素間關(guān)系的表示。

?程序=數(shù)據(jù)結(jié)構(gòu)+算法。

?線性表L=(al,a2，…,an)用數(shù)組表示，假定刪除表中任一元素的概率相

同，則刪除一個元