數(shù)據(jù)結(jié)構(gòu)試卷

1、數(shù)據(jù)結(jié)構(gòu)試卷及答案一、 選擇題（每小題2分，共30分）1計(jì)算機(jī)識(shí)別、存儲(chǔ)和加工處理的對(duì)象被統(tǒng)稱為( )。A.數(shù)據(jù) B.數(shù)據(jù)元素 C.數(shù)據(jù)結(jié)構(gòu) D.數(shù)據(jù)類型2棧和隊(duì)列都是（ ）。A限制存取位置的線性結(jié)構(gòu) B順序存儲(chǔ)的線性結(jié)構(gòu)C鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu) D限制存取位置的非線性結(jié)構(gòu) 3鏈棧與順序棧相比，比較明顯的優(yōu)點(diǎn)是( ) 。A.插入操作更加方便 B.刪除操作更加方便C.不會(huì)出現(xiàn)下溢的情況 D.不會(huì)出現(xiàn)上溢的情況4采用兩類不同存儲(chǔ)結(jié)構(gòu)的字符串可分別簡(jiǎn)稱為( ) 。A.主串和子串 B.順序串和鏈串C.目標(biāo)串和模式串 D.變量串和常量串5 一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元

2、素的地址是：（ ）。A. 110 B .108 C. 100 D. 120 6串是一種特殊的線性表，其特殊性體現(xiàn)在：（ ）。A.可以順序存儲(chǔ) B .數(shù)據(jù)元素是一個(gè)字符C. 可以鏈接存儲(chǔ) D. 數(shù)據(jù)元素可以是多個(gè)字符7設(shè)高度為h的二叉樹上只有度為0和度為2的結(jié)點(diǎn)，則此類二叉樹中所包含的結(jié)點(diǎn)數(shù)至少為：（ ）。A. 2h B .2h-1 C. 2h+1 D. h+1 8樹的基本遍歷策略可分為先根遍歷和后根遍歷；二叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把 由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對(duì)應(yīng)的二叉樹。下列結(jié)論哪個(gè)正確？ ( )。A. 樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序

3、列相同B .樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同C. 樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同D. 以上都不對(duì)9一個(gè)有n個(gè)頂點(diǎn)的無向圖最多有多少邊？（ ）。A. n B .n(n-1) C. n(n-1)/2 D. 2n10在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的多少倍? （ ）。A. 1/2 B .1 C. 2 D. 4 11當(dāng)在二叉排序樹中插入一個(gè)新結(jié)點(diǎn)時(shí)，若樹中不存在與待插入結(jié)點(diǎn)的關(guān)鍵字相同的結(jié)點(diǎn)，且新結(jié)點(diǎn)的關(guān)鍵字小于根結(jié)點(diǎn)的關(guān)鍵字，則新結(jié)點(diǎn)將成為（ ）。A左子樹的葉子結(jié)點(diǎn) B左子樹的分支結(jié)點(diǎn)C右子樹的葉子結(jié)點(diǎn) D右子樹的分支結(jié)點(diǎn)12對(duì)于哈希函數(shù)H(key)=

4、key%13,被稱為同義詞的關(guān)鍵字是( )。A.35和41 B.23和39 C.15和44 D.25和5113、 在下列排序算法中，在待排序的數(shù)據(jù)表已經(jīng)為有序時(shí)，花費(fèi)時(shí)間反而最多的是（ ）。 A.快速排序 B.希爾排序 C.冒泡排序 D.堆排序 14、對(duì)有18個(gè)元素的有序表做折半查找，則查找A3的比較序列的下標(biāo)依次為（ ）。 A.1-2-3 B.9-5-2-3C.9-5-3 D. 9-4-2-3 15、下列排序算法中，某一趟結(jié)束后未必能選出一個(gè)元素放在其最終位置上的是（ ）。 A.堆排序 B.冒泡排序 C.快速排序 D.直接插入排序 二、判斷題（每小題1分，共10分） 1.線性表的長(zhǎng)度是線性表

5、所占用的存儲(chǔ)空間的大小。 2.雙循環(huán)鏈表中，任意一結(jié)點(diǎn)的后繼指針均指向其邏輯后繼。 3.在對(duì)鏈隊(duì)列做出隊(duì)操作時(shí)，不會(huì)改變front指針的值。 4.如果兩個(gè)串含有相同的字符，則說它們相等。 5.如果二叉樹中某結(jié)點(diǎn)的度為1，則說該結(jié)點(diǎn)只有一棵子樹。 6.已知一棵樹的先序序列和后序序列，一定能構(gòu)造出該樹。 7.圖G的一棵最小代價(jià)生成樹的代價(jià)未必小于G的其它任何一棵生成樹的代價(jià)。 8.圖G的拓?fù)湫蛄形ㄒ唬瑒t其弧數(shù)必為n-1（其中n為頂點(diǎn)數(shù)）。 9.對(duì)一個(gè)堆按層次遍歷，不一定能得到一個(gè)有序序列。10.直接選擇排序算法滿足：其時(shí)間復(fù)雜度不受數(shù)據(jù)的初始特性影響，為O(n2)。三填空題（每題2分共20分）1有

6、向圖的存儲(chǔ)結(jié)構(gòu)有（ ）、（ ）、（ ）等方法。2已知某二叉樹的先序遍歷次序?yàn)閍fbcdeg，中序遍歷次序?yàn)閏edbgfa。其后序遍歷次序?yàn)椋?）。層次遍歷次序?yàn)椋?）。3設(shè)有二維數(shù)組A 5 x 7 ,每一元素用相鄰的4個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知A00的存儲(chǔ)地址為100。則按行存儲(chǔ)時(shí)，元素A14的第一個(gè)字節(jié)的地址是（ ）；按列存儲(chǔ)時(shí)，元素A14的第一個(gè)字節(jié)的地址是（ ）。4請(qǐng)?jiān)谙聞澗€上填入適當(dāng)?shù)恼Z(yǔ)句，完成以下法算。Status Preordertraverse(Bitree T,Status(*Visit)(Telemtype e) /先序非遞歸遍歷二叉樹Initstack ( S );

7、 Push ( S,T );While ( !stackempty( S ) ) While ( gettop( S, p )& p ) visit (p-data ) ; ; Pop ( S , p ); If ( !stackempty(s) ) ; ; return ok;四、應(yīng)用題(每小題6分，共18分) 1.假定在學(xué)生的檔案中含有：姓名、學(xué)號(hào)、年齡、性別。如采用線性表作為數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)檔案管理問題，分別給出線性表的在順序?qū)崿F(xiàn)下的類型定義和在鏈接實(shí)現(xiàn)下的類型定義。 2.有一份電文中共使用五個(gè)字符：a、b、c、d、e,它們的出現(xiàn)頻率依次為8、14、10、4、18，請(qǐng)構(gòu)造相應(yīng)的哈夫曼樹(左

8、子樹根結(jié)點(diǎn)的權(quán)小于等于右子樹根結(jié)點(diǎn)的權(quán))，求出每個(gè)字符的哈夫曼編碼。 3.有初始的無序序列為98,65,38,40,12,51,100,77,26,88,給出對(duì)其進(jìn)行歸并排序(升序)的每一趟的結(jié)果。 五算法設(shè)計(jì)題（每小題11分，共22分）1. 單鏈表結(jié)點(diǎn)的類型定義如下：typedef struct LNode int data; struct LNode *next; LNode, *Linklist;寫一算法，將帶頭結(jié)點(diǎn)的有序單鏈表A和B合并成一新的有序表C。(注:不破壞A和B的原有結(jié)構(gòu).)2. 二叉樹用二叉鏈表存儲(chǔ)表示。typedef struct BiTNode TelemType da

9、ta; Struct BiTNode *lchild, *rchild; BiTNode, *BiTree;編寫一個(gè)復(fù)制一棵二叉樹的遞歸算法。一、A A D B B B C A C C A D A C D二、三、1、鄰接矩陣、鄰接表、十字鏈表2、edcgbfa、afbcgde3、144、1844、push(S, p-lchild) pop(S, p) push( S, p-rchild )四、1.順序?qū)崿F(xiàn)： const maxsize=100; 順序表的容量 type datatype=record 檔案數(shù)據(jù)類型 namestring10;姓名 numberinteger;學(xué)號(hào) sexbool

10、ean;性別 ageinteger;年齡 end; type slist =record dataarray 1.maxsize of datatype; lastinteger; end; 鏈接實(shí)現(xiàn)： type pointer=node; node=record namestring 10;姓名 numberinterger； 學(xué)號(hào) sex boolean;性別 ageinteger;年齡 nextpointer;結(jié)點(diǎn)的后繼指針 end; list=pointer; 2.哈夫曼樹為： 相應(yīng)的哈夫曼編碼為： a:001 b:10 c:01 d:000 e:113.初始無序序列： 98 65 3

11、8 40 12 51 100 77 26 88 98 65 38 40 12 51 10077 2688第一次歸并： 65 98 38 40 12 51 77 100 26 88第二次歸并： 38 40 65 98 12 51 77 100 26 88第三次歸并： 12 38 40 51 65 77 98 100 26 88第四次歸并： 12 26 38 40 51 65 77 88 98 100五、Merge(Linklist A, Linklist B, Linklist &C )void Merge(Linklist A, Linklist B, Linklist &C) C=(Link

12、list)malloc(sizeof(LNode);pa=A-next; pb=B-next; pc=C;while(pa&pb) pc-next=(Linklist)malloc(sizeof(LNode);pc=pc-next;if(pa-datadata) pc-data=pa-data; pa=pa-next;else pc-data=pb-data; pb=pb-next;if(!pa) pa=pb;while(pa) pc-next=(Linklist)malloc(sizeof(LNode);pc=pc-next;pc-data=pa-data; pa=pa-next;pc-next=NULL;BiTree CopyTree(BiTree T) if (