數(shù)據(jù)結(jié)構(gòu)習(xí)題(包含全部答案解析)

..數(shù)據(jù)結(jié)構(gòu)習(xí)題集〔自編第一章緒論一、選擇題1．?dāng)?shù)據(jù)結(jié)構(gòu)是一門(mén)研究非數(shù)值計(jì)算的程序設(shè)計(jì)問(wèn)題中的操作對(duì)象以及它們之間的〔和運(yùn)算的學(xué)科。A．結(jié)構(gòu)B．關(guān)系C．運(yùn)算D．算法2．在數(shù)據(jù)結(jié)構(gòu)中,從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成〔。A．動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B．緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C．線(xiàn)性結(jié)構(gòu)和非線(xiàn)性結(jié)構(gòu)D．邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)3．線(xiàn)性表的邏輯順序和存儲(chǔ)順序總是一致的,這種說(shuō)法〔。A．正確B．不正確C．無(wú)法確定D．以上答案都不對(duì)4．算法分析的目的是〔。A．找出算法的合理性B．研究算法的輸人與輸出關(guān)系C．分析算法的有效性以求改進(jìn)D．分析算法的易懂性5.算法的時(shí)間復(fù)雜度取決于〔A．問(wèn)題的規(guī)模B待處理數(shù)據(jù)的初態(tài)C.A和B6．一個(gè)算法應(yīng)該是〔。A．程序B．問(wèn)題求解步驟的描述C．要滿(mǎn)足五個(gè)基本特性D．A和C.7.下面關(guān)于算法說(shuō)法錯(cuò)誤的是〔A．算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)B.為解決某問(wèn)題的算法與為該問(wèn)題編寫(xiě)的程序含義是相同的C.算法的可行性是指指令不能有二義性D.以上幾個(gè)都是錯(cuò)誤的8．以下與數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)無(wú)關(guān)的術(shù)語(yǔ)是〔。A．循環(huán)隊(duì)列B.鏈表C.哈希表D.棧9．在下面的程序段中,對(duì)x的賦值語(yǔ)句的頻度為〔for〔i=0;i<n;i++for<j=0;j<n;j++>x=x+1;A．2nB．nC．n2D．log2n10．以下數(shù)據(jù)結(jié)構(gòu)中,〔是非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)A．樹(shù)B．字符串C．隊(duì)列D．棧11.下列數(shù)據(jù)中,〔是線(xiàn)性數(shù)據(jù)結(jié)構(gòu)。A．哈夫曼樹(shù)B.有向無(wú)環(huán)圖C.二叉排序樹(shù)D.棧12．以下屬于邏輯結(jié)構(gòu)的是〔。A．順序表B.哈希表C.有序表D.單鏈表二、填空題1、_______是信息的載體,是對(duì)客觀事物的符號(hào)表示,它能夠被計(jì)算機(jī)識(shí)別、存儲(chǔ)、加工和處理,________是對(duì)能夠有效的輸人到計(jì)算機(jī)中并且能夠被計(jì)算機(jī)處理的符號(hào)的總稱(chēng)。〔數(shù)據(jù)、數(shù)據(jù)2、數(shù)據(jù)元素是數(shù)據(jù)的______,有些情況下也稱(chēng)為元素、結(jié)點(diǎn)、頂點(diǎn)、記錄等?！不締挝?、________是數(shù)據(jù)不可分割的最小單元,是具有獨(dú)立含義的最小標(biāo)識(shí)單位。例如構(gòu)成一個(gè)數(shù)據(jù)元素的字段、域、屬性等都可稱(chēng)之為_(kāi)_______。〔數(shù)據(jù)項(xiàng)、數(shù)據(jù)項(xiàng)4、數(shù)據(jù)的邏輯結(jié)構(gòu)是指數(shù)據(jù)之間的________。邏輯結(jié)構(gòu)是從________上描述數(shù)據(jù),它與具體存儲(chǔ)無(wú)關(guān),是獨(dú)立于計(jì)算機(jī)的。因此邏輯結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的______________?！策壿嬯P(guān)系、邏輯關(guān)系、數(shù)學(xué)模型5、數(shù)據(jù)的________指數(shù)據(jù)元素及其關(guān)系在計(jì)算機(jī)存儲(chǔ)器內(nèi)的表示。_________是邏輯結(jié)構(gòu)在計(jì)算機(jī)里的實(shí)現(xiàn),也稱(chēng)之為映像?！泊鎯?chǔ)結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)6、數(shù)據(jù)邏輯結(jié)構(gòu)可以分為四種基本的類(lèi)型,_______結(jié)構(gòu)中的元素除了僅僅只是同屬于一個(gè)_________________,不存在什么關(guān)系?！布?、集合7、數(shù)據(jù)邏輯結(jié)構(gòu)的四種基本類(lèi)型中,________中的元素是一種一對(duì)一的關(guān)系,這種結(jié)構(gòu)的特征是：若結(jié)構(gòu)是非空集,則有且只有一個(gè)開(kāi)始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn),并且所有結(jié)點(diǎn)最多只能有一個(gè)直接前驅(qū)和一個(gè)直接后繼。〔線(xiàn)性結(jié)構(gòu)8、數(shù)據(jù)邏輯結(jié)構(gòu)的四種基本類(lèi)型中,____________中的元素是一種一對(duì)多的關(guān)系。〔樹(shù)形結(jié)構(gòu)9、圖型結(jié)構(gòu)或圖狀結(jié)構(gòu)是一種________的關(guān)系。在這種邏輯結(jié)構(gòu)中,所有結(jié)點(diǎn)均可以有多個(gè)前驅(qū)和多個(gè)后繼?！捕鄬?duì)多10、有時(shí)也可將樹(shù)型結(jié)構(gòu)、集合和圖型結(jié)構(gòu)稱(chēng)為_(kāi)_________,這樣數(shù)據(jù)的邏輯結(jié)構(gòu)就可以分為_(kāi)_________和________兩大類(lèi)?！卜蔷€(xiàn)性結(jié)構(gòu)、線(xiàn)性結(jié)構(gòu)、非線(xiàn)性機(jī)構(gòu)11、____________方式是指邏輯上相鄰的結(jié)點(diǎn)被存儲(chǔ)到物理上也相鄰的存儲(chǔ)單元中。這種存儲(chǔ)結(jié)構(gòu)只存儲(chǔ)結(jié)點(diǎn)的數(shù)值,不存儲(chǔ)結(jié)點(diǎn)之間的關(guān)系,結(jié)點(diǎn)之間的關(guān)系是通過(guò)存儲(chǔ)單元的相鄰關(guān)系隱含的表示出來(lái)的?！岔樞虼鎯?chǔ)12、_______方式是種存儲(chǔ)方法,不要求邏輯上相鄰的結(jié)點(diǎn)在物理上也相鄰,即數(shù)據(jù)元素可以存儲(chǔ)在任意的位置上?！叉?zhǔn)酱鎯?chǔ)13、_________方式是利用結(jié)點(diǎn)關(guān)鍵字的值直接計(jì)算出該結(jié)點(diǎn)存儲(chǔ)單元地址,然后將結(jié)點(diǎn)按某種方式存人該地址的一種方法?！采⒘写鎯?chǔ)或哈希存儲(chǔ)14、所謂算法〔Algorithm是對(duì)特定問(wèn)題求解步驟的一種描述,它是指令的其中每個(gè)指令表示一個(gè)或多個(gè)操作。算法的五個(gè)重要特性是__________、__________、__________、__________和__________?！灿邢扌蛄?、有窮性、確定性、可行性、輸入、輸出15、算法的_______性是指算法必須能夠在執(zhí)行有限個(gè)步驟之后結(jié)束,并且每個(gè)步驟都必須在有窮的時(shí)間內(nèi)完成?！灿懈F性16、算法的________性是指算法中的每一個(gè)步驟必須是有明確定義的,不允許有模棱兩可的解釋,也不允許有多義性。并且,在任何條件下,算法只能有惟一的一條執(zhí)行路徑,即只要輸人是相同的就只能得到____________的輸出結(jié)果?！泊_定性、相同17、算法的____________性又稱(chēng)為算法的能行性,是指算法中描述的操作是可以通過(guò)已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來(lái)實(shí)現(xiàn)。〔可行性18、判斷一個(gè)算法的好壞主要以下幾個(gè)標(biāo)準(zhǔn)：________、________、________、_________?！舱_性、可讀性、健壯性、時(shí)間效率和空間效率19、算法分析是對(duì)一種算法所消耗的計(jì)算機(jī)資源的估算,其中包括計(jì)算機(jī)_________的長(zhǎng)短和___________________的大小?！策\(yùn)行時(shí)間、所占據(jù)空間20、空間復(fù)雜度〔SPaceComPlexity也是度量一個(gè)算法好壞的標(biāo)準(zhǔn),它所描述的是算法在運(yùn)行過(guò)程中所占用_____________的大小?！泊鎯?chǔ)空間三、判斷題1．順序存儲(chǔ)方式只能用于存儲(chǔ)線(xiàn)性結(jié)構(gòu)。〔×2．?dāng)?shù)據(jù)元素是數(shù)據(jù)的最小單位?！病?．算法的優(yōu)劣與算法描述語(yǔ)言無(wú)關(guān),但與所用計(jì)算機(jī)有關(guān)。<×>4．健壯的算法不會(huì)因非法的輸入數(shù)據(jù)而出現(xiàn)莫名其妙的狀態(tài)。<>5．?dāng)?shù)據(jù)的邏輯結(jié)構(gòu)是指各元素之間的邏輯關(guān)系,是根據(jù)用戶(hù)需要而建立的。6．?dāng)?shù)據(jù)結(jié)構(gòu)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)在計(jì)算機(jī)中的映像分別稱(chēng)為存儲(chǔ)結(jié)構(gòu)、結(jié)點(diǎn)、數(shù)據(jù)域。〔7．?dāng)?shù)據(jù)的物理結(jié)構(gòu)是指數(shù)據(jù)在計(jì)算機(jī)中實(shí)際的存儲(chǔ)形式?！?．具有存取任一元素的時(shí)間相等這一特點(diǎn)的存儲(chǔ)結(jié)構(gòu)稱(chēng)為隨機(jī)存取結(jié)構(gòu)。9．算法實(shí)際上就是程序,程序也一定是算法。<×>10.在順序存儲(chǔ)結(jié)構(gòu)中,有時(shí)也存儲(chǔ)數(shù)據(jù)結(jié)構(gòu)中元素之間的關(guān)系。<×>11.順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大,且插入、刪除運(yùn)算效率高。<×>12.數(shù)據(jù)結(jié)構(gòu)的基本操作的設(shè)置的最重要的準(zhǔn)則是,實(shí)現(xiàn)應(yīng)用程序與存儲(chǔ)結(jié)構(gòu)的獨(dú)立。<>13.數(shù)據(jù)的邏輯結(jié)構(gòu)說(shuō)明數(shù)據(jù)元素之間的順序關(guān)系,它依賴(lài)于計(jì)算機(jī)的儲(chǔ)存結(jié)構(gòu)。<×>14.判斷一個(gè)算法的好壞主要以下幾個(gè)標(biāo)準(zhǔn)：正確性、有窮性、健壯性和可行性。<×> 15．算法的時(shí)間復(fù)雜度T〔n=O<f<n>>表示隨問(wèn)題規(guī)模n的增大,算法執(zhí)行時(shí)間的增長(zhǎng)率與函數(shù)f<n>的增長(zhǎng)率相同?！菜摹⒕C合題1．用大O形式表示下面算法的時(shí)間復(fù)雜度：for〔i=0；i＜m；i十十for〔j=0；j＜n；j＋＋A[i][j]=i*j；2．寫(xiě)出下面算法的時(shí)間復(fù)雜度：i＝0；s=0；while<s＜n｛i++;s+=i;｝ 3．寫(xiě)出以下算法的時(shí)間復(fù)雜度：for〔i＝0;i＜m;i＋＋for〔j＝0;j＜t;j＋＋c[i][j]=0；for〔i=0；i＜m；i＋＋for〔j=o;j<t;j++for〔k=0；k＜n；k＋＋c［i］［j］＋＝a［i］［k］*b[k][j];4．寫(xiě)出下面算法的時(shí)間復(fù)雜度：i=1;while〔i＜＝ni=i*3;5．求下面函數(shù)中各條語(yǔ)句的頻度和算法的時(shí)間復(fù)雜度：prime〔intn｛inti＝2；while<<n％i！=0＆＆i＜sqrt<n>>i++;if〔i＞sqrt<n>>printf〔"％disaprimenumber.＼n",n；elseprintf〔"％disnotaprimenumber.＼n",n；｝1.該算法的時(shí)間復(fù)雜度為：O<m×n>。2.該算法的時(shí)間復(fù)雜度為：O<>3.該算法的時(shí)間復(fù)雜度為：O<m×n×t>。4.該算法的時(shí)間復(fù)雜度為：log3<n>。5.該算法的時(shí)間復(fù)雜度為：O<>。6．將下列函數(shù),按它們?cè)趎→∝時(shí)的無(wú)窮大階數(shù),從小到大排序。n,n-n3+7n5,nlogn,2n/2,n3,logn,n1/2+logn,<3/2>n,,n!,n2+logn從小到大排列為：logn,n1/2+logn,n,nlogn,n2+logn,n3,n-n3+7n5,2n/2,<3/2>n,n!,第二章線(xiàn)性表一、選擇題1．在一個(gè)長(zhǎng)度為n的順序表中刪除第i個(gè)元素〔0<i<=n時(shí),需要向前移動(dòng)<>個(gè)元素。A．n-iB．n-i+1C．n-i-1D．i+12．從一個(gè)具有n個(gè)元素的線(xiàn)性表中查找其值等于x的結(jié)點(diǎn)時(shí),在查找成功的情況下,需平均比較<>個(gè)元素結(jié)點(diǎn)。A．n/2B．nC．<n-1>/2D．<n+1>/23．對(duì)一個(gè)具有n個(gè)元素的線(xiàn)性表,建立其單鏈表的時(shí)間復(fù)雜度為<>。A．O<n>B．O<1>C．O<n2D．O〔long2n4．線(xiàn)性表采用鏈?zhǔn)酱鎯?chǔ)時(shí),其地址<>。A．必須是連續(xù)的B．一定是不連續(xù)的C．部分地址必須連續(xù)D．連續(xù)與否均可以5．在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插人一個(gè)新的結(jié)點(diǎn),使得鏈表仍然有序,該算法的時(shí)間復(fù)雜度是<>。A．O〔long2nB．O〔lC．O〔n2D．O〔n6．線(xiàn)性表是<>。A．一個(gè)有限序列,可以為空B．一個(gè)有限序列,不可以為空C．一個(gè)無(wú)限序列,可以為空D．一個(gè)無(wú)限序列,不可以為空7．在一個(gè)長(zhǎng)度為n的順序表中,向第i個(gè)位置〔0一1＜n＋1插入一個(gè)新元素時(shí),需要向后移動(dòng)<>個(gè)元素。A．n-iB．n-i＋1C．n－i－1D．i＋18．如果某鏈表中最常用的操作是取第i個(gè)結(jié)點(diǎn)及其前驅(qū),則采用<>存儲(chǔ)方式最節(jié)省時(shí)間。A．單鏈表B．雙向鏈表C．單循環(huán)鏈表D．順序表9．一個(gè)順序存儲(chǔ)線(xiàn)性表的第一個(gè)元素的存儲(chǔ)地址是90,每個(gè)元素的長(zhǎng)度是2,則第6個(gè)元素的存儲(chǔ)地址是〔。A．98B．100C．102D．10610．在順序存儲(chǔ)的線(xiàn)性表〔a1……an中,刪除任意一個(gè)結(jié)點(diǎn)所需移動(dòng)結(jié)點(diǎn)的平均移動(dòng)次數(shù)為<>A．nB．n／2C．<n-1>/2D．〔n＋l/211．在線(xiàn)性表的下列存儲(chǔ)結(jié)構(gòu)中,讀取第i個(gè)元素花費(fèi)的時(shí)間最少的是〔。A．單鏈表B．雙鏈表C．循環(huán)鏈表D．順序表12．若某鏈表中最常用的操作為在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)和刪除最后一個(gè)結(jié)點(diǎn),則采用〔存儲(chǔ)方式最節(jié)省時(shí)間。A．雙鏈表B．單鏈表C．單循環(huán)鏈表D．帶頭結(jié)點(diǎn)的雙循環(huán)鏈表 13．在單鏈表中刪除指針p所指結(jié)點(diǎn)的后繼結(jié)點(diǎn),則執(zhí)行〔操作。A．p->next=p->next->next B．p->next=p->nextC．p=p->next->next D．p=p->next; p->next=p->next->next 14．在一個(gè)單鏈表中,已知q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的前驅(qū),若在q和p之間插入s所指的結(jié)點(diǎn),則執(zhí)行〔操作。 A．s->next=p->next; p->next=s; B．q->next=s; s->next=p;C．p->next=s->next; s->next=p; D．p->next=s; s->next=q; 15．在單鏈表中附加頭結(jié)點(diǎn)的目的是為了〔。 A．保證單鏈表中至少有一個(gè)節(jié)點(diǎn) B．標(biāo)識(shí)單鏈表中首結(jié)點(diǎn)的位置C．方便運(yùn)算的實(shí)現(xiàn) D．說(shuō)明單鏈表是線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)16．循環(huán)單鏈表的主要優(yōu)點(diǎn)是〔。 A．不再需要頭指針了B．從表中任意一個(gè)結(jié)點(diǎn)出發(fā)都能掃描到整個(gè)鏈表 C．已知某個(gè)結(jié)點(diǎn)的位置后,能夠容易找到它的前驅(qū) D．在進(jìn)行插入、刪除操作時(shí),能更好地保證鏈表不斷開(kāi) 17．非空的循環(huán)單鏈表L的尾結(jié)點(diǎn)p滿(mǎn)足〔。 A．p->next=NULL B．p=NULL C．p->next=L D．p=L 18．在雙向循環(huán)鏈表中,在p指針?biāo)赶虻慕Y(jié)點(diǎn)前插入一個(gè)指針q所指向的新結(jié)點(diǎn),其修改指針的操作是<>。注:雙向鏈表的結(jié)點(diǎn)結(jié)構(gòu)為<prior,data,next>。供選擇的答案：A．p->prior=q；q->next=p；p->prior->next=q；q->prior=q；B．p->prior=q；p->prior->next=q;q->next=p；q->prior=p->prior；C．q->next=p； q->prior=p->prior；p->prior->next=q;p->prior=q;D．q->prior=p->prior；q->next=p； p->prior=q； p->prior=q； 19．在雙向鏈表存儲(chǔ)結(jié)構(gòu)中,刪除p所指的結(jié)點(diǎn)時(shí)須修改指針〔。A．p->prior->next=p->next;p->next->prior=p->prior;B．p->prior=p->prior->prior;p->prior->next=p;<刪p的前趨>C．p->next->prior=p;p->next=p->next->next;D．p->next=p->prior->prior;p->prior=p->next->next;二、填空題1．線(xiàn)性表〔LinearList是最簡(jiǎn)單、最常用的一種數(shù)據(jù)結(jié)構(gòu)。線(xiàn)性表中的元素存在著__________的相互關(guān)系?！惨粚?duì)一2．線(xiàn)性表中有且僅有一個(gè)開(kāi)始結(jié)點(diǎn),表中有且僅有一個(gè)終端結(jié)點(diǎn),除開(kāi)始結(jié)點(diǎn)外,其他每個(gè)元素有且僅有一個(gè)__________,除終端結(jié)點(diǎn)外,其他每個(gè)元素有且僅有一個(gè)______。3．線(xiàn)性表是n〔n>=0個(gè)數(shù)據(jù)元素的________。其中n為數(shù)據(jù)元素的個(gè)數(shù),定義為線(xiàn)性表的__________。當(dāng)n為零時(shí)的表稱(chēng)為_(kāi)________。4．所謂順序表〔SequentialLISt是線(xiàn)性表的__________,它是將線(xiàn)性表中的結(jié)點(diǎn)按其____________依次存放在內(nèi)存中一組連續(xù)的存儲(chǔ)單元中,使線(xiàn)性表中相鄰的結(jié)點(diǎn)存放在____________的存儲(chǔ)單元中。5．單鏈表不要求邏輯上相鄰的存儲(chǔ)單元在物理上也一定要相鄰。它是分配一些_______的存儲(chǔ)單元來(lái)存儲(chǔ)線(xiàn)性表中的數(shù)據(jù)元素,這些存儲(chǔ)單元可以分散在內(nèi)存中的_________的位置上,它們?cè)谖锢砩峡梢允且黄B續(xù)的存儲(chǔ)單元,也可以是__________的。因此在表示線(xiàn)性表這種數(shù)據(jù)結(jié)構(gòu)時(shí),必須在存儲(chǔ)線(xiàn)性表元素的同時(shí),也存儲(chǔ)線(xiàn)性表的。6．線(xiàn)性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的每一個(gè)結(jié)點(diǎn)〔Node需要包括兩個(gè)部分：一部分用來(lái)存放元素的數(shù)據(jù)信息,稱(chēng)為結(jié)點(diǎn)的_________；另一部分用來(lái)存放元素的指向直接后繼元素的指針<即直接后繼元素的地址信息>,稱(chēng)為_(kāi)_______或____________。7．線(xiàn)性鏈表的邏輯關(guān)系是通過(guò)每個(gè)結(jié)點(diǎn)指針域中的指針來(lái)表示的。其邏輯順序和物理存儲(chǔ)順序不再一致,而是一種_________存儲(chǔ)結(jié)構(gòu),又稱(chēng)為_(kāi)_________。8．如果將單鏈表最后一個(gè)結(jié)點(diǎn)的指針域改為存放鏈表中的頭結(jié)點(diǎn)的地址值,這樣就構(gòu)成了______________。9．為了能夠快速地查找到線(xiàn)性表元素的直接前驅(qū),可在每一個(gè)元素的結(jié)點(diǎn)中再增加一個(gè)指向其前驅(qū)的指針域,這樣就構(gòu)成了___________。10．雙向鏈表某結(jié)點(diǎn)的指針P,它所指向結(jié)點(diǎn)的后繼的前驅(qū)與前驅(qū)的后繼都是p_______。11．在單鏈表中,刪除指針P所指結(jié)點(diǎn)的后繼結(jié)點(diǎn)的語(yǔ)句是____________。12．在雙循環(huán)鏈表中,刪除指針P所指結(jié)點(diǎn)的語(yǔ)句序列是P->prior->next＝p->next及__________。13．單鏈表是___________的鏈接存儲(chǔ)表示。14．可以使用___________表示樹(shù)形結(jié)構(gòu)。15．向一個(gè)長(zhǎng)度為n的向量的第i個(gè)元素<l≤i≤n+1之前插人一個(gè)元素時(shí),需向后移動(dòng)__________個(gè)元素。16．刪除一個(gè)長(zhǎng)度為n的向量的第i個(gè)元素〔l≤i≤n時(shí),需向前移動(dòng)_______個(gè)元素。17．在單鏈表中,在指針P所指結(jié)點(diǎn)的后面插人一個(gè)結(jié)點(diǎn)S的語(yǔ)句序列是__________。18．在雙循環(huán)鏈表中,在指針P所指結(jié)點(diǎn)前插人指針S所指的結(jié)點(diǎn),需執(zhí)行語(yǔ)句_______。19．取出廣義表A＝〔〔x,〔a,b,c,d中原子c的函數(shù)是_________。20．在一個(gè)具有n個(gè)結(jié)點(diǎn)的有序單鏈表中插人一個(gè)新結(jié)點(diǎn)并使之仍然有序的時(shí)間復(fù)雜度為_(kāi)______________。21．寫(xiě)出帶頭結(jié)點(diǎn)的雙向循環(huán)鏈表L為空表的條件________________。22．線(xiàn)性表、棧和隊(duì)列都是_________________結(jié)構(gòu)。23．向棧中插人元素的操作是先移動(dòng)棧_____________針,再存人元素。1.一對(duì)一2.直接前驅(qū)、直接后繼3.有限序列、長(zhǎng)度、空表4.順序存儲(chǔ)結(jié)構(gòu)、邏輯順序、地址相鄰5.任意、任意、不連續(xù)、邏輯關(guān)系6.數(shù)據(jù)域、指針域、鏈域7.非順序、非順序映像8.循環(huán)鏈表9.雙向鏈表10.所指向的結(jié)點(diǎn)本身11.P->next=p->next->next12.P->next->prior=P->prior13.線(xiàn)性表14.雙鏈表15.n-i+116.n-i17.S->next=P->next;P->next=S18.p->prior->next=S;s->prior=p->prior;s->next=p;p->prior=s;19.head<tail<tail<<head<tail<head<A>>>>>>20.O<n>21.<L==L->Next>&&<L==L->Prior>22.線(xiàn)性23.頂三、判斷題1．線(xiàn)性表采用鏈表存儲(chǔ)時(shí),結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。<×>2．在具有頭結(jié)點(diǎn)的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中,頭指針指向鏈表中的第一個(gè)數(shù)據(jù)結(jié)點(diǎn)。<×>3．順序存儲(chǔ)的線(xiàn)性表不可以隨機(jī)存取。<×>4．單鏈表不是一種隨機(jī)存取結(jié)構(gòu)?！?．順序存儲(chǔ)結(jié)構(gòu)線(xiàn)性表的插入和刪除運(yùn)算所移動(dòng)元素的個(gè)數(shù)與該元素的位置無(wú)關(guān)。<×>6．順序存儲(chǔ)結(jié)構(gòu)是動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu),鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是靜態(tài)存儲(chǔ)結(jié)構(gòu)。<×>7．線(xiàn)性表的長(zhǎng)度是線(xiàn)性表所占用的存儲(chǔ)空間的大小。<×>8．雙循環(huán)鏈表中,任意一結(jié)點(diǎn)的后繼指針均指向其邏輯后繼。<×>9．線(xiàn)性表的惟一存儲(chǔ)形式是鏈表。<×>1.錯(cuò)誤：鏈表存儲(chǔ)中,結(jié)點(diǎn)之間可以連續(xù)也可以不連續(xù),但結(jié)點(diǎn)內(nèi)部是連續(xù)的。2.錯(cuò)誤：頭指針指向頭結(jié)點(diǎn)而不是數(shù)據(jù)結(jié)點(diǎn)。3.錯(cuò)誤：順序存儲(chǔ)的線(xiàn)性表可以隨機(jī)存取。4.正確。5.錯(cuò)誤。6.錯(cuò)誤：順序存儲(chǔ)結(jié)構(gòu)是靜態(tài)存儲(chǔ)結(jié)構(gòu),鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是動(dòng)態(tài)存儲(chǔ)結(jié)構(gòu)。7.錯(cuò)誤：先行表的長(zhǎng)度是線(xiàn)性表中結(jié)點(diǎn)的個(gè)數(shù)。8.錯(cuò)誤：注意最后一個(gè)結(jié)點(diǎn)。9.錯(cuò)誤：也可以有順序存儲(chǔ)的形式。第三章棧和隊(duì)列一、選擇題l．一個(gè)棧的序列是：a,b,c,d,e,則棧的不可能輸出的序列是〔。A．a(chǎn),b,c,d,eB．d,e,c,b,aC．d,c,e,a,bD．e,d,c,b,a2．若一個(gè)棧的輸人序列是1,2,3,…,n,輸出序列的第一個(gè)元素是n,則第k個(gè)輸出元素是〔。A．kB．n-k-1C．n-k+1D．不確定3．判定一個(gè)棧S〔最多有n個(gè)元素為空的條件是〔。A．S->top?。?B．S->top==0C．S->top!=nD．S->top==n4．判定一個(gè)棧S〔最多有n個(gè)元素為滿(mǎn)的條件是〔。A．S->top!=0B．S->top==0C．S->top!=nD．S->top==n5．向一個(gè)棧頂指針為top的不帶頭結(jié)點(diǎn)的鏈棧中插人一個(gè)*S結(jié)點(diǎn)的時(shí)候,應(yīng)當(dāng)執(zhí)行語(yǔ)句〔。A．top->next=S；B．S->next=top；top=S；C．S->next＝top->next；top->next＝S；D．S->next＝top；top＝S->next；6．向一個(gè)帶頭結(jié)點(diǎn)、棧頂指針為top的鏈棧中插人一個(gè)*S結(jié)點(diǎn)的時(shí)候,應(yīng)當(dāng)執(zhí)行語(yǔ)句〔。A．top->next=S；B．S->next=top；top=S；C．S->next=top->next；top->next=S；D．S->next=top；top=S->next；7．判定一個(gè)隊(duì)列Q〔最多有n個(gè)元素為空的條件是〔。A．Q->rear-Q->front==nB．Q->rear-Q->front+1==nC．Q->rear==Q->frontD．Q->rear+1==Q->front8．判定一個(gè)隊(duì)列Q〔最多有n個(gè)元素為滿(mǎn)的條件是〔。A．Q->rear-Q->front==nB．Q->rear-Q->front+1==nC．Q->rear==Q->frontD．Q->rear+1==Q->front9．判定一個(gè)循環(huán)隊(duì)列Q〔最多有n個(gè)元素為空的條件是〔。A．Q->rear==Q->frontB．Q->rear==Q->front＋lC．Q->front==<Q->rear+1>％nD．Q->front==<Q->rear-1>％n10．判定一個(gè)循環(huán)隊(duì)列Q〔最多有n個(gè)元素為滿(mǎn)的條件是〔。A．Q->rear==Q->frontB．Q->rear==Q->front＋lC．Q->front==<Q->rear+1>％nD．Q->front==<Q->rear-1>％n11．在一個(gè)鏈隊(duì)列中,假定front和rear分別為頭指針和尾指針,則插入一個(gè)結(jié)點(diǎn)*S的操作是〔。A．front＝front->nextB．S->next=rear；rear=SC．rear->next=S；rear=SD．S->next=front；front＝S12．在一個(gè)鏈隊(duì)列中,假定front和rear分別為頭指針和尾指針,刪除一個(gè)結(jié)點(diǎn)的操作是〔。A．front=front->nextB．rear=rear->nextC．rear->next=frontD．front->next＝rear13．棧與隊(duì)列都是〔。A．鏈?zhǔn)酱鎯?chǔ)的線(xiàn)性結(jié)構(gòu)B．鏈?zhǔn)酱鎯?chǔ)的非線(xiàn)性結(jié)構(gòu)C．限制存取點(diǎn)的線(xiàn)性結(jié)構(gòu)D．限制存取點(diǎn)的非線(xiàn)性結(jié)構(gòu)14．若進(jìn)棧序列為l,2,3,4,則〔不可能是一個(gè)出棧序列。A．3,2,4,1B．l,2,3,4C．4,2,3,1D．4,3,2,l15．在解決計(jì)算機(jī)主機(jī)與打印機(jī)之間速度不匹配問(wèn)題時(shí)通常設(shè)置一個(gè)打印數(shù)據(jù)緩沖區(qū),主機(jī)將要輸出的數(shù)據(jù)依次寫(xiě)人該緩沖區(qū),而打印機(jī)則從該緩沖區(qū)中取走數(shù)據(jù)打印。該緩沖區(qū)應(yīng)該是一個(gè)〔結(jié)構(gòu)。A．堆棧B．隊(duì)列C．?dāng)?shù)組D．線(xiàn)性表1.C 2.C 3.B 4.D 5.B6.C 7.C 8.A 9.A 10.C11.C12.A 13.C 14.C 15.B二、填空回1．?！瞫tack是限定在________一端進(jìn)行插人或刪除操作的線(xiàn)性表。在棧中,允許插人和刪除操作的一端稱(chēng)為_(kāi)_________,而另一端稱(chēng)為_(kāi)________。不含元素的棧稱(chēng)為_(kāi)______。2．在棧的運(yùn)算中,棧的插人操作稱(chēng)為_(kāi)_______或________,棧的刪除操作稱(chēng)為_(kāi)________或__________。3．根據(jù)棧的定義,每一次進(jìn)棧的元素都在原___________之上,并成為新的__________；每一次出棧的元素總是當(dāng)前的_____________,因此最后進(jìn)棧的元素總是__________,所以棧也稱(chēng)為_(kāi)__________線(xiàn)性表,簡(jiǎn)稱(chēng)為_(kāi)___________表。4．棧是一種操作受到限制的線(xiàn)性表,是一種特殊的線(xiàn)性表,因此棧也有__________和_________________兩種存儲(chǔ)結(jié)構(gòu),分別稱(chēng)為_(kāi)_____________和___5．當(dāng)棧滿(mǎn)的時(shí)候,再進(jìn)行人棧操作就會(huì)產(chǎn)生____________,這種情況的溢出稱(chēng)為_(kāi)__________；當(dāng)?？盏臅r(shí)候,如果再進(jìn)行出棧操作,也會(huì)_____________,這種情況下的溢出稱(chēng)為_(kāi)_________________。6．棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)簡(jiǎn)稱(chēng)為_(kāi)___________,是一種__________________。7．人們?nèi)粘Ｓ?jì)算用到的表達(dá)式都被稱(chēng)為_(kāi)___________,這是由于這種算術(shù)表達(dá)式的運(yùn)算符被置于兩個(gè)操作數(shù)中間。8．計(jì)算機(jī)中通常使用___________,這是一種將運(yùn)算符置于兩個(gè)操作數(shù)后面的算術(shù)表達(dá)式。這種表達(dá)式是由波蘭科學(xué)家謝維奇提出的,因此又稱(chēng)為_(kāi)____________9．隊(duì)列〔Queue也是一種___________,但它與棧不同,隊(duì)列中所有的插人均限定在表的一端進(jìn)行,而所有的刪除則限定在表的另一端進(jìn)行。允許插人的一端稱(chēng)為_(kāi)________,允許刪除的一端稱(chēng)為_(kāi)______________。10．隊(duì)列的特點(diǎn)是_________,因此隊(duì)列又被稱(chēng)為_(kāi)______________．的線(xiàn)性表,或稱(chēng)為_(kāi)________________表。11．隊(duì)列的_________又稱(chēng)為_(kāi)_________,是用一組地址連續(xù)的存儲(chǔ)單元依次存放隊(duì)列中的元素。12．由于隊(duì)列中的元素經(jīng)常變化,對(duì)于隊(duì)列的刪除和插人分別在隊(duì)頭和隊(duì)尾進(jìn)行,因此需要設(shè)置兩個(gè)指針?lè)謩e指向__________和__________,這兩個(gè)指針又稱(chēng)為_(kāi)_________和_____________。13．循環(huán)順序隊(duì)列〔CircularSequenceQueue經(jīng)常簡(jiǎn)稱(chēng)為_(kāi)__________,它是將存儲(chǔ)順序隊(duì)列的存儲(chǔ)區(qū)域看成是一個(gè)首尾相連的一個(gè)環(huán),即將隊(duì)首和隊(duì)尾元素連接起來(lái)形成一個(gè)環(huán)形表。首尾相連的狀態(tài)是通過(guò)數(shù)學(xué)上的_________________來(lái)實(shí)現(xiàn)的。14．在算法或程序中,當(dāng)一個(gè)函數(shù)直接調(diào)用自己或通過(guò)一系列語(yǔ)句間接調(diào)用自己的時(shí)候,則稱(chēng)這個(gè)函數(shù)為,也稱(chēng)為_(kāi)___________。函數(shù)直接調(diào)用自己,則稱(chēng)為_(kāi)_________；當(dāng)一個(gè)函數(shù)通過(guò)另一個(gè)函數(shù)來(lái)調(diào)用自己則稱(chēng)為_(kāi)________________。15．在循環(huán)隊(duì)列中規(guī)定：當(dāng)Q->rear==Q->front的時(shí)候循環(huán)隊(duì)列為_(kāi)__________,當(dāng)〔Q->rear+1％MAXSIZE＝front的時(shí)候循環(huán)隊(duì)列為_(kāi)___________________。16．用鏈表方式表示的隊(duì)列稱(chēng)為_(kāi)___________________。17．已知棧的輸人序列為1,2,3,…,n,輸出序列為a1,a2,…,an,符合a2==n的輸出序列共有__________________。18．一個(gè)棧的輸人序列是12345,則棧的輸出序列為43512是________〔填是否可能。19．一個(gè)棧的輸人序列是12345,則棧的輸出序列為12345是_________〔填是否可能。20．設(shè)sq[1．．maxsize]為一個(gè)順序存儲(chǔ)的棧,變量top指示棧頂元素的位置,則作入棧操作的條件是______________。21．設(shè)sq[1．．maxsize]為一個(gè)順序存儲(chǔ)的棧,變量top指示棧頂元素的位置,如果把棧頂元素彈出并送到X中,則需執(zhí)行語(yǔ)句______________。22．棧的特性是__________________。23．對(duì)棧進(jìn)行退棧時(shí)的操作是先取出元素,后移動(dòng)_________。24．設(shè)s[1．．max]為一個(gè)順序存儲(chǔ)的棧,變量top指示棧頂位置,棧為滿(mǎn)的條件是____。25．設(shè)鏈棧的棧頂指針為top,則棧非空的條件是___________。26．已知循環(huán)隊(duì)列用數(shù)組data[1...n]存儲(chǔ)元素值,用f,r分別作為頭尾指針,則當(dāng)前元素個(gè)數(shù)為_(kāi)___________。27．在一個(gè)循環(huán)隊(duì)列中,隊(duì)首指針指向隊(duì)首元素的________位置。〔前一個(gè)或后一個(gè)28．隊(duì)列中允許進(jìn)行刪除的一端稱(chēng)為_(kāi)______________。29．鏈隊(duì)列實(shí)際上是一個(gè)同時(shí)帶有頭指針和尾指針的單鏈表〔1．．n,尾指針指向該單鏈表的第___________個(gè)元素。30．設(shè)雙向鏈表鏈列為lq,lq的頭指針為lq.Front,尾指針為lq.Rear,則隊(duì)列為空的條件是____________。31．從循環(huán)隊(duì)列中刪除一個(gè)元素,其操作是先取出一個(gè)元素,后移動(dòng)____________32．隊(duì)列中允許進(jìn)行插入的一端稱(chēng)為_(kāi)________。1.表尾、棧頂、棧底、空棧2.進(jìn)棧、入棧、退棧、出棧3.棧頂元素、棧頂元素、棧頂元素、最先出棧、后進(jìn)先出、LIFO4.順序、鏈?zhǔn)健㈨樞驐?、鏈?.溢出、上溢、溢出、下溢6.鏈棧、特殊的單鏈表7.中綴表達(dá)式8.后綴表達(dá)式、波蘭式9.特殊的線(xiàn)性表、隊(duì)尾、隊(duì)頭10.先進(jìn)先出、先進(jìn)先出、FIFO11.順序存儲(chǔ)結(jié)構(gòu)、順序隊(duì)列12.隊(duì)頭元素、隊(duì)尾元素、隊(duì)頭指針、隊(duì)尾指針13.循環(huán)隊(duì)列、取模運(yùn)算14.遞歸函數(shù)、自調(diào)用函數(shù)、直接遞歸調(diào)用、間接遞歸調(diào)用15.空、滿(mǎn)16.鏈隊(duì)列17.n-118.不可能的19.可能的20.top!=maxsize21.x=sq[top];top=top-122.先進(jìn)后出23.棧頂指針24.top==max25.top!=nil26.<n+r-f>modn27.前一個(gè)28.隊(duì)首29.n30.lq->front==lq->rear31.棧頂指針32.隊(duì)尾三、判斷題1．棧和隊(duì)列都是限制存取點(diǎn)的線(xiàn)性結(jié)構(gòu)?！?．不同的入棧和出棧組合可能得到相同輸出序列?！?．消除遞歸一定要用棧?！?．循環(huán)隊(duì)列是順序存儲(chǔ)結(jié)構(gòu)?！?．循環(huán)隊(duì)列不會(huì)產(chǎn)生溢出?！?．循環(huán)隊(duì)列滿(mǎn)的時(shí)候rear==front?！?．在對(duì)鏈隊(duì)列〔帶頭結(jié)點(diǎn)做出隊(duì)操作時(shí)不會(huì)改變front指針的值?！?.正確。2.錯(cuò)誤：不同的入棧和出棧組合得到不同輸出序列。3.錯(cuò)誤：某些情況如尾遞歸可以轉(zhuǎn)換為遞推的形式。4.正確。5.錯(cuò)誤：循環(huán)隊(duì)列不會(huì)產(chǎn)生假溢出。6.錯(cuò)誤。7.正確。四、綜合題1．設(shè)有4個(gè)元素A、B、C和D進(jìn)棧,給出它們所有可能的出棧秩序?？赡艿某鰲Ｐ蛄校骸补?4個(gè)ABCD ABDC ACBD ACDB ADCB BACD BADC BCAD BCDA BDCACBAD CBDA CDBA DCBA不可能的出棧序列：〔共10個(gè)ADBC BDAC CABD CADB CDABDABC DACB DBAC DBCA DCAB習(xí)題四一、選擇項(xiàng)l．空串與空格串〔。A．相同B．不相同C．可能相同D．無(wú)法確定2．設(shè)有兩個(gè)申S1與S2,求串S2在S1中首次出現(xiàn)位置的運(yùn)算稱(chēng)作〔。A．連接B．求子串C．模式匹配D．判子串3．串與普通的線(xiàn)性表相比較,它的特殊性體現(xiàn)在〔。A．順序的存儲(chǔ)結(jié)構(gòu)B．鏈接的存儲(chǔ)結(jié)構(gòu)C．?dāng)?shù)據(jù)元素是一個(gè)字符D．?dāng)?shù)據(jù)元素可以任意4．設(shè)有串S=‘Computer’,則其子串的數(shù)目是〔。A．36B．37C．8D．91.B 2.C3.C 4.B二、境空題1．串是由零個(gè)或多個(gè)字符組成的____________。通常記作：s＝"c1,c2,…,cn"<n=>0>,其中,S稱(chēng)為_(kāi)_______；串中的Ci〔1<=i<=n可以是字母、數(shù)字字格或其他字符。用雙引號(hào)括起來(lái)的部分是_________．即串S的內(nèi)容。2．串中字符的個(gè)數(shù)稱(chēng)為串的________。3．不含有任何字符的串稱(chēng)為_(kāi)________,它的長(zhǎng)度為_(kāi)__________。4．由一個(gè)或多個(gè)空格構(gòu)成的串稱(chēng)為_(kāi)___________,它的長(zhǎng)度為_(kāi)__________。5．串中任意多個(gè)連續(xù)字符組成的子序列稱(chēng)為該串的____________；包含___________的串稱(chēng)為主串。6．字符在序列中的序號(hào)稱(chēng)為該字符在串中的________________。7．兩個(gè)字符串相等是指兩個(gè)字符串的,也就是說(shuō)這兩個(gè)字符串不僅__________,而且對(duì)應(yīng)位置上的字符也。8．兩個(gè)串的比較實(shí)際上是_________的比較。兩個(gè)串從第一個(gè)位置上的字符開(kāi)始進(jìn)行比較,當(dāng)?shù)谝淮纬霈F(xiàn)_____________大的串為大,若比較過(guò)程中出現(xiàn)一個(gè)字符串結(jié)束的情況,則另一個(gè)串為_(kāi)________________。9．串的_______________就是把串所包含的字符序列,依次存人連續(xù)的存儲(chǔ)單元中去。10．有些計(jì)算機(jī)系統(tǒng)中為了充分利用存儲(chǔ)空間,允許一個(gè)存儲(chǔ)單元可以存放多個(gè)字符,串的這種存儲(chǔ)方式是一種__________________。11．串的______________是以存儲(chǔ)單元為存儲(chǔ)單位,一個(gè)存儲(chǔ)單元中只存放_(tái)_________。在這種情況下,即使一個(gè)存儲(chǔ)單元能存放多個(gè)字符,這時(shí)候也只存放_(tái)_______________。12．串在非緊縮方式下,串長(zhǎng)度的存儲(chǔ)是隱式的,__________即串的長(zhǎng)度。13．一些計(jì)算機(jī)是以字節(jié)為存取單位,恰好一個(gè)字符占用一個(gè)字節(jié),自然形成了每個(gè)存儲(chǔ)單元存放_(tái)_________的分配方式,這種方式就是一種__________。這種方式一般不需要存放_(tái)___________的存儲(chǔ)單元,而需要以程序中各變量值所、的字符為結(jié)束符。14．串的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是將存儲(chǔ)區(qū)域分成一系列大小相同的結(jié)點(diǎn),每個(gè)結(jié)點(diǎn)有兩個(gè)城：____________域和________域。其中___________域用于存放數(shù)據(jù),___________域用于存放下一個(gè)結(jié)點(diǎn)的指針。15．子串定位StrIndex<s,t>,也稱(chēng)為_(kāi)______,是返回串t在s主串中的位置。1.有限序列、串名、串值2.長(zhǎng)度3.空串、零4.空格串、空格的個(gè)數(shù)5.子串、子串6.位置7.值相等、長(zhǎng)度相等、相等8.ASCII碼、ASCII碼、較大者9.順序存儲(chǔ)結(jié)構(gòu)10.緊縮式存儲(chǔ)方式11.非緊縮存儲(chǔ)方式、一個(gè)字符、一個(gè)字符12.串所占用的存儲(chǔ)單元的個(gè)數(shù)13.一個(gè)字符、單字節(jié)存儲(chǔ)方式、串長(zhǎng)、不包含14.數(shù)據(jù)、指針、數(shù)據(jù)、指針15.模式匹配三、判斷回1．子串是主串中字符構(gòu)成的有限序列?！病?．KMP算法的最大特點(diǎn)是指示主串的指針不需要回溯。〔3．串中的元素只能是字符?！?．串中的元素只可能是字母?！病?．串是一種特殊的線(xiàn)性表。〔6．串中可以包含有空白字符?！?．串的長(zhǎng)度不能為零?！病?．兩個(gè)串相等必有串長(zhǎng)度相同?！?．兩個(gè)串相等則各位置上字符必須對(duì)應(yīng)相等?！擦?xí)題五一、選擇題l．?dāng)?shù)組常用的兩種基本操作是〔。A．建立與查找B．刪除與查找C．插人與索引D．查找與修改2．對(duì)稀疏矩陣進(jìn)行壓縮存儲(chǔ),常用的兩種方法是〔。A．二元組和散列表B．三元組表和十字鏈表C．三角矩陣和對(duì)角矩陣D．對(duì)角矩陣和十字鏈表3．采用稀疏矩陣的三元組表形式進(jìn)行壓縮存儲(chǔ),若要完對(duì)三元組表進(jìn)行成轉(zhuǎn)置,只要將行和列對(duì)換,這種說(shuō)法〔。A．正確B．錯(cuò)誤C．無(wú)法確定D．以上均不對(duì)4．一個(gè)廣義表的表頭總是一個(gè)廣義表,這種說(shuō)法〔。A．正確B．錯(cuò)誤C．無(wú)法確定D．以上均不對(duì)5．一個(gè)廣義表的表尾總是一個(gè)廣義表,這種說(shuō)法〔。A．正確B．錯(cuò)誤C．無(wú)法確定D．以上均不對(duì)6．廣義表<<a>>的表頭是〔。A．〔B．a(chǎn)C．〔aD．〔〔a7．廣義表〔〔a的表尾是〔。A．〔B．a(chǎn)C．〔aD．〔〔a8．廣義表〔〔a,a的表頭是〔。A．〔B．a(chǎn)C．〔aD．〔〔a9．廣義表〔〔a,a的表尾是〔。A．<>B．a(chǎn)C．〔aD．〔〔a10．廣義表〔a,b,c的表頭是〔。A．a(chǎn)B．〔aC．a(chǎn),bD．〔b,c11．廣義表〔a,b,c的表尾是〔。A．b,cB．〔b,cC．a(chǎn)．b,cD．〔a,b,c12．廣義表A滿(mǎn)足Head〔=Tail〔,則A為〔。A．〔B．〔〔C〔〔,〔D．〔〔,〔,〔1.D 2.B 3.B 4.B 5.A6.C 7.A 8.C 9.C 10.A11.B 12.B二、填空題1．?dāng)?shù)組〔array是n〔n＞1個(gè)__________的有序組合,數(shù)組中的數(shù)據(jù)是按順序存儲(chǔ)在一塊______________的存儲(chǔ)單元中。2．?dāng)?shù)組中的每一個(gè)數(shù)據(jù)通常稱(chēng)為_(kāi)____,________用下標(biāo)區(qū)分,其中下標(biāo)的個(gè)數(shù)由數(shù)組的________________決定。3．由于計(jì)算機(jī)內(nèi)存中的存儲(chǔ)單元是一個(gè)一維的存儲(chǔ)結(jié)構(gòu),因此對(duì)于多維數(shù)組要想按順序存儲(chǔ)到計(jì)算機(jī)存儲(chǔ)單元中就必須有一個(gè)排列順序問(wèn)題。對(duì)于二維數(shù)組,有兩種排列形式：一種是___________；另一種是_____________。4．對(duì)于需要壓縮存儲(chǔ)的矩陣可以分為_(kāi)_________和_________。對(duì)那些具有相同值元素或零元素在矩陣中分布具有一定規(guī)律的矩陣,我們稱(chēng)之為_(kāi)__________；而對(duì)于那些零元素?cái)?shù)目遠(yuǎn)遠(yuǎn)多于非零元素?cái)?shù)目,并且非零元素的分布沒(méi)有規(guī)律的矩陣稱(chēng)為_(kāi)____________。5．在一個(gè)n階方陣a中,若元素滿(mǎn)足性質(zhì)：aij＝aji〔0<=i,j<=n-l,則稱(chēng)A為n階_______。6．采用順序存儲(chǔ)結(jié)構(gòu)表示三元組表<TropeTable>,以實(shí)現(xiàn)對(duì)稀疏矩陣的一種壓縮存儲(chǔ)形式,稱(chēng)為_(kāi)_____________,簡(jiǎn)稱(chēng)________________表。7．________________運(yùn)算是矩陣運(yùn)算中最基本的一項(xiàng),它是將一個(gè)m*n的矩陣變成另外一個(gè)n*m的矩陣,同時(shí)使原來(lái)矩陣中元素的行和列的位置互換而值保持不變。8．廣義表是n〔n>=0個(gè)元素的序列。記作：A＝〔a1,a2,…,an,其中,A是廣義表的_________,n是它的_________,當(dāng)n=0的時(shí)候稱(chēng)為_(kāi)___________。9．在一個(gè)非空的廣義表中,其元素ai可以是某一確定類(lèi)型的單個(gè)元素,稱(chēng)為_(kāi)_________,也可以又是一個(gè)廣義表,稱(chēng)為_(kāi)____________________。10．廣義表的定義是一種遞歸的定義,廣義表是一種遞歸的數(shù)據(jù)結(jié)構(gòu)。當(dāng)廣義表非空的時(shí)候,稱(chēng)第一個(gè)元素a1為廣義表A的__________,稱(chēng)其余元素組成的表〔a2,a3,…,an是A的______________。11．廣義表的深度一般定義為廣義表元素_________,或者說(shuō)是廣義表___________。利用遞歸的定義,廣義表的深度就是所有子表中_________________________。1.相同類(lèi)型數(shù)據(jù)、地址連續(xù)2.數(shù)組元素、數(shù)組元素、維數(shù)3.以行序?yàn)橹?、以列序?yàn)橹?.特殊矩陣、稀疏矩陣、特殊矩陣、稀疏矩陣5.對(duì)稱(chēng)矩陣6.三元組順序表、三元組7.矩陣轉(zhuǎn)置8.名稱(chēng)、長(zhǎng)度、空表9.原子、子表10.表頭、表尾11.最大的層數(shù)、括號(hào)的重?cái)?shù)、最大深度加1三、判斷題1．十字鏈表不是順序存儲(chǔ)結(jié)構(gòu)?！?．三元組表不是一個(gè)隨機(jī)存取結(jié)構(gòu)?！?．稀疏矩陣壓縮存儲(chǔ)后,必然會(huì)失去隨機(jī)存取功能?！?．若一個(gè)廣義表的表頭為空表,則此廣義表也為空表?！?．廣義表是線(xiàn)性表的推廣,是一類(lèi)線(xiàn)性數(shù)據(jù)結(jié)構(gòu)?！?．任何一個(gè)非空廣義表,其表頭可能是單元素或廣義表,其表尾必定是廣義表?！?．一個(gè)稀疏矩陣Am*n采用三元組形式表示,若把三元組中有關(guān)行下標(biāo)與列下標(biāo)的值互換,并把m和n的值互換,則就完成了Am*n的轉(zhuǎn)置運(yùn)算。〔8．?dāng)?shù)組中每個(gè)元素必定具有相同的數(shù)據(jù)類(lèi)型?！?．線(xiàn)性表是廣義表的特例?！?0．如果廣義表中的每個(gè)元素都是原子,則廣義表便成為線(xiàn)性表。〔11．廣義表中原子個(gè)數(shù)即為廣義表的長(zhǎng)度?！?2．廣義表最大子表的深度為廣義表的深度?！?3．廣義表中元素最大的層數(shù)稱(chēng)為廣義表的深度?！?4．廣義表是一種多層次結(jié)構(gòu)?！?5．廣義表是一種線(xiàn)性結(jié)構(gòu)?！?6．廣義表是一種共享結(jié)構(gòu)?！?7．廣義表是一種遞歸結(jié)構(gòu)?！?8．廣義表是一種單鏈表結(jié)構(gòu)?！?.正確：十字鏈表是鏈接存儲(chǔ)結(jié)構(gòu)。2.正確：具有存取任一元素的時(shí)間相等這一特點(diǎn)的存儲(chǔ)結(jié)構(gòu)稱(chēng)為隨機(jī)存取結(jié)構(gòu),三元組表存儲(chǔ)矩陣的時(shí)候,要訪問(wèn)第i行j列元素必須掃描三元組表,顯然查找三元組表前面的元素與后面元素所耗費(fèi)的時(shí)間不同,因此三元組表不是一個(gè)隨機(jī)存取結(jié)構(gòu)。3.正確：隨機(jī)存取結(jié)構(gòu)是指存取任一元素的時(shí)間相等這一特點(diǎn)的存儲(chǔ)結(jié)構(gòu),對(duì)稀疏矩陣壓縮存儲(chǔ)所用的存儲(chǔ)結(jié)構(gòu)是十字鏈表和三元組,而這兩種存儲(chǔ)結(jié)構(gòu)都不是隨機(jī)存取結(jié)構(gòu)。4.錯(cuò)誤：如廣義表L=<<>,<A,B>>為非空,而表頭為空表。5.錯(cuò)誤：廣義表是線(xiàn)性表的推廣,是一類(lèi)非線(xiàn)性數(shù)據(jù)結(jié)構(gòu)。6.正確：表尾的定義是除表頭元素以外其余元素〔可以為空構(gòu)成的表,所以必定是廣義表。7.錯(cuò)誤：應(yīng)該在互換行列后再按照行優(yōu)先重新存儲(chǔ)。8.正確。9.正確。10.正確。11.錯(cuò)誤：廣義表中元素個(gè)數(shù)為廣義表的長(zhǎng)度。12.錯(cuò)誤：廣義表最大子表的深度加1為廣義表的深度。13.正確。14.正確。15.錯(cuò)誤：廣義表是一種非線(xiàn)性結(jié)構(gòu)。16.正確。17.正確。18.正確：注意單鏈表結(jié)構(gòu)不一定是線(xiàn)性的。第六章樹(shù)和二叉樹(shù)一、選擇題l．在二叉樹(shù)后序遍歷中,任一個(gè)結(jié)點(diǎn)均在其子女結(jié)點(diǎn)后面,這種說(shuō)法〔。A．正確B．不正確C．無(wú)法判斷D．以上均不對(duì)2．在二叉樹(shù)先序遍歷中,任一個(gè)結(jié)點(diǎn)均在其子女結(jié)點(diǎn)前面,這種說(shuō)法〔。A．正確B．不正確C．無(wú)法判斷D．以上均不對(duì)3．設(shè)深度為h的二叉樹(shù)上只有葉子結(jié)點(diǎn)和同時(shí)具有左右子樹(shù)的結(jié)點(diǎn),則此類(lèi)二叉樹(shù)中所包含的結(jié)點(diǎn)數(shù)目至少為〔。A．2hB．2hC．2h＋1D．2h-l4．二叉村第k層上最多有〔個(gè)結(jié)點(diǎn)。A．2kB．2k-1C．2k-1D．2k+15．二叉樹(shù)的深度為k,則二叉樹(shù)最多有〔個(gè)結(jié)點(diǎn)。A．2kB．2k-1C．2k-1D．2k-16．設(shè)某一二叉樹(shù)先序遍歷為abdec,中序遍歷為dbeac,則該二叉樹(shù)后序遍歷的順序是〔。A．a(chǎn)bdecB．debacC．debcaD．a(chǎn)bedc7．設(shè)某一二叉樹(shù)中序遍歷為badce,后序遍歷為bdeca,則該二叉樹(shù)先序遍歷的順序是〔。A．a(chǎn)dbecB．decabC．debacD．a(chǎn)bode8．將一棵樹(shù)T轉(zhuǎn)換為一棵二叉樹(shù)T2,則T的先序遍歷是T2的〔。A．先序B．中序C．后序D．無(wú)法確定9．將一棵樹(shù)T轉(zhuǎn)換為一棵二叉樹(shù)T2,則T的后序遍歷是T2的〔。A．先序B．中序C．后序D．無(wú)法碉定l0．樹(shù)最適合于用來(lái)表示〔。A．線(xiàn)性結(jié)構(gòu)的數(shù)據(jù)B．順序結(jié)構(gòu)的數(shù)據(jù)C．元素之間無(wú)前驅(qū)和后繼關(guān)系的數(shù)據(jù)D．元素之間有包含和層次關(guān)系的數(shù)據(jù)11．二叉樹(shù)的葉子結(jié)點(diǎn)在先序、中序和后序遍歷過(guò)程中的相對(duì)秩序〔。A．發(fā)生改變B．不發(fā)生改變C．無(wú)法確定D．以上均不正確12．設(shè)一棵二叉樹(shù)度為2的結(jié)點(diǎn)數(shù)是7,度為1的結(jié)點(diǎn)數(shù)是6,則葉子結(jié)點(diǎn)數(shù)是〔。A．6B．7C．8D．913．用順序存儲(chǔ)的方法,將完全二叉樹(shù)中所有結(jié)點(diǎn)按層逐個(gè)從左到右的順序存放在一維數(shù)組R[1．．n]中,若結(jié)點(diǎn)R[i]有左孩子,則其左孩子是〔。A．R[2i-1]B．R[2i+1]C．R[2i]D．R[2/i]144．用順序存儲(chǔ)的方法,將完全二叉樹(shù)中所有結(jié)點(diǎn)按層逐個(gè)從左到右的順序存放在一維數(shù)組R[1．．n]中,若結(jié)點(diǎn)R[i]有右孩子,則其右孩子是〔。A．R[2i-1]B．R[2i＋l]C．R[2i]D．R[2/i]15．一棵非空的二叉樹(shù),先序遍歷與后序遍歷正好相反,則該二叉樹(shù)滿(mǎn)足〔。A．無(wú)左孩子B．無(wú)右孩子C．只有一個(gè)葉子結(jié)點(diǎn)D．任意二叉樹(shù)16．設(shè)a、b為一棵二叉樹(shù)的兩個(gè)結(jié)點(diǎn),在后序遍歷中,a在b前的條件是〔。A．a(chǎn)在b上方B．a(chǎn)在b下方C．a(chǎn)在b左方D．a(chǎn)在b右方17．線(xiàn)索二叉樹(shù)是一種〔。A．邏輯結(jié)構(gòu)B．線(xiàn)性結(jié)構(gòu)C．邏輯和線(xiàn)性結(jié)構(gòu)D．物理結(jié)構(gòu)18．N個(gè)結(jié)點(diǎn)的線(xiàn)索二叉樹(shù)中,線(xiàn)索的數(shù)目是〔。A．N-1B．N＋1C．2ND．2N－119．權(quán)值為｛l,2,6,8｝的四個(gè)結(jié)點(diǎn)構(gòu)成的哈夫曼樹(shù)的帶權(quán)路徑長(zhǎng)度是〔。A．18B．28C．19D．2920．實(shí)現(xiàn)任意二叉樹(shù)的后序遍歷的非遞歸算法而不使用棧結(jié)構(gòu),最佳方案是二叉村采用〔存儲(chǔ)結(jié)構(gòu)。A．二叉鏈表B．廣義表存儲(chǔ)結(jié)構(gòu)C．三叉鏈表D．順序存儲(chǔ)結(jié)構(gòu)21．對(duì)一個(gè)滿(mǎn)二叉樹(shù),m個(gè)樹(shù)葉,k個(gè)分枝結(jié)點(diǎn),n個(gè)結(jié)點(diǎn),則〔。A．n＝m＋1B．m+1=2nC．m＝k-1D．n=2k+123．具有五層結(jié)點(diǎn)的二叉平衡樹(shù)至少有〔個(gè)結(jié)點(diǎn)。A．10B．12C．15D．1724．設(shè)n,m為一棵二叉樹(shù)上的二個(gè)結(jié)點(diǎn),在中序遍歷時(shí),n在m前的條件是〔。A．n在m右方B．n是m祖先C．n在m左方D．n是m子孫25．線(xiàn)索二又樹(shù)是一種〔結(jié)構(gòu)。A．邏輯B．邏輯和物理C．物理D．線(xiàn)性26．將一棵有100個(gè)結(jié)點(diǎn)的完全二又樹(shù)從根這一層開(kāi)始,每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào),根結(jié)點(diǎn)的編號(hào)為1,則編號(hào)為49的結(jié)點(diǎn)的左孩子編號(hào)為〔。A．98B．99C．50D．48二、填空題1．樹(shù)<Tree>是n<n≥0>個(gè)結(jié)點(diǎn)的_____________集。2．任何一個(gè)非空樹(shù)中：有且僅有一個(gè)特定的結(jié)點(diǎn),稱(chēng)為該樹(shù)的______________的結(jié)點(diǎn),___________結(jié)點(diǎn)之外的其余結(jié)點(diǎn)可分為m<m≥0>個(gè)互不相交的有限集合T1,T2,…,Tm,且其中每一個(gè)集合又是一棵樹(shù),稱(chēng)之為_(kāi)_________的______________。3．樹(shù)的__________是指一個(gè)數(shù)據(jù)元素及指向其子樹(shù)的分支。通常通過(guò)一個(gè)__________來(lái)描述,在樹(shù)型表示中,用一個(gè)圓圈及短線(xiàn)表示。4．結(jié)點(diǎn)的度是指結(jié)點(diǎn)所擁有的________________。5．樹(shù)內(nèi)各結(jié)點(diǎn)度的___________________為樹(shù)的度。6．度大于0的結(jié)點(diǎn)稱(chēng)為_(kāi)_______________或______________________。7．____________稱(chēng)為葉子結(jié)點(diǎn),簡(jiǎn)稱(chēng)為葉子,又稱(chēng)作終端結(jié)點(diǎn)。8．一個(gè)結(jié)點(diǎn)的____________,或者說(shuō)一個(gè)結(jié)點(diǎn)的____________稱(chēng)為該結(jié)點(diǎn)的孩子結(jié)點(diǎn),簡(jiǎn)稱(chēng)為孩子。9．一個(gè)結(jié)點(diǎn)稱(chēng)為其后繼結(jié)點(diǎn)〔即孩子結(jié)點(diǎn)的______________。10．一個(gè)結(jié)點(diǎn)的子樹(shù)中的任一結(jié)點(diǎn)都稱(chēng)為該結(jié)點(diǎn)的_______________。11．從根到該結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)稱(chēng)為該結(jié)點(diǎn)的_____________。12．具有_____________________的結(jié)點(diǎn)互稱(chēng)為兄弟結(jié)點(diǎn),簡(jiǎn)稱(chēng)為兄弟。13．從根結(jié)點(diǎn)開(kāi)始定義,根為_(kāi)_______層,根的孩子為_(kāi)_________層,依次往下類(lèi)推,若某結(jié)點(diǎn)在第k層,則其子樹(shù)的根就在______________層。14．其雙親在同一層次上的結(jié)點(diǎn)互稱(chēng)為_(kāi)__________________。15．樹(shù)中結(jié)點(diǎn)的___________稱(chēng)為樹(shù)的深度,又稱(chēng)為樹(shù)的高度。16．如果樹(shù)中各結(jié)點(diǎn)的各子樹(shù)從左至右是有序排列,不可互換的,則稱(chēng)該樹(shù)為_(kāi)_____。17．如果樹(shù)中各結(jié)點(diǎn)的各子樹(shù)無(wú)排列順序,即可以互換位置,則稱(chēng)為該樹(shù)為_(kāi)________。18．n<n≥0>棵互不相交的樹(shù)的集合稱(chēng)為_(kāi)_____________________。19．二又樹(shù)〔BinaryTree是結(jié)點(diǎn)的有限集合,這個(gè)集合或者是空,或者是由一個(gè)根結(jié)點(diǎn)和__________的稱(chēng)為_(kāi)_____________和____________的二叉樹(shù)構(gòu)成。20．二叉樹(shù)第i層上最多有____________個(gè)結(jié)點(diǎn)。21．深度為k的二又樹(shù)最多有____________個(gè)結(jié)點(diǎn)<k≥l>。22．在任意二叉樹(shù)中,葉子結(jié)點(diǎn)的數(shù)目<即度為0的結(jié)點(diǎn)數(shù)>等于度為2的結(jié)點(diǎn)數(shù)____________。23．一棵深度為k且具有2k-1個(gè)結(jié)點(diǎn)的二叉樹(shù)稱(chēng)為_(kāi)_________。這類(lèi)二叉樹(shù)的特點(diǎn)是,二叉樹(shù)中每一層結(jié)點(diǎn)的個(gè)數(shù)都是______________的個(gè)數(shù)。24．_________是那種在一棵二叉樹(shù)中,除最后一層外,若其余層都是滿(mǎn)的,并且最后一層或者是滿(mǎn)的,或者所缺少的結(jié)點(diǎn)都在右邊。25．具有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的深度是_______________。26．對(duì)于一棵有n個(gè)結(jié)點(diǎn)的完全二叉樹(shù)的結(jié)點(diǎn)進(jìn)行編號(hào)〔自上而下,自左至右,則對(duì)任一結(jié)點(diǎn)i〔l≤i≤n,如果結(jié)點(diǎn)i=l,則結(jié)點(diǎn)i是二叉樹(shù)的____________,無(wú)雙親；如果結(jié)點(diǎn)i>l,則其雙親Parent<i>的序號(hào)是結(jié)點(diǎn)_______________；如果2i≤n,則結(jié)點(diǎn)i的左孩子Lchild<BT,,i是_________,否則結(jié)點(diǎn)i無(wú)左孩子<結(jié)點(diǎn)i必為葉子結(jié)點(diǎn)>；如果2i＋l≤n,則結(jié)點(diǎn)i的右孩子RChild〔BT,i的序號(hào)是____________；否則該結(jié)點(diǎn)無(wú)右孩子。27．二叉樹(shù)的順序存儲(chǔ)結(jié)構(gòu)是用_________________存儲(chǔ)二叉樹(shù)的數(shù)據(jù)元素。28．____________是指按照某條搜索路徑訪問(wèn)樹(shù)中的某個(gè)結(jié)點(diǎn),使得樹(shù)中每個(gè)結(jié)點(diǎn)均被訪問(wèn)一次,而且僅被訪問(wèn)一次。29．先序遍歷二叉樹(shù)的操作定義為：若二叉樹(shù)為空,則為空操作；否則進(jìn)行如下操作：訪問(wèn)二叉樹(shù)____________；先序遍歷二叉樹(shù)____________；先序遍歷二叉樹(shù)_________。30．中序遍歷二叉樹(shù)的操作定義為：若二叉樹(shù)為空,則為空操作；否則進(jìn)行如下操作：中序遍歷二叉樹(shù)__________；訪問(wèn)二又樹(shù)__________；中序遍歷二又樹(shù)____________。31．后序遍歷二叉樹(shù)的操作定義為：若二叉樹(shù)為空,則為空操作；否則進(jìn)行如下操作：后序遍歷二叉樹(shù)___________；后序遍歷二叉樹(shù)_________；訪問(wèn)二叉樹(shù)_____________。32．線(xiàn)索二叉樹(shù)〔ThreadedBinaryTree是充分利用二義鏈表的n+1個(gè)空的指針域作為線(xiàn)索來(lái)標(biāo)志每一個(gè)結(jié)點(diǎn)的________和__________信息。當(dāng)某個(gè)結(jié)點(diǎn)有左孩子的時(shí)候,使其___________指向其左孩子,無(wú)左孩子的時(shí)候,使其左指針域指向該結(jié)點(diǎn)的___________；當(dāng)某個(gè)結(jié)點(diǎn)有有孩子的時(shí)候,使其右指針域指向該結(jié)點(diǎn)的__________,無(wú)右孩子的時(shí)候,使其有指針域指向該結(jié)點(diǎn)的_____________。33．線(xiàn)索二叉樹(shù)的線(xiàn)索鏈表中,指向結(jié)點(diǎn)前驅(qū)和后繼的指針?lè)Q為_(kāi)__________；加上線(xiàn)索的二叉樹(shù)稱(chēng)為_(kāi)____________；對(duì)二叉樹(shù)以某種次序進(jìn)行遍歷使其成為線(xiàn)索二叉樹(shù)的過(guò)程稱(chēng)為_(kāi)______________________。34．樹(shù)的存儲(chǔ)結(jié)構(gòu)常見(jiàn)的有____________、____________和________________。35．樹(shù)的先序遍歷過(guò)程如下：若樹(shù)為空,則進(jìn)行空操作；若樹(shù)非空,則：訪問(wèn)樹(shù)的__________；依次先序遍歷樹(shù)的__________。36．樹(shù)的后序遍歷過(guò)程為：若樹(shù)為空,則進(jìn)行空操作；若樹(shù)非空,則：依次后序遍歷__________；訪問(wèn)_________________。37．森林的先序遍歷過(guò)程為：若森林非空,則：〔1訪問(wèn)森林中第一棵樹(shù)的___________?！?先序遍歷第一棵樹(shù)中_____________?！?先序遍歷_______________________。38．森林的后序遍歷過(guò)程為：若森林非空,則：〔l后序遍歷森林中第一棵樹(shù)的_______________。〔2訪問(wèn)第一棵樹(shù)的_________________________?！?后序遍歷_______________________________。39．從樹(shù)中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之間的_________稱(chēng)為這兩個(gè)結(jié)點(diǎn)的路徑。40．路徑上的分支數(shù)目稱(chēng)為_(kāi)_____________。41．樹(shù)的路徑長(zhǎng)度是指從樹(shù)根到每一結(jié)點(diǎn)的__________________。42．將樹(shù)中的結(jié)點(diǎn)賦上一個(gè)有著某種意義的實(shí)數(shù),稱(chēng)此實(shí)數(shù)為該結(jié)點(diǎn)的____________。43．樹(shù)的帶權(quán)路徑長(zhǎng)度為樹(shù)中所有葉子結(jié)點(diǎn)的____________。44．哈夫曼樹(shù)〔HuffmanTree又稱(chēng)___________。它是n個(gè)帶權(quán)葉子結(jié)點(diǎn)構(gòu)成的所有二叉樹(shù)中,帶權(quán)路徑長(zhǎng)度WPL__________________。45,所謂前綴編碼是指在所有對(duì)字符的編碼中,任何一個(gè)字符都不是____________。46．已知完全二叉樹(shù)的第八層有8個(gè)結(jié)點(diǎn),則其葉子結(jié)點(diǎn)數(shù)是__________________。47．在有n個(gè)葉子結(jié)點(diǎn)的哈夫曼樹(shù)中,總結(jié)點(diǎn)數(shù)是___________。48．已知完全二又樹(shù)的第7層有10個(gè)葉子結(jié)點(diǎn),則整個(gè)二又樹(shù)的結(jié)點(diǎn)數(shù)最多是__________。49．已知二叉樹(shù)中葉子數(shù)為50,僅有一個(gè)孩子的結(jié)點(diǎn)數(shù)為30,則總結(jié)點(diǎn)數(shù)為_(kāi)_________。50．一棵樹(shù)T采用二叉鏈表BT存儲(chǔ),如果樹(shù)T中某結(jié)點(diǎn)為葉子結(jié)點(diǎn),則在二叉鏈表BT中所對(duì)應(yīng)的結(jié)點(diǎn)一定滿(mǎn)足___________________。51．在二叉鏈表中,判斷某指針P所指結(jié)點(diǎn)為葉子結(jié)點(diǎn)的條件是__________。52．若以{4,5,6,7,8}作為葉子結(jié)點(diǎn)的權(quán)值構(gòu)造哈夫曼樹(shù),則其帶權(quán)路徑長(zhǎng)度是___________。53．已知二叉樹(shù)有50個(gè)葉子結(jié)點(diǎn),則該二叉樹(shù)的總結(jié)點(diǎn)數(shù)至少是______________。54．3個(gè)結(jié)點(diǎn)可構(gòu)成___________________棵不同形態(tài)的樹(shù)。55．已知完全二叉樹(shù)的第七層有8個(gè)結(jié)點(diǎn),則其葉子結(jié)點(diǎn)數(shù)是______________.56．將一棵有100個(gè)結(jié)點(diǎn)的完全二叉樹(shù)從根這一層開(kāi)始,每一層上從左到右依次對(duì)結(jié)點(diǎn)進(jìn)行編號(hào),根結(jié)點(diǎn)的編號(hào)為1,則編號(hào)為49的結(jié)點(diǎn)的左孩子編號(hào)為_(kāi)___________。57．若要對(duì)某二叉排序樹(shù)進(jìn)行遍歷,保證輸出的所有結(jié)點(diǎn)序列按鍵值遞增次序排列,應(yīng)對(duì)該二叉樹(shù)采用_______________遍歷法。1.有限2.根、根、根、子樹(shù)3.結(jié)點(diǎn)、記錄4.子樹(shù)數(shù)目5.最大值6.分支結(jié)點(diǎn)、非終端結(jié)點(diǎn)7.度為零的結(jié)點(diǎn)8.后繼結(jié)點(diǎn)、子樹(shù)的根9.雙親結(jié)點(diǎn)10.子孫結(jié)點(diǎn)11.祖先結(jié)點(diǎn)12.同一雙親13.第一、第二、第k+114.堂兄弟15.最大層次16.有序樹(shù)17.無(wú)序樹(shù)18.森林19.兩棵互不相交、左子樹(shù)、右子樹(shù)20.2i-121.2k-122.加123.滿(mǎn)二叉樹(shù)、最大結(jié)點(diǎn)24.完全二叉樹(shù)25.26.根、、2i、2i+127.一組連續(xù)的存儲(chǔ)單元28.遍歷二叉樹(shù)29.根結(jié)點(diǎn)、左子樹(shù)、右子樹(shù)30.左子樹(shù)、根結(jié)點(diǎn)、右子樹(shù)31.左子樹(shù)、右子樹(shù)、根結(jié)點(diǎn)32.前驅(qū)、后繼、左指針域、直接前驅(qū)結(jié)點(diǎn)、右孩子、直接后繼結(jié)點(diǎn)33.線(xiàn)索、線(xiàn)索二叉樹(shù)、線(xiàn)索化34.雙親表示法、孩子表示法、孩子兄弟表示法35.根結(jié)點(diǎn)、各子樹(shù)36.根的各子樹(shù)、根結(jié)點(diǎn)37.根結(jié)點(diǎn)、根結(jié)點(diǎn)的子樹(shù)、除第一棵樹(shù)之外剩余的樹(shù)構(gòu)成的森林38.根結(jié)點(diǎn)的子樹(shù)、根結(jié)點(diǎn)、除第一棵樹(shù)之外剩余的樹(shù)構(gòu)成的森林39.分支40.路徑長(zhǎng)度41.路徑長(zhǎng)度之和42.權(quán)43.帶權(quán)路徑長(zhǎng)度之和44.最優(yōu)二叉樹(shù)、最小的二叉樹(shù)45.另一個(gè)字符的前綴46.6847.2n-148.7449.12950.左子樹(shù)為空51.<p->lchild==nil>&&<p->rchild==nil>52.6953.9954.255.3656.9857.中序三、判斷題1．完全二叉樹(shù)的某個(gè)結(jié)點(diǎn)若無(wú)左孩子,則它必然是葉結(jié)點(diǎn)?！?．存在這樣一種二叉樹(shù),對(duì)它采用任何次序的遍歷結(jié)果相同?！?．度為二的樹(shù)稱(chēng)為二叉樹(shù)?！病?．二叉樹(shù)中不存在度大于2的結(jié)點(diǎn)?！?．當(dāng)二叉樹(shù)中某個(gè)結(jié)點(diǎn)只有一棵子樹(shù)的時(shí)候,無(wú)左右子樹(shù)之分?！病?．任何一棵二叉樹(shù)都可以不用棧實(shí)現(xiàn)前序線(xiàn)索樹(shù)的前序遍歷?！?．哈夫曼編碼是一種前綴編碼,不允許出現(xiàn)兩個(gè)字符編碼相同的情況。〔8．完全二叉樹(shù)某結(jié)點(diǎn)有右子樹(shù),則必然有左子樹(shù)。〔9．前序遍歷一棵二叉樹(shù)的結(jié)點(diǎn)就可以得到排好序的結(jié)點(diǎn)序列。〔×10．將一棵擁有子樹(shù)的樹(shù)轉(zhuǎn)換為二叉樹(shù)后,根結(jié)點(diǎn)可能沒(méi)有左子樹(shù)?！病?1．根據(jù)二叉樹(shù)的前序遍歷和中序遍歷可以得到二又樹(shù)的后序遍歷?！?2．哈夫曼樹(shù)是帶權(quán)路徑長(zhǎng)度最短的二叉樹(shù)。〔13．哈夫曼樹(shù)上權(quán)值較大的結(jié)點(diǎn)離根較遠(yuǎn)?！病?4．中序遍歷森林與后序遍歷與森林相對(duì)應(yīng)的二叉樹(shù)結(jié)果相同?！病?5．在二叉樹(shù)中,具有一個(gè)孩子的結(jié)點(diǎn),在中序遍歷序列中,沒(méi)有后繼子女結(jié)點(diǎn)?！病?6．先序遍歷森林與先序遍歷相對(duì)應(yīng)的二叉樹(shù)結(jié)果不同?！病?7．若一棵二叉樹(shù)的任一非葉子結(jié)點(diǎn)的度為2,則該二叉樹(shù)為滿(mǎn)二叉樹(shù)?！病?8．二叉樹(shù)只能采用二叉鏈表來(lái)存儲(chǔ)?！病?9．給定結(jié)點(diǎn)數(shù)的平衡二叉樹(shù)的高度是惟一的?！病?.正確：根據(jù)完全二叉樹(shù)定義可以知道,若完全二叉