數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)試卷

數(shù)據(jù)結(jié)構(gòu)期末復(fù)習(xí)一、判斷題。1、線性表的邏輯順序與物理順序總是一致的。（×）2、線性表個(gè)后繼。（√）3、單鏈表點(diǎn)。（×）4、數(shù)據(jù)結(jié)構(gòu)是集合。（√）5、棧是一做了限制的線性表。（×）6、算法一定要有輸入和輸出。（×）7、稀疏矩陣的元素少。（×）8、符號(hào)P->next出現(xiàn)在表達(dá)式中表示P所指的那個(gè)結(jié)點(diǎn)的內(nèi)容。（×）9、無論是順序O（1）。（√）10、除插入和刪除操作外，數(shù)序等。（√）中的每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)和一從任何一個(gè)結(jié)點(diǎn)出發(fā)，都能訪問到所有結(jié)帶有結(jié)構(gòu)的的數(shù)據(jù)元素的種對進(jìn)棧、出棧操作總次數(shù)特點(diǎn)是矩陣中的隊(duì)列還是鏈隊(duì)列，插入、刪除運(yùn)算的時(shí)間復(fù)雜度都是組主要操作還有存取、修改、檢索和排11、最小生成樹只有一棵。（×）（分析：最小生成樹數(shù)目大于等于1）二、填空題。1、《數(shù)據(jù)結(jié)構(gòu)》課程討論的算，邏輯結(jié)構(gòu)主要分為集合、線性表、樹和圖。2、順序存儲(chǔ)結(jié)構(gòu)是通過數(shù)組表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過指針表示元素之間的關(guān)系的。3、限定僅在表尾進(jìn)行插入或刪除操作的線性表稱為棧。4、一個(gè)完整的算法應(yīng)具有輸入、有窮性、確定性和可行性等五個(gè)特性。其中有窮性表示執(zhí)行有窮步驟后一束。5、兩個(gè)串相等是指兩個(gè)串的長度和對應(yīng)字符都相等。主要內(nèi)容是數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)和數(shù)據(jù)運(yùn)輸出、定能結(jié)6、隊(duì)列又稱先進(jìn)先出表。7、設(shè)數(shù)組a[1..50,1..80]的基地址為2000，每個(gè)元素占2個(gè)存儲(chǔ)單元，若以行序?yàn)橹餍蝽樞虼鎯?chǔ)，則元素a[45,68]的存儲(chǔ)地址為2000+（44*80+68）*2=9176；若存儲(chǔ)，則元素a[45,68]的存儲(chǔ)地址為2000+（67*50+45）以列序?yàn)橹餍蝽樞?2=8790；8、數(shù)據(jù)的邏輯結(jié)構(gòu)被分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩大類；其中非線性結(jié)構(gòu)又細(xì)分為樹形結(jié)構(gòu)和圖形結(jié)構(gòu)兩類。9、數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)包括順序存儲(chǔ)、鏈?zhǔn)酱鎯?chǔ)索引存儲(chǔ)和哈希存儲(chǔ)等四種。10、限定僅允許在表的一端進(jìn)行插入操作，而在表的另一端進(jìn)行刪除操作的線性表稱為隊(duì)列。11、一個(gè)遞歸模型是由遞歸終止條件和遞歸體兩部分組成，前者確認(rèn)遞歸到何時(shí)結(jié)束，后者確認(rèn)遞歸求解時(shí)的遞推關(guān)系。12、二叉排序樹的平均查找長度和數(shù)的形態(tài)有關(guān)，所以在構(gòu)造時(shí)要進(jìn)行平衡處理。13、在排序的過程中需進(jìn)行比較和移動(dòng)兩種操作。14、在樹結(jié)構(gòu)中，樹內(nèi)各結(jié)點(diǎn)的度的最大值稱為樹的度；雙親在同一層的結(jié)點(diǎn)互為堂兄弟。15、圖可分為無向圖和有向圖，無向圖中的極大連通子圖稱為連通分量。16、外排序的基本方法是歸并排序法歸并兩個(gè)步驟。，它分為文件預(yù)處理和多路17、中序遍歷二叉排序樹可得到一個(gè)關(guān)鍵字的有序序列。三、選擇題。1、數(shù)據(jù)的運(yùn)算是（D）。A、必須用程序語言來描述B、是根據(jù)存儲(chǔ)結(jié)構(gòu)來定義的C、有算術(shù)運(yùn)算和關(guān)系運(yùn)算兩大類D、效率和采用和中存儲(chǔ)結(jié)構(gòu)有關(guān)2、在一個(gè)長度為n的順序線性表中順序查找值為x的元素時(shí)，查找成功時(shí)的平均查找長度（即x與元素的平均比較次數(shù)，假定查找每個(gè)元素的概率都相等）為(C)。AnBn/2C(n+1)/2D(n-1)/23、將長度為n的單鏈表鏈接在長度為m的單鏈表之后的算法的時(shí)間復(fù)雜度為（B）A．O（1）B．O（m）C．O（n）D．O（m+n）4、設(shè)S是一個(gè)長度為n的字符串，其中字符各不相同，則S中的互異非平凡子串（非空串且不同于S本身）個(gè)數(shù)為（C）。A、2n-1B、n(n+1)/2C、n(n+1)/2-1D、n(n-1)/2-1答案解析：長度為n-1的不同子串個(gè)數(shù)為2，長度為n-2的不同子串個(gè)數(shù)為3.。。，長度為1的不同子串個(gè)數(shù)是n，綜合得到C5、下面關(guān)于算法說法錯(cuò)誤的是（A）。A、算法最終必須由計(jì)算機(jī)程序?qū)崿F(xiàn)B、為解決某問題的算法與為該問題編寫的程序含義是想同的C、算法的可行性是指指令不能有二義性D、以上幾個(gè)都是錯(cuò)誤的6、若一個(gè)棧的輸入序列為1,2,3,…,n，輸出序列的第一個(gè)元素是i，則第j個(gè)輸出元素是（D）。A.i-j-1B.i-jC.j-i+1D.不確定的7、最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條件是（B）。A.(rear+1)%n=frontB.rear=frontC．rear+1=frontD.(rear-l)modn=front8、在單鏈表中，指針p指向元素為x的結(jié)點(diǎn)，實(shí)現(xiàn)“刪除x的后繼”的語句是（B）。A.p=p->next;B.p->next=p->next->C.p->next=p;D.p=p->next->next;9、下面關(guān)于線性表的敘述中，錯(cuò)誤的是（B）。A.線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B.線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作C.線性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D.線性表采用鏈?zhǔn)酱鎯?chǔ)，便于進(jìn)行插入和刪除操作10、某算法的時(shí)間復(fù)雜度為O（n2），表明該算法的（C）。A、問題規(guī)模是n2B、執(zhí)行時(shí)間等于n2C、執(zhí)行時(shí)間與n2比D、問題規(guī)模與n2比11、一個(gè)n×n的對稱矩陣,如果以列序?yàn)橹餍蚍湃雰?nèi)存，則容量為（D）。A、n2B、n2/2C、(n+1)2/2D、n(n+1)/212、下列關(guān)于串的敘述中，哪一個(gè)是不正確的？（B）A、串是字符的有限序列B、空串是由空格構(gòu)成的串C、模式匹配是串的一種重要的運(yùn)算D、串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)13、下列程序段的時(shí)間復(fù)雜度為（C）。for(inti=0;i<m;i++)for(intj=0;j<n;j++)A[i][j]=i*j;A、O(m2)B、O(n2)C、O(m*n)D、O(m+n)14、設(shè)S是一個(gè)長度為n的字符串，其中字符各不相同，則S中的互異非平凡子串（非空串且不同于S本身）個(gè)數(shù)為（D）。A、22-1B、n2C、（n2/2）+(n/2）D、（n2/2）+(n/2）-115、對稀疏矩陣采用壓縮存儲(chǔ)，其缺點(diǎn)之一是（C)。A、無法判斷矩陣有多少行多少列B、無法根據(jù)行列號(hào)查找某個(gè)矩陣元素C、無法根據(jù)行列號(hào)計(jì)算矩陣元素的存儲(chǔ)地址D、是矩陣元素之間的邏輯關(guān)系更加復(fù)雜16、設(shè)棧s和隊(duì)列q的初始狀態(tài)為空，元素e1，e2,e3,e4,e5和e6依次通過棧s，當(dāng)一個(gè)元素出棧后，立即進(jìn)入隊(duì)列q。若6個(gè)元素出對列是e2,24,e3,e6,e5,e1,則棧s的容量至少應(yīng)該是（C）A、6B、4C、3D、217、模式串t='abcabaa'，改模式串的nextval函數(shù)值為（）。A-1000123B、-1000121C、-100-1021D、-100-112118、由權(quán)值分別為11，8，6，2，5的葉子結(jié)點(diǎn)生成一棵哈夫曼樹，它的帶權(quán)路徑長度為（B）A、71B、73C）。C、32D、5319、棧和隊(duì)列都是（A、順序存儲(chǔ)的的線性結(jié)構(gòu)B、鏈?zhǔn)酱鎯?chǔ)的線性結(jié)構(gòu)C、限制存儲(chǔ)點(diǎn)的線性結(jié)構(gòu)D、限制存儲(chǔ)點(diǎn)的非線性結(jié)構(gòu)20、某內(nèi)排序方法的穩(wěn)定性是指(D)。A．該排序算法不允許有相同的關(guān)鍵字記錄B．該排序算法允許有相同的關(guān)鍵字記錄C．平均時(shí)間為0（nlog）的排n序方法D．以上都不對21、假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array[，1..100]，設(shè)2個(gè)存儲(chǔ)單元，基地址為10，則LOC[5，5]=（d）。B.818C.10122、在下述結(jié)論中，正確的是（C）每個(gè)數(shù)據(jù)元素占A.808①只有一個(gè)結(jié)點(diǎn)的二叉樹的度為0;②二叉樹的度為2；③二叉樹的左右子樹可任意交換;④深度為K的完全二叉樹的結(jié)點(diǎn)個(gè)數(shù)小于或等于深度相同的滿二叉樹。A．①②③B．②③④C．①④D．①②④23、一棵完全二叉樹上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（D）A、250B、500C、254D、以上答案都不對24、散列文件使用散列函數(shù)將記錄的關(guān)鍵字值計(jì)算轉(zhuǎn)化為記錄的存放地址，因?yàn)樯⒘泻瘮?shù)是一對一的關(guān)系，則選擇好的（A）方法是散列文件(Hash)的關(guān)鍵。散(A)列函數(shù)除(B)余法中的質(zhì)數(shù)(C)沖突處理散(D)列函數(shù)和沖突處理25、設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n，則該圖最多有（A）條邊。A、n(n-1)/2、n(n+B1)/2、n-1、Cn2D26、設(shè)圖如右所示，在下面的5個(gè)序列中，符合深度優(yōu)先遍歷的序列有多少？（D）aebdfcacfdebaedfcafdbcA．5個(gè)．4個(gè)B．3個(gè)Cbec．D2個(gè)df27、下面關(guān)于二分查找的敘述正確的是（D）。A.表必須有序，表可以順序方式存儲(chǔ)，也可以鏈表方式存儲(chǔ)B.表必須有序，且表中數(shù)據(jù)必須是整型、實(shí)型或字符型C.表必須有序，而且只能從小到大列排D.表必須有序，且表只能以順序方式存儲(chǔ)28、設(shè)哈希表長為14，哈希函數(shù)H(key)=key％11，表中已有數(shù)據(jù)的關(guān)鍵字為15，38，61，84共四個(gè)，現(xiàn)將關(guān)鍵字為49的結(jié)點(diǎn)加到表中，用線性探測再散列法解決沖突，則放入的位置是(D)。aA、8B、3C、5D、929、歸并排序的時(shí)間復(fù)雜度是（A、O（n2）B、O（n）C、O（nlogn）D、O（logn）四、應(yīng)用題。C）。1、已知一組記錄的初始序列為（6,8,7,9,0,1,2,3,4,5），畫出對其進(jìn)行堆排序時(shí)建立的大根堆。2、已知一棵二叉樹的先序遍歷結(jié)果是ABECDFGHIJ,中序遍歷結(jié)果是EBCDAFHIGJ，試畫出這棵二叉樹，并寫出它的后序遍歷結(jié)果?！?、畫出和下列森林相應(yīng)的二叉樹，并按中序線索化，用虛線畫出前驅(qū)和后繼線索。4、對下列無向網(wǎng)：（1）寫出它的鄰接矩陣，并按普利姆算法求其最小生成樹；（2）寫出它的鄰接表，并按克魯斯卡爾算法求其最小生成樹；（1）鄰接矩陣：以a為起始點(diǎn)由Prim算法求得的最小生成樹（不唯一）為：（2）鄰接表：由Kruskal算法求得的最小生成樹（不唯一）為：5、序列{45,12,53,3,37,100,24,61,90,78}，（1)畫出它的2）畫出在序列中增加一個(gè)元素60后的二叉排3）畫出在序列中刪除一個(gè)元素100后二叉排序樹，并寫出中序遍歷結(jié)果；（序樹，并寫出中序遍歷結(jié)果；（的二叉排序樹，并寫出中序遍歷結(jié)果；（1）程序題（編寫算法）。五、1、給出折半查找的遞歸算法，并給出算法時(shí)間復(fù)雜度分析。#defineMAXL<表中最多記錄數(shù)>typedefstruct{Keytypekey;/*Keytype為關(guān)鍵字的數(shù)據(jù)類型*/InfoTypedata;/*其他數(shù)據(jù)*/}NodeType;typedefNodeTypeSeqList[MAXL];intBinSearch(SeqListR,intn,Keytypek)/*函數(shù)頭解:intBinSearch(SeqListR,intn,Keytypek)/*函數(shù)頭{*/*/intmid,low,,high;if(low>high)return-1;mid=(low+high)/2;if(n==R[mid])returnmid;elseif(n<R[mid])//查找不成功//查找成功returnBinSearch(R,n,low,mid-1);//在上半?yún)^(qū)查找elsereturnBinSearch(R,n,mid+1,high);//在下半?yún)^(qū)查找}2、借助于快速排序的算法思想，在一組無序的記錄中查找給定的關(guān)鍵字等于key的記錄。設(shè)此記錄存放于數(shù)組R[1...n]中，若查找成功，R數(shù)組中的值，否則顯示"notfind"信息。請則輸出該記錄在位置及其編寫算法并簡要說明算法思想。typedefintKeytype;typedefstruct{Keytypekey;/*Keytype為關(guān)鍵字的數(shù)據(jù)類型*/InfoTypedata;/*其他數(shù)據(jù)*/}RecType;intindex(RecTypeR[],intl,intn,Keytypekey)/*函數(shù)頭*/解：1）算法：intin