數(shù)據(jù)結(jié)構(gòu)c語言版試題

1、數(shù)據(jù)結(jié)構(gòu)考試試卷（A）課程名稱：數(shù)據(jù)結(jié)構(gòu)（C語言）試卷滿分100分考試時間：年月日（第周星期）題號一一三四五六七八九十總分評卷得分評卷簽名復(fù)核得分復(fù)核簽名一、選擇題（每項選擇2分，共34分）1、在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機(jī)無關(guān)的是（D）0A存儲2構(gòu)R物理2構(gòu)C、物理和存儲結(jié)構(gòu)D邏輯結(jié)構(gòu)2、可以把數(shù)據(jù)的邏輯結(jié)構(gòu)劃分成（D）。A、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)B、動態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)G緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)口線性結(jié)構(gòu)和非線性結(jié)構(gòu)3、一個向量第一個元素的存儲地址是100,每個元素的長度為2,則第5個元素的地址是（B）。A110B、108C、100D1204、棧結(jié)構(gòu)通常采用的兩種存儲結(jié)構(gòu)是（A）。A順序存儲結(jié)構(gòu)和鏈

2、式存儲結(jié)構(gòu)；R散列方式和索引方式；G鏈?zhǔn)酱鎯Y(jié)構(gòu)和數(shù)組；D線性存儲結(jié)構(gòu)和非線性存儲結(jié)構(gòu)。5、在下列鏈表中不能從當(dāng)前結(jié)點(diǎn)出發(fā)訪問到其余各結(jié)點(diǎn)的是（A）。A、單鏈表B、單循環(huán)鏈表C、雙向鏈表D、雙向循環(huán)鏈表6、在表長為n的單鏈表中，算法時間復(fù)雜度為O（n）的操作是（A）。A、查找單鏈表中第i個結(jié)點(diǎn)。B、在當(dāng)前結(jié)點(diǎn)之后插入一個結(jié)點(diǎn)。C、刪除表中第一個結(jié)點(diǎn)。D、刪除當(dāng)前結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)。7、數(shù)組A中，每個數(shù)據(jù)元素的長度為3個字節(jié)，行下標(biāo)從1到8,列下標(biāo)從3到10,存放該數(shù)組至少需要的單元數(shù)是（D）。A、80B、100C、240D、2708、稀疏矩陣一般的壓縮存儲方法有兩種，即（C）。A、二維數(shù)組和三

3、維數(shù)組B、三元組和散列C、三元組和十字鏈表D、散列和十字鏈表9、廣義表（a,b,c,d）的表頭是（A）表尾是（D）。A、aB、bC、（a,b）D、（b,c,d）10、已知二叉樹的后序序列為fgbedca,中序序列為fbgadec則該二叉樹的前序序列為（B）,層次序列為（C）。A、abcdefgB、abfgcdeC、abcfgdeD、fgedcba11、某二叉樹只有度為0和度為2的結(jié)點(diǎn)，如果該二叉樹只有21個結(jié)點(diǎn)，則葉子結(jié)點(diǎn)數(shù)為（C）。A、9B、10C、11D、1212、一個有n個頂點(diǎn)的無向圖最多有（C）條邊。A、nB、n（n-1）C、n（n-1）/2D、2n13、對于一個具有n個頂點(diǎn)e條邊的無

4、向圖，若采用鄰接矩陣表示，該矩陣大小是（D）。A、e2B、n+eC、n*eD、n214、如果要求一個線性表既能較快的查找，又能適應(yīng)動態(tài)變化的要求，可以采用（A）方法。A、分塊B、順序C、二分D、散列15、在以下排序算法中，關(guān)鍵字的比較次數(shù)與記錄的初始排列次序無關(guān)的是（D）。A、希爾排序B、起泡排序C、插入排序D、選擇排序二、算法測試（共28分）先按要求填空完成程序，再回答有關(guān)問題。1、（31分）設(shè)h是帶表頭結(jié)點(diǎn)的單鏈表的頭指針，請設(shè)計一個逆置這個單鏈表的程序。即原鏈表為忿肉而），逆置后變?yōu)椋╝n,an-1雙向）。單鏈表結(jié)點(diǎn)結(jié)構(gòu)為：typedefstructnodeintdata;:struct

5、node*link;（2分）LNode;voidinvert（LNode*h）LNode*s,*p;p=h->link;h->link=null；或者0；（2分）while（p!=NULL）s=p;p=p->link;s->link=h->link;_（2分）h->link=s;什么是表頭結(jié)點(diǎn)？（2分）如果該鏈表無表頭結(jié)點(diǎn)，則原程序該做怎樣的修改？（4分）2、（13分）對以下函數(shù)填空，實現(xiàn)以帶頭結(jié)點(diǎn)的單鏈表h為存儲結(jié)構(gòu)的直接選擇排序。單鏈表的結(jié)點(diǎn)結(jié)構(gòu)定義為typedefstructnodeintkey;structnode*next;JD;voidzjxzp

6、x（JD*h）JD*p,*q,*m;intx;p=h->next;while（p!=NULL）q=p->next;m=p;while（q!=NULL）if（m->key>q->key）;（2分）;（2分）if（p!=m）x=p->key;p->key=m->key;m->key=x;（2分）直接選擇排序?qū)儆谙穸?不穩(wěn)定）排序。（2分）該排序算法總的鍵值比較次數(shù)為o（2分）并分析什么情況下有最小移動記錄次數(shù)？什么情況下有最大移動記錄次數(shù)？算法的平均時間復(fù)雜度為多少？（3分）3、（6分）對以下函數(shù)填空實現(xiàn)求中序線索二叉樹中結(jié)點(diǎn)后繼的算法。中序線

7、索樹中結(jié)點(diǎn)結(jié)構(gòu)定義為：typedefstructTbTreeintdata;structTbTree*lchild,*rchild;intLTag,RTag;/左右標(biāo)志，0表示有子女，1表示線索指針TbTree;TbTree*succ（TbTree*p）/p為指向當(dāng)前結(jié)點(diǎn)的指針TbTree*q;if（p->RTag=1）return（）（2分）elseq=p->rchild;while（）q=q->left;（2分）return（q）;(1在中序線索二叉樹中，中序遍歷訪問的第一個結(jié)點(diǎn)左標(biāo)志位（LTag）為分），其lchild=o（1分）三、應(yīng)用題（共35分）1、（6分）已知二

8、叉樹的層次序列為ABCDEFGHIJK,中序序歹U為DBGEHJACIKF,請構(gòu)造一棵二叉樹，并寫出其后序序列。2、（10分）已知二叉樹的先序、中序和后序序列如下，其中有一些看不清的字母用*表示，請先補(bǔ)充*處的字母，再構(gòu)造一棵符合條件的二叉樹（畫出圖示），最后畫出帶頭結(jié)點(diǎn)的中序線索鏈表。前序序列：*BC*G*中序序列：CB*EAGH*后序序列：*EDB*FA3、（6分）將下列二叉樹還原成森林，并寫出先序遍歷森林序列。A8 （ECFGM1!D）（HN）（KIJ4、 （8分）已知圖G=（V,E）,其中V=a,b,c,d,e,E=<a,b>,<a,c>,<a,d>

9、,<b,c>,<d,c>,<b,e>,<c,e>,<d,e>要求：（1） 畫出圖G;（2分）（2） 給出圖G的鄰接矩陣；（2分）（3） 給出圖G的鄰接表；（2分）（4） 給出圖G的一種拓?fù)湫蛄小＃?分）5、（2分）判斷下列序列是否為大根堆，如果不是則把它們調(diào)整成大根堆。90,86,48,73,35,40,42,58,66,206、（3分）按下列輸入順序，建立相應(yīng)的二叉排序樹。（1） 4,5,6（2）5,4,6（3）6,5,4答案及評分標(biāo)準(zhǔn)、選擇題（每項選擇2分，共34分，錯選不給分）1、D2、D3、B4、A5、A6、A7、D8、C9、

10、AD10、BC11、C12、C13、D14、A15、D、算法測試題（共31分）1、structnode*link;（2分）NULL;或者0;（2分）s->link=h->link;（2分）什么是表頭結(jié)點(diǎn)？答：表頭結(jié)點(diǎn)是有時為了操作方便而在鏈表的第一結(jié)點(diǎn)之前添加的一個結(jié)點(diǎn)，該結(jié)點(diǎn)結(jié)構(gòu)與表中結(jié)點(diǎn)相加但數(shù)據(jù)域不存放表中數(shù)據(jù),一或者閑置不用，或者存放特殊信息。表頭結(jié)點(diǎn)的鏈域存放指向鏈表中第一個結(jié)點(diǎn)的指而（2分，回答對點(diǎn)給1分；點(diǎn)0.5分；點(diǎn)0.5分。）如果該鏈表無表頭結(jié)點(diǎn)該做怎樣的修改？修改如下：voidinvert（LNode*h）LNode*s,*p;p=h;（1分）h=NULL;（1

11、分）while（p!=NULL）s=p;p=p->link;s->link=h;11分）h=s;（1分）2、m=q;（2分）q=q->link;（2分）p=p->link;（2分）不穩(wěn)定（2分）n（n-1）/2（2分）當(dāng)待排序序列為“正序”時，有最小移動次數(shù)0；（1分）當(dāng)待排序序列為“逆序”時，有最大移動次數(shù)3（n-1）;（1分）算法的平均時間復(fù)雜度為O（n2）。（1分）3、p->rchild;（2分）q->ITag!=1;（2分）1 （1分）；NULL;或者0;三、應(yīng)用更1、 （4分，畫對根結(jié)點(diǎn)1分，左子樹正確1.5分，右子樹正確1.5分）DGJHEBKIFCA（2分）2、前序序列補(bǔ)充完整為：ABCDEFGH（1分）中序序列補(bǔ)充完整為：CBDEAGHF（1分）后序序列補(bǔ)充完整為：CEDBHGFA（1分）（3分，畫對根結(jié)點(diǎn)1分，左子樹正確1分，右子樹正確1分）（4分）畫對各結(jié)點(diǎn)線索指針得2分，標(biāo)志位正確得1分，表頭結(jié)點(diǎn)正確得3、（4分，畫對各樹根結(jié)點(diǎn)2分，畫對各子樹子女結(jié)點(diǎn)2分）4、（1）該森林的先序序列為:ABCMNSDEFGHK