大工16春《数据结构》开卷考试复习资料

数据结构复习资料(亲自整理)1、链表是一种存储数据的链式结构，每个数据之间都是相关联的。

2、线性结构是一个有序数据元素的集合，包括线性表、栈、队列、双队列、数组和串。

3、树是由n（n>=1）个有限节点组成一个具有层次关系的集合，而二叉树是每个结点最多有两个子树的有序树。

二叉树与树的主要差别在于，二叉树结点的最大度数为2，而树中结点的最大度数没有限制；二叉树的结点有左、右之分，而树的结点无左、右之分。

4、堆是一种可以被看做一棵树的数组对象，总是满足某个节点的值总是不大于或不小于其父节点的值，且堆总是一棵完全二叉树。

5、二叉排序树是一种满足以下递归定义的二叉树：若左子树非空，则左子树所有节点的值均小于它的根节点；若右子树非空，则右子树所有节点的值均大于于它的根节点；左右子树也分别为二叉排序树。

1、在已知前序遍历和中序遍历的情况下，可以通过画树的方法求得后序遍历。

具体步骤如下：首先根据前序遍历的特点，确定根节点；然后观察中序遍历，将左子树和右子树分别确定下来；接着对左子树和右子树分别进行递归，直到遍历完所有节点，最后得到后序遍历。

2、树和二叉树之间可以相互转换。

将树转换为二叉树的方法是：对于每个节点，将其第一个孩子作为其左孩子，将其兄弟作为其右孩子。

将二叉树转换为树的方法是：对于每个节点，将其右孩子作为其兄弟。

3、二叉树线索化是将二叉树中的空指针指向该节点在中序遍历中的前驱或后继节点的过程。

在线索二叉树中，一个结点是叶结点的充要条件为：左、右标志均是1.4、邻接表是图的一种链式存储结构，用于表示图中每个节点的邻居节点。

每个节点都有一个链表，存储着与该节点相邻的节点。

邻接表是一种图的存储结构，对于每个顶点建立一个单链表，单链表中的结点表示依附于该顶点的边（对于有向图是以该顶点为尾的弧）。

邻接表中的表结点和头结点分别表示边和顶点，包含信息如下：表结点adjvex（邻接点）。

nextarc（指向下一个表结点）（权值等信息）；头结点data（顶点信息）和firstarc（指向第一个表结点）。

第一章概论一、选择题1、研究数据结构就是研究（D ）。

A. 数据的逻辑结构B。

数据的存储结构C. 数据的逻辑结构和存储结构D。

数据的逻辑结构、存储结构及其基本操作2、算法分析的两个主要方面是（ A ）。

A。

空间复杂度和时间复杂度 B. 正确性和简单性C。

可读性和文档性D。

数据复杂性和程序复杂性3、具有线性结构的数据结构是（ D ）。

A。

图B。

树C。

广义表D。

栈4、计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入、输出、( B )等5个特性。

A. 可执行性、可移植性和可扩充性B。

可执行性、有穷性和确定性C。

确定性、有穷性和稳定性 D. 易读性、稳定性和确定性5、下面程序段的时间复杂度是（ C )。

for(i=0；i<m;i++）for(j=0;j〈n；j++）a[i］[j]=i＊j；A. O(m2) B。

O（n2) C。

O（m*n) D. O（m+n)6、算法是（D ）。

A。

计算机程序 B. 解决问题的计算方法C。

排序算法 D. 解决问题的有限运算序列7、某算法的语句执行频度为（3n+nlog2n+n2+8），其时间复杂度表示( C ）。

A。

O（n） B. O（nlog2n) C。

O（n2） D. O （log2n)8、下面程序段的时间复杂度为（ C ）.i=1；while(i<=n）i=i*3；A. O(n）B。

O(3n) C。

O(log3n) D. O(n3）9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的（）和运算等的学科。

A. 结构B。

关系C。

运算D。

算法10、下面程序段的时间复杂度是（A ）。

i=s=0；while（s<n)｛i++；s+=i;}A. O(n) B。

O（n2）C。

O（log2n）D。

O(n3)11、抽象数据类型的三个组成部分分别为（A）。

A. 数据对象、数据关系和基本操作B. 数据元素、逻辑结构和存储结构C. 数据项、数据元素和数据类型D. 数据元素、数据结构和数据类型12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量，以下解释错误的是（)。

《数据结构》习题汇编一、单项选择题1.在数据结构中.从逻辑上可以把数据结构分成（）。

A. 动态结构和静态结构B. 紧凑结构和非紧凑结构C. 线性结构和非线性结构D. 内部结构和外部结构2.数据结构在计算机内存中的表示是指（）。

A. 数据的存储结构B. 数据结构C. 数据的逻辑结构D. 数据元素之间的关系3.在数据结构中.与所使用的计算机无关的是数据的（）结构。

A. 逻辑B. 存储C. 逻辑和存储D. 物理4.计算机算法指的是（①）.它必须具备输入、输出和（②）等5个特性。

①A. 计算方法 B. 排序方法C. 解决问题的有限运算序列D. 调度方法②A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性C. 确定性、有穷性和稳定性D. 易读性、稳定性和安全性5.在一个长度为n的顺序表中向第i个元素（1≤i≤n+1）位置插入一个新元素时.需要从后向前依次后移（）个元素。

A. n-iB. n-i+1C. n-i-1D. i6.在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时.需要从前向后依次前移（）个元素。

A. n-iB. n-i+1C. n-i-1D. i7.在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。

A. O(n)B. O(1)C. O(n2)D. O(log2n)8.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为（）。

A. O(n)B. O(n/2)C. O(1)D. O(n2)9.不带头结点的单链表first为空的判定条件是：（）A. first == NULL;B. first->next == NULL;C. first->next == first;D. first != NULL;10.带头结点的单链表first为空的判定条件是：（）A. first == NULL;B. first->next == NULL;C. first->next == first;D. first != NULL;11.设单链表中结点的结构为（data, next）。

《数据结构》课程复习资料一、填空题：1.设需要对5个不同的记录关键字进行排序，则至少需要比较土次，至多需要比较10次。

2.设二叉排序树的高度为h,则在该树中查找关键字key最多需要比较丄次。

3.设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有丄个，比较两次查找成功有结点数有生个。

4.数据结构从逻辑上划分为三种基本类型§线性结构、树型结构和图型结构。

5.在一个具有n个顶点的无向完全图中，包含有n(n-l)/2条边,在一个具有n个顶点的有向完全图中，包含有n(n-l)条边。

6.向一棵B.树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度增加1。

7•在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为0(log2n),整个堆排序过程的时间复杂度为0(nlog2n)。

8.在快速排序、堆排序、归并排序中，归并排序是稳定的。

9.在有n个叶子结点的哈夫曼树屮，总结点数是旷1 °10.—棵树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定左右子树空。

11.已知数组A [ 1 0 ] [ 1 0 ]为对称矩阵，英中每个元素占5个单元。

现将英下三角部分按行优先次序存储在起始地址为1000的连续的内存单元中，则元素A [5, 6]对应的地址是1225 o12.在有n个结点的无向图中，其边数最多为n(n-l)/2。

13.取出广义表A二(x, (a, b, c, d))中原子x的函数是head (A) o14.对矩阵采用压缩存储是为了节省空间。

15.带头结点的双循环链表L为空表的条件是L->next二L->prior 或L-〉next二L。

16.设线性表中元素的类型是实型，其首地址为1024,则线性表屮第6个元素的存储位置是1044。

17.对于顺序存储的栈，因为栈的空间是有限的，在进行入栈(插入)运算时,可能发生栈的上溢，在进行出栈(删除)运算时,可能发生栈的下溢。

机密★启用前大连理工大学网络教育学院2016年9月《数据结构》课程期末复习资料☆注意事项：本复习题满分共：400分。

一、单项选择题（本大题共65小题，每小题3分，共195分）1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。

(A).正确性 (B). 可行性 (C). 健壮性 (D). 输入性2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。

for(i=n-1；i>=0；i--)for(j=0；j<i；j++) S；(A).n2 (B). O(nlgn) (C). O(n) (D). O(n2)3．折半查找法适用于（）。

（A）、有序顺序表（B）、有序单链表（C）、有序顺序表和有序单链表都可以（D）、无限制4．顺序存储结构的优势是（）。

（A）、利于插入操作（B）、利于删除操作（C）、利于顺序访问（D）、利于随机访问5．深度为k的完全二叉树，其叶子结点必在第（）层上。

（A）、k-1 （B）、k （C）、k-1和k （D）、1至k 6．具有60个结点的二叉树，其叶子结点有12个，则度为1的结点数为（）（A）、11 （B）、13 （C）、48 （D）、377.下列程序段的时间复杂度为（）。

for(i=0； i<m； i++) for(j=0； j<t； j++) c[i][j]=0；for(i=0；i<m；i++) for(j=0；j<t；j++) for(k=0；k<n；k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]；(A) O(m*n*t) (B) O(m+n+t) (C) O(m+n*t) (D) O(m*t+n) 8．设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动（）个元素。

(A) n-i (B) n+1 -i (C) n-1-i (D) i9．设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为B，T1、T2和T3的结点数分别为N1、N2和N3，则二叉树B的根结点的左子树的结点数为（）。

数据结构期末试卷一、选择题1．组成数据的基本单位是（）。

(A) 数据项(B) 数据类型(C) 数据元素(D) 数据变量2．设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={<1，2>，<2，3>，<3，4>，<4，1>}，则数据结构A是（）。

(A) 线性结构(B) 树型结构(C) 图型结构(D) 集合3．数组的逻辑结构不同于下列（）的逻辑结构。

(A) 线性表(B) 栈(C) 队列(D) 树4．二叉树中第i(i≥1)层上的结点数最多有（）个。

(A) 2i (B) 2i(C) 2i-1(D) 2i-15．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（）。

(A) p->next=p->next->next (B) p=p->next(C) p=p->next->next (D) p->next=p6．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（）。

(A) 6 (B) 4 (C) 3 (D) 27．将10阶对称矩阵压缩存储到一维数组A中，则数组A的长度最少为（）。

(A) 100 (B) 40 (C) 55 (D) 808．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（）。

(A) 3 (B) 4 (C) 5 (D) 19．根据二叉树的定义可知二叉树共有（）种不同的形态。

(A) 4 (B) 5 (C) 6 (D) 710.设有以下四种排序方法，则（）的空间复杂度最大。

(A) 冒泡排序(B) 快速排序(C) 堆排序(D) 希尔排序二、填空题1.设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。

数据结构复习提纲一，选择题1.数据结构是指（A）。

A.数据元素的组织形式B.数据类型C.数据存储结构D.数据定义2.数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（C）。

A.存储结构B.逻辑结构C.链式存储结构D.顺序存储结构3.设语句x++的时间是单位时间，则以下语句的时间复杂度为（B）。

for(i=1; i<=n; i++)for(j=i; j<=n; j++)x++;A.O(1)B.O(2n)C.O(n)D.O(3n)4.计算机内部数据处理的基本单位是（B）。

A.数据B.数据元素C.数据项D.数据库-------25.在一个长度为n的顺序表中删除第i个元素(1<=i<=n)时，需向前移动A个元素。

A．n-i B．n-i+l C．n-i-1 D．i6. 线性表采用链式存储时，其地址___ D___。

A．必须是连续的B．一定是不连续的C．部分地址必须是连续的D．连续与否均可以7.从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较__C个元素结点。

A．n/2 B．n C．（n+1）/2 D．（n-1）/2 8.在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是D __。

A． p->next=s; s->prior=p;p->next->prior=s; s->next=p->next;B． s->prior=p; s->next=p->next;p->next=s; p->next->prior=s;C． p->next=s; p->next->prior=s;s->prior=p; s->next=p->next;D． s->prior=p; s->next=p->next;p->next->prior=s; p->next=s;9.设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为A。

数据结构习题集含答案目录目录 (1)选择题 (2)第一章绪论. (2)第二章线性表. (4)第三章栈和队列. (6)第四章串. (7)第五章数组和广义表 (8)第六章树和二叉树 (8)第七章图. (11)第八章查找. (13)第九章排序. (14)简答题 (19)第一章绪论. (19)第二章线性表. (24)第三章栈和队列. (26)第四章串. (28)第五章数组和广义表 (29)第六章树和二叉树 (31)第七章图. (36)第八章查找. (38)第九章排序. (39)编程题 (41)第一章绪论. (41)第二章线性表. (41)第三章栈和队列. (52)第四章串. (52)第五章数组和广义表 (52)第六章树和二叉树 (52)第七章图. (52)第八章查找. (52)第九章排序. (57)选择题第一章绪论1. 数据结构这门学科是针对什么问题而产生的？（ A ）A、针对非数值计算的程序设计问题 B 、针对数值计算的程序设计问题C、数值计算与非数值计算的问题都针对D、两者都不针对2. 数据结构这门学科的研究内容下面选项最准确的是（ D ）A、研究数据对象和数据之间的关系 B 、研究数据对象C、研究数据对象和数据的操作D、研究数据对象、数据之间的关系和操作3. 某班级的学生成绩表中查得张三同学的各科成绩记录，其中数据结构考了90分，那么下面关于数据对象、数据元素、数据项描述正确的是（ C ）A、某班级的学生成绩表是数据元素，90 分是数据项B、某班级的学生成绩表是数据对象，90 分是数据元素C、某班级的学生成绩表是数据对象，90 分是数据项D、某班级的学生成绩表是数据元素，90 分是数据元素4. *数据结构是指（A ）。

A、数据元素的组织形式B、数据类型C、数据存储结构D、数据定义5. 数据在计算机存储器内表示时，物理地址与逻辑地址不相同，称之为（C ）。

A、存储结构B、逻辑结构C、链式存储结构D、顺序存储结构6. 算法分析的目的是（ C ）A、找出数据的合理性B、研究算法中的输入和输出关系C、分析算法效率以求改进D、分析算法的易懂性和文档型性7. 算法分析的主要方法（ A ）。

数据结构考试开卷准备资料一、线性表（顺序和链式，基本）1.就地逆置：例：70 30 40 10，将其分为两个区间，逆置前和逆置后，每次将逆置前中的第一个元素放在逆置后区中第一个位置[]70 10 30 40;[70]10 30 40;[10 70]30 40;[30 10 70]40;[40 30 10 70]2.删除大小范围从x到y之间元素方法1：用遍历判断的方法，直接从表中删除，顺序表则还需要在每个元素删除之后后面的元素还要向前移动。

（时间代价为O(n^2)）方法2：建立新的表，遍历原来的表，不满足的元素加到新表中，满足条件的不加，最后将新表赋值给旧表。

（时间代价为O(n)，但是还有额外的空间代价O（n））3.用线性表表示多项式并实现多项式相加（以链表为例）建立一个新的类Node，里面有三个元素，次数(int)，系数(int)，下一个元素地址(Node)，按照这个类型建立链表，并在建立之后按照次数降序排序。

多项式相加：多项式A和多项式B，获取两个多项式的最高次数和最低次数，按照i=最高次项到最低次项逐项判断A和B内是否有该次项，无则记为0，有则提取系数进行相加，最终得到最后结果。

4.交换两个单链表两个元素位置（分别记为A和B）方法1：直接交换两个元素的值(temp=A.data;A.data=B.data;B.data=temp;)方法2：交换两个结点，A的前面结点的Next指向某个temp，B的前面结点的Next指向A，temp指向B；A的Next指向temp1，B的Next指向temp2，此后B的Next指向temp1，B 的Next指向temp2，完成交换。

5.多项式求导数。

由3作为基础。

次数不为零的结点，系数等于次数乘系数，次数等于自己减一，次数为零的，系数等于零。

二、栈1.汉诺塔递归，要移动n层的汉诺塔就意味着要移动n-1层在移动最后一层，所以最终是先移动第一层。

例：三层汉诺塔，就意味着先移动2层，又意味着先移动1层。

《数据结构》复习题及参考答案数据结构复习题及参考答案1. 什么是数据结构？数据结构是一种组织和存储数据的方式，它涉及到数据的组织方式、存储方式、访问方式以及对数据进行操作的算法等。

数据结构的选择对于解决不同类型的问题非常重要。

2. 数据结构有哪些常见的分类？数据结构可以分为以下几类：(1) 线性结构：线性结构是一种有序排列的数据结构，其中数据元素之间存在着一对一的关系。

常见的线性结构有数组、链表、栈和队列等。

(2) 非线性结构：非线性结构是一种数据元素之间存在多对多关系的结构，常见的非线性结构有树和图等。

(3) 逻辑结构：逻辑结构是指数据元素之间的逻辑关系，主要包括集合结构、线性结构、树形结构和图形结构等。

(4) 物理结构：物理结构是指数据的逻辑结构在计算机存储中的表示方式，主要包括顺序存储结构和链式存储结构等。

3. 什么是算法？算法是解决特定问题的一系列步骤或操作的有限序列。

一个算法通常包括输入、输出、基本操作、控制结构和定义算法执行的约定等。

4. 数据结构和算法之间的关系是什么？数据结构是算法的基础，而算法又依赖于数据结构。

只有选择合适的数据结构，才能实现高效的算法。

同时，算法的设计也会对数据结构的选择产生影响。

5. 请解释什么是时间复杂度和空间复杂度？时间复杂度是衡量算法执行时间消耗的度量，表示算法的运行时间与问题规模之间的关系。

通常用大O符号来表示时间复杂度，如O(n)、O(nlogn)等。

空间复杂度是衡量算法执行所需存储空间的度量，表示算法所需的额外空间与问题规模之间的关系。

同样也使用大O符号来表示，如O(1)、O(n)等。

6. 请简要描述以下数据结构的特点及应用场景：(1) 数组：数组是一种连续存储数据元素的线性结构，具有随机访问性能。

适用于知道元素位置的查找和修改操作。

(2) 链表：链表是一种通过指针连接的数据结构，具有插入、删除元素方便的特点。

适用于频繁插入、删除操作以及不知道具体位置的查找操作。

最新国家开放大学电大《数据结构》期末题库及答案考试说明：本人针对该科精心汇总了历年题库及答案，形成一个完整的题库，并且每年都在更新。

该题库对考生的复习、作业和考试起着非常重要的作用，会给您节省大量的时间。

做考题时，利用本文档中的查找工具，把考题中的关键字输到查找工具的查找内容框内，就可迅速查找到该题答案。

本文库还有其他网核及教学考一体化答案，敬请查看。

《数据结构》题库及答案一一、单项选择题1. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是（ C ）。

A. O(1)B. O(n)C. O(n2)D. O(nlog2n)2. 带表头的双向循环链表的空表满足（ B ）。

A. first＝NULL;B. first->rLink==firstC. first->lLink==NULLD. first->rLink==NULL3. 栈的插入和删除操作在( A )进行。

A. 栈顶B. 栈底C. 任意位置D. 指定位置4. 在一个顺序存储的循环队列中，队头指针指向队头元素的( A )位置。

A. 前一个B. 后一个C. 当前D. 后面5. 假定一个顺序存储的循环队列的队头和队尾指针分别为front和rear，则判断队空的条件为( D )。

A. front+1 == rearB. rear+1 == frontC. front == 0D. front == rear6. 设链式栈中结点的结构为（data, link），且top是指向栈顶的指针。

若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x中，则应执行( A )操作。

A. x=top->data; top=top->link;B. top=top->link; x=top->data;C. x=top; top=top->link;D. x=top->data;7. 为增加内存空间的利用率和减少溢出的可能性, 由两个栈共享一块连续的内存空间时, 应将两栈的( D )分别设在这块内存空间的两端。

2016年10月高等教育自学考试全国统一命题考试数据结构导论试卷<课程代码02142>本试卷共4页,满分l00分,考试时间l50分钟。

考生答题注意事项：1．本卷所有试题必须在答题卡上作答。

答在试卷上无效,试卷空白处和背面均可作草稿纸。

2．第一部分为选择题。

必须对应试卷上的题号使用2B铅笔将"答题卡"的相应代码涂黑。

3．第二部分为非选择题。

必须注明大、小题号,使用0．5毫米黑色字迹签字笔作答。

4．合理安排答题空间。

超出答题区域无效。

第一部分选择题<共30分>一、单项选择题<本大题共10小题,每小题2分,共30分>在每小题列出的四个备选项中只有一个是符合题目要求的,请将其选出并将"答题卡"的相应代码涂黑。

错涂、多涂或未涂均无分。

1．已知问题规模为n,则下列程序片段的时间复杂度是C2．若用计算机来模拟银行客户排队等待办理业务的情形,则所应该采用的数据结构是A．栈 B．队列 C．树 D．图3．若线性表采用链式存储结构,则适用的查找方法为A．随机查找 B．散列查找 C．二分查找 D．顺序查找4．已知指针P和q分别指向某单链表中第一个结点和最后一个结点,假设指针s指向另一个单链表中某个结点,则在S所指结点之后插入上述单链表应执行的语句为A．q→next；s→next；s→next2P； B．s→next=P；q→next=s→next；C．p→next=s→next；s→next=q； D．s→next2q；p→next2s→next；5．栈的运算特点是先进后出,元素a、b、c、d依次入栈,则不能得到的出栈序列是A．abed B．dcba C．cabd D．bcda6．在实现队列的链表结构中,其时间复杂度最优的是A．仅设置头指针的单循环链表 B．仅设置尾指针的单循环链表C．仅设置头指针的双向链表 D．仅设置尾指针的双向链表7．任意一棵二叉树的前序和后序遍历的结果序列中,各叶子结点之间的相对次序关系是A．不一定相同B. 都相同 C．都不相同 D．互为逆序8．若某棵树的存储结构采用双亲表示法,如题8图所示,则该树的高度是A．2 B．3 C．4 D．59．无向图的邻接矩阵一定是A．对称矩阵 B．对角矩阵 C．稀疏矩阵 D．三角矩阵10．根据连通图的深度优先搜索的基本思想,如题10图所示的连通图的一个深度优先搜索的结果序列是A．123456 B．123465 C. 126345 D．16254311．用顺序查找方法对含有n个数据元素的顺序表按从后向前查找次序进行查找,现假设查找其中每个数据元素的概率不相等,那么A．该顺序表按查找概率由低到高的顺序来存储数据元素,其ASL最小B．该顺序表按查找概率由高到低的顺序来存储数据元素,其ASL最小C．ASL的大小与数据元素在该顺序表中的位置次序无关D．ASL的大小与查找每个数据元素的概率无关12．已知散列表的存储空间为T[0,…,l6],散列函数为H<k>----k mod l7,用二次探测法解决冲突。