成都東軟資訊科技學院
200 ~200 學年第學期期末試題——資料結構(c語言)
本課程為閉卷考試，試卷共六道大題，試卷滿分100分，考試時間120分鐘。
一．選擇題（10×2分）：共10小題，請將答案填入題中的括號中，每小題只有乙個正確答案，錯選或不選均不給分。
1．組成資料的基本單位是（ ）
ａ．資料項資料型別
c．資料元素d．資料變數
2．線性表的鏈式儲存實現有利於（ ）運算。
a．插入b．讀表元
c．查詢d．定位
3．二叉樹第i(i≥1)層最多有（ ）個結點。
a．2ib．2i
c．2i-1d．2i -1
4．設單鏈表中指標p指向結點a，若刪除a後的結點存在，則需要修改指標的操作為（ ）。
a．p->next=p->next->next b．p=p->next
c．p=p->next->nextd．p->next=p
5．設一數列的輸入順序為1,2,3,4,5,6，通過棧操作不可能排成的輸出序列為（ ）。
a．3,2,5,6,4,1b．1,5,4,6,2,3
c．2,4,3,5,1,6d．4,5,3,6,2,1
6．如果結點a有3個兄弟，而且b為a的雙親，則b是度為（ ）
ａ．34
c．5d．1
7．設迴圈佇列q[0..n-1]的頭尾指標為f.r，當插入元素時尾指標r加1，頭指標f總是指向佇列中第乙個元素的前乙個位置，則佇列中元素計數為（ ）。
a．r-fb．n-(r-f)
c．(r-f+n)%nd．(f-r+n)%n
8．若給定的關鍵字集合為，一趟快速排序結束後，鍵值的排序為（ ）。
a．10,15,14,18,20,36,40,21 b．10,15,14,18,20,40,36,21
c．10,15,14,20,18,40,36,21 d．15,10,14,18,20,36,40,21
9．設有100個元素，用二分法查詢時，最大比較次數是（ ），最小比較次數是（ ）。
a．25b．7
c．10d．1
10．具有2000個結點的二叉樹，其高度至少為（ ）。
a．9b．10
c．11d．12
二．填空題（20分）：每空2分，
１．前序序列和中序序列相同的二叉樹為 。
2．具有64個結點的完全二叉樹的深度為 。
3．資料結構講述的三大關係是
4．已知二叉樹中的葉子樹為50，僅有乙個孩子的結點數為30，則總結點數為
5．簡單選擇排序在最好情況下所做的交換元素次數為
6．佇列的原則是
7．快速排序演算法在最差的情況下其時間複雜度是
8．順序儲存的佇列如果不採用迴圈方式，則會出現問題。
三．簡答題（4×5分）
1． 試比較順序儲存和鏈式儲存的優缺點。（5分）
2． 簡述棧和佇列這兩種資料結構的相同點和不同點。（5分）
3． 已知一棵二叉樹的中序序列和後序序列分別是bdceafhg和decbhgfa，試畫出這棵二叉樹。（5分）
4． 採用簡單選擇排序對線性表（26,15,12,16,5,30）進行排序，進行交換的第一對元素是哪兩個元素？在什麼情況下，第一趟不需要進行元素的交換？（5分）
四．判斷題（5×2分）
１．如果某資料結構的每乙個元素都最多只有乙個直接前驅和乙個直接後繼，則該資料結構必為線性表。( )
2．若有乙個葉子結點是某子樹的中序遍歷的最後乙個結點，則它必是該子樹的先序遍歷的最後乙個結點。( )
3．進棧操作時，必須判斷棧是否已滿。( )
4．如果某排序演算法是穩定的，那麼該方法一定具有實際應用價值。( )
5．折半查詢法的前提之一是線性表有序。( )
五．程式填空題（3×5分）
1．以下是採用氣泡排序法對陣列a進行排序，完成程式。（4分）
bsort(int a, int n)
}}}2．在單鏈表（表頭指標為head）的元素中找出最後乙個值為e的元素，返回其指標；如果找不到，返回null。完成以下程式。(6分)
typedef srruct linknode node;
node *search_link(node *head, int e)
}return q;
}3．下列演算法是輸出一棵二叉樹的第i層的所有結點的值。假定根結點是第1層，完成以下程式。（5分）
typedef srruct linknode node;
void outi(node *tree, int i)
outi
outi
}六．演算法設計題（15分）
1．編寫演算法，刪除順序表第i個元素。（8分）
已知順序表的資料結構如下：
typedef struct
seqlist;
2．編寫演算法，求不帶頭結點的單鏈表的表表長。（7分）
已知單鏈表結點資料結構如下：
typedef struct node
lnode, *linklist;
答案及評分標準：
資料結構(c語言)答案及評分標準
一．選擇題（10×2分）：每小題只有乙個正確答案，錯選或不選均不給分。
二．填空題（20分）：每空2分。
1．沒有左子樹的二叉樹; 2．7; 3．一對一的線性關係一對多的樹關係多對多的圖關係; 4．129; 5．0; 6．先進先出； 7．o(n2)； 8．假溢位。
三．簡答題（4×5分）
1．順序儲存查詢效率高，插入和刪除效率低；鏈式儲存插入和刪除效率高，查詢效率低。
2．棧和佇列都是操作受限的線性表。棧是先進後出，操作在一端進行；佇列是先進先出，插入在一端，刪除在另一端進行。
3．4．交換的第一對元素是26和15，第乙個元素比其他元素都小時不需要進行元素的交換。
四．判斷題（5×2分）
1．×；2．√；3．×；4．×；5．√
五．程式填空題（3×5分）
1．0;a[j+1]lchild,i-1;tree->rchild,i-1
六．演算法設計題（15分）
1．int delete_seqlist(seqlist *l,int i)
for (j=i; j<=l->l->last; ++j)
l->last--;
return 1;
}2．int length_linklist(linklist l)
return j;}
C語言 資料結構 實驗
實驗四 佇列子系統 1 實驗目的 1 掌握佇列的特點及其描述方法。2 用鏈式結構實現乙個佇列。3 掌握佇列的各種基本操作。4 掌握佇列的簡單應用程式。2 實驗內容 1 設計乙個字元型的鏈佇列 2 編寫佇列的進隊 出隊 讀隊頭元素 顯示佇列中全部元素程式 3 設計乙個輸入限制性的雙佇列，要求 輸入只能...
C語言資料結構答案
助人教育qq 707223565 c語言 資料結構綜合測試 一 單項選擇題 1 下列與k n 完全等價的表示式是 c a k n b k n l c k n，n n 1 d n n 1，k n 2 已知int a 5，b 3，p b，q a 下列賦值語句中與b a 等價的語句是 a a p q b ...
1資料結構 c語言版 複習
資料結構複習資料 一 填空題 1.資料結構是一門研究非數值計算的程式設計問題中計算機的操作物件以及它們之間的關係和運算等的學科。2.資料結構被形式地定義為 d,r 其中d是資料元素的有限集合，r是d上的關係有限集合。3.資料結構包括資料的邏輯結構 資料的儲存結構和資料的運算這三個方面的內容。4.資料...