每个邻接链表中的边结点都是按照序号从大到小的顺序链接而成是什么意思?
考试形式闭卷,考试题型一般有:选择题,简答题,程序分析题,程序解答题。
给你一套模拟题吧,练练手:
模拟试题(一)
一、单项选择题(每小题 2 分,共20分)
(1)以下数据结构中哪一个是线性结构?( )
A)有向图 B)队列 C)线索二叉树 D)B树
(2)在一个单链表la中,若要在当前由指针p指向的结点后面插入一个由q指向的结点,则执行如下( )语句序列。
A)p=q; p->next=q; B)p->next=q; q->next=p;
C)p->next=q->next; p=q; D)q->next=p->next; p->next=q;
(3)( )不是队列的基本运算。
A)在队列第i个元素之后插入一个元素 B)从队头删除一个元素
C)判断一个队列是否为空 D)读取队头元素的值
(4)字符A、B、C依次进入一个栈,按出栈的先后顺序组成不同的字符串,至多可以组成( )个不同的字符串。
A)14 B)5 C)6 D)8
(5)由权值分别为3,8,6,2的叶子生成一棵哈夫曼树,它的带权路径长度为( )。
A)11 B)35 C)19 D)53
以下6-8题基于下图:
(6)该二叉树结点的前序遍历的序列为( )。
A)E、G、F、A、C、D、B B)E、A、G、C、F、B、D
C)E、A、C、B、D、G、F D)E、G、A、C、D、F、B
(7)该二叉树结点的中序遍历的序列为( )。
A)A、B、C、D、E、G、F B)E、A、G、C、F、B、D
C)E、A、C、B、D、G、F D)B、D、C、A、F、G、E
(8)该二叉树的按层遍历的序列为( )。
A)E、G、F、A、C、D、B B)E、A、C、B、D、G、F
C)E、A、G、C、F、B、D D)E、G、A、C、D、F、B
(9)下面关于图的存储的叙述中正确的是( )。
A)用邻接表法存储图,占用的存储空间大小只与图中边数有关,而与结点个数无关
B)用邻接表法存储图,占用的存储空间大小与图中边数和结点个数都有关
C)用邻接矩阵法存储图,占用的存储空间大小与图中结点个数和边数都有关
D)用邻接矩阵法存储图,占用的存储空间大小只与图中边数有关,而与结点个数无关
(10)设有关键码序列(q,g,m,z,a,n,p,x,h),下面哪一个序列是从上述序列出发建堆的结果?( )
A)a,g,h,m,n,p,q,x,z B)a,g,m,h,q,n,p,x,z C)g,m,q,a,n,p,x,h,z D)h,g,m,p,a,n,q,x,z
二、(每小题4分,共8分)
已知一个6´5稀疏矩阵如下所示,试:
(1)写出它的三元组线性表;
(2)给出三元组线性表的顺序存储表示。
三、(本题8分)
求网的最小生成树有哪些算法?它们的时间复杂度分别下多少,各适用何种情况?
四、(每小题4分,共8分)
对于如下图所示的有向图若存储它采用邻接表,并且每个顶点邻接表中的边结点都是按照终点序号从小到大的次序链接的,试写出:
(1)从顶点v1出发进行深度优先搜索所得到的深度优先生成树;
(2)从顶点v2出发进行广度优先搜索所得到的广度优先生成树。
五、(本题8分)
已知一个图的顶点集V和边集E分别为:
V={1,2,3,4,5,6,7};
E={,,,,,,,,,,};
试画出此图的图形,给出所有可能的拓扑排序序列。
六、(本题8分)
对于序列{8,18,6,16,29,28},试写出堆顶元素最小的初始堆。
七、(本题8分)
一棵二叉树的先序、中序和后序序列分别如下,其中有一部分未显示出来。试求出空格处的内容,并画出该二叉树。
先序序列: B F ICEH G
中序序列:D KFIA EJC
后序序列: K FBHJ G A
八、(每小题2分,共8分)
设有序列:w={23,24,27,80,28},试给出:
(1)二叉排序树;
(2)哈夫曼树;
(3)平衡二叉树;
(4)对于增量d=2按降序执行一遍希尔排序的结果。
九、(本题9分)
有关键字序列{7,23,6,9,17,19,21,22,5},Hash函数为H(key)=key % 5,采用链地址法处理冲突,试构造哈希表。
十、(本题15分)
假设二叉树中每个结点所含数据元素均为单字母,以二叉链表为存储结构,试编写算法按如下图所示的树状显示二叉树。
模拟试题(一)参考答案
一、单项选择题
(1)B (2)D (3)A (4)B (5)B
(6)C (7)A (8)C (9)B (10)B
二、(每小题4分,共8分)
(1)((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7))
(2)三元组线性表的顺序存储表示如下所示:
三、(本题8分)
求网的最小生成树可使用Prim算法,时间复杂度为O(n2),此算法适用于边较多的稠密图,也可使用Kruskal算法,时间复杂度为O(eloge),此算法适用于边较少的稀疏图。
四、(每小题4分,共8分)
(1)DFS:v1 v2 v3 v4 v5
(2)BFS:v2 v3 v4 v5 v1
五、(本题8分)
图形表示如下图所示:
拓扑排序为:4362517,4362571,4365721,4365217,4365271
六、(本题8分)
所构造的堆如下图所示:
七、(本题8分)
在先序序列空格中依次填ADKJ,中序中依次填BHG,后序中依次填DIEC。
二叉树如下:
八、(每小题2分,共8分)
(1)二叉排序树如下图所示:
(2)哈夫曼树如下图所示:
(3)平衡二叉树如下图所示:
(4)对于增量d=2按降序执行一遍希尔排序的结果:28,80,27,24,23
九、(本题9分)
哈希表如下图所示:
十、(本题15分)
从上图来看,二叉树的第一层显示在第一列,第二层显示在第二列,第三层显示在第三列;每行显示一个结点,从上至下是先显示右子树,再显示根,最后最左子树,也就是以先遍历右子树,最后遍历左子树的中序遍历次序显示各结点。
具体算法实现如下:
// 文件路径名:exam1\alg.h
template
void DisplayHelp(BinTreeNode *r, int level)
// 操作结果:按树状形式显示以r为根的二叉树,level为层次数,可设根结点的层次数为1
{
if(r != NULL)
{ // 空树不显式,只显式非空树
DisplayHelp(r->rightChild, level + 1); // 显示右子树
cout << endl; // 显示新行
for(int i = 0; i < level - 1; i++)
cout << " "; // 确保在第level列显示结点
cout data; // 显示结点
DisplayHelp(r->leftChild, level + 1); // 显示左子树
}
}
template
void Display(const BinaryTree &bt)
// 操作结果:树状形式显示二叉树
{
DisplayHelp(bt.GetRoot(), 1); // 树状显示以bt.GetRoot()为根的二叉树
cout << endl; // 换行
}
邻接表边节点是 n个顶点的无向图最多有n(n-1)/2条边,邻接表中1条边被存储了2次,因此最多有n(n-1)个结点。
邻接表是图的一种最主要存储结构,用来描述图上的每一个点。对图的每个顶点建立一个容器(n个顶点建立n个容器),第i个容器中的结点包含顶点Vi的所有邻接顶点。实际上我们常用的邻接矩阵就是一种未离散化每个点的边集的邻接表。
在有向图中,描述每个点向别的节点连的边(点a->点b这种情况);在无向图中,描述每个点所有的边(点a-点b这种情况)。
扩展资料:
先用边集表存图,然后每条边a,b得优先以std::min(a,b)为第一关键字再按std::max(a,b)为第二关键字排序,再按照修正后的存图方法存图即可。具体代码见nocow上骑马修栅栏那题lgeecn发的题解和代码。
如果使用list存图可以先存图再用list.sort()函数进行排序,不过似乎效率会差一些,毕竟相对于vector,list常数太大了,达到6倍以上。
存图真心不简单,因为真正用的时候你可能会遇到各种问题,但是你可以加以思考,进行容器搭配使用,即可解决。
这样编程就可以了
#include <iostream>
#include <vector>
#define maxn 50 //最多五十个点
using namespace std;
struct node
{
int nodenum; //记录点的号码,实际在该程序中我直接用 N 数组的下标代替该号码了
vector<int>list; //把与该点有边相连的点记录在动态该数组里
};
int n,m;//分别指点的个数 边的条数
node N[maxn];
int main()
{
while(cin>>n>>m&&(n+m))
{
int v1,v2;
for(int i=0;i<m;i++)
{
cin>>v1>>v2; //输入边的两个端点
N[v1].list.push_back(v2);//将于该点有联系的点压入该链中
N[v2].list.push_back(v1);
}
for(int i=1;i<=n;i++)
{
cout<<i<<":它连接的点有: ";
for(int j=0;j<N[i].list.size();j++)cout<<N[i].list[j]<<' ';//依次输出与与他有联系的点
cout<<'
';
}
}
}
/*
样例输入1:
4 5
1 3
1 2
1 4
2 3
2 4
它表示的是下面一个图
0 1 1 1
1 0 1 1
1 1 0 0
1 1 0 0
*/
求解邻接表建图的算法
① 建立有向图的邻接表更简单,每当读人一个顶点对序号 时,仅需生成一个邻接序号为j的边表结点,将其插入到vj的出边表头部即可。② 建立网络的邻接表时,需在边表的每个结点中增加一个存储边上权的数据域。邻接矩阵 邻接链表 存储表示 惟一 不惟一,各边表结点的链接次序取决于建立邻接...
什么叫邻接表
分类: 教育\/科学 >> 科学技术 问题描述:什么叫邻接表 解释 最好在星期六下午之前给 解析:邻接表是图的一种链式存储结构。对图的每个顶点建立一个单链表(n个顶点建立n个单链表),第i个单链表中的结点包含顶点Vi的所有邻接顶点。
邻接矩阵和邻接表怎么画
邻接矩阵是用一个二维数组来表示图,数组的行数和列数都等于顶点的个数,若两个顶点之间存在一条边,则相应位置的值为1;否则为0。邻接表则是用链表来表示每一对相邻的顶点,对于每一个顶点,都存在若干个链表节点,这些节点表示与该顶点相邻的顶点。在实际应用中可以使用Python、C++等编程语言来实现...
数据结构问题
第4题 (2.0) 分在n个顶点和e条边的无向图的邻接矩阵中,表示边存在的元素个数为( )。A、nB、n*eC、eD、2*e第5题 (2.0) 分 对于有向图,其邻接矩阵表示相比邻接表表示更易于进行的操作为( )。A、求顶点的邻接点B、求顶点的度C、深度优先遍历D、广度优先遍历第6题 (2.0) 分 为便于判别有向图中...
图采用邻接矩阵和邻接链表表示时,深度优先遍历算法的时间复杂度有何不...
1.采用邻接矩阵表示时,设邻接矩阵有n×n阶,矩阵包含n^2个元素。对每个顶点来说,搜索其所有邻接点需要搜索矩阵中对应的整个一行,因此,对整个图的遍历来说,需要搜索整个矩阵,算法的时间复杂度为O(n^2)。2.采用邻接表表示时,若邻接表有n个结点和e条边,对每个顶点来说,搜索其所有邻接点需要...
求套公交换乘设计方案!
\/\/定义邻接表中的边结点类型 struct edgenode { int adjvex; \/\/邻接点域 int weight; \/\/权值域 edgenode* next; \/\/指向下一个边结点的链域 edgenode(){} edgenode(int d,int w):adjvex(d),weight(w),next(NULL){} }; struct Top \/\/顶点数组的元素类型 {char data;\/\/顶点数据 edgenode *adj;...
数据结构的问题~
8 在一个单链表中,若要在p所指向的结点之前插入一个新结点,则此算法的时间复杂度的量级为( )。...1、已知一棵树的边的集合表示为{(L,N),(G,K),(G,1),(G,M),(B,E),(B,F),(D,G),...2、对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小是( ) A、n B、(n-1)\/2...
给出一个图如何画出其邻接表,要求具体过程
严蔚敏的《数据结构》c语言版的164面有,画的过程是先画左边那个由表头结点组成的4个单元的线性表,把这个线性表的各单元的序号写在左边,然后再从上到下完成从每个顶点开始的单链表,单链表中的每个邻接点不填顶点名称,填它在表头结点构成的线性表中的序号。画图传图好麻烦,如果有问题请追问。
图的深度优先搜索的时间复杂度
至于在邻接表上遍历时,过程与这个类似,但是邻接表中只是存储了边结点(e条边,无向图也只是2e个结点),加上表头结点为n(也就是顶点个数),因此时间复杂度为O(n+e)另外,在邻接表中判断某个顶点是否关联,最坏时可能需要将链表中所有结点都遍历完(尤其是有向图中),此时时间复杂度自然就是O(...
2015考研:计算机数据结构常用算法(7)?
遍历图的过程实质上是_对每个顶点查找其邻接点的过程___ 其耗费的时间主要取决于采用的存储结构。当用邻接矩阵存储图时,查找每个顶点的邻接点所需的时间O( ),其中n是图中顶点数。而当用邻接表存储图时,找邻接点的所需时间为O(e),其中e为图中边的个数或有向弧的个数,由此,当以邻接表作为...
常仪异舒: 先介绍一下树:1.树的定义 树是一种常见的非线性的数据结构.树的递归定义如下: 树是n(n>0)个结点的有限集,这个集合满足以下条件: ⑴有且仅有一个结点没有前件(父亲结点),该结点称为树的根; ⑵除根外,其余的每个结点都有且仅...
扶余县17344349496: 用邻接表表示无向图时,若图中有30个结点,50条边,则该邻接表有——个边结点 - ?
常仪异舒: 每个点以链表储存与它相关的点,故每条边上的两个点都会有另一个点作为自己的边结点,故每条边产生两个边结点——2 * 50 = 100个边结点.
扶余县17344349496: 基于邻接表建图的几种方法 - ?
常仪异舒: 数据结构书上表示邻接表比较复杂,一般形式如下: typedef struct Node{int dest; //邻接边的弧头结点序号 int weight; //权值信息 struct Node *next; //指向下一条邻接边}Edge; //单链表结点的结构体typedef struct{ DataType data; //结点的一...
扶余县17344349496: 在表长为n的单链表中,算法时间复杂度为O(n)的操作是查找单链表中第i个结点.为什么? - ?
常仪异舒: 因为单链表只能顺序访问,因此每次访问其中第i 个元素需要从头开始,按照序号访问元素的平均查找个数为(n+1)/2,用时间复杂度表示不就是O(n)了
扶余县17344349496: 图的邻接表的深度优先搜索 - ?
常仪异舒: #include "iostream.h" int *visited; //存放当前结点是否遍历 typedef int **MGraph;//定义一个二维数组存放邻接矩阵,暂不定义矩阵大小,数据元素类型为整型//把矩阵看作数组元素是一维数组的一个一维数组 struct ArcNode{ //定义邻接表中的...
扶余县17344349496: 已有a、b两个链表每个链表中的结点包括学号、成绩.要求把两个链表合并,按学号升序排列. - ?
常仪异舒: #include <stdio.h> #include <MALLOC.H> #include <stdlib.h> typedef struct Number { int data; struct Number *next; }Number;void main() { Number head; Number *p,*q,*t; char input; int temp,i,howmany=0,j;printf("Please input the number string:\n...
扶余县17344349496: 根据附件图1,写出三角形的邻接关系,以及结点—弧段的关联关系 - 上...?
常仪异舒: 虽然题1不会做,但是题2做过 希望对你有帮助: 题2源程序如下: #include<stdio.h> #include<malloc.h> struct node{ int key; struct node *next; }; void creat_link(struct node *); main() { struct node *head=NULL; creat_link(head); } void creat_link(...
扶余县17344349496: 邻接表边节点是什么 - ?
常仪异舒: n个顶点的无向图最多有n(n-1)/2条边邻接表中1条边被存储了2次,因此最多有n(n-1)个结点
扶余县17344349496: 判断单链表中的结点是否有序返回真否则为假 - ?
常仪异舒: 所谓有序指的是结点的Key是否按照顺序排列,假设结点结构为: struct Node { int key; int data; Node *next; }; struct LinkedList { Node *header; }; 那么: #define TRUE 1 #define FALSE 0 int IsSequential(LinkedList *list) { Node *p = list.header;...