2003年10月北京自考“數(shù)據(jù)結(jié)構(gòu)”試卷

課程代碼：02331

第一部分 選擇題 (共20分)

一、單項(xiàng)選擇題 (本大題共8小題，每小題2分，共16分)

  1.某算法的空間花費(fèi)s(n)=100nlog2n+0.5n1.5+1000n+2000,其空間復(fù)雜度為 [   ]
　　A.O(1)                      B.O(n)
    C.O(n1.5)                   D.O(nlog2n)

  2.在單項(xiàng)鏈表中刪除一個(gè)指定結(jié)點(diǎn)的后繼的時(shí)間復(fù)雜度為 [   ]
　　A.O(n)                      B.O(nlog2n)
    C.O(1)                      D.O(√n)

  3.在n(n>0)個(gè)元素的順序棧中刪除1個(gè)元素的時(shí)間復(fù)雜度為 [   ]
　　A.O(1)                      B.O(√n)
    C.O(nlog2n)                 D.O(n)

  4.對(duì)長(zhǎng)度為n的字符串進(jìn)行字符定位運(yùn)算的時(shí)間復(fù)雜度為 [   ]
    A.O(1)                      B.O(√n)
    C.O(nlog2n)                 D.O(n)

  5.廣義表的深度是 [   ]
    A.廣義表中子表個(gè)數(shù)           B.廣義表括號(hào)個(gè)數(shù)
    C.廣義表展開后所含的括號(hào)層數(shù) D.廣義表中元素個(gè)數(shù)

  6.高度為h(h>0)的二叉樹最少有________個(gè)結(jié)點(diǎn) [   ]
    A.h                          B.h-1
    C.h+1                        D.2h

  7.n個(gè)頂點(diǎn)的帶權(quán)無(wú)向連通圖的最小生成樹包含________個(gè)頂點(diǎn) [   ]
    A.n-1                        B.n
    C.n/2                        D.n+1

  8.冒泡排序在最好情況下時(shí)間復(fù)雜度為 [   ]
　　A.O(1)                      B.O(nlog2n)
    C.O(n)                      D.O(n2)

   9.采用拉鏈法解決沖突的散列表中，查找的平均查找長(zhǎng)度 [   ]
    A.直接與關(guān)鍵字個(gè)數(shù)有關(guān)      B.直接與裝填因子a有關(guān)
    C.直接與表的容量有關(guān)        D.直接與散列函數(shù)有關(guān)

  10.經(jīng)常修改的索引文件宜采用________做索引。
    A.二叉排序樹                B.滿二叉樹
    C.多叉樹                    D.B+樹

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

二、填空題 (本大題共10小題，每空2分，共20分)

  11.某算法需要的輔助空間為s(n)=10log2n+2000/n+5，則該算法的空間復(fù)雜度為_______________。
  12.在n個(gè)結(jié)點(diǎn)的單鏈表中，在P指向的結(jié)點(diǎn)之后插入一個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度為_______________。
  13.設(shè)SQ為循環(huán)隊(duì)列，存儲(chǔ)在數(shù)組d[m]中，則SQ出隊(duì)操作對(duì)其隊(duì)頭指針front的修改是_______________。
  14.串中所含字符個(gè)數(shù)稱為該串的_______________。
  15.tail(tail(a,b))=_______________。
  16.n(n>0)個(gè)結(jié)點(diǎn)二叉樹對(duì)應(yīng)的森林最多包含_______________棵非空樹。
  17.深度為n(n>0)的二叉樹最多有_______________個(gè)結(jié)點(diǎn)。
  18.n(n>0)個(gè)結(jié)點(diǎn)、(n-1)條邊的連通無(wú)向圖中，頂點(diǎn)度數(shù)最大值為_______________。
  19.堆排序的空間復(fù)雜度_______________。
  20.倒排文件有_______________和主文件構(gòu)成。

三、簡(jiǎn)答題 (本大題共5小題，每小題6分，共30分)

  21.設(shè)有函數(shù)：
     void fuc(int n)
     {int i;
       for(i=1;i*i*i<=n;i++)
         prinft("%d",i*i*i);
     }
     函數(shù)fuc餓時(shí)間復(fù)雜度是多少？

  22.把1、2、3、4依次進(jìn)棧（棧初始為空），任何時(shí)刻（只要棧不空），都可以出（退）棧，試寫出所有可能的出棧序列（如1234）。

  23.若一二叉樹有2度結(jié)點(diǎn)100個(gè)，則其葉結(jié)點(diǎn)有多少個(gè)？該二叉樹可以有多少個(gè)1度頂點(diǎn)？

  24.請(qǐng)畫出廣義表D的圖形表示
     D=(D,(a,b),((a,b),c),())

  25.有向圖（帶權(quán)）G如下所示：
     試給出用迪杰斯特拉（Dijkstra）算法求上圖A到其它各頂點(diǎn)最短路徑得到的數(shù)組P各元素值（A、B、C、D、E、F編號(hào)依次是1、2、3、4、5）。

四、理解題 (本大題共2小題，每小題6分，共12分)

26.指出下面函數(shù)f的功能及返回值的含義。
    int f(char s1[],char s2[])
    {
      int i=0,j=0;
      while(s1[i]&&s2[j]){
        if(s1[i]>s2[j])
          return 1;
        else if(s1[i]<s2[j])
          return -1;
        else i++,j++;
      }
      if(s1[i])
         return 1;
      else if(s2[j])
         return -1;
      else return 0;
    }

27.指出下面函數(shù)FS的功能。其中，p指向先序線索二叉樹的某個(gè)結(jié)點(diǎn)。
    typedef enum{LINK,THERAD}flag;
    typedef char DataType;
    typedef struct node{
      DataType data;
      flag ltag,rtag;
      struct node * lchild, * rchild;
    }BinNode;
    BinNode * FS(BinNode *p)
    {
      if(p->ltag==LINK)
        return p->lchild;
      else
        return p->rchild;
    }

五、算法填充題 (本大題共1小題，18分)

28.下面函數(shù)diff的功能是：根據(jù)兩個(gè)由整數(shù)（都大于-32768）按升序構(gòu)成的單鏈表L1和L2（分別由A，B指向）構(gòu)造一個(gè)單鏈表L3（由*r指向），要求L3中的所有整數(shù)都是L1并且不是L2中的整數(shù)，還要求L3中的所有整數(shù)都兩兩不等。在空缺處填上適當(dāng)字句，使其能正確工作。
    #include <malloc.h>
    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;
      }
    }