計算機數(shù)據(jù)結(jié)構(gòu)習(xí)題1 附答案

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

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

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

4、試按圖論中圖的畫法慣例畫出其邏輯結(jié)構(gòu)圖。試按圖論中圖的畫法慣例畫出其邏輯結(jié)構(gòu)圖。解：解：1.31.3設(shè)有以下三個函數(shù)：設(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結(jié)點后插入結(jié)點后插入S結(jié)點的語句序列是結(jié)點的語句序列是____________________________________。b.b.在P結(jié)點前插入結(jié)點前插入S結(jié)點的語句序列是結(jié)點的語句序列是_______________________

6、_____________。c.c.在表首插入在表首插入S結(jié)點的語句序列是結(jié)點的語句序列是____________________________________。d.d.在表尾插入在表尾插入S結(jié)點的語句序列是結(jié)點的語句序列是____________________________________。(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設(shè)指針變量設(shè)指針變量p指向雙向鏈表中結(jié)點指向雙向鏈表中結(jié)點A，指針變量，指針變量q指向被插入結(jié)點指向被插入結(jié)點B，要求給出在結(jié)點，要求給出在結(jié)點A的后面插入的后面插入結(jié)點結(jié)點B的操作序列（設(shè)雙向鏈表中結(jié)點的兩個指針域分別為的操作序列（設(shè)雙向鏈表中結(jié)點的兩個指針域分別為llinkllink和rl