word 單元練習(xí)1 一．判斷題〔如下各題，正確的請在前面的括號打√；錯誤的打╳〕 〔√〕〔1〕數(shù)據(jù)的邏輯結(jié)構(gòu)與數(shù)據(jù)元素本身的容和形式無關(guān)。 〔√〕〔2〕一個數(shù)據(jù)結(jié)構(gòu)是由一個邏輯結(jié)構(gòu)和這個邏輯結(jié)構(gòu)上的一個根本運(yùn)算集構(gòu)成的整體。 〔ㄨ〕〔3〕數(shù)據(jù)元素是數(shù)據(jù)的最小單位。 〔ㄨ〕〔4〕數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)是一樣的。 〔ㄨ〕〔5〕程序和算法原如此上沒有區(qū)別，所以在討論數(shù)據(jù)結(jié)構(gòu)時可以通用。 〔√〕〔6〕從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。 〔√〕〔7〕數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲映像。 〔√〕〔8〕數(shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計算機(jī)實(shí)際的存儲形式。 〔ㄨ〕〔9〕數(shù)據(jù)的邏輯結(jié)構(gòu)是依賴于計算機(jī)的。 〔√〕〔10〕算法是對解題方法和步驟的描述。 二．填空題 （1） 數(shù)據(jù)有邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩種結(jié)構(gòu)。 （2） 數(shù)據(jù)邏輯結(jié)構(gòu)除了集合以外，還包括：線性結(jié)構(gòu)、樹形結(jié)構(gòu)和圖形結(jié)構(gòu)。 （3） 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們是線性結(jié)構(gòu)和非線性結(jié)構(gòu)。 （4） 樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為非線性結(jié)構(gòu)。 （5） 在樹形結(jié)構(gòu)中，除了樹根結(jié)點(diǎn)以外，其余每個結(jié)點(diǎn)只有1個前趨結(jié)點(diǎn)。 （6） 在圖形結(jié)構(gòu)中，每個結(jié)點(diǎn)的前趨結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以任意多個。 （7） 數(shù)據(jù)的存儲結(jié)構(gòu)又叫物理結(jié)構(gòu)。 （8） 數(shù)據(jù)的存儲結(jié)構(gòu)形式包括：順序存儲、鏈?zhǔn)酱鎯?、索引存儲和散列存儲? （9） 線性結(jié)構(gòu)中的元素之間存在一對一的關(guān)系。 （10） 樹形結(jié)構(gòu)結(jié)構(gòu)中的元素之間存在一對多的關(guān)系， （11） 圖形結(jié)構(gòu)的元素之間存在多對多的關(guān)系。 （12） 數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和算法〔或運(yùn)算〕三個方面的容。 （13） 數(shù)據(jù)結(jié)構(gòu)被定義為(D，R)，其中D是數(shù)據(jù)的有限集合，R是D上的關(guān)系的有限集合。 （14） 算法是一個有窮指令的集合。 （15） 算法效率的度量可以分為事先估算法和事后統(tǒng)計法。 （16） 一個算法的時間復(fù)雜性是算法輸入規(guī)模的函數(shù)。 （17） 算法的空間復(fù)雜度是指該算法所消耗的存儲空間，它是該算法求解問題規(guī)模n的函數(shù)。 （18） 假如一個算法中的語句頻度之和為T〔n〕=6n+3nlog2n，如此算法的時間復(fù)雜度為 O〔nlog2n〕。 （19） 假如一個算法中的語句頻度之和為T〔n〕=3n+nlog2n+n2，如此算法的時間復(fù)雜度為 O〔n2〕。 〔20〕數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計算的程序設(shè)計問題中計算機(jī)的操作對象，以與它們之間的關(guān)系和運(yùn)算的學(xué)科。 三．選擇題 〔1〕數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的〔 A 〕與它們之間的相互聯(lián)系。 A. 存儲結(jié)構(gòu)和邏輯結(jié)構(gòu) B. 存儲和抽象 C. 聯(lián)系和抽象 D. 聯(lián)系與邏輯 〔2〕在邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成：〔 C 〕。 A. 動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B. 緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu) C. 線性結(jié)構(gòu)和非線性結(jié)構(gòu) D. 部結(jié)構(gòu)和外部結(jié)構(gòu) 〔3〕數(shù)據(jù)在計算機(jī)存儲器表示時，物理地址和邏輯地址一樣并且是連續(xù)的，稱之為〔 C 〕。 A. 存儲結(jié)構(gòu) B. 邏輯結(jié)構(gòu) C. 順序存儲結(jié)構(gòu) D. 鏈?zhǔn)酱鎯Y(jié)構(gòu) 〔4〕非線性結(jié)構(gòu)中的每個結(jié)點(diǎn)〔 D 〕。 A. 無直接前趨結(jié)點(diǎn) B. 無直接后繼結(jié)點(diǎn) C. 只有一個直接前趨結(jié)點(diǎn)和一個直接后繼結(jié)點(diǎn) D. 可能有多個直接前趨結(jié)點(diǎn)和多個直接后繼結(jié)點(diǎn) 〔5〕鏈?zhǔn)酱鎯Φ拇鎯Y(jié)構(gòu)所占存儲空間〔 A 〕。 A．分兩局部，一局部存放結(jié)點(diǎn)的值，另一局部存放表示結(jié)點(diǎn)間關(guān)系的指針 B．只有一局部，存放結(jié)點(diǎn)的值 C．只有一局部，存儲表示結(jié)點(diǎn)間關(guān)系的指針 D．分兩局部，一局部存放結(jié)點(diǎn)的值，另一局部存放結(jié)點(diǎn)所占單元素 〔6〕算法的計算量大小稱為算法的〔 C 〕。 A. 現(xiàn)實(shí)性 B. 難度 C. 時間復(fù)雜性 D. 效率 〔7〕數(shù)據(jù)的根本單位是〔 B 〕。 A. 數(shù)據(jù)結(jié)構(gòu) B. 數(shù)據(jù)元素 C. 數(shù)據(jù)項 D. 文件 〔8〕每個結(jié)點(diǎn)只含有一個數(shù)據(jù)元素，所有存儲結(jié)點(diǎn)相繼存放在一個連續(xù)的存儲區(qū)里，這種存儲結(jié)構(gòu)稱為〔 A 〕結(jié)構(gòu)。 A. 順序存儲 B. 鏈?zhǔn)酱鎯? C. 索引存儲 D. 散列存儲 〔9〕每一個存儲結(jié)點(diǎn)不僅含有一個數(shù)據(jù)元素，還包含一組指針，該存儲方式是〔 B 〕存儲方式。 A. 順序 B. 鏈?zhǔn)? C. 索引 D. 散列 〔10〕以下任何兩個結(jié)點(diǎn)之間都沒有邏輯關(guān)系的是〔 D 〕。 A. 圖形結(jié)構(gòu) B. 線性結(jié)構(gòu) C. 樹形結(jié)構(gòu) D. 集合 〔11〕在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是〔 C 〕。 A. 物理結(jié)構(gòu) B. 存儲結(jié)構(gòu) C. 邏輯結(jié)構(gòu) D. 邏輯和存儲結(jié)構(gòu) 〔12〕如下四種根本邏輯結(jié)構(gòu)中，數(shù)據(jù)元素之間關(guān)系最弱的是〔 A 〕。 A. 集合 B. 線性結(jié)構(gòu) C. 樹形結(jié)構(gòu) D. 圖形結(jié)構(gòu) 〔13〕與數(shù)據(jù)元素本身的形式、容、相對位置、個數(shù)無關(guān)的是數(shù)據(jù)的〔 A 〕。 A. 邏輯結(jié)構(gòu) B. 存儲結(jié)構(gòu) C. 邏輯實(shí)現(xiàn) D. 存儲實(shí)現(xiàn) 〔14〕每一個存儲結(jié)點(diǎn)只含有一個數(shù)據(jù)元素，存儲結(jié)點(diǎn)存放在連續(xù)的存儲空間，另外有一組指明結(jié)點(diǎn)存儲位置的表，該存儲方式是〔 C 〕存儲方式。 A. 順序 B. 鏈?zhǔn)? C. 索引 D. 散列 〔15〕算法能正確的實(shí)現(xiàn)預(yù)定功能的特性稱為算法的〔 A 〕。 A. 正確性 B. 易讀性 C. 健壯性 D. 高效性 〔16〕算法在發(fā)生非法操作時可以作出處理的特性稱為算法的〔 C 〕。 A. 正確性 B. 易讀性 C. 健壯性 D. 高效性 〔17〕如下時間復(fù)雜度中最壞的是〔 D 〕。 A. O〔1〕 B. O〔 n〕 C. O〔log2n〕 D. O〔n2〕 〔18〕如下算法的時間復(fù)雜度是〔 D 〕。 for (i=0;i<n;i++) for (j=0;i<n;j++) c[i][j]=i+j; A. O〔1〕 B. O〔 n〕 C. O〔log2n〕 D. O〔n2〕 〔19〕算法分析的兩個主要方面是〔 A 〕。 A. 空間復(fù)雜性和時間復(fù)雜性 B. 正確性和簡明性 C. 可讀性和文檔性 D. 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性 〔20〕計算機(jī)算法必須具備輸入、輸出和〔 C 〕。 A. 計算方法 B. 排序方法 C. 解決問題的有限運(yùn)算步驟 D. 程序設(shè)計方法 四．分析下面各程序段的時間復(fù)雜度 （1） for (i=0;i<n;i++) for (j=0;j<m;j++) A[i][j] 解： O(n*m) 〔2〕 s=0; for (i=0;i<n;i++) for (j=0;j<n;j++) s+=B[i][j]; sum=s; 解： O(n2) 〔3〕 T=A； A=B； B=T； 解：O(1) 〔4〕 s1(int n) { int p=1,s=0; for (i=1;i<=n;i++) { p*=i;s+=p; } return(s); } O(n) 〔5〕 s2(int n) x=0; y=0; for (k=1;k<=n;k++) x++; for (i=1;i<=n;i++) for (j=1;j<=n;j++) y++; 解：O(n2) 五．根據(jù)二元組關(guān)系，畫出對應(yīng)邏輯圖形的草圖，指出它們屬于何種數(shù)據(jù)結(jié)構(gòu)。 〔1〕A=〔D，R〕，其中： D={a，b，c，d，e}， R={ } 解： a b c d e 屬于集合 〔2〕B=〔D,R〕，其中： D={a,b,c,d,e,f}，R={r} R={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>} 〔尖括號表示結(jié)點(diǎn)之間關(guān)系是有向的〕 解： 屬于線性結(jié)構(gòu)。 〔3〕F=〔D,R〕，其中： D={50,25,64,57,82,36,75,55}，R={r} R={<50,25>,<50,64>,<25,36>,<64,57>,<64,82>,<57,55>,<57,75>} 解： 屬于樹結(jié)構(gòu) 〔4〕C=〔D,R〕，其中： D={1,2,3,4,5,6}，R={r} R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}〔園括號表示結(jié)點(diǎn)之間關(guān)系是有向的〕 解： 屬于圖結(jié)構(gòu) 〔5〕E=〔D,R〕，其中： D={a,b,c,d,e,f,g,h}，R={r} R={<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,<g,h>,<e,f>} 解： c 屬于樹結(jié)構(gòu)。單元練習(xí)2 一．判斷題〔如下各題，正確的請在前面的括號打√；錯誤的打╳〕 〔×〕〔1〕線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)優(yōu)于順序存儲。 〔×〕〔2〕鏈表的每個結(jié)點(diǎn)都恰好包含一個指針域。 〔√〕〔3〕在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。 〔×〕〔4〕順序存儲方式的優(yōu)點(diǎn)是存儲密度大，插入、刪除效率高。 〔×〕〔5〕線性鏈表的刪除算法簡單，因為當(dāng)刪除鏈中某個結(jié)點(diǎn)后，計算機(jī)會自動地將后續(xù)的各個單元向前移動。 〔×〕〔6〕順序表的每個結(jié)點(diǎn)只能是一個簡單類型，而鏈表的每個結(jié)點(diǎn)可以是一個復(fù)雜類型。 〔√〕〔7〕線性表鏈?zhǔn)酱鎯Φ奶攸c(diǎn)是可以用一組任意的存儲單元存儲表中的數(shù)據(jù)元素。 〔√〕〔8〕線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。 〔×〕〔9〕順序表結(jié)構(gòu)適宜于進(jìn)展順序存取，而鏈表適宜于進(jìn)展隨機(jī)存取。 〔ㄨ〕〔10〕插入和刪除操作是數(shù)據(jù)結(jié)構(gòu)中最根本的兩種操作，所以這兩種操作在數(shù)組中也經(jīng)常使用。 二．填空題 （1） 順序表中邏輯上相鄰的元素在物理位置上必須相連。 （2） 線性表中結(jié)點(diǎn)的集合是有限的，結(jié)點(diǎn)間的關(guān)系是一對一關(guān)系。 （3） 順序表相對于鏈表的優(yōu)點(diǎn)是：節(jié)省存儲和隨機(jī)存取。 （4） 鏈表相對于順序表的優(yōu)點(diǎn)是：插入、刪除方便。 〔5〕采用順序存儲結(jié)構(gòu)的線性表叫順序表。 〔6〕順序表中訪問任意一個結(jié)點(diǎn)的時間復(fù)雜度均為 O(1) 。 〔7〕鏈表相對于順序表的優(yōu)點(diǎn)是插入、刪除方便；缺點(diǎn)是存儲密度小。 〔8〕在雙鏈表中要刪除結(jié)點(diǎn)*P，其時間復(fù)雜度為 O(1) 。 〔9〕在單鏈表中要在結(jié)點(diǎn)*P之前插入一個新結(jié)點(diǎn)，需找到*P的直接前趨結(jié)點(diǎn)的地址，其查找的時間復(fù)雜度為 O(n) 。 （10） 單鏈表中需知道頭指針才能遍歷整個鏈表。 （11） 性表中第一個結(jié)點(diǎn)沒有直接前趨，稱為開始結(jié)點(diǎn)。 （12） 在一個長度為n的順序表中刪除第i個元素，要移動 n-i 個元素。 （13） 在一個長度為n的順序表中，如果要在第i個元素前插入一個元素，要后移 n- i +1 個元素。 （14） 在無頭結(jié)點(diǎn)的單鏈表中，第一個結(jié)點(diǎn)的地址存放在頭指針中，而其它結(jié)點(diǎn)的存儲地址存放在前趨結(jié)點(diǎn)的指針域中。 （15） 當(dāng)線性表的元素總數(shù)根本穩(wěn)定，且很少進(jìn)展插入和刪除操作，但要求以最快速度存取線性表中的元素時，應(yīng)采用順序存儲結(jié)構(gòu)。 （16） 在線性表的鏈?zhǔn)酱鎯χ?，元素之間的邏輯關(guān)系是通過指針決定的。 （17） 在雙向鏈表中，每個結(jié)點(diǎn)都有兩個指針域，它們一個指向其前趨結(jié)點(diǎn)，另一個指向其后繼結(jié)點(diǎn)。 （18） 對一個需要經(jīng)常進(jìn)展插入和刪除操作的線性表，采用鏈?zhǔn)酱鎯Y(jié)構(gòu)為宜。 （19） 雙鏈表中，設(shè)p是指向其中待刪除的結(jié)點(diǎn)，如此需要執(zhí)行的操作為： p->prior->next=p->next 。 （20） 在如下列圖的鏈表中，假如在指針P所在的結(jié)點(diǎn)之后插入數(shù)據(jù)域值為a和b的兩個結(jié)點(diǎn)，如此可用如下兩個語句： S->next->next=P->next;和P->next=S;來實(shí)現(xiàn)該操作。 P Λ a b S 三．選擇題 〔1〕在具有n個結(jié)點(diǎn)的單鏈表中，實(shí)現(xiàn)〔 A 〕的操作，其算法的時間復(fù)雜度都是O〔n〕。 A．遍歷鏈表或求鏈表的第i個結(jié)點(diǎn) B．在地址為P的結(jié)點(diǎn)之后插入一個結(jié)點(diǎn) C．刪除開始結(jié)點(diǎn) D．刪除地址為P的結(jié)點(diǎn)的后繼結(jié)點(diǎn) 〔2〕設(shè)a、b、c為三個結(jié)點(diǎn)，p、10、20分別代表它們的地址，如此如下的存儲結(jié)構(gòu)稱為〔 B 〕。 A． 循環(huán)鏈表 B．單鏈表 C．雙向循環(huán)鏈表 D．雙向鏈表 〔3〕單鏈表的存儲密度〔 C 〕。 A．大于1 B．等于1 C．小于1 D．不能確定 〔4〕一個順序存儲的線性表，設(shè)每個結(jié)點(diǎn)占m個存儲單元，假如第一個結(jié)點(diǎn)的地址為B，如此第i個結(jié)點(diǎn)的地址為〔 A 〕。 A． B+(i-1)*m B．B+i*m C． B-i*m D． B+(i+1)*m 〔5〕在有n個結(jié)點(diǎn)的順序表上做插入、刪除結(jié)點(diǎn)運(yùn)算的時間復(fù)雜度為〔 B 〕。 A．O〔1〕 B．O〔n〕C．O〔n2〕 D．O〔log2n〕 〔6〕設(shè)Llink、Rlink分別為循環(huán)雙鏈表結(jié)點(diǎn)的左指針和右指針，如此指針P所指的元素是雙循環(huán)鏈表L的尾元素的條件是〔 D 〕。 A．P== L B．P->Llink== L C．P== NULL D．P->Rlink==L 〔7〕兩個指針P和Q，分別指向單鏈表的兩個元素，P所指元素是Q所指元素前驅(qū)的條件是〔 B 〕。 A．P->next==Q->next B．P->next== Q C．Q->next== P D．P== Q 〔8〕用鏈表存儲的線性表，其優(yōu)點(diǎn)是〔 C 〕。 A．便于隨機(jī)存取B．花費(fèi)的存儲空間比順序表少 C．便于插入和刪除 D．?dāng)?shù)據(jù)元素的物理順序與邏輯順序一樣 〔9〕在單鏈表中，增加頭結(jié)點(diǎn)的目的是〔 C 〕。 A．使單鏈表至少有一個結(jié)點(diǎn)B．標(biāo)志表中首結(jié)點(diǎn)的位置 C．方便運(yùn)算的實(shí)現(xiàn) D．說明該單鏈表是線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu) 〔10〕下面關(guān)于線性表的表示中，錯誤的答案是〔 D 〕關(guān)系。 A．順序表必須占一片地址連續(xù)的存儲單元 B．順序表可以隨機(jī)存取任一元素 C．鏈表不必占用一片地址連續(xù)的存儲單元 D．鏈表可以隨機(jī)存取任一元素 〔11〕L是線性表，LengthList〔L〕的值是5，經(jīng)DelList〔L，2〕運(yùn)算后，LengthList〔L〕的值是〔 C 〕。 A．2 B．3 C．4 D．5 〔12〕單鏈表的示意圖如下： L A B C D Λ Q R P 指向鏈表Q結(jié)點(diǎn)的前趨的指針是〔 B 〕。 A．L B．P C．Q D．R 〔13〕設(shè)p為指向單循環(huán)鏈表上某結(jié)點(diǎn)的指針，如此*p的直接前驅(qū)〔 C 〕。 A．找不到 B．查找時間復(fù)雜度為O〔1〕 C．查找時間復(fù)雜度為O〔n〕 D．查找結(jié)點(diǎn)的次數(shù)約為n 〔14〕等概率情況下，在有n個結(jié)點(diǎn)的順序表上做插入結(jié)點(diǎn)運(yùn)算，需平均移動結(jié)點(diǎn)的數(shù)目為〔 C 〕。 A．n B．(n-1)/2 C． n/2 D．(n+1)/2 〔15〕在如下鏈表中不能從當(dāng)前結(jié)點(diǎn)出發(fā)訪問到其余各結(jié)點(diǎn)的是〔 C 〕。 A．雙向鏈表 B．單循環(huán)鏈表 C．單鏈表 D．雙向循環(huán)鏈表 〔16〕在順序表中，只要知道〔 D 〕，就可以求出任一結(jié)點(diǎn)的存儲地址。 A．基地址 B．結(jié)點(diǎn)大小 C．向量大小 D．基地址和結(jié)點(diǎn)大小 〔17〕在雙鏈表中做插入運(yùn)算的時間復(fù)雜度為〔 A 〕。 A．O〔1〕 B．O〔n〕 C．O〔n2〕 D．O〔log2n〕 〔18〕鏈表不具備的特點(diǎn)是〔 A 〕。 A．隨機(jī)訪問 B．不必事先估計存儲空間 C．插入刪除時不需移動元素 D．所需空間與線性表成正比 〔19〕以下關(guān)于線性表的論述，不正確的為〔 C 〕。 A．線性表中的元素可以是數(shù)字、字符、記錄等不同類型 B．線性順序表中包含的元素個數(shù)不是任意的 C．線性表中的每個結(jié)點(diǎn)都有且僅有一個直接前趨和一個直接后繼 D．存在這樣的線性表，即表中沒有任何結(jié)點(diǎn) 〔20〕在〔 B 〕的運(yùn)算中，使用順序表比鏈表好。 A．插入 B．根據(jù)序號查找 C．刪除 D．根據(jù)元素查找 ListNode *Demo1(LinkList L,ListNode *p) { // L是有頭結(jié)點(diǎn)的單鏈表 ListNode *q=L->next; While (q && q->next!=p) q=q->next; if (q) return q; else Error(“*p not in L〞); } 四．分析下述算法的功能 〔1〕 void Demo2(ListNode *p,ListNode *q) { // p,*q是鏈表中的兩個結(jié)點(diǎn) DataType temp; temp=p->data; p->data=q->data; q->data=temp; } 〔2〕 解： 〔1〕返回結(jié)點(diǎn)*p的直接前趨結(jié)點(diǎn)地址。 〔2〕交換結(jié)點(diǎn)*p和結(jié)點(diǎn)*q〔p和q的值不變〕。 五．程序填空 〔1〕線性表中的元素是無序的，并以帶表頭結(jié)點(diǎn)的單鏈表作存儲。試寫一算法，刪除表中所有大于min，小于max的元素，試完成如下程序填空。 Void delete (lklist head; datatype min, max) { q=head->next; while (p!=NULL) { if ((p->data<=min ) | | ( p->data>=max ) {q=p; p= p->next ; } else { q->next= p->next ; delete (p) ; p= q->next ; } } } 〔2〕在帶頭結(jié)點(diǎn)head的單鏈表的結(jié)點(diǎn)a之后插入新元素x，試完成如下程序填空。 struct node { elemtype data; node *next; }; void lkinsert (node *head, elemtype x) { node *s, *p; s= new node ; s->data= x ; p=head->next; while (p!=NULL) && ( p->data!=a ) ____p=p->next ; if (p==NULL) cout<< " 不存在結(jié)點(diǎn)a! "; else {_____s->next=p->next______; ___ p->next=s __________; } } 六．算法設(shè)計題 〔1〕寫一個對單循環(huán)鏈表進(jìn)展遍歷〔打印每個結(jié)點(diǎn)的值〕的算法，鏈表中任意結(jié)點(diǎn)的地址為P 。 解： void Show(ListNode *P) { ListNode *t=P; do { printf("%c",t->data); t=t->rear; } while (t!=P); } （2） 對給定的帶頭結(jié)點(diǎn)的單鏈表L，編寫一個刪除L中值為x的結(jié)點(diǎn)的直接前趨結(jié)點(diǎn)的算法。 解： void delete(ListNode *L) { ListNode *p=L,*q; if(L->next->data==X) { printf(“值為x的結(jié)點(diǎn)是第一個結(jié)點(diǎn)，沒有直接前趨結(jié)點(diǎn)可以刪除〞); return; } For(p->next->data!=X;q=p;p=p->next);// 刪除指針p所指向的結(jié)點(diǎn) q->next=p->next; delete p; } （3） 一個單向鏈表，編寫一個函數(shù)從單鏈表中刪除自第i個結(jié)點(diǎn)起的k個結(jié)點(diǎn)。 解： void Del(node *head,int i,int k) { node *p,*q; int j; if(i==1) for(j=1;j<=k;j++) // 刪除前k個元素 { p=head; // p指向要刪除的結(jié)點(diǎn) head=head->next; delete p; } else { p=head; for(j=1;j<=i-2;j++) p=p->next; // p指向要刪除的結(jié)點(diǎn)的前一個結(jié)點(diǎn) for(j=1;j<=k;j++) { q=p->next; // q 指向要刪除的結(jié)點(diǎn) p->next=q->next; delete q; } } } （4） 有一個單向鏈表〔不同結(jié)點(diǎn)的數(shù)據(jù)域值可能一樣〕，其頭指針為head，編寫一個函數(shù)計算值域為x的結(jié)點(diǎn)個數(shù)。 解：//此題是遍歷單鏈表的每個結(jié)點(diǎn)，每遇到一個結(jié)點(diǎn)，結(jié)點(diǎn)個數(shù)加1，結(jié)點(diǎn)個數(shù)存儲在變量n中。實(shí)現(xiàn)此題功能的函數(shù)如下： int counter(head) node *head； { node *p; int n=0; p=head； while(p!=NULL) { if(p->data==x) n++； p=p->next; } return(n); } 〔5〕有兩個循環(huán)單向鏈表，鏈頭指針分別為head1和head2，編寫一個函數(shù)將鏈表head1到鏈表head2，后的鏈表仍是循環(huán)鏈表。 解：//此題的算法思想是：先找到兩鏈表的尾指針，將第一個鏈表的尾指針與第二個鏈表的頭結(jié)點(diǎn)起來，使之成為循環(huán)的。函數(shù)如下： node *link (node *head1, *head2) { node *p,*q; p=head1; while(p->next!=head1) p=p->next; q=head2; while(q->next!=head2) q=q->next; p->next=head2; q->next=head1; return (head1); } 單元練習(xí)3 一．判斷題〔如下各題，正確的請在前面的括號打√；錯誤的打╳〕 〔√〕〔1〕棧是運(yùn)算受限制的線性表。 〔√〕〔2〕在?？盏那闆r下，不能作出棧操作，否如此產(chǎn)生下溢出。 〔ㄨ〕〔3〕棧一定是順序存儲的線性結(jié)構(gòu)。 〔√〕〔4〕棧的特點(diǎn)是“后進(jìn)先出〞。 〔ㄨ〕〔5〕空棧就是所有元素都為0的棧。 〔ㄨ〕〔6〕在C或C++語言中設(shè)順序棧的長度為MAXLEN，如此top=MAXLEN時表示隊滿。 〔√〕〔7〕鏈棧與順序棧相比，其特點(diǎn)之一是通常不會出現(xiàn)棧滿的情況。 〔ㄨ〕〔8〕一個棧的輸入序列為：A，B，C，D，可以得到輸出序列：C，A，B，D。 〔ㄨ〕〔9〕遞歸定義就是循環(huán)定義。 〔√〕〔10〕將十進(jìn)制數(shù)轉(zhuǎn)換為二進(jìn)制數(shù)是棧的典型應(yīng)用之一。 二．填空題 〔1〕在棧結(jié)構(gòu)中，允許插入、刪除的一端稱為棧頂。 〔2〕在順序棧中，當(dāng)棧頂指針top=-1時，表示?？?。 〔3〕在有n個元素的棧中，進(jìn)棧操作的時間復(fù)雜度為 O〔1〕。 〔4〕在棧中，出棧操作的時間復(fù)雜度為： O(1) 。 〔5〕表達(dá)式，求它的后綴表達(dá)式是棧的典型應(yīng)用。 〔6〕在一個鏈棧中，假如棧頂指針等于NULL，如此表示棧空。 〔7〕向一個棧頂指針為top的鏈棧插入一個新結(jié)點(diǎn)*p時，應(yīng)執(zhí)行 p->next=top；和top=p；操作。 〔8〕順序棧S存儲在數(shù)組 S->data[0..MAXLEN-1]中，進(jìn)棧操作時要執(zhí)行的語句有： S->top ++ 。〔或= S->top+1〕 〔9〕鏈棧LS，指向棧頂元素的指針是 LS->next 。 〔10〕從一個棧刪除元素時，首先取出棧頂元素，然后再移動棧頂指針。 〔11〕由于鏈棧的操作只在鏈表的頭部進(jìn)展，所以沒有必要設(shè)置頭結(jié)點(diǎn)。 〔12〕順序棧S，在對S進(jìn)展進(jìn)棧操作之前首先要判斷棧是否滿。 〔13〕順序棧S，在對S進(jìn)展出棧操作之前首先要判斷棧是否空。 〔14〕假如存空間充足，鏈?？梢圆欢x棧滿運(yùn)算。 〔15〕鏈棧LS是空的條件是 LS->next=NULL 。 〔16〕鏈棧LS的棧頂元素是鏈表的首元素。 〔17〕同一棧的各元素的類型一樣。 〔18〕假如進(jìn)棧的次序是A、B、C、D、E，執(zhí)行三次出棧操作以后，棧頂元素為 B 。 〔19〕A+B/C-D*E的后綴表達(dá)式是： ABC/+DE*- 。 〔20〕四個元素按A、B、C、D順序進(jìn)S棧，執(zhí)行兩次Pop〔S，x〕運(yùn)算后，x的值是 C 。 三．選擇題 〔1〕插入和刪除只能在一端進(jìn)展的線性表，稱為( C )。 A．隊列 B．循環(huán)隊列 C．棧 D．循環(huán)棧 〔2〕設(shè)有編號為1，2，3，4的四輛列車，順序進(jìn)入一個棧結(jié)構(gòu)的站臺，如下不可能的出站順序為 ( D ) A．1234 B．1243 C．1324 D．1423 〔3〕如果以鏈表作為棧的存儲結(jié)構(gòu)，如此出棧操作時〔 B 〕 A．必須判別棧是否滿 B．必須判別棧是否空 C．必須判別棧元素類型 D．隊棧可不做任何判別 〔4〕元素A,B,C,D依次進(jìn)棧以后，棧頂元素是〔 D 〕 A．A B．B C．C D．D 〔5〕順序棧存儲空間的實(shí)現(xiàn)使用〔 B 〕存儲棧元素。 A．鏈表 B．?dāng)?shù)組 C．循環(huán)鏈表 D．變量 〔6〕在C或C++語言中，一個順序棧一旦被聲明，其占用空間的大小〔 A 〕。 A．已固定 B．不固定 C．可以改變 D．動態(tài)變化 〔7〕帶頭結(jié)點(diǎn)的鏈棧LS的示意圖如下，棧頂元素是〔 A 〕 LS H A B C D Λ A．A B．B C．C D．D 〔8〕鏈棧與順序棧相比，有一個比擬明顯的優(yōu)點(diǎn)是〔 B 〕。 A．插入操作更加方便 B．通常不會出現(xiàn)棧滿的情況。 C．不會出現(xiàn)?？盏那闆r D．刪除操作根加方便 〔9〕從一個棧頂指針為top的鏈棧中刪除一個結(jié)點(diǎn)時，用x保存被刪除的結(jié)點(diǎn)，應(yīng)執(zhí)行如下 ( D )命令。 A．x=top;top=top->next; B．top=top->next;x=top->data; C．x=top->data; D．x=top->data;top=top->next; 〔10〕在一個棧頂指針為HS的鏈棧中，將一個S指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)執(zhí)行如下 ( B )命令。 A．HS->next=S; B．S->next=HS->next;HS->next=S; C．S->next=HS->next;HS=S; D．S->next=HS;HS=HS->next; 〔11〕四個元素按A、B、C、D順序進(jìn)S棧，執(zhí)行兩次Pop〔S，x〕運(yùn)算后，棧頂元素的值是〔 B 〕。 A．A B．B C．C D．D 〔12〕元素A,B,C,D依次進(jìn)棧以后，棧底元素是〔 A 〕。 A．A B．B C．C D．D 〔13〕經(jīng)過如下棧的運(yùn)算后，再執(zhí)行ReadTop(s)的值是〔 A 〕。 InitStack(s)〔初始化?！?Push(s,a);Push(s,b); Pop(s) A．a(chǎn) B．b C．1 D．0 〔14〕經(jīng)過如下棧的運(yùn)算后，x的值是〔 B 〕。 InitStack(s)〔初始化棧〕;Push(s,a);Push(s,b); ReadTop(s);Pop(s,x); A．a(chǎn) B．b C．1 D．0 〔15〕經(jīng)過如下棧的運(yùn)算后，x的值是〔 B 〕。 InitStack(s)〔初始化棧〕;Push(s,a);Pop(s,x);Push(s,b);Pop(s,x); A．a(chǎn) B．b C．1 D．0 〔16〕經(jīng)過如下棧的運(yùn)算后，SEmpty(s)的值是〔 C 〕。 InitStack(s)〔初始化?！? Push(s,a); Push(s,b);Pop(s,x); Pop(s,x); A．a(chǎn) B．b C．1 D．0 〔17〕向順序棧中壓入元素時，〔 B 〕。 A． 先存入元素，后移動棧頂指針 B．先移動棧頂指針，后存入元素 C．誰先誰后無關(guān)緊要 D．同時進(jìn)展 〔18〕初始化一個空間大小為5的順序棧S后，S->top的值是〔 B 〕。 A．0 B．-1 C．不再改變 D．動態(tài)變化 〔19〕一個棧的入棧次序ABCDE，如此棧的不可能的輸出序列是 ( C )。 A．EDCBA B．DECBA C．DCEAB D．ABCDE 〔20〕設(shè)有一個順序棧S，元素A,B,C,D,E,F,依次進(jìn)棧，如果六個元素出棧的順序是B，D，C，F(xiàn)，E，A，如此棧的容量至少應(yīng)是 ( A )。 A．3 B．4 C．5 D． 6 四．應(yīng)用題 〔1〕設(shè)有一個棧，元素進(jìn)棧的次序為：A，B，C，D，E，用I表示進(jìn)棧操作，O表示出棧操作，寫出如下出棧的操作序列。 ①C，B，A，D，E ②A，C，B，E，D 解：①IIIOOOIOIO ②IOIIOOIIOO （2） 求后綴表達(dá)式 ① A^B^C/D 解：A B ^ C ^ D / ② -A+B*C+D/E 解：0 A – B C * + D E / + ③ A*(B+C)*D-E 解：A B C + * D * E - ④ (A+B)*C-E/(F+G/H)-D 解：A B + C * E F G H / + / - D - ⑤ 8/(5+2)-6 解：8 5 2 + / 6 - 六．算法設(shè)計題 〔1〕設(shè)用一維數(shù)組stack[n]表示一個堆棧，假如堆棧中每個元素需占用M個數(shù)組單元〔M>1〕。 ①試寫出其入棧操作的算法。 ②試寫出其出棧操作的算法。 解：//用一整型變量top表示棧頂指針，top為0時表示棧為空。棧中元素從S [1]開始存放元素。 //①入棧算法： void push (char x) { if ((top+M)>MAXLEN-1) printf (“堆棧溢出！〞); else { if (top= =0) { top++; S [top]=x; } else { top=top+M; S [top]=x; } } } //②出棧算法： void pop (char x) { if (top= =0) printf (“堆棧為空棧！〞); else { if (top= =1) { x= S [top]; top––; } else { x= S [top]; top=top–M; } } } 〔2〕設(shè)計一個算法，要求判別一個算術(shù)表達(dá)式中的圓括號配對是否正確。 解：//設(shè)表達(dá)式在字符數(shù)組a[ ]中，使用一堆棧S來幫助判斷。 int correct (char a[ ]) { stack s ; InitStack (s); //調(diào)用初始化棧函數(shù) for (i=0; i <strlen(a);i++) if (a[i]= =’(’) Push (s,’(’); else if (a[i]= =’)’) { if StackEmpty (s) //調(diào)用判?？蘸瘮?shù) return 0; //假如棧為空返回0；否如此出棧 else Pop(s); } if (StackEmpty (s) ) //調(diào)用判棧空函數(shù) printf (“配對正確！〞); //假如?？?，說明配對正確，并返回1 else printf (“配對錯誤！〞); //配對錯誤返回0 } （3） 設(shè)計一個將十進(jìn)正整數(shù)轉(zhuǎn)換為十進(jìn)制數(shù)的算法，并要求上機(jī)調(diào)試通過。 解： #include<stdio.h> #include<stdlib.h> typedef struct stacknode //定義棧的存儲結(jié)構(gòu) { int data; struct stacknode *next; }stacknode; typedef struct { stacknode *top; //定義棧頂?shù)闹羔? }linkstack; void Conversion(int n) //棧的應(yīng)用：十——十六進(jìn)制轉(zhuǎn)換 { linkstack s; int x; s.top=NULL; //置棧空 do { x=n%16; //取余數(shù) n= n/16 ; //取新的商 stacknode *p=new stacknode; //申請新結(jié)點(diǎn) p->next=s.top ; //修改棧頂指針 s.top=p; s.top->data=x; //余數(shù)入棧 } while(n); printf("\n\t\t轉(zhuǎn)換后的十六進(jìn)制數(shù)值為："; while (s.top) //出棧處理 { if(s.top->data<10); printf("%d",s.top->data); else switch(s.top->data) { case 10: printf("%c",'A');break; case 11: printf("%c",'B');break; case 12: printf("%c",'C');break; case 13: printf("%c",'D');break; case 14: printf("%c",'E');break; case 15: printf("%c",'F');break; } stacknode *p=s.top; s.top=s.top->next; free(p) ; //出棧一個余數(shù)，收回一個結(jié) } printf("\n\n"); } void main() { int n; printf("\n\t\t請輸入一個十進(jìn)制正整數(shù)："); scanf("%d",&n); Conversion(n); } 單元練習(xí)4 一．判斷題〔如下各題，正確的請在前面的括號打√；錯誤的打╳〕 〔√〕〔1〕隊列是限制在兩端進(jìn)展操作的線性表。 〔√〕〔2〕判斷順序隊列為空的標(biāo)準(zhǔn)是頭指針和尾指針都指向同一個結(jié)點(diǎn)。 〔×〕〔3〕在鏈隊列上做出隊操作時，會改變front指針的值。 〔√〕〔4〕在循環(huán)隊列中，假如尾指針rear大于頭指針front，其元素個數(shù)為rear- front。 〔×〕〔5〕在單向循環(huán)鏈表中，假如頭指針為h，那么p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)的條件是p=h。 〔√〕〔6〕鏈隊列在一定圍不會出現(xiàn)隊滿的情況。 〔×〕〔7〕在循環(huán)鏈隊列中無溢出現(xiàn)象。 〔×〕〔8〕棧和隊列都是順序存儲的線性結(jié)構(gòu)。 〔×〕〔9〕在隊列中允許刪除的一端稱為隊尾。 〔×〕〔10〕順序隊和循環(huán)隊關(guān)于隊滿和隊空的判斷條件是一樣的。 二．填空題 （1） 在隊列中存取數(shù)據(jù)應(yīng)遵循的原如此是先進(jìn)先出。 （2） 隊列是被限定為只能在表的一端進(jìn)展插入運(yùn)算，在表的另一端進(jìn)展刪除運(yùn)算的線性表。 （3） 在隊列中，允許插入的一端稱為隊尾。 （4） 在隊列中，允許刪除的一端稱為隊首〔或隊頭〕。 （5） 隊列在進(jìn)展出隊操作時，首先要判斷隊列是否為空。 （6） 順序隊列在進(jìn)展入隊操作時，首先要判斷隊列是否為滿。 （7） 順序隊列初始化后，front=rear= -1 。 （8） 解決順序隊列“假溢出〞的方法是采用循環(huán)隊列。 （9） 循環(huán)隊列的隊首指針為front，隊尾指針為rear，如此隊空的條件為 front == rear 。 （10） 鏈隊列LQ為空時，LQ->front->next= NULL 。 （11） 設(shè)長度為n的鏈隊列用單循環(huán)鏈表表示，假如只設(shè)頭指針，如此入隊操作的時間復(fù)雜度為 O〔n〕。 （12） 設(shè)長度為n的鏈隊列用單循環(huán)鏈表表示，假如只設(shè)尾指針，如此出隊操作的時間復(fù)雜度為 0〔1〕。 （13） 在一個鏈隊列中，假如隊首指針與隊尾指針的值一樣，如此表示該隊列為空。 （14） 設(shè)循環(huán)隊列的頭指針front指向隊首元素，尾指針rear指向隊尾元素后的一個空閑元素，隊列的最大空間為MAXLEN，如此隊滿標(biāo)志為： front==(rear+1)%MAXLEN 。 （15） 在一個鏈隊列中，假如隊首指針為front，隊尾指針為rear，如此判斷該隊列只有一個結(jié)點(diǎn)的條件為： front==rear && front !NULL 。 (或 front==rear && front <>NULL ) （16） 向一個循環(huán)隊列中插入元素時，首先要判斷隊尾指針，然后再向指針?biāo)傅奈恢脤懭胄碌臄?shù)據(jù)。 （17） 讀隊首元素的操作不改變〔或不影響〕隊列元素的個數(shù)。 〔18〕設(shè)循環(huán)隊列的容量為40〔序號從0到39〕，現(xiàn)經(jīng)過一系列的入隊和出隊運(yùn)算后，有 front=11，rear=19，如此循環(huán)隊列中還有 8 個元素。 〔L= (N＋rear－front)% N=〔40＋19－11〕% 40=8〕 〔19〕隊列Q，經(jīng)過如下運(yùn)算：InitQueue(Q)(初始化隊列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x); ReadFront(Q,x);QEmpty(Q);后的值是0 。 〔20〕隊列Q經(jīng)過InitQueue(Q)(初始化隊列);InQueue(Q,a);InQueue(Q,b); ReadFront(Q,x)后，x的值是 a 。 三．選擇題 〔1〕隊列是限定在〔 D 〕進(jìn)展操作的線性表。 A．中間 B．隊首 C．隊尾 D．端點(diǎn) 〔2〕隊列中的元素個數(shù)是( B )。 A．不變的 B．可變的 C．任意的 D．0 〔3〕同一隊列各元素的類型( A )。 A．必須一致 B．不能一致 C．可以不一致 D．不限制 〔4〕隊列是一個( C )線性表結(jié)構(gòu)。 A．不加限制的 B．推廣了的 C．加了限制的 D．非 〔5〕當(dāng)利用大小為n的數(shù)組順序存儲一個隊列時，該隊列的最后一個元素的下標(biāo)為〔 B 〕。 A．n-2 B．n-1 C．n D．n+1 〔6〕一個循環(huán)隊列一旦說明，其占用空間的大小〔 A 〕。 A．已固定 B．可以變動 C．不能固定 D．動態(tài)變化 〔7〕循環(huán)隊列占用的空間( A )。 A．必須連續(xù) B．不必連續(xù) C．不能連續(xù) D．可以不連續(xù) 〔8〕存放循環(huán)隊列元素的數(shù)組data有10個元素，如此data數(shù)組的下標(biāo)圍是( B )。 A．0..10 B．0..9 C．1..9 D．1..10 〔9〕假如進(jìn)隊的序列為：A，B，C，D，如此出隊的序列是〔 C 〕。 A．B，C，D，A B．A，C，B，D C．A，B，C，D D．C，B，D，A 〔10〕四個元素按：A，B，C，D順序連續(xù)進(jìn)隊Q，如此隊尾元素是〔 D 〕。 A． A B． B C． C D． D 〔11〕四個元素按：A，B，C，D順序連續(xù)進(jìn)隊Q，執(zhí)行一次OutQueue(Q)操作后，隊頭元素是〔 B 〕。 A． A B． B C． C D． D 〔12〕四個元素按：A，B，C，D順序連續(xù)進(jìn)隊Q，執(zhí)行四次OutQueue(Q)操作后，再執(zhí)行QEmpty(Q);后的值是〔 B 〕。 A． 0 B． 1 C． 2 D． 3 〔13〕隊列Q，經(jīng)過如下運(yùn)算后，x 的值是〔 B 〕。 InitQueue(Q)(初始化隊列);InQueue(Q,a); InQueue(Q,b);OutQueue(Q,x); ReadFront (Q,x); A．a(chǎn) B．b C．0 D．1 〔14〕循環(huán)隊列SQ隊滿的條件是( B )。 A．SQ->rear==SQ->front B．(SQ->rear+1)% MAXLEN ==SQ->front C．SQ->rear==0 D．SQ->front==0 〔15〕設(shè)鏈棧中結(jié)點(diǎn)的結(jié)構(gòu)：data為數(shù)據(jù)域，next為指針域，且top是棧頂指針。假如想在鏈棧的棧頂插入一個由指針s所指的結(jié)點(diǎn)，如此應(yīng)執(zhí)行如下〔 A 〕操作。 A．s->next=top->next；top->next=s； B．top->next=s； C．s->next=top；top=top->next； D．s->next=top；top=s； 〔16〕帶頭結(jié)點(diǎn)的鏈隊列LQ示意圖如下，鏈隊列的隊頭元素是〔 A 〕 LQ->front H A B C D Λ LQ->rear A．A B．B C．C D．D 〔17〕帶頭結(jié)點(diǎn)的鏈隊列LQ示意圖如下，指向鏈隊列的隊頭指針是〔 C 〕 LQ