数据 结构客观题复习题集
客观题：
1、已知无向图 G 如下所示，使用克鲁斯卡尔（Kruskal）算法求图 G 的最小生成树，加入到最小生成树中的边依次是：
A、(b,f), (b,d), (a,e), (c,e), (b,e)
B、(b,f), (b,d), (b,e), (a,e), (c,e)
C、(a,e), (b,e), (c,e), (b,d), (b,f)
D、(a,e), (c,e), (b,e), (b,f), (b,d)
2、图的深度优先遍历类似于二叉树的先序遍历
3、我们用一个有向图来表示航空公司所有航班的航线。下列哪种算法最适合解决找给定两城市间最经济的飞行路线问题Dijkstra算法
4、图的广度优先遍历类似于二叉树的层次遍历
5、已知一个图的邻接矩阵如下，则从顶点V1出发按深度优先搜索法进行遍历，可能得到的一种顶点序列为：
6、如果G是一个有28条边的非连通无向图，那么该图顶点个数最少为多少？9；
7、使用迪杰斯特拉（Dijkstra）算法求下图中从顶点1到其他各顶点的最短路径，依次得到的各最短路径的目标顶点是：
8、已知二叉树的前序遍历序列为 ABDCEFG，中序遍历序列为 DBCAFEG，则后序遍历序列为DCBFGEA;
9、在对N个元素进行排序时，基于比较的算法中，其“最坏时间复杂度”中最好的是O(NlogN);
10、将{5, 2, 7, 3, 4, 1, 6}依次插入初始为空的二叉搜索树。则该树的后序遍历结果是1、4、3、2、6、7、5；
11、对一组数据{ 2，12，16，88，5，10 }进行排序，若前三趟排序结果如下： 第一趟排序结果：2，12，16，5，10，88 第二趟排序结果：2，12，5，10，16，88 第三趟排序结果：2，5，10，12，16，88 则采用的排序方法可能是冒泡排序；
12、就排序算法所用的辅助空间而言，堆排序、快速排序、归并排序的关系是堆排序<快速排序<归并排序；
13、有组记录的排序码为{46，79，56，38，40，84 }，采用快速排序（以位于最左位置的对象为基准而）得到的第一次划分结果为40、38、46、56、79、84；
14、对于序列{ 49，38，65，97，76，13，27，50 }，按由小到大进行排序，下面哪一个是初始步长为4的希尔排序法第一趟的结果？49、13、27、50、76、38、65、97；
15、给出关键字序列{ 431, 56, 57, 46, 28, 7, 331, 33, 24, 63 }，下面哪个选择是按次位优先（LSD）链式基数排序进行了一趟分配和收集的结果？——>431——>331->33->63->24->56->46->57->7->28;
解析：次位优先就是按照个、十、百……的顺序进行排序，第一趟排序只看个位；
16、排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置的方法称为插入排序；
17、对N个元素采用简单选择排序，比较次数和移动次数分别为O(N^2)、O(N)；
18、平均查找长度与结点个数无关的查找方法是：利用哈希（散列）表；
19、设散列表的地址区间为[0,16]，散列函数为H(Key)=Key%17。采用线性探测法处理冲突，并将关键字序列{ 26，25，72，38，8，18，59 }依次存储到散列表中。元素59存放在散列表中的地址是：11；
解析：26%17=9；
25%17=8；
72%17=4；
38%17=4（冲突+1放在5）；
8%17=8（冲突+1仍冲突，再+1放在10）；
18%17=1；
59%17=8（冲突三次+1+1+1放在11）；
20、假定有K个关键字互为同义词，若用线性探测法把这K个关键字存入散列表中，至少要进行多少次探测？K(K+1)/2;
解析：已开放地址法为例：
由于K个关键字互为同义词，可假设K个关键字均为1，则有K个1.
1+2+3+4+……+K=K(1+K)/2.
21、将元素序列{18，23，11，20，2，7，27，33，42，15}按顺序插入一个初始为空的、大小为11的散列表中。散列函数为：H(Key)=Key%11，采用线性探测法处理冲突。问：当第一次发现有冲突时，散列表的装填因子大约是多少？0.45；
解析：18%11=7；
23%11=1；
11%11=0;
20%11=9;
2%11=2;
7%11=7(第一次发现冲突是第六个数字)
装填因子=5/11=0.45；
22、给定散列表大小为17，散列函数为H(Key)=Key%17。采用平方探测法处理冲突：hi(k)=(H(k)±i2)%17将关键字序列{ 6, 22, 7, 26, 9, 23 }依次插入到散列表中。那么元素23存放在散列表中的位置是：2；
解析：6%17=6；
22%17=5；
7%17=7；
26%17=9；
9%17=9（冲突一次+1^2放在10）；
23%17=6（发生冲突-1^2放在5，又发生冲突+2^2放在10，又发生冲突-2^2放在2，不冲突）；
23、在散列表中，所谓同义词就是：具有相同散列地址得两个元素；
24、将 {5, 2, 7, 3, 4, 1, 6} 逐个按顺序插入到初始为空的最小堆（小根堆）中。则该树的前序遍历结果为：1、3、5、4、2、7、6；
解析：
25、已知二叉树的先序遍历序列为ABCDEFGH，中序遍历序列为CBEDFAGH，则该二叉树形态中，父节点的右子节点为:G；
解析：
26、已知8个数据元素为（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉搜索树后，最后两层上的结点总数为：2；
27、将下列数（88, 70, 61, 96, 120, 90）按顺序插入初始为空的AVL中，所形成的AVL树的前序遍历结果是：88、70、61、96、90、120；
解析：
28、在下列所示的平衡二叉树中，插入关键字48后得到一棵新平衡二叉树。在新平衡二叉树中，关键字37所在结点的左、右子结点中保存的关键字分别是：24和53
解析：
29、如果AVL树的深度为5（空树的深度定义为−1），则此树最少有多少个结点？20；
30、将 26, 13, 44, 51, 98, 37, 66, 73 顺序插入一棵初始为空的AVL树。下列句子中哪句是错的？
A、44 是根结点
31、具有65个结点的完全二叉树其深度为（根的深度为1）：7；
32、将数字 {10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13, 2} 逐一插入一个初始为空的最小堆（小顶堆），得到的堆序列为：1、3、2、6、7、5、4、15、14、12、9、10、11、13、8；
33、设最小堆（小根堆）的层序遍历结果为{1, 3, 2, 5, 4, 7, 6}。用线性时间复杂度的算法将该堆调整为最大堆（大根堆），则该树的中序遍历结果为：3、5、4、7、2、6、1；
34、设一段文本中包含字符{a, b, c, d, e}，其出现频率相应为{3, 2, 5, 1, 1}。经哈夫曼编码后，文本所占字节数为：25；
35、给定有权无向图的邻接矩阵如下，其最小生成树的总权重是：14;
36、下图为一个AOV网，其可能的拓扑有序序列为：
A、ACBDEF
B、ABCEFD
C、ABCDFE
D、ABCEDF
37、在AOE网中，什么是关键路径？D、从第一个事件到最后一个事件的最长路径
38、给定有向图的邻接矩阵如下：顶点2（编号从0开始）的出度和入度分别是：0和2；
39、下图所示的 AOE 网表示一项包含 8 个活动的工程。活动 d 的最早开始时间和最迟开始时间分别是：12和14；
解析：活动d的最早完成时间即其所在弧的出发顶点2的最早，将2与8+4=12进行比较，选择较大的值12便是活动dde最早开始时间；
最迟开始时间需要倒推，活动6的最迟开始时间是27（8+10+9=27、8+4+6+9=27），推出活动4的最迟开始时间为8+4+7=21，活动5的最迟开始时间为18（3+6=9、8+10=18、27-9=18），活动2的最迟开始时间就是活动4的最迟开始时间-7=14.
40、给出如下图所示的具有 7 个结点的网 G，采用Prim算法，从4号结点开始，给出该网的最小生成树。下列哪个选项给出了正确的树结点收集顺序？
A、4501362
B、4526301
C、4561023
D、4563201
41、给定有向图如下。下列哪个选项不是对应的拓扑序列？
A、abedfc
B、aedbfc
C、aedfbc
D、abdfce
43、下面代码段的时间复杂度是O(log3n)
i=1;
while( i<=n )
i=i*3;
44、数组A[1..5,1..6]每个元素占5个单元，将其按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A[5,5]的地址为：1140；
45、若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。则采用哪种存储方式最节省运算时间？
46、有六个元素以6、5、4、3、2、1的顺序进栈，问哪个不是合法的出栈序列？B、3 4 6 5 2 1
47、表达式a*(b+c)-d的后缀表达式是：A、a b c + * d –
48、如果循环队列用大小为m的数组表示，且用队头指针front和队列元素个数size代替一般循环队列中的front和rear指针来表示队列的范围，那么这样的循环队列可以容纳的元素个数最多为：B、m
49、如果循环队列用大小为m的数组表示，队头位置为front、队列元素个数为size，那么队尾元素位置rear为：
50、若已知一队列用单向链表表示，该单向链表的当前状态（含3个对象）是：1->2->3，其中x->y表示x的下一节点是y。此时，如果将对象4入队，然后队列头的对象出队，则单向链表的状态是：B、2->3->4
51、若用大小为6的数组来实现循环队列，且当前front和rear的值分别为0和4。当从队列中删除两个元素，再加入两个元素后，front和rear的值分别为多少？2和0；
52、若栈采用顺序存储方式存储，现两栈共享空间V[m]：top[i]代表第i（i=1或2）个栈的栈顶；栈1的底在V[0]，栈2的底在V[m-1]，则栈满的条件是：D、top[1]+1==top[2]
53、对于一非空的循环单链表，h和p分别指向链表的头、尾结点，则有：A、p->next == h
54、在双向链表存储结构中，删除p所指的结点，相应语句为：
C、p->prior->next=p->next;p->next->prior=p->prior;
55、给定一个堆栈的入栈序列为{ 1, 2, ⋯, n }，出栈序列为{ p1, p2, ⋯, pn }。如果p2=n，则存在多少种不同的出栈序列？B、n-1
56、采用多项式的非零项链式存储表示法，如果两个多项式的非零项分别为N1和N2个，最高项指数分别为M1和M2，则实现两个多项式相乘的时间复杂度是：A、
57、由分别带权为9、2、5、7的四个叶子结点构成一棵哈夫曼树，该树的带权路径长度为：44；
58、若一棵二叉树的前序遍历序列是{ 4, 2, 1, 3, 6, 5, 7 }，中序遍历序列是{ 1, 2, 3, 4, 5, 6, 7 }，则下列哪句是错的？
A、这是一棵完全二叉树 B、所有的奇数都在叶子结点上
59、已知字符集{ a, b, c, d, e, f, g, h }。若各字符的哈夫曼编码依次是 0100, 10, 0000, 0101, 001, 011, 11, 0001，则编码序列 0100011001001011110101 的译码结果是：D、afeefgd
60、一棵二叉树中，双分支结点数为15，单分支结点数为30，则叶子结点数为（）个。16；
61、设最小堆（小根堆）的层序遍历结果为{5, 18, 15, 28, 22, 42, 40}。用线性时间复杂度的算法将该堆调整为最大堆（大根堆），则该树的中序遍历结果为：B、18, 28, 22, 42, 15, 40, 5
1、Kruskal 算法是维护一个森林，每一步把两棵树合并成一棵。√
2、若图G有环，则G不存在拓扑排序序列。√
3、用邻接矩阵法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关。√
4、在任一有向图中，所有顶点的入度之和等于所有顶点的出度之和。√
5、如果无向图G必须进行两次广度优先搜索才能访问其所有顶点，则G一定有2个连通分量。√
6、在一个有权无向图中，若b到a的最短路径距离是12，且c到b之间存在一条权为2的边，则c到a的最短路径距离一定不小于10。√
7、Prim 算法是维护一个森林，每一步把两棵树合并成一棵。×
8、在具有N个结点的单链表中，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。×
9、如果从有向图 G 的每一点均能通过深度优先搜索遍历到所有其它顶点，该图一定不存在拓扑序列。√
10、仅基于比较的算法能得到的最好的“最坏时间复杂度”是O(NlogN)。√
11、存在一棵总共有2016个结点的二叉树，其中有16个结点只有一个孩子。×
12、若一个结点是某二叉树的中序遍历序列的最后一个结点，则它必是该树的前序遍历序列中的最后一个结点。×
13、某二叉树的后序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无左孩子。×
14、若A和B都是一棵二叉树的叶子结点，则存在这样的二叉树，其前序遍历序列为…A…B…，而中序遍历序列为…B…A…。×
15、要从50个键值中找出最大的3个值，选择排序比堆排序快。√
16、对N个记录进行快速排序，在最坏的情况下，其时间复杂度是O(NlogN)。×
17、希尔排序是稳定的算法。×
18、任何二叉搜索树中同一层的结点从左到右是有序的（从小到大）。√
19、对N个不同的数据采用冒泡排序进行从大到小的排序，当元素基本有序时交换元素次数肯定最多。×
20、在一棵二叉搜索树上查找63，序列39、101、25、80、70、59、63是一种可能的查找时的结点值比较序列。×
21、在散列表中，所谓同义词就是被不同散列函数映射到同一地址的两个元素。×
22、在一棵由包含4、5、6等等一系列整数结点构成的二叉搜索树中，如果结点4和6在树的同一层，那么可以断定结点5一定是结点4和6的父亲结点。×
23、将M个元素存入用长度为S的数组表示的散列表，则该表的装填因子为M/S。√
24、对AVL树中的任一结点，其左子树的高度一定比其右子树的高度要高。×
25、即使把2个元素散列到有100个单元的表中，仍然有可能发生冲突。√
26、如果由结点{ 1, 2, 3, 4 }组成的AVL树的深度是3（根结点的深度是1），则结点2或者结点3一定有两个子结点。√
27、若用平方探测法解决冲突，则插入新元素时，若散列表容量为质数，插入就一定可以成功。×
28、将一棵完全二叉树存于数组中（根结点的下标为1）。则下标为23和24的两个结点是兄弟。×
29、任何最小堆中从根结点到任一叶结点路径上的所有结点是有序的（从小到大）。√
30、对N（≥2）个权值均不相同的字符构造哈夫曼树，则树中任一非叶结点的权值一定不小于下一层任一结点的权值。√
31、哈夫曼编码是一种最优的前缀码。对一个给定的字符集及其字符频率，其哈夫曼编码不一定是唯一的，但是每个字符的哈夫曼码的长度一定是唯一的。×
32、无向连通图至少有一个顶点的度为1。×
33、算法分析的两个主要方面是时间复杂度和空间复杂度的分析。√
34、算法可以没有输入，但是必须有输出。√
35、和具有相同的增长速度。√
36、 是 的。√
37、 和 具有相同的增长速度。×
38、对于顺序存储的长度为N的线性表，访问结点和增加结点的时间复杂度分别对应为O(1)和O(N)。√
39、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用顺序表存储最节省时间。√
40、将N个数据按照从小到大顺序组织存放在一个单向链表中。如果采用二分查找，那么查找的平均时间复杂度是O(logN)。×
41、通过对堆栈S操作：Push(S,1), Push(S,2), Pop(S), Push(S,3), Pop(S), Pop(S)。输出的序列为：123。×
42、若一个栈的输入序列为1，2，3，…，N，输出序列的第一个元素是i，则第j个输出元素是j−i−1。×
43、所谓“循环队列”是指用单向循环链表或者循环数组表示的队列。×
44、在用数组表示的循环队列中，front值一定小于等于rear值。×
45、对于顺序存储的长度为N的线性表，删除第一个元素和插入最后一个元素的时间复杂度分别对应为O(1)和O(N)。×
46、若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。√
47、若用链表来表示一个线性表，则表中元素的地址一定是连续的。×