14章习题2012.docVIP

一、名词解释（见教材） 数据结构、数据结构的逻辑结构、数据结构的物理结构、算法、算法评价、时间复杂度、大O表示法、线性表、栈、队列、广义表、稀疏矩阵 二、填空 1、数据的逻辑结构被分为 _、_ ___、_ __、_ __4种。 2、数据的存储结构被分为_ __、 _ _2种。 3、在定义某种数据结构时，其数据域的数据类型可分为 和 两种，为增强其通用性，应将其再定义为 类型。 4、如果将线性数据结构关系描述为1：1，那么树型和图型数据结构应分别为 、 。 5、数据结构简单地说是指 以及相互之间的 。 6、算法应具备以下5个特性： 、 、 、输入和输出。 7、在分析各种算法的时间复杂度时，一般只讨论相应的数量级，用f(n)表示，请问其中n的含义是 。 8、对于一个单链表，在表头插入结点的时间复杂度为 ，在表尾插入元素的时间复杂度为 。 在表长顺序表中，等概率情况下，插入和删除一个元素平均需移动个元素，具体移动元素的个数与和有关。typedef int ElemType; struct List{ ElemType *list; int size; int MaxSize; }; 其中ElemType的含义是：通用数据 类型；size的含义是： 。 11、 设单链表中指针p 指向结点A，若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为。 12、栈的运算规则为 ，队列的运算规则为 。 13、一个函数调用了自身，这是 调用。 14、非零元素个数远远少于零元素个数的矩阵称为 。 15、顺序存储的稀疏矩阵采用三元组线性表存储，定义如下： struct Triple{ int row,col; ElemType val; }; struct SMatrix{ int m,n,t; struct Triple sm[11]; }; 其中row的含义是：非零元素所在的 ；t的含义是：非零元素的 。 三、选择题 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. 所需空间与线性表长度成正比 栈的插入和删除操作在进行。 A．栈顶 B．栈底 C．栈顶栈底 D．任意位置 一个栈元素时，首先要 ）。 A．B．C．D． ） A.S.top= =-1 B.S.top= =0 C.S.top= =MaxSize D. S.top= =MaxSize-1 9、若循环队列有 n个顺序存储单元，front、rear分别为队首和队尾元素的下标，front指向队首元素之前的一个位置，为则判断队满的条件是( ) A. front = =rear B. (front-1)%n= =rear C. (rear+1) %n= =front D. (rear-1)%n= = front 10、若循环队列有 n个顺序存储单元，front、rear分别为队首和队尾元素的下标，front指向队首元素之前的一个位置，为则判断队空的条件是( ) A. front = =rear B. (front-1)%n= =rear C. (rear+1) %n= =front D. (rear-1)%n= = front 11、队的插入操作在进行。 A． B． C． D．任意位置for (i