下载文档原格式
数据结构(一)一、选择题1.组成数据的基本单位是(C )。
(A)数据项(B)数据类型(C)数据元素(D)数据变最2.设数据结构A=(D, R),其中D={1, 2, 3, 4}, R={r}, r={<l, 2>, <2, 3>, <3, 4>, <4, 1>},则数据结构人是(C )o(A)线性结构(B)树型结构(C)图型结构(D)集合3、数组的逻辑结构不同于下列(D )的逻辑结构。
(A)线性表(B)栈(C)队列(D)树4、二叉树中第i (i$l)层上的结点数最多有(C )个。
(A) 2i (B) 21(C) 2i_1(D) 2i-l5、设指针变量p指向单链表结点A,则删除结点A的后继结点B需要的操作为(A )。
(A) p->next=p-〉next-〉next (B) p=p->next(C) p二p->next->next (D) p->next=p6、设栈S和队列Q的初始状态为空，元素El、E2、E3、E4、E5和E6依次通过栈S, —个元素出栈后即进入队列Q,若6个元素出列的顺序为E2、E4、E3、E6、E5和E1,则栈S的容量至少应该是(C )。
(A) 6 (B) 4 (C) 3 (D) 27、将10阶对称矩阵压缩存储到一维数组A屮，则数组A的长度最少为(C )0(A) 100 (B) 40 (C) 55 (D) 808、设结点A冇3个兄弟结点H.结点B为结点A的双亲结点，则结点B的度数数为(B )。
(A) 3 (B) 4 (0 5 (D) 19、根据二义树的定义可知二义树共有(B )种不同的形态。
(A) 4 (B) 5 (0 6 (D) 710、设有以下四种排序方法，则(B )的空间复杂度最人。
(A)冒泡排序(B)快速排序(C)堆排序(D)希尔排序11、以下说法正确的是(A )A.连通图的牛成树，是该连通图的一个极小连通子图。
数据结构试题集(包含答案-完整版)数据结构试题集（包含答案-完整版）1. 单选题1) 数据结构是一种（）。
a) 存储结构b) 算法c) 数据模型d) 网络答案：c) 数据模型解析：数据结构是一种用于组织和存储数据的方式，描述了数据之间的关系以及对数据的操作。
2) 以下哪种数据结构可以通过索引直接访问元素？a) 链表b) 队列c) 栈d) 数组答案：d) 数组解析：数组是一种线性数据结构，可以通过索引直接访问指定位置的元素。
2. 多选题1) 哪些数据结构属于非线性结构？（）a) 队列b) 树c) 栈d) 图答案：b) 树d) 图解析：线性结构中的元素存在一对一的关系，非线性结构中的元素存在一对多或多对多的关系，树和图属于非线性结构。
2) 下列哪些操作可以在栈上进行？（）a) 入栈b) 出栈c) 查找d) 删除答案：a) 入栈b) 出栈解析：栈是一种后进先出（LIFO）的数据结构，只能在栈顶进行插入和删除操作。
3. 简答题1) 请简要介绍线性表和非线性表。
答案：线性表是数据元素的一个有限序列，元素之间存在一对一的关系。
非线性表是指元素之间存在一对多或多对多的关系，如树和图。
2) 请解释什么是时间复杂度和空间复杂度。
答案：时间复杂度是衡量算法执行效率的度量，表示算法的运行时间随输入规模增长的速度。
空间复杂度是指算法执行过程中所需的存储空间随输入规模增长的速度。
4. 编程题题目：实现一个栈，包含push、pop和getMin三个操作，要求时间复杂度为O(1)。
答案：class MinStack:def __init__(self):self.stack = []self.min_stack = []def push(self, x):self.stack.append(x)if not self.min_stack or x <= self.min_stack[-1]:self.min_stack.append(x)def pop(self):if self.stack.pop() == self.min_stack[-1]:self.min_stack.pop()def getMin(self):return self.min_stack[-1]解析：在栈的基础上，使用一个辅助栈min_stack来记录当前栈中的最小值。
《数据结构》期末考试试卷试题及答案第一部分：选择题（每题2分，共20分）1. 下面哪个数据结构是线性结构？A. 树B. 图C. 队列D. 网络流2. 下面哪个数据结构用于实现广度优先搜索算法？A. 栈B. 队列C. 散列表D. 堆3. 下面哪个数据结构用于实现深度优先搜索算法？A. 栈B. 队列C. 散列表D. 堆4. 下面哪个数据结构用于实现快速排序算法？A. 栈B. 队列C. 散列表D. 堆5. 下面哪个数据结构用于实现优先队列？A. 栈B. 队列C. 散列表D. 堆6. 下面哪个数据结构用于实现哈希表？A. 栈B. 队列C. 散列表D. 堆7. 下面哪个数据结构用于实现最小树算法？A. 栈B. 队列C. 散列表D. 堆8. 下面哪个数据结构用于实现拓扑排序算法？A. 栈B. 队列C. 散列表D. 堆9. 下面哪个数据结构用于实现最短路径算法？A. 栈B. 队列C. 散列表D. 堆10. 下面哪个数据结构用于实现并查集算法？A. 栈B. 队列C. 散列表D. 堆第二部分：填空题（每题2分，共20分）1. 链表是一种______数据结构。
2. 二叉树的节点最多有______个子节点。
3. 堆是一种特殊的______。
4. 散列表的查找效率取决于______。
5. 图的遍历算法包括______和______。
6. 快速排序算法的平均时间复杂度为______。
7. 哈希表中的冲突解决方法有______和______。
8. 最小树算法包括______和______。
9. 最短路径算法包括______和______。
10. 并查集算法用于解决______问题。
第三部分：简答题（每题10分，共50分）1. 请简述栈和队列的区别。
2. 请简述二叉搜索树的特点。
3. 请简述哈希表的原理。
4. 请简述图的深度优先搜索算法。
5. 请简述最小树算法的原理。
第四部分：编程题（每题20分，共50分）1. 编写一个函数，实现链表的插入操作。
数据结构练习题习题1 绪论单项选择题1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。
①A．操作对象Ｂ．计算方法Ｃ．逻辑结构Ｄ．数据映象②A．存储结构Ｂ．关系Ｃ．运算Ｄ．算法2. 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是①的有限集合，R是D上的②有限集合。
①A．算法Ｂ．数据元素Ｃ．数据操作Ｄ．数据对象②A．操作Ｂ．映象Ｃ．存储Ｄ．关系3. 在数据结构中，从逻辑上可以把数据结构分成。
）A．动态结构和静态结构Ｂ．紧凑结构和非紧凑结构Ｃ．线性结构和非线性结构Ｄ．内部结构和外部结构4. 算法分析的目的是①，算法分析的两个主要方面是②。
① A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系C. 分析算法的效率以求改进D. 分析算法的易懂性和文档性② A. 空间复杂性和时间复杂性 B. 正确性和简明性C. 可读性和文档性D. 数据复杂性和程序复杂性5. 计算机算法指的是①，它必具备输入、输出和②等五个特性。
① A. 计算方法 B. 排序方法C. 解决问题的有限运算序列D. 调度方法!② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性填空题（将正确的答案填在相应的空中）1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。
2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。
3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。
4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。
5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。
《数据结构》题库及答案一、选择题1．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。
a. 随机存储；b.顺序存储；c. 索引存取；d. HASH 存取2．一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是 。
a. edcba;b. decba;c. dceab;d.abcde3．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。
a. 4,3,2,1;b. 1,2,3,4;c. 1,4,3,2;d.3,2,4,14．在一个单链表中，已知p 结点是q 结点的直接前驱结点，若在p 和q 之间插入结点s ，则执行的操作是 。
a. s->nxet=p->next; p->next=s;b. p->next=s->next; s->next=p;c. q->next=s; s->next=p;d. p->next=s; s->next=q;5．设有两个串p,q ，求q 在p 中首次出现的位置的运算称作 。
a.联接b.模式匹配c.求子串d.求串长6．二维数组M 的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10，则存放M 至少需要 个字节。
a. 90b.180c.240d.540 7．在线索二叉树中，结点p 没有左子树的充要条件是 。
a. p->lch==NULLb. p->ltag==1c. p->ltag==1且p->lch=NULLd. 以上都不对8．在栈操作中，输入序列为（A ，B ，C ，D ），不可能得到的输出序列为：______A 、（A ，B ，C ，D ） B 、（D ，C ，B ，A ） C 、（A ，C ，D ，B ） D 、（C ，A ，B ，D ）9．已知某二叉树的后序序列是dabec ，中序序列是debac ，则它的先序序列是 。
一、单项选择题1.逻辑关系是指数据元素间的（）A．类型 B．存储方式 C．结构 D．数据项2.对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( )A．顺序表 B.用头指针表示的单循环链表C. 用尾指针表示的单循环链表D. 单链表3.设数组data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作后其头指针front值为（）A．front=front+1 B．front= (front+1)%(m-1)C．front=(front-1)%m D．front=(fro nt+1)%m4.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为( )。
A．rear％n==front B．(front+l)％n==rearC．rear％n-1==front D．(rear+l)％n==front5.在具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队空的条件为( )。
A．rear％n==front B．front+l=rearC．rear==front D．(rear+l)％n=front6.已知一颗二叉树上有92个叶子结点，则它有____个度为2的结点。
( )A. 90B. 91C. 92D. 937.在一棵非空二叉树的中序遍历序列中，根结点的右边_____。
A. 只有右子树上的所有结点B. 只有右子树上的部分结点C. 只有左子树上的所有结点D. 只有左子树上的部分结点8.有n条边的无向图的邻接表存储法中，链表中结点的个数是( )个。
A. nB. 2nC. n/2D. n*n9.判断有向图是否存在回路，除了可利用拓扑排序方法外，还可以利用（）。
A. 求关键路径的方法B.求最短路径的方法C. 深度优先遍历算法D.广度优先遍历算法10.对线性表进行二分查找时，要求线性表必须( )。
数据结构试题及答案⼀、选择题（共10题，每题1分，共10分）1．下⾯关于线性表的叙述中，错误的是哪⼀个？（）A．线性表采⽤顺序存储，必须占⽤⼀⽚连续的存储单元B．线性表采⽤顺序存储，便于进⾏插⼊和删除操作C．线性表采⽤链接存储，不必占⽤⼀⽚连续的存储单元D．线性表采⽤链接存储，便于插⼊和删除操作2．在⼀个单链表中，已知q所指结点是p所指结点的前驱，若在p和q之间插⼊s所指结点，则执⾏的操作是（）。
A. s->next=p->next;p->next=s;B. q->next=s;s->next=p;C. p->next=s->next;s->next=p;D. p->next=s;s->next=q;3．设有三个元素X，Y，Z顺序进栈，下列得不到的出栈排列是( )。
A．XYZ B. YZX C. ZXY D. ZYX4．若⽤⼀个长度为6的数组来实现循环队列，且当前rear和front的值分别为0和3，则从队列中删除⼀个元素，再增加两个元素后，rear和front的值分别是( )。
A．1和5 B．2和4 C．4和2 D. 5和15．下列说法中正确的是（）。
A．⼆叉树就是度为2的树 B．⼆叉树中不存在度⼤于2的结点C．⼆叉树中⾄少有⼀个结点的度为2 D．⼆叉树中任何⼀个结点的度都为2 6．在具有n个结点的⼆叉链表中，共有（）个空指针。
A. nB. n-1C. n+1D. 不确定7．根据⼆叉树与树的转换关系可知，深度为h的满⼆叉树对应的森林由（）棵树构成。
A．1 B．log2n C. h/2 D. h8．在⼀个⽆向图中，所有顶点的度数之和等于所有边数的（）倍。
A．1/2 B．1 C. 2 D. 49．对17个元素的查找表做折半查找，则查找长度为5的元素下标依次是（）。
A．8,17 Ｂ．5,10,12 C．9,16 D．9,1710．关于排序，下列说法中正确的是（）。
数据结构试卷试题及答案一、选择题（每题5分，共40分）1. 数据结构是研究数据元素的（）A. 存储结构B. 处理方法C. 逻辑结构D. 所有以上内容答案：D2. 在数据结构中，通常采用（）方式来表示数据元素之间的逻辑关系。
A. 顺序存储结构B. 链式存储结构C. 索引存储结构D. 散列存储结构答案：B3. 下面哪一个不是栈的基本操作？（）A. 入栈B. 出栈C. 判断栈空D. 获取栈顶元素答案：D4. 下面哪一个不是队列的基本操作？（）A. 入队B. 出队C. 判断队列空D. 获取队头元素答案：D5. 下面哪一个不是线性表的特点？（）A. 有且只有一个根节点B. 每个节点最多有一个前驱和一个后继C. 数据元素类型相同D. 数据元素类型可以不同答案：D6. 在下列哪种情况中，使用链式存储结构比顺序存储结构更合适？（）A. 数据元素经常插入和删除B. 数据元素大小不固定C. 数据元素个数不确定D. 所有以上情况答案：D7. 下面哪一个不是树的遍历方式？（）A. 前序遍历B. 中序遍历C. 后序遍历D. 翻转遍历答案：D8. 在下列哪种情况中，使用散列存储结构比其他存储结构更合适？（）A. 数据元素个数较少B. 数据元素查找频繁C. 数据元素插入和删除频繁D. 数据元素大小不固定答案：B二、填空题（每题5分，共30分）9. 栈是一种特殊的线性表，它的插入和删除操作都限定在表的一端进行，这一端称为______。
答案：栈顶10. 队列是一种特殊的线性表，它的插入操作在表的一端进行，这一端称为______，而删除操作在另一端进行，这一端称为______。
答案：队尾、队头11. 二叉树中的节点包括______和______。
答案：根节点、子节点12. 在图的存储结构中，邻接矩阵表示法用______个一维数组来表示图中各个顶点之间的关系。
答案：两个13. 散列存储结构中，关键码到存储地址的映射方法称为______。
《数据结构》期末考试试题及答案一、选择题（每题2分，共20分）1. 下列哪种数据结构是线性结构？A. 栈B. 树C. 队列D. 图答案：A2. 在计算机科学中，什么是最基本的数据结构？A. 数组B. 链表C. 栈D. 树答案：C3. 下列哪种操作的时间复杂度是O(1)?A. 在链表中插入元素B. 在数组中查找元素C. 在树中删除节点D. 在图中寻找最短路径答案：B4. 下列哪种数据结构常常用于实现栈和队列？A. 数组B. 链表C. 树D. 图答案：A5. 下列哪种数据结构是有序的？A. 栈B. 队列C. 链表D. 图答案：C二、填空题（每题2分，共20分）1. 在数据结构中，栈是一种后进先出（____）的数据结构。
答案：线性表2. 队列是一种先进先出（____）的数据结构。
答案：线性表3. 链表是一种____数据结构，由一系列节点组成。
答案：非线性4. 二叉树是一种特殊的树，它的每个节点最多有两个____。
答案：子节点5. 哈希表是通过____函数将关键字映射到表中的位置来访问数据。
答案：哈希三、判断题（每题2分，共20分）1. 树是一种线性结构。
（）答案：错误2. 链表的插入和删除操作时间复杂度都是O(1)。
（）答案：错误3. 图是一种线性结构。
（）答案：错误4. 哈希表是一种基于顺序结构的的数据结构。
（）答案：错误5. 在数据结构中，时间复杂度O(n)表示算法随着输入规模的增加而线性增长。
（）答案：正确四、简答题（每题10分，共30分）1. 请简述栈和队列的特点和应用场景。
答案：栈是一种后进先出（LIFO）的数据结构，应用场景包括函数调用栈、表达式求值等。
队列是一种先进先出（FIFO）的数据结构，应用场景包括任务队列、缓冲区等。
2. 请简述链表的优缺点。
答案：链表的优点包括动态扩容、插入和删除操作时间复杂度为O(1)、可以方便地实现各种复杂数据结构。
缺点包括占用内存空间较大、不如数组支持随机访问。
数据结构考试题及答案一、选择题1. 下列哪种数据结构是一种线性结构？A. 树B. 栈C. 图D. 队列答案：B. 栈2. 以下哪种不是二叉树的遍历方式？A. 先序遍历B. 层序遍历C. 后序遍历D. 中序遍历答案：B. 层序遍历3. 在队列中，哪种操作不是O(1)时间复杂度的？A. 入队B. 出队C. 判空D. 获取队首元素答案：D. 获取队首元素二、填空题4. 二叉查找树的中序遍历结果为_______。
答案：升序排列的序列5. 栈的特点是_______进，_______出。
答案：后进，先出6. 图中两点间存在边则称它们为_______。
答案：邻接点三、简答题7. 请简要介绍一下栈和队列的应用场景及区别。
答：栈和队列都是常用的数据结构，栈适合用于实现括号匹配、表达式求值等场景，而队列常用于实现广度优先搜索、缓存队列等。
栈是一种后进先出的数据结构，而队列是一种先进先出的数据结构。
8. 什么是哈希表？它的优缺点分别是什么？答：哈希表是一种通过哈希函数将关键字映射到数组位置的数据结构。
其优点是能够快速查找、插入、删除元素，时间复杂度接近O(1)；缺点是可能发生哈希冲突，导致性能下降。
四、综合题9. 给定以下无向图的邻接矩阵表示，请写出图的深度优先搜索（DFS）遍历路径。
```0 1 2 30 0 1 0 11 1 0 1 12 0 1 0 13 1 1 1 0```答：起始节点为0，路径：0 - 1 - 3 - 210. 写出以下树的层序遍历结果。
```1/ \2 3/ \ / \4 5 6 7```答：1 - 2 - 3 - 4 - 5 - 6 - 7以上就是数据结构考试题及答案，希望对您有所帮助。
如果有不清楚的地方，欢迎随时向老师询问。
祝您考试顺利！。
第一章绪论一．选择题1．数据结构被形式地定义为（K，R），其中K是①的有限集合，R是K上的②的有限集合。
①A．算法B．数据元素C．数据操作D．逻辑结构②A．操作B．映象C．存储D．关系2．算法分析的目的是①，算法分析的两个主要方面是②。
①A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进D．分析算法的易懂性和文档性②A．空间复杂性和时间复杂性B．正确性和简明性C．可读性和文档性D．数据复杂性和程序复杂性3．在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为A．逻辑结构B．顺序存储结构C．链表存储结构D．以上都不对4．数据结构中，在逻辑上可以把数据结构分成：( ）。
A．动态结构和静态结构B．紧凑结构和非紧凑结构C．线性结构和非线性结构D．内部结构和外部结构5．以下属于顺序存储结构优点的是（）。
A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示6．数据结构研究的内容是（）。
A．数据的逻辑结构B．数据的存储结构C．建立在相应逻辑结构和存储结构上的算法D．包括以上三个方面7．链式存储的存储结构所占存储空间（）。
A．分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针B．只有一部分，存放结点值C．只有一部分，存储表示结点间关系的指针D．分两部分，一部分存放结点值，另一部分存放结点所占单元数8．计算机算法指的是（1），它具备输入，输出和（2）等五个特性。
（1）A. 计算方法 B.排序方法C. 解决问题的有限运算序列D.调度方法（2）A.可行性，可移植性和可扩充性 B.可行性，确定性和有穷性C.确定性，有穷性和稳定性D.易读性，稳定性和安全性9．以下关于数据的逻辑结构的叙述中正确的是（）。
A．数据的逻辑结构是数据间关系的描述B．数据的逻辑结构反映了数据在计算机中的存储方式C．数据的逻辑结构分为顺序结构和链式结构D．数据的逻辑结构分为静态结构和动态结构10．算法分析的主要任务是（）。
A．探讨算法的正确性和可读性B．探讨数据组织方式的合理性C．为给定问题寻找一种性能良好的解决方案D．研究数据之间的逻辑关系11计算机内部数据处理的基本单位是（）。
A.数据B.数据元素C.数据项D.数据库二、填空题1.下面程序段的时间复杂度是____________。
for (I=1; I<n; I++)for (j=1; j<n; j++) x++;for (k=1; k<n;k++) x++;2．下面程序段的时间复杂度是____________。
s＝0；for（i=0；i<n；i++）for（j=0; j<n; j++）s+=b[i][j]；sum=s;3. 数据结构按逻辑结构可分为两大类，分别是________和______。
4. 一个算法的效率可分为____________效率和__________效率。
5. 设n 为正整数。
下列程序段中前置以记号@的语句的频度为________。
i=1;k=0;while(i<=n-1){@ k+=10*i;i++; }6算法时间复杂度的分析通常有两种方法，即___________和___________的方法，通常我们对算法求时间复杂度时，采用后一种方法。
第二次作业1. 对以下单链表分别执行下列各程序段，画出结果示意图。
(1) Q=P->next;(2) S=P->next->next;(3) R->data=P->data;(4) R->data=P->next->data;(5) T=P;while(T!=NULL){ T->data=T->data*2;T=T->next;}2. 简述以下算法的功能。
Status A(LinkList L) { //L 是无表头结点的单链表if(L&&L->next){Q=L; L=L->next; P=L;while(P->next) P=P->next;P->next=Q; Q->next=NULL;}PR …return OK;}//A3.写一算法在带头结点的单链表结构上实现线性表操作LOCA TE(L,x)。
（求x在单链表L中的位序）4.写一算法在带头结点的单链表结构上实现线性表操作LENGTH(L)。
（求单链表L中的元素个数）5.选择题（1）．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A．head==NULL B．head→next==NULL C．head→next==head D．head!=NULL （2）．完成在双循环链表结点p之后插入s的操作是（）A．p->next=s ; s->prior=p; p->next->prior:=s ; s->next=p->next;B．p->next->prior=s; p->next=s; s->prior=p; s->next:=p->next;C．s->prior=p; s->next:=p->next; p->next=s; p->next->prior=s ;D．s->prior=p; s->next:=p->next; p->next->prior=s ; p->next=s;（3）．线性表是具有n个（）的有限序列。
A．表元素B．字符C．数据元素D．数据项（4）．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。
B．线性表采用顺序存储，便于进行插入和删除操作。
C．线性表采用链接存储，不必占用一片连续的存储单元。
D．线性表采用链接存储，便于插入和删除操作。
（5）．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。
A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表（6）．线性表是________。
A．一个有限序列，可以为空B．一个有限序列，不可以为空C．一个无限序列，可以为空D．一个无限序列，不可以为空（7）．链表不具有的特点是（）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比（8）.在______运算中，使用顺序表比链表好。
A．插入B．删除C．根据序号查找D．根据元素值查找（9）.在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，A．s->next=p->next; p->next=sB．q->next=s; s->next=pC．p->next=s->next; s->next=pD．p->next=s; s->next=q（10）. 在顺序表中，只要知道_______，就可在相同时间内求出任一结点的存储地址。
A．基地址B．结点大小C．向量大小D．基地址和结点大小（11）.以下关于线性表的说法不正确的是______。
A．线性表中的数据元素可以是数字、字符、记录等不同类型。
B．线性表中包含的数据元素个数是任意的。
C．线性表中的每个结点都有且只有一个直接前趋和直接后继。
D．存在这样的线性表：表中各结点都没有直接前趋和直接后继。
（12）.从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较________个元素结点。
A．n/2 B．n C．（n+1）/2 D．（n-1）/2第三次作业一写出下列程序段的输出结果:void main(){Stack S;char x,y;InitStack(S);x=‘c’;y=‘k’;Push(S,x);Push(S,’a’); Push(S,y);Pop(S,x);Push(S,’t’);Push(S,x);Pop(S,x); Push(S,’s’);While(!StackEmpty(S)) {Pop(S,y);printf(y)};printf(x);}二写出下列程序段的输出结果:void main(){Queue Q; InitQueue(Q);char x=‘e’,y=‘c’;EnQueue(Q,’h’); EnQueue(Q,’r’); EnQueue(Q,y);DeQueue(Q,x); EnQueue(Q,x);DeQueue(Q,x); EnQueue(Q,’a’);While(!QueueEmpty(Q){DeQueue(Q,y); printf(y);}}三、假设称正读和反读都相同的字符序列为“回文”，例如，“abba”和“abcba”是回文，“ abcde” ，“ababab”则不是回文。
试写一个算法判别读入的一个以‘@’为结束符的字符序列是否是“回文”。
四、选择题一、单选题1. 对于栈操作数据的原则是（）。
A. 先进先出B. 后进先出C. 后进后出D. 不分顺序2.在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（）A．top不变B．top=0 C．top-- D．top++3. 若一个栈的输入序列为1,2,3,…,n，输出序列的第一个元素是i，则第j个输出元素是（）。
A. i-j-1B. i-jC. j-i+1D. 不确定的4. 某堆栈的输入序列为a, b，c ，d,下面的四个序列中，不可能是它的输出序列的是（）。
A. a，c，b，dB. b, c，d，aC. c, d，b, aD. d, c，a，b6. 用链接方式存储的队列，在进行删除运算时（）。
A. 仅修改头指针B. 仅修改尾指针C. 头、尾指针都要修改D. 头、尾指针可能都要修改7. 假设以数组A[m]存放循环队列的元素,其头尾指针分别为front和rear，则当前队列中的元素个数为（）。
A．(rear-front+m)%m B．rear-front+1 C．(front-rear+m)%m D．(rear-front)%m8. 栈和队列的共同点是（）。
A. 都是先进先出B. 都是先进后出C. 只允许在两端插入和删除元素D. 没有共同点9. 设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4,e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3,e6,e5,e1则栈S的容量至少应该是( )。
A．6 B. 4 C. 3 D. 210. 若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？( )A. 1和5B. 2和4C. 4和2D. 5和111. 在作进栈运算时,应先判别栈是否( ①),在作出栈运算时应先判别栈是否(②)。
