山西省專升本考試試題

1、山西省專升本考試試題數(shù)據(jù)結(jié)構(gòu)試題1(222)一、是非題(下列各題，你認為正確的，請在題干的括號內(nèi)打“√”，錯的打“”。每題1分，共15分）1、數(shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)之間的邏輯結(jié)構(gòu)，數(shù)據(jù)在計算機中的存儲方式和數(shù)據(jù)的運算三個方面...............()2、線性表中的每個結(jié)點最多只有一個前驅(qū)和一個后繼。......()3、從本質(zhì)上看，文件是一種非線性結(jié)構(gòu)。..................()4、線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲，也可以鏈

2、接存儲。非線性的數(shù)據(jù)結(jié)構(gòu)只能鏈接存儲。.......................()5、棧和隊列邏輯上都是線性表。..........................()6、單鏈表從任何一個結(jié)點出發(fā)，都能訪問到所有結(jié)點........()7、單鏈表形式的隊列，頭指針F指向隊列的第一個結(jié)點，尾指針R指向隊列的最后一個結(jié)點。.................................................()8、對某一確

3、定的可利用空間表，給定一串內(nèi)存請求，若采用最佳適配和首次適配這兩種方法之中的一種能滿足該串請求，則也一定能用另一種方法滿足該串請求。()9、多維數(shù)組是向量的推廣。..............................()10、設(shè)串S=a1a2...ai...aj...an則有d(ai)d(aj)。....()11、設(shè)串S的長度為n則S的子串個數(shù)為n(n1)2。...........()12、一般樹和二叉樹的結(jié)點數(shù)目都可以為0。..

4、..............()13、在拓樸排序序列中，任意兩個相繼結(jié)點Vi和Vj都存在從Vi到Vj的路徑。()14、網(wǎng)絡(luò)的最小代價生成樹是唯一的。.....................()15、磁帶是順序存取的外存儲設(shè)備。.......................()二、填空題(每空1分，共10分）1、在樹結(jié)構(gòu)里，有且僅有一個結(jié)點沒有前驅(qū)，稱為根。非根結(jié)點有且僅有一個()且存在一條從根到該結(jié)點的()。2、評價數(shù)據(jù)結(jié)構(gòu)的兩條基本

5、標準是：()和()。3、對于順序存儲的棧，因為棧的空間是有限的，在進行()運算時，可能發(fā)生棧的上溢，在進行()運算時，可能發(fā)生棧的下溢。4、對于單鏈表形式的隊列，其空隊列的F指針和R指針都等于()。5、若S1=‘linked￡stS2=ring則S1S2=()。6、設(shè)根結(jié)點的層數(shù)為0，定義樹的高度為樹中層數(shù)最大的結(jié)點的層數(shù)加1。則高度為k的二叉樹具有的結(jié)點數(shù)目，最少為()最多為()。三、單選題(在本題的每一小題的備選答案中，只有一個答案

6、是正確的，請把你認為正確答案的題號，填入題干的括號內(nèi)。多選不給分。每題3分，共9分)1、對于順序存儲的隊列，存儲空間大小為n，頭指針為F，尾指針為R。若在邏輯上看一個環(huán)，則隊列中元素的個數(shù)為......................()⑴.RF⑵.nRF⑶.(RF1)modn⑷.(nRF）modn2、n個記錄直接插入排序所需的記錄最小移動次數(shù)是.......()⑴.2(n1)⑵.2n⑶.(n3)(n2)2⑷.n223、現(xiàn)有一“遺傳”關(guān)

7、系：設(shè)x是y的父親，則x可以把它的屬性遺傳給y。表示該遺傳關(guān)系最適合的數(shù)據(jù)結(jié)構(gòu)為..............................⑴.向量⑵.樹⑶.圖⑷.二叉樹new(q)；q↑.info←x1⑷[插入〕若P=DL.rear則q↑.rlinknil；q↑.llinkP；、1、數(shù)據(jù)結(jié)構(gòu)概念包括數(shù)據(jù)之間的邏輯結(jié)構(gòu)，數(shù)據(jù)在計算機中的存儲方式和數(shù)據(jù)的運算三個方面...............(y)2、線性表中的每個結(jié)點最多只有一個前驅(qū)

8、和一個后繼。......(y)3、從本質(zhì)上看，文件是一種非線性結(jié)構(gòu)。..................(n)4、線性的數(shù)據(jù)結(jié)構(gòu)可以順序存儲，也可以鏈接存儲。非線性的數(shù)據(jù)結(jié)構(gòu)只能鏈接存儲。.......................(n)5、棧和隊列邏輯上都是線性表。..........................(y)6、單鏈表從任何一個結(jié)點出發(fā)，都能訪問到所有結(jié)點........(n)7、單鏈表形式的隊列，頭指針F指向隊列的第

9、一個結(jié)點，尾指針R指向隊列的最后一個結(jié)點。.................................................()8、對某一確定的可利用空間表，給定一串內(nèi)存請求，若采用最佳適配和首次適配這兩種方法之中的一種能滿足該串請求，則也一定能用另一種方法滿足該串請求。(n)9、多維數(shù)組是向量的推廣。..............................(y)10、設(shè)串S=a1a2...ai...aj...an則

10、有d(ai)d(aj)。....(n)11、設(shè)串S的長度為n則S的子串個數(shù)為n(n1)2。...........(n)12、一般樹和二叉樹的結(jié)點數(shù)目都可以為0。................(n)13、在拓樸排序序列中，任意兩個相繼結(jié)點Vi和Vj都存在從Vi到Vj的路徑。(n)14、網(wǎng)絡(luò)的最小代價生成樹是唯一的。.....................(n)15、磁帶是順序存取的外存儲設(shè)備。.....................

11、..(y)二、填空題(每空1分，共10分）1、在樹結(jié)構(gòu)里，有且僅有一個結(jié)點沒有前驅(qū)，稱為根。非根結(jié)點有且僅有一個(前驅(qū))且存在一條從根到該結(jié)點的(路徑)。2、評價數(shù)據(jù)結(jié)構(gòu)的兩條基本標準是：(存貯需要量)和(運算的時間效率)。3、對于順序存儲的棧，因為棧的空間是有限的，在進行(push)運算時，可能發(fā)生棧的上溢，在進行(pop)運算時，可能發(fā)生棧的下溢。4、對于單鏈表形式的隊列，其空隊列的F指針和R指針都等于(null)。5、若S1=‘l

12、inked￡st“S2=“ring“則S1S2=(linked￡string)。6、設(shè)根結(jié)點的層數(shù)為0，定義樹的高度為樹中層數(shù)最大的結(jié)點的層數(shù)加1。則高度為k的二叉樹具有的結(jié)點數(shù)目，最少為(k)最多為((2^k)1)。三、單選題(在本題的每一小題的備選答案中，只有一個答案是正確的，請把你認為正確答案的題號，填入題干的括號內(nèi)。多選不給分。每題3分，共9分)1、對于順序存儲的隊列，存儲空間大小為n，頭指針為F，尾指針為R。若在邏輯上看一個環(huán)

13、，則隊列中元素的個數(shù)為......................(d)⑴.RF⑵.nRF⑶.(RF1)modn⑷.(nRF）modn2、n個記錄直接插入排序所需的記錄最小移動次數(shù)是.......(a)⑴.2(n1)⑵.2n⑶.(n3)(n2)2⑷.n223、現(xiàn)有一“遺傳”關(guān)系：設(shè)x是y的父親，則x可以把它的屬性遺傳給y。表示該遺傳關(guān)系最適合的數(shù)據(jù)結(jié)構(gòu)為..............................b⑴.向量⑵.樹⑶.圖⑷