全国2005年1月自考数据结构导论试题 (清晰word版) - 自考历年真题

全国2005年1月自考数据结构导论试题 (清晰word版)(一)

2013-05-24 12:33:07 来源:91考试网作者:www.91exam.org 【大中小】

全国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

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，则其后根遍历序列为___________。