1、一、 選擇題1.在邏輯上可以把數據結構分成（ A）A.線性結構和非線性結構 B.動態結構和靜態結構C.緊湊結構和非緊湊結構 D.內部結構和外部結構2. 單鏈表中各結點之間的地址（C） A.必須連續 B.部分必須連續 C.不一定連續 D.以上均不對3.在一個長度為n的順序表中向第i個元素（0<i<=n+1）之前插入一個新元素時，需向后移動（B）個元素。A、n-i B、n-i+1 C、n-i-1 D、i4. 插入和刪除操作只能在一端進行的線性表，稱為（C）。 A.隊列 B.線性表 C.棧 D.循環隊列5、隊列是僅允許在（）進行插入，而在（）進行刪除。(A)A.隊尾，隊首 B.隊尾，隊尾

2、 C.隊首，隊尾 D.隊首，隊首6.鏈表適合于（A）查找。 A.順序 B.二分 C.隨機 D.順序或二分7.數據的基本單位是（A）。A.數據元素 B.數據結構 C.數據項 D.數據對象8.下列哪個不是算法的特性（B）。A.有窮性 B.可數性 C.可行性 D.確定性9.在表長為n的順序表中進行線性查找，它的平均查找長度為（B）。A.ASL=n B.ASL=(n+1)/2 C.ASL=+1 D.ASL=log2n10. 一個線性表第一個元素的存儲地址是320，每個元素的長度為3，則第五個元素的地址是(C）。A.311 B.328 C.332 D.31311.設front、rear分別為循環雙向鏈表

3、結點的左指針和右指針，則指針P所指的元素是雙循環鏈表L的尾元素的條件是（D）。 A.P=L B.P->front=L C.P=NULL D.P->rear=L12. 已知P為單鏈表中的非首尾結點，刪除P結點的后繼結點Q的語句為（A）。 A.P->NEXT=Q->NEXT;FREE(Q); B.Q->NEXT=P; FREE(Q); C.Q->NEXT=P->NEXT;FREE(Q); D.P->NEXT=S;S->NEXT=P;13.循環隊列SQ隊滿的條件是（B）。 A.SQ->rear=SQ->front B. (SQ->

4、;rear+1)%MAXLEN=SQ->front C.SQ->rear=0 D. SQ->front=014.一組記錄的排序碼為（46，79，56，38，40，84），則利用堆排序的方法建立的初始堆為(B)。A、79，46，56，38，40，80 B、84，79，56，38，40，46C、84，79，56，46，40，38 D、84，56，79，40，46，3815.排序趟數與序列原始狀態(原始排列)有關的排序方法是（ACD）方法。A、插入排序 B、選擇排序      C、冒泡排序    D、快

5、速排序16.下列排序方法中，（B）是穩定的排序方法。A、直接選擇排序 B、二分法插入排序C、希爾排序 D、快速排序17.數據序列（8，9，10，4，5，6，20，1，2）只能是下列排序算法中(C)的兩趟排序后的結果。A、選擇排序 B、冒泡排序C、插入排序 D、堆排序18.對序列(15，9，7，8，20，-1，4)進行排序，進行一趟排序后，數據的排列變為（4，9，-1，8，20，7，15），則采用的是（C）排序。A、選擇 B、快速C、希爾 D、冒泡19.一組待排序記錄的關鍵字為（46，79，56，38，40，84），則利用快速排序，以第一個記錄為基準元素得到的一次劃分結果為（ C ）。A(38,

6、40,46,56,79,84) B、(40,38,46,79,56,84)C、(40,38,46,56,79,84)D、(40,38,46,84,56,79)20.用直接插入排序對下面四個序列進行排序（由小到大），元素比較次數最少的是（ C ）。A、94,32,40,90,80,46,21,69 B、32,40,21,46,69,94,90,80C 21,32,46,40,80,69,90,94 D、90,69,80,46,21,32,94,4021.若用冒泡排序對關鍵字序列（18,16,14,12,10,8）進行從小到大的排序，所需進行的關鍵字比較總次數是（B）。A、10 B、15 C、21

7、 D、34 22.就排序算法所用的輔助空間而言，堆排序、快速排序和歸并排序的關系（A）。A、堆排序<快速排序<歸并排序 B、堆排序<歸并排序<快速排序C、堆排序>歸并排序>快速排序 D、堆排序>快速排序>歸并排序23.最小生成樹的構造可使用（B）算法。 A.Dijkstra算法 B.Prim算法 C.Haffman算法 D.Floyd算法24. 具有32個結點的完全二叉樹的深度為（B）。 A. 5 B.6 C.7 D.825. 在有n個葉子結點的哈夫曼樹中，其結點總數為（D）。A不確定 B2n C2n+1 D2n-126.下列陳述正確的是（B）。

8、 A.二叉樹是度為2的有序樹 B. 二叉樹中最多只有二棵樹,且有左右子樹之分 C.二叉樹必有度為2的結點 D. 二叉樹中結點只有一個孩子時無左右之分27.先序為A，B，C的二叉樹共有（A）種。 A.3 B.4 C.5 D.6 28.在樹結構中,若結點B有3個兄弟,A是B的父親結點,則A的度為(B)。 A.3 B.4 C.5 D.6 29.在一個圖中，所有頂點的度數之和等于所有邊數的（B）倍。A、1 B、2 C、3 D、430.n個頂點的強連通圖至少有（A）邊。A、n B、n-1 C、n+1 D、n (n-1)31.在一個無向圖中，所有頂點的度數之和等于所有邊數的（C）倍；在一個有向圖中，所有頂

9、點的入度之和等于所有頂點出度之和的（C）倍。A、1/2 B、2 C、1 D、432.任何一個無向連通圖的最小生成樹（B）。A、只有一棵 B、一棵或多棵 C、一定有多棵 D、可能不存在33.在圖的表示法中，表示形式唯一的是（A）A、鄰接矩陣表示法 B、鄰接表表示法 C、逆鄰接矩陣表示法 D、逆鄰接表表示法34.在一個具有n個頂點的無向圖中，要連通全部頂點至少需要（C）條邊。 A.n B.n+1 C.n-1 D.n+235. 在一個圖中，所有頂點的度數之和等于圖的邊數的（B）。A1/2 B2 C1 D436有7個結點的有向完全圖有（C）邊。 A.30 B.40 C.42 D.5637.假定在一棵二

10、叉樹中，度為2的分支結點個數為15，度為1的分支結點個數為30個，則葉子結點數為（B）。A、15 B、16 C、17 D、4738.設n，m為一棵樹上的兩個結點，在中根遍歷時，n在m前的條件是（C）。A、n在m右方 B、n是m祖先 C、n在m左方 D、n是m子孫39.某二叉樹的后序遍歷序列為：DABEC，中序遍歷序列為：DEBAC，則前序遍歷序列為（D ）。A、ACBED B、DECAB C、DEABC D、CEDBA40.將一棵有100個結點的完全二叉樹從上到下，從左到右依次對結點編號，根結點的編號為1，則編號為45的結點的左孩子的編號為（90），右孩子的編號為（91）。A、46 B、47

11、C、91 D、9141.某樹中，若結點B有4個兄弟，A是B的父親結點，則A的度為（C）。A、3 B、4 C、5 D、642.下列敘述正確的是（D）A、二叉樹是度為2的有序樹 B、二叉樹結點只有一個孩子時無左右之分 C、二叉樹中必有度為2的結點 D、二叉樹中最多只有兩棵子樹，且有左右之分43.由帶權為9、2、5、7的四個葉子結點構造一棵哈夫曼樹，該樹的帶樹路徑長度為（D）。A、23 B、37 C、46 D、4444在圖的表示方法中，表示形式是唯一的是（C）。 A.鄰接表 B.逆鄰接表 C.鄰接矩陣 D.其他44.下列關鍵字序列中，構成大根堆的是(D) A.5，8，1，3，9，6，2，7 B.9，

12、8，1，7，5，6，2，33 C.9，8，6，3，5，l，2，7 D.9，8，6，7，5，1，2，3 45.對序列(15，9，7，8，20，-1，4)進行排序，進行一趟排序后，數據的排列變為（4，9，-1，8，20，7，15），則采用的是（C）排序。A.選擇 B.快速 C.希爾 D.冒泡46.設n，m為一棵樹上的兩個結點，在中根遍歷時，n在m前的條件是（C）。A.n在m右方 B.n是m祖先 C.n在m左方 D.n是m子孫二、填空題1.樹和 圖 都屬于非線性結構。2.順序表中邏輯上相鄰的元素在物理位置上 也 相鄰。3.雙向鏈表有兩個指針域，一個指向前趨，另一個指向_后繼_。4.若進棧的次序是A,

13、B,C,D,E,寫出兩種出棧順序_ABCDE、EDCBA。5.隊列存取數據應遵循的原則是先進先出。6.有20個結點的完全二叉樹，編號為7的結點的父結點編號為 3 。7.兩個序列分別為：L1=3，50，41，42，55，65，70，75，L2=3，50，41，42，65，55，.10，5，用冒泡排序法對L1和L2進行排序，交換次數較少的是序列： L1 。8.在排序方法中，從無序序列中選擇關鍵字最小的記錄，與無序區（初始為空）的第一個記錄交換的排序方法，稱為 選擇 排序。9.有向圖的邊也稱為 弧，用鄰接矩陣存儲有向圖，其第i行的所有元素之和等于頂點i的 出度 。10樹轉換成的二叉樹，其根結點的 右

14、 子樹一定為空。11.二叉排序樹是一種 動態 查找表。12.對一組記錄（50，40，95，20，15，70，60，45，80）進行直接插入排序時，當把第7條記錄60插入到有序表中時，為尋找插入位置需比較 15 次。13.在樹形結構中，樹根結點沒有（前驅）結點，其余每個結點有且只有 1 個前驅結點；葉子結點沒有后繼 結點，其余結點的后繼結點可以任意多個。14.在具有n個結點的二叉樹中，有n+1個空指針。15.深度為k的完全二叉樹至少有2k-1個結點，至多有2k-1個結點，若按自上而下，從左到右次序給結點從1開始編號，則編號最小的葉子結點的編號是n/2+1。16.由a，b，c三個結點構成的二叉樹，

15、共有 30種不同形態，若是構成樹，共有9 種形態。17.樹所對應的二叉樹其根結點的 右 子樹一定為空。18.已知完全二叉樹的第8層有8個結點，則其葉結點數是 68 三、綜合應用題。2.已知完全二叉樹的第8層有4個結點，請計算它的葉子結點數和總結點數。（寫出計算過程）。（6分）解：由題意可知，該完全二叉樹有八層，其中第一層結點數為：1第二層結點數為：2第三層結點數為：4第四層結點數為：8第五層結點數為：16第六層結點數為：32第七層結點數為：64第八層結點數為：4因為第八層結點數為4，且為完全二叉樹，則第八層四個結點為葉子結點，第七層前兩個結點有子結點，其余62個結點無子結點，則第七層的后62個

16、結點為葉子結點，故葉子結點數有4+62=66總結點數為1+2+4+8+16+32+64+4=1313.已知數據序列10,8,18,15,7,16，寫出采用直接插入算法排序時，每一趟排序的結果。（6分）解：直接插入排序過程如下所示初始列：（10），8,18,15,7,16第一趟：（8,10）,18,15,7,16第二趟：（8,10,18），15,7,16第三趟：（8,10,15,18），7,16第四趟：（7,8,10,15,18），16第五趟：（7,8,10,15,16,18）6.一棵具有6層的滿二叉樹中結點數為多少？請寫出計算公式。解：637.給定一個權集W=4,8,6,9,18，畫出相應的哈

17、夫曼樹，并計算WPL。 8.已知二叉樹的先序遍歷序列為:ABDGHCEFI,中序遍歷的序列為：GDHBAECIF。請完成以下各題：（1）畫出此二叉樹。（2）寫出它的后序遍歷序列。GHABDCEFI（3）將此二叉樹看作森林的二叉樹表示，試將它還原為森林。（1）（2）其后序遍歷的序列為：G H D B E I F C A （3） 8-1.對下面的帶權無向圖：124365（1）畫出鄰接矩陣。55（2）畫出它的一棵最小生成樹。 1 10 4 637 5解：（1）124365 0 5 5 0 0 0 （2）最小生成樹 5 0 1 10 0 0 邊為紅色的 5 1 0 0 4 6 0 10 0 0 3 0

18、 0 0 4 3 0 5 0 0 6 0 5 09.有一組關鍵字14,15,30,28,5,10,寫出冒泡排序過程的圖示。解：第一趟排序結果：14,15,28,5,10，（30）第二趟排序結果：14,15,5,10，（28,30）第三趟排序結果：14,5,10，（15,28,30）第四趟排序結果：5,10，（14,15,28,30）第五趟排序結果：5，（10,14,15,28,30）第六趟排序結果：（5,10,14,15,28,30） 351325D12660181798D45710.給定一個權集W=4，5，7，8，6，12，18，試畫出相應的哈夫曼樹，并計算其帶權徑長度WPL。WPL=(12

19、+18)*2+(6+7+8)*3+(4+5)*4=15911.假設用于通信的電文僅由A、B、C、D、E、F、G、H等8個字母組成，字母在電文中出現的頻率分別為7、19、2、6、32、3、21、10。試為這8個字母設計哈夫曼編碼。11-1對于下面所示的圖，求出：12345（1）畫出鄰接矩陣和鄰接表（2）求出各頂點的入度和出度解：（1）鄰接矩陣 1 2 3 4 5鄰接表123524354154（2）ID(1)=1,OD(1)=3;ID(2)=1,OD(2)=1;ID(3)=1,OD(3)=1;ID(4)=2,OD(4)=1;ID(5)=2,OD(5)=1;12.已知一個無向圖的頂點集為a,b,c,

20、d,e，其鄰接矩陣如下，畫出草圖，寫出從頂點a出發按深度優先搜索進行遍歷的結點序列。 0 1 0 0 1 1 0 0 1 0 0 0 0 1 1 0 1 1 0 1 1 0 1 1 0解：acbed（1）（2）深度優先搜索：a b d c e （答案不唯一） 廣度優先搜索：a b e d c （答案不唯一）13.網G的鄰接矩陣如下，試畫出該圖，并畫出它的一棵最小生成樹。 0 8 10 11 0 8 0 3 0 13 10 3 0 4 0 11 0 4 0 7 0 13 0 7 02543125431解： 最小生成樹： 8 11 10 8 3 4 13 7 3 4 716.寫出圖的一種拓撲序列，

21、若在它的鄰接表存儲結構中，每個頂點鄰接表中的邊結點都是按照終點序號從大到小鏈接的，則按此給出惟一一種拓撲序列。17.對圖中所示圖分別寫出深度優先遍歷和廣度優先遍歷的項點序列 18.對圖7-21中所示圖分別用克魯斯卡爾算法和普里姆算法（從頂點2開始）求出其最小生成樹。： 19.根據下圖，實現下列功能：（1）建立圖的鄰接表；（2）輸出圖的拓撲序列。四、算法設計題1、單向鏈表中，在p指針所指向的結點前插入一個元素x,寫出相關算法,并畫出圖形進行描述。解：#include<stdio.h>#include<malloc.h>typedef int DataType;typede

22、f struct node DataType data; struct node *next;Listnode;int Insert(Listnode *head,DataType a,int b)/這個是插入算法 Listnode *p,*h,*s; int k=1; p=head; h=head->next; while(h!=NULL&&k<=b-1) k+; p=h; h=h->next; if(p=NULL) printf("插入失敗"); return 0; s=(Listnode *)malloc(sizeof(Listnod

23、e); s->data=a; s->next=h; p->next=s; return 1;void main() Listnode *H,*p; int x,y; H=(Listnode*)malloc(sizeof(Listnode); H->next=NULL; printf("請輸入將被存入鏈表中的數（0為結束）："); scanf("%d",&x); while(x!=0) p=(Listnode*)malloc(sizeof(Listnode); p->data=x; p->next=H->n

24、ext; H->next=p; scanf(" %d",&x); printf("請輸入將被插入的數:n"); scanf("%d",&x); printf("請輸入將被插入的數的位置：n"); scanf("%d",&y); p=H->next; printf("插入前，鏈表："); while(p!=NULL) printf("%d",p->data); p=p->next ; if(Insert(H,x

25、,y)/這里是調用插入算法 p=H->next; printf("插入后處理后的鏈表：n"); while(p!=NULL) printf("%d",p->data); p=p->next; printf("n"); 2、在單鏈表中刪除第i個結點,若刪除成功返回1,否則返回0,并要求畫出圖形進行描述。解：#include<iostream>#include<iomanip>template<class T>class SeqListpublic:T Delete(int i);T data5;int length