軟件開發(fā)技術(shù)基礎(chǔ) 第4版 習(xí)題答案 -第2章

第2章習(xí)題參考解答一、名詞解釋線性表：線性數(shù)據(jù)結(jié)構(gòu)是由有限個元素組成的有序序列，記作（a0,a1,…,an）。除了a0和an之外，任意元素ai都有一個直接前趨ai-1和一個直接后繼ai+1。a0無前趨，an無后繼。棧：是限制在表的一端進行插入和刪除操作的線性表。隊列：是只能在表的一端進行插入，而在另一端進行刪除操作的線性表。完全二叉樹：從滿二叉樹葉子所在的層次中，自右向左連續(xù)缺少若干葉子所得到的二叉樹被稱為完全二叉樹。帶權(quán)路徑長度：二叉樹有n個帶有權(quán)值的葉子結(jié)點，每個葉子到根的路徑長度乘以其權(quán)值之和稱為二叉樹帶權(quán)路徑長度。無向圖：若圖是由一些頂點和邊構(gòu)成則稱之為無向圖。圖中的路徑:在圖中，若從頂點vi出發(fā)，沿一些邊或弧，經(jīng)過頂點vp1，vp2，…，vpm，到達(dá)頂點vj。則稱頂點序列(vi，vp1，vp2，…，vpm，vj)為從頂點vi到頂點vj的路徑。生成樹: 在無向圖中，一個連通圖的生成樹是它的極小連通子圖，它包含了所有頂點以及足以夠成一棵樹的邊，并且這些邊使得任意兩頂點相互連通。 平均查找長度:是為了確定數(shù)據(jù)元素在查找表中的位置，需要將給定值和表中的數(shù)據(jù)元素的關(guān)鍵字進行比較的次數(shù)的期望值。圖中的弧:若頂點x到y(tǒng)是的一條單向通路，則稱為弧，用<x，y>表示。連通圖:在無向圖中，若從頂點vi到頂點vj有路徑，則稱頂點vi與vj是連通的。如果圖中任意一對頂點都是連通的，則稱此圖是連通圖。二、填空題1.算法效率的衡量主要有兩個指標(biāo)：時間復(fù)雜度和空間復(fù)雜度。2．采用順序存儲結(jié)構(gòu)的線性表稱為順序表，它的數(shù)據(jù)元素按照邏輯順序依次存放在一組連續(xù)的存儲單元中。邏輯上相鄰的數(shù)據(jù)元素，其存儲位置也相鄰。3．單鏈表用一組地址任意的存儲單元存放線性表中的數(shù)據(jù)元素。其邏輯上相鄰的元素的物理位置不一定相鄰。4．單鏈表每個結(jié)點都包含數(shù)據(jù)域和指針域兩部分。5．為了能順次訪問單鏈表的每個結(jié)點，需要保存單鏈表第一個結(jié)點的存儲地址。這個地址稱為單鏈表的頭指針。6．為了操作上的方便，可以在單鏈表的頭部增加一個特殊的結(jié)點，稱為頭結(jié)點。該結(jié)點的數(shù)據(jù)域為空。7．樹有且只有一個根結(jié)點，沒有孩子結(jié)點的結(jié)點可稱為葉子，二叉樹的每個結(jié)點至多只有兩棵子樹。8．圖結(jié)構(gòu)又可分為無向圖和有向圖兩大類。在圖結(jié)構(gòu)中，數(shù)據(jù)元素通常稱為頂點；兩個數(shù)據(jù)元素間的聯(lián)系在有向圖中稱為弧，在無向圖中稱為邊。三、判斷題 （1）線性表每個結(jié)點都有一個前趨和一個后繼。（錯） （2）二叉樹不能用順序方式存儲。（錯） （3）哈夫曼樹又稱最小生成樹。（錯） （4）圖的深度優(yōu)先遍歷優(yōu)于廣度優(yōu)先遍歷。（錯） （5）平均查找長度就是時間復(fù)雜度。（錯）（6）冒泡排序的時間復(fù)雜度優(yōu)于簡單選擇排序。（錯）四、選擇題1.一個有頭結(jié)點的單鏈表中,P為指向頭結(jié)點的指針,則首元(位于頭結(jié)點之后)指針可表示為()。A.P.next.nextB.PC.P.dataD.P.next答：D2.數(shù)列4321依次執(zhí)行入棧操作，在入棧過程中可以隨時執(zhí)行出棧操作，則其出棧順序可能是（）。A.1423B.2413C.1234D.4132答：C3.具有35個結(jié)點的完全二叉樹的深度為（）。A.4B.6C.8D.12答：B4.對長度為12的有序表進行二分查找，在等概率情況下，查找成功的ASL為（）。A.37/12B.39/11C.34/12D.33/11答：A5．一棵完全二叉樹共有200個數(shù)據(jù)元素，自上而下自左向右編號，則第67號點的右孩子是（）號。A．134 B.135C.136 D.137答：B6.二叉樹的中序遍歷順序為abcd，先序遍歷順序為cabd,則二叉樹是下列（）。abcdcabcdcadbabdccabdA.B.C.D.