文档库 最新最全的文档下载
当前位置:文档库 › 数据结构应用题练习

数据结构应用题练习

数据结构应用题练习
数据结构应用题练习

1、假设一棵二叉树的层序序列是ABCDEFGHIJ 和中序序列是DBGEHJACIF,请画出该树。 21、有一个完全二叉树按层次顺序存放在一维数组中,如下所示:

请指出结点P 的父结点,左子女,右子女。 3、给出下列二叉树的先序序列。

4、已知二叉树的先序遍历序列为ABCDEFGH ,中序遍历序列为CBEDFAGH ,画出二叉树。

答案:二叉树形态

A

F

H

G

D

E

C

B

(2)设一棵二叉树的先序序列: A B D F C E G H ,中序序列: B F D A G E H C ①画出这棵二叉树。

②画出这棵二叉树的后序线索树。

③将这棵二叉树转换成对应的树(或森林)。

A

B

F

D (

C

E H

G

(1) (2)

1、已知一棵二叉树的前序序列为:A,B,D,G,J,E,H,C,F,I,K,L中序序列:D,J,G,B,E,H,

A,C,K,I,L,F。

i.写出该二叉树的后序序列;

ii.画出该二叉树;

iii.求该二叉树的高度(假定空树的高度为-1)和度为2、度为1、及度为0的结点个数。

该二叉树的后序序列为:J,G,D,H,E,B,K,L,I,F,C,A。

该二叉树的形式如图所示:

该二叉树高度为:5。

度为2的结点的个数为:3。

度为1的结点的个数为:5。

度为0的结点个数为:4。

5、试用权集合{12,4,5,6,1,2}构造哈夫曼树,并计算哈夫曼树的带权路径长度。

答案:

2

1

5

6

1118

73

4

12

30

WPL=12*1+(4+5+6)*3+(1+2)*4=12+45+12=69

6、已知权值集合为{5,7,2,3,6,9},要求给出哈夫曼树,并计算带权路径长度WPL 。

答案:(1)树形态:

3

2

5

5

1019

9

7

6

13

32

(2)带权

WPL=(6+7+9)*2+5*3+(2+3)*4=44+15+20=79

(3) 假设用于通信的电文仅由8个字母组成,字母在电文中出现的频率分别为0.07,0.19,0.02,0.06,0.32,0.03,0.21,0.10。

① 试为这8个字母设计赫夫曼编码。

② 试设计另一种由二进制表示的等长编码方案。 ③ 对于上述实例,比较两种方案的优缺点。 解:方案1;哈夫曼编码

先将概率放大100倍,以方便构造哈夫曼树。 w={7,19,2,6,32,3,21,10},按哈夫曼规则:【[(2,3),6], (7,10)】, ……19, 21, 32

(100)

(40) (60) 19 21 32 (28) () (11) 7 10 6 (5)

2 3

方案比较:

方案2的WPL=3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3

结论:哈夫曼编码优于等长二进制编码

2.应用题

(1)已知如图6.27所示的有向图,请给出:

①每个顶点的入度和出度;

②邻接矩阵;

③邻接表;

④逆邻接表。

图 6.27 有

2 AOE 网G 如下所示,求关键路径。(要求标明每个顶点的最早发生时间和最迟发生时间,并画出关键路径)

答案:(1)最早发生时间和最迟发生时间: (2)关键路径:

顶点v2v1v0vl ve v5

v4

v32308

662308

66

(2)已知如图6.28所示的无向网,请给出: ① 邻接矩阵; ② 邻接表; ③ 最小生成树

图 6.28 无

→ →

→ → → → → → → → → → → → → → → ^ → → → ^ → → → ^ → → → ^

(3)已知图的邻接矩阵如6.29所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

(2)根据prim 算法,求图G 从顶点1出发的最小生成树,要求表示出其每一步生成过程。(用图或者表的方式均可)。

?????

?????????????????∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞62466325546551356516 答案:(1)广度优先遍历序列:1; 2, 3, 4; 5; 6

(2)最小生成树(prim 算法)

???

??

??

???

????????????????∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞∞6456252363794567555553955434图 6.29 邻接矩

1. 对下面的有向图,从顶点V1开始进行遍

历,试画出遍历得到的DFS 生成森林和BFS 生成森林。

遍历得到的DFS 生成森林和BFS 生成森林如下图:

(5)设哈希表的地址范围为0~17,哈希函数为:H (key )=key%16。用线性探测法处理冲突,输入关键字序列:(10,24,32,17,31,30,46,47,40,63,49),构造哈希表,试回答下列问题:

① 画出哈希表的示意图;

② 若查找关键字63,需要依次与哪些关键字进行比较? ③ 若查找关键字60,需要依次与哪些关键字比较?

④ 假定每个关键字的查找概率相等,求查找成功时的平均查找长度。

查找63,首先要与H(63)=63%16=15号单元内容比较,即63 vs 31 ,no;

然后顺移,与46,47,32,17,63相比,一共比较了6次!

③查找60,首先要与H(60)=60%16=12号单元内容比较,但因为12

号单元为空

(应当有空标记),所以应当只比较这一次即可。

④对于黑色数据元素,各比较1次;共6次; 对红色元素则各不相同,要统计移位的位数。“63”需要6次,“49”需要3次,“40”需要2次,“46”需要3次,“47”需要3次, 所以ASL=1/11(6+2+3×3+6)=23/11

BFS 生成森林

设散列表的长度为m=13,散列函数为H(k)=k MOD m ,给定的关键码序列为19,14,23,1,68,20,84,27,55,11,13,7,试写出用线性探查法解决冲突时所构造的散列表。 答案:表形态:

012

111098765432113112384201927681141

1

1

3

1

1

4

1

2

1

553

73

(2)在一棵空的二叉排序树中依次插入关键字序列为12,7,17,11,16,2,13,9,21,4,请画出所得到的二叉排序树。

12

7 17

2 11 16 21 4 9 13

验算方法: 用中序遍历应得到排序结果: 2,4,7,9,11,12,13,16,17,21

(3)已知如下所示长度为12的表:(Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec )

① 试按表中元素的顺序依次插入一棵初始为空的二叉排序树,画出插入完成之后的二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。

② 若对表中元素先进行排序构成有序表,求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。

③ 按表中元素顺序构造一棵平衡二叉排序树,并求其在等概率的情况下查找成功的平均查找长度。 解:

⑦ 堆排序

第一步,形成初始大根堆(详细过程略),第二步做堆排序。

初始排序 不是大根堆 形成初始大根堆

交换1与10对象 从1到9重新形成堆

交换1与9对象 从1到8重新形成堆

交换1与8对象 从1到7重新形成堆

交换1与7对象 从1到6重新形成堆

交换1与6对象 从1到5重新形成堆

交换1与5对象 从1到4重新形成堆

交换1与4对象 从1到3重新形成堆

交换1与3对象 从1到2重新形成堆

交换1与2对象 得到结果

90、请画出下图中的极大连通子图。

91、对于如下图请画出其用prim 和kruskal 两种不同算法生成最小生成树的各条边的并入顺序。画出最小生成树。并写出广度优先和深度优先的结点遍历顺序。

92、什么是静态查找,什么时动态查找,什么叫平均查找长度。

93、用序列(46,88,45,39,70,58,101,10,66,34)建立一个二叉排序树,画出该树,并求在等概率情况下查找成功的平均查找长度。

94、已知一个线性表(38,25,74,63,

52,48),假定采用h(k)=k%7计算散列地址进行散列存储,若引用线性探测的开放地址法解决冲突,则在该散列表上进行检索的平均检索长度为多少,若利用连地址法处理冲突,则在该散列表上进行检索的平均查找长度为多少?设地址空间为9。请画出算列表。 96、已知长度为12的表:(Jan , Fed , Mar , Apr , May , Jun , Aug , Sep , Oct , Nov , Dec )按表中元素的顺序,依次插入一棵初始为空的二叉排序树,画出插完之后的二叉排序树,并求其在等概率情况下,查找成功的平均查找长度。

98、有散列函数为h(k)=k%11,如果用二次探测在散列的方式解决冲突,49应放入哪?

1 2 3 4 5 6 7 8 9 10 11 12 13 99、用增量序列{8、4、2、1}对下列关键字进行希尔排序,用图表示排序过程。

{56、37、59、41、98、47、94、50、63、52、42、54、60、72、86、90}100、有一组关键字{14,15,30,28,5,10},分别画出冒泡排序、快速排序过程的图示。

15

38

61

84

数据结构树练习题

数据结构-树练习题 一、选择题 1、二叉树的深度为k,则二叉树最多有( C )个结点。 A. 2k B. 2k-1 C. 2k-1 D. 2k-1 2、用顺序存储的方法,将完全二叉树中所有结点按层逐个从左到右的顺序存放在一维数组R[1..N]中,若结点R[i]有右孩子,则其右孩子是( B )。 A. R[2i-1] B. R[2i+1] C. R[2i] D. R[2/i] 3、设a,b为一棵二叉树上的两个结点,在中序遍历时,a在b前面的条件是( B )。 A. a在b的右方 B. a在b的左方 C. a是b的祖先 D. a是b的子孙 4、设一棵二叉树的中序遍历序列:badce,后序遍历序列:bdeca,则二叉树先序遍历序列为()。 A. adbce B. decab C. debac D. abcde 5、在一棵具有5层的满二叉树中结点总数为( A )。 A. 31 B. 32 C. 33 D. 16 6、由二叉树的前序和后序遍历序列( B )惟一确定这棵二叉树。 A. 能 B. 不能 7、某二叉树的中序序列为ABCDEFG,后序序列为BDCAFGE,则其左子树中结点数目为( C )。 A. 3 B. 2 C. 4 D. 5 8、若以{4,5,6,7,8}作为权值构造哈夫曼树,则该树的带权路径长度为( C )。 A. 67 B. 68 C. 69 D. 70 9、将一棵有100个结点的完全二叉树从根这一层开始,每一层上从左到右依次对结点进行编号,根结点的编号为1,则编号为49的结点的左孩子编号为(A )。 A. 98 B. 99 C. 50 D. 48 10、表达式a*(b+c)-d的后缀表达式是( B )。 A. abcd+- B. abc+*d- C. abc*+d- D. -+*abcd 11、对某二叉树进行先序遍历的结果为ABDEFC,中序遍历的结果为DBFEAC,则后序遍历的结果是( B )。 A. DBFEAC B. DFEBCA C. BDFECA D. BDEFAC 12、树最适合用来表示( C )。 A. 有序数据元素 B. 无序数据元素 C. 元素之间具有分支层次关系的数据 D. 元素之间无联系的数据 13、表达式A*(B+C)/(D-E+F)的后缀表达式是( C ) A. A*B+C/D-E+F B. AB*C+D/E-F+ C. ABC+*DE-F+/ D. ABCDED*+/-+ 14、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序()。 A. 不发生改变 B. 发生改变 C. 不能确定 D. 以上都不对 15、假定在一棵二叉树中,度为2的结点数为15,度为1的结点数为30,则叶子结点数为()个。 A. 15 B. 16 C. 17 D. 47 16、由权值为3,6,7,2,5的叶子结点生成一棵哈夫曼树,它的带权路径长度为()。 A. 51 B. 23 C. 53 D. 74

数据结构课程实验指导书

数据结构实验指导书 一、实验目的 《数据结构》是计算机学科一门重要的专业基础课程,也是计算机学科的一门核心课程。本课程较为系统地论述了软件设计中常用的数据结构以及相应的存储结构与实现算法,并做了相应的性能分析和比较,课程内容丰富,理论系统。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因,使得掌握这门课程具有较大的难度: 1)理论艰深,方法灵活,给学习带来困难; 2)内容丰富,涉及的知识较多,学习有一定的难度; 3)侧重于知识的实际应用,要求学生有较好的思维以及较强的分析和解决问题的能力,因而加大了学习的难度; 根据《数据结构》课程本身的特性,通过实验实践内容的训练,突出构造性思维训练的特征,目的是提高学生分析问题,组织数据及设计大型软件的能力。 课程上机实验的目的,不仅仅是验证教材和讲课的内容,检查自己所编的程序是否正确,课程安排的上机实验的目的可以概括为如下几个方面: (1)加深对课堂讲授内容的理解 实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常,实验题中的问题比平时的习题复杂得多,也更接近实际。实验着眼于原理与应用的结合点,使学生学会如何把书上学到的知识用于解决实际问题,培养软件工作所需要的动手能力;另一方面,能使书上的知识变" 活" ,起到深化理解和灵活掌握教学内容的目的。 不少学生在解答习题尤其是算法设计时,觉得无从下手。实验中的内容和教科书的内容是密切相关的,解决题目要求所需的各种技术大多可从教科书中找到,只不过其出

现的形式呈多样化,因此需要仔细体会,在反复实践的过程中才能掌握。 (2) 培养学生软件设计的综合能力 平时的练习较偏重于如何编写功能单一的" 小" 算法,而实验题是软件设计的综合训练,包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧,多人合作,以至一整套软件工作规范的训练和科学作风的培养。 通过实验使学生不仅能够深化理解教学内容,进一步提高灵活运用数据结构、算法和程序设计技术的能力,而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点,使学生学会如何把书本上和课堂上学到的知识用于解决实际问题,从而培养计算机软件工作所需要的动手能力。 (3) 熟悉程序开发环境,学习上机调试程序一个程序从编辑,编译,连接到运行,都要在一定的外部操作环境下才能进行。所谓" 环境" 就是所用的计算机系统硬件,软件条件,只有学会使用这些环境,才能进行 程序开发工作。通过上机实验,熟练地掌握程序的开发环境,为以后真正编写计算机程序解决实际问题打下基础。同时,在今后遇到其它开发环境时就会触类旁通,很快掌握新系统的使用。 完成程序的编写,决不意味着万事大吉。你认为万无一失的程序,实际上机运行时可能不断出现麻烦。如编译程序检测出一大堆语法错误。有时程序本身不存在语法错误,也能够顺利运行,但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误,只能靠自己的上机经验分析判断错误所在。程序的调试是一个技巧性很强的工作,尽快掌握程序调试方法是非常重要的。分析问题,选择算法,编好程序,只能说完成一半工作,另一半工作就是调试程序,运行程序并得到正确结果。 二、实验要求 常用的软件开发方法,是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高,但为了培养一个软件工作者所应具备的科学工作的方法和作风,也应遵循以下五个步骤来完成实验题目: 1) 问题分析和任务定义 在进行设计之前,首先应该充分地分析和理解问题,明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型,而是对所需完成的任务作出明确的回答。例如:输入数据的类型、值的范围以及输入的

数据结构练习题(含答案)

数据结构练习题(含答案)

数据结构练习题 习题1 绪论 1.1 单项选择题 1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的①、数据信息在计算机中的②以及一组相关的运算等的课程。 ① A.操作对象B.计算方法C.逻辑结构D.数据映象 ②A.存储结构B.关系C.运算D.算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=(D,R),其中D是①的有限集合,R是D上的②有限集合。 ① A.算法B.数据元素C.数据操作D.数据对象 ② A.操作B.映象C.存储D.关系 3. 在数据结构中,从逻辑上可以把数据结构分成。 A.动态结构和静态结构B.紧凑结构和非紧凑结构 C.线性结构和非线性结构D.内部结构和外部结构 4. 算法分析的目的是①,算法分析的两个主要方面是②。 ① A. 找出数据结构的合理性 B. 研究算法中的输 入和输出的关系 C. 分析算法的效率以求改进 D. 分析算法的易懂

性和文档性 ② A. 空间复杂性和时间复杂性 B. 正确性和简明性 C. 可读性和文档性 D. 数据复杂性和程序 复杂性 5. 计算机算法指的是①,它必具备输入、输出和②等五个特性。 ① A. 计算方法 B. 排序方法 C. 解决问题的有限运算序列 D. 调度方法 ② A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性 1.2 填空题(将正确的答案填在相应的空中) 1. 数据逻辑结构包括、和三种类型,树形结构和图形结构合称为。 2. 在线性结构中,第一个结点前驱结点,其余每个结点有且只有个前驱结点;最后一个结点后续结点,其余每个结点有且只有个后续结点。 3. 在树形结构中,树根结点没有结点,其余每个结点有且只有个直接前驱结点,叶子结点没有结点,其余每个结点的直接后续结点可以。 4. 在图形结构中,每个结点的前驱结点数和后续结点数可以。 5. 线性结构中元素之间存在关系,树形结构中元素之间存在关系,图形结构中元素之间存在关系。 6. 算法的五个重要特性是__ __ , __ __ , ___ _ ,

数据结构综合习题集(含答案)

数据结构习题集 一、选择题 1.数据结构中所定义的数据元素,是用于表示数据的。( C ) A.最小单位 B.最大单位 C.基本单位 D.不可分割的单位 2.从逻辑上可以把数据结构分为( C ) A.动态结构、静态结构 B.顺序结构、链式结构 C.线性结构、非线性结构 D.初等结构、构造型结构 3.当待排序序列中记录数较少或基本有序时,最适合的排序方法为(A) A.直接插入排序法 B.快速排序法 C.堆排序法 D.归并排序法 4.关于串的的叙述,不正确的是( B) A.串是字符的有限序列 B.空串是由空格构成的串 C.替换是串的一种重要运算 D.串既可以采用顺序存储,也可以采用链式存储 5.带表头结点链队列的队头和队尾指针分别为front和rear,则判断队空的条件为(A )A.front==rear B.front!=NULL C.rear!=NULL D.front==NULL 6.若构造一棵具有n个结点的二叉排序树,最坏的情况下其深度不会超过(B ) A.n/2 B.n C.(n+1)/2 D.n+1 7.将两个各有n个元素的有序表合并成一个有序表,其最少的比较次数为(A) A.n B.2n-1 C.2n D.n2 8.设顺序表有19个元素,第一个元素的地址为200,且每个元素占3个字节,则第14个元素的存储地址为(B ) A.236 B.239 C.242 D.245 9.一个栈的入栈序列是a,b,c,d,e,则栈的输出序列不可能是(A ) A.dceab B.decba C.edcba D.abcde 10.元素大小为1个单元,容量为n个单元的非空顺序栈中,以地址高端为栈底,以top 作为栈顶指针,则出栈处理后,top的值应修改为(D ) A.top=top B.top=n-1 C.top=top-1 D.top=top+1 11.设有一个10阶的对称矩阵A,采用压缩存储方式以行序为主序存储,a00为第一个元素,其存储地址为0,每个元素占有1个存储地址空间,则a45的地址为( B ) A.13 B.35 C.17 D.36 12.栈和队列(C) A.共同之处在于二者都是先进先出的特殊的线性表 B.共同之处在于二者都是先进后出的特殊的线性表 C.共同之处在于二者都只允许在顶端执行删除操作

计10--数据结构专题实验rev2

上机实验要求及规范 《数据结构》课程具有比较强的理论性,同时也具有较强的可应用性和实践性,因此上机实验是一个重要的教学环节。一般情况下学生能够重视实验环节,对于编写程序上机练习具有一定的积极性,但是容易忽略实验的总结,忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目,一般不要急于编程,而是应该按照面向过程的程序设计思路(关于面向对象的训练将在其它后继课程中进行),首先理解问题,明确给定的条件和要求解决的问题,然后按照自顶向下,逐步求精,分而治之的策略,逐一地解决子问题。具体步骤如下: 1.问题分析与系统结构设计 充分地分析和理解问题本身,弄清要求做什么(而不是怎么做),限制条件是什么。按照以数据结构为中心的原则划分模块,搞清数据的逻辑结构(是线性表还是树、图?),确定数据的存储结构(是顺序结构还是链表结构?),然后设计有关操作的函数。在每个函数模块中,要综合考虑系统功能,使系统结构清晰、合理、简单和易于调试。最后写出每个模块的算法头和规格说明,列出模块之间的调用关系(可以用图表示),便完成了系统结构设计。 2.详细设计和编码 详细设计是对函数(模块)的进一步求精,用伪高级语言(如类C语言)或自然语言写出算法框架,这时不必确定很多结构和变量。 编码,即程序设计,是对详细设计结果的进一步求精,即用某种高级语言(如C/C++语言)表达出来。尽量多设一些注释语句,清晰易懂。尽量临时增加一些输出语句,便于差错矫正,在程序成功后再删去它们。 3.上机准备 熟悉高级语言用法,如C语言。熟悉机器(即操作系统),基本的常用命令。静态检查主要有两条路径,一是用一组测试数据手工执行程序(或分模块进行);二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑,在这个过程中再加入一些注释和断言。如果程序中逻辑概念清楚,后者将比前者有效。 4.上机调试程序 调试最好分块进行,自底向上,即先调试底层函数,必要时可以另写一个调用驱动程序,表面上的麻烦工作可以大大降低调试时所面临的复杂性,提高工作效率。 5.整理实验报告 在上机实验开始之前要充分准备实验数据,在上机实践过程中要及时记录实验数据,在上机实践完成之后必须及时总结分析,写出实验报告。

数据结构书面作业练习题

书面作业练习题 李英龙 湖南科技大学数学与计算科学学院

内容简介 在习题部分,既有选择题、判断题,也有用图表解答的练习题、算法设计题或综合解答分析题。并且配有部分练习题的答案供学生自学、练习、参考。 目录 书面作业练习题 习题一绪论 -------------------------------------------------------------3 习题二顺序表示(线性表、栈和队列)-----------------------------------------6 习题三链表(线性表、栈和队列)---------------------------------------------9 习题四串-----------------------------------------------------------------12 习题五数组 --------------------------------------------------------------13 习题六树与二叉树 -------------------------------------------------------15 习题七图-----------------------------------------------------------------24 习题八查找---------------------------------------------------------------30 习题九排序---------------------------------------------------------------33

数据结构综合练习题

数据结构综合练习题

数据结构(一) 一、选择题 1.组成数据的基本单位是( C )。 (A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量 2.设数据结构A=(D,R),其中D={1,2,3,4},R={r},r={<1,2>,<2,3>,<3,4>,<4,1>},则数据结构A 是( C )。 (A) 线性结构(B) 树型结构(C) 图型结构(D) 集合 3.数组的逻辑结构不同于下列( D )的逻辑结构。(A) 线性表(B) 栈(C) 队列(D) 树 4.二叉树中第i(i≥1)层上的结点数最多有(C )个。 (A) 2i (B) 2i(C) 2i-1(D) 2i-1 5.设指针变量p指向单链表结点A,则删除结点A的后继结点B需要的操作为(A )。 (A) p->next=p->next->next (B) p=p->next (C) p=p->next->next (D) p->next=p 6.设栈S和队列Q的初始状态为空,元素E1、E2、E3、E4、E5和E6依次通过栈S,一个元素出栈后即进入队列Q,若6个元素出列的顺序为E2、E4、E3、E6、E5和E1,则栈S的容量至少应该是( C )。 (A) 6 (B) 4 (C) 3 (D) 2

7.将10阶对称矩阵压缩存储到一维数组A中,则数组A 的长度最少为( C )。 (A) 100 (B) 40 (C) 55 (D) 80 8.设结点A有3个兄弟结点且结点B为结点A的双亲结点,则结点B的度数数为( B )。 (A) 3 (B) 4 (C) 5 (D) 1 9.根据二叉树的定义可知二叉树共有( B )种不同的形态。 (A) 4 (B) 5 (C) 6 (D) 7 10.设有以下四种排序方法,则( B )的空间复 杂度最大。 (A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序 11、以下说法正确的是( A ) A.连通图的生成树,是该连通图的一个极小连通子图。 B.无向图的邻接矩阵是对称的,有向图的邻接矩阵一定是不对称的。 C.任何一个有向图,其全部顶点可以排成一个拓扑序列。 D.有回路的图不能进行拓扑排序。 12、以下说法错误的是 ( D ) A.一般在哈夫曼树中,权值越大的叶子离根结点越近 B.哈夫曼树中没有度数为1的分支结点 C.若初始森林中共有n裸二叉树,最终求得的哈夫曼树

数据文件格式

1.交点线文件(*.JDX) 系统提供三种交点线资料的格式: 格式一: XY(或NE) 1 起点编号坐标坐标 0 交点号坐标坐标 R LS1 LS2 R1 R2 交点号坐标坐标 R LS1 LS2 R1 R2 …… 终点编号坐标坐标 0 格式二: XY(或NE) 2 起点编号起点坐标X 起点坐标Y 0 交点号起始边方位角起始边长度 R LS1 LS2 R1 R2 交点号来向边方位角来向边长度 R LS1 LS2 R1 R2 ……… 终点编号终止边方位角终止边长度 0 格式三: XY(或NE) 3 起点编号起点坐标X(或N)起点坐标Y(或E) 0 交点号起始边方位角起始边长度 R LS1 LS2 R1 R2 交点号来向边偏角来向边长度 R LS1 LS2 R1 R2

………. 终点编号终止边偏角终止边长度 0 格式说明: 大地(测量)坐标系,采用“NE”标识;数学直角坐标系采用“XY”标识。 对于低等级路起点坐标和起始边方位角可以假设为0。 偏角的正负与坐标相关,在XY坐标系下:左正右负;在NE坐标系下:左负右正。 变量意义 R:圆曲线半径 LS1、LS2:第1和第2回旋线的长度,对于四级公路,当LS1、LS2的值为负值时表示Lc1和Lc2值(缓和段的长度),HARD系统允许在四级公路中同时存在LS和LC值;(无相应回旋线时输0,成对出现)R1 R2 ---第1、第2回旋线起点半径;(无相应半径时输0,成对出现。) 对于存在虚交的交点线文件,应按如下述格式填写,比如TA、 TB、 TC、 TD 四点组成虚交(TA为总交点,TB、 TC、 TD为分交点),应将这四点共有的曲线信息写在TA 的后面,而其他三点的曲线信息位置填写 -1 。比如: NE n 表示第n种交点线格式 . . . . . TA 坐标坐标 R LS1 LS2 R1 R2 TB 坐标坐标 -1 TC 坐标坐标 -1 TD 坐标坐标 -1 . . . . . . Hard系统能够处理任意多点的虚交问题。 6、提醒用户:交互式设计的同时可以通过“输出文件”输出*.JDX和*.PQX文件以随时存储设计成果。

GIF文件的数据结构以及播放和分解GIF的源代码

GIF文件的数据结构以及播放和分解GIF的源代码 GIF 文件内部是按块划分的,包括控制块和数据块两种。控制块控制数据块的行为,不同的控制块 包含不同的控制参数。数据块只包含一些8bit的字符流,由它前面的控制块来决定它的功能,每个数据 块0—255个字节,数据块的第一个字节指出这个数据块长度(字节数),计算数据块的长度时不包括这 个字节,所以一个空的数据块也有一个字节,那就是数据块的大小&H00。 控制块中的逻辑屏幕描述块和全局彩色表的作用范围是整个数据流, 其他控制块仅控制跟在它们后 面的图形描述块。 GIF文件的典型结构如下表所示。 --------------------------------------- 顺号结构名称长度(字节) --------------------------------------- 1GIF文件头 6 2逻辑屏幕描述块7 3全局彩色表≤768 4图形描述块10 5局部彩色表(可重复n次)≤768 6表式压缩图像数据 7图像控制扩展块8 8无格式文本扩展块 9注释扩展块4-258 10 应用程序扩展块 11 GIF文件结束块 1 ----------------------------------------

一、控制块 1. GIF文件头 文件头由6个固定字节组成,结构如下表所示。 单位:字节 --------------------- 偏移量长度域名称 --------------------- 03GIF标记 33版本号 --------------------- GIF标记存放的是“GIF”的Ascii码,版本号存放的是1987年5月发布的“87a”或者1989年7月发布 的“89a”,或者更加新的版本号。 2. 逻辑屏幕描述块 逻辑屏幕描述块紧跟在GIF文件头之后。 逻辑屏幕描述块由7个固定字节组成,包含定义图像显示区域的参数,包括背景颜色信息。这个数 据块中的坐标相对于虚拟屏幕的左上角,不一定是指显示屏幕的绝对坐标。逻辑屏幕描述块的结构如下 表所示: 单位:字节 -------------------------------- 偏移量长度域名称 -------------------------------- 62逻辑屏幕宽度(像素) 82逻辑屏幕高度(像素)

社会保障卡文件结构和数据项(V2.0) .doc

谢谢观赏 谢谢观赏社会保障卡文件结构和数据项(V2.0) 引言 本规范是《社会保障(个人)卡规范》(LB002-2000)中关于应用文件结构和数据项部分的升级,包括以下主要内容: ——社会保障卡应用的文件结构和数据项。其中包括DDF,ADF和EF的内部属性,访问控制等信息。 1 适用范围 本规范适用于人力资源和社会保障领域面向社会公众发行的社会保障卡。其使用对象主要是与社会保障卡应用相关的卡片设计、制造、管理、发行、受理以及应用系统的研制、开发、集成和维护等组织机构。 2 参考标准 GB/T 16649.5-2002 识别卡带触点的集成电路卡第5部分:应用标识符的国家编 号体系和注册规程 3 定义 以下定义适用于本规范。 3.1 命令(Command) 终端向IC卡发出的一条信息,该信息启动一个操作或请求一个应答。 3.2 响应(Response) IC卡处理完成收到的命令报文后,回送给终端的报文。 3.3 交易(Transaction) 持卡者和业务、管理部门之间根据社会保障卡所支持的应用接受、提供服务的行为。 3.4 集成电路卡(IC卡)(Integrated Circuit(s) Card) 内部封装一个或多个集成电路的ID-1型卡(如ISO/IEC 7810、ISO/IEC 7811第1至第5部分、ISO/IEC 7812和ISO/IEC 7813中描述的)。 3.5 报文(Message) 由终端向卡或卡向终端发出的,不含传输控制字符的字节串。 3.6 报文鉴别代码(Message Authentication Code) 对交易数据及其相关参数进行运算后产生的代码。主要用于验证报文的完整性。 3.7 密钥(Key)

数据结构练习题及参考答案

数据结构练习题 第一部分绪论 一、单选题 1. 一个数组元素a[i]与________的表示等价。 A、 *(a+i) B、 a+i C、 *a+i D、 &a+i 2. 对于两个函数,若函数名相同,但只是____________不同则不是重载函数。 A、参数类型 B、参数个数 C、函数类型 3. 若需要利用形参直接访问实参,则应把形参变量说明为________参数 A、指针 B、引用 C、值 4. 下面程序段的时间复杂度为____________。 for(int i=0; i

数据库的存储结构(文件、记录的组织和索引技术)

数据库的存储结构(文件、记录的组织和索引技术) by 沈燕然0124141 利用课余时间自学了第6章《数据库存储结构》,对于数据 库不同层次的存储结构,文件记录组织和索引技术有了一定的 了解,在这篇札记中将会结合一些具体应用中涉及到的数据存 储和索引知识,以及通过与过去学习过的一些数据结构比较来 记录自己学习的心得体会。这些实例涉及不同的数据库系统, 如Oracle, DB2和Mysql等等,它们之间会有一些差异。不过 本文旨在探讨数据存储方面的问题,因而兼容并包地将其一并收入,凡是可能需要说明之处都会加上相应的注解。:) 1、数据库(DBS)由什么组成?——逻辑、物理和性能特征 1、什么是数据库系统(DBS)——DBS用文件系统实现 在关系模型中,我们把DBS看成关系的汇集。DBS存在的目的就是为了使用户能够简单、方便、容易地存取数据库中的数据。因此在用户的眼中,数据库也就是以某种方式相关的表的集合。用户并不需要去关心表之间关系,更不需要了解这些表是怎样存储的。但是我们现在从DBA(数据库管理员)的角度来看,情况就比那稍稍复杂一点。 实际的数据库包含许多下面列出的物理和逻辑对象: ?表、视图、索引和模式(确定数据如何组织) ?锁、触发器、存储过程和包(引用数据库的物理实现) ?缓冲池、日志文件和表空间(仅处理如何管理数据库性能) 2、什么是表空间?——表空间相当于文件系统中的文件夹。 表空间被用作数据库和包含实际表数据的容器对象之间的一层,表空间可以包含多个不同的表。用户处理的实际数据位于表中,他们并不知道数据的物理表示,这种情况有时被称为数据的物理无关性。

上图描述了一个ORACLE数据库大致的表空间组织,USER中存放主要的数据表,TEMP存放临时数据表,INDX存放索引,TOOLS存放回退段(RBS). 表空间在DB2数据库系统中是比较典型的说法,在Mysql等系统中也直接使用文件系统中文件夹的概念。新建一个表的时候可以指定它所在的表空间,至于用文件具体存储数据时如何存储这可能就是各个数据库系统的商业机密了,至少DB2是这样。另外值得关注的一点是不同于oracles对表空间的严格要求,Mysql的数据库形式相对比较简单,以文件夹的形式存放在安装目录的/data/下面,该数据库的每一个表对应两个文件,一个存放表中数据,另一个存放元数据信息,也就是建表时指明的列属性等等信息。 3、文件中的记录在物理上如何实现?——文件组织形式 在外存中,DB以文件形式组织,而文件由记录组成。文件结构由OS的文件系统提供和管理。文件组织有两种方式——定长记录格式和变长记录格式。 那种格式更好? 定长记录格式——优点是插入操作较简单。 缺点是对记录长度有硬性要求,而且有的记录可能横跨多个快,降低读写效率。 变长记录格式——优点是记录长度自由方便 缺点是记录长度差异导致删除后产生大量“碎片”,记录很难伸长,尤其“被拴记录”移动代价相当大。 中庸之道——预留空间和指针方式 记录长度大多相近——采用预留空间方法,取最大记录长为统一标准,在短记录多于空间处填特定空值或记录尾标志符。 记录长度相差很大——采用指针形式(每纪录后的指针字段把相同属性值记录链接起来)。文件中使用两种块——固定块(存放每条链中第一条记录)和溢出块(存放其 余纪录)。 3、记录在文件中怎样组织?

数据结构毕业设计题目整理

数据结构课程设计题目 1.飞机订票系统(限1 人完成)(顺序或链式存储) 任务:通过此系统可以实现如下功能: 录入: 可以录入航班情况(数据可以存储在一个数据文件中,数据结构、具体数据自定) 查询: 可以查询某个航线的情况(如,输入航班号,查询起降时间,起飞抵达城市,航班票价,票价折扣,确定航班是否满仓); 可以输入起飞抵达城市,查询飞机航班情况; 订票:(订票情况可以存在一个数据文件中,结构自己设定) 可以订票,如果该航班已经无票,可以提供相关可选择航班; 退票:可退票,退票后修改相关数据文件; 客户资料有姓名,证件号,订票数量及航班情况,订单要有编号。 修改航班信息: 当航班信息改变可以修改航班数据文件 要求: 根据以上功能说明,设计航班信息,订票信息,客户信息的存储结构,设计程序完成功能; 2.宿舍管理查询软件(限1 人完成) 任务:为宿舍管理人员编写一个宿舍管理查询软件, 程序设计要求: 采用交互工作方式 建立数据文件,包括学生信息、宿舍信息、住宿信息,学生信息按关键字(姓名、学号)进行排序(排序方法自选,不能相同); 查询: (用二分查找实现以下操作) 按姓名查询 按学号查询 (用顺序查找实现以下操作) 按房号查询 3.校园导航问题(限1 人完成) 设计要求:设计你的学校的平面图,至少包括10个以上的场所,每两个场所间可以有不同的路,且路长也可能不同,找出从任意场所到达另一场所的最佳路径(最短路径)。 要求:能增加场所 4.图书借阅管理系统(限1 人完成)(顺序或链式存储) 主要分为两大功能: 1)图书管理(增加图书、查询图书、删除图书、图书借阅、还书); 2)会员管理(增加会员、查询会员、删除会员、借书信息); 5.学生成绩管理(限1 人完成)(顺序或链式存储) 包括:课程信息,学生信息等;能增加课程或学生。 实现功能:输入、输出、插入、删除、查找、显示、保存、排序、退出。6.活期储蓄帐目管理(限1 人完成) 活期储蓄处理中,储户开户、销户、存入、支出活动频繁,系统设计要求: 1)能比较迅速地找到储户的帐户,以实现存款、取款记账;

数据结构-综合练习题-打印

数据结构综合练习题 1填空题 1.数据结构包含三个方面的内容,分别是数据的逻辑结构、数据的存储结构和数据的运算。 2.实现数据结构的四种存储方法有顺序存储方法、链接存储方法、索引存储方法和散列存储方法。 3.数据结构的逻辑结构有线性结构和非线性结构两大类。 4.一种抽象数据类型包括抽象数据的组织和与之相关的操作两个部分。 5.算法的五个重要特性是输入、输出、确定性、可行性和有穷性。 6.栈顶的位置是随进栈和出栈操作而变化的。 7.在链队列只有一个元素的情况下,对其做删除操作时,应当把对头指针和队尾指针都置为null。 8.操作系统中先来先服务是数据结构中的队列应用的典型例子。 9.在解决计算机主机与打印机之间速度不匹配问题时,通常设置一个打印数据缓冲区,主机将要输 出的数据依次写入该缓冲区,而打印机从该缓冲区中取出数据打印。该缓冲区应该是一个队列结构。 10.有一棵树如下图所示,回答下列问题。11.有一棵树如下图所示,回答下列问题。 (1)这棵树的根结点是K1;(1)结点k3的度是 2 ; (2)这棵树的叶子结点是K2,K4,K5,K7;(2)这棵树的度为 3 ;

12.有一棵树如下图所示,回答下列问题。 13有一棵树如下图所示,回答下列问题。 这棵树的深度为 4 ; (1)结点K3的子女是 K5 ,K6 ; (2)结点K3的双亲结点是 K1 。 14.在一棵二叉树中,度为零的结点个数为n0,度为2的结点的个数为n2,则有n0=n2+1。 15.n (n>0)个结点的二叉树高度最大是 n ,其深度最小是?log 2(n+1)?或??1log 2+n 。 16.n(n>0)个结点的满二叉树深度是)1(log 2+n ,叶子结点数是 (n+1)/2。阿 17.下面二叉树的中序序列是GDHABC 。 18.n (n>0)个结点的哈夫曼树中度为2的结点共 (n-1)/2 个,叶子结点共(n+1)/2个。 19.n 个顶点的有向图最多有 n*(n-1) 条边。 20.n (n>0)个顶点的连通无向图各顶点度之和最少是 2(n-1) 。 21.有6个顶点的无向图至少应有 5 条边才能确保是一个连通图。 22. n(n>0)个顶点的连通无向图至少有 n-1 条边。 23. 恰有 n(n-1) 条边的有向图称为有向完全图。

数据库的存储结构

第五章数据库的存储结构 5.1数据库存储介质的特点 ●内存 容量低(一般只有几百M,最多一两个G),价格高,速度快,数据易丢失(掉电、当机等)。 一般做DBMS(或CPU)和DB之间的数据缓冲区。 实时/内存数据库系统中使用内存存放实时数据。 ●硬盘 容量高(一般有几十G,多到一两百G),价格中,速度较快,数据不易丢失(除非物理性损坏)。 一般做用来存放DB。 实时/内存数据库系统中使用硬盘存放历史数据库。 ●移动硬盘(USB接口) 容量高(一般有几十G),价格中,速度较快,数据不易丢失(除非物理性损坏)。 一般做用来做备份。 ●光盘 容量低(一般650M/片,但光盘可在线更换,海量),价格低,速度中,数据不易丢失(除非物理性损坏)。 一般做用来做备份。 ●磁盘(软盘) 容量低(一般有几M,优盘多到一两百M),价格中,速度较慢,数据不易丢失(除非物理性损坏)。 一般数据库不使用磁盘。 ●磁带 容量低(但可在线更换,海量),价格低,速度最慢,且要按顺序存取,数据不易丢失(除非物理性损坏)。 一般做用来做备份。 按速度从高到低: 内存、硬盘、USB盘(移动硬盘和优盘)、光盘、软盘、磁带。 按在线容量从大到小: 硬盘、移动硬盘、内存、光盘、磁带、优盘、软盘。 物理块:512byte/1K/2K/4K/8K 原因: (1)减少I/O的次数; (2)减少间隙的数目,提高硬盘空间的利用率。 ORACLE逻辑块与物理块(init.ora中db_block_size定义逻辑块大小) 缓冲块和缓冲区(即SGA中的Data Buffer Cache) 延迟写(delayed write)技术/预取(Prefetching)技术(ORACLE中由DBWR进程完成数据的读写)

数据结构(C语言版) 期末复习汇总

数据结构(C语言版)期末复习汇总 第一章绪论 数据结构:是一门研究非数值计算程序设计中的操作对象,以及这些对象之间的关系和操作的学科。 数据结构是一门综合性的专业课程,是一门介于数学、计算机硬件、计算机软件之间的一门核心课程。是设计和实现编译系统、操作系统、数据库系统及其他系统程序和大型应用程序的基础。 数据:是客观事物的符号表示,是所有能输入到计算机中并被计算机程序处理的符号的总称。 如数学计算中用到的整数和实数,文本编辑中用到的字符串,多媒体程序处理的图形、图像、声音及动画等通过特殊编码定义后的数据。 数据的逻辑结构划分:线、树、图 算法的定义及特性 算法:是为了解决某类问题而规定的一个有限长的操作序列。 五个特性:有穷性、确定性、可行性、输入、输出 评价算法优劣的基本标准(4个): 正确性、可读性、健壮性、高效性及低存储量 第二章线性表 线性表的定义和特点: 线性表:由n(n≥0)个数据特性相同的元素构成的有限序列。线性表中元素个数n(n≥0)定义为线性表的长度,n=0时称为空表。 非空线性表或线性结构,其特点: (1)存在唯一的一个被称作“第一个”的数据元素; (2)存在唯一的一个被称作“最有一个”的数据元素; (3)除第一个之外,结构中的每个数据元素均只有一个前驱; (4)除最后一个之外,结构中的每个数据元素均只有一个后继。 顺序表的插入:n个元素在i位插入,应移动(n-i+1)位元素。 顺序表存储结构的优缺点: 优点: 逻辑相邻,物理相邻;可随机存取任一元素;存储空间使用紧凑; 缺点: 插入、删除操作需要移动大量的元素;预先分配空间需按最大空间分配,利用不充分; 表容量难以扩充; 线性表的应用: 一般线性表的合并:★★★ 算法2.1:LA=(7,5,3,11) LB=(2,6,3) 合并后LA=(7,5,3,11,2,6) 算法思想:扩大线性表LA,将存在于线性表LB中而不存在于线性表LA中的数据元素插入到线性表LA中去。只要从线性表LB中依次取得每个数据元素,并依值在线性表LA中

数据结构实验报告

姓名: 学号: 班级: 2010年12月15日

实验一线性表的应用 【实验目的】 1、熟练掌握线性表的基本操作在顺序存储和链式存储上的实现。、; 2、以线性表的各种操作(建立、插入、删除、遍历等)的实现为重点; 3、掌握线性表的动态分配顺序存储结构的定义和基本操作的实现; 4、通过本章实验帮助学生加深对C语言的使用(特别是函数的参数调用、指针类型的 应用和链表的建立等各种基本操作)。 【实验内容】 约瑟夫问题的实现:n只猴子要选猴王,所有的猴子按1,2,…,n编号围坐一圈,从第一号开始按1,2…,m报数,凡报到m号的猴子退出圈外,如此次循环报数,知道圈内剩下一只猴子时,这个猴子就是猴王。编写一个程序实现上述过程,n和m由键盘输入。【实验要求】 1、要求用顺序表和链表分别实现约瑟夫问题。 2、独立完成,严禁抄袭。 3、上的实验报告有如下部分组成: ①实验名称 ②实验目的 ③实验内容:问题描述:数据描述:算法描述:程序清单:测试数据 算法: #include #include typedef struct LPeople { int num; struct LPeople *next; }peo; void Joseph(int n,int m) //用循环链表实现 { int i,j; peo *p,*q,*head; head=p=q=(peo *)malloc(sizeof(peo)); p->num=0;p->next=head; for(i=1;inum=i;q->next=p;p->next=head; } q=p;p=p->next; i=0;j=1; while(i

数据结构选择题

选择一项: 1. 108 2. 110 3. 100 4. 120 2.在n个结点的顺序表中,算法的时间复杂度是O(1)的操作是( b) 选择一项: a. 删除第i个结点(1≤i≤n) b. 访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n) c. 将n个结点从小到大排序 d. 在第i个结点后插入一个新结点(1≤i≤n) 3.以下说法错误的是( d)。 选择一项: a. 由于顺序存储要求连续的存储区域,所以在存储管理上不够灵活 b. 顺序存储的线性表可以随机存取 c. 求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低 d. 线性表的链式存储结构优于顺序存储结构 4.单链表的存储密度( b)。 选择一项: a. 不能确定 b. 小于1 c. 大于1 d. 等于1 5.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动的元素个数为( c)。 选择一项: a. 63 b. 7 c. d. 8 6.在一个长度为n的顺序表中,在第i个元素(1≤i≤n+1)之前插入一个新元素时须向后移动( b)个元素。 选择一项: a. n-i b. n-i+1 c. i d. n-i-1 7.在单链表中,要将s所指结点插入到p所指结点之后,其语句应为(a )。 选择一项: a. s->next=p->next; p->next=s; b. (*p).next=s; (*s).next=(*p).next; c. s->next=p->next; p->next=s->next;

d. s->next=p+1; p->next=s; 8.在双向循环链表中,在p指针所指的结点后插入q所指向的新结点,其修改指针的操作是(b )。 选择一项: a. p->next=q; q->prior=p; p->next->prior=q; q->next=q; b. q->prior=p; q->next=p->next; p->next->prior=q; p->next=q; c. p->next=q; p->next->prior=q; q->prior=p; q->next=p->next; d. q->prior=p; q->next=p->next; p->next=q; p->next->prior=q; 9.在双向链表存储结构中,删除p所指的结点时须修改指针(c )。 选择一项: a. p->prior=p->next->next; p->next=p->prior->prior; b. p->next=p->next->next; p->next->prior=p; c. p->next->prior=p->prior; p->prior->next=p->next; d. p->prior->next=p; p->prior=p->prior->prior; 10.将两个各有n个元素的有序表归并成一个有序表,其最少的比较次数是(c )。 选择一项: a. 2n b. n-1 c. n d. 2n-1 11.线性表L=(a1,a2,……an),下列说法正确的是( b)。 选择一项: a. 表中诸元素的排列必须是由小到大或由大到小 b. 除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直接后继。 c. 每个元素都有一个直接前驱和一个直接后继 d. 线性表中至少有一个元素 12.线性表若采用链式存储结构时,要求内存中可用存储单元的地址(d )。 选择一项: a. 部分地址必须是连续的 b. 一定是不连续的 c. 必须是连续的 d. 连续或不连续都可以 13.线性表L在(d )情况下适用于使用链式结构实现。 选择一项: a. L中结点结构复杂 b. L中含有大量的结点 c. 需经常修改L中的结点值 d. 需不断对L进行删除插入 14.若指定有n个元素的向量,则建立一个有序单链表的时间复杂性的量级是( b)。 选择一项:

相关文档
相关文档 最新文档