杭州電子科技大學數據結構期末試卷

1、杭州電子科技大學學生考試卷（A ）卷考試課程數據結構考試日期2011年 月 日成績課程號教師號任課教師姓名考生姓名學號（8位）年級專業(yè)1 .判斷題：（每小題2分，共20分）1 .鏈棧的初始化是指開辟足夠多的結點，然后置棧頂指針為NULL（）2 .數據的物理結構是指數據在計算機內的實際存儲形式。（）3 .線性表采用鏈表存儲時，查找第i個元素的時間與i的值無關。（）4 .將一棵樹轉成二叉樹，根結點沒有左子樹。（）5 .廣義表的取表尾運算，其結果通常是個表，但有時也可是個原子。（）6 .完全二叉樹的某結點若無左孩子，則它必是 葉結點。（）7 .用鄰接矩陣表示圖時，矩陣元素的個數與邊的條數有關。（）8

2、 .圖的深度優(yōu)先遍歷序列和廣度優(yōu)先遍歷序列不是唯一的。（）9 .用簡單選擇排序算法，只需一趟掃描即可選出鍵值最大（或最小）的元素 。（）10 .采用線性探測法處理散列時的沖突，當從哈希表刪除一個記錄時，不應將這個記錄的所在位置置空，因為這會影響以后的查找。（2 .選擇題：（每小題2分，共18分）1 .設有一個10階的對稱矩陣A,采用壓縮存儲方式，以行序為主存儲，all為第一元素, 其存儲地址為1,每個元素占一個地址空間，則 a85的地址為（）。A. 13B. 33C. 18D. 402 .下面關于線性表的敘述中，錯誤的是哪一個？（）A.線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。B.線性表

3、采用順序存儲，便于進行插入和刪除操作。C.線性表采用鏈接存儲，不必占用一片連續(xù)的存儲單元。D.線性表采用鏈接存儲，便于插入和刪除操作。3 .循環(huán)隊列存儲在數組 A0.m中，則入隊時的操作為（）。A. rear=rear+1B. rear=（rear+1） mod （m-1）C. rear=（rear+1） mod m D. rear=（rear+1）mod（m+1）4 .對于深度為K的滿二叉樹（結點編號從1開始，根結點的層數為1）,其第K層上最后1 個結點的編號為（）。A.2 K B.2 K-1C.2 K-1-1D.2 K-15 . 一個有N個頂點的無向圖最多有（）條邊。A.N B.N*（N

4、-1） C.N*（N -1）/2D.2*N6 .隊列具有（）的特點，是操作受限的線性表。A.先進先出B.先進后出C.沒有特點7 .從未排序序列中依次取出一個元素與已排序序列中的元素依次進行比較，然后將其放在已排序序列的合適位置，該排序方法稱為（）排序法。A.插入 B. 選擇 C. 希爾 D.二路歸并8 .在計算機內實現遞歸算法時所需的輔助數據結構是（）A.棧B.隊列C.樹D.圖9 .若一個算法的時間復雜度用 O（n）表示，其中n的含義是（）A.問題規(guī)模B .語句條數C .循環(huán)層數D,函數數量三.填空題：（每空2分，共12分）1 .非空的平衡二叉樹，樹中每個結點的左子樹和右子樹的深度之差的絕對值

5、不超過2.深度為h的二叉樹最少有 個結點3 .對一棵二叉排序樹進行 遍歷可以得到一個有序序列。4 .具有10個頂點的連通圖，其 最小生成樹的邊數為。5 .在一棵m階B-樹中，每個非葉子結點至多有個關鍵字。6 .快速排序平均時間復雜度為O(nlogn),最壞情況下時間復雜度是。四.應用題：(每小題8分，共40分)1 .已知一棵二叉樹 T的先序序列為：EBADCFHGIKJ中序序列為：ABCDEFGHIJK(1)試畫出該二叉樹.(2)若該二叉樹用孩子兄弟表示法表示，試畫出與此二叉樹對應存儲關系的樹的形態(tài)。2 .設散列表長度為11,散列函數H (k) k MOD1,若輸入順序為(2, 4, 18,

6、23, 26, 7, 12)。試用線性探測開放址法 解決沖突構造散列表并求在等概率情況下查找成功的平均查找K度。3 .假設用于通信的電文由7個字母組成，字母在電文中出現的頻率分別為 5, 7, 9, 16, 23,18, 22要求構建的哈夫曼樹中的結點，其左孩子的權值小于右孩子權值。試為這7個字母設“哈夫曼編碼。4,給廿組關鍵碼18, 31, 16, 22, 51, 30, 24,要求構建一個小頂堆，回出構建初始 世的過程。5.已知帶權的無向圖的鄰接矩陣如下圖所示，其頂點集合為A,B, C,D,日。畫出該圖及其最小生成樹(如有多棵，只需寫出其中一棵即可)。五.算法設計：(每小題5分，共10分)

7、1 .利用二叉鏈表作為存儲結構，試編寫算法求二叉樹中度為2的結點個數。/二叉樹結點 template<class ElemType> struct BTNodeElemTypedata;/結點值BTNode<ElemType> *lchild;/左孩子結點指針BTNode<ElemType> *rchild;/右孩子結點指針;/二叉鏈表類 template<class ElemType> class BinaryTree public:BinaryTree():m_root(NULL)BinaryTree()int count(BTNode<

8、;ElemType>* T)/求一叉樹中度為2的結點的個數.private:BTNode<ElemType> *m_root;/一叉樹根結點指針(沈靜老師班級用)： typedef struct BiTNode TElemType data;struct BiTNode *lchild,*rchild;BiTNode, *BiTree; int Count(BiTree pTree);2 .試寫一個C+程序實現：在帶頭結點的單鏈表中第i個數據元素之前(i的合法值為1&i&len+1,插入新的數據元素 etruefalse template <class

9、ElemType>class LinkList: public List<ElemType> public:LinkList();LinkList();；bool OrderInsert(const ElemType &e, int i); 實現該函數 ;private:int len;/單鏈表長度LinkNode<ElemType> *head;head 是頭指針J/單鏈表結點類emplate <class ElemType> struct LinkNode ElemType data;LinkNode<ElemType> *next;（沈靜老師班級用）：函數形式如