一、選擇題

1． 已知兩個長度分別為m 和n 的升序鏈表，若將它們合并為一個長度為m+n的降序鏈表，則最壞情況下的時間復雜度是( )

A.

B.

C.

D. 【答案】D

m 和n 是兩個升序鏈表長度分別為m 和m 在合并過程中最壞的情況是兩個鏈表中的【解析】

元素依次進行比較，比較的次數是m 和n 中的最大值。

2． 以RS-232為接口，進行7位ASCII 碼字符傳送，帶有一位奇校驗位和兩位停止位，當波特率為9600波特時，字符傳送率為( )。

A.960 B.873 C.1371 D.480

【答案】A

3． 某文件占10個磁盤塊，現要把該文件磁盤塊逐個讀入主存緩沖區，并送用戶區進行分析。假，設一個緩沖區與一個磁盤塊大小相同把一個磁盤塊讀人緩沖區的時間為送到用戶區的時間是

CPU

對一塊數據進行分析的時間為

下，讀人并分析完該文件的時間分別是( )。

A.

B.

C.

D. 【答案】B

【解析】這是一個簡單的緩沖區的問題。由于緩沖區的訪問是互斥的，所以對單一緩沖區，從磁盤寫入和讀出到用戶區的操作必須串行執行，也就是要保證互斥操作。而CPU 對數據的分析與從用戶區讀數據也是需要互斥操作，但是CPU 分析與從磁盤寫入緩沖區的操作可以并行。從本題看，由于分析所用的時間小于從磁盤寫入緩沖區的時間，因此，CPU 會空閑。單緩沖區的總時間=(磁盤寫入緩沖區時間+緩沖區讀出時間)xlO+CPU處理最后一塊數據的時間

=

當采用雙緩沖區時，每塊緩沖區的操作也必須滿足互斥操作，但是，

對兩塊緩沖區的操作卻可以并行，所以，當第一個緩沖區寫滿以后，磁盤緊接著寫另一個緩沖區，同時，前一個已經滿了的緩沖區被讀出到用戶區，并立即進行CPU 的數據分析。讀出操作和數據

將緩沖區的數據傳

在單緩沖區和雙緩沖區結構

分析必須互斥進行，故從時間上看，當數據被讀出并分析后，恰好另一個緩沖區也寫滿了，可以立即進行讀出數據到用戶區并進行數據分析。兩塊緩沖區交替進行讀寫，直到數據分析完畢，因此，總時間=(磁盤寫入緩沖區時間)×10+讀出最后一塊數據時間+CPU分析最后一塊數據時間

=

4． 進程P0和P1的共享變量定義及若進程P0和P1訪問臨界資源的類C 偽代碼實現如下：

則并發執行進程:P0和P1時產生的情況是( )。 A. 不能保證進程互斥進入臨界區，會出現“饑餓”現象 B. 不能保證進程互斥進入臨界區，不會出現“饑餓”現象 C. 能保證進程互斥進入臨界區，會出現“饑餓”現象 D. 能保證進程互斥進入臨界區，不會出現“饑餓”現象 【答案】D

【解析】這是皮特森算法

的實現，保證進入臨界區的進程合理安全。該

算法為了防止兩個進程為進入臨界區而無限期等待，設置變量turn ，表示不允許進入臨界區的編號，每個進程在先設置自己標志后再設置turn 標志，不允許另一個進程進入，這時，再同時檢測另一個進程狀態標志和不允許進入標志，這樣可以保證當兩個進程同時要求進入臨界區時只允許一個進程進入臨界區。保存的是較晚的一次賦值，則較晚的進程等待，較早的進程進入。先到先人，后到等待，從而完成臨界區訪問的要求。

5． 希爾排序的組內排序采用的是( )。

A. 直接插入排序 B. 折半插入排序 C. 快速排序 D. 歸并排序 【答案】A

【解析】希爾排序基本思想是：先將整個待排元素序列按某個增量分割成若干個子序列，在

子序列內進行直接插入排序，然后依次縮減增量再進行排序，待整個序列中的元素基本有序(増量足夠小)時，再對全體元素進行一次直接插入排序。

6． 在子網中，能接收目的地址為的IP 分組的最大主機數是( )。

A.0 B.1 C.2 D.4

【答案】C

【解析】每個子網中忽略子網內全為0和全為1的地址剩下的就是有效主機地址，本題中由于子網的比特數是30, 因此用于主機的只有2位，即00, 01, 10, 11，有效主機地址是2個，

這里

顯然是其廣播地址，因此答案是C 。

7． 下列關于最小生成樹的敘述中，正確的是( )。

Ⅰ. 最小生成樹的代價唯一Ⅱ. 所有權值最小的邊一定會出現在所有的最小生成樹中Ⅲ. 使用普里姆(Prim )算法從不同頂點開始得到的最小生成樹一定相同Ⅳ. 使用普里姆算法和克魯斯卡爾(Kruskal )算法得到的最小生成樹總不相同

A. 僅Ⅰ B. 僅Ⅱ C. 僅Ⅰ、Ⅲ D. 僅Ⅱ、Ⅳ 【答案】A 。

【解析】當圖中存在相同權值的邊時，其最小生成樹可能是不唯一的，但最小生成樹的代價一定是相同的，所以說法Ⅰ正確。從n 個頂點的連通圖中選取n-1條權值最小的邊可能構成回路，所以說法Ⅱ錯誤。當某個頂點有權值相同的邊，使用普里姆(Prim )算法從不同頂點開始得到的最小生成樹并不一定相同，所以說法Ⅲ錯誤。當最小生成樹不唯一時，使用普里姆算法和克魯斯卡爾(Kruskal )算法得到的最小生成樹可能相同，也可能不同，所以說法Ⅳ錯誤。由此可得出正確答案。

8． 設有一棵3階B 樹，如圖1所示。刪除關鍵字78得到一棵新B 樹，其最右葉結點所含的關鍵字是( )。

圖1 3二叉樹圖

A.60 B.60, 62

總結

以上是生活随笔為你收集整理的北京协和医学院823计算机原理,2017年北京协和医学院放射医学研究所(天津)823计算机原理考研题库...的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。