信息技術(shù)類-題庫-數(shù)據(jù)結(jié)構(gòu)與算法分析練習(xí)題

1、計(jì)算機(jī)類計(jì)算機(jī)類-數(shù)據(jù)結(jié)構(gòu)與算法分析練習(xí)題數(shù)據(jù)結(jié)構(gòu)與算法分析練習(xí)題 1. 第一章第一章 1.1 基本概念題基本概念題 1線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ ）的關(guān)系。 【B】 A一對(duì)多 B一對(duì)一 C多對(duì)多 D每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼 注：注：D D 選不全的，第一個(gè)元素就木有前驅(qū)，最后一個(gè)元素就木有后繼。選不全的，第一個(gè)元素就木有前驅(qū)，最后一個(gè)元素就木有后繼。 2數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的（ ）結(jié)構(gòu)。 【D】 A物理 B存儲(chǔ) C邏輯與物理 D邏輯 3結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱為_結(jié)構(gòu)。 【線性】 4數(shù)據(jù)元素是數(shù)據(jù)的基本單位，它（ ） 。 【C】 A只能有

2、一個(gè)數(shù)據(jù)項(xiàng)組成 B至少有二個(gè)數(shù)據(jù)項(xiàng)組成 C可以是一個(gè)數(shù)據(jù)項(xiàng)也可以由若干個(gè)數(shù)據(jù)項(xiàng)組成 D至少有一個(gè)數(shù)據(jù)項(xiàng)為指針類型 5 一種邏輯結(jié)構(gòu)（ ）存儲(chǔ)結(jié)構(gòu)。 【A】 A可以有不同的 B只能有唯一的 C的數(shù)據(jù)元素在計(jì)算機(jī)中的表示稱為 D的數(shù)據(jù)元素之間的關(guān)系稱為 1.2 邏邏輯結(jié)構(gòu)輯結(jié)構(gòu)題題 1通常數(shù)據(jù)的邏輯結(jié)構(gòu)包括_、_、_、_四種類型。 書誠教育專營店 【集合；線性；樹形；圖狀】 2通?？梢园岩槐竞胁煌鹿?jié)的書的目錄結(jié)構(gòu)抽象成_結(jié)構(gòu)。 【樹形】 3通?？梢园涯吵鞘兄懈鞴徽军c(diǎn)間的線路圖抽象成_結(jié)構(gòu)。 【圖狀】 4結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為_結(jié)構(gòu)。 【圖狀（網(wǎng)狀） 】 5結(jié)構(gòu)中的數(shù)據(jù)元素存在一

3、對(duì)多的關(guān)系稱為_結(jié)構(gòu)。 【樹形】 6結(jié)構(gòu)中的數(shù)據(jù)元素存在一對(duì)一的關(guān)系稱為_結(jié)構(gòu)。 【線性】 1.3 物理結(jié)構(gòu)題物理結(jié)構(gòu)題 1把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱稱為物理（ ）結(jié)構(gòu)。 【存儲(chǔ)】 2把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中,并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為_結(jié)構(gòu)。 （物理（存儲(chǔ)） ） 1.4 算法特性題算法特性題 1以下特征中， （ ）不是算法的特性。 【C】 A有窮性 B確定性 C有 0 個(gè)或多個(gè)輸出 D可行性 2算法的時(shí)間復(fù)雜度與（ ）有關(guān)。 【D】 A所使用的計(jì)算機(jī) B與計(jì)算機(jī)的操作系統(tǒng) C與數(shù)據(jù)結(jié)構(gòu) D與算法本身 3要求在 n 個(gè)數(shù)據(jù)元素中找其中值最大的元素，設(shè)基本操作為元素間

4、的比較。則比較的次數(shù)和算法 的時(shí)間復(fù)雜度分別為_和 O(n)。 【n-1】 2. 線性表線性表 2.1 基本概念題基本概念題 1針對(duì)線性表，在存儲(chǔ)后如果最常用的操作是取第 i 個(gè)結(jié)點(diǎn)及其前驅(qū)，則采用（ ）存儲(chǔ)方式最 節(jié)省時(shí)間。 【B】 A單鏈表 B順序表 C單循環(huán)鏈表 D雙鏈表 2.2 順序表順序表 1設(shè)有一個(gè)長度為 n 的順序表，要在第 i 個(gè)元素之前（也就是插入元素作為新表的第 i 個(gè)元素） ，則 移動(dòng)元素個(gè)數(shù)為（ ） 。 【A】 An-i+1 Bn-i Cn-i-1 Di 書誠教育專營店 注：元素要插入到注：元素要插入到 i 的位置，不動(dòng)的是前面的位置，不動(dòng)的是前面 i-1 個(gè)元素，總元

5、素有個(gè)元素，總元素有 n 個(gè)，要移動(dòng)的元素個(gè)數(shù)是：個(gè)，要移動(dòng)的元素個(gè)數(shù)是： n-(i-1) 即：即： n- i +1 2. 設(shè)順序存儲(chǔ)的線性表長度為 n，對(duì)于插入操作，設(shè)插入位置是等概率的，則插入一個(gè)元素平均移動(dòng) 元素的次數(shù)為（ ） 。 【A】 An/2 Bn Cn-1 Dn-i+1 3 .設(shè)順序存儲(chǔ)的線性表長度為 n，對(duì)于刪除操作，設(shè)刪除位置是等概率的，則刪除一個(gè)元素平均移動(dòng) 元素的次數(shù)為（ ） 。 【A】 A(n+1)/2 Bn C2n Dn-i 4線性表的順序結(jié)構(gòu)中， （ ） 。 【C】 A邏輯上相鄰的元素在物理位置上不一定相鄰 B數(shù)據(jù)元素是不能隨機(jī)訪問的 C邏輯上相鄰的元素在物理位置上

6、也相鄰 D進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高 2.3 鏈表鏈表概念題概念題 1鏈表所具備的特點(diǎn)是（ ） 。 【D】 A可以隨機(jī)訪問任一結(jié)點(diǎn) B占用連續(xù)的存儲(chǔ)空間 C可以通過下標(biāo)對(duì)鏈表進(jìn)行直接訪問 D插入刪除元素的操作不需要移動(dòng)元素結(jié)點(diǎn) 2線性表采用鏈?zhǔn)酱鎯?chǔ)時(shí)，其地址（ ） 。 【C】 A一定是不連續(xù)的 B必須是連續(xù)的 C可以連續(xù)也可以不連續(xù) D部分地址必須是連續(xù)的 3設(shè)有一個(gè)不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)?next，指針 p 指向尾結(jié)點(diǎn)，現(xiàn)要使 p 指向 第一個(gè)結(jié)點(diǎn)，可用語句_。 【p=p-next;】 4在雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向_，另一個(gè)指向_。 【結(jié)點(diǎn)的直接后繼

7、 結(jié)點(diǎn)的直接前驅(qū)】 5以下說法中不正確的是（ ） 。 【B】 A雙向循環(huán)鏈表中每個(gè)結(jié)點(diǎn)需要包含兩個(gè)指針域 B已知單向鏈表中任一結(jié)點(diǎn)的指針就能訪問到鏈表中每個(gè)結(jié)點(diǎn) C順序存儲(chǔ)的線性鏈表是可以隨機(jī)訪問的 D單向循環(huán)鏈表中尾結(jié)點(diǎn)的指針域中存放的是頭指針 6以下表中可以隨機(jī)訪問的是（ ） 。 【D】 A單向鏈表 B雙向鏈表 C單向循環(huán)鏈表 D順序表 書誠教育專營店 2.4 鏈表指針題鏈表指針題 基本圖形： 1在一個(gè)單鏈表中，p、q 分別指向表中兩個(gè)相鄰的結(jié)點(diǎn)，且 q 所指結(jié)點(diǎn)是 p 所指結(jié)點(diǎn)的直接后繼， 現(xiàn)要?jiǎng)h除 q 所指結(jié)點(diǎn)，可用的語句是（ ） 。 【C】 Ap=q-next Bp-next=q C

8、p-next=qnext Dq-next=NULL 2在雙向鏈表中，每個(gè)結(jié)點(diǎn)有兩個(gè)指針域，一個(gè)指向結(jié)點(diǎn)的直接后繼，另一個(gè)指向_。 【結(jié)點(diǎn)的直接前驅(qū)】 3設(shè)有一個(gè)頭指針為 head 的單向循環(huán)鏈表，p 指向鏈表中的結(jié)點(diǎn)，若 p-next=_，則 p 所指 結(jié)點(diǎn)為尾結(jié)點(diǎn)。 【 head 】 4設(shè)有一個(gè)頭指針為 head 的單向鏈表，p 指向表中某一個(gè)結(jié)點(diǎn)，且有 p-next=NULL,通過操作 _，就可使該單向鏈表構(gòu)造成單向循環(huán)鏈表。 【p-next=head;】 5帶頭結(jié)點(diǎn)的單向鏈表的頭指針為 head，該鏈表為空的判定條件是（ ）的值為真。 【C】 Ahead = = NULL Bhead-n

9、ext= =head Chead-next= = NULL Dhead = =head-next 6雙向循環(huán)鏈表結(jié)點(diǎn)的數(shù)據(jù)類型為： 【B】 struct node int data; struct node *next; /*指向直接后繼*/ struct node *prior; ； 設(shè) p 指向表中某一結(jié)點(diǎn)， 要顯示 p 所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的數(shù)據(jù)元素， 可用操作 （ ） 。 Aprintf(“%d”,p-next-data); Bprintf(“%d”,p-prior-data); Cprintf(“%d”,p-prior-next); Dprintf(“%d”,p-data); 7要

10、在一個(gè)帶頭結(jié)點(diǎn)的單向循環(huán)鏈表中刪除頭結(jié)點(diǎn)，得到一個(gè)新的不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，若 結(jié)點(diǎn)的指針域?yàn)?next，頭指針為 head，尾指針為 p，則可執(zhí)行 head=head- next; _。 【p-next=head； 】 書誠教育專營店 8設(shè)有一個(gè)頭指針為 head 的單向鏈表，p 指向表中某一個(gè)結(jié)點(diǎn)，且有 p-next= =NULL,通過操作 _，就可使該單向鏈表構(gòu)造成單向循環(huán)鏈表。 【p-next=head;】 9雙向循環(huán)鏈表中，p 指向表中某結(jié)點(diǎn)，則通過 p 可以訪問到 p 所指結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)和直接前驅(qū) 結(jié)點(diǎn)，這種說法是_的（回答正確或不正確） 。 【正確】 10設(shè)有一個(gè)單向鏈表

11、，結(jié)點(diǎn)的指針域?yàn)?next，頭指針為 head，p 指向尾結(jié)點(diǎn)，為了使該單向鏈表改 為單向循環(huán)鏈表，可用語句_。 【p-next=head;】 11設(shè)有一個(gè)單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)?next，頭指針為 head，指針 p 指向表中某結(jié)點(diǎn)，若邏 輯表達(dá)式_的結(jié)果為真，則 p 所指結(jié)點(diǎn)為尾結(jié)點(diǎn)。 【p-next= =head;】 12設(shè)有一個(gè)單向循環(huán)鏈表，頭指針為 head，鏈表中結(jié)點(diǎn)的指針域?yàn)?next，p 指向尾結(jié)點(diǎn)的直接前驅(qū) 結(jié)點(diǎn)，若要?jiǎng)h除尾結(jié)點(diǎn)，得到一個(gè)新的單向循環(huán)鏈表，可執(zhí)行操作_。 【p-next=head； 】 13要在一個(gè)單向鏈表中 p 所指向的結(jié)點(diǎn)之后插入一個(gè) s 所指向的新

12、結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)?next，可執(zhí)行_和 p-next=s;的操作。 【s-next= p-next； 】 14要在一個(gè)單向鏈表中刪除 p 所指向的結(jié)點(diǎn)，已知 q 指向 p 所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若鏈表中結(jié) 點(diǎn)的指針域?yàn)?next，則可執(zhí)行_。 【q-next= p-next； 】 2.5 鏈表鏈表編程題編程題 1編程題編程題 以下是用頭插法建立帶頭結(jié)點(diǎn)且有 n 個(gè)結(jié)點(diǎn)的單向鏈表的程序，要求結(jié)點(diǎn)中的數(shù)據(jù)域從前 向后依次為 n,n-1,1，完成程序中空格部分。 NODE *create2(n) NODE *head , *p, *q; int i; p=(NODE*)malloc(s

13、izeof(NODE); p-next=NULL; head=（1） ; （2） ; for(i=1; idata=i; if(i= =1) p-next=NULL; else p-next= （4） ; q-next= （5） ; return(head); 下面答案：下面答案： （1）p （2）q=p 書誠教育專營店 （3）(NODE*)malloc(sizeof(NODE) （4）q-next （5）p 2編程題編程題 以下函數(shù)在 head 為頭指針的具有頭結(jié)點(diǎn)的單向鏈表中刪除第 i 個(gè)結(jié)點(diǎn)， struct node int data; struct node *next; ; type

14、def struct node NODE int delete(NODE *head,int i ) NODE *p,*q; int j; q=head; j=0; while(q!=NULL) j+; if(q=NULL) return(0); p= _(3)_; _(4)_=p-next; free(_(5)_); return(1); 下面答案：下面答案： （1）jnext （3）q-next （4）q-next （5）p 3. 棧和隊(duì)列棧和隊(duì)列 3.1 棧棧的概念題的概念題 1棧的插入刪除操作在（ ）進(jìn)行。 【B】 A棧底 B棧頂 C任意位置 D指定位置 2以下說法正確的是（ ） 。

15、【C】 A棧的特點(diǎn)是先進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)后出 B棧和隊(duì)列的特點(diǎn)都是先進(jìn)后出 C棧的特點(diǎn)是先進(jìn)后出，隊(duì)列的特點(diǎn)是先進(jìn)先出 D棧和隊(duì)列的特點(diǎn)都是先進(jìn)先出 3棧和隊(duì)列的相同點(diǎn)是（ ） 。 【D】 A都是后進(jìn)先出 B都是后進(jìn)后出 書誠教育專營店 C邏輯結(jié)構(gòu)與線性表不同 D邏輯結(jié)構(gòu)與線性表相同，都是操作規(guī)則受到限制的線性表 3.2 進(jìn)棧出棧題進(jìn)棧出棧題 1元素 3，6，9 按順序依次進(jìn)棧，則該棧的不可能輸出序列是（ ） （進(jìn)棧出棧可以交替進(jìn)行） 。 A9，3，6 B9，6，3 【A】 C6，3，9 D3，9，6 2元素 2，4，6，8 按順序依次進(jìn)棧，則該棧的不可能輸出序列是（ ） （進(jìn)棧出?？梢?/p>

16、交替進(jìn)行） 。 【D】 A8，6，4，2 B2，4，6，8 C4，2，8，6 D8，6，2，4 3一個(gè)棧的進(jìn)棧序列是 5，6，7，8，則棧的不可能的出棧序列是（ ） （進(jìn)出棧操作可以交替進(jìn) 行） 【A】 A5，8，6，7 B7，6，8，5 C7，6，5，8 D8，7，6，5 4. 一個(gè)棧的進(jìn)棧序列是 efgh，則棧的不可能的出棧序列是（ ） （進(jìn)出棧操作可以交替進(jìn)行） 。 【D】 Ahgfe Bgfeh Cfgeh Dehfg 3.3 鏈棧指針題鏈棧指針題 1從一個(gè)棧頂指針為 h 的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用 x 保存被刪結(jié)點(diǎn)的值，可執(zhí)行 x=h-data;和 _。(結(jié)點(diǎn)的指針域?yàn)?next)

17、【h=h-next;】 2向一個(gè)棧頂指針為 h 的鏈棧中插入一個(gè) s 所指結(jié)點(diǎn)時(shí)，可執(zhí)行_和 h=s;。 【s-next=h;】 3從一個(gè)棧頂指針為 h 的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用 x 保存被刪結(jié)點(diǎn)的值，可執(zhí)行_和 h=h-next;。(結(jié)點(diǎn)的指針域?yàn)?next) 【x=h-data;】 4設(shè)有一個(gè)非空的鏈棧，棧頂指針為 hs，要進(jìn)行出棧操作，用 x 保存出棧結(jié)點(diǎn)的值，棧結(jié)點(diǎn)的指針 域?yàn)?next，數(shù)據(jù)域?yàn)?data，則可執(zhí)行 x= _；和 hs= _； 【hs-data; hs-next;】 5設(shè) top 是一個(gè)鏈棧的棧頂指針，棧中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域 data 和指針域 next 組成，設(shè)

18、用 x 接 書誠教育專營店 收棧頂元素，則出棧操作為（ ） 。 【A】 Ax=top-data;top=top-next; Btop=top-next;x=top-data; Cx=top- next;top=top- data; Dtop-next =top; x=top-data; 6設(shè) top 是一個(gè)鏈棧的棧頂指針，棧中每個(gè)結(jié)點(diǎn)由一個(gè)數(shù)據(jù)域 data 和指針域 next 組成，設(shè)用 x 接 收棧頂元素，則取棧頂元素的操作為（ ） 。 【C】 Atop-data= x; Btop=top-next; Cx=top-data; Dx=top-data; top= top-next; 11C

19、12C 13D 14B 15A 7設(shè)有一個(gè)鏈棧，棧頂指針為 hs，現(xiàn)有一個(gè) s 所指向的結(jié)點(diǎn)要入棧，則可執(zhí)行操作 s- next=hs; _。 【hs=s； 】 8設(shè)有一個(gè)非空的鏈棧，棧頂指針為 hs，要進(jìn)行出棧操作，用 x 保存出棧結(jié)點(diǎn)的值，棧結(jié)點(diǎn)的指針 域?yàn)?next，則可執(zhí)行 x=hs-data; _。 【hs=hs-next;】 9設(shè)有一個(gè)鏈棧，棧頂指針為 hs，現(xiàn)有一個(gè) s 所指向的結(jié)點(diǎn)要入棧，則可執(zhí)行操作_ 和 hs=s； 【s-next=hs;】 3.4 鏈棧編鏈棧編程題程題 1編程題編程題 以下函數(shù)為鏈棧的進(jìn)棧操作，x 是要進(jìn)棧的結(jié)點(diǎn)的數(shù)據(jù)域，top 為棧頂指針 struct

20、node ElemType data; struct node *next; ; struct node *top ; void Push(ElemType x) struct node *p; p=(struct node*)malloc(_(1)_); p-data=x; _(2)_; _(3)_; 下面答案：下面答案： （1）sizeof (struct node) （2）p-next=top （3）top=p 3.5 隊(duì)列隊(duì)列概念題概念題 1隊(duì)列的刪除操作在（ ）進(jìn)行。 【A】 A隊(duì)頭 B隊(duì)尾 C隊(duì)頭或隊(duì)尾 D在任意指定位置 2以下說法正確的是（ ） 。 【C】 A隊(duì)列是后進(jìn)先出 B棧

21、的特點(diǎn)是后進(jìn)后出 C棧的刪除和插入操作都只能在棧頂進(jìn)行 書誠教育專營店 D隊(duì)列的刪除和插入操作都只能在隊(duì)頭進(jìn)行 3以下說法不正確的是（ ） 。 【C】 A棧的特點(diǎn)是后進(jìn)先出 B隊(duì)列的特點(diǎn)是先進(jìn)先出 C棧的刪除操作在棧底進(jìn)行，插入操作在棧頂進(jìn)行 D隊(duì)列的插入操作在隊(duì)尾進(jìn)行，刪除操作在隊(duì)頭進(jìn)行 4在隊(duì)列的順序存儲(chǔ)結(jié)構(gòu)中，當(dāng)插入一個(gè)新的隊(duì)列元素時(shí)， 指針的值增 1，當(dāng)刪除一個(gè)元素隊(duì) 列時(shí)， 指針的值增 1。 【尾 頭】 3.6 鏈隊(duì)指針題鏈隊(duì)指針題 1在一個(gè)鏈隊(duì)中，假設(shè) f 和 r 分別為隊(duì)頭和隊(duì)尾指針，則刪除一個(gè)結(jié)點(diǎn)的運(yùn)算為（ ） 。 【D】 Ar=f-next; Br=r-next; Cf=r-

22、next; Df=f-next; 2 在一個(gè)鏈隊(duì)中， 設(shè) f 和 r 分別為隊(duì)頭和隊(duì)尾指針， 則插入 s 所指結(jié)點(diǎn)的操作為_和 r=s; (結(jié) 點(diǎn)的指針域?yàn)?next) 【r-next=s;】 3 在一個(gè)鏈隊(duì)中， f 和 r 分別為隊(duì)頭和隊(duì)尾指針， 隊(duì)結(jié)點(diǎn)的指針域?yàn)?next， s 指向一個(gè)要入隊(duì)的結(jié)點(diǎn)， 則入隊(duì)操作為_；_； 【r-next=s；r=s； 】 4在一個(gè)鏈隊(duì)中，f 和 r 分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的指針域?yàn)?next，則插入一個(gè) s 所指結(jié)點(diǎn) 的操作為_；r=s； 【r-next=s】 5棧和隊(duì)列的操作特點(diǎn)分別是_和 _。 【先進(jìn)后出（后進(jìn)先出） 先進(jìn)先出 （后進(jìn)后出） 】

23、 6在一個(gè)不帶頭結(jié)點(diǎn)的非空鏈隊(duì)中，f 和 r 分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)?data，指針 域?yàn)?next，若要進(jìn)行出隊(duì)操作，并用變量 x 存放出隊(duì)元素的數(shù)據(jù)值，則相關(guān)操作為_; _。 【x=f-data; f=f-next;】 7綜合題綜合題（1）設(shè) head1 和 p1 分別是不帶頭結(jié)點(diǎn)的單向鏈表 A 的頭指針和尾指針，head2 和 p2 分別 是不帶頭結(jié)點(diǎn)的單向鏈表 B 的頭指針和尾指針，若要把 B 鏈表接到 A 鏈表之后，得到一個(gè)以 head1 為頭指 針的單向循環(huán)鏈表，寫出其中兩個(gè)關(guān)鍵的賦值語句（不用完整程序，結(jié)點(diǎn)的鏈域?yàn)?next） 。 （2）單向鏈表的鏈域?yàn)?next

24、，設(shè)指針 p 指向單向鏈表中的某個(gè)結(jié)點(diǎn)，指針 s 指向一個(gè)要插入鏈表 的新結(jié)點(diǎn)，現(xiàn)要把 s 所指結(jié)點(diǎn)插入 p 所指結(jié)點(diǎn)之后，某學(xué)生采用以下語句： p-next=s; s-next=p-next; 這樣做正確嗎？若正確則回答正確，若不正確則說明應(yīng)如何改寫 下面答案：下面答案： （1）p1-next= head2；p2-next= head1； （2）不對(duì)，s-next= p-next；p-next=s； 3.7 鏈隊(duì)編程題鏈隊(duì)編程題 1編程題編程題 以下函數(shù)為鏈隊(duì)列的入隊(duì)操作，x 為要入隊(duì)的結(jié)點(diǎn)的數(shù)據(jù)域的值，front、rear 分別是鏈隊(duì)列 的隊(duì)頭、隊(duì)尾指針 struct node ElemT

25、ype data; struct node *next; 書誠教育專營店 ; struct node *front，*rear; void InQueue(ElemType x) struct node *p; p= (struct node*) _(1)_; p-data=x; p-next=NULL; _(2)_; rear= _(3)_; 下面答案：下面答案： （1）malloc(sizeof (struct node) （2）rear-next=p （3）p 2 編程題編程題 以下函數(shù)為鏈隊(duì)列的出隊(duì)操作 （鏈隊(duì)列帶有頭結(jié)點(diǎn)） ， 出隊(duì)結(jié)點(diǎn)的數(shù)據(jù)域的值由 x 返回， front、 rea

26、r 分別是鏈隊(duì)列的隊(duì)頭、隊(duì)尾指針 struct node ElemType data; struct node *next; ; struct node *front，*rear; ElemType OutQueue() ElemType x; if(_(1)_) printf(隊(duì)列下溢錯(cuò)誤！隊(duì)列下溢錯(cuò)誤！n); exit(1); else struct node *p=front-next; x=p-data; front-next= _(2)_; if(p-next=NULL) rear=front; free(p); _(3)_; 下面答案：下面答案： （1）front= =rear （

27、2）p-next （3）return(x) 3.8 循環(huán)隊(duì)列題循環(huán)隊(duì)列題 1循環(huán)隊(duì)列的隊(duì)頭指針為 f，隊(duì)尾指針為 r，當(dāng)_ _時(shí)表明隊(duì)列為空。 【r= =f】 2循環(huán)隊(duì)列的最大存儲(chǔ)空間為 MaxSize=6，采用少用一個(gè)元素空間以有效地判斷?？栈驐M，若隊(duì)頭 書誠教育專營店 指針 front=4，當(dāng)隊(duì)尾指針 rear= _時(shí)隊(duì)滿，隊(duì)列中共有_個(gè)元素。 【3；5】 3循環(huán)隊(duì)列的最大存儲(chǔ)空間為 MaxSize=8，采用少用一個(gè)元素空間以有效的判斷棧空或棧滿，若隊(duì)頭 指針 front=4，則當(dāng)隊(duì)尾指針 rear= _時(shí)，隊(duì)列為空，當(dāng) rear= _時(shí)，隊(duì)列有 6 個(gè)元素。 【4；2】 4循環(huán)隊(duì)列的引

28、入，目的是為了克服_ 。 【假上溢】 5循環(huán)隊(duì)列的最大存儲(chǔ)空間為 MaxSize，隊(duì)頭指針為 f，隊(duì)尾指針為 r，當(dāng)_時(shí)表明隊(duì)列已滿。 【 （r+1）% MaxSize = f 】 4. 串串 4.1 串的基本概念串的基本概念 性質(zhì)： “”雙引號(hào)內(nèi)的字符串是以0表示結(jié)束的。要多占一個(gè)字節(jié)。 1在 C 語言中，順序存儲(chǔ)長度為 3 的字符串，需要占用（ ）個(gè)字節(jié)。 【】 A3 B4 C6 D12 2在 C 語言中，利用數(shù)組 a 存放字符串“Hello” ，以下語句中正確的是（ ） 。 【A】 Achar a10= “Hello”; Bchar a10; a=“Hello”; Cchar a10=

29、Hello; Dchar a10=H,e,l,l,o; 3兩個(gè)串相等的充分必要條件是_。 【串長度相等且對(duì)應(yīng)位置的字符相等】 4串的兩種最基本的存儲(chǔ)方式是_和 _。 【順序存儲(chǔ) 鏈?zhǔn)酱鎯?chǔ)】 5 A在存儲(chǔ)時(shí)占_個(gè)字節(jié)。 “A”在存儲(chǔ)時(shí)占_個(gè)字節(jié)。 【1；2】 6. 順序存儲(chǔ)字符串“ABCD”需要占用_個(gè)字節(jié)。 【5】 4.2 串函數(shù)串函數(shù) 性質(zhì) StrCmp 函數(shù)有三個(gè)結(jié)果： 第一個(gè)字符串大于第二個(gè)字符串，結(jié)果：1 第一個(gè)字符串等于第二個(gè)字符串，結(jié)果：0 第一個(gè)字符串小于第二個(gè)字符串，結(jié)果：-1 對(duì)應(yīng)位置比較，根據(jù) ASCII 碼進(jìn)行比較。 數(shù)字編碼最小，其次大寫字母，其后是小寫字母。 1串函數(shù)

30、 StrCmp（ “d” ， “D” ）的值為（ ） 。 【B】 A0 B1 C-1 D3 書誠教育專營店 2串函數(shù) StrCmp(“abA”,”aba”)的值為（ ） 。 【D】 A1 B0 C “abAaba” D-1 4.5 串的編程題串的編程題 1程序段 int count=0; char *s=” ABCD”; while(*s!=0)s+;count+; 執(zhí)行后 count= _ _ 【4】 2char *p; 【B】 p=StrCat(“ABD”,”ABC”); Printf(“%s”,p); 的顯示結(jié)果為（ ） 。 A-1 BABDABC CAB D1 3程序段 char *s

31、=”aBcD”;n=0; while(*s!=0) if(*sa s+; 執(zhí)行后 n= _ _ 【2】 5. 數(shù)組和廣義表數(shù)組和廣義表 5.1 數(shù)組數(shù)組坐標(biāo)換算題坐標(biāo)換算題 三個(gè)公式： 對(duì)稱矩陣：P77 下三角矩陣：P77 對(duì)角矩陣：P78 1設(shè)有一個(gè) 10 階的對(duì)稱矩陣 A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹鞔鎯?chǔ)到一維數(shù)組 B 中（數(shù)組下標(biāo)從 1 開始） ，則矩陣中元素 A8,5 在一維數(shù)組 B 中的下標(biāo)是（ ） 。 【A】 A33 B32 C85 D41 2設(shè)有一個(gè) 15 階的對(duì)稱矩陣 A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組 B 中（數(shù)組下標(biāo)從 1 開始

32、） ，則矩陣中元素 a7,6 在一維數(shù)組 B 中的下標(biāo)是（ ） 。 【C】 書誠教育專營店 A42 B13 C27 D32 3設(shè)有一個(gè) 15 階的對(duì)稱矩陣 A，采用壓縮存儲(chǔ)方式將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組 b 中。 （矩陣 A 的第一個(gè)元素為 a1,1，數(shù)組 b 的下標(biāo)從 1 開始） ，則數(shù)組元素 b13對(duì)應(yīng) A 的矩陣元素 是（ ） 。 【A】 Aa5,3 Ba6,4 Ca7,2 Da6,8 4設(shè)有 n 階對(duì)稱矩陣 A，用數(shù)組 S 進(jìn)行壓縮存儲(chǔ)，當(dāng) idata) （2）Preorder(BT-left) （3）Preorder(BT-right) 2編程題編程題 以下程序是后序遍

33、歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中，左、右 指針域分別為 left 和 right，數(shù)據(jù)域 data 為字符型，BT 指向根結(jié)點(diǎn)） 。 void Postorder (struct BTreeNode *BT) if(BT!=NULL) （1） ; 書誠教育專營店 （2） ; （3） ; 下面答案：下面答案： （1）Postorder(BT-left) （2）Postorder(BT-right) （3） printf(“%c”,BT-data) 3編程題編程題 以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指 針域分別為 left 和 rig

34、ht，數(shù)據(jù)域 data 為字符型，BT 指向根結(jié)點(diǎn)） 。 void Inorder (struct BTreeNode *BT) if(BT!=NULL) （1） ; （2） ; （3） ; 下面下面答案：答案： （1） Inorder(BT-left) （2）printf(“%c”,BT-data) （3） Inorder(BT-right) 6.6 哈夫曼樹哈夫曼樹 1設(shè)一棵哈夫曼樹共有 n 個(gè)葉結(jié)點(diǎn)，則該樹有（ ）個(gè)非葉結(jié)點(diǎn)。 【A】 An-1 Bn Cn+1 D2n 2一棵哈夫曼樹有 12 個(gè)葉子結(jié)點(diǎn)（終端結(jié)點(diǎn)） ，該樹總共有（ ）個(gè)結(jié)點(diǎn)。 【C】 A22 B21 C23 D24 3

35、（1）以給定權(quán)重值 1，2，12，13，20，25 為葉結(jié)點(diǎn)，建立一棵哈夫曼樹 （2）若哈夫曼樹有 n 個(gè)非葉子結(jié)點(diǎn)，則樹中共有多少結(jié)點(diǎn)。對(duì)給定的一組權(quán)重值建立的棵哈夫曼 樹是否一定唯一 下面答案下面答案 書誠教育專營店 6.7 樹的遍歷反過來做的題樹的遍歷反過來做的題 1綜合題綜合題 （1）已知某二叉樹的后序遍歷序列是 debca，中序遍歷序列是 dbeac，試畫出該二叉樹 （2）若上述二叉樹的各個(gè)結(jié)點(diǎn)的字符分別代表不同的整數(shù)（其中沒有相等的） ，并恰好使該樹成為 一棵二叉排序樹，試給出 a、b、c、d、e 的大小關(guān)系 （3）給出該樹的前序遍歷序列 下面答案： 2綜合題綜合題 （1）已知某二

36、叉樹的先序遍歷序列是 aecdb，中序遍歷序列是 eadcb，試畫出該二叉樹 （2）給出上述二叉樹的后序遍歷序列 （3）若上述二叉樹的各個(gè)結(jié)點(diǎn)的字符分別是 1，2，3，4，5，并恰好使該樹成為一棵二叉排序樹， 試問 a、b、c、d、e 的值各為多少？ 下面答案： 書誠教育專營店 7. 圖圖 7.1 圖的基本概念圖的基本概念 P124: 全部頂點(diǎn)的度數(shù)為所有邊數(shù)的 2 倍，或者說，邊數(shù)為全部頂點(diǎn)的度數(shù)的一半。 1在一個(gè)無向圖中，所有頂點(diǎn)的度數(shù)之和等于邊數(shù)的（ ）倍。 【D】 A3 B2.5 C1.5 D2 2已知一個(gè)圖的邊數(shù)為 m，則該圖的所有頂點(diǎn)的度數(shù)之和為（ ） 。 【A】 A2m Bm C

37、2m+1 Dm/2 3已知一個(gè)圖的所有頂點(diǎn)的度數(shù)之和為 m，則該圖的邊數(shù)為（ ） 。 【D】 A2m Bm C2m+1 Dm/2 4以下說法不正確的是（ ） 。 【D】 A連通圖 G 一定存在生成樹 B連通圖 G 的生成樹中一定包含 G 的所有頂點(diǎn) C連通圖 G 的生成樹中不一定包含 G 的所有邊 D連通圖 G 的生成樹可以是不連通的 5以下說法不正確的是（ ） 。 【A】 A連通圖 G 的生成樹一定是唯一的 B連通圖 G 一定存在生成樹 C連通圖 G 的生成樹中一定要包含 G 的所有頂點(diǎn) D連通圖 G 的生成樹一定是連通而且不包含回路 7.2 圖的遍歷圖的遍歷 1根據(jù)搜索方法的不同，圖的遍歷

38、有_、 _ 兩種方法 【深度優(yōu)先 廣度優(yōu)先】 2圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是_的。(回答正確或不正確) 【正確】 書誠教育專營店 3已知如圖 1 所示的一個(gè)圖，若從頂點(diǎn) a 出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn) 序列為（ ） 。 【C】 Aabcedf Baebcfd Cabcefd Dacfdeb 4已知如圖 1 所示的一個(gè)圖，若從頂點(diǎn) V1出發(fā)，按廣度優(yōu)先進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列 為（ ） 。 【C】 AV1V2V3V6V7V4V5V8 BV1V2V3V4V5V8V6V7 CV1V2V3V4V5V6V7V8 DV1V2V3V4V8V5

39、V6V7 7.3 圖的最小生成樹圖的最小生成樹 應(yīng)應(yīng)應(yīng)應(yīng)用用用用克克克克魯魯魯魯斯斯斯斯卡卡卡卡爾爾爾爾算算算算法法法法構(gòu)構(gòu)構(gòu)構(gòu)造造造造最最最最小小小小生生生生成成成成樹樹樹樹的的的的過過過過程程程程 書誠教育專營店 7.5 圖的連通性圖的連通性 1以下說法正確的是（ ） 。 【D】 A連通圖 G 的生成樹中不一定包含 G 的所有頂點(diǎn) B連通圖 G 的生成樹中一定要包含 G 的所有邊 C連通圖 G 的生成樹一定是唯一的 D連通圖 G 一定存在生成樹 8. 查找查找 8.1 順序查找順序查找 1對(duì)長度為 n 的線性表進(jìn)行順序查找，在等概率情況下，平均查找長度為（ ） 。 【B】 An B （n+

40、1）/2 C2n Dn-1 2采用順序查找法對(duì)長度為 n 的線性表進(jìn)行查找（不采用表尾設(shè)監(jiān)視哨的方法） ，最壞的情況下要進(jìn) 行（ ）次元素間的比較。 【B】 An+2 Bn Cn-1 Dn/2 8.2 折半查折半查找找 1在有序表2，4，7，14，34，43，47，64，75，80，90，97，120中，用折半查找法查找值 80 時(shí)， 經(jīng)（ ）次比較后查找成功。 【】 A2 B3 C4 D5 書誠教育專營店 2有一個(gè)長度為 10 的有序表，按折半查找對(duì)該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù) 為（ A ） 。 A29/10 B31/10 C26/10 D29/9 3在有序表1，3，8

41、，13，33，42，46，63，76，78，86，97，100中，用折半查找值 86 時(shí)，經(jīng)（ ） 次比較后查找成功。 【D】 A6 B3 C8 D4 4用折半查找法，對(duì)長度為 12 的有序的線性表進(jìn)行查找，最壞情況下要進(jìn)行（ ）次元素間的比較 【A】 A4 B3 C5 D6 5綜合題綜合題 設(shè)有序表為（13，19，25，36，48，51，63，84，91，116，135，200） ，元素的下標(biāo)依次為 1,2,12。 （1）說出有哪幾個(gè)元素需要經(jīng)過 4 次元素間的比較才能成功查到 （2）畫出對(duì)上述有序表進(jìn)行折半查找所對(duì)應(yīng)的判定樹（樹結(jié)點(diǎn)用下標(biāo)表示） （3）設(shè)查找元素 5，需要進(jìn)行多少次元素間的

42、比較才能確定不能查到 下面答案：下面答案： 6折半查找只適用于_存儲(chǔ)的有序表 。 【順序存儲(chǔ)結(jié)構(gòu)】 7有序表為1，2，4，6，10，18，20，32，用課本中折半查找算法查找值 18，經(jīng)（ ）次比較后 成功查到。 【B】 A3 B2 C4 D5 8.3 二叉排序樹二叉排序樹 1二叉樹為二叉排序的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這 種說法是_的。(回答正確或不正確) 【不正確】 2綜合題綜合題 （1）對(duì)給定數(shù)列7,16,4,8,20,9,6,18,5，依次取數(shù)列中的數(shù)據(jù)，構(gòu)造一棵二叉排序樹。 (2 )對(duì)一個(gè)給定的查找值,簡述針對(duì)二叉排序樹進(jìn)行查找的算法步驟， 在

43、上述二叉樹中查找元素 20 共要進(jìn) 行多少次元素的比較? 下面答案：下面答案： 書誠教育專營店 3綜合題綜合題 (1)“一棵二叉樹若它的根結(jié)點(diǎn)的值大于左子樹所有結(jié)點(diǎn)的值，小于右子樹所有結(jié)點(diǎn)的值，則該樹一定 是二叉排序樹” 。該說法是否正確，若認(rèn)為正確，則回答正確，若認(rèn)為不正確則說明理由？ (2)設(shè)有查找表7，16，4，8，20，9，6，18，5，依次取表中數(shù)據(jù)構(gòu)造一棵二叉排序樹. 對(duì)上述二叉樹 給出后序遍歷的結(jié)果. 下面答案：下面答案： 4二叉樹排序中任一棵子樹都是二叉排序樹，這種說法是_的。(回答正確或不正確) 【正確】 5綜合題綜合題（1）設(shè)有一個(gè)整數(shù)序列40，28，6，72，100，3，

44、54依次取出序列中的數(shù)，構(gòu)造一棵二叉 排序樹 （2）對(duì)上述二叉排序樹，在等概率條件下，求成功查找的平均查找長度 下面答案：下面答案： 書誠教育專營店 6綜合題綜合題（1）給定數(shù)列8，17，5，9，21，10，7，19，6，依次取序列中的數(shù)構(gòu)造一棵二叉排序樹 （2）對(duì)上述二叉樹給出中序遍歷得到的序列。 下面答案：下面答案： 7綜合題綜合題（1）設(shè)有一個(gè)整數(shù)序列50，38，16，82，110，13，64，依次取出序列中的數(shù)，構(gòu)造一棵 二叉排序樹 （2）利用上述二叉排序樹，為了查找 110，經(jīng)多少次元素間的比較能成功查到，為了查找 15，經(jīng) 多少次元素間的比較可知道查找失敗 下面答案：下面答案： 書

45、誠教育專營店 8.4 二叉判定二叉判定樹樹 解析：寫判定樹最重要是每次找子樹對(duì)應(yīng)的頂點(diǎn)解析：寫判定樹最重要是每次找子樹對(duì)應(yīng)的頂點(diǎn) 1綜合題綜合題 設(shè)查找表為(16,15,20,53,64,7), (1)用冒泡法對(duì)該表進(jìn)行排序（要求升序排列） ，寫出每一趟的排序過程，通常對(duì) n 個(gè)元素進(jìn)行冒泡排 序要進(jìn)行多少趟冒泡？第 j 趟要進(jìn)行多少次元素間的比較？ (2)在排序后的有序表的基礎(chǔ)上，畫出對(duì)其進(jìn)行折半查找所對(duì)應(yīng)的判定樹.(要求以數(shù)據(jù)元素作為樹結(jié)點(diǎn)) (3)求在等概率條件下,對(duì)上述有序表成功查找的平均查找長度. 2綜合題綜合題（1）畫出對(duì)長度為 10 的有序表進(jìn)行折半查找的判定樹（以序號(hào) 1，2，

46、10 表示樹結(jié)點(diǎn)） （2）對(duì)上述序列進(jìn)行折半查找，求等概率條件下，成功查找的平均查找長度 下面答案：下面答案： （2）ASL=（1x1+2x2+3x4+4x3）/10=29/10 8.5 哈希函數(shù)哈希函數(shù) 1哈希函數(shù)是記錄關(guān)鍵字值與該記錄存儲(chǔ)地址存儲(chǔ)地址之間所構(gòu)造的 。 【對(duì)應(yīng)關(guān)系】 2哈希函數(shù)是記錄關(guān)鍵字值與該記錄_之間所構(gòu)造的對(duì)應(yīng)關(guān)系對(duì)應(yīng)關(guān)系。 【存儲(chǔ)地址】 3散列查找的原理是（ ） 。 【A】 A在待查記錄的關(guān)鍵字值與該記錄的存儲(chǔ)位置之間建立確定的對(duì)應(yīng)關(guān)系 B按待查記錄的關(guān)鍵字有序的順序方式存儲(chǔ) C按關(guān)鍵字值的比較進(jìn)行查找 D基于二分查找的方法 8.6 折半查找編程題折半查找編程題 1綜

47、合題綜合題 以下函數(shù)在a0到an-1中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記 錄的下標(biāo)，失敗時(shí)返回-1，完成程序中的空格 typedef struct int key; NODE; int Binary_Search(NODE a,int n, int k) 書誠教育專營店 int low,mid,high; low=0; high=n-1; while(_(1)_) mid=(low+high)/2; if(amid.key=k) return _(2)_; else if(_(3)_) low=mid+1; else _(4)_; _(5)_; 下面答案：下面答案： （1

48、）lowleft （4）p=p-right （5）p 9. 排序排序 9.1 排序基本概念排序基本概念 1按某關(guān)鍵字對(duì)記錄序列排序，若 在排序前和排序后仍保持它們的前后關(guān)系，則 排序算法是穩(wěn)定的，否則是不穩(wěn)定的。 【 關(guān)鍵字相等的記錄 】 2 以下排序算法中， 在一趟排序過程中， 除了其它相關(guān)操作外， 只進(jìn)行一次元素間的交換的算法是 （ ） 。 【A】 A直接選擇 B冒泡 C直接插入 D折半插入 9.2 直接插入排序直接插入排序 1排序算法中，從未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較（要求比較 次數(shù)盡量少） ，然后將其放入已排序序列的正確位置的方法是（ ） 。 【D】

49、 A冒泡 B直接插入 C選擇排序 D折半插入 3排序方法中，從尚未排序序列中挑選元素，并將其依次放入已排序序列（初始為空）的一端的方法， 稱為（ ）排序。 【C】 A歸并 B插入 C選擇 D快速 4排序過程中，每一趟從無序子表中將一個(gè)待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列 的適當(dāng)位置，直到全部排好序?yàn)橹?，該排序算法? )。 【A】 A直接插入排序 B快速排序 C冒泡排序 D選擇排序 5綜合題綜合題（1）一組記錄的關(guān)鍵字序列為45，40，65，43，35，95寫出利用快速排序的方法，以第一個(gè) 記錄為基準(zhǔn)得到的一趟劃分的結(jié)果（要求給出一趟劃分中每次掃描和交換的結(jié)果） （2）同樣對(duì)序列45，40，65，43，35，95利用直接插入排序，寫出逐次插入過程（從第一個(gè)元素 一直到第六個(gè)元素） 。 下面答案：下面答案： 書誠教育專