搜档网
当前位置:搜档网 › 数据结构课后习题答案第四章

数据结构课后习题答案第四章

数据结构课后习题答案第四章
数据结构课后习题答案第四章

第四章

一、简述下列每对术语的区别:

空串和空白串;串常量和串变量;主串和子串;静态分配的顺序串和动态分配的顺序串;目标串和模式串;有效位移和无效位移。

答:

●空串是指不包含任何字符的串,它的长度为零。

空白串是指包含一个或多个空格的串,空格也是字符。

●串常量是指在程序中只可引用但不可改变其值的串。

串变量是可以在运行中改变其值的。

●主串和子串是相对的,一个串中任意个连续字符组成的串就是这个串的子串,而包含子串的串就称为主串。

●静态分配的顺序串是指串的存储空间是确定的,即串值空间的大小是静态的,在编译时刻就被确定。

动态分配的顺序串是在编译时不分配串值空间,在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定,也是顺序存储空间)。

●目标串和模式串:在串匹配运算过程中,将主串称为目标串,而将需要匹配的子串称为模式串,两者是相对的。

●有效位移和无效位移:在串定位运算中,模式串从目标的首位开始向右位移,每一次合法位移后如果模式串与目标中相应的字符相同,则这次位移就是有效位移(也就是从此位置开始的匹配成功),反之,若有不相同的字符存在,则此次位移就是无效位移(也就是从此位置开始的匹配失败)。

二、假设有如下的串说明:

char s1[30]="Stocktom,CA", s2[30]="March 5 1999", s3[30], *p;

(1)在执行如下的每个语句后p的值是什么?

p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6');

(2)在执行下列语句后,s3的值是什么?

strcpy(s3,s1); strcat(s3,","); strcat(s3,s2);

(3)调用函数strcmp(s1,s2)的返回值是什么?

(4)调用函数strcmp(&s1[5],"ton")的返回值是什么?

(5)调用函数stlen(strcat(s1,s2))的返回值是什么?

解:

(1) stchr(*s,c)函数的功能是查找字符c在串s中的位置,若找到,则返回该位置,否则返回NULL。

因此:

执行p=stchr(s1,'t');后p的值是指向第一个字符t的位置, 也就是p==&s1[1]。

执行p=strchr(s2,'9');后p的值是指向s2串中第一个9所在的位置,也就是p==&s2[9]。

` 执行p=strchr(s2,'6');之后,p的返回值是NULL。

(2)strcpy函数功能是串拷贝,strcat函数的功能是串联接。所以:

在执行strcpy(s3,s1); 后,s3的值是"Stocktom,CA"

在执行strcat(s3,","); 后,s3的值变成"Stocktom,Ca,"

在执行完strcat(s3,s2);后,s3的值就成了"Stocktom,Ca,March 5,1999"

(3)函数strcmp(串1,串2)的功能是串比较,按串的大小进行比较,返回大于0,等于0或小于0的值以表示串1比串2 大,串1等于串2 ,串1小于串2。因此在调用函数strcmp(s1,s2)后,返回值是大于0的数(字符比较是以ascii码值相比的)

(4)首先,我们要知道&s1[5]是一个地址,当放在函数strcmp中时,它就表示指向以它为首地址的一个字符串,所以在strcmp( &s1[5],"ton")中,前一个字符串值是"tom,CA",用它和"ton"比较,应该是后者更大,所以返回值是小于0的数。

(5)strlen是求串长的函数,我们先将s1,s2联接起来,值是"Stocktom,CAMarch 5,1999",数一数有几个字符?是不是23个(空格也是一个)? 所以返回值是23。三、设有A=' ',B='mule',C='old',D='my',计算下列运算的结果(注:“A+B”是Concat的简写)。

(a)A+B (b)B+A (c)D+C+B (d)SubStr(B,3,2)

(e)SubStr(C,1,0) (f)StrLength(A) (g)StrLength(D) (h)StrIndex(B,D)

(i)StrIndex(C,"d") (j)StrInsert(D,2,C) (k)StrInsert (B,I,A)(l)StrDelete(B,2,2)

(m)StrDelete(B,2,0) (n)StrRep(C,2,2, "k")

【解答】

(a)A+B="#mule"; (b)B+A="mule#"

(c)D+C+B="myoldmule" (d)SubStr(B,3,2)= "le"

(e)SubStr(C,1,0)= " " (f)StrLength(A)=1

(g)StrLength(D)=2 (h)StrIndex(B,D)=0

(i)StrIndex(C, "d")=3 (j)StrInsert(D,2,C)= "myldy"

(k)StrInsert (B,I,A)="m#ule" (l)StrDelete(B,2,2)="me"

(m)StrDelete(B,2,0)="mule" (n)StrRep(C,2,2, "k")="ok" 四、假设有如下的串说明:

char sl[30]="Stocktom,CA",s2[30]= "March 5,1999",s3[30];

(1)调用函数strCmp(s1,s2)的返回值是什么?

(2)调用函数strCmp(&s1[5], "ton")的返回值是什么?

(3)调用函数Strlength(StrConcat(s1,s2))的返回值是什么?

【解答】

(1)正数,表示s1大于s2。

(2)负数,表示“tom,CA”小于“ton”。

(3)23,即为s1与s2连接后的长度。

数据结构试题及答案10套

一、单选题(每题 2 分,共20分) 1. 1.对一个算法的评价,不包括如下(B )方面的内容。 A.健壮性和可读性B.并行性C。正确性D.时空复杂度 2.2.在带有头结点的单链表HL中,要向表头插入一个由指针p指向 的结点,则执行(A ). A. p-〉next=HL->next; HL-〉next=p; B. p-〉next=HL;HL=p; C。p->next=HL; p=HL;D. HL=p; p-〉next=HL; 3.3.对线性表,在下列哪种情况下应当采用链表表示?( B ) A.经常需要随机地存取元素 B。经常需要进行插入和删除操作 C。表中元素需要占据一片连续的存储空间D.表中元素的个数不变 4. 4.一个栈的输入序列为1 2 3,则下列序列中不可能是栈的输出序 列的是( C ) A. 2 3 1 ??? B. 3 2 1 C。 3 1 2 ??? D. 1 23 5. 5.AOV网是一种(D )。 A.有向图B.无向图C.无向无环图D.有向无环图 6.6。采用开放定址法处理散列表的冲突时,其平均查找长度(B)。 A.低于链接法处理冲突B.高于链接法处理冲突C.与链接法处理冲突相同 D。高于二分查找 7.7。若需要利用形参直接访问实参时,应将形参变量说明为(D ) 参数. A。值B。函数 C.指针 D。引用 8.8.在稀疏矩阵的带行指针向量的链接存储中,每个单链表中的结 点都具有相同的( A )。 A。行号 B.列号 C.元素值 D.非零元素个数 9.9.快速排序在最坏情况下的时间复杂度为( D )。 A。O(log 2n) B.O(nlog 2 n) C。0(n) D.0 (n2) 10.10.从二叉搜索树中查找一个元素时,其时间复杂度大致为( C ). A.O(n) B. O(1) C。 O(log 2 n) D. O(n2)二、运算题(每题 6 分,共24分)

《数据结构》课后习题答案

第1章绪论 1.简述下列概念:数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。 答案: 数据:是客观事物的符号表示,指所有能输入到计算机中并被计算机程序处理的符号的总称。如数学计算中用到的整数和实数,文本编辑所用到的字符串,多媒体程序处理的图形、图像、声音、动画等通过特殊编码定义后的数据。 数据元素:是数据的基本单位,在计算机中通常作为一个整体进行考虑和处理。在有些情况下,数据元素也称为元素、结点、记录等。数据元素用于完整地描述一个对象,如一个学生记录,树中棋盘的一个格局(状态)、图中的一个顶点等。 数据项:是组成数据元素的、有独立含义的、不可分割的最小单位。例如,学生基本信息表中的学号、姓名、性别等都是数据项。 数据对象:是性质相同的数据元素的集合,是数据的一个子集。例如:整数数据对象是集合N={0,±1,±2,…},字母字符数据对象是集合C={‘A’,‘B’,…,‘Z’,‘a’,‘b’,…,‘z’},学生基本信息表也可是一个数据对象。 数据结构:是相互之间存在一种或多种特定关系的数据元素的集合。换句话说,数据结构是带“结构”的数据元素的集合,“结构”就是指数据元素之间存在的关系。 逻辑结构:从逻辑关系上描述数据,它与数据的存储无关,是独立于计算机的。因此,数据的逻辑结构可以看作是从具体问题抽象出来的数学模型。 存储结构:数据对象在计算机中的存储表示,也称为物理结构。 抽象数据类型:由用户定义的,表示应用问题的数学模型,以及定义在这个模型上的一组操作的总称。具体包括三部分:数据对象、数据对象上关系的集合和对数据对象的基本操作的集合。 2.试举一个数据结构的例子,叙述其逻辑结构和存储结构两方面的含义和相互关系。 答案: 例如有一张学生基本信息表,包括学生的学号、姓名、性别、籍贯、专业等。每个学生基本信息记录对应一个数据元素,学生记录按顺序号排列,形成了学生基本信息记录的线性序列。对于整个表来说,只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录),其他的结点则各有一个也只有一个直接前趋和直接后继。学生记录之间的这种关系就确定了学生表的逻辑结构,即线性结构。 这些学生记录在计算机中的存储表示就是存储结构。如果用连续的存储单元(如用数组表示)来存放这些记录,则称为顺序存储结构;如果存储单元不连续,而是随机存放各个记录,然后用指针进行链接,则称为链式存储结构。 即相同的逻辑结构,可以对应不同的存储结构。 3.简述逻辑结构的四种基本关系并画出它们的关系图。 答案: (1)集合结构 数据元素之间除了“属于同一集合”的关系外,别无其他关系。例如,确定一名学生是否为班级成员,只需将班级看做一个集合结构。 (2)线性结构 数据元素之间存在一对一的关系。例如,将学生信息数据按照其入学报到的时间先后顺序进行排列,将组成一个线性结构。 (3)树结构

数据结构试卷带答案

数据结构试卷(一) 一、选择题(20分) 1.组成数据的基本单位是( 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的度数数为(8.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) 希尔排序 二、填空题(30分) 1.设顺序循环队列Q[0:m-1]的队头指针和队尾指针分别为F和R,其中队头指针F指向当前队头元 素的前一个位置,队尾指针R指向当前队尾元素所在的位置,则出队列的语句为F =____________;。 2.设线性表中有n个数据元素,则在顺序存储结构上实现顺序查找的平均时间复杂度为___________, 在链式存储结构上实现顺序查找的平均时间复杂度为___________。 3.设一棵二叉树中有n个结点,则当用二叉链表作为其存储结构时,该二叉链表中共有________个指 针域,__________个空指针域。 4.设指针变量p指向单链表中结点A,指针变量s指向被插入的结点B,则在结点A的后面插入结点 B的操作序列为______________________________________。 5.设无向图G中有n个顶点和e条边,则其对应的邻接表中有_________个表头结点和_________个表 结点。 6.设无向图G中有n个顶点e条边,所有顶点的度数之和为m,则e和m有______关系。 7.设一棵二叉树的前序遍历序列和中序遍历序列均为ABC,则该二叉树的后序遍历序列为__________。 8.设一棵完全二叉树中有21个结点,如果按照从上到下、从左到右的顺序从1开始顺序编号,则编 号为8的双亲结点的编号是___________,编号为8的左孩子结点的编号是_____________。 9.下列程序段的功能实现子串t在主串s中位置的算法,要求在下划线处填上正确语句。 int index(char s[ ], char t[ ]) { i=j=0; while(i

数据结构期末考试试题及答案

《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 单项选择题1、C 2、D 3、A 4、D 5、C 6、D 7、A 8、B 9、C 10、C 、 1. 对于一个算法,当输入非法数据时,也要能作出相应的处理,这种要求称为 (c )。 (A)、正确性但).可行性(C).健壮性 2 ?设S为C语言的语句,计算机执行下面算法时, for(i=n-1 ; i>=0; i--) for(j=0 ; jvi; j++) (A)、n2(B). O(nlgn) 3?折半查找法适用于( a (D). 输入性 算法的时间复杂度为(d S; (C). O(n) (D). )。 O(n2) (A)、有序顺序表(B)、有序单链表 (C)、有序顺序表和有序单链表都可以 4 .顺序存储结构的优势是( d )。 (A)、利于插入操作(B)、利于删除操作 (C)、利于顺序访问(D)、利于随机访问 5. 深度为k的完全二叉树,其叶子结点必在第 (A)、k-1 ( B)、k (C)、k-1 和 6. 具有60个结点的二叉树,其叶子结点有 (A)、11 ( B)、13 ( C)、48 (D)、无限制 c )层上。 (D)、1 至 k 12个,则度过1 (D)、37 k 的结点数为( 7 .图的Depth-First Search(DFS) 遍历思想实际上是二叉树( 法的推广。 (A)、先序(B)、中序(C)、后序(D)、层序 8.在下列链队列Q中,元素a出队的操作序列为( a )遍历方 front (A )、 (B )、 (C)、 (D )、p=Q.front->next; p->next= Q.front->next; p=Q.front->next; Q.front->next=p->next; p=Q.rear->next; p->next= Q.rear->next; p=Q->next; Q->next=p->next; 9. Huffman树的带权路径长度WPL等于( (A)、除根结点之外的所有结点权值之和(C)、各叶子结点的带权路径长度之和(B) 、 ) 所有结点权值之和 根结点的值 b ■

严蔚敏版数据结构课后习题答案-完整版

第1章绪论 1.1 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解:数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合,是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。 存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。 抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解:抽象数据类型包含一般数据类型的概念,但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义,直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据

类型通常由编程者定义,包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时,要求只定义到数据的逻辑结构和操作说明,不考虑数据的存储结构和操作的具体实现,这样抽象层次更高,更能为其他用户提供良好的使用接口。 1.3 设有数据结构(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.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。 解: ADT Complex{ 数据对象:D={r,i|r,i 为实数} 数据关系:R={} 基本操作: InitComplex(&C,re,im) 操作结果:构造一个复数C ,其实部和虚部分别为re 和im DestroyCmoplex(&C)

数据结构试卷带答案

数据结构试卷带答案 问题说明 部分题目或答案有问题,现将已经发现的公布如下,同学在作这些模拟题的时候应着重做题方法的理解,遇到问题以教材或课件为准,不确定的地方可找同学商量或问我 (1)试卷1第一套填空题第1题,试卷1第2套选择题第3题关于循环队列队头指针和队尾指针的约定与教材不一致,以教材或课件为准,实际上front指向的是队头元素,rear指向当前尚未被占用的第一个队列空间,队慢或队空的判定条件及入队/出队等操作具体可参考课件或教材 (2)试卷1第一套应用题第5题,不声明邻接点顺序时默认编号最小的邻接点为第一邻接点,该图的深度优先遍历序列为123465,答案错。此外,当给定邻接表时则邻接点顺序按照邻接表中的前后顺序确定,如试卷1第二套填空题第8题 (3)试卷1第五套应用题第4题,两种方法处理冲突的方法下所求ASL值相等都为7/6 (4)试卷1第五套填空题第8题答案给出的是小顶堆需满足的条件,大顶堆满足ki>=k2i p->rlink->llink=p->llink;此外,注意课堂中讲的指针名和操作方法 (12)第4套填空题第6题答案错,设哈夫曼树中共有99个结点,则该树中有____50_____个叶子结点;若采用二叉链表作为存储结构,则该树中有__100___个空指针域。

(13)第5套选择第8题答案应为A:设连通图G中的边集E={(a,b),(a,e),(a,c),(b,e),(e,d),(d,f),(f,c)},则从顶点a出发可以得到一种深度优先遍历的顶点序列为(A) abedfc (14)第5套应用题第3题题目未指明查找方法,没法作 (15)第6套选择第5题应选B,实际是任意结点至多只有一个孩子:设二叉树的先序遍历序列和后序遍历序列正好相反,则该二叉树满足的条件是(B) 高度等于其结点数 (16)第7套填空1题问题本身错,设指针变量p指向双向链表中的结点A,指针变量s指向被插入的结点X,则在结点A的后面插入结点X的操作序列为____s->left_____=p;s->right=p->right;___p->right_______=s;s->right->left=s;(设结点中的两个指针域分别为left和right)。(17)第8套填空题第8题答案错 (18)第7套选择第3题题目错,应以60为基准关键字,答案为C.设一组初始记录关键字序列为(60,80,55,40,42,85),则以第一个关键字60为基准而得到的一趟快速排序结果是()。 (C) 42,40,55,60,80,85 (17)第6套填空9题.快速排序算法的空间复杂度平均情况下为_O(logn)_,最坏的情况下为_O(n)_。(18)第9套填空第3题,题目说循环队列有m个元素实际指循环队列总长为m,此外,该题关于队头和队尾指针的约定不同于教材 (19)第9套填空第4题答案错,9个元素冒泡排序,第一趟比较次数为8,最多8趟

数据结构试卷和答案

《数据结构》试题参考答案 (开卷) (电信系本科2001级 2002年12月) 一、回答下列问题 (每题4分,共36分) 1. 某完全二叉树共有15381个结点,请问其树叶有多少个? 答:n2=?n/2?=?15381/2?=7691(个) 2. 假设有二维数组A 7×9,每个元素用相邻的6个字节存储,存储器按字节编址。已知A 的起始存储位置(基地址)为1000,末尾元素A[6][8]的第一个字节地址为多少?若按列存储时,元素A[4][7]的第一个字节地址为多少? 答:① 末尾元素A[6][8]的第一个字节地址=1000+(7行×9列—1)×6B =1000+62×6=1372 ②按列存储时,元素A[4][7]的第一个字节地址=1000+(7列×7行+4)×6B =1000+53×6=1318 3. 在KMP 算法中,已知模式串为ADABBADADA ,请写出模式串的next[j]函数值。 答:根据 0 当j =1时 next[ j ]= max { k |1

(完整word版)数据结构课后习题及答案

填空题(10 * 1 '= 10') 一、概念题 22当对一个线性表经常进行的是插入和删除操作时,采用链式存储结构为宜。 23当对一个线性表经常进行的是存取操作,而很少进行插入和删除操作时,最好采用顺序存储结构。 2.6. 带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。 36循环队列的引入,目的是为了克服假溢出。 4.2. 长度为0的字符串称为空串。 4.5. 组成串的数据元素只能是字符。 4.8. 设T和P是两个给定的串,在T中寻找等于P的子串的过程称为模式匹配,又称P为模式。 7.2. 为了实现图的广度优先搜索,除一个标志数组标志已访问的图的结点外,还需要队列存放被访问的结点实现遍历。 5.7. 广义表的深度是广义表中括号的重数 7.8. 有向图G可拓扑排序的判别条件是有无回路。 7.9. 若要求一个稠密图的最小生成树,最好用Prim算法求解。 8.8. 直接定址法法构造的哈希函数肯定不会发生冲突。 9.2. 排序算法所花费的时间,通常用在数据的比较和交换两大操作。 1.1. 通常从正确性、可读性、健壮性、时空效率等几个方面评价算法的(包括程序)的质量。 1.2. 对于给定的n元素,可以构造出的逻辑结构有集合关系、线性关系树形关系、图状关系四种。 1.3. 存储结构主要有顺序存储、链式存储、索引存储、散列存储四种。 1.4. 抽象数据类型的定义仅取决于它的一组逻辑特性,而与存储结构无关,即不论其内部结构如何变化,只要它的数学特性不 变,都不影响其外部使用。 1.5. 一个算法具有五大特性:有穷性、确定性、可行性,有零个或多个输入、有一个或多个输入。 2.8. 在双向链表结构中,若要求在p指针所指的结点之前插入指针为s所指的结点,则需执行下列语句: s_>prior= p_>prior; s->next= p; p_>prior- next= s; p_>prior= s;。 2.9. 在单链表中设置头结点的作用是不管单链表是否为空表,头结点的指针均不空,并使得对单链表的操作 (如插入和删除)在各种情况下统一。 3.1. 队列是限制在表的一端进行插入和在另一端进行删除的线性表,其运算遵循先进先出原则。 3.2 .栈是限定尽在表位进行插入或删除操作的线性表。 3.5. 在链式队列中,判定只有一个结点的条件是(Q->rear==Q->fro nt)&&(Q->rear!=NULL) 。 3.7. 已知链队列的头尾指针分别是f和r,则将x入队的操作序列是node *p=(node *)malloc(node); p->next=x;] p_>next=NULL; if(r) {r->next=p; r=p;} else {r=p; f=p;}。 3.8. 循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt 和(fron t=-1 &&rear+ ^=MAXSIZE) 。 4.3. 串是一种特殊的线性表,其特殊性表现在数据元素都是由字符组成。 4.7. 字符串存储密度是串值所占存储位和实际分配位的比值,在字符串的链式存储结构中其结点大小是可变的。 5.3. 所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数,则称该矩阵为矩阵中非零元素远远小于元素总数,则称该矩阵为稀 疏矩阵。 5.4. —维数组的逻辑结构是线性结构,存储结构是顺序存储结构;对二维或多维数组,分别按行优先和列优先两种?不同的存储 方式。 7.4. 在有向图的邻接矩阵表示中,计算第i个顶点入度的方法是求邻接矩阵中第?i列非10元素的个数。 7.10. AOV网中,结点表示活动,边表示活动之间的优先关系,AOE网中,结点表示事件,边表示活动。 9.1. 按排序过程中依据不同原则对内部排序方法进行分类,主要有选择排序、交换排序、插入排序归并排序等4类。 9.3 .在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑,则应选择归并排序方法;若只从平均情况下 排序最快考虑,则应选择快速排序方法;若只从最坏情况下排序最快且要节省类存考虑,则应选择堆排序方法。 9.4. 直接插入排序用监视哨的作用是存当前要的插入记录,可又省去查找插入位置时对是否出界的判断。 9.6. 设表中元素的初始状态是按键值递增的,则直接插入排序最省时间,快速排序最费时间。 4.9. 下列程序判断字符串s是否对称,对称则返回1,否则返回0;如?(abba”返回1, ? (”abab”)返回0. Int f (char*s) { Int i=0,j=0;

数据结构课后习题答案

数据结构习题集答案 第1章绪论 1.1 简述下列术语:数据,数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。 解:数据是对客观事物的符号表示。在计算机科学中是指所有能输入到计算机中并被计算机程序处理的符号的总称。 数据元素是数据的基本单位,在计算机程序中通常作为一个整体进行考虑和处理。 数据对象是性质相同的数据元素的集合,是数据的一个子集。 数据结构是相互之间存在一种或多种特定关系的数据元素的集合。存储结构是数据结构在计算机中的表示。 数据类型是一个值的集合和定义在这个值集上的一组操作的总称。抽象数据类型是指一个数学模型以及定义在该模型上的一组操作。是对一般数据类型的扩展。 1.2 试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别。 解:抽象数据类型包含一般数据类型的概念,但含义比一般数据类型更广、更抽象。一般数据类型由具体语言系统内部定义,直接提供给编程者定义用户数据,因此称它们为预定义数据类型。抽象数据

类型通常由编程者定义,包括定义它所使用的数据和在这些数据上所进行的操作。在定义抽象数据类型中的数据部分和操作部分时,要求只定义到数据的逻辑结构和操作说明,不考虑数据的存储结构和操作的具体实现,这样抽象层次更高,更能为其他用户提供良好的使用接口。 1.3 设有数据结构(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.4 试仿照三元组的抽象数据类型分别写出抽象数据类型复数和有理数的定义(有理数是其分子、分母均为自然数且分母不为零的分数)。 解:ADT Complex{ 数据对象:D={r,i|r,i 为实数} 数据关系:R={} 基本操作: InitComplex(&C,re,im) 操作结果:构造一个复数C ,其实部和虚部分别为re 和im DestroyCmoplex(&C) 操作结果:销毁复数C Get(C,k,&e) 操作结果:用e 返回复数C 的第k 元的值

数据结构试题及答案

第一章概论 一、选择题 1、研究数据结构就是研究(D)。 A. 数据的逻辑结构?B。数据的存储结构 C。数据的逻辑结构和存储结构?D.数据的逻辑结构、存储结构及其基本操作(研究非数值计算的程序设计问题中,计算机操作对象以及他们之间的关系和操作) 2、算法分析的两个主要方面是(A)。 A.空间复杂度和时间复杂度???B。正确性和简单性 C。可读性和文档性D.数据复杂性和程序复杂性 3、具有线性结构的数据结构是( D )。(线性结构就是:在非空有限集合中,存在为一个被称为第一个的数据元素和最后一个元素,有除了第一个元素,集合中每一个元素均只有一个前驱,除了最后一个元素有唯一后继)(链表、栈、队列、数组、串) A. 图B. 树??C.广义表(线性表的推广) D.栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。 A.可执行性、可移植性和可扩充性? B. 可执行性、有穷性和确定性 C。确定性、有穷性和稳定性??? D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C )。 for(i=0;i

数据结构试卷B卷(含答案)

《数据结构》试卷B 一、填空题(每空1分,共15分) 1. 向量、栈和队列都是结构,可以在向量的位置插入和删除元素;对于栈 只能在插入和删除元素;对于队列只能在插入和删除元素。 2. 栈是一种特殊的线性表,允许插入和删除运算的一端称为。不允许插入和删除 运算的一端称为。 3. 数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之间 的和运算等的学科。 4. 在顺序表中插入或删除一个元素,需要平均移动元素,具体移动的元素个数与有关。 5. 在具有n个单元的循环队列中,队满时共有个元素。 6. 假设在有序线性表a[20]上进行折半查找,则比较一次查找成功的结点数为1;比较两次查 找成功的结点数为;比较四次查找成功的结点数为;平均查找长度为。 二、判断正误(判断下列概念的正确性,并作出简要的说明。)(每小题1分,共10分) ()1. 线性表的每个结点只能是一个简单类型,而链表的每个结点可以是一个复杂类型。()2. 在表结构中最常用的是线性表,栈和队列不太常用。 ()3. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种后进先出型结构。 ()4. 对于不同的使用者,一个表结构既可以是栈,也可以是队列,也可以是线性表。()5.线性表的逻辑顺序与存储顺序总是一致的 ()6. 栈和队列是一种非线性数据结构。 ()7. 栈和队列的存储方式既可是顺序方式,也可是链接方式。 ()8. 两个栈共享一片连续内存空间时,为提高内存利用率,减少溢出机会,应把两个栈的栈底分别设在这片内存空间的两端。 ()9. 队是一种插入与删除操作分别在表的两端进行的线性表,是一种先进后出型结构。

最全数据结构课后习题答案耿国华版

绪论第1章 √(2)×(3)2.(1)×C )C(3(1)A(2)3. 的语句频度5.计算下列程序中x=x+1for(i=1;i<=n;i++) for(j=1;j<=i;j++) for(k=1;k<=j;k++) x=x+1; 的语句频度为:【解答】x=x+1=n(n+1)(n+2)/6 )+……+(1+2+……+n)T(n)=1+(1+2)+(1+2+3 并确定算法中每一),p(xx+ax+a+…….+ax的值6.编写算法,求一元多项式p(x)=a n20nn20n1规定算法中不能使用要求时间复杂度尽可能小,语句的执行次数和整个算法的时间复杂度,算法的输入和输出)。n,输出为P(x求幂函数。注意:本题中的输入为a(i=0,1,…n)、x和0in采用下列方法1)通过参数表中的参数显式传递()通过全局变量隐式传递。讨论两种方法的优缺点,并在算法中以你认为较好的一种实(2 现输入输出。【解答】1)通过参数表中的参数显式传递(优点:当没有调用函数时,不占用存,调用结束后形参被释放,实参维持,函数通用 性强,移置性强。缺点:形参须与实参对应,且返回值数量有限。 )通过全局变量隐式传递(2 优点:减少实参与形参的个数,从而减少存空间以及传递数据时的时间消耗 缺点:函数通用性降低,移植性差 算法如下:通过全局变量隐式传递参数PolyValue() { int i,n; float x,a[],p; nn=”);printf(“\ scanf(“%f”,&n); nx=”);printf(“\ scanf(“%f”,&x); for(i=0;i

最全数据结构课后习题答案(耿国华版[12bb]

第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.数据逻辑结构包括线性结构、树形结构和图状结构三种类型,树形结构和图状结构合称非线性结构 2.数据的逻辑结构分为集合、线性结构、树形结构和图状结构 4种。 3.在线性结构中,第一个结点没有前驱结点,其余每个结点有且只有 1 个前驱结点;最后一个结点没有后续结点,其余每个结点有且只有 1 个后续结点。 4.线性结构中元素之间存在一对一关系,树形结构中元素之间存在一对多关系,图形结构中元素之间存在多对多关系。 5.在树形结构中,树根结点没有前驱结点,其余每个结点有且只有 1 个前驱结点;叶子结点没. 6.数据结构的基本存储方法是顺序、链式、索引和散列存储。有后续结点,其余每个结点的后续结点可以任意多个。 7.衡量一个算法的优劣主要考虑正确性、可读性、健壮性和时间复杂度与空间复杂度。8.评估一个算法的优劣,通常从时间复杂度和空间复杂度两个方面考察。 9.算法的5个重要特性是有穷性、确定性、可行性、输入和输出。 10.在单链表中,要删除某一指定的结点,必须找到该结点的前驱结点。 11.在单链表中,要删除某一指定的结点,必须找到该结点的前驱结点。 12.在双链表中,每个结点有两个指针域,一个指向前驱结点,另一个指向后继结点。13.在顺序表中插入或删除一个数据元素,需要平均移动 n 个数据元素,移动数据元素的个数与位置有关 14.当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取线性表的元素是,应采用顺序存储结构 15.根据线性表的链式存储结构中每一个结点包含的指针个数,将线性链表分成单链表和双链表。 16.顺序存储结构是通过下标表示元素之间的关系的;链式存储结构是通过指针表示元素之间的关系的 17.带头结点的循环链表L中只有一个元素结点的条件是 L->next->next=L 18.栈是限定仅在表尾进行插入或删除操作的线性表,其运算遵循后进先出的原则。19.空串是零个字符的串,其长度等于零。空白串是由一个或多个空格字符组成的串,其长度等于其包含的空格个数。 20.组成串的数据元素只能是单个字符。 21.一个子串”str”在主串”datastructure”中的位置是 5 。 22.字符串中任意个连续字符构成的部分称为该串的子串。 23.二维数组M的每个元素是6个字符组成的串,行下标i的范围从0到8,列下标j的范围从1到10,则存放M至少需要 540个字节;M的第8列和第5行共占108个字节24.稀疏矩阵一般的压缩存储方法有两种,即三元组表和十字链表。 25.广义表((a),((b),c),(((d))))的长度是 3 ,深度是 4 。 26.在一棵二叉树中,度为零的结点的个数为n0,度为2 的结点的个数为n2,则有n0= n2+1 。 27.在有n个结点的二叉链表中,空链域的个数为__n+1__。 28.一棵有n个叶子结点的哈夫曼树共有__2n-1_个结点 29.深度为5的二叉树至多有 31 个结点。 30.若某二叉树有20个叶子结点,有30个结点仅有一个孩子,则该二叉树的总结点个数为69 。

数据结构课后习题答案清华大学出版社殷人昆

1-1什么是数据? 它与信息是什么关系? 【解答】 什么是信息?广义地讲,信息就是消息。宇宙三要素(物质、能量、信息)之一。它是现实世界各种事物在人们头脑中的反映。此外,人们通过科学仪器能够认识到的也是信息。信息的特征为:可识别、可存储、可变换、可处理、可传递、可再生、可压缩、可利用、可共享。 什么是数据?因为信息的表现形式十分广泛,许多信息在计算机中不方便存储和处理,例如,一个大楼中4部电梯在软件控制下调度和运行的状态、一个商店中商品的在库明细表等,必须将它们转换成数据才能很方便地在计算机中存储、处理、变换。因此,数据(data)是信息的载体,是描述客观事物的数、字符、以及所有能输入到计算机中并被计算机程序识别和处理的符号的集合。在计算机中,信息必须以数据的形式出现。 1-2什么是数据结构? 有关数据结构的讨论涉及哪三个方面? 【解答】 数据结构是指数据以及相互之间的关系。记为:数据结构= { D, R }。其中,D是某一数据对象,R是该对象中所有数据成员之间的关系的有限集合。 有关数据结构的讨论一般涉及以下三方面的内容: ①数据成员以及它们相互之间的逻辑关系,也称为数据的逻辑结构,简称为数据结构; ②数据成员极其关系在计算机存储器内的存储表示,也称为数据的物理结构,简称为存储结构; ③施加于该数据结构上的操作。 数据的逻辑结构是从逻辑关系上描述数据,它与数据的存储不是一码事,是与计算机存储无关的。因此,数据的逻辑结构可以看作是从具体问题中抽象出来的数据模型,是数据的应用视图。数据的存储结构是逻辑数据结构在计算机存储器中的实现(亦称为映像),它是依赖于计算机的,是数据的物理视图。数据的操作是定义于数据逻辑结构上的一组运算,每种数据结构都有一个运算的集合。例如搜索、插入、删除、更新、排序等。 1-3数据的逻辑结构分为线性结构和非线性结构两大类。线性结构包括数组、链表、栈、 队列、优先级队列等; 非线性结构包括树、图等、这两类结构各自的特点是什么? 【解答】 线性结构的特点是:在结构中所有数据成员都处于一个序列中,有且仅有一个开始成员和一个终端成员,并且所有数据成员都最多有一个直接前驱和一个直接后继。例如,一维数组、线性表等就是典型的线性结构 非线性结构的特点是:一个数据成员可能有零个、一个或多个直接前驱和直接后继。例如,树、图或网络等都是典型的非线性结构。 1-4.什么是抽象数据类型?试用C++的类声明定义“复数”的抽象数据类型。要求 (1) 在复数内部用浮点数定义它的实部和虚部。 (2) 实现3个构造函数:缺省的构造函数没有参数;第二个构造函数将双精度浮点数赋给复数的实部,虚部置为0;第三个构造函数将两个双精度浮点数分别赋给复数的实部和虚部。 (3) 定义获取和修改复数的实部和虚部,以及+、-、*、/等运算的成员函数。

数据结构试题及答案

一、判断题: 1、线性表的逻辑顺序与物理顺序总是一致的。( ) 2、线性表的顺序存储表示优于链式存储表示。( ) 3、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。( ) 4、二维数组是其数组元素为线性表的线性表。( ) 5、每种数据结构都应具备三种基本运算:插入、删除和搜索。( ) 6、数据结构概念包括数据之间的逻辑结构,数据在计算机中的存储方式和数据的运算三个 方面。( ) 7、线性表中的每个结点最多只有一个前驱和一个后继。() 8、线性的数据结构可以顺序存储,也可以链接存储。非线性的数据结构只能链接存储。() 9、栈和队列逻辑上都是线性表。() 10、单链表从任何一个结点出发,都能访问到所有结点() 11、删除二叉排序树中一个结点,再重新插入上去,一定能得到原来的二叉排序树。() 12、快速排序是排序算法中最快的一种。() 13、多维数组是向量的推广。() 14、一般树和二叉树的结点数目都可以为0。() 15、直接选择排序是一种不稳定的排序方法。() 16、98、对一个堆按层次遍历,不一定能得到一个有序序列。() 17、在只有度为0和度为k的结点的k叉树中,设度为0的结点有n0个,度为k的结点有nk个,则有n0=nk+1。() 18、折半搜索只适用与有序表,包括有序的顺序表和有序的链表。() 19、堆栈在数据中的存储原则是先进先出。() 20、队列在数据中的存储原则是后进先出。() 21、用相邻矩阵表示图所用的存储空间大小与图的边数成正比。() 22、哈夫曼树一定是满二叉树。() 23、程序是用计算机语言表述的算法。() 24、线性表的顺序存储结构是通过数据元素的存储地址直接反映数据元素的逻辑关系。() 25、用一组地址连续的存储单元存放的元素一定构成线性表。() 26、堆栈、队列和数组的逻辑结构都是线性表结构。() 27、给定一组权值,可以唯一构造出一棵哈夫曼树。() 28、只有在初始数据为逆序时,冒泡排序所执行的比较次数最多。()

十套数据结构试题与答案

数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 (一) (二) (三) (四) (五) (六) (七 )(八 ) (九 ) (十 ) 9 12 15 17 19 21 24 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 数据结构试卷 (一) (二) (三 ) (四 ) (五 ) (六) (七) (八) (九) (十 ) 27 28 29 31 33 35 37 38 39 40 数据结构试卷(一) 、单选题(每题 栈和队列的共同特点是(A ) 。 A. 只允许在端点处插入和删除元素 B. 都是先进后出 C. 都是先进先出 D. 没有共同点 用链接方式存储的队列,在进行插入运算时 (C ). 头、尾指针都要修改 头、尾指针可能都要修改 (D ) 线性表 2分,共20分) 1. 2. A. C. 3. A. 4. 仅修改头指针 B. 仅修改尾指针 D. 以下数据结构中哪一个是非线性结构? 队列 B.栈 C. 设有一个二维数组 A[m][ n],假设 个空间,问 676(10),每个元素占 制表示。 .688 D. 二叉树 A[2][2]存放位置在 (10)存放在什么位置?脚注(10)表示用10进 A[0][0] 存放位置在644(10), A[3][3] .678 C C ) 。 B. A 5.树最适合用来表示( A.有序数据元素 C.元素之间具有分支层次关系的数据 二叉树的第k 层的结点数最多为(D ). k .2 -1 B.2K+1 C.2K-1 若有18个元素的有序表存放在一维数组 6. A 7. 692 D . 696 D. 无序数据元素 乙间无联系的数 据 元素之 f k-1 D. 2 A[19]中,第一个元素放 A[1]中,现进行二 分查找,则查找 A : 3 ]的比较序列的下标依次为 (C ) A. 1 , 2, 3 B. 9 , 5, 2, 3 C. 9 , 5, 3 D. 9 , 4, 2, 3 对n 个记录的文件进行快速排序,所需要的辅助存储空间大致为 D. O 8. A. O (1) B. O (n ) C. O (1og 2n ) D. O (n2) 9. 对于线性表(7, 34, 55, 25, 64, 46, 20, 10)进行散列存储时,若选用 H (K ) =K %9作为散列函数,则散列地址为 1的元素有(D )个, A . 1 B . 2 C . 3 10. 设有6个结点的无向图,该图至少应有 ( A.5 B.6 C.7 D.8 二、填空题(每空 1分,共26分) 1.通常从四个方面评价算法的质量: _ 高效率 _______ 和―强壮性 _______ 。 1. 一个算法的时间复杂度为(n 3 +nlog 2n+14n)/ n 2 ,其数量级表示为 —o(n) ____________________ 。 2. 假定一棵树的广义表表示为 A (C, D (E , F , G , H( I , J )),则树中所含的结点数为 __________ 个,树的深度为 ____________ ,树的度为 ___________ 。 .4 条边才能确保是一个连通图。 正确性 易读性

相关主题