全國計算機等級考試四級試題(一)

1、20XX年全國計算機等級考試四級試題(一)一、選擇題:(共90題,分為1分題和2分題,滿分120分。除標(biāo)注2分題外,其它均為1分題。)(1)若或非門的輸入變量為A和B,輸出變量為Y,則A和B分別為下述哪一種情況時,Y才為1?A)1,0B)0,1C)0,0D)1,1已知寄存器A存有帶符號整數(shù)且只作算術(shù)移位,HA和LA分別代表其最高位和最低位。寄存器B存有帶符號整數(shù)且只作邏輯移位，HB和LB分別代表其最高位和最低位。當(dāng)寄存器A與B都有左移位發(fā)生時,下述哪一個命題是正確的?(2分)A)LA與LB均成為0B)LA與LB均成為1C)LA變成0但LB保持原值D)LA保持原值但LB的值改變下述哪一種情況稱為

2、指令周期?取指令時間B)取操作數(shù)時間C)取指令和執(zhí)行指令的時間D)存儲操作結(jié)果的時間(4)設(shè)S是一個至少有兩個元素的集合，且定義運算X*Y=X適用于S集中的所有元素X和Y,下列命題中哪一個命題必是真命題？I.*在S集中是可結(jié)合的n.*在S集中是可交換的田.*在S集中有單位元A)只有iB)只有nC)環(huán)口田D)呼口m(5)設(shè)Z是整數(shù)集，且設(shè)f:ZXZ-對每一個GZXZ有f(尸m2n。集合0的原象為(2分)A)0XZZx0C)(0 xZ)n(Zx0)D)(0XZ)U(ZX0)對于一個只有3個不同元素的集合A來說,A上的等價關(guān)系的總數(shù)為A)2B)5C)9D)取決于元素是否為數(shù)值(7)設(shè)有命題：對于組成

3、元素為集合的集合C存在函數(shù)為f:C-U豉得對每一個SGC,有f(S)GS該命題的否命題是A)對于集合C,對每個函數(shù)f:C-UC每一個SGC,都有f(S)SB)對于集合C,存在函數(shù)f:C-U或?qū)γ恳粋€SGC,有f(S)tSC)對于集合C,對每一個函數(shù)f:C-U踞在SGC,使得f(S)ESD)對于集合C,不存在函數(shù)f:C-U笊對某些SGC,沒有f(S)S(8)設(shè)(V,E用一連通白無圈圖，V包含3個3度頂點2個2度頂點r個1度頂點且V不再包含其他元素。E的元素個數(shù)為多少?(2分)A)6B)9C)15-rD)5+5r設(shè)連通圖G的頂點數(shù)與邊數(shù)與一立方體相同,即有8個頂點和12條邊。任意一棵G的生成樹的總

4、邊數(shù)為 TOC o 1-5 h z A)7B)8C)9D)10(10)設(shè)圖G的頂點為五邊形P的頂點,其邊為P的邊加上另一條連接P的兩個不相鄰頂點的邊。下列命題中哪個(或哪些)命題是真命題?I.G中存在歐拉回路n.G中存在哈密爾頓回路A)均不是B)只有IC)只有nD)I和II第11-13題是在已知下述Pascal程序的基礎(chǔ)上，并設(shè)在程序執(zhí)行過程中無錯誤發(fā)生。forh:=1ton-1dobeginx:=Ah+1;k:=h;while(k=1)and(Akx)dobeginAk+1:=Ak;k:=k-1end;Ak+1:=xend;假設(shè)在程序開始執(zhí)行時,數(shù)組A1.n是一個已排好序的遞增序列。下列答案

5、中,哪一個最好地描述了程序的執(zhí)行時間(運行時間階數(shù))?A)O(log2n)B)O(n)C)O(nlog2n)D)O(n2)假設(shè)在程序開始執(zhí)行時,數(shù)組A1.n是一組隨機整數(shù)。下列答案中,哪一個最好地描述了最差情況下的程序執(zhí)行時間(運行時間階數(shù))?A)O(log2n)B)O(n)C)O(nlog2n)D)O(n2)上述程序算法的標(biāo)準(zhǔn)名稱是起泡排序法B)插入排序法C)選擇排序法D)快速排序法(14)下面關(guān)于B樹和B+樹的敘述中，不正確的結(jié)論是A)B樹和B+樹都是平衡的多分樹B樹和B+樹都可用于文件的索引結(jié)構(gòu)B樹和B+樹都能有效地支持順序檢索B樹和B+樹都能有效地支持隨機檢索第(15)-(16)題基于下面的敘述:某二叉樹結(jié)點的對稱序序列為A,B,C,D,E,F,GW序序列為B,D,C,A,F,G,E該二叉樹結(jié)點的前序序列為(2分)A)E,G,F,A,