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

1、精選優(yōu)質(zhì)文檔-傾情為你奉上數(shù)據(jù)結(jié)構(gòu)考試試卷 ( A )課程名稱: 數(shù)據(jù)結(jié)構(gòu)（C語言） 試卷滿分 100 分考試時(shí)間: 年 月 日 (第 周 星期 )題 號(hào)一二三四五六七八九十總分評(píng)卷得分評(píng)卷簽名復(fù)核得分復(fù)核簽名一、選擇題(每項(xiàng)選擇2分，共34分)1、在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的是（ D ）。A、存儲(chǔ)結(jié)構(gòu)B、物理結(jié)構(gòu)C、物理和存儲(chǔ)結(jié)構(gòu)D、邏輯結(jié)構(gòu)2、可以把數(shù)據(jù)的邏輯結(jié)構(gòu)劃分成（ D）。A、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)B、動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)C、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)D、線性結(jié)構(gòu)和非線性結(jié)構(gòu)3、一個(gè)向量第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是（ B ）。A、110B、108

2、C、100D、1204、棧結(jié)構(gòu)通常采用的兩種存儲(chǔ)結(jié)構(gòu)是（ A ）。A、順序存儲(chǔ)結(jié)構(gòu)和鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)；B、散列方式和索引方式；C、鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)和數(shù)組；D、線性存儲(chǔ)結(jié)構(gòu)和非線性存儲(chǔ)結(jié)構(gòu)。5、在下列鏈表中不能從當(dāng)前結(jié)點(diǎn)出發(fā)訪問到其余各結(jié)點(diǎn)的是（ A）。 A、單鏈表 B、單循環(huán)鏈表 C、雙向鏈表 D、雙向循環(huán)鏈表學(xué) 院： 專 業(yè)： 學(xué) 號(hào)： 姓 名： 裝 訂 線 6、在表長(zhǎng)為n的單鏈表中，算法時(shí)間復(fù)雜度為O(n)的操作是（ A ）。A、查找單鏈表中第i個(gè)結(jié)點(diǎn)。B、在當(dāng)前結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)。C、刪除表中第一個(gè)結(jié)點(diǎn)。D、刪除當(dāng)前結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)。 7、數(shù)組A中，每個(gè)數(shù)據(jù)元素的長(zhǎng)度為3個(gè)字節(jié)，行下標(biāo)從1到

3、8，列下標(biāo)從3到10，存放該數(shù)組至少需要的單元數(shù)是（ D ）。 A、80 B、100 C、240 D、270 8、稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即（ C ）。 A、二維數(shù)組和三維數(shù)組 B、三元組和散列 C、三元組和十字鏈表 D、散列和十字鏈表 9、廣義表（a,b,c,d）的表頭是（ A ）表尾是（ D）。 A、a B、b C、( a,b) D、(b,c,d) 10、已知二叉樹的后序序列為fgbedca，中序序列為fbgadec則該二叉樹的前序序列為（ B ），層次序列為（ C ）。 A、abcdefg B、abfgcde C、abcfgde D、fgedcba11、某二叉樹只有度為0和度為

4、2的結(jié)點(diǎn)，如果該二叉樹只有21個(gè)結(jié)點(diǎn)，則葉子結(jié)點(diǎn)數(shù)為（ C ）。 A、9 B、10 C、11 D、1212、一個(gè)有n個(gè)頂點(diǎn)的無向圖最多有（ C ）條邊。 A、n B、n(n-1) C、n(n-1)/2 D、2n13、對(duì)于一個(gè)具有n個(gè)頂點(diǎn)e條邊的無向圖，若采用鄰接矩陣表示，該矩陣大小是（ D ）。 A、e2 B、n+e C、n*e D、n2 14、如果要求一個(gè)線性表既能較快的查找，又能適應(yīng)動(dòng)態(tài)變化的要求，可以采用（ A ）方法。 A、分塊 B、順序 C、二分 D、散列專心-專注-專業(yè) 15、在以下排序算法中，關(guān)鍵字的比較次數(shù)與記錄的初始排列次序無關(guān)的是（ D ）。 A、希爾排序 B、起泡排序 C

5、、插入排序 D、選擇排序二、算法測(cè)試（共28分） 先按要求填空完成程序，再回答有關(guān)問題。1、 （31分）設(shè)h是帶表頭結(jié)點(diǎn)的單鏈表的頭指針，請(qǐng)?jiān)O(shè)計(jì)一個(gè)逆置這個(gè)單鏈表的程序。即原鏈表為(a1,a2,a3an)，逆置后變?yōu)? an,an-1a2,a1)。單鏈表結(jié)點(diǎn)結(jié)構(gòu)為：typedef struct nodeint data; _ struct node *link;_（2分）LNode;void invert(LNode *h) LNode *s,*p; p=h->link; h->link=_ NULL ；或者 0 ；（2分） while(p!=NULL) s=p; p=p->

6、link; _ s->link=h->link;_（2分） h->link=s;什么是表頭結(jié)點(diǎn)？（2分）如果該鏈表無表頭結(jié)點(diǎn)，則原程序該做怎樣的修改？（4分）2、 （13分）對(duì)以下函數(shù)填空，實(shí)現(xiàn)以帶頭結(jié)點(diǎn)的單鏈表h為存儲(chǔ)結(jié)構(gòu)的直接選擇排序。單鏈表的結(jié)點(diǎn)結(jié)構(gòu)定義為typedef struct nodeint key; struct node *next;JD;void zjxzpx(JD *h) JD *p,*q,*m;int x;p=h->next;while(p!=NULL) q=p->next; m=p; while(q!=NULL) if (m->ke

7、y>q->key) _;（2分） _;（2分） if (p!=m) x=p->key; p->key=m->key; m->key=x; _;（2分） 直接選擇排序?qū)儆赺(穩(wěn)定/不穩(wěn)定)排序。（2分） 該排序算法總的鍵值比較次數(shù)為_。（2分）并分析什么情況下有最小移動(dòng)記錄次數(shù)？什么情況下有最大移動(dòng)記錄次數(shù)？算法的平均時(shí)間復(fù)雜度為多少？（3分 ） 3、（6分）對(duì)以下函數(shù)填空實(shí)現(xiàn)求中序線索二叉樹中結(jié)點(diǎn)后繼的算法。中序線索樹中結(jié)點(diǎn)結(jié)構(gòu)定義為：typedef struct TbTree int data; struct TbTree *lchild,*rchild;

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

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

10、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答案及評(píng)分標(biāo)準(zhǔn)一、 選擇題（每項(xiàng)選擇2分，共34分，錯(cuò)選不給分）1、D2、D3、B4、A5、A6、A7、D8、C9、AD10、BC11、C12、C13、D14、A15、D二、算法測(cè)試題（共31分）1、struct

11、 node *link;(2分)NULL ；或者 0 ；(2分)s->link=h->link;（2分）什么是表頭結(jié)點(diǎn)？答：表頭結(jié)點(diǎn)是有時(shí)為了操作方便而在鏈表的第一結(jié)點(diǎn)之前添加的一個(gè)結(jié)點(diǎn)，該結(jié)點(diǎn)結(jié)構(gòu)與表中結(jié)點(diǎn)相同，但數(shù)據(jù)域不存放表中數(shù)據(jù)，或者閑置不用，或者存放特殊信息。表頭結(jié)點(diǎn)的鏈域存放指向鏈表中第一個(gè)結(jié)點(diǎn)的指針。（2分，回答對(duì)點(diǎn)給1分；點(diǎn)0.5分；點(diǎn)0.5分。）如果該鏈表無表頭結(jié)點(diǎn)該做怎樣的修改？修改如下：void invert(LNode *h) LNode *s,*p; p=h；(1分)h=NULL;（1分） while(p!=NULL) s=p; p=p->link;

12、 s->link=h;（1分） 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í)，有最小移動(dòng)次數(shù)0；（1分）當(dāng)待排序序列為“逆序”時(shí)，有最大移動(dòng)次數(shù)3(n-1)；（1分）算法的平均時(shí)間復(fù)雜度為O（n2）。（1分）3、p->rchild;（2分）q->LTag!=1;（2分） 1 （1分）；NULL；或者 0 ；三、應(yīng)用題：1、（4分，畫對(duì)根結(jié)點(diǎn)1分，左子樹正確1.5分，右子樹正確1.5分）后序序列為：DGJHEBKIFCA（2分）2、前序序列補(bǔ)充完整為：ABCDEFGH（1分）中序序列補(bǔ)充完整為：CBDEAGHF（1分）后序序列補(bǔ)充完整為：CEDBHGFA（1分）（3分，畫對(duì)根結(jié)點(diǎn)1分，左子樹正確1分，右子樹正確1分）（4分）畫對(duì)各結(jié)點(diǎn)線索指針得2分，標(biāo)志位正確得1分，表頭結(jié)點(diǎn)正確得3、（4分，畫對(duì)各樹根結(jié)點(diǎn)2分，畫對(duì)各子樹子女結(jié)點(diǎn)2分）該森林的先序序列為：ABCMNSDEFGHKIJ（2分）4、（1）（2分,如果畫的是無向圖