數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案

1、a.最優(yōu)二叉樹d.二叉排序樹4. 下列查找方法中，a.順序查找d .哈希查找5. 在順序表查找中，a. 設(shè) 置監(jiān)視 哨b.鏈表存貯c.二分查找數(shù)據(jù)結(jié)構(gòu)期末考試試題及答案期末樣卷參考答案 一是非題（每題 1 分共 10 分）1. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。 F2. 棧和隊(duì)列也是線性表。 如果需要， 可對(duì)它們中的任一 元素進(jìn)行操作。 F3 字符串是數(shù)據(jù)對(duì)象特定的線性表。T4.在單鏈表P指針?biāo)附Y(jié)點(diǎn)之后插入S結(jié)點(diǎn)的操作是：P->next= S ; S-> next = P->next; F5 一個(gè)無向圖的連通分量是其極大的連通子圖。T6 鄰接表可以表示有向圖，也可以表示

2、無向圖。T7. 假設(shè)B是一棵樹，B'是對(duì)應(yīng)的二叉樹。則 B的后 根遍歷相當(dāng)于 B'的中序遍歷。 T8. 通常，二叉樹的第i層上有2i-1個(gè)結(jié)點(diǎn)。F9. 對(duì)于一棵m階的B揺，樹中每個(gè)結(jié)點(diǎn)至多有 m個(gè)關(guān)鍵字。除根之外的所有非終端結(jié)點(diǎn)至少有em/2 0個(gè)關(guān)鍵字。 F 10 對(duì)于任何待排序序列來說，快速排序均快于起泡排序。 F二選擇題（每題 2 分共 28 分）1在下列排序方法中，（c ）方法平均時(shí)間復(fù)雜度為0（nlogn） ，最壞情況下時(shí)間復(fù)雜度為0（n2） ；（d ）方法所有情況下時(shí)間復(fù)雜度均為0(nlogn)。a.插入排序b. 希爾排序c. 快速排序d. 堆排序2.在有 n 個(gè)結(jié)

3、點(diǎn)的二叉樹的二叉鏈表表示中，空指針數(shù)為( b )。a. 不 定b.n+1c.nd.n-13. 下列二叉樹中， （ a ）可用于實(shí)現(xiàn)符號(hào)不等長高效編 碼。b.次優(yōu)查找樹c.二叉平衡樹（ a ）適用于查找有序單鏈表。b.二分查找c.分塊查找為避免查找過程中每一步都檢測整 個(gè)表是否查找完畢，可采用（ a ）方法。d.快速查找 6. 在下列數(shù)據(jù)結(jié)構(gòu)中， （ c ）具有先進(jìn)先出特性， （ b ） 具有先進(jìn)后出特性。a 線性表b .棧C.隊(duì)列d.廣義表7具有 m 個(gè)結(jié)點(diǎn)的二叉排序樹，其最大深度為（f ），最小深度為（ b ）。a. log 2 mb. L Iog2 m+1 c. m/2d .廠 m/2 n

4、 -1e.廠 m/2 nf. m8已知一組待排序的記錄關(guān)鍵字初始排列如下：56，34，58，26，79，52，64，37，28，84，57 。下列選擇中（ c ）是快速排序一趟排序的結(jié)果。（ b ）是希爾排序（初始步長為4）一趟排序的結(jié)果。（ d ）是基數(shù)排序一趟排序的結(jié)果。（ a ）是初始堆（大堆頂） 。a.84，79，64，37，57，52，58，26，28，34，56。b.28，34，57，26，56，52，58，37，79，84，64。c.28，34，37，26，52，56，64，79，58，84，57。d.52，34，64，84，56，26，37，57，58，28，79。e.34，5

5、6，26，58，52，64，37，28，79，57，84。f.34，56，26，58，52，79，37，64，28，84，57。三填空題（每題 2 分共 20 分）1 有向圖的存儲(chǔ)結(jié)構(gòu)有（鄰接矩陣）、（鄰接表） 、（十字鏈表）等方法。2 .已知某二叉樹的先序遍歷次序?yàn)閍fbcdeg，中序遍歷次序?yàn)?cedbgfa。其后序遍歷次序?yàn)椋╡dcgbfa ）。層次遍歷次序?yàn)椋?afbcgde）。3設(shè)有二維數(shù)組 A 5 x 7 ，每一元素用相鄰的 4 個(gè)字節(jié)存 儲(chǔ)，存儲(chǔ)器按字節(jié)編址。已知 A00 的存儲(chǔ)地址為 100。 則按行存儲(chǔ)時(shí)，元素A14的第一個(gè)字節(jié)的地址是 （144）; 按列存儲(chǔ)時(shí)，元素 A14

6、的第一個(gè)字節(jié)的地址是（184 ）。4請(qǐng)?jiān)谙聞澗€上填入適當(dāng)?shù)恼Z句，完成以下法算。Status Preordertraverse（Bitree T，Status（*Visit）（Telemtype e）/ 先序非遞歸遍歷二叉樹。Initstack （ S ）; Push （ S，T ）;While （ !stackempty（ S ） ） While （ gettop（ S， p ）&& p ） visit （p->data ） ; push（S， p->lchild ;Pop （ S ， p ）;If （ !stackempty（s） ） pop（S， p） ; pu

7、sh（ S， p->rchild ）; return ok;四簡答題（每題 5分共 25 分）1將圖示森林轉(zhuǎn)換為二叉樹，并對(duì)該二叉樹中序全序 線索化。2 .已知Hash函數(shù)為 H （ K） =K mod 13，散列地址為 0 -14，用二次探測再散列處理沖突， 給出關(guān)鍵字 （ 23， 34， 56，24， 75， 12， 49， 52， 36， 92， 06， 55）在散列地址的分布。else0 1 2 3 4 5 6 7 8 9 10 1112 13 143. 右 圖 為 一 棵 3 階 B 樹 。 （20，25）a. 畫 出 在 該 樹 上 插 入 元 素 15 后 的 B 樹 。

8、/ I b. 接著，再刪除元素 35，畫出刪除后的 B 樹。 （10,14） （21）（35）4. 已知某無向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖所示。a.請(qǐng)畫出該圖。b根據(jù)存儲(chǔ)結(jié)構(gòu)給出其深度優(yōu)先遍歷序列及廣度優(yōu)先遍 歷序列。C.畫出其深度優(yōu)先生成樹及廣度優(yōu)先生成樹。0 a24 /1 b234 /2 C014/3 d1/4 e012/ 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-

9、>data; pa=pa->next;pc->next=NULL;2. 二叉樹用二叉鏈表存儲(chǔ)表示。 typedef struct BiTNode TelemType data;Struct BiTNode *lchild, *rchild; BiTNode, *BiTree; 編寫一個(gè)復(fù)制一棵二叉樹的遞歸算法。BiTree CopyTree(BiTree T) if (!T ) return NULL;if (!(newT = (BiTNode*)malloc(sizeof(BiTNode) exit(Overflow);newT-> data = T-> dat

10、a;newT-> lchild = CopyTree(T-> lchild);newT-> rchild = CopyTree(T-> rchild); return newT;地址的分布。else5. 設(shè)在某通信系統(tǒng)中使用了八個(gè)字符， 它們出現(xiàn)的頻率分別為 0.08，0.05，0.1，0.12，0.26，0.18，0.14，0.07， 試構(gòu)造一棵赫夫曼樹，并給出赫夫曼編碼。五算法設(shè)計(jì)題（共 17 分）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) .)Merge(Linklist A, Linklist B, Linklist &C ) void Merge(Linklist A, Linklist B, Linklist &C) C=(Linklist)malloc(sizeof(LNode); pa=A->next; pb=B-&