• 目錄
  第一章緒論練習
  第二章線性表
  第三章棧和隊列
  第四章串
  第五章數組和廣義表
  第六章樹和二叉樹
  第七章圖
  第九章查找
  第十章排序

第一章緒論練習

1-8 數據結構的抽象操作的定義與具體實現有關。 (1分)

• T
• F

1-14 數據結構包括數據對象集以及它們的邏輯結構和物理結構，還包括與數據對象相關聯的操作集，以及實現這些操作的高效的算法。 (1分)

• T
• F

2-10 下面關于抽象數據類型的描述，不正確的是（ ）。 (2分)

• A. 數據封裝
• B. 使用與實現分離
• C. 信息隱藏
• D. 用例驅動

2-12 以下關于數據結構的說法中正確的是____。 (2分)

• A 數據結構的邏輯結構獨立于其存儲結構
• B 數據結構的存儲結構獨立于該數據結構的邏輯結構
• C 數據結構的邏輯結構唯一地決定了該數據結構的存儲結構
• D 數據結構僅由其邏輯結構和存儲結構決定

4-2 存儲結構* 數據的存儲結構包含兩個方面：

____的表示，是數據元素在計算機中的映像；

___ 的表示，是指數據元素之間的關系在計算機中的表示方法。

4-5 基本概念*
_____ 一般指由用戶定義的、表示應用問題的數學模型，以及定義在該模型上的一組操作。

4-9 數據結構由___、___和___三部分組成。

4-14 基本概念* 按值的不同特性，在高級語言中的數據類型可分為兩大類：
(1) ____：值不可分解；
(2) ____：值由若干成分組成，可分解，其成分可是以 (1)，也可以是 (2)。

**緒論答案：1-8F 1-14T 2-10D 2-12A 4-2數據元素 關系 4-5抽象數據類型 4-9邏輯結構 存儲結構 運算 4-14原子類型 結構類型**

第二章線性表

pta

1-5 將長度分別為m,n的兩個單鏈表合并為一個單鏈表的時間復雜度為O(m+n)。

• T
• F
  時間復雜度為O(1)，如果是兩個有序鏈表合成一個有序鏈表的時間復雜度為O(M + N)

1-15 所謂“循環隊列”是指用單向循環鏈表或者循環數組表示的隊列。

• T
• F
  所謂“循環隊列”是指用循環數組表示的隊列

1-16在具有頭結點的鏈式存儲結構中，頭指針指向鏈表中的第一個元素結點。

• T
• F
  頭指針指向頭結點

2-12 順序表中第一個元素的存儲地址是100，每個元素的長度為2，則第5個元素的地址是（ ）。

• A 100
• B 105
• C 108
• D 110

答案：1-5F 1-15 F 1-16F 2-12C

課后題

1、編寫算法，實現帶頭結點單鏈表的逆置算法。

void ReverseList( LinkList &Head ) {// 將Head 所指的帶頭結點的單鏈表逆置 if( Head->next && Head->next->next){//當鏈表不是空表或單結點時p=Head->next;q=p->next; p -> next=NULL;//將開始結點變成終端結點while (q) {//每次循環將后一個結點變成開始結點p=q; q=q->next ;//先將指針同步后移一位p->next = Head-> next;Head->next = p;//然后將p指針提到第一個位置去} }

第三章棧和隊列

pta

2-19
如果循環隊列用大小為m的數組表示，隊頭位置為front、隊列元素個數為size，那么隊尾元素位置rear為： (2分)

• A front+size
• B front+size-1
• C (front+size)%m
• D (front+size-1)%m

答案：2-19D

應用舉例

1、數制轉換

//數制轉換 void conversion( ) {initstack(S);scanf (“%”,N);while(N){push(S,N%8）N=N/8;}while(! Stackempty(S)){pop(S,e);printf(“%d”,e);} }

2.括號匹配的檢驗
假設表達式中允許包含兩種括號：圓括號和方括號，其嵌套順序隨意，例：
( [ ] ( ) )或[ ( [ ] [ ] ) ]等為正確的格式
[ ( ] )或( [ ( ) )或 ( ( ) ] )均為不正確的格式。
思路：1）凡出現左括弧，則進棧；
2）凡出現右括弧，首先檢查棧是否空？
若棧空，則表明該“右括弧”多余
否則和棧頂元素比較，
若相匹配，則“左括弧出棧”
否則表明不匹配
3）表達式檢驗結束時，
若棧空，則表明表達式中匹配正確
否則表明“左括弧”有余。

課后習題

1、假設以帶頭結點的循環鏈表表示隊列，并且只設一個指針指向隊尾元素（注意不設頭指針）， 試編寫相應的隊列初始化、入隊列和出隊列的算法。

typedef struct QNode {QElemType data; struct QNode *next; }QNode,*QueuePtr; typedef struct { //鏈隊指針類型 QueuePtr tail; //隊尾指針 }LinkQueue; void InitQueue(Queue &Q) {//初始化循環鏈表表示的隊列QQ.tail=(QueuePtr)malloc(sizeof(QNode));Q.tail->next=Q.tail;}//InitQueue Status EnQueue(QueuePtr &tail,QElemType e ）{q = (QueuePtr)malloc(sizeof(QNode));//分配空間，構造入隊列元素結點 q->data = e; //元素賦值 q->next = tail ->next; //入隊列 tail ->next = q;tail = tail ->next; //隊尾指針后移 return OK; } Status DeQueue(QueuePtr & tail,QElemType &e）{if(tail == tail ->next) return ERROR; //隊列已空q = tail ->next->next;//q指向帶頭結點鏈表的第一個元素e = q->data; //返回出隊列元素 tail ->next->next = q ->next; //元素出隊列 free(q); //釋放空間 return OK; }

3-31 判別輸入的字符序列是否為“回文”。 例如 abcdedcba 或 abccba是回文，兩頭讀過來都相同。
試寫一個算法判別輸入的一個以“@”為結束符的字符序列是否為回文。

分析：由于回文的字符序列中的分界線不明確，因此算法中，除了需要用一個棧外，還需要用一個隊列，否則無法判別。

算法的基本思想是： 將依次讀入的字符分別插入棧和隊列，然后依次進行比較“棧頂”和“隊頭”的字符。

注意：循環隊列隊滿的條件(rear+1)/maxsize == front

第四章串

2-2 (neuDS_C++)串是一種特殊的線性表，其特殊性體現在( )。

• A 可以順序存儲
• B 數據元素是一個字符
• C 可以鏈接存儲
• D 數據元素可以是多個字符

2-10 (neuDS)設主串的長度為n，模式串的長度為m，則串匹配的KMP算法時間復雜度是( )。

• A O(m)
• B O(n)
• C O(n + m)
• D O(n×m)

2-11 若串S=“software”，其子串的數目是 (2分)

• A 8
• B 37
• C 36
• D 9
  子串數目 = （∑n）+1 = n*(n+1)/2 + 1

注意：定長順序存儲即將字符存于數組中且總下標1開始，而0號單元存儲長度 串的模式匹配：子串的定位操作 int Index(SString S,SString T, int pos){ //返回子串T在主串S中第pos個字符之后的位置，若不存在，則函數值為0，其中，T非空，(1≦pos≦Strlength（S））。i=pos; //指向串s的第pos個字符j=1; //指向串t的第1個字符while((i<=S[0])&&(j<=T[0])）{if(S[i]==T[j]) { ++i; ++j; } //繼續比較后繼字符else {i=i-j+2; j=1;} //串S指針回溯重新開始匹配}if(j>T[0]) return i-T[0]; //匹配成功，返回模式串t在串s中的起始位置else return 0; //匹配失敗返回0 } //Index 串答案：2-2B 2-10C 2-11B

第五章數組和廣義表

知識點

廣義表的分類
（1）線性表：元素全部是原子的廣義表。
（2）純表：與樹對應的廣義表.
（3）再入表：與圖對應的廣義表(允許結點共享)，
（4）遞歸表：允許有遞歸關系的廣義表，例如E=(a,E)。
這四種表的關系滿足：遞歸表?再入表? 純表 ? 線性表
LS = ( 1, 2, …, n)均可分解為
表頭 Head(LS) = 1 和
表尾 Tail(LS) = ( 2, …, n) 兩部分

pta

2-3 稀疏矩陣在計算機中通常采用（）來表示。 三元組線性表
2-4廣義表是一種（）數據結構。 遞歸的
2-7在定義稀疏矩陣的十字鏈接存儲結構時，每個結點結構需包含（）個域。 5
十字鏈表標志稀疏矩陣：在鏈表中，每個非零元可用一個含有5個域的結點表示，其中i，j，e這三個域分別表示非零元所在行、列以及值，向右域right和向下域down分別表示同行的下一個非零元和同列的下一個非零元

第六章樹和二叉樹

必會知識點

性質1：在二叉樹的第i層上至多有2^i-1個結點。(i≥1)
性質 2 ：深度為 k 的二叉樹上至多含 2^k-1 個結點（k≥1）
性質 3 ：具有 n 個結點的完全二叉樹的深度為log₂n +1
性質 4 ：若對含 n 個結點的完全二叉樹從上到下且從左至右進行 1 至 n 的編號，則對完全二叉樹中任意一個編號為 i 的結點：
(1) 若 i=1，則該結點是二叉樹的根，無雙親,
否則，編號為i/2的結點為其雙親結點;
(2) 若 2i>n，則該結點無左孩子，否則，編號為 2i 的結點為其左孩子結點；
(3) 若 2i+1>n，則該結點無右孩子結點， 否則，編號為2i+1 的結點為其右孩子結點。

樹二叉樹

先序遍歷	先序遍歷
后序遍歷	中序遍歷

pta

2-7 設高為h的二叉樹（規定葉子結點的高度為1）只有度為0和2的結點，則此類二叉樹的最少結點數和最多結點數分別為： (3分)

• A 2h, 2^h-1
• B 2h?1, 2^h-1
• C 2h?1, 2^h-1-1
• D 2^h-1+1, 2^h-1

2-23 設 T 是非空二叉樹，若 T 的先序遍歷和后序遍歷序列相同，則 T 的形態是 __ (2分)

• A 只有一個根結點
• B 沒有度為 1 的結點
• C 所有結點只有左孩子
• D 所有結點只有右孩子

答案：2-7B 2-23A

5-1 下列代碼的功能是將二叉樹T中的結點按照層序遍歷的順序輸出。

typedef struct TreeNode *Tree; struct TreeNode {int Key;Tree Left;Tree Right; };void Level_order ( Tree T ) {Queue Q;if ( !T ) return; Q = CreateQueue( MaxElements ); Enqueue( T, Q ); while ( !IsEmpty( Q ) ){T = Front_Dequeue ( Q ); /* return the front element and delete it from Q */printf("%d ", T->Key);if ( T->Left ) Enqueue( T->Left, Q ) (3分);if ( T->Right (3分) ) Enqueue( T->Right, Q ) (3分);} }

5-4
已知先序遍歷序列和中序遍歷序列建立二叉樹。 例如

輸入先序遍歷序列： ABDFGC， 再輸入中序遍歷序列： BFDGAC，則 輸出該二叉樹的后序遍歷序列： FGDBCA。

#include <stdio.h> #include <stdlib.h> #include <string.h> typedef char ElementType; typedef struct BiTNode{ElementType data;struct BiTNode *lchild;struct BiTNode *rchild; }BiTNode,*BiTree;BiTree CreatBinTree(char *pre,char*in,int n ); void postorder( BiTree T );int main() {BiTree T;char prelist[100];char inlist[100];int length;scanf("%s",prelist);scanf("%s",inlist);length=strlen(prelist);T=CreatBinTree(prelist,inlist, length);postorder( T );return 0; } void postorder( BiTree T ) {if(T){postorder(T->lchild);postorder(T->rchild);printf("%c",T->data);} } BiTree CreatBinTree(char *pre,char*in,int n) {BiTree T;int i;if(n<=0) return NULL;T=(BiTree)malloc(sizeof(BiTNode));T->data=pre[0];for(i=0;in[i]!=pre[0];i++);T->lchild= CreatBinTree(pre+1,in, i)//i為左子樹的長度，若<=0，則無左子樹 (3分);T->rchild= CreatBinTree(pre+i+1,in+i+1,n-1-i )//n-i-1為右子樹長度 (3分);return T; }

課后習題

1.深度為k的完全二叉樹至少有____個結點。至多有____個結點，若按自上而下，從左到右次序給結點編號（從1開始），則編號最小的葉子結點的編號是____。 2^k-1 2^k-1 2^k-1+1
2.已知一棵二叉樹的前序遍歷的結果是ABECDFGHIJ, 中序遍歷的結果是EBCDAFHIGJ, 試畫出這棵二叉樹。

中序非遞歸算法

void InOrderTraverse(BiTree T, Status (*Visit)(TElemType e)){InitStack(S); Push(S,T);while(!StackEmpty(S)){ while(GetTop(S,p) && p) Push(S,p->lchild);Pop(S,p); if(!StackEmpty(S)){ Pop(S,p); if(! Visit(p ->data)) return ERROR;Push(S,p->rchild)；}}return OK; } 未掌握：5-4 已知后序序遍歷序列和中序遍歷序列建立二叉樹。 例如 > 輸入后序遍歷序列： FGDBCA， 再輸入中序遍歷序列： BFDGAC，則 輸出該二叉樹的先序遍歷序列： ABDFGC。 > 中序非遞歸算法

第七章圖

知識點

深度優先遍歷

//連通圖 void DFS(Graph G, int v) {// 從頂點v出發，深度優先搜索遍歷連通圖 G，需要設置一個輔助數組visited[v] = TRUE; VisitFunc(v);for(w=FirstAdjVex(G,v);w!=0; w=NextAdjVex(G,v,w))if (!visited[w]) DFS(G,w); // 對v的尚未訪問的鄰接頂點w// 遞歸調用DFS } // DFS//非連通圖 void DFSTraverse(Graph G, Status (*Visit)(int v)) {// 對圖 G 作深度優先遍歷。VisitFunc = Visit; for (v=0; v<G.vexnum; ++v) visited[v] = FALSE; // 訪問標志數組初始化for (v=0; v<G.vexnum; ++v) if (!visited[v]) DFS(G, v);// 對尚未訪問的頂點調用DFS }

廣度優先搜索

//使用隊列 void DFSTraverse(Graph G，Status (*Visit)(int v)){for(v=0;v<G.vexnum;++v) visited[v]=FALSE; //訪問標志數組初始化InitQueue(Q)；//置空的輔助隊列Qfor (v=0;v<G.vexnum;++v)if (!visited[v]) {//v尚未訪問visited[v]=TRUE； Visit(v)；EnQueue(Q，v)；while(!QueueEmpty(Q)){DelQueue(Q，u)；//隊頭元素出隊并置為u，訪問ufor(w=FirstAdiVex(G,u);w!=0;w=NextAdjVex(G,u,w))if (!visited[w]){visited[v]=TRUE； Visit(w)；EnQueue(Q，v); //u的尚未訪問的鄰接頂點w入隊列}//if}//while} // if }// DFSTraverse

最小生成樹

//普里姆算法（按逐個將頂點連通的方式來構造最小生成樹。） //需要設置一個輔助數組記錄最小生成樹元素，先遍歷頂點判斷頂點是否已屬于最小生成樹， //若是則遍歷其鄰接點，若其臨界點不含于最小生成樹中則參與比較大小 int U; int V[1001]; typedef struct Adjacency{//表結點int leftAdjvex;int rightAdjvex; //鄰接點的位置int weight;struct Adjacency * nextarc; //指向下一個表結點的指針 }Adjacency; typedef struct VNode{int data; //頂點信息Adjacency * firstarc; //指向第一個表結點的指針 }VNode, VexList[2000]; //AdjList表示鄰接表類型 typedef struct{VexList vexList; //頭結點數組int vexNumber, edgeNumber; //圖的當前頂點數和邊數 }ALGraph; /---找最小邊--- Adjacency* findMinEdge(ALGraph alGraph){//先遍歷頂點判斷頂點是否已屬于最小生成樹，若是則遍歷其鄰接點，若其臨界點不含于最小生成樹中則參與比較大小Adjacency *b = (Adjacency*)malloc(sizeof(Adjacency));b = NULL;for (int i = 1; i <= alGraph.vexNumber; ++i) {//遍歷頂點判斷頂點if(V[i] != 0){//是否已屬于最小生成樹Adjacency *a = (Adjacency*)malloc(sizeof(Adjacency));a = alGraph.vexList[i].firstarc;while (a != NULL) {//當鄰接點含于最小生成樹時，a=下一個鄰接點if(V[a->rightAdjvex] != 0){a = a->nextarc;}else{if(b == NULL){b = a;}else{if(a->weight < b->weight){b = a;}}a = a->nextarc;}}}else{continue;}}return b; } int prim(ALGraph alGraph,Adjacency *c){int w;V[c->leftAdjvex] = V[c->rightAdjvex] = 1;U = 2;w = c->weight;Adjacency *b = (Adjacency*)malloc(sizeof(Adjacency));b = findMinEdge(alGraph);while (b != NULL){V[b->rightAdjvex] = 1;w += b->weight;U++;b = findMinEdge(alGraph);}if(U != alGraph.vexNumber)return -1;return w; } 克魯斯卡爾(Kruskal)算法 先構造一個只含n個頂點的子圖SG，然后從權值最小的邊開始，若它的添加不使SG中產生回路，則在SG上加上這條邊，如此重復，直至加上n-1 條邊為止。

拓撲排序
用DFS遍歷一個無環有向圖，并在DFS算法退棧返回時打印相應的頂點，則輸出的頂點序列是
求最短路徑的迪杰斯特拉算法

pta

2-4 在N個頂點的無向圖中，所有頂點的度之和不會超過頂點數的多少倍？ (2分)

• A 1
• B 2
• C (N?1)/2
• D N?1

2-18以下哪個命題是正確的？ (3分)

• A 對于帶權無向圖G = (V, E)，M是G的最小生成樹，則M中任意兩點V1到V2的路徑一定是它們之間的最短路徑
• B P是頂點S到T的最短路徑，如果該圖中的所有路徑的權值都加1，P仍然是S到T的最短路徑
• C 深度優先遍歷也可用于完成拓撲排序
• D 以上都不是

2-24 用DFS遍歷一個無環有向圖，并在DFS算法退棧返回時打印相應的頂點，則輸出的頂點序列是？ (2分)

• A 無序的
• B 拓撲有序
• C 逆拓撲有序
• D 以上都不對

第九章查找

知識點

二叉排序樹的刪除操作
(1) 若待刪除的結點是葉子結點，直接刪去該結點。如圖(a)所示，直接刪除結點9。
(2) 若待刪除的結點只有左子樹而無右子樹。根據二叉排序樹的特點，可以直接將其左子樹的根結點放在被刪結點的位置。如圖(b)所示，p作為q的右子樹根結點，要刪除p結點，只需將p的左子樹(其根結點為3)作為q結點的右子樹。
(3) 若待刪除的結點只有右子樹而無左子樹。與(2)情況類似，可以直接將其右子樹的根結點放在被刪結點的位置。如圖?所示，p作為q的右子樹根結點，要刪除p結點，只需將p的右子樹(其根結點為8)作為q結點的右子樹。
(4) 若左右子樹均存在則找左樹最大的結點或者右樹最小的結點取代此節點并轉至（2）或（3）刪除原來位置的次節點

pta

2-14給定散列表大小為11，散列函數為H(Key)=Key%11。按照線性探測沖突解決策略連續插入散列值相同的4個元素。問：此時該散列表的平均不成功查找次數是多少？

• A 1
• B 4/11
• C 21/11
• D 不確定
  平均不成功查找長度，顧名思義即對N（N為表長）種查找不成功的不同情況的探測次數求和并取平均，對于表中的空格只探測一次便能證明查找失敗所以m個空格直接加m，對于非空，則需要比較并繼續探測下一個空格是否為空。
  此題 = （（11-4）+（5+4+3+2））/11

第十章排序

堆排序

1、建堆
把待排序記錄R[1…n]看作一棵二叉樹，將R[1]作為二叉樹的根，R[2…n]依次逐層從左到右順序排列，構成一棵完全二叉樹，任意結點R[i]的左孩子是R[2i]，右孩子是R[2i+1]，雙親是R[i/2]。（注意：這時的完全二叉樹并不具備堆的特征）。此時所有i>n/2」的結點R[i]都沒有孩子結點，因此以R[i]為根的子樹已經是堆。從i=n/2的結點R[i]開始，比較根結點與左、右孩子的關鍵字
例如此例，從12即R[5]開始一直篩選R[4]、R[3]、R[2]、R[1]

總結

以上是生活随笔為你收集整理的大二上数据结构复习的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。