数据结构自考2014年10月真题及答案解析

本试卷为单选题型，填空题，算法阅读，算法设计等题型。

一、单项选择题(本大题共15小题，每小题2分，共30分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。

1.下列选项中，属于逻辑结构的是(　　)

A.线性表
B.链表
C.顺序栈
D.循环队列

2.下列关于算法输出的叙述中，正确的是(　　)

A.算法一定没有输出
B.算法可以没有输出
C.算法至少有一个输出
D.算法必须有多个输出

3.针对线性表逻辑上相邻的两个元素，下列叙述中，正确的是(　　)

A.采用顺序存储时一定相邻，采用链式存储时也一定相邻
B.采用顺序存储时一定相邻，采用链式存储时不一定相邻
C.采用顺序存储时不一定相邻，采用链式存储时一定相邻
D.采用顺序存储时不一定相邻，采用链式存储时也不一定相邻

4.队列和栈的特征分别是(　　)

A.先进先出，先进后出
B.先进先出，先进先出
C.先进后出，先进先出
D.先进后出，先进后出

5.在二维数组a[8][10]中，每个数组元素a[i][j]占用3个存储空间，所有数组元素存放在一个连续的存储空间中，则该数组需要的存储空间个数是(　　)

A.80
B.100
C.240
D.270

6.广义表A=(a，(b，e，(e，f，g，h)))的表长是(　　)

A.2
B.3
C.4
D.7

7.设深度为k(k≥1)的二叉树中只有度为0和度为2的结点，则该二叉树中所包含的结点数至少是(　　)

A.k+1
B.2k+1
C.2k-1
D.2k

8.下列选项中，可以唯一确定一棵二叉树的两种遍历序列是(　　)

A.前序遍历序列和中序遍历序列
B.前序遍历序列和后序遍历序列
C.前序遍历序列和层次遍历序列
D.后序遍历序列和层次遍历序列

9.下列关于无向连通图特性的叙述中，正确的是(　　)

A.边数大于顶点个数减1
B.所有顶点的度之和为偶数
C.度为1的顶点个数一定为偶数
D.度为1的顶点个数一定为奇数

10.下列关于无向图广度优先搜索序列的叙述中，正确的是(　　)

A.广度优先搜索序列只有一种
B.广度优先搜索序列可能不存在
C.广度优先搜索序列可能有多种
D.广度优先搜索序列一定有多种

11.设带权连通图G中含有n(n>1)个顶点e条边。下列关于G的最小生成树的叙述中， 正确的是(　　)

A.生成树中一定含有权值最小的e条边
B.生成树中可能含有权值最小的n+1条边
C.生成树中一定含有权值最小的n条边
D.生成树中可能含有权值最小的n-1条边

12.下列排序方法中，时间复杂度与数据初始状态相关的是(　　)

A.直接选择排序
B.快速排序
C.基数排序
D.箱排序

13.下列排序方法中，效率较高且稳定的方法是(　　)

A.直接插入排序
B.冒泡排序
C.快速排序
D.归并排序

讯享网

14.下列叙述中，不符合m阶B树定义的是(　　)

A.根结点最多有m棵子树
B.所有叶结点都在同一层上
C.各结点内关键字均升序或降序排列
D.叶结点之间通过指针链接

15.假设散列表长m=11，散列函数H(key)=key%11。表中已有4个结点：H(39)=6，H(41)=8，H(53)=9，H(76)=10，占了4个位置，其余位置为空。现采用线性探查法处理冲突，存储关键字85时需要探查的次数是(　　)

A.2
B.3
C.4
D.5

二、填空题(本大题共10小题，每小题2分，共20分) 请在每小题的空格中填上正确答案。错填、不填均无分。

11.著名计算机科学家沃思曾指出：算法+______=程序。

12.描述算法占内存空间效率的术语是___。

13.设顺序表第1个元素的存储地址是2000，每个数据元素占4个字节，则第41个元素的存储地址是___。

14.栈和队列是操作受限的线性表，其中只能在表的一端进行插入或删除操作的是___。

15.广义表A=(a,(b,c,(e,f,g,h)))，tail(A)=___。

16.一颗左子树为空的二叉树在中序线索化后，其空指针域的个数为___。

17.除邻接表外，图的另一种链式存储方式是___。

18.含n个顶点e条边的带权连通图G，采用迪杰斯特拉算法得到的某个给定顶点到其余各顶点最短路径的条数是___。

19.DFS算法的中文名称是___。

110.若构造一颗具有n个结点的二叉排序树，在最坏情况下，其深度为______。

三、解答题(本大题共4小题，每小题5分，共20分)

21.26.设Q是有N个存储空间的循环队列，初始状态front=rear=0，约定指针rear指向的单元始终为空，回答下列问题。(1)写出数据元素X入队的语句序列;(2)写出队首元素出队并保存到变量Y的语句序列;(3)给出计算队列长度L的表达式。

22.已知稀疏矩阵M如下，采用三元组表存储。请回答下列问题。(1)给出三元组表的类型定义。(2)画出矩阵M按行优先的三元组表。

23.将百分制成绩分成五个等级，已知成绩的对应关系及分布情况如下表所示：请根据最优二叉树的基本原理，采用类C语言，描述你所设计的成绩判定过程。

24.给定有向无环图G如题29图所示，写出G的5种不同的拓扑排序序列。

四、算法阅读题(本大题共4小题，每小题5分，共20分)

31.请写出下列程序段的输出结果。Seqstack S; //初始化栈S char x, y;X=‘L’; y=‘O’;Push(s, x); Push(S,x);Push(s, y); x=Pop(S);Push(S, ‘E’); Push(s,x);x=Pop( S ); Push(S,‘H’);while(! StackEmpty (s)) {y=Pop(S);putchar( y );}putchar( x );输出结果

32.带头结点的单链表定义如下，其中freq域记录本结点被访问的次数，初值为0，单链表始终以freq值从大到小有序。函数f31完成的功能是：查找给定关键字所在结点，若查找成功，则该结点的freq域加1，并按freq值调整结r旨位置。请将空白处(1)～(3)补充完整。在答题卡上作答。

33.阅读程序，回答下列问题。若顺序表R的元素个数n=6，关键字依次为{41，82，75，24，8，16}，则：(1)写出函数f32执行后的输出结果：(2)函数f32的功能是什么?

34.已知二叉树的二叉链表类型定义如下：typedef struct node {        char data;        struct node *lchild, *rchild;}BinTNode;typedef BinTNode * BinTree;函数f33的功能是将二叉树Bt变换为它的镜像。镜像的含义如题33图所示请将空白处(1)~(4)填写适当内容,使其完成指定功能,请在答题卡上作答。

五、算法设计题(本大题共1小题，共10分)

41.已知带头结点的单链表类型定义如下：typedef struct node {        int data;         struct node *next;} ListNode;typedef ListNode *List_ptr;请编写函数InvertList实现单链表的原地逆转。要求在原链表上进行逆转，不允许申请新的表结点空间。函数原型如下List_ptr InvertList( List_ptr head); //原地逆转单链表head