1-4章习题2015论述.doc

一、名词解释（见教材） 数据结构、数据结构的逻辑结构、数据结构的物理结构、算法、算法评价、时间复杂度、大O表示法、线性表、栈、队列、广义表、稀疏矩阵 二、填空 1、数据的逻辑结构被分为_集合结构_、_线性结构___、_树形结构__、__图形结构__4种。 2、数据的存储结构被分为_顺序结构__、链接结构_、索引结构_、和__散列结构__4种。 3、在定义某种数据结构时，其数据域的数据类型可分为 简单类型 和 结构体类型 两种，为增强其通用性，应将其再定义为 通用数据 类型。 4、如果将线性数据结构关系描述为1：1，那么树型和图型数据结构应分别为 1：N 、 M：N 。 5、数据结构简单地说是指 数据 以及相互之间的 联系 。 6、算法应具备以下5个特性： 有穷性 、 正确性 、 可行性 、输入和输出。 7、在分析各种算法的时间复杂度时，一般只讨论相应的数量级，用f(n)表示，请问其中n的含义是 处理问题的样本量 。 8、对于一个单链表，在表头插入结点的时间复杂度为 O(1) ，在表尾插入元素的时间复杂度为 O(n) 。 9、 在表长为n的顺序表中，在等概率情况下，插入和删除一个元素平均需移动 表长的一半（即n/2 ） 个元素，具体移动元素的个数与表长（n） 和 该元素在表中的位置 有关。 10、顺序表的定义如下： typedef int ElemType; struct List{ ElemType *list; int size; int MaxSize; }; 其中ElemType的含义是：通用数据 类型；size的含义是：顺序表中元素的个数。 11、 设单链表中指针p 指向结点A，q指针指向其后继结点。若要删除A的后继结点（假设A存在后继结点），则需修改指针的操作为p-next=q-next;。 12、栈的运算规则为 后进先出 ，队列的运算规则为 先进先出 。 13、一个函数调用了自身，这是 递归 调用。 14、非零元素个数远远少于零元素个数的矩阵称为 稀疏矩阵 。 非零元素所在的 行 ；t的含义是：非零元素的个数。 三、选择题 1、顺序表物理结构中的存储单元（ A ）。 A. 一定是连续的 B. 一定是不连续的 C. 不一定是连续的 D. 经删除操作后不连续 2、对一个线性表的存取操作很少，而插入和删除操作较多时应采用 B 数据结构。 A．线性表 B. 队列 C. 图 D. 树 3、对一个线性表的随机读取操作较多时，应采用 B 存储结构。 A.静态顺序存储 B. 动态顺序存储 C. 动态链接存储 D. 静态链接存储 4、 顺序表适用于（ A ） 的场合。 A. 频繁查询 B. 频繁插入与删除 C. 问题规模较小 D. 问题规模较大 5、 链表不具有的特点是（A ）。 A． 可随机访问任一元素 B. 插入、删除不需要移动元素 C. 不必事先估计存储空间 D. 所需空间与线性表长度成正比 6、栈的插入和删除操作在（ A ）进行。 A．栈顶 B．栈底 C．栈顶或栈底 D．任意位置 7、向一个顺序栈S（栈顶指针为top）中插入元素x时，首先要（ B ）。 A．S-stack[S-top]=x; B．S-top++; C．S -top--; D．x= S-stack[S-top]; 8、对一个顺序存储结构的栈，栈满的判断条件是（ D ） A.S.top= =-1 B.S.top= =0 C.S.top= =MaxSize D. S.top= =MaxSize-1 9、若循环队列有 n个顺序存储单元，front、rear分别为队首和队尾元素的下标，front指向队首元素之前的一个位置，为则判断队满的条件是(C) A. front = =rear B. (front-1)%n= =rear C. (rear+1) %n= =front D. (rear-1)%n= = front 10、若循环队列有 n个顺序存储单元，front、rear分别为队首和队尾元素的下标，front指向队首元素之前的一个位置，为则判断队空的条件是(A) A. front = =rear B. (front-1)%n= =rea