数据结构习题数据结构是习题解析好还是1800题好

数据结构习题时间:2021-01-09 阅读:()

数据结构习题

一、选择题 1．C 2．D 解析：A．完全二叉树可以用数组存储，树是非线性结构 B．链表且插入和删除运算效率高 C．链表也有双向链表，有两个指针域 3．A 4．A．顺序表可随机访问任一元素 5．D 6．这道题你是不是弄错了全都对啊 7．D 满二叉树：结点总数目N=2^H -1 H为数高度，求出结点总数为255 满二叉树，只有度为0 和度为2 的结点，度为0 的结点等于度为1 结点数目+1 因此选D 8．C 这题不用画图就可做出来，后序遍历序列是dabec，------》得到根节点是：c 前序遍历；根左右所以第一个一定是c 只有A项符合 9. A 虽然你没给图但是一般都是A相因为见过好多这个题中序遍历和层次遍历结果一样 10. D 11.C 12.B 在最坏情况:比较次数为___每次查找都要从第一个比较到最后一个，都要遍历N次：总的比较次数N*N,平均比较次数就是N 13. C 二、填空题 1．出栈 2．n/2+n/(n+1) 1+2+3……n+n)/(n+1)=．n/2+n/(n+1) 3．1 4．设待排数据元素的关键字为（67，24，14，22，33，15，11，15），用选择法将其按升序排序，需要比较的次数为【】。

5．13 6．11 3+6+2=11 *7．15 方法同选择题上那个满二叉树 8．无图 9. 16 和第七题一样的方法

数据结构试题

一.判断题（）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）查找。