計(jì)算機(jī)專(zhuān)業(yè)基礎(chǔ)綜合

計(jì)算機(jī)專(zhuān)業(yè)（基礎(chǔ)綜合）-試卷4（總分98,考試時(shí)間90分鐘）單項(xiàng)選擇題單項(xiàng)選擇題1-40小題。下列每題給出的四個(gè)選項(xiàng)中，只有一個(gè)選項(xiàng)是最符合題目要求的。在順序表中刪除一個(gè)元素的時(shí)間復(fù)雜度為（）。O（1）B.O（logn）C.O（n）D.O（n2）設(shè)棧S和隊(duì)列Q的初始狀態(tài)均為空，元素abcdefg依次進(jìn)入棧S。若每個(gè)元素出棧后立即進(jìn)入隊(duì)列Q，且7個(gè)元素出隊(duì)的順序是bdcfeag，則棧S的容量至少是（）。A.1B.2C.3D.4設(shè)A是一個(gè)已有10個(gè)元素的棧，棧中依次是A1，A2，…，A10，棧頂是A10；B是一個(gè)已有10個(gè)元素的循環(huán)隊(duì)列，隊(duì)列中元素依次為B1，B2，…，B10，隊(duì)頭元素為B1。A、B均采用順序結(jié)構(gòu)，現(xiàn)要將棧中元素全部移入隊(duì)列中，需（）次基本操作才能使得隊(duì)列中元素與棧中元素交替排列，即B中排列后的元素為B1，A1，B2，.A2，…，B10，A10。（不必考慮存儲(chǔ)空間）A,100B.1000C,50D.20設(shè)高度為H的二叉樹(shù)上只有度為0和度為2的結(jié)點(diǎn)，則此類(lèi)二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)至少為（）。A.2*HB.2*H-1C.2*H+1D.H+1設(shè)有13個(gè)值，用它們組成一棵哈夫曼樹(shù)，則該哈夫曼樹(shù)共有（）個(gè)結(jié)點(diǎn)。TOC\o"1-5"\h\zA.13B.12C.26D.25已知10個(gè)數(shù)據(jù)元素為（54，28，16，34，73，62，95，60，23，43），按照依次插入結(jié)點(diǎn)的方法生成一棵二叉排序樹(shù)后，查找值為62的結(jié)點(diǎn)所需比較的次數(shù)為（）。A.2B.3C.4D.5當(dāng)向一棵m階的B一樹(shù)做插入操作時(shí)，若一個(gè)結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)等于（），則必須分裂成兩個(gè)結(jié)點(diǎn)，當(dāng)向一棵m階的B-樹(shù)做刪除操作時(shí)，若一個(gè)結(jié)點(diǎn)中的關(guān)鍵字個(gè)數(shù)等于（），則可能需要同它的左兄弟或右兄弟結(jié)點(diǎn)合并成一個(gè)結(jié)點(diǎn)。A.m，m/2-2B.m-1，m/2-1C.m+1，m/2D.m/2，m/2+1下面關(guān)于Prim算法和Kruskal算法的時(shí)間復(fù)雜度正確的是（）。Prim算法的時(shí)間復(fù)雜度與網(wǎng)中的邊數(shù)有關(guān)，適合于稀疏圖

Prim算法的時(shí)間復(fù)雜度與網(wǎng)中的邊數(shù)無(wú)關(guān)，適合于稠密圖Kruskal算法的時(shí)間復(fù)雜度與網(wǎng)中的邊數(shù)有關(guān)，適合于稠密圖Kruskal算法的時(shí)間復(fù)雜度與網(wǎng)中的邊數(shù)無(wú)關(guān)，適合于稀疏圖數(shù)據(jù)序列F={2，1，4，9，8，10，6，20）只能是下列排序算法中的（）的兩趟排序后的結(jié)果?？焖倥判駼,冒泡排序C.選擇排序D.插入排序在含有n個(gè)關(guān)鍵字的大頂堆中，關(guān)鍵字最小的記錄有可能存儲(chǔ)在（）位置上。A.n/2B.n/2-1C.1D.n/2+2馮?諾依曼機(jī)中指令和數(shù)據(jù)均以二進(jìn)制形式存放在存儲(chǔ)器中，CPU區(qū)分它們的依據(jù)是（）。指令操作碼的譯碼結(jié)果B.指令和數(shù)據(jù)的尋址方式C.指令周期的不同階段D.指令和數(shù)據(jù)所在的存儲(chǔ)單元IEEE754標(biāo)準(zhǔn)浮點(diǎn)數(shù)的尾數(shù)采用（）機(jī)器數(shù)形式。A.原碼B.補(bǔ)碼C.移碼D.反碼字長(zhǎng)16位的補(bǔ)碼定點(diǎn)小數(shù)的表示范圍是（）。0?1-2-15-（1-2-15）?1-2-15-1?1-2-15-1?1補(bǔ)碼定點(diǎn)小數(shù)除法中，被除數(shù)和除數(shù)應(yīng)滿(mǎn)足（）。A.0<I被除數(shù)IMI除數(shù)IB.0<|被除數(shù)IMI除數(shù)IC.0<|除數(shù)I<I被除數(shù)ID.0<I被除數(shù)I<I除數(shù)I某機(jī)器采用四體低位交叉存儲(chǔ)器，現(xiàn)分別執(zhí)行下述操作：（1）讀取6個(gè)連續(xù)地址單元中存放的存儲(chǔ)字，重復(fù)80次；（2）讀取8個(gè)連續(xù)地址單元中存放的存儲(chǔ)字，重復(fù)60次。則（1）、（2）所花時(shí)間之比為（）。A.1：1B.2：1C.4：3D.3：4下列說(shuō)法中錯(cuò)誤的是（）。虛擬存儲(chǔ)器的引入主要是為了解決主存容量的問(wèn)題虛擬存儲(chǔ)器通過(guò)頁(yè)表來(lái)實(shí)現(xiàn)虛實(shí)地址的映射虛擬存儲(chǔ)器是一個(gè)容量很大的邏輯模型，不是任何實(shí)際的存儲(chǔ)器虛擬存儲(chǔ)器完全由硬件實(shí)現(xiàn)在指令格式中，采用擴(kuò)展操作碼設(shè)計(jì)方案的目的是（）?？s短指令字長(zhǎng)B.增加指令字長(zhǎng)C.保持指令字長(zhǎng)不變的基礎(chǔ)上增加指令數(shù)量D.保持指令字長(zhǎng)不變的基礎(chǔ)上擴(kuò)大指令尋址空間磁盤(pán)的平均存取時(shí)間是指平均尋道時(shí)間和平均等待時(shí)間之和。若磁盤(pán)的轉(zhuǎn)速提高一倍，則（）。A.平均存取時(shí)間減半B.平均尋道時(shí)間減半C.平均等待時(shí)間減半D.以上都正確下列說(shuō)法正確的是（）。

取指周期一定等于機(jī)器周期指令字長(zhǎng)等于機(jī)器字長(zhǎng)的前提下，取指周期等于機(jī)器周期指令字長(zhǎng)等于存儲(chǔ)字長(zhǎng)的前提下，取指周期等于機(jī)器周期取指周期與機(jī)器周期沒(méi)有必然聯(lián)系下列說(shuō)法中正確的是（）。微處理器的程序稱(chēng)為微程序微指令控制器的執(zhí)行速度比硬布線控制器快存放微程序的控制存儲(chǔ)器可用ROM或EPROM來(lái)實(shí)現(xiàn)在微程序控制器中，微指令使用機(jī)器指令來(lái)解釋執(zhí)行同步通信比異步通信數(shù)據(jù)傳輸率高的原因是（）。A.同步通信不需要應(yīng)答信號(hào)B.同步通信使用公共時(shí)鐘進(jìn)行同步同步通信中，通信雙方的速度相近D.以上都包括CPU在中斷周期要完成的任務(wù)不包括（）。A.保護(hù)斷點(diǎn)B.關(guān)中斷C.保護(hù)現(xiàn)場(chǎng)D.向量地址送PC實(shí)時(shí)系統(tǒng)中的進(jìn)程調(diào)度，通常采用（）算法。A.先來(lái)先服務(wù)B,時(shí)間片輪轉(zhuǎn)C.搶占式的優(yōu)先數(shù)高者優(yōu)先D.響應(yīng)比高者優(yōu)先進(jìn)程由就緒態(tài)轉(zhuǎn)換為運(yùn)行態(tài)是由（）引起的。A.中斷事件B.進(jìn)程狀態(tài)轉(zhuǎn)換C.進(jìn)程調(diào)度D.為程序創(chuàng)建進(jìn)程以下（）不是產(chǎn)生死鎖的原因。A.資源共享B.并發(fā)執(zhí)行的進(jìn)程數(shù)太多C.系統(tǒng)資源不足D.進(jìn)程推薦順序非法把程序地址空間中使用的邏輯地址變成內(nèi)存中物理地址稱(chēng)為）。A.加載B.物理化C,重定位D.邏輯化下面關(guān)于虛擬存儲(chǔ)器的論述中，正確的是（）。在段式系統(tǒng)中以段為單位管理用戶(hù)的邏輯空間，以頁(yè)為單位管理內(nèi)存的物理空間；有了虛擬存儲(chǔ)器才允許用戶(hù)使用比內(nèi)存更大的地址空間為了提高請(qǐng)求分頁(yè)系統(tǒng)中內(nèi)存的利用率，允許用戶(hù)使用不同大小的頁(yè)面為了能讓更多的作業(yè)同時(shí)運(yùn)行，通常只裝入10%?30%的作業(yè)即啟動(dòng)運(yùn)行最佳適應(yīng)算法是實(shí)現(xiàn)虛擬存儲(chǔ)器的常用算法在下列文件的物理結(jié)構(gòu)中，（）不利于文件長(zhǎng)度的動(dòng)態(tài)增長(zhǎng)。A,連續(xù)結(jié)構(gòu)B,鏈接結(jié)構(gòu)C,索引結(jié)構(gòu)D.哈希結(jié)構(gòu)設(shè)文件F1的當(dāng)前引用計(jì)數(shù)值為1，先建立F1的符號(hào)鏈接（軟鏈接）文件F2,再建F1的硬鏈接文件F3，然后刪除F1。此時(shí)，F(xiàn)2和F3的引用計(jì)數(shù)值分別是（）。A.0、1B.1、1C,1、2D.2、1如果I/O設(shè)備與存儲(chǔ)設(shè)備間的數(shù)據(jù)交換不經(jīng)過(guò)CPU來(lái)完成，則這種數(shù)據(jù)交換方式是（）。A.程序查詢(xún)方式B.中斷方式C.DMA方式D.無(wú)條件存取方式

驅(qū)動(dòng)調(diào)度算法中，（）算法可能會(huì)隨時(shí)改變移動(dòng)臂的運(yùn)動(dòng)方向。A.電梯調(diào)度B.最短尋找時(shí)間優(yōu)先C.掃描D,單向掃描某虛存系統(tǒng)有3頁(yè)初始為空的頁(yè)框，若采用先進(jìn)先出的頁(yè)面淘汰算法，則在下列的頁(yè)面需求提出時(shí)，會(huì)產(chǎn)生（）次缺頁(yè)中斷?設(shè)頁(yè)面走向?yàn)椋?32143543215?。A.7B.8C.9D.10傳輸線上的位流信號(hào)同步，應(yīng)該屬于下列OSI的（）層處理。A.物理層B.數(shù)據(jù)鏈路層C.網(wǎng)絡(luò)層D.傳輸層測(cè)得一個(gè)以太網(wǎng)數(shù)據(jù)的波特率是40Mbps，那么其數(shù)據(jù)率是（）。A.10MbpsB.20MbpsC.40MbpsD.80Mbps數(shù)據(jù)鏈路層采用了后退N幀（GBN）協(xié)議，發(fā)送方已經(jīng)發(fā)送了編號(hào)為0?7的幀。當(dāng)計(jì)時(shí)器超時(shí)時(shí)，若發(fā)送方只收到0、2、3號(hào)幀的確認(rèn)，則發(fā)送方需要重發(fā)的幀數(shù)是（）。TOC\o"1-5"\h\zA.2B.3C.4D.5一個(gè)C類(lèi)地址，采用了40作為子網(wǎng)掩碼，那么這個(gè)C類(lèi)地址可以劃分為（）個(gè)子網(wǎng)。A,16B.32C,64D.128下列地址中，不屬于多播地址的是（）。A,3B.9C,2D.55下列的網(wǎng)絡(luò)協(xié)議中，（）的運(yùn)輸層協(xié)議是使用TCP的。A.TFTPB.DNSC.RIPD.TELNEI、一個(gè)FTP的用戶(hù)，發(fā)送了LIS27、命令來(lái)獲取服務(wù)器的文件列表，這時(shí)候服務(wù)器應(yīng)該通過(guò)（）端口來(lái)傳輸該列表。A,21B.20C,22D.19UDP的報(bào)文頭部不包括（）。A.目的地址B.報(bào)文長(zhǎng)度C.目的UDP端HD.源UDP端口綜合應(yīng)用題綜合應(yīng)用題41-47小題。1.

給定二叉椅壞點(diǎn)的結(jié)構(gòu)定義(ypcdcfsirucrnode*link；structnod-etiniitem*linkIfr,"給定數(shù)維intoCLE,編寫(xiě)遞歸程序.由數(shù)組我}建立錦標(biāo)機(jī)如給定數(shù)組m<!T*ASM,A‘I?,?E*對(duì)應(yīng)的錦標(biāo)樹(shù)為給定集合S={0,1,2,3,4),以及優(yōu)先關(guān)系R={0〈1,1<4,1<2,20,2<4,4<0)o(1)R是偏序關(guān)系嗎？(2)證明你的結(jié)論。下圖所示為雙總線結(jié)構(gòu)機(jī)器的數(shù)據(jù)通路，IR為指令寄存器，PC為程序計(jì)數(shù)器(具有自增功能)，M為主存(受R/W信號(hào)控制)，AR為地址寄存器，DR為數(shù)據(jù)緩沖寄存器，ALU由加、減控制信號(hào)決定完成何種操作，控制信號(hào)G控制的是一個(gè)門(mén)電路。另外，線上標(biāo)注有小圈表示有控制信號(hào)，例中yi表示y寄存器的輸入控制信號(hào)，R1o為寄存器R1的輸出控制信號(hào)，未標(biāo)字符的線為直通線，不受控制。(1)“ADDR2,R0”指令完成(R0)+(R2)一R0的功能操作，畫(huà)出其指令周期流程圖，假設(shè)該指令的地址已放APC中。并列出相應(yīng)的微操作控制信號(hào)序列。(2)若將“取指周期”縮短為一個(gè)CPU周期，請(qǐng)先畫(huà)出修改數(shù)據(jù)通路，后畫(huà)出指令周期流程圖。(3)在(2)的基礎(chǔ)上，將“執(zhí)行周期”也縮短為一個(gè)CPU周期，先修改運(yùn)算器數(shù)據(jù)通路，后畫(huà)出指令周期流程圖。此時(shí)加法指令速度比(1)提高幾倍？□tin有兩部計(jì)算機(jī)M1和M2,指令系統(tǒng)相同。它們的操作頻率頻率分別是400MHz和200MHz。指令分成A、B和C三類(lèi)，在M1上執(zhí)行分別需4、6和8個(gè)周期；在M2上執(zhí)行分別需2、4和3個(gè)周期?，F(xiàn)有一程序在兩機(jī)器上執(zhí)行，其中A、B和C三類(lèi)指令依次占30%、50%和20%。請(qǐng)問(wèn)哪一部機(jī)器較快完成，快幾倍？某會(huì)議有n個(gè)參與者，等大家到齊后會(huì)議才能開(kāi)始，利用P、V原語(yǔ)操作實(shí)現(xiàn)會(huì)議參與者進(jìn)程。

完成以下各小題。（1）什么是Belady現(xiàn)象?為什么會(huì)產(chǎn)生這種現(xiàn)象？（2）頁(yè)面置換算法FIFO為什么會(huì)出現(xiàn)Belady現(xiàn)象?簡(jiǎn)述理由。（3）頁(yè)面置換算法LRU為什么不會(huì)出現(xiàn)Belady現(xiàn)象?簡(jiǎn)述理由。假定A和B是試圖在一個(gè)以太網(wǎng)上發(fā)送的兩個(gè)站。每個(gè)站都有一個(gè)穩(wěn)定的幀的隊(duì)列準(zhǔn)備發(fā)送，A的幀編號(hào)是A1，A2和A3等，B的幀編號(hào)是B1，B2和B3等。再假定指數(shù)后退的基本單元時(shí)間是T=51.2微秒?，F(xiàn)在A和B同時(shí)嘗試發(fā)送1號(hào)幀，碰撞，并且剛好分別選擇了0xT和1xT的退避時(shí)間，也就是