数据结构练习题
1、在数据结构中，从逻辑上可以把数据结构分成
A、动态结构和静态结构
B、紧凑结构和非紧凑结构
B、线性结构和非线性结构D、内部结构和外部结构
2、线性表的顺序存储结构是一种_____的结构，线性表的链式存储结构是一种____的存储结构
A、随机存取
B、顺序存取
C、索引存储
D、散列存取
3、线性表若采用链式存储结构时，要求内存中可用存储单元的地址____
A、必须是连续的
B、部分地址必须是连续的
B、一定是不连续的D、连续或不连续都可以
4、在下列叙述中，正确的是____
A、线性表的顺序存储结构优于链表存储结构
B、二维数组是其数据元素为线性表的线性表
C、栈的操作方式是先进先出
D、队列的操作方式是先进后出
5、一个顺序表第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是___
A、110
B、108
C、100
D、120
6、一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是____
A、edcba
B、decba
C、dceab
D、abcde
7、一个栈的入队序列是1，2，3，4，则队列的输出序列是____
A、4，3，2，1
B、1，2，3，4
C、1，4，3，2
D、3，2，4，1
8、判定一个栈ST空的(最多元素为m0)为空的条件是_____
A、ST->top!=0
B、ST->top= =0
C、S T->top!=m0
D、ST->top= =m0
9、判定一个栈(最多元素为m0)为满的条件是_____
A、ST->top!=0
B、ST->top= =0
D、ST->top!=m0 D、ST->top= =m0
10、判定一个队列QU(最多元素为m0)为空的条件是_____
A、QU->rear-QU->front= =m0
B、Q U->rear-QU->front-1= =m0
C、Q U->front= =QU->rear
D、QU->front= =QU->rear+1
11、判定一个队列QU(最多元素为m0)为空的条件是_____
A、QU->rear-QU->front= =m0
B、QU->rear-QU->front-1= =m0
C、QU->front= =QU->rear
D、QU->front= =QU->rear+1
12、判定一个循环队列QU(最多元素为m0)为空的条件是_____
A、QU->rear-QU->front= =m0
B、QU->rear-QU->front-1= =m0
C、QU->front= =（QU->rear+1）%m0
D、QU->front! =（QU->rear+1）%m0
13、判定一个循环队列QU(最多元素为m0)为满的条件是_____
A 、QU->rear -QU->front= =m0
B 、QU->rear -QU->front -1= =m0
C 、QU->front= =（QU->rear+1）%m0
D 、QU->front! =（QU->rear+1）%m0
14、循环队列用数组A[0,m-1]存放其元素值，已知其头尾指针分别是front 和rear ，则当前队列中的元素个数是_____
A 、（rear -front+m ）%m
B 、rear -front+1
C 、rear -front-1
E 、 rear -front
15、如下图所示的4棵二叉树中，____不是完全二叉树。
A
B
C D
16、在线索二叉树中，t 所指结点没有左子树的充要条件是______
A 、t->left=null
B 、t->ltag=1
C 、t->ltag=1且t->left=null
D 、以上都不对
17、二叉树按某种顺序线索化后，任一结点均有指向其前驱和后继的线索，这种说法___
A 、正确
B 、错误
18、二叉树的前序遍历序列中，任意一个结点均处在其子女结点的前面，这种说法____
A 、正确
B 、错误
19、由于二叉树中每个结点的度最大为2，所以二叉树是一种特殊的树，这种说法____
A 、正确
B 、错误
20、如果T2是由有序树T 转换而来的二叉树，那么T 中结点的前序就是T2种结点的___
A 、前序
B 、中序
C 、后序
D 、以上都不是 21、如果T2是由有序树T 转换而来的二叉树，那么T 中结点的后序就是T2种结点的___
A 、前序
B 、中序
C 、后序
D 、以上都不是 22、在以非空二叉树的中序遍历序列中，根结点的右边_____。
A 、只有右子树上的所有结点
B 、只有右子树上的部分结点
C 、只有左子树上的部分结点
D 、只有左子树上的所有结点
23、任何一棵二叉树的叶结点在先序、中序和后序遍历序列中的相对次序____
A 、不发生改变
B 、发生改变
C 、不能确定
D 、以上都不对 24、对一个满二叉树，m 个树叶，n 个结点，深度为h ，则____。
A 、n=h+m
B 、h+m=2n
C 、m=h-1
D 、n=2 h - 1 25、如下图t1有____个叶结点
二、填空题
1、在线性结构中，第一个结点____前驱结点，其余每个结点有且只有_____个前驱结点；最后一个结点____后续结点，其余每个结点有且只有____个后续结点。
2、在树形结构中，树根结点没有_____结点，其余每个结点有且只有_____个前驱结点；叶子结点没有____后续结点，其余每个结点的后续结点可以_____。
3、线性结构中元素之间存在_____关系，树形结构中元素之间存在_____关系，图形结构中元素之间存在_____关系。
4、算法的五个重要特性是____、____、____、____、____。
5、下列程序段的时间复杂度是_____
i=1;
while(i<=n)
i=i*3;
6、向一个长度为n的顺序表的第i个元素(1<=i<=n+1)之前插入一个元素时，需向后移动___个元素。
7、在一个长度为n的顺序表中删除第i个元素(1<=i<=n)时，需向前移动___个元素。
8、向栈中压入元素的操作是先_______，后_________。
9、对栈进行退栈时的操作是先_______，后_________。
10、在一个循环队列中，队首指针指向队首元素的______位置。
11、从循环队列中删除一个元素时，其操作是先______，后______。
12、在具有n个单元的循环队列中，队满时共有______个元素。
13、设有两个串p和q，求q在p中首次出现的位置的运算称作______。
14、设串s1=’ABCDEFG’,s2=’PQRST’,函数con(x,y)返回x和y串的连接串,subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串,len(s)返回串s的长度，则con(subs(s1,2,len(s2))，subs(s1,len(s2),2))的结果串是______。
15、空串是______，其长度等于____；空格串是_____，其长度等于_____。
16、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为_____。
17、按照二叉树的定义，具有3个结点的二叉树有____种。
18、深度为5的二叉树至多有_____个结点。
19、深度为k的完全二叉树至少有_____个结点，至多有___个结点，若按自上而下，从左到右次序给结点编号（从1开始），则编号最小的叶子结点的编号是_____
三、简答题
1、对于一个栈，给出输入项及其输入顺序A,B,C。试给出全部的可能的输出序列(要
有出入栈的过程分析)。
2、现按中序遍历二叉树的结果为abc，问有多少种不同形态的二叉树可以得到这一遍
历结果，并画出这些二叉树。
3、已知一棵树如图所示，画出其孩子兄弟表示。
4、已知一棵二叉树的中序序列为cbedahgijf，后序序列为cedbhjigfa，画出该二叉树的
先序线索二叉树。
5、画出以数据集{4，5，6，7，10，12，18}为结点权值所构造的哈夫曼树,并计算其
带权路径长度。
(1)、画出二叉树表示；
(2)、写出前序遍历，中序遍历和后序遍历的结果；
(3)、写出结点值c的父结点，其左、右孩子；
(4)、画出把此二叉树还原成森林的图；
7、有一份电文中共使用5个字符：a、b、c、d、e，它们出现的频率依次为4、7、5、
2、9，试画出对应的哈夫曼树(请按左子树根结点的权小于等于右子树根结点的权的
次序构造)，并求出每个字符的哈夫曼编码。
数据结构实验报告 一．题目要求 1）编程实现二叉排序树，包括生成、插入，删除； 2）对二叉排序树进行先根、中根、和后根非递归遍历； 3）每次对树的修改操作和遍历操作的显示结果都需要在屏幕上用树的形状表示出来。 4）分别用二叉排序树和数组去存储一个班(50人以上)的成员信息(至少包括学号、姓名、成绩3项),对比查找效率，并说明在什么情况下二叉排序树效率高,为什么? 二．解决方案 对于前三个题目要求，我们用一个程序实现代码如下 #include 第 1 章 绪 论 (2005-07-14) - 第 1 章 绪 论 课后习题讲解 1. 填空 ⑴（ ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 【解答】数据元素 ⑵（ ）是数据的最小单位，（ ）是讨论数据结构时涉及的最小数据单位。 【解答】数据项，数据元素 【分析】数据结构指的是数据元素以及数据元素之间的关系。 ⑶ 从逻辑关系上讲，数据结构主要分为（ ）、（ ）、（ ）和（ ）。 【解答】集合，线性结构，树结构，图结构 ⑷ 数据的存储结构主要有（ ）和（ ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ ）和（）。 【解答】顺序存储结构，链接存储结构，数据元素，数据元素之间的关系 ⑸ 算法具有五个特性，分别是（ ）、（ ）、（ ）、（ ）、（ ）。 【解答】有零个或多个输入，有一个或多个输出，有穷性，确定性，可行性 ⑹ 算法的描述方法通常有（ ）、（ ）、（ ）和（ ）四种，其中，（ ）被称为算法语言。 【解答】自然语言，程序设计语言，流程图，伪代码，伪代码 ⑺ 在一般情况下，一个算法的时间复杂度是（ ）的函数。 【解答】问题规模 ⑻ 设待处理问题的规模为n，若一个算法的时间复杂度为一个常数，则表示成数量级的形式为（ ），若为 n*log25n，则表示成数量级的形式为（ ）。 【解答】Ο(1)，Ο(nlog2n) 【分析】用大O记号表示算法的时间复杂度，需要将低次幂去掉，将最高次幂的系数去掉。 2. 选择题 ⑴ 顺序存储结构中数据元素之间的逻辑关系是由（ ）表示的，链接存储结构中的数据元素之间的逻辑关系是由（ ）表示的。 A 线性结构 B 非线性结构 C 存储位置 D 指针 【解答】C，D 【分析】顺序存储结构就是用一维数组存储数据结构中的数据元素，其逻辑关系由存储位置（即元素在数组中的下标）表示；链接存储结构中一个数据元素对应链表中的一个结点，元素之间的逻辑关系由结点中的指针表示。 ⑵ 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是（ ）。 A 树 B 图 C 线性表 D 集合 【解答】B 【分析】将丈夫、妻子和子女分别作为数据元素，根据题意画出逻辑结构图。 ⑶ 算法指的是（ ）。 A 对特定问题求解步骤的一种描述，是指令的有限序列。 B 计算机程序 C 解决问题的计算方法 D 数据处理 【解答】A 【分析】计算机程序是对算法的具体实现；简单地说，算法是解决问题的方法；数据处理是通过算法完成的。所以，只有A是算法的准确定义。 ⑷ 下面（ ）不是算法所必须具备的特性。 A 有穷性 B 确切性 C 高效性 D 可行性 【解答】C 【分析】高效性是好算法应具备的特性。 ⑸ 算法分析的目的是（ ），算法分析的两个主要方面是（ ）。 A 找出数据结构的合理性 B 研究算法中输入和输出的关系 C 分析算法的效率以求改进 D 分析算法的易读性和文档性 E 空间性能和时间性能 F 正确性和简明性 G 可读性和文档性 H 数据复杂性和程序复杂性 页眉内容 1 第1章 绪论 1.1 简述下列术语：数据，数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解：数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合，是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 填空题： 1.常见的数据结构有__结构，_____结构，____结构等三种。 2.常见的存储结构有_________结构，______结构等两种。 3.数据的基本单位是____，它在计算机中是作为一个整体来处理的。 4.数据结构中的结构是指数据间的逻辑关系，常见的结构可分为两大类，______和_____。 5.《数据结构》课程讨论的主要内容是数据的逻辑结构、存储结构和________。 1.2设有数据结构(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.3设有以下三个函数： ()1000 2124++=n n n f ，()3450015n n n g +=，()n n n n h log 5005.3+= 请判断以下断言正确与否： (1) f(n)是O(g(n)) (2) h(n)是O(f(n)) (3) g(n)是O(h(n)) (4) h(n)是O(n 3.5) (5) h(n)是O(nlogn) 解：(1)对 (2)错 (3)错 (4)对 (5)错 数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s 一，实验题目 实验十一：图实验 采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径。 二，问题分析 本程序要求采用邻接表存储有向图，设计算法判断任意两个顶点间手否存在路径，完成这些操作需要解决的关键问题是：用邻接表的形式存储有向图并输出该邻接表。用一个函数实现判断任意两点间是否存在路径。 1，数据的输入形式和输入值的范围：输入的图的结点均为整型。 2，结果的输出形式：输出的是两结点间是否存在路径的情况。 3，测试数据：输入的图的结点个数为：4 输入的图的边得个数为：3 边的信息为：1 2，2 3，3 1 三，概要设计 （1）为了实现上述程序的功能，需要： A，用邻接表的方式构建图 B，深度优先遍历该图的结点 C，判断任意两结点间是否存在路径 （2）本程序包含6个函数： a，主函数main（） b，用邻接表建立图函数create_adjlistgraph() c，深度优先搜索遍历函数dfs() d，初始化遍历数组并判断有无通路函数dfs_trave() e，输出邻接表函数print() f，释放邻接表结点空间函数freealgraph() 各函数间关系如右图所示： 四，详细设计 （1）邻接表中的结点类型定义： typedef struct arcnode{ int adjvex; arcnode *nextarc; }arcnode; （2）邻接表中头结点的类型定义： typedef struct{ char vexdata; arcnode *firstarc; }adjlist; （3）邻接表类型定义： typedef struct{ adjlist vextices[max]; int vexnum,arcnum; }algraph; （4）深度优先搜索遍历函数伪代码： int dfs(algraph *alg,int i,int n){ arcnode *p; visited[i]=1; p=alg->vextices[i].firstarc; while(p!=NULL) { if(visited[p->adjvex]==0){ if(p->adjvex==n) {flag=1; } dfs(alg,p->adjvex,n); if(flag==1) return 1; } p=p->nextarc; } return 0; } （5）初始化遍历数组并判断有无通路函数伪代码： void dfs_trave(algraph *alg,int x,int y){ int i; for(i=0;i<=alg->vexnum;i++) visited[i]=0; dfs(alg,x,y); } 五，源代码 #include "stdio.h" #include "stdlib.h" #include "malloc.h" #define max 100 typedef struct arcnode{ //定义邻接表中的结点类型 int adjvex; //定点信息 arcnode *nextarc; //指向下一个结点的指针nextarc }arcnode; typedef struct{ //定义邻接表中头结点的类型 char vexdata; //头结点的序号 arcnode *firstarc; //定义一个arcnode型指针指向头结点所对应的下一个结点}adjlist; typedef struct{ //定义邻接表类型 adjlist vextices[max]; //定义表头结点数组 江南大学现代远程教育第一阶段练习题及答案 考试科目:《数据结构》第一章至第四章（总分100分） ______________学习中心（教学点）批次：层次： 专业：学号：身份证号： 姓名：得分： 一、选择题（每题3分，共30分） 1、在树形结构中，数据元素间存在（）的关系。 Ａ、一对一Ｂ、一对多Ｃ、多对多Ｄ、除同属一个集合外别无关系 2、下列说法中错误的是（）。 Ａ、数据对象是数据的子集 Ｂ、数据元素间关系在计算机中的映象即为数据的存储结构 Ｃ、非顺序映象的特点是借助指示元素存储地址的指针来表示数据元素间逻辑关系 Ｄ、抽象数据类型指一个数学模型及定义在该模型上的一组操作 3、下列不属算法特性的是（）。 Ａ、有穷性Ｂ、确定性Ｃ、零或多个输入Ｄ、健壮性 4、在长为n的顺序表中删除一个数据元素，平均需移动（）个数据元素。 Ａ、n Ｂ、n-1 Ｃ、n/2 Ｄ、(n-1)/2 5、若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。 Ａ、顺序表Ｂ、双链表Ｃ、带头结点的双向循环链表Ｄ、单循环链表 6、在一个可存放n个数据元素的顺序栈中，假设以高地址端为栈底，以top为栈顶指针，当向栈中压入一个数据元素时，top的变化是（）。 Ａ、不变Ｂ、top=n Ｃ、top++ Ｄ、top-- 7、设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则删除一个结点的操作是（）。 Ａ、rear=front->next Ｂ、rear=rear->next Ｃ、front=front->next Ｄ、front=rear->next 8、判定一个栈顶指针为S且不带头结点的链栈为空栈的条件是（）。 Ａ、S Ｂ、S->next Ｃ、S->next==NULL Ｄ、!S 9、设在一不带头结点的链队列中，front和rear分别为其队头和队尾指针，则判定该队中只有一个结点的条件是（）。 Ａ、front->next Ｂ、rear->next Ｃ、front==rear Ｄ、front!=rear 10、串的长度是指（）。 第1章绪论 一、选择题 1. 算法的计算量的大小称为计算的（）。 A．效率 B. 复杂性 C. 现实性 D. 难度 2. 算法的时间复杂度取决于（） A．问题的规模 B. 待处理数据的初态 C. A和B 3.计算机算法指的是（1），它必须具备（2）这三个特性。 (1) A．计算方法 B. 排序方法 C. 解决问题的步骤序列 D. 调度方法 (2) A．可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C. 确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 4．一个算法应该是（） A．程序 B．问题求解步骤的描述 C．要满足五个基本特性 D．A和C. 5. 下面关于算法说法错误的是（） A．算法最终必须由计算机程序实现 B.为解决某问题的算法同为该问题编写的程序含义是相同的 C. 算法的可行性是指指令不能有二义性 D. 以上几个都是错误的 6. 下面说法错误的是（）【南京理工大学 2000 一、2 （1.5分）】 (1）算法原地工作的含义是指不需要任何额外的辅助空间 （2）在相同的规模n下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法 （3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界 （4）同一个算法，实现语言的级别越高，执行效率就越低 A．(1) B.(1),(2) C.(1),(4) D.(3) 7．从逻辑上可以把数据结构分为（）两大类。【武汉交通科技大学 1996 一、4（2分）】A．动态结构、静态结构 B．顺序结构、链式结构 C．线性结构、非线性结构 D．初等结构、构造型结构 8．以下与数据的存储结构无关的术语是（）。【北方交通大学 2000 二、1（2分）】A．循环队列 B. 链表 C. 哈希表 D. 栈 9．以下数据结构中，哪一个是线性结构（）？【北方交通大学 2001 一、1（2分）】A．广义表 B. 二叉树 C. 稀疏矩阵 D. 串 10．以下那一个术语与数据的存储结构无关？（）【北方交通大学 2001 一、2（2分）】A．栈 B. 哈希表 C. 线索树 D. 双向链表 11．在下面的程序段中，对x的赋值语句的频度为（）【北京工商大学 2001 一、10（3分）】 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为正整数，则最后一行的语句频度在最坏情况下是（） 数据结构实验---图的储存与遍历 学号： 姓名： 实验日期： 2016.1.7 实验名称： 图的存贮与遍历 一、实验目的 掌握图这种复杂的非线性结构的邻接矩阵和邻接表的存储表示，以及在此两种常用存储方式下深度优先遍历(DFS)和广度优先遍历(BFS)操作的实现。 二、实验内容与实验步骤 题目1：对以邻接矩阵为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接矩阵为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接矩阵表示，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 题目2：对以邻接表为存储结构的图进行DFS 和BFS 遍历 问题描述：以邻接表为图的存储结构，实现图的DFS 和BFS 遍历。 基本要求：建立一个图的邻接表存贮，输出顶点的一种DFS 和BFS 序列。 测试数据：如图所示 V0 V1 V2 V3 V4 三、附录： 在此贴上调试好的程序。 #include #define M 100 typedef struct node { char vex[M][2]; int edge[M ][ M ]; int n,e; }Graph; int visited[M]; Graph *Create_Graph() { Graph *GA; int i,j,k,w; GA=(Graph*)malloc(sizeof(Graph)); printf ("请输入矩阵的顶点数和边数(用逗号隔开)：\n"); scanf("%d,%d",&GA->n,&GA->e); printf ("请输入矩阵顶点信息：\n"); for(i = 0;i 第一章习题 一、问答题 1.什么是数据结构？ 2.叙述四类基本数据结构的名称与含义。 3.叙述算法的定义与特性。 4.叙述算法的时间复杂度。 5.叙述数据类型的概念。 6.叙述线性结构与非线性结构的差别。 7.叙述面向对象程序设计语言的特点。 8.在面向对象程序设计中，类的作用是什么？ 9.叙述参数传递的主要方式及特点。 10.叙述抽象数据类型的概念。 二、判断题（在各题后填写“√”或“×”） 1.线性结构只能用顺序结构来存放，非线性结构只能用非顺序结构来存放。（） 2.算法就是程序。（） 3.在高级语言（如C或 PASCAL）中，指针类型是原子类型。（） 三、计算下列程序段中X=X+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 四、试编写算法，求一元多项式P n (x)=a +a 1 x+a 2 x2+a 3 x3+…a n x n的值P n (x )，并确定算法中的每 一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用 求幂函数。注意：本题中的输入a i (i=0,1,…,n),x和n，输出为P n (x )。通常算法的输入和输 出可采用下列两种方式之一： （1）通过参数表中的参数显式传递。 （2）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。 实习题 设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减法、乘法、除法，以及求有理数的分子、分母。 第一章答案 1.3计算下列程序中x=x+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】x=x+1的语句频度为： T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6 1.4试编写算法，求p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执 行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法（1）通过参数表中的参数显式传递（2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 2013-2014学年二学期数据结构期末考试模拟试卷(1~6卷) 一、应用题(3小题，共24分) 1已知某字符串S中共有8种字符，各种字符分别出现2次、1次、4次、5次、7次、3 次、4次和9次，对该字符串用［0,1］进行前缀编码，问该字符串的编码至少有多少位。 【解答】以各字符出现的次数作为叶子结点的权值构造的哈夫曼编码树如图所示。其带权路 径长度=2X 5+1X 5+3X 4+5X 3+9X 2+4X 3+4X 3+7X 2=98，所以，该字符串的编码长度至少为98位。 2.已知关键码序列为(Ja n, Feb, Mar, Apr, May, Jun, Jul, Aug, Sep, Oct, Nov, Dec), 散列表的地址空间为0~16,设散列函数为H(x)= ［i/2」(取下整数)，其中i为关键码 中第一个字母在字母表中的序号，采用链地址法处理冲突构造散列表，并求等概率情况下查找成功的平均查找长度。 【解答】H(Ja n)=10/2=5, H(Feb)=6/2=3, H(Mar)=13/2=6, H(Apr)=1/2=0 H(May)=13/2=6, H(Ju n)=10/25, H(Jul)=10/25, H(Aug)=1/2=0 H(Sep)=19/2=8, H(Oct) =15/2=7, H(Nov) =14/2=7, H(Dec) =4/2=2 采用链地址法处理冲突，得到的开散列表如下： 平均查找长度=(1 X 7+2X 4+3X 1)/12=18/12 3.分析下面各程序段的时间复杂度 (1)s1(int n) { int p=1,s=0; for (i=1;iv=n;i++) { p*=i;s+=p; } return(s); } ——0(n) (2)s2(int n) x=0;y=0; For (k=1;kv=n;k++) x++; For (i=1;iv=n;i++) For (j=1;jv=n;j++) y++; ——0(n) 1?下述算法的功能是什么？ ListNode *Demo l(LinkList L P ListNode *p) ("L是有头结蛊的单链表 ListNodc *q=L->rLCxt P (1) V ‘V … 」(1 )返回结点*p的直接前趋结点地址。 q=q->nest; if (q) return q, else ?ro< #*p not in L"); I ⑵ i/oid Demo2(LisINode *p ,ListNode +q) 〔//p t*q*8S 表中的 两个结点 (2)交换结点*p和结点*q (p和q的值不变)。 DataTypetemp; temp=p->data, p->data=q->data; q-x^ata^emp, 1.对给定的一组权值W=( 5, 2, 9, 11, 8, 3, 7),试构造相应的哈夫曼树，并计算它的带权路径长度。【解答】构造的哈夫曼树如图所示。 邻接矩阵的实现 1. 实验目的 （1）掌握图的逻辑结构 （2）掌握图的邻接矩阵的存储结构 （3）验证图的邻接矩阵存储及其遍历操作的实现2. 实验内容 （1）建立无向图的邻接矩阵存储 （2）进行深度优先遍历 （3）进行广度优先遍历3．设计与编码MGraph.h #ifndef MGraph_H #define MGraph_H const int MaxSize = 10; template int vertexNum, arcNum; }; #endif MGraph.cpp #include 第一章习题 一．填空题 １、数据结构被形式地定义为（D, R），其中D是的有限集合，R是D上的有限集合。 ２、数据结构按逻辑结构可分为两大类，它们分别是和。 ３、线性结构中元素之间存在关系，树形结构中元素之间存在关系，图形结构中元素之间存在关系。 ４、一个算法的效率可分为效率和效率。 ５、简单地说，一个算法所进行的计算次数的多少称为，一个算法所需要辅助存储空间的多少称之为。 ６、根据数据元素之间关系的不同特性，通常有四类基本结构，它们是集合、、、。 二．选择题 １、算法分析的目的是（） A、找出数据结构的合理性 B、研究算法中的输入和输出的关系 C、分析算法的效率以求改进 D、分析算法的易懂性和文档性 ２、算法分析的两个主要方面是（） A、空间复杂性和时间复杂性 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 ３、计算机算法指的是（） A、计算方法 B、排序方法 C、解决问题的有限运算序列 D、调度方法 ４、计算机算法必须具备输入、输出和（）等5个特性。 A、可行性、可移植性和可扩充性 B、可行性、确定性和有穷性 C、确定性、有穷性和稳定性 D、易读性、稳定性和安全性 ５、数据元素是数据的基本单位，其内（）数据项。 A、只能包含一个 B、不包含 C、可以包含多个 D、必须包含多个 ６、逻辑关系是指数据元素间的（） Ａ、类型Ｂ、存储方式Ｃ、结构Ｄ、数据项 ７、数据结构有（）种基本逻辑结构。 A、１ B、２ C、３ D、４ ８、下列四种基本的逻辑结构中，数据元素之间关系最弱的是（）。 A、集合 B、线性结构 C、树形结构 D、图状结构 ９、一个存储结构点存储一个（）。 A、数据项 B、数据元素 C、数据结构 D、数据类型 10、某算法的时间复杂度为O(2n)，表明该算法的（） A、问题规模是2n B、执行时间等于2n C、执行时间与2n成正比 D、问题规模与2n成正比 11、算法执行时间一般与（）无关。 A、问题规模大小 B、计算机的档次 C、程序设计语言的种类或版本 D、算法设计者的 水平 12、算法分析的主要任务是分析算法（） A、是否具有较好的可读性 B、是否存在语法错误 C、功能是否符合设计要求 D、执 行时间和问题规模之间的关系。 13、下列时间复杂度中最坏的是（） 第三章栈和队列 一、判断题： 1、栈和队列都是限制存取点的线性结构(易) 2、栈和队列是两种重要的线性结构。(易) 3、带头结点的单链表形式的队列，头指针F指向队列的头结点，尾指针R指向队列的最后一个结点(易) 4、在对不带头结点的链队列作出队操作时，不会改变头指针的值。(易) 答案：1-4 √√×× 二、选择题： 1、一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是C____。 A、 edcba B、 decba C、 dceab D、 abcde 2、若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi 为_C___。 A、 i B、 n=i C、 n-i+1 D、不确定 3、栈结构通常采用的两种存储结构是_A___。 A、顺序存储结构和链式存储结构 B、散列方式和索引方式 C、链表存储结构和数组 D、线性存储结构和非线性存储结构 4、判定一个顺序栈ST（最多元素为m0）为空的条件是_B___。A、top !=0 B、top= =0 C、top !=m0 D、top= =m0-1 5、判定一个顺序栈ST（最多元素为m0）为栈满的条件是D。A、top！=0 B、top= =0 C、top！=m0 D、top= =m0-1 6、队列操作的原则是( A ) A、先进先出 B、后进先出 C、只能进行插入 D、只能进行删 除 7、向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__ _C_。(不带空的头结点) (易) A、HS—＞next=s;9 B、s—＞next= HS—＞next; HS—＞next=s; C、s—＞next= HS; HS=s; D、s—＞next= HS; HS= HS—＞next 实验1 (C语言补充实验) 有顺序表A和B,其元素值均按从小到大的升序排列，要求将它们合并成一 个顺序表C,且C的元素也是从小到大的升序排列。 #include 求A QB #include 《数据结构》第一章练习题 1、单项选择题 1.1数据结构是一门非数值计算的程序设计问题中计算机的（ ）以及它们之间的（ ）和运算等的学科。 ①A 数据元素 B 计算方法 C 逻辑存储 D 数据映像 ②A 结构 B 关系 C 运算 D 算法 1.2数据结构被形式的定义为（K,R ），其中K 是（ ）的有限集，R 是K 上的（ ）有限集。 ①A 算法B 数据元素C 数据操作D 逻辑结构 ②A 操作B 映像C 存储D 关系 1.3在数据结构中，从逻辑上可以把数据结构分为（ ）。 A 动态结构和静态结构 B 紧凑结构和非紧凑结构 C 线性结构和非线性结构 D 内部结构和外部结构 1.4数据结构在计算机内存中的表示是指（ ）。 A 数据的存储结构 B 数据结构 C 数据的逻辑结构 D 数据元素之间的关系 1.5在数据结构中，与所使用的计算机无关的是数据的（ ）结构。 A 逻辑 B 存储 C 逻辑和存储 D 物理 1.6算法分析的目的是（)，算法分析的两个主要方面是（ ）。①A 找出数据结构的合理性 B 研究算法中输入与输出的关系 C 分析算法效率以求改进 D 分析算法的易懂性和文档性 ②A 空间复杂度和时间复杂度 B 正确性和简明性 C 可读性和文档性 D 数据复杂性和程序复杂性 1.7计算机算法是指（ ），它必须具备输入、输出和（ ）等5个特性。 ①A 计算方法 B 排序方法 C 解决问题的有限运算序列 D 调度方法 ②A 可行性、可移植性和可扩充性 B 可行性、确定性和有穷性 C 确定性、有穷性和稳定性 D 易读性、稳定性和安全性 1.8在以下的叙述中，正确的是（ ）。 A 线性表和线性存储结构优于链表存储结构 B 二维数组是其数据元素为线性表的线性表 C 栈的操作方式是先进先出 D 队列的操作方式是先进后出 1.9在决定选择何种存储结构时，一般不考虑（ ）。 、管路敷设技术通过管线不仅可以解决吊顶层配置不规范高中资料试卷问题，而且可保障各类管路习题到位。在管路敷设过程中，要加强看护关于管路高中资料试卷连接管口处理高中资料试卷弯扁度固定盒位置保护层防腐跨接地线弯曲半径标等，要求技术交底。管线敷设技术中包含线槽、管架等多项方式，为解决高中语文电气课件中管壁薄、接口不严等问题，合理利用管线敷设技术。线缆敷设原则：在分线盒处，当不同电压回路交叉时，应采用金属隔板进行隔开处理；同一线槽内强电回路须同时切断习题电源，线缆敷设完毕，要进行检查和检测处理。、电气课件中调试对全部高中资料试卷电气设备，在安装过程中以及安装结束后进行 高中资料试卷调整试验；通电检查所有设备高中资料试卷相互作用与相互关系，根据生产工艺高中资料试卷要求，对电气设备进行空载与带负荷下高中资料试卷调控试验；对设备进行调整使其在正常工况下与过度工作下都可以正常工作；对于继电保护进行整核对定值，审核与校对图纸，编写复杂设备与装置高中资料试卷调试方案，编写重要设备高中资料试卷试验方案以及系统启动方案；对整套启动过程中高中资料试卷电气设备进行调试工作并且进行过关运行高中资料试卷技术指导。对于调试过程中高中资料试卷技术问题，作为调试人员，需要在事前掌握图纸资料、设备制造厂家出具高中资料试卷试验报告与相关技术资料，并且了解现场设备高中资料试卷布置情况与有关高中资料试卷电气系统接线等情况 ，然后根据规范与规程规定，制定设备调试高中资料试卷方案。 、电气设备调试高中资料试卷技术电力保护装置调试技术，电力保护高中资料试卷配置技术是指机组在进行继电保护高中资料试卷总体配置时，需要在最大限度内来确保机组高中资料试卷安全，并且尽可能地缩小故障高中资料试卷破坏范围，或者对某些异常高中资料试卷工况进行自动处理，尤其要避免错误高中资料试卷保护装置动作，并且拒绝动作，来避免不必要高中资料试卷突然停机。因此，电力高中资料试卷保护装置调试技术，要求电力保护装置做到准确灵活。对于差动保护装置高中资料试卷调试技术是指发电机一变压器组在发生内部故障时，需要进行外部电源高中资料试卷切除从而采用高中资料试卷主要保护装置。 数据结构练习题 第一部分绪论 一、单选题 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 第1章绪论 2.(1)×(2)×(3)√ 3.（1）A（2）C（3）C 5.计算下列程序中x=x+1的语句频度 for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 【解答】x=x+1的语句频度为： T(n)=1+(1+2)+（1+2+3）+……+（1+2+……+n）=n(n+1)(n+2)/6 6.编写算法，求一元多项式p n(x)=a0+a1x+a2x2+…….+a n x n的值p n(x0),并确定算法中每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入为a i(i=0,1,…n)、x和n,输出为P n(x0)。算法的输入和输出采用下列方法 （1）通过参数表中的参数显式传递 （2）通过全局变量隐式传递。讨论两种方法的优缺点，并在算法中以你认为较好的一种实现输入输出。 【解答】 （1）通过参数表中的参数显式传递 优点：当没有调用函数时，不占用内存，调用结束后形参被释放，实参维持，函数通用性强，移置性强。 缺点：形参须与实参对应，且返回值数量有限。 （2）通过全局变量隐式传递 优点：减少实参与形参的个数，从而减少内存空间以及传递数据时的时间消耗 缺点：函数通用性降低，移植性差 算法如下：通过全局变量隐式传递参数 PolyValue() { int i,n; float x,a[],p; printf(“\nn=”); scanf(“%f”,&n); printf(“\nx=”); scanf(“%f”,&x); for(i=0;i数据结构第一章课后习题与答案
计算机数据结构习题1附答案
数据结构试题库答案
数据结构实验十一：图实验
数据结构第1阶段练习题
数据结构 习题 第一章 绪论
数据结构实验---图的储存与遍历
数据结构课后习题及解析第一章
数据结构题库教材
数据结构实验报告图实验
数据结构练习题(第一章)
数据结构相关题库及答案
数据结构实验
数据结构第一章练习题
数据结构练习题及参考答案
最全数据结构课后习题答案(耿国华版[1]
相关主题
文本预览