數(shù)據(jù)結(jié)構(gòu)c語言版期末試卷及答案一、選擇題（每題2分，共20分）1.在數(shù)據(jù)結(jié)構(gòu)中，線性表的順序存儲結(jié)構(gòu)相比于鏈?zhǔn)酱鎯Y(jié)構(gòu)的優(yōu)點(diǎn)是（）。A.存儲密度高B.存儲空間少C.插入和刪除操作快D.存儲空間連續(xù)2.棧的基本操作中，不包括（）。A.入棧B.出棧C.讀棧頂元素D.清空棧3.在二叉樹的遍歷中，先序遍歷的順序是（）。A.根-左-右B.左-根-右C.左-右-根D.右-左-根4.哈希表的構(gòu)造中，解決沖突的常用方法不包括（）。A.分離鏈接法B.線性探測法C.鏈地址法D.排序法5.以下哪個不是圖的遍歷算法（）。A.深度優(yōu)先搜索B.廣度優(yōu)先搜索C.迪杰斯特拉算法D.快速排序算法6.在排序算法中，時間復(fù)雜度為O(nlogn)的算法是（）。A.冒泡排序B.快速排序C.選擇排序D.插入排序7.以下哪個是最小生成樹算法（）。A.迪杰斯特拉算法B.弗洛伊德算法C.克魯斯卡爾算法D.以上都是8.以下哪個不是查找算法（）。A.順序查找B.二分查找C.哈希查找D.歸并排序9.以下哪個是外部排序的方法（）。A.插入排序B.快速排序C.歸并排序D.選擇排序10.在數(shù)據(jù)庫中，B樹和B+樹的主要區(qū)別是（）。A.B樹的節(jié)點(diǎn)可以存儲數(shù)據(jù)B.B+樹的非葉子節(jié)點(diǎn)不存儲數(shù)據(jù)C.B樹的葉子節(jié)點(diǎn)不存儲數(shù)據(jù)D.B+樹的葉子節(jié)點(diǎn)之間有指針連接二、填空題（每題2分，共20分）1.在數(shù)據(jù)結(jié)構(gòu)中，線性表的兩種存儲結(jié)構(gòu)分別是________和________。2.棧的特點(diǎn)是________，即后進(jìn)先出。3.在二叉樹中，如果一個節(jié)點(diǎn)的左子樹為空，則稱該節(jié)點(diǎn)為________。4.哈希表的構(gòu)造中，解決沖突的常用方法之一是________法。5.圖的遍歷算法中，________算法可以找到從源點(diǎn)到目標(biāo)點(diǎn)的最短路徑。6.排序算法中，時間復(fù)雜度為O(n)的算法是________排序。7.最小生成樹算法中，________算法適用于稠密圖。8.查找算法中，________查找的時間復(fù)雜度為O(logn)。9.外部排序的方法中，________排序適用于大數(shù)據(jù)量的排序。10.在數(shù)據(jù)庫中，B+樹相比于B樹的優(yōu)勢在于________。三、簡答題（每題10分，共30分）1.請簡述鏈表相比于順序表的優(yōu)點(diǎn)。2.請簡述二叉搜索樹的性質(zhì)。3.請簡述哈希表解決沖突的方法。四、編程題（每題15分，共30分）1.請編寫一個函數(shù)，實(shí)現(xiàn)對一個整數(shù)數(shù)組進(jìn)行快速排序。```cvoidquickSort(intarr[],intlow,inthigh){if(low<high){intpivot=partition(arr,low,high);quickSort(arr,low,pivot-1);quickSort(arr,pivot+1,high);}}intpartition(intarr[],intlow,inthigh){intpivot=arr[high];inti=(low-1);for(intj=low;j<=high-1;j++){if(arr[j]<pivot){i++;swap(&arr[i],&arr[j]);}}swap(&arr[i+1],&arr[high]);return(i+1);}voidswap(inta,intb){intt=a;a=b;b=t;}```2.請編寫一個函數(shù)，實(shí)現(xiàn)對一個字符串?dāng)?shù)組進(jìn)行排序。```cvoidsortStrings(chararr[],intn){for(inti=0;i<n-1;i++){for(intj=0;j<n-i-1;j++){if(strcmp(arr[j],arr[j+1])>0){chartemp=arr[j];arr[j]=arr[j+1];arr[j+1]=temp;}}}}```五、綜合題（每題20分，共20分）1.請?jiān)O(shè)計(jì)一個算法，實(shí)現(xiàn)對一個圖的深度優(yōu)先搜索（DFS）。```cvoidDFS(intv,boolvisited[],intgraph[],intV){visited[v]=true;cout<<v<<"";for(inti=0;i<V;i++){if(graph[v][i]&&!visited[i]){DFS(i,visited,graph,V);}}}voidaddEdge(intgraph[][5],intv,intw){graph[v][w]=1;graph[w][v]=1;}intmain(){intV=5;intgraph[5][5]={0};addEdge(graph,0,1);addEdge(graph,0,4);addEdge(graph,1,2);addEdge(graph,1,3);addEdge(graph,1,4);addEdge(grap