南京信息工程大學濱江學院數(shù)據(jù)結構期末試題及答案

1、一、單項選擇題1、在以下的表達中,正確的選項是A .A. 線性表的線性存儲結構優(yōu)丁鏈表存儲結構B. 二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表C. 棧的操作方式是先進先出D. 隊列的操作方式是先進后出2、判定一個循環(huán)隊列qu最多元素為m0為空的條件是A .A. qu->front=qu->rearB. qu->front!=qu->rearC. qu->front=qu->rear+1%m0D. qu->front!=qu->rear+1%m03、向一個棧頂指針為hs的鏈棧中插入一個s所指結點時,那么執(zhí)行C A. hs->next=s;B. s-

2、>next=hs->next;hs->next=s;C. s->next=hs;hs=s;D. s->next=hs;hs=sh->next4、申是一種特殊的線性表,其特殊性表達在 B .A. 可以順序存儲B.數(shù)據(jù)元素是一個字符C.可以存儲D.數(shù)據(jù)元素可以是多個字符5、設矩陣A是一個對稱矩陣,為了節(jié)省存儲,將其下三角局部按行序存 放在一維數(shù)組B1,n(n-1)/2中,對下三角局部中任一元素aid(i ),在一維 數(shù)組B的下標位置k的值是(B ).A. i(i-1)/2+j-1B. i(i-1)/2+jC. i(i+1)/2+j-1D. i(i+1)/2+j6

3、、將遞歸算法轉換成對應的非遞歸算法時,通常需要使用 (A ).A.棧 B.隊列 C.鏈表 D.樹7、樹的根本遍歷策略可分為先根遍歷和后根遍歷義樹的根本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷.這里,我們把由樹轉化得到的二義樹叫做這棵樹對應的二義樹.結論 _A_是正確的.A. 樹的先根遍歷序列與其對應的二義樹的先序遍歷序列相同B. 樹的后根遍歷序列與其對應的二義樹的后序遍歷序列相同C. 樹的先根遍歷序列與其對應的二義樹的中序遍歷序列相同D. 以下都不對8、對一個滿二義樹,m個樹葉,n個結點,深度為h,貝U( D ).A. n=h+mB. h+m=2nC. m=h-1 D.n=2 h-19、具有

4、7個頂點的無向圖至少應有(A )條邊才能保證是一個連通圖.A. 5 B. 6 C. 7 D. 810、判定一個有向圖是否存在回路除了可以利用拓撲排序方法外,還可以利用D .A.求關鍵路徑的方法B.求最短路徑的Dijkstra方法C.寬度優(yōu)先遍歷算法D.深度優(yōu)先遍歷算法11、有一個有序表為1,3,9,12,32,41, 45,62,75,77,82,95,100,當二分查找值為82的結點時,C次比擬后查找成功.A. 1B. 2C. 4D. 812、如果要求一個線性表既能較快地查找,乂能適應動態(tài)變化的要求,可以采用 A_查找方法.A.分塊 B.順序 C.二分D.散列13、在所有排序方法中,關鍵字比

5、擬的次數(shù)與記錄的初始排列次序無關的是 DA.希爾排序 B.起泡排序C.插入排序 D.選擇排序14、 快速排序方法在C情況下最不利丁發(fā)揮其長處.A. 要排序的數(shù)據(jù)量太大B. 要排序的數(shù)據(jù)中含有多個相同值C. 要排序的數(shù)據(jù)已根本有序D. 要排序的數(shù)據(jù)個數(shù)為奇數(shù)15、 索引無序文件是指A.A. 主文件無序,索引表有序B. 主文件有序,索引表無序C. 主文件有序,索引表有序D. 主文件無序,索引表無序二、填空題(每空2分,共30分)16、 下面程序段的時間復雜度是 O(m*n).for ( i=0;i<n;i+)for (j=0; j<m; j+)aij=0;17、向棧中壓入元素的操作是

6、_p->next=s;p->data=x;s=p;_ .18、在hq的鏈隊中,判定只有一個結點的條件是_hq->front=hq->rear_.19、二維數(shù)組Amn采用行序為主方式存儲,每個元素占k個存儲單元,并且第一個元素的存儲地址是LOC(A00) , Aij的地址是LOC(A00)+(n*i+j)*k .20、有如下遞歸方程：void print(int w) int i;if (w!=0)( print(w-l);for (i=1;i<=w;i+) print( "3d ,w);rpintf( "/n );調用語句print(4)結果是

7、 12 23 3 34 4 4 421、廣義表(a,(a,b),d,e,(i,j),k) 的長度是 5 深度是 _322、以數(shù)據(jù)集4,5,6,7,10,12,18為結點權值所構造的哈夫曼樹為 其帶權路徑長度為23、 圖G的鄰接表如以下圖所示,其從頂點v1出發(fā)的深度優(yōu)先搜索序歹0為_v1->v2->v3->v6->v5->v4_,其從頂點v1出發(fā)的寬度優(yōu)先搜索序歹0 為 v1->v2->v5->v4->v3->v6.24、在各種查找中,平均查找長度與結點個數(shù) n無關的查法方法是 哈希025、在對一組記錄54,38,96,23,15,72

8、,60,45,83 進行直接插入排序時,當把第7個記錄60插入到有序表時,為尋找插入位置需比擬 _3_次.26、 順序查找法的平均查找長度為_n(n+1)/2;二分查找法的平均 查找長度為(n+1)*log2(n+1)/n-1.三、解答操作題(每題 5分,共20分)27、 序列503,87,512,61,908,170,897,275,653,462,采用基數(shù)排序法對該序列作升序排序時的每趟的結果.A0=170A1=61A2=512->462A3=503->653A5=275A7=87->897A8=90828、設給定權集w=2,3,4,7,8,9,度構造關丁 w的一棵哈夫曼

9、樹,并求其加權路徑長度wpl.29、對以下圖所示的樹：(1)轉換成對應的二義樹形式,并且說明轉換規(guī)那么;30.現(xiàn)有稀疏矩陣A如以下圖所示,要求畫出以下幾種表示法.(2)帶行指針向量的單鏈表表示法(3)十字鏈表示法.四、算法閱讀題(每題6分,共121500220<50133000000-6000000009000000028000(1)三元組表示法),請在空白31、以下算法的功能是實S申的逆序(申均采用順序存儲方式處填入適當?shù)娜軸eqString *invert (SegString *s)( int i;char tempfor (i=0; i<s->length/2; i+

10、)( temp=s->chi;s->chi=s->ch s->length-i+1 ;s->chs->length-i+1= tem return s ;32. 以下算法的功能是實現(xiàn)鏈棧的進棧運算,請在空白處填入適當?shù)娜?鏈棧的類型定義如下：Typedef struct stacknode (DataType data;Struct stacknode *next; StackNode;Typedef struct (StackNode *top;LinkStack;Void Push(LinkStack *s,DataType x)StackNode p;

11、*p=(StackOde*)malloc(sizeof(StackNode);p->data= x ;p->next= s->tops->top= p ; 五、算法設計題33、假設二義樹采用方法存儲,編寫一個函數(shù)復制一棵給定的二義樹.結點結構為:left dataCopy(BiTree *T) (if(!T)return NULL;BiTree *S=new BiTree;if(T->Lchild) S->Lchild=T->Lchild; Copy(T->Lchild);if(T->Rchild) S->Rchild=T->R

12、child; Copy(T->Rchild);卷、單項選擇題1. B 2.A 3. C 4. B 5. B 6. A 7. A8. D 9. A 10. D11. C 12. A 13. D 14. C 15. A、填空題每題2分,共30分)16. O(m*n) 17.先移動棧頂指針,后存入元素18. hq->front=hq->rear 19. LOC(A00)+(n*i+j)*k20.答 13 3 34 4 4 423、v1,v2,v3,v6,v5,v4v1,v2,v5,v4,v3,v624、哈希表查找法 25、326、(n+1)/2(n+1)*log2(n+1)/n-1

13、三、操作題(每題5分,共20分)27、初始：503 , 87, 512 , 61 , 908 , 170 , 897 , 275 , 653 , 462第 1 趟(按個位排序)170,61,462,512,503,653,475,87,897,908第2趟(按十位排序)503,908,512,653,61,462,170,175,87,897第3趟(按白位排序)61,87,170,275,462,503,512,653,897,90828、加權路徑長度 wpl=7 X2+8 X2+4 X3+2 X4+3 X4+9 X2=8029 . (1)(2)前序：abcejfdghki中序:jefcgkhidba后序：jfekihgdcba30.四、算法設計題(每題 6分,共12分)31. s-length-i+1TempReturn(s)32. p->data=x;p->next=s->top;s