第 1 題.( 復合題共計 10 分) 選擇題
第 1.1 題.(客觀單選題 1 分) 線性表的邏輯順序和儲存順序總是一致的，這種說法：
正確不正確
有些情況可能是正確的
取決於機器實現
第 1.2 題.(客觀單選題 1 分) 乙個順序表第1個元素的儲存位址是100，每個元素占用位元組數為5，第5個元素的起始位址是：
105110
115120
第 1.3 題.(客觀單選題 1 分)
準備雜湊儲存的資料依次為｛32，75，63，48，94，25，46，18，70｝，雜湊表的長度是12，用除留餘法建構函式。
（1）能夠獲得最好雜湊效果的雜湊函式是怎樣的？
（2）是否會發生衝突的情況？
（3）用線性探測法處理衝突問題，請計算等概率情況下的查詢成功的平均查詢長度。
h(key)=key%12
不會發生衝突
平均查詢長度 10/12
h(key)=key%11
會發生衝突
平均查詢長度 10/9
h(key)=key%11
不會發生衝突
平均查詢長度 9/9
h(key)=key%9
會發生衝突
平均查詢長度 14/9
第 1.4 題.(客觀單選題 1 分) 遞迴演算法的實現通常需要使用：佇列棧
鍊錶樹第 1.5 題.(客觀單選題 1 分)
二叉樹的前序遍歷序列是abdecf，中序遍歷序列是dbeacf，該二叉樹經過下列函式處理後，輸出結果是：
template
void binarytree process(btnode* t,void (*visit)(const elemtype &e)) }
debafc
acbfed
dbeafc
debfca
第 1.6 題.(客觀單選題 1 分) 樹最適合用來表示：
有序資料元素
無序資料元素
元素之間有分支層次關係的資料
元素之間無聯絡的資料
第 1.7 題.(客觀單選題 1 分) 乙個有n個頂點的無向圖最多有（ ）條邊：
n(n-1)/2
n(n-1)n2n
第 1.8 題.(客觀單選題 1 分) 快速排序的時間複雜度是o（nlog2n），這樣的速度是以（ ）為代價的：
提高cpu速度
增加儲存量
提高演算法的複雜性
以上三個選項都是正確的
第 1.9 題.(客觀單選題 1 分)
一組資料的邏輯結構用二元組表示如下，這是乙個二叉樹結構，把該二叉樹轉換為樹，得到的先根遍歷和後根遍歷序列是：
b=(k，r)；
k=；r=；
對應樹的
先根遍歷是abcdefghi
後根遍歷是dcbfihgea
dcbfihgea對應樹的
先根遍歷是bcdafehig
後根遍歷是dcbfihgea
對應樹先根遍歷是abcdefghi
後根遍歷是bcdafehig
對應樹先根遍歷是abecfgdhi
後根遍歷是bcdafehig
第 1.10 題.(客觀單選題 1 分)
以下列序列構造二叉排序樹，與用其它3個序列所構造的結果不同的是（ c）。
a.(100,80,90,60,120,110,130)
b.(100,120,110,130,80,60,90)
c.(100,60,80,90,120,110,130)
d.(100,80,60,90,120,130,110)ab
cd第 2 題.( 復合題共計 16 分) 填空題
第 2.1 題.(主觀題 2 分) 在順序儲存的線性結構中插入或刪除乙個元素，需要進行元素的移動，具體移動的元素個數與 （1） 有關。
參***
（1）被操作元素的位置
第 2.2 題.(主觀題 2 分) 在單鏈表中，出了表頭結點外，任一結點的儲存位置由 （2） 指示。
參***
（2）前驅結點的指標域
第 2.3 題.(主觀題 2 分) 已知l為一單鏈表，p指向表中某個結點，使p指向其後繼結點的語句為 （3） 。
參***
（3）p = p->next;
第 2.4 題.(主觀題 2 分) 限定只能在一端進行元素插入、在另一端進行元素刪除操作的線性結構稱為 （4） 。
參***
（4）佇列
第 2.5 題.(主觀題 2 分) 使用快速排序方法對n個元素進行排序，其演算法時間複雜性為（用大o表示法） （5） 。
參***
（5）o(nlogn)
第 2.6 題.(主觀題 2 分) 使用二分法對乙個線性結構進行查詢，該線性結構必須滿足兩個條件：
① （6） 和② （7） 。
參***
（6）元素順序儲存（7）元素有序存放
第 2.7 題.(主觀題 2 分)
畫出長度為13的有序表、使用折半查詢方法得到的判定樹，該樹有多少層？平均查詢長度是多少？
參***
判定樹圖，略
4層。平均查詢長度 = 4*6+4*4+2*2+1*1 = 45
第 2.8 題.(主觀題 2 分) 向量v中儲存整數序列：
56，12，75，29，37，63，42，94，現對其進行快速排序，樞軸元素取為56，則進行一趟劃分後的序列為 （9） ，完成最終的排序共需進行 （10） 次劃分操作。
參***
42，12，37，29，56，63，75，94
5次第 3 題.( 復合題共計 5 分) 簡答題
第 3.1 題.(主觀題 5 分) 一組關鍵碼，用雜湊儲存方式依次存入下表中，雜湊函式h(key)=key%7，請填寫儲存結果。
設每個關鍵碼的查詢概率相等，計算該雜湊結構的平均查詢長度。
參***
23，54，10，43，16，35 h(key)=key%7 檢索長度8/6=1.33
第 4 題.( 復合題共計 35 分) 演算法設計題
第 4.1 題.(主觀題 5 分)
帶頭結點的單鏈表如課本定義。請寫出刪除第i個結點的演算法，刪除結點的值儲存在變數e中，如果第i個結點不存在，則返回false表示刪除不成功，否則返回true表示刪除成功。
參考函式原型：
template
bool linklist::delete(elemtype &e,int i);
參***
// 在單鏈表中刪除第i個資料元素並用資料變數e返回其值（i的合法值為1≤i≤len）
template
bool linklist::delete(elemtype &e,int i)
q=p->next;
p->next=q->next; // 刪除q結點
if (q == tail)
tail = p;
e=q->data;
delete q; //釋放空間
--len; // 表長減1
return true; //時間複雜度為o(n)
} 第 4.2 題.(主觀題 5 分)
帶頭結點的單鏈表如課本定義。請寫出輸出整個單鏈表資料的演算法。
參考函式原型：
template
void linklist ::tr**erse(void(*visit)(const elemtype &e)) const ；
參***
// 依序對單鏈表中的每個資料元素呼叫函式visit()一次且僅一次
template void linklist
::tr**erse(void(*visit)(const elemtype &e)) const
}第 4.3 題.(主觀題 5 分)
請寫出直接插入排序演算法。排序資料儲存在陣列data中，長度為n。
參考函式原型如下：
template
void insertsort(elemtype data, int n) ；
參***
// 直接插入排序,陣列data用於存放待排序元素，n為待排序元素個數
template
void insertsort(elemtype data, int n)
}第 4.4 題.(主觀題 5 分)
《資料結構》模擬試卷一
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
成都東軟資訊科技學院 200 200 學年第學期期末試題 資料結構 c語言 本課程為閉卷考試，試卷共六道大題，試卷滿分100分，考試時間120分鐘。一 選擇題 10 2分 共10小題，請將答案填入題中的括號中，每小題只有乙個正確答案，錯選或不選均不給分。1 組成資料的基本單位是 資料項資料型別 c ...
資料結構模擬考試試卷
一 判斷題 下列各題，正確的請在前面的括號內打 錯誤的打 1.程式和演算法原則上沒有區別，所以在討論資料結構時可以通用。2.在單鏈表中，元素的儲存位置用指標聯絡，所以可以從頭結點開始查詢任何乙個元素。3.乙個棧的輸入序列為 a，b，c，d，可以得到輸出序列 c，a，b，d。4.佇列是一種 先進先出 ...