山西省專升本考試試題

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

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

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

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

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

6、是正確的，請(qǐng)把你認(rèn)為正確答案的題號(hào)，填入題干的括號(hào)內(nèi)。多選不給分。每題3分，共9分)1、對(duì)于順序存儲(chǔ)的隊(duì)列，存儲(chǔ)空間大小為n，頭指針為F，尾指針為R。若在邏輯上看一個(gè)環(huán)，則隊(duì)列中元素的個(gè)數(shù)為......................()⑴.RF⑵.nRF⑶.(RF1)modn⑷.(nRF）modn2、n個(gè)記錄直接插入排序所需的記錄最小移動(dòng)次數(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ù)在計(jì)算機(jī)中的存儲(chǔ)方式和數(shù)據(jù)的運(yùn)算三個(gè)方面...............(y)2、線性表中的每個(gè)結(jié)點(diǎn)最多只有一個(gè)前驅(qū)

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

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

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

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

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

13、，則隊(duì)列中元素的個(gè)數(shù)為......................(d)⑴.RF⑵.nRF⑶.(RF1)modn⑷.(nRF）modn2、n個(gè)記錄直接插入排序所需的記錄最小移動(dòng)次數(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⑴.向量⑵.樹⑶.圖⑷