一．判斷題（下列各題，正確的請在前面的括號內打√；錯誤的打×）
（×）1.程式和演算法原則上沒有區別，所以在討論資料結構時可以通用。
（√）2.在單鏈表中，元素的儲存位置用指標聯絡，所以可以從頭結點開始查詢任何乙個元素。
（×）3.乙個棧的輸入序列為：a，b，c，d，可以得到輸出序列：c，a，b，d。
（√）4.佇列是一種「先進先出」的線性表。
（×）5.如果兩個串含有相同的字元，則說明它們相等。
（√）6.不使用遞迴，也可以實現二叉樹的前序、中序和後序遍歷。
（×）7.用鄰接表法儲存圖，占用的儲存空間大小只與圖中的邊數有關，而與結點的個數無關。
（×）8.在二叉排序樹中，根結點的值都小於孩子結點的值。
（×）9.如果某種排序演算法不穩定，則該排序方法就沒有實際應用價值。
（×）10.含多於兩棵樹的森林轉換的二叉樹，其根結點一定無右孩子。
二．填空題
1．演算法效率的度量可以分為事先估算法和事後統計法。
2．資料結構按邏輯結構可分為兩大類，它們分別是：線性結構和非線性結構。
3．線性資料結構的結點元素之間存在一對一關係。
4．鍊錶相對於順序表的優點有插入、刪除方便；缺點是儲存密度小 。
5．當棧空時做出棧操作，則產生下溢 。
6．向乙個棧頂指標為top的鏈棧插入乙個新結點*p時，應執行p->next=top；和 top=p；操作。
7．鏈隊列為空時，lq->front->next= null 。
8．設迴圈佇列的頭指標front指向隊頭元素，尾指標rear指向隊尾元素後的乙個空閒元素，佇列的最大空間為maxlen，當rear9．設s="a:/document/"，則"m"字元定位的位置為 8 。
10．串順序儲存非緊湊格式的缺點是： 空間利用率低 。
11．前序為a，b，c且後序為c，b，a的二叉樹共有 4 種。
12．樹內各結點度的最大值稱為樹的度 。
13．圖的遍歷有： 深度優先搜和廣度優先搜等方法。
14．有n條邊的無向圖鄰接矩陣中，1的個數是 _2n____。
15．二叉排序樹中任意結點的關鍵字值小於其右子樹中各結點的關鍵字值。
16．內排序是指整個排序過程，全部在計算機的記憶體中進行。
17．快速排序在最壞情況下的時間複雜度是 o（n2） 排序的一種改進。
18．處理衝突的兩類主要方法是開放定址法和拉鍊法
19．在如圖所示的鍊錶中，若在指標p所在的結點之後插入資料域值為a和b的兩個結點，則可用下列兩個語句：s->next->next=p->next; 和 p->next=s; 來實現該操作。ps
20．已知一棵二叉樹的中序序列為：gdhbeacijf，後序序列為：ghdebjifca。請寫出這棵樹的前序序列： abdghecfij 。
三．選擇題
1．每乙個儲存結點不僅含有乙個資料元素，還包含一組指標，該儲存方式是（ b ）儲存方式
a. 順序b. 鏈式c. 索引d. 雜湊
2．下列演算法的實際複雜度是（ d ）
for (i=0;i for (j=0;ic[i][j]=i+j;
a. o（1b. o（ n） c. o（log2n） d. o（n2）
3．單鏈表的儲存密度（ c ）。
a． 大於1b． 等於1c．小於1d． 不能確定
4．在n個結點的順序表中，演算法的時間複雜度是o (1)的操作是（ a ）。
a． 訪問第i個結點(1<=i<-n)和求第i個結點的直接前驅(2<=i<=n)
b． 在第i個結點之後插入乙個新結點(1<=i<=n)
c． 刪除第i個結點(1<=i<=n)
d． 將n個結點從小到大排序
5．鏈棧與順序棧相比，有乙個比較明顯的優點是 ( a )。
a．通常不會出現棧滿的現象 b．插入操作方便
c．不會出現棧空的現象d．刪除操作方便
6．經過下列棧的運算後，x的值是（ b ）。
initstack(s) (初始化棧);push(s,a);pop(s,x);push(s,b);pop(s,x);
a．ab．bc．1d．0
7．迴圈佇列sq隊滿的條件是( b )。
a．sq->rear==sq->frontb．(sq->rear+1)%maxlen==sq->front
c．sq->rear==0d．sq->front==0
8．佇列q，經過下列運算後，再執行qempty(q) 的值是（ c ）。
initqueue(q) (初始化佇列);inqueue(q,a); inqueue(q,b);outqueue(q,x);
readfront(q,x);
a．ab．bc．0d．1
9．c語言中用於得到字串長度的函式是（ c ）。
a．strcpy b．strcmpc．strlen d．strcat
10．若字串"abcdefg"採用鏈式儲存，假設每個指標占用2個位元組，若希望儲存密度50％，則每個結點應儲存( a )個字元。
a．2b．3c．4d．5
11．下列4棵樹中，（ b ）不是完全二叉樹。
abcd．
12．任何一棵二叉樹的葉結點在前序、中序、後序遍歷序列中的相對次序（ a ）。
a．不發生改變 b．發生改變 c．不能確定d．以上都不對
13．在圖的表示法中，表示形式唯一的是（ a ）。
a．鄰接矩陣表示法b．鄰接表表示法
c．逆鄰接表表示法d．鄰接表和逆鄰接表表示法
14．對於乙個具有n個頂點的有向圖的邊數最多有（ b ）。
a．nb．n（n-1c．n（n-1）/2 d．2n
15．雜湊查詢是由鍵值的（ b ）確定雜湊表中的位置，來進行儲存或查詢。
a．本身b. 雜湊函式 c．相反數d．平方
16．有乙個長度為12的有序表，按二分查詢法對該錶進行查詢，在表內各元素等概率情況下查詢成功所需的平均比較次數為（ b ）。
a．35／12b．37／12c．39／12d．43／12
17．不穩定的排序方法是指在排序前後，關鍵字值相等的不同記錄間的前後相對位置（ c ）。
a．保持相反 b．保持不變 c．不定d．無關
18．用直接插入排序法對下面的四個序列進行由小到大的排序，元素比較次數最少的是（ b ）。
a，94，32，40，90，80，46，21，69 b．21，32，46，40，80，69，90，94
c．32，40，21，46，69，94，90，80 d．90，69，80，46，21，32，94，40
19．對有14個元素的有序表a[1..14]作二分查詢，查詢元素a[4]時的被比較元素依次為：
a．a[1]，a[2]，a[3]，a[4b．a[1]，a[14]，a[7]，a[4]
c．a[7]，a[3]，a[5]，a[4d．a[7]，a[5]，a[3]，a[4]
20．若圖g中（ a ）都有方向，則稱g為有向圖。
a．每條邊 b．部分邊c．一條邊d．每個頂點
四．應用題
1． 設有乙個棧，元素進棧的次序為：a，b，c，d，e，用i表示進棧操作，o表示出棧操作，寫出下列出棧的操作序列。
（1）c，b，a，d，e
（2）a，c，b，e，d
解：（1）iiioooioio
（2）ioiiooiioo
2． 把下列一般樹轉換為二叉樹
解：3． 給定如圖所示二叉樹t，請畫出與其對應的中序線索二叉樹。【2000計算機研究生考題】
解： （1） 中序遍歷序列：55 40 25 60 28 08 33 54
（2） 中序線索二叉樹：
4． 已知乙個無向圖有6個結點，9條邊，這9條邊依次為（0，1），（0，2），（0，4），（0，5），（1，2），（2，3），（2，4），（3，4），（4，5）。試畫出該無向圖，並從頂點0出發，分別寫出按深度優先搜尋和廣度優先搜尋進行遍歷的結點序列。
解：從頂點0出發的深度優先搜尋遍歷的結點序列：0 1 2 3 4 5 （不唯一）。
從頂點0出發的廣度優先搜尋遍歷的結點序列：0 1 2 4 5 3 （不唯一）。
5． 畫出對長度為10的有序表進行折半查詢的判定樹，並求其等概率時查詢成功的平均查詢長度。
解：長度為10的判定樹：
1次能找到
2次能找到
《資料結構》模擬試卷一
a.98b.99c.50d.48 8 下列序列中，a 是執行第一趟快速排序後得到的序列 排序的關鍵字型別是字串 a.da ax eb de bb ff ha gc b.cd eb ax da ff ha gc bb c.gc ax eb cd bb ff da ha d.ax bb cd da ff...
資料結構C 模擬試卷
第 1 題.復合題共計 10 分 選擇題 第 1.1 題.客觀單選題 1 分 線性表的邏輯順序和儲存順序總是一致的，這種說法 正確不正確 有些情況可能是正確的 取決於機器實現 第 1.2 題.客觀單選題 1 分 乙個順序表第1個元素的儲存位址是100，每個元素占用位元組數為5，第5個元素的起始位址是...
《資料結構》課程模擬試卷2019
學號姓名教師得分 一 填空 30分左右 1.由85個節點構成的完全二叉樹，其深度為其中第6層的節點數為 個。2 關鍵字1，2，3，5，13，18，27，對其進行折半查詢，那麼查詢關鍵字13的比較次數是 次。3 有一棵二叉樹，它的中序遍歷為 4，5，2，1，6,3，前序遍歷為 1，2，4，5，3，6那...