南通大學2022—2023學年期末

《數據結構》考試試卷（B卷）

考試范圍：《數據結構》；滿分：100分；考試時間：120分鐘

院/系：專業：姓名：考號：

題號一二三四五總分

得分

注意事項：

1.答題前填寫好自己的姓名、專業、考號等信息

2.本試題所有答案，應按試題順序寫在答題紙上，不必抄題，寫清題號。寫在試卷上不得

分。

第I卷（選擇題）

評卷人得分

一、單項選擇題：1?10小題。下列每題給出的選項中，只有一

個選項是符合題目要求的。

1.將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時間復雜度為（）

A.O（1）

B.0（n）

C.0（m）

D.0（m+n）

2.在一個長度為n（n>l）的帶頭結點的單鏈表h上，設有尾指針r（指向尾結點），則執

行（）操作與鏈表的長度有關。

A.刪除單鏈表中的第一個元素

B.刪除單鏈表中的最后一個元素

C.在單鏈表第一個元素前插入一個新元素

D.在單鏈表最后一個元素后插入一個新元素

3.下列選項中，在I/O總線的數據線上傳輸的信息包括（）

I.1/0接口中的命令字

11.1/0接口中的狀態字

III.中斷類型號

A.僅I、II

B.僅I、III

C.僅II、III

D.I、II、III

4.已知兩個長度分別為m和n的升序鏈表，若將它們合并為一個長度為m+n的降序鏈

表，則最壞情況下的時間復雜度是()

A.O(n)

B.O(m*n)

C.O(min(m,n))

D.O(max(m,n))

5.內部異常(內中斷)可分為故障(fault)＞陷阱(trap)和終止(abort)三類。下列有

關內部異常的敘述中，錯誤的()

A.內部異常的產生與當前執行指令相關

B.內部異常的檢測由CPU內部邏輯實現

C.內部異常的響應發生在指令執行過程中

D.內部異常處理后返回到發生異常的指令繼續執行

6.已知一個線性表為(38,25,74,63,52,48),假定采用H(K)=Kmod7計算散

列地址進行散列存儲，若利用線性探測的開放定址法處理沖突，則在該散列表上進行查找

的平均查找長度為()；若利用鏈地址法處理沖突，則在該散列上進行查找的平均查

找長度為()

A.1.5,1

B.1.7,3/2

C.2,4/3

D.2.3,7/6

7.通過POP3協議接收郵件時，使用的傳輸層服務類型是()

A.無連接不可靠的數據傳輸服務

B.無連接可靠的數據傳輸服務

C.有連接不可靠的數據傳輸服務

D.有連接可靠的數據傳輸服務

8.下列選項中，不能構成折半查找中關鍵字比較序列的是()

A.500,200,450,180

B.500,450,200,180

C.180,500,200,450

D.180,200,500,450

9.在雙向鏈表存儲結構中，刪除p所指的結點時須修改指針(）O

A.p->prior->next=p->next;p->next->prior=p->prior;

B.p->prior=p->prior->prior;p->prior->next=p;（刪Ip的前趨）

C.p->next->prior=p;p->next=p->next->next;

D.p->next=p->prior->prior;p->prior=p->next->next;

10.下列有關浮點數加減運算的敘述中，正確的是（）

1.對階操作不會引起階碼上溢或下溢

II.右規和尾數舍入都可能引起階碼上溢

III.左規時可能引起階碼下溢

IV.尾數溢出時結果不一定溢出

A.僅II、ni

B.僅I、II、IV

C.僅I、HRIV

D.I、II、III、IV

第n卷(非選擇題)

評卷人得分

二、填空題：11?15小題。請將答案寫在答題紙指定位置上。

11.所謂算法(Algorithm)是對特定問題求解步驟的一種描述，它是指令的其中每個指令

表示一個或多個操作。算法的五個重要特性是、、、

和O

12.是數據不可分割的最小單元，是具有獨立含義的最小標識單位。例如構成一

個數據元素的字段、域、屬性等都可稱之為。

13.給定一組數據6,2,7,10,3,12｝以它構造一棵哈夫曼樹，則樹高為,帶權

路徑長度WPL的值為0

14.在哈希函數H(key)=key%p中，p值最好取。

15.n個頂點的連通圖至少有條邊。

評卷人得分

三、判斷題：16?25小題。請將答案寫在答題紙指定位置上。

16.完全二叉樹一定存在度為1的結點。()

17.有n個數順序(依次)入棧,出棧序列有Cn種，Cn=[l/(n+1)]*(2n)!/[(n!)*

(n!)]□()

18.數據的邏輯結構是指各元素之間的邏輯關系，是根據用戶需要而建立的。()

19.二叉排序樹刪除一個結點后，仍是二叉排序樹。()

20.若輸入序列為1,2,3,4,5,6,則通過一個棧可以輸出序列1,5,4,6,2,3。

()

21.棧是實現過程和函數等子程序所必需的結構。()

22.拓撲排序的有向圖中，最多存在一條環路。()

23.哈希函數越復雜越好，因為這樣隨機性好，沖突概率小。()

24.若一棵二叉樹中的結點均無右孩子，則該二叉樹的中根遍歷和后根遍歷序列正好相

同。()

25.二叉樹中每個結點的兩棵子樹的高度差等于1。()

評卷人得分

----------------四、程序填空：26?27小題。請將答案寫在答題紙指定位置上。

26.完善下面算法。

后綴表達式求值，表達式13/25+61的后綴表達式格式為：13,25/61,+

FUNCcompute(a):real；后綴表達式存儲在數組中。

BEGIN

setnull(s)；i:=l；ch:=(1)；

WHILEch<>,@,DO

BEGIN

CASEchOF

x:=0；

WHILEch<>9,'DO

BEGIN

x:=x*10+ord(ch)-ord('O')；

i:=i+l；ch:=(2)；

END

'+':x:=pop(s)+pop(s)；

'-':x:=pop(s)；x:二pop(s)-X;

'*':x:=pop(s)*pop(s)；

79:x:=pop(s)；x:二pop(s)/x；

ENDCASE

push(s,x)；i:=i+l；ch:=a[i]；

END；

comput:=(3)；

END；

27.一線性表存儲在帶頭結點的雙向循環鏈表中，L為頭指針，在空缺處填寫相應的語

句。

voidunknown(BNODETP*L)

p=L->next;q=p->next;r=q->next；

while(q!=L)

while(p!=L)&&(p->data>q->data)p=p->prior；

q->prior->next=r；(1)；

q->next=p->next；q->prior=p；

(2)；(3)；q=r；p=q->prior；

(4)：

評卷人得分

五、算法設計題：28?31小題。請將答案寫在答題紙指定位置

上。

28.設有一個數組中存放了一個無序的關鍵序列Kl、K2...Kn?現要求將Kn放在將

元素排序后的正確位置上，試編寫實現該功能的算法，要求比較關鍵字的次數不超過no

（注：用程序實現）

29.設計算法將一個帶頭結點的單鏈表A分解為兩個具有相同結構的鏈表B、C,其中B

表的結點為A表中值小于零的結點，而C表的結點為A表中值大于零的結點（鏈表A的

元素類型為整型，要求B、C表利用A表的結點）

30.設中序穿線二叉樹的結點由五個域構成：info:給出結點的數據場之值。LL：當ET為1

時，則給出該結點的左兒子之地址，當LT為。時，則給出按中序遍歷的前驅結點的地址。

LT:標志域，為1或為0oRL：當RT為1時，則給出該結點的右兒子的地址；當RT為0

時，則給出按中序遍歷的后繼結點地址。RT:標志域為0或為1。

請編寫程序，在具有上述結點結構的中序穿線二叉樹上，求某一結點p的按后序遍歷次序

的后繼結點的地址q,設該中序穿線二叉樹的根結點地址為r。另外，請注意必須滿足：

（1）額外空間的使用只能為O（1）,（2）程序為非遞歸。

31.設記錄RI,R2,…，Rn按關鍵字值從小到大順序存儲在數組r[L.n]中，在r[n+l]處設

立一個監督哨，其關鍵字值為+oo；試寫一查找給定關鍵字k的算法。

【標準答案】

第I卷(選擇題)

一、單項選擇題：1?10小題。下列每題給出的選項中，只有一個選項是符合題目要求

的。

1.C

2.B

3.D

4.D

5.D

6.C

7.D

8.A

9.A

10.D

第II卷(非選擇題)

二、填空題：11?15小題。請將答案寫在答題紙指定位置上。

11.有限序列、有窮性、確定性、可行性、輸入、輸出

12.數據項、數據項

13.5；96

14.小于等于表長的最大素數或不包含小于20的質因子的合數

15.n-1

三、判斷題：16?25小題。請將答案寫在答題紙指定位置上。

16.x

17.N

18.Y

19.7

20.x

21.N

22.x

23.x

24.q

25.x

四、程序填空：26?27小題。請將答案寫在答題紙指定位置上。

26.(1)a(或a[l](2)a[i](3)pop(s)或s[l]；

27.(1)r->prior=q->prior;〃將q結點摘下，以便插入到適當位置。

(2)p->next->prior=q;//(2)(3)將q結點插入

(3)p->next=q;

(4)-next;或r=q->next;〃后移指針，再將新結點插入到適當位置。

五、算法設計題：28?31小題。請將答案寫在答題紙指定位置上。

28.intPartition(RecTypeK[],int1,intn)

〃交換記錄子序列K[L.n]中的記錄，使樞軸記錄到位，并返回其所在位置，

〃此時，在它之前(后)的記錄均不大(小)于它

inti=l;j=n;K[0]=K[j];x=K[j].key;

while(i<j)

while(i<j&&K[i].key<=x)i++;

if(i<j)K[j]=K[i];

while(i<j&&K[j].key>=x)j—;

if(i<j)K[i]=K[j];

}//while

K[i]=K[0];returni;

}//Partition

29.voidDisCreat1(LinkedListA)

〃人是帶頭結點的單鏈表，鏈表中結點的數據類型為整型。本算法將A分解成兩個單鏈表

B和C,B中結點的數據小于零，C中結點的數據大于零。

B=A;

C=(LinkedList)malloc(sizeof(LNode));〃為C申請結點空間。

C->next=null//C初始化為空表。

p=A->next;〃p為工作指針。

B->next=null;//B表初始化。

while(p!=null)

r=p->next;〃暫存p的后繼。

if(p->data<0)〃小于0的放入B表。

p->next=B->next;B->next=p;}〃將小于0的結點鏈入B表。

elsep->next=C->next;C->next=p;}

p=r;〃p指向新的待處理結點。

)

}〃算法結束。

30.BiThrTreeInThrPostSucc(BiThrTreer,p)

〃在中序線索二叉樹r上，求結點p(假定存在)的后序后繼結點q)

if(p==r)return(null)〃若p為根結點，后序后繼為空

T二p

whil