第第頁學(xué)年度第學(xué)期期末考試《數(shù)據(jù)結(jié)構(gòu)與算法課程設(shè)計(jì)》（A）卷專業(yè)班級(jí)姓名學(xué)號(hào)單選題（每題的備選答案中只有一個(gè)最佳答案，每題2分，共60分）1.在數(shù)據(jù)結(jié)構(gòu)中,從邏輯上可以把數(shù)據(jù)結(jié)構(gòu)分成()。A、動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)C、線性結(jié)構(gòu)和非線性結(jié)構(gòu)D、內(nèi)部結(jié)構(gòu)和外部結(jié)構(gòu)2.在數(shù)據(jù)結(jié)構(gòu)中,從存儲(chǔ)結(jié)構(gòu)上可以將之分為()。A、動(dòng)態(tài)結(jié)構(gòu)和靜態(tài)結(jié)構(gòu)B、順序存儲(chǔ)和非順序存儲(chǔ)C、緊湊結(jié)構(gòu)和非緊湊結(jié)構(gòu)D、線性結(jié)構(gòu)和非線性結(jié)構(gòu)3.某算法的時(shí)間復(fù)雜度是O(n^2),表明該算法的()。A、執(zhí)行時(shí)間與n^2成正比B、問題規(guī)模是n^2C、執(zhí)行時(shí)間等于n^2D、問題規(guī)模與n^2成正比4.for(i=1；i<=n；i++)for(j=1；j<=n；j++)x=x+1；在這程序段中,x=x+1；的語句頻度為()。A、0(2n)B、O(n)C、O(n^2)D、O(log2n)5.以下數(shù)據(jù)結(jié)構(gòu)中，()是非線性數(shù)據(jù)結(jié)構(gòu)。A、樹B、字符串C、隊(duì)D、棧6.順序存儲(chǔ)，存儲(chǔ)單元的地址()。A、一定連續(xù)B、一定不連續(xù)C、不一定連續(xù)D、部分連續(xù)，部分不連續(xù)7.下列廣義表是線性表的是（）A、L＝（a，b，L）B、L＝（a，L）C、L＝（a，b，c）D、L＝（a，b，（a，b））8.二叉樹中第6層上的結(jié)點(diǎn)個(gè)數(shù)最多為（）A、32B、16C、12D、69.已知森林F=T1，T2A、2B、3C、8 D、1110.n個(gè)頂點(diǎn)的強(qiáng)連通圖至少有（）條邊。A、nB、n－1C、n＋1D、n（n－1）11.設(shè)無向圖的頂點(diǎn)個(gè)數(shù)為n,則該圖最多有（）條邊。A、n－1B、n（n－1）/2C、n（n＋1）/2D、n12.若表R在排序前已按鍵值遞增順序排序,則（）方法的比較次數(shù)最少。A、直接插入排序B、快速排序C、歸并排序D、直接選擇排序13.下列排序方法中最穩(wěn)定的是（）A、冒泡排序B、直接選擇排序C、希爾排序D、快速排序14.采用分塊查找時(shí),若線性表中共有625個(gè)元素,查找每個(gè)元素的概率相同，假設(shè)采用順序查找來確定結(jié)點(diǎn)所在的塊，則每塊分為（）個(gè)結(jié)點(diǎn)最佳。A、9B、25C、6D、62515.用線性探查法查找散列表，可能要探查多個(gè)散列地址。這些位置上的鍵值（）A、一定都不是同義詞B、一定都是同義詞C、不一定是同義詞D、都相同16.下面不屬于數(shù)據(jù)的存儲(chǔ)結(jié)構(gòu)的是（）A、散列存儲(chǔ)B、鏈?zhǔn)酱鎯?chǔ)C、索引存儲(chǔ)D、壓縮存儲(chǔ)17.下面對(duì)非空線性表的邏輯特征描述不正確的是（）A、只有一個(gè)元素沒有直接前趨B、只有一個(gè)元素沒有直接后繼C、除開始和終端元素外，任何一個(gè)元素都有且僅有一個(gè)直接前趨和一個(gè)直接后繼D、任何一個(gè)元素都有可能有多個(gè)直接前趨和多個(gè)直接后繼18.在頭指針為head且表長于1的單循環(huán)鏈表中，指針p指向表中某個(gè)結(jié)點(diǎn)，若p－＞next－＞next＝head，則（）A、p指向頭結(jié)點(diǎn)B、p指向尾結(jié)點(diǎn)C.*p的直接后繼是頭結(jié)點(diǎn)D.*p的直接后繼是尾結(jié)點(diǎn)19.棧的特點(diǎn)是（）A、先進(jìn)先出B、后進(jìn)后出C.后進(jìn)先出D、隨意進(jìn)出20.最不適合用作鏈隊(duì)的鏈表是（）A、只帶隊(duì)首指針的非循環(huán)雙向鏈表 B、只帶隊(duì)首指針的循環(huán)雙向鏈表C.只帶隊(duì)尾指針的循環(huán)雙向鏈表D、只帶隊(duì)尾指針的循環(huán)單向鏈表21.設(shè)數(shù)組A[m]為循環(huán)隊(duì)列Q的存儲(chǔ)空間，front為隊(duì)頭指針，rear為隊(duì)尾指針,采用少用一個(gè)無緊空間的方法來解決隊(duì)空和隊(duì)滿的判定問題，則判定Q為空隊(duì)列的條件是（）A、（rear－fron）％m＝＝1B、front＝＝rearC.（rear－front）％m＝＝m－1D.front＝＝（rear+1）％m22.下列選擇中，不屬于線性結(jié)構(gòu)的是（）A、線性表B、雙向鏈表C、循環(huán)隊(duì)列D、二叉樹23.某線性表L含有n個(gè)元素，采用單循環(huán)鏈表保持，僅有尾指針指向鏈表的終端結(jié)點(diǎn)。在最后一個(gè)結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)及刪除第一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度分別是（）A、O（1）和O（1）B、、O（1）和O（n）C、O（n）和O（1）D、O（n）和O（n）24.下列應(yīng)用中會(huì)用到棧的是（）A、計(jì)算后綴表達(dá)式的值B、圖的廣度優(yōu)先遍歷C、對(duì)數(shù)組進(jìn)行希爾排序D、對(duì)散列表進(jìn)行查找25.設(shè)棧初始為空，入棧序列為1，2，3，4，5，下列選項(xiàng)中，不可能得到的出棧序列是（）A、1，2，3，4，5B、3，1，4，2，5C、4，3，2，5，1D、5，4，3，2，126.已知廣義表LS＝（（（c，（d）），（e，（f））），（g，h），（（m，n））），head（LS）是（）A、cB、（c）C、（c，（d））D、（（c，（d）），（e，（f）））27.設(shè)線性表采用順序存儲(chǔ)方式保存，每個(gè)元素占8個(gè)存儲(chǔ)單元。第1個(gè)元素的存儲(chǔ)地址為200，則第5個(gè)元素占用的最后一個(gè)存儲(chǔ)單元的地址是（）A、239B、240C、247D、24828.一棵完全二叉樹T的全部K個(gè)葉子結(jié)點(diǎn)都在同一層中，每個(gè)分結(jié)點(diǎn)都有兩個(gè)孩子結(jié)點(diǎn)。T中包含的結(jié)點(diǎn)數(shù)是（）A、k B、2k?1C、k2D、29.設(shè)字符集中有n個(gè)字符，對(duì)其進(jìn)行哈夫曼編碼，得到的哈夫曼樹的結(jié)點(diǎn)總數(shù)是（）A、2n－1B、2nC、2n＋1D、不確定30.設(shè)圖G的鄰接矩陣A如下所示。G的各頂點(diǎn)的度依次是（）A=A、1，2，1，2B、2，2，1，1C、3，4，2，3D、4，4，2，2判斷題（對(duì)的選“A”，錯(cuò)的選“B”，每題2分，共40分）31.數(shù)據(jù)的運(yùn)算描述是定義在數(shù)據(jù)的邏輯結(jié)構(gòu)上的。（）32.數(shù)據(jù)運(yùn)算的實(shí)現(xiàn)是基于數(shù)據(jù)的邏輯結(jié)構(gòu)的。（）33.一個(gè)數(shù)據(jù)結(jié)構(gòu)中，如果數(shù)據(jù)元素值發(fā)生改變，則它的邏輯結(jié)構(gòu)也隨之改變。（）34.非線性結(jié)構(gòu)中，每個(gè)元素最多只有一個(gè)前趨元素。（）35.線性表中所有元素的數(shù)據(jù)類型必須相同。（）36.線性表中的結(jié)點(diǎn)按前趨、后繼關(guān)系可以排成一個(gè)線性序列。（）37.線性表中每個(gè)元素都有一個(gè)前趨元素和一個(gè)后繼元素。（）38.線性表的長度是線性表占用的存儲(chǔ)空間的大小。（）39.線性表的邏輯順序總與其物理順序一致。（）40.線性表的順序存儲(chǔ)結(jié)構(gòu)優(yōu)于鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。（）41.順序表具有隨機(jī)存取特性，而鏈表不具有隨機(jī)存取特性。（）42.棧的定義不涉及數(shù)據(jù)的邏輯結(jié)構(gòu)。（）43.棧和隊(duì)列都是線性表，只是在插入和刪除時(shí)受到了一些限制。（）44.棧和隊(duì)列都是限制存取端的線性表。（）45.隊(duì)列是一種對(duì)進(jìn)隊(duì)、出隊(duì)操作的次序做了限制的線性表。（）46.隊(duì)列是一種對(duì)進(jìn)隊(duì)、出隊(duì)操作的次數(shù)做了限制的線性表。（）47.n個(gè)元素進(jìn)隊(duì)的順序和出隊(duì)的順序總是一致的。（）48.n個(gè)元素通過一個(gè)隊(duì)列，其出隊(duì)序列是唯一的。（）49.串是由有限個(gè)字符構(gòu)成的序列。（）50.串中每個(gè)元素只能是字母。（）A卷答案(標(biāo)準(zhǔn)答案及評(píng)分標(biāo)準(zhǔn))單選題（每題