每个邻接链表中的边结点都是按照序号从大到小的顺序链接而成是什么意思？

数据结构C++版一般的考试形式是什么？~

考试形式闭卷，考试题型一般有：选择题，简答题，程序分析题，程序解答题。

给你一套模拟题吧，练练手：

模拟试题（一）

一、单项选择题（每小题 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

*/ 

---

扶余县17344349496： 数据结构 二叉树 - ？
常仪异舒： 先介绍一下树: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;...