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

2013年10月北京高教自考“數據結構”試卷

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

  第一部分 選擇題 (共分)

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

  某算法的空間花費s(n)=nlogn+n+n+其空間復雜度為 [ ]

  AO() BO(n)

  CO(n) DO(nlogn)

  在單項鏈表中刪除一個指定結點的後繼的時間復雜度為 [ ]

  AO(n) BO(nlogn)

  CO() DO(√n)

  在n(n>)個元素的順序棧中刪除個元素的時間復雜度為 [ ]

  AO() BO(√n)

  CO(nlogn) DO(n)

  對長度為n的字符串進行字符定位運算的時間復雜度為 [ ]

  AO() BO(√n)

  CO(nlogn) DO(n)

  廣義表的深度是 [ ]

  A廣義表中子表個數 B廣義表括號個數

  C廣義表展開後所含的括號層數 D廣義表中元素個數

  高度為h(h>)的二叉樹最少有________個結點 [ ]

  Ah Bh

  Ch+ Dh

  n個頂點的帶權無向連通圖的最小生成樹包含________個頂點 [ ]

  An Bn

  Cn/ Dn+

  冒泡排序在最好情況下時間復雜度為 [ ]

  AO() BO(nlogn)

  CO(n) DO(n)

  采用拉鏈法解決沖突的散列表中查找的平均查找長度 [ ]

  A直接與關鍵字個數有關 B直接與裝填因子a有關

  C直接與表的容量有關 D直接與散列函數有關

  經常修改的索引文件宜采用________做索引

  A二叉排序樹 B滿二叉樹

  C多叉樹 DB+樹

  第二部分 非選擇題 (共分)

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

  某算法需要的輔助空間為s(n)=logn+/n+則該算法的空間復雜度為_______________

  在n個結點的單鏈表中在P指向的結點之後插入一個結點的時間復雜度為_______________

  設SQ為循環隊列存儲在數組d[m]中則SQ出隊操作對其隊頭指針front的修改是_______________

  串中所含字符個數稱為該串的_______________

  tail(tail(ab))=_______________

  n(n>)個結點二叉樹對應的森林最多包含_______________棵非空樹

  深度為n(n>)的二叉樹最多有_______________個結點

  n(n>)個結點(n)條邊的連通無向圖中頂點度數最大值為_______________

  堆排序的空間復雜度_______________

  倒排文件有_______________和主文件構成

  三簡答題 (本大題共小題每小題分)

  設有函數

  void fuc(int n)

  {int i;

  for(i=;i*i*i<=n;i++)

  prinft(%di*i*i);

  }

  函數fuc餓時間復雜度是多少?

  依次進棧(棧初始為空)任何時刻(只要棧不空)都可以出(退)棧試寫出所有可能的出棧序列(如)

  若一二叉樹有度結點則其葉結點有多少個?該二叉樹可以有多少個度頂點?

  請畫出廣義表D的圖形表示

  D=(D(ab)((ab)c)())

  有向圖(帶權)G如下所示

  試給出用迪傑斯特拉(Dijkstra)算法求上圖A到其它各頂點最短路徑得到的數組P各元素值(ABCDEF編號依次是)

  四理解題 (本大題共小題每小題分)

  指出下面函數f的功能及返回值的含義

  int f(char s[]char s[])

  {

  int i=j=;

  while(s &&s[j]){

  if(s >s[j])

  return ;

  else if(s

  return ;

  else i++j++;

  }

  if(s )

  return ;

  else if(s[j])

  return ;

  else return ;

  }

  指出下面函數FS的功能其中p指向先序線索二叉樹的某個結點

  typedef enum{LINKTHERAD}flag;

  typedef char DataType;

  typedef struct node{

  DataType data;

  flag ltagrtag;

  struct node * lchild * rchild;

  }BinNode;

  BinNode * FS(BinNode *p)

  {

  if(p>ltag==LINK)

  return p>lchild;

  else

  return p>rchild;

  }

  五算法填充題 (本大題共小題分)

  下面函數diff的功能是根據兩個由整數(都大於)按升序構成的單鏈表L和L(分別由AB指向)構造一個單鏈表L(由*r指向)要求L中的所有整數都是L並且不是L中的整數還要求L中的所有整數都兩兩不等在空缺處填上適當字句使其能正確工作

  #include

  typedef struct node {

  int d;

  struct node *next

  } Node;

  void diff (Node *A Node *B Node **r)

  {

  int lastnum;

  Node * p;

  *r=NULL;

  if(!A)return;

  while(_____________)

  if (A>d < B>d)

  _____________;

  p=(Node*) malloc (sizeof(Node));

  p>d=lastnum;

  p>next=*r_____________;

  do A=A>next;while(_____________);

  }

  else if (A>d > B>d)

  B=B>next

  else {

  _____________;lastnum=A>d;

  while (A&&A>d==lastnum)A=A>next;

  }

  while (A) {

  lastnum=A>d;

  p=(Node*) malloc (sizeof(Node));

  p>d=lastnum;

  _____________*r=p;

  while (A&&A>d==lastnum) A=A>next;

  }

  }


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