下载文档原格式
数据结构考试题及答案一、选择题（每题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. 单选题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来记录当前栈中的最小值。
数据结构考试试题题库一、选择题1. 在数据结构中，线性表是按照什么顺序存储数据的？A. 随机B. 无序C. 有序D. 连续2. 栈（Stack）是一种遵循哪种原则的数据结构？A. 先进先出（FIFO）B. 先进后出（LIFO）C. 后进先出（LILO）D. 随机访问3. 哈希表（Hash Table）的主要优点是什么？A. 存储空间大B. 访问速度快C. 易于排序D. 易于扩展二、简答题1. 请简述数组和链表的区别。
2. 什么是二叉树？请描述二叉树的几种遍历方法。
三、计算题1. 给定一个单链表，编写一个算法来删除链表中的重复元素。
2. 假设有一个数组，其中包含n个元素，编写一个算法来找到数组中的第k小的元素。
四、应用题1. 描述如何使用队列来实现一个打印任务调度系统。
2. 请解释二叉搜索树（BST）的插入操作，并给出相应的算法实现。
五、编程题1. 编写一个C++函数，实现对一个给定的整数数组进行排序。
2. 编写一个Python函数，实现对一个二叉树进行层次遍历。
六、论述题1. 讨论图的两种存储结构：邻接矩阵和邻接表，并比较它们的优缺点。
2. 解释什么是递归，并给出一个使用递归解决实际问题的例子。
结束语数据结构的学习不仅仅是对概念的理解，更重要的是能够将这些概念应用到实际问题的解决中。
通过本题库的练习，希望能够加深你对数据结构的理解和应用能力。
请注意，这只是一个示例题库，实际的考试题库可能会包含更多的题目和不同的题型。
考生应根据具体的课程内容和考试要求来准备。
数据结构考试试题一、选择题（每题2分，共20分）1. 在数据结构中，队列是一种______。
A. 线性结构B. 非线性结构C. 树形结构D. 图结构2. 对于长度为n的线性表，在顺序存储结构中，从第i个元素（1≤i≤n）开始，连续做m（1≤m≤n-i+1）个元素的删除操作，需要进行的移动元素次数为______。
A. mB. n-mC. i+m-1D. m+n-m-13. 在二叉树的遍历中，先序遍历的顺序是______。
A. 根左右B. 左右根C. 左根右D. 左右根4. 哈希表的冲突可以通过多种方式解决，其中不是解决冲突的方法是______。
A. 开放寻址法B. 链地址法C. 建立一个公共溢出区D. 二分查找法5. 排序算法中，时间复杂度为O(nlogn)的算法是______。
A. 选择排序B. 冒泡排序C. 快速排序D. 插入排序6. 在图的遍历中，深度优先搜索（DFS）使用的是______。
A. 栈B. 队列C. 哈希表D. 数组7. 堆排序算法中，将堆中的最后一个元素和第一个元素交换，然后重新调整堆的过程称为______。
A. 堆调整B. 堆缩小C. 堆替换D. 堆重建8. 一个长度为n的链表，删除已知第k个元素的时间复杂度是______。
A. O(1)B. O(n)C. O(k)D. O(nk)9. 字符串“Knuth”在一棵二叉查找树中，按照K->n->u->t->h的顺序插入后，使用中序遍历得到的结果是______。
A. hKnuctB. hnKutC. hKnutD. hnuct10. 对于长度为n的数组，如果使用归并排序算法进行排序，其时间复杂度为______。
A. O(n)B. O(n^2)C. O(nlogn)D. O(logn)二、简答题（每题5分，共30分）11. 请简述什么是时间复杂度，并给出最好、最坏和平均时间复杂度的定义。
12. 解释一下什么是平衡二叉树，并说明它在数据结构中的重要性。
一、算法设计题（每题15分，共60分）答题要求：①用自然语言说明所采用算法的思想；②给出每个算法所需的数据结构定义，并做必要说明；③写出对应的算法程序，并做必要的注释。
1、有一个带头结点的单链表，每个结点包括两个域，一个是整型域info，另一个是指向下一个结点的指针域next。
假设单链表已建立，设计算法删除单链表中所有重复出现的结点，使得info域相等的结点只保留一个。
3、约瑟夫环问题（Josephus问题）是指编号为1、2、…，n的n（n>0）个人按顺时针方向围坐成一圈，现从第s个人开始按顺时针方向报数，数到第m个人出列，然后从出列的下一个人重新开始报数，数到第m的人又出列，…，如此重复直到所有的人全部出列为止。
现要求采用循环链表结构设计一个算法，模拟此过程。
4、编程实现单链表的就地逆置。
23．在数组 A[1..n]中有n个数据，试建立一个带有头结点的循环链表，头指针为h，要求链中数据从小到大排列，重复的数据在链中只保存一个.5、设计一个尽可能的高效算法输出单链表的倒数第K个元素。
3、假设以I和O分别表示入栈和出栈操作。
栈的初态和终态均为空，入栈和出栈的操作序列可表示为仅由I和O组成的序列，称可以操作的序列为合法序列，否则称为非法序列。
（15分）（1）下面所示的序列中哪些是合法的？A. IOIIOIOOB. IOOIOIIOC. IIIOIOIOD. IIIOOIOO（2）通过对（1）的分析，写出一个算法，判定所给的操作序列是否合法。
若合法，返回true，否则返回false（假定被判定的操作序列已存入一维数组中）。
5、设从键盘输入一整数的序列：a1, a2, a3，…，an,试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai进栈；当ai=-1时，输出栈顶整数并出栈。
算法应对异常情况（入栈满等）给出相应的信息。
设有一个背包可以放入的物品重量为S，现有n件物品，重量分别为W1，W2，...，W n。
第一章概论一、填空题1. 数据结构是一门研究非数值计算的程序设计问题中计算机的 操作对象 以及它们之间的 关系 和运算等的学科。
2. 数据结构被形式地定义为（D, R ），其中D 是 数据元素 的有限集合，R 是D 上的 关系 有限集合。
3. 数据结构包括数据的 逻辑结构 、数据的 存储结构 和数据的 运算 这三个方面的内容。
4. 数据结构按逻辑结构可分为两大类，它们分别是 线性结构 和 非线性结构 。
5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。
6． 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 没有后续结点，其余每个结点有且只有1个后续结点。
7. 在树形结构中，树根结点没有 前驱 结点，其余每个结点有且只有 1 个前驱结点；叶子结点没有 后续 结点，其余每个结点的后续结点数可以任意多个 。
8. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个 。
9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序 、 链式 、 索引 和 散列 。
10. 数据的运算最常用的有5种，它们分别是插入 、 删除、修改、 查找 、排序。
11. 一个算法的效率可分为 时间 效率和 空间 效率。
二、单项选择题（ B ）1. 非线性结构是数据元素之间存在一种：A ）一对多关系B ）多对多关系C ）多对一关系D ）一对一关系（ C ）2. 数据结构中，与所使用的计算机无关的是数据的 结构；A) 存储 B) 物理 C) 逻辑 D) 物理和存储（ C ）3. 算法分析的目的是：A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性（ A ）4. 算法分析的两个主要方面是：A) 空间复杂性和时间复杂性 B) 正确性和简明性C) 可读性和文档性 D) 数据复杂性和程序复杂性（ C ）5. 计算机算法指的是：A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法（ B ）6. 计算机算法必须具备输入、输出和 等5个特性。
数据结构考试题⽬数据结构49道题1. 数据结构是⼀门研究什么内容的学科？2. 数据元素之间的关系在计算机中有⼏种表⽰⽅法？各有什么特点？3. 数据类型和抽象数据类型是如何定义的。
⼆者有何相同和不同之处，抽象数据类型的主要特点是什么？使⽤抽象数据类型的主要好处是什么？5．评价⼀个好的算法，您是从哪⼏⽅⾯来考虑的？8．对于⼀个数据结构，⼀般包括哪三个⽅⾯的讨论？9. 当你为解决某⼀问题⽽选择数据结构时，应从哪些⽅⾯考虑？11．数据结构与数据类型有什么区别？15. 在编制管理通讯录的程序时, 什么样的数据结构合适? 为什么?18．设计⼀数据结构，⽤来表⽰某⼀银⾏储户的基本信息：账号、姓名、开户年⽉⽇、储蓄类型、存⼊累加数、利息、帐⾯总数。
19. 请在下列算法的横线上填⼊适当的语句。
FUNCTION inclusion(ha,hb:linklisttp):boolean;{以ha 和hb 为头指针的单链表分别表⽰有序表A 和B，本算法判别表A 是否包含在表B 内，若是，则返回“true”，否则返回“false”}BEGINpa:=ha^.next; pb:=hb^.next; （1） ;WHILE（2） DOIF pa^.data=pb^.data THEN（3） ELSE（4） ;（5）END;20．完善算法：已知单链表结点类型为：TYPE ptr=^node；node=RECORDdata：integer； next：ptrEND；过程create 建⽴以head 为头指针的单链表。
PROCEDURE create ( (1) )；VAR p,q：ptr； k：integer；BEGINnew（head）； q:=head；read（k）；WHILE k>0 DOBEGIN(2); (3); (4); (5);read（k）END;q^.next：=NIL;END;22．假设链表p 和链表q 中的结点值都是整数,且按结点值的递增次序链接起来的带表头结点的环形链表。
数据结构试题6一、单项选择题（每小题3分，共30分）1．设栈的输入序列是1、2、3、4，则______不可能是其出栈序列。
( )[A] 1234 [B] 2134 [C] 1432 [D] 43122．在一个具有n个结点的线性链表中查找某个结点，若查找成功，需要平均比较_____个结点。
( )[A] n [B] n/2 [C] (n+1)/2 [D] (n-1)/23．设每个字符占一个字节，二维数组A中每个元素有6个字符组成，其行下标从0到9，列下标从0到3，元素_____当A按行优先存储起始地址与当A按列优先存储的起始地址相同。
( )[A] A[3][0] [B] A[3][1] [C] A[3][2] [D] A[2][3]4．具有2000个结点的非空二叉树的最小深度为_______。
( )[A] 9 [B] 10 [C] 11 [D] 125．已知某二叉树的后根序列是dabec，中根序列是debac，则先根序列是_____。
( )[A] acbed [B] decab [C] deabc [D] cedba6. 无向图中所有边的数目等于所有顶点的度数之和的_____倍。
( )[A] 1 [B] 2 [C] 1/2 [D] 不一定7．递归函数F(n)=F(n-1)+n+1(n>1)的递归体是_______。
( )[A] F(0)=0 [B] F(1)=1 [C] F(n)=n+1 [D] F(n)=F(n-1)+n+18. 若需要在O(nlog2n)的时间内完成对n个元素的排序，且要求排序是稳定的,则可选择的排序方法是_______。
( )[A] 快速排序[B] 堆排序[C] 归并排序[D] 直接插入排序9．在对n个元素的序列进行排序时,堆排序所需要的附加存储空间是__。
( )[A] O(1) [B] O(log2n) [C] O(n) [D] O(n log2n)10．假定有K个关键字互为同义词，若用线性探查法把这K个关键字存入散列表中，则总的探查次数至少为______。
数据结构考试试题题库一、选择题1. 在数据结构中，栈（Stack）是一种特殊的线性表，其特点是：A. 允许在表的任意位置插入和删除元素B. 只能在表的一端进行插入和删除操作C. 只能在表的两端进行插入和删除操作D. 只能在表的中间进行插入和删除操作答案：B2. 假设有一个单链表，头结点的指针域为head，链表中每个结点包含一个数据域data和指向下一个结点的指针域next。
若要删除指针p所指向的结点，以下哪个操作是正确的？A. p = p->nextB. p->next = p->next->nextC. p = p->next->nextD. p = NULL答案：B3. 在二叉树的遍历算法中，先序遍历的顺序是：A. 先访问根节点，然后遍历左子树，最后遍历右子树B. 先遍历左子树，然后访问根节点，最后遍历右子树C. 先遍历右子树，然后访问根节点，最后遍历左子树D. 同时遍历左子树和右子树答案：A4. 哈希表的冲突可以通过多种方式解决，以下哪种不是解决哈希表冲突的方法？A. 链地址法B. 开放地址法C. 再哈希法D. 排序法答案：D5. 快速排序算法的时间复杂度在最好、最坏和平均情况下分别是：A. O(n log n), O(n^2), O(n)B. O(n), O(n log n), O(n^2)C. O(n log n), O(n), O(n log n)D. O(n^2), O(n log n), O(n)答案：A二、简答题1. 请简述什么是图，并说明图的两种基本表示方法。
答案：图是一种数据结构，由顶点（或称为节点）和边组成。
图可以表示为有向图或无向图。
图的两种基本表示方法为邻接矩阵和邻接表。
邻接矩阵是一个二维数组，其元素表示顶点之间的连接关系；邻接表则使用链表存储每个顶点的邻接点。
2. 什么是二叉搜索树（BST）？请简述其特点。
答案：二叉搜索树是一种特殊的二叉树，其中每个节点的值都大于或等于其左子树中所有节点的值，并且小于或等于其右子树中所有节点的值。
数据结构考试题及答案一、选择题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.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。
A. 13B. 33C. 32D. 402. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。
A. BA+141B. BA+180C. BA+222D. BA+2253. 假设以行序为主序存储二维数组A=array[1..100，1..100]，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]=（）。
A. 808B. 818C. 1010D. 10204. 数组A[0..5,0..6]的每个元素占五个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。
A. 1175B. 1180C. 1205D. 12107.设二维数组A[1.. m，1.. n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。
A.（i-1）*n+jB.（i-1）*n+j-1C. i*（j-1）D. j*m+i-18. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。
A. 60B. 66C. 18000D. 339. 用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j 沿链移动的操作为( )。
A. j=r[j].nextB. j=j+1C. j=j->nextD. j=r[j]-> next填空：4. 广义表A= ((( a，b)，(c，d，e)))，取出A中的原子e的操作是: _______。
5. 广义表A((( ),(a,(b),c)))，head(tail(head(tail(head(A))))等于。
6. 已知广义表L=（（x,y,z），a，（u，t，w）），从L表中取出原子项t的运算是（）。
head（tail（tail（L）））B. tail（head（head（tail（L））））C. head（tail（head（tail（L））））D. head（tail （head（tail（tail（L）））））7. 已知广义表LS＝((a,b,c),(d,e,f)),运用head和tail函数取出LS中原子e的运算是( )。
head(tail(LS))B. tail(head(LS))C.head(tail(head(tail(LS))))D.head(tail(tail(head(LS))))8. 广义表的_______ 定义为广义表中括弧的重数。
9．设广义表L=((),()), 则head(L)是___；tail(L)是____；L的长度是___；深度是__。
10. 当广义表中的每个元素都是原子时，广义表便成了_______。
11. n阶对称矩阵a满足a[i][j]=a[j][i],i,j=1..n,，用一维数组t存储时，t的长度为________12. 设广义表L=（（a,b,c）），则L的长度和深度分别为（）。
A. 1和1B. 1和3C. 1和2D. 2和313. 下面说法不正确的是( )。
A.广义表的表头总是一个广义表B. 广义表的表尾总是一个广义表C.广义表难以用顺序存储结构D. 广义表可以是一个多层次的结构1. 将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（B ）。
供选择的答案：A. 198B. 195C. 1973. 设A是n*n的对称矩阵，将A的对角线及对角线上方的元素以列为主的次序存放在一维数组B[1..n(n+1)/2]中，对上述任一元素aij(1≤i，j≤n，且i≤j)在B中的位置为( B )。
A. i(i-l)/2+jB. j(j-l)/2+iC. j(j-l)/2+i-1D. i(i-l)/2+j-14. A[N，N]是对称矩阵，将下面三角（包括对角线）以行序存储到一维数组T[N（N+1）/2]中，则对任一上三角元素a[i][j]对应T[k]的下标k是（B ）。
A. i（i-1）/2+jB. j（j-1）/2+iC. i（j-i）/2+1D. j（i-1）/2+15. 设二维数组A[1.. m，1..n]（即m行n列）按行存储在数组B[1.. m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为( A )。
A.（i-1）*n+jB.（i-1）*n+j-1C. i*（j-1）D. j*m+i-17. 数组A[0..4,-1..-3,5..7]中含有元素的个数（B ）。
A. 55B. 45C. 36D. 168. 广义表A=(a,b,(c,d),(e,(f,g))),则下面式子的值为（D ）。
Head(Tail(Head(Tail(Tail(A)))))A. (g)B. (d)C. cD. d9. 已知广义表: A=(a,b), B=(A,A), C=(a,(b,A),B),求下列运算的结果:tail(head(tail(C))) =( F )。
A.（a）B. AC. aD. (b)E. bF. (A)10. 广义表运算式Tail(((a,b),(c,d)))的操作结果是（ C ）。
A. (c,d)B. c,dC. ((c,d))D. d11. 广义表L=（a，（b，c）），进行Tail（L）操作后的结果为（D ）。
A. cB. b，cC.（b，c）D.（（b，c））12. 广义表（（a,b,c,d））的表头是（A ），表尾是（D ）。
A. aB.（）C.（a,b,c,d）D.（b,c,d）二、判断题1. 数组不适合作为任何二叉树的存储结构。
（×）2. 从逻辑结构上看，n维数组的每个元素均属于n个向量。
（√）3. 稀疏矩阵压缩存储后，必会失去随机存取功能。
（√）4. 数组是同类型值的集合。
（×）5. 数组可看成线性结构的一种推广，因此与线性表一样，可以对它进行插入，删除等操作※6. 一个稀疏矩阵A m*n采用三元组形式表示，若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了A m*n的转置运算。
（×）7. 二维以上的数组其实是一种特殊的广义表。
（√ ）8. 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。
（×）9. 若一个广义表的表头为空表，则此广义表亦为空表。
（×）10. 广义表中的元素或者是一个不可分割的原子，或者是一个非空的广义表。
（×）11. 所谓取广义表的表尾就是返回广义表中最后一个元素。
（×）12. 广义表的同级元素（直属于同一个表中的各元素）具有线性关系。
（√ ）13. 对长度为无穷大的广义表，由于存储空间的限制，不能在计算机中实现。
（√ ）14. 一个广义表可以为其它广义表所共享。
（√ ）三、填空题1．设广义表L=((),()), 则head(L)是(1) () ___；tail(L)是(2) （()_）__；L的长度是(3)2_ _；深度是(4)_2 _。
2. 已知广义表A=(9,7,( 8,10,(99)),12)，试用求表头和表尾的操作Head( )和Tail( )将原子元素99从A中取出来。
head（head（tail（tail（head（tail（tail（A）））））））3. 广义表的深度是__表展开后所含括号的层数____。
4. 广义表(a,(a,b),d,e,((i,j),k))的长度是（1）5，深度是（2） 3 _。
5. 已知广义表LS=(a，(b，c，d)，e),运用head和tail函数取出LS中原子b的运算是_head(head(tail(LS)))_____。
6. 广义表A=（（（a，b），（c，d，e））），取出A中的原子e的操作是:__head(tail(tail(head(tail(head(A))))))__。
一、基础知识题5.1 已知二维数组A[3][5]，其每个元素占3个存储单元，并且A[0][0]的存储地址为1200。
求元素A[1][3]的存储地址（分别对以行序和列序为主序存储进行讨论），该数组共占用多少个存储单元？【解答】按照以行序为主序存储公式：LOC(i，j)=LOC(c1，c2)+[(i-c1)*(d2-c2+1)+(j-c2)]*L 在C语言中有：LOC(i，j)=LOC(0，0)+(i*(d2+1)+j)*L则：LOC(A[1][3])=1200+(1*5+3)*3=1224 (按行序存储)LOC(A[1][3])=1200+(3*3+1)*3=1230 (按列序存储)5.2 有一个10阶的对称矩阵A，采用压缩存储方式以行序为主序存储，A[1][1]为第一元素，其存储地址为1，每个元素占一个地址空间，求A[7][5]和A[5][6]的地址。
【解答】按照公式：LOC(A[7][5])=7(7-1)/2＋5 = 26LOC(A[5][6])=LOC(A[6][5])=6(6-1)/2+5=205.3 设有一个二维数组A[m][n]，设A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，问A[3][3]存放在什么位置？【解答】因为A[0][0]存放位置在644，A[2][2]存放位置在676，每个元素占一个空间，说明一行有15个元素（算法：（676－2－644）/2）。
A[3][3]存放位置是692。
5.4 二维数组A[9][10]的元素都是6个字符组成的串，请回答下列问题：（1）存放A至少需要( )个字节；（2）A的第7列和第4行共占( )个字节；（3）若A按行存放，元素A[7][4]的起始地址与A按列存放时哪一个元素的起始地址一致。
【解答】按照题5.1给出的公式：（1）存放A需要9*10*6=540个字节（2）A的第7列和第4行共占(9+10-1)*6=108个字节3）LOC(A[7][4])= LOC(A[0][0])+[7*10+4]*L (按行序存储)LOC(A[i][j])= LOC(A[0][0])+[j*9+i]*L（按列序存储，0<=i<=8,0<=j<=9)所以,i=2,j=8。
即元素A[7][4]的起始地址与A按列存放时A[2][8]的起始地址一致。
第二章习题1. L是线性表，已知Length(L)的值是5，经运算Delete(L, 2)后，Length(L)的值是（）A. 5B. 0C.4D.62. 线性表中，只有一个直接前驱和一个直接后继的是（）A. 首元素B. 尾元素C. 中间的元素D. 所有的元素3. 带头节点的单链表为空的判断条件是（）A. head == NULLB. head->next == NULLC. head->next = headD. head != NULL4. 不带头节点的单链表head为空的判定条件是（）A. head = =NULLB. head->next == NULLC. head->next = headD. head != NULL 5．非空的循环单链表head的尾结点P满足（）。
