数据结构16*比16大吗

谋学网www.mouxue.com

16春学期《数据结构》在线作业

一、单选题（共 20 道试题，共 40 分。）

1. 设串s1=’FG’，s2=’PQRST’，函数on(x,y)返回x和y串的连接串，sus(s, i, j)返回串s的从序号i开始的j个字符组成的子串，ln(s)返回串s的长度，则on(sus(s1, 2, ln(s2)), sus(s1, ln(s2), 2))的结果串是（） . F . FG . PQRST . FF

正确答案：

2. 折半搜索与二叉搜索树的时间性能() . 相同 . 完全不同 . 有时不相同

. 数量级都是O（log2n） 正确答案：

3. 深度优先遍历类似于二叉树的() . 先序遍历 . 中序遍历 . 后序遍历 . 层次遍历 正确答案：

4. 单链表的存储密度（） . 大于1 . 等于1 . 小于1 . 不能确定 正确答案：

5. 在表长为ｎ的链表中进行线性查找，它的平均查找长度为（ ） . ＡＳＬ＝ｎ

. ＡＳＬ＝（ｎ＋１）／２ . .

正确答案：

6. 设F是一个森林，是由F变换得的二叉树。若F中有n

大工16秋《数据结构》在线作业3

一、单选题（共 10 道试题，共 50 分。）

1. 若在线性表中采用折半查找法查找元素，该线性表应该（）。 A. 元素按值有序，且采用链式存储结构 B. 元素按值有序，且采用顺序存储结构 C. 采用顺序存储结构 D. 元素按值有序 正确答案：B

2. 设有序表中的元素为(12，17，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。 A. 1 B. 2 C. 3 D. 4

正确答案：C

3. 设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）。 A. n和2e B. 2n和e C. e和n D. n和e 正确答案：A

4. 设有向图n个顶点和e条边，进行拓扑排序时，总的计算时间为（）。 A. O (nlog2e) B. O (n+e) C. O (en ) D. O ( elog2n) 正确答案：B

5. 下面给出的四种排序法中（）排序法是不稳定性排序法。 A. 插入 B. 冒泡 C. 堆排序 D. 二路归并 正确答案：C

6. 对一组数据（46,79,56,38,40,84）排序，则采用快速排序的方法，以第一个记录

电子科技大学电子科大16秋《数据结构》在线作业1

一、单选题（共 16 道试题，共 48 分。）

1. 设串sl=″Data Structures with Java″,s2=″it″，则子串定位函数index(s1,s2)的值为（ ）。 A. 15 B. 16 C. 17 D. 18

正确答案：

2. 下面程序段的时间复杂度为（ ）。 for (i=0; i

3. n个顶点的有向完全图中含有向边的数目最多为（ ）。 A. n-1 B. n

C. n(n-1)/2 D. n(n-1) 正确答案：

4. 在数据结构中，数据的逻辑结构可以分成（ ）。 A. 内部结构和外部结构 B. 线性结构和非线性结构 C. 紧凑结构和非紧揍结构 D. 动态结构和静态结构 正确答案：

5. 逻辑上通常可以将数据结构分为（ ）。 A. 动态结构和静态结构 B. 顺序结构和链式结构 C. 线性结构和非线性结构 D. 初等结构和组合结构 正确答案：

6. 在目标串T［0..n-1］=″xwxxyxy″中，对模式串P［0..m-1］=″xy″进行子串定位操作的结果是（ ）。 A. 0 B. 2 C. 3

D. 5

正确答案：

7. 已知函数Sub

大工16秋《数据结构》在线作业3

一、单选题（共 10 道试题，共 50 分。）

1. 若在线性表中采用折半查找法查找元素，该线性表应该（）。 A. 元素按值有序，且采用链式存储结构 B. 元素按值有序，且采用顺序存储结构 C. 采用顺序存储结构 D. 元素按值有序 正确答案：B

2. 设有序表中的元素为(12，17，24，35，47，50，62)，则在其中利用二分法查找值为24的元素需要经过（）次比较。 A. 1 B. 2 C. 3 D. 4

正确答案：C

3. 设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（）。 A. n和2e B. 2n和e C. e和n D. n和e 正确答案：A

4. 设有向图n个顶点和e条边，进行拓扑排序时，总的计算时间为（）。 A. O (nlog2e) B. O (n+e) C. O (en ) D. O ( elog2n) 正确答案：B

5. 下面给出的四种排序法中（）排序法是不稳定性排序法。 A. 插入 B. 冒泡 C. 堆排序 D. 二路归并 正确答案：C

6. 对一组数据（46,79,56,38,40,84）排序，则采用快速排序的方法，以第一个记录

第10章 内部排序

一、选择题（每小题2分，共20分）

1.从未排序序列中依次取出一个元素与已排序序列中的元素依次进行比较，然后放在已排序序列的合适位置，该排序方法称为（ ）排序法。

A.插入排序 B.选择排序 C.希尔排序 D.二路归并排序

2.下列排序算法中( )排序在一趟结束后不一定能选出一个元素放在其最终位置上。 A.选择 B.冒泡 C.归并 D.堆 3.若一组记录的排序码为（46, 79, 56, 38, 40, 84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（ ）。

A. 38, 40, 46, 56, 79, 84 B. 40, 38, 46, 79, 56, 84 C. 40, 38， 46, 56, 79, 84 D. 40, 38, 46, 84, 56, 79

4.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为（ ）。

A.希尔排序 B.冒泡排序 C.

第6章 树和二叉树

一、选择题（每小题1分，共10分） 1.以下数据结构中，（ A ）是非线性数据结构。 A.树 B.线性表 C.队列 D.栈 2.在一棵二叉树中第五层上的结点数最多为（ B ）。 A.8 B.15 C.16 D.32

3. 已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（ A ）。

A. CBEFDA B. FEDCBA C. CBEDFA D. 不定 4.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是( B ）。 A.9 B.11 C.15 D.不确定

5.给定二叉树如图所示。设N代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。若遍历后的结点序列为3,7,5,6,1,2,4，则其遍历方式是（ D ）。

A. LRN B. NRL C. RLN D. RNL 6.在下列存储形式中，哪一个不是树的存储形式？（ D ）

A.双

第1章绪论

一、选择题（每小题2分，共20分） 1.以下哪一个不是算法的特性（ ）。

A.有穷性 B.确定性 C.简洁性 D.可行性 2.数据结构的定义为(D，S)，其中D是( )的集合。

A. 算法 B. 数据元素 C. 数据操作 D. 逻辑结构

3.设n是描述问题规模的非负整数，下面程序片段的时间复杂度是（ ）。 x=2；

while(x

2

A. O(log2n) B. O(n) C. O(nlog2n) D. O(n) 4.执行下面程序段时，执行Ｓ语句的次数为（ ）． for （int i=1；i<=n；i++）

for (int j=1； j<=i； j++) S；

A. n2 B. n2/2 C. n(n+1) D. n(n+1)/2 5.在下面的程序段中，对x的赋值语句的频度为（ ）。 for(i=1；i<=n;i++)

for(j=1；j<=n；j++) x=x+1;

2

A. O(2n) B. O(n) C. O(n) D. O(log2n) 6.在数据结构的讨论中把数据结构从逻辑上分为 （ ）。 A.

数据结构

1

1.为解决计算机与打印机之间速度不匹配问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应该是（ ）。（全国统考2009） A．栈 B．队列 C．树 D．图

2.设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后入队Q，若出队序列为e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是（ ）。（全国统考2009）

A．1 B．2 C．3 D．4

3.若元素abcdef依次进栈，允许进栈、出栈交替进行，不允许连续三次进行出栈操作，则不可能得到的出栈序列是（ ）。（全国统考2010）

A．dcebfa B．cbdaef C．dbcaef D．afedcb 4.某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作，则不可能得到的顺序是（ ）。（全国统考2010） A．bacde B．dbace C．dbcae D．ecbad

5.元素abcde依次进入初

数据结构习题

一、 单选题

1. 研究数据结构就是研究 D

A) 数据的逻辑结构

B) 数据的逻辑结构和存储结构 C) 数据的存储结构

D) 数据的逻辑结构、存储结构及其数据在运算上的实现 2. 下面关于算法的说法，错误的是 D 。

A) 算法最终必须由计算机程序实现

B) 为解决某问题的算法与为该问题编写的程序含义是相同的 C) 算法的可行性是指指令不能有二义性 D) 以上几个都是错误的

3. 计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备

5个特性输入、输出 、 B 。 A) 可执行性、可移植性和可扩充性 B) 可执行性、有穷性和确定性 C) 确定性、有穷性和稳定性 D) 易读性、稳定性和确定性

4. 以下属于逻辑结构的概念是 C 。

A) 顺序表 B) 哈希表 C) 有序表 D) 单链表

5. 具有线性结构的数据结构是 D 。

A) 图 B) 树 C) 广义表 D) 栈

6. 数据的存储结构包括顺序、链接、散列和 D 种基本类型。

A) 向量 B) 数组 C) 集

数据结构复习201406

第一章绪论

基本知识点：数据结构与算法的概念。

重点：数据结构的逻辑结构、存储结构、数据运算三方面的概念及相互关系；算法时间复杂度分析。

难点：分析算法的时间复杂度。 知识要点：

数据：在计算机科学中数据是指所有能输入到计算机中并被计算机处理的符号的总称。 数据元素：数据的基本单位，是数据的一个元素。

数据对象：性质相同的数据元素的集合，是数据的一个子集。

数据结构：相互之间存在一种或多种特定关系的数据元素的集合，一般包括三个方面的内容，即数据的逻辑结构、存储结构和数据的运算。

数据类型：一个值的集合和定义在这个值集上的一组运算的总称。

数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象（数据元素）以及它们之间关系和操作（运算）的学科。

数据的逻辑结构是指数据元素之间逻辑关系的整体。 数据的存储结构是指数据结构在计算机内的表示。

四种基本数据结构：集合、线性结构、树形结构、图结构。

算法具有的五个基本特性是：有穷性、可行性、确定性、输入和输出。 算法执行的时间是问题规模的函数。 算法的时间复杂度是指，随着问题规模n的增大，算法执行时间的增长率和f(n)的增长率相同时，则称该算法的时间复杂度为O(f(n))。