1、第1章選擇題：1.1 數據結構在計算機內存中的表示是指：A數據的存儲結構 B.數據結構C數據的邏輯結構 D.數據元素之間的關系1.2 數據的邏輯結構是指： A. 數據所占的存儲空間量 B各數據元素之間的邏輯關系C. 數據在計算機中順序或鏈接的存儲方式D. 存儲在內存或外存中的數據1.3 在下列的敘述中，正確的是： A數據的邏輯結構是指數據的各數據項之間的邏輯關系。B數據的物理結構是指數據在計算機內的實際存儲形式。 C在順序存儲結構中，數據元素之間的關系是顯示體現的。D鏈接存儲結構是通過結點的存儲位置相鄰來體現數據元素之間的關系。填空題：1.4 數據結構主要研究 數據的邏輯結構 ， 數據的存儲結

2、構 ， 數據的運算 三個方面的內容。1.5 鏈接存儲的特點是通過附加 指針域 來表示數據元素之間的邏輯關系。1.6 數據結構中討論的三種經典結構包括： 線性表 ， 樹 ， 圖 。1.7 數據結構中常用的存儲方法有： 順序 ， 鏈接 ， 索引 ， 散列 。1.8 順序存儲結構可以通過位置 隱含 表示關系，鏈接存儲結構通過附加指針來 顯示 表示關系。1.9 算法的特性包括 有窮性 ， 確定性 ， 可行性 ，輸入和輸出。1.10 算法性能分析的兩個主要定量評價指標是 時間復雜度 和 空間復雜度 。簡答題：1.11 數據結構研究的三方面內容之間有什么聯系和區別？ 數據結構研究的三方面內容包括: 數據的

3、邏輯結構、存儲結構和運算。數據的邏輯結構是數學模型，存儲結構是指邏輯結構到存儲區域的映射，運算是定義在邏輯結構上，實現在存儲結構上。1.12 簡述數據結構中討論的三種經典結構的邏輯特征是什么？三種經典結構：線性表、樹和圖。邏輯特征分別為：（1）線性表：一對一。有且僅有一個開始結點和一個終端結點，其余的內部結點都有且僅有一個前趨結點和一個后繼結點。（2）樹：一對多。有且僅有一個開始結點，可有若干個終端結點，其余的內部結點都有且僅有一個前趨結點，可以有若干個后繼結點。（3）圖：多對多。可有若干個開始結點和終端結點，其余的內部結點可以有若干個前趨結點和若干個后繼結點。1.13 簡述各種常用存儲方法的

4、基本思想。各種方法的基本思想：順序存儲：邏輯上相鄰的數據元素存儲在物理位置上相鄰的存儲單元里。鏈接存儲：通過附加指針域表示數據元素之間的關系。索引存儲：除了存儲數據元素，還要建立附加的索引表來標識數據元素的地址。散列存儲：根據關鍵字直接計算出該結點的存儲地址，通常稱為關鍵字地址轉換法。第2章選擇題：2.1 線性表L=（a1，a2，an），下列說法正確的是：A. 每個元素都有一個直接前驅和一個直接后繼。B. 線性表中至少有一個元素。C. 表中元素的排列順序必須是由小到大或由大到小。D. 除第一個和最后一個元素外，其余每個元素都有且僅有一個直接前驅和一個直接后繼。2.2 下面關于線性表的敘述中，錯

5、誤的是：A線性表若采用順序存儲，必須占用一片連續的存儲單元B線性表若采用順序存儲，便于進行插入和刪除操作C線性表若采用鏈接存儲，不必占用一片連續的存儲單元D線性表若采用鏈接存儲，便于插入和刪除操作2.3 在長度為n的順序表的第i(1in+1)個位置上插入一個元素，元素的移動次數為：A .n-i+1 B .n-i C .i D .i-12.4 刪除長度為n的順序表中的第i(1in)個位置上的元素，元素的移動次數為：A. n-i+1 B. n-i C. i D. i-12.5 已知一個帶頭結點單鏈表L，在表頭元素前插入新結點 *s的語句為：A. L=s; s->next=L; B. s-&g

6、t;next=L->next; L->next=s; C. s=L; s->next=L; D. s->next=L; s=L;2.6 已知一個不帶頭結點單鏈表的頭指針為L，則在表頭元素之前插入一個新結點*s的語句為：A. L=s; s->next=L; B. s->next=L; L=s; C. s=L; s->next=L; D. s->next=L; s=L;2.7 已知單鏈表上一結點的指針為p，則在該結點之后插入新結點*s的正確操作語句為：A p->next=s; s->next=p->next; B s->nex

7、t=p->next; p->next=s;C p->next=s; p->next=s->next; D p->next=s->next; p->next=s;2.8 已知單鏈表上一結點的指針為p，則刪除該結點后繼的正確操作語句是：A s= p->next; p=p->next; free(s); B p=p->next; free(p);C s= p->next; p->next=s->next; free(s);D p=p->next; free(p->next);2.9 設一個鏈表最常用的操作

8、是在表尾插入結點和在表頭刪除結點，則選用下列哪種存儲結構效率最高？A. 單鏈表B. 雙鏈表 C. 單循環鏈表D. 帶尾指針的單循環鏈表2.10 線性表的鏈接存儲結構是一種（ ）存儲結構。A. 隨機存取 B. 順序存取 C. 索引存取 D. 散列存取2.11 鏈表不具備的特點是：A. 插入刪除不需要移動元素 B. 不必事先估計存儲空間 C. 可隨機訪問任一結點 D. 所需空間與其長度成正比填空題：2.1 在單鏈表L中，指針p所指結點有后繼結點的條件是 p->next!=NULL 。2.2 判斷帶頭結點的單鏈表L為空的條件 L->next=NULL。2.12 順序表和鏈表中能實現隨機存

9、取的是 順序表 ，插入、刪除操作效率高的是 鏈表 。2.13 對于一個具有n個結點的單鏈表，已知一個結點的指針p，在其后插入一個新結點的時間復雜度為 O（1） ；若已知一個結點的值為x，在其后插入一個新結點的時間復雜度為 O（n） 。2.14 順序表的存儲密度 大 ，鏈表的存儲密度 小 。 簡答題：2.15 比較順序表和鏈表這兩種線性表不同存儲結構的特點。順序表存儲密度大存儲空間連續靜態分配隨機存取插、刪效率低鏈表存儲密度大存儲空間可不連續動態分配順序存取插、刪效率高2.16 簡述頭結點的作用。頭結點的作用是使得單鏈表在表頭位置的插、刪操作同中間位置的插、刪操作完全相同。即使“空表”與“非空表

10、”的操作統一，也使“表頭結點”與其他位置結點的操作完全一致，無須特殊處理。2.17 寫出單鏈表存儲結構的C語言描述。typedef int DataType; typedef struct Node DataType data; struct Node *next; LinkList;完善程序題：2.18 設計一個算法，其功能為：向一個帶頭結點的有序單鏈表（從小到大有序）中插入一個元素x，使插入后鏈表仍然有序。請將代碼補充完整。typedef int DataType;typedef struct Node DataType data; ; /*定義指向該結構類型的指針變量next*/Link

11、list;void insert(Linklist *L,DataType x) Linklist *s,*p=L; while(p->next && p->next->data<x) ; /*p指針后移一步*/ ; /*申請一個新結點空間，將其地址賦給變量s*/s->data=x; ; ; /*將*s結點插入到*p結點的后面*/struct Node * next; p=p->next; s=(LinkList *)malloc(sizeof(LinkList);s->next=p->next; p->next=s;2.1

12、9 設計一個函數功能為：在帶頭結點的單鏈表中刪除值最小的元素。請將代碼補充完整。typedef int DataType;typedef Node /*定義結構體類型*/DataType data;struct Node * next;LinkList;void deleteMin(LinkList *L)LinkList *p=L->next,*q;/*首先查找值最小的元素，指針q指向最小元素結點*/q=p;while(p)if( p->data < q->data)q=p; ; /* p指針后移一步，比較單鏈表中的每一個結點*/if(!q) return; /*不存

13、在最小結點（空表）時，直接退出*/ p=L; /*若存在最小結點，則先找到最小結點的前驅，即*q的前驅*/while( )p=p->next; ; /*從單鏈表中刪除最小元素結點（指針q所指結點）*/ ; /* 釋放指針q所指結點的空間*/structp=p->next;p->next!=qp->next=q->next; free(q);算法設計題：2.20 已知長度為n的線性表A中的元素是整數，寫算法求線性表中值大于item的元素個數。分兩種情況編寫函數：（1）線性表采用順序存儲；（2）線性表采用單鏈表存儲。（1）線性表采用順序存儲#define MAX 10

14、24typedef int DataType;typedef struct DataType dataMAX;int last; SeqList;int LocateElem (SeqList *L, DataType item)int i,j=0; for(i=0;i<=L->last ;i+) if( L->datai >item ) j+; return j;（2）線性表采用單鏈表存儲typedef int DataType; typedef struct Node DataType data; struct Node *next; LinkList;int lo

15、cateElem(LinkList *L, DataType item ) LinkList *p=L->next; int i=0; while ( p ) if( p->data >item) i+; return i ;2.21 試寫一算法實現對不帶頭結點的單鏈表H進行就地（不額外增加空間）逆置。 typedef int DataType;typedef struct Node DataType data; struct Node *next; LinkList;LinkList * Reverse(LinkList *L)LinkList *p,*q;if (!L)

16、return;p=H->next; q=H->next; L->next=NULL;while(q)q=q->next; p->next= L; L=p; p=q; return L;第3章選擇題：3.1 設一個棧的輸入序列是 1，2，3，4，5，則下列序列中，是棧的合法輸出序列的是：A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 2 1 5 D. 3 5 2 4 1 3.2 設有一順序棧，元素1，2，3，4，5依次進棧，如果出棧順序是2，4，3，5，1則棧的容量至少是：A .1 B. 2 C. 3 D. 43.3 若用一個大小為6的數組來實現循

17、環隊列，且當前rear和front的值分別為0和3，當入隊一個元素，再出隊兩個元素后，rear和front的值分別為： A. 1和 5 B. 2和4 C. 4和2 D. 5和1 填空題：3.4 棧和隊列都是操作受限的線性表，棧的運算特點是 LIFO ，隊列的運算特點是 FIFO 。3.5 若序列a、b、c、d、e按順序入棧，假設P表示入棧操作，S表示出棧操作，則操作序列PSPPSPSPSS后得到的輸出序列為 acdeb 。3.6 已知一個順序棧*s，棧頂指針是top，它的容量為MAXSIZE，則判斷棧空的條件為 s->top=-1 ，棧滿的條件是 s->top=MAXSIZE-1

18、。3.7 對于隊列來說，允許進行刪除的一端稱為 隊頭 ，允許進行插入的一端稱為 隊尾 。3.8 某循環隊列的容量MAXSIZE=6，隊頭指針front=3，隊尾指針rear=0，則該隊列有_3_個元素。簡答題：3.9 棧上的基本運算有哪些？棧的基本運算有：（1）初始化棧 initStack（s）：構造了一個空棧s。（2）判棧空empty（s）：若棧s為空棧，返回值為“真”（1），否則返回值為“假”（0）。（3）入棧push（s，x）：在棧s的頂部插入一個新元素x， x成為新的棧頂元素。（4）出棧pop（s）：刪除棧s的棧頂元素。（5）讀棧頂元素top（s）：棧頂元素作為結果返回，不改變棧的狀態

19、。3.10 循環順序隊列的存儲結構圖示及C語言描述？C語言描述： 循環順序隊列圖示：#define MAXSIZE 1024 typedef int DataType;typedef struct DataType dataMAXSIZE; int rear , front; SeQueue;SeQueue *sq; 3.11 簡述棧和隊列有哪些聯系與區別？棧和隊列都是運算運算受限的線性表，邏輯結構相同；都可以順序存儲和鏈接存儲，存儲結構也相同；插入和刪除運算都限制在線性表的表端完成，且不需要查找運算。二者差別主要體現在運算的限制不同：棧是后進先出（LIFO）的線性表，限制它的插入和刪除操作僅

20、在表的一端進行。隊列是先進先出（FIFO）的線性表，只允許在表的一端進行插入，而在表的另一端進行刪除。算法設計題：3.12 通常稱正讀和反讀都相同的字符序列為“回文”，例如，“abcdeedcba”、 “abcdcba”是回文。若字符序列存儲在一個單鏈表中，編寫算法判斷此字符序列是否為回文。（提示：將一半字符先依次進棧）#define maxsize 100typedef char datatype1;typedef struct datatype1 datamaxsize; int top; seqstack;typedef int datatype;typedef struct node

21、datatype data; struct node *next; Linklist;Duichen(Linklist *head) int i=1;Linklist *p; seqstack *s;s=initSeqStack();p= head->next;n=0;while(p)n+; p=p->next;p=head->next;while(i<=n/2)push(s, p->data); i+; if (n%2!=0) p=p->next; while(p&&p->data=pop(s) p=p->next;if (p)

22、 return 0 else return 1;第5章選擇題：5.1 設數據結構D-S可以用二元組表示為D-S=(D，S)，rS，其中：D=A，B，C，D，r=<A，B>，<A，C>，<B，D>，則數據結構D-S是：A線性結構 B樹形結構 C圖形結構 D集合5.2 樹最適合用來表示： A有序數據元素 B.無序數據元素 C元素之間具有分支層次關系的數據 D.元素之間無聯系的數據5.3 有關二叉樹下列說法正確的是：A二叉樹是度為2的有序樹B二叉樹中結點的度可以小于2 C二叉樹中至少有一個結點的度為2 D二叉樹中任何一個結點的度都為25.4 深度為10的完全二叉樹

23、，第3層上的的結點數是：A .15B .16C . 4D .325.5 設一棵樹的度為4，其中度為1、2、3、4的結點個數分別為6、3、2、1，則這棵樹中葉子結點的個數為：A .8 B. 9 C. 10 D. 115.6 對于二叉樹來說，第i 層上最多包含的結點個數為： A2i - 1 B. 2i + 1 C2i D.2i5.7 樹的后根遍歷序列等同于與該樹對應的二叉樹的哪種序列？A. 前序序列 B. 中序序列 C. 后序序列 D. 層序序列5.8 設森林F中有三棵樹，第一，第二，第三棵樹的結點個數分別為M1，M2和M3。與森林F對應的二叉樹根結點的右子樹上的結點個數是： AM1 BM1+M2

24、 CM3 DM2+M3填空題：5.9 二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點個數是 11 。5.10 包含n個結點的二叉樹，高度最大為 n ，高度最小為。5.11 某完全二叉樹共有200個結點，則該二叉樹中有 1 個度為1的結點。5.12 一棵高度為10的滿二叉樹中的結點總數為 210-1 個，其中葉子結點數為 29 。5.13 某完全二叉樹結點按層順序編號（根結點的編號是1），若21號結點有左孩子結點，則它的左孩子結點的編號為_42_。5.14 深度為k的完全二叉樹至少有 2k-1 個結點，至多有 2k-1 個結點。5.15 n個結點的線索二叉樹上含有 n+1 條線索

25、。簡答題：5.16 畫出包含三個結點的樹和二叉樹的所有不同形態。5.17 找出滿足下面條件的二叉樹：（1）前序遍歷與中序遍歷結果相同：只有右分支的單分支二叉樹（2）前序遍歷和后序遍歷結果相同：只有一個根結點的二叉樹 （3）中序遍歷和后序遍歷結果相同：只有左分支的單分支二叉樹5.18 一棵二叉樹的中序、后序遍歷序列分別為： G L D H B E I A C J F K和L G H D I E B J K F C A，請回答：（1）畫出二叉樹邏輯結構的圖示。（2）畫出此二叉樹的二叉鏈表存儲結構的圖示并給出C語言描述。（3）畫出上題中二叉樹的中序線索二叉樹。（4）畫出中序線索二叉鏈表存儲結構圖示并

26、給出C語言描述。（1）二叉樹的邏輯結構圖示：（2）二叉鏈表存儲結構的圖示及C語言描述： typedef char DataType; typedef struct NodeDataType data; struct Node *lchild,*rchild;BiTree;（3）中序線索二叉樹：（4）中序線索二叉鏈表的圖示及C語言描述：typedef char DataType; typedef struct NodeDataType data; struct Node *lchild,*rchild; int ltag,rtag;BiThrTree;5.19 設有森林如圖5.31所示，請回答：

27、（1）畫出與該森林對應的二叉樹的邏輯結構圖示。（2）寫出該二叉樹的前序、中序、后序遍歷序列。（3）畫出該二叉樹的中序線索二叉鏈表的圖示并給出C語言描述。圖5.31（1）二叉樹的邏輯結構圖示： （2）前序遍歷序列：ABCDFGEH，中序遍歷序列：ADGFCBHE 后序遍歷序列：GFDCHEBA（3）中序線索二叉鏈表的圖示及C語言描述：typedef char DataType; typedef struct NodeDataType data; struct Node *lchild,*rchild; int ltag,rtag;BiThrTree;5.20 設有森林 B=(D,S), D=A,

28、B,C,D,E,F,G,H,I,J, rSr=<A,B>,<A,C>,<A,D>,<B,E>,<C,F>,<G,H>,<G,I>,<I,J> 請回答：（1）畫出與森林對應的二叉樹的邏輯結構圖示。（2）寫出此二叉樹的前序、中序、后序遍歷序列。（3）畫出此二叉樹的二叉鏈表存儲結構的圖示并給出C語言描述。（1）與森林對應的二叉樹的邏輯結構圖示：（2）前序遍歷序列：ABECFDGHIJ，中序遍歷序列：EBFCDAHJIG后序遍歷序列：EFDCBJIHGA（3）二叉鏈表存儲結構的圖示及C語言描述： typed

29、ef char DataType; typedef struct NodeDataType data; struct Node *lchild,*rchild;BiTree;5.21 請畫出5.32中的各二叉樹對應的森林。圖5.325.22 假設用于通信的電文由字符集a，b，c，d，e，f，g，h中的字母構成，這8個字母在電文中出現的概率分別為0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10，試為這8個字母進行哈夫曼編碼。請回答：（1）畫出哈夫曼樹（按根點權值左小右大的原則）。（2）寫出依此哈夫曼樹對各個字母的哈夫曼編碼。（3）求出此哈夫曼樹的帶權路徑長度WPL。

30、（1）哈夫曼樹： （2）各字母的哈夫曼編碼： a:1010 b:00 c:10000 d:1001e:11f:10001g:01h:1011（3）哈夫曼樹的帶權路徑長度WPL： =0.07×4+0.19×2+0.02×5+0.06×4+0.32×2+0.03×5+0.21×2+0.10×4=2.61完善程序題：5.23 設計一個算法，其功能為：利用中序線索求結點的中序后繼。請將代碼補充完整。typedef char DataType; typedef struct NodeDataType data; struct

31、 Node *lchild, ; int ltag,rtag;BiThrTree;BiThrTree * InOrderNext(BiThrTree *p) /* 求中序后繼 */if( ) p=p->rchild; /*若結點*p無右孩子 */ else /*若結點*p有右孩子 */ ; while(p->ltag=0) ; return ;*rchild p->rtag=1p=p->rchildp=p->lchildp第6章選擇題：6.1 n個頂點的有向圖中有向邊的數目最多為：A n-1 B n C n(n-1)/2 D n(n-1)6.2 下面哪一方法可以判

32、斷出一個有向圖是否有環（回路）：A深度優先遍歷 B. 求最短路徑 C. 拓撲排序 D. 廣度優先遍歷填空題：6.3 某無向圖的鄰接矩陣如下所示，則該圖中有 9 條邊，有 6 個頂點。6.4 在無向圖的鄰接矩陣存儲結構中，第i列上非零元素的個數是頂點vi的 度 ，而在有向圖的鄰接矩陣中，第i列上非零元素的個數是頂點vi的 入度 。6.5 若無向圖采用鄰接矩陣存儲，則存儲空間的大小只與圖中 頂點 的個數有關。6.6 對于一個具有n個頂點和e條邊的連通圖，其生成樹中的頂點數和邊數分別為 n 和n-1 。簡答題：6.7 設一個有向圖為G=(V,E)，其中V= v1,v2,v3,v4，E=< v2

33、,v1>,< v2,v3>,< v4,v1>,< v1,v4>,< v4,v2>，請回答下列各問：（1）畫出該有向圖，求出每個頂點的入度和出度。（2）畫出該圖的鄰接矩陣存儲結構圖示。（3）對（2）中的鄰接矩陣，給出從頂點v2出發的DFS序列和DFS生成樹。（4）對（2）中的鄰接矩陣，給出從頂點v2出發的BFS序列和BFS生成樹。（1）有向圖：頂點v1的入度是2，出度是1；頂點v2的入度是1，出度是2；頂點v3的入度是1，出度是0；頂點v4的入度是1，出度是2。（2）鄰接矩陣存儲結構圖示：（3）DFS序列： v2, v1,v4,v3 （4）B

34、FS序列： v2, v1,v3,v4生成樹： 生成樹：6.8 對圖6.44所示的無向圖，依次輸入各邊：(v1,v2)、(v1,v4)、(v2,v3)、(v3,v4)、(v3,v5)，請回答下列各問：（1）寫出該無向圖的二元組表示。（2）畫出該圖的鄰接表（頭插法建表）存儲結構圖示。（3）對（2）中的鄰接表，給出從頂點v1出發的DFS序列和DFS生成樹。（4）對（2）中的鄰接表，給出從頂點v1出發的BFS序列和BFS生成樹。 （1）無向圖的二元組表示：設G=(V,E)，V為頂點集，E為邊集，則V=v1,v2,v3,v4,v5E=(v1,v2)、(v1,v4)、(v2,v3)、(v3,v4)、(v3

35、,v5) （2）圖的鄰接表（頭插法建表）存儲結構圖示：（3）從頂點v1出發： （4）從頂點v1出發：DFS序列：v1,v4,v3,v5,v2 BFS序列：v1,v4,v2,v3,v5 DFS生成樹： BFS生成樹：畫出圖6.45中所有可能的最小生成樹。 圖6.44 圖6.456.1 圖6.45的所有可能的最小生成樹：第7章選擇題：7.1 在對n個元素進行起泡排序的過程中，最好情況下的時間復雜度為：A O(n3) B O(n2) C O(n) D O(1) 7.2 堆排序屬于下列哪類排序？A. 插入 B. 交換 C. 歸并 D. 選擇7.3 下列哪組序列是堆： A(79,40,46,56,38,

36、84) B. (84,56,79,46,38,40) C(40,38,46,56,79,84) D. (84,38,46,40,56,79)7.4 下列排序算法中，哪種排序方法在一趟結束后不一定能選出一個元素放在其最終位置上。A. 簡單選擇排序 B. 冒泡排序 C. 歸并排序 D. 堆排序7.5 就平均性能而言，目前最好的內排序方法是：A. 冒泡 B. 希爾插入 C. 交換 D. 快速7.6 在下面的排序方法中，平均時間復雜度為O(n2)且是不穩定的排序方法為： A. 快速排序 B. 直接插入排序 C. 直接選擇排序 D. 起泡排序填空題：7.7 每次從無序子表中取出一個元素，把它插入到有序子

37、表中的適當位置，此種排序方法叫做 插入 排序。7.8 快速排序的平均時間復雜度是 O（nlog2n） ，平均空間復雜度是O（log2n） 。7.9 設記錄的排序碼序列為：（49，38，65，97，76，13，27），若采用快速排序，則第一趟劃分的結果為 27,38,134976,97,65 。7.10 快速排序、堆排序和歸并排序的平均時間復雜度都是 O（nlog2n），但其中穩定的排序方法只有歸并 。7.11 在直接插入排序、希爾排序、起泡排序、快速排序中穩定的排序方法有 直接插入 和 起泡 。7.12 在堆排序、快速排序和歸并排序中，若只從存儲空間考慮，則首先應選取 堆排序 方法，其次選取快

38、速排序方法。7.13 直接插入排序和簡單選擇排序兩種排序算法中，關鍵字的比較次數與初始序列無關的是 簡單選擇 。簡答題：7.14 常用的實現排序的方法有幾大類？它們的實現思想是什么？插入排序的基本思想是：將一個待排序記錄按照排序碼的大小插入到一個有序序列的適當位置，使得插入后的序列仍然有序，直到所有記錄全部插入到有序序列中。交換排序的基本思想是： 兩兩比較待排序記錄的排序碼，不符合排列順序則交換記錄，直到所有記錄的排序碼都符合排序要求。選擇排序的基本思想是： 每一次從待排序記錄序列中選取一個排序碼最小（或最大）的記錄，放在待排序記錄序列的最前面（或最后面），重復此過程，直到所有的記錄按排序碼排

39、好序。歸并排序的基本思想是： 利用“歸并”技術實現的排序方法。所謂歸并就是將兩個或多個有序表合并成一個有序表的過程。如果是將兩個有序表合并成一個有序表稱為二路歸并，二路歸并是最簡單和最常用的。基數排序的基本思想是：基數排序是基于排序碼的結構分解，然后通過“分配”和“收集”方法實現的排序。7.15 給定排序碼的序列39、33、13、15、58、41、27、46、23。請回答：（1）采用希爾（Shell）排序（步長分別為5,3,1），寫出各趟排序結果。（2）采用快速排序的方法進行排序，寫出各趟排序結果。（1）希爾排序：393313155841274623 （初始）39271315584133462

40、3 （1趟希爾排序結果）152713334623395841 （2趟希爾排序結果） 131523273339414658 （3趟希爾排序結果）（2）快速排序：393313155841274623 （初始）23 33131527 39 41 4658 （1層劃分結果）1513 23 33 27 39 41 46 58 （2層劃分結果）1315 23 27 3339 41 46 58 （3層劃分結果）7.16 判斷下列序列是否為堆？如果不是，則把它們調整成堆。 （1） （503，87，512，61，908，170，896，275，653，462） （2） （12，70，33，65，24，48，92

41、，86，33，55） （3） （100，55，97，30，23，86，60，8，12） （4） （5，56，18，40，38，27，58，30，78，28，98）（1）不是堆，調整為大根堆：（908，653，896，503，462，170，512，275，61，87）（2）不是堆，調整為小根堆：（12，24，33，33，55，48，92，86，65，70）（3）是大根堆（4）不是堆，調整為小根堆：（5，28，18，30，38，27，58，40，78，56，98）7.17 設待排序文件各個記錄的排序碼序列為：19、23、2、67、39、91、43、25，進行堆排序，請回答：（1）畫出初始建成的大

42、根堆對應的完全二叉樹。（2）寫出初始大根堆序列。（3）畫出第一趟堆排序后對應的完全二叉樹。（1）初始建成的大根堆 （3）第一趟堆排序后對應的完全二叉樹（2）初始大根堆序列：91 67 43 25 39 2 19 23完善程序題：7.18 設計一個算法，其功能為：利用直接插入排序的方法，將一組存儲在帶頭結點的單鏈表中的記錄遞增排序。請將算法補充完整。typedef struct node int key; DataType other; ; /* 定義單鏈表的指針域next */ LinkList;void insertSort(LinkList *L) LinkList *p,*q,*s;p=

43、L->next; L->next=NULL; while(p) q=L;while(q->next && ) /* 指針q從頭開始查找，尋找合適的插入位置 */ ;s=p->next; ; /* 將指針p所指的結點插入到q之后 */ ;p=s;struct node *next;q->next->data<p->dataq=q->next;p->next=q->next;q->next=p;第8章選擇題：8.1 對線性表進行二分查找時，要求線性表必須：A以順序方式存儲 B以順序方式存儲，且按關鍵字有序C以鏈接方式存儲 D以鏈接方式存儲，且按關鍵字有序8.2 順序查找法適合于存儲結構為（ ）的線性表。 A散列存儲 B順序存儲或鏈接存儲C壓縮存儲D索引存儲8.3 若結點的存儲地址與其關鍵字之間存在某種函數關系，