一．选择题：
1． 若长度为n的线性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动___个数据元素。(a)
2. 在单链表中，已知q指的结点是p指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行b)
a. q->next=p; s->next=p
b. s->next=p; q->next=s;
c. p->next=s; s->next=q;
d. s->next=q; q->next=p;
3. 某堆栈的输入序列为a,b,c,d,下面的四个序列中不可能是它的输出序列。(c)
4. 在一棵树中，__没有前驱结点。(c)
a. 分支结点 b. 叶结点 c. 树根结点 d. 空结点。
5. 一棵深度为8（根的层次号为1）的满二叉树共有___个结点。(b)
a. 256 b. 255 c. 128 d. 127
6. 下面二叉树的中序遍历序列为a)
a. dbeafc
b. debfca
c. bdeacf
d. abcdef
7. 连通图g有n个顶点，图的生成树有___条边。(b)
a. n b. n-1 c. n(n-1)/2 d. (n+1)/2
8. 在有向图中每个顶点的度等于该顶点的c)
a. 入度 b. 出度 c. 入度与出度之和 d. 入度与出度之差。
9. 设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为b）
a．o（nlog2e） b．o（n+e）c．o(ne) d．o(n2)
10. 一个对象序列的排序码为，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为___c）a．c．
二．填空题：
1. 已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为loc(a1)，那么，loc(ai)=_loc(a1)+(i-1)*k___
2. 若一棵二叉树有10个叶结点，则该二叉树中度为2的结的点个数为___9___
3. 具有n个结点的非空二叉排序树的最小深度为。
4. 广义表（（a,b,c,d））的表尾是___d___
5. 一个不带有权的无向图采用邻接矩阵存储方法，其邻接是一个___矩阵。
6. 二维数组是一种非线性结构，其中的每一个数组元素最多有___个直接前驱（或直接后继）。
7. 链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的___域的值。
8. 在一个链式栈中，若栈顶指针等于null则为___
9. 由树转化成二叉树，其根的右孩子指针。
10. 设带权有向图g的邻接矩阵为a，若图中不存在弧，则a[i,j]的值为。
三．判断题：
1. 数组是一种没有插入与删除操作的线性结构。(
2. 稀疏矩阵中值为0的元素分布有规律，因此可以采用三元组方法进行压缩存储。(
3. 空串与由空格组成的串没有区别。(
4. 完全二叉树就是满二叉树。(
5. 有向图是一种非线性结构。(
6. 带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。(
7. aoe 网是一种带权的无环连通图。(
8. 一个广义表的表尾总是一个广义表。(
9. 存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。(
10. 对于有n个对象的待排序序列进行归并排序，所需平均时间为o（nlog2n）。(
数据结构练习题(二)
一．选择题：
1． 在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为。
a n b n/2 c (n+1)/2 d (n-1)/2
2. 下面关于图的存储的叙述中，哪一个是正确的。 （
a．用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关
b．用邻接矩阵法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关。
c．用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。
d．用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关。
3． 栈的插入和删除操作在___进行。（
a 栈顶 b 栈底 c 任意位置 d 指定位置。
4． 由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为。
a 24 b 73 c 48d 53
5． 若**性表中采用折半查找法查找元素，该线性表应该。
a．元素按值有序 b．采用顺序存储结构。
c．元素按值有序，且采用顺序存储结构。
d．元素按值有序，且采用链式存储结构。
6． 对二叉排序树进行遍历，可以得到该二叉树所有结点构成的排序序列。(
a. 前序 b．中序 c．后序 d．按层次。
7． 具有n个顶点的有向图最多有条边。(
a．n b．n(n-1) c. n(n+1) d. 2n
8. 线性表是。
a.一个以上的元素构成的序列。
b.一个以上的元素构成的集合。
c.任意个有限元素构成的集合。
d.任意个有限元素构成的序列。
9． 串的下列存储结构中，最节省空间的是。
a.紧缩格式的顺序存储方式。
b.非紧缩格式的顺序存储方式。
c.结点大小为1的链式存储方式。
d.自定义结点大小的链式存储方式。
10．若二叉树采用二叉链表存储结构，要交换其所有分支结点左右子树的位置，利用( )遍历方法最合适。
a．前序 b．中序 c．后序 d．按层次。
二．填空题：
1．稀疏矩阵一般的压缩存储方法有两种，即三元组和___
2．主程序第一次调用递归函数被称为外部调用，递归函数自己调用自己被称为内部调用，它们都需要利用栈保存调用后的___地址。
3．在一棵树中，__结点没有后继结点。
4．广义表（（a,b,c,d））的表尾是。
5．在具有n个单元的循环队列中，队满时共有___个元素。
6．在一棵二叉树中有n0个叶结点，有n2个度为2的结点，则n0
7．在以head为表头指针的带表头结点的单链表中，判断链表为空的条件为。
8．n个顶点的连通图用邻接矩阵表示时，该矩阵至少有___个非零元素。
9．数据的逻辑结构被分为和非线性结构两种。
10. 抽象数据类型的最重要的特点是___和信息隐蔽。
三．判断题：
1． 由树转化成二叉树，其根的右孩子指针域为空。(
2． 完全二叉树可以是满二叉树。(
3． 有向图不是一种非线性结构。(
4． 非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。(
5． 深度为h的非空二叉树的第i层最多有2 h-1 个结点。(
6． 给定aoe网的关键路径是唯一的。(
7． 链式存储在插入和删除时需要保持物理存储空间的顺序分配，不需要保持数据元素之间的逻辑顺序。(
8． 一个广义表的表头总是一个广义表。(
9． 数据的基本单位是数据项。(
10. 栈和队列都是运算受限的线性结构。(
数据结构练习题(三)
一．选择题：
1．采用顺序查找方法查找长度为n的线性表，不成功时平均查找长度为。(
c.(n+1)/2 d.(n-1)/2
2. 具有65个结点的完全二叉树的高度为。（
a．8 b．7 c．6 d．5
3. 在一个无向图中，所有顶点的度数之和等于所有边数的（ ）倍。
a．3 b．2 c．1 d．1/2
4. 线性链表不具有的特点是（ ）
a．随机访问 b．不必事先估计所需存储空间大小。
c．插入与删除时不必移动元素 d．所需空间与线性表长度成正比。
5. 向顺序栈中压入新元素时，应当（ ）
a．先移动栈顶指针，再存入元素 b．先存入元素，再移动栈顶指针。
c．先后次序无关紧要d．同时进行。
6. 在一棵二叉树的二叉链表中，空指针域数等于非空指针域数加。
a. 2b. 1c. 0d. –1
7. 具有6个顶点的无向图至少应该有___条边才能确保是一个连通图。（
a.8b. 7c. 6d. 5
8. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为（ ）排序法。
a．插入 b．选择 c．希尔 d．二路归并。
9．按逐点插入法建立对应于序列(54，28，16，34，73，62，95，60，26，43)的二叉排序树后，查找62要进行___次比较。（
数据结构练习
第1章。1.从逻辑上可以把数据结构分为。a 动态结构 静态结构 b 顺序结构 链式结构。c.线性结构 非线性结构 d 初等结构 构造型结构。2.关于算法的描述，不正确的是。a.算法最终必须由计算机程序实现。b 所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界。c.健壮的算法不会因非法的输人数...
数据结构练习
一 选择题。1 广度优先遍历的含义是 从图中某个顶点v出发，在访问了v之后依次访问v的各个未被访问过的邻接点，然后分别从这些邻接点出发依次访问它们的邻接点，且 先被访问的顶点的邻接点 先于 后被访问的顶点的邻接点 被访问，直至图中所有已被访问的顶点的邻接点都被访问到是下图的广度优先遍历序列。a.1 ...
数据结构练习
1 数据结构中，与所使用的计算机无关的是。a.存储结构 b.物理结构 c.逻辑结构 d.物理和存储结构。2 在存储数据时，通常不仅要存储各数据元素的值，还要存储。a 数据的处理方法b 数据元素的类型。c 数据元素之间的关系 d 数据的存储方法。3 算法分析的目的。4 如果对线性表的操作只有两种，即删...