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
可乐答的不错。可以保证。我做的结果一样。
本章介绍的是栈和队列的逻辑结构定义及在两种存储结构(顺序存储结构和链式存储结构)上如何实现栈和队列的基本运算。本章的重点是掌握栈和队列在两种存储结构上实现的基本运算，难点是循环队列中对边界条件的处理。
--------------------------------------------------------------------------------
1.栈的逻辑结构、存储结构及其相关算法(综合应用):
栈的逻辑结构和我们先前学过的线性表相同，如果它是非空的，则有且只有一个开始结点，有且只能有一个终端结点，其它的结点前后所相邻的也只能是一个结点(直接前趋和直接后继),但是栈的运算规则与线性表相比有更多的限制，栈(Stack)是仅限制在表的一端进行插入和删除运算的线性表，通常称插入、删除这一端为栈顶，另一端称为栈底。表中无元素时为空栈。栈的修改是按后进先出的原则进行的，我们又称栈为LIFO表(Last In First Out).
栈的基本运算有六种：
构造空栈：InitStack(S)、
判栈空: StackEmpty(S)、
判栈满： StackFull(S)、
进栈： Push(S,x)、可形象地理解为压入，这时栈中会多一个元素
退栈： Pop(S) 、 可形象地理解为弹出，弹出后栈中就无此元素了。
取栈顶元素：StackTop(S),不同与弹出，只是使用栈顶元素的值，该元素仍在栈顶不会改变。
--------------------------------------------------------------------------------
由于栈也是线性表，因此线性表的存储结构对栈也适用，通常栈有顺序栈和链栈两种存储结构，这两种存储结构的不同，则使得实现栈的基本运算的算法也有所不同。
--------------------------------------------------------------------------------
我们要了解的是，在顺序栈中有"上溢"和"下溢"的概念。顺序栈好比一个盒子，我们在里头放了一叠书，当我们要用书的话只能从第一本开始拿(你会把盒子翻过来吗?真聪明^^)，那么当我们把书本放到这个栈中超过盒子的顶部时就放不下了(叠上去的不算，哼哼)，这时就是"上溢","上溢"也就是栈顶指针指出栈的外面，显然是出错了。反之，当栈中已没有书时，我们再去拿，看看没书，把盒子拎起来看看盒底，还是没有，这就是"下溢"。"下溢"本身可以表示栈为空栈,因此可以用它来作为控制转移的条件。
链栈则没有上溢的限制，它就象是一条一头固定的链子，可以在活动的一头自由地增加链环(结点)而不会溢出，链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要在头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。
以上两种存储结构的栈的基本操作算法是不同的，我们主要要学会进栈和退栈的基本算法以解决简单的应用问题。
--------------------------------------------------------------------------------
2.队列的逻辑结构、存储结构及其相关算法(综合应用)。
队列(Queue,念Q音)也是一种运算受限的线性表，它的运算限制与栈不同，是两头都有限制，插入只能在表的一端进行(只进不出)，而删除只能在表的另一端进行(只出不进)，允许删除的一端称为队尾(rear)，允许插入的一端称为队头 (Front)
,队列的操作原则是先进先出的，所以队列又称作FIFO表(First In First Out)
队列的基本运算也有六种：
置空队 ：InitQueue(Q)
判队空： QueueEmpty(Q)
判队满： QueueFull(Q)
入队 ： EnQueue(Q,x)
出队 ： DeQueue(Q)
取队头元素： QueueFront(Q),不同与出队，队头元素仍然保留
--------------------------------------------------------------------------------
队列也有顺序存储和链式存储两种存储结构，前者称顺序队列，后者为链队。
对于顺序队列，我们要理解"假上溢"的现象。
我们现实中的队列比如人群排队买票，队伍中的人是可以一边进去从另一头出来的，除非地方不够，总不会有"溢出"的现象，相似地，当队列中元素完全充满这个向量空间时，再入队自然就会上溢，如果队列中已没有元素，那么再要出队也会下溢。
那么"假上溢"就是怎么回事呢?
因为在这里，我们的队列是存储在一个向量空间里，在这一段连续的存储空间中，由一个队列头指针和一个尾指针表示这个队列，当头指针和尾指针指向同一个位置时，队列为空，也就是说，队列是由两个指针中间的元素构成的。在队列中，入队和出队并不是象现实中，元素一个个地向前移动，走完了就没有了,而是指针在移动，当出队操作时，头指针向前(即向量空间的尾部)增加一个位置，入队时，尾指针向前增加一个位置，在某种情况下，比如说进一个出一个，两个指针就不停地向前移动，直到队列所在向量空间的尾部，这时再入队的话，尾指针就要跑到向量空间外面去了，仅管这时整个向量空间是空的，队列也是空的，却产生了"上溢"现象，这就是假上溢。
为了克服这种现象造成的空间浪费，我们引入循环向量的概念，就好比是把向量空间弯起来，形成一个头尾相接的环形，这样，当存于其中的队列头尾指针移到向量空间的上界(尾部)时，再加1的操作(入队或出队)就使指针指向向量的下界，也就是从头开始。这时的队列就称循环队列。
通常我们应用的大都是循环队列。由于循环的原因，光看头尾指针重叠在一起我们并不能判断队列是空的还是满的，这时就需要处理一些边界条件，以区别队列是空还是满。方法至少有三种，一种是另设一个布尔变量来判断(就是请别人看着，是空还是满由他说了算)，第二种是少用一个元素空间，当入队时，先测试入队后尾指针是不是会等于头指针，如果相等就算队已满，不许入队。第三种就是用一个计数器记录队列中的元素的总数，这样就可以随时知道队列的长度了，只要队列中的元素个数等于向量空间的长度，就是队满。
以上是顺序队列，我们要掌握相应算法以解决简单应用问题。
--------------------------------------------------------------------------------
队列的链式存储结构称为链队列，一个链队列就是一个操作受限的单链表。为了便于在表尾进行插入(入队)的操作，在表尾增加一个尾指针，一个链队列就由一个头指针和一个尾指针唯一地确定。链队列不存在队满和上溢的问题。在链队列的出队算法中，要注意当原队中只有一个结点时，出队后要同进修改头尾指针并使队列变空。
--------------------------------------------------------------------------------
3.栈和队列的应用(领会)
教材中举了几个例子，对于我们初学者来说，看上去比较繁，我们只要掌握一点，那就是，对于什么情况下用栈和队列作为解决问题的数据结构。
判断的要点就是：如果这个问题满足后进先出(LIFO)的原则，就可以使用栈来处理。如果这个问题满足先进先出(FIFO)的原则，就可以使用队列来处理。
比如简单的说，有一个数组序列，我们输入时按顺序输入，但是输出时需要逆序输出，那么它就可以利用栈来处理，把这个数组存入一个栈中就可以容易地按逆序输出结果了
假溢出是是队列在一端进入插入，TOP值就会增加，在另一端删除，当判断TOP==MAX-1是，就会说明已经队满，但实际在队列的另一端还是有存储空间的，这就是“假溢出”。
解决方法：设置队列为循环队列就可以了。TOP=（TOP+1）MOD （MAX-1）。
下面是一个实例， 不过这个实现会浪费一个元素的存储空间。如果不想浪费队列的存储空间， 就需要设置一个监视变量。
public class Queue {
private T[] queue;
private int front;
private int rear;
public Queue(T[] q){
this.queue = q;
this.front = 0;
this.rear = 0;
}
public boolean enqueue(T t){
if(!isFull()){
queue[rear] = t;
rear = (rear + 1) % queue.length;
return true;
}else{
throw new UnsupportedOperationException("Queue is full!");
}
}
public T dequeue(){
if(!isEmpty()){
T v = queue[front];
front = (front + 1) % queue.length;
return v;
}else{
throw new UnsupportedOperationException("Queue is empty!");
}
}
public boolean isEmpty(){
if(front == rear){
return true;
}else{
return false;
}
}
public boolean isFull(){
if(front == ((rear + 1) % queue.length)){
return true;
}else{
return false;
}
}
}
数据结构试题,求解答。(很重要,不会就别乱回答了。会追加分的,万分感谢...
5、我知道的快速排序版本就有3个，虽然算法几乎一摸一样的，不过对作支点的那个数的位置的互换略有不同，那么每轮的结果自然不一样，我好不容易找到原版教材的算法，是机械工业出版社的《数据结构、算法与应用 ——c++语言描述》版，但愿是一样的算法 1）、以46为支点 ：78，29 ——46，25，29...
数据结构试题,麻烦告诉我怎么算的和答案
只存储非0元素，行优先时，第i行第k个元素相对于整体是第i*(i-1)\/2+k个，第一个地址为1000，则第2个为1001，相应的第i*(i-1)\/2+k个为1000+i*(i-1)\/2+k-1，我相信你能算出a[8][5]的地址了
数据结构试题
答案是 度数为3的结点有14个。假设：三叉树中度为3的结点x个， 度为2的结点y个，度为1的结点z个，度为0的结点m个,总结点数sum sum = x+y+z+m 从另外一个角度看，除了根节点，树的每个结点上方都关联一个分支，所以总结点数sum=分支数+1= 3x+2y+z+1（因为度数为3的结点有3个分支...
数据结构高手进,帮忙答下题
一、1、B 2、B 3、 ?4、C 《 A的深度为1，B的深度为3，D的深度为3》5、C 6、B?7、C 8、B 直接插入排序 ：n个不同的数据元素，最多需要比较n*(n-1)\/2 9、C 10、A 二、1.线性结构 ，非线性结构 。2. 352 < 100+ (6*20+6)*2 > ， 232 ...
数据结构试题麻烦各位会的朋友看一下
中缀算式（3+4X）-2Y\/3的4X和2Y应该是4*X、2*Y，即应理解为：（3+4*X）-2*Y\/3 其为：3 4 X*+2Y*3\/- 前缀表达式，就是把运算符放在前面、操作数放在后面。中缀表达式，就是把运算符放在两个操作数之间，即常见的算术运算表达式。后缀表达式，就是把操作数放在前面、运算符放在后面。以...
一道简单的数据结构考试题,学的东西基本都还老师了。。。那位能不吝赐 ...
（1）知道先序序列和中序序列也可以确定一个树的结构 （2）知道先序序列和后续序列不可以确定一颗树的结构，因为只能确定根，不能确定左右子树。这里列举一个反例：A --B --F print_pre_order : A B F print_post_order : F B A print_in_order : F B A --F --B A print_pre_...
数据结构试题求解
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,将森林转换成二叉树后，其根结点的左子树上有___个结点。
数据结构试题求解
选择题 ( )1.设有两个长度为n的单向链表，结点类型相同。若以H1为表头指针的链表是非循环的，以H2为表头指针的链表是循环的，则___。A. 对于两个链表来说，删除第一个结点的操作，其时间复杂度都是O（1）。B. 对于两个链表来说，删除最后一个结点的操作，其时间复杂度都是O（n）。C.循环链...
求以下试题(数据结构)的详细答案~谢谢啦
1.中序遍历是左根右，中间是根；前序遍历前面是根左右，前面是根。 原理不细说了，递归，先结束的先输出。这里的根是指相对的根，一边看图吧，光说不好描述。由A找到中序的位置，所以BFD是A的左子树，EGC在A的右子树，以此类推。。。2.二叉排序树 只要保证左边都小，右边都大。。3.归并：两...
求数据结构期末测试题一套
一、单选题 1. 以下数据结构中哪一个是线性结构？( )A. 有向图 B. 栈 C. 线索二叉树 D. B树 2. 在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行( )。A. HL=p; p->next=HL; B. p->next=HL; HL=p;C. p->next=HL; p=HL; D. p...