數(shù)據(jù)結(jié)構復習題

1、一、填空：一、填空：1順序存儲結(jié)構的特點是（順序存儲結(jié)構的特點是（），鏈接存儲結(jié)構的特點是（，鏈接存儲結(jié)構的特點是（）。【解答】用元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的【解答】用元素在存儲器中的相對位置來表示數(shù)據(jù)元素之間的邏輯關系，用指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏邏輯關系，用指示元素存儲地址的指針表示數(shù)據(jù)元素之間的邏輯關系。輯關系。2.2.算法在發(fā)生非法操作時可以作出處理的特性稱為（算法在發(fā)生非法操作時可以作出處理的特

2、性稱為（）。【解答】健壯性【解答】健壯性3.3.常見的算法時間復雜度用大Ｏ記號表示為：常數(shù)階常見的算法時間復雜度用大Ｏ記號表示為：常數(shù)階()、對數(shù)、對數(shù)階()、線性階、線性階()、平方階、平方階()和指數(shù)階和指數(shù)階()?！窘獯稹浚稀窘獯稹浚?1)，Ｏ，Ｏ(log2n)，Ｏ，Ｏ(n)，Ｏ，Ｏ(n2)，Ｏ，Ｏ(2n)4將下列函數(shù)按它們在將下列函數(shù)按它們在n時的無窮大階數(shù)，從小到大排列。時的無窮大階數(shù)，從小到大排列。nnn37n5nlogn2

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

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

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

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