P147-05.在二叉树中有两个结点m和n，若m是n的祖先，则使用(C)可以找到从m到n的路径。
A. 先序遍历 B.中序遍历 C.后序遍历 D.层序遍历
分析:在后序遍历退回时访问根节点，就可以从下向上把从n到m的路径上的结点输出，若采用非递归算法，则当后序遍历访问到n时，栈中把根到n的父指针的路径上的结点都记忆下来，也可以找到从m到n的路径。
P148-18.线索二叉树是一种(物理结构)。
分析:
逻辑结构：集合、线性、树和图
物理结构：线性存储和非线性存储
其中，线性存储结构有顺序（sequential）、链式（linked）、索引（indexed）和散列（hashing）4种结构
而加上的线索就是利用指针来指向前驱后继，是一种链式结构，故为存储结构，提了存储方式即为物理(存储)结构
P148-20.判断线索二叉树中*p结点有右孩子结点的条件是(C)
A.p!=NULL B.p->rchild!=NULL C.p->rtag==0 D.p->rtag==1
分析:对于线索二叉树来说，除了遍历结果的第一个结点左孩子指针与最后一个节点右孩子指针指向NULL之外，其余无左右孩子的结点的左右孩子指针均指向逻辑上的前驱后继，所以叶子节点有可能无右孩子但指向逻辑上的后继，所以此时p->rchild!=NULL并不成立但却无右孩子
P174-01.给定一棵二叉树的先根遍历序列和后根遍历序列，能否唯一确定一棵树？
答:可以.对于一棵树来说,它的孩子没有左右孩子之分,只有第一个、第二个、第三个等孩子之分.故对于一棵树来说,其后根遍历就是孩子从1到n先后遍历,最后遍历根节点,而树转换为二叉树后,它的同层级孩子被分到同层级前一个孩子的右孩子结点,而二叉树的中序遍历为左根右,即先左孩子然后根最后右孩子,而二叉树中的左孩子即对应树中第一个孩子,根对应根,右孩子对应树中兄弟,所以左根右顺序即左子树的左边结点-根节点-所有右子树结点,右子树即为兄弟,对应到树中即是将所有兄弟遍历完之后再遍历根节点,也就是后根遍历,而二叉树的中序和其它序的组合是可以确定一棵唯一二叉树的,故可以.
P196-05 一下关于图的叙述中，正确的是()
A. 强连通有向图的任何顶点到其他所有顶点都有弧
B. 图的任意顶点的入度等于出度
C. 有向完全图一定是强连通有向图
D. 有向图的边集的子集和顶点集的子集可构成原有向图的子图
答:有向完全图即任意两个顶点之前两条弧都存在，所以所有顶点之间必定都有路径，所以强连通，C正确。若边集的顶点包含了顶点子集中不存在的顶点，则无法构成子图。
12 若具有n个顶点的图是一个环，则它有()棵生成树。
A. n^2 B.n C.n-1 D.1 答:若为一个环,则n个顶点有n条边,每去掉一条边即为一颗生成树。
P215-07 用邻接表存储的图的深度优先遍历算法类似于树的()。
A. 中序遍历 B.先序遍历 C.后序遍历 D.按层次遍历
答:对于图的深度优先遍历来说，是出队的时候访问并将其邻接点入队，先遍历先输出，所以是先序遍历，若用递归方法在递归函数后输出，则为后序遍历。
P216-10 判断有向图中是否存在回路，除可以利用拓扑排序外，还可以利用()
A.求关键路径的方法B.求最短路径的Dijkstra算法C.深度优先遍历算法D.广度优先遍历算法
答:对于无向图来说，若DFS中遇到了回边，则必定存在环;对于有向图来说，若在DFS结束前遇到了以出发点为弧尾的回弧，且弧头在生成树中为出发点子孙，则存在回路。
11 使用DFS算法递归地遍历一个无环有向图，并在退出递归时输出相应顶点，这样得到的顶点序列是()
A.逆拓扑有序 B.拓扑有序 C.无序的 D.都不是
答:由于是退出递归时输出相应顶点，即相当于先入栈，最后一路回退输出，所以为逆序。
P233- 09 以下关于拓扑排序的说法中，错误的是(Ⅲ)
Ⅰ.若某有向图存在环路，则该有向图一定不存在拓扑排序
Ⅱ.在拓扑排序算法中为暂存入度为0的顶点,可以使用栈,也可以使用队列
Ⅲ.若有向图的拓扑有序序列唯一,则图中每个顶点的入度和出度最多为1
答:只有Ⅲ正确,对于Ⅰ,若有向图存在环路,则会出现后面的点到前面的点存在路径,与拓扑定义不符;对于Ⅱ,栈相当于深度优先,而队列相当于广度优先,只要保证入度为0的先进入,且顺序正确即可,所以队列也可以;对于Ⅲ,有序序列唯一的话，可以增删一条不会影响整体拓扑序列的弧,比如A→B→C增加一条A直接指向C的弧,其序列依然为ABC，但图改变
12 若一个有向图具有有序的拓扑排序序列,则它的邻接矩阵必定为(C)
A.对称 B.稀疏 C.三角 D.一般
答:题目关键在于”有序”二字，有序代表由小到大,比如ABCDE…,这种边只会出现在邻接矩阵的上三角，故为三角矩阵
13.下列关于图的说法中,正确的是(Ⅲ)
Ⅰ.有向图中顶点V的度等于其邻接矩阵中第V行中1的个数
Ⅱ. 无向图的邻接矩阵一定是对称矩阵,有向图的邻接矩阵一定是非对称矩阵
Ⅲ.在图G的最小生成树G1中,某条边的权值可能会超过未选边的权值
Ⅳ.若有向无环图的拓扑序列唯一,则可以唯一确定该图
答:Ⅰ应等于出+入;Ⅱ有向图邻接矩阵也可以对称;Ⅲ若存在环则环中最大的边会被舍弃,但仍有可能小于其他非此环中的边;Ⅳ A→B→C增加A直接指向C的弧，其拓扑序列不变
P300-10 下列关于B+树和B数的叙述中，不正确的是(A)
A. B树和B+树都能有效地支持顺序查找
B. B树和B+树都能有效地支持随机查找
C. B树和B+树都是平衡的多叉树
D. B树和B+树都可以用于文件索引结构
答: B树不存在线性结构，不可以进行顺序查找，B+树所有关键字在最底层用链表连接，支持顺序查找，都支持随机查找。随机查找的意思是，从所有关键字中随即抽取一个与结果进行比较，两者都支持。
P310-01. 只能在顺序存储结构上进行的查找方法是(B)
A. 顺序查找法 B.折半查找法 C.树型查找法 D.散列查找法
答:折半查找需要获取一段数据的中间元素，要求具有随机存取的特性，仅顺序存储符合要求;而C和D分别对应的是树形存储结构与散列表结构，与顺序存储无关。
P311-08 对包含n个元素的散列表进行查找,平均查找长度是()
A. O(log2n) B.O(1) C.不直接依赖于n D.直接依赖于表长m
答:ASL直接相关于装填因子α=n/m,无法获得具体的AST数量级
A选项中ASL只相关于n，错误;B选项中与任何因素都不相关，错误;C选项，因为与n和m都相关，所以不直接依赖于n正确，而D错误。
09 采用开放定址法解决冲突的散列查找中,发生聚集的原因主要是(D)
A. 数据元素过多 B.负载因子过大 C.散列函数选择不当 D.解决冲突的方法选择不当
答:A选项数据元素过多时，若可承载数量也多则也不容易发生冲突;B选项易误选，负载因子过大→容易发生冲突→容易发生聚集，不是主要原因，负载因子过大也需要解决冲突方法不当才会发生聚集;C选项散列函数选择不当 导致的是产生冲突过多;D.解决冲突的方法选择不当就会导致非同义词与同义词的冲突变多,是聚集的主要原因。
P322-04 对任意7个关键字进行基于比较的排序,至少要进行()次关键字之间的两两比较
A.13 B.14 C.15 D.6
答:题目中问至少要进行多少次比较，即进行了这么多次比较之后，一定可以将元素排列完毕，所以需要考虑到最坏情况下的最少比较次数才能保证所有情况都可以经过这么多次比较后完成排序。公式:⌈log2(n!)⌉，将n带入,得13。
解析:n个关键字有n!种可能的排列顺序，若至少进行t次比较，由于每次比较要选择两个元素，因而能做的最大选择数为2^t，这2^t种选择需要将n!种排列覆盖掉，即2^t≥n!,得t.
P334-11 下列序列中,()可能是执行第一趟快速排序后所得到的序列.
Ⅰ.{68,11,18,69,23,93,73} Ⅱ.{68,11,69,23,18,93,97} Ⅲ.{93,73,68,11,69,23,18} Ⅳ.{68,11,69,23,18,73,93}
A.Ⅰ、Ⅳ B.Ⅱ、Ⅲ C.Ⅲ、Ⅳ D.只有Ⅳ
答:直接将最终排序结果写出,然后判断选项是否符合一趟排序结果判断处于最终位置的元素的数量即有一个元素处于它的最终位置上.
P344-03 设线性表中每个元素有两个数据项k1和k2,现对线性表按以下规则进行排序:先看数据项k1,k2值小的元素在前,大的元素在后;在k1值相同的情况下,再看k2,k2值小的在前,大的元素在后.满足这种要求的排序方法是(D)
A. 先按k1进行直接插入排序,再按k2进行简单选择排序
B. 先按k2进行直接插入排序,再按k1进行简单选择排序
C. 先按k1进行简单选择排序,再按k2进行直接插入排序
D. 先按k2进行简单选择排序,再按k1进行直接插入排序
答: k1权重大于k2,先按k2后按k1,需要先排出k2,且要求对k1的排序具有稳定性,而简单选择排序不稳定,所以要用直接插入排序排k1
P345-04 若只想得到1000个元素组成的序列中第10个最小元素之前的部分排序的序列,用(D)方法最快.
A.冒泡排序 B.快速排序 C.希尔排序 D.堆排序
答:依题意,要求排序算法可以确定最小元素的最终位置,故排除BC,其次,要找出10个,冒泡排序每一趟需要从头至尾排序一次时间复杂度为O(n),堆排序在构造小根堆后每趟调整时间复杂度为0(;ogn)<O(n).故选择堆排序
09 构建n个记录的初始堆,其时间复杂度为(A).
A. O(n) B.O(n^2) C.O(logn) D.O(nlogn)
答:第i层最多2^(i-1)个结点,每个结点最多对比关键字2次,n个结点的完全二叉树高h=⌊logn⌋+!,向下调整最多需要下坠(h-i)层,只有第1~(h-1)层才有可能需要调整,求和计算可得比较次数≤4n,即时间复杂度数量级为 O(n)
P353-03 在下列排序算法中,平均情况下空间复杂度为O(n)的是(D);最坏情况下空间复杂度为O(n)的是(C).
Ⅰ.希尔排序 Ⅱ.堆排序 Ⅲ.冒泡排序 Ⅳ.归并排序 Ⅴ.快速排序 Ⅵ.基数排序
A. ⅠⅣⅤ B.ⅡⅤ C.ⅣⅤ D.Ⅳ
答:除了归并排序其余排序的空间复杂度均来自递归栈,为O(logn),归并由于要复制数组,故需要O(n)的空间复杂度;堆排序只需按顺序建立数组表示的完全二叉树,不存在最坏情况,故不选,希尔排序每次步长折半递归,为O(logn),冒泡空间复杂度O(1),,归并排序最坏最好都是O(n),快排若本身有序则一直取首元素作为比较值递归,其最坏空间复杂度为O(n),基数排序空间复杂度与基数r也有关.
P359-04 下列排序算法中属于稳定排序的是(ⅠⅣⅥ),平均时间复杂度为O(nlogn)的是(ⅡⅥⅦ),在最好的情况下，时间复杂度可以达到线性时间的有(ⅠⅣ)
Ⅰ.冒泡排序 Ⅱ.堆排序 Ⅲ.选择排序 Ⅳ.直接插入排序 Ⅴ.希尔排序(O(n^1.3)) Ⅵ.归并排序 Ⅶ.快速排序
答:归并排序也是稳定排序,希尔排序的时间复杂度并不容易衡量,最好的复杂度为(O(n^1.3)),当数组本身有序时,冒泡和直接插入排序的时间复杂度为O(n)
P369-02 设有5个初始归并段,每个归并段有20个记录,采用5路平衡归并排序,若不采用败者树,使用传统的顺序排序选出最小记录(简单选择排序)的方法,总的比较次数为();若采用败者树最小的方法,总的比较次数约为() .
A．20 B.300 C.396 D.500
答:若不使用败者树,则每趟从归并段中选择一个最小值，假设正好每个归并段选出19个,则每趟比较4次，共选出519个,共比较4519=380次,然后每个归并段剩余一个元素,再使用简单选择排序选出,需比较4+3+2+1=10次380+10=390≈396,(答案中对于100个元素采用99趟排序,每趟比较4次,499=396);
若使用败者树,败者树为完全二叉树,5路归并意味着败者树的外界点有5个,败者树的高度h=⌈log5⌉=3。每次在参加比较的记录中选择一个关键字最小的记录,比较次数不超过h,共100个记录,需要的比较次数不超过100×3=300,故选B
05 在下列关于外部排序过程输入/输出缓冲区作用的叙述中,不正确的是(D)
A. 暂存输入输出记录 B.内部归并的工作区 C.产生初始归并段的工作区 D.传送用户界面的消息
答:在外部排序过程中输入/输出缓冲区就是排序的内存工作区,例如做m路平衡归并需要m个输入缓冲区和1个输出缓冲区,用以存放参加归并的和归并完成的记录。在产生初始归并段时也用作内部排序的工作区。
06 在做m路平衡归并排序的过程中,为实现输入/内部归并/输出的并行处理,需要设置(D)
个输入缓冲区和(A)个输出缓冲区
①A.2 ②B.m ③C.2m-1 ④D.2m
①A.2 ②B.m ③C.2m-1 ④D.2m
答:当无特殊要求时,需要m个输入缓冲区和1个输出缓冲区。由于内部归并和输入输出之间没有冲突且与输入输出相比所耗时间很短，若要实现输入/内部排序/输出的并行处理,则将它们都乘以2即可。
第二期伴学营基础阶段《数据结构》期中测评
75/100
6
单选(5分)
对于不带头结点的链栈L（next域表示该结点下一个元素），top指针指向栈顶元素（栈顶在链头方向），则x结点进栈操作为
得分/总分
0.00/5.00
**A.**top->next=x;top=x;
B.top=x;top-next=x;
**C.**top=x;x->next=top;
**D.**x->next=top;top=x;
正确答案：D你错选为A
对于链栈，入栈和出栈都在队头进行，而队头指针指向的是栈顶元素，栈顶元素即队头，其next指针指向下一个元素，也就是链表中的第二个元素，有新元素入栈的话，则新元素变为队头，指向原本的队头
11
单选(5分)
有一个10阶的三对角矩阵M，其元素 mi,j（1≤i,j≤10）按列优先依次压缩存入下标从0开始的一维数组 A 中，则 A[20] 对应的元素是（ ）
得分/总分
**A.**m7,7
**B.**m8,8
**C.**m8,7
**D.**m7,8
正确答案：D你错选为C
对于列优先，第一列有两个元素，第j列从头直到第一个有效数据间有j-2个0,若数组下标从0开始，则关系式为
mi,j=A[2+(j-2)3+i-(j-2)-1]=A[i+2j-3],假设下标为n的数组元素为矩阵中第j列的元素，则有:
2+3*(j-2)+1≤n+1<2+3*(j-1) (下标为n的元素实际上是数组中第n+1个元素),得j≤(n+4)/3,右边n=20代入结果向下取整，得j=8,所以列数为8,即i+2*8-3=20,得i=7
故选D
18
单选(5分)
下列关于并查集的说法中，正确的是 （ ）
得分/总分
**A.**并查集是双亲表示法存储的树
**B.**并查集是孩子表示法存储的树
**C.**并查集的效率和树的高度无关
**D.**并查集可以用于迪杰斯特拉算法求最短路径
并查集是双亲表示法存储的树，Find查找操作的效率和树的高度相关，树越矮，效率越高，A正确，BC错误。并查集的常见应用：①克鲁斯卡尔算法求最小生成树；②求无向图的连通分量；③判断无向图的连通性。并查集不会用于迪杰斯特拉算法，D错误。
对于n（n≥2）个字符构造的二叉哈夫曼树，每个字符结点的权值都大于0（但各节点权值可能相等）。则下列叙述错误的是 ( )
**A.**树中两个权值最小的结点一定是兄弟结点
**B.**该哈夫曼树的最大高度是 n
**C.**该哈夫曼树的结点总数为 2n-1
**D.**所有非叶结点的权值之和不小于所有叶结点的权值之和
正确答案：A你错选为B
A选项：该选项不严谨，若各个字符结点的权值都为1，则所有的结点都是“权值最小的结点”，但不一定都是兄弟。(没想到真是这么无聊的错误)
B选项：根据哈夫曼树的构造过程，包含n个叶结点的哈夫曼树，最大高度为n。
C选项：二叉哈夫曼树中，只有度为2和度为0的结点。度为0的结点数为 n，假设度为2的结点数为 m，则 2m+1= m+n，即 m=n-1。因此该哈夫曼树的结点总数为 2n-1。
D选项：根据哈夫曼树的构造过程可知，单独一个根节点的权值，就等于所有叶子结点的权值之和，再加上其他非叶结点的权值，一定大于所有叶子结点的权值之和。