数据结构复题 及答案.doc

《数据结构复题 及答案.doc》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、一、填空。1．顺序存储结构的特点是（静态存储的物理次序和逻辑次序一致），链式存储结构的特点式（动态存储的物理次序和逻辑次序不一定一致）。2．算法在遇到非法操作时可以作出合理处理的特性为（健壮性）。3．常见的算法时间复杂度用大O记号表示为：常数阶（O(1)），对数阶（O(log2n)），线性阶（O(n)），平方阶(O(n2))和指数阶（O(2n)）。4．在单链表中，除了头结点以外，任一结点的存储位置由（其直接前驱的指针域）指示。5．当线性表采用顺序存储结构时，其主要特点是（静态存储物理次序和逻辑次序一致）。6．在

2、双链表中，每个结点设置了两个指针域，其中一个指向（直接前驱）结点，另一个指向（直接后继）结点。7．设有一个空栈，栈顶指针为1000H，现有输入序列为1，2，3，4，5，经过push,push,pop,push,pop,push,push后，输出序列是（2,3），栈顶指针是（1003H）。8．栈S通常采用的两种存储结构是（顺序存储和链序存储）；其判定栈空的条件分别是（s->top==-1top->next==NULL）,判定栈满的条件分别是（s->top==stack_size-1）。9．（栈）可作为实现递归函数

3、调用的一种数据结构。10．栈和队列是两种特殊的线性表，栈的操作特性是（先进后出），队列的操作特性是（先进先出），栈和队列的主要区别是（栈是在表的一端进行操作，队列是在表的两端进行操作）。11．循环队列的引入是为了克服（假溢出）。12．数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为((front-rear+n）modn）。13．用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别为（O(1)）和（O(n)）。14．串是一

4、种特殊的线性表，其特殊性体现在（串的数据限定为字符集）。15．两个串相等的充分必要条件是（两个串的长度相等并且每个对应位置的字符都相等）。16．（数据元素）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。17．从逻辑关系上讲，数据结构主要分为（集合结构）、（线性结构）、（树形结构）、（图状结构或网状结构）。18．数据的存储结构主要有（顺序）和（非顺序）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（数据的表示）和（关系的表示）。19．算法具有5个特性，分别是（可行性，有限性，确定性，输入

5、和输出）20．顺序表中第一个元素的地址是100，每个元素的长度为2，则第五个元素的存储地址是（108）。21．单链表中设置头指针的作用是（标识链表在内存中的位置）。22、设单链表中指针P指向结点A，若要删除A的后继结点（假设A存在后继结点），则修改指针的操作为（p->next=p->next->next;）。23．设S=”IAMATEACHER”,其长度为（14）。24．对于栈和队列，无论它们采用顺序存储结构还是链式存储结构，进行插入和删除操作的时间复杂度都是（O(1)）。25．数组通常有两种运算：（获得特定位

6、置的元素值）和（修改特定元素的值），这决定了数组通常采用（顺序）结构来存储。26．设有一个10阶的三角矩阵A采用压缩存储（按行序存储），A[0][0]为第一个，其存储地址为d，每个元素占一个存储单元，则元素A[8][5]的存储地址为（d+41）。27．稀疏矩阵压缩存储的方法有两种，分别是（三元组表表示法）和（十字链表法）。28．一个n×n的对称矩阵，按行优先或列优先进行压缩存储，则其存储容量为（n(n+1)/2）。29．设n×n的下三角矩阵A（行列下标均从1开始）已压缩到一维数组S[1]到S[n(n+1)/2]

7、中，若按行优先存储，则A[i][j]在数组S中的存储位置是（i(i-1)/2+j-1）。30．树是n(n≥0)个结点的有限集合，在一棵非空树中，有（1）个根结点，其余结点分成m(m≥0)个（互不相交的有限集）的集合，每个集合都是根结点的子树。31．树中某结点的子树的个数称为该结点的度，子树的根结点称为该结点的（孩子结点），该结点称为子树根结点的（双亲结点）。32．一棵二叉树的第i(i≥1)层最多有（2i-1）个结点，一棵有n(n>0)个结点的满二叉树共有（(n+1)/2）个叶子结点和（(n-1)/2）个非终端结

8、点。33．深度为k的二叉树中所含叶子的个数最多为（2k-1）。34．某二叉树的先序遍历序列是ABCDEFG,中序遍历序列是CBDAFGE，则其后序遍历序列是（CDBGFEA）。35．在具有n个结点的二叉链表中，共有（2n）个指针域，其中(n-1）指针域是指向其左右孩子。36．在有n个叶子的哈夫曼树中，分支结点总数为（n-1）。37．设无向图G中顶点数n,则图G至少有(0)条边，至多有（