数据结构试题求解

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.某线性表采用顺序存储结构，元素长度为4，首地址为100，则下标为12的（第13个）元素的存储地址为148。
正确。第0个元素地址为100，则第i个元素地址为100+4*i，将12代入得148。
（ ）2.在任何一种线性链表上都无法进行随机访问。
错误。比如只要知道顺序表首地址和每个数据元素所占存储单元的个数，就可以求出第i个数据元素的存储地址来，这也是顺序表具有按数据元素的序号随机存取的特点。
（ ）3.顺序栈是一种规定了元素进栈顺序的栈。
错误。按存储结构来分，堆栈分为顺序栈和链栈，其中栈的顺序存储结构简称为顺序栈，它是运算受限的顺序表，却并没有规定元素进栈顺序。
（ ）4.循环列表中每一个元素都有后继。
正确。注意，这里可能有笔误，应写为“循环链表”而非“循环列表”。
（ ）5.删除一个二叉树中的一个结点，再重新插入上去，一定能得到原来的二叉排序树。
错误。
二.填空题。
6.下面程序的时间复杂度为___________。
for (int i=1; i<=m; i++)
for (int j=1; j<=n; j++ )
S+=i
法则1：for循环：一个for循环的运行时间至多是该for循环内语句（包含测试）的运行时间乘以迭代的次数。
法则2：嵌套循环：从里向外分析这些循环。在一组嵌套循环内部的一条语句总的运行时间为该语句的运行时间乘以该组所有循环的大小的乘积。
对于此处嵌套的for循环，根据以上法则，时间复杂度为O(m*n)。
7.在长度为n的顺序表的第i（1≤i≤n+1）个位置上插入一个元素，元素的移动次数是____________。
从第i个元素（原来的）到第n个元素，每个元素后移一位，一共需要n+1-i次。
8.在一个具有n个结点的有序单链表中插入一个新结点，并让插入后的单链表仍然有序，则该操作的时间复杂性数量级为______。
找到节点位置，O(n)；单链表插入操作，O(n)；总的时间复杂度为O(n+n)=O(n)。
9.若用s[1]～s[n]作为两个顺序栈的共同存储空间，左右两个栈的栈顶分别为t1和t2，则判断某个栈是否可以插入新元素的条件是_________________。
当程序中同时使用两个栈时，可以将两个栈的栈底设在向量空间的两端，让两个栈各自向中间延伸。当一个栈里的元素较多，超过向量空间的一半时，只要另一个栈的元素不多，那么前者就可以占用后者的部分存储空间。
此处判断某个栈是否可以插入新元素的条件是&t1!=&t2
10.设森林T中有三棵树，第一，二，三棵树的结点个数分别为n1,n2,n3,将森林转换成二叉树后，其根结点的左子树上有____________个结点。
将一个森林转换为二叉树的具体方法是：① 将森林中的每棵树变为二叉树；② 因为转换所得的二叉树的根结点的右子树均为空，故可将各二叉树的根结点视为兄弟从左至右连在一起，就形成了一棵二叉树。
个人认为此处可以填3个答案，n1-1或者n2-1或者n3-1。
11.在带权值有向图的邻接矩阵中，第i行上非零元素的个数等于_______________。
当节点Vi与某节点Vj相邻接,则A(i,j)取非0值。
12.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是_____________。
散列（Hash）查找。

数据的逻辑结构分为哪四种?

逻辑结构有四种基本类型：集合结构、线性结构、树状结构和网络结构。
1、集合结构：集合结构的集合中任何两个数据元素之间都没有逻辑关系，组织形式松散。
2、线性结构：线性结构指的是数据元素之间存在着“一对一”的线性关系的数据结构。
3、树状结构：树状结构是一个或多个节点的有限集合。
4、网络结构：网络结构是指通信系统的整体设计，它为网络硬件、软件、协议、存取控制和拓扑提供标准。

扩展资料：
线性结构中的结点按逻辑关系依次排列形成一个“锁链”。必存在唯一的一个"第一个元素"和唯一的一个"最后的元素"。除最后元素之外，其它数据元素均有唯一的"后继"；除第一元素之外，其它数据元素均有唯一的"前驱"。
树形结构具有分支、层次特性，其形态有点象自然界中的树。网络结构广泛采用的是国际标准化组织（ISO）在1979年提出的开放系统互连（OSI-Open System Interconnection)的参考模型。

数据结构题，急，悬赏高分

1B 2C 3C 4D 5C 6A 7D 8A 9A 问题补充： 10B 11A 12C 13 2,4,(((),y))) 14 请注意看一下这题,因为这题你可能打错了,因为少了一个左括号,或者是多了一个右括号.你检查一下此题吧. 15 cdbgfea 16 2*m-1,∟log2N」+1（这个答案不好以符号形似打出来，是log以2为底N的对数向下取整后加1） 17 ?（不知道） 18 n-1,n*(n-1)/2 19 得看你们的书上数组第一个元素下标是从00开始还是从11开始，如果是你们书上下标是从00开始，则答案是：340；如果下标从11开始，则答案是：300。不过一般情况下，书上都是从00开始的。 20 50％

数据结构算法设计题 设计在单链表中删除值相同的多余结点的算法

搞一个指针指向头结点，然后另一个指针开始遍历链表，然后和第一个指针指向的节点所包含的数据比较，相同就把第二个指针指向的节点删掉，后面的接上。第二个指针遍历到尾后，和第一个指针同时指向头节点后一个节点，第二个指针开始继续遍历