数据结构 (第 4 版）习题及实验参考答案
数据结构复习资料完整版
数据结构基础及深入及考试
复习资料
习题及实验参考答案见附录
结论
1、数据的逻辑结构是指数据元素之间的逻辑关系。    即从逻辑关系上描述数据，    它与数据
的存储无关，是独立于计算机的。
2、数据的物理结构亦称存储结构，    是数据的逻辑结构在计算机存储器内的表示    （或映像）。
它依赖于计算机。存储结构可分为    4 大类：顺序、链式、索引、散列
3、抽象数据类型：由用户定义， 用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作） 。它与数据类型实质上是一个概念，但其特征是使
用与实现分离，实行封装和信息隐蔽（独立于计算机）    。
4、算法：是对特定问题求解步骤的一种描述，    它是指令的有限序列，是一系列输入转换
为输出的计算步骤。
5、在数据结构中，从逻辑上可以把数据结构分成（    C    ）
A 、动态结构和表态结构    B 、紧凑结构和非紧凑结构
C、线性结构和非线性结构    D 、内部结构和外部结构
6、算法的时间复杂度取决于（    A    ）
A 、问题的规模    B 、待处理数据的初态    C、问题的规模和待处理数据的初态
线性表
1、线性表的存储结构包括顺序存储结构和链式存储结构两种。
2、表长为  n 的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，
插入一个元素所需移动元素的平均次数为（    E    ），删除一个元素需要移动的元素的个数
为（    A    ）。
A 、(n-1)/2    B、 n    C、 n+1    D 、n-1    E、n/2    F、 (n+1)/2    G、 (n-2)/2
3、“线性表的逻辑顺序与存储顺序总是一致的。    ”这个结论是（    B    ）
A 、正确的    B、错误的    C、不一定，与具体的结构有关
4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（    D    ）
A 、必须是连续的    B、部分地址必须是连续的    C 一定是不连续的    D 连续或不连续都可
以
5、带头结点的单链表为    空的判定条件是（    B    ）
A 、head==NULL    B 、 head->next==NULL    C、 head->next=head    D、 head!=NULL
6、不带头结点的单链表    head 为空的判定条件是（    A    ）
A 、head==NULL    B、 head->next==NULL    C、 head->next=head    D 、 head!=NULL
7、非空的循环单链表    head 的尾结点  P 满足（    C    ）
A 、p->next==NULL    B 、p==NULL    C、 p->next==head    D 、 p==head
8 、在一个具有    n  个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是
（ B  ）
A 、O(1)    数据结构与算法题库B、 O(n)    C、 O(n2)    D、 O(nlog 2n)

1

数据结构 (第 4 版）习题及实验参考答案
数据结构复习资料完整版
9、在一个单链表中，若删除    p 所指结点的后继结点，则执行（    A    ）
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;
10、在一个单链表中，若在    p 所指结点之后插入    s 所指结点，则执行（    B ）
A 、 s->next=p;p->next=s;
B 、 s->next=p->next;p->next=s;
C 、s->next=p->next;p=s;
D 、p->next=s;s->next=p;
11、在一个单链表中， 已知 q 是 p 的前趋结点， 若在 q 和 p 之间插入结点    s，则执行（  C    ）
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;
12、在线性结构中，第一个结点    没有    前趋结点，其余每个结点有且只有    1    个
前趋结点。
栈和队列
1、在栈操作中，输入序列为（    A ，B ， C， D），不可能得到的输出数列是（    D    ）
A 、（A ，B，C，D）    B、（D，C，B，A ）
C、（A ，C，D ， B）    D、（ C， A ， D， B ）
2、设栈  ST 用顺序存储结构表示，则栈    ST 为空的条件（    B    ）
A 、 ST.top=ST.base<>0    B 、 ST.top=ST.base==0
C、 ST.top=ST.base<>n    D 、 ST.top=ST.base==n
3、向一个栈顶指针为    HS 的链栈中插入一个    s 结点时，执行（    C    ）
A 、HS->next=s;    B 、 s->next=HS->next;HS->next=s;
C、 s->next=HS;HS=S;    D、 s->next=HS;HS=HS->next;
4、从一个栈顶指针为    HS 的链栈中删除一个结点，用    x 保存被删结点的值，则执行（    C ）
A 、x=HS;HS=HS->next;    B、 HS=HS->next;x=HS->data;
C、 x=HS->data;HS=HS->next;    D、 s->next=HS;HS=HS->next;
5、用单链表表示的链示队列的队头在链表的（    A    ）位置。
A 、链头    B、链尾    C、链中
6、判定一个链队列Ｑ（最多元素个数为    n）为空的条件是（    A    ）
Ａ、Ｑ .front==Q.rear    B、 Q.front!=Q.rear
C、Q.front==(Q.rear+1)%n    D 、 Q.front!=(Q.rear+1)%n
7、在链队列Ｑ中，插入要所指结点需顺序执行的指令是（    B    ）
A 、Q.front->next=s;f=s;
B、 Q.rear->next=ar=s;
C、 s->ar=s;
D 、s->next=Q.front;Q.front=s;
8、在一个链队列    Q 中，删除一个结点需要执行的指令是（    C    ）
A 、 Q.rear=Q.front->next;
B 、 Q.rear->ar->next->next;

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。