安陽工學院軟件工程專業(yè)2015-2016學年數(shù)據(jù)結構檢測題

1、安陽工學院軟件工程專業(yè)2015-2016學年數(shù)據(jù)結構檢測題1.樹型結構是數(shù)據(jù)元素之間存在一種： （） 單選題A、一對多關系(正確答案)B、多對多關系C、多對一關系D、一對一關系2.數(shù)據(jù)結構被形式化定義為( K,R)，其中K是數(shù)據(jù)元素的有限集合，R是K上的（）有限集合。 單選題A、 操作B、映像C、存儲D、關系(正確答案)3.數(shù)據(jù)在計算機存儲內(nèi)表示時，物理地址與邏輯地址不相同，稱之為（） 單選題A、 存儲結構B、邏輯結構C、鏈式存儲結構(正確答案)D、順序存儲結構4.數(shù)據(jù)結構中，與所使用的計算機無關的是數(shù)據(jù)（）的結構； 單選題A、 存儲B、物理C、邏輯(正確答案)D、物理和存儲5.計算機算法指的

2、是（） 單選題A、 計算方法B、調(diào)度方法C、解決問題的有窮指令序列(正確答案)D、處理問題的任何程序6.算法分析的目的是： ( ) 單選題A、 找出數(shù)據(jù)結構的合理性B、 研究算法中的輸入和輸出的關系C、分析算法的效率以求改進(正確答案)D、分析算法的易懂性和文檔性7.算法分析的兩個主要方面是： （） 單選題A、 空間復雜性和時間復雜性(正確答案)B、 正確性和簡明性C、 可讀性和文檔性D、數(shù)據(jù)復雜性和程序復雜性8.下面關于線性表的敘述錯誤的是（）。 單選題A、 線性表采用順序存儲必須占用一片連續(xù)的存儲空間B、 線性表采用鏈式存儲不必占用一片連續(xù)的存儲空間C、 線性表采用鏈式存儲便于插入和刪除操

3、作的實現(xiàn)D、 線性表采用順序存儲便于插入和刪除操作的實現(xiàn)(正確答案)9.數(shù)據(jù)在計算機內(nèi)有順序和鏈式存儲方式，在存儲空間使用的靈活性上，鏈式存儲比順序存儲要（） 單選題A、 低B、高(正確答案)C、相同D、不好說10.下面程序的時間復雜度為( )int i=1 1while(i=n) n+1i=i*2 log2n+？ 單選題O(n)O(logn)(正確答案)O(n)O(n)11.下面程序的時間復雜度為( )for（i=1，s=0； i=n； i+）t=1；for(j=1；jnext；p-data=r-data；p-next=r-next；free(r)；B、r=p-next；r-data=p-d

4、ata；p-next=r-next；free(r)；C、r=p-next；p-next=r-next；free(r)；(正確答案)D、r=p-next；p-data=r-data；free(r)；19.在一個單鏈表中，已知指針s指向待插入的其值為x的新結點A，若將結點A插入到單鏈表指針變量p之后，則需要修改的操作序列為() )。 單選題A、s=p-next；p-data=s-data；p-next=s-next；free(s)；B、s=p-next；s-data=p-data；p-next=r-next；C、s-data=x；s-next=p-next；p-next=s；(正確答案)D、p-n

5、ext=s；s-next=p-next； s-data=x;20.單鏈表中，增加一個頭結點的目的是為了（） 單選題A、 使單鏈表至少有一個結點B、標示表結點中首結點位置C、 方便運算實現(xiàn)(正確答案)D、 說明單鏈表是線性表的鏈式存儲21.數(shù)據(jù)的最小單位是（）。 單選題A、 數(shù)據(jù)項(正確答案)B、 數(shù)據(jù)類型C、 數(shù)據(jù)元素D、 數(shù)據(jù)變量22.設一條單鏈表的頭指針變量為head且有頭結點，則其判空條件是（）。 單選題A、 head= NULLB、 head-next= NULL(正確答案)C、 head-next=headD、 head!= NULL23.非空循環(huán)鏈表head的尾結點(由p指針所指)

6、滿足（）。 單選題A、p-next= NULLB、 p= NULLC、p-next=head(正確答案)D、 p=head24.設指針變量front表示鏈式隊列的隊頭指針，指針變量rear表示鏈式隊列的隊尾指針，指針變量s指向?qū)⒁腙犃械慕Y點X，則入隊列的操作序列為（）。 單選題A、 front-next=s；front=s；B、 s-next=rear；rear=s；C、 rear-next=s；rear=s；(正確答案)D、 s-next=front；front=s；25.設指針變量top指向當前順序棧的棧頂，則刪除棧頂元素的操作序列為（）。 單選題A、 top=top+1;B、 top=

7、top-1;(正確答案)C、 top-next=top;D、 top=top-next;26.棧中元素的進出原則是 （） 單選題A、先進先出B、后進先出(正確答案)C、棧空則進D、棧滿則出27.若已知一個棧的入棧序列是1，2，3，n，再依次輸出序列為p1，p2，p3，pn，而且中途沒有入棧元素。若p1=n，則pi為 （） 單選題A、IB、n=iC、n-i+1(正確答案)D、不確定28. 根據(jù)二叉樹定義，具有三個不同數(shù)據(jù)結點的不同的二叉樹有（）種。 單選題A、3B、5(正確答案)C、4D、61.數(shù)據(jù)元素是數(shù)據(jù)的基本單位，_是數(shù)據(jù)表示中最小的單位。 填空題_(答案：數(shù)據(jù)項)2.數(shù)據(jù)結構是一門研究非

8、數(shù)值計算的程序設計問題中計算機的_以及它們之間的_和運算等的學科。 填空題_(答案：操作對象 關系)3.數(shù)據(jù)結構被形式地定義為(D, R)，其中D是_的有限集合，R是D上的 _有限集合。 填空題_(答案：數(shù)據(jù)元素 關系)4.數(shù)據(jù)結構包括數(shù)據(jù)的_、數(shù)據(jù)的_ 和數(shù)據(jù)的_這三個方面的內(nèi)容。 填空題_(答案：邏輯結構 存儲結構 運算)5.在線性結構中，第一個節(jié)點_前趨節(jié)點，其余每個節(jié)點有且只有1個前趨節(jié)點。 填空題_(答案：無)6.數(shù)據(jù)結構按邏輯結構可分為兩大類，它們分別是_和 _。 填空題_(答案：線性結構 非線性結構)7.數(shù)據(jù)的存儲結構可以用4種基本的存儲方法表示，分別是_、_、_ 、_ 。 填空

9、題_(答案：順序 鏈式 索引 散列)8.順序存儲結構是把邏輯上相鄰的結點存儲在物理上_的存儲單元里，結點之間的邏輯關系由存儲單元位置的相鄰關系來體現(xiàn)。 填空題_(答案：連續(xù))9.鏈式存儲結構是把邏輯上相鄰的結點存儲在物理上 _的存儲單元里，結點之間的邏輯關系由附加的指針域來體現(xiàn)。 填空題_(答案：任意)10.向一個長度為n的順序表的第i個元素(1in+1)之前插入一個元素時，需向后移動_個元素。 填空題_(答案：n-i+1)11.在順序表中訪問任意一結點的時間復雜度均為_，因此，順序表也稱為隨機存取的數(shù)據(jù)結構。 填空題_(答案：O(1)12.數(shù)據(jù)的物理結構主要包括_和_兩種情況。 填空題_(答

10、案：順序存儲結構 鏈式存儲結構)13.棧的插入和刪除只能在棧的棧頂進行，后進棧的元素必定先出棧，所以又把棧稱為_表；隊列的插入和刪除運算分別在隊列的兩端進行，先進隊列的元素必定先出隊列，所以又把隊列稱為_表。 填空題_(答案：FILO FIFO)14.向量(順序表)、棧和隊列都是_結構，可以在向量的任何位置插入和刪除元素；對于棧只能在_ 插入和刪除元素；對于隊列只能在_插入和_刪除元素。 填空題_(答案：線性 棧頂 隊尾 隊首)15.在具有n個單元的循環(huán)隊列中，隊滿時共有_個元素。 填空題_(答案：n-1)16.深度為k的完全二叉樹至少有_個節(jié)點，至多有_個節(jié)點。若按自上而下、從左到右的次序給

11、節(jié)點編號(從1開始)，則編號最小的葉子節(jié)點的編號是_。 填空題_(答案：2k-1 2k-1 2k-1)17.在一棵二叉樹中，度為0的節(jié)點的個數(shù)為n0,度為2的節(jié)點個數(shù)為n2，則有n0=_ 填空題_(答案：n2+1)18.在一棵具有n個節(jié)點的完全二叉樹中，如果按照自上而下、從左到右的次序給節(jié)點編號(從1開始)，對于任意非根節(jié)點i(1in)，可以推斷出它的雙親節(jié)點是_，如果2in，則節(jié)點i無左孩子(節(jié)點i為葉子節(jié)點)，否則i的左孩子節(jié)點為_，如果2i+1n，則節(jié)點i無右孩子，否則i的右孩子節(jié)點為_。 填空題_(答案：i/2 2i 2i+1)1.鏈表的每個結點中都恰好包含一個指針。 判斷題對錯(正確

12、答案)2.鏈表的物理存儲結構具有同鏈表一樣的順序。 判斷題對錯(正確答案)3.鏈表的刪除算法很簡單，因為當刪除鏈中某個結點后，計算機會自動地將后續(xù)的各個單元向前移動。 判斷題對錯(正確答案)4.線性表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。 判斷題對錯(正確答案)5.順序表結構適宜于進行順序存取，而鏈表適宜于進行隨機存取。 判斷題對錯(正確答案)6.順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。 判斷題對錯(正確答案)7.線性表在物理存儲空間中也一定是連續(xù)的。 判斷題對錯(正確答案)8.線性表在順序存儲時，邏輯上相鄰的元素未必在存儲的物理位置次序上相鄰。 判

13、斷題對錯(正確答案)9.線性表的每個結點只能是一個簡單類型，而鏈表的每個結點可以是一個復雜類型。 判斷題對錯(正確答案)10.入棧操作和入隊列操作在鏈式存儲結構上實現(xiàn)時不需要考慮棧溢出的情況。 判斷題對(正確答案)錯11.順序表查找指的是在順序存儲結構上進行查找。 判斷題對錯(正確答案)12.在表結構中最常用的是線性表，棧和隊列不太常用。 判斷題對錯(正確答案)13.棧是一種對所有插入、刪除操作限于在表的一端進行的線性表，是一種后進先出型結構。 判斷題對(正確答案)錯14.棧和鏈表是兩種不同的數(shù)據(jù)結構。 判斷題對錯(正確答案)15.棧和隊列是一種非線性數(shù)據(jù)結構。 判斷題對錯(正確答案)16.對于不同的使用者，一個表結構既可以是棧，也可以是隊列， 判斷題對(正確答案)錯