數(shù)據(jù)結構習題

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

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

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

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

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

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

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

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

9、#define OK1#define ERROR0#define INFEASIBLE-1#define OVERFLOW-2typedef intStatus;/Status是函數(shù)的類型，其值是函數(shù)結果狀態(tài)代碼。typedef int ElemType;/定義數(shù)據(jù)元素類型取為 int /=/= 2. 定義數(shù)據(jù)結構/=/= 2.2 單鏈表存儲結構(帶頭結點的線性鏈表)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個結點位置送至p /=/ The end of List.h /= 3.1 棧3.2 棧的應用舉例 3.3 棧與遞歸的實現(xiàn)*3.4 隊列 1、 _是限定僅在表的一端（通常為表尾）進行插入或刪除操作的線性表。A: 隊列B: 棧C: 串D: 樹2、 對棧的操作所具有的特征為_。A: “先進先出” B: “后進后出” C: “先進后出” D: 上面三者都不是3、 _是棧的典型操作。A: Enqueue B: Dequeue C:

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

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

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

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

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

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

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

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

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

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

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

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

23、A1，3的地址是_。2.有一個二維數(shù)A，行下標的范圍是1到10，列下標的范圍是0到5，每個數(shù)組元素用相鄰的2個字節(jié)存儲。存儲器按字節(jié)編址。 假設存儲數(shù)組元素A1，0的第一個字節(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、 /= 稀疏矩陣三元組的轉置操作Status

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

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

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

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

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

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

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

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

32、T,Status (*Visit)(TElemType e)/=先序遍歷二叉樹T,對每個結點調(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) 實現(xiàn)的算法，訪問結點可調(diào)用函數(shù)Visit(TElemType e)。56、 已知某二叉樹操作的頭文件，試寫出函數(shù) Po

33、stOrderTraverse(BiTree T,Status (*Visit)(TElemType e) 實現(xiàn)的算法，訪問結點可調(diào)用函數(shù)Visit(TElemType e)。57、 已知某二叉樹操作的頭文件如下，試寫出函數(shù) leaf(BiTree T) 實現(xiàn)的算法。int leaf(BiTree T)/=求二叉樹T的葉結點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) 實現(xiàn)的算法。59、 已知某二叉樹操作的頭文件，試寫出函數(shù) node(BiTree T) 實現(xiàn)的算法。60、 已知某二叉樹操作的頭文件，試寫出函數(shù) depth(BiTree T) 實現(xiàn)的算法。7.1 圖的定義和術語 7.2 圖的存儲結構 7.3 圖的遍歷 7.4 圖的連通性問題 7.5 有向無環(huán)圖及其應用 7.6 最短路徑 1、 _適用于表示稠密圖。A: 散列表B: 雙鏈表C: 鄰接表D: 鄰接矩陣2、 _適用于表示稀疏圖。A: 鄰接矩陣B: 二叉鏈表C: 散列表D: 鄰接表3、 有向圖的鄰接矩陣_。A: 可能是不對稱的B: 一定是三角矩陣C:

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

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

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

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

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

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

41、第一條依附該頂點的弧的指針VNode,AdjListMAX_VERTEX_NUM;typedef struct AdjList vertices; int vexnum,arcnum; /圖的當前頂點數(shù)和弧數(shù)GraphKind kind; /圖的種類標志ALGraph;/= 3. 定義基本操作/= 3.2 圖的鄰接表存儲表示的基本操作Status Get_Degree(ALGraph &G);/計算入度和出度Status Get_Degree(ALGraph &G)/計算入度和出度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 動態(tài)查找表 9.3 哈希表 1、 在查找操作中，如查找成功，則結果給出的是_。A: 查找表的長度B: 成功比較的次數(shù)C: 失敗比較的次數(shù)D: 關鍵字等于給定值的記錄2、 查找操作的功能是：在查找表中確定一個_等于給定值的記錄或數(shù)據(jù)元素。A: 關鍵字B: 數(shù)據(jù)項C: 結點D: 指針4、 靜態(tài)查找表_。A: 僅能完成查詢和檢索操作，不能進行插入和刪除操作B: 不僅能完成查詢和

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

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

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

46、表中。取哈希函數(shù)H(k)= k mod 13。試求出各關鍵字的哈希函數(shù)H(k)的值。假定采用二次探測再散列法解決沖突(增量序列di=1,1，22,22,)，寫出關鍵字在表中的位置和相應的查找次數(shù)，并求出平均查找長度ASL。 表中位置 0 1 2 3 4 5 6 7 8 9 10 11 12 關鍵字k 41 H(k) 2 查找次數(shù) 1 表中位置 0 1 2 3 4 5 6 7 8 9 10 11 12 關鍵字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)關鍵字相同的數(shù)據(jù)元素。N8、排

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

49、間復雜度T(n)為_。19、 直接選擇排序的空間復雜度S(n) 為_。20、 堆排序的時間復雜度T(n)為_。21、 堆排序的空間復雜度S(n) 為_。22、 二路歸并的時間復雜度T(n) 為_。 23、 二路歸并的空間復雜度S(n) 為_。24、 冒泡排序的時間復雜度T(n)為_。25、 起泡排序的空間復雜度S(n) 為_。26、 樹形選擇排序的時間復雜度T(n) 為_。27、 錦標賽排序的時間復雜度T(n) 為_。28、 后序遍歷二叉樹算法在最壞情況下的空間復雜度S(n)為_（設二叉樹的結點數(shù)為n）。 已知關鍵字序列，畫出快速排序第一次遞歸劃分后的結果。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 已知關鍵字序列，畫出選擇排序前兩次排序后的結果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 .已知關鍵字序列，畫出堆排序第一次的建堆過程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已知關鍵字序列，畫出堆排序第二次的建堆過程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 已知關鍵字序列，畫出鏈式基數(shù)排序的2次分配和收集過程編程題29、 已知某排序基本操作的頭文件如下，試寫出插入排序函數(shù) InsertSort(SqList &L) 實現(xiàn)的算法。/= 1. 預定義常量和類型/= 2. 定義數(shù)據(jù)結構/= 2.1 待排序的數(shù)據(jù)表的存儲表示#define MAXSIZE 20/數(shù)據(jù)表的最大長度typedef struct KeyType key;/關鍵字Info

52、Type otherinfo;/其他數(shù)據(jù)項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);/=輸出中間結果/InsertSort 30.已知某排序基本操作的頭文件，試寫出快速排序函數(shù) QSort(SqList &L,int low,int high)實現(xiàn)的算法，可以調(diào)用Partition(SqList &L,int low,i