全国2003年10月自考（课程代码：02142）数据结构导论试题
全国2003年10月高等教育自学考试
数据结构导论试题
课程代码：02142
一、单项选择题（本大题共15小题，每小题2分，共30分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1．下列说法正确的是（ ）
A．数据是数据元素的基本单位
B．数据元素是数据项中不可分割的最小标识单位
C．数据可由若干个数据元素构成
D．数据项可由若干个数据元素构成
2．数据结构的基本任务是（ ）
A．逻辑结构和存储结构的设计 B．数据结构的运算实现
C．数据结构的评价与选择 D．数据结构的设计与实现
3．在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（ ）
A．O（1） B．O（n）
C．O（nlog2n） D．O(n2)
4．顺序存储的线性表（a1,a2,…,an）,在任一结点前插入一个新结点时所需移动结点的平均次数为（ ）
A．n B．n/2
C．n+1 D．(n+1)/2
5．下列树U′，经剪技运算DELETE（U′，x，2）后为（ ）
6．一棵有16结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的双亲结点及右孩子结点的编号分别为（ ）
A．2，14 B．2，15
C．3，14 D．3，15
7．设有一5阶上三角矩阵A［1..5，1..5］，现将其上三角中的元素按列优先顺序存放在一堆数组B［1..15］中。已知B［1］的地址为100，每个元素占用2个存储单元，则A［3，4］的地址为（ ）
A．116 B．118
C．120 D．122
8．一个带权的无向连通图的最小生成树（ ）
A．有一棵或多棵 B．只有一棵
C．一定有多棵 D．可能不存在
9．下列有关图遍历的说法中不正确的是（ ）
A．连通图的深度优先搜索是一个递归过程
B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征
C．非连通图不能用深度优先搜索法
D．图的遍历要求每一顶点仅被访问一次
10．在最坏的情况下，查找成功时二叉排序树的平均查找长度（ ）
A．小于顺序表的平均查找长度 B．大于顺序表的平均查找长度
C．与顺序表的平均查找长度相同 D．无法与顺序表的平均查找长度比较
11．闭散列表中由于散列到同一个地址而引起的“堆积”现象，是由（ ）
A．同义词之间发生冲突引起的
B．非同义词之间发生冲突引起的
C．同义词之间或非同义词之间发生冲突引起的
D．散列表“溢出”引起的
12．从外存设备的观点看，存取操作的基本单位是（ ）
A．逻辑记录 B．数据元素
C．文件 D．物理记录
13．对文件进行检索操作时，每次都要从第一个记录开始的文件是（ ）
A．顺序文件 B．索引文件
C．顺序索引文件 D．散列文件
14．一组记录的键值为（46，74，18，53，14，20，40，38，86，65），利用堆排序的方法建立的初始堆为（ ）
A．（14，18，38，46，65，40，20，53，86，74）
B．（14，38，18，46，65，20，40， 53，86，74）
C．（14，18，20，38，40，46，53，65，74，86）
D．（14，86，20，38，40，46，53，65，74，18）
15．对序列（22，86，19，49，12，30，65，35，18）进行一趟排序后得到的结果如下：（18，12，19，22，49，30，65，35，86），则可以认为使用的排序方法是（ ）
A．选择排序 B．冒泡排序
C．快速排序 D．插入排序
二、填空题（本大题共13小题，每空2分，共26分）
请在每小题的空格中填上正确答案。错填、不填均无分。
16．表示逻辑关系的存储结构可以有四种方式，即顺序存储方式、链式存储方式、_______________和散列存储方式。
17．设某非空双链表，其结点形式为 若要删除指针q所指向的结点，则需执行下述语句段：q->prior->next＝q->next; _______________。
18．如图所示，设输入元素的顺序是A，B，C，D，通过栈的变换，在输出端可得到各种排列。若输出序列的第一个元素为D，则输出序列为_______________。
19．队列中允许进行删除的一端为________________。
20．设一棵二叉树中度为2的结点数为10，则该树的叶子数为________________。
21．如图所示的二叉树，若按后根遍历，则其输出序列为________________。
22．一个具有n个顶点的有向完全图的弧数为________________。
23．查找表的数据结构有别于线性表、树型结构等，其逻辑结构为________________。
24．长度为L的顺序表，采用设置岗哨方式顺序查找，若查找不成功，其查找长度为________________。
25．在开散列表上查找某元素时，通常分两步进行，首先必须计算该键值的散列地址，然后在地址指针所指________________中查找该结点。
26．文件的检索有顺序存取、________________和按关键字存取三种方式。
27．在待排序的n个记录中任取一个记录，以该记录的键值作为标准，将所有记录分为两组，使得第一组中各记录的键值均小于或等于该键值，第二组中的各记录的键值均大于该键值；然后将该记录排在两组中间。再对所分成的两组分别使用上述方法，直到所有记录都排在适当位置为止。这种排序方法称为________________。
28．在对一组记录关键字（54，38，96，23，15，72，60，45，83）进行冒泡排序时，整个冒泡排序过程中需进行________________趟才能完成。
三、应用题（本大题共5小题，共30分）
29．设有一顺序队列sq，容量为5，初始状态时sq.front=sq.rear=0，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理由后停止。（6分）
（1） d,e,b入队
（2） d,e出队
（3） i,j入队
（4） b出队
（5） n,o,p入队
30．已知无向图G的邻接矩阵如下，假设对其每行元素访问时必须从右到左，请写出从V0开始的深度优先搜索的序列。（4分）
31．画出下列二叉树的二叉链表表示图。（6分）
32．用二分查找法对一个长度为10的有序表进行查找，填写查找每一元素需要的比较次数。（8分）
33．已知序列（10，18，4，3，6，12，1，9，15，8），请给出采用二路归并排序法对该序列进行升序排序时的每一趟结果。（6分）
四、设计题（本大题共2小题，共14分）
34．设某带头结头的单链表的结点结构说明如下：
typedef struct nodel
{
int data;
struct nodel*next;
}node;
试设计一个算法：void copy(node*head l, node*head 2)，将以head 1为头指针的单链表复制到一个不带有头结点且以head2为头指针的单链表中。（6分）
35．修改冒泡排序法以实现双向冒泡排序。双向冒泡排序指第一次把最大记录放到表尾，第二次把最小记录放到表头，如此反复进行。试编写修改后的算法：void dbubble(int a[],int n)。（8分）
试题word文档下载：
数据结构导论试题
课程代码：02142
一、单项选择题（本大题共15小题，每小题2分，共30分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1．下列说法正确的是（ ）
A．数据是数据元素的基本单位
B．数据元素是数据项中不可分割的最小标识单位
C．数据可由若干个数据元素构成
D．数据项可由若干个数据元素构成
2．数据结构的基本任务是（ ）
A．逻辑结构和存储结构的设计 B．数据结构的运算实现
C．数据结构的评价与选择 D．数据结构的设计与实现
3．在一个具有n个结点的有序单链表中插入一个新结点，并使插入后仍然有序，则该操作的时间复杂性量级为（ ）
A．O（1） B．O（n）
C．O（nlog2n） D．O(n2)
4．顺序存储的线性表（a1,a2,…,an）,在任一结点前插入一个新结点时所需移动结点的平均次数为（ ）
A．n B．n/2
C．n+1 D．(n+1)/2
5．下列树U′，经剪技运算DELETE（U′，x，2）后为（ ）
6．一棵有16结点的完全二叉树，对它按层编号，则对编号为7的结点X，它的双亲结点及右孩子结点的编号分别为（ ）
A．2，14 B．2，15
C．3，14 D．3，15
7．设有一5阶上三角矩阵A［1..5，1..5］，现将其上三角中的元素按列优先顺序存放在一堆数组B［1..15］中。已知B［1］的地址为100，每个元素占用2个存储单元，则A［3，4］的地址为（ ）
A．116 B．118
C．120 D．122
8．一个带权的无向连通图的最小生成树（ ）
A．有一棵或多棵 B．只有一棵
C．一定有多棵 D．可能不存在
9．下列有关图遍历的说法中不正确的是（ ）
A．连通图的深度优先搜索是一个递归过程
B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征
C．非连通图不能用深度优先搜索法
D．图的遍历要求每一顶点仅被访问一次
10．在最坏的情况下，查找成功时二叉排序树的平均查找长度（ ）
A．小于顺序表的平均查找长度 B．大于顺序表的平均查找长度
C．与顺序表的平均查找长度相同 D．无法与顺序表的平均查找长度比较
11．闭散列表中由于散列到同一个地址而引起的“堆积”现象，是由（ ）
A．同义词之间发生冲突引起的
B．非同义词之间发生冲突引起的
C．同义词之间或非同义词之间发生冲突引起的
D．散列表“溢出”引起的
12．从外存设备的观点看，存取操作的基本单位是（ ）
A．逻辑记录 B．数据元素
C．文件 D．物理记录
13．对文件进行检索操作时，每次都要从第一个记录开始的文件是（ ）
A．顺序文件 B．索引文件
C．顺序索引文件 D．散列文件
14．一组记录的键值为（46，74，18，53，14，20，40，38，86，65），利用堆排序的方法建立的初始堆为（ ）
A．（14，18，38，46，65，40，20，53，86，74）
B．（14，38，18，46，65，20，40， 53，86，74）
C．（14，18，20，38，40，46，53，65，74，86）
D．（14，86，20，38，40，46，53，65，74，18）
15．对序列（22，86，19，49，12，30，65，35，18）进行一趟排序后得到的结果如下：（18，12，19，22，49，30，65，35，86），则可以认为使用的排序方法是（ ）
A．选择排序 B．冒泡排序
C．快速排序 D．插入排序
二、填空题（本大题共13小题，每空2分，共26分）
请在每小题的空格中填上正确答案。错填、不填均无分。
16．表示逻辑关系的存储结构可以有四种方式，即顺序存储方式、链式存储方式、_______________和散列存储方式。
| prior | data |
|
18．如图所示，设输入元素的顺序是A，B，C，D，通过栈的变换，在输出端可得到各种排列。若输出序列的第一个元素为D，则输出序列为_______________。
19．队列中允许进行删除的一端为________________。
20．设一棵二叉树中度为2的结点数为10，则该树的叶子数为________________。
21．如图所示的二叉树，若按后根遍历，则其输出序列为________________。
22．一个具有n个顶点的有向完全图的弧数为________________。
23．查找表的数据结构有别于线性表、树型结构等，其逻辑结构为________________。
24．长度为L的顺序表，采用设置岗哨方式顺序查找，若查找不成功，其查找长度为________________。
25．在开散列表上查找某元素时，通常分两步进行，首先必须计算该键值的散列地址，然后在地址指针所指________________中查找该结点。
26．文件的检索有顺序存取、________________和按关键字存取三种方式。
27．在待排序的n个记录中任取一个记录，以该记录的键值作为标准，将所有记录分为两组，使得第一组中各记录的键值均小于或等于该键值，第二组中的各记录的键值均大于该键值；然后将该记录排在两组中间。再对所分成的两组分别使用上述方法，直到所有记录都排在适当位置为止。这种排序方法称为________________。
28．在对一组记录关键字（54，38，96，23，15，72，60，45，83）进行冒泡排序时，整个冒泡排序过程中需进行________________趟才能完成。
三、应用题（本大题共5小题，共30分）
29．设有一顺序队列sq，容量为5，初始状态时sq.front=sq.rear=0，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理由后停止。（6分）
（1） d,e,b入队
（2） d,e出队
（3） i,j入队
（4） b出队
（5） n,o,p入队
30．已知无向图G的邻接矩阵如下，假设对其每行元素访问时必须从右到左，请写出从V0开始的深度优先搜索的序列。（4分）
31．画出下列二叉树的二叉链表表示图。（6分）
32．用二分查找法对一个长度为10的有序表进行查找，填写查找每一元素需要的比较次数。（8分）
| 元素下标 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
| 比较次数 |
四、设计题（本大题共2小题，共14分）
34．设某带头结头的单链表的结点结构说明如下：
typedef struct nodel
{
int data;
struct nodel*next;
}node;
试设计一个算法：void copy(node*head l, node*head 2)，将以head 1为头指针的单链表复制到一个不带有头结点且以head2为头指针的单链表中。（6分）
35．修改冒泡排序法以实现双向冒泡排序。双向冒泡排序指第一次把最大记录放到表尾，第二次把最小记录放到表头，如此反复进行。试编写修改后的算法：void dbubble(int a[],int n)。（8分）
试题word文档下载：
 |
全国2003年10月自考（课程代码：02142）数据结构导论试题.doc |