输出在顺序表{3,6,2,10,1,8,5,7,4,9},中采用顺序方法查找关键字5的过程。

数据结构能力测试集训题目线性表1.实现顺序表各种基本运算的算法，并基础上设计一个主程序完成如下功能：(1)初始化顺序表L；(2)采用尾插法依次插入a，b，c，d，e；（3）输出顺序表L；（4）输出顺序表L的长度；（5）判断顺序表L是否为空；（6）输出顺序表L的第3个元素；（7）输出元素a的位置；（8）在第四个元素位置上插入f元素；（9）输出顺序表L；（10）删除顺序表L的第3个元素；（11）输出顺序表L；（12）释放顺序表L。

2.实现单链表各种基本运算的算法，并基础上设计一个主程序完成如下功能：(1)初始化单链表h；(2)采用尾插法依次插入a，b，c，d，e；（3）输出单链表h；（4）输出单链表h的长度；（5）判断单链表h是否为空；（6）输出单链表h的第3个元素；（7）输出元素a的位置；（8）在第四个元素位置上插入f元素；（9）输出单链表h；（10）删除单链表h的第3个元素；（11）输出单链表h；（12）释放单链表h；3.实现双链表各种基本运算的算法，并基础上设计一个主程序完成如下功能：(1)初始化双链表h；(2)采用尾插法依次插入a，b，c，d，e；（3）输出双链表h；（4）输出双链表h的长度；（5）判断双链表h是否为空；（6）输出双链表h的第3个元素；（7）输出元素a的位置；（8）在第四个元素位置上插入f元素；（9）输出双链表h；（10）删除双链表h的第3个元素；（11）输出双链表h；（12）释放双链表h；4.实现循环单链表各种基本运算的算法，并基础上设计一个主程序完成如下功能：(1)初始化循环单链表h；(2)采用尾插法依次插入a，b，c，d，e；（3）输出循环单链表h；（4）输出循环单链表h的长度；（5）判断循环单链表h是否为空；（6）输出循环单链表h的第3个元素；（7）输出元素a的位置；（8）在第四个元素位置上插入f元素；（9）输出循环单链表h；（10）删除循环单链表h的第3个元素；（11）输出循环单链表h；（12）释放循环单链表h；5.实现循环单链表各种基本运算的算法，并基础上设计一个主程序完成如下功能：(1)初始化循环双链表h；(2)采用尾插法依次插入a，b，c，d，e；（3）输出循环双链表h；（4）输出循环双链表h的长度；（5）判断循环双链表h是否为空；（6）输出循环双链表h的第3个元素；（7）输出元素a的位置；（8）在第四个元素位置上插入f元素；（9）输出循环双链表h；（10）删除循环双链表h的第3个元素；（11）输出循环双链表h；（12）释放循环双链表h；6.求集合的并，交，差运算（用有序单链表表示）栈和队列7.实现顺序栈各种基本运算的算法，编写一个程序实现顺序栈的各种基本运算，并在此基础上设计一个主程序完成以下各种功能：（1）初始化栈s（2）判断栈s是否非空（3）依次进栈元素a，b，c，d，e（4）判断栈s是否非空（5）输出栈长度（6）输出从栈顶到栈底元素（7）输出出栈序列（8）判断栈s是否非空（9）释放栈8.实现链栈各种基本运算的算法，编写一个程序，实现链栈的各种基本算法，并在此基础上设计一个主程序完成如下功能：（1）初始化链栈s（2）判断链栈s是否非空（3）依次进栈元素a，b，c，d，e（4）判断链栈s是否非空（5）输出链栈长度（6）输出从栈顶到栈底元素（7）输出链栈序列（8）判断链栈s是否非空（9）释放链栈9.实现顺序队列各种基本运算的算法，编写一个程序，实现顺序循环队列各种基本运算，并在此基础上设计一个主程序完成如下功能：（1）初始化队列q（2）判断队列q是否非空（3）依次进队列元素a，b，c（4）出队一个元素，输出该元素（5）输出队列q的元素的个数（6）依次进队列元素d，e，f（7）输出队列q的元素的个数（8）输出出队序列（9）释放队列10.实现链队各种基本运算的算法，编写一个程序，实现链队的各种基本运算，在此基础上设计一个主程序完成如下功能：（1）初始化链队q（2）判断链队q是否非空（3）依次进链队元素a，b，c（4）出队一个元素，输出该元素（5）输出链队q的元素的个数（6）依次进链队元素d，e，f（7）输出链队q的元素的个数（8）输出出队序列（9）释放链队串11.实现顺序串各种基本运算的算法，编写一个程序实现顺序的基本运算的算法，比在此基础上设计一个主程序完成如下功能：（1）建立s=”abcdefghefghijklmn”和串s1=”xyz”（2）输出串s（3）输出串s的长度（4）在串s的第9个字符位置插入串s1而产生串s2（5）输出串s2（6）删除串s第2个字符开始的5个字符而产生的串s2（7）输出串s2（8）将串s第2个字符开始的5个字符替换成串s1而产生串s2（9）输出串s2（10）提取串s的第2个字符开始的10个字符而产生串s3（11）输出串s3（12）将串s1和串s2连接起来而产生的串s4（13）输出串s412.实现链串个各种基本运算的算法，编写一个程序实现链串的各种基本运算，并在此基础上设计一个主程序完成如下功能；（1）建立s=”abcdefghefghijklmn”和串s1=”xyz”（2）输出串s（3）输出串s的长度（4）在串s的第9个字符位置插入串s1而产生串s2（5）输出串s2（6）删除串s第2个字符开始的5个字符而产生的串s2（7）输出串s2（8）将串s第2个字符开始的5个字符替换成串s1而产生串s2（9）输出串s2（10）提取串s的第2个字符开始的10个字符而产生串s3（11）输出串s3（12）将串s1和串s2连接起来而产生的串s4（13）输出串s413.顺序串的各种模式匹配运算，编写一个程序实现顺序串的各种模式匹配运算，并在此基础上完成如下功能：（1）建立”abcabcdabcdeabcdefabcdefg”目标串s和”abcdeabcdefab”模式串t（2）采用简单匹配算法求t在s中的位置（3）由模式串t求出next值和nextval值（4）采用KMP算法求t在s中的位置（5）采用改进的KMP算法求t在s中的位置查找14.实现顺序查找的算法，编写一个程序输出在顺序表{3，6，2，10，1，8，5，7，4，9}中采用顺序方法查找关键字5的过程。

1、在一个长度为n的顺序存储的线性表中，删除第i个元素（1≤i≤n）时，需要从前向后依次前移（A）个元素A.n一iB.n一i十1C.n一i一1D.i2、假定有一个空间大小为f的循环队列，其队首和队尾指针分别为1和r，则判断队空的条件为（D）A.f十1= =rB.r＋1= =fC.r= =0D.r= =13、某程序中基本操作的原操作其语句调用频度为（3n+nlog2n+8）, 则该程序的时间复杂度为（B）A．O（n） B．O（nlog2n）C．O（n2） D．O（log2n）4、二叉树的第i层上至多有（C）个结点。

A．i B．2iC．2i-1 D．2i+15、每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（A）排序A．插入 B．交换C．选择 D．归并6、当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈满，则出栈时，用（C）语句修改top指针A．top++ B．top=0C．top-- D．top=N7、由权值分别为3,6,7,2,5的叶子结点生成一棵赫夫曼树，它的带权路径长度为（D）A．51 B．23C．53 D．548、在一棵二叉树中，第4层上的结点数最多为（B）A．31 B．8C．15 D．169、设有字符序列{16、8、3、24、15、1、12、18、17、4、5、23}，新序列为{5、8、3、4、15、1、12、16、17、18、24、23}是下列哪个排序算法一趟扫描的结果（D）A、起泡排序B、初始步长为4的shell的排序C、二路归并排序D、以第一个元素为分界元素的快速排序10、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为 (C)A. nB. n/2C. (n+1)/2D. (n-1)/211、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s 所指的结点,则执行(D)A.s→next=p→next; p→next=sB.p→next=s; s→next=qC.p→next=s→next; s→next=pD.q →next=s; s→next =p12、栈的插入和删除操作在（A）进行A. 栈顶B. 栈底C. 任意位置D. 指定位置13、在一棵深度为5的完全二叉树中,至少含有(B)结点A.15B. 16C. 30D. 3114、在一个单链表HL中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（D）A.q一>next=p一>next；p一>next=q；B.p一>next=q一>next；q=p；C.q一>next=p一>next；p一>next=q；D.p一>next=q一>next；q一>next=p；15、请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用折半查找关键码12需做多少次关键码比较（C）A.2B.3C.4D.516、下面关于图的存储的叙述中，哪一个是正确的（A）A．用数组表示法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关B．用数组表示法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关C．用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关D．用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关17、在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（A）A 行号B 列号C 元素值D 地址18、在稀疏矩阵的三元组顺序表存储中，每个结点包含有3个域，下面哪个不是的（D）A.元素所在的行号B.元素所在的列号C.元素本身的值D.元素个数19、下面程序段的时间复杂度为（C）for(int i=0; i<m; i++)for(int j=0; j<n; j++)a[i][j]=i*j;A. O(m)B. O(n)C. O(m*n)D. O(m+n)20、执行下面程序段时，执行S语句的次数为（D）for(int i=1; i<=n; i++)for(int j=1; j<=i; j++)S;A. nB. n/2C. n(n+1)D. n(n+1)/221、下面算法的时间复杂度为（C）int f(unsigned int n) {if(n==0 || n==1) return 1;Else return n*f(n-1);}A. O(1)B. O(n)C. O(n)D. O(n!)22、在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（D）A.HL=p; p->next=HL；B. p->next=HL; HL=p;C. p->next=HL; p=HL；D. p->next=HL->next; HL->next=p;23、下列数据组织形式中，(C)的结点按逻辑关系依次排列形成一个"锁链"。

找出数字的顺序（使用整数和小数）数字是我们日常生活中不可或缺的一部分，无论是整数还是小数，它们都在不同的场景中发挥着重要的作用。

而正确地找出数字的顺序对于我们理解和应用数字都非常重要。

本文将介绍一些方法来帮助我们准确地找出数字的顺序。

首先，对于整数的顺序，我们可以采用以下的方法：1. 从最小到最大排序：在给定一组整数的时候，我们可以按照数字的大小从最小到最大进行排序。

这可以通过比较数字的大小来实现。

例如，对于数字4、1、3和2，我们可以将它们从最小到最大排序为1、2、3和4。

2. 从最大到最小排序：与从最小到最大排序类似，我们也可以按照数字的大小从最大到最小进行排序。

这种排序方式可以帮助我们快速找出一组数字中的最大值。

例如，对于数字4、1、3和2，我们可以将它们从最大到最小排序为4、3、2和1。

3. 逆序排序：有时候，我们需要逆序排列一组数字。

逆序排序是指按照与顺序相反的方式排列数字。

例如，对于数字4、1、3和2，逆序排序后的结果为4、3、2和1。

针对小数的顺序，我们可以采用以下的方法：1. 根据小数位数排序：小数可以有不同的位数，我们可以根据小数的位数来排序。

首先，我们可以将小数按照小数点后的数字位数进行分类。

例如，有小数0.25、0.3、0.135和0.058，我们可以将它们分别归类为小数位数为2、1、3和3的小数。

然后，我们可以按照小数位数从小到大排序。

2. 根据小数的大小排序：除了按照小数位数排序外，我们还可以按照小数的大小进行排序。

这种排序方式与整数的排序类似，我们可以通过比较小数的大小来确定它们的顺序。

例如，对于小数0.25、0.3、0.135和0.058，按照大小排序后的结果为0.058、0.135、0.25和0.3。

3. 综合排序：有时候，我们需要将整数和小数一起排序。

可以先将整数和小数分开进行排序，然后再将它们合并起来形成最终的顺序。

例如，对于数字4、1、3、0.25、0.3、0.135和0.058，我们可以先将整数和小数分开排序，得到整数排序结果为1、3和4，小数排序结果为0.058、0.135、0.25和0.3，然后将它们合并起来得到最终的顺序为0.058、0.135、0.25、0.3、1、3和4。

数据结构之两条有序顺序表的中位数查找（⽅法介绍）
在学习数据结构时遇到⼀种⽞⽽⼜⽞的⽅法，这种⽅法似乎可以按着某种规律去理解，但是⼜摸不着他的最深层的原理。

题⽬描述：
有⼀条顺序表A{1，3，4，5，6，7，8}，他的中位数是5即为位置是（长度L/2）+1，当长度为偶数的时候则直接为L/2。

⽽要求是给两条有序的顺序顺序表找出其中的中位数（及两个表中所有数的中位数）
解题⽅法：
⼀、当然，⽆论什么问题都有笨⽅法，可以将两个数组合并然后直接根据数组下标求出中位数，但是其浪费了⼤量的存储空间。

故不采取。

⼆、重点讲这种⽅法。

1. 分别求出两个线性表的的中位数分别为 a,b,当两个中位数相等时直接退出
2. 当a>b时，则将a所在的线性表中数较⼤的那⼀半去掉，然后将b在的线性表中数较⼩的那⼀半去掉，再各⾃求剩下数的中位数；
3. 当a<b时，则将a所在的线性表中数较⼩的那⼀半去掉，然后将b在的线性表中数较⼤的那⼀半去掉，再各⾃求剩下数的中位数；
依次重复上述三个步骤直到只剩下两个数则取其中较⼩的那个为两个顺序表的中位数。

⾄于解题的原理，恕在下理解不深，我就不能深⼊解释了。

如若有能解惑的仁兄，⿇烦留⾔相告。

填空题（10 ＊1’ = 10' ）一、概念题2。

2.当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。

2。

3。

当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。

2。

6。

带头结点的单链表L中只有一个元素结点的条件是L—〉Next->Next==Null。

3。

6。

循环队列的引入,目的是为了克服假溢出.4。

2。

长度为0的字符串称为空串。

4。

5.组成串的数据元素只能是字符。

4。

8.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。

7.2。

为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。

5.7。

广义表的深度是广义表中括号的重数7。

8.有向图G可拓扑排序的判别条件是有无回路。

7.9。

若要求一个稠密图的最小生成树，最好用Prim算法求解。

8。

8.直接定址法法构造的哈希函数肯定不会发生冲突。

9。

2。

排序算法所花费的时间，通常用在数据的比较和交换两大操作。

1。

1。

通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。

1。

2.对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。

1。

3。

存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。

1。

4。

抽象数据类型的定义仅取决于它的一组逻辑特性,而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变,都不影响其外部使用。

1。

5.一个算法具有五大特性:有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。

2.8.在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点,则需执行下列语句:s—〉prior= p—〉prior; s-〉next= p; p-〉prior- next= s；p-〉prior= s；。

2.9。

在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空,并使得对单链表的操作（如插入和删除)在各种情况下统一。

第10章排序10.1排序的相关知识一、填空题1.将一个数据元素（或记录）的任意序列，重新排列成一个按关键字有序的序列叫2.大多数排序算法都有两个基本的操作：____________ 和___________ 。

二、选择题1.（）排序算法的稳定性是指（）。

A.经过排序后，能使关键字相同的元素保持原顺序中的相对位置不变B.经过排序后，能使关键字相同的元素保持原顺序中的绝对位置不变C.排序算法的性能与被排序元素的个数关系不大D.排序算法的性能与被排序元素的个数关系密切2.（）关于排序的以下叙述中，正确的是（）。

A.稳定的排序方法优于不稳定的排序方法，因为稳定的排序方法效率高B.对同一个线性表使用不同的排序方法进行排序，得到的排序结果可能不同C.排序方法都是在顺序表上实现的，在链表上无法实现排序方法D.在顺序表上实现的排序方法都可以在链表上实现3.（）以下不属于内部排序方法的是（）。

A.选择排序B. 插入排序C. 归并排序D. 拓扑排序10.2插入排序填空题1. 在对一组记录（54, 38, 96, 23，15，72，60，45, 83）进行直接插入排序时，当把第个记录60插入到有序表时，为寻找插入位置至少需比较______________ 次。

二、选择题：1.（）排序方法中，从未排序序列中依次取出元素与已排序序列（初始时空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（）。

A. 希尔排序B. 冒泡排序C. 插入排序D. 选择排序2.（）折半插入排序算法的平均情况下的时间复杂度为（）。

2 3A. O（n）B. O （nlog 2n）C. O （n ）D. O （n ）3.（）对含有n个元素的顺序表采用直接插入排序方法进行排序，在最坏情况下所需的比较次数是（）。

A.n-1B. n+1C. n/2D. n（n-1）/2三、简答题1.给出关键字序列{4,5,1,2,8,6,7,3,10,9} 的直接插入排序过程。

第一章1．典型的编译程序在逻辑功能上由哪几部分组成答：编译程序主要由以下几个部分组成：词法分析、语法分析、语义分析、中间代码生成、中间代码优化、目标代码生成、错误处理、表格管理。

2. 实现编译程序的主要方法有哪些答：主要有：转换法、移植法、自展法、自动生成法。

3. 将用户使用高级语言编写的程序翻译为可直接执行的机器语言程序有哪几种主要的方式答：编译法、解释法。

4. 编译方式和解释方式的根本区别是什么答：编译方式：是将源程序经编译得到可执行文件后，就可脱离源程序和编译程序单独执行，所以编译方式的效率高，执行速度快；解释方式：在执行时，必须源程序和解释程序同时参与才能运行，其不产生可执行程序文件，效率低，执行速度慢。

、第二章1.乔姆斯基文法体系中将文法分为哪几类文法的分类同程序设计语言的设计与实现关系如何答：1）0型文法、1型文法、2型文法、3型文法。

2）2. 写一个文法，使其语言是偶整数的集合，每个偶整数不以0为前导。

答：Z SME | B{S1|2|3|4|5|6|7|8|9M | D | MDD0|SB2|4|6|8E0|B3. 设文法G为：N D|NDD 0|1|2|3|4|5|6|7|8|9请给出句子123、301和75431的最右推导和最左推导。

答：N ND N3ND3N23D23123%N ND NDD DDD1DD12D123N ND N1ND1N01D01301N ND NDD DDD3DD30D301N ND N1ND1N31ND31N431ND431N5431D543175431N ND NDD NDDD NDDDD DDDDD7DDDD75DDD754DD7543D75431 4. 证明文法S iSeS|iS| i是二义性文法。

答：对于句型iiSeS存在两个不同的最左推导：S iSeS iiSesS iS iiSeS所以该文法是二义性文法。

…5. 给出描述下面语言的上下文无关文法。

数组指针01：逆序输出从键盘输入n个整数（n<100），存放在一个一维数组中，逆序输出能被3整除的元素，并逆序输出数组下标为3的倍数的元素。

输入格式：第一个整数为个数n，后续为n个整数输出格式：第一行能被3整除的元素，第二行为下标为3的倍数的元素，各个数值之间用空格分隔。

输入：10 2 7 9 10 5 4 3 6 8 20输出：6 3 920 3 10 2#include <iostream>using namespace std;const int MAX=100;int main(){int a[MAX],n,i;cin>>n;for(i=0;i<n;i++)cin>>a[i];for(i=n-1;i>=0;i--)if(a[i]%3==0)cout<<a[i]<<" ";cout<<endl;for(i=n-1;i>=0;i--)if(i%3==0)cout<<a[i]<<" ";cout<<endl;return 0;}数组指针02：逆序存储从键盘输入n（n<100）个整数，存放在一个一维数组a中，将它们逆序存放在另一个整型数组b中，并按b数组中下标从小到大的顺序输出下标为3的倍数的数组元素。

输入格式：第一个数为数组中元素个数n，之后为n个元素。

输出格式：下标为3的倍数的元素，各个数值之间用空格分隔。

输入：10 2 7 9 10 5 4 3 6 8 20输出：20 3 10 2#include <iostream> using namespace std; const int MAX=100;int main(){int a[MAX],b[MAX],n,i; cin>>n;for(i=0;i<n;i++){cin>>a[i];b[n-1-i]=a[i];}for(i=0;i<n;i++)if(i%3==0)cout<<b[i]<<" ";cout<<endl;return 0;}数组指针03：平均值从键盘输入任意个整数（以0结束，假设不超过100个），存放在一个一维数组中，计算这组数的平均值（实型）。

习题八查找一、单项选择题1．顺序查找法适合于存储结构为（）的线性表。

A. 散列存储Ｂ. 顺序存储或链式存储C. 压缩存储D. 索引存储2．若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录,其平均查找长度AＳL为( )。

Ａ． (n－1）/2 B． n/2 C. (ｎ+1）／２ D. n3.适用于折半查找的表的存储方式及元素排列要求为（ )Ａ．链接方式存储,元素无序 B．链接方式存储,元素有序Ｃ.顺序方式存储，元素无序 D．顺序方式存储,元素有序4.当在一个有序的顺序存储表上查找一个数据时,即可用折半查找,也可用顺序查找,但前者比后者的查找速度( )Ａ．必定快 B．不一定 C. 在大部分情况下要快 D．取决于表递增还是递减5．当采用分块查找时，数据的组织方式为 ( )A.数据分成若干块,每块内数据有序B.数据分成若干块,每块内数据不必有序，但块间必须有序,每块内最大（或最小）的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块D．数据分成若干块,每块(除最后一块外)中数据个数需相同6．二叉树为二叉排序树的充分必要条件是其任一结点的值均大于其左孩子的值、小于其右孩子的值。

这种说法（)。

Ａ.正确 B. 错误７. 二叉查找树的查找效率与二叉树的((１） )有关，在（(2) )时其查找效率最低。

(１): A. 高度 B. 结点的多少 C. 树型 D．结点的位置（２)： A. 结点太多Ｂ. 完全二叉树C．呈单枝树Ｄ. 结点太复杂。

8．如果要求一个线性表既能较快的查找,又能适应动态变化的要求，则可采用( ）查找法。

A. 分快查找Ｂ. 顺序查找 C. 折半查找D．基于属性9．分别以下列序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( )。

Ａ.(1０0，80，９0， 60， 12０,110,１30） B.(１00，1２0，110,13０,８0， 60, 90) C．(1０0,6０, 8０, 90, 1２0，１10，130) D. (100,８0，６0, 90, 1２０，13０,１10）１０.下图所示的４棵二叉树，( )是平衡二叉树。