文档库 最新最全的文档下载
当前位置:文档库 › 数据结构2

数据结构2

数据结构2

2.1 试编写一个算法,将一个顺序表逆置,并使用最少的辅助存储空间实现。

2.2 试编写一个算法,将两个元素值递减排列的顺序表合并为一个非递增的顺序表。

2.3 试编写一个算法,计算带头结点的循环单链表的长度。

2.4 试编写一个算法,在一个递增有序排列的单链表中插入一个新结点x,并保持有序。

2.5 试编写一个算法,将一个单链表逆置。

2.6 试编写一个算法,在一个双向循环链表中将结点x插入到指定结点p之前。

2.7 试编写一个算法,计算一个循环队列中包含的元素个数。

2.8 试编写一个算法,实现对一个以只带尾指针的循环单链表表示的队列的入队出队操作。

数据结构-数据结构历年考题及答案2

中国矿业大学2011-2012学年 《数据结构》试卷(A卷)(考试时间:100分钟) 一. 填空(每空2分,共40分) 1. 数据结构式具有相同性质的数据元素的(1)。 2. 通常程序在调用另一个程序时,都需要使用一个(2)来保存被调用程序内分配的局部变量、形式参数的存储空间以及返回地址。 3. 有6行8列的二维数组A,每个元素用相邻的6个字节存储,存储器按字节编址,已知A的起始存储地址(基址)为1000,在行优先存储和列优先存贮情况下A[5,5]的存储地址分别为__(3)_____,_____(4)____。 4. 完全二叉树第4 个节点的父节点是第 (5) 节点,左孩子是第 (6) 个节点。如果该二叉树有10层,则共有 (7) 个节点。 5. 请描述在循环队列Q中,队头和队尾指针分别由front和rear表示,该队列有10个存储空间,判断队空和队满的条件分别分:_____(8)________,_______(9)_________。 6. 字符串t=”child”,s=”cake”,请写出下列函数的结果:StrLength(t) =(10)__;Concat(SubString(s,3,1),SubString(t,2,2))=____(11)___。 7. 一棵二叉树为 则后序序列为(12),中序序列为(13),先序序列为__(14)____。 8. 请用数据序列{53,17,12,66,58,70,87,25,56,60 }构造一棵二叉排序树_(15)_。 9.。一个栈输入的序列式1,2,3,则可能的且以2为开头的输出序列是 (16) ,不可能的序列是____(17)____。 10. 有n个结点的无向完全图的边数分别为_______(18)_______。 11. 要从数据:2,3,4,8,9,11,13查找11,若采用折半查找法,则在(19)次比较后,才找到该数据。 12. 在直接插入排序、希尔排序、冒泡排序和快速排序中,平均情况下(20)_____最快。 二简答题: 1给定{15,3,14,2,6,9,16,17},试为这8个数设计哈夫曼编码,并计算其带权路径长度。 2请对下图的无向带权图按克鲁斯卡尔算法求其最小生成树。(要求使用图画出每一步过程)。 C G E D F B H A

数据结构课后习题答案

第1章绪论 1.简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案: 数据:是客观事物的符号表示,指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数,文本编辑所用到的字符串,多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素:是数据的基本单位,在计算机中通常作为一个整体进行考虑和处理。在有些情况下,数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象,如一个学生记录,树中棋盘的一个格局(状态)、图中的一个顶点等。 数据项:是组成数据元素的、有独立含义的、不可分割的最小单位。例如,学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象:是性质相同的数据元素的集合,是数据的一个子集。例如:整数数据对象是集合N={0,±1,±2,…},字母字符数据对象是集合C={‘A’,‘B’,…,‘Z’,‘a’,‘b’,…,‘z’},学生基本信息表也可是一个数据对象。 数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。换句话说,数据结构是带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。 逻辑结构:从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。因此,数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构:数据对象在计算机中的存储表示,也称为物理结构。 抽象数据类型:由用户定义的,表示应用问题的数学模型,以及定义在这个模型上的一组操作的总称。具体包括三部分:数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2.试举一个数据结构的例子,叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案: 例如有一张学生基本信息表,包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素,学生记录按顺序号排列,形成了学生基本信息记录的线性序列。对于整个表来说,只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录),其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构,即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录,则称为顺序存储结构;如果存储单元不连续,而是随机存放各个记录,然后用指针进行链接,则称为链式存储结构。 即相同的逻辑结构,可以对应不同的存储结构。 3.简述逻辑结构的四种基本关系并画出它们的关系图。

数据结构试卷及答案2套

数据结构试卷1 一、单项选择题:(每小题2分,共20分) 1. 在一个长度为n的顺序表中顺序搜索一个值为x的元素时,在等概率的情况下,搜索成功时的数据平均比较次数为________。 A. n B. n/2 C.(n+1)/2 D.(n-1)/2 2. 不带头结点的单链表first为空的判定条件是_________。 A. first->next == NULL; B. first == NULL; C. first->next == first; D. first != NULL; 3. 栈的插入和删除操作在__________进行。 A. 栈顶 B. 栈底 C. 任意位置 D. 指定位置 4. 假定一个链式队列的队头和队尾指针分别为front和rear,则判断队空的条件为__________。 A. front==rear B. front!=NULL C. rear!=NULL D. front==NULL 5. 设有一个广义表A ( (x, (a, b) ), (x, (a, b), y) ),运算Head (Head (Tail (A) ) ) 的执行结果为________。 A.y B.(a, b) C.(x,(a,b)) D.x 6. 在一棵具有n个结点的二叉树中,所有结点的空子树个数等于_________。 A. n B. n-1 C. n+1 D. 2*n 7. 利用n个值作为叶结点的权重,生成的霍夫曼树中共包含有_________个结点。 A. n B. n+1 C. 2*n D. 2*n-1 8. 设无向图的顶点个数为n,则该图最多有________条边。 A. n-1 B. n(n-1)/2 C. n(n+1)/2 D. n(n-1) 9. 任何一个无向连通图的最小生成树_________。 A.只有一棵 B. 一棵或多棵 C. 一定有多棵 D. 可能不存在 10. 从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较,然后将其放在已排序序列的合适位置,该排序方法称为_______排序法。 A.选择B.二路归并C.交换 D.插入 二、填空题(每空1分,共20分) 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的____________以及它们之间的___________和运算等的学科。 2. 顺序表中逻辑上相邻的元素的物理位置________相邻。单链表中逻辑上相邻的元素的物理位置__________相邻。 3. 在单链表中,除了首元结点外,任一结点的存储位置由___________________ 指示。 4. ________ 是被限定为只能在表的一端进行插入运算,在表的另一端进行删除运算的线性

严蔚敏版数据结构课后习题答案-完整版

第1章绪论 1.1 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解:数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合,是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解:抽象数据类型包含一般数据类型的概念,但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义,直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据

类型通常由编程者定义,包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时,要求只定义到数据的逻辑结构和操作说明,不考虑数据的存储结构和操作的具体实现,这样抽象层次更高,更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R),其中 {}4,3,2,1d d d d D =,{}r R =,()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解: 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。 解: ADT Complex{ 数据对象:D={r,i|r,i 为实数} 数据关系:R={} 基本操作: InitComplex(&C,re,im) 操作结果:构造一个复数C ,其实部和虚部分别为re 和im DestroyCmoplex(&C)

数据结构图习题

第七章图:习题 习题 一、选择题 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. 有向图,有向边,弧,弧头,弧尾,权值 b. 无向图,无向边(v, w),权值 2.顶点集(Vertices ):a. 无向图:度(TD(v)) b. 有向图:出度(ID(v)),入度(OD(v)),度(TD(v) = ID(v) + OD(v)) 无向完全图:n 个顶点,(1)2 n n -条边 有向完全图:n 个顶点,(1)n n -条边 网:带权图 连通分量:无向图中的极大连通子图(多个),无向完全图的连通分量就是本身(一个) 强连通分量:有向图中的极大连通子图,其中i v 到j v 以及j v 到i v 都有路径 生成树:图的极小连通子图,含有图的全部n 个顶点,只有n-1条边,少一条则不能连通, 多一条则形成回路 生成森林:不完全图中的各个连通分量的生成树,构成图的生成森林 二、存储结构 顶点:可采用链表或数组存储顶点列表,一般采用链表存储 边:1. 邻接矩阵(数组) a. 无向图:对称阵,可采用矩阵压缩存储方式。A[i][j] = 0表示i v 和j v 没有连接; A[i][j] = 1表示i v 和j v 有边连接;第i 行的和表示顶点i v 的度 b. 有向图:不对称阵。,[][]i j A i j w =表示顶点i v 到j v 的有向弧的权值;[][]A i j =∞ 表示表示顶点i v 到j v 没有弧连接或者i = j 2. 邻接表(链表,有向无向都可用) 边结点:adjvex (邻接点),nextarc (下一条边),info (权值) 顶点结点:data (顶点数据),firstarc (第一条边) 3. 十字链表(Othogonal List ) 弧结点:tailvex (弧尾结点),headvex (弧头结点),tlink (弧尾相同的下一条弧),hlink (弧头相同的下一条弧),info (权值) 顶点结点:data (顶点数据),firstin (第一条入弧),firstout (第一条出弧) 三、图的遍历(每个顶点只被访问一次) 1. 深度优先遍历(类似树的先根遍历) 基本思想:假设初始状态是图中所有顶点未曾被访问,则深度优先搜索可从图中某个顶 点v 出发,访问此结点,然后依次从v 的未被访问的邻接点出发深度优先遍 历图,直至图中所有和v 有路径相通的顶点都被访问到;若此时图中尚有顶 点未被访问(非连通图),则另选图中一个未曾被访问的顶点作起始点,重 复上述过程,直至图中所有顶点都被访问到为止。

经典数据结构面试题(含答案)

.栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中,增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是__________________________ 13.树是结点的集合,它的根结点数目是_____________________ 14.在深度为5的满二叉树中,叶子结点的个数为_______________ 15.具有3个结点的二叉树有(_____________________ 16.设一棵二叉树中有3个叶子结点,有8个度为1的结点,则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh,中序遍历访问顺序是dgbaechf,则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为:安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中,算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________

数据结构试题二及答案(详细)

吉首大学试题库 一、一、单选题(每题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.组成数据的基本单位是() (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.算法的五个重要特性是_______、_______、______、_______、_______。 7.数据结构的三要素是指______、_______和________。 8.链式存储结构与顺序存储结构相比较,主要优点是________________________________。 9.设有一批数据元素,为了最快的存储某元素,数据结构宜用_________结构,为了方便插入一个元素,数据结构宜用____________结构。 四、算法分析题 1.求下列算法段的语句频度及时间复杂度参考答案: 选择题1. C 2.C 3. C 4. A、B 5. C 6.C、B

数据结构:图子系统

/* *题目:编写按键盘输入的数据建立图的邻接矩阵存储 * 编写图的深度优先遍历程序 * 编写图的广度优先遍历程序 * 设计一个选择式菜单形式如下: * 图子系统 * *********************************** * * 1------更新邻接矩阵* * * 2------深度优先遍历* * * 3------广度优先遍历* * * 0------ 返回* * *********************************** * 请选择菜单号(0--3): */ #include #include #define GRAPHMAX 30 #define QUEUEMAX 30 typedef struct //图的邻接表的结构体 { char value[GRAPHMAX]; //记录图中的点值 int data[GRAPHMAX][GRAPHMAX]; //记录图中的边的关系int n, e; //记录图中的点的个数及边的个数 }pGraph; typedef struct //队列结构体 { int queueData[QUEUEMAX]; int front, rear, count; //队头,队尾,数目 }grQueue; void createCraph(pGraph *G); void DFSTraverse(pGraph *G); void BFSTraverse(pGraph *G); void DFS(pGraph *G, int i); void BFS(pGraph *G, int i); void initQueue(grQueue *Q); int queueEmpty(grQueue *Q); int queueFull(grQueue *Q); int outQueue(grQueue *Q); void inQueue(grQueue *Q, int i);

数据结构-图习题

第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

经典数据结构面试题(含答案)

栈和队列的共同特点是__________________________ .栈通常采用的两种存储结构是______________________ .用链表表示线性表的优点是_______________________ 8.在单链表中,增加头结点的目的是___________________ 9.循环链表的主要优点是________________________- 12.线性表的顺序存储结构和线性表的链式存储结构分别是 __________________________ 13.树是结点的集合,它的根结点数目是_____________________ 14.在深度为5的满二叉树中,叶子结点的个数为_______________ 15.具有3个结点的二叉树有(_____________________ 16.设一棵二叉树中有3个叶子结点,有8个度为1的结点,则该二叉树中总的结点数为____________________ 17.已知二叉树后序遍历序列是dabec,中序遍历序列是debac,它的前序遍历序列是 ____________________________ 18.已知一棵二叉树前序遍历和中序遍历分别为ABDEGCFH和DBGEACHF,则该二叉树的后序遍历为______________________ 19.若某二叉树的前序遍历访问顺序是abdgcefh,中序遍历访问顺序是dgbaechf,则其后序遍历的结点访问顺序是_______________________ 20.数据库保护分为:安全性控制、完整性控制、并发性控制和数据的恢复。 在计算机中,算法是指_______________________ 算法一般都可以用哪几种控制结构组合而成_____________________ .算法的时间复杂度是指______________________ 5. 算法的空间复杂度是指__________________________ 6. 算法分析的目的是__________________________

数据结构期末试题2及答案

B 卷 一、单项选择题 1、若结点的存储地址与其关键字之间存在某种映射关系,则称这种存储结构为( )。 A. 顺序存储结构 B. 链式存储结构 C. 索引存储结构 D. 散列存储结构 2、在长度为n的顺序表的第i(1≤i≤n+1)位置上插入一个元素,元素的移动次数( )。 A. n-i+1 B. n-I C. i D. i-1 3、对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为( )。 A. 顺序表 B.用头指针表示的单循环链表 C. 用尾指针表示的单循环链表 D. 单链表 4、若进栈序列为a,b,c,则通过入出栈操作可能得到的a,b,c的不同排列个数为( )。 A. 4 B. 5 C. 6 D. 7 5、为查找某一特定单词在文本中的出现的位置,可应用的串运算是( )。 A. 插入 B. 删除 C. 串联接 D. 子串定位 6、已知函数sub(s,i,j)的功能功能是返回串s中的从第i个字符起长度为j的子串,函数scopy(s,1)的功能为复制串t到s。若字符串S=”SCIENCESTUDY“,则调用函数scopy(P,sub(S,1,7)))后得到 A. P=”SCIENCE” B. P=“STUDY” C. S=”SCIENGE” D. S=”STUDY” 7、三维数组A[4][5][6]按行优先存储在内存中,若每个元素占2个存储

单元,且数组中第一个元素的存储地址为120,则元素A[3][4][5]的存储地址为( )。 A. 356 B. 358 C. 360 D. 362 8、如右图所示广义表是一种()。 A. 线性表 B. 纯表 C. 结点共享表 D. 递归表 9、下列陈述中正确的是( )。 A. 二叉树是度为2的有序树 B. 二叉树中结点只有一个孩子时无左右之分 C. 二叉树中必有度为2的结点 D. 二叉树中最多只有两棵子树,并且有若右之分 10、n个顶点的有向完全图中含有有有向边的数目最多为 ( ) A. n-1 B. n C. n(n-1)/2 D. n(n-1) 11、已知一个有向图如下所示,则从顶点a出发进行深度优先遍历,不可能得到的DFS序列为( )。 A. a d b e f c B. a d c e f b C. a d c b f e D. a d e f c b 12、在最好和最坏情况下的时间复杂度均为O(nlogn)且稳定的排序方法是( )。 A. 快速排序 B. 堆排序 C. 归并排序 D. 基数排序 13、不可能生成右图所示二叉排序树的关键字的序列是( )。

数据结构(C语言版)(第2版)课后习题答案

数据结构(C语言版)(第2版) 课后习题答案 李冬梅

目录 第1章绪论...................................................................................... 错误!未定义书签。第2章线性表 .................................................................................. 错误!未定义书签。第3章栈和队列 .............................................................................. 错误!未定义书签。第4章串、数组和广义表 ............................................................... 错误!未定义书签。第5章树和二叉树 .......................................................................... 错误!未定义书签。第6章图 ........................................................................................... 错误!未定义书签。第7章查找...................................................................................... 错误!未定义书签。第8章排序...................................................................................... 错误!未定义书签。

数据结构无向图

#include #include #define INFINITY 100000 //最大值∞ #define MAX_VERTEX_NUM 20 //最大顶点个数 typedef struct mygraph{ char vexs[MAX_VERTEX_NUM]; //顶点向量 int arcs[MAX_VERTEX_NUM][MAX_VERTEX_NUM]; //邻接矩阵 int vexnum, arcnum; //图的当前顶点和弧数 }MGraph; typedef struct myedge{ int adjvex; int endvex; int lowcost; } closedge[MAX_VERTEX_NUM]; void CreateUDN(MGraph &G) ; //创建无向网络 int LocateVex(MGraph G, char v); //结点的在顶点向量中的下标 void PrintUDN(MGraph G); //输出存储结构示意图 void MiniSpanTree_PRIM(MGraph G,closedge &minedge);//求最小生成树的算法void PrintMinEdge(MGraph G,closedge minedge); //输出最小生成树的边 int main() { MGraph G;//定义一个图的变量 closedge minedge; CreateUDN(G); printf("该图的邻接矩阵存储示意图如下:\n"); PrintUDN(G); printf("\n"); MiniSpanTree_PRIM(G,minedge); printf("该图生成树的边如下:\n"); PrintMinEdge(G,minedge); printf("\n"); return 0; } void CreateUDN(MGraph &G) { int i,j,k,m; char v1,v2; char ch;

数据结构第2版习题答案—严蔚敏

)。 第2章线性表 1 .选择题 (1)顺序表中 第一个 元素的存储 地址是100,每个元素的 长度为2,则第5个元素的 地址是( )。 A . 110 答案: B 解释:顺序表中的数据连续存储,所以第 D . 120 5个元素的地址为: 100+2*4=108。 (3)向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移 动的元 素个数为( )。 C . 63 A . 8 B . 答案:B 解释:平均要移动的元素个数为: (4) 链接存储的存储结构所占存储空间( n/2。 )。 A .分两部分,一部分存放结点值,另一部分存放表示结点间关系的指针 B .只有一部分,存放结点值 C .只有一部分,存储表示结点间关系的指针 D .分两部分,一部分存放结点值,另一部分存放结点所占单元数 答案:A (5) 线性表若采用链式存储结构时,要求内存中可用存储单元的地址( A .必须是连续的 C . 一定是不连续的 答案:D (6) 线性表1在( B ?部分地址必须是连续的 D ?连续或不连续都可以 )情况下适用于使用链式结构实现。 B.需不断对L 进行删除插入 D.L 中结点结构复杂 A .需经常修改L 中的结点值 C . L 中含有大量的结点 答案:B 解释:链表最大的优点在于插入和删除时不需要移动数据,直接修改指针即可。 (7) 单链表的存储密度( )。 A .大于1 B .等于1 答案:C 解释:存储密度是指一个结点数据本身所占的存储空间和整个结点所占的存储空 间之比,假设单链表一个结点本身所占的空间为 D ,指针域所占的空间为 N ,则存储密 度为:D/(D+N),—定小于 1。 (8) 将两个各有 n 个元素的有序表归并成一个有序表,其最少的比较次数是( C ?小于1 D ?不能确定 B . 2n-1 C . 2n D . n-1 C . 100

数据结构--图的应用及其实现

实验六图的应用及其实现 (相关知识点:拓扑排序、关键路径、最小生成树和最短路径) 一、实验目的 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开始)。于是,他请你帮助计算一下,旅游完上述的城市最短需要多少路程。 输入

数据结构课后习题详解(超完整,超经典)

第1章 绪论 1.1 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解:数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合,是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解:抽象数据类型包含一般数据类型的概念,但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义,直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据类型通常由编程者定义,包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时,要求只定义到数据的逻辑结构和操作说明,不考虑数据的存储结构和操作的具体实现,这样抽象层次更高,更能为其他用户提供良好的使用接口。 1.3 设有数据结构(D,R),其中 {}4,3,2,1d d d d D =,{}r R =,()()(){}4,3,3,2,2,1d d d d d d r = 试按图论中图的画法惯例画出其逻辑结构图。 解: 1.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。 解: ADT Complex{ 数据对象:D={r,i|r,i 为实数} 数据关系:R={} 基本操作: InitComplex(&C,re,im) 操作结果:构造一个复数C ,其实部和虚部分别为re 和im DestroyCmoplex(&C) 操作结果:销毁复数C Get(C,k,&e) 操作结果:用e 返回复数C 的第k 元的值 Put(&C,k,e) 操作结果:改变复数C 的第k 元的值为e IsAscending(C) 操作结果:如果复数C 的两个元素按升序排列,则返回1,否则返回0

数据结构试题2(含答案)

期末样卷参考答案 一.是非题(每题2分共20分) 1. 线性表的链式存储结构优于顺序存储结构。F 2. 栈和队列也是线性表。如果需要,可对它们中的任一元素进行操作。F 3.字符串是数据对象特定的线性表。T 4.在单链表P指针所指结点之后插入S结点的操作是:P->next= S ; S-> next = P->next; F 5.一个无向图的连通分量是其极大的连通子图。T 6.邻接表可以表示有向图,也可以表示无向图。T 7.假设B是一棵树,B′是对应的二叉树。则B的后根遍历相当于B′的中序遍历。 T 8.通常,二叉树的第i层上有2i-1个结点。F 9.对于一棵m阶的B-树,树中每个结点至多有m 个关键字。除根之外的所有非终端 结点至少有┌m/2┐个关键字。F 10.对于任何待排序序列来说,快速排序均快于起泡排序。F 二.选择题(每题2分共28分) 1.在下列排序方法中,(c)方法平均时间复杂度为0(nlogn),最坏情况下时间复杂度为0(n2);(d)方法所有情况下时间复杂度均为0(nlogn)。 a. 插入排序 b. 希尔排序 c. 快速排序 d. 堆排序 2. 在有n个结点的二叉树的二叉链表表示中,空指针数为(b)。 a.不定 b.n+1 c.n d.n-1 3. 下列二叉树中,(a)可用于实现符号不等长高效编码。 a.最优二叉树 b.次优查找树 c.二叉平衡树 ?? d.二叉排序树 4. 下列查找方法中,(a)适用于查找有序单链表。 a.顺序查找 b.二分查找 c.分块查找 d.哈希查找 5. 在顺序表查找中,为避免查找过程中每一步都检测整个表是否查找完毕,可采用 (a)方法。 a.设置监视哨 b.链表存贮 c.二分查找 d.快速查找 6. 在下列数据结构中,(c)具有先进先出特性,(b)具有先进后出特性。 a.线性表 b.栈 c.队列 d.广义表 7.具有m个结点的二叉排序树,其最大深度为(f),最小深度为(b)。 a. log 2 m b. └ log2 m ┘ +1 c. m/2 d .┌ m/2 ┐ -1 e. ┌ m/2 ┐ f. m 8.已知一组待排序的记录关键字初始排列如下:56,34,58,26,79,52,64,37,28,84,57。 下列选择中(c)是快速排序一趟排序的结果。 (b)是希尔排序(初始步长为4)一趟排序的结果。 (d)是基数排序一趟排序的结果。 (a)是初始堆(大堆顶)。 a)84,79,64,37,57,52,58,26,28,34,56。 b)28,34,57,26,56,52,58,37,79,84,64。 c)28,34,37,26,52,56,64,79,58,84,57。 d)52,34,64,84,56,26,37,57,58,28,79。

相关文档