数据结构基础及深入及考试

复习资料

习题及实验参考答案见附录

结论

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(nlog2n)

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=s;Q.rear=s; C、s->next=Q.rear;Q.rear=s; D、s->next=Q.front;Q.front=s;

8、在一个链队列Q中，删除一个结点需要执行的指令是（ C ） A、Q.rear=Q.front->next;

B、Q.rear->next=Q.rear->next->next;

C、Q.front->next=Q.front->next->next; D、Q.front=Q.rear->next;

9、栈和队列的共同点（ C ） A、都是先进后出 B、都是先进先出

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

10、栈的特点是_先进后出，队列的特点是先进先出

11、线性表、栈和队列都是线性结构，可以在线性表的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入元素和在队首删除元素。

串和数组

1、设串s1=’ABCDEFG’，s2=’PQRST’，函数Concat(x,y)返回x和y串的连接串，Substr(s,I,j)返回串s从序号i开始的j个字符组成的子串，length(s)返回串s的长度，则Concat(Substr(s1,2, length(s2), Substr(s1,length(s2),2))的结果串是（ D ）

A、BCDEF B、BCDEFG C、BCPQRST D、BCDEFEF 2、串是一种特殊的线性表，其特殊性体现在（ D ） A、可以顺序存储 B、数据元素是一个字符 C、可以链接存储 D、数据元素可以是多个字符

3、设有两个串p和q，求q在p中首次出现的位置的运算称作（ B ） A、连接 B、模式匹配 C、求子串联 D、求串长 4、串的两种最基本的存储方式是顺序存储方式和链接存储方式。

树和二叉树

1、树最合适用来表示（ B ）

A、有序数据元素 B、元素之间具有分支层次关系的数据 C、无序数据元素 D、元素之间无联系的数据

2、按照二叉树的定义，具有3个结点的二叉树有（ C ）种。 A、3 B、4 C、5 D、6

3、在一棵有n个结点的二叉树中，若度为2的结点数为n2，度为1的结点数为n1，度为0的结点数为n0，则树的最大高度为（ E ），其叶结点数为（ G ）；树的最小高度为（ B ），其叶结点数为（ G ）；若采用链表存储结构，则有（ I ）个空链域。

A、n/2 B、[log2n]+1 C、log2n D、n E、n0 + n1 + n2 F、n1 + n2 G、n2 +1 H、1 I、n+1 J、n1 K、n2 L、n1 +1 4、在一棵二叉树上第5层的结点数最多为（ B ）。（假设根结点的层数为0） A、8 B、16 C、15 D、32

5、深度为5的二叉树至多有（ C ）个结点。 A、16 B、32 C、31 D、10

6、在一非空二叉树的中序遍历序列中，根结点的右边（ A ） A、只有右子树上的所有结点 B、只有右子树上的部分结点 C、只有左子树上的部分结点 D、只有左子树上的所有结点

7、一棵完全二叉树按层次遍历的序列为ABCDEFGHI，则在先序遍历中结点E的直接前趋为（ D ），后序遍历中结点B的直接后继是（ E ）。