一： 內(nèi)容：1、設(shè)線性表存放在向量A[arrsize]的前elenum個(gè)分量中，且遞增有序。試設(shè)計(jì)一算法，將x插入到線性表的適當(dāng)位置上，以保持線性表的有序性。 2、用向量作存儲(chǔ)結(jié)構(gòu)，試設(shè)計(jì)一個(gè)算法，僅用一個(gè)輔助結(jié)點(diǎn)，實(shí)現(xiàn)將線性表中的結(jié)點(diǎn)循環(huán)右移k位的運(yùn)算。 3、用向量作存儲(chǔ)結(jié)構(gòu)，試設(shè)計(jì)一個(gè)算法，僅用一個(gè)輔助結(jié)點(diǎn)，實(shí)現(xiàn)將線性表逆置的運(yùn)算。 要求：了解線性表的邏輯結(jié)構(gòu)特征，熟練掌握線性表的順序存儲(chǔ)結(jié)構(gòu)的描述方法，及在其上實(shí)現(xiàn)各種基本運(yùn)算的方法。 二：內(nèi)容：1、已知帶頭結(jié)點(diǎn)的動(dòng)態(tài)單鏈表L中的結(jié)點(diǎn)是按整數(shù)值遞增排序的，試寫一算法將值為x的結(jié)點(diǎn)插入到表L中，使L仍然有序。 2、設(shè)計(jì)一算法，逆置帶頭結(jié)點(diǎn)的動(dòng)態(tài)鏈表L。要求利用原表的結(jié)點(diǎn)空間，并要求用盡可能少的時(shí)間完成。 3、假設(shè)有兩個(gè)按元素值遞增有序的線性表A和B，均以單鏈表作存儲(chǔ)結(jié)構(gòu)，試編寫算法將A表和B表歸并成一個(gè)按元素值遞減有序的線性表C，并要求利用原表的空間存放C。 要求：熟練掌握線性表的單鏈?zhǔn)芥溄哟鎯?chǔ)結(jié)構(gòu)及在其上實(shí)現(xiàn)線性表的各種基本運(yùn)算的方法。 三：內(nèi)容：1、假設(shè)在長(zhǎng)度大于1的單循環(huán)鏈表中，既無頭結(jié)點(diǎn)也無頭指針。s為指向某個(gè)結(jié)點(diǎn)的指針，試編寫算法刪除結(jié)點(diǎn)*s的直接前驅(qū)結(jié)點(diǎn)。 2、已知由單鏈表表示的線性表中，含有三類字符的數(shù)據(jù)元素（如：字母、數(shù)字和其它字符），設(shè)計(jì)算法構(gòu)造三個(gè)以循環(huán)鏈表示的線性表，使每一個(gè)表中只含同一類的字符，且利用原表中的結(jié)點(diǎn)空間作為這三個(gè)表的空間。（頭結(jié)點(diǎn)可以另辟空間） 3、有一雙鏈表，每個(gè)結(jié)點(diǎn)中除有prior、data和next域外，還有一訪問頻度域freq，在鏈表被啟用前，其值均初始化為零。每當(dāng)在鏈表上進(jìn)行一次LOCATE(L,x)運(yùn)算，元素值為x的結(jié)點(diǎn)中freq域的值增1，并使此鏈表中結(jié)點(diǎn)保持按freq遞減的順序排列，以便使頻繁訪問的結(jié)點(diǎn)總是靠近表頭。設(shè)計(jì)滿足上述要求的LOCATE算法。 要求：熟練掌握線性表的循環(huán)鏈?zhǔn)胶碗p鏈?zhǔn)芥溄哟鎯?chǔ)結(jié)構(gòu)及在其上實(shí)現(xiàn)線性表的各種基本運(yùn)算的方法。 四：內(nèi)容：1、設(shè)單鏈表中存放著n個(gè)字符，設(shè)計(jì)算法，判斷該字符串中是否有中心對(duì)稱關(guān)系。例如：xyzzyx、xyzyx都算是中心對(duì)稱的字符串。 2、設(shè)計(jì)算法判斷一個(gè)算術(shù)表達(dá)式的圓括號(hào)是否配對(duì)。（提示：對(duì)表達(dá)式進(jìn)行掃描，遇‘(’進(jìn)棧，遇‘)’退掉棧頂?shù)摹?’，表達(dá)式被掃描完畢，棧為空) 3、假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并只設(shè)一個(gè)指針指向隊(duì)尾，編寫相應(yīng)的置隊(duì)空、入隊(duì)和出隊(duì)算法。 要求：掌握棧和隊(duì)列的數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)；熟練掌握在兩種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)棧和隊(duì)列的基本運(yùn)算；學(xué)會(huì)利用棧和隊(duì)列解決一些實(shí)際問題。 五：內(nèi)容：1、若X和Y是用結(jié)點(diǎn)大小為1的單鏈表表示的串，設(shè)計(jì)算法找出X中第一個(gè)不在Y中出現(xiàn)的字符。 2、設(shè)計(jì)一算法，在順序串上實(shí)現(xiàn)串的比較運(yùn)算strcmp(S,T)。 3、若S和T是用結(jié)點(diǎn)大小為1的單鏈表存儲(chǔ)的兩個(gè)串，設(shè)計(jì)算法將S中首次與T匹配的子串逆置。 要求：熟練掌握串的順序和鏈接存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)方法；熟練掌握在兩種存儲(chǔ)結(jié)構(gòu)上實(shí)現(xiàn)串的各種運(yùn)算。 六：內(nèi)容：1、以二叉鏈表作存儲(chǔ)結(jié)構(gòu)，設(shè)計(jì)求二叉樹高度的算法。 2、一棵n個(gè)結(jié)點(diǎn)的完全二叉樹用向量作存儲(chǔ)結(jié)構(gòu)，用非遞歸算法實(shí)現(xiàn)對(duì)該二叉樹進(jìn)行前序遍歷。 3、以二叉鏈表作存儲(chǔ)結(jié)構(gòu)，編寫非遞歸的前序、中序、后序遍歷算法。 要求：熟悉二叉樹的各種存儲(chǔ)結(jié)構(gòu)的特點(diǎn)及適用范圍；掌握建立二叉樹的存儲(chǔ)結(jié)構(gòu)的方法；熟練掌握二叉樹的前序、中序、后序遍歷的遞歸及非遞歸算法；靈活運(yùn)用遞歸的遍歷算法實(shí)現(xiàn)二叉樹的其它各種運(yùn)算。