數(shù)據(jù)結(jié)構(gòu)考試專用附帶完整答案

單元測驗1一．判斷題(X)(1)數(shù)據(jù)的邏輯結(jié)構(gòu)和數(shù)據(jù)的存儲結(jié)構(gòu)是相同的。(X)(2)程序和算法原則上沒有區(qū)別，所以在討論數(shù)據(jù)結(jié)構(gòu)時可以通用。(7)(3)從邏輯關(guān)系上講，數(shù)據(jù)結(jié)構(gòu)主要分為線性結(jié)構(gòu)和非線性結(jié)構(gòu)兩類。(7)(4)數(shù)據(jù)的存儲結(jié)構(gòu)是數(shù)據(jù)的邏輯結(jié)構(gòu)的存儲映像。(X)(5)數(shù)據(jù)的邏輯結(jié)構(gòu)是依賴于計算機的。(7)(6)算法是對解題方法和步驟的描述。二．填空題數(shù)據(jù)有邏輯結(jié)構(gòu)和存儲結(jié)構(gòu)兩種結(jié)構(gòu)。2?數(shù)據(jù)結(jié)構(gòu)按邏輯結(jié)構(gòu)可分為兩大類，它們是線性結(jié)構(gòu)和非線性結(jié)構(gòu)。樹形結(jié)構(gòu)和圖形結(jié)構(gòu)合稱為非線性結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)又叫物理結(jié)構(gòu)。數(shù)據(jù)的存儲結(jié)構(gòu)形式包括：順序存儲和鏈?zhǔn)酱鎯€性結(jié)構(gòu)中的元素之間存在二對二的關(guān)系。樹形結(jié)構(gòu)中的元素之間存在二對多的關(guān)系。圖形結(jié)構(gòu)的元素之間存在多對多的關(guān)系。數(shù)據(jù)結(jié)構(gòu)主要研究數(shù)據(jù)的邏輯結(jié)構(gòu)、存儲結(jié)構(gòu)和二者之間的相互運算三個方面的內(nèi)容。一個算法的時間復(fù)雜度是問題規(guī)模的函數(shù)。時間復(fù)雜度：O(1)vO(log2n)vO(n)vO(nlog2n)vO(n2)vO(n3)v...vO(2n)vO(n!)若一個算法中的語句頻度之和為T(n)=6n+3nlog2n，貝I」算法的時間復(fù)雜度為O(nlog2n)。12.若一個算法中的語句頻度之和為T(n)=3n+nlog2n+n2，貝I」算法的時間復(fù)雜度為O(n2)。三.選擇題數(shù)據(jù)結(jié)構(gòu)通常是研究數(shù)據(jù)的(D)及它們之間的相互聯(lián)系。聯(lián)系與邏輯B.存儲和抽象C.聯(lián)系和抽象D.存儲結(jié)構(gòu)和邏輯結(jié)構(gòu)數(shù)據(jù)在計算機內(nèi)存儲時，數(shù)據(jù)元素在存儲器內(nèi)相對位置可以表示元素之間的邏輯關(guān)系，稱為(D)存儲結(jié)構(gòu)B.邏輯結(jié)構(gòu)C.鏈?zhǔn)酱鎯Y(jié)構(gòu)D.順序存儲結(jié)構(gòu)鏈接存儲的存儲結(jié)構(gòu)所占存儲空間(A)。分兩部分，一部分存放結(jié)點的值，另一部分存放表示結(jié)點間關(guān)系的指針只有一部分，存放結(jié)點值只有一部分，存儲表示結(jié)點間關(guān)系的指針分兩部分，一部分存放結(jié)點值，另一部分存放結(jié)點所占單元數(shù)在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是(B)A.物理結(jié)構(gòu)B.邏輯結(jié)構(gòu)(不用進行計算)C?存儲結(jié)構(gòu)D.邏輯和存儲結(jié)構(gòu)5?算法能正確的實現(xiàn)預(yù)定功能的特性稱為(A)A.正確性B.易讀性C.健壯性D.高效性算法在發(fā)生非法操作時可以作出處理的特性稱為(B)A.正確性B.健壯性C.易讀性D.高效性下列時間復(fù)雜度中最壞的是(A)A.O(n2)B.O(log2n)C.O(n)D.O(1)8?算法分析的兩個主要方面是(C)。A.可讀性和文檔性B.正確性和簡明性C.空間復(fù)雜性和時間復(fù)雜性D.數(shù)據(jù)復(fù)雜性和程序復(fù)雜性四．分析下面各程序段的時間復(fù)雜度(1)s=0;for(i=0;i<n;i++)O(n)2for(j=0;j<n;j++)O(n2)s=s+B[i][j];(2)for(i=0;i<n;i++) O(n)for(j=0;i<n;j++)2c[i][j]=i+j; O(n2)單元測驗2一．判斷題(7)(1)在線性表的鏈?zhǔn)酱嫒〗Y(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上并不一定緊鄰。(X)(3)順序存儲方式的優(yōu)點是存儲密度大，插入、刪除效率高f鏈?zhǔn)酱鎯Α?x)(4)鏈表的刪除算法簡單，因為當(dāng)刪除鏈中某個結(jié)點后，計算機會自動地將后續(xù)的各個單元向前移動。(7)(5)線性表采用順序存儲，必須占用一片連續(xù)的存儲單元。(x)(6)順序表結(jié)構(gòu)適宜于進行順序存取，而鏈表適宜于進行隨機存取。二．填空題順序表相對于鏈表的優(yōu)點是：節(jié)省存儲和隨機存取。2?鏈表相對于順序表的優(yōu)點有插入、刪除方便；缺點是存儲密度小。在一個長度為n的順序表中刪除第i個元素，要移動n-i個元素。當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快速度存取線性表中的元素時，應(yīng)采用順序存儲結(jié)構(gòu)在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過指針決定的。對一個需要經(jīng)常進行插入和刪除操作的線性表，采用鏈接存儲結(jié)構(gòu)為宜。三.選擇題1?單鏈表的存儲密度(C)。存儲密度=(結(jié)點數(shù)據(jù)本身所占的存儲量)/(結(jié)點結(jié)構(gòu)所占的存儲總量)A.大于1 B.等于1C.小于1 D.不能確定已知一個順序存儲的線性表，設(shè)每個結(jié)點需占m個存儲單元，若第一個結(jié)點的地址為B,則第i個結(jié)點的地址為(A)。A.B+(i-1)*m B.B+i*m C.B-i*m D.B+(i+1)*m在有n個結(jié)點的順序表上做插入、刪除結(jié)點運算的時間復(fù)雜度為(B)A.O(1) B.O(n) C.O(n2) D.O(log2n)下面關(guān)于線性表的敘述中，錯誤的是(B)關(guān)系。A.順序表必須占一片地址連續(xù)的存儲單元B.鏈表可以隨機存取任一元素C.鏈表不必占用一片地址連續(xù)的存儲單元D.順序表可以隨機存取任一元素鏈表不具備的特點是(C)。A.插入刪除時不需移動元素 B.不必事先估計存儲空間C.隨機訪問 D.所需空間與線性表成正比用鏈?zhǔn)酱鎯Y(jié)構(gòu)存儲的線性表，其優(yōu)點是(B)。A.便于隨機存取 B.便于插入和刪除C.花費的存儲空間比順序表少 D.數(shù)據(jù)元素的物理順序與邏輯順序相同四．程序填空1、求帶頭結(jié)點的單鏈表長的算法：intf(linknode*head,intn){P=head;n=0;While(P->next!=NULL){P=P->next;++n;}returnn;}2、 在單鏈表中查找內(nèi)容為x的結(jié)點的算法：Node*Lsearch(linknode*head,charx){P=head;while(P->next!=NULL&&P->data!=x)P=P->next;if(P->next==NULL)printf("沒有找到!\n");elsereturnP; /*找到，返回結(jié)點指針*/}3、 在帶頭結(jié)點head的單鏈表的結(jié)點a之后插入新元素x：structNode{Chardata;Node*next;};voidListInsert(Node*head,Charx){node*p,*s;p=head->next;while(p!=NULL)&&(p->data!=a)P=P->next;if(p==NULL)printf("不存在結(jié)點a,無法插入!\n");

elseelse{s=(node*)malloc(sizeof(node));:〃讓指針s指向x的地址s->data=x;s->next=p->next;p->next=s;單元測驗3一．判斷題(7)(1)棧是運算受限制的線性表。(7)(2)在棧空的情況下，不能作出棧操作，否則產(chǎn)生下溢出。(X)(3)棧一定是順序存儲的線性結(jié)構(gòu)。(7)(4)棧的特點是“后進先出”。(7)(5)鏈棧與順序棧相比，其特點之一是通常不會出現(xiàn)棧滿的情況。(X)(6)一個棧的輸入序列為：A,B,C,D,可以得到輸出序列：C,A,B,D。二．填空題在棧結(jié)構(gòu)中，允許插入、刪除的一端稱為」頂。在一個鏈棧中，若棧頂指針等于NULL,則表示?？铡Ｒ阎樞驐,在對S進行出棧操作之前首先要判斷棧是否空。從一個棧刪除元素時，首先取出棧頂元素，然后再移動棧頂指針。5?順序棧用data[n]存儲數(shù)據(jù)，棧頂指針是top,則值為x的元素入棧的操作是data[top]=x：top++：三.選擇題設(shè)有編號為1,2,3,4的四輛列車,順序進入一個棧式結(jié)構(gòu)的站臺,下列不可能的出站順序為(B)A.1234B.1423C.1324D.1243順序棧存儲空間的實現(xiàn)使用(B)存儲棧元素。A.鏈表B.數(shù)組C.循環(huán)鏈表D.變量如果以鏈表作為棧的存儲結(jié)構(gòu),則出棧操作時(B)A.必須判別棧是否滿 B.必須判別棧是否空C.必須判別棧元素類型 D.隊棧可不做任何判別4?一個棧的入棧次序ABCDE,則棧的不可能的輸出序列是(D)。A.A.EDCBAB.DECBA5、棧與一般線性表的區(qū)別在于A.數(shù)據(jù)元素的類型不同C.操作是否受限制C.ABCDE D.DCEAB(C)。數(shù)據(jù)元素的個數(shù)不同D.邏輯結(jié)構(gòu)不同6.帶頭結(jié)點的鏈棧LS的示意圖如下，棧頂元素是(A)6.帶頭結(jié)點的鏈棧LS的示意圖如下，棧頂元素是(A)A．AB．BC．CD．D單元測驗4一．判斷題(7)(1)隊列是限制在兩端進行操作的線性表。(7)(2)判斷順序隊列為空的標(biāo)準(zhǔn)是頭指針和尾指針均指向同一個結(jié)點(x)(3)在循環(huán)鏈隊列中無溢出現(xiàn)象。(X)(4)棧和隊列都是順序存儲的線性結(jié)構(gòu)。(x)(5)在隊列中允許刪除的一端稱為隊尾。(x)(6)順序隊列和順序循環(huán)隊列的隊滿和隊空的判斷條件是一樣的。二．填空題在隊列中存取數(shù)據(jù)應(yīng)遵從的原則是先進先出。在隊列中，允許插入的一端稱為—隊社。對于隊列，只能在—隊琵刪除元素。解決順序隊列“假溢出”的方法是釆用循環(huán)隊列。順序隊列的隊頭指針為front,隊尾指針為rear,則隊空的條件為front==rear。在一個鏈隊列中，若隊頭指針與隊尾指針的值相同，則表示該隊列為空。7.區(qū)分循環(huán)隊列的滿與空，有三種方法，它們是設(shè)計數(shù)器 、設(shè)標(biāo)志位 _和少用一個存儲空間 。8.循環(huán)隊列存儲在數(shù)組A[m]中，則入隊時的操作為rear=(rear+1)%m9.設(shè)順序循環(huán)隊列的隊頭指示器front指向隊頭元素，隊尾指示器rear指向隊尾元素后的一個空閑元素，隊列的最大空間為M,則用犧牲一個存儲單元區(qū)分隊列滿與空時，隊列為空的標(biāo)志為front=rear隊滿標(biāo)志為front==(rear+1)%M。10.已知鏈隊列的頭尾指針分別是Q->front和Q->rear，則將值x入隊的操作序列是p=(LQNode*)malloc(sizeof(LQNode))；p->data=x;p->next=NULL；Q->rear->next=p(進行連接)：Q->rear=p(指針后移)：三．選擇題1．同一隊列內(nèi)各元素的類型(A)。A.必須一致 B.不能一致 C.不限制 D.可以不一致2．隊列是一個(D)線性表結(jié)構(gòu)。A.不加限制的 B.推廣了的 C.非D.加了限制的四個元素按:A,B,C,D順序連續(xù)進隊Q,執(zhí)行一次出隊操作后，隊頭元素是(先進先出(C)A.D B.CC.B D.A若用一個大小為6的數(shù)組來實現(xiàn)循環(huán)隊列，且當(dāng)前front和rear的值分別為3和0,當(dāng)從隊列中刪除一個元素，再加入兩個元素后，front和rear的值分別為(B)。出隊一個元素front+1入隊一個元素rear+1D.1和5刪除值最小的元素D.判斷是否還有元素A.5和1B.D.1和5刪除值最小的元素D.判斷是否還有元素以下屬于隊列的操作有(D)。A.在隊首插入元素 B按元素的大小排序6.設(shè)棧S和隊列Q的初始狀態(tài)為空，元素el,e2,e3,e4,e5和e6依次通過棧S，一個元素出棧后即進隊列Q，若6個元素出隊的序列是e2,e4,e3,e6,e5,e1則棧S的容量至少應(yīng)該是(C)。A. A. 6 B.4C.3 D.2單元測驗5一、選擇題若對n階對稱矩陣A(行下標(biāo)和列下標(biāo)范圍均為1???n),將其下三角形的元素(包括主對角線上所有元素)依次存放于一維數(shù)組B[0..(n(n+l))/2-l]中，則在B中確定ay(i<j的位置k的關(guān)系為(B)。A.i*(i-1)/2+j-1B.j*(j-1)/2+i-1C.i*(i+1)/2+jD.j*(j+1)/2+i注意：1?下標(biāo)從1開始2?對稱矩陣3.i<j同時滿足這三個條件答案為B1?下標(biāo)從1開始2.對稱矩陣3?i>=j同時滿足這三個條件答案為A1?下標(biāo)從0開始2.對稱矩陣3.i<j同時滿足這三個條件答案為D1?下標(biāo)從0開始2.對稱矩陣3.i>=j同時滿足這三個條件答案為C假設(shè)以行序為主序存儲二維數(shù)組A=array[1..1OO,1..100]，設(shè)每個數(shù)據(jù)元素占2個存儲單元，基地址為10,則LOC[5,5]=(B)(注意該題下標(biāo)從1開始：計算10+(4*100+4)*2=818若下標(biāo)從0開始則結(jié)果為1020注意列主序算法的不同)A.808 B.818 C.1010 D.1020設(shè)有數(shù)組A[i,j],數(shù)組的每個元素長度為3字節(jié)，i的值為1到8,j的值為1至到10,數(shù)組從內(nèi)存首地址BA開始順序存放，當(dāng)用以列為主存放時，元素A[5,8]的存儲首地址為(B)。同下題8行10列填完一列再填下一列到A[4,8]—共60個元素A.BA+141 B.BA+180 C.BA+222 D.BA+225二維數(shù)組A的每個元素是由6個字符組成的串，其行下標(biāo)i=0,1,?,8,列下標(biāo)j=1,2,?,10。若A按行優(yōu)先存儲，元素A[8,5]的起始地址與當(dāng)A按列優(yōu)先存儲時的元素(B)的起始地址相同。設(shè)每個字符占一個字節(jié)。計算方法：該2維數(shù)組一共是9行10列即每行10個元素，每列9個元素行主序(也就是填滿一行再填下一行)A[8,5]相當(dāng)于第(8*10+5)=85個元素當(dāng)為列主序(即填滿一列再填下一列)的時候85/9=9。。。4即可以填滿9列還剩4個元素即A[3,10]A.A[8,5] B.A[3,10] C.A[5,8] D.A[0,9]設(shè)有一個10階的對稱矩陣A,采用壓縮存儲方式，以行序為主存儲，an為第一元素，其存儲下標(biāo)序號為1,則a85的下標(biāo)序號為(B)。85alla21a22a31a32a33……(若為列主序就是alla12...a110a21)以此類推。那么a11到a77—共有(1+7)*7/2=28個。a81到a85是5個，所以就是33。A.13 B.33 C.18 D.40有一個100*90的稀疏矩陣，非0元素有10個，設(shè)每個整型數(shù)占2字節(jié)，則用三元組表示該矩陣時，所需的字節(jié)數(shù)是(B)。a(ij,k)其中i是非0元素的行，j是非0元素的列，k是值。在用三元組表示稀疏矩陣，還要三個成員來記住，矩陣的行數(shù)列數(shù)，總的元素數(shù)，所以所需的字節(jié)數(shù)是10*(1+1+1)*2+3*2=66A.60 B.66 C.18000 D.33單元測驗6一．判斷題(7)(1)二叉樹的前序遍歷中，任意一個結(jié)點均處于其孩子結(jié)點的前面。(7)(2)由二叉樹的前序遍歷序列和中序遍歷序列，可以推導(dǎo)出后序遍歷的序列。(7)(3)在完全二叉樹中，若一個結(jié)點沒有左孩子，則它必然是葉子結(jié)點。(7)(4)具有n個葉子結(jié)點的哈夫曼樹共有2n-1個結(jié)點。二．填空題在樹中，一個結(jié)點所擁有的子樹數(shù)稱為該結(jié)點的度。度為零的結(jié)點稱為葉結(jié)點。由一棵二叉樹的前序序列和中序序列可唯一確定這棵二叉樹。哈夫曼樹是帶權(quán)路徑長度的二叉樹。已知完全二叉樹的第8層有8個結(jié)點(根結(jié)點計為第1層)，則其葉結(jié)點數(shù)是 —。(畫圖)三個結(jié)點可以組成二種不同形態(tài)的樹。將一棵完全二叉樹按層次從0開始編號，對于為5的結(jié)點，該結(jié)點左孩子的編號為：。左孩子2n+1結(jié)點最少的二叉樹是空二叉樹。對于二叉樹來說，第5層上至多有16個結(jié)點。2k-110?深度為5的二叉樹至多有31個結(jié)點。最多?滿二叉樹2^-1最少?單支樹k+1具有n個結(jié)點的滿二叉樹層數(shù)lo%(n+1)下取整葉結(jié)點數(shù)為no,度為2的結(jié)點為巴，則有關(guān)系n0=n2+1三.選擇題樹最適合用來表示(B)。A.有序數(shù)據(jù)元素 B.元素之間有分支層次的關(guān)系C.元素之間無聯(lián)系的數(shù)據(jù) D.無序數(shù)據(jù)元素前序為A，B，C的二叉樹共有(A)種。TOC\o"1-5"\h\zA.5 B.4 C.3 D.2根據(jù)二叉樹的定義，具有3個結(jié)點的二叉樹有(C)種樹型。A.3 B.4 C.5 D.6將一棵有80個結(jié)點的完全二叉樹從上到下，從左到右依次對結(jié)點編號，根結(jié)點的編號為0，則編號為38的結(jié)點的右孩子編號為(C)。右孩子2n+2A.76 B.77 C.78 D.79用5個權(quán)值｛3,2,4,5,1｝構(gòu)造的哈夫曼樹的帶權(quán)路徑長度是(B)(畫圖)A.32 B.33 C.34 D.15WPL=4*2+5*2+3*2+2*1+1*1=336?在樹結(jié)構(gòu)中，若結(jié)點B有3個兄弟，A是B的父親結(jié)點，則A的度為為(B)。\o"CurrentDocument"A.3 B.4 C.5 D.6下列陳述正確的是(C)。A.二叉樹是度為2的有序樹 B?二叉樹中結(jié)點只有一個孩子時無左右之分C.二叉樹中最多只有兩棵子樹，且有左右子樹之分 D.二叉樹中必有度為2的結(jié)點某二叉樹的前序遍歷序列為:DABCEFG，中序遍歷序列為:BACDFGE，則層次遍歷序列為(C)。A.BCAGFEDB.ABCDEFG C.DAEBCFG D.BCAEFGD

四．應(yīng)用題1、某二叉樹的結(jié)點數(shù)據(jù)采用順序存儲，其結(jié)構(gòu)如下（其中，“/\”表示結(jié)點為空）：0123456789ABC八DEF八八G請畫出該二叉樹，并分別寫出按前序、中序、后序、層序遍歷的結(jié)點序列。解法：按照滿二叉樹寫出編號，然后依次填充。2、已知一棵二叉樹的中序遍歷結(jié)點序列為BFDGAEHC,后序遍歷結(jié)點序列為FGDBHECA。請畫出此二叉樹，并寫出該樹的前序遍歷結(jié)點序列。ABDFGCEH3．已知一棵二叉樹的后序遍歷和中序遍歷的序列分別為：A,C,D,B,G,I,H,F,E和A,B,C,D,E,F,G,H,I請畫出該二叉樹，并寫出它的前序遍歷的序列。答：恢復(fù)的二叉樹為其前序遍歷的序列為4．已知一棵二叉樹的前序遍歷和中序遍歷的序列分別為：A，B，D，G，H，C，E，F(xiàn)，I和G，D，H，B，A，E，C，I，F(xiàn)請畫出此二叉樹，并寫出它的后序遍歷的序列。答：恢復(fù)的二叉樹為其后序遍歷的序列為：GHDBEIFCA5.已知一棵樹的層次遍歷的序列為：ABCDEFGHIJ,中序遍歷的序列為：DBGEHJACIF,請畫出該二叉樹，并寫出它的后序遍歷的序列。解：

解：6、某二叉樹的結(jié)點數(shù)據(jù)采用順序存儲，其結(jié)構(gòu)如下：1234567891011121314151617181920EAFDHCGIB1）畫出該二叉樹（3分）2）寫出按層次遍歷的結(jié)點序列（2分）解：（解：（1）7、 某二叉樹的存儲如下：00237580101JHFDBACEGI000940000012346891057lchilddatarchild其中根結(jié)點的指針為6，lchild、rchild分別為結(jié)點的左、右孩子的指針域，data為數(shù)據(jù)域。（1）畫出該二叉樹（3分）（2）寫出該樹的前序遍歷的結(jié)點序列（2分）1）解：（2）前序遍歷的結(jié)點序列：ABCEDFHGIJ

1）哈夫曼樹的構(gòu)造方法：依次選擇權(quán)值最小和次小的數(shù)的數(shù)分別作為二叉樹的左右孩子WPL的計算以及哈弗曼編碼給定一個權(quán)集W={4,5,7,8,6,12,18}，試畫出相應(yīng)的哈夫曼樹，并計算其帶權(quán)路徑長度WPL。WPL=(12+18)*2+(6+7+8)*3+(4+5)*4=159給定一個權(quán)集W={3,15,17,14,6,16,9,2},試畫出相應(yīng)的哈夫曼樹,并計算其帶權(quán)路徑長度WPL解WPL=(16+17)*2+(9+14+15)*3+6*4+(2+3)*5=2295?假設(shè)用于通信的電文僅由A、B、C、D、E、F、G、H8個字母組成，字母在電文中出現(xiàn)的頻率分別為7,19,2,6,32,3,21,10。試為這8個字母設(shè)計哈夫曼編碼。23字母編號對應(yīng)編碼出現(xiàn)頻率A10107B0019C100002D10016E1132F100013G0121H101110解：以權(quán)值：2、323字母編號對應(yīng)編碼出現(xiàn)頻率A10107B0019C100002D10016E1132F100013G0121H101110單元測驗7一．判斷題(X)(1)在無向圖中，(VI,V2)與(V2,VI)是兩條不同的邊。(X)(2)鄰接表只能用于有向圖的存儲。(7)(3)一個圖的鄰接矩陣表示是唯一的。(X)(4)有向圖不能進行廣度優(yōu)先遍歷。(7)(5)若一個無向圖中任一頂點出發(fā)，進行一次深度優(yōu)先遍歷，就可以訪問圖中所有的頂點，則該圖一定是連通的。二．填空題圖有：鄰接矩陣和鄰接表等常用存儲方式。圖的遍歷有:深度優(yōu)先搜索和廣度優(yōu)先搜索等方法。圖的鄰接矩陣表示法是表示頂點—之間相鄰關(guān)系的矩陣。有向圖G用鄰接矩陣存儲，其第i行的所有元素之和等于頂點i的 出度。有向圖的鄰接矩陣表示中，第i列上非0元素的個數(shù)為頂點i的入度。6?設(shè)有一稀疏圖G,則G采用鄰接表 存儲比較節(jié)省空間。設(shè)有一稠密圖G,則G采用鄰接矩陣—存儲比較節(jié)省空間。n個頂點的有向完全圖有n(n-1) 條邊。若為無向圖則有n(n-1/2條邊9?對于具有n個頂點的圖，其生成樹有且僅有n-1條邊。無向圖的鄰接矩陣一定是對稱矩陣。三.選擇題在下列表示方法中，(D)是有向圖邊的表示方法。A.(1，2) B.(1，2> C.<1，2) D.<1，2>在一個有向圖中，所有頂點的入度之和等于所有頂點的出度之和的(B)倍。A.1/2 B.1 C.2 D.4對于一個具有n個頂點的無向圖的邊數(shù)最多有(B)。A.n B.n(n-1)/2 C.n(n-1) D.2n在一個具有n個頂點的無向圖中，要連通全部頂點至少需要(B)條邊。A.n B.n-1 C.n+1 D.n/25?有8個結(jié)點的有向完全圖有(C)條邊。n(n-1)A.14 B.28 C.56 D.112無向圖頂點v的度是關(guān)聯(lián)于該頂點(B)的數(shù)目。A.頂點 B.邊 C.序號 D.下標(biāo)有n個頂點的無向圖的鄰接矩陣是用(B)數(shù)組存儲。A.—維 B.n行n列 C.任意行n列 D.n行任意列在一個具有n個頂點e條邊的圖中，所有頂點的度數(shù)之和等于(C)。舉例得出結(jié)論即可A.e B.n C.2e D.2n四．應(yīng)用題1．根據(jù)如下無向圖(1)畫出該圖的鄰接矩陣和鄰接表(2)并分別給出該圖鄰接矩陣下的深度優(yōu)先搜索遍歷和廣度優(yōu)先搜索遍歷的結(jié)點序列。鄰接矩陣鄰接表表示方法ABABCDEFGA0110000B1011000C1001000D0110110E0001001F0001001G0000110A—>B—>CB—>A—>DC—>A—>DD—>B—>C—>E—>FE—>D—>GF—>D—>GG—>E—>F深度優(yōu)先遍歷ABDCEGF廣度優(yōu)先遍歷ABCDEFG2?分別用普里姆(Prim)算法和克魯斯卡爾(Kruskal)算法畫出構(gòu)造該無向帶權(quán)圖最小生成樹的過程。單元測驗8一．判斷題(X)(1)如果某種排序算法不穩(wěn)定，則該排序方法就沒有實際應(yīng)用價值。(7)(2)對n個記錄的進行快速排序，所需要的平均時間是O(nlog2n)(X)(3)堆排序所需的時間與待排序的記錄個數(shù)無關(guān)。(7)(4)當(dāng)待排序的元素個數(shù)很多時，為了交換元素的位置要占用較多的時間，這是影響時間復(fù)雜度的主要因素。(7)(5)對快速排序來說，初始序列為遞增有序或遞減有序都是最壞情況。(7)(6)采用希爾方法排序時，若關(guān)鍵字的排列雜亂無序，則效率較高。二．填空題大多數(shù)排序算法都有兩個基本的操作:比較和移動對n個關(guān)鍵字進行冒泡排序，時間復(fù)雜度為O(誼)?？焖倥判蛟谧顗那闆r下的時間復(fù)雜度是O(n2)。在排序前，關(guān)鍵字值相等的不同記錄，排序后相對位置保持_丕變一的排序方法，稱為穩(wěn)定的排序方法。當(dāng)增量為1時，該趟希爾排序與直接插入排序基本一致。第一趟排序后，序列中鍵值最大的記錄交換到最后的排序算法是冒泡排序。依次將待排序的每個記錄插入到一個有序已排序序列中的排序方法稱為插入排序。對一組記錄(54,38，96，23，15，72，60，45，83)進行直接插入排序時，當(dāng)把第7個記錄60插入到有序表時，為尋找插入位置需比較3_次。有序區(qū)［152338547296］無序區(qū)［604583］待插入元素60先和96比較再和72比較最后和54比較兩個序列分別為:L1={25，57，48，37，92，86，12，33}交換15次L2={25，37，33，12，48，57，86，92}交換4次用冒泡排序法對L1和L2進行排序，交換次數(shù)較少的是序列：.L2—。對一組記錄(54,35，96，21，12，72，60，44，80)進行直接選擇排序時，第四次選擇和交換后，未排序記錄是54,72,60,96,80第一次有序區(qū)［12］無序區(qū)［3596215472604480］第二次有序區(qū)［1221］無序區(qū)［96355472604480］第三次有序區(qū)［122135］無序區(qū)［965472604480］第四次有序區(qū)［12213544］無序區(qū)［5472609680］三.選擇題排序是根據(jù)(A)的大小重新安排各元素的順序。A.關(guān)鍵字B.數(shù)組C.元素件D.結(jié)點排序方法中，從無序序列中選擇關(guān)鍵字最小的記錄，將其與無序區(qū)(初始為空)的第一個記錄交換的排序方法，稱為(B)。A.插入排序 B.選擇排序 C.希爾排序 D.快速排序每次把待排序方的區(qū)間劃分為左、右兩個區(qū)間，其中左區(qū)間中元素的值不大于基準(zhǔn)元素的值，右區(qū)間中元素的值不小于基準(zhǔn)元素的值，此種排序方法叫做(D)。A.冒泡排序 B.堆排序 C.希爾排序 D.快速排序快速排序在(C)情況下最易發(fā)揮其長處。A.待排序的數(shù)據(jù)中含有多個相同的關(guān)鍵字B.待排序的數(shù)據(jù)已基本有序C.待排序的數(shù)據(jù)完全無序 D.待排序的數(shù)據(jù)中最大值與最小值相差懸殊直接插入排序的方法是從第(B)個元素開始，插入到前邊適當(dāng)位置的排序方法。A.1 B.2 C.3 D.n第一個元素初始時已經(jīng)選定為a［0］堆的形狀是一棵(C)。A.二叉排序樹 B.滿二叉樹 C.完全二叉樹 D.任意二叉樹7．內(nèi)排序是指在排序的整個過程中，全部數(shù)據(jù)都在計算機的（A）中完成的排序。A.內(nèi)存B.外存C.內(nèi)存和外存 D.寄存器外排序則是將數(shù)據(jù)部分導(dǎo)入內(nèi)存依次排序下述幾種排序方法中，平均時間復(fù)雜度最小的是（A）。A.希爾排序O（n1-3） B.直接插入排序 C.冒泡排序D.直接選擇排序?qū)個數(shù)據(jù)進行快速排序，在最壞情況下，算法的時間復(fù)雜度是（B）。A.O（n） B.O（n2） C.O（nlog2n） D.O（n3）冒泡排序的方法對n個數(shù)據(jù)進行排序，第一趟排序共需要比較（C）次。A.1 B.2 C.n-1D.n用直接插入排序法對下面的四個序列進行由小到大的排序，元素比較次數(shù)最少的是（B）。A，94， 32， 40， 90， 80， 46， 21， 69 B. 21，32，46，40，80，69，90，94C.32， 40， 21， 46， 69， 94， 90， 80 D. 90，69，80，46，21，32，94，40一個數(shù)據(jù)序列的關(guān)鍵字為：（46，79，56，38，40，84），采用快速排序，并以第一個數(shù)為基準(zhǔn)得到第一次劃分的結(jié)果為：（C）以46（Low）為基準(zhǔn)進行第一次快速排序（遞歸）?先右后左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，79，56，84）四.應(yīng)用題已知數(shù)據(jù)序列｛80，18，9，90，27，75，42，69｝，試寫出采用冒泡排序（從小到大）算法排序時，每一趟排序的結(jié)果。第一次189802775426990第二次918277542698090第三次918274269758090已知數(shù)據(jù)序列｛40，63，11，84，35，93，58，39｝，試寫出采用直接選擇排序（從小到大）每一趟排序結(jié)果。第一次11 63408435935839第二次1135408463935839第三次1135398463935840第四次11353940 84639358第五次1135394058639384第六次113539405863 9384第七次11353940586384 93第八次1135394058638493已知數(shù)據(jù)序列｛12，2，16，30，28，10，17，20｝，寫出希爾排序（從小到大）每一趟（設(shè)d=4,2,1）的排序結(jié)果。第一次122162028101730第二次122161017202830第三次212101617202830已知數(shù)據(jù)序列｛10,1,15a,18,7,15b｝（ab為了區(qū)別兩個15）,試寫出采用快速排序（從小到大）每一趟排序的結(jié)果。第一次17101815a15b第二次171015b15a185．已知數(shù)據(jù)序列{18，17，60，40，07，32，73趟排序結(jié)果。第一次18 17604007327365第二次1718 604007327365第三次171860 4007327365第四次17184060 07327365第五次0717184060 327365第六次071718324060 7365第七次07171832406073 65第八次0717183240606573五．程序填空1．直接選擇排序VoidSelectSort(DataTypea[],intn){inti,j,small;DataTypetemp;for(i=0;i<n-1;i++){Small=i;for(j=i+1;j<n;i++)if(a[j].key<a[small].key)small=j;if(small!=i){temp=a[i];a[i]=a[small];a[small=temp;}}}

65}，試寫出采用直接插入排序(從小到大)每2、直接插入排序VoidInsertSort(DataTypea[],intn){inti,j;DataTypetemp;for(i=0;ivn-1;i++){temp=a[i+1];j=i；while(j>-1&&temp.keyva[j].key){aj+1]=a[i];j--；}a[j+1]=temp;}}3、冒泡排序VoidBubbleSort(DataTypea[],intn){intij,flag=1;DataTypetemp;for(i=0;ivn-1&&flag==1;i++){flag=0;for(j=0;jvn-1-i;j++){if(a[j].key >a[j+1].key){flag=1;temp=a[j];a[j]=aj+1];a[j+1]=temp;}}}}單元測驗9一．判斷題(7)(1)二分査找法要求待査表的關(guān)鍵字值必須有序。(X)(2)對有序表而言采用二分查找總比采用順序查找法速度快。 慢(X)(3)在二叉排序樹中，根結(jié)點的值都小于孩子結(jié)點的值。 小于右孩子結(jié)點的值(7)(4)哈希表是一種將關(guān)鍵字轉(zhuǎn)換為存儲地址的存儲方法。(7)(5)哈希法的查找效率主要取決于哈希表構(gòu)造時選取的哈希函數(shù)和處理沖突的方法。(X)(6)在二叉排序樹上刪除一個結(jié)點時，不必移動其它結(jié)點，只要將該結(jié)點的父結(jié)點的相應(yīng)的指針域置空即可。二．填空題1?在分塊查找方法中，首先查找索引表，然后再查找相應(yīng)的塊。2?順序查找、二分查找、分塊查找都屬于靜態(tài)查找。對于長度為n的線性表，若進行順序查找，則時間復(fù)雜度為O(n)。4?對于長度為n的線性表，若采用二分査找，則時間復(fù)雜度為：O(log2n)_。在關(guān)鍵字序列(7,10，12，18，28，36,45，92)中，用二分查找法查找關(guān)鍵字92,要比較4次才找到。第一次mid=(low+high)/2=3查找a[3]=18,low=mid+1=4第二次mid=(low+high)/2=5查找a[5]=36,low=mid+1=6第三次mid=(low+high)/2=6查找a[6]=45,low=mid+1=7第四次mid=(low+high)/2=7查找a[7]=92?對二叉排序樹進行查找的方法是用待查的值與根結(jié)點的鍵值進行比較，若比根結(jié)點小，則繼續(xù)在，左子樹中杳找。7?二叉排序樹是一種動態(tài)查找表。哈希法既是一種存儲方法，又是一種至找方法。設(shè)哈希函數(shù)H(k)和鍵值匕，k2，若k子k2，且H(k1)=H(k2),則稱這種現(xiàn)象為哈希沖突。處理沖突的兩類主要方法是開放定址法和鏈表法。在哈希函數(shù)H(key)=key%P中，P一般應(yīng)取質(zhì)數(shù)。 為了最大情況避免哈希沖突在査找過程中有插入元素或刪除元素操作的，稱為_動基査找。三.選擇題對線性表進行二分查找時，要求線性表必須(B)。A.以順序方式存儲 B.以順序方式存儲，且結(jié)點按關(guān)鍵字有序排序C.以鏈接方式存儲 D.以