算法与数据结构习题
❶ 数据结构与算法题需要回答
《数据结构与算法》模拟题
一、填空题：（共15分）（每空一分）
按照排序时，存放数据的设备，排序可分为<1> 排序和<2> 排序。内部排序和外部排序
图的常用的两种存储结构是<3> 和<4> 。邻接矩阵和邻接表
数据结构中的三种基本的结构形式是<5> 线性结构 和<6> 树型结构 、图型结构<7> 。
一个高度为6的二元树，最多有<8> 63 个结点。
线性查找的时间复杂度为：<9> O(n^2) ，折半查找的时间复杂度为：<10> O(nlogn) 、堆分类的时间复杂度为：<11> O(nlogn) 。
在采用散列法进行查找时，为了减少冲突的机会，散列函数必须具有较好的随机性，在我们介绍的几种散列函数构造法中，随机性最好的是<12> 随机数 法、最简单的构造方法是除留余数法<13> 。
线性表的三种存储结构是：数组、<14> 链表 、<15> 静态链表 。
二、回答下列问题：（共30分）
现有如右图的树，回答如下问题：看不见图
根结点有：
叶结点有：
具有最大度的结点：
结点的祖先是：
结点的后代是：
栈存放在数组A[m]中，栈底位置是m-1。试问：
栈空的条件是什么？top=m-1
栈满的条件是什么？top=-1
数据结构和抽象数据型的区别与联系：
数据结构（data structure)—是相互之间存在一种或多种特定关系的数据元素的集合。数据元素相互之间的关系称为结构。
抽象数据类型（ADT）：是指一个数学模型（数据结构）以及定义在该模型（数据结构）上的一组操作。
❷ 数据结构与算法的题目，怎么做
首先，要能够读懂代码，总结算法的思想，搞清楚该题算法是完成什么功能，然后是填空也好，写算法结果也好，就不成问题了。要想提高的快，就得多练啊。同时教材中的相关算法也要熟，好多是书中的原算法
1. 在计算机中，算法是指什么？
答案：解题方案的准确而完整的描述。
2. 在下列选项中，哪个不是一个算法一般应该具有的基本特征？
说明：算法的四个基本特征是：可行性、确定性、有穷性和拥有足够的情报。 答案：无穷性。
3. 算法一般都可以用哪几种控制结构组合而成？ 答案：顺序、选择、循环。 4. 算法的时间复杂度是指？
答案：算法执行过程中所需要的基本运算次数。 5. 算法的空间复杂度是指？
答案：执行过程中所需要的存储空间。 6. 算法分析的目的是？
答案：分析算法的效率以求改进。 7. 下列叙述正确的是（C）
A．算法的执行效率与数据的存储结构无关
B．算法的空间复杂度是指算法程序中指令（或语句）的条数 C．算法的有穷性是指算法必须能在执行有限个步骤之后终止 D．算法的时间复杂度是指执行算法程序所需要的时间 8. 数据结构作为计算机的一门学科，主要研究什么？
答案：主要研究数据的逻辑结构、对各种数据结构进行的运算，以及数据的存储结构。 9. 数据结构中与所使用的计算机无关的是数据的（C） A．存储结构 B．物理结构
C．逻辑结构 D．物理和存储结构 10. 下列叙述中，错误的是（B）
A．数据的存储结构与数据处理的效率密切相关 B．数据的存储结构与数据处理的效率无关
C．数据的存储结构在计算机中所占的空间不一定是连续的 D．一种数据的逻辑结构可以有多种存储结构 11. 数据的存储结构是指什么？
答案：数据的逻辑结构在计算机中的表示。 12. 数据的逻辑结构是指？
答案：反映数据元素之间逻辑关系的数据结构。
13. 根据数据结构中各数据元素之间前后件关系的复杂程度，一般将数据结构分为？ 答案：线性结构和非线性结构。
14. 下列数据结构具有记忆功能的是（C） A．队列 B．循环队列 C．栈
D．顺序表
15. 下列数据结构中，按先进后出原则组织数据的是（B） A．线性链表 B．栈
C．循环链表 D．顺序表
❸ 数据结构与算法判断题
1、错。存储结构才依赖计算机
2、正确
3、正确
4、错。链式存储的插入删除效率高
5、错。顺序的结点也可以是复杂类型
6、正确
7、正确。 a进，a出，b进，b出，c进，d进，d出，c出就可得到这个输出。
8、错误。递归实际上是利用栈结构进行定义。
9、正确。
❹ 算法与数据结构填空题
1、 3
2、 15 (2^k-1)
3、 129 (2^7-1-3+5)
4、 logn (完全二叉树最小深度)
5、 前序遍历(DLR), 中序遍历(LDR), 后序遍历(LRD)
6、 深度优先搜索法, 广度优先搜索法
7、 Kruskal算法, prim算法
8、 e, e
❺ 数据结构与算法选择题！
第一题，DFS（深度优先遍历）是一个递归算法，在遍历的过程中，先访问的点被压入栈底（栈是先进后出），再说：拓扑有序是指如果点U到点V有一条弧，则在拓扑序列中U一定在V之前。深度优先算法搜索路径恰恰是一条弧，栈的输出是从最后一个被访问点开始输出，最后一个输出的点是第一个被访问的点。所以是逆的拓扑有序序列
第二题：无向图路径长度是指两个顶点之间弧的条数，如果两顶点路径长度有2条弧，则有3个顶点例如A——B——C；
第三题：A：极小连通图是一棵生成树，只有N-1条边，但是连通分量可能有N条边，例如极小连通图A—— B——C，连通分量“A”——B——C——“A”(这里的最后一个“A”跟第一个“A”一致）：；
B:你查下极大强连通子图概念就明白了；
C:你看看第二题的例子就明白了，AC之间没有弧，但他们是一个拓扑序列；
D：例如：环形图就不满足，比如长方形，四个顶点，两种遍历都能访问到每个顶点，但不是完全图
❻ 算法与数据结构试题 急用！！！
这是我写的顺序查找和二分查找代码
#include<iostream.h>
#define elemtype int
int sqsearch(elemtype a[],int n,elemtype x); //顺序查找
int sqsearch2(elemtype a[],int n,elemtype x); //顺序查找，打印查找过程
int binsearch(elemtype a[],int n,elemtype x); //折半查找
int binsearch2(elemtype a[],int n,elemtype x); //折半查找，打印查找过程
void printarray(elemtype a[],int n); //打印数组数据
int main()
{
int i,x;
const int n=9;
elemtype a1[10]={0,34,23,12,56,90,78,89,45,67};
elemtype a2[10]={0,12,23,34,45,56,67,78,89,90};
//顺序查找
cout<<"顺序查找："<<endl;
cout<<"a1[]=";
printarray(a1,n);
cout<<"输入要查找的数据：";
cin>>x;
if((i=sqsearch(a1,n,x))>0) //找到
cout<<"找到x==a1["<<i<<"]"<<endl;
else //未找到
cout<<"找不到"<<x<<endl;
cout<<endl<<"查找过程："<<endl;
sqsearch2(a1,n,x); //查找过程
cout<<"完成顺序查找！"<<endl;
//二分法查找
cout<<"二分法查找："<<endl;
cout<<"a2[]=";
printarray(a2,n);
cout<<"输入要查找的数据：";
cin>>x;
if((i=binsearch(a2,n,x))>0) //找到
cout<<"找到x==a1["<<i<<"]"<<endl;
else //未找到
cout<<"找不到"<<x<<endl;
cout<<endl<<"查找过程："<<endl;
binsearch2(a2,n,x);
cout<<"完成顺序查找！"<<endl;
return 0;
}
//在数组a[1.2...n]中顺序查找x
//找到时返回元素下标，否则返回0
int sqsearch(elemtype a[],int n,elemtype x) //a[]是数组，n是元素个数，x是要查找的数
{
int i;
if(a[0]==x)
return 1;
else
{
a[0]=x;
for(i=n;!(a[i]==x);--i); //若找到则i大于0
return i;
}
}
//在数组a[1.2...n]中顺序查找x,打印每次比较结果
//找到时返回元素下标，否则返回0
int sqsearch2(elemtype a[],int n,elemtype x) //a[]是数组，n是元素个数，x是要查找的数
{
int i;
a[0]=x;
for(i=n;!(a[i]==x);--i)
if(a[i]>x)
cout<<a[i]<<">"<<x<<endl;
else
cout<<a[i]<<"<"<<x<<endl;
return i;
}
//在数组a[1.2...n]中二分法查找x
//找到时返回元素下标，否则返回0
//前提：a[1.2...n]是非递减有序的
int binsearch(elemtype a[],int n,elemtype x) //二分查找
{
int mid,low=1,high=n;
while(low<=high)
{
mid=(low+high)/2;
if(x==a[mid])
return mid;
else if(x<a[mid])
high=mid-1;
else
low=mid+1;
}
return 0;
}
//在数组a[1.2...n]中二分法查找x，每次打印比较结果
//找到时返回元素下标，否则返回0
//前提：a[1.2...n]是非递减有序的
int binsearch2(elemtype a[],int n,elemtype x) //查找过程
{
int mid,low=1,high=n;
while(low<=high)
{
mid=(low+high)/2;
if(x==a[mid])
{
cout<<a[mid]<<"="<<x<<endl;
return mid;
}
else if(x<a[mid])
{
cout<<a[mid]<<">"<<x<<endl;
high=mid-1;
}
else
{
cout<<a[mid]<<"<"<<x<<endl;
low=mid+1;
}
}
return 0;
}
//打印顺组数据a[1....n]
void printarray(int a[],int n)
{
int i;
cout<<"{";
for(i=0;i<=n;i++)
{
cout<<a[i];
while(i<n)
{
cout<<",";
break;
}
}
cout<<"}"<<endl;
}
❼ 求数据结构与算法分析高人帮忙做下这几道题目。（希望能给出正确答案，在此谢过！！！）
填空题
1. n-1
因为队尾指针总是指向空。
2. 1
因为无向图的邻接矩阵是对称的。
3. 61
元素数量=
(rear+max-front) 当front > rear
(front+max-rear) 当rear > front
4. 深度优先搜索算法
5.
判断题
1. F
二叉树就可以用数组存储。
2. F
当发生冲突时，它要在下一个位置找，但如果该位置已被占用，仍需要继续向前。故同
义词不一定相邻。
3. F
图的邻接矩阵的行列数只取决于顶点数量。
4. F
没有最快的排序算法，只有特定条件下的相对较快。
5. T
选择题
1. D
2. B
Loc(a[6]) = Loc(a[1]) + (6-1)*2
= 90 + 10 =100
3. A
4. C
5. C
进堆排序时，每个元素在最底下的叶子层都有，然后较大的非叶子结点存储。
6. C
构造一棵二叉树：
/
* +
A + - F
B C D E
对该二叉树进行后序遍历即可。
7. C
折半查找要求查找表有序，并且可以根据下标定位，要求是直接存取。
顺序存储方式：可直接存取，但插入删除需耗时间
链式存储方式：只能顺序存取，插入删除方便
8. D
二次探测再散列法：
addr(key) = (初始哈希值+di)%表长
di=1、-1、4、-4、9、-9...
addr(15) = 15 % 11 = 4
addr(38) = 38 % 11 = 5
addr(61) = 61 % 11 = 6
addr(84) = 84 % 11 = 7
addr(49) = 49 % 11 = 5 有冲突
addr(49) = (5+1)%14=6 有冲突
addr(49) = (5-1)%14=4 有冲突
addr(49) = (5+4)%14=9
9. D
执行p的后继指针(next)指向p的直接后继结点(next)的下一个结点(next)即可