数据与算法期末试题

1. 数据结构与算法选择题！

第一题，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：例如：环形图就不满足，比如长方形，四个顶点，两种遍历都能访问到每个顶点，但不是完全图

2. 求数据结构与算法分析高人帮忙做下这几道题目。（希望能给出正确答案，在此谢过！！！）

填空题
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)即可

3. 数据结构与算法判断题

1、错。存储结构才依赖计算机
2、正确
3、正确
4、错。链式存储的插入删除效率高
5、错。顺序的结点也可以是复杂类型
6、正确
7、正确。 a进，a出，b进，b出，c进，d进，d出，c出就可得到这个输出。
8、错误。递归实际上是利用栈结构进行定义。
9、正确。

4. 求北邮数据结构和算法历年期末考题~~~~邮箱[email protected]

2005年http://wenku..com/view/87ffa663caaedd3383c4d37f.html
2006年http://wenku..com/view/fe0dd56427d3240c8447ef7f.html
数据结构的。其他年的宿舍楼下打印店也都有

5. 数据结构与算法试题，高分，求答案啊

给你第一题解法吧：后面的实在是不想做。

先根：ABCDEFGHI

中根：CBEDAGFHI

遍历的基本方法：先左子树后右子树。

1,先根遍历可以确定根节点为A,

2,依据1步，可以在中根遍历中确定左子树为：CBED,右为：GFHI

3,在可以重复1,2步。就可以得到结果。

A

BF

CDGH

I

4,O(n^3)+O(1)

6. 算法与数据结构试题 急用！！！

这是我写的顺序查找和二分查找代码
#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;
}