國家開放大學《數據結構（本）》單元測試參考答案

1、國家開放大學數據結構（本）單元測試參考答案單元1 緒論1.數據結構中，與所使用的計算機無關的是數據的（ ）。A. 物理和存儲結構B. 物理結構C. 邏輯結構D. 存儲結構2.組成數據的基本單位是（ ）。A. 數據變量B. 數據項C. 數據類型D. 數據元素3.研究數據結構就是研究（ ）。A. 數據的存儲結構B. 數據的邏輯結構和存儲結構C. 數據的邏輯結構D. 數據的邏輯結構和存儲結構以及其數據在運算上的實現4.在數據結構中，從邏輯上可以把數據結構分成（ ）。A. 線性結構和非線性結構B. 動態結構和靜態結構C. 緊湊結構和非緊湊結構D. 內部結構和外部結構5.數據結構是一門研究計算機中（ ）

2、對象及其關系的科學。A. 非數值運算B. 集合C. 數值運算D. 非集合6.下列說法不正確的是（ ）。A. 數據項是數據中不可分割的最小可標識單位B. 數據項可由若干個數據元素構成C. 數據可由若干個數據元素構成D. 數據元素是數據的基本單位7.設有如下遺產繼承規則：丈夫和妻子可以互相繼承遺產，子女可以繼承父親和母親的遺產，子女間不能相互繼承，則表示該遺產繼承關系最合適的數據結構應該是（ ）結構。A. 樹形B. 線性C. 圖狀D. 集合8.算法的時間復雜度與（ ）有關。A. 算法本身B. 數據結構C. 所使用的計算機D. 算法的程序設計9.算法分析的兩個主要方面是（ ）。A. 正確性和簡明性B

3、. 可讀性和文檔性C. 時間復雜性和空間復雜性D. 數據復雜性和程序復雜性10.數據的存儲結構包括數據元素的表示和（ ）。A. 數據元素間關系的表示B. 相關算法C. 數據處理的方法D. 數據元素的類型11.數據元素是數據的最小單位（×）。12.數據的邏輯結構是指數據的各數據項之間的邏輯關系（×）。13.算法的優劣與算法描述語言無關，但與所用計算機有關（×）。14.算法是在數據結構的基礎上對特定問題求解步驟的一種描述，也是若干條指令組成的優先序列（）。15.算法可以用不同的語言描述，如果用C語言等高級語言來描述，則算法實際上就是程序了（×）。16.程序一

4、定是算法（×）。17.數據的物理結構是指數據在計算機內的實際存儲形式（）。18.數據結構中評價算法的兩個重要指標是時間復雜度和空間復雜度（）。19.在順序存儲結構中，有時也存儲數據結構中元素之間的關系（×）。單元2 線性表1.線性表的順序存儲比鏈式存儲最與利于進行（ ）操作。A. 表頭插入或刪除B. 表尾插入或刪除C. 按值插入或刪除D. 查找2.鏈表不具備的特點是（ ）。A. 不必事先估計存儲空間B. 所需空間與其長度成正比C. 插入、刪除不需要移動元素D. 可隨機訪問任一結點3.向一個有127個元素的順序表中插入一個新元素，并保持原來的順序不變，平均要移動（ ）個元素。

5、A. 63B. 7C. 8D. 63.54.在一個長度為n的順序存儲線性表中，向第i個元素（1in）之前插入一個新元素時，需要依次后移（ ）個元素。A. n-i-1B. n-i+1C. iD. n-i5.在一個長度為n的順序存儲線性表中，刪除第i個元素（1in），需要前移（ ）個元素。A. n-i-1B. iC. n-i+1D. n-i6.一個順序存儲線性表的第一個元素的存儲地址是90，每個元素的長度是2，則第6個元素的存儲地址是（ ）。A. 106B. 98C. 102D. 1007.用鏈表表示線性表的優點是（ ）。A. 便于插入和刪除B. 便于隨機存取C. 數據元素的物理順序和邏輯順序相同

6、D. 花費的存儲空間較順序存儲少8.帶頭結點的鏈表為空的判斷條件是（ ）（設頭指針為head）。A. head->next=NULLB. head->next=headC. head=NULLD. head!=NULL9.非空的單向循環鏈表的尾結點滿足（ ）（設頭指針為head，指針p指向尾結點）。A. p->next=NULLB. p=headC. p->next=headD. p=NULL10.在一個單鏈表中，p、q分別指向表中兩個相鄰的結點，且q所指結點是p所指結點的直接后繼，現要刪除q所指結點，可用語句（ ）。A. p->next=qB. p->ne

7、xt=q->nextC. q->next=NULLD. p=q->next11.線性表在鏈式存儲中各結點之間的地址（ ）。A. 必須連續B. 部分地址必須連續C. 連續與否無所謂D. 不能連續12.有關線性表的正確說法是（ ）。A. 表中的元素必須按由小到大或由大到下排序B. 線性表至少要求一個元素C. 除了一個和最后一個元素外，其余元素都有一個且僅有一個直接前驅和一個直接后繼D. 每個元素都有一個直接前驅和一個直接后繼13.若某線性表最常用的操作是存取任一指定序號的元素和在最后進行插入和刪除運算，則利用（ ）存儲方式最省時間。A. 雙向循環鏈表B. 帶頭結點的雙向循環鏈表C

8、. 單向循環鏈表D. 順序表14.在單鏈表中，若*p不是尾結點，在其后插入*s結點的操作是（ ）。A. s->next=p->next;p=s;B. s->next=p->next;p->next=s;C. s->next=p;p->next=s;D. p->next=s;s->next=p;15.在一個長度為n的順序表中為了刪除第5個元素，由第6個元素開始從后到前依次移動了15個元素。則原順序表的長度為（ ）。A. 19B. 25C. 21D. 2016.對于一個具有n個結點的單向鏈表，在給定值為x的結點之后插入一個新結點的時間復雜度為（

9、 ）。A. O(1)B. O(n3)C. O(n2)D. O(n)17.設順序存儲的線性表長度為n，對于插入操作，設插入位置是等概率的，則插入一個元素平均移動元素的次數為（ ）。A. nB. n-i+1C. n-1D. n/218.線性表的順序結構中，（ ）。A. 進行數據元素的插入、刪除效率較高B. 邏輯上相鄰的元素在物理位置上也相鄰C. 邏輯上相鄰的元素在物理位置上不一定相鄰D. 數據元素是不能隨機訪問的19.以下說法中不正確的是（ ）。A. 雙向循環鏈表中每個結點需要包含兩個指針域B. 單向循環鏈表中尾結點的指針域中存放的是頭指針C. 順序存儲的線性鏈表是可以隨機訪問的D. 已知單向鏈表

10、中任一結點的指針就能訪問到鏈表中每個結點20.以下表中可以隨機訪問的是（ ）。A. 單向鏈表B. 單向循環鏈表C. 順序表D. 雙向鏈表21.設鏈表中的結點是NODE類型的結構體變量，且有NODE *p；為了申請一個新結點，并由p指向該結點，可用以下語句（ ）。A. p=(NODE)malloc(sizeof(p);B. p=(NODE*)malloc(sizeof(NODE);C. p=(*NODE)malloc(sizeof(NODE);D. p=(NODE*)malloc(sizeof(p);22.設head為非空的單向循環鏈表頭指針，p指向鏈表的尾結點，則滿足邏輯表達式（ ）的值為真。

11、A. p->next=NULLB. p=NULLC. p->next=headD. p-=head23.順序存取的線性表樂意隨機存取（）。24.由于順序存儲要求連續的存儲區域，所以在存儲管理上不夠靈活（）。25.線性表中的元素可以是各種各樣的，但同一線性表中的數據元具有相同的特性，因此是屬于同一數據對象（）。26.在線性表的順序存儲結構中，邏輯上相鄰的兩個元素但是在物理上位置并不一定是相鄰的（×）。27.在單鏈表中，任何兩個元素的存儲位置之間都有固定的聯系，因為可以從頭結點進行查找任何一個元素（×）。28.線性表的鏈式存儲結構優于順序存儲結構（×）。2

12、9.在線性表的順序存儲結構中，插入和刪除元素時，移動元素的個數與該袁術的位置有關（）。30.在單鏈表中，要取得某個元素，只要知道該元素的指針機可，因此單鏈表是隨機存取的存儲結構。（×）31.順序存儲方式只能用于存儲線性結構。（×）32.順序存儲方式的有點是存儲密度大，且插入、刪除運算效率高。（×）單元3 棧和隊列1.一個順序棧一旦被聲明，其占用空間的大小（ ）。A. 已固定B. 動態變化C. 可以改變D. 不能固定2.鏈棧和順序棧相比，有一個比較明顯的缺點，即（ ）。A. 不會出現棧空的情況B. 插入操作更加方便C. 刪除操作更加方便D. 通常不會出現棧滿的情況3

13、.用單鏈表表示的鏈式隊列的隊頭在鏈表的（ ）位置。A. 鏈頭B. 任意位置C. 鏈尾D. 鏈中4.在解決計算機主機與打印機之間速度不匹配問題時通常設置一個打印數據緩沖區，主機將要輸出的數據依次寫入緩沖區中，而打印機則從緩沖區中取出數據打印，該緩沖區應該是一個（ ）結構。A. 數組B. 堆棧C. 隊列D. 線性表5.循環隊列Am 存放其元素，用front和rear分別表示隊頭及隊尾，則循環隊列滿的條件是（ ）。A. （rear+1)%m=frontB. （rear=frontC. （rear+1)%m-1=frontD. （rear =front+16.在一個棧頂指針為top的鏈棧中，將一個p指

14、針所指的結點入棧，應執行（ ）。A. p->next=top; top=p;B. top->next=p;C. p->next=top->next; top->next=p;D. p->next=top->next; top=top->next;7.在一個棧頂指針為top的鏈棧中刪除一個結點時，用 x保存被刪結點的值，則執行（ ）。A. x=top->data; top=top->next;B. x=top;top=top->next;C. top=top->next; x=top->data;D. x=top-&g

15、t;data;8.在一個鏈隊中，設front和rear分別為隊首和隊尾指針，則插入p所指結點時，應執行（ ）。A. p->next=rear;rear=p;B. rear->next=p;rear=p;C. front->next=p;front=p;D. p->next=front;front=p;9.在鏈隊列中，f和r分別為隊頭和隊尾指針，要把s所指結點入隊，應執行（ ）。A. r->next=s-> next; r=s;B. r->next=s;C. r->next=s;r=s;D. r->next=s-> next;10.設t

16、op是一個鏈棧的棧頂指針，棧中每個結點由一個數據域data和指針域next組成，設用x接收棧頂元素，則取棧頂元素的操作為（ ）。A. x=top->data;top= top->next;B. top=top->next;C. x=top->data;D. top->data=x;11.一個隊列的入隊序列是2，4，6，8，則隊列的輸出序列是（ ）。A. 6，4，2，8B. 4，2，8，6C. 2，4，6，8D. 8，6，4，212.一個棧的進棧序列是5，6，7，8，則棧的不可能的出棧序列是（ ）。（進出棧操作可以交替進行）A. 8，7，6，5B. 7，6，8，5C

17、. 7，6，5，8D. 5，8，6，713.棧的插入刪除操作在（ ）進行。A. 棧底B. 棧頂C. 指定位置D. 任意位置14.棧和隊列的相同點是（ ）。A. 邏輯結構與線性表相同，都是操作規則受到限制的線性表B. 邏輯結構與線性表不同C. 都是后進后出D. 都是后進先出15.以下說法正確的是（ ）。A. 棧的特點是先進先出，隊列的特點是先進后出B. 棧和隊列的特點都是先進后出C. 棧和隊列的特點都是先進先出D. 棧的特點是先進后出，隊列的特點是先進先出16.設有一個帶頭結點的鏈隊列，隊列中每個結點由一個數據域data和指針域next組成，front和rear分別為鏈隊列的頭指針和尾指針。設p

18、指向要入隊的新結點(該結點已被賦值)，則入隊操作為（ ）。A. rear->next=p;p = rear;B. rear->next=p;rear=p;C. p =rear->next;rear=p;D. rear=p;rear->next=p;17.設有一個帶頭結點的鏈隊列，隊列中每個結點由一個數據域data和指針域next組成，front和rear分別為鏈隊列的頭指針和尾指針，要執行出隊操作，用x保存出隊元素的值，p為指向結點類型的指針，可執行如下操作：p=front->next;x=p->data;然后指行（ ）。A. front->next=

19、p->next;B. front=p->next;C. front=p;D. front->next =p;18.以下說法不正確的是（ ）。A. 順序隊列中，當尾指針已經超越隊列存儲空間的上界，則一定是隊列已滿B. 順序隊列中，隊列的頭指針和尾指針均超越隊列存儲空間的上界，則隊列已空C. 順序棧中，棧滿時再進行進棧操作稱為“上溢”D. 順序棧中，棧空時再作出棧棧操作稱為“下溢”19.一個遞歸算法必須包括（ ）。A. 迭代部分B. 終止條件和迭代部分C. 遞歸部分D. 終止條件和遞歸部分20.假定一個鏈式隊列的隊頭和隊尾指針分別為front和rear，則判斷隊空的條件為（ ）。

20、A. front=NULLB. front!=NULLC. rear!=NULLD. front=rear21.向順序棧中壓入新元素時，應當（ ）。A. 先存入元素，再移動棧頂指針B. 同時進行C. 先后次序無關緊要D. 應當先移動棧頂指針，再存入元素22.判斷一個循環隊列Q（最多元素為m）為滿的條件是（ ）。A. Q->front=(Q->rear+1)%mB. Q->rear!=(Q->front+1)%mC. Q->front=Q->rearD. Q->front=Q->rear+122.判斷棧滿（元素個數最多n個）的條件是（ ）。A. t

21、op=n-1B. top!=0C. top=-1D. top=024.隊列的刪除操作是在（ ）。A. 隊頭B. 隊尾C. 隊后D. 隊前25.一個隊列的入隊序列是a,b,c,d,按該隊列的可能輸出序列使各元素依次入棧，該棧的可能輸出序列是 （ ）。（進棧出棧可以交替進行）。A. d,a,b,cB. d,b,a,cC. c,a,b,dD. d,c,b,a單元4 串1.以下陳述中正確的是（ ）。A. 串的長度必須大于零B. 串是一種特殊的線性表C. 空串就是空格串D. 串中元素只能是字母2.設有兩個串p和q，其中q是p的子串，q在p中首次出現的位置的算法稱為（ ）。A. 匹配B. 求子串C. 連接

22、D. 求串長3.串是（ ）。A. 任意個字母的序列B. 不少于一個字符的序列C. 有限個字符的序列D. 不少于一個字母的序列4.串的長度是指（ ）。A. 串中所含字符的個數B. 串中所含不同字母的個數C. 串中所含不同字符的個數D. 串中所含非空格字符的個數5.在C語言中，存儲字符串“ABCD”需占用（ ）字節。A. 2B. 3C. 4D. 56.下面關于串的敘述中，不正確的是（ ）。A. 空串是由空格構成的串B. 串即可以采用順序存儲，也可以采用鏈式存儲C. 串是字符的有限序列D. 模式匹配是串的一種重要運算7.串與普通的線性表相比較，它的特殊性體現在（ ）。A. 順序的存儲結構B. 數據元

23、素是一個字符C. 鏈接的存儲結構D. 數據元素可以任意8.空串與空格串（ ）。A. 可能相同B. 相同C. 無法確定D. 不相同9.兩個字符串相等的條件是（ ）。A. 兩串包含的字符相同B. 兩串的長度相等，并且兩串包含的字符相同C. 兩串的長度相等，并且對應位置上的字符相同D. 兩串的長度相等10.在實際應用中，要輸入多個字符串，且長度無法預定。則應該采用（ ）存儲比較合適（ ）。A. 順序B. 堆結構C. 無法確定D. 鏈式11.下列關于串的敘述中，不正確的是（ ）。A. 空串是由空格構成的串B. 串既可以采用順序存儲，也可以采用鏈式存儲C. 串是字符的有限序列D. 模式匹配是串的一種重要

24、運算12.串是一種特殊的線性表，其特殊性體現在（ ）。A. 可以順序存儲B. 數據元素是一個字符C. 數據元素可以是多個字符D. 可以鏈接存儲13.串函數StrCmp(“abA”,”aba”)的值為（ ）。A. “abAaba”B. -1C. 1D. 014.在C語言中，存儲字符串“ABCD”需要占用（ ）字節。A. 2B. 3C. 4D. 515.設主串為“ABcCDABcdEFaBc”，以下模式串能與主串成功匹配的是（ ）。A. AbcB. BCdC. ABCD. Bcd16.字符串 a1=“AEIJING”，a2=“AEI”，a3=“AEFANG”，a4=“AEFI”中最大的是（ ）。A

25、. a4B. a3C. a2D. a117.字符串abcd321ABCD的子串是（ ）。A. 321aB. abcDC. abcABCDD. 21ABC18.數組a經初始化char a =“English”；a1中存放的是（ ）。 A. EB. 字符EC. 字符nD. n19.空串的長度為（ ）。A. 1B. 2C. 0D. 3 單元5 數組和廣義表1.一維數組A采用順序存儲結構，每個元素占用4個字節，第8個元素的存儲地址為120，則該數組的首地址是（ ）。A. 90B. 32C. 92D. 882.稀疏矩陣采用壓縮存儲的目的主要是（ ）。A. 減少不必要的存儲空間的開銷B. 對矩陣元素的存取

26、變得簡單C. 去掉矩陣中的多余元素D. 表達變得簡單3.一個非空廣義表的表頭（ ）。A. 只能是原子B. 不可能是原子C. 只能是子表D. 可以是子表或原子4.常對數組進行的兩種基本操作是（ ）。A. 索引與、和修改B. 建立與刪除C. 查找和修改D. 查找與索引5.在二維數組A810中，每一個數組元素Aij 占用3個存儲空間，所有數組元素相繼存放于一個連續的存儲空間中，則存放該數組至少需要的存儲空間是（ ）。A. 80B. 100C. 270D. 2406.設有一個18階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數組B中（數組下標從1開始），則矩陣中元素A10,8

27、在一維數組B中的下標是（ ）。A. 58B. 53C. 18D. 457.廣義表(a)的表尾是（ ）。A. aB. (a)C. (a)D. 08.設有一個10階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數組B中（數組下標從1開始），則矩陣中元素A8,5在一維數組B中的下標是（ ）。A. 85B. 41C. 32D. 339.設廣義表類（(a,b,c)），則L的長度和深度分別為（ ）。A. 1和2B. 1和3C. 2和3D. 1和110.廣義表( a , a ,b , d , e ,( (i ,j ) ,k ) )的表頭是_。A. ( a )B. aC. (a ,b)

28、D. a,(a,b)11.廣義表的（a，d，e，（i，j），k）表尾是_。A. kB. （k）C. （d，e，（i，j），k ）D. （i，j），k）12.稀疏矩陣的壓縮存儲方式通常有兩種，即（ ）。A. 三元組和十字鏈表B. 二元組和三元組C. 散列和十字鏈表D. 三元組和散列13.設有一個對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數組B中（數組下標從1開始），B數組共有55個元素，則矩陣是（ ）階的對稱矩陣。A. 5B. 20C. 15D. 1014.設有一個18階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數組B中（數組下標從1開始），

29、則數組中第53號元素對應于矩陣中的元素是（ ）。A. a8,1B. a8,5C. a10,8D. a7,615.對稀疏矩陣進行壓縮存儲,可采用三元組表，一個10 行8列的稀疏矩陣A共有73個零元素，其相應的三元組表共有( )個元素。A. 7B. 10C. 80D. 816.廣義表(a)的表尾是（ ）。A. ( )B. (a)C. aD. (a)17.廣義表(a,(a,b),d,e,(i,j),k)的長度和深度分別是（ ）。A. 5，5B. 6，6C. 5，3D. 6，4單元6 樹和二叉樹1.假定一棵二叉樹中，雙分支結點數為15，單分支結點數為30，則葉子結點數為（ ）。A. 17B. 15C.

30、 47D. 162.已知某二叉樹的后續遍歷序列是dabec，中序遍歷是debac，則它的先序遍歷序列是（ ）。A. acbedB. cedbaC. deabcD. decab3.二叉樹第k層上最多有（ ）個結點。A. 2k-1B. 2k-1C. 2k-1D. 2k4.二叉樹的深度為k，則二叉樹最多有（ ）個結點。A. 2k-1B. 2k-1C. 2kD. 2k-15.設某一二叉樹先序遍歷為abdec，中序遍歷為dbeac，則該二叉樹后序遍歷的順序是（ ）。A. abdecB. debacC. abedcD. debca6.設某一二叉樹中序遍歷為badce，后序遍歷為bdeca，則該二叉樹先序遍

31、歷的順序是（ ）。A. decabB. abcdeC. adbecD. debac7.樹最適合于用來表示（ ）。A. 順序結構的數據B. 元素之間無前驅和后繼關系的數據C. 線性結構的數據D. 元素之間有包含和層次關系的數據8.一棵非空的二叉樹，先序遍歷與后續遍歷正好相反，則該二叉樹滿足（ ）。A. 無右孩子B. 無左孩子C. 任意二叉樹D. 只有一個葉子結點9.設a，b為一棵二叉樹的兩個結點，在后續遍歷中，a在b前的條件是（ ）。A. a在b上方B. a在b右方C. a在b下方D. a在b左方10.權值為1，2，6，8的四個結點構成的哈夫曼樹的帶權路徑長度是（ ）。A. 28B. 19C.

32、18D. 2911.如果將給定的一組數據作為葉子數值，所構造出的二叉樹的帶權路徑長度最小，則該樹稱為（ ）。A. 二叉樹B. 平衡二叉樹C. 完全二叉樹D. 哈夫曼樹12.下列有關二叉樹的說法正確的是（ ）。A. 完全二叉樹中，任何一個結點的度，或者為0或者為2B. 二叉樹中結點個數必大于0C. 二叉樹中度為0的結點的個數等于度為2的結點的個數加1D. 二叉樹的度是213.二叉樹是非線性數據結構，所以（ ）。A. 順序存儲結構和鏈式存儲結構都能存儲B. 它不能用鏈式存儲結構存儲C. 它不能用順序存儲結構存儲D. 順序存儲結構和鏈式存儲結構都不能使用14.任何一棵二叉樹的葉結點在先序、中序和后序

33、遍歷序列中的相對次序（ ）。A. 發生改變B. 不能確定C. 不發生改變D. 以上都不對15.一棵有n個結點采用鏈式存儲的二叉樹中，共有（ ）個指針域為空。A. nB. n+1C. n-2D. n-116.設一棵哈夫曼樹共有n個非葉結點，則該樹有（ ）個葉結點。A. n-1B. n+1C. nD. 2n17.一棵完全二叉樹共有5層，且第5層上有六個結點，該樹共有（ ）個結點。A. 23B. 30C. 21D. 2018.在一棵二叉樹中，若編號為i的結點是其雙親結點的右孩子，則雙親結點的順序編號為（ ）。A. i/2向下取整B. 2i+1C. i/2.0D. i/2+119.一棵采用鏈式存儲的二

34、叉樹中有n個指針域為空,該二叉樹共有（ ）個結點。A. n-1B. n+1C. n-2D. n20.一棵 結點數31<n<40的完全二叉樹，最后一層有4個結點，則該樹有（ ）個葉結點。A. 35B. 36C. 18D. 1721.設一棵哈夫曼樹共有2n+1個結點，則該樹有（ ）個非葉結點。A. n-1B. 2nC. nD. n+122.在一棵具有35個結點的完全二叉樹中，該樹的深度為( )。A. 6B. 7C. 8D. 523.在一棵二叉樹中，若編號為i的結點存在左孩子，則左孩子結點的順序編號為( )。A. 2i+1B. 2i+2C. 2iD. 2i-124.在一棵具有n個結點的二

35、叉樹的第i層上，最多具有( )個結點。A. 2nB. 2i+1C. 2iD. 2i-125.以二叉鏈表作為二叉樹的存儲結構，在有n個結點的二叉鏈表中（n>0），鏈表中空鏈域的個數為（ ）。A. n+1B. n-1C. 2n+1D. 2n-126.將含有150個結點的完全二叉樹從根這一層開始，每一層從左到右依次對結點進行編號，根結點的編號為1，則編號為69的結點的雙親結點的編號為（ ）。A. 35B. 34C. 36D. 3327.有n個葉子結點的哈夫曼樹的結點總數為（ ）。A. 2n+1B. 2n-1C. 2nD. 不確定28.下面關于二叉樹的結論正確的是（ ）。A. 二叉樹中，度為0的

36、結點個數等于度為2的結點個數加1B. 二叉樹的度是2C. 二叉樹中結點的個數必大于0D. 完全二叉樹中，任何一個結點的度，或者為0，或者為2單元7 圖1.在一個圖G中，所有頂點的度數之和等于所有邊數之和的（ ）倍。A. 1/2B. 4C. 2D. 12.鄰接表是圖的一種（ ）。A. 索引存儲結構B. 散列存儲結構C. 順序存儲結構D. 鏈式存儲結構3.如果從無向圖的任一頂點出發進行一次深度優先搜索即可訪問所有頂點，則該圖一定是（ ）。A. 完全圖B. 連通圖C. 一棵樹D. 有回路4.下列有關圖遍歷的說法不正確的是（ ）。A. 連通圖的深度優先搜索是一個遞歸過程B. 圖的遍歷要求每一頂點僅被訪

37、問一次C. 圖的廣度優先搜索中鄰接點的尋找具有“先進先出”的特征D. 非連通圖不能用深度優先搜索法5.無向圖的鄰接矩陣是一個（ ）。A. 對稱矩陣B. 上三角矩陣C. 對角矩陣D. 零矩陣6.圖的深度優先遍歷算法類似于二叉樹的（ ）遍歷。A. 中序B. 先序C. 后序D. 層次7.已知下圖所示的一個圖，若從頂點V1出發，按深度優先搜索法進行遍歷，則可能得到的一種頂點序列為（ ）。A. V1V2V4V8V3V5V6V7B. V1V2V4V5V8V3V6V7C. V1V2V4V8V5V3V6V7D. V1V3V6V7V2V4V5V88.已知如圖2所示的一個圖，若從頂點a出發，按廣度優先搜索法進行遍

38、歷，則可能得到的一種頂點序列為（ ）。A. aebcfdB. abcedfC. abcefdD. acfdeb9.已知如圖3所示的一個圖，若從頂點a出發，按深度優先搜索法進行遍歷，則可能得到的一種頂點序列為（ ）。A. aedfcbB. acfebdC. aebcfdD. abecdf10.一個具有n個頂點的無向完全圖包含（ ）條邊。A. n（n-1）/2B. n（n+1）C. n（n-1）D. n（n+1）/211.已知如圖4所示的一個圖，若從頂點a出發，按深度優先搜索法進行遍歷，則可能得到的一種頂點序列為（ ）。A. aebcfdB. abecdfC. aedfcbD. acfebd12.

39、已知如圖5所示的一個圖，若從頂點a出發，按廣度優先搜索法進行遍歷，則可能得到的一種頂點序列為（ ）。A. abcedfB. aebcfdC. abcefdD. acfdeb13.已知如圖6所示的一個圖，若從頂點V1出發，按深度優先搜索法進行遍歷，則可能得到的一種頂點序列為（ ）。A. V1V2V4V8V5V3V6V7B. V1V2V4V5V8V3V6V7C. V1V2V4V8V3V5V6V7D. V1V3V6V7V2V4V5V814.已知如圖7所示的一個圖，若從頂點V1出發，按深廣優先搜索法進行遍歷，則可能得到的一種頂點序列為（ ）。A. V1V2V3V4V5V6V7V8B. V1V2V3V6

40、V7V4V5V8C. V1V2V3V4V8V5V6V7D. V1V2V3V4V5V8V6V715.采用鄰接表存儲的圖的廣度優先搜索遍歷算法類似于二叉樹的（ ）。A. 后續遍歷B. 中序遍歷C. 層次遍歷D. 先序遍歷16.下面結論中不正確的是（ ）。A. 按廣度優先搜索遍歷時，與始點相鄰的結點先于不與始點相鄰的結點訪問B. 圖的多重鄰接表表示法中，表中結點的數目等于圖中邊的條數C. 一個圖按廣度優先搜索法遍歷的結果是唯一的D. 無向圖的鄰接表表示法中，表中結點的數目是圖中邊的條數的2倍17.下面說法不正確的是（ ）。A. 圖的遍歷是從給定的原點出發每一個頂點僅被訪問一次B. 圖的深度遍歷不適用

41、于有向圖C. 遍歷的基本算法有兩種：深度遍歷和廣度遍歷D. 圖的深度遍歷是一個遞歸過程18.任何一棵無向連通圖的最小生成樹（ ）。A. 可能不存在B. 只有一棵C. 一定有多棵D. 有一棵或多棵19.在一個具有n個頂點的無向圖中，要連通全部頂點至少需要（ ）邊。A. n-1B. nC. n/2D. n+120.采用鄰接表存儲的圖的深度優先搜索遍歷算法類似于二叉樹的（ ）。A. 層次遍歷B. 后續遍歷C. 中序遍歷D. 先序遍歷單元8 查找1.線性表只有以（ ）方式存儲，才能進行折半查找。A. 鏈接B. 順序C. 二叉樹D. 關鍵字有序的2.有序表為2，4，10，13，33，42，46，64，7

42、6，79，85，95，120，用折半查找值為85的結點時，經（ ）次比較后成功查到。A. 1B. 8C. 4D. 23.采用順序查找法對長度為n（n為偶數）的線性表進行查找，采用從前向后的方向查找。在等概率條件下成功查找到前n/2個元素的平均查找長度為（ ）。A. (n+1)/2B. n/2C. (n+2)/4D. (2n+1)/44.對二叉排序樹進行（ ）遍歷，可以使遍歷所得到的序列是有序序列。A. 按層次B. 中序C. 前序D. 后序5.以下說法正確的是（ ）。A. 二叉樹的根結點值大于其左子樹結點的值，小于右子樹結點的值，則它是一棵二叉排序樹。B. 二叉樹中任一結點的值均大于其左孩子的值

43、，小于其右孩子的值。則它是一棵二叉排序樹。C. 二叉排序樹中某一結點的左兒子一定小于樹中任一個結點的右兒子。D. 二叉排序樹中任一棵子樹都是二叉排序樹。6.對線性表進行二分查找時，要求線性表必需（ ）。A. 以順序方式存儲B. 以鏈接方式存儲C. 以鏈接方式存儲，且結點按關鍵字有序排列D. 以順序方式存儲，且結點按關鍵字有序排列7.使用折半查找法時，要求查找表中各元素的鍵值必須是（ ）排列的。A. 遞減B. 無序C. 遞增或遞減D. 遞增8.已知一個有序表為11,22,33,44,55,66,77,88,99，則順序查找元素55需要比較（ ）次。A. 5B. 3C. 4D. 69.有一個長度為

44、10的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數為（ ）。A. 31/10B. 29/9C. 26/10D. 29/1010.采用分塊查找時，若線性表中共有324個元素，查找每個元素的概率相同，假設采用順序查找來確定結點所在的塊，每塊應分（ ）個結點最佳。A. 6B. 324C. 18D. 1011.如果要求一個線性表既能較快地查找，又能動態適應變化要求，可以采用（ ）查找方法。A. 折半B. 分塊C. 順序D. 散列12.關于哈希查找的說法正確的是（ ）。A. 刪除一個元素后，不管用哪種方法處理沖突，都只需簡單地把該元素刪除掉B. 因為沖突是不可避免的，所以裝填因

45、子越小越好C. 除留余數法是最好的D. 哈希函數的好壞要根據具體情況而定13.采用順序查找方法查找長度為n的線性表時，每個元素的平均查找長度為（ ）。A. n/2B. (n+1)/2C. (n-1)/2D. n14.采用分塊查找時，數據的組織方式為（ ）。A. 把數據分城若干塊，每塊內數據有序，每塊內最大（或最小）的數據組成索引表B. 把數據分城若干塊，每塊內數據有序C. 把數據分城若干塊，塊內數據不必有序，但塊間必需有序，每塊內最大（或最小）的數據組成索引表D. 把數據分城若干塊，每塊（除最后一塊外）中的數據個數相等15.假設在有序線性表A1.20上進行折半查找，則比較五次查找成功的結點數為

46、（ ）。A. 8B. 4C. 5D. 6單元9 排序1.設有1000個無序的元素，希望用最快的速度挑選出其中前10個最大的元素，最好選用（）排序法。A. 冒泡排序B. 基數排序C. 快速排序D. 堆排序2.對數據元素序列（49，72，68，13，38，50，97，27）進行排序，前三趟排序結果時的結果依次為第一趟：49，72，68，13，38，50，97，27；第二趟：49，68，72，13，38，50，97，27；第三趟：13，49，68，72，38，50，97，27。該排序采用的方法是（ ）。A. 選擇排序法B. 插入排序法C. 堆排序法D. 冒泡排序法3.一組記錄的關鍵字序列為（47，8

47、0，57，39，41，46），利用堆排序（堆頂元素是最小元素）的方法建立的初始化堆為（ ）。A. 39，41，46，80，47，57B. 39，47，46，80，41，57C. 41，39，46，47，57，80D. 39，80，46，47，41，574.一組記錄的關鍵字序列為（37，70，47，29，31，85），利用快速排序，以第一個關鍵字為分割元素，經過一次劃分后結果為（ ）。A. 31，29，37，47，77，85B. 31，29，37，85，47，70C. 29，31，37，47，70，85D. 31，29，37，70，47，855.下述幾種排序方法中，要求內存量最大的是（ ）。A. 插入排序B. 選擇