NOIP2009普及組和提高組初賽試題和答案分析

1、NOIP2009普及組和提高組初賽試題和答案分析（選擇題和問題求解題部分） -chu2009-10-17 23:58      今天下午2：304：30是信息學奧賽的初賽。      因為我在等C語言的試卷出來，現(xiàn)在沒有事，就把pascal語言已經(jīng)出來的選擇題和問題求解部分，分析一下，因為C語言也是一樣的題目。有興趣的可以看看吧，自己做的答案，歡迎探討。     普及組和提高組的選擇題和問題求解題。     第十五屆

2、全國青少年信息學奧林匹克聯(lián)賽初賽試題 （ 普及組 Pascal 語言 二小時完成） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 一. 單項選擇題（共20題，每題1.5分，共計30分。每題有且僅有一個正確答案。） 1、 關(guān)于圖靈機下面的說法哪個是正確的： A) 圖靈機是世界上最早的電子計算機 B) 由于大量使用磁帶操作，圖靈機運行速度很慢。 C) 圖靈機是英國人圖靈發(fā)明的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮了重要作用。 D) 圖靈機只是一個理論上的計算模型。 【分析】選擇D        A最早的計算機是ENIAC

3、0;  B圖靈機是計算機模型，沒有運行速度，更談不上磁帶操作        C圖靈機是英國人阿蘭圖靈提出的理論，         阿蘭圖靈本人在二戰(zhàn)中破譯德軍密碼系統(tǒng)發(fā)揮重要作用，而不是圖靈機發(fā)揮作用。2、 關(guān)于計算機內(nèi)存，下列說法哪個是正確的： A) 隨機存儲器（RAM）的意思是當程序運行時，每次具體分配給程序的內(nèi)存位置是隨機而不確定的。 B) 1MB內(nèi)存通常是指1024*1024字節(jié)大小的內(nèi)存。 C) 計算機內(nèi)存嚴格說來包括主存（m

4、emory）、高速緩存（cache）和寄存器（register）三個部分。 D) 一般內(nèi)存中的數(shù)據(jù)即使在斷電的情況下也能保留2個小時以上。 【分析】選擇B 1MB=1024KB=1024*1024B        A中RAM不是位置隨機，而是隨時訪問，所謂“隨機存取”，指的是當存儲器中的消息被讀取或?qū)懭霑r，所需要的時間與信息所在的位置無關(guān)。        C中高速緩存和寄存器的物理實現(xiàn)是集成在CPU中，這兩部分不屬于馮諾依曼體系中的五大部分的任意一個部分。

5、        D中2秒都保留不住 馬上丟失3、 下列關(guān)于BIOS的說法哪個是正確的： A) BIOS是計算機基本輸入輸出系統(tǒng)軟件的簡稱。 B) BIOS包含了鍵盤、鼠標、聲卡、顯卡、打印機等常用輸入輸出設備的驅(qū)動程序。 C) BIOS一般由操作系統(tǒng)廠商來開發(fā)完成。 D) BIOS能提供各種文件拷貝、復制、刪除以及目錄維護等文件管理功能。 【分析】選A 其實bios=Basic Input Output System。但是對于是否是軟件這一說法還存在爭議呢！     

6、0;  B中BIOS只存一些系統(tǒng)啟動的基本信息，這些設備的驅(qū)動程序是不存的。        C項中BIOS一般是由單獨的芯片廠家生產(chǎn)的，最著名的都是臺灣的三家BIOS芯片廠家。        D項中，固件BIOS根本沒有這些功能。4、 關(guān)于CPU下面那個說法是正確的： A) CPU全稱為中央處理器（或中央處理單元）。 B) CPU可以直接運行匯編語言。 C) 同樣主頻下，32位的CPU比16位的CPU運行速度快一倍。 D) CPU最早是由Inte

7、l公司發(fā)明的。 【分析】選擇A CPU=Central Processing Unit                B項中，CPU只能執(zhí)行機器指令，也就是二進制的代碼                C項中，位數(shù)只能說明處理的字長，所在的系統(tǒng)硬件指令不同，速度很難說誰快  

8、60;             D項中，Intel最早發(fā)明的是微處理器，而CPU之前就由電子管、晶體管實現(xiàn)著呢。5、 關(guān)于ASCII，下面哪個說法是正確的： A) ASCII碼就是鍵盤上所有鍵的唯一編碼。 B) 一個ASCII碼使用一個字節(jié)的內(nèi)存空間就能夠存放。 C) 最新擴展的ASCII編碼方案包含了漢字和其他歐洲語言的編碼。 D) ASCII碼是英國人主持制定并推廣使用的。 【分析】選擇B ASCII碼是用一個字節(jié)保存的，八位二進制0127編碼。  &

9、#160;     A項，和鍵盤沒有對應關(guān)系        C項，擴展的ASCII碼用兩個字節(jié)，漢字編碼不是擴展ASCII的內(nèi)容。        D項，美國標準信息交換碼，美國6、 下列軟件中不是計算機操作系統(tǒng)的是： A) Windows B) Linux C) OS/2 D) WPS 【分析】選D   WPS=Word Processing System(金山公司的文字處理系統(tǒng)) &#

10、160;              B是開源Linux系統(tǒng) C是蘋果公司的系統(tǒng)7、 關(guān)于互聯(lián)網(wǎng)，下面的說法哪一個是正確的： A) 新一代互聯(lián)網(wǎng)使用的IPv6標準是IPv5標準的升級與補充。 B) 互聯(lián)網(wǎng)的入網(wǎng)主機如果有了域名就不再需要IP地址。 C) 互聯(lián)網(wǎng)的基礎(chǔ)協(xié)議為TCP/IP協(xié)議。 D) 互聯(lián)網(wǎng)上所有可下載的軟件及數(shù)據(jù)資源都是可以合法免費使用的。 【分析】選擇C 主要互聯(lián)網(wǎng)的協(xié)議是TCP/IP，TCP是傳輸層的文件傳輸協(xié)議，IP是網(wǎng)絡層的網(wǎng)際協(xié)議。 

11、       A中IPv6是IPv4的升級        B中必須有IP，域名是為了好記的        D中盜版非法8、 關(guān)于HTML語言下面哪種說法是正確的： A) HTML實現(xiàn)了文本、圖形、聲音乃至視頻信息的統(tǒng)一編碼。 B) HTML全稱為超文本標記語言。 C) 網(wǎng)上廣泛使用的Flash動畫都是由HTML編寫的。 D) HTML也是一種高級程序設計語言。 【分析】選擇B HTML(Hyper

12、Text Mark-up Language)即超文本標記語言，是構(gòu)成網(wǎng)頁文檔的主要語言。        A文本、圖形、聲音和視頻都是有各自的編碼，沒有統(tǒng)一。        C中Flash是由專門的軟件Adobe公司的Flash軟件制作。        D是一種標記語言，可以說類似于腳本，不是高級編程語言。9、 關(guān)于程序設計語言，下面哪種說法是正確的： A) 加了注釋的程序一般會比同樣的沒

13、有加注釋的程序運行速度慢。 B) 高級語言開發(fā)的程序不能使用在低層次的硬件系統(tǒng)（如：自控機床）或低端手機上。 C) 高級語言相對于低級語言更容易實現(xiàn)跨平臺的移植。 D) 以上說法都不對。 【分析】選擇C 以前的真題中出現(xiàn)過該選項，高級語言的特點        A注釋會在編譯的時候被忽視的，不影響程序運行        B高級語言可以使用底層硬件，編譯后生成目標代碼，可以在硬件系統(tǒng)上執(zhí)行10、 已知大寫字母A的ASCII編碼為65（十進制），則大寫字母J的十

14、進制ASCII編碼為： A) 71 B) 72 C) 73 D) 以上都不是 【分析】選擇D 64+9=7411、 十進制小數(shù)125.125對應的八進制數(shù)是 A) 100.1 B) 175.175 C) 175.1 D) 100.175 【分析】選擇C                 整數(shù)部分除以8取余數(shù)，結(jié)果反序?qū)?；小?shù)部分乘以8取整數(shù)，正序?qū)憽?2、 有六個元素FEDCBA 從左到右依次順序進棧，在進棧過程中會有元素被彈出棧。問下列哪一個不可

15、能是合法的出棧序列？ A) EDCFAB B) DECABF C) CDFEBA D) BCDAEF 【分析】選擇C                       注意入棧順序是FA                當CD出棧后，棧頂為E，F(xiàn)是

16、出不來的，故C不合法。13、 表達式 a*(b+c)-d 的后綴表達式是 A) abcd*+- B) abc+*d- C) abc*+d- D) -+*abcd 【分析】選擇B                  主要是考樹的遍歷，要明白前綴、中綴和后綴表達式。              &

17、#160; 構(gòu)造二叉樹，操作數(shù)做葉子節(jié)點，運算符做非葉節(jié)點。按中序遍歷就可以得到中綴表達式。14、 一個包含n個分支節(jié)點（非葉節(jié)點）的非空二叉樹，它的葉節(jié)點數(shù)目最多為： A) 2n + 1 B) 2n - 1 C) n - 1 D) n + 1 【分析】選擇D                考二叉樹的性質(zhì)：N0=N2+1 即葉子節(jié)點比二叉節(jié)點數(shù)多一個。15、 快速排序最壞情況下的算法復雜度為： A) O (log2n) B) O (n) C) O

18、 (nlog2n) D) O (n2) 【分析】選擇D    最壞情況時間復雜度，每次選擇的數(shù)都是最靠邊的數(shù)。16、 又一個由4000個整數(shù)構(gòu)成的順序表，假定表中的元素已經(jīng)按升序排列，采用二分查找定位一個元素。則最多需要幾次比較就能確定是否存在所查找的元素： A) 11次 B) 12次 C) 13次 D) 14次 【分析】選擇B         211-1=2047   212-1=4095      2047<4000

19、<4095 故樹的高度為12 17、 排序算法是穩(wěn)定的意思是關(guān)鍵碼相同的記錄排序前后相對位置不發(fā)生改變，下列哪種排序算法是不穩(wěn)定的： A) 冒泡排序 B) 插入排序 C) 歸并排序 D) 快速排序 【分析】選擇D        快排會造成數(shù)據(jù)左右位置的調(diào)換        其它排序可以編程時注意邊界條件就可以達到穩(wěn)定。18、 已知n個頂點的有向圖，若該圖是強連通的（從所有頂點都存在路徑到達其他頂點），則該圖中最少有多少條有向邊？ A) n B) n + 1 C)

20、 n - 1 D) n* (n - 1)【分析】選擇A                    構(gòu)成一個有向的圈（環(huán)），所有節(jié)點都在圈的上面。19、 全國信息學奧林匹克的官方網(wǎng)站為參與信息學競賽的老師同學們提供相關(guān)的信息和資源，請問全國信息學奧林匹克官方網(wǎng)站的網(wǎng)址是： A) B) / C) D) 【分析】選擇C   官網(wǎng)20、 在參加NOI系列競賽過程中，下面哪一種

21、行為是 不 被嚴格禁止的： A) 攜帶書寫工具，手表和不具有通訊功能的電子詞典進入賽場。 B) 在聯(lián)機測試中通過手工計算出可能的答案并在程序里直接輸出答案來獲取分數(shù)。 C) 通過互聯(lián)網(wǎng)搜索取得解題思路。 D) 在提交的程序中啟動多個進程以提高程序的執(zhí)行效果。 【分析】選擇A                 B某種意義上這是一種作弊行為        C當然不行，一般不

22、會連外部網(wǎng)絡         D造成服務器宕機，影響賽事二. 問題求解（共2題，每空5分，共10分） 1. 小陳現(xiàn)有2個任務A，B要完成，每個任務分別有若干步驟如下：A=a1->a2->a3，B=b1->b2->b3->b4->b5。在任何時候，小陳只能專心做某個任務的一個步驟。但是如果愿意，他可以在做完手中任務的當前步驟后，切換至另一個任務，從上次此任務第一個未做的步驟繼續(xù)。每個任務的步驟順序不能打亂，例如a2->b2->a3->b3是合法的，而 a2->b3-&

23、gt;a3->b2是不合法的。小陳從B任務的b1步驟開始做，當恰做完某個任務的某個步驟后，就停工回家吃飯了。當他回來時，只記得自己已經(jīng)完成了整個任務A，其他的都忘了。使計算小陳飯前已做的可能的任務步驟序列共有 _ 種。 【分析】70解法一：   相當于以前的A到B路程的問題，呵呵a3 0    1    4    10   20   35 a2 0    1    3 &

24、#160;  6    10   15a1 0    1    2    3    4    5     0    1    1    1    1    1   

25、60;      b1   b2   b3   b4   b5看懂了嗎？學過奧數(shù)的應該能明白吧。然后把a3那一行加起來1+4+10+20+35=70。解法二：排列組合+加法原理B任務中的b1一定做，而且肯定是第一個做的。除了b1外，第一類：完成A任務               只有1種。第二類：完成A任務和b2 &#

26、160;         有C(4,1)=4種。第三類：完成A任務和b2、b3       有C(5,2)=10種。第四類：完成A任務和b2、b3、b4   有C(6,3)=20種。第五類：完成A任務和b2、b3、b4、b5有C(7,4)=35種。加起來1+4+10+20+35=70。2. 有如下的一段程序： 1. a:=1; 2. b:=a; 3. d:=-a; 4. e:=a+d; 5. c:=2*d; 6. f:=b+e-d; 7

27、. g:=a*f+c; 現(xiàn)在要把這段程序分配到若干臺（數(shù)量充足）用電纜連接的PC上做并行執(zhí)行。每臺PC執(zhí)行其中的某幾個語句，并可隨時通過電纜與其他PC通訊，交換一些中間結(jié)果。假設每臺PC每單位時間可以執(zhí)行一個語句，且通訊花費的時間不計。則這段程序最快可以在_單位時間內(nèi)執(zhí)行完畢。注意：任意中間結(jié)果只有在某臺PC上已經(jīng)得到，才可以被其他PC引用。例如若語句4和6被分別分配到兩臺PC上執(zhí)行，則因為語句6需要引用語句4的計算結(jié)果，語句6必須在語句4之后執(zhí)行。 【分析】5可以畫出一個拓撲圖1>2>467   >3/    &#

28、160;             /               5/第一時間1，第二時間2和3，第三時間4和5，第四時間6，第五時間7。|第十五屆全國青少年信息學奧林匹克聯(lián)賽初賽試題（ 提高組 Pascal 語言 二小時完成 ） 全部試題答案均要求寫在答卷紙上，寫在試卷紙上一律無效 一、單項選擇題 （共10題，每題1.5分，共計15分，

29、每題有且僅有一個正確答案。）1、關(guān)于圖靈機下面的說法哪個是正確的：A）圖靈機是世界上最早的電子計算機。B）由于大量使用磁帶操作，圖靈機運行速度很慢。C）圖靈機只是一個理論上的計算模型。D）圖靈機是英國人圖靈發(fā)明的，在二戰(zhàn)中為破譯德軍的密碼發(fā)揮了重要作用?！痉治觥窟x擇C               A最早的計算機是ENIAC          

30、60;        B圖靈機是計算機模型，沒有運行速度，更談不上磁帶操作                D圖靈機是英國人阿蘭圖靈提出的理論，               阿蘭圖靈本人在二戰(zhàn)中破譯德軍密碼系統(tǒng)發(fā)揮重要作用，而不是圖靈機發(fā)揮作

31、用。    2、關(guān)于BIOS下面的說法哪個是正確的：A）BIOS是計算機基本輸入輸出系統(tǒng)軟件的簡稱。B）BIOS里包含了鍵盤、鼠標、聲卡、圖形界面顯器等常用輸入輸出設備的驅(qū)動程序。C）BIOS一般由操作系統(tǒng)廠商來開發(fā)完成。D）BIOS能提供各種文件拷貝、復制、刪除以及目錄維護等文件管理功能。【分析】選A         其實bios=Basic Input Output System。但是對于是否是軟件這一說法還存在爭議呢！      

32、  B中BIOS只存一些系統(tǒng)啟動的基本信息，這些設備的驅(qū)動程序是不存的。        C項中BIOS一般是由單獨的芯片廠家生產(chǎn)的，最著名的都是臺灣的三家。        D項中，固件BIOS根本這些功能。3、已知大寫字母A的ASCII編碼為41（十六進制），則大寫字母J的十六進制ASCII編碼為：A）48 B）49 C）50 D）以上都不是【分析】選擇D   41+9=4A    這道題目網(wǎng)上的

33、不一致，我問過我參加考試的學生，應該是這樣的。 考的是十六進制加法和細心。4、在字長為16位的系統(tǒng)環(huán)境下，一個16位帶符號整數(shù)的二進制補碼為1111111111101101。其對應的十進制整數(shù)應該是：A）19 B）-19 C）18 D）-18【分析】選擇B               1111111111101101的原碼為1000000000010011 也就是-19，最高位為符號位。5、一個包含n個分支結(jié)點（非葉結(jié)點）的非空滿k叉樹，k>=1，它

34、的葉結(jié)點數(shù)目為：A）nk+1 B）nk-1 C）(k+1)n-1 D）(k-1)n+1【分析】選擇D                考多叉樹的性質(zhì)，N0=(K-1)N+1，考試的時帶入K=2時候，驗證二叉樹能得到結(jié)果。6、表達式a*(b+c)-d的后綴表達式是：A）abcd*+- B）abc+*d- C）abc*+d- D）-+*abcd【分析】選擇B        

35、          主要是考樹的遍歷，要明白前綴、中綴和后綴表達式。                構(gòu)造二叉樹，操作數(shù)做葉子節(jié)點，運算符做非葉節(jié)點。按中序遍歷就可以得到中綴表達式。7、最優(yōu)前綴編碼，也稱Huffman編碼。這種編碼組合的特點是對于較頻繁使用的元素給與較短的唯一編碼，以提高通訊的效率。下面編碼組合哪一組不是合法的前綴編碼：A）（00，01，10

36、，11）B）（0，1，00，11）C）（0，10，110，111）D）（1，01，000，001）【分析】選擇B                0是00的前綴碼，這部分是數(shù)據(jù)結(jié)構(gòu)中哈夫曼編碼處的知識。8、快速排序平均情況和最壞情況下的算法時間復雜度分別為：A）平均情況O(nlog(2,n)，最壞情況O(n2)B）平均情況O(n)，最壞情況O(n2)C）平均情況O(n)，最壞情況O(nlog(2,n)D）平均情況O(log(2,n)，最壞情況O(n

37、2)【分析】選擇A                最好的時候是n×log（2，n），最壞情況的是退化成冒泡排序，復雜度為O（n2）。9、左圖給出了一個加權(quán)無向圖，從頂點V0開始用prim算法求最小生成樹。則依次加入最小生成樹的頂點集合的頂點序列為：A）V0，V1，V2，V3，V5，V4B）V0，V1，V5，V4，V3，V3C）V1，V2，V3，V0，V5，V4D）V1，V2，V3，V0，V4，V5 【分析】選擇A  

38、              加入的邊依次為v0v1、v1v2、v1v3（或v2v3）、v1v5、v3v4。                10、全國信息學奧林匹克的官方網(wǎng)站為參與信息學競賽的老師同學們提供相關(guān)的信息和資源，請問全國信息學奧林匹克官方網(wǎng)站的網(wǎng)址是：A）B）/C）D）【分析

39、】選擇C   官網(wǎng)二.不定項選擇題（共10題，每題1.5分，共計15分，每題正確答案的個數(shù)不少于1。多選或少選均不得分）。1、關(guān)于CPU下面哪些說法是正確的：A）CPU全稱為中央處理器（或中央處理單元）。B）CPU能直接運行機器語言。C）CPU最早是由Intel公司發(fā)明的。D）同樣主頻下，32位的CPU比16位的CPU運行速度快一倍?！痉治觥窟x擇AB                C項中，Intel最早發(fā)明的是微處理器，而CP

40、U之前就由電子管、晶體管實現(xiàn)著呢             D項中，位數(shù)只能說明處理的字長，所在的系統(tǒng)硬件指令不同，速度很難說誰快。    2、關(guān)于計算機內(nèi)存下面的說法哪些是正確的：A）隨機存儲器（RAM）的意思是當程序運行時，每次具體分配給程序的內(nèi)存位置是隨機而不確定的。B）一般的個人計算機在同一時刻只能存/取一個特定的內(nèi)存單元。C）計算機內(nèi)存嚴格來說包括主存（memory）、高速緩存（cache）和寄存器（register）三個部分。D）1MB

41、內(nèi)存通常是指1024*1024字節(jié)大小的內(nèi)存?！痉治觥窟x擇BD             一般是對字節(jié)的一個單元串行操作。1MB=1024KB=1024*1024B                A中RAM不是位置隨機，而是隨時訪問，所謂“隨機存取”，指的是當存儲器中的消息被讀取或?qū)懭霑r，所需要的時間與這段信息所在的位置

42、無關(guān)。              C中高速緩存和寄存器的物理實現(xiàn)是集成在CPU中，這兩部分不屬于馮諾依曼體系中的五大部分的任意一個部分。3、關(guān)于操作系統(tǒng)下面說法哪些是正確的：A.多任務操作系統(tǒng)專用于多核心或多個CPU架構(gòu)的計算機系統(tǒng)的管理。B.在操作系統(tǒng)的管理下，一個完整的程序在運行過程中可以被部分存放在內(nèi)存中。C.分時系統(tǒng)讓多個用戶可以共享一臺主機的運算能力，為保證每個用戶都得到及時的響應通常會采用時間片輪轉(zhuǎn)調(diào)度的策略。D.為了方便上層應用程序的開發(fā)，操作系統(tǒng)都是

43、免費開源的?！痉治觥窟x擇BC               A多任務系統(tǒng)可以是單個CPU構(gòu)架的，普通的PC都是多任務的。               D操作系統(tǒng)不是都免費開源4、關(guān)于計算機網(wǎng)絡，下面的說法哪些是正確的：A）網(wǎng)絡協(xié)議之所以有很多層主要是由于新技術(shù)需要兼容過去老的實現(xiàn)方案。B）新一代互聯(lián)網(wǎng)使用的IPv6標準是

44、IPv5標準的升級與補充。C）TCP/IP是互聯(lián)網(wǎng)的基礎(chǔ)協(xié)議簇，包含有TCP和IP等網(wǎng)絡與傳輸層的通訊協(xié)議。D）互聯(lián)網(wǎng)上每一臺入網(wǎng)主機通常都需要使用一個唯一的IP地址，否則就必須注冊一個固定的域名來標明其地址?！痉治觥窟x擇C             A網(wǎng)絡協(xié)議分層不是為了兼容，而是根據(jù)網(wǎng)絡分層模型來的。             B新的IPv6是IPv4的升級

45、。             D即使注冊了域名也要有IP地址的。5、關(guān)于HTML下面哪些說法是正確的：A）HTML全稱超文本標記語言，實現(xiàn)了文本、圖形、聲音、乃至視頻信息的統(tǒng)一編碼。B）HTML不單包含有網(wǎng)頁內(nèi)容信息的描述，同時也包含對網(wǎng)頁格式信息的定義。C）網(wǎng)頁上的超鏈接只能指向外部的網(wǎng)絡資源，本網(wǎng)站網(wǎng)頁間的聯(lián)系通過設置標簽來實現(xiàn)。D）點擊網(wǎng)頁上的超鏈接從本質(zhì)上就是按照該鏈接所隱含的統(tǒng)一資源定位符（URL）請求網(wǎng)絡資源或者網(wǎng)絡服務?！痉治觥窟x擇BD  &#

46、160;             A沒有都統(tǒng)一編碼                C本網(wǎng)站頁面也可以用超鏈接，就是絕對路徑。也可以用相對路徑。               

47、60; 6、若3個頂點的無權(quán)圖G的鄰接矩陣用數(shù)組存儲為0，1，11，0，10，1，0，假定在具體存儲中頂點依次為：v1，v2，v3 關(guān)于該圖，下面的說法哪些是正確的：A）該圖是有向圖。B）該圖是強聯(lián)通的。C）該圖所有頂點的入度之和減所有頂點的出度之和等于1。D）從v1開始的深度優(yōu)先遍歷所經(jīng)過的頂點序列與廣度優(yōu)先的頂點序列是相同的?！痉治觥窟x擇ABD                可以畫出這個有向圖，矩陣存儲的時候，矩陣為非對稱，故為有向

48、圖。                C入度之和等于出度之和。7、在帶尾指針（鏈表指針clist指向尾結(jié)點）的非空循環(huán)單鏈表中每個結(jié)點都以next字段的指針指向下一個節(jié)點。假定其中已經(jīng)有了2個以上的結(jié)點。下面哪些說法是正確的：A）如果p指向一個待插入的新結(jié)點，在頭部插入一個元素的語句序列為：p.next:=clist.next;clist.next:=p;B）如果p指向一個待插入的新結(jié)點，在尾部插入一個元素的語句序列為：p.next:=clist;

49、clist.next:=p;C）在頭部刪除一個結(jié)點的語句序列為：p:=clist.next;clist.next:=clist.next.next;dispose(p);D）在尾部刪除一個結(jié)點的語句序列為：p:=clist;clist:=clist.next;dispose(p);【分析】選擇AC                B應為p.next:=clist.next;clist.next:=p;    

50、            D中要循環(huán)找到尾指針的上一個元素才能進行刪除8、散列表的地址區(qū)間為0-10，散列函數(shù)為H(K)=K mod 11。采用開地址法的線性探查法處理沖突，并將關(guān)鍵字序列26，25，72，38，8，18，59存儲到散列表中，這些元素存入散列表的順序并不確定。假定之前散列表為空，則元素59存放在散列表中的可能地址有：A）5 B）7 C）9 D）10 【分析】選擇ABC   哈希函數(shù)的沖突避免      

51、           計算各個的散列值26   25    72    38    8    18    59                  &#

52、160;                           4     3     6        5     8   7 &

53、#160;  4                這樣就可能5的順序：25、59                                    7的順序：25、26、38、59   &