西北大學2014年數據結構試卷一、簡答問題：（每小題4分，共16分）四類數據結構線性結構與非線性結構有何差別？簡述算法的定義與特性。設有1000個無序元素，僅要求找出前10個最小元素，在下列排序方法中（歸并排序、基數排序、快速排序、堆排序、插入排序）哪一種方法最好，為什么？二、判斷正誤：（每小題1分，共5分）正確在（）內打√，否則打r。（）二叉排序樹或是一棵空樹，或是具有下列性質的二叉樹：若它的左子樹非空，則根結點的值大于其左孩子的值，若它的右子樹非空，則根結點的值大于其右孩子的值。（）索引順序表的特點是塊內可無序，塊間要有序。（）子串是主串中任意個連續字符組成的序列。（）線性結構只能用順序結構存放，非線性結構只能用鏈表存放。（）快速排序的樞軸元素可以任意選定。三、單項選擇題：(每小題1分，共4分)1．棧S最多能容納4個元素。現有6個元素按A、B、C、D、E、F的順序進棧,問下列哪一個序列是可能的出棧序列?A)E、D、C、B、A、FB)B、C、E、F、A、DC)C、B、E、D、A、FD)A、D、F、E、B、C2．將一棵有100個結點的完全二叉樹從根這一層開始，每一層從左到右依次對結點進行編號，根結點編號為1，則編號為49的結點的左孩子的編號為：A、98 B、99 C、50 D、483.對下列關鍵字序列用快速排序法進行排序時，速度最快的情形是：A）{21、25、5、17、9、23、30}B）{25、23、30、17、21、5、9}B）{21、9、17、30、25、23、5}D）{5、9、17、21、23、25、30}4.設森林F中有三棵樹，第一、第二和第三棵樹的結點個數分別為M1、M2和M3。與森林F對應的二叉樹根結點的右子樹上的結點個數是：A）M1B）M1+M2C）M3D）M2+M3四、填空題：(每小題2分,共20分)設一哈希表表長M為100，用除留余數法構造哈希函數，即H（K）=KMODP（P<=M）,為使函數具有較好性能，P應選N個結點的二叉樹采用二叉鏈表存放，共有空鏈域個數為單鏈表與多重鏈表的區別是在各種查找方法中，平均查找長度與結點個數無關的是深度為6（根層次為1）的二叉樹至多有個結點。已知二維數組A[20][10]采用行序為主方式存儲,每個元素占2個存儲單元,并且A[10][5]的存儲地址是1000,則A[18][9]的存儲地址是在一個單鏈表中p所指結點之后插入s所指結點時,應執行s->next=和p->next=的操作.8．廣義表((a,b),c,d)的表頭是,表尾是9．循環單鏈表LA中，指針P所指結點為表尾結點的條件是10．在一個待排序的序列中，只有很少量元素不在自己最終的正確位置上，但離他們的正確位置都不遠，則使用排序方法最好。五、構造題：（每小題5分，共25分）已知一棵二叉樹，其中序序列DBCAFGE，后序序列DCBGFEA，構造該二叉樹。設哈希表長度為11，哈希函數H（K）=（K的第一字母在字母表中的序號）MOD11，若輸入順序為（D，BA，TN，M，CI，I，K，X，TA），處理沖突方法為線性探測再散列或鏈地址法，要求構造哈希表，并求出等概率情況下查找成功平均查找長度。有一組關鍵字{50，52，85，22，96，17，36，55}，請用快速排序，寫出第一趟排序結果。已知葉子結點值2，3，5，6，9，11，構造哈夫曼樹，計算其帶權路徑長度。畫出8個結點的折半判定樹。六、算法設計題：（每小題15分，共30分）（僅要求給出子程序）1．編寫算法，判斷帶頭結點的雙向循環鏈表L是否對稱。（15分）對稱是指：設各元素值a1,a2,...,an,則有ai=an-i+1，即指：a1=an，a2=an-1。。。。。。。結點結構為：priordatanext二叉排序樹T用二叉鏈表表示，其中各元素均不相同。寫出遞歸算法，按遞減順序打印各元素的值。（10分）寫出完成上述要求的非遞歸算法。（5分）試卷參考答案與評分標準

一、簡答問題：（每小題4分，共16分）1．

集合結構、線性結構、樹形結構、網狀結構2．

線性結構的前驅與后繼之間為一對一關系，非線性結構的前驅與后繼之間通常為一對多或多對多關系。3．

解決特定問題的有限指令序列。有限性、確定性、可行性、有0個或多個輸入數據、有1個或多個輸出結果。4．

堆排序。因為一趟堆排序排定一個元素，只需進行前10趟堆排序就可以了。其它排序方法均需進行完全排序。二、判斷正誤：（每小題1分，共5分）正確在（

）內打√，否則打。1.（）

2.（√）

3.（√）

4.（）

5.（√）三、單項選擇題：(每小題1分，共4分)1．C)

2．A)

3.

A)

4.

D)四、填空題：(每小題2分,共20分)1．

97

2.

n+1

3.鏈域數目不同

4.哈希查找法

5.26–1

6.1168

7.p->next

、

s

8.(a,b)

、

(c,d)9.P->next==LA

10.直接插入五、構造題：（每小題5分，共25分）1．

2．

012345678910KTABAMDCIX

TNIASL=20/9

012345678910

ASL=15/93．

{36，17，22，50，96，85，52，55}4．

WPL=11×2+6×2+9×2+5×3+2×4+3×4

=87[注]：哈夫曼樹的左右子樹可以互換。5．

[注]：如果求中點時采用向上取整，則二叉樹的形態為左子樹偏長。

六、算法設計題：（每小題15分，共30分）

（僅要求給出子程序）1．[解答]：intjudge(DLinkListL){p=L->next;

q=L->prior;while(p!=q)

{if(p->data!=q->data)return0;if(p->next==q)return1;p=p->next;q=q->prior;

}return1;}[注]：可以不用返回值，而用打印信息。2．

[解答]：（1）voidprint_1(BiTreeT){if(T!=NULL)

{print_1(T->RChild);

printf(“%c”,T->data);

print_1(T->LChild);

}}（2）void

Print_2（BiTreeT）{InitStack(&S);p=T;while(p!=NULL||!IsEmp