数据结构易错100题_设一组权值集合15 3 14 2 6 9

1. 链表的物理存储结构具有同链表一样的顺序（）。
   答案：正确。
   物理存储结构不连续。

2. 已知某二叉树的前序为（1 - 2 - 3 - 4 - 5 - 6 - 7 - 8 - 9），中序为（2 - 3 - 1 - 6 - 7 - 8 - 5 - 9 - 4），则它的后续为？
   答案：3 - 2 - 8 - 7 - 6 - 9 - 5 - 4 - 1。
   

3. 设栈最大长度为 3 ，入栈序列为 1 ， 2 ， 3 ， 4 ， 5 ， 6 ，则不可能得出栈序列是（）
   A. 1 ， 2 ， 3 ， 4 ， 5 ， 6
   B. 2 ， 1 ， 3 ， 4 ， 5 ， 6
   C. 3 ， 4 ， 2 ， 1 ， 5 ， 6
   D. 4 ， 3 ， 2 ， 1 ， 5 ， 6
   答案：D。
   数组长度是 3 ，要想 4 第一个出，就要 1 , 2 , 3 , 4 先进栈，长度就超过 4 ，所以选 D 。

4. 设一组权值集合 W=( 15 ， 3 ， 14 ， 2 ， 6 ， 9 ， 16 ， 17 ) ，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为（ ）
   答案：229。

给定N个权值作为N个叶子结点，构造一棵二叉树，若该树的带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。

1. 最优二叉树，又被称为 哈夫曼树.
2. 哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

5. 线性表的链式存储结构既方便其存取操作，也方便其插入与删除操作，这种说法（）
   答案：错误。
   线性表的链式存储结构便于插入和删除，但不利于存取。线性表的顺序存储结构存取方便，但插入和删除都需要移动大量元素。

6. 已知不带头结点的双向循环链表中的结点结构为(data,last,next) ,在指针p所指结点之后插入由指针s指向的新结点，相应操作为（）
   答案：s -> last = p; s -> next = p -＞next; p -> next -> last = s; p -＞next = s。

7. 已知操作符包括+、-、*、/、(和)。将中缀表达式 a+b-a*((c+d)/e-f)+g 转换为后缀表达式 ab+acd+e/f-*-g+时，用栈来存放暂时还不能确定运算次序的操作符。若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是（ ）。
   答案：5。

// 伪代码
stack 操作符栈;
for i=1 to n{
   
	if 当前操作符是操作数
		直接打印;
	else if 当前操作符是操作符{
   
		if 当前操作符是'('
			压入栈内;
		else if 当前操作符是')'
			不断弹出并打印栈顶元素直至栈顶为'(';
			弹出栈顶;
		else if 当前操作符优先级高于栈顶操作符 || 栈为空
			压入栈内;
		else
			不断弹出并打印栈顶元素直至栈顶优先级不大于当前元素;
			当前操作符入栈;

	}
}
打印栈中剩余操作符; 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

8. 一颗二叉树的前序遍历是 ABCDFGHE ，后序遍历是 BGHFDECA ，中序遍历是？
   答案：BADGFHCE。

9. 关于双链表的搜索给定元素操作的说法正确的是?
   如果链表数据是无序的，则单向搜索与双向搜索平均速度相同。
   如果链表是有序的，而要搜索的数据距离最小值（最大值）较近，这种情况下双向搜索平均速度更快。
   因此双向搜索更稳定，方差更小。

10. 下面说法正确的有（ ）
    A.字符串是一种对象
    B.字符串是一种基本数据类型
    C.字符串是一种数据类型
    D.字符串是一种引用数据类型
    答案：ACD。
    string是一个对象，是数据类型，但不是基本数据类型。
    

11. 下列应用中，适合使用B+树的是（） 。
    A. 编译器中的词法分析
    B. 关系数据库系统中的索引
    C. 网络中的路由表快速查找
    D. 操作系统的磁盘空闲块管理
    答案：B。
    B+ 树是应文件系统所需而产生的 B- 树的变形，前者比后者更加适用于实际应用中的操作系统的文件索引和数据库索引，因为前者磁盘读写代价更低，查询效率更加稳定。
    编译器中的词法分析使用有穷自动机和语法树。网络中的路由表快速查找主要靠高速缓存、路由表压缩技术和快速查找算法。系统一般使用空闲空间链表管理磁盘空闲块。

概念：
B+ 树是一种树数据结构，通常用于数据库和操作系统的文件系统中。B+ 树的特点是能够保持数据稳定有序，其插入与修改拥有较稳定的对数时间复杂度。B+ 树元素自底向上插入，这与二叉树恰好相反。
 
拓展：
B- 树是平衡 m 叉查找树（左边分支都比根节点小，右边都大），B- 树中所有节点的孩子节点数的最大值称为B-树的阶；B- 树上，如果是根节点且不是叶节点则，至少有两个分支，若是非根非叶节点，至少有m/2向上取整个分支；B- 树的特殊结构：有n个分支的节点有n-1个关键字；
每个关键字的左侧子树和右侧子树的最大高度差为1；且所有叶子节点都在同一层！！！！！！！！

12. 广义表K=(m, n, (p, (q, s)), (h, f)),则head[tail[head[tail[tail(K)]]]]的值为（）
    答案：q。
    head() 返回列表的第一个元素；
    tail() 返回列表的删去第一个元素之后的剩余列表；
    K=(m, n, (p, (q, s)), (h, f)),
    head[tail[head[tail[tail(K)]]]]
    tail(K) ------- (n, (p, (q, s)), (h, f))
    tail[tail[K]] -------- ((p, (q, s)), (h, f))
    head() ----- ((p, (q, s))
    tail() ----- (q, s)
    head() ------- q

13. 在程序设计中，要对两个16K×16K的多精度浮点数二维数组进行矩阵求和时，行优先读取和列优先读取的区别是（）
    答案：行优先快。
    二维数组是默认的存储模式是行优先存储，也就是每行的数据都是连续的，而每列的数据是不连续的，所以按行访问更快。况且这是个长宽相等的方正。

14. 设哈希表长为 14 ，哈希函数是 H(key) = key % 11, 表中已有数据的关键字为 15，38，61，84 共四个，现要将关键字为 49 的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )
    答案：9。
    49 % 11 = 5 被占用了
    (5 + 1 ^ 2) % 11 = 6 还是被占用了
    (5 - 1 ^ 2) % 11 = 4 被占用了
    (5 + 2 ^ 2) % 11 = 9 未被占用，所以在 9 的位置放入 49

二次探测法是指平方探测法。 二次探测法在表中寻找“下一个”空桶的公式为： $$\begin{gathered} h_i=(h_0+i^2))\%m \\ {h}_i=(h \end{gathered}$$