内容发布更新时间 : 2024/5/2 19:33:04星期一 下面是文章的全部内容请认真阅读。

**

新年快乐 数据结构习题

习题2

2.1选择题

（1）线性表是具有n个 __________的有限序列（n!=0）。 A.表元素 B.字符 C.数据元素 D.数据项

（2）顺序表的存储结构是一种__________的存储结构。 A.随机存取 B.顺序存取 C.索引存取 D.HASH存取

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

A.n-i B.n-i+1 C.n-i-1 D.i

(4)链表是一种采用____________存储结构存储的线性表。 A.顺序 B链式 C.星式 D.网状

（5）下面关于线性表的叙述错误的是_____________。 A.线性表采用顺序存储方式，必须占用一片连续的存储空间 B.线性表采用链式存储方式，不必占用一片连续的存储空间 C.线性表采用链式存储方式，便于插入和删除操作的实现 D.线性表采用顺序存储方式，便于插入和删除操作的实现

（6）设某链表中最常用的操作是在链表的尾部插入或删除元素，则选用____________存储方式最节省运算时间。

A.单项链表 B.单向循环链表 C.双向链表 D.双向循环链表

(7)设指针q指向单链表中的结点A，指针p指向单链表中的结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B之间插入结点X的操作序列为____________。 A.s->next=p->next; p->next=-s; B.q->next=s; s->next=p; C.p->next=s->next; s->next=p; D.p->next=s; s->next=q;

(8)设指针变量p指向单链表结点A，则删除结点A的后继结点B的操作为___________。 A.p->next=p->next->next B.P=P->next C.p=p->next->next D.P->next=p

(9)在一个以h为头的单循环链表中，p指针指向链尾的条件是__________. A.P->next=h B.p->next=NULL C.p->next->next=h D.p->data=-1

(10)对于只在首尾两端进行插入操作的线性表，宜采用的存储结构为___________。 A.顺序表 B.用头指针表示的单循环链表 C.单链表 D.用尾指针表示的单循环链表 2.2填空题

（1）线性表是n个元素的_____________________________。 （2）线性表的存储结构有______________________________。

（3）设线性表中有n个数据元素，则在顺序存储结构上实现顺序查找的平均时间复杂度为___________________，在链式存储结构上实现顺序查找的平均时间复杂度为

**

**

___________________。

（4）设顺序线性表中有n个数据元素，则第i个位置上插入一个数据元素需要移动表中___________个数据元素；删除第i个位置上的数据元素需要移动表中___________个元素。 （5）若频繁地对线性表进行插入与删除操作，该线性表应采用_________________存储结构。 （6）链式存储结构中的结点包含________________域和_________________域。

（7）在双链表中，每个结点有两个指针域，一个指向____________，另一个指向_______________。

（8）对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为______________，在表尾插入时间的复杂度为_________________。

（9）设指针变量p指向单链表中的结点A，指针s指向被插入结点B，则在结点A的后面插入结点B的操作序列为_________________________________________________。

（10）设指针变量p指向单链表中的结点A，则删除结点A的后继结点（假设存在）的语句序列我为：

S=p->next; p->next=___________________；free(s)；

习题2参考答案 2.1选择题

(1). C. (2). B. (3). B. (4). B. 5. D. 6. B. 7. B. 8. A. 9. A. 10. D. 2.2.填空题 (1). 有限序列

(2). 顺序存储和链式存储 (3). Ｏ(n) O(n) (4). n-i+1 n-i (5). 链式

(6). 数据 指针 (7). 前驱 后继 (8). Ο(1) Ο(n)

(9). s->next=p->next; p->next=s ; (10). s->next

习题三 3.1选择题

1）下列说法正确的是（）

A.堆栈是在两端操作、先进后出的线性表 B.堆栈是在一端操作、先进先出的线性表 C.队列是在一端操作、先进先出的线性表 D.队列是在两端操作、先进先出的线性表 2）栈和队列的共同点是（） A.都是先进先出 B.都是先进先出

C.只允许在端点出插入和删除元素 D.没有共同点

3）以下数据结构中（）是非线性结构。 A.队列

**

**

B.栈 C.线性表 D.二叉树

4）若一个栈的入栈序列是1，2,3，，n。其输出序列为p1,p2,p3,?pn,,,p1=n,则pi为（） ?A. I B. N-i C. N-i+1 D. 不确定

5）当利用大小为N的一位素组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。 A.top++ B.Top-- C.Top=0 D.Top

6）4个元素s栈的顺序是A,B,C,D,经运算，pop(s)后栈顶元素是（） A. A B. B C. C D.D

7)一个栈的输入序列是a，b，c，d，e，则栈的不可能的输出序列是（） A. adcba B. decba C. dceab D. abcde 8)设输入序列是1,2,3，?n，经过栈的作用后输出序列的第一个元素是n，则输出序列中第i个输出元素是（） A.n-i B.n-1-i C.n+1-i D.不能确定

9）字符A、B、C、D依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成（）个不同的字符串

A.15 B.14 C.16 D.21

10)递归函数f(n)=f(n-1)+n(n>1)的递归出口是（） A.f(1)=0 B.f(1)=1 C.f(0)=1 D.f(n)=n

11)设指针变量top指向当前链式栈的栈顶，则删除栈顶的元素的操作序列为（） A.top=top+1 B.top=top-1

C.top->next=top D.top = top->next 12)中缀表达式A-(B+C/D)*E的后缀表达式是（） A.ABC+D/*E- B.ABCD/+E*- C.AB-C+D/E* D.ABC-+D/E*

13)用front和rear分别表示顺序循环队列的队首和队尾指针，判断队空的条件是（） A.front+1==rear B.(rear+1)%maxsize == front C.front==0 D.front==rear

14)判定一个循环队列QU（最多元素为m0）为满队列的条件是（） A.QU->front==QU->rear B.QU->front!=QU->rear

**