2023年中央電大計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)數(shù)據(jù)結(jié)構(gòu)本科試卷

中央電大計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)數(shù)據(jù)結(jié)構(gòu)(本科)試卷７2023年7月已考一、選擇題(每小題１分,共１0分)在一個(gè)長(zhǎng)度為n的順序表的任一位置插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為（）。 ?A．Ｏ(n）? ?B.Ｏ(n/２)???C．O(1） ??D.Ｏ(n2)帶頭結(jié)點(diǎn)的單鏈表fｉrst為空的鑒定條件是:? A．firsｔ==NUＬL； B．first－>link=＝NＵLL;? Ｃ.ｆirｓt->link==fiｒst;??D．firｓt!＝NULＬ;當(dāng)運(yùn)用大小為n的數(shù)組順序存儲(chǔ)一個(gè)隊(duì)列時(shí)，該隊(duì)列的最大長(zhǎng)度為(）。A.n－2???B.n－1 ? Ｃ.n?? D.n+1在系統(tǒng)實(shí)現(xiàn)遞歸調(diào)用時(shí)需運(yùn)用遞歸工作記錄保存實(shí)際參數(shù)的值。在傳值參數(shù)情形，需為相應(yīng)形式參數(shù)分派空間，以存放實(shí)際參數(shù)的副本;在引用參數(shù)情形,需保存實(shí)際參數(shù)的(），在被調(diào)用程序中可直接操縱實(shí)際參數(shù)。Ａ.空間???B.副本 ?C.返回地址??Ｄ.地址在一棵樹(shù)中,(）沒(méi)有前驅(qū)結(jié)點(diǎn)。A.分支結(jié)點(diǎn)?Ｂ.葉結(jié)點(diǎn)?C.樹(shù)根結(jié)點(diǎn) D.空結(jié)點(diǎn)在一棵二叉樹(shù)的二叉鏈表中,空指針域數(shù)等于非空指針域數(shù)加(）。Ａ．2 ?B.1??C．0 ?D.–1對(duì)于長(zhǎng)度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長(zhǎng)度為（)的值除以9。?A．20?B．18?C.2５ D．2２在有向圖中每個(gè)頂點(diǎn)的度等于該頂點(diǎn)的()。A.入度? ?B.出度?? Ｃ．入度與出度之和 D.入度與出度之差在基于排序碼比較的排序算法中,（)算法的最壞情況下的時(shí)間復(fù)雜度不高于O(nlog2n)。Ａ.起泡排序??B.希爾排序??Ｃ.歸并排序??D.快速排序當(dāng)α的值較小時(shí),散列存儲(chǔ)通常比其他存儲(chǔ)方式具有()的查找速度。A．較慢? ?B．較快?? C.相同填空題（每小題1分,共1０分）二維數(shù)組是一種非線性結(jié)構(gòu),其中的每一個(gè)數(shù)組元素最多有________＿個(gè)直接前驅(qū)（或直接后繼)。將一個(gè)ｎ階三對(duì)角矩陣Ａ的三條對(duì)角線上的元素按行壓縮存放于一個(gè)一維數(shù)組Ｂ中,A[0］[0]存放于B［0］中。對(duì)于任意給定數(shù)組元素B[K]，它應(yīng)是A中第_____＿_(dá)＿_(dá)行的元素。鏈表對(duì)于數(shù)據(jù)元素的插入和刪除不需移動(dòng)結(jié)點(diǎn)，只需改變相關(guān)結(jié)點(diǎn)的_＿＿_(dá)___＿域的值。在一個(gè)鏈?zhǔn)綏Ｖ?若棧頂指針等于ＮULL則為_(kāi)_＿_(dá)＿_(dá)＿＿。主程序第一次調(diào)用遞歸函數(shù)被稱為外部調(diào)用，遞歸函數(shù)自己調(diào)用自己被稱為內(nèi)部調(diào)用，它們都需要運(yùn)用棧保存調(diào)用后的___＿＿＿_(dá)__地址。在一棵樹(shù)中,_＿_(dá)＿＿_(dá)結(jié)點(diǎn)沒(méi)有后繼結(jié)點(diǎn)。一棵樹(shù)的廣義表表達(dá)為a(ｂ（c,d（ｅ,f),ｇ(h)），i(ｊ,k(x,y))),結(jié)點(diǎn)f的層數(shù)為_(kāi)_＿_(dá)__。假定根結(jié)點(diǎn)的層數(shù)為0。在一棵AVL樹(shù)（高度平衡的二叉搜索樹(shù))中,每個(gè)結(jié)點(diǎn)的左子樹(shù)高度與右子樹(shù)高度之差的絕對(duì)值不超過(guò)___＿_(dá)_＿_(dá)。n(n﹥0)個(gè)頂點(diǎn)的無(wú)向圖最多有_＿_(dá)＿_(dá)__＿條邊，最少有＿_(dá)__＿_(dá)＿_(dá)條邊。在索引存儲(chǔ)中，若一個(gè)索引項(xiàng)相應(yīng)數(shù)據(jù)對(duì)象表中的一個(gè)表項(xiàng)（記錄),則稱此索引為_(kāi)__＿＿＿_(dá)_索引,若相應(yīng)數(shù)據(jù)對(duì)象表中的若干個(gè)表項(xiàng),則稱此索引為＿_(dá)_＿_(dá)_＿_(dá)索引。判斷題(每小題１分，共10分）數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu),數(shù)組元素之間的關(guān)系既不是線性的也不是樹(shù)形的。鏈?zhǔn)酱鎯?chǔ)在插入和刪除時(shí)需要保持物理存儲(chǔ)空間的順序分派,不需要保持?jǐn)?shù)據(jù)元素之間的邏輯順序。在用循環(huán)單鏈表表達(dá)的鏈?zhǔn)疥?duì)列中，可以不設(shè)隊(duì)頭指針,僅在鏈尾設(shè)立隊(duì)尾指針。通常遞歸的算法簡(jiǎn)樸、易懂、容易編寫(xiě)，并且執(zhí)行的效率也高。一個(gè)廣義表的表尾總是一個(gè)廣義表。當(dāng)從一個(gè)小根堆(最小堆）中刪除一個(gè)元素時(shí),需要把堆尾元素填補(bǔ)到堆頂位置，然后再按條件把它逐層向下調(diào)整,直到調(diào)整到合適位置為止。對(duì)于一棵具有n個(gè)結(jié)點(diǎn)，其高度為h的二叉樹(shù)，進(jìn)行任一種順序遍歷的時(shí)間復(fù)雜度為O（h)。存儲(chǔ)圖的鄰接矩陣中，鄰接矩陣的大小不僅與圖的頂點(diǎn)個(gè)數(shù)有關(guān)，并且與圖的邊數(shù)也有關(guān)。直接選擇排序是一種穩(wěn)定的排序方法。閉散列法通常比開(kāi)散列法時(shí)間效率更高。運(yùn)算題(每小題8分,共４0分)設(shè)有一個(gè)１010的對(duì)稱矩陣Ａ，將其下三角部分按行存放在一個(gè)一維數(shù)組B中，A［0]［0]存放于B[0］中，那么A[8][5]存放于B中什么位置。這是一個(gè)記錄單鏈表中結(jié)點(diǎn)的值等于給定值x的結(jié)點(diǎn)數(shù)的算法，其中whｉle循環(huán)有錯(cuò),請(qǐng)重新編寫(xiě)出對(duì)的的wｈiｌe循環(huán)。iｎｔcounｔ(ListNode*Ha,ElemTyｐex） ? ?{?//Hａ為不帶頭結(jié)點(diǎn)的單鏈表的頭指針ｉnｔn＝0; ? ??????ｗｈilｅ(Ha－>ｌiｎk!=NULL){? Ｈa＝Hａ-＞link；? if(Ｈａ－>data==x)ｎ++; ?}returnn;? ? ?? }已知一棵二叉樹(shù)的前序和中序序列,求該二叉樹(shù)的后序序列。前序序列:A,B,C，Ｄ,E，Ｆ,G，H,I,J中序序列：Ｃ，Ｂ,A，Ｅ，F(xiàn),D，I,H,J,G后序序列：已知一個(gè)有序表（15,２6,34,3９,45,56,5８,63,74,76，８3，94)順序存儲(chǔ)于一維數(shù)組ａ[1２]中，根據(jù)折半搜索過(guò)程填寫(xiě)成功搜索下表中所給元素34，56,58,6３，9４時(shí)的比較次數(shù)。34565863943456586394元素值比較次數(shù)設(shè)散列表為HT[17]，待插入關(guān)鍵碼序列為{Jan,Feb,Mar，Apr，Ｍaｙ,June,Jｕly,Aｕg,Sep，Ocｔ，Noｖ，Dec}，散列函數(shù)為H（kｅy)＝i２，其中,i是關(guān)鍵碼第一個(gè)字母在字母表中的序號(hào)?，F(xiàn)采用線性探查法解決沖突。字母ＡBCDEＦＧHIＪKLM序號(hào)1２3４５67８910111213字母ＮOPＱRSTUVWXYZ序號(hào)1４151６171８19202１222324２526試畫(huà)出相應(yīng)的散列表；計(jì)算等概率下搜索成功的平均搜索長(zhǎng)度;算法分析題（每小題８分,共24分）１．閱讀下列算法,并補(bǔ)充所缺語(yǔ)句ｖoidpurｇｅ_linkst(LｉｓｔNode*&lａ）｛ //從頭指針為la的帶表頭結(jié)點(diǎn)的有序鏈表中刪除所有值相同的多余元素,／/并釋放被刪結(jié)點(diǎn)空間。ListNoｄep,q,t;ElemTypｅｔｅｍp;p=la-＞link;ｗhilｅ(p!＝ＮULL){ ???q=p;temｐ=p->ｄata;p=p->ｌｉnk;? iｆ(ｐ!＝NＵLL&&＿_(dá)_＿＿_(dá)＿_(dá))p=p->link; ? ｅlse{wｈｉｌe(p！=NＵLL&&_＿_(dá)){? ? t=ｐ;p＝p-＞link;ｄeletet;??｝q->lｉnｋ=p; ?}}}下面給出一個(gè)排序算法,它屬于數(shù)據(jù)表類的成員函數(shù),其中cｕrreｎｔSiｚe是數(shù)據(jù)表實(shí)例的當(dāng)前長(zhǎng)度,Vector[]是存放數(shù)據(jù)表元素的一維數(shù)組。tｅmplate<cｌａssT>voiｄｄataＬist<T>:：ｕnknowｎ(）｛ Ttemp;ｉnti,ｊ，n=cｕrｒenｔＳize; ?for(i=1;i<ｎ;i++)ｉｆ(Ｖｅctor［i].key<Ｖｅctoｒ[ｉ-1］.kｅy){ ? temp＝Ｖｅｃtｏｒ[ｉ];Vector[ｉ］=Ｖector[i-1]; ??for(ｊ＝i-2；j>＝0;j--） ? if（ｔemp.key<Vecｔor［j］.key）Vｅcｔｏr[j+1]=Ｖeｃtor[j];? ?ｅｌsｅbreａk; ??Vectoｒ[j+1]=temp；}??}寫(xiě)出該算法的功能。針對(duì)有n個(gè)數(shù)據(jù)對(duì)象的待排序的數(shù)據(jù)表,在最佳情況下，算法的排序碼比較次數(shù)和對(duì)象移動(dòng)次數(shù)分別是多少？比較次數(shù):移動(dòng)次數(shù)：已知二叉樹(shù)中的結(jié)點(diǎn)類型用BinＴreeNode表達(dá)，被定義為：structBinＴｒeeNoｄｅ｛ElemTypeｄaｔａ; BiｎTｒeｅNｏde＊leftChiｌd,＊riｇhtChｉld;}；其中data為結(jié)點(diǎn)值域,leｆtChild和ｒiｇｈｔＣｈild分別為指向左、右子女結(jié)點(diǎn)的指針域。根據(jù)下面函數(shù)的定義指出函數(shù)的功能。算法中參數(shù)ＢＴ指向一棵二叉樹(shù)的樹(shù)根結(jié)點(diǎn)。? BｉｎTrｅe(cuò)Ｎode*BｉnTｒｅe(cuò)SwｏpX(ＢiｎTreｅNoｄｅ＊ＢT）{??ｉf（BＴ==ＮＵLＬ)rｅｔuｒnＮUＬL;???eｌsｅ{ ?? BinＴreeＮodｅ*pt=ｎewＢinＴrｅe(cuò)Node; ? pt->data=BT->ｄaｔa;?? ?pｔ－>ｒｉgｈｔChild=BinTreeＳwopX(BT->leｆtＣｈild)；? ?pt->ｌefｔhild=BiｎＴreｅSwoｐX（BT-＞righｔＣhild); ???rｅturnpt; } ?}算法設(shè)計(jì)題（6分)已知二叉樹(shù)中的結(jié)點(diǎn)類型用BｉnTｒeeNｏde表達(dá),被定義為：ｓｔｒuctＢTｒeeNｏde{ｃｈardata;?BiｎTreｅNoｄe*lｅftＣｈild，*ｒigｈtChilｄ;};其中daｔa為結(jié)點(diǎn)值域，ｌeftChild和ｒｉghｔChilｄ分別為指向左、右子女結(jié)點(diǎn)的指針域，根據(jù)下面函數(shù)聲明編寫(xiě)出求一棵二叉樹(shù)中結(jié)點(diǎn)總數(shù)的算法,該總數(shù)值由函數(shù)返回。假定參數(shù)BT初始指向這棵二叉樹(shù)的根結(jié)點(diǎn)。ｉntBTreｅCｏuｎt(ＢｉnTreeNode*BＴ）;

中央電大計(jì)算機(jī)科學(xué)與技術(shù)專業(yè)數(shù)據(jù)結(jié)構(gòu)(本科)試題參考答案及評(píng)分標(biāo)準(zhǔn)7一、選擇題(每小題1分，共10分)1.A ２.B??3．B ?４.Ｄ ?５.C??６.Ａ ?7.Ｃ 8.Ｃ9.Ｃ 1０．B二、填空題(每小題1分,共1０分）1.2?? ２．(Ｋ+１)/3 3.指針 ?４．空棧5.返回? ６.葉子???7．3 ?8.19.n（ｎ-１）/2，0? 10．稠密，稀疏第9和10小題中有一空錯(cuò)則1分全扣。三、判斷題(每小題1分,共10分)1.對(duì) 2.錯(cuò)?3.對(duì)?4．錯(cuò) ５．對(duì)?６.對(duì)?7.錯(cuò)?８．錯(cuò)９.錯(cuò) 10.錯(cuò)四、運(yùn)算題（每小題8分，共40分）根據(jù)題意,矩陣A中當(dāng)元素下標(biāo)Ｉ與Ｊ滿足Ｉ≥J時(shí),任意元素Ａ[I]［Ｊ]在一維數(shù)組B中的存放位置為I*（I+1)/2+J，因此，A[8][5]在數(shù)組B中位置為???8＊（８+1)/2+5=41。whｉle（Ha!＝ＮULL)｛ ｉf（Ha->daｔａ==x）n++；?Hａ=Ｈa->linｋ；}后序序列：C,B,Ｆ,E,I，Ｊ,H，Ｇ,D,A345658639403456586394021344元素值比較次數(shù)? ?? ?? ?//對(duì)1個(gè)給1分，全對(duì)給8分??Ｈ（Jaｎ)=１02＝５,成功.?? H(Feｂ)=6２=3，成功.?Ｈ（Ｍar）=１32=6，成功.? H(Aｐｒ)＝12=０，成功.H（Maｙ)=13２=6，=7,成功, H(Jｕne)=1０2=5,＝6，=7,=8，成功.?Ｈ(Ｊｕly)=１02=５,＝６，=7,=8,＝9，成功.?Ｈ(Aug)=１2=0，=1，成功．??H(Sep)=192=9，＝10,成功. H(Ocｔ）＝１５2=7，=8，＝9,=10,=11,成功. Ｈ(Nｏv)=142＝7，=8，=9,=10，=11,=１２,成功. Ｈ（Dec)=4２=２,成功.相應(yīng)的散列表(6分），錯(cuò)一個(gè)存儲(chǔ)位置扣１分,最