计算机科学与技术专业数据结构习题 内附答案
第一章 绪论
一、填空题
1. 数据是描述客观事物的数、字符以及所有能输入到计算机且能够被计算机程序加工处理的符号集合。_________是数据的基本单位;___________是数据的最小单位。通常被计算机加工处理的数据不是孤立无关的,而是彼此之间存在着某种联系,将这种数据间的联系称为________。
2. 数据结构进行形式化定义时,可以从逻辑上认为数据结构DS是_________的集合D和D上_________的集合R所构成的二元组:DS=(D,R)。
3. 已知某数据结构的二元组形式表示为:A=(D,R),D={01,02,03,04,05,06,07,08,09},R={r},r={<01,02>,<01,03>,<01,04>,<02,05>,<02,06>,<03,07>,<03,08>,<03,09>}。则此数据结构属于_____________结构。
4. 一个算法的时间复杂度通常用问题规模大小的函数来表示,当一个算法的时间复杂度与问题规模n大小无关时,则表示为__________;成正比关系时,则表示为___________;成对数关系时,则表示为___________;成平方关系时,则表示为__________。
5. 数据结构的逻辑结构包括_____________、树型结构和图型结构三种类型,其中树型结构和图型结构合称为_____________;数据结构的存储结构主要包括____________和____________两种类型。
6. 线性结构的特点是:第一个结点_______前驱结点,其余结点有且仅有_______个前驱结点;最后一个结点_______后继结点,其余每个结点有且仅有_______个后继结点。
7. 树型结构的特点是:根结点没有________结点,其余每个结点有且仅有________个前驱结点;叶子结点_________后继结点,其余结点可以有_________个后继结点。
8. 图型结构的特点是:每个结点可以有_________个前驱结点和后继结点。
9. 程序段for(i=1,s=0;s<n;i++) s=s+i;的时间复杂度为___________。
10. 常见的时间复杂度有常数阶O(1)、对数阶O(log2n)、线性阶O(n)、平方阶O(n2)、线性对数阶O(nlog2n)、立方阶O(n3)、指数阶O(2n)等等,这些数量阶之间的大小关系为__________________________。
二、分析下列用二元组形式表示的数据结构,指出他们分别属于何种类型的数据结构。
1. A=(K,R),其中:K={a,b,c,d,e,f,g,h},R={r},r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,
<f,g>,<g,h>}。
2. B=(K,R),其中:K={a,b,c,d,e,f,g,h},R={r},r={<d,b>,<d,g>,<d,a>,<b,c>,<g,e>,
<g,h>,<e,f>}。
3. C=(K,R),其中:K={ a,b,c,d,e },R={r},r={<a,b>,<b,c>,<c,d>,<d,e>,<e,f>,<a,d>,
<c,f>}。
4. D=(K,R),其中:K={48,25,64,57,82,36,75},R={r1,r2},r1={<25,36>,<36,48>,<48,
57>,<57,64>,<64,75>,<75,82>};r2={<48,25>,<48,64>,<64,57>,<64,82>,<25,36>,<25,75>}。
5. E=(K,R),其中:K={1,2,3,4,5,6,7},R={r},r={<1,2>,<2,1>,<1,4>,<4,1>,<2,
3>,<3,2>,<3,4>,<4,3>,<1,3>,<3,1>}。
三、指出下列各函数的功能并求出其时间复杂度。
1. void prime(int n)
{
int i;
for(i=2;i<=sqrt(n);i++) if (n %i==0) break;
if (i>sqrt(n)) printf(“yes”); else printf(“no”);
}
2. long sum1(int n)
{
数据结构中评价算法的两个重要指标是 9.一个算法具有 5 个特性: 或多个输入...参考答案: 在线性表的链式存储结构中,头指针指链表的指针,若链表有头结点则是...
一个算法具有以下 5 个重要特性: 1) 、有穷性 2) 、确定性 3) 、 可行... 数据结构习题集参考答案 49页 免费 数据结构习题集答案 113页 免费 数据结构...
数据结构复习题及参考答案_工学_高等教育_教育专区...装载因子是散列表的一个重要参数,它反映了散列表的...7.已知一个带权图的顶点集 V 和边集 G 分别为...
数据结构习题集及参考答案... 33页 2财富值 数据结构习题集(含答案) 44页...6.算法的五个重要特性是 ___、 ___、 ___、 ___、 ___。 7.数据结构...
数据结构复习题及参考答案_从业资格考试_资格考试/认证_教育专区。数据结构考试...装载因子是散列表的一个重要参数,它反映了散列表的装满程度。 [ 数据结构第 1...
数据结构习题集答案_C语... 113页 免费 操作系统期末试题选择题... 24页 ...线性结构中元素之间存在 中元素之间存在 关系。 6. 算法的五个重要特性是__ ...
数据结构复习题及答案 涉及数据结构的各各重要知识点 并且解答详细涉及数据结构的各各重要知识点 并且解答详细隐藏>> 第1 章绪 论课后习题讲解 1. 填空 ⑴( ...
2014数据结构习题集答案_工学_高等教育_教育专区。数据结构《数据结构》习题集答案 黄橡丽 2014 年 8 月 第一章-第五章 参考答案一.单选与填空 1. n(n-1...
习题1 参考答案 1 至 8 题答案略。 9.(1)【解】该逻辑结构为线性结构,其图形表示如下: Sun Mon Tue Wed Thu Fri Sat (2)【解】该逻辑结构为树型结构,...
2014数据结构习题集答案_教育学_高等教育_教育专区。《数据结构》习题集答案 2014 年 8 月 第一章-第五章 参考答案 一.单选与填空 1. n(n-1)/2 2.O(...
热门文档