数据结构--第1-4章选择题(有-答案)

第1章绪论5．选择题（1）在数据结构中，从逻辑上可以把数据结构分成（）。A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构（2）与数据元素本身的形式、内容、相对位置、个数无关的是数据的（）。A．存储结构B．存储实现C．逻辑结构D．运算实现（3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（）。A．数据具有同一特点B．不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C．每个数据元素都一样D．数据元素所包含的数据项的个数要相等（4）以下说法正确的是（）。A．数据元素是数据的最小单位B．数据项是数据的基本单位C．数据结构是带有结构的各数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构说明：注意几个概念：数据项是数据的最小单位而不是基本单位，数据元素才是数据的基本单位，数据结构是带有结构的数据元素的集合而不是数据项的集合。（5）以下与数据的存储结构无关的术语是（）。A．顺序队列B.链表C.有序表D.链栈说明：数据的存储结构只有数组（或称为顺序存储）和链表两种。顺序队列是用数组存储的队列，链表和链栈都是用链表。（6）以下数据结构中，（）是非线性数据结构A．树B．字符串C．队D．栈第2章线性表1．选择题（1）一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。A．110B．108C．100D．120说明：计算公式：A+(i-1)*L，A为起始地址，i是元素序号，L是元素长度。（2）在n个结点的顺序表中，算法的时间复杂度是O(1)的操作是（）。A．访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）B．在第i个结点后插入一个新结点（1≤i≤n）C．删除第i个结点（1≤i≤n）D．将n个结点从小到大排序（3）向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动的元素个数为（）。A．8B．63.5C．63D．7说明：n个元素的顺序表共有n+1个插入位置（包括一头一尾），在第i个位置插入元素需要移动n-i+1个元素，因此平均为(1+2+…+n)/(n+1)=n/2。（4）链接存储的存储结构所占存储空间（）。A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数（5）线性表若采用链式存储结构时，要求内存中可用存储单元的地址（）。A．必须是连续的B．部分地址必须是连续的C．一定是不连续的D．连续或不连续都可以（6）线性表Ｌ在（）情况下适用于使用链式结构实现。A．需经常修改Ｌ中的结点值Ｂ．需不断对Ｌ进行删除插入C．Ｌ中含有大量的结点Ｄ．Ｌ中结点结构复杂（7）单链表的存储密度（）。A．大于1B．等于1C．小于1D．不能确定说明：存储密度的定义在课本p41表2.1的末尾，它是小于或等于1的一个实数。（8）将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（）。A．nB．2n-1C．2nD．n-1说明：合并两个有序表的算法见课本算法2.15和算法2.16。当两个表中的一个完全排在另一个表的前面时，比较的次数最少，此时只是后面表中的第一个元素与前面表中的元素逐一比较一次，然后就直接将两个表连接起来。（9）在一个长度为n的顺序表中，在第i个元素（1≤i≤n+1）之前插入一个新元素时须向后移动（）个元素。A．n-iB．n-i+1C．n-i-1D．i(10)线性表L=(a1，a2,……an)，下列说法正确的是（）。A．每个元素都有一个直接前驱和一个直接后继B．线性表中至少有一个元素C．表中诸元素的排列必须是由小到大或由大到小D．除第一个和最后一个元素外，其余每个元素都有一个且仅有一个直接前驱和直接后继。(11)若指定有n个元素的向量，则建立一个有序单链表的时间复杂性的量级是（）。A．O(1)B．O(n)C．O(n2)D．O(nlog2n)说明：这道题其实有些问题。若题目的意思是，有n个元素，事先我们不知道元素的大小次序，我们依此将这些元素一个个插入单链表中并且使得单链表有序。注意这是单链表，第8章的一些快速排序算法在这里用不上。因为是单链表，每次插入一个元素，只能从表头开始逐一比较，寻找插入的位置。在最坏的情况下，需要比较n(n-1)/2次，时间复杂性为O(n2)。但平均却是O(n)。如果n个元素事先已存在单链表中，现在对其排序，则可采用类似“冒泡排序”或“简单选择排序”那样的算法，时间复杂性为O(n2)。(12)以下说法错误的是（）。A．求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B．顺序存储的线性表可以随机存取C．由于顺序存储要求连续的存储区域，所以在存储管理上不够灵活D．线性表的链式存储结构优于顺序存储结构(13)在单链表中，要将s所指结点插入到p所指结点之后，其语句应为（）。A．s-next=p+1;p-next=s;B．(*p).next=s;(*s).next=(*p).next;C．s-next=p-next;p-next=s-next;D．s-next=p-next;p-next=s;(14)在双向链表存储结构中，删除p所指的结点时须修改指针（）。A．p-next-prior=p-prior;p-prior-next=p-next;B．p-next=p-next-next;p-next-prior=p;C．p-prior-next=p;p-prior=p-prior-prior;D．p-prior=p-next-next;p-next=p-prior-prior;(15)在双向循环链表中，在p指针所指的结点后插入q所指向的新结点，其修改指针的操作是（）。A．p-next=q;q-prior=p;p-next-prior=q;q-next=q;B．p-next=q;p-next-prior=q;q-prior=p;q-next=p-next;C．q-prior=p;q-next=p-next;p-next-prior=q;p-next=q;D．q-prior=p;q-next=p-next;p-next=q;p-next-prior=q;说明：对于（13）、（14）、（15）这类题，在草稿纸上画一画链表就明白了。要注意的是，按语句次序，一旦修改了某根指针，就要删掉原来的指针。第3章栈和队列1．选择题（1）若让元素1，2，3，4，5依次进栈，则出栈次序不可能出现（）的情况。A．5,4,3,2,1B．2,1,5,4,3C．4,3,1,2,5D．2,3,5,4,1（2）若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。A．iB．n-iC．n-i+1D．不确定说明：p1=n表明全部元素入栈之后才出栈，因此出栈序列只能是n,n-1,…,2,1,第i个出栈的必为n-i+1。（3）数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素个数的公式为（）。A．r-fB．(n+f-r)%nC．n+r-fD．（n+r-f)%n说明：当用数组表示循环队列时，f、r是数组元素的下脚标。由于是循环的，所以有可能rf。若rf，则r-f即为队列的元素个数；当rf时，必须按(n+r-f)%n计算。注意当rf时，(n+r-f)%n=(r-f)%n=r-f。（4）链式栈结点为：(data,link)，top指向栈顶.若想摘除栈顶结点，并将删除结点的值保存到x中,则应执行操作（）。A．x=top-data;top=top-link；B．top=top-link;x=top-link；C．x=top;top=top-link；D．x=top-link；说明：链栈是一个单链表，表头为栈顶，见课本p47图3.3。（5）设有一个递归算法如下intfact(intn){//n大于等于0if(n=0)return1;elsereturnn*fact(n-1);}则计算fact(n)需要调用该函数的次数为（）。A．n+1B．n-1C．nD．n+2说明：可观察函数的参数，它将依次为n,n-1,…,1,0，共n+1个。（6）栈在（）中有所应用。A．递归调用B．函数调用C．表达式求值D．前三个选项都有必须指出，递归调用使用的是系统堆栈，不是应用程序设计的栈。（7）为解决计算机主机与打印机间速度不匹配问题，通常设一个打印数据缓冲区。主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（）。A．队列B．栈C．线性表D．有序表（8）设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次进入栈S，一个元素出栈后即进入Q，若6个元素出队的序列是e2、e4、e3、e6、e5和e1，则栈S的容量至少应该是（）。A．2B．3C．4D．6说明：由于一个元素出栈后即进入队列，而队列是“先进先出”，所以出队的序列就是出栈的序列。（9）在一个具有n个单元的顺序栈中，假设以地址高端作为栈底，以top作为栈顶指针，则当作进栈处理时，top的变化为（）。A．top不变B．top=0C．top--D．top++（10）设计一个判别表达式中左，右括号是否配对出现的算法，采用（）数据结构最佳。A．线性表的顺序存储结构B．队列C.线性表的链式存储结构D.栈（11）用链接方式存储的队列，在进行删除运算时（）。A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改说明：题目的意思是，用单链表实现队列，头指针指向第一个元素结点（首元结点），不使用头结点。不然的话，象课本p65图3.13的情形，删除操作只可能修改头结点中的指针，头指针永远不变。由于队列是“先进先出”的，所以删除的一定是队列第一个元素，当队列元素只剩一个时，删除后需同时修改头、尾指针。（12）循环队列存储在数组A[0..m]中，则入队时的操作为（）。A.rear=rear+1B.rear=(rear+1)%(m-1)C.rear=(rear+1)%mD.rear=(rear+1)%(m+1)说明：数组长度是m+1而不是m。（13）最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是（）。A.(rear+1)%n==frontB.rear==frontC．rear+1==frontD.(rear-l)%n==front说明：题目指的是课本p63图3.11所示的循环队列。（14）栈和队列的共同点是（）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点说明：栈的“端点”是栈顶，队列的“端点”是队头。（15）一个递归算法必须包括（）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分说明：“迭代”是循环的另一种说法。第4章串、数组和广义表1．选择题（1）串是一种特殊的线性表，其特殊性体现在（）。A．可以顺序存储B．数据元素是一个字符C．可以链式存储D．数据元素可以是多个字符（2）下面关于串的的叙述中，（）是不正确的？A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储（3）串“ababaaababaa”的next数组为（）。A．012345678999B．012121111212C．011234223456D．0123012322345（4）串“ababaabab”的nextval为（）。A．010104101B．010102101C．010100011D．010101011（5）串的长度是指（）。A．串中所含不同字母的个数B．串中所含字符的个数C．串中所含不同字符