國(guó)家開放大學(xué)(中央廣播電視大學(xué))2015年秋季學(xué)期“開放本科”期末考試數(shù)據(jù)結(jié)構(gòu)(本)試題2016年1月一、單項(xiàng)選擇題(每小題2分，共30分)1.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，可采用三元組表，一個(gè)有10行的稀疏矩陣A共有97個(gè)零元素，其相應(yīng)的三元組表共有3個(gè)元素。該矩陣A有()列。A.8C.7B.9D.10答案：102.子串“acd”在主串“abdcacdefac”中的位置是()。A.3C.7B.5D.1答案：53.序列12，16，8，4按順序依次進(jìn)棧，按該棧的可能輸出序列依次入隊(duì)列，該隊(duì)列的不可能輸出序列是()。(進(jìn)棧、出?？梢越惶孢M(jìn)行)。A.16，12，8，4B.4，8，12，16C.8，4，16，12D.16，12，4，8答案：B.4，8，12，164.在一個(gè)不帶頭結(jié)點(diǎn)的鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，對(duì)該隊(duì)列進(jìn)行出隊(duì)操作，并把結(jié)點(diǎn)的值保存在變量e中，其運(yùn)算為()。A.e=f->data；r=r->nextB.e=f->data；r->next=rC.e=f->data；f=f->nextD.e=f一>data；f一>next=f答案：C.e=f->data；f=f->next

5.數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)內(nèi)存中的表示是()。A.給相關(guān)變量分配存儲(chǔ)單元C.數(shù)據(jù)的邏輯結(jié)構(gòu)B.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)D.算法的具體體現(xiàn)答案：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)6.以下說法正確的是()。A.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)必須占用連續(xù)的存儲(chǔ)空間B.一種邏輯結(jié)構(gòu)可以有不同的存儲(chǔ)結(jié)構(gòu)C.一種邏輯結(jié)構(gòu)只能有唯一的存儲(chǔ)結(jié)構(gòu)D.線性表的順序存儲(chǔ)結(jié)構(gòu)不必占用連續(xù)的存儲(chǔ)空間答案：一種邏輯結(jié)構(gòu)可以有不同的存儲(chǔ)結(jié)構(gòu)7.在一個(gè)單鏈表中要?jiǎng)h除p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)，可執(zhí)行q=p一>next；和()。A.p一>next=q->nextB.p=q->nextC.p->next=qD.p->next=q答案：A.p一>next=q->next8.在數(shù)據(jù)結(jié)構(gòu)和算法中，與所使用的計(jì)算機(jī)有關(guān)的是()。A.數(shù)據(jù)元數(shù)間的抽象關(guān)系C.算法的時(shí)間復(fù)雜度B.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)D.數(shù)據(jù)的邏輯結(jié)構(gòu)答案：數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)9.以下表中可以隨機(jī)訪問的是()。A.單向鏈表B.雙向鏈表C.單向循環(huán)鏈表D.順序表答案：順序表10.頭指針為head的不帶頭結(jié)點(diǎn)的單向鏈表為空的判定條件是邏輯表達(dá)式()為真。A.head==NULLB.head->next==NULLC.head->next=NULLD.head一>next!=NULL答案：head==NULL11.設(shè)有一個(gè)長(zhǎng)度為32的順序表，要在第5個(gè)元素之前插入1個(gè)元素(也就是插入元素作為新表的第5個(gè)元素)，需移動(dòng)元素個(gè)數(shù)為()。A.25C.5B.28D.6答案：2812.設(shè)有一個(gè)長(zhǎng)度為33的順序表，要?jiǎng)h除第10個(gè)元素(下標(biāo)從1開始)需移動(dòng)元素的個(gè)數(shù)為()。A.11B.10C.23D.14答案：2313.設(shè)有一個(gè)28階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中(數(shù)組下標(biāo)從1開始)，則數(shù)組中第26號(hào)元素對(duì)應(yīng)于矩陣中的元素是()。A.a7，5C.a6，5B.a7，6D.a7，4答案：a7，514.在一個(gè)不帶頭結(jié)點(diǎn)的單循環(huán)鏈表中，p、q分別指向表中第一個(gè)結(jié)點(diǎn)和尾結(jié)點(diǎn)，現(xiàn)要?jiǎng)h除第一個(gè)結(jié)點(diǎn)，且p、q仍然分別指向新表中第一個(gè)結(jié)點(diǎn)和尾結(jié)點(diǎn)?？捎玫恼Z句是p=p一>next；和()。A.p=q->nextB.p->next=qC.q=pD.q一>next=p答案：q一>next=p15.在一棵二叉樹中，若編號(hào)為16的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的左孩子，則他的雙親結(jié)點(diǎn)的順序編號(hào)為()。A.7B.8C.32D.33答案：8二、填空題(每小題2分，共24分)16.數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為（物理存儲(chǔ)）結(jié)構(gòu)。17.四類基本結(jié)構(gòu)分別為（集合、線性、樹形、圖狀）結(jié)構(gòu)。18.隊(duì)列的操作特點(diǎn)是先進(jìn)（先出）。19.廣義表((b，a，c)，c，d，(e，i，j，k))的表尾是（(c，d，(e，i，j，k))）。20.設(shè)有一個(gè)長(zhǎng)度為20的順序表，第8號(hào)元素到第20號(hào)元素依次存放的值為8，9，…，20。某人想要在第8號(hào)元素前插入1個(gè)元素7(也就是插入元素作為新表的第8個(gè)元素)，程序中他的做法是用語句for(i=8；i<=20；i++)a[i+1]=a[i]；a[8]=7；即從第8號(hào)元素開始，直到第20號(hào)元素，每個(gè)元素依次向后(右)移動(dòng)1個(gè)位置，然后把7存放在第8號(hào)位置。事實(shí)上這樣做是錯(cuò)誤的.其結(jié)果是新表中第20號(hào)元素的值為（8）。21.設(shè)有一棵有38個(gè)結(jié)點(diǎn)的完全二叉樹，該樹共有（6）層。(根所在結(jié)點(diǎn)為第1層)22.一棵有18個(gè)結(jié)點(diǎn)的二叉樹，其2度結(jié)點(diǎn)數(shù)的個(gè)數(shù)為8，則該樹共有（1）個(gè)1度結(jié)點(diǎn)。23.對(duì)一組記錄(1，3，9，2，12，7，5，4，6)進(jìn)行直接插人排序(由小到大排序)，當(dāng)把第6個(gè)記錄7插人有序表，為尋找插人位置需比較（3）次。24.序列5，3，8，4，7，6，采用冒泡排序算法，經(jīng)一趟冒泡后，序列的結(jié)果是（3，5，4，7，6，8）。(按升序排序)25.廣義表(b，a，(c，b)，f，e，((i，j)，k))的長(zhǎng)度是（6）。26.一棵有18個(gè)葉結(jié)點(diǎn)的哈夫曼樹，則該樹共有（17）個(gè)非葉結(jié)點(diǎn)。27.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，可采用三元組表，一個(gè)8行7列的稀疏矩陣A共有51個(gè)零元素，其相應(yīng)的三元組表共有（5）個(gè)元素。

三、問答和綜合題(每小題10分，共30分)28.設(shè)數(shù)據(jù)集合a={6，17，10，13，8，15，12，18，14}(1)依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。(2)給出對(duì)該二叉樹中序遍歷的序列。(3)對(duì)該二叉樹進(jìn)行查找，成功查找到14要進(jìn)行多少次元素間的比較?29.設(shè)有序表為(2，5，11，12，30，48，58)，元素的序號(hào)依次為1，2，3，…7.(1)畫出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(樹中結(jié)點(diǎn)用序號(hào)表示)。(2)說明成功查找到元素11需要經(jīng)過多少次比較?(3)在等概率條件下，給出成功查找的平均查找長(zhǎng)度?30.(1)如圖1所示，若從頂點(diǎn)a出發(fā)，首先經(jīng)過頂點(diǎn)c按廣度優(yōu)先搜索法進(jìn)行遍歷，給出可能得到的一種頂點(diǎn)序列。(2)如圖1所示，給出從頂點(diǎn)h出發(fā)，首先經(jīng)過頂點(diǎn)d和e按深度優(yōu)先搜索法進(jìn)行遍歷，給出可能得到的一種頂點(diǎn)序列。(3)一組記錄的關(guān)鍵字序列為(80，57，41，39，46，47)，利用堆排序的方法的方法建立小根堆(堆頂元素是最小元素)，給出按篩選法建立的的初始堆。

四、程序填空題(每空2分，共16分)31.以下冒泡法程序?qū)Υ娣旁赼[1]，a[2]，……，a[n]中的序列進(jìn)行冒泡排序，完成程序中的空格部分，其中n是元素個(gè)數(shù)，程序按升序排列。voidbsort(NODEal，int){ NODEtemp；inti，j，flag；for(j=1；j<=n一1；①j++{ flag=0；for(i=1；②i<=n一j；i十十)if(a[i].key>a[i+1].key){ flag==1；③temp=a[i]；a[i]=ali+1]；④a[i+1]=temp； }if(flag==0)break； }}程序中flag的功能是⑤判斷某一趟排序中是否有元素交換32.以下函數(shù)為鏈棧的出棧操作，出棧結(jié)點(diǎn)的數(shù)據(jù)由x返回structnode{ ElemTypedata；structnode*next；}；ElemTypePop(){ intx；if(top==①NULL){printf("棧下溢錯(cuò)誤!\n")；exit(1)； }X=top→data;top=top-next;returnx；}四、程序填空題(每空2分，共16分)31.(10分)(1)(2)(3)(4)(5)32.(6分)(1)(2)(3)國(guó)家開放大學(xué)(中央廣播電視大學(xué))2016年春季學(xué)期“開放本科”期末考試數(shù)據(jù)結(jié)構(gòu)(本)試題2016年7月一、單項(xiàng)選擇題(每小題2分，共30分)1.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，可采用三元組表，一個(gè)10行8列的稀疏矩陣A共有73個(gè)零元素，其相應(yīng)的三元組表共有()個(gè)元素。A.8B.80C.7D.10參考答案：72.字符串()是“abcd321ABCD”的子串。A.“21AB”B.“abcD”C.“aBCD”D.“321a”參考答案：“21AB”3.棧和隊(duì)列的共同特點(diǎn)是()。A.都是操作受限的線性結(jié)構(gòu)C.都是先進(jìn)后出B.元素都可以隨機(jī)進(jìn)出D.都是先進(jìn)先出參考答案：都是操作受限的線性結(jié)構(gòu)4.在一個(gè)鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，p指向一個(gè)新結(jié)點(diǎn)，要為結(jié)點(diǎn)p所指結(jié)點(diǎn)賦值x，并人隊(duì)的運(yùn)算為p->data=x；p->next=NULL；().A.f一>next=p；f=p；B.r一>next=p；r=p；C.r=p；p->next=r；D.p->next=f；f=p；參考答案：r一>next=p；r=p；5.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的()結(jié)構(gòu)。A.邏輯B.存儲(chǔ)C.邏輯與存儲(chǔ)D.物理參考答案：邏輯6.順序表所具備的特點(diǎn)之一是()。A.可以隨機(jī)訪問任一結(jié)點(diǎn)B.不需要占用連續(xù)的存儲(chǔ)空間C.插人元素的操作不需要移動(dòng)元素D.刪除元素的操作不需要移動(dòng)元素參考答案：可以隨機(jī)訪問任一結(jié)點(diǎn)7.數(shù)據(jù)元素是數(shù)據(jù)的基本單位，它()。A.只能有一個(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)為指針類型參考答案：可以是一個(gè)數(shù)據(jù)項(xiàng)也可以由若干個(gè)數(shù)據(jù)項(xiàng)組成8.設(shè)有頭指針為head的非空的單向鏈表，指針p指向其尾結(jié)點(diǎn)，要使該單向鏈表成為單向循環(huán)鏈表，則可利用下述語句()。A.p=head；B.p=NULL；C.p->next=head；D.head=p；參考答案：p->next=head；9.在線性表的順序結(jié)構(gòu)中，以下說法正確的是()。A.邏輯上相鄰的元素在物理位置上不一定相鄰B.數(shù)據(jù)元素是不能隨機(jī)訪問的C.邏輯上相鄰的元素在物理位置上也相鄰D.進(jìn)行數(shù)據(jù)元素的插人、刪除效率較高參考答案：邏輯上相鄰的元素在物理位置上也相鄰10.對(duì)鏈表，以下敘述中正確的是()。A.不能隨機(jī)訪問任一結(jié)點(diǎn)B.結(jié)點(diǎn)占用的存儲(chǔ)空間是連續(xù)的C.插人刪除元素的操作一定要要移動(dòng)結(jié)點(diǎn)D.可以通過下標(biāo)對(duì)鏈表進(jìn)行直接訪問參考答案：不能隨機(jī)訪問任一結(jié)點(diǎn)11.設(shè)有一個(gè)長(zhǎng)度為35的順序表，要在第5個(gè)元素之前插入1個(gè)元素(也就是插入元素作為新表的第5個(gè)元素)，則移動(dòng)元素個(gè)數(shù)為()。A.30C.5B.31D.6參考答案：3112.設(shè)有一個(gè)長(zhǎng)度為40的順序表，要?jiǎng)h除第10個(gè)元素(下標(biāo)從1開始)需移動(dòng)元素的個(gè)數(shù)為()。A.11B.10C.30D.31參考答案：3013.設(shè)有一個(gè)25階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中(數(shù)組下標(biāo)從1開始)，則矩陣中元素ar，s在一維數(shù)組B中的下標(biāo)是().A.25B.24C.26D.27參考答案：2614.線性表在存儲(chǔ)后，如果相關(guān)操作中有要求：利用已知的指向某結(jié)點(diǎn)的指針或序號(hào)，訪問該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則采用()的存儲(chǔ)方式是不可行的。A.單向鏈表B.雙向鏈表C.單向循環(huán)鏈表D.順序表參考答案：?jiǎn)蜗蜴湵?5.在一棵二叉樹中，若編號(hào)為i的結(jié)點(diǎn)存在左孩子，i結(jié)點(diǎn)的左孩子的順序編號(hào)為()。A.i/2.0B.2*iC.2*i+1D.i十2參考答案：2*i二、填空題(每小題2分，共24分)16.廣義表((b，a，c)，c，d，f，e，((i，j)，k))的長(zhǎng)度是____________.參考答案：617.數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)元素之間的抽象關(guān)系稱為____________結(jié)構(gòu)。參考答案：邏輯18.棧的操作特點(diǎn)是后進(jìn)______________.參考答案：先出19.廣義表((b，a，c)，c，d，f，e，((i，j)，k))的表頭是________________.參考答案：(b，a，c)20.設(shè)有一個(gè)長(zhǎng)度為18的順序表，第8號(hào)元素到第18號(hào)元素依次存放的值為8，9，…，18.某人想要?jiǎng)h除第8號(hào)元素，程序中他的做法是用語句for(i=18；i<=9；i--)a[i-1]=a[i]；即從第18號(hào)元素開始，直到第9號(hào)元素，每個(gè)元素依次向前(左)移動(dòng)1個(gè)位置，事實(shí)上這樣做是錯(cuò)誤的，其結(jié)果新表中第9號(hào)元素的值為_________________________.參考答案：1821.一棵二叉樹，有1個(gè)2度結(jié)點(diǎn)，2個(gè)1度結(jié)點(diǎn)，則該樹共有________個(gè)結(jié)點(diǎn)。參考答案：522.設(shè)有一棵深度為5的完全二叉樹，該樹共有21個(gè)結(jié)點(diǎn)，第5層上有_____個(gè)結(jié)點(diǎn)。(根所在結(jié)點(diǎn)為第1層)參考答案：623.中序遍歷______________樹可得到一個(gè)有序序列。參考答案：二叉排序樹24.序列12，10，13，11，16，14，采用冒泡排序算法，經(jīng)一趟冒泡后，序列的結(jié)果是_____________________.(按升序排序)參考答案：10，12，11，13，14，1625.對(duì)16個(gè)元素的序列用冒泡排序法進(jìn)行排序，共需要進(jìn)行________趟冒泡。參考答案：1526.一棵有16個(gè)葉結(jié)點(diǎn)的哈夫曼樹，則該樹共有_________個(gè)非葉結(jié)點(diǎn)。參考答案：1527.在對(duì)一組記錄(40，24，82，9，1，78，46，31，69)進(jìn)行直接插人排序(由小到大排序)，當(dāng)把第7個(gè)記錄46插人到有序表時(shí)，為尋找插人位置需比較__次。參考答案：3三、問答和綜合題(每小題10分，共30分)28.設(shè)有序表為(5，8，14，15，33，51，61，73，81，82，93)，元素的序號(hào)依次為1，2，3，……，11.(1)畫出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(樹中結(jié)點(diǎn)可用序號(hào)表示)(2)說明成功查找到元素33需要經(jīng)過多少次比較?(3)在等概率條件下，給出成功查找的平均查找長(zhǎng)度?參考答案：29.(1)如圖1所示，若從頂點(diǎn)a出發(fā)，首先經(jīng)過c按圖的深度優(yōu)先搜索法進(jìn)行遍歷，給出可能得到的一種頂點(diǎn)序列。(2)設(shè)有向圖如圖2所示下，寫出首先刪除頂點(diǎn)1的1種拓?fù)湫蛄?。參考答案?0.(1)設(shè)數(shù)據(jù)集合a={7，4，9，8，6，5，3}，依次取a中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹。(2)對(duì)該二叉樹進(jìn)行查找，成功查找到5要進(jìn)行多少次元素間的比較?(3)給出對(duì)上述二叉排序樹進(jìn)行中序遍歷的序列參考答案：四、程序填空題(每空2分，共16分)31.以下函數(shù)在a[0]到a[n-1]中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo)，失敗時(shí)返回一1，完成程序中的空格typedefstruct{ intkey；…}NODE；intBinary_Search(NODEa[]，intn，intk){ intlow，mid，high；low=0；high=n一1；while①_________________{ mid=(low+high)/2；if(a[mid].key==k)return②________________;elseif③____________________low=mid+1；else④________________; } ⑤__________________;}參考答案：(1)low<=high(2)mid(3)a[mid].key<k(4)high=mid一1(5)return-132.以下函數(shù)為鏈棧的進(jìn)棧操作，x是要進(jìn)棧的結(jié)點(diǎn)的數(shù)據(jù)域，top為棧頂指針。structnode{ ElemTypedata；structnode*next；}；structnode*top；voidPush(ElemTypex){ structnode*p；p=(structnode*)malloc①______________;p->data=x；②___________________;③___________________;}參考答案：(1)sizeof(structnode)(2)p->next=top(3)top=p國(guó)家開放大學(xué)(中央廣播電視大學(xué))2017年春季學(xué)期“開放本科”期末考試數(shù)據(jù)結(jié)構(gòu)(本)試題2017年6月一、單項(xiàng)選擇題(每小題3分，共30分)1.設(shè)有一個(gè)長(zhǎng)度為26的順序表，要插人一個(gè)元素，并使它成為新表的第6個(gè)元素，需移動(dòng)元素的個(gè)數(shù)為()。A.21B.22C.20D.19參考答案：212.頭指針為head的帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，p指向尾結(jié)點(diǎn)，要使該鏈表成為不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，可執(zhí)行head=head->next；和()。A.p=head->nextB.head->next=pC.head->next=p->nextD.p->next=head；參考答案：p->next=head；3.元素111，113，115，117按順序依次進(jìn)棧，則該棧的不可能輸出序列是()(進(jìn)棧出?？梢越惶孢M(jìn)行)。A.117，115，113，111B.111，113，115.117C.117，115，111，113D.113，111，117，115參考答案：117，115，111，1134.設(shè)有一個(gè)20階的對(duì)稱矩陣A(第一個(gè)元素為a1.1)，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中(數(shù)組下標(biāo)從1開始)，則矩陣元素a6.2在一維數(shù)組B中的下標(biāo)是()。A.21B.17C.28D.23參考答案：17

5.設(shè)有串pl=”ABADF”，P2=”ABAFD”，P3=”ABADFA”，P4=”ABAF”，以下四個(gè)串中最大的是()。A.p3C.plB.p2D.p4參考答案：p26.在一棵二叉樹中，若編號(hào)為i的結(jié)點(diǎn)存在左孩子，則左孩子的順序編號(hào)為().A.2i+1C.2iB.2i-1D.2i+2參考答案：2i7.如圖1所示，若從頂點(diǎn)a出發(fā)，按圖的廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為().A.abecdfB.aecbdfC.aebcfdD.aedfcb參考答案：aecbdf8.線性表以()方式存儲(chǔ)，能進(jìn)行折半查找。A.鏈接B.順序C.關(guān)鍵字有序的順序D.二叉樹參考答案：關(guān)鍵字有序的順序9.一棵具有38個(gè)結(jié)點(diǎn)的完全二叉樹，最后一層有()個(gè)結(jié)點(diǎn)。A.7C.6B.5D.8參考答案：710.下圖的拓?fù)湫蛄惺?A.52346B.23645C.56234D.23564參考答案：56234二、填空題(每小題2分，共24分)11.結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為____________結(jié)構(gòu)。參考答案：圖狀12.n個(gè)元素進(jìn)行冒泡法排序，第j趟冒泡要進(jìn)行__________次元素間的比較。參考答案：n-j13.中序遍歷__________樹可得到一個(gè)有序序列。參考答案：二叉排序樹14.待排序的序列為8，3，4，1，2，5，9，采用直接選擇排序算法，當(dāng)進(jìn)行了兩趟選擇后：結(jié)果序列為____________________.參考答案：1，2，4，8，3，5，915.廣義表((a，b)，d，e，((i，j)，k))的長(zhǎng)度是__________.參考答案：416.廣義表的(c，a，(a，b)，d，e，((i，j)，k))深度是__________.參考答案：317.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，可采用三元組表，一個(gè)有10行10列的稀疏矩陣A共有95個(gè)零元素，其相應(yīng)的三元組表共有__________個(gè)元素。參考答案：518.在對(duì)一組記錄(50，49，97，22，16，73，65，47，88)進(jìn)行直接插人排序時(shí)，當(dāng)把第7個(gè)記錄65插人到有序表時(shí)，為尋找插人位置需比較__________次。參考答案：319.一棵有5個(gè)葉結(jié)點(diǎn)的哈夫曼樹，該樹中總共有________個(gè)結(jié)點(diǎn)。參考答案：920.設(shè)有一棵深度為4的完全二叉樹，第四層上有5個(gè)結(jié)點(diǎn)，該樹共有_________個(gè)結(jié)點(diǎn)。(根所在結(jié)點(diǎn)為第1層)。參考答案：1221.設(shè)有一個(gè)長(zhǎng)度為40的順序表，要?jiǎng)h除第8個(gè)元素需移動(dòng)元素的個(gè)數(shù)為____.參考答案：3222.有以下程序段chara[]="English”；char*p=a；intn=0；while(*p!=‘\0’){n++；p++；)結(jié)果中，n的值是________.參考答案：7三、綜合題(每小題中每問5分，共30分)23.有一個(gè)長(zhǎng)度為11的有序表(1，2，11，15，24，28，30，56，69，70，80)，元素的下標(biāo)依次為1，2，3，……，11，按折半查找對(duì)該表進(jìn)行查找。(1)畫出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹。(2)說出成功查找到元素56，需要依次經(jīng)過與哪些元素的比較?(3)說出不成功查找元素72，需要進(jìn)行元素比較的次數(shù)?參考答案：24.(1)一組記錄的關(guān)鍵字序列為(57.90，67，50，51，56)，利用堆排序(堆頂元素是最小元素)的方法建立初始堆(要求以完全二叉樹描述)。(2)對(duì)關(guān)鍵字序列(56.51，71，54，46，106)利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，給出經(jīng)過一次劃分后的結(jié)果。(3)一組記錄的關(guān)鍵字序列為(60，47，80，57，39，41，46，30)，利用歸并排序的方法，分別給出(1，1)歸并、(2，2)歸并、(4，4)歸并的結(jié)果序列。參考答案：四、程序填空題(每空2分，共16分)25.設(shè)線性表為(16，20，26，24)，以不帶頭結(jié)點(diǎn)的單向鏈表存儲(chǔ)，鏈表頭指針為head，以下程序的功能是輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)域data。Structnode{ intdata；structnode*next；}；typedefstructnodeNODE；#defineNULLOvoidmain(){ NODE*head，*p；p=head；/*p為工作指針*/ do{ printf(“%d\n”，(1)_______________)；(2)______________________;}while((3)______________________)}參考答案：(1)p->data(2)p=p->next(3)p!=NULL26.以下函數(shù)為直接選擇排序算法，對(duì)a[1]，a[2]，…a[n]中的記錄進(jìn)行直接選擇排序，完成程序中的空格typedefstruct{ intkey;…}NODE；voidselsort(NODEa[]，intn){inti，j，k；NODEtemp；for(i=l；i<=(1)_____________；i十十){ k=i； for(j=i+1；j<=(2)______________；j十十) if(a[j].key<a[k].key)(3)___________________; if(i!=k){ temp=a[i]； (4)__________________________; (5)_____________________________;} }}參考答案：(1)n-1(2)n(3)k=j(4)a[i]=a[k](5)a[k]=temp國(guó)家開放大學(xué)(中央廣播電視大學(xué))2017年秋季學(xué)期“開放本科”期末考試數(shù)據(jù)結(jié)構(gòu)(本)試題2018年1月一、單項(xiàng)選擇題(每小題3分，共30分)1.設(shè)有頭指針為head的帶有頭結(jié)點(diǎn)的非空單向循環(huán)鏈表，指針p指向其尾結(jié)點(diǎn)，要?jiǎng)h除頭結(jié)點(diǎn)，并使其仍為單向循環(huán)鏈表，則可利用下述語句head==head一>next；()。A.p=head；B.p=NULL；C.p一>next=head；D.head=p；參考答案：p一>next=head；2.以下說法不正確的是()。A.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不必占用連續(xù)的存儲(chǔ)空間B.一種邏輯結(jié)構(gòu)只能有唯一的存儲(chǔ)結(jié)構(gòu)C.一種邏輯結(jié)構(gòu)可以有不同的存儲(chǔ)結(jié)構(gòu)D.線性表的順序存儲(chǔ)結(jié)構(gòu)必須占用連續(xù)的存儲(chǔ)空間參考答案：一種邏輯結(jié)構(gòu)只能有唯一的存儲(chǔ)結(jié)構(gòu)3.把數(shù)據(jù)存儲(chǔ)到計(jì)算機(jī)中，并具體體現(xiàn)()稱為物理結(jié)構(gòu)。A.數(shù)據(jù)元素間的邏輯關(guān)系B.數(shù)據(jù)的處理方法C.數(shù)據(jù)的性質(zhì)D.數(shù)據(jù)的運(yùn)算參考答案：數(shù)據(jù)元素間的邏輯關(guān)系4.鏈表所具備的特點(diǎn)之一是()。A.可以隨機(jī)訪問任一結(jié)點(diǎn)B.需要占用連續(xù)的存儲(chǔ)空間C.插人元素的操作不需要移動(dòng)元素D.刪除元素的操作需要移動(dòng)元素參考答案：插人元素的操作不需要移動(dòng)元素5.圖狀結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在()的關(guān)系。A.一對(duì)一B.多對(duì)多C.一對(duì)多D.每一個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼參考答案：多對(duì)多6.元素15，9，11，13按順序依次進(jìn)棧，則該棧的不可能輸出序列是()(進(jìn)棧出棧可以交替進(jìn)行)。A.13，11，9，15C.13，11，15，9B.15，9，11，13D.9，15，13，11參考答案：13，11，15，97.設(shè)有一個(gè)14階的對(duì)稱矩陣A(第一個(gè)元素為a1，1)，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中(數(shù)組下標(biāo)從1開始)，則矩陣中元素a4.3在一維數(shù)組B中的下標(biāo)是()。A.9B.10C.11D.8參考答案：98.在一棵二叉樹中，若編號(hào)為8的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為()。A.18B.16C.15D.17參考答案：179.設(shè)一棵哈夫曼樹共有14個(gè)非葉結(jié)點(diǎn)，則該樹總共有()個(gè)結(jié)點(diǎn)。A.29C.30B.27D.28參考答案：29

10.如圖1所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為().A.abecdfC.aebcfdB.acfebdD.aedbfc參考答案：aedbfc二、填空題(每小題2分，共24分)11.隊(duì)列的特點(diǎn)之一是：元素進(jìn)、出隊(duì)的次序是：先進(jìn)_________。參考答案：先出12._________________結(jié)構(gòu)中，數(shù)據(jù)元素間存在一對(duì)多的關(guān)系。參考答案：樹形13.對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ)，矩陣中每個(gè)非零元素對(duì)應(yīng)的三元組包括該元素的三項(xiàng)信息是______________。參考答案：行下標(biāo)、列下標(biāo)、數(shù)組元素14.在對(duì)11個(gè)記錄的序列(12，35，9，7，2，11，56，95，37，58，60)進(jìn)行直接插入排序時(shí)，當(dāng)把第6個(gè)記錄11插入到有序表時(shí)，為尋找插入位置，元素間需比較____________次。(由小到大排列)參考答案：315.哈希函數(shù)是記錄關(guān)鍵字的值與該記錄____________之間所構(gòu)造的對(duì)應(yīng)關(guān)系。參考答案：存儲(chǔ)位置16.20個(gè)元素進(jìn)行冒泡法排序，通常需要進(jìn)行19趟冒泡，其中第10趟冒泡共需要進(jìn)行____________次元素間的比較。參考答案：1017.一棵有19個(gè)結(jié)點(diǎn)的二叉樹，采用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)，該樹結(jié)構(gòu)中有__________個(gè)指針域?yàn)榭?。參考答案?018.中序遍歷一棵____________樹可得到一個(gè)有序序列。參考答案：二叉排序樹19.二叉排序樹插人操作中，新插人的結(jié)點(diǎn)總是以樹的____________結(jié)點(diǎn)被插人的。參考答案：葉20.廣義表的(a，(d，a，b)，h，(e，((i，j)，k)))深度是____________。參考答案：421.序列4，2，5，3，8，6，7，9，采用歸并排序算法(升序)，經(jīng)一趟歸并后，序列的結(jié)果：___________。參考答案：2，4，3，5，6，8，7，922.字符串a(chǎn)l=“teijing”，a2=“tef”，a3=“teifang”，a4=“tefi”最小的是_______。參考答案：a2三、綜合題(每小題中每問6分，共30分)23.設(shè)查找表為(1)畫出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(樹中結(jié)點(diǎn)用下標(biāo)表示)。(2)說明成功查找到元素86需要經(jīng)過多少次比較?(3)求在等概率條件下，成功查找的平均比較次數(shù)?參考答案：24.(1)一組記錄的關(guān)鍵字序列為(26，59，36，18，20，25)，給出利用堆排序(堆頂元素是最小元素)的方法建立的初始堆(要求以完全二叉樹描述)。(2)對(duì)關(guān)鍵字序列(26，59，36，18，20，64)采用快速排序，給出以第一個(gè)關(guān)鍵字為分割元素，經(jīng)過一次劃分后的結(jié)果。參考答案：四、程序填空題(每空2分，共16分)25.以下函數(shù)在a[0]到a[n-1]中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo)，失敗時(shí)返回一1，完成程序中的空格typedefstruct{ intkey；……}NODE；intBinary_Search(NODEa[]，intn，intk){intlow，mid，high；low=＝0；high=n一1；while((1)_____________){ mid=((2)_______________)if(a[mid].key==k)return(3)___________________; elseif((4)____________________) low=mid+1；else(5)_____________________; } Return-1}參考答案：(1)low<=high(2)(low+high)/2(3)mid；(4)a[mid].key<k(5)high=mid-1；26.以下程序是前序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分(樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn))。voidInorder(structBTreeNode*BT){ if(BT!=NULL){ (1)_________________; (2)__________________; Inorder(BT一一>right)；}利用上述程序?qū)D2進(jìn)行先序遍歷，結(jié)果是(3)_______________________.參考答案：(1)printf(“%c”，BT一>data)(2)Inorder(BT->left)(3)abdfec國(guó)家開放大學(xué)(中央廣播電視大學(xué))2018年春季學(xué)期“開放本科”期末考試數(shù)據(jù)結(jié)構(gòu)(本)試題2018年7月一、單項(xiàng)選擇題(每小題3分，共30分)1.數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括數(shù)據(jù)元素的表示和()。A.數(shù)據(jù)處理的方法B.相關(guān)算法C.數(shù)據(jù)元素的類型D.數(shù)據(jù)元素間的關(guān)系的表示參考答案：數(shù)據(jù)元素間的關(guān)系的表示2.在一個(gè)頭指針為head的單向鏈表中，p指向尾結(jié)點(diǎn)，要使該鏈表成為單向循環(huán)鏈表可執(zhí)行()。A.p=head->next；B.head->next=p；C.head一>next=p->next；D.p一>next=head；參考答案：p一>next=head；3.元素111，113，115，117按順序依次進(jìn)棧，則該棧的不可能輸出序列是()(進(jìn)棧出?？梢越惶孢M(jìn)行)。A.117，115，113，111B.111，113，115，117C.117，115，111，113D.113，111，117，115參考答案：117，115，111，1134.以下說法正確的是()。A.棧的特點(diǎn)是先進(jìn)后出C.隊(duì)列的特點(diǎn)是先進(jìn)后出B.棧的特點(diǎn)是先進(jìn)先出D.棧和隊(duì)列的特點(diǎn)都是先進(jìn)后出參考答案：棧的特點(diǎn)是先進(jìn)后出5.設(shè)有一個(gè)20階的對(duì)稱矩陣A(第一個(gè)元素為a1.1)，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中(數(shù)組下標(biāo)從1開始)，則矩陣中元素a6.2在一維數(shù)組B中的下標(biāo)是()。A.24C.16B.17D.23參考答案：176.設(shè)一棵有2n+1個(gè)結(jié)點(diǎn)的二叉樹，除葉結(jié)點(diǎn)外每個(gè)結(jié)點(diǎn)度數(shù)都為2，則該樹共有()個(gè)葉結(jié)點(diǎn)。A.nB.n+1C.n+2D.n一1參考答案：n+17.已知如圖1所示的一個(gè)圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為()。A.abecdfC.aebcfdB.aecbdfD.aedfcb參考答案：aecbdf8.線性表以()方式存儲(chǔ)，能進(jìn)行折半查找。A.關(guān)鍵字有序的順序C.鏈接B.順序D.二叉樹參考答案：關(guān)鍵字有序的順序9.一棵具有38個(gè)結(jié)點(diǎn)的完全二叉樹，最后一層有()個(gè)結(jié)點(diǎn)。A.7C.6B.5D.8參考答案：7

10.對(duì)一個(gè)棧頂指針為top的鏈棧進(jìn)行出棧操作，用變量e保存棧頂元素的值，則執(zhí)行()。A.e=top一>next；top->data=e；B.top=top->next；e=top->data；C.e=top一>data；top=top一>next；D.top=top一>next；e=data；參考答案：e=top一>data；top=top一>next；二、填空題(每小題2分，共24分)11.數(shù)組a經(jīng)初始化chara[]="English”；a[7]中存放的是_______。參考答案：字符串結(jié)束符12.設(shè)有串pl=”ABADF”，P2=”ABAFD”，P3=”ABADFA”P4=”ABAF”，四個(gè)串中最大的是______。參考答案：P213.在一棵二叉樹中，若編號(hào)為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為______。參考答案：2i+114.設(shè)有一個(gè)長(zhǎng)度為20的順序表，要插入一個(gè)元素，并作為第8個(gè)元素，需移動(dòng)元素的個(gè)數(shù)為______。參考答案：1315.結(jié)構(gòu)中的數(shù)據(jù)元素存在多對(duì)多的關(guān)系稱為______結(jié)構(gòu)。參考答案：圖狀16.設(shè)有一棵深度為4的完全二叉樹，第四層上有5個(gè)結(jié)點(diǎn)，該樹共有______個(gè)結(jié)點(diǎn)。(根所在結(jié)點(diǎn)為第1層)參考答案：1217.一棵二叉樹中有n個(gè)非葉結(jié)點(diǎn)，每一個(gè)非葉結(jié)點(diǎn)的度數(shù)都為2，則該樹共有______個(gè)葉結(jié)點(diǎn)。參考答案：n+118.在對(duì)一組記錄(55，39，97，22，16，73，65，47，88)進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄65插入到有序表時(shí)，為尋找插入位置需比較______次。(由小到大排序)參考答案：319.n個(gè)元素進(jìn)行冒泡法排序，第j趟冒泡要進(jìn)行______次元素間的比較。參考答案：n-j20.一棵有n個(gè)葉結(jié)點(diǎn)的哈夫曼樹，則該樹共有______個(gè)結(jié)點(diǎn)。參考答案：2n-121.中序遍歷______可得到一個(gè)有序序列。參考答案：二叉排序樹22.廣義表((a，b)，d，e，((i，j)，k))的長(zhǎng)度是______。參考答案：4

三、綜合題(每小題中每問6分，共30分)23.(1)設(shè)有數(shù)據(jù)集合{40，29，7，73，101，4，55，2，81，92，39}，依次取集合中各數(shù)據(jù)構(gòu)造一棵二叉排序樹。(2)一組記錄的關(guān)鍵字序列為(5，8，6，3，4，7)，利用堆排序(堆頂元素是最小元素)的方法建立初始堆。(要求用完全二叉樹表示)24.(1)以2，3，4，7，8，9作為葉結(jié)點(diǎn)的權(quán)，構(gòu)造一棵哈夫曼樹。(2)給出上述哈夫曼樹葉結(jié)點(diǎn)的哈夫曼編碼。(3)一組記錄的關(guān)鍵字序列為(37，70，47，29，31，85)，利用快速排序，以第一個(gè)關(guān)鍵字為分割元素，給出經(jīng)過一次劃分后結(jié)果。(從小到大排序)

四、程序填空題(每空2分，共16分)25.設(shè)線性表為(6，10，16，4)，以下程序用說明結(jié)構(gòu)變量的方法建立單向鏈表，并輸出鏈表中各結(jié)點(diǎn)中的數(shù)據(jù)。#defineNULL0voidmain(){ NODEa，b，c，d，*head，*p；a.data=6；b.data=10；c.data=16；d.data=4；/*d是尾結(jié)點(diǎn)*/head=(1)______________ a.next=&b；b.next=&c；c.next=&d；(2)______________；/*以上結(jié)束建表過程*/p=head；/*p為工作指針，準(zhǔn)備輸出鏈表*/do{ printf(“%d\n”，(3)____________)；(4)______________________; }while((5)_______________)；}參考答案：(1)&a(2)d->>next=NULL(3)p->data(4)p=p->next(5)p!=NULL26.以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分(樹結(jié)構(gòu)中左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn))。voidInorder(structBTreeNode*BT){ if(BT!=NULL){(1)_______________;(2)_______________;Inorder(BT->right)；}}利用上述程序?qū)τ覉D進(jìn)行遍歷，結(jié)果是(3)________________________參考答案：(1)Inorder(BT->left)(2)printf(“%c”，BT一>data)(3)bedafc國(guó)家開放大學(xué)(中央廣播電視大學(xué))2018年秋季學(xué)期“開放本科”期末考試數(shù)據(jù)結(jié)構(gòu)(本)試題2019年1月一、單項(xiàng)選擇題(每小題3分，共30分)1.如下圖所示，若從頂點(diǎn)a出發(fā)，按圖的廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為()。A.acebdfC.aecbdfB.aecbfdD.acefdb參考答案：aecbdf2.結(jié)構(gòu)中的元素之間存在一對(duì)多的關(guān)系是()。A.集合B.線性結(jié)構(gòu)C.樹形結(jié)構(gòu)D.圖狀結(jié)構(gòu)參考答案：樹形結(jié)構(gòu)3.設(shè)有一個(gè)長(zhǎng)度為18的順序表，要在第4個(gè)元素之前插入1個(gè)元素(也就是插入元素作為新表的第4個(gè)元素)，則移動(dòng)元素個(gè)數(shù)為()。A.15C.5B.16D.4參考答案：154.一個(gè)不帶頭結(jié)點(diǎn)的單循環(huán)鏈表，尾指針為rear，在鏈表中插人一個(gè)s所指向的新結(jié)點(diǎn)，并作為新的尾結(jié)點(diǎn)，可執(zhí)行()。A.rear一>next=s；s一>next=rear一>next；rear=s；B.rear一>next=s一>next；rear=s；C.s一>next=rear一>next；rear一>next=s一>next；rear=s；D.s一>next=rear一>next；rear一>next=s；rear=s；參考答案：s一>next=rear一>next；rear一>next=s；rear=s；5.元素a，b，c，d按順序依次進(jìn)棧，則該棧的不可能輸出序列是()(進(jìn)棧出?？梢越惶孢M(jìn)行).A.c，b，a，dC.a，c，b，dB.d，c，b，aD.d，c，a，b參考答案：d，c，a，b6.在一個(gè)棧頂指針為top的鏈棧中進(jìn)行出棧操作，用變量x保存棧頂元素的值，則執(zhí)行()。A.x=top->data；top=top->next；C.top=top一>next；x=top一>data；B.x=top->data；D.top=top->next；x=data；參考答案：x=top->data；top=top->next；7.設(shè)有一個(gè)18階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼鎯?chǔ)到一維數(shù)組B中(數(shù)組下標(biāo)從1開始)，則矩陣中a10.8元素對(duì)應(yīng)于數(shù)組中第()號(hào)元素。(矩陣中的第1個(gè)元素是a1.1)A.51C.52B.53D.54參考答案：538.一棵采用鏈?zhǔn)酱鎯?chǔ)的二叉樹中，共有n個(gè)指針域被有效使用(即指針域?yàn)榉强?。該二叉樹有()個(gè)指針域?yàn)榭铡.n+1C.n--1B.nD.n+2參考答案：n+29.在一棵二叉樹中，若編號(hào)為9的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號(hào)為()。A.18C.15B.16D.19參考答案：1910.設(shè)一棵哈夫曼樹共有15個(gè)非葉結(jié)點(diǎn)，則該樹總共有()個(gè)結(jié)點(diǎn)。A.29C.31B.27D.28參考答案：31二、填空題(每小題2分，共24分)11.在n個(gè)整數(shù)中求最大數(shù)的算法中，其基本操作是_____________.參考答案：元素間的比較12.設(shè)有一個(gè)長(zhǎng)度為20的順序表，要?jiǎng)h除第5個(gè)元素，則最少要移動(dòng)元素的個(gè)數(shù)為_____________.參考答案：1513.在雙向鏈表中，要?jiǎng)h除p所指的結(jié)點(diǎn)，其中所用的一條語句(p->prior)->next=p->next；的功能是：使P所指結(jié)點(diǎn)的直接前驅(qū)的右指針指向_____________.參考答案：P所指結(jié)點(diǎn)的直接后繼14.設(shè)有一個(gè)頭指針為head的單向鏈表，p指向鏈表中的某結(jié)點(diǎn)，若要使該鏈表成為單向循環(huán)鏈表，可用語句while(p->next!=NULL)_____________.和p一>next=head；。參考答案：p=p->next15.在一個(gè)鏈隊(duì)中，設(shè)front和rear分別為隊(duì)頭和隊(duì)尾指針，則s所指結(jié)點(diǎn)(數(shù)據(jù)域已賦值)的人隊(duì)操作為s一>next=NULL；_____________rear=s；。參考答案：rear->next=s；16.字符串a(chǎn)l=“heijing”，a2=“hef”，a3=“heifang”，a4=“hefi”中最小的是_______.參考答案：a217.棧的特點(diǎn)之一是：元素進(jìn)、出棧的次序是：后進(jìn)_____________.參考答案：先出18.在對(duì)10個(gè)記錄的序列(14，30，10，7，22，13，66，85，47，58)進(jìn)行直接插人排序時(shí)，當(dāng)把第6個(gè)記錄13插人到有序表時(shí)，為尋找插人位置，元素間需比較_____________次。(由小到大排列)參考答案：419.18個(gè)元素進(jìn)行冒泡法排序，通常需要進(jìn)行17趟冒泡，其中第10趟冒泡共需要進(jìn)行_____________次元素間的比較。參考答案：820.一棵有15個(gè)結(jié)點(diǎn)的哈夫曼樹，采用鏈?zhǔn)浇Y(jié)構(gòu)存儲(chǔ)，該樹結(jié)構(gòu)中有____________個(gè)葉結(jié)點(diǎn)。參考答案：821.廣義表的(b，(a，b)，d，(c，((e，f)，j)))深度是_____________.參考答案：422.序列4，2，7，9，5，3，8，6采用歸并排序算法(升序)，經(jīng)一趟歸并后，序列的結(jié)果為_____________.參考答案：2，4，7，9，3，5，6，8三、綜合題(每小題6分，共30分)23.(1)已知某二叉樹的后序遍歷序列是febch，給出該二叉樹的根結(jié)點(diǎn)?又該二叉樹的中序遍歷序列是fbehc，分別給出該二叉樹的左、右子樹的結(jié)點(diǎn)?(2)畫出上述二叉樹?若上述二叉樹的各個(gè)結(jié)點(diǎn)的字符分別代表不同的整數(shù)(其中沒有相等的)，并恰好使該樹成為一棵二叉排序樹，試給出h、b、c、f、e的大小關(guān)系。

24.設(shè)查找表為(1，2，3，4，5，6，7，8，9，10，11)(1)畫出對(duì)上述查找表進(jìn)行折半查找所對(duì)應(yīng)的判定樹(樹中結(jié)點(diǎn)用數(shù)值表示)。(2)說明成功查找到元素5，9各需要經(jīng)過多少次元素間的比較?(3)說明查找不到元素4.2，5.5各需要經(jīng)過多少次元素間的比較?四、程序填空題(每空2分，共16分)25.以下程序是折半插人排序的算法設(shè)待排序的記錄序列存放在a[1]，…a[n]中，以a[0]作為輔助工作單元，以下程序是要把a(bǔ)[i]插人到已經(jīng)有序的序列a[1]，…a[i一1]中。voidbinsort(NODEa[]，intn){ intx，i，j，s，k，m；For(i=2；i<=(1)___________；i++){ a0]=a[i]；x=a[i].key；s=1；j=i-1；while(s<=j){ m=(2)_____________; if(x<a[m].key) (3)__________________; else (4)__________________;}for(k=i一1；k>=j+1；k--) (5)______________=a[k]；a[j+1]==a[0]； }}參考答案：(1)n(2)(s+j)/2；(3)j=m一1；(4)s=m+1；(5)a[k+1]26.以下程序是中序遍歷二叉樹的遞歸算法的程序，完成程序中空格部分(樹結(jié)構(gòu)中，左、右指針域分別為left和right，數(shù)據(jù)域data為字符型，BT指向根結(jié)點(diǎn))。voidInorder(structBTreeNode*BT){ aif(BT!=NULL)(1)_____________;(2)_____________;Inorder(BT->right)；}}利用上述程序?qū)τ覉D進(jìn)行遍歷，結(jié)果是(3)_____________________;參考答案：(1)Inorder(BT一>left)(2)printf(“%c”，BT->data)(3)bedfa國(guó)家開放大學(xué)2019年春季學(xué)期期末統(tǒng)一考試數(shù)據(jù)結(jié)構(gòu)(本)試題2019年7月一、單項(xiàng)選擇題(每小題3分，共30分)1.以下說法正確的是()。A.在順序表中可以隨機(jī)訪問任一結(jié)點(diǎn)B.一種邏輯結(jié)構(gòu)在存儲(chǔ)時(shí)只能采用一種存儲(chǔ)結(jié)構(gòu)C.對(duì)鏈表進(jìn)行插入、刪除元素的操作一定要移動(dòng)結(jié)點(diǎn)D.在鏈表中可以隨機(jī)訪問任一結(jié)點(diǎn)參考答案：在順序表中可以隨機(jī)訪問任一結(jié)點(diǎn)2.線性表在存儲(chǔ)后，如果要求：僅通過已知的指向第i個(gè)結(jié)點(diǎn)的指針，進(jìn)行相關(guān)操作，訪問到該結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，則采用()存儲(chǔ)方式是不可行的。A.單鏈表B.雙鏈表C.單循環(huán)鏈表D.順序表參考答案：?jiǎn)捂湵?.棧和隊(duì)列的共同特點(diǎn)是()。A.都是先進(jìn)后出B.元素都可以隨機(jī)進(jìn)出C.只容許在端點(diǎn)處插人和刪除元素D.都是先進(jìn)先出參考答案：只容許在端點(diǎn)處插人和刪除元素4.元素4，6，8，10按順序依次進(jìn)棧，按該棧的可能輸出序列依次人隊(duì)列，該隊(duì)列的可能輸出序列是()(進(jìn)棧出?？梢越惶孢M(jìn)行)。A.10，8，4，6C.8，4，6，10B.10，6，4，8D.10，8，6，4參考答案：10，8，6，4

5.在一個(gè)不帶頭結(jié)點(diǎn)的鏈隊(duì)中，假設(shè)f和r分別為隊(duì)頭和隊(duì)尾指針，從該隊(duì)列中進(jìn)行出隊(duì)操作，并把結(jié)點(diǎn)的值保存在變量x中的操作為()。A.x=r->data；r=r->next；B.r一r一>next；x=r一>data；C.x=f~>data；f=f->next；D.f一f->next；x-f一>data；參考答案：x=f~>data；f=f->next；6.設(shè)有一個(gè)18階的對(duì)稱矩陣A，采用壓縮存儲(chǔ)的方式，將其下三角部分以行序?yàn)橹餍虼娴揭痪S數(shù)組B中(數(shù)組下標(biāo)從1開始)，則矩陣元素ag.2對(duì)應(yīng)于數(shù)組B中第()號(hào)元素。(矩陣中的第1個(gè)元素是a1.1)A.42B.39C.38D.40參考答案：387.一棵采用鏈?zhǔn)酱鎯?chǔ)的二叉樹中，共有n一1個(gè)指針域被有效使用(即指針域?yàn)榉强?。該二叉樹中有()個(gè)指針域?yàn)榭?。A.n+1B.nC.n-1D.n一2參考答案：n+18.設(shè)一棵哈夫曼樹共有n個(gè)非葉結(jié)點(diǎn)，則該樹共有()個(gè)結(jié)點(diǎn)。A.2nB.2n+1C.2n一1D.2n+2參考答案：2n+1

9.如圖所示，若從頂點(diǎn)a出發(fā)，按圖的廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點(diǎn)序列為()。A.ahbedfcC.ahebcdfB.ahcfebdD.ahebcfd參考答案：ahebcdf10.線性表以()方式存儲(chǔ)，能進(jìn)行折半查找。A.關(guān)鍵字有序的鏈接C.關(guān)鍵字有序的順序B.順序D.數(shù)組參考答案：關(guān)鍵字有序的順序二、填空題(每小題2分，共24分)11.n個(gè)元素進(jìn)行冒泡法排序，通常需要進(jìn)行(n-1)趟冒泡。12.在對(duì)一組序列(35，19，77，2，6，53，55，27，26，98)進(jìn)行直接插入排序時(shí)，當(dāng)把第9個(gè)記錄26插入到有序表時(shí)，為尋找插入位置需進(jìn)行(6)次元素間的比較。13.在C語言中，分別存儲(chǔ)“S”和‘s’，各需要占用(兩個(gè)和1個(gè))字節(jié)。14.數(shù)據(jù)的邏輯結(jié)構(gòu)在計(jì)算機(jī)中的表示稱為(存儲(chǔ)結(jié)構(gòu))結(jié)構(gòu)。15.在一棵二叉樹中，若編號(hào)為i的結(jié)點(diǎn)是其雙親結(jié)點(diǎn)的左孩子，則i結(jié)點(diǎn)的雙親結(jié)點(diǎn)的順序編號(hào)為(i/2).16.設(shè)有一個(gè)頭指針為head的單向鏈表，p指向表中某一個(gè)結(jié)點(diǎn)，且有p一>next為NULL，現(xiàn)要把該單向鏈表構(gòu)造成單向循環(huán)鏈表，可通過操作(p一>next=head；).17.從一個(gè)棧頂指針為top的鏈棧中刪除一個(gè)結(jié)點(diǎn)時(shí)，用d保存被刪結(jié)點(diǎn)的值，可執(zhí)行d=top->data；和(top=top->next；).(結(jié)點(diǎn)的指針域?yàn)閚ext，數(shù)據(jù)域?yàn)閐ata)。18.循環(huán)鏈隊(duì)列中，設(shè)front和rear分別為隊(duì)頭和隊(duì)尾指針，(最多元素為MaxSize，采用少用一個(gè)元素的模式)，判斷循環(huán)鏈隊(duì)列為滿的條件為:(front==(rear+1)%MaxSize).19.一棵有7個(gè)權(quán)重值構(gòu)造的哈夫曼樹，共有(13)個(gè)結(jié)點(diǎn)。20.二叉樹中有1個(gè)1度結(jié)點(diǎn)，8個(gè)2度結(jié)點(diǎn)，則該二叉樹樹共有(18)個(gè)結(jié)點(diǎn)。21.如圖所示的二叉樹，其先序遍歷序列為(215934786).22.在查找表中，通過記錄的某關(guān)鍵字能唯一地確定一個(gè)記錄，該關(guān)鍵字稱為(主關(guān)鍵字).三、綜合題(每小題6分共30分)23.(1)對(duì)給定權(quán)值4，2，6，6，7，8，構(gòu)造高度為4層的哈夫曼樹。(設(shè)根為第1層)提示：構(gòu)造中當(dāng)出現(xiàn)有兩個(gè)以上值相等的可選結(jié)點(diǎn)時(shí)，可適當(dāng)選擇結(jié)點(diǎn)組合，以控制樹的高度。(2)求樹的帶權(quán)路徑長(zhǎng)度。(2)WPL=(4+2+6+6)*3十(7+8)*2=8424.如下的一棵二叉樹，(1)請(qǐng)給出前序遍歷序列?請(qǐng)給出中序遍歷序列?(2)把1，2，3，4，5，6，7，8，9填人，使它成為一棵二叉排序樹。提示：設(shè)圖中的樹是二叉排序樹，則中序遍歷序列是有序的，從而找出中序遍歷序列與1，2，…9的對(duì)應(yīng)關(guān)系。(3)在圖中給出在二叉排序樹中插入結(jié)點(diǎn)2.5的結(jié)果。

四、程序填空題(每空2分，共16分)25.以下函數(shù)為直接選擇排序算法，對(duì)a[1]，a[2]，…a[n]中的記錄進(jìn)行直接選擇排序，完成程序中的空格typedefstruct{intkey；…}NODE；voidselsort(NODEa[]，intn){Inti，j，k；NODEtemp；for(i=1；i<=(1)____________；i++) { k-i；for(j=i十1；j<=(2)____________；j++)if(a[j].key<alk].key)(3)______________;if(i!=k){ temp=ai； (4)____________________ (5)_____________________} }}參考答案：(1)n一1(2)n(3)k=j(4)a[i]=a[k](5)a[k]=temp

26.設(shè)有一個(gè)頭指針為head的不帶頭結(jié)點(diǎn)單向鏈表，且p、q是指向鏈表中結(jié)點(diǎn)類型的指針變量，p指向鏈表中某結(jié)點(diǎn)a(設(shè)鏈表中沒有結(jié)點(diǎn)的數(shù)據(jù)域與結(jié)點(diǎn)a的數(shù)據(jù)域相同)，在以下程序段中，寫出相關(guān)語句(1)使該單向鏈表成為單向循環(huán)鏈表(2)刪去a結(jié)點(diǎn)q＝p；x=p一>data；while(q一>next!=NULL)q=q一>next；(1)_____________________q=p；p=->next；while(p->data!l=x){ q一p；(2)______________________}(3)______________________________參考答案：(1)q->next=head；(2)p=p->next；(3)q->next=p->next；國(guó)家開放大學(xué)2019年秋季學(xué)期期末統(tǒng)一考試數(shù)據(jù)結(jié)構(gòu)(本)試題2020年1月一、單項(xiàng)選擇題(每小題3分，共30分)1.以下說法不正確的是()。A.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)不必占用連續(xù)的存儲(chǔ)空間B.一種邏輯結(jié)構(gòu)只能有唯一的存儲(chǔ)結(jié)構(gòu)C.一種邏輯結(jié)構(gòu)可以有不同的存儲(chǔ)結(jié)構(gòu)D.線性表的順序存儲(chǔ)結(jié)構(gòu)必須占用連續(xù)的存儲(chǔ)空間參考答案：一種邏輯結(jié)構(gòu)只能有唯一的存儲(chǔ)結(jié)構(gòu)2.單向鏈表所具備的特點(diǎn)之一是()。A.可以隨機(jī)訪問表中任一結(jié)點(diǎn)B.需要占用連續(xù)的存儲(chǔ)空間C.插入元素和刪除元素的操作不需