Question

帮看下数据结构的一些选择题 判断题 填空题 写出题号和答案 能写解析的就写点解析 不然看不懂 急需！！！

老师给的考试复习题的看不懂部分，没给答案，求解析。。。。。会多少写多少吧，感激不尽！！！不多
选择//写下解析

6、若线性表最常用的操作是在最后1个元素之后插一个元素和删除第一个元素，则采用(D)存储方法最节省时间。
A双链表 B带头指针的单循环链表
C单链表 D带尾指针的单循环链表
16、节点前序为 xyz的二叉树有( )不同状态
A .3 B. 4 C.5 D.6

判断
1、基于某种逻辑结构之上的基本操作其实现是唯一的()
2、线性结构的基本特征：每个元素必有一个直接前驱和一个直接后继。()
3、若线性表的总长度基本稳定，且很少进行插入和删除，但要求以最快的
速度读取元素，则采用顺序结构较好。()
4、对待矩阵只需存放包括主对角元素在内的下（或上）三角的元素。()
5、空串和空格串是相同的。()
6、稀疏矩阵十大量值为0的元素分布没有规律，所以可采用三元组表法存储()
7、哈夫曼树实际是给定一组确定权值的叶子节点构造出来的二叉树中带
权路径长度最短的二叉树。()
8、用一维数组存储完全二叉树时容易产生空间的浪费。()
9、用邻接矩阵存储图，所占存储空间大小与顶点数有关而与边数无关。()
10、顺序查拭技术适合于顺序存储结构或者链式存储结构。()

填空 //写下算法
1、一个顺序存储的基本线性表，设每个节点占m个存储单元，第一个节点的
地址为d1，则第i个节点的地址为_______。
2、设有个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址是d，每个元素占1个地址空间，则元素A[8][5]的存储地址为____。
5、已知无向图G的顶点数为n，边数为e，其邻接表的空间复杂度为____。

Answer 1

6、若线性表最常用的操作是在最后1个元素之后插一个元素和删除第一个元素，则采用(D)存储方法最节省时间。
A双链表 B带头指针的单循环链表
C单链表 D带尾指针的单循环链表
的确是D正确

16、节点前序为 xyz的二叉树有( )不同状态
A .3 B. 4 C.5 D.6
这个是C，5种

判断
1、基于某种逻辑结构之上的基本操作其实现是唯一的()
错误，存储结构不同，实现也不同

2、线性结构的基本特征：每个元素必有一个直接前驱和一个直接后继。()
错误，至多一前一后

3、若线性表的总长度基本稳定，且很少进行插入和删除，但要求以最快的
速度读取元素，则采用顺序结构较好。()
正确

4、对待矩阵只需存放包括主对角元素在内的下（或上）三角的元素。()
对称矩阵吧，答案正确

5、空串和空格串是相同的。()
错，空串没字符

6、稀疏矩阵十大量值为0的元素分布没有规律，所以可采用三元组表法存储()
错，非0元素

7、哈夫曼树实际是给定一组确定权值的叶子节点构造出来的二叉树中带
权路径长度最短的二叉树。()
正确

8、用一维数组存储完全二叉树时容易产生空间的浪费。()
错误，没有浪费

9、用邻接矩阵存储图，所占存储空间大小与顶点数有关而与边数无关。()
正确，顶点数平方

10、顺序查拭技术适合于顺序存储结构或者链式存储结构。()
顺序查找吧，正确

填空 //写下算法
1、一个顺序存储的基本线性表，设每个节点占m个存储单元，第一个节点的
地址为d1，则第i个节点的地址为_______。
d1 + (i - 1) *m

2、设有个10阶的对称矩阵A采用压缩存储，A[0][0]为第一个元素，其存储地址是d，每个元素占1个地址空间，则元素A[8][5]的存储地址为____。
d + 8 * (8 + 1) / 2 + 5 = d + 41

5、已知无向图G的顶点数为n，边数为e，其邻接表的空间复杂度为____。
O(n+e)

追问

能解释一下上面2个选择题的过程吗，我不明白原理

能解释一下上面2个选择题的过程吗，我不明白原理

追答

6：在最后1个元素之后插一个元素和删除第一个元素

尾指针的单循环其尾结点后继域指针指向表头，因此可以完成
虽然双循环链表也可以，考虑到双循环链表用的空间超过尾指针的单循环，相对而言要存储密度小些，但是题目中说的是双链表，并不能保证循环，如果不循环，依然和单链表一样得从头开始
16：这个3个结点二叉树的形态就是5种，参见教科书的二叉树计数内容

追问

既然是在最后1个元素之后插一个元素和删除第一个元素，为什么单链表和双链表不好呢，单，双链表不能直接找到最后1个元素吗？那带头结点的单循环链表和带尾结点的单循环链表有什么区别，带尾结点比带头结点好在哪里？

追答

单链表和双链表都只有表头指针，找到表尾要从头开始啊！
哪里有什么带尾结点的，是带尾结点指针！这样才能直接访问到尾结点啊