数据结构和算法|集18

在2006门CS考试中提出了以下问题。

1、考虑多项式p（x）＝a0+a1x+a2x^ 2 +a3x^ 3，其中ai＝＝！0，对于所有i.在输入x上计算p所需的最小乘法数为：

（A） 三, （B） 四, （C） 六, （D） 九,

答复（A）

对于给定表达式的求值，可以使用以下顺序最小化乘法。 p（x）=a0+x（a1+x（a2+a3x））

2.为了在未加权图上实现Dijkstra的最短路径算法，使其在线性时间内运行，将使用的数据结构为： （A） 排队 （B） 堆叠 （C） 堆 （D） B-树

答复（A） 无加权图中的最短路径是指为了到达图中的目标而必须经过的最小边数。这与解决加权版本的问题相同，其中所有权重恰好为1。如果我们使用队列（FIFO）而不是优先级队列（Min Heap），我们可以得到线性时间O（|V |+|E |）内的最短路径。基本上是这样的 BFS 遍历图形以获得最短路径。

3.三元最大堆类似于二进制最大堆，但节点没有两个子节点，而是有三个子节点。三元堆可以用如下数组表示：根存储在第一个位置[0]，下一级的节点从左到右从[1]到[3]存储。树的第二级从左到右的节点从[4]位置开始存储。通过将x放置在位置a[n]并将其推到树上以满足heap属性，可以将项目x插入到包含n个项目的三元堆中。

以下哪一项是表示3元最大堆的数组中的有效元素序列？ （A） 1,3,5,6,8,9 （B） 9,6,3,1,8,5 （C） 9,3,6,8,5,1 （D） 9,5,6,8,3,1

答复（D）

                                      9
                                   /  |   
                                /     |     
                              5       6      8
                           /  |
                         /    |
                       3      1

4.假设元素7、2、10和4按该顺序插入到上述问题中找到的有效3元最大堆中，以下哪一项是数组中表示结果堆的项序列？ （A） 10,7,9,8,3,1,5,2,6,4 （B） 10,9,8,7,6,5,4,3,2,1 （C） 10,9,4,5,7,6,8,2,1,3 （D） 10,8,6,9,7,2,3,4,1,5

答复（A）

After insertion of 7
                                          9
                                      /   |   
                                    /     |     
                                  7       6       8
                               / | 
                             /   |  
                            3    1    5    

插入2之后

                                           9
                                      /    |   
                                    /      |     
                                  7        6       8
                               / |        /
                             /   |       /
                            3    1    5  2

插入10后

                                 10
                             /    |   
                           /      |     
                        7         9       8
                    / |        / |
                  /   |       /  |
                3    1    5  2    6

插入4之后

                                 10
                             /   |   
                           /     |     
                         7        9       8
                      / |       / | 
                    /   |      /  |   
                  3    1    5  2   6    4

如果您发现任何答案/解释不正确，或者您想分享有关上述主题的更多信息，请发表评论。