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

一、單項選擇題 1、在以下的敘述中，正確的是( A )。 A. 線性表的線性存儲結構優(yōu)于鏈表存儲結構 B. 二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表 C. 棧的操作方式是先進先出 D. 隊列的操作方式是先進后出2、判定一個循環(huán)隊列qu(最多元素為m0)為空的條件是( A )。 A. qu-front=qu-rear B. qu-front!=qu-rear C. qu-front=(qu-rear+1)%m0 D. qu-front!=(qu-rear+1)%m03、向一個棧頂指針為hs的鏈棧中插入一個s所指結點時，則執(zhí)行( C )。 A. hs-next=s; B. s-next=hs-next;hs-next=s; C. s-next=hs;hs=s; D. s-next=hs;hs=sh-next4、串是一種特殊的線性表，其特殊性體現(xiàn)在（ B ）。 A. 可以順序存儲 B. 數(shù)據(jù)元素是一個字符 C. 可以鏈接存儲 D. 數(shù)據(jù)元素可以是多個字符5、設矩陣A是一個對稱矩陣，為了節(jié)省存儲，將其下三角部分按行序存放在一維數(shù)組B1,n(n-1)/2中，對下三角部分中任一元素ai,j(ij),在一維數(shù)組B的下標位置k的值是（ B ）。 A. i(i-1)/2+j-1 B. i(i-1)/2+j C. i(i+1)/2+j-1 D. i(i+1)/2+j6、將遞歸算法轉換成對應的非遞歸算法時，通常需要使用( A )。 A. 棧 B. 隊列 C. 鏈表 D. 樹7、樹的基本遍歷策略可分為先根遍歷和后根遍歷叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉化得到的二叉樹叫做這棵樹對應的二叉樹。結論_A_是正確的。 A. 樹的先根遍歷序列與其對應的二叉樹的先序遍歷序列相同 B. 樹的后根遍歷序列與其對應的二叉樹的后序遍歷序列相同 C. 樹的先根遍歷序列與其對應的二叉樹的中序遍歷序列相同 D. 以下都不對8、對一個滿二叉樹，m個樹葉，n個結點，深度為h，則( D )。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2h-19、具有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. 1 B. 2 C. 4 D. 812、如果要求一個線性表既能較快地查找，又能適應動態(tài)變化的要求，可以采用_A_查找方法。 A. 分塊 B. 順序 C. 二分 D. 散列13、在所有排序方法中，關鍵字比較的次數(shù)與記錄的初始排列次序無關的是_D_。 A. 希爾排序 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;in;i+) for (j=0; jnext=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-1); for (i=1;iv2-v3-v6-v5-v4_，其從頂點v1出發(fā)的寬度優(yōu)先搜索序列為_v1-v2-v5-v4-v3-v6_。24、在各種查找中，平均查找長度與結點個數(shù)n無關的查法方法是_哈希_。25、在對一組記錄54,38,96,23,15,72,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的一棵哈夫曼樹，并求其加權路徑長度wpl。29、對下圖所示的樹： (1)轉換成對應的二叉樹形式，并且說明轉換規(guī)則； (2)寫出前序、中序、后序遍歷的結果；30.現(xiàn)有稀疏矩陣A如下圖所示，要求畫出以下幾種表示法。（1）三元組表示法（2）帶行指針向量的單鏈表表示法 （3）十字鏈表示法。四、算法閱讀題(每小題6分，共12分)31、下列算法的功能是實S串的逆序(串均采用順序存儲方式)，請在空白處填入適當?shù)膬?nèi)容。SeqString *invert (SegString *s) int i; char temp for (i=0; ilength/2; i+) temp=s-chi; s-chi=s-ch s-length-i+1 ; s-chs-length-i+1= temp ; return s ;32.下列算法的功能是實現(xiàn)鏈棧的進棧運算，請在空白處填入適當?shù)膬?nèi)容。 鏈棧的類型定義如下：Typedef struct stacknode DataType data; Struct stacknode *next; StackNode; Typedef struct StackNode *top; LinkStack;Void Push(LinkStack *s,DataType x) StackNode p; *p=(StackNode *)malloc(sizeof(StackNode); p-data= x ; p-next= s-top ; s-top= p ; 五、算法設計題33、假設二叉樹采用鏈接方法存儲，編寫一個函數(shù)復制一棵給定的二叉樹。結點結構為：Copy(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-Rchild; Copy(T-Rchild);D 卷一、單項選擇題1. B 2. A 3. C 4. B 5. B 6. A 7. A 8. D 9. A 10. D 11. 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)*k 20. 答 1 2 2 3 3 3 4 4 4 4 23、 v1,v2,v3,v6,v5,v4 v1,v2,v5,v4,v3,v6 24、哈希表查找法 25、3 26、(n+1)/2 (n+1)*log2(n+1)/n-1三、操作題（每小題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=72+82+43+24+34+92=8029（1）(2) 前序：abcejfdghki 中序：jefcgkhidba 后序：jfekihgdcba30. 四、算法設計題（每小題 6 分，共 12 分）參考答案31.s-length-i+1 Temp Return(s) 32. p-data=x; p-next=s-top; s-top=p;五、算法