c 數(shù)據(jù)結(jié)構(gòu)考試試題及答案

c數(shù)據(jù)結(jié)構(gòu)考試試題及答案

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