数据结构问题求解

Question

题目比较多，希望有人解答一下了，能答几道是几道吧，回答最多的给分酬谢。
感谢大家！

一.判断题。
（ ）1.栈和队列都不适合用散列存储法存储。
（ ）2.如果树用二叉树链表表示，则判断某个结点是不是树叶的条件是该结点左，右两个指针域的值都为空。
（ ）3.一组关键码已完全有序时，最快的排序方法是快速排序。
（ ）4.9阶B-树中，除根以外的任何一个非叶子结点中的关键字数目均在5～9之间。

二.填空题.
5.带头结点的循环链表L为空表的条件是___________
6.在单链表中，删除指针p所指结点的后继结点的语句序列是_________。
7.若一个栈的输入序列为1，2……，n,则其输出序列的第2个元素为n的输出序列的种数是____________。
8.s1=“my”， s2=“ ” ,s 3=“computer”，则s1，s2和s3连接后的结果是________________。
9.具有10个结点的二叉树的深度最多为（树根编号从0开始）___________。
10.已知二叉树有50个叶子结点，则此二叉树至少有____________个结点。
11.在_______________线索二叉树中，有可能每个结点的右孩子指针域都不为空。
12.可以进行拓扑排序的有向图一定是__________。
呵呵，很高兴在这里和大家交流一下了。我是在准备考研，不过考的是个二类大学了，所以题目比较基础吧，只是我的基础不太好了，^_^。

真的很感谢所有答题的朋友，耽误大家宝贵的时间了。可惜最佳答案只有一个了，不过这段时间里我还会继续请教的，分数也都会给到200分的，真心希望大家能够继续给予指导了：

http://zhidao.baidu.com/question/41403121.html

Answer 1

一.判断题。
（ ）1.栈和队列都不适合用散列存储法存储。
错。线性表数据的四种基本存储方法包含：顺序存储，链接存储，索引存储，散列存储。其中散列存储，就是根据结点的关键字直接计算出该结点的存储地址。

（ ）2.如果树用二叉树链表表示，则判断某个结点是不是树叶的条件是该结点左，右两个指针域的值都为空。
中文语法错误。应该写成“则判断某个结点是不是树叶的条件是该结点左，右两个指针域的值是否都为空。”

（ ）3.一组关键码已完全有序时，最快的排序方法是快速排序。
正确。所有基于比较方法的排序方法的时间下界不会低于O(nlogn)。这个结论的具体证明，请参考有关算法的书籍，例如《算法导论》第8章。快速排序在理想情况下，能严格地达到O(nlogn)的下界。

（ ）4.9阶B-树中，除根以外的任何一个非叶子结点中的关键字数目均在5～9之间。
正确。B-树是一种非二叉的查找树。它除了要满足查找树的特性，还要满足以下结构特性：一棵M阶的B-树，（1） 树的根或者是一片叶子（一个节点的树），或者其儿子数在2和M之间。（2） 除根外，所有的非叶子节点的孩子数在M/2和M之间。（3），所有的叶子节点都在相同的深度。

二.填空题.
5.带头结点的循环链表L为空表的条件是___________
L==L->nxt==L->pre==NULL; // 实际使用应写成条件并列式（使用“&&”）

6.在单链表中，删除指针p所指结点的后继结点的语句序列是_________。
tmp = p; do { tmp=tmp->nxt; delData(tmp); } while(tmp!=NULL); p->nxt = NULL;

7.若一个栈的输入序列为1，2……，n,则其输出序列的第2个元素为n的输出序列的种数是____________。
0 // 可能有问题

8.s1=“my”， s2=“ ” ,s 3=“computer”，则s1，s2和s3连接后的结果是________________。
"my computer"

9.具有10个结点的二叉树的深度最多为（树根编号从0开始）___________。
9

10.已知二叉树有50个叶子结点，则此二叉树至少有____________个结点。
(50-1)x2+1 = 99

11.在_______________线索二叉树中，有可能每个结点的右孩子指针域都不为空。
中序遍历的

12.可以进行拓扑排序的有向图一定是__________。
无回路的图

Answer 2

1、对。栈和队列只允许访问两头的数据，不适合散列存储
2、对。
3、错。应该是冒泡排序。只需要从头到尾比较一遍，不涉及到交换操作，时间是O(n)
4、错。注意看“风骚的可乐”的解释，5-9是非叶结点的孩子数目，对应的关键字数目就是4-8.
5、(L==L->next)&&(L==L->prior)
6、if(p->next) p->next=p->next->next
7、输出的第2个是N，则前N-1个只有1个先出来，所以有N-1种
8、my computer
9、9。每层只有1个结点，就相当于一条链
10、99个。根据二叉树性质，度为2的结点数目为度为0的结点数目减1，50-1=49。而度为1的结点数目不明。
11、后序。每个结点的右孩子域都不为空，则说明叶结点必然不在遍历序列的末尾，所以是后序遍历
12、无有向环。

Answer 3

一.
1.错.
2.对.
3.对.
4.不知道.
二.
5.(L==L->next)&&(L==L->prior)
6.__ P->next= P->next ->next _。
7. i-j-1
8.不知道
9.最多为10
10.至少有6吧
11.无回路的图吧.
你考研究生吧.
好难呀..汗死啦..强烈要求加分哦.

Answer 4

一
1、错
2、对
3、错
4、对
二
5、L->next == L
6、u=p->next;p->next=u->next;free(u)
7、n-1
8、my computer
9、9
10、99
11、中序
12、有向无环图

要解答的发短消息给我。

Answer 5

8，my computer
为顺序结构！