注意事项1. 考试时间2小时，13：00-15：00 2. 题目4选2 3. 所有题目均使用标准输入和标准输出3. 只提交源程序，文件后缀名只能是.C或.CPP 4. 源文件大小不能超过10K，否则会被当作恶意提交而扣分5. 严格按照题目要求输出，去掉不需要的提示信息或调试信息6. 在程序中不要使用fflush(stdin)函数，否则会导致结果错误另外注意：本次是模拟测试，上机时间是4个小时，我们考试时间从14点开始到17点30分结束。同学视自己的能力，能做几道做几道。
哈夫曼树
时间限制: 100 second 内存限制: 100 Kb
描述
构造哈夫曼树（最优二叉树）
输入
输入n个结点每个结点的权值
输出
构造哈夫曼树（是最优二叉树）得到每个结点的哈夫曼编码
输入样例
23
186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8
输出样例
1( 186):00
2( 64):1001
3( 13):101100
4( 22):110010
5( 32):11100
6( 103):011
7( 21):110001
8( 15):101101
9( 47):11010
10( 57):0101
11( 1):101111000
12( 5):10111101
13( 32):11101
14( 20):110000
15( 57):1010
16( 63):1000
17( 15):101110
18( 1):101111001
19( 48):11011
20( 51):0100
21( 80):1111
22( 23):110011
23( 8):1011111
提示
输入第一行是结点数23 第二行是这几个结点的权值输出格式为结点号（权值）：哈夫曼编码
///////////////////////////////////////
计算huffman树WPL
时间限制: 5 second 内存限制: 100 Kb
描述
假设用于通信的电文由ｎ（4
输入
仅一组数据，分为两行输入；第１行为ｎ的值，第２行为ｎ（0
输出
一个整数，表示所构造哈夫曼树的带权路径长度（输出整数后换行）。
输入样例
8
7 19 2 6 32 3 21 10
输出样例
261
提示
Huffman树可以使用数组存储
//////////////////////////////////
求最小生成树的代价
时间限制: 5 second 内存限制: 100 Kb
描述
求无向网的最小生成树的代价。
输入
仅一组数据，输入数据第一行为两个正整数n和m，分别表示顶点数和边数。后面紧跟m 行数据，每行数据是一条边的信息，包括三个数字，分别表示该边的两个顶点和边上的权值。输出
输出得到的最小生成树的代价。
输入样例
8 11
1 2 3
1 4 5
1 6 18
2 4 7
2 5 6
3 5 10
3 8 20
4 6 15
4 7 11
5 7 8
5 8 12
输出样例
59
提示
每次找到最小生成树的一条边时累加其权值即可得到最小生成树的代价
///////////////////////////
判断堆栈出栈序列是否有效
时间限制: 5 second 内存限制: 100 Kb
描述
如果以序列“1,2,3,4”作为一个栈（初始为空）的输入，那么可得到输出序列“1,2,3,4”或“4,3,2,1”或“2,3,1,4”等等，但是肯定得不到输出序列“4,1,2,3”或“3,1,2,4”等等。请编写一个程序，判断能否通过一个栈得到给定的输出序列。
输入
有多组数据；输入的第一行为整数n（1
输出
对于每一组数据，输出一个yes或no（表示能否通过栈得到该序列）。
输入样例
2
6
3 4 2 1 5 6
4
3 1 2 4
输出样例
yes
no
提示
根据栈的后进先出特性进行判断
////////////////////////////
约瑟夫环
时间限制: 5 second 内存限制: 100 Kb
描述
编号为1,2,...,n的n个人按顺时针方向围坐一圈，每人持有一个密码（正整数）。现在给定一个随机数m>0，从编号为1的人开始，按顺时针方向1开始顺序报数，报到m时停止。报m的人出圈，同时留下他的密码作为新的m值，从他在顺时针方向上的下一个人开始，重新从1开始报数，如此下去，直至所有的人全部出圈为止。
输入
仅有一组数据，输入数据第一行为两个正整数n和m，分别表示人的个数及初始随机数，第二行为n个整数，表示每个人持有的密码
输出
在一行输出n个整数表示依次出圈人的编号，整数之间用空格分隔
输入样例
7 5
3 8 1 22
4 9 15
输出样例
5 2
6
7 4 3 1
提示
使用不带头节点的单循环链表
/////////////////////
根据二叉树的先序和中序列得到后序序列
时间限制: 5 second 内存限制: 100 Kb
描述
二叉树的每个节点用一个字符表示，如果知道二叉树的先序序列和中序序列则可以构造出一颗二叉树，进而可以得到该二叉树的后序序列
输入
仅一组数据，第一行为该二叉树的先序序列，第二行为该二叉树的中序遍历序列。
输出
输出该二叉树的后序遍历序列
输入样例
ABDGCEFH
DGBAECHF
输出样例
GDBEHFCA
提示
使用递归算法，根据先序序列找到树根，然后在中序序列中找到左右子树。此题不一定需要把树建立起来，可以在递归同时就得到后序序列。
///////////////////////////
求无向图连通子图
时间限制: 5 second 内存限制: 100 Kb
描述
求无向图连通子图个数
输入
仅一组数据，输入数据第一行为两个正整数n（1
输出
输出由两行构成，第一行输出该图中连通子图的个数。第二行按照升序输出每个连通子图中顶点个数。
输入样例
9 8
1 2
1 3
2 4
3 4
5 7
5 6
6 7
8 9
输出样例
3
2 3 4
提示
图的连通性以吐得遍历为基础，因此本题需要在图的遍历算法基础上实现
////////////////////////////////////
根据给定的关键字构造小顶堆，输出堆的中序遍历序列
时间限制: 5 second 内存限制: 100 Kb
描述
给出一组关键字（数字），根据这些关键字构造一个小顶堆，然后输出该小顶堆所对应的二叉树的中序遍历序列。
输入
仅一组数据，输入数据第一行为1个正整数n，表示关键字个数。第2行为n个整数表示n 个关键字。
输出
在一行上输出由这些关键字构成的小顶堆所对应的中序遍历序列。
输入样例
9
49 38 65 97 76 13 27 18 20
输出样例
97 20 38 18 76 13 65 27 49
提示
堆是一个完全二叉树，可以用数组存储
数据结构实验指导书 一、实验目的 《数据结构》是计算机学科一门重要的专业基础课程，也是计算机学科的一门核心课程。本课程较为系统地论述了软件设计中常用的数据结构以及相应的存储结构与实现算法，并做了相应的性能分析和比较，课程内容丰富，理论系统。本课程的学习将为后续课程的学习以及软件设计水平的提高打下良好的基础。 由于以下原因，使得掌握这门课程具有较大的难度： 1）理论艰深，方法灵活，给学习带来困难； 2）内容丰富，涉及的知识较多，学习有一定的难度； 3）侧重于知识的实际应用，要求学生有较好的思维以及较强的分析和解决问题的能力，因而加大了学习的难度； 根据《数据结构》课程本身的特性，通过实验实践内容的训练，突出构造性思维训练的特征，目的是提高学生分析问题，组织数据及设计大型软件的能力。 课程上机实验的目的，不仅仅是验证教材和讲课的内容，检查自己所编的程序是否正确，课程安排的上机实验的目的可以概括为如下几个方面： （1）加深对课堂讲授内容的理解 实验是对学生的一种全面综合训练。是与课堂听讲、自学和练习相辅相成的必不可少的一个教学环节。通常，实验题中的问题比平时的习题复杂得多，也更接近实际。实验着眼于原理与应用的结合点，使学生学会如何把书上学到的知识用于解决实际问题，培养软件工作所需要的动手能力；另一方面，能使书上的知识变" 活" ，起到深化理解和灵活掌握教学内容的目的。 不少学生在解答习题尤其是算法设计时，觉得无从下手。实验中的内容和教科书的内容是密切相关的，解决题目要求所需的各种技术大多可从教科书中找到，只不过其出
现的形式呈多样化，因此需要仔细体会，在反复实践的过程中才能掌握。 (2) 培养学生软件设计的综合能力 平时的练习较偏重于如何编写功能单一的" 小" 算法，而实验题是软件设计的综合训练，包括问题分析、总体结构设计、用户界面设计、程序设计基本技能和技巧，多人合作，以至一整套软件工作规范的训练和科学作风的培养。 通过实验使学生不仅能够深化理解教学内容，进一步提高灵活运用数据结构、算法和程序设计技术的能力，而且可以在需求分析、总体结构设计、算法设计、程序设计、上机操作及程序调试等基本技能方面受到综合训练。实验着眼于原理与应用的结合点，使学生学会如何把书本上和课堂上学到的知识用于解决实际问题，从而培养计算机软件工作所需要的动手能力。 (3) 熟悉程序开发环境，学习上机调试程序一个程序从编辑，编译，连接到运行，都要在一定的外部操作环境下才能进行。所谓" 环境" 就是所用的计算机系统硬件，软件条件，只有学会使用这些环境，才能进行 程序开发工作。通过上机实验，熟练地掌握程序的开发环境，为以后真正编写计算机程序解决实际问题打下基础。同时，在今后遇到其它开发环境时就会触类旁通，很快掌握新系统的使用。 完成程序的编写，决不意味着万事大吉。你认为万无一失的程序，实际上机运行时可能不断出现麻烦。如编译程序检测出一大堆语法错误。有时程序本身不存在语法错误，也能够顺利运行，但是运行结果显然是错误的。开发环境所提供的编译系统无法发现这种程序逻辑错误，只能靠自己的上机经验分析判断错误所在。程序的调试是一个技巧性很强的工作，尽快掌握程序调试方法是非常重要的。分析问题，选择算法，编好程序，只能说完成一半工作，另一半工作就是调试程序，运行程序并得到正确结果。 二、实验要求 常用的软件开发方法，是将软件开发过程划分为分析、设计、实现和维护四个阶段。虽然数据结构课程中的实验题目的远不如从实际问题中的复杂程度度高，但为了培养一个软件工作者所应具备的科学工作的方法和作风，也应遵循以下五个步骤来完成实验题目： 1) 问题分析和任务定义 在进行设计之前，首先应该充分地分析和理解问题，明确问题要求做什么?限制条件是什么。本步骤强调的是做什么?而不是怎么做。对问题的描述应避开算法和所涉及的数据类型，而是对所需完成的任务作出明确的回答。例如：输入数据的类型、值的范围以及输入的
数据结构模拟试题一 一、判断题（每小题1 分，共15分） 1.计算机程序处理的对象可分为数据和非数据两大类。 2.全体自然数按大小关系排成的序列是一个线性表。 3.在描述单向链表的结点类型时，必须首先描述数值字段，然后再描述指针字段。 4.顺序栈是一种规定了存储方法的栈。 5.树形结构中的每个结点都有一个前驱。 6.在任何一棵完全二叉树中，最多只有一个度为1的分支结点。 7.若某顶点是有向图的根，则该顶点的入度一定是零。 8.如果某图的邻接矩阵有全零的行，没有全零的列，则该图一定是有向图。 9.用一维数组表示矩阵可以节省存储空间。 10.广义表的长度与广义表中含有多少个原子元素有关。 11.分块查找的效率与线性表被分成多少块有关。 12.散列表的负载因子等于存入散列表中的结点个数。 13.在起泡排序过程中，某些元素可能会向相反的方向移动。 14.按某种逻辑关系组织起来的记录的集合称为逻辑记录。 15.索引非顺序文件的特点是索引表中的索引项不一定按关键字大小有序排列。 二、填空题（每空1分，共15分） 1.顺序表是一种_____________线性表。 2.若用Q[1]~Q[m]作为非循环顺序队列的存储空间，则对该队列最多只能执行___次插入操作。 3.栈和队列的区别在于________的不同。 4.在高度为h(h≥0)的二叉树中至少有___个结点，至多有___个结点。 5.若用二叉链表来存储具有m个叶子，n个分支结点的树，则二叉链表中有___个左指针域为空的结点，有___个右指针域 为空的结点。 6.n个顶点的有根有向图中至少有___条边，至多有___条边。 7.10行20列矩阵若用行优先顺序表来表示，则矩阵中第8行第7列元素是顺序表中第___个元素。 8.在各元素查找概率相等的情况下，用顺序查找方法从含有12个元素的有序表中查找一个元素，元素间的平均比较次数是 _____。 9.在归并两个长度为m的有序表时，排序码的比较次数至少是___次，至多是___次。 10.在高度为3的6阶B-树中，至少有___个关键字，至多有___个关键字。 三、选择题（每题2分，共30分） 1.计算机所处理的数据一般具有某种内在联系性，这是指________。 A．元素和元素之间存在某种关系B．数据和数据之间存在某种关系 C．元素内部具有某种结构D．数据项和数据项之间存在某种关系 2. 假设顺序表目前有4个元素，第i个元素放在R[i]中，1≤i≤4 。若把新插入元素存入R[6]，则________。 A．会产生运行错误B．R[1]~R[6]不构成一个顺序表 C．顺序表的长度大于顺序表元素个数，会降低存储空间利用率 D．顺序表元素序号和数组元素下标不一致，会给使用带来麻烦 3. 设H是不带表头结点循环单向链表的表头指针，P是和H同类型的变量。当P指向链表最后一个结点时，_________。A．P所指结点指针字段的值为空B．P的值与H的值相等 C．P所指结点的地址与H的值相等D．P所指结点指针字段的值与H的值相等 4. 栈的定义不涉及数据的__________。 A．逻辑结构B．存储结构C．运算D．逻辑结构和存储结构 5. 设5个元素进栈的顺序是1,2,3,4,5，则出栈的顺序有可能是___________。 A．2,4,1,3,5 B．3,4,1,5,2 C．3,2,4,1,5 D．4,1,3,2,5 6. 若某棵二叉树结点的前序序列和中序序列相同，则该二叉树_________。 A．只有一个结点B．每个结点都没有左孩子C．每个结点都没有右孩子D．不存在 7.对于一棵具有n个结点，度为3的树来说，____________。 A．树的高度至多是n-3 B．树的高度至多是n-2 C．树的最低高度是┏log3(n+1)┓ D．至少在某一层上正好有3个结点 8．n个顶点的有向图如果可以进行拓扑排序，则可以断定该有向图__________。 A．含n个强连通分量B．有唯一的入度为0的顶点C．有多个出度为0的顶点 D．是一个有根有向图 9. 特殊矩阵用行优先顺序表表示，_____________ A．简化了矩阵元素之间的逻辑关系B．便于按行处理矩阵元素
数据结构(C语言版) 实验报告
专业班级学号姓名 实验1 实验题目：单链表的插入和删除 实验目的： 了解和掌握线性表的逻辑结构和链式存储结构，掌握单链表的基本算法及相关的时间性能分析。 实验要求： 建立一个数据域定义为字符串的单链表，在链表中不允许有重复的字符串；根据输入的字符串，先找到相应的结点，后删除之。 实验主要步骤： 1、分析、理解给出的示例程序。 2、调试程序，并设计输入数据（如：bat，cat，eat，fat，hat，jat，lat，mat，#），测 试程序的如下功能：不允许重复字符串的插入；根据输入的字符串，找到相应的结点并删除。 3、修改程序： （1）增加插入结点的功能。 （2）将建立链表的方法改为头插入法。 程序代码: #include"" #include"" #include"" #include"" typedef struct node . . 示意图：
head head head 心得体会： 本次实验使我们对链表的实质了解更加明确了，对链表的一些基本操作也更加熟练了。另外实验指导书上给出的代码是有一些问题的，这使我们认识到实验过程中不能想当然的直接编译执行，应当在阅读并完全理解代码的基础上再执行，这才是实验的意义所在。
实验2 实验题目：二叉树操作设计和实现 实验目的： 掌握二叉树的定义、性质及存储方式，各种遍历算法。 实验要求： 采用二叉树链表作为存储结构，完成二叉树的建立，先序、中序和后序以及按层次遍历 的操作，求所有叶子及结点总数的操作。 实验主要步骤： 1、分析、理解程序。 2、调试程序，设计一棵二叉树，输入完全二叉树的先序序列，用#代表虚结点（空指针）， 如ABD###CE##F##，建立二叉树，求出先序、中序和后序以及按层次遍历序列，求 所有叶子及结点总数。 实验代码 #include"" #include"" #include"" #define Max 20 ertex=a; irstedge=NULL; irstedge; G->adjlist[i].firstedge=s; irstedge; R[i] 留在原位
上机实验要求及规范 《数据结构》课程具有比较强的理论性，同时也具有较强的可应用性和实践性，因此上机实验是一个重要的教学环节。一般情况下学生能够重视实验环节，对于编写程序上机练习具有一定的积极性，但是容易忽略实验的总结，忽略实验报告的撰写。对于一名大学生必须严格训练分析总结能力、书面表达能力。需要逐步培养书写科学实验报告以及科技论文的能力。拿到一个题目，一般不要急于编程，而是应该按照面向过程的程序设计思路（关于面向对象的训练将在其它后继课程中进行），首先理解问题，明确给定的条件和要求解决的问题，然后按照自顶向下，逐步求精，分而治之的策略，逐一地解决子问题。具体步骤如下： 1.问题分析与系统结构设计 充分地分析和理解问题本身，弄清要求做什么（而不是怎么做），限制条件是什么。按照以数据结构为中心的原则划分模块，搞清数据的逻辑结构（是线性表还是树、图？），确定数据的存储结构（是顺序结构还是链表结构？），然后设计有关操作的函数。在每个函数模块中，要综合考虑系统功能，使系统结构清晰、合理、简单和易于调试。最后写出每个模块的算法头和规格说明，列出模块之间的调用关系（可以用图表示），便完成了系统结构设计。 2.详细设计和编码 详细设计是对函数（模块）的进一步求精，用伪高级语言（如类C语言）或自然语言写出算法框架，这时不必确定很多结构和变量。 编码，即程序设计，是对详细设计结果的进一步求精，即用某种高级语言（如C/C++语言）表达出来。尽量多设一些注释语句，清晰易懂。尽量临时增加一些输出语句，便于差错矫正，在程序成功后再删去它们。 3.上机准备 熟悉高级语言用法，如C语言。熟悉机器（即操作系统），基本的常用命令。静态检查主要有两条路径，一是用一组测试数据手工执行程序（或分模块进行）；二是通过阅读或给别人讲解自己的程序而深入全面地理解程序逻辑，在这个过程中再加入一些注释和断言。如果程序中逻辑概念清楚，后者将比前者有效。 4.上机调试程序 调试最好分块进行，自底向上，即先调试底层函数，必要时可以另写一个调用驱动程序，表面上的麻烦工作可以大大降低调试时所面临的复杂性，提高工作效率。 5.整理实验报告 在上机实验开始之前要充分准备实验数据，在上机实践过程中要及时记录实验数据，在上机实践完成之后必须及时总结分析，写出实验报告。
《数据结构实验指导书》答案 实验一： 1、请编写函数int fun(int *a, int *b),函数的功能是判断两个指针a和b所指存储单元的值 的符号是否相同；若相同函数返回1，否则返回0。这两个存储单元中的值都不为0。 在主函数中输入2个整数、调用函数fun、输出结果。 #include
1+2+3+……+*n，在主函数中输入、调用、输出结果。 #include
void input(int *a,int n) { int i; for (i=0;i
一．是非题 1. 数据结构(应该是抽象数据类型)可用三元式表示(D，S，P)。其中：D是数据对象，S是D上的关系，P是对D的基本操作集。(f) 2 简单地说,数据结构是带有结构的数据元素的集合。(t) 3 判断带头结点的非空循环单链表(头指针为L)中指针p所指结点是最后一个元素结点 的条件是：p->next==L。(t) 4 线性表的链式存储结构具有可直接存取表中任一元素的优点。(f) 5 线性表的顺序存储结构优于链式存储结构。(f) 6. 在单链表P指针所指结点之后插入S结点的操作是： P->next= S ; S-> next = P->next;。(f) (顺序弄反了S-> next = P->next; P->next= S ;) 7 对于插入、删除而言，线性表的链式存储优于顺序存储。(t) 8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f) 9. 栈和队列是操作上受限制的线性表。(t) 10. 队列是与线性表完全不同的一种数据结构。(f) (栈和队列是操作上受限制的线性表) 11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。(f) (两端) 12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。(f) ( “如果需要,可对它们中的任一元素进行操作.” 这里的意思是在O(1)的时间来读和改某个元素。比如数组的直接索引。 栈：如果需要，每一次只能对栈顶的元素进行操作 队列：如果需要，每一次只能对两端，或者只能对队列头的元素进行操作。) 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(f) 14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。(f) (二叉树和树相互独立) 15 二叉树是一棵结点的度最大为二的树。(f) (二叉树和树相互独立) 16 赫夫曼树中结点个数一定是奇数。(t) 17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t) (LDR) 18 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历。(f) (后根遍历相当于中序遍历) 19. 通常，二叉树的第i层上有2i-1个结点。(f) (应该为1~2i-1个) 20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t) 21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(t) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树。(t) 23 邻接多重表可以用以表示无向图，也可用以表示有向图。(f) (只能表示无向图，有向图用十字链表) 24 可从任意有向图中得到关于所有顶点的拓扑次序。(f) (带环图没有) 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t)
实习一： 1、编写一个读入一个字符串，把它存入一个链表，并按相反的次序打印的程序。 2、设有一个单位的人员工资有如下信息：name、department、 base pay、allowance、total。现从键盘输入一组人员工资数据并将它们存储到名为paydata的文件中；再从paydata取出工资数据并给每个人的base pay增加100元，增加后将工资数据显示于屏幕(每行1人)。请编写能够完成上述工作的程序。 代码如下： 1.#include
数据结构上机实验题目 实验一线性表的顺序存储结构 实验学时 2学时 背景知识:顺序表的插入、删除及应用。 目的要求： 1．掌握顺序存储结构的特点。 2．掌握顺序存储结构的常见算法。 实验容 1．输入一组整型元素序列，建立顺序表。 2．实现该顺序表的遍历。 3．在该顺序表中进行顺序查找某一元素,查找成功返回1,否则返回0。4．判断该顺序表中元素是否对称,对称返回1,否则返回0。 5．实现把该表中所有奇数排在偶数之前,即表的前面为奇数,后面为偶数。 6．输入整型元素序列利用有序表插入算法建立一个有序表。 7．利用算法6建立两个非递减有序表并把它们合并成一个非递减有序表。 8. 利用该顺序结构实现循环队列的入队、出队操作。 8．编写一个主函数,调试上述算法。 #include
#define OVERFLOW 0 #define MAXSIZE 100 typedef int ElemType; typedef struct list {ElemType elem[MAXSIZE]; int length; }Sqlist; void Creatlist(Sqlist &L) {int i; printf("请输入顺序表的长度："); //输入一组整型元素序列，建立一个顺序表。 scanf("%d",&L.length); for(i=0;i 2011-2012学年第一学期期末考查 《数据结构》试卷 （答案一律写在答题纸上，在本试卷上做答无效） 一、选择（每题1分，共10分） 1.长度为n的线性表采用顺序存储结构，一个在其第i个位置插入新元素的算法时间复杂度为（D） A.O(0) B.O(1) C.O(n) D.O(n2) 2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（D） A.543612 B.453126 C.346512 D.234156 3.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（B ） A.8 B.9 C.10 D.11 4.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（ B ） A. m-n B.m-n-1 C.n+1 D.m+n 5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（B） A.9 B.11 C.15 D.不确定 6.下列哪一个方法可以判断出一个有向图是否有环。（A） A.深度优先遍历 B.拓扑排序 C.求最短路径 D.求关键路径 7.第7层有10个叶子结点的完全二叉树不可能有（B ）个结点。 A.73 B.234 C.235 D.236 8.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（B） A.（100,80,90,60,120,110,130） B.（100, 120, 110,130,80, 60,90） C.（100,60,80,90,120,110,130） D.（100,80, 60,90, 120, 130,110） 9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（B ） A.选择排序 B.起泡排序 C.快速排序 D.插入排序 10.对线性表进行折半查找时，要求线性表必须（D） A.以顺序方式存储 B.以顺序方式存储，且数据元素有序 习题二 ⒉１描述以下四个概念的区别：头指针变量，头指针，头结点，首结点（第一个结点）。解：头指针变量和头指针是指向链表中第一个结点（头结点或首结点）的指针；在首结点之前附设一个结点称为头结点；首结点是指链表中存储线性表中第一个数据元素的结点。若单链表中附设头结点，则不管线性表是否为空，头指针均不为空，否则表示空表的链表的头指针为空。 2.2简述线性表的两种存储结构有哪些主要优缺点及各自使用的场合。 解：顺序存储是按索引直接存储数据元素，方便灵活，效率高，但插入、删除操作将引起元素移动，降低了效率；而链式存储的元素存储采用动态分配，利用率高，但须增设表示结点之间有序关系的指针域，存取数据元素不如顺序存储方便，但结点的插入和删除十分简单。顺序存储适用于线性表中元素数量基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素的情况；而链式存储适用于频繁进行元素动态插入或删除操作的场合。 2.3 在头结点为h的单链表中，把值为b的结点s插入到值为a的结点之前，若不存在a，就把结点s插入到表尾。 Void insert(Lnode *h,int a,int b) {Lnode *p,*q,*s; s=(Lnode*)malloc(sizeof(Lnode)); s->data=b; p=h->next; while(p->data!=a&&p->next!=NULL) {q=p; p=p->next; } if (p->data==a) {q->next=s; s->next=p;} else {p->next=s; s->next=NULL; } } 2.4 设计一个算法将一个带头结点的单链表A分解成两个带头结点的单链表A和B，使A中含有原链表中序号为奇数的元素，而B中含有原链表中序号为偶数的元素，并且保持元素原有的相对顺序。 Lnode *cf(Lnode *ha) {Lnode *p,*q,*s,*hb; int t; p=ha->next; q=ha; t=0; hb=(Lnode*)malloc(sizeof(Lnode)); s=hb; while(p->next!=NULL) {if (t==0) {q=p;p=p->next;t=1;} else {q->next=p->next; p->next=s->next; s->next=p; s=p; p=p->next; t=0; } } s->next=NULL; return (hb); } 数据结构上机实验报告 学院：电子工程学院 专业：信息对抗技术 姓名： 学号： 教师：饶鲜 日期： 目录 实验一线性表 ........................................................................................................ - 2 - 一、实验目的.................................................................................................... - 2 - 二、实验代码.................................................................................................... - 2 - 三、实验结果.................................................................................................... - 8 - 四、个人思路.................................................................................................... - 9 - 实验二栈和队列 .................................................................................................... - 9 - 一、实验目的.................................................................................................... - 9 - 二、实验代码.................................................................................................. - 10 - 三、实验结果.................................................................................................. - 15 - 四、个人思路.................................................................................................. - 16 - 实验三数组 .......................................................................................................... - 16 - 一、实验目的.................................................................................................. - 16 - 二、实验代码.................................................................................................. - 16 - 三、实验结果.................................................................................................. - 18 - 四、个人思路.................................................................................................. - 18 - 实验四树 .............................................................................................................. - 18 - 一、实验目的.................................................................................................. - 18 - 二、实验代码.................................................................................................. - 19 - 三、实验结果.................................................................................................. - 24 - 四、个人思路.................................................................................................. - 25 - 注意事项1. 考试时间2小时，13：00-15：00 2. 题目4选2 3. 所有题目均使用标准输入和标准输出3. 只提交源程序，文件后缀名只能是.C或.CPP 4. 源文件大小不能超过10K，否则会被当作恶意提交而扣分5. 严格按照题目要求输出，去掉不需要的提示信息或调试信息6. 在程序中不要使用fflush(stdin)函数，否则会导致结果错误另外注意：本次是模拟测试，上机时间是4个小时，我们考试时间从14点开始到17点30分结束。同学视自己的能力，能做几道做几道。 哈夫曼树 时间限制: 100 second 内存限制: 100 Kb 描述 构造哈夫曼树（最优二叉树） 输入 输入n个结点每个结点的权值 输出 构造哈夫曼树（是最优二叉树）得到每个结点的哈夫曼编码 输入样例 23 186 64 13 22 32 103 21 15 47 57 1 5 32 20 57 63 15 1 48 51 80 23 8 输出样例 1( 186):00 2( 64):1001 3( 13):101100 4( 22):110010 5( 32):11100 6( 103):011 7( 21):110001 8( 15):101101 9( 47):11010 10( 57):0101 11( 1):101111000 12( 5):10111101 13( 32):11101 14( 20):110000 15( 57):1010 16( 63):1000 17( 15):101110 18( 1):101111001 19( 48):11011 20( 51):0100 21( 80):1111 22( 23):110011 23( 8):1011111 提示 输入第一行是结点数23 第二行是这几个结点的权值输出格式为结点号（权值）：哈夫曼编码 数据结构模拟卷(含答案)经典习题 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位10. 下列图示的顺序存储结构表示的二叉树是( ) 《数据结构》课程上机实验指导书 实验一 【实验名称】顺序表的基本算法 【实验目的】 创建一个顺序表，掌握线性表顺序存储的特点。设计和验证顺序表的查找、插入、删除算法。 【实验要求】 （1）从键盘读入一组整数，按输入顺序形成顺序表。并将创建好的顺序表元素依次打印在屏幕上。 设计一个带选择菜单的主函数，菜单中具备任意选择删除、插入、查找数据元素（2）的功能。 当选择删除功能时，从键盘读入欲删除的元素位置或元素值，按指定方式删除；3（）当选择插入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号。 （4）每种操作结束后，都能在屏幕上打印出此时顺序表元素的遍历结果。 【实验步骤】、实验前先写好算法。1 上机编写程序。2、编译。3、调试。4、 综合实例！，2-62-8！带菜单的主函数参考书上2.5，，，书上参考算法例程：2-12-42-5注意：顺序表的结构体！typedef struct { datatype items[listsize]; int length; }SpList; 实验二 【实验名称】单链表的基本算法 【实验目的】 创建一个单链表，掌握线性表链式存储的特点。设计和验证链表的查找、插入、删除、求表长的算法。【实验要求】 （1）从键盘读入一组整数，按输入顺序形成单链表。并将创建好的单链表元素依次打印在屏幕上。（注意：选择头插法或者尾插法！） 设计一个带选择功能菜单的主函数，菜单中至少具备任意选择删除、插入、查找（2）数据元素，和求单链表表长等几项功能。 当选择删除功能时，从键盘读入欲删除的元素位置，按指定位置删除；当选择插）（3入功能时，从键盘读入新元素值和被插入位置，在指定位置插入；当选择查找功能时，从键盘读入欲查找的元素值，返回其位置序号；当选择求表长功能时，返回该单链表表长的数值。 （4）每种操作结束后，都能在屏幕上打印出此时单链表元素的遍历结果。 【实验步骤】、实验前先写好算法。1 、上机编写程序。2 编译。3、调试。4、 综合实例！！带菜单的主函数参考书上，2-132-15，2-172.5，，书上参考算法例程：2-102-12 另外，注意，指针的初始化！指针的操作必须谨慎！链表的结构体如下：typedef struct Node { Datatype ch; struct Node *next; }LNode, *Pnode, *Linklist; 实验三 《数据结构》上机练习题 1、设有两个有序序列，利用归并排序将它们排成有序表，并输出。 2、设有一有序序列，从键盘输入一个数，判别是否在序列中，如果在输出“YSE”；否则，将它插入到序列中使它仍然有序，并输出排序后的序列。 3、设有一有序序列，从键盘输入一个数，判别是否在序列中，如果不在，则输出“NO”，否则，将它从序列中删除它，并输出删除后的序列。 4、从键盘输入一组任意数据，建立一个有序链表，并从链头开始输出该链，使输出结果是有序的。 5、从键盘输入一组任意数据，建立一个包含所有输入数据的单向循环链表，并从链表的任意开始，依次输出该链表中的所有结点。 10、设有一个链表，（自己建立，数据从键盘输入），再从键盘输入一个数，判别是否在链表中，如果不在，则输出“NO“，否则，将它从链表中删除，并输出删除后的链表。 11、设有一个链表，（自己建立，数据从键盘输入），再从键盘输入一个数，判别是否在链表中，如果在输出“YSE”，否则，将它从插入到链头，并输出插入后的链表。 12、设有一个链表，（自己建立，数据从键盘输入），再从键盘输入一个数，判别是否在链表中，如果在输出“YSE”，否则，将它从插入到链尾，并输出插入后的链表。 13、编写栈的压栈push、弹栈pop函数，从键盘输入一组数据，逐个元素压入堆栈，然后再逐个从栈中弹出它们并输出。 14、编写栈的压栈push、弹栈pop函数，用它判别（）的匹配问题。 15、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树中序遍历的结果。 16、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树先序遍历的结果。 17、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树后序遍历的结果。 18、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树的总结点数。 19、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出二叉树叶子结点数。 20、按类似先序遍历结果输入一序列，建立一棵二叉树（算法6、4），输出此二叉树的高度。 21、给出一个无向图的邻接矩阵，输出各个顶点的度。 22、给出一个有向图的邻接矩阵，输出各个顶点的入度与出度。 23、输入一个有序序列，利用折半查找来查找一个数是否在序列中，如在，则输出其位置，否则输出“NO”。 24、用插入排序方法对一组数据进行排序，并输出每趟排序的结果。 25、用选择排序方法对一组数据进行排序，并输出每趟排序的结果。 26、用希尔（SHELL）排序方法对一组数据进行排序，并输出每趟排序的结果。 27、用快速排序方法对一组数据进行排序，并输出每趟排序的结果。． 答案： 1. #include 练习题 一、单项选择题 1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合 C. 类型的有限集合 D. 关系的有限集合 2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 3. 若不带头结点的单链表的指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 4. 引起循环队列队头位置发生变化的操作是( ) A. 出队 B. 入队 C. 取队头元素 D. 取队尾元素 5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( ) A. 2，4，3，1，5，6 B. 3，2，4，1，6，5 C. 4，3，2，1，5，6 D. 2，3，5，1，6，4 1 6. 字符串通常采用的两种存储方式是( ) A. 散列存储和索引存储 B. 索引存储和链式存储 C. 顺序存储和链式存储 D. 散列存储和顺序存储 7. 数据结构是（） A．一种数据类型 B．数据的存储结构 C．一组性质相同的数据元素的集合 D．相互之间存在一种或多种特定关系的数据元素的集合 8. 算法分析的目的是（） A．辨别数据结构的合理性 B．评价算法的效率 C．研究算法中输入与输出的关系 D．鉴别算法的可读性 9. 在线性表的下列运算中，不．改变数据元素之间结构关系的运算是 （） A．插入B．删除 C．排序D．定位 10. 下列图示的顺序存储结构表示的二叉树是( ) 2 《数据结构简明教程》练习题及参考答案 练习题1 1. 单项选择题 （1）线性结构中数据元素之间是（）关系。 A.一对多 B.多对多 C.多对一 D.一对一 答：D （2）数据结构中与所使用的计算机无关的是数据的（）结构。 A.存储 B.物理 C.逻辑 D.物理和存储 答：C （3）算法分析的目的是（）。 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 D.分析算法的易懂性和文档性 答：C （4）算法分析的两个主要方面是（）。 A.空间复杂性和时间复杂性 B.正确性和简明性 C.可读性和文档性 D.数据复杂性和程序复杂性 答：A （5）计算机算法指的是（）。 A.计算方法 B. 排序方法 C.求解问题的有限运算序列 D.调度方法答：C （6）计算机算法必须具备输入、输出和（）等5个特性。 A.可行性、可移植性和可扩充性 B.可行性、确定性和有穷性 C.确定性、有穷性和稳定性 D.易读性、稳定性和安全性 答：B 2. 填空题 （1）数据结构包括数据的①、数据的②和数据的③这三个方面的内容。 答：①逻辑结构②存储结构③运算 数据结构简明教程 （2）数据结构按逻辑结构可分为两大类，它们分别是①和②。 答：①线性结构②非线性结构 （3）数据结构被形式地定义为（D,R），其中D是①的有限集合，R是D上的②有限集合。 答：①数据元素②关系 （4）在线性结构中，第一个结点①前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点②后继结点，其余每个结点有且只有1个后继结点。 答：①没有②没有 （5）在树形结构中，树根结点没有①结点，其余每个结点有且只有②个前驱结点；叶子结点没有③结点，其余每个结点的后继结点数可以是④。 答：①前驱②1 ③后继④任意多个 （6）在图形结构中，每个结点的前驱结点数和后继结点数可以是（）。 答：任意多个 （7）数据的存储结构主要有四种，它们分别是①、②、③和④存储结构。 答：①顺序②链式③索引④哈希 （8）一个算法的效率可分为①效率和②效率。 答：①时间②空间 3. 简答题 （1）数据结构和数据类型两个概念之间有区别吗？ 答：简单地说，数据结构定义了一组按某些关系结合在一起的数组元素的集合。数据类型不仅定义了一组数据元素，而且还在其上定义了一组操作。 （2）简述线性结构、树形结构和图形结构的不同点。 答：线性结构反映结点间的逻辑关系是一对一的，树形线性结构反映结点间的逻辑关系是一对多的，图在结构反映结点间的逻辑关系是多对多的。 （3）设有采用二元组表示的数据逻辑结构S=(D,R)，其中D={a,b,…,i}，R={(a,b),(a,c),(c,d),(c,f),(f,h),(d,e),(f,g),(h,i)}，问相对于关系R，哪些结点是开始结点，哪些结点是终端结点？ 答：该逻辑结构为树形结构，其中a结点没有前驱结点，称为根结点，b、e、g、i结点没有后继结点，是终端结点，也称为叶子结点。 （4）以下各函数是算法中语句的执行频度，n为问题规模，给出对应的时间复杂度： T1(n)=n log2n-1000log2n T2(n)=3 log2 n-1000log2n《数据结构》期末考试题及答案
数据结构上机例题及答案
数据结构上机实验报告
数据结构上机考试题
数据结构模拟卷(含答案)经典习题培训讲学
数据结构上机实验指导
数据结构上机考试(含答案)
数据结构模拟卷(含答案)经典习题
数据结构课程__课后习题答案
相关主题
文本预览