【正文】 點(diǎn)的循環(huán)雙鏈表Ck的表頭指針為Ck_h，要在指針ptr指向處前插入一個(gè)rtr所指結(jié)點(diǎn)。 Lk_h = ptr。x)。 /* n為結(jié)點(diǎn)計(jì)數(shù)單元 */}return (n) 。答：算法設(shè)計(jì)如下：Length_Lk (Lk_h){n = 0 。 ptr = ptrNext 。有人編寫了下面的算法，試圖完成Prior域的鏈接：Com_Cd (Cd_h){ ptr = Cd_hNext 。 答：能夠達(dá)到在指針ptr所指結(jié)點(diǎn)之前插入一個(gè)由指針qtr所指結(jié)點(diǎn)的目的。 ptrNext = qtr 。對(duì)于單鏈表來說，得到一個(gè)結(jié)點(diǎn)的直接后繼容易，得到它的直接前驅(qū)難，所以這樣的設(shè)計(jì)是有其可取之處的。 ptrNext = ptrNextNext 。讀懂并加以理解。按照算法的描述，能夠保證插入后最后一個(gè)結(jié)點(diǎn)的Next域?yàn)椤唉眴?？答：能夠?4．如何判斷一個(gè)順序表是否為空？ 答：只需判定Sq_num的當(dāng)前值是多少，如果Sq_num為0，則表示順序表Sq為空，否則表示該順序表里有數(shù)據(jù)元素存在。 2．線性表L第i個(gè)存儲(chǔ)結(jié)點(diǎn)ai的起始地址LOC（ai）可以通過下面的公式計(jì)算得到： LOC（ai）= LOC（ai1）+k其中k表示存儲(chǔ)結(jié)點(diǎn)的長度。 D．ptrNext = qtr 。 B．qtrNext = ptrNext 。 Free (ptr)。C．tail = tailNextNext 。 B．tail = tailNext 。 A．ni B．ni+1 C．ni1 D．i 8．在長度為n的順序表中，刪除第i個(gè)元素（1≤i≤n）時(shí)，需要往前移動(dòng) A 個(gè)元素。 ptrNext = ptrNextNext 。 rtrNext = qtrNext。 B．ptrNext = rtrNext。 A．n B．n/2 C．n+1 D．(n+1)/2 5．在一個(gè)單鏈表中，已知qtr所指結(jié)點(diǎn)是ptr所指結(jié)點(diǎn)的直接前驅(qū)。二、選擇1．下面，對(duì)非空線性表特點(diǎn)的論述， C 是正確的。 qtrNext = ptr 。那么，該鏈表起始結(jié)點(diǎn)的存儲(chǔ)位置應(yīng)該表示成 tailNextNext 。 6．在一個(gè)雙鏈表中，已經(jīng)由指針ptr指向需要?jiǎng)h除的存儲(chǔ)結(jié)點(diǎn)，則刪除該結(jié)點(diǎn)所要執(zhí)行的兩條操作是 ①ptrPriorNext = ptrNext。2．線性表中數(shù)據(jù)元素的個(gè)數(shù)n稱為線性表的 長度 。}答：（1）的時(shí)間復(fù)雜度為O(1)；（2）的時(shí)間復(fù)雜度O(n)；（3）中“printf (“j=%”, j)。 j++) { printf (“j=%”, j)。 jn。 kn。 i++) for (j=0。 if (x=0) printf (“輸入的是正數(shù)”)。} 2．用類C語言中的ifelse語句，編寫算法，描述當(dāng)輸入的數(shù)據(jù)大于等于0時(shí)，輸出信息：“輸入的是正數(shù)”；當(dāng)輸入的數(shù)據(jù)小于0時(shí)，輸出信息：“輸入的是負(fù)數(shù)”。void num (){ i=1。答：因?yàn)?不能為除數(shù)，本題第（3）步不具有有效性，所以它不是一個(gè)算法。從這個(gè)意義上說，鏈?zhǔn)酱鎯?chǔ)降低了存儲(chǔ)器的利用率。在存儲(chǔ)結(jié)點(diǎn)里，不僅要存放數(shù)據(jù)結(jié)點(diǎn)的內(nèi)容，還要（顯式或隱式地）存放數(shù)據(jù)結(jié)點(diǎn)間的邏輯關(guān)系。 i++) k++。 A．只有線性關(guān)系 B．只有樹型關(guān)系 C．線性關(guān)系和樹型關(guān)系都不 D．線性關(guān)系和樹型關(guān)系都 4．鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中，每個(gè)數(shù)據(jù)的存儲(chǔ)結(jié)點(diǎn)里 D指向鄰接存儲(chǔ)結(jié)點(diǎn)的指針，用以反映數(shù)據(jù)間的邏輯關(guān)系。 12．“基本操作”是指算法中那種所需時(shí)間與操作數(shù)的具體取值 無關(guān) 的操作。8．如果兩個(gè)數(shù)據(jù)結(jié)點(diǎn)之間有著邏輯上的某種關(guān)系，那么就稱這兩個(gè)結(jié)點(diǎn)是 鄰接 的。4．?dāng)?shù)據(jù)是由一個(gè)個(gè) 數(shù)據(jù)元素 集合而成的。習(xí)題解答《數(shù)據(jù)結(jié)構(gòu)基礎(chǔ)教程》習(xí)題解答（新）第1章習(xí)題解答一、填空1．?dāng)?shù)據(jù)是指所有能夠輸入到計(jì)算機(jī)中被計(jì)算機(jī)加工、處理的 符號(hào) 的集合。5．?dāng)?shù)據(jù)項(xiàng)是數(shù)據(jù)元素中 不可再分割 的最小標(biāo)識(shí)單位，通常不具備完整、確定的實(shí)際意義，只是反映數(shù)據(jù)元素某一方面的屬性。9．在一個(gè)存儲(chǔ)結(jié)點(diǎn)里，除了要有數(shù)據(jù)本身的內(nèi)容外，還要有體現(xiàn) 數(shù)據(jù)間鄰接關(guān)系 的內(nèi)容。二、選擇1．在常見的數(shù)據(jù)處理中， B 是最基本的處理。 A．只能有1個(gè) B．只能有2個(gè) C．只能有3個(gè) D．可以有多個(gè)5．本書將采用 C 來描述算法。其時(shí)間復(fù)雜度為 B 。 3．為什么說鏈?zhǔn)酱鎯?chǔ)既提高了存儲(chǔ)的利用率，又降低了存儲(chǔ)的利用率？答：由于鏈?zhǔn)酱鎯?chǔ)是通過指針來體現(xiàn)數(shù)據(jù)元素之間的邏輯關(guān)系的，因此，存儲(chǔ)結(jié)點(diǎn)可以不占用存儲(chǔ)器的連續(xù)存儲(chǔ)區(qū)。 4．列舉幾個(gè)數(shù)據(jù)之間具有樹型結(jié)構(gòu)的實(shí)際例子。但如果n的初值不為0，則是一個(gè)正確的算法。 do { printf (“i = %d\n”, i )。答：算法編寫如下。 else printf (“輸入的是負(fù)數(shù)”)。 jn。 k++) 2 y=y+1。 j++) x++。 for (k=j?！眻?zhí)行次數(shù)的數(shù)量級(jí)為O(n)，“x++。 3．以順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)的線性表，被稱為 順序表 。 ②ptrNextPrior = ptrPrior。 8．在一個(gè)不帶表頭結(jié)點(diǎn)的非空單鏈表中，若要在指針qtr所指結(jié)點(diǎn)的后面插入一個(gè)值為x的結(jié)點(diǎn)，則需要執(zhí)行下列操作： ptr = malloc (size)。 9．順序表Sq = (a1，a2，a3，…，an)（n≥1）中，每個(gè)數(shù)據(jù)元素需要占用w個(gè)存儲(chǔ)單元。 A．所有結(jié)點(diǎn)有且只有一個(gè)直接前驅(qū) B．所有結(jié)點(diǎn)有且只有一個(gè)直接后繼 C．每個(gè)結(jié)點(diǎn)至多只有一個(gè)直接前驅(qū)，至多只有一個(gè)直接后繼 D．結(jié)點(diǎn)間是按照1對(duì)多的鄰接關(guān)系來維系其邏輯關(guān)系的 2．一般單鏈表Lk_h為空的判定條件是 A 。現(xiàn)要在qtr所指結(jié)點(diǎn)和ptr所指結(jié)點(diǎn)之間插入一個(gè)rtr所指的結(jié)點(diǎn)，要執(zhí)行的操作應(yīng)該是 C 。C．qtrNext = rtr。 6．在一個(gè)單鏈表中，若現(xiàn)在要?jiǎng)h除ptr指針?biāo)附Y(jié)點(diǎn)的直接后繼結(jié)點(diǎn)，則需要執(zhí)行的操作是 A 。C．ptr = ptrNextNext 。 A．ni B．ni+1 C．ni1 D．i 9．設(shè)tail是指向一個(gè)非空帶表頭結(jié)點(diǎn)的循環(huán)單鏈表的尾指針。 tail = tailNext 。 D．ptr = tailNextNext 。 free (ptr)。 ptrNext = qtr 。 ptr = qtr 。這個(gè)公式對(duì)嗎？為什么？ 答：這個(gè)公式是對(duì)的，因?yàn)榈趇個(gè)存儲(chǔ)結(jié)點(diǎn)ai的起始地址LOC（ai），實(shí)際上就是等于第i1個(gè)存儲(chǔ)結(jié)點(diǎn)ai1的起始地址LOC（ai1）加上一個(gè)存儲(chǔ)結(jié)點(diǎn)的長度k得到。5．在算法23里，操作“Sq_num=Sq_num 1”的作用是什么？沒有它行嗎？ 答：該操作是非常重要的，因?yàn)轫樞虮砝锂?dāng)前擁有的元素個(gè)數(shù)是通過Sq_num來記錄的，刪除了一個(gè)元素，Sq_num必須減1，這樣才能正確反映出刪除后表中元素的個(gè)數(shù)。因?yàn)樵瓉韕trNext里是“Λ”，做了第1步操作： qtrNext = ptrNext 。試問，編寫者能夠達(dá)到目的嗎？其思想是什么？ x = ptrData 。 free (qtr)。 8．在一個(gè)單鏈表中，為了在指針ptr所指結(jié)點(diǎn)之前插入一個(gè)由指針qtr所指的結(jié)點(diǎn)，有人編寫了下面的操作序列，其中temp是一個(gè)臨時(shí)工作單元。 temp = ptrData 。編寫者的思想是考慮到在單鏈表中得到一個(gè)結(jié)點(diǎn)的前驅(qū)信息較為困難，因此在這里先把qtr所指結(jié)點(diǎn)插入到ptr所指結(jié)點(diǎn)的后面，暫時(shí)成為它的直接后繼。 qtr = Cd_h 。}Cd_hPrior = qtr 。 ptr = Lk_h 。} 2．用總是在表的頭部插入整數(shù)結(jié)點(diǎn)的方法建立一個(gè)單鏈表，當(dāng)輸入為0時(shí)，建表過程結(jié)束。 while (x != “0”) { ptr = malloc (size)。 scanf (%d, amp。模仿圖221，對(duì)一般插入位置標(biāo)示出下面4個(gè)操作步驟：①rtrNext = ptr 。 答：4個(gè)操作步驟的具體功能體現(xiàn)如下圖所示。 qtr = Ck_h2 。 qtr = rtr 。試編寫一個(gè)算法，功能是從表中去除值大于min、且值小于max的數(shù)據(jù)元素。amp。amp。試編寫一個(gè)算法，功能是從表中去除所有值大于min、且值小于max的數(shù)據(jù)元素。 /* 往后移動(dòng)qtr和ptr */ ptr = ptrNext 。}}} 7．一個(gè)單鏈表Lk的表頭指針為Lk_h，不同結(jié)點(diǎn)的Data域值有可能相同。Count_Lk (Lk_h){ n = 0 。}第3章習(xí)題解答一、填空1．限定插入和刪除操作只能在一端進(jìn)行的線性表，被稱為是 棧 。 5．如果操作順序是先讓字母A、B、C進(jìn)棧，做兩次出棧；再讓字母D、E、F進(jìn)棧，做一次出棧；最后讓字母G進(jìn)棧，做三次出棧。 8．設(shè)某棧的元素輸入順序是5，想得到1的輸出順序。二、選擇1．一個(gè)棧的元素進(jìn)棧序列是a、b、c、d、e，那么下面的 C 不能做為一個(gè)出棧序列?，F(xiàn)在由指針ptr所指結(jié)點(diǎn)要進(jìn)隊(duì)，則插入操作應(yīng)該是 B 。 Lq_rear = ptr。 Lq_front = ptr。 A．先保存被刪結(jié)點(diǎn)的值，再修改棧頂指針 B．先修改棧頂指針，再保存被刪結(jié)點(diǎn)的值 C．無須修改棧頂指針的值 D．誰先誰后沒有關(guān)系 8．一個(gè)循環(huán)隊(duì)列的最大容量為m+1，front為隊(duì)首指針，rear為隊(duì)尾指針。（注：所給順序中，I表示進(jìn)棧操作，O表示出棧操作） A．IIIOOOIO B．IOIOIOIO C．IIOOIOIO D．IOIIIOOO三、問答 1．若元素進(jìn)棧的序列是…、n，有一個(gè)出棧序列的第1個(gè)元素是n。試問，在下面所列的6種元素序列里，哪些可以是這個(gè)棧的出棧序列？ A．c，e，a，b，d B．c，b，a，d，e C．d，c，a，b，eD．a(chǎn)，c，b，e，d E．a(chǎn)，b，c，d，e F．e，a，b，c，d 答：對(duì)A進(jìn)行分析。由于是d第1個(gè)出棧，因此a、b、c三者出棧的順序必須是c、b、a。但所給序列里，它們的出棧順序全亂了，故F不能是該棧的出棧序列。 ch = ‘A’+12 。 printf (“%c”, ch)。有人將其轉(zhuǎn)化為相應(yīng)的后綴表達(dá)式是abcde////。而對(duì)隊(duì)列來說，插入在一端進(jìn)行，刪除在另一端進(jìn)行，這就使得數(shù)據(jù)元素到達(dá)隊(duì)列（即往隊(duì)列里插入元素）的順序與數(shù)據(jù)元素離開隊(duì)列（即從隊(duì)列里刪除元素）的順序是完全一致的。初始時(shí)有Qs_front = Qs_rear = 0。在做（5）時(shí)，由于隊(duì)滿（假溢出），故操作停止。 j++) printf (“%3d”, x)。答：算法設(shè)計(jì)如下：Empty_Ss (Ss, Ss_top){ if (Ss_top == 0) /* 棧空 */ return (1) 。 else /* 隊(duì)列非空！*/ { qtr = Qs_front 。 答：取得鏈?zhǔn)疥?duì)列首元素的值，只有在隊(duì)列非空的前途下才有意義。 x = ptrData 。試給出該遞歸的公式、結(jié)束條件，并編寫出相應(yīng)的遞歸算法。}} 5．將中綴表達(dá)式轉(zhuǎn)化為后綴表達(dá)式的方法類似于中綴表達(dá)式求值。試用這種方法，用圖示將中綴表達(dá)式5+8*32轉(zhuǎn)化成為相應(yīng)的后綴表達(dá)式。該過程直至整個(gè)表達(dá)式結(jié)束。第4章習(xí)題解答一、填空1．字符串是一種特殊的線性表，特殊在于它的數(shù)據(jù)元素只能是 字符 ，特殊在于串可以作為一個(gè) 整體 參與所需要的處理。 5．設(shè)有串s=“I am a teacher”。 7．所謂“數(shù)組”，是指n（n1)個(gè)具有 相同 類型的數(shù)據(jù)的有序集合。二、選擇1．設(shè)有兩個(gè)串s1和s2。已知：算法con(x, y)返回串x和y的連接串；subs(s, i, j)返回串s的第i個(gè)字符開始往后j個(gè)字符組成的子串；len(s)返回串s的長度。試問元素a85的地址是 A 。那么按行順序存儲(chǔ)時(shí)元素M[4][6]的起始地址與M按列順序存儲(chǔ)時(shí)元素 B 的起始地址相同。 A．SA+141 B．SA+180 C．SA+222 D．SA+225 8．設(shè)有一個(gè)5階上三角矩陣A，將其元素按列優(yōu)先順序存放在一維數(shù)組B中。不過，如果我們把它看作是其每個(gè)元素為一維數(shù)組的一個(gè)一維數(shù)組，那么就可以把二維數(shù)組視為是線性表的一種推廣（因?yàn)橐痪S數(shù)組即是線性表），因此可以說它的數(shù)據(jù)元素間的邏輯關(guān)系呈現(xiàn)出的是一種線性結(jié)構(gòu)。試找出元素下標(biāo)i、j與存儲(chǔ)序號(hào)k間的對(duì)應(yīng)關(guān)系。 答：改寫的算法41可以是如下所示。 return(NULL)。while (j= St2_len){ St3[j+St1_len]=St2[j]。return(St3)。Equal_St(St1, St2){ i=1。 else { if (St1[i] != “\0” || St2[i] != “\0”) /* 比較是由于長度不同而結(jié)束 */ return (0)。 答：用for 循環(huán)改寫的算法如下。} 4．編寫一個(gè)算法，將順序串St中所有的大寫字母全部換成小寫字母。 i++) if ((A=St[i])amp。（提示：