智慧樹知到《算法與數(shù)據(jù)結(jié)構(gòu)》章節(jié)測試答案

智慧樹知到算法與數(shù)據(jù)結(jié)構(gòu)章節(jié)測試答案 智慧樹知到算法與數(shù)據(jù)結(jié)構(gòu)章節(jié)測試答案緒論1、數(shù)據(jù)結(jié)構(gòu)是一門研究非數(shù)值計(jì)算的程序設(shè)計(jì)問題中計(jì)算機(jī)的數(shù)據(jù)元素以及它們之間的_和運(yùn)算等的學(xué)科。A:結(jié)構(gòu)B:算法C:關(guān)系D:運(yùn)算正確答案：關(guān)系2、算法的描述形式包括A:自然語言B:流程圖C:類程序設(shè)計(jì)語言D:N-S圖正確答案：自然語言,流程圖 ,類程序設(shè)計(jì)語言,N-S圖3、算法的特征包括有窮性、確定性、可行性和輸入輸出。A:對B:錯(cuò)正確答案：對4、對算法的描述包括程序形式和描述形式。A:對B:錯(cuò)正確答案：對5、描述形式是算法的最終形式A:對B:錯(cuò)正確答案：錯(cuò)6、"數(shù)據(jù)結(jié)構(gòu)'是介于( )、( )和( )三者之間的一門核心課程。A:數(shù)學(xué)B:計(jì)算機(jī)硬件C:計(jì)算機(jī)軟件D:語句正確答案：數(shù)學(xué),計(jì)算機(jī)硬件,計(jì)算機(jī)軟件7、 著名計(jì)算機(jī)科學(xué)家沃思教授提出的公式： 程序 = ( ) + ( )，也說明了數(shù)據(jù)結(jié)構(gòu)的重要性。A:算法B:語法C:數(shù)據(jù)結(jié)構(gòu)D:編程環(huán)境正確答案：算法,數(shù)據(jù)結(jié)構(gòu)8、描述非數(shù)值計(jì)算問題的數(shù)學(xué)模型不再是數(shù)學(xué)方程，而是數(shù)據(jù)結(jié)構(gòu)( )。A:表B:樹C:圖D:集合正確答案：表,樹,圖,集合9、 數(shù)據(jù)結(jié)構(gòu)是一門研究( )程序設(shè)計(jì)問題中計(jì)算機(jī)的( )以及它們之間的( )和( )等的學(xué)科。A:非數(shù)值計(jì)算B:操作對象C:關(guān)系D:操作正確答案：非數(shù)值計(jì)算,操作對象,關(guān)系,操作10、 順序存儲結(jié)構(gòu): 借助元素在存儲器中的( )來表示數(shù)據(jù)元素間的邏輯關(guān)系。A:地址B:結(jié)構(gòu)C:相對位置D:數(shù)值正確答案：相對位置第一章1、（）是一種最簡單的線性結(jié)構(gòu)。A:圖B:線性表C:樹D:集合正確答案：線性表2、（ ）線性表的數(shù)據(jù)元素可以由所描述對象的各種特征的數(shù)據(jù)項(xiàng)組成。A:有序存儲B:散列存儲C:鏈?zhǔn)酱鎯:順序存儲正確答案：鏈?zhǔn)酱鎯?、已知單向鏈表中指針p指向結(jié)點(diǎn)A，( ）表示刪除A的后繼結(jié)點(diǎn)（若存在）的鏈操作（不考慮回收）。A:pnext=pB:p=pnextC:p=pnextnextD:pnext=pnextnext正確答案：pnext=pnextnext4、已知last指向單向簡單鏈表的尾結(jié)點(diǎn)，將s所指結(jié)點(diǎn)加在表尾，不正確的操作是。A:s-next=NULL, last-next=s,last=s;B:s-next=NULL, last-next=s, s=last;C:last-next=s,s-next=NULL,last=s;D:last-next=s,last=s,last-next=NULL;正確答案：s-next=NULL, last-next=s, s=last;5、已知h是指向單向加頭鏈表的首指針，刪除表頭結(jié)點(diǎn)的操作是_。A:p=h-next;free(p);h=h-next;B:free(h-next);h=h-next;C:p=h,h=p-next;free(p);D:p=h-next,h-next=p-next;free(p);正確答案：p=h-next,h-next=p-next;free(p);6、有N個(gè)元素組成的線性表，我們說此線性表的長度為（ ）A:nB:n+1C:n-1D:0正確答案：n7、對線性表中的數(shù)據(jù)元素進(jìn)行（ ）和（ ）等操作，實(shí)現(xiàn)表的長度的增長或縮短。A:插入B:遍歷C:訪問D:刪除正確答案：插入,刪除8、線性表的抽象數(shù)據(jù)類型定義A:數(shù)據(jù)對象B:函數(shù)關(guān)系C:數(shù)據(jù)關(guān)系D:基本操作正確答案：數(shù)據(jù)對象,數(shù)據(jù)關(guān)系,基本操作9、我們使用（ ），實(shí)現(xiàn)線性表的順序存儲。A:數(shù)值B:函數(shù)C:數(shù)組D:語句正確答案：數(shù)組10、線性表的基本操作是用C語言中的（ ）對其進(jìn)行表示的。A:循環(huán)語句B:函數(shù)C:結(jié)構(gòu)體D:條件語句正確答案：函數(shù)11、 在鏈表中第i 個(gè)結(jié)點(diǎn)之前插入新的元素 e ，表的邏輯結(jié)構(gòu)不變。A:對B:錯(cuò)正確答案：錯(cuò)12、在單鏈表中插入結(jié)點(diǎn)只需要（）。但同時(shí)，若要在第（ ）個(gè)結(jié)點(diǎn)之前插入元素，修改的是第 （ ）個(gè)結(jié)點(diǎn)的指針。A: iB:修改指針C:i+1D:i-1正確答案：i ,修改指針,i-113、單鏈表和線性表中所有基本操作相同，且編程實(shí)現(xiàn)方法相同。A:對B:錯(cuò)正確答案：錯(cuò)14、數(shù)字鐘程序中使用的時(shí)間，可以是系統(tǒng)時(shí)間。A:對B:錯(cuò)正確答案：對15、和單鏈表的差別僅在于，判別鏈表中最后一個(gè)結(jié)點(diǎn)的條件不再是( )，而是（ )。A:"后繼是否為頭結(jié)點(diǎn)'B:"前繼是否為頭結(jié)點(diǎn)'C:"前繼是否為空'D:"后繼是否為空'正確答案："后繼是否為頭結(jié)點(diǎn)',"后繼是否為空'16、雙向鏈表的"刪除' 時(shí)需要同時(shí)修改兩個(gè)方向上的指針,改變結(jié)點(diǎn)之間的邏輯關(guān)系。A:對B:錯(cuò)正確答案：對17、雙向鏈表的"插入' 時(shí)不需要同時(shí)修改兩個(gè)方向上的指針,改變結(jié)點(diǎn)之間的邏輯關(guān)系。A:對B:錯(cuò)正確答案：錯(cuò)18、 雙向鏈表中，當(dāng)指針p指向非空表中的非頭尾結(jié)點(diǎn)時(shí)，以下哪個(gè)式子是正確的（）A:p-next-prior=pB:p=p-nextC:p-next =p-priorD:p=p-prior-next正確答案：p-next-prior=p ,p=p-prior-next19、 雙向鏈表中，當(dāng)指針p指向非空表中的非頭尾結(jié)點(diǎn)時(shí)，以下哪個(gè)式子是正確的（）A:p-next=p -priorB:p-prior=p-nextC:p-next-prior=pD:p=p-prior正確答案：p-next-prior=p20、 雙向鏈表需要在結(jié)點(diǎn)中設(shè)兩個(gè)指針域( )A:parent指針域B:prior指針域C:數(shù)據(jù)域D:next指針域正確答案：prior指針域,next指針域第二章1、隊(duì)列是一種（ ）的線性表。A:先進(jìn)先出B:先進(jìn)后出C:只能插入D:只能刪除正確答案：先進(jìn)先出2、設(shè)指針變量front表示鏈?zhǔn)疥?duì)列的隊(duì)頭指針，指針變量rear表示鏈?zhǔn)疥?duì)列的隊(duì)尾指針，指針變量s指向?qū)⒁腙?duì)列的結(jié)點(diǎn)X，則入隊(duì)列的操作序列為（ ）。A: front-next=s；front=s；B: s-next=rear；rear=s；C: rear-next=s；rear=s；D: s-next=front；front=s；正確答案：rear-next=s；rear=s；3、棧操作數(shù)據(jù)的原則是（ ）。A:后進(jìn)先出B:先進(jìn)先出C:后進(jìn)后出D:不分順序正確答案：后進(jìn)先出4、棧與隊(duì)列是一種特殊操作的線性表（ ）A:對B:錯(cuò)正確答案：對5、和鏈棧類似，用單鏈表來實(shí)現(xiàn)鏈隊(duì)。根據(jù)隊(duì)的先入先出(FIFO)原則，為了操作上的方便，使用一個(gè)( )和( )。A:數(shù)據(jù)域B:頭指針C:尾指針D:指針域正確答案：頭指針,尾指針6、隊(duì)列的順序存儲結(jié)構(gòu)用C語言中（ ）數(shù)據(jù)類型實(shí)現(xiàn)。A:一維數(shù)組實(shí)現(xiàn)B:二維數(shù)組實(shí)現(xiàn)C:結(jié)構(gòu)體D:枚舉型正確答案：一維數(shù)組實(shí)現(xiàn)7、棧和隊(duì)列不能進(jìn)行再分配了。A:對B:錯(cuò)正確答案：錯(cuò)8、隊(duì)列允許在表的一端進(jìn)行插入操作和刪除操作。A:對B:錯(cuò)正確答案：錯(cuò)9、入棧需要修改地址指針。A:對B:錯(cuò)正確答案：對10、 鏈棧主要的運(yùn)算，如插入、刪除是在棧頂執(zhí)行的。 鏈表的頭部作棧頂是最方便的，需要像單鏈表那樣為了運(yùn)算方便附加一個(gè)頭結(jié)點(diǎn)。A:對B:錯(cuò)正確答案：錯(cuò)11、鏈棧的結(jié)點(diǎn)結(jié)構(gòu)與單鏈表的結(jié)點(diǎn)結(jié)構(gòu)相同，由（）和（）組成。A:指針域 雙親域B:數(shù)據(jù)域 指針域C:孩子域 指針域D:雙親域正確答案：數(shù)據(jù)域 指針域12、 構(gòu)造一個(gè)空棧S 時(shí)，不需要用動態(tài)存儲空間分配函數(shù)。A:對B:錯(cuò)正確答案：錯(cuò)13、順序棧中數(shù)據(jù)元素與棧頂指針的變化：非空棧中的棧頂指針top始終在的 （）下一個(gè)位置A:棧中任意元素B:棧頂元素C:棧底元素D:棧中元素正確答案：棧頂元素14、在初始化空順序棧時(shí)一般不限定棧的最大容量，因?yàn)?，棧在使用過程中所需最大空間的大小很難估計(jì)。A:對B:錯(cuò)正確答案：對15、利用（）的存儲單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，這種形式的棧稱為順序棧。A:一組地址相同B:一組地址不連續(xù)C:一組地址連續(xù)D:一組地址斷開正確答案：一組地址連續(xù)第三章1、串(即字符串)是一種特殊的線性表，它的數(shù)據(jù)元素是（ ）。A:數(shù)字B:單個(gè)字符C:圖D:表正確答案：B2、包含零個(gè)字符(n=0)的串稱為空串，通常記為，其長度為零；空串是任意串的子串。A:對B:錯(cuò)正確答案：A3、空串與空格串相同A:對B:錯(cuò)正確答案：B4、串比較是按字符的ASCII值比較的，而不是按串的長度比較的。 StrCompare(data, structures) _ 0；A:大于B:等于C:小于D:小于等于正確答案：C5、SubString( sub, commander, 1, 9) 求得 sub = _；A:commanrB:coanderC:commanderD:comander正確答案： C6、串的基本操作中，操作對象大多為"串的整體'。A:對B:錯(cuò)正確答案：A7、在串的表示和實(shí)現(xiàn)過程中，用一組地址不連續(xù)的存儲單元存儲串值中的字符序列，稱為串的定長順序存儲方式。A:對B:錯(cuò)正確答案：B8、在順序串中，用一個(gè)指針來指向最后一個(gè)字符，C語言的表示如下：typedef struct char dataMAXSIZE; int curlen; SeqString;請定義一個(gè)串變量：A: structg sB:typedef struct s；C:SqString s；D:SeqString s；正確答案：D9、在C語言中，存在一個(gè)稱為"堆'的自由存儲區(qū)，并由C語言的動態(tài)分配函數(shù)_來管理。A:malloc( )B:malloc( )和free( )C:free( )D:main()正確答案：B10、堆分配存儲結(jié)構(gòu)的串有順序存儲結(jié)構(gòu)的特點(diǎn)，在操作中對串長又沒有任何限制，因而在串處理的應(yīng)用程序中常被選用。A:對B:錯(cuò)正確答案：A第四章1、設(shè)按照從上到下、從左到右的順序從1開始對完全二叉樹進(jìn)行順序編號，則編號為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號為（ ）。A: 2i+1B: 2iC: i/2D:2i-1正確答案：B2、設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（ ）。A:空或只有一個(gè)結(jié)點(diǎn)B:高度等于其結(jié)點(diǎn)數(shù)C:任一結(jié)點(diǎn)無左孩子D:任一結(jié)點(diǎn)無右孩子正確答案：D3、二叉樹的第k層的結(jié)點(diǎn)數(shù)最多為( )A:2的k次冪-1B:2K+1C:2K-1D:2的k-1次冪正確答案：D4、設(shè)某棵二叉樹的中序遍歷序列為ABCD，前序遍歷序列為CABD，則后序遍歷該二叉樹得到序列為（ ）。A:BADCB:BCDAC:CDABD:CBDA正確答案：A5、滿二叉樹一定是完全二叉樹，完全二叉樹不一定是滿二叉樹。（ ）A:對B:錯(cuò)正確答案：A6、設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（ ）A:對B:錯(cuò)正確答案：B7、深度為k的完全二叉樹中最少有（ ）個(gè)結(jié)點(diǎn)。A: 2k-1-1B: 2k-1+1C: 2k-1正確答案：C8、設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為2的結(jié)點(diǎn)數(shù)為N2，則下列等式成立的是（ ）。A:N0=N1+1B:N0=Nl+N2C:N0=N2+1D:N0=2N1+l正確答案：C9、設(shè)二叉樹的先序遍歷序列和后序遍歷序列正好相反，則該二叉樹滿足的條件是（ ）。A:空或只有一個(gè)結(jié)點(diǎn)B:高度等于其結(jié)點(diǎn)數(shù)C: 任一結(jié)點(diǎn)無左孩子D:任一結(jié)點(diǎn)無右孩子正確答案：D10、 樹的帶權(quán)路徑長度定義為，樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長度之和(對所有葉子結(jié)點(diǎn))。（）A:對B:錯(cuò)正確答案：A第五章1、設(shè)某無向圖有n個(gè)頂點(diǎn)，則該無向圖的鄰接表中有（ ）個(gè)表頭結(jié)點(diǎn)。A:2nB:nC:n/2D: n(n-1)正確答案：B2、設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為（ ）。A:第i行非0或非元素的個(gè)數(shù)之和B:第i列非0或非元素的個(gè)數(shù)之和C:第i行0元素的個(gè)數(shù)之和D: 第i列0元素的個(gè)數(shù)之和正確答案：B3、設(shè)某完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有（ ）條邊A:n(n-1)/2B:n(n-1)C:n的2次冪D:n的2次冪-1正確答案：A4、 子串"ABC'在主串"AABCABCD'中的位置為2。( )A:對B:錯(cuò)正確答案：A5、 對鏈表進(jìn)行插入和刪除操作時(shí)不必移動鏈表中結(jié)點(diǎn)。( )A:對B:錯(cuò)正確答案：A6、深度為k的完全二叉樹中最少有（ ）個(gè)結(jié)點(diǎn)。A: 2k-1-1B: 2k-1+1C: 2k-1正確答案：C7、設(shè)某二叉樹中度數(shù)為0的結(jié)點(diǎn)數(shù)為N0，度數(shù)為1的結(jié)點(diǎn)數(shù)為Nl，度數(shù)為2的結(jié)點(diǎn)數(shù)為N2，則下列等式成立的是（ ）。A:N0=N1+1B:N0=Nl+N2C:N0=N2+1D:N0=2N1+l正確答案：C8、設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為（ ）。A:第i行非0或非元素的個(gè)數(shù)之和B:第i列非0或非元素的個(gè)數(shù)之和C:第i行0元素的個(gè)數(shù)之和D:第i列0元素的個(gè)數(shù)之和正確答案：B9、簡單回路就是回路。A:對B:錯(cuò)正確答案：B10、圖中任兩點(diǎn)有路徑相通，該圖稱為連通圖（）A:對B:錯(cuò)正確答案：A第六章1、時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（ ）。A: 堆排序B: 冒泡排序C: 希爾排序D:快速排序正確答案：A2、設(shè)一組權(quán)值集合W=2，3，4，5，6，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為（ ）。A:20B:30C:40D:45正確答案：D3、設(shè)一組權(quán)值集合W=2，3，4，5，6，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為（ ）A:20B:30C:40D:45正確答案：D4、 連通圖的最小生成樹的邊上的權(quán)值之和是唯一的。( )A:對B:錯(cuò)正確答案：A5、設(shè)某無向圖有n個(gè)頂點(diǎn)，則該無向圖的鄰接表中有（ ）個(gè)表頭結(jié)點(diǎn)。A:2nB:nC:n/2D: n(n-1)正確答案：B6、設(shè)用鄰接矩陣A表示有向圖G的存儲結(jié)構(gòu)，則有向圖G中頂點(diǎn)i的入度為（ ）。A:第i行非0或非元素的個(gè)數(shù)之和B:第i列非0或非元素的個(gè)數(shù)之和C:第i行0元素的個(gè)數(shù)之和D: 第i列0元素的個(gè)數(shù)之和正確答案：B7、以數(shù)據(jù)集1，3，5，7為葉結(jié)點(diǎn)的權(quán)值，構(gòu)造一棵哈夫曼樹，求出帶權(quán)路徑長度WPL（）。A:26B:28C:29D:30正確答案：C8、設(shè)某完全無向圖中有n個(gè)頂點(diǎn)，則該完全無向圖中有（ ）條邊A:n(n-1)/2B:n(n-1)C:n的2次冪D:n的2次冪-1正確答案：A9、查找表可分為兩類（）A:動態(tài)查找表B:順序查找表C:靜態(tài)查找表D:起泡查找表正確答案：AC10、使用折半方法進(jìn)行查找的表是一個(gè)有序表。A:對B:錯(cuò)正確答案：A第七章1、執(zhí)行一趟快速排序能夠得到的序列是（ ）。A: 41，12，34，45，27 55 72，63B:45，34，12，41 55 72，63，27C: 63，12，34，45，27 55 41，72D:12，27，45，41 55 34，63，72正確答案：A2、排序分穩(wěn)定排序和不穩(wěn)定排序。（ ）A:對B:錯(cuò)正確答案：A3、設(shè)一組權(quán)值集合W=2，3，4，5，6，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長度之和為（ ）A:20B:30C:40D:45正確答案：D4、冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（ ）A:對B:錯(cuò)正確答案：A5、設(shè)一組初始記錄關(guān)鍵字序列為(45，80，55，40，42，85)，則以第一個(gè)記錄關(guān)鍵字45為基準(zhǔn)而得到一趟快速排序的結(jié)果是（ ）。A:40，42，45，55，80，83B:42，40，45，80，85，88C:42，40，45，55，80，85D:42，40，45，85，55，80正確答案：C6、設(shè)一組初始記錄關(guān)鍵字序列為(25，50，15，35，80，85，20，40，36，70)，其中含有5個(gè)長度為2的有序子表，則用歸并排序的方法對該記錄關(guān)鍵字序列進(jìn)行一趟歸并后的結(jié)果為（ ）。A:15，25，35，50，20，40，80，85，36，70B:15，25，35，50，80，20，85，40，70，36C:15，25，35，50，80，85，20，36，40，70D:15，25，35，50，80，20，36，40，70，85正確答案：A7、設(shè)一組初始記錄關(guān)鍵字序列為(50，40，95，20，15，70，60，45)，則以增量d=4的一趟希爾排序結(jié)束后前4條記錄關(guān)鍵字為（ ）。A: 40，50，20，95B:15，40，60，20C:15，20，40，45D:45，40，15，20正確答案：B8、執(zhí)行一趟快速排序能夠得到的序列是（ ）。A:41，12，34，45，27 55 72，63B:45，34，12，41 55 72，63，27C:63，12，34，45，27 55 41，72正確答案：A9、隊(duì)列的順序存儲結(jié)構(gòu)用C語言中（ ）數(shù)據(jù)類型實(shí)現(xiàn)。A:一維數(shù)組實(shí)現(xiàn)B:二維數(shù)組實(shí)現(xiàn)C:結(jié)構(gòu)體D:枚舉型正確答案：A10、時(shí)間復(fù)雜度不受數(shù)據(jù)初始狀態(tài)影響而恒為O(nlog2n)的是（ ）。A: 堆排序B: 冒泡排序C: 希爾排序D:快速排序正確答案：A