第8章 数据结构解析.ppt

第8章 数据结构与算法 8.1 线性结构 考点：线性表的特点，栈和队列的特点 一、线性表 1.定义： （1）存在唯一的一个称作“第一个”的元素 （2）存在唯一的一个称作“最后一个”的元素 （3）除第一个和最后一个元素外，序列中的每个元素均只有一个直接前驱和直接后继 2.线性表的存储结构：顺序存储和链式存储  二、栈和队列 1.栈的定义和基本运算 2.队列的定义和基本运算 3.串的定义和基本运算 练习 1.设有一个初始为空的栈，若输入序列为1、2、3、…、n（n3），且输出序列的第一个元素是 n-1，则输入序列中所有元素都出栈后， —— 。 A.元素 n-2 一定比 n-3 先出栈 B.元素 1～n-2 在输出序列中的排列是不确定的 C.输出序列末尾的元素一定为 1 D. 输出序列末尾的元素一定为 n 2.栈和队列都是线性的数据结构。以下关于栈和队列的叙述中，正确的是 ——。 A. 栈适合采用数组存储，队列适合采用循环单链表存储 B. 栈适合采用单链表存储，队列适合采用数组存储 C. 栈和队列都不允许在元素序列的中间插入和删除元素 D. 若进入栈的元素序列确定，则从栈中出来的序列也同时确定 3.若在单向链表上，除访问链表中所有结点外，还需在表尾频繁插入结点，那么采用——最节省时间。 A.仅设尾指针的单向链表 B.仅设头指针的单向链表 C.仅设尾指针的单向循环链表 D.仅设头指针的单向循环链表 4.已知栈 S 初始为空，对于一个符号序列a1a2a3a4a5（入栈次序也是该次序），当用I表示入栈、O表示出栈，则通过栈S得到符号序列a2a4a5a3a1的操作序列为—— 。 A. I O I I O O I O O I B. I I O I O I O I O O C. I O O I I O I O I O D. I I O I I O I O O O 5.队列是一种按“先进先出”原则进行插入和删除操作的数据结构。若初始队列为空，输入序列为 a b c d e，则可得到的输出序列为 —— A. abcde B.abdce C.edcba D. edabc 6.以下应用中，必须采用栈结构的是 。 A.使一个整数序列逆转 B.递归函数的调用和返回 C.申请和释放单链表中的结点 D.装入和卸载可执行程序 8.2 数组和矩阵 考点：数组和矩阵的定义以及基本运算 一、数组的定义及基本运算 二、矩阵的定义及基本运算 练习 1.下三角矩阵A[0…8，0…8]如下图所示，若将其下三角元素（即行下标不小于列下标的所有元素）按列压缩存储在数组M[0…m]中，即A[0,0]存储在M[0]、A[1,0]存储在M[1]、A[2,0]存储在M[2]，…，A[8,8]存储在M[44]，则元素A[5,5]存储在—1—。若将其下三角元素按行压缩存储在数组M[0…m]中，即A[0,0]存储在M[0]、A[1,0]存储在M[1]、A[1,2]存储在M[2]，…，A[8,8]存储在M[44]，则元素A[5,5]存储在 2 。 （1）A.M[15] B.M[20] C.M[35] D.M[39] （2）A.M[15] B.M[20] C.M[35] D.M[39] 3.设数组a[0..m,1..n]的每个元素占用1个存储单元，若元素按行存储，则数组元素a[i,j]（0≤i≤m，1≤j≤n）相对于数组空间首地址的偏移量为（32） 。 （32）A. (i+1)*n+j B. i*n+j-1 C. i*m+j D. i*(m+1)+j-1 2.对于二维数组 a[1..6,1..8]，设每个元素占 2 个存储单元，且以列为主序存储，则元素 a[4,4]相对于数组空间起始地址的偏移量是 ———— 个存储单元。 A. 28 B. 42 C. 48 D. 54 4.已知对称矩阵 An*n（Ai,j=Aj,i）的主对角线元素全部为 0，若用一维数组 B 仅存储矩阵 A 的下三角区域的所有元素（不包括主对角线元素），则数组 B 的大小为 （40） 。 A. n(n-1) B. n2/2 C. n(n-1)/2 D. n(n+1)/2 8.3 树和图 考点：二叉树的定义及基本运算，图的定义及基本运算 一、树的定义 二、二叉树的定义及基本运算 三、图的定义及基本运算 练习 1.某二叉树的先序遍历序列为 ABFCDE、中序遍