数据结构总复习题(da-an).doc

《数据结构总复习题(da-an).doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构总复习题一、填空题1.数据结构是研究数据的__逻辑结构_和_物理结构，并在这种结构上定义相关的运算，设计实现这些运算的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为___时间复杂度__和__空间复杂度___。学号2.数据的基本单位是__数据元素，数据的最小单位是__数据项。3.算法是对特定问题求解___步骤____的一种描述，是指令的有限序列。4.一个算法的时间复杂度为(3n3+2n—7)，其数量级表示为O（n3）。5.一个算法具有5个特性：确定性、可行性、有穷性、输入和输出。6.算法性能的分析和度量，可以从算法的时间复杂度和空

2、间复杂度来评价算法的优劣。学号7.数据的逻辑结构包括集合结构、线性结构、树形结构和图型结构四种类型。8.通常象交通、道路问题的数学模型是一种称为图型结构的数据结构。9.数据结构在计算机中的表示称为数据的物理结构，它可以采用___顺序存储___或_链式存储__两种存储方法。10.线性表有两种存储结构，分别为顺序存储和链式存储。11.链式存储的特点是利用指针来表示数据元素之间的逻辑关系。姓名12.若频繁地对线性表进行插入和删除操作，该线性表宜采用_链式存储____存储结构。13.线性表中的数据元素之间具有一对一的线性关系，除第一个和最后一个元素外，其他数据元

3、素有且只有一个直接后继和直接前趋。14.顺序表中逻辑上相邻的元素的物理位置_也相邻____。15.在单链表L中，指针P所指结点有后继结点的条件是__p->next!=NULL__。16.在顺序存储的线性表中插入或删除一个元素平均约移动表中__50%_（或一半）_的元素.17.在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=_p->next__和p->next=__s____的操作。18.在一个单链表中删除p的后继结点q时，应执行以下操作p->next=q->next。19.对带头结点head的单链表，则判断其为空的条件为head-

4、>next=NULL。20.对带头结点head的循环单链表尾结点(由p所指向)判非空的条件为p->next=head。21.在栈结构中，允许插入的一端称为栈顶；在队列结构中，允许插入的一端称为队尾。22.栈是一种特殊的线性表，它允许在表的一端进行_插入和删除___操作，栈中元素的进出原则为__先进后出__。23.队列中元素的入队和出队应遵循_先进先出___原则，数据元素1，2，3，4，5按照次序入队后，第一个出队的是__1____。1.在循环队列中，存储空间为0～n-1。设队头指针front指向队头元素前一个空闲元素，队尾指针指向队尾元素，那么其队空标志

5、为rear=front，队满标志为(rear+1)%n=front。2.假定一个顺序队列的对首和队尾分别为f和r，则判断队空的条件为_f=r____。3.设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存储地址为239。4.在一个长度为n的顺序表中删除第i个元素（1≤i≤n），需向前移动n-i个元素。5.在一个长度为n的顺序表中第i个元素前（1≤i≤n），插入一个元素，需向后移动n-i+1个元素。6.若线性表采用顺序存储结构，线性表的最大长度为1000，每个数据元素占3个存储单元，则要分配给该线性表____3000_

6、_____存储单元，若第一个数据元素的存储地址是2000，则第11个元素的存储地址是_____2030_____。7.二维数组有两种存储方式，第一种是以___行__为主序的存储方式，第二种是以___列__为主序的存储方式。现有一个二维数组A[6][7]，按第一种方式存储，A[0][0]的存储地址是1000，每个元素占5个字节，则元素A[3][5]的存储地址是___1115___。1000+(3*7+5)*58.设有一个二维数组A[5][4]，按行序优先存储，A[0][0]的存储地址是10，每个数组元素占2个字节，则A[3][2]的存储地址是_128(10

7、+(3*4+2)*2_)__。9.现有一个二维数组A[6][8]，若以行为主序顺序存储,A[0][0]的存储地址是2000，每个元素占2个字节，则元素A[3][5]的存储地址是____2046_。若以列为主序顺序存储,则元素A[3][5]的存储地址是_2086。10.两个串相等的充分必要条件是:___串长相等___且__对应的字符相等___。11.不含任何字符的串称为空串其长度为0。12.对于稀疏矩阵的压缩存储，通常用一个三元组表示非零元素的信息，其中包括非零元素所在的行、列以及它的值。13.若二叉树中有20个叶子结点，则该二叉树有19个度为2的结点。1

8、4.若二叉树中度为2的结点有15个，则该二叉树有___16____个叶子结点。1