全国2014年4月高等教育自学考试
数据结构导论试题
课程代码:02142
一、单项选择题(本大题共15小题,每小题2分,共30分)
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将“答题纸”的相应代码涂黑。错涂、多涂或未涂均无分。
1.下列几种算法时间复杂度中,最小的是
A.O(log
2n) B.O(n)
C.O(n
2) D.O(1)
2.数据的存储方式中除了顺序存储方式和链式存储方式之外,还有
A.索引存储方式和树形存储方式 B.线性存储方式和散列存储方式
C.线性存储方式和索引存储方式 D.索引存储方式和散列存储方式
3.表长为n的顺序表中做删除运算的平均时间复杂度为
A.O(1) B.O(log
2n)
C.O(n) D.O(n
2)
4.顺序表中定位算法(查找值为x的结点序号最小值)的平均时间复杂度为
A.O(1) B.O(log
2n)
C.O(n) D.O(n
2)
5.元素的进栈次序为A,B,C,D,E,出栈的第一个元素为E,则第四个出栈的元素为
A.D B.C
C.B D.A
6.带头结点的链队列中,队列头和队列尾指针分别为front和rear,则判断队列空的条件为
A.front==rear B.front!=NULL
C.rear!==NULL D.front==NULL
7.深度为5的二叉树,结点个数最多为
A.31个 B.32个
C.63个 D.64个
8.如果结点A有2个兄弟结点,结点B为A的双亲,则B的度为
A.1 B.3
C.4 D.5
9.将题9图所示的一棵树转换为二叉树,结点C是
A.A的左孩子
B.A的右孩子
C.B的右孩子
D.E的右孩子
10.n为图的顶点个数,e为图中弧的数目,则图的拓扑排序算法的时间复杂度为
A.O(n) B.O(e)
C.O(n-e) D.O(n+e)
11.无向图的邻接矩阵是
A.对角矩阵 B.稀疏矩阵
C.上三角矩阵 D.对称矩阵
12.在具有101个元素的顺序表中查找值为x的元素结点时,平均比较元素的次数为
A.50 B.51
C.100 D.101
13.构造散列函数的方法很多,常用的构造方法有
A.数字分析法、除留余数法、平方取中法
B.线性探测法、二次探测法、除留余数法
C.线性探测法、除留余数法、链地址法
D.线性探测法、二次探测法、链地址法
14.就平均时间性能而言,快速排序方法最佳,其时间复杂度为
A.O(n) B.O(nlog
2n)
C.O(n
2) D.O(1og
2n)
15.下述算法中,不稳定的排序算法是
A.直接插入排序 B.冒泡排序
C.堆排序 D.归并排序
二、填空题(本大题共13小题,每小题2分,共26分)
16.数据的基本单位是_________。
17.双向循环链表中,在p所指结点的后面插入一个新结点*t,需要修改四个指针,分别为
t->prior=P;t->next=p->next;_________;p->next=t;。
18.在带有头结点的循环链表中,尾指针为rear,判断指针P所指结点为首结点的条件是_________。
19.若线性表中最常用的操作是求表长和读表元素,则顺序表和链表这两种存储方式中,较节省时间的是_________。
20.不含任何数据元素的栈称为_________。
21.稀疏矩阵一般采用的压缩存储方法是_________。
22.100个结点的二叉树采用二叉链表存储时,用来指向左、右孩子结点的指针域有_________个。
23.已知完全二叉树的第5层有5个结点,则整个完全二叉树有_________个结点。
24.n个顶点的有向图G用邻接矩阵A[1..n,1..n]存储,其第i列的所有元素之和等于顶点
V
i的_________。
25.具有10个顶点的有向完全图的弧数为_________。
26.要完全避免散列所产生的“堆积’’现象,通常采用_________解决冲突。
27.在长度为n的带有岗哨的顺序表中进行顺序查找,查找不成功时,与关键字的比较次数为_________。
28.归并排序算法的时间复杂度是_________。
三、应用题(本大题共5小题,每小题6分,共30分)
29.稀疏矩阵A如题29图所示,写出该稀疏矩阵A的三元组表示法。
30.设二叉树的中序遍历序列为BDCEAFHG,后序遍历序列为DECBHGFA,试画出该二叉树。
31.写出题31图所示无向图的邻接矩阵,并写出每个顶点的度。
题31图
32.已知散列表的地址空间为0至13,散列函数H(k)=kmod11,(mod为求余运算),待散列序列为(26,61,38,84,49),用二次探测法解决冲突,构造该序列的散列表,要求写出处理冲突的过程。
33.将一组键值(80,50,65,13,86,35,96,57,39,79,59,15)应用二路归并排序算法从小到大排序,试写出各趟的结果。
四、算法设计题(本大题共2小题,每小题7分,共14分)
34.设单链表及链栈S的结构定义如下:
typedef struct node
{ Data Type data;
struct node*next;
}linkstack;
编写一个算法void ReverseList(1inkstack *head),借助于栈S将带头结点单链表head中序号为奇数的结点逆置,序号为偶数的结点保持不变。(例如:单链表的逻辑结构为(a
1,a
2,a
3,a
4,a
5,a
6),逆置后变为(a
5,a
2,a
3,a
4,a
1,a
6))。
说明:栈的初始化运算用InitStack(S);进栈运算用Push(S,x);判栈空运算用EmptyStack(S);出栈运算用Pop(S);取栈顶元素运算用Gettop(S)。
35.以二叉链表作为存储结构,试编写递归算法实现求二叉树中叶子结点个数。
自考试题下载: