数据结构复习题 及答案.doc

一、填空。 1．顺序存储结构的特点是（ 静态存储的物理次序和逻辑次序一致 ），链式存储结构的特点式（ 动态存储的物理次序和逻辑次序不一定一致 ）。 2．算法在遇到非法操作时可以作出合理处理的特性为（ 健壮性 ）。 3．常见的算法时间复杂度用大O记号表示为：常数阶（ O(1) ），对数阶（ O(log2n ) ），线性阶（O(n) ），平方阶( O(n2) )和指数阶（ O(2n) ）。 4．在单链表中，除了头结点以外，任一结点的存储位置由（ 其直接前驱的指针域 ）指示。 5．当线性表采用顺序存储结构时，其主要特点是（ 静态存储物理次序和逻辑次序一致）。 6．在双链表中，每个结点设置了两个指针域，其中一个指向（ 直接前驱 ）结点，另一个指向（ 直接后继 ）结点。 7．设有一个空栈，栈顶指针为1000H，现有输入序列为1，2，3，4，5，经过push,push,pop,push,pop,push,push后，输出序列是（ 2,3 ），栈顶指针是（ 1003 H ）。 8．栈S通常采用的两种存储结构是（ 顺序存储和链序存储 ）；其判定栈空的条件分别是（ s-top==-1 top-next==NULL ）, 判定栈满的条件分别是（ s-top==stack_size-1 ）。 9．（ 栈 ）可作为实现递归函数调用的一种数据结构。 10．栈和队列是两种特殊的线性表，栈的操作特性是（ 先进后出 ），队列的操作特性是（ 先进先出 ），栈和队列的主要区别是（ 栈是在表的一端进行操作，队列是在表的两端进行操作 ）。 11．循环队列的引入是为了克服（ 假溢出 ）。 12．数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为 ( (front-rear+n）mod n ）。 13．用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别为（ O(1) ）和（ O(n) ）。 14．串是一种特殊的线性表，其特殊性体现在（ 串的数据限定为字符集 ）。 15．两个串相等的充分必要条件是（ 两个串的长度相等 并且每个对应位置的字符都相等 ）。 16．（ 数据元素 ）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。 17．从逻辑关系上讲，数据结构主要分为（ 集合结构 ）、（ 线性结构 ）、（ 树形结构 ）、（ 图状结构或网状结构 ）。 18．数据的存储结构主要有（ 顺序 ）和（ 非顺序 ）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（ 数据的表示）和（ 关系的表示 ）。 19．算法具有5个特性，分别是（ 可行性，有限性，确定性，输入和输出 ） 20．顺序表中第一个元素的地址是100，每个元素的长度为2，则第五个元素的存储地址是（ 108 ）。 21．单链表中设置头指针的作用是（ 标识链表在内存中的位置 ）。 22、设单链表中指针P指向结点A，若要删除A的后继结点（假设A存在后继结点），则修改指针的操作为（ p-next=p-next-next; ）。 23．设S=”I AM A TEACHER”,其长度为（ 14 ）。 24．对于栈和队列，无论它们采用顺序存储结构还是链式存储结构，进行插入和删除操作的时间复杂度都是（ O(1) ）。 25．数组通常有两种运算：（ 获得特定位置的元素值 ）和（ 修改特定元素的值 ），这决定了数组通常采用（ 顺序 ）结构来存储。 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]中，若按行优先存储，则A