数据结构单元练习参考答案

第1章单元测试1、算法的时间复杂度取决于___。

答案：A和B2、数据在计算机内存中的表示是指（）答案：数据的存储结构3、算法指的是（）答案：求解特定问题的指令有限序列4、在数据结构中，与所使用的计算机无关的数据结构是（）答案：逻辑7、某线性表采用顺序存储结构,每个元素占4个存储单元,首地址为100,则第12个元素的存储地址为( )。

答案：1448、算法能正确地实现预定功能的特性称为算法的（）。

答案：正确性第2章单元测试1、链表不具备的特点是（）。

答案：可随机访问任意一个结点3、线性表的顺序存储表示优于链式存储表示。

答案：错4、顺序存储结构的缺点是不便于修改,插入和删除需要移动很多结点。

答案：对5、在设头、尾指针的单链表中,与长度n有关的操作是( )。

答案：删除最后一个结点6、设指针q指向单链表中结点A,指针p指向单链表中结点A的后继结点B,指针s指向被插入的结点X,则在结点A和结点B间插入结点X的操作序列为( )。

答案：q->next=s; s->next=p;7、对于只在表的首、尾两端进行插入操作的线性表,宜采用的存储结构为( )。

答案：用尾指针表示的循环单链表8、在一个单链表中,若p所指节点不是最后节点,在p之后插入s所指节点,则执行( )。

答案：s->link=p->link;p->link=s;9、在双向链表存储结构中，删除p所指的结点时须修改指针____。

答案：p->next->prior=p->prior; p->prior->next=p->next;10、若事先不知道线性表的长度,则处理线性表时较好的存储结构是( )。

答案：单链表11、向一个有127个元素的顺序表中插入一个新元素并保存,原来顺序不变,平均要移动( )个元素。

答案：63.512、某线性表采用顺序存储结构,每个元素占4个存储单元,首地址为100,则第12个元素的存储地址为( )。

数据结构习题答案.doc单元练习1一．判断题（下列各题，正确的请在前面的括号内打√；错误的打╳）（√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。

（√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。

（ㄨ）（3）数据元素是数据的最小单位。

（ㄨ）（4）数据的逻辑结构和数据的存储结构是相同的。

（ㄨ）（5）程序和算法原则上没有区别，所以在讨论数据结构时可以通用。

（√）（6）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。

（√）（7）数据的存储结构是数据的逻辑结构的存储映像。

（√）（8）数据的物理结构是指数据在计算机内实际的存储形式。

（ㄨ）（9）数据的逻辑结构是依赖于计算机的。

（√）（10）算法是对解题方法和步骤的描述。

二．填空题（1）数据有逻辑结构和存储结构两种结构。

（2）数据逻辑结构除了集合以外，还包括：线性结构、树形结构和图形结构。

（3）数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。

（4）树形结构和图形结构合称为非线性结构。

（5）在树形结构中，除了树根结点以外，其余每个结点只有 1 个前趋结点。

（6）在图形结构中，每个结点的前趋结点数和后续结点数可以任意多个。

（7）数据的存储结构又叫物理结构。

（8）数据的存储结构形式包括：顺序存储、链式存储、索引存储和散列存储。

（9）线性结构中的元素之间存在一对一的关系。

（10）树形结构结构中的元素之间存在一对多的关系，（11）图形结构的元素之间存在多对多的关系。

（12）数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）三个方面的内容。

（13）数据结构被定义为(D，R)，其中D是数据的有限集合，R是D 上的关系的有限集合。

（14）算法是一个有穷指令的集合。

（15）算法效率的度量可以分为事先估算法和事后统计法。

（16）一个算法的时间复杂性是算法输入规模的函数。

（17）算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模n的函数。

最新版《数据结构》各章习题及答案第一章绪论一、选择题1.组成数据的基本单位是（）（A）数据项（B）数据类型（C）数据元素（D）数据变量2.数据结构是研究数据的（）以及它们之间的相互关系。

（A）理想结构，物理结构（B）理想结构，抽象结构（C）物理结构，逻辑结构（D）抽象结构，逻辑结构3.在数据结构中，从逻辑上可以把数据结构分成（）（A）动态结构和静态结构（B）紧凑结构和非紧凑结构（C）线性结构和非线性结构（D）内部结构和外部结构4.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。

① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像② （A）结构（B）关系（C）运算（D）算法5.算法分析的目的是（）。

（A）找出数据结构的合理性（B）研究算法中的输入和输出的关系（C）分析算法的效率以求改进（D）分析算法的易懂性和文档性6.计算机算法指的是（①）,它必须具备输入、输出和（②）等5 个特性。

① （A）计算方法（B）排序方法（C）解决问题的有限运算序列（D）调度方法② （A）可执行性、可移植性和可扩充性（B）可行性、确定性和有穷性（C）确定性、有穷性和稳定性（D）易读性、稳定性和安全性二、判断题1.数据的机内表示称为数据的存储结构。

（）2.算法就是程序。

（）3.数据元素是数据的最小单位。

（）4.算法的五个特性为：有穷性、输入、输出、完成性和确定性。

（）5.算法的时间复杂度取决于问题的规模和待处理数据的初态。

（）三、填空题1.数据逻辑结构包括________、________、_________ 和__________ 四种类型,其中树形结构和图形结构合称为_____ 。

2.在线性结构中,第一个结点____前驱结点,其余每个结点有且只有______ 个前驱结点；最后一个结点______后续结点,其余每个结点有且只有 _______ 个后续结点。

3.在树形结构中,树根结点没有_______ 结点,其余每个结点有且只有_______个前驱结点；叶子结点没有 ________ 结点,其余每个结点的后续结点可以_________。

数据结构第一教学单元单元测验答案一、选择1.下列叙述中关于好的编程风格，正确的描述是：A.程序中的注释是可有可无的B.对递归定义的数据结构不要使用递归过程C.递归应是封闭的，尽量少使用全局变量D.多采用一些技巧以提高程序运行效率答案：C算法应当要有良好的可读性,加上注释可以提高可读性,递归算法可读性也较强,而D可能可读性会不强2.通常从正确性、易读性、健壮性、高效性等四个方面评价算法(包括程序)的质量。

以下解释错误的是( )A.正确性算法应能正确地实现预定的功能(即处理要求)B.易读性算法应易于阅读和理解以便于调试修改和扩充C.健壮性当环境发生变化时，算法能适当地做出反应或进行处理，不会产生不需要的运行结果D.高效性即达到所需要的时间性能答案：C健壮性是输入数据非法时,算法也能适当做出反应,而不会得到莫名其妙的结果3.以下说法正确的是 ( )A.数据元素是数据的最小单位B.数据项是数据的基本单位C.数据结构是带有结构的各数据项的集合D.数据结构是带有结构的数据元素的集合答案：D数据元素是数据的基本单位,数据项是最小单位4.下面关于线性表的叙述中，错误的是哪一个？（）A.线性表采用顺序存储，必须占用一片连续的存储单元。

B.线性表采用顺序存储，便于进行插入和删除操作。

C.线性表采用链接存储，不必占用一片连续的存储单元。

D.线性表采用链接存储，便于插入和删除操作。

答案：B5.链表不具有的特点是：A.可随机访问任一个元素B.插入删除不需要移动元素C.不必事先估计存储空间D.所需空间与线性表长度成正比答案：A6.线性表是具有n个（）的有限序列A．表元素 B．字符 C．数据元素 D．数据项 E．信息项答案：C7.设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。

A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表答案：D8.线性表（ a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）A．O（i） B．O（1） C．O（n） D．O（i-1）答案C9.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。

题目：设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用（）排序法。

选项A：快速排序选项B：堆排序选项C：冒泡排序选项D：基数排序答案：堆排序题目：对数据元素序列（49，72，68，13，38，50，97，27）进行排序，前三趟排序结果时的结果依次为第一趟：49，72，68，13，38，50，97，27；第二趟：49，68，72，13，38，50，97，27；第三趟：13，49，68，72，38，50，97，27。

该排序采用的方法是（）。

选项A：冒泡排序法选项B：选择排序法选项C：插入排序法选项D：堆排序法答案：插入排序法题目：一组记录的关键字序列为（47，80，57，39，41，46），利用堆排序（堆顶元素是最小元素）的方法建立的初始化堆为（）。

选项A：39，47，46，80，41，57选项B：39，41，46，80，47，57选项C：39，80，46，47，41，57选项D：41，39，46，47，57，80答案：39，41，46，80，47，57题目：一组记录的关键字序列为（37，70，47，29，31，85），利用快速排序，以第一个关键字为分割元素，经过一次划分后结果为（）。

选项A：31，29，37，85，47，70选项B：31，29，37，47，77，85选项C：31，29，37，70，47，85选项D：29，31，37，47，70，85答案：31，29，37，47，77，85题目：下述几种排序方法中，要求内存量最大的是（）。

选项A：快速排序选项B：归并排序选项C：选择排序选项D：插入排序答案：归并排序题目：若待排序序列在排序前已按关键字递增排列，则采用（）方法比较次数最多。

选项A：直接选择排序选项B：归并排序选项C：归并排序。

单元2 同步训练及参考答案同步训练一、单项选择题1．线性表是（）的有限序列。

A．数据B．数据项C．数据元素D．表元素2．以下关于线性表的说法不正确的是（）。

A．线性表中的数据元素可以是数字、字符、记录等不同类型。

B．线性表中包含的数据元素个数不是任意的。

C．线性表中的每个结点都有且只有一个直接前驱和直接后继。

D．存在这样的线性表：表中各结点都没有直接前驱和直接后继。

3．顺序表是线性表的（）。

A．链式存储结构B．顺序存储结构C．索引存储结构D．散列存储结构4．对于顺序表的优缺点，以下说法错误的是（）。

A．无需为表示结点间的逻辑关系而增加额外的存储空间B．可以方便地随机存取表中的任一结点C．插入和删除运算较方便D．容易造成一部分空间长期闲置而得不到充分利用5．在顺序表中，只要知道（），就可在相同时间内求出任一结点的存储地址。

A．基地址B．结点存储长度C．向量大小D．基地址和存储长度6．一个顺序表第一个元素的存储地址是100，每个元素的存储长度为4，则第5个元素的地址是（）。

A．110 B．116 C．100 D．120 7．一个长度为n的顺序表中，在第i（1≤i≤n+1）个元素的位置上插入一个新元素时，需要向后移动个元素。

A．n-i B．n-i+1 C．n-i-1 D．i8．一个长度为n的顺序表中，删除第i（1≤i≤n）个元素时，需要向前移动（）个元素。

A．n-i B．n-i+1 C．n-i-1 D．i9．在一个长度为n的顺序表中插入一个结点需平均移动（）个结点。

A．（n+1）/2 B．n/2 C．（n-1）/2 D．n10．在一个长度为n的顺序表中删除一个结点需平均移动（）个结点。

A．（n+1）/2 B．n/2 C．（n-1）/2 D．n11．在（）情况下应当选择顺序表作为数据的存储结构。

A．对线性表的主要操作为插入操作B．对线性表的主要操作为插入操作和删除操作C．线性表的表长变化较大D．对线性表的主要操作为存取线性表的元素12．下列算法实现在顺序表L的第i（1≤i≤L->length+1）个结点的位置上插入值为t的元素，其中ListSize为顺序表L的容量，表中第1个结点的数据存放在数组元素L->data[0]中。

单元测验4一．判断题<下列各题，正确的请在前面的括号内打√；错误的打╳）<√）<1）队列是限制在两端进行操作的线性表。

<√）<2）判断顺序队列为空的标准是头指针和尾指针都指向同一个结点。

<×）<3）在链队列上做出队操作时，会改变front指针的值。

<√）<4）在循环队列中，若尾指针rear大于头指针front，其元素个数为rear- front。

<×）<5）在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是p=h。

<√）<6）链队列在一定范围内不会出现队满的情况。

<×）<7）在循环链队列中无溢出现象。

<×）<8）栈和队列都是顺序存储的线性结构。

<×）<9）在队列中允许删除的一端称为队尾。

<×）<10）顺序队和循环队关于队满和队空的判断条件是一样的。

二．填空题（1）在队列中存取数据应遵循的原则是先进先出。

（2）队列是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

（3）在队列中，允许插入的一端称为队尾。

（4）在队列中，允许删除的一端称为队首<或队头）。

（5）队列在进行出队操作时，首先要判断队列是否为空。

（6）顺序队列在进行入队操作时，首先要判断队列是否为满。

（7）顺序队列初始化后，front=rear= -1 。

（8）解决顺序队列“假溢出”的方法是采用循环队列。

循环队列的队首指针为front，队尾指针为rear，则队空的条件为 front == rear 。

（10）链队列LQ为空时，LQ->front->next= NULL 。

（11）设长度为n的链队列用单循环链表表示，若只设头指针，则入队操作的时间复杂度为 O<n）。

（12）设长度为n的链队列用单循环链表表示，若只设尾指针，则出队操作的时间复杂度为 0<1）。

单元练习8一．判断题〔以下各题，正确的请在前面的括号内打√；错误的打╳〕〔√〕〔1〕图可以没有边，但不能没有顶点。

〔ㄨ〕〔2〕在无向图中，〔V1，V2〕与〔V2，V1〕是两条不同的边。

〔ㄨ〕〔3〕邻接表只能用于有向图的存储。

〔√〕〔4〕一个图的邻接矩阵表示是唯一的。

〔ㄨ〕〔5〕用邻接矩阵法存储一个图时，所占用的存储空间大小与图中顶点个数无关，而只与图的边数有关。

〔ㄨ〕〔6〕有向图不能进展广度优先遍历。

〔√〕〔7〕假设一个无向图的以顶点V1为起点进展深度优先遍历，所得的遍历序列唯一，则可以唯一确定该图。

〔√〕〔8〕存储无向图的邻接矩阵是对称的，因此只要存储邻接矩阵的上三角〔或下三角〕局部就可以了。

〔ㄨ〕〔9〕用邻接表法存储图时，占用的存储空间大小只与图中的边数有关，而与结点的个数无关。

〔√〕〔10〕假设一个无向图中任一顶点出发，进展一次深度优先遍历，就可以访问图中所有的顶点，则该图一定是连通的。

二．填空题（1）图常用的存储方式有邻接矩阵和邻接表等。

（2）图的遍历有：深度优先搜和广度优先搜等方法。

（3）有n条边的无向图邻接矩阵中，1的个数是_2n____。

（4）有向图的边也称为_ 弧___。

（5）图的邻接矩阵表示法是表示__顶点____之间相邻关系的矩阵。

（6）有向图G用邻接矩阵存储，其第i行的所有元素之和等于顶点i的__出度____。

（7）n个顶点e条边的图假设采用邻接矩阵存储，则空间复杂度为： O〔n2〕。

（8）n个顶点e条边的图假设采用邻接表存储，则空间复杂度为： O〔n+e〕。

（9）设有一稀疏图G，则G采用_邻接表____存储比拟节省空间。

（10）设有一稠密图G，则G采用_邻接矩阵____存储比拟节省空间。

（11）图的逆邻接表存储构造只适用于__有向____图。

（12） n个顶点的完全无向图有 n(n-1)/2_ 条边。

（13）有向图的邻接表表示适于求顶点的出度。

（14）有向图的邻接矩阵表示中，第i列上非0元素的个数为顶点V i的入度。