九九热最新网址,777奇米四色米奇影院在线播放,国产精品18久久久久久久久久,中文有码视频,亚洲一区在线免费观看,国产91精品在线,婷婷丁香六月天

歡迎來到裝配圖網(wǎng)! | 幫助中心 裝配圖網(wǎng)zhuangpeitu.com!
裝配圖網(wǎng)
ImageVerifierCode 換一換
首頁 裝配圖網(wǎng) > 資源分類 > DOC文檔下載  

數(shù)據(jù)結(jié)構(gòu)習(xí)題集與實(shí)驗(yàn)指導(dǎo)

  • 資源ID:23694639       資源大小:1.38MB        全文頁數(shù):177頁
  • 資源格式: DOC        下載積分:14.9積分
快捷下載 游客一鍵下載
會員登錄下載
微信登錄下載
三方登錄下載: 微信開放平臺登錄 支付寶登錄   QQ登錄   微博登錄  
二維碼
微信掃一掃登錄
下載資源需要14.9積分
郵箱/手機(jī):
溫馨提示:
用戶名和密碼都是您填寫的郵箱或者手機(jī)號,方便查詢和重復(fù)下載(系統(tǒng)自動生成)
支付方式: 支付寶    微信支付   
驗(yàn)證碼:   換一換

 
賬號:
密碼:
驗(yàn)證碼:   換一換
  忘記密碼?
    
友情提示
2、PDF文件下載后,可能會被瀏覽器默認(rèn)打開,此種情況可以點(diǎn)擊瀏覽器菜單,保存網(wǎng)頁到桌面,就可以正常下載了。
3、本站不支持迅雷下載,請使用電腦自帶的IE瀏覽器,或者360瀏覽器、谷歌瀏覽器下載即可。
4、本站資源下載后的文檔和圖紙-無水印,預(yù)覽文檔經(jīng)過壓縮,下載后原文更清晰。
5、試題試卷類文檔,如果標(biāo)題沒有明確說明有答案則都視為沒有答案,請知曉。

數(shù)據(jù)結(jié)構(gòu)習(xí)題集與實(shí)驗(yàn)指導(dǎo)

目錄基礎(chǔ)練習(xí)題及答案1第一章 緒論1第二章 線性表3第三章 棧和隊(duì)列7第四-五章 串和數(shù)組12第六章 樹和二叉樹.16第七章 圖.24第八章 查找.30第九章 排序.33數(shù)據(jù)結(jié)構(gòu)實(shí)驗(yàn)指導(dǎo)34實(shí)驗(yàn)一 線性表的應(yīng)用.34實(shí)驗(yàn)二 棧和隊(duì)列的應(yīng)用.39實(shí)驗(yàn)三 串的應(yīng)用.47實(shí)驗(yàn)四 數(shù)組.48實(shí)驗(yàn)五 二叉樹的應(yīng)用.51實(shí)驗(yàn)六 圖的應(yīng)用.55實(shí)驗(yàn)七 查找.56實(shí)驗(yàn)八 排序.61配套題集算法答案64第一章 緒論.64第二章 線性表.67第三章 棧與隊(duì)列.79第四章 串.89第五章 數(shù)組和廣義表.101第六章 樹和二叉樹.114第七章 圖.133第八章 動態(tài)存儲管理.148第九章 查找.152第十章 內(nèi)部排序.163基礎(chǔ)練習(xí)題及答案第一章 緒論一、 填空題1. 數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的 操作對象 以及它們之間的 關(guān)系 和運(yùn)算等的學(xué)科。2. 數(shù)據(jù)結(jié)構(gòu)被形式地定義為(D, R),其中D是 數(shù)據(jù)元素 的有限集合,R是D上的 關(guān)系 有限集合。3. 數(shù)據(jù)結(jié)構(gòu)包括數(shù)據(jù)的 邏輯結(jié)構(gòu) 、數(shù)據(jù)的 存儲結(jié)構(gòu) 和數(shù)據(jù)的 運(yùn)算 這三個(gè)方面的內(nèi)容。4. 數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類,它們分別是 線性結(jié)構(gòu) 和 非線性結(jié)構(gòu) 。5. 線性結(jié)構(gòu)中元素之間存在一對一關(guān)系,樹形結(jié)構(gòu)中元素之間存在一對多關(guān)系,圖形結(jié)構(gòu)中元素之間存在多對多關(guān)系。6 在線性結(jié)構(gòu)中,第一個(gè)結(jié)點(diǎn) 沒有 前驅(qū)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有 1個(gè)前驅(qū)結(jié)點(diǎn);最后一個(gè)結(jié)點(diǎn) 沒有 后續(xù)結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有1個(gè)后續(xù)結(jié)點(diǎn)。7. 在樹形結(jié)構(gòu)中,樹根結(jié)點(diǎn)沒有 前驅(qū) 結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)有且只有 1 個(gè)前驅(qū)結(jié)點(diǎn);葉子結(jié)點(diǎn)沒有 后續(xù) 結(jié)點(diǎn),其余每個(gè)結(jié)點(diǎn)的后續(xù)結(jié)點(diǎn)數(shù)可以任意多個(gè) 。8. 在圖形結(jié)構(gòu)中,每個(gè)結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)數(shù)和后續(xù)結(jié)點(diǎn)數(shù)可以 任意多個(gè) 。9數(shù)據(jù)的存儲結(jié)構(gòu)可用四種基本的存儲方法表示,它們分別是順序 、鏈?zhǔn)?、索引 和 散列 。10. 數(shù)據(jù)的運(yùn)算最常用的有5種,它們分別是插入 、 刪除、修改、 查找 、排序。11. 一個(gè)算法的效率可分為 時(shí)間 效率和 空間 效率。12.任何一個(gè)C程序都由 一個(gè)主函數(shù) 和若干個(gè)被調(diào)用的其它函數(shù)組成。13. 變量一經(jīng)說明,就確定該變量的取值范圍(即存儲單元)及 確定變量所允許的運(yùn)算 。二、單項(xiàng)選擇題( C )1. 數(shù)據(jù)結(jié)構(gòu)中,與所使用的計(jì)算機(jī)無關(guān)的是數(shù)據(jù)的 結(jié)構(gòu);A) 存儲 B) 物理 C) 邏輯 D) 物理和存儲( C )2. 算法分析的目的是:A) 找出數(shù)據(jù)結(jié)構(gòu)的合理性 B) 研究算法中的輸入和輸出的關(guān)系C) 分析算法的效率以求改進(jìn) D) 分析算法的易懂性和文檔性( A )3. 算法分析的兩個(gè)主要方面是:A) 空間復(fù)雜性和時(shí)間復(fù)雜性 B) 正確性和簡明性C) 可讀性和文檔性 D) 數(shù)據(jù)復(fù)雜性和程序復(fù)雜性( C )4. 計(jì)算機(jī)算法指的是:A) 計(jì)算方法 B) 排序方法 C) 解決問題的有限運(yùn)算序列 D) 調(diào)度方法( B )5. 計(jì)算機(jī)算法必須具備輸入、輸出和 等5個(gè)特性。A) 可行性、可移植性和可擴(kuò)充性 B) 可行性、確定性和有窮性C) 確定性、有窮性和穩(wěn)定性 D) 易讀性、穩(wěn)定性和安全性三、簡答題1. 數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)類型兩個(gè)概念之間有區(qū)別嗎?答:簡單地說,數(shù)據(jù)結(jié)構(gòu)定義了一組按某些關(guān)系結(jié)合在一起的數(shù)組元素。數(shù)據(jù)類型不僅定義了一組帶結(jié)構(gòu)的數(shù)據(jù)元素,而且還在其上定義了一組操作。2. 簡述線性結(jié)構(gòu)與非線性結(jié)構(gòu)的不同點(diǎn)。答:線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是 一對一的,非線性結(jié)構(gòu)反映結(jié)點(diǎn)間的邏輯關(guān)系是多對多的。四、閱讀下列C程序段,寫出相應(yīng)的執(zhí)行結(jié)果2. long int fact(n)int n;long f;if(n>1)f=n*fact(n-1); else f=1;return(f);main()int n;long y;n=5;y=fact(n);printf(“%d,%ldn”,n,y);答:運(yùn)行結(jié)果為: 5,120 1. printf(“Input x”);scanf(“%d”,&x);if (x<=30) if(x>20) y=x;else if (x>10) y=2*x;if (x>0&&x<30)printf(“x=%d,y=%d”,x,y);else printf(“輸入數(shù)據(jù)錯(cuò)!”);試寫出當(dāng)x分別為18,8時(shí)的執(zhí)行結(jié)果。答:運(yùn)行結(jié)果為:x=18,y=36 x=8,y=運(yùn)行前的值, 且從x30開始為數(shù)據(jù)錯(cuò)五、分析下面各程序段的時(shí)間復(fù)雜度2. s=0; for i=0; i<n; i+)for(j=0; j<n; j+) s+=Bij;sum=s;答:O(n2)答:O(n2)1. for (i=0; i<n; i+)for (j=0; j<m; j+)Aij=0;答:O(m*n)3. x=0;for(i=1; i<n; i+) for (j=1; j<=n-i; j+)x+;解:因?yàn)閤+共執(zhí)行了n-1+n-2+1= n(n-1)/2,所以執(zhí)行時(shí)間為O(n2)4. i=1; while(i<=n) i=i*3;答:O(log3n)六、設(shè)有數(shù)據(jù)邏輯結(jié)構(gòu)S=(D,R),試按各小題所給條件畫出這些邏輯結(jié)構(gòu)的圖示,并確定相對于關(guān)系R,哪些結(jié)點(diǎn)是開始結(jié)點(diǎn),哪些結(jié)點(diǎn)是終端結(jié)點(diǎn) 1. D=d1,d2,d3,d4 R=(d1,d2),(d2,d3),(d3,d4) 答: d1d2d3d4 d1無直接前驅(qū),是首結(jié)點(diǎn) d4無直接后繼是尾結(jié)點(diǎn)2. D=d1,d2,d9 R=(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5), (d6,d7),(d8,d9) 答: 此圖為樹形結(jié)構(gòu) d1無直接前驅(qū),是根結(jié)點(diǎn) d2,d5,d7,d9無直接后繼是葉子結(jié)點(diǎn)3. D=d1,d2,d9 R=(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9), (d5,d6),(d8,d9),(d9,d7), (d4,d7), (d4,d6)答: 此圖為圖形結(jié)構(gòu) d1,d2無直接前驅(qū),是開始結(jié)點(diǎn) d6,d7無直接后繼是終端結(jié)點(diǎn)第二章 線性表一、填空1.在順序表中插入或刪除一個(gè)元素,需要平均移動 表中一半 元素,具體移動的元素個(gè)數(shù)與 表長和該元素在表中的位置 有關(guān)。2. 線性表中結(jié)點(diǎn)的集合是 有限 的,結(jié)點(diǎn)間的關(guān)系是 一對一 的。3. 向一個(gè)長度為n的向量的第i個(gè)元素(1in+1)之前插入一個(gè)元素時(shí),需向后移動 n-i+1 個(gè)元素。4. 向一個(gè)長度為n的向量中刪除第i個(gè)元素(1in)時(shí),需向前移動 n-i 個(gè)元素。5. 在順序表中訪問任意一結(jié)點(diǎn)的時(shí)間復(fù)雜度均為 O(1) ,因此,順序表也稱為 隨機(jī)存取 的數(shù)據(jù)結(jié)構(gòu)。6.順序表中邏輯上相鄰的元素的物理位置 必定相鄰。單鏈表中邏輯上相鄰的元素的物理位置 不一定 相鄰。7.在單鏈表中,除了首元結(jié)點(diǎn)外,任一結(jié)點(diǎn)的存儲位置由 其直接前驅(qū)結(jié)點(diǎn)的鏈域的值 指示。8 在n個(gè)結(jié)點(diǎn)的單鏈表中要刪除已知結(jié)點(diǎn)*p,需找到它的前驅(qū)結(jié)點(diǎn)的地址,其時(shí)間復(fù)雜度為O(n)。二、判斷正誤( )1. 鏈表的每個(gè)結(jié)點(diǎn)中都恰好包含一個(gè)指針。 答:錯(cuò)誤。鏈表中的結(jié)點(diǎn)可含多個(gè)指針域,分別存放多個(gè)指針。例如,雙向鏈表中的結(jié)點(diǎn)可以含有兩個(gè)指針域,分別存放指向其直接前趨和直接后繼結(jié)點(diǎn)的指針。( )2. 鏈表的物理存儲結(jié)構(gòu)具有同鏈表一樣的順序。錯(cuò),鏈表的存儲結(jié)構(gòu)特點(diǎn)是無序,而鏈表的示意圖有序。( )3. 鏈表的刪除算法很簡單,因?yàn)楫?dāng)刪除鏈中某個(gè)結(jié)點(diǎn)后,計(jì)算機(jī)會自動地將后續(xù)的各個(gè)單元向前移動。錯(cuò),鏈表的結(jié)點(diǎn)不會移動,只是指針內(nèi)容改變。( )4. 線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型,而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。錯(cuò),混淆了邏輯結(jié)構(gòu)與物理結(jié)構(gòu),鏈表也是線性表!且即使是順序表,也能存放記錄型數(shù)據(jù)。( )5. 順序表結(jié)構(gòu)適宜于進(jìn)行順序存取,而鏈表適宜于進(jìn)行隨機(jī)存取。 錯(cuò),正好說反了。順序表才適合隨機(jī)存取,鏈表恰恰適于“順藤摸瓜”( )6. 順序存儲方式的優(yōu)點(diǎn)是存儲密度大,且插入、刪除運(yùn)算效率高。錯(cuò),前一半正確,但后一半說法錯(cuò)誤,那是鏈?zhǔn)酱鎯Φ膬?yōu)點(diǎn)。順序存儲方式插入、刪除運(yùn)算效率較低,在表長為n的順序表中,插入和刪除一個(gè)數(shù)據(jù)元素,平均需移動表長一半個(gè)數(shù)的數(shù)據(jù)元素。( )7. 線性表在物理存儲空間中也一定是連續(xù)的。錯(cuò),線性表有兩種存儲方式,順序存儲和鏈?zhǔn)酱鎯?。后者不要求連續(xù)存放。( )8. 線性表在順序存儲時(shí),邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。錯(cuò)誤。線性表有兩種存儲方式,在順序存儲時(shí),邏輯上相鄰的元素在存儲的物理位置次序上也相鄰。( )9. 順序存儲方式只能用于存儲線性結(jié)構(gòu)。錯(cuò)誤。順序存儲方式不僅能用于存儲線性結(jié)構(gòu),還可以用來存放非線性結(jié)構(gòu),例如完全二叉樹是屬于非線性結(jié)構(gòu),但其最佳存儲方式是順序存儲方式。(后一節(jié)介紹)( )10. 線性表的邏輯順序與存儲順序總是一致的。錯(cuò),理由同7。鏈?zhǔn)酱鎯蜔o需一致。三、單項(xiàng)選擇題( C )1數(shù)據(jù)在計(jì)算機(jī)存儲器內(nèi)表示時(shí),物理地址與邏輯地址相同并且是連續(xù)的,稱之為:(A)存儲結(jié)構(gòu) (B)邏輯結(jié)構(gòu) (C)順序存儲結(jié)構(gòu) (D)鏈?zhǔn)酱鎯Y(jié)構(gòu)( B )2.一個(gè)向量第一個(gè)元素的存儲地址是100,每個(gè)元素的長度為2,則第5個(gè)元素的地址是 (A)110 (B)108 (C)100 (D)120( A )3. 在n個(gè)結(jié)點(diǎn)的順序表中,算法的時(shí)間復(fù)雜度是O(1)的操作是:(A) 訪問第i個(gè)結(jié)點(diǎn)(1in)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)(2in) (B) 在第i個(gè)結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)(1in)(C) 刪除第i個(gè)結(jié)點(diǎn)(1in)(D) 將n個(gè)結(jié)點(diǎn)從小到大排序( B )4. 向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來順序不變,平均要移動 個(gè)元素(A)8 (B)63.5 (C)63 (D)7( A )5. 鏈接存儲的存儲結(jié)構(gòu)所占存儲空間:(A) 分兩部分,一部分存放結(jié)點(diǎn)值,另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針(B) 只有一部分,存放結(jié)點(diǎn)值(C) 只有一部分,存儲表示結(jié)點(diǎn)間關(guān)系的指針(D) 分兩部分,一部分存放結(jié)點(diǎn)值,另一部分存放結(jié)點(diǎn)所占單元數(shù)( B )6. 鏈表是一種采用 存儲結(jié)構(gòu)存儲的線性表;(A)順序 (B)鏈?zhǔn)?(C)星式 (D)網(wǎng)狀( D )7. 線性表若采用鏈?zhǔn)酱鎯Y(jié)構(gòu)時(shí),要求內(nèi)存中可用存儲單元的地址:(A)必須是連續(xù)的 (B)部分地址必須是連續(xù)的(C)一定是不連續(xù)的 (D)連續(xù)或不連續(xù)都可以( B )8 線性表在 情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。()需經(jīng)常修改中的結(jié)點(diǎn)值 ()需不斷對進(jìn)行刪除插入 ()中含有大量的結(jié)點(diǎn) ()中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜( C )9 單鏈表的存儲密度()大于1; ()等于1; ()小于1; ()不能確定( B )10 設(shè)a1、a2、a3為3個(gè)結(jié)點(diǎn),整數(shù)P0,3,4代表地址,則如下的鏈?zhǔn)酱鎯Y(jié)構(gòu)稱為P034P0a13a24A30()循環(huán)鏈表 ()單鏈表 ()雙向循環(huán)鏈表 ()雙向鏈表四、簡答題1.試比較順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)缺點(diǎn)。在什么情況下用順序表比鏈表好?答: 順序存儲時(shí),相鄰數(shù)據(jù)元素的存放地址也相鄰(邏輯與物理統(tǒng)一);要求內(nèi)存中可用存儲單元的地址必須是連續(xù)的。優(yōu)點(diǎn):存儲密度大(1?),存儲空間利用率高。缺點(diǎn):插入或刪除元素時(shí)不方便。鏈?zhǔn)酱鎯r(shí),相鄰數(shù)據(jù)元素可隨意存放,但所占存儲空間分兩部分,一部分存放結(jié)點(diǎn)值,另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針優(yōu)點(diǎn):插入或刪除元素時(shí)很方便,使用靈活。缺點(diǎn):存儲密度?。?lt;1),存儲空間利用率低。順序表適宜于做查找這樣的靜態(tài)操作;鏈表宜于做插入、刪除這樣的動態(tài)操作。若線性表的長度變化不大,且其主要操作是查找,則采用順序表;若線性表的長度變化較大,且其主要操作是插入、刪除操作,則采用鏈表。2 .描述以下三個(gè)概念的區(qū)別:頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)(第一個(gè)元素結(jié)點(diǎn))。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是什么?答:首元結(jié)點(diǎn)是指鏈表中存儲線性表中第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。為了操作方便,通常在鏈表的首元結(jié)點(diǎn)之前附設(shè)一個(gè)結(jié)點(diǎn),稱為頭結(jié)點(diǎn),該結(jié)點(diǎn)的數(shù)據(jù)域中不存儲線性表的數(shù)據(jù)元素,其作用是為了對鏈表進(jìn)行操作時(shí),可以對空表、非空表的情況以及對首元結(jié)點(diǎn)進(jìn)行統(tǒng)一處理。頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)(或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn))的指針。若鏈表中附設(shè)頭結(jié)點(diǎn),則不管線性表是否為空表,頭指針均不為空。否則表示空表的鏈表的頭指針為空。這三個(gè)概念對單鏈表、雙向鏈表和循環(huán)鏈表均適用。是否設(shè)置頭結(jié)點(diǎn),是不同的存儲結(jié)構(gòu)表示同一邏輯結(jié)構(gòu)的問題。 頭結(jié)點(diǎn)headdatalink 頭指針 首元結(jié)點(diǎn)簡而言之,頭指針是指向鏈表中第一個(gè)結(jié)點(diǎn)(或?yàn)轭^結(jié)點(diǎn)或?yàn)槭自Y(jié)點(diǎn))的指針;頭結(jié)點(diǎn)是在鏈表的首元結(jié)點(diǎn)之前附設(shè)的一個(gè)結(jié)點(diǎn);數(shù)據(jù)域內(nèi)只放空表標(biāo)志和表長等信息(內(nèi)放頭指針?那還得另配一個(gè)頭指針?。┦自亟Y(jié)點(diǎn)是指鏈表中存儲線性表中第一個(gè)數(shù)據(jù)元素a1的結(jié)點(diǎn)。五、線性表具有兩種存儲方式,即順序方式和鏈接方式。現(xiàn)有一個(gè)具有五個(gè)元素的線性表L=23,17,47,05,31,若它以鏈接方式存儲在下列100119號地址空間中,每個(gè)結(jié)點(diǎn)由數(shù)據(jù)(占2個(gè)字節(jié))和指針(占2個(gè)字節(jié))組成,如下所示:05U17X23V31Y47Z100120其中指針X,Y,Z的值分別為多少?該線性表的首結(jié)點(diǎn)起始地址為多少?末結(jié)點(diǎn)的起始地址為多少? 答:X= 116 Y= 0 Z= 100 首址= 108 末址= 112 六、閱讀分析題指出以下算法中的錯(cuò)誤和低效(即費(fèi)時(shí))之處,并將它改寫為一個(gè)既正確又高效的算法。Status DeleteK(SqList&a, int i, int k)/本過程從順序存儲結(jié)構(gòu)的線性表a中刪除第i個(gè)元素起的k個(gè)元素if ( i<1 | k<0 | i+k> a.length ) return INFEASIBLE; /參數(shù)不合法elsefor(count = 1; count <k; count + ) /刪除一個(gè)元素for ( j = a.length; j>=i+1; j-) a.elemj-1 = a.elemj;a.length - -; return OK; / DeleteK注:上題涉及的類型定義如下:# define LIST INIT SIZE 100# define LISTINCREMENT 10typedef struct Elem Type *elem; /存儲空間基址Int length; /當(dāng)前長度Int listsize; /當(dāng)前分配的存儲容量SqList;答:錯(cuò)誤有兩處: 參數(shù)不合法的判別條件不完整。例如表長為10,若從第一位置(i=1)刪除10個(gè)元素(k=10),要求合理但會被判為非法。合法的入口參數(shù)條件為(0<ia.length) (0ka.length-i) 應(yīng)將if ( i<1 | k<0 | i+k> a.length ) return INFEASIBLE改為:if (!(0<ia.length) (oka.length-i))) return INFEASIBLE第二個(gè)FOR語句中,元素前移的次序錯(cuò)誤。應(yīng)將for ( j = a.length; j>=i+1; j-) a.elemj-1 = a.elemj;改為for (j>=i+1; j = a.length; j+) a.elemj-1 = a.elemj;七、編程題invsl(n,a)int n;ET a;int k;ET t;for (k=1; k<=n/2; k+)t=ak-1; ak-1=an-k; an-k=t;return;1.寫出在順序存儲結(jié)構(gòu)下將線性表逆轉(zhuǎn)的算法,要求使用最少的附加空間。解:輸入:長度為n的線性表數(shù)組A(1:n)輸出:逆轉(zhuǎn)后的長度為n的線性表數(shù)組A(1:n)。C語言描述如下(其中ET為數(shù)據(jù)元素的類型):2.已知L是無表頭結(jié)點(diǎn)的單鏈表,且P結(jié)點(diǎn)既不是首元結(jié)點(diǎn),也不是尾元結(jié)點(diǎn),請寫出在P結(jié)點(diǎn)后插入S結(jié)點(diǎn)的核心語句序列。答:此題答案不唯一,但若從已給定序列中挑選,則限制頗多。(7) Q=P;已知P結(jié)點(diǎn),則不必“順藤摸瓜”,直接鏈接即可。(4) S->next=P->next;(1) P->next=S;(11) P=L;(8) while(P->next!=Q)P=P->next;(10) P=Q;(4) S->next=P->next;P->next=S;3. 編寫程序,將若干整數(shù)從鍵盤輸入,以單鏈表形式存儲起來,然后計(jì)算單鏈表中結(jié)點(diǎn)的個(gè)數(shù)(其中指針P指向該鏈表的第一個(gè)結(jié)點(diǎn))。 解:編寫C程序如下全局變量及函數(shù)提前說明:#include<stdio.h>#include<stdlib.h>typedef struct liuyuint data;struct liuyu*link;test;liuyu *p,*q,*r,*head;int m=sizeof(test);void main () /*第一步,從鍵盤輸入整數(shù),不斷添加到鏈表*/int i;head=(test*)malloc(m); /*m=sizeof(test);*/p=head; i=0;while (i!=-9999) printf("/ninput an integer stop by -9999:");scanf("%d",&i);p->data=i; /* input data is saved */p->link=(test*)malloc(m); /*m=sizeof(test);*/q=p;p=p->link;q->link=NULL; /*原先用p->link=NULL似乎太晚!*/ p=head; i=0; /*統(tǒng)計(jì)鏈表結(jié)點(diǎn)的個(gè)數(shù)并打印出來*/while (p->link!=NULL)printf("%d",p->data);p=p->link;i+;printf("n node number=%dn", i-1); /*結(jié)點(diǎn)的個(gè)數(shù)不包括-9999*/第三章 棧和隊(duì)列一、填空題1.向量、棧和隊(duì)列都是 線性 結(jié)構(gòu),可以在向量的 任何 位置插入和刪除元素;對于棧只能在 棧頂 插入和刪除元素;對于隊(duì)列只能在 隊(duì)尾 插入和 隊(duì)首 刪除元素。2. 棧是一種特殊的線性表,允許插入和刪除運(yùn)算的一端稱為 棧頂 。不允許插入和刪除運(yùn)算的一端稱為 棧底 。3. 隊(duì)列 是被限定為只能在表的一端進(jìn)行插入運(yùn)算,在表的另一端進(jìn)行刪除運(yùn)算的線性表。4. 在一個(gè)循環(huán)隊(duì)列中,隊(duì)首指針指向隊(duì)首元素的 前一個(gè) 位置。5. 在具有n個(gè)單元的循環(huán)隊(duì)列中,隊(duì)滿時(shí)共有 n-1 個(gè)元素。6. 向棧中壓入元素的操作是先 移動棧頂指針 ,后 存入元素 。7. 從循環(huán)隊(duì)列中刪除一個(gè)元素時(shí),其操作是 先 移動隊(duì)首指針 ,后 取出元素 。8.帶表頭結(jié)點(diǎn)的空循環(huán)雙向鏈表的長度等于 0 。L=head頭結(jié)點(diǎn)R=headhead解:二、 判斷正誤( )1. 線性表的每個(gè)結(jié)點(diǎn)只能是一個(gè)簡單類型,而鏈表的每個(gè)結(jié)點(diǎn)可以是一個(gè)復(fù)雜類型。 錯(cuò),線性表是邏輯結(jié)構(gòu)概念,可以順序存儲或鏈?zhǔn)酱鎯Γc元素?cái)?shù)據(jù)類型無關(guān)。( )2. 在表結(jié)構(gòu)中最常用的是線性表,棧和隊(duì)列不太常用。 錯(cuò),不一定吧?調(diào)用子程序或函數(shù)常用,CPU中也用隊(duì)列。( )3. 棧是一種對所有插入、刪除操作限于在表的一端進(jìn)行的線性表,是一種后進(jìn)先出型結(jié)構(gòu)。( )4. 對于不同的使用者,一個(gè)表結(jié)構(gòu)既可以是棧,也可以是隊(duì)列,也可以是線性表。 正確,都是線性邏輯結(jié)構(gòu),棧和隊(duì)列其實(shí)是特殊的線性表,對運(yùn)算的定義略有不同而已。( )5. 棧和鏈表是兩種不同的數(shù)據(jù)結(jié)構(gòu)。 錯(cuò),棧是邏輯結(jié)構(gòu)的概念,是特殊殊線性表,而鏈表是存儲結(jié)構(gòu)概念,二者不是同類項(xiàng)。( )6. 棧和隊(duì)列是一種非線性數(shù)據(jù)結(jié)構(gòu)。 錯(cuò),他們都是線性邏輯結(jié)構(gòu),棧和隊(duì)列其實(shí)是特殊的線性表,對運(yùn)算的定義略有不同而已。( )7. 棧和隊(duì)列的存儲方式既可是順序方式,也可是鏈接方式。 ( )8. 兩個(gè)棧共享一片連續(xù)內(nèi)存空間時(shí),為提高內(nèi)存利用率,減少溢出機(jī)會,應(yīng)把兩個(gè)棧的棧底分別設(shè)在這片內(nèi)存空間的兩端。 ( )9. 隊(duì)是一種插入與刪除操作分別在表的兩端進(jìn)行的線性表,是一種先進(jìn)后出型結(jié)構(gòu)。 錯(cuò),后半句不對。( )10. 一個(gè)棧的輸入序列是12345,則棧的輸出序列不可能是12345。 錯(cuò),有可能。三、 單項(xiàng)選擇題( B )1.棧中元素的進(jìn)出原則是 先進(jìn)先出 后進(jìn)先出 ??談t進(jìn) 棧滿則出( C )2.若已知一個(gè)棧的入棧序列是1,2,3,n,其輸出序列為p1,p2,p3,pn,若p1=n,則pi為 i n=i n-i+1 不確定解釋:當(dāng)p1=n,即n是最先出棧的,根據(jù)棧的原理,n必定是最后入棧的(事實(shí)上題目已經(jīng)表明了),那么輸入順序必定是1,2,3,n,則出棧的序列是n,3,2,1。(若不要求順序出棧,則輸出序列不確定)( B )3.判定一個(gè)棧ST(最多元素為m0)為空的條件是ST->top<>0 ST->top=0 ST->top<>m0 ST->top=m0( A )4.判定一個(gè)隊(duì)列QU(最多元素為m0)為滿隊(duì)列的條件是QU->rear QU->front = = m0 QU->rear QU->front 1= = m0 QU->front = = QU->rear QU->front = = QU->rear+1解:隊(duì)滿條件是元素個(gè)數(shù)為m0。由于約定滿隊(duì)時(shí)隊(duì)首指針與隊(duì)尾指針相差1,所以不必再減1了,應(yīng)當(dāng)選A。當(dāng)然,更正確的答案應(yīng)該取模,即:QU->front = = (QU->rear+1)% m0( D )5數(shù)組用來表示一個(gè)循環(huán)隊(duì)列,為當(dāng)前隊(duì)列頭元素的前一位置,為隊(duì)尾元素的位置,假定隊(duì)列中元素的個(gè)數(shù)小于,計(jì)算隊(duì)列中元素的公式為()rf; ()(nfr)% n; ()nrf; ()(nrf)% n6. 從供選擇的答案中,選出應(yīng)填入下面敘述 ? 內(nèi)的最確切的解答,把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。設(shè)有4個(gè)數(shù)據(jù)元素a1、a2、a3和a4,對他們分別進(jìn)行棧操作或隊(duì)操作。在進(jìn)?;蜻M(jìn)隊(duì)操作時(shí),按a1、a2、a3、a4次序每次進(jìn)入一個(gè)元素。假設(shè)?;蜿?duì)的初始狀態(tài)都是空?,F(xiàn)要進(jìn)行的棧操作是進(jìn)棧兩次,出棧一次,再進(jìn)棧兩次,出棧一次;這時(shí),第一次出棧得到的元素是 A ,第二次出棧得到的元素是 B 是;類似地,考慮對這四個(gè)數(shù)據(jù)元素進(jìn)行的隊(duì)操作是進(jìn)隊(duì)兩次,出隊(duì)一次,再進(jìn)隊(duì)兩次,出隊(duì)一次;這時(shí),第一次出隊(duì)得到的元素是 C ,第二次出隊(duì)得到的元素是 D 。經(jīng)操作后,最后在棧中或隊(duì)中的元素還有 E 個(gè)。供選擇的答案:AD:a1 a2 a3 a4E: 1 2 3 0答:ABCDE2, 4, 1, 2, 27.從供選擇的答案中,選出應(yīng)填入下面敘述 ? 內(nèi)的最確切的解答,把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。棧是一種線性表,它的特點(diǎn)是 A 。設(shè)用一維數(shù)組A1,n來表示一個(gè)棧,An為棧底,用整型變量T指示當(dāng)前棧頂位置,AT為棧頂元素。往棧中推入(PUSH)一個(gè)新元素時(shí),變量T的值 B ;從棧中彈出(POP)一個(gè)元素時(shí),變量T的值 C 。設(shè)棧空時(shí),有輸入序列a,b,c,經(jīng)過PUSH,POP,PUSH,PUSH,POP操作后,從棧中彈出的元素的序列是 D ,變量T的值是 E 。供選擇的答案:A: 先進(jìn)先出 后進(jìn)先出 進(jìn)優(yōu)于出 出優(yōu)于進(jìn) 隨機(jī)進(jìn)出B,C: 加1 減1 不變 清0 加2 減2D: a,b b,c c,ab,a c,b a,cE: n+1 n+2 n n-1 n-2答案:ABCDE=2, 2, 1, 6, 4注意,向地址的高端生長,稱為向上生成堆棧;向地址低端生長叫向下生成堆棧,本題中底部為n,向地址的低端遞減生成,稱為向下生成堆棧。8.從供選擇的答案中,選出應(yīng)填入下面敘述 ? 內(nèi)的最確切的解答,把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。在做進(jìn)棧運(yùn)算時(shí),應(yīng)先判別棧是否 A ;在做退棧運(yùn)算時(shí),應(yīng)先判別棧是否 B 。當(dāng)棧中元素為n個(gè),做進(jìn)棧運(yùn)算時(shí)發(fā)生上溢,則說明該棧的最大容量為 C 。為了增加內(nèi)存空間的利用率和減少溢出的可能性,由兩個(gè)棧共享一片連續(xù)的內(nèi)存空間時(shí),應(yīng)將兩棧的 D 分別設(shè)在這片內(nèi)存空間的兩端,這樣,只有當(dāng) E 時(shí),才產(chǎn)生上溢。供選擇的答案:A,B:空 滿 上溢 下溢C: n-1 n n+1 n/2D: 長度 深度 棧頂 棧底E:兩個(gè)棧的棧頂同時(shí)到達(dá)??臻g的中心點(diǎn) 其中一個(gè)棧的棧頂?shù)竭_(dá)??臻g的中心點(diǎn) 兩個(gè)棧的棧頂在達(dá)棧空間的某一位置相遇 兩個(gè)棧均不空,且一個(gè)棧的棧頂?shù)竭_(dá)另一個(gè)棧的棧底答案:ABCDE2, 1, 2, 4, 3四、簡答題1.說明線性表、棧與隊(duì)的異同點(diǎn)。答:相同點(diǎn):都是線性結(jié)構(gòu),都是邏輯結(jié)構(gòu)的概念。都可以用順序存儲或鏈表存儲;棧和隊(duì)列是兩種特殊的線性表,即受限的線性表,只是對插入、刪除運(yùn)算加以限制。不同點(diǎn):運(yùn)算規(guī)則不同,線性表為隨機(jī)存取,而棧是只允許在一端進(jìn)行插入、刪除運(yùn)算,因而是后進(jìn)先出表LIFO;隊(duì)列是只允許在一端進(jìn)行插入、另一端進(jìn)行刪除運(yùn)算,因而是先進(jìn)先出表FIFO。 用途不同,堆棧用于子程調(diào)用和保護(hù)現(xiàn)場,隊(duì)列用于多道作業(yè)處理、指令寄存及其他運(yùn)算等等。2.設(shè)有編號為1,2,3,4的四輛列車,順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的車站,具體寫出這四輛列車開出車站的所有可能的順序。答:至少有14種。 全進(jìn)之后再出情況,只有1種:4,3,2,1 進(jìn)3個(gè)之后再出的情況,有3種,3,4,2,1 3,2,4,1 3,2,1,4 進(jìn)2個(gè)之后再出的情況,有5種,2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 進(jìn)1個(gè)之后再出的情況,有5種,1,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,33.假設(shè)正讀和反讀都相同的字符序列為“回文”,例如,abba和abcba是回文,abcde 和ababab則不是回文。假設(shè)一字符序列已存入計(jì)算機(jī),請分析用線性表、堆棧和隊(duì)列等方式正確輸出其回文的可能性?答:線性表是隨機(jī)存儲,可以實(shí)現(xiàn),靠循環(huán)變量(j-)從表尾開始打印輸出;堆棧是后進(jìn)先出,也可以實(shí)現(xiàn),靠正序入棧、逆序出棧即可;隊(duì)列是先進(jìn)先出,不易實(shí)現(xiàn)。哪種方式最好,要具體情況具體分析。若正文在機(jī)內(nèi)已是順序存儲,則直接用線性表從后往前讀取即可,或?qū)⒍褩m旈_到數(shù)組末尾,然后直接用POP動作實(shí)現(xiàn)。(但堆棧是先減后壓還是)若正文是單鏈表形式存儲,則等同于隊(duì)列,需開輔助空間,可以從鏈?zhǔn)组_始入棧,全部壓入后再依次輸出。4.順序隊(duì)的“假溢出”是怎樣產(chǎn)生的?如何知道循環(huán)隊(duì)列是空還是滿?答:一般的一維數(shù)組隊(duì)列的尾指針已經(jīng)到了數(shù)組的上界,不能再有入隊(duì)操作,但其實(shí)數(shù)組中還有空位置,這就叫“假溢出”。采用循環(huán)隊(duì)列是解決假溢出的途徑。另外,解決隊(duì)滿隊(duì)空的辦法有三: 設(shè)置一個(gè)布爾變量以區(qū)別隊(duì)滿還是隊(duì)空; 浪費(fèi)一個(gè)元素的空間,用于區(qū)別隊(duì)滿還是隊(duì)空。 使用一個(gè)計(jì)數(shù)器記錄隊(duì)列中元素個(gè)數(shù)(即隊(duì)列長度)。我們常采用法,即隊(duì)頭指針、隊(duì)尾指針中有一個(gè)指向?qū)嵲兀硪粋€(gè)指向空閑元素。判斷循環(huán)隊(duì)列隊(duì)空標(biāo)志是: f=rear 隊(duì)滿標(biāo)志是:f=(r+1)%N5.設(shè)循環(huán)隊(duì)列的容量為40(序號從0到39),現(xiàn)經(jīng)過一系列的入隊(duì)和出隊(duì)運(yùn)算后,有 front=11,rear=19; front=19,rear=11;問在這兩種情況下,循環(huán)隊(duì)列中各有元素多少個(gè)?答:用隊(duì)列長度計(jì)算公式: (Nrf)% N L=(401911)% 40=8 L=(401119)% 40=32五、閱讀理解按照四則運(yùn)算加、減、乘、除和冪運(yùn)算()優(yōu)先關(guān)系的慣例,并仿照教材例3-2的格式,畫出對下列算術(shù)表達(dá)式求值時(shí)操作數(shù)棧和運(yùn)算符棧的變化過程:ABC/D+EF1. 寫出下列程序段的輸出結(jié)果(棧的元素類型SElem Type為char)。void main( )Stack S;Char x,y;InitStack(S);x=c;y=k;Push(S,x); Push(S,a); Push(S,y);Pop(S,x); Push(S,t); Push(S,x);Pop(S,x); Push(S,s);while(!StackEmpty(S) Pop(S,y);printf(y); ;Printf(x);答:輸出為“stack”。2. 寫出下列程序段的輸出結(jié)果(隊(duì)列中的元素類型QElem Type為char)。void main( )Queue Q; Init Queue (Q);Char x=e; y=c;EnQueue (Q,h); EnQueue (Q,r); EnQueue (Q, y);DeQueue (Q,x); EnQueue (Q,x); DeQueue (Q,x); EnQueue (Q,a); while(!QueueEmpty(Q) DeQueue (Q,y);printf(y); ;Printf(x);答:輸出為“char”。3. 簡述以下算法的功能(棧和隊(duì)列的元素類型均為int)。void algo3(Queue &Q)Stack S; int d;InitStack(S);while(!QueueEmpty(Q) DeQueue (Q,d); Push(S,d);while(!StackEmpty(S) Pop(S,d); EnQueue (Q,d); 六、試寫一個(gè)算法判別讀入的一個(gè)以為結(jié)束符的字符序列是否是“回文”。答: int Palindrome_Test()/判別輸入的字符串是否回文序列,是則返回1,否則返回0InitStack(S);InitQueue(Q);while(c=getchar()!=)Push(S,c);EnQueue(Q,c); /同時(shí)使用棧和隊(duì)列兩種結(jié)構(gòu)while(!StackEmpty(S)Pop(S,a);DeQueue(Q,b);if(a!=b) return ERROR;return OK;/Palindrome_Test 第四五章 串和數(shù)組一、填空題1. 不包含任何字符(長度為0)的串 稱為空串; 由一個(gè)或多個(gè)空格(僅由空格符)組成的串 稱為空白串。2. 設(shè)S=“A;/document/Mary.doc”,則strlen(s)= 20 , “/”的字符定位的位置為 3 。3. 子串的定位運(yùn)算稱為串的模式匹配; 被匹配的主串 稱為目標(biāo)串, 子串 稱為模式。4. 設(shè)目標(biāo)T=”abccdcdccbaa”,模式P=“cdcc”,則第 6 次匹配成功。5. 若n為主串長,m為子串長,則串的古典(樸素)匹配算法最壞的情況下需要比較字符的總次數(shù)為 (n-m+1)*m 。6. 假設(shè)有二維數(shù)組A68,每個(gè)元素用相鄰的6個(gè)字節(jié)存儲,存儲器按字節(jié)編址。已知A的起始存儲位置(基地址)為1000,則數(shù)組A的體積(存儲量)為 288 B ;末尾元素A57的第一個(gè)字節(jié)地址為 1282 ;若按行存儲時(shí),元素A14的第一個(gè)字節(jié)地址為 (8+4)6+1000=1072 ;若按列存儲時(shí),元素A47的第一個(gè)字節(jié)地址為 (674)61000)1276 。(注:數(shù)組是從0行0列還是從1行1列計(jì)算起呢?由末單元為A57可知,是從0行0列開始!)7. 設(shè)數(shù)組a160, 170的基地址為2048,每個(gè)元素占2個(gè)存儲單元,若以列序?yàn)橹餍蝽樞虼鎯Γ瑒t元素a32,58的存儲地址為 8950。答:不考慮0行0列,利用列優(yōu)先公式: LOC(aij)=LOC(ac1,c2)+(j-c2)*(d1-c1+1)+i-c1)*L得:LOC(a32,58)=2048+(58-1)*(60-1+1)+32-1*289508. 三元素組表中的每個(gè)結(jié)點(diǎn)對應(yīng)于稀疏矩陣的一個(gè)非零元素,它包含有三個(gè)數(shù)據(jù)項(xiàng),分別表示該元素的 行下標(biāo) 、 列下標(biāo) 和 元素值 。9.求下列廣義表操作的結(jié)果:(1) GetHead【(a,b),(c,d)】= (a, b) ; /頭元素不必加括號(2) GetHead【GetTail【(a,b),(c,d)】= (c,d) ;(3) GetHead【GetTail【GetHead【(a,b),(c,d)】= b ;(4) GetTail【GetHead【GetTail【(a,b),(c,d)】= (d) ;二、單選題( B )1. 串是一種特殊的線性表,其特殊性體現(xiàn)在: 可以順序存儲 數(shù)據(jù)元素是一個(gè)字符 可以鏈?zhǔn)酱鎯?數(shù)據(jù)元素可以是多個(gè)字符( B )2. 設(shè)有兩個(gè)串p和q,求q在p中首次出現(xiàn)的位置的運(yùn)算稱作: 連接 模式匹配 求子串 求串長( D )3. 設(shè)串s1=ABCDEFG,s2=PQRST,函數(shù)con(x,y)返回x和y串的連接串,subs(s, i, j)返回串s的從序號i開始的j個(gè)字符組成的子串,len(s)返回串s的長度,則con(subs(s1, 2, len(s2), subs(s1, len(s2), 2)的結(jié)果串是:BCDEF BCDEFG BCPQRST BCDEFEF解:con(x,y)返回x和y串的連接串,即 con(x,y)ABCDEFGPQRST;subs(s, i, j)返回串s的從序號i開始的j個(gè)字符組成的子串,則subs(s1, 2, len(s2)subs(s1, 2, 5)= BCDEF; subs(s1, len(s2), 2)subs(s1, 5, 2)= EF;所以con(subs(s1, 2, len(s2), subs(s1, len(s2), 2)con( BCDEF, EF)之連接,即BCDEFEF( A )4. 假設(shè)有60行70列的二維數(shù)組a160, 170以列序?yàn)橹餍蝽樞虼鎯?,其基地址?0000,每個(gè)元素占2個(gè)存儲單元,那么第32行第58列的元素a32,58的存儲地址為 。(無第0行第0列元素) 16902 16904 14454 答案A, B, C均不對答:此題與填空題第8小題相似。(57列60行31行)2字節(jié)10000=16902( B )5. 設(shè)矩陣A是一個(gè)對稱矩陣,為了節(jié)省存儲,將其下三角部分(如下圖所示)按行序存放在一維數(shù)組B 1, n(n-1)/2 中,對下三角部分中任一元素ai,j(ij), 在一維數(shù)組B中下標(biāo)k的值是:i(i-1)/2+j-1 i(i-1)/2+j i(i+1)/2+j-1 i(i+1)/2+j解:注意B的下標(biāo)要求從1開始。先用第一個(gè)元素去套用,可能有B和C;再用第二個(gè)元素去套用B和C,B=2而C3(不符);所以選B6. 從供選擇的答案中,選出應(yīng)填入下面敘述 ? 內(nèi)的最確切的解答,把相應(yīng)編號寫在答卷的對應(yīng)欄內(nèi)。有一個(gè)二維數(shù)組A,行下標(biāo)的范圍是0到8,列下標(biāo)的范圍是1到5,每個(gè)數(shù)組元素用相鄰的4個(gè)字節(jié)存儲。存儲器按字節(jié)編址。假設(shè)存儲數(shù)組元素A0,1的第一個(gè)字節(jié)的地址是0。存儲數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是 A 。若按行存儲,則A3,5和A5,3的第一個(gè)字節(jié)的地址分別是 B 和 C 。若按列存儲,則A7,1和A2,4的第一個(gè)字節(jié)的地址分別是 D 和 E 。供選擇的答案:AE:28 44 76 92 108 116 132 176 184 188答案:ABCDE=8, 3, 5, 1, 67.有一個(gè)二維數(shù)組A,行下標(biāo)的范圍是1到6,列下標(biāo)的范圍是0到7,每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲,存儲器按字節(jié)編址。那么,這個(gè)數(shù)組的體積是 A 個(gè)字節(jié)。假設(shè)存儲數(shù)組元素A1,0的第一個(gè)字節(jié)的地址是0,則存儲數(shù)組A的最后一個(gè)元素的第一個(gè)字節(jié)的地址是 B 。若按行存儲,則A2,4的第一個(gè)字節(jié)的地址是 C 。若按列存儲,則A5,7的第一個(gè)字節(jié)的地址是 D 。供選擇的答案AD:12 66 72 96 114 120 156 234 276 282 (11)283 (12)288答案:ABCD=12, 10, 3, 9三、簡答題1. KMP算法的設(shè)計(jì)思想是什么?它有什么優(yōu)點(diǎn)?答:其設(shè)計(jì)思想是,利用已經(jīng)部分匹配的結(jié)果來加快模式串的滑動速度。主要優(yōu)點(diǎn)有二:一是在模式與主串已經(jīng)部分匹配的情況下,可以大大加快匹配速度;二是主串指針不回溯,可以使外設(shè)文件邊讀入邊匹配。2. 已知二維數(shù)組Am,m采用按行優(yōu)先順序存放,每個(gè)元素占K個(gè)存儲單元,并且第一個(gè)元素的存儲地址為Loc(a11),請寫出求Loc(aij)的計(jì)算公式。如果采用列優(yōu)先順序存放呢?解:公式教材已給出,此處雖是方陣,但行列公式仍不相同;按行存儲的元素地址公式是: Loc(aij)= Loc(a11) + (i-1)*m+(j-1) * K按列存儲的元素地址公式是: Loc(aij)= Loc(a11) + (j-1)*m+(i-1) * K3.遞歸算法比非遞歸算法花費(fèi)更多的時(shí)間,對嗎?為什么?答:不一定。時(shí)間復(fù)雜度與樣本個(gè)數(shù)n有關(guān),是指最深層的執(zhí)行語句耗費(fèi)時(shí)間,而遞歸算法與非遞歸算法在最深層的語句執(zhí)行上是沒有區(qū)別的,循環(huán)的次數(shù)也沒有太大差異。僅僅是確定循環(huán)是否繼續(xù)的方式不同,遞歸用棧隱含循環(huán)次數(shù),非遞歸用循環(huán)變量來顯示循環(huán)次數(shù)而已。四、計(jì)算題1. 設(shè)s=I AM A STUDENT, t=GOOD, q=WORKER, 求Replace(s,STUDENT,q) 和Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)。解: Replace(s,STUDENT,q)I AM A WORKER 因?yàn)?SubString(s,6,2)A ;SubString(s,7,8) STUDENTConcat(t,SubString(s,7,8)GOOD STUDENT所以Concat(SubString(s,6,2), Concat(t,SubString(s,7,8)A GOOD STUDENT2.已知主串s=ADBADABBAABADABBADADA,模式串pat=ADABBADADA。寫出模式串的nextval函數(shù)值,并由此畫出KMP算法匹配的全過程。解:(由演示程序得知)nextval函數(shù)值為0 1 0 2 1 0 1 0 4 0 在第12個(gè)字符處發(fā)現(xiàn)匹配!s=ADBADABBAABADABBADADApat=ADABBADADA3.用三元組表表示下列稀疏矩陣: 解:參見填空題4. 三元素組表中的每個(gè)結(jié)點(diǎn)對應(yīng)于稀疏矩陣的一個(gè)非零元素,它包含有三個(gè)數(shù)據(jù)項(xiàng),分別表示該元素的 行下標(biāo) 、 列下標(biāo) 和 元素值 。所以(1)可列表為: (2)可列表為:8866416-225943565353233685467858124. 下列各

注意事項(xiàng)

本文(數(shù)據(jù)結(jié)構(gòu)習(xí)題集與實(shí)驗(yàn)指導(dǎo))為本站會員(jun****875)主動上傳,裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對上載內(nèi)容本身不做任何修改或編輯。 若此文所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng)(點(diǎn)擊聯(lián)系客服),我們立即給予刪除!

溫馨提示:如果因?yàn)榫W(wǎng)速或其他原因下載失敗請重新下載,重復(fù)下載不扣分。




關(guān)于我們 - 網(wǎng)站聲明 - 網(wǎng)站地圖 - 資源地圖 - 友情鏈接 - 網(wǎng)站客服 - 聯(lián)系我們

copyright@ 2023-2025  zhuangpeitu.com 裝配圖網(wǎng)版權(quán)所有   聯(lián)系電話:18123376007

備案號:ICP2024067431-1 川公網(wǎng)安備51140202000466號


本站為文檔C2C交易模式,即用戶上傳的文檔直接被用戶下載,本站只是中間服務(wù)平臺,本站所有文檔下載所得的收益歸上傳人(含作者)所有。裝配圖網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對上載內(nèi)容本身不做任何修改或編輯。若文檔所含內(nèi)容侵犯了您的版權(quán)或隱私,請立即通知裝配圖網(wǎng),我們立即給予刪除!