版權(quán)說(shuō)明:本文檔由用戶(hù)提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、1數(shù)據(jù)結(jié)構(gòu)習(xí)題數(shù)據(jù)結(jié)構(gòu)習(xí)題一、一、名詞解釋名詞解釋1.數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)的邏輯結(jié)構(gòu)、數(shù)據(jù)物理結(jié)構(gòu)、順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)、算法、時(shí)間復(fù)雜度、空間復(fù)雜度。2.線(xiàn)性表、順序表、單鏈表、雙向鏈表、循環(huán)鏈表、雙向循環(huán)鏈表、三個(gè)概念的區(qū)別:頭指針、頭結(jié)點(diǎn)、首元結(jié)點(diǎn)(第1個(gè)元素結(jié)點(diǎn))。3.棧(順序棧、鏈棧)、隊(duì)列(順序隊(duì)、鏈隊(duì))、循環(huán)隊(duì)列、遞歸、稀疏矩陣、三元組。4.樹(shù)、葉子結(jié)點(diǎn)、結(jié)點(diǎn)的度、樹(shù)的度、樹(shù)的高(深)度、二叉樹(shù)、遍歷、滿(mǎn)二
2、叉樹(shù)、完全二叉樹(shù)、哈夫曼樹(shù)、WPL、哈夫曼編碼。5.圖(有向、無(wú)向)、網(wǎng)、邊、弧、度、入度、出度、完全圖(有向、無(wú)向)、(強(qiáng))連通圖(分量)、(最?。┥蓸?shù)、鄰接矩陣、鄰接表、DFS、BFS。6.查找表、關(guān)鍵字、靜態(tài)查找、動(dòng)態(tài)查找、ASL、順序查找、折半查找、分塊查找、二叉排序樹(shù)。7、排序、內(nèi)(外)排序、穩(wěn)定性、插入(直接、希爾),交換(起泡、快速),選擇(直接、堆),2路歸并。一、一、填空題填空題1.數(shù)據(jù)結(jié)構(gòu)是研究數(shù)據(jù)的_邏輯結(jié)構(gòu)__
3、和___物理結(jié)構(gòu)__,并在這種結(jié)構(gòu)上定義相關(guān)的運(yùn)算,設(shè)計(jì)實(shí)現(xiàn)這些運(yùn)算的算法,分析算法的效率。算法的效率包括時(shí)間和空間兩個(gè)方面,分別稱(chēng)為_(kāi)__時(shí)間復(fù)雜度____和__空間復(fù)雜度___。2.數(shù)據(jù)的基本單位是__數(shù)據(jù)元素__,數(shù)據(jù)的最小單位是__數(shù)據(jù)項(xiàng)_。3.算法是對(duì)特定問(wèn)題求解___步驟___的一種描述,是指令的有限序列。4.一個(gè)算法的時(shí)間復(fù)雜度為(3n32n—7),其數(shù)量級(jí)表示為O(n3)_。5.一個(gè)算法具有5個(gè)特性:確定性、可行性、有窮
4、性、輸入和輸出。6.算法性能的分析和度量,可以從算法的時(shí)間復(fù)雜度和空間復(fù)雜度來(lái)評(píng)價(jià)算法的優(yōu)劣。7.數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合結(jié)構(gòu)、線(xiàn)性結(jié)構(gòu)、樹(shù)形結(jié)構(gòu)和圖型結(jié)構(gòu)四種類(lèi)型。8.數(shù)據(jù)結(jié)構(gòu)在計(jì)算機(jī)中的表示稱(chēng)為數(shù)據(jù)的物理結(jié)構(gòu),它可以采用__順序存儲(chǔ)___或__鏈?zhǔn)酱鎯?chǔ)_兩種存儲(chǔ)方法。9.線(xiàn)性表有兩種存儲(chǔ)結(jié)構(gòu),分別為順序存儲(chǔ)和鏈?zhǔn)酱鎯?chǔ)。10.鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是利用指針來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系。11.若頻繁地對(duì)線(xiàn)性表進(jìn)行插入和刪除操作,該線(xiàn)性表宜采用_
5、鏈?zhǔn)酱鎯?chǔ)__存儲(chǔ)結(jié)構(gòu)。12.線(xiàn)性表中的數(shù)據(jù)元素之間具有一對(duì)一的線(xiàn)性關(guān)系,除第一個(gè)和最后一個(gè)元素外,其他數(shù)據(jù)元素有且只有一個(gè)直接后繼和直接前趨。13.在一個(gè)單鏈表中p所指結(jié)點(diǎn)之后插入一個(gè)s所指結(jié)點(diǎn)時(shí),應(yīng)執(zhí)行snext=__pnext______和pnext=__s______的操作。14.在一個(gè)單鏈表中刪除p的后繼結(jié)點(diǎn)q時(shí),應(yīng)執(zhí)行以下操作pnext=qnext。15.對(duì)帶頭結(jié)點(diǎn)head的單鏈表,則判斷其為空的條件為headnext=NUL
6、L。學(xué)號(hào)姓名學(xué)號(hào)339.若深度為6的完全二叉樹(shù)的第6層有3個(gè)葉結(jié)點(diǎn),則該二叉樹(shù)一共有34個(gè)結(jié)點(diǎn)。40.深度為15的滿(mǎn)二叉樹(shù)上,第11層有_2^(111)=1024個(gè)結(jié)點(diǎn)。41.一棵具有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù),它的深度為7,其中度為1的結(jié)點(diǎn)有1個(gè)。42.某二叉樹(shù)的后根遍歷序列為abd,中根遍歷序列為adb,則它的先根遍歷序列為dab。43.哈夫曼樹(shù)是指對(duì)于一組帶有確定權(quán)值的葉子結(jié)點(diǎn)構(gòu)造的具有最小帶權(quán)路徑長(zhǎng)度的二叉樹(shù)。44.具有m個(gè)葉子結(jié)
7、點(diǎn)的哈夫曼樹(shù)共有2m1個(gè)結(jié)點(diǎn)。45.已知一棵哈夫曼樹(shù)含有60個(gè)葉子結(jié)點(diǎn),則該樹(shù)中共有59個(gè)非葉子結(jié)點(diǎn)。46.在一個(gè)具有n個(gè)頂點(diǎn)無(wú)向完全圖中,含有n(n1)2邊;在一個(gè)具有n個(gè)頂點(diǎn)有向完全圖中,含有n(n1)邊。一個(gè)具有4個(gè)頂點(diǎn)的無(wú)向完全圖有6條邊。47.具有n個(gè)頂點(diǎn)的連通圖至少需有n1條邊。48.一個(gè)連通圖的生成樹(shù)是該圖的極小連通子圖。若這個(gè)連通圖有n個(gè)頂點(diǎn),則它的生成樹(shù)有n1條邊。49.在有向圖的鄰接矩陣中,第i行中非零元素的個(gè)數(shù)正好
8、是第i個(gè)頂點(diǎn)的出度;第i列中非零元素的個(gè)數(shù)正好是第i個(gè)頂點(diǎn)的入度。50.在一個(gè)圖中,所有頂點(diǎn)的度數(shù)之和等于所有邊數(shù)的2倍。51.在無(wú)向圖G的鄰接矩陣A中,若A[i][j]等于1,則A[j][i]等于1。52.對(duì)二叉排序樹(shù)進(jìn)行中序遍歷,可以得到按關(guān)鍵字從小到大排列的結(jié)點(diǎn)序列。53.一個(gè)有序表為1,3,9,12,32,41,45,62,75,77,82,95,100,當(dāng)折半查找值為82的結(jié)點(diǎn)時(shí),經(jīng)過(guò)4次比較后查找成功。54.在線(xiàn)性表中采用折
9、半查找法查找一個(gè)數(shù)據(jù)元素,線(xiàn)性表中元素應(yīng)該按值有序,并且采用___順序存儲(chǔ)__存儲(chǔ)方法。55.在簡(jiǎn)單選擇排序、堆排序、快速排列、歸并排序四種排序方法中,排序方法穩(wěn)定的是__歸并排序。56.冒泡排序是一種穩(wěn)定的排序方法,對(duì)n個(gè)元素的序列進(jìn)行冒泡排序時(shí),最多需進(jìn)行n1趟。該排序方法的時(shí)間復(fù)雜度為O(n2)。57.給定序列100,86,48,73,35,39,42,57,66,21,按堆的定義,則它一定大根堆。58.數(shù)據(jù)結(jié)構(gòu)是指數(shù)據(jù)及其相互之
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶(hù)所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶(hù)上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶(hù)上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶(hù)因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)題答案
- 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題附答案
- 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題a
- 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題及答案12級(jí)
- 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題
- 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題目
- whut數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題
- 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題目
- 數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題2
- 數(shù)據(jù)結(jié)構(gòu)與算法分析—期末復(fù)習(xí)題及答案
- 廣工2015數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題目及答案
- 數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)題
- 4《數(shù)據(jù)結(jié)構(gòu)導(dǎo)論》復(fù)習(xí)題
- 數(shù)據(jù)結(jié)構(gòu)期末總復(fù)習(xí)題
- 數(shù)據(jù)結(jié)構(gòu)與算法復(fù)習(xí)題
- 數(shù)據(jù)結(jié)構(gòu)算法設(shè)計(jì)題復(fù)習(xí)題
- 數(shù)據(jù)結(jié)構(gòu)習(xí)題及答案
- 《數(shù)據(jù)結(jié)構(gòu)》習(xí)題及答案
- 數(shù)據(jù)結(jié)構(gòu)與算法分析六套期末復(fù)習(xí)題含答案
- 算法與數(shù)據(jù)結(jié)構(gòu)重考復(fù)習(xí)題(0910)79
評(píng)論
0/150
提交評(píng)論