Question

数据结构练习题！求答案！

一．选择题：
1． 若长度为n的线性表采用顺序存储结构，删除它的第i数据元素之前，需要先依次向前移动_______个数据元素。( D )
A.n-i B.n+i C.n-i-1 D.n-i+1
2. 在单链表中，已知q指的结点是p指的结点的直接前驱结点，若在q和p指的结点之间插入一个由s指的结点，则需执行________。( C)
q->next=p; s->next=p
s->next=p; q->next=s;
p->next=s; s->next=q;
s->next=q; q->next=p;
3. 某堆栈的输入序列为a,b,c,d,下面的四个序列中，__________不可能是它的输出序列。( A )
A.a,c,b,d B.b,c,d,a C.d,c,a,b D.c,d,b,a
4. 在一棵树中，_______没有前驱结点。( B )
A. 分支结点 B. 叶结点 C. 树根结点 D. 空结点
5. 一棵深度为8（根的层次号为1）的满二叉树共有______个结点。( )
A. 256 B. 255 C. 128 D. 127
6. 下面二叉树的中序遍历序列为________。( )
A. DBEAFC
B. DEBFCA
C. BDEACF
D. ABCDEF
7. 连通图G有n个顶点,图的生成树有______条边。( )
A. n B. n-1 C. n(n-1)/2 D. (n+1)/2
8. 在有向图中每个顶点的度等于该顶点的________。( )
A. 入度 B. 出度 C. 入度与出度之和 D. 入度与出度之差
9. 设有向图有n个顶点和e条边，采用邻接表作为其存储表示，在进行拓扑排序时，总的计算时间为________。（ ）
A．O（nlog2e） B．O（n+e）C．O(ne) D．O(n2)
10. 一个对象序列的排序码为{46，79，56，38，40，84}，采用快速排序以位于最左位置的对象为基准而得到的第一次划分结果为_______。（ ）
A．{38，46，79，56，40，84} B．{38，79，56，46，40，84}
C．{40，38，46，56，79，84} D．{38，46，56，79，40，84}

二．填空题：
1. 已知具有n个元素的一维数组采用顺序存储结构，每个元素占k个存储单元，第一个元素的地址为LOC(a1)，那么，LOC(ai)=__________。
2. 若一棵二叉树有10个叶结点，则该二叉树中度为2的结的点个数为_________。
3. 具有n个结点的非空二叉排序树的最小深度为__________。
4. 广义表（（a,b,c,d））的表尾是_________。
5. 一个不带有权的无向图采用邻接矩阵存储方法，其邻接是一个_____矩阵。
6. 二维数组是一种非线性结构，其中的每一个数组元素最多有_________个直接前驱（或直接后继）。
7. 链表对于数据元素的插入和删除不需移动结点，只需改变相关结点的________域的值。
8. 在一个链式栈中，若栈顶指针等于NULL则为________。
9. 由树转化成二叉树，其根的右孩子指针_________。
10. 设带权有向图G的邻接矩阵为A，若图中不存在弧<vi,vj>,则A[i,j]的值为___________。

三．判断题：
数组是一种没有插入与删除操作的线性结构。( )
稀疏矩阵中值为0的元素分布有规律，因此可以采用三元组方法进行压缩存储。( )
空串与由空格组成的串没有区别。( )
完全二叉树就是满二叉树。( )
有向图是一种非线性结构。( )
带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。( )
AOE 网是一种带权的无环连通图。( )
一个广义表的表尾总是一个广义表。( )
存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。( )
对于有n个对象的待排序序列进行归并排序，所需平均时间为O（nlog2n）。( )

最好发到我的邮箱！331872411@qq.com

Answer 1

一．选择题：
1． A 这个题目你是不是写的不完整啊
要是：删除它的第i数据元素 ，需要移动？个的话 你的答案错了。例如：删除第一个，移动N-1个；删除第二个，移动N-2个 ----以此类推 删除第n-1个移动1个 删除第n个移动0 个

要是：删除它的第i数据元素之前的元素，同理 就会选D

2. B 你的答案错了，这个题的答案是 B ,注意：题目是 q是p的前驱
3. C 你的答案错了这个题的答案是C， C.d,c,a,b 栈是先进后出 d一个出 说明c ,b,a都还在栈中 而出的序列 只能是c ,b,a
4.C 你的答案错了，这个题的答案是 C 只有根结点没有直接前驱
5. C 给你一个公式： 一棵深度为H（根的层次号为1）的满二叉树共有_2^H-1_____个结点.推到过程：第i层结点数目为：2^(i-1) i取值 从1到树深h，所以，每层的结点数目相加 就是树的总节点数 ，利用等比公式 得到上面给你的公式。
6. 这个没有图啊：
下面二叉树的中序遍历序列为________。( )
A. DBEAFC
B. DEBFCA
C. BDEACF
D. ABCDEF
7. C 因为题目说是联通同 因此是无向图 所以C
8. C
9. B 拓扑排序就是对边和顶点操作 所以与边和顶点的个数相关
10. B
二．填空题：
1.LOC(ai)=__LOC(a1)+(i-1)*k________。
2. 9 （n0=n2+1）
3. log2(n+1)
4. （a,b,c,d）
5. 对称
6. 2
7. 指针
8. 栈空
9. 变成兄弟结点
10.0
三．判断题：
数组是一种没有插入与删除操作的线性结构。(错 )
稀 疏矩阵中值为0的元素分布有规律，因此可以采用三元组方法进行压缩存储。(错 )
空串与由空格组成的串没有区别。( 错 )
完全二叉树就是满二叉树。( 错)
有向图是一种非线性结构。(对 )
带权连通图的最小生成树的权值之和一定小于它的其它生成树的权值之和。( 对 )
AOE 网是一种带权的无环连通图。( 对 )
一个广义表的表尾总是一个广义表。( 错 )
存储图的邻接矩阵中，邻接矩阵的大小不但与图的顶点个数有关，而且与图的边数也有关。( 对 )
对于有n个对象的待排序序列进行归并排序，所需平均时间为O（nlog2n）。( 对 )

已发送 查收吧