发布时间 : 星期三 文章数据结构复习题答案修订版更新完毕开始阅读
一、填空题
1、根据需要，数据元素又被称为__ 元素 _、_ 结点 _、__ 顶点 _或 记录 。
2、在一棵二叉搜索树中，每个分支结点的左子树上所有结点的值一定 小于 该结点的值，右子树上所有结点的值一定 大于 该结点的值。
3、通常从 正确性 、 可读性 、 健壮性 、 高效性 等几方面评价算法的(包括程序)质量。
4、假定一棵二叉树的结点数为18，则它的最小深度为 5 ，最大深度为 18 。 5、顺序存储结构是通过 物理上相邻 表示元素之间的关系的;链式存储结构是通过 指针 表示元素之间的关系的。
6、在线性结构中,第一个结点 无 前驱结点,其余每个结点有且只有 1 个前驱结点；最后一个结点 无 后续结点,其余每个结点有且只有 1 个后续结点。 7、在树形结构中，树根结点没有 前驱 结点，每一个结点只有一个 前驱 结点，称为 根结点 。
8、栈是 操作受限 的线性表，其运算遵循 后进先出 的原则。 9、哈夫曼树是带权路径度 长度最短 的树，通常权值较大的结点离根 较近 。 10、从数据结构的观点看，通常所说的\数据\应分成三个不同的层次，即数据 、 数据元素和 数据项。
11、一个运算的实现是指一个完成该运算功能的 程序 。运算实现的核心是处理步骤的规定，即 算法设计 。
12、线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接 前驱 外，其他结点有且仅有一个直接 前驱 ;除终端结点没有直接 后续 外，其它结点有且仅有一个直接 后续 。
13、顺序表的特点是 表中相邻的数据元素在内存中存储位置也相邻 。
14、栈的基本运算至少应包括 初始化 、进栈 、出栈、与 读栈 、判栈空五种。 15、从有序表(12，18，30，43，56，78，82，95)中依次二分查找43和56元素时，其查找长度分别为 1 和 3 。
16、对于顺序栈而言，在栈满状态下，如果此时在作进栈运算，则会发生“ 上溢 ”。 17、深度为k(k>=1)的二叉树至多有 2^k-1 个结点。 18、结点最少的树为 只有一个结点 ，结点最少的二叉树为 空二叉树 。
19、常见时间复杂性的量级有：常数阶O( 1 )、对数阶O( log2n )、线性阶O ( n )、平方阶O( n^2 )、和指数阶O( 2^n )。
20、数据结构的三要素是指 数据元素、 逻辑结构 和 存储结构 。 21、二叉树由 根结点， 左子树 ， 右子树 三个基本单元组成。 22、向栈中压入元素的操作是先 存入元素 ，后 移动栈顶指针 。
23、一棵有n个结点的满二叉树有 0 个度为1的结点、有（n-1）/2 个分支 （非 终端）结点和 （n+1）/2 个叶子，该满二叉树的深度为? log2(n) ?+1。 24、通常从四个方面评价算法的质量：正确性、易读性、强壮性和高效性。
25、一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为o（n）。 26、假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为9个，树的深度为3，树的度为3。
27、后缀算式9 2 3 +- 10 2 / -的值为-1。中缀算式（3+4X）-2Y/3对应的后缀算式为3 4 X * + 2 Y * 3 / -。
28、若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指针。在这种存储结构中，n个结点的二叉树共有2n个指针域，其中有n-1个指针域是存放了地址，有n+1个指针是空指针。
29、对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点分别有e个和2e个。
30、AOV网是一种有向无回路的图。
31、在一个具有n个顶点的无向完全图中，包含有n*（n-1）/2条边，在一个具有n个顶点的有向完全图中，包含有n*（n-1)条边。
32、在快速排序、堆排序、归并排序中，归并排序是稳定的。 二、选择题
1、关于逻辑结构，以下说法错误的是 ( B )
A.逻辑结构与数据元素本身的形成、内容无关 B.逻辑结构与数据元素的相对位置有关 C.逻辑结构与所含结点个数无关
D.一些表面上很不相同的数据可以有相同的逻辑结构
2、对于单链表表示法，以下说法错误的是 （ C ） A.数据域用于存储线性表的一个数据元素
B.指针域或链域用于存放一个指向本结点所含数据元素的直接后继所在结点的指针 C.所有数据通过指针的链接而组织成单链表
D.NULL称为空指针，它不指向任何结点，只起标志作用 3、单链表中，增加头结点的目的是为了 ( C )
A.使单链表至少有一个结点 B.标示表结点中首结点的位置
C.方便运算的实现 D.说明单链表是线性表的链式存储实现 4、线性表若采用链表存储结构时，要求内存中可用存储单元的地址 ( D )
A.必需是联系的 B.部分地址必须是连续的 C.一定是不连续的 D.连续不连续都可以
5、如果以链表作为栈的存储结构,则退栈操作时 ( C )
A.必须判别栈是否满 B.判别栈元素的类型 C.必须判别栈是否空 D. 队栈不做任何判别 6、深度为6的二叉树最多有( B )个结点
A.64 B.63 C.32 D.31
7、 设一个栈的输入序列是 1，2，3，4，5,则下列序列中，是栈的合法输出序列的是 D。
A. 5 1 2 3 4 B. 4 5 1 3 2 C. 4 3 1 2 5 D. 3 2 1 5 4 8、循环链表主要优点是 （ D ）
A.不再需要头指针了
B.已知某个结点的位置后，能够容易找到它的直接前趋 C.在进行插入、删除运算时，能更好地保证链表不断开 D.从表中任一结点出发都能扫描到整个链表 9、下面关于线性表的叙述正确的是 ( A )
A.线性表采用顺序存储，必须占用一片连续的存储单元 B.线性表采用顺序存储，便于进行插人和删除操作 C.线性表采用链接存储，不必占用一片连续的存储单元 D.线性表采用链接存储，不便于插人和删除操作 10、带头结点的单链表Head为空的判定条件是 ( B )
A.Head=Null B.Head->next=NULL C.Head->next=Head 11、以下说法错误的是 （ D ）
A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B.在三叉链表上，二叉树的求双亲运算很容易实现 C.在二叉链表上，求根，求左、右孩子等很容易实现 D.在二叉链表上，求双亲运算的时间性能很好 12、以下说法错误的是 ( B )
A.用数字式计算机解决问题的实质是对数据的加工处理
B.程序设计的实质是数据处理
C.数据的逻辑结构是数据的组织形式，基本运算规定了数据的基本操作方式 D.运算实现是完成运算功能的算法，或这些算法的设计
13、对于数据结构课程的主要内容，以下解释正确的是 （ C ） A.数据结构的定义，包括逻辑结构、存储结构和基本运算集 B.数据结构的实现，包括存储实现、运算实现和基本运算集
C.数据结构的评价和选择，包括逻辑结构的选择、基本运算集的选择和存储选择 14、一般地，一个存储结构包括以下三个主要部分。以下说法错误的是 ( A ) A．存储结点每个存储结点可以存放一个或一个以上的数据元素 B.数据元素之间关联方式的表示 也就是逻辑结构的机内表示 C.附加设施，如为便于运算实现而设置的“哑结点”等等 15、顺序存储结构 （ C ）
A.仅适合于静态查找表的存储 B.仅适合于动态查找表的存储 C.既适合静态又适合动态查找表的存储 D.既不适合静态又不适合动态查找表的存储 16、线性结构中的一个结点代表一个 （ A ）
A. 数据元素 B. 数据项 C. 数据 D. 数据结构 17、与数据元素本身的形式、内容、相对位置、个数无关的是数据的 （ C ）
A存储结构 B.存储实现 C.逻辑结构 D.运算实现
18、以下说法错误的是 （ D ）
A.所谓数据的逻辑结构指的是数据元素之间的逻辑关系的整体
B.数据的逻辑结构是指各数据元素之间的逻辑关系，是用户按使用需要而建立的 C.数据结构、数据元素、数据项在计算机中的映象分别称为存储结构、结点、数据域 D.数据项是数据的基本单位
19、对顺序表上的插入算法的时间复杂性分析来说，通常以（B ）为标准操作 A.条件判断 B.结点移动 C.算术表达式 D.赋值语句 20、单链表的一个存储结点包含 （ D ）
A.数据域或指针域 B.指针域或链域 C.指针域和链域 D.数据域和链域 21、在一棵高度为k的满二叉树中，结点总数为 C A．2k-1 B．2k C．2k-1 D．?log2k?+1
22、在完全二叉树中，若一个结点是叶结点，则它没 C 。 A．左子结点 B．右子结点 C．左子结点和右子结点
D．左子结点，右子结点和兄弟结点
23、下面哪一方法可以判断出一个有向图是否有环回路. B
A．广度优先遍历 B. 拓扑排序 C. 求最短路径 D. 求关键路径 24、判定一个栈ST（最多元素为m0）为空的条件是 B
A．ST->top<>0 B．ST->top=0 C．ST->top<>m0 D．ST->top=m0 25、具有n(n>0)个结点的完全二叉树的深度为 C 。
A. ?log2(n)? B. ? log2(n)? C. ? log2(n) ?+1 D. ?log2(n)+1? 26、任何一个无向连通图的最小生成树 B
A．只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在 27、在数据结构中，从逻辑上可以把数据结构分成 C
A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 线性结构和非线性结构 D. 内部结构和外部结构 28、线性表采用链式存储结构时，其地址 D 。
A. 必须是连续的 B. 部分地址必须是连续的 C. 一定是不连续的 D. 连续与否均可以
29、在单链表指针为p的结点之后插入指针为s的结点，正确的操作是： B
A．p->next=s；s->next=p->next; B． s->next=p->next；p->next=s; C．p->next=s；p->next=s->next; D． p->next=s->next；p->next=s;
30、如果以链表作为栈的存储结构，则退栈操作是 （ B ） A.必须判别栈是否满 B.必须判别栈是否空 C.判别栈元素的类型 D.对栈不做任何操作 31、栈和队列的共同特点是( A )。
A.只允许在端点处插入和删除元素 B.都是先进后出