【文章內(nèi)容簡介】 一個端點不在生成樹中的邊進(jìn)行排序，取權(quán)值最小的邊，將它和另一個端點加進(jìn)生成樹中。重復(fù)步驟直到所有頂點都加進(jìn)了生成樹。加入的邊依次為 v0vv1vv1v3（或 v2v3）、　Prim 算 法 實 現(xiàn) ： 　 　 （ 1） 集 合 ： 設(shè) 置 一 個 數(shù) 組 set(i=0,1,..,n1),初 始 值 為 0,代 表 對 應(yīng) 頂 點 不 在 集 合 中（ 注 意 ： 頂 點 號 與 下 標(biāo) 號 差 1） 　 　 （ 2） 圖 用 鄰 接 矩 陣 或 鄰 接 表 表 示 ， 路 徑 不 通 用 無 窮 大 表 示 ， 在 計 算 機 中 可 用 一 個 大整 數(shù) （ 如 1 30） 代 替 。 福建省莆田第一中學(xué) 信息學(xué)奧賽興趣小組 整理：林梓雨　 　全國信息學(xué)奧林匹克的官方網(wǎng)站為參與信息學(xué)競賽的老師同學(xué)們提供相關(guān)的信息 和資源，請問全國信息學(xué)奧林匹克官方網(wǎng)站的網(wǎng)址是：答案（C）A） B） C） D） 二、.不定項選擇題（共 10 題，每題 分，共計 15 分，每題正確答案的個數(shù)不少于 1。多選或少選均不得分）。答案（AB）關(guān)于 CPU 下面哪些說法是正確的： A）CPU 全稱為中央處理器（或中央處理單元）。 B）CPU 能直接運行機器語言。 C）CPU 最早是由 Intel 公司發(fā)明的。 D）同樣主頻下，32 位的 CPU 比 16 位的 CPU 運行速度快一倍。 Intel 最早發(fā)明的是微處理器，而 CPU 之前就由電子管、晶體管實現(xiàn) 位數(shù)只能說明處理的字長，所在的系統(tǒng)硬件指令不同，速度很難說誰快。64bit CPU 擁有更大的尋址能力，最大支持到 16GB 內(nèi)存， 32bit 支持 4G 內(nèi)存，而16bit 只支持 64K 內(nèi)存（1M） 。64 位 CPU 一次可提取 64 位數(shù)據(jù)，比 32 位提高了一倍，理論上性能會提升 1 倍。但這是建立在 64bit 操作系統(tǒng)，64bit 軟件的基礎(chǔ)上的（30% ） 。WindowsXP 64 位關(guān)于計算機內(nèi)存下面的說法哪些是正確的：答案（BD） A）隨機存儲器（RAM）的意思是當(dāng)程序運行時，每次具體分配給程序的內(nèi)存位置是隨機而不確定的。B）一般的個人計算機在同一時刻只能存/ 取一個特定的內(nèi)存單元。C）計算機內(nèi)存嚴(yán)格來說包括主存（ memory）、高速緩存（cache ）和寄存器（register）三個部分。D）1MB 內(nèi)存通常是指 1024*1024 字節(jié)大小的內(nèi)存。 一般是對字節(jié)的一個單元串行操作。1MB=1024KB=1024*1024BRAM 不是位置隨機，而是隨時訪問，所謂“隨機存取”，指的是當(dāng)存儲器中的消息被讀取或?qū)懭霑r，所需要的時間與這段信息所在的位置無關(guān)。 福建省莆田第一中學(xué) 信息學(xué)奧賽興趣小組 整理：林梓雨高速緩存和寄存器的物理實現(xiàn)是集成在 CPU 中，這兩部分不屬于馮諾依曼體系中的五大部分的任意一個部分。關(guān)于操作系統(tǒng)下面說法哪些是正確的：答案（BC） CPU 架構(gòu)的計算機系統(tǒng)的管理。 ，一個完整的程序在運行過程中可以被部分存放在內(nèi)存中。 ，為保證每個用戶都得到及時的響應(yīng)通常會采用時間片輪轉(zhuǎn)調(diào)度的策略。 ，操作系統(tǒng)都是免費開源的。 多任務(wù)系統(tǒng)可以是單個 CPU 構(gòu)架的，普通的 PC 都是多任務(wù)的。 操作系統(tǒng)不是都免費開源關(guān)于計算機網(wǎng)絡(luò)，下面的說法哪些是正確的：答案（C）A）網(wǎng)絡(luò)協(xié)議之所以有很多層主要是由于新技術(shù)需要兼容過去老的實現(xiàn)方案。 B）新一代互聯(lián)網(wǎng)使用的 IPv6 標(biāo)準(zhǔn)是 IPv5 標(biāo)準(zhǔn)的升級與補充。 C）TCP/IP 是互聯(lián)網(wǎng)的基礎(chǔ)協(xié)議簇，包含有 TCP 和 IP 等網(wǎng)絡(luò)與傳輸層的通訊協(xié)議。 D）互聯(lián)網(wǎng)上每一臺入網(wǎng)主機通常都需要使用一個唯一的 IP 地址，否則就必須注冊一個固定的域名來標(biāo)明其地址。網(wǎng)絡(luò)協(xié)議分層不是為了兼容，而是根據(jù)網(wǎng)絡(luò)分層模型來的。 新的 IPv6 是 IPv4 的升級。 即使注冊了域名也要有 IP 地址的。關(guān)于 HTML 下面哪些說法是正確的：答案（BD）A）HTML 全稱超文本標(biāo)記語言，實現(xiàn)了文本、圖形、聲音、乃至視頻信息的統(tǒng)一編碼。 B）HTML 不單包含有網(wǎng)頁內(nèi)容信息的描述，同時也包含對網(wǎng)頁格式信息的定義。 C）網(wǎng)頁上的超鏈接只能指向外部的網(wǎng)絡(luò)資源，本網(wǎng)站網(wǎng)頁間的聯(lián)系通過設(shè)置標(biāo)簽來實現(xiàn)。 D）點擊網(wǎng)頁上的超鏈接從本質(zhì)上就是按照該鏈接所隱含的統(tǒng)一資源定位符（URL）請求網(wǎng)絡(luò)資源或者網(wǎng)絡(luò)服務(wù)。 沒有都統(tǒng)一編碼本網(wǎng)站頁面也可以用超鏈接，就是絕對路徑。也可以用相對路徑。若 3 個頂點的無權(quán)圖 G 的鄰接矩陣用數(shù)組存儲為{{0，1，1}{1，0，1}{0，1，0}} ，假定在具體存儲中頂點依次為：v1，v2，v3 關(guān)于該圖，下面的說法哪些是正確的：答案（ABD）A）該圖是有向圖。 B）該圖是強聯(lián)通的。 福建省莆田第一中學(xué) 信息學(xué)奧賽興趣小組 整理：林梓雨C）該圖所有頂點的入度之和減所有頂點的出度之和等于 1。 D）從 v1 開始的深度優(yōu)先遍歷所經(jīng)過的頂點序列與廣度優(yōu)先的頂點序列是相同的。 可以畫出這個有向圖，矩陣存儲的時候，矩陣為非對稱，故為有向圖。 入度之和等于出度之和。在帶尾指針（鏈表指針 clist 指向尾結(jié)點）的非空循環(huán)單鏈表中每個結(jié)點都以 next 字段的指針指向下一個節(jié)點。假定其中已經(jīng)有了 2 個以上的結(jié)點。下面哪些說法是正確的：答案（AC）A）如果 p 指向一個待插入的新結(jié)點，在頭部插入一個元素的語句序列為： p^.next:=clist^.next。clist^.next:=p。 B）如果 p 指向一個待插入的新結(jié)點，在尾部插入一個元素的語句序列為： p^.next:=clist。clist^.next:=p。 C）在頭部刪除一個結(jié)點的語句序列為： p:=clist^.next。clist^.next:=clist^.next^.next。dispose(p)。 D）在尾部刪除一個結(jié)點的語句序列為： p:=clist。clist:=clist^.next。dispose(p)。 B 應(yīng)為 p^.next:=clist^.next。clist^.next:=p。 D 中要循環(huán)找到尾指針的上一個元素才能進(jìn)行刪除散列表的地址區(qū)間為 010，散列函數(shù)為 H(K)=K mod 11。采用開地址法的線性探查法處理沖突，并將關(guān)鍵字序列 26，25，72，38，8，18，59 存儲到散列表中，這些元素存入散列表的順序并不確定。假 定之前散列表為空，則元素 59 存放在散列表中的可能地址有：答案（ABC）A）5 B）7 C）9 D）10 選擇 ABCD 哈希函數(shù)的沖突避免 計算各個的散列值 26 25 72 38 8 18 59 5 4 6 5 8 7 4 這樣就可能 5 的順序：259…… 7 的順序：22359…… 9 的順序：223159…… 10 的順序：……59 上面的順序不是唯一的。排序算法是穩(wěn)定的意思是關(guān)鍵碼相同的記錄排序前后相對位置不發(fā)生改變，下列哪些排序算法是穩(wěn)定的：答案（ABCD）A）插入排序 B）基數(shù)排序 C）歸并排序 D）冒泡排序 福建省莆田第一中學(xué) 信息學(xué)奧賽興趣小組 整理：林梓雨 在編程實現(xiàn)的時候，只要控制好邊界都是可以達(dá)到穩(wěn)定排序的。在參加 NOI 系列競賽過程中，下面哪些行為是被嚴(yán)格禁止的：答案（BCD）A）攜帶書寫工具，手表和不具有通訊功能的電子詞典進(jìn)入賽場。B）在聯(lián)機測試中通過手工計算出可能的答案并在程序里直接輸出答案來獲取分?jǐn)?shù)。 C）通過互聯(lián)網(wǎng)搜索取得解題思路。D）在提交的程序中啟動多個進(jìn)程以提高程序的執(zhí)行效率。 A 有時候是可以的。這里考的是 NOI，不是 NOIP。三.、問題求解（共 2 題，每空 5 分，共計 10 分） G 中的所有頂點排成一個線性序列，使得圖中任意一對頂點 u和 v，若u，v∈E(G)，則 u 在線性序列 中出現(xiàn)在 v 之前，這樣的線性序列成為拓?fù)湫蛄小Ｈ缦碌挠邢驘o環(huán)圖，對其頂點做拓?fù)渑判颍瑒t所有可能的拓?fù)湫蛄械膫€數(shù)為__432____。用排列組合，先確定 12346 的順