山東大學(xué)網(wǎng)絡(luò)教育《數(shù)據(jù)結(jié)構(gòu)》( A 卷)

山東大學(xué)網(wǎng)絡(luò)教育《數(shù)據(jù)結(jié)構(gòu)》(A卷)山東大學(xué)網(wǎng)絡(luò)教育《數(shù)據(jù)結(jié)構(gòu)》(A卷)山東大學(xué)網(wǎng)絡(luò)教育《數(shù)據(jù)結(jié)構(gòu)》(A卷)資料僅供參考文件編號(hào)：2022年4月山東大學(xué)網(wǎng)絡(luò)教育《數(shù)據(jù)結(jié)構(gòu)》(A卷)版本號(hào)：A修改號(hào)：1頁次：1.0審核：批準(zhǔn):發(fā)布日期：《數(shù)據(jù)結(jié)構(gòu)》模擬卷一、選擇題在一個(gè)長度為n的順序表的任一位置插入一個(gè)新元素的漸進(jìn)時(shí)間復(fù)雜度為（A）。 A.O(n) B.O(n/2) C.O(1) D.O(n2)帶頭結(jié)點(diǎn)的單鏈表first為空的判定條件是：（B）。 A.first==NULL; B.first->link==NULL; C.first->link==first; D.first!=NULL;3.從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（C）兩大類。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)在系統(tǒng)實(shí)現(xiàn)遞歸調(diào)用時(shí)需利用遞歸工作記錄保存實(shí)際參數(shù)的值。在傳值參數(shù)情形，需為對(duì)應(yīng)形式參數(shù)分配空間，以存放實(shí)際參數(shù)的副本；在引用參數(shù)情形，需保存實(shí)際參數(shù)的（D），在被調(diào)用程序中可直接操縱實(shí)際參數(shù)。A.空間 B.副本 C.返回地址 D.地址5.以下數(shù)據(jù)結(jié)構(gòu)中，哪一個(gè)是線性結(jié)構(gòu)（D）。A．廣義表B.二叉樹C.稀疏矩陣D.串6.以下屬于邏輯結(jié)構(gòu)的是（C）。A．順序表B.哈希表C.有序表D.單鏈表對(duì)于長度為9的有序順序表，若采用折半搜索，在等概率情況下搜索成功的平均搜索長度為（C）的值除以9。A.20 B.18 C.25 D.22在有向圖中每個(gè)頂點(diǎn)的度等于該頂點(diǎn)的（C）。A.入度 B.出度 C.入度與出度之和 D.入度與出度之差在基于排序碼比較的排序算法中，（C）算法的最壞情況下的時(shí)間復(fù)雜度不高于O(nlog2n)。A.起泡排序 B.希爾排序 C.歸并排序 D.快速排序當(dāng)α的值較小時(shí)，散列存儲(chǔ)通常比其他存儲(chǔ)方式具有（B）的查找速度。A.較慢 B.較快 C.相同D.不同二、填空題二維數(shù)組是一種非線性結(jié)構(gòu)，其中的每一個(gè)數(shù)組元素最多有___2___個(gè)直接前驅(qū)（或直接后繼）。將一個(gè)n階三對(duì)角矩陣A的三條對(duì)角線上的元素按行壓縮存放于一個(gè)一維數(shù)組B中，A[0][0]存放于B[0]中。對(duì)于任意給定數(shù)組元素B[K]，它應(yīng)是A中第_「(K+1)／3」_行的元素。鏈表對(duì)于數(shù)據(jù)元素的插入和刪除不需移動(dòng)結(jié)點(diǎn)，只需改變相關(guān)結(jié)點(diǎn)的_指針__域的值。在一個(gè)鏈?zhǔn)綏Ｖ?，若棧頂指針等于NULL則為__空棧__。主程序第一次調(diào)用遞歸函數(shù)被稱為外部調(diào)用，遞歸函數(shù)自己調(diào)用自己被稱為內(nèi)部調(diào)用，它們都需要利用棧保存調(diào)用后的__返回___地址。在一棵樹中，_葉子_結(jié)點(diǎn)沒有后繼結(jié)點(diǎn)。一棵樹的廣義表表示為a(b(c,d(e,f),g(h)),i(j,k(x,y)))，結(jié)點(diǎn)f的層數(shù)為__3__。假定根結(jié)點(diǎn)的層數(shù)為0。在一棵AVL樹（高度平衡的二叉搜索樹）中，每個(gè)結(jié)點(diǎn)的左子樹高度與右子樹高度之差的絕對(duì)值不超過__1____。n(n﹥0)個(gè)頂點(diǎn)的無向圖最多有_n（n-1）/2__條邊，最少有___0___條邊。在索引存儲(chǔ)中，若一個(gè)索引項(xiàng)對(duì)應(yīng)數(shù)據(jù)對(duì)象表中的一個(gè)表項(xiàng)（記錄），則稱此索引為_稠密_索引，若對(duì)應(yīng)數(shù)據(jù)對(duì)象表中的若干個(gè)表項(xiàng)，則稱此索引為__稀疏__索引。三、判斷題數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu)，數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的(對(duì))鏈?zhǔn)酱鎯?chǔ)在插入和刪除時(shí)需要保持物理存儲(chǔ)空間的順序分配，不需要保持?jǐn)?shù)據(jù)元素之間的邏輯順序(錯(cuò))在用循環(huán)單鏈表表示的鏈?zhǔn)疥?duì)列中，可以不設(shè)隊(duì)頭指針，僅在鏈尾設(shè)置隊(duì)尾指針(對(duì))通常遞歸的算法簡單、易懂、容易編寫，而且執(zhí)行的效率也高(錯(cuò))一個(gè)廣義表的表尾總是一個(gè)廣義表(對(duì))當(dāng)從一個(gè)小根堆（最小堆）中刪除一個(gè)元素時(shí)，需要把堆尾元素填補(bǔ)到堆頂位置，然后再按條件把它逐層向下調(diào)整，直到調(diào)整到合適位置為止(對(duì))對(duì)于一棵具有n個(gè)結(jié)點(diǎn)，其高度為h的二叉樹，進(jìn)行任一種次序遍歷的時(shí)間復(fù)雜度為O(h)(錯(cuò))存儲(chǔ)圖的鄰接矩陣中，鄰接矩陣的大小不但與圖的頂點(diǎn)個(gè)數(shù)有關(guān)，而且與圖的邊數(shù)也有關(guān)(錯(cuò))直接選擇排序是一種穩(wěn)定的排序方法(錯(cuò))閉散列法通常比開散列法時(shí)間效率更高(錯(cuò))四、運(yùn)算題設(shè)有一個(gè)1010的對(duì)稱矩陣A，將其下三角部分按行存放在一個(gè)一維數(shù)組B中，A[0][0]存放于B[0]中，那么A[8][5]存放于B中什么位置。解：根據(jù)題意，矩陣A中當(dāng)元素下標(biāo)I與J滿足I≥J時(shí)，任意元素A[I][J]在一維數(shù)組B中的存放位置為I*(I+1)/2+J，因此，A[8][5]在數(shù)組B中位置為 8*(8+1)/2+5=41。這是一個(gè)統(tǒng)計(jì)單鏈表中結(jié)點(diǎn)的值等于給定值x的結(jié)點(diǎn)數(shù)的算法，其中while循環(huán)有錯(cuò)，請(qǐng)重新編寫出正確的while循環(huán)。intcount(ListNode*Ha,ElemTypex) { 3456586394345658639434565863943456586394021344 H(Feb)=62=3，成功. H(Mar)=132=6，成功. H(Apr)=12=0，成功.H(May)=132=6，=7，成功， H(June)=102=5，=6，=7，=8，成功.H(July)=102=5，=6，=7，=8，=9，成功. H(Aug)=12=0，=1，成功. H(Sep)=192=9，=10，成功. H(Oct)=152=7，=8，=9，=10，=11，成功. H(Nov)=142=7，=8，=9，=10，=11，=12，成功. H(Dec)=42=2，成功.相應(yīng)的散列表012345678910111213AprAugDecFebJanMarMayJuneJulySepOctNov(1)(2)(1)(1)(1)(1)(2)(4)(5)(2)(5)(6)(2)搜索成功的平均搜索長度為 1/12*(1+2+1+1+1+1+2+4+5+2+5+6)=31/12五、算法設(shè)計(jì)題已知二叉樹中的結(jié)點(diǎn)類型用BinTreeNode表示，被定義為:structBTreeNode{chardata; BinTreeNode*leftChild,*rightChild;};其中data為結(jié)點(diǎn)值域，leftChild和rightChild分別為指向左、右子女結(jié)點(diǎn)的指針域，根據(jù)下面函數(shù)聲明編寫出求一棵二叉樹中結(jié)點(diǎn)總數(shù)的算法，該總數(shù)值由函數(shù)返回。假定參數(shù)BT初始指向這棵二叉樹的根結(jié)點(diǎn)。IntBTreeLeafCount(BinTreeNode*BT);解：intBTreeLeafCount(BinTreeNode*BT){ if(BT==NULL)return0;