C語言數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題

1、一、單選題1. 在數(shù)據(jù)結(jié)構(gòu)中，從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分為（ ）。A動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu) B緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C線性結(jié)構(gòu)和非線性結(jié)構(gòu)D內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2. 算法具備輸入，輸出和（ ）等五個(gè)特性A.可行性，可移植性和可擴(kuò)充性 B.可行性，確定性和有窮性C.確定性，有窮性和穩(wěn)定性 D.易讀性，穩(wěn)定性和安全性3. 鏈表不具備的特點(diǎn)是（ ）。A可隨機(jī)訪問任一結(jié)點(diǎn)B插入刪除不需要移動(dòng)元素C不必事先估計(jì)存儲(chǔ)空間D所需空間與其長度成正比4線性表是（ ）。 A一個(gè)有限序列，可以為空B一個(gè)有限序列，不可以為空C一個(gè)無限序列，可以為空D一個(gè)無限序列，不可以為空5下面關(guān)于線性表的敘述中，錯(cuò)誤的是哪一個(gè)? （ ）。A

2、線性表采用順序存儲(chǔ)，必須占用一片連續(xù)的存儲(chǔ)單元B線性表采用順序存儲(chǔ)，便于進(jìn)行插入和刪除操作。C線性表采用鏈?zhǔn)酱鎯?chǔ)，不必占用一片連續(xù)的存儲(chǔ)單元D線性表采用鏈?zhǔn)酱鎯?chǔ)，便于進(jìn)行插入和刪除操作。6以下關(guān)于線性表的說法不正確的是（）。A線性表中的數(shù)據(jù)元素可以是數(shù)字、字符、記錄等不同類型。B線性表中包含的數(shù)據(jù)元素個(gè)數(shù)不是任意的。C線性表中的每個(gè)結(jié)點(diǎn)都有且只有一個(gè)直接前趨和直接后繼。D存在這樣的線性表：表中各結(jié)點(diǎn)都沒有直接前趨和直接后繼。7設(shè)有一個(gè)棧，元素的進(jìn)棧次序?yàn)锳, B, C, D, E,下列是不可能的出棧序列（）。 AA, B, C, D, E BB, C, D, E, ACE, A, B, C,

3、D DE, D, C, B, A8在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端（即0單元）作為棧底，以top作為棧頂指針，當(dāng)做出棧處理時(shí)，top變化為（）。 Atop不變 Btop=0 Ctop- Dtop+9在循環(huán)隊(duì)列中，若front與rear 分別表示對頭元素和隊(duì)尾元素的位置，則判斷循環(huán)隊(duì)列空的條件是（）。Afrontrear1 Brearfront1 Cfrontrear Dfront010若INDEX（S，T）表示求T在S中的位置的操作，則對于S=“BeijingNanjing”，T=“jing”，INDEX（S，T）=（）。A.2 B.3 C.4 D.511串是一種特殊的線性表，其特

4、殊性體現(xiàn)在（）。A可以順序存儲(chǔ)B數(shù)據(jù)元素是一個(gè)字符C可以鏈?zhǔn)酱鎯?chǔ)D數(shù)據(jù)元素可以是多個(gè)字符12稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即（）。A.二維數(shù)組和三維數(shù)組 B.三元組和散列C.三元組和十字鏈表 D.散列和十字鏈表13對矩陣進(jìn)行壓縮存儲(chǔ)是為了（）。A方便運(yùn)算B方便存儲(chǔ)C提高運(yùn)算速度 D減少存儲(chǔ)空間14假設(shè)在一棵二叉樹中，雙分支結(jié)點(diǎn)數(shù)為15，單分支結(jié)點(diǎn)數(shù)為30個(gè)，則葉子結(jié)點(diǎn)數(shù)為（）個(gè)。A. 15 B. 16 C. 17 D. 4715樹最適合用來表示（ ）。A有序數(shù)據(jù)元素B無序數(shù)據(jù)元素C元素之間具有分支層次關(guān)系的數(shù)據(jù)D元素之間無聯(lián)系的數(shù)據(jù)16根據(jù)先序序列ABDC（根左右）和中序序列DBAC（左根

5、右）確定對應(yīng)的二叉樹，該二叉樹（ ）。A. 是完全二叉樹 AB. 不是完全二叉樹 B CC. 是滿二叉樹D D. 不是滿二叉樹 17已知一棵完全二叉樹的結(jié)點(diǎn)總數(shù)為9個(gè)，則最后一層的結(jié)點(diǎn)數(shù)為( )。A. 1 B. 2 C. 3 D. 4 12 34 5 6 78 918對于一個(gè)無向圖，下面( )種說法是正確的。A. 每個(gè)頂點(diǎn)的入度等于出度 B. 每個(gè)頂點(diǎn)的度等于其入度與出度之和C. 每個(gè)頂點(diǎn)的入度為0 D. 每個(gè)頂點(diǎn)的出度為019對于長度為18的順序存儲(chǔ)的有序表，若采用折半查找，則查找第15個(gè)元素的比較次數(shù)為( )。A. 3 B. 4 C. 5 D. 620若要對1000個(gè)元素排序，要求既快又節(jié)

6、省存儲(chǔ)空間，則最好采用（ ）方法。A. 直接插入排序B. 歸并排序C. 堆排序D. 快速排序二、判斷題1. 順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。（ F ）2. 已知指針P指向鍵表L中的某結(jié)點(diǎn)，執(zhí)行語句P=P.next不會(huì)刪除該鏈表中的結(jié)點(diǎn)。（ T ）3. 隊(duì)列是一種插入和刪除操作分別在表的兩端進(jìn)行的線性表，是一種先進(jìn)后出的結(jié)構(gòu)。（ F ）4.如果一個(gè)串中的所有字符均在另一串中出現(xiàn)，則說前者是后者的子串。（ F ）5. 用鄰接矩陣法存儲(chǔ)一個(gè)圖時(shí)，在不考慮壓縮存儲(chǔ)的情況下，所占用的存儲(chǔ)空間大小只與圖中結(jié)點(diǎn)個(gè)數(shù)有關(guān)，而與圖的邊數(shù)無關(guān)。（ T ）6.快速排序是不穩(wěn)定排序。（ T ）7. 在哈夫曼樹中，權(quán)

7、值最小的結(jié)點(diǎn)離根結(jié)點(diǎn)最近。（ F ）8.若圖G的最小生成樹不唯一，則G的邊數(shù)一定多于n-1，并且權(quán)值最小的邊有多條（其中n為G的頂點(diǎn)數(shù)）。（ T ）9.給出不同的輸入序列建造二叉排序樹，一定得到不同的二叉排序樹。（ F ）10.冒泡排序算法關(guān)鍵字比較的次數(shù)與記錄的初始排列次序無關(guān)。（ F ）三、填空題1數(shù)據(jù)的邏輯結(jié)構(gòu)有四種基本形態(tài)，分別是集合、( 線性表 )、樹和圖。2. 一個(gè)算法的效率可分為時(shí)間效率和( 空間 )效率。3在單鏈表中，要?jiǎng)h除某一指定的結(jié)點(diǎn)，必須找到該結(jié)點(diǎn)的（ 前驅(qū) ）結(jié)點(diǎn)。4當(dāng)對一個(gè)線性表經(jīng)常進(jìn)行插入和刪除操作時(shí)，采用( 鏈?zhǔn)?)存儲(chǔ)結(jié)構(gòu)為宜。5對于隊(duì)列而言，只能在（ 隊(duì)尾 ）

8、位置插入元素。7稀疏矩陣一般的壓縮存儲(chǔ)方法有兩種，即（ 三元組 ）和十字鏈表。8 在一棵二叉樹中，度為零的結(jié)點(diǎn)的個(gè)數(shù)為n0，度為2 的結(jié)點(diǎn)的個(gè)數(shù)為n2，則有n0（ n2+1 ）。9. 三叉鏈表比二叉鏈表多一個(gè)指向（ 雙親 ）的指針域。10. 具有10個(gè)頂點(diǎn)的無向圖，邊的總數(shù)最多為（ 45）。N(N-1)/2四、綜合應(yīng)用題要點(diǎn)1.二叉樹先序遍歷、中序遍歷、后序遍歷 根左右 左根右 左右根要點(diǎn)2.哈夫曼樹的生成 排序 選數(shù) 連接最小的數(shù) 比較 要點(diǎn)3.森林和二叉樹的相互轉(zhuǎn)換 要點(diǎn)4.將圖轉(zhuǎn)換成最小生成樹要點(diǎn)5.根據(jù)稀疏矩陣對應(yīng)的三元組線性表，畫出稀疏矩陣要點(diǎn)6.根據(jù)無向圖或者有向圖的鄰接表，畫出無

9、向圖或者有向圖要點(diǎn)7.求最短路徑的Dijkstra算法五、算法設(shè)計(jì)題。要點(diǎn)：著重關(guān)注單鏈表的基本操作（數(shù)據(jù)插入、刪除、判斷單鏈表是否為空，返回單鏈表元素個(gè)數(shù)等），?；蛘哧?duì)列兩種結(jié)構(gòu)鏈?zhǔn)交蛘唔樞虼鎯?chǔ)結(jié)構(gòu)定義中的方法。比如出棧（隊(duì)列）、進(jìn)棧（隊(duì)列），獲取棧（隊(duì)列）首元素，判斷棧（隊(duì)列）是否為空等等。#include<stdio.h>#define MAXSIZE 20 #define OK 1#define ERROR 0typedef int Status; typedef int ElemType;typedef structElemType dataMAXSIZE;int len

10、gth; / 線性表中元素個(gè)數(shù)SqList;/初始化線性表SqList InitList()SqList L;L.length=0;return L;/插入元素Status ListInsert(SqList *L,int i,ElemType e)int k;if(L->length=MAXSIZE | i<0 | i>L->length)return ERROR;for(k=L->length-1;k>=i;k-)L->datak+1=L->datak;L->datai=e;L->length+;return OK;/獲取元素El

11、emType GetElem(SqList L,int i)if(L.length=0 | i<0 | i>L.length-1)printf("位置錯(cuò)誤！");return L.datai;/刪除元素Status ListDelete(SqList *L,int i,ElemType *e)int k;if(L->length=0 | i<0 | i>L->length-1)return ERROR;*e=L->datai;for(k=i;k<L->length;k+)L->datak-1=L->datak;L->length-;return OK;/清空線性表void ClearList(SqList *L)L->length=0;/判斷線性表是否為滿Status ListFull(SqList L)if(L.length=MAXSIZE)return OK;elsereturn ERROR;/判斷線性表是否為空Status ListFull(SqList L)if(L.length=0)return OK;elsereturn ERROR;int main()Status x;ElemType y,*e,z;SqList L=InitList();Li