全國(guó)2007年10月高等教育自學(xué)考試

數(shù)據(jù)結(jié)構(gòu)試題

課程代碼：02331

一、單項(xiàng)選擇題（本大題共15小題，每小題2分，共30分）

在每小題列出的四個(gè)備選項(xiàng)中只有一個(gè)是符合題目要求的，請(qǐng)將其代碼填寫在題后的括號(hào)內(nèi)。錯(cuò)選、多選或未選均無分。

1.下面程序段的時(shí)間復(fù)雜度為(      )

  s=0；

  for(i=1；i<n；i++)

    for(j=1；j<i；j++)

      s+=i*j；

A.O(1) B.O(logn)

C.O(n) D.O(n²)

2.已知指針p和q分別指向某單鏈表中第一個(gè)結(jié)點(diǎn)和最后一個(gè)結(jié)點(diǎn)。假設(shè)指針s指向

  另一個(gè)單鏈表中某個(gè)結(jié)點(diǎn)，則在s所指結(jié)點(diǎn)之后插入上述鏈表應(yīng)執(zhí)行的語(yǔ)句為(      )

A.q->next=s->next；s->next=p； B.s->next=p；q->next=s->next；

C.p->next=s->next；s->next=q； D.s->next=q；p->next=s->next；

3.在計(jì)算機(jī)內(nèi)實(shí)現(xiàn)遞歸算法時(shí)所需的輔助數(shù)據(jù)結(jié)構(gòu)是(      )

A.棧 B.隊(duì)列

C.樹 D.圖

4.假設(shè)以數(shù)組A[m]存放循環(huán)隊(duì)列的元素。已知隊(duì)列的長(zhǎng)度為length，指針rear指向隊(duì)

  尾元素的下一個(gè)存儲(chǔ)位置，則隊(duì)頭元素所在的存儲(chǔ)位置為(      )

A.(rear-length+m+1)％m B.(rear-length+m)％m

C.(rear-length+m-1)％m D.(rear-length)％m

5.通常將鏈串的結(jié)點(diǎn)大小設(shè)置為大于1是為了(      )

A.提高串匹配效率 B.提高存儲(chǔ)密度

C.便于插入操作 D.便于刪除操作

6.帶行表的三元組表是稀疏矩陣的一種(      )

A.順序存儲(chǔ)結(jié)構(gòu) B.鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

C.索引存儲(chǔ)結(jié)構(gòu) D.散列存儲(chǔ)結(jié)構(gòu)