電大數(shù)據(jù)結(jié)構(gòu)(本科)期末復(fù)習(xí)材料1

1、數(shù)據(jù)結(jié)構(gòu)（本）期末綜合練習(xí)一、單項(xiàng)選擇題1數(shù)據(jù)元素是數(shù)據(jù)的基本單位，它（C ）。B .至少有二個數(shù)據(jù)項(xiàng)組成D .至少有一個數(shù)據(jù)項(xiàng)為指針類型B.只能有唯一的D.的數(shù)據(jù)元素之間的關(guān)系稱為B .數(shù)據(jù)元素是不能隨機(jī)訪問的D .進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高A 只能有一個數(shù)據(jù)項(xiàng)組成C 可以是一個數(shù)據(jù)項(xiàng)也可以由若干個數(shù)據(jù)項(xiàng)組成2 一種邏輯結(jié)構(gòu)（ A ）存儲結(jié)構(gòu)。A 可以有不同的C 的數(shù)據(jù)元素在計(jì)算機(jī)中的表示稱為3 線性表的順序結(jié)構(gòu)中，（ C ）。A 邏輯上相鄰的元素在物理位置上不一定相鄰C 邏輯上相鄰的元素在物理位置上也相鄰4. 以下說法中不正確的是（ B ） o結(jié)點(diǎn)的指針就能訪問到鏈表中每個結(jié)點(diǎn)A .

2、雙向循環(huán)鏈表中每個結(jié)點(diǎn)需要包含兩個指針域B. 已知單向鏈表中任D .單向循環(huán)鏈表中尾結(jié)點(diǎn)的指針域中存放的是頭指針D .順序表C. 順序存儲的線性鏈表是可以隨機(jī)訪問的5. 以下表中可以隨機(jī)訪問的是（D ）oA .單向鏈表B .雙向鏈表C.單向循環(huán)鏈表6. 雙向循環(huán)鏈表結(jié)點(diǎn)的數(shù)據(jù)類型為：struct node int data;struct node *next;/*指向直接后繼 */struct node *prior;；設(shè) p 指向表中某一結(jié)點(diǎn)，要顯示 p 所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)的數(shù)據(jù)元素，可用操作（B ）。A. printf（ “%d”,p-next-data）;B. printf（ “%d

3、”,p-prior-data）;C . printf（ “%d ”,p-prior-next）;D . printf（ “%d ”,p-data）;7. 設(shè)順序存儲的線性表長度為n,對于刪除操作，設(shè)刪除位置是等概率的，則刪除一個元素平均移動元素的次數(shù)為（ A ）。A. (n+1)/2B. nC. 2nD . n-i8.個棧的進(jìn)棧序列是efgh，則棧的不可能的出棧序列是（D ）（進(jìn)出棧操作可以交替進(jìn)行）9.設(shè) top 是一個鏈棧的棧頂指針,棧中每個結(jié)點(diǎn)由一個數(shù)據(jù)域 data 和指針域 next 組成, 設(shè)用 x 接收棧頂元素,則出棧操作為（A）。A hgfeB gfehC fgehD . ehf

4、gA . x=top-data;top=top-next;C . x=top- next;top=top- data;B . top=top-next;x=top-data;D . top-next =top; x=top-data;10 .設(shè) top 是一個鏈棧的棧頂指針，棧中每個結(jié)點(diǎn)由一個數(shù)據(jù)域 data 和指針域 next 組成，設(shè)用 x 接收棧頂元素，則取棧頂元素的操作為（ C ）。A. top-data= x; B. top=top-next;11.以下說法正確的是（C ）。A .隊(duì)列是后進(jìn)先出C 棧的刪除和插入操作都只能在棧頂進(jìn)行C . x=top-data; D . x=top-

5、data; top= top-nextB .棧的特點(diǎn)是后進(jìn)后出D .隊(duì)列的刪除和插入操作都只能在隊(duì)頭進(jìn)行13 .串函數(shù) StrCmp( abA”,”aba”)的值為( D )。A. 1B. 0C.“abAaba”D. -114. char *p;p=StrCat(“ABD ”,”ABC ”);Printf( “%s”,p);的顯示結(jié)果為( B )。A. -1B. ABDABCC. ABD. 115 .設(shè)有一個12階的對稱矩陣A，采用壓縮存儲方式將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組b中（矩陣A的第一個元素為 ai,i，數(shù)組b的下標(biāo)從1開始），則矩陣A中第4行的元素在數(shù)組b中的下標(biāo) i 一定有

6、（ A ）。A、 7W i next= =head C . head-next= = NULL D . head = =head-next35 .以下特征中，（D ）不是算法的特性。A.有窮性 B .確定性 C .可行性.有0個或多個輸出36 設(shè)順序存儲的線性表長度為n,對于插入操作，設(shè)插入位置是等概率的，則插入一個元素平均移動元素的次數(shù)為（ A ）。A n/2B nC. n-1D. n-i+137設(shè)有一個長度為 n 的順序表,要在第 i 個元素之前（也就是插入元素作為新表的第 i 個元素）, 則移動元素個數(shù)為（ A ）。A n-i+1 B n-i C n-i-1 Di38一個棧的進(jìn)棧序列是

7、5, 6, 7, 8,則棧的不可能的出棧序列是（ A ）（進(jìn)出棧操作可以交替進(jìn)行）A 5,8,6,7B 7,6, 8, 5C 7,6,5,8D 8,7, 6, 539棧的插入刪除操作在（D）進(jìn)行。A 棧底 B 任意位置 C 指定位置 D 棧頂 40棧和隊(duì)列的相同點(diǎn)是（D）。A .都是后進(jìn)先出B.都是后進(jìn)后出C .邏輯結(jié)構(gòu)與線性表不同D .邏輯結(jié)構(gòu)與線性表相同，都是操作規(guī)則受到限制的線性表41 以下說法正確的是（ C ）。A .棧的特點(diǎn)是先進(jìn)先出，隊(duì)列的特點(diǎn)是先進(jìn)后出B .棧和隊(duì)列的特點(diǎn)都是先進(jìn)后出C.棧的特點(diǎn)是先進(jìn)后出，隊(duì)列的特點(diǎn)是先進(jìn)先出D .棧和隊(duì)列的特點(diǎn)都是先進(jìn)先出42 .在C語言中，利

8、用數(shù)組 a存放字符串“ Hello ”，以下語句中正確的是（ A ）。Achar a10= “Hello” ;Bchar a10; a=“Hello” ;Cchar a10= Hello ; Dchar a10= H ,e,l ,l ,o;43元素 2, 4, 6, 8 按順序依次進(jìn)棧,則該棧的不可能輸出序列是（ D ）（進(jìn)棧出?？梢越惶孢M(jìn)行） 。A 8,6,4,2 B 2,4,6,8 C4,2,8,6 D 8,6, 2, 444. 設(shè)有一個15階的對稱矩陣 A，采用壓縮存儲方式將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組b 中。（矩陣A的第一個元素為ai,i,數(shù)組b的下標(biāo)從1開始），則數(shù)組元素b

9、13對應(yīng)A的矩陣元素是（A ）。A. a5,3B. a6,4C. a7,2D. a6,845. 設(shè)有一個15階的對稱矩陣A,采用壓縮存儲的方式，將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組B中（數(shù)組下標(biāo)從1開始），則矩陣中元素 a7,6在一維數(shù)組B中的下標(biāo)是（C ）。A. 42B. 13 C . 27 D . 3246. 一棵完全二叉樹共有 30 個結(jié)點(diǎn),則該樹一共有（ D）層 （根結(jié)點(diǎn)所在層為第一層 ）。A. 6B. 4C . 3D . 547. 串函數(shù) StrCmp （“d”，“D）的值為（B ）。A . 0B. 1C . -1D. 348. 以下說法正確的是（ D ）。A.連通圖G的生成樹中

10、不一定包含G的所有頂點(diǎn)B .連通圖G的生成樹中一定要包含 G的所有邊C.連通圖G的生成樹一定是唯一的D .連通圖G 一定存在生成樹49. 在一棵二叉樹中，若編號為i的結(jié)點(diǎn)存在右孩子，則右孩子的順序編號為（ D ） oA . 2iB. 2i-1 C . 2i+2 D . 2i+150. 對二叉排序樹進(jìn)行（ C ）遍歷，遍歷所得到的序列是有序序列。A .按層次B .前序C .中序D .后序51 .設(shè)一棵有n個結(jié)點(diǎn)采用鏈?zhǔn)酱鎯Φ亩鏄洌瑒t該樹共有（ D ）個指針域?yàn)榭?。A 2nB. 2n+1 C . 2n+2 D . n+152 .以下排序算法中,在一趟排序過程中，除了其它相關(guān)操作外，只進(jìn)行一次元素

11、間的交換的算法是(A )oA.直接選擇B.冒泡C.直接插入D.折半插入53 .已知如圖1所示的一個圖，若從頂點(diǎn)a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷,則可能得到的一種頂點(diǎn)序列為（B ）o AC.aebcfd.acfdeb54 .對長度為n的線性表進(jìn)行順序查找，在等概率情況下，平均查找長度為（B. (n+1) /2C . 2nD . n-155 .在有序表1 , 3, 8, 13, 33, 42, 46, 63, 76, 78, 86, 97, 100中,用折半查找值86時，經(jīng)（D ）次比較后查找成功。56 .如圖若從頂點(diǎn)a出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的頂點(diǎn)序列為（A )oA rear-n

12、ext=p;rear=p;B rear-next=p; p = rear;A. acfgedbB. aedcbgfC. acfebdgD. aecbdgf57.有一個長度為10的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為（A ）。A . 29/10B.31/10C26/10 D . 29/958. 一棵哈夫曼樹有12個葉子結(jié)點(diǎn)（終端結(jié)點(diǎn)），該樹總共有（ C ）個結(jié)點(diǎn)。A. 22B . 21C . 23D . 2459 . 一組記錄的關(guān)鍵字序列為（37, 70 , 47, 29, 31 , 85）,利用快速排序，以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為（A ）

13、。A. 31, 29, 37, 47,C. 31 , 29, 37, 70,70, 8547, 85BD.29, 31, 37, 47, 70, 85.31, 29, 37, 85,47, 7060 .隊(duì)列的刪除操作在（A )進(jìn)行。A.隊(duì)頭B .隊(duì)尾C .隊(duì)頭或隊(duì)尾D.在任意指疋位置61. （ A ）是性質(zhì)相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的子集。A .數(shù)據(jù)對象B .數(shù)據(jù)元素C .數(shù)據(jù)結(jié)構(gòu)D .數(shù)據(jù)項(xiàng)NODE *p ;為了申請一個新結(jié)點(diǎn)，并由62. 設(shè)鏈表中的結(jié)點(diǎn)是 NODE類型的結(jié)構(gòu)體變量，且有向該結(jié)點(diǎn)，可用以下語句(D )。A . p=(NODE *)malloc(sizeof(p);B. p=

14、(*NODE)malloc(sizeof(NODE);C. p=(NODE )malloc(sizeof(p);D. p=(NODE *)malloc(sizeof(NODE);63. 設(shè)順序存儲的線性長度為n,要在第i個元素之前插入一個新元素，按課本的算法當(dāng)i=( C )時,移動元素次數(shù)為2A. n/2B . nC . n-1C . 164 . 一個棧的進(jìn)棧序列是 1, 2, 3, 4,則棧的不可能的出棧序列是( D)(進(jìn)出棧操作可以交替進(jìn)行)A . 3, 2, 4, 1B . 3, 2, 1 , 4C . 4, 3, 2, 1D. 1 , 4, 2, 365 .設(shè)有一個帶頭結(jié)點(diǎn)的鏈隊(duì)列，隊(duì)

15、列中每個結(jié)點(diǎn)由一個數(shù)據(jù)域data和指針域next組成，front和rearCp = rear-next;rear=p;D rear=p;rear-next=p;66以下說法不正確的是（ D ）。A 順序棧中，棧滿時再進(jìn)行進(jìn)棧操作稱為“上溢”B. 順序棧中，?？諘r再作出棧棧操作稱為“下溢”C. 順序隊(duì)列中，隊(duì)列的頭指針和尾指針均超越隊(duì)列存儲空間的上界，則隊(duì)列已空D. 順序隊(duì)列中，當(dāng)尾指針已經(jīng)超越隊(duì)列存儲空間的上界，則一定是隊(duì)列已滿67.設(shè)有一個20階的對稱矩陣 A，采用壓縮存儲方式，將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組中（矩陣A的第一個元素為an，數(shù)組b的下標(biāo)從1開始），則矩陣元素a8,5在

16、一維數(shù)組b中的下 標(biāo)是（ D ）。A. 30B. 28C. 40D 3368已知一個圖的所有頂點(diǎn)的度數(shù)之和為m,則m 定不可能是D ）。A4B8C1269以下說法正確的是（C ）。A 連通圖 G 的生成樹中可以包含回路D9B 連通圖G的生成樹可以是不連通的C.連通圖G的生成樹一定是連通而不包含回路的D .連通圖G的生成樹一定是唯一的70對 n 個元素進(jìn)行冒泡排序,通常要進(jìn)行 n-1 趟冒泡,在第 j 趟冒泡中共要進(jìn)行（ C ）次元素間的比較。AjBj-1C n-jD n-j-171在排序過程中,可以有效地減少一趟排序過程中元素間的比較次數(shù)的算法是（C ）。A 冒泡72 一棵哈夫曼樹有A 2n-

17、273數(shù)據(jù)的（AA 邏輯B 物理74從 n 個數(shù)中選取最大元素（A .基本操作是數(shù)據(jù)元素間的交換C.算法的時間復(fù)雜度是0（ n2）B 選擇C 折半插入D 直接插入n 個葉子結(jié)點(diǎn)（終端結(jié)點(diǎn)） ,該樹總共有（ B ）個結(jié)點(diǎn)。B 2n-1C 2nD 2n+2）結(jié)構(gòu)與所使用的計(jì)算機(jī)無關(guān)。C.存儲D .邏輯與存儲B）。B .算法的時間復(fù)雜度是0（n）D .需要進(jìn)行（n +1）次數(shù)據(jù)元素間的比較75 .設(shè)head為非空的單向循環(huán)鏈表頭指針，p指向鏈表的尾結(jié)點(diǎn)， 則滿足邏輯表達(dá)式（B ）的值為真。A . p-next=NULLB.p-next= =headCp-next=headD. p= =NULL76.

18、設(shè)順序存儲的線性表長度為n，要刪除第 i 個元素，按課本的算法，當(dāng)i= （ C ）時，移動元素的95 .線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在（ C ）的關(guān)系。次數(shù)為 3。B . n/2C . n-377.一個棧的進(jìn)棧序列是 a, b,c,d,則棧的不可能的出棧序列是（）。A . dcbaB . bcadC. cbadD. adbc78. 設(shè)有一個帶頭結(jié)點(diǎn)的鏈隊(duì)列,隊(duì)列中每個結(jié)點(diǎn)由一個數(shù)據(jù)域data 和指針域 next 組成, front 和 rear分別為鏈隊(duì)列的頭指針和尾指針,要執(zhí)行出隊(duì)操作,用x 保存出隊(duì)元素的值, p 為指向結(jié)點(diǎn)類型的指針,可執(zhí)行如下操作： p=front-next;x=p-

19、data;然后指行（ D ）。A. front=p-next;B. front-next =p;C. front=p;D . front-next=p-next;C ）字節(jié)。79. 在 C 語言中,存儲字符串“ ABCD ”需要占用（B. 2A. 480. 設(shè)有一個10階的對稱矩陣 A，采用壓縮存儲方式將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組b中。（矩陣A的第一個元素為 ai,i，數(shù)組b的下標(biāo)從1開始），則矩陣元素a5,3對應(yīng)一維數(shù)組b的數(shù) 組元素是（ C ）。A. b18B. b8C. b13D. b1081設(shè)有一個15階的對稱矩陣A，采用壓縮存儲方式將其下三角部分以行序?yàn)橹餍虼鎯Φ揭痪S數(shù)組

20、b中。（矩陣A的第一個元素為 a1,1,數(shù)組b的下標(biāo)從1開始），則數(shù)組元素b13對應(yīng)A的矩陣元素是（ A ）。A.a5,3B. a6,4C.a7,2D .a6,882.深度為 5 的完全二叉樹共有20 個結(jié)點(diǎn),則第 5 層上有（ C ）個結(jié)點(diǎn) （根所在結(jié)點(diǎn)為第一層 ）。A. 3B. 8C.D. 683.已知一個圖的所有頂點(diǎn)的度數(shù)之和為m,且m是以下4中情況之一，貝U m只可能是（D ）。A. 9B. 7C.1584. 以下說法正確的是（ C ）。A .連通圖 G 的生成樹中不一定包含G的所有頂點(diǎn) B 連通圖G的生成樹中一定要包含 G的所有邊85. 線性表只要以（ C ）方式存儲就能進(jìn)行折半查找

21、。A .鏈接B .順序C .關(guān)鍵字有序的順序D .二叉樹86 對二叉排序樹進(jìn)行（C ）遍歷，遍歷所得到的序列是有序序列。A .按層次B .前序C .中序D .后序87 對n個元素進(jìn)行冒泡排序若某趟冒泡中只進(jìn)行了（C ）次元素間的交換，則表明序列已經(jīng)排好序。A. 1B. 2C. 0D. n-188 .在對一組元素（64, 48, 106, 33, 25, 82, 70, 55, 93）進(jìn)行直接插入排序時，當(dāng)進(jìn)行到要把第7個元素70插入到已經(jīng)排好序的子表時，為找到插入位置，需進(jìn)行（ C ）次元素間的比較（指由小到大排序）。A. 6B. 2C. 3D. 489.如圖，若從頂點(diǎn)a出發(fā)按廣度優(yōu)先搜索法進(jìn)

22、行遍歷，則可能得到的頂點(diǎn)序列為（C ）。A. acebdgfB . acfedgbC. abecdgfD . abecfdgaecg90 . 一棵哈夫曼樹有10個非葉子結(jié)點(diǎn)（非終端結(jié)點(diǎn)），該樹總共有（A ）個結(jié)點(diǎn)。A . 21B . 20C . 22D . 1991 . 一棵哈夫曼樹有12個葉子結(jié)點(diǎn)（終端結(jié)點(diǎn)），該樹總共有（ C）個結(jié)點(diǎn)。A . 21B . 22C . 23D. 2492 .隊(duì)列的插入操作在（進(jìn)行。A.隊(duì)頭B.隊(duì)尾C.隊(duì)頭或隊(duì)尾D .在任意指定位置93 .隊(duì)列的刪除操作在（ B進(jìn)行。A.隊(duì)尾B.隊(duì)頭C.隊(duì)頭或隊(duì)尾D .在任意指定位置94 .鏈表所具備的特點(diǎn)是（C ）。A.可以隨

23、機(jī)訪問任一結(jié)點(diǎn)B. 占用連續(xù)的存儲空間C.插人刪除元素的操作不需要移動元素結(jié)點(diǎn)D.可以通過下標(biāo)對鏈表進(jìn)行直接訪問A. 一對一B. 一對多C.多對多D.每一個元素都有一個直接前驅(qū)和一個直接后繼96.算法的時間復(fù)雜度與（C ）有關(guān)。A.所使用的計(jì)算機(jī)B.與計(jì)算機(jī)的操作系統(tǒng)C.與算法本身D.與數(shù)據(jù)結(jié)構(gòu)97. 4.在一個單鏈表中，p,q分別指向表中兩個相鄰的結(jié)點(diǎn)，且q所指結(jié)點(diǎn)是p所指結(jié)點(diǎn)的直接后繼，現(xiàn)要刪除q所指結(jié)點(diǎn)，可用的語句是（）。A. p =q- riextB. p_n ext=qC. p-n ext=q-n extD.q-n ext=NULL98在一個鏈隊(duì)中，假設(shè) f和r分別為隊(duì)頭和隊(duì)尾指針，

24、則刪除一個結(jié)點(diǎn)的運(yùn)算為（C ）A. r=f-n ext;B. r=r-n ext; C. f=f-n ext;D. f=r-n ext;99元素3,6,9按順序依次進(jìn)棧，則該棧的不可能輸出序列是（B ）（進(jìn)棧出?？梢越惶孢M(jìn)行）A. 9, 6, 3 B. 9 , 3, 6 C. 6, 3, 9 D. 3, 9, 6100. 設(shè)有一個10階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序?yàn)橹鞔鎯Φ揭痪S數(shù)組B 中（數(shù)組下標(biāo)從1開始），則矩陣中元素戊.s在一維數(shù)組B中的下標(biāo)是（）A.33B.32C. 85D. 41101. 排序方法中，從尚未排序序列中挑選元素，并將其依次放入已排序序列（初始為空

25、）的一端的方法， 稱為（D ）排序。A.歸并 B. 插人 C. 快速 D. 選擇102. 排序算法中，從未排序序列中依次取出元素與已排序序列（初始為空）中的元素進(jìn)行比較（要求比較次數(shù)盡量少），然后將其放入已排序序列的正確位置的方法是（C）。A.冒泡 B.直接插入C.折半插入D.選擇排序二、填空題1. 通常數(shù)據(jù)的邏輯結(jié)構(gòu)包括集合、亠線性一、_樹形、圖狀四種類型。2. 通常可以把一本含有不同章節(jié)的書的目錄結(jié)構(gòu)抽象成_樹形結(jié)構(gòu)。3. 設(shè)有一個單向鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，頭指針為head, p指向尾結(jié)點(diǎn)，為了使該單向鏈表改為單向循環(huán)鏈表，可用語句 p-next=head;。4. 要在一個單向鏈表

26、中p所指向的結(jié)點(diǎn)之后插入一個s所指向的新結(jié)點(diǎn)，若鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext,可執(zhí)行 _ s-next= p-next :禾口 p-next=s;的操作。5. 設(shè)有一個單向循環(huán)鏈表，頭指針為head，鏈表中結(jié)點(diǎn)的指針域?yàn)閚ext, p指向尾結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若要刪除尾結(jié)點(diǎn)，得到一個新的單向循環(huán)鏈表，可執(zhí)行操作_ p-next=head ;。6. 設(shè)有一個非空的鏈棧，棧頂指針為hs,要進(jìn)行出棧操作，用x保存出棧結(jié)點(diǎn)的值，棧結(jié)點(diǎn)的指針域?yàn)閚ext，則可執(zhí)行 x=hs-data;hs=hs-next;。7. 在一個鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的指針域?yàn)閚ext，則插入一個s所指結(jié)點(diǎn)的

27、操作 為 _ r-next=s _ ; r=s;&在一個不帶頭結(jié)點(diǎn)的非空鏈隊(duì)中，f和r分別為隊(duì)頭和隊(duì)尾指針，隊(duì)結(jié)點(diǎn)的數(shù)據(jù)域?yàn)閐ata,指針域?yàn)閚ext,若要進(jìn)行出隊(duì)操作，并用變量x存放出隊(duì)元素的數(shù)據(jù)值，則相關(guān)操作為x=f-data; f=f-n ext;。9.循環(huán)隊(duì)列的隊(duì)頭指針為f,隊(duì)尾指針為r，當(dāng)_ r= =f _時表明隊(duì)列為空。10循環(huán)隊(duì)列的最大存儲空間為MaxSize=8，采用少用一個元素空間以有效的判斷棧空或棧滿，若隊(duì)頭指針front=4，則當(dāng)隊(duì)尾指針rear= 4時，隊(duì)列為空，當(dāng)rear= 2 時，隊(duì)列有6個元素。11稀疏矩陣存儲時，采用一個由行號_ 、列號_、_非零元_ 3部分信息

28、組成的三元組唯一確定矩陣中的一個非零元素。12. 一棵二叉樹沒有單分支結(jié)點(diǎn)，有6個葉結(jié)點(diǎn)，則該樹總共有 _生_個結(jié)點(diǎn)。13. 一棵二叉樹順序編號為 6的結(jié)點(diǎn)（樹中各結(jié)點(diǎn)的編號與等深度的完全二叉樹中對應(yīng)位置上結(jié)點(diǎn)的編號相同），若它存在右孩子，則右孩子的編號為 13。14按照二叉樹的遞歸定義，對二叉樹遍歷的常用算法有亠先序_、_中序 _、后序一三種。15結(jié)構(gòu)中的數(shù)據(jù)元素存在多對多的關(guān)系稱為圖狀 結(jié)構(gòu)。_樹形_ _纟吉構(gòu)。gdbeihfca16把數(shù)據(jù)存儲到計(jì)算機(jī)中，并具體體現(xiàn)數(shù)據(jù)之間的邏輯結(jié)構(gòu)稱為物理（存儲） 結(jié)構(gòu)。17結(jié)構(gòu)中的數(shù)據(jù)元素存在一對多的關(guān)系稱為18如圖3所示的二叉樹，其后序遍歷序列為gh

29、19.如圖4所示的二叉樹，其前序遍歷序列為20.二叉樹為二叉排序的充分必要條件是其任一結(jié)點(diǎn)的值均大于其左孩子的值、小于其右孩子的值。這種說法是._錯誤_的。（回答正確或不正確）尾 指針的值增1，當(dāng)刪除一個元素隊(duì)列廣度優(yōu)先兩種方法。21在隊(duì)列的順序存儲結(jié)構(gòu)中，當(dāng)插入一個新的隊(duì)列元素時, 時， 頭 指針的值增1。22根據(jù)搜索方法的不同，圖的遍歷有深度優(yōu)先23循環(huán)隊(duì)列的引入，目的是為了克服假上溢24通常可以把某城市中各公交站點(diǎn)間的線路圖抽象成-圖狀_ _結(jié)構(gòu)。25. 結(jié)構(gòu)中的元素之間存在多對多的關(guān)系稱為一圖狀_結(jié)構(gòu)。26. 要在一個單向鏈表中刪除p所指向的結(jié)點(diǎn)，已知q指向p所指結(jié)點(diǎn)的直接前驅(qū)結(jié)點(diǎn)，若

30、鏈表中結(jié)點(diǎn)的指針域?yàn)?next，則可執(zhí)行q_next= p_next ;27. 設(shè)有一個單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，頭指針為head，指針p指向表中某結(jié)點(diǎn)，若邏輯表達(dá)式p-n ext=head;的結(jié)果為真，貝U p所指結(jié)點(diǎn)為尾結(jié)點(diǎn)。28. 設(shè)有一個鏈棧，棧頂指針為hs,現(xiàn)有一個s所指向的結(jié)點(diǎn)要入棧，則可執(zhí)行操作_ s-next=hs;和hs=s;29. 順序存儲字符串“ ABCD ”需要占用 _5=個字節(jié)。30. 循環(huán)隊(duì)列的最大存儲空間為MaxSize=6，采用少用一個元素空間以有效地判斷?？栈驐M，若隊(duì)頭指針front=4，當(dāng)隊(duì)尾指針rear= 3時隊(duì)滿，隊(duì)列中共有 5個元素。31

31、. 一棵二叉樹葉結(jié)點(diǎn)（終端結(jié)點(diǎn)）數(shù)為 5,單分支結(jié)點(diǎn)數(shù)為 2,該樹共有11 個結(jié)點(diǎn)32. 設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點(diǎn)的編號為奇數(shù)，該葉節(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為10,該完全二叉樹一共有 21=_個結(jié)點(diǎn)。33棵二叉樹中順序編號為5的結(jié)點(diǎn)（樹中各結(jié)點(diǎn)的編號與等深度的完全二叉中對應(yīng)位置上結(jié)點(diǎn)的編號相同），若它存在左孩子，則左孩子的編號為_ 10.34 結(jié)構(gòu)中的數(shù)據(jù)元素存在一對一的關(guān)系稱為線性結(jié)構(gòu)。35.棵有n個葉結(jié)點(diǎn)的二叉樹，其每一個非葉結(jié)點(diǎn)的度數(shù)都為2，則該樹共有2n-1個結(jié)點(diǎn)。36 圖的深度優(yōu)先搜索和廣度優(yōu)先搜索序列不一定是唯一的。此斷言是正確 的。（回答正確或不正確）37. 串的兩

32、種最基本的存儲方式分別是順序存儲和鏈?zhǔn)酱鎯?8. 按某關(guān)鍵字對記錄序列排序，若關(guān)鍵字關(guān)鍵字相等的記錄的記錄在排序前和排序后仍保持它們的前后關(guān)系，則排序算法是穩(wěn)定的，否則是不穩(wěn)定的。39. 設(shè)有一個不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，結(jié)點(diǎn)的指針域?yàn)閚ext，指針p指向尾結(jié)點(diǎn)，現(xiàn)要使 p指向第一個結(jié)點(diǎn)，可用語句 p=p_next;_40. 要在一個帶頭結(jié)點(diǎn)的單向循環(huán)鏈表中刪除頭結(jié)點(diǎn)，得到一個新的不帶頭結(jié)點(diǎn)的單向循環(huán)鏈表，若結(jié)點(diǎn)的指針域?yàn)?next，頭指針為 head,尾指針為 p,則可執(zhí)行 head=head- next;p-next=head ; _41. 在雙向鏈表中，每個結(jié)點(diǎn)有兩個指針域，一個指向 結(jié)

33、點(diǎn)的直接后繼，另一個指向結(jié)點(diǎn)的直接前驅(qū)42 .設(shè)有一個頭指針為head的單向鏈表，p指向表中某一個結(jié)點(diǎn)，且有p-next= =NULL,通過操作 p-next=head; _，就可使該單向鏈表構(gòu)造成單向循環(huán)鏈表。43.循環(huán)隊(duì)列的最大存儲空間為MaxSize，隊(duì)頭指針為f，隊(duì)尾指針為r，當(dāng)_ （r+1） %MaxSize=f _時表明隊(duì)列已滿。44 .從一個棧頂指針為h的鏈棧中刪除一個結(jié)點(diǎn)時，用x保存被刪結(jié)點(diǎn)的值，可執(zhí)行 x=h-data;和h=h-next; （結(jié)點(diǎn)的指針域?yàn)?next）45. 程序段 int count=0;char *s= ABCD ”；while（*s!= 0 s+;co

34、u nt+;執(zhí)行后 count= _ 4_46. 兩個串相等的充分必要條件是_47. 棵二叉樹總結(jié)點(diǎn)數(shù)為11，葉結(jié)點(diǎn)數(shù)為5,該樹有_4_個雙分支結(jié)點(diǎn)，_2_個單分支結(jié)點(diǎn)。48. 對二叉樹的遍歷可分為一先序、中序、后序、層次四種不同的遍歷次序。49. 設(shè)一棵完全二叉樹，其最高層上最右邊的葉結(jié)點(diǎn)的編號為偶數(shù)，該葉節(jié)點(diǎn)的雙親結(jié)點(diǎn)的編號為9，該完全二叉樹一共有 18個結(jié)點(diǎn)。50. 雙向循環(huán)鏈表中，p指向表中某結(jié)點(diǎn)，則通過 p可以訪問到p所指結(jié)點(diǎn)的直接后繼結(jié)點(diǎn)和直接前驅(qū)結(jié)這種說法是正確51 .52.53.折半查找只適用于順序存儲結(jié)構(gòu)存儲的有序表。的(回答正確或不正確)。54.55.哈希函數(shù)是記錄關(guān)鍵字值

35、與該記錄存儲地址之間所構(gòu)造的對應(yīng)關(guān)系。56.深度為k的二叉樹最多有2k-1結(jié)點(diǎn)。57.二叉樹排序中任一棵子樹都是二叉排序樹，這種說法是正確的。(回答正確或不正確)58.串的兩種最基本的存儲方式是順序存儲和鏈?zhǔn)酱鎯?9.結(jié)構(gòu)中的元素之間存在多對多的關(guān)系稱為圖狀結(jié)構(gòu)。60.設(shè)有一個鏈棧，棧頂指針為hs,現(xiàn)有一個s所指向的結(jié)點(diǎn)要入棧，則可執(zhí)行操作s- next=hs; _ hs=s; _。61.循環(huán)隊(duì)列的最大存儲空間為MaxSize=6，采用少用一個元素空間以有效地判斷?？栈驐M，若隊(duì)頭指針front=4 ,當(dāng)隊(duì)尾指針rear= _3_時隊(duì)滿，隊(duì)列中共有5_個元素。62. A 在存儲時占1個字節(jié)?！?/p>

36、A”在存儲時占 2個字節(jié)。63.程序段 char *s= aBcD ”;n=0;while(*s!= 0 if(*s = a&*s = z n+; s+;執(zhí)行后n= _2 一三、綜合題1. (1)已知某二叉樹的后序遍歷序列是debca，中序遍歷序列是 dbeac,試畫出該二叉樹(2)若上述二叉樹的各個結(jié)點(diǎn)的字符分別代表不同的整數(shù)(其中沒有相等的)，并恰好使該樹成為棵二叉排序樹，試給出a、b、c、d、e的大小關(guān)系(3)給出該樹的前序遍歷序列答: (1)(2) dbean ext=s; s-n ext=p-n ext;這樣做正確嗎？若正確則回答正確，若不正確則說明應(yīng)如何改寫答：(1) pi-nex

37、t= head2； P2-next= headi；(2) 不對，s-next= p-next ； p-next=s ；3. (i)設(shè)有一個整數(shù)序列40, 28, 6, 72, I00, 3, 54依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹(2)對上述二叉排序樹，在等概率條件下，求成功查找的平均查找長度答：(1)(2) ASL= (1x1+2x2+3x3+4 ) /7=18/74. (1)畫出對長度為10的有序表進(jìn)行折半查找的判定樹(以序號1, 2,10表示樹結(jié)點(diǎn))(2)對上述序列進(jìn)行折半查找，求等概率條件下，成功查找的平均查找長度35 40 6543 35 9540 43 45 65 35 95(

38、2) ASL= (1x1+2x2+3x4+4x3 ) /10=29/105. (1)利用篩選過程把序列 42 , 82, 67, 102, 16, 32, 57,52建成堆（小根堆），畫出相應(yīng)的完全二叉樹（不要求中間過程）42, 82,16, 67, 32, 57答:(2) 102， 52,6. ( 1)利用篩選法，把序列 37 , 77, 62, 97, 11, 27, 52,47建成堆（小根堆），畫出相應(yīng)的完全二叉樹（2）寫出對上述堆所對應(yīng)的二叉樹進(jìn)行前序遍歷得到的序列7. （1） 一組記錄的關(guān)鍵字序列為45 , 40, 65, 43, 35, 95寫出利用快速排序的方法，以第一個記錄為基

39、準(zhǔn)得到的一趟劃分的結(jié)果（要求給出一趟劃分中每次掃描和交換的結(jié)果）（2）同樣對序列45 , 40, 65, 43, 35, 95利用直接插入排序，寫出逐次插入過程（從第一個元素一直到第六個元素）35 40 6543659535 40 43 45 65 9535 40 43 43 65 95&設(shè)有一個不帶頭結(jié)點(diǎn)的單向鏈表，頭指針為head，結(jié)點(diǎn)類型為 NODE，每個結(jié)點(diǎn)包含一個數(shù)據(jù)域data和一個指針域next，該鏈表有兩個結(jié)點(diǎn)，p指向第二個結(jié)點(diǎn)（尾結(jié)點(diǎn)），按以下要求寫出相應(yīng) 語句（不要求完整程序，（1）、（ 2）、（ 3）、（ 4）是一個連續(xù)的過程）。（1） 新開辟一個結(jié)點(diǎn)，使指針s指向該結(jié)點(diǎn)，

40、結(jié)點(diǎn)的數(shù)據(jù)成員data賦值為1（2） 把該結(jié)點(diǎn)插入鏈表的尾部，釋放指針s的指向（3）刪除鏈表的第一個結(jié)點(diǎn)（4）已知p1指向另一個新結(jié)點(diǎn)，把它插入到p所指結(jié)點(diǎn)和尾結(jié)點(diǎn)之間答：（1） s=（ NODE* ） malloc（sizeof（NODE）;s-data=1;(2) p_next=s;s-next= NULL ；free(s)(3) head = head -next ；(4) P2next= p-next ；p_n ext=p 1；9. （1）利用篩選過程把序列42 , 82, 67, 102, 16, 32,57, 52建成堆（小根堆），畫出相應(yīng)的完全二叉樹（不要求中間過程）（2 ）寫出

41、對上述堆對應(yīng)的完全二叉樹進(jìn)行中序遍歷得到的序列答:初始樹(2) 102, 52, 42, 82, 16, 67, 32, 57中序遍歷：中序2, 3, 4, 5, 6, 7, 14, 16, 18判定樹(以序列中的元素作為樹的結(jié)點(diǎn))(2)為了成功查找到 100需要進(jìn)行多少次元素間的比較？為了查找9，經(jīng)過多少次元素間的比較可知道查找失敗？(2)4次；3次11.找15，經(jīng)多少次元素間的比較可知道查找失敗。答:(2)三次；四次(1)設(shè)有一個整數(shù)序列50 , 38, 16, 82, 110, 13, 64，依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹(2)利用上述二叉排序樹，為了查找110,經(jīng)多少次元素間的

42、比較能成功查到，為了查12.(1)設(shè)有查找表5,14,2,6,18,7,4,16,3,依次取表中數(shù)據(jù)，構(gòu)造一棵二叉排序樹。(2)說明如何由序列的二叉排序樹得到相應(yīng)序列的排序結(jié)果，對上述二叉排序給出中序遍歷的結(jié)果。答：14181613. (1)已知某二叉樹的先序遍歷序列是aecdb,中序遍歷序列是 eadcb,試畫出該二叉樹(2)給出上述二叉樹的后序遍歷序列(3)若上述二叉樹的各個結(jié)點(diǎn)的字符分別是1, 2, 3, 4, 5，并恰好使該樹成為一棵二叉排序樹，試問a、b、c、d、e的值各為多少?答:(3) e=1,a=2,d=3,c=4,b=5 14. (1)設(shè)有一個整數(shù)序列40, 28, 6, 7

43、2, 100, 3, 54依次取出序列中的數(shù)，構(gòu)造一棵二叉排序樹(2)對上述二叉排序樹，在等概率條件下，求成功查找的平均查找長度答：(1)(2) ASL=15. (1)給定數(shù)列8 ,17, 5, 9, 21, 10, 7, 19, 6，依次取序列中的數(shù)構(gòu)造一棵二叉排序樹(2)對上述二叉樹給出中序遍歷得到的序列答:(2) 5, 6, 7 8, 9, 10, 17, 18, 19, 2116. (1)利用篩選過程把序列 42 , 82, 67, 102, 16, 32,57,52建成堆（小根堆），畫出相應(yīng)的完全二叉樹（不要求中間過程）(2)寫出對上述堆對應(yīng)的完全二叉樹進(jìn)行中序遍歷得到的序列答:(1

44、)426782102, 52, 42,17.( 1)3257以給定權(quán)重值1, 2,3242575282, 16, 67, 32, 5712,102I6713, 20, 25為葉結(jié)點(diǎn)，建立一棵哈夫曼樹(2)權(quán)重值建立的棵哈夫曼樹是否一定唯一答:若哈夫曼樹有 n個非葉子結(jié)點(diǎn)，則樹中共有多少結(jié)點(diǎn)。對給定的一組（2） 2n-1 不一定唯一四、程序填空題1.以下函數(shù)在a0到an-1中，用折半查找算法查找關(guān)鍵字等于k的記錄，查找成功返回該記錄的下標(biāo),失敗時返回-1，完成程序中的空格typedef struct int key;NODE;int Binary_Search(NODE a,int n, int k)int low,mid,high;low=0;