2022年《數(shù)據(jù)結(jié)構(gòu)（本）》形考任務(wù)1-4（包括實(shí)踐活動(dòng)3）

2022年國(guó)家開(kāi)放大學(xué)數(shù)據(jù)結(jié)構(gòu)（本）形考任務(wù)1-4（包括實(shí)踐活動(dòng)3）

形考1

答案在題目后面，請(qǐng)往下拉！

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

:邏輯結(jié)構(gòu)

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

;給相關(guān)變量分配存儲(chǔ)單元

;物理結(jié)構(gòu)"

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

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

;數(shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)元素構(gòu)成

;數(shù)據(jù)項(xiàng)是數(shù)據(jù)中不可分割的最小可標(biāo)識(shí)單位

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

"題目3：一個(gè)存儲(chǔ)結(jié)點(diǎn)存儲(chǔ)一個(gè)（）。

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

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

;數(shù)據(jù)結(jié)構(gòu)

;數(shù)據(jù)項(xiàng)"

"題目4：數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的（）。

:物理結(jié)構(gòu)

;邏輯結(jié)構(gòu)

;存儲(chǔ)結(jié)構(gòu)

;物理和存儲(chǔ)結(jié)構(gòu)"

"題目5:在線性表的順序結(jié)構(gòu)中，以下說(shuō)法正確的是（）。

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

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

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

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

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

:插入刪除元素的操作一定要要移動(dòng)結(jié)點(diǎn)

;不能隨機(jī)訪問(wèn)任一結(jié)點(diǎn)

;可以通過(guò)下標(biāo)對(duì)鏈表進(jìn)行直接訪問(wèn)

;結(jié)點(diǎn)占用的存儲(chǔ)空間是連續(xù)的"

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

:輸入性

;可讀性

;可行性

;有窮性"

"題目8:算法的時(shí)間復(fù)雜度與（）有關(guān)。

:數(shù)據(jù)結(jié)構(gòu)

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

;所使用的計(jì)算機(jī)

1

;算法本身”

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

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

:n-i+1

;n-i-1

；i

;n-i*fi

”題目10:設(shè)有一個(gè)長(zhǎng)度為n的順序表，要?jiǎng)h除第i個(gè)元素移動(dòng)元素的個(gè)數(shù)為

（）O

:n-i-1

;n-i

；i

;n-i+1"

"題目11:在一個(gè)單鏈表中，p、q分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)

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

:p->next=q->next

;q->；next=NULL

;p->next=q

;p=q->next"

"題目12：在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(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)鏈表的尾結(jié)點(diǎn)滿足（）（設(shè)頭指針為head,指針

p指向尾結(jié)點(diǎn)）。

:p==head

;p->；next-NULL

;p->next-head

;p==NULL"

"題目14：鏈表不具有的特點(diǎn)是（）。

:插入刪除不需要移動(dòng)元素

;不必事先估計(jì)存儲(chǔ)空間

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

;可隨機(jī)訪問(wèn)任一元素"

"題目15:帶頭結(jié)點(diǎn)的鏈表為空的判斷條件是（）（設(shè)頭指針為head）o

:head->next-head

;head->；next-NULL

;head!=NULL

；head==NULL"

"題目16:在一個(gè)長(zhǎng)度為n的順序表中為了刪除第5個(gè)元素，由第6個(gè)元素開(kāi)始

從后到前依次移動(dòng)了15個(gè)元素。則原順序表的長(zhǎng)度為（）。

:19

2

；21

；25

；20"

"題目17:有關(guān)線性表的正確說(shuō)法是（）。

:除了一■個(gè)和最后一■個(gè)元素外，其余元素都有一■個(gè)且僅有一■個(gè)直接前驅(qū)和一■個(gè)直

接后繼

;每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼

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

;線性表至少栗求一個(gè)元素"

"題目18:向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素，并保持原來(lái)的順序

不變，平均要移動(dòng)（）個(gè)元素。

:63

；8

；7

;63.5"

"題目19：一個(gè)順序表第一個(gè)元素的存儲(chǔ)地址是90,每個(gè)元素的長(zhǎng)度為2,則第

6個(gè)元素的地址是（）。

:98

;100

；106

；102"

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

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

尾結(jié)點(diǎn)?？捎玫恼Z(yǔ)句是p=p->；next;和（）o

：q=p

;q->next=p

;p=q->；next

;p->next=q"

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

題目22：數(shù)據(jù)元素之間的抽象關(guān)系稱為物理結(jié)構(gòu)。

題目23：數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為邏輯結(jié)構(gòu)。

題目24：數(shù)據(jù)的邏楫結(jié)構(gòu)是與存儲(chǔ)該結(jié)構(gòu)的計(jì)算機(jī)相關(guān)的。

題目25：數(shù)據(jù)結(jié)構(gòu)中，元素之間存在多對(duì)多的關(guān)系稱為樹(shù)狀結(jié)構(gòu)。

題目26：通常可以把一本含有不同章節(jié)的書的目錄結(jié)構(gòu)抽象成線性結(jié)構(gòu)。

題目27：通?？梢园涯吵鞘兄懈鞴徽军c(diǎn)間的線路圖抽象成樹(shù)型結(jié)構(gòu)。

題目28:設(shè)有一個(gè)不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext,指

針p指向尾結(jié)點(diǎn)，現(xiàn)要使p指向第一個(gè)結(jié)點(diǎn)，可用語(yǔ)句p=p->next;。

題目29:設(shè)有一個(gè)單向鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext,頭指針為head,p指

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

題目30:設(shè)有一個(gè)單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext,頭指針為head,

指針p指向表中某結(jié)點(diǎn)，若邏輯表達(dá)式p->next==head;的結(jié)果為真，則p所

指結(jié)點(diǎn)為尾結(jié)點(diǎn)。

題目31:要在一個(gè)單向鏈表中p所指向的結(jié)點(diǎn)之后插入一個(gè)s所指向的新

結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext,可執(zhí)行p->next=s;s->next=

3

p->；next;的操作。

題目32:要在一個(gè)單向鏈表中刪除p所指向的結(jié)點(diǎn)，已知q指向p所指結(jié)

點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext,則可執(zhí)行q->；next=

p->next;

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

不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，若結(jié)點(diǎn)的指針域?yàn)閚ext,頭指針為head,尾指針

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

題目34:設(shè)有一個(gè)單向循環(huán)鏈表，頭指針為head,鏈表中結(jié)點(diǎn)的指針域?yàn)?/p>

next,p指向尾結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若要?jiǎng)h除尾結(jié)點(diǎn)，得到一個(gè)新的單向循環(huán)

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

"題目35:設(shè)線性表以不帶頭結(jié)點(diǎn)的單向鏈表存儲(chǔ)，鏈表頭指針為head,以

下程序的功能是輸出鏈表中各結(jié)點(diǎn)中的數(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:設(shè)有一個(gè)頭指針為head的不帶頭結(jié)點(diǎn)單向鏈表，p、q是指向鏈

表中結(jié)點(diǎn)類型的指針變量，p指向鏈表中結(jié)點(diǎn)a,(設(shè)鏈表中沒(méi)有結(jié)點(diǎn)的數(shù)據(jù)域

與結(jié)點(diǎn)a的數(shù)據(jù)域相同)，寫出相關(guān)語(yǔ)句

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

⑵插入結(jié)點(diǎn)s,使它成為a結(jié)點(diǎn)的直接前驅(qū)

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}"

答案

標(biāo)準(zhǔn)答案1:物理結(jié)構(gòu)

標(biāo)準(zhǔn)答案2：數(shù)據(jù)項(xiàng)可由若干個(gè)數(shù)據(jù)元素構(gòu)成

標(biāo)準(zhǔn)答案3：數(shù)據(jù)元素

4

標(biāo)準(zhǔn)答案4邏輯結(jié)構(gòu)

標(biāo)準(zhǔn)答案5邏輯上相鄰的元素在物理位置上也相鄰

標(biāo)準(zhǔn)答案6不能隨機(jī)訪問(wèn)任一結(jié)點(diǎn)

標(biāo)準(zhǔn)答案7可讀性

標(biāo)準(zhǔn)答案8算法本身

標(biāo)準(zhǔn)答案9n-i+1

標(biāo)準(zhǔn)答案10:n-i

標(biāo)準(zhǔn)答案11:p->next=q->next

標(biāo)準(zhǔn)答案12:s->next=p->next;p->next=s;

標(biāo)準(zhǔn)答案13:p->next-head

標(biāo)準(zhǔn)答案14:可隨機(jī)訪問(wèn)任一元素

標(biāo)準(zhǔn)答案15:head->next==NULL

標(biāo)準(zhǔn)答案16:20

標(biāo)準(zhǔn)答案17:除了一個(gè)和最后一個(gè)元素外，其余元素都有一個(gè)且僅有一個(gè)直接

前驅(qū)和一個(gè)直接后繼

標(biāo)準(zhǔn)答案1863.5

標(biāo)準(zhǔn)答案19100

標(biāo)準(zhǔn)答案20q->next=p

標(biāo)準(zhǔn)答案21對(duì)

標(biāo)準(zhǔn)答案22錯(cuò)

標(biāo)準(zhǔn)答案23錯(cuò)

標(biāo)準(zhǔn)答案24錯(cuò)

標(biāo)準(zhǔn)答案25錯(cuò)

標(biāo)準(zhǔn)答案26錯(cuò)

標(biāo)準(zhǔn)答案27錯(cuò)

標(biāo)準(zhǔn)答案28對(duì)

標(biāo)準(zhǔn)答案29對(duì)

標(biāo)準(zhǔn)答案30對(duì)

標(biāo)準(zhǔn)答案31錯(cuò)

標(biāo)準(zhǔn)答案32對(duì)

標(biāo)準(zhǔn)答案33對(duì)

標(biāo)準(zhǔn)答案34對(duì)

標(biāo)準(zhǔn)答案35{p->data}{p=p->next}{p!=NULL}

標(biāo)準(zhǔn)答案36{q->next!=NULL}{p=p->next}{q->next=s}

形考2

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

：3,2,1

；3,1,2

；1,3,2

；2,1,3"

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

：1,2,3,4

5

；1,4,3,2

；4,3,2,1

；3,2,4,1"

"題目3：向順序棧中壓入新元素時(shí)，應(yīng)當(dāng)（）。

:先移動(dòng)棧頂指針，再存入元素

;先后次序無(wú)關(guān)緊要

;先存入元素，再移動(dòng)棧頂指針

;同時(shí)進(jìn)行"

"題目4：在一個(gè)棧頂指針為top的鏈棧中，將一個(gè)p指針?biāo)傅慕Y(jié)點(diǎn)入棧，應(yīng)

執(zhí)行（）。

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

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

;top-figtjnext=p;

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

”題目5:在一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用x保存被刪結(jié)點(diǎn)

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

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

;x=top->data;

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

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

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

:rear==m-1

;front-rear+1

;rear=m

;front~rear"

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

:front-rear+1

;rear=MaxSize

;（rear+1）%MaxSize二二front

;rear%MaxSize==front"

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

:top=二n-1

；top!二0

;top二7

;top-0"

”題目9:設(shè)有一個(gè)20階的對(duì)稱矩陣A（第一個(gè)元素為a1,1）,采用壓縮存儲(chǔ)的

方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），

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

:21

；17

；23

；28"

”題目10：在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題時(shí)通常設(shè)置一個(gè)打印

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

6

出數(shù)據(jù)打印，該緩沖區(qū)應(yīng)該是一個(gè)（）結(jié)構(gòu)。

:線性表

;隊(duì)列

;數(shù)組

;堆棧"

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

:迭代部分

;終止條件和迭代部分

;遞歸部分

;終止條件和遞歸部分"

"題目12:在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)

的運(yùn)算為（）。

:r=r->next;

;f=f->next;

;f=r->next;

;r=f->next;"

"題目13:在一個(gè)鏈隊(duì)中，假設(shè)千和r分別為隊(duì)頭和隊(duì)尾指針，則插入s所指結(jié)

點(diǎn)的運(yùn)算為（）。

: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]中存放的是（）。

:字符串的結(jié)束符

;變量h

；"h"

；字符h"

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

（）。

:Bed

;Abe

;BCd

;ABC"

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

的是（）。

:a2

；a1

;a4

;a3"

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

:兩串的長(zhǎng)度相等，并且兩串包含的字符相同

;兩串的長(zhǎng)度相等，并且對(duì)應(yīng)位置上的字符相同

;兩串包含的字符相同

;兩串的長(zhǎng)度相等"

7

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

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

:28

;64

;90

;70"

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

:只能是原子

;不可能是原子

;可以是子表或原子

;只能是子表"

"題目20：對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，可采用三元組表，一個(gè)10行8列的稀疏矩

陣A,其相應(yīng)的三元組表共有6個(gè)元素，矩陣A共有（）個(gè)零元素。

:10

；72

；74

；8"

"題目21:對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，可采用三元組表，一個(gè)10行8列的稀疏矩

陣A共有73個(gè)零元素，A的右下角元素為6,其相應(yīng)的三元組表中的第7個(gè)元素

是（）。

:（10,8,7）

;（7,8,10）

;（10,8,6）

;（7,10,8）"

"題目22：對(duì)一個(gè)棧頂指針為top的鏈棧進(jìn)行入棧操作，通過(guò)指針變量p生成入

棧結(jié)點(diǎn)，并給該結(jié)點(diǎn)賦值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的帶頭結(jié)點(diǎn)的單向鏈表為空的判定條件是（）為真。

:head_>；next!=NULL

;head->next-NULL

;head==NULL

;head->next!=NULL"

"題目24：設(shè)有一個(gè)對(duì)稱矩陣A,采用壓縮存儲(chǔ)的方式，將其下三角部分以行序

為主序存儲(chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開(kāi)始），B數(shù)組共有55個(gè)元素，則該

矩陣是（）階的對(duì)稱矩陣。

:5

；15

；20

；10"

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

8

:"E"

IfII

；n

；字符n

；字符E"

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

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

s->next=hs；"

"題目27:設(shè)有一個(gè)非空的鏈棧，棧頂指針為hs,要進(jìn)行出棧操作，用x

保存出棧結(jié)點(diǎn)的值，棧

結(jié)點(diǎn)的指針域?yàn)閚ext,則可執(zhí)行hs=hs->next;x=hs->data;"

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

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

和h=p;"

題目29:設(shè)有一個(gè)非空的鏈棧，棧頂指針為hs,要進(jìn)行出棧操作，用x保

存出棧結(jié)點(diǎn)的值，棧結(jié)點(diǎn)的指針域?yàn)閚ext,數(shù)據(jù)域?yàn)閐ata,則可執(zhí)行hs=

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

題目30:在一個(gè)鏈隊(duì)中，千和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的指針域?yàn)?/p>

next,則插入所指結(jié)點(diǎn)的操作為r->next=s：r=s;

題目31:在一個(gè)鏈隊(duì)中，千和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的指針域?yàn)?/p>

next,s指向一個(gè)要入隊(duì)的結(jié)點(diǎn)，則入隊(duì)操作為r=s;r->next=s;

題目32:在一個(gè)不帶頭結(jié)點(diǎn)的非空鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，

隊(duì)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閐ata,指針域?yàn)閚ext,若要進(jìn)行出隊(duì)操作，并用變量x存放

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

題目33:對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，可采用三元組表，一個(gè)6行7列的稀疏矩陣

A相應(yīng)的三元組表共有8個(gè)元素，則矩陣A共有34個(gè)零元素。

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

r,當(dāng)（r+1）%MaxSize=f時(shí)表明隊(duì)列已滿。

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

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

題目37:對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包

括該元素的行下標(biāo)、列下標(biāo)、和非零元素值三項(xiàng)信息。

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

”題目39:

設(shè)有n階對(duì)稱矩陣A,用一維數(shù)組s壓縮存儲(chǔ)A的下三角元素，s的下標(biāo)從零開(kāi)

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

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

有效的判斷棧空或棧滿，若隊(duì)頭指針front=4,當(dāng)隊(duì)尾指針rear=3時(shí)隊(duì)滿。

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

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

有5個(gè)元素。

"題目42:以下函數(shù)為鏈棧的進(jìn)棧操作，x是要進(jìn)棧的結(jié)點(diǎn)的數(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ù)為鏈隊(duì)列的入隊(duì)操作，x為要入隊(duì)的結(jié)點(diǎn)的數(shù)據(jù)域的

值，front、rear分別鏈隊(duì)列的隊(duì)頭、隊(duì)尾指針

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)}"

答案

標(biāo)準(zhǔn)答案1:3,1,2

標(biāo)準(zhǔn)答案2：1,2,3,4

標(biāo)準(zhǔn)答案3：先移動(dòng)棧頂指針，再存入元素

標(biāo)準(zhǔn)答案4:p->next=top;top=p;

標(biāo)準(zhǔn)答案5:x=top->data；top=top->next;

標(biāo)準(zhǔn)答案6:front=rear

標(biāo)準(zhǔn)答案7:(rear+1)%MaxSize-front

標(biāo)準(zhǔn)答案8:top==n-1

標(biāo)準(zhǔn)答案9:17

標(biāo)準(zhǔn)答案10:隊(duì)列

10

標(biāo)準(zhǔn)答案11終止條件和遞歸部分

標(biāo)準(zhǔn)答案12f=f->next;

標(biāo)準(zhǔn)答案13r->next=s;r=s;

標(biāo)準(zhǔn)答案14字符串的結(jié)束符

標(biāo)準(zhǔn)答案15Bed

標(biāo)準(zhǔn)答案16:a1

標(biāo)準(zhǔn)答案17兩串的長(zhǎng)度相等，并且對(duì)應(yīng)位置上的字符相同

標(biāo)準(zhǔn)答案1870

標(biāo)準(zhǔn)答案19可以是子表或原子

標(biāo)準(zhǔn)答案2074

標(biāo)準(zhǔn)答案21(10,8,6)

標(biāo)準(zhǔn)答案22p->next=top;top=p;

標(biāo)準(zhǔn)答案23head->next-NULL

標(biāo)準(zhǔn)答案2410

標(biāo)準(zhǔn)答案25字符n

標(biāo)準(zhǔn)答案26錯(cuò)

標(biāo)準(zhǔn)答案27錯(cuò)

標(biāo)準(zhǔn)答案28對(duì)

標(biāo)準(zhǔn)答案29錯(cuò)

標(biāo)準(zhǔn)答案30對(duì)

標(biāo)準(zhǔn)答案31錯(cuò)

標(biāo)準(zhǔn)答案32對(duì)

標(biāo)準(zhǔn)答案33對(duì)

標(biāo)準(zhǔn)答案34對(duì)

標(biāo)準(zhǔn)答案35錯(cuò)

標(biāo)準(zhǔn)答案36對(duì)

標(biāo)準(zhǔn)答案37對(duì)

標(biāo)準(zhǔn)答案38對(duì)

標(biāo)準(zhǔn)答案39錯(cuò)

標(biāo)準(zhǔn)答案40對(duì)

標(biāo)準(zhǔn)答案41對(duì)

標(biāo)準(zhǔn)答案42{A.sizeof(structnode)}{p->next=top}{top=p}

標(biāo)準(zhǔn)答案43{(sizeof(structnode)){rear->next=p}lp)

形考3

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

結(jié)點(diǎn)數(shù)為()O

:16

；15

；17

；47"

"題目2:二叉樹(shù)第k層上最多有()個(gè)結(jié)點(diǎn)。

:2k-1

11

；2k

；2k-1

；2k-1"

"題目3：將含有150個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始，每一層從左到右依

次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào)，根結(jié)點(diǎn)的編號(hào)為1,則編號(hào)為69的結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)

為（）。

:33

；34

;35

;36"

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

長(zhǎng)度最小，則該樹(shù)稱為（）。

:二叉樹(shù)

;平衡二叉樹(shù)

;哈夫曼樹(shù)

;完全二叉樹(shù)"

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

:33

；32

；16

;31"

"題目6：一棵完全二叉樹(shù)共有6層，且第6層上有6個(gè)結(jié)點(diǎn)，該樹(shù)共有（）

個(gè)結(jié)點(diǎn)。

:38

；37

；72

；31"

"題目7：利用3、6、8、12這四個(gè)值作為葉子結(jié)點(diǎn)的權(quán)，生成一棵哈夫曼樹(shù)，

該樹(shù)中所有葉子結(jié)點(diǎn)中的最長(zhǎng)帶權(quán)路徑長(zhǎng)度為（）。

:18

；16

；30

；12"

"題目8:在一棵樹(shù)中，（）沒(méi)有前驅(qū)結(jié)點(diǎn)。

:空結(jié)點(diǎn)

;樹(shù)根結(jié)點(diǎn)

;葉結(jié)點(diǎn)

;分支結(jié)點(diǎn)”

"題目9:設(shè)一棵采用鏈?zhǔn)酱鎯?chǔ)的二叉樹(shù)，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2,該樹(shù)

結(jié)點(diǎn)中共有20個(gè)指針域?yàn)榭?，則該樹(shù)有（）個(gè)葉結(jié)點(diǎn)。

:21

；22

；10

；9"

12

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

:2

；4

；1

:1/2"

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

:鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

;索引存儲(chǔ)結(jié)構(gòu)

;順序存儲(chǔ)結(jié)構(gòu)

;散列存儲(chǔ)結(jié)構(gòu)"

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

:后序

;先序

;層次

;中序"

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

遍歷，則可能得到的一種頂點(diǎn)序列為（）。

:V1V2V4V8V3V5V6V7

;V1V3V6V7V2V4V5V8

;V1V2V4V5V8V3V6V7

;V1V2V4V8V5V3V6V7"

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

遍歷，則可能得到的一種頂點(diǎn)序列為（）。

:aedfcb

;aebcfd

;abecdf

;aecbdf"

"題目15:圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（）的關(guān)系。

:多對(duì)多

;一對(duì)一

；一對(duì)多

;每一個(gè)元素都有一個(gè)且只有一個(gè)直接前驅(qū)和一個(gè)直接后繼"

"題目16:在一棵二叉樹(shù)中，若編號(hào)為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編

號(hào)為（）。

:2i

；2i+2

；2i+1

；2i-1"

"題目17：一棵具有16個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，共有（）層。（設(shè)根結(jié)點(diǎn)在

第一層）

:4

；5

；6

；7"

13

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

序列。

:后序

;按層次

；中序

;前序"

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

:2m

;m/2

;m

;2m+1"

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

有11個(gè)結(jié)點(diǎn)。

題目21：一棵有14個(gè)結(jié)點(diǎn)的完全二叉樹(shù)，則它的最高層上有7個(gè)結(jié)點(diǎn)。

題目22：一棵二叉樹(shù)有6個(gè)葉結(jié)點(diǎn)，則該樹(shù)總共有11個(gè)結(jié)點(diǎn)。

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

題目24：對(duì)于一棵具有n個(gè)結(jié)點(diǎn)的二叉樹(shù)，其相應(yīng)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中共有n-1

個(gè)指針域空。

題目25:設(shè)一棵完全二叉樹(shù)，其最高層上最右邊的葉結(jié)點(diǎn)的編號(hào)為奇數(shù)，

該葉結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為10,該完全二叉樹(shù)一共有21個(gè)結(jié)點(diǎn)。

題目26：設(shè)一棵完全二叉樹(shù)，其最高層上最右邊的葉結(jié)點(diǎn)的編號(hào)為偶數(shù)，

該葉結(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號(hào)為9,該完全二叉樹(shù)一共有19個(gè)結(jié)點(diǎn)。

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

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

題目28:一棵有8個(gè)權(quán)重值構(gòu)造的哈夫曼數(shù)，共有17個(gè)結(jié)點(diǎn)。

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

15個(gè)結(jié)點(diǎn)。

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

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

指向根結(jié)點(diǎn))。完成程序中空格部分。

void

Inorder(structBTreeNode*BT)

(

if(BT!=NULL)

(

Inorder(BT->Ieft);

[[1]]

[[3]]

}

利用上述程序?qū)ψ髨D進(jìn)行后序遍歷，結(jié)果是[[2]]；

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

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

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

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

14

指向根結(jié)點(diǎn))。

voidInorder(structBTreeNode*BT)

if(BT!=NULL){

Inorder(BT->Ieft);}

[[2]];

[[3]]；

}

利用上述程序?qū)τ覉D進(jìn)行中序遍歷，結(jié)果是[[1]];

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

"題目32:(1)以3,4,5,8,9,作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹(shù)。該樹(shù)

的帶權(quán)路徑長(zhǎng)度為{A;B;C;D}.

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

(2)權(quán)重為3的葉結(jié)點(diǎn)的哈夫曼編碼為{A;B;C;D}o

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

"題目33：(1)以2,3,4,7,8,9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹(shù)，該

樹(shù)的帶權(quán)路徑長(zhǎng)度為{A;B；C;D)

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

(2)權(quán)重值為4的葉結(jié)點(diǎn)的哈夫曼編碼為{A;B;C;D}o

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

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

該二叉樹(shù)的根結(jié)點(diǎn)是｛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)已知某二叉樹(shù)的先序遍歷序列是aecdb,中序遍歷序列是eadcb,

該二叉樹(shù)的根結(jié)點(diǎn)是｛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)以給定權(quán)重值5,6,17,18,25,30,為葉結(jié)點(diǎn)，建立一棵哈

夫曼樹(shù)，該樹(shù)的中序遍歷序列為｛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)權(quán)重值為6的葉結(jié)點(diǎn)的哈夫曼為｛A;B;C;D｝.

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

答案

標(biāo)準(zhǔn)答案1:16

標(biāo)準(zhǔn)答案2：2k-1

15

標(biāo)準(zhǔn)答案3:34

標(biāo)準(zhǔn)答案4:哈夫曼樹(shù)

標(biāo)準(zhǔn)答案5:31

標(biāo)準(zhǔn)答案6:37

標(biāo)準(zhǔn)答案7：18

標(biāo)準(zhǔn)答案8:樹(shù)根結(jié)點(diǎn)

標(biāo)準(zhǔn)答案9:10

標(biāo)準(zhǔn)答案102

標(biāo)準(zhǔn)答案11鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

標(biāo)準(zhǔn)答案12先序

標(biāo)準(zhǔn)答案13V1V2V4V8V5V3V6V7

標(biāo)準(zhǔn)答案14aecbdf

標(biāo)準(zhǔn)答案15多對(duì)多

標(biāo)準(zhǔn)答案162i+1

標(biāo)準(zhǔn)答案175

標(biāo)準(zhǔn)答案18中序

標(biāo)準(zhǔn)答案192m

標(biāo)準(zhǔn)答案20對(duì)

標(biāo)準(zhǔn)答案21對(duì)

標(biāo)準(zhǔn)答案22錯(cuò)

標(biāo)準(zhǔn)答案23錯(cuò)

標(biāo)準(zhǔn)答案24錯(cuò)

標(biāo)準(zhǔn)答案25對(duì)

標(biāo)準(zhǔn)答案26錯(cuò)

標(biāo)準(zhǔn)答案27錯(cuò)

標(biāo)準(zhǔn)答案28錯(cuò)

標(biāo)準(zhǔn)答案29對(duì)

標(biāo)準(zhǔn)答案30:{Inorder(BT->right)){printf("%c”,BT->data)}

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

標(biāo)準(zhǔn)答案31:{printf(<<%cw,BT->data)){Inorder(BT->right)}

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

標(biāo)準(zhǔn)答案32:子問(wèn)題1:B;子問(wèn)題2:C

標(biāo)準(zhǔn)答案33:子問(wèn)題1:B;子問(wèn)題2:C

標(biāo)準(zhǔn)答案34:子問(wèn)題1:D;子問(wèn)題2：C

標(biāo)準(zhǔn)答案35:子問(wèn)題1:D；子問(wèn)題2：A

標(biāo)準(zhǔn)答案36:子問(wèn)題1:B;子問(wèn)題2：D

形考4

"題目1：對(duì)線性表進(jìn)行二分查找時(shí)，要求線性表必須（）。

：以鏈接存儲(chǔ)方式

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

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

；以順序存儲(chǔ)方式"

16

"題目2:采用順序查找方法查找長(zhǎng)度為n的線性表時(shí)，每個(gè)元素的平均查找長(zhǎng)

度為（）。

:（n-1）/2

;（n+1）/2

;n/2

；n"

"題目3:有一個(gè)長(zhǎng)度為10的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情

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

:29/10

；26/10

；31/10

；29/9"

"題目4：已知一個(gè)有序表為{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ù)開(kāi)始逐個(gè)插入數(shù)據(jù)來(lái)形

成二叉排序樹(shù)，若希望高度最小，應(yīng)該選擇的序列是（）。

: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:對(duì)于順序存儲(chǔ)的有序表{5,12,20,26,37,42,46,50,64},若采用折半

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

:6

；4

；5

；3"

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

是（）。

:直接選擇排序

;希爾排序

；冒泡排序

;直接插入排序”

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

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

:選擇排序

;插入排序

;交換排序

;歸并排序"

"題目9：依次將每?jī)蓚€(gè)相鄰的有序表合并成一個(gè)有序表的排序方法稱為（）。

:選擇排序

17

;交換排序

;插入排序

;歸并排序"

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

:交換排序

;選擇排序

;歸并排序

;插入排序"

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

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

錄的關(guān)鍵字，這種排序稱為（）。

:歸并排序

;快速排序

;插入排序

;堆排序"

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

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

: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時(shí)，經(jīng)（）次比較后查找成功。

:3

；5

；4

；2"

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

行排序，要把第七個(gè)元素47插入到已排序中，為尋找插入的合適位置需要進(jìn)行

（）次元素間的比較。

:5

；6

；4

；3"

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

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

:插入

；歸并

;快速

;選擇”

"題目16:一組記錄的關(guān)鍵字序列為（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:一組記錄的關(guān)鍵字序列為（25,48,16,35,79,82,23,40,36,

72）,其中，含有5個(gè)長(zhǎng)度為2的有序表，按歸并排序的方法對(duì)該序列進(jìn)行一趟

歸并后的結(jié)果為（)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個(gè)數(shù)據(jù)元素為（54,28,16,34,73,62,95,60,26,43),

對(duì)該數(shù)列從小到大排序,經(jīng)過(guò)一趟冒泡排序后的序列為()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：一組記錄的關(guān)鍵字序列為（46,79,56,38,40,84）,利用快速排

序，以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過(guò)一次劃分后結(jié)果為（）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:一組記錄的關(guān)鍵字序列為（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ù)是二叉排序樹(shù)的查找算法，若二叉樹(shù)為空，則返回根結(jié)

點(diǎn)的指針，否則，返回值是指向樹(shù)結(jié)點(diǎn)的結(jié)構(gòu)指針p（查找成功p指向查到的樹(shù)

結(jié)點(diǎn)，不成功p指向?yàn)镹ULL）完成程序中的空格

typedefstructBnode

{intkey;

structBnode*Ieft;

structBnode*right;

}Bnode;

Bnode*BSearch(Bnode*bt,intk)

/*bt用于接收二叉排序樹(shù)的根結(jié)點(diǎn)的指針，k用以接收要查找的關(guān)鍵字*/

{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：以下程序是折半插入排序的算法

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

要把a(bǔ)插入到已經(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)設(shè)查找表為(1,10,11,14,23,27,29,55,68),畫出對(duì)上述查

找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(shù)，為了成功查找到元素14,需要依次與元素{A；

B；C；D}進(jìn)行比較。

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)一組記錄的關(guān)鍵字序列為(47,80,57,39,41,46),利

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

形式建堆)。

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)對(duì)關(guān)鍵字序列(56,51,71,54,46,106),利用快速排序，以第

一個(gè)關(guān)鍵字為分割元素，經(jīng)過(guò)一次劃分后結(jié)果為{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)一組記錄的關(guān)鍵字序列為(60,47,80,57,39,41,46,30),利用歸

并排序的方法，經(jīng)過(guò)(2,2)歸并的結(jié)果序列為(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)對(duì)關(guān)鍵字序列(36,69,46,28,30,74)采用快速排序，以第一

個(gè)關(guān)鍵字為分割元素，經(jīng)過(guò)一次劃分后的結(jié)果序列為｛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)用冒泡法對(duì)上述序列排序，經(jīng)兩越冒泡的結(jié)果序列為｛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)一組記錄的關(guān)鍵字序列為｛45,40,65,43,35,95｝寫出利

用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一趟劃分的結(jié)果為｛A;B;C;D｝;

A.354065453595

B.354065434595

C.354043456595

D.354045436595

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

次元素間的比較。

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

答案

標(biāo)準(zhǔn)答案1:以順序存儲(chǔ)方式，且數(shù)據(jù)元素有序

標(biāo)準(zhǔn)答案2:(n+1)/2

標(biāo)準(zhǔn)答案3:29/10

標(biāo)準(zhǔn)答案4:5

標(biāo)準(zhǔn)答案5:37,24,12,30,53,45,96

標(biāo)準(zhǔn)答案6:4

標(biāo)準(zhǔn)答案7：直接選擇排序

標(biāo)準(zhǔn)答案8:插入排序

標(biāo)準(zhǔn)答案9:歸并排序

標(biāo)準(zhǔn)答案10:交換排序

標(biāo)準(zhǔn)答案11:快速排序

標(biāo)準(zhǔn)答案12：40,20,30,38,46,56,79,84,90,110

標(biāo)準(zhǔn)答案13：3

標(biāo)準(zhǔn)答案14：5

標(biāo)準(zhǔn)答案15：選擇

標(biāo)準(zhǔn)答案16：18,20,25,59,26,36

標(biāo)準(zhǔn)答案17:16,25,35,48,23,40,79,82,36,72

標(biāo)準(zhǔn)答案18：28,16,34,54,62,73,60,26,43,95

21

標(biāo)準(zhǔn)答案1940,38,46,56,79,84

標(biāo)準(zhǔn)答案2039,46,41,57,80,47

標(biāo)準(zhǔn)答案21{NULL}{k}{p=p->left}{p=p->right}{p}

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

標(biāo)準(zhǔn)答案23子問(wèn)題1:C:子問(wèn)題2:B

標(biāo)準(zhǔn)答案24子問(wèn)題1:B:子問(wèn)題2:A

標(biāo)準(zhǔn)答案25子問(wèn)題1:0;子問(wèn)題2:D

標(biāo)準(zhǔn)答案26子問(wèn)題1:D:子問(wèn)題2:A

標(biāo)