數(shù)據(jù)結構編程試題及答案

一、單項選擇題（每題2分，共20分）1.線性表采用鏈式存儲時，其地址（）。A.必須是連續(xù)的B.一定是不連續(xù)的C.部分地址必須是連續(xù)的D.連續(xù)與否均可以2.棧和隊列的共同特點是（）。A.只允許在端點處插入和刪除元素B.都是先進后出C.都是先進先出D.沒有共同點3.具有n個結點的完全二叉樹的深度為（）。A.?log?n?+1B.log?nC.?log?n?D.log?n+14.對線性表進行二分查找時，要求線性表必須（）。A.以順序方式存儲B.以鏈式方式存儲C.以順序方式存儲，且結點按關鍵字有序排列D.以鏈式方式存儲，且結點按關鍵字有序排列5.在一個單鏈表中，已知q結點是p結點的前驅結點，若在q和p之間插入s結點，則執(zhí)行（）。A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;C.q->next=s;s->next=p;D.p->next=s;s->next=q;6.若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[1]中，現(xiàn)進行二分查找，則查找A[3]的比較序列的下標依次為（）。A.1，2，3B.9，5，2，3C.9，5，3D.9，4，2，37.已知一個棧的入棧序列是1，2，3，…，n，其輸出序列為p1，p2，p3，…，pn，若p1=n，則pi為（）。A.iB.n-iC.n-i+1D.不確定8.樹最適合用來表示（）。A.有序數(shù)據(jù)元素B.無序數(shù)據(jù)元素C.元素之間具有分支層次關系的數(shù)據(jù)D.元素之間無聯(lián)系的數(shù)據(jù)9.圖的深度優(yōu)先遍歷類似于樹的（）遍歷。A.先序B.中序C.后序D.層次10.對n個不同的排序碼進行冒泡排序，在元素無序的情況下比較的次數(shù)為（）。A.n+1B.nC.n-1D.n(n-1)/2二、多項選擇題（每題2分，共20分）1.以下屬于線性結構的有（）。A.線性表B.棧C.隊列D.樹2.關于棧的說法正確的有（）。A.后進先出B.先進后出C.只能在一端進行插入和刪除操作D.可以在兩端進行插入和刪除操作3.二叉樹的遍歷方式有（）。A.先序遍歷B.中序遍歷C.后序遍歷D.層次遍歷4.圖的存儲結構有（）。A.鄰接矩陣B.鄰接表C.十字鏈表D.鄰接多重表5.排序算法中，穩(wěn)定的排序算法有（）。A.冒泡排序B.選擇排序C.插入排序D.歸并排序6.以下關于隊列的說法正確的是（）。A.先進先出B.后進先出C.可以在隊頭刪除元素D.可以在隊尾插入元素7.哈希表的處理沖突的方法有（）。A.開放定址法B.鏈地址法C.再哈希法D.建立公共溢出區(qū)8.以下哪些操作是數(shù)據(jù)結構中的基本操作（）。A.插入B.刪除C.查找D.排序9.對于一個有向圖，其拓撲排序的結果可能（）。A.唯一B.不唯一C.不存在D.有無數(shù)個10.以下關于線性表的順序存儲和鏈式存儲說法正確的是（）。A.順序存儲需要連續(xù)的存儲空間B.鏈式存儲不需要連續(xù)的存儲空間C.順序存儲插入和刪除操作效率低D.鏈式存儲查找操作效率低三、判斷題（每題2分，共20分）1.線性表的順序存儲結構比鏈式存儲結構更好。（）2.棧和隊列都是特殊的線性表。（）3.完全二叉樹一定是滿二叉樹。（）4.二分查找只適用于有序的順序表。（）5.圖的鄰接矩陣表示法是唯一的。（）6.冒泡排序是一種不穩(wěn)定的排序算法。（）7.哈希表的平均查找長度與處理沖突的方法有關。（）8.樹的度是指樹中所有結點的度數(shù)之和。（）9.線性表的鏈式存儲結構中，結點的存儲單元可以是不連續(xù)的。（）10.隊列的插入操作在隊頭進行，刪除操作在隊尾進行。（）四、簡答題（每題5分，共20分）1.簡述線性表順序存儲和鏈式存儲的優(yōu)缺點。2.簡述棧和隊列的區(qū)別。3.簡述二叉樹的性質。4.簡述快速排序的基本思想。五、討論題（每題5分，共20分）1.討論在實際應用中，如何選擇合適的排序算法。2.討論圖的遍歷算法（深度優(yōu)先和廣度優(yōu)先）的應用場景。3.討論哈希表在實際開發(fā)中的應用及優(yōu)缺點。4.討論線性表的不同存儲結構對其基本操作（插入、刪除、查找）的影響。答案一、單項選擇題1.D2.A3.A4.C5.C6.D7.C8.C9.A10.D二、多項選擇題1.ABC2.ABC3.ABCD4.ABCD5.ACD6.ACD7.ABCD8.ABC9.ABC10.ABCD三、判斷題1.×2.√3.×4.√5.√6.×7.√8.×9.√10.×四、簡答題1.順序存儲優(yōu)點是可隨機存取，存儲密度大；缺點是插入、刪除操作效率低，需連續(xù)空間。鏈式存儲優(yōu)點是插入、刪除靈活，無需連續(xù)空間；缺點是不可隨機存取，存儲密度小。2.棧是后進先出，只能在棧頂操作；隊列是先進先出，在隊尾插入，隊頭刪除。3.如第i層最多2^(i-1)個結點；深度為k最多2^k-1個結點；度為0結點比度為2結點多1個等。4.選基準元素，將表分兩部分，小的放左邊，大的放右邊，再分別對兩部分排序。五、討論題1.數(shù)據(jù)量小且基本有序選插入排序；數(shù)據(jù)量大選快速、歸并等高效排序；要求穩(wěn)定選冒泡、插入等。2.