0012數(shù)據(jù)結(jié)構(gòu)解析

1、0012數(shù)據(jù)結(jié)構(gòu)第一次作業(yè)填空題1 、已知棧的基本操作函數(shù)：int In itStack(SqStack *S); /構(gòu)造空棧int StackEmpty(SqStack *S);判斷?？読nt Push(SqStack*S,ElemType e);入棧int Pop(SqStack *S,ElemType *e);出棧函數(shù) con version實(shí)現(xiàn)十進(jìn)制數(shù)轉(zhuǎn)換為八進(jìn)制數(shù)，請將函數(shù)補(bǔ)充完整。void conv ersi on()Ini tStack(S);scanf(%d ”，&N);while(N)(1)；N=N/8;while(2)Pop(S,&e);printf(%d

2、” ,e);/conv ersi on2.設(shè)循環(huán)隊(duì)列的容量為70，現(xiàn)經(jīng)過一系列的入隊(duì)和出隊(duì)操作后，front 為 20，rear為 11，則隊(duì)列中元素的個(gè)數(shù)為 _。3.在一個(gè)單鏈表中刪除 p 所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)時(shí)，應(yīng)執(zhí)行以下操作：q = p-n ext;p-n ext=_一；4. 一個(gè)算法的效率可分為()效率和()效率。5數(shù)據(jù)結(jié)構(gòu)被形式地定義為(D, R)，其中 D 是()的有限集合，R 是 D 上的() 有限集合。6. 下面程序段的時(shí)間復(fù)雜度是( ) for(i=0;im;i+)for(j=0;jnext4.時(shí)間 空間5.數(shù)據(jù)元素 關(guān)系6.m*n 單選題 一個(gè)具有 n 個(gè)頂點(diǎn)的有向圖最多有(

3、 )條邊A:nx(n -1)/2B: nX(n+1)/2C:nX(n -1)D: n2參考答案: B 判斷題 折半查找只適用于有序表，包括有序的順序表和鏈表參考答案:錯(cuò)誤 判斷題 用循環(huán)單鏈表表示的鏈隊(duì)列中，可以不設(shè)隊(duì)頭指針，僅在隊(duì)尾設(shè)置隊(duì)尾指針。參考答案:正確 判斷題 在單鏈表中，要訪問某個(gè)結(jié)點(diǎn)，只要知道該結(jié)點(diǎn)的地址即可；因此，單鏈表是一種 隨機(jī)存取結(jié)構(gòu)。參考答案:錯(cuò)誤單選題判斷一個(gè)循環(huán)隊(duì)列Q (最多 n 個(gè)元素)為滿的條件是：A: Q-front=(Q-rear+1)%nB: Q-rear=Q-front+1C: Q-front=(Q-rear-1)%nD： Q-rear=Q-front參

4、考答案： A 單選題 在單鏈表中，指針 p 指向元素為 x 的結(jié)點(diǎn)，實(shí)現(xiàn)刪除 x 的后繼的語句是 :A： p=p-nextB： p=p-next-nextC： p-next=pD： p-next=p-next-next參考答案： D 單選題 在雙向循環(huán)鏈表中，在 p 指針?biāo)傅慕Y(jié)點(diǎn)后插入一個(gè)指針 q 所指向的新結(jié)點(diǎn)，修改 指針的操作是 :A： p-next=q;q-prior=p;p-next-prior=q;q-next=q;B： q-prior=p;q-next=p-next;p-next-prior=q;p-next=q;C： q-next=p-next;q-prior=p;p-next

5、=q;p-next=q;D： p-next=q;p-next-prior=q;q-prior=p;q-next=p-next;參考答案： B 多選題 抽象數(shù)據(jù)類型的組成部分分別為 :A:數(shù)據(jù)對象B:存儲結(jié)構(gòu)C:數(shù)據(jù)關(guān)系D:基本操作參考答案： ACD 多選題 不具有線性結(jié)構(gòu)的數(shù)據(jù)結(jié)構(gòu)是:A:圖B:棧C:廣義表D:樹參考答案：ACD多選題算法分析的兩個(gè)主要方面是（）A:正確性B:簡單性C:空間復(fù)雜度D:時(shí)間復(fù)雜度參考答案：CD第二次作業(yè)單選題設(shè)一棵完全二叉樹有 300 個(gè)結(jié)點(diǎn)，則共有 _個(gè)葉子結(jié)點(diǎn)A： 150B: 152C: 154D: 156參考答案：A單選題由3個(gè)結(jié)點(diǎn)所構(gòu)成的二叉樹有 _種形態(tài)

6、.A: 2B: 3C: 4D: 5參考答案：D單選題設(shè)有兩個(gè)串 p 和 q,求 q 在 p 中首次出現(xiàn)的位置的運(yùn)算稱作：A:連接B:模式匹配C:求子串D:求串長參考答案：B單選題棧中元素的進(jìn)出原則是A:先進(jìn)先出B:后進(jìn)先出C:?？談t進(jìn)D:棧滿則出參考答案：B單選題鏈表是一種采用 _存儲結(jié)構(gòu)存儲的線性表A:順序B:星式C:鏈?zhǔn)紻:網(wǎng)狀參考答案：C單選題數(shù)據(jù)在計(jì)算機(jī)存儲器內(nèi)表示時(shí)，物理地址與邏輯地址相同并且是連續(xù)的，稱之為：A:存儲結(jié)構(gòu)B:順序存儲結(jié)構(gòu)C:邏輯結(jié)構(gòu)D:鏈?zhǔn)酱鎯⒖即鸢福築判斷題鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針參考答案：錯(cuò)誤判斷題如果將所有中國人按照生日來排序，則使用哈希排序算法最

7、快參考答案：錯(cuò)誤填空題1.數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示，它們分別是（）2在具有 n 個(gè)元素的循環(huán)隊(duì)列中，隊(duì)滿時(shí)具有 _個(gè)元素.3.廣義表 A=（a）,a） 的表頭是（）4. 稀疏矩陣一般的壓縮存儲方法有（）和（）兩種。5. 用順序存儲的方法，將完全二叉樹中所有結(jié)點(diǎn)按層逐個(gè)從左到右的順序存放在一維數(shù)組R1.N 中，若結(jié)點(diǎn) Ri有右孩子，則其右孩子是（）6.如果從無向圖的任一頂點(diǎn)出發(fā)進(jìn)行一次深度優(yōu)先搜索即可訪問所有頂點(diǎn)，貝U該圖（）7. n 個(gè)頂點(diǎn)的連通圖至少有 _邊。8.已知一個(gè)有序表為（11 , 22 , 33 , 44 , 55 , 66 , 77 , 88 , 99）,則折半查

8、找 55 需要比較（9. 對一棵二叉排序樹按（）遍歷，可得到結(jié)點(diǎn)值從小到大的排列序列。10. 一個(gè)序列中有 10000 個(gè)元素，若只想得到其中前10 個(gè)最小元素，則最好采用（方法參考答案：1順序、鏈?zhǔn)健⑺鞴璉、散列2. n-13. （a）4.三元組十字鏈表5. R0+16.連通圖心曰）次7.n-1 8.19.中序10.堆排序第三次作業(yè) 單選題 在對 n 個(gè)元素的序列進(jìn)行排序時(shí)，堆排序所需要的附加存儲空間是:A： O(log2n)B： O(1)C： O(n)D： O(nlog2n)參考答案： B 單選題 若需要在 O(nlog2n) 的時(shí)間內(nèi)完成對數(shù)組的排序， 且要求排序是穩(wěn)定的， 則可選擇 的

9、排序方法是( )A:快速排序B:堆排序C:歸并排序D:直接插入?yún)⒖即鸢福?C 單選題 設(shè)哈希表長 m=14, 哈希函數(shù) H(key)=key MOD 11 。表中已有 4 個(gè)結(jié)點(diǎn):addr(15)=4,addr(38)=5,addr(61)=6,addr(84)=7 其余地址為空，如用二次探測 再散列處理沖突，則關(guān)鍵字為 49 的地址為 :A: 3B: 5C: 8D：9參考答案： C 論述題 1.設(shè)有編號為 1，2，3，4 的四輛列車，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的車站，具體寫出這四輛列 車開出車站的所有可能的順序。2.已知二叉樹如下圖所示，請寫出先序遍歷、中序遍歷和后序遍歷序列。3編寫遞歸算法，計(jì)算

10、二叉樹中葉子結(jié)點(diǎn)的數(shù)目4.函數(shù)實(shí)現(xiàn)單鏈表的插入算法，請?jiān)诳崭裉帉⑺惴ㄑa(bǔ)充完整 int List In sert(L in kListL,i nt i,ElemType e)LNode *p,*s;intj;P=L;j=O;while(p!=NULL)&(jI-1) n ext;j+;if(p=NULL|ji-1) retur n ERROR; s=(LNode *)malloc(sizeof(LNode);s-data=e;；_；_return OK;/*Listl nsert*/5.對于一個(gè)棧，給出輸入項(xiàng) A,B,C,D ，如果輸入項(xiàng)序列為 A,B,C,D ，試給出全部可能的輸出序列

11、。6. 已知二叉樹的先序遍歷序列為ABCDEFGH,中序遍歷序列為 CBEDFAGH，畫出二叉樹7.1、已知圖 G 的鄰接矩陣如下所示：（1）求從頂點(diǎn) 1 出發(fā)的廣度優(yōu)先搜索序列；（2）根據(jù) prim 算法， 求圖 G 從頂點(diǎn) 1 出發(fā)的最小生成樹， 要求表示出其每 步生成過程。（用圖或者表的方式均可）。Q06150OO6Q05O03oo150056斗卜卍500500002Q036Q0Q06GOQO42600參考答案：1.答：至少有 14 種。 全進(jìn)之后再出情況，只有 1 種：4, 3, 2, 1 進(jìn) 3 個(gè)之后再出的情況，有3 種，3,4,2,13,2,4,13,2,1,43進(jìn) 2 個(gè)之后再

12、出的情況，有4進(jìn) 1 個(gè)之后再出的情況，有5 種，2,4,3,12,3,4,12,1,3,4 2,1,4,32,1,3,45 種，1,4,3,21,3,2,41,3,4,2 1,2,3,41,2,4,3先序：BECFGDH中序：FEBGCHD后序：FEGHDCB2.6.3.法一：核心部分為：DLR(liuyu *root) /*中序遍歷 遞歸函數(shù) */if(root!=NULL)if(root-lchild=NULL)&(root-rchild=NULL)sum+;printf(%dn,root-data);DLR(root-lchild);DLR(root-rchild); retu

13、rn(0);法二：int LeafCount_BiTree(Bitree T)/ 求二叉樹中葉子結(jié)點(diǎn)的數(shù)目if(!T) return 0; / 空樹沒有葉子else if(!T-lchild&!T-rchild) return 1; / 葉子結(jié)點(diǎn)else return Leaf_Count(T-lchild)+Leaf_Count(T-rchild);/ 左子樹的葉子數(shù)加上右子樹的葉子數(shù)/LeafCount_BiTree4.(1)s-next=p-next (2)p-next=s5.ABCD ABDC ACDB ACBD ADCB BACD BADC BCAD BCDA CBDA CB

14、ADCDBA DCBA7.廣度優(yōu)先遍歷序列：1；2, 3, 4; 5; 6最小生成樹（prim 算法）I1第四次作業(yè)論述題1. 寫出用直接插入排序?qū)㈥P(guān)鍵字序列 54,23,89,48,64,50,25,90,34 排 序過程的每一趟結(jié)果。2.設(shè)待排序序列為 10,18,4,3,6,12,1,9,15,8請寫出希爾排序每一趟的結(jié)果。 增量序列為 5 ，3，2，1。3.寫出下列程序的時(shí)間復(fù)雜度for(i=0;ifor (j=0; jAij=0;4.寫出下列程序的時(shí)間復(fù)雜度s=0;for i=0; ifor（j=0; j s+=Bij;sum=s;5.設(shè)循環(huán)隊(duì)列的容量為 40（序號從 0 到 39）

15、，現(xiàn)經(jīng)過一系列的入隊(duì)和出隊(duì)運(yùn)算后， 有front=11, rear=19; front=19, rear=11;問在這兩種情況下，循環(huán)隊(duì)列 中各有元素多少個(gè)？6.若一個(gè)線性表中最常用的操作是取第 i 個(gè)元素和找第 i 個(gè)元素的前趨元素，則采用（ ） 存儲方式最節(jié)省時(shí)間 .7.在一個(gè)長度為 n 的順序表中刪除第 i 個(gè)元素，需要向前移動(dòng)（）個(gè)元素 .8. 帶頭結(jié)點(diǎn)的單鏈表 head 為空的判定條件是（）。9. 一個(gè)循環(huán)隊(duì)列 Q 的存儲空間大小為 M,其隊(duì)頭和隊(duì)尾指針分別為front 和 rear，則循環(huán)隊(duì)列中元素的個(gè)數(shù)為：_。10. 設(shè)串長為 n,模式串長為 m,則 KMP 算法所需的附加空間為

16、（）參考答案:1.54, 23, 89， 48， 64, 50， 25, 90， 341： (23, 54), 89, 48, 64, 50, 25, 90, 342.初始：10 , 18 , 4 , 3 , 6 , 12 , 1 , 9 , 15 , 8d=5:10,1,4,3,6,12 , 18 ,15,8d=3:3 , 1 , 4 , 8 , 6 , 12 , 10, 9 ,15 , 18d=2:3 , 1 , 4 , 8 , 6 , 9 , 10 , 12 ,15 , 18d=1:1 , 3 , 4 , 6 , 8 , 9 , 10 , 12 ,15 , 183.O (m*n)4.O

17、(nA2)6.順序表初始:2(2354 ,89), 483(23,48 ,54 , 89)4(23,48 ,54 , 64,5(23,48 ,50 ,54,6(23,25 ,48 ,50,7(2325 ,48 , 50,64, 50, 25, 90, 34,64, 50, 25, 90 , 3489), 50, 25, 90, 3464 , 89), 25 , 90 , 3454, 64, 89), 90, 3454, 64, 89, 90), 3450 , 54, 64, 89, 90, 34)5.(1) L= (40+ 19- 11) % 40=8(2) L= (40 + 11- 19) % 40=328:(23 ,7.n-18.head- next=NULL9.(rear-front+M)%M10.O(m)單選題計(jì)算機(jī)算法必須具備輸入、輸出和 _ 等 5 個(gè)特性A :易讀性、穩(wěn)定性和安全性B :