數(shù)據(jù)結(jié)構(gòu)課件：1-5復(fù)習(xí)

一、選擇題

1.在數(shù)據(jù)結(jié)構(gòu)中，與所使用的計(jì)算機(jī)無關(guān)的數(shù)據(jù)叫___

結(jié)構(gòu)。

A.存儲B.物理C.邏輯D.物理和存儲2.在一個(gè)長度為n的順序表中，向第i個(gè)元素(1≤i≤n+1)之前插入一個(gè)新元素時(shí)，需向后移動

個(gè)元素。

A.n-1B.n-i+1C.n-i-1D.I3.線性表是

。A.一個(gè)有限序列,可以為空B一個(gè)有限序列,不能為空C.一個(gè)無限序列,可以為空D.一個(gè)無限序列,不能為空4.對順序存儲的線性表，設(shè)其長度為n，在任何位置上插入或刪除操作都是等概率的,刪除一個(gè)元素時(shí)大約要移動表中的

個(gè)元素。

A.n+1B.n-1C.(n-1)/2D.n5.線性表采用鏈?zhǔn)酱鎯r(shí)，其地址

_A.必須是連續(xù)的B.部分地址必須是連續(xù)的

C.一定是不連續(xù)的D.連續(xù)與否均可以

6.設(shè)單鏈表中指針p指著結(jié)點(diǎn)(數(shù)據(jù)域?yàn)閙)，指針f指著將要插入的新結(jié)點(diǎn)(數(shù)據(jù)域?yàn)閤)，當(dāng)x插在結(jié)點(diǎn)m之后時(shí)，只要先修改

后修改p->link=f即可。

A.f->link=p;B.f->link=p->link;C.p->link=f->link;D.f=nil;7.在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)時(shí)需修改指針

。

A.((p->rlink)->rlink)->link=p;p->rlink=(p->rlink)->rlink;B.(p->llink)->rlink=p->rlink;(p->rlink)->llink=p->llink;C.p->llink=(p->llink)->llink;((p->llink)->llink)->rlink=p;D.((p->llink)->llink)->rlink=p;p->llink=(p->llink)->llink;8.在雙向鏈表存儲結(jié)構(gòu)中，刪除p所指的結(jié)點(diǎn)的前趨結(jié)點(diǎn)（若存在）時(shí)需修改指針

。

A.((p->llink)->llink)->rlink=p;p->llink=(p->llink)->llink;B.((p->rlink)->rlink)->llink=p;p->rlink=(p->rlink)->rlink;C.(p->llink)->rlink=p->rlink;(p->rlink)->llink=p->llink;D.p->llink=(p->llink)->llink;((p->llink)->llink)->rlink=p;9.根據(jù)線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)，每個(gè)結(jié)點(diǎn)所含指針的個(gè)數(shù)，鏈表分為單鏈表和

。

A.循環(huán)鏈表B.雙向鏈表C.普通鏈表D.無頭結(jié)點(diǎn)鏈表10.從一個(gè)具有n個(gè)節(jié)點(diǎn)的單鏈表中查找其值等于x結(jié)點(diǎn)時(shí)，在查找成功的情況下，需平均比較

個(gè)結(jié)點(diǎn)。

A.nB.n/2C.(n-1)/2D.(n+1)/211.在一個(gè)單鏈表中，已知*q結(jié)點(diǎn)是*p結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，若在*q和*p之間插入*s結(jié)點(diǎn)，則執(zhí)行

。

A.s->next=p->next;p->next=s;B.p->next=s->next;s->next=p;C.q->next=s;s->next=p;D.p->next=s;s->next=q;12.在一個(gè)具有n個(gè)單元的順序棧中，假定以地址低端作為棧底，以top作為棧頂指針，則當(dāng)做退棧處理時(shí)，top變化為

。

A.top不變Ｂ.top＝-nC.top＝top-1D.top=top+113.向順序棧中壓入元素時(shí)，是

。

A.先存入元素，后移動棧頂指針

B.先移動棧頂指針，后存入元素

14.在一個(gè)順序存儲的循環(huán)隊(duì)列中，隊(duì)首指針指向隊(duì)首元素的

。

A.前一個(gè)位置B.后一個(gè)位置

C.隊(duì)首元素位置D.隊(duì)尾元素位置

15.若進(jìn)棧序列為1,2,3,4,進(jìn)棧過程中可以出棧，則

不可能是一個(gè)出棧序列。

A.3,4,2,1B.2,4,3,1C.1,4,2,3D.3,2,1,416.在具有n個(gè)單元的順序存儲的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)空的條件是

。

A.front==rear+1B.front+1==rearC.front==rearD.front==017.在具有n個(gè)單元的順序存儲的循環(huán)隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則判斷隊(duì)滿的條件是

。

A.rear%n==frontB.(rear-1)%n==front

C.(rear-1)%n==rearD.(rear+1)%n==front18.向一個(gè)棧頂指針為hs的鏈棧中插入一個(gè)*s結(jié)點(diǎn)時(shí)，則執(zhí)行

。

A.hs->next=s;B.s->next=hs->next;hs->next=s;C.s->next=hs；hs=s;D.s->next=hs;hs=hs->next;19.在一個(gè)鏈隊(duì)列中，假定front和rear分別為隊(duì)首指針和隊(duì)尾指針，則進(jìn)行插入*s結(jié)點(diǎn)的操作時(shí)應(yīng)執(zhí)行

。

A.front->next=s;front=s;B.rear->next=s;rear=s;C.front=front->next;D.front=rear->next;20設(shè)字符串s1='abcdefg',s2='pqrst'，則運(yùn)算

s=concat(sub(s1,2,len(s2)),sub(s1,len(s2),2))后串值為

。

A.'bcdef'B.'bcdefg'C.'bcpqrst'D.'bcdefef'二、填空1.在線性結(jié)構(gòu)中第一結(jié)點(diǎn)

_______，其余每個(gè)結(jié)點(diǎn)有且只有

_______；最后一個(gè)結(jié)點(diǎn)

________，其余每個(gè)結(jié)點(diǎn)有且只有________。2.對于順序存儲的線性表，當(dāng)隨機(jī)插入或刪除一個(gè)元素時(shí)，約需平均移動表長

___

的元素。

3.對于長度為n的順序表，插入或刪除元素的時(shí)間復(fù)雜性為

____

；對于順序?；蜿?duì)列，插入或刪除元素的時(shí)間復(fù)雜性為

_______

。4.從順序表中刪除第i個(gè)元素時(shí)，首先把第i個(gè)元素賦給

_______

帶回，接著從

_______

開始向后的所有元素均

______一個(gè)位置，最后使線性表的長度

__

。5.在線性表的順序存儲中，元素之間的邏輯關(guān)系是通過

_____

決定的；在線性表的鏈接存儲中，元素之間的邏輯關(guān)系是通過

_____

決定的。6.在具有n個(gè)單元、順序存儲的循環(huán)隊(duì)列中，隊(duì)滿時(shí)共有

個(gè)元素。7.無論對于順序存儲還是鏈接存儲的棧和隊(duì)列來說，進(jìn)行插入或刪除運(yùn)算的時(shí)間復(fù)雜性均相同，則為

。8.一個(gè)數(shù)據(jù)結(jié)構(gòu)用二元組表示時(shí)，它包括

的集合K和K上

的集合R。9．對于一個(gè)二維數(shù)組A[1..m,1..n]，若按行序?yàn)橹餍虼鎯?，則任一元素A[i,j]的相對地址（即偏移地址）為

。10二維數(shù)組A[10][20]采用列序?yàn)橹鞣绞酱鎯?，每個(gè)元素占一個(gè)存儲單元，并且A[0][0]的存儲地址是200，則A[6][12]的地址是____.11廣義表（a,(a,b),d,e,((i,j),k))的長度是__，深度是__三、綜合題1.用三元組表示下面稀疏矩陣的轉(zhuǎn)置矩陣。(行序?yàn)橹餍虻姆绞?┏01000┓┃20003┃M＝┃00400┃┗00050┛

2.二維數(shù)組A[10..20][5..10]采用行序?yàn)橹鞣绞酱鎯?，每個(gè)元素占4個(gè)存儲單元，并且A[10][5]的存儲地址是1000，則A[18][9]的地址是多少？3設(shè)head[p]為求廣義表的表頭函數(shù)，tail[p]為求廣義表p的表尾函數(shù),給出下列廣義表的運(yùn)算結(jié)果：（1）head[(a