數據結構試題10篇
數據結構試題(1)
2007年山東省學分互認和專升本考試
《數據結構》模擬試題(1)
一、單項選擇題(從下列各題四個備選答案中選出一個正確答案；每小題1分,共11分)
1.數據的不可分割的基本單位是____。
A.元素 B.結點 C.數據類型 D.數據項
2.下列算法suanfa2的時間復雜度為____。
int suanfa2(int n)
{ int t=1；
while(t0)個結點的完全二叉樹的深度是____。
A.log2(n) B.log2(n)+1
C.log2(n+1) D.log2(n)+1
7.與中綴表達式a+b*c-d等價的前綴表達式是____。
A.+a-*bcd B.*+-abcd
C.-+a*bcd D.abcd+*-
8.折半查找有序表(6,15,30,37,65,68,70,72,89,99),若查找元素37,需依次 與表中元素____進行比較,。
A.65,15,37 B.68,30,37
C.65,15,30 D.65,15,30,37
9.對長度為10的表作選擇(簡單選擇)排序,共需比較____次關鍵字。
A.45 B.90 C.55 D.110
10.對n個元素的表作快速排序,在最壞情況下,算法的時間復雜度為____。
A.O(log2 n) B.O(nlog2 n) C.O(n2) D.O(2n )
11.對長度為10的表作2_路歸并排序,共需移動____次(個)記錄。
A.20 B.45 C.40 D.30
二、填空(每空1分,共11分)
1.一個數據結構在計算機中的表示(映象)稱為 ________________。
2.線性表中 ____________________________ 稱為表的長度。
3.棧中元素的進出原則為 _____________________ 。
4.設數組A[1..10,1..8]的基地址為2000,每個元素占2個存儲單元,若以行序為主序順序存儲,則元素A[4,5]的存儲地址為_____；若以列序為主序順序存儲,則元素A[4,5]的存儲地址為______。
5.一棵深度為6的滿二叉樹有______個非終端結點。
6.若一棵二叉樹中有8個度為2的結點,則它有_____個葉子。
7.順序查找n個元素的順序表,當使用監視哨時,若查找成功,比較關鍵字的次數至少為____次, 最多為____次；若查找失敗,比較關鍵字的次數為____次。
8.對長度為400的表采用分塊(區)查找,最理想的塊長為____。
三、回答下列問題 (每小題5分,共10分)
1.線性表的存儲結構,在什么情況下采用順序結構? 為什么?
2.二叉樹有哪幾種基本形態? 畫圖說明之。
四、試畫出下列存儲結構圖(每小題4分,共20分)
1.數組A[1..2,0..2] 的以列序為主序的順序存儲結構。
2.依次將元素 A,C,D,B 插入一個初始狀態為空的鏈式棧中,試畫出所有插入完成之后的鏈式棧。
3.二叉樹的順序存儲結構:
4.圖的鄰接矩陣:
5.有向圖的逆鄰接表:
五、求解下列問題 (每小題6分,共24分)
1.給定30個字符組成的電文:
D D D D D A A A B E E A A F C D A A C A B B C C C B A A D D
試為字符 A、B、C、D、E、F 設計哈夫曼(Huffman)編碼。
(1)畫出相應的哈夫曼樹；
(2)分別列出 A、B、C、D、E、F 的哈夫曼碼；
(3)計算該樹的帶權路徑長度WPL。
2.試按表( 10,8,9,12,20,5,6,15,19,25 )中元素的排列次序, 將所有元素插入一棵初始為空的二叉排序樹中, 使之仍是一棵二叉排序樹。
(1)試畫出插入完成之后的二叉排序樹；
(2)若查找元素17,它將依次與二叉排序樹中哪些元素比較大小?
(3)假設每個元素的查找概率相等,試計算該樹的平均查找長度 ASL。
(4)對該樹進行中序遍歷,試寫出中序遍歷序列。
3.試將森林 F={ T1,T2,T3,T4 }轉換為一棵二叉樹。
T1 T2 T3 T4
4.找出下面網絡的最小生成樹。
六、填空題(在算法中有下劃線____的位置填空,使之成為完整、正確的算法)
算法說明:已知r[1..n]是n個記錄的遞增有序表,用折半查找法查找關鍵字為k的記錄,若查找失敗,則輸出”Failure”,返回零；否則輸出”Success”,并返回該記錄的序號值。(共8分)
算法(C函數):
int bin_search(struct arecord r[],int n,k:keytype)
/* r[1..n]為n個記錄的遞增有序表,k為關鍵字 */
{ int low, mid, hig ；
low=1； hig=n ； /* 各變量初始化 */
while( _____ )
{ mid=___________________ ；
if(k
數據結構試題(2)
《數據結構》綜合復習資料
一、填空題
1. 數據結構是（ ）。
2. 堆棧的特點是（ ） ，隊列的特點是（ ），字符串中的數據元素為（ ）。
3. 列舉三種樹的存儲方式（ ）、（ ）和（ ）。
4. 哈希表查找技術的性能取決于三個因素，它們是（ ）、（ ）和（ ）。
5. ADT稱為抽象數據類型，它是指（ ）。
6. 求下列程序的時間復雜度，并用大O表示方法表示（ ）。
for( i=1 ; idata);
InOrderTraverse(p->rchild); }
}
3、用順序表存儲空間的動態分配的方法實現線性表的插入算法。即在順序存儲的線性表中的第i個數據元素之前插入一個數據元素。
解：Status ListInsert_sq(sequenlist &L,int i,entrytype e)
{ if(iL.len+1) return ERROR; // i值不合法
if (L.len>=L.listsize) //檢查空間是否已滿
{ newbase=(elemtype *)realloc(L.a,(listsize +LISTINCREMENT)*sizeof(elemtype)); // 增加空間
if (!newbase) exit (Overflow); // 空間增加失敗
L.a=newbase; //空間增加成功
L.listsize + = LISTINCREMENT; }
q=&(L.a[i-1])； // q指向插入位置
for (p=&(L.a[L.len-1]);p>=q; --p) *(p+1)=*p; //將線性表第i個元素之后的所有元素向后移動
*q=e; / /插入 e
++L.len; // 表長 + 1
Return OK;
}
4、使用遞歸編寫算法計算二叉樹的高度。
解：int Height(BinTree T) { int i,j; if(!T) return 0; else { i=Height(T->lchild); j=Height(T->rchild); return 1+i>j?i:j; } }
5、已知Q是一個非空隊列，S是一個空棧。僅用隊列和棧的ADT函數和少量工作變量，編寫一個算法，將隊列Q中的所有元素逆置。
棧的ADT函數有：
makeEmpty(s:stack)；置空棧
push(s:stack; value:datatype)；新元素value進棧
pop(s:stack):datatype；出棧，返回棧頂值
isEmpty(s:stack):boolean；判棧空否
隊列的ADT函數有：
enqueue(q:queue;value:datatype)；元素value進隊
deQueue(q:queue):datatype；出隊列，返回隊頭值
isEmpty(q:queue):boolean；判隊列空否
解：void change（queue q,stack s）
{ datatype temp;
makeEmpty(s);
while (!isEmpty(q))
{ temp=deQueue(q);
push(s,temp);
}
while (!isEmpty(s))
{ temp=pop(s);
endueue(q,temp);
}
}
6、串的堆分配存儲結構如下:
typedef struct
{ char *ch;
int len;
} HSTRING;
編寫串復制的算法StringCopy(HSTRING *ss, HSTRING *dd)，將串ss中的各個字符復制到串dd中。
解：int StringCopy(HSTRING *ss, HSTRING *dd)
{ int I;
dd=malloc(ss->len * sizeof(char));
if(!dd)
{ printf(“Memory Overflow!”);
return 0; }
else
{ for(I=0;Ilen;I++)
dd.ch[I]=ss.ch[I];
return 1;
}
}
7、圖的鄰接矩陣和鄰接表存儲結構定義如下：
鄰接矩陣: typedef struct
{ int vexnum,arcnum;
char vexs[100];
int arcs[100,100]
} MGraph;
鄰接表：typedef struct arcptr
{ int adjvex; //鄰接點的存儲位置
struct arcptr *nextarc; } ArcNode; //下鄰接點
typedef struct vexnode
{ char data; //數據元素
ArcNode *firstarc;
} Vnode;//第一個鄰接點
typedef struct
{ int vexnum,arcnum; //圖的頂點個數
Vnode vertices[100];
} ALGraph;
給出將無向圖的鄰接矩陣轉換成鄰接表的算法。
解：void MatToList(MGraph g, ALGraph *G)
/*將鄰接矩陣g轉換成鄰接表G*/
{ int i,j,n=g.vexnum; ArcNode *p; /*n為頂點數*/
G=(ALGraph *)malloc(sizeof(ALGraph));
for (i=0;ivertices[i].data = g. vexs[i];
G->vertices[i].firstarc=NULL;
}
for (i=0;i=0;j--)
if (g.arcs[i][j]!=0)
{
p=(ArcNode *)malloc(sizeof(ArcNode)); /*創建結點*p*/
p->adjvex=j;
p->nextarc=G->adjlist[i].firstarc;/*將*p鏈到鏈表上*/
G->vertices[i].firstarc=p;
}
G->vexnum=n; G->arcnum=g.arcnum;
}
數據結構試題(3)
第一章
1-1
1.數據結構的研究內容不涉及（D）
A 數據結果如何組織 B 數據如何存儲
C 數據的運算如何實現 D 采用何種語言描述算法
2.描述數據的存儲結構時不需要知道（A）
A 計算機內存芯片的有關參數 B 數據元素的構成
C 數據元素的類型 D 使用何種算法描述語言
3.在選擇何種存儲結構時，一般不考慮（A）
A 數據元素的值如何 B 數據元素的數目多少
C 對數據可以實施哪些操作 D 所用編程語言實現這種結構是否方便
4.數據的存儲結構通常有（D）
A 順序存儲結構和鏈式存儲結構
B 順序存儲結構、鏈式存儲結構和索引結構
C 順序存儲結構、鏈式存儲結構和散引結構
D順序存儲結構、鏈式存儲結構、索引結構和散列結構
5.數據采用順序存儲結構，要求（D）
A 存儲的是屬于線性結構的數據
B 根據數據元素值的大小，有序地存放各數據元素
C 按照存儲單元地址由低到高的順序存放各數據元素
D 各數據元素存放方法有規律，能隱含地表示數據元素之間的邏輯關系
6.數據采用鏈式存儲結構，要求（A）
A 每個鏈接點占用一片地址連續的存儲空間
B 所有鏈接點占用一片地址連續的存儲空間
C 鏈接點的最后那個域一定為指針域
D 每個鏈接點有多少個直接后續結點，它就應該設置多少個指針域
9.一個完整的算法應該具有__B___等5個特性
A 可執行性、可移植性和可擴充性 B 可執行性、確定性和有窮性
C 確定性、有窮性和穩定性 D 易讀性、穩定性和安全性
10.下面的敘述中，不正確的是__A___
A 算法與程序都獨立于具體計算機與具體程序設計語言
B 程序是用計算機語言表達的算法
C 流程圖是圖形化的算法
D 程序就是算法，但算法不一定是程序
11.算法的執行時間一般與___D__無關
A 問題規模的大小 B 計算機的檔次
C 編程語言的種類和版本 D 算法設計者的水平
12.算法的時間復雜度主要與_A___有關
A 問題的規模 B 計算機的硬件性能
C 編譯程序的質量 D 程序設計語言
13.算法分析的前提是___A__
A 算法是正確的 B 算法盡可能簡單
C 算法運行時間少 D 算法占用空間少
14.算法分析的目的是___C__
A 研究算法的輸入與輸出之間的關系
B 找出數據結果的合理性
C 分析算法的效率，以求改進算法
D 分析算法的可讀性
15.算法分析的主要任務是分析__D_
A 算法是否具有較好的可讀性
B 算法中是否存在語法錯誤
C 算法的功能是否符合設計要求
D 算法的執行時間與問題規模之間的關系
1-2
1.“數據結構”課程研究的主要內容包括 邏輯結構 、 存儲結構 、和 算法 這3個方面
2.一個完整的算法應該具有 輸入 、 輸出 、 有窮性 、 確定性 和 有效性 5個特性
3數據的邏輯結構是指 數據元素在客觀世界中存在的邏輯關系 ，而存儲結構是指 具有某種邏輯關系的數據在計算機存儲器中的存儲方式 。
4.數據的邏輯結構可以分為 線性結構 和 非線性結構 兩大類
5.除了順存儲結構與鏈式存儲結構之外，數據的存儲結構通常還有 索引結構 和散列結構
6.邏輯上相鄰的數據元素在物理位置上也相鄰是 順序 存儲結構的特點之一
7.邏輯上相鄰的數據元素在物理位置上不要求相鄰是 鏈式 存儲結構的特點之一
8.為了實現隨機訪問，線性結構應該采用 順序 存儲結構
9.鏈式存儲結構的主要優點是 插入、刪除、等操作的時間效率高
10.算法分析是指 對算法質量優劣的評價 ，主要從 時間復雜度 和 空間復雜度 這兩個方面對算法進行分析
第二章
2-1
1.一個順序表占用的存儲空間大小與__B__無關
A 表的長度 B 元素的存放順序
C 元素的類型 D 元素中各字段的類型
2.設存儲分配是從低地址到高地址進行的。若每個元素占用4個存儲單元，則某元素的地址是指它所占用的單元的__A__
A 第1個單元的地址 B 第2個單元的地址
C 第3個單元的地址 D 第4個單元的地址
3.若線性表采用順序存儲結構，每個元素占用4個存儲單元，第1個元素的存儲地址為100，則第12個元素的存儲地址是__B_
A 112 B 114 C 148 D 412
4.若長度為n的線性表采用順序存儲結構，在表的第i個位置插入一個數據元素，i的合法值應該是__D_
A i>0 B i≤n C 1≤i≤n D 1≤i≤n+1
5.若長度為n的非空線性表采用順序存儲結構，刪除表的第i個數據元素，i的合法值應該是__C__
A i>0 B i≤n C 1≤i≤n D 1≤i≤n+1
6.若長度為n的非空線性表采用順序存儲結構，刪除表的第i個數據元素，首先需要移動表中__A_個數據元素
A n-1 B n+i C n-i+1 D n-i-1
7.若長度為n的線性表采用順序存儲結構，在表的第i個位置插入一個數據元素，需要移動表中_C_個元素
A 1 B n+i C n-i+1 D n-i-1
8.若頻繁地對線性表進行插入和刪除操作，該線性表應該采用__C_存儲結構合適
A 散列 B 順序 C 鏈式 D 索引
9.一般情況下，鏈表中所占用的存儲單元地址是_C_
A 無序的 B 連續的 C 不連續的 D 部分連續的
10.鏈表中的每一個鏈結點所占用的存儲單元__B_
A 不比連續 B 一定連續 C 部分連續 D 連續與否無所謂
11.與單向鏈表相比，雙向鏈表的優點之一是__A_
A 插入、刪除操作更簡便 B 可以進行隨機訪問
C 可以省略頭結點指針 D 可以訪問相鄰結點
15.在一個具有n個鏈結點的線性鏈表中查找某一個鏈結點，若查找成功，需要平均比較_C_個鏈結點
A n B n/2 C (n+1)/2 D (n-1)/2
18.在非空線性鏈表中由P所指的鏈結點后面插入一個有q所指的鏈結點的過程是依次執行_B_
A q->link=p;p->link=q
B q->link=p->link;p->link=q
C q->link=p->link:p=q
D p->link=q;q->link=p
2-2
1.順序表是一種_采用順序存儲結構的_線性表
2.在程序設計中，藐視線性表的順序存儲結構一般都用_數組_
4.在順序表的_緊挨著最后那個數據元素之后_插入一個新的數據元素不必移動任何元素
6.長度為n的線性表采用順序存儲結構，刪除其第i個元素（1≤i≤n），首先_將表的第i+1個元素至第n個元素依次前移一個位置_，然后_表長減1_
8.若某線性表采用順序存儲結構，每個元素占4個存儲單元，首地址為100，則第12個元素的存儲地址為_144_
9.線性表的鏈式存儲結構主要包括_單鏈表_、_循環鏈表_和_雙向鏈表_三種形式
10.線性表的順序存儲結構是通過_元素的地址_直接反映數據元素之間的邏輯關系，而鏈式存儲結構則是通過_指針_間接反映數據元素之間的邏輯關系
11.根據_鏈表的每個鏈結點中指針域的數目是1還是2_的多少，可以將鏈表分為線性鏈表（單鏈表）和雙向鏈表
16.若p為指向循環鏈表中某鏈結點的指針變量，判斷循環鏈表是否只有一個鏈結點的標志是“p->link===p”
第三章
3-1
1.所謂特殊矩陣是指_C__比較特殊
A 矩陣元素之間的關系 B 矩陣的處理辦法
C 矩陣元素的取值 D 矩陣的存儲方法
2.所謂稀疏矩陣是指_A_的矩陣
A 零元素較多且分布無規律 B 非零元素較少
C 元素較少 不適合采用二維數組表示
3.下面的說法中，不正確的是_D__
A 只需存放對稱矩陣中包括主對角線元素在內的下（或上）三角部分的元素即可
B 只需存放對角矩陣中的非零元素即可
C 稀疏矩陣中值為零的元素較多，因此可以采用三元組表方法存儲
D 稀疏矩陣中大量值為零的元素分布有規律，因此可以采用三元組表方法存儲
3-2
1.一般情況下，數組最基本的操作是_根據給定的數組下標檢索相應元素、修改或存取相應元素以及排序_
2.一個m行n列的矩陣可以看成是長度為_n_的線性表，表中的每一個元素是長度為m的線性表
3.一個m行n列的矩陣可以看成是長度為_m_的線性表，表中的每一個元素是長度為n的線性表
4.已知具有4行6列的矩陣A采用行序為主序存儲，每個元素占用4個存儲單元，該數組一共占用了_96_個存儲單元
7.對特殊矩陣采用壓縮存儲方法的主要目的是 節省存儲空間的開銷
第四章
4-1
1.堆棧和隊列的共同之處在于它們具有相同的_A_
A 邏輯特性 B 物理特性 C 運算方法 D 元素類型
2．若某堆棧初始為空，PUSH與POP分別表示對堆棧進行一次進棧操作，那么，對于進棧序列a,b,c,d,e，經過PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH，以后，得到的出棧序列號是_B_
A b,a B b,c C b,d D b,e
3，若5個元素的出棧序列為1,2,3,4,5，則進棧序列可能是_D_
A 2,4,3,1,5 B 2,3,1,5,4 C 3,1,4,2,5 D 3,1,2,5,4
4.某隊列初始為空，若它的輸入序列為a,b,c,d，它的輸出序列應為_A_
A a,b,c,d B d,c,b,a C a,c,b,d D d,a,c,b
6.設n個元素的進棧序列為1,2,3,…,n，出棧序列為P1，P2，P3，…，Pn，若P1=n，則pi（1≤ilink C p=top->link D p=p->link
16.在循環隊列中，若front與rear分別表示對頭元素和隊尾元素的位置，則判斷循環隊列對空的條件是_C_
A front=rear+1 B rear=front+1 C front=rear D front=0
17.描述某循環隊列的數組為QUEUE[0..M-1]，當循環隊列滿時，隊列中有_B_個元素
A M B M-1 C M+1 D M+2
18.在解決計算機主機與打印機之間速度不匹配問題時，通常設置一個打印數據緩沖區，主機將要輸出的數據依次寫入該緩沖區，而打印機則依次從該緩沖區，而打印機則依次從該緩沖區中取出數據打印，該緩沖區應該是一個_D_結構
A 線性表 B 數組 C 堆棧 D 隊列
19.設計一個遞歸問題的非遞歸算法通常需要設置_C_結構
A 線性表 B 數組 C 堆棧 D 隊列
20.中輟表達式A—（B＋C/D）×E的后綴形式是_B_
A ABC＋D/×E— B ABCD/＋E×— C AB—C＋D/E× D ABC—＋D/E×
4-2
1.堆棧和隊列的邏輯結構都是_線性_結構
2.堆棧的插入和刪除操作都是在_棧頂_位置上進行，而隊列的插入在_隊尾_進行，刪除操作在_隊頭_進行
3.對某堆棧執行刪除操作時，只有在_棧中只有一個位置的_情況下，才會將棧底元素刪除
4.在具體的程序設計過程中，堆棧的順序存儲結構一般是利用一個_數組_描述的，同時還要定義一個整型變量來_給出棧頂元素的位置_
5.堆棧采用順序存儲結構，未溢出的情況下往堆棧中插入一個元素，首先_將棧頂指針后移一個位置_，然后 將被插入元素放在修改后的棧頂指針所指出位置
6.隊列采用順序存儲結構，為溢出時插入一個元素 首先 將隊尾指針后移一個位置 ，然后再 將被插入元素放在修改后的隊尾指針所指出的位置
7.當堆棧的最大長度難以估計時，堆棧最好采用 鏈式 存儲結構
9.中輟形式的算術表達式A—（B＋C/D）×E的后綴形式為 ABC—D/E×＋
10.后綴形式的算術表達式ABCD/—E×＋的中綴形式為 A＋（B－C/D）×E
4-4
若按從左到右的順序依次讀入已知序列（a,b,c,d,e,f.,g）中的元素，然后結合堆棧操作，能得到下列序列中的哪些序列（每個元素進棧一次，下列序列表示出棧的次序）？
（d,e,c,f,b,g,a） （f,e,g,d,a,c,b） （e,f,d,g,b,c,a） （c,d,b,e,f,a,g）
答：可以得到.
4-5設有編號1,2,3,4的4輛列車，順序進入一個棧式結構的站臺，請寫出這4輛車列車開出車站的所有可能的順序
答：這4輛列車開出車站的所有可能的順序有4中種情況，它們分別如下：
1,2,3,4 1,2,4,3, 1,3,2,4 1,3,4,2, 2,1,3,4 1,4,3,2 2,1,4,3,
2,3,1,4 2,3,4,1 2,4,3,1 3,2,,1,4 3,2,4,1 3,4,2,1 4,3,2,1
第五章
5-1
（1）廣義表是指廣義表___D__
A.度為0 B.尚未賦值
C.不含任何原子元素 D.不含任何元素
（2）廣義表中的元素分為__C___
A.原子元素 B.表元素
C.原子元素和表元素 D任意元素
（3）廣義表的長度是指__A___
A.廣義表中的元素的個數 B.廣義表中原子元素的個數
C.廣義表中表元素的個數 D.廣義表中括號嵌套的層數
（4）廣義表的深度是指_D____
A.廣義表中元素的個數 B.廣義表中原子元素的個數
C.廣義表中表元素的個數 D.廣義表中括號嵌套的層數
（5）在一個長度為n、包含m個原子元素的廣義表中，_D____
A.m和n相等 B.m不大于n
C.m不小于n D.m與n無關
（6）廣義表A=（（），（a）,(b,)(c,d)）)的長度為__B___
A.2 B.3 C.4 D.5
（7）廣義表A=（（），（a）,(b,(c,d))）的深度為__B___
A.2 B.3 C.4 D.5
5-3請分別寫出下列各廣義表的長度和深度。
（1）A=（（a））
（2）B=（a，（b,c,d）,e,（））
（3）C=（x，（（y）,B,A））
（4）D=（A,D）
答：（1）A的長度為1
（2）B的長度為4
（3）C的長度為2
（4）D的長度為∞
第六章
6-1 請回答空串與空格串有何區別。
6-2 兩個字符串相等的充分必要條件是什么？
第七章
7-1
（1）樹形結構最適合用來描述__C___
A.有序的數據元素 B.無序的數據元素
C.數據元素之間具有的層次關系的數據 D.數據元素之間沒有關系的數據
（2）對于一棵具有n個結點、度為4的樹而言，_B____
A樹的深度最多是n—4 B.樹的深度最多是n—3
C.第i層上最多有4×（i—1）個結點 D.最少在某一層上正好友4個結點
（3）“二叉樹為空”意味著二叉樹__D___
A.由一些未賦值的空結點組成 B.根結點無子樹
C.不存在 D.沒有結點
（4）按照二叉樹的定義，具有3個結點的二叉樹有_D____種形態（不考慮數據信息的組合情況）
A.2 B.3 C.4 D.5
（5）若一棵深度為7的樹有8個度為1的結點，有7個度為2的結點，有6個度為3結點，有5個度為4的結點，有4個度為5的結點，有3個度為6的結點，有2個度為7的結點，則該樹一共有__D___個葉結點。
A.35 B.28 C.77 D.78
（6）若一棵二叉樹有10個度為2的結點，則該二叉樹的葉結點的個數是_B____
A.9 B.11 C.12 D.不確定
（7）若一棵滿二叉樹有2047個結點，則該二叉樹中葉結點的個數為_B____
A.512 B.1024 C.2048 D.4096
（10）具有n個結點的非空完全二叉樹的深度為_D___
A.n—1 B.n C.??log2n? D.??log2n?+1
（11）具有2000個結點的非空二叉樹的最小深度為__C___
A.9 B.10 C.11 D.12
（13）若二叉樹的前序序列與后序序列的次序正好相反，則該二叉樹一定是__D___的二叉樹。
A.空或僅有一個結點 B.其分支結點無左子樹
C.其分支結點無右子樹 C.其分支結點的度都為1
（14）任何一棵非空二叉樹中的葉結點的前序遍歷、中序遍歷與后序遍歷中的相對位置__B___
A.都會發生改變 B.不會發生改變
C.有可能會發生改變 D.部分會發生改變
（16）對一棵二叉樹排序進行__B___遍歷，可以得到該二叉樹的所有結點按值從小到大排列的序列。
A.前序 B.中序 C.后序 D.按層次
（21）平衡二叉樹中任意結點的平衡因子只能是__D___之一。
A.0,1,2 B.0,1 C.—1，+1 D.0，—1，+1
7-2
（1）任何非空樹中有且僅有一個結點沒有前驅結點，該結點就是樹的_根結點____
（2）樹的層次定義為__根結點為第1層，若某結點在第i層，則其孩子結點（若存在的話）在第i++層____
（5）非空二叉樹一共有_4____種基本形態
（6）非空二叉樹中第i層最多有__2的i-1次方___個結點。
（10）若具有n個結點的非空二叉樹有個葉結點，則該二叉樹有__-1___個度為2的結點，__n-2+1____個度為1的結點。
（11）對具有n個結點的完全二叉樹按照層次從上到下，每一層從左到右的次序對所有結點進行編號，編號為i的結點的雙親結點的編號為_??i/2? ____，左孩子的編號為___2i__，右孩子的編號為_2i+1____。
（13）二叉樹的遍歷方式通常有_前序遍歷__、_中序遍歷_、_后序遍歷__和__按層次遍歷__4種
（14）已知二叉樹的前序遍歷序列為ABDCEFG，中序遍歷序列為DBCAFEG，后續遍歷序列為_DCBFGEA____
（16）在二叉樹中，若結點A有左孩子Y和右孩子X，則在結點的前序序列、中序序列和后序序列中，結點__Y__一定的結點_X___的前面。
（18）對二叉排序樹進行_中序遍歷_，可以得到該二叉樹中所有結點組成的按值有序排列的序列。
7-6 一棵度為2的樹與一棵二叉有什么區別？
答：度為2的樹不一定是有序樹，而一棵度為2的二叉樹一定是有序樹。
7-7 請分別畫出具有3個結點的樹和具有3個結點的二叉樹的所有形態。
7-8 請分別列出如圖7.47所示二叉樹的所有葉結點與分支結點，并分別指出各結點的度以及所在的曾次數
7-10 已知某算術表達式的中綴形式為A+B×C—D/E，后綴形式為ABC×+DE/—，請寫出其前綴形式（利用二叉樹的遍歷序列）。
答：前綴形式為—＋A×BC/DE
7-11 已知某二叉樹的前序序列為ABDEGCFHIJ，中序序列為DBGEAHFIJC，請寫出后序序列。
答：后序遍歷序列：DGEBHJIFCA
第八章
8-1
（1）在一個圖中，所有頂點的度數之和等于所有邊數的__C___倍。
A.1/2 B.1 C.2 D.4
（2）一個具有n個頂點的無向圖最多有_A____條邊。
A.n(n-1)/2 B.n(n-1) C.n(n+1)/2 D. n2
（3）一個具有n個頂點的有向圖最多有___B__條邊
A.n(n-1)/2 B.n(n-1) C.n(n+1)/2 D. n2
（4）在一個具有n個頂點的無向圖中，有連同全部頂點至少需要__C___條邊。
A.n B.n+1 C.n-1 D2n
（5）具有n個頂點的連通圖的生成樹一定有_C____條邊。
A.n B.n+1 C.n-1 D2n
（7）在帶權圖中，兩個頂點之間的路徑長度是__D___。
A.路徑上的頂點數目 B.路徑上的邊的數目
C路徑上頂點和邊的數目 D.路徑上所有邊的權值之和
（8）若具有n個頂點的無向圖采用鄰接矩陣儲存方法，該鄰接矩陣一定為一個__B___。
A.一般矩陣 B.堆成矩陣 C.對角矩陣 D.稀疏矩陣
（9）若圖的鄰接矩陣中主對角線上的元素均為0，其余元素全為1，則可以斷定該圖一定__C___。
A.是無向圖 B.是有向圖
C.是完全圖 D.不是帶權圖
（10）有向圖的鄰接表的第i個鏈表中的邊結點數目是第i個頂點的_B____
A.度數 B.出度 C.入度 D.邊數
（11）若某圖的鄰接表中的邊結點數目為奇數，則該圖__C___。
A.一定有奇數個頂點 B.一定有偶數個頂點
C.一定是有向圖 C.可能是無向圖
（12）若某圖的鄰接表中的邊結點數目為偶數，則該圖__C___。
A.一定是無向圖 B.可能是有向圖
C.可能是無向圖，也可能是有向圖 D.一定是偶數個頂點
（13）若無向圖有k條邊，則相應的鄰接表中就有__C___個邊結點
A.k-1 B.k C.2k D. k2
（22）已知某有向圖G=（V，E），其中V={v1,v2,v3,v4,v5,v6}，E={，，，，，，，}，G的拓撲序列是__A___
A.v3,v1,v4,v5,v2,v6 B.v3,v4,v1,v5,v2,v6
C.v1,v3,v4,v5,v2,v6 D.v1,v4,v3,v5,v2,v6
（24）下面涉及到AOE網的敘述中，正確的是_D____。
A.AOE網是一個帶權的連通無向圖
B.AOE網是一個帶權的連通有向圖
C. AOE網是一個帶權的無環連通圖
D. AOE網是一個帶權的無環有向圖
（25）下面關于AOE網的敘述中，不正確的是_D____。
A.若所有關鍵活動都提前完成，則整個工程一定能夠提前完成
B.即使所有非關鍵活動都未按時完成，整個工程仍有可能按時完成
C.任何一個關鍵活動的延期完成，都會導致整個工程的延期完成
D.任何一個關鍵活動的提前完成，都會導致整個工程的提前完成
8-2
設一有向圖為G=（V,E）,其中，V={V1,V2.V3.V4，},E={,,,,},請畫出該有向圖。
8-3已知給定有向圖如圖所示，請完成
（1）分別寫出每個頂點的入度與出度
（2）畫出相應的鄰接矩陣與鄰接表
（3）畫出強連通分量
第九章
9-1
1.衡量查找算法性能好壞的主要標準是（D）
A 參加比較的關鍵字值的多少
B 被查找的關鍵字值在關鍵字序列中的位置
C 關鍵字序列中是否存在被查找關鍵字值
D 關鍵字值的平均比較次數的多少
2.順序查找方法的有點之一是（A）
A 被查找對象的排列次序無限制 B 適合排序連續順序文件的查找
C 適合鏈接順序文件的查找 D 查找時間效率高
3.對線性表采用折半查找，該線性表必須（C）
A 元素按值有序排列
B 采用順序結構
C 元素按值有序排列，并且采用順序存儲結構
D 元素按值有序排列，并且采用鏈式存儲結構
6.為了實現分塊查找，線性表必須采用（C）結構
A 順序存儲 B 鏈式存儲 C 索引存儲 D 散列存儲
7.只能在順序存儲結構上才能實現的查找辦法是（C）法
A 順序存儲 B樹形查找 C 折半查找 D 散列查找
9-2
1.文件的邏輯結構是指_邏輯記錄之間具有的邏輯關系_，文件的物理結構是指_邏輯記錄在存儲介質上的組織方式__
2.文件的物理結構中通常有__連續組織方式___、__鏈接組織方式___和__隨機組織方式__3種組織方式
3.文件的關鍵字是_能夠標識不同記錄的屬性或屬性組___
4.文件的最基本操作是_查找__和_排序___
5.對線性表采用折半查找方法，該線性表必須采用__順序___存儲結構，并且_數據元素按值有序排列___
6．在鏈表中只能采用_順序_查找
數據結構試題(4)
一、簡述與證明
1. 給出排序穩定性的含義、作用和證明方法，并給出簡單選擇排序方法的排序穩定性證明。
2. 說明、、三種函數階的定義，給出函數階的示例證明過程。
3. 設，給出間的函數階證明過程。
二、方法選擇
1. 只想得到N個元素序列中第K個最大元素之前的部分遞減有序序列（K
數據結構試題(5)
數據結構實驗1窗體頂端
窗體底端
一、程序設計題?(10分)
1. 雙向鏈表排序問題 4分
題目描述
隨機輸入一些數據，然后排序后輸出。建議使用雙向鏈表結點和雙向鏈表類來實現。參考第4講ppt里的第3個例題。
可以不使用下面的參考代碼，自行編寫。
關于雙向鏈表和雙向結點的參考代碼如下：
// 自定義類型
enum StatusCode {SUCCESS, FAIL, UNDER_FLOW, OVER_FLOW,RANGE_ERROR, DUPLICATE_ERROR,
NOT_PRESENT, ENTRY_INSERTED, ENTRY_FOUND, VISITED, UNVISITED};
template
void Write(const ElemType &e)
// 操作結果: 顯示數據元素
{
cout position)
{ // 當前位置在所查找位置之后,向前查找
for (; curPosition > position; curPosition--)
curPtr = curPtr->back; // 查找位置position
}
return curPtr;
}
template
void DblLinkList::Init()
// 操作結果：初始化線性表
{
head = new DblNode; // 構造頭指針
head->next = head; // 空循環鏈表的頭結點后繼為頭結點本身
head->back = head; // 空雙向循環鏈表的頭結點前驅為頭結點本身
curPtr = head; curPosition = 0;// 初始化當前位置
count = 0; // 初始化元素個數
}
template
DblLinkList::DblLinkList()
// 操作結果：構造一個空鏈表
{
Init();
}
template
DblLinkList::~DblLinkList()
// 操作結果：銷毀線性表
{
Clear(); // 清空線性表
delete head; // 釋放頭結點所點空間
}
template
int DblLinkList::Length() const
// 操作結果：返回線性表元素個數
{
return count;
}
template
bool DblLinkList::Empty() const
// 操作結果：如線性表為空，則返回true，否則返回false
{
return head->next == head;
}
template
void DblLinkList::Clear()
// 操作結果：清空線性表
{
ElemType tmpElem; // 臨時元素值
while (Length() > 0)
{ // 表性表非空，則刪除第1個元素
Delete(1, tmpElem);
}
}
template
void DblLinkList::Traverse(void (*visit)(const ElemType &)) const
// 操作結果：依次對線性表的每個元素調用函數(*visit)
{
for (DblNode *tmpPtr = head->next; tmpPtr != head; tmpPtr = tmpPtr->next)
{ // 用tmpPtr依次指向每個元素
(*visit)(tmpPtr->data); // 對線性表的每個元素調用函數(*visit)
}
}
template
int DblLinkList::GetCurPosition() const
// 操作結果：返回當前位置
{
return curPosition;
}
template
StatusCode DblLinkList::GetElem(int position, ElemType &e) const
// 操作結果：當線性表存在第position個元素時，用e返回其值，返回ENTRY_FOUND,
// 否則返回NOT_PRESENT
{
if (position < 1 || position > Length())
{ // position范圍錯
return NOT_PRESENT; // 元素不存在
}
else
{ // position合法
DblNode *tmpPtr;
tmpPtr = GetElemPtr(position); // 取出指向第position個結點的指針
e = tmpPtr->data; // 用e返回第position個元素的值
return ENTRY_FOUND;
}
}
template
StatusCode DblLinkList::SetElem(int position, const ElemType &e)
// 操作結果：將線性表的第position個位置的元素賦值為e,
// position的取值范圍為1≤position≤Length(),
// position合法時返回SUCCESS,否則返回RANGE_ERROR
{
if (position < 1 || position > Length())
{ // position范圍錯
return RANGE_ERROR;
}
else
{ // position合法
DblNode *tmpPtr;
tmpPtr = GetElemPtr(position); // 取出指向第position個結點的指針
tmpPtr->data = e; // 設置第position個元素的值
return SUCCESS;
}
}
template
StatusCode DblLinkList::Delete(int position, ElemType &e)
// 操作結果：刪除線性表的第position個位置的元素, 并用e返回其值,
// position的取值范圍為1≤position≤Length(),
// position合法時返回SUCCESS,否則返回RANGE_ERROR
{
if (position < 1 || position > Length())
{ // position范圍錯
return RANGE_ERROR;
}
else
{ // position合法
DblNode *tmpPtr;
tmpPtr = GetElemPtr(position - 1); // 取出指向第position - 1個結點的指針
tmpPtr = tmpPtr->next; // tmpPtr指向第position 個結點
tmpPtr->back->next = tmpPtr->next; // 修改向右的指針
tmpPtr->next->back = tmpPtr->back; // 修改向左的指針
e = tmpPtr->data; // 用e返回被刪結點元素值
if (position == Length())
{ // 刪除尾結點,當前結點變為頭結點
curPosition = 0; // 設置當前位置的序號
curPtr = head; // 設置指向當前位置的指針
}
else
{ // 刪除非尾結點,當前結點變為第position個結點
curPosition = position; // 設置當前位置的序號
curPtr = tmpPtr->next; // 設置指向當前位置的指針
}
count--; // 刪除成功后元素個數減1
delete tmpPtr; // 釋放被刪結點
return SUCCESS;
}
}
template
StatusCode DblLinkList::Insert(int position, const ElemType &e)
// 操作結果：在線性表的第position個位置前插入元素e
// position的取值范圍為1≤position≤Length()+1
// position合法時返回SUCCESS, 否則返回RANGE_ERROR
{
if (position < 1 || position > Length() + 1)
{ // position范圍錯
return RANGE_ERROR; // 位置不合法
}
else
{ // position合法
DblNode *tmpPtr, *nextPtr, *newPtr;
tmpPtr = GetElemPtr(position - 1); // 取出指向第position-1個結點的指針
nextPtr = tmpPtr->next; // nextPtr指向第position個結點
newPtr = new DblNode(e, tmpPtr, nextPtr);// 生成新結點
tmpPtr->next = newPtr; // 修改向右的指針
nextPtr->back = newPtr; // 修改向左的指針
curPosition = position; // 設置當前位置的序號
curPtr = newPtr; // 設置指向當前位置的指針
count++; // 插入成功后元素個數加1
return SUCCESS;
}
}
template
DblLinkList::DblLinkList(const DblLinkList & ccopy)
// 操作結果：由線性表copy構造新線性表——復制構造函數模板
{
int copyLength = ccopy.Length(); // copy的長度
ElemType e;
Init(); // 初始化線性表
for (int curPosition = 1; curPosition > it.expn;
fb.InsItem(it);
}
while( cin>>c && c)
{
if(c==1) fc=fa+fb;
else if(c==2) fc=fa-fb;
else fc=fa*fb;
fc.Display();
cout
數據結構試題(6)
數據結構
實驗一 線性表抽象數據類型的實現
【實驗內容】1.初始化雙鏈表
2.對初始化好的雙鏈表進行銷毀，清空，判空，求長，獲取元素的值，求某個元素的前驅或后繼，在某個元素之后插入元素，刪除某個元素
3.我在小組的負責的程序段是在某個元素之后插入元素
【實驗方法與步驟】
編寫程序如下：
#include
#include
#define TRUE 1
#define OK 1
#define FALSE 0
#define ERROR 0
#define OVERFLOW 0
typedef char ElemType;
typedef int status;
typedef struct DuLNode
{ElemType data;
struct DuLNode *prior,*next;
}DuLNode,*DuLinkList;
status InitList(DuLinkList &L);
status ClearList(DuLinkList L);
status DestoryList(DuLinkList &L);
status ListEmpty(DuLinkList L);
int ListLength(DuLinkList L);
status GetElem(DuLinkList L,int i,ElemType &e);
int LocateElem(DuLinkList L,ElemType e);
status PreElem(DuLinkList L,ElemType cur_e,ElemType &pre_e);
status NextElem(DuLinkList L,ElemType cur_e,ElemType &next_e);
status GetElem(DuLinkList L,int i);
status ListInsert(DuLinkList L,int i,ElemType e);
status ListDelete(DuLinkList L,int i,ElemType &e);
void ppp(ElemType e);
#include "zongde.h"
status InitList(DuLinkList &L)
{
L=(DuLinkList)malloc(sizeof(DuLNode));
if(L)
{ L->next=L;
L->prior=L;
return OK;
}
else
return OVERFLOW;
}
status DestroyList(DuLinkList &L)
{
DuLinkList q,p=L->next;
while(p!=L)
{
q=p->next;
free(p);
p=q;
}
free(L);
L=NULL;
return OK;
}
status ClearList(DuLinkList L)
{
DuLinkList q,p;
p=L->next;
while(p!=L)
{
q=p->next;
free(p);
p=q;
}
L->next=L->prior=L;
return OK;
}
status ListEmpty(DuLinkList L)
{
if(L->next==L&&L->prior==L)
return TRUE;
else
return FALSE;
}
int ListLength(DuLinkList L)
{
int i=0;
DuLinkList p;
p=L->next;
while(p!=L)
{
i++;
p=p->next;
}
return i;
}
status GetElem(DuLinkList L,int i,ElemType &e)
{ //當第i個元素存在時，其值賦給e并返回OK，否則返回ERROR
int j=1; //j為計時器
DuLinkList p;
p=L->next;
while(p!=L&&jnext;
j++;
}
if(p==L||j>i) //第i個元素不存在
return ERROR;
e=p->data; //取第i個元素
return OK;
}
int LocateElem(DuLinkList L,ElemType e)
{
int i=0;
DuLinkList p;
p=L->next;
while(p!=L)
{
i++;
if(p->data==e)
return i;
else
p=p->next;
}
}
status PreElem(DuLinkList L,ElemType cur_e,ElemType &pre_e)
{ DuLinkList p;
p=L;
{ if (p->data==cur_e)
{pre_e=p->prior->data;
return TRUE;
}
p=p->next;
}
return FALSE;
}
status ListInsert(DuLinkList L,int i,ElemType e)
{
DuLinkList p,s;
int k;
p=L;
if(iListLength(L)+1)//i值不合法
return ERROR;
k=LocateElem(L,e);//在L中確定第i-1個元素的位置指針p
if(!k)
return ERROR;
s=(DuLinkList)malloc(sizeof(DuLNode));
if(!s)
return OVERFLOW;
s->data=e;//在第i-1個元素之后插入
s->prior=p;
s->next=p->next;
p->next->prior=s;
p->next=s;
return OK;
}
status ListDelete(DuLinkList L,int i,ElemType &e)
{
DuLinkList p;
p=L;
if(iListLength(L))
return ERROR;
GetElem(L,i,e);
if(!p)
return ERROR;
e=p->data;
p->prior->next=p->next;
p->next->prior=p->prior;
free(p);
return OK;
}
void ppp(ElemType e)
{
printf("插入后新鏈表:\n");
printf("%c",e);
}
#include
#include "zongde.h"
status InitList(DuLinkList &L)
{
L=(DuLinkList)malloc(sizeof(DuLNode));
if(L)
{ L->next=L;
L->prior=L;
return OK;
}
else
return OVERFLOW;
}
status GetElem(DuLinkList L,int i,ElemType &e)
{//當第i個元素存在時，其值賦給e并返回OK，否則返回ERROR
int j=1; //j為計時器
DuLinkList p;
p=L->next;
while(p!=L&&jnext;
j++;
}
if(p==L||j>i) //第i個元素不存在
return ERROR;
e=p->data; //取第i個元素
return OK;
}
status ListInsert(DuLinkList L,int i,ElemType e)
{
DuLinkList p,s;
int k;
p=L;
if(iListLength(L)+1)//i值不合法
return ERROR;
k=LocateElem(L,e);//在L中確定第i-1個元素的位置指針p
if(!k)
return ERROR;
s=(DuLinkList)malloc(sizeof(DuLNode));
if(!s)
return OVERFLOW;
s->data=e;//在第i-1個元素之后插入
s->prior=p;
s->next=p->next;
p->next->prior=s;
p->next=s;
return OK;
}
int main
{
DuLinkList pA;
InitList(pA);
int newdate;
int i,j,e;
printf("please input the position you want to insert: \n")；
scanf("%d",&i); /* 輸入要插入的位置 */
printf("please input the data you want to insert: \n");
scanf("%d",&newdata); /* 輸入新結點的數據 */
ListInsert(pA,i,newdata); /* 調用雙向鏈表的插入函數
for(j=1;j0;k--)
weight[k]=weight[k-1];
weight[0]=0;
ht=huffmantree(n,weight);
huffmancoding(n,hc,ht,str);
}
void huff()
{
int i;
while(1)
{
huffman();
printf("\n是否繼續？\n1.繼續\n2.返回菜單\n");
scanf("%d",&i);
if(i==2)break;
fflush(stdin);
getchar();
}
}
main()
{
int i,j,k;
while(1)
{
printf("請選擇要運行的功能：\n");
printf("1.哈夫曼編碼譯碼器\n");
printf("2.退出該程序\n\n");
printf("你的選擇為：");
scanf("%d",&i);
switch(i)
{
case 1:huff();break;
case 2:exit(0);
default:break;
}
fflush(stdin);
getchar();
system("cls");
}
}
【實驗結果】
對一組字符求哈夫曼編碼：you,are,my,sunshine!
各個字符的權值為：y的權重為：11; o的權重為：23;u的權重為：5;,的權重為：7;a的權重為：9;r的權重為：121; e的權重為：211;,的權重為：985;m的權重為：66;y的權重為：89;,的權重為：0;s的權重為：2;u的權重為：44;n的權重為：58;s的權重為：93;h的權重為：36; i的權重為：47;n的權重為：14;e的權重為：12;!的權重為：0
各個字符的哈夫曼編碼為:y的編碼為：01111011;o的編碼為:001100;u的編碼為：011110011;,的編碼為：01111000; a的編碼為：01111010;r的編碼為：0110;e的編碼為：010;,的編碼為：1;m的編碼為：01110;y的編碼為：0000;,的編碼為：
01111001000;s的編碼為：0010;h的編碼為：011111;i的編碼為：00011;n的編碼為：0011011;e的編碼為：0011010;!的編碼為：01111001001
程序運行結果為：
實驗四 快速排序
【實驗內容】1.用折半查找實現折半排序
2.利用折半排序對四十組數據或四十組以上數據排序
【實驗方法與步驟】
編寫程序如下：
#include
#include
#define MAX 100
typedef struct {
int elem[MAX];
int length;
}SSTable;
void BInsertSort(SSTable *L);
int main(){
int m,i=1,a,k;
SSTable ST;
printf("Please input those numbers and press \"-1\" to end!\n");
scanf(" %f",&a);
while(a!=-1){
ST.elem[i++]=a;
scanf(" %f",&a);
}
ST.length=i-1;
BInsertSort(&ST);
printf("The result is:\n");
for(m=1;m
數據結構試題(7)
數據結構課程設計
課程設計名稱：圖的基本操作實現
教 學 類 型：課程設計
學 院 名 稱：軟件學院
專 業 班 級：軟件開發1221808
姓 名：劉貞杭
學 號： 201220180804
目 錄
一、問題描述 1
二、算法思想 1
三、模塊劃分 1
四、主函數脈絡圖 2
五、程序清單 2
六、測試結果 12
七、總結 14
八、參考資料 14
一、問題描述
圖的基本操作的實現
(1)自選存儲結構,輸入含n個頂點（用字符表示頂點）和e 條邊的圖G；
(2)求每個頂點的度,輸出結果；
(3)指定任意頂點x為初始頂點,對圖G作DFS遍歷,輸出DFS 頂點序列(提示:使用一個棧實現DFS)；
(4)指定任意頂點x為初始頂點,對圖G作BFS遍歷,輸出BFS 頂點序列(提示:使用一個隊列實現BFS)；
(5)輸入頂點x,查找圖G:若存在含x的頂點,則刪除該結點及 與之相關連的邊,并作DFS遍歷(執行操作3)；否則輸出信 息“無x”；
(6)判斷圖G是否是連通圖，輸出信息“YES”/“NO”；
(7)如果選用的存儲結構是鄰接矩陣,則用鄰接矩陣的信息生 成圖G的鄰接表,即復制圖G,然再執行操作(2)；反之亦然。
二、算法思想
選取鄰接矩陣的存儲結構創建一個n個頂點，e條邊的圖；設定計數器統計每個頂點的出度和入度，即為每個頂點的度；編寫LocateVex(AdjMGraph G,char x)函數，將任意輸入的頂點的下標記錄在k中返回k,對書中深度遍歷和廣度遍歷做相應的修改使其從頂點k開始遍歷，即可實現任意指定頂點為初始頂點對圖的深度和廣度遍歷；輸入頂點x，若查找存在，刪除該節點和與之相關聯的邊，然后進行深度遍歷，若查找不存在，輸出“無x”；判斷圖是否連通從兩個方面，一是n個頂點必須有大于等于n-1條邊，二是沒有任何一個頂點的度為零，同時滿足這兩個條件的圖是連通的，否則就不是連通的；利用已生成的以鄰接矩陣方式存儲的圖G的信息創建以鄰接表存儲的圖G，然后使用計數器統計每個節點的出度和入度，求出各節點的度。
三、模塊劃分
1.鄰接矩陣存儲結構下圖的操作
Initiate(AdjMGraph *G,int n) 初始化
InsertVertex(AdjMGraph *G,DataType vertex) 在圖G中插入節點vertex
InsertEdge(AdjMGraph *G,int v1,int v2,int weight) 在圖G中插入邊
DeleteEdge(AdjMGraph *G,int v1,int v2) 在圖G中刪除邊
DeleteVertex(AdjMGraph *G,int v) 刪除節點V
GetFirstVex(AdjMGraph G,int v) 在圖G中尋找序號為v的節點的第一個鄰接節點
GetNextVex(AdjMGraph G,int v1,int v2) 在圖G中尋找v1節點的鄰接節點v2的下一個鄰接節點
CreatGraph(AdjMGraph *G,DataType V[],int n,RowColWeight E[],int e) 建圖
VexDegree(AdjMGraph *G,DataType V[],int n,RowColWeight E[],int e) 求度
2.圖的操作函數
LocateVex(AdjMGraph G,char x) 記錄遍歷初始節點的下標
DepthFSearch(AdjMGraph G,int v,int visited[],void Visit(DataType item))
DepthFirstSearch(AdjMGraph G,int k,void Visit(DataType item)) 深度優先遍歷
BroadFSearch(AdjMGraph G,int v,int visited[],void Visit(DataType item))
BroadFirstSearch(AdjMGraph G,int k,void Visit(DataType item)) 廣度優先遍歷
ElseDFS(AdjMGraph G,int k,void Visit(DataType item)) 刪除節點x后的遍歷
GraphConect(AdjMGraph G,RowColWeight E[],int e) 判斷圖是否連通
AdacencyMatrix(AdjMGraph G) 鄰接矩陣的輸出
AdjacencyList(AdjMGraph G,RowColWeight E[]) 鄰接表的輸出
3.鄰接表存儲結構下的圖的操作
AdjInitiate(AdjLGraph *G) 初始化
InsertVertex1(AdjLGraph *G,int i,DataType vertex) 在圖中插入節點vertex
InsertEdge1(AdjLGraph *G,int v1,int v2) 在圖中加入邊
CreatGraph1(AdjLGraph *G,DataType v[],int n,RowColWeight d[],int e) 建圖
VexDegree1(AdjLGraph *G,DataType V[],int n,RowColWeight E[],int e) 求度
4.主函數 main(void)
四、主函數脈絡圖
五、程序清單
#include"SeqList.h"
typedef struct
{
SeqList Vertices;
int edge[MaxVertices][MaxVertices];
int numOfEdges;
}AdjMGraph;
void Initiate(AdjMGraph *G,int n)
{
int i,j;
for(i=0;iedge[i][j]=MaxWeight;
}
G->numOfEdges=0;
ListInitiate(&G->Vertices);
}
void InsertVertex(AdjMGraph *G,DataType vertex)
{
ListInsert(&G->Vertices,G->Vertices.size,vertex);
}
void InsertEdge(AdjMGraph *G,int v1,int v2,int weight)
{
if(v1G->Vertices.size || v2G->Vertices.size)
{
printf("參數v1或v2越界出錯!\n");
exit(1);
}
G->edge[v1][v2]=weight;
G->numOfEdges++;
}
void DeleteEdge(AdjMGraph *G,int v1,int v2)
{
if(v1G->Vertices.size || v2G->Vertices.size || v1==v2)
{
printf("參數v1或v2越界出錯!\n");
exit(1);
}
if(G->edge[v1][v2]==MaxWeight || v1==v2)
{
printf("該邊不存在!\n");
exit(0);
}
G->edge[v1][v2]=MaxWeight;
G->numOfEdges--;
}
void DeleteVertex(AdjMGraph *G,int v)
{
int n=ListLength(G->Vertices),i,j;
DataType x;
for(i=0;i0 && G->edge[i][j]numOfEdges--;
for(i=v;iedge[i+1][j];
for(i=0;iedge[i][j+1];ListDelete(&G->Vertices,v,&x);
}
int GetFirstVex(AdjMGraph G,int v)
{
int col;
if(vG.Vertices.size)
{
printf("參數v1越界出錯!\n");
exit(1);
}
for(col=0;col0 && G.edge[v][col]numOfVerts1=0;
G->numOfEdges1=0;
for(i=0;ia[i].sorce=i;
G->a[i].adj=NULL;
}
}
void InsertVertex1(AdjLGraph *G,int i,DataType vertex)
{
if(i>=0 && ia[i].data=vertex;
G->numOfVerts1++;
}
else printf("結點越界");
}
void InsertEdge1(AdjLGraph *G,int v1,int v2)
{
Edge *p;
if(v1=G->numOfVerts1 || v2=G->numOfVerts1)
{
printf("參數v1或v2越界出錯!");
exit(0);
}
p=(Edge *)malloc(sizeof(Edge));
p->dest=v2;
p->next=G->a[v1].adj;
G->a[v1].adj=p;
G->numOfEdges1++;
}
void CreatGraph1(AdjLGraph *G,DataType v[],int n,RowColWeight d[],int e)
{
int i,k;
AdjInitiate(G);
for(i=0;i
數據結構試題(8)
數據結構知識整理（部分）
第一章：緒論
1．數據：數據是外部信息的載體，他能夠被計算機識別、存儲和加工處理，是計算機程序加工的原料；
2．數據元素：數據元素是數據的基本單位，在計算機中通常被作為一個整體進行考慮和處理；
3．一個數據元素可由若干個數據項組成。數據項是不可分割的、含有獨立意義的最小數據單位，數據項有時也稱為字段或域；
4．數據結構是相互之間存在的一種或多種特定關系的數據元素的集合。在任何問題中，數據元素之間都不是孤立的，而是存在著一定的關系，這種關系稱為結構；
5．4種基本數據結構：集合：只有“同屬一個集合”的關系；
線性結構：存在著一對一的關系；
樹形結構：存在著一對多的關系；
圖狀結構：存在著多對多的關系；
6．數據結構包括數據的邏輯結構和物理結構。邏輯結構：從具體問題抽象出來的數學模型，與數據在計算機中的具體儲存沒有關系。從邏輯上可以把數據結構分為線性結構和非線性結構，其中集合、樹、圖形結構屬于非線性結構；
7．數據的物理結構又叫存儲結構，是數據在計算機中的表示和存儲，包括數據元素的表示和存儲以及數據元素之間關系的表示和存儲，存儲結構必須依賴于計算機。數據元素之間的關系在計算機中的表示有兩種:順序映像和非順序映像。分別對應兩和數據的存儲結構：順序存儲結構和鏈式存儲結構；順序存儲結構是指把邏輯上相鄰的數據元素存儲在物理位置相鄰的存儲單元中；鏈式存儲結構不要求必須相鄰。鏈式存儲結構中的數據元素叫做結點，在結點中附近設地址域 來存儲與該結點相鄰的結點的地址來實現結點之間邏輯關系；
8．在軟件設計中，抽象數據類型通常包括定義、表示和實現三部分
9．算法：是指在有限的時間范圍之內為解決某一問題而采取的方法和步驟的準確完整的描述，他是一個有窮的規則序列，這些規則決定了解決某一特定問題的一系列運算；
10算法的特征：有窮性，確定性，可行性，輸入，輸出；算法+數據結構=程序；
11．評價一個算法的主要標準：正確性，可讀性，健壯性，運行時間，占用空間；
健壯性要求算法要全面細致的考慮所有可能出現的邊界情況和異常情況；實際上，算法的時間效率和空間效率經常是一對矛盾，相互抵觸，我們要根據實際問題進行處理，有時要犧牲空間換取時間，有時要犧牲時間換取空間。運行的時間還取決于：計算機硬件的速度；書寫程序的高級語言；問題的規模；，
12．時間復雜度和空間復雜度：算法在運行時所要耗費的時間代價和算法中數據結構所占用的空間代價；
13．時間復雜度的比較：O（1）＜O（log n）＜O(n)＜O( nlog n)＜O（n2）O（n3）；
14．算法分析的兩個主要方面是文檔復雜性和時間復雜性；
15．算法分析的目的是分析算法效率的合理性；
第二章：線性表
1．線性結構的特點：（1）存在唯一的一個被稱作“第一個”的數據元素；（2）存在唯一的一個被稱作“最后一個”的數據元素；（3）除第一個之外，集合中每一個數據元素均只有一個前驅；（4）除最后一個之外，集合中每一個數據元素均只有一個后繼；
2．線性表是n個數據元素的有限序列，數據元素可以有多個項組成。對于同一個線性表，其中的數據元素必須具有相同特性（同一種數據類型），相鄰的數據元素存在序偶關系；
3．數據的下標為該元素在線性表中的位序；線性表中數據元素之間的相對位置關系可以與數據元素的值有關也可以無關；
4．線性表的常見操作：初始化——構造空的線性表；
銷毀——銷毀一個以存在的線性表；
查找——查出線性表中滿足特定條件的地步；
存取——存取線性表中的第i個元素，檢查或更新某個數據項
求長度——求出線性表中數據元素的個數；
判空——判斷當前線性表是否為空；
5．線性表的順序表示是指的用一組地址連續的存儲單元依次存儲線性表的數據元素。線性表的這種機內表示稱作線性表的順序存儲結構或順序映像，通常稱這種存儲結構的線性表為順序表。以元素在計算機內的“物理位置相鄰”來表示線性表中數據之間的邏輯關系；順序表是一種隨機存取的存儲結構，通常用數組來描述數據結構中的順序存儲結構；
6．線性表的插入注意幾點：1.在向順序表中進行插入操作時先檢查表空間是否滿了；
2．要檢驗插入位置的有效性1＜i＜n+1（n為源表長）；
3．注意數據的移動方向；
7．順序表的刪除是指刪除表中的第i個元素，注意以下幾點：
1．要檢查刪除位置的有效性；
2．刪除ai后，該數據不存在，如果需要，先取出再刪除；
必須通過順序元素的移動才能體現邏輯關系的變化；元素的移動次數不僅與表長有關，而且還與插入或刪除的位置有關。插入或刪除一個數據元素，平均移動表中的一半元素；
8．順序表的查找是指在順序表中查找某個值等于給定值的元素位置，在順序表L中查找是否存在和e相同的數據元素的最簡便方法是，令e和L中的數據元素逐個比較；
9．線性表的鏈式存儲結構是用一組任意的存儲單元來存放線性表的數據元素，這組存儲單元可以是連續的也可以是不連續的；對于每一個元素而言，除了存儲本身的信息外，還需存儲一個指示其直接后繼存放位置的指針。存儲元素數據的信息區域稱為信息域，存儲直接后繼存放位置的域叫做指針域。由于此鏈表中的每個結點中只有一個指向后繼的指針，所以成其為單鏈表或線性鏈表（可以用頭指針來表示一個單鏈表）
10．單鏈表的插入需修改插入位置之前的結點和當前插入饑餓點的指針指向（修改指針域，將新結點插入）；單鏈表的刪除是指刪除單鏈表的第i個結點，可將刪除位置之前的結點（i-1個）的指針指向第i+1個結點，然后釋放掉該結點所占用的內存；
11．循環鏈表：它的特點是表中最后一個指針的結點的指針域不再為空，而是指向表頭結點，整個鏈表形成一個環。由此可以從任意的結點出發均可找到鏈表中的其他結點。可以改變一下鏈表的標識方法，不用頭指針而用一個指向表尾結點的指針R來標識，這樣，從尾結點的指針域立即可以得到表頭結點的地址無論查找第一個還是最后一個都很方便；
12．找后繼的時間復雜度為O（1），找前驅的時間復雜度為O（n）如果希望找前驅的時間復雜度也為O（1），需要付出空間的代價，在每個結點中再設一個指向前驅的指針域，由這種結點組成的鏈表稱為雙向鏈表；
13．順序存儲結構可以實現對表中元素的隨機存取，但在進行插入或刪除操作時需要大量元素；鏈表在存儲空間的合理利用、插入刪除操作不需要移動大量元素方面優于順序表，但鏈表不能像順序表那樣實現元素的隨機存取；14.若主要進行元素存取的操作，則宜選用順序存儲結構；若主要進行插入、刪除操作，則宜選用鏈式存儲結構。在多數場合下，鏈表是線性表的首選存儲結構。
14.順序表的初始化，插入，刪除，查找；單鏈表的初始化，插入，刪除，查找，建立；
第三章：棧和隊列
1．棧是限定僅在表尾進行插入和刪除操作的線性表。允許插入、刪除的一端稱為棧頂，另一端稱為棧底，不含任何數據元素的棧稱為空棧。棧的修改是按先進后出的原則進行的。因此，棧又被稱為后進先出的線性表。棧頂的位置隨著結點的插入和刪除而變化，為此需要一個稱為棧頂指針的位置指示器來表示棧頂的當前位置。
2．和線性表類似，棧也有兩種存儲表示方法：順序棧和鏈棧。順序棧：利用一組地址連續的存儲單元一次存放自棧底到棧頂的數據元素；
3．入棧時，首先應判斷棧是否滿了，棧滿時不能入棧；否則出現空間的溢出，這種現象稱為上溢。出棧和讀棧頂元素操作，應先判斷棧是否為空，為空不能操作；
4．棧的鏈接存儲結構稱為鏈棧，利用鏈表實現。鏈表中的每個數據元素有兩部分信息組成一部分是存儲本身的信息，一部分是存儲一個指示其直接后繼的信息（即直接后繼的存儲位置）。我們稱它有兩個域：其中存儲數據元素信息的域稱為數據域；存儲直接后繼存儲位置的域稱為指針域。鏈棧沒有必要向單鏈表一樣附加頭指針；
5．隊列是一種運算受限制的線性表，元素的添加在表的一端進行，而元素的刪除在表的另一端進行。允許插入的一端稱為隊尾，允許刪除的一端成為隊 頭；
6．向隊列添加元素稱為進隊，從隊列中刪除元素稱為出隊；隊列的特點是先進入隊列的元素先出隊，所以隊列也稱作先進先出表或FIFO表。
7．和線性表類似，隊列也有兩種存儲表示：順序隊列和鏈隊列；和順序棧相類似，隊列也可以簡單的用一維數組表示，而頭指針始終指向隊列頭元素，尾指針始終指向隊列尾元素的下一個位置。
8.隨著元素的不斷插入、刪除兩端向后移動，隊列很快移動到數組末端造成溢出而前面的單元格無法使用，這種現象叫做假溢出。解決這個問題的兩種方法：1.每次刪除一個元素后將整個隊列向前移動一個單元，保持隊列頭總固定在數組的第一個單元。若只是這樣，每次刪除元素時都要執行一次循環操作將隊列中所有元素向前移動一個單元，造成了系統的額外開銷。2.將順序隊列的存儲區域假想為是一個頭尾相連的圓環，當隊頭指示器達到數組的上限時，如果還有數據元素出隊，隊頭指示器指向數組的0端。這樣做，出隊結點空出的空間可被重新利用，除非整個數組單元真的全部被隊列結點占用，否則不會出現溢出，從而解決了假溢出的問題。雖然此時在物理上的隊尾在隊首之前，但邏輯上隊首仍在前，進隊和出隊仍按先進先出的原則進行，通常把這種特殊結構的隊列叫做循環隊列。
9.用鏈表表示的隊列稱為鏈隊列。一個鏈隊列需要兩個分別指示隊頭和隊尾的指針才能唯一確定。為了操作方便，在鏈隊列中添加一個頭結點，并令頭指針指向頭結點；
10.循環隊列的基本操作； 鏈隊列的基本操作；順序隊列的基本操作；順序棧的基本操作；棧的應用和隊列的應用；棧的基本運算
第四章：串、數組和廣義表
1.串：是由零個或多個字符組成的有限序列。記為：s=’a1a2a3…..an’
其中s為串名，用單引號括起來的字符序列是串的值；串中字符的數目n稱為串的長度由一個或多個空格組成的串，稱為空格串，它的長度是空格字符的個數。為了方便區分，
來表示空串。
2．串中任意一個連續的字符組成子序列稱為該串的子串，包含子串的串相應的稱為主串；子串在主串中的位置則以子串的第一個字符在主串中的位置來表示，稱為子串位置。當且僅當兩個串的長度相等并且各對應位置的字符都相等時才相等。
3．單引號本身不屬于串，串的數據對象約束為字符集，線性表則不限。
4．我們用一組地址連續的存儲單元存儲串值的字符序列；有三種方法表示串的長度：（1）用一個變量來表示串的長度；（2）在串尾存儲一個不會在串中出現的特殊字符作為串的終結符；（3）用數組的0號單元存放串的長度，串值從1號單元格開始存放；
5．和線性表的鏈式存儲結構類似，也可以用鏈表的方式存儲串值。此時將存儲區域分成一系列大小相同的結點，當討論僅限于單鏈表時，每個結點有兩個域：data域存放字符，next域存放指向下一個結點的指針；串的鏈式存儲會涉及結點的大小（是指結點的data域可存放字符的個數），由此將串的鏈式存儲分為2種：結點大小為1和結點大小為k。為1的特點：鏈表的存儲密度小，存儲效率較低但形式簡單，較易進行串的運算；為k的特點：鏈表的存儲密度大，存儲效率較高，但運算速度相比結點為1時要慢一些，串的插入運算不方便。
6.串的運算（模式匹配：在主串中尋找子串的過程稱為模式匹配。若匹配成功則返回子串在主串中首次出現的存儲位置（或序號），否則匹配失敗）。
7。多維數組：每個元素受到n個線性關系的約束，每個元素在線性關系的序號稱為該元素的下標，并稱該數組為n維數組。三維數組可以看作數組元素是二維數組的一維數組，一維數組可以看作一個線性表；
8．數組被定義其維數和維界不會變化，數組一邊只有兩種操作：存取和修改
9．數組的順序表示和實現；特殊矩陣（對稱，三角，稀疏）；
10．廣義表：是n個元素的優先序列，一邊記作LS=（a1,a2……an）其中，LS為廣義表的名稱，習慣上大寫字母表示廣義表的名稱，小寫字母表示原子。
11．稱第一個元素a1為LS廣義表的表頭（Head），稱其余元素組成的表為LS的表尾；n為廣義表的長度，即為廣義表最外層包含的元素個數。廣義表的深度定義為所含括弧的重數，注意：“原子”的深度定義為0，“空表”的深度為1。
以下幾個例子：B=(e),是指列表B只有一個原子e，B的長度和深度都為1，且表頭為Head(B)=e, 表尾為Tail(B)=()
E=（a,E）這是一個遞歸的表，其長度為2，深度為無窮值，E相當于一個無限的列表E=(a,(a,(a,))),表頭為a，表尾為E；
12．廣義表的特點：1、廣義表的元素有次序性，元素的位置不能隨意以調換；2、廣義表有長度，最外層包含的元素個數即為長度；3、廣義表有深度，所以如果表中元素是列表，要把列表用單元素表示出來，這樣再來計算廣義表的深度；4、廣義表是一種多層次的數據結構；5、廣義表中的元素可以共享，列表可以為其它列表所共享；6、廣義表中的元素可以遞歸，即廣義表中的列表可以是其本身的一個子表；7、任何一個非空廣義表LS均可分解為表頭和表尾兩部分；8、另外，任何一個非空表，表頭可能是原子，可能是列表，但表尾一定是列表；廣義表可以看成是線性表的推廣，線性表是廣義表的特例；
13．廣義表的存儲結構及實現
第五章：樹和二叉樹
1．樹是n個有限數據元素的集合，n=0時成這棵樹為空樹。
2．非空樹T中：（1）有一個特殊的數據元素稱為樹的根節點，根節點沒有前驅結點；
（2）若n〉1，除根節點外的其余數據被分成m個互不相交的集合T1，T2，…….Tm，其中每一個集合本身又是一顆樹，樹T1，T2，…….Tm稱為這個根節點的子樹；
3.樹的定義還可以表述為二元組的形式：T=（D，R）其中D為樹T中節點的集合，R為樹中節點關系的集合。當樹不為空時，D={Root}∪Df,其中Root為樹T的根節點，DF為樹T的根Root的子樹集合。DF可以如下表示：DF=D1∪D2∪D3…….Dn且Di∩Dj=空集；當樹T
中的結點個數大于1時，有：R={,i=1,2,3,…..m}其中Root為樹T的根節點，ri是樹T的根節點Root的子樹Ti的根節點；
4.樹的特點：樹的根節點沒有前驅結點，除根節點外的所有節點有且只有一個前驅結點；
樹中所有結點可以有零個或多個后繼結點；
5．樹的表示方法（4種）：
（1）．直觀表示法：倒著以分支樹的形式表示，特點是邏輯結構很直觀，是數據結構中最常用樹的描述方法；
（2）．嵌套集合表示法：將根節點是為一個大集合，其若干棵子樹構成這個大集合中若干個互不相干的子集，如此嵌套下去，即構成一棵樹的嵌套集合表示；
（3）．凹入表示法：主要用于樹的屏幕和打印輸出；
（4）．廣義表表示法：就是將根作為由子樹森林組成表的名字寫在表的左邊，這樣依次將樹表示出來
6．樹的術語（12個）：（1） 結點：表示樹中的元素，包括數據項及若干指向其子樹的分支；（2）結點的度：結點所擁有的子樹的個數：（3）葉結點：度為0的結點，也叫終端結點；（4）分枝結點：度不為0的結點，也叫非終端結點；一棵樹除葉結點外，其余為分枝結點；（5）孩子，雙親，兄弟：樹中一個結點的子樹的根結點稱為這個結點的孩子；這個結點稱為他孩子結點的雙親；具有同一個雙親的孩子結點互為兄弟；（6）路徑，路徑長度：如果一棵樹的一串結點n1,n2……nk有如下關系：結點ni是ni+1的父結點（1
數據結構試題(9)
數據結構試題3
一、單項選擇題（每小題3分，共30分）
1、假設有 n個關鍵字，它們具有相同的Hash 函數值，用線性探測法把這 n個關鍵字存入到Hash地址空間中要做（ ）次探測。
A、n2 B、n(n+1) C、n(n+1)/2 D、n(n-1)/2
2、若有一個棧的輸入序列是 1，2，3，…，n 輸出序列的第一個元素是 n，則第 i 個輸出元素是（ ）。
A、n-i B、n-i-1 C、n-i+1 D、不確定
3、在一棵度為3的樹中，度為 3的結點數為 2 個，度為2的結點數為 1個，度為1 的結點樹為2個，那么度為 0的結點數為（ ）。
A、4 B、5 C、6 D、7
4、在一個具有 n個結點的無向完全圖中，包含有（ ）條邊。
A、n(n-1)/2 B、n(n-1) C、n(n+1)/2 D、n2
5、已知一個有序表為（13，18，24，35，47，50，62，83，90，115，134），當二分檢索值為90的元素時，需（ ）次比較可檢索成功。
A、 1 B、2 C、3 D、4
6、在所有排序方法中，關鍵字的比較次數與記錄的初始排序無關的是（ ）。
A、Shell排序 B、冒泡排序 C、直接插入排序 D、直接選擇排序
7、已知 8 個元素（34，76，45，18，36，54，92，65），按照依次插入結點的方法生成一棵二叉排序樹，該樹的深度為（ ）。
A、4 B、5 C、6 D、7
8、設有一個10階的對稱矩陣 A，采用壓縮存儲方式以行序為主存儲，a00為第一個元素， 其存儲地址為0，每個元素占有 1個存儲地址空間，則a85的地址為 （ ）。
A、13 B、33 C、17 D、32
9、設關鍵字序列為：3，7，6，9，8，1，4，5，2。進行排序的最小交換次數為（ ）。
A、6 B、7 C、8 D、20
10、給定權的集合{15，3，14，2，6，9，16，17}，所構造出的哈夫曼樹的帶
權路徑長度為（ ）。
A、129 B、219 C、189 D、229
二、判斷題 （認為對的，在題后的括號內打“√”，錯的打“ⅹ”，每小題１分， 共１０分）
1、在單鏈表中任何兩個元素的存儲位置之間都有固定的聯系，因為可以從頭結點進行查找任何一個元素。 （ ）
2、若一個葉子結點是某子樹的中序遍歷序列的最后一個結點，則它必是該子樹的先序遍歷中的最后一個結點。 （ ）
3、用相鄰矩陣法存儲一個圖時，不在考慮壓縮存儲的情況下，所占用的存儲空間大小與圖中結點的個數有關，而與圖的邊數無關。 （ ）
4、哈希表的查找效率主要取決于哈希建表時所選取的哈希函數和處理沖突
的方法兩個方面。 （ ）
5、因為算法和程序沒有區別，所以在數據結構中二者是通用的。 （ ）
6、進棧操作 push(x,s)作用于鏈接棧時，無須判滿。 （ ）
7、穩定排序算法是最好的。 （ ）
8、二叉搜索樹的左、右子樹都是二叉搜索樹。 （ ）
9、先序遍歷一棵二叉搜索樹所得的結點訪問序列不可能是鍵值遞增序列。 （ ）
10、表中的每一個元素都有一個前驅和后繼元素。 （ ）
三、填空題（每小題2分，共20分）
1、在散列表(Hash)查找中，評判一個散列函數優劣的兩個主要條件是_______和________。
2、設根結點處在第一層，那么具有 n 個結點的完全二叉樹，其高度為_____。
3、快速排序方法的最壞時間復雜度為______，平均時間復雜度為___。
4、給定表（55，63，44，38，75，80，31，56），用篩選法建立初始堆，則初始堆表為_________。
5、設圖 G 的頂點數為 n，邊數為 e，各頂點的度數為 D(Vi)，則e=________。
6、將5個不同的數據進行排序，至少需要比較_____次，至多需要比較_______次。
7、二分折半查找的查找速度一般比順序查找的速度快，設有100個元素，用二分折半查找時，最大比較次數是____，最小比較次數是_____。
8、由 a，b，c3 個結點構成的二叉樹，共有_________種不同的結構。
9、在一棵高度為 h 的平衡二叉樹中，至少含有________個結點，最多含有 2 h -1 個結點。
10、在一個單鏈表中刪除*p 結點，應執行如下操作 ：
q=p→next;
p→data=p→next→data;
p→next=________;
free(q);
四、簡答題（每題10分，共60分）
1、在單鏈表、雙鏈表和單循環鏈表中，若僅知道指針p指向某結點，不知道頭指針，能否將結點p從相應的鏈表中刪去？若可以，其時間復雜度各為多少？
2、假設用于通訊的電文僅有 8 個字母組成，字母在電文中出現的頻率分別為：7， 19，2，6，32，3，21，10。試用這8個頻率值構造哈夫曼樹，并畫出該哈夫曼所對應的森林。
3、已知一個長度為12的表（Jan，Feb，Mar，Apr，May，June，July，Aug，Sep， Oct，Nov，Dec）：
（1）構造最價二叉排序樹；
(2)試求在等概率情況下對此二叉排序樹進行折半檢索時檢索成功的平均長度。
4、對于下圖，試給出：
（1）每個頂點的入度和出度； （2）鄰接矩陣；
（3）逆鄰接表； （4）強連通分量；
5、快速排序、插入排序、自然兩路歸并排序、堆排序，哪一種排序方法所需的輔助空間最大？請簡單說明。
6、分析以下程序段中語句x=x+y的執行次數。
x=0; y=0;
for(int i=1;i
數據結構試題(10)
一、單項選擇題(共40分，每題2分)
1. 樹形結構是數據元素之間存在一種（ D ）。
A.一對一關系 B.多對多關系
C.多對一關系 D.一對多關系
2. 設語句x++的時間是單位時間，則以下語句的時間復雜度為（ B ）。
for(i=1; i
