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

一、單項(xiàng)選擇題 1、在以下的敘述中，正確的是( A )。 A. 線性表的線性存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈表存儲(chǔ)結(jié)構(gòu) B. 二維數(shù)組是其數(shù)據(jù)元素為線性表的線性表 C. 棧的操作方式是先進(jìn)先出 D. 隊(duì)列的操作方式是先進(jìn)后出2、判定一個(gè)循環(huán)隊(duì)列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、向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)s所指結(jié)點(diǎn)時(shí)，則執(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. 可以順序存儲(chǔ) B. 數(shù)據(jù)元素是一個(gè)字符 C. 可以鏈接存儲(chǔ) D. 數(shù)據(jù)元素可以是多個(gè)字符5、設(shè)矩陣A是一個(gè)對(duì)稱矩陣，為了節(jié)省存儲(chǔ)，將其下三角部分按行序存放在一維數(shù)組B1,n(n-1)/2中，對(duì)下三角部分中任一元素ai,j(ij),在一維數(shù)組B的下標(biāo)位置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、將遞歸算法轉(zhuǎn)換成對(duì)應(yīng)的非遞歸算法時(shí)，通常需要使用( A )。 A. 棧 B. 隊(duì)列 C. 鏈表 D. 樹7、樹的基本遍歷策略可分為先根遍歷和后根遍歷叉樹的基本遍歷策略可分為先序遍歷、中序遍歷和后序遍歷。這里，我們把由樹轉(zhuǎn)化得到的二叉樹叫做這棵樹對(duì)應(yīng)的二叉樹。結(jié)論_A_是正確的。 A. 樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的先序遍歷序列相同 B. 樹的后根遍歷序列與其對(duì)應(yīng)的二叉樹的后序遍歷序列相同 C. 樹的先根遍歷序列與其對(duì)應(yīng)的二叉樹的中序遍歷序列相同 D. 以下都不對(duì)8、對(duì)一個(gè)滿二叉樹，m個(gè)樹葉，n個(gè)結(jié)點(diǎn)，深度為h，則( D )。 A. n=h+m B. h+m=2n C. m=h-1 D. n=2h-19、具有7個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有( A )條邊才能確保是一個(gè)連通圖。 A. 5 B. 6 C. 7 D. 810、判定一個(gè)有向圖是否存在回路除了可以利用拓?fù)渑判蚍椒ㄍ?，還可以利用( D )。 A. 求關(guān)鍵路徑的方法 B. 求最短路徑的Dijkstra方法 C. 寬度優(yōu)先遍歷算法 D. 深度優(yōu)先遍歷算法11、有一個(gè)有序表為1,3,9,12,32,41,45,62,75,77,82,95,100,當(dāng)二分查找值為82的結(jié)點(diǎn)時(shí)，( C )次比較后查找成功。 A. 1 B. 2 C. 4 D. 812、如果要求一個(gè)線性表既能較快地查找，又能適應(yīng)動(dòng)態(tài)變化的要求，可以采用_A_查找方法。 A. 分塊 B. 順序 C. 二分 D. 散列13、在所有排序方法中，關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無(wú)關(guān)的是_D_。 A. 希爾排序 B. 起泡排序 C. 插入排序 D. 選擇排序14、快速排序方法在( C )情況下最不利于發(fā)揮其長(zhǎng)處。 A. 要排序的數(shù)據(jù)量太大 B. 要排序的數(shù)據(jù)中含有多個(gè)相同值 C. 要排序的數(shù)據(jù)已基本有序 D. 要排序的數(shù)據(jù)個(gè)數(shù)為奇數(shù)15、索引無(wú)序文件是指( A )。 A. 主文件無(wú)序，索引表有序 B. 主文件有序，索引表無(wú)序 C. 主文件有序，索引表有序 D. 主文件無(wú)序，索引表無(wú)序二、填空題（每空 2 分，共 30 分）16、下面程序段的時(shí)間復(fù)雜度是_O(m*n)_。 for ( i=0;in;i+) for (j=0; jnext=s;p-data=x;s=p;_。18、在hq的鏈隊(duì)中，判定只有一個(gè)結(jié)點(diǎn)的條件是_hq-front=hq-rear_。19、已知二維數(shù)組Amn采用行序?yàn)橹鞣绞酱鎯?chǔ)，每個(gè)元素占k個(gè)存儲(chǔ)單元，并且第一個(gè)元素的存儲(chǔ)地址是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_，其從頂點(diǎn)v1出發(fā)的寬度優(yōu)先搜索序列為_v1-v2-v5-v4-v3-v6_。24、在各種查找中，平均查找長(zhǎng)度與結(jié)點(diǎn)個(gè)數(shù)n無(wú)關(guān)的查法方法是_哈希_。25、在對(duì)一組記錄54,38,96,23,15,72,60,45,83進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表時(shí)，為尋找插入位置需比較_3_次。26、順序查找法的平均查找長(zhǎng)度為_n(n+1)/2_；二分查找法的平均查找長(zhǎng)度為_(n+1)*log2(n+1)/n-1_。三、解答操作題（每小題 5 分，共 20 分）27、已知序列503,87,512,61,908,170,897,275,653,462,采用基數(shù)排序法對(duì)該序列作升序排序時(shí)的每趟的結(jié)果。A0=170A1=61A2=512-462A3=503-653A5=275A7=87-897A8=90828、設(shè)給定權(quán)集w=2,3,4,7,8,9,度構(gòu)造關(guān)于w的一棵哈夫曼樹，并求其加權(quán)路徑長(zhǎng)度wpl。29、對(duì)下圖所示的樹： (1)轉(zhuǎn)換成對(duì)應(yīng)的二叉樹形式，并且說(shuō)明轉(zhuǎn)換規(guī)則； (2)寫出前序、中序、后序遍歷的結(jié)果；30.現(xiàn)有稀疏矩陣A如下圖所示，要求畫出以下幾種表示法。（1）三元組表示法（2）帶行指針向量的單鏈表表示法 （3）十字鏈表示法。四、算法閱讀題(每小題6分，共12分)31、下列算法的功能是實(shí)S串的逆序(串均采用順序存儲(chǔ)方式)，請(qǐng)?jiān)诳瞻滋幪钊脒m當(dāng)?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.下列算法的功能是實(shí)現(xiàn)鏈棧的進(jìn)棧運(yùn)算，請(qǐng)?jiān)诳瞻滋幪钊脒m當(dāng)?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 ; 五、算法設(shè)計(jì)題33、假設(shè)二叉樹采用鏈接方法存儲(chǔ)，編寫一個(gè)函數(shù)復(fù)制一棵給定的二叉樹。結(jié)點(diǎn)結(jié)構(gòu)為：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 卷一、單項(xiàng)選擇題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. 先移動(dòng)棧頂指針，后存入元素 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趟(按個(gè)位排序)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、加權(quán)路徑長(zhǎng)度wpl=72+82+43+24+34+92=8029（1）(2) 前序：abcejfdghki 中序：jefcgkhidba 后序：jfekihgdcba30. 四、算法設(shè)計(jì)題（每小題 6 分，共 12 分）參考答案31.s-length-i+1 Temp Return(s) 32. p-data=x; p-next=s-top; s-top=p;五、算法