【MOOC】《數(shù)據(jù)結(jié)構(gòu)》(南京郵電大學(xué))章節(jié)中國大學(xué)慕課答案

【MOOC】《數(shù)據(jù)結(jié)構(gòu)》(南京郵電大學(xué))章節(jié)中國大學(xué)慕課答案

有些題目順序不一致，下載后按鍵盤ctrl+F進(jìn)行搜索第1章緒論（視頻總時(shí)長30'，共計(jì)3個(gè)）第1章單元測驗(yàn)1.單選題：從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為__________兩大類

選項(xiàng)：

A、動(dòng)態(tài)結(jié)構(gòu)、靜態(tài)結(jié)構(gòu)

B、順序結(jié)構(gòu)、鏈?zhǔn)浇Y(jié)構(gòu)

C、線性結(jié)構(gòu)、非線性結(jié)構(gòu)

D、初等結(jié)構(gòu)、構(gòu)造型結(jié)構(gòu)

答案：【線性結(jié)構(gòu)、非線性結(jié)構(gòu)】2.單選題：算法的計(jì)算量的大小稱為計(jì)算的__________。

選項(xiàng)：

A、效率

B、時(shí)間復(fù)雜性

C、現(xiàn)實(shí)性

D、難度

答案：【時(shí)間復(fù)雜性】3.單選題：下列函數(shù)的時(shí)間復(fù)雜度是（）intfunc（intn）｛inti=0,sum=0;while(sumreturni;｝

選項(xiàng)：

A、

B、

C、

D、

答案：【】4.單選題：下面程序段的時(shí)間復(fù)雜度為________________。for(i=0;i<p=""><>for(j=0;j<p=""><>x++;

選項(xiàng)：

A、

B、

C、

D、

答案：【】5.單選題：算法的時(shí)間復(fù)雜度取決于______________。

選項(xiàng)：

A、問題規(guī)模

B、計(jì)算機(jī)的軟硬件配置

C、兩者都是

D、兩者都不是

答案：【問題規(guī)?！?.單選題：數(shù)據(jù)結(jié)構(gòu)采用鏈?zhǔn)酱鎯?chǔ)時(shí)，存儲(chǔ)單元的地址_______________。

選項(xiàng)：

A、一定連續(xù)

B、一定不連續(xù)

C、不一定連續(xù)

D、部分連續(xù)，部分不連續(xù)

答案：【不一定連續(xù)】7.單選題：從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為______兩大類。

選項(xiàng)：

A、初等結(jié)構(gòu)和構(gòu)造性結(jié)構(gòu)

B、順序結(jié)構(gòu)和鏈?zhǔn)浇Y(jié)構(gòu)

C、線性結(jié)構(gòu)和非線性結(jié)構(gòu)

D、動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)

答案：【線性結(jié)構(gòu)和非線性結(jié)構(gòu)】8.單選題：下面說法正確的是____。

選項(xiàng)：

A、健壯的算法不會(huì)因?yàn)榉欠ǖ妮斎霐?shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)

B、算法的優(yōu)劣與算法的描述語言無關(guān)，但與所用計(jì)算機(jī)環(huán)境因素有關(guān)

C、數(shù)據(jù)的邏輯結(jié)構(gòu)依賴于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)

D、以上幾個(gè)都是錯(cuò)誤的

答案：【健壯的算法不會(huì)因?yàn)榉欠ǖ妮斎霐?shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)】9.單選題：程序步越少的算法執(zhí)行效率越高。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】10.單選題：順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】11.單選題：數(shù)據(jù)結(jié)構(gòu)的操作的實(shí)現(xiàn)與數(shù)據(jù)的存儲(chǔ)表示相關(guān)。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】12.單選題：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)內(nèi)的實(shí)際存儲(chǔ)形式。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】13.單選題：健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】14.單選題：算法的優(yōu)劣與算法描述語言無關(guān)，但與所用計(jì)算機(jī)有關(guān)。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】15.單選題：數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)的各數(shù)據(jù)項(xiàng)之間的邏輯關(guān)系。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】16.四種基本的邏輯結(jié)構(gòu)包括集合結(jié)構(gòu)、_______結(jié)構(gòu)、線性結(jié)構(gòu)和圖形結(jié)構(gòu)

答案：【樹形/樹/樹型】17.四種基本的邏輯結(jié)構(gòu)包括集合結(jié)構(gòu)、_______結(jié)構(gòu)、線性結(jié)構(gòu)和樹形結(jié)構(gòu)

答案：【圖形/圖/圖型】18.四種基本的邏輯結(jié)構(gòu)包括線性結(jié)構(gòu)、_______結(jié)構(gòu)、圖形結(jié)構(gòu)和樹形結(jié)構(gòu)

答案：【集合】19.四種基本的邏輯結(jié)構(gòu)包括集合結(jié)構(gòu)、_______結(jié)構(gòu)、圖形結(jié)構(gòu)和樹形結(jié)構(gòu)

答案：【線性】20.已知算法關(guān)鍵步驟的執(zhí)行次數(shù),則算法的漸近時(shí)間復(fù)雜度為_______。（請用x^y表示x的y次方，采用半角括號）

答案：【O(n^2)】21.求aFunc方法的時(shí)間復(fù)雜度為____________。（注意答案中不要有空格，用logn表示底數(shù)為2的對數(shù)，用半角括號表示）voidaFunc(intn){for(inti=2;i<n;i++){i*=2;printf("%i\n",i);}}

答案：【O(logn)】22.求該方法的漸近時(shí)間復(fù)雜度為__________.(注意填寫答案時(shí)不要有空格，用x^y的方式表達(dá)x的y次方)voidaFunc(intn){for(inti=0;i<n;i++){for(intj=i;j<n;j++){printf("HelloWorld\n");}}}

答案：【O(n^2)】第1章作業(yè)1.確定劃線語句的執(zhí)行次數(shù)，計(jì)算它們的漸近時(shí)間復(fù)雜度（注意本題有兩個(gè)問題）。y=0;while(n>=y*y)y++;

答案：執(zhí)行次數(shù)是解析：設(shè)下劃線語句執(zhí)行次數(shù)為t，進(jìn)行遞推：第1次執(zhí)行后，y=1，如果n>=1*1時(shí)，則有下一趟第2次執(zhí)行后，y=2，如果n>=2*2時(shí)，則有下一趟....第t次執(zhí)行后，y=t，此時(shí)為最后1趟，滿足n因此t是滿足的最小整數(shù)，即評分要點(diǎn)：向下取整寫成向上取整扣1分，沒有+1扣1分，沒有取整符號扣2分答案：漸進(jìn)時(shí)間復(fù)雜度是評分要點(diǎn)：沒有大O扣5分2.確定劃線語句的執(zhí)行次數(shù)，計(jì)算它們的漸近時(shí)間復(fù)雜度（注意本題有兩個(gè)問題，不討論n=1的情況）。i=1;x=0;for(i=0;i<p=""><>for(j=0;j<p=""><>a[i][j]=0;

答案：執(zhí)行次數(shù)為評分要點(diǎn)：寫成帶大O的形式扣5分答案：漸近時(shí)間復(fù)雜度是評分要點(diǎn)：沒有寫大O口5分3.確定劃線語句的執(zhí)行次數(shù)，計(jì)算它們的漸近時(shí)間復(fù)雜度（注意本題有兩個(gè)問題）。i=1;x=0;do{x++;i=3*i;}while(i<p=""><>

答案：執(zhí)行次數(shù)解析：設(shè)執(zhí)行次數(shù)為t，則有，不等式成立時(shí)為最后一次劃線語句執(zhí)行次。得到答案。評分要點(diǎn)：上下限寫錯(cuò)或沒有上下限得8分，寫成對數(shù)形式但是底數(shù)寫錯(cuò)得5分，寫成近似時(shí)間復(fù)雜度或者其他答案不給分答案：漸近時(shí)間復(fù)雜度評分要點(diǎn)：沒有大O扣5分；括號內(nèi)公式寫錯(cuò)扣5分；4.確定劃線語句的執(zhí)行次數(shù)，計(jì)算它們的漸近時(shí)間復(fù)雜度（注意本題有兩個(gè)問題）。i=1;k=0;do{k=k+10*i;i++;}while(i<=n)

答案：執(zhí)行次數(shù)為n寫成n+1但是沒有給條件或者O(n)扣5分答案：漸進(jìn)時(shí)間復(fù)雜度為O(n)評分要點(diǎn)：沒有寫大O扣5分第2章線性表（視頻總時(shí)長63'3''，共計(jì)9個(gè)）第2章單元測驗(yàn)1.單選題：在單鏈表中指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是：（）。

選項(xiàng)：

A、p->link=s;s->link=p->link;

B、s->link=p->link;p->link=s;

C、p->link=s;p->link=s->link;

D、p->link=s->link;p->link=s;

答案：【s->link=p->link;p->link=s;】2.單選題：在一個(gè)以first為頭指針的單循環(huán)鏈表中，p指針指向尾結(jié)點(diǎn)的條件是__________。

選項(xiàng)：

A、p->link=first

B、p->link=NULL

C、p->link->link=first

D、p->element=-1

答案：【p->link=first】3.單選題：設(shè)一個(gè)鏈表最常用的操作是在末尾插入結(jié)點(diǎn)和刪除尾結(jié)點(diǎn)，則選用________最節(jié)省時(shí)間。

選項(xiàng)：

A、單鏈表

B、單循環(huán)鏈表

C、帶尾指針的單循環(huán)鏈表

D、帶表頭結(jié)點(diǎn)的雙循環(huán)鏈表

答案：【帶表頭結(jié)點(diǎn)的雙循環(huán)鏈表】4.單選題：以下選項(xiàng)__________不是鏈表結(jié)構(gòu)所具備特征。

選項(xiàng)：

A、插入、刪除操作不需要移動(dòng)元素

B、可隨機(jī)存取任意位置元素

C、不必預(yù)先估計(jì)和申請連續(xù)存儲(chǔ)空間

D、所需存儲(chǔ)空間與線性表長度呈正比

答案：【可隨機(jī)存取任意位置元素】5.單選題：在帶表頭結(jié)點(diǎn)的單鏈表中，設(shè)指針first指向表頭結(jié)點(diǎn)，當(dāng)______時(shí)，表示鏈表為空。

選項(xiàng)：

A、first==NULL

B、first->link==NULL

C、first->link==first

D、first!=NULL

答案：【first->link==NULL】6.單選題：線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)所具有的特點(diǎn)是________。

選項(xiàng)：

A、所需空間地址必須連續(xù)

B、可隨機(jī)存取

C、插入、刪除操作不必移動(dòng)元素

D、需要事先估計(jì)所需存儲(chǔ)空間

答案：【插入、刪除操作不必移動(dòng)元素】7.單選題：已知順序表中每個(gè)元素占2個(gè)存儲(chǔ)單元，第一個(gè)元素存儲(chǔ)地址為100，則表中第6個(gè)元素的存儲(chǔ)地址是_______。

選項(xiàng)：

A、112

B、120

C、110

D、140

答案：【110】8.單選題：對于線性表，下列說法正確的是_______________。

選項(xiàng)：

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

B、線性表中至少要有一個(gè)元素

C、表中元素必須有序排列

D、除第一個(gè)元素與最后一個(gè)元素，其他每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼

答案：【除第一個(gè)元素與最后一個(gè)元素，其他每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼】9.單選題：如果線性表最常用的操作是讀取第i個(gè)元素的值，則采用______存儲(chǔ)方式最高效。

選項(xiàng)：

A、順序表

B、有序表

C、單鏈表

D、雙向鏈表

答案：【順序表】10.單選題：在包含n個(gè)結(jié)點(diǎn)的單鏈表上進(jìn)行元素查找操作，平均時(shí)間復(fù)雜度是_______。

選項(xiàng)：

A、O(1)

B、O(n)

C、O(n/2)

D、O(n^2)

答案：【O(n)】11.單選題：循環(huán)鏈表的主要優(yōu)點(diǎn)是_______。

選項(xiàng)：

A、不再需要頭指針

B、訪問某個(gè)結(jié)點(diǎn)時(shí)，可以快速訪問它的直接前驅(qū)

C、進(jìn)行插入和刪除操作時(shí)避免斷鏈現(xiàn)象

D、從表中任意結(jié)點(diǎn)出發(fā)都能掃描整個(gè)鏈表

答案：【從表中任意結(jié)點(diǎn)出發(fā)都能掃描整個(gè)鏈表】12.單選題：在單鏈表中添加表頭結(jié)點(diǎn)的目的是_______。

選項(xiàng)：

A、使得單鏈表至少存在一個(gè)結(jié)點(diǎn)

B、避免斷鏈現(xiàn)象

C、方便插入和刪除操作的實(shí)現(xiàn)

D、說明單鏈表是線性表的鏈?zhǔn)酱鎯?chǔ)

答案：【方便插入和刪除操作的實(shí)現(xiàn)】13.單選題：在循環(huán)單鏈表中，設(shè)指針first指向頭結(jié)點(diǎn)，當(dāng)_____時(shí)表示鏈表為空。

選項(xiàng)：

A、first==NULL

B、first->link==NULL

C、first->link==first

D、first->link->link==first

答案：【first==NULL】14.單選題：在單鏈表上進(jìn)行查找操作，最好情況的時(shí)間復(fù)雜度為O(1)。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】15.單選題：在順序表上進(jìn)行查找操作，最好情況的時(shí)間復(fù)雜度為O(n)。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】16.單選題：取單鏈表的第i個(gè)元素的時(shí)間與i值的大小有關(guān).

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】17.單選題：取順序表的第i個(gè)元素的時(shí)間與i值的大小有關(guān).

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】18.單選題：取線性表的第i個(gè)元素的時(shí)間與i值的大小有關(guān).

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】19.單選題：鏈表存儲(chǔ)實(shí)現(xiàn)的線性表上，元素的插入操作需要移動(dòng)的元素個(gè)數(shù)，與元素插入位置有關(guān)。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】20.單選題：順序存儲(chǔ)實(shí)現(xiàn)的線性表上，元素的插入操作需要移動(dòng)的元素個(gè)數(shù)，與元素插入位置有關(guān)。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】21.單選題：鏈表方式實(shí)現(xiàn)的線性表中，存在邏輯關(guān)系的兩個(gè)數(shù)據(jù)元素不一定存儲(chǔ)在相鄰的地址上。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】22.單選題：在順序表上，物理上相鄰的兩個(gè)數(shù)據(jù)元素之間存在邏輯關(guān)系。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】23.單選題：在順序表上，邏輯上相鄰的兩個(gè)數(shù)據(jù)元素，在物理存儲(chǔ)位置上不一定相鄰

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】24.單選題：線性表的特點(diǎn)是每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】25.單選題：順序存儲(chǔ)方式插入和刪除時(shí)效率太低，因此它不如鏈?zhǔn)酱鎯?chǔ)方式好。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】26.單選題：線性表采用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)的存儲(chǔ)空間可以是不連續(xù)的。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】27.單選題：線性表就是順序存儲(chǔ)的表。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】28.指針r的指向如上圖所示，現(xiàn)在需要在r后插入一個(gè)由指針p指向的新結(jié)點(diǎn)，請完成如下算法填空（答案中請不要包含空格和分號）：p->llink=r;p-rlink=r->rlink;r->rlink->llink=p;__________________;

答案：【r->rlink=p】29.指針r的指向如上圖所示，現(xiàn)在需要在r后插入一個(gè)由指針p指向的新結(jié)點(diǎn)，請完成如下算法填空（答案中請不要包含空格和分號）：p->llink=r;p-rlink=r->rlink;r->rlink=p;___________;

答案：【p->rlink->llink=p】30.線性表，在前插入一個(gè)元素，需要移動(dòng)______個(gè)元素（提示：答案不唯一，寫出一個(gè)答案即可）。

答案：【51/0】31.線性表，刪除需要移動(dòng)______個(gè)元素（提示：答案不唯一，寫出一個(gè)答案即可）。

答案：【50/0】第2章作業(yè)1.已知first指向鏈表結(jié)構(gòu)A的第一個(gè)結(jié)點(diǎn)，p是鏈表上的某個(gè)結(jié)點(diǎn)，請給出下列情況的判斷條件：（示例）如果A是單鏈表，則結(jié)點(diǎn)p是頭結(jié)點(diǎn)的判斷條件是什么？p結(jié)點(diǎn)是尾結(jié)點(diǎn)的判斷條件是什么？(頭結(jié)點(diǎn)特指存儲(chǔ)線性表第一個(gè)元素的結(jié)點(diǎn)，請與表頭結(jié)點(diǎn)區(qū)別)答：p==first是頭結(jié)點(diǎn)判斷條件，p->link==NULL是尾結(jié)點(diǎn)判斷條件。（1）如果A是帶表頭結(jié)點(diǎn)的單鏈表，則結(jié)點(diǎn)p是頭結(jié)點(diǎn)的判斷條件是什么？p結(jié)點(diǎn)是尾結(jié)點(diǎn)的判斷條件是什么？（2）如果A是單循環(huán)鏈表，則結(jié)點(diǎn)p是頭結(jié)點(diǎn)的判斷條件是什么？p結(jié)點(diǎn)是尾結(jié)點(diǎn)的判斷條件是什么？（3）如果A是帶表頭結(jié)點(diǎn)的循環(huán)鏈表，則結(jié)點(diǎn)p是頭結(jié)點(diǎn)的判斷條件是什么？p結(jié)點(diǎn)是尾結(jié)點(diǎn)的判斷條件是什么？

（1）如果A是帶表頭結(jié)點(diǎn)的單鏈表，則結(jié)點(diǎn)p是頭結(jié)點(diǎn)的判斷條件是什么？p結(jié)點(diǎn)是尾結(jié)點(diǎn)的判斷條件是什么？答案：p==first->link是頭結(jié)點(diǎn)判斷條件，p->link==NULL是尾結(jié)點(diǎn)判斷條件。（2）如果A是單循環(huán)鏈表，則結(jié)點(diǎn)p是頭結(jié)點(diǎn)的判斷條件是什么？p結(jié)點(diǎn)是尾結(jié)點(diǎn)的判斷條件是什么？答案：p==first是頭結(jié)點(diǎn)判斷條件，p->link==first是尾結(jié)點(diǎn)判斷條件。（3）如果A是帶表頭結(jié)點(diǎn)的循環(huán)鏈表，則結(jié)點(diǎn)p是頭結(jié)點(diǎn)的判斷條件是什么？p結(jié)點(diǎn)是尾結(jié)點(diǎn)的判斷條件是什么？答案：p==first-link是頭結(jié)點(diǎn)判斷條件，p->link==first是尾結(jié)點(diǎn)判斷條件。2.完成下列算法填空，將兩個(gè)有序遞增的帶表頭結(jié)點(diǎn)的單鏈表合并為一個(gè)有序遞增的單鏈表。鏈表結(jié)點(diǎn)Node和鏈表SingleList結(jié)構(gòu)體定義如下：typedefstructnode{ElemTypeelement;structnode*link;}Node;typedefstructheaderlist{Node*head;intn;}HeaderList;voidMergeList1(HeaderList*La,HeaderList*Lb,HeaderList*Lc){//合并鏈表La和Lb，合并后的新表使用頭指針Lc指向Node*pa,*pb,*pc,*q;pa=La->head->link;pb=Lb->head->link;pc=Lc->head;while(pa&&pb){if(____________________){pc->link=pa;pc=pa;pa=pa->link;La->n--;}elseif(pa->element>pb->element){pc->link=___________;pc=________;pb=_________;Lb->n--;}else{pc->link=pa;pc=pa;pa=_________;q=_________;free(pb);pb=q;}Lc->n++;}pc->link=pa?pa:pb;//插入剩余段Lc->n+=pa?La->n:Lb->n;}

voidMergeList1(headerList*La,headerList*Lb,headerList*Lc){//合并鏈表La和Lb，合并后的新表使用頭指針Lc指向Node*pa,*pb,*pc,*q;pa=La->head->link;pb=Lb->head->link;pc=Lc->head;while(pa&&pb){if(pa->elementelement){pc->link=pa;pc=pa;pa=pa->link;La->n--;}elseif(pa->element>pb->element){pc->link=pb;pc=pb;pb=pb->link;Lb->n--;}else{pc->link=pa;pc=pa;pa=pa->link;q=pb->link;free(pb);pb=q;}Lc->n++;}pc->link=pa?pa:pb;//插入剩余段Lc->n+=pa?La->n:Lb->n;}評分要點(diǎn)：一空5分3.請完成下列算法填空現(xiàn)對單鏈表的逆置存儲(chǔ)，逆置存儲(chǔ)是指將元素線性關(guān)系逆置后的鏈表存儲(chǔ)，例如（a0,a1,a2），關(guān)系逆置后為（a2,a1,a0).單鏈表結(jié)點(diǎn)Node和單鏈表SingleList結(jié)構(gòu)體定義如下：typedefstructnode{ElemTypeelement;structnode*link;}Node;typedefstructsinglelist{Node*first;intn;}SingleList;voidinvert(SingleList*L){Node*p=__________,*q;L->first=NULL;while(_____){q=p->link;p->link=_______;L->first=_______;p=_______;}}注意：程序題語法錯(cuò)誤不扣分，為了避免程序題在互評時(shí)因?yàn)檎Z法錯(cuò)誤帶來理解不當(dāng)被誤傷，請盡量寫清楚注釋，或簡單描述一下算法思想。

voidinvert(SingleList*L){Node*p=L->first,*q;L->first=NULL;while(p){q=p->link;p->link=L->first;L->first=p;p=q;}}評分標(biāo)準(zhǔn)：一個(gè)空7分，語法錯(cuò)誤不扣分4.請完成下列算法填空實(shí)現(xiàn)對順序表逆置存儲(chǔ)，逆置存儲(chǔ)是指將元素線性關(guān)系逆置后的順序存儲(chǔ)，例如（a0,a1,a2），關(guān)系逆置后為（a2,a1,a0).SeqList的結(jié)構(gòu)體定義如下：typedefstructseqList{intn;intmaxLength;ElemType*element;}SeqList;voidInvert(SeqList*L){ElemTypetemp;inti;for(i=0;i<________;i++){temp=____________;L->element[i]=L->element[___________];L->element[________]=___________;}}注意：程序題語法錯(cuò)誤不扣分，為了避免程序題在互評時(shí)因?yàn)檎Z法錯(cuò)誤被誤傷，請盡量寫清楚注釋，或簡單描述一下算法思想。

voidInvert(SeqList*L){ElemTypetemp;inti;for(i=0;in/2;i++){temp=L->element[i];L->element[i]=L->element[L->n-i-1];L->element[L->n-i-1]=temp;}}評分要點(diǎn)：語法錯(cuò)誤不扣分，一個(gè)空7分第3章堆棧和隊(duì)列（視頻總時(shí)長70'54''，共計(jì)9個(gè)）第3章作業(yè)1.請完成算法填空，實(shí)現(xiàn)帶表頭結(jié)點(diǎn)的單鏈表形式實(shí)現(xiàn)的隊(duì)列上的元素入隊(duì)與出隊(duì)操作，隊(duì)列和元素結(jié)點(diǎn)結(jié)構(gòu)體定義如下：typedefstructnode{ElemTypeelement;structnode*link;}Node;typedefstructqueue{Node*front;//注意front指向表頭結(jié)點(diǎn)，非頭結(jié)點(diǎn)，請對視頻中提供的代碼進(jìn)行修改Node*rear;//指向尾結(jié)點(diǎn)}Queue;voidEnQueue(Queue*Q,ElemTypex){Node*p=(Node*)malloc(sizeof(Node));____________=x;p->link=NULL;____________=p;Q->rear=p;}voidDeQueue(Queue*Q){//若隊(duì)列為空，直接返回if(___________==NULL)return;Node*p=_____________;Q->front->link=___________;free(p);//若出隊(duì)后，隊(duì)列為空，則需重置rearif(______________==NULL)Q->rear=Q->front;//指向表頭結(jié)點(diǎn)}特別注意！！！如果答案上傳的是完整代碼的，請標(biāo)記下劃線，以便于批改

voidEnQueue(Queue*Q,ElemTypex){Node*p=(Node*)malloc(sizeof(Node));p->element=x;p->link=NULL;Q->rear->link=p;Q->rear=p;}評分要點(diǎn)：一空4分voidDeQueue(Queue*Q){//若隊(duì)列為空，直接返回if(Q->front->link==NULL)return;Node*p=Q->front->link;Q->front->link=p->link;free(p);//若出隊(duì)后，隊(duì)列為空，則需重置rearif(Q->front->link==NULL)Q->rear=NULL;}評分要點(diǎn)：一空3分2.設(shè)A,B,C,D,E五個(gè)元素依次進(jìn)棧（允許元素進(jìn)棧后立即出棧），問能否得到下列元素出棧序列。若能得到，則給出相應(yīng)的push和pop操作序列；若不能，則說明理由。(1)A，B，C，D，E(2)A，C，E，B，D(3)C，A，B，D，E(4)E，D，C，B，A

(1)能，操作序列:push(A),pop(),push(B),pop(),push(C),pop(),push(D),pop(),push(E),pop()(2)和(3)不能。對(2)中的E，B，D而言，E最先出棧則表明，此時(shí)B和D均在棧中，由于，B先于D進(jìn)棧，所以應(yīng)有D先出棧。同理(3)也不能。(2)和(3)不能。對(2)中的E，B，D而言，E最先出棧則表明，此時(shí)B和D均在棧中，由于，B先于D進(jìn)棧，所以應(yīng)有D先出棧。同理(3)也不能。(4)能，操作序列:push(A),push(B),push(C),push(D),push(E),pop(),pop(),pop(),pop(),pop()3.寫出下列表達(dá)式的后綴形式。(1)(a+b)/(c+d）(2)b^2-4*a*c(3)a*c-b/c^2(4)(a+b)*c+d/(e+f）(5)(a+b)*(c*d+e)-a*c

(1)ab+cd+/(2)b2^4a*c*-(3)ac*bc2^/-(4)ab+c*def+/+(5)ab+cd*e+*ac*-第3章單元測驗(yàn)1.單選題：為解決計(jì)算機(jī)主機(jī)與打印機(jī)間速度不匹配問題，通常設(shè)一個(gè)打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要輸出的數(shù)據(jù)依次寫入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的數(shù)據(jù)結(jié)構(gòu)應(yīng)該是_____.

選項(xiàng)：

A、隊(duì)列

B、堆棧

C、有序表

D、數(shù)組

答案：【隊(duì)列】2.單選題：

選項(xiàng)：

A、21

B、20

C、19

D、18

答案：【21】3.單選題：

選項(xiàng)：

A、20

B、18

C、22

D、16

答案：【20】4.單選題：最多可存儲(chǔ)n個(gè)數(shù)據(jù)元素的循環(huán)隊(duì)列，front為隊(duì)頭標(biāo)識(shí)，rear為隊(duì)尾標(biāo)識(shí),則隊(duì)滿的條件是()

選項(xiàng)：

A、(rear+1)%(n+1)==front

B、(front+1)%(n+1)==rear

C、(rear+1)%n==front

D、(front+1)%n==rear

答案：【(rear+1)%(n+1)==front】5.單選題：最多可存儲(chǔ)n個(gè)數(shù)據(jù)元素的循環(huán)隊(duì)列，front為隊(duì)頭標(biāo)識(shí)，rear為隊(duì)尾標(biāo)識(shí),則隊(duì)空的條件是()

選項(xiàng)：

A、rear==front

B、front+1==rear

C、(rear+1)%n==front

D、(rear+1)%(n+1)==front

答案：【rear==front】6.單選題：遞歸過程或函數(shù)調(diào)用時(shí)，處理參數(shù)及返回地址，要用一種稱為______的數(shù)據(jù)結(jié)構(gòu)。

選項(xiàng)：

A、堆棧

B、隊(duì)列

C、數(shù)組

D、線性表

答案：【堆棧】7.單選題：設(shè)a,b,c,d,e,f依次進(jìn)棧，允許入棧后立刻出棧，則下面得不到的出棧序列為______。

選項(xiàng)：

A、f,e,d,c,b,a

B、b,c,a,f,e,d

C、d,c,e,f,b,a

D、c,a,b,d,e,f

答案：【c,a,b,d,e,f】8.單選題：設(shè)計(jì)一個(gè)判別表達(dá)式中左右括號是否配對出現(xiàn)的算法，采用_______實(shí)現(xiàn)最佳。

選項(xiàng)：

A、線性表的順序存儲(chǔ)結(jié)構(gòu)

B、隊(duì)列

C、線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

D、堆棧

答案：【堆棧】9.單選題：設(shè)棧S初始狀態(tài)為空，元素e1,e2，e3，e4,e5和e6依次進(jìn)入棧S，若6個(gè)元素出隊(duì)的序列是e2,e4,e3,e6,e5,e1，則棧S的容量至少應(yīng)該是__________。

選項(xiàng)：

A、6

B、5

C、4

D、3

答案：【3】10.單選題：棧和隊(duì)列的共同點(diǎn)是__________。

選項(xiàng)：

A、都是先進(jìn)先出

B、都是先進(jìn)后出

C、都是線性結(jié)構(gòu)

D、沒有共同點(diǎn)

答案：【都是線性結(jié)構(gòu)】11.單選題：假設(shè)以數(shù)組A[m]存放循環(huán)隊(duì)列的元素，front為隊(duì)頭標(biāo)識(shí)，rear為隊(duì)尾標(biāo)識(shí)，則當(dāng)前隊(duì)列中的元素個(gè)數(shù)為______。

選項(xiàng)：

A、(rear-front)%m

B、front-rear

C、(front-rear)%m

D、rear-front

答案：【(rear-front)%m】12.單選題：若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少?

選項(xiàng)：

A、1和5

B、2和4

C、4和2

D、5和1

答案：【2和4】13.單選題：用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除運(yùn)算時(shí)_______。

選項(xiàng)：

A、僅修改頭指針

B、僅修改尾指針

C、頭、尾指針都要修改

D、頭、尾指針可能都要修改

答案：【頭、尾指針可能都要修改】14.單選題：在具有m個(gè)存儲(chǔ)單元的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有個(gè)數(shù)據(jù)元素。

選項(xiàng)：

A、m

B、m-1

C、m-2

D、m+1

答案：【m-1】15.單選題：已知某多項(xiàng)式的中綴表達(dá)式為(a+b*c)/d+e*f，則其后綴表達(dá)式為_______。

選項(xiàng)：

A、abc*+d/ef*+

B、abc*+d/+ef*

C、abc*+def/*+

D、ab+c*d/ef*+

答案：【abc*+d/ef*+】16.單選題：設(shè)數(shù)組data[m]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭標(biāo)識(shí)，rear為隊(duì)尾標(biāo)識(shí)，則執(zhí)行出隊(duì)操作時(shí)對front執(zhí)行的操作是______。

選項(xiàng)：

A、front=front+1

B、front=(front+1)%(m-1)

C、front=(front-1)%m

D、front=(front+1)%m

答案：【front=(front+1)%m】17.單選題：若元素入棧序列為a,b,c,d，則不可能得到的出棧序列為_________（提示：元素可以入棧后立刻出棧）。

選項(xiàng)：

A、c,b,a,d

B、c,b,d,a

C、d,b,c,a

D、b,c,d,a

答案：【d,b,c,a】18.單選題：在移動(dòng)營業(yè)廳通過“取號、叫號”辦理業(yè)務(wù)的服務(wù)模式符合______特征。

選項(xiàng)：

A、集合

B、堆棧

C、隊(duì)列

D、線性表

答案：【隊(duì)列】19.單選題：堆棧和隊(duì)列的主要區(qū)別是_______。

選項(xiàng)：

A、邏輯結(jié)構(gòu)不同

B、存儲(chǔ)結(jié)構(gòu)不同

C、限定元素插入和刪除的位置不同

D、名字不同

答案：【限定元素插入和刪除的位置不同】20.單選題：設(shè)數(shù)組data[100]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭標(biāo)識(shí)，rear為隊(duì)尾標(biāo)識(shí)，當(dāng)front==80，rear==15時(shí)，以下說法正確的是_______。

選項(xiàng)：

A、data數(shù)組中下標(biāo)從16到79的位置都為空閑位置

B、隊(duì)列元素個(gè)數(shù)為36

C、data數(shù)組中下標(biāo)從16到80的位置都為空閑位置

D、隊(duì)列元素個(gè)數(shù)為34

答案：【data數(shù)組中下標(biāo)從16到79的位置都為空閑位置】21.單選題：設(shè)數(shù)組data[m]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭標(biāo)識(shí)，rear為隊(duì)尾標(biāo)識(shí)，則執(zhí)行入隊(duì)操作時(shí)對rear執(zhí)行的操作是______。

選項(xiàng)：

A、rear=(rear+1)%m

B、rear=(rear+1)%(m-1)

C、rear=rear+1

D、++rear

答案：【rear=(rear+1)%m】22.單選題：設(shè)數(shù)組data[20]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭標(biāo)識(shí)，rear為隊(duì)尾標(biāo)識(shí)，當(dāng)front==4，rear==15時(shí)，以下說法正確的是_______。

選項(xiàng)：

A、隊(duì)列中還能存放數(shù)據(jù)元素的空閑位置數(shù)量為8個(gè)

B、隊(duì)列中還能存放數(shù)據(jù)元素的空閑位置數(shù)量為7個(gè)

C、隊(duì)列中還能存放數(shù)據(jù)元素的空閑位置數(shù)量為9個(gè)

D、隊(duì)列中還能存放數(shù)據(jù)元素的空閑位置數(shù)量為6個(gè)

答案：【隊(duì)列中還能存放數(shù)據(jù)元素的空閑位置數(shù)量為8個(gè)】23.單選題：設(shè)數(shù)組data[20]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間，front為隊(duì)頭標(biāo)識(shí)，rear為隊(duì)尾標(biāo)識(shí)，當(dāng)front==4，rear==15時(shí)，以下說法正確的是_______。

選項(xiàng)：

A、data數(shù)組中下標(biāo)從4到15的位置存儲(chǔ)的是隊(duì)列元素

B、data數(shù)組中下標(biāo)從5到14的位置存儲(chǔ)的是隊(duì)列元素

C、該循環(huán)隊(duì)列當(dāng)前存儲(chǔ)的隊(duì)列元素個(gè)數(shù)是11個(gè)

D、該循環(huán)隊(duì)列當(dāng)前存儲(chǔ)的隊(duì)列元素個(gè)數(shù)是10個(gè)

答案：【該循環(huán)隊(duì)列當(dāng)前存儲(chǔ)的隊(duì)列元素個(gè)數(shù)是11個(gè)】24.單選題：算術(shù)表達(dá)式的后綴形式為264－×2/，每個(gè)操作數(shù)均為一位數(shù)，此表達(dá)式的值為_____。

選項(xiàng)：

A、2

B、1

C、3

D、4

答案：【2】25.單選題：設(shè)有一順序棧，元素3,2,1依次進(jìn)棧，進(jìn)棧后可立即出棧，共可得到________種不同的出棧序列。

選項(xiàng)：

A、5

B、6

C、4

D、3

答案：【5】26.單選題：一個(gè)棧的輸入序列是1,2,3,4,5，則棧的輸出序列不可能是1,2,3,4,5。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】27.單選題：設(shè)數(shù)組data[30]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間,front指向隊(duì)頭，則data[(front+1)%30]為隊(duì)頭元素

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】28.單選題：設(shè)數(shù)組data[20]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間,front指向隊(duì)頭，則data[front+1]為隊(duì)頭元素

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】29.單選題：設(shè)數(shù)組data[20]作為循環(huán)隊(duì)列SQ的存儲(chǔ)空間,front指向隊(duì)頭，則data[front]為隊(duì)頭元素

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】30.單選題：棧和隊(duì)列的存儲(chǔ)方式既可是順序方式，也可是鏈接方式。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】31.單選題：隊(duì)是一種插入和刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出型結(jié)構(gòu)。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】32.單選題：棧是一種對所有插入、刪除操作限于在表的一端進(jìn)行的線性表，是一種后進(jìn)先出型結(jié)構(gòu)。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】33.單選題：a^2的后綴表達(dá)式是aa*

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】34.單選題：已知某長度為maxSize的循環(huán)隊(duì)列,front為隊(duì)頭標(biāo)識(shí)，rear為隊(duì)尾標(biāo)識(shí)，則rear==front時(shí)表示該隊(duì)列為滿隊(duì)列。

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】第4章數(shù)組（視頻總時(shí)長64'46''，共計(jì)8個(gè)）第4章單元測驗(yàn)1.設(shè)有10階對稱矩陣A，其中矩陣元素用a(i,j)表示，i為行下標(biāo)，i=0,1,...,9，j為列下標(biāo)，j=0,1,...,9，將A按照行優(yōu)先順序存儲(chǔ)下三角元素的方式存儲(chǔ)至一維數(shù)組B，則數(shù)組B[7]中存儲(chǔ)的矩陣元素是a(___,___)。（請直接填寫i和j的值，用一個(gè)空格隔開，注意答案不唯一，寫一個(gè)即可）

答案：【13/31】2.設(shè)有10階對稱矩陣A，其中矩陣元素用a(i,j)表示，i為行下標(biāo)，i=0,1,...,9，j為列下標(biāo)，j=0,1,...,9，將A按照行優(yōu)先順序存儲(chǔ)下三角元素的方式存儲(chǔ)至一維數(shù)組B，則數(shù)組B[8]中存儲(chǔ)的矩陣元素是a(___,___)。（請直接填寫i和j的值，用一個(gè)空格隔開，注意答案不唯一，寫一個(gè)即可）

答案：【23/32】3.設(shè)有10階對稱矩陣A，其中矩陣元素用a(i,j)表示，i為行下標(biāo)，i=0,1,...,9，j為列下標(biāo)，j=0,1,...,9，將A按照行優(yōu)先順序存儲(chǔ)下三角元素的方式存儲(chǔ)至一維數(shù)組B，則數(shù)組B[6]中存儲(chǔ)的矩陣元素是a(___,___)。（請直接填寫i和j的值，用一個(gè)空格隔開，注意答案不唯一，寫一個(gè)即可）

答案：【30/03】4.設(shè)有10階對稱矩陣A，其中矩陣元素用a(i,j)表示，i為行下標(biāo)，i=0,1,...,9，j為列下標(biāo)，j=0,1,...,9，將A按照行優(yōu)先順序存儲(chǔ)下三角元素的方式存儲(chǔ)至一維數(shù)組B，則數(shù)組B[11]中存儲(chǔ)的矩陣元素是a(___,___)。（請直接填寫i和j的值，用一個(gè)空格隔開，注意答案不唯一，寫一個(gè)即可）

答案：【14/41】5.設(shè)有10階對稱矩陣A，其中矩陣元素用a(i,j)表示，i為行下標(biāo)，i=0,1,...,9，j為列下標(biāo)，j=0,1,...,9，將A按照行優(yōu)先順序存儲(chǔ)下三角元素的方式存儲(chǔ)至一維數(shù)組B，則數(shù)組B[34]中存儲(chǔ)的矩陣元素是a(___,___)。（請直接填寫i和j的值，用一個(gè)空格隔開，注意答案不唯一，寫一個(gè)即可）

答案：【67/76】6.設(shè)有6階對稱矩陣A，其中矩陣元素用a(i,j)表示，i為行下標(biāo)，i=0,1,...,5，j為列下標(biāo)，j=0,1,...,5，將A按照行優(yōu)先順序存儲(chǔ)下三角元素的方式存儲(chǔ)至一維數(shù)組B，設(shè)每個(gè)矩陣元素占2個(gè)字節(jié)，已知數(shù)組B的首地址為100，則，a(3,3)的地址是_________。

答案：【118】7.設(shè)有6階對稱矩陣A，其中矩陣元素用a(i,j)表示，i為行下標(biāo)，i=0,1,...,5，j為列下標(biāo)，j=0,1,...,5，將A按照行優(yōu)先順序存儲(chǔ)下三角元素的方式存儲(chǔ)至一維數(shù)組B，設(shè)每個(gè)矩陣元素占2個(gè)字節(jié)，已知數(shù)組B的首地址為100，則，a(0,5)的地址是_________。

答案：【130】8.將4×6的二維數(shù)組A按照行優(yōu)先順序存儲(chǔ)到一維數(shù)組B中，則B[0]中存儲(chǔ)的二維數(shù)組元素是A[0][__]。

答案：【0】9.將4×6的二維數(shù)組A按照行優(yōu)先順序存儲(chǔ)到一維數(shù)組B中，則B[3]中存儲(chǔ)的二維數(shù)組元素是A[0][__]。

答案：【3】10.將4×6的二維數(shù)組A按照行優(yōu)先順序存儲(chǔ)到一維數(shù)組B中，則B[19]中存儲(chǔ)的二維數(shù)組元素是A[3][__]。

答案：【1】11.將4×6的二維數(shù)組A按照行優(yōu)先順序存儲(chǔ)到一維數(shù)組B中，則B[6]中存儲(chǔ)的二維數(shù)組元素是A[1][__]。

答案：【0】12.設(shè)有5×8的數(shù)組A，其每個(gè)元素占4個(gè)字節(jié)，已知A[3][3]在內(nèi)存中的地址是148，按行優(yōu)先順序存儲(chǔ)，A[4][5]的地址是_________。

答案：【188】13.設(shè)有5×8的數(shù)組A，其每個(gè)元素占4個(gè)字節(jié)，已知A[0][3]在內(nèi)存中的地址是52，按行優(yōu)先順序存儲(chǔ)，A[4][4]的地址是_________。

答案：【184】14.設(shè)有5×8的數(shù)組A，其每個(gè)元素占4個(gè)字節(jié)，已知A[3][4]在內(nèi)存中的地址是152，按行優(yōu)先順序存儲(chǔ)，A[2][0]的地址是_________。

答案：【104】15.設(shè)有5×8的數(shù)組A，其每個(gè)元素占4個(gè)字節(jié)，已知A[2][5]在內(nèi)存中的地址是124，按行優(yōu)先順序存儲(chǔ)，A[1][3]的地址是_________。

答案：【84】16.設(shè)有6階對稱矩陣A，其中矩陣元素用a(i,j)表示，i為行下標(biāo)，i=0,1,...,5，j為列下標(biāo)，j=0,1,...,5，將A按照行優(yōu)先順序存儲(chǔ)下三角元素的方式存儲(chǔ)至一維數(shù)組B，設(shè)每個(gè)矩陣元素占2個(gè)字節(jié)，已知數(shù)組B的首地址為100，則，a(5,5)的地址是_________。

答案：【140】17.設(shè)有6階對稱矩陣A，其中矩陣元素用a(i,j)表示，i為行下標(biāo)，i=0,1,...,5，j為列下標(biāo)，j=0,1,...,5，將A按照行優(yōu)先順序存儲(chǔ)下三角元素的方式存儲(chǔ)至一維數(shù)組B，設(shè)每個(gè)矩陣元素占2個(gè)字節(jié)，已知數(shù)組B的首地址為100，則，a(2,3)的地址是_________。

答案：【116】18.設(shè)有6階對稱矩陣A，其中矩陣元素用a(i,j)表示，i為行下標(biāo)，i=0,1,...,5，j為列下標(biāo)，j=0,1,...,5，將A按照行優(yōu)先順序存儲(chǔ)下三角元素的方式存儲(chǔ)至一維數(shù)組B，設(shè)每個(gè)矩陣元素占2個(gè)字節(jié)，已知數(shù)組B的首地址為100，則，a(1,3)的地址是_________。

答案：【114】[vk-content]19.設(shè)有5×8的數(shù)組A，其每個(gè)元素占2個(gè)字節(jié)，已知A[0][4]在內(nèi)存中的地址是120，按列優(yōu)先順序存儲(chǔ)，A[2][6]的地址是_________。

答案：【144】20.設(shè)有5×8的數(shù)組A，其每個(gè)元素占2個(gè)字節(jié)，已知A[1][3]在內(nèi)存中的地址是112，按列優(yōu)先順序存儲(chǔ)，A[0][5]的地址是_________。

答案：【130】21.設(shè)有5×8的數(shù)組A，其每個(gè)元素占2個(gè)字節(jié)，已知A[0][5]在內(nèi)存中的地址是130，按列優(yōu)先順序存儲(chǔ)，A[2][1]的地址是_________。

答案：【94】22.設(shè)有5×8的數(shù)組A，其每個(gè)元素占2個(gè)字節(jié)，已知A[3][6]在內(nèi)存中的地址是146，按列優(yōu)先順序存儲(chǔ)，A[1][4]的地址是_________。

答案：【122】23.將4×6的二維數(shù)組A按照行優(yōu)先順序存儲(chǔ)到一維數(shù)組B中，則B[23]中存儲(chǔ)的二維數(shù)組元素是A[3][__]。

答案：【5】24.設(shè)有10×5的數(shù)組A，其每個(gè)元素占2個(gè)字節(jié)，已知A[6][3]在內(nèi)存中的地址是166，按行優(yōu)先順序存儲(chǔ)，A[2][0]的地址是_________。

答案：【120】25.設(shè)有10×5的數(shù)組A，其每個(gè)元素占2個(gè)字節(jié)，已知A[0][2]在內(nèi)存中的地址是104，按行優(yōu)先順序存儲(chǔ)，A[8][2]的地址是_________。

答案：【184】26.設(shè)有10×5的數(shù)組A，其每個(gè)元素占2個(gè)字節(jié)，已知A[7][3]在內(nèi)存中的地址是176，按行優(yōu)先順序存儲(chǔ)，A[6][0]的地址是_________。

答案：【160】27.設(shè)有10×5的數(shù)組A，其每個(gè)元素占2個(gè)字節(jié)，已知A[3][2]在內(nèi)存中的地址是134，按行優(yōu)先順序存儲(chǔ)，A[0][1]的地址是_________。

答案：【102】第4章作業(yè)1.稀疏矩陣如下圖所示，請給出(1)行三元組表;(2)快速轉(zhuǎn)置算法所需的num數(shù)組;(3)快速轉(zhuǎn)置算法所需的k數(shù)組。

評分要點(diǎn)：錯(cuò)一處扣2分，扣完為止評分要點(diǎn)：錯(cuò)一處扣2分，扣完為止2.稀疏矩陣以行三元組表方式存儲(chǔ)，請完成下列程序?qū)崿F(xiàn)稀疏矩陣元素的查找運(yùn)算，并給出算法時(shí)間復(fù)雜度分析。提示：實(shí)現(xiàn)該方法所需結(jié)構(gòu)體定義如下typedefintElemType;typedefstructterm{intcol,row;/*非零元素在稀疏矩陣中的列下標(biāo)col和行下標(biāo)row*/ElemTypevalue;/*非零元素的值*/}Term;typedefstructsparsematrix{intm,n,t;/*m是矩陣行數(shù)，n是矩陣列數(shù)，t是實(shí)際非零元素個(gè)數(shù)*/Termtable[maxSize];/*存儲(chǔ)非零元素的三元組表*/}SparseMatrix;ElemTypeFind(SparseMatrix*M,inti,intj){if(i>=m||j>=n)returnNULL;for(k=0;k<__________;k++){if(M->table[k].row==_________&&M->table[k].col==j)returnM->table[k].value;}returnZERO;//ZERO為預(yù)定義的零元值}

ElemTypeFind(SparseMatrix*M,inti,intj){if(i>=m||j>=n)returnNULL;for(k=0;kt;k++){if(M->table[k].row==i&&M->table[k].col==j)returnM->table[k].value;}returnZERO;//ZERO為預(yù)定義的零元值}評分要點(diǎn)：一空5分時(shí)間復(fù)雜度是O(t)評分要點(diǎn)：沒有大O扣5分3.以行優(yōu)先存儲(chǔ)對稱矩陣的下三角元素，對稱矩陣結(jié)構(gòu)體定義如下：typedefintElemType;typedefstructsmatrix{ElemType*elements;intm;//階數(shù)}SMatrix請完成以下算法填空題：（1）查找運(yùn)算ElemTypeFind(SMatrix*dm,inti,intj)//查找[i][j]ElemTypeFind(SMatrix*dm,inti,intj)//m行m列{inttemp,k;if(i<0||i>=_________||j<0||j>=___________)returnERROR;if(i<p=""><>{temp=i;____________;j=temp;}k=_____________;returndm->elements[k];}（2）賦值運(yùn)算voidSetValue(SMatrix*dm,inti,intj,ElemTypex)voidSetValue(SMatrix*dm,inti,intj,ElemTypex)//設(shè)置[i][j]=x{inttemp,k;if(ik=____________;dm->elements[_________]=___________;}

//查找[i][j]ElemTypeFind(SMatrix*dm,inti,intj)//m行m列{inttemp,k;if(i<0||i>=dm->m||j<0||j>=dm->m)returnERROR;if(ii=j;j=temp;}k=(1+i)*i/2+j;returndm->elements[k];}評分要點(diǎn)：一空5分//賦值voidSetValue(SMatrix*dm,inti,intj,ElemTypex)//設(shè)置[i][j]=x{inttemp,k;if(ii=j;j=temp;}k=(1+i)*i/2+j;dm->elements[k]=x;}評分要點(diǎn)：一空5分第5章樹和二叉樹（視頻總時(shí)長220'10''，共計(jì)22個(gè)）第5章單元測驗(yàn)（二叉樹的性質(zhì)、遍歷算法）1.單選題：一個(gè)高度為4的滿二叉樹上共有______個(gè)分支結(jié)點(diǎn)。

選項(xiàng)：

A、4

B、5

C、6

D、7

答案：【7】2.單選題：一個(gè)高度為7的滿二叉樹上共有______個(gè)分支結(jié)點(diǎn)。

選項(xiàng)：

A、61

B、62

C、63

D、64

答案：【63】3.單選題：一個(gè)高度為6的滿二叉樹上共有______個(gè)分支結(jié)點(diǎn)。

選項(xiàng)：

A、30

B、31

C、32

D、33

答案：【31】4.單選題：一個(gè)高度為9的滿二叉樹上共有______個(gè)分支結(jié)點(diǎn)。

選項(xiàng)：

A、254

B、255

C、256

D、257

答案：【255】5.單選題：高度為4的二叉樹上至多有_______個(gè)結(jié)點(diǎn)。

選項(xiàng)：

A、15

B、16

C、17

D、18

答案：【15】6.單選題：高度為6的二叉樹上至多有_______個(gè)結(jié)點(diǎn)。

選項(xiàng)：

A、62

B、63

C、64

D、65

答案：【63】7.單選題：一個(gè)高度為5的二叉樹上最多有____個(gè)葉子結(jié)點(diǎn)。

選項(xiàng)：

A、8

B、16

C、24

D、32

答案：【16】8.單選題：一個(gè)高度為9的二叉樹上最多有____個(gè)葉子結(jié)點(diǎn)。

選項(xiàng)：

A、64

B、128

C、256

D、512

答案：【256】9.單選題：一個(gè)高度為3的二叉樹上最多有____個(gè)葉子結(jié)點(diǎn)。

選項(xiàng)：

A、1

B、2

C、3

D、4

答案：【4】10.單選題：假設(shè)一棵含有15個(gè)結(jié)點(diǎn)的完全二叉樹中，按層次從上到下、每層結(jié)點(diǎn)從左到右的順序，從0到14編號，則編號為6的結(jié)點(diǎn)的左孩子編號為____________。

選項(xiàng)：

A、7

B、12

C、13

D、無左孩子

答案：【13】11.單選題：在一棵度為3的樹中，度為3的結(jié)點(diǎn)個(gè)數(shù)為2，度為2的結(jié)點(diǎn)個(gè)數(shù)為1，則度為0的結(jié)點(diǎn)個(gè)數(shù)為_________。

選項(xiàng)：

A、4

B、5

C、6

D、7

答案：【6】12.包含216個(gè)元素的完全二叉樹的高度是_________。

答案：【8】13.包含314個(gè)元素的完全二叉樹的高度是_________。

答案：【9】14.包含96個(gè)元素的完全二叉樹的高度是_________。

答案：【7】15.包含494個(gè)元素的二叉樹的高度至少為_________。

答案：【9】16.包含300個(gè)元素的二叉樹的高度至少為_________。

答案：【9】17.包含169個(gè)元素的二叉樹的高度至少為_________。

答案：【8】18.包含80個(gè)元素的二叉樹的高度至少為_________。

答案：【7】19.一棵二叉樹中，若度為1的結(jié)點(diǎn)個(gè)數(shù)為19，度為2的結(jié)點(diǎn)的個(gè)數(shù)為15，則葉結(jié)點(diǎn)的個(gè)數(shù)為_______。

答案：【16】20.已知一棵二叉樹結(jié)點(diǎn)的先序遍歷序列為：C,A,D,E,B,F,中序遍歷序列為A,C,B,F,E,D,則結(jié)點(diǎn)B的右孩子為：_______。（請用NULL表示空，答案里不要有空格）

答案：【F】21.已知一棵二叉樹結(jié)點(diǎn)的先序遍歷序列為：F,C,B,D,E,A,中序遍歷序列為C,F,D,B,E,A,則結(jié)點(diǎn)B的右孩子為：_______。（請用NULL表示空，答案里不要有空格）

答案：【E】22.已知一棵二叉樹結(jié)點(diǎn)的先序遍歷序列為：A,B,F,E,C,D,中序遍歷序列為B,E,F,A,C,D,則結(jié)點(diǎn)F的左孩子為：_______。（請用NULL表示空，答案里不要有空格）

答案：【E】23.已知一棵二叉樹結(jié)點(diǎn)的先序遍歷序列為：E,B,F,C,A,D,中序遍歷序列為B,F,C,E,A,D,則結(jié)點(diǎn)B的右孩子為：_______。（請用NULL表示空，答案里不要有空格）

答案：【F】24.已知一棵二叉樹結(jié)點(diǎn)的先序遍歷序列為：F,B,D,C,E,A,中序遍歷序列為D,C,B,F,E,A,則結(jié)點(diǎn)D的右孩子為：_______。（請用NULL表示空，答案里不要有空格）

答案：【C】25.已知一棵二叉樹結(jié)點(diǎn)的先序遍歷序列為：A,D,B,C,E,F,中序遍歷序列為D,A,E,C,F,B,則結(jié)點(diǎn)C的左孩子為：_______。（請用NULL表示空，答案里不要有空格）

答案：【E】26.已知一棵二叉樹結(jié)點(diǎn)的先序遍歷序列為：D,F,A,E,C,B,中序遍歷序列為A,F,E,C,D,B,則結(jié)點(diǎn)D的左孩子為：_______。（請用NULL表示空，答案里不要有空格）

答案：【F】27.已知一棵二叉樹結(jié)點(diǎn)的先序遍歷序列為：C,F,E,A,D,B,中序遍歷序列為E,A,F,B,D,C,則結(jié)點(diǎn)B的左孩子為：_______。（請用NULL表示空，答案里不要有空格）

答案：【NULL】28.假設(shè)一棵含有13個(gè)結(jié)點(diǎn)的完全二叉樹中，按層次從上到下、每層結(jié)點(diǎn)從左到右的順序，從0開始編號，則編號為4的結(jié)點(diǎn)的右孩子編號為_______（如果孩子不存在，則填寫NULL）。

答案：【10】29.假設(shè)一棵含有16個(gè)結(jié)點(diǎn)的完全二叉樹中，按層次從上到下、每層結(jié)點(diǎn)從左到右的順序，從0開始編號，則編號為12的結(jié)點(diǎn)的右孩子編號為_______（如果孩子不存在，則填寫NULL）。

答案：【NULL】30.假設(shè)一棵含有18個(gè)結(jié)點(diǎn)的完全二叉樹中，按層次從上到下、每層結(jié)點(diǎn)從左到右的順序，從0開始編號，則編號為14的結(jié)點(diǎn)的左孩子編號為_______（如果孩子不存在，則填寫NULL）。

答案：【NULL】31.假設(shè)一棵含有16個(gè)結(jié)點(diǎn)的完全二叉樹中，按層次從上到下、每層結(jié)點(diǎn)從左到右的順序，從0開始編號，則編號為6的結(jié)點(diǎn)的左孩子編號為_______（如果孩子不存在，則填寫NULL）。

答案：【13】32.一棵二叉樹中，若葉結(jié)點(diǎn)的個(gè)數(shù)為11，度為1的結(jié)點(diǎn)個(gè)數(shù)為18，度為2的結(jié)點(diǎn)的個(gè)數(shù)為_______。

答案：【10】33.一棵二叉樹中，若度為1的結(jié)點(diǎn)個(gè)數(shù)為17，度為2的結(jié)點(diǎn)的個(gè)數(shù)為8，則葉結(jié)點(diǎn)的個(gè)數(shù)為_______。

答案：【9】34.一棵二叉樹中，若度為1的結(jié)點(diǎn)個(gè)數(shù)為18，度為2的結(jié)點(diǎn)的個(gè)數(shù)為18，則葉結(jié)點(diǎn)的個(gè)數(shù)為_______。

答案：【19】35.一棵二叉樹中，若葉結(jié)點(diǎn)的個(gè)數(shù)為14，度為1的結(jié)點(diǎn)個(gè)數(shù)為12，度為2的結(jié)點(diǎn)的個(gè)數(shù)為_______。

答案：【13】36.高度為9的二叉樹上至多有_______個(gè)結(jié)點(diǎn)。

答案：【511】37.假設(shè)一棵含有19個(gè)結(jié)點(diǎn)的完全二叉樹中，按層次從上到下、每層結(jié)點(diǎn)從左到右的順序，從0開始編號，則編號為7的結(jié)點(diǎn)的左孩子編號為_______（如果孩子不存在，則填寫NULL）。

答案：【15】38.已知某二叉樹的高度為6，則該樹上最多有_______個(gè)結(jié)點(diǎn)。

答案：【63】39.一棵有n個(gè)結(jié)點(diǎn)的二叉樹采用二叉鏈表方式存儲(chǔ)，有________個(gè)空指針域（答案不要有空格）。

答案：【n+1】40.已知一棵二叉樹結(jié)點(diǎn)的先序遍歷序列為：F,A,C,B,D,E,中序遍歷序列為A,F,D,B,C,E,則結(jié)點(diǎn)B的右孩子為：_______。（請用NULL表示空，答案里不要有空格）

答案：【NULL】41.已知一棵二叉樹結(jié)點(diǎn)的先序遍歷序列為：C,A,D,B,E,F,中序遍歷序列為C,D,A,E,B,F,則結(jié)點(diǎn)B的左孩子為：_______。（請用NULL表示空，答案里不要有空格）

答案：【E】42.已知一棵二叉樹結(jié)點(diǎn)的先序遍歷序列為：E,C,B,D,F,A,中序遍歷序列為B,D,C,E,A,F,則結(jié)點(diǎn)C的左孩子為：_______。（請用NULL表示空，答案里不要有空格）

答案：【B】43.已知一棵二叉樹結(jié)點(diǎn)的先序遍歷序列為：F,D,A,E,C,B,中序遍歷序列為D,E,A,F,C,B,則結(jié)點(diǎn)D的左孩子為：_______。（請用NULL表示空，答案里不要有空格）

答案：【NULL】第5章單元測驗(yàn)（森林轉(zhuǎn)換二叉樹、堆、哈夫曼編碼）1.單選題：序列63,73,29,28,14,71是最大堆

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】2.單選題：序列61,19,17,36,33,71不是最小堆

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】3.單選題：序列56,42,24,12,30,11不是最大堆

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】4.單選題：序列33,27,95,19,45,17不是最小堆

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】5.單選題：序列53,23,62,70,42,15不是最大堆

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】6.單選題：序列86,84,74,7,71,68是最大堆

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】7.單選題：序列95,78,33,17,41,23是最大堆

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】8.單選題：序列58,40,72,99,9,10是最大堆

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】9.單選題：序列11,42,58,80,46,67不是最小堆

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【錯(cuò)誤】10.單選題：序列37,82,81,56,48,42不是最大堆

選項(xiàng)：

A、正確

B、錯(cuò)誤

答案：【正確】11.已知英文字母集合{A,B,C,D,E,F,G,H}及其權(quán)值集合{24,19,29,9,6,13,17,21}，對字母進(jìn)行哈夫曼編碼，得到的哈夫曼樹的WPL值為_________（提示：要求對應(yīng)的哈夫曼樹上任意結(jié)點(diǎn)的左孩子權(quán)值不大于右孩子權(quán)值，答案中不要有空格）

答案：【400】12.已知英文字母集合{A,B,C,D,E,F,G,H}及其權(quán)值集合{24,19,29,9,6,13,17,21}，英文字母H的哈夫曼編碼為_________（提示：要求該編碼對應(yīng)的哈夫曼樹上左分支編碼為0，右分支編碼為1，且任意結(jié)點(diǎn)的左孩子權(quán)值不大于右孩子權(quán)值，答案中不要有空格）

答案：【110】13.已知英文字母集合{A,B,C,D,E,F,G,H}及其權(quán)值集合{24,19,29,9,6,13,17,21}，英文字母G的哈夫曼編碼為_________（提示：要求該編碼對應(yīng)的哈夫曼樹上左分支編碼為0，右分支編碼為1，且任意結(jié)點(diǎn)的左孩子權(quán)值不大于右孩子權(quán)值，答案中不要有空格）

答案：【100】14.已知英文字母集合{A,B,C,D,E,F,G,H}及其權(quán)值集合{24,19,29,9,6,13,17,21}，英文字母F的哈夫曼編碼為_________（提示：要求該編碼對應(yīng)的哈夫曼樹上左分支編碼為0，右分支編碼為1，且任意結(jié)點(diǎn)的左孩子權(quán)值不大于右孩子權(quán)值，答案中不要有空格）

答案：【000】15.已知英文字母集合{A,B,C,D,E,F,G,H}及其權(quán)值集合{24,19,29,9,6,13,17,21}，英文字母E的哈夫曼編碼為_________（提示：要求該編碼對應(yīng)的哈夫曼樹上左分支編碼為0，右分支編碼為1，且任意結(jié)點(diǎn)的左孩子權(quán)值不大于右孩子權(quán)值，答案中不要有空格）

答案：【0010】16.已知英文字母集合{A,B,C,D,E,F,G,H}及其權(quán)值集合{24,19,29,9,6,13,17,21}，英文字母D的哈夫曼編碼為_________（提示：要求該編碼對應(yīng)的哈夫曼樹上左分支編碼為0，右分支編碼為1，且任意結(jié)點(diǎn)的左孩子權(quán)值不大于右孩子權(quán)值，答案中不要有空格）

答案：【0011】17.已知英文字母集合{A,B,C,D,E,F,G,H}及其權(quán)值集合{24,19,29,9,6,13,17,21}，英文字母C的哈夫曼編碼為_________（提示：要求該編碼對應(yīng)的哈夫曼樹上左分支編碼為0，右分支編碼為1，且任意結(jié)點(diǎn)的左孩子權(quán)值不大于右孩子權(quán)值，答案中不要有空格）

答案：【01】18.已知英文字母集合{A,B,C,D,E,F,G,H}及其權(quán)值集合{24,19,29,9,6,13,17,21}，英文字母B的哈夫曼編碼為_________（提示：要求該編碼對應(yīng)的哈夫曼樹上左分支編碼為0，右分支編碼為1，且任意結(jié)點(diǎn)的左孩子權(quán)值不大于右孩子權(quán)值，答案中不要有空格）

答案：【101】19.對最小堆序列10,21,70,27,31,83執(zhí)行2次刪除操作（提示：對優(yōu)先級隊(duì)列執(zhí)行刪除操作默認(rèn)刪除堆頂元素）后得到最小堆序列_____________（提示：堆元素刪除操作需調(diào)用AdjustDown方法，請將答案表示成元素序列，并用半角逗號相隔，答案中不要有空格）。

答案：【27,31,70,83】20.對最大堆序列95,61,66,9,19,27執(zhí)行1次刪除操作（提示：對優(yōu)先級隊(duì)列執(zhí)行刪除操作默認(rèn)刪除堆頂元素）后得到最大堆序列_____________（提示：堆元素刪除操作需調(diào)用AdjustDown方法，請將答案表示成元素序列，并用半角逗號相隔，答案中不要有空格）。

答案：【66,61,27,9,19】21.向最大堆99,72,76,7,30,41依次插入元素86,91,91,94,97，最終得到的最大堆是____________（提示：堆的元素插入操作需調(diào)用AdjustUp方法，請將答案表示成元素序列，并用半角逗號相隔，答案中不要有空格）。

答案：【99,97,86,91,94,41,76,7,72,30,91】22.向最大堆84,49,82,26,29,46依次插入元素94,99,89,80,94，最終得到的最大堆是____________（提示：堆的元素插入操作需調(diào)用AdjustUp方法，請將答案表示成元素序列，并用半角逗號相隔，答案中不要有空格）。

答案：【99,94,84,89,94,46,82,26,49,29,80】23.向最大堆92,54,65,18,36,53依次插入元素82,86,88,97,81，最終得到的最大堆是____________（提示：堆的元素插入操作需調(diào)用AdjustUp方法，請將答案表示成元素序列，并用半角逗號相隔，答案中不要有空格）。

答案：【97,92,82,86,88,53,65,18,54,36,81】24.向最大堆71,69,32,25,33,15依次插入元素84，最終得到的最大堆是____________（提示：堆的元素插入操作需調(diào)用AdjustUp方法，請將答案表示成元素序列，并用半角逗號相隔，答案中不要有空格）。

答案：【84,69,71,25,33,15,32】25.請將給定數(shù)據(jù)元素序列72,46,24,44,91,96調(diào)整成最大堆：____________（提示：調(diào)整過程需調(diào)用AdjustDown方法，請將答案表示成元素序列，并用半角逗號相隔，答案中不要有空格）。

答案：【96,91,72,44,46,24】26.請將給定數(shù)據(jù)元素序列36,65,42,54,98,76調(diào)整成最小堆：____________（提示：調(diào)整過程需調(diào)用AdjustDown方法，請將答案表示成元素序列，并用半角逗號相隔，答案中不要有空格）。

答案：【36,54,42,65,98,76】27.已知英文字母集合{A,B,C,D,E,F,G,H}及其權(quán)值集合{24,19,29,9,6,13,17,21}，英文字母A的哈夫曼編碼為_________（提示：要求該編碼對應(yīng)的哈夫曼樹上左分支編碼為0，右分支編碼為1，且任意結(jié)點(diǎn)的左孩子權(quán)值不大于右孩子權(quán)值，答案中不要有空格）

答案：【111】28.已知一個(gè)有序森林如下圖所示，它的中序遍歷序列為_______________________（答案請表示為結(jié)點(diǎn)序列，用半角逗號相隔，答案不要有空格）。

答案：【D,A,H,G,E,C,F,B】29.已知一個(gè)有序森林如下圖所示，它的中序遍歷序列為_______________________（答案請表示為結(jié)點(diǎn)序列，用半角逗號相隔，答案不要有空格）。

答案：【D,H,A,B,F,C,G,E】30.已知一個(gè)有序森林如下圖所示，它的先序遍歷序列為_______________________（答案請表示為結(jié)點(diǎn)序列，用半角逗號相隔，答案不要有空格）。

答案：【G,A,H,D,C,E,F,B】31.已知一個(gè)有序森林如下圖所示，它的先序遍歷序列為_______________________（答案請表示為結(jié)點(diǎn)序列，用半角逗號相隔，答案不要有空格）。

答案：【D,H,E,F,B,C,A,G】32.已知一個(gè)有序森林如下圖所示，它的先序遍歷序列為_______________________（答案請表示為結(jié)點(diǎn)序列，用半角逗號相隔，答案不要有空格）。

答案：【A,D,H,B,F,E,G,C】33.對最大堆序列61,56,48,23,53,19執(zhí)行1次刪除操作（提示：對優(yōu)先級隊(duì)列執(zhí)行刪除操作默認(rèn)刪除堆頂元素）后得到最大堆序列_____________（提示：堆元素刪除操作需調(diào)用AdjustDown方法，請將答案表示成元素序列，并用半角逗號相隔，答案中不要有空格）。

答案：【56,53,48,23,19】34.對最大堆序列59,55,57,50,45,22執(zhí)行3次刪除操作（提示：對優(yōu)先級隊(duì)列執(zhí)行刪除操作默認(rèn)刪除堆頂元素）后得到最大堆序列_____________（提示：堆元素刪除操作需調(diào)用AdjustDown方法，請將答案表示成元素序列，并用半角逗號相隔，答案中不要有空格）。

答案：【50,45,22】35.請將給定數(shù)據(jù)元素序列87,32,15,22,56,43調(diào)整成最小堆：____________（提示：調(diào)整過程需調(diào)用AdjustDown方法，請將答案表示成元素序列，并用半角逗號相隔，答案中不要有空格）。

答案：【15,22,43,32,56,87】36.請將給定數(shù)據(jù)元素序列71,28,21,72,92,73調(diào)整成最小堆：____________（提示：調(diào)整過程需調(diào)用AdjustDown方法，請將答案表示成元素序列，并用半角逗號相隔，答案中不要有空格）。

答案：【21,28,71,72,92,73】第5章作業(yè)（森林、堆、哈夫曼編碼）1.已知英文字母集合{A,B,C,D,E,F,G,H}及其權(quán)值集合{29,9,26,27,2,23,8,24}，請給出以上英文字母的哈夫曼編碼并計(jì)算WPL值，要求該編碼對應(yīng)的哈夫曼樹上左分支編碼為0，右分支編碼為1，且任意結(jié)點(diǎn)的左孩子權(quán)值不大于右孩子權(quán)值。A:____________B:____________C:____________D:____________E:____________F:____________G:____________H:____________WPL=____________

字符與編碼的對應(yīng)關(guān)系如下：A:01B:1000C:111D:00E:10010F:101G:10011H:110WPL=417評分要點(diǎn)：編碼錯(cuò)一個(gè)扣2分，WPL錯(cuò)扣4分2.對最小堆序列14,39,50,79,95,59執(zhí)行2次刪除操作，請給出最終得到的最小堆。

50,59,95,793.向最小堆35,75,37,85,93,72依次插入元素1,6，請給出最終得到的最小堆。

1,6,35,75,93,72,37,854.請將給定數(shù)據(jù)元素序列84,23,32,54,16,97調(diào)整成最大堆。

97,54,84,23,16,325.已知一個(gè)有序森林如下所示，請給出它的帶右鏈的先序表示法（填寫圖下方表格即可）。下標(biāo)0123456789elementltagsibling

elementBDEAFJCIGHltag0001101111sibling54-1-1-187-19-1評分要點(diǎn)：錯(cuò)一處扣1分，扣完為止6.已知一個(gè)有序森林如下所示，它的中序遍歷序列為_______________________。

F,H,C,B,G,E,A,D7.已知一個(gè)有序森林如下所示，它的先序遍歷序列為_______________________。

D,B,H,C,E,A,F,G8.已知一棵二叉樹如下所示，請畫出這棵二叉樹對應(yīng)的有序森林。

評分要點(diǎn)：錯(cuò)一處扣2分，扣完為止第5章作業(yè)（二叉樹的遍歷）1.已知一棵二叉樹結(jié)點(diǎn)的后遍歷序列為：A,C,B,D,F,E,中序遍歷序列為C,A,E,F,B,D,請畫出該二叉樹。

評分要點(diǎn)：錯(cuò)一處扣5分，扣完為止2.已知一棵二叉樹結(jié)點(diǎn)的先序遍歷序列為：F,D,E,B,C,A,中序遍歷序列為D,B,E,F,A,C,請畫出該二叉樹。

評分要點(diǎn)：錯(cuò)一處扣5分，扣完為止3.設(shè)二叉樹以二叉鏈表方式存儲(chǔ)，試完成下列問題的遞歸算法。設(shè)二叉樹結(jié)點(diǎn)和二叉樹結(jié)構(gòu)體定義如下：typedefstructbtnode{ElemTypeelemen