数据结构09
第九章查找习题
9.1若简单顺序查找算法所要查找的元素的下标从0开始，因而不能用监视哨，故查找失败时要返回-1。试设计相应的算法。
9.2对有序数据表（5,7,9,12,15,18,20,22,25,30,100），按二分查找方法模拟查找元素10和28，并分别画出其搜索过程。
9.3构造有20个元素的二分查找的判定树，并求解下列问题：
（1）各元素的查找长度最大是多少？
（2）查找长度为1、2、3、4、5的元素各有多少？具体是哪些元素？（假设下标从0开始）
（3）查找第13个元素依次要比较哪些元素？
9.4对有n个元素的有序表按二分查找方法查找时，最大的查找长度是多少？
9.5设计算法以构造有n个元素（下标范围从1到n）的二分查找的判定树。
9.6判断题：若二叉树中每个结点的值均大于其左孩子的值，小于其右孩子的值，则该二叉树一定是二叉排序树。
9.7分别以下列数据序列为输入构造二叉排序树，并计算出在等概率情况下的平均查找长度。
（1）100，60，20，80，50，150，110，120，200，70，135
（2）90，80，40，160，155，50，20，30，10，100，70，123，67
9.8设计算法，以求出给定二叉排序树中值为最大的结点。
9.9设计算法，对给定的二叉排序树，求出在等概论情况下的平均查找长度。
9.10对给定的二叉树，假设其中各结点的值均不相同，设计算法以判断该二叉树是否是二叉排序树。
9.11对给定的二叉树，假设其中可能存在值相同的结点，设计算法以判断该二叉树是否是二叉排序树。
9.12对给定的数组数据，其不同的输入序列是否一定可以构造出不同的二叉排序树？
9.13以数据集合{1,2,3,4,5,6}的不同序列为输入构造5棵高度为6的二叉排序树。
9.14已知一棵二叉排序树如下，其各结点的值虽然未知，但其中序序列为1,2,3,4,5,6,7,8,9。请标注各结点的值。
9.15分别以下列数据序列为输入构造平衡二叉树，并依次指出所用的调整操作。
（1）100，80，60，20，50，120，200，150，110，70，135
（2）10，20，30，40，50，100，90，80，70，60，155，23，67
（3）100，180，260，125，50，20，200，15，10，70，135
9.16选择数据集合{1,2,3,4,5,6，7}的某一序列为输入构造平衡二叉树，要求用到4
种调整操作。
9.17高度为8的平衡二叉树至少有多少个结点？高度为n的平衡二叉树至少有多少个结点？
9.18设计算法以判断给定的二叉树是否是平衡二叉树。
9.19*设计算法由键盘输入数据构造平衡二叉树。
9.20*设数组A[n]的元素递增有序，设计算法以数组A[n]的元素值构造平衡二叉树。
9.21设计算法在m阶B-树中(m>=3)中查找关键字x的位置。
9.22已知散列表地址区间为0～9,散列函数为H(k)=k % 7,采用线性探测法处理冲突。将关键字序列11,22,35,48,53,62,71,85依次存储到散列表中，试构造出该散列表，并求出在等概论情况下的平均查找长度。
9.23设散列函数为H(k)=k % 7，采用拉链法处理冲突，将关键字序列10,26,38,43,55,69,72,88,100,92依次存储到散列表中，并求出在等概论情况下的平均查找长度。
9.24设关键字序列为JAN,FEB,MAR,APR,MAY,JUN,JUL,AUG,SEP,OCT,NOV,DEC,散列函数为H(k)=序号/4，其中序号指首字母在字母表中的序号，例如，字母A的序号为1。采用拉链法处理冲突，构造出该散列表，并求出在等概论情况下的平均查找长度。
9.25已知散列表的地址区间为0～10，散列函数为H(k)=k % 11，采用线性探测法处理冲突。设计算法在其中查找值为x的元素，若查找成功，返回其下标，否则返回－1。
9.26已知散列表地址区间为0～10，散列函数为H(k)=k % 11，采用线性探测法处理冲突。设计算法将值为x的元素插入到表中。
9.27假设散列函数为H(k)=k % 7，采用拉链法处理冲突。设计算法在其中查找值为x 的元素。若查找成功，返回其所在结点的指针，否则返回NULL。
9.28*已知散列表地址区间为0～10，散列函数为H(k)=k % 11，采用线性探测法处理冲突。设计算法删除其中值为x的元素。
数据结构实验报告
数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 实验一线性表的顺序存储实验 一、实验目的 1、掌握用Visual C++6.0上机调试顺序表的基本方法 2、掌握顺序表的基本操作，插入、删除、查找等算法的实现 二、实验内容 1、顺序表基本操作的实现 [问题描述] 当我们要在顺序表的第i个位置上插入一个元素时，必须先将顺序表中第i个元素之后的所有元素依次后移一个位置，以便腾空一个位置，再把新元素插入到该位置。若是欲删除第i个元素时，也必须把第i个元素之后的所有元素前移一个位置。 [基本要求] 要求生成顺序表时，可以键盘上读取元素，用顺序存储结构实现存储。 实验二单链表实验 一、实验目的 1、掌握用Visual C++6.0上机调试单链表的基本方法 2、掌握单链表的插入、删除、查找、求表长以及有序单链表的合并算法的实现 二、实现内容 1、单链表基本操作的实现 [问题描述]要在带头结点的单链表h中第i个数据元素之前插入一个数据元素x ，首先需要在单链表中寻找到第i-1个结点并用指针p 指示，然后申请一个由指针s 指示的结点空间，并置x为其数据域值，最后修改第i-1个结点，并使x结点的指针指向第i个结点，要在带头结点的单链表h中删除第i个结点，首先要计数寻找到第i个结点并使指针p指向其前驱第i-1个结点，然后删除第i个结点并释放被删除结点空间。 [基本要求]用链式存储结构实现存储 [实现提示]链式存储结构不是随机存储结构，即不能直接取到单链表中某个结点，而要从单链表的头结点开始一个一个地计数寻找。 2、求表长以及有序单链表的合并算法的实现 [问题描述] 假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并计算表长。要求利用原来两个单链表的结点存放归并后的单链表。 [基本要求]用链式存储结构实现存储 实验三栈的实现及应用 一、实验目的 1、掌握顺序栈的类型定义方法。 2、掌握在顺序栈上实现的六种基本算法。 2、掌握顺序栈的简单应用。 二、实验内容 数据结构和软件工程简介 数据结构的基本概念 ?数据是描述客观事物并能为计算机加工处理的符号的集合。数据元素是数据的基本单位，即数据集合中的个体。有些情况下也把数据元素称为结点、记录等。一个数据元素可由一个或多个数据项组成。数据项是有独立含义的数据最小单位，有时也把数据项称为域、字段等。 ?数据结构（Data Structure）是指数据元素的组织形式和相互关系。数据结构一般包括以下三方面的内容。 1、数据的逻辑结构 ?数据的逻辑结构从逻辑上抽象地反映数据元素间的结构关系，它与数据在计算机中的存储表示方式无关。 因此，数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 ?数据的逻辑结构有两大类： ?线性结构——线性结构的逻辑特征是：有且仅有一个始端结点和一个终端结点，并且除两个端点结点外的所有结点都有且仅有一个前趋结点和一个后继结点。线性表、堆栈、队列、数组、串等都是线性结构。 ?非线性结构——非线性结构的逻辑特征是：一个结点可以有多个前趋结点和后继结点。如树形结构、图等 2、数据的物理结构 ?数据的物理结构是逻辑结构在计算机存储器里的映像，也称为存储结构。 ?数据的存储结构可用以下四种基本存储方法体现： ?顺序存储方法——把逻辑上相邻的结点存储在物理位置上相邻的存储单元里，结点之间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储结构称为顺序存储结构。 ?链式存储方法——不要求逻辑上相邻的结点在物理位置上也相邻，结点之间的逻辑关系是由附加的指针字段表示的。由此得到的存储结构称为链式存储结构。 ?索引存储方法——在存储结点信息的同时，还建立附加的索引表，索引表中的每一项称为索引项。索引项由关键字和地址组成，关键字是能惟一标识一个结点的那些数据项，而地址一般是指示结点所在存储位置的记录号。 ?散列存储方法——根据结点的关键字直接计算出该结点的存储地址。 ?用不同的存储方法对同一种逻辑结构进行存储映像，可以得到不同的存储结构。四种基本的存储方法也可以组合起来对数据逻辑结构进行存储映像。 3、数据的运算 ?数据的运算是指对数据施加的操作。它是定义在数据的逻辑结构上的，但运算的具体实现要在物理结构上进行。数据的每种逻辑结构都有一个运算的集合，常用的运算有检索、插入、删除、更新、排序等 线性表： 1．顺序表 ?当线性表采用顺序存储结构时称之为顺序表。在顺序表中，数据元素按逻辑次序依次放在一组地址连续的存储单元里。由于逻辑上相邻的元素存放在内存的相邻单元里，所以顺序表的逻辑关系蕴含在存储单元的邻接关系中。在高级语言中，可以直接用数组实现。 2. 单链表 ?采用链式存储结构的链表是用一组任意的存储单元来存放线性表的数据元素，这组存储单元既可以是连续的，也可以是不连续的，甚至可以是零星分布在内存中的任何位置上，从而可以大大提高存储器的使用效率。 ?在线性链表中，每个元素结点除存储自身的信息外，还要用指针域额外存储一个指向其直接后继的信息（即后继的存储位置：地址）。 3. 栈与队列 栈与队列是两种特殊的线性表。即它们的逻辑结构与线性表相同，只是其插入、删除运算仅限制在线性表的一端或两端进行。 一，实验题目 实验十一：图实验 采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析 本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1，数据的输入形式和输入值的范围：输入的图的结点均为整型。 2，结果的输出形式：输出的是两结点间是否存在路径的情况。 3，测试数据：输入的图的结点个数为：4 输入的图的边得个数为：3 边的信息为：1 2，2 3，3 1 三，概要设计 （1）为了实现上述程序的功能，需要： A，用邻接表的方式构建图 B，深度优先遍历该图的结点 C，判断任意两结点间是否存在路径 （2）本程序包含6个函数： a，主函数main（） b，用邻接表建立图函数create_adjlistgraph() c，深度优先搜索遍历函数dfs() d，初始化遍历数组并判断有无通路函数dfs_trave() e，输出邻接表函数print() f，释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示： 四，详细设计 （1）邻接表中的结点类型定义： typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; （2）邻接表中头结点的类型定义： typedef struct{ char vexdata; arcnode *firstarc; }adjlist; （3）邻接表类型定义： typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; （4）深度优先搜索遍历函数伪代码： int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } （5）初始化遍历数组并判断有无通路函数伪代码： void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五，源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组 数据结构试卷（一） 一、单选题（每题2 分，共20分） 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4.设有一个二维数组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 5.树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 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 8.对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O（1） B. O（n） C. O（1og2n） D. O（n2） 9.对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K） =K %9作为散列函数，则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 10.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、填空题（每空1分，共26分） 1.通常从四个方面评价算法的质量：_________、_________、_________和_________。 2.一个算法的时间复杂度为(n3+n2log2n+14n)/n2，其数量级表示为________。 3.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数 为__________个，树的深度为___________，树的度为_________。 4.后缀算式9 2 3 +- 10 2 / -的值为__________。中缀算式（3+4X）-2Y/3对应的后缀算式 为_______________________________。 5.若用链表存储一棵二叉树时，每个结点除数据域外，还有指向左孩子和右孩子的两个指 针。在这种存储结构中，n个结点的二叉树共有________个指针域，其中有________个指针域是存放了地址，有________________个指针是空指针。 6.对于一个具有n个顶点和e条边的有向图和无向图，在其对应的邻接表中，所含边结点 分别有_______个和________个。 7.AOV网是一种___________________的图。 8.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有 向完全图中，包含有________条边。 9.假定一个线性表为(12,23,74,55,63,40)，若按Key % 4条件进行划分，使得同一余数的元 素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。 K 1373—2 20139730236 余玲 数据结构与程序构建第十三十四章笔记在阅读完数据结构与程序构建的第十三章后，了解了许多查找程序设计。同时也了解到查找技术在编程中作用很大，是重要的操作基础之一。 顺序查找就是线性表遍历查找法。从表的一端开始，向另一端逐个按给定值与关键码进行比较，若找到。查找成功。，并给出数据元素在表中的位置；若整个表检测完，未找到相同的关键码，则查找失败。给出失败信息。 从数据结构的逻辑关系层面考虑，顺序查找的方向是可以从左到右，也可以是从右到左。但是如果进一步考虑存储结构，该结论就不一定正确，比如单链表只能从左到右，如果决定使用链表，又要考虑从右到左的查找，显然必须启用双向链表，为了操作方便性而付出空间代价。 主要源码（顺序查找） Int seqsearching::ltorsearching(int*data,int length,int seekdata) { Int i=1; While(i<=length && data[i]!=seekdata) I++; If(i<=length) Return i; Else Return 0; } Int seqsearching::rtorsearching(int*data,int length,int seekdata) { Int i=length; While(i>0 && data[i]!=seekdata) I--; If(i>=1) Return i; Else Return 0; } Int seqsearching::gtorsearching(int*data,int length,int seekdata) { Data[0]=seekdata; Int i=length; While(data[i]!=seekdata) I--; Return i; } Int seqsearching::displaydata(int*data,int length) { Int i; Count<<“坐标” For(i=1;i<=length;i++) Count< 数据结构实验---图的储存与遍历 学号： 姓名： 实验日期： 2016.1.7 实验名称： 图的存贮与遍历 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 V0 V1 V2 V3 V4 三、附录： 在此贴上调试好的程序。 #include #define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;i 数据结构09 一. 填空题（26分，每空2分） 1. 声明抽象数据类型的目的是________________________________________。 2. 已知结点类Node 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 《数据结构》试题参考答案 （开卷） （电信系本科2001级 2002年12月） 一、回答下列问题 (每题4分，共36分) 1. 某完全二叉树共有15381个结点，请问其树叶有多少个？ 答：n2=?n/2?=?15381/2?=7691(个) 2. 假设有二维数组A 7×9，每个元素用相邻的6个字节存储，存储器按字节编址。已知A 的起始存储位置（基地址）为1000，末尾元素A[6][8]的第一个字节地址为多少？若按列存储时，元素A[4][7]的第一个字节地址为多少？ 答：① 末尾元素A[6][8]的第一个字节地址＝1000＋（7行×9列—1）×6B ＝1000＋62×6=1372 ②按列存储时，元素A[4][7]的第一个字节地址＝1000＋（7列×7行＋4）×6B ＝1000＋53×6=1318 3. 在KMP 算法中，已知模式串为ADABBADADA ，请写出模式串的next[j]函数值。 答：根据 0 当j ＝1时 next[ j ]＝ max { k |1 实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列，要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include 求A QB #include 学生姓名__________ 学号_________________院系___________ 班级___________ -------------------------------密------------------------------封----------------------------线--------------------------------- 烟台大学20 09 ～20 10 学年第 二 学期 数据结构 试卷A （考试时间为120分钟） （注：第三大题答案请写在后面的空白答题纸上） 一、选择题(每小题2分，共20分) 1. 以下四类基本的逻辑结构反映了四类基本的数据组织形式，解释错误的是 ( ) A 、集合中任何两个结点之间都有逻辑关系但组织形式松散 B 、线性结构中结点按逻辑关系依次排列形成一条"锁链" C 、树形结构具有分支、层次特性，其形态有点像自然界中的树 D 、图状结构中的各个结点按逻辑关系互相缠绕，任何两个结点都可以邻接 2. 若结点的存储地址与其关键字之间存在某种映射关系，则称这种存储结构为( ) A 、顺序存储结构 B 、链式存储结构 C 、索引存储结构 D 、散列存储结构 3. 在长度为n 的顺序表的第i (1≤i ≤n+1)个位置上插入一个元素，元素的移动次数为( ) A 、n-i+1 B 、n-i C 、i D 、i-1 4. 对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为( ) A 、顺序表 B 、用头指针表示的单循环链表 C 、用尾指针表示的单循环链表 D 、单链表 5. 一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是（ ） A 、e d c b a B 、d e c b a C 、d c e a b D 、a b c d e 6. 已知图1如右所示，若从顶点A 出发按深度优先搜索进行遍历， 则可能得到的顶点序列为（ ） A 、 A ，B ，E ，C ，D ，F B 、 A ，C ，F ，E ，B ，D C 、 A ，E ，B ，C ，F ，D D 、 A ，E ，D ，F ，C ，B 7. n 个顶点的有向图中含有向边的数目最多为 ( ) A 、n-1 B 、n C 、n(n-1)/2 D 、n(n-1) 8. 若一个栈的输入顺序是1，2，…，n ，输出序列的第一个元素是n ，则第i （1≤i ≤n ）个输出元素是（ ） A 、n-i B 、n-i-1 C 、i+1 D 、n -i+1 9. 已给图2，（ ）是该图的正确的拓扑排序序列 A 、1，2，3，4，5 B 、1，3，2，4，5 C 、1，2，4，3，5 D 、1，2，3，5，4 10. 为查找某一特定单词在文本中出现的位置，可应用的串运算是( ) A 、插入 B 、删除 C 、串联接 D 、子串定位 二、填空题(每小题2分，共30分) 1. 存储结构是逻辑结构的__________实现。 2. 若一个算法中的语句频度之和为T(n)=n+4nlogn ，则算法的时间复杂度为________。 3. 数组A[1..10,-2..6,2..8]以行优先顺序存储，设基地址为100，每个元素占3个存储单元，则元素A[5,0,7]的存 储地址是 。 4. 在无向图的邻接矩阵A 中，若A[i,j]等于1，则A[j,i]等于________。 5. 对带有头结点的链队列lq ，判定队列中只有一个数据元素的条件是___________。 图2 4.1数据结构与算法 1.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算和操作包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构；（2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构； （3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点； （2）每一个结点最多有一个前件，也最多有一个后件。 非线性结构：不满足线性结构条件的数据结构。 1．3 线性表及其顺序存储结构 线性表由一组数据元素构成，数据元素的位置只取决于自己的序号，元素之间的相对位置是线性的。 在复杂线性表中，由若干项数据元素组成的数据元素称为记录，而由多个记录构成的线性表又称为文件。 非空线性表的结构特征： （1）且只有一个根结点a1，它无前件； 2009年全国自考数据结构模拟试卷(一) 一、单项选择题(本大题共15小题,每小题2分,共30分)在每小题列出的四个备选项目中只有一个是符号题目要求的,请将其代码填写的括号内.错选、多选或未选均无分。 1. 任何一个带权的无向连通图的最小生成树() A. 只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在 答案：B 2. Aarr和Barr两个数组的说明如下： VARAarr:Array［0··7］of char; Barr:Array［-5··2,3,··8］of char; 这两个数组分别能存放的字符的最大个数是() A. 7和35 B. 1和5 C. 8和48 D. 1和6 答案：C 3. 下列说法中正确的是() A. 任何一棵二叉树中至少有一个结点的度为2 B. 任何一棵二叉树中的每个结点的度为2 C. 任何一棵二叉树中的度肯定等于2 D. 任何一棵二叉树中的度可以小于2 答案：D 4. 二分查找算法要求被查找的表是() A. 键值有序的链表 B. 键值不一定有序的链表 C. 键值有序的顺序表 D. 键值不一定有序的顺序表 答案：C 5. 设图G采用邻接表存储，则拓扑排序算法的时间复杂度为() A. O(n) B. O(n+e) C. O(n2) D. O(n×e) 答案：B 6. 设数组data［0..m］作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为() A. front:＝front+1 B. front:＝(front+1)mod m C. rear:＝(rear+1)mod m D. front:＝(front+1)mod (m+1) 答案：D 7. 设串s1=′ABCDEFG′,s2=′PQRST′,函数con(x,y)返回x和y串的连(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的 con(subs(s1,2,len(s2)),subs(s1,len(s2),2)的结果串是() A. BCDEF B. BCDEFG C. BCPQRST D. BCDEFEF 答案：D 8. 设二叉树根结点的层次为0，一棵高度为h的满二叉树中的结点个数是() A. A B. B C. C D. D 答案：D 9. 森林T中有4棵树 ，第一、二、三、四棵树的结点个数分别是n1,n2,n3,n4，那么当把森林T转换成一棵二叉树后，其根结点的左孩子上有() 个结点。 A. n1-1 B. n1 C. n1+n2+n3 D. n2+n3+n4 答案：A 10. 对广义表((a),(b))进行下面的操作head(head((a),(b)))后的结果是() A. a B. (a) 图实验 一，邻接矩阵的实现 1.实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现 2.实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历 3．设计与编码 #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template 数据结构教程 上机实验报告 实验七、图算法上机实现 一、实验目的： 1.了解熟知图的定义和图的基本术语，掌握图的几种存储结构。 2.掌握邻接矩阵和邻接表定义及特点，并通过实例解析掌握邻接 矩阵和邻接表的类型定义。 3.掌握图的遍历的定义、复杂性分析及应用，并掌握图的遍历方 法及其基本思想。 二、实验内容： 1.建立无向图的邻接矩阵 2.图的深度优先搜索 3.图的广度优先搜索 三、实验步骤及结果： 1.建立无向图的邻接矩阵： 1)源代码： #include "" #include "" #define MAXSIZE 30 typedef struct { char vertex[MAXSIZE]; ertex=i; irstedge=NULL; irstedge; irstedge=p; p=(EdgeNode*)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } int visited[MAXSIZE]; ertex); irstedge; ertex=i; irstedge=NULL; irstedge;irstedge=p; p=(EdgeNode *)malloc(sizeof(EdgeNode)); p->adjvex=i; irstedge; irstedge=p; } } typedef struct node { int data; struct node *next; }QNode; ertex); irstedge;ertex); //输出这个邻接边结点的顶点信息 visited[p->adjvex]=1; //置该邻接边结点为访问过标志 In_LQueue(Q,p->adjvex); //将该邻接边结点送人队Q } 汕头职业技术学院 2008-2009学年第一学期期末试卷（C） 课程名称数据结构学分_____ 拟题人何汉阳审题人___________ 系(校区) 计算机系班级_____________ __ 学号_____ 姓名_ _________ 一、填空（26分，每空一分） 1.在设计算法和程序时，不仅要考虑数据的____________及其_________，而且要考虑数据在存储器中 的____________。 2.算法设计的基本要求是：_____________、_____________和_____________。 3.估算算法运行时间的基本考虑是：确定问题的_______和确定算法执行基本操作的_______，在难以精 确计算基本执行次数的情况下，只考虑相对于问题规模N的_______。 4.对于长度为n的顺序表的删除算法，它的最坏情况时间复杂性及其量级分别是______和______，平均 时间复杂性及其量级分别为________和________。 5.串的堆型存储结构的特点是：仍以一组地址_______的存储单元存放串的字符序列，但其存储空间是 在算法执行过程中____________得到的。 6.顺序队列存在假满现象，解决这个问题的常用方法是构建_______________。 7.图的常用存储结构有__________和__________，Prim 算法是选用____________来存储图中的所有边。 8.解决散列查找的两个主要问题是：(1)构造一个计算简单且冲突尽量少的、地址分布比较_______的 ______________; (2)拟定解决__________的方案。 9.假定一个顺序表的长度为50，并假定查找每个元素的概率都相同，则在查找成功情况下的平均查找长 度_________，在查找不成功情况下的平均查找长度_________。 10.关键字比较的次数与记录的初始排列次序无关的排序方法是_______排序；每次使两个相邻的有序表 合成一个有序表的排列方法叫做________排序。 二、选择题（在正确答案上打“√”，共20分，每小题2分） 1、下面关于线性表的叙述中，错误的是______。 A）线性表采用顺序存储，必须占用一片连续的存储单元 B）线性表采用链接存储，不必占用一片连续的存储单元 C）线性表采用链接存储，可以随机存取表中的任一结点 D）线性表采用顺序存储，无须为表示结点间的逻辑关系而增加额外的存储空间 2、若某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用_____存储方式最节省运算时间。数据结构实验题目数据结构实验题目09级
数据结构和软件工程简介
数据结构实验十一：图实验
算法与数据结构试题及答案
数据结构与程序
数据结构实验---图的储存与遍历
南京工程学院数据结构样卷09级加答案
数据结构实验报告图实验
数据结构试卷和答案
数据结构实验
烟台大学数据结构试题2009~2010年度
软件技术基础(包含数据结构、软件工程、数据库基础知识和基本内容)
2009年全国自考数据结构模拟试卷(一)及答案
数据结构实验报告图实验
数据结构图实验报告
2008-09(1)数据结构期末试卷(C)
- 烟台大学数据结构试题2009~2010年度
- 南京工程学院数据结构样卷09级附答案
- 09-10第二学期数据结构试卷B-答案
- 南京工程学院数据结构样卷09级附答案
- 09级《数据结构》课程设计任务书
- 数据结构实验题目数据结构实验题目09级
- 2008-09(1)数据结构期末试卷(C)
- 《数据结构》 样题
- 数据结构期末考卷09级
- 数据结构试题2010~2011年度
- 2009级数据结构试卷A及答案
- 数据结构试卷和答案
- 数据结构09级信本期中试卷.2011.5.5
- 2009年全国自考数据结构模拟试卷(六)及答案
- 2009年全国自考数据结构模拟试卷(四)及答案
- 2009年全国自考数据结构模拟试卷(九)及答案
- 南京工程学院 数据结构样卷09级附答案
- 09 详细设计 面向数据结构
- 数据结构实验指导09级.
- 《数据结构》期末考A、B卷(本科)范文