數(shù)據(jù)結(jié)構(gòu)課后答案

1、-作者xxxx-日期xxxx數(shù)據(jù)結(jié)構(gòu)課后答案【精品文檔】第1章 緒論1簡(jiǎn)述下列概念：數(shù)據(jù)、數(shù)據(jù)元素、數(shù)據(jù)項(xiàng)、數(shù)據(jù)對(duì)象、數(shù)據(jù)結(jié)構(gòu)、邏輯結(jié)構(gòu)、存儲(chǔ)結(jié)構(gòu)、抽象數(shù)據(jù)類(lèi)型。答案：數(shù)據(jù)：是客觀事物的符號(hào)表示，指所有能輸入到計(jì)算機(jī)中并被計(jì)算機(jī)程序處理的符號(hào)的總稱(chēng)。如數(shù)學(xué)計(jì)算中用到的整數(shù)和實(shí)數(shù)，文本編輯所用到的字符串，多媒體程序處理的圖形、圖像、聲音、動(dòng)畫(huà)等通過(guò)特殊編碼定義后的數(shù)據(jù)。數(shù)據(jù)元素：是數(shù)據(jù)的基本單位，在計(jì)算機(jī)中通常作為一個(gè)整體進(jìn)行考慮和處理。在有些情況下，數(shù)據(jù)元素也稱(chēng)為元素、結(jié)點(diǎn)、記錄等。數(shù)據(jù)元素用于完整地描述一個(gè)對(duì)象，如一個(gè)學(xué)生記錄，樹(shù)中棋盤(pán)的一個(gè)格局（狀態(tài)）、圖中的一個(gè)頂點(diǎn)等。數(shù)據(jù)項(xiàng)：是組成數(shù)據(jù)

2、元素的、有獨(dú)立含義的、不可分割的最小單位。例如，學(xué)生基本信息表中的學(xué)號(hào)、姓名、性別等都是數(shù)據(jù)項(xiàng)。數(shù)據(jù)對(duì)象：是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個(gè)子集。例如：整數(shù)數(shù)據(jù)對(duì)象是集合N=0，1，2，字母字符數(shù)據(jù)對(duì)象是集合C=A，B，Z， a，b，z，學(xué)生基本信息表也可是一個(gè)數(shù)據(jù)對(duì)象。數(shù)據(jù)結(jié)構(gòu)：是相互之間存在一種或多種特定關(guān)系的數(shù)據(jù)元素的集合。換句話說(shuō)，數(shù)據(jù)結(jié)構(gòu)是帶“結(jié)構(gòu)”的數(shù)據(jù)元素的集合，“結(jié)構(gòu)”就是指數(shù)據(jù)元素之間存在的關(guān)系。邏輯結(jié)構(gòu)：從邏輯關(guān)系上描述數(shù)據(jù)，它與數(shù)據(jù)的存儲(chǔ)無(wú)關(guān)，是獨(dú)立于計(jì)算機(jī)的。因此，數(shù)據(jù)的邏輯結(jié)構(gòu)可以看作是從具體問(wèn)題抽象出來(lái)的數(shù)學(xué)模型。存儲(chǔ)結(jié)構(gòu)：數(shù)據(jù)對(duì)象在計(jì)算機(jī)中的存儲(chǔ)表示，也稱(chēng)為

3、物理結(jié)構(gòu)。抽象數(shù)據(jù)類(lèi)型：由用戶定義的，表示應(yīng)用問(wèn)題的數(shù)學(xué)模型，以及定義在這個(gè)模型上的一組操作的總稱(chēng)。具體包括三部分：數(shù)據(jù)對(duì)象、數(shù)據(jù)對(duì)象上關(guān)系的集合和對(duì)數(shù)據(jù)對(duì)象的基本操作的集合。2試舉一個(gè)數(shù)據(jù)結(jié)構(gòu)的例子，敘述其邏輯結(jié)構(gòu)和存儲(chǔ)結(jié)構(gòu)兩方面的含義和相互關(guān)系。答案：例如有一張學(xué)生基本信息表，包括學(xué)生的學(xué)號(hào)、姓名、性別、籍貫、專(zhuān)業(yè)等。每個(gè)學(xué)生基本信息記錄對(duì)應(yīng)一個(gè)數(shù)據(jù)元素，學(xué)生記錄按順序號(hào)排列，形成了學(xué)生基本信息記錄的線性序列。對(duì)于整個(gè)表來(lái)說(shuō)，只有一個(gè)開(kāi)始結(jié)點(diǎn)(它的前面無(wú)記錄)和一個(gè)終端結(jié)點(diǎn)(它的后面無(wú)記錄)，其他的結(jié)點(diǎn)則各有一個(gè)也只有一個(gè)直接前趨和直接后繼。學(xué)生記錄之間的這種關(guān)系就確定了學(xué)生表的邏輯結(jié)構(gòu)，

4、即線性結(jié)構(gòu)。這些學(xué)生記錄在計(jì)算機(jī)中的存儲(chǔ)表示就是存儲(chǔ)結(jié)構(gòu)。如果用連續(xù)的存儲(chǔ)單元(如用數(shù)組表示)來(lái)存放這些記錄，則稱(chēng)為順序存儲(chǔ)結(jié)構(gòu)；如果存儲(chǔ)單元不連續(xù)，而是隨機(jī)存放各個(gè)記錄，然后用指針進(jìn)行鏈接，則稱(chēng)為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。即相同的邏輯結(jié)構(gòu)，可以對(duì)應(yīng)不同的存儲(chǔ)結(jié)構(gòu)。3簡(jiǎn)述邏輯結(jié)構(gòu)的四種基本關(guān)系并畫(huà)出它們的關(guān)系圖。答案：（1）集合結(jié)構(gòu)數(shù)據(jù)元素之間除了“屬于同一集合”的關(guān)系外，別無(wú)其他關(guān)系。例如，確定一名學(xué)生是否為班級(jí)成員，只需將班級(jí)看做一個(gè)集合結(jié)構(gòu)。（2）線性結(jié)構(gòu)數(shù)據(jù)元素之間存在一對(duì)一的關(guān)系。例如，將學(xué)生信息數(shù)據(jù)按照其入學(xué)報(bào)到的時(shí)間先后順序進(jìn)行排列，將組成一個(gè)線性結(jié)構(gòu)。（3）樹(shù)結(jié)構(gòu)數(shù)據(jù)元素之間存在一對(duì)多的關(guān)

5、系。例如，在班級(jí)的管理體系中，班長(zhǎng)管理多個(gè)組長(zhǎng)，每位組長(zhǎng)管理多名組員，從而構(gòu)成樹(shù)形結(jié)構(gòu)。（4）圖結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)數(shù)據(jù)元素之間存在多對(duì)多的關(guān)系。例如，多位同學(xué)之間的朋友關(guān)系，任何兩位同學(xué)都可以是朋友，從而構(gòu)成圖形結(jié)構(gòu)或網(wǎng)狀結(jié)構(gòu)。其中樹(shù)結(jié)構(gòu)和圖結(jié)構(gòu)都屬于非線性結(jié)構(gòu)。 四類(lèi)基本邏輯結(jié)構(gòu)關(guān)系圖4存儲(chǔ)結(jié)構(gòu)由哪兩種基本的存儲(chǔ)方法實(shí)現(xiàn)？答案：（1）順序存儲(chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)是借助元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系，通常借助程序設(shè)計(jì)語(yǔ)言的數(shù)組類(lèi)型來(lái)描述。（2）鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)順序存儲(chǔ)結(jié)構(gòu)要求所有的元素依次存放在一片連續(xù)的存儲(chǔ)空間中，而鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)，無(wú)需占用一整塊存儲(chǔ)空間。但為了表示結(jié)點(diǎn)之間的關(guān)系，需

6、要給每個(gè)結(jié)點(diǎn)附加指針字段，用于存放后繼元素的存儲(chǔ)地址。所以鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)通常借助于程序設(shè)計(jì)語(yǔ)言的指針類(lèi)型來(lái)描述。5選擇題（1）在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成（ ）。A動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C線性結(jié)構(gòu)和非線性結(jié)構(gòu) D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)答案：C（2）與數(shù)據(jù)元素本身的形式、內(nèi)容、相對(duì)位置、個(gè)數(shù)無(wú)關(guān)的是數(shù)據(jù)的（ ）。A存儲(chǔ)結(jié)構(gòu) B存儲(chǔ)實(shí)現(xiàn)C邏輯結(jié)構(gòu) D運(yùn)算實(shí)現(xiàn)答案：C（3）通常要求同一邏輯結(jié)構(gòu)中的所有數(shù)據(jù)元素具有相同的特性，這意味著（ ）。 A數(shù)據(jù)具有同一特點(diǎn)B不僅數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)數(shù)要相同，而且對(duì)應(yīng)數(shù)據(jù)項(xiàng)的類(lèi)型要一致C每個(gè)數(shù)據(jù)元素都一樣D數(shù)據(jù)元素所包含的數(shù)據(jù)項(xiàng)的個(gè)

7、數(shù)要相等答案：B（4）以下說(shuō)法正確的是（ ）。A數(shù)據(jù)元素是數(shù)據(jù)的最小單位B數(shù)據(jù)項(xiàng)是數(shù)據(jù)的基本單位C數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)項(xiàng)的集合D一些表面上很不相同的數(shù)據(jù)可以有相同的邏輯結(jié)構(gòu)答案：D解釋?zhuān)簲?shù)據(jù)元素是數(shù)據(jù)的基本單位，數(shù)據(jù)項(xiàng)是數(shù)據(jù)的最小單位，數(shù)據(jù)結(jié)構(gòu)是帶有結(jié)構(gòu)的各數(shù)據(jù)元素的集合。（5）算法的時(shí)間復(fù)雜度取決于（ ）。A問(wèn)題的規(guī)模B待處理數(shù)據(jù)的初態(tài)C計(jì)算機(jī)的配置DA和B答案：D解釋?zhuān)核惴ǖ臅r(shí)間復(fù)雜度不僅與問(wèn)題的規(guī)模有關(guān)，還與問(wèn)題的其他因素有關(guān)。如某些排序的算法，其執(zhí)行時(shí)間與待排序記錄的初始狀態(tài)有關(guān)。為此，有時(shí)會(huì)對(duì)算法有最好、最壞以及平均時(shí)間復(fù)雜度的評(píng)價(jià)。（6）以下數(shù)據(jù)結(jié)構(gòu)中，（ ）是非線性數(shù)據(jù)結(jié)構(gòu)

8、A樹(shù) B字符串 C隊(duì)列 D棧答案：A6試分析下面各程序段的時(shí)間復(fù)雜度。（1）x=90; y=100;while(y0)if(x100) x=x-10;y-;else x+;答案：O(1)解釋?zhuān)撼绦虻膱?zhí)行次數(shù)為常數(shù)階。（2）for (i=0; in; i+)for (j=0; jm; j+)aij=0;答案：O(m*n)解釋?zhuān)赫Z(yǔ)句aij=0;的執(zhí)行次數(shù)為m*n。（3）s=0; for i=0; in; i+)for(j=0; jn; j+) s+=Bij;sum=s;答案：O(n2)解釋?zhuān)赫Z(yǔ)句s+=Bij;的執(zhí)行次數(shù)為n2。（4）i=1; while(i=n) i=i*3;答案：O(log3n)

9、 解釋?zhuān)赫Z(yǔ)句i=i*3;的執(zhí)行次數(shù)為log3n。（5）x=0;for(i=1; in; i+) for (j=1; j1y=0;while(x(y+1)* (y+1) y+;答案：O()解釋?zhuān)赫Z(yǔ)句y+;的執(zhí)行次數(shù)為。第2章 線性表1選擇題（1）順序表中第一個(gè)元素的存儲(chǔ)地址是100，每個(gè)元素的長(zhǎng)度為2，則第5個(gè)元素的地址是（ ）。A110 B108 C100 D120答案：B解釋?zhuān)喉樞虮碇械臄?shù)據(jù)連續(xù)存儲(chǔ)，所以第5個(gè)元素的地址為：100+2*4=108。（2）在n個(gè)結(jié)點(diǎn)的順序表中，算法的時(shí)間復(fù)雜度是O(1)的操作是（ ）。A訪問(wèn)第i個(gè)結(jié)點(diǎn)（1in）和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)（2in） B在第i個(gè)結(jié)點(diǎn)

10、后插入一個(gè)新結(jié)點(diǎn)（1in）C刪除第i個(gè)結(jié)點(diǎn)（1in）D將n個(gè)結(jié)點(diǎn)從小到大排序答案：A解釋?zhuān)涸陧樞虮碇胁迦胍粋€(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度都是O(n2)，排序的時(shí)間復(fù)雜度為O(n2)或O(nlog2n)。順序表是一種隨機(jī)存取結(jié)構(gòu)，訪問(wèn)第i個(gè)結(jié)點(diǎn)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)都可以直接通過(guò)數(shù)組的下標(biāo)直接定位，時(shí)間復(fù)雜度是O(1)。（3） 向一個(gè)有127個(gè)元素的順序表中插入一個(gè)新元素并保持原來(lái)順序不變，平均要移動(dòng) 的元素個(gè)數(shù)為（ ）。A8 B63.5 C63 D7答案：B解釋?zhuān)浩骄苿?dòng)的元素個(gè)數(shù)為：n/2。（4）鏈接存儲(chǔ)的存儲(chǔ)結(jié)構(gòu)所占存儲(chǔ)空間（ ）。A分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放表示結(jié)點(diǎn)間關(guān)系的指針B只

11、有一部分，存放結(jié)點(diǎn)值C只有一部分，存儲(chǔ)表示結(jié)點(diǎn)間關(guān)系的指針D分兩部分，一部分存放結(jié)點(diǎn)值，另一部分存放結(jié)點(diǎn)所占單元數(shù)答案：A（5）線性表若采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)時(shí)，要求內(nèi)存中可用存儲(chǔ)單元的地址（ ）。A必須是連續(xù)的 B部分地址必須是連續(xù)的C一定是不連續(xù)的 D連續(xù)或不連續(xù)都可以答案：D（6）線性表在（ ）情況下適用于使用鏈?zhǔn)浇Y(jié)構(gòu)實(shí)現(xiàn)。A需經(jīng)常修改中的結(jié)點(diǎn)值 需不斷對(duì)進(jìn)行刪除插入 C中含有大量的結(jié)點(diǎn) 中結(jié)點(diǎn)結(jié)構(gòu)復(fù)雜答案：B解釋?zhuān)烘湵碜畲蟮膬?yōu)點(diǎn)在于插入和刪除時(shí)不需要移動(dòng)數(shù)據(jù)，直接修改指針即可。（7）單鏈表的存儲(chǔ)密度（ ）。A大于1 B等于1 C小于1 D不能確定答案：C解釋?zhuān)捍鎯?chǔ)密度是指一個(gè)結(jié)點(diǎn)數(shù)據(jù)本身所占

12、的存儲(chǔ)空間和整個(gè)結(jié)點(diǎn)所占的存儲(chǔ)空間之比，假設(shè)單鏈表一個(gè)結(jié)點(diǎn)本身所占的空間為D，指針域所占的空間為N，則存儲(chǔ)密度為：D/(D+N)，一定小于1。（8）將兩個(gè)各有n個(gè)元素的有序表歸并成一個(gè)有序表，其最少的比較次數(shù)是（ ）。An B2n-1 C2n Dn-1答案：A解釋?zhuān)寒?dāng)?shù)谝粋€(gè)有序表中所有的元素都小于（或大于）第二個(gè)表中的元素，只需要用第二個(gè)表中的第一個(gè)元素依次與第一個(gè)表的元素比較，總計(jì)比較n次。（9）在一個(gè)長(zhǎng)度為n的順序表中，在第i個(gè)元素（1in+1）之前插入一個(gè)新元素時(shí)須向后移動(dòng)（ ）個(gè)元素。An-i Bn-i+1 Cn-i-1 DI答案：B(10) 線性表L=(a1，a2,an)，下列說(shuō)法正

13、確的是（ ）。A每個(gè)元素都有一個(gè)直接前驅(qū)和一個(gè)直接后繼B線性表中至少有一個(gè)元素C表中諸元素的排列必須是由小到大或由大到小D除第一個(gè)和最后一個(gè)元素外，其余每個(gè)元素都有一個(gè)且僅有一個(gè)直接前驅(qū)和直接后繼。答案：D(11) 創(chuàng)建一個(gè)包括n個(gè)結(jié)點(diǎn)的有序單鏈表的時(shí)間復(fù)雜度是（ ）。AO(1) BO(n) CO(n2) DO(nlog2n)答案：C解釋?zhuān)簡(jiǎn)捂湵韯?chuàng)建的時(shí)間復(fù)雜度是O(n)，而要建立一個(gè)有序的單鏈表，則每生成一個(gè)新結(jié)點(diǎn)時(shí)需要和已有的結(jié)點(diǎn)進(jìn)行比較，確定合適的插入位置，所以時(shí)間復(fù)雜度是O(n2)。(12) 以下說(shuō)法錯(cuò)誤的是（ ）。A求表長(zhǎng)、定位這兩種運(yùn)算在采用順序存儲(chǔ)結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率不比采用鏈?zhǔn)酱鎯?chǔ)

14、結(jié)構(gòu)時(shí)實(shí)現(xiàn)的效率低B順序存儲(chǔ)的線性表可以隨機(jī)存取C由于順序存儲(chǔ)要求連續(xù)的存儲(chǔ)區(qū)域，所以在存儲(chǔ)管理上不夠靈活D線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)結(jié)構(gòu)答案：D解釋?zhuān)烘準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)和順序存儲(chǔ)結(jié)構(gòu)各有優(yōu)缺點(diǎn)，有不同的適用場(chǎng)合。(13) 在單鏈表中，要將s所指結(jié)點(diǎn)插入到p所指結(jié)點(diǎn)之后，其語(yǔ)句應(yīng)為（ ）。As-next=p+1; p-next=s;B(*p).next=s; (*s).next=(*p).next;Cs-next=p-next; p-next=s-next;Ds-next=p-next; p-next=s; 答案：D (14) 在雙向鏈表存儲(chǔ)結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)須修改指針（ ）。Ap-n

15、ext-prior=p-prior; p-prior-next=p-next;Bp-next=p-next-next; p-next-prior=p;Cp-prior-next=p; p-prior=p-prior-prior;Dp-prior=p-next-next; p-next=p-prior-prior;答案：A(15) 在雙向循環(huán)鏈表中，在p指針?biāo)傅慕Y(jié)點(diǎn)后插入q所指向的新結(jié)點(diǎn)，其修改指針的操作是（ ）。Ap-next=q; q-prior=p; p-next-prior=q; q-next=q;Bp-next=q; p-next-prior=q; q-prior=p; q-next

16、=p-next;Cq-prior=p; q-next=p-next; p-next-prior=q; p-next=q;Dq-prior=p; q-next=p-next; p-next=q; p-next-prior=q;答案：C第3章 棧和隊(duì)列1選擇題（1）若讓元素1，2，3，4，5依次進(jìn)棧，則出棧次序不可能出現(xiàn)在（ ）種情況。A5，4，3，2，1 B2，1，5，4，3 C4，3，1，2，5 D2，3，5，4，1答案：C解釋?zhuān)簵Ｊ呛筮M(jìn)先出的線性表，不難發(fā)現(xiàn)C選項(xiàng)中元素1比元素2先出棧，違背了棧的后進(jìn)先出原則，所以不可能出現(xiàn)C選項(xiàng)所示的情況。（2）若已知一個(gè)棧的入棧序列是1，2，3，n，其輸

17、出序列為p1，p2，p3，pn，若p1=n，則pi為（ ）。Ai Bn-i Cn-i+1 D不確定答案：C解釋?zhuān)簵Ｊ呛筮M(jìn)先出的線性表，一個(gè)棧的入棧序列是1，2，3，n，而輸出序列的第一個(gè)元素為n，說(shuō)明1，2，3，n一次性全部進(jìn)棧，再進(jìn)行輸出，所以p1=n，p2=n-1，pi=n-i+1。（3）數(shù)組用來(lái)表示一個(gè)循環(huán)隊(duì)列，為當(dāng)前隊(duì)列頭元素的前一位置，為隊(duì)尾元素的位置，假定隊(duì)列中元素的個(gè)數(shù)小于，計(jì)算隊(duì)列中元素個(gè)數(shù)的公式為（ ）。Ar-f B(n+f-r)%n Cn+r-f D（n+r-f)%n答案：D解釋?zhuān)簩?duì)于非循環(huán)隊(duì)列，尾指針和頭指針的差值便是隊(duì)列的長(zhǎng)度，而對(duì)于循環(huán)隊(duì)列，差值可能為負(fù)數(shù)，所以需要將

18、差值加上MAXSIZE（本題為n），然后與MAXSIZE（本題為n）求余，即（n+r-f)%n。（4）鏈?zhǔn)綏＝Y(jié)點(diǎn)為：(data,link)，top指向棧頂.若想摘除棧頂結(jié)點(diǎn)，并將刪除結(jié)點(diǎn)的值保存到x中,則應(yīng)執(zhí)行操作（ ）。Ax=top-data;top=top-link； Btop=top-link;x=top-link； Cx=top;top=top-link； Dx=top-link；答案：A解釋?zhuān)簒=top-data將結(jié)點(diǎn)的值保存到x中，top=top-link棧頂指針指向棧頂下一結(jié)點(diǎn)，即摘除棧頂結(jié)點(diǎn)。（5）設(shè)有一個(gè)遞歸算法如下 int fact(int n) /n大于等于0 if(n=

19、0) return 1; else return n*fact(n-1); 則計(jì)算fact(n)需要調(diào)用該函數(shù)的次數(shù)為（ ）。An+1 Bn-1 C n D n+2答案：A解釋?zhuān)禾厥庵捣?。設(shè)n=0，易知僅調(diào)用一次fact(n)函數(shù)，故選A。（6）棧在（ ）中有所應(yīng)用。A遞歸調(diào)用 B函數(shù)調(diào)用 C表達(dá)式求值 D前三個(gè)選項(xiàng)都有答案：D解釋?zhuān)哼f歸調(diào)用、函數(shù)調(diào)用、表達(dá)式求值均用到了棧的后進(jìn)先出性質(zhì)。（7）為解決計(jì)算機(jī)主機(jī)與打印機(jī)間速度不匹配問(wèn)題，通常設(shè)一個(gè)打印數(shù)據(jù)緩沖區(qū)。主機(jī)將要輸出的數(shù)據(jù)依次寫(xiě)入該緩沖區(qū)，而打印機(jī)則依次從該緩沖區(qū)中取出數(shù)據(jù)。該緩沖區(qū)的邏輯結(jié)構(gòu)應(yīng)該是（ ）。A隊(duì)列 B棧 C 線性表 D有

20、序表答案：A解釋?zhuān)航鉀Q緩沖區(qū)問(wèn)題應(yīng)利用一種先進(jìn)先出的線性表，而隊(duì)列正是一種先進(jìn)先出的線性表。（8）設(shè)棧S和隊(duì)列Q的初始狀態(tài)為空，元素e1、e2、e3、e4、e5和e6依次進(jìn)入棧S，一個(gè)元素出棧后即進(jìn)入Q，若6個(gè)元素出隊(duì)的序列是e2、e4、e3、e6、e5和e1，則棧S的容量至少應(yīng)該是（）。A2 B3 C4 D 6答案：B解釋?zhuān)涸爻鲫?duì)的序列是e2、e4、e3、e6、e5和e1，可知元素入隊(duì)的序列是e2、e4、e3、e6、e5和e1，即元素出棧的序列也是e2、e4、e3、e6、e5和e1，而元素e1、e2、e3、e4、e5和e6依次進(jìn)入棧，易知棧S中最多同時(shí)存在3個(gè)元素，故棧S的容量至少為3。（

21、9）若一個(gè)棧以向量V1.n存儲(chǔ)，初始棧頂指針top設(shè)為n+1，則元素x進(jìn)棧的正確操作是( )。Atop+; Vtop=x;BVtop=x; top+;Ctop-; Vtop=x;DVtop=x; top-;答案：C解釋?zhuān)撼跏紬ｍ斨羔榯op為n+1，說(shuō)明元素從數(shù)組向量的高端地址進(jìn)棧，又因?yàn)樵卮鎯?chǔ)在向量空間V1.n中，所以進(jìn)棧時(shí)top指針先下移變?yōu)閚，之后將元素x存儲(chǔ)在Vn。（10）設(shè)計(jì)一個(gè)判別表達(dá)式中左，右括號(hào)是否配對(duì)出現(xiàn)的算法，采用（）數(shù)據(jù)結(jié)構(gòu)最佳。A線性表的順序存儲(chǔ)結(jié)構(gòu) B隊(duì)列 C. 線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) D. 棧答案：D解釋?zhuān)豪脳５暮筮M(jìn)先出原則。（11）用鏈接方式存儲(chǔ)的隊(duì)列，在進(jìn)行刪除

22、運(yùn)算時(shí)（）。A. 僅修改頭指針 B. 僅修改尾指針C. 頭、尾指針都要修改 D. 頭、尾指針可能都要修改答案：D解釋?zhuān)阂话闱闆r下只修改頭指針，但是，當(dāng)刪除的是隊(duì)列中最后一個(gè)元素時(shí)，隊(duì)尾指針也丟失了，因此需對(duì)隊(duì)尾指針重新賦值。（12）循環(huán)隊(duì)列存儲(chǔ)在數(shù)組A0.m中，則入隊(duì)時(shí)的操作為（）。A. rear=rear+1 B. rear=(rear+1)%(m-1) C. rear=(rear+1)%m D. rear=(rear+1)%(m+1) 答案：D解釋?zhuān)簲?shù)組A0.m中共含有m+1個(gè)元素，故在求模運(yùn)算時(shí)應(yīng)除以m+1。（13）最大容量為n的循環(huán)隊(duì)列，隊(duì)尾指針是rear，隊(duì)頭是front，則隊(duì)空的條

23、件是（）。 A. (rear+1)%n=front B. rear=front Crear+1=front D. (rear-l)%n=front答案：B解釋?zhuān)鹤畲笕萘繛閚的循環(huán)隊(duì)列，隊(duì)滿條件是(rear+1)%n=front，隊(duì)空條件是rear=front。（14）棧和隊(duì)列的共同點(diǎn)是（）。A. 都是先進(jìn)先出 B. 都是先進(jìn)后出 C. 只允許在端點(diǎn)處插入和刪除元素 D. 沒(méi)有共同點(diǎn)答案：C解釋?zhuān)簵Ｖ辉试S在棧頂處進(jìn)行插入和刪除元素，隊(duì)列只允許在隊(duì)尾插入元素和在隊(duì)頭刪除元素。（15）一個(gè)遞歸算法必須包括（）。A. 遞歸部分 B. 終止條件和遞歸部分C. 迭代部分 D. 終止條件和迭代部分答案：B第

24、4章 串、數(shù)組和廣義表1選擇題（1）串是一種特殊的線性表，其特殊性體現(xiàn)在（ ）。 A可以順序存儲(chǔ) B數(shù)據(jù)元素是一個(gè)字符 C可以鏈?zhǔn)酱鎯?chǔ) D數(shù)據(jù)元素可以是多個(gè)字符若 答案：B（2）串下面關(guān)于串的的敘述中，（ ）是不正確的？ A串是字符的有限序列 B空串是由空格構(gòu)成的串C模式匹配是串的一種重要運(yùn)算 D串既可以采用順序存儲(chǔ)，也可以采用鏈?zhǔn)酱鎯?chǔ)答案：B解釋?zhuān)嚎崭癯３Ｊ谴淖址现械囊粋€(gè)元素，有一個(gè)或多個(gè)空格組成的串成為空格串，零個(gè)字符的串成為空串，其長(zhǎng)度為零。 （3）串“ababaaababaa”的next數(shù)組為（ ）。A C D答案：C（4）串“ababaabab”的nextval為（ ）。A01

25、0104101 B010102101 C010100011 D010101011 答案：A（5）串的長(zhǎng)度是指（ ）。A串中所含不同字母的個(gè)數(shù) B串中所含字符的個(gè)數(shù)C串中所含不同字符的個(gè)數(shù) D串中所含非空格字符的個(gè)數(shù)答案：B解釋?zhuān)捍凶址臄?shù)目稱(chēng)為串的長(zhǎng)度。（6）假設(shè)以行序?yàn)橹餍虼鎯?chǔ)二維數(shù)組A=array1.100,1.100，設(shè)每個(gè)數(shù)據(jù)元素占2個(gè)存儲(chǔ)單元，基地址為10，則LOC5,5=（ ）。A808 B818 C1010 D1020答案：B解釋?zhuān)阂孕行驗(yàn)橹?，則LOC5,5=（5-1）*100+（5-1）*2+10=818。（7）設(shè)有數(shù)組Ai,j，數(shù)組的每個(gè)元素長(zhǎng)度為3字節(jié)，i的值為1到8，j

26、的值為1到10，數(shù)組從內(nèi)存首地址BA開(kāi)始順序存放，當(dāng)用以列為主存放時(shí)，元素A5,8的存儲(chǔ)首地址為（ ）。ABA+141 BBA+180 CBA+222 DBA+225答案：B解釋?zhuān)阂粤行驗(yàn)橹?，則LOC5,8=（8-1）*8+（5-1）*3+BA=BA+180。（8）設(shè)有一個(gè)10階的對(duì)稱(chēng)矩陣A，采用壓縮存儲(chǔ)方式，以行序?yàn)橹鞔鎯?chǔ)，a11為第一元素，其存儲(chǔ)地址為1，每個(gè)元素占一個(gè)地址空間，則a85的地址為（ ）。A13 B32 C33 D40答案：C（9）若對(duì)n階對(duì)稱(chēng)矩陣A以行序?yàn)橹餍蚍绞綄⑵湎氯切蔚脑?包括主對(duì)角線上所有元素)依次存放于一維數(shù)組B1.(n(n+1)/2中，則在B中確定aij（i

27、j）的位置k的關(guān)系為（ ）。Ai*(i-1)/2+j Bj*(j-1)/2+i Ci*(i+1)/2+j Dj*(j+1)/2+i答案：B（10）二維數(shù)組A的每個(gè)元素是由10個(gè)字符組成的串，其行下標(biāo)i=0,1,8,列下標(biāo)j=1,2,10。若A按行先存儲(chǔ)，元素A8,5的起始地址與當(dāng)A按列先存儲(chǔ)時(shí)的元素（ ）的起始地址相同。設(shè)每個(gè)字符占一個(gè)字節(jié)。AA8,5 BA3,10 C. A5,8 DA0,9答案：B解釋?zhuān)涸O(shè)數(shù)組從內(nèi)存首地址M開(kāi)始順序存放，若數(shù)組按行先存儲(chǔ)，元素A8,5的起始地址為：M+（8-0）*10+（5-1）*1=M+84；若數(shù)組按列先存儲(chǔ)，易計(jì)算出元素A3,10的起始地址為：M+（10

28、-1）*9+（3-0）*1=M+84。故選B。（11）設(shè)二維數(shù)組A1. m，1. n（即m行n列）按行存儲(chǔ)在數(shù)組B1. m*n中，則二維數(shù)組元素Ai,j在一維數(shù)組B中的下標(biāo)為（ ）。A(i-1)*n+j B(i-1)*n+j-1 Ci*(j-1) Dj*m+i-1答案：A解釋?zhuān)禾厥庵捣?。取i=j=1，易知A1,1的的下標(biāo)為1，四個(gè)選項(xiàng)中僅有A選項(xiàng)能確定的值為1，故選A。（12）數(shù)組A0.4,-1.-3,5.7中含有元素的個(gè)數(shù)（ ）。A55 B45 C36 D16答案：B解釋?zhuān)汗灿?*3*3=45個(gè)元素。（13）廣義表A=(a,b,(c,d),(e,(f,g)，則Head(Tail(Head(T

29、ail(Tail(A)的值為（ ）。A(g) B(d) Cc Dd答案：D解釋?zhuān)篢ail(A)=(b,(c,d),(e,(f,g)；Tail(Tail(A)=( (c,d),(e,(f,g)； Head(Tail(Tail(A)= (c,d)；Tail(Head(Tail(Tail(A)=(d)；Head(Tail(Head(Tail(Tail(A)=d。（14）廣義表(a,b,c,d)的表頭是（ ），表尾是（ ）。Aa B( ) C(a,b,c,d) D(b,c,d)答案：C、B解釋?zhuān)罕眍^為非空廣義表的第一個(gè)元素，可以是一個(gè)單原子，也可以是一個(gè)子表，(a,b,c,d)的表頭為一個(gè)子表(a,b

30、,c,d)；表尾為除去表頭之外，由其余元素構(gòu)成的表，表為一定是個(gè)廣義表，(a,b,c,d)的表尾為空表( )。（15）設(shè)廣義表L=(a,b,c)，則L的長(zhǎng)度和深度分別為（ ）。A1和1 B1和3 C1和2 D2和3 答案：C解釋?zhuān)簭V義表的深度是指廣義表中展開(kāi)后所含括號(hào)的層數(shù)，廣義表的長(zhǎng)度是指廣義表中所含元素的個(gè)數(shù)。根據(jù)定義易知L的長(zhǎng)度為1，深度為2。2應(yīng)用題 （1）已知模式串t=abcaabbabcab寫(xiě)出用KMP法求得的每個(gè)字符對(duì)應(yīng)的next和nextval函數(shù)值。答案：模式串t的next和nextval值如下：j1 2 3 4 5 6 7 8 9 10 11 12 t串a(chǎn) b c a a

31、b b a b c a bnextj0 1 1 1 2 2 3 1 2 3 4 5nextvalj0 1 1 0 2 1 3 0 1 1 0 5（2）設(shè)目標(biāo)為t=“abcaabbabcabaacbacba”,模式為p=“abcabaa” 計(jì)算模式p的naxtval函數(shù)值； 不寫(xiě)出算法,只畫(huà)出利用KMP算法進(jìn)行模式匹配時(shí)每一趟的匹配過(guò)程。答案： p的nextval函數(shù)值為0110132。（p的next函數(shù)值為0111232）。 利用KMP(改進(jìn)的nextval)算法，每趟匹配過(guò)程如下： 第一趟匹配： abcaabbabcabaacbacba abcab(i=5,j=5) 第二趟匹配： abcaa

32、bbabcabaacbacba abc(i=7,j=3) 第三趟匹配： abcaabbabcabaacbacba a(i=7,j=1) 第四趟匹配： abcaabbabcabaac bacba (成功) abcabaa(i=15,j=8)（3）數(shù)組A中，每個(gè)元素Ai,j的長(zhǎng)度均為32個(gè)二進(jìn)位,行下標(biāo)從-1到9，列下標(biāo)從1到11，從首地址S開(kāi)始連續(xù)存放主存儲(chǔ)器中，主存儲(chǔ)器字長(zhǎng)為16位。求： 存放該數(shù)組所需多少單元？ 存放數(shù)組第4列所有元素至少需多少單元？ 數(shù)組按行存放時(shí)，元素A7,4的起始地址是多少？ 數(shù)組按列存放時(shí)，元素A4,7的起始地址是多少？答案：每個(gè)元素32個(gè)二進(jìn)制位，主存字長(zhǎng)16位，故

33、每個(gè)元素占2個(gè)字長(zhǎng)，行下標(biāo)可平移至1到11。（1）242 （2）22 （3）s+182 （4）s+142(4)請(qǐng)將香蕉banana用工具 H( )Head( )，T( )Tail( )從L中取出。L=(apple,(orange,(strawberry,(banana),peach),pear)答案：H（H（T（H（T（H（T（L）第5章 樹(shù)和二叉樹(shù)1選擇題（1）把一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)后，這棵二叉樹(shù)的形態(tài)是（ ）。 A唯一的 有多種C有多種，但根結(jié)點(diǎn)都沒(méi)有左孩子 有多種，但根結(jié)點(diǎn)都沒(méi)有右孩子答案：A 解釋?zhuān)阂驗(yàn)槎鏄?shù)有左孩子、右孩子之分，故一棵樹(shù)轉(zhuǎn)換為二叉樹(shù)后，這棵二叉樹(shù)的形態(tài)是唯一的。（2）由

34、3個(gè)結(jié)點(diǎn)可以構(gòu)造出多少種不同的二叉樹(shù)？（ ）A2 B3 C4 D5 答案：D解釋?zhuān)何宸N情況如下： （3）一棵完全二叉樹(shù)上有1001個(gè)結(jié)點(diǎn)，其中葉子結(jié)點(diǎn)的個(gè)數(shù)是（ ）。A250 B 500 C254 D501 答案：D解釋?zhuān)涸O(shè)度為0結(jié)點(diǎn)（葉子結(jié)點(diǎn)）個(gè)數(shù)為A，度為1的結(jié)點(diǎn)個(gè)數(shù)為B，度為2的結(jié)點(diǎn)個(gè)數(shù)為C，有A=C+1，A+B+C=1001，可得2C+B=1000，由完全二叉樹(shù)的性質(zhì)可得B=0或1，又因?yàn)镃為整數(shù)，所以B=0，C=500，A=501，即有501個(gè)葉子結(jié)點(diǎn)。（4）一個(gè)具有1025個(gè)結(jié)點(diǎn)的二叉樹(shù)的高h(yuǎn)為（ ）。A11 B10 C11至1025之間 D10至1024之間答案：C解釋?zhuān)喝裘繉觾H

35、有一個(gè)結(jié)點(diǎn)，則樹(shù)高h(yuǎn)為1025；且其最小樹(shù)高為log21025+1=11，即h在11至1025之間。（5）深度為h的滿m叉樹(shù)的第k層有（ ）個(gè)結(jié)點(diǎn)。(1=k=h) Amk-1 Bmk-1 Cmh-1 Dmh-1答案：A解釋?zhuān)荷疃葹閔的滿m叉樹(shù)共有mh-1個(gè)結(jié)點(diǎn)，第k層有mk-1個(gè)結(jié)點(diǎn)。（6）利用二叉鏈表存儲(chǔ)樹(shù)，則根結(jié)點(diǎn)的右指針是（ ）。A指向最左孩子 B指向最右孩子 C空 D非空答案：C解釋?zhuān)豪枚骀湵泶鎯?chǔ)樹(shù)時(shí)，右指針指向兄弟結(jié)點(diǎn)，因?yàn)楦?jié)點(diǎn)沒(méi)有兄弟結(jié)點(diǎn)，故根節(jié)點(diǎn)的右指針指向空。（7）對(duì)二叉樹(shù)的結(jié)點(diǎn)從1開(kāi)始進(jìn)行連續(xù)編號(hào)，要求每個(gè)結(jié)點(diǎn)的編號(hào)大于其左、右孩子的編號(hào)，同一結(jié)點(diǎn)的左右孩子中，其左孩子

36、的編號(hào)小于其右孩子的編號(hào)，可采用（ ）遍歷實(shí)現(xiàn)編號(hào)。A先序 B. 中序 C. 后序 D. 從根開(kāi)始按層次遍歷答案：C解釋?zhuān)焊鶕?jù)題意可知按照先左孩子、再右孩子、最后雙親結(jié)點(diǎn)的順序遍歷二叉樹(shù)，即后序遍歷二叉樹(shù)。（8）若二叉樹(shù)采用二叉鏈表存儲(chǔ)結(jié)構(gòu)，要交換其所有分支結(jié)點(diǎn)左、右子樹(shù)的位置，利用（ ）遍歷方法最合適。A前序 B中序 C后序 D按層次答案：C解釋?zhuān)汉罄m(xù)遍歷和層次遍歷均可實(shí)現(xiàn)左右子樹(shù)的交換，不過(guò)層次遍歷的實(shí)現(xiàn)消耗比后續(xù)大，后序遍歷方法最合適。（9）在下列存儲(chǔ)形式中，（ ）不是樹(shù)的存儲(chǔ)形式？A雙親表示法 B孩子鏈表表示法 C孩子兄弟表示法 D順序存儲(chǔ)表示法答案：D解釋?zhuān)簶?shù)的存儲(chǔ)結(jié)構(gòu)有三種：雙親表

37、示法、孩子表示法、孩子兄弟表示法，其中孩子兄弟表示法是常用的表示法，任意一棵樹(shù)都能通過(guò)孩子兄弟表示法轉(zhuǎn)換為二叉樹(shù)進(jìn)行存儲(chǔ)。（10）一棵非空的二叉樹(shù)的先序遍歷序列與后序遍歷序列正好相反，則該二叉樹(shù)一定滿足（ ）。A所有的結(jié)點(diǎn)均無(wú)左孩子 B所有的結(jié)點(diǎn)均無(wú)右孩子C只有一個(gè)葉子結(jié)點(diǎn) D是任意一棵二叉樹(shù)答案：C解釋?zhuān)阂驗(yàn)橄刃虮闅v結(jié)果是“中左右”，后序遍歷結(jié)果是“左右中”，當(dāng)沒(méi)有左子樹(shù)時(shí)，就是“中右”和“右中”；當(dāng)沒(méi)有右子樹(shù)時(shí)，就是“中左”和“左中”。則所有的結(jié)點(diǎn)均無(wú)左孩子或所有的結(jié)點(diǎn)均無(wú)右孩子均可，所以A、B不能選，又所有的結(jié)點(diǎn)均無(wú)左孩子與所有的結(jié)點(diǎn)均無(wú)右孩子時(shí)，均只有一個(gè)葉子結(jié)點(diǎn)，故選C。（11）設(shè)哈

38、夫曼樹(shù)中有199個(gè)結(jié)點(diǎn)，則該哈夫曼樹(shù)中有（ ）個(gè)葉子結(jié)點(diǎn)。A99B100 C101D102答案：B解釋?zhuān)涸诠蚵鼧?shù)中沒(méi)有度為1的結(jié)點(diǎn)，只有度為0（葉子結(jié)點(diǎn)）和度為2的結(jié)點(diǎn)。設(shè)葉子結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2的結(jié)點(diǎn)的個(gè)數(shù)為n2，由二叉樹(shù)的性質(zhì)n0=n2+1，則總結(jié)點(diǎn)數(shù)n= n0+n2=2*n0-1，得到n0=100。（12）若X是二叉中序線索樹(shù)中一個(gè)有左孩子的結(jié)點(diǎn)，且X不為根，則X的前驅(qū)為（ ）。AX的雙親 BX的右子樹(shù)中最左的結(jié)點(diǎn) CX的左子樹(shù)中最右結(jié)點(diǎn) DX的左子樹(shù)中最右葉結(jié)點(diǎn)答案：C（13）引入二叉線索樹(shù)的目的是（ ）。A加快查找結(jié)點(diǎn)的前驅(qū)或后繼的速度 B為了能在二叉樹(shù)中方便的進(jìn)行插入與刪除C

39、為了能方便的找到雙親 D使二叉樹(shù)的遍歷結(jié)果唯一答案：A（14）設(shè)F是一個(gè)森林，B是由F變換得的二叉樹(shù)。若F中有n個(gè)非終端結(jié)點(diǎn)，則B中右指針域?yàn)榭盏慕Y(jié)點(diǎn)有（ ）個(gè)。An1BnCn + 1Dn + 2答案：C（15）n（n2）個(gè)權(quán)值均不相同的字符構(gòu)成哈夫曼樹(shù)，關(guān)于該樹(shù)的敘述中，錯(cuò)誤的是（）。A該樹(shù)一定是一棵完全二叉樹(shù)B樹(shù)中一定沒(méi)有度為1的結(jié)點(diǎn)C樹(shù)中兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)D樹(shù)中任一非葉結(jié)點(diǎn)的權(quán)值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值答案：A解釋?zhuān)汗蚵鼧?shù)的構(gòu)造過(guò)程是每次都選取權(quán)值最小的樹(shù)作為左右子樹(shù)構(gòu)造一棵新的二叉樹(shù)，所以樹(shù)中一定沒(méi)有度為1的結(jié)點(diǎn)、兩個(gè)權(quán)值最小的結(jié)點(diǎn)一定是兄弟結(jié)點(diǎn)、任一非葉結(jié)點(diǎn)的權(quán)

40、值一定不小于下一層任一結(jié)點(diǎn)的權(quán)值。2應(yīng)用題（1）試找出滿足下列條件的二叉樹(shù) 先序序列與后序序列相同 中序序列與后序序列相同 先序序列與中序序列相同 中序序列與層次遍歷序列相同答案：先序遍歷二叉樹(shù)的順序是“根左子樹(shù)右子樹(shù)”，中序遍歷“左子樹(shù)根右子樹(shù)”，后序遍歷順序是：“左子樹(shù)右子樹(shù)根，根據(jù)以上原則有 或?yàn)榭諛?shù)，或?yàn)橹挥懈Y(jié)點(diǎn)的二叉樹(shù) 或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有左子樹(shù)的二叉樹(shù) 或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹(shù)的二叉樹(shù) 或?yàn)榭諛?shù)，或?yàn)槿我唤Y(jié)點(diǎn)至多只有右子樹(shù)的二叉樹(shù)（2）設(shè)一棵二叉樹(shù)的先序序列： A B D F C E G H ，中序序列： B F D A G E H C畫(huà)出這棵二叉樹(shù)。畫(huà)出這

41、棵二叉樹(shù)的后序線索樹(shù)。將這棵二叉樹(shù)轉(zhuǎn)換成對(duì)應(yīng)的樹(shù)（或森林）。答案： ABFDCEHG （3） 假設(shè)用于通信的電文僅由8個(gè)字母組成，字母在電文中出現(xiàn)的頻率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。 試為這8個(gè)字母設(shè)計(jì)赫夫曼編碼。 試設(shè)計(jì)另一種由二進(jìn)制表示的等長(zhǎng)編碼方案。 對(duì)于上述實(shí)例，比較兩種方案的優(yōu)缺點(diǎn)。答案：方案1；哈夫曼編碼先將概率放大100倍，以方便構(gòu)造哈夫曼樹(shù)。 w=7,19,2,6,32,3,21,10，按哈夫曼規(guī)則：【（2,3），6, (7,10)】, 19, 21, 32（100）（40） （60）19 21 32 （28）（17） （

42、11） 7 10 6 （5） 2 3 0 1 0 1 0 119 21 32 0 10 1 0 17 10 6 0 12 3 方案比較：字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率10002001301040115100610171108111字母編號(hào)對(duì)應(yīng)編碼出現(xiàn)頻率111002003111104111051061111170181101方案1的WPL方案2的WPL3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3結(jié)論：哈夫曼編碼優(yōu)于等長(zhǎng)二進(jìn)制編碼（4）已知下列字符A、B、C、D、E、F、G的權(quán)值分別為3、12、7、4、2、8，11，試填寫(xiě)出其對(duì)應(yīng)哈夫曼樹(shù)HT的存儲(chǔ)結(jié)構(gòu)的初態(tài)

43、和終態(tài)。答案：weightparentlchildrchild13000212000370004400052000680007110008000900010000110001200013000初態(tài):終態(tài)：weightparentlchildrchild13800212120037100044900528006810007111100859519911481015123611201397122713210134701112第6章 圖1選擇題（1）在一個(gè)圖中，所有頂點(diǎn)的度數(shù)之和等于圖的邊數(shù)的（ ）倍。 A1/2 B1 C2 D4 答案：C（2）在一個(gè)有向圖中，所有頂點(diǎn)的入度之和等于所有頂點(diǎn)的出度之和的（ ）倍。 A1/2 B1 C2 D4 答案：B解釋?zhuān)河邢驁D所有頂點(diǎn)入度之和等于所有頂點(diǎn)出度之和。（3）具有n個(gè)頂點(diǎn)的有向圖最多有（ ）條邊。 An Bn(n-1) Cn(n+1) Dn2 答案：B解釋?zhuān)河邢驁D的邊有方向之分，即為從n個(gè)頂點(diǎn)中選取2個(gè)頂點(diǎn)有序排列，結(jié)果為n(n-1)。（4）n個(gè)頂點(diǎn)的連通圖用鄰接距陣表示時(shí)，該距陣