東北大學2002年數據結構考研試題
來源：
時間：2007-06-06 14:35:43
2002年考研試題
一、回答下列問題：（24分）
1，如果用一個循環(huán)數組q[0..m-1]表示隊列時，該隊列只有一個隊列頭指針front，不設隊列尾指針rear，而改置計數器count用以記錄隊列中結點的個數。
1）編寫實現隊列的基本運算：判空、入隊、出隊（3分）
2）隊列中能容納元素的最多個數是多少？（1分）
2、設有對角矩陣a[1..n,1..n]把非零元素按列存儲在向量b[1..3*n-2]中，使得b[k]=a[I,j].
求：（1）用I,j表示k的下標變換公式（2分）
（2）用k表示I,j的下標變換公式（2分）
3、設二叉排序樹中關鍵字由1到1000的整數組成，現要查找關鍵字為363的結點，下述評關鍵字序列哪一個不可能是在二叉排序樹中找到的序列？說明原因。（4分）
（1）51，250，501，390，320，340，382，363
（2）24，877，125，342，501，623，421，363
4、設有n個無序元素，按非遞減次序排序，但只想得到前面長度為k的部分序列，其中n>>k，最好采用什么排序方法？為什么？（2分）
如果有這樣一個序列{59，11，26，34，17，91，25}，得到的部分序列是：{11，17，25}，對于該例使用所選擇的方法實現時，共執(zhí)行多少次比較？（3分）
5、在B-樹和B 樹中查找關鍵字時有什么不同？（2分）
6、寫出對關鍵字序列{503，087，512，061，908，124，897，275，653，426}
建立一棵平衡二叉樹的過程，并寫出調整平衡時的指針變化。（5分）
二、解答下列問題：（10分）
1、畫出對長度為10的有序表進行二分查找的判定樹并求其等概率時查找成功的平均查找長度（5分）。
2、設有一組關鍵字{9，01，23，14，55，20，84，27}，采用哈希函數：H（key）=key mod 7 ，表長為10，用開放地址法的二次探測再散列方法Hi=(H(key) di)mod10(di=1*1,2*2,3*3….)解決沖突。要求：對該關鍵字序列構造哈希表，并計算查找成功的平均查找長度（5分）。
三、已知L為沒有頭結點的的單鏈表中第一個結點的指針，每個結點數據域存放一個字符，該字符可能是英文字母字符或數字字符或其他字符，編寫算法構造三個以帶頭結點的單循環(huán)鏈表表示的線性表，使每個表中只含同一類字符。（要求用最少的時間和最少的空間）（15分）
四、對以二叉鏈表存儲的非空二叉樹，從右向左依次釋放所有的葉子結點，釋放的同時把結點值存放到一個向量中
要求：（1）用文字寫出實現上述過程的基本思想（3分）
（2）寫出算法（12分）
五、設二叉排序樹已經以二叉鏈表的形式存儲在內存中，使用遞歸方法，求各結點的平衡因子并輸出。
要求：（1）用文字寫出實現上述過程的基本思想（3分）
（2）寫出算法（12分）
六、假設一個有向圖g已經以右圖所示的逆鄰接表形式存儲在內存中，
要求：（1）寫出逆鄰接表的存儲結構定義（3分）
（2）用文字寫出在逆鄰接表上實現拓撲排序的基本思想（3分）
（3）寫出在逆鄰接表上實現拓撲排序的算法 （15分）。
結束
特別聲明：①凡本網注明稿件來源為"原創(chuàng)"的，轉載必須注明"稿件來源：育路網"，違者將依法追究責任；
②部分稿件來源于網絡，如有侵權，請聯(lián)系我們溝通解決。
閱讀全文
招生服務平臺始創(chuàng)于1999年
打開微信掃一掃，關注育路教育官方微信
