蘇州大學
2003年攻讀碩士學位研究生入學考試試題
學科，專業：…………研究方向：………….考試科目：操作系統與數據結構

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

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







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

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

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

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

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

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

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

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

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

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

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

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

4， 描述請求分頁存儲管理方式的實現過程。（20‘）
5， 請敘述UNIX的文件管理系統的設計和實現。（20‘）
蘇州大學
2000年攻讀碩士學位研究生入學考試試題
學科，專業：…………研究方向：………….考試科目：數據結構及程序設計
算法請用類 PASCAL或類C 語言編寫，程序請用PASCAL 或類C語言編寫
一．填空（15分）
1．已知一棵二叉樹的前根序列是BEFCGDH，中根序列是FEBGCHD，則后根序列必為（ ）。
2．設二叉樹根結點的層次為1，深度為K的二叉樹至多有（ ）個結點。
3．ISAM文件是（ ）文件，VSAM文件是（ ）文件。
二．若在三對角線矩陣A中，三條對角線組成的帶狀區域按行的順序放在一維數組中，即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

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

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

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

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

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

四川省省會城市是哪里？（答案為兩個字）

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