舊數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試卷一

1、數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題一數(shù)據(jù)結(jié)構(gòu)導(dǎo)論試題一（課程代碼：（課程代碼：2142）一、單項(xiàng)選擇題（本大題共一、單項(xiàng)選擇題（本大題共15小題，每小題小題，每小題2分，共分，共30分）分）在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。1算法指的是【A】A對(duì)特定問題求解步驟的一種描述。B計(jì)算

2、機(jī)程序C排序方法D數(shù)據(jù)處理2在數(shù)據(jù)結(jié)構(gòu)課程里決定選取何種存儲(chǔ)結(jié)構(gòu)時(shí)，一般不考慮【A】A各結(jié)點(diǎn)的值如何B結(jié)點(diǎn)個(gè)數(shù)的多少C對(duì)數(shù)據(jù)有哪些運(yùn)算D所用編程語言實(shí)現(xiàn)這種結(jié)構(gòu)是否方便3線性表采用鏈接存儲(chǔ)時(shí)，其地址【D】A必須是連續(xù)的B部分地址必須是連續(xù)的C一定是不連續(xù)的D連續(xù)與否均可以4設(shè)線性表有n個(gè)元素，在順序表上實(shí)現(xiàn)比在鏈表上實(shí)現(xiàn)效率高的算法是【A】A輸出第i(0≤i≤n—1)個(gè)元素值B交換第0個(gè)元素與第1個(gè)元素的值C順序輸出這n個(gè)元素的值D輸出

3、與給定值x相等的元素在線性表中的序號(hào)5在一個(gè)以head為頭指針的非空循環(huán)單鏈表中，尾結(jié)點(diǎn)指針p滿足【A】A.pnext==headB.pnext==NULLC.p==NULLD.p==head6若用一個(gè)大小為6的數(shù)組來實(shí)現(xiàn)循環(huán)隊(duì)列，且隊(duì)尾指針rear和隊(duì)頭指針front的值分別為0和3，當(dāng)從隊(duì)列中刪除一個(gè)元素，再加入兩個(gè)元素后，rear和front的值分別為多少【B】A.1和5B.2和4C.4和2D.5和17若一個(gè)棧的輸入序列是1，2，

4、3，…，n，輸出序列的第一個(gè)元素是n，則第i個(gè)輸出元素是【D】A不確定BniCni1Dni18對(duì)特殊矩陣采用壓縮存儲(chǔ)的目的主要是為了【D】A表達(dá)變得簡單B對(duì)矩陣元素的存取變得簡單C去掉矩陣中的多余元素D減少不必要的存儲(chǔ)空間9設(shè)二叉樹有n個(gè)結(jié)點(diǎn)，則其深度為【D】An一1BnCD不能確定10按照二叉樹的定義，具有3個(gè)結(jié)點(diǎn)的二叉樹有【C】素，與已經(jīng)排序序列中的元素作比較，將其放入已排序序列的正確位置上。15對(duì)n個(gè)元素進(jìn)行冒泡排序，在所有元素有

5、序的情況下比較的次數(shù)為n(n1)2。三、應(yīng)用題（本大題共三、應(yīng)用題（本大題共5小題，每小題小題，每小題5分，共分，共25分）分）1若頻繁地對(duì)一個(gè)線性表進(jìn)行插入和刪除操作，則該線性表宜采用何種存儲(chǔ)結(jié)構(gòu)，為什么鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。因?yàn)椴迦牒蛣h除操作需要從頭結(jié)點(diǎn)起查找被插入或刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，并修改這些結(jié)點(diǎn)的指針域，查找過程平均移動(dòng)指針域?yàn)楸黹L的一半；而采用順序結(jié)構(gòu)存儲(chǔ)線性表，插入和刪除操作需要平均移動(dòng)表中的一半元素。但移動(dòng)指針域操作比移動(dòng)元素操

6、作花費(fèi)的時(shí)間少得多。2設(shè)有編號(hào)為1，2，3，4，5，6的六輛列車，順序進(jìn)入一個(gè)棧式結(jié)構(gòu)的站臺(tái)，問：能否得到編號(hào)序列為435612不能和135426能的出站順序，并說明為什么不能得到或者如何得到。（進(jìn)棧操作用push表示出棧操作用pop表示）3對(duì)如下圖所示的一棵二叉樹，試寫出它的先根遍歷、中根遍歷和后根遍歷的結(jié)果序列。先根：ABDEGCF中根：DBGEACF后根：DGEBFCA4一棵二叉排序樹的結(jié)構(gòu)如下圖，結(jié)點(diǎn)的值為1～8，請(qǐng)?jiān)诟鹘Y(jié)點(diǎn)所在