2022年数据结构--章宣贯 .pdf

《2022年数据结构--章宣贯 .pdf》由会员分享，可在线阅读，更多相关《2022年数据结构--章宣贯 .pdf（21页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第 1 章绪论一、选择题1. 算法的计算量的大小称为计算的（）。2. 算法的时间复杂度取决于（）3. 计算机算法指的是（），它必须具备（） 这三个特性。4一个算法应该是（）。5. 下面关于算法说法错误的是（）A算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的6. 下面说法错误的是（） (1）算法原地工作的含义是指不需要任何额外的辅助空间（2）在相同的规模 n 下，复杂度 O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（4）同一个算

2、法，实现语言的级别越高，执行效率就越低 A(1) B.(1),(2) C.(1),(4) D.(3) 7从逻辑上可以把数据结构分为（）两大类。A动态结构、静态结构 B顺序结构、链式结构C线性结构、非线性结构 D初等结构、构造型结构8以下与数据的存储结构无关的术语是（）。A循环队列 B. 链表 C. 哈希表 D. 栈9以下数据结构中，哪一个是线性结构（）？A广义表 B. 二叉树 C. 稀疏矩阵 D. 串名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 21 页 - - - -

3、 - - - - - 10以下那一个术语与数据的存储结构无关？（）A栈 B. 哈希表 C. 线索树 D. 双向链表11在下面的程序段中，对x 的赋值语句的频度为（）FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A O(2n) BO(n) CO(n2) DO(log2n) 12程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF AjAj+1 THEN Aj与 Aj+1 对换；其中 n 为正整数，则最后一行的语句频度在最坏情况下是（）A. O（n） B. O(nlogn) C. O(n3) D. O(n2) 13以下哪

4、个数据结构不是多型数据类型（）A栈 B广义表 C有向图 D字符串14以下数据结构中，（）是非线性数据结构A树 B字符串 C队 D栈15. 下列数据中，（）是非线性数据结构。A栈 B. 队列 C. 完全二叉树 D. 堆16连续存储设计时，存储单元的地址（）。A一定连续 B 一定不连续 C 不一定连续 D 部分连续，部分不连续17以下属于逻辑结构的是（）。A顺序表 B. 哈希表 C.有序表 D. 单链表二、判断题名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 21 页 - -

5、 - - - - - - - 1. 数据元素是数据的最小单位。( ) 2. 记录是数据处理的最小单位。 ( ) 3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；( ) 4算法的优劣与算法描述语言无关，但与所用计算机有关。( ) 5健壮的算法不会因非法的输入数据而出现莫名其妙的状态。( ) 6算法可以用不同的语言描述，如果用C 语言或 PASCAL 语言等高级语言来描述，则算法实际上就是程序了。( ) 7程序一定是算法。 ( ) 8数据的物理结构是指数据在计算机内的实际存储形式。( ) 9. 数据结构的抽象操作的定义与具体实现有关。( ) 10. 在顺序存储结构中，有时也存储数据结构中元素

6、之间的关系。( ) 11. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。( ) 12. 数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。 ( ) 13. 数据的逻辑结构说明数据元素之间的顺序关系, 它依赖于计算机的储存结构. ( ) 三、填空1数据的物理结构包括的表示和的表示。2. 对于给定的 n 个元素 , 可以构造出的逻辑结构有（1） ，（2） ， （3） ，_（4）_四种。3数据的逻辑结构是指。4一个数据结构在计算机中称为存储结构。5抽象数据类型的定义仅取决于它的一组_（1）_，而与_（2）_无关，即不论其内部结构如何变化，只要它的_（3）_不变，都不

7、影响其外部使用。6数据结构中评价算法的两个重要指标是名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 21 页 - - - - - - - - - 7. 数据结构是研讨数据的 _（1）_和_（2）_，以及它们之间的相互关系，并对与这种结构定义相应的 _（3）_，设计出相应的（ 4）_。8 一个算法具有 5 个特性 : （1） 、 （2） 、 （3） ，有零个或多个输入、有一个或多个输出。9已知如下程序段FOR i:= n DOWNTO 1 DO 语句 1 BEGIN x:=

8、x+1 ； 语句 2 FOR j:=n DOWNTO i DO 语句 3 y:=y+1; 语句 4 END ；语句 1 执行的频度为（1） ；语句 2 执行的频度为（2） ；语句 3 执行的频度为 （3） ；语句 4 执行的频度为（4） 。10在下面的程序段中，对的赋值语句的频度为_（表示为 n 的函数） FOR i ： TO n DO FOR j ：TO i DO FOR k：1 TO j DO ： delta ；11. 下面程序段中带下划线的语句的执行次数的数量级是：i ：=1； WHILE in DO i ：=i*2; 12. 下面程序段中带下划线的语句的执行次数的数量级是( )。i:=

9、1; WHILE in BEGIN FOR j:=1 TO n DO x:=x+1;i:=i*2 END；13. 下面程序段中带有下划线的语句的执行次数的数量级是( ) i ：=n*n WHILE i1 DO i:=i div 2; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 21 页 - - - - - - - - - 14. 计算机执行下面的语句时，语句s 的执行次数为 _ 。 FOR(i=l；i=i;j-) s; 15. 下面程序段的时间复杂度为_。(n1) s

10、um=1； for (i=0;sumn;i+) sum+=1; 16设 m.n 均为自然数， m可表示为一些不超过n 的自然数之和， f(m,n) 为这种表示方式的数目。 例 f(5,3)=5，有 5 种表示方式： 3+2，3+1+1，2+2+1，2+1+1+1，1+1+1+1+1 。以下是该函数的程序段，请将未完成的部分填入，使之完整int f(m,n) int m,n; if(m=1) return (1) ; if(n=1) return (2) ; if(mn) return f(m,m); if (m=n) return 1+ (3) ; return f(m.n-1)+f(m-n,

11、 (4) ); 执行程序， f(6,4)= 。17. 在有 n 个选手参加的单循环赛中，总共将进行_场比赛。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 21 页 - - - - - - - - - 四、应用题1. 数据结构是一门研究什么内容的学科？2. 数据元素之间的关系在计算机中有几种表示方法？各有什么特点？3. 数据类型和抽象数据类型是如何定义的。二者有何相同和不同之处，抽象数据类型的主要特点是什么？使用抽象数据类型的主要好处是什么？4. 回答问题（每题 2 分）

12、（1）在数据结构课程中，数据的逻辑结构，数据的存储结构及数据的运算之间存在着怎样的关系？（2） 若逻辑结构相同但存储结构不同， 则为不同的数据结构。 这样的说法对吗？举例说明之。（3）在给定的逻辑结构及其存储表示上可以定义不同的运算集合，从而得到不同的数据结构。这样说法对吗？举例说明之。（4）评价各种不同数据结构的标准是什么？5评价一个好的算法，您是从哪几方面来考虑的？6解释和比较以下各组概念（1）抽象数据类型及数据类型（2）数据结构、逻辑结构、存储结构（3）抽象数据类型（4）算法的时间复杂性（5）算法（6）频度7. 根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？8对于一个数据结构，

13、一般包括哪三个方面的讨论？9. 当你为解决某一问题而选择数据结构时，应从哪些方面考虑？10. 若将数据结构定义为一个二元组（D，R）, 说明符号 D，R 应分别表示什么？名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 21 页 - - - - - - - - - 11数据结构与数据类型有什么区别？12数据的存储结构由哪四种基本的存储方法实现？13若有 100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？14. 运算是数据结构的一个重要方

14、面。试举一例，说明两个数据结构的逻辑结构和存储方式完全相同， 只是对于运算的定义不同。 因而两个结构具有显著不同的特性，是两个不同的结构。15. 在编制管理通讯录的程序时, 什么样的数据结构合适 ? 为什么 ? 16. 试举一例，说明对相同的逻辑结构, 同一种运算在不同的存储方式下实现，其运算效率不同。17. 有实现同一功能的两个算法A1和 A2，其中 A1的时间复杂度为Tl=O(2n) ，A2的时间复杂度为 T2=O(n2)，仅就时间复杂度而言，请具体分析这两个算法哪一个好。18设计一数据结构，用来表示某一银行储户的基本信息：账号、姓名、开户年月日、储蓄类型、存入累加数、利息、帐面总数。19

15、. 写出下面算法中带标号语句的频度。 TYPE ar=ARRAY1.n OF datatype; PROCEDURE perm ( a: ar; k, n: integer); VAR x: datatype; i:integer; BEGIN （1）IF k=n THEN BEGIN （2）FOR i:=1 TO n DO （3）write (ai); writeln; END ELSE BEGIN 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 21 页 - - -

16、- - - - - - （4） FOR i:=k TO n DO （5）ai:=ai+i*i; （6） perm (a, k+1, n); END; END; 设 k 的初值等于 1。20. 分析下面程序段中循环语句的执行次数。i:=0;s:=0;n:=100; REPEAT i:=i+1; s:=s+10*i; UNTIL NOT(in) AND (sn); 21下列算法对一 n 位二进制数加 1，假如无溢出，该算法的最坏时间复杂性是什么？并分析它的平均时间复杂性。TYPE num=ARRAY 1.n of 0.1；PROCEDURE Inc （VAR a：num ）；VAR i ：inte

17、ger ；BEGIN i ：=n；WHILE Ai=1 DO BEGIN Ai：=0； i：=i-1 ；END ；END ；Ai ：=1；END Inc；22. 阅读下列算法，指出算法A的功能和时间复杂性名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 21 页 - - - - - - - - - PROCEDURE A (h,g:pointer); (h,g 分别为单循环链表（ single linked circular list）中两个结点指针 ) PROCEDURE

18、 B(s,q:pointer) ； VAR p:pointer; BEGIN p:=s; WHILE p.nextq DO p:=p.next; p.next:=s; END;(of B) BEGIN B(h,g); B(g,h); END; （of A ）23. 调用下列 C函数 f(n) 或 PASACAL 函数 f(n) 回答下列问题 : （1） 试指出 f(n) 值的大小，并写出f(n) 值的推导过程 ; （2） 假定 n= 5，试指出 f(5) 值的大小和执行 f(5) 时的输出结果。 C函数： int f(int n) int i,j，k,sum= 0; for(i=l; ii-1

19、; j-) for(k=1;kprior=q; q-next=p; p-prior-next=q; q-prior=p-prior; B） q-prior=p-prior; p-prior-next=q; q-next=p; p-prior=q-next; C） q-next=p; p-next=q; p-prior-next=q; q-next=p; D） p-prior-next=q; q-next=p; q-prior=p-prior; p-prior=q; 【答案】 D 4 在一个具有n个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是（ ）A）O(nlog2n）B ） O

20、(1 ）C） O(n ）D） O(n2）【答案】 C 5 在一个以 h 为头指针的单循环链中，p 指针指向链尾结点的条件是（）A）p-next=NULL B） p-next=h C）p-next-next=h D） p-data=-1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 21 页 - - - - - - - - - 【答案】 B 6对于一个具有n 个结点的线性表，建立其单链表的时间复杂度是（） A）O(n) B） O(1) C） O(nlog2n) D） O

21、(n2) 【答案】 A 8在双向链表存储结构中，删除p 所指的结点时须修改指针（）A）p-prior-next=p-next p-next-prior=p-prior; B）p-prior=p-prior-prior p-prior-next=p; C）p-next-prior=p p-next=p-next-next D）p-next=p-prior-prior p-prior=p-next-next; 【答案】 A 9线性表采用链式存储时，其元素地址（）A）必须是连续的B）一定是不连续的C）部分地址是连续的D）连续与否均可【答案】 D 2.2填空题1线性表L=（a1，a2，, ， an）用

22、数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。【答案】（ n-1 ）/2 2在单链表中设置头结点的作用是_。【答案】 主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除第一个结点不必另作判断。另外，不论链表是否为空，链表头指针不变。3线性表的顺序存储是通过_来反应元素之间的逻辑关系，而链式存储结构是通过 _来反应元素之间的逻辑关系。【答案】（ 1）数据元素的前后顺序（2）元素中的指针名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12

23、页，共 21 页 - - - - - - - - - 4当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，则采用_存储结构最节省时间，相反当经常进行插入和删除操作时，则采用_存储结构最节省时间。【答案】（ 1）顺序（2）链式5对于一个具有n 个结点的单链表，在已知的结点*p 后插入一个新结点的时间复杂度为_，在给定值为x 的结点后插入一个新结点的时间复杂度为_。【答案】（ 1）O(1) （2）O(n) 7. 对于双向链表， 在两个结点之间插入一个新结点需修改的指针共_个，单链表为 _个。【答案】（ 1）4 （2）2 8. 循环单链表的最大优点是_。【答案】从任一结点出发都可访问到

24、链表中每一个元素。9若要在一个不带头结点的单链表的首结点*p 结点之前插入一个*s 结点时， 可执行下列操作： s-next=_; p-next=s; t=p-data; p-data= _; s-data=_; 【答案】（ 1）p-next （2）s-data （3） t 10某线性表采用顺序存储结构，每个元素占据4 个存储单元，首地址为100，则下标为11的（第 12 个）元素的存储地址为_。【答案】 144 11带头结点的双循环链表L 中只有一个元素结点的条件是_。【答案】 L-next-next=L 2.3 判断题名师资料总结 - - -精品资料欢迎下载 - - - - - - - -

25、 - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 21 页 - - - - - - - - - 1取线性表的第i 个元素的时间同i 的大小有关（）【答案】2线性表的特点是每个元素都有一个前驱和一个后继（）【答案】3 顺序存储方式的优点是存储密度大，且插入、删除运算效率高（）【答案】4线性表采用链表存储时，结点的存储空间可以是不连续的（）【答案】5链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高（）【答案】6顺序存储方式只能用于存储线性结构（）【答案】【解析】线性结构、树型结构和图状结构均可用顺序存储表示。

26、9顺序存储结构的主要缺点是不利于插入或删除操作（）【答案】10顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好（）【答案】2.4程序设计题1设顺序表 va 中的数据元素递增有序。试设计一个算法， 将 x 插入到顺序表的适当位置上，以保持该表的有序性。【算法源代码】void Insert_SqList(SqList va,int x)/*把 x 插入递增有序表va 中*/ int i; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 21 页 - - - - -

27、 - - - - if(va.length MAXSIZE) return; for(i=va.length-1;va.elemix&i=0;i-) va.elemi+1=va.elemi; va.elemi+1=x; va.length+; /*Insert_SqList*/ 2设A=（a1，a2， ，am） 和 B=（b1，b2，bn）均为顺序表，试设计一个比较A，B 大小的算法（请注意：在算法中，不要破坏原表A 和 B）。【算法分析】比较顺序表A和 B，并用返回值表示结果，值为1，表示 AB ；值为 -1 ，表示AB ；值为 0，表示 A=B 。1）当两个顺序表可以互相比较时，若对应元素

28、不等，则返回值为1 或-1 ；2）当两个顺序表可以互相比较的部分完全相同时，若表长也相同，则返回值为0；否则，哪个较长，哪个就较大【算法源代码】int ListComp(SqList A,SqList B) for(i=1;i=A.length&iB.elemi?1:-1; if(A.length=B.length) return 0; return A.lengthB.length?1:-1; /* 当两个顺序表可以互相比较的部分完全相同时，哪个较长，哪个就较大*/ /*ListComp */ 3已知指针ha 和 hb 分别指向两个单链表的头结点，并且已知两个链表的长度分别为m和 n。试设计

29、一个算法将这两个链表连接在一起（即令其中一个表的首元结点连在另一个表名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 21 页 - - - - - - - - - 的最后一个结点之后），假设指针hc 指向连接后的链表的头结点，并要求算法以尽可能短的时间完成连接运算。【算法分析】1）单链表ha 的头结点作为连接后的链表的头结点，即hc=ha；2）查找单链表ha 的最后一个结点，由指针p 指向，即p-next=NULL ；3）将单链表hb 的首元结点（非头结点）连接在p 之后

30、，即 p-next=hb-next；4）回收单链表hb 的头结点空间【算法源代码】void ListConcat(LinkList ha,LinkList hb,LinkList *hc) /* 把链表 hb 接在 ha 后面形成链表hc*/ *hc=ha; p=ha;/*由指针 p 指向 ha 的尾元结点 */ p=p-next; p-next=hb-next; free(hb); /*ListConcat */ 4试设计一个算法，在无头结点的动态单链表上实现线性表操作INSERT （L，i，b），并和在带头结点的动态单链表上实现相同操作的算法进行比较。【算法分析】1）生成新结点存放元素b，

31、由指针new指向；2）将 new插入在单链表的第i 个元素的位置上：若i=1 ，new插在链表首部；否则查找第i-1个结点，由指针p 指向，然后将new插在 p 之后。【算法源代码】void Insert(LinkList *L,int i,int b) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 21 页 - - - - - - - - - LinkList new; new=(LinkList*)malloc(sizeof(LNode); new-data=b;

32、 if(i=1) /*插入在链表头部*/ New-next=*L; *L=new; else /*插入在第i 个元素的位置 */ p=*L; while(-i1) p=p-next; new-next=p-next;p-next=new; /*Insert */ 5已知线性表中的元素以值递增有序排列，并以单链表作存储结构。试设计一个高效的算法，删除表中所有值大于mink 且小于maxk 的元素（若表中存在这样的元素），同时释放被删结点空间 （注意：mink 和 maxk 是给定的两个参变量。它们的值可以和表中的元素相同，也可以不同）。【算法分析】1）查找最后一个不大于mink 的元素结点，由指

33、针p 指向；2）如果还有比mink 更大的元素，查找第一个不小于maxk 的元素，由指针q 指向；3）p-next=q ，即删除表中所有值大于 mink 且小于 maxk 的元素。【算法源代码】void Delete_Between(LinkList *L,int mink,int maxk) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 21 页 - - - - - - - - - p=*L; while(p-next-datanext; /*p是最后一个不大于mi

34、nk 的元素 */ if(p-next) /*如果还有比mink 更大的元素 */ q=p-next; while(q-datanext; /*q是第一个不小于maxk的元素 */ p-next=q; /*Delete_Between */ 第三章 栈和队列练习题1、顺序栈 S,栈顶指针为 top, 则栈置空操作是 _.2、设有一栈 , 结点结构为data | next 栈顶指针为h. 则执行 ?*?s? 结点入栈操作是_和_. 3、栈是一种特殊的_, 又称为 _. 4、判定一个栈ST（最多元素为m0）为空的条件是、 ST-top0 、 ST-top=0 、 ST-topm0 、 ST-top

35、=m0 5、设输入序列为1,2,3,4,5借助一个栈不可能得到的输出序列是( ) A 、 1,2,3,4,5 B 、5,4,3,2,1 C 、 4,3,1,2,5 D、 1,3,2,5,4 6、顺序队列和循环队列的队满及队空判断条件是一样的( ) 7、栈和队列都是线性表.( ) 8、排序和查找是两种基本的数据结构.( ) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 21 页 - - - - - - - - - 9、 队列是一种特殊的_, 允许插入的一端称为_,? 允

36、许删除的一端称为_,所以队列又称为_. 10、栈的两个重要应用是_和_. 11、栈和队列都是运算受到限制的特殊的线性表, 栈和队列有何不同? 12、用数组A存放循环队列的元素值, 若其头指针为front,尾指针为rear, 则循环队列中当前元素个数为 ( ). A、 (rear-front+m)%m B 、 (rear-front+1)%m C 、 (rear-front-1+m)%m D 、 (rear-front)%m 13、设循环队列Q头指针为 front,尾指针为rear, 队列的最大容量为M,写出循环队列队满和队空的判定条件. 14、给出循环队列的入队和出队算法. 15、由于查找运算

37、的主要操作是关键字的比较, 所以 ,? 通常把查找过程中对关键字需要执行的_作为衡量一个查找算法效率优劣的标准. 16、设计算法判断一个算术表达式的圆括号是否正确配对,( 提示 :? 对表达式进行扫描, 凡遇(就进栈 , 遇)就退掉栈顶的 ),表达式被扫描完毕, 栈就为空 .) 17、程序段的输出结果是_（队列中的元素类型QElem Type 为 char ）。void main( ) Queue Q; Init Queue (Q); Char x= e，y=c;EnQueue (Q,h); EnQueue (Q, r ); EnQueue (Q, y); DeQueue (Q,x); EnQ

38、ueue (Q,x); DeQueue (Q,x); EnQueue (Q, a);while(!QueueEmpty(Q) DeQueue (Q,y);printf(y); ; Printf(x); 18、设循环队列的容量为40（序号从 0 到 39），现经过一系列的入队和出队运算后，有名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 21 页 - - - - - - - - - front=11， rear=19; front=19， rear=11 ；问在这两种情况

39、下，循环队列中各有元素多少个？19、设两个栈共享向量空间V(1:m), 它们的栈底分别设在向量的两端, 且进栈的每个元素只占一个分量 , 试写出这两个栈公用的栈操作算法pushi(i,x),popi(i),其中 i 为 0 或 1, 用以指示栈号20、已知 Ackerman 函数的定义如下 : akm(m,n)=n+1 当 m=0时akm(m-1,1) 当 m0,n=0 时akm(m-1,akm(m,n-1) 当 m0,n0 时写出递归算法21、设 HS为一个链栈的栈顶指针, 试写出退栈的算法,( 回收被删除的结点) 22、中缀算术表达式3*(5+x)/y所对应的后缀算术表达式为_. 23、设

40、有编号为1，2，3，4 的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序. 24、写出栈的顺序存储结构( 即顺序栈 ) 的类型定义 . 25、写出队列的顺序存储结构( 顺序队列 ) 的类型定义 . 26、 假设表达式由单字母变量和双目运算符构成. 试写一个算法, 将一个通常书写正确的表达式转换为逆波兰式. 27、带有头结点的链队列q, 队头指针 front,队尾指针rear,? 则置空队的算法描述为: q-front=malloc(sizeof(linklist); _ ; _ ; 28、顺序队的“假溢出”是怎样产生的？如何知道循环队列是空还是满？29、若已知

41、一个栈的入栈序列是1，2，3，, ，n，其输出序列为p1，p2， p3，, ，pn，若p1=n，则 pi 为( ) 、 i 、 n=i 、 n-i+1 、不确定名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 21 页 - - - - - - - - - 30、队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。（）31、判定一个队列QU （最多元素为m0 ）为满队列的条件是（）、 QU-rear QU-front = = m0 、 QU-rear Q

42、U-front 1= = m0 、 QU-front = = QU-rear 、 QU-front = = QU-rear+1 32、数组用来表示一个循环队列，为当前队列头元素的前一位置，为队尾元素的位置，假定队列中元素的个数小于，计算队列中元素的公式为A、r f; B、（ nf r ）% n; C 、nr f; D、（ nr f ）% n 33、说明线性表、栈与队的异同点。34、简述以下算法的功能（栈和队列的元素类型均为int ）。void algo3(Queue &Q) Stack S; int d; InitStack(S); while(!QueueEmpty(Q) DeQueue (

43、Q,d); Push(S,d); ; while(!StackEmpty(S) Pop(S,d); EnQueue (Q,d); 35、向量、 栈和队列都是结构， 可以在向量的位置插入和删除元素；对于栈只能在插入和删除元素；对于队列只能在插入和删除元素。36、栈是一种特殊的线性表，允许插入和删除运算的一端称为。不允许插入和删除运算的一端称为。37、是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 21 页，共 21 页 - - - - - - - - -