蘇州大學(xué)
2003年攻讀碩士學(xué)位研究生入學(xué)考試試題
學(xué)科，專業(yè)：…………研究方向：………….考試科目：操作系統(tǒng)與數(shù)據(jù)結(jié)構(gòu)

數(shù)據(jù)結(jié)構(gòu)
1、 設(shè)以單向鏈表存儲(chǔ)串，試編寫判別給定串是否具有對(duì)稱性的算法，并要求算法時(shí)間復(fù)雜度為O（length（s））�？梢栽O(shè)輔助空間，length（s）可以設(shè)為已知參數(shù)。（10）
2、 設(shè)一有向環(huán)用鄰接表表示，試設(shè)計(jì)遞歸算法，設(shè)計(jì)以Vo出發(fā)最長(zhǎng)路徑的長(zhǎng)度。（15）
3、 簡(jiǎn)述表達(dá)式求值的基本思想，并對(duì)表達(dá)式6/（3-1）求值的操作過程，要求寫出操作數(shù)棧和運(yùn)算棧的變化情況。（15）
4、 推導(dǎo)上三角陣在壓縮存儲(chǔ)時(shí)的地址計(jì)算公式。（10）
5、 編寫算法，求給定結(jié)點(diǎn)在給定的二叉排序樹中解的層次。（10）
6、 畫出有序表（18、34、56、77、78、100、345、450、888）中進(jìn)行折半查找的判定樹，求等概率時(shí)查找成功時(shí)的平均查找長(zhǎng)度。（15）

操作系統(tǒng)
1.1 操作系統(tǒng)及其功能
1.2內(nèi)存地址重定位
1.3進(jìn)程和線程
2.4Spooling技術(shù)
2、敘述操作系統(tǒng)提供系統(tǒng)調(diào)用的原因，并舉例說明應(yīng)用程序使用這些系統(tǒng)功能調(diào)用的兩種方式。（10）
3、為了支持請(qǐng)求式分頁(yè)內(nèi)存管理，通常頁(yè)表項(xiàng)內(nèi)存有一標(biāo)志位，用來記錄相應(yīng)的頁(yè)是否被寫過，請(qǐng)解釋該標(biāo)志位的操作者及其作用。
4、假設(shè)有一組任務(wù)序列{（x、y）}，x表示到達(dá)時(shí)間，y表示需要運(yùn)行的時(shí)間，在FCFS和最短作業(yè)優(yōu)先下的平均周轉(zhuǎn)時(shí)間。（10）
5、給出一種文件目錄結(jié)構(gòu)的設(shè)計(jì)，并評(píng)價(jià)這種設(shè)計(jì)的優(yōu)缺點(diǎn)。
6、超市可容納500人同時(shí)購(gòu)物，有6扇可供出入的門，既可進(jìn)又可出，每扇
門只允許一個(gè)人通過：
6.1用PV操作及信號(hào)量描述進(jìn)入和離開該超市的算法，使得該超市的購(gòu)物容量得到最大發(fā)揮。
6.2如再加一個(gè)限制條件：同一個(gè)顧客進(jìn)出必須通過同一扇門，那么相應(yīng)算法如何寫







2001年攻讀碩士學(xué)位研究生入學(xué)考試試題
學(xué)科，專業(yè)：…………研究方向：………….考試科目：操作系統(tǒng).

一，是非題：判斷是非并給出解釋。（5‘*4）
1．1分布式操作系統(tǒng)和網(wǎng)絡(luò)操作系統(tǒng)沒有本質(zhì)區(qū)別。
1．2使用快表技術(shù)事實(shí)上將增加一次快表的訪問時(shí)間，所以在內(nèi)存中應(yīng)該慎用該技術(shù)。
1．3死鎖在操作系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)中是絕對(duì)不容許出現(xiàn)。
1．4原語(yǔ)操作是不可被中斷的。
二，簡(jiǎn)述題。（5‘*4）
2．1進(jìn)程和線程的異同。
2．2操作系統(tǒng)本質(zhì)上也需要時(shí)空開銷的，這樣解釋這些開銷還是值得的。
2．3簡(jiǎn)述存儲(chǔ)器管理的基本目的和基本問題。
2．4簡(jiǎn)述設(shè)備分配的基本類型和基本策略。
三，敘述中斷機(jī)制在操作系統(tǒng)中的地位和作用。（10‘）
四，試給出一種實(shí)現(xiàn)虛存的解決方案。（10‘）
五，舉出設(shè)備管理子系統(tǒng)中利用中斷，輪詢和DMA的例子。（12‘）
六，以下是 Linux文件系統(tǒng)的四個(gè)相關(guān)的結(jié)構(gòu)定義的一部分：
6．1請(qǐng)描述這些結(jié)構(gòu)的作用和相互關(guān)系；（8‘）
6．2根據(jù)這些結(jié)構(gòu)，請(qǐng)描述文件的物理結(jié)構(gòu)；（8‘）
6．3基于這些結(jié)構(gòu)，請(qǐng)?jiān)O(shè)計(jì)至少四條有關(guān)文件系統(tǒng)功能調(diào)用的實(shí)現(xiàn)。（12‘）
struct inode{
struct list_head i_hash;
struct list_head i_dentry;
unsigned ling i_ino;
unsigned int i_count;
kdev_t i_dev;
umode_t i_mode;
off_t i_size;
time_t i_atime;
time_t i_mtime;
time_t i_ctime;
unsigned long i_blksize;
unsigned long i_block;
union{
struct ext2_inode_info ext2_i;
}u;
};
struct ext2_inode_info{
_u32 i_data[15];
_u32 _flags;
};

struct dentry{
int d_count;
struct inode *d_inode;/*Where the name belongs to –NULL is negative*/
struct dentry *d_parent;/*parent directory*/
struct list_head d_hash;/*lookup hash list*/
unsigned char d_iname[DNAME_INLINE_LEN];/*small names*/
};
struct list_head{
struct list_head *next,*prev;
};
2001年攻讀碩士學(xué)位研究生入學(xué)考試試題
學(xué)科，專業(yè)：…………研究方向：………….考試科目：數(shù)據(jù)結(jié)構(gòu)及程序設(shè)計(jì)
算法請(qǐng)用類 PASCAL或類C 語(yǔ)言編寫，程序請(qǐng)用PASCAL 或類C語(yǔ)言編寫
一．假設(shè)以帶頭結(jié)點(diǎn)的循環(huán)鏈表表示隊(duì)列，并且只設(shè)一個(gè)指針指向隊(duì)尾結(jié)點(diǎn)（注意不設(shè)頭指針），試編寫相應(yīng)的置空隊(duì)列，入隊(duì)列和出隊(duì)列的算法。（10分）

二．假設(shè)有兩個(gè)按元素值遞增有序排列的線性表A和B，A和B均一單鏈表表示，請(qǐng)編寫算法將表A，B歸并成一按元素值遞減有序排列的線性表C，并要求利用原表（即表A和表B）結(jié)點(diǎn)空間存放表C。（10分）

三．1．何謂排序方法的穩(wěn)定性？（3分）
2．下列排序方法哪些是穩(wěn)定的哪些是不穩(wěn)定的？（4分）
3．對(duì)不穩(wěn)定的方法舉實(shí)例說明之。（8分）
直接插入排序，希爾排序，快速排序，歸并排序

四．試編寫歸并排序算法。（10分）

五．有下列關(guān)鍵字：（10分）
15，23，29，31，47，66，74，85，90，98，102
1．畫出描述折半查找過程的判別樹。
2．對(duì)含關(guān)鍵字的有序表，采用折半查找，在查找成功時(shí)，關(guān)鍵字比較次數(shù)至多是多少？在查找不成功時(shí)，關(guān)鍵字比較次數(shù)至多是多少？

六．編寫一算法，判別以鄰接表方式存儲(chǔ)的有向圖中是否存在頂點(diǎn)Vi到頂點(diǎn)Vj的路徑。（10分）

七．1．何謂二叉排序樹？（5分）
2．把數(shù)據(jù)組織為二叉排序樹有和優(yōu)點(diǎn)？（5分）
3．設(shè)有一組數(shù)據(jù)a1,a2,a3,……,an,試編寫一程序把這n個(gè)數(shù)據(jù)放入一二叉排序樹中，要求該樹盡可能平衡（二叉排序樹用鏈表表示，算法輸出為該二叉排序樹的根結(jié)點(diǎn)）。（10分）

八．編寫一算法，輸出一集合的冪集。（15分）
蘇州大學(xué)
2000年攻讀碩士學(xué)位研究生入學(xué)考試試題
學(xué)科，專業(yè)：…………研究方向：………….考試科目：操作系統(tǒng)

1， 簡(jiǎn)述題（4*8‘）
1．1， 請(qǐng)簡(jiǎn)述進(jìn)程和現(xiàn)程之間的異同。
1．2， 程序的鏈接方法中有一種是運(yùn)行時(shí)動(dòng)態(tài)鏈接，什么是運(yùn)行是動(dòng)態(tài)鏈接，有什么特點(diǎn)？
1．3， 如何區(qū)分分時(shí)操作系統(tǒng)的客戶運(yùn)行的程序和網(wǎng)絡(luò)操作系統(tǒng)所支持的客戶端的運(yùn)行程序？
1．4， 簡(jiǎn)述設(shè)備管理的基本功能。

2，如果一個(gè)作業(yè)在執(zhí)行中，按下列頁(yè)號(hào)訪問：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6作業(yè)固定占用4塊內(nèi)存空間，采用先進(jìn)先出淘汰算法和最近最少調(diào)用淘汰算法是，各產(chǎn)生多少次缺頁(yè)中斷？寫出在淘汰時(shí)在內(nèi)存的頁(yè)面號(hào)和被淘汰的頁(yè)面號(hào)。（18‘）

3， 用管程的方法解決生產(chǎn)者—消費(fèi)者問題：有若干個(gè)生產(chǎn)者和消費(fèi)者共享一個(gè)容量為m的緩沖區(qū)。（10‘）

4， 描述請(qǐng)求分頁(yè)存儲(chǔ)管理方式的實(shí)現(xiàn)過程。（20‘）
5， 請(qǐng)敘述UNIX的文件管理系統(tǒng)的設(shè)計(jì)和實(shí)現(xiàn)。（20‘）
蘇州大學(xué)
2000年攻讀碩士學(xué)位研究生入學(xué)考試試題
學(xué)科，專業(yè)：…………研究方向：………….考試科目：數(shù)據(jù)結(jié)構(gòu)及程序設(shè)計(jì)
算法請(qǐng)用類 PASCAL或類C 語(yǔ)言編寫，程序請(qǐng)用PASCAL 或類C語(yǔ)言編寫
一．填空（15分）
1．已知一棵二叉樹的前根序列是BEFCGDH，中根序列是FEBGCHD，則后根序列必為（ ）。
2．設(shè)二叉樹根結(jié)點(diǎn)的層次為1，深度為K的二叉樹至多有（ ）個(gè)結(jié)點(diǎn)。
3．ISAM文件是（ ）文件，VSAM文件是（ ）文件。
二．若在三對(duì)角線矩陣A中，三條對(duì)角線組成的帶狀區(qū)域按行的順序放在一維數(shù)組中，即a11放在B[1]中，a12放在B[2]中，……，寫一個(gè)地址公式，由B[1]的地址Loc（B[1]）確定aij的地址Loc（A[i，j]）。（10分）

a11 a12
a21 a22 a23
A= a32 a33 a34

a n-1 n-1 a n-1 n
a n n-1 a n n

三．設(shè)一篇短文中出現(xiàn)的字符D={S，I，P，Q，T}，每個(gè)字符出現(xiàn)的次數(shù)為F={10，29，4，9，5}
1．如何對(duì)上面的諸字符進(jìn)行二進(jìn)制編碼，使得
（1） 該短文的總長(zhǎng)度最短；
（2） 為了譯碼，任一字符的編碼不應(yīng)是另一字符的編碼的前綴。
2． 按你得出的字符編碼，將二進(jìn)制字串‘000100011010100’進(jìn)行譯碼（譯成字符）。
（15分）
四．試編寫廣度優(yōu)先遍歷圖的算法。（10分）

五．已知二叉樹前根遍歷序列的后根遍歷序列，試編寫生成該二叉樹的算法。算法的輸入為二個(gè)以字符串形式表示的前根遍歷序列和后根遍歷序列，算法的輸出為該二叉樹，用根結(jié)點(diǎn)指針表示。（10分）

六．生成一個(gè)按蛇形方式排列自然數(shù)1，2，3，4，……，n（n+1）/2的上三角N階方陣，N階方陣用二維數(shù)組表示，試編寫程序。（10分）
N=5的N階方陣的上三角為：
1 3->4 10->11
2 5 9 12
6 8 13
7 14
15

七．選取哈希函數(shù)H（k）=(3k)MOD 11,d1=H(k),di=(di-1 + (7k)MOD 10 + 1)MOD 11 (i=1,2,3……)。試在0到10的地址空間里對(duì)關(guān)鍵字序列（22，41，53，46，30，13，01，67）構(gòu)造哈希表，并求在等概情況下查找成功與不成功時(shí)的平均查找長(zhǎng)度。（15分）

八．有若干條紅色，黃色的色條隨機(jī)擺滿一行，試用復(fù)雜度為O（n）的算法把他們按顏色有序擺放（顏色相同放在一起），最多使用一個(gè)單元的額外附加空間。（15分）
zz

11能被5整除嗎？

考研論壇提示：
1、請(qǐng)勿發(fā)布個(gè)人聯(lián)系方式或詢問他人聯(lián)系方式，包括QQ和手機(jī)等。
2、未經(jīng)允許不得發(fā)布任何資料出售、招生中介等廣告信息。
3、如果發(fā)布了涉及以上內(nèi)容的話題或跟帖，您在考研網(wǎng)的注冊(cè)賬戶可能被禁用。