数据结构(专)阶段练习1new.doc

华东理工大学网络学院（专科） 《数据结构》（ch1绪论和ch2线性表） 班级 学号 姓名 成绩 名词解释（每小题2分，共10分） 1.数据结构逻辑结构存储结构线性结构非线性结构数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。 逻辑结构：指数据元素之间的逻辑关系。 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构。 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。 （√）2. 单链表中逻辑上相邻的元素未必在存储的物理位置次序上相邻。 （√）3. 顺序表中逻辑上相邻的元素的物理位置必定相邻。 （×）4. 链式存储是一种随机存取的数据结构。 （×）5. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。 （√）6. 在顺序表中按下标序号访问任意一结点的时间复杂度均为O 1 。 （√）7. 在顺序表中插入或删除一个元素，需要平均移动表中一半元素。 （√）8. 带头结点的单向链表L为空的判定条件是L- next null。 （×）9. 线性表的逻辑顺序与存储顺序总是一致的。 （√）10. 任何一个算法的设计取决于选定的数据（逻辑）结构，而算法的实现依赖于采用的存储结构。 四、单选题（每题2分，共30分） 1.有程序如下： i 1; k 0;? while i n k k+10*i;i++; 该程序段的时间p所指结点之后插入结点s的操作是 D 。 A p- next s; s- prior p; p- next- prior s; s- next p- next B p- next s; p- next- prior s; s- prior p; s- next p- next C s- prior p; s- next p; p- next s; p- next- prior s D s- prior p; p- next s; s- next p- next ;p- next- prior s; 5. 在n个结点的带头结点的单链表中，要在已知结点*p之后插入一个新结点，则其操作的时间复杂度为 A 。 A O（1） B O n C O n+1 D O n2 6. 在n个结点的带头结点的单链表中，要在已知结点*p之前插入一个新结点，则其操作的时间复杂度为 B 。 A O（1） B O n C O n+1 D O n2 7. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动 B 个元素。 A 8 B 63.5 C 63 D 7 8. 在n个结点的单链表中，算法的时间复杂度是O n 的操作是 A ： A 求链表的第i个结点 B 在地址为p的结点之后插入一个结点 C 删除开始结点 D 删除地址为p的结点的后继结点 9. 在n个结点的顺序表中，算法的时间复杂度是O 1 的操作是 A ： A 访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n） B 在第i个结点后插入一个新结点（1≤i≤n） C 删除第i个结点（1≤i≤n） D 将n个结点从小到大排序 10. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是 B A 110 B 108 C 100 D 120 11. 对于只在表的首、尾进行插入操作的线性表，宜采用的存储结构为： C A 顺序表 B 用头指针表示的单循环链表C 用尾指针表示的单循环链表 D 单链表 12. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址： D A 必须是连续的 B部分地址必须是连续的 C 一定是不连续的 D 连续或不连续都可以 13. 有一个带头结点的双向循环链表，头指针为head, 则其为空的条件是： C A head- prior NULL B head- next NULL C head- next head D head- next- prior NULL 14. 若一个算法中的语句频度之和为T n 37n+4nlogn+5n2，则算法的时间复杂度为____D_________ 。 A O（1） B O n C O n