Question

数据结构试题求解

我知道大家的时间都非常宝贵，希望能够抽出一点点的空闲给予解答（最好能写出理由），我将不胜感激，能答几道是几道吧，回答最多的给分酬谢。
多谢了！

一.判断题
1.（ ）带表头结点的双向循环链表判空的条件是：first->next==first(first为表头指针)。
2.（ ）一个有向图的邻接表和逆邻接表中的结点个数一定相等。
3.（ ）一棵3阶B树是平衡的3路搜索树，反之，一棵平衡的3路搜索树是3阶B树。

二.填空题
1. 下面程序段时间复杂度为________
for (int i=0;i<n;i++)
for (int j=0;j<k;j++ )
S+=i;
2.数据结构的存储结构包括顺序，________，索引和散列四种。
3.设森林T中有三棵树，第一，二，三棵树的结点个数分别为n1,n2,n3,将森林转换成二叉树后，其根结点的左子树上有________个结点。
4.对二叉搜索树进行________遍历，可以得到按关键字从小到大排列的结点序列。

三.选择题
1.已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为________。
A. O(1) B. O(m) C. O(n) D.O(m+n)
2.设有一个递归算法如下：
int fact(int n) { //n大于等于0
if(n<=0) return 1;
else return n*fact(n-1);
}
则计算fact(n)需要调用该函数的次数为________次。
A. n B. n+1 C. n+2 D.n-1

Answer 1

1 错。给的条件能确定链表含1个元素，而非空。
2 错。
3 错。M阶B树要求（叶上）至少M/2个元素，上面所谓的叶就是倒数第二层了，而三阶平衡树最底层可以有1个元素。
1. 下面程序段时间复杂度为________
for (int i=0;i<n;i++)
for (int j=0;j<k;j++ )
S+=i;

O(n*k)
2 数据结构的存储结构包括顺序，________，索引和散列四种。

链接
3.设森林T中有三棵树，第一，二，三棵树的结点个数分别为n1,n2,n3,将森林转换成二叉树后，其根结点的左子树上有________个结点。

n1-1。
森林转为二叉树之后，原第一棵树T1的根节点将成为二叉树Tn的根节点，其余的采取貌似于长兄如父的方式排列，原先是父子关系的还是步子，但是原先是兄弟的也变成了父子，对于其他树的根节点的有分支，会分到左分支的另一派左分支上。所以是n1-1

4.对二叉搜索树进行________遍历，可以得到按关键字从小到大排列的结点序列。

中序
二叉搜索树为了搜索的方便，根节点大于左边的，小于右边的。所以中序遍历才会得到所要序列
三.选择题
1.已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为________。
A. O(1) B. O(m) C. O(n) D.O(m+n)

B。步进m次（即O(m)）以达到其尾节点，然后将该节点的next指向B。如果给定了条件是链表既存有头，又存有尾，那么就是o(1).这里选B。

2.设有一个递归算法如下：
int fact(int n) { //n大于等于0
if(n<=0) return 1;
else return n*fact(n-1);
}
则计算fact(n)需要调用该函数的次数为________次。
A. n B. n+1 C. n+2 D.n-1

B

可乐答的不错。可以保证。我做的结果一样。

Answer 2

大略看了下，错了请见谅。
-------------

一.判断题
1.（ ）带表头结点的双向循环链表判空的条件是：first->next==first(first为表头指针)。
错。给的条件能确定链表含1个单元，而非空。

2.（ ）一个有向图的邻接表和逆邻接表中的结点个数一定相等。
错。但是有向图的弧(指相邻点vi到vj的有向边)数等于邻接表(逆邻接表)个出边表结点(入边表结点)的数目。

3.（ ）一棵3阶B树是平衡的3路搜索树，反之，一棵平衡的3路搜索树是3阶B树。
错。

二.填空题
1. 下面程序段时间复杂度为________
for (int i=0;i<n;i++)
for (int j=0;j<k;j++ )
S+=i;

O(n*k)

2.数据结构的存储结构包括顺序，________，索引和散列四种。

链接

3.设森林T中有三棵树，第一，二，三棵树的结点个数分别为n1,n2,n3,将森林转换成二叉树后，其根结点的左子树上有________个结点。

n1-1。
森林转为二叉树之后，原第一棵树T1的根节点将成为二叉树Tn的根节点，其右子树的根节点为原来T2的根节点，左子树的节点数显然为原来T1的总结点数减去成为Tn根节点的原T1的根节点，即n1-1。

4.对二叉搜索树进行________遍历，可以得到按关键字从小到大排列的结点序列。

中序

三.选择题
1.已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为________。
A. O(1) B. O(m) C. O(n) D.O(m+n)

B。之前答错了……
已知单链表A，我们需要步进m次（即O(m)）以达到其尾节点，然后将该节点的next指向B，即可完成拼接。因此选B。

2.设有一个递归算法如下：
int fact(int n) { //n大于等于0
if(n<=0) return 1;
else return n*fact(n-1);
}
则计算fact(n)需要调用该函数的次数为________次。
A. n B. n+1 C. n+2 D.n-1

选B（取n=0，特殊情况）。

Answer 3

你 真恶心

Answer 4

哥们给的分好高啊，可惜我回答不了。