2022年《數(shù)據(jù)結構（本）》形考任務1-4（包括實踐活動3）

2022年國家開放大學數(shù)據(jù)結構（本）形考任務1-4（包括實踐活動3）

形考1

答案在題目后面，請往下拉！

”題目1：把數(shù)據(jù)存儲到計算機中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結構稱為（）0

:邏輯結構

;算法的具體實現(xiàn)

;給相關變量分配存儲單元

;物理結構"

"題目2：下列說法中，不正確的是（）。

:數(shù)據(jù)元素是數(shù)據(jù)的基本單位

;數(shù)據(jù)項可由若干個數(shù)據(jù)元素構成

;數(shù)據(jù)項是數(shù)據(jù)中不可分割的最小可標識單位

;數(shù)據(jù)可有若干個數(shù)據(jù)元素構成"

"題目3：一個存儲結點存儲一個（）。

:數(shù)據(jù)類型

;數(shù)據(jù)元素

;數(shù)據(jù)結構

;數(shù)據(jù)項"

"題目4：數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)的（）。

:物理結構

;邏輯結構

;存儲結構

;物理和存儲結構"

"題目5:在線性表的順序結構中，以下說法正確的是（）。

:數(shù)據(jù)元素是不能隨機訪問的

;邏輯上相鄰的元素在物理位置上也相鄰

;進行數(shù)據(jù)元素的插入、刪除效率較高

;邏輯上相鄰的元素在物理位置上不一定相鄰"

"題目6：對鏈表，以下敘述中正確的是（）。

:插入刪除元素的操作一定要要移動結點

;不能隨機訪問任一結點

;可以通過下標對鏈表進行直接訪問

;結點占用的存儲空間是連續(xù)的"

"題目7:下列的敘述中，不屬于算法特性的是（）。

:輸入性

;可讀性

;可行性

;有窮性"

"題目8:算法的時間復雜度與（）有關。

:數(shù)據(jù)結構

;計算機的操作系統(tǒng)

;所使用的計算機

1

;算法本身”

”題目9:設有一個長度為n的順序表，要在第i個元素之前（也就是插入元素

作為新表的第i個元素），插入一個元素，則移動元素個數(shù)為（）。

:n-i+1

;n-i-1

；i

;n-i*fi

”題目10:設有一個長度為n的順序表，要刪除第i個元素移動元素的個數(shù)為

（）O

:n-i-1

;n-i

；i

;n-i+1"

"題目11:在一個單鏈表中，p、q分別指向表中兩個相鄰的結點，且q所指結點

是p所指結點的直接后繼，現(xiàn)栗刪除q所指結點，可用語句（）。

:p->next=q->next

;q->；next=NULL

;p->next=q

;p=q->next"

"題目12：在一個單鏈表中p所指結點之后插入一個s所指的結點時，可執(zhí)行

（）O

:s->next=p-Sgt;next;p->next=s;

;p->next=s->；next;

;p->next=s;s->next=p->next

;p=s-figt;next"

"題目13:非空的單向循環(huán)鏈表的尾結點滿足（）（設頭指針為head,指針

p指向尾結點）。

:p==head

;p->；next-NULL

;p->next-head

;p==NULL"

"題目14：鏈表不具有的特點是（）。

:插入刪除不需要移動元素

;不必事先估計存儲空間

;邏輯上相鄰的元素在物理位置上不一定相鄰

;可隨機訪問任一元素"

"題目15:帶頭結點的鏈表為空的判斷條件是（）（設頭指針為head）o

:head->next-head

;head->；next-NULL

;head!=NULL

；head==NULL"

"題目16:在一個長度為n的順序表中為了刪除第5個元素，由第6個元素開始

從后到前依次移動了15個元素。則原順序表的長度為（）。

:19

2

；21

；25

；20"

"題目17:有關線性表的正確說法是（）。

:除了一■個和最后一■個元素外，其余元素都有一■個且僅有一■個直接前驅和一■個直

接后繼

;每個元素都有一個直接前驅和一個直接后繼

;表中的元素必須按由小到大或由大到下排序

;線性表至少栗求一個元素"

"題目18:向一個有127個元素的順序表中插入一個新元素，并保持原來的順序

不變，平均要移動（）個元素。

:63

；8

；7

;63.5"

"題目19：一個順序表第一個元素的存儲地址是90,每個元素的長度為2,則第

6個元素的地址是（）。

:98

;100

；106

；102"

"題目20:在一個不帶頭結點的單循環(huán)鏈表中，p、q分別指向表中第一個結

點和尾結點，現(xiàn)栗刪除第一個結點，且p、q仍然分別指向新表中第一個結點和

尾結點。可用的語句是p=p->；next;和（）o

：q=p

;q->next=p

;p=q->；next

;p->next=q"

題目21：數(shù)據(jù)元素可以有一個或多個數(shù)據(jù)項組成。

題目22：數(shù)據(jù)元素之間的抽象關系稱為物理結構。

題目23：數(shù)據(jù)的邏輯結構在計算機中的表示稱為邏輯結構。

題目24：數(shù)據(jù)的邏楫結構是與存儲該結構的計算機相關的。

題目25：數(shù)據(jù)結構中，元素之間存在多對多的關系稱為樹狀結構。

題目26：通?？梢园岩槐竞胁煌鹿?jié)的書的目錄結構抽象成線性結構。

題目27：通?？梢园涯吵鞘兄懈鞴徽军c間的線路圖抽象成樹型結構。

題目28:設有一個不帶頭結點的單向循環(huán)鏈表，結點的指針域為next,指

針p指向尾結點，現(xiàn)要使p指向第一個結點，可用語句p=p->next;。

題目29:設有一個單向鏈表，結點的指針域為next,頭指針為head,p指

向尾結點，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句p->；next=head。

題目30:設有一個單向循環(huán)鏈表，結點的指針域為next,頭指針為head,

指針p指向表中某結點，若邏輯表達式p->next==head;的結果為真，則p所

指結點為尾結點。

題目31:要在一個單向鏈表中p所指向的結點之后插入一個s所指向的新

結點，若鏈表中結點的指針域為next,可執(zhí)行p->next=s;s->next=

3

p->；next;的操作。

題目32:要在一個單向鏈表中刪除p所指向的結點，已知q指向p所指結

點的直接前驅結點，若鏈表中結點的指針域為next,則可執(zhí)行q->；next=

p->next;

題目33:要在一個帶頭結點的單向循環(huán)鏈表中刪除頭結點，得到一個新的

不帶頭結點的單向循環(huán)鏈表，若結點的指針域為next,頭指針為head,尾指針

為p,貝[可執(zhí)行head=head->；next;p->；next=head;。

題目34:設有一個單向循環(huán)鏈表，頭指針為head,鏈表中結點的指針域為

next,p指向尾結點的直接前驅結點，若要刪除尾結點，得到一個新的單向循環(huán)

鏈表，可執(zhí)行操作p->next=head;。

"題目35:設線性表以不帶頭結點的單向鏈表存儲，鏈表頭指針為head,以

下程序的功能是輸出鏈表中各結點中的數(shù)據(jù)域data,完成程序中空格部分。

#defineNULL0

voidmain()

{NODE*head,*p;

p=head;/*p為工作指針*/

do

{printf("%d\n",[[1]];

[⑵]；

}while[[3]];

}

;[[1]]->{p->data/p=p->next/p!=NULL}"

"題目36:設有一個頭指針為head的不帶頭結點單向鏈表，p、q是指向鏈

表中結點類型的指針變量，p指向鏈表中結點a,(設鏈表中沒有結點的數(shù)據(jù)域

與結點a的數(shù)據(jù)域相同)，寫出相關語句

⑴使該單向鏈表成為單向循環(huán)鏈表

⑵插入結點s,使它成為a結點的直接前驅

q=p;x=p->；data;

while[[3]])q=q->next;

q->next=head;

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

while(p->data!=x)

{q=P；

[⑴]

)

s->next=p;

[[2]]

;[[1]]->{p=p->next/q->next=s/q->next!=NULL}"

答案

標準答案1:物理結構

標準答案2：數(shù)據(jù)項可由若干個數(shù)據(jù)元素構成

標準答案3：數(shù)據(jù)元素

4

標準答案4邏輯結構

標準答案5邏輯上相鄰的元素在物理位置上也相鄰

標準答案6不能隨機訪問任一結點

標準答案7可讀性

標準答案8算法本身

標準答案9n-i+1

標準答案10:n-i

標準答案11:p->next=q->next

標準答案12:s->next=p->next;p->next=s;

標準答案13:p->next-head

標準答案14:可隨機訪問任一元素

標準答案15:head->next==NULL

標準答案16:20

標準答案17:除了一個和最后一個元素外，其余元素都有一個且僅有一個直接

前驅和一個直接后繼

標準答案1863.5

標準答案19100

標準答案20q->next=p

標準答案21對

標準答案22錯

標準答案23錯

標準答案24錯

標準答案25錯

標準答案26錯

標準答案27錯

標準答案28對

標準答案29對

標準答案30對

標準答案31錯

標準答案32對

標準答案33對

標準答案34對

標準答案35{p->data}{p=p->next}{p!=NULL}

標準答案36{q->next!=NULL}{p=p->next}{q->next=s}

形考2

"題目1:若讓元素1,2,3依次進棧，則出棧順序不可能為（）。

：3,2,1

；3,1,2

；1,3,2

；2,1,3"

"題目2：一個隊列的入隊序列是1,2,3,4O則隊列的輸出序列是（）。

：1,2,3,4

5

；1,4,3,2

；4,3,2,1

；3,2,4,1"

"題目3：向順序棧中壓入新元素時，應當（）。

:先移動棧頂指針，再存入元素

;先后次序無關緊要

;先存入元素，再移動棧頂指針

;同時進行"

"題目4：在一個棧頂指針為top的鏈棧中，將一個p指針所指的結點入棧，應

執(zhí)行（）。

:p->next=top->next;top->next=p;

;p->next=top;top=p;

;top-figtjnext=p;

;p->next=top->next;top=top->next;"

”題目5:在一個棧頂指針為top的鏈棧中刪除一個結點時，用x保存被刪結點

的值，則執(zhí)行（）。

:x=top;top=top->next;

;x=top->data;

;x=top->data;top=top->next;

;top=top->next;x=top->data;"

”題目6:判斷一個順序隊列（最多元素為m）為空的條件是（）。

:rear==m-1

;front-rear+1

;rear=m

;front~rear"

”題目7：判斷一個循環(huán)隊列為滿的條件是（）。

:front-rear+1

;rear=MaxSize

;（rear+1）%MaxSize二二front

;rear%MaxSize==front"

”題目8:判斷棧滿（元素個數(shù)最多n個）的條件是（）。

:top=二n-1

；top!二0

;top二7

;top-0"

”題目9:設有一個20階的對稱矩陣A（第一個元素為a1,1）,采用壓縮存儲的

方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中（數(shù)組下標從1開始），

則矩陣元素a6,2在一維數(shù)組B中的下標是（）。

:21

；17

；23

；28"

”題目10：在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印

數(shù)據(jù)緩沖區(qū)，主機將要輸出的數(shù)據(jù)依次寫入緩沖區(qū)中，而打印機則從緩沖區(qū)中取

6

出數(shù)據(jù)打印，該緩沖區(qū)應該是一個（）結構。

:線性表

;隊列

;數(shù)組

;堆棧"

"題目11:一個遞歸算法必須包括（）。

:迭代部分

;終止條件和迭代部分

;遞歸部分

;終止條件和遞歸部分"

"題目12:在一個鏈隊中，假設f和r分別為隊頭和隊尾指針，則刪除一個結點

的運算為（）。

:r=r->next;

;f=f->next;

;f=r->next;

;r=f->next;"

"題目13:在一個鏈隊中，假設千和r分別為隊頭和隊尾指針，則插入s所指結

點的運算為（）。

:f->next=s;f=s;

;r->next=s;r=s;

;s->next=f;f=s;

;s->next=r;r=s;"

"題目14：數(shù)組a經(jīng)初始化chara[]="EngIish"；a[7]中存放的是（）。

:字符串的結束符

;變量h

；"h"

；字符h"

"題目15:設主串為“ABcCDABcdEFaBc”,以下模式串能與主串成功匹配的是

（）。

:Bed

;Abe

;BCd

;ABC"

”題目16：字符串a(chǎn)1="AEIJING",a2="AEI",a3="AEFANG",a4="AEFI"中最大

的是（）。

:a2

；a1

;a4

;a3"

”題目17：兩個字符串相等的條件是（）。

:兩串的長度相等，并且兩串包含的字符相同

;兩串的長度相等，并且對應位置上的字符相同

;兩串包含的字符相同

;兩串的長度相等"

7

"題目18:一維數(shù)組A采用順序存儲結構，每個元素占用6個字節(jié)，第6個元素

的存儲地址為100,則該數(shù)組的首地址是（）。

:28

;64

;90

;70"

"題目19：一個非空廣義表的表頭（）。

:只能是原子

;不可能是原子

;可以是子表或原子

;只能是子表"

"題目20：對稀疏矩陣進行壓縮存儲，可采用三元組表，一個10行8列的稀疏矩

陣A,其相應的三元組表共有6個元素，矩陣A共有（）個零元素。

:10

；72

；74

；8"

"題目21:對稀疏矩陣進行壓縮存儲，可采用三元組表，一個10行8列的稀疏矩

陣A共有73個零元素，A的右下角元素為6,其相應的三元組表中的第7個元素

是（）。

:（10,8,7）

;（7,8,10）

;（10,8,6）

;（7,10,8）"

"題目22：對一個棧頂指針為top的鏈棧進行入棧操作，通過指針變量p生成入

棧結點，并給該結點賦值a,則執(zhí)行：p=（structnode*）maIIoc（sizeof（struct

node）；p->data=a;和（）0

:p->next=top;p=top;

;p->；next-top；top=p；

;top->next=p;p=top;

;top=top-Sgt；next;p=top;"

“題目23:頭指針為head的帶頭結點的單向鏈表為空的判定條件是（）為真。

:head_>；next!=NULL

;head->next-NULL

;head==NULL

;head->next!=NULL"

"題目24：設有一個對稱矩陣A,采用壓縮存儲的方式，將其下三角部分以行序

為主序存儲到一維數(shù)組B中（數(shù)組下標從1開始），B數(shù)組共有55個元素，則該

矩陣是（）階的對稱矩陣。

:5

；15

；20

；10"

"題目25:數(shù)組a經(jīng)初始化chara[]="English”；a[1]中存放的是（）。

8

:"E"

IfII

；n

；字符n

；字符E"

"題目26：設有一個鏈棧，棧頂指針為hs,現(xiàn)有一個s所指向的結點要入棧，

則可執(zhí)行操作。hs=s;

s->next=hs；"

"題目27:設有一個非空的鏈棧，棧頂指針為hs,要進行出棧操作，用x

保存出棧結點的值，棧

結點的指針域為next,則可執(zhí)行hs=hs->next;x=hs->data;"

"題目28:有一個鏈棧，棧頂指針為h,現(xiàn)有一個p所指向的結點要入棧，

則可執(zhí)行操作p->next=h;

和h=p;"

題目29:設有一個非空的鏈棧，棧頂指針為hs,要進行出棧操作，用x保

存出棧結點的值，棧結點的指針域為next,數(shù)據(jù)域為data,則可執(zhí)行hs=

hs->next;x=hs->data;

題目30:在一個鏈隊中，千和r分別為隊頭和隊尾指針，隊結點的指針域為

next,則插入所指結點的操作為r->next=s：r=s;

題目31:在一個鏈隊中，千和r分別為隊頭和隊尾指針，隊結點的指針域為

next,s指向一個要入隊的結點，則入隊操作為r=s;r->next=s;

題目32:在一個不帶頭結點的非空鏈隊中，f和r分別為隊頭和隊尾指針，

隊結點的數(shù)據(jù)域為data,指針域為next,若要進行出隊操作，并用變量x存放

出隊元素的數(shù)據(jù)值，則相關操作為x=f->；data；f=f->；next；

題目33:對稀疏矩陣進行壓縮存儲，可采用三元組表，一個6行7列的稀疏矩陣

A相應的三元組表共有8個元素，則矩陣A共有34個零元素。

題目34：循環(huán)隊列的最大存儲空間為MaxSize,隊頭指針為f,隊尾指針為

r,當（r+1）%MaxSize=f時表明隊列已滿。

題目35:循環(huán)隊列的隊頭指針為f,隊尾指針為r,當r==千時表明隊列已滿。

題目36:空串的長度是0;空格串的長度是空格字符的個數(shù)。

題目37:對稀疏矩陣進行壓縮存儲，矩陣中每個非零元素對應的三元組包

括該元素的行下標、列下標、和非零元素值三項信息。

題目38:循環(huán)隊列的引入，目的是為了克服假上溢。

”題目39:

設有n階對稱矩陣A,用一維數(shù)組s壓縮存儲A的下三角元素，s的下標從零開

始，元素s[26]相應于A中的元素為a7,5o"

題目40:循環(huán)隊列的最大存儲空間為MaxSize=6,采用少用一個元素空間以

有效的判斷?？栈驐M，若隊頭指針front=4,當隊尾指針rear=3時隊滿。

題目41:循環(huán)隊列的最大存儲空間為MaxSize=6,采用少用一個元素空間以

有效的判斷?？栈驐M，若隊頭指針front=4,隊尾指針rear=3時，隊列中共

有5個元素。

"題目42:以下函數(shù)為鏈棧的進棧操作，x是要進棧的結點的數(shù)據(jù)域，top為棧

頂指針

structnode

{EIemTypedata;

9

structnode*next;

};

structnode*top;

voidPush(ElemTypex)

(

structnode*p;

p=(structnode*)maIIoc[[1]];

p->data=x;

[[3]];

[[2]]；

1

;[[1]]->{A.sizeof(structnode)/top=p/p->next=top}"

”題目43:以下函數(shù)為鏈隊列的入隊操作，x為要入隊的結點的數(shù)據(jù)域的

值，front、rear分別鏈隊列的隊頭、隊尾指針

structnode

{EIemTypedata;

structnode*next;

};

structnode*front,*rear;

voidInQueue(ElemTypex)

(

structnode*p;

p=(structnode*)maIIoc[[3]];

p->data=x;

p->；next二NULL;

[[1]]；

rear=[⑵];

)

;[⑴]->；{rear->next=p/p/(sizeof(structnode)}"

答案

標準答案1:3,1,2

標準答案2：1,2,3,4

標準答案3：先移動棧頂指針，再存入元素

標準答案4:p->next=top;top=p;

標準答案5:x=top->data；top=top->next;

標準答案6:front=rear

標準答案7:(rear+1)%MaxSize-front

標準答案8:top==n-1

標準答案9:17

標準答案10:隊列

10

標準答案11終止條件和遞歸部分

標準答案12f=f->next;

標準答案13r->next=s;r=s;

標準答案14字符串的結束符

標準答案15Bed

標準答案16:a1

標準答案17兩串的長度相等，并且對應位置上的字符相同

標準答案1870

標準答案19可以是子表或原子

標準答案2074

標準答案21(10,8,6)

標準答案22p->next=top;top=p;

標準答案23head->next-NULL

標準答案2410

標準答案25字符n

標準答案26錯

標準答案27錯

標準答案28對

標準答案29錯

標準答案30對

標準答案31錯

標準答案32對

標準答案33對

標準答案34對

標準答案35錯

標準答案36對

標準答案37對

標準答案38對

標準答案39錯

標準答案40對

標準答案41對

標準答案42{A.sizeof(structnode)}{p->next=top}{top=p}

標準答案43{(sizeof(structnode)){rear->next=p}lp)

形考3

"題目1：假定一棵二叉樹中，雙分支結點數(shù)為15,單分支結點數(shù)為30,則葉子

結點數(shù)為()O

:16

；15

；17

；47"

"題目2:二叉樹第k層上最多有()個結點。

:2k-1

11

；2k

；2k-1

；2k-1"

"題目3：將含有150個結點的完全二叉樹從根這一層開始，每一層從左到右依

次對結點進行編號，根結點的編號為1,則編號為69的結點的雙親結點的編號

為（）。

:33

；34

;35

;36"

"題目4：如果將給定的一組數(shù)據(jù)作為葉子數(shù)值，所構造出的二叉樹的帶權路徑

長度最小，則該樹稱為（）。

:二叉樹

;平衡二叉樹

;哈夫曼樹

;完全二叉樹"

"題目5:在一棵度具有5層的滿二叉樹中結點總數(shù)為（）。

:33

；32

；16

;31"

"題目6：一棵完全二叉樹共有6層，且第6層上有6個結點，該樹共有（）

個結點。

:38

；37

；72

；31"

"題目7：利用3、6、8、12這四個值作為葉子結點的權，生成一棵哈夫曼樹，

該樹中所有葉子結點中的最長帶權路徑長度為（）。

:18

；16

；30

；12"

"題目8:在一棵樹中，（）沒有前驅結點。

:空結點

;樹根結點

;葉結點

;分支結點”

"題目9:設一棵采用鏈式存儲的二叉樹，除葉結點外每個結點度數(shù)都為2,該樹

結點中共有20個指針域為空，則該樹有（）個葉結點。

:21

；22

；10

；9"

12

"題目10：在一個圖G中，所有頂點的度數(shù)之和等于所有邊數(shù)之和的（）倍。

:2

；4

；1

:1/2"

"題目11:鄰接表是圖的一種（）。

:鏈式存儲結構

;索引存儲結構

;順序存儲結構

;散列存儲結構"

"題目12：圖的深度優(yōu)先遍歷算法類似于二叉樹的（）遍歷。

:后序

;先序

;層次

;中序"

"題目13：已知下圖所示的一個圖，若從頂點V1出發(fā)，按深度優(yōu)先搜索法進行

遍歷，則可能得到的一種頂點序列為（）。

:V1V2V4V8V3V5V6V7

;V1V3V6V7V2V4V5V8

;V1V2V4V5V8V3V6V7

;V1V2V4V8V5V3V6V7"

"題目14：已知如下圖所示的一個圖，若從頂點a出發(fā)，按廣度優(yōu)先搜索法進行

遍歷，則可能得到的一種頂點序列為（）。

:aedfcb

;aebcfd

;abecdf

;aecbdf"

"題目15:圖狀結構中數(shù)據(jù)元素的位置之間存在（）的關系。

:多對多

;一對一

；一對多

;每一個元素都有一個且只有一個直接前驅和一個直接后繼"

"題目16:在一棵二叉樹中，若編號為i的結點存在右孩子，則右孩子的順序編

號為（）。

:2i

；2i+2

；2i+1

；2i-1"

"題目17：一棵具有16個結點的完全二叉樹，共有（）層。（設根結點在

第一層）

:4

；5

；6

；7"

13

"題目18:對二叉排序樹進行()遍歷，可以使遍歷所得到的序列是有序

序列。

:后序

;按層次

；中序

;前序"

"題目19:已知一個圖的邊數(shù)為m,則該圖的所有頂點的度數(shù)之和為()。

:2m

;m/2

;m

;2m+1"

題目20：一棵二叉樹的葉結點(終端結點)數(shù)為5,單分支結點數(shù)為2,該樹共

有11個結點。

題目21：一棵有14個結點的完全二叉樹，則它的最高層上有7個結點。

題目22：一棵二叉樹有6個葉結點，則該樹總共有11個結點。

題目23：根據(jù)搜索方法的不同，圖的遍歷有.先序；中序；后序三種方法。

題目24：對于一棵具有n個結點的二叉樹，其相應的鏈式存儲結構中共有n-1

個指針域空。

題目25:設一棵完全二叉樹，其最高層上最右邊的葉結點的編號為奇數(shù)，

該葉結點的雙親結點的編號為10,該完全二叉樹一共有21個結點。

題目26：設一棵完全二叉樹，其最高層上最右邊的葉結點的編號為偶數(shù)，

該葉結點的雙親結點的編號為9,該完全二叉樹一共有19個結點。

題目27：按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有深度優(yōu)先遍歷和

深度優(yōu)先遍兩種方法。

題目28:一棵有8個權重值構造的哈夫曼數(shù)，共有17個結點。

題目29：一棵有7個葉結點的二叉樹，其1度結點數(shù)的個數(shù)為2,則該樹共有

15個結點。

"題目30:以下程序是后序遍歷二叉樹的遞歸算法的程序，完成程序中空格

部分(樹結構中左、右指針域分別為left和right,數(shù)據(jù)域data為字符型，BT

指向根結點)。完成程序中空格部分。

void

Inorder(structBTreeNode*BT)

(

if(BT!=NULL)

(

Inorder(BT->Ieft);

[[1]]

[[3]]

}

利用上述程序對左圖進行后序遍歷，結果是[[2]]；

;[[1]]->{Inorder(BT->right)/d,e,b,f,c,a/

printf(a%c>>,BT->data))"

"題目31:以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格

部分(樹結構中左、右指針域分別為left和right,數(shù)據(jù)域data為字符型，BT

14

指向根結點)。

voidInorder(structBTreeNode*BT)

if(BT!=NULL){

Inorder(BT->Ieft);}

[[2]];

[[3]]；

}

利用上述程序對右圖進行中序遍歷，結果是[[1]];

;[[1]]->{d,b,e,a,f,c/printf("%c”,BT->data)/Inorder(BT->right)!"

"題目32:(1)以3,4,5,8,9,作為葉結點的權，構造一棵哈夫曼樹。該樹

的帶權路徑長度為{A;B;C;D}.

A,64B.65C.62D.66

(2)權重為3的葉結點的哈夫曼編碼為{A;B;C;D}o

A.010B.0101C.000D.0111"

"題目33：(1)以2,3,4,7,8,9作為葉結點的權，構造一棵哈夫曼樹，該

樹的帶權路徑長度為{A;B；C;D)

A,66B.80C.62D.87

(2)權重值為4的葉結點的哈夫曼編碼為{A;B;C;D}o

A.0001B.1110C.001D.110"

"題目34：(1)已知某二叉樹的后序遍歷序列是debca,中序遍歷序列是dbeac,

該二叉樹的根結點是｛A;B;C;D)

A.eB.cC.bD.a

(2)先序遍歷序列是列;B;C;D｝o

A.e,b,c,d,aB.c,a,b,,d,eC.a,b,d,e,cD.

a.c,b,d,e,"

"題目35:(1)已知某二叉樹的先序遍歷序列是aecdb,中序遍歷序列是eadcb,

該二叉樹的根結點是｛A;B;C;D);

A.eB.cC.bD.a

(2)后序遍歷序列為｛A;B;C;DU

A.e,d,b,c,aB.c,a,b,,d,eC.a,b,d,e,cD.a.c,b,d,e,"

"題目36：(1)以給定權重值5,6,17,18,25,30,為葉結點，建立一棵哈

夫曼樹，該樹的中序遍歷序列為｛A;B；C;D)

A.5,11,28,6,17,58,30,101,18,43,25

B.5,11,6,28,17,58,30,101,18,43,25

C.5,11,6,28,101,58,30,17,18,43,25

D.5,11,6,28,17,58,30,101,18,25,43

(2)權重值為6的葉結點的哈夫曼為｛A;B;C;D｝.

A.1001B.011C.001D.0001

答案

標準答案1:16

標準答案2：2k-1

15

標準答案3:34

標準答案4:哈夫曼樹

標準答案5:31

標準答案6:37

標準答案7：18

標準答案8:樹根結點

標準答案9:10

標準答案102

標準答案11鏈式存儲結構

標準答案12先序

標準答案13V1V2V4V8V5V3V6V7

標準答案14aecbdf

標準答案15多對多

標準答案162i+1

標準答案175

標準答案18中序

標準答案192m

標準答案20對

標準答案21對

標準答案22錯

標準答案23錯

標準答案24錯

標準答案25對

標準答案26錯

標準答案27錯

標準答案28錯

標準答案29對

標準答案30:{Inorder(BT->right)){printf("%c”,BT->data)}

{d,e,b,f,c,a}

標準答案31:{printf(<<%cw,BT->data)){Inorder(BT->right)}

{d,b,e,a,f,c）

標準答案32:子問題1:B;子問題2:C

標準答案33:子問題1:B;子問題2:C

標準答案34:子問題1:D;子問題2：C

標準答案35:子問題1:D；子問題2：A

標準答案36:子問題1:B;子問題2：D

形考4

"題目1：對線性表進行二分查找時，要求線性表必須（）。

：以鏈接存儲方式

；以鏈接存儲方式，且數(shù)據(jù)元素有序

；以順序存儲方式，且數(shù)據(jù)元素有序

；以順序存儲方式"

16

"題目2:采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長

度為（）。

:（n-1）/2

;（n+1）/2

;n/2

；n"

"題目3:有一個長度為10的有序表，按折半查找對該表進行查找，在等概率情

況下查找成功的平均比較次數(shù)為（）。

:29/10

；26/10

；31/10

；29/9"

"題目4：已知一個有序表為{11,22,33,44,55,66,77,88,99},則順序查找元素

55需要比較（）次。

:5

；6

；4

；3"

"題目5:有數(shù)據(jù)［53,30,37,12,45,24,96},從空二叉樹開始逐個插入數(shù)據(jù)來形

成二叉排序樹，若希望高度最小，應該選擇的序列是（）。

:30,24,12,37,45,96,53

;45,24,53,12,37,96,30

;12,24,30,37,45,53,96

；37,24,12,30,53,45,96"

"題目6:對于順序存儲的有序表{5,12,20,26,37,42,46,50,64},若采用折半

查找，則查找元素26的比較次數(shù)是（）。

:6

；4

；5

；3"

"題目7:在所有的排序方法中，關鍵字比較的次數(shù)與記錄初始排列秩序無關的

是（）。

:直接選擇排序

;希爾排序

；冒泡排序

;直接插入排序”

"題目8:從未排序序列中依次取出元素與已經(jīng)排好序的序列中的元素作比較。

將其放入已排序序列的正確的位置上，此方法稱為（）。

:選擇排序

;插入排序

;交換排序

;歸并排序"

"題目9：依次將每兩個相鄰的有序表合并成一個有序表的排序方法稱為（）。

:選擇排序

17

;交換排序

;插入排序

;歸并排序"

"題目10:當兩個元素出現(xiàn)逆序的時候就交換位置，這種排序方法稱為（）。

:交換排序

;選擇排序

;歸并排序

;插入排序"

"題目11:每次把待排序的區(qū)間劃分為左、右兩個子區(qū)間，其中左區(qū)間中記錄的

關鍵字均小于等于基準記錄的關鍵字，右區(qū)間中記錄的關鍵字均大于等于基準記

錄的關鍵字，這種排序稱為（）。

:歸并排序

;快速排序

;插入排序

;堆排序"

”題目12：一組記錄的關鍵字序列為（46,20,30,79,56,38,40,84,90,110）,

利用快速排序，以第一個關鍵字為分割元素，經(jīng)過一次劃分后結果為（）。

:20,30,40,38,46,79,56,84,90,100

;30,20,40,38,46,84,56,79,90,100

；40,20,30,38,46,56,79,84,90,110

;20,3038,40,46,56,79,84,90,100

”題目13:在有序表｛10,14,34,43,47,64,75,80,90｝中，用折半查找法

查找值80時，經(jīng)（）次比較后查找成功。

:3

；5

；4

；2"

"題目14：對序列（49,38,65,97,76,13,47,50）采用直接插入排序法進

行排序，要把第七個元素47插入到已排序中，為尋找插入的合適位置需要進行

（）次元素間的比較。

:5

；6

；4

；3"

"題目15:排序方法中，從未排序序列中挑選元素，并將其依次放入已排序序列

（初始為空）的一端的方法，稱為（）排序。

:插入

；歸并

;快速

;選擇”

"題目16:一組記錄的關鍵字序列為（26,59,36,18,20,25）,利用堆排序

的方法建立的初始小根堆為（）。

:18,20,36,59,26,25

；18,20,25,59,26,36

18

；26,18,59,20,36,25

；26,59,36,18,20,25"

”題目17:一組記錄的關鍵字序列為（25,48,16,35,79,82,23,40,36,

72）,其中，含有5個長度為2的有序表，按歸并排序的方法對該序列進行一趟

歸并后的結果為（)O

16,25,35,48,23,40,79,82,36,72

16,25,35,48,79,82,23,36,40,72

16,25,48,35,79,82,23,36,40,72

16,25,35,48,79,23,36,40,82,72"

'題目18:已知10個數(shù)據(jù)元素為（54,28,16,34,73,62,95,60,26,43),

對該數(shù)列從小到大排序,經(jīng)過一趟冒泡排序后的序列為()O

28,16,34,54,62,73,60,26,43,95

16,28,34,54,73,62,60,26,43,95

16,28,34,54,62,60,73,26,43,95

28,16,34,54,62,60,73,26,43,95"

'題目19：一組記錄的關鍵字序列為（46,79,56,38,40,84）,利用快速排

序，以第一個關鍵字為分割元素，經(jīng)過一次劃分后結果為（）O

:40,38,46,79,56,84

；40,38,46,56,79,84

；40,38,46,84,56,79

；38,40,46,56,79,84"

"題目20:一組記錄的關鍵字序列為（80,57,41,39,46,47）,利用堆排序（堆

頂元素是最小元素）的方法建立的初始堆為（）。

:39,46,41,57,80,47

;39,47,46,80,41,57

;39,80,46,47,41,57

;41,39,46,47,57,80"

"題目21：以下函數(shù)是二叉排序樹的查找算法，若二叉樹為空，則返回根結

點的指針，否則，返回值是指向樹結點的結構指針p（查找成功p指向查到的樹

結點，不成功p指向為NULL）完成程序中的空格

typedefstructBnode

{intkey;

structBnode*Ieft;

structBnode*right;

}Bnode;

Bnode*BSearch(Bnode*bt,intk)

/*bt用于接收二叉排序樹的根結點的指針，k用以接收要查找的關鍵字*/

{Bnode*p;

if(bt==[[2]])

return(bt);

p=bt;

while(p->key!=[[5]])

{if(kkey)

[[1]]；

19

else[[3]];

if(p==NULL)break;

)

return([[4]]；

}

;[[1]]->{p=p->Ieft/NULL/p=p->right/p/k)"

"題目22：以下程序是折半插入排序的算法

設待排序的記錄序列存放在a[1],…a[n]中，以a[0]作為輔助工作單元，程序是

要把a插入到已經(jīng)有序的序列a[1],…a[i7]中。

voidbinsort(NODEa[],intn)

{intx,i,j,s,k,m;

for(i=2；i<；=[[4]]；i++)

{a[0]=a；

x=a.key;

S=1;

j=i-1；

while(s<=j)

{m=[⑴]

if(x<a[m].key)[[2]]eIse

[[5]]}for(k=i-1;k>=j+1;k--)

[[3]]=a[k]；

a[j+1]=a[0];

}

}

;[[1]]->{(s+j)/2/j=m-1/a[k+1]/n/s=m+1}"

"題目23：(1)設查找表為(1,10,11,14,23,27,29,55,68),畫出對上述查

找表進行折半查找所對應的判定樹，為了成功查找到元素14,需要依次與元素{A；

B；C；D}進行比較。

A.23,10,1,14B,23,29,27,14C.23,10,11,14

D.23,29,55,14

(2)在等概率條件下，成功查找的平均比較次數(shù)為{A;B;C;D}o

A.24/9B.25/9C.3D.2.5

It

"題目24:(1)一組記錄的關鍵字序列為(47,80,57,39,41,46),利

用堆排序的方法建立的初始堆為{A;B;C;D}(堆頂元素是最小元素，采用樹的

形式建堆)。

A.39,41,57,80,47,46B,39,41,46,80,47,57

C.39,47,46,80,41,57D.39,41,57,80,46,47

(2)輸出堆頂元素后，調(diào)整后的堆為{A;B;C;D}。

A.41,47,46,80,57B.41,57,46,80,47

C.41,57,80,47,46D.41,80,46,47,57"

"題目25:(1)對關鍵字序列(56,51,71,54,46,106),利用快速排序，以第

一個關鍵字為分割元素，經(jīng)過一次劃分后結果為{A;B;C;D};

A.46,51,56,54,71,106B.56,51,54,46,71,106

20

C.46,51,54,56,71,106D.56,51,46,54,71,106

(2)一組記錄的關鍵字序列為(60,47,80,57,39,41,46,30),利用歸

并排序的方法，經(jīng)過(2,2)歸并的結果序列為(A；B；C；D｝。.

A.(30,57,60,80,47,39,41,46)B.(47,60,57,80,

30,39,41,46)

C.(41,57,60,80,30,39,47,46)D.(47,57,60,80,

30,39,41,46)"

"題目26：(1)對關鍵字序列(36,69,46,28,30,74)采用快速排序，以第一

個關鍵字為分割元素，經(jīng)過一次劃分后的結果序列為｛A;B;C;D)

A.30,28,46,36,69,74B.28,30,36,46,69,74

C.28,30,46,36,69,74D,30,28,36,46,69,74

(2)用冒泡法對上述序列排序，經(jīng)兩越冒泡的結果序列為｛A;B;C;D｝。

A.36,28,30,46,69,74B.36,46,28,20,69,74

.C.38,36,30,46,69,74D.28,36,,30,46,69,74"

"題目27:(1)一組記錄的關鍵字序列為｛45,40,65,43,35,95｝寫出利

用快速排序的方法，以第一個記錄為基準得到的一趟劃分的結果為｛A;B;C;D｝;

A.354065453595

B.354065434595

C.354043456595

D.354045436595

(2)對上述序列利用直接插入排序，逐次插入過程中，共進行了｛A;B；C;D)

次元素間的比較。

A.8B.11C.9D.10"

答案

標準答案1:以順序存儲方式，且數(shù)據(jù)元素有序

標準答案2:(n+1)/2

標準答案3:29/10

標準答案4:5

標準答案5:37,24,12,30,53,45,96

標準答案6:4

標準答案7：直接選擇排序

標準答案8:插入排序

標準答案9:歸并排序

標準答案10:交換排序

標準答案11:快速排序

標準答案12：40,20,30,38,46,56,79,84,90,110

標準答案13：3

標準答案14：5

標準答案15：選擇

標準答案16：18,20,25,59,26,36

標準答案17:16,25,35,48,23,40,79,82,36,72

標準答案18：28,16,34,54,62,73,60,26,43,95

21

標準答案1940,38,46,56,79,84

標準答案2039,46,41,57,80,47

標準答案21{NULL}{k}{p=p->left}{p=p->right}{p}

標準答案22{n}{(s+j)/2}{j=m-1}{s=m+1}{a[k+1]}

標準答案23子問題1:C:子問題2:B

標準答案24子問題1:B:子問題2:A

標準答案25子問題1:0;子問題2:D

標準答案26子問題1:D:子問題2:A

標