数据结构与算法应用真题_《数据结构,算法与应用》

艾丽游戏ing 2023-12-05 18:40 1

数据结构与算法选择题！

第一题是应该选D

最坏的情况下蜕变为单支树树的深度为n 那么其平均查找长度为(n+1)/2

跟顺序查找是相同的

第二题没看懂。。

baidu

数据结构与算法求高手作答.感激不敬

第1题

题目类型：单选题

题目：数据结构主要研究（ 4 ）

可选答案:

1.数据的逻辑结构

2.数据的存储结构

3.数据的逻辑结构和存储结构

4.数据的逻辑结构、存储结构以及数据在操作上的实现

第2题

题目类型：单选题

题目：由于数据的逻辑结构通过不同的存储映像方法可得到不同的存储结构，常见的数据存储结构没有（3）。

可选答案:

1.邻接存储结构

2.顺序存储结构

3.索引存储结构

4.散列存储结构

第3题

题目类型：单选题

题目：我们在讨论某种数据结构时，主要讨论四个方面的问题，①数据的逻辑结构②数据的存储结构③在数据的逻辑结构上定义的数据的基本操作；④基本操作算法的具体实现；这四个问题的讨论的先后顺序应该是怎样的？（1）

可选答案:

1.①②③④

2.①③②④

3.②①③④

4.②①④③

第4题

题目类型：单选题

题目：线性链表是通过何种方式表示元素之间的关系 ( 1 )

可选答案:

1.后继元素地址

2.元素的存储顺序

3.左、右孩子地址

4.元素的相对存储位置

第5题

题目类型：单选题

题目：用线性链表存储线性表时，要求存储空间 (2)

可选答案:

1.必须是连续的

2.连续不连续都可以

3.部分元素的存储空间必须是连续的

4.必须是不连续的

第6题

题目类型：单选题

题目：对于经常要存取线性表任意指定位置元素的应用，线性表应采用 (1) 存储结构。

可选答案:

1.顺序存储结构

2.链式存储结构

3.线性链表

4.栈

第7题

题目类型：单选题

题目：具有线性结构的数据结构是( 2 )

可选答案:

赫夫曼树

2.栈

3.图

4.树

第8题

题目类型：单选题

题目：一个栈的入栈序列是abcde，则栈的不可能的输出序列是（3 ）。

可选答案:

1.edcba

2.decba

3.dceab

4.abcde

第9题

题目类型：单选题

题目：向一个栈顶指针为HS的链栈中将一个S指针所指的结点入栈，执行（2 ）。

可选答案:

1.HS->next=s

2.S->next=HS->next;HS->next=s

S->next=HS;HS=s

4.S->next=HS;HS=HS->next

第10题

题目类型：单选题

题目：下列说法正确的是 (2)

可选答案:

1.堆栈是在两端操作、先进后出的线性表

2.堆栈是在一端操作、先进后出的线性表

3.队列是在一端操作、先进先出的线性表

4.队列是在两端操作、后进先出的线性表

数据结构算法试题急！试构造下图的最小生成树，要求分步给出构造过程。

图有如下参数:

边数=8 顶点数=5

顶点顶点边的权值

v1 v2 6

v1 v3 4

v1 v4 2

v2 v3 5

v2 v4 8

v2 v5 6

v3 v4 5

v4 v5 7

用Kruskal(克鲁斯卡尔)算法,求最小生成树.

先将所有边的权值按照从小到大排序:

顶点顶点边的权值

v1 v4 2

v1 v3 4

v2 v3 5

v3 v4 5

v1 v2 6

v2 v5 6

v4 v5 7

v2 v4 8

然后,每次提取权值最小边,逐步组成最小生成树:

(1) 取最小边(v1, v4, 2)

v1 -- v4

(2) 取边(v1, v3, 4),不会产生环路.

v1 -- v4

(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"

#define MAXEDGE 20

#define MAXVEX 20

#define INF 65535

typedef struct

{int arc[MAXVEX][MAXVEX];

int numVertexes, numEdges;

}MGraph;

typedef struct

{int begin;

int end;

int weight;

}Edge; //对边集数组Edge结构的定义

//创建图

void CreateMGraph(MGraph *G)

{int i, 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];

}}

}//交换权值以及头和尾

void Swapn(Edge *edges,int i, int j)

{int temp;

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;

}//对权值进行排序 (选择排序法)

void sort(Edge edges[],MGraph *G)

{int i,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);

}}

//查找连线顶点的尾部下标

int Find(int *parent, int f)

{while ( parent[f] > 0)

{f = parent[f];

}return f;

}//生成最小生成树

void MiniSpanTree_Kruskal(MGraph G)

{int i, j, n, m;

int k = 0;

int parent[MAXVEX]; //定义一数组用来判断边与边是否形成环路

Edge edges[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]

{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);

}}

}int main(void)

{MGraph G;

CreateMGraph(&G);

MiniSpanTree_Kruskal(G);

return 0;

}

数据结构与算法题目1

答案为61,

以下为理论:

1) 根据给定的n个权值{w1, w2, …, wn}，构造n棵二叉树的集合F = {T1, T2, …, Tn}，其

中每棵二叉树中均只含一个带权值为wi的根结点,其左、右子树为空树;

(2) 在F中选取其根结点的权值为最小的两棵二叉树，分别作为左、右子树构造一棵新的二叉树，并置这棵新的二叉树根结点的权值为其左、右子树根结点的权值之和;

(3) 从F中删去这两棵树，同时加入刚生成的新树;

(4) 重复(2)和(3)两步，直至F中只含一棵树为止。

简单点说, 路径求法是这样的.先从这组权值中选取最小的两个结点如5和6组成新树,父结点W=11,将11加入权值中并去掉5和6,w={11,8,12},然后又选取最小的两个结点11和8,组成新树,父结点值为19加入权值中并去掉11和8,w={19,12}.直到最后根结点W=31.

这个时候将所有叶子结点和它的路径长度相乘再进行累加

所以是5*3+6*3+8*2+12*1 = 61

太深了

急！急！急！，求且大家帮忙做一下《数据结构》试题。好急啊！！谢谢谢谢~~~

太多了。估计没人做。如果没人做的话分给我吧。别浪费了。谢谢

4d5d8b9d10c11A13a15b

没空,下班了

DBCbcbbd

往下的太多了呵呵

数据结构与算法分析编程题

void permute(const std::string str, int low = 0, int high = -1)

{std::string cpy = str;

int len = ((high == -1)?cpy.length():high);

int a, b, t;

a = b = t = len-1;

if(len == 1)

std::cout << cpy << std::endl;

while(true)

{a = b = len-1;

while(--a >= low && cpy[a] > cpy[a+1]);

if(a < low) break;

t = a+1;

while(b > a && cpy[b--] < cpy[a]);b++;

cpy[a] ^= cpy[b] ^= cpy[a] ^= cpy[b];

std::reverse(&cpy[t], &cpy[len]);

std::cout << cpy << std::endl;

}}

本文地址： https://www.syshengyuanda.com/wanjialuntan/3zWNEvjymVEP1n2.html

数据结构与算法应用真题_《数据结构,算法与应用》

数据结构与算法选择题！

数据结构与算法 求高手作答.感激不敬

数据结构算法 试题 急！ 试构造下图的最小生成树，要求分步给出构造过程。

数据结构与算法题目1

急！急！急！，求且大家帮忙做一下《数据结构》试题。好急啊！！谢谢谢谢~~~

数据结构与算法分析 编程题

数据结构与算法求高手作答.感激不敬

数据结构算法试题急！试构造下图的最小生成树，要求分步给出构造过程。

数据结构与算法分析编程题