2019年数据结构期末考试题及答案.docx

PAGE PAGE # / 23 2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为 C。 动态结构和静态结构B.松懈结构和非松懈结构 C.线性结构和非线性结构D.内部结构和外部结构 数据结构在计算机内存中的表示是指 A。 数据的存储结构B.数据结构C.数据的逻辑结构D.数据元素之间的 关系 在数据结构中，与所使用的计算机无关的是数据的 A结构。 逻辑B.存储C.逻辑和存储D.物理 在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C。 数据的处理方法B.数据元素的类型 C.数据元素之间的关系D.数据的存储方法 在决定选取何种存储结构时，大凡不考虑 A。 各结点的值如何B.结点个数的多少 C.对数据有哪些运算D.所用的编程语言实现这种结构是否便当。 以下说法正确的是 D。 数据项是数据的基本单位 数据元素是数据的最小单位 数据结构是带结构的数据项的集合 —些表面上很不相同的数据可以有相同的逻辑结构 算法分析的目的是C,算法分析的两个主要方面是 A。 A.找出数据结构的合理性 B.研究算法中的输入和输出的关系 C.分析算法的效率以求改进 C.分析算法的易读性和文档性 A.空间复杂度和时间复杂度 B.正确性和简明性 C.可读性和文档性D.数据复杂性和程序复杂性 下面程序段的时间复杂度是 O( n2)。 s= 0； for (I = 0; iv n; i + + ) for (j = 0; jv n; j + + ) s+ = B[i][j]; sum= s; 下面程序段的时间复杂度是 O(n*m)。 for (i = 0; iv n; i+ + ) for (j = 0; jv m; j+ + ) A[i][j] = 0; 下面程序段的时间复杂度是 O( log3n)。 i = 0; while (iv= n) i = i * 3 ; 在以下的叙述中，正确的是 B。 线性表的顺序存储结构优于链表存储结构 二维数组是其数据元素为线性表的线性表 栈的操作方式是先进先出 队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着 B。 数据元素具有同一特点 不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型 要一致 每个数据元素都一样 数据元素所包含的数据项的个数要相等 链表不具备的特点是 A。 A.可随机访问任一结点B.插入删除不需要移动元素 不必事先估计存储空间D.所需空间与其长度成正比 不带头结点的单链表 head 为空的判定条件是 A。 n ext = = NULL C. head—> next = = headD head = NULL 带头结点的单链表 head 为空的判定条件是 B。 n ext = = NULL C. head—> next = = headD head = NULL 若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后 一个结点，则采用 D 存储方式最节省运算时间。 A.单链表B.给出表头指针的单循环链表 C.双链表D.带头结点的双循 环链表 需要分配较大空间，线插入和删除不需要移动元素的性表，其存储结 构是 B。 A.单链表B.静态链表C.线性链表D.顺序存储结构 非空的循环单链表 head 的尾结点（由 p 所指向）满足 C。 p—> next— NULLB p= = NULL C. p—> next== headD. p= = head 19 .在循环双链表的p所指的结点之前插入s所指结点的操作是D。 A．p—> prior —> prior B．p—> prior —> prior C．s—> prior — > n ext = s D． s—> prior—> prior = s 20.如果最常用的操作是取第i个结点及其前驱，则采用 D存储方式最节 省时间。 A.单链表B.双链表C.单循环链表D.顺序表 21．在一个具有 n 个结点的有序单链表中插入一个新结点并仍然保持有序 的时间复杂度是 B。 A. O（1） B. O（n） C. O（ n2）D. O（nlog2n） 在一个长度为n （n>1）的单链表上，设有头和尾两个指针，执行 B 操作与链表的长度有关。 删除单链表中的第一个元素 删除单链表中的最后一个元素 在单链表第一个元素前插入一个新元素 在单链表最后一个元素后插入一个新元素 与单链表相比，双链表的优点之一是 D。 插入、删除操作更简单 可以进行随机访问 可以省略表头指针或表尾指针 顺序访问相邻结点更灵敏 如果对线性表的操作只有两种，即删除第一个元素，在最后一个元素 的后面插入新元素，则最佳使用 B。 只有表头指针没有表尾指针的循环单链表 只有表尾指针没有表头指针