c數據結構考試試題及答案

一、單項選擇題（每題2分，共10題）1.在數據結構中，與所使用的計算機無關的是數據的（）結構。A.存儲B.物理C.邏輯D.物理和存儲答案：C2.線性表的順序存儲結構是一種（）的存儲結構。A.隨機存取B.順序存取C.索引存取D.散列存取答案：A3.棧和隊列的共同特點是（）。A.都是先進后出B.都是先進先出C.只允許在端點處插入和刪除元素D.沒有共同點答案：C4.設有一個10階的對稱矩陣A，采用壓縮存儲方式，以行序為主存儲，a11為第一元素，其存儲地址為1，每個元素占1個地址空間，則a85的地址為（）。A.33B.32C.13D.40答案：A5.若一棵二叉樹具有10個度為2的結點，5個度為1的結點，則度為0的結點個數是（）。A.9B.11C.15D.不能確定答案：B6.對于有n個頂點的有向圖，其邊數最多為（）。A.n-1B.n(n-1)C.n(n+1)/2D.n(n-1)/2答案：D7.下列排序算法中，（）算法可能會出現下面情況：初始數據有序時，花費的時間反而最多。A.堆排序B.冒泡排序C.快速排序D.歸并排序答案：C8.順序查找法適用于查找順序存儲或鏈式存儲的線性表，平均查找長度為（）。A.(n+1)/2B.n/2C.(n-1)/2D.n答案：A9.散列函數有一個共同的性質，即函數值應當以（）取其值域的每個值。A.最大概率B.最小概率C.同等概率D.平均概率答案：C10.以下數據結構中，（）是非線性數據結構。A.樹B.字符串C.隊列D.棧答案：A二、多項選擇題（每題2分，共10題）1.數據結構研究的內容包括（）。A.數據的邏輯結構B.數據的存儲結構C.數據的運算D.數據的排序答案：ABC2.線性表的鏈式存儲結構與順序存儲結構相比優點是（）。A.便于插入和刪除操作B.便于隨機存取C.所有的操作算法實現簡單D.便于利用零散的存儲器空間答案：AD3.下面關于串的的敘述中，正確的是（）。A.串是字符的有限序列B.空串是由空格構成的串C.模式匹配是串的一種重要運算D.串既可以采用順序存儲，也可以采用鏈式存儲答案：ACD4.二叉樹的遍歷方式有（）。A.先序遍歷B.中序遍歷C.后序遍歷D.層序遍歷答案：ABCD5.圖的存儲結構有（）。A.鄰接矩陣B.鄰接表C.十字鏈表D.鄰接多重表答案：ABCD6.下列排序算法中，穩定的排序算法是（）。A.冒泡排序B.歸并排序C.快速排序D.直接插入排序答案：ABD7.哈希表的沖突處理方法有（）。A.開放定址法B.再哈希法C.鏈地址法D.建立公共溢出區答案：ABCD8.以下關于線性表的說法正確的是（）。A.線性表中的元素可以是各種各樣的，但同一線性表中的元素必須具有相同特性B.線性表中的元素必須是同一類型的數據C.線性表中的元素是有序的D.線性表中的元素個數是有限的答案：ABCD9.棧的操作有（）。A.入棧B.出棧C.讀棧頂元素D.清空棧答案：ABC10.下列關于隊列的說法正確的是（）。A.隊列是一種操作受限的線性表B.隊列是先進先出的線性表C.隊列的插入操作在隊尾進行D.隊列的刪除操作在隊頭進行答案：ABCD三、判斷題（每題2分，共10題）1.數據的邏輯結構與數據元素本身的內容和形式無關。（）答案：正確2.順序存儲方式只能用于存儲線性結構。（）答案：錯誤3.棧是一種對進棧、出棧操作總次數做了限制的線性表。（）答案：錯誤4.完全二叉樹一定是滿二叉樹。（）答案：錯誤5.有向圖的鄰接矩陣一定是對稱矩陣。（）答案：錯誤6.快速排序是一種穩定的排序算法。（）答案：錯誤7.順序查找法適用于查找順序存儲的線性表，不適用于鏈式存儲的線性表。（）答案：錯誤8.哈希表的查找效率主要取決于哈希函數和處理沖突的方法。（）答案：正確9.二叉樹中每個結點最多有兩個子結點，所以二叉樹的度為2。（）答案：錯誤10.在一個單鏈表中，已知q所指結點是p所指結點的前驅結點，若在q和p之間插入s結點，則執行s->next=p;q->next=s;（）答案：錯誤四、簡答題（每題5分，共4題）1.簡述線性表的順序存儲結構和鏈式存儲結構的優缺點。答案：順序存儲結構優點：可隨機存取元素；存儲密度大。缺點：插入、刪除操作需移動大量元素；需預先分配足夠大的存儲空間。鏈式存儲結構優點：插入、刪除操作方便，不需要移動元素；不需要預先分配很大的存儲空間。缺點：不能隨機存取元素；存儲密度小。2.簡述二叉樹的性質。答案：二叉樹性質有：二叉樹第i層上最多有2^(i-1)個結點；深度為k的二叉樹最多有2^k-1個結點；在任意一棵二叉樹中，度為0的結點（葉子結點）總是比度為2的結點多1個等。3.簡述圖的深度優先遍歷和廣度優先遍歷的思想。答案：深度優先遍歷思想：從圖中某個頂點v出發，訪問v，然后選擇一個與v相鄰且未被訪問的頂點w進行深度優先遍歷，遞歸進行直到所有頂點被訪問。廣度優先遍歷思想：從圖中某個頂點v出發，訪問v，然后依次訪問v的所有鄰接頂點，再對這些鄰接頂點的鄰接頂點依次訪問，直到所有頂點被訪問。4.簡述散列函數的構造方法有哪些？答案：散列函數構造方法有直接定址法、數字分析法、平方取中法、折疊法、除留余數法等。五、討論題（每題5分，共4題）1.討論在數據結構中，如何優化順序表的插入操作？答案：可以采用以下方法優化。一是在順序表的末尾預留一定的空閑空間，減少元素移動次數。二是當需要插入元素時，先判斷順序表的空間是否足夠，若不足則進行擴容操作。2.討論二叉樹在實際應用中的作用。答案：二叉樹在編碼方面有哈夫曼樹用于數據壓縮；在搜索方面二叉排序樹可用于快速查找；在表達式求值等方面也有應用，它可以方便地表示表達式的語法結構。3.討論圖的連通性判斷有哪些應用？答案：在網絡通信中可判