数据结构练习题及答案

一、单选题

1 以下叙述正确的是( )。

A. 在顺序存储的线性表中，逻辑上相邻的两个数据元素在物理上并不一定相邻 B. 链式存储的线性表可以随机存取 C. 顺序存储的线性表可以随机存取

D. 在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数仅于该元素的位置有关

2 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为( )。（1≦i ≦n+1）

A. O(0) B. O(1) C. O(n) D.O(n)

3 若某线性表中最常用的操作是取第i个元素和删除最后一个元素，则采用（ ）存储方式最节省时间。

A. 顺序表 B. 单链表 C. 双链表 D. 单循环链表 4 带头结点的单链表head为空的判断条件是( )。

A. head==NULL B. head->next==NULL C. head->next==head D. head!=NULL

5 在单链表中增加头结点（在教材中称为哨位结点）的目的是为了( )。 A. 方便运算的实现 B. 用于标识单链表

C. 使单链表中至少有一个结点 D. 用于标识起始结点的位置 6 将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为( )。 A. O(1) B. O(n) C. O(m) D. O(n+m)

7 若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用( )存储方式最节省时间。

A. 单链表 B. 双链表 C. 带头结点的双循环链表 D. 单循环链表 8.单链表的存储密度（ ）。

A.大于1 B.等于1 C.小于1 D.不能确定 9 非空的循环单链表head的尾结点（由p指针所指）满足( )。 A. p->next==NULL B. p==NULL C. p->next==head D. p=head

10 在一个单链表中，已知(*q)结点是(*p)结点的前驱结点，若在(*q)和(*p)之间插入(*s) 结点,则执行( )。

A. s->next=p->next ; p->next=s ; B. p->next=s->next ; s->next=p ; C. q->next=s ; s->next=p ; D. p->next=s ; s->next=q ;

2

11 在一个单链表中，若删除(*p)结点的后继结点，则执行( )。 A. p->next=p->next->next ;

B. p=p->next; p->next=p->next->next ; C. p->next=p->next ; D. p =p->next->next ;

12 循环链表的主要优点是（ ）。 A. 不在需要头指针了

B. 已知某个结点的位置后，能容易找到它的直接前驱 C. 走进行插入、删除运算时，能更好地保证链表不断开 D. 从表中任一结点出发都能扫描到整个链表

13 向具有n个不同元素的链表中插入一个数据元素，最坏情况下需访问几个元素？ A. n B. n/2 C. 1 D. n/3 14．数组A[5][6]的每个元素占5个单元，将其按行优先顺序存储在起始地址为 1000的连续的存储单元中，则元素A[4][5]的地址为（ ）。 A. 1140 B. 1145 C. 1120 D. 1125

15．求字符串T在字符串S中首次出现的位置的操作称为( )。 A. 串的模式匹配 B. 求子串 C. 求串的长度 D. 串的连接

16.如下陈述中正确的是( )。 A.串是一种特殊的线性表 B.串的长度必须大于零 C.串中元素只能是字母 D.空串就是空白串

17．稀疏矩阵一般的压缩存储方法有两种，即( ) A. 二维数组和三维数组 B．三元组和散列 C．三元组和十字链表 D．散列和十字链表 18．栈和队列都是（ ）

A.顺序存储的线性表 B.链式存储的线性表 C.限制存取点的线性结构 D.限制存取点的非线性结构

19.若已知一个栈的输入序列为1,2,3,4,……,n，其输出序列p1, p2, …..,pn。若p1＝n,则pi为 ( )。

A.i B.n-i C.n-i+1 D.不确定

20．假设以数组A[m]存放循环队列的元素，其头、尾指针分别为front和rear,则当前队列中的元素个数为( )。

A. (rear – front + m) % m B. rear – front + 1 C. (front – rear + m) % m D. (rear – front) % m 21．对稀疏矩阵进行压缩存储是为了（ ）

A. 便于进行矩阵运算 B. 便于输入和输出 C. 节省存储空间 D. 降低运算的时间复杂度 22．串是（ ）

A. 一些符号构成的序列 B. 一些字母构成的序列 C. 一个以上字符构成的序列 D. 任意有限个字符构成的序列 23. 栈和队列的主要区别在于 ( )。

A. 它们的逻辑结构不一样 B. 它们的存储结构不一样 C. 所包含的运算个数不一样 D. 插入删除运算的限定不一样 二、填空题：

1 一个算法的运算时间函数为T（n）=1000，则其大O表示的运算时间是 。 2 非顺序映象的特点是借助 表示数据元素之间的逻辑关系。

3 在一个长度为n的顺序存储的线性表中，向第i个元素（1<=i<=n+1）之前插入一个新元素时需向后移动 元素。

4 在一个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可用p表示为head= 。 5 下面程序段的时间复杂度是___ ___。 for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) a[i][j]=0;

6 按顺序存储方法存储的线性表称为_______ ， 按链式存储方法存储的线性表称为_______。

7 顺序表相对于链表的优点有_________ 和_ ________ 。

8 在n个结点的顺序表中插入一个结点需平均移动______ 个结点，具体移动次数取决于 __ ___ ___ 。

9 在n个结点的顺序表中删除一个结点需平均移动___ ___ 个结点，具体移动次数取决于 __ ____ __ 。

10 在n个结点的单链表中要删除p指结点，需找到_ __ ，其时间复杂度为_ ____ 。

11 双链表中每个结点有两个指针域，一个指向 __ ，另一个指向_ _ ___ 。 12 顺序表的存储密度为 而链表的存储密度为 。

13 循环队列的引入，目的是为了克服 。 14 在串S=“structure”中，以t为首字符的子串有 个。 答案： 一、单选题

二、填空题：

本文来源：https://www.bwwdw.com/article/w494.html