國家開放大學(xué)《數(shù)據(jù)結(jié)構(gòu)（本）》綜合練習(xí)題參考答案

1、國家開放大學(xué)數(shù)據(jù)結(jié)構(gòu)（本）綜合練習(xí)題參考答案一、填空題1.對稀疏矩陣進(jìn)行壓縮存儲(chǔ)，可采用三元組表，一個(gè)有10行的稀疏矩陣A共有97個(gè)零元素，其相應(yīng)的三元組表共有3個(gè)元素。該矩陣A有（10）列。2.結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為（圖狀）結(jié)構(gòu)。3.在單向鏈表中，q指向p所指結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)，要?jiǎng)h除q所指結(jié)點(diǎn)，可以用操作（p->next;）= q->next;。4.n個(gè)元素進(jìn)行冒泡法排序，第j趟冒泡要進(jìn)行（n-j）次元素間的比較。5.對稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對應(yīng)的三元組包括該元素的行下標(biāo)、列下標(biāo)和（數(shù)組元素）三項(xiàng)信息。6.中序遍歷（二叉排序樹）樹可得到一個(gè)有序序

2、列。7.隊(duì)列的操作特點(diǎn)是后進(jìn)（后出）。8.待排序的序列為8，3，4，1，2，5，9，采用直接選擇排序算法，當(dāng)進(jìn)行了兩趟選擇后，結(jié)果序列為（1，2，4，8，3，5，9）。9.n個(gè)元素進(jìn)行冒泡法排序，通常需要進(jìn)行（n-1）趟冒泡。10.廣義表（a，b），d，e（i，j），k）的長度是（4） 。11.中序遍歷二叉排序樹可得到一個(gè)（有序）的序列。12.廣義表的（c，a，（a，b），d，e，（i，j），k）深度是（3）。13.廣義表（c，a，（a，b），d，e，（i，j），k）的長度是（6）。14.對稀疏矩陣進(jìn)行壓縮存儲(chǔ)，可采用三元組表，一個(gè)有10 行10列的稀疏矩陣A共有95個(gè)零元素，其相應(yīng)的三元組表

3、共有（5）個(gè)元素。15.廣義表的（c，a，（a，b），d，e，（i，j），k）深度是（3）。16.在對一組記錄（50，49，97，22，16，73，65，47，88）進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄65 插入到有序表時(shí)，為尋找插入位置需比較（3）次。17.循環(huán)隊(duì)列在規(guī)定少用一個(gè)存儲(chǔ)空間的情況下，隊(duì)空的判定條件為（front=rear）。18.一棵有5個(gè)葉結(jié)點(diǎn)的哈夫曼樹，該樹中總共有（9）個(gè)結(jié)點(diǎn)。19.c語言中，字符串“E”存儲(chǔ)時(shí)占（2）個(gè)字節(jié)。20.設(shè)有一棵深度為4的完全二叉樹，第四層上有5個(gè)結(jié)點(diǎn)，該樹共有（12）個(gè)結(jié)點(diǎn)。（根所在結(jié)點(diǎn)為第1層）。21.一棵二叉樹中有n個(gè)非葉結(jié)點(diǎn)，每一個(gè)非葉結(jié)

4、點(diǎn)的度數(shù)都為2，則該樹共有（n+1）個(gè)葉結(jié)點(diǎn)。22.設(shè)有一個(gè)長度為40的順序表，要?jiǎng)h除第8個(gè)元素需移動(dòng)元素的個(gè)數(shù)為（32）。23.在對一組記錄（55，39，97，22，16，73，65，47，88）進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄65插入到有序表時(shí)，為尋找插入位置需比較（3）次。24.有以下程序段： char a =“English”; char *p=a; int n=0; while( *p!=0) n+; p+;結(jié)果中，n的值是（7）。25.設(shè)：char a ="AEIJING"該字符串在計(jì)算機(jī)中存儲(chǔ)時(shí)占（8）個(gè)字節(jié)。棧的特點(diǎn)之一是：元素進(jìn)、出棧的次序是：先進(jìn)（后出

5、）。26.結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為（圖狀）結(jié)構(gòu)。27.對稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對應(yīng)的三元組包括該元素的三項(xiàng)信息是（行下標(biāo)，行下標(biāo)，數(shù)組元素）。28.對稀疏矩陣進(jìn)行壓縮存儲(chǔ)，可采用三元組表，一個(gè)有8行的稀疏矩陣A共有92個(gè)零元素，其相應(yīng)的三元組表共有4個(gè)元素。該矩陣A有（12） 列。29.在對10個(gè)記錄的序列（9，35，19，77，2，10，53，45，27，68）進(jìn)行直接插入排序時(shí)，當(dāng)把第6個(gè)記錄10 插入到有序表時(shí)，為尋找插入位置，元素間需比較（4）次。（按升序排序）30.循環(huán)鏈隊(duì)列中，設(shè)front和rear分別為隊(duì)頭和隊(duì)尾指針，最大存儲(chǔ)空間元素為MaxSize

6、，采用少用一個(gè)存儲(chǔ)空間的模式，則判斷循環(huán)鏈隊(duì)列為空的條件是（front=rear）為真。31.字符串a(chǎn)1="beijing"，a2 ="bef"，a3="beifang"，a4="befi"最小的是（a2）。32.n個(gè)元素進(jìn)行冒泡法排序，第j趟冒泡要進(jìn)行（n-j）次元素間的比較。33.10個(gè)元素進(jìn)行冒泡法排序，其中第5趟冒泡共需要進(jìn)行（5）次元素間的比較。34.設(shè)有一棵深度為4的完全二叉樹，第四層上有5個(gè)結(jié)點(diǎn)，該樹共有（12）個(gè)結(jié)點(diǎn)。（根所在結(jié)點(diǎn)為第1層）35.（中序）遍歷一棵二叉排序樹可得到一個(gè)有序序列。36中序

7、遍歷一棵（二叉排序樹）可得到一個(gè)有序序列。37.廣義表（c，（a，b，c），（d，e，f），（i，j），k）的長度是（4）。38.待排序的序列為9，4，5，1，2，6，10，采用直接選擇排序算法，當(dāng)進(jìn)行了兩趟選擇后，結(jié)果序列為（1，2，5，9，4，6，10）。39.廣義表的（c，（b，a，b），f，e，（i，j），k）深度是（3）。40.廣義表（a，b），d，e，（i，j），k）的長度是（4）。41.序列4，2，5，3，8，6，采用冒泡排序算法（升序），經(jīng)一趟冒泡后，結(jié)果序列是（2，4，3，5，6，8）。42.廣義表的（c，a，（a，b），d，e，（i，j），k）深度是（3） 。43.待排序的

8、序列為8，3，4，1，2，5，9，采用直接選擇排序算法，當(dāng)進(jìn)行了兩趟選擇后，結(jié)果序列為（1，2，4，8，3，5，9）。44.線性表用（順序）方式存儲(chǔ)需要占用連續(xù)的存儲(chǔ)空間。45.線性表用（順序）方式存儲(chǔ)可以隨機(jī)訪問。46.線性表用關(guān)鍵字（有序）的順序方式存儲(chǔ)，可以用二分法排序。47.順序表6，5，1，2，4，3，8，7經(jīng)過一趟（1，1）歸并后的結(jié)果序列為（5，6），（1，2），（3，4），（7，8）。二、單項(xiàng)選擇題1.棧和隊(duì)列的共同特點(diǎn)是（ ）。A. 都是先進(jìn)后出B. 元素都可以隨機(jī)進(jìn)出C. 都是先進(jìn)先出D. 都是操作受限的線性結(jié)構(gòu)2.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括數(shù)據(jù)元素的表示和（ ）。A. 數(shù)據(jù)元素的

9、類型B. 相關(guān)算法C. 數(shù)據(jù)處理的方法D. 數(shù)據(jù)元素間的關(guān)系的表示3.對一個(gè)棧頂指針為top的鏈棧進(jìn)行入棧操作，通過指針變量p生成入棧結(jié)點(diǎn)，則執(zhí)行：p=(struct node *)malloc(sizeof(struct node);p->data=a;和（ ）。A. top=top->next; p=top;B. p->next=top; p=top;C. p->next=top; top=p;D. top->next=p; p=top;4.樹狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ ）的關(guān)系。A. 每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B. 多對多C. 一對多D.

10、 一對一5.設(shè)頭指針為head的非空的單向鏈表，指針p指向尾結(jié)點(diǎn),則通過以下操作（ ）可使其成為單向循環(huán)鏈表。A. head = p;B. p->next = NULL ;C. p=head;D. p->next=head;6.設(shè)有一個(gè)長度為26的順序表，要插入一個(gè)元素，并使它成為新表的第6個(gè)元素，需移動(dòng)元素的個(gè)數(shù)為（ ）。A. 19B. 20C. 22D. 217.一種邏輯結(jié)構(gòu)（ ）。A. 是指某一種數(shù)據(jù)元素的性質(zhì)B. 只能有唯一的存儲(chǔ)結(jié)構(gòu)C. 可以有不同的存儲(chǔ)結(jié)構(gòu)D. 與存儲(chǔ)該邏輯結(jié)構(gòu)的計(jì)算機(jī)相關(guān)8.頭指針為head的帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，p所指向尾結(jié)點(diǎn)，要使該鏈表成為不帶頭

11、結(jié)點(diǎn)的單向循環(huán)鏈表，可執(zhí)行head=head->nex;和（ ）。A. head->next=p->nextB. head->next=pC. p->next=head;D. p= head->next9.把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為（ ）。A. 邏輯結(jié)構(gòu)B. 存儲(chǔ)結(jié)構(gòu)C. 數(shù)據(jù)元素的存儲(chǔ)D. 給數(shù)據(jù)元素分配存儲(chǔ)空間10.元素111，113，115，117按順序依次進(jìn)棧，則該棧的不可能輸出序列是（ ）（進(jìn)棧出?？梢越惶孢M(jìn)行）。A. 111，113，115，117B. 117，115，111，113C. 117，115，113，11

12、1D. 113，111，117，11511.圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ ）的關(guān)系。A. 每一個(gè)元素都有一個(gè)且只有一個(gè)直接前驅(qū)和一個(gè)直接后繼B. 多對多C. 一對一D. 一對一12.以下說法正確的是（ ）。A. 棧和隊(duì)列的特點(diǎn)都是后進(jìn)后出B. 隊(duì)列的特點(diǎn)是先進(jìn)后出C. 棧的特點(diǎn)是先進(jìn)先出D. 棧的特點(diǎn)是先進(jìn)后出13.一個(gè)單鏈表中，在p所指結(jié)點(diǎn)之后插入一個(gè)s所指的結(jié)點(diǎn)時(shí)，可執(zhí)行：s->next=p->next;和（ ）。A. s=p->next;B. p=s->next;C. p->next=s->next;D. p->next=s;14.設(shè)有一個(gè)

13、20階的對稱矩陣A（第一個(gè)元素為a1,1），采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣元素a6,2在一維數(shù)組B中的下標(biāo)是（ ）。A. 23B. 21C. 17D. 2815.元素12，14，16，18順序依次進(jìn)棧，則該棧的不可能輸出序列是（ ）。（進(jìn)棧出棧可以交替進(jìn)行）。A. 14，12，18，16B. 18，16，12，14C. 12，14，16，18D. 18，16，14，1216.設(shè)有串p1="ABADF"，P2="ABAFD"，P3="ABADFA"，P4="ABAF

14、"，以下四個(gè)串中最大的是（ ）。A. p1B. p3C. p4D. p217.設(shè)有一個(gè)30階的對稱矩陣A（第一個(gè)元素為a1,1），采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a9,2在一維數(shù)組B中的下標(biāo)是（ ）。A. 41B. 38C. 32D. 1818.數(shù)組a經(jīng)初始化char a =“English”;a7中存放的是（ ）。A. 變量hB. 字符hC. "h"D. 字符串的結(jié)束符19.設(shè)有一個(gè)長度為32的順序表，要?jiǎng)h除第8個(gè)元素需移動(dòng)元素的個(gè)數(shù)為（ ）。A. 22B. 15C. 24D. 1420.設(shè)主串為

15、“ABcCDABcdEFaBc”，以下模式串能與主串成功匹配的是（ ）。A. ABCB. BCdC. BcdD. Abc21.在一棵二叉樹中，若編號為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號為（ ）。A. 2i+1B. 2iC. 2i-1D. 2i+222.在一棵二叉樹中，若編號為i的結(jié)點(diǎn)存在左孩子，則左孩子的順序編號為（ ）。A. 2iB. 2i+1C. 2i+2D. 2i-123.一棵具有16個(gè)結(jié)點(diǎn)的完全二叉樹，共有（ ）層。（設(shè)根結(jié)點(diǎn)在第一層）A. 5B. 4C. 6D. 724.如下圖所示，若從頂點(diǎn)a出發(fā)，按圖的廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。A. aebcfd

16、B. abecdfC. aedfcbD. aecbdf25.如下圖所示，若從頂點(diǎn)a出發(fā)，按圖的深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。A. acfebgdB. aedfcgbC. aebcfgdD. abecdfg26.線性表以（ ）方式存儲(chǔ)，能進(jìn)行折半查找。A. 鏈接B. 二叉樹C. 關(guān)鍵字有序的順序D. 順序27.字符串“DABcdabcd321ABC”的子串是（ ）。A. “aBcd”B. “cd32”C. “321a”D. “ABcD”28.一棵具有38個(gè)結(jié)點(diǎn)的完全二叉樹，最后一層有（ ）個(gè)結(jié)點(diǎn)。A. 5B. 7C. 6D. 829.如下圖所示，若從頂點(diǎn)a出發(fā)，按廣度

17、優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。A. abcfgdeB. abcdfegC. abcdfgeD. acbfedg30.下圖的拓?fù)湫蛄惺牵?）。A. 5 6 2 3 4B. 2 3 6 4 5C. 2 3 5 6 4D. 5 2 3 4 631.下面關(guān)于線性表的敘述錯(cuò)誤的是（ ）。A. 線性表采用順序存儲(chǔ)便于插入和刪除操作的實(shí)現(xiàn)B. 線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)空間C. 線性表采用鏈?zhǔn)酱鎯?chǔ)便于插入和刪除操作的實(shí)現(xiàn)D. 線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)空間32.設(shè)有頭指針為head的不帶頭結(jié)點(diǎn)的非空的單向循環(huán)鏈表，指針p指向其尾結(jié)點(diǎn)，要?jiǎng)h除第一個(gè)結(jié)點(diǎn)，則可

18、利用下述語句 head=head->next;和（ ）。A. p->next =head;B. p=NULL;C. head=p;D. p=head;33.以下數(shù)據(jù)結(jié)構(gòu)中是非線性結(jié)構(gòu)的是（ ）。A. 二叉樹B. 隊(duì)列C. 棧D. 線性表34.以下說法正確的是（ ）。A. 線性表的順序存儲(chǔ)結(jié)構(gòu)不必占用連續(xù)的存儲(chǔ)空間B. 一種邏輯結(jié)構(gòu)只能有唯一的存儲(chǔ)結(jié)構(gòu)C. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)必須占用連續(xù)的存儲(chǔ)空間D. 一種邏輯結(jié)構(gòu)可以有不同的存儲(chǔ)結(jié)構(gòu)35.設(shè)有一個(gè)長度為18的順序表，要?jiǎng)h除第7個(gè)元素需移動(dòng)元素的個(gè)數(shù)為（ ）。A. 10B. 13C. 12D. 1136.把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體

19、體現(xiàn)（ ）稱為物理結(jié)構(gòu)。A. 數(shù)據(jù)的運(yùn)算B. 數(shù)據(jù)元素間的邏輯關(guān)系C. 數(shù)據(jù)的性質(zhì)D. 數(shù)據(jù)的處理方法37.兩個(gè)字符串相等的充要條件是（ ）。A. 兩個(gè)字符串的長度相等B. 同時(shí)具備（A）和（C）兩個(gè)條件C. 兩個(gè)字符串中對應(yīng)位置上的字符相等D. 以上答案都不對38.順序表所具備的特點(diǎn)之一是（ ）。A. 插入元素的操作不需要移動(dòng)元素B. 不需要占用連續(xù)的存儲(chǔ)空間C. 可以隨機(jī)訪問任一結(jié)點(diǎn)D. 刪除元素的操作不需要移動(dòng)元素39.設(shè)某鏈表中最常用的操作是在鏈表的尾部插入或刪除元素，在已知尾指針的條件下，選用下列（ ）存儲(chǔ)方式最節(jié)省運(yùn)算時(shí)間。A. 雙向鏈表B. 雙向循環(huán)鏈表C. 單向鏈表D. 單向循

20、環(huán)鏈表4.圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ ）的關(guān)系。A. 一對一B. 多對多C. 一對多D. 每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼41.元素13，15，19，20順序依次進(jìn)棧，則該棧的不可能輸出序列是（ ）。（進(jìn)棧出?？梢越惶孢M(jìn)行）A. 13，15，19，20B. 15，13，20，19C. 19，13，15，20D. 20，19，15，1342.元素20，14，16，18按順序依次進(jìn)棧，則該棧的不可能輸出序列是（ ）。（進(jìn)棧出?？梢越惶孢M(jìn)行）A. 20，14，16，18B. 14，20，18，16C. 18，16，20，14D. 18，16，14，2043.設(shè)指針q指向單鏈表中結(jié)點(diǎn)A

21、，指針p指向單鏈表中結(jié)點(diǎn)A的后繼結(jié)點(diǎn)B，則在表中刪除結(jié)點(diǎn)B的操作為（ ）。A. q->next=p->next；B. p->next；p=q；C. q->next=p；D. p->next=q->next；44.設(shè)有一個(gè)12階的對稱矩陣A（左上角第一個(gè)元素為a1,1），采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a5,4在一維數(shù)組B中的下標(biāo)是（ ）。A. 12B. 11C. 13D. 1445.棧和隊(duì)列的共同特點(diǎn)之一是（ ）。A. 都是先進(jìn)后出B. 沒有共同點(diǎn)C. 只允許在端點(diǎn)處插入和刪除元素D. 都是先

22、進(jìn)先出46.設(shè)有一個(gè)長度為22的順序表，要?jiǎng)h除第8個(gè)元素需移動(dòng)元素的個(gè)數(shù)為（ ）。A. 25B. 23C. 14D. 1547.用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行插入運(yùn)算時(shí)（ ）。A. 頭、尾指針都不需要修改B. 需修改尾指針C. 需修改頭指針D. 頭、尾指針都需要修改48.在一棵二叉樹中，若編號為5的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號為（ ）。A. 9B. 10C. 12D. 1149.字符串 a1="AEIJING"，a2="AEI"，a3="AEFANG"，a4="AEFI"中最大的是（ ）。A. a4B. a2C

23、. a3D. a150.一棵具有5層的完全二叉樹，最后一層有4個(gè)結(jié)點(diǎn)，則該樹總共有（ ）個(gè)結(jié)點(diǎn)。A. 14B. 15C. 18D. 1951.設(shè)有一個(gè)20階的對稱矩陣A（第一個(gè)元素為a1,1），采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素a6,2在一維數(shù)組B中的下標(biāo)是（ ）。A. 18B. 23C. 21D. 1752.如下圖所示，若從頂點(diǎn)a出發(fā)，按圖的廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。A. abcfgdeB. abcdfgeC. abcedfgD. acbfedg53.以下說法正確的是（ ）。A. 前序遍歷二叉排序

24、樹可得到一個(gè)有序序列。B. 若二叉樹中左子樹上所有結(jié)點(diǎn)的值均小于根結(jié)點(diǎn)的值，右子樹上所有結(jié)點(diǎn)的值均大于根結(jié)點(diǎn)的值。則該樹為二叉排序樹。C. 二叉樹中任意一個(gè)結(jié)點(diǎn)的值均大于其左孩子的值，小于其右孩子的值。則該樹為二叉排序樹。D. 二叉樹中任意一個(gè)非葉結(jié)點(diǎn)的值都大于其左子樹上所有結(jié)點(diǎn)的值，小于其右子樹上所有結(jié)點(diǎn)的值，則該樹為二叉排序樹。54.字符串"abcd321ABCD"的子串是（ ）。A. abcDB. "321a"C. "21ABC"D. "abcABCD"55.二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為（ ）。A. 2K+1

25、B. 2k-1C. 2k-1D. 2K-156.數(shù)組a經(jīng)初始化char a =“English”;a1中存放的是（ ）。A. "n"B. "E"C. 字符nD. 字符E57.如下圖所示，若從頂點(diǎn)6出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。A. 6，2，7，9，8，4，3B. 6，2，8，7，9，3，4C. 6，9，2，3，7，8，4D. 6，9，3，2，8，7，458.如下圖所示，若從頂點(diǎn)a出發(fā)，按圖的深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。A. aedfcbB. acfebdC. aebcfdD. abecdf

26、59.如下圖所示，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為（ ）。A. abcdfgeB. abcfegdC. abcfgdeD. acbfedg60.下圖的拓?fù)湫蛄惺牵?）。A. 2 3 4 5 6B. 5 6 4 2 3C. 5 2 3 4 6D. 5 2 3 6 4三、綜合題1.有一個(gè)長度為11的有序表（1，2，11，15，24，28，30，56，69，70，80），元素的下標(biāo)依次為：1，2，3，11，按折半查找對該表進(jìn)行查找。（1）畫出對上述查找表進(jìn)行折半查找所對應(yīng)的判定樹。（2）說出成功查找到元素56，需要依次經(jīng)過與哪些元素的比較？（3）說出不成功查找元素

27、72，需要進(jìn)行元素比較的次數(shù)？參考答案：（1）（2）28，69，30，56（3）4次2.（1）以3，4，5，8，9，作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹。（2）給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。（2）n個(gè)葉結(jié)點(diǎn)的哈夫曼樹，總共有多少個(gè)結(jié)點(diǎn)？參考答案：（1）（2）3：0004：0015：018：109：11（3）2n-13.（1）一組記錄的關(guān)鍵字序列為（57，90，67，50，51，56），利用堆排序（堆頂元素是最小元素）的方法建立初始堆（要求以完全二叉樹描述 ）。（2）對關(guān)鍵字序列（56，51，71，54，46，106）利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，給出經(jīng)過一次劃分后結(jié)果。（3）一組記錄

28、的關(guān)鍵字序列為（60，47，80，57，39，41，46，30），利用歸并排序的方法，分別給出（1，1）歸并、（2，2）歸并、（4，4）歸并的結(jié)果序列。參考答案：（1）（2）46，51，54，56，71，106（3）（47，60）（57，80）（39，41）（30，46）（47，57，60，80）（30，39，41，46）（30，39，41，46，47，57，60，80）4.（1）設(shè)有數(shù)據(jù)集合40，29，7，73，101，4，55，2，81，92，39，依次取集合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹。（2）在上述二叉排序樹上進(jìn)行查找，給出成功查找到元素92的查找路徑，其中共經(jīng)過了多少次元素間的的比較。（

29、3）有一個(gè)長度為10的有序表，按折半查找對該表進(jìn)行查找，給出在等概率情況下查找成功的平均比較次數(shù)為。參考答案：（1）（2）40，73，101，81，92。共5個(gè)元素比較（3）29/105.（1）以2，3，4，7，8，9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹。（2）給出相應(yīng)權(quán)重值葉結(jié)點(diǎn)的哈夫曼編碼。（3）一組記錄的關(guān)鍵字序列為（47，80，57，39，41，46），利用堆排序的方法建立的初始堆（堆頂元素是最小元素，以樹的形式給出）。參考答案：（1）（2）2：00003：00014：0017：108：119：01（3）6.（1）一組記錄的關(guān)鍵字序列為（36，69，46，28，30，35），給出利用堆排序

30、（堆頂元素是最小元素）的方法建立的初始堆（要求以完全二叉樹描述 ）。（2）對關(guān)鍵字序列（36，69，46，28，30，74）采用快速排序，給出以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過一次劃分后的結(jié)果。（3）設(shè)有數(shù)據(jù)集合30，73，101，4，8，9，2，81，依次取集合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹。參考答案：（1）28，30，35，69，36，46 （2）30，28，36，46，69，74（3）7.（1）已知某二叉樹的后序遍歷序列是debca，中序遍歷序列是dbeac，試畫出該二叉樹。（2）若上述二叉樹的各個(gè)結(jié)點(diǎn)的字符分別代表不同的整數(shù)（其中沒有相等的），并恰好使該樹成為一棵二叉排序樹，試給出a、b、c、

31、d、e的大小關(guān)系。（3）給出該樹的前序遍歷序列。參考答案：（1）（2）d<b<e<a<c（3）abdec8.（1）一組記錄的關(guān)鍵字序列為45，40，65，43，35，95，寫出利用快速排序的方法，以第一個(gè)記錄為基準(zhǔn)得到的一趟劃分的結(jié)果（要求給出一趟劃分中每次掃描和交換的結(jié)果）。（2）對序列45，40，65，43，35，95利用直接插入排序，寫出逐次插入過程（從第一個(gè)元素一直到第六個(gè)元素）。參考答案：（1）（2）40 45 65 43 35 9540 43 45 65 35 9535 40 43 45 65 959.（1）設(shè)head1和p1分別是不帶頭結(jié)點(diǎn)的單向鏈表A的頭

32、指針和尾指針，head2和p2分別是不帶頭結(jié)點(diǎn)的單向鏈表B的頭指針和尾指針，若要把B鏈表接到A鏈表之后，得到一個(gè)以head1為頭指針的單向循環(huán)鏈表，寫出其中兩個(gè)關(guān)鍵的賦值語句（不用完整程序，結(jié)點(diǎn)的鏈域?yàn)閚ext）。（2）單向鏈表的鏈域?yàn)閚ext，設(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）

33、不對，s->next= p->next；p->next=s；10.（1）設(shè)根為第1層,對給定權(quán)值1，3，4，4，5，6，構(gòu)造深度為5的哈夫曼樹。提示：構(gòu)造中當(dāng)出現(xiàn)被選的結(jié)點(diǎn)值有多個(gè)相等時(shí)，可嘗試不同組合，以得到要求的樹的深度。（2）求樹的帶權(quán)路徑長度。（3）用鏈接法存儲(chǔ)上述哈夫曼樹，結(jié)點(diǎn)中共有多少個(gè)指針域?yàn)榭眨f明理由？（4）給出對上述哈夫曼樹中序遍歷得到的的序列。（5）一棵哈夫曼樹有n個(gè)非葉結(jié)點(diǎn)，構(gòu)造該樹共有多少個(gè)權(quán)重值？簡述理由？參考答案：（1）（2）WPL=1*4+3*4+4*3+6*2+4*2+5*2=58（3）有12個(gè)空指針域，因?yàn)楣?1個(gè)結(jié)點(diǎn)，22個(gè)指針域，除根結(jié)

34、點(diǎn)外，每個(gè)結(jié)點(diǎn)對應(yīng)一個(gè)指針域，共10個(gè)指 域非空，故有 22-10=12個(gè)空指針域。（針對哈夫曼樹還可有其它理由）（4）1，4，3，8，4，14，6，23，4，9，5（5）n+1，因?yàn)槿~結(jié)點(diǎn)比非葉結(jié)點(diǎn)多1。四、程序填空題1.以下是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分（樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn)）。void Inorder(struct BTreeNode *BT) if(BT!=NULL) Inorder(BT->left) ; printf("%c",BT->data) ; Inorde

35、r(BT->right);利用上述程序?qū)ο聢D進(jìn)行遍歷，結(jié)果是 d b f e a c 。2.設(shè)線性表為（16，20，26，24），以不帶頭結(jié)點(diǎn)的單向鏈表存儲(chǔ)，鏈表頭指針為head，以下程序的功能是輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)域data。struct node int data; struct node *next;typedef struct node NODE;#define NULL 0void main() NODE *head,*p; p=head; /*p為工作指針*/ do printf("%dn", p->data ); p=p->next ;

36、while( p!=NULL );3.以下冒泡法程序?qū)Υ娣旁赼1，a2，an中的序列進(jìn)行排序，完成程序中的空格部分，其中n是元素個(gè)數(shù)，要求按升序排列。void bsort (NODE a ,int n) NODE temp; int i,j,flag; for(j=1; j<=n-1 ;j+) flag=0; for(i=1; i<=n-j ;i+) if(ai.key>ai+1.key) flag=1; temp=ai; ai=ai+1 ; ai+1=temp ; if(flag=0)break; 設(shè)有序列6，4，5，8，2，1，給出由該程序經(jīng)過兩趟冒泡后的結(jié)果序列 4，5

37、，2，1，6，8 。4.以下函數(shù)為直接選擇排序算法，對a1，a2，an中的記錄進(jìn)行直接選擇排序，完成程序中的空格：typedef struct int key; NODE;void selsort(NODE a ,int n) int i,j,k; NODE temp; for(i=1;i<= n-1 ;i+) k=i; for(j=i+1;j< n ;j+) if(aj.key<ak.key) k=j ; if(i!=k) temp=ai; ai=ak ; ak=temp ; 5.設(shè)線性表為（1，3，7，5），以下程序用說明結(jié)構(gòu)變量的方法建立單向鏈表，并輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)。struct node int data; struct node *next;typedef struct node NODE;#define NULL 0void main() NODE a,b,c,d,*head,*p; a.data=6; b.data=10; c.data=16; c.data=4; /*d是尾結(jié)點(diǎn)*/ head= &a ; a.next=&b; b.next=&c; c.next=&d; d->next=NULL ; /*以上結(jié)束建表過程*/ p=head; /*p為工作指針，準(zhǔn)備輸出鏈表*/ do printf