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

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

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







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

一，是非題：判斷是非并給出解釋。（5‘*4）
1．1分布式操作系統(tǒng)和網(wǎng)絡(luò)操作系統(tǒng)沒有本質(zhì)區(qū)別。
1．2使用快表技術(shù)事實上將增加一次快表的訪問時間，所以在內(nèi)存中應(yīng)該慎用該技術(shù)。
1．3死鎖在操作系統(tǒng)的設(shè)計和實現(xiàn)中是絕對不容許出現(xiàn)。
1．4原語操作是不可被中斷的。
二，簡述題。（5‘*4）
2．1進程和線程的異同。
2．2操作系統(tǒng)本質(zhì)上也需要時空開銷的，這樣解釋這些開銷還是值得的。
2．3簡述存儲器管理的基本目的和基本問題。
2．4簡述設(shè)備分配的基本類型和基本策略。
三，敘述中斷機制在操作系統(tǒng)中的地位和作用。（10‘）
四，試給出一種實現(xiàn)虛存的解決方案。（10‘）
五，舉出設(shè)備管理子系統(tǒng)中利用中斷，輪詢和DMA的例子。（12‘）
六，以下是 Linux文件系統(tǒng)的四個相關(guān)的結(jié)構(gòu)定義的一部分：
6．1請描述這些結(jié)構(gòu)的作用和相互關(guān)系；（8‘）
6．2根據(jù)這些結(jié)構(gòu)，請描述文件的物理結(jié)構(gòu)；（8‘）
6．3基于這些結(jié)構(gòu)，請設(shè)計至少四條有關(guān)文件系統(tǒng)功能調(diào)用的實現(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年攻讀碩士學位研究生入學考試試題
學科，專業(yè)：…………研究方向：………….考試科目：數(shù)據(jù)結(jié)構(gòu)及程序設(shè)計
算法請用類 PASCAL或類C 語言編寫，程序請用PASCAL 或類C語言編寫
一．假設(shè)以帶頭結(jié)點的循環(huán)鏈表表示隊列，并且只設(shè)一個指針指向隊尾結(jié)點（注意不設(shè)頭指針），試編寫相應(yīng)的置空隊列，入隊列和出隊列的算法。（10分）

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

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

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

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

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

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

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

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

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

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

4， 描述請求分頁存儲管理方式的實現(xiàn)過程。（20‘）
5， 請敘述UNIX的文件管理系統(tǒng)的設(shè)計和實現(xiàn)。（20‘）
蘇州大學
2000年攻讀碩士學位研究生入學考試試題
學科，專業(yè)：…………研究方向：………….考試科目：數(shù)據(jù)結(jié)構(gòu)及程序設(shè)計
算法請用類 PASCAL或類C 語言編寫，程序請用PASCAL 或類C語言編寫
一．填空（15分）
1．已知一棵二叉樹的前根序列是BEFCGDH，中根序列是FEBGCHD，則后根序列必為（ ）。
2．設(shè)二叉樹根結(jié)點的層次為1，深度為K的二叉樹至多有（ ）個結(jié)點。
3．ISAM文件是（ ）文件，VSAM文件是（ ）文件。
二．若在三對角線矩陣A中，三條對角線組成的帶狀區(qū)域按行的順序放在一維數(shù)組中，即a11放在B[1]中，a12放在B[2]中，……，寫一個地址公式，由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}，每個字符出現(xiàn)的次數(shù)為F={10，29，4，9，5}
1．如何對上面的諸字符進行二進制編碼，使得
（1） 該短文的總長度最短；
（2） 為了譯碼，任一字符的編碼不應(yīng)是另一字符的編碼的前綴。
2． 按你得出的字符編碼，將二進制字串‘000100011010100’進行譯碼（譯成字符）。
（15分）
四．試編寫廣度優(yōu)先遍歷圖的算法。（10分）

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

六．生成一個按蛇形方式排列自然數(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的地址空間里對關(guān)鍵字序列（22，41，53，46，30，13，01，67）構(gòu)造哈希表，并求在等概情況下查找成功與不成功時的平均查找長度。（15分）

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

一周有幾天？（答案為數(shù)字）

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