下载文档原格式
山东科技大学
2018年硕士研究生入学考试试题
考试科目：数据结构与操作系统 科目代码：823
《数据结构》部分
一、简答题（30分，每题5分）
1、串、数组、广义表从元素间关系上可以看成线性结构，它们与
一般意义上的线性表相比有何特殊性？
2、借助栈可以实现更复杂的操作，请简述如何利用栈实现对表达
式中括号是否匹配的检验。
3、基于关键字比较的查找算法所能达到最优时间复杂度是？能否
设计一种与问题规模无关的查找算法？请给出基本思路。
4、图的广度优先遍历与树的何种遍历策略相似？请给出简单解释。
5、《数据结构》中经常采用“树形化组织”的方式来整理数据，
比如折半查找表、二叉排序树、大顶堆/小顶堆等，请简述这样
做的优点。
6、何为稳定的排序方法？何为不稳定的排序方法？哪些排序算法
是不稳定的？
二、综合应用题（40分，每题10分）
1、假设用于通信的电文共有8个字母A,B,C,D,E,F,G,H组成，字
母在电文中出现的频率分别是{0.2，0.04，0.06，0.02，0.12，
0.24，0.25，0.07}。
①试为这8个字符设计哈夫曼编码；
②试设计另一种由二进制表示的等长编码方案；。
数据结构复习题（课程代码 252259）一、填空题（本大题共40小题）1.队列中是按照______先进先出______的原则进行数据元素的增删。
2.___栈__又称为LIFO表。
3.在顺序存储的完全二叉树中，若编号为i的结点有左孩子结点，则其右孩子结点的编号为___2i+1___。
4.存储地址与关键字之间存在某种映射关系的存储结构为_______散列存储结构_______。
5.在串S=“structure”中，以r为首字符的子串有_9_个。
6.设有整型二维数组M[4][3]，每个元素（整数）占2个存储单元，元素按行的顺序存储，数组的起始地址为200，元素M[1][1]的地址是___208____。
7.在一个具有n个顶点的无向完全图中，包含有___ n(n-1)/2_____条边，在一个具有n个顶点的有向完全图中，包含有__ n(n-1)______条边。
8.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元素成为一个子表，则得到的四个子表分别为_____（12，40）（）（74）（23,55，63）____。
9.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度____增加1______。
10.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为__ O(log2n)______，整个堆排序过程的时间复杂度为__ O(nlog2n)______。
11.在快速排序、堆排序、归并排序中，____归并_____排序是稳定的。
12.一棵深度为5的满二叉树中的结点数为_______31_______个。
13.在含n个顶点和e条边的无向图的邻接矩阵中,非零元素的个数为__2e __。
14.从一棵二叉排序树中查找一个元素时，若元素的值大于根结点的值，则继续向____右子树____查找。
15._____拓朴排序______可以判断出一个有向图中是否有环。
数据结构与算法(Python版)《数据结构》参考答案(A卷)数据结构与算法是计算机科学中非常重要的基础知识，它们在软件开辟中起着至关重要的作用。
在Python编程语言中，数据结构与算法同样扮演着重要的角色。
本文将介绍数据结构与算法在Python中的应用，匡助读者更好地理解和运用这些知识。
一、数据结构1.1 列表(List)Python中最常用的数据结构之一是列表，它可以存储任意类型的数据，并且支持增删改查等操作。
1.2 字典(Dictionary)字典是另一个常用的数据结构，它以键值对的形式存储数据，可以快速查找和修改数据。
1.3 集合(Set)集合是一种无序且不重复的数据结构，可以进行交集、并集、差集等操作，非常适合处理数学运算。
二、算法2.1 排序算法Python中有多种排序算法可供选择，如冒泡排序、快速排序、归并排序等，每种算法都有其适合的场景和特点。
2.2 查找算法查找算法用于在数据集中查找指定的元素，常见的查找算法有线性查找、二分查找等，可以提高查找效率。
2.3 图算法图算法是一类特殊的算法，用于解决图结构中的问题，如最短路径、最小生成树等，在网络分析和路由规划中有广泛应用。
三、应用实例3.1 数据处理数据结构与算法在数据处理中有着重要的应用，可以匡助我们高效地处理大量数据，如数据清洗、分析和建模等。
3.2 网络编程在网络编程中，我们时常需要使用数据结构与算法来处理网络数据包、路由信息等，确保网络通信的稳定和高效。
3.3 人工智能在人工智能领域，数据结构与算法也扮演着重要的角色，如机器学习算法中的数据预处理、特征选择等。
四、优化技巧4.1 空间复杂度优化在编写代码时，我们应该尽量减少空间复杂度，避免不必要的内存占用，提高程序的运行效率。
4.2 时间复杂度优化算法的时间复杂度直接影响程序的运行速度，我们可以通过选择合适的算法和数据结构来优化时间复杂度。
4.3 算法优化技巧除了选择合适的数据结构和算法外，我们还可以通过优化代码逻辑、减少循环嵌套等方式来提高程序的性能。
Python 程序设计语言基础知识一、Python 的基本数据类型二、(1)算术运算符：**、*、/、//、%、＋、－。
(2)关系运算符：<、<＝、>、>＝、＝＝、！＝、in 。
“==”表示判断，“=”表示赋值。
(3)逻辑运算符：not 、and 、or 。
(5)x ＋＝1：将变量x 的值加1，与“x ＝x ＋1”等价，类似还有“－＝”、“*＝”、“/＝”、“%＝” (6)取某三位数n 各个位的方法：个位：n % 10 十位： n // 10 % 10 或n %100 // 10 百位： n //100 三、字符串字符串是用单引号(')、双引号(″)或三引号(''')括起来的一个字符序列，起始和末尾的引号必须要一致。
1.字符串的特点(1)字符串是不可变对象。
即一旦创建了一个字符串，那么这个字符串的内容是不可改变的。
(2)通过索引来访问字符串中的字符。
索引表示字符在字符串的位置，第一个元素的索引号是0，第二个元素的索引号是1，以此类推。
2.字符串的切片操作通过字符串的切片操作可以获得字符串的一个子串。
格式为：字符串名[start ：end ：step]step 默认为1，表示返回下标从start 到end －1的字符构成的一个子串。
四、列表列表是由0个或多个元素组成的序列，其中的元素可以是数字、字符串等混合类型的数据，甚至是其他的列表。
1.列表的特点(1)列表用[]表示，元素间用逗号分隔，不同类型的元素可以存储在同一列表中。
(2)列表的大小是可变的，可以根据需要增加或缩小。
(3)列表是可变对象。
一个列表被创建后，可以直接修改列表中的元素值。
2.列表的访问列表中的元素是通过索引来定位的，第一个元素的索引号是0。
列表中的元素可以通过索引进行访问。
3.列表的切片操作列表的切片形式为list[i ：j ：k]，i 为起始位置索引(包含)，默认为0，j 为终止位置索引(不含)，默认至序列尾；k 为切片间隔，默认为1。
嵌入式常考数据结构嵌入式常考数据结构在嵌入式系统开发中，数据结构是一个非常重要的概念。
它用于组织和管理数据，是实现各种功能和算法的基础。
在本文中，我们将介绍嵌入式常考的一些数据结构及其在嵌入式系统中的应用。
1. 数组（Array）数组是最基本的数据结构之一，它是一种连续存储的数据结构，其中的元素按照顺序存储。
在嵌入式系统中，数组常用于存储一系列的数据，比如传感器采集的数据、图像的像素值等。
通过数组，我们可以方便地对这些数据进行索引和处理。
2. 链表（Linked List）链表是一种非连续存储的数据结构，它由一系列的节点组成，每个节点包含数据和指向下一个节点的指针。
链表可以动态地分配内存，适用于嵌入式系统中对内存空间比较敏感的场景。
在嵌入式系统中，链表常用于实现队列、堆栈等数据结构，以及动态管理内存空间。
3. 栈（Stack）栈是一种具有特定的操作规则的线性数据结构，它采用“先进后出”的原则。
栈常用于保存临时数据、函数调用的返回地址等。
在嵌入式系统中，栈被广泛应用于函数调用、中断处理等场景。
4. 队列（Queue）队列是一种具有特定的操作规则的线性数据结构，它采用“先进先出”的原则。
队列常用于实现任务调度、事件处理等。
在嵌入式系统中，队列可以用于实现消息传递、任务处理等功能。
5. 树（Tree）树是一种非线性的数据结构，它由节点和边组成，每个节点可以有多个子节点。
树常用于组织和管理具有层次关系的数据。
在嵌入式系统中，树广泛应用于文件系统、配置管理、数据压缩等领域。
6. 图（Graph）图是一种由节点和边组成的非线性数据结构，节点之间的关系可以是任意的。
图常用于描述网络拓扑、路径规划等。
在嵌入式系统中，图可以用于实现网络通信、最短路径算法等。
7. 哈希表（Hash Table）哈希表是一种根据关键字直接访问数据的数据结构，它通过哈希函数将关键字映射到存储位置。
哈希表具有快速查找的特点，常用于实现字典、缓存等。
广东财经大学硕士研究生入学考试试卷考试年度：2023年考试科目代码及名称：809-数据结构适用专业：085404计算机技术［友情提醒：请在考点提供的专用答题纸上答题，答在本卷或草稿纸上无效！］、一、单选题（10题，每题1分，共10分）1.算法的时间复杂度取决于（）。
A.问题的规模B.待处理数据的初态C.计算机的配置D.A和B2.某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。
A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表3.设一个栈的输入序列是1，2，3，4，5,则下列序列中，（）是栈的合法输出序列。
A. 5 1 2 3 4B. 4 5 1 3 2C. 4 3 1 2 5D. 3 2 1 5 44.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为( )。
A. 1和5B. 2和4C. 4和2D. 5和15.下面关于串的的叙述中，（）是不正确的。
A．串是字符的有限序列B．空串是由空格构成的串C．模式匹配是串的一种重要运算D．串既可以采用顺序存储，也可以采用链式存储6.设给定权值总数有n个，其哈夫曼树的结点总数为( ) 个。
A．不确定B．2n C．2n+1 D．2n-17.具有k条边的无向图，对其邻接矩阵的对称性及非零元素的数量，下列说法正确的是（）。
A. 不对称2k个B.对称2k个C. 不对称k个D. 对称k个8.对50个记录的有序表作折半查找，当查找失败时，至少需要比较（）次关键字。
A．3 B．4 C．5 D．69.不能保证每趟排序至少能将一个元素放到其最终位置上的排序方法是（）。
A.插入排序B. 快速排序C. 冒泡排序D. 堆排序10.下列几种排序方法中，（）是稳定的排序方法。
A.堆排序、冒泡排序B. 快速排序、堆排序C.希尔排序、归并排序D. 归并排序、冒泡排序二、简答题（5题，每题10分，共50分）1. 以下是二叉链表存储结构的表示，s是初值为0的全局变量。
数据结构考研笔记整理（全）一、第二章线性表●考纲内容●一、线性表的基本概念●线性表是具有相同数据结构类型的n个数据元素的有限序列；线性表为逻辑结构，实现线性表的存储结构为顺序表或者链表●二、线性表的实现●1、顺序表●定义(静态分配)●#define MaxSize 50 \\ typedef struct{ \\ ElemType data[MaxSize];\\ intlength;\\ }SqList;●定义(动态分配)●#define MaxSize 50\\ typedef strcut{\\ EleType *data; //指示动态非配数组的指针\\ int MaxSize,length;\\ }SqList;●c的动态分配语句为L.data=(ElemType*)malloc(sizeof(ElemType)*InitSize);●c++动态分配语句为L.data=new ElemType[InitSize];●插入操作●删除操作●按值寻找●2、链表●单链表●单链表的定义●●头插法建立单链表●●尾插法建立单链表●●按序号查找getElem(LinkList L,int i)和按值查找locateElem(LinkListL,ElemType e)●插入结点（后插）●p=getElem(L,i-1); //查找插入位置的前驱结点\\ s.next=p.next;\\p.next=s;●将前插操作转化为后插操作,即先将s插入的p的后面然后调换s和p的数据域●s.next=p.next;\\ p.next=s.next;\\ temp=p.data;\\ p.data=s.data;\\s.data=temp;●删除结点●p.getElem(L,i-1);\\ q=p.next;\\ p.next=q.next;\\ free(q);●双链表（结点中有prior指针和next指针）●循环链表●静态链表●借助数组来描述线性表的链式存储结构，结点中的指针域next为下一个元素的数组下标●三、线性表的应用●使用的时候如何选择链表还是顺序表？●表长难以估计，经常需要增加、删除操作——链表;表长可以估计，查询比较多——顺序表●链表的头插法，尾插法，逆置法，归并法，双指针法；顺序表结合排序算法和查找算法的应用●小知识点（选择题）二、第三章栈，队列和数组●考纲内容●一、栈和队列的基本概念●栈：后进先出，LIFO，逻辑结构上是一种操作受限的线性表●队列：先进先出，FIFO，逻辑结构上也是一种操作受限的线性表●二、栈和队列的顺序存储结构●栈的顺序存储●●队列的顺序存储●进队：队不满时，送值到队尾元素，再将队尾指针加一●出队：队不空时，取队头元素值，再将队头指针加一●判断队空：Q.front==Q.rear==0;●循环队列（牺牲一个单元来区分队空和队满，尾指针指向队尾元素的后一个位置，也就是即将要插入的位置）●初始：Q.front==Q.rear●队满：(Q.rear+1)%MaxSize=Q.front●出队，队首指针进1:Q.front=(Q.front+1)%MaxSize●入队，队尾指针进1:Q.rear=(Q.rear+1)%MaxSize●队列长度：(Q.rear+MaxSize-Q.front)%MaxSize●三、栈和队列的链式存储结构●栈的链式存储●●队列的链式存储●实际是上一个同时带有头指针和尾指针的单链表，尾指针指向单链表的最后一个结点，与顺序存储不同,通常带有头结点●四、多维数组的存储●行优先：00，01，02，10，11，12●列优先：00，10，01，11，02，12●五、特殊矩阵的压缩存储●对称矩阵●三角矩阵●三对角矩阵（带状矩阵）●稀疏矩阵●将非零元素及其相应的行和列构成一个三元组存储●十字链表法●六、栈、队列、数组的应用●栈在括号匹配中的应用●栈在递归中的应用●函数在递归调用过程中的特点：最后被调用的函数最先执行结束●队列在层次遍历中的应用●二叉树的层次遍历●1跟结点入队●2若队空，则结束遍历，否则重复3操作●3队列中的第一个结点出队并访问，若有左孩子，则左孩子入队；若有右孩子，则右孩子入队●重点为栈的(出入栈过程、出栈序列的合法性)和队列的操作及其特征●小知识点(选择题)●n个不同元素进栈，出栈元素不同排列的个数为{2n\choose n }/(n+1)●共享栈是指让两个顺序栈共享一个存储空间，将两个栈的栈底分别设置在共享空间的两端，两个栈顶向共享空间的中间延伸，可以更有效的利用存储空间，同时对存储效率没有什么影响●双端队列是指允许两端都可以进行入队和出队操作的队列●输出受限的双端队列：允许两端插入，只允许一端删除●输入受限的双端队列：允许两端删除，只允许一端插入三、第四章串●考纲内容●字符串模式匹配●暴力算法●注意指针回退时的操作是i=i-j+2;j=j+1;●kmp算法●手工求next数组时，next[j]=s的最长相等前后缀长度+1，其中s为1到j-1个字符组成的串●在实际kmp算法中，为了使公式更简洁、计算简单，如果串的位序是从1开始的，则next数组需要整体加一；如果串的位序是从0开始的，则next数组不需要加一●根据next数组求解nextval数组：如果p[j]==p[next[j]]，则nextval[j]=nextval[next[j]]，否则nextval[j]=next[j];●小知识点●串和线性表的区别：1线性表的数据元素可以不同，但串的数据元素一般是字符；2串的操作对象通常是子串而不是某一个字符四、第五章树与二叉树●考纲内容●一、树的基本概念●定义●树是一种递归的数据结构，是一种逻辑结构●树的性质●结点数为n，则边的数量为n-1●树中的结点数等于所有结点的度数之和加1（一个结点的孩子个数称为该结点的度，树中结点的最大度数称为树的度，每一条边表示一个结点，对应一个度，只有根结点上面无边，故结点树=度数之和+1）●度为m的树中第i层至多有m^{i-1}个结点（i\geq1）（m叉树的第i层最多有m^{i-1}个结点）●高度为h的m叉树至多有(m^h-1)/(m-1)个结点（假设每一个结点都有m个孩子，则由等比数列的求和公式可以推导出该式子）●具有n个结点的m叉树的最小高度是\lceil log_m(n(m-1)+1)\rceil（由高度为h的m叉树的最大结点树公式有，n满足式子(m^{h-1}-1)/(m-1) \leq n\leq (m^h-1)/(m-1)）●高度为h的m叉树至少有h个结点；高为h，度为m的树至少有h+m-1个结点（m叉树并不等于度为m的树，m叉树可以为空树，要求所有结点的度小于等于m，而度为m的树一定有一个结点的度数为m）●二、二叉树●二叉树的定义及其主要特征●定义●特点●每个结点至多只有两颗子树●二叉树是有序树，其子树有左右之分，次序不能颠倒，否则将成为另一颗二叉树，即使树中结点只有一颗子树，也要区分他是左子树还是右子树●特殊的二叉树●满二叉树：高度为h，结点数为2^h-1，所有叶子结点都集中在二叉树的最下面一层，除叶子结点外的所有结点度数都为2，从根结点为1开始编号，对于编号为i的结点，其父结点为\lfloor i/2 \rfloor，左孩子(若有)编号为2i，右孩子(若有)编号为2i+1，所以编号为偶数的结点只可能是左孩子，编号为奇数的结点只可能是右孩子●完全二叉树：删除了满二叉树中编号更大的结点，高为h，结点数为n的完全二叉树的每个结点的编号都与高度为h的满二叉树中编号为1到n的结点相同。
大一python常考知识点Python作为一门广泛应用于编程领域的高级编程语言，具有简洁、易读和强大的特点，因此在大一的学习过程中也成为了常考的重要知识点。
本文将介绍一些大一Python常考的知识点，以帮助您更好地掌握这门编程语言。
1. 变量与数据类型在Python中，变量用于存储数据，并且不需要事先声明。
常见的数据类型包括整数(int)、浮点数(float)、字符串(str)、布尔值(bool)等。
Python还提供了列表(list)、元组(tuple)和字典(dictionary)等数据结构，用于存储多个数据。
2. 条件语句与循环语句条件语句用于根据条件判断执行不同的代码块。
常用的条件语句包括if语句和if-else语句。
循环语句用于重复执行某一段代码，常见的循环语句包括for循环和while循环。
3. 函数与模块函数是一段可重复使用的代码块，可以接受参数并返回结果。
使用函数可以简化代码的编写与维护。
Python提供了许多内置函数，同时也可以自定义函数。
此外，Python还支持模块化编程，可以通过导入模块来扩展功能。
4. 字符串处理Python提供了强大的字符串处理功能。
可以使用索引与切片操作来访问字符串中的字符或子串，还可以使用内置的字符串方法来实现字符串的格式化、拼接、查找与替换等操作。
5. 列表与字典操作列表(list)是一种有序且可变的数据结构，可以存储多个元素。
可以通过索引访问列表中的元素，并且可以通过内置方法来添加、删除、修改和排序列表中的元素。
字典(dictionary)是一种无序且可变的数据结构，由键值对组成。
可以通过键来访问字典中的值，也可以通过内置方法来添加、删除和修改字典中的元素。
6. 文件操作在Python中，可以使用内置的open函数来进行文件操作。
可以打开文件、读取文件内容、写入文件内容和关闭文件。
使用文件操作可以实现文件的读取与写入，进而实现数据的存储与读取。
7. 异常处理异常处理是一种处理程序运行时可能出现的错误的方式。
代码考试题及答案题目一：基础数据结构编写一个函数，该函数接收一个整数数组作为参数，并返回数组中所有元素的总和。
题目二：排序算法实现一个冒泡排序算法，对给定的整数数组进行排序，并返回排序后的数组。
题目三：递归算法编写一个递归函数，计算并返回斐波那契数列的第n项。
题目四：动态规划给定一个整数数组，找到子数组的最大和。
题目五：图算法实现一个深度优先搜索（DFS）算法，用于遍历图。
答案题目一：基础数据结构```pythondef sum_of_elements(array):total = 0for element in array:total += elementreturn total```题目二：排序算法```pythondef bubble_sort(array):n = len(array)for i in range(n):for j in range(0, n-i-1):if array[j] > array[j+1]:array[j], array[j+1] = array[j+1], array[j] return array```题目三：递归算法```pythondef fibonacci(n):if n <= 1:return nelse:return fibonacci(n-1) + fibonacci(n-2)```题目四：动态规划```pythondef max_subarray_sum(array):max_current = max_global = array[0]for i in range(1, len(array)):max_current = max(array[i], max_current + array[i])if max_current > max_global:max_global = max_currentreturn max_global```题目五：图算法```pythondef dfs(graph, start, visited=None):if visited is None:visited = set()visited.add(start)print(start)for neighbor in graph[start] - visited:dfs(graph, neighbor, visited)```请注意，以上代码示例仅用于演示，实际考试题目和答案可能会有所不同。
东北大学2021年硕士研究生招生考试考试大纲科目代码：858；科目名称：C语言程序设计与数据结构一、考试性质C语言程序设计与数据结构是软件学院软件工程专业和电子信息专业（专业代码：083500、085400）硕士生入学考试初试的专业课之一。
考试对象为参加软件学院软件工程专业和电子信息专业2021年全国硕士研究生招生考试入学考试的准考考生。
二、考试形式与试卷结构（一）考试形式：闭卷，笔试（二）考试时间：180分钟（三）考试题型及比例（均为约占）：选择题（30%），填空题（10%），程序设计题（20%），应用题（26.7%），算法设计题（13.3%）。
（四）参考书目：李周芳译《标准C程序设计》（第7版），清华大学出版社2017.07，严蔚敏，吴伟民编著《数据结构》（C语言版）清华大学出版社2018.06。
三、考查要点（一）C语言程序设计部分（1）掌握常量、变量的概念，掌握常见数据类型（字符型、整型和浮点型）变量的定义和使用。
（2）掌握各种运算符的使用方法并理解运算符的优先级和关联性。
（3）掌握各种数据类型的输入、输出，掌握数据类型之间的转换规则。
（4）熟练使用条件语句（含if、if-else、switch）、循环语句（含while、do-while、for语句，包括循环嵌套和break语句与continue语句），掌握顺序、分支、循环三种基本程序结构，以及基本程序结构的堆叠和嵌套。
（5）熟练掌握一维数组、二维数组的定义和使用，熟练掌握字符串的定义和使用、掌握字符串处理函数的定义和使用。
（6）熟练掌握函数的定义和调用，理解函数的递归和嵌套调用，了解不同类型存储变量的定义、使用范围和生命周期。
（7）熟练掌握结构体的定义和使用，掌握结构体数组的定义和使用。
（8）理解指针的定义，掌握通过指针访问数组、字符串和结构体的方法。
（9）掌握文件的定义及处理方法。
（二）数据结构部分（1）理解数据结构的基本概念和术语，掌握数据的逻辑结构、存储结构及其差异，掌握算法的概念，掌握分析算法时间复杂度和空间复杂度的方法。
Status Init_SqList( SqList *L ){ L->elem_array=( ElemType * )malloc(MAX_SIZE*sizeof( ElemType ) ) ; if ( !L -> elem_array ) return ERROR ;else { L->length= 0 ; return OK ; }}顺序线性表插入Status Insert_SqList(Sqlist *L，int i ，ElemType e){ int j ;if ( i<0||i>L->length-1) return ERROR ;if (L->length>=MAX_SIZE){ printf(“线性表溢出!\n”); return ERROR ; }for ( j=L->length–1; j>=i-1; --j )L->Elem_array[j+1]=L->Elem_array[j];/* i-1位置以后的所有结点后移 */L->Elem_array[i-1]=e; /* 在i-1位置插入结点 */L->length++ ;return OK ;}ElemType Delete_SqList(Sqlist *L，int i){ int k ; ElemType x ;if (L->length==0){ printf(“线性表L为空!\n”); return ERROR; }else if ( i<1||i>L->length ){ printf(“要删除的数据元素不存在!\n”) ;return ERROR ; }else { x=L->Elem_array[i-1] ; /*保存结点的值*/for ( k=i ; k<L->length ; k++)L->Elem_array[k-1]=L->Elem_array[k];/* i位置以后的所有结点前移 */L->length--; return (x);}}Status Locate_Delete_SqList(Sqlist *L，ElemType x)/* 删除线性表L中值为x的第一个结点 */{ int i=0 , k ;while (i<L->length) /*查找值为x的第一个结点*/{ if (L->Elem_array[i]!=x ) i++ ;else{ for ( k=i+1; k< L->length; k++)L->Elem_array[k-1]=L->Elem_array[k];L->length--; break ;}}if (i>L->length){ printf(“要删除的数据元素不存在!\n”) ;return ERROR ; }return OK;}顺序链式表的创建（头插法）LNode *create_LinkList(void)/* 头插入法创建单链表,链表的头结点head作为返回值 */ { int data ;LNode *head, *p;head= (LNode *) malloc( sizeof(LNode));head->next=NULL; /* 创建链表的表头结点head */while (1){ scanf(“%d”, &data) ;if (data==32767) break ;p= (LNode *)malloc(sizeof(LNode));p–>data=data; /* 数据域赋值 */p–>next=head–>next ; head–>next=p ;/* 钩链，新创建的结点总是作为第一个结点 */}return (head);}LNode *create_LinkList(void)/* 尾插入法创建单链表,链表的头结点head作为返回值 */ { int data ;LNode *head, *p, *q;head=p=(LNode *)malloc(sizeof(LNode));p->next=NULL; /* 创建单链表的表头结点head */while (1){ scanf(“%d”,& data);if (data==32767) break ;q= (LNode *)malloc(sizeof(LNode));q–>data=data; /* 数据域赋值 */q–>next=p–>next; p–>next=q; p=q ;/*钩链，新创建的结点总是作为最后一个结点*/}return (head);}ElemType Get_Elem(LNode *L ， int i){ int j ; LNode *p;p=L->next; j=1; /* 使p指向第一个结点 */while (p!=NULL && j<i){ p=p–>next; j++; } /* 移动指针p , j计数 */if (j!=i) return(-32768) ;else return(p->data);/* p为NULL 表示i太大; j>i表示i为0 */}按值查找LNode *Locate_Node(LNode *L，int key)/* 在以L为头结点的单链表中查找值为key的第一个结点 */ { LNode *p=L–>next;while ( p!=NULL&& p–>data!=key) p=p–>next;if (p–>data==key) return p;else{ printf(“所要查找的结点不存在!!\n”);retutn(NULL);}}单链表插入void Insert_LNode(LNode *L，int i，ElemType e)/* 在以L为头结点的单链表的第i个位置插入值为e的结点 */ { int j=0; LNode *p，*q;p=L–>next ;while ( p!=NULL&& j<i-1){ p=p–>next; j++; }if (j!=i-1) printf(“i太大或i为0!!\n ”);else{ q=(LNode *)malloc(sizeof(LNode));q–>data=e; q–>next=p–>next;p–>next=q;}}顺序链式表，按序号删除void Delete_LinkList(LNode *L， int i)/* 删除以L为头结点的单链表中的第i个结点 */{ int j=1; LNode *p，*q;p=L; q=L->next;while ( p->next!=NULL&& j<i){ p=q; q=q–>next; j++; }if (j!=i) printf(“i太大或i为0!!\n ”);else{ p–>next=q–>next; free(q); }}按值删除void Delete_LinkList(LNode *L，int key)/* 删除以L为头结点的单链表中值为key的第一个结点 */{ LNode *p=L, *q=L–>next;while ( q!=NULL&& q–>data!=key){ p=q; q=q–>next; }if (q–>data==key){ p->next=q->next; free(q); }elseprintf(“所要删除的结点不存在!!\n”);}/* 合并以La, Lb为头结点的两个有序单链表 */LNode *Merge_LinkList(LNode *La， LNode *Lb){ LNode *Lc, *pa , *pb , *pc, *ptr ;Lc=La ; pc=La ; pa=La->next ; pb=Lb->next ; while (pa!=NULL && pb!=NULL){ if (pa->data<pb->data){ pc->next=pa ; pc=pa ; pa=pa->next ; } /* 将pa所指的结点合并，pa指向下一个结点 */if (pa->data>pb->data){ pc->next=pb ; pc=pb ; pb=pb->next ; } /* 将pa所指的结点合并，pa指向下一个结点 */if (pa->data==pb->data){ pc->next=pa ; pc=pa ; pa=pa->next ;ptr=pb ; pb=pb->next ; free(ptr) ; }/* 将pa所指的结点合并，pb所指结点删除 */}if (pa!=NULL) pc->next=pa ;else pc->next=pb ; /*将剩余的结点链上*/free(Lb) ;return(Lc) ;}方法平均时间最坏所需时间附加空间稳定性直接插入 O(n2) O(n2) O(1) 稳定的Shell排序 O(n1.3) O(1) 不稳定的直接选择 O(n2) O(n2) O(1) 不稳定的堆排序 O(n㏒2n) O(n㏒2n) O(1) 不稳定的冒泡排序 O(n2) O(n2) O(1) 稳定的快速排序 O(n㏒2n) O(n2) O(㏒2n) 不稳定的归并排序 O(n㏒2n) O(n㏒2n) O(n) 稳定的基数排序 O(d(n+r)) O(d(n+r)) O(n+r) 稳定的。
