數(shù)據(jù)結(jié)構(gòu)第2章典型例題解析(編輯修改稿)
2025-04-21 03:01 本頁面
【文章內(nèi)容簡介】 隨機存取的特點。【答案】正確3．鏈表中的頭結(jié)點僅起到標識的作用?！痉治觥款^結(jié)點是附加在第一個元素結(jié)點之前的一個結(jié)點，當該鏈表表示一個非空的線性表時，頭結(jié)點的指針域指向第一個元素結(jié)點，為空表時，該指針域為空。其作用是為了運算上的方便?！敬鸢浮垮e誤4．線性表采用鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。【分析】鏈表是通過一組任意的存儲單元來存儲線性表中的數(shù)據(jù)元素的，為建立起數(shù)據(jù)元素之間的線性關系，對每個數(shù)據(jù)元素，除了存放數(shù)據(jù)元素自身的信息之外，還需要存放其后繼元素所在的存儲單元的地址。鏈表中結(jié)點的存儲空間可以是不連續(xù)的，但結(jié)點內(nèi)部的存儲空間必須是連續(xù)的?！敬鸢浮垮e誤5．在單鏈表中和在順序表中插入一個元素其時間復雜度均為O(n)，因此說它們的執(zhí)行時間是相等的。【分析】大O記法表示時間漸近復雜度，是指一個算法中的時間耗費，往往是問題規(guī)模n的函數(shù)T(n)，當n趨向于無窮大時，T(n)的數(shù)量級稱為算法的時間漸近復雜度。雖然兩種存儲結(jié)構(gòu)下的插入操作時間復雜度均為O(n)，但由于兩者的基本操作不同，因此不能說它們的執(zhí)行時間是相等的。【答案】錯誤6．所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表?！痉治觥快o態(tài)鏈表是指以數(shù)組方式存儲鏈表的數(shù)據(jù)，數(shù)組的每個元素包含有數(shù)據(jù)域data和指針域next，其存儲的是該結(jié)點邏輯上的后繼結(jié)點的相對地址（即在數(shù)組中的下標）。其存儲空間不發(fā)生變化，而其內(nèi)容可以發(fā)生變化?！敬鸢浮垮e誤7．靜態(tài)鏈表與動態(tài)鏈表在元素的插入、刪除上類似，不需做元素的移動?！痉治觥快o態(tài)鏈表是指以數(shù)組方式存儲鏈表的數(shù)據(jù)，對鏈表進行插入和刪除運算時，只需改變指針，不需移動數(shù)據(jù)。【答案】正確8．靜態(tài)鏈表既有順序存儲的優(yōu)點，又有動態(tài)鏈表的優(yōu)點。所以，它存取表中第i個元素的時間與i無關。【分析】因為靜態(tài)鏈表的存取特性與動態(tài)鏈表是一樣的，只能順序地找到第i個元素，不能隨機地存取第i個元素，故其存取表中第i個元素的時間與i有關?！敬鸢浮垮e誤9．靜態(tài)鏈表中能容納的元素個數(shù)的最大數(shù)在表定義時就確定了，以后不能增加?！痉治觥恳驗殪o態(tài)鏈表是以數(shù)組方式存儲鏈表的數(shù)據(jù)，數(shù)組空間大小在數(shù)組定義時就已確定，一般不會發(fā)生變化?！敬鸢浮空_10．取線性表的第i個元素的時間同i的大小有關。【分析】存取線性表中數(shù)據(jù)元素的時間開銷與其存儲結(jié)構(gòu)有關。順序存儲結(jié)構(gòu)具有按序號隨機訪問的特點，同i的大小無關?！敬鸢浮垮e誤三、簡答題1．如圖211所示的雙向鏈表中，欲在結(jié)點p前插入一個結(jié)點s，請完成有關操作。圖211 第1題圖sprior=pprior。pprior=s。 snext=p?！窘獯稹恐荒苁恰皊priornext=s?！倍荒転椤皃priornext=s?！?。因為在上面的第二條語句中已經(jīng)改變了結(jié)點p的前驅(qū)結(jié)點，結(jié)點p的前驅(qū)結(jié)點已經(jīng)為s結(jié)點，而不是操作前的前驅(qū)結(jié)點。在下面的語句順序下，可有兩個答案進行選擇。sprior=pprior。 pprior=s。snext=p。讀者做這種題時，最好予以圖示，不易出錯。2．已知線性表非遞減有序，存儲于一個一維數(shù)組A[0..n1] 中（表長為n，設為全局量），下面算法的功能是什么？void del(DataType A[]){ int i,j。 i=1。 while (i=n1)if (A[i]!=A[i+1])i++。else{for (j=(i+2)。jn。j++)A[j1]=A[j]。n。}}【解答】由于一維數(shù)組中的元素按元素非遞減有序排列，值相同的元素必為相鄰的元素，因此依次比較相鄰兩個元素，若值相等，則刪除其中一個，否則繼續(xù)向后查找。故算法功能是刪除一維數(shù)組中多余的值相同的元素。3．下述算法的功能是什么？LinkList Demo(LinkList L){ // L是無頭結(jié)點的單鏈表 LNode *q,*p。 if (L amp。amp。 Lnext){ q=L。 L=Lnext。 p=L。
研究報告相關推薦
鄂ICP備17016276號-1