衢州市青少年信息學競賽輔導教師比賽筆試試卷請將答案填寫在答題紙中。一、單項選擇題（共20題，每題2分，共計40分。每題僅有一個正確答案。）1算法是指（）。A為解決問題而編制的計算機程序B為解決問題而采取的方法與步驟C為解決問題而需要采用的計算機語言D為解決問題而采用的計算方法2完全二叉樹共有2N1個結點，則它的葉結點數(shù)是（）。AN1BNC2ND2N13遞歸過程或函數(shù)調(diào)用時，處理參數(shù)和返回地址，通常使用一種稱為（）的數(shù)據(jù)結構。A隊列B多維數(shù)組C線性表D棧4200785D16的結果是（）A100010001002B24148C46416D1214105在WORD環(huán)境下使用的“剪貼板”是。A一塊內(nèi)存區(qū)域B一塊軟盤空間C一塊屏幕區(qū)域D一塊硬盤空間6設ACTRUE，BDFALSE，以下邏輯運算表達式值為真的有（）。ABADCBADCBACD7設T是一棵有N個頂點的樹，下列說法不正確的是（）。AT有N條邊BT是連通的CT是無環(huán)的DT有N1條邊8INTERNET網(wǎng)的通信協(xié)議是（）AX25BCSMA/CDCTCP/IPDCDMA9計算機在工作過程中，若突然停電，（）中的信息不會丟失。AROM和RAMBCPUCROMDRAM10在以下各項中，）不是操作系統(tǒng)軟件。ASOLARISBLINUXCWINDOWSVISTADSYBASE11對有序數(shù)組5，13，19，21，37，56，64，75，88，92，100進行二分查找，成功查找元素19的查找長度（比較次數(shù)）是（）A1B2C3D412在WINDOWS9X中，菜單項后帶有符號“”，表示該菜單項。A可以進行開關選擇B執(zhí)行時有對話框C有若干子命令D不能執(zhí)行13二叉樹T，已知其先根遍歷是1243576（數(shù)字為節(jié)點的編號，下同），中根遍歷2415736，則該二叉樹的后根遍歷是（）。A4257631B4275631C7425631D427653114面向對象程序設計（OBJECTORIENTEDPROGRAMMING）是一種程序設計的方法論，它將對象作為程序的基本單元，將數(shù)據(jù)和程序封裝在對象中，以提高軟件的重用性、靈活性和擴展性。下面關于面向對象設計的說法中，不正確的是（。A面向對象程序設計通常只采用自頂向下設計方法進行設計。B面向對象程序設計方法具有繼承性（INHERITANCE）、封裝性（ENCAPSULATION）、多態(tài)性POLYMORPHISM）等幾大特點。C支持面向對象特性的語言稱為面向對象的編程語言，目前較為流行的有C，JAVA，C等。D面向對象的程序設計的雛形來自于SIMULA語言，后來在SMALLTALK語言的完善和標準化的過程中得到更多的擴展和對以前思想的重新注解。至今，SMALLTALK語言仍然被視為面向對象語言的基礎。15HTML的標準各稱是（）。A主頁制作語言B超文本標識語言CWWW編程語言DINTERNET編程語言16地面上有標號為A、B、C的3根細柱，在A柱上放有10個直徑相同中間有孔的圓盤，從上到下一次編號為1，2，3，將A柱上的部分盤子經(jīng)過B柱移入C柱，也可以再B柱上暫存。如果B柱上的操作記錄為“進，進，出，進，進出，出，進，進，出，進，出，出”。那么C柱上，從下到上的盤子的編號為（）。A243657B241257C243176D24367517在以下各項中，（）不是CPU的組成部分。A控制器B運算器C寄存器D主板18設棧S的初始狀態(tài)為空，元素A,B,C,D,E,F依次入棧S，出棧的序列為B,D,F,E,C,A，則棧S的容量至少應該是（）。A6B5C4D319歐拉圖G是指可以構成一個閉合回路的圖，且圖G的每一條邊恰好在這個閉合回路上出現(xiàn)一次（即一筆畫成）。在以下各個描述中，不一定是歐拉圖的是（）。A圖G中沒有度為奇數(shù)的頂點B包含歐拉環(huán)游圖（歐拉環(huán)游是指通過圖中每邊恰好一次的閉路徑）C包含歐拉閉跡的圖（歐拉跡是指通過圖中每邊恰好一次的路徑）D存在一條回路，通過每個頂點恰好一次20在WORD正文部分輸入文字超過一行的寬度的時，WORD（）。A將把超出部分留在同一行B將等待按回車鍵把超出部分換行到下一行C將自動把超出部分換行到下一行D將把超出部分舍去二、不定項選擇題。（共10題，每題2分，共計20分。每題正確選項可能為一項或多項。）1下列數(shù)中，（）與25625相等。A（11001111）2B（317）8C（11001101）2D（195）162在下列關于算法復雜性的說法中，正確的有（）。A算法的時間復雜度，是指它在某臺計算機上具體實現(xiàn)時的運行時間。B算法的時間復雜度，是指對于該算法的一種或幾種主要的運算，運算的次數(shù)與問題的規(guī)模之間的函數(shù)關系。C一個問題如果NPC類的，就意味著在解決該問題時，不存在一個具有多項式時間復雜度的算法。D一個問題如果是NP類的，與C有相同的結論。31對于一個大小為3的棧，若輸入隊列為123456，則下列輸出隊列有可能的是（）。A123456B654321C312456D316524E3216544正確的二維數(shù)組類型說明是ATYPEAR2ARRAY15,51OFINTEGERBTYPEAR2ARRAY15OFARRAY51OFINTEGERCTYPEAR2ARRAY15,15OFINTEGERDTYPEAR2ARRAY15OFARRAY15OFINTEGERETYPEAR2ARRAY15,15OF015下列關于數(shù)據(jù)結構的敘述中正確的是（）。A數(shù)據(jù)結構是帶有結構的數(shù)據(jù)元素的集合B線性表的線性存儲結構優(yōu)于鏈式存儲結構C隊列是限定僅在一端進行插入，在另一端進行刪除的線性表D二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表E圖是一種非線性數(shù)據(jù)結構6評價一個算法的好壞有多種指標，下列是算法評價指標的是（）。A正確性B運行時間C占用空間D迭代次數(shù)E簡單性7對按關鍵字排序好的線性表進行二分查找，該線性表適合的存儲結構為（）。A鏈接存儲B索引存儲C散列存儲D順序存儲E循環(huán)存取8在下列防火墻（FIREWALL）的說法中，正確的有（）A防火墻式一項協(xié)助確保信息安全的設備，其會依照特定的規(guī)則，允許或是限制數(shù)據(jù)通過。B防火墻可能是一臺專屬的硬件或是安裝在一般硬件上的一套軟件。C網(wǎng)絡層防火墻可以視為一種IP數(shù)據(jù)包過濾器，只允許符合特定規(guī)則的數(shù)據(jù)包通過，其余的一概禁止穿越防火墻。D應用層防火墻是在TCP/IP的應用層上工作，可以攔截進出某應用程序的所有數(shù)據(jù)包。9以下哪些是計算機的輸出設備（）。A音箱B顯示器C打印機D掃描儀E繪圖儀10對給定的整數(shù)序列54,73,21,35,67,78,63,24,89進行從小到大的排序時,采用快速排序的第一趟掃描的結果是。A24,21,35,54,67,78,63,73,89B24,35,21,54,67,78,63,73,89C24,21,35,54,67,63,73,78,89D21,24,35,54,63,67,73,78,89三、問題求解（共4題，每題5分，共計20分）1（排列組合）在圖中有5個編號為1、2、3、4、5的區(qū)域，要在每個區(qū)域中涂上紅、黃、藍、綠四種顏色中的一種，使有相鄰邊區(qū)域的顏色不同，共有_種不同的涂色方法。（2分）又有右圖中有5個編號為1、2、3、4、5的區(qū)域，要在每個區(qū)域中涂上紅、黃、藍、綠四種顏色中的一種，使有相鄰邊區(qū)域的顏色不同，共有_種不同的涂色方法。（3分）2（圖）請用鄰接矩陣表示下圖中各個頂點的相鄰關系。3（二叉樹）有二叉樹中序序列為ABCEFGHD，后序序列為ABFHGEDC，請畫出此二叉樹，并求前序序列。4（遞歸問題）傳說在印度佛教圣地貝拿勒斯圣廟里，安放著一個黃銅板，板上插著三根寶石針，其中一根寶石針從下到上插放著由大到小的49片有孔的金片，晝夜都有一個值班的僧侶按如下規(guī)則移動金片一次只能移動一片，而小片永遠要在大片的上面，當時有人聲稱當49片金片全從一根寶石針上移動到另一根寶石針上時，就發(fā)生一聲巨響。49片金片從一根寶石針上移動到另一根寶石針上總共需要移動_次。四、完善程序（共10空，每空2分，共20分）1、快速排序（過程）【參考程序】PROCEDUREQUICKSORTVARRARRAY1NOFDATATYPELOW,HIGHINTEGERVARI,JINT