熱點推薦:
您现在的位置: 電腦知識網 >> 編程 >> 數據結構 >> 正文

全國2013年1月高等教育自學考試數據結構導論試題

2022-06-13   來源: 數據結構 

  一單項選擇題 (在每小題的四個備選答案中選出一個正確答案並將正確答案的序號填在題干的括號內錯選多選或未選均無分每小題分)

  下列數據結構中( )不都是線性結構

  A棧和隊列

  B隊列和數組

  C數組和串

  D文件和隊列

  為了最快地對線性結構的數據進行某數據元素的讀取操作則其數據存儲結構宜采用( )方式

  A順序存儲

  B鏈式存儲

  C索引存儲

  D散列存儲

  設雙鏈表中結點的前趨指針和後繼指針的域名分別為t和r則刪除雙鏈表中指針s所指結點的操作為( )

  As>t>r=s>t;s>r>t=s>r;

  Bs>t>r=s>r;s>r>t=s>t;

  Cs>r=s>t>r;s>t=s>r>t;

  Ds>t=s>t>r;s>r=s>r>t;

  假設left和right為雙向鏈表中指向直接前趨結點和直接後繼結點的指針域現要把一個指針s所指的新結點作為非空雙鏈表中q所指地點(中間結點)的直接後繼結點插入到該雙向鏈表中則下列算法段能正確完成上述要求的是( )

  Aq>right=s; s>left=q; q>right>left=s; s>right=q>right;

  Bs>left=q; q>right=s; q>right>left=s; s>right=q>right;

  Cs>left=q; s>right=q>right; q>right>left=s; q>right=s;

  D以上都不對

  由下列三棵樹組成轉的森林換成一棵二叉樹為( )

  

  具有個結點的完全二叉樹的深度為( )

  A

  B

  C

  D

  已知一個稀疏矩陣的三元組表如下()()()()()()則其轉置矩陣的三元組表中第個三元組為( )

  A()

  B()

  C()

  D()

  無向圖的鄰接矩陣是一個( )

  A對稱矩陣

  B零矩陣

  C上三角矩陣

  D對角矩陣

  下列說法中正確的是( )

  A一個具有n個頂點的無向完全圖的邊數為n(n)

  B連通圖的生成樹是該圖的一個極大連通子圖

  C圖的廣度優先搜索是一個遞歸過程

  D對於非連通圖的遍歷過程中每調用一次深度優先搜索算法都得到該圖的一個連通分量

  順序查找法與二分查找法對存儲結構的要求是( )

  A順序查找與二分查找均只適用於順序表

  B順序查找與二分查找既適用於順序表也適用於鏈表

  C順序查找只適用於順序表

  D二分查找只適用於順序表

  在開散列表上每個地址單元所鏈接的同義詞表( )

  A其鍵值相同

  B其元素值相同

  C其散列地址相同

  D其含義相同

  散列文件中的記錄通常成組存放若干個記錄組成一個存儲單位這個存儲單位稱為( )

  A磁道

  B

  C柱面

  D

  索引非順序文件中的索引表是( )

  A非稠密索引

  B稠密索引

  C主索引

  D多級索引

  對n個記錄的文件進行堆排序最壞情況下的執行時間為( )

  AO(log n)

  BO(nlog n)

  CO(n)

  DO(n )

  一組記錄的關鍵碼為()則利用快速排序方法以第一個記錄為基准得到的一次劃分結果為( )

  A

  B

  C

  D

  二填空題(每小題 分)

  請在每小題的空格中填上正確答案錯填不填均無分

  下列程序段的時間復雜性的量級為_________

  for (i=;i

  for(j=i;j

  t=t+1

  17.設某非空單鏈表,其結點形式為

  date next

  , 若要刪除指針q所指結點的直接後繼結點,則需執行下列語句序列:

  p=q->next;________;free(p);

  18.隊列可以看成是一種運算受限制的線性表,也稱為______線性表。Tw.wINgwit.cOm

  19.鏈棧的類型定義如下:

  typedef struct node

  { DateType date;

  struct node *next;

  }LStackTp;

  若棧非空,則退棧操作可以用下列算法片段實現:

  p=ls;/* ls為棧頂指針*/

  *x=p->date; /*棧頂元素通過參數返回*/

  ___________;

  free(p); /*釋放原棧頂結點空間*/

  20.在非空樹上,_____沒有直接前趨。

  21.設有33個值,用它們組成一棵哈夫曼樹,則該哈夫曼樹中共有____個結點。

  22.無向圖中的連通分量定義為無向圖的_________。

  23.在開散列表上查找鍵值等於K的結點,首先必須計算該鍵值的______,然後再通過指針查找該結點。

  24.對靜態表順序查找算法采用設置崗哨方式與普通的設置循環控制變量相比,進行一次查找所花費的平均時間大約減少_____。

  25.若要對某二叉排序樹進行遍歷,保證輸出的所有結點鍵值序列按遞增次序排列,應對該二叉樹采用_________遍歷法。

  26.文件的基本存取單位是_________。

  27.設需將一組數據按升序排序。在無序區中依次比較相鄰兩個元素a i 和a i+1 的值,若a i 的值大於a i+1 的值,則交換a i 和a i+1 。如此反復,直到某一趟中沒有記錄需要交換為止,該排序方法被稱為_________。

  28.在插入排序、快速排列、堆排序、歸並排序中,排序方法不穩定的有_________。

  三、應用題 (本大題共5小題,共30分)

  29.現有一組單詞(WEK,SUN,MON,TUE,WED,THU,FRI,SAT),其相應的散列函數值為(3,2,6,3,2,5,6,0),散列表長度為10(散列地址空間為0..9),要求:(6分)

  (1)構造該閉散列表,並用線性探測法解決沖突;

  (2)若對每個元素查找一次,求總的比較次數。

  30.已知無向圖G的鄰接矩陣如下。假設對其訪問時每行元素必須從右到左,請畫出其所有的連通分量,並且寫出按深度優先搜索時各連通分量的訪問序列。(8分)

  

  31.設要將序列(Q,H,C,Y,P,A,M,S,R)按字母升序排序,請畫出采用堆排序方法時建立的初始堆及第一次輸出堆頂元素後篩選調整以後的堆。(8分)

  32.設二叉樹後根遍歷的結果為BCA,畫出所有可得到這一結果的二叉樹。(5分)

  33.設有一循環隊列sq.data[maxsize],一般情況下隊列中至多可存放多少個元素?為什麼?(3分)

  四、設計題 (本大題共2小題,共14分)

  34.設有兩個按升序排列的單鏈表X和Y,其頭指針分別為p,q結點結構說明如下:

  typedef struct nodel

  {

  int data;

  struct nodel *next

  }node;

  試設計一個算法void concat(node *p,*q)將它們合並成一個以p為頭指針的單鏈表Z,使其仍然有序。(6分)

  35.設有序表r長度為n,欲在表中查找鍵值為Kn的某元素。若查找成功,則返回該元素在有序表r中的位置,若不成功,則返回0值。用二分查找法,編寫一算法完成上述操作,並給出該算法的平均查找長度。該有序表存儲結構定義如下:(8分)

  typedef struct

  { keytype key;

  Elemtype data;

  }rec;

  typedef struct

  { rec item[maxsize+1];

  int n;

  }sqtable;


From:http://tw.wingwit.com/Article/program/sjjg/201311/23603.html
    推薦文章
    Copyright © 2005-2022 電腦知識網 Computer Knowledge   All rights reserved.