數(shù)據(jù)結(jié)構(gòu)一、單項選擇題1.在帶有頭結(jié)點的單鏈表HL中，要向表頭插入一個由指針p指向的結(jié)點，則執(zhí)行A.p->next=HL->next;HL->next=p;B.p->next=HL;HL=p;C.p->next=HL;p=HL;D.HL=p;p->next=HL;2.對線性表，在下列情況下應(yīng)當采用鏈表表示。A.經(jīng)常需要隨機地存取元素;B.經(jīng)常需要進行插入和刪除操作;C.表中元素需要占據(jù)一片連續(xù)的存儲空間;D.表中元素的個數(shù)不變;3.快速排序在最壞情況下的時間復雜度為。A．O(log2n)B．O(nlog2n)C．0(n)D．0(n2)4.若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素放A[1]中，現(xiàn)進行二分查找，則查找到A［3］元素經(jīng)過比較的數(shù)組下標依次為。A.1，2，3 B.9，5，2，3C.9，5，3 D.9，4，2，35.對于線性表（7，34，55，25，64，46，20，10）進行散列存儲時，若選用H（K）=K%9作為散列函數(shù)，則散列地址為1的元素有個。A．1B．2C．3D．46.設(shè)有6個結(jié)點的無向圖，該圖至少應(yīng)有條邊才能確保是一個連通圖。A.5B.6C.7D.87.設(shè)一組權(quán)值集合W=(15，3，14，2，6，9，16，17)，要求根據(jù)這些權(quán)值集合構(gòu)造一棵哈夫曼樹，則這棵哈夫曼樹的帶權(quán)路徑長度為。 A129B219C189D2298.設(shè)哈夫曼樹中的葉子結(jié)點總數(shù)為m，若用二叉鏈表作為存儲結(jié)構(gòu)，則該哈夫曼樹中總共有個空指針域。A2m-1 B2m C2m+1 D4m9.若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復雜度為(1≤i≤n+1)。A.O(log2n)

B.O(1)

C.O(n)

D.O(n2)10.若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，rear和front的值分別為多少。A．1和5B.2和4C．4和2D.5和111.若有18個元素的有序表存放在一維數(shù)組A[19]中，第一個元素存放于A[1]中，現(xiàn)進行折半查找，則查找到A[3]元素經(jīng)過比較的數(shù)組下標依次為。A.1，2，3 B.9，5，2，3C.9，5，3 D.9，4，2，312.若有向圖G的拓撲序列中頂點Vi在頂點Vj之前，則下列情形不可能出現(xiàn)的是。

A.G中有一條從Vj到Vi的路徑

B.G中有弧<Vi，Vj>C.G中有一條從Vi到Vj的路徑

D.

G中沒有弧<Vi,Vj>13.下面關(guān)于求關(guān)鍵路徑的說法不正確的是。

A．求關(guān)鍵路徑是以拓撲排序為基礎(chǔ)的；

B．一個事件的最早開始時間與以該事件為尾的弧的活動最早開始時間相等；

C．一個事件的最遲開始時間為以該事件為尾的弧的活動最遲開始時間與該活動的持續(xù)時間的差；D．關(guān)鍵活動一定位于關(guān)鍵路徑上；二、填空題1.設(shè)某無向圖中頂點數(shù)和邊數(shù)分別為n和e，所有頂點的度數(shù)之和為d，則e=。2.設(shè)一棵二叉樹的前序序列為ABC，則有種不同的二叉樹可以得到這種序列。3.設(shè)查找表中有100個元素，如果用二分法查找方法查找數(shù)據(jù)元素X，則最多需要比較次就可以斷定數(shù)據(jù)元素X是否在查找表中。4.設(shè)有向圖G中有向邊的集合E={<1，2>，<2，3>，<1，4>，<4，2>，<4，3>}，則該圖的一種拓撲序列為。5.設(shè)指針變量p指向單鏈表中結(jié)點A，指針變量s指向被插入的結(jié)點X，則在結(jié)點A的后面插入結(jié)點X需要執(zhí)行的語句序列：s->next=p->next;。6.設(shè)一棵完全二叉樹的第三層上有2個葉子結(jié)點，則有種不同的完全二叉樹符合此種情況。7.用S表示入棧操作，X表示出棧操作，若元素入棧的順序為1234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為。8.一棵完全二叉樹上有1001個結(jié)點，其中葉子結(jié)點的個數(shù)是。9.在一個以head為頭指針的單循環(huán)鏈表中，p

指針指向鏈尾結(jié)點的條件是（8）。三、判斷題(錯誤打“×”，正確打“√”)1.調(diào)用一次深度優(yōu)先遍歷可以訪問到圖中的所有頂點。()2.已知一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（）3.層次遍歷初始堆可以得到一個有序的序列。（）4.將一棵樹T轉(zhuǎn)化成二叉樹，則該二叉樹中一定沒有右子樹。（）5.如果某個有向圖的鄰接表中第i條單鏈表為空，則第i個頂點的出度為零。（）6.在一棵二叉樹中，除葉結(jié)點外，假定其余每個結(jié)點都只有左孩子，沒有右孩子，則對它分別進行中序遍歷和后序遍歷，會得到相同的結(jié)果。()7.用鄰接矩陣法存儲一個圖所需的存儲單元數(shù)目與圖的邊數(shù)有關(guān)。()8.查找相同結(jié)點的效率折半查找總比順序查找高。()9.線性表的特點是每個元素都有一個前驅(qū)和一個后繼。()10.快速排序算法在最好情況下的時間復雜度為O(N)。()

計算機組成原理一、單項選擇題1、DRAM存儲器的中文含義是_____。

A、靜態(tài)隨機存儲器B、靜態(tài)只讀存儲器

C、動態(tài)隨機存儲器D、動態(tài)只讀存儲器2、微型計算機的運算器、控制器及內(nèi)存存儲器的總稱是_____。A、CPU

B、MPU

C、主機D、ALU3、硬盤連同驅(qū)動器是一種_____。

A、內(nèi)存儲器B、半導體存儲器

C、只讀存儲器D、外存儲器4、在內(nèi)存中，每個基本單位都被賦予一個唯一的序號，這個序號稱之為_____。A、容量B、編號

C、字節(jié)D、地址5、在下列存儲器中，訪問速度最快的是_____。

A、硬盤存儲器B、磁帶存儲器

C、半導體RAM(內(nèi)存儲器)D、軟盤存儲6、半導體只讀存儲器(ROM)與半導體隨機存儲器(RAM)的主要區(qū)別在于_____。A、ROM可以永久保存信息，RAM在掉電后信息會丟失B、RAM是內(nèi)存儲器，ROM是外存儲器C、ROM掉電后，信息會丟失，RAM則不會D、ROM是內(nèi)存儲器，RAM是外存儲器7、計算機存儲器是一種_____。A、輸出部件B、輸入部件

C、運算部件D、記憶部件

8、計算機中存儲數(shù)據(jù)的最小單位是_____。A、位B、字

C、字節(jié)D、字長9、微型計算機的微處理器包括_____。A、CPU和存儲器B、運算器和累加器

C、CPU和控制器D、運算器和控制器10、微型計算機的性能主要由微處理器的_____決定。A、質(zhì)量B、價格性能比

C、CPUD、控制器

11、一般用微處理器的_____進行分類。A、字長B、價格

C、性能D、規(guī)格

12、一臺微型計算機的字長為4個字節(jié)，它表示_____。A、能處理的字符串最多為4個ASCⅡ碼字符B、能處理的數(shù)值最大為4位十進制數(shù)9999C、在CPU中運算的結(jié)果為8的32次方D、在CPU中作為一個整體加以傳送處理的二進制代碼為32位13、微機的性能指標中的內(nèi)存容量是指_____。A、軟盤的容量B、RAM和ROM的容量

C、RAM的容量D、ROM的容量14、在下面關(guān)于計算機系統(tǒng)硬件的說法中，不正確的是_____。A、當關(guān)閉計算機電源后，RAM中的程序和數(shù)據(jù)就消失了B、CPU主要由運算器、控制器和寄存器組成C、軟盤和硬盤上的數(shù)據(jù)均可由CPU直接存取D、軟盤和硬盤驅(qū)動器既屬于輸入設(shè)備，又屬于輸出設(shè)備15、下面關(guān)于ROM的說法中，不正確的是_____。A、ROM是只讀存儲器的英文縮寫

B、ROM中的內(nèi)容在斷電后不會消失C、CPU不能向ROM隨機寫入數(shù)據(jù)

D、ROM是只讀的，所以它不是內(nèi)存而是外存16、光盤驅(qū)動器通過激光束來讀取光盤上的數(shù)據(jù)時，光學頭與光盤_____。

A、播放VCD時接觸B、不直接接觸

C、直接接觸D、有時接觸有時不接觸17、下列有關(guān)存儲器讀寫速度的排列，正確的是_____。

A、Cache>硬盤>RAM>軟盤

B、Cache>RAM>硬盤>軟盤

C、RAM>Cache>硬盤>軟盤

D、RAM>硬盤>軟盤>Cache18、使用Cache可以提高計算機運行速度，這是因為_____。

A、Cache增大了內(nèi)存的容量B、Cache可以存放程序和數(shù)據(jù)

C、Cache縮短了CPU的等待時間D、Cache擴大了硬盤的容量19、運算器的組成部分不包括_____。

A、控制線路B、譯碼器

C、寄存器D、加法器20、把內(nèi)存中的數(shù)據(jù)傳送到計算機的硬盤，稱為_____。A、顯示B、輸入

C、讀盤D、寫盤21、用MIPS為單位來衡量計算機的性能，它指的是計算機的_____。

A、傳輸速率B、存儲器容量

C、字長D、運算速度22、微型計算機存儲器系統(tǒng)中的Cache是_____。A、只讀存儲器 B、高速緩沖存儲器 可編程只讀存儲器 D、可擦除可再編程只讀存儲器23、計算機斷電后，再次通電也不能恢復的是。ROM和RAM中的信息B、RAM中的信息C、ROM中的信息D、硬盤中的信息24、下列選項中，存儲容量相等的是_____。A、1MB與1000B B、1KB與1024bC、1GB與1024MB D、1GB與1024Mb25、關(guān)于存儲容量單位的描述，正確的是。A、1MB=1000KBB、1MB=1024BC、1GB=1024KBD、1MB=1024KB26、下列存儲器中，斷電后信息不會丟失的是。Ａ、DRAMＢ、CACHEＣ、SRAMＤ、EPROM27、32位微機中的32是指該微機。Ａ、能同時處理32位二進制數(shù)Ｂ、運算精度可達小數(shù)點后32位Ｃ、具有32根地址線Ｄ、能同時處理32位十進制數(shù)28、數(shù)據(jù)總線用于在各器件、設(shè)備之間傳送信息，以下說法中錯誤的是。Ａ、數(shù)據(jù)總線線數(shù)與機器字長一致Ｂ、數(shù)據(jù)總線是雙向總線Ｃ、數(shù)據(jù)總線是用來傳輸數(shù)值型數(shù)據(jù)Ｄ、數(shù)據(jù)總線通常是指外部總線29、下列存儲器中，存儲容量最大的是。Ａ、軟磁盤存儲器Ｂ、硬磁盤存儲器Ｃ、光盤存儲器Ｄ、內(nèi)存儲器30、微型計算機中，控制器的基本功能是。Ａ、存儲各種控制信息Ｂ、傳輸各種控制信號Ｃ、產(chǎn)生各種控制信息Ｄ、從內(nèi)存取指令和執(zhí)行指令31、微機存儲系統(tǒng)中配置高速緩沖存儲器的目的是為了解決。Ａ、主機與外設(shè)之間速度不匹配問題Ｂ、CPU與輔助存儲器之間速度不匹配問題Ｃ、CPU與內(nèi)存儲器之間速度不匹配問題Ｄ、內(nèi)存儲器與輔助存儲器之間速度不匹配問題32、下列存儲器中，為了不丟失信息需要進行周期性刷新的是。Ａ、磁盤存儲器B、DRAMC、CD-ROMＤ、ROM33、計算機的硬件系統(tǒng)是指____。Ａ、控制器,運算器Ｂ、存儲器,控制器Ｃ、接口電路,I/O設(shè)備Ｄ、A,B,C合起來34、在計算機中訪問速度最快的存儲器是____。Ａ、硬盤Ｂ、磁帶Ｃ、RAMＤ、軟盤35、微型計算機的結(jié)構(gòu)原理采用總線結(jié)構(gòu)，系統(tǒng)總線分為。Ａ、時序總線、運算總線Ｂ、內(nèi)部總線、外部總線Ｃ、連接總線、邏輯總線Ｄ、網(wǎng)絡(luò)總線、邏輯總線36、隨機存儲器RAM中的信息可以隨時讀出或?qū)懭?，當讀出RAM中的信息時______。A、破壞RAM中原有信息B、釋放該信息占用的RAM單元C、RAM中的內(nèi)容全部清0D、RAM原有信息保持不變37、在計算機系統(tǒng)中，外存儲器必須通過______才能實現(xiàn)與主機的信息交換。A、電纜B、總線插槽C、接口D、插座38、CPU中的可存放少量數(shù)據(jù)。A、存儲器B、輔助存儲器C、寄存器D、只讀存儲器39、CPU不能直接訪問的存儲器是。A、ROMB、RAMC、CacheD、DVD-ROM40、磁盤緩沖區(qū)位于。A、主存儲器內(nèi)B、I/O接口內(nèi)C、磁盤存儲器內(nèi)Ｄ、I/O設(shè)備內(nèi)41、地址總線是傳送地址信息的一組線，下面正確的是。A、用來選擇信息傳送的對象B、控制CPU讀/寫內(nèi)存信息C、一根地址線傳送一個地址D、20根地址線能尋址范圍為64KB42、計算機中對數(shù)據(jù)進行加工與處理的部件稱為。 A、運算器 B、控制器 C、顯示器 D、存儲器43、下列簡寫中，不代表擴展插槽類型的是。 A、IDE B、ISA C、PCI D、AGP44、系統(tǒng)總線用于實現(xiàn)之間的連接； A、芯片級B、插件板級C、主板上各大部件D、Cache與內(nèi)存45、對于輔助存儲器，的說法是正確的。

A、不是一種永久性的存儲設(shè)備 B、能永久地保存信息，是文件的主要存儲介質(zhì)

C、可被中央處理器直接訪問 D、是CPU與主存之間的緩沖存儲器46、計算機在執(zhí)行U盤上的程序時，首先把U盤上的程序和數(shù)據(jù)讀入到，然后才能被才能被計算機運行。A、軟盤B、內(nèi)存C、硬盤D、緩存47、I/O接口位于_____。

A、主機和I/O設(shè)備之間B、主機和總線之間

C、總線和I/O設(shè)備之間D、CPU與存儲器之間48、基于馮·諾依曼提出的存儲程序控制原理的計算機系統(tǒng)，其硬件基本結(jié)構(gòu)包括：、控制器、存儲器、輸入設(shè)備和輸出設(shè)備。A、運算器B、顯示器C、鍵盤D、鼠標49、某處理器具有32GB的尋址能力，則該處理器的地址線有。A、36根B、35根C、32根D、33根50、外存中的文件必須讀入后計算機才能進行處理。A、ROMB、RAMC、CacheD、CPU51、I/O操作的任務(wù)是將輸入設(shè)備輸入的信息送入主機，或者將主機中的內(nèi)容送到輸出設(shè)備。下面關(guān)于I/O操作的敘述中錯誤的是。A、PC機中CPU通過執(zhí)行輸入指令和輸出指令向I/O控制器發(fā)出啟動I/O操作的命令，并負責對I/O設(shè)備進行全程控制。B、I/O設(shè)備的種類多，性能相差很大，與計算機主機的連接方法也各不相同。C、為了提高系統(tǒng)的效率，I/O操作與CPU的數(shù)據(jù)處理操作通常是并行進行的。D、多個I/O設(shè)備可以同時進行工作。52、漢字系統(tǒng)中的漢字字庫里存放的是漢字的_____。A、機內(nèi)碼B、國標碼

C、字形碼D、輸入碼53、計算機中的機器數(shù)有三種表示方法，下列_____不是。

A、原碼B、反碼

C、補碼D、ASCII54、在計算機內(nèi)部用機內(nèi)碼而不用國標碼表示漢字的原因是_____。A、有些漢字的國標碼不唯一，而機內(nèi)碼唯一

B、在有些情況下，國標碼有可能造成誤解C、機內(nèi)碼比國標碼容易表示

D、國標碼是國家標準，而機內(nèi)碼是國際標準55、將二進制數(shù)11011101轉(zhuǎn)化成十進制是_____。A、220B、221

C、251D、321

56、將(10.10111)2轉(zhuǎn)化為十進制數(shù)是_____。A、2.78175B、2.71785

C、2.71875D、2.81775

57、將十進制數(shù)215轉(zhuǎn)換成二進制8進制數(shù)是_____。A、(327)8B、(268.75)8

C、(352)8D、(326)858、與十六進制數(shù)(BC)等值的二進制數(shù)是_____。

A、10111011B、10111100

C、11001100D、1100101159、下列字符中ASCII碼值最小的是_____。

A、AB、M

C、kD、a二、填空題1、運算器是由和組成。2、單片機是將CPU、和集成在一個芯片上的計算機。3、內(nèi)存讀寫信息是按為單位進行的；磁盤讀寫信息是按為單位進行的。4、如果一個計算機的CPU有20根地址總線，那么，它的最大內(nèi)存容量為MB。5、Cache存儲系統(tǒng)可以解決內(nèi)存的問題；虛擬存儲系統(tǒng)可以解決內(nèi)存的問題。6、PC機硬件在邏輯上主要由CPU、內(nèi)存、外存、I/O設(shè)備與等主要部件組成。7、當CPU從cache或主存取到一條將要執(zhí)行的指令后，立即進入操作。8、計算機所使用的I/O接口分成多種類型。從數(shù)據(jù)傳輸方式來看，有串行接口和接口。9、每一種不同類型的CPU都有自己獨特的一組指令，一個CPU所能執(zhí)行的全部指令稱為。三、判斷題1、給每個存儲單元的編號，稱為地址。2、總線由數(shù)據(jù)總線、地址總線和控制總線組成。3、CD-ROM利用表面的平和凹表示“0”和“1”。4、某計算機內(nèi)存容量為512KB，那么它的內(nèi)存地址寄存器需要19位二進制。5、計算機執(zhí)行一條指令需要的時間稱為指令周期。6、“存儲程序”原理是圖靈提出的。7、寄存器是內(nèi)存中的一種暫存機構(gòu)。8、鍵盤是PC機的標準輸入設(shè)備，缺少鍵盤的計算機就無法正常運行。9、計算機系統(tǒng)有硬件和軟件兩部分組成，其中只有硬件是必不可少的。10、I/O接口就是I/O設(shè)備與I/O總線之間的連接裝置。11、鍵盤上的Alt鍵只能與另一個字母鍵或功能鍵同時按下時才有作用。12、單擊鼠標左鍵后完成什么樣的操作是由操作系統(tǒng)決定的。13、顯示器的像素單元越多，則可允許設(shè)置的顯示分辨率就越高。

操作系統(tǒng)一、單項選擇題下列關(guān)于操作系統(tǒng)的論述中，正確的是。對批處理作業(yè)，必須提供相應(yīng)的作業(yè)控制信息對于分時系統(tǒng)，不一定全部提供人機交互功能從響應(yīng)角度看，分時系統(tǒng)與實時系統(tǒng)的要求相似由于采用了分時系統(tǒng)，用戶可以獨占計算機的文件系統(tǒng)關(guān)于并發(fā)，描述正確的是。多個CPU在同一時刻同時運行多個計算任務(wù)在同一時刻運行多個CPU同時運算同一個任務(wù)多個計算任務(wù)在同一時間間隔內(nèi)運行現(xiàn)代操作系統(tǒng)必須提供的功能是。GUI B．編輯源程序C．處理中斷D．編譯源程序用整型信號量實現(xiàn)生產(chǎn)者-消費者問題時，需要定義個信號量。A．1B.2C．3D．4下列的進程狀態(tài)變化中，_________轉(zhuǎn)換是不可能的。A．運行→就緒 B．運行→等待C．等待→運行 D．等待→就緒進程同步時的臨界區(qū)，指的是。A.一個區(qū)間 B.臨界資源C.互斥訪問 D.一段代碼下列信息中，不屬于PCB的內(nèi)容是。進程打開文件的描述符表進程調(diào)度信息程序段、數(shù)據(jù)段的內(nèi)存基址和長度完整的程序代碼以下關(guān)于管程的描述中錯誤的是。管程是進程同步工具，解決信號量機制中大量同步操作分散的問題管程每次只允許一個進程進入管程管程中signal操作的作用和信號量機制中的V操作相同管程是被進程調(diào)用的，管程是語法單位，無創(chuàng)建和撤銷假設(shè)就緒隊列中有10個進程，以時間片輪轉(zhuǎn)方式進行進程調(diào)度，時間片大小為300ms，CPU進行進程切換要花費10ms，這時系統(tǒng)開銷所占比率約為3%；若就緒隊列中進程個數(shù)增加到20個，其余條件不變，則系統(tǒng)開銷所占的比率將。增加B.減少C.不變D.無法判斷進程調(diào)度算法采用固定時間片輪