信息學選拔試題及答案.doc

信息學興趣小組選拔試題 班級 姓名 學號 成績 1 有紅 黃 黑 白四色球各一個 放置在一個內(nèi)存編號為 1 2 3 4 四個格子的盒中 每個格子放置一只球 它們的順序不知 甲 乙 丙三人猜測放置順序如下 甲 黑編號 1 黃編號 2 乙 黑編號 2 白編號 3 丙 紅編號 2 白編號 4 結果證明甲乙丙三人各猜中了一半 寫出四色球在盒子中放置情況及推理過程 寫出四色球在盒子中放置情況及推理過程 2 列舉一個算法 使算法的解能對應相應的問題 例如 設問題為 學生答題 答對一題可得 10 分 答錯一題則要扣去 5 分 輸入答對 的題數(shù) M 與答錯的題數(shù) N 求最后得分 S 是多少 列舉出相應算法為 X 10 Y 5 READ M N S X M Y N 現(xiàn)有以下問題 用五角錢換成 5 分 2 分與 1 分的硬幣 可有多少種換法 請列出該問題的算法 請列出該問題的算法 3 下圖中用點表示城市 點與點之間的聯(lián)系表示城市間的道路 D C A B 試問 能否找出一條從 A 城市出發(fā) 經(jīng)過圖中所有道路一次后又回到出發(fā)點的通路來 能否從 A 出發(fā) 找出去每個城市且只去一次的通路來 若能 則寫出通路 否則說明理由 4 一個將角編了號的正三角形可以繞著外心 O 中心 逆時針旋轉 1200 如下圖所示 1 3 0 0 2 3 1 2 圖一 圖二 如果將這一旋轉用字母 a 來表示 看作運算對象 同時用 aa 或 a2 表示旋轉 E F a 1200后再旋轉 1200 也就是說將連續(xù)運動看作乘法運算 那么三角形狀態(tài) 可 簡稱為元素 即可與運動表達式關聯(lián)起來 請回答 如果將圖一的原始三角形連續(xù)旋轉 1200N 次 簡單地表示為 an N 為任意自 然數(shù) 試求 an 的值 指三角形旋轉后的結果狀態(tài) 如果將下面的旋轉看作是 a 的逆元素 記為 a 1 則有 a 1 a2 試求 a n 3 1 0 0 1 2 2 3 圖三 5 已知一個數(shù)列 U1 U2 U3 UN 往往可以找到一個最小的 K 值和 K 個 數(shù) a1 a2 ak使得數(shù)列從某項開始都滿足 UN K a1UN K 1 a2UN K 2 akUN A 例如對斐波拉契數(shù)列 1 1 2 3 5 可以發(fā)現(xiàn) 當 K 2 a1 1 a2 1 時 從 第 3 項起 即 N 1 都滿足 U n 2 Un 1 Un 試對數(shù)列 12 22 32 n2 求 K 和 a1 a2 aK使得 A 式成立 6 某班有 50 名學生 每位學生發(fā)一張調(diào)查卡 上寫 a b c 三本書的書名 將讀過 的書打 結果統(tǒng)計數(shù)字如下 只讀 a 者 8 人 只讀 b 者 4 人 只讀 c 者 3 人 全部讀過的有 2 人 讀過 a b 兩本書的有 4 人 讀過 a c 兩本書的有 2 人 讀過 b c 兩本書的有 3 人 6 1 讀過 a 的人數(shù)是 2 一本書也沒有讀過的人數(shù)是 7 在磁盤的目錄結構中 我們將與某個子目錄有關聯(lián)的目錄數(shù)稱為度 例如下圖 該圖表達了 A 盤的目錄結構 D1 Dll D2 均表示子目錄的名字 在這里 根 目錄的度為 2 D1 子目錄的度為 3 D11 子目錄的度為 4 D12 D2 D111 D112 D113 的度均為 1 不考慮子目錄的名字 則可簡單的圖 示為如下所示的樹結構 若知道一個磁盤的目錄結構中 度為 2 的子目錄有 2 個 度為 3 的子目錄有 1 個 度為 4 的子目錄有 3 個 試問 度為 1 的子目錄有幾個 8 根據(jù) Nocomachns 定理 任何一個正整數(shù) n 的立方一定可以表示成 n 個連續(xù)的奇數(shù)的和 aa 例如 13 1 23 3 5 33 7 9 11 43 13 15 17 19 在這里 若將每一個式中的最小奇數(shù)稱為 X 那么當給出 n 之后 請寫出 X 與 n 之間 的關系表達式 9 有 2 n 的一個長方形方格 用一個 1 2 的骨牌鋪滿方格 例如 n 3 時 為 2 3 方 格 此時用一個 1 2 的骨牌鋪滿方格 共有 3 種鋪法 試對給出的任意一個 n n 0 求出鋪法總數(shù)的遞推公式 10 在 a b c d e f 六件物品中 按下面的條件能選出的物品是 1 a b 兩樣至少有一樣 2 a d 不能同時取 3 a e f 中必須有 2 樣 4 b c 要么都選 要么都不選 5 c d 兩樣中選一樣 6 若 d 不選 則 e 也不選 11 平面上有三條平行直線 每條直線上分別有 7 5 6 個點 且不同直線上三個點都不 在同一條直線上 問用這些點為頂點 能組成多少個不同三角形 12 如下圖 有一個無窮大的的棧 S 在棧的右邊排列著 1 2 3 4 5 共五個車廂 其中每個 車廂可以向左行走 也可以進入棧 S 讓后面的車廂通過 現(xiàn)已知第一個到達出口的是 3 號車廂 請寫出所有可能的到達出口的車廂排列總數(shù) 不必給出每種排列 出口 1 2 3 4 5 S 13 將 N 個紅球和 M 個黃球排成一行 例如 N 2 M 3 可得到以下 6 種排法 紅紅黃黃黃 紅黃紅黃黃 紅黃黃紅黃 黃紅紅黃黃 黃紅黃紅黃 黃黃黃紅紅 問題 當 N 4 M 3 時有多少種不同排法 不用列出每種排法 14 現(xiàn)在市場上有一款汽車 A 很熱銷 售價是 2 萬美元 汽車 A 每加侖汽油可以 行駛 20 英里 普通汽車每年大約行駛 12000 英里 油價是每加侖 1 美元 不久我 公司就要推出新款節(jié)油汽車 B 汽車 B 每加侖汽油可以行駛 30 英里 現(xiàn)在我們要 為 B 制定價格 它的價格略高于 A 我們預計如果用戶能夠在兩年內(nèi)通過節(jié)省油錢 把 B 高出 A 的價錢彌補回來 則他們就會購買 B 否則就不會購買 B 那么 B 的最 高價格應為 萬美元 15 無向圖 G 有 16 條邊 有 3 個 4 度頂點 4 個 3 度頂點 其余頂點的度均小于 3 則 G 至少有 個頂點 16 一個家具公司生產(chǎn)桌子和椅子 現(xiàn)在有 113 個單位的木材 每張桌子要使用 20 個單位 的木材 售價是 30 元 每張椅子要使用 16 個單位的木材 售價是 20 元 使用已有的木材 生產(chǎn)桌椅 不一定要把木材用光 最多可以賣 元錢 17 75 名兒童到游樂場去玩 他們可以騎旋轉木馬 坐滑行鐵道 乘宇宙飛船 已知其中 20 人這三種東西都玩過 55 人至少玩過其中的兩種 若每樣乘坐一次的費用是 5 元 游樂場總共收入 700 可知有 名兒童沒有玩過其中任何一種 18 將數(shù)組 32 74 25 53 28 43 86 47 中的元素按從小到大的順序排列 每次可以交換任 意兩個元素 最少需要交換 次 19 有 3 個課外小組 物理組 化學組和生物組 今有張 王 李 趙 陳 5 名同學 已知張 王為物理組成員 張 李 趙為化學組成員 李 趙 陳為生物組成員 如 果要在 3 個小組分別選出 3 位組長 一位同學最多只能擔任一個小組的組長 共有 種選擇方案 20 尋找假幣 現(xiàn)有 80 枚硬幣 其中有一枚是假幣 其重量稍輕 所有真幣的重量都相 同 如果使用不帶砝碼的天平稱重 最少需要稱幾次 就可以找出假幣 你還要指出 第 1 次的稱重方法 請寫出你的結果 21 取石子游戲 現(xiàn)有 5 堆石子 石子數(shù)依次為 3 5 7 19 50 甲乙兩人輪流從任一 堆中任取 每次只能取自一堆 不能不取 取最后一顆石子的一方獲勝 甲先取 問甲有沒有獲勝策略 即無論乙怎樣取 甲只要不失誤 都能獲勝 如果有 甲第 一步應該在哪一堆里取多少 請寫出你的結果 答案 1 四色球在盒子中放置的情況為 4 1234 黑紅白黃 推理過程是 4 假定 黑為 1 黃為 2 黑為 2 白為 3 紅為 2 白為 4 黃為 4 2 列出的算法是 K 0 FOR i 0 TO 10 DO K K 50 I 5 DIV 2 1 ENDFOR 3 能 例如 A D C E A F C B A 不能 本題的回答要點如下 要到達 D E F B 四個點之一 必須由 A C 出發(fā)才可 因為 A C 只可能出發(fā)一次 所以這樣的通路不存在 4 a 當 n MOD 3 1 時 a2 當 n MOD 3 1 時 a2 當 n MOD 3 2 時 a 當 n MOD 3 2 時 a3 當 n MOD 3 0 時 a3 當 n MOD 3 0 時 5 當 K 3 a1 a2 ak為 a1 3 a2 3 a3 1 時 對數(shù)列 122232 n2 A 成立 6 讀過 a 的人數(shù)是 12 人 2 一本書也沒讀過的人數(shù)是 30 人 7 度為 1 的子目錄有 9 個 8 給出 n 之后 X 與 n 之間的關系表達式為 N2 N 1 9 對給出的任意一個 n n 0 用 F n 表示其鋪法的總數(shù)的遞推公式為 F 1 1 F 2 2 F n F n 2 F n 1 n 3 10 在 a b c d e f 六件物品中 按條件能選出的物品