数据结构全国2014年4月高等教育自学考试
全国2014年4月高等教育自学考试
一、单项选择题(本大题共15小题，每小题2分，共30分)
2023年国家公务员报名人数统计1.下列几种算法时间复杂度中，最小的是
A.O(log2n)
B.O(n)
C.O(n2)2022四六级登录入口
D.O(1)
2.数据的存储方式中除了顺序存储方式和链式存储方式之外，还有
A.索引存储方式和树形存储方式吉林大学考研成绩查询
B.线性存储方式和散列存储方式
C.线性存储方式和索引存储方式
D.索引存储方式和散列存储方式
3.表长为n的顺序表中做删除运算的平均时间复杂度为
A.O(1)
B.O(log2n)
C.O(n)
D.O(n2)
4.顺序表中定位算法(查值为x的结点序号最小值)的平均时间复杂度为
A.O(1)
B.O(log2n)
C.O(n)
D.O(n2)
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个
2021国家公务员考试行测
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(nlog2n)
C.O(n2)
D.O(1og2n)
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用邻接矩阵，1..n]存储，其第i列的所有元素之和等于顶点V i的_________。
25.具有10个顶点的有向完全图的弧数为_________。
26.要完全避免散列所产生的“堆积’’现象，通常采用_________解决冲突。
27.在长度为n的带有岗哨的顺序表中进行顺序查，查不成功时，与关键字的比较次数为_________。
28.归并排序算法的时间复杂度是_________。
三、应用题(本大题共5小题，每小题6分，共30分)
29.稀疏矩阵A如题29图所示，写出该稀疏矩阵A的三元组表示法。