数据结构A (2)
计算机科学与信息工程学院期末考试
数据结构 试卷（ A 卷）
专业: 课程代码: 学号: 姓 名:
一、单选题（每小题2分，共30分）
1.数据在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为________。
A. 存储结构
B. 逻辑结构
C. 顺序存储结构
D. 链式存储结构
[能力层次：记忆 ]；[难易度： A ]
2. 线性表的链式存储结构与顺序存储结构相比优点是________。
A. 所有的操作算法简单
B. 便于插入和删除
C. 便于利用零散的存储器空间
D. 便于随机存取
[能力层次：理解 ]；[难易度： C ]
3. 两个指针P 和Q ，分别指向单链表的两个元素，P 所指元素是Q 所指元素前驱的条件是________。
A. P->next==Q->next
B. P->next== Q
C. Q->next== P
D. P== Q
[能力层次：理解 ]；[难易度： C ]
4. 在单链表中，若*p 不是尾结点，在其后插入*s 结点的操作是_______。
A. s->next =p; p->next=s;
B. s->next=p->next; p->next=s;
C. s->next=p->next; p=s;
D. p->next=s; s->next=p;
[能力层次：简单运用]；[难易度： C ]
5. 从一个栈顶指针为top 的链栈中删除一个结点时，用x 保存被删除的结点，应执行下列________命令。
A．x=top;top=top->next; B．top=top->next;x=top->data;
C．x=top->data; D．x=top->data;top=top->next;
[能力层次：理解 ]；[难易度： C ]
6. 设已将元素a1, a2, a3依次入栈，元素a4正等待进栈。那么下列4个序列中不可能出现的出栈序列是__________。
A. a3 a1 a4 a2
B. a3 a2 a4 a1
C. a3 a4 a2 a1
D. a4 a3 a2 a1
[能力层次：理解 ]；[难易度： C ]
7. 串是一种特殊的线性表，其特殊性体现在__________。
A.可以顺序存储B．数据元素是一个字符
C.可以链接存储D．数据元素可以是多个字符
[能力层次：理解 ]；[难易度： B ]
8.数组A[6,10]的每个元素占4个存储单元，若按行优先次序存进行存储，数组元素A[3,5]的存储地址为1000，则A[0,0]的存储地址是_______。
A. 872
B. 860
C.868
D. 864
[能力层次：简单运用]；[难易度： D ]
9..一棵二叉树如下图1所示，按中序遍历的序列为_______。
图1
A. abdgcefh
B. dgbaechf
C. gdbehfca
D. abcdefgh
[能力层次：简单运用]；[难易度： D ]
10.判断线索二叉树中某结点*p有左孩子的条件是_______。
A. p->lchild==null
B. p->lchild==null
C. p->ltag==0
D. p->ltag==1
[能力层次：简单运用]；[难易度： C ]
11. A，B为一棵二叉树上的两个结点，在中序遍历时，A在B前的条件是______。
A. A在B的右方
B. A是B的祖先
C. A在B左方
D. A是B子孙
[能力层次：简单运用]；[难易度： B ]
12. 一个有n个顶点的无向图最多有_________条边。
A. n
B. n(n-1)
C. n(n-1)/2
D. 2n
[能力层次：理解 ]；[难易度： B ]
13. 任何一个无向连通图________最小生成树。
A.只有一棵
B. 有一棵或多棵
C. 一定有多棵
D. 可能不存在
[能力层次：简单运用]；[难易度： D ]
14. 有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下，查找成功所需的平均比较次数为________。
A. 35/12
B. 37/12
C. 39/12 D, 43/12
[能力层次：简单运用]；[难易度： D ]
15. 下列排序方法中，时间复杂度不受数据初始状态影响，恒为O(n2)的是_______。
A. 堆排序
B.冒泡排序
C. 直接选择排序
D.快速排序
[能力层次：理解 ]；[难易度： C ]
二、填空题（每空2分，共30分）
1.数据有_________结构和___________结构两种结构。
[能力层次：记忆 ]；[难易度： B ]
2.在数据结构中，评价算法的两个重要指标是算法的时间复杂度和__________。
[能力层次：记忆 ]；[难易度： B ]
3．已知广义表A=（（a,b）,(c,d)）,则tail(A)等于__________。
[能力层次：记忆 ]；[难易度： C ]
4. 栈是限定在___________进行插入和删除操作的线性表。
[能力层次：记忆 ]；[难易度： C ]
5．二分查找要求查找表中所有元素必须按关键字排列。
[能力层次：记忆 ]；[难易度： B ]
6．哈夫曼树是访问叶子结点的外部路径长度________的二叉树。
[能力层次：记忆 ]；[难易度： C ]
7．n个顶点的连通图的生成树具有条边。
[能力层次：记忆 ]；[难易度： C ]
8.对于一棵具有n个结点的树，该树中所有结点的度之和为。
[能力层次：记忆 ]；[难易度： B ]
9. 在哈希函数H(key)=key mod p中，p最好取_______。
[能力层次：记忆 ]；[难易度： B ]
10. 若要对某二叉排序树进行遍历，保证所有结点序列按键值递增有序排列，应对该二叉树采用________遍历法。
[能力层次：记忆 ]；[难易度： C ]
11.在一个长度为n的顺序表中向第i个元素（0 [能力层次：记忆 ]；[难易度： C ] 12.有如下图2，其深度优先遍历序列是_________，广度优先遍历序列是_______。 图2 [能力层次：记忆 ]；[难易度： B ] 13.对n（n>0）个记录进行冒泡排序，最少要交换_______记录。 [能力层次：记忆 ]；[难易度： C ] 三、应用题（每题4分，共20分） 1.双向链表的类型为： typedef struct node { datatype element; struct node *prior,*next; } Dlistnode; Dlistnode *p, *s; 在双向链表L中，p指向L链表中某一结点（非头结点），写出在p结点之后插入s 所指结点的语句。 [能力层次：综合运用 ]；[难易度： C ] 2.已知一棵二叉树的前序序列和中序序列分别为ABDGHCEFI和GDHBAECIF请画出此二叉树并写出后序遍历序列。 [能力层次：综合运用 ]；[难易度： D ] 3.有字符a,b,c,d,e,f,其权值分别为5，18，12，2，8，30，试构造Huffman树；并求出 每个字符的哈夫曼编码。 [能力层次：综合运用 ]；[难易度： C ] 4.分别采用Prim算法（以顶点1为结点）和Kruskal算法给出下图3的最小生成树。 图3 [能力层次：综合运用 ]；[难易度： D ] 5. 给定结点的关键字序列为：19,14,23,1,68,20,84,27,55,11,10,79.设该散列表的长度为13,散列函数为：H(K)=K%13。 画出线性探测再散列解决冲突时所构造的散列表，并求出其平均查找长度。 [能力层次：综合运用 ]；[难易度： D ] 四、算法填空（每题5分，共10分）。 1．将两个有序的顺序表合并成一个有序表 void merge(int R[ ], int A[ ],int s1,int m,int s2) //对两个升序顺序表R[s1]~R[n]和R[n+1]~R[s2]合并，结果存入升序顺序表A中{ int i,j,k; i=s1;j=m+1;k=s1; while((i<=n)&&(j<=________)) if(R[i]<=R[j]) { A[k]=R[i];i++;______;} else {A[k]=R[j]; ______ ;k++;} while(i<= ) //复制第一个区间中剩下元素 { A[k]=R[i];i++;k++;} while(j<=s2) //复制第二个区间中剩下元素 { ;j++;k++;} } [能力层次：综合运用 ]；[难易度： C ] 2.下面是实现线索二叉树的遍历算法 //--------二叉树的二叉线索存储表示--------- Typedef enum PointerTag { Link, Thread };//Link=0; 指针，Thread==1:线索 Typedef struct BithrNode { TElemType data; Struct BithrNode *lchild, *rchild; //左右孩子指针 PointerTag LTag, _________; //左右标志 }BiThrTree; 算法为： Status InOrderTraverse_Thr(BiThrTree T, Status(*Visit(TElemType e)){ //本线索二叉树带有头结点T，T指向头结点，头结点的左链lchild指向根结点，中//序遍历二叉线索树T的非递归算法，对每个数据元素调用函数Visit. p=T->lchild; //p指向根结点 while (__________) { //空树或遍历结束时，p==T while (p->LTag==Link) ____________; if (!Visit(p->data)) return ERROR; //访问其左子树为空的结点 while (_____________&&p->rchild!=T) { p=p->rchild; Visit(p->data); // 访问后继结点 } _______________; } Return OK; } [能力层次：综合运用 ]；[难易度： D ] 设顺序表L是一个递增有序表（不允许有相同的值），试写一算法将x插入L中，并使L仍是一个有序表。 [能力层次：综合运用]；[难易度：D ] 顺序表的存储结构如下： Typedef struct { Elemtype *data; //存储空间基址 Int Length; //当前长度 } SqList; 算法名定义为： void Insert(SqList &L, DataType x) { } 数据结构实验总结报告 李博杰PB10000603 一、调试过程中遇到哪些问题？ （1）在二叉树的调试中，从广义表生成二叉树的模块花了较多时间调试。 由于一开始设计的广义表的字符串表示没有思考清晰，处理只有一个孩子的节点时发生了混乱。调试之初不以为是设计的问题，从而在代码上花了不少时间调试。 目前的设计是： Tree = Identifier(Node,Node) Node = Identifier | () | Tree Identifier = ASCII Character 例子：a(b((),f),c(d,e)) 这样便消除了歧义，保证只有一个孩子的节点和叶节点的处理中不存在问题。 （2）Huffman树的调试花了较长时间。Huffman编码本身并不难处理，麻烦的是输入输出。 ①Huffman编码后的文件是按位存储的，因此需要位运算。 ②文件结尾要刷新缓冲区，这里容易引发边界错误。 在实际编程时，首先编写了屏幕输入输出（用0、1表示二进制位）的版本，然后再加入二进制文件的读写模块。主要调试时间在后者。 二、要让演示版压缩程序具有实用性，哪些地方有待改进？ （1）压缩文件的最后一字节问题。 压缩文件的最后一字节不一定对齐到字节边界，因此可能有几个多余的0，而这些多余的0可能恰好构成一个Huffman编码。解码程序无法获知这个编码是否属于源文件的一部分。因此有的文件解压后末尾可能出现一个多余的字节。 解决方案： ①在压缩文件头部写入源文件的总长度（字节数）。需要四个字节来存储这个信息（假定文件长度不超过4GB）。 ②增加第257个字符（在一个字节的0~255之外）用于EOF。对于较长的文件，会造成较大的损耗。 ③在压缩文件头写入源文件的总长度%256的值，需要一个字节。由于最后一个字节存在或不存在会影响文件总长%256的值，因此可以根据这个值判断整个压缩文件的最后一字节末尾的0是否在源文件中存在。 （2）压缩程序的效率问题。 在编写压缩解压程序时 ①编写了屏幕输入输出的版本 ②将输入输出语句用位运算封装成一次一个字节的文件输入输出版本 ③为提高输入输出效率，减少系统调用次数，增加了8KB的输入输出缓存窗口 这样一来，每写一位二进制位，就要在内部进行两次函数调用。如果将这些代码合并起来，再针对位运算进行一些优化，显然不利于代码的可读性，但对程序的执行速度将有一定提高。 第七章图：习题 习题 一、选择题 1．设完全无向图的顶点个数为n，则该图有( )条边。 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。为了避免重复检测顶点的入度是否为零，需要设立一个____来存放入度为零的顶点。 一、定义与术语 图：无序数据结构 基本构成：1.边集（Edge ）：a. 有向图，有向边 数据结构总结 -标准化文件发布号：（9556-EUATWK-MWUB-WUNN-INNUL-DDQTY-KII 一、单项选择（每题2分，共 20 分） 1、分析下面程序段的时间复杂度： ( ) i=1;j=1; while(i<=n) i=i*3; while(j<=n) j++; A、O(n+log3n) B、O(n) C、O(log3n) D、O(n*log3n) 2、下面关于串的的叙述中，哪一个是不正确的： （） A、串是字符的有限序列 B、空串是由空格构成的串 C、模式匹配是串的一种重要运算 D、串既可以采用顺序存储，也可以 采用链式存储 3、从逻辑上可以把数据结构分为两大类（） A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 4、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删 除运算，则利用（）存储方式最节省时间。 A．顺序表B．双链表C．带头结点的双循环链表 D．单循环链表 5、有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈 序列？（） A. 5 4 3 6 1 2 B. 4 5 3 1 2 6 C. 3 4 6 5 2 1 D. 2 3 4 1 5 6 6、最大容量为n的循环队列，队尾指针是rear，队头是front，则队满的条件是（） A. (rear+1) MOD n=front B. rear=front C．rear+1=front D. (rear-l) MOD n=front 7、在一个长度为n的顺序表中删除第i个元素，需向前移动（）个元素。 A. n B.i-1 C.n-i D.n-i+1 8、对一颗具有n个节点的树，其中所有度之和等于（）。 A. n B.n-1 C.n-2 D.n+1 9、某二叉树的前序和后序序列正好相反，则该二叉树一定是： ( ) A、高度等于其结点数 B、任意一个二叉树 C、所有节点均无左孩子 D、所有节点均无右孩子 10、已知一棵完全二叉树的第6层（根节点为第一层）有8个叶子节点，则完 全二叉树的节点个数至多是： A、39 B、52 C、111 D、119 ( ) 11、以下数据结构中，（）是非线性数据结构。 A．树 B．字符串 C．队 D．栈 12、设栈N和队列M初始状态为空，元素1,2,3,4,5,6依次通过栈N，一个元素 出栈后进队列M，若6个元素出队的序列是2,4,3,6,5,1,则栈N的容量至少应该 是： ( ) A、2 B、3 C、4 D、5 13、一棵完全二叉树上有100个结点，其中叶子结点的个数是 （） A． 50 B． 51 C．52 D．49 14、有关二叉树下列说法正确的是（） A．二叉树的度为2 B．一棵二叉树的度可以小于2 吉首大学试题库 一、一、单选题（每题2 分，共20分） 1. 1. 栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2. 2. 用链接方式存储的队列，在进行插入运算时( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 3. 3. 以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 4. 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. 5. 树最适合用来表示( )。 A.有序数据元素 B.无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6. 6. 二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.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.8. 对n个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. O（1） B. O（n） C. O（1og2n） D. O（n2） 9.9. 对于线性表（7，34，55，25，64，46，20，10）进行散列存储时，若选用H（K）=K %9 作为散列函数，则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 10.10. 设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。 A.5 B.6 C.7 D.8 二、二、填空题（每空1分，共26分） /* *题目：编写按键盘输入的数据建立图的邻接矩阵存储 * 编写图的深度优先遍历程序 * 编写图的广度优先遍历程序 * 设计一个选择式菜单形式如下： * 图子系统 * *********************************** * * 1------更新邻接矩阵* * * 2------深度优先遍历* * * 3------广度优先遍历* * * 0------ 返回* * *********************************** * 请选择菜单号（0--3）： */ #include 第8章 图 8-1 画出1个顶点、2个顶点、3个顶点、4个顶点和5个顶点的无向完全图。试证明在n 个顶点的无向完全图中，边的条数为n(n-1)/2。 【解答】 【证明】 在有n 个顶点的无向完全图中，每一个顶点都有一条边与其它某一顶点相连，所以每一个顶点有 n-1条边与其他n-1个顶点相连，总计n 个顶点有n(n-1)条边。但在无向图中，顶点i 到顶点j 与顶点j 到顶点i 是同一条边，所以总共有n(n-1)/2条边。 8-2 右边的有向图是强连通的吗？请列出所有的简单路径。 【解答】 点，它不是强连通的有向图。各个顶点自成强连通分量。 所谓简单路径是指该路径上没有重复的顶点。 从顶点A 出发，到其他的各个顶点的简单路径有A →B ，A →D →B ，A →B →C ，A →D →B →C ，A →D ，A →B →E ，A →D →E ，A →D →B →E ，A →B →C →F →E ，A →D →B →C →F →E ，A →B →C →F ，A 1个顶点的 无向完全图 2个顶点的 无向完全图 3个顶点的 无向完全图 4个顶点的 无向完全图 5个顶点的 无向完全图 A D ????????? ?????? ?????=01 00000001001010000 010*********Edge →D →B →C →F 。 从顶点B 出发，到其他各个顶点的简单路径有B →C ，B →C →F ，B →E ，B →C →F →E 。 从顶点C 出发，到其他各个顶点的简单路径有C →F ，C →F →E 。 从顶点D 出发，到其他各个顶点的简单路径有D →B ，D →B →C ，D →B →C →F ，D →E ，D →B →E ，D →B →C →F →E 。 从顶点E 出发，到其他各个顶点的简单路径无。 从顶点F 出发，到其他各个顶点的简单路径有F →E 。 8-3 给出右图的邻接矩阵、邻接表和邻接多重表表示。 【解答】 (1) 邻接矩阵 A D 数据与结构知识点总结 数据结构概述 定义 我们如何把现实中大量而复杂的问题以特定的数据类型（比如：结构体等）和特定 的存储结构（比如：数组，链表等）保存到主存储器（内存）中，以及在此基础上 为实现某个功能（比如：查找某个元素，删除某个元素，对所有元素进行排序）而 执行的相应操作，这个相应的操作也叫算法。 数据结构= 个体+ 个体的关系 算法= 对存储数据的操作 理解：如果数据都无法保存的话，如何对数据进行操作呢？这时候数据的存储是一个很关键的问题，那么我们就要通过特定的数据类型和特定的存储 结构保存到内存中。那么问题来了： 问题1：保存一个省的人事之间的关系就不能用链表或数组来实现， 因为那样不能得知哪个是老大老二，谁是领导和属下，所以 它无法体现，那么怎么办呢？ ——利用用树来实现，做一个人事管理系统 问题2：如果是个交通图，开辟很多站点，那么我要在各站点间修路 每个站点相同，或者说给出两个站点，系统能给出两站点间 最短路径，那又该怎么办呢？ ——利用图来实现，使各个点之间相关联 发现：把一个实际的问题如何保存在计算机里面，这是第一步要解决的问题。如果数据都不能保存，那还怎么对它操作呢？ 那么该如何保存呢？ 保存个体（特定的数据类型）； 保存个体和个体之间的关系（特定的存储结构）。 算法：解题的方法和步骤 衡量算法的标准（前2条最关键） 1、时间复杂度：大概程序要执行的次数，而非执行的时间 2、空间复杂度：算法执行过程中大概所占用的最大内存 3、难易程度 4、健壮性：不能出现当给一个非法的数整个程序就挂了 数据结构的地位： 数据结构是软件中最核心的课程，几乎所有的编程语言都能找到数据结构的影子 程序= 数据的存储+ 数据的操作+ 可被计算机执行的语言 课程总结(提要) 一、数据结构和抽象数据类型ADT 定义：一个数学模型以及定义在该模型上的一组操作。 构成一个抽象数据类型的三个要素是： 数据对象、数据关系、基本操作 数据结构(非数值计算程序设计问题中的数学模型) ·逻辑结构（描述数据元素之间的关系） 线性结构——线性表、栈、队列、串、数组、广义表 非线性结构——树和森林、二叉树、图 集合结构——查找表、文件 ·存储结构（逻辑结构在存储器中的映象） 按“关系”的表示方法不同而分： 顺序结构—以数据元素在存储器中的一个固定的相对位置来表示“关系” 链式结构—以指针表示数据元素的“后继”或“前驱” ·基本操作(三类) 结构的建立和销毁 查找——引用型操作（不改变元素间的关系） 按“关系”进行检索 按给定值进行检索 遍历——访问结构中的每一个数据元素，且对每个元素只访问一次修改——加工型操作（改变元素间的关系） 插入 删除 更新（删除+插入） 二、线性结构 ·线性表和有序表 ——不同存储结构的比较 顺序表：可以实现随机存取；O(1) 插入和删除时需要移动元素；O(n) 需要预分配存储空间; 适用于“不常进行修改操作、表中元素相对稳定”的场合。 链表：只能进行顺序存取；O(n) 插入和删除时只需修改指针; O(1) 不需要预分配存储空间; 适用于“修改操作频繁、事先无法估计最大表长”的场合。 ——应用问题的算法时间复杂度的比较 例如，以线性表表示集合进行运算的时间复杂度为O(n2), 而以有序表表示集合进行运算的时间复杂度为O(n) ·栈和队列——数据类型的特点及其应用范畴 ·串——和线性表的差异： 数据对象不同（数据元素限定为单个字符）、基本操作集不同（串整体作为操作对象）、存储结构不同 ??串的模式匹配算法 ·数组——只有引用型的操作，∴只需要顺序存储结构 多维到一维的不同映象方法： 以行序为主序（低下标优先） 以列序为主序（高下标优先） ·广义表——多层次的线性结构 特性：次序性、长度、层次性、深度、递归等 独有的特性：共享 存储结构的特点 数据结构（C语言版）（第2版） 课后习题答案 李冬梅 目录 第1章绪论...................................................................................... 错误!未定义书签。第2章线性表 .................................................................................. 错误!未定义书签。第3章栈和队列 .............................................................................. 错误!未定义书签。第4章串、数组和广义表 ............................................................... 错误!未定义书签。第5章树和二叉树 .......................................................................... 错误!未定义书签。第6章图 ........................................................................................... 错误!未定义书签。第7章查找...................................................................................... 错误!未定义书签。第8章排序...................................................................................... 错误!未定义书签。 #include 实验六图的应用及其实现 （相关知识点：拓扑排序、关键路径、最小生成树和最短路径） 一、实验目的 1．进一步功固图常用的存储结构。 2．熟练掌握在图的邻接表实现图的基本操作。 3．理解掌握AOV网、AOE网在邻接表上的实现以及解决简单的应用问题。 二、实验内容 一>.基础题目：(本类题目属于验证性的，要求学生独立完成) [题目一]：从键盘上输入AOV网的顶点和有向边的信息,建立其邻接表存储结构,然后对该图拓扑排序,并输出拓扑序列. 试设计程序实现上述AOV网的类型定义和基本操作,完成上述功能。 测试数据：教材图7.28 [题目二]：从键盘上输入AOE网的顶点和有向边的信息,建立其邻接表存储结构,输出其关键路径和关键路径长度。试设计程序实现上述AOE网类型定义和基本操作,完成上述功能。 测试数据：教材图7.29 二>.简单应用题目：（ACM/ICPC训练题，本类题目属于设计性的，要求学生三人为一个团队，分工协作完成)） 【题目三】高速公路 描述 某国共有n个城市（n不超过200），有些城市之间直接有一条高速公路相连，高速公路都是双向的，总共有m条。每条高速公路都有自己的载重限制，即载重最大值。通过车辆的载重不能超过公路的载重限制。如今我们想了解的是，从某一起点城市出发，到达目标城市，车辆最多能带多重的货物。 输入 输入的第一行为两个整数n和m。以下有m行，每行三个整数描述一条公路，分别是首尾相连的城市以及载重限制。然后是一个整数k，即问题个数。接下来k行描述k个问题，每行两个整数表示起点城市和目标城市。问题数不超过一百。 输出 输出包括k行，每行对应一个问题，输出从起点到目标的最大载重量。如果两城市间无路径则输出-1。 样例输入 3 3 1 2 100 2 3 100 1 3 50 2 1 3 2 3 样例输出 100 100 【题目四】最短的旅程 描述 在Byteland有n个城市（编号从1到n），它们之间通过双向的道路相连。Byteland 的国王并不大方，所以，那里只有n -1条道路，但是，它们的连接方式使得从任意城市都可以走到其他的任何城市。 一天，starhder到了编号为k的城市。他计划从城市k开始，游遍城市m1，m2，m3……，mj（不一定要按这个顺序旅游）。每个城市mi都是不同的，并且，也与k不同。Starhder ——就像每一个旅行家一样，携带的钱总是有限的，所以，他要以最短的路程旅行完所有的城市（从城市k开始）。于是，他请你帮助计算一下，旅游完上述的城市最短需要多少路程。 输入 数据结构教案第七章图 第7章图 【学习目标】 1．领会图的类型定义。 2．熟悉图的各种存储结构及其构造算法，了解各种存储结构的特点及其选用原则。 3．熟练掌握图的两种遍历算法。 4．理解各种图的应用问题的算法。 【重点和难点】 图的应用极为广泛，而且图的各种应用问题的算法都比较经典，因此本章重点在于理解各种图的算法及其应用场合。 【知识点】 图的类型定义、图的存储表示、图的深度优先搜索遍历和图的广度优先搜索遍历、无向网的最小生成树、最短路径、拓扑排序、关键路径 【学习指南】 离散数学中的图论是专门研究图性质的一个数学分支，但图论注重研究图的纯数学性质，而数据结构中对图的讨论则侧重于在计算机中如何表示图以及如何实现图的操作和应用等。图是较线性表和树更为复杂的数据结构，因此和线性表、树不同，虽然在遍历图的同时可以对顶点或弧进行各种操作，但更多图的应用问题如求最小生成树和最短路径等在图论的研究中都早已有了特定算法，在本章中主要是介绍它们在计算机中的具体实现。这些算法乍一看都比较难，应多对照具体图例的存储结构进行学习。而图遍历的两种搜索路径和树遍历的两种搜索路径极为相似，应将两者的算法对照学习以便提高学习的效益。 【课前思考】 1. 你有没有发现现在的十字路口的交通灯已从过去的一对改为三对，即每个方向的直行、左拐和右拐能否通行都有相应的交通灯指明。你能否对某个丁字路口的6条通路画出和第一章绪论中介绍的"五叉路口交通管理示意图"相类似的图？ 2. 如果每次让三条路同时通行，那么从图看出哪些路可以同时通行？ 同时可通行的路为：(AB,BC,CA),(AB,BC,BA),(AB,AC,CA),(CB,CA,BC) 数据结构知识点总结 绪论 时间复杂度T（n）=O（f（n）） 通常用：常量阶O(1)线性阶O(n)平方阶O(n^2)对数阶O(logn)指数阶O(2^n)计算的复杂性：算法的计算量的大小 算法的时间复杂度取决于问题的规模和待处理数据的初态。 算法：是对特定问题求解步骤的一种描述，它是指令的有限序列。 （1）有穷性（2）确定性（3）可行性（4）输入（5）输出 从逻辑上可以把数据结构分为线性结构和非线性结构 栈与数据的存储结构无关 串是线性结构 有序表属于逻辑结构 连续存储设计时，存储单元的地址一定连续 一、数据：是对客观事物的符号表示，在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。它是计算机程序加工的“原料”。 二、数据元素：是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。一个数据元素可由若干个数据项组成。数据项是数据的不可分割的最小单位。 三、数据对象：是性质相同的数据元素的集合，是数据的一个子集。 四、数据机构：是相互之间存在一种或多种特定关系的数据元素的集合。在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为结构。根据数据元素之间关系的不同特性，通常有下 列4类基本结构：（1）集合------------数据元素仅有同属一个关系的关系（2）线性结构----------结构中数据元素之间存在一个对一个的关系（3）树形结构------------结构中的数据元素之间存在一个对多个的关系（4）图状结构或网状结构-----------结构中的数据元素之间存在多个对多个的关系 五、元素在存贮结构（1）物理结构（存储结构）：它包括数据元素的表示和关系。（2）逻辑结构 六、位bit：在计算机中表示信息的最小单位是二进制的一位 七、元素element/节点node：位串 八、数据域：当数据元素由若干数据项组成时，位串中对应于各个数据项的子位串 九、数据元素之间的关系在计算机中有两种不同的表示方法，顺序映像和非顺序映像，并由此得到两种不同的存储结构：顺序存储结构（借助元素在存储器中的相对位置来表示数据元素之间的逻辑关系）和链式存储结构（借助指示元素存储地址的指针表示数据元素之间的逻辑关系）。 算法：是对特定问题求解步骤的一种描述，它是指令的有限序列。 （1）有穷性（2）确定性（3）可行性（4）输入（5）输出 算法设计要求：（1）正确性（2）可读性（3）健壮性（4）效率与低存储量需求 ------------------------------------------------------------------------------- 线性表：采用顺序存储，便于进行插入和删除的操作 顺序表的优点：结构紧凑，存储空间利用率高，操作简单。（存储密度大）缺点：它需要一块连续的存贮空间。 数据结构图的存储结构及基本操作 1.实验目的 通过上机实验进一步掌握图的存储结构及基本操作的实现。 2.实验内容与要求 要求： ⑴能根据输入的顶点、边/弧的信息建立图； ⑵实现图中顶点、边/弧的插入、删除； ⑶实现对该图的深度优先遍历； ⑷实现对该图的广度优先遍历。 备注：单号基于邻接矩阵，双号基于邻接表存储结构实现上述操作。 3.数据结构设计 逻辑结构：图状结构 存储结构：顺序存储结构、链式存储结构 4.算法设计 #include }ArcNode; typedef struct VNode { char data[2]; //顶点就设置和书上V1等等一样吧 ArcNode *firstarc; }VNode,AdjList[MAX _VERTEX_NUM]; typedef struct { AdjList vertices; int vexnum,arcnum; }ALGraph; typedef struct { int data[MAX_VERTEX_ NUM+10]; int front; int rear; }queue; int visited[MAX_VERTE X_NUM]; queue q; int main() { ALGraph G; int CreateUDG(ALGraph &G); int DeleteUDG(ALGraph &G); int InsertUDG(ALGraph &G); void BFSTraverse(ALGrap h G, int (*Visit)(ALGraph 数据库的体系结构Revised on November 25, 2020 数据库的体系结构 1.三级模式结构 数据库的体系结构分为三级：外部级、概念级和内部级（图），这个结构称为数据库的体系结构，有时亦称为三级模式结构或数据抽象的三个级别。虽然现在DBMS的产品多种多样，在不同的操作系统下工作，但大多数系统在总的体系结构上都具有三级结构的特征。 从某个角度看到的数据特性，称为数据视图(Data View)。 外部级最接近用户，是单个用户所能看到的数据特性，单个用户使用的数据视图的描述称为外模式。概念级涉及到所有用户的数据定义，也就是全局性的数据视图，全局数据视图的描述称概念模式。内部级最接近于物理存储设备，涉及到物理数据存储的结构，物理存储数据视图的描述称为内模式。 图三级模式结构 数据库的三级模式结构是对数据的三个抽象级别。它把数据的具体组织留给DBMS去做，用户只要抽象地处理数据，而不必关心数据在计算机中的表示和存储，这样就减轻了用户使用系统的负担。 三级结构之间往往差别很大，为了实现这三个抽象级别的联系和转换，DBMS在三级结构之间提供两个层次的映象(Mapping)：外模式／模式映象，模式／内模式映象。这里的模式是概念模式的简称。 数据库的三级模式结构，即数据库系统的体系结构如图所示。 图数据库系统的体系结构 2.三级结构和两级映象 （1）概念模式 概念模式是数据库中全部数据的整体逻辑结构的描述。它由若干个概念记录类型组成，还包含记录间联系、数据的完整性安全性等要求。 数据按外模式的描述提供给用户，按内模式的描述存储在磁盘中，而概念模式提供了连接这两级的相对稳定的中间点，并使得两级中任何一级的改变都不受另一级的牵制。概念模式必须不涉及到存储结构、访问技术等细节，只有这样，概念模式才能达到物理数据独立性。概念模式简称为模式。 （2）外模式 外模式是用户与数据库系统的接口，是用户用到的那部分数据的描述。外模式由若干个外部记录类型组成。 用户使用数据操纵语言(DML)语句对数据库进行操作，实际上是对外模式的外部记录进行操作。有了外模式后，程序员不必关心概念模式，只与外模式发生联系，按照外模式的结构存储和操纵数据。 （3）内模式 内模式是数据库在物理存储方面的描述，定义所有内部记录类型、索引和文件的组织方式，以及数据控制方面的细节。 （4）模式／内模式映象 模式／内模式映象存在于概念级和内部级之间，用于定义概念模式和内模式之间的对应性。由于这两级的数据结构可能不一致，即记录类型、字段类型的命名和组成可能不—样，因此需要这个映象说明概念记录和内部记录之间的对应性。 模式／内模式映象一般是放在内模式中描述的。 一、实验目的和要求 （1）掌握图的相关概念，包括图，有向图，无向图，完全图，子图，连通图，度，入度，出度，简单回路和环等定义。 （2）重点掌握图的各种存储结构，包括邻接矩阵和邻接表等。 （3）重点掌握图的基本运算，包括创建图，输出图，深度优先遍历，广度优先遍历等。 （4）掌握图的其他运算 ，包括最小生成树，最短路径，拓扑排序和关键路径等算法。 （5）灵活运用图这种数据结构解决一些综合应用问题。 二、实验内容和方法 (1)实验内容： 1、编写一个程序algo8-1.cpp ，实现不带权图和带权图的邻接矩阵与邻接表的相互转换算法、输出邻接矩阵与邻接表的算法，并在此基础上设计一个程序exp8-1.cpp 实现如下功能： ①建立如图1所示的有向图G 的邻接矩阵，并输出； ②由有向图G 的邻接矩阵产生邻接表，并输出； ③再由②的邻接表产生对应的邻接矩阵，并输出。 图1 2、编写一个程序algo8-2.cpp ，实现图的遍历运算，并在此基础上设计一个程序exp8-2.cpp 完成如下功能： ①输出图1所示的有向图G 从顶点0开始的深度优先遍历序列（递归算法）； ②输出图1所示的有向图G 从顶点0开始的深度优先遍历序列（非递归算法）； ③输出图1所示的有向图G 从顶点0开始的广度优先遍历序列。 3、设计一个程序exp8-3.cpp,采用邻接表存储图，并输出图8.1（a ）中从指定顶点1出发的所有深度优先遍历序列。 1 5 6 9 7 5 8 4 5 3 0 1 5 2 4 3 (2)实验方法： 1、综合运用课本所学的知识，用不同的算法实现在不同的程序功能。 2、结合指导老师的指导，解决程序中的问题，正确解决实际中存在的异常情况，逐步改善功能。 3、根据实验内容，编译程序。 三、实验环境： Windows 7，Visual C++6.0 三、实验过程描述 文件graph.h中定义了图的邻接矩阵表示类型和邻接表表示类型，该头文件在以下三个实验中都会使用到。其代码如下： #ifndef GRAPH_H_INCLUDED #define GRAPH_H_INCLUDED typedef int InfoType; #define MAXV 100 //最大顶点个数 #define INF 32767 //INF表示无限大 //以下定义邻接矩阵类型 typedef struct { int no; InfoType info; }VertexType; typedef struct { int edges[MAXV][MAXV]; int n,e; VertexType vexs[MAXV]; }MGraph; //以下定义邻接表类型 typedef struct ANode { int adjvex; struct ANode* nextarc; InfoType info; }ArcNode; typedef int Vertex; typedef struct VNode { Vertex data; 1. O(1)、O(log 2n)、O(n)、O(nlog 2n)、O(n 2) O(n 3)、O(n k )、O(2n )。 2. 在顺序表中第i 个位置插入一个结点的移动次数为n-i+1，插入平均移动n/2次， 删除顺序表第i 个结点移动次数为n-i ，平均移动(n-1)/2次。 3. 定义变量p=(LinkList)malloc(sizeof(ListNode))或p=(LinkNode*)malloc(sizeof(ListNode)) 4. 单循环链表判断空：head= =head->next 5. 共享向量空间判断满top1=top2-1 6. 入队EnQueue ，出队DeQueue ，front=rear 空队列，循环队列克服假上溢 7. 循环队列判断队满(rear+1)%m=front ，循环队列指针移动方向顺时针。 8. 链队列判空：Q->front=Q->rear=NULL 9. 求串长strlen ，串复制strcpy(to,from)，联接strcat(to,from)，串比较strcmp(s1大就大于s1小就小于， 小写字母>大写字母)，字符定位strchr 10. 串的子串定位（模式匹配）下标从0开始，最坏情况下时间复杂度比较次数O((n-m+1)m) 11. 二维数组下标为0公式：行优先LOC(a 00)+[i*n+j]*d ，列优先LOC(a 00)+[j*m+i]*d 12. 三维数组下标为0公式：三维数组A mnp 按行优先LOC(a ijk )=LOC(a 000)+[i*n*p+j*p+k]*d 13. 对称矩阵一共有n(n+1)/2个元素，存储位置k=I*(I+1)/2+J(I=max(i,j),J=min(i,j))下标0开始 14. 上三角矩阵：k=i*(2n-i+1)+j-i ，下三角矩阵：k=i*(i+1)/2+j 。上三角i>j 下三角i数据结构实验总结报告
数据结构图习题
数据结构--图重点
数据结构总结
数据结构试题二及答案(详细)
数据结构：图子系统
数据结构-图习题
数据结构的总结
数据结构课程总结
数据结构(C语言版)(第2版)课后习题答案
数据结构无向图
数据结构--图的应用及其实现
(完整版)数据结构详细教案——图
数据结构知识点总结
数据结构图的存储结构及
数据库的体系结构
数据结构图实验报告汇总
数据结构(公式及重点汇总)