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

1、期末樣卷參考答案一是非題（每題2分共20分）1.線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。F棧和隊(duì)列也是線性表。如果需要，可對(duì)它們中的任一元素進(jìn)行操作。F3字符串是數(shù)據(jù)對(duì)象特定的線性表。T在單鏈表P指針?biāo)附Y(jié)點(diǎn)之后插入S結(jié)點(diǎn)的操作是：P-next=S;S-next=P-next;F個(gè)無(wú)向圖的連通分量是其極大的連通子圖。T6鄰接表可以表示有向圖，也可以表示無(wú)向圖。T假設(shè)B是一棵樹，B是對(duì)應(yīng)的二叉樹。則B的后根遍歷相當(dāng)于B的中序遍歷。T通常，二叉樹的第i層上有2口個(gè)結(jié)點(diǎn)。F對(duì)于一棵m階的B-樹，樹中每個(gè)結(jié)點(diǎn)至多有m個(gè)關(guān)鍵字。除根之外的所有非終端結(jié)點(diǎn)至少有m/2=個(gè)關(guān)鍵字。F對(duì)于任何待排序序列來(lái)說(shuō)，快速

2、排序均快于起泡排序。F二.選擇題（每題2分共28分）在下列排序方法中，（）方法平均時(shí)間復(fù)雜度為，最壞情況下時(shí)間復(fù)在下列排序方法中，（）方法平均時(shí)間復(fù)雜度為，最壞情況下時(shí)間復(fù)雜度為0（n2）；（d）方法所有情況下時(shí)間復(fù)雜度均為0（nl插入排序希爾排序快速排序堆排序在有個(gè)結(jié)點(diǎn)的二叉樹的二叉鏈表表示中，不定a.b.n+1空指針數(shù)為（找）。下列二叉樹中，（a）可用于實(shí)現(xiàn)符號(hào)不等長(zhǎng)高效編碼。最優(yōu)二叉樹次優(yōu)查找樹二叉平快衡順樹二叉排序樹下列查找方法中，（a）適用于查找有序單鏈表。順序查找二分查找分塊查找快順哈希查找在順序表查找中，為避免查找過(guò)程中每一步都檢測(cè)整個(gè)表是否查找完畢，可采用（a）方法。設(shè)置監(jiān)視哨

3、鏈表存貯二分查找快速查找在下列數(shù)據(jù)結(jié)構(gòu)中，（快）具有先進(jìn)先出特性，（b）具有先進(jìn)后出特性。a線性表?xiàng)ｊ?duì)列廣義表具有m個(gè)結(jié)點(diǎn)的二叉排序樹，其最大深度為（f）,最小深度為（b）。a.log2mb.Llog2m+1c.m/2d.rm/2i-1e.rm/2if.m8.已知一組待排序的記錄關(guān)鍵字初始排列如下：56，34，58，26，79，52，64，37，28，84，57。下列選擇中（c）是快速排序一趟排序的結(jié)果。（b）是希爾排序（初始步長(zhǎng)為4）一趟排序的結(jié)果。（d）是基數(shù)排序一趟排序的結(jié)果。（a）是初始堆（大堆頂）。a)84，79，64，37，57，52，58，26，28，34，56。b)28，34，

4、57，26，56，52，58，37，79，84，64c)28，34，37，26，52，56，64，79，58，84，57d)52，34，64，84，56，26，37，57，58，28，79。e)34，56，26，58，52，64，37，28，79，57，84。f)34，56，26，58，52，79，37，64，28，84，57。三填空題(每題2分共20分)1對(duì)于有向圖的存儲(chǔ)結(jié)構(gòu)有(鄰接矩陣)、(鄰接表)、(十字鏈表)等方法。2已知某二叉樹的先序遍歷次序?yàn)?，中序遍歷次序?yàn)?。其后序遍歷次序?yàn)?edcgbfa)。層次遍歷次序?yàn)?afbcgde)。3設(shè)有二維數(shù)組每一元素用相鄰的個(gè)字節(jié)存儲(chǔ)，存儲(chǔ)器按字節(jié)

5、編址已知的起始地址為則按行存儲(chǔ)時(shí)，元素的第一個(gè)字節(jié)的地址是()按列存儲(chǔ)時(shí)，元素的第一個(gè)字節(jié)的地址是().請(qǐng)?jiān)谙聞澗€上填入適當(dāng)?shù)恼Z(yǔ)句，完成以下法算。StatusPreordertraverse(BitreeT,Status(*Visit)(Telemtypee)/先序非遞歸遍歷二叉樹。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);push(S,p-rchild);returnok;四結(jié)構(gòu)問

6、答題(每題6分共24分)1將圖示森林轉(zhuǎn)換為二叉樹，并對(duì)該二叉樹中序全序線索化。2.已知Hash函數(shù)為H(K)=Kmod13，散列地址為0-14，用二次探測(cè)再散列處理沖突，給出關(guān)鍵字(23，34，56，24，75，12，49,52，36，92，06，55)在散列地址的分布。012345678910111213143.右圖為一棵3階B樹。(20，25)畫出在該樹上插入元素15/|后的B_樹。(10，14)(21)(35)接著，再刪除元素35,畫出刪除后的B_樹。4已知某無(wú)向圖的鄰接表存儲(chǔ)結(jié)構(gòu)如圖所示。請(qǐng)畫出該圖。.根據(jù)存儲(chǔ)結(jié)構(gòu)給出其深度優(yōu)先遍歷序列及廣度優(yōu)先遍歷序列。.畫出其深度優(yōu)先生成樹及廣度優(yōu)

7、先生成樹。五算法設(shè)計(jì)題(共8分)1.單鏈表結(jié)點(diǎn)的類型定義如下：typedefstructLNodeintdata;structLNode*next;LNode,*Linklist;寫一算法，將帶頭結(jié)點(diǎn)的有序單鏈表A和B合并成一新的有序表C。(注:不破壞A和B的原有結(jié)構(gòu))Merge(LinklistA,LinklistB,Linklist&C)voidMerge(LinklistA,LinklistB,Linklist&C)C=(Linklist)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;elsepc-data=pb-data;pb=pb-ne