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

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

2013-11-15 15:25:23  來源: 數據結構 

  一單項選擇題(本大題共 小題每小題 分)

  在每小題列出的四個備選項中只有一個是符合題目要求的請將其代碼填寫在題後的括號內錯選多選或未選均無分

   在數據結構中數據的邏輯結構可以分成(   )

  A 內部結構和外部結構 B 線性結構和非線性結構

  C 緊湊結構和非緊揍結構 D 動態結構和靜態結構

   在以單鏈表為存儲結構的線性表中數據元素之間的邏輯關系用(   )

  A 數據元素的相鄰地址表示 B 數據元素在表中的序號表示

  C 指向後繼元素的指針表示 D 數據元素的值表示

   設 p 指向單鏈表中的一個結點 s 指向待插入的結點則下述程序段的功能是(   )

  s > next = p > next; p > next = s;

  t = p > data; p > data = s > data; s >data = t;

  A 結點 *p 與結點 *s 的數據域互換

  B 在 p 所指結點的元素之前插入元素

  C 在 p 所指結點的元素之後插入元素

  D 在結點 *p 之前插入結點 *s

   棧和隊列都是(   )

  A 限制存取位置的線性結構 B 順序存儲的線性結構

  C 鏈式存儲的線性結構 D 限制存取位置的非線性結構

   若數組 s[n] 為兩個棧 s 和 s 的共用存儲空間且僅當 s[n] 全滿時各棧才不能進行進棧操作則為這兩個棧分配空間的最佳方案是 s 和 s 的棧頂指針的初值分別為(   )

  A 和 n+ B 和 n/

  C 和 n D 和 n+

   執行下列程序段後串 X 的值為(   )

  S= 〞 abcdefgh 〞 ; T= 〞 xyzw 〞 ;

  substr (XSstrlen(T));

  substr (YS stelen(T));

  strcat (XY);

  A 〞 cdefgh 〞 B 〞 cdxyzw 〞

  C 〞 cdefxy 〞 D 〞 cdefef 〞

   多維數組之所以有行優先順序和列優先順序兩種存儲方式是因為(   )

  A 數組的元素處在行和列兩個關系中 B 數組的元素必須從左到右順序排列

  C 數組的元素之間存在次序關系 D 數組是多維結構內存是一維結構

   從廣義表 LS =( (p q) r s )中分解出原子 q 的運算是(   )

  A tail (head (LS)) B head (tail (head (LS)))

  C head (tail (LS)) D tail (tail (head (LS)))

   在具有 n 個葉子結點的嚴格二叉樹中結點總數為(   )

  A n+ B n

  C n D n

   是有向圖的一條邊則稱(   )

  A v i 鄰接於 v j B v j 鄰接於 v i

  C v i 和 v j 相互鄰接 D v i 與 v j 不相鄰接

   在一個帶權連通圖 G 中權值最小的邊一定包含在 G 的(   )

  A 最小生成樹中 B 深度優先生成樹中

  C 廣度優先生成樹中 D 深度優先生成森林中

   當在二叉排序樹中插入一個新結點時若樹中不存在與待插入結點的關鍵字相同的結點且新結點的關鍵字小於根結點的關鍵字則新結點將成為(   )

  A 左子樹的葉子結點 B 左子樹的分支結點

  C 右子樹的葉子結點 D 右子樹的分支結點

   希爾排序的增量序列必須是(   )

  A 遞增的 B 隨機的

  C 遞減的 D 非遞減的

   如果在排序過程中每次均將一個待排序的記錄按關鍵字大小加入到前面已經有序的子表中的適當位置則該排序方法稱為(   )

  A 插入排序 B 歸並排序

  C 冒泡排序 D 堆排序

   設置溢出區的文件是(   )

  A 索引非順序文件 B ISAM 文件

  C VSAM 文件 D 順序文件

  二填空題(本大題共 小題每小題 分)

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

   下列程序段的時間復雜度為 ________________

  product = ;

  for (i = n;i>; i)

  for (j = i+; j

  product *=j;

  17 .已知指針 p 指向單鏈表中某個結點,則語句 p -> next =p -> next -> next 的作用是 ________________ 。TW.WiNGwit.coM

  18 .假設元素只能按 a,b,c,d 的順序依次進棧,且得到的出棧序列中的第一個元素為 c ,則可能得到的出棧序列為 ________________ ,不可能得到的出棧序列為 ________________ 。

  19 .若鏈串結點中的指針占 4 個字節,每個字符占 1 個字節,則結點大小為 2 的鏈串的存儲密度為 ________________ 。

  

  20 .右圖表示的廣義表為 ________________ 。

  21 .若一棵滿三叉樹中含有 121 個結點,則該

  樹的深度為 ________________ 。

  22 .若以鄰接矩陣表示有向圖,則鄰接矩陣上

  第 i 行中非零元素的個數即為頂點 v i 的 ________________ 。

  23 .若希望只進行 8 趟排序便能在 4800 個元素中找出其中值最小的 8 個元素,並且要求排序過程中所進行的關鍵字比較次數盡可能少,則應該選用 ________________ 排序方法。

  24 .在含 20 個關鍵字的 3 階 B 樹( 2 - 3 樹)上查找一個關鍵字,至多需要訪問 ___________ 次外存。

  25 .文件上的兩類主要操作為 ________________ 和 ________________ 。

  三、解答題(本大題共 4 小題,每小題 5 分,共 20 分)

  26 .設棧 S1 的入棧序列為 1 2 3 4 (每個數字為 13 個元素),則不可能得到出棧序列 3142 。但可通過增設棧 S2 來實現。例如,按下圖中的箭頭指示,依次經過棧 S1 和 S2 ,便可得到序列 3 1 4 2 。

  

  如果用 H1 和 H2 分別表示棧 S1 和 S2 的進棧操作,用 P1 和 P2 分別表示兩個棧的出棧操作,則得到 3 1 4 2 的一個操作步驟為

  H1 , H1 , H1 , P1 , H2 , P2 , P1 , H2 , P1 , H2 , P2 , H1 , P1 , H2 , P2 , P2

  請仿照上例寫出利用兩個棧從 1 2 3 4 得到 4 1 3 2 的操作步驟。

  27 .已知樹如右圖所示,

  

  ( 1 )寫出該樹的後序序列;

  ( 2 )畫出由該樹轉換得到的二叉樹。

  28 .為關鍵字( 17 , 33 , 31 , 40 , 48 )構造一個長度為 7 的散列表,設散列函數為 h(key)=key%7, 用開放定址法解決沖突的探查序列是

  hi = (h(key) + i(key%5+1))%7 0 ≤ i ≤ 6

  ( 1 )畫出構造所得的散列表;

  ( 2 )求出在等概率情況下查找成功時的平均查找長度。

  29 .已知 R [ 1..8 ]中的元素依次為( 12 , 5 , 9 , 20 , 6 , 31 , 24 , 27 ),寫出按算法 MergeSortDC  對 R 進行自頂向下的二路歸並排序過程中,前 5 次調用函數 Merge(R, low, mid, high) 時參數 low, mid 和 high 的值。

  void MergeSortDC (int R[], int low, int mid, int high )

  {

  int mid;

  if (low

  {

  mid = (low +high)/2;

  MergeSortDC (R, low, mid);

  MergeSortDC (R, mid+1, high);

  Merge (R, low, mid, high);

  }

  } // MergeSortDC

  ( 1 )第一次調用時的參數值;

  ( 2 )第二次調用時的參數值;

  ( 3 )第三次調用時的參數值;

  ( 4 )第四次調用時的參數值;

  ( 5 )第五次調用時的參數值;

  四、算法閱讀題(本大題共 4 小題,每小題 5 分,共 20 分)

  30 .下列函數的功能是,對以帶頭結點的單鏈表作為存儲結構的兩個遞增有序表(表中不存在值相同的數據元素)進行如下操作:將所有在 Lb 表中存在而 La 表中不存在的結點插入到 La 中,其中 La 和 Lb 分別為兩個鏈表的頭指針。請在空缺處填入合適內容,使其成為一個完整的算法。

  void union (LinkList La, LinkList Lb)

  {

  // 本算法的功能是將所有 Lb 表中存在而 La 表中不存在的結點插入到 La 表中

  LinkList pre = La, q;

  LinkList pa = La -> next;

  LinkList pb = Lb -> next;

  free (Lb);

  while (pa && pd)

  {

  if (pa -> data data)

  { pre = pa; pa = pa -> next;}

  else if (pa -> data > pb ->data)

  {

  (1) ;

  pre = pb;

  pb = pb -> next;

  (2) ;

  }

  else

  {

  q = pb; pb = pb -> next; free (q);

  }

  }

  if (pb)

  (3) ;

  }

  (1)

  (2)

  (3)

  31 .已知串的存儲結構為動態存儲分配的順序串。閱讀下列算法,並<
From:http://tw.wingwit.com/Article/program/sjjg/201311/23383.html

    推薦文章
    Copyright © 2005-2013 電腦知識網 Computer Knowledge   All rights reserved.