1、数据结构等级考试例题分析和习题数据结构与算法 例题分析一、选择题1数据的_包括集合、线性结构、树型结构和图状结构四种基本类型。 A)算法描述 B)基本运算 C)逻辑结构 D)存储结构 答案C 分析数据结构是数据元素之间逻辑关系的整体。根据数据元素之间关系的不同特性，数据的逻辑结构通常包括集合、线性结构、树型结构和图状结构四种基本类型。2_中任何两个结点之间都没有逻辑关系。 A)集合 B)图状结构 C)树型结构 D)线性结构 答案A 分析树型结构具有分支、层次特性，其形态有点像自然界中的树。集合中任何两个结点之间都没有逻辑关系，组织形式松散。图状结构最复杂，其中的各个结点按逻辑关系互相关联，任何
2、两个结点都可以邻接。线性结构中结点按逻辑关系依次排列形成一条“链”。3数据的存储结构包括顺序、_、索引和散列四种基本类型。 A)向量 B)数组 C)集合 D)链接 答案D 分析数据的计算机内部表示称为数据的存储结构。通常，存储结点之间有四种关联方式，称为四种基本存储方式，即：顺序存储、链式存储、索引存储和散列存储。4计算机算法指的是_。 A)计算方法 B)调度方法 C)排序方法 D)解决某一问题的有限运算序列 答案D 分析算法的定义是算法规定了求解给定类型问题所需的所有“处理方法与步骤”及其执行顺序，使得给定类型的任何问题能在有限时间内被求解，所以本题应选D。5下面_的时间复杂性最好，即执行时
3、间最短。 A)O(n) B)O(nlog2n) C)O(log2n) D)O(n3) 答案C 分析算法的时间复杂性的数量级采用大O表示，通常有常量级、对数级、线性与对数乘积级、平方级、立方级、指数级等级别，对应量级表示依次为O(1)，O(log2n)，O(n)，O(nlog2n)，O(n2)，O(n3)，O(2n)。当n较大时，量级越靠前的算法，其运行时间越短，或者说该算法效率越高。所以，上述四个选项中应选C。6把算法的工作量大小和实现算法所需的存储单元多少分别称为算法的_(1)_和_(2)_。 (1) A)可实现性 B)时间复杂度 C)困难度 D)计算有效性 (2) A)可行性 B)高效性
4、C)可实现性 D)空间复杂度 答案(1)B (2)D 分析算法的复杂性是指对一个在有限步骤内终止算法和所需存储空间大小的估计。算法的计算量是算法的时间复杂性，算法所需存储空间大小是算法的空间复杂性。7在一个长度为n的顺序表中，向第i个元素(1in+1)位置插入一个新元素时，需要从后向前依次后移_个元素。 A) n-i B) i C) n-i-1 D) n-i+l 答案D 分析线性表的插入运算是指在表的第i (1in+1)个位置上，插入一个新结点x，使长度为n的线性表变成长度为n+l的线性表。用顺序表作为线性表的存储结构时，插入算法的基本步骤是：将结点ai, ，an各后移一位以便腾出第i个位置；
5、将x置入该空位；表长加1。根据步骤可知需移动元素个数是从i到n个，即n-i+1个。8从一个长度为n的顺序表中，删除第i个元素(1in)时，需要从前向后依次向前移动_个元素。 A) i B) n-i C) n-i-1 D) n-i+l 答案B 分析线性表的删除运算是指将表的第i (1in)个结点删去，使长度为n的线性表变成长度为n-1的线性表。若i=n，则只要简单地删除终端结点，无需移动结点：若1in-1，则必须将表中位置i+l，i+2，n上的结点依次前移到位置i，i+l，n-1上，以填补删除操作造成的空缺。所以，当1in - 1时，需要向前移动的元素个数是从i+l到n个，即n-i个。当i=n时
6、，移动元素个数为n-i。9对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的，插入一个元素时平均移动表中的_个元素。 A) n/2 B) (n-1)2 C) (n+1)2 D) n 答案A 分析在顺序表中，插入操作可在第1，2，n，n+1个位置上进行，它们对应的移动表中元素的个数分别是n，n-1，1，0，它们的和为s=n(n+1)2。在任何位置上插入或删除操作都是等概率时，插入一个元素平均要移动元素个数为 sn+1个，即n/2个。10在一个长度为n的线性表中顺序查找值为x的元素时，在等概率情况下，查找成功时的平均查找长度_。 A)n/2 B) (n-1)2 C) (n+1
7、)2 D)n 答案C 分析在长度为n的顺序表中，共有n个元素，若x等于顺序表中第1，2，n个位置上的元素时，对应的查找长度分别为1，2，n，它们的和szn(n+1)2。在等概率的情况下，查找成功时的平均查找长度为sn，即(n+1)2。11单链表要求内存中可用存储单元的地址 。 A)必须是连续的 B)一定是不连续的 C)部分地址必须是连续的 D)可以是连续的，也可以是不连续的 答案D 分析单链表的结点由数据域和指针(链)域两部分组成。数据域用于存储线性表的一个数据元素。指针域(链域)用于存放一个指针，该指针指向本结点的直接后继结点。单链表就是通过指针来表示结点间的逻辑关系而不是通过结点在存储单元
8、中的位置来表示，所以存储单元地址是否连续并不重要。12在单链表中，头指针的作用是_。 A)方便运算的实现 B)用于标识单链表 C)使单链表中至少有一个结点 D)用于标识首结点位置 答案B 分析单链表通常设置头指针变量head，该变量的值是指向单链表的第一个结点的指针，称为头指针。单链表的每一个结点都被一个指针所指，并且任何结点也只能通过指向它的指针才能引用。因此，对单链表中任一结点的访问必须首先根据头指针变量中存放的头指针找到第一个结点，再按有关各结点链域中存放的指针顺序往下找，直到找到所需的结点。由此可见，头指针变量具有标识单链表的作用。13在一个单链表中，若要删除p指针所指向结点的后继结点
9、，则执行_。 A)p-next=p B)p=p-next-next C)p-next=p-next-next D)p=p-next；p-next=p-next-next 答案C 分析假设q为p指针所指向的结点的后继结点，则q=p-next，若要删除q，应将q的链域q-next的值传给p指针的链域p-next，即p-next=p-next-next。14在一个头指针为ph的单链表中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行_操作。 A)p-next=q-next；q=p B)p-next=q-next；q-next=p C)q-next=p-next；p-next=q D)
10、q-next=p-next；p-next=q-next 答案B 分析若要在指针q所指结点的后面插入一个由指针p所指向的结点，应将结点p的链域p-next指向结点q的后继结点(q-next)；将结点q的链域q-next改为指向结点po相应的操作为p-next=q-next：q-next=p。15若某链表最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用_存储方式最节省时间。 A)单链表 B)双链表 C)单循环链表 D)带头结点的双循环链表 答案D 分析在单链表中，无论是在最后一个结点之后插入一个结点，还是删除最后一个结点，都必须首先从头指针开始顺序往下找，直至到达最后一个结点
11、时才进行插入或删除操作。所以，采用这种存储方式的插入和删除操作并不方便。双链表、单循环链表与单链表一样，插入、删除操作都不方便。在上述选项中，只有带头结点的双循环链表可以通过头结点的链域ptior迅速地找到链表的最后一个结点，以便进行插入、删除操作。故采用带头结点的双循环链表存储方式最节省时间。 B)s-prior=p； s-next=p-next； p-next=S； p-next-prior=S； D)s-prior=p； s-next=p-next； p-next-prior=S； p-next=S；16在循环双链表的p结点之后插入s结点的操作是_。 A)p-next=S； p-next
12、-prior=S； s-prior=p； s-next=p-next； C)p-next=S； s-prior=p； p-next-prior=S； s-next=p-next； 答案D 分析对于A选项，p-next指向的是p所指结点的后继结点，执行第一条语句后，s所指结点变为p所指结点的后继结点，造成p所指结点原来的后继结点丢失。故选项A不正确。对于选项B，错误发生在第三、四条语句，第三条语句将s所指结点指定为p所指结点的后继结点，而第四条语句又将p所指结点的后继结点即s所指结点的直接前趋结点定义为s，前后冲突。故选项B也不正确。选项C与选项A的错误类似。只有D选项正确。17采用链接方式存储
13、线性表的优点是_。 A)便于随机存取 B)花费的存储空间较顺序存储少 C)便于插入和删除操作 D)数据元素的物理顺序和逻辑顺序相同 答案C 分析在链表上，对实现读表元运算必须对表结点进行扫描，其时间复杂度为O(n)，故选项A不对。而插入和删除操作可通过修改链域的指针来完成，无须移动其他有关结点，这是链表的一个优点。故选项C正确。选项B和D用来描述链表不正确。链表是通过指针来反映数据元素间的逻辑关系，因此，链表中数据元素的物理顺序与逻辑顺序可以不相同，但链表花费的存储空间比顺序存储多。18栈的插入和删除操作在_进行。 A)栈底 B)栈顶 C)指定位置 D)任意位置 答案B 分析栈可以看成是一种“
14、特殊的”线性表，这种线性表上的插入和删除运算限定在表的某一端进行。允许进行插入和删除的这一端称为栈顶，另一端称为栈底。所以，选项B正确。19在下面栈的基本运算中，不是加工型运算的是_。 A)初始化 B)进栈 C)退栈 D)判栈空 答案D 分析选项A初始化：加工型运算，其作用是设置一个空栈S。选项B进栈：加工型运算，其作用是将元素x插入栈S中，使x成为栈S的栈顶元素。选项C退栈：加工型运算，其作用是当栈不空时，取栈顶元素，并从栈中删除当前栈顶元素。选项D判栈空：引用型运算，功能是若栈S为空栈，则结果为真；否则结果为假。20实现递归调用属于_的应用。 A)栈 B)数组 C)队列 D)二叉树 答案A
15、 分析栈是一种应用范围广泛的数据结构，适用于各种具有“后进先出”特性的问题。递归是一个重要的概念，同时也是一种重要的程序设计方法。简单地说，如果在一个函数或数据结构的定义中又应用了它自身，那么这个函数或数据结构称为是递归定义的，简称递归。应用栈与递归之间的关系，可以解决很多实际问题，如计算一个数的阶乘。 21在顺序栈中进行退栈操作时，_。 A)谁先谁后都可以 B)先移动栈顶指针，后取出元素 C)不分先后，同时进行 D)先取出元素，后移动栈顶指针 答案D 分析在栈中进行退栈操作被称为删除栈顶元素运算。退栈操作的步骤是先要将栈顶元素取出，由参数返回，并将栈顶下标减1。22假定利用数组an顺序存储一
16、个栈，用top表示栈顶指针，用top=n+l表示栈空，该数组所能存储的栈的最大长度为n，则表示栈满的条件是_。 A)top = -1 B)top = 0 C)top l D)top = 1 答案D 分析栈空是指栈中不含任何数据元素，栈满是指栈中没有任何的空闲空间。根据本题的假设栈顶指针top=n+l表示栈空，可知，该数组将栈底放在下标大的那端，它的下界为1，上界为n，当top=n时存入第一个元素，因为该数组所能存储的栈的最大长度为n，所以，栈满时栈顶指针top应等于1。23假设一个栈的输入序列为A，B，C，D，E，则下列序列中不可能是栈的输出序列的是_。 A)B，C，D，A，E B)E，D，A
17、，C，B C)B，C，A，D，E D)A，E，D，C，B 答案B 分析用1为进栈操作，0为出栈操作。对选项A、选项C、选项D选项的输出序列可以分别通过1101010010、1101001010、1011110000操作序列得到。而对于B选项的输出序列，第一个输出元素是E，可知先执行了11111操作，因为栈是后进先出的，所以在输出A之前，必须要输出C，B。故选项B不可能是栈的输出序列。24在一个顺序存储的循环队列中，队头指针指向队头元素的_。 A)当前位置 B)任意位置 C)前一个位置 D)后一个位置 答案C 分析循环队列的队头指针指示队头元素在数组中实际位置的前一个位置，队尾指针指示队尾元素在
18、数组中的实际位置。所以，选项C正确。25在由n个单元组成的顺序存储的循环队列sq中，假定f和r分别为队头指针和队尾指针，则判断队满的条件是_。 A)f = (r十1)n B) (r-1)n = f C)f = r D) (f+1)n = r 答案A 分析在由n个单元组成的循环队列sq中，因为出队和入队分别要将头指针f和尾指针r在循环意义下加1，所以某一元素出队后，若头指针已从前面追上尾指针，即sq-f = sq-r，则当前队列为空：若某一元素入队后，尾指针已从后面追上头指针，即sq-r = sq-f，则当前队列为满。可见，仅凭等式sq-r = sq-f是无法区别循环队列是空还是满的。为了区分队
19、空、队满的条件，采用下面的方法：入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为是队满，即判别队满的条件是：(sq-r+1)n = sq-f。从而也保证了sq-r = sq-f是队空的判别条件。注意：队满条件使得循环队列中，始终有一个元素的空间(即队头指针指示的结点)是空的，即有n个单元组成的循环队列只能表示长度不超过n-1的队列。26设循环队列中数组的下标范围是1n，其头尾指针分别为f和r，则其元素个数为_。 A) r-f B) r-f+l C) (r-f) mod (n+1) D) (r-f+n) mod n 答案D 分析因为队头指针指示的结点不用于存储队列元素，只起标志作
20、用。所以，当rf时，队内元素个数为(r-f) mod n；当rf时，队内元素个数为 (n-(f-r) mod n，综合上述情况，队内元素个数为 (n-f/r) mod n。27树最适合于表示_。 A)有序数据元素 B)无序数据元素 C)元素之间无联系的数据 D)元素之间具有分支层次关系的数据 答案D 分析树是一种“分支层次”结构。所谓“分支”是指树中任一结点的子孙可以按它们所在的子树的不同而划分成不同的“分支”；所谓“层次”是指树上所有结点可以按它们的层数划分成不同的“层次”。所以说树最适合于表示元素之间具有分支层次关系的数据。28由3个结点可以构造出多少种不同的二叉树_。 A)3 B)4 C
21、)5 D)6 答案C 分析二叉树是结点的有穷集合，它或者是空集或者同时满足下述两个条件： 有且仅有一个称为根的结点； 其余结点分为两个互不相交的集合T1、T2，n与T2都是二叉树，并且T1与T2有顺序关系(T1在T2之前)，它们分别称为根的左子树和右子树。 由上述二叉树的定义可知，可以根据子树的位置不同划分出不同二叉树。有3个结点可以构造出5种不同的二叉树，如图119所示。 图119 由3个结点构造出的二叉树类型29在一棵深度为k的完全二叉树中，所含结点个数不小于_。 A)2k B)2k+1 C)2k-1 D)2k-1 答案D 分析若一棵二叉树至多只有最下面的两层上结点的度数可以小于2，并且最
22、下一层上的结点都集中在该层最左边的若干位置上，则此二叉树称为完全二叉树。最下一层只含一个结点时的完全二叉树所含结点个数最小。此时除最下一层以外的结点构成一棵深度为k-1的满二叉树，含结点数为2 k-l -l。再加上最下一层的结点得出深度为k的完全二叉树含结点个数的最小值2 k-1。30在有n个结点的二叉链表中，值为非空的链域的个数为_。 A)n-1 B)n+l C)2n-1 D)2n+l 答案A 分析二叉链表的结点形式如下：LchildDataRchild 其中，data域称为数据域，用于存储二叉树结点中的数据元素；lchild域称为左孩子指针域，用于存放指向本结点左孩子的指针；rchild域
23、称为右孩子指针域，用于存放指向本结点右孩子的指针。二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是指向该结点的一个孩子的指针，或者是空指针NULL。 从二叉链表的结构可推断出，二叉链表的每个结点(除根结点外)和非空链域是一一对应的关系。所以，本题应选A选项。31在下列存储形式中，_不是树的存储形式。 A)双亲表示法 B)顺序存储表示 C)孩子兄弟表示法 D)孩子链表表示法 答案D 分析孩子链表表示法、双亲表示法、孩子兄弟表示法是树的三种常用存储结构。 孩子链表表示法是树的一种链式存储结构。与二叉树的二叉链表存储方法类似，孩子链表表示法的基本思想是：树上的一个结点的内容(数据元素)以
24、及指向该结点所有孩子的指针存储在一起以便于运算的实现。 双亲表示法是树上每个结点的孩子可以有任意多个，但双亲只有一个。因此，通过指向双亲的指针而将树中所有结点组织在一起形成一种存储结构是十分简洁的。树的这种存储表示方法称为双亲表示法。 孩子兄弟链表中所有存储结点的形式相同，均含三个域：数据域用于存储树上结点中的数据元素；孩子域用于存放指向本结点第一个孩子的指针；兄弟域用于存放指向本结点下一个兄弟的指针。32若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素的平均查找长度为_。 A) n B) n+l C) (n-1)2 D) (n+1)2 答案D 分析对于含有n个元素的表，顺序查找的
25、平均查找长度为： ASL = nPl + (n-1) P2 + +2Pn-1 +Pn 当每个元素的查找概率相等，即Pi = ln，则顺序查找的平均查找长度为：ASL = (n+1)2。33对长度为4的顺序表进行查找，若第一个元素的概率为18，第二个元素的概率为14，第三个元素的概率为38，第四个元素的概率为14，则查找任一元素的平均查找长度为_。 A)118 B)74 C)94 D)114 答案C 分析对顺序表进行查找，并求任一元素的概率使用公式： ASL = P i C i =P i (n-i+1) 代入原题中的数据得：ASL = 4(18) +3(14) +2(38)+1(14) = 94
26、。34对于长度为n的顺序存储的有序表，若采用二分查找法，则对所有元素的最长查找长度为_的值向下取整再加1。 A) log 2 (n+1) B) n2 C) log 2 n D) (n+1)2 答案C 分析二分查找法在查找成功时进行比较的关键字的个数最多不超过树的深度，而具有n个结点的判定树的深度为log 2 n的值向下取整加1，所以，二分查找法在查找成功时和给定值进行比较的关键字个数至多为log 2 n的值向下取整加1。35对于长度为8的顺序存储结构的有序表，若采用二分查找法查找，在等概率的情况下的平均查找长度为_的值除以8。 A)17 B)19 C)21 D)20 答案B 分析当每个记录的查
27、找概率相等，则二分查找法的平均查找长度为： ASL = (n+1)/2log 2 (n+1) - 1，又因为log 2 8=3，代入公式即可。所以本题的ASL的值为198。36线性表进行二分查找法查找，其前提条件是_。 A)线性表以顺序方式存储，并且按关键码值排好序 B)线性表以链式方式存储，并且按关键码值排好序 C)线性表以顺序方式存储，并且按关键码的检索频率排好序 D)线性表以链式方式存储，并且按关键码的检索频率排好序 答案A 分析二分查找法只适用于有序表，且限于顺序存储结构，对线性链表无法进行二分查找法查找。而顺序结构存储其顺序是按关键码值排好序的。37若对n个元素进行直接插入排序，则进
28、行第i趟排序过程前，有序表中的元素个数为_。 A)1 B)i-1 C)i D)i+l 答案C 分析在直接排序的操作中，当i=l时，排序实际上是一个空操作。所以，操作的过程从i=2开始，当进行第i趟操作时，有序表中已经有i个元素了。38若对n个元素进行直接插入排序，在进行第i趟排序时，假定元素ri+1的插入位置为rj，则需要移动的元素的次数为_。 A) j-i B) i-1 C) i-j-1 D) i-j+1 答案D 分析当第ri+1元素插入位置rj时，两者之间位置相差的个数为i+l-j。所以，在位置j后面的每个元素就都要向后移动一位，次数为i-j+1。39在对n个元素进行冒泡排序的过程中，第一
29、趟排序至多需要进行_对相邻元素之间的交换。 A) n2 B) n-1 C) n D) n+l 答案B 分析本题要求至多需要的次数。分析可知，当第一个需要比较的元素为该待排序列中关键字最大的元素时，进行元素交换的次数最多，即n-1次。40在对n个元素进行快速排序的过程中，平均情况下的空间复杂性为_。 A)O(1) B)O(n2) C)O(log 2 n) D)O(n log 2 n) 答案D 分析在快速排序的非递归算法中，可引进一个栈。这个栈的大小由递归调用的深度决定，最多不会超过n，如果每次都要选较大的部分进栈，处理较短的部分，深度最多不超过log 2 n。也就是说，快速排序需要的附加存储开销为O(log 2 n)。可以证明平均比较次数是O(n log 2 n)。41以下四种排序方法中，需要附加的内存空间最大的是_。 A)插入排序 B)选择排序 C)快度排序 D)归并排序 答案D 分析插入排序只需要一个记录的辅助空间，空间复杂度为O(1)；选择排序需要用一个辅助数组存放指向各个记录的指针，空间复杂度大于插入排序；快速排序的平均比较次数为O(n log 2 n)；
