數(shù)據(jù)結(jié)構(gòu)-線性表-習(xí)題

第二章線性表一、選擇題線性表是（）A．一個有限序列，可以為空 B．一個有限序列，不可以為空 C．一個無限序列，可以為空 D．一個無限序列，不可以為空一維數(shù)組與線性表的特征是（）。 A．前者長度固定，后者長度可變 B．兩者長度均固定 C．后者長度固定，前者長度可變 D．兩者長度均可變用單鏈表方式存儲的線性表，存儲每個結(jié)點需要兩個域，一個數(shù)據(jù)域，另一個是(). A．當前結(jié)點所在地址域 B．指針域 C．空指針域 D．空閑域用鏈表表示線性表的優(yōu)點是（）。 A．便于隨機存取 B．便于進行插入和刪除操作 C．占用的存儲空間較順序表少 D．元素的物理順序與邏輯順序相同在具有n個結(jié)點的單鏈表中，實現(xiàn)___的操作，其算法的時間復(fù)雜度都是O（n）。 A．遍歷鏈表和求鏈表的第i個結(jié)點 D．刪除地址為P的結(jié)點的后繼結(jié)點 B．在地址為P的結(jié)點之后插入一個結(jié)點C．刪除開始結(jié)點下面關(guān)于線性表的敘述中，錯誤的是（）。 A．線性表采用順序存儲必須占用一片連續(xù)的存儲單元 B．線性表采用順序存儲便于進行插入和刪除操作 C．線性表采用鏈式存儲不必占用一片連續(xù)的存儲單元 D．線性表采用鏈式存儲便于進行插入和刪除操作已知單鏈表的每個結(jié)點包括一個指針域next，它指向該結(jié)點的后繼結(jié)點?，F(xiàn)要將指針q指向的新結(jié)點插入到指針p指向的結(jié)點之后，下面的操作序列中正確的是（）。 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為三個結(jié)點；p,10,20代表地址，則如下的鏈表存儲結(jié)構(gòu)稱為（）。 A．鏈表 B．單鏈表 C．雙向循環(huán)鏈表 D．雙向鏈表單鏈表的存儲密度（）。 A．大于1 B．等于1 C．小于1 D．不能確定己知一個順序存儲的線性表，設(shè)每個結(jié)點需占m個存儲單元，若第一個結(jié)點的地址al，則第i個結(jié)點的地址為（）。 A.al+(i-1)*m B.al+i*m C.al-i*m D.al+(i+1)*m在n個結(jié)點的順序表中，算法的時間復(fù)雜度是O(l）的操作是（）。 A．訪問第i個結(jié)點（1≤i≤n）和求第i個結(jié)點的直接前驅(qū)（2≤i≤n) B．在第i個結(jié)點之后插入一個新結(jié)點（1≤i≤n-1） C．刪除第i個結(jié)點（1≤i≤n) D．將n個結(jié)點從小到大排序在線性表中（）只有一個直接前驅(qū)和一個直接后繼。 A．首元素 B．中間元素 C．尾元素 D．所有元素對具有n個結(jié)點的線性表進行查找運算，所需的算法時間復(fù)雜度為（）。 A.0(n2) B.0(nlog2n) C.O(log2n) D.O(n)線性表采用順序存儲的缺點是（）。 A．存儲密度降低 B．只能順序訪問 C．元素的邏輯順序與物理順序不一致 D．插入、刪除操作效率低以下鏈表結(jié)構(gòu)中，從當前結(jié)點出發(fā)能夠訪問到任一結(jié)點的是（）。 A．單向鏈表和雙向鏈表 B．雙向鏈表和循環(huán)鏈表 C．單向鏈表和循環(huán)鏈表 D．單向鏈表、雙向鏈表和循環(huán)鏈表線性表是具有n個（）的有限序列。 A．數(shù)據(jù)項 B．數(shù)據(jù)元素 C．表元素 D．字符若長度為n的線性表采用鏈式存儲結(jié)構(gòu)，訪問其第i個元素的算法時間復(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é)點的單鏈表L為空的條件是() A.L!＝NULL B.L＝＝NULL C.L->next＝＝NULL D.L->next＝＝L帶頭結(jié)點的單鏈表L為空的條件是() A.L!＝NULL B.L＝＝NULL C.L->next＝＝NULL D.L->next＝＝L兩個指針P和Q，分別指向單鏈表的兩個元素，P所指元素是Q所指元素前驅(qū)的條件是（）。 A.P->next＝＝Q->next B.P->next＝＝Q C.Q->next＝＝P D.P＝＝Q在長度為n的順序表中，若要刪除第i(1≤i≤n）個元素，則需要向前移動元素的次數(shù)為（）。 A.1 B.n一i C.n一i+1 D.n一i一l在長度為n的順序表中第i(1≤i≤n）個位置上插入一個元素時，為留出插入位置所需移動元素的次數(shù)為（）。 A.n-i B.i C.n–i+1 D.n-i-l假定己建立以下動態(tài)鏈表結(jié)構(gòu)，且指針Pl和P2已指向如圖所示的結(jié)點：則以下可以將P2所指結(jié)點從鏈表中刪除并釋放該結(jié)點的語句組是() 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é)點插入到鏈表尾部，構(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個不同鏈表的第一個結(jié)點，此函數(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的最后一個結(jié)點由指針返回 D．將鏈表hl拆分成兩個鏈表二、判斷題循環(huán)鏈表不是線性表.(×)線性表就是順序存儲的表。(×)線性表只能用順序存儲結(jié)構(gòu)實現(xiàn)。(×)鏈表中的頭結(jié)點僅起到標識的作用。(√)線性表的鏈式存儲結(jié)構(gòu)優(yōu)于順序存儲。(×)順序存儲的線性表可以實現(xiàn)隨機存取。(√)順序存儲方式只能用于存儲線性結(jié)構(gòu)。(√)鏈表的每個結(jié)點都恰好包含一個指針域。(×)所謂靜態(tài)鏈表就是一直不發(fā)生變化的鏈表。(×)鏈表中的結(jié)點可含多個指針域鏈表中的結(jié)點可含多個指針域,分別存放多個指針。集合與線性表的區(qū)別在于是否按關(guān)鍵字排序。(×)取線性表的第i個元素的時間同i的大小有關(guān).(×)順序存儲結(jié)構(gòu)的主要缺點是不利于插入或刪除操作。(√)線性表的特點是每個元素都有一個前驅(qū)和一個后繼。(×)對任何數(shù)據(jù)結(jié)構(gòu)鏈式存儲結(jié)構(gòu)一定優(yōu)于順序存儲結(jié)構(gòu)。(×)順序存儲方式的優(yōu)點是存儲密度大，插入、刪除效率高。(×)為了很方便的插入和刪除數(shù)據(jù)，可以使用雙向鏈表存放數(shù)據(jù)。(×)順序存儲方式的優(yōu)點是存儲密度大，且插入、刪除運算效率高。(×)順序存儲方式插入和刪除時效率太低，因此它不如鏈式存儲方式好。(×)線性表采用鏈表存儲時，結(jié)點和結(jié)點內(nèi)部的存儲空間可以是不連續(xù)的。(√)線性表鏈式存儲的特點是可以用一組任意的存儲單元存儲表中的數(shù)據(jù)元素。(√)在線性表的順序存儲結(jié)構(gòu)中，邏輯上相鄰的兩個元素在物理位置上并不一定相鄰。(×)在線性表的順序結(jié)構(gòu)中，插入和刪除元素時，移動元素的個數(shù)與該元素的位置有關(guān)。(×)在單鏈表中，要取得某個元素，只要知道該元素的指針即可，因此單鏈表是隨機存取的存儲結(jié)構(gòu)。(×)鏈表是采用鏈式存儲結(jié)構(gòu)的線性表,進行插入、刪除操作時，在鏈表中比在順序存儲結(jié)構(gòu)中效率高。(√)在單鏈表中，任何兩個元素的存儲位置之間都有固定的聯(lián)系，所以可以從頭結(jié)點開始查找任何一個元素。(√)線性表中的元素可以是各種各樣的，但同一線性表中的數(shù)據(jù)元素具有相同的特性，因此屬于同一數(shù)據(jù)對象。(√)三、填空題順序表中邏輯上相鄰的元素在物理位置上 相鄰。在鏈表中邏輯上相鄰的元素的物理位置 相鄰。帶頭結(jié)點的雙循環(huán)鏈表L為空表的條件是： 。在單鏈表p結(jié)點之后插入s結(jié)點的操作是： 。順序表相對于鏈表的優(yōu)點有 和 。在雙鏈表中要刪除已知結(jié)點*p，其時間復(fù)雜度為 。在順序表中訪問任意一個結(jié)點的時間復(fù)雜度均為 。鏈接存儲的特點是利用 來表示數(shù)據(jù)元素之間的邏輯關(guān)系。帶頭結(jié)點的雙循環(huán)鏈表L中只有一個元素結(jié)點的條件是： 在單鏈表L中，指針p所指結(jié)點有后繼結(jié)點的條件是： 在單鏈表中除首結(jié)點外，任意結(jié)點的存儲位置都由 結(jié)點中的指針指示。已知指針p指向單鏈表L中的某結(jié)點，則刪除其后繼結(jié)點的語句是： 在n個結(jié)點的單鏈表中要刪除已知結(jié)點*p，需要找到 .其時間復(fù)雜度為 。鏈表相對于順序表的優(yōu)點有 和 操作方便；缺點是存儲密度 。建立單鏈表的算法時間復(fù)雜度；建立有序單鏈表的算法時間復(fù)雜度。在單鏈表中設(shè)置頭結(jié)點的作用是 。對于雙向鏈表,在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共 個，單鏈表為 個。在一個長度為n的順序表中第i個元素（1<=i<=n）之前插入一個元素時，需向后移動 個元素。在循環(huán)鏈表中，可根據(jù)一個結(jié)點的地址訪問整個鏈表，而單鏈表中需知道 才能訪問整個鏈表。順序存儲結(jié)構(gòu)是通過 表示元素之間的關(guān)系的;鏈式存儲結(jié)構(gòu)是通過 表示元素之間的關(guān)系的。有一單鏈表結(jié)構(gòu)如下，若要刪除值為c的結(jié)點，應(yīng)做的操作是 在n個結(jié)點的順序表中插入一個結(jié)點，平均需要移動 個結(jié)點，具體的移動次數(shù)取決于 。在n個結(jié)點的順序表中刪除一個結(jié)點，平均需要移動 個結(jié)點，具體的移動次數(shù)取決于 。在雙向循環(huán)鏈表中,向p所指的結(jié)點之后插入指針f所指的結(jié)點，其操作是 、 、 、 。線性表L=（a1,a2,…,an）用數(shù)組表示，假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動元素的個數(shù)是 。循環(huán)單鏈表與非循環(huán)單鏈表的主要不同是，循環(huán)單鏈表尾結(jié)點的指針，而非循環(huán)單鏈表的尾結(jié)點指針。當線性表的元素總數(shù)基本穩(wěn)定，且很少進行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應(yīng)采用 存儲結(jié)構(gòu)。線性表L=(a1,a2，…，an）用數(shù)組存儲。假定刪除表中任一元素的概率相同，則刪除一個元素平均需要移動的元素個數(shù)是。在單鏈表中要在已知結(jié)點*p之前插入一個新結(jié)點，需找到 ，其時間復(fù)雜度為 ；而在雙鏈表中，完成同樣操作時其時間復(fù)雜度為 。對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點*p后插入一個新結(jié)點的時間復(fù)雜度為 ,在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為 。根據(jù)線性表的鏈式存儲結(jié)構(gòu)中每一個結(jié)點包含的指針個數(shù)，將線性鏈表分成 和 ；而又根據(jù)指針的連接方式，鏈表又可分成 和 。在雙向鏈表結(jié)構(gòu)中，若要求在p指針所指的結(jié)點之前插入指針為s所指的結(jié)點，則需執(zhí)行下列語句：s^.next:=p；s^.prior:= ；p^.prior:=s； :=s；設(shè)單鏈表的結(jié)點結(jié)構(gòu)為(data,next)，next為指針域，已知指針px指向單鏈表中data為x的結(jié)點，指針py指向data為y的新結(jié)點,若將結(jié)點y插入結(jié)點x之后，則需要執(zhí)行以下語句: ； ;設(shè)有結(jié)點定義如下，且已建立如下圖所示的帶有頭結(jié)點的單向鏈表：structnode{intdata;structnode*next;};函數(shù)sum的功能是：計算鏈表中各結(jié)點數(shù)據(jù)域之和，作為函數(shù)值返回。請?zhí)羁铡ntsum(structnode*head){ints=0;structnode*p;p=head->next;do{s=s＋；p=p->next;}while(p!＝)；returns;}己知head指向一個帶有頭結(jié)點的單向鏈表，鏈表中每個結(jié)點包含整型數(shù)據(jù)域（data)和指針域（next）。以下算法用來查找鏈表所有結(jié)點中數(shù)據(jù)域值最大的結(jié)點的位置，由指針s傳回調(diào)用程序。請?zhí)羁?。structlink{ 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（）