數(shù)據(jù)結(jié)構(gòu)習(xí)題

1、1.1 什么是數(shù)據(jù)結(jié)構(gòu)1.2 基本概念和術(shù)語1.3 抽象數(shù)據(jù)類型的表示與實(shí)現(xiàn)1.4 算法和算法分析1、 數(shù)據(jù)結(jié)構(gòu)是一門研究_的程序設(shè)計(jì)問題中，計(jì)算機(jī)的操作對象以及它們之間的關(guān)系和操作等的學(xué)科。A: 數(shù)據(jù)庫B: 數(shù)值計(jì)算C: 高級語言D: 非數(shù)值計(jì)算2、 數(shù)據(jù)結(jié)構(gòu)課程屬于計(jì)算機(jī)科學(xué)知識體中_領(lǐng)域的綜合性專業(yè)基礎(chǔ)課。A: 離散結(jié)構(gòu)Discrete Structures (DS)B: 程序設(shè)計(jì)語言Programming Languages (PL)C: 程序設(shè)計(jì)基礎(chǔ)Programming Fundamentals (PF)D: 算法與復(fù)雜性Algorithms and Complexity (AL)

2、3、 “數(shù)據(jù)結(jié)構(gòu)”是介于_、程序設(shè)計(jì)和代數(shù)系統(tǒng)三者之間的核心課程。A: 計(jì)算機(jī)硬件B: 計(jì)算機(jī)軟件C: 數(shù)據(jù)庫系統(tǒng)D: 計(jì)算機(jī)操作系統(tǒng)4、 具有相同性質(zhì)的計(jì)算機(jī)數(shù)據(jù)集合及在這個(gè)集合上的一組操作，稱為_。A: 邏輯結(jié)構(gòu)B: 物理結(jié)構(gòu)C: 數(shù)據(jù)類型D: 數(shù)據(jù)結(jié)構(gòu)5、 數(shù)據(jù)結(jié)構(gòu)可記為DS = D, R，其中D是某一數(shù)據(jù)對象，R是該對象中所有數(shù)據(jù)成員之間_的有限集合。A: 算法B: 關(guān)系C: 數(shù)據(jù)元素D: 數(shù)據(jù)類型 6、 數(shù)據(jù)結(jié)構(gòu)中，與計(jì)算機(jī)存儲器有關(guān)的是數(shù)據(jù)的_結(jié)構(gòu)。A: 線性B: 非線性C: 物理D: 邏輯7、 _分別屬于邏輯結(jié)構(gòu)和物理結(jié)構(gòu)。A: 樹和圖B: 表和索引C: 順序和鏈接D: 順序表和

3、散列表8、 在問題規(guī)模n較大情況下，效率相對較高的時(shí)間復(fù)雜度T(n)為_。A: O(n2)B: O(2n)C: O(100n)D: O(n*log2n) 9、 判斷：科學(xué)家尼克勞斯沃斯(Niklaus Wirth)關(guān)于數(shù)據(jù)結(jié)構(gòu)的一個(gè)公式是：數(shù)據(jù)結(jié)構(gòu)程序 算法。10、 判斷：數(shù)據(jù)結(jié)構(gòu)由基本的抽象數(shù)據(jù)類型組成，并包括一組相關(guān)的服務(wù)或操作。11、 判斷：在數(shù)據(jù)結(jié)構(gòu)中，算法的每條指令或語句的執(zhí)行次數(shù)是有限的。12、 判斷：時(shí)間復(fù)雜度高的算法，其空間復(fù)雜度也高。13、 判斷：算法的時(shí)間復(fù)雜度達(dá)到T(n)=O(n2)時(shí)，當(dāng)n增大后，算法的執(zhí)行時(shí)間會急劇增大，這類算法常稱為“壞”的算法。14、 判斷：算法的

4、健壯性是指：算法應(yīng)具有容錯(cuò)處理。當(dāng)輸入非法數(shù)據(jù)時(shí)，算法應(yīng)對其作出反應(yīng)，而不是產(chǎn)生莫名其妙的輸出結(jié)果。 15、 已知某算法如下，其平均時(shí)間復(fù)雜度T(N)=_。void sub1(int N) int i,j; for (i=1;i=N;+i) for (j=1;j1;-i) /運(yùn)行1次 for (j=0;jaj+1) /運(yùn)行 (N-1)+ (N-2)+2)次 temp=aj; aj=aj+1; aj+1=temp; 2.1 線性表的類型定義2.2 線性表的順序表示和實(shí)現(xiàn)2.3 線性表的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)2.4 一元多項(xiàng)式的表示及相加1、 線性表是由n(n)個(gè)_數(shù)據(jù)元素a1，a2， an組成的有限序列

5、。A: 數(shù)值型 B: 非數(shù)值型 C: 同種類型 D: 不同類型 2、 順序表的特點(diǎn)是以元素在計(jì)算機(jī)內(nèi)_相鄰來表示線性表中數(shù)據(jù)元素之間的邏輯關(guān)系。A: 邏輯位置 B: 物理位置 C: 磁盤位置 D: 扇區(qū)位置 3、 鏈表中結(jié)點(diǎn)的邏輯次序和物理次序_。A: 一定相同B: 一定不相同C: 不一定相同D: 與結(jié)點(diǎn)的內(nèi)容有關(guān)4、 鏈表用一組任意的存儲單元來依次存放線性表的結(jié)點(diǎn)，這組存儲單元_。A: 必須是連續(xù)的B: 必須是不連續(xù)的C: 按結(jié)點(diǎn)的前后次序排列D: 即可以是連續(xù)的，也可以是不連續(xù)的5、 _的插入和刪除操作會移動(dòng)大量的結(jié)點(diǎn)。A: 單鏈表B: 雙鏈表C: 順序表D: 循環(huán)鏈表6、 在雙向鏈表的結(jié)

6、點(diǎn)中有兩個(gè)指針域，其一指向直接后繼，另一指向_ 。A: 尾結(jié)點(diǎn)B: 頭結(jié)點(diǎn)C: 直接前趨D: 結(jié)點(diǎn)本身7、 指向雙向鏈表結(jié)點(diǎn)d的指針，存在下面的關(guān)系：_。A: d-next-prior = d-prior-nextB: d-next- next = d-prior- prior C: d-next- next = dD: d-prior- prior = d8、 順序表的特點(diǎn)有：_。A: 插入、刪除效率高B: 存儲空間能動(dòng)態(tài)分配C: 可方便隨機(jī)存取數(shù)據(jù)元素D: 邏輯關(guān)系與物理位置不一致9、 鏈表的特點(diǎn)有：_。A: 插入、刪除效率低B: 存儲空間不能靜態(tài)分配C: 邏輯關(guān)系與物理位置一致D: 隨機(jī)

7、存取數(shù)據(jù)元素效率低10、 循環(huán)鏈表是另一種形式的鏈?zhǔn)酱鎯Y(jié)構(gòu)。它的特點(diǎn)是表中最后一個(gè)結(jié)點(diǎn)的指針域指向_ 。A: 尾結(jié)點(diǎn)B: 頭結(jié)點(diǎn)C: 前一個(gè)結(jié)點(diǎn)D: 空 11、 已知某單鏈表操作的頭文件，試寫出函數(shù)LocatePos(LinkList L,int i,Position &p)實(shí)現(xiàn)的算法。12、 已知某單鏈表操作的頭文件試寫出函數(shù)InsFirst(LinkList &L,ElemType e)實(shí)現(xiàn)的算法。13、 已知某單鏈表操作的頭文件，試寫出函數(shù)DelFirst(LinkList &L,ElemType &e)實(shí)現(xiàn)的算法。14、 已知某單鏈表操作的頭文件，試寫出函數(shù)Append(LinkLi

8、st &L,ElemType e)實(shí)現(xiàn)的算法。15、 已知某單鏈表操作的頭文件，試寫出函數(shù)ListInsert(LinkList &L,int i,ElemType e)實(shí)現(xiàn)的算法。16、 已知某單鏈表操作的頭文件，試寫出函數(shù)ListDelete(LinkList &L,int i,ElemType &e)實(shí)現(xiàn)的算法。17、 已知某單鏈表操作的頭文件如下，試寫出函數(shù)MergeList(LinkList La, LinkList Lb, LinkList &Lc)實(shí)現(xiàn)的算法。單鏈表操作的頭文件：List.h/=/= 1. 預(yù)定義常量和類型/=#define TRUE1#define FALSE0

9、#define OK1#define ERROR0#define INFEASIBLE-1#define OVERFLOW-2typedef intStatus;/Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼。typedef int ElemType;/定義數(shù)據(jù)元素類型取為 int /=/= 2. 定義數(shù)據(jù)結(jié)構(gòu)/=/= 2.2 單鏈表存儲結(jié)構(gòu)(帶頭結(jié)點(diǎn)的線性鏈表)typedef struct LNodeElemType data;struct LNode *next;*Link,*Position;typedef structLink head,tail;int len;LinkList;

10、/=/= 3. 定義基本操作/=/= 3.2 單鏈表基本操作StatusLocatePos(LinkList L,int i,Position &p);/定位:將單鏈表中第i個(gè)結(jié)點(diǎn)位置送至p /=/ The end of List.h /= 3.1 棧3.2 棧的應(yīng)用舉例 3.3 棧與遞歸的實(shí)現(xiàn)*3.4 隊(duì)列 1、 _是限定僅在表的一端（通常為表尾）進(jìn)行插入或刪除操作的線性表。A: 隊(duì)列B: 棧C: 串D: 樹2、 對棧的操作所具有的特征為_。A: “先進(jìn)先出” B: “后進(jìn)后出” C: “先進(jìn)后出” D: 上面三者都不是3、 _是棧的典型操作。A: Enqueue B: Dequeue C:

11、 SortD: Pop4、 滿棧時(shí)執(zhí)行_操作會產(chǎn)生上溢。A: PopB: PushC: Enqueue D: Dequeue 5、 空棧時(shí)執(zhí)行_操作會產(chǎn)生下溢。A: PopB: PushC: Enqueue D: Dequeue 6、 _的一個(gè)重要應(yīng)用是在程序中實(shí)現(xiàn)遞歸調(diào)用。A: 棧B: 隊(duì)列C: 數(shù)組D: 生成樹7、 在隊(duì)列中，允許插入的一端叫_。A: 隊(duì)尾B: 隊(duì)頭C: 頂D: 底8、 對隊(duì)列的操作所具有的特征為_。A: “先進(jìn)后出” B: “后進(jìn)先出” C: “先進(jìn)先出” D: 上面三者都不是9、 _是隊(duì)列的典型操作。A: Psh B: PopC: SortD: EnQueue 10、

12、對雙端隊(duì)列_。A: 插入只能在隊(duì)尾進(jìn)行B: 刪除只能在隊(duì)頭進(jìn)行C: 插入和刪除可以在兩端進(jìn)行D: 插入和刪除只能分別在兩端進(jìn)行11、 當(dāng)隊(duì)列的最大長度不能預(yù)估時(shí)，宜采用_。A: 循環(huán)隊(duì)列B: 雙端隊(duì)列C: 順序隊(duì)列D: 鏈隊(duì)列12、 樹的層次遍歷和圖的廣度優(yōu)先搜索常用到_數(shù)據(jù)結(jié)構(gòu)。A: 棧B: 隊(duì)列C: 數(shù)組D: 生成樹13、 非遞歸算法比遞歸算法可讀性好。答案:N14、 遞歸算法總可以轉(zhuǎn)換為非遞歸算法，此時(shí)常需要顯式地使用隊(duì)列結(jié)構(gòu)。答案:N15、 非遞歸算法一般比遞歸算法的運(yùn)行效率要低 。答案:N16、 遞歸算法的表達(dá)相對非遞歸的算法更簡潔，但實(shí)際運(yùn)行效率往往不如后者。答案:Y17、 遞歸算

13、法屬于“好”的算法，即其T(n)已都是關(guān)于n的多項(xiàng)式數(shù)量級。答案15:N 18、 N已知某循環(huán)順序隊(duì)列操作的頭文件如下，試寫出函數(shù)QueueInput(SqQueue &Q) 實(shí)現(xiàn)的算法，可以調(diào)用函數(shù)EnQueue(SqQueue &Q,QElemType e)。19、 試寫出函數(shù)QueueOutput(SqQueue Q) 實(shí)現(xiàn)的算法，可以調(diào)用函數(shù)QueueLength(SqQueue Q,int &len)。20、 試寫出函數(shù)QueueEmpty(SqQueue Q) 實(shí)現(xiàn)的算法。21、 試寫出函數(shù)QueueLength(SqQueue Q,int &len) 實(shí)現(xiàn)的算法。22、 試寫出函

14、數(shù) EnQueue(SqQueue &Q,QElemType e)實(shí)現(xiàn)的算法。23、 試寫出函數(shù)DeQueue(SqQueue &Q,QElemType &e) 實(shí)現(xiàn)的算法。棧和隊(duì)列操作的頭文件：List_QU.h/=/= 1. 預(yù)定義常量和類型/=#define TRUE1#define FALSE0#define OK1#define ERROR0#define INFEASIBLE-1#define OVERFLOW-2typedef intStatus;/Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼。typedef int ElemType;/定義數(shù)據(jù)元素類型取為 int /=/=

15、 2. 定義數(shù)據(jù)結(jié)構(gòu)/=/= 2.6 循環(huán)順序隊(duì)列存儲表示#define MAXQSIZE20/最大隊(duì)列長度typedef struct QElemType *base;/初始化的動(dòng)態(tài)分配存儲空間intfront;/頭指針，若隊(duì)列不空，指向隊(duì)列頭元素;intrear;/尾指針，若隊(duì)列不空，指向隊(duì)列尾元素的下一個(gè)位置;SqQueue;/=/= 3. 定義基本操作/=/= 3.6 循環(huán)順序隊(duì)列基本操作StatusQueueInput(SqQueue &Q);/通過輸入數(shù)據(jù)建立循環(huán)順序隊(duì)列StatusEnQueue(SqQueue &Q,QElemType e);/入隊(duì)/=/ The end of

16、List.h /=4.1 串類型的定義4.2 串的表示和實(shí)現(xiàn)4.3 串的模式匹配算法.4.4 串操作應(yīng)用舉例1、 _是一種特殊的線性表，其數(shù)據(jù)元素最為簡單，僅是單個(gè)字符。A: 串B: 隊(duì)列 C: 數(shù)組 D: 生成樹 2、 子串定位運(yùn)算又稱為_。A: 查找 B: 排序 C: 替換 D: 模式匹配 3、 串的長度表示有多種，PASCAL采用的方法是_。A: 串長用獨(dú)立的單元存儲，通常為第一個(gè)元素 B: 串長用獨(dú)立的單元存儲，通常為最后一個(gè)元素 C: 在串的末尾設(shè)結(jié)束標(biāo)記0 D: 在串的末尾用回車表示 4、 串的長度表示有多種，C語言采用的方法是_。A: 串長用獨(dú)立的單元存儲，通常為第一個(gè)元素 B:

17、 串長用獨(dú)立的單元存儲，通常為最后一個(gè)元素 C: 在串的末尾設(shè)結(jié)束標(biāo)記0 D: 在串的末尾用回車表示 5、 串的長度表示有多種，C語言采用的方法是_。A: 串長用第一個(gè)元素存儲 B: 在串的末尾設(shè)結(jié)束標(biāo)記0 C: 在串的末尾用雙引號表示 D: 串長用獨(dú)立的單元存儲，但不一定是第1個(gè)元素6、 _不是常見的串表示方法。A: 定長順序存儲表示法 B: 堆分配存儲表示法 C: 塊鏈存儲表示 D: 循環(huán)隊(duì)列 1、 已知某字符串操作的頭文件，試寫出函數(shù) StrCompare(HString S,HString T) 實(shí)現(xiàn)的算法。2、 已知某字符串操作的頭文件，試寫出函數(shù) Concat(HString &T

18、,HString S1, HString S2) 實(shí)現(xiàn)的算法。3、 已知某字符串操作的頭文件，試寫出函數(shù) SubString(HString &Sub,HString S,int pos,int len) 實(shí)現(xiàn)的算法。4、 已知某字符串操作的頭文件，試寫出函數(shù) Index(HString S,HString T,int pos) 實(shí)現(xiàn)的算法，可以調(diào)用函數(shù)StrLength(HString &T)。5、 已知某字符串操作的頭文件，試寫出函數(shù) StrInsert(HString &S,int pos,HString T) 實(shí)現(xiàn)的算法，可以調(diào)用函數(shù)StrAssign(HString &T, char

19、 * chars)和StrLength(HString &T)。6、 已知某字符串操作的頭文件，試寫出函數(shù) StrDelete(HString &S,int pos,int len) 實(shí)現(xiàn)的算法，可以調(diào)用函數(shù)StrAssign(HString &T, char * chars)和StrLength(HString &T)。串操作的頭文件：List_STR.h/=/= 1. 預(yù)定義常量和類型/=#define TRUE1#define FALSE0#define OK1#define ERROR0#define INFEASIBLE-1#define OVERFLOW-2typedef intS

20、tatus;/Status是函數(shù)的類型，其值是函數(shù)結(jié)果狀態(tài)代碼。typedef int ElemType;/定義數(shù)據(jù)元素類型取為 int /=/= 2. 定義數(shù)據(jù)結(jié)構(gòu)/=/= 2.8 串的定長順序存儲表示/= 2.9 串的堆分配存儲表示typedef structchar *ch; /若是非空串,則按串長分配存儲區(qū),否則ch為NULLint length; /串長度HString; 5.1 數(shù)組的定義 5.2 數(shù)組的順序表示和實(shí)現(xiàn) 5.3 矩陣的壓縮存儲 5.4 廣義表的定義 5.5 廣義表的存儲結(jié)構(gòu) 5.6 m元多項(xiàng)式的表示*5.7 廣義表的遞歸算法*1、 一維數(shù)組可以看成是一個(gè)簡單的_。A

21、: 串B: 棧C: 隊(duì)列 D: 線性表 2、 二維數(shù)組也可看成是一個(gè)線性表，其中每一個(gè)元素是_。A: 具有相同長度的一維數(shù)組 B: 具有不同長度的一維數(shù)組 C: 具有相同長度的隊(duì)列或棧 D: 具有不同長度的隊(duì)列或棧 3、 二維數(shù)組中的元素最多可有_個(gè)直接前驅(qū)（邊界除外）。A: 1 B: 2 C: 3D: 4 4、 N維數(shù)組也可看成是一個(gè)線性表，其中每一個(gè)元素是_。A: 具有不同長度的N-1維數(shù)組B: 具有相同長度的N-1維數(shù)組C: 具有不同長度的N-2維數(shù)組D: 具有相同長度的N-2維數(shù)組5、 _特點(diǎn)是：其矩陣階數(shù)很大，非零元個(gè)數(shù)較少，零元很多，但非零元的排列沒有一定規(guī)律。A: 對稱矩陣 B:

22、 對角矩陣 C: 三角矩陣 D: 稀疏矩陣 6、 _不是稀疏矩陣的存儲方法。A: 循環(huán)隊(duì)列 B: 三元組表 C: 帶行指針的鏈表 D: 十字鏈表 7、 廣義表是線性表的推廣，其表中的元素_。A: 是多個(gè)線性表 B: 是多個(gè)數(shù)組 C: 可以具有不同的結(jié)構(gòu) D: 不可以有不同的結(jié)構(gòu) 8、 _在人工智能等領(lǐng)域得到了廣泛的應(yīng)用，通常其第一個(gè)元素稱為表頭，其余元素組成表尾。A: 鏈表 B: 散列表 C: 順序表 D: 廣義表 1.有一個(gè)二維數(shù)A，行下標(biāo)的范圍是0到8，列下標(biāo)的范圍是1到5，每個(gè)數(shù)組元素用相鄰的2個(gè)字節(jié)存儲。存儲器按字節(jié)編址。 假設(shè)存儲數(shù)組元素A0，1的第一個(gè)字節(jié)的地址是0。若按列存儲，則

23、A1，3的地址是_。2.有一個(gè)二維數(shù)A，行下標(biāo)的范圍是1到10，列下標(biāo)的范圍是0到5，每個(gè)數(shù)組元素用相鄰的2個(gè)字節(jié)存儲。存儲器按字節(jié)編址。 假設(shè)存儲數(shù)組元素A1，0的第一個(gè)字節(jié)的地址是1。若按列存儲，則A2，3的地址是_。編程題1、/= 稀疏矩陣三元組的相加操作Status AddSMatrix(TSMatrix A,TSMatrix B,TSMatrix &C);/矩陣相加A+B-C2、 /= 稀疏矩陣三元組的相減操作Status SubSMatrix(TSMatrix A,TSMatrix B,TSMatrix &C);/矩陣相減A-B-C3、 /= 稀疏矩陣三元組的轉(zhuǎn)置操作Status

24、TransposeSMatrix(TSMatrix S,TSMatrix &T);/求矩陣S的轉(zhuǎn)置矩陣T4、 /= 稀疏矩陣三元組的相乘操作Status MulSMatrix(TSMatrix A,TSMatrix B,TSMatrix &C);/矩陣相乘A=B*C 6.1 樹的定義和基本術(shù)語6.2 二叉樹6.3 遍歷二叉樹和線索二叉樹6.4 樹和森林6.5 樹與等價(jià)問題6.6 赫夫曼樹及其應(yīng)用6.7 回溯法與樹的遍歷6.8 樹的計(jì)數(shù) 1、 對非完全二叉樹而言，采用_存儲結(jié)構(gòu)會浪費(fèi)許多存儲空間。A: 順序B: 鏈?zhǔn)紺: 索引D: 散列2、 對完全二叉樹而言，采用順序存儲結(jié)構(gòu)_。A: 遍歷算法效

25、率低B: 刪除算法效率低C: 會浪費(fèi)許多存儲空間D: 不會浪費(fèi)許多存儲空間3、 采用雙親表示的樹的存儲結(jié)構(gòu)，其特點(diǎn)是：從當(dāng)前結(jié)點(diǎn)出發(fā)_。A: 容易找到雙親和其孩子B: 容易找到雙親和根結(jié)點(diǎn)C: 容易找到孩子，但不易找到其雙親D: 容易找到雙親，但不易找到其孩子4、 樹的度是指樹內(nèi)各結(jié)點(diǎn)_。A: 度的最小值B: 度的最大值C: 度的平均值D: 度的累加值5、 樹是n(n=0)個(gè)結(jié)點(diǎn)的有限集。在任意一棵非空樹中：有且僅有一個(gè)特定的稱為_的結(jié)點(diǎn)。根6、 樹是n(n=0)個(gè)結(jié)點(diǎn)的有限集。當(dāng)n1時(shí),其余結(jié)點(diǎn)可分為m(m0)個(gè)互不相交的有限集T1,T2,.Tm,其中每一個(gè)集合稱為根的_。子樹7、 多棵互不

26、相交的樹的集合稱為_。森林8、 _常用于二叉樹的存儲結(jié)構(gòu)，其特點(diǎn)是：從當(dāng)前結(jié)點(diǎn)出發(fā)能馬上找到其左右子樹，也能直接找到其雙親。三叉鏈表9、 _常用于二叉樹的存儲結(jié)構(gòu)，其特點(diǎn)是：從當(dāng)前結(jié)點(diǎn)出發(fā)能馬上找到其左右子樹，但不能直接找到其雙親。二叉鏈表10、 樹中的終端結(jié)點(diǎn)又稱_。葉結(jié)點(diǎn)11、 樹中的非終端結(jié)點(diǎn)又稱_。分支結(jié)點(diǎn)12、 樹中的葉結(jié)點(diǎn)是指度為_的結(jié)點(diǎn)。013、 樹中結(jié)點(diǎn)的_是指該結(jié)點(diǎn)擁有子樹的數(shù)目。度14、 一棵樹從根到某結(jié)點(diǎn)所經(jīng)分支上的所有結(jié)點(diǎn)都是該結(jié)點(diǎn)的_。祖先15、 以某結(jié)點(diǎn)為根的子樹中的任一結(jié)點(diǎn)都稱為該結(jié)點(diǎn)的_。子孫16、 通常規(guī)定樹中根的孩子為第_層結(jié)點(diǎn)。217、 _的邏輯特征是：每

27、個(gè)數(shù)據(jù)元素至多有一個(gè)直接前趨和二個(gè)直接后繼。二叉樹18、 樹的邏輯特征是：每個(gè)數(shù)據(jù)元素至多有一個(gè)直接前趨和_個(gè)直接后繼。多19、 樹中的_結(jié)點(diǎn)沒有直接前趨，但有多個(gè)直接后繼。根20、 樹中的_結(jié)點(diǎn)沒有直接后繼，但有一個(gè)直接前趨。葉21、 二叉樹可有_種不同的形態(tài)。522、 二叉樹的度不大于_。223、 二叉樹的第3層上至多有個(gè)_結(jié)點(diǎn)。424、 深度為3的二叉樹至多有_個(gè)結(jié)點(diǎn)。725、 二叉樹的第_層上至多有個(gè)4結(jié)點(diǎn)。326、 二叉樹的第_層上至多有個(gè)8結(jié)點(diǎn)。427、 深度為_的二叉樹至多有15個(gè)結(jié)點(diǎn)。428、 二叉樹的第_層上至多有個(gè)32結(jié)點(diǎn)。629、 先序遍歷二叉樹算法的時(shí)間復(fù)雜度T(n)為

28、_（設(shè)二叉樹的結(jié)點(diǎn)數(shù)為n）。O(n)30、 中序遍歷二叉樹算法的時(shí)間復(fù)雜度T(n)為_（設(shè)二叉樹的結(jié)點(diǎn)數(shù)為n）。O(n) 31、 中序遍歷二叉樹算法在最壞情況下的空間復(fù)雜度S(n)為_（設(shè)二叉樹的結(jié)點(diǎn)數(shù)為n）。O(n) 32、 后序遍歷二叉樹算法的時(shí)間復(fù)雜度T(n)為_（設(shè)二叉樹的結(jié)點(diǎn)數(shù)為n）。O(n)33、 *將下面的森林轉(zhuǎn)化成一棵二叉樹。34、 *將下面的二叉樹轉(zhuǎn)化成樹或森林35、 *已知一棵二叉樹結(jié)點(diǎn)的前序序列和中序序列，請構(gòu)造出這棵二叉樹。前序序列：A-B-D-H-I-E-J-C-F-G 中序序列：H-D-I-B-E-J-A-F-C-G36、 *某通信電文由5 個(gè)字母組成，它們的出現(xiàn)概

29、率如下表所示，將這些概率大小作為5個(gè)字母結(jié)點(diǎn)所對應(yīng)的權(quán)，試畫出相應(yīng)的赫夫曼樹和赫夫曼編碼。要求概率較小的結(jié)點(diǎn)作為左孩子結(jié)點(diǎn)，概率較大的結(jié)點(diǎn)作為右孩子結(jié)點(diǎn);連接左孩子的連線對應(yīng)編碼0，連接右孩子的連線對應(yīng)編碼1。字母 A B C D E 概率 0.18 0.3 0.32 0.05 0.15 37、 *有5個(gè)帶權(quán)的結(jié)點(diǎn)A、B、C、D和E，它們的權(quán)分別如為：20、5、10、60和15。試構(gòu)造一棵擁有這5個(gè)葉結(jié)點(diǎn)的最優(yōu)二叉樹，并求出相應(yīng)的帶權(quán)路徑長度WPL。38、 *已知某二叉樹采用順序存儲結(jié)構(gòu)，其圖示如下（其中“”表示該結(jié)點(diǎn)不存在），請畫出相應(yīng)的二叉樹。 編號 0 1 2 3 4 5 6 7 8 9

30、 10 11 12 13 14 15 結(jié)點(diǎn) A B C D E F G H 39、 已知某二叉樹如下,現(xiàn)采用一維數(shù)組的順序存儲結(jié)構(gòu)來表示，請?zhí)顚懗鲈摱鏄涓鹘Y(jié)點(diǎn)在一維數(shù)組中的位置（結(jié)點(diǎn)不存在的單元可用“”或空來表示）。 40、 判斷：滿二叉樹必定是完全二叉樹或順序二叉樹41、 判斷：完全二叉樹必定是滿二叉樹或順序二叉樹42、 判斷：順序二叉樹不一定是滿二叉樹。43、 判斷：森林至少有三棵樹組成。44、 判斷：森林至少有兩棵以上的二叉樹組成。45、 判斷：一般的樹可以轉(zhuǎn)換成二叉樹，而森林可以轉(zhuǎn)換成兩棵以上的二叉樹。46、 判斷：一棵二叉樹可以轉(zhuǎn)換成一棵普通的樹，但不能轉(zhuǎn)換成森林。47、 判斷：雙

31、親在同一層的結(jié)點(diǎn)互為兄弟結(jié)點(diǎn)。48、 判斷：雙親在同一層的結(jié)點(diǎn)互為堂兄弟結(jié)點(diǎn)。49、 判斷：樹的深度是指樹中最大的分支數(shù)。50、 判斷：樹中結(jié)點(diǎn)的最大層次數(shù)就是樹的高度。51、 判斷：二叉樹是一種無序樹。52、 判斷：有序樹是指所有結(jié)點(diǎn)的孩子有先后之分的樹。53、 判斷：森林是m(m=0)棵互不相交的樹的集合。 54、 已知某二叉樹操作的頭文件，試寫出函數(shù) PreOrderTraverse(BiTree T,Status (*Visit)(TElemType e) 實(shí)現(xiàn)的算法，訪問結(jié)點(diǎn)可調(diào)用函數(shù)Visit(TElemType e)。Status PreOrderTraverse(BiTree

32、T,Status (*Visit)(TElemType e)/=先序遍歷二叉樹T,對每個(gè)結(jié)點(diǎn)調(diào)用函數(shù)Visit一次且僅一次if(T!= _(_)_)Visit(T-data);PreOrderTraverse(_(_)_);_(_)_ (T-rchild,Visit); return OK;/PreOrderTraverse 55、 已知某二叉樹操作的頭文件，試寫出函數(shù) InOrderTraverse(BiTree T,Status (*Visit)(TElemType e) 實(shí)現(xiàn)的算法，訪問結(jié)點(diǎn)可調(diào)用函數(shù)Visit(TElemType e)。56、 已知某二叉樹操作的頭文件，試寫出函數(shù) Po

33、stOrderTraverse(BiTree T,Status (*Visit)(TElemType e) 實(shí)現(xiàn)的算法，訪問結(jié)點(diǎn)可調(diào)用函數(shù)Visit(TElemType e)。57、 已知某二叉樹操作的頭文件如下，試寫出函數(shù) leaf(BiTree T) 實(shí)現(xiàn)的算法。int leaf(BiTree T)/=求二叉樹T的葉結(jié)點(diǎn)if (T = NULL) return (_(_)_);/形態(tài)0if (T-lchild = NULL)& (T-rchild = NULL)return (_(_)_);/形態(tài)1else return (_(_)_);/形態(tài)2-4/leaf58、 已知某二叉樹操作的頭文

34、件，試寫出函數(shù) branch(BiTree T) 實(shí)現(xiàn)的算法。59、 已知某二叉樹操作的頭文件，試寫出函數(shù) node(BiTree T) 實(shí)現(xiàn)的算法。60、 已知某二叉樹操作的頭文件，試寫出函數(shù) depth(BiTree T) 實(shí)現(xiàn)的算法。7.1 圖的定義和術(shù)語 7.2 圖的存儲結(jié)構(gòu) 7.3 圖的遍歷 7.4 圖的連通性問題 7.5 有向無環(huán)圖及其應(yīng)用 7.6 最短路徑 1、 _適用于表示稠密圖。A: 散列表B: 雙鏈表C: 鄰接表D: 鄰接矩陣2、 _適用于表示稀疏圖。A: 鄰接矩陣B: 二叉鏈表C: 散列表D: 鄰接表3、 有向圖的鄰接矩陣_。A: 可能是不對稱的B: 一定是三角矩陣C:

35、一定是不對稱D: 一定是對稱4、 鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。其中采用_表示頂點(diǎn)及有關(guān)信息，稱為頂點(diǎn)表。A: 數(shù)組B: 矩陣C: 單鏈表D: 雙鏈表5、 數(shù)據(jù)結(jié)構(gòu)中，無向圖的邊_。A: 總是與兩個(gè)頂點(diǎn)相連接B: 可以與多個(gè)頂點(diǎn)相連接C: 可以與一個(gè)頂點(diǎn)相連接，另一端不與其他頂點(diǎn)相連D: 可以同時(shí)與一個(gè)頂點(diǎn)相連接，形成環(huán)6、 采用普里姆算（Prim）法構(gòu)造最小生成樹時(shí)，_。A: 只能從某一個(gè)頂點(diǎn)出發(fā)B: 可以從任意一個(gè)邊出發(fā)C: 只能從最小權(quán)的邊開始D: 只能從最大權(quán)的邊開始7、 求解最小生成樹的問題可與_的實(shí)際問題相關(guān)聯(lián)。A: N個(gè)城市間建立通信網(wǎng)絡(luò)B: 一個(gè)城市到N個(gè)城市間的交通運(yùn)輸C:

36、學(xué)生選修多門相關(guān)課程安排D: 一個(gè)工程項(xiàng)目進(jìn)度計(jì)劃安排8、 求解關(guān)鍵路徑的問題可與_的實(shí)際問題相關(guān)聯(lián)。A: N個(gè)城市間建立通信網(wǎng)絡(luò)B: 一個(gè)城市到N個(gè)城市間的交通運(yùn)輸C: 學(xué)生選修多門相關(guān)課程安排D: 一個(gè)工程項(xiàng)目進(jìn)度計(jì)劃安排9、 用有向邊表示一個(gè)工程中的各項(xiàng)活動(dòng)，邊上的權(quán)值表示活動(dòng)持續(xù)時(shí)間的有向無環(huán)圖，簡稱為_。A: 拓?fù)渚W(wǎng)絡(luò)B: 關(guān)鍵路徑C: AOV網(wǎng)D: AOE網(wǎng)10、 AOV網(wǎng)中的頂點(diǎn)表示_。A: 最短路徑B: 活動(dòng)C: 活動(dòng)的前后次序D: 活動(dòng)的持續(xù)時(shí)間11、 AOE網(wǎng)中有向邊的權(quán)值表示_。A: 活動(dòng)B: 事件C: 活動(dòng)的前后次序D: 活動(dòng)的持續(xù)時(shí)間12、 判斷：網(wǎng)絡(luò)是一種有向圖。N

37、13、 判斷：完全圖中任何二個(gè)結(jié)點(diǎn)間都有一條邊。Y14、 判斷：圖中任何結(jié)點(diǎn)都應(yīng)該有一條邊或弧與其相連。N15、 判斷：圖中有些邊可以只有一個(gè)端點(diǎn)。N16、 判斷：起點(diǎn)和終點(diǎn)相同的路徑稱為簡單回路或簡單環(huán)。N17、 判斷：無向圖的極大連通子圖叫做連通分量。Y18、 圖是由_集合及其之間的關(guān)系集合組成的一種數(shù)據(jù)結(jié)構(gòu)。Vertex19、 圖的數(shù)據(jù)結(jié)構(gòu)G( V, E )，其中E = (x, y) | x, y V 是_的集合。edge 20、 _相對較少的圖稱為稀疏圖。edge 21、 在一個(gè)有向圖中，一個(gè)頂點(diǎn)v的入度就是與它相關(guān)聯(lián)的_的個(gè)數(shù)。弧頭(Head) 22、 _的鄰接矩陣是對稱的。無向圖2

38、3、 鄰接表是圖的一種鏈?zhǔn)酱鎯Y(jié)構(gòu)。其中依附于頂點(diǎn)vi的邊由vi指向的一個(gè)_表示。單鏈表24、 用頂點(diǎn)表示活動(dòng)，有向邊 表示活動(dòng)的前后次序的有向無環(huán)圖，簡稱為_。AOV25、 圖的邏輯特征是每個(gè)數(shù)據(jù)元素可以有_個(gè)直接前趨和多個(gè)直接后繼。多26、 有10個(gè)頂點(diǎn)的連通圖至少有_條邊。927、 已知無向圖G1如下，列出相應(yīng)的鄰接矩陣。 G1.arcs= 28、 已知有向圖G的鄰接矩陣1如下，請畫出相應(yīng)圖。G1.arcs= 29、 根據(jù)下面給定的網(wǎng)，試按Prim算法，寫出從V1出發(fā)構(gòu)建最小代價(jià)生成樹的過程（要求畫出開始的兩個(gè)中間過程和最終的最小代價(jià)生成樹）。30、 根據(jù)下面給定的網(wǎng)，試按Kruskal

39、算法，寫出構(gòu)建最小代價(jià)生成樹的過程（要求畫出開始的兩個(gè)中間過程和最終的最小代價(jià)生成樹）。31、 已知某無向圖的鄰接表如下所示，基于該鄰接表按深度優(yōu)先搜索，寫出從V1出發(fā)遍歷各結(jié)點(diǎn)的次序，并畫出該無向圖。遍歷各結(jié)點(diǎn)的次序：V1,V4,V5,V3,V2,V7,V8,V6 32、 已知某無向圖的鄰接表如下所示，基于該鄰接表按廣度優(yōu)先搜索，寫出從V1出發(fā)遍歷各結(jié)點(diǎn)的次序，并畫出該無向圖。 遍歷各結(jié)點(diǎn)的次序：V1,V3,V4,V5,V7,V6,V8,V2 編程題33、 已知某圖的基本操作的頭文件如下，試寫出函數(shù) Get_Degree(ALGraph &G) 實(shí)現(xiàn)的算法。/= 1. 預(yù)定義常量和類型/=

40、2. 定義數(shù)據(jù)結(jié)構(gòu)/= 2.2 鄰接表存儲表示#define MAX_VERTEX_NUM 20typedef enumDG,DN,AG,AN GraphKind;/有向圖，有向網(wǎng)，無向圖，無向網(wǎng)typedef struct ArcNodeint adjvex;/該弧所指向的頂點(diǎn)的位置struct ArcNode *nextarc;/指向下一條弧的指針int Weight;/該弧相關(guān)信息:權(quán)重ArcNode;typedef struct VNodeVertexType data;/頂點(diǎn)信息int InDegree,OutDegree;/頂點(diǎn)的入度和出度ArcNode *firstarc;/指向

41、第一條依附該頂點(diǎn)的弧的指針VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum,arcnum; /圖的當(dāng)前頂點(diǎn)數(shù)和弧數(shù)GraphKind kind; /圖的種類標(biāo)志ALGraph;/= 3. 定義基本操作/= 3.2 圖的鄰接表存儲表示的基本操作Status Get_Degree(ALGraph &G);/計(jì)算入度和出度Status Get_Degree(ALGraph &G)/計(jì)算入度和出度int i;ArcNode*t;for(i=0; iadjvex.InDegree+;while (t-nexta

42、rc!= _(_)_) t= t-nextarc;G.verticesi.OutDegree+;G.verticest-adjvex.InDegree+;return OK;/Get_Degree 9.1 靜態(tài)查找表 9.2 動(dòng)態(tài)查找表 9.3 哈希表 1、 在查找操作中，如查找成功，則結(jié)果給出的是_。A: 查找表的長度B: 成功比較的次數(shù)C: 失敗比較的次數(shù)D: 關(guān)鍵字等于給定值的記錄2、 查找操作的功能是：在查找表中確定一個(gè)_等于給定值的記錄或數(shù)據(jù)元素。A: 關(guān)鍵字B: 數(shù)據(jù)項(xiàng)C: 結(jié)點(diǎn)D: 指針4、 靜態(tài)查找表_。A: 僅能完成查詢和檢索操作，不能進(jìn)行插入和刪除操作B: 不僅能完成查詢和

43、檢索操作，也能進(jìn)行插入和刪除操作C: 不能完成查詢和檢索操作，但能進(jìn)行插入和刪除操作D: 不能完成查詢和檢索操作，也不能進(jìn)行插入和刪除操作5、 動(dòng)態(tài)查找表_。A: 僅能完成查詢和檢索操作，不能進(jìn)行插入和刪除操作B: 不僅能完成查詢和檢索操作，也能進(jìn)行插入和刪除操作C: 不能完成查詢和檢索操作，但能進(jìn)行插入和刪除操作D: 不能完成查詢和檢索操作，也不能進(jìn)行插入和刪除操作6、 _的特點(diǎn)是：查找效率與查找對象的規(guī)模N無直接關(guān)系，而與裝填因子、解決沖突的方法有關(guān)。A: 鏈表B: 順序表C: 索引表D: 散列表7、 哈希表的平均查找長度與_。A: 與裝填因子和表的長度有關(guān)B: 與裝填因子和表的長度都無關(guān)

44、C: 與裝填因子、解決沖突的方法有關(guān)，而與表的長度無關(guān)D: 與裝填因子、解決沖突的方法無關(guān)，而與表的長度有關(guān)8、 _需要有解決沖突的方法。A: 順序查找B: 二分查找C: 散列表查找D: 二叉樹查找 9、 順序查找不適用于單鏈表。N10、 二分查找不適用于單鏈表。Y11、 順序查找要求查找表有序。N12、 二分查找要求查找表有序。Y13、 順序表既可適用二分查找又可適用順序查找。Y14、 雙鏈表既可適用二分查找又可適用順序查找。N表中位置 0 1 2 3 4 5 6 7 8 9 10 關(guān)鍵字k 25 H(k) 3 查找次數(shù) 1 15、 設(shè)有一組關(guān)鍵字，其出現(xiàn)次序?yàn)椋?5、37、9、35、21、

45、36、45、31。要求用哈希(Hash)方法將存入長度為11個(gè)位置的表中。取哈希函數(shù)H(k)= k mod 11。試求出各關(guān)鍵字的哈希函數(shù)H(k)的值。假定采用步長為1的線性探測再散列法解決沖突(增量序列di=1,2,3,)，寫出關(guān)鍵字在表中的位置和相應(yīng)的查找次數(shù)，并求出平均查找長度ASL。表中位置 0 1 2 3 4 5 6 7 8 9 10 關(guān)鍵字k 25 H(k) 3 查找次數(shù) 1 平均查找長度ASL=(3+1+1+1+1+3+1+1)/8=1.5 16、 設(shè)有一組關(guān)鍵字，其出現(xiàn)次序?yàn)椋?1、23、18、47、30、19、37、5、40。要求用哈希(Hash)方法將存入長度為13個(gè)位置的

46、表中。取哈希函數(shù)H(k)= k mod 13。試求出各關(guān)鍵字的哈希函數(shù)H(k)的值。假定采用二次探測再散列法解決沖突(增量序列di=1,1，22,22,)，寫出關(guān)鍵字在表中的位置和相應(yīng)的查找次數(shù)，并求出平均查找長度ASL。 表中位置 0 1 2 3 4 5 6 7 8 9 10 11 12 關(guān)鍵字k 41 H(k) 2 查找次數(shù) 1 表中位置 0 1 2 3 4 5 6 7 8 9 10 11 12 關(guān)鍵字k 41 H(k) 2 查找次數(shù) 1 平均查找長度ASL=(8*1+4)/9=12/9=1.56 10.1概述10.2插入排序10.3快速排序10.4選擇排序10.5歸并排序10.6基數(shù)排序

47、10.7各種內(nèi)部排序方法的比較討論 1、 起泡排序?qū)儆赺。A: 插入排序B: 交換排序C: 選擇排序D: 歸并排序2、 快速排序?qū)儆赺。A: 插入排序B: 交換排序C: 選擇排序D: 歸并排序3、 堆排序?qū)儆赺。A: 插入排序B: 交換排序C: 選擇排序D: 歸并排序4、 _是穩(wěn)定的。A: 堆排序B: 希爾排序C: 快速排序D: 二路歸并排序5、 _是不穩(wěn)定的。A: 快速排序B: 冒泡排序C: 直接插入排序D: 二路歸并排序6、 _需要占用的存儲空間相對較大。A: 快速排序B: 直接選擇排序C: 直接插入排序D: 二路歸并排序7、排序算法的穩(wěn)定性是指：是否允許出現(xiàn)關(guān)鍵字相同的數(shù)據(jù)元素。N8、排

48、序算法的穩(wěn)定性是指：關(guān)鍵字相同的數(shù)據(jù)對象在排序過程中是否保持前后次序不變。Y9、 內(nèi)排序是指排序過程全部在內(nèi)存中進(jìn)行。Y10、 外排序的排序過程要使用到外部存儲器，而不使用內(nèi)部存儲器。N11、 有n個(gè)關(guān)鍵字的序列K1,K2,Kn稱為小根堆，當(dāng)且僅當(dāng)KiK2i 且 _。12、 有n個(gè)關(guān)鍵字的序列K1,K2,Kn稱為大根堆，當(dāng)且僅當(dāng)KiK2i 且 _。13、 順序查找的平均時(shí)間復(fù)雜度T(n)為_。14、 二分查找的平均時(shí)間復(fù)雜度T(n)為_。15、 直接插入排序的空間復(fù)雜度S(n)為_。16、 快速排序的時(shí)間復(fù)雜度T(n)為_。 17、 快速排序的空間復(fù)雜度S(n) 為_。18、 直接選擇排序的時(shí)

49、間復(fù)雜度T(n)為_。19、 直接選擇排序的空間復(fù)雜度S(n) 為_。20、 堆排序的時(shí)間復(fù)雜度T(n)為_。21、 堆排序的空間復(fù)雜度S(n) 為_。22、 二路歸并的時(shí)間復(fù)雜度T(n) 為_。 23、 二路歸并的空間復(fù)雜度S(n) 為_。24、 冒泡排序的時(shí)間復(fù)雜度T(n)為_。25、 起泡排序的空間復(fù)雜度S(n) 為_。26、 樹形選擇排序的時(shí)間復(fù)雜度T(n) 為_。27、 錦標(biāo)賽排序的時(shí)間復(fù)雜度T(n) 為_。28、 后序遍歷二叉樹算法在最壞情況下的空間復(fù)雜度S(n)為_（設(shè)二叉樹的結(jié)點(diǎn)數(shù)為n）。 已知關(guān)鍵字序列，畫出快速排序第一次遞歸劃分后的結(jié)果。i r1 r2 r3 r4 r5 r

50、6 r7 r8 57 49 32 86 12 65 57* 28 1 28 49 32 12 57 65 57* 86 2 12 28 32 49 57 57* 65 86 已知關(guān)鍵字序列，畫出選擇排序前兩次排序后的結(jié)果i r1 r2 r3 r4 r5 r6 r7 r8 57 49 32 86 57* 65 12 28 1 12 49 32 86 57* 65 57 282 12 28 32 86 57* 65 57 49 .已知關(guān)鍵字序列，畫出堆排序第一次的建堆過程i r1 r2 r3 r4 r5 r6 r7 r8 28 49 32 86 12 65 77 511 86 51 77 49 1

51、2 65 32 28已知關(guān)鍵字序列，畫出堆排序第二次的建堆過程i r1 r2 r3 r4 r5 r6 r7 r8 28 49 32 86 12 65 77 512 77 51 65 49 12 28 32 86 已知關(guān)鍵字序列，畫出鏈?zhǔn)交鶖?shù)排序的2次分配和收集過程編程題29、 已知某排序基本操作的頭文件如下，試寫出插入排序函數(shù) InsertSort(SqList &L) 實(shí)現(xiàn)的算法。/= 1. 預(yù)定義常量和類型/= 2. 定義數(shù)據(jù)結(jié)構(gòu)/= 2.1 待排序的數(shù)據(jù)表的存儲表示#define MAXSIZE 20/數(shù)據(jù)表的最大長度typedef struct KeyType key;/關(guān)鍵字Info

52、Type otherinfo;/其他數(shù)據(jù)項(xiàng)RcdType;/記錄類型typedef struct RcdType rMAXSIZE+1;/r0閑置或用作哨兵單元int length;/順序表長度SqList;/順序表類型/= 2.2 采用順序表存儲表示的堆typedef SqList HeapType;/= 3. 定義基本操作/= 3.1 插入排序void InsertSort(SqList &L) /直接插入排序int i,j;for(i=2;i=L.length;i+)/=比較if(LT(L.ri.key,L.ri-1.key) L.r0= L.ri;L.ri= _(_)_;/=后移for(j=i-2;LT(L.r0.key,L.rj.key);-j)L.rj+1= _(_)_;/=插入L.rj+1= _(_)_;Output_Data_List1(L,i);/=輸出中間結(jié)果/InsertSort 30.已知某排序基本操作的頭文件，試寫出快速排序函數(shù) QSort(SqList &L,int low,int high)實(shí)現(xiàn)的算法，可以調(diào)用Partition(SqList &L,int low,i