C題庫期末復(fù)習(xí)

期末復(fù)習(xí)第一章緒論數(shù)據(jù)結(jié)構(gòu)的基本概念和術(shù)語數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)等基本概念數(shù)據(jù)結(jié)構(gòu)的邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)及數(shù)據(jù)運(yùn)算的含義及其相互關(guān)系數(shù)據(jù)結(jié)構(gòu)的四種邏輯結(jié)構(gòu)及四種常用的存儲(chǔ)表示方法抽象數(shù)據(jù)類型的概念及其與數(shù)據(jù)結(jié)構(gòu)的關(guān)系算法的描述和分析算法、算法的時(shí)間復(fù)雜度和空間復(fù)雜度的概念算法描述和算法分析的方法第二章線性表線性表的邏輯結(jié)構(gòu)線性表的邏輯結(jié)構(gòu)特征線性表上定義的基本運(yùn)算，并能利用基本運(yùn)算構(gòu)造出較復(fù)雜的運(yùn)算線性表的順序存儲(chǔ)結(jié)構(gòu)順序表的存儲(chǔ)方式及它如何映射線性表中元素之間的邏輯關(guān)系順序表的存儲(chǔ)結(jié)構(gòu)定義線性表基本運(yùn)算在順序表上的實(shí)現(xiàn)方法及其時(shí)間性能分析利用順序表設(shè)計(jì)算法解決應(yīng)用問題設(shè)順序表va中的數(shù)據(jù)元素遞增有序。試寫一算法，將x插入到順序表的適當(dāng)位置上，以保持該表的有序性。解題思路：在遞增有序的順序表中插入一個(gè)元素x，首先應(yīng)查找待插入元素的位置。因順序表元素遞增有序，采用折半查找法比順序查找效率要高。查到插入位置后，從此位置直到線性表尾依次向后移動(dòng)一個(gè)元素位置，之后將元素x插入即可。假設(shè)順序表va存放在數(shù)組A[]中（假設(shè)下標(biāo)從1開始）。voidInsert（ElemTypeA[]，intsize,ElemTypex）。

{low=1；high=num；//假設(shè)下標(biāo)從1開始

while（low<=high）∥對(duì)分查找元素x的插入位置。

{mid=（low+high）/2；

if（A[mid]==x）{low=mid+1；break；}

else

if（A[mid]>x）high=mid-1；elselow=mid+1；

}

for（i=num；i>=low；i--）A[i+1]=A[i]；∥元素后移。

A[i+1]=x；∥將元素x插入。

}算法結(jié)束線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)鏈表的存儲(chǔ)方式及它如何映射線性表中元素之間的邏輯關(guān)系鏈表中頭指針和頭節(jié)點(diǎn)的使用單鏈表、雙鏈表、循環(huán)鏈表在鏈接方式上的區(qū)別各種鏈表的存儲(chǔ)結(jié)構(gòu)定義線性表基本運(yùn)算在鏈表上的實(shí)現(xiàn)方法及其時(shí)間性能分析循環(huán)鏈表上尾指針取代頭指針的作用利用鏈表設(shè)計(jì)算法解決簡單的應(yīng)用問題已知線性表中的元素以值遞增有序排列，并以單鏈表（帶頭結(jié)點(diǎn)）作為存儲(chǔ)結(jié)構(gòu)，試寫一算法刪除表中所有值大于mink且小于maxk的元素。

解題思路：首先找到最后一個(gè)元素值小于等于mink的結(jié)點(diǎn)位置（q）；再往后依次刪除結(jié)點(diǎn)直到第一個(gè)值大于等于maxk結(jié)點(diǎn)為止。voiddelete(sqlist*la,intmink,intmark){sqlist*p,*q,;

q=la;

p=la->next;

while(p&&p->data<=mink)

{q=p;p=p->next;}

while(p&&p->data<maxk)

{u=p;p=p->next;free(p);}

q->next=p;}寫出單鏈表（帶頭結(jié)點(diǎn)）就地逆置算法。voidreverse(linklist*h){linklistp,q;p=h->next;h->next=NULL;while(p!=null){q=p;//q指向當(dāng)前結(jié)點(diǎn)p=p->next;//p指向下一個(gè)結(jié)點(diǎn)q->next=h->next;//將*q插入到*h之后h->next=q;}}順序表和鏈表的比較順序表和鏈表的主要優(yōu)缺點(diǎn)根據(jù)應(yīng)用問題的時(shí)空要求，為線性表選擇合理的存儲(chǔ)結(jié)構(gòu)第三章棧與隊(duì)列棧的邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)及其相關(guān)算法棧的邏輯結(jié)構(gòu)特點(diǎn)，棧與線性表的關(guān)系順序棧和鏈棧的存儲(chǔ)結(jié)構(gòu)定義順序棧和鏈棧上進(jìn)棧、退棧等基本運(yùn)算的實(shí)現(xiàn)方法棧上的“上溢”和“下溢”的概念及其判別條件遞歸過程中棧的作用設(shè)計(jì)遞歸程序的原則和方法利用棧設(shè)計(jì)算法解決簡單的應(yīng)用問題假設(shè)以S和X分別表示入棧和出棧操作，則對(duì)初態(tài)和終態(tài)均為空的棧操作可由S和X組成的序列表示（如SXSX）。（1）試指出判別給定序列是否合法的一般規(guī)則。（2）兩個(gè)不同合法序列（對(duì)同一輸入序列）能否得到相同的輸出元素序列？如能得到，請(qǐng)舉列說明。

（1）通常有兩條規(guī)則。第一是給定序列中S的個(gè)數(shù)和X的個(gè)數(shù)相等；第二是從給定序列的開始，到給定序列中的任一位置，S的個(gè)數(shù)要大于或等于X的個(gè)數(shù)。（2）可以得到相同的輸出元素序列。例如，輸入元素為A，B，C，則兩個(gè)輸入的合法序列ABC和BAC均可得到輸出元素序列ABC。對(duì)于合法序列ABC，我們使用本題約定的S×S×S×操作序列；對(duì)于合法序列BAC，我們使用SS××S×操作序列。試證明：若借助棧由輸入序列1,2,…,n得到輸出序列為P1,P2,…,Pn（它是輸入序列的一個(gè)排列），則在輸出序列中不可能出現(xiàn)這樣的情形：存在著i<j<k,使Pj<Pk<Pi。

如果i<j，則對(duì)于pi<pj情況，說明pi在pj入棧前先出棧。而對(duì)于pi>pj的情況，則說明要將pj壓到pi之上，也就是在pj出棧之后pi才能出棧。這就說明，對(duì)于i<j<k，不可能出現(xiàn)pj<pk<pi的輸出序列。換句話說，對(duì)于輸入序列1，2，3，不可能出現(xiàn)3，1，2的輸出序列。隊(duì)列的邏輯結(jié)構(gòu)，存儲(chǔ)結(jié)構(gòu)及其相關(guān)算法隊(duì)列的邏輯結(jié)構(gòu)特點(diǎn)，隊(duì)列與線性表的關(guān)系順序隊(duì)列和鏈隊(duì)列的存儲(chǔ)結(jié)構(gòu)定義（PASCAL語言的類型描述）順序隊(duì)列（主要是循環(huán)隊(duì)列）和鏈隊(duì)列上入隊(duì)、出隊(duì)等基本運(yùn)算的實(shí)現(xiàn)方法隊(duì)列的“上溢”和“下溢”的概念及其判別條件循環(huán)隊(duì)列取代普通的順序隊(duì)列的原因利用隊(duì)列設(shè)計(jì)算法解決簡單的應(yīng)用問題在一個(gè)循環(huán)鏈隊(duì)中只有尾指針（記為rear，結(jié)點(diǎn)結(jié)構(gòu)為數(shù)據(jù)域data，指針域next），請(qǐng)給出這種隊(duì)列的入隊(duì)和出隊(duì)操作的實(shí)現(xiàn)過程（算法）。

voidEnQueue(LinkedListrear,ElemTypex){s=(LinkedList)malloc(sizeof(LNode));//申請(qǐng)結(jié)點(diǎn)空間

s->data=x;s->next=rear->next;//將s結(jié)點(diǎn)鏈入隊(duì)尾

rear->next=s;rear=s;//rear指向新隊(duì)尾}voidDeQueue(LinkedListrear){if(rear->next==rear){printf(“隊(duì)空\n”);exit(0);}s=rear->next->next;//s指向隊(duì)頭

rear->next->next=s->next;//隊(duì)頭出隊(duì)。

printf(“出隊(duì)元素是”，s->data);

if(s==rear)rear=rear->next;//空隊(duì)列

free(s);}第四章串串及其運(yùn)算串的概念及其與線性表的關(guān)系串上定義的基本運(yùn)算，并能利用基本運(yùn)算構(gòu)造出較復(fù)雜的運(yùn)算串的存儲(chǔ)結(jié)構(gòu)和基本運(yùn)算的實(shí)現(xiàn)串的兩種主要存儲(chǔ)結(jié)構(gòu)—順序串和鏈串的存儲(chǔ)結(jié)構(gòu)定義（C語言的類型描述）順序串上串的基本運(yùn)算的實(shí)現(xiàn)樸素的模式匹配算法與KMP算法的算法思想及時(shí)間復(fù)雜度分析KMP算法中next和nextval數(shù)組的求值方法

求模式串t1=‘a(chǎn)aab’，t2=‘a(chǎn)bcabaa’，t3=‘a(chǎn)dabbadada’的next和nextval數(shù)組值第六章樹樹的概念樹的邏輯結(jié)構(gòu)特征樹的常用術(shù)語及含義二叉樹二叉樹的定義，二叉樹與樹的差別完全二叉樹和滿二叉樹的概念二叉樹的性質(zhì)二叉樹的順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的定義（C語言的類型描述）和表示方法二叉樹的遍歷二叉樹的先序、中序、后序、層序遍歷算法求給定二叉樹的先序、中序、后序遍歷對(duì)應(yīng)的結(jié)點(diǎn)訪問序列由二叉樹的先序和中序、中序和后序、中序和層序的序列確定二叉樹以遍歷算法為基礎(chǔ)，設(shè)計(jì)有關(guān)算法解決簡單的應(yīng)用問題線索二叉樹二叉樹線索化的目的線索二叉樹存儲(chǔ)結(jié)構(gòu)的表示方法在線索二叉樹中查找給定結(jié)點(diǎn)的前趨和后繼的方法樹和森林樹和森林與二叉樹之間的轉(zhuǎn)換方法和對(duì)應(yīng)關(guān)系樹的各種存儲(chǔ)結(jié)構(gòu)的表示方法及其特點(diǎn)樹的先序和后序遍歷方法森林的先序和中序遍歷方法哈夫曼樹及其應(yīng)用最優(yōu)二叉樹的概念及特點(diǎn)求哈夫曼樹的方法設(shè)計(jì)哈夫曼編碼的方法一、下面是用c語言編寫的對(duì)不帶頭結(jié)點(diǎn)的單鏈表進(jìn)行就地逆置的算法，該算法用L返回逆置后的鏈表的頭指針，試在空缺處填入適當(dāng)?shù)恼Z句（不允許使用額外的輔助變量）。voidreverse（linklist&L）{p=NULL;q=L;while（q!=NULL）{(1);q->next=p;p=q;(2)___;}

(3)_____;}二、假設(shè)以I和O分別表示入棧和出棧操作。棧的初態(tài)和終態(tài)均為空，入棧和出棧的操作序列可表示為僅由I和O組成的序列，稱可以操作的序列為合法序列，否則稱為非法序列。（1）下面所示的序列中哪些是合法的？

A.IOIIOIOOB.IOOIOIIOC.IIIOIOIOD.IIIOOIOO（2）通過對(duì)（1）的分析，寫出一個(gè)算法，判定所給的操作序列是否合法。若合法，返回TRUE，否則返回FALSE（假定被判定的操作序列已存入一維數(shù)組A中）。三、設(shè)模式串t=‘a(chǎn)bcabaa’，試求出該模式串的next和nextval數(shù)組的值。四、設(shè)一棵二叉樹的先序、中序遍歷序列分別為先序遍歷序列：ABDFCEGH中序遍歷序列：BFDAGEHC（1）畫出這棵二叉樹。（2）畫出這棵二叉樹的后序線索樹。（3）將這棵二叉樹轉(zhuǎn)換成對(duì)應(yīng)的樹（或森林）。第七章圖圖的概念圖的邏輯結(jié)構(gòu)特征圖的常用術(shù)語及含義圖的存儲(chǔ)結(jié)構(gòu)圖的鄰接矩陣的存儲(chǔ)結(jié)構(gòu)定義及表示法和特點(diǎn)圖的鄰接表的存儲(chǔ)結(jié)構(gòu)定義及表示法和特點(diǎn)圖的遍歷圖的深度優(yōu)先搜索和廣度優(yōu)先搜索遍歷算法及時(shí)間性能確定兩種遍歷所得到的頂點(diǎn)訪問序列圖的兩種遍歷與樹的遍歷之間的關(guān)系利用圖的兩種遍歷設(shè)計(jì)算法解決簡單的應(yīng)用問題生成樹和最小生成樹生成樹和最小生成樹的概念對(duì)給定的圖畫出深度和廣度優(yōu)先生成樹或生成森林Prim和Kruskal算法的基本思想對(duì)給定的連通圖，根據(jù)Prim和Kruskal算法構(gòu)造出最小生成樹有向無環(huán)圖的應(yīng)用拓?fù)渑判虻幕舅枷牒筒襟E拓?fù)渑判虿怀晒Φ脑蚯蠼o定AOV網(wǎng)的拓?fù)湫蛄嘘P(guān)鍵路徑、關(guān)鍵活動(dòng)的概念求AOE網(wǎng)的關(guān)鍵路徑的步驟和方法對(duì)給定的AOE網(wǎng)，求關(guān)鍵路徑和工期最短路徑最短路徑的含義求單源最短路徑的Dijkstra算法的基本思想和時(shí)間性能對(duì)于給定的有向圖，畫出根據(jù)Dijkstra算法求單源最路徑的過程示意圖求每一對(duì)頂點(diǎn)間最短路徑的Floyd算法的基本思想和時(shí)間性能A(k)[i,j](1≤k≤n)的含義對(duì)于給定的有向圖，用Floyd算法求每一對(duì)頂點(diǎn)之間的最短路徑長度，能寫出A(0)

，Ａ(1)

，……Ａ(n)的值1.請(qǐng)給出所示有向圖的

1)每個(gè)頂點(diǎn)的入/出度；

2)鄰接矩陣；

3)逆鄰接表；

4)強(qiáng)連通分量。2.畫出所示無向圖的鄰接表，它所鄰接到的頂點(diǎn)序號(hào)由小到大排列，列出從頂點(diǎn)1出發(fā)深度優(yōu)先和廣度優(yōu)先搜索遍歷該圖所得頂點(diǎn)序列和邊的序列。1562431524633.分別畫出按以下兩種算法求所示無向帶權(quán)圖的最小生成樹的過程

1)Prim算法

2)Kruskal算法4.試列出下圖中全部可能的拓?fù)溆行蛐蛄?，并指出?yīng)用教材182頁算法toposort求得的是哪一個(gè)。abcedfgh493265355765451235645.對(duì)于如下AOE網(wǎng)絡(luò)，計(jì)算各活動(dòng)弧的e(ai)和l(ai)函數(shù)值，列出關(guān)鍵路徑。123456789a1=6a2=4a3=5a4=1a5=1a6=2a7=9a8=8a9=4a10=2a11=4第九章查找基本概念靜態(tài)查找表和動(dòng)態(tài)查找表的含義平均查找長度ASL的定義靜態(tài)查找表順序查找、折半查找、分塊查找的算法思想、算法實(shí)現(xiàn)、ASL的分析計(jì)算折半查找對(duì)存儲(chǔ)結(jié)構(gòu)和關(guān)鍵字的要求三種查找方法的主要優(yōu)缺點(diǎn)動(dòng)態(tài)查找表二叉排序樹的定義、特點(diǎn)和用途二叉排序樹的查找方法和算法實(shí)現(xiàn)、ASL的分析和計(jì)算二叉排序樹的插入、刪除、建樹方法輸入實(shí)例對(duì)所建二叉排序樹形態(tài)的影響平衡二叉樹的定義和作用哈希表哈希表、哈希函數(shù)、哈希地址和裝填因子等有關(guān)概念哈希函數(shù)的選取原則及產(chǎn)生沖突的原因常用的哈希函數(shù)的構(gòu)造方法解決沖突的主要方法產(chǎn)生“堆積”現(xiàn)象的原因哈希表查找和其它表查找的本質(zhì)區(qū)別。采用線性探測法或拉鏈法解決沖突時(shí)，哈希表的建表方法、查找過程以及ASL的分析計(jì)算1.已知含12個(gè)關(guān)鍵字的有序表及其相應(yīng)權(quán)值為：

123456789101112

關(guān)鍵字ABCDEFGHIJKL

權(quán)值463493261534(1)畫出對(duì)以上有序表進(jìn)行折半查找的判定樹，求折半查找時(shí)查找成功的平均查找長度ASL。(2)若為等概率查找，求折半查找時(shí)查找成功的平均查找長度ASL。3.已知如下長度為12的表：(Jan,Feb,Mar,Apr,May,June,July,Aug,Sep,Oct,Nov,Dec)(1)試按表中元素的順序依次插入一棵初始為空的二叉排序樹，請(qǐng)畫出插入完成之后的二叉排序樹，并求其在等概率的情況下查找成功的平均查找長度ASL。選取哈希函數(shù)H(k)=(3k)MOD11。

1)用線性探測開放定址法處理沖突，

2)用鏈地址法處理沖突試在0~10的散列地址空間中對(duì)關(guān)鍵字序列(22,41,53,46,