數(shù)據(jù)結(jié)構(gòu)與算法試題

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

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

3、循環(huán)雙向鏈表結(jié)點的左指針和右指針，則指針P所指的元素是雙循環(huán)鏈表L的尾元素的條件是（ D。A.P=L B.P->front=L C.P=NULL D.P->rear=L12 .已知P為單鏈表中的非首尾結(jié)點，刪除P結(jié)點的后繼結(jié)點 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 .循環(huán)隊列SQ隊滿的條件是（ B。1 / 161第1頁共16頁A.SQ->rear=SQ-&g

4、t;front B. (SQ->rear+1)%MAXLEN=SQ->frontC.SQ->rear=0 D. SQ->front=014 .一組記錄的排序碼為(46, 79, 56, 38, 40, 84),則利用堆排序的方法建立的初始堆為（B）。A 79, 46, 56, 38, 40, 80B、84,79,56,38,40,46C84,79,56,46,40,38D84,56,79,40,46,3815 .排序趟數(shù)與序列原始狀態(tài)（原始排列）有關的排序方法是（ ACD 方法。A、插入排序B 、選擇排序C冒泡排序D 、快速排序16 .下列排序方法中，（B）是穩(wěn)定的排序

5、方法。A、直接選擇排序B 、二分法插入排序C希爾排序 D 、快速排序17 .數(shù)據(jù)序列（8 , 9 ,10, 4, 5, 6, 20, 1 , 2）只能是下列排序算法中 （C）的兩趟排序后的結(jié)果。A選擇排序B、冒泡排序C插入排序D、堆排序18 .對序列（15, 9, 7, 8, 20,-1, 4）進行排序，進行一趟排序后，數(shù)據(jù)的排列變?yōu)椋?, 9, -1 , 8, 20, 7, 15）,則采用的是（ C 排序。A、選擇B、快速C希爾D、冒泡19.一組待排序記錄的關鍵字為（46, 79, 56, 38, 40, 84）,則利用快速排序，以第一個記錄為基準元素得到的一次劃分結(jié)果為（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.用直接插入排序?qū)ο旅嫠膫€序列進行排序（由小到大），元素比較次數(shù)最少的是C）。A 94,32,40,90,80,46,21,69BC 21,32,46,40,80,69,90,94D、32,40,21,46,69,94,90,80、90,69,80,46,21,32,94,4021.若用冒泡排序?qū)﹃P鍵字序列（18,16,14,12,10,8）進行從小到大的排序，所需進行的關鍵字比較總次數(shù)是（B）。A、 10 B 、15 C 、21D 、

7、3422 .就排序算法所用的輔助空間而言，堆排序、快速排序和歸并排序的關系（ AA、堆排序快速排序歸并排序B、堆排序歸并排序快速排序2 / 162第2頁共16頁C堆排序 歸并排序 快速排序D堆排序 快速排序 歸并排序23 .最小生成樹的構(gòu)造可使用（B）算法。A.Dijkstra 算法 B.Prim 算法 C.Haffman 算法 D.Floyd 算法24 .具有32個結(jié)點的完全二叉樹的深度為（B）。A. 5B.6C.7D.825 .在有n個葉子結(jié)點的哈夫曼樹中，其結(jié)點總數(shù)為（ D）oA.不確定 B . 2n C , 2n+1 D . 2n-126 .下列陳述正確的是（ B）。A.二叉樹是度為2

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

9、于所有頂點出度之和的（ C倍。A 1/2 B 、2 C 、1 D 、432 .任何一個無向連通圖的最小生成樹（ B。A、只有一棵 B 、一棵或多棵C 一定有多棵D 、可能不存在33 .在圖的表示法中，表示形式唯一的是（ AA、鄰接矩陣表示法 B 、鄰接表表示法C逆鄰接矩陣表示法D 、逆鄰接表表示法34 .在一個具有n個頂點的無向圖中，要連通全部頂點至少需要（ C 條邊。A.n B.n+1C.n-1D.n+235 .在一個圖中，所有頂點的度數(shù)之和等于圖的邊數(shù)的（B）。第3頁共16頁3 / 163A. 1/2 B . 2 C . 1 D . 436 .有7個結(jié)點的有向完全圖有（ C 邊。A.30B

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

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

12、構(gòu)成大根堆的是（DA.5 , 8, 1, 3, 9, 6, 2, 7B.9 ,8,1, 7, 5,6,2, 33C.9 , 8, 6, 3, 5, l , 2, 7D.9 ,8,6, 7, 5,1,2, 346 .對序列（15, 9, 7, 8, 20,-1, 4）進行排序，進行一趟排序后，數(shù)據(jù)的排列變?yōu)椋?, 9,-1 , 8, 20, 7, 15）,則采用的是（C排序。A.選擇B. 快速 C. 希爾 D. 冒泡4 / 164第4頁共16頁46.設n, m為一棵樹上的兩個結(jié)點，在中根遍歷時， n在m前的條件是（C）。A.n在 m右方B.n 是m祖先 C.n 在m左方 D.n是m子孫二、填空題

13、1 .樹和圖都屬于非線性結(jié)構(gòu)。2 .順序表中邏輯上相鄰的元素在物理位置上也相鄰。3 .雙向鏈表有兩個指針域，一個指向前趨，另一個指向 后繼_。4 .若進棧的次序是A,B,C,D,E,寫出兩種出棧順序 _ABCDEEDCBA5 .隊列存取數(shù)據(jù)應遵循的原則是先進先出。6 .有20個結(jié)點的完全二叉樹，編號為 7的結(jié)點的父結(jié)點編號為3。7 .兩個序列分別為： L1=3 , 50, 41 , 42, 55, 65, 70, 75 , L2=3 , 50, 41 , 42, 65, 55,.10, 5,用冒泡排序法對 L1和L2進行排序，交換次數(shù)較少的是序列：L18 .在排序方法中，從無序序列中選擇關鍵字

14、最小的記錄，與無序區(qū)（初始為空）的第一個記錄交換的排序方法，稱為選擇 排序。9 .有向圖的邊也稱為弧,用鄰接矩陣存儲有向圖，其第 i行的所有元素之和等于頂點i的出度 。10 .樹轉(zhuǎn)換成的二叉樹，其根結(jié)點的 右 子樹一定為空。11 .二叉排序樹是一種 動態(tài) 查找表。12 .對一組記錄（50, 40, 95, 20, 15, 70, 60, 45, 80）進行直接插入排序時，當把第 7條記錄60插入到有序表中時，為尋找插入位置需比較15次。13 .在樹形結(jié)構(gòu)中，樹根結(jié)點沒有（前驅(qū)）結(jié)點，其余每個結(jié)點有且只有1 個前驅(qū)結(jié)點;葉子結(jié)點沒有后繼結(jié)點,其余結(jié)點的后繼結(jié)點可以 任意多個14 .在具有n個結(jié)點

15、的二叉樹中，有 n+1個空指針。15.深度為k的完全二叉樹至少有2k-1個結(jié)點，至多有2k-1個結(jié)點,若按自上而下,從左到右次序給結(jié)點從1開始編號，則編號最小的葉子結(jié)點的編號是n/2+1。5 / 165第5頁共16頁16 .由a, b, c三個結(jié)點構(gòu)成的二叉樹，共有 形態(tài)。30種不同形態(tài),若是構(gòu)成樹，共有17 .樹所對應的二叉樹其根結(jié)點的右子樹一定為空。18 .已知完全二叉樹的第 8層有8個結(jié)點，則其葉結(jié)點數(shù)是 68三、綜合應用題。2 .已知完全二叉樹的第 8層有4個結(jié)點，請計算它的葉子結(jié)點數(shù)和總結(jié)點數(shù)。(寫出計算過程)。(6分)解：由題意可知，該完全二叉樹有八層，其中第一層結(jié)點數(shù)為：1第二層

16、結(jié)點數(shù)為：2第三層結(jié)點數(shù)為：4第四層結(jié)點數(shù)為：8第五層結(jié)點數(shù)為：16第六層結(jié)點數(shù)為：32第七層結(jié)點數(shù)為：64第八層結(jié)點數(shù)為：4因為第八層結(jié)點數(shù)為4,且為完全二叉樹，則第八層四個結(jié)點為葉子結(jié)點，第七 層前兩個結(jié)點有子結(jié)點，其余 62個結(jié)點無子結(jié)點，則第七層的后 62個結(jié)點為 葉子結(jié)點,故葉子結(jié)點數(shù)有 4+62=66總結(jié)點數(shù)為 1+2+4+8+16+32+64+4=1313 .已知數(shù)據(jù)序列10,8,18,15,7,16,寫出采用直接插入算法排序時，每一趟排序的結(jié)果。(6分)解：直接插入排序過程如下所示 初始列：(10), 8,18,15,7,16第一趟：(8,10) ,18,15,7,16第二趟：

17、(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層的滿二叉樹中結(jié)點數(shù)為多少？請寫出計算公式。解：2K -1 26-1 637 .給定一個權集 W=4,8,6,9,18,畫出相應的哈夫曼樹，并計算 WPL8 .已知二叉樹的先序遍歷序列為 ：ABDGHCEFI,中序遍歷的序列為： GDHBAECIF請完成以下各6 / 166第6頁共16頁題:(1)畫出此二叉樹。(2)寫出它的后序遍歷序列。D B E I F C A8-1,對下面的帶權無向圖：(1)畫出鄰接

18、矩陣。(2)畫出它的一棵最小生成樹。10解：(1)廠 0 55 00 0、5 015 100 10 010 0 00460300043050060509,有一組關鍵字14,15,30,28,5,10, 寫出冒泡排序過程的 圖示。解：第一趟排序結(jié)果：14,15,28,5,10 , (30)第二趟排序結(jié)果：14,15,5,10 ,(28,30 )第三趟排序結(jié)果：14,5,10 , (15,28,30 )第四趟排序結(jié)果：5,10,(14,15,28,30 )第五趟排序結(jié)果：5, (10,14,15,28,30 )第六趟排序結(jié)果：(5,10,14,15,28,30)第7頁共16頁7 / 16710.給

19、定一個權集 W=4, 5, 7, 8, 6, 12, 18,試畫出相應的哈夫曼樹，并計算其帶權徑長度WPLWPL=(12+18)*2+(6+7+8)*3+(4+5)*4=15911.假設用于通信的電文僅由現(xiàn)的頻率分別為7、19、2、6、A、B、C、D E、F、G 32、3、21、10。試為這11-1對于下面所示的圖，求出:(1)畫出鄰接矩陣和鄰接表(2)求出各頂點的入度和出度解：(1)鄰接矩陣1 2 3 4 51 011012 000103 000014 100005 00010鄰接表1 1235A2-f4A35A4A1A54A(2) ID(1)=1QD(1)=3;ID(2)=1,OD(2)=

20、1;ID(3)=1QD(3)=1;ID(4)=2,OD(4)=1;ID(5)=2QD(5)=1;8 / 168第8頁共16頁12 .已知一個無向圖的頂點集為a,b,c,d,e,其鄰接矩陣如下，畫出草圖，寫出從頂點 a出發(fā)按深度優(yōu)先搜索進行遍歷的結(jié)點序列。'01001、10 0 100 0 0 1 10 110 1解:（2）深度優(yōu)先搜索：a b d c e 廣度優(yōu)先搜索：a b e d c10 110（答案不唯一）（答案不唯一）13 .網(wǎng)G的鄰接矩陣如下，試畫出該圖，并畫出它的一棵最小生成樹。0810110803013103040110407013070解:共9 / 16916.寫出圖的

21、一種拓撲序列，若在它的鄰接表存儲結(jié)構(gòu)中，每個頂點鄰接表中的邊結(jié)點都是18 .對圖7-21中所示圖分別用克魯斯卡爾算法和普里姆算法（從頂點2開始）求出其最小生成樹。10 / 1610第10頁共16頁19 .根據(jù)下圖，實現(xiàn)下列功能:x,寫出相關算法，并畫出圖形進行描11 / 1611(1)建立圖的鄰接表；(2)輸出圖的拓撲序列。四、算法設計題1、單向鏈表中，在 p指針所指向的結(jié)點前插入一個元素 述。解：#include<stdio.h>#include<malloc.h>typedef int DataType;typedef struct nodeDataType dat

22、a;第11頁共16頁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(Listnode);s->data=a;s->next=

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

24、;,&x); printf("請輸入將被插入的數(shù)：n");scanf("%d",&x);printf("請輸入將被插入的數(shù)的位置：n");12 / 1612第12頁共16頁scanf("%d",&y);p=H->next;printf(" 插入前，鏈表：");while(p!=NULL)printf("%d",p->data);p=p->next ;if(Insert(H,x,y)/這里是調(diào)用插入算法p=H->next;prin

25、tf("插入后處理后的鏈表：n");while(p!=NULL)printf("%d",p->data);p=p->next;printf("n");圖2-1。在結(jié)點P之后插入結(jié)點£2、在單鏈表中刪除第i個結(jié)點，若刪除成功返回1,否則返回0,并要求畫出圖形進行描述。 解：#include<iostream> #include<iomanip> template<class T> class SeqList13 / 1613第13頁共16頁public:T Delete(int i);T data5;int length;)；template<class T>T Seq