湖北大學(xué)2017級(jí)普通本科期末軟件技術(shù)基礎(chǔ)考試試卷VIP

卷號(hào)：B（2017年1月）湖北大學(xué)2017級(jí)普通本科期末考試試卷軟件技術(shù)基礎(chǔ)考試范圍第1至第10章命題人黃海軍院系信工系考試形式閉卷課程類別必修學(xué)期20162專業(yè)教育技術(shù)學(xué) 大題號(hào)一二三四五六七八九十班級(jí)題分206815202110學(xué)號(hào)得分姓名閱卷人總分說(shuō)明：要求考生將所有答案答在答題紙上，寫在試卷紙上無(wú)效?！绢}得分一、選擇題（從下列備選答案中選出一個(gè)正確答案。答案選錯(cuò)或未選者，該題不得分。本大題共10小題，每小題2分，共20分）1、數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無(wú)關(guān)的是數(shù)據(jù)的________結(jié)構(gòu)。A)存儲(chǔ)B)物理C)邏輯D)物理和存儲(chǔ)2、算法分析的目的是：A)找出數(shù)據(jù)結(jié)構(gòu)的合理性B)研究算法中的輸入和輸出的關(guān)系C)分析算法的效率以求改進(jìn)D)分析算法的易懂性和文檔性3、向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng)個(gè)元素A）8B）63.5C）63D）74、鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間：A）分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針B）只有一部分，存放結(jié)點(diǎn)值C）只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針D）分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)5、鏈表適用于查找A）順序B）二分法C）順序，也能二分法D）隨機(jī)6、二叉樹是非線性數(shù)據(jù)結(jié)構(gòu)，所以。Ａ）它不能用順序存儲(chǔ)結(jié)構(gòu)存儲(chǔ);Ｂ）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都能存儲(chǔ);Ｃ）它不能用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)存儲(chǔ);Ｄ）順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)都不能使用；7、下面的排序算法中，不穩(wěn)定的排序是______。A）起泡排序；B）折半插入排序；C）希爾排序；D、基數(shù)排序。8.一個(gè)具有n個(gè)頂點(diǎn)e條邊的無(wú)向圖采用鄰邦接表表示，則表向量的大小為____。A）n；B)n+1；C)n-1；D)n+e9、采用鄰接表存儲(chǔ)的圖，其深度優(yōu)先遍歷類似二叉樹的。A）先序遍歷； B）中序遍歷； C）后序遍歷； D）層次遍歷10、在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的倍。A）1/2B）1C）2D）4本題得分二、名詞解釋（本大題共2小題，每小題3分，共6分）1、二叉樹2、線索化本題得分三、判斷題（下列命題你認(rèn)為正確的在題后括號(hào)內(nèi)打“√”，錯(cuò)誤的打“×”。本大題共8小題，每小題1分，共8分）1、鏈表的物理存儲(chǔ)結(jié)構(gòu)具有同鏈表一樣的順序。（）2、順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大，且插入、刪除運(yùn)算效率高。（）3、二叉樹中每個(gè)結(jié)點(diǎn)的兩棵子樹是有序的。（）4、森林的先根遍歷和后根遍歷與對(duì)應(yīng)的二叉樹分別進(jìn)行先序和后序遍歷結(jié)果相同。（）5、由３個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹有23種形態(tài)。（）6、鏈表結(jié)構(gòu)的序列適合于采用二分查找。（）7、任何一個(gè)無(wú)向連通圖的最小生成樹只有一棵。（）8、用鄰接表表示圖進(jìn)行廣度優(yōu)先遍歷時(shí)，通常是采用隊(duì)列來(lái)實(shí)現(xiàn)算法的。（）本題得分四、填空題（將答案填在題目中的括號(hào)內(nèi)。本大題共8小題，共15個(gè)空，每空1分，共15分）1、數(shù)據(jù)結(jié)構(gòu)被形式地定義為（D,R），其中D是（1）的有限集合，R是D上的（2）有限集合。2、線性結(jié)構(gòu)中元素之間存在（3）關(guān)系，樹形結(jié)構(gòu)中元素之間存在（4）關(guān)系，圖形結(jié)構(gòu)中元素之間存在（5）關(guān)系。3、在單鏈表中，除了首元結(jié)點(diǎn)外，任一結(jié)點(diǎn)的存儲(chǔ)位置由其（6）指示。4、向一個(gè)長(zhǎng)度為n的順序表的第i個(gè)元素(1≤i≤n+1)之前插入一個(gè)元素時(shí)，需向后移動(dòng)（7）個(gè)元素。5、在順序表中訪問(wèn)任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為（8），因此，順序表也稱為（9）的數(shù)據(jù)結(jié)構(gòu)。6、子串的定位運(yùn)算稱為（10）；（11）稱為目標(biāo)串，（12）稱為模式。7、用鄰接表表示圖進(jìn)行深度優(yōu)先遍歷時(shí)，通常是采用（13）來(lái)實(shí)現(xiàn)算法的。8、n個(gè)頂點(diǎn)e條邊的圖采用鄰接矩陣存儲(chǔ)，深度優(yōu)先遍歷算法的時(shí)間復(fù)雜度為（14）；若采用鄰接表存儲(chǔ)時(shí)，該算法的時(shí)間復(fù)雜度為（15）。本題得分五、簡(jiǎn)答題（回答要點(diǎn)，并作簡(jiǎn)明扼要的解釋。本大題共2小題，每小題5分，共20分）1、數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個(gè)概念之間有區(qū)別嗎？2、描述以下三個(gè)概念的區(qū)別：頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)（第一個(gè)元素結(jié)點(diǎn)）。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么？3、給定二叉樹的兩種遍歷序列，分別是：前序遍歷序列：D，A，C，E，B，H，F(xiàn)，G，I；中序遍歷序列：D，C，B，E，H，A，G，I，F(xiàn)，試畫出二叉樹B，并寫出其后序遍歷的序列。4、把如圖所示的樹轉(zhuǎn)化成二叉樹。本題得分六、算法分析題（本大題共3小題，每小題7分，共21分）1、閱讀下列C程序段，寫出相應(yīng)的執(zhí)行結(jié)果printf(“Inputx”);scanf(“%d”,&x);if(x<=30)if(x>20)y=x;elseif(x>10)y=2*x; if(x>0&&x<30)printf(“x=%d,y=%d”,x,y); elseprintf(“輸入數(shù)據(jù)錯(cuò)！”);試寫出當(dāng)x分別為18，8時(shí)的執(zhí)行結(jié)果2、設(shè)哈希（Hash）表的地址范圍為0～17，哈希函數(shù)為：H（K）＝KMOD16。K為關(guān)鍵字，用線性探測(cè)法再散列法處理沖突，輸入關(guān)鍵字序列：（10，24，32，17，31，30，46，47，40，63，49）造出Hash表，試回答下列問(wèn)題：（1）畫出哈希表的示意圖；（2）若查找關(guān)鍵字63，需要依次與哪些關(guān)鍵字進(jìn)行比較？（3）若查找關(guān)鍵字60，需要依次與哪些關(guān)鍵字比較？（4）假定每個(gè)關(guān)鍵字的查找概率相等，求查找成功時(shí)的平均查找長(zhǎng)度。3、已知如圖所示的有向圖，請(qǐng)給出該圖的:每個(gè)頂點(diǎn)的入/出度