智慧樹知到算法與數(shù)據(jù)結(jié)構(gòu)章節(jié)測(cè)試答案智慧樹知到算法與數(shù)據(jù)結(jié)構(gòu)章節(jié)測(cè)試答案緒論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:對(duì)B:錯(cuò)正確答案：對(duì)4、對(duì)算法的描述包括程序形式和描述形式。A:對(duì)B:錯(cuò)正確答案：對(duì)5、描述形式是算法的最終形式A:對(duì)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:操作對(duì)象C:關(guān)系D:操作正確答案：非數(shù)值計(jì)算,操作對(duì)象,關(guān)系,操作10、 順序存儲(chǔ)結(jié)構(gòu): 借助元素在存儲(chǔ)器中的( )來表示數(shù)據(jù)元素間的邏輯關(guān)系。A:地址B:結(jié)構(gòu)C:相對(duì)位置D:數(shù)值正確答案：相對(duì)位置第一章1、（）是一種最簡(jiǎn)單的線性結(jié)構(gòu)。A:圖B:線性表C:樹D:集合正確答案：線性表2、（ ）線性表的數(shù)據(jù)元素可以由所描述對(duì)象的各種特征的數(shù)據(jù)項(xiàng)組成。A:有序存儲(chǔ)B:散列存儲(chǔ)C:鏈?zhǔn)酱鎯?chǔ)D:順序存儲(chǔ)正確答案：鏈?zhǔn)酱鎯?chǔ)3、已知單向鏈表中指針p指向結(jié)點(diǎn)A，( ）表示刪除A的后繼結(jié)點(diǎn)（若存在）的鏈操作（不考慮回收）。A:p>next=pB:p=p>nextC:p=p>next>nextD:p>next=p>next>next正確答案：p>next=p>next>next4、已知last指向單向簡(jiǎn)單鏈表的尾結(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è)元素組成的線性表，我們說此線性表的長(zhǎng)度為（ ）A:nB:n+1C:n-1D:0正確答案：n7、對(duì)線性表中的數(shù)據(jù)元素進(jìn)行（ ）和（ ）等操作，實(shí)現(xiàn)表的長(zhǎng)度的增長(zhǎng)或縮短。A:插入B:遍歷C:訪問D:刪除正確答案：插入,刪除8、線性表的抽象數(shù)據(jù)類型定義A:數(shù)據(jù)對(duì)象B:函數(shù)關(guān)系C:數(shù)據(jù)關(guān)系D:基本操作正確答案：數(shù)據(jù)對(duì)象,數(shù)據(jù)關(guān)系,基本操作9、我們使用（ ），實(shí)現(xiàn)線性表的順序存儲(chǔ)。A:數(shù)值B:函數(shù)C:數(shù)組D:語句正確答案：數(shù)組10、線性表的基本操作是用C語言中的（ ）對(duì)其進(jìn)行表示的。A:循環(huán)語句B:函數(shù)C:結(jié)構(gòu)體D:條件語句正確答案：函數(shù)11、 在鏈表中第i 個(gè)結(jié)點(diǎn)之前插入新的元素 e ，表的邏輯結(jié)構(gòu)不變。A:對(duì)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:對(duì)B:錯(cuò)正確答案：錯(cuò)14、數(shù)字鐘程序中使用的時(shí)間，可以是系統(tǒng)時(shí)間。A:對(duì)B:錯(cuò)正確答案：對(duì)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:對(duì)B:錯(cuò)正確答案：對(duì)17、雙向鏈表的“插入” 時(shí)不需要同時(shí)修改兩個(gè)方向上的指針,改變結(jié)點(diǎn)之間的邏輯關(guān)系。A:對(duì)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:對(duì)B:錯(cuò)正確答案：對(duì)5、和鏈棧類似，用單鏈表來實(shí)現(xiàn)鏈隊(duì)。根據(jù)隊(duì)的先入先出(FIFO)原則，為了操作上的方便，使用一個(gè)( )和( )。A:數(shù)據(jù)域B:頭指針C:尾指針D:指針域正確答案：頭指針,尾指針6、隊(duì)列的順序存儲(chǔ)結(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:對(duì)B:錯(cuò)正確答案：錯(cuò)8、隊(duì)列允許在表的一端進(jìn)行插入操作和刪除操作。A:對(duì)B:錯(cuò)正確答案：錯(cuò)9、入棧需要修改地址指針。A:對(duì)B:錯(cuò)正確答案：對(duì)10、 鏈棧主要的運(yùn)算，如插入、刪除是在棧頂執(zhí)行的。 鏈表的頭部作棧頂是最方便的，需要像單鏈表那樣為了運(yùn)算方便附加一個(gè)頭結(jié)點(diǎn)。A:對(duì)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í)，不需要用動(dòng)態(tài)存儲(chǔ)空間分配函數(shù)。A:對(duì)B:錯(cuò)正確答案：錯(cuò)13、順序棧中數(shù)據(jù)元素與棧頂指針的變化：非空棧中的棧頂指針top始終在的 （）下一個(gè)位置A:棧中任意元素B:棧頂元素C:棧底元素D:棧中元素正確答案：棧頂元素14、在初始化空順序棧時(shí)一般不限定棧的最大容量，因?yàn)?，棧在使用過程中所需最大空間的大小很難估計(jì)。A:對(duì)B:錯(cuò)正確答案：對(duì)15、利用（）的存儲(chǔ)單元依次存放自棧底到棧頂?shù)臄?shù)據(jù)元素，這種形式的棧稱為順序棧。A:一組地址相同B:一組地址不連續(xù)C:一組地址連續(xù)D:一組地址斷開正確答案：一組地址連續(xù)第三章1、串(即字符串)是一種特殊的線性表，它的數(shù)據(jù)元素是（ ）。A:數(shù)字B:單個(gè)字符C:圖D:表正確答案：B2、包含零個(gè)字符(n=0)的串稱為空串，通常記為，其長(zhǎng)度為零；空串是任意串的子串。A:對(duì)B:錯(cuò)正確答案：A3、空串與空格串相同A:對(duì)B:錯(cuò)正確答案：B4、串比較是按字符的ASCII值比較的，而不是按串的長(zhǎng)度比較的。 StrCompare(data, structures) _ 0；A:大于B:等于C:小于D:小于等于正確答案：C5、SubString( sub, commander, 1, 9) 求得 sub = _；A:commanrB:coanderC:commanderD:comander正確答案： C6、串的基本操作中，操作對(duì)象大多為“串的整體”。A:對(duì)B:錯(cuò)正確答案：A7、在串的表示和實(shí)現(xiàn)過程中，用一組地址不連續(xù)的存儲(chǔ)單元存儲(chǔ)串值中的字符序列，稱為串的定長(zhǎng)順序存儲(chǔ)方式。A:對(duì)B:錯(cuò)正確答案：B8、在順序串中，用一個(gè)指針來指向最后一個(gè)字符，C語言的表示如下：typedef struct char dataMAXSIZE; int curlen; SeqString;請(qǐng)定義一個(gè)串變量：A: structg sB:typedef struct s；C:SqString s；D:SeqString s；正確答案：D9、在C語言中，存在一個(gè)稱為“堆”的自由存儲(chǔ)區(qū)，并由C語言的動(dòng)態(tài)分配函數(shù)_來管理。A:malloc( )B:malloc( )和free( )C:free( )D:main()正確答案：B10、堆分配存儲(chǔ)結(jié)構(gòu)的串有順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)，在操作中對(duì)串長(zhǎng)又沒有任何限制，因而在串處理的應(yīng)用程序中常被選用。A:對(duì)B:錯(cuò)正確答案：A第四章1、設(shè)按照從上到下、從左到右的順序從1開始對(duì)完全二叉樹進(jìn)行順序編號(hào)，則編號(hào)為i結(jié)點(diǎn)的左孩子結(jié)點(diǎn)的編號(hào)為（ ）。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:對(duì)B:錯(cuò)正確答案：A6、設(shè)一棵二叉樹的先序序列和后序序列，則能夠唯一確定出該二叉樹的形狀。（ ）A:對(duì)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)路徑長(zhǎng)度定義為，樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和(對(duì)所有葉子結(jié)點(diǎn))。（）A:對(duì)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的存儲(chǔ)結(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:對(duì)B:錯(cuò)正確答案：A5、 對(duì)鏈表進(jìn)行插入和刪除操作時(shí)不必移動(dòng)鏈表中結(jié)點(diǎn)。( )A:對(duì)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的存儲(chǔ)結(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、簡(jiǎn)單回路就是回路。A:對(duì)B:錯(cuò)正確答案：B10、圖中任兩點(diǎn)有路徑相通，該圖稱為連通圖（）A:對(duì)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)路徑長(zhǎng)度之和為（ ）。A:20B:30C:40D:45正確答案：D3、設(shè)一組權(quán)值集合W=2，3，4，5，6，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長(zhǎng)度之和為（ ）A:20B:30C:40D:45正確答案：D4、 連通圖的最小生成樹的邊上的權(quán)值之和是唯一的。( )A:對(duì)B:錯(cuò)正確答案：A5、設(shè)某無向圖有n個(gè)頂點(diǎn)，則該無向圖的鄰接表中有（ ）個(gè)表頭結(jié)點(diǎn)。A:2nB:nC:n/2D: n(n-1)正確答案：B6、設(shè)用鄰接矩陣A表示有向圖G的存儲(chǔ)結(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)路徑長(zhǎng)度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:動(dòng)態(tài)查找表B:順序查找表C:靜態(tài)查找表D:起泡查找表正確答案：AC10、使用折半方法進(jìn)行查找的表是一個(gè)有序表。A:對(duì)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:對(duì)B:錯(cuò)正確答案：A3、設(shè)一組權(quán)值集合W=2，3，4，5，6，則由該權(quán)值集合構(gòu)造的哈夫曼樹中帶權(quán)路徑長(zhǎng)度之和為（ ）A:20B:30C:40D:45正確答案：D4、冒泡排序在初始關(guān)鍵字序列為逆序的情況下執(zhí)行的交換次數(shù)最多。（ ）A:對(duì)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è)長(zhǎng)度為2的有序子表，則用歸并排序的方法對(duì)該記錄關(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ì)列的順序存儲(chǔ)結(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