大連理工大學(xué)考研專業(yè)課真題_2005年_數(shù)據(jù)結(jié)構(gòu).pdf

大連理工考研專業(yè)課真題_2005年_數(shù)據(jù)結(jié)構(gòu) ，大連理工考研專業(yè)課真題 2005年 數(shù)據(jù)結(jié)構(gòu)。
歡迎下載！
大連理工考研專業(yè)課真題 數(shù)據(jù)結(jié)構(gòu)(2005)
一、填空題(10分) 1.對長度為n的線性表采用順序查找，在等概率的條件下，查找成功的平均檢索長度為 _____。
在長度為 n的順序表中刪除第i(1<=i<=n)個(gè)數(shù)據(jù)元素需要移動(dòng)_____個(gè)數(shù)據(jù)元 素。
在長度為 n的順序表中的第 i(1<=i<=n)個(gè)數(shù)據(jù)元素之前插入一個(gè)新元素，需要移 動(dòng)______個(gè)數(shù)據(jù)元素。
2.高度為 i(i>=1)的完全二叉樹最多有______個(gè)結(jié)點(diǎn)，最少有_____個(gè)結(jié)點(diǎn)；若按自上而 下，從左到右的次序給結(jié)點(diǎn)編號(從 1開始)，則編號最小的葉子結(jié)點(diǎn)的編號為______。
3.設(shè)有n階 3對角陣(aij)n×n將其三條對角線上的元素存于數(shù)組 B[3][n]中，使得元 素 B[u][v]＝aij， 從(i，j)到(u，v)的下標(biāo)變換公式為___________。
4.線性表的______存儲結(jié)構(gòu)是隨機(jī)存儲結(jié)構(gòu)。
5.設(shè)字符 a,b,c,d,e,f的使用頻度分別為3，4，9，12，15，20。
則b，d的哈夫曼編碼分 別為______,_________.
二、回答下列問題 (20分) 1.對長度為n的記錄序列進(jìn)行快速排序時(shí)，所需進(jìn)行的比較次數(shù)依賴于這 n個(gè)元素的初始 排列。
(1)你＝7時(shí)，在最好情況下需要進(jìn)行多少次比較？請說明理由。
(2)對 n＝7，給出一 個(gè)最后情況的初始排列的具體例子。
2.已知在一棵含有 n個(gè)結(jié)點(diǎn)的樹中，只有度為 k的分支結(jié)點(diǎn)和度為0的葉子結(jié)點(diǎn)，求該樹 含有的葉子結(jié)點(diǎn)數(shù)。
3.假設(shè)一棵二叉樹的層次遍歷序列為abcdefghij， 中序遍歷序列為 db