带的数据结构补充习题资料.docVIP

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