用循环链表实现的有序队列

一、选择：(每题2分，共30分) 简单选择排序 冒泡排序 归并排序 稳定1、下列排序算法中，其中（ ）是稳定的。

堆排序 希尔排序 快速排序 基数排序 不稳定A) 堆排序，冒泡排序 B) 快速排序，堆排序 C) 直接选择排序，希尔排序 D) 归并排序，冒泡排序 2、下列排序方法中，哪一个是稳定的排序方法？（ ）A)堆排序 B)二分法插入排序 C)希尔排序 D)快速排序3、一个栈的输入序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ ）。

A) 2 3 4 1 5 B) 5 4 1 3 2 C) 2 3 1 4 5 D) 1 5 4 3 2 4、非空循环链表head 的尾结点 *p 满足下列( )条件A)head->next==p; B)head==p; C)p->next==head; D)p->next==0 5、下列编码中属前缀码的是( )A){1,01,000,001} B){1,01,011,010} C){0,10,110,11} D){0,1,00,11} 6、对于哈希函数H(key)=key % 7,被称为同义词的关键字是( )A)36和50 B)23和39 C)15和44 D)25和517、将一个长度为n 的向量的第i 个元素删除时，需要前移( )个元素。

A) i B) n-i C) n+1 D) n-i+18、有一个有序表为{ 1，3，9，12，32，41，45，62，77，88，92，100}，用折半查找法，若要找62，要经过( )次比较。

A. 3 B. 6 C. 4 D. 5 9、高度为 K 的二叉树最大的结点数为（ ）。

A)2k B)2k-1 C)2k -1 D)2k-1-110、对表长为n 的顺序表进行顺序查找，在查找概率相等的情况下，查找成功的平均查找长度为( )A) (n-1)/2 B) n/2 C) (n+1)/2 D) n11、如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用（ ）A)深度优先搜索算法 B)广度优先搜索算法 C)求最小生成树的prim 算法 D)拓扑排序算法12、已知有向图的正邻接链表的存储结构如下，从顶点1出发的按深度优先遍历序列是( )。

. . . . .一、单选题第1章绪论1、在数据结构中，从逻辑上可以把数据结构分成A、动态结构和静态结构C、线性结构和非线性结构2、算法分析的两个主要方面是A、空间复杂性和时间复杂性C、可读性和文档性3、数据的不可分割的最小单位是B、紧凑结构和非紧凑结构D、内部结构和外部结构B、正确性和简明性D、数据复杂性和程序复杂性A、结点B、数据元素C、数据项D、数据对象4、在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为A、规则B、集合C、结构D、运算5、与程序运行时间有关的因素主要有以下四方面，其中与算法关系密切的是A、问题的规模C、机器执行速度二、判断题1、数据结构是带有结构的数据元素的集合。

2、程序越短，运行的时间就越少。

3、处理同一问题的算法是唯一的。

B、机器代码质量的优劣D、语句的执行次数4、一个完整算法可以没有输入，但必须有输出。

三、填空题1、______________是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

2、______________结构的数据元素之间存在一对多的关系。

3、数据结构的形式化定义为(D，S)，其中D 是______________的有限集，S 是 D 上关系的有限集。

4、数据结构在计算机中的______________称为存储结构。

5、数据元素之间的关系在计算机中有两种不同的表示方法：顺序映象和非顺序映象，由此- 1 -得到两种不同的存储结构是______________存储结构和______________存储结构。

6、一个算法具有五个特性：______________、______________、______________、有零个或多个输入、有一个或多个输出。

7、评价一个算法的好坏应该从算法的正确性、可读性、___________和_________________等几方面进行。

四、解答题1、设n 为正整数。

数据结构简答题和论述题1、试描述数据结构和抽象数据类型的概念与程序设计语⾔中数据类型概念的区别。

【解答】数据结构是指相互之间存在⼀定关系的数据元素的集合。

⽽抽象数据类型是指⼀个数据结构以及定义在该结构上的⼀组操作。

程序设计语⾔中的数据类型是⼀个值的集合和定义在这个值集上⼀组操作的总称。

抽象数据类型可以看成是对数据类型的⼀种抽象。

串:是零个或多个字符组成的有限序列。

串是⼀种特殊的线性表，它的每个结点仅由⼀个字符组成。

空串 :长度为零的串，它不包含任何字符。

空⽩串 :仅由⼀个或多个空格组成的串⼦串 :串中任意个连续字符组成的⼦序列称为该串的⼦串。

串变量和串常量通常在程序中使⽤的串可分为：串变量和串常量。

（1）串变量 ：串变量和其它类型的变量⼀样，其取值是可以改变的。

（2）串常量 ：串常量和整常数、实常数⼀样，在程序中只能被引⽤但不能改变其值。

即只能读不能写。

（1）树形图表⽰： 树形图表⽰是树结构的主要表⽰⽅法。

（2）树的其他表⽰法① 嵌套集合表⽰法：是⽤集合的包含关系来描述树结构。

② 凹⼊表表⽰法：类似于书的⽬录③ ⼴义表表⽰法：⽤⼴义表的形式表⽰的。

上图 (a)树的⼴义表表⽰法如下：（A（B（E，F（I，J））， C，D（G，H）））1．中序遍历的递归算法定义：若⼆叉树⾮空，则依次执⾏如下操作：(1)遍历左⼦树； (2)访问根结点； (3)遍历右⼦树。

2．先序遍历的递归算法定义：若⼆叉树⾮空，则依次执⾏如下操作：(1) 访问根结点； (2) 遍历左⼦树； (3) 遍历右⼦树。

3．后序遍历得递归算法定义：若⼆叉树⾮空，则依次执⾏如下操作：(1)遍历左⼦树； (2)遍历右⼦树； (3)访问根结点。

2、链表具有的特点是B 插⼊、删除不需要移动元素C 不必事先估计存储空间D 所需空间与线性表长度成正⽐顺序队列（1）队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表。

（2） 顺序队列的表⽰①和顺序表⼀样顺序队列⽤⼀个向量空间存放当前队列中的元素。

一、选择题1-1 下列关于数据和逻辑结构的叙述中，哪一个是不正确的（）。

A ) 数据的逻辑结构是数据间关系的描述B) 数据的逻辑结构抽象反映数据元素间的逻辑关系C) 数据的逻辑结构具体反映数据在计算机中的存储方式D) 数据的逻辑结构分为线性结构和非线性结构C1-2 以下关于数据的存储结构的叙述中哪一条是正确的（）。

A) 数据的存储结构是数据间关系的抽象描述B) 数据的存储结构是逻辑结构在计算机存储器中的实现C) 数据的存储结构分为线性结构和非线性结构D) 数据的存储结构对数据运算的具体实现没有影响B二、简答题1-1 数据结构的存储方式有哪几种？1-2 算法的时间复杂度仅与问题的规模相关吗?1-1 数据结构的存储方式有哪几种？【解析】常用的存储表示方法有四种:1 、顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。

由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。

2 、链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。

由此得到的存储表示称为链式存储结构, 通常借助于程序语言的指针类型描述。

3 、索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。

组成索引表的索引项由结点的关键字和地址组成。

若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index ）。

若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。

4 、散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址。

1-2 算法的时间复杂度仅与问题的规模相关吗?【解析】算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。

但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。

我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。

三、应用题: 分析以下程序段的时间复杂度。

习题集一、填空题⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。

⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。

⑶ 从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。

⑷ 数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。

⑸ 算法具有五个特性，分别是（）、（）、（）、（）、（）。

⑹ 算法的描述方法通常有（）、（）和（）三种，⑺ 在一般情况下，一个算法的时间复杂度是（）的函数。

⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*logn，则表示成数量级的形式为（）。

(9)顺序存储结构的特点是（），链接存储结构的特点是（）。

(10) 在顺序表中，等概率情况下，插入和删除一个元素平均需移动（）个元素，具体移动元素的个数与（）和（）有关。

(11) 顺序表中第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的存储地址是（）。

(12) 设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为（）。

(13) 单链表中设置头结点的作用是（）。

(14) 非空的单循环链表由头指针head指示，则其尾结点（由指针p所指）满足（）。

(15)在由尾指针rear指示的单循环链表中，在表尾插入一个结点s的操作序列是（）；删除开始结点的操作序列为（）。

(16) 一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时间复杂度为（）；在给定值为x的结点后插入一个新结点的时间复杂度为（）。

（17）已知一维数组A采用顺序存储结构，每个元素占用4个存储单元，第9个元素的地址为144，则第一个元素的地址是（）。

A 108B 180C 176D 112（18）在长度为n的线性表中查找值为x的数据元素的时间复杂度为：（）。

A O(0)B O(1)C O(n)D O(n2)（19）在一个长度为n的顺序表的第i（1≤i≤n+1）个元素之前插入一个元素，需向后移动（）个元素，删除第i（1≤i≤n）个元素时，需向前移动（）个元素。

第二章习题与解答一判断题1．线性表的逻辑顺序与存储顺序总是一致的。

2．顺序存储的线性表可以按序号随机存取。

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

7．线性表的链式存储结构优于顺序存储结构。

8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。

9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

二单选题 (请从下列A，B，C，D选项中选择一项)1．线性表是( ) 。

(A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空；(C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。

2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。

插入一个元素时平均要移动表中的（）个元素。

(A) n/2 (B) n+1/2 (C) n -1/2 (D) n3．线性表采用链式存储时，其地址( ) 。

(A) 必须是连续的；(B) 部分地址必须是连续的；(C) 一定是不连续的；(D) 连续与否均可以。

4．用链表表示线性表的优点是（）。

(A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和删除(D)数据元素的物理顺序与逻辑顺序相同5．某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。

(A)单链表(B)双链表(C)单循环链表(D)带头结点的双循环链表6．循环链表的主要优点是( )。

(A)不在需要头指针了(B)已知某个结点的位置后，能够容易找到他的直接前趋(C)在进行插入、删除运算时，能更好的保证链表不断开(D)从表中的任意结点出发都能扫描到整个链表7．下面关于线性表的叙述错误的是( )。

《数据结构》习题库之三：判断题1. 程序就是算法，但算法不一定是程序。

（）2. 线性表只能采用顺序存储结构或者链式存储结构。

（）3. 线性表的链式存储结构是通过指针来间接反映数据元素之间逻辑关系的。

（）4. 除插入和删除操作外，数组的主要操作还有存取、修改、检索和排序等。

（）5. 稀疏矩阵中0元素的分布有规律，因此可以采用三元组方法进行压缩存储。

（）6. 不管堆栈采用何种存储结构，只要堆栈不空，可以任意删除一个元素。

（）7. 确定串Ｔ在串Ｓ中首次出现的位置的操作称为串的模式匹配。

（）8. 深度为h的非空二叉树的第i层最多有2i-1 个结点。

（）9. 满二叉树就是完全二叉树。

（）10. 已知一棵二叉树的前序序列和后序序列可以唯一地构造出该二叉树。

（）11. 非空二叉排序树的任意一棵子树也是二叉排序树。

（）12. 对一棵二叉排序树进行前序遍历一定可以得到一个按值有序的序列。

（）13. 若有向图G=(V,E)的拓扑序列不唯一，则图中必须有两条弧和。

（）14. 散列表的查找效率主要取决于所选择的散列函数与处理冲突的方法。

（）15. 序列初始为逆序时，泡排序法所进行的元素之间的比较次数最多。

（）16. 算法一定要有输入和输出。

（）17. 算法分析的目的旨在分析算法的效率以求改进算法。

（）18. 非空线性表中任意一个数据元素都有且仅有一个直接后继元素。

（）19. 数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。

（）20. 线性链表中各个链结点之间的地址不一定要连续。

（）21. 若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适。

（）22. 若线性表采用顺序存储结构，每个数据元素占用4个存储单元，第12个数据元素的存储地址为144，则第1个数据元素的存储地址是101。

（）23. 若长度为n的线性表采用顺序存储结构，删除表的第i个元素之前需要移动表中n-i+1个元素。

（）24. 符号link(p)出现在表达式中表示p所指的那个结点的内容。

c语言中linklist的作用C语言中LinkList的作用什么是LinkListLinkList（链表）是C语言中用来存储和操作数据的一种数据结构。

它与数组相比，拥有更灵活的插入和删除操作。

链表由节点（Node）组成，每个节点包含一个数据项和一个指向下一个节点的指针。

链表的头节点是链表的起始点，尾节点则指向NULL。

LinkList的作用1.动态内存分配：链表的节点可以动态地分配和释放内存，因此链表可以根据实际需要进行动态的添加和删除操作，不受固定大小的限制。

2.插入和删除操作效率高：由于链表的特性，插入和删除操作只需要修改节点指针的指向，而不需要移动其他节点，因此链表在某些特定场景下可以比数组更高效。

3.实现高级数据结构：链表可以用来实现其他高级数据结构，比如栈（Stack）和队列（Queue），或者作为其他数据结构的底层实现。

4.提供灵活的数据结构设计：链表可以设计成单向链表、双向链表或循环链表，根据实际需求选择合适的链表结构。

LinkList的应用场景链表在许多编程问题中都有着广泛的应用，以下是一些常见的应用场景： - 线性表：链表可以实现线性表，可以用来存储和操作一组有序的数据。

- 多项式运算：链表可以用来存储和运算多项式，实现多项式的相加、相乘等操作。

- 图的表示：链表可以用来表示图的连接关系，比如邻接链表表示法。

- 高级数据结构：链表可以作为实现其他高级数据结构的基础，比如树（Tree）、图（Graph）等。

- 文件操作：链表可以用来实现文件的读取和写入操作，链表可以实现文件的增删改查等功能。

总结链表作为一种灵活和高效的数据结构，广泛应用于C语言的编程中。

通过链表，我们可以动态地分配内存，高效地进行插入和删除操作。

而且，链表还可以作为其他高级数据结构的基础实现，扩展了数据结构的功能和应用场景。

在C语言中，掌握链表的使用方法和原理，对于编写高效的程序和解决复杂的编程问题都有很大的帮助。

队列研究的基本原理队列是一种非常重要的数据结构，其基本原理是“先进先出”，即先加入队列的元素先被取出。

队列在计算机科学中被广泛应用，例如操作系统中的进程调度、网络数据包传输等等。

本文将介绍队列的基本原理、应用场景以及常见的队列实现方式。

一、队列的基本原理队列是一种线性数据结构，可以看成是特殊的线性表。

队列的基本操作包括入队和出队。

入队是在队列的尾部添加一个元素，出队是从队列的头部删除一个元素。

由于队列是先进先出的，因此每次出队操作总是删除队列中最早被加入的元素。

队列的头部和尾部分别称为队头和队尾，队头是队列中最早加入的元素，队尾是队列中最后加入的元素。

队列的实现有多种方式，最常见的是使用数组或链表来实现。

使用数组实现队列时，需要定义一个数组来存储队列中的元素，同时使用两个指针front和rear分别指向队列的头部和尾部。

入队操作时，将元素添加到rear指向的位置，同时将rear指针向后移动一位；出队操作时，将front指针向后移动一位，同时删除队头元素。

当front等于rear时，队列为空。

使用链表实现队列时，每个节点包含一个元素和一个指向下一个节点的指针。

使用两个指针front和rear分别指向队列的头部和尾部节点。

入队操作时，新建一个节点并将其添加到rear指向的节点后面，同时将rear指针指向新节点；出队操作时，删除front指向的节点，同时将front指针指向下一个节点。

当front等于rear时，队列为空。

二、队列的应用场景队列在计算机科学中有广泛的应用场景，下面列举几个常见的例子。

1. 操作系统中的进程调度在操作系统中，进程是指正在运行的程序的实例。

操作系统需要管理多个进程的运行，因此需要进行进程调度。

操作系统使用队列来管理进程，将所有等待运行的进程加入到一个队列中，依次从队列中取出进程进行运行。

当一个进程运行结束或等待某些资源时，将其重新加入到队列中等待运行。

2. 网络数据包传输在网络中，数据包是网络传输的基本单位。

数据结构期中期末选择判断复习题判断题：U1-U31.（×）数据元素是数据的最小单位。

2.（√）健壮的算法不会因非法的输入数据而出现莫名其妙的状态。

3.（×）数据的逻辑结构是指数据的各数据项之间的逻辑关系。

4.（×）数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。

5.（×）数据的物理结构是指数据在计算机内的实际存储形式。

6.（×）数据结构的抽象操作的定义与具体实现有关。

7.（×）顺序存储方式的优点是存储密度大，且插入，删除运算效率高。

8.（√）顺序存储方式插入和删除时的效率太低，在这方面它不如链式存储方式好。

9.（√）顺序存储结构的主要缺点是不利于插入和删除操作。

10.（×）对任何数据结构链式存储结构一定优于顺序存储结构。

11.（×）取线性表的第i个元素的时间同i的大小有关。

12.（√）线性表、栈和队列都是线性结构。

13.（√）链表是采用链式存储结构的线性表，进行插入、删除操作时，在链表中比在顺序存储结构中效率高。

14.（×）线性表中每一个元素均存在唯一一个前驱和唯一一个后继。

15.（×）循环链表不是线性表。

16.（×）线性表的长度是线性表所占用的存储空间的大小。

17.（×）在单链表表示的线性表中，取线性表的第i个元素操作的时间复杂度为O(1)。

18.（√）删除带头结点单链表的第一个元素结点的时间复杂度是O(1)。

19.（√）栈是实现过程和函数等子程序所必需的结构。

20.（√）栈是一种插入与删除操作都限定在表的一端进行的线性表。

21.（√）若输入序列为1,2,3,4,5,6,则通过一个栈可以输出序列3,2,5,6,4,1。

22.（×）在顺序存储结构表示的栈中删除一个元素时可能会引起栈内数据元素的移动。

23.（√）栈既可以采用顺序存储结构表示也可以采用链式存储结构表示。