搜索
第一章绪论考点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个位置插入一个新元素的算法的时间复杂度是（）AO（0）BO（1）CO（n）DO（n*n）分析：6.顺序表的插入算法中，当n个空间已满时，可申请再增加分配m个空间。若申请失败，则说明系统没有（）可分配的存储空间。Am个Bm个连续的Cn+m个Dn+m个连续的解答：D7.简述线性表的顺序存储和链式存储的特点的比较8.对于顺序存储的线性表，设其长度为n，在任何位置上插入或删除都是等概率的。插入一个元素时大约要移动表中（）元素。An/2B(n+1)/2C(n-1)/2Dn解答A9.设顺序表的长度为n，并设从表中删除元素的概率相等。则在平均情况下，从表中删除一个元素需要移动的元素个数是（）A(n-1)/2Bn/2Cn(n-1)/2Dn(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.设计一个算法intincrease(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队列的操作方式是先进后出解答：B6.执行（）操作时，需要使用队列作为辅助存储空间A查找哈希表B广度优先搜索图C先序遍历二叉树D深度优先搜索图分析：考察上述几种操作在额外空间上的需求。查找哈希表和先序遍历二叉树不需要比较额外的空间；而深度优先搜索图则可以利用递归的方法，使用堆栈，而不使用队列作为辅助存储空间；只有广度优先搜索图需要用到队列作为辅助存储空间。解答：B考点2入栈出栈分析1.元素abcde依次进入初始为空的栈中，若元素进栈后可停留，可出栈，直到所有元素都出栈，则在所有可能的出栈序列中，以元素d开头的序列个数是：A3B4C5D6分析：该题考查堆栈的进出问题，出栈顺序必为d-c-b-a-，e的顺序不定，在任意一个“-”上都有可能。故可能以d开头的序列个数是4解答：B2.当入队序列为1、2、3时，出队序列可以是什么？当入栈序列为1、2、3时，出栈序列可以是什么？解答：出队序列为123，出栈序列可以是123,132,231,213,321考点3栈的基本操作1.利用栈求表达式的值时，设立操作数栈OPND，设OPND只有两个存储单元，在下列表达式中，不发生上溢的是：A．a-b*(c-d)B.(a-b)*c-dC.(a-b*c)-dD.(a-b)*(c-d)分析：只有B的运算顺序是依次向右，不需要暂存其他的操作数来配合运算优先顺序解答：B2.向一个栈顶指针为top的链栈中插入一个s结点，则执行：A．top-next=sBs-next=top-next;top-next=sC.s-next=top;top=sD.s-next=top;top=top-next解答：C关键考点点评：3.用不带头结点的链表表示队列，在进行删除运算时A仅修改头指针B仅修改尾指针C头尾指针都要修改D头尾指针可能都要修改解答：A4．当两个栈共享一个空间时，栈用一维数组stack（0，n-1）表示，梁栈顶指针分别为top[1]和top[2],则栈满时的条件为：分析：两个栈共享一个空间时，由于栈底是固定的且有两个，