國家開放大學本科末考試數(shù)據(jù)結構歷年試題與參考答案15秋至19秋

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

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

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

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

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

10.對一個棧頂指針為top的鏈棧進行出棧操作，用變量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]中存放的是_______。參考答案：字符串結束符12.設有串pl=”ABADF”，P2=”ABAFD”，P3=”ABADFA”P4=”ABAF”，四個串中最大的是______。參考答案：P213.在一棵二叉樹中，若編號為i的結點存在右孩子，則右孩子的順序編號為______。參考答案：2i+114.設有一個長度為20的順序表，要插入一個元素，并作為第8個元素，需移動元素的個數(shù)為______。參考答案：1315.結構中的數(shù)據(jù)元素存在多對多的關系稱為______結構。參考答案：圖狀16.設有一棵深度為4的完全二叉樹，第四層上有5個結點，該樹共有______個結點。(根所在結點為第1層)參考答案：1217.一棵二叉樹中有n個非葉結點，每一個非葉結點的度數(shù)都為2，則該樹共有______個葉結點。參考答案：n+118.在對一組記錄(55，39，97，22，16，73，65，47，88)進行直接插入排序時，當把第7個記錄65插入到有序表時，為尋找插入位置需比較______次。(由小到大排序)參考答案：319.n個元素進行冒泡法排序，第j趟冒泡要進行______次元素間的比較。參考答案：n-j20.一棵有n個葉結點的哈夫曼樹，則該樹共有______個結點。參考答案：2n-121.中序遍歷______可得到一個有序序列。參考答案：二叉排序樹22.廣義表((a，b)，d，e，((i，j)，k))的長度是______。參考答案：4

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

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

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

5.在一個不帶頭結點的鏈隊中，假設f和r分別為隊頭和隊尾指針，從該隊列中進行出隊操作，并把結點的值保存在變量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.設有一個18階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存到一維數(shù)組B中(數(shù)組下標從1開始)，則矩陣元素ag.2對應于數(shù)組B中第()號元素。(矩陣中的第1個元素是a1.1)A.42B.39C.38D.40參考答案：387.一棵采用鏈式存儲的二叉樹中，共有n一1個指針域被有效使用(即指針域為非空)。該二叉樹中有()個指針域為空。A.n+1B.nC.n-1D.n一2參考答案：n+18.設一棵哈夫曼樹共有n個非葉結點，則該樹共有()個結點。A.2nB.2n+1C.2n一1D.2n+2參考答案：2n+1

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

四、程序填空題(每空2分，共16分)25.以下函數(shù)為直接選擇排序算法，對a[1]，a[2]，…a[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.設有一個頭指針為head的不帶頭結點單向鏈表，且p、q是指向鏈表中結點類型的指針變量，p指向鏈表中某結點a(設鏈表中沒有結點的數(shù)據(jù)域與結點a的數(shù)據(jù)域相同)，在以下程序段中，寫出相關語句(1)使該單向鏈表成為單向循環(huán)鏈表(2)刪去a結點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；國家開放大學2019年秋季學期期末統(tǒng)一考試數(shù)據(jù)結構(本)試題2020年1月一、單項選擇題(每小題3分，共30分)1.以下說法不正確的是()。A.線性表的鏈式存儲結構不必占用連續(xù)的存儲空間B.一種邏輯結構只能有唯一的存儲結構C.一種邏輯結構可以有不同的存儲結構D.線性表的順序存儲結構必須占用連續(xù)的存儲空間參考答案：一種邏輯結構只能有唯一的存儲結構2.單向鏈表所具備的特點之一是()。A.可以隨機訪問表中任一結點B.需要占用連續(xù)的存儲空間C.插入元素和刪除元素的操作不需