16年408-数据结构

第一题：

解析：

经过查表可知：a的链接地址是1010H，而1010H正是表中e所在的位置。

由题可知f存放的位置是1014H，

要将f链接在a和e的中间，则a后面要链接f，f后面要链接e，e的链接地址不变

因此答案是1014H ，1004H，1010H，

答案选D

第二题：

解析：
选D。

p->next->prev：p的后一个节点的prev指针

p->prev->next：p的前一个结点的next指针

p删除后，很显然p的后一个节点的prev指针应该指向p的前一个节点（p->prev）,p的前一个结点的next指针应该指向p的后一个结点（p->next）。

第三题：

解析：

轨道具有先进先出的特点，因此可以将每一个轨道看作是一个队列，而由于驶出的序列是

1-9，数字小的先驶出，也就是说数字小的要放在数字大的后面。

8放入第一个轨道，4比8小，不能放在8的后面，因此放入第二个轨道。2最小放在第三个轨道中，5比4大可以放在第二个轨道，3比2大，可以放在第3个轨道，9比8大可以放在第一个轨道，1比上诉数字都要小，所以1只能放入第四个轨道，接下来是6和7，可以放入轨道二，三，四当中，因此至少需要四条轨道。

9，8

5，4

3，2

1

第四题：

解析：

三对角矩阵的特点：第一行有两个元素，从第二行开始到倒数第二行都有三个元素。

第一行到第三十行中间有28层是三个元素，再加上第一行2个元素，第30行2个元素一共是：

2+2+28*3=88，

因为要存入数组当中，而数组下标是从0开始的，因此最后一个元素的下标是37.

答案选B

第五题：

解析：

我们可以画一颗树出来观察一下：一颗树中，除了根结点外，一个非根结点对应一条边。

题目说有15条边，也就是15个非根节点，总共有25个结点，则根结点的个数为25-15=10，有10个根结点，代表10颗树，答案选C

第六题：

解析：

深度优先遍历的特点是，一条路走到底。

跟V1相连的有三个点V2,V3,V5,因此有三条路可选

V1-V2-V5-V4-V3

V1-V3-V2-V5-V4

V1-V5-V4-V3-V2

只有D错，答案选D

第七题：

解析：

第八题：

解析：

显然选B，因为题目给到这是一个长度1000的数组，如果x在数组开头的位置，使用折半查找需要折半许多次。

而使用题目所示的算法，假设x在前3个元素当中，则x最多只需要和A[0],A[3],A[2],A[1],进行比较。只需要比较4次。

使用折半查找显然比较次数更多。

第九题：

解析：

B+树的特点是：树中所有的关键字都存储在叶子结点上，且叶子结点之间通过指针链接，因此可以支持顺序查找，A对

第十题：

解析：

对于一个文件大小比较小的，一般使用内存进行排序就能满足需求，也叫内排序。

而对于一个比较大的文件，光使用内存还是不够的，还需要使用外存进行排序，而外存一般使用的是归并排序，答案选D.