2003年10月北京自考“数据结构”试卷

日期:12-15| http://www.59wj.com |公共课历年真题|人气:677

2003年10月北京自考“数据结构”试卷

课程代码:02331

第一部分 选择题 (共20分)

一、单项选择题 (本大题共8小题,每小题2分,共16分)

  1.某算法的空间花费s(n)=100nlog2n+0.5n1.5+1000n+2000,其空间复杂度为 [   ]
  A.O(1)                      B.O(n)
    C.O(n1.5)                   D.O(nlog2n)

  2.在单项链表中删除一个指定结点的后继的时间复杂度为 [   ]
  A.O(n)                      B.O(nlog2n)
    C.O(1)                      D.O(√n)

  3.在n(n>0)个元素的顺序栈中删除1个元素的时间复杂度为 [   ]
  A.O(1)                      B.O(√n)
    C.O(nlog2n)                 D.O(n)

  4.对长度为n的字符串进行字符定位运算的时间复杂度为 [   ]
    A.O(1)                      B.O(√n)
    C.O(nlog2n)                 D.O(n)

  5.广义表的深度是 [   ]
    A.广义表中子表个数           B.广义表括号个数
    C.广义表展开后所含的括号层数 D.广义表中元素个数

  6.高度为h(h>0)的二叉树最少有________个结点 [   ]
    A.h                          B.h-1
    C.h+1                        D.2h

  7.n个顶点的带权无向连通图的最小生成树包含________个顶点 [   ]
    A.n-1                        B.n
    C.n/2                        D.n+1

  8.冒泡排序在最好情况下时间复杂度为 [   ]
  A.O(1)                      B.O(nlog2n)
    C.O(n)                      D.O(n2)

   9.采用拉链法解决冲突的散列表中,查找的平均查找长度 [   ]
    A.直接与关键字个数有关      B.直接与装填因子a有关
    C.直接与表的容量有关        D.直接与散列函数有关

  10.经常修改的索引文件宜采用________做索引。
    A.二叉排序树                B.满二叉树
    C.多叉树                    D.B+树


第二部分 非选择题 (共80分)

二、填空题 (本大题共10小题,每空2分,共20分)

  11.某算法需要的辅助空间为s(n)=10log2n+2000/n+5,则该算法的空间复杂度为_______________。
  12.在n个结点的单链表中,在P指向的结点之后插入一个结点的时间复杂度为_______________。
  13.设SQ为循环队列,存储在数组d[m]中,则SQ出队操作对其队头指针front的修改是_______________。
  14.串中所含字符个数称为该串的_______________。
  15.tail(tail(a,b))=_______________。
  16.n(n>0)个结点二叉树对应的森林最多包含_______________棵非空树。
  17.深度为n(n>0)的二叉树最多有_______________个结点。
  18.n(n>0)个结点、(n-1)条边的连通无向图中,顶点度数最大值为_______________。
  19.堆排序的空间复杂度_______________。
  20.倒排文件有_______________和主文件构成。


三、简答题 (本大题共5小题,每小题6分,共30分)

  21.设有函数:
     void fuc(int n)
     {int i;
       for(i=1;i*i*i<=n;i++)
         prinft("%d",i*i*i);
     }
     函数fuc饿时间复杂度是多少?

  22.把1、2、3、4依次进栈(栈初始为空),任何时刻(只要栈不空),都可以出(退)栈,试写出所有可能的出栈序列(如1234)。

  23.若一二叉树有2度结点100个,则其叶结点有多少个?该二叉树可以有多少个1度顶点?

  24.请画出广义表D的图形表示
     D=(D,(a,b),((a,b),c),())

  25.有向图(带权)G如下所示:
     试给出用迪杰斯特拉(Dijkstra)算法求上图A到其它各顶点最短路径得到的数组P各元素值(A、B、C、D、E、F编号依次是1、2、3、4、5)。

四、理解题 (本大题共2小题,每小题6分,共12分)

26.指出下面函数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.指出下面函数FS的功能。其中,p指向先序线索二叉树的某个结点。
    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.下面函数diff的功能是:根据两个由整数(都大于-32768)按升序构成的单链表L1和L2(分别由A,B指向)构造一个单链表L3(由*r指向),要求L3中的所有整数都是L1并且不是L2中的整数,还要求L3中的所有整数都两两不等。在空缺处填上适当字句,使其能正确工作。
    #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;
      }
    }

www.59wj.com 如果觉得《2003年10月北京自考“数据结构”试卷》公共课历年真题,zikao不错,可以推荐给好友哦。
本文Tags: 自学考试 - 历年真题 - 公共课历年真题,zikao,
在百度中搜索相关文章:2003年10月北京自考“数据结构”试卷
在谷歌中搜索相关文章:2003年10月北京自考“数据结构”试卷
在soso中搜索相关文章:2003年10月北京自考“数据结构”试卷
在搜狗中搜索相关文章:2003年10月北京自考“数据结构”试卷
相关分类导航|
热门推荐|