数据结构导论自考题-2
(总分100, 做题时间90分钟)
一、单项选择题
   在每小题列出的四个备选项中只有一个是符合题目要求的。
1. 
与数据元素本身的形式、内容、相对位置、个数无关的是数据的(    )
   A．存储结构    B．存储实现
   C．逻辑结构    D．运算实现
A  先序中序后序遍历二叉树B  C  D 
    分值: 2
答案:C
2. 
所有的存储结点存放在一个连续的存储空间，该存储方式是(    )存储方式。
   A．顺序    B．链式
   C．索引    D．散列
A  B  C  D 
    分值: 2
答案:A
[解析] 本题主要考查的知识点是顺序存储方式。
[要点透析] 顺序存储方式是指所有存储结点存放在一个连续的存储区里。利用结点在存储器中的相对位置来表示数据元素之间的逻辑关系。
3. 
设线性表有n个元素，以下操作中，(    )在顺序表上实现比在链表上实现效率更高。
   A．输出第i(1≤i≤n)个元素值    B．交换第1个元素与第2个元素的值
   C．在第i个元素前插入一个元素    D．删除第i个元素
A  B  C  D 
    分值: 2
答案:A
[解析] 本题主要考查的知识点为顺序表和链表。
[要点透析] 由于顺序表具有随机存取特性，所以和链表相比输出第i个元素时效率很高。本题答案为A。
4. 
与单链表相比，双链表的优点之一是(    )
   A．插入、删除操作更简单    B．可以进行随机访问
   C．可以省略表头指针或表尾指针    D．前后访问相邻结点更灵活
A  B  C  D 
    分值: 2
答案:D
5. 
循环队列的队满条件为(    )
   A．(CQ.rear+1)%maxsize==(CQ.front+1)%maxsize
   B．(CQ.rear+1)%maxsize==CQ.front+1
   C．(CQ.rear+1)%maxsize==CQ.front
   D．CQ.rear==CQ.front
A  B  C  D 
    分值: 2
答案:C
[解析] 本题主要考查的知识点是循环队列的队满条件。
[要点透析] 约定循环队列的队头指针指示队头元素在数组中实际位置的前一个位置，队尾指针指示队尾元素在数组中的实际位置。当队尾指针“绕一圈”后赶上队头指针时，视为队满。
6. 
数组5][0...5]的每个元素占5个字节，将其以列为主序存储在起始地址为1000的内存单元中，则元素A[5][5]的地址是(    )
   A．1175    B．1180
   C．1205 D．1210
A  B  C  D 
    分值: 2
答案:A
7. 
若二叉树(如图所示)采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，最合适的遍历方法是(    )
   
   A．先序遍历    B．中序遍历
   C．后序遍历    D．按层次遍历
A  B  C  D 
    分值: 2
答案:A
[解析] 本题主要考查的知识点是二叉链表存储结构。
[要点透析] 交换二叉树的左右子树的过程可用递归方法完成，第1步将根结点的左右子树交换，第2步在左子树中递归调用交换函数，第3步在右子树中递归调用交换函数。因此，采用先序遍历的方法最合适。
8. 
设有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，a00为第一个元素，其存储地址为0，每个元素占有1个存储地址空间，则a45的地址为(    )
   A．13    B．19
   C．17 D．36
A  B  C  D 
    分值: 2
答案:B
9. 
在有向图中，所有顶点的入度之和是所有顶点出度之和的(    )
   A．0.5倍    B．1倍
   C．2倍    D．4倍
A  B  C  D 
    分值: 2
答案:B
10. 
设无向图G中顶点数为n，则图G最多拥有边的条数是(    )
   A．n    B．n-1
   C．n(n-1)/2  D．n(n-1)
A  B  C  D 
    分值: 2
答案:C
[解析] 本题主要考查的知识点是无向图中边的条数。
[要点透析] 在无向图为完全图时，取得的边数最多，此时任意两个顶点间都有直接边，边的条数为：(n-1)+…+2+1=n(n-1)/2。
11. 
在图中，从顶点v1出发，按深度优先遍历图的顶点序列是(    )
   
   A．v1 v3 v5 v4 v2 v6 v7    B．v1 v2 v4 v7 v6 v5 v3
   C．v1 v5 v3 v4 v2 v7 v6    D．v1 v4 v7 v2 v6 v5 v3
A  B  C  D 
    分值: 2
答案:C
[解析] 本题主要考查的知识点是深度优先遍历。
[要点透析] 连通图深度优先搜索的基本思想是：假定图中某个顶点vi为出发点。首先访问出发点，然后任选一个vi的未访问过的邻接点vj，以vj为新的出发点继续进行深度优先搜索，直至图中所有顶点都被访问过。
12. 
采用分块查时，若线性表中共有625个元素，查每个元素的概率相同，假设采用顺序查来确定结点所在的块时，每块应分结点的个数是(    )
   A．10    B．25
   C．6    D．625
A  B  C  D 
    分值: 2
答案:B
[解析] 本题主要考查的知识点是分块查。
[要点透析] 分块查一般都是要求每个块的存储空间大小是一样的，而且块数不能太多，每个块也不要太小，否则就成了顺序查了。由于10和6都不能被625整除，不宜作为划分块的标准，而如果采用625，则每个块只有一个元素，这样就失去了分块的意义了。
13. 
从未排序序列中依次取出元素与已排序序列中的元素作比较，将其放入已排序序列的正确位置上，应采用(    )
   A．归并排序    B．插入排序
   C．快速排序    D．选择排序
A  B  C  D 
    分值: 2
答案:B
14. 
具有24个记录的序列，采用冒泡排序最少的比较次数是(    )
   A．1    B．23
   C．24    D．529

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