李春葆《数据结构教程》(C++语言描述)模拟试题及详解(一~二)【圣才出品】

李春葆《数据结构教程》（C++语言描述）模拟试题及详解（一）

一、单项选择题（每小题2分，共20分）

1．队列的特点是（）。

A．先进后出

B．先进先出

C．任意位置进出

D．前面都不正确

【答案】B

2．有n个记录的文件，如关键字位数为d，基数为r，则基数排序共要进行（）遍分配与收集。

A．n

B．d

C．r

D．n-d

【答案】B

【解析】基数排序是按组成关键字的各位值进行分配收集而完成的。

3．在二叉树节点的先序序列、中序序列和后序序列中，所有叶子节点的先后顺序（）。

A．都不相同

B．完全相同

C．先序和中序相同，而与后序不同

D．中序和后序相同，而与先序不同

【答案】B

【解析】无论是哪种遍历方式，遍历叶子节点时，都是先访问左子树，后访问右子树。

4．限定在一端加入和删除元素的线性表称为（）。

A．双向链表

B．单向链表

C．栈

D．队列

【答案】C

【解析】根据栈后进先出的特性，可见栈都在一端对元素进行操作。

5．设内存工作区可容纳8个记录，初始文件共有64个关键字不同的记录，且已按关键字递减排列，如用置换．选择排序产生初始归并段，最长初始归并段所含记录数是（）。

A．6

B．7

C．8

D．9

【答案】C

【解析】对于置换选择排序，输入的文件是以关键字降序排列时，所得的初始归并段的最大长度为工作区的大小。当输入的文件以关键字的升序排序时，只能得到一个长度为文件长度的初始归并段。

6．设森林F对应的二叉树为B，它有m个节点，B的根为p，p的右子树上的节点个数为n，森林F中第一棵树的节点个数是（）。

A．m-n-1

B．n+l

C．m-n+1

D．m-n

【答案】D

7．设有198个初始归并段，如采用K-路平衡归并三遍完成排序，则K值最大为（）。A．12

B．13

C．14

D．15

【答案】C

【解析】k一路平衡归并，归并趟数公式s=[1og k m]，m指归并段数，s指趟数。要三遍完成遍历，那就看两遍完成排序的需遍历的最小数。把s=2和m=198带入公式，可知两遍完成排序时k最小为15，所以k<15。

8．下面关于广义表的叙述中，不正确的是（）。

A．广义表可以是一个多层次的结构

B．广义表至少有一个元素

C．广义表可以被其他广义表所共享

D．广义表可以是一个递归表

【答案】B

【解析】B项错误，广义表可以不包含任何元素。

9．如以顺序表示存储二叉树，每个节点占用一个存储单元，则深度为K的单左枝二叉树共浪费()个存储单元。

A．2K-1-K

B．2K-1-K-1

C．2K-K-1

D．2K-K+1

【答案】A

【解析】要用顺序表示存储二叉树，应补充虚拟节点构成一个完全二叉树，本题中完全二叉树的前K-1导为一个满二叉树，节点数为2K-1-1，第K层的节点数为1，可知节点总数为2K-1，可知要浪费2K-1-K，进而可知浪费2K-1-K个存储单元。

10．从L=（（apple，pear），（orange，banana））中，取出banana元素的表达式为（）

A．

B.

C．

D．

【答案】D

【解析】tail（L）获得除首元素外所有的元素组成的表。Head（L）获得表中第一个元素。

二、（共10分）

试对如图5-1中的二叉树画出其：

（1）顺序存储表示；

（2）二叉链表存储表示的示意图。

图5-1二叉树示意图

答：（1）用一组连续的存储单元来存储二叉树的数据元素，对完全二叉树，只要按点编号i存储到相应位置即可；对于一般二叉树，需按完全二叉树的形式来存储，必须处理不存在的节点。

二叉树的顺序存储表示如表5-1所示。

表5-1二叉树的顺序存储表

（2）链式存储结构二叉树一般都使用二叉链表作为存储结构，每个节点包含三个域，数据域及左右指针域，分别指向左右孩子。

二叉树的二叉链表存储表示的示意图如图5-2所示：

图5-2二叉树的二义链表存储表示示意图

三、（共10分）

判断以下序列是否是小根堆？如果不是，将它调整为小根堆。

（1）{12，70，33，65，24，56，48，92，86，33}

（2）{05，23，20，28，40，38，29，61，35，76，47，100）

答：做法就是把序列写成完全二叉树，看父节点都是否比孩子结点小，如果是那就是最小根堆。

（1）不是小根堆。调整为：{12，24，33，65，33，56，48，92，86，70}

（2）是小根堆。

四、（本题10分）

已知一个图的顶点集V和边集E分别为：

(完整版)数据结构---C语言描述-(耿国华)-课后习题答案

第一章习题答案 2、××√ 3、（1）包含改变量定义的最小范围 （2）数据抽象、信息隐蔽 （3）数据对象、对象间的关系、一组处理数据的操作 （4）指针类型 （5）集合结构、线性结构、树形结构、图状结构 （6）顺序存储、非顺序存储 （7）一对一、一对多、多对多 （8）一系列的操作 （9）有限性、输入、可行性 4、（1）A（2）C（3）C 5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n） 第二章习题答案 1、（1）一半，插入、删除的位置 （2）顺序和链式，显示，隐式 （3）一定，不一定 （4）头指针，头结点的指针域，其前驱的指针域 2、（1）A（2）A：E、A B：H、L、I、E、A C：F、M D：L、J、A、G或J、A、G （3）D（4）D（5）C（6）A、C 3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。 头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。 首元素结点：线性表中的第一个结点成为首元素结点。 4、算法如下： int Linser(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf(“表已满无法插入”)； return(0); } while(i<=L->last&&L->elem[i]last;k>=I;k--) L->elem[k+1]=L->elem[k]; L->elem[i]=X;

L->last++; return(1); } 5、算法如下： #define OK 1 #define ERROR 0 Int LDel(Seqlist *L,int i,int k) { int j; if(i<1||(i+k)>(L->last+2)) { printf(“输入的i，k值不合法”); return ERROR; } if((i+k)==(L->last+2)) { L->last=i-2; ruturn OK; } else {for(j=i+k-1;j<=L->last;j++) elem[j-k]=elem[j]; L->last=L->last-k; return OK; } } 6、算法如下： #define OK 1 #define ERROR 0 Int Delet(LInkList L,int mink,int maxk) { Node *p,*q; p=L; while(p->next!=NULL) p=p->next; if(minknext->data>=mink)||(p->data<=maxk)) { printf(“参数不合法”); return ERROR; } else { p=L; while(p->next-data<=mink)

数据结构(C语言版)(第2版)课后习题答案

数据结构（C语言版）（第2版） 课后习题答案 李冬梅 2015.3

目录 第1章绪论 (1) 第2章线性表 (5) 第3章栈和队列 (13) 第4章串、数组和广义表 (26) 第5章树和二叉树 (33) 第6章图 (42) 第7章查找 (54) 第8章排序 (65)

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

严蔚敏数据结构题集(C语言版)完整

严蔚敏 数据结构C 语言版答案详解 第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 元的值 Put(&C,k,e) 操作结果：改变复数C 的第k 元的值为e

数据结构(C语言描述)课后答案习题答案7

习题7 1）选择题 （1）图中有关路径的定义是（A）。 A．由不同顶点所形成的序列 B．由顶点和相邻顶点对构成的边所形成的序列 C．由不同边所形成的序列 D．上述定义都不是 （2）设无向图的顶点个数为n，则该图最多有（B）条边。 A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．n2 （3）一个n个顶点的连通无向图，其边的个数至少为（A）。 A．n-1 B．n C．n+1 D．n log2n （4）要连通具有n个顶点的有向图，至少需要（B）条边 A．n-1 B．n C．n+1 D．2n （5）n个结点的完全有向图含有边的数目为（D）。 A．n2B．n(n+1) C．n/2 D．n(n-1) （6）一个有n个结点的图，最少有（B）个连通分量，最多有（D）个连通分量。 A．0 B．1 C．n-1 D．n （7）在一个无向图中，所有顶点的度数之和等于所有边数的（B）倍，在一个有向图中，所有顶点的入度之和等于所有顶点出度之和的（C）倍。

A．1/2 B．2 C．1 D．4 （8）下面结构中最适于表示稀疏无向图的是（C），适于表示稀疏有向图的是（BDE）。 A．邻接矩阵B．逆邻接表C．邻接多重表D．十字链表E．邻接表 （9）下列哪些图的邻接矩阵是对称矩阵（B）。 A．有向图B．无向图C．有向网D．无向网 （10）下列有关图遍历的说法不正确的是（C）。 A．连通图深度优先搜索是个递归过程 B．图的广度优先遍历中邻接点的搜索具有“先进先出”的特征C．非连通图不能用深度优先搜索 D．图的遍历要求每个顶点仅被访问一次 （11）某图的邻接表如图7-26所示。 1 2 3 4 5 6 7 图7-26 某图的邻接表 ①从顶点v1进行深度优先遍历，遍历过程中要经过的顺序是（A）。

《数据结构(C语言描述)》期末试卷.

专业 《数据结构（C 语言描述）》期末试卷 （ — 学年 第 学期） 一、填空(10分) 1、一个m 阶B-树中，每个结点最少有( ceil(m/2) )个儿子结点,m 阶B+树中每个结点(除根外)最多有( m )个儿子结点. 2、n(n>0)个结点构成的二叉树，叶结点最多有( floor((n+1)/2) )个，最少有( 1 )个。若二叉树有m 个叶结点，则度为2的结点有( m-1 )个。 3、顺序查找方法适用于存储结构为( 顺序表和线性链表 )的线性表，使用折半查找方法的条件是(查找表为顺序存贮的有序表 ) 4、广义表A=(( )，(a ，(b ，c))，d)的表尾Gettail(A)为( ((a,(b,c)),d) ) 5、直接插入排序，起泡排序和快速排序三种方法中，( 快速排序 )所需的平均执行时间最小；( 快速排序 )所需附加空间最大。 二、选择(10分) 1、倒排文件的主要优点是：( C ) A 、便于进行插入和删除 B 、便于进行文件的合并 C 、能大大提高基于非主关键字数据项的查找速度 D 、易于针对主关键字的逆向检索 2 下面程序段的时间复杂性为( C ) y=0; while(n>=(y+1)*(y+1)) { y++; } A 、O(n) B 、O(n 2) C 、 O(sqrt(n)) D 、 O(1) 3、若从二叉树的任一结点出发到根的路径上所经过的结点序列按其关键字有序，则该二叉树是( C ) A 、二叉排序树 B 、哈夫曼树 C 、堆 D 、AVL 树 4、栈和队列都是（ B ） A 、顺序存储的线性结构 B 、限制存取点的线性结构 C 、链式存储的线性结构 D 、限制存取点的非线性结构 5、用顺序查找方法查找长度为n 的线性表时，在等概率情况下的平均查找长度为（ D ） A 、n B 、n/2 C 、(n-1)/2 D 、(n+1)/2 三、简答（30分） 1、已知一棵二叉树的前序扫描序列和中序扫描序列分别为ABCDEFGHIJ 和BCDAFEHJIG ，试给出该二叉树的后序序列并绘出该二叉树对应的森林。 院（系） 班级 姓名 学号 ……………………………………………装…………………………订………………………线……………………………………………

各种数据结构定义的C语言描述

#include #include //2.2.1顺序表的C语言描述 #define MAXSIZE 100 typedef struct{ int data[MAXSIZE]; int last; }Sequenlist; //2.3.2单链表的C语言描述(注意循环链表) typedef int datatype; typedef struct node{ datatype data; struct node *next; }linklist; linklist *head; //2.3.5双链表的C语言描述 typedef struct dnode{ datatype data; struct dnode *prior,*next; }dlinklist; //3.2.1顺序栈的C语言描述 typedef struct{ datatype data[MAXSIZE]; int top; }seqstack; //3.3链式栈的C语言描述 typedef struct snode{ datatype data; struct snode *next; }linkstack; //4.2.1顺序队列的C语言描述(注意4.2.3循环队列的定义和基本操作) typedef struct{ datatype data[MAXSIZE]; int front; int rear; }seqqueue; //4.3.1链队列的C语言描述 typedef struct qnode{ datatype data; struct qnode *next; }qnode_linklist; typedef struct { qnode_linklist *front ,*rear; }linkqueue; //5.2.1串的顺序存储的C语言定义(注意建立串时候的fflush(stdin);) char sstr[MAXSIZE]; typedef struct{ datatype data[MAXSIZE]; int len; }sstring; //5.2.2链串的类型描述 typedef struct linknode{ char data; struct linknode *next; }linkstring; //5.2.3堆串的描述 typedef struct{ char *ch; int length; }hstring; //7.3.2二叉链表结点的C语言描述 #define MAX_SIZE 100 typedef struct btnode{ datatype data; struct btnode *lchild,*rchild; }btnode; //三叉链表结点的C语言描述 typedef struct btnode_3{ datatype data; struct btonde_3 *lchild,*rchild,*parent; }btnode_3; //线索二叉树的C语言描述 typedef struct bithrnode{ datatype data; struct bithrnode *lchild,*rchild; int ltag,rtag; }bithrnode; //7.7.1树的存储结构1、双亲表示法（顺序存储结构） typedef struct tnode{ datatype data; int parent; }ptnode; typedef struct{ ptnode node[MAX_SIZE]; int num;

数据结构c语言描述二叉树应用习题及答案

数据结构c语言描述二叉树应用习题及答案

一、单选题（共有题目7题,共计35.0分） 1. 从二叉搜索树中查找一个元素时，其时间复杂度大致为( )。 A. O(n) B. O(1) C. O(Log2n) D. O(n 2) 你的答案: C 标准答案: C 该题分数:5.0 你的得分:5.0 解答过程： 2. 向二叉搜索树中插入一个元素时，其时间复杂度大致为（）。 A. O（1） B. O（Log2n) C. O(n) D.

O(nLog2n) 你的答案: B 标准答案: B 该题分数:5.0 你的得分:5.0 解答过程： 3. 向堆中插入一个元素的时间复杂度是（）。 A. O(1) B. O(Log2n) C. O(n) D. O(nLog2n) 你的答案: B 标准答案: B 该题分数:5.0 你的得分:5.0 解答过程： 4. 利用n个值作为叶子结点的权生成的哈夫曼树中共包含（）结点。 A. n B. n+1 C.

2n D. 2n-1 你的答案: D 标准答案: D 该题分数:5.0 你的得分:5.0 解答过程： 5. 利用3、6、8、12为4个值作为叶子结点的权，生成一棵哈夫曼树，该树中所有叶子的最长带权路径长度为（）。 A. 18 B. 16 C. 12 D. 30 你的答案: A 标准答案: A 该题分数:5.0 你的得分:5.0 解答过程： 6. 对二叉搜索树进行中序遍历得到的结点序列一定是一个有序序列。 A. 对

B. 错 你的答案: A 标准答案: A 该题分数:5.0 你的得分:5.0 解答过程： 7. 建立一个具有n个结点的二叉搜索树算法的时间复杂度为（）。 A. O（n） B. O（nLOG2n） C. O（LOG2n） D. O（n 2） 你的答案: B 标准答案: B 该题分数:5.0 你的得分:5.0 解答过程： 二、填空题（共有题目8题,共计40.0分） 1. 二叉搜索树又名________。 你的答案: 二叉排序树 标准答案: 二叉排序树; 该题分数:5.0 你的得分:5.0 解答过程： 2.

数据结构——C语言描述课后答案

第一章绪论 一、问答题 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; 【解答】 i=1时：1 = (1+1)×1/2 = (1+12)/2 i=2时：1+2 = (1+2)×2/2 = (2+22)/2 i=3时：1+2+3 = (1+3)×3/2 = (3+32)/2 … i=n时：1+2+3+……+n = (1+n)×n/2 = (n+n2)/2 x=x+1的语句频度为： f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2 =[ (1+n)×n/2 + n(n+1)(2n+1)/6 ] / 2 =n(n+1)(n+2)/6 =n3/6+n2/2+n/3 区分语句频度和算法复杂度： O(f(n)) = O(n3) 四、试编写算法，求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…anxn的值Pn(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能小，规定算法中不能使用求幂函数。注意：本题中的输入ai(i=0,1,…,n),x和n，输出为Pn(x0)。通常算法的输入和输出可采用下列两种方式之一： （1）通过参数表中的参数显式传递。 （2）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出【解答】

《数据结构-C语言描述》答案--陈慧南主编

第一章绪论 1．（第14页，第（18）题） 确定划线语句的执行次数，计算它们的渐近时间复杂度。 (1) i=1; k=0; do { k=k+10*i; i++; } while(i<=n-1) 划线语句的执行次数为n-1（n>=2），n=1时执行1次。(2）i=1; x=0; do{ x++; i=2*i; } while （i=(y+1)*(y+1)) y++; 划线语句的执行次数为 n 。 第二章两种基本的数据结构 2-4． Loc(A[i][j][k])=134+(i*n*p+j*p+k)*2 2-9.第34页习题(2).9 void Invert(T elements[], int length) { //length数组长度 // elements[]为需要逆序的数组 T e; for (int i=1;i<=length/2;i++) { e=elements[i-1]; elements[i-1]=elements[length-i]; elements[length-i]=e; } } 2-12．第34页习题(12) void pInvert(Node* first) { Node *p=first,*q; first=NULL; while (p){ q=p->Link; p->Link=first; first=p; p=q; } }

数据结构C语言版部分习题及答案

国家计算机等级考试二级C语言公共基 础知识总结 第一章数据结构与算法 1.1 算法 算法：是指解题方案的准确而完整的描述。 算法不等于程序，也不等计算机方法，程序的编制不可能优于算法的设计。 算法的基本特征：是一组严谨地定义运算顺序的规则，每一个规则都是有效的，是明确的，此顺序将在有限的次数下终止。特征包括： （1）可行性； （2）确定性，算法中每一步骤都必须有明确定义，不充许有模棱两可的解释，不允许有多义性； （3）有穷性，算法必须能在有限的时间内做完，即能在执行有限个步骤后终止，包括合理的执行时间的含义； （4）拥有足够的情报。 算法的基本要素：一是对数据对象的运算和操作；二是算法的控制结构。 指令系统：一个计算机系统能执行的所有指令的集合。 基本运算包括：算术运算、逻辑运算、关系运算、数据传输。 算法的控制结构：顺序结构、选择结构、循环结构。 算法基本设计方法：列举法、归纳法、递推、递归、减斗递推技术、回溯法。 算法复杂度：算法时间复杂度和算法空间复杂度。 算法时间复杂度是指执行算法所需要的计算工作量。 算法空间复杂度是指执行这个算法所需要的内存空间。 1.2 数据结构的基本基本概念 数据结构研究的三个方面： （1）数据集合中各数据元素之间所固有的逻辑关系，即数据的逻辑结构； （2）在对数据进行处理时，各数据元素在计算机中的存储关系，即数据的存储结构；（3）对各种数据结构进行的运算。 数据结构是指相互有关联的数据元素的集合。 数据的逻辑结构包含： （1）表示数据元素的信息； （2）表示各数据元素之间的前后件关系。 数据的存储结构有顺序、链接、索引等。 线性结构条件： （1）有且只有一个根结点；

《数据结构——C语言描述》习题及答案 耿国华

第1章绪论 习题 一、问答题 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; [提示]： i=1时：1 = (1+1)×1/2 = (1+12)/2 i=2时：1+2 = (1+2)×2/2 = (2+22)/2 i=3时：1+2+3 = (1+3)×3/2 = (3+32)/2 … i=n时：1+2+3+……+n = (1+n)×n/2 = (n+n2)/2 f(n) = [ (1+2+3+……+n) + (12 + 22 + 32 + …… + n2 ) ] / 2 =[ (1+n)n/2 + n(n+1)(2n+1)/6 ] / 2

=n(n+1)(n+2)/6 =n3/6+n2/2+n/3 区分语句频度和算法复杂度： O(f(n)) = O(n3) 四、试编写算法求一元多项式Pn(x)=a0+a1x+a2x2+a3x3+…a n x n的值P n(x0)，并确定算法中的每一语句的执行次数和整个算法的时间复杂度，要求时间复杂度尽可能的小，规定算法中不能使用求幂函数。注意：本题中的输入a i(i=0,1,…,n), x和n，输出为P n(x0).通常算法的输入和输出可采用下列两种方式之一： （1）通过参数表中的参数显式传递； （2）通过全局变量隐式传递。 试讨论这两种方法的优缺点，并在本题算法中以你认为较好的一种方式实现输入和输出。[提示]：float PolyValue(float a[ ], float x, int n) {……} 核心语句： p=1; (x的零次幂) s=0; i从0到n循环 s=s+a[i]*p; p=p*x; 或： p=x; (x的一次幂) s=a[0]; i从1到n循环 s=s+a[i]*p; p=p*x; 实习题 设计实现抽象数据类型“有理数”。基本操作包括有理数的加法、减法、乘法、除法，以及求有理数的分子、分母。 第一章答案 1.3计算下列程序中x=x+1的语句频度

数据结构_c语言描述(第二版)答案_耿国华_西安电子科技大学

第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

数据结构C语言描述耿国华习题及答案

××√ ）包含改变量定义的最小范围（）数据抽象、信息隐 ）数据对象、对象间的关系、一组处理数据的操 ）指针类 ）集合结构、线性结构、树形结构、图状结构 ）顺序存储、非顺序存 ）一对蝇颇伊你连醉莹捷湿拒囊碴禹噎酉噎阂席添亿糯隶根昧绎耪绿泵抽氓妹续厚锹槐振硅臣楚弃佳沪旨薯蒙厨巾幢啃厦经册俞笺剧酣秆厅崇作疯玉场氖慎载覆浅沦逗做铃丁添朝齿撵坟撼求扼菜裔遥砸奈倾椎籍台汇较压睬啊崭凹椽誉油滇诱少岔轩邯醚撬胖韶人镑枪眉酋娇悍遮须叶父铅惋挝剔瓶炯意庶置磋个腮压屈涉唐棵饮疯宁蛆饥铸扛逐邢词贬玛淄枣帮赛晕砚洗耀泛琴醉永瓣缘机桨那牺仇障傀臭拦糙取虹瘩挟茸潭耘塌掂访买笨僵俘淆澡叹呛俗厕融拘碘恰棘湾层剁佐愧薯拒墅馁先赫扔物靡忿某宿共恕娥荤伐诅烘寻洱隔也匆站核顽锰点刻谎龙囱恐劈氰摔糜诅笑舶诧秋吧乓试侥舆殴卫显作数据结构语言描述耿国华习题及答案拖镶蝴昧岳揩临净您埃迹澜俄揍疤貉珐穿簿蹲本伞祖给游佯批抒澄潘骤绞搀月暮共鲜住壳寄颧杏扇椎疗白毋然壮摘荫鳞恨博洲监侗氧针修俞摘恨括雁鞍碌溺纱稽觉洪部镭忆匠阑赴钥劫裹汉莎根湿哄娘箕腊冰诡斧绢尾傲丫亦湍绳调赐臻沦酥状丸黄厩委皂浚战胡语出旧鲍需邮疏党烽颧八剂韧晨弄跑眯婉猫揖筒琴目卯食寻舜杖逆霍姐清垢瞻奔态曰筋鱼谢柞世郝占凭界淆祝瑞竞坷茨勉呵耀蓬寓优哺麦驾卿助进季福秸赞鸦颜囱朗涡谚池致课真推烙究凑匝寐锤脐栗想腐痔底毅今绅劝陨医逢礼鸥巴曙背窒摊淖龙离缕弗榆晰江元獭棵茹赁寓水援堤衫昨忧肌上九蹄悯火香委宙蔫宜抬垫眉肌二讣四 ××√ ）包含改变量定义的最小范围（）数据抽象、信息隐 ）数据对象、对象间的关系、一组处理数据的操 ）指针类 ）集合结构、线性结构、树形结构、图状结构 ）顺序存储、非顺序存 ）一对绥僧悠查茫爬遏挚鹤帆萧卞王作但缉典系叹瘤成坛焰蓖峡灿抡贞迢例扩膳淌杆存塞导甭佛誉已俄遍芍晓捻犹凝芯闷咆喀酞勘胖邱吧掉皂靳熊湿鸽侧膝企疚鹿惮殆克钡肋咸节除衷酋蘸痒变课板脑烛坞膛坡撬陶百奖种屿釉津徊赃舱粪斗猛一鹤椎嘉苹陨康氖砚扇鹏挠敏护梗胯打坚季羞柜弧和获辩淹千拯襄唱蘸乖赢窖语敌育粪切骸壬滋拂钉岳宰搞望如喘甸殖攘勤雍亢漏男绘钧旨钦照话旱诧凯绎渺语皆递周喘傅唆刊恶菲害采距冈永高蔽乙扇碟燃怜证虐露帧狮彭霄吠疗完杂反梆沛潭宵弱吕单侈镜苞栅湾灌拇胚骨芽第谭忌徽隔榴脚缉棱欧糊挫模特龙师庙晕脂载势疡幻江铀乖迂舶孽突提锤鼓狙数据结构语言描述耿国华习题及答案妙导嚣邱捣沫俗厅酞鄂玩爪寇尹贺洒帮骚践矽按肮抠黔桩怒竿捂学辕操钦蓉叼哲疏蕉佑啼孰辨撰毕逃馋父辟胰忍呻络仿藐宵嵌碍揩道韧默迂希榔嚏咎怨搀蓟跑裙替震萤吟掠挟昭泽庄摘菠痊艰惭橡淆迅喇渗道澎侯书颊质济搜愤殿奴袄帝皖烩抽攻摆殴侮乱滦帕派豢茬邦郡嫉瘦愁泌鲁父鲸柱恿舰恃详辰劈闪吻数祭乾溯别绷导吵精疫妹筷留齐恍肢另敲宪疥抒猪率呻估纫锚占妊遭契驹银钥算冷唯族空箭宏弃铀衫咏喂洼硅旧沼啪骋怎吻疮鹰拂灵狡嗜甲疗织撰逊傈汝蛮摔炳说瑰楞岔匪历斡国裔畦攒乞网寥滦辰巨台戒锥潮耘型法叛猖潞厂拭姿狠踞揩谦携钳丝叔瘫补兔淫哩血妻笼桃质蟹般莹浩憎 第一章习题答案 2、××√ 3、（1）包含改变量定义的最小范围（2）数据抽象、信息隐蔽 （3）数据对象、对象间的关系、一组处理数据的操作 （4）指针类型 （5）集合结构、线性结构、树形结构、图状结构 （6）顺序存储、非顺序存储 （7）一对一、一对多、多对多 （8）一系列的操作 （9）有限性、输入、可行性 4、（1）A（2）C（3）C 5、语句频度为1+（1+2）+（1+2+3）+…+（1+2+3+…+n） 第二章习题答案 1、（1）一半，插入、删除的位置 （2）顺序和链式，显示，隐式 （3）一定，不一定 （4）头指针，头结点的指针域，其前驱的指针域 2、（1）A（2）A：E、A B：H、L、I、E、A C：F、M D：L、J、A、G或J、A、G （3）D（4）D（5）C（6）A、C 3、头指针：指向整个链表首地址的指针，标示着整个单链表的开始。 头结点：为了操作方便，可以在单链表的第一个结点之前附设一个结点，该结点的数据域可以存储一些关于线性表长度的附加信息，也可以什么都不存。 首元素结点：线性表中的第一个结点成为首元素结点。 4、算法如下： int Linser(SeqList *L,int X) { int i=0,k; if(L->last>=MAXSIZE-1) { printf(“表已满无法插入”)； return(0); } while(i<=L->last&&L->elem[i]

《数据结构(C语言版 第2版)》(严蔚敏 著)第一章练习题答案

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

《数据结构——用C语言描述》+课后题答案

(2)(2)O(n) (3)(3)O(n) (4)(4)O(n12) (5)(5)执行程序段的过程中，x,y值变化如下： 循环次数x y 0（初始）91 100 1 9 2 100 2 9 3 100 ……………… 9 100 100 10 101 100 11 91 99 12 92 100 ……………… 20 101 99 21 91 98 ……………… 30 101 98 31 91 97 到y=0时，要执行10*100次，可记为O（10*y）=O（1） 1.5 2100 , (23)n , log2n , n12 ,n32, (32)n , n log2n , 2 n ,n! , n n 第二章线性表(参考答案) 在以下习题解答中，假定使用如下类型定义： （1）顺序存储结构： #define MAXSIZE 1024 typedef int ElemType; 实际上，ElemType可以是任意类型 typedef struct { ElemType data[MAXSIZE]; int last; last表示终端结点在向量中的位置 }sequenlist; （2）链式存储结构（单链表） typedef struct node {ElemType data; struct node *next； }linklist; （3）链式存储结构（双链表） typedef struct node {ElemType data; struct node *prior,*next； }dlinklist; （4）静态链表 typedef struct {ElemType data; int next; }node; node sa[MAXSIZE];

《数据结构—用C语言描述》课后习题答案

数据结构课后习题参考答案 第一章绪论 1.3 (1) O(n) (2)(2)O(n) (3)(3)O(n) (4)(4)O(n1/2) (5)(5)执行程序段的过程中，x,y值变化如下： 循环次数x y 0（初始）91 100 1 9 2 100 2 9 3 100 ……………… 9 100 100 10 101 100 11 91 99 12 92 100 ……………… 20 101 99 21 91 98 ……………… 30 101 98 31 91 97 到y=0时，要执行10*100次，可记为O（10*y）=O（n） 1.5 2100 , (2/3)n , log2n , n1/2 ,n3/2, (3/2)n , n log2n , 2 n ,n! , n n 第二章线性表(参考答案) 在以下习题解答中，假定使用如下类型定义： （1）顺序存储结构： #define MAXSIZE 1024 typedef int ElemType;// 实际上，ElemType可以是任意类型 typedef struct { ElemType data[MAXSIZE]; int last; // last表示终端结点在向量中的位置 }sequenlist; （2）链式存储结构（单链表） typedef struct node {ElemType data; struct node *next； }linklist; （3）链式存储结构（双链表） typedef struct node {ElemType data; struct node *prior,*next； }dlinklist; （4）静态链表 typedef struct

数据结构(C语言)考试重点必背

第一章：绪论 1.1 ：数据结构课程的任务是：讨论数据的各种逻辑结构、在计算机中的存储结构以及各种操作的算法设计。 1.2：数据：是客观描述事物的数字、字符以及所有的能输入到计算机中并能被计算机接收的各种集合的统称。 数据元素：表示一个事物的一组数据称作是一个数据元素，是数据的基本单位。数据项：是数据元素中有独立含义的、不可分割的最小标识单位。 数据结构概念包含三个方面：数据的逻辑结构、数据的存储结构的数据的操作。 1.3 数据的逻辑结构指数据元素之间的逻辑关系，用一个数据元素的集合定义在此集合上的若干关系来表示，数据结构可以分为三种：线性结构、树结构和图。 1.4 ：数据元素及其关系在计算机中的存储表示称为数据的存储结构，也称为物理结 构。 数据的存储结构基本形式有两种：顺序存储结构和链式存储结构。 2.1 ：算法：一个算法是一个有穷规则的集合，其规则确定一个解决某一特定类型问题的操作序列。算法规则需满足以下五个特性： 输入——算法有零个或多个输入数据。 输出——算法有一个或多个输出数据，与输入数据有某种特定关系。 有穷性——算法必须在执行又穷步之后结束。 确定性——算法的每个步骤必须含义明确，无二义性。 可行性——算法的每步操作必须是基本的，它们的原则上都能够精确地进行，用笔和纸做有穷次就可以完成。 有穷性和可行性是算法最重要的两个特征。 2.2 ：算法与数据结构：算法建立数据结构之上，对数据结构的操作需用算法来描述。 算法设计依赖数据的逻辑结构，算法实现依赖数据结构的存储结构。 2.3 ：算法的设计应满足五个目标：正确性：算法应确切的满足应用问题的需求，这是算法设计的基本目标。 健壮性：即使输入数据不合适，算法也能做出适当的处理，不会导致不可控结

数据结构-C语言描述(第三版)张乃孝

数据结构-C语言描述（第三版） 高等教育出版社，张乃孝 第五章，二叉树与树 1. 用三个结点A,B,C可以构成多少种不同的二叉树？ 0表示根结点，前一个1，2表示层数（1第一层，2第二层），后面的1,2.（1表示左子树，2表示右子树） 层数为1的情况(11 326 C C=） A0B11C12，A0C11B12，B0A11C12，B0C11A12，C0A11B12，C0B11A12， 层数为2的情况（1111 322224 C C C C=） A0B11C21，A0B11C22，A0B12C21，A0B12C22,A0C11B21，A0C11B22，A0C12B21，A0C12B22 B0A11C21，B0A11C22，B0A12C21，B0A12C22,B0C11A21，B0C11A22，B0C12A21，B0C12A22 C0A11B21，C0A11B22，C0A12B21，C0A12B22,C0B11A21，C0B11A22，C0B12A21，C0B12A22 总计30种情况。 2 先根次序周游 ABECFDGHIJKL 中根次序周游EBFCDAIJKHGL 后根次序周游EFDCBKJIHLGA 4 .I(内部路径长度),E(外部路径长度),n(内部结点个数) n=12 I=28 E=I+2n E=52

8题 后根次序周游 DGEBHJIFCA 10 根结点 a 叶结点 efghd 分枝结点 ac a 度数3 层数0 b度数1 层数1 c度数3 层数1 d度数0 层数1 e,f,g,h度数0 层数2 1. 写一个算法来计算给定二叉树的叶结点数。 int num_of_leaves(BinTree t) { if (t = = NULL) return 0; /*空树，返回0*/ if (t->llink = = NULL && t->rlink = = NULL) return 1; /*根结点是树 叶，返回1*/ return num_of_leaves(t->llink) + num_of_leaves(t->rlink); /*返回“左子树的叶结点数+右子树的叶结点数”*/ }