数据结构复习材料(包含全部规范标准答案).doc

-数据结构习题集（自编）第一章 绪论一、选择题1数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的（）和运算的学科。 A结构 B关系 C运算 D算法2在数据结构中，从逻辑上可以把数据结构分成（）。A动态结构和静态结构 B紧凑结构和非紧凑结构C线性结构和非线性结构 D逻辑结构和存储结构3线性表的逻辑顺序和存储顺序总是一致的，这种说法（）。 A正确 B不正确 C无法确定 D以上答案都不对4算法分析的目的是（）。A找出算法的合理性 B研究算法的输人与输出关系C分析算法的有效性以求改进 D分析算法的易懂性5. 算法的时间复杂度取决于（ ）A问题的规模B待处理数据的初态 C. A和B6一个算法应该是（ ）。A程序 B问题求解步骤的描述 C要满足五个基本特性 DA和C. 7. 下面关于算法说法错误的是（ ）A算法最终必须由计算机程序实现B.为解决某问题的算法与为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的8以下与数据的存储结构无关的术语是（ ）。A循环队列 B. 链表 C. 哈希表 D. 栈9在下面的程序段中，对x的赋值语句的频度为（ ）for（i=0;i<n;i+） for(j=0;j<n;j+) x=x+1;A 2n Bn Cn2 Dlog2n 10以下数据结构中，（ ）是非线性数据结构A树 B字符串 C队列 D栈11. 下列数据中，（ ）是线性数据结构。A哈夫曼树 B.有向无环图 C. 二叉排序树 D. 栈12以下属于逻辑结构的是（ ）。A顺序表 B. 哈希表 C.有序表 D. 单链表二、填空题1、_是信息的载体，是对客观事物的符号表示，它能够被计算机识别、存储、加工和处理，_是对能够有效的输人到计算机中并且能够被计算机处理的符号的总称。（数据、数据） 2、数据元素是数据的_，有些情况下也称为元素、结点、顶点、记录等。（基本单位）3、_是数据不可分割的最小单元，是具有独立含义的最小标识单位。例如构成一个数据元素的字段、域、属性等都可称之为_。（数据项、数据项） 4、数据的逻辑结构是指数据之间的_。逻辑结构是从_上描述数据，它与具体存储无关，是独立于计算机的。因此逻辑结构可以看作是从具体问题抽象出来的_。（逻辑关系、逻辑关系、数学模型） 5、数据的_指数据元素及其关系在计算机存储器内的表示。_是逻辑结构在计算机里的实现，也称之为映像。（存储结构、存储结构） 6、数据逻辑结构可以分为四种基本的类型，_结构中的元素除了仅仅只是同属于一个_，不存在什么关系。（集合、集合） 7、数据逻辑结构的四种基本类型中，_中的元素是一种一对一的关系，这种结构的特征是：若结构是非空集，则有且只有一个开始结点和一个终端结点，并且所有结点最多只能有一个直接前驱和一个直接后继。（线性结构） 8、数据逻辑结构的四种基本类型中，_中的元素是一种一对多的关系。（树形结构） 9、图型结构或图状结构是一种_的关系。在这种逻辑结构中，所有结点均可以有多个前驱和多个后继。（多对多） 10、有时也可将树型结构、集合和图型结构称为_，这样数据的逻辑结构就可以分为_和_两大类。（非线性结构、线性结构、非线性机构） 11、_方式是指逻辑上相邻的结点被存储到物理上也相邻的存储单元中。这种存储结构只存储结点的数值，不存储结点之间的关系，结点之间的关系是通过存储单元的相邻关系隐含的表示出来的。（顺序存储） 12、_方式是种存储方法，不要求逻辑上相邻的结点在物理上也相邻，即数据元素可以存储在任意的位置上。（链式存储） 13、_方式是利用结点关键字的值直接计算出该结点存储单元地址，然后将结点按某种方式存人该地址的一种方法。（散列存储或哈希存储） 14、所谓算法（Algorithm）是对特定问题求解步骤的一种描述，它是指令的其中每个指令表示一个或多个操作。算法的五个重要特性是_、_、_、_和_。（有限序列、有穷性、确定性、可行性、输入、输出）15、算法的_性是指算法必须能够在执行有限个步骤之后结束，并且每个步骤都必须在有穷的时间内完成。（有穷性） 16、算法的_性是指算法中的每一个步骤必须是有明确定义的，不允许有模棱两可的解释，也不允许有多义性。并且，在任何条件下，算法只能有惟一的一条执行路径，即只要输人是相同的就只能得到_的输出结果。（确定性、相同） 17、算法的_性又称为算法的能行性，是指算法中描述的操作是可以通过已经实现的基本运算执行有限次来实现。（可行性） 18、判断一个算法的好坏主要以下几个标准：_、_、_、_。（正确性、可读性、健壮性、时间效率和空间效率） 19、算法分析是对一种算法所消耗的计算机资源的估算，其中包括计算机_的长短和_的大小。（运行时间、所占据空间） 20、空间复杂度（SPace ComPlexity）也是度量一个算法好坏的标准，它所描述的是算法在运行过程中所占用_的大小。（存储空间）三、判断题 1顺序存储方式只能用于存储线性结构。（） 2数据元素是数据的最小单位。（） 3算法的优劣与算法描述语言无关，但与所用计算机有关。() 4健壮的算法不会因非法的输入数据而出现莫名其妙的状态。()5数据的逻辑结构是指各元素之间的逻辑关系，是根据用户需要而建立的。 6数据结构、数据元素、数据项在计算机中的映像分别称为存储结构、结点、数据域。（） 7数据的物理结构是指数据在计算机中实际的存储形式。（） 8具有存取任一元素的时间相等这一特点的存储结构称为随机存取结构。9算法实际上就是程序，程序也一定是算法。()10. 在顺序存储结构中，有时也存储数据结构中元素之间的关系。()11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()12. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。()13. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。 ()14. 判断一个算法的好坏主要以下几个标准：正确性、有穷性、健壮性和可行性。()15算法的时间复杂度T（n）=O(f(n)表示随问题规模n的增大，算法执行时间的增长率与函数f(n)的增长率相同。（）四、综合题 1用大O形式表示下面算法的时间复杂度： for（i=0；im；i十十） for（j=0；jn；j） Aij=i*j； 2写出下面算法的时间复杂度： i0； s=0； while(sn） i+; s+=i; 3写出以下算法的时间复杂度： for（i0; im; i）for（j0 ; jt; j） cij=0；for（i=0；im；i） for（j=o; j<t; j+） for（k=0；kn；k） cijaik*bkj;4写出下面算法的时间复杂度：i=1;while（in） i=i*3;5求下面函数中各条语句的频度和算法的时间复杂度：prime（int n） int i2； while (ni）！=0isqrt(n) ) i+; if（isqrt(n) ) printf（”d is a prime number.n”，n）； else printf（”d is not a prime number.n”，n）；1. 该算法的时间复杂度为：O(mn)。2. 该算法的时间复杂度为：O()3. 该算法的时间复杂度为：O(mnt)。4. 该算法的时间复杂度为：log3(n)。5. 该算法的时间复杂度为：O()。6将下列函数，按它们在n时的无穷大阶数，从小到大排序。 n, n-n3+7n5, nlogn, 2n/2, n3, logn, n1/2+logn, (3/2)n, ,n!, n2+logn从小到大排列为：logn, n1/2+logn, n, nlogn, n2+logn，n3, n-n3+7n5, 2n/2, (3/2)n, n!,第二章 线性表一、选择题 1在一个长度为n的顺序表中删除第i个元素（0<i<=n）时，需要向前移动( )个元素。 An-i Bn-i+1 Cn-i-1 Di+12从一个具有n个元素的线性表中查找其值等于x的结点时，在查找成功的情况下，需平均比较( )个元素结点。 An/2 Bn C(n-1)/2 D(n +1)/2 3对一个具有n个元素的线性表，建立其单链表的时间复杂度为( )。 AO(n) BO(1) CO(n2） DO（long2n） 4线性表采用链式存储时，其地址( )。 A 必须是连续的 B一定是不连续的 C部分地址必须连续 D连续与否均可以 5在一个具有n个结点的有序单链表中插人一个新的结点，使得链表仍然有序，该算法的时间复杂度是( )。 AO（long2n） BO（l） CO（n2） DO（n）6线性表是( )。 A一个有限序列，可以为空 B一个有限序列，不可以为空 C一个无限序列，可以为空 D一个无限序列，不可以为空7在一个长度为n的顺序表中，向第i个位置（0一1n1）插入一个新元素时，需要向后移动( )个元素。 An-i Bn-i1 Cni1 Di18如果某链表中最常用的操作是取第i个结点及其前驱，则采用( )存储方式最节省时间。 A单链表 B双向链表 C单循环链表 D顺序表9一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（）。 A98 B100 C102 D10610在顺序存储的线性表（a1an）中，删除任意一个结点所需移动结点的平均移动次数为( ) An Bn2 C(n-1)/2 D（nl）/211在线性表的下列存储结构中，读取第i个元素花费的时间最少的是（）。 A单链表 B双链表 C循环链表 D顺序表12若某链表中最常用的操作为在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方式最节省时间。 A双链表 B单链表 C单循环链表 D带头结点的双循环链表13在单链表中删除指针p所指结点的后继结点，则执行（ ）操作。Ap->next=p->next->nextBp->next=p->nextCp=p->next->nextDp=p->next;p->next=p->next->next14在一个单链表中，已知q所指结点是p所指结点的前驱，若在q和p之间插入s所指的结点，则执行（ ）操作。As->next=p->next;p->next=s;Bq->next=s;s->next=p;Cp->next=s->next;s->next=p;Dp->next=s;s->next=q;15在单链表中附加头结点的目的是为了（ ）。A保证单链表中至少有一个节点B标识单链表中首结点的位置C方便运算的实现D说明单链表是线性表的链式存储16循环单链表的主要优点是（ ）。A不再需要头指针了B从表中任意一个结点出发都能扫描到整个链表C已知某个结点的位置后，能够容易找到它的前驱D在进行插入、删除操作时，能更好地保证链表不断开17非空的循环单链表L的尾结点p满足（ ）。Ap->next=NULLBp=NULLCp->next=LDp=L18在双向循环链表中,在p指针所指向的结点前插入一个指针q所指向的新结点,其修改指针的操作是( )。注:双向链表的结点结构为(prior,data,next)。 供选择的答案：Ap->prior=q； q->next=p； p->prior->next=q； q->prior=q；Bp->prior=q； p->prior->next=q; q->next=p； q->prior=p->prior；Cq->next=p；q->prior=p->prior；p->prior->next=q; p->prior=q;Dq->prior=p->prior； q->next=p； p->prior=q；p->prior=q；19在双向链表存储结构中，删除p所指的结点时须修改指针（ ）。Ap->prior->next=p->next; p->next->prior=p->prior;Bp->prior=p->prior->prior; p->prior->next=p;(删p的前趋)Cp->next->prior=p; p->next=p->next->next;Dp->next= p->prior->prior; p->prior= p->next->next;二、填空题1线性表（Linear List）是最简单、最常用的一种数据结构。线性表中的元素存在着_的相互关系。（一对一）2线性表中有且仅有一个开始结点，表中有且仅有一个终端结点，除开始结点外，其他每个元素有且仅有一个_，除终端结点外，其他每个元素有且仅有一个_。3线性表是n（n>=0）个数据元素的_。其中n为数据元素的个数，定义为线性表的_。当n为零时的表称为_。4所谓顺序表（Sequential LISt）是线性表的_，它是将线性表中的结点按其_依次存放在内存中一组连续的存储单元中，使线性表中相邻的结点存放在_的存储单元中。5单链表不要求逻辑上相邻的存储单元在物理上也一定要相邻。它是分配一些_的存储单元来存储线性表中的数据元素，这些存储单元可以分散在内存中的_的位置上，它们在物理上可以是一片连续的存储单元，也可以是_的。因此在表示线性表这种数据结构时，必须在存储线性表元素的同时，也存储线性表的。6线性表的链式存储结构的每一个结点（Node）需要包括两个部分：一部分用来存放元素的数据信息，称为结点的_；另一部分用来存放元素的指向直接后继元素的指针(即直接后继元素的地址信息)，称为_或_。7线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。其逻辑顺序和物理存储顺序不再一致，而是一种_存储结构，又称为_。8如果将单链表最后一个结点的指针域改为存放链表中的头结点的地址值，这样就构成了_。9为了能够快速地查找到线性表元素的直接前驱，可在每一个元素的结点中再增加一个指向其前驱的指针域，这样就构成了_。10双向链表某结点的指针P，它所指向结点的后继的前驱与前驱的后继都是p_。11在单链表中，删除指针P所指结点的后继结点的语句是_。12在双循环链表中，删除指针P所指结点的语句序列是P->prior->nextp->next及_。13单链表是_的链接存储表示。14可以使用_表示树形结构。15向一个长度为n的向量的第i个元素(lin+1）之前插人一个元素时，需向后移动_个元素。16删除一个长度为n的向量的第i个元素（lin）时，需向前移动_个元素。17在单链表中，在指针P所指结点的后面插人一个结点S的语句序列是_。18在双循环链表中，在指针P所指结点前插人指针S所指的结点，需执行语句_。19取出广义表A（x，（a，b，c，d）中原子c的函数是_。20在一个具有n个结点的有序单链表中插人一个新结点并使之仍然有序的时间复杂度为_。21写出带头结点的双向循环链表L为空表的条件_。22线性表、栈和队列都是_结构。23向栈中插人元素的操作是先移动栈_针，再存人元素。1. 一对一2. 直接前驱、直接后继3. 有限序列、长度、空表4. 顺序存储结构、逻辑顺序、地址相邻5. 任意、任意、不连续、逻辑关系6. 数据域、指针域、链域7. 非顺序、非顺序映像8. 循环链表9. 双向链表10. 所指向的结点本身11. P->next=p->next->next12. P->next->prior=P->prior13. 线性表14. 双链表15. n-i+116. n-i17. S->next=P->next; P->next=S18. p->prior->next=S; s->prior=p->prior;s->next=p;p->prior=s;19. head(tail(tail(head(tail(head(A)20. O(n)21. (L=L->Next) && (L=L->Prior)22. 线性23. 顶三、判断题1线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。()2在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。()3顺序存储的线性表不可以随机存取。() 4单链表不是一种随机存取结构。（）5顺序存储结构线性表的插入和删除运算所移动元素的个数与该元素的位置无关。() 6顺序存储结构是动态存储结构，链式存储结构是静态存储结构。()7线性表的长度是线性表所占用的存储空间的大小。()8双循环链表中，任意一结点的后继指针均指向其逻辑后继。()9线性表的惟一存储形式是链表。() 1. 错误：链表存储中，结点之间可以连续也可以不连续，但结点内部是连续的。2. 错误：头指针指向头结点而不是数据结点。3. 错误：顺序存储的线性表可以随机存取。4. 正确。5. 错误。6. 错误：顺序存储结构是静态存储结构，链式存储结构是动态存储结构。7. 错误：先行表的长度是线性表中结点的个数。8. 错误：注意最后一个结点。9. 错误：也可以有顺序存储的形式。第三章 栈和队列一、选择题 l一个栈的序列是：a，b，c，d，e，则栈的不可能输出的序列是（）。Aa，b，c，d，e Bd，e，c，b，a Cd，c，e，a，b De，d，c，b，a 2若一个栈的输人序列是1，2，3，n，输出序列的第一个元素是n，则第k个输出元素是（ ）。 Ak Bn-k-1 Cn-k+1 D不确定3判定一个栈S（最多有n个元素）为空的条件是（ ）。 AS->top！0 BS->top= =0 CS->top!=n DS->top= =n4判定一个栈S（最多有n个元素）为满的条件是（ ）。 AS->top!=0 BS->top= =0 CS->top!=n DS->top= =n5向一个栈顶指针为top的不带头结点的链栈中插人一个*S结点的时候，应当执行语句（ ）。 Atop->next=S； BS->next=top；top=S； CS->nexttop->next；top->nextS；DS->nexttop；topS->next；6向一个带头结点、栈顶指针为top的链栈中插人一个*S结点的时候，应当执行语句（ ）。 Atop->next=S； BS->next=top；top=S； CS->next=top->next；top->next=S； DS->next=top；top=S->next；7判定一个队列Q（最多有n个元素）为空的条件是（ ）。 AQ->rear-Q->front= =n BQ->rear-Q->front+1= =n CQ->rear = = Q->front DQ->rear +1= = Q->front8判定一个队列Q（最多有n个元素）为满的条件是（）。 AQ->rear-Q->front= =n BQ->rear-Q->front+1= =n CQ->rear = = Q->front DQ->rear +1= = Q->front9判定一个循环队列Q（最多有n个元素）为空的条件是（ ）。 AQ->rear = = Q->front BQ->rear = = Q->frontl CQ->front= =(Q->rear +1)n DQ->front= =(Q->rear -1)n10判定一个循环队列Q（最多有n个元素）为满的条件是（ ）。 AQ->rear = = Q->front BQ->rear = = Q->frontl CQ->front= =(Q->rear +1)n DQ->front= =(Q->rear -1)n11在一个链队列中，假定front和rear分别为头指针和尾指针，则插入一个结点*S的操作是（ ）。 Afrontfront->next BS->next=rear；rear=S Crear->next=S；rear=S DS->next=front；frontS12在一个链队列中，假定front和rear分别为头指针和尾指针，删除一个结点的操作是（ ）。 Afront=front->next Brear=rear->next Crear->next=front Dfront->nextrear 13栈与队列都是（ ）。A链式存储的线性结构 B链式存储的非线性结构C限制存取点的线性结构 D限制存取点的非线性结构 14若进栈序列为l，2，3，4，则（ ）不可能是一个出栈序列。 A3，2，4，1 Bl，2，3，4 C4，2，3，1 D4，3，2，l 15在解决计算机主机与打印机之间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写人该缓冲区，而打印机则从该缓冲区中取走数据打印。该缓冲区应该是一个（ ）结构。 A堆栈 B队列 C数组 D线性表1. C2. C3. B4. D5. B6. C7. C8. A9. A10. C 11. C12. A13. C14. C15. B二、填空回1栈（stack）是限定在_一端进行插人或删除操作的线性表。在栈中，允许插人和删除操作的一端称为_，而另一端称为_。不含元素的栈称为_。2在栈的运算中，栈的插人操作称为_或_，栈的删除操作称为_或_。3根据栈的定义，每一次进栈的元素都在原_之上，并成为新的_；每一次出栈的元素总是当前的_，因此最后进栈的元素总是_，所以栈也称为_线性表，简称为_表。4栈是一种操作受到限制的线性表，是一种特殊的线性表，因此栈也有_和_两种存储结构，分别称为_和_5当栈满的时候，再进行人栈操作就会产生_，这种情况的溢出称为_；当栈空的时候，如果再进行出栈操作，也会_，这种情况下的溢出称为_。6栈的链式存储结构简称为_，是一种_。7人们日常计算用到的表达式都被称为_，这是由于这种算术表达式的运算符被置于两个操作数中间。8计算机中通常使用_，这是一种将运算符置于两个操作数后面的算术表达式。这种表达式是由波兰科学家谢维奇提出的，因此又称为_9队列（Queue）也是一种_，但它与栈不同，队列中所有的插人均限定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插人的一端称为_，允许删除的一端称为_。10队列的特点是_，因此队列又被称为_的线性表，或称为_表。11队列的_又称为_，是用一组地址连续的存储单元依次存放队列中的元素。12由于队列中的元素经常变化，对于队列的删除和插人分别在队头和队尾进行，因此需要设置两个指针分别指向_和_，这两个指针又称为_和_。13循环顺序队列（Circular Sequence Queue）经常简称为_，它是将存储顺序队列的存储区域看成是一个首尾相连的一个环，即将队首和队尾元素连接起来形成一个环形表。首尾相连的状态是通过数学上的_来实现的。14在算法或程序中，当一个函数直接调用自己或通过一系列语句间接调用自己的时候，则称这个函数为，也称为_。函数直接调用自己，则称为_；当一个函数通过另一个函数来调用自己则称为_。15在循环队列中规定：当Q->rear= =Q->front的时候循环队列为_， 当（Q->rear+1）MAXSIZEfront的时候循环队列为_。16用链表方式表示的队列称为_。17已知栈的输人序列为1，2，3，n，输出序列为a1，a2，an，符合a2= =n的输出序列共有_。18一个栈的输人序列是12345，则栈的输出序列为43512是_（填是否可能）。19一个栈的输人序列是12345，则栈的输出序列为12345是_（填是否可能）。20设sq1maxsize为一个顺序存储的栈，变量top指示栈顶元素的位置，则作入栈操作的条件是_。21设sq1maxsize为一个顺序存储的栈，变量top指示栈顶元素的位置，如果把栈顶元素弹出并送到X中，则需执行语句_。22栈的特性是_。23对栈进行退栈时的操作是先取出元素，后移动_。24设s1max为一个顺序存储的栈，变量top指示栈顶位置，栈为满的条件是_。25设链栈的栈顶指针为top，则栈非空的条件是_。26已知循环队列用数组data1.n存储元素值，用f，r分别作为头尾指针， 则当前元素个数为_。27在一个循环队列中，队首指针指向队首元素的_位置。（前一个或后一个）28队列中允许进行删除的一端称为_。29链队列实际上是一个同时带有头指针和尾指针的单链表（1n），尾指针指向该单链表的第_个元素。30设双向链表链列为lq，lq的头指针为lq.Front，尾指针为lq.Rear，则队列为空的条件是_。31从循环队列中删除一个元素，其操作是先取出一个元素，后移动_32队列中允许进行插入的一端称为_。1. 表尾、栈顶、栈底、空栈2. 进栈、入栈、退栈、出栈3. 栈顶元素、栈顶元素、栈顶元素、最先出栈、后进先出、LIFO4. 顺序、链式、顺序栈、链栈5. 溢出、上溢、溢出、下溢6. 链栈、特殊的单链表7. 中缀表达式8. 后缀表达式、波兰式9. 特殊的线性表、队尾、队头10. 先进先出、先进先出、FIFO11. 顺序存储结构、顺序队列12. 队头元素、队尾元素、队头指针、队尾指针13. 循环队列、取模运算14. 递归函数、自调用函数、直接递归调用、间接递归调用15. 空、满16. 链队列17. n-118. 不可能的19. 可能的20. top!=maxsize21. x=sqtop; top=top-122. 先进后出23. 栈顶指针24. top=max25. top!=nil26. (n+r-f)mod n27. 前一个28. 队首29. n30. lq->front=lq->rear31. 栈顶指针32. 队尾三、判断题1栈和队列都是限制存取点的线性结构。（ ）2不同的入栈和出栈组合可能得到相同输出序列。（ ）3消除递归一定要用栈。（ ）4循环队列是顺序存储结构。（ ）5循环队列不会产生溢出。（ ）6循环队列满的时候rear= =front。（ ）7在对链队列（带头结点）做出队操作时不会改变front指针的值。（）1. 正确。2. 错误：不同的入栈和出栈组合得到不同输出序列。3. 错误：某些情况如尾递归可以转换为递推的形式。4. 正确。5. 错误：循环队列不会产生假溢出。6. 错误。7. 正确。四、综合题1设有4个元素A、B、C和D进栈，给出它们所有可能的出栈秩序