精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆数据结构试题库及答案第一章 概论一、选择题1、讨论数据结构就是讨论（ D ）；B. 数据的储备结构A. 数据的规律结构C. 数据的规律结构和储备结构D. 数据的规律结构、储备结构及其基本操作2、算法分析的两个主要方面是（ A ）； A. 空间复杂度和时间复杂度 B. 正确性和简洁性 C. 可读性和文档性 D. 数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）；A. 图 B. 树 C. 广义表 D. 栈6、算法是（ D ）；A. 运算机程序 B. 解决问题的运算方法 C. 排序算法D. 解决问题的有限运算序列7、某算法的语句执行频度为（ 3n+nlog 2n+n 2+8 ）, 其时间复杂度表示（ C ）；A. O〔n〕 B. O〔nlog 2n〕 C. O〔n 2〕 D. O〔log 2n〕 11 、抽象数据类型的三个组成部分分别为（ A ）；A. 数据对象、数据关系和基本操作 B. 数 据 元 素 、 逻 辑 结 构 和 存 储 结 构C. 数据项、数据元素和数据类型 二、填空题 三、综合题D. 数据元素、数据结构和数据类型1、将数量级O〔1〕,O〔N〕,O〔N2〕,O〔N3〕,O〔NLOG2N〕,O〔LOG2N〕,O〔2N〕 按增长率由小到大排序；答案：O〔1〕 O〔log 2N〕 O〔N〕 O〔Nlog 2N〕 O〔N2〕 O〔N3〕 O〔2N〕 一、填空题1. 数据结构被形式地定义为 有限集合；（D, R ）,其中 D 是数据元素 的有限集合, R 是 D 上的 关系2. 数据结构包括数据的 规律结构 、数据的 储备结构 和数据的 运算 这三个方面的内容；3. 数据结构按规律结构可分为两大类,它们分别是线性结构 和非线性结构 ；名师归纳总结 8．数据的储备结构可用四种基本的储备方法表示,它们分别是次序、链式、索引、第 1 页,共 37 页- - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆散列 ；9. 数据的运算最常用的有5 种,它们分别是 插入、删除、修改、查找、排序；二、单项选择题（ C ）2. 数据结构中,与所使用的运算机无关的是数据的 结构；A〕 储备 B〕 物理 C〕 规律 D〕 物理和储备三、简答题1.数据结构和数据类型两个概念之间有区分吗？答：简洁地说,数据结构定义了一组按某些关系结合在一起的数组元素；数据类型不仅定义了一组带结构的数据元素, 而且仍在其上定义了一组操作；2. 简述线性结构与非线性结构的不同点；答：线性结构反映结点间的规律关系是一对一的,点间的规律关系是多对多的；非线性结构反映结四、分析下面各程序段的时间复杂度2. s=0; 1. for 〔i=0; inext=q;q->prior=p;p->next->prior=q;q->next=q; B. p->next=q;p->next->prior=q;q->prior=p;q->next=p->next; C. q->prior=p;q->next=p->next;p->next->prior=q;p->next=q; D. q->next=p->next;q->prior=p;p->next=q;p->next=q; 10 、线性表是 n 个（ ）的有限序列；A. 表元素 B. 字符 C. 数据元素 D. 数据项11 、从表中任一结点动身,都能扫描整个表的是（ ）；A. 单链表 B. 次序表 C. 循环链表 D. 静态链表12 、在具有 n个结点的单链表上查找值为 x 的元素时,其时间复杂度为（ ）；A. O〔n〕 B. O〔1〕 C. O〔n 2〕 D. O〔n-1〕 15 、性表的以下储备结构中,读取元素花费的时间最少的是（ ）； A. 单链表 B. 双链表 C. 循环链表 D. 次序表16 、在一个单链表中,如删除 p所指向结点的后续结点,就执行（ ）；A. p->next=p->next->next; B. p=p->next;p->next=p->next->next; C. p =p->next; D. p=p->next->next; 名师归纳总结 17 、将长度为 n 的单链表连接在长度为m的单链表之后的算法的时间复杂度为（）；第 3 页,共 37 页A. O〔1〕 B. O〔n〕 C. O〔m〕 D. O〔m+n〕 18 、线性表的次序储备结构是一种（ a ）储备结构； N A. 随机存取B. 次序存取C. 索引存取D. 散列存取19 、次序表中,插入一个元素所需移动的元素平均数是（）； A. 〔n-1〕/2 B. n C. n+1 D. 〔n+1〕/211 、不带头结点的单链表head 为空的判定条件是（ b ）；A. head==NULL B. head->next==NULL - - - - - - -精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆C. head->next==head D. head.=NULL 12 、在以下对次序表进行的操作中,算法时间复杂度为 O〔1〕 的是（ ）；A. 拜访第 i个元素的前驱（ 1< i n） B. 在 第 i 个 元 素 之 后 插 入 一 个 新 元 素〔 1 i n 〕C. 删除第 i个元素 〔 1 i n 〕 D. 对次序表中元素进行排序13 、已知指针 p和q分别指向某单链表中第一个结点和最终一个结点； 假设指针 s 指向另一个单链表中某个结点,就在 s 所指结点之后插入上述链表应执行的语句为（ a ）；A. q->next=s->next ；s->next=p ；B. s->next=p ；q->next=s->next ；C. p->next=s->next ；s->next=q ；D. s->next=q ；p->next=s->next ；15、在表长为 n 的次序表中, 当在任何位置删除一个元素的概率相同时, 删除一个元素所需移动的平均个数为（ a ）；A. 〔n-1〕/2 B. n/2 C. 〔n+1〕/2 D. n 二、填空题1、设单链表的结点结构为（data,next）；已知指针 p 指向单链表中的结点,q指向新结点,；欲将 q插入到 p结点之后,就需要执行的语句：；答案： q->next=p->next p->next=q3、写出带头结点的双向循环链表L 为空表的条件；答案： L->prior==L->next==L5、在一个单链表中删除 p所指结点的后继结点时,应执行以下操作：q = p->next; p->next=_ q->next ___; 三、判定题3、用循环单链表表示的链队列中,可以不设队头指针,仅在队尾设置队尾指针； x4、次序储备方式只能用于储备线性结构；5、性表的次序储备结构中,规律上相邻的两个元素但是在物理位置上不肯定是相邻的；6、链式储备的线性表可以随机存取；四、程序分析填空题1、函数 GetElem实现返回单链表的第i 个元素,请在空格处将算法补充完整；int GetElem〔LinkList L,int i,Elemtype *e〕{ LinkList p；int j； p=L->next;j=1; while〔p&&jnext ;++j; } if〔.p||j>i〕 return ERROR; *e= p->data ; return OK; } 名师归纳总结 - - - - - - -第 4 页,共 37 页精选学习资料 - - - - - - - - - 学而不思就惘,思而不学就殆2、函数实现单链表的插入算法,请在空格处将算法补充完整；int ListInsert〔LinkList L,int i,ElemType e〕{ LNode *p,*s;int j; p=L;j=0; while〔〔p.=NULL〕&&〔jnext;j++; } if〔p==NULL||j>i-1〕 return ERROR; s=〔LNode *〕malloc〔sizeof〔LNode〕〕; s->data。
