杭州電子科技大學(xué)數(shù)據(jù)結(jié)構(gòu)期末試卷

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

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

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

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

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

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

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

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

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