2.3　考研真題與典型題詳解

一、選擇題

1下述哪一條是順序存儲結(jié)構(gòu)的優(yōu)點？（　　）[江蘇大學(xué)2006研]

A．插入運(yùn)算方便

B．可方便地用于各種邏輯結(jié)構(gòu)的存儲表示

C．存儲密度大

D．刪除運(yùn)算方便

【答案】C

【解析】順序存儲結(jié)構(gòu)插入刪除操作較麻煩，需要移動大量元素，順序存儲結(jié)構(gòu)也不能用于各種邏輯結(jié)構(gòu)的存儲表示，只能表示線性的邏輯結(jié)構(gòu)。

2線性表是具有n個（　　）的有限序列（n＞0）。

A．表元素

B．字符

C．?dāng)?shù)據(jù)元素

D．?dāng)?shù)據(jù)項

E．信息項

【答案】C

【解析】一個線性表是n個數(shù)據(jù)元素的有限序列。至于每個數(shù)據(jù)元素的具體含義，在不同的情況下各不相同。

3若某線性表最常用的操作是存取任一指定序號的元素和在最后進(jìn)行插入和刪除運(yùn)算，則利用（　　）存儲方式最節(jié)省時間。[哈爾濱工業(yè)大學(xué)2001研]

A．順序表

B．雙鏈表

C．帶頭結(jié)點的雙循環(huán)鏈表

D．單循環(huán)鏈表

【答案】A

【解析】線性表采用順序表，便于進(jìn)行存取任一指定序號的元素（隨機(jī)存取）；線性表采用鏈表，便于進(jìn)行插入和刪除操作。但該題是在最后進(jìn)行插入和刪除運(yùn)算，所以利用順序表存儲方式最節(jié)省時間。

4設(shè)一個鏈表最常用的操作是在末尾插入結(jié)點和刪除尾結(jié)點，則選用（　　）最節(jié)省時間。[江蘇大學(xué)2006研]

A．帶頭結(jié)點的雙循環(huán)鏈表

B．單循環(huán)鏈表

C．帶尾指針的單循環(huán)鏈表

D．單鏈表

【答案】A

【解析】要快速地在末尾插入元素，需要能立馬得到末尾元素結(jié)點，故最好是循環(huán)鏈表。要快速地在末尾刪除元素，需要立馬得到末尾元素結(jié)點的前繼結(jié)點，故最好是雙向鏈表。綜上可見為雙循環(huán)鏈表。

5靜態(tài)鏈表中指針表示的是（　　）。[中南大學(xué)2003研]

A．下一元素的地址

B．內(nèi)存儲器的地址

C．下一元素在數(shù)組中的位置

D．左鏈或右鏈指向的元素的地址

【答案】C

【解析】靜態(tài)鏈表是一種特殊的鏈表，不同于使用指針實現(xiàn)的鏈表，它采用數(shù)組進(jìn)行數(shù)據(jù)的存儲。靜態(tài)鏈表的一般結(jié)構(gòu)為：

struct static_list
{
  ElemType data;
  int next;
}

這種結(jié)構(gòu)是預(yù)先分配一個較大的空間，類似于一次申請一個較大的數(shù)組，但是元素的增刪操作都不會移動元素，只需要更改相關(guān)元素next的值就行。因此，靜態(tài)鏈表中的指針實際上表示的就是下一個元素在數(shù)組中的位置。

6在n個結(jié)點的線性表的數(shù)組實現(xiàn)中，算法的時間復(fù)雜性是O（1）的操作是（　　）。[哈爾濱工業(yè)大學(xué)2003研]

A．訪問第i個結(jié)點（1≤i≤n）和求第i個結(jié)點的直接前驅(qū)（2≤i≤n）

B．在第i個結(jié)點后插入一個新結(jié)點（1≤i≤n）

C．刪除第i個結(jié)點（1≤i≤n）

D．以上都不對

【答案】A

【解析】BC兩項操作復(fù)雜性均為O（n），順序存儲結(jié)構(gòu)具有隨機(jī)存取的特點，則訪問元素時間復(fù)雜度為O（1）。

7若長度為n的線性表采用順序存儲結(jié)構(gòu)，在其第i個位置插入一個新元素的算法的時間復(fù)雜度為（　　）（1≤i≤n＋1）。

A．O（0）

B．O（1）

C．O（n）

D．O（n²）

【答案】C

【解析】線性表采用順序存儲結(jié)構(gòu)，插入和刪除操作的時間復(fù)雜度均為O（n），需要移動大量元素。

8對于雙向循環(huán)鏈表，在p指針?biāo)傅慕Y(jié)點之后插入s指針?biāo)附Y(jié)點的操作應(yīng)為（　　）。[北京工業(yè)大學(xué)2004研]

A．p->right=s;s->left=p;p->right->left=s;s->right=p->right;

B．p->right=s;p->right->left=s;s->left=p;s->right=p->right;

C．s->left=p;s->right=p->right;p->right=s;p->right->left=s;

D．s->left=p;s->right=p->right;p->right->left=s;p->right=s;

【答案】D

【解析】先建立好s指向p和p的后繼結(jié)點的鏈接，即s->left=p;s->right=p->right;然后建立p的后繼結(jié)點指向s的鏈接，即p->right->left=s;最后，斷開p與后繼結(jié)點的鏈接，將p指向s，即p->right=s。

9線性表的順序存儲結(jié)構(gòu)是一種（　　）。[北京理工大學(xué)2006研]

A．隨機(jī)存取的存儲結(jié)構(gòu)

B．順序存取的存儲結(jié)構(gòu)

C．索引存取的存儲結(jié)構(gòu)

D．Hash存取的存儲結(jié)構(gòu)

【答案】A

【解析】線性表包括順序存儲結(jié)構(gòu)和鏈?zhǔn)酱鎯Y(jié)構(gòu)，順序存儲結(jié)構(gòu)能夠隨機(jī)存取表中的元素，但插入和刪除操作較麻煩，鏈?zhǔn)酱鎯Y(jié)構(gòu)不能隨機(jī)訪問表中的元素，但是能夠表示元素之間的先后次序，而且插入和刪除操作較容易。

二、填空題

1當(dāng)線性表的元素總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除操作，但要求以最快的速度存取線性表中的元素時，應(yīng)采用______存儲結(jié)構(gòu)。[北方交通大學(xué)2001研]

【答案】順序

【解析】順序存儲結(jié)構(gòu)的存取操作比較方便，時間復(fù)雜度為O（1），但插入和刪除操作不如鏈?zhǔn)酱鎯Y(jié)構(gòu)方便；而且需要連續(xù)的存儲空間，由于該線性表的元素總數(shù)基本穩(wěn)定，而且很少進(jìn)行插入刪除操作，為了更快的存取元素，順序表更合適。

2在一個長度為n的順序表中第i個元素（1≤i≤n）之前插入一個元素時，需向后移動______個元素。[北京工商大學(xué)2001研]

【答案】n－i＋1

【解析】在第i個元素之前插入元素，需要移動第i個及以后的所有元素，因此需要向右移動n－i＋1個元素。

3在單鏈表中設(shè)置頭結(jié)點的作用是______。[哈爾濱工業(yè)大學(xué)2000研]

【答案】保證處理第一個結(jié)點和后面的結(jié)點的時候設(shè)計的算法相同，實現(xiàn)程序的高效性。

4對于一個具有n個結(jié)點的單鏈表，在已知的結(jié)點p后插入一個新結(jié)點的時間復(fù)雜度為______，在給定值為x的結(jié)點后插入一個新結(jié)點的時間復(fù)雜度為______。[哈爾濱工業(yè)大學(xué)2001研]

【答案】O（1）；O（n）

【解析】第一種情況只需直接修改指針的指向。第二種情況必須從頭結(jié)點遍歷找到x的結(jié)點。

5在雙向循環(huán)鏈表中，向P所指的結(jié)點之后插入指針f所指的結(jié)點，其操作是______、______、______、______。[中國礦業(yè)大學(xué)2000研]

【答案】f->next=p->next;f->prior=p;p->next->prior=f;p->next=f;

【解析】考察雙向循環(huán)鏈表的插入操作，詳見2.1復(fù)習(xí)筆記圖2-4。

6順序存儲結(jié)構(gòu)是通過______表示元素之間的關(guān)系的；鏈?zhǔn)酱鎯Y(jié)構(gòu)是通過______表示元素之間的關(guān)系的。[北京理工大學(xué)2001研]

【答案】物理位置；指針

【解析】順序存儲結(jié)構(gòu)是通過物理位置表示元素之間的關(guān)系的，鏈?zhǔn)酱鎯Y(jié)構(gòu)通過指針表示元素之間的關(guān)系。

7對于雙向鏈表，在兩個結(jié)點之間插入一個新結(jié)點需修改的指針共______個，單鏈表為______個。[南京理工大學(xué)2000研]

【答案】4；2

【解析】雙向鏈表插入新結(jié)點需要修改四個指針，單鏈表只需修改兩個指針。

8在單鏈表L中，指針P所指結(jié)點有后繼結(jié)點的條件是______。[合肥工業(yè)大學(xué)2001研]

【答案】P->next!=NULL

【解析】指針?biāo)附Y(jié)點的指針域所指向的元素非空，說明該指針?biāo)附Y(jié)點有后繼結(jié)點。

三、綜合題

1線性表有兩種存儲結(jié)構(gòu)：一是順序表，二是鏈表。試問：

（1）如果有2個線性表同時并存，并且在處理過程中各表的長度會動態(tài)變化，線性表的總數(shù)也會自動地改變。在此情況下，應(yīng)選用哪種存儲結(jié)構(gòu)？為什么？

（2）若線性表的總數(shù)基本穩(wěn)定，且很少進(jìn)行插入和刪除，但要求以最快的速度存取線性表中的元素，那么應(yīng)采用哪種存儲結(jié)構(gòu)？為什么？

答：（1）應(yīng)選擇鏈?zhǔn)酱鎯Y(jié)構(gòu)。它可動態(tài)申請內(nèi)存空間，不受表長度（即表中元素個數(shù)）的影響，插入、刪除時間復(fù)雜度為O（1）。

（2）應(yīng)選擇順序存儲結(jié)構(gòu)。順序表可以隨機(jī)存取，元素存取的時間復(fù)雜度為O（1）。

2說明在線性表的鏈?zhǔn)酱鎯Y(jié)構(gòu)中，頭指針與頭結(jié)點之間的根本區(qū)別；頭結(jié)點與首元結(jié)點的關(guān)系。[廈門大學(xué)2000研]

答：（1）頭結(jié)點是在鏈表的第一個結(jié)點之前附加一個結(jié)點（該結(jié)點可以不存儲任何信息，也可以存儲鏈表長度等信息），從而使得鏈表的第一個結(jié)點和其他結(jié)點在處理問題上的操作保持一致。

頭指針是為了標(biāo)識一個鏈表而產(chǎn)生的，當(dāng)鏈表存在頭結(jié)點時，則頭指針指向頭結(jié)點，當(dāng)鏈表不存在頭結(jié)點時，頭指針指向鏈表的第一個元素（也可能為空）。

（2）首元結(jié)點也就是第一元素結(jié)點，它是頭結(jié)點后邊的第一個結(jié)點。

3寫算法將單鏈表L1拆成二個鏈表，其中以L1為頭的鏈表保持原來向后的鏈接，另一個鏈表的頭為L2，其鏈接方向與L1相反，L1包含原鏈表的奇數(shù)序號的結(jié)點，L2包含原鏈表的偶數(shù)序號的結(jié)點。[東華大學(xué)2004研]

答：

LinkedList DisUnion(LinkedList* L1,LinkedList* L2)
{
//該算法將L1和L2表拆分成兩個鏈表，其中L2鏈接方向與L1相反
  int i=0;
  L2=(LNode*)malloc(sizeof(LNode));
  L2->next=null; //空鏈表
  LNode* p=L1->next;
  LNode* pre=L1;
  while(p)
  {
    i++;
    if(i%2)
    { //奇數(shù)序號結(jié)點存在L1中
      pre->next=p;
      pre=p;
      p=p->next;
    }
    else
    { //偶數(shù)序號存放在L2中
      s=p->next;
      p->next=L2->next;
      L2->next=p;
      p=s;
    }
  }
}

4在數(shù)組A[1…n]中有n個數(shù)據(jù)，試建立一個帶有頭結(jié)點的循環(huán)鏈表，頭指針為h，要求鏈中數(shù)據(jù)從小到大排列，重復(fù)的數(shù)據(jù)在鏈中只保存一個。

答：

LinkedList create(ElemType A[],int n)
{
//由含有n個數(shù)據(jù)的數(shù)組A生成循環(huán)鏈表，要求鏈表有序并且無值重復(fù)結(jié)點
  LinkedList h;
  h=(LinkedList)malloc(sizeof(LNode)); //申請結(jié)點空間
  h->next=h; //形成一個空循環(huán)鏈表
  LNode* pre,p;
  for(i=0;i<n;i++)
  {
    pre=h;
    p=h->next;
    while(p!=h&&p->data<A[i])
    { //查找及安排A[i]的插入位置
      pre=p;
      p=p->next;
    }
    if(p==h||p->data!=A[i])
    { //去掉重復(fù)數(shù)據(jù)
      s=(LinkedList)malloc(sizeof(LNode));
      s->data=A[i];
      pre->next=s;
      s->next=p;
    }
  } //for
  return h;
} //create()