《數(shù)據(jù)結(jié)構(gòu)》綜合練習(xí)

綜合練習(xí)一、單項(xiàng)選擇題數(shù)據(jù)在計(jì)算機(jī)存儲(chǔ)器內(nèi)表示時(shí)，物理地址與邏輯地址不相同的，稱(chēng)之為。存儲(chǔ)結(jié)構(gòu) B.邏輯結(jié)構(gòu)C.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) D.順序存儲(chǔ)結(jié)構(gòu)設(shè)語(yǔ)句x++的時(shí)間是單位時(shí)間，則以下語(yǔ)句的時(shí)間復(fù)雜度為（B。for(i=1;i<=n;i++)for(j=i;j<=n;j++)x++;A.O(1) B.O(n2) C.O(n) D.O(n3)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的最大優(yōu)點(diǎn)是（D。便于隨機(jī)存取 B.存儲(chǔ)密度高C.無(wú)需預(yù)分配空間 D.便于進(jìn)行插入和刪除操作{a0,a1,……,an－1}中，每一個(gè)數(shù)據(jù)元素所占的存儲(chǔ)單元的數(shù)目為4，01007（D。A.106 B.107 C.124 D.128在線(xiàn)性表中若經(jīng)常要存取第i（A）存儲(chǔ)方式。順序表 B.帶頭結(jié)點(diǎn)的單鏈表C.不帶頭結(jié)點(diǎn)的單鏈表 D.循環(huán)單鏈表在鏈表中若經(jīng)常要?jiǎng)h除表中最后一個(gè)結(jié)點(diǎn)或在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)采用（C）存儲(chǔ)方式。順序表 B.用頭指針標(biāo)識(shí)的循環(huán)單鏈表C.用尾指針標(biāo)識(shí)的循環(huán)單鏈表 D.雙向鏈表在一個(gè)含有n個(gè)結(jié)點(diǎn)的有序單鏈表中插入一個(gè)新結(jié)點(diǎn)時(shí)間復(fù)雜度是（C。O(1) B.O(log2n) C.O(n) D.O(n2){a0,a1,……,an-1}中第iai(0≤i≤n-1（B）個(gè)數(shù)據(jù)元素。A.i B.n-i-1 C.n-i D.n-i+1在棧中存取數(shù)據(jù)的原則是（B。先進(jìn)先出 B.先進(jìn)后出C.后進(jìn)后出 D.沒(méi)有限制若將整數(shù)、、34依次進(jìn)棧，則不可能得到的出棧序列是（DA．1234 B.1324 C.4321 D.1423在鏈棧中，進(jìn)行出棧操作時(shí)（B。需判斷棧是否滿(mǎn) B.需判斷棧是否為空C.需判斷棧元素的類(lèi)型 D.需對(duì)棧作任何差別在順序棧中，若棧頂指針top指向棧頂元素的存儲(chǔ)單元，且順序棧的最大容量是maxSiz，則順序棧的判空條件是B。top==0 B.top==-1 C.top==maxSize D.top==maxSize-1topmaxSize。則順序棧的判滿(mǎn)的條件是。top==0 B.top==-1 C.top==maxSize D.top==maxSize-1在隊(duì)列中存取數(shù)據(jù)元素的原則是（A。A．先進(jìn)先出 B.先進(jìn)后C.后進(jìn)后出 D.沒(méi)有限制在循環(huán)順序隊(duì)列中，假設(shè)以少用一個(gè)存儲(chǔ)單元的方法來(lái)區(qū)分隊(duì)列判滿(mǎn)和判空的條件，front和rear分別為隊(duì)首和隊(duì)尾指針，它們分別指向隊(duì)首元素和隊(duì)尾元素的下一個(gè)存單元，隊(duì)列的最大存儲(chǔ)容量為maxSize，則隊(duì)列的判空條件是（A。A．front==rear B.front!=rearC.front==rear+1 D.front==(rear+1)%maxSize在循環(huán)順序隊(duì)列中，假設(shè)以少用一個(gè)存儲(chǔ)單元的方法來(lái)區(qū)分隊(duì)列判滿(mǎn)和判空的條件，front和rear分別為隊(duì)首和隊(duì)尾指針，它們分別指向隊(duì)首元素和隊(duì)尾元素的下一個(gè)存單元，隊(duì)列的最大存儲(chǔ)容量為maxSize，則隊(duì)列的判滿(mǎn)條件是（D。A．front==rear B.front!=rearC.front==rear+1 D.front==(rear+1)%maxSize在循環(huán)順序隊(duì)列中，假設(shè)以少用一個(gè)存儲(chǔ)單元的方法來(lái)區(qū)分隊(duì)列判滿(mǎn)和判空的條件，front和rear單元，隊(duì)列的最大存儲(chǔ)容量為maxSize，則隊(duì)列的長(zhǎng)度是（C。rear-front B.rear-front+1C.(rear-front+maxSize)%maxSize D.(rear-front+1)%maxSize設(shè)長(zhǎng)度為n隊(duì)操作的時(shí)間復(fù)雜度為（B。A．O(1) B．O(n) C．O(logn) D．O(n2)2串的長(zhǎng)度是( A )串中包含的字符個(gè)數(shù) B.串中包含的不同字符個(gè)數(shù)C.串中除空格以外的字符個(gè)數(shù) D.串中包含的不同字母?jìng)€(gè)數(shù)設(shè)有兩個(gè)串pqpq在p（C）求子串 B．聯(lián)接 C．模式匹配 D．求串長(zhǎng)10A為第一元11素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a的地址為（B 。85A.13 B.33 C.18 D.407.有一個(gè)二維數(shù)組A[1..6,0..7]每個(gè)數(shù)組元素用相鄰的6個(gè)字節(jié)存儲(chǔ)存儲(chǔ)器按字編址，那么這個(gè)數(shù)組占用的存儲(chǔ)空間大小是（D ）個(gè)字節(jié)。A.48 B.96 C.252 D.288在哈夫曼樹(shù)中，任何一個(gè)結(jié)點(diǎn)它的度都是（C。A.0或1 B.1或2 C.0或2 D.0或1或2對(duì)一棵深度為h（D。A.2h B.2h-1 C.C.只有一個(gè)根結(jié)點(diǎn) D.任意一棵二叉

D.2h-11523結(jié)點(diǎn)的個(gè)數(shù)是（C）A．2 B.3 C.4 D.5 若某棵二叉樹(shù)的先根遍歷序列為，中根遍歷序列為根遍歷序列為（B。FEDCBA B.CDBFEA C.CDBEFA D.DCBEFAn（C）個(gè)空的指針域。A．n-1 B.n C.n+1 D.0利用二叉鏈表存儲(chǔ)樹(shù)，則根結(jié)點(diǎn)的右指針是（C。指向最左孩子 指向最右孩子 空 非空引入二叉線(xiàn)索樹(shù)的目的是（A。加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度B．為了能在二叉樹(shù)中方便的進(jìn)行插入與刪C．為了能方便的找到雙親 使二叉樹(shù)的遍歷結(jié)果唯一FF變換得的二叉樹(shù)。若Fn個(gè)非終端結(jié)點(diǎn)，則B域?yàn)榭盏慕Y(jié)點(diǎn)有（C）個(gè)。A．n1 B．n C．n+1 D．n+2錯(cuò)誤！未找到引用源。，則所有頂點(diǎn)的入度之和為。錯(cuò)誤！未找到引用源。 B.錯(cuò)誤！未找到引用源。 C.錯(cuò)誤！未找到用源。 D.錯(cuò)誤！未找到引用源。具有6個(gè)頂點(diǎn)的無(wú)向圖至少應(yīng)有（A ）條邊才能確保是一個(gè)連通圖。A.5 B.6 C.7 D.8一個(gè)有n個(gè)頂點(diǎn)的無(wú)向圖最多有（C ）條邊。錯(cuò)誤！未找到引用源。 B.錯(cuò)誤！未找到引用源。 C.錯(cuò)誤！未找到用源。 D.錯(cuò)誤！未找到引用源。34..n個(gè)頂點(diǎn)的連通圖用鄰接距陣表示時(shí)，該距陣至少有（B）個(gè)非零元素。A．n B．2(n-1) C．n/2 35對(duì)某個(gè)無(wú)向圖的鄰接矩陣來(lái)說(shuō)，下列敘述正確的是A。元素個(gè)數(shù)一定相等矩陣中的非零元素個(gè)數(shù)等于圖中的邊數(shù)的度數(shù)矩陣中非全零行的行數(shù)等于圖中的頂點(diǎn)數(shù).32任何一個(gè)無(wú)向連通圖的最小生成樹(shù)B。A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在下面（B）方法可以判斷出一個(gè)有向圖是否有環(huán)。A．深度優(yōu)先遍歷 B．拓?fù)渑判?C．求最短路徑 D．求關(guān)鍵路徑對(duì)線(xiàn)性表進(jìn)行二分查找時(shí)，要求線(xiàn)性表必(B )A.以順序方式存儲(chǔ) 以順序方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字值有序排C.以鏈接方式存儲(chǔ) 以鏈接方式存儲(chǔ)，且結(jié)點(diǎn)按關(guān)鍵字值有序排用二分查找法查找具有nD)A.O(n2) B.O(nlogn) C.O(n) D.O(logn)2 264要比(B 次。A.9 B.7 C.5 D.3若結(jié)點(diǎn)的存儲(chǔ)地址與其關(guān)鍵字之間存在某種映射關(guān)系，則稱(chēng)這種存儲(chǔ)結(jié)構(gòu)(D A.順序存儲(chǔ)結(jié)構(gòu) 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) 索引存儲(chǔ)結(jié)構(gòu) D.散列存儲(chǔ)結(jié)構(gòu)14，哈希函數(shù)是H(key)=key%11，表中已有數(shù)據(jù)的關(guān)鍵字為84共四個(gè)，現(xiàn)要將關(guān)鍵字為49的元素加到表中，用二次探測(cè)法解決沖突，則放入的位置是（D。42.下面給出的四種排序算法中B )是不穩(wěn)定的排序。A．插入排序 B．堆排序 C．二路歸并排序 D．冒泡排序43.在下列排序算法中，哪一種算法的時(shí)間復(fù)雜度與初始排序序列無(wú)關(guān)（D ）A．直接插入排序B．冒泡排序 C．快速排序 D．直接選擇排序44.關(guān)鍵字序列只能是下列排序算法(C )的兩趟排后的結(jié)果。A．選擇排序 B.冒泡排序 C.插入排序 D.堆排序45一組記錄的關(guān)鍵字為467563484，則利用快速排序的方法，以第一個(gè)錄為支點(diǎn)得到的一次劃分結(jié)果為（C 。A．(38,40,46,56,79,84) B．(40,38,46,79,56,84)C．(40,38,46,56,79,84) D．(40,38,46,84,56,79)46.在對(duì)一組關(guān)鍵字序列{15，33,55，100，65，50，40，95}，進(jìn)行直接插入排序時(shí)，把65插入，需要比較(A)次。A.2B.4C.6D.8從待排序的序列中選出關(guān)鍵字值最大的記錄放到有序序列中，該排序方法稱(chēng)( B )。希爾排序 B.直接選擇排序C.冒泡排序 D.快速排序當(dāng)待排序序列基本有序時(shí)，以下排序方法中B )最不利于其優(yōu)勢(shì)的發(fā)揮。直接選擇排序 B.快速排序 C.冒泡排序 D.直接插入排49..在待排序序列局部有序時(shí)，效率最高的排序算法( B )。A.直接選擇排序 B.直接插入排序 C.快速排序 D.歸并排序1000010(D)省時(shí)間。A．冒泡排序 B．快速排序 C．簡(jiǎn)單選擇排序 D．堆排序二、填空題一個(gè)串的任意連續(xù)字符組成的子序列稱(chēng)為串子串 該串稱(chēng)主串 。若兩個(gè)串的長(zhǎng)度相等且對(duì)應(yīng)位置上的字符也相等，則稱(chēng)兩個(gè)相等 。尋找子串在主串中的位置，稱(chēng)模式匹配 。其中，子串又稱(chēng)模式串。設(shè)數(shù)組A[1..5,1..6]的基地址為1000，每個(gè)元素占5個(gè)存儲(chǔ)單元，若以行序?yàn)橹餍蛐虼鎯?chǔ)，則元素A[5,5]的存儲(chǔ)地址1140 。一個(gè)n×n的對(duì)稱(chēng)矩陣，如果以相同的元素只存儲(chǔ)一次的原則進(jìn)行壓縮存儲(chǔ)，則其元壓縮后所需的存儲(chǔ)容量n(n+1)/2 。對(duì)矩陣壓縮的目的是為節(jié)省存儲(chǔ)空間 。循環(huán)順序隊(duì)列是將順序隊(duì)列的存儲(chǔ)區(qū)域看成是一個(gè)首尾相連的環(huán)過(guò)數(shù)學(xué)上的求模（或取余）運(yùn)算來(lái)實(shí)現(xiàn)的。10050。217。m2m-1。40711在深度為kk個(gè)結(jié)點(diǎn)。假定待查找記錄個(gè)數(shù)為n,則在等概率的情況下，順序查找在查找成功情況下的平均找長(zhǎng)度(n+1)/2 ；在查找失敗情況下的平均查找長(zhǎng)度n+1。對(duì)線(xiàn)性表進(jìn)行二分查找時(shí)，要求線(xiàn)性表必須以順序方式存儲(chǔ)，且數(shù)據(jù)有序。分塊查找分為兩個(gè)階段，分別是確定待查元素所在的塊在塊內(nèi)查找待查的元素。哈希法存儲(chǔ)中，沖突指的是不同關(guān)鍵字值對(duì)應(yīng)到相同的存儲(chǔ)地址。遞增序列。哈希法存儲(chǔ)的基本思想是根關(guān)鍵字 來(lái)決定存儲(chǔ)地址。若用錯(cuò)誤！未找到引用源。表示圖中頂點(diǎn)數(shù)，則有 錯(cuò)誤！未找到引用源。邊的無(wú)向圖稱(chēng)為完全圖。錯(cuò)誤！未找到引用源個(gè)頂點(diǎn)的連通無(wú)向圖至少錯(cuò)誤！未找到引用源。條邊至多錯(cuò)誤！未找到引用源。條邊。錯(cuò)誤！未找到引用源。的鄰接矩陣為：則頂點(diǎn)錯(cuò)誤！未找到引用源。的入度是 3 。對(duì)于一個(gè)有向圖，若一個(gè)頂點(diǎn)的度錯(cuò)誤！未找到引用源，出度錯(cuò)誤！未找到引源，則對(duì)應(yīng)逆鄰接表中該頂點(diǎn)單鏈表中的邊結(jié)點(diǎn)數(shù)錯(cuò)誤！未找到引用源。。在求最小生成樹(shù)的兩種算法中克魯斯卡爾算法適合于稀疏圖。數(shù)據(jù)結(jié)構(gòu)中的迪杰斯特拉算法是用來(lái)某個(gè)源點(diǎn)到其余各頂點(diǎn)的最短路徑。執(zhí)行排序操作時(shí)，根據(jù)使用的存儲(chǔ)器可將排序算法分為 內(nèi)排序和外排序。26. {50,40,95,20,15,70,60,45,80}進(jìn)行直接插入排序時(shí)，當(dāng)把第7個(gè)記錄60插入到有序表中時(shí)，為尋找插入位置需比較3 次。27. 序。28. {