2023年中央電大計算機科學與技術專業(yè)數(shù)據(jù)結構本科試卷

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

中央電大計算機科學與技術專業(yè)數(shù)據(jù)結構(本科)試題參考答案及評分標準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小題中有一空錯則1分全扣。三、判斷題(每小題1分,共10分)1.對 2.錯?3.對?4．錯 ５．對?６.對?7.錯?８．錯９.錯 10.錯四、運算題（每小題8分，共40分）根據(jù)題意,矩陣A中當元素下標Ｉ與Ｊ滿足Ｉ≥J時,任意元素Ａ[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ù)? ?? ?? ?//對1個給1分，全對給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２=２,成功.相應的散列表(6分），錯一個存儲位置扣１分,最