第一章 绪论考点1 数据结构基础知识1. 数据的逻辑结构是指（），数据的存储结构是指（） 分析：数据结构包括三方面的内容：数据的逻辑结构、存储结构和数据的运算其中，逻辑结构是指各数据元素之间的逻辑关系，存储结构是指逻辑结构用计算机语言的实现 解答：数据元素之间的逻辑关系；数据的逻辑结构用计算机语言的实现2. 在数据结构中，从逻辑上可以把数据结构分为：（A）A 线性和非线性结构 B 紧凑和非紧凑结构C 动态和静态结构 D 内部和外部结构 分析：数据结构中，逻辑上可以把数据结构分成线性结构和非线性结构线性结构的顺序存储结构是一种随机存取的存储结构，线性表的链式存储结构是一种顺序存储结构线性表若采用链式存储表示时，所有结点之间的存储单元地址可连续可不连续逻辑结构与数据元素本身的形式、内容、相对位置、所含结点个数无关 关键考点点评：线性结构的特征，有且仅有一个开始结点和终端结点，所有结点最多只有一个直接前驱和后继栈和队列非线性结构的结点有多个前驱或后继，树和图3. 数据结构在物理上可以分为（）存储结构和链式存储结构分析：物理存储解答：顺序4. 下列术语中，（）与数据的存储结构无关A 循环队列 B 堆栈C 散列表 D 单链表解答 ： A5. （）不是算法所必须具备的特性A 有穷性 B 确定性C 高效性 D 可行性分析：算法的五个重要特征：有穷性、确定性、可行性、输入和输出。
解答：C考点2 时间复杂度计算1. 设n是描述问题规模的非负整数，下面程序段的时间复杂度是（） 2.第二章 线性表考点1 线性表的基本概念1. 线性表是n个（）的有限序列A 字符 B数据元素 C 由数据项 D 信息项解析：解答 B2. 线性表是一个（）A 有限序列，可以为空 B 有限序列，不能为空C 无限序列，可以为空 D 无限序列，不能为空解答 A 关键考点点评： 对于非空线性表1. 有且仅有一个开始结点，没有直接前驱，有且仅有一个直接后继；2. 有且仅有一个终结结点，没有直接后继，有且仅有一个直接前驱；3. 其余的内部结点都有且仅有一个直接前驱和后继3. 单链表不能随机存取元素原因是：要得到元素的存储地址，必须（）解答：从起始结点开始扫描以得到其地址注： 顺序表可以，但是链表不行考点2 线性表的顺序存储结构1. 下述（）是顺序存储结构的优点A 插入运算方便 B 可方便地用于各种逻辑结构的存储表示C 存储密度大 D 删除运算方便解答： C2. 线性表的（）存储结构是随机存储结构分析：随机存储结构代表可以直接访问其中的任意一个元素。
解答：顺序 关键考点点评： 顺序存储：把线性表的结点按逻辑次序依次存放在一组地址连续的存储单元里一般可以用数组实现3. 设线性表有n个元素，以下操作中，（）在顺序表上实现比在链表上实现效率更高A 输出第i个元素值 B 交换第一个第二个元素的值C 顺序输出所有元素 D 输出与给定值x相等的元素性表中的序号 解答：A4. 若某线性表最常用的操作是存取任意指定序号的元素和最后进行插入和删除运算，则利用（）存储方式最节省时间A 顺序表 B 双链表 C 带头结点的双循环链表 D 单循环链表 解答：A5. 若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度是（）A O（0） B O（1） C O（n） D O（n*n） 分析： 6. 顺序表的插入算法中，当n个空间已满时，可申请再增加分配m个空间若申请失败，则说明系统没有（）可分配的存储空间A m个 B m个连续的 C n+m个 D n+m个连续的 解答：D7. 简述线性表的顺序存储和链式存储的特点的比较8. 对于顺序存储的线性表，设其长度为n，在任何位置上插入或删除都是等概率的。
插入一个元素时大约要移动表中（）元素A n/2 B (n+1)/2 C (n-1)/2 D n 解答 A9. 设顺序表的长度为n，并设从表中删除元素的概率相等则在平均情况下，从表中删除一个元素需要移动的元素个数是（）A (n-1)/2 B n/2 C n(n-1)/2 D n(n+1)/2解答 A10. 在n个结点的线性表的数组实现中，算法的时间复杂性是O(1)的操作是：A 访问第i个结点（1<=i<=n）和求第i个结点的直接前驱(2<=i<=n)B 在第i个结点后插入一个新的结点（1<=i<=n）C 删除第i个结点（1<=i<=n）D以上都不对 解答： A11. 顺序存储的线性表A，其数据元素为整型 ，编写算法，将A拆成B和C两个表，使A中元素值大于等于0的存入B，小于0存入C要求：（1）表B和C另外设置存储空间 （2）B和C不另外设置，而利用A的空间考点3 线性表的链式存储结构1. 以下关于链式存储结构的叙述，（）是不正确的A 结点除自身信息外还包括指针域，因此存储密度小于顺序结构B 逻辑上相邻的结点物理上不必相邻C 可以通过计算直接确定i个结点的存储位置D插入删除操作方便，不必移动结点 解答：C2. 链表不具备的特点是（）A 可随机访问任一个元素 B 插入和删除时不需要移动元素C 不必事先估计存储空间 D 所需空间与线性表长度成正比分析：A是顺序表的特点，链表的元素不可以直接随机访问，一般是从链表的起始位置依次搜索得到答案：A3. 线性表可用顺序表或者链表存储，它们有什么优缺点？如果有n个表同时并存，并且在处理过程中各表的长度会动态发生变化，表得到总数也可能自动改变，在这种情况下应该选用哪种存储表示分析：考点4 单链表及其基本操作1. 对链表设置表头结点的作用是什么 解答：一般来说，设置表头结点的目的是统一空表与非空表的操作，简化链表操作的实现，而且，头结点也可以用来存储一些链表的基本信息，如链表长度等。
2. 对给定的n个元素，建立一个有序单链表的时间复杂度是：分析：在不申请额外存储空间的前提下，建立一个n元素的有序单链表是时间复杂度是O(n*n)，因为对任意一个元素，插入单链表中合适位置的开销是O(n)，对n个元素则是O(n*n)3. 将长度为n的单链表接在长度为m的单链表之后的算法的时间复杂度是： 分析：由于将长度为 n的单链表连接在长度为m的单链表之后的操作，需要把长度为m的单链表遍历一遍，找到最后一个结点，所以时间复杂度我O(m)4. 设计一个算法int increase(LinkList *L)，判定带头结点单链表L是否是递增的，若是返回1，否则返回0.5. 有一个无头结点的单链表，结点有数据域data，指针域next，表头指针为h，通过遍历链表，将链表中所有的链表方向逆转要求逆转后的链表的表头指针h指向原链表的最后一个结点算法如下请填空关键考点点评：6. 在一个单链表中，若删除p所指结点的后继结点，则执行：答案：A7. 在单向链表中p结点的后面插入新结点s，应执行语句：答案：s->next=p->next;p->next=s8.9. 已知线性表中的元素以值递增有序排列，并以单链表作为存储结构。
编写算法，删除表中所有值相同的元素，同时释放被删除的结点空间10. 设有序表以带头结点的单链表存储请设计一个函数，实现在该表内插入一个新元素的操作要求插入后，仍为有序表假定每个结点有两个域，element和link，元素为整型，link具有指向后继结点的指针类型，要求使用类型说明定义单链表结构，并实现函数11. 编写逆向输出的不带头结点的单向链表中数据域的递归算法设表中有四个结点，从表头至表尾其数据域分别为10,30,20,40作图表示出该算法的执行过程设该链表的结点的数据类型名称为list，结点的数据域和指针域的名称分别是data和next，不必写出list的定义考点5 循环链表及其基本操作1. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间A 非循环的单链表 B 仅有头指针的单循环链表C 非循环的双链表 D 仅有尾指针的单循环链表答案：D2. 有一个含头结点的单循环链表，头指针为head，则判断其是否为空的条件是：答案：head->next==head3. 设线性表非空，采用下列（）所描述的链表可以在O（1）时间内在表尾插入一个新结点。
A 带表头结点的单链表，一个链表指针指向表头结点B 带表头结点的单循环链表，一个链表指针指向表头结点C 不带表头结点的单链表，一个链表指针指向表的第一个结点D 不带表头结点的单循环链表，一个链表指针指向表的第一个结点分析：这里用O（1）时间插入的方法是，在表头结点后面插入一个新表头，然后把原来表头改成新的结点解答：B考点6 双链表及其基本操作1. N表示线性表中当前元素的数目，p表示指针的存储单元大小，E表示数据元素的存储单元大小，D表示可以在数组中存储的线性表元素的最大数目，那么使用顺序表所需空间大小为（），使用双向链表（不考虑头结点）所需空间的大小为（）分析：考察线性表存储空间的计算解答：ED，（2P+E）n2.解答：B3. 指针p指向双向链表的某个结点，在指针p所指结点之后插入s所指结点结点结构：prior-data-next，操作序列是：分析：链表中插入结点的顺序是一般先处理被插入者解答：s->prior=p;s->next=p->next;p->next->prior=s;p->next=s;考点7单链表的应用1.2.3.考点8 单循环链表的应用1. 设计一个将单循环链表逆置的算法函数考点9 其他链表及特殊算法1. 判断带头结点的双向循环链表s是否对称相等的算法如下所示，请填空。
第三章 栈和队列考点1 栈和队列的基本概念1. 判断：线性表、栈和队列的逻辑结构完全相同解答：正确2. 判断：栈和队列都是线性表，只是在插入和删除时受到一些限制分析：栈和队列是两种特殊的线性表，他们的逻辑结构与线性表相同只是其运算规则较线性表有更多的限制，故又称他们为运算受限的线性表解答：正确3. 判断：在链队列中，除了队头指针外，还必须设队尾指针，否则无法进行队列的插入操作解答：正确 关键考点点评：队列的链式存储结构简称链队列它是限制仅在表头删除和表尾插入的单链表注意：增加指向链表上的最后一个结点的尾指针，便于在表尾作插入操作4. 循环队列的优点是什么？如何判断它的空和满5. 以下的叙述中，正确的是：A线性表的线性存储结构优于链式存储结构B二维数组是其数据元素为线性表的线性表C栈的操作方式是先进先出D队列的操作方式是。