数据结构模块

1.已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则该完全二叉树的结点个数最多是()。C

A. 39
B. 52
C. 111
D. 119

• 谨记！！！完全二叉树最后两层都可能有叶结点
• 两种情况：第六层或者第七层是最后一层
  第七层是最后一层时完全二叉树的结点个数最多
  此时 第六层总26-1 =32个结点中有8个是叶子节点
  则第六层中另外24个结点都有孩子 而满足结点数最多 则第七层共有24*2=48个结点
  总结点数就是63+48=111

2. 解析XML时，需要校验节点是否闭合，如必须有与之对应，用（）数据结构实现比较好（） D

A. 链表
B. 树
C. 队列
D. 栈

• 什么叫做节点是否闭合 ，如《property》《/property》 类似括号匹配
• 栈的应用：
  1、符号匹配；
  2、表达式求值；
  3、实现函数调用

3.给出下述节点及权值（括号中数字为权值），构造huffman树，其带权路径长度为（）a(7),b(5),c(4),d(2) B

A. 18
B. 35
C. 36
D. 46

• (2+4)3+52+1*7=35
  

4.在一般情况下，采用压缩存储后，对称矩阵是所有特殊矩阵中存储空间节约最多的，这样的说法正确吗？B

A. 正确
B. 不正确

• 稀疏矩阵，0元素远多于非0元素且非0元素分布没有规律。比如一个矩阵只有零散的两个1，其他元素都是0，那压缩存储的时候只需要记录这两个非0元素的位置（行，列）还有值（1）就可以了，其他元素都是0。
  可以利用零元素节约大量存储、运算和程序运行时间

5. 若一棵二叉树的前序遍历序列为a， e， b， d， c，后序遍历序列为 b， c， d， e， a，则根结点的孩子结点（ ）。A

A. 只有 e
B. 有 e、 b
C. 有 e、 c
D. 无法确定

• 解析：

1. 前序遍历： a,e,b,d,c 后序遍历：b,c,d,e,a 。由此可说明 a 是 e 的直接根结点
2. 前序遍历： a,e,（b,d,c） 后序遍历：（b,c,d）,e,a 此时把 bdc 当作整体，忽略内部顺序。由此可见 e 是 bdc 整体的双亲结点，所以 e 是 a 的唯一孩子结点
   

6. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算,则利用（）存储方式最节省时间。 A

A. 顺序表
B. 双链表
C. 带头结点的双循环链表
D. 单循环链表

1. 存取任一指定序号的元素
2. 最后进行插入和删除运算,因为插入和删除操作都是在最后进行的，所以无需大量移动数据元素

7.

矩阵转置算法（三元组顺序表）

• 解析：例如一个矩阵需要转置
  
  
• 矩阵的行数 n 和列数 m 的值交换；
• 将三元组中的i和j调换；
• 转换之后的表同样按照行序（置换前的列序）为主序，进行排序；

8.数组A=array[1..100，1..100]以行序为主序存储，设每个数据元素占2个存储单元，基地址为10，则LOC[5，5]应为。C

A. 1020
B. 1010
C. 818 从1开始数，数到5 ；有4行完整的100+ 1到5要4个单位 = 10042+4*2+10 = 818
D. 808

9. 若无向图G=(V，E)中含8个顶点，为保证图G在任何情况下都是连通的，则需要的边数最少是

A. 6
B. 7
C. 16
D. 22

• 在任何情况下都要保持连通，当然也包括任意变动图G中的边，G始终保持连通。
  很容易错选A
  
  
• 为什么还要加7个点组成完全连通，再加1，因为第8个点跟任何7个点中1个点连接，如果这个点调整不跟第8个点的连接，那么这个点只能跟其他6个点连接，跟其他6个点连接已经重复，重复边不算，强行重复会减去一条边，也就变成21条边。所以22条边怎么调整，8个点都是连通的。

10. 设F是一个森林,B是由F变换得到的二叉树。若F中有n个非终端结点,则B中右指针域为空的结点有()个C

A. n-1
B. n
C. n+1
D. n+2

11. 具有 60 个结点的二叉树，其叶子结点有 12 个，则度为 1 的结点数为（ ）D

A.11
B.14
C.48
D.37

• 解析 结点的度：结点子树的个数
  （1） 60个节点共有59个度；
  （2） 叶子节点12个，所以度为1和度为2的节点数和为48；
  （3） 59 = 2*（48-x）+x;
  （4） x = 37;

12. 面关于图的存储的叙述中正确的是（ ）B

A. 用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关
B. 用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关
C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关
D. 用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关

• 解析：图的两种存储方式——
  (1) 、邻接矩阵
  使用的是两个数来表示图，一个一位数组的存储顶点的信息，一个二维数组（邻接矩阵）存储图中的边或者是弧的信息
  设图有n个顶点，则邻接矩阵是一个n * n的方阵！
  所以总结下来邻接矩阵只跟图的顶点有关！

  (2)、邻接表
  使用数组 + 链表的方式来存储图
  图中的顶点使用一维数组来存储，图中每个顶点的所有邻节点构成一个线性表，邻接点的个数是不确定的，所以使用单链表来存储
  所有总结下来邻接表既和顶点有关也和变有关！

13.已知广义表（a,b,c）,（d,e,f），从A中取出原子e的运算是（）D

A.tail(head(A))
B.head(tail(A))
C.head(tail(tail(head(A))))
D.head(tail(tail(A))) head去掉后的意思

• 解析
  tail(A) = (d,e,f)
  tail(tail(A)) = (e,f)
  head(tail(tail(A))) = e

14.有软件结构图如下所示。该结构图的深度是（）

• 插图
  

A.4
B.5
C.2
D.3

• 根据考研大纲 层数为1 开始
  
  

15. 树的父链表示法其实就是用数组表示树的存储结构()对

• 解析
  
  树的表示方法：父亲数组表示法；儿子链表表示法；左儿子右兄弟二叉树表示法。
  父节点表示法的思想是让每个节点持有它的父节点的索引，这种方式是从子节点出发。
  孩子链表表示法也是用一维数组来存储树中各结点的信息。

16.设森林F中有三棵树，第一，第二，第三棵树的结点个数分别为M1，M2和M3。与森林F对应的二叉树根结点的右子树上的结点个数是( )。M2+M3 [注意M1+M2 or M1+M3]

①将所有树转换为二叉树；
②第一个二叉树保持不变，从第二棵二叉树开始，依次将其作为前一棵二叉树的右孩子。
所以，这道题目中，左子树中结点个数为M1-1，而右子树的结点个数为M2+M3.

17. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素,则采用（）存储方式最节省运算时间。 D

A.单链表
B.仅有头指针的单循环链表
C.双链表
D.仅有尾指针的单循环链表

• 解析：删除第一个也只需要tail->next=tail->next->next;

18.下列关于堆和栈的区别描述错误的有A

A.申请方式的不同，堆是系统自动分配，栈是自己申请
B.栈的大小是固定的，堆的大小受限于系统中有效的虚拟内存
C.栈的空间由系统决定何时释放，堆需要自己决定何时去释放
D.堆的使用容易产生碎片，但是用起来最方便

1.栈内存操作系统来分配，堆内存由程序员自己来分配。
2.栈有系统自动分配，只要栈 剩余空间大于所申请空间，系统将为程序提供内存，否则将报异常提示栈溢出。

19.求最小生成树的普里姆(Prim)算法中边上的权可正可负。 （）正确

• 解析：
  可以负值啊 狄杰斯特拉算法不支持的