[自学考试密押题库与答案解析]数据结构自考题模拟3
数据结构自考题模拟3



一、单项选择题


列出的四个选项中只有一个选项是符合题目要求的
问题:1.  设有两个串p和q，求q在p中首次出现的位置的运算称为
A.连接
B.模式匹配
C.求子串
D.求串长
答案:B
问题:2.  对于shell排序来说，给定的一组排序数值为
    49,38,65,97,13,27,49,55,04 
    则第二趟排序后的结果为     
A.04,13,27,49,49,38,55,65,76,97
B.04,13,27,38,49,49,55,65,76,97
C.13,04,49,38,27,49,55,65,97,76
D.13,27,49,55,04,49,38,65,97,76
答案:C
问题:3.  将上万个一组无序并且互不相等的正整数序列，存放于顺序存储结构中，采用    方法能够最快地出其中最大的正整数。
A.快速排序
B.插入排序
C.选择排序
D.归并排序
答案:C
问题:4.  长度为12的按关键字有序的查表采用顺序组织方式。若采用二分查方法，则在等概率情况下，查失败时的ASL值是
A.37/12
B.62/13
C.39/12
D.49/13
答案:B
问题:5.  一个具有N个顶点的有向图最多有    条边。
A.N(N-1)/2
B.N(N-1)
C.N(N+1)
D.N(N+1)/2
答案:B
问题:6.  Aarr和Barr两个数组的说明如下：
    VAR  Aarr:Array[O··7]of char; 
        Barr:Array[-5··2,3,··8]of char; 这两个数组分别能存放的字符的最大个数是     
A.7和35
B.1和5
C.8和48
D.1和6
答案:C
问题:7.  对于一棵具有三个结点的二叉树，共有    种不同的树的形态。
A.4
B.5
C.6
D.7
答案:B
问题:8.  设一个数组中，行下标i的范围是从1到8，列下标的范围是从1到10，假设此数组的初始存储地址是A，则如果将此数组按照列优先的顺序连续存放，则元素Q[5][8]的起始地址是
A.1
B.23
C.24
D.529
答案:C
问题:9.  具有24个记录的序列，采用冒泡排序最少的比较次数是
A.1
B.23
C.24
D.529
答案:B
问题:10.  下列说法中正确的是
A.任何一棵二叉树中至少有一个结点的度为2
B.任何一棵二叉树中的每个结点的度为2
C.任何一棵二叉树中的度肯定等于2
D.任何一棵二叉树中的度可以小于2
答案:D
问题:11.  二分查算法要求被查的表是
A.键值有序的链表
B.键值不一定有序的链表
C.键值有序的顺序表
D.键值不一定有序的顺序表
答案:C
问题:12.  下面的程序在执行时，S语句共被执行了    次。
    i=1; 
    while(i＜=n) 
      {for(j=i;j＜n;j++) 
        {    S  ; 
            } 
        i=i+1; 
        } 
     
答案:A
问题:13.  堆(Heap)是
A.完全二叉树
B.线性表
C.二叉排序树
D.平衡二叉树
答案:B
问题:14.  下面程序的时间复杂性是
    for (i=1;i＜=n;i++) 
      for(j=1;j＜=m;j++) 
          {A[i][j]=i*j; 
          } 
A.O(m2)
B.O(n2)
C.O(m*n)
D.O(m+n)
答案:C
问题:15.  与数据元素本身的形式、内容、相对位置、个数无关的是数据的
A.存储结构
B.存储实现
C.逻辑结构
D.运算实现
答案:C



二、填空题
问题:1.  ______的有向图，其全部顶点有可能排成一个拓扑序列。
答案:存在入度为O的结点且没有回路
问题:2.  朴素的串匹配算法的特点是简单，但是其效率较低，其时间匹配算法的最坏时间是______(假设模式串的长度是m，目标串的长度是n)。
答案:0(m+n)
问题:3.  任何连通图的连通分量只有一个，即______。
答案:其自身
问题:4.  设有一个已按各元素的值排好序的线性表，长度为125，对给定的k值，用二分法查与k相等的元素，若查成功，则至少需要比较______次，至多需比较______次。
答案:1  7
问题:5.  在非空队列中，头指针始终指向______，而尾指针始终指向______。
答案:队头元素  队尾元素
问题:6.  数组的长度是______，线性表的长度是______。
答案:固定的  可变的
问题:7.  如果一个图中有n条边，则此图的生成树含有______条边，所以生成树是图的边数______的连通图。
答案:n-1  最少
问题:8.  设二维数组A[10··20,5··10]按行优先存储·，每个元素占4个存储单元，A[10,5]的存储地址是1000，则A[15,10]的存储地址是______。
答案:1700
问题:9.  顺序串是用一组地址连续的存储单元来存储串中的字符序列，所以可以用字符数组来实现，按照存储分配方式的不同可以将顺序串分为两类：即______和______。
答案:静态存储分配的顺序串  动态存储分配的顺序串数据结构与算法分析答案
问题:10.  在线性表的顺序存储中，元素之间的逻辑关系是通过______决定的；在线性表的链接存储中，元素之间的逻辑关系是通过______决定的。
答案:相邻位置  链接指针



三、解答题
问题:1.  试分别画出具有3个结点的树和具有3个结点的二叉树的所有不同的形态。
答案:含有三个结点的树只有两种形式[见(1)和(2)]；含有3个结点的二叉树有5种形态[见(3)，(4)，(5)，(6)，(7)]
     
    对于一棵普通的树来说，图(4)，(5)，(6)，(7)是完全相同的，但如果它们作为二叉树，则表示不同的二叉树，因为在一棵二叉树中，每个结点的孩子都有左右之分，即使某节含有一个孩子，则此孩子结点仍有左右点之分。 
问题:2.  已知串S=‘(xyz)*’，t=‘(x+z)*y’，试利用串的基本运算将s串转化为t串，t串转化为s串。
答案:t=CONCAT(Rep(sup(s,1,5),‘y’,‘+’),Rep(sub(s,6,1),‘*’,‘*y’))
    s=CONCAT(Rep(sub(t,1,5),‘+’,‘y’)，Rep(sub(t,6,2),‘*y’,‘*’)) 
多项式A(x)=anXn+an-1Xn-1+…+a1X+a0的线性表表示法有下列两种可能的形式：
    A=(n,an,an-1，…，a1，a0) 
    A=(m，1m-1，bm-1，1m-2，bm-2，…，10，b0) 
    其中：m为非零项的个数，1i，bi分别为非零项的指数和系数。试分析：
3.  两种表示方法对存储空间的需要情况；
答案:第一种表示需要n+2个实数存储单元，其中n为多项式的最高幂数；第二种表示需要2m+1个实数存储单元，其中m为非零系数的个数。显然，当非零系数较少时，第二种表示法需要较少的存储空间。
4.  进行多项式相加，采用哪一种表示方法处理较为简单?
答案:采用每种表示法处理多项式相加比较简单，只需将次数较低的多项式的各项的系数加到次数较高的多项式的相应项的系数上去即可。而第二种方法要查到相同的指数才能将系数相加，相加之和可能为0，这就要修改项数m；另外当某个多项式中有的项而在另一个多项式中没有，显然其和也应作相应的修改。
问题:5.  假设有一个容量为5的队列，假设其初始状态为front=rear=0，则对此队列进行下列操作之后，请画出此时的头、尾指针的变化情况和相应的队列内元素的存储情况。
    (1)队列为空(即没有任何元素进入)； 
    (2)A，B，C入队； 
    (3)A出队； 
    (4)B，C出队，此时队列为空。 
答案:
     
     
     
    根据队列的操作规则：进队时，将新元素插入到rear所指的位置，然后将rear加1，front不变，出队时，删除front所指的元素，然后将front加1，rear不变，则有：A，B，C进队列后，rear指针指向3，front不变，A出队列时，删除A，将front加1，所以front指向1，rear不变，B，C都出队时，fron加2，rear不变，此时，rear和front相等。 



四、算法阅读题
问题:1.  以下运算实现在循环队上的入队列，请在______处用适当的语句予以填充。
    int EnCycQueue(CycquetaeTp*sq,DataType x) 
          { if((sq—＞rear+1)%maxsize==______) 
                {error("队满");return(0);) 
            else{______; 
                ______; 
            return(1); 
            } 
        } 
答案:sq—＞front sq—＞rear=(sq—＞rear+1)%maxsize sq—＞data[sq—＞rear]=x
问题:2.  以下程序段采用先根遍历方法求二叉树的叶子数，请在______处填充适当的语句。
    void countleaf(bitreptr t,int*count)/*根指针为t，假定叶子数count的初值为0*/ 
        { if(t!=NULL) 
            { if((t—＞lchild==NULL)(t—＞rchild==NULL))______; 
              countleaf(1—＞lehild,count); 
            ______; 
            } 
        } 
答案:*count++  eountleaf(1—＞rehild,count)
问题:3.  以下为冒泡排序的算法。请分析算法，并在______处用适当的语句予以填充。
    void bubblesort(int n,list r)  /*fiag为特征位，定义为布尔型*/ 
    { for(i=1;i＜=______，i++) 
        {______; 
          for(j=1;j＜=______;j++) 
            if(r[j+1].key＜r[j].key){flag=0;p=r[j];r[j]=r[j+1];r[j+1]=P;} 
          if(flag)return; 
        } 
    } 
答案:n-1  flag-1  n-i
问题:4.  基于三元组的稀疏矩阵转置的处理方法有两种，以下运算按照矩阵A的三元组a.data的次序进行转置(快速转置)，请在______处用适当的语句予以填充。
    Fast_Trans_Sparmat(SpMatrixTp a,SpMatrixTp*b) 
      { (*b)．mu=a.nu;(*b).nu=a.mu;(*b).tu=a.tu; 
        if(a.tu)
    { for(col)=1;______col++)unm[col]=0 
      for(t=1;t＜=a.tu;t++)num[a.data[t].j]++; 
      cpot[1]=1; 
      for(col=2;col＜=a.nu;col++)cpot[col]=______; 
      for(p=1;p＜=a.tu;p++) 
        { col=a.data[p].j; 
          q=cpot[col]; 
      (*b).data[q].i=a．data[p].j; 
      (*b).data[q].j=a.data[p].i; 
      (*b).data[q].v=a.data[p].v; 
          ______; 
        } 
      } 
    } 
答案:col—＞=a.nu  cpot[col-1]+num[col-1]  cpot[col]++




五、算法设计题
问题:1.  假设在表示一棵二叉树的二叉链表上增加两个域，双亲域用于指示其双亲结点，标志域flag(可取，0…2)的值，用以区分在遍历过程中到达该结点时继续向左或向右或访问该结点。试以此存储结构编写不用栈进行后序遍历的递推形式的算法。
答案:要解答该题必须分析结点所在的状态，这可以通过结点的标志域来进行。对一个结点来说，当前的结点可能由：(1)其双亲结点转换；(2)其左子树遍历结束转换；(3)其右子树遍历结束转换。所以算法主要执行按这三种状态进行处理或处理当前结点切换结点的状态。从而可将算法描述为：
    void postorder(r)/*后序遍历此二叉树*/ 
    bitree*t/*设为bitree类型的结点含四个域：flag，parent，lchild，rehild，其中flag的域初值为0，指针t指向根结点*/ 
    { bitree * P; 
      P=t; 
      while(p!=Null) 
      switch(—＞flag) 
      { case 0:p—＞flag=1; 
              if(p—＞lchild!=Null) 
              p=p—＞lehild; 
              break; 
      case 1:p—＞flag=2 
            if(jp—＞rchild!=Null) 
                p=p—＞rchild; 
                break; 
      case 2:p—＞flag=0; 
            printf(p—＞data); 
            p=jp—＞parent; 
              break; 
      default; 
      } 
    } /*postorder*/

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。