數(shù)據(jù)結(jié)構(gòu) 課后習(xí)題重點解析

1、數(shù)據(jù)結(jié)構(gòu)數(shù)據(jù)結(jié)構(gòu) 課后作業(yè)講解課后作業(yè)講解難點剖析難點剖析2013.12.30第一章 緒論 以下數(shù)據(jù)結(jié)構(gòu)中，哪一個是邏輯結(jié)構(gòu)（ ）？ A順序表 B. 散列表 C. 有序表 D. 單鏈表答案：答案：選C解析：解析：A和D是線性表的物理存儲實現(xiàn)方式，B也就是哈希表，也是一種物理結(jié)構(gòu)。C是一種邏輯結(jié)構(gòu)，它只規(guī)定了表中元素有序排列，而不關(guān)心具體的存儲方式（連續(xù)或離散的）。第一章 緒論答案：答案：選D解析：解析：概念掌握。第一章 緒論 順序存儲表示中數(shù)據(jù)元素之間的邏輯關(guān)系是由（ ）表示的，鏈接存儲表示中數(shù)據(jù)元素之間的邏輯關(guān)系是由（ ）表示的。 A. 指針 B. 邏輯順序 C. 存儲位置 D. 問題上下文

2、答案：答案：第一個選C，第二個選A解析：解析：順序存儲一般使用數(shù)組存儲，而數(shù)據(jù)元素的邏輯關(guān)系是通過元素在數(shù)組中的位置表示的，也就是我們所說的下標，所以第一個空應(yīng)該選C。第一章 緒論 一個數(shù)據(jù)結(jié)構(gòu)在計算機中 稱為存儲結(jié)構(gòu)。 計算機執(zhí)行下面的語句時，語句s的執(zhí)行次數(shù)為 。 FOR(i=l；i=i;j-) s; 表示(n+3)(n-2)/2解析：解析：外層循環(huán)的執(zhí)行次數(shù)為n-2次里層循環(huán)的執(zhí)行次數(shù)分別是n、n-1、n-2、4、3次，所以s的執(zhí)行次數(shù)應(yīng)為(3+n)*(n-2)/2。實際上是一個等差數(shù)列求和。當i=1時，里層循環(huán)為n次，當i=n-2時，里層循環(huán)為3次。第二章 線性表 順序表是線性表的（

3、）存儲表示。 A有序 B連續(xù) C數(shù)組 D順序存取答案：答案：選C解析：解析：順序表是線性表的物理存儲的一種實現(xiàn)方式，其實質(zhì)就是一個數(shù)組。1. 線性表中的元素并不具備有序性，元素之間不存在有序的邏輯關(guān)系，所以A不是。2. 順序表確實在內(nèi)存中開辟了一個連續(xù)的存儲空間，但是，僅僅是連續(xù)的存儲空間，還不能描述線性表的邏輯特征，即： 線性表中的相鄰元素具有序偶關(guān)系，3. 順序存取是一種存儲方式，而不是存儲表示。第二章 線性表 帶頭結(jié)點的雙向循環(huán)鏈表L為空表的條件是（ ）。 AL-lLink-rLink= NULL BL-rLink= Link CL-lLink = NULL DL=NULL答案：答案：選

4、B解析：解析：雙向循環(huán)鏈表要是空表，那么頭結(jié)點的右指針應(yīng)指向自己，形成一個環(huán)路。第二章 線性表 某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ ）存儲方式最節(jié)省運算時間。 A單鏈表 B僅有頭指針的單循環(huán)鏈表 C雙鏈表 D僅有尾指針的單循環(huán)鏈表答案：答案：選D解析：解析：比較每個選項的插入和刪除操作的時間復(fù)雜度就可得出最節(jié)省時間的數(shù)據(jù)結(jié)構(gòu)。第二章 線性表 靜態(tài)鏈表中指針表示的是（ ）。 A內(nèi)存地址 B數(shù)組下標 C下一元素地址 D左、右孩子地址答案：答案：選B解析：解析：單鏈表中的指針表示的是下一個元素的地址。在靜態(tài)鏈表中，我們通過數(shù)組下標確定元素的所在位置。第二

5、章 線性表 根據(jù)線性表的鏈式存儲結(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù)，將線性鏈表分成_和_；而又根據(jù)指針的連接方式，鏈表又可分成_和_。單鏈表多重鏈表動態(tài)鏈表靜態(tài)鏈表第二章 線性表 下面是用c語言編寫的對不帶頭結(jié)點的單鏈表進行就地逆置的算法，該算法用L返回逆置后的鏈表的頭指針，試在空缺處填入適當?shù)恼Z句。 void reverse（linklist &L）p=null； q=L；while（q！=null）(1) ; q-next=p；p=q；(2) ; (3) ; L=L-next; /暫存后繼q=L; /待逆置結(jié)點L=p; /頭指針仍為L第三章 棧和隊列答案：答案：第一題選D，第二題選C解

6、析：解析：這兩題是棧的混洗一類型的題目。進棧肯定是按照一個給定的順序，但是通過不同時刻出棧達到混洗目的。第一題中只知道輸出序列的第一個元素是i，但是后續(xù)元素的輸出是不定的，所以選D。第二題中知道輸出序列的第一個輸出元素是n，而n是最后一個輸入元素，那么這意味著，n該輸出序列其實是一個逆輸入序列，那么第i個元素為n-i+1。第三章 棧和隊列 若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少？( ) A. 1和 5 B. 2和4 C. 4和2 D. 5和1 6.答案：答案：選B解析：解析：

7、根據(jù)循環(huán)隊列的插入和刪除函數(shù)，手動執(zhí)行對應(yīng)操作，觀察rear和front的變化。初始狀態(tài)： rear=0，front=3；刪除一個元素后（即出隊）： rear=0，front=4；加入一個元素后（即入隊）： rear=1，front=4；加入一個元素后（即入隊）： rear=2，front=4；（即為終態(tài)）第三章 棧和隊列 假設(shè)以數(shù)組Am存放循環(huán)隊列的元素,其頭尾指針分別為front和rear，則當前隊列中的元素個數(shù)為（ ）。 A(rear-front+m)%m Brear-front+1 C(front-rear+m)%m D(rear-front)%m答案：答案：選A解析：解析：循環(huán)隊列其

8、他操作：隊頭、隊尾指針加1，可用取模(余數(shù))運算實現(xiàn)。隊頭指針進1: front = (front+1) %maxsize;隊尾指針進1: rear = (rear+1) % maxsize;隊列初始化：front = rear = 0;隊空條件：front = rear;隊滿條件：(rear+1) % maxsize = front;第三章 棧和隊列 消除遞歸不一定需要使用棧，此說法（ ）。 隊列邏輯上是一個下端和上端既能增加又能減少的線性表。（ ）T解析：解析：尾遞歸算法可以通過迭代算法來消除遞歸。T第四、五章 字符串、數(shù)組和廣義表 若串S=“software”，其子串的數(shù)目是（ ）。 A

9、8 B37 C36 D9第四、五章 字符串、數(shù)組和廣義表 設(shè)廣義表L=（a,b,c），則L的長度和深度分別為（ ）。 A. 1和1 B. 1和3 C. 1和2 D. 2和3答案：答案：選C解析：解析：n ( 0 )個表元素組成的有限序列，記作 LS = (a0, a1, a2, , an-1)LS是表名，ai是表元素，它可以是表 (稱為子表)，可以是數(shù)據(jù)元素(稱為原子)。n為表的長度。廣義表的深度（廣義表中括號的重數(shù)）設(shè)非空廣義表為LS=(a1,a2,an) 其中ai(i=1,2,n)或為原子或為LS的子表。原子的深度為零，空表的深度為1，其它情況下表長為各子表深度最大值加1。第四、五章 字符

10、串、數(shù)組和廣義表 實現(xiàn)字符串拷貝的函數(shù) strcpy為： void strcpy(char *s , char *t) /*copy t to s*/while ( ) *s+=*t+ 或 (*s+=*t+)!=0第六章 樹答案：答案：選A解析：解析：根據(jù)滿二叉樹的計算類比得出結(jié)果。第六章 樹 設(shè)森林F對應(yīng)的二叉樹為B，它有m個結(jié)點，B的根為p,p的右子樹結(jié)點個數(shù)為n,森林F中第一棵樹的結(jié)點個數(shù)是（ ） Am-n Bm-n-1 Cn+1 D條件不足，無法確定答案：答案：選A解析：解析：森林的對應(yīng)的二叉樹的根加上根的左子樹就是第一棵樹，那么第一棵樹的結(jié)點個數(shù)即為m-n。第六章 樹 某二叉樹的前序

11、序列和后序序列正好相反，則該二叉樹一定是（）的二叉樹。 A空或只有一個結(jié)點 B任一結(jié)點無左子樹 C高度等于其結(jié)點數(shù) D任一結(jié)點無右子樹答案：答案：選C解析解析：前序遍歷為根左右，后序遍歷為左右根，而要是兩者序列逆反，那么意味著每層只有一個節(jié)點，前序遍歷得到的是從根到葉子節(jié)點的順序輸出，而后序遍歷得到則是從葉子節(jié)點到根的逆序輸出。第六章 樹 二叉樹以后序遍歷序列與前序遍歷序列反映的同樣的信息。（ ）解析：解析：反應(yīng)的都是樹的一種序列化信息。T第六章 樹 在順序存儲的二叉樹中，編號為i和j的兩個結(jié)點處在同一層的條件是 。解析：解析：用順序存儲二叉樹時，要按完全二叉樹的形式存儲，非完全二叉樹存儲時，

12、要加“虛結(jié)點”。設(shè)編號為i和j的結(jié)點在順序存儲中的下標為s 和t ,則結(jié)點i和j在同一層上的條件是log2s=log2t。log2s=log2t第七章 圖 若一個有向圖的鄰接距陣中，主對角線以下的元素均為零,則該圖的拓撲有序序列（ ）。 A存在 B不存在答案：答案：選A解析：解析：主對角線以下的元素均為零，說明圖中不存在環(huán)，所以該圖攢在拓撲有序序列。第七章 圖 下列關(guān)于AOE網(wǎng)的敘述中，不正確的是（ ）。 A關(guān)鍵活動不按期完成就會影響整個工程的完成時間 B任何一個關(guān)鍵活動提前完成，那么整個工程將會提前完成 C所有的關(guān)鍵活動提前完成，那么整個工程將會提前完成 D某些關(guān)鍵活動提前完成，那么整個工程

13、將會提前完成答案：答案：選B解析：解析：并不是任意一個關(guān)鍵活動提前完成就意味著整個工程將會提前完成，比如兩個事件有兩個關(guān)鍵活動，其中一個提前完成，不能使整個工程提前完成。第七章 圖 任何無向圖都存在生成樹。（ ） 拓撲排序算法把一個無向圖中的頂點排成一個有序序列。 （ ） 在AOE圖中，關(guān)鍵路徑上活動的時間延長多少，整個工程的時間也就隨之延長多少。 （ ）FFT第九章 查找 既希望較快的查找又便于線性表動態(tài)變化的查找方法是 ( ) A順序查找 B. 折半查找 C. 索引順序查找 D. 哈希法查找答案：答案：選C解析：解析：解題關(guān)鍵在于查找方法要適應(yīng)線性表的動態(tài)變化，因而C是最適合的。第九章 查

14、找 在平衡二叉樹中插入一個結(jié)點后造成了不平衡，設(shè)最低的不平衡結(jié)點為A,并已知A的左孩子的平衡因子為0右孩子的平衡因子為1,則應(yīng)作( ) 型調(diào)整以使其平衡。 A. LL B. LR C. RL D. RR答案：答案：選C解析：解析：要掌握平衡二叉樹各種不平衡類型的處理方法。第九章 查找 下面關(guān)于哈希(Hash，雜湊)查找的說法正確的是( ) A哈希函數(shù)構(gòu)造的越復(fù)雜越好，因為這樣隨機性好，沖突小 B除留余數(shù)法是所有哈希函數(shù)中最好的 C不存在特別好與壞的哈希函數(shù)，要視情況而定 D若需在哈希表中刪去一個元素，不管用何種方法解決沖突都只要 簡單的將該元素刪去即可答案：答案：選C解析解析：理解哈希的本質(zhì)：

15、在記錄的存儲地址和它的關(guān)鍵字之間建立一個確定的對應(yīng)關(guān)系；這樣，不經(jīng)過比較，一次存取就能得到所查元素的查找方法。哈希函數(shù)的好壞取決于數(shù)據(jù)本身。第九章 查找 散列函數(shù)有一個共同的性質(zhì)，即函數(shù)值應(yīng)當以( )取其值域的每個值。 A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率答案：答案：選D第九章 查找 完全二叉樹肯定是平衡二叉樹。（ ） Hash表的平均查找長度與處理沖突的方法無關(guān)。（ ） 在平衡二叉樹中，向某個平衡因子不為零的結(jié)點的樹中插入一新結(jié)點，必引起平衡旋轉(zhuǎn)。（ ）FFF第九章 查找 己知有序表為(12,18,24,35,47,50,62,83,90,115，134)當用二分法

16、查找90時，需_次查找成功，47時_成功，查100時，需_次才能確定不成功。 動態(tài)查找表和靜態(tài)查找表的重要區(qū)別在于前者包含有_和_運算，而后者不包含這兩種運算。243插入刪除第十章 排序 下列排序算法中，其中（ ）是穩(wěn)定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接選擇排序，歸并排序 D. 歸并排序，冒泡排序答案：答案：選D解析：解析：什么是排序的穩(wěn)定性：排序方法的穩(wěn)定性: 如果在對象序列中有兩 個對象ri和rj, 它們的排序碼 ki = kj , 且在排序之前, 對象ri排在rj前面。如果在排序之后, 對象ri仍在對象rj的前面, 則稱這個排序方法是穩(wěn)定的, 否則稱這個排序

17、方法是不穩(wěn)定的。第十章 排序1. 排序趟數(shù)與序列的原始狀態(tài)有關(guān)的排序方法是( )排序法。 A插入 B. 選擇 C. 冒泡 D. 快速2. 下列排序算法中，在待排序數(shù)據(jù)已有序時，花費時間反而最多的是( ) 排序。 A 冒泡 B. 希爾 C. 快速 D. 堆 3. 快速排序方法在（ ）情況下最不利于發(fā)揮其長處。 A. 要排序的數(shù)據(jù)量太大 B. 要排序的數(shù)據(jù)中含有多個相同值 C. 要排序的數(shù)據(jù)個數(shù)為奇數(shù) D. 要排序的數(shù)據(jù)已基本有序答案答案：1選C、D2選C3選D第十章 排序 直接插入排序用監(jiān)視哨的作用是 _。 對于7個元素的集合1，2，3，4，5，6，7進行快速排序，具有最小比 較和交換次數(shù)的初始排列次序