NOIP2010(帕斯卡改進小組)
壹、多項選擇題
1.10十進制數相當於16十進制數A1.2是()。
a . 101.2 b . 111.4 c . 161.125d . 177.25
2.壹個字節由()二進制組成。
A.8B.16 C.32 D .以上都有可能。
3.下列邏輯表達式的值始終為真()。
A.P∨(┓P∧Q)∨(┓P∧┓Q)
B.Q∨(┓P∧Q)∨(P∧┓Q)
C.P∨Q∨(P∧┓Q)∨(┓P∧Q)
D.P∨┓Q∨(P∧┓Q)∨(┓P∧┓Q)
4.4下可執行文件的默認擴展名。Linux是()。
A.exeb.com.dll.d .以上都不是。
5.如果方程7*7=41在某個系統中成立，那麽方程12*12=()在這個系統中也成立。
A.b . 100 c . 164d . 196
6.提出計算機“存儲程序”工作原理的是()。
A.克勞德？香農. b .戈登。摩爾·查爾斯？巴比克·馮？諾伊曼
7.前綴表達式“+3 * 2+5 12”的值是()。
A.23 B. 25 C. 37 D. 65
8.主存的訪問速度比中央處理器(CPU)的工作速度慢很多，影響了後者的效率。根據局部性原理，CPU訪問的存儲單元通常傾向於在壹個連續的小區域內。因此，為了提高整個系統的執行效率，在CPU中引入了()。
A.寄存器b .緩存c .閃存d .外部存儲器
9.完全二叉樹的順序存儲方案是指將完全二叉樹的節點按照從上到下、從左到右的順序結構存儲在壹個數組中。假設根節點存儲在數組的位置1，節點K的父節點如果存在，應該存儲在數組的位置()。
A.2kb.2k+1 C.K./2，輪D. (k+1)/2。
10.下列比賽中歷史最悠久的是()。
A.NOIP·NOI·IOI·APIO
二、不定選擇題
1.元素R1、R2、R3、R4和R5按照R1、R2、R3、R4和R5的順序堆疊。如果第1個是R3，那麽第5個可能是()。
A.R2 R4 R5
2.Pascal語言、C語言、C++語言都屬於()。
A.高級語言b .自然語言c .解釋語言d .編譯語言
3.就地排序是指輔助空間(除了存儲要排序的元素)的大小與數據大小無關的壹種排序算法。下列屬於原位排序的有()。
A.冒泡排序b .插入排序c .基數排序d .選擇排序
4.在整數的補碼表示法中，下列說法正確的是()。
A.只有負整數的最高編碼位是1。
b .編碼位數確定後，所能表示的最小整數和最大整數的絕對值相同。
C.整數0只有壹個唯壹代碼。
D.用補碼表示的兩個數相加時，如果在最高有效位產生進位，則表示運算溢出。
5.如果二叉樹的前序遍歷序列是ABCDEFG，後序遍歷序列是CBFEGDA，那麽根節點的左子樹中的節點數可能是()。
A0 b . 2 c . 4d . 6
6.在下面的HTML語句中，能正確生成NOI官方網站超鏈接的是()。
A.& lta URL = " h t t p://w w w w n o I . c n " >歡迎來到NOI網站
B.& lta href = " h t t p://w w w n o I . c n " >歡迎來到NOI網站
C.& lta & gth t t p://w w w w n o I . c n & lt；/a & gt；
D.& lt壹個名稱" h t t p://w w w n o I c n " >歡迎來到NOI網站
7.關於拓撲排序，下列說法正確的是()。
A.所有連通有向圖都可以實現拓撲排序。
b對於同壹個圖，拓撲序的結構是唯壹的。
C.在拓撲排序中，入度為0的節點總是排在入度大於0的節點之前。
D.拓撲排序結果序列中的第壹個節點必須是入度大於0的點。
8.平面的法線是指垂直於該平面的直線。平面通過點(1，1，1)，(0，3，0)，(2，0，0)的法線是()。
A.通過點(1，1，1)和(2，3，3)的直線
B.通過點(1，1，1)和(3，2，1)的直線
C.通過點(0，3，0)和(-3，1，1)的直線
D.通過點(2，0，0)和(5，2，1)的直線
9.鏈表中有兩個指針字段llink和rlink，分別指向節點的前任和繼任者。設p指向鏈表中的壹個節點，其左右節點非空。現在需要刪除節點P，那麽下面的語句順序是正確的
( )。
a . p-& gt；rlink-& gt；llink = p-& gt；rlink
p->；llink-& gt；rlink = p-& gt；llink刪除p；
b . p-& gt；llink-& gt；rlink = p-& gt；rlink
p->；rlink-& gt；llink = p-& gt；llink刪除p；
C.p->rlink-& gt；llink = p-& gt；llink
p->；rlink-& gt；llink-& gt；rlink = p-& gt；rlink刪除p；
D.p->llink-& gt；rlink = p-& gt；rlink
p->；llink-& gt；rlink-& gt；link = p-& gt；llink刪除p；
10.今年(2010)發生的事件有()。
A.惠普實驗室的研究員Vinay Deolalikar聲稱已經證明了P≠NP。
B.英特爾收購了電腦安全軟件公司McAfee。
C.蘋果發布iPhone 4手機。
D.微軟發布Windows 7操作系統。
第三，解決問題
1.LZW編碼是壹種自適應字典編碼。在編碼的過程中，最開始只有壹個基本結構元素的編碼字典。如果在編碼過程中遇到新條目，該條目和新代碼將被添加到字典中，並用於編碼後續信息。
例如，考慮壹個要編碼的信息字符串:“xyx yy yy xyx”。初始字典只有三個詞條，第壹個是X，代碼是1；第二個是y，代碼是2；第三個是空格，編碼為3；因此，字符串“xyx”的代碼是1-2-1(其中-是代碼分隔符)，它後面的壹個空格是1-2-1-3。但是因為有壹個空格，我們知道前面的“xyx”是壹個單詞，又因為這個單詞不在字典裏，我們可以自適應的把這個詞條加入字典，編碼為4，然後按照新的字典對後續的信息進行編碼，以此類推。於是，最終得到代碼:1-2-1-3-2-2-3-5-3-4。
我們可以看到信息被壓縮了。壓縮後的信息傳輸給接收方，接收方根據基本字典就可以完成序列的完全恢復。解碼過程是編碼過程的反向操作。現在已知初始字典中的三個詞條如上所述，接收方接收到的編碼信息為2-2-1-2-3-1-3-4-3-1-2-1-3-5-3-6。
2.無向圖G有七個頂點。如果沒有由奇邊組成的簡單環，它最多有_ _ _ _ _ _ _ _ _條邊。
3.記住T是壹個隊列，開頭是空的，現有的n個總數不超過32的正整數依次放入隊列。如果不管這些數是什麽，我們都能找到壹種出隊列的方法使得某壹時刻隊列T中的數之和正好是9，那麽n的最小值就是_ _ _ _ _ _ _ _ _。
第四，閱讀程序寫出結果
1.
常數
size = 10；
定義變量
I，j，cnt，n，m:整數；
數據:數組[1..size]的整數；
開始
readln(n，m)；
對於i := 1到n do
read(data[I])；
對於i := 1到n do
開始
CNT:= 0；
對於j := 1到n do
if(data[I]& lt；data[j])或((data[j] = data[i])和(j & lt我))
然後是Inc(CNT)；
如果cnt = m
然後writeln(data[I])；
結束；
結束。
投入
5 2
96 -8 0 16 87
輸出:_ _ _ _ _ _ _ _ _
2.
常數
size = 100；
定義變量
na，nb，I，j，k:整數；
a，b:數組[1..size]的整數；
開始
readln(na)；
對於i := 1到na do
讀(a[I])；
readln(nb)；
for i := 1 to nb do
讀作(b[I])；
I:= 1；
j:= 1；
while(我& lt= na)和(j & lt= nb) do
開始
如果a[I]& lt；= b[j]那麽
開始
寫(a[i]，' ')；
inc(壹)；
結束
否則開始
寫(b[j]，' ')；
Inc(j)；
結束；
結束；
如果我& lt=那na呢
對於k := i到na do
寫(a[k]，' ')；
如果j & lt那麽= nb
對於k := j到nb do
寫(b[k]，' ')；
結束。
投入
五
1 3 5 7 9
四
2 6 10 14
輸出:_ _ _ _ _ _ _ _ _
3.
常數
num = 5；
定義變量
n:整數；
函數r(n:整數) :整數；
定義變量
I:整數；
開始
如果n & lt= num then
開始
r:= n；
退出；
結束；
對於i :=1到num do
如果r(n-I)& lt；那麽0
開始
r:= I；
退出；
結束；
r:=-1；
結束；
開始
readln(n)；
writeln(r(n))；
結束。
輸入16
輸出:_ _ _ _ _ _ _ _ _
4.
常數
size = 100；
定義變量
n，m，x，y，I:整數；
r: array[1..size]的整數；
映射:數組[1..尺寸，1..大小]的布爾值；
找到:布爾型；
函數成功:布爾型；
定義變量
I:整數；
開始
對於i :=1到n do
如果不是映射[r[i]][r[i mod n + 1]]
那麽開始吧
成功:=假；
退出；
結束；
成功:=真；
結束；
過程交換(var a，b:整數)；
定義變量
t:整數；
開始
t:= a；
a:= b；
b:= t；
結束；
procedure perm(左、右:整數)；
定義變量
I:整數；
開始
如果找到
然後退出；
如果離開& gt正確
那麽開始吧
如果成功
那麽開始吧
對於i := 1到n do
writeln(r[i]，' ')；
發現:=真；
結束；
退出；
結束；
對於i:=從左到右做
開始
swap(r[left]，r[I])；
燙發(左+ 1，右)；
swap(r[left]，r[I])；
結束；
結束；
開始
readln(n，m)；
fillchar(map，sizeof(map)，false)；
對於i := 1到m do
開始
readln(x，y)；
map[x][y]:= true；
map[y][x]:= true；
結束；
對於i := 1到n do
r[I]:= I；
發現:=假；
perm(1，n)；
如果找不到
然後writeln('無解決')；
結束。
輸入:
9 12
1 2
2 3
3 4
4 5
5 6
6 1
1 7
2 7
3 8
4 8
5 9
6 9
輸出:_ _ _ _ _ _ _ _ _
動詞 （verb的縮寫）改進程序
1.(過河)壹個月的壹個漆黑的夜晚，壹群人在河的右岸，試圖通過唯壹的木橋走到河的左岸。在黑暗中，過橋時，他們不得不用燈照明。不幸的是，他們只有壹盞燈。另外，木橋最多能承受兩個人同時通過，否則就會倒塌。每個人都獨自走過獨木橋。不同的人可能需要不同的時間。兩個人壹起過獨木橋，因為只有壹盞燈，所以需要的時間就是慢壹點的人獨自過橋的時間。現在輸入n (2
比如有三個人，A，B，C，他們單獨過橋的時間是1.24，那麽總的最少需要時間是7。具體方法是:A和B壹起過橋到河的左岸，A獨自返回河的右岸帶回燈光，然後A和C壹起過橋到河的左岸，總時間為2+65，438+0+4。
常數
SIZE = 100；
無窮大= 10000；
左=真；
右=假；
左向右=真；
RIGHT _ TO _ LEFT = false
定義變量
n，I:整數；
時間:數組[1..Size]的整數；
位置:數組[1..大小]的布爾值；
函數max(a，b :integer):整數；
開始
如果a & gtb那麽
最大:= a
其他
max:= b；
結束；
函數go(stage : boolean):整數；
定義變量
I，j，num，tmp，ans:整數；
開始
if (stage =從右向左)
那麽開始吧
num:= 0；
ans:= 0；
對於i := 1到n do
如果pos[i] = Rignt，則
開始
inc(數字)；
如果時間[I]& gt；然後回答
ans:= time[I]；
結束；
如果__________，那麽
開始
go:= ans；
退出；
結束；
ans :=無窮大；
對於i := 1至n–1 do
如果pos[i] = RIGHT，那麽
對於j := i+1到n do
如果pos[j] = RIGHT，那麽
開始
pos[I]:= LEFT；
pos[j] :=左；
tmp := max(time[i]，time[j])+_ _ _ _ _ _ _；
如果tmp & lt然後回答
ans:= tmp；
pos[i] :=右；
pos[j]:= RIGHT；
結束；
go:= ans；
結束
else if (stage =從左到右)
那麽開始吧
ans :=無窮大；
對於i := 1到n do
如果_______那麽
開始
pos[i] :=右；
tmp:= _ _ _ _ _ _ _ _；
如果tmp & lt然後回答
ans:= tmp；
_________;
結束；
go:= ans；
結束
else go:= 0；
結束；
開始
readln(n)；
對於i := 1到n do
開始
read(time[I])；
pos[i] :=右；
結束；
writeln(go(RIGHT _ TO _ LEFT))；
結束。
NOIP2010提高小組參考答案和評分標準(Pascal語言)
壹、單項選擇題(* * 10題，每題1.5分，* * 15分)
1 2 3 4 5 6 7 8 9 10
C A A D B D C B C B
二、不定選擇題(* * 10題，每題1.5分，* * * 15分，多選或少選不計分)
1 2 3 4 5 6 7 8 9 10
ACD AD ABD AC B B D D BCD ABC
三、解題(***3題，每題5分，* * * 15分)
1.yyxy xx yyxy xyx xx xyx
2.12
3.18
四、閱讀程序寫結果(***4題，每題7分，28分作***)
1.16
2.1 2 3 5 6 7 9 10 14
3.4
4.1 6 9 5 4 8 3 2 7
五、完善程序(1空2分，其余10空，每空2.5分，* * * 27分)
(註意:在下面的過程中可能有壹些等價的填空方法。各省可以請自己的專家在電腦上審核，不壹定要報科委審核。)
1.①數量& lt= 2(或數字
②走(從左到右)
③位置[i] =左(或左=位置[i])
④ time[i]+go(從右向左)(或go(從右向左)+time[i])
⑤位置[i] :=左側
在這個問題中，LEFT可以替換為true，LEFT_TO_RIGHT可以替換為true，RIGHT_TO_LEFT可以替換為false。
2.① opt[k]
② home[r] := k
③ j := i+i(或j := 2 * i或j := i * 2)
④ swap(i，j)(或swap(j，I))
⑤值[i]+堆[1](或堆[1]+值[I])
⑥即時通訊