02331数据结构10Word格式.docx

02331数据结构10Word格式.docx

《02331数据结构10Word格式.docx》由会员分享，可在线阅读，更多相关《02331数据结构10Word格式.docx（11页珍藏版）》请在冰点文库上搜索。

必须对应试卷上的题号使用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个存储空间，所有数组元素存放

在一个连续的存储空间中，则该数组需要的存储空间个数是

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

6．广义表A=（a，（b，e，（e，f，g，h）））的表长是

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

7．设深度为k（k≥1）的二叉树中只有度为0和度为2的结点，则该二叉树中所包含的结

点数至少是

A．k+1B．2k+1C．2k-lD．2k

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

A．前序遍历序列和中序遍历序列B．前序遍历序列和后序遍历序列

C．前序遍历序列和层次遍历序列D．后序遍历序列和层次遍历序列

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

A．边数大于顶点个数减lB．所有顶点的度之和为偶数

C．度为l的顶点个数一定为偶数D．度为l的顶点个数一定为奇数

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．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如下，采用三元组表存储。

请回答下列问题。

（1）给出三元组表的类型定义。

（2）画出矩阵M按行优先的三元组表。

28．将百分制成绩分成五个等级，已知成绩的对应关系及分布情况如下表所示：

请根据最优二叉树的基本原理，采用类C语言，描述你所设计的成绩判定过程。

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

四、算法阅读题（本大题共4小题，每小题5分。

30．请写出下列程序段的输出结果。

31．带头结点的单链表定义如下，其中freq域记录本结点被访问的次数，初值为0，单链表始终以freq值从大到小有序。

函数f3l完成的功能是：

查找给定关键字所在结点，若查找成功，则该结点的freq域加l，并按freq值调整结r旨位置。

请将空白处

（1）～（3）补充完整。

在答题卡上作答。

32．阅读程序，回答下列问题。

若顺序表R的元素个数n=6，关键字依次为{41，82，75，24，8，16}，则：

（1）写出函数f32执行后的输出结果：

（2）函数f32的功能是什么?

五、算法设计题（本大题共l小题，共“l0分）

34．已知带头结点的单链表类型定义如下：