一.填空题
1. _集合__、线性结构、__树形结构____ 、图形结构
2.p->next!=NULL
3.时间复杂度和空间复杂度
4.随机存取
5..队尾
6. n-1
二、单选题、
1-5DAACC 6-10DBDDB 11-15DCABD
三，简答题
1、
2、数据是对客观事物的描述形式和编码形式的统称，是算法和程序的处理对象和计算结构。数据元素又称数据结点，简称结点，通常一个数据结点由用来描述一个独立事的名称、数量、特性、性质的一组相关信息。多数情况下，一个结点包含有多个数据项，每个数据项是结点的一个域，能够用来唯一标识结点的域称为关键字域。
算法：有穷规则的集合，而规则规定了解决某一特定问题的运算序列。
有穷性：必须在执行有穷步后终止。
确定性：每一步必须具有确定的定义，不能含糊不清，不带二义性。
可行性：所有运算都可以精确地实现。
输出数据：必须有输出数据，包括输出某种动作或控制信号。
输入数据：作为执行前的初始量。不是必须。
算法有两种表现形式：描述形式和程序形式。
计算时间复杂的的方法：
?支配性语句度量法：在一段程序中，往往有一条语句执行次数最多，话费时间也就是最多，其他语句执行次数的和将不超过这套语句执行次数的常数倍，那么就称这条语句在话费时间上是起支配性作用的典型语句，于是可选这条语句的执行次数作为度量这段程序花费时间的阶。
?
四、应用题
1、
2、、对给定的n个权值bai{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中du每棵二叉树Ti中只有一个权值zhi为Wi的根结点，
它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的
升序排列。）二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。三、从F中删除这
两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。四、重复二和三两步，直到集合F中只有一棵二叉树为止。
树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL
WPL=∑Wi*Li (i=1到n)
WPL=(2+4)*3+(6+8+10)*2
=66
第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。 2. 算法的时间复杂度取决于（） 3.计算机算法指的是（），它必须具备（）这三个特性。 4．一个算法应该是（）。 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]对换； 其中 n为正整数，则最后一行的语句频度在最坏情况下是（） A. O（n） B. O(nlogn) C. O(n3) D. O(n2) 13．以下哪个数据结构不是多型数据类型（） A．栈 B．广义表 C．有向图 D．字符串 14．以下数据结构中，（）是非线性数据结构 A．树 B．字符串 C．队 D．栈 15. 下列数据中，（）是非线性数据结构。 A．栈 B. 队列 C. 完全二叉树 D. 堆 16．连续存储设计时，存储单元的地址（）。 A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续17．以下属于逻辑结构的是（）。 A．顺序表 B. 哈希表 C.有序表 D. 单链表 二、判断题
数据结构试卷 一、单项选择题（本大题 共15小题，每小题2分，共30分） 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1 . 下列选项中与数据存储结构无关的术语是（） A.顺序表 B.链表 C. 链队列 D.栈 2 . 将两个各有n个元素的有序表归并成一个有序表，最少的比较次数是（） A.n-1 B.n C.2n-1 D.2n 3 . 已知循环队列的存储空间大小为m，队头指针front指向队头元素，队尾指针rear 指向 队尾元素的下一个位置，则向队列中插入新元素时，修改指针的操作是（） A.rear=(rear-1)%m; B.front=(front+1)%m; C.front=(front-1)%m; D.rear=(rear+1)%m; 4 . 递归实现或函数调用时，处理参数及返回地址，应采用的数据结构是（） A.堆栈 B.多维数组 C. 队列 D. 线性表 5 . 设有两个串p和q，其中q是p的子串，则求q在p中首次出现位置的算法称为（）A.求子串 B.串联接 C.串匹配D.求串长 6 . 对于广义表A，若head(A)等于tail(A)，则表A为（） A.() B.(()) C.((),()) D.((),(), ()) 7.若一棵具有n(n>0)个结点的二叉树的先序序列与后序序列正好相反，则该二叉树一 定是（） A.结点均无左孩子的二叉树 B.结点均无右孩子的二叉树 C.高度为n的二叉树 D.存在度为2的结点的二叉树 8.若一棵二叉树中度 为l的结点个数是3，度为2 的结点个数是4，则该二叉树叶子结点的个数是（） A.4 B.5 C.7 D.8 9. 某算法有3 个程序段，第一程序段的执行次数为错误！未找到引用源。，第二个程序段执 行次数为4n，第三个程序段的执行次数 为0.06错误！未找到引用源。，则该算法的时间复 杂度为（）。 A．O（n）B ．O（错误！未找到引用源。） C ．O（错误！未找到引用源。）D．O （错误！未找到引用源。） 10.已知有向图G=(V，E)，其中V={V1，V2，V3，V4}，E={
数据结构复习资料 一、填空题 1. 数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。 2. 数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有限集合。 3. 数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。 4. 数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。 6．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。 7. 在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。 8. 在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。 9．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。 10. 数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。 11. 一个算法的效率可分为时间效率和空间效率。 12. 在顺序表中插入或删除一个元素，需要平均移动表中一半元素，具体移动的元素个数与表长和该元素在表中的位置有关。 13. 线性表中结点的集合是有限的，结点间的关系是一对一的。 14. 向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时，需向后移动n-i+1 个元素。 15. 向一个长度为n的向量中删除第i个元素(1≤i≤n)时，需向前移动n-i 个元素。 16. 在顺序表中访问任意一结点的时间复杂度均为O(1)，因此，顺序表也称为随机存取的数据结构。 17. 顺序表中逻辑上相邻的元素的物理位置必定相邻。单链表中逻辑上相邻的元素的物理位置不一定相邻。 18．在单链表中，除了首元结点外，任一结点的存储位置由其直接前驱结点的链域的值指示。 19．在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。 20. 向量、栈和队列都是线性结构，可以在向量的任何位置插入和删除元素；对于栈只能在栈顶插入和删除元素；对于队列只能在队尾插入和队首删除元素。
单项选择 （ B ） 1. 通常所说的主机是指∶ A) CPU B) CPU和内存C) CPU、内存与外存D) CPU、内存与硬盘 （ C ）2. 在计算机内部，一切信息的存取、处理和传送的形式是∶ A) ACSII码B) BCD码C)二进制D)十六进制 （ D ）3. 软件与程序的区别是∶ A)程序价格便宜、软件价格昂贵； B)程序是用户自己编写的，而软件是由厂家提供的； C) 程序是用高级语言编写的，而软件是由机器语言编写的； D) 软件是程序以及开发、使用和维护所需要的所有文档的总称，而程序只是软件的一部分。 （ C ）4. 所谓“裸机”是指∶ A) 单片机B)单板机C) 不装备任何软件的计算机D) 只装备操作系统的计算机 （ D ）5. 应用软件是指∶ A)所有能够使用的软件B) 能被各应用单位共同使用的某种软件 C)所有微机上都应使用的基本软件D) 专门为某一应用目的而编制的软件 （A）6. C语言中的常量可分为整型常量、实型常量、字符型常量及(枚举)四种。 （A）符号常量（B）长整型常量（C）逻辑常量（D）二进制整数 （ C ）7. 编译程序的功能是∶ A)发现源程序中的语法错误B)改正源程序中的语法错误 C)将源程序编译成目标程序D)将某一高级语言程序翻译成另一种高级语言程序 （A）8. 系统软件中最重要的是∶ A) 操作系统B) 语言处理系统C) 工具软件D) 数据库管理系统 （ C ）9. 可移植性最好的计算机语言是∶ A) 机器语言B)汇编语言C) 高级语言D) 自然语言
（ B ）10. 非线性结构是数据元素之间存在一种： A）一对多关系B）多对多关系C）多对一关系D）一对一关系 （ C ）11. 数据结构中，与所使用的计算机无关的是数据的结构； A) 存储B) 物理C) 逻辑D) 物理和存储 （ C ）12. 算法分析的目的是： A) 找出数据结构的合理性B) 研究算法中的输入和输出的关系 C) 分析算法的效率以求改进D) 分析算法的易懂性和文档性 （A）13. 算法分析的两个主要方面是： A) 空间复杂性和时间复杂性B) 正确性和简明性 C) 可读性和文档性D) 数据复杂性和程序复杂性 （ C ）14. 计算机算法指的是： A) 计算方法B) 排序方法C) 解决问题的有限运算序列D) 调度方法 （ B ）15. 计算机算法必须具备输入、输出和等5个特性。 A) 可行性、可移植性和可扩充性B) 可行性、确定性和有穷性 C) 确定性、有穷性和稳定性D) 易读性、稳定性和安全性 （ C ）16．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为： （A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构 （ B ）17.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 （A）110 （B）108 （C）100 （D）120 （A）18. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：（A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） （B）在第i个结点后插入一个新结点（1≤i≤n） （C）删除第i个结点（1≤i≤n） （D）将n个结点从小到大排序 （ B ）19. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动个元素 （A）8 （B）63.5 （C）63 （D）7 （A）20. 链接存储的存储结构所占存储空间： （A）分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针
一.填空题 1. _集合__、线性结构、__树形结构____ 、图形结构 2.p->next!=NULL 3.时间复杂度和空间复杂度 4.随机存取 5..队尾 6. n-1 二、单选题、 1-5DAACC 6-10DBDDB 11-15DCABD 三，简答题 1、
2、数据是对客观事物的描述形式和编码形式的统称，是算法和程序的处理对象和计算结构。数据元素又称数据结点，简称结点，通常一个数据结点由用来描述一个独立事的名称、数量、特性、性质的一组相关信息。多数情况下，一个结点包含有多个数据项，每个数据项是结点的一个域，能够用来唯一标识结点的域称为关键字域。 算法：有穷规则的集合，而规则规定了解决某一特定问题的运算序列。 有穷性：必须在执行有穷步后终止。 确定性：每一步必须具有确定的定义，不能含糊不清，不带二义性。 可行性：所有运算都可以精确地实现。 输出数据：必须有输出数据，包括输出某种动作或控制信号。 输入数据：作为执行前的初始量。不是必须。 算法有两种表现形式：描述形式和程序形式。 计算时间复杂的的方法： ?支配性语句度量法：在一段程序中，往往有一条语句执行次数最多，话费时间也就是最多，其他语句执行次数的和将不超过这套语句执行次数的常数倍，那么就称这条语句在话费时间上是起支配性作用的典型语句，于是可选这条语句的执行次数作为度量这段程序花费时间的阶。 ? 四、应用题
1、 2、、对给定的n个权值bai{W1,W2,W3,...,Wi,...,Wn}构成n棵二叉树的初始集合F= {T1,T2,T3,...,Ti,...,Tn}，其中du每棵二叉树Ti中只有一个权值zhi为Wi的根结点， 它的左右子树均为空。（为方便在计算机上实现算法，一般还要求以Ti的权值Wi的 升序排列。）二、在F中选取两棵根结点权值最小的树作为新构造的二叉树的左右子树，新二叉树的根结点的权值为其左右子树的根结点的权值之和。三、从F中删除这 两棵树，并把这棵新的二叉树同样以升序排列加入到集合F中。四、重复二和三两步，直到集合F中只有一棵二叉树为止。 树的带权路径长度规定为所有叶子结点的带权路径长度之和，记为WPL WPL=∑Wi*Li (i=1到n) WPL=(2+4)*3+(6+8+10)*2 =66
第一章 1、数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和操作等的学科。 数据结构(Data Structure)：相互之间存在一种或多种特定关系的数据元素的集合。 2、数据结构的形式定义：二元组Data_Structure=(D,S) 其中，D 是数据元素的有限集，S 是D 上关系的有限集。 3、数据元素之间关系的映像：１、顺序映像(顺序存储结构)：以相对的存储位置表示后继关系。 2、非顺序映像(链式存储结构)：借助指针元素存储地址的指针表示数据元素之间的逻辑关系。 任何一个算法的设计取决于数据(逻辑)结构，其实现取决于物理结构。 4、 算法的定义：对特定问题求解步骤的一种描述，它是指令的有限序列，其中每一条指令表示一个或多个操作。 特性：有穷性、确定性、可行性、输入、输出 5、 算法的评价——衡量算法优劣的标准 正确性(correctness):满足具体问题的需求 可读性(readability)：易读、易理解 健壮性(robustness):当输入数据非法时，算法能够做出反应或进行处理 效率与低存储量:执行时间短、存储空间小 作业的答案：试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 第二章 1、线性表是一种最简单的线性结构。 线性结构 是一个数据元素的有序（次序）关系 特点：存在唯一的一个“第一个”的数据元素；存在唯一的一个“最后一个”的数据元素；除第一个数据元素外，均有唯一的前驱；除最后一个数据元素外，均有唯一的后继 2、线性表类型的实现——顺序映像 定义：用一组地址连续的存储单元依次存放线性表中的数据元素。 ? 以“存储位置相邻”表示有序对
习题练习第一章绪论 1、void maxtrixmult (int n,int a[][100],int b[][100],intc[][100]) { int j,k,r; int x; for(r=0;r<=n;r++) 1) n+2 { for (j=0;j<=n;j++) 2) (n+1)*(n+2) { x=0; 3) (n+1)2 for(k=1；k<=n;k++) 4) (n+1)3 x+=a[r][k]*[k][j]; 5) n* (n+1)2 c[r][j]=x; 6) (n+1)2 } } } 计算时间每条语句的频度和该算法的时间复杂度 2．一个算法应该是（ B ）。【中山大学 1998 二、1（2分）】 A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 4．从逻辑上可以把数据结构分为（ C ）两大类。【武汉交通科技大学 1996 一、4（2分）】 A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 5．以下与数据的存储结构无关的术语是（ D ）。【北方交通大学 2000 二、1 （2分）】 A．循环队列 B. 链表 C. 哈希表 D. 栈 6．连续存储设计时，存储单元的地址（ A ）。【中山大学 1999 一、1（1分）】A．一定连续 B．一定不连续 C．不一定连续 D．部分连续，部分不连续 7. 数据元素是数据的最小单位。( F ) 【北京邮电大学 1998 一、1（2分）】【青岛大学 2000 一、1 （1分）】 【上海交通大学 1998 一、1】【山东师范大学 2001 一、1 （2分）】 第二章线性表 1．线性表是具有n个（ C ）的有限序列（n>0）。【清华大学 1998 一、 4（2分）】 A．表元素 B．字符 C．数据元素 D．数据项 E．信 息项
数据结构试卷（一） 一、单选题（每题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条件进行划分，使得同一余数的元 素成为一个子表，则得到的四个子表分别为____________________________、___________________、_______________________和__________________________。
1.1 请说明算法具有哪些特性，各是什么含义？ 算法的一般性质包括：（1）通用性对于那些符合输入类型的任意输入数据,都能根据算法进行问题求解,包保证计算结构的正确性.（2）有效性组成算法的每一条指令都必须是能够被人或机器确切执行的.（3）确定性算法每执行一步之后,对于它的下一步,应该有明确的指示.即,保证每一步之后都有关于下一步动作的指令,不能缺乏下一步指令或仅仅含有模糊不清的指令.（4）有穷性算法的执行必须在有限步内结束. 1.2简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类 型和抽象数据类型。 数据：指所有能够输入到计算机中并被计算机程序处理的符号集合。数据元素（data element）：数据集合中的一个实体，是计算机程序中加工处理的基本单位。例如：一条学生记录（包括学号、姓名、年龄等）就是一个数据元素数据对象（data object）：性质相同的数据元素的集合。是数据的一个子集。数据结构(data structure)：相互之间存在一种或多种关系的数据元素的集合。即包括数据元素的集合和数据元素之间的关系的集合。存储结构：数据结构在计算机中的表示（也称映像）叫做物理结构。又称为存储结构。数据类型（data type）:是一个“值”的集合和定义在此集合上的“一组操作”的总称。抽象数据类型（abstract data type，简称ADT）：是指一个数学模型以及定义在此数学模型上的一组操作。1.3设n为正整数。试确定下列各程序段中前置以记号@的语句频度： (1) x=n; y=0; //n为不小于1的常数 while (x>=(y+1)*(y+1)) { @ y++; } n1/2向下取整 (2) i=1; j=0; while (i+j<=n) { @ if (i>j) j++; else i++; } n 注：@语句指的是if…else语句，语句频度为j++和i++执行的次数之和。 1.4请说明下列算法的时间复杂度。 (1) void sf1 (int n) { int i, x=0; for(i=1; i Problem A : Hardwood Species From:POJ, 2418 Description Hardwoods are the botanical group of trees that have broad leaves, produce a fruit or nut, and generally go dormant in the winter. America's temperate climates produce forests with hundreds of hardwood species -- trees that share certain biological characteristics. Although oak, maple and cherry all are types of hardwood trees, for example, they are different species. Together, all the hardwood species represent 40 percent of the trees in the United States. On the other hand, softwoods, or conifers, from the Latin word meaning "cone-bearing," have needles. Widely available US softwoods include cedar, fir, hemlock, pine, redwood, spruce and cypress. In a home, the softwoods are used primarily as structural lumber such as 2x4s and 2x6s, with some limited decorative applications. Using satellite imaging technology, the Department of Natural Resources has compiled an inventory of every tree standing on a particular day. You are to compute the total fraction of the tree population represented by each species. Input Input to your program consists of a list of the species of every tree observed by the satellite; one tree per line. No species name exceeds 30 characters. There are no more than 10,000 species and no more than 1,000,000 trees. Output Print the name of each species represented in the population, in alphabetical order, followed by the percentage of the population it represents, to 4 decimal places. Sample Input Red Alder Ash Aspen Basswood Ash Beech Yellow Birch Ash Cherry Cottonwood 一、简答题 1、链表：链表就是一串存储数据的链式结构。链式的优点在于，每个数据之间都是相 关联的。 2、线性结构： 线性结构是一个有序数据元素的集合。常用的线性结构有：线性表，栈，队列，双队列，数组，串。 3、树与二叉树 二叉树是每个结点最多有两个子树的有序树； 树是由n（n>=1）个有限节点组成一个具有层次关系的集合。 树和二叉树的2个主要差别： 1. 树中结点的最大度数没有限制，而二叉树结点的最大度数为2； 2. 树的结点无左、右之分，而二叉树的结点有左、右之分。 4、堆 堆通常是一个可以被看做一棵树的数组对象。堆总是满足下列性质： 堆中某个节点的值总是不大于或不小于其父节点的值； 堆总是一棵完全二叉树。 5、二叉排序树 二叉排序数的（递归）定义：1、若左子树非空，则左子树所有节点的值均小于它的根节点；2、若右子树非空，则右子树所有节点的值均大于于它的根节点；3、左右子树也分别为二叉排序树。 二、应用题 1、树与二叉树 ①前中后序遍历序列 一、已知前序、中序遍历，求后序遍历 例：前序遍历: GDAFEMHZ中序遍历: ADEFGHMZ 画树求法： 第一步，根据前序遍历的特点，我们知道根结点为G 第二步，观察中序遍历ADEFGHMZ。其中root节点G左侧的ADEF必然是root的左子树，G右侧的HMZ必然是root的右子树。 第三步，观察左子树ADEF，左子树的中的根节点必然是大树的root的leftchild。在前序遍历中，大树的root的leftchild位于root之后，所以左子树的根节点为D。 第四步，同样的道理，root的右子树节点HMZ中的根节点也可以通过前序遍历求得。在前序遍历中，一定是先把root和root的所有左子树节点遍历完之后才会遍历右子树，并且遍历的左子树的第一个节点就是左子树的根节点。 同理，遍历的右子树的第一个节点就是右子树的根节点。 ②树与二叉树的转换 树转换为二叉树： 单元练习1 一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳） （√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。 （√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（ㄨ）（3）数据元素是数据的最小单位。 （ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。 （ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。 （√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。 （√）（7）数据的存储结构是数据的逻辑结构的存储映像。 （√）（8）数据的物理结构是指数据在计算机内实际的存储形式。 （ㄨ）（9）数据的逻辑结构是依赖于计算机的。 （√）（10）算法是对解题方法和步骤的描述。 二．填空题 （1）数据有逻辑结构和存储结构两种结构。 （2）数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构。 （3）数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 （4）树形结构和图形结构合称为非线性结构。 （5）在树形结构中，除了树根结点以外，其余每个结点只有 1 个前趋结点。 （6）在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。 （7）数据的存储结构又叫物理结构。 （8）数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。 （9）线性结构中的元素之间存在一对一的关系。 （10）树形结构结构中的元素之间存在一对多的关系， （11）图形结构的元素之间存在多对多的关系。 （12）数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的内容。（13）数据结构被定义为(D，R)，其中D是数据的有限集合，R是D上的关系的有限集合。（14）算法是一个有穷指令的集合。 （15）算法效率的度量可以分为事先估算法和事后统计法。 （16）一个算法的时间复杂性是算法输入规模的函数。 （17）算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n的函数。（18）若一个算法中的语句频度之和为T（n）=6n+3nlog2n，则算法的时间复杂度为 O（nlog2n）。（19）若一个算法中的语句频度之和为T（n）=3n+nlog2n+n2，则算法的时间复杂度为 O（n2）。（20）数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象，以及它们之间的关系和运算的学科。 1．算法的效率可分为 时间 效率和空间效率。 2．向一个长度为n 的顺序表的第i 个数据元素（0≤i ≤n ）之前插入一个数据元素时，需向后移动 n-i+1 个数据元素。 3． 队列 是被限定为只能在表的一端进行插入操作，在表的另一端进行删除操作的线性表。 4．设字符串S=″I □AM □A □STUDENT ″（其中□表示空格字符），则S 的长度为____14_______。 5．一棵有n 个叶子的哈夫曼树的结点总数为 2n-1 个。 6．在树形结构中，没有后继的结点是 叶子 结点 7．含n 个顶点的无向连通图中至少含有 n-1 条边。 8．n 个顶点的无向图G 用邻接矩阵A ［n ］［n ］存储，其中第i 列的所有元素之和等于顶点V i 的__|n-i |__。 9．对一组整数{60，40，90，20，10 ，70，50，80}进行直接插入排序时，当把第4个整数20插入到有序表中时，为寻找插入位置需比较 5 次。 10．在数据存放无规律的线性表中进行查找的最佳方法是 顺序查找 。 1. 设循环队列的容量为 30（序号从0到29），现经过一系列的入队和出队操作后，有①front=11，rear=19 ②front=19，rear=11；问在这两种情况下，循环队列的长度各是多少？ ①19-11=8 ②30-(19-11)-1=21 2. 已知一棵二叉树如图所示，请写出先根序、中根序和后根序遍历序列。 3. 已知一个无向图的邻接表如下图所示，试写出从顶点0出发分别进行深度优先和广度优先搜索遍历得到的顶点序列。 4. 试写出一组键值（46，58，15，45，90，18，10，62）应用直接插入排序算法从小到大排序后各趟的结果。 第一趟：[46],58,15,45,90,18,10,62 先根序：ABDEGCF 中根序：DBEGAFC 后根序：DGEBFCA 0 2 1 4 3 5 6 深度优先：0361425 广度优先：0235614 数据结构1 1、 单项选择题（每小题2分，共20分） 在下列每小题的四个备选答案中选出一个正确的答案，并将其字母标号填入题目的括号内。 1.栈和队列都是（ C ）。 A.顺序存储的线性结构 B.链式存储的线性结构 C.限制存储点的线性结构 D.限制存储点的非线性结构 2.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p 之间插入s结点，则执行（ C ）。 A.s->next=p->next; p->next=s; B.p->next=s->next; s- >next=p; C.q->next=s;s->next=p; D.p->next=s; s->next=q; 3.稀疏矩阵一般的压缩存储方法有两种，即（ C ）。 A．二维数组和三维数组 B三元组和散列 C．三元组和十字链表 D散列和十字链表 4.对于下面的二叉树，按后序遍历所得的结点序列为（ D ）。 A． 1234567 B． 1245367 C． 4251637 D． 452673l 5.深度为5的二叉树至多有（ C ）个结点。 A. 16 B .32 C. 31 D.10 6.Huffman树的WPL 是指（ C ）。 A．除根以外所有结点的权值之和 B．所有结点权值之和 C．各叶子结点的带权路径长度之和 D．根结点的值 7.下列排序方法中，（ D ）的比较次数与记录的初始排列状态无关？A．直接插入排序 B．起泡排序 C．快速排序 D．直接选择排序8.若一棵二叉树具有10个度为2的结点，则该二叉树的度为0的结点个数是( B) A. 9 B．11 C．12 D．不确定 9.设输入序列为1,2,3,4,5，借助一个栈不可能得到的输出序列是( C )。 A.1,2,3,4,5 B.1,4,3,2,5 C.4，1,3,2,5 D.1,3,2,5,4 10.对下图，不能得到的拓扑序列是(D) A.l,2,3,4,5,6,7,8 B.1,5,2,6,3,7,4,8 C.1,2,5,6,3,4,7,8 D.1,2,3,4,8,7,6,5 2、 填空题（每空1分，共20分） 11.数据元素之间的 关系 称为结构，通常有如下四种基本结构：集合结构、 线性 结构、 树形 结构和 图形 结构。 12.具有n个结点的无向图中，有 n(n-1)/2 条边的无向图称为完全图；对于具有n个结点有向图，有 n(n-1) 条弧的有向图称为有向完全图。 13.循环队列用数组A[0..m-1]存放其元素值。已知其头尾指针分别是front和rear，则当前队列中的元素个数是 (rear-front+m)%m ，判断队空的条件是 front==rear 。 14.在二叉树的第i层上至多有2i-1 结点。 15.设有一个二维数组A[0..6,0..8]，A[0][0]存放位置为500，每个元素占2个字节，以行序为主序列，则A[4][5]在位置 582 。 模拟试题三 一、选择题 1．数据结构是研究数据的（）以及它们的相互关系。 (A)理想结构，物理结构 (B)理想结构，抽象结构 (C)物理结构，逻辑结构 (D) 抽象结构，逻辑结构 2．线性表采用链式存储时，其地址（） (A)必须是连续的 (B) 部分地址必须是连续的 (C) 一定是不连续的 (D) 连续与否均可以 3．串的逻辑结构与（）的逻辑结构不相同。 (A) 线形表 (B) 栈 (C) 队列 (D) 查找表（集合） 4．完成堆排序的全过程需要（）个记录大小的辅助空间。 (A)1 (B)n (C)n*㏒2n (D)└n*㏒2n┘ 5．若给定的关键字集合为{20,15,14,18,21,36,40,10}，一趟快速排序接束时，键值的排列为（） (A)10,15,14,18,20,36,40,21 (B)10,15,14,18,20,40,36,21 (C)10,15,14,20,18,40,36,21 (D)15,10,14,18,20,36,40,21 6．有一棵二叉树如下图，该树是（） (A)二叉平衡树 (B) 二叉排序树 (C) 堆的形状 (D) 以上都不是 7．对于含有个n顶点e条边的无向连通图，利用Prim算法生成最小代价生成树其时间复杂度为( )。 (A)O(log2n) (B)O(n*n) (C)O(n*e) (D)O(e*log2e) 8．n个顶点的强连通图至少有（）条边。 (A)n+ (B)n+1 (C)n-1 (D)n*(n-1) 9．设有100个元素，用二分法查找时，最大比较次数是（），最小比较次数是（）。 (A)25 (B)7 (C)10 (D)1 10在内部排序中，排序时不稳定的有（） (A)插入排序 (B)冒泡排序 (C)快速排序 (D)归并排序 二、填空题 1．具有64个结点的完全二叉树的深度为（）。 2．有向图G用邻接距阵A{1……n,1……n}存储，其第i列的所有元素等于顶点i的 （）。 3．设有一空栈，栈顶指针为1000H（十六进制），现有输入序列为1,2,3,4,5，经过 Push,Push,PoP,Push,Pop,Push,Push后，输出序列为（）。 *4．线索二叉树中某结点D，没有左孩子的主要条件（）。 *5．模式中”ababbabbab”的前缀函数为（）。 6．设图G的顶点数为n，边数为e，第i个顶点的度数为D(vi)，则e=( )（即边数与各顶点的度数之间的关系）。 7．按（）遍历二叉树，可以得到按递增的关键码序列，在图中所示的二叉树中，检索关键字85的过程中，需与85进行比较的关键字序列为（）。 8．下列算法实现二叉搜索树上的查找，请在空格处填上恰当的语句，完成上述功能。 bitreptr *bstsearch(t,k) 数据库的体系结构Revised on November 25, 2020 数据库的体系结构 1.三级模式结构 数据库的体系结构分为三级：外部级、概念级和内部级（图），这个结构称为数据库的体系结构，有时亦称为三级模式结构或数据抽象的三个级别。虽然现在DBMS的产品多种多样，在不同的操作系统下工作，但大多数系统在总的体系结构上都具有三级结构的特征。 从某个角度看到的数据特性，称为数据视图(Data View)。 外部级最接近用户，是单个用户所能看到的数据特性，单个用户使用的数据视图的描述称为外模式。概念级涉及到所有用户的数据定义，也就是全局性的数据视图，全局数据视图的描述称概念模式。内部级最接近于物理存储设备，涉及到物理数据存储的结构，物理存储数据视图的描述称为内模式。 图三级模式结构 数据库的三级模式结构是对数据的三个抽象级别。它把数据的具体组织留给DBMS去做，用户只要抽象地处理数据，而不必关心数据在计算机中的表示和存储，这样就减轻了用户使用系统的负担。 三级结构之间往往差别很大，为了实现这三个抽象级别的联系和转换，DBMS在三级结构之间提供两个层次的映象(Mapping)：外模式／模式映象，模式／内模式映象。这里的模式是概念模式的简称。 数据库的三级模式结构，即数据库系统的体系结构如图所示。 图数据库系统的体系结构 2.三级结构和两级映象 （1）概念模式 概念模式是数据库中全部数据的整体逻辑结构的描述。它由若干个概念记录类型组成，还包含记录间联系、数据的完整性安全性等要求。 数据按外模式的描述提供给用户，按内模式的描述存储在磁盘中，而概念模式提供了连接这两级的相对稳定的中间点，并使得两级中任何一级的改变都不受另一级的牵制。概念模式必须不涉及到存储结构、访问技术等细节，只有这样，概念模式才能达到物理数据独立性。概念模式简称为模式。 （2）外模式 外模式是用户与数据库系统的接口，是用户用到的那部分数据的描述。外模式由若干个外部记录类型组成。 用户使用数据操纵语言(DML)语句对数据库进行操作，实际上是对外模式的外部记录进行操作。有了外模式后，程序员不必关心概念模式，只与外模式发生联系，按照外模式的结构存储和操纵数据。 （3）内模式 内模式是数据库在物理存储方面的描述，定义所有内部记录类型、索引和文件的组织方式，以及数据控制方面的细节。 （4）模式／内模式映象 模式／内模式映象存在于概念级和内部级之间，用于定义概念模式和内模式之间的对应性。由于这两级的数据结构可能不一致，即记录类型、字段类型的命名和组成可能不—样，因此需要这个映象说明概念记录和内部记录之间的对应性。 模式／内模式映象一般是放在内模式中描述的。专题一 数据结构
数据结构复习资料(亲自整理)
数据结构单元1练习参考答案
数据结构复习资料1
数据结构1
1数据结构是研究数据的()以及它们的相互关系
数据库的体系结构
相关主题
文本预览