2018上海大學832真題回憶版
一．選擇（2*30）
每一道選擇題保證是考察的原題，但是具體的數(shù)字可能有出入。對于不能保證數(shù)字正確的題目都找到了類似的題目以保證問題與答案的匹配性。
1.下列排序算法穩(wěn)定的是（）
A．冒泡排序，直接插入排序
B．基數(shù)排序，希爾排序
C．堆排序，選擇排序
D．歸并排序，快速排序
2.下列不同進制數(shù)中真值最大的是（）
A．*（2）
B．45（8）
C．29（16）
D．97（10）
3.以下說法正確的是（）
A．cache一般采用DRAM
B．SRAM不需要刷新
C．SRAM比DRAM集成度高
D．DRAM是非易失性存儲器
4.下列操作復雜度為O（1）的是（）
A．在順序表中插入一個元素
B．在單鏈表中訪問一個元素
C．在單鏈表中插入一個元素
D．在順序表中訪問一個元素
5.數(shù)組中有100個遞增存儲的整數(shù)，折半查找時查找一個元素的比較次數(shù)不可能超過（）
A.100 B.25 C.10 D.9
6.一個完全二叉樹共有100個結(jié)點，則有共有（）個葉子結(jié)點
A.26 B.33 C.44 D.45
7.一般家用臺式電腦是（）
A．微型機
B．小型機
C．中型機
D．大型機
8.微程序存儲在（）
A．主存儲器
B．程序計數(shù)器
C．控制存儲器
D．指令寄存器
9.一地址指令（）
A．可能有一個操作數(shù)，也可能有兩個操作數(shù)
B．不可能是數(shù)據(jù)傳送指令
C．不可能是運算指令
D．以上都對
10.決定程序執(zhí)行順序的是（）
A．指令寄存器
B．數(shù)據(jù)寄存器
C．程序計數(shù)器
D．控制存儲器
11. 在指令格式中，采用擴展操作碼設(shè)計方案的目的是（）
A．減少指令字長度
B．增加指令字長度
C．保持指令字長度不變而增加操作指令的數(shù)量
D．保持指令字長度不變而增加尋址空間
12.下列哪個操作不能由運算器實現(xiàn)（）
A．發(fā)出“讀”信號
B．兩個整數(shù)比較大小
C．歡迎補充
D．歡迎補充
13.存儲一個n階上三角矩陣需要數(shù)組的大小是（）
A．log2n
B．n^2
C. n*(n+1)/2
D. n*(n-1)/2
14. 對于深度為4的棧，入棧順序為ABCDEF，則出棧順序可能是（）
A.AFEDCB B.ABDFEC C.DFABCE D.CEFABD
15.下列哪種排序方式，當待排序數(shù)列越有序時，排序速度越慢（）
A．選擇排序
B．插入排序
C．快速排序
D．冒泡排序
16.每一個內(nèi)存塊都可以映射到任意一個cache塊中，這種映射方式稱為（）
A．直接映射
B．全相連映射
C．半相連映射
D．組相連映射
17.下列說法正確的是（）
A．chche的出現(xiàn)是為了解決cpu與主存間容量差異的矛盾
B．交叉存儲器技術(shù)可以使不同存儲器部分塊同時串行傳輸數(shù)據(jù)
C．直接尋址方式不需要進行地址的運算
D．歡迎補充
18.下列哪個不是DMA的工作方式
A．多路選擇
B．周期挪用
C．與CPU交替訪存
D．停止CPU訪問內(nèi)存
19.二維數(shù)組A[7][9],按行優(yōu)先順序存放在首地址是600的地址連續(xù)的內(nèi)存空間內(nèi)，每個數(shù)據(jù)占兩個字節(jié)。則A[6][3]所在的地址是（）
A 828 B 814 C 714 D 614
20.512K*8容量的DRAM，需要的地址線和數(shù)據(jù)線條數(shù)總數(shù)是（）
A.512 B.64 C.27 D.10
21. 對有序表（02，16,24,33,48,57,66,71,79,84,86,91）進行折半查找，查找成功的平均查找長度是（）
A．37/12 B.37/13 C.39/13 D.49/12
22.下列關(guān)于二叉樹的判斷正確的是（）
A 二叉樹的度為2
B 二叉樹中葉子結(jié)點的個數(shù)是度為二的結(jié)點個數(shù)加一
C 對于n個結(jié)點的二叉樹，葉子結(jié)點個數(shù)的二倍加上度為一的結(jié)點的個數(shù)等于n+1
D 如果二叉樹前序和后序遍歷序列相反，那么二叉樹任一結(jié)點都沒有做左子樹
23-30 很基礎(chǔ)，忘卻了。歡迎補充。
二．填空（30’）
31.（1）數(shù)據(jù)采用奇校驗碼校驗方式，補充空格
（）0110110；（）1011001；（）0001101
（2）奇校驗碼能檢出（）位錯，糾正（）位錯
（3）奇校驗碼的碼距是多少？
32. 一個直接映射的cache大小為512B，塊大小為4B，主存以字節(jié)編址。主存地址長16位。問：
（1）該機器能尋址多大空間
（2）cache共分多少塊，內(nèi)存共分多少塊
（3）畫出主存格式示意圖，標好位數(shù)
（4）給出cache地址的映射函數(shù)
33.給出一組數(shù)據(jù)：45,06,15,33,81,02,64,77。
（1）寫出用冒泡排序算法第一趟排序后的狀態(tài)。
（2）寫出用快速排序（選擇第一個數(shù)為基準）第一趟排序后的狀態(tài)。
34.
（1）對于n個結(jié)點的二叉樹遍歷的時間復雜度是？
（2）一個二叉樹如圖，給出二叉樹的前序，中序，后序遍歷序列。(非原圖)
三．簡答題(60’)
35.操作數(shù)a，b已經(jīng)分別存放在寄存器R2，R3中，補碼表示。ALU有+，-，M（傳送）三種功能。
（1）指出哪些微指令是相容的。
（2）將（a+b）*1/2的結(jié)果存放到R1中，寫出此操作的微指令。
（3）采用字段直接譯碼方式定義微指令集，問需要多少字段？給出理由。
36.有8K*8的ROM芯片和8K*4的RAM芯片，組成由16K*8的RAM和8K*8的ROM組成的存儲器，其中高地址是ROM。
（1）計算各需要多少芯片
（2）畫出連線圖。（必須連的線有地址線，數(shù)據(jù)線，RD，WE，CS，MERQ）。
37(10’)
（1） 給出單鏈表定義代碼
（2） 統(tǒng)計數(shù)列中比正整數(shù)x小的個數(shù)，如12.23.32.45.54.65。x=33。返回3。寫出你的算法程序，必要處予以注釋
（3） 把比正數(shù)x大的奇數(shù)從單鏈表中刪除，寫出你的算法程序，必要處予以注釋
38 （9’）
有兩個字符串A,B，設(shè)計一個算法，判斷能否在對A進行若干次循環(huán)左移或右移之后出現(xiàn)B是A的子串的情況。如A=’ABACA’,B=’CAA’，存在；A=’ABCBA’,B=’BAB’,不存在。
（1） 寫出你的算法思想(3’)
（2） 寫出你的算法程序，必要處予以注釋(6’)
39（11’）
（1） 寫出基于鄰接表存儲的連通圖深度優(yōu)先遍歷算法程序
（2） 分析你設(shè)計的算法的復雜度
（3） 根據(jù)下圖寫出鄰接表，并根據(jù)你的鄰接表給出從結(jié)點0出發(fā)的深度優(yōu)先遍歷序列（非原圖）
