《數(shù)據(jù)結(jié)構(gòu)》試題（A卷）（考試時(shí)間：90分鐘）一、單項(xiàng)選擇題（本大題共15小題，每題2分，共30分）（每題只有一個(gè)選項(xiàng)是正確的,將答案填寫在括號(hào)內(nèi)，錯(cuò)選、多項(xiàng)選擇不得分）（）是構(gòu)成數(shù)據(jù)的基本單位，是一個(gè)數(shù)據(jù)整體中相對(duì)獨(dú)立的單元。A．?dāng)?shù)據(jù)B.數(shù)據(jù)元素C.數(shù)據(jù)對(duì)象D.數(shù)據(jù)結(jié)構(gòu)2.算法計(jì)算量的大小稱為算法的（

）。A.效率?????B.復(fù)雜度C.數(shù)據(jù)元素之間的關(guān)系????D.數(shù)據(jù)的儲(chǔ)存方法3.若某線性表最常用的操作是存取任一指定序號(hào)的元素和在最后進(jìn)行插入或刪除運(yùn)算，則采納以下（）方式最節(jié)儉時(shí)間

。A.鏈?zhǔn)絻?chǔ)存

B.

索引儲(chǔ)存

C.次序儲(chǔ)存

D.散列儲(chǔ)存4.下述哪一條是次序儲(chǔ)存結(jié)構(gòu)的長(zhǎng)處？（

）A.儲(chǔ)存密度大?B.插入運(yùn)算方便?C.刪除運(yùn)算方便?D.可方便地用于各樣邏輯結(jié)構(gòu)的儲(chǔ)存表示5.在一個(gè)單鏈表中，若刪除p所指結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)，則履行（>next=p->next->next>next=p->next=p->next;p->next=p->next->next=p->next->next

）。6.帶頭結(jié)點(diǎn)的單鏈表

head為空的判斷條件是（

）。==NULL>next==NULL>next==head

!==NULL7.非空的循環(huán)單鏈表

head的尾結(jié)點(diǎn)

(由

p所指向

)知足（

）。>head==NULL

==NULL

>next==head

==head8.下邊對(duì)于線性表的表達(dá)中，錯(cuò)誤的選項(xiàng)是哪一個(gè)？（）線性表采納次序儲(chǔ)存，一定占用一片連續(xù)的儲(chǔ)存單元。B.線性表采納次序儲(chǔ)存，便于進(jìn)行插入和刪除操作。C.線性表采納鏈?zhǔn)絻?chǔ)存，不用占用一片連續(xù)的儲(chǔ)存單元。D.線性表采納鏈?zhǔn)絻?chǔ)存，便于插入和刪除操作。9.行列操作的原則是（

）。A.后進(jìn)先出

B.先進(jìn)先出

C.只好進(jìn)行插入

D.只好進(jìn)行刪除10.棧中同意進(jìn)行插入和刪除的一端稱為（）。A.棧首B.棧尾C.棧頂D.棧底11．假定以數(shù)組A[n]寄存循環(huán)行列的元素，其首尾指針?lè)謩e為為（）。

front

和rear，則目前行列中的元素個(gè)數(shù)A．（rear-front+n）%nC.(front-rear+n)%n

B.rear-front+1D.(rear-front)%n12.最大容量為

n的循環(huán)行列，隊(duì)尾指針是

rear，隊(duì)首指針是

front，則隊(duì)空的判斷條件是（

）。A.（rear+1）%n==front==front

+1==front

D.(rear-1)%n==front13.將一個(gè)十進(jìn)制的數(shù)變換成二進(jìn)制的數(shù)，能夠使用以下一種稱為（A.圖B.樹(shù)C.廣義表D.棧14.把一棵樹(shù)變換為二叉樹(shù)后，這棵二叉樹(shù)的形態(tài)是（）。

）的數(shù)據(jù)結(jié)構(gòu)。A.有

2種

B.有3種

C.有

4種

D.獨(dú)一的15.一棵左右子樹(shù)均不空的二叉樹(shù)在先序線索化后，此中空鏈域的個(gè)數(shù)是（

）。A.3

B.2

C.0

D.不確立二、填空題（本大題共10個(gè)空，每空2分，合計(jì)20分）1．?dāng)?shù)據(jù)結(jié)構(gòu)是研究程序設(shè)計(jì)上當(dāng)算機(jī)操作的以及它們之間的關(guān)系和運(yùn)算的一門學(xué)科。2．在一個(gè)單鏈表中，已知指針q所指結(jié)點(diǎn)是指針p所指結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在q和p之間插入結(jié)點(diǎn)s，則應(yīng)履行兩條語(yǔ)句：______，。3．字符串采納結(jié)點(diǎn)大小為2的鏈表作為其儲(chǔ)存結(jié)構(gòu)，是指鏈表的每個(gè)鏈結(jié)點(diǎn)的域中只寄存了2個(gè)字符。4．廣義表（a,b,c,d）的表尾是。5．一棵深度為k的二叉樹(shù)，最多有個(gè)結(jié)點(diǎn)。6．已知有向圖G=（V，E），此中:V={v1,v2,v3,v4,v5,v6,v7},E={<v1,v2>,<v1,v3>,<v1,v4>,<v2,v5>,<v3,v5>,<v3,v6>,<v4,v6>,<v5,v7>,<v6,v7>},則G的拓?fù)湫蛄惺莀_____。7.有n個(gè)極點(diǎn)的連通圖起碼有條邊。8.圖的儲(chǔ)存常采納和兩種方法。三、判斷題（本大題共10小題，每題1分，共10分）（請(qǐng)?jiān)诿款}后邊的括號(hào)里寫出答案，假如正確，請(qǐng)寫“√”，假如錯(cuò)誤，請(qǐng)寫“×”）1.線性表采納鏈表儲(chǔ)存時(shí)，結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的儲(chǔ)存空間能夠是不連續(xù)的。（）2．線性表就是次序儲(chǔ)存的表。（）當(dāng)線性表的元素總數(shù)基本穩(wěn)固，且極少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時(shí)，應(yīng)采納次序儲(chǔ)存結(jié)構(gòu)。（）4．線性表的鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)所需要的儲(chǔ)存空間一般要多于次序儲(chǔ)存結(jié)構(gòu)。（）5.串的長(zhǎng)度是指串中所含不一樣字符的個(gè)數(shù)。（）6.對(duì)稀少矩陣進(jìn)行壓縮儲(chǔ)存的目的是節(jié)儉儲(chǔ)存空間。（）7.二叉樹(shù)是非線性數(shù)據(jù)結(jié)構(gòu)，因此它不可以采納次序儲(chǔ)存結(jié)構(gòu)儲(chǔ)存。（）8.隨意一棵二叉樹(shù)中起碼有一個(gè)結(jié)點(diǎn)的度為2。（）9.對(duì)線性表進(jìn)行二分查找時(shí)，要求線性一定以次序方式儲(chǔ)存，且結(jié)點(diǎn)按重點(diǎn)字有序排序。（）10.采納線性探測(cè)法解決矛盾問(wèn)題，所產(chǎn)生的一系列后繼散列地點(diǎn)一定大于等于原散列地點(diǎn)。（）四、應(yīng)用題（本小題共5小題，每題6分，共30分）1.簡(jiǎn)述以下算法的功能（假定棧和行列的元素種類均為int）(6分)voidfun1(Queue&Q){StackS;intx;Initstack(S);While(!QueueEmpty(Q)){DeQueue(Q,x);Push(S,x);}While(!StackEmpty(S)){Pop(S,x);EnQueue(Q,x);}}2.請(qǐng)將以下圖的一棵樹(shù)變換成一棵二叉樹(shù)。（6分）圖一棵樹(shù)3.給定葉結(jié)點(diǎn)(a,b,c,d,e,f,g)，權(quán)值分別為{23,12,15,7,17,2,8}，畫出對(duì)應(yīng)的哈夫曼樹(shù)，并寫出各葉結(jié)點(diǎn)的哈夫曼編碼。（6分）（6分）已知圖G的毗鄰表以下圖，則：從極點(diǎn)v1出發(fā)的深度優(yōu)先搜尋序列為_(kāi)______。從極點(diǎn)v1出發(fā)的廣度優(yōu)先搜尋序列為_(kāi)______。5.求結(jié)構(gòu)圖所示無(wú)向網(wǎng)的最小生成樹(shù)（6分）圖圖G的毗鄰表圖無(wú)向網(wǎng)五、算法設(shè)計(jì)題（本大題共1小題，每題10分，共10分）1.已知查找表的數(shù)據(jù)元素種類以下：TypedefstructRectype{intnum;charname[8];}Rectype;假定查找表中有n個(gè)記錄，而且是按num降序次序儲(chǔ)存TypedefRectypeSqlist[100];密要求：（1）寫出對(duì)給定值K進(jìn)行二分查找的算法和main函數(shù)。（2）二分查找算法的函數(shù)頭部為“intbinsearch(SqlistR,intn,intK)“（3）在main函數(shù)中成立該查找表、調(diào)用二分查找算法，并輸出查找結(jié)果。封線《數(shù)據(jù)結(jié)構(gòu)》試題（B卷）（考試時(shí)間：90分鐘）一、單項(xiàng)選擇題（本大題共15小題，每題2分，共30分）（每題只有一個(gè)選項(xiàng)是正確的,將答案填寫在括號(hào)內(nèi)，錯(cuò)選、多項(xiàng)選擇不得分）1．在數(shù)據(jù)結(jié)構(gòu)中，數(shù)據(jù)的（）結(jié)構(gòu)是獨(dú)立于計(jì)算機(jī)的。A.邏輯B.儲(chǔ)存C.散列D.索引2．以下程序段的時(shí)間復(fù)雜度為（）。for(i=0;i<n;i++)x=x-2;2n）??（n）C.O（1）D.O（n2）3.鏈?zhǔn)絻?chǔ)存結(jié)構(gòu)表示的線性表也稱為（）。A.鏈表B.次序表C.雙鏈表D.物理表4.不帶頭結(jié)點(diǎn)的單鏈表（頭指針為head）為空的判斷條件是（）。A．head==NULLB．head->next==headC．head->next==NULLD．head!=NULL5．線性表若采納次序結(jié)構(gòu)時(shí)，要求內(nèi)存中可用儲(chǔ)存單元的地點(diǎn)（）。A．必定是不連續(xù)的B．部分地點(diǎn)是連續(xù)的C．必定是連續(xù)的D．連續(xù)不連續(xù)都能夠6.對(duì)于單鏈表，在兩個(gè)結(jié)點(diǎn)之間插入一新結(jié)點(diǎn)需要改正的指針共（）個(gè)。7.若線性表中有n個(gè)元素，算法（）在單鏈表上實(shí)現(xiàn)要比在次序表上實(shí)現(xiàn)效率更高。A.刪除全部值為x的元素B.在最后一個(gè)元素的后邊插入一個(gè)新元素C.次序輸出前k個(gè)元素D.互換此中某兩個(gè)元素的值8.對(duì)于次序表，接見(jiàn)結(jié)點(diǎn)和增添、刪除結(jié)點(diǎn)的時(shí)間復(fù)雜度分別為（）。(n)O(n)B.O(1)O(n)C.O(n)O(1)D.O(1)O(1)9.行列的刪除操作是在（）進(jìn)行。A．隊(duì)首B．隊(duì)尾C．隊(duì)首前一單元D．隊(duì)尾后一單元10.以下對(duì)于棧的表達(dá)中，正確的選項(xiàng)是（）。A．棧底元素必定是最后入棧的元素B．棧操作依據(jù)先進(jìn)后出的原則C．棧頂元素必定是最初入棧的元素D．以上三種說(shuō)法都不對(duì)11.設(shè)棧S和行列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6挨次進(jìn)入棧S,一個(gè)元素出棧后即進(jìn)入Q，若6個(gè)元素出隊(duì)的序列是e2、e4、e3、e6、e5和e1，則棧S的容量起碼是（）個(gè)。B.412.假定為循環(huán)行列分派的向量空間為Q[20],若行列的長(zhǎng)度和隊(duì)頭指針值分別為13和17，則目前尾指針的值為_(kāi)_____。?13.銀行業(yè)務(wù)叫號(hào)系統(tǒng)采納了數(shù)據(jù)結(jié)構(gòu)。A．棧B．廣義表C．行列D．圖14.依據(jù)二叉樹(shù)的定義，擁有3個(gè)結(jié)點(diǎn)的不一樣形狀的二叉樹(shù)有______種。15.n個(gè)結(jié)點(diǎn)的線索二叉樹(shù)上含有的線索數(shù)為_(kāi)_____。+1二、填空題（本大題共10個(gè)空，每空2分，共20分）1．?dāng)?shù)據(jù)結(jié)構(gòu)包括三個(gè)方面的內(nèi)容，即數(shù)據(jù)的邏輯結(jié)構(gòu)

、數(shù)據(jù)的

結(jié)構(gòu)和對(duì)數(shù)據(jù)所施加的操作。2．已知指針的語(yǔ)句是

q值為

NULL

、指針，

p指向單鏈表

L中的某結(jié)點(diǎn)，則刪除后來(lái)繼結(jié)點(diǎn)（要求由指針，free(q)。

q指向）3．設(shè)廣義表

L=（a,( )）

,則

Head(L)=

。4．當(dāng)且僅當(dāng)兩個(gè)串的相等而且各個(gè)對(duì)應(yīng)地點(diǎn)上的字符都相等時(shí)，稱這兩個(gè)串相等。5.二叉樹(shù)的第4層結(jié)點(diǎn)數(shù)最多為個(gè)。6．除了利用求重點(diǎn)路徑的方法，還能夠利用7．圖的遍歷主要有和8.4

方法判斷出一個(gè)有向圖能否有環(huán)（回路）。兩種方法。三、判斷題（本大題共10小題，每題1分，共10分）（請(qǐng)?jiān)诿款}后邊的括號(hào)里寫出答案，假如正確，請(qǐng)寫“√”，假如錯(cuò)誤，請(qǐng)寫“×”）1.對(duì)于一個(gè)線性表，采納次序儲(chǔ)存方式進(jìn)行插入和刪除結(jié)點(diǎn)時(shí)效率太低，采納鏈?zhǔn)絻?chǔ)存方式更好。（）2.所謂靜態(tài)鏈表就是向來(lái)不發(fā)生變化的鏈表。（）3.在次序表中，最后一個(gè)元素有一個(gè)后繼。（）4.線性表就是鏈?zhǔn)絻?chǔ)存的表。（）5.串是一種特別的線性表，其特別性表此刻數(shù)據(jù)元素能夠是多個(gè)字符。（）6.對(duì)稀少矩陣進(jìn)行壓縮儲(chǔ)存的目的是便于輸入和輸出。（）7.隨意一棵二叉樹(shù)中的度能夠小于2。（）8.樹(shù)形結(jié)構(gòu)最適適用來(lái)表示元素之間擁有分支層次關(guān)系的數(shù)據(jù)。（）9.當(dāng)采納分塊查找時(shí)，數(shù)據(jù)的組織方式為：數(shù)據(jù)分紅若干塊，每塊內(nèi)數(shù)據(jù)一定有序。（）10.次序查找法合適于儲(chǔ)存結(jié)構(gòu)為次序儲(chǔ)存或鏈?zhǔn)絻?chǔ)存的線性表。（）四、應(yīng)用題（本小題共5小題，每題6分，共30分）下邊是對(duì)二叉樹(shù)進(jìn)行操作的算法，其功能為（6分）Voidunknown(BtreeBT){Btreep=BT,temp;If(p!=NULL){temp=p->lchild;p->lchild=p->rchild;p->rchid=temp;unknown(p->lchild);unknown(p->rchild);}2.請(qǐng)寫出以下圖二叉樹(shù)的先序遍歷序列、中序遍歷序列和后序遍歷序列。（6分）圖二叉樹(shù)3．已知以下圖的有向圖，請(qǐng)給出：（共6分）①每個(gè)極點(diǎn)的入度和出度；（2分）②毗鄰矩陣；（4分）圖有向圖4.要求用普里姆算法畫出以下圖無(wú)向網(wǎng)的最小生成樹(shù)，假定從a極點(diǎn)出發(fā)結(jié)構(gòu)最小生成樹(shù)，寫出各條邊加入生成樹(shù)的序次（用權(quán)值表示）。（6分）圖無(wú)向網(wǎng)5.以下算法的運(yùn)轉(zhuǎn)結(jié)果是（棧的元素種類為char）(6分)voidmain( ){stackS;charx=’a’,y=’b’;initstack(S);push(S,x);push(S,y);printf(“%c”,x);printf(“%c”,y);pop(S,x);pop(S,y);printf(“%c”,x);printf(“%c”,y);}五、算法設(shè)計(jì)題（本大題共1小題，每題10分，共10分）已知查找表的數(shù)據(jù)元素種類以下：TypedefstructRectype{intnum;charname[8];}Rectype;假定查找表中有n個(gè)記錄，而且是采納次序儲(chǔ)存TypedefRectypeSqlist[100];要求：（1）寫出對(duì)給定值K進(jìn)行以前端開(kāi)始次序查找的算法和main函數(shù)。（2）次序查找算法的函數(shù)頭部為“intsearch(SqlistR,intn,intK)“（3）在main函數(shù)中成立該查找表、調(diào)用次序查找算法，并輸出查找結(jié)果。《數(shù)據(jù)結(jié)構(gòu)》（A卷）試題標(biāo)準(zhǔn)答案及評(píng)分標(biāo)準(zhǔn)一、單項(xiàng)選擇題（本大題共15小題，每題2分，合計(jì)30分）二、填空題（本大題共10個(gè)空，每空2分，合計(jì)20分）1.對(duì)象>next=s,s->net=p3.數(shù)據(jù)4.（b,c,d）,v3,v4,v6,v2,v5,v78.毗鄰矩陣，毗鄰表（不分先后）三、判斷題（本大題共10小題，每題1分，合計(jì)10分）1.×2.×3.√4.√5.×6.√7.×8.×9.√10.×四、應(yīng)用題（本大題共5小題，每題6分，共30分）1．利用棧將行列中的元素逆置（6分）2.（6分）AB（6分）此中：哈夫曼樹(shù)（分）哈夫曼編碼（分）a:10b:110c:111d:0111e:00f:0110g:011EC4.（6分）此中深度優(yōu)先搜尋序列為v1,v2,v3,v6,v5,v4(3分)FD廣度優(yōu)先搜尋序列為v1,v2,v5,v4,v3,v6(3分)5.（6分）G五、算法設(shè)計(jì)題（10分）intbinsearch(SqlistR,intn,intK)（5分）[intlow=0,high=n-1,mid;while(low<=high){mid=(low+high)/2;if(R[mid].key==K)returnmid;elseif(R[mid].key>K)low=mid+1;return-1;}elsehigh=mid-1;}main( )(5分){SqlistR;intn,k,i;scanf(“%d”,&n);for(i=0;i<n;i++)/*按num升序輸入數(shù)據(jù)*/{scanf(“%d\n”,&R[i].num);

gets(R[i].name);

}scanf(“%d”,&k);i=binsearch(R,n,k);if(i==-1)printf(

“noffound!

”);

else

printf(“found!”);

}荊楚理工學(xué)院成人高等教育期末考試《數(shù)據(jù)結(jié)構(gòu)