数据结构基本复习题答案

1、绪论 ( B ) B）串错误的是 (A) (A) B）散列表 (B) B）串逻辑结构存储结构结点和C）线索二叉树C）顺序表C）线索二叉树、数据和数据的运算。、顶点D）B树D）双链表D）B树。第 1 绪论 ( B ) B）串错误的是 (A) (A) B）散列表 (B) B）串逻辑结构存储结构结点和C）线索二叉树C）顺序表C）线索二叉树、数据和数据的运算。、顶点D）B树D）双链表D）B树。1 自测习题二、选择题1以下数据结构中，属于线性结构的是 A ）有向图2下列与数据元素有关的叙述中A）数据元素是有独立含义的数据最小单位B）数据元素是描述数据的基本单位C）数据元素可以称做结点D）数据元素可以称做

2、记录3以下术语中与数据的存储结构无关的是 A）栈4以下数据结构中，属于线性结构的是 A ）有向图三、填空题1数据结构包括的三方面内容分别是：数据的的2数据元素是数据的基本单位， 在某些情况下也可以称为记录线性结构和5 个特性：输入和链式存储结构时间T（n）=_O(n线性表（B）B）双向链表和循环链表D）单向链表、双向链表和循结构、 树图（网）、 输出 、确定性有穷性 。、 索引。效率和2结构。、线性结构和5 个特性：输入和链式存储结构时间T（n）=_O(n线性表（B）B）双向链表和循环链表D）单向链表、双向链表和循结构、 树图（网）、 输出 、确定性有穷性 。、 索引。效率和2结构。、和空间)

3、散列效_。四种。型4一个正确的算法应该具有可行性5数据的存储结构包括顺序、6一个数据结构在计算机中的映象称为7一个算法的效率主要是指该算法的率。8以下程序段的时间复杂度sum=0; for(i=0 ; in; i+) for( j=0; jlink=p-link-link 2线性表 L=( a 用数组存储。假定删除表中任一元素的概。头 率 相 同 ， 则 删 除 一 个 元 素 平 均 需 要 移 动 的 元 素 个 数 是。头 (n-1)/2 3设有结点定义struct node int data; struct node *next; ; 且已建立如图 2-2 所示的带有头结点的单向链表：

4、data next head 图 2-2 填空题 3 附图函数 sum的功能是：计算链表中各结点数据域之和，作为函数值返回。请填空。int sum(struct node *head) int s=0; struct node *p; p=head-next; do s=s+ p-data ; p=p-next; 栈和队列（B，D）B）6、5、4、3、2、1 D）5、6、3、4、2、1 ）链式存储的线性结构 Dfront 表示，队尾指针用 rear 表示，栈和队列（B，D）B）6、5、4、3、2、1 D）5、6、3、4、2、1 ）链式存储的线性结构 Dfront 表示，队尾指针用 rear 表

5、示，（A）B）front+1=rear B）15 3 7 2 + * - ）限制存取点的非线性结构C） rear+1=frontC）15 3 * 7 2 + return s; 第 3 章3 自测习题二、选择题1有 6 个元素按 6、5、4、3、2、1 的顺序进栈，进栈过程中可以出栈，则以下可能的出栈序列是 A ）1、4、3、5、2、6 C ）3、1、4、2、6、5 2栈和队列都是（ C）A）顺序存储的线性结构 BC）限制存取点的线性结构3设循环队列的队首指针用则判断队空的条件是 A）front=rearD）rear=0 4、设有中缀算术表达式： 15 3 * （7 + 2 ）, 其对应的后缀

6、算术表达式为 （B） A ）15 3 - 7 2 + * 先进先出，其对应的中缀表达。(a+b)-(b+c)/2。自测习题选择题） 10 ） 26 个 C。，其对应的前 先进先出，其对应的中缀表达。(a+b)-(b+c)/2。自测习题选择题） 10 ） 26 个 C。，其对应的前 C ） 11 D） 27 个 D） 12 ）28个三、填空题1队列是限制插入只能在表的一端， 而删除在表的另一端进行的线性表，其操作特点是2设有一个空栈， 栈顶指针值为 100，现有输入序列为 1，2，3，4，5，经过操作序列： Push、Pop、Push、Push、Pop、Push、Push、Pop后，现在已出栈的

7、序列是 1 、3、5，栈顶指针是 102 。3设有后缀算术表达式： 2 x y + * 3 y - /式为 2*(x+y)/(3-y) 4已知一算术表达式的中缀形式为：缀表达式形式应为 -+ab/+bc2 第 4 章 串4.1一1设有一个字符串 S=“ABC 123 XYZ”，问该串的长度为（ C）A） 9 B2设有一个字符串 S=”windows”，其子串的数目是 (29个) A） 25 个 B(D) ） 串可以顺序存储 D） 数据元素是一个字符 。填空题已知串 S=”abaabccd(D) ） 串可以顺序存储 D） 数据元素是一个字符 。填空题已知串 S=”abaabccd”，求该串 S

8、的子串运算结果，两个串相等的充分必要条件是不仅两个串的长度相等，而不含任何字符的串称为空串，其长度为只含有空格字符的串称为选择题设有二维数组 A09 , 0 19 ，其每个元素占个字100，那）284 C0。空格，其长度为串中空格符）402 D）444 A） 串中允许有空串 BC） 串可以链式存储二SubStr( “abaabccd”, 4, 3)=abc，SubStr( “abaabccd”, 5, 0)= 。且各个位置上对应的字符也要相等。的个数。第 5章 数组与广义表5 自测习题一节，数组按行优先顺序存储，第一个元素的存储地址为么元素 A8,12 的存储地址为 (D) A）262 B设有

9、一个 10阶的对称矩阵， 采用压缩存储方式， 以行优先1175）17 填空题设有二维数组 A1010 ，其每个元素占个字节设有一个 10阶的对称矩阵， 采用压缩存储方式， 以行优先1175）17 填空题设有二维数组 A1010 ，其每个元素占个字节， 数组按列100，那么元素 A6,6设有广义表 A=(x, (a, b), (x, (a, b), y)选择题A）3 Cm个，度结点有 n 个，则该二）2*m+n C1，且每个元素占 1）33 ，则广义表）4 ）m+2*n D）m+2*n+1 ）23 D）5 顺序存储， a 为第一个元素，其存储地址为个地址空间，则 a 的地址为 (A) ）26 二

10、优先顺序存储， 第一个元素的存储地址为的存储地址为 232。 (下标从 0 开始) A的长度为 2，深度为 4。第 6 章 树6 自测习题三.1. 如果结点 A是结点 B的双亲，而且结点有个兄弟，则结点的度是(D) A）2 B2. 设有一棵二叉树，其度结点有叉树的结点总数为 (D) A）m+n BABCDEFG，中序遍历序列(A) ）CDFGBEA C ）CDBAFGE D ）12 CA、B、C、D和 E，每个字母在电文中出C）110 EFHIGJK，中序遍历序列为(G) B）F B一定是 C的(A) ABCDEFG，中序遍历序列(A) ）CDFGBEA C ）CDBAFGE D ）12 CA

11、、B、C、D和 E，每个字母在电文中出C）110 EFHIGJK，中序遍历序列为(G) B）F B一定是 C的(A) B填空题）26 C）111 DC）G ）后继 C D）25）1111 ）相邻结点 D）是：CBDAFEG，则该二叉树的后序遍历序列是A）CDBFGEA BCDBFEGA 4. 设有 13 个值，由它们组成一棵哈夫曼树，则该哈夫曼树中结点个数共有 (D)。A）13 B5. 设电文中出现的字母为现的次数分别为： 6，23，3，5和 12，按哈夫曼编码，则字母的编码应是 (C) (D) A）10 B6. 已知一棵二叉树的先序遍历序列为HFIEJGK，则该二叉树根的右子树的根是A）E

12、D）J 7. 设结点 A有左孩子结点 B，右孩子结点 C，则在先序遍历、中序遍历、后序遍历这三种基本遍历序列中A）前驱不相邻结点四.n 个结点的二叉树中，一共有个指针域为空。i 层上最多有k 的且恰好有 -1个结点的；如该结点有右孩子，则。m，则左、右子树都非空的结点个数是2in 个结点的二叉树中，一共有个指针域为空。i 层上最多有k 的且恰好有 -1个结点的；如该结点有右孩子，则。m，则左、右子树都非空的结点个数是2i2m-11k个结点。2n 个指针域，其中 n+1 2. 一棵非空的二叉树，其第3. 满二叉树是一棵深度为二叉树。4. 将一棵完全二叉树按层次编号， 对任一编号为 i 的结点有：

13、如该结点有左孩子，则其编号为 2i 其编号为 2i+1 5. 设一棵二叉树中只有叶子结点和左、 右子树都非空的结点， 如果叶子结点的个数是6. 设有一棵树（如图 6-5 所示），请回答下列问题：根结点是 A；叶子结点有D H I J F K ；的双亲是B；的祖先是 C A；的孩子是 K；的孩子是无；的子孙有 H I J；的兄弟是 E；的兄弟是 C；结点的层数是 4；树的深度是 4；为根的子树深度是 2；这棵树的度是 3。，写出该表达式的波兰式图（A）V3V6V7）V1 V2 V4 V5 V8 V3 V6 V7 C）图 6-5 填空题 6的附图，写出该表达式的波兰式图（A）V3V6V7）V1 V

14、2 V4 V5 V8 V3 V6 V7 C）7. 现有一表达式 ( a+b )*c-d / e-*+abc/de ，以及逆波兰式 ab+c*de/- 。第 7 章7 自测习题二、选择题1 对如图 7-4 所示的无向图 G，若从顶点 V1开始，按深度优先搜索法进行遍历，则可能的访问顺序为V1V2V5V4V8图7-4 选择题1的附图A）V1 V2 V4 V8 V5 V6 V3 V7 B ）V1 V2 V3 V4 V5 V6 V7 V8 C）V1 V2 V3 V4 V8 V5 V6 V7 D2 对如图 7-5 所示的无向图 G，若从顶点 V1开始，按广度优先搜索法进行遍历，则可能的访问顺序为（V6V

15、4V7B）V1 V2 V6 V3 V4 V5 V7 V8 D）V1 V2 V6 V3 V5 V4 V7 V8 B）B）2 倍 n-1 n 2 倍。 1 V6V4V7B）V1 V2 V6 V3 V4 V5 V7 V8 D）V1 V2 V6 V3 V5 V4 V7 V8 B）B）2 倍 n-1 n 2 倍。 1 倍。V8C）1/2 倍2D）不确定V2V3V5图7-5 选择题2的附图A）V1 V2 V3 V4 V5 V6 V7 V8 C）V1 V2 V6 V3 V4 V7 V8 V53 在一个无向图中，所有顶点的度数之和等于所有边数的（A）1 倍三、填空题1有 n 个顶点的无向连通图至少有 n-1

16、条边，有 n 个顶点的有向强连通图至少有 n 条弧。2在一个有 n 个顶点的无向图中，要连通所有顶点，至少需要条边。3用邻接矩阵表示无向图时， 若图中有 n=500个顶点，m=500条边，则形成的邻接矩阵共有 25000 个元素，其中 1000 个非零元素。4有 n 个顶点的无向图的邻接矩阵是对称的，因而只需存储( +n)/2 条边即可。5在一个有向图中，所有顶点的度数之和等于图中弧数的在一个有向图中，所有顶点的出度之和等于图中弧数的6对一个有 n 个顶点和 e 条边的连通图， 其生成树的顶点数和边数该行所对应的，一列中非零元素的个数表示。查找D B）以链式方式存储， 且元素已按值排好C）以链

17、式方式存储016 ，散列函数为 H1(K)=K % 17，采用线26，25，72，38，8，18，59 依12 的有序表中查找一个元素时，查该列所对应的顶点的D）以顺序方式存储，且元素分别为该行所对应的，一列中非零元素的个数表示。查找D B）以链式方式存储， 且元素已按值排好C）以链式方式存储016 ，散列函数为 H1(K)=K % 17，采用线26，25，72，38，8，18，59 依12 的有序表中查找一个元素时，查该列所对应的顶点的D）以顺序方式存储，且元素7无向图的邻接矩阵中一行中非零元素的个数表示顶点的度度第 8 章三、选择题1使用折半查找，线性表必须A）以顺序方式存储序已按值排好序

18、2散列表的地址区间为性探测法解决冲突，将关键字序列次存储到散列表中（1）元素 59存放在散列表中的地址为 ( D ) A）8 B ）9 C ） 10 D）11（2）查找元素 59，需要比较的次数为 (C ) A）2 B ）3 C） 4 D ）5 四、填空题1采用折半查找算法在长度为找成功的平均查找长度为 _37/12_ 。排序(B) B）归并排序(C ) ）数据元素的个数）关键字值的最大值）2，1，3，4，5 ）5，3，1，2，4 ）4，3，1，7，6，5，2 D）1，2，3，4，5，6，7 4，1，2，3 ，应用一种排序方法进 C）快速排序排序(B) B）归并排序(C ) ）数据元素的个数）关键字值的最大值）2，1，3，4，5 ）5，3，1，2，4 ）4，3，1，7，6，5，2 D）1，2，3，4，5，6，7 4，1，2，3 ，应用一种排序方法进 C）快速排序 D ）找算法依次搜索 20、43、56时，查找长度分别为 4 1 3 。第 9 章二、选择题1下列排序方法中，哪一种是稳定的排序方法：A）选择排序希尔排序2快速排序 每次划分的效果好坏和以下何种因素有直接关系：A）关键字的排列情况 BC）轴的相对大小 D3对以下几个关键字序列进行 快速排序 ，以第一个元素为轴，一次划分效果最好 的是：( c) A）1，2，3，4，5 BC）3，1，2，4， D4对以下几个关键字序列进行