02331数据结构201410

数据结构试卷第1页共12页2014年10月高等教育自学考试全国统一命题考试数据结构试卷(课程代码02331)本试卷共8页，满分l00分。考试时间l50分钟。考生答题注意事项：1．本卷所有试题必须在答题卡上作答。答在试卷上无效，试卷空白处和背面均可作草稿纸。2．第一部分为选择题。必须对应试卷上的题号使用2B铅笔将“答题卡”的相应代码涂黑。3．第二部分为非选择题。必须注明大、小题号。使用0．5毫米黑色字迹签字笔作答。4．合理安排答题空间，超出答题区域无效。第一部分选择题一、单项选择题(本大题共l5小题，每小题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个存储空间，所有数组元素存放在一个连续的存储空间中，则该数组需要的存储空间个数是数据结构试卷第2页共12页A．80B．100C．240D．2706．广义表A=(a，(b，e，(e，f，g，h)))的表长是A．2B．3C．4D．77．设深度为k(k≥1)的二叉树中只有度为0和度为2的结点，则该二叉树中所包含的结点数至少是A．k+1B．2k+1C．2k-lD．2k8．下列选项中，可以唯一确定一棵二叉树的两种遍历序列是A．前序遍历序列和中序遍历序列B．前序遍历序列和后序遍历序列C．前序遍历序列和层次遍历序列D．后序遍历序列和层次遍历序列9．下列关于无向连通图特性的叙述中，正确的是A．边数大于顶点个数减lB．所有顶点的度之和为偶数C．度为l的顶点个数一定为偶数D．度为l的顶点个数一定为奇数10．下列关于无向图广度优先搜索序列的叙述中，正确的是A．广度优先搜索序列只有一种B．广度优先搜索序列可能不存在C．广度优先搜索序列可能有多种D．广度优先搜索序列一定有多种11．设带权连通图G中含有n(n1)个顶点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个位置，其余位置为空。现采用线性探查法数据结构试卷第3页共12页处理冲突，存储关键字85时需要探查的次数是A．2B．3C．4D．5第二部分非选择题二、填空题(本大题共l0小题，每小题2分，共20分)请在答题卡上作答。三、简答题(本大题共4小题，每小题5分。共20分)请在答题卡上作答。26．设Q是有N个存储空间的循环队列，初始状态front=rear=0，约定指针rear指向的单元始终为空，回答下列问题。(1)写出数据元素X人队的语句序列；(2)写出队首元素出队并保存到变量Y的语句序列；(3)给出计算队列长度L的表达式。27.已知稀疏矩阵M如下，采用三元组表存储。数据结构试卷第4页共12页请回答下列问题。(1)给出三元组表的类型定义。(2)画出矩阵M按行优先的三元组表。28．将百分制成绩分成五个等级，已知成绩的对应关系及分布情况如下表所示：请根据最优二叉树的基本原理，采用类C语言，描述你所设计的成绩判定过程。29．给定有向无环图G如题29图所示，写出G的5种不同的拓扑排序序列。四、算法阅读题(本大题共4小题，每小题5分。共20分)请在答题卡上作答。30．请写出下列程序段的输出结果。数据结构试卷第5页共12页31．带头结点的单链表定义如下，其中freq域记录本结点被访问的次数，初值为0，单链表始终以freq值从大到小有序。函数f3l完成的功能是：查找给定关键字所在结点，若查找成功，则该结点的freq域加l，并按freq值调整结r旨位置。请将空白处(1)～(3)补充完整。在答题卡上作答。数据结构试卷第6页共12页32．阅读程序，回答下列问题。数据结构试卷第7页共12页若顺序表R的元素个数n=6，关键字依次为{41，82，75，24，8，16}，则：(1)写出函数f32执行后的输出结果：(2)函数f32的功能是什么?数据结构试卷第8页共12页五、算法设计题(本大题共l小题，共“l0分)请在答题卡上作答。34．已知带头结点的单链表类型定义如下：数据结构试卷第9页共12页数据结构试卷第10页共12页数据结构试卷第11页共12页数据结构试卷第12页共12页