二級公共基礎(chǔ)知識第一部分 計算機(jī)系統(tǒng)附有答案

二級公共基礎(chǔ)知識第一部分計算機(jī)系統(tǒng)[復(fù)制]1.1概述[填空題]_________________________________1、下列關(guān)于馮·諾依曼結(jié)構(gòu)計算機(jī)硬件組成方式描述正確的是________。[單選題]*A、由運(yùn)算器、寄存器和控制器組成(正確答案)B、由運(yùn)算器、存儲器和控制器組成2、在計算機(jī)系統(tǒng)中，主機(jī)是指________。[單選題]*硬件系統(tǒng)(正確答案)硬件系統(tǒng)和軟件系統(tǒng)中央處理器和主存儲器D、配有操作系統(tǒng)的計算機(jī)答題解析：計算機(jī)的主機(jī)包括中央處理器（運(yùn)算器和控制器）和主存儲器。3、完整的計算機(jī)系統(tǒng)包括________。[單選題]*A、內(nèi)存與外存(正確答案)B、主機(jī)與外設(shè)1.2計算機(jī)硬件系統(tǒng)[填空題]_________________________________1、計算機(jī)完成一條指令花費(fèi)的時間成為一個________。[單選題]*A、執(zhí)行時序(正確答案)B、存取周期C、執(zhí)行速度D、指令周期答案解析：2、總線帶寬是指總線的________。[單選題]*長度(正確答案)數(shù)據(jù)傳輸率寬度D、位數(shù)答案解析：總線是連接計算機(jī)中各個部件的數(shù)據(jù)傳輸線，是各個部件共享的傳輸介質(zhì)?？偩€的性能指標(biāo)包括總線寬度（數(shù)據(jù)總線的根數(shù)）、總線帶寬（數(shù)據(jù)傳輸率）及時鐘同步/異步等。3、CPU芯片內(nèi)部鏈接各元件的總線是________。[填空題]*空1答案：A、系統(tǒng)總線B、外圍總線C、外部總線D、內(nèi)部總線正確芯片內(nèi)部鏈接各元件的總線稱為內(nèi)部總線。4、要使用外存儲器中的信息，應(yīng)先將其調(diào)入________。[單選題]*內(nèi)存儲器(正確答案)控制器C、運(yùn)算器D、微處理器答案解析：計算機(jī)中要使用外存儲器中的信息，要現(xiàn)將其調(diào)入內(nèi)存儲器（CPU可以直接訪問內(nèi)存）。5、下面設(shè)備中不屬于外部設(shè)備的是________。[單選題]*輸出設(shè)備(正確答案)外部存儲器輸入設(shè)備內(nèi)部存儲器答案解析：中央處理器和主存儲器構(gòu)成計算機(jī)的主機(jī)，除主機(jī)以外，圍繞著主機(jī)設(shè)置的各種硬件配置稱為外部設(shè)備或外圍設(shè)備?？煞譃橐韵挛孱悾狠斎?輸出設(shè)備、輔助存儲器（外存）、終端設(shè)備、過程控制設(shè)備和脫機(jī)設(shè)備。6、在計算機(jī)中，運(yùn)算器的基本功能是________。[單選題]*存儲各種控制信息(正確答案)進(jìn)行算數(shù)和邏輯運(yùn)算保持各種控制狀態(tài)控制機(jī)器各個部件協(xié)調(diào)一致的工作答題解析：[單選題]*運(yùn)算器可以執(zhí)行算術(shù)運(yùn)算和邏輯運(yùn)算，并能控制這些操作的速度。(正確答案)7、CPU對存儲器兩次讀／寫操作之間的最小間隔稱為_______。[單選題]*A、存取周期(正確答案)B、讀寫時間C、存儲容量D、存儲帶寬答題解析：CPU對存儲器兩次讀／寫操作之間的最小間隔成為存取周期。存儲器進(jìn)行一次完整的讀寫操作所需的全部時間稱為存取時間。存儲容量是指存儲器可以容納的二進(jìn)制信息量，用存儲器中存儲地址寄存器MAR的編址數(shù)與存儲字位數(shù)的乘積表示。存儲帶寬是說的存儲器的吞吐量，也就是說存儲器能一次處理的數(shù)據(jù)寬度。8、在計算機(jī)系統(tǒng)中一般存儲容量最大的是______。[單選題]*A、軟盤(正確答案)B、內(nèi)存C、硬盤D、光盤答題解析：存儲容量是指存儲器可以容納的二進(jìn)制信息量，用存儲器中存儲地址寄存器MAR的編址數(shù)與存儲字位數(shù)的乘積表示。系統(tǒng)對存儲的識別是以Byte(字節(jié)）為單位，每個字節(jié)由8位二進(jìn)制組成，即8bit(比特，也稱“位”）。按照計算機(jī)的二進(jìn)制方式，1Byte=8bit；1KB=1024Byte；1MB=1024KB;1GB=1024MB:1TB=1024GB.一般U盤的容量有1GB、2GB、4GB、8GB、16GB、32GB、64GB.常見的硬盤容量有8GB、16GB、32GB、40GB、64GB、80GB、100GB、120GB、160GB、200GB、240GB、250GB、300GB、320GB、400GB、480GB、500GB、512GB、640GB、750GB、800GB、880GB、960GB、1TB、1.5TB、2TB、3TB、4TB、5TB、6TB、7TB、8TB、10TB等等。內(nèi)存的的容量一般都是2的整次方倍，比如64MB、128MB等，一般而言，內(nèi)存容量越大越有利于系統(tǒng)的運(yùn)行。軟盤由于其存儲容量小，漸漸被淘汰了。最常用的是3.5英寸的[單選題]*軟盤，可以讀寫1.44MB,5.25英寸的軟盤1.2MB.常見的光盤主要有三種，分別為CD(650MB、700MB、800MB、(正確答案)890MB)、DVD(437G、9.7G)和藍(lán)光光盤（8.50、17G).9、下列存儲器中斷電后信息會丟失的是_______。[單選題]*硬盤(正確答案)ROMC、CD-ROMD、RAM答題解析：斷電后其中信息會丟失的是RAM，RAM就是隨機(jī)存取存儲器，是與CPU直接交換數(shù)據(jù)的內(nèi)部存儲器。它可以隨時讀寫，而且速度很快，通常作為操作系統(tǒng)或其他正在運(yùn)行中的程序的臨時數(shù)據(jù)存儲介質(zhì)。RAM在計算機(jī)和數(shù)字系統(tǒng)中用來暫時存儲程序、數(shù)據(jù)和中間結(jié)果。10、I/O方式中使計算機(jī)系統(tǒng)并行工作程度最高的是________。DMA程序查詢C、程序中斷D、通道答題解析：I/O方式包含程序查詢、程序中斷、DMA和通道等。（1）程序查詢方式。程序主動查詢輸入/輸入設(shè)備是否準(zhǔn)備好：如果準(zhǔn)備好，CPU執(zhí)行I/O操作；否則，CPU會一直查詢并等待設(shè)備準(zhǔn)備好后執(zhí)行I/O操作。這就會使CPU大部分時間處于等待狀態(tài)，系統(tǒng)效率不高。（2）程序中斷方式。在執(zhí)行過程中，出現(xiàn)異?；蛱厥馇闆r時，CPU停止當(dāng)前程序的運(yùn)行，轉(zhuǎn)而執(zhí)行對這些異?；蛱厥馇闆r進(jìn)行處理的程序，處理完再回到現(xiàn)行程序的斷點(diǎn)處繼續(xù)運(yùn)行。（3）DMA方式。直接內(nèi)存存取是I/O設(shè)備與主存儲器之間由硬件組成的直接數(shù)據(jù)通道，由于高速設(shè)備I/O與主存之間的成組數(shù)據(jù)傳送。（4）通道方式。通道是一個獨(dú)立于CPU的專門管理I/O的處理機(jī)，它控制設(shè)備與內(nèi)存直接進(jìn)行數(shù)據(jù)交換。通道有自己的通道指令，通道指令由CPU啟動，并在操作結(jié)束時向CPU發(fā)送中斷信號。通道控制方式可以做到一個通道控制多臺設(shè)備與內(nèi)存進(jìn)行數(shù)據(jù)交換，與DMA方式相比，通道方式減輕了CPU的工作負(fù)擔(dān)，增加了計算機(jī)系統(tǒng)的并行工作程度。所以相比來說，通道方式并行工作程度最高。11、計算機(jī)中緩沖技術(shù)用于________。[單選題]*提高主機(jī)和設(shè)備交換信息的速度(正確答案)提供主、輔存接口提高設(shè)備利用率擴(kuò)充相對地址空間答題解析：[單選題]*計算機(jī)中緩沖技術(shù)可用于提高主機(jī)和設(shè)備交換信息的速度。(正確答案)12、整數(shù)在計算機(jī)中存儲和運(yùn)算通常采用的格式是________。[單選題]*A、反碼(正確答案)B、原碼C、補(bǔ)碼D、偏移碼答題解析：14、下面描述錯誤的是________。[單選題]*一個數(shù)的反碼的反碼是原碼(正確答案)正數(shù)的補(bǔ)碼和原碼相同C、正數(shù)的反碼和原碼相同D、負(fù)數(shù)的補(bǔ)碼是在該數(shù)原碼的最后一位上加1答題解析：正整數(shù)的原碼、反碼和補(bǔ)碼是一樣的。在二進(jìn)制中，通常負(fù)數(shù)采用補(bǔ)碼的形式表示。原碼轉(zhuǎn)換為反碼：符號我不變，數(shù)值位分別“按位取反”。原碼轉(zhuǎn)換為補(bǔ)碼的規(guī)則：符號位不變，數(shù)值位按位取反，末位在加1。15、下列敘述中正確的是________。[單選題]*A、兩個正數(shù)的補(bǔ)碼之“和”等于兩整數(shù)“和”的補(bǔ)碼(正確答案)B、正整數(shù)的偏移碼還是其本身，負(fù)整數(shù)補(bǔ)碼的符號位取反即是其偏移碼C、01111111D、10000001答題解析：A、10000001B、00000001C、11111111D、10000000A、128B、－1C、－128D、019、計算機(jī)工作的本質(zhì)是________。[單選題]*取指令、分析指令和執(zhí)行指令(正確答案)執(zhí)行程序的過程進(jìn)行數(shù)的運(yùn)算存取數(shù)據(jù)答案解析：計算機(jī)工作的過程就是取指令、分析指令、執(zhí)行指令3個基本工作的重復(fù)。20、指令的尋址方式是________。[單選題]*確定本條指令的數(shù)據(jù)地址或下一條要執(zhí)行的指令地址(正確答案)確定本條指令的數(shù)據(jù)地址與下一條將要執(zhí)行的指令地址僅確定下一條將要執(zhí)行的指令地址僅確定本條指令的數(shù)據(jù)地址答題解析：[單選題]*尋址方式分為兩類，即指令尋址方式和數(shù)據(jù)尋址方式。尋址方式是指確定本條指令的數(shù)據(jù)地址以及下一條將要執(zhí)行的指令地址。(正確答案)21、計算機(jī)指令的尋址方式是指______。[單選題]*確定本條指令的數(shù)據(jù)地址以及下一條將要執(zhí)行的指令地址(正確答案)確定下條指令的數(shù)據(jù)地址以及本條指令的地址C、確定本條指令的數(shù)據(jù)地址以及本條指令的地址D、確定下條指令的數(shù)據(jù)地址以及下條將要執(zhí)行的指令地址答題解析：計算機(jī)指令的尋址方式是指確定本條指令的數(shù)據(jù)地址以及下一條將要執(zhí)行的指令地址。22、下面屬于指令尋址的是________。[單選題]*直接尋址(正確答案)立即尋址C、跳躍尋址D、隱含尋址答題解析：尋址方式是指尋找指令或操作數(shù)有效的地址方式，即確定本條指令的數(shù)據(jù)地址及下一條待執(zhí)行指令的地址的方法。尋址方式分為指令尋址和數(shù)據(jù)尋址。尋找下一條將要執(zhí)行的指令稱為指令尋址。常見的指令尋址有順序?qū)ぶ泛吞S尋址。尋找指令中表示的操作數(shù)或怎樣計算出操作數(shù)的地址稱為數(shù)據(jù)尋址。常見的數(shù)據(jù)存執(zhí)有隱含尋址、立即（數(shù)）尋址、直接尋址、間接尋址、寄存器尋址、寄存器間尋址、相對尋址、基址尋址、變址尋址、堆棧尋址。23、下列敘述錯誤的是________。[單選題]*取指令操作需要占用一個機(jī)器周期(正確答案)分析指令在取指周期后期就可以完成，因此無需分配一個完整的機(jī)器周期每個機(jī)器周期至少完成一個基本操作每條指令的執(zhí)行所需要的機(jī)器周期數(shù)是相同的答題解析：指令周期是取出一條指令并執(zhí)行這條指令的時間。由于各條指令的操作功能不同，因此各種指令的指令周期是不盡相同的。在計算機(jī)中，為了方便管理，常把一條指令的執(zhí)行過程劃分為若干個階段，每一階段完成一項工作。例如，取指令、存儲器讀，存儲器寫等，這每一項工作稱為一個基本操作。完成一個基本操作所需要的時間稱為機(jī)器周期。分析指令是由指令譯碼電路完成的，所占用的時間極短，無需分配一個完整的機(jī)器周期，一般是在取指令周期后期（取指結(jié)束之前的很短時間內(nèi)）就可以完成。24、不同類型計算機(jī)的指令系統(tǒng)中，________。[單選題]*指令的條數(shù)以及每一條指令中的操作碼和地址碼是不同的(正確答案)指令的條數(shù)是不同的，但大部分指令中的操作碼和地址是相同的其指令中的操作碼是相同的，但地址碼是不同的D、其指令中的操作碼是不同的，但地址碼是相同的答題解析：[單選題]*不同的計算機(jī)，其指令系統(tǒng)也不同，這主要取決于所用的CPU。(正確答案)25、下列敘述中正確的是________。[單選題]*解決實際問題的計算機(jī)指令的集合稱為計算機(jī)的指令系統(tǒng)(正確答案)某種計算機(jī)的所有指令的集合稱為該計算機(jī)的指令系統(tǒng)計算機(jī)指令的尋址方式稱為計算機(jī)的指令系統(tǒng)D、程序中所以指令的集合稱為該程序的指令系統(tǒng)答題解析：指令系統(tǒng)是指計算機(jī)所執(zhí)行的全部指令的集合，它描述了計算機(jī)內(nèi)全部的控制信息和“邏輯判斷”能力。不同計算機(jī)的指令系統(tǒng)包含的指令種類和數(shù)目也不同。26、下列敘述中正確的是________。[單選題]*在CPU執(zhí)行一條指令的過程中至少占用一個機(jī)器周期(正確答案)在CPU執(zhí)行一條指令的過程中只需要占用一個機(jī)器周期C、在CPU執(zhí)行一條指令的過程中至少要占用二個機(jī)器周期D、在CPU執(zhí)行一條指令的過程中只需要占用二個機(jī)器后期答題解析：通常用內(nèi)存中讀取一個指令字的最短時間來規(guī)定CPU周期，也稱為機(jī)器周期。由于指令執(zhí)行時指令必須訪問存儲器，所以占用一個機(jī)器周期。分析指令是由指令譯碼電路完成的，所占用的時間極短，無需分配一個完整的機(jī)器周期，一般是在取指令周期后期（取指令結(jié)束前的很短時間內(nèi)）就可以完成。指令的執(zhí)行和指令中的操作數(shù)有關(guān)，比較復(fù)雜；可能不訪問存儲器（無操作數(shù)）；訪問一次存儲器（單地址直接尋址等）；訪問兩次或多次存儲器等。因此，指令執(zhí)行可能會是一個機(jī)器周期到幾個機(jī)器周期。27、CPU中指令寄存器的任務(wù)是________。[單選題]*用來存放后續(xù)指令地址(正確答案)保存當(dāng)前正在執(zhí)行的指令保存當(dāng)前CPU所訪問的主存單元的地址保存將要存儲的下一數(shù)據(jù)字節(jié)的地址答案解析：指令寄存器用于暫存當(dāng)前正在執(zhí)行的指令。28、程序的局部性包括時間局部性和空間局部性兩個方面。時間局部性是指________。如果一個存儲項被訪問，則該項在近期可能很快被再次訪問如果一個存儲項被訪問，則該項在近期不可能很快被訪問如果一個存儲項被訪問，則該項及其鄰近的項也可能很快被訪問D、如果一個存儲項被訪問，則該項及其鄰近的項不可能很快被訪問答題解析：程序局部性原理，是指程序在執(zhí)行時呈現(xiàn)出局部性規(guī)律，即在一段時間內(nèi)，整個程序的執(zhí)行僅限于程序中的某一部分。相應(yīng)的，執(zhí)行所訪問的存儲空間也局限于某個內(nèi)存區(qū)域。程序局部性包括程序的時間局部性和程序的空間局部性。1、程序的時間局部性：是指程序即將用到的信息可能就是目前正在使用的信息。2、程序的空間局部性：是指程序即將用到對的信息可能與目前正在使用的信息在空間上相鄰或者臨近。[單選題]*如果一個存儲項被訪問，則該項在近期可能很快被再次訪問。這種規(guī)律稱為________。(正確答案)A、程序的存儲局部性B、程序的空間局部性C、程序的時間局部性D、程序的訪問局部性答題解析：時間局部性是指如果程序中的某條指令一旦執(zhí)行，則不久以后該指令可能再次被執(zhí)行；如果某數(shù)據(jù)被訪問，則不久之后該數(shù)據(jù)可能再次被訪問?？臻g局部性是指一旦程序訪問了某個存儲單元，則不久之后，其附近的存儲單元也被訪問。下列敘述中正確的是________。在計算機(jī)內(nèi)部，指令用二進(jìn)制表示，數(shù)據(jù)用ASCII碼表示在計算機(jī)內(nèi)部，指令與數(shù)據(jù)均用二進(jìn)制表示在計算機(jī)內(nèi)部，指令用十六進(jìn)制表示，數(shù)據(jù)用二進(jìn)制表示在計算機(jī)內(nèi)部，指令用十六進(jìn)制表示，數(shù)據(jù)用ASCII表示答題解析：計算機(jī)中數(shù)據(jù)最終都是以二進(jìn)制表示的，因為在計算機(jī)中只能識別兩種狀態(tài)，這是由現(xiàn)行的馮·諾依曼體系的計算機(jī)結(jié)構(gòu)所決定。計算機(jī)各部件之間的信息傳輸線稱為系統(tǒng)總線，它不包括________。A、通信總線B、控制總線C、地址總線D、數(shù)據(jù)總線答題解析：[單選題]*系統(tǒng)總線包含有三種不同功能的總線，即數(shù)據(jù)總線、地址總線和控制總線。(正確答案)下列存儲區(qū)中，掉電時其存儲內(nèi)容不會消失的是________。高速緩沖存儲器（Cache）靜態(tài)存儲單元C、動態(tài)存儲單元D、只讀存儲器答題解析：只讀存儲器（ROM）只能讀不能寫，掉電時不會丟失；隨機(jī)存儲器（RAM）在斷電后不能保留數(shù)據(jù)。根據(jù)存儲單元的工作原理不同，RAM分為靜態(tài)存儲單元和動態(tài)存儲單元。高速緩沖存儲器（Cache）是存在于主存于CPU之間的一級存儲器，有高靜態(tài)存儲芯片（SRAM）組成，容量比較小但速度比主存高得多，接近于CPU的速度。斷電后不能保留數(shù)據(jù)。處理器的速度是指處理器核心工作的速率，一般表述為________。A、系統(tǒng)的時鐘速率B、執(zhí)行指令的速度C、執(zhí)行程序的速度D、處理器總線的速度答題解析：處理器的速度是指處理器核心工作的速率，它常用系統(tǒng)的時鐘速率來表述。下面不屬于接口設(shè)備的是________。CPU網(wǎng)卡C、顯卡D、聲卡答題解析：接口設(shè)備是指硬件構(gòu)成或者是允許人和電腦、通信系統(tǒng)或者其他電子信息系統(tǒng)互動的原件系統(tǒng)。主板、CPU、內(nèi)存是計算機(jī)的核心，不屬于接口設(shè)備。下列關(guān)于計算機(jī)總線的描述中正確的是______。A、地址總線是單向的，數(shù)據(jù)和控制總線是雙向的B、控制總線是單向的，數(shù)據(jù)和地址總線是雙向的控制總線和地址總線是單向的，數(shù)據(jù)總線是雙向的控制總線、地址總線和數(shù)據(jù)總線都是雙向的答題解析：控制總線傳送的是各種控制信號，有CPU至存儲器、I/0接口設(shè)備的控制信號，有I/0接口送向CPU的應(yīng)答信號、請求信號，因此，控制總線上的信息是雙向傳輸?shù)?。?shù)據(jù)總線是CPU與存儲器、CPU與I/0接口設(shè)備之間傳送數(shù)據(jù)信息（各種指令數(shù)據(jù)信息）的總線，這些信號通過數(shù)據(jù)總線往返于CPU與存儲器、CPU與I/0接口設(shè)備之間，因此，數(shù)據(jù)總線上的信息是雙向傳輸?shù)?。地址總線上傳送的是CPU向存儲器、I/0接口設(shè)備發(fā)出的地址信息，尋址能力是CPU特有的功能，地址總線上傳送的地址信息僅由CPU發(fā)出，因此，地址總線上的信息是單向傳輸?shù)摹?.3操作系統(tǒng)[填空題]_________________________________1、順序程序不具有________。[單選題]*A、并發(fā)性(正確答案)B、順序性C、封閉性D、可再現(xiàn)性答案解析：2、一進(jìn)程已獲得除CPU以外的所有所需運(yùn)行資源，經(jīng)調(diào)度分配CPU給它后，該進(jìn)程將進(jìn)入________。[單選題]*A、運(yùn)行狀態(tài)(正確答案)B、就緒狀態(tài)C、阻塞狀態(tài)D、活動狀態(tài)答案解析：一個進(jìn)程的活動情況至少可以劃分為以下5種基本狀態(tài)：（1）運(yùn)行狀態(tài)處于運(yùn)行狀態(tài)的進(jìn)程實際上正占據(jù)這CPU。顯然，處于這種狀態(tài)的進(jìn)程數(shù)目不能多于CPU的數(shù)目。在單CPU的情況下，處于運(yùn)行狀態(tài)的進(jìn)程只能有一個。（2）就緒狀態(tài)這種狀態(tài)的進(jìn)程已獲得除CPU以外的一切所需資源，只是因為缺少CPU而不能運(yùn)行，一旦獲得CPU，它就立即投入運(yùn)行。（3）等待狀態(tài)一個進(jìn)程正在等待某一事件的發(fā)生而暫時停止執(zhí)行。在這種狀態(tài)下，即使把CPU分配給它，該進(jìn)程也不能運(yùn)行，及處于等待狀態(tài)，又稱為阻塞狀態(tài)或封鎖狀態(tài)。（4）創(chuàng)建狀態(tài)進(jìn)程正在創(chuàng)建過程中，尚不能執(zhí)行。（5）終止?fàn)顟B(tài)進(jìn)程運(yùn)行結(jié)束。3、如果一個進(jìn)程在運(yùn)行時因某種原因暫停，該進(jìn)程將脫離運(yùn)行狀態(tài)進(jìn)入________。[單選題]*A、靜止?fàn)顟B(tài)(正確答案)B、停止?fàn)顟B(tài)C、阻塞狀態(tài)D、就緒狀態(tài)答案解析：進(jìn)程3種狀態(tài)裝換條件如下：（1）處于就緒狀態(tài)的進(jìn)程，一旦分配到CPU，就轉(zhuǎn)為運(yùn)行狀態(tài)。（2）處于運(yùn)行狀態(tài)的進(jìn)程，當(dāng)需要等待某個事件發(fā)生才能繼續(xù)運(yùn)行時，則轉(zhuǎn)為等待狀態(tài)（阻塞狀態(tài)）；或者由于分配給它的時間用完，就讓出CPU而轉(zhuǎn)為就緒狀態(tài)。（3）處于等待狀態(tài)的進(jìn)程，如果它等待的事件已經(jīng)發(fā)生，即條件得到滿足，就轉(zhuǎn)為就緒狀態(tài)。4、進(jìn)程是________。[單選題]*一個系統(tǒng)軟件(正確答案)與程序等效的概念程序的執(zhí)行過程存放在內(nèi)存中的程序答案解析：進(jìn)程是指一個具有一定獨(dú)立功能的程序關(guān)于某個數(shù)據(jù)集合的一次運(yùn)行活動。簡單的說，進(jìn)程可以并發(fā)執(zhí)行的程序的執(zhí)行過程，它是控制程序管理下的基本的多道程序單位。5、進(jìn)程具有多種屬性，并發(fā)性之外的另一重要屬性是________。[填空題]*答案解析：A、動態(tài)性B、靜態(tài)性C、易用性D、封閉性進(jìn)程的特性包括并行性和動態(tài)性。6、操作系統(tǒng)在控制和管理進(jìn)程過程中，進(jìn)程存在的唯一標(biāo)志的數(shù)據(jù)結(jié)構(gòu)________。[單選題]*FIFO(正確答案)FCBC、FDTD、FCB答案解析：進(jìn)程控制塊FCB是由系統(tǒng)為每個進(jìn)程分別建立的，用以記錄對應(yīng)進(jìn)程的程序和數(shù)據(jù)的存儲情況，記錄進(jìn)程的動態(tài)信息。系統(tǒng)根據(jù)PCB而感知進(jìn)程的存在，根據(jù)PCB中的信息進(jìn)程實施控制管理。當(dāng)進(jìn)程結(jié)束時，系統(tǒng)即收回它的PCB，進(jìn)程也隨之消亡。因此可以說，PCB是一個進(jìn)程存在的標(biāo)志。7、理論上計算機(jī)虛擬內(nèi)存最大容量取決于________。[單選題]*計算機(jī)地址位數(shù)(正確答案)物理內(nèi)存大小C、磁盤空間大小D、數(shù)據(jù)存放的實際地址答題解析：[單選題]*計算機(jī)地址位數(shù)決定了內(nèi)存的最大容量，決定了虛擬內(nèi)存的最大容量。虛擬內(nèi)存容量的大小和操作系統(tǒng)也有關(guān)，地址位數(shù)只是決定最大容量，操作系統(tǒng)決定實際容量。(正確答案)8、在操作系統(tǒng)中，將文件名轉(zhuǎn)換為文件存儲地址的結(jié)構(gòu)是________。[單選題]*文件目錄(正確答案)PCB表路徑名D、文件名答題解析：為了根據(jù)文件名存取文件，必須建立文件名與文件在外存空間中的物理地址的對應(yīng)，表示這種對應(yīng)關(guān)系的數(shù)據(jù)結(jié)構(gòu)成為文件目錄。9、下列敘述中正確的是________。[單選題]*進(jìn)程在運(yùn)行狀態(tài)下，如果時間片用完即終止(正確答案)進(jìn)程一旦創(chuàng)建即進(jìn)入運(yùn)行狀態(tài)處于阻塞狀態(tài)的進(jìn)程，當(dāng)阻塞原因解除后即進(jìn)入就緒狀態(tài)進(jìn)程就在就緒狀態(tài)下，如果時間片用完即終止答題解析：進(jìn)程3重狀態(tài)轉(zhuǎn)換條件如下：（1）處于就緒狀態(tài)的進(jìn)程，一旦分配到CPU，就轉(zhuǎn)為運(yùn)行狀態(tài)。（2）處于運(yùn)行狀態(tài)的進(jìn)程，當(dāng)需要等待某個時間發(fā)生才能繼續(xù)運(yùn)行時，則轉(zhuǎn)為等待狀態(tài)（阻塞狀態(tài)）；或者由于分配給它的時間片用完，就讓出CPU而轉(zhuǎn)為就緒狀態(tài)。（3）處于等待狀態(tài)的進(jìn)程，如果它等待的事件已經(jīng)發(fā)生，即條件得到滿足，就轉(zhuǎn)為就緒狀態(tài)。10、下列不屬于文件屬性的是________。[單選題]*A、文件長度(正確答案)B、文件名稱C、文件類型D、文件內(nèi)容答題解析：11、下列關(guān)于多道程序環(huán)境下進(jìn)行描述正確的是________。[單選題]*單CPU的計算機(jī)允許多個進(jìn)程并發(fā)執(zhí)行(正確答案)單CPU的計算機(jī)只允許執(zhí)行1個進(jìn)行C、多個程序可以合并成一個進(jìn)程執(zhí)行D、多個CPU共同執(zhí)行一個程序答題解析：多道程序設(shè)計程序是指允許多個程序同事進(jìn)入內(nèi)存并運(yùn)行。及同時把多個程序放入內(nèi)存，并允許它們交替在CPU運(yùn)行，多個程序可共享系統(tǒng)中的和各種硬、軟件資源。當(dāng)一個程序因I/O請求而暫停運(yùn)行時，CPUC便立即轉(zhuǎn)去運(yùn)行另一個程序。12、一個正在運(yùn)行的進(jìn)程由于所申請的資源得不到滿足要調(diào)用________。[單選題]*A、阻塞進(jìn)程原語(正確答案)B、撤銷進(jìn)程原語C、喚醒進(jìn)程原語D、創(chuàng)建進(jìn)程原語答題解析：f1b6ba825f1b6ba825e440b8cb387de7d7c33e11.png'/>13、當(dāng)一個進(jìn)程在運(yùn)行過程中釋放了系統(tǒng)資源要調(diào)用________。[單選題]*A、阻塞進(jìn)程原語(正確答案)B、撤銷進(jìn)程原語C、喚醒進(jìn)程原語D、創(chuàng)建進(jìn)程原語答案解析：14、當(dāng)一進(jìn)程在運(yùn)行狀態(tài)下結(jié)束時要調(diào)用________。[單選題]*A、撤銷進(jìn)程原語(正確答案)B、喚醒進(jìn)程原語C、阻塞進(jìn)程原語D、創(chuàng)建進(jìn)程原語答題解析：15、下列敘述中正確的是________。[單選題]*虛擬存儲器的空間大小取決于計算機(jī)的訪存能力(正確答案)實際外存都應(yīng)是虛擬存儲器的空間虛擬存儲器使存儲系統(tǒng)即具有相當(dāng)于外存的容量又具有與主存一樣的訪問速度實際物理存儲空間必須大于虛擬存儲器空間答題解析：虛擬存儲器的空間大小取決于計算機(jī)的訪存能力。16、如果作業(yè)的邏輯地址空間大于計算機(jī)實際的物理內(nèi)存空間，則應(yīng)采用的存儲管理技術(shù)是________。[單選題]*請求分頁式管理(正確答案)分區(qū)存儲管理可變分區(qū)存儲管理段頁式存儲管理答題解析：請求頁式管理是動態(tài)頁內(nèi)存管理的一種，它在作業(yè)和進(jìn)程開始執(zhí)行之前，不把作業(yè)或進(jìn)程的程序段和數(shù)據(jù)段一次性全部裝入內(nèi)存，而只裝入被認(rèn)為是經(jīng)常反復(fù)執(zhí)行和調(diào)用的工作區(qū)部分。分區(qū)存儲管理是將內(nèi)存劃分成若干個連續(xù)區(qū)域，每個區(qū)分裝入一個運(yùn)行作業(yè)。分區(qū)存儲管理的主要確定是不能充分利用內(nèi)存，也不能實現(xiàn)對內(nèi)存的擴(kuò)充。具體可分為固定分區(qū)和可變分區(qū)兩種方式。段頁式存儲管理方式即先將用戶程序分成若干個段，再把每個段分成若干個頁，并為每一個段賦予一個段名。內(nèi)存是以頁為基本單位分配給每個用戶程序的。17、操作系統(tǒng)的四項主要功能是________。[單選題]*進(jìn)程管理、存儲管理、設(shè)備管理和文件管理(正確答案)CPU管理、文件管理、中斷管理和外設(shè)管理用戶管理、文件管理、中斷管理和外設(shè)管理D、程序管理、文件管理、中斷管理和外設(shè)管理答題解析：操作系統(tǒng)主要包括以下幾個方面的功能：①進(jìn)程管理，其主要工作主要是進(jìn)程調(diào)度女，在單用戶單任務(wù)的情況下，處理器僅為一個用戶的一個任務(wù)所獨(dú)占，進(jìn)程管理的工作十分簡單。但在多道程序或多用戶的情況下，組織多個作業(yè)或任務(wù)是，就要解決處理器的調(diào)度、分配和回收等問題。②存儲管理分為幾種功能：存儲分配、存儲共享、存儲保護(hù)、存儲擴(kuò)張。③設(shè)備管理功能：設(shè)備傳輸控制、設(shè)備獨(dú)立性、設(shè)備分配。④文件管理：文件存儲空間的管理、目錄管理、文件操作管理、文件保護(hù)。⑤作業(yè)管理是負(fù)責(zé)處理用戶提交的任何要求。18、不屬于操作系統(tǒng)主要特性的是________。[單選題]*A、共享性(正確答案)B、并發(fā)性C、異步性D、不可中斷性答題解析：19、計算機(jī)I/O接口的功能不包括________。[單選題]*實現(xiàn)外部設(shè)備之間的互聯(lián)(正確答案)實現(xiàn)設(shè)備的選擇實現(xiàn)數(shù)據(jù)緩存以達(dá)到速度匹配實現(xiàn)電平轉(zhuǎn)換答題解析：CPU與外設(shè)之間的數(shù)據(jù)交換必須通過接口來完成、通常接口有以下功能：（1）設(shè)置數(shù)據(jù)的寄存、緩存邏輯，以適應(yīng)CPU與外設(shè)之間的速度差異。（2）能夠進(jìn)行信息格式的轉(zhuǎn)換，例如：串行和并行的轉(zhuǎn)換。（3）能夠協(xié)調(diào)CPU和外設(shè)兩者在信息的類型和電平的差異。（4）協(xié)調(diào)時序差異。（5）地址譯碼和設(shè)備選擇功能。（6）設(shè)置中斷和DMA控制邏輯，以保證在中斷和DMA允許的情況下產(chǎn)生中斷和DMA請求信號，并在接受中斷和DMA應(yīng)答之后完成中斷處理和DMA傳輸。對操作系統(tǒng)的進(jìn)程管理描述正確的是________。進(jìn)程管理包括作業(yè)管理進(jìn)程管理是指對用戶程序的組織與管理進(jìn)程管理的主要工作是處理器調(diào)度D、進(jìn)程管理僅解決處理器的分配調(diào)度答案解析：[單選題]*操作系統(tǒng)在進(jìn)程管理的以下方面做工作：進(jìn)程控制、控制同步、進(jìn)程通信和進(jìn)程調(diào)度。(正確答案)分時操作系統(tǒng)的特點(diǎn)是________。A、互聯(lián)性B、關(guān)聯(lián)性C、共享性D、獨(dú)立性答案解析：分時操作系統(tǒng)的特點(diǎn)有：（1）交互性（同時性）：用戶與系統(tǒng)進(jìn)行人機(jī)對話。用戶在終端上可以直接輸入、調(diào)試和運(yùn)行自己的程序，在本機(jī)上是修改程序中的錯誤，直接獲得結(jié)果。（2）多路性（多用戶同時性）：多用戶同時在各自終端上使用同一CPU和其他資源，充分發(fā)揮系統(tǒng)的效率。（3）獨(dú)立性：用戶可彼此獨(dú)立操作，互補(bǔ)干擾，互補(bǔ)混淆。（4）及時性：用戶在短時間內(nèi)可得到系統(tǒng)的即是回答。下列敘述中正確的是________。并發(fā)程序的執(zhí)行過程中，程序與其執(zhí)行過程是一一對應(yīng)的并發(fā)程序具有共享性C、并發(fā)程序具有順序性D、并發(fā)程序具有封閉性答題解析：并發(fā)程序的特點(diǎn)：（1）失去了程序的封閉性（程序結(jié)果的不可再現(xiàn)性）（2）程序與計算不在一一對應(yīng)。（3）程序并發(fā)執(zhí)行的相互制約。使用緩沖技術(shù)可以________。適當(dāng)降低CPU運(yùn)行速度提高CPU對存儲器的訪問速度提高CPU對I/O設(shè)備的訪問速度改善CPU對I/O設(shè)備之間速度不匹配的情況答題解析：緩沖區(qū)技術(shù)用到了緩沖區(qū)，而緩沖區(qū)的引入是為了緩和CPU和I/O設(shè)備的不匹配，減少對CPU的中斷頻率，提高CPU和I/O設(shè)備的并行性。下列敘述中錯誤的是______。A、一個程序只能對應(yīng)一個進(jìn)程B、一個進(jìn)程可以包含多個程序C、進(jìn)程是程序的執(zhí)行過程D、進(jìn)程具有一定的生命期答題解析：程序只是一組指令的有序集合，它本身沒有任何運(yùn)行的含義，它只是一個靜態(tài)的實體。而進(jìn)程則不同，它是程序在某個數(shù)據(jù)集上的執(zhí)行。進(jìn)程是一個動態(tài)的實體，它有自己的生命周期。它因創(chuàng)建而產(chǎn)生，因調(diào)度而運(yùn)行，因等待資源或事件而被處于等待狀態(tài)，因完成任務(wù)而被撤消。反映了一個程序在一定的數(shù)據(jù)集上運(yùn)行的全部動態(tài)過程。一般來說，一個進(jìn)程肯定有一個與之對應(yīng)的程序，而且只有一個。而一個程序有可能沒有與之對應(yīng)的進(jìn)程（因為它沒有執(zhí)行），也有可能有多個進(jìn)程與之對應(yīng)（運(yùn)行在幾個不同的數(shù)據(jù)集上）。下列敘述中正確的是________。處于運(yùn)行狀態(tài)的進(jìn)程數(shù)最多等于計算機(jī)系統(tǒng)中CPU的個數(shù)進(jìn)程一旦被創(chuàng)建即處于運(yùn)行狀態(tài)進(jìn)程可以在就緒狀態(tài)下結(jié)束進(jìn)程可以在等待（阻塞）狀態(tài)下結(jié)束答題解析：運(yùn)行狀態(tài)是指進(jìn)程已獲得CPU，并且在CPU上執(zhí)行的狀態(tài)。顯然，有n個CPU的系統(tǒng)中，最多有n個運(yùn)行狀態(tài)的進(jìn)程。進(jìn)程創(chuàng)建后進(jìn)入就緒狀態(tài)。當(dāng)一個進(jìn)程到達(dá)自然結(jié)束點(diǎn)或出現(xiàn)了無法克服的錯誤，或是被操作系統(tǒng)或其它有終止權(quán)的進(jìn)程所終結(jié)，它將進(jìn)入終止?fàn)顟B(tài)。下列存儲管理中屬于連續(xù)存儲管理的是________。請求分頁式存儲管理分區(qū)存儲管理C、頁式存儲管理D、段式存儲管理答題解析：請求頁式管理是動態(tài)頁式內(nèi)存管理的一種，它在作業(yè)和進(jìn)程開始執(zhí)行之前，不把作業(yè)或進(jìn)程的程序段和數(shù)據(jù)段一次性全部裝入被認(rèn)為是經(jīng)常反復(fù)執(zhí)行和調(diào)用對的工作區(qū)部分。分區(qū)存儲管理是將內(nèi)存劃分若干個連續(xù)區(qū)域，每個分區(qū)裝入一個運(yùn)行做魚。分區(qū)存儲管理是將內(nèi)存劃分成若干個連續(xù)區(qū)域，每個分區(qū)裝入一個運(yùn)行作業(yè)。分區(qū)存儲管理的主要確定是不能充分利用內(nèi)存，也不能實現(xiàn)內(nèi)存的擴(kuò)充。具體可分為固定分區(qū)和可變分區(qū)兩種方式。段頁式存儲管理方式即先將用戶程序分成若干個段，再把每個段分成若干個頁，并為每一個段賦予一個段名。內(nèi)存是以頁為基本單位分配給每個用戶程序的。計算機(jī)系統(tǒng)的I/O方式不包括________。通道程序查詢C、程序中斷D、D/A與A/D轉(zhuǎn)換答題解析：CPU對外部設(shè)備的控件方式主要有四種：①循環(huán)測試I/O方式（查詢方式）。②中斷處理方式。③直接內(nèi)存存?。―MA）方式。④通道方式。D/A是數(shù)模轉(zhuǎn)換，把數(shù)字量轉(zhuǎn)換為模擬量，一般用于輸入電壓電流信號。A/D是模擬轉(zhuǎn)換，把模擬量轉(zhuǎn)換為數(shù)字量，一般用于采集電壓電流信號。在操作系統(tǒng)中，進(jìn)程調(diào)度可稱為________。A、作業(yè)調(diào)度B、高級調(diào)度C、低級調(diào)度D、設(shè)備調(diào)度答題解析：進(jìn)程調(diào)度又稱為低級調(diào)度。一個已經(jīng)獲得除CPU以外的所有所需資源的進(jìn)程處于______。A、任意狀態(tài)B、運(yùn)行狀態(tài)C、就緒狀態(tài)D、阻塞狀態(tài)答題解析：就緒狀態(tài)：是指一個進(jìn)程已經(jīng)具備運(yùn)行條件，但由于沒有獲得CPU而不能運(yùn)行所處的狀態(tài)。運(yùn)行狀態(tài)：是指進(jìn)程已獲得CPU,并且在CPU上執(zhí)行的狀態(tài)。阻塞狀態(tài)：也稱等待狀態(tài)，是指進(jìn)程因等待某種事件發(fā)生而暫時不能運(yùn)行的狀態(tài)。在操作系統(tǒng)中，文件系統(tǒng)是指______。A、文件的目錄B、文件的集合負(fù)責(zé)存取和管理文件信息的軟件機(jī)構(gòu)實現(xiàn)文件管理的一組軟件答題解析：文件系統(tǒng)就是操作系統(tǒng)中實現(xiàn)文件統(tǒng)一管理的一組軟件、被管理的文件以及為實施文件管理所需要的一些數(shù)據(jù)結(jié)構(gòu)的總稱。下列敘述中正確的是______。處于就緒狀態(tài)的進(jìn)程，一旦分配到CPU,就轉(zhuǎn)為等待狀態(tài)處于等待狀態(tài)的進(jìn)程，如果它等待的事件已經(jīng)發(fā)生，就轉(zhuǎn)為就緒狀態(tài)C、處于運(yùn)行狀態(tài)的進(jìn)程，當(dāng)分配給它的時間片用完時，則轉(zhuǎn)為等待狀態(tài)D、進(jìn)程可以在就緒狀態(tài)下結(jié)束答題解析：運(yùn)行中的進(jìn)程可以處于以下三種狀態(tài)之一：①運(yùn)行狀態(tài)：是指進(jìn)程已獲得CPU,并且在CPU上執(zhí)行的狀態(tài)。②就緒狀態(tài)：是指一個進(jìn)程已經(jīng)具備運(yùn)行條件，但由于沒能獲得CPU而不能運(yùn)行時所處的狀態(tài)。③等待狀態(tài)：也稱為阻塞狀態(tài)或封鎖狀態(tài)。是指進(jìn)程因等待某種事件發(fā)生而暫時不能運(yùn)行的狀態(tài)。虛擬存儲技術(shù)是________。A、擴(kuò)充內(nèi)存物理空間的技術(shù)B、對主存儲邏輯擴(kuò)展的技術(shù)擴(kuò)充外存空間的技術(shù)擴(kuò)充輸入輸出緩沖區(qū)的技術(shù)答題解析：虛擬存儲技術(shù)是利用大容量的外存來擴(kuò)充內(nèi)存，產(chǎn)生一個比有限的實際內(nèi)存空間大得多、邏輯的虛擬存儲空間。引入多道程序設(shè)計的目的在于________。充分利用存儲器提高實時響應(yīng)速度有利于代碼共享，減少主、輔存信息交換量充分利用CPU，減少CPU等待時間答題解析：引入多道程序設(shè)計技術(shù)的根本目的是為了提高CPU的利用率，充分發(fā)揮計算機(jī)系統(tǒng)部件的并行性，現(xiàn)代計算機(jī)系統(tǒng)采用了多道程序設(shè)計技術(shù)。采用時間片輪轉(zhuǎn)算法調(diào)度的目的是使得________。先來先服務(wù)多個進(jìn)程都能得到系統(tǒng)的及時響應(yīng)優(yōu)先級較高的進(jìn)程得到及時調(diào)度需CPU最短的進(jìn)程先執(zhí)行答題解析：時間片輪轉(zhuǎn)算法的基本思想是將CPU的處理時間分成一個個時間片，就緒隊列中的進(jìn)程輪流運(yùn)行一個時間片。當(dāng)時間片結(jié)束時，就強(qiáng)迫運(yùn)行程序讓出CPU。輪轉(zhuǎn)法目的是式多個進(jìn)程都能得到系統(tǒng)的及時響應(yīng)。為了描述進(jìn)程的動態(tài)變化過程，在進(jìn)程控制塊中定義了________。A、進(jìn)程優(yōu)先數(shù)B、進(jìn)程狀態(tài)字進(jìn)程打開文件表進(jìn)程起始地址答題解析：[單選題]*進(jìn)程控制塊（PCB）是系統(tǒng)為了管理進(jìn)程設(shè)置的一個專門的數(shù)據(jù)結(jié)構(gòu)。系統(tǒng)用它來記錄進(jìn)程的外部特征，描述進(jìn)程的運(yùn)動變化過程。同時，系統(tǒng)可以利用PCB來控制和管理進(jìn)程，所以說，PCB（進(jìn)程控制塊）是系統(tǒng)感知進(jìn)程存在的唯一標(biāo)志。(正確答案)在多道程序設(shè)計中，將一臺獨(dú)占設(shè)備改造為共享設(shè)備的一種技術(shù)是________。使用SPOOLing系統(tǒng)緩沖技術(shù)C、并發(fā)技術(shù)D、串行化答題解析：SPOOLing系統(tǒng)實現(xiàn)設(shè)備管理的虛擬技術(shù)，即：將獨(dú)占設(shè)備改造為共享設(shè)備。它由專門負(fù)責(zé)I/O的常駐內(nèi)存的進(jìn)程以及輸入并、輸出并組成。在單CPU的情況下，處于運(yùn)行狀態(tài)的進(jìn)程只能有________。A、1個B、2個C、0個D、任意個答題解析：運(yùn)行狀態(tài)是指進(jìn)程已獲得CPU，并且在CPUC上執(zhí)行的狀態(tài)。顯然，在一個單CPU系統(tǒng)中，最多只有一個進(jìn)程處于運(yùn)行狀態(tài)。第二部分?jǐn)?shù)據(jù)結(jié)構(gòu)與算法2.1算法[填空題]_________________________________1、下列關(guān)于算法的描述中錯誤的是。[單選題]*算法強(qiáng)調(diào)動態(tài)的執(zhí)行過程，不同于靜態(tài)的計算公式(正確答案)算法必須能在有限個步驟之后終止算法設(shè)計必須考慮算法的復(fù)雜度算法的優(yōu)劣取決于運(yùn)行算法程序的環(huán)境本題考查知識點(diǎn)是算法。算法的基本特征有可行性、確定性、有窮性、擁有足夠的情報，所以A、B是正確的。算法的設(shè)計要求包括效率與低存儲量，即要考慮算法的時間復(fù)雜度與空間復(fù)雜度，所以C是正確的，算法的優(yōu)劣與算法描述語言有關(guān)，與所用計算機(jī)無關(guān)。2、為了降低算法的空間復(fù)雜度，要求算法盡量采用原地工作（inplace).所謂原地工作是指_______。[單選題]*執(zhí)行算法時不使用任何存儲空間(正確答案)執(zhí)行算法時所使用的額外空間隨算法所處理的數(shù)據(jù)空間大小的變化而變化執(zhí)行算法時不使用額外空間執(zhí)行算法時所使用的額外空間固定（即不隨算法所處理的數(shù)據(jù)空間大小的變化而變化）答題解析：本題考查知識點(diǎn)是算法。一個算法的空間復(fù)雜度，一般是指執(zhí)行這個算法所需要的內(nèi)存空間。一個算法所占用的存儲空間包括程序所占的空間、輸入的初始數(shù)據(jù)所占的存儲空間以及算法執(zhí)行過程中所需要的額外空間。其中額外空間包括算法程序執(zhí)行過程中的工作單元以及某種數(shù)據(jù)結(jié)構(gòu)所需要的附加存儲空間。如果額外空間相對于問題規(guī)模來說是常數(shù)，則稱該算法是原地（inplace)工作的。所以本題答案為D.3、下列敘述中正確的是______。[單選題]*對同一批數(shù)據(jù)作不同的處理，如果數(shù)據(jù)存儲結(jié)構(gòu)相同，不同算法的時間復(fù)雜度肯定相同(正確答案)解決同一個問題的不同算法的時間復(fù)雜度必定是相同的對同一批數(shù)據(jù)作同一種處理，如果數(shù)據(jù)存儲結(jié)構(gòu)不同，不同算法的時間復(fù)雜度肯定相同解決同一個問題的不同算法的時間復(fù)雜度一般是不同的答題解析：本題考查知識點(diǎn)是算法。所謂算法的時間復(fù)雜度，是指執(zhí)行算法所需要的計算工作量。解決同一個問題的不同算法的時間復(fù)雜度一般是不同的，時間復(fù)雜度也能夠反映出一個算法的優(yōu)劣程度。所以本題答案為D.4、下列敘述中正確的是_____。[單選題]*算法復(fù)雜度是指算法控制結(jié)構(gòu)的復(fù)雜程度。(正確答案)算法設(shè)計只需考慮結(jié)果的可靠性。數(shù)據(jù)的存儲結(jié)構(gòu)會影響算法的效率。算法復(fù)雜度是用算法中指令的條數(shù)來度量的。答題解析：本題考查的知識點(diǎn)是算法。算法的設(shè)計要求包括效率與低存儲量，即要考慮算法的時間復(fù)雜度與空間復(fù)雜度。因此選項B錯誤；算法的復(fù)雜度主要包括時間復(fù)雜度和空間復(fù)雜度。所謂算法的時間復(fù)雜度，是指執(zhí)行算法所需要的計算工作量；一個算法的空間復(fù)雜度，一般是指執(zhí)行這個算法所需要的內(nèi)存空間，因此選項A、第1頁[填空題]_________________________________2.2數(shù)據(jù)結(jié)構(gòu)的基本概念[填空題]_________________________________1、設(shè)數(shù)據(jù)元素的集合D={1,2,3,4,5}，則滿足下列關(guān)系R的數(shù)據(jù)結(jié)構(gòu)中為線性結(jié)構(gòu)的是。[單選題]*R={(1,2),(3,4),(5,1)}(正確答案)R={(1,3),(4,1),(3,2),(5,4)}R={(1,2),(2,3),(4,5)}D、R={(1,3),(2,4),(3,5)}本題的考查知識點(diǎn)是線性結(jié)構(gòu)與非線性結(jié)構(gòu)。線性結(jié)構(gòu)用圖形表示更加直觀，（1,3）圖形表示為1->3，（4,1）圖形表示為4->1，其余R中的元素圖形表示以此類推。線性結(jié)構(gòu)要求有且只有一個根結(jié)點(diǎn)，而且每一個結(jié)點(diǎn)最多有一個前件，也最多有一個后件。2、下列敘述中正確的是。A、所有數(shù)據(jù)結(jié)構(gòu)必須有根結(jié)點(diǎn)[單選題]*所有數(shù)據(jù)結(jié)構(gòu)必須有終端結(jié)點(diǎn)（即葉子結(jié)點(diǎn)）(正確答案)只有一個根結(jié)點(diǎn)，且只有一個葉子結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是線性結(jié)構(gòu)沒有根結(jié)點(diǎn)或沒有葉子結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)一定是非線性結(jié)構(gòu)本題考查知識點(diǎn)是數(shù)據(jù)結(jié)構(gòu)。用無向圖表示的網(wǎng)狀模型是非線性結(jié)構(gòu)，它可以沒有根節(jié)點(diǎn)和葉子節(jié)點(diǎn)。選項A、B錯誤。樹形結(jié)構(gòu)是非線性結(jié)構(gòu)，非空二叉樹只有一個根節(jié)點(diǎn)，最多有兩顆子樹（可以有一個或沒有），所以C錯誤。3、下列敘述中正確的是。[單選題]*非線性結(jié)構(gòu)只能采用鏈?zhǔn)酱鎯Y(jié)構(gòu)(正確答案)非線性結(jié)構(gòu)只能用多重鏈表表示所有數(shù)據(jù)結(jié)構(gòu)既可以采用順序存儲結(jié)構(gòu)，也可以采用鏈?zhǔn)酱鎯Y(jié)構(gòu)有的非線性結(jié)構(gòu)也能采用順序存儲結(jié)構(gòu)本題考查知識點(diǎn)是非線性結(jié)構(gòu)。二叉樹是一種很有用的非線性結(jié)構(gòu)，二叉樹的存儲結(jié)構(gòu)一共有兩種：順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，且順序存儲結(jié)構(gòu)僅適用于完全二叉樹。非完全二叉樹只能用鏈?zhǔn)酱鎯Y(jié)構(gòu)。對于滿二叉樹與完全二叉樹可以按層進(jìn)行順序存儲，但是順序存儲對于一般二叉樹不適應(yīng)。所以本題答案為D。4、下列敘述中正確的是______。[單選題]*A.只有一個根結(jié)點(diǎn)和一個葉子結(jié)點(diǎn)的必定是線性結(jié)構(gòu)(正確答案)非線性結(jié)構(gòu)可以為空只有一個根結(jié)點(diǎn)的必定是線性結(jié)構(gòu)或二叉樹沒有根結(jié)點(diǎn)的一定是非線性結(jié)構(gòu)答題解析：本題的考查知識點(diǎn)是數(shù)據(jù)結(jié)構(gòu)。線性結(jié)構(gòu)與非線性結(jié)構(gòu)都可以是空的數(shù)據(jù)結(jié)構(gòu)，一個空的數(shù)據(jù)結(jié)構(gòu)究竟是屬于線性結(jié)構(gòu)還是屬于非線性結(jié)構(gòu)，這要根據(jù)具體情況來確定，所以D選項錯誤；二叉樹是非線性結(jié)構(gòu)中的一種常見結(jié)構(gòu)。二叉樹有兩個特點(diǎn)：①非空二叉樹只有一個根結(jié)點(diǎn)，所以C選項錯誤；②每一個結(jié)點(diǎn)最多有兩顆子樹，且分別稱為該結(jié)點(diǎn)的左子樹與右子樹，只有一個根結(jié)點(diǎn)和一個葉子結(jié)點(diǎn)可以構(gòu)成一個二叉樹，因此它可能是非線性結(jié)構(gòu)，所以A選項錯誤。所以本題答案為B.5、下列數(shù)據(jù)結(jié)構(gòu)中為非線性結(jié)構(gòu)的是______。[單選題]*A、雙向鏈表(正確答案)B、循環(huán)隊列C、循環(huán)鏈表D、二叉鏈表答題解析：本題考查知識點(diǎn)是二叉樹存儲結(jié)構(gòu)。二叉樹（binarytree)是一種很有用的非線性結(jié)構(gòu)。由于二叉樹的存儲結(jié)構(gòu)中每一個存儲結(jié)點(diǎn)有兩個指針域，因此，二叉樹的鏈?zhǔn)酱鎯Y(jié)構(gòu)也稱為二叉鏈表。所以本題答案為D.6、下列敘述中正確的是______。[單選題]*A、數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素可以是另一種數(shù)據(jù)結(jié)構(gòu)(正確答案)B、數(shù)據(jù)結(jié)構(gòu)中的數(shù)據(jù)元素只能是另一種線性結(jié)構(gòu)以上說法均不正確答題解析：本題考查知識點(diǎn)是數(shù)據(jù)結(jié)構(gòu)。數(shù)據(jù)結(jié)構(gòu)是指反應(yīng)數(shù)據(jù)元素之間關(guān)系的數(shù)據(jù)元素集合的表示。更通俗地說，數(shù)據(jù)結(jié)構(gòu)是指帶有結(jié)構(gòu)的數(shù)據(jù)元素的集合。所謂結(jié)構(gòu)實際上就是指數(shù)據(jù)元素之間的前后件關(guān)系。所以本題答案為A.7、下列敘述中正確的是_____。[單選題]*A、有多個指針域的鏈表有可能是線性結(jié)構(gòu)。(正確答案)B、有多個指針域的鏈表一定是非線性結(jié)構(gòu)。答題解析：本題的考查知識點(diǎn)是數(shù)據(jù)結(jié)構(gòu)。在鏈?zhǔn)酱鎯Y(jié)構(gòu)中，每個結(jié)點(diǎn)指針域中的指針用于指向該結(jié)點(diǎn)的前件或后件。在用鏈?zhǔn)浇Y(jié)構(gòu)表示非線性結(jié)構(gòu)時，其指針域的個數(shù)要多一些。并不能確定有多個指針域的鏈表是線性結(jié)構(gòu)還是非線性結(jié)構(gòu)，故A正確，B錯誤。二叉樹的存儲結(jié)構(gòu)是有兩個指針域的鏈表，但反過來不一定成立，故C錯誤。非空的二叉樹，只有一個根結(jié)點(diǎn)，而二叉樹是一個典型的非線性結(jié)構(gòu)，故8、設(shè)數(shù)據(jù)集合為D={1,2,3,4,5},下列數(shù)據(jù)結(jié)構(gòu)B=(D,R)中為非線性結(jié)構(gòu)的是______。[單選題]*A、R={(1,2),(2,3),(4,3),(3,5)}(正確答案)B、R={(1,2),(2,3),(3,4),(4,5)}C.R={(5,4),(4,3),(3,2),(2,1)}D.R={(2,5),(5,4),(3,2),(4,3)}答題解析：本題考查的知識點(diǎn)是非線性結(jié)構(gòu)。如果一個非空的數(shù)據(jù)結(jié)構(gòu)滿足下列兩個條件，1)有且只有一個根結(jié)點(diǎn)；2)每一個結(jié)點(diǎn)最多有一個前件，也最多有一個后件。則稱該數(shù)據(jù)結(jié)構(gòu)為線性結(jié)構(gòu)。數(shù)據(jù)的邏輯結(jié)構(gòu)有兩個要素，一是數(shù)據(jù)元素的集合，通常記為D;二是D上的關(guān)系，它反映了D中各元素之前的前后件關(guān)系，通常記為R.即一個數(shù)據(jù)結(jié)構(gòu)可以表示成B=(D,R),其中B表示數(shù)據(jù)結(jié)構(gòu)。為了反映D中各元素之間的前后件關(guān)系，一般用二元組來表示。例如，假設(shè)a與b是D中的兩個數(shù)據(jù)，則二元組（a,b)表示a是b的前件，b是a的后件。線性結(jié)構(gòu)用圖形表示更加直觀，選項B的結(jié)構(gòu)為：1->2->3->4->5;選項C的結(jié)構(gòu)為：5->4->3->2->1:選項D的結(jié)構(gòu)為：2->5->4->3->2.選項B、C、D均為線性結(jié)構(gòu)。選項A中結(jié)點(diǎn)3有兩個前件，分別為2和4,不滿足線性結(jié)構(gòu)的定義，所以為非線性結(jié)構(gòu)。2.3線性表及其順序存儲結(jié)構(gòu)[填空題]_________________________________1、下列敘述中正確的是______。[單選題]*能采用順序存儲的必定是線性結(jié)構(gòu)(正確答案)所有的線性結(jié)構(gòu)都可以采用順序存儲結(jié)構(gòu)具有兩個以上指針的鏈表必定是非線性結(jié)構(gòu)循環(huán)隊列是隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)答題解析：本題的考查知識點(diǎn)是線性結(jié)構(gòu)。在計算機(jī)中存放線性表，一種最簡單的方法是順序存儲，也稱為順序分配。故本題答案為B.2.4棧和隊列[單選題]*1、設(shè)棧的存儲空間為S(1:50),初始狀態(tài)為top=51.現(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=50,則棧中的元素個數(shù)為______。(正確答案)A.50B、0C、1D、49答題解析：本題的考查知識點(diǎn)是棧。棧是限定在一端進(jìn)行插入與刪除的線性表。棧有向上生長堆棧和向下生長堆棧之分，當(dāng)棧是倒著壓的時候，存放一個元素之后，top=51-1=50,存兩個元素之后，top=51-2=49,因此當(dāng)top=50時，棧中有51-50=1個元素。所以本題答案為C。2、設(shè)棧的存儲空間為S(1:m),初始狀態(tài)為top=m+1.經(jīng)過一系列入棧與退棧操作后，top=1.現(xiàn)又要將一個元素進(jìn)棧，棧頂指針top值變?yōu)開_____。[單選題]*A、2(正確答案)B、發(fā)生棧滿的錯誤C、mD、0答題解析：初始狀態(tài)為top=m+1,也就是說，棧是向上增長的，每次壓入一個元素，棧的第3頁TOP指針向上移動一位。當(dāng)壓入第一個元素時，TOP指針指向m+1-1=m當(dāng)壓入第二個元素時，TOP指針指向m+1-2=m-1。以此類推，top=1時，棧是滿的，所以再將一個元素進(jìn)棧時，會發(fā)生棧滿的錯誤。所以本題答案選B.3、設(shè)棧的順序存儲空間為S(1:m),初始狀態(tài)為top=m+1.現(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=0,則棧中的元素個數(shù)為。[單選題]*A、m+1(正確答案)B、1C、不可能D、m答題解析：本題考查知識點(diǎn)是棧。在棧的順序存儲空間S(1:m)中，S(bottom)通常為棧底元素，S(top)為棧頂元素。top=0表示?？?；top=m表示棧滿。所以此時棧中沒有元素。選項C正確。4、設(shè)棧的存儲空間為S(1:60),初始狀態(tài)為top=61.現(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=1,則棧中的

A、59B、0C、1D、60答題解析：本題的考查知識點(diǎn)是棧。在棧中，棧頂指針的動態(tài)變化反映了棧中元素的變化情況。故本題答案選D.7、設(shè)棧的存儲空間為S(1:50),初始狀態(tài)為top=0.現(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=51,則棧中的元素個數(shù)為_______。A、1B、50C、0D、不可能答題解析：本題的考查知識點(diǎn)是棧。棧是限定在一端進(jìn)行插入與刪除的線性表。在棧的順序存儲空間S（1:m)中，S(bottom)通常為棧底元素（在棧非空的情況下），S(top)為棧頂元素。Top=0表示?？?，top=m表示棧滿。入棧運(yùn)算時指在棧頂位置插入一個新元素（即top加1)退棧運(yùn)算是指取出棧頂元素賦給一個指定的變量（即top減1).棧中的元素一共50個，所以top的最大值為50.故本題答案為D.[單選題]*

8、設(shè)棧的存儲空間為S(1:50),初始狀態(tài)為top=-1.現(xiàn)經(jīng)過一系列正常的入棧與退棧操作后，top=30,則棧中棧是一種特殊的線性表，這種線性表只能在固定的一端進(jìn)行插入和刪除操作，允許插入和刪除的一端稱為棧頂，另一端稱為棧底。一個新元素只能從棧頂一端進(jìn)入，刪除時，只能刪除棧頂?shù)脑?，即剛剛被插入的元素。這表明棧的運(yùn)算規(guī)則是"先進(jìn)后出"（或稱"后進(jìn)先出"）。在棧頂進(jìn)行插入運(yùn)算，稱為進(jìn)棧（或入棧），在棧頂進(jìn)行刪除運(yùn)算，稱為退棧（或出棧）。本題中，依次進(jìn)棧，即依次插入元素A、B、C、D、E、F，依次退棧三次FED，并將的三個元素XYZ依次入隊，則元素退隊的順序為FEDZYXCBA。所以本題答案為B。12、循環(huán)隊列的存儲空間為Q（1：200），初始狀態(tài)為front=rear=200。經(jīng)過一系列正常的入隊與退隊操作后，front=rear=1，則循環(huán)隊列中的元素個數(shù)為______。A、1B、0或200(正確答案)C、199D、2答題解析：本題考查知識點(diǎn)是循環(huán)隊列。循環(huán)隊列是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。在隊列中，隊是指針rear與隊頭指針ront共同反映了以列中元素動態(tài)變化的情況。在循環(huán)以列中，用隊尾指針rear指向隊列中的隊尾元素，用隊頭指針front指向隊頭元素的前一個位置，13、設(shè)循環(huán)隊列為Q(1：m),初始狀態(tài)為front=rear=m?，F(xiàn)經(jīng)一系列入隊與退隊操作后，front=rear=m-1,則[單選題]*______。(正確答案)A、該循環(huán)隊列已空B、該循環(huán)隊列已滿該循環(huán)隊列中有1個元素該循環(huán)隊列已空或已滿答題解析：本題考查知識點(diǎn)是循環(huán)隊列。循環(huán)隊列是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。在隊列中，隊尾指針rear與隊頭指針front共同反映了隊列中元素動態(tài)變化的情況。在循環(huán)隊列中，用隊尾指針rear指向隊列中的隊尾元素，用隊頭指針front指向隊頭元素的前一個位置，因此從隊頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間所有的元素均為隊列中的元素，由循環(huán)隊列的動態(tài)變化的過程可以看出，當(dāng)循環(huán)隊列滿時有front=rear,而當(dāng)循環(huán)隊列空時也有fron=rear.既在循環(huán)隊列中，當(dāng)front=rear時，不能確定是隊列滿還是隊列空。所以本題答案為D.某循環(huán)隊列的存儲空間為Q(1:m),初始狀態(tài)為front=rear=m.現(xiàn)經(jīng)過一系列的入隊操作和退隊操作后，front=m,rear=m-1,則該循環(huán)隊列中的元素個數(shù)為_____。A、mB、m-1C、1D、0答題解析：本題考查知識點(diǎn)是循環(huán)隊列。循環(huán)隊列是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。在隊列中，隊尾指針rear與隊頭指針front共同反映了隊列中元素動態(tài)變化的情況。在循環(huán)隊列中，用隊尾指針rear指向隊列中的隊尾元素，用隊頭指針front指向隊頭元素的前一個位置，因此從隊頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間所有的元素均為隊列中的元素。所以本題答案為B.經(jīng)過一系列的入隊操作和退隊操作后，頭指針（front=m)，尾指針（rear=m-1)說明入隊m-1次，退隊m次，已經(jīng)形成了循環(huán)效果。所以公式m+(m-1)-m，得出隊列中有元素m-1個。本題的正確答案：B。設(shè)循環(huán)隊列的存儲空間為Q(1:50),初始狀態(tài)為front=rear=50.現(xiàn)經(jīng)過一系列入隊與退隊操作后，front=rear=1,此后又正常地插入了兩個元素。最后該隊列中的元素個數(shù)為_____。A、1B、2C、3D、52答題解析：本題考查知識點(diǎn)是循環(huán)隊列。循環(huán)隊列是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。由循環(huán)隊列動態(tài)變化過程可以看出，當(dāng)循環(huán)隊列滿時有front=rear,當(dāng)循環(huán)隊列空時也有front=rear.即在循環(huán)隊列中，當(dāng)front=rear時，不能確定是隊列滿還是隊列空。題目中，front=rear=1時，又正常插入了兩個元素，說明隊列在正常插入兩個元素前，該隊列為空。因為之后插入了兩個元素，故最后該隊列中的元素個數(shù)為2.所以本題答案為B.循環(huán)隊列的存儲空間為Q(1:50),初始狀態(tài)為front=rear=50.經(jīng)過一系列正常的入隊與退隊操作后，front=rear=25,此后又正常地插入了一個元素，則循環(huán)隊列中的元素個數(shù)為______。A、51B、49C、50D、1，或50且產(chǎn)生上溢錯誤答題解析：本題考查知識點(diǎn)是循環(huán)隊列。循環(huán)隊列是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。經(jīng)過一系列的入隊操作和退隊操作后，頭指針（front=25)尾指針（rear=25)說明入隊25次，退隊25次，此時隊列中有零個元素或隊列滿，此后又正常地插入了一個元素，說明隊列滿的情況是不可能的，所以此時隊列中元素個數(shù)為1或50且產(chǎn)生上溢錯誤。所以本題答案為D。17、循環(huán)隊列的存儲空間為Q(1:40),初始狀態(tài)為front=rear=40.經(jīng)過一系列正常的入隊與退隊操作后，front=rear=15,此后又正常地退出了一個元素，則循環(huán)隊列中的元素個數(shù)為______。A、16B、39，或0且產(chǎn)生下溢錯誤C、9D、14答題解析：本題考查知識點(diǎn)是循環(huán)隊列。初始狀態(tài)為front=rear,說明隊列為滿或空。經(jīng)過一系列的入隊操作和退隊操作后，頭指針（front=15)尾指針（rear=15)說明入隊15次，退隊15次，此時隊列依舊為滿或空，此后又正常地退出了一個元素，此時隊列中元素個數(shù)為39或0且產(chǎn)生下溢錯誤.所以本題答案為B.18、設(shè)循環(huán)隊列的存儲空間為Q(1:100),初始狀態(tài)為空?，F(xiàn)經(jīng)過一系列正常操作后，front=49,則循環(huán)隊列中的元素個數(shù)為。A、不確定B、49C、51D、50答題解析：本題的考查知識點(diǎn)是循環(huán)隊列。循環(huán)隊列是將隊列存儲空間的最后一個位置繞到第一個位置，形成邏輯上的環(huán)狀空間，供隊列循環(huán)使用。經(jīng)過一系列的正常操作后，頭指針front=49只能確定出隊49次，不能確定入隊次數(shù)，所以不能確定此時隊列中元素的個數(shù)。故本題答案為A.19、循環(huán)隊列的存儲空間為Q(1:100),初始狀態(tài)為front=rear=100.經(jīng)過一系列正常的入隊與退隊操作后，front=rear=99,則循環(huán)隊列中的元素個數(shù)為。A、0或100B、1C、2D、99答題解析：本題考查知識點(diǎn)是循環(huán)隊列。當(dāng)隊頭和隊尾指針指向同一個元素時，隊列為空或隊列為滿。故所以本題答案為A.20、某帶鏈的隊列初始狀態(tài)為front=rear=NULL.經(jīng)過一系列正常的入隊與退隊操作后，front=10,rear=5.該隊列中的元素個數(shù)為______。A、4B、5C、不確定D、6答題解析：本題考查知識點(diǎn)是循環(huán)隊列。在鏈?zhǔn)酱鎯Ψ绞街?，每個結(jié)點(diǎn)有兩部分組成，一部分為數(shù)據(jù)域，一部分為指針域，front=rear時說明只有一個元素，其他情況無法判斷。所以本題答案為C.21、某帶鏈的隊列初始狀態(tài)為front=rear=NULL.經(jīng)過一系列正常的入隊與退隊操作后，front=rear=10.該隊列中的元素個數(shù)為_______。A、1B、01或0[單選題]*不確定(正確答案)答題解析：本題的考查知識點(diǎn)是帶鏈隊列。在初始狀態(tài)為front=rear=NULL的帶鏈隊列入隊時，如果插入的結(jié)點(diǎn)既是隊首結(jié)點(diǎn)又是隊尾結(jié)點(diǎn)，則rear和front同時指向這個結(jié)點(diǎn)；否則在循環(huán)隊列的隊尾加入一個新元素，rear指向新增結(jié)點(diǎn)的數(shù)據(jù)域，rear＋1,front不變。退隊時，在循環(huán)隊列的排頭位置退出一個元素并賦給指定的變量，front指向第二個結(jié)點(diǎn)的數(shù)據(jù)域，front+1,rear不變。當(dāng)front=rear=10時，front和rear同時指向這個唯一元素，所以該隊列中的元素個數(shù)為1.故本題答案為A.22、下列處理中與隊列有關(guān)的是______。[單選題]*A、操作系統(tǒng)中的作業(yè)調(diào)度(正確答案)B、執(zhí)行程序中的過程調(diào)用C、執(zhí)行程序中的循環(huán)控制D、以上說法均不正確答題解析：本題考查知識點(diǎn)隊列。在計算機(jī)系統(tǒng)中，如果一次只能執(zhí)行一個用戶程序，則在多個用戶程序需要執(zhí)行時，這些用戶程序必須先按照到來的順序進(jìn)行排隊等待。這通常是由計算機(jī)操作系統(tǒng)來進(jìn)行管理的。在操作系統(tǒng)中，用一個線性表來組織管理用戶程序的排隊執(zhí)行，原則是：初始線性表為空；當(dāng)有用戶程序到來時，將該用戶程序加入到線性表的末尾進(jìn)行等待；當(dāng)計算機(jī)系統(tǒng)執(zhí)行完當(dāng)前的用戶程序后，就從線性表的頭部取出一個用戶程序執(zhí)行。是按照先進(jìn)先出的原則進(jìn)行操作的。所以本題答案為A.23、下列敘述中正確的是_____。[單選題]*有兩個指針域的鏈表一定是二叉樹的存儲結(jié)構(gòu)(正確答案)二分查找適用于任何存儲方式的有序表循環(huán)隊列是隊列的一種存儲結(jié)構(gòu)所有二叉樹均不適合用順序存儲結(jié)構(gòu)答題解析：24、下列敘述中正確的是_____。[單選題]*在循環(huán)隊列中，隊頭指針和隊尾指針的動態(tài)變化決定隊列的長度(正確答案)在循環(huán)隊列中，隊尾指針的動態(tài)變化決定隊列的長度.在帶鏈的隊列中，隊頭指針與隊尾指針的動態(tài)變化決定隊列的長度在帶鏈的棧中，棧頂指針的動態(tài)變化決定棧中元素的個數(shù)答題解析：本題的考查知識點(diǎn)是循環(huán)隊列。在循環(huán)隊列中，用隊尾指針rear指向隊列中的隊尾元素，用排頭指針front指向排頭元素的前一個位置，因此，從排頭指針front指向的后一個位置直到隊尾指針rear指向的位置之間所有的元素均為隊列中的元素。我的答案：故本題答案選A.2.5線性鏈表[填空題]_________________________________1、下列敘述中正確的是_____。[單選題]*所謂有序表是指在順序存儲空間內(nèi)連續(xù)存放的元素序列(正確答案)有序表只能順序存儲在連續(xù)的存儲空間內(nèi)有序表可以用鏈接存儲方式存儲在不連續(xù)的存儲空間內(nèi)任何存儲方式的有序表均能采用二分法進(jìn)行查找答題解析：本題考查知識點(diǎn)是有序表。有序表具有兩個基本特點(diǎn)：1)所有元素所占的存儲空間是不連續(xù)的。2)各數(shù)據(jù)元素的存儲空間與按邏輯順序依次存放可以不一致。所以本題答案為C.[填空題]_________________________________2、帶鏈的棧與順序存儲的棧相比，其優(yōu)點(diǎn)是_____。[單選題]*入棧與退棧操作方便(正確答案)可以省略棧底指針入棧操作時不會受棧存儲空間的限制而發(fā)生溢出以上選項都不是答題解析：本題考查知識點(diǎn)是鏈?zhǔn)酱鎯Y(jié)構(gòu)和順序存儲結(jié)構(gòu)的特點(diǎn)。順序存儲時如果開辟的空間已滿，則再次插入會造成“上溢錯誤”，因此不便于存儲空間的擴(kuò)充和動態(tài)分配。鏈?zhǔn)酱鎯r各數(shù)據(jù)元素的邏輯次序靠結(jié)點(diǎn)的指針來指示，結(jié)點(diǎn)空間可以動態(tài)申請和釋放。所以本題答案是C.3、下列敘述中正確的是______。[單選題]*有兩個指針域的鏈表稱為二叉鏈表(正確答案)循環(huán)鏈表是循環(huán)隊列的鏈?zhǔn)酱鎯Y(jié)構(gòu)帶鏈的棧有棧頂指針和棧底指針，因此又稱為雙重鏈表結(jié)點(diǎn)中具有多個指針域的鏈表稱為多重鏈表答題解析：本題考查知識點(diǎn)是鏈表的定義。二叉鏈表：以二叉鏈表作為樹的存儲結(jié)構(gòu)。鏈表中結(jié)點(diǎn)的兩個鏈域分別指向該結(jié)點(diǎn)的第一個孩子結(jié)點(diǎn)和第一個孩子下一個兄弟結(jié)點(diǎn)。因此A選項錯誤。循環(huán)鏈表是鏈?zhǔn)酱鎯Y(jié)構(gòu)，循環(huán)隊列是線性存儲結(jié)構(gòu)，因此B選項錯誤。雙向鏈表也叫雙鏈表，是鏈表的一種，它的每個數(shù)據(jù)結(jié)點(diǎn)中都有兩個指針，分別指向直接后繼和直接前驅(qū)。所以，從雙向鏈表中的任意一個結(jié)點(diǎn)開始，都可以很方便地訪問它的前驅(qū)結(jié)點(diǎn)和后繼結(jié)點(diǎn)。因此C選項錯誤。每個結(jié)點(diǎn)只有一個鏈域的鏈表稱為單鏈表，相反如果有多個鏈域即為多重鏈表。所以本題答案為D.4、在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，其存儲空間一般是不連續(xù)的，并且_____。[單選題]*A、前件結(jié)點(diǎn)的存儲序號小于后件結(jié)點(diǎn)的存儲序號(正確答案)B、前件結(jié)點(diǎn)的存儲序號大于后件結(jié)點(diǎn)的存儲序號C。5、在線性表的順序存儲結(jié)構(gòu)中，其存儲空間連續(xù)，各個元素所占的字節(jié)數(shù)______。A.6、能從任意一個結(jié)點(diǎn)開始沒有重復(fù)地掃描到所有結(jié)點(diǎn)的數(shù)據(jù)結(jié)構(gòu)是_____。[單選題]*A、有序鏈表B、雙向鏈表C、二叉鏈表D、循環(huán)鏈表(正確答案)7、下列敘述中錯誤的是______。[單選題]*不管是順序棧還是帶鏈的棧，在操作過程中其棧底指針均是固定不變的。(正確答案)帶鏈棧的棧底指針在操作過程中是有可能改變的。不管是順序棧還是帶鏈的棧，在操作過程中其棧頂指針均是動態(tài)變化的。順序棧的棧底指針在操作過程中是固定不變的。答題解析：本題考查的知識點(diǎn)是數(shù)據(jù)結(jié)構(gòu)。棧是一種特殊的線性表，是按照”先進(jìn)后出，后進(jìn)先出”的原則組織數(shù)據(jù)的。鏈?zhǔn)浇Y(jié)構(gòu)則把每一個存儲結(jié)點(diǎn)分兩部分：一部分用于存儲數(shù)據(jù)元素的值，稱為數(shù)據(jù)域；另一部分用于存放下一個元素的序號，稱指針域。帶鏈的棧則可以通過指針域的變化改變原有的棧的組織數(shù)據(jù)原則；而順序棧的棧底指針不變，棧頂指針改變，所以選項A錯誤。所以本題答案為A.8、下列敘述中錯誤的是______。[單選題]*循環(huán)鏈表是循環(huán)隊列的存儲結(jié)構(gòu)(正確答案)二叉鏈表是二叉樹的存儲結(jié)構(gòu)棧是線性結(jié)構(gòu)循環(huán)隊列是隊列的存儲結(jié)構(gòu)答題解析：本題的考查知識點(diǎn)是循環(huán)鏈表。隊列的順序存儲結(jié)構(gòu)一般采用循環(huán)隊列的形式。線性鏈表的插入刪除運(yùn)算過程中，對于空表和對第一個結(jié)點(diǎn)的處理必須單獨(dú)考慮，使空表與非空表的運(yùn)算不統(tǒng)一。為了克服這個缺點(diǎn)，可以采用另一種鏈接方式，即循環(huán)鏈表。故本題答案為A.9、在帶鏈棧中，經(jīng)過一系列正常的操作后，如果top=bottom,則棧中的元素個數(shù)為______。[單選題]*A、1(正確答案)B、0C、0或1D、棧滿答題解析：本題的考查知識點(diǎn)是棧。棧頂指針top動態(tài)反映了棧中元素的變化情況，棧元素入棧時在棧頂插入一個新元素，top指向新結(jié)點(diǎn)的數(shù)據(jù)域，元素退棧時取出棧頂元素并賦給一個指定的變量，top指向此時的第1個結(jié)點(diǎn)的數(shù)據(jù)域。如果top=bottom不等于NULL,則top=bottom同時指向唯一一個元素的數(shù)據(jù)域，此時棧中的元素個數(shù)為1；如果top=bottom=NULL,則棧中的元素個數(shù)為0.故本題答案為C.2.6樹與二叉樹[填空題]_________________________________1、設(shè)二叉樹如下：[填空題]_________________________________[單選題]*

(正確答案)B、DBGEAFHCC、DGEBHFCAD、ABCDEFGH答題解析：本題考查知識點(diǎn)是二叉樹的后序遍歷。結(jié)點(diǎn)。后序遍歷指在訪問根結(jié)點(diǎn)、退歷左子樹與追歷右子樹這三者中，首先遍歷左子樹，然后遍歷右子樹，最后訪問根結(jié)點(diǎn)，并且遍歷左、右子樹時，仍然先遍歷左子樹，然后遍歷右子樹，最后訪問根所以本題答案為C.4、某二叉樹的前序序列為ABCD,中序序列為DCBA,則后序序列為______。[單選題]*A、BADCB、DCBAC、CDABD、ABCD(正確答案)答題解析：本題考查知識點(diǎn)是二叉樹的遍歷。在先左后右的原則下，根據(jù)訪問根結(jié)點(diǎn)的次序，二又樹的遍歷可以分為3種，前序遍歷、中序遍歷和后序遍歷。前序遍歷是指在訪問根結(jié)點(diǎn)、遍歷左子樹與追歷右子樹這三者中，首先訪問根結(jié)點(diǎn)：然后遍歷左子樹，最后遍歷右子樹；并且遍歷左、右子樹時，仍然先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹。二又樹的中序遍歷指在訪問根結(jié)點(diǎn)、遍歷左子樹與遍歷右子樹這三者中，首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后退歷右子樹，井且調(diào)歷左、右子樹時，仍然先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。二又樹的后序退歷指在訪問遍歷左子樹與退歷右子樹，然后訪問根結(jié)點(diǎn)、這三者中，首先遍歷左子樹，然后訪問右子樹，最后退歷根結(jié)點(diǎn)：并且遍歷左、右子樹時，仍然先退歷左子樹，然后訪問遍歷右子樹，最后訪問根結(jié)點(diǎn)。所以本題答案為B.5、某二叉樹的中序序列為BDCA,后序序列為DCBA,則前序序列為______。[單選題]*A、DCBAB、BDCAC、ABCDD、BADC(正確答案)答題解析：本題考查知識點(diǎn)是二叉樹的遍歷。二叉樹前序遍歷順序是DLR,即先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹，并且遍歷子樹的時候也按照DLR的順序遞歸遍歷。中序遍歷順序是LDR,后續(xù)遍歷順序是LRD.由后序序列得知A為根結(jié)點(diǎn)，由中序得知B為A的左子樹，C為B的右子樹，D為C的左子樹。因此，前序序列為ABCD.6、設(shè)某二叉樹的后序序列與中序序列均為ABCDEFGH,則該二叉樹的前序序列為_______。[單選題]*A、DCBAHGFEB、ABCDEFGHC、EFGHABCDD、HGFEDCBA(正確答案)答題解析：本題考查的是二叉樹的遍歷。二叉樹的后序遍歷：后序遍歷左子樹，后序遍歷右子樹，訪問根結(jié)點(diǎn)。二叉樹的中序遍歷為：中序遍歷左子樹，訪問根結(jié)點(diǎn)，中序遍歷右子樹。由兩種遍歷順序可知，該二叉樹每個結(jié)點(diǎn)均缺失了右邊子樹，這樣造成后序和中序序列相同?；蛘?，可以根據(jù)前序遍歷和后序遍歷的特點(diǎn)，前序遍歷由根結(jié)點(diǎn)開頭，后序遍歷由根結(jié)點(diǎn)結(jié)尾，所以本題根結(jié)點(diǎn)為H.所以本題答案為D.7、設(shè)某二叉樹的前序序列與中序序列均為ABCDEFGH,則該二叉樹的后序序列為______。[單選題]*A、EFGHABCDB、HGFEDCBAC、DCBAHGFE(正確答案)D、ABCDEFGHO答題解析：本題考查的是二叉樹的遍歷。二叉樹的前序遍歷：訪問根節(jié)點(diǎn)，前序遍歷左子樹，前序遍歷右子樹。二叉樹的中序遍歷為：中序遍歷左子樹，訪問根結(jié)點(diǎn)，中序遍歷右子樹。由兩種遍歷順序可知，該二叉樹每個結(jié)點(diǎn)均缺失了左邊子樹，這樣造成前序序和中序序列相同?；蛘撸梢愿鶕?jù)前序遍歷和后序遍歷的特點(diǎn)，前序遍歷由根結(jié)點(diǎn)開頭，后序遍歷由根結(jié)點(diǎn)結(jié)尾，所以本題根結(jié)點(diǎn)為A.所以本題答案為B.8、若某二義樹中的所有結(jié)點(diǎn)值均大于其左子樹上的所有結(jié)點(diǎn)值，且小于右子樹上的所有結(jié)點(diǎn)值，則該二叉樹遍歷序列中有序的是。[單選題]*A、前序序列(正確答案)B、中序序列C、后序序列D、以上說法均不正確正確答案：B答題解析：本題考查知識點(diǎn)是二叉樹遍歷。所有結(jié)點(diǎn)值均大于左子樹的所有結(jié)點(diǎn)，且小于右子樹所有結(jié)點(diǎn)，若想該二叉樹遍歷序列有序（數(shù)值從小到大）則需要首先遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后遍歷右子樹。這樣的遍歷順序符合中序序列。所以本題答案為B.9、設(shè)非空二叉樹的所有子樹中，其左子樹上的結(jié)點(diǎn)值均小于根結(jié)點(diǎn)值，而右子樹上的結(jié)點(diǎn)值均不小于根結(jié)點(diǎn)值，則稱該二叉樹為排序二叉樹。對排序二叉樹的遍歷結(jié)果為有序序列的是______。[單選題]*A、中序序列(正確答案)B、前序序列C、后序序列D、前序序列或后序序列答題解析：本題的考查知識點(diǎn)是排序二叉樹的遍歷。排序二叉樹的性質(zhì)：按中序遍歷排序二叉樹，所得到的中序遍歷序列是一個遞增有序序列。故本題答案為A.10、在具有n個結(jié)點(diǎn)的二叉樹中，如果各結(jié)點(diǎn)值互不相同，但前序遍歷序列與中序遍歷序列相同，則該二叉樹的深度為_______（根結(jié)點(diǎn)在第1層）。[單選題]*A、n(正確答案)n/2+1n+1D、n-1答題解析：本題的考查知識點(diǎn)是二叉樹的遍歷。二叉樹的前序遍歷步驟為首先訪問根結(jié)點(diǎn)，然后前序遍歷左子樹，最后前序遍歷右子樹。中序遍歷步驟為首先中序遍歷左子樹，然后訪問根結(jié)點(diǎn)，最后中序遍歷右子樹。若前序遍歷和中序遍歷相同，則說明此二叉樹每個結(jié)點(diǎn)均缺失了左結(jié)點(diǎn)，故二叉樹每一層均有一個結(jié)點(diǎn)存在，所以深度為n.所以本題答案為A.11、某二叉樹的前序序列為ABCD,中序序列為BDCA,則該二叉樹的深度為______。[單選題]*4(正確答案)32D、不確定答題解析：本題的考查知識點(diǎn)是二叉樹的深度。二叉樹前序遍歷順序是DLR,即先訪問根結(jié)點(diǎn)，然后遍歷左子樹，最后遍歷右子樹，并且遍歷子樹的時候也按照DLR的順序遞歸遍歷。中序遍歷順序是LDR.后續(xù)遍歷順序是LRD.由前序序列得知A為根結(jié)點(diǎn)，B為A的左子樹，由中序得知C為B的右子樹，D為C的左子樹，所以深度為4.所以本題答案為A.12、設(shè)二叉樹中共有15個結(jié)點(diǎn)，其中的結(jié)點(diǎn)值互不相同。如果該二叉樹的前序序列與中序序列相同，則該二叉樹的深度為_______。[單選題]*A、15(正確答案)B、6C、4D、不存在這樣的二叉樹答題解析：本題考查的是二叉樹的遍歷。二叉樹的前序遍歷：首先訪問根結(jié)點(diǎn)，前序遍歷左子樹，前序遍歷右子樹。二叉樹的中序遍歷為：中序遍歷左子樹，訪問根結(jié)點(diǎn)，中序遍歷右子樹。若要該二叉樹的前序序列與中序序列相同，則該二叉樹每個結(jié)點(diǎn)均缺失了左子樹，只有右子樹（除葉子結(jié)點(diǎn)）。也就是說該二叉樹的每一層只有一個結(jié)點(diǎn)，故該二叉樹的深度為15.所以本題答案為A.設(shè)二叉樹中共有31個結(jié)點(diǎn)，其中的結(jié)點(diǎn)值互不相同。如果該二叉樹的后序序列與中序序列相同，則該二叉樹的深度為_______。A、17B、16C、31D、5答題解析：本題考查的是二叉樹的遍歷。二叉樹的后序遍歷：遍歷左子樹，遍歷右子樹，訪問根結(jié)點(diǎn)。二叉樹的中序遍歷為：中序遍歷左子樹，訪問根結(jié)點(diǎn)，中序遍歷右子樹。若要該二叉樹的后序