數據結構與算法復習題含答案(已修改)

　

【正文】 《數據結構與算法》20152016學年第1學期考試復習題一、 選擇題（下面各小題有一個正確答案，請將正確答案的編號填寫在各小題的括號內）。在一棵具有5層的滿二叉樹中結點總數為（ A ）。A) 31 B）32C）33 D）16串的邏輯結構與（ D ）的邏輯結構不相同。A）線性表 B）棧C）隊列 D）集合下列序列中，執行第一趟快速排序后得到的序列是（ A ）。A）[d,a,e,d,b]f[h,g] B) [c,e,a,d]f[h,g,b]C) [g,a,e,c,b]f[d,h] D) [a,b,c,d,]f[e,g,h]n個頂點的強連通圖至少有（ A ）條邊。A）n B）n+1 C）n1 D）n(n1)數據結構中，在邏輯上可以把數據結構分成（ B ）。A）動態結構和靜態結構B）線性結構和非線性結構C）緊湊結構和非緊湊結構D）內部結構和外部結構鏈式存儲的存儲結構所占存儲空間（ A ）。A）分兩部分，一部分存放結點值，另一部分存放表示結點間關系的指針B）只有一部分，存放結點值C）只有一部分，存儲表示結點間關系的指針D）分兩部分，一部分存放結點值，另一部分存放結點所占單元數有一個有序表{1，4，6，10，18，35，42，53，67，71，78，84，92，99}。當用二分查找法查找鍵值為84的結點時，經（ B ）比較后查找成功。A) 4B)3C)2D)12設單鏈表中指針p指向結點m，若要刪除m之后的結點（若存在），則需修改指針的操作為（ A ）。A）pnext=pnextnext。 B） p=pnext。C）p=pnextnext。 D） pnext=p。n個頂點，e條邊的有向圖的鄰接矩陣中非零元素有（ C ）個。A）nB）2eC）e D） n+e對下圖V4的度為（ C ）。A）1 B）2 C）3 D）4 v1 v2 v3 v41在一棵度為3的樹中，度為3的結點個數為2，度為2的結點個數為1，則度為0的結點個數為（ C ）。A）4 B）5C）6 D）71在數據結構中，從邏輯上可以把數據結構分為（ C ）。 A）動態結構和靜態結構 B）緊湊結構和非緊湊結構 C）線性結構和非線性結構 D）內部結構和外部結構 1用一維數組A進行順序存儲時，若起始地址為loc(A1)，元素長度為c，則A的第i個數組單元在存放地址loc(Ai)，等于（ B ）。A）loc(A1)+i*c B）loc(A1)+(i1)*cC）loc(A1)+i*c+1 D）loc(A1)+(i+1)*c1（ C ）在進行插入操作時，常產生假溢出現象。A）順序棧 B）循環隊列C）順序隊列 D）鏈隊列1某線性表中最常用的操作是在最后一個元素之后插入一個元素和刪除第一個元素，則采用（ D ）存儲方式最節省運算時間。 A) 單鏈表 B) 僅有頭指針的單循環鏈表 C) 雙鏈表 D) 僅有尾指針的單循環鏈表1向一個棧頂指針為hs的鏈棧中插入一個s結點時，應執行（ D ）。 A) hsnext=s。 B) snext=hsnext。 hsnext=s。 C) snext=hs。 hs=s。 D) snext=hs。hs=hsnext。1在一個鏈隊列中，假定front和rear分別為隊首和隊尾指針，則刪除一個結點的操作為（ B ）。 A) rear=rearnext。 B) front=frontnext。 C) rear=frontnext。 D) front=rearnext1已知棧的最大容量為4。若進棧序列為1，2，3，4，5，6，且進棧和出棧可以穿插進行,則可能出現的出棧序列為（ C ）。 A) 5，4，3，2，1，6 B) 2，3，5，6，1，4 C) 3，2，5，4，1，6 D) 1，4，6，5，2，31已知廣義表L=((x,y,z),a,(u,t,w))，從L 表中取出原子項t 的操作是（ D ）。 A) Head(Head(Tail(Tail(L)))) B) Tail(Head(Head(Tail(L)))) C) Head(Tail(Head(Tail(L)))) D)Head(Tail(Head(Tail(Tail(L)))))下列各種數據結構中屬于線性結構的有（ A ）。 A）棧 B) 二叉樹 C) 廣義表 D) 圖2倘若在對串的插入、刪除運算中，期望運算速度最快，則應采用（ C ）。 A）順序表示法 B）單字符為結點的單鏈表表示法 C）等量分塊表示法 D）不等量分塊表示法2廣義表head(((a,b),(c,d)))的運算結果為（ A ）。 A）(a,b) B）(c,d) C）空表 D）（（a,b）,(c,d)）2 n個頂點的圖的最小生成樹必定（ D ），是不正確的描述。 A）不唯一 B）權的總和唯一 C）不含回路 D）有n條邊2采用鏈結構存儲線性表時，其地址（ B ）。 A）必須是連續的 B）連續不連續都可以 C）部分地址必須是連續 D）必須是不連續的2隊列的操作的原則是（ A ）。 A）先進先出 B) 后進先出 C) 只能進行插入 D) 只能進行刪除2以下屬于順序存儲結構優點的是（ A ）。 A) 存儲密度大 B) 插入運算方便 C）刪除運算方便 D）可方便地用于各種邏輯結構的存儲表示2數據結構研究的內容是（ D ）。 A）數據的邏輯結構 B）數據的存儲結構 C）建立在相應邏輯結構和存儲結構上的算法 D）包括以上三個方面2在一個單鏈表中，已知q結點是p結點的前趨結點，若在q和p之間插入s結點，則須執行（ A ） A）qnext=s。snext=p。B）snext=pnext。pnext=s。 C）pnext=snext。snext=p D）pnext=s。snext=q。2若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（ D ）存儲方式最節省時間。 A）順序表 B）雙鏈表 C）帶頭結點的雙循環鏈表 D）單循環鏈表下面關于線性表的敘述中，錯誤的是哪一個？（ D ） A）線性表采用順序存儲，必須占用一片連續的存儲單元。 B）線性表采用鏈接存儲，便于插入和刪除操作。 C）線性表采用鏈接存儲，不必占用一片連續的存儲單元。 D）線性表采用順序存儲，便于進行插入和刪除操作。3在一個具有n個單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當做出棧處理時，top變化為（ C ）。 A）top不變 B）top=0 C）top 16