電大數(shù)據(jù)結(jié)構(gòu)（本）選擇題 精篇復(fù)習(xí)資料

1、一、單項選擇題(每小題2分，共30分)1.非空的單向循環(huán)鏈表的尾結(jié)點滿足(c)(設(shè)頭指針為head，指針p指向尾結(jié)點)。a.p-next=nullb.p=nullc.p-next=headd.p=head2.一種邏輯結(jié)構(gòu)(a)。a.可以有不同的存儲結(jié)構(gòu)b.只能有唯一的存儲結(jié)構(gòu)c.是指某一種數(shù)據(jù)元素之間的存儲關(guān)系d.以上三種說法均不正確3.把數(shù)據(jù)存儲到計算機中，并具體體現(xiàn)數(shù)據(jù)元素間的邏輯結(jié)構(gòu)稱為(a)。a.物理結(jié)構(gòu)b.邏輯結(jié)構(gòu)c.算法的具體實現(xiàn)d.給相關(guān)變量分配存儲單元4.在一個單鏈表中p所指結(jié)點之后插人一個s所指的結(jié)點時，可執(zhí)行(d)。 a.p-next=s;s-next=p-next b.p

2、-next=s-next c.p=s-next d.s-next=p-next;p-next=s5.在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則插入s所指結(jié)點的運算為(b)a.f-next=s;f=sb.r-next=s;r=sc.s-next=r;r=sd.s-next=f;f=s6. 元素1,3,5,7按順序依次進(jìn)棧，則該棧的不可能輸出序列是(c)(進(jìn)棧出?？梢越惶孢M(jìn)行)。a.7,5,3,1 b.1,3,5,7 c.7,5,1,3 d.3,1,7,57.設(shè)有一個20階的對稱矩陣a，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組b中(數(shù)組下標(biāo)從1開始)，則矩陣中元素a9,2

3、在一維數(shù)組b中的下標(biāo)是(d)。a.41 b.32 c.18 d.388.設(shè)有兩個串p和q，求q在p中首次出現(xiàn)的位置的運算稱作(d)。a.連接 b.求子串 c.求串長 d.模式匹配9.在一棵二叉樹中，若編號為i的結(jié)點存在左孩子，則左孩子的順序編號為(a)。a.2i b.21一1 c.2i十1 d.2i十210.設(shè)一棵有n個葉結(jié)點的二叉樹，除葉結(jié)點外每個結(jié)點度數(shù)都為2，則該樹共有(d)個結(jié)點。a.2n b.2n十1 c.2n+2 d.2n一111.已知如圖1所示的一個圖，若從頂點a出發(fā)，按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點序列為(d)。 a.abecdf b.acfebd c.aebcf

4、d d.aedfcb12.線性表以(a)方式存儲，能進(jìn)行折半查找。a.關(guān)鍵字有序的順序 b.順序c.鏈接 d.二插樹13.有一個長度為12的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為(d)。a.35/12b.39/12c.41/12d.37/1214.設(shè)已有m個元素有序，在未排好序的序列中挑選第m+1個元素，并且只經(jīng)過一次元素的交換就使第m+1個元素排序到位，該方法是(d)。a.折半排序b.冒泡排序c.歸并排序d.簡單選擇排序15.一組記錄的關(guān)鍵字序列為(47,80,57,39,41,46)，利用堆排序(堆頂元素是最小元素)的方法建立的初始堆為(a)。a.39,4

5、1,46,80,47,57b.39,47,46,80,41,57c.41,39,46,47,57,80d.39,80,46,47,41,571.鏈表所具備的特點是(c)。 a.可以隨機訪問任一結(jié)點 b.占用連續(xù)的存儲空間 c.插人刪除元素的操作不需要移動元素結(jié)點 d.可以通過下標(biāo)對鏈表進(jìn)行直接訪問2.線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在(a)的關(guān)系。 a.一對一 b.一對多 c.多對多d.每一個元素 都有一個直接前驅(qū)和一個直接后繼3.算法的時間復(fù)雜度與(c)有關(guān)。 a.所使用的計算機 b.與計算機的操作系統(tǒng) c.與算法本身 d.與數(shù)據(jù)結(jié)構(gòu)4.在一個單鏈表中，p,q分別指向表中兩個相鄰的結(jié)點，且q所

6、指結(jié)點是p所指結(jié)點的直接后繼，現(xiàn)要刪除q所指結(jié)點，可用的語句是(c)。 a.p=q-next b.p-next=q c.p-next=q-next d.q-next=null5. 在一個鏈隊中，假設(shè)f和r分別為隊頭和隊尾指針，則刪除一個結(jié)點的運算為(c) a.r=f-next; b.r=r-next; c.f=f-next; d.f=r-next;6. 元素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,67.設(shè)有一個10階的對稱矩陣a，采用壓縮存儲的方式，將其下三角部分以行序為主存儲到一維數(shù)

7、組b中(數(shù)組下標(biāo)從1開始)，則矩陣中元素a8,5在一維數(shù)組b中的下標(biāo)是(a)a.33 b.32 c.85 d.418.在c語言中，順序存儲長度為3的字符串，需要占用(a)個字節(jié)。a.4 b. 3 c.6 d. 129一棵有n個結(jié)點采用鏈?zhǔn)酱鎯Φ亩鏄渲校灿?a)個指針域為空。a. n+1 b. n c. n-1 d. n-210.設(shè)一棵哈夫曼樹共有n個葉結(jié)點，則該樹有(a)個非葉結(jié)點。a.n-1 b. n c. n+1 d.2n11.在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的(d)倍 a.3 b.2.5 c.1.5 d.212. 已知如圖所示的一個圖，若從頂點v，出發(fā)，按廣度優(yōu)先進(jìn)行遍歷，

8、則可能得到的一種頂點序列為(c)。 a.v1v2v3v6v7v4v5v8 b.v1v2v3v4v5v8v6v7 c.v1v2v3v4v5v6v7v8 d.v1v2v3v4v8v5v6v713.在有序表2,4,7,14,34,43,47,64,75,80,90,97,120中，用折半查找法查找值80時，經(jīng)(a)次比較后查找成功。 a.4 b. 2 c. 3 d. 514.排序算法中，從未排序序列中依次取出元素與已排序序列(初始為空)中的元素進(jìn)行比較(要求比較次數(shù)盡量少)，然后將其放入已排序序列的正確位置的方法是(c)。 a.冒泡 b.直接插入 c.折半插入 d.選擇排序15.排序方法中，從尚未排

9、序序列中挑選元素，并將其依次放入已排序序列(初始為空)的一端的方法，稱為(d)排序。 a.歸并 b.插人c.快速 d.選擇1.針對線性表，在存儲后如果最常用的操作是取第i個結(jié)點及其前驅(qū)，則采用(d)存儲方式最節(jié)省時間。 a.單鏈表 b.雙鏈表c.單循環(huán)鏈表 d.順序表2.數(shù)據(jù)結(jié)構(gòu)中，與所使用的計算機無關(guān)的是數(shù)據(jù)的(d)結(jié)構(gòu)。 a.物理 b.存儲c.邏輯與物理d.邏輯3.以下特征中，(d)不是算法的特性。a.有窮性 c.可行性b.確定性 d.有0個或多個輸出4.設(shè)有一個長度為n的順序表，要在第i個元素之前(也就是插人元素作為新表的第個元素)，則移動元素個數(shù)為(a)。 a. n-i+1 b. n-

10、i c. n-i-1 d.i5.棧的插人刪除操作在(d)進(jìn)行。 a.棧底 b.任意位置 c.指定位置 d.棧頂6.以下說法正確的是(c)。 a.棧的特點是先進(jìn)先出，隊列的特點是先進(jìn)后出 b.棧和隊列的特點都是先進(jìn)后出 c.棧的特點是先進(jìn)后出，隊列的特點是先進(jìn)先 出 d.棧和隊列的特點都是先進(jìn)先出8.設(shè)有一個15階的對稱矩陣a，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組b中(數(shù)組下標(biāo)從1開始)，則矩陣中元素a7,6。在一維數(shù)組b中的下標(biāo)是(c)。 a.42 b. 13 c.27 d. 329.串函數(shù)strcmp (d,d)的值(b)。 a. 0 b. 1 c.-1 d. 310

11、.在一棵二叉樹中，若編號為i的結(jié)點存在右孩子，則右孩子的順序編號為(d) a. 2i b. 2i-1 c. 2i+2 d. 2i+111.設(shè)一棵有n個葉結(jié)點采用鏈?zhǔn)酱鎯Φ亩鏄?，除葉結(jié)點外每個結(jié)點度數(shù)都為2，則該樹共有(d)個指針域為空。 a. 2n b. 2n+ l c. 2n+2 d. n+ l12.已知如圖1所示的一個圖，若從頂點a出發(fā)，按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的一種頂點序列為(b)。 a.abeedfb. abeefdc. aebefdd. acfdeb 13.在有序表1,3,8,13,33,42,46,63,76,78,86,97,100中，用折半查找值86時，經(jīng)(d)次

12、比較后查找成功。 a.6 b. 3 c.8 d. 4 14.有一個長度為10的有序表，按折半查找對該表進(jìn)行查找，在等概率情況下查找成功的平均比較次數(shù)為(a)。 a. 29/10 b. 31/10 c.26/10 d. 29/9 15.一組記錄的關(guān)鍵字序列為(37,70,47,29,31,85)，利用快速排序，以第一個關(guān)鍵字為分割元素，經(jīng)過一次劃分后結(jié)果為(a)。 a. 31,29,37,47,70,85 b. 29,31,37,47,70,85 c. 31,29,37,70,47,85 d. 31,29,37,85,47,702.以下說法中不正確的是(b)。 a.雙向循環(huán)鏈表中每個結(jié)點需要包含

13、兩個指針域 b.已知單向鏈表中任一結(jié)點的指針就能訪問到鏈表中每個結(jié)點 c.順序存儲的線性鏈表是可以隨機訪問的 d.單向循環(huán)鏈表中尾結(jié)點的指針域中存放的是頭指針3.雙向循環(huán)鏈表結(jié)點的數(shù)據(jù)類型為: struct node int data; struct node *next;/*指向直接后繼*/ struct node *prior; ; 設(shè)p指向表中某一結(jié)點，要顯示p所指結(jié)點的直接前驅(qū)結(jié)點的數(shù)據(jù)元素，可用操作(b)a. printf(%d,p-next-data);b. printf(%d,p-prior-data);c. printf(%d,p-prior-next);d. printf(%

14、d,p-data);5.設(shè)top是一個鏈棧的棧頂指針，棧中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成,設(shè)用x接收棧頂元素，則取棧頂元素的操作為(c)a.top-data= x; b.top= top-next;c.x=top-data;d.x=top-data; top= top-next;6.以下說法不正確的是(c)。 a.棧的特點是后進(jìn)先出b.隊列的特點是先進(jìn)先出c.棧的刪除操作在棧底進(jìn)行，插人操作在棧頂進(jìn)行 d.隊列的插入操作在隊尾進(jìn)行，刪除操作在隊頭進(jìn)行7. char *p; p= strcat (abd,abc); printf(%s, p); 的顯示結(jié)果為(b)。 a.-1

15、b. abdabc c.ab d. 18. 深度為5的滿二叉樹至多有(b)個結(jié)點(根結(jié)點為第一層)。 a. 40 b. 31 c. 34 d.359.已知一個圖的所有頂點的度數(shù)之和為m，則該圖的邊數(shù)為(d)。 a. 2m b.m c. 2m+1 d. m/210.以下說法不正確的是(a)。 a.連通圖g的生成樹一定是唯一的 b.連通圖g一定存在生成樹 c.連通圖g的生成樹中一定要包含g的所有頂點 d.連通圖g的生成樹一定是連通而且不包含回路11.有序表為1,2,4,6,10,18,20,32，用課本中折半查找算法查找值18，經(jīng)(b)次比較后成功查到。 a.3 b.2 c.4 d.512.在排序

16、過程中，可以通過某一趟排序的相關(guān)操作所提供的信息，判斷序列是否已經(jīng)排好序，從而可以提前結(jié)束排序過程的排序算法是(a)。 a.冒泡b.選擇c.直接插入 d.折半插入13.用折半查找法，對長度為12的有序的線性表進(jìn)行查找，最壞情況下要進(jìn)行(a)次元素間的比較。 a. 4 b. 3 c.5 d. 614.如圖若從頂點a出發(fā)按深度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的頂點序列為(b) a.acfgedb b.aedbgfcc.acfebdg d.aecbdgf15.一棵哈夫曼樹總共有25個結(jié)點，該樹共有(a)個非葉結(jié)點(非終端結(jié)點)。 a.12 b. 13 c.14 d.151.從n個數(shù)中選取最大元素(c)

17、。a.基本操作是數(shù)據(jù)元素間的交換b.算法的時間復(fù)雜度是o(n2)c.算法的時間復(fù)雜度是o(n)d.需要進(jìn)行(n十1)次數(shù)據(jù)元素間的比較2.設(shè)head為非空的單向循環(huán)鏈表頭指針，p指向鏈表的尾結(jié)點,則滿足邏輯表達(dá)式(d)的值為真。a. p-next=null b. p=nullc. p-next=head d. p-next = head3.設(shè)順序存儲的線性表長度為n，要刪除第i個元素,按課本的算法,當(dāng)i =(c)時,移動元素的次數(shù)為3。a. 3 b. n/2 c. n-3 d. 35. 設(shè)有一個帶頭結(jié)點的鏈隊列，隊列中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，front和rear分別為

18、鏈隊列的頭指針和尾指針，要執(zhí)行出隊操作，用x保存出隊元素的值，p為指向結(jié)點類型的指針，可執(zhí)行如下操作:p=front-next; x=p-data;然后執(zhí)行(b)。a. front=p-next; b. front -next=p-next;c. front=p; d. front-next =p;6. 在c語言中，存儲字符串a(chǎn)bcd需要占用(c)字節(jié)。a. 4 b. 2 c. 5 d. 37.設(shè)有一個10階的對稱矩陣a，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中。(矩陣a的第一個元素為al,1 ，數(shù)組b的下標(biāo)從1 開始) ，則矩陣元素a5,3對應(yīng)一維數(shù)組b的數(shù)組元素是(c)

19、。a. b18 b. b8 c. b13 d. b108.深度為5的完全二叉樹共有20個結(jié)點，則第5層上有(c)個結(jié)點。(根所在層為第一層)a. 3 b. 8 c. 5 d. 69.巳知一個圖的所有頂點的度數(shù)之和為m，且m是以下4種情況之一，則m只可能是(d)a. 9 b. 7 c. 15 d. 810.線性表只要以(c)方式存儲就能進(jìn)行折半查找。a.鏈接 b.順序c.關(guān)鍵字有序的順序d.二叉樹11.對n個元素進(jìn)行冒泡排序若某趟冒泡中只進(jìn)行了(c)次元素間的交換則表明序列已經(jīng)排好序。a. 1 b. 2 c. 0 d. n-112.在對一組元素(64,48,106,33,25,82,70,55,

20、93)進(jìn)行直接插入排序時,當(dāng)進(jìn)行到要把第7個元素70插入到已經(jīng)排好序的子表時，為找到插入位置，需進(jìn)行(c)次元素間的比較(指由小到大排序)。a. 6 b. 2 c. 3 d. 413.如圖，若從頂點a出發(fā)按廣度優(yōu)先搜索法進(jìn)行遍歷，則可能得到的頂點序列為(b)。a. acebdgfb. abecdgfc. acfedgbd. abecfdg14.一棵哈夫曼樹有10個非葉子結(jié)點(非終端結(jié)點), 該樹總共有(a)個結(jié)點。a. 21 b. 20 c. 22 d. 191.數(shù)據(jù)元素是數(shù)據(jù)的基本單位,它(c)。a.只能有一個數(shù)據(jù)項組成b.至少有二個數(shù)據(jù)項組成c.可以是一個數(shù)據(jù)項也可以由若干個數(shù)據(jù)項組成d.

21、至少有一個數(shù)據(jù)項為指針類型2.線性表的順序結(jié)構(gòu)中,(c)。a.邏輯上相鄰的元素在物理位置上不一定相鄰b.數(shù)據(jù)元素是不能隨機訪問的c.邏輯上相鄰的元素在物理位置上也相鄰d.進(jìn)行數(shù)據(jù)元素的插入、刪除效率較高3.以下表中可以隨機訪問的是(d)。a.單向鏈表b.雙向鏈表c.單向循環(huán)鏈表d.順序表4.設(shè)順序存儲的線性表長度為n,對于刪除操作,設(shè)刪除位置是等概率的,則刪除一個元素平均移動元素的次數(shù)為(a)。a.(n+1)/2 c.2n b.n d.n-i5.設(shè)top是一個鏈錢的棧頂指針,戰(zhàn)中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成,設(shè)用x接收錢頂元素,則出戰(zhàn)操作為(a)。a.x=top-data;

22、top=top-next;b.top=top-next;x=top-data;c.x=top-next;top=top-data;d.top-next=top;x=top-data;6.以下說法正確的是(c)。a.隊列是后進(jìn)先出b.棧的特點是后進(jìn)后出c.棧的刪除和插人操作都只能在棧頂進(jìn)行d.隊列的刪除和插入操作都只能在隊頭進(jìn)行7.串函數(shù)strcmp(b,cd)的值為(d)。a.1 b.0 c.bcd d.-18.設(shè)有一個12階的對稱矩陣a,采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中(矩陣a的第一個元素為a1,1,數(shù)組b的下標(biāo)從1開始),則矩陣a中第4行的元素在數(shù)組b中的下標(biāo)i一定有(a)。a7=i=10b.11=i=15c.9=i=14d.6=ine