数据结构c期末考试题及答案.docVIP

数据结构c期末考试题及答案

一、单项选择题（每题2分，共10题）

1.在一个单链表中，若p所指的结点不是最后一个结点，在p之后插入s所指结点，则执行（）。

A.s-next=p;p-next=s;

B.s-next=p-next;p=s;

C.s-next=p-next;p-next=s;

D.p-next=s;s-next=p;

答案：C

2.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占1个地址空间，则a85的地址为（）。

A.33

B.32

C.13

D.40

答案：A

3.若进栈序列为1,2,3,4,5,6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（）。

A.2,3,5,1,6,4

B.3,2,5,4,1,6

C.4,3,2,1,5,6

D.2,3,4,1,6,5

答案：A

4.二叉树的前序遍历序列为ABDEGCFH，中序遍历序列为DBGEACHF，则后序遍历序列为（）。

A.DGEBHFCA

B.DGEBHACF

C.DGHEBFCA

D.ABCDEFGH

答案：A

5.对于顺序存储的线性表，其算法的时间复杂度为O(1)的运算是（）。

A.查找第i个元素

B.在第i个元素之后插入一个新元素

C.删除第i个元素

D.查找与给定值x相等的元素

答案：A

6.设无向图G=(V,E)和G=(V,E)，如果G是G的生成树，则下面说法错误的是（）。

A.G为G的连通分量

B.G是G的无环子图

C.V=V

D.E?E

答案：A

7.具有6个顶点的无向图至少应有（）条边才能确保是一个连通图。

A.5

B.6

C.7

D.8

答案：A

8.下列排序算法中，时间复杂度不受数据初始状态影响，恒为O(nlog?n)的是（）。

A.快速排序

B.冒泡排序

C.直接选择排序

D.堆排序

答案：D

9.串是一种特殊的线性表，其特殊性体现在（）。

A.可以顺序存储

B.数据元素是一个字符

C.可以链式存储

D.数据元素可以是多个字符

答案：B

10.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

A.顺序表

B.双链表

C.单循环链表

D.带头结点的双循环链表

答案：A

二、多项选择题（每题2分，共10题）

1.以下属于线性结构的有（）。

A.队列

B.栈

C.线性表

D.二叉树

E.图

答案：ABC

2.下列关于二叉树遍历的说法正确的有（）。

A.二叉树的前序遍历是先访问根结点，然后遍历左子树，最后遍历右子树

B.二叉树的中序遍历是先遍历左子树，然后访问根结点，最后遍历右子树

C.二叉树的后序遍历是先遍历左子树，然后遍历右子树，最后访问根结点

D.二叉树的层序遍历是按层次从上到下、从左到右依次访问各结点

E.二叉树的遍历顺序是固定不变的

答案：ABCD

3.下面关于图的存储结构的说法正确的有（）。

A.邻接矩阵可以表示有向图和无向图

B.邻接表适用于稀疏图的存储

C.邻接矩阵存储图时，空间复杂度为O(n2)，n为顶点个数

D.邻接表存储图时，对于无向图，边表结点数是顶点度数之和

E.图的存储结构只有邻接矩阵和邻接表两种

答案：ABCD

4.下列关于排序算法的叙述中，正确的有（）。

A.冒泡排序在最好情况下的时间复杂度为O(n)

B.快速排序在最坏情况下的时间复杂度为O(n2)

C.堆排序的时间复杂度为O(nlog?n)

D.直接插入排序在最好情况下的时间复杂度为O(n)

E.归并排序的空间复杂度为O(n)

答案：ABC

5.顺序表的特点有（）。

A.可以随机访问

B.插入和删除操作需要移动元素

C.存储空间连续

D.不需要额外的指针空间（除了存储数据的空间）

E.适合频繁插入和删除操作

答案：ABCD

6.栈的应用包括（）。

A.函数调用

B.表达式求值

C.括号匹配

D.深度优先有哪些信誉好的足球投注网站

E.队列模拟

答案：ABC

7.以下关于树