軟件學(xué)生會(huì)學(xué)習(xí)部試卷-數(shù)據(jù)結(jié)構(gòu)期末習(xí)題選講

習(xí)題選講數(shù)據(jù)結(jié)構(gòu)與算法分析1一．單項(xiàng)選擇題1、下面程序段的時(shí)間復(fù)雜度為（）A.O(n)B.O(n^2)C.O(n(n-1)/2)D.O(logn)voidfun1(intn){x=0;for(i=0;i<n;i++)

for(j=i+1;j<n;j++)

x++;}b22、若某線性表最常用的操作是刪除最后一個(gè)結(jié)點(diǎn)，則采用存儲(chǔ)結(jié)構(gòu)算法的時(shí)間效率最高的是（）

a.單鏈表

b.給出表尾指針的單循環(huán)鏈表

c.雙向鏈表

d.給出表尾指針雙向循環(huán)鏈表d33、在單鏈表指針為p的結(jié)點(diǎn)之后插入指針為s的結(jié)點(diǎn)，正確的操作是（

）A．p->next=s;s->next=p->next;B．s->next=p->next;p->next=s;C．p->next=s;p->next=s->next;D．s->next=p;p->next=s;b44、若一個(gè)棧以向量S[1..n]存儲(chǔ)，初始棧頂指針top為n+1，則下面x進(jìn)棧的正確操作是（

）A．top+=1;S[top]=x;B．S[top]=x;top+=1;C．top-=1;S[top]=x;D．S[top]=x;top--;c55、下列說(shuō)法正確的是（

）(1)稀疏矩陣壓縮存儲(chǔ)后，必會(huì)失去隨機(jī)存取功能。(2)若一個(gè)廣義表的表頭為空表，則此廣義表亦為空表。(3)廣義表的取表尾運(yùn)算，其結(jié)果通常是個(gè)表，但有時(shí)也可是個(gè)單元素值。(4)從邏輯結(jié)構(gòu)上看，n維數(shù)組是由多個(gè)n-1維的數(shù)組構(gòu)成。A．僅(1)(2) B．僅(1)(4)C．僅(2)(3) D．僅(3)(4)b66、下列說(shuō)法錯(cuò)誤的是（）在圖G的最小生成樹(shù)G1中，可能會(huì)有某條邊的權(quán)值超過(guò)未選邊的權(quán)值。不同求最小生成樹(shù)的方法得到的生成樹(shù)是相同的.當(dāng)改變網(wǎng)上某一關(guān)鍵路徑上任一關(guān)鍵活動(dòng)后，必將產(chǎn)生不同的關(guān)鍵路徑網(wǎng)絡(luò)的最小生成樹(shù)是唯一的A12B23C234D14c77、有n個(gè)葉子的哈夫曼樹(shù)中分支節(jié)點(diǎn)總數(shù)為（

）。A．n-1B．2n+1C．n+1D．不確定n+n2=2n2+1n=n2+1n2=n-1a88、已知一算術(shù)表達(dá)式的中綴形式為：A+B*C-D/E，后綴形式為：ABC*+DE/-，則其前綴形式為（）A．-A+B*C/DE B．-A+B*CD/E C．-+*ABC/DE D．-+A*BC/DEd99、設(shè)森林F中有三棵樹(shù)，第1、第2和第3棵樹(shù)的結(jié)點(diǎn)個(gè)數(shù)分別為M1、M2和M3（M1，M2，M3皆大于0）。與森林F對(duì)應(yīng)的二叉樹(shù)根結(jié)點(diǎn)的右子樹(shù)上的結(jié)點(diǎn)個(gè)數(shù)是（

）A．M1 B．M1+M2 C．M3 D．M2+M3d1010、已知有向圖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ù)湫蛄惺牵ǎ〢．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V7a1111、下面關(guān)于折半查找的敘述中，正確的是（）A．表必須有序，表可以順序方式存儲(chǔ)，也可以鏈表方式存儲(chǔ)B．表必須有序且表中數(shù)據(jù)必須是整型，實(shí)型或字符型C．表必須有序，而且只能從小到大排列D．表必須有序，且表只能以順序方式存儲(chǔ)d1212、設(shè)二叉排序樹(shù)中關(guān)鍵字由1到1000的整數(shù)組成，現(xiàn)要查找關(guān)鍵字為363的結(jié)點(diǎn)，下述關(guān)鍵字序列中不可能是在二叉排序樹(shù)中查到的序列（）1）51，250，501，382，320，340，390，3632）24，877，125，342，421，623，501，3633）345，829，765，542，412，395，341，3634）965，741，259，478，275，249，360，363A）僅1）2）B）僅1）2）3）C）僅1）4）D）僅2）a1313、對(duì)序列{15,9,7,8,20,-1,4}用希爾排序方法排序，經(jīng)一趟后序列變?yōu)閧15,-1,4,8,20,9,7}，則該次采用的增量是（

）A．1 B．2 C．3 D．4d1414、下列說(shuō)法中，錯(cuò)誤的是（

）(1)外部排序是把外存文件調(diào)入內(nèi)存，可利用內(nèi)部排序的方法進(jìn)行排序，因此排序所花的時(shí)間取決于內(nèi)部排序的時(shí)間(2)在外部排序時(shí)，利用敗者樹(shù)方法選擇當(dāng)前最小關(guān)鍵字過(guò)程的復(fù)雜度取決于歸并的路數(shù)。(3)影響外排序的時(shí)間因素主要是內(nèi)存與外設(shè)交換信息的總次數(shù)。A．僅(1) B．僅(1)(2) C．僅(2)(3) D．(1)(2)(3)a1515、有n個(gè)葉子的哈夫曼樹(shù)的結(jié)點(diǎn)總數(shù)為（

）。A．不確定B．2nC．2n+1D．2n-1d16填空題1、用S表示入棧操作，X表示出棧操作，若元素入棧的順序?yàn)?234，為了得到1342出棧順序，相應(yīng)的S和X的操作串為（

）。2、若用一個(gè)大小為6的數(shù)組來(lái)實(shí)現(xiàn)循環(huán)隊(duì)列，且當(dāng)前rear和front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為（

）。S×SS×S××2和4173、廣義表A=(a,b,((c,d),(e,(f,g))))，則Head(Tail(Head(Tail(Tail(A)))))的值為（

）。4、在一棵高度為4的完全3叉樹(shù)中，結(jié)點(diǎn)總數(shù)在（

）之間。5、假設(shè)一個(gè)森林由4個(gè)節(jié)點(diǎn)構(gòu)成，則森林可能的形態(tài)有（

）種（假設(shè)森林中的樹(shù)不計(jì)順序，樹(shù)中的各個(gè)子樹(shù)也不計(jì)順序）。14--4081819森林無(wú)向圖6、無(wú)向圖G(V,E)，其中V(G)={1,2,3,4,5,6,7}，E(G)={(1,2)，(1,3)，(2,4)，(2,5)，(3,6)，(3,7)，(6,7)，(5,1)}，對(duì)該圖從頂點(diǎn)3開(kāi)始進(jìn)行遍歷，去掉遍歷中未走過(guò)的邊，得到生成樹(shù)G’(V,E)，V(G’)=V(G)，E(G’)={(1,3)，(3,6)，(7,3)，(1,2)，(1,5)，(2,4)}，則采用的遍歷方法是（

）。寬度優(yōu)先遍歷207、有向圖G=(V,E)，其中V(G)={0,1,2,3,4,5}，用三元組<a,b,d>表示弧<a,b>及弧上的權(quán)d。E(G)為{<0,5,100>,<0,2,10>,<1,2,5>,<0,4,30>,<4,5,60>,<3,5,10>,<2,3,50>,<4,3,20>}，則從源點(diǎn)0到頂點(diǎn)3的最短路徑長(zhǎng)度是（

）。50218、散列表的地址區(qū)間為0～17，散列函數(shù)為H(K)=Kmod17。采用線性探測(cè)法處理沖突，并將關(guān)鍵字序列：26，25，72，38，8，18，59依次存儲(chǔ)到散列表中。元素59存放在散列表中的地址是（

）。9、向一個(gè)長(zhǎng)度為n的向量的第i個(gè)元素(1≤i≤n+1)之前插入一個(gè)元素時(shí)，需向后移動(dòng)

（）個(gè)元素。10、設(shè)有關(guān)鍵碼序列（Q，H，C，Y，Q，A，M，S，R，D，F(xiàn)，X），要按照關(guān)鍵碼值遞增的次序進(jìn)行排序。若采用初始步長(zhǎng)為7的Shell排序法，則一趟掃描的結(jié)果是（

）。11n-i+122三、問(wèn)答題1、設(shè)有nn對(duì)稱(chēng)矩陣A，aij=aji如圖所示。為了節(jié)約存儲(chǔ)，只存對(duì)角線及對(duì)角線以上的元素。將上三角矩陣中的元素按列存放到一個(gè)一維數(shù)組B中。問(wèn)：(1)存放對(duì)稱(chēng)矩陣A上三角部分的一維數(shù)組B要有多少個(gè)元素？(2)若在一維數(shù)組B中從0號(hào)位置開(kāi)始存放，則矩陣A中的任一元素aij在只存上三角部分的情形下，應(yīng)存于一維數(shù)組的什么下標(biāo)位置？給出計(jì)算公式。232、假設(shè)關(guān)鍵字集合為（30，15，10，40，35，43，25，28），所有關(guān)鍵字順序輸入。要求：構(gòu)造一棵平衡二叉樹(shù)排序樹(shù)T（給出每插入一個(gè)節(jié)點(diǎn)后平衡二叉樹(shù)的狀態(tài)）。243、設(shè)有12個(gè)初始?xì)w并段，其長(zhǎng)度分別為8,6,30,35,62,18,84,68,11,60,3,20；試畫(huà)出表示歸并過(guò)程的最佳4路歸并樹(shù)，并計(jì)算樹(shù)的WPL。254、已知一棵二叉樹(shù)的先序遍歷序列是B,A,C,D,G,F,E和整數(shù)序列3,2,0,1,3,0,0。其中整數(shù)序列中的第i個(gè)數(shù)表示先序序列第i個(gè)結(jié)點(diǎn)的狀態(tài)，含義如下：0——本結(jié)點(diǎn)為葉結(jié)點(diǎn)1——本結(jié)點(diǎn)只有左孩子2——本結(jié)點(diǎn)只有右孩子3——本結(jié)點(diǎn)有兩個(gè)孩子（1）請(qǐng)畫(huà)出該二叉樹(shù)；（2）請(qǐng)說(shuō)明，這樣的方式能否唯一地表示一棵二叉樹(shù)。若“能”，請(qǐng)用數(shù)學(xué)歸納法給出證明；若“不能”，請(qǐng)找出反例。26歸納法（構(gòu)造性證明）假設(shè)樹(shù)的節(jié)點(diǎn)數(shù)為n（n>=0）當(dāng)n=0時(shí)，空樹(shù)當(dāng)n=1時(shí)，只有根節(jié)點(diǎn)的樹(shù)歸納假設(shè):當(dāng)結(jié)點(diǎn)數(shù)小于k（k>1）時(shí)，結(jié)論正確。有先序列可以確定樹(shù)的根。如果根只有一個(gè)兒子（其狀態(tài)是1或2，不可能是0）其余結(jié)點(diǎn)全在根左子樹(shù)（或右子樹(shù)）上。由歸納假設(shè)，剩余部分（結(jié)點(diǎn)數(shù)小于k）可以唯一確定根的左（或右）子樹(shù)。如果根由兩個(gè)兒子（狀態(tài)為3），那么在先序序列中，根的右側(cè)結(jié)點(diǎn)必為根的左孩子，并可根據(jù)左孩子的狀態(tài)畫(huà)出左子樹(shù)；類(lèi)似，剩余結(jié)點(diǎn)就是根的右子樹(shù)。27四、算法題1、對(duì)單鏈表中元素按插入方法排序的C語(yǔ)言描述算法如下，其中L為鏈表頭結(jié)點(diǎn)指針。請(qǐng)?zhí)畛渌惴ㄖ袠?biāo)出的空白處，完成其功能。typedefstructnode{ intdata; structnode*next;}linknode,*link;28voidInsertSort(linkL){linkp,q,r,u; p=L->next; L->next=NULL; while((1)) { r=L; q=L->next; while((2)&&q->data<=p->data) {r=q;q=q->next; } u=p->next;

(3);

(4); p=u; }}typedefstructnode{ intdata; structnode*next;}linknode,*link;(1)p!=NULL∥當(dāng)鏈表尚未到尾(2)q!=NULL∥查p結(jié)點(diǎn)在鏈表中的插入位置(3)p->next=r->next∥將p結(jié)點(diǎn)鏈入鏈表中(4)r->next=p∥r是q的前驅(qū)，u是下個(gè)待插入結(jié)點(diǎn)的指針。292、請(qǐng)寫(xiě)出判斷一棵二叉樹(shù)是否為平衡二叉樹(shù)的算法（假設(shè)不要求該二叉樹(shù)是排序二叉樹(shù)）。已知二叉樹(shù)采用二叉鏈表表示，其數(shù)據(jù)定義如下：typedefstructBiTNode{intdata;//關(guān)鍵字//左右孩子指針structBiTNode*lchild,*rchild;}BiTNode,*BiTree;30intIsBalanced(BiTreeT)//檢查二叉樹(shù)T是否是平衡樹(shù)。{//如果不平衡則返回-1，否則返回樹(shù)的深度。 if(!T)return0; depthLeft=IsBalanced(T->lchild); if(depthLeft==-1)return-1;depthRight=IsBalanced(T->rchild);if(depthRight==-1)return-1; if(depthLeft–depthRight>1|| depthRight–depthLeft>1)return-1;return1+(depthLeft>depthRight? depthLeft:depthRight);}313、計(jì)數(shù)排序算法對(duì)一個(gè)待排序的表（用數(shù)組表示）進(jìn)行排序，并將排序結(jié)果存放到另一個(gè)新的表中。假設(shè)，表中所有待排序的關(guān)鍵字互不相同，計(jì)數(shù)排序算法針對(duì)表中的每個(gè)記錄，掃描待排序的表一趟，統(tǒng)計(jì)表中有多少個(gè)記錄的關(guān)鍵字比該記錄的關(guān)鍵字小，假設(shè)針對(duì)某一個(gè)記錄，統(tǒng)計(jì)出的計(jì)數(shù)值為c，那么，這個(gè)記錄在新的有序表中的合適的存放位置即為c。(1)給出適用于計(jì)數(shù)排序的數(shù)據(jù)表定義；(2)使用C語(yǔ)言編寫(xiě)實(shí)現(xiàn)計(jì)數(shù)排序的算法；(3)對(duì)于有n個(gè)記錄的表，關(guān)鍵碼比較次數(shù)是多少？(4)該算法的空間復(fù)雜度是多少？32voidCountSort(RecTypea[],b[],intn)//計(jì)數(shù)排序算法，將a中記錄排序放入b中{for(i=0;i<n;i++)//對(duì)每一個(gè)元素a[i]

{ cnt=0; for(j=0;j<n;j++)//統(tǒng)計(jì)關(guān)鍵字比a[i]小的元素個(gè)數(shù) if(a[j].key<a[i].key)cnt++; b[cnt]=a[i];}}//Count_Sorttypedefstruct{ intkey; datatypeinfo}RecType33其它題目1、鏈表不具備的特點(diǎn)是()。A．插入和刪除不需要移動(dòng)元素

B．可隨機(jī)訪問(wèn)任一結(jié)點(diǎn)C．不必預(yù)分配空間

D．所需空間與其長(zhǎng)度成正比B342、下面程序段的時(shí)間復(fù)雜度為（

）voidfun1(intn){i=1;while(i<=n) i=i*3;}35log3n3、下面程序段的時(shí)間復(fù)雜度為（）A.O(n)B.O(n^2)C.O(n(n-1)/2)D.O(√n)voidfun1(intn){s=0;i=0;while(s<n){

i++;

s=s+i;}}D364、不帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是()。A．head＝＝NULLB．Head->next＝＝NULLC．Head->next＝＝headD．head!＝NULL另：帶頭結(jié)點(diǎn)的單鏈表head為空的判定條件是()。AB375、帶頭結(jié)點(diǎn)的循環(huán)單鏈表head中，head為空的判定條件是()。A．head＝＝NULLB．head—>next＝＝NULLC．head—>next＝＝headD．head!＝NULLC386、在長(zhǎng)度為n的()上，刪除第一個(gè)元素，其算法復(fù)雜度為O(n)。A．只有表頭指針的不帶頭結(jié)點(diǎn)的循環(huán)單鏈表B．只有表尾指針的不帶頭結(jié)點(diǎn)的循環(huán)單鏈表C．只有表尾指針的帶頭結(jié)點(diǎn)的循環(huán)單鏈表D．只有表尾指針的帶頭結(jié)點(diǎn)的循環(huán)雙鏈表A397、若線性表中有2n個(gè)元素，算法()在單鏈表上實(shí)現(xiàn)要比在順序表上實(shí)現(xiàn)效率更高。A．刪除所有值為x的元素

B．在最后一個(gè)元素的后面插入一個(gè)新元素C．順序輸出前k個(gè)元素

D．交換其中某兩個(gè)元素的值A(chǔ)409、文件局部有序或文件長(zhǎng)度較小時(shí)，最佳排序方法是（）。A.直接插入排序B.冒泡排序C.簡(jiǎn)單選擇排序D.歸并排序A411.算法的優(yōu)劣與算法描述語(yǔ)言無(wú)關(guān)，但與所用計(jì)算機(jī)有關(guān)。（）2.算法可以用不同的語(yǔ)言描述，如果用C語(yǔ)言或PASCAL語(yǔ)言等高級(jí)語(yǔ)言來(lái)描述，那么算法實(shí)際上就是程序。（）

3.棧和隊(duì)列的存儲(chǔ)方式，既可以是順序方式，又可以是鏈?zhǔn)椒绞?。（?.帶頭結(jié)點(diǎn)的鏈隊(duì)出隊(duì)時(shí)不會(huì)改變頭指針的值，但可能改變尾指針。（）5.一顆樹(shù)中的葉子結(jié)點(diǎn)數(shù)一定等于其對(duì)應(yīng)的二叉樹(shù)的葉子數(shù)。（）FFTTF426.線性表用鏈表存儲(chǔ)時(shí)，結(jié)點(diǎn)間存儲(chǔ)空間可不連續(xù)的。（）7.哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的樹(shù)，路徑上權(quán)值較大的結(jié)點(diǎn)離根較近。（）8.完全二叉樹(shù)中，若一個(gè)結(jié)點(diǎn)沒(méi)有左子樹(shù)，則必是葉子結(jié)點(diǎn)。（）9.當(dāng)待排記錄按關(guān)鍵字從大到小或從小到大基本有序時(shí)，快速排序的執(zhí)行時(shí)間最省。（）10.排序的穩(wěn)定性是指排序算法中的比較次數(shù)保持不變，且算法能夠終止。（）TTTFF4311.在順序表上實(shí)現(xiàn)分塊查找，在等概率查找情況下，其平均查找長(zhǎng)度不僅與表的元素個(gè)數(shù)有關(guān)，而且與每一塊中的元素個(gè)數(shù)有關(guān)。（）12.內(nèi)部排序就是整個(gè)排序過(guò)程完全在內(nèi)存中進(jìn)行的排序。（）13.存在這樣的二叉樹(shù)，對(duì)它采用任何次序的遍歷，結(jié)果相同。（）14.有一個(gè)小堆，堆中任意結(jié)點(diǎn)的關(guān)鍵字均小于它的左、右孩子關(guān)鍵字。則其中具有最大值的結(jié)點(diǎn)一定是一個(gè)葉子結(jié)點(diǎn)，并可能在堆的最后兩層中。（）15.散列表的查找效率主要取決于所選擇的散列函數(shù)與處理沖突的方法。（）TTTTT4416.順序存儲(chǔ)結(jié)構(gòu)的主要缺點(diǎn)是不利于插入或刪除操作。（）17.線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。（）18.對(duì)查找進(jìn)行時(shí)間分析時(shí)，只需要考慮查找成功的平均情況。（）19.堆是一顆完全二叉樹(shù)，反之亦然。（）

20.給定一棵樹(shù)，可以找到唯一的一顆二叉樹(shù)與之對(duì)應(yīng)。（）TFFFT