數(shù)據(jù)結(jié)構(gòu)復(fù)習(xí)題

1、一、填空：一、填空：1順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是（順序存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是（），鏈接存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是（，鏈接存儲(chǔ)結(jié)構(gòu)的特點(diǎn)是（）?！窘獯稹坑迷卦诖鎯?chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的【解答】用元素在存儲(chǔ)器中的相對(duì)位置來(lái)表示數(shù)據(jù)元素之間的邏輯關(guān)系，用指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏邏輯關(guān)系，用指示元素存儲(chǔ)地址的指針表示數(shù)據(jù)元素之間的邏輯關(guān)系。輯關(guān)系。2.2.算法在發(fā)生非法操作時(shí)可以作出處理的特性稱為（算法在發(fā)生非法操作時(shí)可以作出處理的特

2、性稱為（）。【解答】健壯性【解答】健壯性3.3.常見(jiàn)的算法時(shí)間復(fù)雜度用大Ｏ記號(hào)表示為：常數(shù)階常見(jiàn)的算法時(shí)間復(fù)雜度用大Ｏ記號(hào)表示為：常數(shù)階()、對(duì)數(shù)、對(duì)數(shù)階()、線性階、線性階()、平方階、平方階()和指數(shù)階和指數(shù)階()。【解答】Ｏ【解答】Ｏ(1)，Ｏ，Ｏ(log2n)，Ｏ，Ｏ(n)，Ｏ，Ｏ(n2)，Ｏ，Ｏ(2n)4將下列函數(shù)按它們?cè)趯⑾铝泻瘮?shù)按它們?cè)趎時(shí)的無(wú)窮大階數(shù)，從小到大排列。時(shí)的無(wú)窮大階數(shù)，從小到大排列。nnn37n5nlogn2

3、n2n3log2nn12log2n(32)nn!n2log2n【解答】【解答】log2nn12log2nnnlog2nn2log2nn3nn37n52n2(32)nn!5在長(zhǎng)度為在長(zhǎng)度為n的線性表中查找值為的線性表中查找值為x的數(shù)據(jù)元素的時(shí)間復(fù)雜度的數(shù)據(jù)元素的時(shí)間復(fù)雜度為：為：（）。AO(0)BO(1)CO(n)DO(n2)【解答】【解答】C6在一個(gè)長(zhǎng)度為在一個(gè)長(zhǎng)度為n的順序表的第的順序表的第i（1≤i≤n1）個(gè)元素之前插）個(gè)元素之前插

4、入一個(gè)元素，需向后移動(dòng)（入一個(gè)元素，需向后移動(dòng)（）個(gè)元素，刪除第）個(gè)元素，刪除第i（1≤i≤n）個(gè)）個(gè)1212棧和隊(duì)列是兩種特殊的線性表，棧的操作特性是（棧和隊(duì)列是兩種特殊的線性表，棧的操作特性是（），隊(duì)列，隊(duì)列的操作特性是（的操作特性是（），棧和隊(duì)列的主要區(qū)別在于（，棧和隊(duì)列的主要區(qū)別在于（）?！窘獯稹亢筮M(jìn)先出，先進(jìn)先出，對(duì)插入和刪除操作限定的位置【解答】后進(jìn)先出，先進(jìn)先出，對(duì)插入和刪除操作限定的位置不同不同1313數(shù)組通常只有兩種運(yùn)

5、算：（數(shù)組通常只有兩種運(yùn)算：（）和（）和（），這決定了數(shù)組通常采，這決定了數(shù)組通常采用（用（）結(jié)構(gòu)來(lái)實(shí)現(xiàn)存儲(chǔ)。）結(jié)構(gòu)來(lái)實(shí)現(xiàn)存儲(chǔ)?！窘獯稹看嫒。薷?，順序存儲(chǔ)【解答】存取，修改，順序存儲(chǔ)【分析】數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)集合，在數(shù)組【分析】數(shù)組是一個(gè)具有固定格式和數(shù)量的數(shù)據(jù)集合，在數(shù)組上一般不能做插入、刪除元素的操作。除了初始化和銷毀之上一般不能做插入、刪除元素的操作。除了初始化和銷毀之外，在數(shù)組中通常只有存取和修改兩種操作。外，

6、在數(shù)組中通常只有存取和修改兩種操作。1414二維數(shù)組二維數(shù)組A中行下標(biāo)從中行下標(biāo)從10到20，列下標(biāo)從，列下標(biāo)從5到10，按行優(yōu)先，按行優(yōu)先存儲(chǔ)，每個(gè)元素占存儲(chǔ)，每個(gè)元素占4個(gè)存儲(chǔ)單元，個(gè)存儲(chǔ)單元，A[10][5]的存儲(chǔ)地址是的存儲(chǔ)地址是1000，則元素，則元素A[15][10]的存儲(chǔ)地址是（的存儲(chǔ)地址是（）?！窘獯稹俊窘獯稹?140【分析】數(shù)組【分析】數(shù)組A中每行共有中每行共有6個(gè)元素，元素個(gè)元素，元素A[15][10]的前面共的前面