第8章-数据结构

第8章数据结构与算法8.1线性结构

考点：线性表的特点，栈和队列的特点

一、线性表1.定义：（1）存在唯一的一个称作“第一个”的元素（2）存在唯一的一个称作“最后一个”的元素（3）除第一个和最后一个元素外，序列中的每个元素均只有一个直接前驱和直接后继2.线性表的存储结构：顺序存储和链式存储

二、栈和队列1.栈的定义和基本运算2.队列的定义和基本运算3.串的定义和基本运算练习1.设有一个初始为空的栈，若输入序列为1、2、3、…、n（n>3），且输出序列的第一个元素是n-1，则输入序列中所有元素都出栈后，—— 。A.元素n-2一定比n-3先出栈B.元素1～n-2在输出序列中的排列是不确定的C.输出序列末尾的元素一定为1D.输出序列末尾的元素一定为n2.栈和队列都是线性的数据结构。以下关于栈和队列的叙述中，正确的是——。A.栈适合采用数组存储，队列适合采用循环单链表存储B.栈适合采用单链表存储，队列适合采用数组存储C.栈和队列都不允许在元素序列的中间插入和删除元素D.若进入栈的元素序列确定，则从栈中出来的序列也同时确定AC3.若在单向链表上，除访问链表中所有结点外，还需在表尾频繁插入结点，那么采用——最节省时间。A.仅设尾指针的单向链表B.仅设头指针的单向链表C.仅设尾指针的单向循环链表 D.仅设头指针的单向循环链表4.已知栈S初始为空，对于一个符号序列a1a2a3a4a5（入栈次序也是该次序），当用I表示入栈、O表示出栈，则通过栈S得到符号序列a2a4a5a3a1的操作序列为—— 。A.IOIIOOIOOIB.IIOIOIOIOOC.IOOIIOIOIOD.IIOIIOIOOO5.队列是一种按“先进先出”原则进行插入和删除操作的数据结构。若初始队列为空，输入序列为abcde，则可得到的输出序列为 ——A.abcde

B.abdce

C.edcbaD.edabcAAD6.以下应用中，必须采用栈结构的是。A.使一个整数序列逆转B.递归函数的调用和返回C.申请和释放单链表中的结点D.装入和卸载可执行程序B8.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]CB3.设数组a[0..m,1..n]的每个元素占用1个存储单元，若元素按行存储，则数组元素a[i,j]（0≤i≤m，1≤j≤n）相对于数组空间首地址的偏移量为（32）。（32）A.(i+1)*n+jB.i*n+j-1C.i*m+jD.i*(m+1)+j-1

2.对于二维数组a[1..6,1..8]，设每个元素占2个存储单元，且以列为主序存储，则元素a[4,4]相对于数组空间起始地址的偏移量是 ———— 个存储单元。A.28B.42C.48D.54

4.已知对称矩阵An*n（Ai,j=Aj,i）的主对角线元素全部为0，若用一维数组B仅存储矩阵A的下三角区域的所有元素（不包括主对角线元素），则数组B的大小为（40）。A.n(n-1)B.n2/2C.n(n-1)/2D.n(n+1)/2DBC8.3树和图考点：二叉树的定义及基本运算，图的定义及基本运算一、树的定义二、二叉树的定义及基本运算三、图的定义及基本运算练习1.某二叉树的先序遍历序列为ABFCDE、中序遍历序列为BFADCE，则该二叉树根的左孩子和右孩子结点分别是—— 。A.B和FB.F和BC.B和CD.C和B2.若无向连通图G具有n个顶点，则以下关于图G的叙述中，错误的是——。A.G的边数一定多于顶点数B.G的生成树中一定包含n个顶点C.从G中任意顶点出发一定能遍历图中所有顶点D.G的邻接矩阵一定是n阶对称矩阵3.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点（即叶子结点）个数是（39）。A.不确定B.9C.11D.15CAC4.以下关于图及其存储结构的叙述中，正确的是（41）。A.无向图的邻接矩阵一定是对称的B.有向图的邻接矩阵一定是不对称的C.无向图采用邻接表存储更节省存储空间D.有向图采用邻接表存储更节省存储空间

5.知某二叉树的先序遍历序列是ABDCE，中序遍历序列是BDAEC，则该二叉树为——

AC6.某二叉树为单枝树（即非叶子节点只有一个孩子节点）且具有n个节点）则该二叉树_____

A.共有n层,每层只有一个结点

B.共有n层，相邻两层的结点数正好相差一倍

C.先序遍历序列与中序遍历序列相同

D.后序遍历序列与中序遍历序列相同

A8.4常用算法

考点：算法的定义，算法的常用描述工具，常用的排序算法，查找算法，以及字符串处理算法和递归算法一、算法概述（算法定义，算法描述工具）二、排序算法三、查找算法四、字符串处理五、递归算法六、图的相关算法练习1.在直接插入排序、冒泡排序、简单选择排序和快速排序方法中，能在第一趟排序结束后就得到最大（或最小）元素的排序方法是（43）。A.冒泡排序和快速排序B.直接插入排序和简单选择排序C.冒泡排序和简单选择排序D.直接插入排序和快速排序2.对n个元素的有序表A[1…n]进行二分（折半）查找，则成功查找到表中的任意一个元素时，最多与A中的（39）个元素进行比较。A.n-1B.n/2C.n(n-1)/2D.n3.以下关于程序员流程图、N-S盒图和决策的叙述中，错误的是（32）。A.N-S盒图可以避免随意的控制转移B.N-S盒图可以同时表示程序逻辑和数据结构

C.程序流程图中的控制流可以任意转向

D.决策表适宜表示多重条件组合下的行为CBA4.若构造哈希表时不发生冲突，则给定的关键字与其哈希地址之间的对应关系是（43）。（其中n>1且m>1）A.1:1B.1:nC.n:1D.n:m5.

（38）并不是算法必须具备的特性。A.可行性B.可移植性C.确定性D.有穷性6.设S是一个长度为5的字符串，其中的字符各不相同，则计算S中互异的非平凡子串（非空且不同于S本身）数目的算式为 （41） 。A.5+4+3+2+1B.5+4+3+2C.4+3+2+1D.4+3+2ABB7.折半（二分）查找方法对查找表的要求是（42）。A.链表存储结构，元素有序排列B.链表存储结构，元素无序排列C.顺序存储结构，元素有序排列D.顺序存储结构，元素无序排列C

在以下情形中，___(35)___适合于采用队列数据结构。A．监视一个火车票售票窗口等待服务的客户D．描述一个组织中的管理机构C．统计一个商场中的顾客数D．监视进入某住宅楼的访客元素3、1、2依次全部进入一个栈后，陆续执行出栈操作，得到的出栈序列为___(36)___。A．3、2、1

B．3、1、2

C．1、2、3

D．2、1、3

AD以下各图用树结构描述了7个元素之间的逻辑关系，其中___(39)___适合采用二分法查找元素。a

C

对于二维数组a[0…4,1…5]，设每个元素占1个存储单元，且以行为主序存储，则元素a[2,1]相对于数组空间起始地址的偏移量是___(40)___。A．5

B．10

C．15

D．25

B设数组a[1...m，1…n]（m>1,n>2）中的元素以行为主序存放，每个元素占用1个存储单元，则最后一个数组元素a[m,n]相对于数组空间首地址的偏移量为____（35）_____。（35）A.（m-1）*n+n-1B.（m-1）*nC.m*（n-1）D.m*n●设push、pop分别为表示入栈、出栈操作，若初始栈为空，对于元素序列abc，则操作序列push、pop、pop、push、push、pop__(36)_____。(36)A.得到出栈序列为abcB.得到出栈序列为bacC.得到出栈序列为bcaD.是非法的操作序列AD在有11个元素的有序数组a[1..11]中进行二分法查找（既折半查找），依次与___（37）___比较后，成功找到元素a[5]。（37）A.a[6]、a[2]、a[5]B.a[6]、a[4]、a[5]C.a[6]、a[3]、a[4]、a[5]D.a[6]、a[8]、a[4]、a[5]从未排序的序列中依次取出一个元素与已排序序列中的元素进行比较，然后将其放在已排序序列的合适位置上，该排序方法为___（39）___。（39）A.插入排序B.选择排序C.快速排序D.冒泡排序CA一个高度为h的满二叉树的结点总数为2（h次方）-1其每一层结点个数都达到最大值。从根结点开始顺序编号，即根结点编号为1，其左、右孩子结点编号分别为2和3，再下一层从左到右的编号为4、5、6、7，依次类推，每一层都从左到右依次编号，直到最后的叶子结点层为止。那么，在一颗满二叉树中，对于编号m和n的两个结点，若m=2n+1，则__(38)_(38)A.m是n的左孩子B.m是n的右孩子

C.n是m的左孩子D.n是m的右孩子在具有n（n>0）个顶点的简单无向图中，最多含有___（43）___条边。（43）A.n（n-1）B.n（n+1）C.n*（n-1）/2D.n*（n+1）/2BC