数据结构期末考试(题集).pdf

数据结构的基本概念选择题（1）顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。A.线性结构 B.非线性结构 C.存储位置 D.指针（2）假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产，子女可以继承父亲或母亲的遗产；子女间不能相互继承，则表示该遗产继承关系的最合适的数据结构应 该 是（）。A.树 B.图 C.线性表 D.集合（3）计算机所处理的数据一般具有某种内在联系，这 是 指（）oA.数据和数据之间存在某种关系 B.元素和元素之间存在某种关系C.元素内部具有某种结构 D.数据项和数据项之间存在某种关系（4）在数据结构中，与所使用的计算机无关的是数据的（）。A.树 B.图 C.线性表 D.集合（5）在存储数据时，通常不仅要存储各数据元素的值，还要存储（一）oA.数据的处理方法 B.数据元素的类型C.数据元素之间的关系 D.数据的存储方法（6）在链接存储结构中，要 求（A.每个结点占用一片连续的存储区域C.结点的最后一个域是指针类型（7）下列说法不正确的是（）。A.数据元素是数据的基本单位C.数据可由若干个数据项构成.）。B.所有结点占用一片连续的存储区域D.每个结点有多少个后继就设多少个指针B.数据项是数据中不可分割的最小单位D.数据元素可由若干个数据项构成（8）以下与数据的存储结构无关的术语是（）。A.循环队列 B.链表C.散列表D.栈（9）以下术语属于逻辑结构的是（）。A.顺序表 B.哈希表 C.有序表（10）可 以 用（-）定义一个完整的数据结构。A.数据元素 B.数据对象 C.数据关系D.单链表D.抽象数据类型（11）对于数据结构的描述，下列说法中不正确的是（）。A.相同的逻辑结构对应的存储结构也必相同B.数据结构由逻辑结构、存储结构和基本操作三方面组成C.数据结构基本操作的实现与存储结构有关D.数据的存储结构是数据的逻辑结构的机内实现(1 2)以下关于链接存储结构的叙述中，()是不正确的。A.结点除数据信息外还包括指针域，因此存储密度小于顺序存储结构B.逻辑上相邻的结点物理上不一定相邻C.可以通过计算得到第i 个结点的存储地址D.插入和删除操作方便，不必移动结点(1 3)可 以 用()、数据关系和基本操作定义一个完整的抽象数据类型。A.数据元素 B.数据对象C.原子类型 D.存储结构应用题(1 4)设有数据结构(D,R),其中 D=1,2,3,4,5,6 ,R=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)。试画出其逻辑结构图并指出属于何种结构。(1 5)试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。(1 6)说明数据的逻辑结构和存储结构之间的关系。(1 7)抽象数据类型的主要特点是什么？数据类型和抽象数据类型的关系如何？使用抽象数据类型的主要好处是什么？1算法和算法分析选择题（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.分析算法的易读性和文档性E.空间性能和时间性能F.正确性和简明性G.可读性和文档性H.数据复杂性和程序复杂性（7）算法的时间复杂度与（）有关。A.问题规模 B.计算机硬件性能C.编译程序的质量 D.程序设计语言（8）算法的时间复杂度与（）有关。A.问题规模 B.待处理数据的初态C.算法的易读性 D.A和B（9）某算法的时间复杂度是0（1?）,表明该算法（）。A.问题规模是M B.执行时间等于I?C.执行时间与I?成正比 D.问题规模与M成正比（10）下面说法错误的是（）。算法原地工作的含义是指示不需要如何额外的辅助空间在相同的规模n 下，复杂度O(n)的算法在时间上总是优于复杂度0(2)的算法所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界同一个算法，实现语言的级别越高，执行效率就越低(11)算法for(i=n-1;i=1;i)for(j=l；jafj+l)aj与 aU+1交换;其中n 为正整数，则最后一行语句的频度(执行次数)在最坏情况下是()A.O(n)B.O(nlog2n)C.O(n3)D.O(n2)(12)算法的时间复杂度属于一种()A.事前统计的方法 B.事先分析估算的方法C.事后统计的方法 D.事后分析估算的方法(13)设某算法完成对n 个元素进行处理,所需的时间是T(n)=1 00 nlog2n+200n+500,则该算法的时间复杂度是()。A.0(1)B.O(n)C.O(nlog2n)D.O(nlog2n+n)(14)假设时间复杂度为。(i?)的算法在有200个元素的数组上运行需要3.1m s,则在有400个元素的数组上运行需要()msoA.3.1 B.6.2 C.12.4 D.x(无法确定)(15)下列程序段加下划线的语句执行()次。for(m=0,i=l;i=l;i+)for(j=l;j=2*i;j+)m=m+1 ；A.n2 B.3n C.n(n+1)D.n应用题(16)将下列函数按它们的n-8 时的无穷大阶数，从小到大排列。n,n-n3-7n5,nlog2n,2n，2,n3,log2n,nl/2+log2n,(3/2),n!,n+log2n(17)分析以下程序段，并用大。记号表示其执行时间。i=l;k=0;while(in-l)k=k+10*i;i+；else i+;for(i=l;i=n;i+)for(j=l；j=i；j+)for(k=l;k=j;k+)x+;i=l；j=0;while(i+jj)j+；i=l;k=0;dok=k+10*i;i+；w h i l e (i =n)f o r (i=0;i n;i+)y=0;f o r (j=0;j m;j+)w h i l e (y+l)*(y+l)=n)a i j =O;y=y+i(1 8)有实现同一功能的两个算法Al和A2,其 中Al的时间复杂度为=0(2”)，A2的时间复杂度为T 2=O(n 2),仅就时间复杂度而言，请具体分析这两个算法哪一个好。综合应用题(1 9)设n是偶数，且有程序段：f o r (i=l;i=n;i+)i f(2*i=n)f o r (j=2*I;j 0(1)C.0(1)、O(n)D.0(1)、0(1)(8)顺序表的插入算法中，当n个空间已满时，可再申请增加分配m个空间，若申请失败，则说明系统没有()可分配的存储空间。A.m个 B.m个连续的 C.n+m个 D.n+m个连续的应用题(9)设A是一个线性表(a“a 2,，a Q,采用顺序存储结构，则在等概论的前提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在为与跖|之间(l W i W n)的概率为(n-i)/(n (n-1)/2),则平均每插入一个元素所移动的元素个数是多少？(1 0)设n表示线性表中的元素个数，E表示存储数据元素所需要的存储单元大小,7D表示可以在数组中存储线性表的最大元素个数(D 2 n),则使用顺序存储方式存储线性表需要多少存储空间？(1 1)在什么情况下线性表使用顺序存储比较好？算法设计题(1 2)试以顺序表作存储结构，实现线性表就地逆置。(1 3)设计算法判断给定字符串是否是回文。所谓回文是正读和反读均相同的字符串,例如a bc ba 或 a bba 是回文，而 a bc d a 不是回文。(1 4)设 计 个时间复杂度为O(n)的算法，实现将数组A n 中所有元素循环左移k个位置。(1 5)已知数组A n 中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为O(n)。(1 6)假定数组中有多个零元素，设计算法将数组中所有非零元素移到数组的前端。(1 7)顺序存储的线性表A,其数据元素为整型，设计算法将A拆 成 B和 C两个表，使 A中值大于0 的元素存入表B,值小于0 的元素存入表C,要求B和 C不另外设置存储空间而利用A的空间。(1 8)已知顺序表L中的元素递增有序排列，设计算法将元素x 插入到表L中并保持表L仍递增有序.(1 9)设计一个高效算法，在顺序表中删除所有元素值为x 的元素，要求空间复杂度为 0(1)。(20)设计算法实现从顺序表L中删除所有值在x 和 y之间的所有元素，要求时间性能复杂度为O(n),空间性能为0(1)。(21)设计算法删除顺序表中重复的元素,要求算法移动元素的次数较少并使剩余元素间的相对次序保持不变。(22)给定n个记录的有序序列A n 和 m个记录的有序序列B m ,将它们归并为个有序序列，存放在C f n+m 中，试写出这一算法(假设A、B和 C均为升序序列)。84线性链表选择题(1)线性表的链接存储结构是一种()的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取(2)线性表采用链接存储时,A.地址必须是连续的C.地址一定是不连续的(3)链表不具有的特点是(_A.可随机访问任一元素C.不必事先估计存储空间B.部分地址必须是连续的D.地址连续与否均可以B.插入、删除不需要移动元素D.所需空间与线性表长度成正比(4)在 具 有 n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是()A.0(1)B.O(n)C.O(n2)D.O(nlog2nl)(5)对于n 个元素组成的线性表，建立一个单链表的时间复杂度是(_ _ _ _)。A.0(1)B.O(n)C.O(n2)D.O(nlog2nl)(6)对于n 个元素组成的线性表，建立一个有序单链表的时间复杂度是()。A.0(1)B.O(n)C.O(n2)D.O(nlog2nl)(7)在单链表中删除指针p 所指结点的后续结点，则 执 行()。A.p-next=p-next-next B.p-next=p-nextC.p=p-next-next D.p=p-next;p-next=p-next-next(8)在一个单链表中，已知q 所指结点是p 所指结点的直接前驱，若在q 和 p 之间插入S所指结点，则 执 行()操作。A.s-next=p-next;p-next=s;B.q-next=s;s-next=p;C.p-next=s-next;s-next=p;D.p-next=s;s-next=q(9)在一个长度为n(n l)的带头结点的单链表h 上，另设有尾指针r 指向尾结点，执 行()操作与链表的长度有关。A.删除单链表中的第一个元素B.删除单链表中的最后一个元素C.在单链表第一个元素前插入一个新元素D.在单链表的最后一个元素后插入一个新元素(10)在单链表中附加头结点的目的是为了(A.保证单链表中至少有一个结点 B.标识单链表中首结点的位置C.方便运算的实现 D.说明单链表是线性表的链式存储9（1 1）将长度为n个单链表链接在长度为m的单链表之后的算法，其时间复杂度是（）.A.0（1）B.O（n）C.O（m）D.O（n+m）（1 2）循环单链表的主要优点是（）oA.不再需要头指针了B.从表中任一结点出发都能扫描到整个链表C.已知某个结点的位置后，能够容易找到它的直接前驱D.在进行插入、删除操作时，能更好地保证链表不断开（1 3）将线性表（a,a2,-an）组织为一个带头结点的循环单链表，设H为链表的头指针，则链表中最后一个结点的指针域中存放的是（）。A.变量H的地址 B.变量H的值C.元素a 1的地址 D.空指针（1 4）非空的循环单链表L的尾结点p满 足（A.p=N UL L B.p-n e x t=N UL L C.p-n e x t=L D.p=L（1 5）若要在0（1）的时间内实现两个循环单链表的首尾相接，则两个循环单链表应各设一个指针，分别指向（）oA.各自的头结点 B.各自的尾结点C.各自的第一个元素结点 D.一个表的头结点，一个表的尾结点（1 6）设线性表非空，（）可以在O的时间内在表尾插入个新结点。A.带头结点的单链表，有一个链表指针指向头结点B.带头结点的循环单链表，有一个链表指针指向头结点C.不带头结点的单链表，有一个链表指针指向表的第一个结点D.不带头结点的循环单链表，有个链表指针指向表中某个结点（除第一个结点外）（1 7）设 指 针r e a r指向带头结点的循环单链表的尾指针，若要删除链表的第个元素结点，正确的操作是（A.s=r e a r;r e a r=r e a r-n e x t;B.r e a r=r e a r-n e x t;C.r e a r=r e a r-n e x t-n e x t;D.s=r e a r-n e x t-n e x t;r e a r-n e x t-n e x t=s-n e x t;（1 8）设有两个长度为n个单链表，以h l为头指针的链表是非循环的，以h 2为尾指针的链表是循环的，则（）oA.在两个链表上删除第一个结点的操作，其时间复杂度均为0（1）B.在两个链表的表尾插入一个结点的操作，其时间复杂度均为O（n）C.循环链表要比非循环链表占用更多的存储空间D.循环链表要比非循环链表占用更少的存储空间（1 9）使用双链表存储线性表，其优点是可以（）。10A.提高查找速度C.节约存储空间B.更方便数据的插入和删除D.很快回收存储空间(20)与单链表相比，双链表的优点之一是(_ _ _ _A.插入和删除操作更简单 B.可以进行随机访问C.可以省略表头指针或表尾指针 D.访问其后相邻结点更灵活(21)带头结点的循环双链表L 为空表的条件是(A.L-next-prior=NULL B.L-prior=LC.L-next=L D.B 和 C 都对(22)在循环双链表的p 所指结点后插入s所指结点的操作是()。A.p-next=s;s-prior=p;p-next-prior=s;s-next=p-next;B.p-next=s;p-next-prior=s;s-prior=p;s-next=p-next;C.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;(23)在双链表中指针pa所指结点后面插入pb所指结点，执行的语句序列是(一)opb-next=pa-next;pb-prior=pa;pa-next=pb;pa-next-prior=pb;A.B.C.D.(24)在一个双链表中，删除结点p 的操作是()oA.p-prior-next=p-next;p-next-prior=p-prior;B.p-prior=p-prior-prior;p-prior-prior=p;C.p-next-prior=p;p-next=p-next-next;D,p-next=p-prior-prior;p-prior=p-prior-prior;应用题(25)单链表设置头结点的作用是什么？(26)线性表的顺序存储结构具有三个弱点：其一，插入或删除操作需要移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；其三，表的容量难以扩充。试问，线性表的链接存储结构是否能够克服上述三个弱点？(27)若频繁地对一个线性表进行插入和删除操作，该线性表采用什么存储结构比较好？(28)设 n 表示线性表中的元素个数，P表示指针所需的存储单元大小，E 表示存储数据元素所需的存储单元大小，则使用单链表存储方式存储该线性表需要多少存储空间(不考虑头结点)？算法设计题II（2 9）设计算法依次打印单链表中每个结点的数据信息。（3 0）求单链表的长度。（3 1）设计算法将值为x 的结点插入到不带头结点的单链表L中值为k的结点之前,若找不到值为k的结点，则将x 插入到链表的末尾。（3 2）判断非空单链表是否递增有序。（3 3）已知非空线性链表由l i s t 指 出,结点结构为（da t a,l i nk）。请编写算法,将链表中数据域最小的结点移到链表的最前面。要求：不得额外申请新的结点。（3 4）给定一个带头结点的单链表，设 h e a d为头指针，设计算法按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间（要求：不允许使用数组作辅助空间）。（3 5）已知非空线性链表山l i s t 指出，设计算法交换p所指结点与其后续结点在链表中的位置（设 p 所指结点不是链表的最后一个结点）。（3 6）设计算法实现将单链表就地逆置。（3 7）头插法建立单链表。（3 8）尾插法建立单链表（3 9）复制一个单链表。（4 0）设计算法实现将单链表就地逆置。（4 1）在一个有序单链表（假设从小到大排列）中插入一个元素值为x 的结点，使得插入后单链表仍然有序。（4 2）设单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结点。（4 3）已知单链表中各结点的元素值为整型且递增有序，设计算法删除表中大于mi nk 且小于ma xk 的所有元素，并释放被删结点的存储空间。（4 4）有两个整数序列A=（a i，a 2,，a m）和 B=（b“b2,b j 已经存入两个单链表中，设计算法判断序列B是否是序列A的子序列。（4 5）设线性表C=（a b a2,b2,an,b j 采用带头结点的单链表存储，设计算法将表C拆分为两个线性表A和 B,使 得 A=（a i，a21 an）,B=（bI（b2,，,b n）。12（4 6）有两个递增有序的单链表l a和1b,设计算法将这两个单链表合并为一个有序链表。（4 7）有两个有序的单链表，一个表为升序，另一个表为降序，设计算法将这两个链表合并为一个有序链表。（4 8）已知单链表A和B的 数 据（设为整型）递增有序，设计算法利用原有结点，将表A中与表B具有相同值的结点删除，将表B中与原表A不同值的结点存入表A中，并保持表A的递增有序。（4 9）设计算法将循环单链表就地逆置。（5 0）已知L为单链表的头结点地址，表中共有m （m 3）个结点，从表中第i个（1i an.|,an,）改造成（a”a2,，an.|,an,an.p,a2（a p。（5 6）判断带头结点的循环双链表是否对称。（5 7）设计算法实现双链表中第i个结点的前面插入一个值为x的结点。（5 8）已知非空循环双链表he a d的存储结构为：S t ru c t D N od e T EI e m i nf o;S t ru c t D N od e *l e f t;S t ru c t D N od e *ri g ht;13设计算法实现从链表中删除指针P所指结点的前驱结点（假设该结点存在）。（59）已知非空双链表由d 指出，结点结构为（priordatanext）,请设计算法将链表中数据值最大（假定唯一）的那个结点移至链表的最前面。要求不得额外申请新的双链表结点。（60）设计算法实现将双链表中结点p 与其后继结点互换位置。（61）设有一个双链表，每个结点中除了有prior、data和 next三个域外，还有一个访问频度域freq,在链表被起用之前，其值均初始化为零，每当在双链表上进行一次 LOCATE运算时，令元素值为x 的结点中freq域的值增1,并使此链表中结点保持频度递减的顺序排列，以便使频繁访问的结点总是靠近表头。编写算法实现符合上述要求的LOCATE算法。14静态链表选择题（1）静态链表中指针表示的是（A.下一结点在内存中的地址C.左、右孩子的存储位置.）。B.下一元素在数组中的下标D.左、右孩子的地址（2）以下说法错误的是（）。静态链表既有顺序存储的优点又有动态链表的优点。所以，它存取表中第i 个元素的时间与i 无关静态链表中能容纳的元素个数在定义表时必须是确定的静态链表与动态链表在元素的插入、删 除 上 类似，不需做元素的移动A.，B.C.，D.（3）用数组r 存储静态链表，结点的n e x t 域指向后继，工作指针j 指向链中某结点,使j 沿链移动的操作为（）A.j=r j .n e x t B.j=j+lC.j=j-n e x t D.j=r j -n e x t（4）线性表的静态链表存储与顺序存储相比，优 点 是（）。A.所有基本操作的算法实现简单 B.便于随机存取C.便于插入和删除 D.便于利用零散的存储空间（5）下图所示数组中以静态链表形式存储了一个线性表，设头指针为a O.l i n k,则该线性表的元素依次为（）。2 3 4 5 6 7 8d a t al i n kA.60,63,40,45,74,C.74,2 5,45,60,40,2 563B.45,63,2 5,60,40,74D.2 5,45,60,40,63,74156线性表综合选择题（1）下面关于线性表的叙述中，错误的是（）。A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作C.线性表采用链接存储，不必占用一片连续的存储单元D.线性表采用链接存储，便于插入和删除操作（2）若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱，则采用（一）存储方法最节约时间。A.顺序表 B.单链表 C.双链表 D.循环单链表（3）若链表中最常用的操作是在最后一个结点之后插入个结点和删除第个结点，则 采 用（）存储方法最节约时间。A.单链表 B.循环双链表C.循环单链表 D.带尾指针的循环单链表（4）设线性表有n个元素，以下操作中，（）在顺序表上实现比在链表上实现的效率更高。A.输出第i （l W i W n）个元素值B.交换第1个和第2个元素的值C.顺序输出所有n个元素D.查找与给定值x相等的元素在线性表中的序号（5）如果对于具有n（n l）个元素的线性表的基本操作有4种：删除第一个元素；删除最后一个元素；在第一个元素前插入新元素；在最后一个元素的后面插入新元素。则最好使用（）。A.只设尾指针的循环单链表B.只设尾指针的非循环单链表C.只设头指针的循环双链表D.同时设置头指针和尾指针的循环单链表应用题（6）请比较线性表的两种基本的存储结构顺序表和单链表。（7）举例说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，算法的效率不同。（8）如果某线性表中数据元素的类型不致，但是希望能根据下标随机存取每个元素，请为这个线性表设计一个合适的存储结构。（9）线性链表有哪几种常见的变形？各有何特点？16算法设计题(1 0)用顺序表表示集合，设计算法实现集合的求交集运算。(1 1)用顺序表表示集合，设计算法实现集合的求并集运算。(1 2)用顺序表表示集合，设计算法实现集合的求差集运算，要求不另外开辟空间。(1 3)假定以有序表表示集合，设计算法判断两个给定集合是否相等。(1 4)设两个单链表L 1 和 L 2 分别表示两个集合，设计算法判断L 1 是否是L 2 的子集。(1 5)已知两个不带头结点的单链表A和 B分别表示两个集合，并且其元素值递增有序，求 A、B的交集C,并以同样的递增形式存储，要求尽可能节省时间。(1 6)在某商店的仓库中，对电视机按其价格从低到高建立一个单链表，链表的每个结点指出同样价格的电视机的台数。现 有 m 台价格为n元的电视机入库，请编写算法完成仓库的进货管理。(1 7)从键盘输入n个英语单词，输入格式为n,w p W 2，wn,其中n 表示随后输入英语单词个数，试编写算法建立一个单链表，要求：如果单词重复出现，则只在链表上只保留个；统计单词重复出现的次数，然后输出次数最多的前k (k 0)个人围成一个圈，每个人持有一个密码m (m W l),从 第 1 个人开始报数，报 到 m 时停止报数，报 m 的人出圈，再从他的下一个人起重新报数，报 到 m时停止报数，报 m的出圈，如此下去，直到所有人全部出圈为止。当任意给定n和 m后，设计算法求n个人出圈的次序。(2 1)编写算法，完成下述要求：建立一个链表用于存放输入的二进制数，链表中的每个结点的d at a域存放一个二进制位。在此链表上实现对二进制数加1 的运算，并输出运算结果。(2 2)有一个不带头结点的单链表h,通过遍历链表将链表中所有的链接方向逆转，17算法如下，请在空格处填写正确的语句。void Inverse(&h)if()return：p=h-next;pr=NULL;while()h-next=pr;pr=h;h=p;)(23)设两个带头结点的单链表A和B,表中结点的数据为整型，下血算法产生表A和表B的并集并以表C存储，请填写算法中空白处的语句，完成其功能。187栈的基本概念选择题(1)经过以下栈运算后，X的 值 是()。InitStack(s),Push(s,a),Push(s,b),Pop(s,x),GetTop(s,x)A.a B.b C.1 D.0（2）经过以下栈运算后，StackEmpty 的 值 是（）。InitStack（s）,Push（s,a）,Push（s,b）,Pop（s,x）,Pop（s,y）A.a B.b C.1 D.0（3）（一）不是栈的基本运算。A.删除栈顶元素 B.删除栈底元素C.判断栈是否为空 D.将栈置为空栈（4）设有一个空栈，栈顶指针为1000H（十六进制，下同），每个元素需要1个单位的存储空间，则执行 PUSH,PUSH,POP,PUSH,POP,PUSH,POP,PUSH操作后，栈顶指针值为（）。A.1002H B.1003H C.1004H D.1005H（5）个栈的入栈序列是1,2,3,4,5 ,则栈的不可能的输出序列是（）。A.（5,4,3,2,1 B.4,5,3,2,1 C.4,3,5,1,2 D.1,2,3,4,5（6）若一个栈的输入序列是1,2,3,n,输出序列的第一个元素是n,则第i个输出元素是（）。A.不确定 B.n-i C.n-i-1 D.n-i+1（7）若一个栈的输入序列是1,2,3,n,其输出序列是pi，P2，Pn，若pi=3,则 P 2 的 值（）。A.一定是2 B.一定是1 C.不可能是1 D.以上都不对（8）若一个栈的输入序列是pi，P 2 1 ,Pn，其输出序列是1，2,3,，n,若P3=l,则 pi 的 值（）。A.可能是2 B.一定是2 C.不可能是2 D.不可能是3（9）当字符序列t3_ 依次通过栈，输出长度为3 且可用作C 语言标识符的序列有()。A.4 个 B.5 个C.3 个 D.6 个应用题（10）设有一个栈，元素进栈的次序为A,B,C,D,E,能否得到如下出栈序列,若能，请写出操作序列，若不能，请说明原因。19C,E,A,B,DC,B,A,D,E(11)在操作序列 push(l)、push(2)、pop、push、push(7)pop push(6)之后,栈顶元素和栈底元素分别是什么？(push(k)表示整数k入栈,pop表示栈顶元素出栈。)(12)设 元 素 1、2、3、P、A 依次经过一个栈，进栈次序为123PA,在栈的输出序列中，有哪些序列可作为C+程序设计语言的变量名。(13)如果进栈序列为A、B、C、D,则可能的出栈序列是什么？算法设计题(14)假设以I 和 0 分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I 和 0 组成的序列，称可以操作的序列为合法序列，否则称为非法序列。下面所示的序列中哪些是合法的？A.IOIIOIOO B.I00I0II0 C.IIIOIOIO D.IIIOOIOO 通过对的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true,否则返回false(假定被判定的操作序列已存入-维数组中)。208顺序栈选择题（1）在一个具有n 个单元的顺序栈中，假定以地址低端（即下标为0 的单元）作为栈底，以 top作为栈顶指针，当出栈时，top的变化为（）。A.不变 B.top=0 C.top-1 D.top=top+1（2）设数组Sn作为两个栈S1和 S2的存储空间，对任何一个栈只有当Sn全满时才不能进行进栈操作。为这两个栈分配空间的最佳方案是（）。A.S1的栈底位置为0,S2的栈底位置为n-1B.S1的栈底位置为0,S2的栈底位置为n/2C.S1的栈底位置为0,S2的栈底位置为nD.S1的栈底位置为0,S2的栈底位置为1（3）为了增加内存空间的利用率和减少溢出的可能性,两个栈共享一片连续的内存空间时，应将两栈的栈底分别设在这片内存空间的两端，这样，当（）时才产生上溢。A.两个栈的栈顶同时到达栈空间的中心点B.其中一个栈的栈顶到达栈空间的中心点C.两个栈的栈顶在栈空间的某一位置相遇D.两个栈均不空，且一个栈的栈顶到达另一个栈的栈底（4）两个栈共享一个数组空间的好处是（）。A.减少存取时间，降低发生上溢的可能性B.节省存储空间，降低发生上溢的可能性C.减少存取时间，降低发生下溢的可能性D.节省存储空间，降低发生下溢的可能性算法设计题（5）假设以I 和 0 分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅有I 和 0 组成的序列，称可以操作的序列为合法序列，否则称为非合法序列。下面所示的序列中哪些是合法的？通过对的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回true,否则返回false（假定被判定的操作序列已存入一维数组中）。（6）下面的算法将一个整数e压入到堆栈S,请在空格处填上适当的语句实现该操作。Typedef struct int*base;int top;int stacksize;SqStack;21int Push(SqStack S,int e)if()S上ase=(int*)realloc(S.base,(S.stacksize+l)*sizeof(int);if()printf(Not Enough Memory!n );retuan 0;)S.t op=;S.s t a c ks i z e=;)_ _ _ _ _ _ _ _ _ _ _ _ _ _;retuan 1;229链栈选择题(1)向一个栈顶指针为h 的带头结点的链栈中插入指针S 所指的结点时，应执行()。A.h-next=s;C.s-next=h;h-next=s;B.s-next=h;D.s-next=h-next;h-next=s;(2)从栈顶指针为top的链栈中删除个结点，用 x 保存被删除结点的值，则执行()。A.x=top;top=top-next;C.top=top-next;x=top-data;B.x=top-data;D.x=top-data;top=top-next;231 0队列的基本概念选择题(1)队列的“先进先出”特性是指()oA.最后插入队列中的元素总是最后被删除B.当同时进行插入、删除操作时，总是插入操作优先C.每当有删除操作时，总要先做一次插入操作D.每次从队列中删除的总是最早插入的元素(2)允许对队列进行的操作有()。A.对队列中的元素排序 B.取出最近入队的元素C.在队头元素之前插入元素 D.删除队头元素(3)一个队列的入队顺序是1、2、3、4,则队列的输出顺序是()。A.4 3 2 1 B.12 3 4 C.14 3 2 D.3 2 4 1241 1 顺序队列选择题(1)循环队列存储在数组A0mJ中，则入队时的操作为()。A rear=rear+1 B.rear=(rear+1)mod(m-1)C,rear=(rear+1)mod m D.rear=(rear+1)mod(m+1)(2)若用一个长度为6 的数组来实现循环队列，且当前rear和 front的值分别为0和3,则从队列中删除一个元素,再增加两个元素后,rear和front的值分别为(A.1 和 5 B.2 和 4 C.4 和 2 D.5 和 1(3)已知循环队列的存储空间为数组A2IJ,front指向队头元素的前一个位置，rear指向队尾元素，假设当前front和 rear的值分别是8和 3,则该队列的长度为()。A.5 B.6 C.16 D.17(4)如图所示为一个元素类型为字符型的环形队列，如 果 front指向队头元素的前一个位置，rear指向队尾元素，则所表示的队列为()。0123456789 10 1 1 12 13 14 15 16 17 18 19 20 21 22t reart frontA.The f B.beautiful The f C.flower is D.eautiful The fThef10weR1sbeauTifu1应用题(5)举例说明顺序队列的“假溢出”现象。(6)简述顺序队列假溢出的避免方法及队列满或空的判定条件。(7)在操作序列 EnQueue(l)、EnQueue(3)DeQueue、EnQueue、EnQueue(7)、DeQueue EnQueue(9)之后，队头元素和队尾元素分别是什么？(EnQueue(k)表示整数k 入队，DeQueue表示队头元素出队。)算法设计题(8)在循环队列中设置一个标志flag,当 fronl=rear且 flag=0时为队空，当 front=rear且 flag=l时为队满。编写相应的入队和出队算法。(9)如果设置一个计 数 器 count累计队列的长度，则 当 count=0时队列为空，当count=QueueSize时队列为满。试设计相应的入队和出队算法。(10)251 2 链队列选择题（1）用不带头结点的单链表存储队列时，其队头指针指向队头结点，队尾指针指向队尾结点，则执行删除操作时，（）oA.仅修改队首指针 B.仅修改队尾指针C.队首指针和队尾指针都需要修改 D.队首指针和队尾指针可能都需要修改（2）在链队列中，设指针f 和 r分别指向队首和队尾，则播入s所指结点的操作是()。A.f-next=s;f=s;C.s-next=r;r=s;B.D.r-next=s;r=s;s-next=f;f=s;（3）设循环单链表表示的队列长度为n,（）。若只设头指针，则进队操作的时间性能为A.O(n)B.0(1)C.O(n2)D.O(nlog2n)_ _ _ _）。B.只带队首指针的循环双链表D.只带队尾指针的循环单链表（4）最不适合用作链队列的链表是（A.只带队首指针的非循环双链表C.只带队尾指针的循环双链表算法设计题（5）假设以不带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针。试设计相应的入队和出队算法。261 3 栈和队列的应用选择题(1)设计一个判别表达式中左右括号是否配对的算法，采用()数据结构最佳。A.顺序表 B.栈 C.队列 D.链表(2)如果数据是在程序的运行过程中逐步产生的，并且要求先产生的数据后处理,后产生的数据先处理，则最合适的数据结构是()。A.顺序表 B.顺序栈 C.顺序队列 D.堆(3)在解决计算机主机和打印机之间速度不匹配问题时通常设置一个打印缓冲区,该缓冲区应该是一个()结构。A.栈 B.队列 C.数组 D.线性表(4)执 行()操作时，需要使用队列作为辅助数据结构。A.深度优先遍历图 B.广度优先遍历图C.散列查找 D.遍历二叉树(5)表达式 3*2八(4+2*2-6*3)-5(一),其中人表示乘幕。A.3,2,4,1,1；#*(+*-C.3,2,4,2,2；#*八(-求值过程中当扫描到B.3,2,8；#*A-D.3,2,8；#*A(-6 时，对象栈和算符栈为(6)利用栈计算表达式的值时