数据结构模拟试题 2
一、单项选择题(本大题共 15 小题,每小题 2 分,共 30 分)
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选
均无分。
1.下面程序段的时间复杂度为( )
s=0;
for(i=1;i<n;i++)
for(j=1;j<i;j++)
s+=i*j;
A.O(1) B.O(logn)
C.O(n) D.O(n
2
)
2.已知指针 p 和 q 分别指向某单链表中第一个结点和最后一个结点。假设指针 s 指向
另一个单链表中某个结点,则在 s 所指结点之后插入上述链表应执行的语句为( )
A.q->next=s->next;s->next=p; B.s->next=p;q->next=s->next;
C.p->next=s->next;s->next=q; D.s->next=q;p->next=s->next;
3.在计算机内实现递归算法时所需的辅助数据结构是( )
A.栈 B.队列
C.树 D.图
4.假设以数组 A[m]存放循环队列的元素。已知队列的长度为 length,指针 rear 指向队
尾元素的下一个存储位置,则队头元素所在的存储位置为( )
A.(rear-length+m+1)%m B.(rear-length+m)%m
C.(rear-length+m-1)%m D.(rear-length)%m
5.通常将链串的结点大小设置为大于 1 是为了( )
A.提高串匹配效率 B.提高存储密度
C.便于插入操作 D.便于删除操作
6.带行表的三元组表是稀疏矩阵的一种( )
A.顺序存储结构 B.链式存储结构
C.索引存储结构 D.散列存储结构
7.表头和表尾均为空表的广义表是( )
A.() B.(())
C.((())) D.((),())
8.用二叉链表表示具有 n 个结点的二叉树时,值为空的指针域的个数为( )
A.n-1 B.n
C.n+l D.2n
9.为便于判别有向图中是否存在回路,可借助于( )
A.广度优先搜索算法 B.最小生成树算法
C.最短路径算法 D.拓扑排序算法
10.连通网的最小生成树是其所有生成树中( )
A.顶点集最小的生成树 B.边集最小的生成树
C.顶点权值之和最小的生成树 D.边的权值之和最小的生成树
11.按排序过程中依据的原则分类,快速排序属于( )
A.插入类的排序方法 B.选择类的排序方法
C.交换类的排序方法 D.归并类的排序方法
12.下列关键字序列中,构成小根堆的是( )
A.{84,46,62,41,28,58,15,37}
B.{84,62,58,46,41,37,28,15}
C.{15,28,46,37,84,41,58,62}