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

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

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

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

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

5、章 線性表 根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù)，將線性鏈表分成_和_；而又根據(jù)指針的連接方式，鏈表又可分成_和_。單鏈表多重鏈表動(dòng)態(tài)鏈表靜態(tài)鏈表第二章 線性表 下面是用c語言編寫的對(duì)不帶頭結(jié)點(diǎn)的單鏈表進(jìn)行就地逆置的算法，該算法用L返回逆置后的鏈表的頭指針，試在空缺處填入適當(dāng)?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é)點(diǎn)L=p; /頭指針仍為L第三章 棧和隊(duì)列答案：答案：第一題選D，第二題選C解

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

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

8、他操作：隊(duì)頭、隊(duì)尾指針加1，可用取模(余數(shù))運(yùn)算實(shí)現(xiàn)。隊(duì)頭指針進(jìn)1: front = (front+1) %maxsize;隊(duì)尾指針進(jìn)1: rear = (rear+1) % maxsize;隊(duì)列初始化：front = rear = 0;隊(duì)空條件：front = rear;隊(duì)滿條件：(rear+1) % maxsize = front;第三章 棧和隊(duì)列 消除遞歸不一定需要使用棧，此說法（ ）。 隊(duì)列邏輯上是一個(gè)下端和上端既能增加又能減少的線性表。（ ）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 )個(gè)表元素組成的有限序列，記作 LS = (a0, a1, a2, , an-1)LS是表名，ai是表元素，它可以是表 (稱為子表)，可以是數(shù)據(jù)元素(稱為原子)。n為表的長度。廣義表的深度（廣義表中括號(hào)的重?cái)?shù)）設(shè)非空廣義表為LS=(a1,a2,an) 其中ai(i=1,2,n)或?yàn)樵踊驗(yàn)長S的子表。原子的深度為零，空表的深度為1，其它情況下表長為各子表深度最大值加1。第四、五章 字符

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

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

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

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

14、找 在平衡二叉樹中插入一個(gè)結(jié)點(diǎn)后造成了不平衡，設(shè)最低的不平衡結(jié)點(diǎn)為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ù)雜越好，因?yàn)檫@樣隨機(jī)性好，沖突小 B除留余數(shù)法是所有哈希函數(shù)中最好的 C不存在特別好與壞的哈希函數(shù)，要視情況而定 D若需在哈希表中刪去一個(gè)元素，不管用何種方法解決沖突都只要 簡單的將該元素刪去即可答案：答案：選C解析解析：理解哈希的本質(zhì)：

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

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

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