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

《数据结构期末考试题集.pdf》由会员分享，可在线阅读，更多相关《数据结构期末考试题集.pdf（38页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构的基本概念选择题(1)顺序存储结构中数据元素之间的逻辑关系是由()表示的，链接存储结构中的数据元素之间的逻辑关系是由()表示的。A.线性结构 B。非线性结构。C存 储 位 置。D.指针(2)假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产，子女可以继承父亲或母亲的遗产；子女间不能相互继承，则表示该遗产继承关系的最合适的数据结构应 该 是()oA.树0 B.图。0 Co线性表 0 Do集合(3)计算机所处理的数据一般具有某种内在联系，这 是 指()。A o数据和数据之间存在某种关系 B.元素和元素之间存在某种关系C.元素内部具有某种结构。D.数据项和数据项之间存在某种关系(4)在数据结

2、构中，与所使用的计算机无关的是数据的().A.树。o B.图 o Co线性表。D.集合(5)在存储数据时，通常不仅要存储各数据元素的值，还 要 存 储()。A.数据的处理方法。B.数据元素的类型C.数据元素之间的关系 D.数据的存储方法(6)在链接存储结构中，要 求()。A.每个结点占用一片连续的存储区域。B.所有结点占用一片连续的存储区域C.结点的最后一个域是指针类型。D.每个结点有多少个后继就设多少个指针(7)下列说法不正确的是().A.数据元素是数据的基本单位。B.数据项是数据中不可分割的最小单位C 数据可由若干个数据项构成。D。数据元素可由若干个数据项构成(8)以下与数据的存储结构无关

3、的术语是()。A循环队列。B,链表。C。散列表。D.栈(9)以下术语属于逻辑结构的是()。A。顺序表。Bo哈希表。C.有序表。D.单链表(10)可 以 用()定义一个完整的数据结构。A。数据元素。B.数据对象。C.数据关系 D.抽象数据类型(11)对于数据结构的描述，下 列 说 法 中 不 正 确 的 是()。A.相同的逻辑结构对应的存储结构也必相同B.数据结构由逻辑结构、存储结构和基本操作三方面组成C.数据结构基本操作的实现与存储结构有关D.数据的存储结构是数据的逻辑结构的机内实现(12)以下关于链接存储结构的叙述中，()是不正确的。A.结点除数据信息外还包括指针域，因此存储密度小于顺序存储

4、结构B.逻辑上相邻的结点物理上不一定相邻C o可以通过计算得到第i个结点的存储地址D。插入和删除操作方便，不必移动结点(13)可 以 用()、数据关系和基本操作定义一个完整的抽象数据类型.A.数据元素。B.数据对象。C.原子类型。D.存储结构应用题(14)设有数据结构(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).试画出其逻辑结构图并指出属于何种结构。(15)试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。(16)说明数据的逻辑结构和存储结构之间的关系。(17)抽象数据类型

5、的主要特点是什么？数据类型和抽象数据类型的关系如何？使用抽象数据类型的主要好处是什么？1 4算法和算法分析选择题(1)算法指的是()OA.对特定问题求解步臊的一种描述，是指令的有限序列B.计算机程序C.解决问题的计算方法D.数据处理(2)下面()不是算法所必须具备的特性。A.有穷性。B.确切性。C o高效性。D。可行性(3)算法必须具备输入、输出和()等特性。A。可行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、稳定性和有穷性 D.易读性、稳定性和健壮性(4)算法应该具有确定性、可行性和有穷性，其中有穷性是指(_ _ _)A.算法在有穷的时间内终止。B 输入是有穷的C o输出是

6、有穷的 o 0 D.描述步骤是有穷的(5)当输入非法错误时，一个“好”的算法会进行适当处理，而不会产生难以理解的输出结果，这称为算法的().A.可读性。B o 健壮性。C.正确性。D.有穷性(6)算法分析的目的是(),算法分析的两个主要方面是()。A.找出数据结构的合理性。B.研究算法中输入和输出的关系C.分析算法的效率以求改进。D.分析算法的易读性和文档性E o 空间性能和时间性能 F 正确性和简明性G.可读性和文档性。H.数据复杂性和程序复杂性(7)算法的时间复杂度与()有关.A.问题规模。B.计算机硬件性能C.编译程序的质量。D。程序设计语言(8)算法的时间复杂度与()有关.A 问题规模

7、。B.待处理数据的初态C.算法的易读性。口5和 8(9)某算法的时间复杂度是0(n 与，表 明 该 算 法(A。问题规模是南。B.执行时间等于r?C.执行时间与n?成正比。D.问题规模与r?成正比(10)下面说法错误的是()算法原地工作的含义是指示不需要如何额外的辅助空间在相同的规模n 下，复杂度O(n)的算法在时间上总是优于复杂度0(2)的算法所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界同一个算法，实现语言的级别越高，执行效率就越低(I I)算法for(i=n 1;i)=1 ;i )。fo r (j=1;j 2 上+1)2 口 与 2 口+1交换；其 中n 为正整数，则最后一行语

8、句的频度(执行次数)在最坏情况下是()。A,O (n)B.O (n log2n)C.O (n3)。D.O (n2)(12)算法的时间复杂度属于一种()。A.事前统计的方法。B o 事先分析估算的方法C.事后统计的方法。D,事后分析估算的方法(13)设 某 算 法 完 成 对 n 个 元 素 进 行 处 理，所 需 的 时 间 是 T(n)=1 0 0 nlog2n+200n+50 0,则该算法的时间复杂度是().A.O (1)0 0 B.O (n)C.O (nl o g2 n)D.O (n lo g 2n+n)(14)假设时间复杂度为0(n?)的算法在有200个元素的数组上运行需要3.1m s

9、,则在有400个元素的数组上运行需要()ms A。3。1 B.60 2。C.12o 4。D。x(无法确定)(15)下列程序段加下划线的语句执行()次。fo r (m=0,i=1;i=1;i+)。for(j=1 ;j j)J+;eIse i+;fo r (i=1;i =n;i+)for(j=1;j =i;j+)。fo r(k=1;k=j;k+)。x+;i=1;k=0；d o(o k=k+10*i;。i+;w h ile (i =n)y=0；w h i Ie(y+1)*(y+1)=n)y=y+l for(i=0;i n;i+)f o r(j=0；j m ；j+)a i j =0;(18)有实现同一

10、功能的两个算法A 1和A 2,其 中A1的时间复杂度为T尸O (2),A2的时间复杂度为Tz=O(n2),仅就时间复杂度而言，请具体分析这两个算法哪一个好。综合应用题(19)设n是偶数，且有程序段：f o r (i=1 ；i=n；i+)if(2*i=n)。f or(j=2*l;j next。B.p-n e x t=p n e x tC.p=p n e x t ne x t 。D.p=p-n ex t ;p ne x t =p-nex t ne x t(8)在一个单链表中，已知q所指结点是p所指结点的直接前驱，若在q和p之间插 入s所指结点，则 执 行()操作。Ao s next=p-next;

11、p-n ext=s;。B.qne x t =s;s-next=p;C.p n e x t =s n e x t;s-n e xt=p;。D.p-n e xt=s;s-next=q(9)在一个长度为n(n1)的带头结点的单链表h上，另设有尾指针r指向尾结点,执 行()操作与链表的长度有关。A 删除单链表中的第一个元素B.删除单链表中的最后一个元素C.在单链表第一个元素前插入一个新元素D.在单链表的最后一个元素后插入一个新元素(10)在单链表中附加头结点的目的是为了().A.保证单链表中至少有一个结点。B.标识单链表中首结点的位置C.方便运算的实现。D.说明单链表是线性表的链式存储(11)将 长

12、度 为 n 个单链表链接在长度为m 的单链表之后的算法，其时间复杂度是().A.O (1 )0 0 6 B.O (n)o C.O (m)D.O (n+m)(12)循环单链表的主要优点是()。A.不再需要头指针了B。从表中任一结点出发都能扫描到整个链表C.已知某个结点的位置后，能够容易找到它的直接前驱D.在进行插入、删除操作时，能更好地保证链表不断开(13)将线性表(a,a z,，为)组织为一个带头结点的循环单链表，设 H 为链表的头指针，则 链 表 中 最 后 一 个 结 点 的 指 针 域 中 存 放 的 是().A.变量H 的地址。B.变量H 的值C o 元 素a i的地 址。D.空指针(

13、14)非空的循环单链表L 的尾结点p 满 足().A.p=NULl_ B.p n e xt=NULL C.p-n e x t=L。D.p=L(15)若要在0(1)的时间内实现两个循环单链表的首尾相接，则两个循环单链表应各设一个指针，分 别 指 向()。A.各自的头结点。B.各自的尾结点C.各自的第一个元素结点。D.一个表的头结点，一个表的尾结点(16)设线性表非空，()可以在0(1)的时间内在表尾插入一个新结点。A.带头结点的单链表，有一个链表指针指向头结点B o 带头结点的循环单链表，有一个链表指针指向头结点C.不带头结点的单链表，有一个链表指针指向表的第一个结点D.不带头结点的循环单链表，

14、有一个链表指针指向表中某个结点(除第一个结点外)(17)设指针r e a r 指向带头结点的循环单链表的尾指针，若要删除链表的第一个元素结点，正确的操作是()。A.s=re a r;re a r=r ear next;B.re a r=r ear-n e x t;C.rea r=r e a r-n ext n e x t;D.s=r e ar ne x t -n ex t ;r ear-next n ext=s-n ext；(18)设有两个长度为n 个单链表，以 h i 为头指针的链表是非循环的，以 h 2 为尾指针的链表是循环的，则()。A.在两个链表上删除第一个结点的操作，其时间复杂度均为

15、O (1)B.在两个链表的表尾插入一个结点的操作，其时间复杂度均为O (n)C.循环链表要比非循环链表占用更多的存储空间D.循环链表要比非循环链表占用更少的存储空间(19)使用双链表存储线性表，其优点是可以()。A.提高查找速度。B.更方便数据的插入和删除C.节约存储空间。D.很快回收存储空间(2 0)与单链表相比，双链表的优点之一是()。A.插入和删除操作更简单 B.可以进行随机访问C.可以省略表头指针或表尾指针 D.访问其后相邻结点更灵活(2 1)带头结点的循环双链表L为空表的条件是()。A.Lnextp r ior=NULl_。B.L-)pr ior=LC.Lne x t=L。D.B 和

16、 C 都对(2 2)在循环双链表的p所指结点后插入s所指结点的操作是()oA.p-n e x t=s;s-pr i or=p;pn e x tpr i o r=s;s-ne x t=p-nex t;B.p-next=s;p nextpr i o r=s；s-p r i o r=p;s-n e x t=pnext;C.s-pr ior=p；sn e x t=p_)n e xt;p-nex t=s;p n e x t-pr i or=s；D.s-pr ior=p;sne x t=p-next;p-next-pr ior=s;p n e x t=s;(2 3)在 双 链 表 中 指 针p a所 指

17、结 点 后 面 插 入p b所指结点，执行的语句序列是(pb-n e x t=p a n e x t;。pb p r ior=pa;pa-next=pb;。pa-nex t pr ior=p b;A.。B.。C.。D.(2 4)在一个双链表中，删除结点p的 操 作 是()oA。p)p r i or n e x t=p next；p n e xt p r i o r=p pr i or；B.p-p r ior=p-p r i orpr i o r;pp r ior-p r ior=p;C.p-ne x tpr i or=p;pnext=p-ne x t-nex t;D.p-next=p p r

18、ior-pr io r;p pr ior=p pr iorpr i or;应用题(2 5)单链表设置头结点的作用是什么？(2 6)线性表的顺序存储结构具有三个弱点：其一，插入或删除操作需要移动大量元素；其二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用：其三，表的容量难以扩充。试问，线性表的链接存储结构是否能够克服上述三个弱点？(2 7)若频繁地对一个线性表进行插入和删除操作，该线性表采用什么存储结构比较好？(2 8)设n表示线性表中的元素个数，P表示指针所需的存储单元大小，E表示存储数据元素所需的存储单元大小，则使用单链表存储方式存储该线性表需要多少存储空间(不考虑头

19、结点)？算法设计题(29)设计算法依次打印单链表中每个结点的数据信息。(30)求单链表的长度。(31)设计算法将值为x的结点插入到不带头结点的单链表L中值为k的结点之前，若找不到值为k的结点，则 将x插入到链表的末尾。(32)判断非空单链表是否递增有序。(33)已知非空线性链表由lis t指出，结点结构为(d at a,I ink)。请编写算法，将链表中数据域最小的结点移到链表的最前面。要求：不得额外申请新的结点。(34)给定一个带头结点的单链表，设head为头指针，设计算法按递增次序输出单链表中各结点的数据元素，并释放结点所占的存储空间(要求：不允许使用数组作辅助空间)。(35)已知非空线性

20、链表由l i s t指出，设计算法交换p所指结点与其后续结点在链表 中 的 位 置(设p所指结点不是链表的最后一个结点)。(36)设计算法实现将单链表就地逆置。(37)头插法建立单链表.(38)尾插法建立单链表(39)复制一个单链表。(40)设计算法实现将单链表就地逆置。(41)在一个有序单链表(假设从小到大排列)中插入一个元素值为x的结点，使得插入后单链表仍然有序.(42)设单链表以非递减有序排列，设计算法实现在单链表中删去值相同的多余结点。(43)已知单链表中各结点的元素值为整型且递增有序，设计算法删除表中大于mink且小于m a x k的所有元素，并释放被删结点的存储空间.(44)有两个

21、整数序列A=(ai,a2,am)和B=(b”b2,b )已经存入两个单链表中，设计算法判断序列B是否是序列A的子序列.(45)设线性表0=(a,b,a2,b2,a,b)采用带头结点的单链表存储，设计算法将表C拆分为两个线性表A和B,使 得A=(a“az,-,a),B=(bi,b2,b)(46)有两个递增有序的单链表la和lb,设计算法将这两个单链表合并为一个有序链表。(47)有两个有序的单链表，一个表为升序，另一个表为降序，设计算法将这两个链表合并为一个有序链表。(48)已知单链表A和B的数据(设为整型)递增有序，设计算法利用原有结点，将表A中与表B具有相同值的结点删除，将表B中与原表A不同值

22、的结点存入表A中，并保持表A的递增有序。(49)设计算法将循环单链表就地逆置。(50)已知L为单链表的头结点地址，表中共有m(m3)个结点，从 表 中 第i个(1i n ext(4)线性表的静态链表存储与顺序存储相比,优点是().A.所有基本操作的算法实现简单。B 便于随机存取C.便于插入和删除。D。便于利用零散的存储空间(5)下图所示数组中以静态链表形式存储了一个线性表，设头指针为a0.link,则该线性表的元素依次为()OC.74,25 ,4 5 ,60,4 0,63。D。25,4 5 ,60,40,6 3 ,746 线性表综合选择题(1)下面关于线性表的叙述中，错 误 的 是().A。线

23、性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作C.线性表采用链接存储，不必占用一片连续的存储单元D.线性表采用链接存储，便于插入和删除操作(2)若某线性表中最常用的操作是取第i个元素和找第i个元素的前驱，则采用()存储方法最节约时间。A.顺序表。B o单链表。C.双链表 D.循环单链表(3)若链表中最常用的操作是在最后一个结点之后插入一个结点和删除第一个结点，则 采 用()存储方法最节约时间。A o单链表。o B o循环双链表C.循环单链表。D.带尾指针的循环单链表(4)设线性表有n个元素，以下操作中，()在顺序表上实现比在链表上实现的效率更高。A.

24、输 出 第i(1 W iW n)个元素值B.交换第1个和第2个元素的值C.顺序输出所有n个元素D.查找与给定值x相等的元素在线性表中的序号(5)如果对于具有n(n 1)个元素的线性表的基本操作有4种：删除第一个元素；删除最后一个元素；在第一个元素前插入新元素；在最后一个元素的后面插入新元素。则 最 好 使 用()。A.只设尾指针的循环单链表B.只设尾指针的非循环单链表C 只设头指针的循环双链表D.同时设置头指针和尾指针的循环单链表应用题(6)请比较线性表的两种基本的存储结构顺序表和单链表。(7)举例说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，算法的效率不同。(8)如果某线性表中数据

25、元素的类型不一致，但是希望能根据下标随机存取每个元素，请为这个线性表设计一个合适的存储结构。(9)线性链表有哪几种常见的变形？各有何特点？算法设计题(10)用顺序表表示集合，设计算法实现集合的求交集运算.(11)用顺序表表示集合，设计算法实现集合的求并集运算。(12)用顺序表表示集合，设计算法实现集合的求差集运算，要求不另外开辟空间。(13)假定以有序表表示集合，设计算法判断两个给定集合是否相等.(14)设两个单链表L1和L2分别表示两个集合,设计算法判断L1是否是L 2的子集。(15)已知两个不带头结点的单链表A和B分别表示两个集合，并且其元素值递增有序，求A、B的交集C,并以同样的递增形式

26、存储，要求尽可能节省时间。(16)在某商店的仓库中，对电视机按其价格从低到高建立一个单链表，链表的每个结点指出同样价格的电视机的台数。现 有 m台价格为n 元的电视机入库，请编写算法完成仓库的进货管理。(17)从键盘输入n 个英语单词，输入格式为n,wi,W 2,w,其 中 n 表示随后输入英语单词个数，试编写算法建立一个单链表，要求：如果单词重复出现，则只在链表上只保留一个：统计单词重复出现的次数，然后输出次数最多的前k(k 0)个人围成一个圈，每个人持有一个密码m (m=1 ),从 第 1 个人开始报数，报 到 m时停止报数，报 m 的人出圈，再从他的下一个人起重新报数，报 到 m时停止报

27、数，报 m的出圈，如此下去，直到所有人全部出圈为止。当任意给定n 和 m后，设计算法求n 个人出圈的次序。(21)编写算法，完成下述要求：建立一个链表用于存放输入的二进制数，链表中的每个结点的d ata域存放一个二进制住。在此链表上实现对二进制数加1 的运算，并输出运算结果.(22)有一个不带头结点的单链表h,通过遍历链表将链表中所有的链接方向逆转，算法如下，请在空格处填写正确的语句.v o id I n v e r s e (&h)if()re t urn;。p=h next;pr=NULL;while()h n ext=p r；p r=h;h=p;(23)设两个带头结点的单链表A 和 B,

28、表中结点的数据为整型，下面算法产生表A和表B 的并集并以表0 存储，请填写算法中空白处的语句，完成其功能。7栈的基本概念选择题(1)经过以下栈运算后，X 的 值 是().InitS t a c k(s),Push(s,a),Push(s,b),Pop(s,x),G e tTop(s,x)A.a o B.b C.1 D.0(2)经过以下栈运算后，S t a ckEm p ty(s)的值是()。Ini t Sta c k(s),P u sh(s,a),Pus h(s,b),Pop(s,x),P o p(s,y)A.a B.b C.1 o D.0(3)()不是栈的基本运算。A.删除栈顶元素。B.删除

29、栈底元素C。判断栈是否为空。D.将栈置为空栈(4)设有一个空栈，栈顶指针为1000H(十六进制，下 同)，每个元素需要1 个单位的存储空间，则执行 PUSH,PUSH,POP,PUSH,POP,PUSH,POP,PUSH 操作后,栈顶指针值为().A.10O2H。B.1003H。0.1 004H。D.1005H(5)一个栈的入栈序列是1,2,3,4,5 ,则栈的不可能的输出序列是()。Ao(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 个输出元素是()。Ao 不确定 B

30、o n io C.n-i 1 。D。n i+1(7)若一个栈的输入序列是1,2,3,，n,其输出序列是p“pz,，p.,若 p尸3,则 P2的 值().A,一定是2。B.一定是1 。C 不可能是1 D o 以上都不对(8)若一个栈的输入序列是小，p z,，p”其输出序列是1,2,3,n,若 p 3=1,则 p i的 值()OA。可能是2 B 一定是2。C 不可能是2 D.不可能是3(9)当字符序列t3 _ 依次通过栈，输出长度为3 且 可 用 作 0 语言标识符的序列有(_ _ _ _ _ _A.4 个。B.5 个。C.3 个。D.6 个应用题(10)设有一个栈，元素进栈的次序为A,B,C,D

31、,E,能否得到如下出栈序列，若能，请写出操作序列，若不能，请说明原因。C,E,A,B,D。C,B,A,D,E(1 1)在操作序列 p u s h (1)、p u s h(2),p o p、p u s h (5)、p u s h (7 )、p o p,pu s h(6)之后，栈顶元素和栈底元素分别是什么？(p u s h(k )表示整数k入栈，p o p表示栈顶元素出栈。)(1 2)设元 素1、2、3、P、A依次经过一个栈，进栈次序为1 2 3 P A，在栈的输出序列中，有哪些序列可作为C+程序设计语言的变量名.(1 3)如果进栈序列为A、B、C、D,则可能的出栈序列是什么？算法设计题(1 4)

32、假 设 以I和0分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和0组成的序列，称可以操作的序列为合法序列，否则称为非法序列.下面所示的序列中哪些是合法的？A.I O I I O I O O B.1 0 0 1 0 I 1 0 C 1 1 1 0 1 0 1 0 。D.I I 1 0 0 1 0 0通过对的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返 回t r u e,否则返回f al s e (假定被判定的操作序列已存入一维数组中)。8 4顺序栈选择题(1)在一个具有n个单元的顺序栈中，假定以地址低端(即下标为0的单元)作为栈底，以t o p作为

33、栈顶指针，当出栈时，t o p的 变 化 为(),A.不变。B o t o p=0 。C.t o p 1。D.t o p =t o p +1(2)设数组S n 作为两个栈S 1和S 2的存储空间，对任何一个栈只有当S n 全满时才不能进行进栈操作.为这两个栈分配空间的最佳方案是()。A.S 1的栈底位置为O,S2的栈底位置为n-1B.S 1的栈底位置为0,S 2的栈底位置为n/2C.S 1的栈底位置为0,S 2的栈底位置为nD.S1的栈底位置为0,S2的栈底位置为1(3)为了增加内存空间的利用率和减少溢出的可能性，两个栈共享一片连续的内存空间时，应将两栈的栈底分别设在这片内存空间的两端，这样，

34、当()时才产生上溢。A.两个栈的栈顶同时到达栈空间的中心点B.其中一个栈的栈顶到达栈空间的中心点C.两个栈的栈顶在栈空间的某一位置相遇D.两个栈均不空，且一个栈的栈顶到达另一个栈的栈底(4)两个栈共享一个数组空间的好处是()。A.减少存取时间，降低发生上溢的可能性B.节省存储空间，降低发生上溢的可能性C.减少存取时间，降低发生下溢的可能性D.节省存储空间，降低发生下溢的可能性算法设计题(5)假 设 以I和0分别表示入栈和出栈操作。栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅有I和0组成的序列，称可以操作的序列为合法序列，否则称为非合法序列。下面所示的序列中哪些是合法的？通过对的分析，写

35、出一个算法，判定所给的操作序列是否合法。若合法，返 回true,否则返回fa l se(假定被判定的操作序列已存/n ex t =s;。B.s n ext=h;C.s-nex t =h;h-n ext=s。Do s-n e x t=h-n e x t;hn e xt 二s;(2)从栈顶指针为t o p的链栈中删除一个结点，用x保存被删除结点的值，则执行()oA.x=t o p;t op=top-n ext。B x=t o p d a t a;C.top=top n e x t;x=t o p da ta;。D.x=top d ata;t op=top-n e x t;1 0队列的基本概念选择题

36、(1)队 列 的“先进先出”特 性 是 指(_)。A.最后插入队列中的元素总是最后被删除B 当同时进行插入、删除操作时，总是插入操作优先C.每当有删除操作时，总要先做一次插入操作D.每次从队列中删除的总是最早插入的元素(2)允许对队列进行的操作有()oA.对队列中的元素排序。B.取出最近入队的元素C.在队头元素之前插入元素。D.删除队头元素(3)一个队列的入队顺序是1、2、3、4,则队列的榆出顺序是()。A.432 1。B 123 4 C.1432。D。324111 4顺序队列选择题(1)循环队列存储在数组A 0 m 中，则入队时的操作为()。Ao rear=r e a r+1 。B.r e

37、a r=Cre a r+1 )mod (m-1)C.rea r=(rear+1)mod m。Do rea r=(rear+1)mo d (m+1 )(2)若用一个长度为6 的数组来实现循环队列，且当 前 r e a r 和 fr o n t 的值分别为 0 和 3,则从队列中删除一个元素，再增加两个元素后，re a r 和 f r o n t 的值分别 为()oA.1 和 5。Bo 2 和 4。C.4 和 2。D.5 和 1(3)已知循环队列的存储空间为数组A 2 1 ,f r o n t 指向队头元素的前一个位置，r e a 指向队尾元素，假设当前f r o n t和 r e a r 的值分

38、别是8 和 3,则该队列 的 长 度 为()oA。5。B.6。C.16 D.17(4)如图所示为一个元素类型为字符型的环形队列，如 果 f r o n t 指向队头元素的前一个位置，r e a r 指向队尾元素，则所表示的队列为()。1 22ThefI0weR1sbeauTifu1T r ear T f ron tA.The f。Bo be a ut i f ul The f C.flower is。Do ea utifu I The f应用题(5)举例说明顺序队列的“假溢出”现象。(6)简述顺序队列假溢出的避免方法及队列满或空的判定条件。(7)在操作序列 EnQu e ue(1 )、EnOu

39、e u e(3)DeQueue、EnQue u e(5)、EnQueu e(7)DeQueue、E n Queue(9)之后，队头元素和队尾元素分别是什么？(EnQ u eue(k)表示整数k入队，DeQu e u e表示队头元素出队。)算法设计题(8)在循环队列中设置一个标志f l a g,当f ront=rear且f lag=O时为队空，当f r o n t=re a r且f I a g=1时为队满。编写相应的入队和出队算法.(9)如果设置一个计数器co u n t累计队列的长度，则 当count=0时队列为空，当cou n t=QueueS i z e时队列为满。试设计相应的入队和出队算

40、法.(10)1 2链队列选择题(1)用不带头结点的单链表存储队列时，其队头指针指向队头结点，队尾指针指向队尾结点，则执行删除操作时，().A.仅修改队首指针。B。仅修改队尾指针C.队首指针和队尾指针都需要修改。D.队首指针和队尾指针可能都需要修改(2)在链队列中，设指针f和r分别指向队首和队尾，则插入s所指结点的操作是().A.f next=s;f=s;。B.r n e xt=s;r=s;C.s)next=r;r=s;D.s-ne x t=f;f=s；(3)设循环单链表表示的队列长度为n,若只设头指针，则进队操作的时间性能为()。Ao O (n)B.O (1)。C.O (n2)D.O (n I

41、 o g 2n)(4)最 不 适 合 用 作 链 队 列 的 链 表 是().A.只带队首指针的非循环双链表。B.只带队首指针的循环双链表C.只带队尾指针的循环双链表。Do只带队尾指针的循环单链表算法设计题(5)假设以不带头结点的循环链表表示队列，并且只设一个指针指向队尾结点，但不设头指针.试设计相应的入队和出队算法。13 4栈和队列的应用选择题(1)设计一个判别表达式中左右括号是否配对的算法，采 用()数据结构最佳。A.顺序表。B。栈。C.队列。D.链表(2)如果数据是在程序的运行过程中逐步产生的，并且要求先产生的数据后处理，后产生的数据先处理，则最合适的数据结构是()。A。顺序表。B o顺

42、序栈。C.顺序队列 D。堆(3)在解决计算机主机和打印机之间速度不匹配问题时通常设置一个打印缓冲区，该缓冲区应该是一个()结构。A.栈。B.队 列。C.数组。D。线性表(4)执 行()操作时，需要使用队列作为辅助数据结构。A。深度优先遍历图。B.广度优先遍历图C.散列查找。D.遍历二叉树(5)表 达 式3*2八(4+2*2 6*3)5求值过程中当扫 描 到6时，对象栈和算符栈为()，其 中-表示乘森。A.3,2,4,1 ,1；#*-(+*-。B.3,2,8；#*八 一C.3,2,4,2,2；#*八(一。D.3,2,8；#*八(6)利用栈计算表达式的值时，设置操作数栈OPND,设OPND只有存储

43、单元，计算下列表达式是不发生上溢 的 是()。Ao a-b*(c _d)o B.(a一 b)*c一 d 。C.(a b*c)-d 。D.(a一 b)*(cd)(7)与中缀表达式a*b+c/d-e等价的前缀表达式是()。A.1-*a b/cd e B.*+/ab c d e C.+*a b 一/c d e。D。*ab+cd/e(8)解 决h a n o i塔问题的递归算法，其时间复杂度是()。A.O (n)Bo O(n2)。C。O (2)。D.O (n!)(9)4个圆盘的汉诺塔，总的移动次数为().A.7。o o Bo 8。o C.15。o D.16(10)一个递归的求解过程可以用递归函数求解，

44、也可以用非递归函数求解，从运行时间上看，通常递归函数要比非递归函数().A.快一些。B。慢一些。C.相同。D.无法比较(11)栈和队列的主要区别在于()A 它们的逻辑结构不一样。B 它们的存储结构不一样C,所包含的运算不一样。D.插入、删除运算的限定不一样(12)栈和队列的共同点是()。A.都是先进先出。B.都是先进后出C.只允许在端点处插入和删除元素。D.没有共同点(13)栈和队列具有相同的()。A.逻辑结构。B.抽象数据类型。C.存储结构 D.运算(14)设栈S和队列Q的初始状态为空，元素e1、e2、e 3、e4、e5、e6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出队的顺序是e

45、2、e 4、e3、e 6、e5、e1,则栈S的容量至少应该是()。A.6 B.4 C.3 o o D.2算法设计题(15)假设一个算术表达式中可以包含三中括号：园 括 号“(”和“)”，方括号和“以及花括号“”和 ,且这三种括号可按任意的次序嵌套使用。编写算法判断表达式中所含括号是否配对出现。(16)设计算法把一个十进制整数转换为二至九进制之间的任一进制数输出.(17)设计递归算法求解在n元集合A=1,2,，n 中选取k(k/n)个元素的所有组合。例如，从集合1,2,3,4)中选取2个元素的所有组合为：1,2,1 ,3,1 ,4,2,3,2,4,3,4。(18)已 知Q是一个循环队列，S是一个

46、顺序栈，设计算法实现将队列中所有元素逆转。(19)设 栈S中有2 n个元素，从栈顶到栈底的元素依次为a m a z e,，a 2,a”要求通过一个循环队列重新排列栈中元素，使得从栈顶到栈底的元素依次为a?”a2 n-2,，az,a2I,a2n-3,，a 请设计算法实现该操作，要求空间复杂度和时间复杂度均为O (n).(20)利用两个栈S1和S2模拟一个队列，已知栈的三个运算定义如下：PUSH(ST,x)元 素x入ST;POP(ST,x)ST栈顶元素出栈，赋给变量x;Sem p ty(S T)判ST栈是否为空.那么如何利用栈的运算来实现该队列的三个运算：enqueue插入一个元素入队列：d e

47、q ueue删除一个元素出队列；q u eu e _em p t y判断队列是否为空。(21)一个双端队列Q是限定在线性表的两端(LE F T端 和RIGHT端)都可以进行插入和删除操作的线性表，队列为空的条件是LEFT=RIGHT。若采用顺序存储结构存储双端队列，要求：定义双端队列的存储结构；给出在指定端L(表 示 左 端)和R(表 示 右 端)进 行 插 入(Que u e Inser t)和删除(Qu e ueDe I e te)操作的算法。14 4数组选择题(1)数组通常具有的两种基本操作是()。A 查找和修改 B 查找和索引。C.索引和修改。D.建立和删除(2)将数组称为随机存取结构

48、是因为(A.数组元素是随机的。B.对数组任一元素的存取时间是相等的C.随时可以对数组进行访问。D 数组的存储结构是不定的(3)下面说法中，不 正 确 的 是()。A.数组是一种线性结构B.数组是一种定长的线性结构C.除了插入和删除操作外，数组的基本操作还有存取、修改、检索和排序等D数组的基本操作有存取、修改、检索和排序等，没有插入和删除操作(4)二维数组SZ 3。.5,。1 0 含有的元素个数是()A.8 8 o o B.99。C.8 0。D.9 0(5)数组A。5,0.6的每个元素占五个字节，将其按列优先次序存储在起始地址为1 000的内存单元中，则元素A 5,5 的 地 址 是()。A 1

49、175 B 1180。Co 1 2 0 5。D.1 210(6)C语言中定义的整数一维数组a 5 0 和二维数组b 10 5 具有相同的首元素地址，即&0)=&(1300),在以列序为主序时，218的地址和()的地址相同。A.b 1 7 Bo b1 8 C.b 8 1 D.b 7 1(7)二维数组A的每个元素是由6个字符组成的串，行下标的范围从。8,列下标 的 范 围 是0 9,则 存 放A至 少 需 要()个字节，A的第8列 和 第5行共占()个字节，若A按行序优先方式存储，元素A 8 5 的起始地址与当A按列优先存储时的()元素的起始地址一致。A 90 B 1 80。C。2 4 0。D.5

50、40E.108 o o F.114 G.54。H.A 8 5I.A 3 1 0 J A 5 8。K.A 4 9(8)三维数组A 8,8,1 0 采用行序为主的方式从地址A 0,0,0开始存放，假设每个元素占用存储空间大小为L,则元素A 3,2,8 的存放位置是()。A。A0,0,0+198*L。o B.A 0,0,0+1 08*LC A 0,。，0+2 68*L o。D.A 0,0,0+13*L算法设计题(9)若在矩阵A中存放一个元素a,.j(0W iW n-1,OWjWm 1 )，该元素是第i行元素中最小值且又是第j列元素中最大值，则称此元素为该矩阵的一个马鞍点。假设以二维数组存储矩阵A,试