武漢科技大學856數(shù)據(jù)結構（C語言版）歷年考研真題匯編

目錄

2014年武漢科技大學856數(shù)據(jù)結構（C語言版）A卷考研真題

2013年武漢科技大學856數(shù)據(jù)結構（C語言版）A卷考研真題

2013年武漢科技大學856數(shù)據(jù)結構（C語言版）B卷考研真題

2014年武漢科技大學856數(shù)據(jù)結構（C語言

版）A卷考研真題

考試科目代碼及科目名稱：856數(shù)據(jù)結構(C語言版)

答題內(nèi)容寫在答題紙上，寫在試卷或草稿紙上一律無效考完后試題

隨答題紙交回。

考試時間3小時，總分值150分。

一、選擇題（10小題，每題2分，共20分）

1．算法分析的主要內(nèi)容是（）。

A．正確性

B．可讀性和穩(wěn)定性

C．簡單性

D．空間復雜性和時間復雜性

2．線性表若采用鏈式存儲結構時，要求內(nèi)存中可用存儲單元的地

址（）。

A．必須是連續(xù)的

B．部分地址必須是連續(xù)的

C．一定是不連續(xù)的

D．連續(xù)或不連續(xù)都可以

3．設有6個元素按1、2、3、4、5、6的順序進棧，下列不合法的出

棧序列是（）。

A．234165

B．324651

C．431256

D．546321

4．設有二維數(shù)組A[1..12，1..10]，其每個元素占4個字節(jié)，數(shù)據(jù)按

行優(yōu)先順序存儲，第一個元素的存儲地址為100，那么元素A[5，5]的存

儲地址為（）。

A．76

B．176

C．276

D．376

5．已知一棵二叉樹的先序序列為ABDGCFK，中序序列為

DGBAFCK，則后序序列為（）。

A．ACFKDBG

B．GDBFKCA

C．KCFAGDB

D．ABCDFKG

6．在二叉樹結點的先序，中序和后序序列中，所有葉子結點的先

后順序（）。

A．都不相同

B．完全相同

C．先序和中序相同，而與后序不同

D．中序和后序相同，而與先序不同

7．圖的深度優(yōu)先遍歷類似于二叉樹的（）。

A．先序遍歷

B．中序遍歷

C．后序遍歷

D．層次遍歷

8．下面（）算法適合構造一個稠密圖G的最小生成樹。

A．Prim算法

B．Kruskal算法

C．Floyd算法

D．DIjkstra算法

9．對關鍵碼{46，79，56，38，40，84}采用堆排序，則初始化堆

(小堆)后最后一個元素是（）。

A．84

B．46

C．56

D．38

10．在Hash函數(shù)H(k)=kMODm中，一般來講m應?。ǎ?/p>

A．奇數(shù)

B．偶數(shù)

C．素數(shù)

D．充分大的數(shù)

二、填空題（10小題，每題2分，共20分）

1．在單向鏈表某P結點之后插入S結點的操作是（）。

2．線性表Ｌ用數(shù)組表示，假定刪除表中任一元素的概率相同，則

刪除一個元素平均需要移動元素的個數(shù)是（）。

3．一個棧的輸入序列是：1，2，3則不可能的棧輸出序列是

（）。

4．一棵二叉樹高度為h，所有結點的度或為0，或為2，則該二叉樹

最少有（）結點。

5．在完全二叉樹中，編號為i和j的兩個結點處于同一層的條件是

（）。

6．若無向圖G=（V，E），其中V={a，b，c，d，e}E={(a，

B．，(a，D．，(a，C．，(d，C．，(b，e)}，現(xiàn)采用圖的（）遍歷

方法從頂點a開始遍歷圖，得到的序列為abecd。

7．求最短路徑的Dijkstra算法的時間復雜度為（）。

8．假定有k個關鍵字互為同義詞，若用線性探測再散列法把這k個

關鍵字存入散列表中，至少要進行（）次探測。

9．設在已排序的線性表中共有元素n個，若用二分法查找表中的元

素。若查找成功，至少要比較（）次

10．對一組記錄（54，38，96，23，15，2，60，45，83）進行直

接插入排序，當把第7個記錄60插入到有序表時，為尋找插入位置需比

較（）次。

三、綜合應用題（7小題，每題10分，共70分）

1．已知A[1..N]是一棵順序存儲的完全二叉樹，如何求出A[i]和A[j]

的最近的共同祖先？

2．請給出一棵哈夫曼樹中分支數(shù)B與葉子節(jié)點數(shù)n0所滿足關系式，

并證明你的結論。

3．下面的排序算法的思想是：第一趟比較將最小的元素放在r[0]

中，最大的元素放在r[n-1]中，第二趟比較將次小的放在r[1]中，將次大

的放在r[n-2]中，…，依次下去，直到待排序列為遞增序。（注：<-->

代表兩個變量的數(shù)據(jù)交換）。

voidsort(SqList&r，intn)

{i=0;

while((1))

{min=max=i;

for(j=i+1;(2);++j)

{if((3))min=j;elseif(r[j].key>r[max].key)max=j;}

if((4))r[min]<-->r[i];

if(max!=n-i-1)

{if((5))r[min]<-->r[n-i-1];elser[max]<-->r[n-i-1];}

i++;

}

}//sort

4．如下圖所示的AOE網(wǎng)

（1）寫出所有的拓撲序列

（2）求各頂點代表的事件的最早發(fā)生時間和最遲發(fā)生時間

（3）求各條弧代表的活動的最早開始時間和最遲開始時間

（4）給出其關鍵路徑

5．設哈希函數(shù)H（K）=3Kmod11，哈希地址空間為0～10，對關

鍵字序列（32，13，49，24，38，21，4，10），按下述兩種解決沖突

的方法構造哈希表，并分別求出等概率下查找成功時和查找失敗時的平

均查找長度ASLsucc和ASLunsucc。

（1）線性探測法（2）鏈地址法

6．全國有10000人參加競賽，只錄取成績優(yōu)異的前10名，并將他們

從高分到低分輸出。而對落選的其他考生，不需排出名次，問此種情況

下，用何種排序方法速度最快？為什么？

7．假定對有序表(3，4，5，17，24，35，40，54，58，72，80，

123)進行折半查找，試回答問題：

（1）畫出描述折半查找過程的判定樹；

（2）若查找元素54，需依次與那些元素比較?

（3）若查找元素20，需依次與那些元素比較?

（4）分別求等概率情況下查找成功和不成功時的平均查找長度。

四、算法設計與編程（4小題，每題10分，共40分）

1．設有一頭指針為L的帶有表頭結點的非循環(huán)雙向鏈表，其每個結

點中除有pred（前驅(qū)指針），data（數(shù)據(jù)）和next（后繼指針）域外，還

有一個訪問頻度域freq。在鏈表被啟用前，其值均初始化為零。每當在

鏈表中進行一次Locate(L，x)運算時，令元素值為x的結點中freq域的值

增1，并使此鏈表中結點保持按訪問頻度非增（遞減）的順序排列，同

時最近訪問的結點排在頻度相同的結點的最后，以便使頻繁訪問的結點

總是靠近表頭。試編寫符合上述要求的Locate(L，x)運算的算法，該運

算為函數(shù)過程，返回找到結點的地址，類型為指針型。

2．已知二叉樹用下面的順序存儲結構，寫出先序遍歷該二叉樹的

算法。

1234567

dataABCDEFG

Lc2400080

Rc3560790

3．編寫在后序線索二叉樹中求任一結點直接前驅(qū)的算法（結點結

構包括數(shù)據(jù)域data、左孩子域left、右孩子域right、左標志域ltag和右標

志域rtag，標志域為0表示沒有孩子，孩子域為線索）。

4．有n個記錄存儲在帶頭結點的雙向鏈表中，現(xiàn)用雙向冒泡排序法

對其按上升序進行排序，請寫出這種排序的算法。（注：雙向冒泡排序

即相鄰兩趟排序向相反方向冒泡）。

2013年武漢科技大學856數(shù)據(jù)結構（C語言

版）A卷考研真題

考試科目代碼及科目名稱：856數(shù)據(jù)結構(C語言版)

答題內(nèi)容寫在答題紙上，寫在試卷或草稿紙上一律無效考完后試題

隨答題紙交回。

考試時間3小時，總分值150分。

一、選擇題（10小題，每題2分，共20分）

1．有六個元素6，5，4，3，2，1的順序進棧，問下列哪一個不是

合法的出棧序列？（）

A．543612

B．453126

C．346521

D．234156

2．對有序表A[1..14]做二分查找，查找元素A[4]前被比較元素依次

為（）。

A．A[1]，A[2]，A[3]

B．A[1]，A[14]，A[7]

C．A[7]，A[3]，A[5]

D．A[7]，A[5]，A[3]

3．下面幾個符號串編碼集合中，不是前綴編碼的是（）。

A．{0，10，110，1111}

B．{11，10，001，101，0001}

C．{00，010，0110，1000}

D．{b，c，aa，ac，aba，abb，abc}

4．適用于折半查找的表的存儲方式及元素排列要求為（）。

A．鏈接方式存儲，元素無序

B．鏈接方式存儲，元素有序

C．順序方式存儲，元素無序

D．順序方式存儲，元素有序

5．最大容量為n的循環(huán)隊列，隊尾指針是rear，隊頭是front，則隊

空的條件是（）。

A．(rear+1)MODn=front

B．rear=front

C．rear+1=front

D．(rear-l)MODn=front

6．將兩個各有n個元素的有序表歸并成一個有序表，最少的比較次

數(shù)是（）

A．n-1

B．n

C．2n-1

D．2n

7．具有n個頂點、e條邊的無向圖的鄰接矩陣中，零元素的個數(shù)為

（）

A．e

B．2e

C．n2-2e

D．n2-1

8．某索引順序表共有元素395個，平均分成5塊。若先對索引表采

用順序查找，再對塊中元素進行順序查找，則在等概率情況下，分塊查

找成功的平均查找長度是（）

A．43

B．79

C．198

D．200

9．要以O（nlogn）時間復雜度進行穩(wěn)定的排序，可用的排序方法

是（）

A．歸并排序

B．快速排序

C．堆排序

D．冒泡排序

10．設哈希表長為14，哈希函數(shù)是H(key)=key%11，表中已有數(shù)據(jù)

的關鍵字為15，38，61，84共四個，現(xiàn)要將關鍵字為49的結點加到表

中，用二次探測再散列法解決沖突，則放入的位置是（）

A．8

B．3

C．5

D．9

二、填空題（10小題，每題2分，共20分）

1．下面程序段的時間復雜度為（）。(n>1)

sum=1；

for(i=0;sum<n;i++)sum+=1;

2．數(shù)據(jù)結構由數(shù)據(jù)的邏輯結構、存儲結構和數(shù)據(jù)的（）三部

分組成。

3．長度為11的有序表，采用折半查找，在等概率情況下查找成功

的平均查找長度為（）。

4．使用一個100個元素的數(shù)組存儲循環(huán)隊列，如果采取少用一個元

素空間的方法來區(qū)別循環(huán)隊列的隊空和隊滿，約定隊頭指針front等于隊

尾指針rear時表示隊空。若為front=8，rear=6，則隊列中的元素個數(shù)為

（）。

5．將有關二叉樹的概念推廣到三叉樹，一顆有244個結點的完全三

叉樹的深度為（）。

6．設一顆完全二叉樹共有101個結點，它有（）葉子結點。

7．出棧操作時應判別棧是否（）。

8．帶頭結點的單鏈表Head為空的條件是（）。

9．快速排序的時間復雜度為（）。

10．某二叉樹的先序和后序序列正好相反，則該二叉樹一定是

（）的二叉樹。

三、判斷題（10小題，每題2分，共20分）

1．數(shù)據(jù)元素是數(shù)據(jù)的最小單位。（）

2．折半查找方法要求待查表必須是順序存儲結構的有序表。

（）

3．當兩個字符出現(xiàn)的頻率相同時，則其哈夫曼編碼也相同。

（）

4．如果某種排序算法是不穩(wěn)定的，則該算法是沒有實際意義的。

（）

5．將一棵樹轉換為二叉樹后，根結點沒有右子樹。（）

6．串既可采用順序存儲，也可采用鏈式存儲。（）

7．一個廣義表的表尾總是一個廣義表。（）

8．完全二叉樹的葉子結點只可能在層次最大的一層上出現(xiàn)。

（）

9．順序存儲結構的主要缺點是不利于插入或刪除操作。（）

10．算法是對特點問題求解步驟的一種描述，因此它可以沒有輸入

和輸出。（）

四、綜合應用題（6小題，每題10分，共60分）

1．下表列出了某工序之間的優(yōu)先關系和各工序所需時間。要求：

（1）畫出AOE網(wǎng)

（2）列出各事件的最早開始時間、最遲開始時間

（3）找出關鍵路徑并指明完成該工程所需最短時間。

工序代號所需時間前驅(qū)工序工序代號所需時間前驅(qū)工序

a16無a79a4，a5

a24無a87a4，a5

a35無a94a2，a6

a41a1a102a7

a51a2a114a8，a9

a62a3a123a11

2．若一棵完全二叉樹中葉子結點的個數(shù)為n，且最底層結點數(shù)

≧2，則此二叉樹的深度H=？

3．已知一顆二叉樹的中序序列為BJFKDGAELIMHC，后序序列為

JKFGDBLMIHECA，畫出該二叉樹的先序線索二叉樹。

4．在n×n矩陣A中，所有下標值滿足關系式i+j＜n+l的元素aij(1≤i，

j≤n)的值均為0，現(xiàn)將A中其它元素按行優(yōu)先順序依次存儲到長一維數(shù)組

sa中，其中元素a1，n存儲在sa［0］。

(1)設n=10，元素a4，9存儲在sa［p］，寫出下標p的值；

(2)設元素ai，j存儲在sa［k］中，寫出由i，j和n計算k的一般公式。

5．假定對有序表(1，9，15，21，24，35，52，54，61，65，97)進

行折半查找，試回答問題：

（1）畫出描述折半查找過程的判定樹；

（2）分別求等概率情況下查找成功和不成功時的平均查找長度。

6．已知待排記錄的關鍵字序列為{25，96，11，63，57，78，

44}，請回答下列問題：

(1)寫出堆排序的初始堆（大根堆）關鍵字序列；

寫出堆排序1趟以后（交換與調(diào)整之后）的關鍵字序列；

(2)寫出快速排序1趟以后的關鍵字序列；

寫出快速排序2趟以后的關鍵字序列。

(3)寫出冒泡排序1趟以后的關鍵字序列；

五、算法設計與編程（3小題，每題10分，共30分）

1．函數(shù)digit(n，k)的功能是求正整數(shù)n中從右端開始的第k(≥1)個數(shù)

字的值（k從1開始），如果k超過了n的位數(shù)，則函數(shù)返回－1；否則返

回n中第k個數(shù)字。

例如：digit(264539，3)=5

digit(7622，5)=-1

要求分別用遞歸和非遞歸設計該函數(shù)。

2．設有一個正整數(shù)序列組成的有序單鏈表（按遞增次序有序，且

允許有相等的整數(shù)存在），試編寫能實現(xiàn)下列功能的算法：（要求用

最少的時間和最小的空間）

⑴確定在序列中比正整數(shù)x大的數(shù)有幾個（相同的數(shù)只計算一

次）。

⑵在單鏈表中將比正整數(shù)x小的數(shù)按遞減次序排列。

⑶將比x大的偶數(shù)從單鏈表中刪除。

3．在二叉樹中查找值為x的結點，請編寫一算法用以打印值為x的

結點的所有祖先，假設值為x的結點不多于1個。

2013年武漢科技大學856數(shù)據(jù)結構（C語言

版）B卷考研真題

考試科目代碼及科目名稱：856數(shù)據(jù)結構(C語言版)

答題內(nèi)容寫在答題紙上，寫在試卷或草稿紙上一律無效考完后試題

隨答題紙交回。

考試時間3小時，總分值50分。

一、選擇題（10小題，每題2分，共20分）

1．指針p1和p2分別指向兩個無頭結點的非空單循環(huán)鏈表中的尾結

點，要將兩個鏈表鏈接成一個新的單循環(huán)鏈表，應執(zhí)行的操作為

（）

A．p1－＞next=p2－＞next;p2－＞next=p1－＞next;

B．p2－＞next=p1－＞next;p1－＞next=p2－＞next;

C．p=p2－＞next;p1－＞next=p;p2－＞next=p1－＞next;

D．p=p1－＞next;p1－＞next=p2－＞next；p2－＞next=p;

2．如果將矩陣An×n的每一列看成一個子表，整個矩陣看成是一個

廣義表L，即

L=((a11，a21，…，an1)，(a12，a22，…，an2)，…，（a1n，a2n，

…，ann）)，并且可以通過求表頭head和求表尾tail的運算求取矩陣中的

每一個元素，則求得a21的運算是（）

A．head(tail(head(L)))

B．head(head(head(L)))

C．tail(head(tail(L)))

D．head(head(tail(L)))

3．若非連通無向圖G含有21條邊，則G的頂點個數(shù)至少為（）

A．7

B．8

C．21

D．22

4．已知有向圖G=(V，E)，其中V={V1，V2，V3，V4}，E=

{<V1，V2>，<V1，V3>，<V2，V3>，<V2，V4>，<V3，V4>}，圖G

的拓撲序列是（）

A．V1，V2，V3，V4

B．V1，V3，V2，V4

C．V1，V3，V4，V2

D．V1，V2，V4，V3

5．在下圖中，從頂點1出發(fā)進行深度優(yōu)先遍歷可得到的序列是

（）

A．1234567

B．1426375

C．1425367

D．1246537

6．以下屬于邏輯結構的是（）。

A．順序表

B．哈希表

C．有序表

D．單鏈表

7．一個棧的入棧序列是a，b，c，d，e，則棧的不可能的輸出序列

是()。

A．edcba

B．decba

C．dceab

D．a(chǎn)bcde

8．具有10個葉結點的二叉樹中有()個度為2的結點。

A．8

B．9

C．10

D．ll

9不帶頭結點的單鏈表head為空的判定條件是()。

A．head==NULL

B．head->next=NULL

C．head->next=head

D．head!=NULL

10．設有下三角矩陣用數(shù)組A[0..10，0..10]表示，按行優(yōu)先順序存

放其非零元素，每個非零元素占2個字節(jié)，存放的基址為100，則元素

A[5，5]的存放地址為（DD）。

A．110

B．120

C．130

D．140

二、填空題（10小題，每題2分，共20分）

1．某二叉樹的先序和中序序列正好一樣，則該二叉樹一定是

（）的二叉樹。

2.N個元素的順序查找的平均查找長度為（）。

3．在做進棧操作時應判別棧是否（）。

4．對n個元素進行起泡排序時，最少的比較次數(shù)是（）。

5．設一棵完全二叉樹共有500個結點，則在該二叉樹中有（）

個度為2的結點。

6．二叉樹的葉子結點n0與度為2的結點數(shù)n2的關系是（）。

7．對于雙向鏈表，在兩個結點之間插入一個新結點需修改的指針

共（）個。

8．向一個棧頂指針為top的鏈棧中插入一個s指針所指結點的操作語

句是（）。

9．用5個權值{3，2，4，5，1}構造的哈夫曼(Huffman)樹的帶權路

徑長度是（）。

10．在有向圖的鄰接矩陣表示中，計算第I個頂點入度的方法是

（）。

三、判斷題（10小題，每題2分，共20分）

1．從循環(huán)單鏈表的任一結點出發(fā)，不一定能找到表中所有結點。

（）

2．快速排序算法是穩(wěn)定的排序，而shell排序是不穩(wěn)定的。

（）

3．在數(shù)據(jù)結構中，數(shù)據(jù)的存儲結構與所使用的計算機無關。

（）

4．棧和隊列的存儲方式，既可以是順序方式，又可以是鏈式方

式。（）

5．內(nèi)排序要求數(shù)據(jù)一定要以順序方式存儲。（）

6．快速排序的速度在所有排序方法中為最快，而且所需附加空間

也最少。（）

7．一顆哈夫曼樹中結點的度要么是0，要么是2。（）

8．數(shù)據(jù)的邏輯結構是指數(shù)據(jù)的各數(shù)據(jù)項之間的邏輯關系。

（）

9．算法的優(yōu)劣與算法描述語言無關，但與所用計算機有關。（

）

10．任何一棵二叉樹中至少有一個結點的度為2。（）

四、綜合應用題（6小題，每題10分，共60分）

1．下表給出了某工程各工序之間的優(yōu)先關系和各工序所需時間。

工序代號所需時間前驅(qū)工序工序代號所需時間前驅(qū)工序

a115無a815a7

a210無a980a5

a350a1，a2a1060a9

a48a2a1115a6

a8，

a515a3，a4a1230