軟件學生會學習部試卷-數(shù)據(jù)結構期末習題選講

習題選講數(shù)據(jù)結構與算法分析1一．單項選擇題1、下面程序段的時間復雜度為（）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、若某線性表最常用的操作是刪除最后一個結點，則采用存儲結構算法的時間效率最高的是（）

a.單鏈表

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

c.雙向鏈表

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

）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、若一個棧以向量S[1..n]存儲，初始棧頂指針top為n+1，則下面x進棧的正確操作是（

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

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

）。A．n-1B．2n+1C．n+1D．不確定n+n2=2n2+1n=n2+1n2=n-1a88、已知一算術表達式的中綴形式為：A+B*C-D/E，后綴形式為：ABC*+DE/-，則其前綴形式為（）A．-A+B*C/DE B．-A+B*CD/E C．-+*ABC/DE D．-+A*BC/DEd99、設森林F中有三棵樹，第1、第2和第3棵樹的結點個數(shù)分別為M1、M2和M3（M1，M2，M3皆大于0）。與森林F對應的二叉樹根結點的右子樹上的結點個數(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的拓撲序列是（）A．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、下面關于折半查找的敘述中，正確的是（）A．表必須有序，表可以順序方式存儲，也可以鏈表方式存儲B．表必須有序且表中數(shù)據(jù)必須是整型，實型或字符型C．表必須有序，而且只能從小到大排列D．表必須有序，且表只能以順序方式存儲d1212、設二叉排序樹中關鍵字由1到1000的整數(shù)組成，現(xiàn)要查找關鍵字為363的結點，下述關鍵字序列中不可能是在二叉排序樹中查到的序列（）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、對序列{15,9,7,8,20,-1,4}用希爾排序方法排序，經一趟后序列變?yōu)閧15,-1,4,8,20,9,7}，則該次采用的增量是（

）A．1 B．2 C．3 D．4d1414、下列說法中，錯誤的是（

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

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

）。2、若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當前rear和front的值分別為0和3，當從隊列中刪除一個元素，再加入兩個元素后，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ù)在（

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

）種（假設森林中的樹不計順序，樹中的各個子樹也不計順序）。14--4081819森林無向圖6、無向圖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)}，對該圖從頂點3開始進行遍歷，去掉遍歷中未走過的邊，得到生成樹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>及弧上的權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>}，則從源點0到頂點3的最短路徑長度是（

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

）。9、向一個長度為n的向量的第i個元素(1≤i≤n+1)之前插入一個元素時，需向后移動

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

）。11n-i+122三、問答題1、設有nn對稱矩陣A，aij=aji如圖所示。為了節(jié)約存儲，只存對角線及對角線以上的元素。將上三角矩陣中的元素按列存放到一個一維數(shù)組B中。問：(1)存放對稱矩陣A上三角部分的一維數(shù)組B要有多少個元素？(2)若在一維數(shù)組B中從0號位置開始存放，則矩陣A中的任一元素aij在只存上三角部分的情形下，應存于一維數(shù)組的什么下標位置？給出計算公式。232、假設關鍵字集合為（30，15，10，40，35，43，25，28），所有關鍵字順序輸入。要求：構造一棵平衡二叉樹排序樹T（給出每插入一個節(jié)點后平衡二叉樹的狀態(tài)）。243、設有12個初始歸并段，其長度分別為8,6,30,35,62,18,84,68,11,60,3,20；試畫出表示歸并過程的最佳4路歸并樹，并計算樹的WPL。254、已知一棵二叉樹的先序遍歷序列是B,A,C,D,G,F,E和整數(shù)序列3,2,0,1,3,0,0。其中整數(shù)序列中的第i個數(shù)表示先序序列第i個結點的狀態(tài)，含義如下：0——本結點為葉結點1——本結點只有左孩子2——本結點只有右孩子3——本結點有兩個孩子（1）請畫出該二叉樹；（2）請說明，這樣的方式能否唯一地表示一棵二叉樹。若“能”，請用數(shù)學歸納法給出證明；若“不能”，請找出反例。26歸納法（構造性證明）假設樹的節(jié)點數(shù)為n（n>=0）當n=0時，空樹當n=1時，只有根節(jié)點的樹歸納假設:當結點數(shù)小于k（k>1）時，結論正確。有先序列可以確定樹的根。如果根只有一個兒子（其狀態(tài)是1或2，不可能是0）其余結點全在根左子樹（或右子樹）上。由歸納假設，剩余部分（結點數(shù)小于k）可以唯一確定根的左（或右）子樹。如果根由兩個兒子（狀態(tài)為3），那么在先序序列中，根的右側結點必為根的左孩子，并可根據(jù)左孩子的狀態(tài)畫出左子樹；類似，剩余結點就是根的右子樹。27四、算法題1、對單鏈表中元素按插入方法排序的C語言描述算法如下，其中L為鏈表頭結點指針。請?zhí)畛渌惴ㄖ袠顺龅目瞻滋帲瓿善涔δ堋ypedefstructnode{ 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∥當鏈表尚未到尾(2)q!=NULL∥查p結點在鏈表中的插入位置(3)p->next=r->next∥將p結點鏈入鏈表中(4)r->next=p∥r是q的前驅，u是下個待插入結點的指針。292、請寫出判斷一棵二叉樹是否為平衡二叉樹的算法（假設不要求該二叉樹是排序二叉樹）。已知二叉樹采用二叉鏈表表示，其數(shù)據(jù)定義如下：typedefstructBiTNode{intdata;//關鍵字//左右孩子指針structBiTNode*lchild,*rchild;}BiTNode,*BiTree;30intIsBalanced(BiTreeT)//檢查二叉樹T是否是平衡樹。{//如果不平衡則返回-1，否則返回樹的深度。 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、計數(shù)排序算法對一個待排序的表（用數(shù)組表示）進行排序，并將排序結果存放到另一個新的表中。假設，表中所有待排序的關鍵字互不相同，計數(shù)排序算法針對表中的每個記錄，掃描待排序的表一趟，統(tǒng)計表中有多少個記錄的關鍵字比該記錄的關鍵字小，假設針對某一個記錄，統(tǒng)計出的計數(shù)值為c，那么，這個記錄在新的有序表中的合適的存放位置即為c。(1)給出適用于計數(shù)排序的數(shù)據(jù)表定義；(2)使用C語言編寫實現(xiàn)計數(shù)排序的算法；(3)對于有n個記錄的表，關鍵碼比較次數(shù)是多少？(4)該算法的空間復雜度是多少？32voidCountSort(RecTypea[],b[],intn)//計數(shù)排序算法，將a中記錄排序放入b中{for(i=0;i<n;i++)//對每一個元素a[i]

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

B．可隨機訪問任一結點C．不必預分配空間

D．所需空間與其長度成正比B342、下面程序段的時間復雜度為（

）voidfun1(intn){i=1;while(i<=n) i=i*3;}35log3n3、下面程序段的時間復雜度為（）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、不帶頭結點的單鏈表head為空的判定條件是()。A．head＝＝NULLB．Head->next＝＝NULLC．Head->next＝＝headD．head!＝NULL另：帶頭結點的單鏈表head為空的判定條件是()。AB375、帶頭結點的循環(huán)單鏈表head中，head為空的判定條件是()。A．head＝＝NULLB．head—>next＝＝NULLC．head—>next＝＝headD．head!＝NULLC386、在長度為n的()上，刪除第一個元素，其算法復雜度為O(n)。A．只有表頭指針的不帶頭結點的循環(huán)單鏈表B．只有表尾指針的不帶頭結點的循環(huán)單鏈表C．只有表尾指針的帶頭結點的循環(huán)單鏈表D．只有表尾指針的帶頭結點的循環(huán)雙鏈表A397、若線性表中有2n個元素，算法()在單鏈表上實現(xiàn)要比在順序表上實現(xiàn)效率更高。A．刪除所有值為x的元素

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

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

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

20.給定一棵樹，可以找到唯一的一顆二叉樹與之對應。（）TFFFT