計算機數(shù)據(jù)結構習題1 附答案

1、第1章緒論1.11.1簡述下列術語：數(shù)據(jù)，數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結構、存儲結構、數(shù)據(jù)類型和抽象數(shù)據(jù)類型。簡述下列術語：數(shù)據(jù)，數(shù)據(jù)元素、數(shù)據(jù)對象、數(shù)據(jù)結構、存儲結構、數(shù)據(jù)類型和抽象數(shù)據(jù)類型。解：數(shù)據(jù)解：數(shù)據(jù)是對客觀事物的符號表示。在計算機科學中是指所有能輸入到計算機中并被計算機程序處理的符號的總稱。數(shù)據(jù)元素數(shù)據(jù)元素是數(shù)據(jù)的基本單位，在計算機程序中通常作為一個整體進行考慮和處理。數(shù)據(jù)對象數(shù)據(jù)對象是性質相同的數(shù)據(jù)元素的集合，是數(shù)據(jù)的一個子集

2、。數(shù)據(jù)結構數(shù)據(jù)結構是相互之間存在一種或多種特定關系的數(shù)據(jù)元素的集合。存儲結構存儲結構是數(shù)據(jù)結構在計算機中的表示。數(shù)據(jù)類型數(shù)據(jù)類型是一個值的集合和定義在這個值集上的一組操作的總稱。抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型是指一個數(shù)學模型以及定義在該模型上的一組操作。是對一般數(shù)據(jù)類型的擴展。1.21.2填空題：填空題：1.常見的數(shù)據(jù)結構有_線性__結構，__樹形___結構，__圖形__結構等三種。2.常見的存儲結構有__順序存儲_______結構，__鏈式

3、存儲____結構等兩種。3.數(shù)據(jù)的基本單位是_數(shù)據(jù)元素___，它在計算機中是作為一個整體來處理的。4.數(shù)據(jù)結構中的結構是指數(shù)據(jù)間的邏輯關系，常見的結構可分為兩大類，__線性結構____和__非線性結構___。5.《數(shù)據(jù)結構》課程討論的主要內容是數(shù)據(jù)的邏輯結構、存儲結構和_____算法____。1.21.2設有數(shù)據(jù)結構設有數(shù)據(jù)結構(DR)(DR)，其中，其中，，??4321ddddD???rR?????????433221ddddddr?

4、試按圖論中圖的畫法慣例畫出其邏輯結構圖。試按圖論中圖的畫法慣例畫出其邏輯結構圖。解：解：1.31.3設有以下三個函數(shù)：設有以下三個函數(shù)：，，??10002124???nnnf??3450015nnng????nnnnhlog5005.3??請判斷以下斷言正確與否：請判斷以下斷言正確與否：(1)(1)f(n)f(n)是O(g(n))O(g(n))(2)(2)h(n)h(n)是O(f(n))O(f(n))(3)(3)g(n)g(n)是O(h

5、(n))O(h(n))(4)(4)h(n)h(n)是O(nO(n3.53.5)(5)(5)h(n)h(n)是O(nlogn)O(nlogn)解：解：(1)對(2)錯(3)錯(4)對(5)錯a.a.在P結點后插入結點后插入S結點的語句序列是結點的語句序列是____________________________________。b.b.在P結點前插入結點前插入S結點的語句序列是結點的語句序列是_______________________

6、_____________。c.c.在表首插入在表首插入S結點的語句序列是結點的語句序列是____________________________________。d.d.在表尾插入在表尾插入S結點的語句序列是結點的語句序列是____________________________________。(1)(1)Pnext=SPnext=S(2)(2)Pnext=PnextnextPnext=Pnextnext(3)(3)Pnext=Sn

7、extPnext=Snext(4)(4)Snext=PnextSnext=Pnext(5)(5)Snext=LSnext=L(6)(6)Snext=NULLSnext=NULL(7)(7)Q=PQ=P(8)(8)while(Pnext!=Q)while(Pnext!=Q)P=PnextP=Pnext(9)(9)while(Pnext!=NULL)while(Pnext!=NULL)P=PnextP=Pnext(10)(10)P=QP=Q

8、(11)(11)P=LP=L(12)(12)L=SL=S(13)(13)L=PL=P解：解：a.(4)(1)b.(7)(11)(8)(4)(1)c.(5)(12)d.(9)(1)(6)2.52.5在如下數(shù)組在如下數(shù)組A中鏈接存儲了一個線性表，表頭指針為中鏈接存儲了一個線性表，表頭指針為A[0].nextA[0].next，試寫出該線性表。，試寫出該線性表。其中數(shù)組其中數(shù)組A的定義如下：的定義如下：structnodeintdatastr

9、uctnodenextA[8]A01234567data605070903040next3572041解：解：7050406030902.62.6設指針變量設指針變量p指向雙向鏈表中結點指向雙向鏈表中結點A，指針變量，指針變量q指向被插入結點指向被插入結點B，要求給出在結點，要求給出在結點A的后面插入的后面插入結點結點B的操作序列（設雙向鏈表中結點的兩個指針域分別為的操作序列（設雙向鏈表中結點的兩個指針域分別為llinkllink和rl