数据结构课后练习题汇编.pdf

《数据结构课后练习题汇编.pdf》由会员分享，可在线阅读，更多相关《数据结构课后练习题汇编.pdf（54页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构课后练习题第一章绪论-、选择题1、数据结构被形式定义为（D,S）,其 中 口 是（）的有限集合，S 是 D 上 的（）有限集合。A、算 法 B、数 据 元 素 C、数 据 操 作 D、逻 辑 关 系 E、操 作 F、映 象 G、存 储 H、关系2、数据结构是一门研究非数值计算的程序设计问题中计算机的（1）以及它们之间的（）和运算的学科。（1）A、操作对象 B、计算方法 C、逻辑存储 D、数据映象（2）A、结构 B、关系 C、运算 D、算法3、算法分析的目的是（），算法分析的二个主要方面是（A、给出数据结构的合理性 B、研究算法中输入输出的关系C、空间复杂性和时间复杂性D、分析算法的效率

2、以求改进E、正确性和简明性F、分析算法的易懂性和文档性4、在数据结构中，从逻辑上可以把数据结构分成（）。A、动态和静态结构B、紧凑接和非紧凑结构C、线性与非线性结构D、内部结构和外部结构5、计算机算法指的是（），它必具备输入、输 出 和（）5 个特性。A、计 算 方 法 B、排 序 方 法 C、解决问题的有限运算序列D、可行性、可移植性和可扩充性E、可行性、确定性和有穷性6、线性表的顺序存储结构是一种（）的存储结构，线性表的链式存储结构是 种（）A、随 机 存 取 B、顺 序 存 取 C、索引存取 D、散列存取7、算法的时间复杂度取决于（）A、问 题 的 规 模 B、待处理数据的初态C、问题的

3、规模和待处理数据的初态8、线性表若采用链表存储结构时，要求内存中可用存储单元的地址（）A、必须是连续的 B、部分地址必须是连续的C、一定是不连续的 D、连续不连续都可以9、在以下的叙述中，正确的是（）A、线性表的线性存储结构优于链式存储结构B、二维数组是它的每个数据元素为一个线性表的线性表C、栈的操作方式是先进先出D、队列的操作方式是先进后出10、根据数据元素之间关系的不同特性，以下四类基本的逻辑结构反映了四类基本的数据组织形式。以下解释错误的是（）A、集合中任何两个结点之间都有逻辑关系但组织形式松散B、线性结构中结点按逻辑关系依次排列形成一条“锁链”C、树形结构具有分支、层次特性，其形态有点

4、像自然界中的树D、图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接11、以下说法正确的是（）A、数据元素是数据的最小单位B、数据项是数据的基本单位C、数据结构是带有结构的各数据项的集合D、数据结构是带有结构的数据元素的集合二、填空题1、数据逻辑结构包括（）四种类型，树型和图型结构合称（）。2、对于给定的n个元素，可以构造出的逻辑结构有（）、（）、（）和（）四种。3、算法的五个重要特性是（）。4、评价算法的性能从利用计算机资源角度看主要从（）方面进行分析。5、线性结构中元素之间存在（）关系，树型结构中元素之间存在（）关系，图型结构中元素之间存 在（）关系。6、下面程序段的时间复杂度

5、是（）。i=s=O;w h i l e（s n）i+;s+;7、下面程序段的时间复杂度是（）。s=0;f o r（I=0;k n;I+）f o r（j=0;j m;j+）s+=a i j；8、所 谓 数 据 的 逻 辑 结 构 指 的 是 数 据 元 素 之 间 的。9、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容。1 0、在线性结构中，开始结点 前驱结点，其余每个结点有且只有一个结点。1 1、在树形结构中，根 结 点 只 有,根结点无前驱，其余每个结点有且只有 前驱结点；叶子结点没有 结点，其 余 每 个 结 点 的 后 继 结 点 可 以。1 2、在图形结构

6、中，每 个 结 点 的 前 驱 结 点 和 后 继 结 点 可 以 有。1 3、存储结构是逻辑结构的 实现。1 4、从数据结构的观点看，通常所说的数据”应分成三个不同的层次，即、和1 5、根据需要，数 据 元 素 又 被 称 为、或。1 6、通常，存 储 结 点 之 间 可 以 有、四种关联方式，称为四种基本存储方式。1 7、通常从、等几方面评价算法的（包括程序）的质量。1 8、一 个算法的时空性能是指该算法的 和，前者是算法包含的.后 者 是 算 法 需 要 的。1 9、在一般情况下，一个算法的时间复杂性是 的函数。2 0、常见时间复杂性的量级有：常数阶0（）、对数阶0（）、线性阶0 （）、

7、平方阶0（）、和指数阶0（）。通常认为，具有指数阶量级的算法是 的。2 1、数据结构的基本任务是数据结构的 和。2 2、数据对象是性质相同的 的集合。2 3、抽象数据类型是指一个 以及定义在该模型上的一组操作。三、判断题1 .数据元素是数据的最小单位。2 .数据结构是带有结构的数据元素的集合。3 .数据结构，数据元素，数据项在计算机中的映象分别称为存储结构，结点，数据域。4.数据项是数据的基本单位。5 .数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要建立的。6 .数据的物理结构是数据在计算机中实际的存储形式。7 .算法和程序没有区别，所以在数据结构中二者是通用的。8 .顺序存储结

8、构属于静态结构，链式存储结构属于动态结构。四、计算应用题1、设n为正正数。确定下列各程序段中前置以记号 的语句的频度。（1）I=l;k=0;While(In-l)k+=10*I;1+；k=0;for(I=l;I=n;I+)for(j=I；j=n;j+)k+;(2)I=l；j=O;While(I+jj)j+;else 1+;2、写出下面算法中带标号语句的频度。Void perm(int a,k,n)int xj;(1)if(k=n)(2)for(I=1 ;I=n;I+)(3)printf(d”,aI);else(4)for(I=k;I=n;I+)(5)aI+=I*I;(6)perm(a,k+l,

9、n);执行函数调用语句perm(a,l,n)3、指出下列两个算法的时间复杂度。(1)int sum 1 (int n)int p=l,sum=0,I;for(I=1 ;I=n;I+)p*=I;sum+=p;return(sum);(2)int sum2(int n)int sum=0,I,j;for(I=l;I=n;I+)p=1 ;for(j=1 ;j=I;j+)p*=j;sum+=p;returm(sum);4、有下列几种用二元组表示的数据结构，画出它们对应的逻辑图形表示，并指出它们属于哪种结构。(1)A=(K,R),其 中:K=a,b,c,d,e,f,g,h R=(r)r=,(2)B=(K

10、,R)淇 中:K=a,b,c,d,e,f,g,h R=(r)r=,(3)C=(K,R),其中：k=1,2,345,6 R=r r=(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)(4)D=(K.R),K=48,25,64,57,82,36,75),R=rl,r2rl=,r2=,5、设有如图所示的逻辑结构图，给出它的逻辑结构。KI6、简述下列术语：数据，数据元素，数据结构，数据对象。7、逻辑结构与存储结构是什么关系？8、将 数 量 级 n,n2,n nlog2n,log2n,2n,品,n!,（2/3）,n2）按增长率进行排列。五、算法设计题1.已知输

11、入x,y,z三个不相等的整数，设计一个算法，使得这三个数按从大到小输出，并考虑所用算法的比较次数和元素移动次数。2.编写在输入10个数中找出最小或最大的数的算法。3.在数组An中查找值为k 的元素，若找到则输出其位置i（lWiWn）,否则输出0 作为标志。设计求解此问题的类C 语言算法，并分析其最坏情况时间复杂度。第二章线性表练习题一、选择题1、表长为N 的顺序表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（），删除一个元素需要移动的元素个数为（）。A.（N-l）/2 B.N C.N+l D.N-l E.N/2 F.（N+l）/2 G（N-2）/22、线

12、性表是具有N 个（）的有限序列。A、表 元 素 B、字 符 C、数据元素 D、数据项 E、信息3、”线性表的逻辑顺序和物理顺序总是一致的。”这个结论是（）。A、正 确 的 B、错误的 C、不一定，与具体结构有关。4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（）oA、必须是连续的 B、部分地址必须是连续的 C、一定是不连续的 D、连续或不连续都可以。5、带头结点的单链表为空的判定条件是（）。A、head=NULL B、head-next=NULL C head-next=head D、head!=NULL6、不带头结点的单链表head为空的判定条件是（）。A、head=NULL B

13、、head-next=NULL C、head-next=head D、head!=NULL7、非空的循环单链表head的尾结点P 满 足（）。A、P-NEXT=NULL B、p=NULL C p-next=head D p=head8、在一个具有n 个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（）。A、0（1）B、0（n）C、0（n2）D、O（nlog2n）9、在一个单链表中，若删除P 所指结点的后继结点，则 执 行（）。A、p-next=p-next-next B、p=p-next;p-next=p-next-next C、p-next=p-next;D、p=p-next-ne

14、xt;10、在一个单链表中，若在P 所指结点之后插入S 所指结点，则 执 行（）。A、s-next=p;p-next=s;B、s-next=p-next;p-next=s;C、s-next=p-next;p=s;D、p-next=s;s-next=p;11、在一个单链表中，已知q 是 p 的前趋结点，若 q 和 p 之间插入结点s,则 执 行（）。A、s-next=p-next;p-next=s;B、p-next=s-next;s-next=p;C、q-next=s;s-next=p;D、p-next=s;s-next=q;12、假设双链表结点的类型如下：typedef struct link

15、nodeint data;/数据域struct linknode*llink;/指向前趋结点的指针域struct linknode*rlink;/指向后继结点的指针域bnode现将一个q 所指新结点作为非空双向链表中的p 所指结点的前趋结点插入到该双链表中，能iE确完成此要求的语句段是（）。A、q-rlink=p;q-llink=p-llink;p-llink=q;p-llink-rlink=q;B、p-Ilink=q;q-rlink=p;p-llink-rlink=q;q-llink=p-llinkC、q-llink=p-rlink;q-rlink=p;p-llink-rlink=q;p-l

16、link=q;D、以上都不对1 3、如上题结点结构，如在此非空循环双向链表的结点p 之后插入结点s 的操作序列是（）oA、p-rlink=s;s-llink=p;p-rlink-llink=s;s-rlink=p-rlink;B、p-rlink-s;p-rlink-llink=s;s-llink=p;s-rlink=p-rlink;C、s-llink=p;s-rlink=p-rlink;p-rlink=s;p-rlink-llink=s;D、s-llink=p;s-rlink=p-rlink;p-rlink-llink=s;p-rlink=s;14、在一个长度为n 的单链表上，设有头和尾两个指

17、针，执 行（）操作与链表的长度无关。A、删除单链表中的第一个元素 B、删除单链表中最后一个元素 C、在单链表第一个元素前插入一个新元素 D、在单链表最后个元素后插入一个新元素15、线性结构中的一个结点代表一个（）A、数据元素 B、数据项 C、数据 D、数据结构16、非空线性表L=（ai,a2,a，,an）,下列说法正确的是（）A、每个元素都有一个直接前驱和直接后继B、线性表中至少要有一个元素C、表中诸元素的排列顺序必须是由小到大或由大到小的D、除第一个元素和最后一个元素外其余每个元素都有一个且仅有一个直接前驱和直接后继17、顺序表是线性表的（）A、链式存储结构 B、顺序存储结构 C、索引存储结

18、构 D、散列存储结构18、对于顺序表，以下说法错误的是（）A、顺序表是用-维数组实现的线性表，数组的下标可以看成是元素的绝对地址B、顺序表的所有存储结点按相应数据元素间的逻辑关系决定的次序依次排列C、顺序表的特点是:逻辑结构中相邻的结点在存储结构中仍相邻D、顺序表的特点是:逻辑上相邻的元素，存储在物理位置也相邻的单元中19、对顺序表上的插入、删除算法的时间复杂性分析来说，通 常 以（）为标准操作。A、插入操作 B、结点移动 C、算术表达式 D、删除操作20、对于顺序表的优缺点，以下说法错误的是（）A、无需为表示结点间的逻辑关系而增加额外的存储空间B、可以方便地随机存取表中的任一结点C、插入和删

19、除运算较方便D、山于顺序表要求占用连续的空间，存储分配只能预先进行（静态分配）21、若某线性表中最常用的操作是取第i 个元素和找第i 个元素的前趋元素，则 采 用（）存储方式最节省时间。A、顺序表 B、单链表 C、双链表 D、单循环链表22、循环链表主要优点是（）A、不再需要头指针了B、已知某个结点的位置后，能够容易找到它的直接前趋C、在进行插入、删除运算时，能更好地保证链表不断开D、从表中任一结点出发都能扫描到整个链表23、在线性表的下列存储结构中，读取元素花费时间最少的是（）A、单链表 B、双链表 C、循环链表 D、顺序表二、填空题1、在线性结构中，第一个结点（）前趋结点，其余每个结点有且

20、只有（）个前趋结点。2、在顺序表中插入或删除一个元素，需要平均移动（）元素，具体移动的元素个数与（）有关3、已知L 是无表头结点的单链表，试从下列提供的答案中选择合适的语句序列，分别实现：（1）表首插入S 结点的语句序列是（）。（2）表尾插入S 结点的语句序列是（）。A、P-next=S;B、P=L;C、L=S;D、P-next=S-next;E、S-next=P-next;F、S-next=L;G、S-next=NULL;H、while（P-next!=Q）p=p-next;I、while（P-nexl!=NULL）P=P-next;4、已知L 是带表头结点的非空单链表，试从下列提供的答案中

21、选择合适的语句序列。（1）删除首元结点的语句序列是（），（2）删除尾元结点的语句序列是（）A、P=P-next;B、P-next=P-next-next;C、while（P!=NULL）p=p-next;D、while（Q-next!=NULL）P=Q;Q=Q-next;E while（P-next!=Q）P=P-next;F、Q=P;G Q=P-next;H、P=L;I、L=L-next;J、free（Q）;5、已知L 是带表头结点的非空链表，且 P 结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。（1）删除P 结点的直接后继结点的语句序列是（），（2）删 除 P

22、 结点的直接前趋结点的语句序列是（）A、P-next=P-next-next;B、P=P-Pnext-next;C、while（P-next!=Q）P=P-next;D、while（P-next-next=Q）P=P-next;E、Q=P;F、Q=P-next;G、P=L;H、L=L-next;I、free（Q）;6、已知结点编号，在各结点查找概率相等的情况下，从 n 个结点的单链表中查找一个结点，平均要访问（）个结点，从 n 个结点的双链表中查找一个结点，平均要访问（）个结点。7、对于一个具有n 个结点的单链表，在已知p 所指结点后插入一个新结点的时间复杂度是（）；在值域为给定值的结点后插入

23、一个新结点的时间复杂度是（）。8、单链表是（）的链接存储表示。9、单链表中设置头结点的作用是()。10、在单链表中，除首元结点外，任一结点的存储位置由()指示。11、在非空双向循环链表中，在结点q 的前面插入结点p 的过程如下：p-prior=q-prior;q-prior-next=p;p-next=q;();12、在双向链表中，每个结点有两个指针域，一个指向(),另一个指向()。13、顺序表中逻辑上相邻的元素的物理位置()相邻。单链表中逻辑上相邻的元素的物理位置()相邻。14、为了便于讨论，有时将含n(n20)个结点的线性结构表示成(a“a?,a j,其中每个去代表一个。ai称为 结点,a

24、称为 结点,i 称 为 由 在 线 性 表 中 的。对任意一对相邻结点ai、a+i(lWin),ai称为ai+i的直接，ai+i称为4 的直接。15、线性结构的基本特征是：若至少含有一个结点，则除起始结点没有直接 外，其他结点有且仅有一个直接;除终端结点没有直接 外，其 它 结 点 有 且 仅 有 一 个 直 接.16、所有结点按1对 1 的邻接关系构成的整体就是 结构。17、线性表的逻辑结构是 结构。其所含结点的个数称为线性表的 o18、在单链表中，指针p 所指结点为最后个结点的条件是 o三、判断题1.顺序存储的线性表可以随机存取。2.顺序存储的线性表的插入和删除操作不需要付出很大的代价，因

25、为平均每次操作只有近一半的元素需要移动。3.线性表中的元素可以是各种各样的，但同线性表中的数据元素具有相同的特性，因此是属于同数据对象。4.在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上不一定相邻。5.在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。6.在单链表中，可以从头结点进行查找任何一个元素。7.线性表的链式存储结构优于顺序存储结构。8.在线性表的顺序存储结构中，插入和删除元素时，移动元素的个数与该元素的位置有关。9.在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。10.顺序存储方式只能用于存储线性结构。四、简答题1、

26、若较频繁地对一个线性表进行插入和删除操作，该线性表宜采用哪种存储结构？为什么？2、描述概念：头指针、头结点、首元结点的区别？3、设 A 是一个线性表(a ia2.an),采用顺序存储结构，则在等概率的前提下，平均每插入一个元素需要移动的元素个数为多少？若元素插在为与ai+i之 间(0next)q=L;L=L-next;p=L;while(p-next)p=p-next;p-next=q;q-next=NULL;)return L;)7、如 果 有 n个线性表同时共存，并且在处理过程中各表的长度会发生动态变化，线性表的总长度也会自动地改变。在此情况下，应选择哪一种存储结构。为什么？8、若线性表的

27、总数基本稳定，且很少进行插入删除操作，但要求以最快的方式存取线性表的元素，应该用哪种存储结构。为什么？9、设有多项式 a(x)=9+8 x+9 x 4+5 x i b(x)=-2 x+2 2 x7-5 x1 0(1)用单链表给出a(x)、b(x)的存储表示；(2)设 c (x)=a(x)+b(x),求得c(x)并用单链表给出其存储表示。五、设计题1、编写一个函数将一个顺序表A (有多个元素且任何元素不为0)分拆成两个顺序表，使 A 中大于0的元素存放在B中，小于0的元素存放在C中。2、设顺序表L中的数据元素递增有序。试写一算法，将 e插入到顺序表的适当位置，插入后保持该表的有序性。3、A、B

28、为元素递增有序排列的单链表(同一表中可能有相同元素)，编写算法另建一单链表C,保存两个表的公共元素，要求C的元素值各不相同且递增有序。4、设有一个由正整数组成的无序单链表，编写算法实现下列功能：(1)找出最小值结点，且显示该数值。(2)若该数值为奇数，则将其与直接后继结点的数值交换。(3)若为偶数，则将其直接后继结点删除。六、编程附加题1 .试分别用顺序表和单链表作为存储结构，实现将线性表(a0,ai,a2,.a.)就地逆置的操作，所 谓“就地”指辅助空间为O (D o2 .设顺序表L是一个递增(允许有相同的值)有序表，试写一算法将x插 入 L中，并使L仍为一个有序表。3 .设单链表L是一个非

29、递减有序表，试写一个算法将x 插入其中后仍保持L的有序性。4 .试写出在无头结点的单链表的第i个元素之前插入一个元素的算法。5 .设 A、B是两个线性表，其表中元素递增有序，长度分别为m和 n。试写一算法分别以顺序存储和链式存储将A和 B归并成一个仍按元素值递增有序的线性表C,请分析算法的时间复杂度。6 .设指针la和 1 b 分别指向两个无头结点的单链表的首结点，设计从表la中删除第i个元素起共le n 个元素，并将这些元素插入到1 b 中第j 个结点之前的算法。7 .单链表L是一个递减有序表，试写一高效算法，删除表中值大于m in 且小于m a x 的结点(若表中有这样的结点)，同时释放被

30、删结点空间，这里m in 和 m ax是两个给定的参数。请分析你的时间复杂度。8.编写一个算法将一个头结点指针为p a的单链表A分解成两个单链表A和 B,其头结点指针分别为p a和p b,使得A链表中含有链表A中的序号为奇数的元素，而 B链表中含有原链表A中的序号为偶数的元素，且保持原来的相对顺序。9 .假设以两个元素依值递增有序排列的线性表A,B 分别表示两个集合，先要求另辟空间构造一个线性表C,其元素为两集合的交集，且表C中的元素也依值递增有序排列。是对顺序表编写求C的算法。1 0 .设有线性表A=(ai,a2,.所)和 B=(b i,b 2,.息)。试写合并A、B为线性表C的算法,使得:

31、c=f(i,am,b,bm+x,b.)寺m n;线性表A,B和 C均以单链表作存储结构，且 C表利用A表和B表的结点空间。11.假设在长度大于1 的单循环链表中，既无头结点也无头指针。S 为指向链表中某个结点的指针，试编写算法删除结点*s 的直接前驱结点。12.计算带头结点的循环链表的结点个数。13.已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其他字符)，试编写算法构造三个以循环链表表示的线性表使得每个表中只含有同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。14.已知A,B和 C 为三个递增有序的线性表，现要求对A 表作如下操作：

32、删去那些既在B 表中出现又在C表中出现的元素。试对顺序表编写实现上述操作的算法，并分析你的算法的时间复杂度(注：题中没特别指明同一表中的元素值各不相同)。15.双向循环链表中，设计满足下列条件的算法。(1)在值为x 的结点之前插入值为y 的结点。(2)删除值为x 的结点。16.设有一个循环双链表，其中有一结点的指针为P,编写算法将P 与其右边的一个结点进行交换。17.设有一个双链表，每个结点中除有prior、data和 next三个域外，还有一个可访问频度域fre q,在链表被起用之前，其值均初始为0。每当链表进行一次LocateNode(L,x)运算时令元素值为x 的结点中freq域 的 值

33、 加 1,并调整表中结点的次序，使其按访问频度的递减次序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode的运算的算法。18.给出用单链表存储多项式的结构，并编写一个按指数值递增次序输入所产生的多项式链表的过程。19.根据上题的多项式链表结构，编写一个过程实现两个多项式相加的运算。20.(Josephus环)任给正整数n、k,按下述方法可得排列1,2,n 的一个置换:将数字1,2,n环形排列，按顺时针方向从1 开始计数；计满K 时输出该位置上的数字(并从环中删去该数字)，然后从下一个数字开始继续计数，直到环中所有数字均被输出为止。例如，n=10,k=3时，输出的置

34、换是3,6,9,2,7,1,8,5,10。分别以数组和以不带头结点的、已知尾指针的单循环链表为存储结构解决上述问题。2 1 已知在一维数组Al.m+n中依次存放着两个向量(a,a2”am)和(也加，.bn),编写算法将两个向量的位置互换，即 把(bi,b2.bn)放 到(ai,a2.am)之前。2 2 给定个不带头结点的单链表，编写计算此链表长度的算法。2 3 设ha和hh分别是两个带头结点的非递减有序单链表的表头指针，试设计一个算法，将这两个有序链表合并成一个非递增有序的单链表。要求结果链表仍使用原来两个链表的存储空间，不另外占用其它的存储空间。表中允许有重复的数据。2 4 设有一个由正整数

35、组成的无序(向后)单链表，编写完成下列功能的算法：(I)找出最小值结点，且打印该数值；(2)若该数值是奇数，则将其与直接后继结点的数值交换；(3)若该数值是偶数，则将其直接后继结点删除；2 5 利用顺序表的操作，实现以下的函数。(1)从顺序表中删除具有最小值的元素并由函数返回被删元素的值，空出的位置由最后一个元素填补。(2)从顺序表中删除具有给定值x 的所有元素。(3)从有序顺序表中删除其值在给定值s 与 t 之 间(要 求 s 小于t)的所有元素。2 6 如果以单链表表示集合，设计算法建立先后输入的两个集合的差。2 7 已知一个线性表中的元素按元素值非递减有序排列，分别以顺序存储和链式存储编

36、写一个算法删除表中多余的值相同的元素。2 8 设 A=(aba2,a3，a“)和 B=(bhb2%)是两个顺序表(假定所含数据元素均为整数)。若 n=m 且ai=bi（i=l,.,n）厕称 A=B;若 ai=bi（i=l,.,j）且 aj+bj+i（jcnWm）,则称 AB。是编写一个比较A 和 B 的算法，当 AB是分别输出-1,0 或 者 1。2 9 已知一个循环单链表如图2.1所示，编写一个算法将所有箭头方向取反。head图2.13 0 假设有一个单循环链表，其结点含有三个域：prior,d a ta,和 next。其中data为数据域，next指向后继结点，prior为指针域，它的值为

37、空指针，试编写算法将此表改为双向循环链表。3 1 设 A 是一个双向循环链表，其表中元素递增有序。试写一算法插入一个元素x,使 表 A 中的元素依然递增有序。32写出将双向循环链表倒置的算法。3 3 设计一算法，将一个用循环链表表示的稀疏多项式分解成两个多项式，使这两个多项式各自仅有奇次幕或偶次第项，并要求利用原链表中的结点空间来构造这两个链表。3 4 设以带头结点的双向链表表示的线性表L=（a,a2,.,an）,试写一时间复杂度为0（n）的算法，将 L 改造为L=（ai,a3”.,an,a4,a2）。3 5 设一单向链表的头指针为h ead,链表的记录中包含着整数类型的key域，试设计算法，

38、将此链表的记录按照k ey 递增的顺序进行就地排序。第三章栈与队列 练习题一、选择题1、栈结构通常采用的两种存储结构是（）。A、顺序存储结构和链表存储结构 B、散列和索引方式 C、链表存储结构和数组D、线性链表结构和非线性存储结构2、设栈ST用顺序存储结构表示，则栈ST为空的条件是（）A ST.top-ST.baseoO ST.top-ST.base=0 C、ST.top-ST.baseon D、ST.top-ST.base=n3、向一个栈顶指针为H S的链栈中插入一个s 结点时，则 执 行（）A HS-next=s;s-next=HS-next;HS-next=s;C、s-next=HS;H

39、S=s;D、s-next=HS;HS=HS-next;4、从一个栈顶指针为H S的链栈中删除一个结点，用 x 保存被删除结点的值，则 执 行（）A、x=HS;HS=HS-next;B、HS=HS-next;x=HS-data;C、x=HS-data;HS=HS-next;D、s-next=Hs;Hs=HS-next;5 表达式a*（b+c）-d 的后缀表达式为（）A、abcdd+-B、abc+*d-C、abc*+d-D、-+*abcd6、中缀表达式A-（B+C/D）*E的后缀形式是（）A、AB-C+D/E*B、ABC+D/E*C、ABCD/E*+-D、ABCD/+E*-7、一个队列的入列序列是

40、1,2,3,4,则队列的输出序列是（）A、4,3,2,1 B、1,2,3,4 C、1,4,3,2 D、3,2,4,18、循环队列SQ采用数组空间SQ.base0,n-l存放其元素值，已知其头尾指针分别是front和 re a r,则判定此循环队列为空的条件是（）A Q.rear-Q.front=n B、Q.rear-Q.front-1 =n C、Q.front=Q.rear D、Q.front=Q.rear+19、循环队列SQ 采用数组空间SQ.base0,n-l存放其元素值，己知其头尾指针分别是front和 re a r,则判定此循环队列为满的条件是（）A Q.front=Q.rear B、

41、Q.front!=Q.rear C Q.front=（Q.rear+1 ）%n D Q.front!=（Q.rear+l）%n10、若在一个大小为6 的数组上实现循环队列，且当前rear和 front的值分别为0 和 3,当从队列中删除一个元素，再加入两个元素后，rear和 front的值分别为（）A、1,5 B、2,4 C、4,2 D、5,111、用单链表表示的链式队列的队头在链表的（）位置A、链 头 B、链 尾 C、链中12、判定一个链队列Q（最多元素为n 个）为空的条件是（）A Q.front=Q.rear B、Q.front!=Q.rear C、Q.front=（Q.rear+l）%n

42、 D Q.front!=（Q.rear+l）%n13、在链队列Q 中，插入s 所指结点需顺序执行的指令是（）A、Q.front-next=s;f=s;B、Q.rear-next=s;Q.rear=s;C、s-next=Q.rear;Q.rear=s;D、s-next=Q.front;Q.front=s;14、在一个链队列Q 中，删除一个结点需要执行的指令是（）A、Q.rear=Q.front-next;B、Q.rear-next=Q.rear-next-next;C、Q.front-next=Q.front-next-next;D、Q.front=Q.rear-next;15、用不带头结点的单

43、链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作 时（）A、仅 修 改 队 头 指 针 B、仅修改队尾指针C、队头尾指针都要修改 D、队头尾指针都可能要修改。16、栈和队列的共同点是（）A、都 是 先 进 后 出 B、都是先进先出 C、只允许在端点处插入和删除元素 D、没有共同点17、消除递归（）需要使用栈。A、一 定 B、不一定18、设有一顺序栈S,元素设,s2,s3,s4,s5,s6依次进栈,如果6 个元素出栈的顺序是s2,s3,s4,s6,s5,sl,则栈的容量至少应该是（）A、2 B、3 C、5 D、619、若一个栈的输入序列是a,b,c,则通过入、出栈操作

44、可能得到a,b,c的不同排列个数为（）A、4 B、5 C、6 D、720、设有一顺序栈已经含有3 个元素，如图3.1所示元素a4正等待进栈。下列不可能出现的出栈序列是（）A、a3,al,a4,a2 B、a3,a2,a4,al C、a3,a4,a2,al D、a4,a3,a2,al0maxsize-1丁Topala2a3图3.121、链栈和顺序栈相比，有一个比较明显的优势是（）A、通常不会出现栈满的情况 B、通常不会出现栈空的情况C、插入操作更容易实现 D、删除操作更加容易实现22、若一个栈的输入序列是1,2,3,4,n,输出序列的第一个元素是n,则第i 个输出元素是（）A、不确定 B、n-i

45、C、n-i+1 D、n-i-123、以下说法正确的是（）A、因链栈本身没有容量限制,故在用户内存空间的范围内不会出现栈满情况B、因顺序栈本身没有容量限制，故在用户内存空间的范围内不会出现栈满情况C、对于链栈而言，在栈满状态下，如果此忖再作进栈运算，则会发生“上溢”D、对于顺序栈而言在栈满状态下如果此时再作进栈运算，则会发生“下溢”。二、判断题1、在顺序栈栈满情况下，不能做进栈运算，否则会产生“上溢”。2、链栈与顺序栈相比的一个优点是链栈插入和删除操作更加方便。3、若一个栈的输入序列为1,2,3,，n,其输出序列的第一个元素为n,则其输出序列的每个元素比 一定满足 ai=i+l(i=l,2,n)

46、。4、在链队列中，即使不设置尾指针也能进行入队操作。5、在对链队列(带头指针)做出队操作时，不会改变front指针的值。6、循环队列中元素个数为rear-fronto7、一个栈的输入序列是1 2 3,4,则在栈的输出序列中可以得到4,3,1,2。8、一个栈的输入序列是1 2 3,4,则在栈的输出序列中可以得到1,2,3,4。9、若以链表作为栈的存储结构，则进栈需要判断栈是否满。10、若以链表作为栈的存储结构，则出栈需要判断栈是否空。三、填空题1、栈的特点是()，队列的特点是()。2、线性表、栈、队列都是()结构，可以在线性表的()位置插入和删除元素；对于栈只能在()插入和删除元素；对于队列只能

47、在()插入元素和在()位置删除元素。3、有程序如下，则此程序的输出结果(栈的元素类型是SelemType为 ch ar)是()。Void main()stack s;char x,y;initstack(s);x=c;y=k;push(s,x);push(s,a);push(s,y);pop(s,x);push(s,t,);push(s,x);pop(s,x)；push(s,s,);while(istackemply(s)pop(s,y);printf(y);printf(x);4、在栈顶指针为H S的链栈中，判定栈空的条件是()。5、向栈中压入元素的操作是先()后()。6、对栈进行退栈操作是

48、先()后()。7、用循环链表表示的队列长度为n,若只设头指针，则出队和入队的时间复杂度分别是()和()；若只设尾指针，则出队和入队的时间复杂度分别是()和()。8、从循环队列中删除一个元素时，其操作是()。9、在一个循环队列中，队首指针指向队首元素的()。10、在具有n 个单元的循环队列中，队满时共有()个元素。11、在 H Q 的链队列中，判断只有一个结点的条件是()。12、设栈S 和队列Q 的出始状态为空，元素2力,311?依次通过栈5,一个元素出栈后即进入队列Q。若这6个元素出队列的顺序是b,d,c,f,e,a则栈S 的容量至少应该是()。13、有程序如下，则此程序的输出结果(队列的元素

49、类型是QSelemType为 ch ar)是()。Void main()char x=，e,y=c;enqueue(q,h);enqueue(q,T);enqueue(q,y);dequeue(q,x);enqueue(q,x);degueue(q,x);enqueue(q,a);while(!queueempty(q)dequeue(q,y);printf(y);)printf(x);14、有如下递归函数：int dunno(int m)(int value;if(m=0)value=3;else value=dunno(m-l)+5;return(value);执行语句 printf(dn

50、”,dunno(3);的结果是()。四、简答题1、对于堆栈，给出三个输入项A,B,C,如果输入项序列为A B C,试给出全部可能的输出序列，并写出每种序列对应的操作。例如：A 进 B 进 C 进 C 出 B 出A 出，产生的序列为CBA。2、简述以下算法的功能(栈的元素类型是SelemType为 int)。(1)status algo 1 (stack s)int I,n,a255;n=0;while(!stackempty(s)n+;pop(s,an);for(I=1 ;I0 时(1)编写一个计算gcd(m,n)的递归过程(2)将上述过程转化为非递归过程(3)画出计算gcd(20,6)的过程