欢迎您访问江西自考网!  今天是
当前位置: 网站首页 > 历年真题 >

全国2010年1月自考数据结构试题

2013-08-18 11:20来源:湖南自考网
全国2010年1月高等教育自学考试
数据结构试题
课程代码:02331
一、单项选择题(本大题共15小题,每小题2分,共30分)
  在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.若一个算法的时间复杂度用T(n)表示,其中n的含义是(     )
A.问题规模    B.语句条数     C.循环层数        D.函数数量
2.具有线性结构的数据结构是(     )
A.树          B.图           C.栈和队列       D.广义表
3.将长度为n的单链表连接在长度为m的单链表之后,其算法的时间复杂度为(     )
A.O(1)        B.O(m)         C.O(n)           D.O(m+n)
4.在带头结点的双向循环链表中插入一个新结点,需要修改的指针域数量是(     )
A.2个         B.3个    .    C.4个           D.6个
5.假设以数组A[60]存放循环队列的元素,其头指针是front=47,当前队列有50个元素,则队列的尾指针值为(     )
A.3          B.37             C.50           D.97
6.若栈采用链式存储结构,则下列说法中正确的是(     )
A.需要判断栈满且需要判断栈空               B.不需要判断栈满但需要判断栈空
C.需要判断栈满但不需要判断栈空             D.不需要判断栈满也不需要判断栈空
7.若串str=”Software”,其子串的数目是(     )
A.8        B.9      C.36           D.37
8.设有一个10阶的下三角矩阵A,采用行优先压缩存储方式,all为第一个元素,其存储地址为1000,每个元素占一个地址单元,则a85的地址为    (     )
A.1012     B.1017      C.1032          D.1039
9.允许结点共享的广义表称为(     )
A.纯表     B.线性表     C.递归表         D.再入表
10.下列数据结构中,不属于二叉树的是(     )
A.B树      B.AVL树     C.二叉排序树       D.哈夫曼树
11.对下面有向图给出了四种可能的拓扑序列,其中错误的是(     )

A.1,5,2,6,3,4    B.1,5,6,2,3,4   C.5,1,6,3,4,2    D.5,1,2,6,4,3
12.以v1为起始结点对下图进行深度优先遍历,正确的遍历序列是(     )

A.v1,v2,v3,v4,v5,v6,v7      B.v1,v2,v5,v4,v3,v7,v6
C.v1,v2,v3,v4,v7,v5,v6      D.v1,v2,v5,v6,v7,v3,v4
13.下列排序算法中不稳定的是(     )
A.快速排序      B.归并排序       C.冒泡排序       D.直接插入排序
14.一个有序表为(1,3,9,12,32,41,45,62,75,77,82,95,100),当采用折半查找方法查找值32时,查找成功需要的比较次数是(     )
A.2        B.3       C.4       D.8
15.采用ISAM组织文件的方式属于(     )
A.链组织       B.顺序组织      C.散列组织         D.索引组织
 
二、填空题(本大题共10小题,每小题2分,共20分)
    请在每小题的空格中填上正确答案。错填、不填均无分。
16.数据元素及其关系在计算机存储器内的表示称为_________。
17.长度为n的线性表采用单链表结构存储时,在等概率情况下查找第i个元素的时间复杂度是_________。
18.下面是在顺序栈上实现的一个栈基本操作,该操作的功能是_________。
    typedef struct{
    DataType data[100];
         int top;
    }SeqStack;
    DataType f18(SeqStack*S)
    {    if(StackEmpty(S))
    Error(”Stack is empty”);
    return S->data[S->top];
    }
19.在串匹配中,一般将主串称为目标串,将子串称为_________。
20.已知广义表C=(a(b,c),d),则:tail(head(tail(C)))= _________。
21.用6个权值分别为6、13、18、30、7和16的结点构造一棵哈夫曼(Huffman)树,该树的带权路径长度为_________。
22.已知有向图如下所示,其中顶点A到顶点C的最短路径长度是_________。

23.对序列{55,46,13,05,94,17,42}进行基数排序,第一趟排序后的结果是_________。
24.高度为3的3阶B-树最少的关键字总数是_________。
25.VSAM通常作为大型索引顺序文件的标准组织,其动态索引结构采用的是_________。
三、解答题(本大题共4小题,每小题5分,共20分)
26.假设二叉树的RNL遍历算法定义如下:
  若二叉树非空,则依次执行如下操作:
    (1)遍历右子树;
  (2)访问根节点;
  (3)遍历左子树。
已知一棵二叉树如图所示,请给出其RNL遍历的结果序列。
27.已知一个无向图G=(V,E),其中V={A,B,C,D,E,F},邻接矩阵表示如下所示。

请回答下列问题:
(1)请画出对应的图G。
(2)画出图G的邻接表存储结构。
28.已知一组待排记录的关键字序列为(16,12,18,60,15,36,14,18,25,85),用堆排序方法建小根堆,请给出初始建堆后的序列。
29.已知一棵二叉排序树如图所示。
    请回答下列问题:
    (1)画出插入元素23后的树结构;
(2)请画出在原图中删除元素57后的树结构。

四、算法阅读题(本大题共4小题,每小题5分,共20分)
30.已知下列程序,Ls指向带头结点的单链表。
 Typedefstruct node  {
         DataType  data;
      struct node * next;
 } * LinkList;
 void f30( LinkList Ls )
{   LinkList p, q;
      q = Ls->next;
      if ( q && q->next ) {
           Ls->next = q->next;
           p=q
           while ( p->next )
                p = p->next;
           p->next = q;
           q->next = NULL;
}
}
请回答下列问题:
(1)当Ls指向的链表如下图所示,请画出执行本函数之后的链表的结果。

(2)请简述算法的功能。
31.已知字符串处理函数f31程序如下。
    int f31(char*strl,char*str2)
    {  while(*strl==*str2&&(*strl!=’\0’)){
    strl++;
    str2++;
  }
    return(*strl-*str2 ? l∶0);
    }
    请回答下列问题:
    (1)若调用语句是f31(”abcde”,”abcdf’),则函数的返回值是什么?若调用语句是    f31(”abcde”,”abcde”),则函数的返回值是什么?
    (2)简述该函数的功能。
32.数组A[]中存储有n个整数,请阅读下列程序。
    void f32(intA[],int n)
    {  inti,j,k,x;
    k=n-l;
        while(k>0){
    i=k;  k=0;
    for(j=O;j<i;j++)
    if(A[j]>A[j+1]){
    x=A[j];
    A[j]=A[j+l];
    A[j+1]=x;
   k=j;
    }//end of if
  }//end of while
   return;
    }
  请回答下列问题:
  (1)当A[]={10,8,2,4,6,7}时,执行f32(A,6)后,数组A中存储的结果是什么?
  (2)说明该算法的功能。
33.下面程序实现二分查找算法。
    Typedef struct{
   KeyType key;
    InfoType otherinfo;
    }SeqList[N+1];
    int BinSearch(SeqList R, int n,KeyType K)
    {  int low=1,high=n;
       while(    (1)    ){
    mid=(1ow+high)/2;
    if(    (2)    )
    return mid;
    if(R[mid].key>K)
   high=mid-1;
    else
       (3)   
   }
       return O;
    }  //BinSearch
  请在空白处填写适当内容,使该程序功能完整。
  (1)
  (2)
  (3)
 
五、算法设计题(本题10分)
34.已知二叉树采用二叉链表存储,其结点结构定义如下:
    typedef struct Node{
  ElmType data;
    struct Node  *lchild,*rchild;
    }*BiTree;
    请编写递归函数SumNodes(BiTree T),返回二叉树T的结点总数。
 
 
本试题下载:
全国2010年1月自考02331数据结构试题.doc

上一篇:全国2009年10月自考数据结构试题

下一篇:全国2010年10月自考数据结构试题