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