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