



下載本文檔
版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡介
第二章線性表一、選擇題線性表是()A.一個(gè)有限序列,可以為空 B.一個(gè)有限序列,不可以為空 C.一個(gè)無限序列,可以為空 D.一個(gè)無限序列,不可以為空一維數(shù)組與線性表的特征是()。 A.前者長度固定,后者長度可變 B.兩者長度均固定 C.后者長度固定,前者長度可變 D.兩者長度均可變用單鏈表方式存儲(chǔ)的線性表,存儲(chǔ)每個(gè)結(jié)點(diǎn)需要兩個(gè)域,一個(gè)數(shù)據(jù)域,另一個(gè)是(). A.當(dāng)前結(jié)點(diǎn)所在地址域 B.指針域 C.空指針域 D.空閑域用鏈表表示線性表的優(yōu)點(diǎn)是()。 A.便于隨機(jī)存取 B.便于進(jìn)行插入和刪除操作 C.占用的存儲(chǔ)空間較順序表少 D.元素的物理順序與邏輯順序相同在具有n個(gè)結(jié)點(diǎn)的單鏈表中,實(shí)現(xiàn)___的操作,其算法的時(shí)間復(fù)雜度都是O(n)。 A.遍歷鏈表和求鏈表的第i個(gè)結(jié)點(diǎn) D.刪除地址為P的結(jié)點(diǎn)的后繼結(jié)點(diǎn) B.在地址為P的結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)C.刪除開始結(jié)點(diǎn)下面關(guān)于線性表的敘述中,錯(cuò)誤的是()。 A.線性表采用順序存儲(chǔ)必須占用一片連續(xù)的存儲(chǔ)單元 B.線性表采用順序存儲(chǔ)便于進(jìn)行插入和刪除操作 C.線性表采用鏈?zhǔn)酱鎯?chǔ)不必占用一片連續(xù)的存儲(chǔ)單元 D.線性表采用鏈?zhǔn)酱鎯?chǔ)便于進(jìn)行插入和刪除操作已知單鏈表的每個(gè)結(jié)點(diǎn)包括一個(gè)指針域next,它指向該結(jié)點(diǎn)的后繼結(jié)點(diǎn)。現(xiàn)要將指針q指向的新結(jié)點(diǎn)插入到指針p指向的結(jié)點(diǎn)之后,下面的操作序列中正確的是()。 A.q=p->next; p->next=q->next; B.p->next=q->next; q=p->next; C.q->next=p->next; p->next=q; D.p->next=q; q->next=p->next;設(shè)al,a2,a3為三個(gè)結(jié)點(diǎn);p,10,20代表地址,則如下的鏈表存儲(chǔ)結(jié)構(gòu)稱為()。 A.鏈表 B.單鏈表 C.雙向循環(huán)鏈表 D.雙向鏈表單鏈表的存儲(chǔ)密度()。 A.大于1 B.等于1 C.小于1 D.不能確定己知一個(gè)順序存儲(chǔ)的線性表,設(shè)每個(gè)結(jié)點(diǎn)需占m個(gè)存儲(chǔ)單元,若第一個(gè)結(jié)點(diǎn)的地址al,則第i個(gè)結(jié)點(diǎn)的地址為()。 A.al+(i-1)*m B.al+i*m C.al-i*m D.al+(i+1)*m在n個(gè)結(jié)點(diǎn)的順序表中,算法的時(shí)間復(fù)雜度是O(l)的操作是()。 A.訪問第i個(gè)結(jié)點(diǎn)(1≤i≤n)和求第i個(gè)結(jié)點(diǎn)的直接前驅(qū)(2≤i≤n) B.在第i個(gè)結(jié)點(diǎn)之后插入一個(gè)新結(jié)點(diǎn)(1≤i≤n-1) C.刪除第i個(gè)結(jié)點(diǎn)(1≤i≤n) D.將n個(gè)結(jié)點(diǎn)從小到大排序在線性表中()只有一個(gè)直接前驅(qū)和一個(gè)直接后繼。 A.首元素 B.中間元素 C.尾元素 D.所有元素對具有n個(gè)結(jié)點(diǎn)的線性表進(jìn)行查找運(yùn)算,所需的算法時(shí)間復(fù)雜度為()。 A.0(n2) B.0(nlog2n) C.O(log2n) D.O(n)線性表采用順序存儲(chǔ)的缺點(diǎn)是()。 A.存儲(chǔ)密度降低 B.只能順序訪問 C.元素的邏輯順序與物理順序不一致 D.插入、刪除操作效率低以下鏈表結(jié)構(gòu)中,從當(dāng)前結(jié)點(diǎn)出發(fā)能夠訪問到任一結(jié)點(diǎn)的是()。 A.單向鏈表和雙向鏈表 B.雙向鏈表和循環(huán)鏈表 C.單向鏈表和循環(huán)鏈表 D.單向鏈表、雙向鏈表和循環(huán)鏈表線性表是具有n個(gè)()的有限序列。 A.?dāng)?shù)據(jù)項(xiàng) B.?dāng)?shù)據(jù)元素 C.表元素 D.字符若長度為n的線性表采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu),訪問其第i個(gè)元素的算法時(shí)間復(fù)雜度為()。 A.0(l) B.0(n) C.0(n2) D.0(log2n)指針P指向循環(huán)鏈表L的首元素的條件是()。 A.P==L B.L->next==P C.P->next==NULL D.P->next==L指針P所指的元素是雙循環(huán)鏈表L的尾元素的條件是()。 A.P==L B.P->prior==L C.P==NULL D.P->next==L不帶頭結(jié)點(diǎn)的單鏈表L為空的條件是() A.L!=NULL B.L==NULL C.L->next==NULL D.L->next==L帶頭結(jié)點(diǎn)的單鏈表L為空的條件是() A.L!=NULL B.L==NULL C.L->next==NULL D.L->next==L兩個(gè)指針P和Q,分別指向單鏈表的兩個(gè)元素,P所指元素是Q所指元素前驅(qū)的條件是()。 A.P->next==Q->next B.P->next==Q C.Q->next==P D.P==Q在長度為n的順序表中,若要?jiǎng)h除第i(1≤i≤n)個(gè)元素,則需要向前移動(dòng)元素的次數(shù)為()。 A.1 B.n一i C.n一i+1 D.n一i一l在長度為n的順序表中第i(1≤i≤n)個(gè)位置上插入一個(gè)元素時(shí),為留出插入位置所需移動(dòng)元素的次數(shù)為()。 A.n-i B.i C.n–i+1 D.n-i-l假定己建立以下動(dòng)態(tài)鏈表結(jié)構(gòu),且指針Pl和P2已指向如圖所示的結(jié)點(diǎn):則以下可以將P2所指結(jié)點(diǎn)從鏈表中刪除并釋放該結(jié)點(diǎn)的語句組是() A.pl->next=p2->next;free(pl); B.pl=p2;free(p2); C.pl->next=p2->next;free(p2); D.pl=p2->next;free(p2);若已建立如圖所示的單向鏈表,則以下不能將s所指的結(jié)點(diǎn)插入到鏈表尾部,構(gòu)成新的單向鏈表的語句組是()。 A.s->next=a->next->next;a->next->next=s; B.a=a->next;a->next=s;s->next=NULL; C.s->next=NULL;a=a->next;a->next=s; D.a=a->next;s->next=a->next;a->next=s->next;有如下函數(shù),其中形參hl和h2分別指向2個(gè)不同鏈表的第一個(gè)結(jié)點(diǎn),此函數(shù)的功能是()。 Voidfun(structnode*hl,structnode*h2){ structnode*t; t=hl; while(t->next!='\0') t=t->next;t->next=h2; } A.將鏈表h2接到鏈表h1后 B.將鏈表h1接到鏈表h2后 C.找到鏈表hl的最后一個(gè)結(jié)點(diǎn)由指針返回 D.將鏈表hl拆分成兩個(gè)鏈表二、判斷題循環(huán)鏈表不是線性表.(×)線性表就是順序存儲(chǔ)的表。(×)線性表只能用順序存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)。(×)鏈表中的頭結(jié)點(diǎn)僅起到標(biāo)識(shí)的作用。(√)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)優(yōu)于順序存儲(chǔ)。(×)順序存儲(chǔ)的線性表可以實(shí)現(xiàn)隨機(jī)存取。(√)順序存儲(chǔ)方式只能用于存儲(chǔ)線性結(jié)構(gòu)。(√)鏈表的每個(gè)結(jié)點(diǎn)都恰好包含一個(gè)指針域。(×)所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。(×)鏈表中的結(jié)點(diǎn)可含多個(gè)指針域鏈表中的結(jié)點(diǎn)可含多個(gè)指針域,分別存放多個(gè)指針。集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。(×)取線性表的第i個(gè)元素的時(shí)間同i的大小有關(guān).(×)順序存儲(chǔ)結(jié)構(gòu)的主要缺點(diǎn)是不利于插入或刪除操作。(√)線性表的特點(diǎn)是每個(gè)元素都有一個(gè)前驅(qū)和一個(gè)后繼。(×)對任何數(shù)據(jù)結(jié)構(gòu)鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)一定優(yōu)于順序存儲(chǔ)結(jié)構(gòu)。(×)順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大,插入、刪除效率高。(×)為了很方便的插入和刪除數(shù)據(jù),可以使用雙向鏈表存放數(shù)據(jù)。(×)順序存儲(chǔ)方式的優(yōu)點(diǎn)是存儲(chǔ)密度大,且插入、刪除運(yùn)算效率高。(×)順序存儲(chǔ)方式插入和刪除時(shí)效率太低,因此它不如鏈?zhǔn)酱鎯?chǔ)方式好。(×)線性表采用鏈表存儲(chǔ)時(shí),結(jié)點(diǎn)和結(jié)點(diǎn)內(nèi)部的存儲(chǔ)空間可以是不連續(xù)的。(√)線性表鏈?zhǔn)酱鎯?chǔ)的特點(diǎn)是可以用一組任意的存儲(chǔ)單元存儲(chǔ)表中的數(shù)據(jù)元素。(√)在線性表的順序存儲(chǔ)結(jié)構(gòu)中,邏輯上相鄰的兩個(gè)元素在物理位置上并不一定相鄰。(×)在線性表的順序結(jié)構(gòu)中,插入和刪除元素時(shí),移動(dòng)元素的個(gè)數(shù)與該元素的位置有關(guān)。(×)在單鏈表中,要取得某個(gè)元素,只要知道該元素的指針即可,因此單鏈表是隨機(jī)存取的存儲(chǔ)結(jié)構(gòu)。(×)鏈表是采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的線性表,進(jìn)行插入、刪除操作時(shí),在鏈表中比在順序存儲(chǔ)結(jié)構(gòu)中效率高。(√)在單鏈表中,任何兩個(gè)元素的存儲(chǔ)位置之間都有固定的聯(lián)系,所以可以從頭結(jié)點(diǎn)開始查找任何一個(gè)元素。(√)線性表中的元素可以是各種各樣的,但同一線性表中的數(shù)據(jù)元素具有相同的特性,因此屬于同一數(shù)據(jù)對象。(√)三、填空題順序表中邏輯上相鄰的元素在物理位置上 相鄰。在鏈表中邏輯上相鄰的元素的物理位置 相鄰。帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L為空表的條件是: 。在單鏈表p結(jié)點(diǎn)之后插入s結(jié)點(diǎn)的操作是: 。順序表相對于鏈表的優(yōu)點(diǎn)有 和 。在雙鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p,其時(shí)間復(fù)雜度為 。在順序表中訪問任意一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度均為 。鏈接存儲(chǔ)的特點(diǎn)是利用 來表示數(shù)據(jù)元素之間的邏輯關(guān)系。帶頭結(jié)點(diǎn)的雙循環(huán)鏈表L中只有一個(gè)元素結(jié)點(diǎn)的條件是: 在單鏈表L中,指針p所指結(jié)點(diǎn)有后繼結(jié)點(diǎn)的條件是: 在單鏈表中除首結(jié)點(diǎn)外,任意結(jié)點(diǎn)的存儲(chǔ)位置都由 結(jié)點(diǎn)中的指針指示。已知指針p指向單鏈表L中的某結(jié)點(diǎn),則刪除其后繼結(jié)點(diǎn)的語句是: 在n個(gè)結(jié)點(diǎn)的單鏈表中要?jiǎng)h除已知結(jié)點(diǎn)*p,需要找到 .其時(shí)間復(fù)雜度為 。鏈表相對于順序表的優(yōu)點(diǎn)有 和 操作方便;缺點(diǎn)是存儲(chǔ)密度 。建立單鏈表的算法時(shí)間復(fù)雜度;建立有序單鏈表的算法時(shí)間復(fù)雜度。在單鏈表中設(shè)置頭結(jié)點(diǎn)的作用是 。對于雙向鏈表,在兩個(gè)結(jié)點(diǎn)之間插入一個(gè)新結(jié)點(diǎn)需修改的指針共 個(gè),單鏈表為 個(gè)。在一個(gè)長度為n的順序表中第i個(gè)元素(1<=i<=n)之前插入一個(gè)元素時(shí),需向后移動(dòng) 個(gè)元素。在循環(huán)鏈表中,可根據(jù)一個(gè)結(jié)點(diǎn)的地址訪問整個(gè)鏈表,而單鏈表中需知道 才能訪問整個(gè)鏈表。順序存儲(chǔ)結(jié)構(gòu)是通過 表示元素之間的關(guān)系的;鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)是通過 表示元素之間的關(guān)系的。有一單鏈表結(jié)構(gòu)如下,若要?jiǎng)h除值為c的結(jié)點(diǎn),應(yīng)做的操作是 在n個(gè)結(jié)點(diǎn)的順序表中插入一個(gè)結(jié)點(diǎn),平均需要移動(dòng) 個(gè)結(jié)點(diǎn),具體的移動(dòng)次數(shù)取決于 。在n個(gè)結(jié)點(diǎn)的順序表中刪除一個(gè)結(jié)點(diǎn),平均需要移動(dòng) 個(gè)結(jié)點(diǎn),具體的移動(dòng)次數(shù)取決于 。在雙向循環(huán)鏈表中,向p所指的結(jié)點(diǎn)之后插入指針f所指的結(jié)點(diǎn),其操作是 、 、 、 。線性表L=(a1,a2,…,an)用數(shù)組表示,假定刪除表中任一元素的概率相同,則刪除一個(gè)元素平均需要移動(dòng)元素的個(gè)數(shù)是 。循環(huán)單鏈表與非循環(huán)單鏈表的主要不同是,循環(huán)單鏈表尾結(jié)點(diǎn)的指針,而非循環(huán)單鏈表的尾結(jié)點(diǎn)指針。當(dāng)線性表的元素總數(shù)基本穩(wěn)定,且很少進(jìn)行插入和刪除操作,但要求以最快的速度存取線性表中的元素時(shí),應(yīng)采用 存儲(chǔ)結(jié)構(gòu)。線性表L=(a1,a2,…,an)用數(shù)組存儲(chǔ)。假定刪除表中任一元素的概率相同,則刪除一個(gè)元素平均需要移動(dòng)的元素個(gè)數(shù)是。在單鏈表中要在已知結(jié)點(diǎn)*p之前插入一個(gè)新結(jié)點(diǎn),需找到 ,其時(shí)間復(fù)雜度為 ;而在雙鏈表中,完成同樣操作時(shí)其時(shí)間復(fù)雜度為 。對于一個(gè)具有n個(gè)結(jié)點(diǎn)的單鏈表,在已知的結(jié)點(diǎn)*p后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為 ,在給定值為x的結(jié)點(diǎn)后插入一個(gè)新結(jié)點(diǎn)的時(shí)間復(fù)雜度為 。根據(jù)線性表的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)中每一個(gè)結(jié)點(diǎn)包含的指針個(gè)數(shù),將線性鏈表分成 和 ;而又根據(jù)指針的連接方式,鏈表又可分成 和 。在雙向鏈表結(jié)構(gòu)中,若要求在p指針?biāo)傅慕Y(jié)點(diǎn)之前插入指針為s所指的結(jié)點(diǎn),則需執(zhí)行下列語句:s^.next:=p;s^.prior:= ;p^.prior:=s; :=s;設(shè)單鏈表的結(jié)點(diǎn)結(jié)構(gòu)為(data,next),next為指針域,已知指針px指向單鏈表中data為x的結(jié)點(diǎn),指針py指向data為y的新結(jié)點(diǎn),若將結(jié)點(diǎn)y插入結(jié)點(diǎn)x之后,則需要執(zhí)行以下語句: ; ;設(shè)有結(jié)點(diǎn)定義如下,且已建立如下圖所示的帶有頭結(jié)點(diǎn)的單向鏈表:structnode{intdata;structnode*next;};函數(shù)sum的功能是:計(jì)算鏈表中各結(jié)點(diǎn)數(shù)據(jù)域之和,作為函數(shù)值返回。請?zhí)羁铡ntsum(structnode*head){ints=0;structnode*p;p=head->next;do{s=s+;p=p->next;}while(p!=);returns;}己知head指向一個(gè)帶有頭結(jié)點(diǎn)的單向鏈表,鏈表中每個(gè)結(jié)點(diǎn)包含整型數(shù)據(jù)域(data)和指針域(next)。以下算法用來查找鏈表所有結(jié)點(diǎn)中數(shù)據(jù)域值最大的結(jié)點(diǎn)的位置,由指針s傳回調(diào)用程序。請?zhí)羁铡tructlink{ chardata; structlink*next;};main(){ structlink*head,*q; findmax(head,&q); printf("max=%d\n",q->data);}findmax(structlink*head,structlink**s){ structlink*p; p=head->next; *s=p; while()
溫馨提示
- 1. 本站所有資源如無特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫網(wǎng)僅提供信息存儲(chǔ)空間,僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 個(gè)人安全防護(hù)技巧的試題及答案
- 確保通過的保安證考試試題及答案
- 2025保安證考試考情分析試題及答案
- 防盜知識(shí)與技能試題及答案
- 2025年保安證考試備忘清單試題及答案
- 2025年保安證考前必看試題及答案
- 廣東省5g通信基站建設(shè)工程項(xiàng)目一標(biāo)段
- 試題縱深研究的保安證試題及答案
- 2025年保安證考試圖解寶典試題及答案
- 江西信息應(yīng)用職業(yè)技術(shù)學(xué)院《品牌經(jīng)營與管理》2023-2024學(xué)年第二學(xué)期期末試卷
- 2025年初級社會(huì)工作者綜合能力全國考試題庫(含答案)
- 2024年全國國家版圖知識(shí)競賽題庫及答案(中小學(xué)組)
- 人教PEP版六年級下冊Unit 3 Where did you go 單元整體教學(xué)設(shè)計(jì)
- 人工挖孔樁專項(xiàng)施工方案(水鉆法)
- 教育部人文社科項(xiàng)目申請書范本-2-副本
- GA∕T 743-2016 閃光警告信號燈
- 珍愛生命預(yù)防溺水 安全教育主題班會(huì)PPT課件
- 呼吸內(nèi)科實(shí)習(xí)生出科考試試題卷與答案
- 完整版專家信息登記表
- 比例的應(yīng)用評課
- 5米以上深基礎(chǔ)專項(xiàng)施工方案
評論
0/150
提交評論