数据结构作业系统第七章复习资料

7.22③试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点vi到顶点vj的路径(i≠j)。注意：算法中涉及的图的基本操作必须在此存储结构上实现。

实现下列函数：

Status DfsReachable(ALGraph g, int i, int j);

/* Judge if it exists a path from vertex 'i' to */

/* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/

图的邻接表以及相关类型和辅助变量定义如下：Status visited[MAX_VERTEX_NUM];

typedef char VertexType;

typedef struct ArcNode {

int adjvex;

struct ArcNode *nextarc;

} ArcNode;

typedef struct VNode {

V ertexType data;

ArcNode *firstarc;

} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {

AdjList vertices;

int vexnum, arcnum;

} ALGraph;

Status DfsReachable(ALGraph g, int i, int j)

/* Judge if it exists a path from vertex 'i' to */

/* vertex 'j' in digraph 'g'. */ /* Array 'visited[]' has been initialed to 'false'.*/

{

int k;

ArcNode *p;

visited[i]=1;

for(p=g.vertices[i].firstarc;p;p=p->nextarc)

{

if(p)

{

k=p->adjvex;

if(k==j)return 1;

if(visited[k]!=1)

if(DfsReachable(g,k,j))return 1;

}

}

return 0;

}

7.23③同7.22题要求。试基于图的广度优先搜索策略写一算法。

实现下列函数：

Status BfsReachable(ALGraph g, int i, int j);

/* Determine whether it exists path from vertex i to */

/* vertex j in digraph g with Breadth_First Search. */

/* Array 'visited' has been initialed to 'false'. */

图的邻接表以及相关类型和辅助变量定义如下：

Status visited[MAX_VERTEX_NUM];

typedef char VertexType;

typedef struct ArcNode {

int adjvex;

struct ArcNode *nextarc;

} ArcNode;

typedef struct VNode {

V ertexType data;

ArcNode *firstarc;

} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {

AdjList vertices;

int vexnum, arcnum;

} ALGraph;

Status InitQueue(Queue &q);

Status EnQueue(Queue &q, int e);

Status DeQueue(Queue &q, int &e);

Status QueueEmpty(Queue q);

Status GetFront(Queue q, int &e);

Status BfsReachable(ALGraph g, int i, int j)

/* Determine whether it exists path from vertex i to */

/* vertex j in digraph g with Breadth_First Search. */

/* Array 'visited' has been initialed to 'false'. */

{

Queue q;

int k,n;

ArcNode *p;

InitQueue(q);

EnQueue(q,i);

while(!QueueEmpty(q))

{

DeQueue(q,k);

visited[k]=1;

for(p=g.vertices[k].firstarc;p;p=p->nextarc)

{

n=p->adjvex;

if(n==j)return 1;

if(visited[n]!=1)EnQueue(q,n);

}

}

return 0;

}

7.24③试利用栈的基本操作编写，按深度优先搜索策略

遍历一个强连通图的非递归形式的算法。算法中不规定具

体的存储结构，而将图Graph看成是一种抽象的数据类型。

实现下列函数：

void Traverse(Graph dig, VertexType v0, void(*visit)(VertexType));

/* Travel the digraph 'dig' with Depth_First Search. */

图以及相关类型、函数和辅助变量定义如下：

Status visited[MAX_VERTEX_NUM];

int LocateVex(Graph g, VertexType v);

VertexType GetVex(Graph g, int i);

int FirstAdjVex(Graph g, int v);

int NextAdjVex(Graph g, int v, int w);

void visit(char v);

Status InitStack(SStack &s);

Status Push(SStack &s, SElemType x);

Status Pop(SStack &s, SElemType &x);

Status StackEmpty(SStack s);

Status GetTop(SStack s, SElemType &e);

void Traverse(Graph dig, V ertexType v0, void (*visit)(VertexType))

{

int i,v,flag;SStack s;VertexType p; //flag来记录某点还有没有邻接点InitStack(s);

if(dig.vexnum&&dig.arcnum)

{ i=LocateVex(dig,v0);visited[i]=TRUE;visit(v0);Push(s,v0);

while(!StackEmpty(s))

{GetTop(s,p);v=LocateVex(dig,p);flag=0;

for(i=FirstAdjVex(dig,v);i>=0;i=NextAdjVex(dig,v,i))

{ if(!visited[i]) {p=GetVex(dig,i); flag=1; break;}}

if(flag)

{visit(p);visited[i]=TRUE;

Push(s,p);

}

else{Pop(s,p); }

}

}

}

7.27④采用邻接表存储结构，编写一个判别无向图中任意给定的两个顶点之间是否存在一条长度为k的简单路径的算法。

实现下列函数：

Status SinglePath(ALGraph g, VertexType sv, VertexType tv,

int k, char *sp);

/* Judge whether it exists a path from sv to tv with length k */

/* in graph g, return path using string sp if exists. */

图的邻接表以及相关类型、函数和辅助变量定义如下：

Status visited[MAX_VERTEX_NUM];

typedef char StrARR[100][MAX_VERTEX_NUM+1];

typedef char VertexType;

typedef struct ArcNode {

int adjvex;

struct ArcNode *nextarc;

} ArcNode;

typedef struct VNode {

V ertexType data;

ArcNode *firstarc;

} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {

AdjList vertices;

int vexnum, arcnum;

} ALGraph;

int LocateVex(Graph g, VertexType v);

void inpath(char *&path, VertexType v);

/* Add vertex 'v' to 'path' */

void depath(char *&path, VertexType v);

/* Remove vertex 'v' from 'path' */

Status SinglePath(ALGraph g, VertexType sv, VertexType tv, int k, char *sp) /* Judge whether it exists a path from sv to tv with length k */

/* in graph g, return path using string sp if exists. */

{ int i,j,l;

ArcNode *p;

if(sv==tv && k==0)

{ inpath(sp,tv);

return OK; }

else

{

i=LocateVex(g,sv);

visited[i]=1;

inpath(sp,sv);

for(p=g.vertices[i].firstarc;p;p=p->nextarc)

{

l=p->adjvex;

if(!visited[l])

{

if(SinglePath(g,g.vertices[l].data,tv,k-1,sp))

return OK;

else

depath(sp,g.vertices[l].data);

}

}

visited[i]=0;

}

}

7.28⑤已知有向图和图中两个顶点u和v，试编写算法求

有向图中从u到v的所有简单路径。

实现下列函数：

void AllPath(ALGraph g, VertexType sv, VertexType tv,

StrARR &path, int &i);

/* Get all the paths from vertex sv to tv, save them */

/* into Array path which contains string components. */

/* Return the number of path using i */

图的邻接表以及相关类型、函数和辅助变量定义如下：Status visited[MAX_VERTEX_NUM];

typedef char StrARR[100][MAX_VERTEX_NUM+1]; typedef char VertexType;

typedef struct ArcNode {

int adjvex;

struct ArcNode *nextarc;

} ArcNode;

typedef struct VNode {

V ertexType data;

ArcNode *firstarc;

} VNode, AdjList[MAX_VERTEX_NUM];

typedef struct {

AdjList vertices;

int vexnum, arcnum;

} ALGraph;

int LocateVex(Graph g, VertexType v);

void inpath(char *path, VertexType v);

/* Add vertex 'v' to 'path' */

void depath(char *path, VertexType v);

/* Remove vertex 'v' from 'path' */

void AllPath2(ALGraph g, V ertexType sv, VertexType tv,

StrARR &path, int &i,int &d,VertexType A[]) { int j,k,l,m,n;

ArcNode *p;

j=LocateVex(g,sv);

visited[j]=1;

A[d++]=sv;

if(sv==tv)

{

m=0;

for(n=0;n

path[i][m++]=A[n];

i++;

}

else

for(p=g.vertices[j].firstarc;p;p=p->nextarc)

{

l=p->adjvex;

if(!visited[l])

AllPath2(g,g.vertices[l].data,tv,path,i,d,A);

}

visited[j]=0;

d--;

}

void AllPath(ALGraph g, VertexType sv, VertexType tv,

StrARR &path, int &i)

/* Get all the paths from vertex sv to tv, save them */

/* into Array path which contains string components. */

/* Return the number of path using i */

{

int d=0,j,l;

VertexType A[MAX_VERTEX_NUM],B[MAX_VERTEX_NUM];

for(l=0;l<5;l++)

{

strcpy(B,path[l]);

for(j=0;j

depath(path[l],B[j]);

}

AllPath2(g,sv,tv,path,i,d,A);

}

7.31③试完成求有向图的强连通分量的算法，并分析算法的时间复杂度。

实现下列函数：

void StronglyConnected(OLGraph dig, StrARR &scc, int &n);

/* Get all the strongly connected components in the digraph dig, */

/* and put the ith into scc[i] which is a string. */

图的十字链表以及相关类型和辅助变量定义如下：

Status visited[MAX_VERTEX_NUM];

int finished[MAX_VERTEX_NUM];

typedef char StrARR[MAX_VERTEX_NUM][MAX_VERTEX_NUM+1]; // 记录各强连通分量typedef struct ArcBox {

int tailvex,headvex;

struct ArcBox *hlink,*tlink;

} ArcBox;

typedef struct VexNode {

V ertexType data;

ArcBox *firstin,*firstout;

} VexNode;

typedef struct {

V exNode xlist[MAX_VERTEX_NUM];

int vexnum, arcnum;

} OLGraph;

int count;

void DFS1(OLGraph dig,int v);

void DFS2(OLGraph dig,int v,StrARR &scc,int j,int k);

void StronglyConnected(OLGraph dig, StrARR &scc, int &n)

/* Get all the strongly connected components in the digraph dig, */ /* and put the ith into scc[i] which is a string. */ {

int i,k=0,v;

count=0;

for(v=0;v

if(!visited[v])

DFS1(dig,v);

for(v=0;v

visited[v]=0;

for(i=dig.vexnum-1;i>=0;i--)

{

v=finished[i];

if(!visited[v])

{

DFS2(dig,v,scc,n,k);

n++;

}

}

}

void DFS1(OLGraph dig,int v)

{

int w;

ArcBox *p;

visited[v]=1;

for(p=dig.xlist[v].firstout;p;p=p->tlink)

{ w=p->headvex;

if(!visited[w])

DFS1(dig,w);

}

finished[count++]=v;

}

void DFS2(OLGraph dig,int v,StrARR &scc,int j,int k)

{

int w;

ArcBox *p;

visited[v]=1;

scc[j][k++]=dig.xlist[v].data;

for(p=dig.xlist[v].firstin;p;p=p->hlink)

{

w=p->tailvex;

if(!visited[w])

DFS2(dig,w,scc,j,k);

}

}

7.29⑤试写一个算法，在以邻接矩阵方式存储的

有向图G中求顶点i到顶点j的不含回路的、长度为k

的路径数。

实现下列函数：

int SimplePath(MGraph G, int i, int j, int k);

/* 求有向图G的顶点i到j之间长度为k的简单路径条数*/

图的邻接矩阵存储结构的类型定义如下：

typedef enum {DG,DN,AG,AN} GraphKind; // 有向图,有向网,无向图,无向网

typedef struct {

VRType adj; // 顶点关系类型。对无权图，用1(是)或0(否)表示相邻否；

// 对带权图，则为权值类型

InfoType *info; // 该弧相关信息的指针(可无)

}ArcCell,AdjMatrix[MAX_VERTEX_NUM][MAX_VERTEX_NUM];

typedef struct {

AdjMatrix arcs; // 邻接矩阵

V ertexType vexs[MAX_VERTEX_NUM]; // 顶点向量

int vexnum,arcnum; // 图的当前顶点数和弧数

GraphKind kind; // 图的种类标志

}MGraph;

int SimplePath(MGraph G, int i, int j, int k)

/* 求有向图G的顶点i到j之间长度为k的简单路径条数*/

{

int sum=0,v;

if( G.arcs[i][j].adj &&k==1 && !visited[j])

sum=1;

else

if(k>1)

{ visited[i]=1;

for(v=0;v

{

if(G.arcs[i][v].adj && !visited[v])

sum+=SimplePath(G,v,j,k-1);

}

visited[i]=0;

}

return sum;

}

实现下列函数：

int Search(SSTable s, KeyType k);

/* Index the element which key is k */

/* in StaticSearchTable s. */ /* Return 0 if x is not found. */

静态查找表的类型SSTable定义如下：typedef struct {

KeyType key;

... ... // 其他数据域

} ElemType;

typedef struct {

ElemType *elem;

int length;

} SSTable;

int Search(SSTable a, KeyType k)

/* Index the element which key is k */ /* in StaticSearchTable s. */ /* Return 0 if x is not found. */ {

int i;

for(i=1;i<=a.length;i++)

if(a.elem[i].key==k)return i;

return 0;

}

数据结构第1章作业

第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（） A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（）。 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（） (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。 A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？ A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（） A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（） FOR i:=1 TO n DO FOR j:=1 TO n DO x:=x+1; A． O(2n) B．O(n) C．O(n2) D．O(log2n) 12．程序段 FOR i:=n-1 DOWNTO 1 DO FOR j:=1 TO i DO IF A[j]>A[j+1] THEN A[j]与A[j+1]对换；

《数据结构》习题汇编07 第七章 图 试题

第七章图试题 一、单项选择题 1.在无向图中定义顶点的度为与它相关联的（）的数目。 A. 顶点 B. 边 C. 权 D. 权值 2.在无向图中定义顶点 v i与v j之间的路径为从v i到达v j的一个（）。 A. 顶点序列 B. 边序列 C. 权值总和 D. 边的条数 3.图的简单路径是指（）不重复的路径。 A. 权值 B. 顶点 C. 边 D. 边与顶点均 4.设无向图的顶点个数为n，则该图最多有（）条边。 A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1) 5.n个顶点的连通图至少有（）条边。 A. n-1 B. n C. n+1 D. 0 6.在一个无向图中，所有顶点的度数之和等于所有边数的 ( ) 倍。 A. 3 B. 2 C. 1 D. 1/2 7.若采用邻接矩阵法存储一个n个顶点的无向图，则该邻接矩阵是一个 ( )。 A. 上三角矩阵 B. 稀疏矩阵 C. 对角矩阵 D. 对称矩阵 8.图的深度优先搜索类似于树的（）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 9.图的广度优先搜索类似于树的（）次序遍历。 A. 先根 B. 中根 C. 后根 D. 层次 10.在用Kruskal算法求解带权连通图的最小（代价）生成树时，通常采用一个（）辅助结构， 判断一条边的两个端点是否在同一个连通分量上。 A. 位向量 B. 堆 C. 并查集 D. 生成树顶点集合 11.在用Kruskal算法求解带权连通图的最小（代价）生成树时，选择权值最小的边的原则是该边不能 在图中构成（）。 A. 重边 B. 有向环 C. 回路 D. 权值重复的边 12.在用Dijkstra算法求解带权有向图的最短路径问题时，要求图中每条边所带的权值必须是 （）。 A. 非零 B. 非整 C. 非负 D. 非正 13.在一个连通图中进行深度优先搜索得到一棵深度优先生成树，树根结点是关节点的充要条件是它至少 有（）子女。

数据结构第10章 习题答案

1．下列排序算法中，其中（ D ）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 2．有一组数据（15，9，7，8，20，-1，7，4）用快速排序的划分方法进行一趟划分后数据的排序为 ( A )（按递增序）。 A．下面的B，C，D都不对。 B．9，7，8，4，-1，7，15，20 C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，20 3.下列排序算法中，在每一趟都能选出一个元素放到其最终位置上，并且其时间性能受数据初始特性影响的是：（ B ）。 A. 直接插入排序 B. 快速排序 C. 直接选择排序 D. 堆排序 4．如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ D ）方法最快。 A．起泡排序 B．快速排列 C．Shell排序 D．堆排序 E．简单选择排序 5．从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后将其放在已排序序列的合适位置，该排序方法称为( A )排序法。 A. 插入 B. 选择 C. 希尔 D. 二路归并 6. 在排序算法中，每次从未排序的记录中挑出最小（或最大）关键码字的记录，加入到已排序记录的末尾，该排序方法是（ A ）。 A. 选择 B. 冒泡 C. 插入 D. 堆 7. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（ C ）次比较。 A. 3 B. 10 C. 15 D. 25 8. 对序列{15，9，7，8，20，-1，4，} 用希尔排序方法排序，经一趟后序列变为{15，-l，4，8，20，9，7}则该次采用的增量是 ( B ) A. l B. 4 C. 3 D. 2 9. 堆排序是（ E ）类排序 A. 插入 B. 交换 C. 归并 D. 基数 E. 选择 10．排序方法有许多种，（1）法从未排序的序列中依次取出元素，与已排序序列（初始时为空）中的元素作比较，将其放入已排序序列的正确位置上；（2）法从未排序的序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端；交换排序方法是对序列中的元素进行一系列比较，当被比较的两元素逆序时，进行交换；（3）和（4）是基于这类方法的两种排序方法，而（4）是比（3）效率更高的方法；（5）法是基于选择排序的一种排序方法，是完全二叉树结构的一个重要应用。 （1）--（5）: A．选择排序 B．快速排序 C．插入排序 D．起泡排序 E．归并排序 F．shell排序 G．堆排序 H．基数排序 10.1C 5 2A 3D 4B 5G 1．若不考虑基数排序，则在排序过程中，主要进行的两种基本操作是关键字的__ ____和记录的_____。比较,移动 2．分别采用堆排序，快速排序，冒泡排序和归并排序，对初态为有序的表，则最省时间的是_____算法，最费时间的是______算法。冒泡,快速 3. 设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需__________趟，写出第一趟结束后，数组中数据的排列次序__________。3,(10,7,-9,0,47,23,1,8,98,36) 4．对给定文件（28，07，39，10，65，14，61，17，50，21）选择第一个元素28进行划分，写出其快速排序第一遍的排序过程。

数据结构试题及答案10套

一、单选题（每题 2 分，共20分） 1. 1.对一个算法的评价,不包括如下（B ）方面的内容。 Ａ.健壮性和可读性Ｂ．并行性C。正确性Ｄ．时空复杂度 2.2．在带有头结点的单链表ＨL中,要向表头插入一个由指针p指向 的结点，则执行（A ). Ａ. p－〉ｎｅxt=HL->nexｔ; ＨL-〉nexｔ=p; B． p-〉next=HL；ＨL=p； Ｃ。p-＞ｎext=HＬ； p＝HL；Ｄ. HL=p; ｐ－〉next＝ＨL； 3.3．对线性表,在下列哪种情况下应当采用链表表示？( B ） Ａ.经常需要随机地存取元素 B。经常需要进行插入和删除操作 C。表中元素需要占据一片连续的存储空间D．表中元素的个数不变 4. 4.一个栈的输入序列为１ 2 3，则下列序列中不可能是栈的输出序 列的是( C ） A. 2 3 1 ??? B. ３ 2 1 C。 3 １ 2 ??? D. 1 ２３ 5. 5.AＯV网是一种（D ）。 A．有向图Ｂ．无向图Ｃ．无向无环图D．有向无环图 6.6。采用开放定址法处理散列表的冲突时,其平均查找长度（Ｂ)。 A．低于链接法处理冲突B．高于链接法处理冲突Ｃ.与链接法处理冲突相同 D。高于二分查找 7.7。若需要利用形参直接访问实参时，应将形参变量说明为（D ) 参数. Ａ。值Ｂ。函数 C.指针 D。引用 8.８．在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结 点都具有相同的（ A )。 A。行号 B.列号 C．元素值 D．非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为( D )。 A。O（loｇ 2n) B．Ｏ（nlog 2 n） C。０（n) D.0 （n2） 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C ). Ａ．O(n） B. Ｏ(1） C。 O（log 2 n） D. O(n2)二、运算题（每题 6 分，共２４分）

数据结构第十章习题课

1．下列排序算法中，其中（）是稳定的。 A. 堆排序，冒泡排序 B. 快速排序，堆排序 C. 直接选择排序，归并排序 D. 归并排序，冒泡排序 2．若需在O(nlog2n)的时间内完成对数组的排序，且要求排序是稳定的，则可选择的排序方法是（）。 A. 快速排序 B. 堆排序 C. 归并排序 D. 直接插入排序3．排序趟数与序列的原始状态有关的排序方法是( )排序法。 A．插入 B. 选择 C. 冒泡 D. 快速4．对一组数据（84，47，25，15，21）排序，数据的排列次序在排序的过程中 的变化为（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47 （4） 15 21 25 47 84 则采用的排序是( )。 A. 选择 B. 冒泡 C. 快速 D. 插入5．对序列{15，9，7，8，20，-1，4}进行排序，进行一趟后数据的排列变为{4，9，-1，8，20，7，15}；则采用的是（）排序。 A. 选择 B. 快速 C. 希尔 D. 冒泡6．若上题的数据经一趟排序后的排列为{9，15，7，8，20，-1，4}，则采用的 是（）排序。 A．选择 B. 堆 C. 直接插入 D. 冒泡 7．在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）A．直接插入排序B．冒泡排序C．简单选择排序 8．下列排序算法中，（）算法可能会出现下面情况：在最后一趟开始之前，所有元素都不在其最终的位置上。 A. 堆排序 B. 冒泡排序 C. 快速排序 D. 插入排序 9. 下列排序算法中，占用辅助空间最多的是：( ) A. 归并排序 B. 快速排序 C. 希尔排序 D. 堆排序10．用直接插入排序方法对下面四个序列进行排序（由小到大），元素比较次数 最少的是（）。 A．94,32,40,90,80,46,21,69 B．32,40,21,46,69,94,90,80 C．21,32,46,40,80,69,90,94 D．90,69,80,46,21,32,94,40 11. 若用冒泡排序方法对序列{10,14,26,29,41,52}从大到小排序，需进行（）次比较。 A. 3 B. 10 C. 15 D. 25 12．对n个记录的线性表进行快速排序为减少算法的递归深度，以下叙述正确

数据结构习题及答案——严蔚敏

第一章绪论 一、选择题 1.组成数据的基本单位是（） （A）数据项（B）数据类型（C）数据元素（D）数据变量 2.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 3.在数据结构中，从逻辑上可以把数据结构分成（） （A）动态结构和静态结构（B）紧凑结构和非紧凑结构 （C）线性结构和非线性结构（D）内部结构和外部结构 4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ② （A）结构（B）关系（C）运算（D）算法 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5 个特性。 ① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法

② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性 （C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性 二、判断题 1.数据的机内表示称为数据的存储结构。（） 2.算法就是程序。（） 3.数据元素是数据的最小单位。（） 4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。（） 5.算法的时间复杂度取决于问题的规模和待处理数据的初态。（） 三、填空题 1.数据逻辑结构包括________、________、_________ 和_________四种类型,其中树形结构和图形结构合称为_____。 2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______个前驱结点；最后一个结点______后续结点,其余每个结点有且只有_______个后续结点。 3.在树形结构中,树根结点没有_______结点,其余每个结点有且只 有_______个前驱结点；叶子结点没有________结点,其余每个结点的后续结点可以_________。 4.在图形结构中,每个结点的前驱结点数和后续结点数可以 _________。 5.线性结构中元素之间存在________关系,树形结构中元素之间存 在______关系,图形结构中元素之间存在_______关系。 6.算法的五个重要特性是_______、_______、______、_______、

数据结构课程作业

数据结构课程作业_A 交卷时间：2017-08-09 10:08:51 一、单选题 1. (7分)设有一个二维数组A[m][n]，假设A[0][0]存放位置在644(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在什么位置脚注(10)表示用10进制表示。 A. 688 B. 678 C. 692 D. 696 纠错 得分： 7 知识点：第五章 展开解析 答案 C 解析第五章第二节综合题目 2. (7分)若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2，3 C. 9，5，3 D. 9，4，2，3 纠错 得分： 0 知识点：第九章 展开解析 答案 D 解析第九章第一节有序表的查找

(7分)设某完全无向图中有n个顶点，则该完全无向图中有（）条边。 A. n(n-1)/2 B. n(n-1) C. n2 D. n2-1 纠错 得分： 7 知识点：第七章 展开解析 答案 A 解析第七章第一节综合题目 4. (7分)若在任意一棵二叉树中，有n0个叶子结点，有n2个度为2的结点，则：n0=_____ A. n2+1 B. n2-1 C. n2+2 D. n2-2 纠错 得分： 7 知识点：第六章 展开解析 答案 A 解析第六章第二节二叉树的性质 5. (7分)栈的插入和删除操作在（）进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置

得分： 7 知识点：第三章 展开解析 答案 A 解析第三章第一节栈的表示和实现 6. (7分)设有序表中有1000个元素，则用二分查找查找元素X最多需要比较（）次。 A. 25 B. 10 C. 7 D. 1 纠错 得分： 7 知识点：第九章 展开解析 答案 B 解析第九章第一节有序表的查找 7. (7分)设某棵二叉树的高度为10，则该二叉树上叶子结点最多有（）。 A. 20 B. 256 C. 512 D. 1024 纠错 得分： 7 知识点：第六章 展开解析 答案 C 解析第六章第六节二叉树的性质

数据结构各章作业题目

第一章作业 一、选择题 1.被计算机加工的数据元素不是孤立的，它们彼此之间一般存在某种关系，通常把数据元素之间的 这种关系称为( )。 A. 规则 B. 结构 C. 集合 D. 运算 2.在Data_Structure=(D,S)中，D是( )的有限集合。 A. 数据元素 B. 算法 C. 数据操作 D.数据对象 3.计算机所处理的数据一般具有某种关系，这是指( )之间存在的某种关系。 A. 数据与数据 B. 数据元素与数据元素 C. 元素内数据项与数据项 D. 数据文件内记录与记录 4.顺序存储表示中数据元素之间的逻辑关系是由( )表示的。 A. 指针 B. 逻辑顺序 C. 存储位置 D. 问题上下文 5.链接存储表示中数据元素之间的逻辑关系是由( )表示的。 A. 指针 B. 逻辑顺序 C. 存储位置 D. 问题上下文 6.从逻辑上可将数据结构分为( )。 A. 动态结构和静态结构 B. 紧凑结构和非紧凑结构 C. 内部结构和外部结构 D. 线性结构和非线性结构 7.以下选项属于线性结构的是( )。 A. 广义表 B. 二叉树 C. 串 D. 稀疏数组 8.以下选项属于非线性结构的是( )。 A. 广义表 B. 队列 C. 优先队列 D. 栈 9.以下属于逻辑结构的是( ) A. 顺序表 B. 散列表 C. 有序表 D. 单链表 10.一个完整的算法应该具有( )等特性。 A. 可执行性、可修改性和可维护性 B. 可行性、确定性和有穷性

C. 确定性、有穷性和可靠性 D. 正确性、可读性和有效性 11.若一个问题既可以用迭代方法也可以用递归方法求解，则( )的方法具有更高的时空效率。 A. 迭代 B. 递归 C. 先递归后迭代 D. 先迭代后递归 12.一个递归算法必须包括( ) A. 递归部分 B. 终止条件和递归部分 C. 迭代部分 D. 终止条件和迭代部 分 13.算法的时间复杂度与( )有关。 A. 问题规模 B. 源程序长度 C. 计算机硬件运行速度 D. 编译后执行程序的 质量 二、指出下列各算法的功能并求出其时间复杂度。 (1) int Prime(int n){ int i=2,x=(int)sqrt(n); //sqrt(n)为求n的平方根 while(i<=x){ if(n%i==0)break; i++; } if(i>x) return 1; else return 0; } (2) int sum1(int n){ int p=1,s=0; for(int i=1;i<=n;i++){ p*=i;s+=p;

数据结构习题及答案概论

第1章算法 一、选择题 1.算法的时间复杂度是指（）。 A）执行算法程序所需要的时间 B）算法程序中的指令条数 C）算法执行过程中所需要的基本运算次数 D）算法程序的长度 2.算法的空间复杂度是指（）。 A）算法程序的长度 B）算法程序所占的存储空间 C）算法执行过程中所需要的存储空间 D）算法程序中的指令条数 3.下面（）的时间复杂度最好（即执行时间最短）。 log) A）O(n ) B）O(n 2 log ) D）O(n2) C）O(n n 2 4.下面累加求和程序段的时间复杂度为（）。 int sum(int a[],int n) { int i, s=0; for (i=0;i

int i=0,s1=0,s2=0; while(ix) return 1; else return 0; } log) A）O(1 ) B）O(n 2 C）O(n ) D）O(n) 8.下面程序段的时间复杂度为（） int fun(int n) { int i=1,s=1; while(s

数据结构作业第1章

第1章绪论 1. 填空 （1）（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 （2）（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 （3）从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 （4）数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 （5）算法具有五个特性，分别是（）、（）、（）、（）、（）。 （6）在一般情况下，一个算法的时间复杂度是（）的函数。 （7）设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链式存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 ⑵假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（）。 A 树 B 图 C 线性表 D 集合 ⑶算法指的是（）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 ⑷下面（）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 ⑸算法分析的目的是（），算法分析的两个主要方面是（）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性H 数据复杂性和程序复杂性 3. 判断题 （1）算法的时间复杂度都要通过算法中的基本语句的执行次数来确定。 （2）每种数据结构都具备三个基本操作：插入、删除和查找。 （3）逻辑结构与数据元素本身的内容和形式无关。 （4）基于某种逻辑结构之上的基本操作，其实现是唯一的。 4. 分析以下各程序段，并用大O记号表示其执行时间。

数据结构第七章图

数据结构习题（图） 一、选择题 1．设完全无向图的顶点个数为n，则该图有( B )条边。 A. n-l B. n(n-l)/2 C.n(n+l)/2 D. n(n-l) 2．在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 A.3 B.2 C.1 D.1/2 3．有向图的一个顶点的度为该顶点的( )。 A.入度 B. 出度 C.入度与出度之和 D.(入度+出度)/2 4．在无向图G (V，E)中，如果图中任意两个顶点vi、vj (vi、vj∈V，vi≠vj)都的，则称该图是( )。 A.强连通图 B.连通图 C.非连通图 D.非强连通图 5．若采用邻接矩阵存储具有n个顶点的一个无向图，则该邻接矩阵是一个( )。 A.上三角矩阵 B.稀疏矩阵 C.对角矩阵 D.对称矩阵 6．若采用邻接矩阵存储具有n个顶点的一个有向图，顶点vi的出度等于邻接矩阵 A.第i列元素之和 B.第i行元素之和减去第i列元素之和 C.第i行元素之和 D.第i行元素之和加上第i列元素之和 7．对于具有e条边的无向图，它的邻接表中有( )个边结点。 A.e-l B.e C.2(e-l) D. 2e 8．对于含有n个顶点和e条边的无向连通图，利用普里姆Prim算法产生最小生成时间复杂性为( )，利用克鲁斯卡尔Kruskal算法产生最小生成树（假设边已经按权的次序排序），其时间复杂性为( )。 A. O(n2) B. O(n*e) C. O(n*logn) D.O(e) 9．对于一个具有n个顶点和e条边的有向图，拓扑排序总的时间花费为O( ) A.n B.n+l C.n-l D.n+e 10．在一个带权连通图G中，权值最小的边一定包含在G的( )生成树中。 A.最小 B.任何 C.广度优先 D.深度优先 二、填空题 1．在一个具有n个顶点的无向完全图中，包含有____条边；在一个具有n个有向完全图中，包含有____条边。 2．对于无向图，顶点vi的度等于其邻接矩阵____ 的元素之和。 3．对于一个具有n个顶点和e条边的无向图，在其邻接表中，含有____个边对于一个具有n个顶点和e条边的有向图，在其邻接表中，含有_______个弧结点。 4．十字链表是有向图的另一种链式存储结构，实际上是将_______和_______结合起来的一种链表。 5．在构造最小生成树时，克鲁斯卡尔算法是一种按_______的次序选择合适的边来构造最小生成树的方法；普里姆算法是按逐个将_______的方式来构造最小生成树的另一种方法。 6．对用邻接表表示的图进行深度优先遍历时，其时间复杂度为一；对用邻接表表示的图进行广度优先遍历时，其时间复杂度为_______。 7．对于一个具有n个顶点和e条边的连通图，其生成树中的顶点数为_______ ，边数为_______。 8．在执行拓扑排序的过程中，当某个顶点的入度为零时，就将此顶点输出，同时将该顶点的所有后继顶点的入度减1。为了避免重复检测顶点的入度是否为零，需要设立一个____来存放入度为零的顶点。 三、简答题 l．回答以下问题：

第二章数据结构习题作业

2.6．数据的存储结构主要有哪两种？它们之间的本质区别是什么？ 答：主要有：顺序存储结构和链式存储结构两种。 区别: 顺序存储结构是借助元素在存储器的相对位置来表示数据间的逻辑关系，而链式存储结构是借助指针来表示数据间的逻辑关系。 2.7 设数据结构的集合为D={d1,d2,d3,d4,d5},试指出下列各关系R所对应的数据结构B=(D,R)中哪些是线性结构，哪些是非线性结构。 （1）R={(d1,d2),(d2,d4),(d4,d2),(d2,d5),(d4,d1)}; ( 2 ) R={(d5,d4),(d4,d3),(d3,d1),(d1,d2)}; ( 3 ) R={(di,di+1)|i=4,3,2,1}; ( 4 ) R={(di,dj)|i

2.〉链表：扩展性强，易于删除，添加；内存中地址非连续；长度可以实时变化；适用于需要进行大量增添或删除元素操作而对访问元素无要求的程序。 （2）缺点 顺序表：插入，删除操作不方便；扩展性弱；不易删除，添加。 链表：不易于查询，索引慢。 （3）顺序表和链表的优缺点是互相补充的关系。 2.17 试比较单向链表与双向链表的优缺点。 答：（1）优点 单向链表：耗存储空间小； 双向链表：可以从任何一点开始进行访问; （2）缺点： 单向链表：访问时必须从头开始，耗时。 双向链表：耗存储空间大。 （3）两者为互补关系 2.22 CQ[0:10]为一循环队列，初态front=rear=1,画出下列操作后队的头，尾指示器状态： （1）d,e,h,g,入队； （2）d,e出队； （3）I,j,k,l,m入队； （4）b出队；

数据结构习题与答案

第 1 章绪论 课后习题讲解 1. 填空 ⑴（）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（）是数据的最小单位，（）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶从逻辑关系上讲，数据结构主要分为（）、（）、（）和（）。 【解答】集合，线性结构，树结构，图结构 ⑷数据的存储结构主要有（）和（）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸算法具有五个特性，分别是（）、（）、（）、（）、（）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹算法的描述方法通常有（）、（）、（）和（）四种，其中，（）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺在一般情况下，一个算法的时间复杂度是（）的函数。 【解答】问题规模 ⑻设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（），若为n*log25n，则表示成数量级的形式为（）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴顺序存储结构中数据元素之间的逻辑关系是由（）表示的，链接存储结构中的数据元素之间的逻辑关系是由（）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。

数据结构第一章课后习题与答案

第 1 章 绪 论 (2005-07-14) - 第 1 章 绪 论 课后习题讲解 1. 填空 ⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构 ⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模 ⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为 n*log25n，则表示成数量级的形式为（ ）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。

2. 选择题 ⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 ⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。 ⑶ 算法指的是（ ）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。 ⑷ 下面（ ）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 【解答】C 【分析】高效性是好算法应具备的特性。 ⑸ 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性

数据结构第7章 图习题

第7章图 一、单项选择题 1．在一个无向图G中，所有顶点的度数之和等于所有边数之和的______倍。 A．l/2 B．1 C．2 D．4 2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的______倍。 A．l/2 B．1 C．2 D．4 3．一个具有n个顶点的无向图最多包含______条边。 A．n B．n＋1 C．n-1 D．n(n-1)/2 4．一个具有n个顶点的无向完全图包含______条边。 A．n(n-l) B．n(n+l) C．n(n-l)/2 D．n(n-l)/2 5．一个具有n个顶点的有向完全图包含______条边。 A．n(n-1) B．n(n+l) C．n(n-l)/2 D．n(n+l)/2 6．对于具有n个顶点的图，若采用邻接矩阵表示，则该矩阵的大小为______。 A．n B．n×n C．n-1 D．(n-l) ×(n-l) 7．无向图的邻接矩阵是一个______。 A．对称矩阵B．零矩阵 C．上三角矩阵D．对角矩阵 8．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则表头向量的大小为______。 A．n B．e C．2n D．2e 9．对于一个具有n个顶点和e条边的无(有)向图，若采用邻接表表示，则所有顶点邻接表中的结点总数为______。

A．n B．e C．2n D．2e 10．在有向图的邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是入边也不是出边 11．在有向图的逆邻接表中，每个顶点邻接表链接着该顶点所有______邻接点。 A．入边B．出边 C．入边和出边D．不是人边也不是出边 12．如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是______。 A．完全图B．连通图 C．有回路D．一棵树 13．采用邻接表存储的图的深度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 14．采用邻接表存储的图的广度优先遍历算法类似于二叉树的______算法。 A．先序遍历B．中序遍历 C．后序遍历 D．按层遍历 15．如果无向图G必须进行二次广度优先搜索才能访问其所有顶点，则下列说法中不正确的是______。 A．G肯定不是完全图B．G一定不是连通图 C．G中一定有回路D．G有二个连通分量 16．下列有关图遍历的说法不正确的是______。 A．连通图的深度优先搜索是一个递归过程 B．图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C．非连通图不能用深度优先搜索法 D．图的遍历要求每一顶点仅被访问一次 17．下列说法中不正确的是______。 A．无向图中的极大连通子图称为连通分量

数据结构作业及答案

第一章绪论 一、选择题 1.数据结构是一门研究非数值计算的程序设计问题中计算机的1以及它们之间的2和运算等的学科。1 A.数据元素 B.计算方法 C.逻辑存储 D.数据映像 2 A.结构 B.关系 C.运算 D.算法 2.数据结构被形式地定义为(K, R)，其中K是1的有限集，R是K上的2有限集。 1 A.算法 B.数据元素 C.数据操作 D.逻辑结构 2 A.操作 B.映像 C.存储 D.关系 3.在数据结构中，从逻辑上可以把数据结构分成。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 4.线性结构的顺序存储结构是一种1的存储结构，线性表的链式存储结构是一种2的存储结构。A.随机存取 B.顺序存取 C.索引存取 D.散列存取 5.算法分析的目的是1，算法分析的两个主要方面其一是指2，其二是指正确性和简单性。1 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 2 A.空间复杂度和时间复杂度 B.研究算法中的输入和输出的关系 C.可读性和文档性 D.数据复杂性和程序复杂性k 6.计算机算法指的是1，它必须具备输入、输出和2等5个特性。 1 A.计算方法 B.排序方法 C.解决问题的有限运算序列 D.调度方法 2 A.可执行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 7.线性表的逻辑顺序与存储顺序总是一致的，这种说法。A.正确 B.不正确 8线性表若采用链式存储结构时，要求内存中可用存储单元的地址。 A.必须连续的 B.部分地址必须连续的 C.一定是不续的D连续不连续都可以 9.以下的叙述中，正确的是。A.线性表的存储结构优于链式存储结构 B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出10.每种数据结构都具备三个基本运算：插入、删除和查找，这种说法。A.正确B.不正确 二、填空题1.数据逻辑结构包括三种类型、和，树形结构和图形结构合称为。2.在线性结构中，第一个结点前驱结点，其余每个结点有且只有个前驱结点；最后一个结点后续结点，其余每个结点有且只有个后续结点。3.算法的五个重要特性是、、、、。 4.下面程序段的时间复杂度是。 for( i = 0; i < n; i++) for( j = 0; j < m; j++) A[i][j] = 0; 5.下面程序段的时间复杂度是。 i = s = 0; while ( s < n) { i ++; /* i = i +1*/ s += i; /* s = s + i*/ } 6.下面程序段的时间复杂度是。 s = 0; for( i = 0; i < n; i++) for( j = 0; j < n; j++) s += B[i][j]; sum = s; 7.下面程序段的时间复杂度是。 i = 1; while ( i <= n ) i = i * 3;

数据结构第七章图练习及答案

1．拓扑排序的结果不是唯一的，试写出下图任意2个不同的拓扑序列。 2．写出求以下AOE网的关键路径的过程。要求：给出每一个事件和每一个活动的最早开 始时间和最晚开始时间。 【解析】解题关键是弄清拓扑排序的步骤 （1）在AOV网中，选一个没有前驱的结点且输出；（2）删除该顶点和以它为尾的弧；（3）重复上述步骤直至全部顶点均输出或不再有无前驱的顶点。 【答案】（1）0132465 （2）0123465 【解析】求关键路径首先求关键活动，关键活动ai的求解过程如下 （1）求事件的最早发生时间ve(j), 最晚发生时间vl(j); （2）最早发生时间从ve(0)开始按拓扑排序向前递推到ve(6), 最晚发生时间从vl(6)按逆拓扑排序向后递推到vl(0); （3）计算e(i),l(i)：设ai由弧表示，持续时间记为dut，则有下式成立 e(i)=ve(j) l(i)=vl(k)-dut() （4）找出e(i)-l(i)=0的活动既是关键活动。 【答案】

关键路径为：a0->a4->a6->a9 7.1选择题 1．对于一个具有n个顶点和e条边的有向图，在用邻接表表示图时，拓扑排序算法时间复杂度为（B） A）O(n) B）O(n+e) C）O(n*n) D）O(n*n*n) 2．设无向图的顶点个数为n，则该图最多有（B）条边。 A）n-1 B）n(n-1)/2 C）n(n+1)/2 D）n2 3．连通分量指的是（B） A）无向图中的极小连通子图 B）无向图中的极大连通子图 C）有向图中的极小连通子图 D）有向图中的极大连通子图 4．n个结点的完全有向图含有边的数目（D） A）n*n B）n（n+1） C）n/2 D）n*（n-1） 5．关键路径是（A） A）AOE网中从源点到汇点的最长路径 B）AOE网中从源点到汇点的最短路径 C）AOV网中从源点到汇点的最长路径 D）AOV网中从源点到汇点的最短路径 6．有向图中一个顶点的度是该顶点的（C） A）入度B）出度C）入度与出度之和D）（入度+出度）/2 7．有e条边的无向图，若用邻接表存储，表中有（B）边结点。 A） e B）2e C）e-1 D）2(e-1) 8．实现图的广度优先搜索算法需使用的辅助数据结构为（B）

数据结构第十章习题课

1 .下列排序算法中，其中（ ）是稳定的。 A.堆排序，冒泡排序 B.快速排序，堆排序 C.直接选择排序，归并排序 D.归并排序，冒泡排序 2.若需在O （nlog 2n ）的时间内完成对数组的排序，且要求排序是稳定的，贝U 可选 择的排序方法是（ ）。 A.快速排序 B.堆排序 C.归并排序 D.直接插入排序 3.排序趟数与序列的原始状态有关的排序方法是（）排序法。 A .插入 B.选择 C.冒泡 D.快速 15， 21）排序，数据的排列次序在排序的过程中 （2） 15 47 25 84 21 （3） 15 21 25 84 47 （4） 15 21 25 47 84则采用的排序是 （ ） A.选择 B.冒泡 5. 对序列｛15，9，7，8，20，-1, 4｝进行排序，进行一趟后数据的排列变为｛4, 9, -1，8，20，7，15｝;则采用的是（ A.选择 B.快速 6. 若上题的数据经一趟排序后的排列为 ｛9，15，7，8, 是（ ）排序。 A .选择 B.堆 C.直接插入 D.冒泡 7. 在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（ ） A .直接插入排序 B .冒泡排序 C .简单选择排序 8. 下列排序算法中，（ ）算法可能会出现下面情况：在最后一趟开始之前, 所有元素都不在其最终的位置上。 A.堆排序 B.冒泡排序 C.快速排序 D.插入排序 9. 下列排序算法中，占用辅助空间最多的是: A.归并排序 B.快速排序 10. 用直接插入排序方法对下面四个 序列进行排序（由小到大），元素比较次数 最少的是（ ）O A . 94,32,40,90,80,46,21,69 B . 32,40,21,46,69,94,90,80 C . 21,32,46,40,80,69,90,94 D . 90,69,80,46,21,32,94,40 11. 若用冒泡排序方法对序列｛10,14,26,29,41,52｝从大到小排序，需进行 （ ） 4.对一组数据（84，47，25, 的变化为（1） 84 47 25 15 21 C.快速 D.插入 ）排序。 C.希尔 D.冒泡 20, -1 , 4｝，则采用的 C.希尔排序 D.堆排序