全国自考（数据结构）模拟试卷2

如果您发现本试卷没有包含本套题的全部小题，请尝试在页面顶部本站内搜索框搜索相关题目，一般都能找到。

35．下列算法用于判断带头结点的循环双链表A是否对称相等，请在算法中的一填上正确的语句。
int dlink_symmetry(dlklist s)
  {j=true;
    p=s—＞next;
    q=s—＞prior;
    while(p!=q)&(______)
      if(p—＞data=q—＞data)
         { (______);
        (______);
         }
      else
           j=false;
       return(j);
  }
点击查看答案
34．以下为单链表的定位运算，分析算法，请在______处填上正确的语句。
int locate_iklist(1klist head,datatype x)
  /*求表head中第一个值等于x的结点的序号。不存在这种结点时结果为0*/
    { p=head;j=O;
      while(______){p=p—＞next;j++;}
      if(p—＞data==x)return(j);
      else{return(0);
    }
点击查看答案
36．若输入12000个不同的整数，其值介于0和19999之间，采用散列表存储这些数，散列函数为h(k)=k/2，请设计实现的算法。
点击查看答案
33．以下是图的广度优先搜索算法，请在______处填充适当的语句。
Bfs(GraphTp g,int v)
    { QueptrTp Q;
    ArcNodeTp*P;
    InitQueue(&Q);
    printf("%"”,v);
    visited[v]=1;
    ______
    while(!EmptyQueue(Q))
    {______;
    p=g.adjlist[v].firstarc;
    while(p! =NULL)
    { if(! visited[p—＞adjvex])
    { printf("%"”,p—＞adjvex);
      visited[p—＞adjvex]=1);
      EnQueue(&Q，p—＞adjvex);
    }
    ______;
    }
   }
  }
点击查看答案
32．以下运算实现在循环队上取队头，请在______处用适当的语句予以填充。
int GetHead(CycqueueTp sq,DataType*x)
       { if(sq.rear==______return(0);
          else{*x=sq.data[______];
               return(1);
              }
       }
点击查看答案
31．请画出二叉树的五种基本形态。
点击查看答案
30．已知散列函数为H(K)=K mod 12，键值序列为25,37,52,43,84,99,120,15,26,11,70,82，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。
点击查看答案
28．以上述两个单链表为基础，通过插入和删除等运算得出A(x)+B(x)的存储表示，使其存储空间覆盖A(x)和B(x)的存储空间。
点击查看答案
29．假设一个循环队列的容量为50，对其进行人队和出队操作，则经过一段时间之后，有：
(1)front=35，rear=12；
(2)front=12，rear=35。
其中front和rear分别是队头和队尾指针。
求：循环队列中元素的个数?
点击查看答案
27．用单链表给出B(x)的存储表示。
点击查看答案
25．在线性表的顺序存储中，元素之间的逻辑关系是通过______决定的；在线性表的链接存储中，元素之间的逻辑关系是通过______决定的。
点击查看答案
设有多项式
A(x)=7+3x+9x⁸+5x¹⁷
B(x)=8x+22x⁷一9x⁸
用单链表给出A(x)的存储表示。
点击查看答案
24．顺序串是用一组地址连续的存储单元来存储串中的字符序列，所以可以用字符数组来实现，按照存储分配方式的不同可以将顺序串分为两类：即______和______。
点击查看答案
23．设二维数组A[10··20,5··10]按行优先存储·，每个元素占4个存储单元，A[10,5]的存储地址是1000，则A[15,10]的存储地址是______。
点击查看答案
22．如果一个图中有n条边，则此图的生成树含有______条边，所以生成树是图的边数______的连通图。
点击查看答案
21．数组的长度是______，线性表的长度是______。
点击查看答案
18．任何连通图的连通分量只有一个，即______。
点击查看答案
20．在非空队列中，头指针始终指向______，而尾指针始终指向______。
点击查看答案
19．设有一个已按各元素的值排好序的线性表，长度为125，对给定的k值，用二分法查找与k相等的元素，若查找成功，则至少需要比较______次，至多需比较______次。
点击查看答案
17．朴素的串匹配算法的特点是简单，但是其效率较低，其时间匹配算法的最坏时间是______(假设模式串的长度是m，目标串的长度是n)。
点击查看答案
16． ______的有向图，其全部顶点有可能排成一个拓扑序列。
点击查看答案
14．当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为 ( )
- A．n²
- B．n·lonaⁿ
- C．log2ⁿ
- D．n-1
点击查看答案
15．栈一般情况下常采用以下两种存储方式( )
- A．顺序结构和散列结构
- B．散列结构和链式结构
- C．线性结构和非线性结构
- D．顺序存储结构和链式结构
点击查看答案
13．假定一棵二叉树的结点为18个，则此二叉树的最大高度为( )，最小高度为( )
- A．4
- B．5
- C．6
- D．18
点击查看答案
12．下面关于线性表的叙述错误的是( )
- A．线性表采用顺序存储，必须占用一片连续的存储单元
- B．线性表采用顺序存储，便于进行插入和删除操作
- C．线性表采用链接存储，不必占用一片连续的存储单元
- D．线性袁采用链接存储，不便于插入和删除操作
点击查看答案
11．考虑下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是( )
- A．直接插入排序和快速排序
- B．快速排序和归并排序
- C．直接选择排序和归并排序
- D．直接插入排序和归并排序
点击查看答案
9．线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着( )
- A．每个结点所代表的数据元素都一样
- B．每个结点所代表的数据元素包含的数据项的个数要相等
- C．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致
- D．结点所代表的数据元素有同一特点
点击查看答案
10．非空的循环单链表head的尾结点(由指针p所指)满足( )
- A．p—＞next=NULL
- B．p=NULL
- C．p—＞next=head
- D．p=head
点击查看答案
7．如果一个队列的入队顺序是1,2,3,4,5，则此队列的出队顺序是( )
- A．5,4,3,2,1
- B．4,5,1,2,3
- C．1,2,3,4,5
- D．不确定
点击查看答案
8．静态查找表与动态查找表二者的根本差别在于( )
- A．它们的逻辑结构不一样
- B．施加在其上的操作不同
- C．所包含的数据元素的类型不一样
- D．存储实现不一样
点击查看答案
5．在一个具有N个顶点的无向完全图中，包含的边的总数是( )
- A．N(N-1)/2
- B．N(N-1)
- C．N(N+1)
- D．N(N+1)/2
点击查看答案
6．在一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p，q之间插入s结点，则执行( )操作。
- A．s—＞next=p—＞next;p—＞next=s;
- B．q—＞next=s;s—＞next=p;
- C．p—＞next=s—＞next;s—＞next=p;
- D．p—＞next=s;s—＞next=q;
点击查看答案
4． ( )方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。
- A．归并排序
- B．插入排序
- C．快速排序
- D．选择排序
点击查看答案
3．下面的查找方式中，可以对无序表进行查找的是( )
- A．顺序查找
- B．二分查找
- C．二叉排序树
- D．B-树上的查找
点击查看答案
2．磁带适合存储的文件类型是( )
- A．索引文件
- B．顺序文件
- C．散列文件
- D．多关键字文件
点击查看答案
1．循环链表的主要优点是( )
- A．不再需要头指针了
- B．已知某个结点的位置后，能够容易找到它的直接前趋
- C．在进行插入、删除运算时，能更好地保证链表不断开
- D．从表中任一结点出发都能扫描到整个链表
点击查看答案

全国自考（数据结构）模拟试卷2

36．若输入12000个不同的整数，其值介于0和19999之间，采用散列表存储这些数，散列函数为h(k)=k/2，请设计实现的算法。

32．以下运算实现在循环队上取队头，请在处用适当的语句予以填充。
int GetHead(CycqueueTp sq,DataTypex)
       { if(sq.rear==return(0);
          else{x=sq.data[__];
               return(1);
              }
       }

31．请画出二叉树的五种基本形态。

30．已知散列函数为H(K)=K mod 12，键值序列为25,37,52,43,84,99,120,15,26,11,70,82，采用拉链法处理冲突，试构造开散列表，并计算查找成功的平均查找长度。

28．以上述两个单链表为基础，通过插入和删除等运算得出A(x)+B(x)的存储表示，使其存储空间覆盖A(x)和B(x)的存储空间。

29．假设一个循环队列的容量为50，对其进行人队和出队操作，则经过一段时间之后，有：
(1)front=35，rear=12；
(2)front=12，rear=35。
其中front和rear分别是队头和队尾指针。
求：循环队列中元素的个数?

27．用单链表给出B(x)的存储表示。

25．在线性表的顺序存储中，元素之间的逻辑关系是通过决定的；在线性表的链接存储中，元素之间的逻辑关系是通过决定的。

设有多项式
A(x)=7+3x+9x⁸+5x¹⁷
B(x)=8x+22x⁷一9x⁸
用单链表给出A(x)的存储表示。

24．顺序串是用一组地址连续的存储单元来存储串中的字符序列，所以可以用字符数组来实现，按照存储分配方式的不同可以将顺序串分为两类：即和。

23．设二维数组A[10··20,5··10]按行优先存储·，每个元素占4个存储单元，A[10,5]的存储地址是1000，则A[15,10]的存储地址是______。

22．如果一个图中有n条边，则此图的生成树含有条边，所以生成树是图的边数的连通图。

21．数组的长度是，线性表的长度是。

18．任何连通图的连通分量只有一个，即______。

20．在非空队列中，头指针始终指向，而尾指针始终指向。

19．设有一个已按各元素的值排好序的线性表，长度为125，对给定的k值，用二分法查找与k相等的元素，若查找成功，则至少需要比较次，至多需比较次。

17．朴素的串匹配算法的特点是简单，但是其效率较低，其时间匹配算法的最坏时间是______(假设模式串的长度是m，目标串的长度是n)。

16． ______的有向图，其全部顶点有可能排成一个拓扑序列。

14．当初始序列已经按键值有序时，用直接插入算法进行排序，需要比较的次数为 ( )

15．栈一般情况下常采用以下两种存储方式( )

13．假定一棵二叉树的结点为18个，则此二叉树的最大高度为( )，最小高度为( )

12．下面关于线性表的叙述错误的是( )

11．考虑下列四种排序方法，在排序过程中，关键码比较的次数与记录的初始排列顺序无关的是( )

9．线性结构中的一个结点代表一个数据元素，通常要求同一线性结构的所有结点所代表的数据元素具有相同的特性，这意味着( )

10．非空的循环单链表head的尾结点(由指针p所指)满足( )

7．如果一个队列的入队顺序是1,2,3,4,5，则此队列的出队顺序是( )

8．静态查找表与动态查找表二者的根本差别在于( )

5．在一个具有N个顶点的无向完全图中，包含的边的总数是( )

6．在一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p，q之间插入s结点，则执行( )操作。

4． ( )方法是对序列中的元素通过适当的位置交换将有关元素一次性地放置在其最终位置上。

3．下面的查找方式中，可以对无序表进行查找的是( )

2．磁带适合存储的文件类型是( )

1．循环链表的主要优点是( )