发布时间 : 星期五 文章数据结构习题更新完毕开始阅读144210a7195f312b3169a5d5
数据结构习题
第一章 绪论
一、单项选择题
1.与数据元素本身的形式、内容、相对位置、个数无关的是数据的( ) A.存储结构 B.逻辑结构 C.算法 D.操作 2. 以下说法错误的是（ ）。 A. 抽象数据类型具有封装性。
B. 抽象数据类型具有信息隐蔽性。
C. 使用抽象数据类型的用户可以自己定义对抽象数据类型中数据的各种操作。 D. 抽象数据类型的一个特点是使用与实现分离。 3．算法指的是（ ）
A．计算机程序 B．解决问题的计算方法 C．排序算法 D．解决问题的有限运算序列
4．在计算机存储器内表示时，物理地址和逻辑地址相同并且是连续的，称之为 A．逻辑结构 B．顺序存储结构 C．链表存储结构 D．以上都不对 5．算法分析的目的是 ① ，算法分析的两个主要方面是 ② 。 ①A．找出数据结构的合理性 B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进 D．分析算法的易懂性和文档性 ②A．空间复杂性和时间复杂性 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性
6．数据结构是一门研究非数值计算的程序设计问题中计算机的 ① 以及它们之间的 ② 和运算等的学科。
①A．操作对象 B．计算方法 C．逻辑存储 D．数据映象 ②A．结构 B．关系 C．运算 D．算法
7．数据结构被形式地定义为（K，R），其中K是 ① 的有限集合，R是K上的 ② 的有限集合。 ①A．算法 B．数据元素 C．数据操作 D．逻辑结构 ②A．操作 B．映象 C．存储 D．关系 8．在数据结构中，从逻辑上可以把数据结构分成 。 A．动态结构和静态结构 B．紧凑结构和非紧凑结构
1
C．线性结构和非线性结构 D．内部结构和外部结构
二、填空题
1.数据的基本单位是 ，最小单位 。
2.算法的的特性有 、 、 、输入、输出 。 3. 数据结构按结点的关系，可分为4种逻辑结构： 、 、树结构、图结构。 4. 数据结构的存储结构包括顺序、________、索引和散列等四种。 5．算法质量的度量标准有两个： 复杂度和 复杂度。
6．数据的逻辑结构是从逻辑关系上描述数据，它与数据的_____无关，是独立于计算机的。
7．线性结构中元素之间存在 关系，树形结构中元素之间存在 关系，图形结构中元素之间存在 关系。
8．下面程序段的时间复杂度是 。 for (i=1; i for (j=1; j for(i=0; i count=0; x=2; while (x x *= 2; count++; } return (count) } 11．下面程序段的时间复杂度是 。 s＝0； 2 for（i=0；i 12．下面程序段的时间复杂度是 。 for (i=1; i for (j=1; j 三、判断题 1.算法的运行时间涉及加、减、乘、除、转移、存、取、等基本运算。要想准确地计算总运算时间是不可行的。 2.为度量一个搜索算法的性能，需要在时间和空间方面进行权衡。 3.数据的基本单位是数据项。 5.数据的最小单位是数据项。 4. 数据的逻辑结构是指各数据元素之间的逻辑关系，是用户根据应用需要建立的。 四、简答题 1.怎样理解数据结构在计算机课中的核心地位。 2.为什么要用抽象数据类型来描述数据结构。 3.描述数据结构、逻辑结构、存储结构和运算的有关概念及其相互之间的关系。它们如何影响算法的设计与实现。 4.描述算法所具备的基本特征，并指出算法与程序之间的差异。 3 第二章 线性表 一、单项选择题 1.线性表是一个具有n个（ ）的有限序列。 A．表元素 B．字符 C．数据元素 D．数据项 2.线性链表不具有的特点是（ ）。 A．随机访问 B．不必事先估计所需存储空间大小 C．插入与删除时不必移动元素 D．所需空间与线性表长度成正比 3.向有127个元素原顺序表中插入一个元素，平均要移动（ ）个元素。 A. 8 B. 63.5 C. 63 D. 7 4.一个有序顺表有255个对象，采用顺序搜索法查表，搜索成功的平均搜索长度为（ ）。 A.128 B.127 C.126 D.255 5．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（ ）。 A．O(n) O(n) B．O(n) O(1) C．O(1) O(n) D．O(1) O(1) 6．表长为n的顺序存储的线性表，当在任何位置上插入和删除一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（ ），删除一个元素需要移动元素的平均个数为（ ）。 A.(n-1)/2 B.(n+1)/2 C.n/2 D.n E.(n-2)/2 7. 在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（ ）。 A. O(n) B. O(n/2) C. O(1) D. O(n) 2 8.线性链表不具有的特点是（ ）。 A．随机访问 B．不必事先估计所需存储空间大小 C．插入与删除时不必移动元素 D．所需空间与线性表长度成正比 9.带头结点的单链表first为空的判定条件是（ ） A. first == NULL; B. first->next == NULL; C. first->next == first; D. first != NULL; 10.用链表表示线性表的优点是( ) A.便于随机存取 B.花费的存储空间比顺序表少 C.便于插入与删除 D.数据元素的物理顺序与逻辑顺序相同 11.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（ ）。 A.s->next=p->next; p->next=s; B.p->next=s->next; s->next=p; C.q->next=s;s->next=p; D.p->next=s; s->next=q; 12. 已知单链表A长度为m，单链表B长度为n，若将B联接在A的末尾，其时间复杂度应为（ ）。 A. O(1) B. O(m) C. O(n) D. O(m+n) 13．设单链表中结点的结构为 4