數(shù)據(jù)結(jié)構(gòu)與算法?？荚囶}+參考答案一、單選題（共40題，每題1分，共40分）1.現(xiàn)代微型計算機(jī)中所采用的電子元器件是：A、電子管B、大規(guī)模和超大規(guī)模集成電路C、晶體管D、小規(guī)模集成電路正確答案：B答案解析：現(xiàn)代微型計算機(jī)屬于第四代計算機(jī)，其主要電子元器件是大規(guī)模和超大規(guī)模集成電路。電子管是第一代計算機(jī)的主要元器件；晶體管是第二代計算機(jī)的主要元器件；小規(guī)模集成電路是第三代計算機(jī)的主要元器件。2.設(shè)棧的順序存儲空間為S(1:m)，初始狀態(tài)為Top=-1，則棧中的數(shù)據(jù)元素個數(shù)為A、top+1B、m-top+1C、m-topD、top-m正確答案：A答案解析：初始狀態(tài)Top=-1，?？铡．?dāng)有元素入棧時，Top會增加。棧中數(shù)據(jù)元素個數(shù)等于Top值加1，即棧中的數(shù)據(jù)元素個數(shù)為Top+1。而棧的存儲空間為S(1:m)，Top的取值范圍是-1到m-1，所以棧中數(shù)據(jù)元素個數(shù)一定是大于Top+1的。B選項m-top+1計算錯誤；C選項m-top不是棧中數(shù)據(jù)元素個數(shù)的正確計算方式；D選項top-m無實際意義。3.一名員工可以使用多臺計算機(jī)，每臺計算機(jī)可由多名員工使用，則實體員工和計算機(jī)間的聯(lián)系是A、多對一B、一對一C、一對多D、多對多正確答案：D答案解析：員工和計算機(jī)之間是多對多的聯(lián)系。因為一名員工可以使用多臺計算機(jī)，每臺計算機(jī)又可由多名員工使用，符合多對多聯(lián)系的定義。4.為了保證獨立的微機(jī)能夠正常工作，必須安裝的軟件是：A、網(wǎng)站開發(fā)工具B、辦公應(yīng)用軟件C、高級程序開發(fā)語言D、操作系統(tǒng)正確答案：D答案解析：操作系統(tǒng)是管理計算機(jī)硬件與軟件資源的系統(tǒng)軟件，能控制計算機(jī)的運行、管理內(nèi)存、處理器等硬件資源，為其他軟件運行提供基礎(chǔ)環(huán)境，是微機(jī)正常工作必須安裝的軟件。網(wǎng)站開發(fā)工具用于創(chuàng)建網(wǎng)站，高級程序開發(fā)語言用于編寫程序，辦公應(yīng)用軟件用于辦公處理，它們都不是微機(jī)正常工作必需安裝的基礎(chǔ)軟件。5.在微機(jī)中，西文字符所采用的編碼是：A、EBCDIC碼B、ASCII碼C、國標(biāo)碼D、BCD碼正確答案：B答案解析：ASCII碼是基于拉丁字母的一套電腦編碼系統(tǒng)，主要用于顯示現(xiàn)代英語和其他西歐語言，是微機(jī)中西文字符所采用的編碼。EBCDIC碼主要用于IBM大型機(jī)等；國標(biāo)碼是漢字編碼；BCD碼是用二進(jìn)制編碼的十進(jìn)制數(shù)，都不是西文字符的編碼。6.描述數(shù)據(jù)庫物理存儲結(jié)構(gòu)與物理存取方法的是A、用戶模式B、外模式C、內(nèi)模式或物理模式D、概念模式正確答案：C答案解析：內(nèi)模式也稱物理模式，它是數(shù)據(jù)庫物理結(jié)構(gòu)和存儲方式的描述，定義了數(shù)據(jù)在數(shù)據(jù)庫內(nèi)部的表示方式和物理存儲結(jié)構(gòu)，以及數(shù)據(jù)的物理存取方法。用戶模式即外模式，是用戶與數(shù)據(jù)庫系統(tǒng)的接口，是用戶用到的那部分?jǐn)?shù)據(jù)的描述。外模式是模式的子集。概念模式是數(shù)據(jù)庫中全體數(shù)據(jù)的邏輯結(jié)構(gòu)和特征的描述，是所有用戶的公共數(shù)據(jù)視圖。7.定義學(xué)生關(guān)系模式如下：Student(S#,Sn,Ssex，class，monitorS#)（其屬性分別為學(xué)號、學(xué)生名、性別、班級和班長學(xué)號），則該關(guān)系的主鍵是A、S#B、(S#,class)C、(S#,monitorS#)D、monitorS#正確答案：A答案解析：在關(guān)系模式Student中，學(xué)號S#能唯一標(biāo)識每一個學(xué)生，所以主鍵是S#。其他選項中，(S#,class)不能唯一確定一條記錄，因為不同班級可能有相同學(xué)號的學(xué)生；(S#,monitorS#)中monitorS#不能唯一確定一條記錄；monitorS#更不能作為主鍵，它只是一個外鍵，用來關(guān)聯(lián)班長的學(xué)號。8.需求分析的主要任務(wù)是A、確定軟件開發(fā)工具B、確定軟件系統(tǒng)的功能C、確定軟件開發(fā)人員D、確定軟件開發(fā)方法正確答案：B答案解析：需求分析是對軟件系統(tǒng)要實現(xiàn)的功能、性能、用戶界面等方面進(jìn)行詳細(xì)的調(diào)研和分析，以確定軟件系統(tǒng)應(yīng)該具備哪些功能，所以主要任務(wù)是確定軟件系統(tǒng)的功能。而確定軟件開發(fā)方法、工具和人員通常不是需求分析階段的主要任務(wù)。9.下面屬于“對象”成份之一的是A、規(guī)則B、封裝C、繼承D、屬性正確答案：D答案解析：屬性是對象的組成部分之一，它描述了對象的特征和狀態(tài)。規(guī)則、繼承、封裝不屬于對象的直接成份，它們是面向?qū)ο缶幊痰囊恍┨匦浴?0.設(shè)二叉樹共有375個結(jié)點，其中度為2的結(jié)點有187個。則度為1的結(jié)點個數(shù)是A、188B、0C、不可能有這樣的二叉樹D、1正確答案：B11.下列敘述中正確的是A、在帶鏈的隊列中，隊頭指針與隊尾指針的動態(tài)變化決定隊列的長度B、在帶鏈的棧中，棧頂指針的動態(tài)變化決定棧中元素的個數(shù)C、在循環(huán)隊列中，隊尾指針的動態(tài)變化決定隊列的長度D、在循環(huán)隊列中，隊頭指針和隊尾指針的動態(tài)變化決定隊列的長度正確答案：D12.下面對軟件特點描述正確的是A、軟件是一種邏輯實體而不是物理實體B、軟件不具有抽象性C、軟件具有明顯的制作過程D、軟件的運行存在磨損和老化問題正確答案：A答案解析：軟件是一種邏輯實體，具有抽象性，沒有明顯的制作過程，運行不存在磨損和老化問題。選項B錯誤，軟件具有抽象性；選項C錯誤，軟件沒有明顯的制作過程；選項D錯誤，軟件運行不存在磨損和老化問題。所以正確答案是A。13.在PowerPoint演示文稿中利用“大綱”窗格組織、排列幻燈片中的文字時，輸入幻燈片標(biāo)題后進(jìn)入下一級文本輸入狀態(tài)的最快捷方法是：A、按Ctrl+Enter組合鍵B、按Shift+Enter組合鍵C、按回車鍵Enter后，從右鍵菜單中選擇“降級”D、按回車鍵Enter后，再按Tab鍵第18組正確答案：A14.設(shè)表的長度為15。則在最壞情況下，快速排序所需要的比較次數(shù)為A、105B、55C、15D、75正確答案：A答案解析：快速排序在最壞情況下的時間復(fù)雜度為\(O(n^2)\)。對于長度為\(n=15\)的表，其比較次數(shù)為\(1+2+3+\cdots+14=\frac{14\times(14+1)}{2}=105\)，所以在最壞情況下，快速排序所需要的比較次數(shù)大于\(105\)。15.下面不屬于數(shù)據(jù)庫系統(tǒng)特點的是A、數(shù)據(jù)冗余度高B、數(shù)據(jù)獨立性高C、數(shù)據(jù)共享性好D、數(shù)據(jù)具有完整性正確答案：A答案解析：數(shù)據(jù)庫系統(tǒng)的特點包括數(shù)據(jù)共享性好、數(shù)據(jù)獨立性高、數(shù)據(jù)冗余度低以及數(shù)據(jù)具有完整性等。數(shù)據(jù)冗余度高不是數(shù)據(jù)庫系統(tǒng)的特點，它會導(dǎo)致數(shù)據(jù)不一致等問題，而數(shù)據(jù)庫系統(tǒng)通常致力于減少數(shù)據(jù)冗余。16.數(shù)據(jù)庫系統(tǒng)的數(shù)據(jù)獨立性是指A、不會因為系統(tǒng)數(shù)據(jù)存儲結(jié)構(gòu)與數(shù)據(jù)邏輯結(jié)構(gòu)的變化而影響應(yīng)用程序B、不會因為數(shù)據(jù)的變化而影響應(yīng)用程序C、不會因為存儲策略的變化而影響存儲結(jié)構(gòu)D、不會因為某些存儲結(jié)構(gòu)的變化而影響其他的存儲結(jié)構(gòu)正確答案：A答案解析：數(shù)據(jù)庫系統(tǒng)的數(shù)據(jù)獨立性包括物理獨立性和邏輯獨立性。物理獨立性是指用戶的應(yīng)用程序與存儲在磁盤上的數(shù)據(jù)庫中數(shù)據(jù)是相互獨立的，即數(shù)據(jù)在磁盤上的數(shù)據(jù)庫中怎樣存儲是由DBMS管理的，用戶程序不需要了解，應(yīng)用程序要處理的只是數(shù)據(jù)的邏輯結(jié)構(gòu)，這樣當(dāng)數(shù)據(jù)的物理存儲改變了，應(yīng)用程序不用改變。邏輯獨立性是指用戶的應(yīng)用程序與數(shù)據(jù)庫的邏輯結(jié)構(gòu)是相互獨立的，即當(dāng)數(shù)據(jù)的邏輯結(jié)構(gòu)改變時，用戶程序也可以不變。所以數(shù)據(jù)獨立性是指不會因為系統(tǒng)數(shù)據(jù)存儲結(jié)構(gòu)與數(shù)據(jù)邏輯結(jié)構(gòu)的變化而影響應(yīng)用程序。17.下面描述中正確的是A、軟件是程序、數(shù)據(jù)及相關(guān)文檔的集合B、軟件就是程序和數(shù)據(jù)C、軟件就是程序和相關(guān)文檔D、軟件就是可執(zhí)行的程序正確答案：A答案解析：軟件是程序、數(shù)據(jù)及相關(guān)文檔的集合。程序是軟件的可執(zhí)行部分，數(shù)據(jù)是軟件處理的對象，文檔則是對軟件功能、使用方法、設(shè)計思路等的說明，這三部分共同構(gòu)成了軟件，B選項只強調(diào)程序和數(shù)據(jù)，C選項只強調(diào)程序和相關(guān)文檔，D選項只強調(diào)可執(zhí)行程序，都不全面。18.在PowerPoint2010中，將一個高為2厘米，寬為4厘米的矩形高度調(diào)整為3厘米，在默認(rèn)狀態(tài)下，其寬度將變?yōu)椋篈、保持4厘米不變B、3厘米C、5厘米D、6厘米第33組正確答案：A答案解析：在PowerPoint2010中，當(dāng)對矩形等圖形進(jìn)行高度調(diào)整時，若要保持其寬高比例不變，需按住Shift鍵進(jìn)行操作。若不按住Shift鍵，默認(rèn)狀態(tài)下高度改變時寬度會保持不變，本題中只是調(diào)整了矩形的高度，未按住Shift鍵，所以寬度保持4厘米不變，答案選A。對圖形進(jìn)行尺寸調(diào)整時，要注意是否按住特定按鍵以保證寬高比例的變化符合預(yù)期，默認(rèn)狀態(tài)下不做特殊操作，圖形的各邊尺寸變化是獨立的，不會自動按比例調(diào)整。19.下列敘述中正確的是A、算法的優(yōu)化主要通過程序的編制技巧來實現(xiàn)B、數(shù)值型算法只需考慮計算結(jié)果的可靠性第19組C、對數(shù)據(jù)進(jìn)行壓縮存儲會降低算法的空間復(fù)雜度D、算法的復(fù)雜度與問題的規(guī)模無關(guān)正確答案：C答案解析：1.**選項A**：-空間復(fù)雜度是指算法在運行過程中占用的存儲空間大小。對數(shù)據(jù)進(jìn)行壓縮存儲，能夠減少數(shù)據(jù)存儲所需的空間，從而降低算法的空間復(fù)雜度，所以選項A正確。2.**選項B**：-算法的優(yōu)化主要是通過對算法本身的設(shè)計和改進(jìn)來實現(xiàn)的，比如選擇更優(yōu)的算法策略、減少不必要的計算等，而不僅僅是通過程序的編制技巧。程序編制技巧只是實現(xiàn)優(yōu)化的手段之一，不是主要方式，所以選項B錯誤。3.**選項C**：-算法的復(fù)雜度包括時間復(fù)雜度和空間復(fù)雜度等，它們都與問題的規(guī)模密切相關(guān)。一般來說，問題規(guī)模越大，算法的復(fù)雜度可能越高，所以選項C錯誤。4.**選項D**：-數(shù)值型算法不僅要考慮計算結(jié)果的可靠性，還要考慮計算效率、數(shù)值穩(wěn)定性等多方面因素，所以選項D錯誤。20.鐵路訂票系統(tǒng)中實體車票與實體旅客間的聯(lián)系是A、M：NB、1：NC、N：1D、1：1正確答案：A21.設(shè)某樹的度為3，且度為3的結(jié)點數(shù)為5，度為1的結(jié)點數(shù)為6，沒有度為2的結(jié)點。則該樹中的葉子結(jié)點數(shù)為A、20B、11C、不可能有這樣的樹D、22正確答案：B22.小李正在Word中編輯一篇包含12個章節(jié)的書稿，他希望每一章都能自動從新的一頁開始，最優(yōu)的操作方法是：A、將每一章標(biāo)題的段落格式設(shè)為“段前分頁”B、在每一章最后連續(xù)按回車鍵Enter，直到下一頁面開始處C、在每一章最后插入分頁符D、將每一章標(biāo)題指定為標(biāo)題樣式，并將樣式的段落格式修改為“段前分頁”正確答案：D23.定義課程的關(guān)系模式如下：Course(C#,Cn,Cr，prC1#,prC2#)（其屬性分別為課程號、課程名、學(xué)分、先修課程號1和先修課程號2），則該關(guān)系的主鍵是A、C#B、prC1#C、prC2#D、(C#,prC1#,prC2#)正確答案：A答案解析：主鍵是能唯一標(biāo)識關(guān)系中每一個元組的屬性或?qū)傩越M。在Course關(guān)系模式中，課程號C#能唯一確定一門課程，而先修課程號prC1#和prC2#可能存在多門課程有相同的先修課程號情況，不能唯一標(biāo)識元組，所以主鍵是C#。24.下列敘述中錯誤的是A、線性結(jié)構(gòu)也能采用鏈?zhǔn)酱鎯Y(jié)構(gòu)第36組B、非線性結(jié)構(gòu)一定不能采用順序存儲結(jié)構(gòu)C、有的非線性結(jié)構(gòu)也能采用順序存儲結(jié)構(gòu)D、線性結(jié)構(gòu)一定能采用順序存儲結(jié)構(gòu)正確答案：B25.第四代計算機(jī)的標(biāo)志是微處理器的出現(xiàn)，微處理器的組成是：A、運算器和存儲器B、存儲器和控制器C、運算器和控制器D、運算器、控制器和存儲器正確答案：C答案解析：第四代計算機(jī)的標(biāo)志是微處理器的出現(xiàn)，微處理器由運算器和控制器組成。運算器負(fù)責(zé)算術(shù)運算和邏輯運算，控制器則負(fù)責(zé)指揮和協(xié)調(diào)計算機(jī)各部件的工作，控制計算機(jī)的運行流程。存儲器不屬于微處理器的組成部分。26.小明希望在Excel的每個工作簿中輸入數(shù)據(jù)時，字體、字號總能自動設(shè)為Calibri、9磅，最優(yōu)的操作方法是：A、先輸入數(shù)據(jù)，然后選中這些數(shù)據(jù)并設(shè)置其字體、字號B、先選中整個工作表，設(shè)置字體、字號后再輸入數(shù)據(jù)C、先選中整個工作表并設(shè)置字體、字號，之后將其保存為模板，再依據(jù)該模板創(chuàng)建新工作簿并輸入數(shù)據(jù)D、通過后臺視圖的常規(guī)選項，設(shè)置新建工作正確答案：D27.樹的度為3，且有9個度為3的結(jié)點，20個葉子結(jié)點，但沒有度為1的結(jié)點。則該樹總的結(jié)點數(shù)為A、29B、不可能有這樣的樹C、47D、30正確答案：D28.小劉在PowerPoint演示文稿中插入了一幅Office自帶的WMF格式剪貼畫，他希望分別調(diào)整一下該剪貼畫各部分顏色，最優(yōu)的操作方法是：A、通過新建主題顏色來調(diào)整剪貼畫各部分的默認(rèn)顏色B、先取消剪貼畫組合，然后分別設(shè)置各部分的顏色C、剪貼畫作為一個圖片整體，只能整體改變其顏色D、通過“圖片工具|格式”選項卡上的“顏色”工具重新著色即可正確答案：B答案解析：在PowerPoint中，對于插入的WMF格式剪貼畫，若要分別調(diào)整各部分顏色，首先要取消剪貼畫組合，使其成為多個獨立部分，然后就可以分別對各部分設(shè)置顏色了。A選項新建主題顏色只能改變主題相關(guān)顏色，不能單獨針對剪貼畫各部分；C選項與實際操作不符，剪貼畫可組合也可取消組合后分別操作；D選項“圖片工具|格式”選項卡上的“顏色”工具主要是進(jìn)行一些預(yù)設(shè)的重新著色等操作，不能分別調(diào)整各部分顏色。29.下列敘述中正確的是A、排序二叉樹的中序遍歷序列是有序序列B、多重鏈表必定是非線性結(jié)構(gòu)C、任何二叉樹只能采用鏈?zhǔn)酱鎯Y(jié)構(gòu)D、堆可以用完全二叉樹表示，其中序遍歷序列是有序序列第11組正確答案：A答案解析：排序二叉樹的特點是左子樹上所有節(jié)點的值均小于根節(jié)點的值，右子樹上所有節(jié)點的值均大于根節(jié)點的值。所以其進(jìn)行中序遍歷，是先遍歷左子樹，再訪問根節(jié)點，最后遍歷右子樹，得到的序列是有序序列。選項B多重鏈表有線性和非線性之分；選項C二叉樹也可以采用順序存儲結(jié)構(gòu)；選項D堆的中序遍歷序列不一定是有序序列。30.下面屬于應(yīng)用軟件的是A、交通管理appB、安卓(AndroiD.操作系統(tǒng)C、C語言編譯器D、數(shù)據(jù)庫管理系統(tǒng)正確答案：A答案解析：應(yīng)用軟件是為滿足用戶不同領(lǐng)域、不同問題的應(yīng)用需求而設(shè)計開發(fā)的軟件。交通管理app是專門用于交通管理相關(guān)功能的軟件，屬于應(yīng)用軟件。安卓操作系統(tǒng)是系統(tǒng)軟件，用于管理和控制計算機(jī)硬件與軟件資源。C語言編譯器是將C語言代碼轉(zhuǎn)換為機(jī)器可執(zhí)行代碼的工具，屬于開發(fā)工具軟件。數(shù)據(jù)庫管理系統(tǒng)是用于管理數(shù)據(jù)庫的軟件系統(tǒng)，屬于系統(tǒng)軟件范疇。31.為了保證公司網(wǎng)絡(luò)的安全運行，預(yù)防計算機(jī)病毒的破壞，可以在計算機(jī)上采取的方法是：A、磁盤掃描B、開啟防病毒軟件C、修改注冊表D、安裝瀏覽器加載項正確答案：B答案解析：開啟防病毒軟件是預(yù)防計算機(jī)病毒破壞的有效方法之一。防病毒軟件可以實時監(jiān)測計算機(jī)系統(tǒng)，檢測并清除病毒、木馬、惡意軟件等威脅，保護(hù)計算機(jī)系統(tǒng)的安全。磁盤掃描主要用于檢查磁盤錯誤等，不能直接預(yù)防病毒。安裝瀏覽器加載項可能會帶來安全風(fēng)險，而不是預(yù)防病毒。修改注冊表不當(dāng)可能會導(dǎo)致系統(tǒng)故障，也不能有效預(yù)防病毒。32.度為3的一棵樹共有30個結(jié)點，其中度為1的結(jié)點個數(shù)分別為3,4。則該樹中的葉子結(jié)點數(shù)為A、不可能有這樣的樹B、16C、14D、15正確答案：D33.旅游管理系統(tǒng)中實體旅游團(tuán)與實體游客之間的聯(lián)系是A、N：1B、1：NC、M：ND、1：1正確答案：C34.下面不屬于需求分析階段工作的是A、需求計劃B、撰寫軟件需求規(guī)格說明書C、需求獲取D、需求分析正確答案：A答案解析：需求分析階段的工作主要包括需求獲取、需求分析、編寫軟件需求規(guī)格說明書、需求評審等。需求計劃不屬于需求分析階段的工作內(nèi)容。35.生產(chǎn)每種產(chǎn)品需要多種零件，則實體產(chǎn)品和零件間的聯(lián)系是A、多對一B、一對一C、多對多D、一對多正確答案：C答案解析：生產(chǎn)每種產(chǎn)品需要多種零件，說明一種產(chǎn)品對應(yīng)多種零件；同時，一個零件也可能被多種產(chǎn)品所需要，所以實體產(chǎn)品和零件間的聯(lián)系是多對多。36.研究量子計算機(jī)的目的是為了解決計算機(jī)中的：A、計算精度問題B、速度問題C、存儲容量問題D、能耗問題正確答案：D37.十進(jìn)制整數(shù)設(shè)為整數(shù)類I，則下面屬于類I的實例的是A、518E-2B、0.518C、518第34組D、-518正確答案：D答案解析：1.首先分析選項A：-“-518”是一個十進(jìn)制整數(shù)，符合整數(shù)類I的定義。2.接著看選項B：-“0.518”是小數(shù)，不是整數(shù)，不屬于類I。3.再看選項C：-“518E-2”表示科學(xué)計數(shù)法，即518×10?2=5.18，是小數(shù)，不是整數(shù)，不屬于類I。4.最后看選項D：-“518第34組”不是一個有效的數(shù)字表示形式，不屬于整數(shù)類I。所以