第二次單元測試題庫(串到樹)(1)_第1頁
第二次單元測試題庫(串到樹)(1)_第2頁
第二次單元測試題庫(串到樹)(1)_第3頁
已閱讀5頁,還剩12頁未讀, 繼續(xù)免費(fèi)閱讀

下載本文檔

版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報或認(rèn)領(lǐng)

文檔簡介

1、PAGE1 / NUMPAGES17一、判斷題四串1、確定串在串中首次出現(xiàn)的位置的操作稱為串的模式匹配。()2、如果一個串中的所有字符均在另一串中出現(xiàn),則說前者是后者的子串。()3、一個任意串是其自身的子串。()1、2、3、五數(shù)組和廣義表1、多維數(shù)組是向量的推廣。()/*數(shù)組和廣義表線性表在含義上的擴(kuò)展*/2、用相鄰矩陣表示圖所用的存儲空間大小與圖的邊數(shù)成正比。()/*頂點(diǎn)*/3、除插入和刪除操作外,數(shù)組的主要操作還有存取、修改、檢索和排序等。()4、稀疏矩陣中0元素的分布有規(guī)律,因此可以采用三元組方法進(jìn)行壓縮存儲。()/*稀疏矩陣中0元素的分布無規(guī)律*/5.如果采用如下方式定義一維字符數(shù)組:

2、constintmaxSize=30;/*常變量在程序運(yùn)行中不能進(jìn)行修改*/charamaxSize;則這種數(shù)組在程序執(zhí)行過程中不能擴(kuò)充。6.如果采用如下方法定義一維字符數(shù)組:intmaxSize=30;char*a=newcharmaxSize;則這種數(shù)組在程序執(zhí)行過程中不能擴(kuò)充。7.數(shù)組是一種靜態(tài)的存儲空間分配,就是說,在程序設(shè)計時必須預(yù)先定義數(shù)組的數(shù)據(jù)類型和存儲空間大小,由編譯程序在編譯時進(jìn)行分配。/*對于數(shù)組一旦規(guī)定了它的維數(shù)和各維長度,便可1為它分配存儲空間*/8.多維數(shù)組是一種復(fù)雜的數(shù)據(jù)結(jié)構(gòu),數(shù)組元素之間的關(guān)系既不是線性的也不是樹形的。9.使用三元組表示稀疏矩陣中的非零元素能節(jié)省存

3、儲空間。10.用字符數(shù)組存儲長度為n的字符串,數(shù)組長度至少為n+1。1-56-1011、一個廣義表的深度是指該廣義表展開后所含括號的層數(shù)。()12.一個廣義表的表頭總是一個廣義表。()13.一個廣義表的表尾總是一個表。()14.一個廣義表(a),(b),c),(d)的長度為3,深度為4。()15.一個廣義表(a),(b),c),(d)的表尾是((b),c),(d))。(129)11、12、13、14、15、六樹1、一般樹和二叉樹的結(jié)點(diǎn)數(shù)目都可以為0。()2、在只有度為0和度為k的結(jié)點(diǎn)的k叉樹中,設(shè)度為0的結(jié)點(diǎn)有n0個,度為k的結(jié)點(diǎn)有nk個,則有n0=nk+1。()3、折半搜索只適用與有序表,包

4、括有序的順序表和有序的鏈表。()4、哈夫曼樹一定是滿二叉樹。()5、給定一組權(quán)值,可以唯一構(gòu)造出一棵哈夫曼樹。()6、深度為h的非空二叉樹的第i層最多有2i-1個結(jié)點(diǎn)。()7、滿二叉樹也是完全二叉樹。()8、已知一棵二叉樹的前序序列和后序序列可以唯一地構(gòu)造出該二叉樹。()29、非空二叉排序樹的任意一棵子樹也是二叉排序樹。()10、對一棵二叉排序樹進(jìn)行前序遍歷一定可以得到一個按值有序的序列。()11、設(shè)與一棵樹T所對應(yīng)的二叉樹為BT,則與T中的葉子結(jié)點(diǎn)所對應(yīng)的BT中的結(jié)點(diǎn)也一定是葉子結(jié)點(diǎn)。()12、哈夫曼樹一定是完全二叉樹。()13、由一棵二叉樹的前序序列和后序序列可以唯一確定它。()14、在完

5、全二叉樹中,若某結(jié)點(diǎn)元左孩子,則它必是葉結(jié)點(diǎn)。()15、樹的帶權(quán)路徑長度最小的二叉樹中必定沒有度為1的結(jié)點(diǎn)。()16、二叉樹可以用0度2的有序樹來表示。()17、一組權(quán)值,可以唯一構(gòu)造出一棵哈夫曼樹。()18、將一棵樹轉(zhuǎn)換成二叉樹后,根結(jié)點(diǎn)沒有左子樹;()/*沒有右子樹*/19、用樹的前序遍歷和中序遍歷可以導(dǎo)出樹的后序遍歷;()20.二叉樹是一棵無序樹。()21.在一棵二叉樹中,假定每個結(jié)點(diǎn)只有左子女,沒有右子女,對它分別進(jìn)行前序遍歷和后序遍歷,則具有相同的結(jié)果。()22.在一棵二叉樹中,假定每個結(jié)點(diǎn)只有左子女,沒有右子女,對它分別進(jìn)行中序遍歷和后序遍歷,則具有相同的結(jié)果。()23.在一棵二叉

6、樹中,假定每個結(jié)點(diǎn)只有左子女,沒有右子女,對它分別進(jìn)行前序遍歷和中根遍歷,則具有相同的結(jié)果。()24.在一棵二叉樹中,假定每個結(jié)點(diǎn)只有左子女,沒有右子女,對它分別進(jìn)行前序遍歷和按層遍歷,則具有相同的結(jié)果。()25.在樹的存儲中,若使每個結(jié)點(diǎn)帶有指向雙親結(jié)點(diǎn)的指針,這為在算法中尋找雙親結(jié)點(diǎn)帶來方3便。()26.對于一棵具有n個結(jié)點(diǎn),其高度為h的二叉樹,進(jìn)行任一種次序遍歷的時間復(fù)雜度為O(n)。()27.對于一棵具有n個結(jié)點(diǎn),其高度為h的任何二叉樹,進(jìn)行任一種次序遍歷的時間復(fù)雜度均為O(h)。()28.對于一棵具有n個結(jié)點(diǎn)的任何二叉樹,進(jìn)行前序、中序或后序的任一種次序遍歷的空間復(fù)雜度為O(log2

7、n)。()/*log2n下取整+1*/29.在一棵具有n個結(jié)點(diǎn)的線索二叉樹中,每個結(jié)點(diǎn)的指針域可能指向子女結(jié)點(diǎn),也可能作為線索,使之指向某一種遍歷次序的前驅(qū)或后繼結(jié)點(diǎn),所有結(jié)點(diǎn)中作為線索使用的指針域共有n個。()30.線索二叉樹中的每個結(jié)點(diǎn)通常包含有5個數(shù)據(jù)成員。()1-56-1011-1516-2021-2526-30二、填空題:四串1、一個串的任意個連續(xù)的字符組成的子序列稱為該串的_子串_,包含該子串的串稱為_主串_。2、求串T在主串S中首次出現(xiàn)的位置的操作是_Index(S,T,pos)_。3、在初始為空的隊(duì)列中插入元素A,B,C,D以后,緊接著作了兩次刪除操作,此時的隊(duì)尾元素是_D_。

8、4、在長度為n的循環(huán)隊(duì)列中,刪除其節(jié)點(diǎn)為x的時間復(fù)雜度為_O(n)_。45、已知廣義表L為空,其深度為_1_。6.若設(shè)串S=“documentHash.doc0”,則該字符串S的長度為_16_。1、子串,主串2、Index(S,T,pos)3、D4、O(n)5、16.16五數(shù)組和廣義表1、已知一順序存儲的線性表,每個結(jié)點(diǎn)占用k個單元,若第一個結(jié)點(diǎn)的地址為DA1,則第i個結(jié)點(diǎn)的地址為_DA1+(i-1)*k_。2、設(shè)一行優(yōu)先順序存儲的數(shù)組A56,A00的地址為1100,且每個元素占2個存儲單元,則A23的地址為_1130_。3、設(shè)有二維數(shù)組A919,其每個元素占兩個字節(jié),第一個元素的存儲地址為1

9、00,若按行優(yōu)先順序存儲,則元素A6,6的存儲地址為_340_,按列優(yōu)順序存儲,元素A6,6的存儲地址為_220_。/*100+(6*9+6)*2*/4、假設(shè)以行為優(yōu)先存儲的三維數(shù)組A567,A000的地址為1100,每個元素占兩個存儲單元,則A432的地址為_1482_。/*1100+(4*6+3)*7+2*2*/4、設(shè)二維數(shù)組Amn按列優(yōu)先存儲,每個元素占1個存儲單元,元素A00的存儲地址loc(A00),則Aij的存儲地址loc(Aij)=_loc(A00)+j*_m+i_。6、稀疏矩陣一般采用_三元組_方法進(jìn)行壓縮存儲。7、稀疏矩陣可用_三元組_進(jìn)行壓縮存儲,存儲時需存儲非零元的_行號

10、_、_列號_、_值_。8、若矩陣中所有非零元素都集中在以主對角線為中心的帶狀區(qū)域中,區(qū)域外的值全為0,則稱為_對角矩陣_。9、若一個n階矩陣A中的元素滿足:Aij=Aji(0=I,j=j)_和_(1+j)*(j-1)/2+i(i=j)_(下標(biāo)從0開始)。11、設(shè)有一下三角形矩陣A55按行壓縮存儲到數(shù)組B中,B0的地址為100,每個元素占2個單元,則A32地址為_116_。/*3*(3+1)/2+2*2=16*/12.一維數(shù)組所占用的空間是連續(xù)的。但數(shù)組元素不一定順序存取,通常是按元素的_下標(biāo)_存取的。13.在程序運(yùn)行過程中不能擴(kuò)充的數(shù)組是_靜態(tài)_分配的數(shù)組。這種數(shù)組在聲明它時必須指定它的大小。

11、14.在程序運(yùn)行過程中可以擴(kuò)充的數(shù)組是_動態(tài)_分配的數(shù)組。這種數(shù)組在聲明它時需要使用數(shù)組指針。?15.二維數(shù)組是一種非線性結(jié)構(gòu),其中的每一個數(shù)組元素最多有_個直接前驅(qū)(或直接后繼)。16.若設(shè)一個nn的矩陣A的開始存儲地址LOC(0,0)及元素所占存儲單元數(shù)d已知,按行存儲時其任意一個矩陣元素aij的存儲地址為_LOC(0,0)+(i*n+j)d_。17.對稱矩陣的行數(shù)與列數(shù)_相等_且以主對角線為對稱軸,aij=aji,因此只存儲它的上三角部分或下三角部分即可。18.將一個n階對稱矩陣的上三角部分或下三角部分壓縮存放于一個一維數(shù)組中,則一維數(shù)組需要存儲_n*(n+1)/2_個矩陣元素。19.利用三元組表存放稀疏矩陣中的非零元素,則在三元組表中每個三元組元素對應(yīng)一個非零元素的行號、列號和_值_。1、DA1+(i-1)*k2、1100+(6*2+3)*2=11303、100+(19*6+6)*2=34

溫馨提示

  • 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
  • 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
  • 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
  • 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
  • 5. 人人文庫網(wǎng)僅提供信息存儲空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
  • 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
  • 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。

最新文檔

評論

0/150

提交評論