電大數(shù)據(jù)結(jié)構(gòu)歷年試題匯編選擇題

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->

2、;next=p->next B.p->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按順序依次進棧，則該棧的不可能輸出序列是(C)(進棧出?？梢越惶孢M行)。A.7,5,3,1 B.1,3,5,7 C.7,5,1,3 D.3,1,7,57.設(shè)有一個20階

3、的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中(數(shù)組下標從1開始)，則矩陣中元素A9,2在一維數(shù)組B中的下標是(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所示的一個圖，若從頂點

4、a出發(fā)，按深度優(yōu)先搜索法進行遍歷，則可能得到的一種頂點序列為(D)。 A.abecdf B.acfebd C.aebcfd D.aedfcb12.線性表以(A)方式存儲，能進行折半查找。A.關(guān)鍵字有序的順序 B.順序C.鏈接 D.二插樹13.有一個長度為12的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(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)鍵

5、字序列為(47,80,57,39,41,46)，利用堆排序(堆頂元素是最小元素)的方法建立的初始堆為(A)。A.39,41,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.可以通過下標對鏈表進行直接訪問2.線性結(jié)構(gòu)中數(shù)據(jù)元素的位置之間存在(A)的關(guān)系。 A.一對一 B.一對多 C.多對多D.每一個元素 都有一個直接前驅(qū)和一個直接后繼3.算法的時間復雜度與(C)有關(guān)。 A.所使用的計

6、算機 B.與計算機的操作系統(tǒng) C.與算法本身 D.與數(shù)據(jù)結(jié)構(gòu)4.在一個單鏈表中，p,q分別指向表中兩個相鄰的結(jié)點，且q所指結(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按順序依次進棧，則該棧的不可能輸出序列

7、是(B)(進棧出?？梢越惶孢M行) A. 9,6,3 B. 9,3,6 C. 6,3,9 D. 3,9,67.設(shè)有一個10階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主存儲到一維數(shù)組B中(數(shù)組下標從1開始)，則矩陣中元素A8,5在一維數(shù)組B中的下標是(A)A.33 B.32 C.85 D.418.在C語言中，順序存儲長度為3的字符串，需要占用(A)個字節(jié)。A.4 B. 3 C.6 D. 129一棵有n個結(jié)點采用鏈式存儲的二叉樹中，共有(A)個指針域為空。A. n+1 B. n C. n-1 D. n-210.設(shè)一棵哈夫曼樹共有n個葉結(jié)點，則該樹有(A)個非葉結(jié)點。A.n-1 B.

8、n C. n+1 D.2n11.在一個無向圖中，所有頂點的度數(shù)之和等于邊數(shù)的(D)倍 A.3 C.1.5 D.212. 已知如圖所示的一個圖，若從頂點V，出發(fā)，按廣度優(yōu)先進行遍歷，則可能得到的一種頂點序列為(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.排序算法中，從未排序序列中依次取出元素與已排序序

9、列(初始為空)中的元素進行比較(要求比較次數(shù)盡量少)，然后將其放入已排序序列的正確位置的方法是(C)。 A.冒泡 B.直接插入 C.折半插入 D.選擇排序15.排序方法中，從尚未排序序列中挑選元素，并將其依次放入已排序序列(初始為空)的一端的方法，稱為(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

10、.可行性B.確定性 D.有0個或多個輸出4.設(shè)有一個長度為n的順序表，要在第i個元素之前(也就是插人元素作為新表的第個元素)，則移動元素個數(shù)為(A)。 A. n-i+1 B. N-i C. n-i-1 D.i5.棧的插人刪除操作在(D)進行。 A.棧底 B.任意位置 C.指定位置 D.棧頂6.以下說法正確的是(C)。 A.棧的特點是先進先出，隊列的特點是先進后出 B.棧和隊列的特點都是先進后出 C.棧的特點是先進后出，隊列的特點是先進先 出 D.棧和隊列的特點都是先進先出8.設(shè)有一個15階的對稱矩陣A，采用壓縮存儲的方式，將其下三角部分以行序為主序存儲到一維數(shù)組B中(數(shù)組下標從1開始)，則矩陣

11、中元素a7,6。在一維數(shù)組B中的下標是(C)。 A.42 B. 13 C.27 D. 329.串函數(shù)StrCmp ("d","D")的值(B)。 A. 0 B. 1 C.-1 D. 310.在一棵二叉樹中，若編號為i的結(jié)點存在右孩子，則右孩子的順序編號為(D) A. 2i B. 2i-1 C. 2i+2 D. 2i+111.設(shè)一棵有n個葉結(jié)點采用鏈式存儲的二叉樹，除葉結(jié)點外每個結(jié)點度數(shù)都為2，則該樹共有(D)個指針域為空。 A. 2n B. 2n+ l C. 2n+2 D. n+ l 13.在有序表1,3,8,13,33,42,46,63,76,78,8

12、6,97,100中，用折半查找值86時，經(jīng)(D)次比較后查找成功。 A.6 B. 3 C.8 D. 4 14.有一個長度為10的有序表，按折半查找對該表進行查找，在等概率情況下查找成功的平均比較次數(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.以下說法中不正

13、確的是(B)。 A.雙向循環(huán)鏈表中每個結(jié)點需要包含兩個指針域 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&q

14、uot;,p->prior->data);C. printf("%d",p->prior->next);D. printf("%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.棧的特點是后進先出B.隊

15、列的特點是先進先出C.棧的刪除操作在棧底進行，插人操作在棧頂進行 D.隊列的插入操作在隊尾進行，刪除操作在隊頭進行7. char *p; p= StrCat ("ABD","ABC"); Printf("%s", p); 的顯示結(jié)果為(B)。 A.-1 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

16、)。 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.在排序過程中，可以通過某一趟排序的相關(guān)操作所提供的信息，判斷序列是否已經(jīng)排好序，從而可以提前結(jié)束排序過程的排序算法是(A)。 A.冒泡B.選擇C.直接插入 D.折半插入13.用折半查找法，對長度為12的有序的線性表進行查找，最壞情況下要進行(A)次元素間的比較。 A. 4 B. 3 C.5

17、D. 614.如圖若從頂點a出發(fā)按深度優(yōu)先搜索法進行遍歷，則可能得到的頂點序列為(B) A.acfgedb B.aedbgfcC.acfebdg D.aecbdgf15.一棵哈夫曼樹總共有25個結(jié)點，該樹共有(A)個非葉結(jié)點(非終端結(jié)點)。 A.12 B. 13 C.14 D.151.從n個數(shù)中選取最大元素(C)。A.基本操作是數(shù)據(jù)元素間的交換B.算法的時間復雜度是O(n2)C.算法的時間復雜度是O(n)D.需要進行(n十1)次數(shù)據(jù)元素間的比較2.設(shè)head為非空的單向循環(huán)鏈表頭指針，p指向鏈表的尾結(jié)點,則滿足邏輯表達式(D)的值為真。A. p->next=NULL B. p=NULLC

18、. p->next=head D. p->next = head3.設(shè)順序存儲的線性表長度為n，要刪除第i個元素,按課本的算法,當i =(C)時,移動元素的次數(shù)為3。A. 3 B. n/2 C. n-3 D. 35. 設(shè)有一個帶頭結(jié)點的鏈隊列，隊列中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成，front和rear分別為鏈隊列的頭指針和尾指針，要執(zhí)行出隊操作，用x保存出隊元素的值，p為指向結(jié)點類型的指針，可執(zhí)行如下操作:p=front->next; x=p->data;然后執(zhí)行(B)。A. front=p->next; B. front ->next=p

19、->next;C. front=p; D. Front->next =p;6. 在C語言中，存儲字符串"ABCD"需要占用(C)字節(jié)。A. 4 B. 2 C. 5 D. 37.設(shè)有一個10階的對稱矩陣A，采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中。(矩陣A的第一個元素為al,1 ，數(shù)組b的下標從1 開始) ，則矩陣元素a5,3對應(yīng)一維數(shù)組b的數(shù)組元素是(C)。A. b18 B. b8 C. b13 D. b108.深度為5的完全二叉樹共有20個結(jié)點，則第5層上有(C)個結(jié)點。(根所在層為第一層)A. 3 B. 8 C. 5 D. 69.巳知一個

20、圖的所有頂點的度數(shù)之和為m，且m是以下4種情況之一，則m只可能是(D)A. 9 B. 7 C. 15 D. 810.線性表只要以(C)方式存儲就能進行折半查找。A.鏈接 B.順序C.關(guān)鍵字有序的順序D.二叉樹11.對n個元素進行冒泡排序若某趟冒泡中只進行了(C)次元素間的交換則表明序列已經(jīng)排好序。A. 1 B. 2 C. 0 D. n-112.在對一組元素(64,48,106,33,25,82,70,55,93)進行直接插入排序時,當進行到要把第7個元素70插入到已經(jīng)排好序的子表時，為找到插入位置，需進行(C)次元素間的比較(指由小到大排序)。A. 6 B. 2 C. 3 D. 413.如圖，

21、若從頂點a出發(fā)按廣度優(yōu)先搜索法進行遍歷，則可能得到的頂點序列為(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.至少有一個數(shù)據(jù)項為指針類型2.線性表的順序結(jié)構(gòu)中,(C)。A.邏輯上相鄰的元素在物理位置上不一定相鄰B.數(shù)據(jù)元素是不能隨機訪問的C.邏輯上相鄰的元素在物理位置上也相鄰D.進行數(shù)據(jù)元素的插入、

22、刪除效率較高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;top=top->next;B.top=top->next;x=top->data;C.x=top->next;top=top->data;D.top-

23、>next=top;x=top->data;6.以下說法正確的是(C)。A.隊列是后進先出B.棧的特點是后進后出C.棧的刪除和插人操作都只能在棧頂進行D.隊列的刪除和插入操作都只能在隊頭進行7.串函數(shù)StrCmp("b","cd")的值為(D)。A.1 B.0 C."bcd" D.-18.設(shè)有一個12階的對稱矩陣A,采用壓縮存儲方式將其下三角部分以行序為主序存儲到一維數(shù)組b中(矩陣A的第一個元素為a1,1,數(shù)組b的下標從1開始),則矩陣A中第4行的元素在數(shù)組b中的下標i一定有(A)。A7<=i<=10B.11&

24、lt;=i<=15C.9<=i<=14D.6<=i<=99.已知一個圖的邊數(shù)為m,則該圖的所有頂點的度數(shù)之和為(A)。A.2m B.m C.2m十1 D.m/210.以下說法不正確的是(D)。 A.連通圖G一定存在生成樹 B.連通圖G的生成樹中一定包含G的所有頂點 C.連通圖G的生成樹中不一定包含G的所有邊 D.連通圖G的生成樹可以是不連通的11.散列查找的原理是(A)。A.在待查記錄的關(guān)鍵字值與該記錄的存儲位置之間建立確定的對應(yīng)關(guān)系B.按待查記錄的關(guān)鍵字有序的順序方式存儲 C.按關(guān)鍵字值的比較進行查找D.基于二分查找的方法12.排序過程中,每一趟從元序子表中將一

25、個待排序的記錄按其關(guān)鍵字的大小放置到已經(jīng)排好序的子序列的適當位置,直到全部排好序為止,該排序算法是(A)。A.直接插入排序B.快速排序C.冒泡排序D.選擇排序13.采用順序查找法對長度為n的線性表進行查找(不采用表尾設(shè)監(jiān)視哨的方法).最壞的情況下要進行(B)次元素間的比較。A.n+2 B.n C.n-l D.n/214.如圖若從頂點a出發(fā)按廣度優(yōu)先搜索法進行遍歷,則可能得到的頂點序列為(D)。A.acebdfghB.aebcghdfC.aedfbcghD.abecdfgh15.一棵哈夫曼樹總共有23個結(jié)點,該樹共有(D)個葉結(jié)點(終端結(jié)點)。A.10 B.13 C.11 D.121.(B)是性

26、質(zhì)相同的數(shù)據(jù)元素的集合,是數(shù)據(jù)的子集A.數(shù)據(jù)元素B.數(shù)據(jù)對象C.數(shù)據(jù)結(jié)構(gòu)D.數(shù)據(jù)項2.設(shè)鏈表中的結(jié)點是NODE類型的結(jié)構(gòu)體變量,且有NODE頭P;為了申請一個新結(jié)點,并由p指向該結(jié)點,可用以下語句(A)。A.p=(NODE*)mallocsizeof(NODE);B.p=(* NODE)malloc(sizeof(NODE);C.p=(NODE)malloc(sizeof(p);D.p=(NODE*)malloc(sizeof(p);3.設(shè)順序存儲的線性表長度為n,要在第i個元素之前插入一個新元素,按課本的算法當i=(D)時,移動元素次數(shù)為2A.n/2 B.n C.1 D.n-l5.設(shè)有一個帶

27、頭結(jié)點的鏈隊列,隊列中每個結(jié)點由一個數(shù)據(jù)域data和指針域next組成,front和rear分別為鏈隊列的頭指針和尾指針。設(shè)p指向要入隊的新結(jié)點該結(jié)點已被賦值),則入隊操作為(A)。A.rear->next=p;rear=p;B.rear->next=p;p=rear;C.p=rear->next;rear=p;D.rear=p;rear->next=p;6.以下說法不正確的是(C)。A.順序棧中,錢滿時再進行進棧操作稱為"上溢"B.順序棧中,找空時再作出棧操作稱為"下溢"C.順序隊列中,當尾指針已經(jīng)超越隊列存儲空間的上界,則一定

28、是隊列已滿D.順序隊列中,隊列的頭指針和尾指針均超越隊列存儲空間的上界,則隊列已空7.設(shè)有一個20階的對稱矩陣A,采用壓縮存儲方式,將其下三角部分以行序為主序存儲到一維數(shù)組中矩陣A的第一個元素為al,l,數(shù)組b的下標從1開始),則矩陣元素a8,5在一維數(shù)組b中的下標是(D)。A.30 B.28 C.40 D.338.深度為5的完全二叉樹第5層上有4個結(jié)點,該樹一共有(D)個結(jié)點。A.28 B.30 C.31 D.199.已知一個圖的所有頂點的度數(shù)之和為m,則m一定不可能是(D)。A.4 B.8 C.12 D.911.對n個元素進行冒泡排序,通常要進行n-l趟冒泡,在第j趟冒泡中共要進行(C)次元素間的比較。A.j B.