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