数据结构习题带答案.pdf

补充习题 第一章至第五章 一、单选或填空题 1. 下列程序段中 S 语句的执行频度为 。 for(i ＝0 ；i ＜n ；i++ ） for(j ＝0 ；j ＜i ；j++ ） S ； 2. 下列算法的时间复杂度是（ ）。 for(i ＝0 ；i ＜n ；i++ ） c[i] ＝i ； 3. 算法的时间复杂度可表示为 O(1) 、线性阶 、平方阶 O(n2) 、对数阶 n O(logn)和指数阶 O(2 )等。 4 以下关于数据结构的基本概念中，叙述正确的是 A) 数据元素是数据不可分割的最小单位。 B) 数据是数据对象的子集。 C) 数据元素之间的关系在计算机中可用顺序映像和非顺序映像两种不同的方法表示。 D) 数据结构在计算机中的表示又称为逻辑结构。 5. 在数据结构中，数据的逻辑结构包括（ ）。 A) 线性结构和非线性结构 B) 逻辑结构和物理结构 C) 顺序结构和链式结构 D) 虚拟结构和抽象结构 6. 在数据结构中，数据的存储结构包括 。 　 A) 线性结构和非线性结构 B) 逻辑结构和物理结构 　C) 顺序结构和链式结构 D) 虚拟结构和抽象结构 7. 线性结构的数据元素之间存在一种( ) 。 A ．一对多关系 B ．多对多关系 C ．多对一关系 D ．一对一关系 8. 在长度为 n 的顺序表中插入一个元素，需要平均移动 个元素。 A) n/2 B)n C) n(n-1) D) n(n+1) 9. 在有 n 个元素的顺序表中做插入、删除运算，平均时间复杂度为 。 10. 顺序表中逻辑上相邻的元素物理位置 相邻，单链表中逻辑上相邻的元素的物理位 置 相邻。 A)必然、必然 B)必然、不一定 C)不一定、必然 D)不一定、不一定 11．相对于顺序存储而言，链式存储的优点是（ ）。 A ．随机存取 B ．节约空间 C ．增、删操作方便 D ．节点间关系简单 12 以下关于头结点的描述中，叙述错误的是 ．． A) 头结点是对链表首元结点的别称 B) 若链表中附设头结点，则头指针一定不为空 C) 头结点中不存储链表的数据元素，而是一些诸如表长之类的辅助信息 D) 在单链表中附设头结点，插入或删除首元素时不必进行特殊处理 13．已知 L 是无表头结点的单链表，且 P 所指结点既不是首元结点，也不是尾元结点，则 在 P 之后插入 S 所指结点，则执行（ ）。 A) S-next=P-next ； P-next=S ； B) P-next=S-next ； S-next=P ； C) S-next=P； P-next ＝S； D) P-next=S ； S-next=P ； 14. 已知L 是带表头结点的非空单链表，且 P 结点是 S 结点的直接前驱。则删除 S 结点的语 句序列为 。 I. P-next = S ;free(P) II. P-next = P-next-next; free(S)