下载文档原格式
数据结构试卷（一）王彬一、单选题（每题2 分，共20分）1.栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时( ).A. 仅修改头指针B. 头、尾指针都要修改C. 仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？( )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置？脚注(10)表示用10进制表示。
cA．688 B．678 C．692 D．6965.树最适合用来表示( )。
A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( d ).A．2k-1 B.2K+1 C.2K-1 D. 2k-17.若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( )A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O（n）C. O（1og2n）D. O（n2）9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9作为散列函数，则散列地址为1的元素有（ c d）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。
A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：____ ____、________、________和_______。
2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。
数据结构考试题及答案一、选择题（每题2分，共20分）1. 以下哪个不是线性数据结构？A. 数组B. 链表C. 树D. 图2. 在一个单链表中，删除一个节点的操作需要知道该节点的：A. 地址B. 值C. 索引D. 前驱节点的引用3. 栈（Stack）是一种：A. 线性表B. 树状结构C. 图结构D. 散列表4. 哈希表解决冲突最常用的方法是：A. 排序B. 链地址法C. 再散列D. 除留余数法5. 以下哪个排序算法是稳定的？A. 快速排序B. 冒泡排序C. 选择排序D. 堆排序二、简答题（每题10分，共30分）1. 简述数组和链表的区别。
2. 解释二叉搜索树的基本概念及其优势。
3. 什么是递归？请给出一个简单的递归算法例子。
三、计算题（每题25分，共50分）1. 给定一个无序数组，请写出一个时间复杂度为O(n log n)的排序算法，并说明其工作原理。
2. 描述如何使用队列来实现一个简单的文本编辑器的撤销和重做功能。
四、编程题（共30分）编写一个函数，该函数接受一个整数数组作为参数，返回数组中所有元素的和。
如果数组为空，返回0。
答案一、选择题1. 答案：C（树和图都是非线性结构）2. 答案：D（需要前驱节点的引用来删除节点）3. 答案：A（栈是一种后进先出的特殊线性表）4. 答案：B（链地址法是解决哈希冲突的常用方法）5. 答案：B（冒泡排序是稳定的排序算法）二、简答题1. 数组和链表的区别：- 数组是连续的内存空间，链表是非连续的。
- 数组的索引访问速度快，链表需要遍历。
- 数组的大小固定，链表动态可变。
2. 二叉搜索树的基本概念及其优势：- 二叉搜索树是一种特殊的二叉树，左子树上所有节点的值小于它的根节点的值，右子树上所有节点的值大于它的根节点的值。
- 优势：支持快速的查找、插入和删除操作。
3. 递归是函数自己调用自己的过程。
例如，计算n的阶乘的递归算法： ```cint factorial(int n) {if (n <= 1) return 1;return n * factorial(n - 1);}```三、计算题1. 快速排序算法：- 选择一个元素作为“基准”（pivot）。
数据结构考试题目和答案一、单项选择题1. 在数据结构中，线性结构和非线性结构的区别在于（）。
A. 结构中元素的个数B. 结构中是否包含子结构C. 结构中元素之间是否有一对一的对应关系D. 结构中元素之间是否有层次关系答案：D2. 一个栈的入栈序列为1, 2, 3, 4, 5，则可能的出栈序列为（）。
A. 4, 3, 2, 5, 1B. 5, 4, 3, 2, 1C. 5, 4, 3, 1, 2D. 1, 2, 3, 4, 5答案：B3. 在二叉树中，度为2的节点数为n，度为1的节点数为m，度为0的节点数为p，则m的值为（）。
A. nB. n-1C. p-1D. p+1答案：B4. 哈希表的冲突解决方法中，开放定址法和链地址法的主要区别在于（）。
A. 是否使用链表B. 是否使用数组C. 是否使用额外的存储空间D. 是否使用线性探测答案：C5. 对于一个无向图，其邻接矩阵表示法中，矩阵的行数和列数分别为（）。
A. 顶点数和边数B. 顶点数和顶点数C. 边数和边数D. 边数和顶点数答案：B二、填空题1. 在顺序表中，插入一个元素平均需要移动元素的个数为表长减1，即 _______ 。
答案：n-12. 快速排序算法的时间复杂度为 _______ 。
答案：O(n^2)3. 折半查找法的平均查找长度为 _______ 。
答案：O(log n)4. 在图的遍历中，深度优先搜索（DFS）使用的栈是_______ 。
答案：非必需的5. 一个完全二叉树有15个度为2的节点，则该树的叶子节点数为 _______ 。
答案：16三、简答题1. 什么是二叉搜索树？请简述其特点。
答案：二叉搜索树是一种特殊的二叉树，其中每个节点的值都大于其左子树中所有节点的值，并且小于其右子树中所有节点的值。
其特点包括：- 每个节点的左子树只包含小于节点值的节点。
- 每个节点的右子树只包含大于节点值的节点。
- 左子树和右子树也必须是二叉搜索树。
数据结构试题及答案一、选择题1. 下列哪项不是线性结构的特点？A. 有且只有一个根节点B. 每个节点最多有一个前驱和一个后继C. 至少有一个节点D. 每个节点最多有一个前驱和多个后继答案：D解析：线性结构的特点包括有且只有一个根节点、每个节点最多有一个前驱和一个后继、至少有一个节点。
选项D描述的是非线性结构的特点。
2. 在单链表中，增加一个头节点的作用是（）A. 便于首元节点的插入和删除操作B. 便于首元节点的访问C. 便于链表的操作D. 便于链表的删除答案：A解析：在单链表中，增加一个头节点可以使得首元节点的插入和删除操作更加方便，避免了首元节点特殊情况的处理。
3. 下面哪一个不是栈的基本运算？A. 入栈B. 出栈C. 初始化栈D. 求栈顶元素答案：C解析：栈的基本运算包括入栈、出栈、求栈顶元素和判断栈空。
初始化栈是创建栈的过程，不属于基本运算。
二、填空题4. 在顺序表中，元素之间的逻辑关系是由_______表示的。
答案：物理位置解析：顺序表中，元素之间的逻辑关系是通过物理位置来表示的。
每个元素在内存中占据连续的存储空间。
5. 设栈S的初始状态为空。
若元素序列为ABCDEF，当元素序列的进栈和退栈操作交叉进行时，下列序列中不可能出现在栈S中的是_______。
答案：BACF解析：当元素序列的进栈和退栈操作交叉进行时，栈中可能出现的序列有很多种，但BACF不可能是栈中出现的序列，因为元素C在元素F之前进栈，但F在C之前出栈，违反了栈的后进先出原则。
三、判断题6. 线性表是一种随机存取结构，因此可以随机访问表中的任一元素。
（）答案：正确解析：线性表是一种随机存取结构，支持随机访问表中的任一元素，时间复杂度为O(1)。
7. 在双向链表中，每个节点包含两个指针，一个指向前一个节点，另一个指向下一个节点。
（）答案：正确解析：双向链表中的每个节点确实包含两个指针，一个指向前一个节点，另一个指向下一个节点，便于从任意方向遍历链表。
第一章绪论一、选择题1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。
1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像2 A.结构 B.关系 C.运算 D.算法2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。
1 A.算法 B.数据元素 C.数据操作 D.逻辑结构2 A.操作 B.映像 C.存储 D.关系3.在数据结构中，从逻辑上可以把数据结构分成。
A.动态结构和静态结构B.紧凑结构和非紧凑结构C.线性结构和非线性结构D.内部结构和外部结构4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。
A.随机存取 B.顺序存取 C.索引存取 D.散列存取5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。
1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系C.可读性和文档性D.数据复杂性和程序复杂性k6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。
1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性C.确定性、有穷性和稳定性D.易读性、稳定性和安全性7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。
A.正确 B.不正确8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。
A.必须连续的B.部分地址必须连续的C.一定是不续的D连续不连续都可以9.以下的叙述中，正确的是。
A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。
参考答案第一章、绪论一、选择题1 B；2 A； 3 B；4 C ；5 C； 6 B；7 C；8 C；9 D；10 B。
二、填空题1、存储；2、无，1，无，1；3、前驱，1，后继，任意多个；4、一对一，一对多，多对多；5、时间复杂度，空间复杂度；6、集合，线性结构，树形结构，图形结构；7、顺序结构，链式结构，索引结构，散列结构；8、顺序。
三、问答题与算法题1、3 ；2、T1 ( n ) = 5n 2 -O ( n ) ; T2 ( n ) = 3 n 2 + O ( n ) ; T3 ( n ) = 8 n 2 + O(log n) ;T4 ( n ) = 1.5 n 2 + O ( n ) 。
T4 ( n ) 较优，T3 ( n )较劣。
3、见课本。
第二章线性表一、选择题1C；2A；3D；4B；5D；6B；7C；8B；9A；10C；11D；12D；13C；14C.二、填空题1、O ( 1 ), O ( n )；2、单链表，双链表；3、地址，指针；4、4，2；5、便于访问尾结点和头结点；6、前驱；7、L->next== L且L->prior== L；8、顺序。
三、问答题与算法题1、头指针：结点或头结点的指针变量。
其作用是存放第一个结点或头结点的地址，从头指针出发可以找到链表中所有结点的信息。
头结点：是附加在链表的第一个结点之前的一个特殊结点，其数据域一般不存放信息。
其作用是为了简化运算，将空表与非空表统一起来，将第一个结点与其他结点的处理统一起来。
首结点：是链表的第一个结点。
2、(1)基于空间的考虑。
当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。
(2)基于时间的考虑。
若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。
第1 章绪论1.简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。
答案：数据：是客观事物的符号表示，指所有能输入到计算机中并被计算机程序处理的符号的总称。
如数学计算中用到的整数和实数，文本编辑所用到的字符串，多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。
数据元素：是数据的基本单位，在计算机中通常作为一个整体进行考虑和处理。
在有些情况下，数据元素也称为元素、结点、记录等。
数据元素用于完整地描述一个对象，如一个学生记录，树中棋盘的一个格局（状态）、图中的一个顶点等。
数据项：是组成数据元素的、有独立含义的、不可分割的最小单位。
例如，学生基本信息表中的学号、姓名、性别等都是数据项。
数据对象：是性质相同的数据元素的集合，是数据的一个子集。
例如：整数数据对象是集合N={0，±1，±2，… }，字母字符数据对象是集合C={‘A’，‘B’，… ，‘Z’，‘a’，‘b’，…，‘z’}，学生基本信息表也可是一个数据对象。
数据结构：是相互之间存在一种或多种特定关系的数据元素的集合。
换句话说，数据结构是带“结构”的数据元素的集合，“结构”就是指数据元素之间存在的关系。
逻辑结构：从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。
因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。
存储结构：数据对象在计算机中的存储表示，也称为物理结构。
抽象数据类型：由用户定义的，表示应用问题的数学模型，以及定义在这个模型上的一组操作的总称。
具体包括三部分：数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。
2.试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。
答案：例如有一张学生基本信息表，包括学生的学号、姓名、性别、籍贯、专业等。
每个学生基本信息记录对应一个数据元素，学生记录按顺序号排列，形成了学生基本信息记录的线性序列。
数据结构习题(有答案) 第１章绪1。
1 有下列几种二元组表示的数据结构，试画出它们分别对应的图形表示，并指出它们分别属于何种结构。
（1) A= （ D,R )，其中,D = { ａ1，ａ2,ａ３，a４}, R={ ｝(2） B= （ D,R ),其中，D = ｛ a，ｂ,c,d，ｅ｝, R＝｛ (a,ｂ),(ｂ，c），（c，d）,(d，e）｝（3) C= （ D，Ｒ），其中，D = ｛ a，b，c,d，ｅ,f，g}, R=｛（d,b)，(d,g），(1）集合(2) 线性表a b c d e(３）树fgabcde(4）图1453621 / 48·····谢阅。
（b,a),（ｂ，c),（ｇ，e），（e，f)}（4) K= （ D,R ），其中,Ｄ= ｛ 1，2，3,4，5，６}, R=｛〈1，2＞,〈2，3＞，〈2，4＞，<3，４>，<３，５>，＜3，6>,<4,5〉,〈４，6〉}1.２设n为正整数,求下列各程序段中的下划线语句的执行次数。
（1) i=1；ｋ=0ｗhiｌe(i 〈=n-1){k+=１0＊i ；i＋+;（2) fｏr （ｉnt i=１；ｉ＜=n； i+＋）ｆor （int j＝１; j〈=ｎ; ｊ+＋)｛ｃ［i］［j］=0；解:(１) n－1（2) ∑∑∑====ninjnkn111312 / 48·····谢阅。
｝ﻩ fｏr(inｔk=1； k〈=n; ｋ＋＋）c[ｉ]［j］=c[i］［j]+a[ｉ］［k]*ｂ［k］[j］｝（3) x=０；ｙ=０;for （int ｉ＝1; i＜=n; i++)fｏr (inｔ j=1; j<＝ｉ; ｊ+＋)for (inｔk=1; k〈＝ｊ; k ＋＋）(３）62)1)(nn(n21)(216)12)(1(2121212)1(1112111111++=+•+++•=+=+==∑∑∑∑∑∑∑∑========nnnnniii ijnininiijjkniijni3 / 48·····谢阅。
一、单选题（每题 2 分，共20分）1.1.对一个算法的评价,不包括如下（B ）方面的内容。
A．健壮性和可读性B．并行性C．正确性D．时空复杂度2.2。
在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行（A ）。
A。
p—>next=HL->next；HL—>next=p; B. p->next=HL；HL=p；C。
p—>next=HL；p=HL；D。
HL=p; p—〉next=HL;3.3.对线性表，在下列哪种情况下应当采用链表表示？( B ）A。
经常需要随机地存取元素 B.经常需要进行插入和删除操作C。
表中元素需要占据一片连续的存储空间 D.表中元素的个数不变4.4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是（ C ）A. 2 3 1B. 3 2 1C。
3 1 2 D。
1 2 35.5。
AOV网是一种（D )。
A．有向图B．无向图C．无向无环图D．有向无环图6.6。
采用开放定址法处理散列表的冲突时，其平均查找长度（B）.A．低于链接法处理冲突 B. 高于链接法处理冲突C．与链接法处理冲突相同D．高于二分查找7.7.若需要利用形参直接访问实参时，应将形参变量说明为（D ）参数。
A．值B．函数C．指针D．引用8.8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（A ）。
A．行号B．列号C．元素值D．非零元素个数9.9。
快速排序在最坏情况下的时间复杂度为（D )。
A．O（log2n）B．O（nlog2n）C．0（n) D．0（n2)10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C )。
A。
O（n) B。
O(1）C。
O(log2n）D。
O（n2）二、运算题（每题6 分，共24分)1.1。
数据结构是指数据及其相互之间的______________。
当结点之间存在M对N（M:N）的联系时，称这种结构为_____________________。
数据结构试题及答案一、选择题题目1：以下哪一个不是线性结构的基本特征？A. 有且只有一个根节点B. 每个节点最多有一个前件和一个后件C. 数据元素之间存在一对一的线性关系D. 数据元素可以任意插入和删除答案：D解析：线性结构的基本特征包括有且只有一个根节点，每个节点最多有一个前件和一个后件，数据元素之间存在一对一的线性关系。
数据元素任意插入和删除是线性表的特点，但不是线性结构的基本特征。
题目2：下列哪种排序算法的平均时间复杂度是 O(n log n)？A. 冒泡排序B. 选择排序C. 快速排序D. 插入排序答案：C解析：快速排序在平均情况下的时间复杂度为 O(n log n)，而冒泡排序、选择排序和插入排序的平均时间复杂度均为O(n^2)。
二、填空题题目3：在树形结构中，节点拥有的子节点的个数称为______。
答案：度解析：在树形结构中，节点拥有的子节点的个数称为“度”。
例如，一个节点有两个子节点，则其度为2。
题目4：对于具有 n 个节点的二叉树，其完全二叉树的最小深度为______。
答案：log2(n+1)解析：完全二叉树的最小深度是最后一个节点所在的层级。
对于具有 n 个节点的二叉树，其最小深度为 log2(n+1)。
三、判断题题目5：堆排序是一种不稳定的排序算法。
（对/错）答案：对解析：堆排序是一种不稳定的排序算法。
在堆排序过程中，相等的数据元素可能会改变它们在原数组中的相对位置。
题目6：在顺序存储结构中，数据的插入和删除操作的时间复杂度是 O(1)。
（对/错）答案：错解析：在顺序存储结构中，数据的插入和删除操作的时间复杂度不是 O(1)。
当插入或删除的位置不是在数组的末尾时，需要移动大量元素，其时间复杂度为 O(n)。
四、应用题题目7：给定一个长度为 n 的整数数组 arr，请编写一个算法，找出数组中的旋转点。
假设数组中不包含重复元素，并且原数组是一个升序排序的数组。
例如，数组 `[4, 5, 6, 7, 0, 1, 2]` 的旋转点是 4。
第二章线性表1、试描述头指针、头结点、开始结点的区别、并说明头指针和头结点的作用。
答：开始结点是指链表中的第一个结点，也就是没有直接前趋的那个结点。
链表的头指针是一指向链表开始结点的指针(没有头结点时)，单链表由头指针唯一确定，因此单链表可以用头指针的名字来命名。
头结点是我们人为地在链表的开始结点之前附加的一个结点。
有了头结点之后，头指针指向头结点，不论链表否为空，头指针总是非空。
而且头指针的设置使得对链表的第一个位置上的操作与在表其他位置上的操作一致(都是在某一结点之后)。
2、何时选用顺序表、何时选用链表作为线性表的存储结构为宜?答：在实际应用中，应根据具体问题的要求和性质来选择顺序表或链表作为线性表的存储结构，通常有以下几方面的考虑：1.基于空间的考虑。
当要求存储的线性表长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用顺序表；反之，当线性表长度变化大，难以估计其存储规模时，采用动态链表作为存储结构为好。
2.基于时间的考虑。
若线性表的操作主要是进行查找，很少做插入和删除操作时，采用顺序表做存储结构为宜；反之，若需要对线性表进行频繁地插入或删除等的操作时，宜采用链表做存储结构。
并且，若链表的插入和删除主要发生在表的首尾两端，则采用尾指针表示的单循环链表为宜。
4、设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。
因已知顺序表L是递增有序表，所以只要从头找起找到第一个比它大(或相等)的结点数据，把x插入到这个数所在的位置就是了。
算法如下：void InsertIncreaseList( Seqlist *L , Datatype x ){int i;for ( i=0 ; i < L -> length && L->data[ i ] < x ; i++) ; // 查找并比较,分号不能少InsertList ( L ，x , i ); // 调用顺序表插入函数}5、写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同。
先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。
void DeleteList(Nodetype *L){Nodetype *p,*q,*s;if(L->Next==NULL||L->Next==NULL){printf("删除错误\n");exit(0);}p=L->Next;q=p->Next;while(p->Next!=NULL){while(q){s=q;if(q->Data==p->Data){s->Next=q->Next;free(q);q=s->Next;}elseq=q->Next;}p=p->Next;}}第三章栈与队列1、简述栈的逻辑结构、存储结构及其相关算法答：栈的逻辑结构和线性表相同，如果它是非空的，则有且只有一个开始结点，有且只能有一个终端结点，其它的结点前后所相邻的也只能是一个结点(直接前趋和直接后继),但是栈的运算规则与线性表相比有更多的限制，栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表，通常称插入、删除这一端为栈顶，另一端称为栈底。
表中无元素时为空栈。
栈的修改是按后进先出的原则进行的，我们又称栈为LIFO表(Last In First Out)。
由于栈也是线性表，因此栈有顺序栈和链栈两种存储结构栈的基本运算有六种：构造空栈：InitStack(S)、判栈空: StackEmpty(S)、判栈满：StackFull(S)、进栈：Push(S,x)、可形象地理解为压入，这时栈中会多一个元素退栈：Pop(S) 、可形象地理解为弹出，弹出后栈中就无此元素了。
取栈顶元素：StackTop(S),不同与弹出，只是使用栈顶元素的值，该元素仍在栈顶不会改变。
2、简述队列的逻辑结构、存储结构及其相关算法。
答：队列是一种运算受限的线性表，它的运算限制与栈不同，是两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，允许删除的一端称为队尾(rear)，允许插入的一端称为队头(Front) ,队列的操作原则是先进先出的，所以队列又称作FIFO表(First In First Out)。
队列也有顺序存储和链式存储两种存储结构，前者称顺序队列，后者为链队。
队列的基本运算也有六种：置空队：InitQueue(Q)判队空：QueueEmpty(Q)判队满：QueueFull(Q)入队：EnQueue(Q,x)出队：DeQueue(Q)取队头元素：QueueFront(Q),不同与出队，队头元素仍然保留3、设计算法判断一个算术表达式的圆括号是否正确配对。
对表达式进行扫描，凡遇到“(”就进栈，遇“)”就退掉栈顶的“(”，表达式被扫描完毕，栈为空。
表示圆括号匹配。
否则圆括号不匹配。
int PairBracket( char *S){//检查表达式中括号是否配对int i;SeqStack T; //定义一个栈InitStack (&T);for (i=0; i<strlen(S) ; i++){if ( S[i]=='(' ) Push(&T, S[i]); //遇'('时进栈if ( S[i]==')' ) Pop(&T); //遇')'时出栈}return !EmptyStack(&T); // 由栈空否返回正确配对与否}第四章串1、简述下列每对术语的区别：空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。
答：空串是指不包含任何字符的串，它的长度为零。
空白串是指包含一个或多个空格的串，空格也是字符。
串常量是指在程序中只可引用但不可改变其值的串。
串变量是可以在运行中改变其值的。
主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。
静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。
动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。
目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。
有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。
2、假设有如下的串说明：char s1[30]="Stocktom,CA", s2[30]="March 5 1999", s3[30], *p;(1)在执行如下的每个语句后p的值是什么?p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6');答：stchr(*s,c)函数的功能是查找字符c在串s中的位置，若找到，则返回该位置，否则返回NULL。
因此：执行p=stchr(s1,'t');后p的值是指向字符t的位置, 也就是p==&s1[5]。
执行p=strchr(s2,'9');后p的值是指向s2串中第一个9所在的位置,也就是p==&s2[9]。
执行p=strchr(s2,'6');之后，p的返回值是NULL。
(2)在执行下列语句后，s3的值是什么?strcpy(s3,s1); strcat(s3,","); strcat(s3,s2);答：strcpy函数功能是串拷贝，strcat函数的功能是串联接。
所以：在执行strcpy(s3,s1); 后，s3的值是"Stocktom,CA"在执行strcat(s3,","); 后，s3的值变成"Stocktom,Ca,"在执行完strcat(s3,s2);后，s3的值就成了"Stocktom,Ca,March 5,1999"(3)调用函数strcmp(s1,s2)的返回值是什么?答：函数strcmp(串1，串2)的功能是串比较，按串的大小进行比较，返回大于0，等于0或小于0的值以表示串1比串2 大，串1等于串2 ，串1小于串2。
因此在调用函数strcmp(s1,s2)后，返回值是大于0的数(4)调用函数strcmp(&s1[5],"ton")的返回值是什么?答：首先，我们要知道&s1[5]是一个地址，当放在函数strcmp中时，它就表示指向以它为首地址的一个字符串，所以在strcmp( &s1[5],"ton")中，前一个字符串值是"tom,CA",用它和"ton"比较，应该是后者更大，所以返回值是小于0的数。
(5)调用函数stlen(strcat(s1,s2))的返回值是什么?答：strlen是求串长的函数，我们先将s1,s2联接起来，值是"Stocktom,CAMarch 5,1999",数一数有几个字符?是不是23个(空格也是一个)? 所以返回值是23。
