数据算法题
❶ 数据结构算法题
int BTreeCount(BinTreeNode* BT, char x){
if(BT){
if(BT->data>x) return BTreeCount(BT->left,x)+BTreeCount(BT->right,x)+1;
else return BTreeCount(BT->left,x)+BTreeCount(BT->right,x);
}}
❷ 求数据结构与算法分析高人帮忙做下这几道题目。（希望能给出正确答案，在此谢过！！！）
填空题
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)即可
❸ 数据结构与算法选择题
1.A
存取任一指定序号，用顺序表最方便，在最后进行插入和删除运算，顺序表也可以方便的实现。
2.C
第一个是5，第二个是4，都可以，表示5、4是最后进栈的，之后再要出栈1，不可能
3.D
4.C
5.A
生成树
6.D
二分查找的前提是该查找必须是顺序存储的有序表
7.C
8.不清楚
9.B
abc,cba正好倒过来。
10.B
❹ 有三道数据结构算法与分析的题不太明白，求助达人帮忙。在此十分感谢！！！
1 根据一组记录（56，42，50，64，48）依次插入结点生成一棵AVL树，当插入到值为___50___的结点时需要进行旋转调整。
2、函数实现单链表的删除算法，请在空格处将算法补充完整。
int ListDelete(LinkList L,int i,ElemType *s){
LNode *p,*q;
int j;
p=L;j=0;
while(( p->next__)&&(j<i-1)){
p=p->next;j++;
}
if(p->next==NULL||j>i-1) return ERROR;
q=p->next;
p->next=q->next ;
*s=q->data;
free(q);
return OK;
}/*listDelete*/
____p->next____ ； _____p->next=q->next ____
3、描述下面算法的功能
int fun(sqstring *s,sqstring *t,int start)
{ int i=start-1,j=0;
while(i<s->len&&j<t->len)
if(s->data[i]==t->data[j]){
i++;j++;
}
else{
i=i-j+1;j=0;
}
if(j>=t->len)
return i-t->len+1;
else
return -1;
}
这是字符串的模式匹配。在主串S中寻找与子串T匹配的串，如果找到匹配的串，就返回这个子串的首元素下标值，否则返回-1
❺ 数据结构算法 试题 急！ 试构造下图的最小生成树，要求分步给出构造过程。
图有如下参数:
边数=8顶点数=5
顶点顶点边的权值
v1v26
v1v34
v1v42
v2v35
v2v48
v2v56
v3v45
v4v57
用Kruskal(克鲁斯卡尔)算法,求最小生成树.
先将所有边的权值按照从小到大排序:
顶点顶点边的权值
v1v42
v1v34
v2v35
v3v45
v1v26
v2v56
v4v57
v2v48
然后,每次提取权值最小边,逐步组成最小生成树:
(1)取最小边(v1,v4,2)
v1--v4
(2)取边(v1,v3,4),不会产生环路.
v1--v4
|
|
v3
(3)取边(v2,v3,5),不会产生环路.
v1--v4
|
|
v3--v2
(4)如果取边(v3,v4,5),会产生环路,所以不能取.
如果取边(v1,v2,6),会产生环路,所以不能取.
取边(v2,v5,6),不会产生环路.
v1--v4
|
|
v3--v2--v5
这就是最小生成树,连通了所有顶点,总权值最小.
顶点边的权值
(v1,v4)2
(v1,v3)4
(v2,v3)5
(v2,v5)6
//C语言测试程序
//最小生成树Kruskal(克鲁斯卡尔)算法
#include"stdio.h"
#defineMAXEDGE20
#defineMAXVEX20
#defineINF65535
typedefstruct
{
intarc[MAXVEX][MAXVEX];
intnumVertexes,numEdges;
}MGraph;
typedefstruct
{
intbegin;
intend;
intweight;
}Edge;//对边集数组Edge结构的定义
//创建图
voidCreateMGraph(MGraph*G)
{
inti,j;
G->numEdges=8;//边数
G->numVertexes=5;//顶点数
for(i=0;i<G->numVertexes;i++)//初始化图
{
for(j=0;j<G->numVertexes;j++)
{
if(i==j)
G->arc[i][j]=0;
else
G->arc[i][j]=G->arc[j][i]=INF;
}
}
G->arc[0][1]=6;
G->arc[0][2]=4;
G->arc[0][3]=2;
G->arc[1][2]=5;
G->arc[1][3]=8;
G->arc[1][4]=6;
G->arc[2][3]=5;
G->arc[3][4]=7;
for(i=0;i<G->numVertexes;i++)
{
for(j=i;j<G->numVertexes;j++)
{
G->arc[j][i]=G->arc[i][j];
}
}
}
//交换权值以及头和尾
voidSwapn(Edge*edges,inti,intj)
{
inttemp;
temp=edges[i].begin;
edges[i].begin=edges[j].begin;
edges[j].begin=temp;
temp=edges[i].end;
edges[i].end=edges[j].end;
edges[j].end=temp;
temp=edges[i].weight;
edges[i].weight=edges[j].weight;
edges[j].weight=temp;
}
//对权值进行排序(选择排序法)
voidsort(Edgeedges[],MGraph*G)
{
inti,j,min;
for(i=0;i<(G->numEdges-1);i++)
{
min=i;
for(j=i+1;j<G->numEdges;j++)
{
if(edges[min].weight>edges[j].weight)
{
min=j;
}
}
if(i!=min)
{
Swapn(edges,i,min);
}
}
printf("边的权值排序之后: ");
for(i=0;i<G->numEdges;i++)
{
printf("(%d,%d)%d ",edges[i].begin,edges[i].end,edges[i].weight);
}
}
//查找连线顶点的尾部下标
intFind(int*parent,intf)
{
while(parent[f]>0)
{
f=parent[f];
}
returnf;
}
//生成最小生成树
voidMiniSpanTree_Kruskal(MGraphG)
{
inti,j,n,m;
intk=0;
intparent[MAXVEX];//定义一数组用来判断边与边是否形成环路
Edgeedges[MAXEDGE];//定义边集数组,edge的结构为begin,end,weight,均为整型
//用来构建边集数组并排序
for(i=0;i<G.numVertexes-1;i++)
{
for(j=i+1;j<G.numVertexes;j++)
{
if(G.arc[i][j]<INF)
{
edges[k].begin=i;
edges[k].end=j;
edges[k].weight=G.arc[i][j];
k++;
}
}
}
sort(edges,&G);//从小到大排序
for(i=0;i<G.numVertexes;i++)
{
parent[i]=0;
}
printf("打印最小生成树： ");
for(i=0;i<G.numEdges;i++) //循环每一条边
{
n=Find(parent,edges[i].begin);
m=Find(parent,edges[i].end);
if(n!=m)//假如n与m不等，说明此边没有与现有的生成树形成环路
{
parent[n]=m; //将此边的结尾顶点放入下标为起点的parent中
//表示此顶点已经在生成树集合中
printf("(%d,%d)%d ",edges[i].begin,edges[i].end,edges[i].weight);
}
}
}
intmain(void)
{
MGraphG;
CreateMGraph(&G);
MiniSpanTree_Kruskal(G);
return0;
}
❻ 数据结构与算法题需要回答
《数据结构与算法》模拟题
一、填空题：（共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）：是指一个数学模型（数据结构）以及定义在该模型（数据结构）上的一组操作。
❼ 数据结构与算法试题，高分，求答案啊
给你第一题解法吧：后面的实在是不想做。
先根：ABCDEFGHI
中根：CBEDAGFHI
遍历的基本方法：先左子树后右子树。
1,先根遍历可以确定根节点为A,
2,依据1步，可以在中根遍历中确定左子树为：CBED,右为：GFHI
3,在可以重复1,2步。就可以得到结果。
A
BF
CDGH
I
4,O(n^3)+O(1)
