數據結構選題單選題：(每小題10分，共計100分)1、算法是指()為解決問題而編寫的計算機程序 B.為解決問題而采取的方法與步驟C.為解決問題而需要采用的計算機語言 D.為解決問題而采用的計算方法2、設棧S的初始狀態為空，現有5個元素組成的序列{1,2,3,4,5},對該序列在S棧上依次進行如下操作(從序列中的1開始，出棧后不再進棧)：進棧、進棧、進棧、出棧、進棧、出棧、進棧。試問出棧的元素序列是( ){5,4,3,2,1} B.{2,1}{2,3} D.{3,4}3、設循環隊列中數組的下標范圍是1-n,其中頭尾指針分別是f和r,則其元素個數是()r-f B.r-f+1 C.(r-f)MODn+1(r-f+n)MODn4、 在待排序的數據表已經為有序時,下列排序算法中花費時間反而多的是( )堆排序 B?希爾排序C.冒泡排序 D.快速排序5、 在有n個子葉節點的哈夫曼樹中，其節點總數為()不確定 B.2n-1 C.2n+1D.2n6、 某數列有1000個各不相同的單元,由低到高按序排列,現要對該數列進行二分法檢索,在最壞的情況下,需要檢視()個單元()A.1000 B.10 C.100 D.5007、 已知數組A中，每個元素A[I,J]在存儲時要占3個字節，設I從1變化到8,J從1變化到10，分配內存時是從地址SA開始連續按行存儲分配的。試問：A[5,8]的起始地址為()A.SA+141 B.SA+180C.SA+222 D.SA+2258、 線性表若采用鏈表存儲結構,要求內存中可用存儲單元地址()A.必須連續 B.部分地址必須連續C.一定不連續 D.連續不連續均可9、下列敘述中,正確的是()

A.線性表的線性存儲結構優于鏈表存儲結構 B.隊列的操作方式是先進后出C.棧的操作方式是先進先出 D.二維數組是指它的每個數據元素為一個線性表的線性表10、電線上停著兩種鳥(A,B),可以看出兩只相鄰的鳥就將電線分為了一個線段。這些線段可公為兩類：一類是兩端的小鳥相同；另一類是兩端的小鳥不相同。已知：電線上兩個頂點上正好停著相同的小鳥，試問兩端為不同小鳥的線段數目一定是( )A.奇數 B.偶數 C.可奇可偶 D.數目固定單選題：(每小題10分，共計100分)1、在列車轉轍網絡中，有四個車皮編號為1，2，3，4，并按此順序送入棧中進行調度，這些車皮取出的順序是()A.4123 B.3241 C.3412 D.43122、從未排序序列中挑選元素，并將其依次放入已排序序列(初始時為空)的一端這種排序方法稱為()A.插入排序BA.插入排序B?歸并排序C.選擇排序 D.快速排序3、在計算遞歸函數時，如不使用遞歸過程，則一般情況下必須借助于()數據結構()A.棧 B.樹C.雙向隊列D.廣義表4、使用雙向鏈表存放數據的優點是()A.提高檢索速度B.很方便地插入和刪除數據C.節約存儲空間D.很快回收存儲空間5、對一個滿二叉樹，m個樹葉，l分枝結點，n個結點，貝")A.n=l+m B.6A.n=l+m B.6、一維數組與線性表的區別是()A.前者長度固定，后者長度可變C?兩者長度均固定后者長度固定，前者長度可變D.兩者長度均可變7、用某種排序方法對線性表25,84,21,47,15,27,68,35,20進行排序，結點變化如下：(1)25,84,21,47,15,27,68,35,20;(2)20,15,21,25,47,27,68,35,84;(3)15,20,21,25,35,27,47,68,84;(4)15,20,21,25,27,35,47,68,84.那么，排序方法是( )A.選擇排序 B.希爾排序C?合并排序 D?快速排序8、具有12個記錄的序列，采用冒泡排序最少的比較次數是()A．1B．144C．11D．669、下面關于二叉樹的敘述正確的是()—棵二叉樹中葉子結點的個數等于度為2的結點個數加1—棵二又樹中的結點個數大于0二叉樹中任何一個結點要么是葉，要么恰有兩個子女二叉樹中，任何一個結點的左子樹和右子樹上的結點個數一定相等10、先序序列和中序序列相同的二叉樹為空樹或()A.任一結點均無右孩子的非空二叉樹 B.僅有兩個結點的二叉樹任一結點均無左孩子的非空二叉樹 D.不存在這樣的二叉樹單選題：(每小題10分，共計100分)1、 設有三個元素A、B、C順序進棧，在進棧過程中可以出棧，出棧次序錯誤的排列是()A.ABC B.BCA C.CAB D.CBA2、 下面四種內排序方法中，要求內存容量最大的是( )A?插入排序 B?選擇排序 C.快速排序 D?歸并排序3、 設有序列F：(49,38，65，97，76,13,27，50)，使用快速排序法，其趟數為()A.3 B.2 C.1 D.44、 給出一組整型數28、10、37、63、35、30、23，請用二叉樹對它進行排序。為此，首先要生成一棵二叉樹，規則是把第一數放在根處，接著凡比它小的數放在左子樹，比它大的數放在右子樹，直到把所有的數均安排好。然后對此二叉樹進行( )，得到的就是按照升序排列好的序列。()A.前序遍歷 B.中序遍歷 C.后序遍歷 D.橫向遍歷5、 用某種排序方法對線性表(84,47,25,15,21)進行排序時，結點序列的變化如下：(1)84,47,25,15,21;(2)15,47,25,84,21;(3)15,21,25,84,47;(4)15,21,25,47,84.那么，所采用的排序方法是( )A.選擇排序 B.冒泡排序 C.插入排序 D.快速排序6、 設二叉樹根結點的層次為0,—棵高度為b的滿二叉樹中結點的個數是()A.2"b B.2'(b—1) C.2'bTD.2'(b+1)T7、深度為5的二叉樹至多有()個結點()

A．16B．32C．31D．10A．16B．32C．31D．108、下面關于線性表的描述，錯誤的是()棧是線性表的一種任給一個索引I(1〈=1〈=表中元素個數)，就能在線性表中唯一確定一個元素線性表的任一元素都有前驅和后繼 D.線性表是一個線性序列9、帶權路徑長度最小的二叉樹是()A.順序二叉樹B.A.順序二叉樹B.二叉排序樹C.判定樹D.哈夫曼樹10、有12個結點的平衡二叉樹的最大深度是()4 B.5C.6 D.34 B.5C.6 D.3單選題：(每小題10分，共計100分)1、 若用冒泡排序法對序列18，14，6，27，8，12，16，52，10，26，47，29，41，24從小到大進行排序，共要進行( )次比較。()A.33 B.45 C.70 D.912、 設n,m為某二叉樹上的兩個結點，在中序遍歷時，n在m前的條件是()A.n在m右方 B.n是m祖先 C.n在m左方 D.n是m子孫3、 下列四種排序方法，如果被排序的序列中諸元素恰好已經按要求(由小到大或由大到小排序，就元素的比較次數和移動次數而言，哪種方法最少？()A?冒泡排序 B.直接選擇排序C.直接插入排序 D?歸并排序4、 如果某二叉樹的前序為STUWV，中序為UWTVS，那么該二叉樹的后序是()A.WUVTS B.UWVTS C.VWUTSD.WUTSVTOC\o"1-5"\h\z5、 按照二叉樹的定義，具有3個結點的二叉樹有( )A.3種 B.4種 C.5種 D.6種6、 對以下關鍵字序列用快速排序法進行排序，速度最慢的情況是( )A.{19，23，3，15，7，21，8} B.{23，21，28，15，19，3，7}C.{19，7，15，28，23，21，3} D.{3，7，15，19，21，23，28}7、 數組A中，每個元素A[I，j]的長度為3個字節，行下標I為1到8,列下標j從1到10。從首地址SA開始連續存放在存儲器中，存放該數組至少需要的單元數是( )A.80B.100C.240D.270A.80B.100C.240D.2708、樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉化得到的二叉樹叫做這棵樹對應的二叉樹。正確的結論是()A.樹的先根遍歷序列與其對應的二叉樹的先序遍歷序列相同樹的先根遍歷序列與其對應的二叉樹的中序遍歷序列相同樹的后根遍歷序列與其對應的二叉樹的先序遍歷序列相同樹的后根遍歷序列與其對應的二叉樹的后序遍歷序列相同9、 在數據結構中，從邏輯上可以把數據結構分成()A.動態結構和靜態結構 B.線性結構和非線性結構C.內部結構和外部結構 D.緊湊結構和非緊湊結構10、 如果T2是由有序樹T轉換而來的二叉樹，那么T中結點的后序就是T2中結點的()A?前序 B?中序 C.后序 D.層次序單選題：(每小題10分，共計100分)1、 某二叉樹的前序遍歷結點訪問順序是abdgcefh，中序遍歷的結點訪問順序是dgbaechf，則其后序遍歷的結點訪問順序是()A.bdgcefha B.gdbecfha C.bdgaechf D.gdbehfca2、 從未排序序列中挑選元素，并將其依次放入已排序序列(初始時為空)的一端，這種排序方法稱為()A?插入排序 B?選擇排序 C?歸并排序 D?快速排序3、 快速排序方法在()情況下最不利于發揮其長處( )A.被排序的數據量太大 B.被排序數據中含有多個相同值C.被排序數據已基本有序 D.被排序數據數目為奇4、 下面關于數據結構的敘述中，正確的敘述是( )順序存儲方式的優點是存儲密度大，且插入、刪除運算效率高鏈表中的每一個結點都包含一個指針包含n個結點的二叉排序樹的最大檢索長度為log\-2n將一棵樹轉換為二又樹后，根結點沒有右子樹5、在計算機科學領域中,算法分為兩類:數值型算法和非數值型算法。下面的算法，哪一個屬于數值算法類()A.迭代法 B.冒泡法 C.黑盒法 D.雜湊(Hash)法6、 若已知一個棧的輸入序列為1,2,3…，n其輸出序列為Pl,P2,…，Pn。若P1=n，則Pi為()A.I B.n+I C.n-I+1D.不確定7、 帶頭結點的單鏈表Head為空的判定條件是()A.Head二NIL B.Head".Next二NILC.Head".Next二Head D.Head二Head8、 二維數組a的成員是6個字符組成的串，行下標I的范圍從0到8,列下標j的范圍從1到10,則存放a至少需要()個字節()TOC\o"1-5"\h\zA.90 B.180 C.240 D.5409、 由3個結點可以構造出多少種不同的有向樹( )A.2 B.3 C.4 D.510、 二維數組M[I,j]的元素是4個字符(每個字符占一個存儲單元)組成的串，行下標I的范圍從0到4,列下標j的范圍從0到5°M按行存儲元素M[3,5]的起始地址與M按列存儲時元素( )_的起始地址相同。()A.m[2,4] B.m[3,4] C.m[3,5] D.m[4,4]單選題：(每小題10分,共計100分)TOC\o"1-5"\h\z1、 判斷一個有向圖是否存在回路除了可以利用拓撲排序方法外,還可以利用( )A.求關鍵路徑的方法 B.求最短路徑的方法C.廣度優先遍歷方法 D.深度優先遍歷方法2、 在一非空二叉樹的中序遍歷序列中,根結點的右邊( )A.只有右子樹上的所有結點 B.只有右子樹上的部分結點C.只有左子樹上的所有結點 D.只有左子樹上的部分結點3、 一個隊列的入列序列是1,2,3,4,則隊列的輸出序列是( )A.4,3,2,1 B.1,2,3,4C.1,4,3,2 D.3,2,4,14、鄰接表存儲結構下圖的深度優先遍歷算法結構類似于二叉樹的()

A.先序遍歷 B.中序遍歷 C.后序遍歷按層遍歷5、 設待排序的記錄為(20,16,13,14,19)，經過下列過程將這些記錄排序：(1)20,16,13,14,19;(2)16,20,13,14,19;(3)13,16,20,14,19;(4)13,14,16,20,19;(5)13,14,16,19,20.所用的排序方法是( )A.直接插入排序 B?冒泡排序 C.希爾排序 D.堆排序6、 計算機算法一般被劃分為數值算法和非數值算法兩大類，下列敘述中，哪個不屬于數值算法()A.迭代法B.直接法C.雜湊(Hash)法D.消去法7、用歸并排序方法對線表49，38，65，97，76，13，27，49，55，04)進行排序時其第三趟的排序結果為()A.12，2738，49，49，65，76，97，04，55B.38，49，65，97，13，27，49，76，04，55C.38，49，65，97，13，76，27，49，04，55D.01，13，27，38，49，49，55，65，76，978、棧和隊列都是()A.順序存儲的線性結構 B.鏈式存儲的非線性結構限制存取點的線性結構 D.限制存取點的非線性結構9、對N個結點的線性表進行查找，用順序查找的時間復雜性為()A.N*N B.Nlog2n C.n D.log2n10、若進棧序列為1，2，3.4假定進棧和出棧可以穿插進行，則可能的出棧序列是()A.2，4，1，3 B.3，1，4，2 C.3，4，1，2 D.1，2，3，4單選題：(每小題10分，共計100分)1、 設計一個判別表達式中左、右括號是否配對的算法，采用()數據結構最佳( )A.線性表的順序存儲結構 B.棧 C.隊列線性表的鏈式存儲結構2、 設一棵二叉樹，其葉子結點分別帶權10，12，4，7，5，18，2則其帶權路徑長度最小為()A.120B.130C.140D.150

A.120B.130C.140D.1503、以下關于數據結構的敘述，正確的是()線性表的線性存儲結構優于鏈式結構二叉樹的第I層上有2的(1-1)次幕個結點，深度為K的二叉樹上有2的(k-1)次幕個結點二維數組是其數據元素為線性表的線性表棧的操作方式是先進先出4、循環隊列用數組A[0???m-1]存放其元素值，已知其頭尾指針分別是front和rear，則當前隊列中的元素個數是()A.(rear-front+m)MODm B.rear-front-1 C.rear-front+1D.rear-front5、把一般樹轉化為二叉樹的方法是：對每一結點的子樹，在其根之間加水平連線，然后僅保留()而抹掉該結點和其它子樹之間的連線，最后以樹的根結點為軸，將樹順時針轉45度即可()C.左子樹 D.最左子樹C.AOVC.左子樹 D.最左子樹C.AOV網 D.AOE網B.可執行性、確定性和有窮性6、 下列哪一種圖的鄰接矩陣是對稱矩陣( )A.有向圖 B.無向圖7、 計算機算法必須具備的三個特性是()A?可執行性、可移植性和可擴充性C.確定性、有窮性和穩定性 D.易讀性、穩定性和安全性8、對長度為10的有序表進行折半查找，設在等概率時查找成功的平均查找長度是()A.2.9 B.3.1C.3.4 D.2.6A.2.9 B.3.1C.3.4 D.2.69、設有6個結點的無向圖，該圖至少應該有()條邊才能確保是一個連通圖()A.5 B.6 C.7D.8A.5 B.6 C.7D.810、有6個元素按6，5，4，3，2.1的順序進棧，問下列哪一個不是合法的出棧序列()A.5，4，3，6，1，24，5，3，1，2，6A.5，4，3，6，1，24，5，3，1，2，63，4，6，5，2，12，3，1，4，5，63，4，6，5，2，12，3，1，4，5，6最新信息學奧賽模擬試題一、選擇題(共20題，每題1.5分，共計30分。每題有5個備選答案，前10個題為單選題，即每題有且只有一個正確答案，選對得分；后10題為不定項選擇題，即每題有1至5個正確答案，只有全部選對才得分)。1.微型計算機的性能主要取決于()。內存B)主板C)中央處理器D)硬盤E)顯示器128KB的存儲器用十六進制表示，它的最大的地址碼是()10000B)EFFFC)1FFFFD)FFFFFE)FFFF能將高級語言程序轉換為目標程序的是().調試程序B)解釋程序C)編輯程序D)編譯程序E)連接程序A=11001010B,B=00001111B,C=01011100B則AVBAC=()B01011110B)00001111C)01011100D)11001110E)11001010計算機病毒傳染的必要條件是()。在內存中運行病毒程序對磁盤進行讀寫操作在內存中運行含有病毒的可執行程序復制文件刪除文件TCP／IP協議共有()層協議3B)4C)5D)6E)77.192.168.0.1是屬于().A類地址B)B類地址B)C類地址D)D類地址E)E類地址對給定的整數序列(54,73,21,35,67,78,63,24,89)進行從小到大的排序時,采用快速排序的第一趟掃描的結果是().(24,21,35,54,67,78,63,73,89)(24,35,21,54,67,78,63,73,89)(24,21,35,54,67,63,73,78,89)(21,24,35,54,63,67,73,78,89)(24,21,35,54,67,63,73,78,89)一棵n個結點的完全二叉樹，則二叉樹的高度h為().A)n/2B)log2nC)(log2n)/2D)[log2n]+1E)2n-1下圖對該圖進行廣度優先拓樸排序得到的頂點序列正確的是().A)1,2,3,4,5,61,3,2,4,5,61,3,2,4,6,51,2,3,4,6,5,1,3,2,4,5,6下列屬于馮.諾依曼計算機模型的核心思想是（）.A） 采用二進制表示數據和指令；B） 采用”存儲程序”工作方式C） 計算機硬件有五大部件（運算器、控制器、存儲器、輸入和輸出設備）D） 結構化程序設計方法E） 計算機軟件只有系統軟件12.下列屬于輸入設備的是（）.A）打印機B）掃描儀C）光筆D）鼠標E）顯示器13.算式(1000)10-(100)16-(10)8的結果是().A)(890)10B)(986)8C)(1011100000)2D)(2E0)16E)(736)10下面關于算法的正確的說法是（）A） 算法必須有輸出B） 算法必須在計算機上用某種語言實現C） 算法不一定有輸入D） 算法必須在有限步執行后能結束E） 算法的每一步驟必須有確切的定義下列關于十進制數100的正確說法是（）.A） 原碼為01100100BB） 反碼為64HC） 反碼為9BHD） 補碼為64HE） 補碼為9BH16.關于windows系統中的窗口和對話框的說法正確的是（）.A） 對話框能移動和改變大小B） 窗口能移動和改變大小C） 對話框只能移動和但不能改變大小D） 對話框不能移動但能改變大小E） 窗口能移動和但不能改變大小17．下列邏輯運算正確的是（）。A） A（A+B）=AB） A+（A?B）=AA(B+C)=A?B+ACA+(B?C)=(A+B)?(A+C)A+1=A18.下列關于排序說法正確的是().插入排序、冒泡排序是穩定的選擇排序的時間復雜性為O(n2)選擇排序、希爾排序、快速排序、堆排序是不穩定的希爾排序、快速排序、堆排序的時間復雜性為O(nlog2n)快速排序是速度最快的排序對于一個大小為3的棧，若輸入隊列為123456，則下列輸出隊列有可能的是()。A)123456B)654321C)432165D)431256E)321654設有一個含有13個元素的Hash表(0?12),Hash函數是:H(key)=key%13,其中％是求余數運算。用二次探查法解決沖突，則對于序列(8、31、20、33、18、53、27)，則下列說法正確的是()。27在1號格子中33在6號格子中31在5號格子中20在7號格子中18在4號格子中二．問題求解(5分*2=10分)一個商場有m種顏色的小球，每種小球足夠多，在這m種小球中挑選n個小球的選法有多少種？如m=2,n=3時有4種選法分別是：兩種小球的個數分別為03,12,21,30.問：當m=4,n=4時TOC\o"1-5"\h\z選法數= 。如果一棵m度樹中有n1個度為1的結點，n2個度為2的結點， .有nm個度為m的結點，則該樹中葉結點的的個數= .三.閱讀程序寫出正確的程序運行結果(4分*8=32分)programt1;varn:integer;functioncount(n:integer):integer;beginifn=1thencount:=0elseifnmod2=0thencount:=count(ndiv2)+1elsecount:=count(n*3+1)+1;end;beginreadln(n);writeln(count(n));end.輸入:99輸出:programt2;varhi,lo:integer;procedurepl(m,n:integer;varhi,lo:integer);varI:integer;beginI:=n;hi:=0;lo:=0;RepeatI:=I-1;lo:=lo+m;Iflo>=10000thenbeginLo:=lo-10000;Hi:=hi+1;End;UntilI=0;Write(hi:4,',‘,lo:4)End;BeginP1(200,343,hi,lo);End.輸出:programt3;Vard1,d2,X,Min:real;beginMin:=10000;X:=3;whileX<15dobegind1:=sqrt(9+(X-3)*(X-3));d2:=sqrt(4+(15-X)*(15-X));if(d1+d2)<MinthenMin:=d1+d2;X:=x+0.001;end;writeln(Min:10:2);end.輸出：programt4;vari,k,n:integer;x,w:array[1..500]ofinteger;beginreadln(n);fori:=1tondobeginx[i]:=0;w[i]:=1;end;fori:=2totrunc(sqrt(n))+1doifx[i]=0thenbegink:=i*i;whileK<=ndobeginx[k]:=i;k:=k+i;end;end;fori:=ndownto1doifx[i]<>0thenbeginw[x[i]]:=w[x[i]]+w[i];w[idivx[i]]:=w[idivx[i]]+w[i];w[i]:=0;end;writeln(w[2],w[3]:5,w[5]:5);end.輸入:20輸出:四.完善程序題(4分*7=28分)1?降序組合?給定兩個自然數n,r(n>r),輸出從數1到n中按降序順序取r個自然數的所有組合.例如,n=5,r=3時,有如下組合：543542541532531521432431421321程序如下：programtk1;varn,r,i,j：integer;a:array[1..2O]ofinteger;beginwrite('n,r=');repeatreadln(n,r);untiln>r;i:=1;a[1]:=n;writeln('result:');repeatifi<>rthenifa[i]>r-ithenbegin___(1)___;i:=i+1;endelsebegin___(2)___;a[I]