全国2005年1月自考（课程代码：02142）数据结构导论试题
全国2005年1月高等教育自学考试
数据结构导论试题
课程代码：02142
一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.数据的四种基本逻辑结构是指( )
A.数组、链表、树、图形结构 B.线性表、链表、栈队列、数组广义表
C.线性结构、链表、树、图形结构 D.集合、线性结构、树、图形结构
2.数据结构中，通常采用两种方法衡量算法的时间复杂性，即( )
A.最大时间复杂性和最小时间复杂性
B.最好时间复杂性和最坏时间复杂性
C.部分时间复杂性和总体时间复杂性
D.平均时间复杂性和最坏时间复杂性
3.下列关于线性表的叙述中，不正确的是( )
A.线性表是n个结点的有穷序列
B.线性表可以为空表
C.线性表的每一个结点有且仅有一个前趋和一个后继
D.线性表结点间的逻辑关系是1:1的联系
4.在一个单链表中，若p所指结点不是最后结点，则删除p所指结点的后继结点的正确操作是( )
A.p=p->next B.p->next=p->next
C.p->next=p->next->next D.p->next=p
5.栈和队列( )
A.共同之处在于二者都是先进先出的特殊的线性表
B.共同之处在于二者都是先进后出的特殊的线性表
C.共同之处在于二者都只允许在顶端执行删除操作
D.没有共同之处
6.二维数组A［5］［6］采用按列为主序的存储方式，每个元素占3个存储单元，若A［0］［0］的存储地址是100，则A［4］［3］的存储地址是( )
A.127 B.142
C.150 D.157
7.深度为k的二叉树至多有( )
A.2k个结点 B.2k-1个结点
C.2k-1个结点 D.2k-1-1个结点
8.对于如图所示二叉树采用中根遍历，正确的遍历序列应为( )
A.ABCDEF B.ABECDF
C.CDFBEA D.CBDAEF
9.下面关于生成树的描述中，不正确的是( )
A.生成树是树的一种表现形式
B.生成树一定是连通的
C.生成树一定不含有环
D.若生成树顶点个数为n，则其边数一定为n-1
10.图的邻接表如下所示，从顶点V1出发采用深度优先搜索法遍历该图，则可能的顶点序列
是( )
A.V1V2V3V4V5 B.V1V2V3V5V4
C.V1V4V3V5V2 D.V1V3V4V5V2
11.下列查找方法中，不属于动态的查找方法是( )
A.二叉排序树法 B.平衡树法
C.散列法 D.斐波那契查找法
12.要解决散列引起的冲突问题，常采用的方法有( )
A.数字分析法、平方取中法
B.数字分析法、线性探测法
C.二次探测法、平方取中法
D.二次探测法、链地址法
13.用于外存储器的数据组织结构散列文件，主要适用于( )
A.顺序存取 B.随机存取
C.索引存取 D.以上三种都可以
14.堆排序属于一种选择排序，其时间复杂性为( )
A.O(1) B.O(nlog2n)
C.O(n) D.O(n2)
15.下列排序方法中，属于不稳定的排序方法是( )
A.直接插入排序法 B.冒泡排序法
C.基数排序法 D.归并排序法
二、填空题(本大题共13小题，每小题2分，共26分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16.根据不同的描述方式，对数据的操作运算通常可分为加工型运算和__________两种基本
类型。
17.数据结构中的算法，通常采用最坏时间复杂度和____________两种方法衡量其效率。
18.判断带头结点head的单链表为空的条件是___________。
19.若顺序表每个元素长度均为5，其中第一个元素的存储地址为30，则第6个元素的存储地址为___________。
20.若front和rear分别表示循环队列Q的头指针和尾指针，m0表示该队列的最大容量，则判断循环队列为满的条件是___________。
21.对于顺序存储结构的二维数组，通常采用___________两种存放方式存储数据元素。
22.若某二叉树的先根遍历序列为CEDBA，中根遍历序列为DEBAC，则其后根遍历序列为___________。
23.具有n个结点的完全二叉树，其深度为___________。
24.图主要采用___________两种存储结构存放。
25.索引顺序查找通常分两个阶段进行，首先采用顺序查找法或二分法确定所要查找的块，然后再用___________法在块中找到具体的元素值。
26.二叉排序树是一种特殊的有序表，若要保证输出序列其键值完全按递增排列，则应对二叉排序树采用___________法遍历。
27.文件常见的存储结构有顺序文件、链接文件、 索引文件和___________四种。
28.在各种内部排序中，占用存储空间较大的排序通常是___________排序。
三、应用题(本大题共5小题，每小题6分，共30分)
29.已知某二叉树的顺序存储结构如图所示，试画出该二叉树。
30.试用Prim算法构造下图的最小生成树，要求分步给出构造过程
31.已知散列函数为H(key)=key%7，散列表长度为7(散列地址空间为0..6)，待散列序列为：(25，48，32，50，68)。要求：
(1)根据以上条件构造一散列表，并用线性探测法解决有关地址冲突；
(2)若要用该散列表查找元素68，给出所需的比较次数。
32.已知一组键值序列为(38，64，73，52，40，37，56，43)，试采用快速排序法对该组序列
作升序排序，并给出每一趟的排序结果。
33.已知一组键值序列(26，21，32，56，78，89，90)，试采用二路归并排序法对该组序列
作升序排序，并给出每一趟的排序结果。
四、设计题(本大题共2小题，每小题7分，共14分)
34.试编写一算法，以完成在带头结点单链表L中第i个位置前插入元素X的操作。
35.二叉树是由所有度数不大于2的结点构成的一种特定树，若某结点度为2，则该结点有左
右两个孩子，请编写算法计算一二叉树所有度数为2的结点个数。
试题文档下载：
数据结构导论试题
课程代码：02142
一、单项选择题(本大题共15小题，每小题2分，共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1.数据的四种基本逻辑结构是指( )
A.数组、链表、树、图形结构 B.线性表、链表、栈队列、数组广义表
C.线性结构、链表、树、图形结构 D.集合、线性结构、树、图形结构
2.数据结构中，通常采用两种方法衡量算法的时间复杂性，即( )
A.最大时间复杂性和最小时间复杂性
B.最好时间复杂性和最坏时间复杂性
C.部分时间复杂性和总体时间复杂性
D.平均时间复杂性和最坏时间复杂性
3.下列关于线性表的叙述中，不正确的是( )
A.线性表是n个结点的有穷序列
B.线性表可以为空表
C.线性表的每一个结点有且仅有一个前趋和一个后继
D.线性表结点间的逻辑关系是1:1的联系
4.在一个单链表中，若p所指结点不是最后结点，则删除p所指结点的后继结点的正确操作是( )
A.p=p->next B.p->next=p->next
C.p->next=p->next->next D.p->next=p
5.栈和队列( )
A.共同之处在于二者都是先进先出的特殊的线性表
B.共同之处在于二者都是先进后出的特殊的线性表
C.共同之处在于二者都只允许在顶端执行删除操作
D.没有共同之处
6.二维数组A［5］［6］采用按列为主序的存储方式，每个元素占3个存储单元，若A［0］［0］的存储地址是100，则A［4］［3］的存储地址是( )
A.127 B.142
C.150 D.157
7.深度为k的二叉树至多有( )
A.2k个结点 B.2k-1个结点
C.2k-1个结点 D.2k-1-1个结点
8.对于如图所示二叉树采用中根遍历，正确的遍历序列应为( )
A.ABCDEF B.ABECDF
C.CDFBEA D.CBDAEF
9.下面关于生成树的描述中，不正确的是( )
A.生成树是树的一种表现形式
B.生成树一定是连通的
C.生成树一定不含有环
D.若生成树顶点个数为n，则其边数一定为n-1
10.图的邻接表如下所示，从顶点V1出发采用深度优先搜索法遍历该图，则可能的顶点序列
是( )
A.V1V2V3V4V5 B.V1V2V3V5V4
C.V1V4V3V5V2 D.V1V3V4V5V2
11.下列查找方法中，不属于动态的查找方法是( )
A.二叉排序树法 B.平衡树法
C.散列法 D.斐波那契查找法
12.要解决散列引起的冲突问题，常采用的方法有( )
A.数字分析法、平方取中法
B.数字分析法、线性探测法
C.二次探测法、平方取中法
D.二次探测法、链地址法
13.用于外存储器的数据组织结构散列文件，主要适用于( )
A.顺序存取 B.随机存取
C.索引存取 D.以上三种都可以
14.堆排序属于一种选择排序，其时间复杂性为( )
A.O(1) B.O(nlog2n)
C.O(n) D.O(n2)
15.下列排序方法中，属于不稳定的排序方法是( )
A.直接插入排序法 B.冒泡排序法
C.基数排序法 D.归并排序法
二、填空题(本大题共13小题，每小题2分，共26分)
请在每小题的空格中填上正确答案。错填、不填均无分。
16.根据不同的描述方式，对数据的操作运算通常可分为加工型运算和__________两种基本
类型。
17.数据结构中的算法，通常采用最坏时间复杂度和____________两种方法衡量其效率。
18.判断带头结点head的单链表为空的条件是___________。
19.若顺序表每个元素长度均为5，其中第一个元素的存储地址为30，则第6个元素的存储地址为___________。
20.若front和rear分别表示循环队列Q的头指针和尾指针，m0表示该队列的最大容量，则判断循环队列为满的条件是___________。
21.对于顺序存储结构的二维数组，通常采用___________两种存放方式存储数据元素。
22.若某二叉树的先根遍历序列为CEDBA，中根遍历序列为DEBAC，则其后根遍历序列为___________。
23.具有n个结点的完全二叉树，其深度为___________。
24.图主要采用___________两种存储结构存放。
25.索引顺序查找通常分两个阶段进行，首先采用顺序查找法或二分法确定所要查找的块，然后再用___________法在块中找到具体的元素值。
26.二叉排序树是一种特殊的有序表，若要保证输出序列其键值完全按递增排列，则应对二叉排序树采用___________法遍历。
27.文件常见的存储结构有顺序文件、链接文件、 索引文件和___________四种。
28.在各种内部排序中，占用存储空间较大的排序通常是___________排序。
三、应用题(本大题共5小题，每小题6分，共30分)
29.已知某二叉树的顺序存储结构如图所示，试画出该二叉树。
| A | B | C | D | E | F | G |
31.已知散列函数为H(key)=key%7，散列表长度为7(散列地址空间为0..6)，待散列序列为：(25，48，32，50，68)。要求：
(1)根据以上条件构造一散列表，并用线性探测法解决有关地址冲突；
(2)若要用该散列表查找元素68，给出所需的比较次数。
32.已知一组键值序列为(38，64，73，52，40，37，56，43)，试采用快速排序法对该组序列
作升序排序，并给出每一趟的排序结果。
33.已知一组键值序列(26，21，32，56，78，89，90)，试采用二路归并排序法对该组序列
作升序排序，并给出每一趟的排序结果。
四、设计题(本大题共2小题，每小题7分，共14分)
34.试编写一算法，以完成在带头结点单链表L中第i个位置前插入元素X的操作。
35.二叉树是由所有度数不大于2的结点构成的一种特定树，若某结点度为2，则该结点有左
右两个孩子，请编写算法计算一二叉树所有度数为2的结点个数。
试题文档下载：
 |
全国2005年1月自考（课程代码：02142）数据结构导论试题.doc |