发布时间 : 星期日 文章数据结构习题集2015更新完毕开始阅读
数据结构作业
2014-2015第2学期
课程： 学院： 专业： 班级： 姓名： 学号：
数据结构 计算机学院 网络工程 14（1）班
- 1 -
淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 2
第1章 绪论
一、选择题：
1、下列算法的时间复杂度是（ ） for(i=0;i A．O（1） B．O（n） C．O（log2n） D．O（nlog2n） 2、数据在计算机存储器内表示时，根据结点的关键字直接计算出该结点的存储地址，这种方法称为（ ） A．索引存储方法 B．顺序存储方法 C．链式存储方法 D．散列存储方法 3、以下哪一个术语与数据的存储结构无关？（ ）。 A.顺序表 B.链表 C.散列表 D.队列 4、算法在发生非法操作时可以做出处理的特性称为（ ）。 A．正确性 B．易读性 C．健壮性 D．高效性 5、逻辑结构是指数据元素的（ ）。 A．关联方式 B．存储方式 C．结构 D．数据项 6、研究数据结构就是研究（ ）。 A．数据的逻辑结构 B．数据的存储结构 C．数据的逻辑结构和存储结构 D．数据的逻辑结构、存储结构及其数据的运算 7、从逻辑上可以把数据结构分为（ ）。 A.动态结构和静态结构 B.紧凑结构和非紧凑结构 C.线性结构和非线性结构 D.内部结构和外部结构 8、以下有关数据的叙述中错误的是（ ）。 A．计算机能够处理的数据包括整数、实数、字符、声音、图像等 B．数据的逻辑结构是从逻辑关系上描述数据，它取决于数据的存储方式 C．数据存储结构的实现依赖于计算机语言 D．数据的运算是定义在数据的逻辑结构上的 9、数据的基本单位是（ ）。 A.数据结构 B.数据元素 C.数据项 D.文件 10、下列算法的时间复杂度是（ ） for(i=0;i for(j=0;j A．O（m2） B．O（n2） C．O（m×n） D．O（m+n） 11、算法分析的两个主要方面是（ ）。 A．正确性和简明性 B．数据复杂性和程序复杂性 C．可读性和可维护性 D．时间复杂性和空间复杂性 12、与数据元素本身的形式、内容、相对位置、个数无关的是数据的（ ）。 A．存储结构 B．逻辑结构 C．算法 D．操作 13、下列叙述中正确的是( )。 A．一个逻辑数据结构只能有一种存储结构 B．数据的逻辑结构属于线性结构，存储结构属于非线性结构 淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 3 C．一个逻辑数据结构可以有多种存储结构，且各种存储结构不影响数据处理的效率 D．一个逻辑数据结构可以有多种存储结构，且各种存储结构影响数据处理的效率 二、填空题： 1、数据结构是相互之间存在一种或多种特定关系的数据元素的集合，它包括三方面的内容，分别是数据的逻辑结构、（ ）和（ ）。 2、( )结构与数据元素本身的内容和形式无关。 3、程序段“for(i=1;i<=n;i++) {k++; for(j=1;j<=n;j++) x=x+k;}”的时间复杂度为( )。 4、数据结构是一门研究非数值计算的程序设计问题中计算机的（ ）以及它们之间的（ ） 和运算等的学科。 5、数据结构被形式地定义为（D, R），其中D是（ ） 的有限集合，R是D上的（ ） 有限集合。 6、数据结构按逻辑结构可分为两大类，它们分别是（ ） 和（ ） 。 7、线性结构中元素之间存在（ ）关系，树形结构中元素之间存在（ ）关系，图形结构中 元素之间存在（ ）关系。 8、在线性结构中，（ ）没有 前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点 （ ） 后续结点，其余每个结点有且只有1个后续结点。 9、在树形结构中，树根结点没有 （ ）结点，其余每个结点有且只有（ ）个前驱结点；叶子结 点没有（ ）结点，其余每个结点的后续结点数可以任意多个。 10、在图形结构中，每个结点的前驱结点数和后续结点数可以（ ） 。 11、对于给定的n个元素,可以构造出的逻辑结构有（ ）四种。 12、顺序映象的特点是借助元素在存储器中的（ ）来表示数据元素之间的逻辑关系。 非顺序映象的特点是借助是指示元素存储地址的（ ）表示数据元素之间的逻辑关系。任何一个算法的设计取决于选定（ ）结构，而算法的实现依赖于采用的（ ）结构。 13、数据类型是一组（ ）的值集合以及定义在这个值集合上的一组操作的总称。 14、数据对象是（ ）数据元素的集合，是数据的一个子集。 三、判断题： 1、顺序存储方式优点是存储密度大，且插入和删除运算效率高。 （ ） 2、顺序存储结构属于静态存储结构，链式存储结构属于动态存储结构。 （ ） 3、线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。 （ ） 4、数据的机内表示称为数据的存储结构。 （ ） 5、在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。（ ） 6、数据元素是数据的最小单位。 （ ） 7、基于某种逻辑结构之上的运算，其实现是惟一的。 （ ） 成绩____________ 日期____________________ 淮南师范学院 计算机学院 网络工程14（1）班 数据结构作业 4 第2章 线性表 一、 选择题： 1、在表长为n的顺序表上做插入运算，平均要移动的结点数为（ ）。 A．n B．n/2 C．n/3 D．n/4 2、在一个单链表中，若P所指结点不是最后结点，在P之后插入S所指结点，则执行（ ） A．S->next=P->next;P->next=S B．P->next=S->next;S->next=P； C．P->next=P;P->next=S； D．P->next=S;S->next=P； 3、在已知头指针的单链表中，要在其尾部插入一新结点，其算法所需的时间复杂度为（ ） A．Ｏ（1） B．Ｏ（log2n） C．O（n） D．O（n2） 4、对于只在表的首、尾两端进行插入操作的线性表，宜采用的存储结构为（ ） A．顺序表 B．用头指针表示的单循环链表 C．用尾指针表示的单循环链表 D．单链表 5、线性表是（ ） A．一个有限序列，可以为空 B．一个有限序列，不能为空 C．一个无限序列，可以为空 D．一个无限序列，不能为空 6、在n个结点的双链表的某个结点前插入一个结点的时间复杂度是（ ） A．O（n） B．O（1） C．O（log2n） D．O（n2） 7、线性表采用链式存储时，结点的地址（ ） A．必须是连续的 B．必须是不连续的 C．连续与否均可 D．必须有相等的间隔 8、在单链表中，增加头结点的目的是（ ） A．使单链表至少有一结点 B．标志表中首结点位置 C．方便运算的实现 D．说明单链表是线性表的链式存储实现 9、带头结点的单链表head为空的判定条件是（ ） A．head = NULL； B．head - > next = NULL； C．head - > next = head； D．head ! = NULL； 10、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度为（ ） A．Ｏ（1） B．Ｏ（n） C．Ｏ（n2） D．Ｏ（log2n） 11、下列有关线性表的叙述中，正确的是（ ） A．线性表中的元素之间是线性关系 B．线性表中至少有一个元素 C．线性表中任何一个元素有且仅有一个直接前趋 D．线性表中任何一个元素有且仅有一个直接后继 12、在单链表中，存储每个结点需有两个域，一个是数据域，另一个是指针域，它指向该结点的（ ） A．直接前趋 B．直接后继 C．开始结点 D．终端结点 13、将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是（ ）。 A．n B.2n-1 C.2n D.n-1 14、链表不具有的特点是（ ）。 A．随机访问 B．不必事先估计存储空间 C．插入删除时不需移动元素 D．所需的空间与线性表成正比 15、在一个单链表中，已知q所指结点是p所指结点的直接前趋，若在p，q之间插入s结点，则执行的 操作是（ ）。 A．s->next=p->next;p->next=s; B．q->next=s;s->next=p;