学习-----好资料
单元练习8
一．判断题（下列各题，正确的请在前面的括号内打√；错误的打）╳（√）（1）图可以没有边，但不能没有顶点。
（ㄨ）（2）在无向图中，（V，V）与（V，V）是两条不同的边。1221（ㄨ）（3）邻接表只能用于有向图的存储。
（√）（4）一个图的邻接矩阵表示是唯一的。
（ㄨ）（5）用邻接矩阵法存储一个图时，所占用的存储空间大小与图中顶点个数无关，而只与图的边数有关。
（ㄨ）（6）有向图不能进行广度优先遍历。
（√）（7）若一个无向图的以顶点V为起点进行深度优先遍历，所得的遍历序列唯一，则可以唯一1确定该图。
（√）（8）存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角（或下三角）部分就可以了。
（ㄨ）（9）用邻接表法存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。
（√）（10）若一个无向图中任一顶点出发，进行一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。
二．填空题
（1）图常用的存储方式有邻接矩阵和邻接表等。
（2）图的遍历有：深度优先搜和广度优先搜等方法。
（3）有n条边的无向图邻接矩阵中，1的个数是 _2n____。
（4）有向图的边也称为 _ 弧___ 。
（5）图的邻接矩阵表示法是表示 __顶点____之间相邻关系的矩阵。
（6）有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的 __出度____。
2）n。e条边的图若采用邻接矩阵存储，则空间复杂度为：O（（7）n个顶点
（8）n个顶点e条边的图若采用邻接表存储，则空间复杂度为：O（n+e）。
（9）设有一稀疏图G，则G采用 _邻接表____存储比较节省空间。
（10）设有一稠密图G，则G采用 _邻接矩阵____存储比较节省空间。
（11）图的逆邻接表存储结构只适用于 __有向____图。
（12） n个顶点的完全无向图有 n(n-1)/2_ 条边。
（13）有向图的邻接表表示适于求顶点的出度。
（14）有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点V的入度。i （15）对于具有n个顶点的图，其生成树有且仅有n-1 条边。
（16）对n个顶点，e条弧的有向图，其邻接表表示中，需要n+e 个结点。
（17）从图中某一顶点出发，访遍图中其余顶点，且使每一顶点仅被访问一次，称这一过程为图
的遍历。
（18）无向图的邻接矩阵一定是对称矩阵。
更多精品文档．
学习-----好资料
（19）一个连通网的最小生成树是该图所有生成树中权最小的生成树。
（20）若要求一个稠密图G的最小生成树，最好用Prim 算法来求解。
三．选择题
（1）在一个图中，所有顶点的度数之和等于图的边数的( C )倍。
A．1/2 B. 1 C. 2 D. 4
（2）在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( B )倍。
A．1/2 B. 1 C. 2 D. 4
（3）对于一个具有n个顶点的有向图的边数最多有（ B ）。
A．n B．n(n-1) C．n(n-1)/2 D．2n
（4）在一个具有n个顶点的无向图中，要连通全部顶点至少需要（ C ）条边。
A．n B．n+1
C． n-1
D．n/2
（5）有8个结点的有向完全图有( C )条边。
A．14 B. 28 C. 56 D. 112
（6）深度优先遍历类似于二叉树的( A )。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历（7）广度优先遍历类似于二叉树的( D )。
A．先序遍历 B．中序遍历 C．后序遍历 D．层次遍历（8）任何一个无向连通图的最小生成树( A )。
A．只有一棵 B．一棵或多棵 C．一定有多棵 D．可能不存在（9）无向图顶点v的度是关联于该顶点（ B ）的数目。
A．顶点 B．边 C．序号 D．下标
（10）有n个顶点的无向图的邻接矩阵是用（ B ）数组存储。
A．一维 B．n行n列 C．任意行n列 D．n行任意列
（11）对于一个具有n个顶点和e条边的无向图，采用邻接表表示，则表头向量大小为（ C ）。n+e
D． Cn+1
．n
n-1
A． B． A ）。（12）在图的表示法中，表示形式唯一的是
（ B．邻接表表示法 A．邻接矩阵表示法．邻接表和逆邻接表表示法 C．逆邻接表表示法 D ）。e条边的图中，所有顶点的度数之和等于（ C 13（）在一个具有n个顶点2e
D． C． 2n ． A．n Be
）。）下列图中，度为（143的结点是（B
1
2
3
54更多精品文档．
学习-----好资料
D. V C. V A．V B. V4321（15）下列图是
（ A ）。
1
2
3
54
D. 无环图 B. 强连通图 C. 生成树 A．连通图
。） D （16）如下图所示，从顶点a出发，按深度优先进行遍历，则可能得到的一种顶点
序列为（
a
f ，b，e，c，dA．a，d ，，f，e，bB．a，c b
c
d f，，c，，C. ae，b
e b ，f，c，eD. a，，d
f d
）A 。17（）如下图所示，从顶点a出发，按广度优先进行遍历，则可能得到的一种顶点序
列为（
a
f ，b，e，，d，cA.ad f，，，e，caB.，b b
c
d c，f，eC.a，，b，
e b ，c，eD.a，，d，
f f d
）算法。18（）最小生成树的构造可使用（ A
prim算法 B．卡尔算法 C．迪杰斯特拉算法 D．哈夫曼算法 A． A ）下面关于图的存储结构的叙述中正确的是（）。（19 用邻接矩阵存储图，占用空间大小只与图中顶点数有关，而与边数无关．A
用邻接矩阵存储图，占用空间大小只与图中边数有关，而与顶点数无关
B．用邻接表存储图，占用空间大小只与图中顶点数有关，而与边数无关．C 用邻接表存储图，占用空间大小只与图中边数有关，而与顶点数无关D．
（20）连通分量是（）的极大连通子图。 C
．无向图 B ．树 A ．图 C ．有向图D
四．应用题（30分）更多精品文档．
好资料学习-----．有向图如下图所示，画出邻接矩阵和邻接表1
①
③②
⑤④
解：（1）邻接矩阵
1 2 3 4 5
110101????020010????100300??000410????010500??
（2）邻接表
1 2 3 5 ∧
2 ∧ 4
∧ 3 5
∧ 4 1
∧ 5 4
），5，），（，（）条边依次为（条边，这个结点，．2 已知一个无向图有6990，1,02）,04,（0出发，分别0443423，），（，），（，），（，5）。试画出该无向图，并从顶点221（，），（分）写出按深度优先搜索和按广度优先搜索进行遍历的结点序列。（5 解：
5
12 4
3
3 5（答案不唯一）
4 出发的深度优先搜索遍历的结点序列：从顶点00 1 2
（答案不唯一）出发的广度优先搜索遍历的结点序列：00 1 2 4 5 3从顶点
3．已知一个无向图的顶点集为：{a，b，c，d，e}，其邻接矩阵如下，画出草图，写出顶点a 出更多精品文档．
学习-----好资料
发按深度优先搜索进行遍历的结点序列。（5分）
01001????00011????11000??01101????01101??
解：
（1）（2）深度优先搜索：
a a
b d
c e （答案不唯一）
广度优先搜索：
c e b a b e
d c （答案不唯一）
d
4．网G的邻接矩阵如下，试画出该图，并画出它的一棵最小生成树。
0810110????803013??
??004103??110407????070013??
解：最小生成树：
1 1
8 11
10 8
3 4 3 4
2 4
3 2
13 7 3 4
7 5 5
5. 已知某图G的邻接矩阵如图，
0101??（1）画出相应的图；??0011??）要使此图为完全图需要增加几条边。（2??1001??1010
解：
（1） 1 21 2
4 3 3 4
（2）完全无向图应具有的边数为：n*(n-1)1/2=4*(4-1)/2=6，所以还要增加2条边（如右图）。更多精品文档．
好资料学习-----:
．已知如图所示的有向图，请给出该图的6
/出度；1）每个顶点的入（邻接表；（2）邻接矩阵。（3）
数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素
数据结构模拟试卷（一） 一、选择题（每题2分，20题，共40分） 1. 数组A[1..5,1..6]的每个元素占5个单元，将其按行优先顺序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为（）。 A．1140 B．1145 C．1120 D．1125 2. 下面的序列中，（）是堆。 A．1,510,6,7,8,9,2 B．1,2,8,4,3,9,10,5 C．9,8,7,6,4,8,2,1 D．9,8,7,6,5,4,3,7 3. 二叉树上结点的左子树深度减去其右子树深度称为该结点的平衡因子。平衡二叉树中任意结点的平衡因子只能是（）。 A．0 B．0,1 C．-1,0,1 D．1 4. 栈和队列的共同特点是： A．都是先进先出B．都是先进后出 C．只允许在端点处插入和删除元素D．没有共同点 5. 若进栈序列为a,b,c，则通过入出栈操作可能得到的a,b,c的出栈的不同排列个数为( ) A．4 B．5 C．6 D．7 6. 关键路径是AOE网中的______ 。 A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最短的回路 D．活动的最早开始时间与最迟发生时间相等 7. 已知数据元素为( 32 ，75 ，46 ，19 ，26，56 ，93 ，66 )，按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（）。 A．4 B．5 C．7 D．6 8. 下列说法不正确的是______。 A．图的遍历是从给定的源点出发，每一个顶点仅被访问一次 B．遍历的基本算法有两种：深度遍历和广度遍历 C．图的深度遍历不适用于有向图 D．图的深度遍历是一个递归过程 9. 单循环链表的主要优点是（）。 A．从表中任一结点出发都能扫描到整个链表 B．不再需要头指针了 C．在进行插入、删除操作时，能更好地保证链表不断开 D．已知某个结点的位置后，能够容易找到它的直接前趋 10. 已知一棵树的前序遍历是”GDAFEMHZ”，而中序遍历是”ADEFGHMZ”，求后序遍历？A．ADEFGHMZ B．DAEFHZMG C．AEFDHZMG D．AFEDHMZG 11. 一个包含n个节点的四叉树，每个节点都有四个指向孩子节点的指针，这4n个指针中有多少个空指针？ A．2n+1 B．3n-1 C．3n D．3n+1 12. 和顺序栈相比,链栈有一个比较明显的优势是() A．通常不会出现栈满的情况
数据结构练习题(含答案)
数据结构练习题 习题1 绪论 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 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ ,
第2章自测卷答案姓名班级 一、填空（每空1分，共13分） 1. 【严题集 2.2①】在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。 2. 线性表中结点的集合是有限的，结点间的关系是一对一的。 3. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。 4. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。 5. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。 6. 【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。 7. 【严题集2.2①】在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。 8．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。 二、判断正误（在正确的说法后面打勾，反之打叉）（每小题1分，共10分）（×）1. 链表的每个结点中都恰好包含一个指针。 答：错误。链表中的结点可含多个指针域，分别存放多个指针。 例如，双向链表中的结点可以含有两个指针域，分别存放指向其 直接前趋和直接后继结点的指针。 （×）2. 链表的物理存储结构具有同链表一样的顺序。 错，链表的存储结构特点是无序，而链表的示意图有序。 （×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 错，链表的结点不会移动，只是指针内容改变。 （×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序 表，也能存放记录型数据。 （×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
少年易学老难成，一寸光阴不可轻- 百度文库 《数据结构》 一、单项选择题（本大题共10小题，每小题3分，共30分） 1、若进栈的序列为1，2，3，4，则不可能得到的出栈序列是（）。 A. 3,2,1,4 B. 3,2,4,1 C. 4,2,3,1 D. 2,3,4,1 2、深度为k的完全二叉树所含叶结点的个数最多为（），设根结点在第1层上。 A. 2k B. 2k-1 C. k D. 2k-1 3、衡量查找算法效率的主要标准是（）。 A. 元素个数 B. 所需的存储量 C. 平均查找长度 D. 算法难易程度 4、与线性表的顺序存储不相符的特性是（）。 A. 插入和删除操作灵活 B. 需要连续的存储空间 C. 便于随机访问 D. 存储密度大 5、若进队序列为1，2，3，则出队序列是（）。 A. 3,2,1 B. 1,2,3 C. 1,3,2 D. 3,1,2 6、不带头结点的单链表L为空的判定条件是（）。 A. L==NULL B. L->next==NULL C. L->next==L D. L!=NULL 7、union(A,B,C)表示求集合A和B的并集C。若A={a,b,c},B={c,d},则union(A,B,C)运算后C=（）。 A．{a,b,c,d} B．{a,b,c} C．{a,b} D．{c,d} 8、数组A中，每个元素的长度为3个存储单元，行下标i从1到5，列下标j从1到6，从首地址SA开始连续存放在存储器内，存放该数组至少需要的存储单元数是（）。 A. 90 B. 70 C. 50 D. 30 9、遍历一棵具有n个结点的二叉树，在先序序列、中序序列和后序序列中所有叶子结点的相对次序（）。 A. 都不相同 B. 完全相同 C. 先序和中序相同 D. 中序和后序相同 10、用给定的哈夫曼编码来压缩数据文件，其压缩效率主要取决于（）。 A. 文件长度 B. 平均码长 C. 被压缩文件的特征 D. 以上都不是 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、当利用大小为N的数组顺序存储一个栈时，假定用top==N表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。 A. top++ B. top-- C. top=0 D. top=N-1 7、在一个带头结点的双向循环链表中，若要在p所指向的结点之前插入一个新结点，则需要相继修改（）个指针域的值。 A. 2 B. 3 C. 4 D. 5 8、利用3,6,8,12,5,7这六个值作为叶子结点的权，生成一棵哈夫曼树，该树的深度为（）。 A. 3 B. 4
第2章答案 一、填空 1.在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。 2. 线性表中结点的集合是有限的，结点间的关系是一对一的。 3. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。 4. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。 5. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。 6.顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。 7.在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。 8．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。 二、判断正误（在正确的说法后面打勾，反之打叉） （×）1. 链表的每个结点中都恰好包含一个指针。 答：错误。链表中的结点可含多个指针域，分别存放多个指针。例如，双向链表中的结点可以含有两个指针 域，分别存放指向其直接前趋和直接后继结点的指针。 （×）2. 链表的物理存储结构具有同链表一样的顺序。错，链表的存储结构特点是无序，而链表的示意图有序。（×）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。错，链表的结点不会移动，只是指针内容改变。 （×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，混淆了逻辑结构与物理结构，链表也是线性表！且即使是顺序表，也能存放记录型数据。 （×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 错，正好说反了。顺序表才适合随机存取，链表恰恰适于“顺藤摸瓜” （×）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 错，前一半正确，但后一半说法错误，那是链式存储的优点。顺序存储方式插入、删除运算效率较低， 在表长为n的顺序表中，插入和删除一个数据元素，平均需移动表长一半个数的数据元素。 （×）7. 线性表在物理存储空间中也一定是连续的。 错，线性表有两种存储方式，顺序存储和链式存储。后者不要求连续存放。 （×）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。 错误。线性表有两种存储方式，在顺序存储时，逻辑上相邻的元素在存储的物理位置次序上也相邻。（×）9. 顺序存储方式只能用于存储线性结构。 错误。顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于 非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍） （×）10. 线性表的逻辑顺序与存储顺序总是一致的。 错，理由同7。链式存储就无需一致。 三、单项选择题
数据结构试题（A05） 一、选择题（共10小题，每小题1分，共10分） 1.下面程序段的时间复杂度是( ) m=0; for(i=1;i<=n;i++) for(j=1;j<=n;j++) m=m+1； A. O(n2) B.O(m+n+1) C.O(m+n) D. O(n) 2.在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是( ) A.p=p->next; B.p->next=p->next->next; C.p->next=p; D.p=p->next->next; 3.在长度为n的顺序表，当在任何位置上删除一个元素的概率相等时，删除一个元素需要移动的元素的平均个数为( ) A.n/2 B.（n-1）/ 2 C.(n+1)/2 D.(n+2)/2 4.一个栈的输入序列为 1 2 3 4 5，则下列序列中不可能是栈的输出序列的是( ) A. 2 3 4 1 5 B. 5 4 1 3 2 C. 2 3 1 4 5 D. 1 5 4 3 2 6.设循环队列中数组的下标范围是1～n，其头尾指针分别为f和r，则其元素个数为( ) A. r-f B. r-f+1 C. (r-f) mod n+1 D. (r-f+n) mod n 7.以下序列不是堆的是( )。 A.（100，85，98，77，80，60，82，40，20，10，66） B.（100，98，85，82，80，77，66，60，40，20，10） C.（100，85，40，77，80，60，66，98，82，10，20） D.（10，20，40，60，66，77，80，82，85，98，100） 8．在有序表（12，24，36，48，60，72，84）中折半查找关键字72时所需进行的关键字比较次数为( )。 A. 3 B. 4 C. 5 D. 2 9.在待排序的元素序列基本有序的前提下，效率最高的排序方法是( )。 A.选择排序 B.冒泡排序 C.快速排序 D.插入排序 二、填空题（共20小题，每小题1分，共20分） 1、在单链表中，删除指针P所指结点的后继结点的语句是。 2、线性表的两种存储结构分别是和。 3、己知完全二叉树的第4层有5个结点，则其叶子结点数是。 4、将下三角矩阵A[1….8，1….8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占4个单元，则A[7，5]的地址是。 5、有n个结点的强连通有向图G至少有条弧。 7、在有序表A[1….20]中，采用二分查找算法查找元素值等于A[12]的元素，所
一、填空题 二、1. 向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。 2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为栈顶。不允许插入和删除运算的一端称为栈底。 3. 队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。 4. 在一个循环队列中，队首指针指向队首元素的前一个位置。 5. 在具有n个单元的循环队列中，队满时共有n-1 个元素。 6. 向栈中压入元素的操作是先存入元素，后移动栈顶指针。 7.从循环队列中删除一个元素时，其操作是先移动队首指针，后取出元素。 8. 带表头结点的空循环双向链表的长度等于0。 解： 二、判断正误（判断下列概念的正确性，并作出简要的说明。） 三、（×）1. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。 错，线性表是逻辑结构概念，可以顺序存储或链式存储，与元素数据类型无关。 （×）2. 在表结构中最常用的是线性表，栈和队列不太常用。 错，不一定吧？调用子程序或函数常用，CPU中也用队列。
（√）3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）4. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 正确，都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不同 而已。 （×）5. 栈和链表是两种不同的数据结构。 错，栈是逻辑结构的概念，是特殊殊线性表，而链表是存储结构概念，二者不是同 类项。 （×）6. 栈和队列是一种非线性数据结构。 错，他们都是线性逻辑结构，栈和队列其实是特殊的线性表，对运算的定义略有不 同而已。 （√）7. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 （√）8. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （×）9. 队是一种插入与删除操作分别在表的两端进行的线性表，是一种先进后出型结构。 错，后半句不对。 （×）10. 一个栈的输入序列是12345，则栈的输出序列不可能是12345。 错，有可能。 三、单项选择题（每小题1分，共20分） （B）1. 栈中元素的进出原则是 Ａ．先进先出Ｂ．后进先出Ｃ．栈空则进Ｄ．栈满则出
数据结构模拟卷(含答案)经典习题
练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4
6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( )
一、单项选择题（在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。每小题2分，共40分） 1、串的长度是（）。 A、串中不同字母的个数 B、串中不同字符的个数 C、串中所含字符的个数，且大于0 D、串中所含字符的个数 2、若用数组S[1..n]作为两个栈S1和S2的共同存储结构，对任何一个栈，只有当S全满时才不能作入栈操作。为这两个栈分配空间的最佳方案是（）。 A、S1的栈底位置为0，S2的栈底位置为n+1 B、S1的栈底位置为0，S2的栈底位置为n/2 C、S1的栈底位置为1，S2的栈底位置为n D、S1的栈底位置为1，S2的栈底位置为n/2 3、队列操作的原则是（）。 A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删除 4、有64个结点的完全二叉树的深度为（）（根的层次为1）。 A、8 B、7 C、6 D、5 5、在有n个结点的二叉链表中，值为非空的链域的个数为（）。 A、n-1 B、2n-1
C、n+1 D、2n+1 6、带权有向图G用邻接矩阵A存储，则顶点i的人度等于A中（）。 A、第i行非∞的元素之和 B、第i列非∞的元素之和 C、第i行非∞且非0的元素个数 D、第i列非∞且非0的元素个数 7、在有n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为（）。 A、0(n) B、0(log2n) C、0(nolg2n) D、0(n2) 8、若表R在排序前已按键值递增顺序排列，则（）算法的比较次数最少。 A、直接插入排序 B、快速排序 C、归并排序 D、选择排序 9、下列排序算法中，（）排序在某趟结束后不一定选出一个元素放到其最终的位置上。 A、选择 B、冒泡 C、归并 D、堆
一．是非题 1. 数据结构(应该是抽象数据类型)可用三元式表示(D，S，P)。其中：D是数据对象，S是D上的关系，P是对D的基本操作集。(f) 2 简单地说,数据结构是带有结构的数据元素的集合。(t) 3 判断带头结点的非空循环单链表(头指针为L)中指针p所指结点是最后一个元素结点 的条件是：p->next==L。(t) 4 线性表的链式存储结构具有可直接存取表中任一元素的优点。(f) 5 线性表的顺序存储结构优于链式存储结构。(f) 6. 在单链表P指针所指结点之后插入S结点的操作是： P->next= S ; S-> next = P->next;。(f) (顺序弄反了S-> next = P->next; P->next= S ;) 7 对于插入、删除而言，线性表的链式存储优于顺序存储。(t) 8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f) 9. 栈和队列是操作上受限制的线性表。(t) 10. 队列是与线性表完全不同的一种数据结构。(f) (栈和队列是操作上受限制的线性表) 11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。(f) (两端) 12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。(f) ( “如果需要,可对它们中的任一元素进行操作.” 这里的意思是在O(1)的时间来读和改某个元素。比如数组的直接索引。 栈：如果需要，每一次只能对栈顶的元素进行操作 队列：如果需要，每一次只能对两端，或者只能对队列头的元素进行操作。) 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(f) 14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。(f) (二叉树和树相互独立) 15 二叉树是一棵结点的度最大为二的树。(f) (二叉树和树相互独立) 16 赫夫曼树中结点个数一定是奇数。(t) 17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t) (LDR) 18 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历。(f) (后根遍历相当于中序遍历) 19. 通常，二叉树的第i层上有2i-1个结点。(f) (应该为1~2i-1个) 20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t) 21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(t) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树。(t) 23 邻接多重表可以用以表示无向图，也可用以表示有向图。(f) (只能表示无向图，有向图用十字链表) 24 可从任意有向图中得到关于所有顶点的拓扑次序。(f) (带环图没有) 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t)
第十一章文件 一、选择题 1. 散列文件使用散列函数将记录的关键字值计算转化为记录的存放地址，因为散列函数是一对一的关系，则选择好的（）方法是散列文件的关键。【哈尔滨工业大学 2001二、5 （2分）】 A. 散列函数 B. 除余法中的质数 C. 冲突处理 D. 散列函数和冲突处理 2. 顺序文件采用顺序结构实现文件的存储，对大型的顺序文件的少量修改，要求重新复制整个文件，代价很高，采用（）的方法可降低所需的代价。【北京邮电大学 2000 二、8 （20/8分）】 A. 附加文件 B. 按关键字大小排序 C. 按记录输入先后排序 D. 连续排序 3. 用ISAM组织文件适合于（）。【中科院软件所 1998】 A．磁带 B．磁盘 4．下述文件中适合于磁带存储的是（）。【中科院计算所 2000 一、7（2分）】 A. 顺序文件 B. 索引文件 C. 散列文件 D. 多关键字文件 5. 用ISAM和VSAM组织文件属于（）。 A. 顺序文件 B. 索引文件 C. 散列文件
【中国科技大学 1998 二、5（2分）中科院计算所 1998 二、5（2分）】 6. ISAM文件和VASM文件属于（）。【山东大学 2001 二、5 (1分)】 A. 索引非顺序文件 B. 索引顺序文件 C. 顺序文件 D. 散列文件 7. B+树应用在（ ）文件系统中。【北京邮电大学 2001 一、1（2分）】 A. ISAM B. VSAM 二、判断题 1. 文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。【长沙铁道学院 1998 一、5 (1分)】 2. 倒排文件是对次关键字建立索引。【南京航空航天大学 1997 一、10（1分）】 3. 倒排序文件的优点是维护简单。【南京航空航天大学 1995 五、10（1分）】 【西安交通大学 1996 二、6 (3分)】 4. 倒排文件与多重表文件的次关键字索引结构是不同的。 5. Hash表与Hash文件的唯一区别是Hash文件引入了‘桶’的概念。【南京航空航天大学1996六10(1分）】 6. 文件系统采用索引结构是为了节省存储空间。【北京邮电大学 2000 一、10 （1分）】
模拟试卷三 一、单选题（每题 2 分，共20分） 1.对一个算法的评价，不包括如下（）方面的内容。 A．健壮性和可读性B．并行性C．正确性D．时空复杂度 2.在带有头结点的单链表HL中，要向表头插入一个由指针p指向的结点，则执行( )。 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.对线性表，在下列哪种情况下应当采用链表表示？( ) A.经常需要随机地存取元素 B.经常需要进行插入和删除操作 C.表中元素需要占据一片连续的存储空间 D.表中元素的个数不变 4.一个栈的输入序列为1 2 3，则下列序列中不可能是栈的输出序列的是( ) A. 2 3 1 B. 3 2 1 C. 3 1 2 D. 1 2 3 5.AOV网是一种（）。 A．有向图B．无向图C．无向无环图D．有向无环图 6.采用开放定址法处理散列表的冲突时，其平均查找长度（）。 A．低于链接法处理冲突 B. 高于链接法处理冲突 C．与链接法处理冲突相同D．高于二分查找 7.若需要利用形参直接访问实参时，应将形参变量说明为（）参数。 A．值B．函数C．指针D．引用 8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具有相同的（）。 A．行号B．列号C．元素值D．非零元素个数 9.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 10.从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(log2n) D. O(n2) 二、运算题（每题 6 分，共24分） 1.数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N） 的联系时，称这种结构为_____________________。 2.队列的插入操作是在队列的_________进行，删除操作是在队列的__________进行。 3.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件 是_____________________。 4.对于一个长度为n的单链存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 5.设W为一个二维数组，其每个数据元素占用4个字节，行下标i从0到7 ，列下标j 从0到3 ，则二维数组W的数据元素共占用＿_____＿个字节。W中第6 行的元素和第4 列的元素共占用＿_______＿个字节。若按行顺序存放二维数组W，其起始地址为100，则二维数组元素W[6，3]的起始地址为＿________＿。 6.广义表A= (a,(a,b),((a,b),c)),则它的深度为____________，它的长度为____________。 7.二叉树是指度为2的____________________树。一棵结点数为N的二叉树，其所有结 点的度的总和是_____________。 8.对一棵二叉搜索树进行中序遍历时，得到的结点序列是一个______________。对一棵由 算术表达式组成的二叉语法树进行后序遍历得到的结点序列是该算术表达式的
数据结构练习题 习题1 绪论 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 填空题（将正确的答案填在相应的空中） 1. 数据逻辑结构包括、和三种类型，树形结构和图形结构合称为。 2. 在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。 3. 在树形结构中，树根结点没有结点，其余每个结点有且只有个直接前驱结点，叶子结点没有结点，其余每个结点的直接后续结点可以。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ , __ __ , _ ___。 7. 分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。 for (i=0;i 一、概念题（每空0.5分，共28分） 1．树（及一切树形结构）是一种“________”结构。在树上，________结点没有直接前趋。对树上任一结点X来说，X是它的任一子树的根结点惟一的________。 2．由３个结点所构成的二叉树有种形态。 3．一棵深度为6的满二叉树有个分支结点和个叶子。 4．一棵具有２５７个结点的完全二叉树，它的深度为。 5．二叉树第i(i>=1)层上至多有______个结点；深度为k(k>=1)的二叉树至多有______个结点。6．对任何二叉树，若度为2的节点数为n2，则叶子数n0=______。 7．满二叉树上各层的节点数已达到了二叉树可以容纳的______。满二叉树也是______二叉树，但反之不然。 8．设一棵完全二叉树有700个结点，则共有个叶子结点。 9.设一棵完全二叉树具有1000个结点，则此完全二叉树有个叶子结点，有个度为2的结点，有个结点只有非空左子树，有个结点只有非空右子树。 10.一棵含有n个结点的k叉树，可能达到的最大深度为，最小深度为。 11.二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是。 12.中序遍历的递归算法平均空间复杂度为。 13.二叉树通常有______存储结构和______存储结构两类存储结构。 14.如果将一棵有n个结点的完全二叉树按层编号，则对任一编号为i(1<=i<=n)的结点X有： （1）若i=1,则结点X是______；若i〉1,则X的双亲PARENT(X)的编号为______。 （2）若2i>n，则结点X无______且无______；否则，X的左孩子LCHILD(X)的编号为______。 （3）若2i+1>n，则结点X无______；否则，X的右孩子RCHILD(X)的编号为______。 15.每个二叉链表的访问只能从______结点的指针，该指针具有标识二叉链表的作用。 16.二叉链表中每个存储结点的每个指针域必须有一个值，这个值或者是____________的指针，或者是______。 17.具有n个结点的二叉树中,一共有________个指针域,其中只有________个用来指向结点的左 右孩子，其余的________个指针域为NULL。 18.二叉树有不同的链式存储结构，其中最常用的是________与________。 19.若二叉树的一个叶子是某子树的中根遍历序列中的第一个结点，则它必是该子树的后根遍历序列中的________个结点。 20.树与二叉树之间最主要的差别是：二叉树中各结点的子树要区分为________和________，即使在结点只有一棵子树的情况下，也要明确指出该子树是________还是________。 21.树的结点数目至少为________，二叉树的结点数目至少为________。 22.树的主要遍历方法有________、________、________等三种。 23.由________转换成二叉树时，其根结点的右子树总是空的。 24.哈夫曼（Huffman）树是带权路径长度________的树，通常权值较大的结点离根________。 25.用5个权值{3, 2, 4, 5, 1}构造的哈夫曼（Huffman）树的带权路径长度是。 26. n个结点的线索二叉树中的线索数目为。 27.用数组[1..n]存放d堆，对于位于i的节点项，其父节点为；子节点为。 二、选择题（每空1分，共15分） （）1．不含任何结点的空树。 （Ａ）是一棵树; （Ｂ）是一棵二叉树; （Ｃ）是一棵树也是一棵二叉树; （Ｄ）既不是树也不是二叉树 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2 数据结构练习题 一、简答题 1．什么是拓扑排序？ 2．什么是堆积？ 3．图的邻接矩阵与邻接表两种存储表示法在空间代价上的差别为何？ 4．算法与程序的区别是什么? 5．什么是堆(heap)？ 6．什么是栈(stack)？ 7．什么样的图遍历后由所有顶点和遍历时所经过的边所构成的子图一定是生成树？ 8．举例说明希尔(Shell)排序是否是稳定的排序方法？ 9．什么是遍历运算？ 10．什么是A VL树？ 11．链表中的表头指针、表头结点和开始结点有什么不同？各自所起的作用是什么？12．举例说明直接选择排序是否是稳定的排序方法？ 13．什么是完全二叉树(complete binary tree) ？ 14．什么是稀疏矩阵(sparse matrix) ？ 15．试述链接存储结构的优缺点。 16．什么是A VL树，它与最佳二叉排序树最主要的差别是什么？ 17．什么是假溢出？ 18．什么是排序算法的“稳定性”？ 19．设高度为h的二叉树中只有度为0和度为2的结点，问此类二叉树中的结点数可能达到的最大值和最小值各为多少？ 20．顺序查找、折半查找和分块查找各自的平均查找长度ASL是多少？ 二、单选题 1．顺序表中逻辑上相邻的结点其物理位置也( )。 A．一定相邻B．不必相邻C．按某种规律排列D．无要求 2．下面关于串的叙述中，哪一个是不正确的? ( ) A．串是字符的有限序列C．模式匹配是串的一种重要运算 B．空串是由空格构成的串D．串既可以采用顺序存储，也可以采用链式存储3.某二叉树结点的前序序列为ECBAD，中序序列为EBCDA，则该二叉树结点的后序序列 为( )。 A．ABCED B．DECAB C．DEABC D．BDACE 4. 设二维数组A[m][n] 按列优先顺序存储且每个元素占c个单元，则元素A[i][j] 的地址为()。 A．LOC(A[0][0])+(j*m+i)*c B．LOC(A[0][0])+(i*n+j)*c C．LOC(A[0][0])+[(j-1)*m+i-1]*c D．LOC(A[0][0])+[(i-1)*n+j-1]*c 5.在下述几种排序方法中，不稳定的排序方法是()。 A．直接插入排序B．冒泡排序 C．直接选择排序D．归并排序 6.散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值()。 A．同等概率B．最大概率C．最小概率D．平均概率 7．在有n个结点的顺序表中进行插入、删除运算，平均时间复杂度为( )。 A．Ο(1)B．Ο(n)C．Ο(log2n)D．Ο(n2 ) 8．设s1="abc"，则strlen(s1) = ( )。 A．0 B． 1 C．2 D．3 9. 完全二叉树是下列情况的哪一种( )。 A．一定是满二叉树B．可能是满二叉树 C．一定不是满二叉树D．不是二叉树 10. 下列说法不正确的是( )。 A．图的遍历是从给定的源点出发每个顶点仅被访问一次 B．遍历的基本方法有两种：深度优先遍历和广度优先遍历 C．图的深度遍历不适用于有向图 D．图的深度优先遍历是一个递归过程 11. 数组A[6,7] 的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5,5] 的地址是( )。 A．1165 B．1170 C．1175 D．1180 12. 在下面的排序方法中，其比较次数与待排序记录的初始排列状态无关的是( )。A．直接插入排序B．快速排序 C．直接选择排序D．归并排序数据结构自测题及解答
数据结构模拟卷(含答案)经典习题
数据结构练习题
相关主题
文本预览