【計(jì)算機(jī)專業(yè)】專業(yè)課模擬題

1、計(jì)算機(jī)操作系統(tǒng)模擬試題操作系統(tǒng)模擬試題 一一、填空題（本題共25分，每題5分）1、進(jìn)程的邏輯地址到_地址的轉(zhuǎn)換，稱為重定位。2、分區(qū)管理分為_和_兩種方式。3、處理機(jī)在執(zhí)行系統(tǒng)程序時(shí)的狀態(tài)稱為_，在執(zhí)行用戶程序時(shí)的狀態(tài)稱為_。4、如果為了使所有進(jìn)程都有機(jī)會(huì)運(yùn)行，最好采用的調(diào)度算法是_。5、對記錄式文件，操作系統(tǒng)為用戶存取文件信息的最小單位是_。二、（本題滿分為10分）以打印機(jī)為例說明SPOOLING的工作原理，系統(tǒng)如何利用SPOOLING技術(shù)將打印機(jī)模擬為虛擬打印機(jī)。三、（本題滿分為10分）對于如下的頁面訪問序列：1， 2， 3， 4， 1， 2， 5， 1， 2， 3， 4， 5當(dāng)內(nèi)存塊數(shù)量

2、分別為3和4時(shí)，試問：使用FIFO、LRU置換算法產(chǎn)生的缺頁中斷是多少？（所有內(nèi)存開始時(shí)都是空的，凡第一次用到的頁面都產(chǎn)生一次缺頁中斷）四、（本題滿分為15分）某虛擬存儲(chǔ)器的用戶編程空間共32個(gè)頁面，每頁為1KB，內(nèi)存為16KB。假定某時(shí)刻一用戶頁表中已調(diào)入內(nèi)存的頁面的頁號(hào)和物理塊號(hào)的對照表如下：頁號(hào)物理塊號(hào)031721138則邏輯地址0A5C(H)所對應(yīng)的物理地址是什么？要求：寫出主要計(jì)算過程。五、（本題滿分為15分）假定具有5個(gè)進(jìn)程的進(jìn)程集合PP0,P1,P2,P3,P4,系統(tǒng)中有三類資源A，B和C。其中A類資源有10個(gè)，B類資源有5個(gè)，C類資源有7個(gè)。假定在某時(shí)刻有如下狀態(tài)：Alloca

3、tion Max AvailableA B C A B C A B C P0 0 1 0 7 5 3 3 3 2P1 2 0 0 3 2 2 P2 3 0 2 9 0 2P3 2 1 1 2 2 2P4 0 0 2 4 3 3試給出Need，并說明當(dāng)前系統(tǒng)是否處于安全狀態(tài)，如果是，給出安全序列。如果不是，說明理由。答案一、1、物理 2、靜態(tài)分區(qū) 動(dòng)態(tài)分區(qū) 3、系統(tǒng)態(tài) 用戶態(tài)4、輪轉(zhuǎn)法 5、記錄二、當(dāng)用戶進(jìn)程請求打印輸出時(shí)，Spooling系統(tǒng)同意打印輸出，但并不真正把打印機(jī)分配給該用戶進(jìn)程，而只為它做兩件事：1，由輸出進(jìn)程在輸出井中為之申請一空閑盤塊區(qū)，并將要打印的數(shù)據(jù)送入其中；2，輸出進(jìn)程再

4、為用戶進(jìn)程申請一張空白的用戶請求打印表，并將用戶的打印要求填入表中，再將該表掛到請求打印隊(duì)列之上。如果還有進(jìn)程要求打印輸出，系統(tǒng)仍可以接受該請求，同樣做上面的工作。如果打印機(jī)空閑，輸出進(jìn)程將從請求打印隊(duì)列的隊(duì)首取出一張請求表，根據(jù)表中的要求將要打印的數(shù)據(jù)從輸出井傳送到內(nèi)存緩沖區(qū)，再由打印機(jī)進(jìn)行打印。打印完畢，輸出進(jìn)程再查看請求打印隊(duì)列中是否還有等待要打印的請求表，若有，再取出一張表，并根據(jù)其中的要求進(jìn)行打印，如此下去，直至請求隊(duì)列為空位置，輸出進(jìn)程才將自己阻塞起來，等待下次再由打印請求時(shí)才被喚醒。三、FIFO淘汰算法：內(nèi)存塊為3時(shí)，缺頁中斷（或稱缺頁次數(shù)、頁面故障）為9；內(nèi)存塊為4時(shí)，缺頁中斷

5、為10。LRU淘汰算法：內(nèi)存塊為3時(shí)，缺頁中斷為10；內(nèi)存塊為4時(shí)，缺頁中斷為8。四、125C（H）（要求寫出計(jì)算步驟）分析頁式存儲(chǔ)管理的邏輯地址分為兩部分：頁號(hào)和頁內(nèi)地址。由已知條件“用戶編程空間共32個(gè)頁面”，可知頁號(hào)部分占5位；由“每頁為1KB”，1K=210，可知內(nèi)頁地址占10位。由“內(nèi)存為16KB”，可知有16塊，塊號(hào)為4位。邏輯地址0A5C（H）所對應(yīng)的二進(jìn)制表示形式是：0001010 0101 1100 ，根據(jù)上面的分析，下劃線部分為頁內(nèi)地址，編碼 “000 10” 為頁號(hào)，表示該邏輯地址對應(yīng)的頁號(hào)為2。查頁表，得到物理塊號(hào)是4（十進(jìn)制），即物理塊地址為：01 00 ，拼接塊內(nèi)地

6、址10 0101 1100，得01 0010 0101 1100，即125C（H）。五、當(dāng)前系統(tǒng)處于安全狀態(tài)，安全序列如下求解：work = Available = (3 , 3 , 2 )尋找Needj = work = ( 3 , 3 , 2 )( j = 0 , 1 , 2 , 3 , 4)j = 1 Need1 = (1 ,2 ,3 ) = (3 , 3 , 2 )work : = (3 , 3 , 2 ) + (2 ,0,0 ) = (5 , 3 , 2 )尋找Needj= work = ( 5 , 3 , 2 )( j = 0 , 2 , 3 , 4)j = 3 Need3 = (

7、0 ,1 ,1 ) = (5 , 3 , 2 )work : = (5 , 3 , 2 ) + (2 ,1,1 ) = (7 , 4 , 3 )尋找Needj= work = (7 , 4 , 3 ) ( j = 0 ,2 , 4)j = 4 Need4 = (4 ,3 ,1 ) = (7 , 4 , 3 )work : = (7 , 4 , 3 ) + (0 ,0,2 ) = (7 , 4 , 5)尋找Needj= work = (7 , 4 , 5) (j = 0 , 2 )j = 2 Need2 = (6 ,0,0 ) = (7 , 4 , 5 )work : = (7 , 4 , 5

8、) + (3 ,0,2 ) = (10 , 4 , 7) 尋找Needj= work = (10 , 4 , 7) ( j = 0 )j = 0 work : = (10, 4 , 7 ) + (0 ,1 ,0 ) = (10 , 5 , 7)所以安全序列為P1，P3，P4，P2，P0。操作系統(tǒng)模擬試題 二一、 填空題（本題共25分，每題5分）1、 操作系統(tǒng)是計(jì)算機(jī)系統(tǒng)的一種系統(tǒng)軟件，它以盡量合理、有效的方式組織和管理計(jì)算機(jī)的_，并控制程序的運(yùn)行，使整個(gè)計(jì)算機(jī)系統(tǒng)能高效地運(yùn)行。2、 操作系統(tǒng)中，對信號(hào)量S的P原語操作定義中，使進(jìn)程進(jìn)入相應(yīng)等待隊(duì)列等待的條件是_。3、 銀行家算法中，當(dāng)一個(gè)進(jìn)程提

9、出的資源請求將導(dǎo)致系統(tǒng)從_進(jìn)入_時(shí)，系統(tǒng)就拒絕它的資源請求。4、 在請求頁式存儲(chǔ)管理中，若采用FIFO頁面淘汰算法，則當(dāng)分配的頁面數(shù)增加時(shí)，_的次數(shù)可能增加也可能減少。5、 采用段式存儲(chǔ)管理的系統(tǒng)中，若地址用24位表示，其中8位表示段號(hào)，則允許每段的最大長度是_。 二、（本題滿分為10分）在操作系統(tǒng)中，P操作和V操作各自的動(dòng)作是如何定義的？三、（本題滿分為10分）假設(shè)一個(gè)活動(dòng)頭磁盤有200道, 編號(hào)從0-199. 當(dāng)前磁頭正在143道上服務(wù), 并且剛剛完成了125道的請求. 現(xiàn)有如下訪盤請求序列(磁道號(hào)):86, 147, 91, 177, 94, 150, 102, 175, 130試給出采

10、用下列算法后磁頭移動(dòng)的順序和移動(dòng)總量(總磁道數(shù)).(1). 先來先服務(wù)(FCFS)磁盤調(diào)度算法.(2). 最短尋道時(shí)間優(yōu)先(SSTF)磁盤調(diào)度算法.(3).掃描法(SCAN)磁盤調(diào)度算法.(假設(shè)沿磁頭移動(dòng)方向不再有訪問請求時(shí), 磁頭沿相反方向移動(dòng).)四、（本題滿分為15分）設(shè)系統(tǒng)中有三類資源A、B和C，又設(shè)系統(tǒng)中有5個(gè)進(jìn)程P1，P2，P3，P4和P5.在T0時(shí)刻系統(tǒng)狀態(tài)如下：最大需求量 已分配資源量 剩余資源量A B C A B C A B CP1 8 6 4 1 2 1 2 1 1P2 4 3 3 3 1 1P3 10 1 3 4 1 3P4 3 3 3 3 2 2P5 5 4 6 1 1

11、3(1)系統(tǒng)是否處于安全狀態(tài)？如是，則給出進(jìn)程安全序列.(2)如果進(jìn)程P5申請1個(gè)資源類A、1個(gè)資源類B和1個(gè)資源類C，能否實(shí)施分配？為什么？五、（本題滿分為15分）有n+1個(gè)進(jìn)程A1, A2, .An 和 B:(1)A1,.An通過同一個(gè)緩沖區(qū)各自不斷地向B發(fā)送消息, B不斷地取消息, 它必 須取走發(fā)來的每一個(gè)消息. 剛開始時(shí)緩沖區(qū)為空. 試用P、V操作正確實(shí)現(xiàn)之. (2)若緩沖區(qū)個(gè)數(shù)增至m個(gè), 試用P、V操作實(shí)現(xiàn)正確的通訊.答案：一、1、資源 2、S0 3、安全狀態(tài) 不安全狀態(tài)4、缺頁中斷 5、216二、在操作系統(tǒng)中，P操作和V操作各自的動(dòng)作是如何定義的？答：P操作順序執(zhí)行下述兩個(gè)動(dòng)作：信

12、號(hào)量的值減1，即S=S-1； 如果S0，則該進(jìn)程繼續(xù)執(zhí)行；如果S0，則把該進(jìn)程的狀態(tài)置為阻塞態(tài)，把相應(yīng)的PCB連入該信號(hào)量隊(duì)列的末尾，并放棄處理機(jī)，進(jìn)行等待（直至其它進(jìn)程在S上執(zhí)行V操作，把它釋放出來為止）。V操作順序執(zhí)行下述兩個(gè)動(dòng)作：S值加1，即S=S+1；如果S0，則該進(jìn)程繼續(xù)運(yùn)行； 如果S0，則釋放信號(hào)量隊(duì)列上的第一個(gè)PCB（即信號(hào)量指量指針項(xiàng)所指向的PCB）所對應(yīng)的進(jìn)程（把阻塞態(tài)改為就緒態(tài)），執(zhí)行V操作的進(jìn)程繼續(xù)運(yùn)行。三、（1）86，147，91，177，94，150，102，175，130（2）當(dāng)前磁頭在143道上：147，150，130，102，94，91，86，175，177（3

13、）當(dāng)前磁頭在143道上，并且剛剛完成125道的請求147，150，175，177，130，102，94，91，86四、 （1）最大需求量 已分配資源量 剩余資源量 尚需要量A B C A B C A B C A B CP1 8 6 4 1 2 1 2 1 1 7 4 3P2 4 3 3 3 1 1 1 2 2P3 10 1 3 4 1 3 6 0 0P4 3 3 3 3 2 2 0 1 1P5 5 4 6 1 1 3 4 3 3系統(tǒng)是處于安全狀態(tài)，安全序列為：P4，P2，P1，P3，P5（2）P5申請（1，1，1）最大需求量 已分配資源量 剩余資源量 尚需要量A B C A B C A B C

14、 A B CP1 8 6 4 1 2 1 1 0 0 7 4 3P2 4 3 3 3 1 1 1 2 2P3 10 1 3 4 1 3 6 0 0P4 3 3 3 3 2 2 0 1 1P5 5 4 6 2 2 4 3 2 2不能實(shí)施分配，因?yàn)榉峙浜笳也坏桨踩蛄?，系統(tǒng)將處于不安全狀態(tài).五、(1) n+1個(gè)進(jìn)程P1, P2, .,Pn 和 Q ，一個(gè)緩沖區(qū)Pi( i=1,.,n):Repeat生產(chǎn)消息；P(S1);向緩沖區(qū)送消息；V(S2)Until FalseQ: Repeat P(S2);從緩沖區(qū)取消息；V(S1)；處理消息；Until FalseS1=1, S2=0(2)k個(gè)緩沖區(qū)Pi

15、( i=1,.,n):Repeat生產(chǎn)消息；P(S1);P(mutex);向BUFFERl中送消息；l:=(l+1) mod k;V(mutex);V(S2) Until False S1=k;S2=0;mutex=1;l=0;ll=0Q: RepeatP(S2);P(mutex);從BUFFERll取消息；ll:=(ll+1) mod k;V(mutex);V(S1)Until False 微機(jī)原理與接口技術(shù)（七）一、填空題（每題5分，共5個(gè)題，總分25分）18086/8088 CPU具有兩種外部中斷，它們是_和_。2（234）10_2_163第二代CPU使用的電子器件是_；第三代CPU采用

16、的電子器件是_。4EIA RS-232C 的TXD和RXD數(shù)據(jù)線上的電平邏輯1=_V；邏輯0=_V。5在8086中，段寄存器CS1200H，指令指針寄存器IPFF00H，此時(shí)指令的物理地址為：_。二、（10分）什么是中斷源？8086通常的中斷源有哪些？三、（10分）何為邏輯地址？何為物理地址？它們倆者之間有何關(guān)系？四、（15分）編寫程序段實(shí)現(xiàn)如下功能：（1）將立即數(shù)17H送DL；立即數(shù)7FH送AL。（2）從DX所指的端口中讀取一個(gè)字節(jié)至AL；將AX中的一個(gè)字輸出至DX和DX1所指的端口中。五、（15分）在1000H開始的內(nèi)存中，放有1000個(gè)ASCII字符，請?jiān)O(shè)計(jì)一程序，將這串ASCII字符以

17、異步串行通信方式從8255A PB0輸出，采用偶校驗(yàn)、一位起始位、一位終止位、波特率500 (可調(diào)用1ms軟件定時(shí)程序 “D1MS”)。8255A接口連接圖如下：8255A工作方式控制字如下D7D6D5D4D3D2D1D0特征位A組方式 A口C47B組方式B口 C03答案一、1、 可屏蔽中斷，非屏蔽中斷2、 11101010，EA3、 半導(dǎo)體，集成電路4、-3-15，+3+155、21F00H二、引起中斷的原因或能發(fā)出中斷申請的來源稱為中斷源。通常中斷源有以下幾種：（1）一般的輸入輸出設(shè)備。如鍵盤、行打印機(jī)等。（2）數(shù)據(jù)通道中斷源。如磁盤、磁帶等。（3）實(shí)時(shí)時(shí)鐘。（4）故障源。如電源掉電等。三

18、、物理地址是存儲(chǔ)器的實(shí)際地址，一個(gè)存儲(chǔ)單元的物理地址是惟一，邏輯地址為程序設(shè)計(jì)中所使用的存儲(chǔ)器地址，它由段基址和地內(nèi)偏移地址兩部份構(gòu)成，物理地址=段基址16偏移地址，可見一個(gè)存儲(chǔ)單元的邏輯地址可以有若干個(gè)四、（1）MOV DL,17HMOVAL,7FH（2）IN AL,DXOUTDX,AX五、MOV SI ,1000HMOV CX ,1000MOV DX,30FH MOV AL ,10000000B OUT DX,AL MOV DX,30DHMOV AL,0FFH OUT DX ,ALCALL D1MSCALL D1MSL1: MOV BL ,8MOV AL ,0OUT DX ,AL CALL

19、 D1MSCALL D1MSMOV AL ,SIAND AL ,ALJP L2OR AL ,80HL2: OUT DX ,ALCALL D1MSCALL D1MSROR AL,1DEC BLJNZ L2MOV AL ,0FFHOUT DX ,ALCALL D1MSCALL D1MSINC SI LOOP L1HLT；微機(jī)原理與接口技術(shù)（九）一、填空題（每題5分，共5個(gè)題，總分25分）1、數(shù)制轉(zhuǎn)換：247.86=H =_BCD2、8086CPU中典型總線周期由_個(gè)時(shí)鐘周期組成，其中T1期間，CPU輸出_信息。3、異步串行通信數(shù)據(jù)格式由起始位、 位、 位和 位等4部分組成。4、如果一個(gè)程序在執(zhí)行前

20、（CS）=0A7F0H，（IP）=2B40H，該程序的起始物理地址是_。5、用4K4bit的存儲(chǔ)器芯片構(gòu)成32KB的存儲(chǔ)器, 所需要的芯片數(shù)是 片。二、（10分）EU與BIU各自的功能是什么？如何協(xié)同工作？三、（10分）8086如何響應(yīng)一個(gè)可屏蔽中斷請求？簡述響應(yīng)過程。四、（15分）用其他指令完成和下列指令一樣的功能:(1)REP MOVSB (2) REP LODSB (3) REP STOSB (4) REP SCASB五、（15分）已知某8255A在系統(tǒng)中占用888BH號(hào)端口地址，現(xiàn)欲安排其PA，PB，PC口全部為輸出，PA，PB口均工作于方式0模式，并將PC6置位，使PC3復(fù)位，試編寫

21、出相應(yīng)的初始化程序。答案一、1、F7.DCH 001001000111.10000110 BCD 2、4個(gè) 地址 3、數(shù)據(jù) 奇偶校驗(yàn) 停止 4、0AAA40H 5、16二、EU是執(zhí)行部件，主要的功能是執(zhí)行指令。BIU是總線接口部件，與片外存儲(chǔ)器及I/O接口電路傳輸數(shù)據(jù)。EU經(jīng)過BIU進(jìn)行片外操作數(shù)的訪問，BIU為EU提供將要執(zhí)行的指令。EU與BIU可分別獨(dú)立工作，當(dāng)EU不需BIU提供服務(wù)時(shí)，BIU可進(jìn)行填充指令隊(duì)列的操作。三、當(dāng)8086收到INTR的高電平信號(hào)時(shí)，在當(dāng)前指令執(zhí)行完且IF=1的條件下，8086在兩個(gè)總線周期中分別發(fā)出INTA#有效信號(hào)；在第二個(gè)INTA#期間，8086收到中斷源發(fā)

22、來的一字節(jié)中斷類型碼；8086完成保護(hù)現(xiàn)場的操作，CS、IP內(nèi)容進(jìn)入堆棧，請除IF、TF；8086將類型碼乘4后得到中斷向量表的入口地址，從此地址開始讀取4字節(jié)的中斷處理程序的入口地址，8086從此地址開始執(zhí)行程序，完成了INTR中斷請求的響應(yīng)過程。四、(1) LOOP1:MOVAL,BYTE PTR SIMOVES:BYTE PTR DI, ALINC SI 或: DEC SIINC DI 或: DEC DILOOPLOOP1(2)LOOP1:MOVAL, BYTE PTR SIINC SI 或: DEC SILOOPLOOP1(3)LOOP1:MOVES:BYTE PTR DI, ALIN

23、C DI 或: DEC DILOOPLOOP1(4)LOOP1:CMPAL,ES:BYTE PTR DIJE EXITINC DI 或: DEC DILOOPLOOP1EXIT:五、MOV AL， 80H OUT 8BH，AL MOV AL，ODH OUT 8BH，AL MOV AL，06HOUT 8BH，AL 微機(jī)原理與接口技術(shù)（十）一、填空題（每題5分，共5個(gè)題，總分25分）1、10111B用十六進(jìn)制數(shù)表示為 H，八進(jìn)制數(shù)表示為 O。2、微機(jī)的系統(tǒng)總線是連接CPU、存儲(chǔ)器及I/O的總線，AB表示 總線，DB表示 總線，CB表示 總線。3、8086CPU是一個(gè) 位的微處理器，具有 位數(shù)據(jù)總線

24、， 位地址總線，可尋址空間為 。4、8086CPU可分為 、 兩大部分。5、用8k1位的存儲(chǔ)芯片，組成8k16位的存儲(chǔ)器，需用 擴(kuò)展，要用 片。二、（10分）8086基本總線周期是如何組成的？各狀態(tài)中完成什么基本操作？三、（10分）設(shè)采用8251A進(jìn)行串行異步傳輸，每幀信息對應(yīng)1個(gè)起始位，7個(gè)數(shù)據(jù)位，1個(gè)奇/偶校驗(yàn)位，1個(gè)停止位，波特率為4800，則每分鐘能傳輸?shù)淖畲笞址麛?shù)為多少個(gè)？四、（15分）某系統(tǒng)中8253占用地址為100H103H。初始化程序如下：MOV DX， 103HMOV AL， 16HOUT DX， ALSUB DX， 3OUT DX， AL問：1、此段程序是給8253的哪一個(gè)

25、計(jì)數(shù)器初始化？安排工作在哪種工作方式？2、若該計(jì)數(shù)器的輸入脈沖的頻率為1MHZ，則其輸出脈沖的頻率是多少？五、（15分）根據(jù)下列要求編寫一個(gè)匯編語言程序:：代碼段的段名為COD_SG數(shù)據(jù)段的段名為DAT_SG堆棧段的段名為STK_SG變量HIGH_DAT所包含的數(shù)據(jù)為95將變量HIGH_DAT裝入寄存器AH，BH和DL程序運(yùn)行的入口地址為START答案一、1、11，212、地址，數(shù)據(jù)，系統(tǒng)3、16，16，16，64KB4、RAM，ROM5、分段，2二、基本總線周期由4個(gè)時(shí)鐘(CLK)周期組成，按時(shí)間順序定義為T1、T2、T3、T4。在T1期間8086發(fā)出訪問目的地的地址信號(hào)和地址鎖存選通信號(hào)A

26、LE；T2期間發(fā)出讀寫命令信號(hào)RD#、WR#及其它相關(guān)信號(hào)；T3期間完成數(shù)據(jù)的訪問；T4結(jié)束該總線周期。三、每幀占1+7+1+1=10位，波特率為4800 bit/s,故每分鐘能傳送的最大字符數(shù)為4800*60/10=28800個(gè)四、計(jì)數(shù)器0 工作于方式3 45.454KHZ 五、DAT_SG SEGEMNTHIGH_DATDB 95DAT_SG ENDS;STK_SG SEGMENTDW 64 DUP(?)STK_SG ENDS;COD_SG SEGMENTMAIN PROC FARASSUMECS: COD_SG, DS: DAT_SG, SS: STK_SGSTART:MOV AX, D

27、AT-SGMOV DS, AXMOV AH, HIGH_DATMOV BH, AHMOVDL, AHMOVAH, 4CHINT 21HMAIN ENDPCOD_SGENDSEND START數(shù)據(jù)結(jié)構(gòu)（八）一、填空題（本大題共有5個(gè)題，每題5分，共25分，將正確答案填在空格處）1.設(shè)棧的輸入序列是1，2，n，若輸出序列的第一個(gè)元素是n,則第i個(gè)輸出元素是 。2.廣義表（a，b，c，d）的表尾是 。3.有一棵非空的二叉樹（假設(shè)第0層為根結(jié)點(diǎn)）,其第i層上至多有 個(gè)結(jié)點(diǎn)。4.已知有序表為（12，18，24，35，47，50，62，83，90，115，134），當(dāng)用折半法查找時(shí)90時(shí)，需進(jìn)行 次查找可

28、確定成功。5.已知二維數(shù)組A10.205.10,每個(gè)數(shù)組元素占4個(gè)存儲(chǔ)單元，若按行優(yōu)先順序存放數(shù)據(jù)元素，a105的存儲(chǔ)地址是1000，則a189的存儲(chǔ)地址是 。二、（本題滿分為10分）證明：樹中的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的度數(shù)加1。三、（本題滿分為10分）如圖所示有向圖，采用dijkstra算法求出從頂點(diǎn)0到其它頂點(diǎn)的最短路徑，并說明整個(gè)計(jì)算過程。四、（本題滿分為15分）已知，一棵二叉樹中根遍歷的結(jié)點(diǎn)序列為DCBGEAHFIJK，先根遍歷的結(jié)點(diǎn)序列為ABCDEGFHJIK，畫出對應(yīng)的二叉樹，并寫出后根遍歷的結(jié)點(diǎn)序列。五、（本題滿分為15分）試寫出希爾排序的算法。答案：一、1.n-i+1 2.（） 3

29、.2i 4.2 5.1208二、根據(jù)樹的定義，在一棵樹中，除樹根結(jié)點(diǎn)外，每個(gè)結(jié)點(diǎn)有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)，也就是說，每個(gè)結(jié)點(diǎn)與指向他的一個(gè)分支一一對應(yīng)，所以除樹根之外的結(jié)點(diǎn)數(shù)等于所有結(jié)點(diǎn)的分支數(shù)（度數(shù)），從而可得樹中的結(jié)點(diǎn)數(shù)等于所有節(jié)點(diǎn)的度數(shù)加1.三、（1）選4 （2）選1（3）選4 （4）選6（5）選7 （6）選8或選6四、五、見課本數(shù)據(jù)結(jié)構(gòu)（九）一、填空題（本大題共有5個(gè)題，每題5分，共25分，將正確答案填在空格處）1.在一個(gè)長度為n的順序表中刪除第i個(gè)元素（0in-1）時(shí)，需向前移動(dòng) 個(gè)元素。2.廣義表（a）,(b),c),(d)）的長度是 。3.深度為K的完全二叉樹至少有 個(gè)結(jié)點(diǎn)。4.在一

30、棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n0,度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，則有n0。5.長度為255的表，采用分塊查找法，每塊的最佳長度是 。二、（本題滿分為10分）有7個(gè)帶權(quán)結(jié)點(diǎn)，其權(quán)值分別為：4，7，8，2，5，16，30，試以它們?yōu)槿~子結(jié)點(diǎn)構(gòu)造一棵哈夫曼樹（要求按每個(gè)結(jié)點(diǎn)的左子樹根結(jié)點(diǎn)的權(quán)值小于等于右子樹根結(jié)點(diǎn)的權(quán)值的次序構(gòu)造）三、（本題滿分為10分）在帶頭結(jié)點(diǎn)的單鏈表中查找數(shù)據(jù)域?yàn)閤的結(jié)點(diǎn)，并返回首次找到的節(jié)點(diǎn)的序號(hào)。四、（本題滿分為15分）設(shè)有一組關(guān)鍵字（19，01，23，14，55，20，84，27，68，11，10，77），采用散列函數(shù)H(key)=key%13，采用開放定址法的二次探測再

31、散列方法解決沖突，試在0到18的形式列地址空間中對該關(guān)鍵字序列構(gòu)造散列表。五、（本題滿分為15分）二叉樹采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，試設(shè)計(jì)一個(gè)算法計(jì)算一棵給定二叉樹的所有結(jié)點(diǎn)數(shù)。答案：一、1.n-i-1 2.3 3.2k-1 4.n2 5.15二、構(gòu)造的哈夫曼樹為：三、int locate(SNode *p,ElemType x)int i=0;SNode*q=pnext;while(q!=null&qdata!=x)q=qnext;i+;if(q=null)return(-1);elsereturn(i); 四、計(jì)算散列地址：H(19)=19%13=6 H(01)=01%13=1 H(23)=23%1

32、3=10H(14)=14%13=1(沖突) H1=(1+12)%19=2 H(55)=55%13=3 H(20)=20%13=7 H(84)=84%13=6(沖突) H1=(6+12)%19=7（沖突） H2=(6-12)%19=5H(27)=27%13=1（沖突） H1=(1+12)%19=2（沖突） H2=(1-12)%19=0 H(68)=68%13=3（沖突） H1=(3+12)%19=4H(11)=11%13=11 H(10)=10%13=10（沖突） H1=(10+12)%19=11（沖突） H2=(10-12)%19=9H(77)=77%13=12 散列表為：0123456789

33、10-1112131415161718270114556884192010231177ASL=（7*1+2*2+3*3）/12=20/12=5/3五、int nodes(BTree *b)int num1,num2;If(b=null)return(0)；elsenum1=nodes(bleft);num2=nodes(bright);return(num1+num2+1); 數(shù)據(jù)結(jié)構(gòu)（十）一、填空題（本大題共有5個(gè)題，每題5分，共25分，將正確答案填在空格處）1.設(shè)某二叉樹前序?yàn)閍bdcef, 中序?yàn)閐baecf，則此二叉樹的后序?yàn)?。2.具有4個(gè)頂點(diǎn)的無向完全圖有 條邊。3.已知二維數(shù)組A

34、1020,每個(gè)數(shù)組元素占1個(gè)存儲(chǔ)單元，若按列優(yōu)先順序存放數(shù)據(jù)元素，a00的存儲(chǔ)地址是200，則a612的存儲(chǔ)地址是 。4.具有n個(gè)結(jié)點(diǎn)的完全二叉樹的深度為 。5.已知有序表為（12，18，24，35，47，50，62，83，90，115，134），當(dāng)用折半法查找時(shí)47時(shí)，需進(jìn)行 次查找可確定成功。二、（本題滿分為10分）（1）將圖（a）中給定的樹轉(zhuǎn)換成二叉樹（2）將圖（b）中給定的二叉樹轉(zhuǎn)換成樹（3）將圖（c）中給定的森林轉(zhuǎn)換成二叉樹三、（本題滿分為10分）求以數(shù)據(jù)集（4，5，6，7，10，12，18）為結(jié)點(diǎn)權(quán)值所構(gòu)造的哈夫曼樹，并且計(jì)算出其帶權(quán)路徑長度。四、（本題滿分為15分）假設(shè)查找表以單

35、鏈表的形式存儲(chǔ)，試寫出對此單鏈表進(jìn)行順序查找時(shí)的實(shí)現(xiàn)算法。五、（本題滿分為15分）寫出一趟快速排序的算法。答案：一、1.dbefca2.63.3324.log2n+15.4二、（1）（2） （3）三、（4+5）*4+（10+6+7）*3+(18+12)*2=165四、struct Elemtype /數(shù)據(jù)元素的數(shù)據(jù)類型定義keytype key; /關(guān)鍵字項(xiàng)；struct LnodeElemtype data ;struct Lnode * next ;intseqsearch (Lnode *L ,keytype s )Lnode*p=L-next;intn=1;while(p&(p-dat

36、a.key!=s)p=p-next;n+;if(p)return n;elsereturn 1;五、int Partition(SqList &L, int low,int high)pivotkey=L.rlow.key;while(lowhigh)while(low=pivotkey) -high;L.rlowL.rhigh；while(lowhigh&L.rhigh.key=pivotkey) +low;L.rlowL.rhigh；returnlow;C語言程序設(shè)計(jì) （九）一、填空題。寫出下列程序的運(yùn)行結(jié)果（本題共有5小題，每小題5分，滿分25分）1.main()inta,b;a=5;a

37、=a+4;printf(“%d”,a);b=2;a=+-b;printf(“%dn”,a);程序運(yùn)行結(jié)果是：（ ）2.# include intf(int x) static y=1;y+; x += y;return x;main() int k;k=f(3);printf(%d %dn, k, f(k);程序運(yùn)行結(jié)果是：（ ）3.main()int x;x=3;doprintf(“%d”,x-);while(!x);程序運(yùn)行結(jié)果是：（ ）4.main()int i,j,row,col,m,a33=100,200,300,28,72,-30,-850,2,6;m=a00;for(i=0;i3

38、;i+)for(j=0;j3;j+)if(ajm)m=aj; row=i; col=j;printf(“%d,%d,%d”,m,row,col);程序運(yùn)行結(jié)果是：（ ）5.以下fun函數(shù)的功能是將一個(gè)字符串的內(nèi)容顛倒過來#include“stdio.h”#include“string.h”voidfun(char str)int i,j,k;for(i=0,j= ;ij;i+, ) k=str; str=strj; strj=k;二、程序設(shè)計(jì)題（本題共有3個(gè)小題，第一題10分，剩余兩題每題20分，滿分50分）1.判斷101-200之間有多少個(gè)素?cái)?shù)，并輸出所有素?cái)?shù)。2.輸入8個(gè)整數(shù)放入一維數(shù)組w

39、中，輸出交換前的數(shù)組；找出其中最小和最大數(shù)，并將他們分別與數(shù)組中的第一個(gè)元素和最后一個(gè)元素交換位置；輸出交換后的數(shù)組。3.編寫一個(gè)函數(shù)，輸入n為偶數(shù)時(shí)，調(diào)用函數(shù)求1/2+1/4+.+1/n,當(dāng)輸入n為奇數(shù)時(shí)，調(diào)用函數(shù) 1/1+1/3+.+1/n答案：一、1.912.583.34.-850,2,05.strlen(str)-1 j-或-j或j-=1二、1.#include math.h main() int m,i,k,h=0,leap=1; printf(n); for(m=101;m=200;m+) k=sqrt(m+1); for(i=2;i=k;i+) if(m%i=0) leap=0;

40、break; if(leap) printf(%-4d,m);h+; if(h%10=0) printf(n); leap=1; printf(nThe total is %d,h); 2.#include main() int w8,i,min,max,t;printf(請輸入8個(gè)整型數(shù)據(jù):);for(i=0;i8;i+) scanf(%d,&w);printf(交換前的數(shù)組:);for(i=0;i8;i+) printf(%dt,w);printf(n);min=0;for(i=1;i8;i+) if (wwmin) min=i; t=w0;w0=wmin;wmin=t;printf(交換

41、最小值后的數(shù)組:);for(i=0;i8;i+) printf(%dt,w);max=0;for(i=1;iwmax) max=i;t=w7;w7=wmax;wmax=t;printf(交換最大值后的數(shù)組:);for(i=0;i1) break; if(n%2=0) printf(Even=); sum=dcall(peven,n); else printf(Odd=); sum=dcall(podd,n); printf(%f,sum); float peven(int n) float s; int i; s=1; for(i=2;i=n;i+=2) s+=1/(float)i; retu

42、rn(s); float podd(n) int n; float s; int i; s=0; for(i=1;i=n;i+=2) s+=1/(float)i; return(s); float dcall(fp,n) float (*fp)(); int n; float s; s=(*fp)(n); return(s); C語言程序設(shè)計(jì) （十）一、填空題。寫出下列程序的運(yùn)行結(jié)果（本題共有5小題，每小題5分，滿分25分）1.main()intk;floats;for(k=0, s=0; k 7; k +)s += k/2;printf(%d,%fn, k, s); 程序運(yùn)行結(jié)果是：（ ）2

43、.函數(shù) voidf(char s , char t ) int k=0;while (sk=tk) k+; 等價(jià)于void f(char *s, char *t) while ();3.# include # include main() int a=1,b=4,c=2;float x=10.5 , y=4.0 , z;z=(a+b)/c+sqrt(double)y)*1.2/c+x;pritnf(%fn,z); 程序運(yùn)行結(jié)果是：（ ）4.intfun(int *x,int n)if (n=0) return x0;else return x0+fun(x+1,n-1);main()int a

44、=1,2,3,4,5,6,7;printf(“%d”, fun(a,3);程序運(yùn)行結(jié)果是：（ ）5.以下程序的功能是利用指針指向三個(gè)整型變量，并通過指針運(yùn)算找出三個(gè)數(shù)中的最大值#include main()int x,y,z,max, *px, *py, *pz, *pmax;scanf(“%d%d%d”,&x,&y,&z);px=&x; py=&y; pz=&z; pmax=&max;if(*pmax*py) *pmax=*py;if(*pmax*pz) *pmax=*pz;printf(“max=%d”,max);二、程序設(shè)計(jì)題（本題共有3個(gè)小題，第一題10分，剩余兩題每題20分，滿分50分）1. 寫一個(gè)函數(shù)，求一個(gè)字符串的長度，在main函數(shù)中輸入字符串，并輸出其