2012年下学期《数据结构》总复习
一、单项选择题。
1.数据结构中,与所使用的计算机无关的是数据的（A）结构。
A. 逻辑
B. 物理
C. 顺序
D. 物理和存储
2.评价一个算法写成程序后，从开始运行到结束所需存储量的主要标准
是___B____。
A. 算法易于调试
B. 算法的空间复杂度
C. 算法的稳定性和正确性
D. 算法的时间复杂度
3.设有字符串s1和s2，求s1在s2中首次出现的位置的运算称为B_____。
A. 连接
B. 模式匹配
C. 求子串
D. 求串长
4.以下关于字符串的说法，不正确的是___C ___。
A. 字符串即可以顺序存储，又可以堆存储。
B. 两个字符串的比较不可以直接使用关系运算符“==”来实现。
C. 当比较两个字符串相等时，它们的长度也一定相同。
D. 如果字符串以堆分配方式存储，则无法实现“求子串”的运算。
5.设二维数组b[5][8]的首地址是300，按行优先方式存储，每个元素占6
个字节的存储空间，则b[2][4]元素的存储地址是_______。
A. 320
B. 324
C. 420
D. 424
6.设有广义表X=(1，(2，3)，((4，5)，5，6))，其深度是______。
A．3 B．4 C．5 D．6
7.设一棵二叉树中有5个叶子结点，有2个度为1的结点，则该二叉树
中总的结点数为___________。
A. 8
B. 11
C. 12
D. 15
8.对长度为7的顺序存储的有序表，若采用二分查找，在等概率情况下
的平均查找长度为（）的七分之一。
A、14
B、15
C、17
D、21
9.若某二叉排序树具有n个结点，且“退化”为左单分技的形状，则在
该二叉排序树中查找一个元素的平均时间复杂度为____。
A、O(n2)
B、O(lo g2n)
C、O(1)
D、O(n)
10.下列排序方法中，平均时间复杂度不是O(nlo g2n) 的是______。
A.快速排序
B. 希尔排序
C.树形选择排序
D.二路归并排序
11.数据的存储结构是指___C___。
A. 数据以文件的形式存储在外存中
B. 数据所占的存储空间量
C. 数据的逻辑结构在计算机中的表示
D. 数据在计算机中的顺序存储方式
12.评价一个算法时间性能的主要标准是_____A__。
A. 算法的时间复杂度
B.算法的稳定性和正确性
C. 算法的可读性
D. 算法是否配备有完整而规范的注释
13.如下陈述中正确的是____A___。
A．串是一种特殊的线性表B．串的长度必须大于零
C．串中元素只能是单个字母字符D．空串就是空格串
14.设有字符串s1=“IN T”，s2=“int”，则strcmp(s1,s2)的值_____。
A. 等于0
B. 小于0
C. 大于0
D. 以上都不对
15.若在C语言中定义了一个二维数组A[5][6]，其A[1][0] 元素的地址为
3000，每个元素占10个字节，则元素A[3][5]的地址为______。
A、3035
B、3160
C、3170
D、3180
16.设有广义表D=(a，b，D)，其长度和深度分别是______。
A．长度和深度都是3 B．长度和深度都是无穷大
C．长度是3，深度是无穷大D．长度是无穷大，深度是3
17.深度为5的二叉树，其结点的个数最多为___D___。
A. 32
B. 16
C. 5
D. 31
18.对顺序存储的有序表（5，12，20，25，28，31，34，39，41，48），
若采用二分法查找，则查找元素12的比较次数为_______
A、2
B、3
C、4
D、5
19.从具有n个结点的二叉排序树中查找一个元素时，在平均情况下的时
间复杂度大致为____。
A、O(n2)
B、O(n)
C、O(1)
D、O(lo g2n)
20.下列选项中，_________不是稳定的排序方法。
A.直接插入排序
B.快速排序
C.冒泡排序
D. 二路归并排序
21.从逻辑上可以把数据结构简单地划分为__B________。
A. 内部结构和外部结构
B. 线性结构和非线性结构
C. 动态结构和静态结构
D. 紧凑结构和非紧凑结构
22.下面关于算法空间复杂度的说法正确的是_B_____。
A. 算法空间复杂度是指算法执行过程中所需要的存储空间
B. 算法空间复杂度是指算法程序所占的存储空间
C. 算法空间复杂度是指算法程序的代码长度
D. 算法空间复杂度是指算法程序中的指令条数
23.设某字符串s=“Good”，则strlen(s)的值为______。
A. 1
B. 2
C. 4
D. 5
24.字符串通常采用的两种存储方式是_____B_。
A. 散列存储和索引存储
B. 索引存储和顺序存储
C. 顺序存储和堆存储
D. 散列存储和链式存储
25.已知二维数组A中有100个元素，按行优先的顺序存储，若第30个元
素的地址为1860，每个元素占8个字节，则第10个元素的地址为______。
A、1680
B、1700
C、1760
D、1920
26.设有广义表D=(a，b，(a,b,(a,b)))，其长度是______。
A．3 B．4 C．5 D．6
27.二叉树根结点数目是______。
A. 有且只有1
B. 0或1或2
C. 0或1
D. 至多为2
28.对长度为11的顺序存储的有序表，若采用二分查找，在等概率情况下
的平均查找长度为（）。
A、3
B、4
C、5
D、6
29.若某二叉排序树接近于满二叉树，且树中每个结点的左右子树比较平
衡，则在该二叉树中查找一个元素的最坏情况下时间复杂度为____。
A、O(n2)
B、O(n)
C、O(1)
D、O(lo g2n)
30.下列排序方法中，平均时间复杂度不是O(n2) 的是______。
A.直接插入排序
B.直接选择排序
C.冒泡排序
D.二路归并排序
二、判断题
1.访问元素个数为n的数组第i个元素算法的时间复杂度为O(1) 。（）
2.若一组元素以A、B、C、D、E的顺序进栈，每个元素进栈后都可以
立即出栈，则不可能以“C、D、E、B、A”的顺序出栈。（）
3.顺序队列和链队列所表示的数据逻辑结构完全相同。（）
4.串是线性表的特例，其特殊性在于数据元素是单个字符。（）
5.一个广义表的长度是指该广义表展开后所括号的层数。（）
6.若已知某二叉树的按层次遍历和中序遍历序列，则可以唯一地确定一
棵二叉树。（）
7.带权图最小生成树的形状一定是唯一的。（）
8.对一棵二叉排序树进行中序遍历时，得到的结点序列是一个有序递增
的结点序列。（）
9.在对n个元素进行冒泡排序的过程中，最好情况下需要进行n/2趟。（）
10.二分插入排序的关键字比较次数比直接插入排序的最坏情况要好、最
好情况要坏。（）
11.集合是一种特殊的线性结构。（）
12.顺序表在定义之后，其容量还可以扩充，而链表容量不易扩充。（）
13.队列的顺序存储要占用存储器中连续的存储单元，而链式存储则可能
不占用存储器中连续的存储单元。（）
14.若对串的读取操作明显多于插入和删除操作，则串适合于采用顺序存
储结构。（）
15.广义表的元素可以是子表，也可以是单元素。（）
16.不存在这样的二叉树，它的前序遍历和后序遍历结果相同。（）
17.四个顶点的有向图，若定义每条弧的起点和终点不可以相同，则最多
有12条弧。（）
18.顺序查找要求被查找的表一定是有序的顺序表。( )
19.在对n个元素进行快速排序的过程中，最好情况下需要进行n/2趟。（）
20.希尔排序算法的时间复杂度约为O(n2)。（）
21.算法的有穷性，也称为有限性，是指算法必须能在执行有限个步骤之
后终止。（）
22.与顺序表相比，链表的缺点是插入、删除操作效率低。（）
23.若以1、2、3、4的顺序进栈，每个数据进栈后都可以立即出栈，则出
栈的序列是不可能是3、4、1、2 。（）
24.使用系统函数strcmp对串进行比较时，若两串相等则返回1，否则返
回0。（）
25.在压缩存放稀疏矩阵的非零元素时，若还存放此非零元素所在的行号
和列号，则可以使用三元组表来实现压缩存储。（）。
26.完全二叉树中度为1的结点个数要么为0个，要么为1个。（）
27.在具有n个顶点的有向图中，所有顶点的入度之和等于所有顶点的出
度之和。（）
28.若对具有n个元素的有序表采用二分法查找，则算法的时间复杂度为O
（n）。( )
29.在对n个元素进行直接插入排序的过程中，共需要进行n-1趟。（）
30.二路归并排序法不是稳定的排序算法。（）
三、填空题
1.瑞士计算机科学家N.Wirth教授曾提出这样一个等式：程序= 算法+
________数据结构____。
2.若长度为n的线性表采用链式存储结构，访问第i（i∈[1,n]）个元素
的算法平均时间复杂度为______。
3.在一个长度为n的顺序表第i（i∈[1,n+1]）个元素之前插入一个新
元素，需要向后移动____________个元素。
4.设有一顺序栈S，八个元素以S1、S2、S3、S4、S5、S6、S7、S8依次进
栈，如果出栈顺序是S2、S4、S3、S6、S5、S1、S8、S7，则栈的容量至少是______。
5.若某循环队列的数组下标定义为MAXSIZE，排头指针为front，队尾
指针为rear，则计算该队列中元素个数的表达式为____________。
6.下面的代码是对某定长顺序存储字符串string1的有关声明与操作：
Trypdef struct
{ char data[MAXSIZE];
int curlen;
}SeqString;
SeqString string1; //声明字符串string1
string1.curlen=0; //初始化空字符串string1的长度为0
string1.data[0]=’\0’; //初始化空字符串string1
…//对字符串s进行其他操作
若字符串string1非空，则其结束标志’\0’对应的数组元素可以表示为：____。
7.已知稀疏矩阵如下图所示，将其压缩后存储到SpMat（稀疏矩阵）类
型的变量a中，三元组类型的数组域data从0下标开始保存非零元素，则a.data[4].v的值是_______。
1 0 0 0 0 2
0 0 3 0 0 0
5 0 0 9 0 0
0 0 0 0 0 0
0 0 0 4 0 0
8.如果一棵树有8个度为1的结点，有5个度为2的结点，有2个度为3
的结点，有1个度为5的结点，其余结点均为叶子，则该树的度为____。
9.若某二叉树有60个结点，则其深度最小为_______。
10.设一棵完全二叉树共有100个叶子结点，则该二叉树共有_____个度为
1的结点。
11.若某二叉树的共有29个结点，则该二叉树的叶子结点数最多为____个。
12.图的存储结构通常分为两种，它们是：________________。
13.如下图所示的有向无环图，请写出它的唯一拓扑排序序列：_______。
14.在构造散列函数时，先取关键字的平方，然后根据可使用空间的大小，
选取平方数的中间几位为散列地址，这种方法称为______。
15.从排序的稳定性上分析，直接插入排序是________排序。
16.若某算法基本操作执行次数的表达式为2n3+6n2+12n+200 ,
则该算法运行时的时间复杂度为____________。
17.设某顺序表在内存中存储的首地址为80080，每个元素占用16个字节
的存储空间，则从80160开始的地址中存储的是该顺序表中的第____
个元素。
18.链表中各元素的访问方式为_________访问。
19.设某顺序栈的数组下标定义为10，栈空时top值为0，当执行“出栈、
出栈、进栈、出栈、进栈、进栈、进栈”后，top的值为______。20.若某循环队列的数组下标定义为MAX，排头指针为front，队尾指针为
rear，则该队列为满的条件是：__________________。
21.下面的代码是对某定长顺序存储字符串s的有关声明与操作：
Trypdef struct
{ char data[MAXSIZE];
int len;
}SeqString;
SeqString s; //声明字符串s
s.len=0; //初始化字符串s的长度为0
…//对字符串s进行其他操作
则表示该字符串s（s不空）长度的表达式为：_______。
22.一个广义表为(a,b,(b,c),c,((d,(e,f)),g))，则该广义表的长度
为。
23.如果一棵树有200个度为1的结点，有7个度为2的结点，有4个度
为3的结点，有1个度为4的结点，其余结点均为叶子，则该树的叶子结点数为_______。
24.某完全二叉树共有1200个结点，则该二叉树中有____个叶子结点。
25.某完全二叉树有31个结点，最下面一层的结点数为______。
26.若某二叉树的共有8个结点，则该二叉树的叶子结点数最少为____个。
27.在一个有9个顶点的无向图中，要连通所有顶点，至少需要_____条边。
28.有向无环图如下图所示，请写出其所有的拓扑排序序列：_______。
29.不经过任何比较，通过计算就能直接得到记录所在的存储地址，这种
查找方法称作________查找。
30.在常用的各种内部排序算法中，每一轮排序都能够使无序表中的第一
条记录插入到有序表中的是__________排序。
31.下面语句段执行的时间复杂度是________。
i n t i,j,n,s=0;
c i n>>n;//这里用n表示问题的规模
fo r(i=1;i<=10;i++)
fo r(j=1;j<=10;j++)
s+=i+j;
32.访问长度为n的顺序表第i个元素，需要移动的元素个数为_______。
33.带头结点的单链表head为空的判断条件是。
34.当栈满时再执行进栈操作，会产生。
35.设某循环队列的排头front值为17，队尾rear值为15，保存队列元素
的数组下标定义为30，则该循环队列中有______个元素。
36.串是一种特殊的线性表，其特殊性在于。
37.一个广义表为((a,b),(b,c),c,((d,(e,f)),g))，则该广义表的深度
为。
38.如果一棵树有6个度为1的结点，有5个度为2的结点，有2个度为3
的结点，其余结点均为叶子，则该树的结点总数为_______。
39.某完全二叉树有39个结点，计算其深度为_______。
40.深度为5的完全二叉树，结点个数最少为______。
41.若某完全二叉树结点按层顺序编号，则40号结点的右孩子结点编号为
______。
42.5个顶点的有向图，最多有_______条弧。
43.对于一个有n个顶点和e条边的连通图，其生成树中的顶点数为___。
44.对顺序存储的有序表（6，14，21，27，28，32，35，39，47）进行二
分法查找，则查找元素39的比较次数为_______。
45.对n个记录进行冒泡排序时，最少的比较次数是______次。
四、简答
1、单链表、双向链表和循环链表，三者之间有何异同点？
2、请叙述顺序查找的基本思想。
3、线性表的链式存储结构是怎样的？
4、请叙述二叉排序树的查找思想。
5、线性表的顺序存储结构有何特点？
6、什么是散列表？为什么说它的平均比较次数与表中记录的个数无关？
五、应用题。
1、设有如下图所示的森林，请画出将其转换为二叉树的过程。
2、设有如下图所示的网络(其中的两处交叉边并不连通)，请画出用“克
鲁斯卡尔算法”构造最小生成树的过程，所画各图要求按“① ② ③ ……”的顺序编号。
4、某无向图的邻接矩阵如下图所示，设各顶点使用V1、V2、V3、……
来表示，请画出该无向图和其邻接表的表示法。
1 1
1 0 0
1 0 1 0 1 0
1 1
0 1 0 1
1 0 1 0
1 0
0 1
0 1 0 1
0 0 1 0 1 0
1、设某二叉树的后序遍历序列为：AHEFBK RGD C，中序遍历序列为：
ABEH FCG RKD，请按下列要求绘图：
①试画出该二叉树（4分）。
②试画出该二叉树的先序线索二叉树（3分）。
③试画出该二叉树的先序线索二叉链表（3分）。
2、设有如下页图所示的带权连通无向图，从A点出发，使用“普里姆算
法”构造最小生成树，请画出构造最小生成树的全过程，所画各图要求按“①②③……”的顺序编号。
六、算法设计。
1、编写算法：删除带头结点的单链表head中第i个结点。
2、编写顺序栈的出栈算法。
3、编写直接插入排序算法。
4、编写求二叉树叶子结点数的递归算法。
5、编写算法：删除长度为n的顺序表L第i (1≤i≤n)个结点。
6、编写顺序队列的入队算法。
7、编写冒泡排序算法。
8、编写求二叉树中度为2结点个数的递归算法。
9、编写算法：在长度为n的顺序表L第i (1≤i≤n+1)个结点之前插入一
个新结点x。
10、编写顺序队列的出队算法。
11、编写直接选择排序算法。
12、编写递归算法：统计二叉树中度为1的结点个数。
一、填空。 1．顺序存储结构的特点是（静态存储的物理次序和逻辑次序一致），链式存储结构的特点式（动态存储的物理次序和逻辑次序不一定一致）。 2．算法在遇到非法操作时可以作出合理处理的特性为（健壮性）。 3．常见的算法时间复杂度用大O记号表示为：常数阶（ O(1) ），对数阶（ O(log2n ) ），线性阶（O(n) ），平方阶( O(n2) )和指数阶（ O(2n) ）。 4．在单链表中，除了头结点以外，任一结点的存储位置由（其直接前驱的指针域）指示。 5．当线性表采用顺序存储结构时，其主要特点是（静态存储物理次序和逻辑次序一致）。6．在双链表中，每个结点设置了两个指针域，其中一个指向（直接前驱）结点，另一个指向（直接后继）结点。 7．设有一个空栈，栈顶指针为1000H，现有输入序列为1，2，3，4，5，经过push,push,pop,push,pop,push,push后，输出序列是（ 2,3 ），栈顶指针是（ 1003 H ）。8．栈S通常采用的两种存储结构是（顺序存储和链序存储）；其判定栈空的条件分别是（ s->top==-1 top->next==NULL ）, 判定栈满的条件分别是（ s->top==stack_size-1 ）。 9．（栈）可作为实现递归函数调用的一种数据结构。 10．栈和队列是两种特殊的线性表，栈的操作特性是（先进后出），队列的操作特性是（先进先出），栈和队列的主要区别是（栈是在表的一端进行操作，队列是在表的两端进行操作）。 11．循环队列的引入是为了克服（假溢出）。 12．数组Q[n]用来表示一个循环队列，front为队头元素的前一个位置，rear为队尾元素的位置，计算队列中元素个数的公式为 ( (front-rear+n）mod n ）。 13．用循环链表表示的队列长度为n，若只设头指针，则出队和入队的时间复杂度分别为（ O(1) ）和（ O(n) ）。 14．串是一种特殊的线性表，其特殊性体现在（串的数据限定为字符集）。 15．两个串相等的充分必要条件是（两个串的长度相等并且每个对应位置的字符都相等）。 16．（数据元素）是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。17．从逻辑关系上讲，数据结构主要分为（集合结构）、（线性结构）、（树形结构）、（图状结构或网状结构）。 18．数据的存储结构主要有（顺序）和（非顺序）两种基本方法，不论哪种存储结构，都要存储两方面的内容：（数据的表示）和（关系的表示）。 19．算法具有5个特性，分别是（可行性，有限性，确定性，输入和输出） 20．顺序表中第一个元素的地址是100，每个元素的长度为2，则第五个元素的存储地址是（ 108 ）。 21．单链表中设置头指针的作用是（标识链表在内存中的位置）。 22、设单链表中指针P指向结点A，若要删除A的后继结点（假设A存在后继结点），则修改指针的操作为（ p->next=p->next->next; ）。 23．设S=”I AM A TEACHER”,其长度为（ 14 ）。 24．对于栈和队列，无论它们采用顺序存储结构还是链式存储结构，进行插入和删除操作的时间复杂度都是（ O(1) ）。 25．数组通常有两种运算：（获得特定位置的元素值）和（修改特定元素的值），这决定了数组通常采用（顺序）结构来存储。
1. 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O (n) D. O (n2) 2．设一棵二叉树的深度为k，则该二叉树中最多有（ D ）个结点。 A. 2k-1 B. 2k C.2k-1 D. 2k-1 3．二叉树中第i(i≥1)层上的结点数最多有（ C ）个。 A. 2i B. 2i C. 2i-1 D. 2i-1 4．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ A ）。 A. p->next=p->next->next B. p=p->next C. p=p->next->next D. p->next=p 5．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ C ）。 A. 6 B. 4 C. 3 D. 2 6.设有以下四种排序方法，则（ B ）的空间复杂度最大。 A. 冒泡排序 B. 快速排 C. 堆排序 D. 希尔排序7．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ B ）。 A. 3 B. 4 C. 5 D. 1 8．根据二叉树的定义可知二叉树共有（ B ）种不同的形态。 A. 4 B. 5 C. 6 D. 7 9．对一个算法的评价，不包括如下（ A ）方面的内容。 A．并行性 B．健壮性和可读性 C．正确性 D．时空复杂度10．在二叉排序树中插入一个结点的时间复杂度为（ C ）。 A．O(1) B．O(n) C．O(log 2 n) D．O(n2)
一．是非题 1. 数据结构(应该是抽象数据类型)可用三元式表示(D，S，P)。其中：D是数据对象，S是D上的关系，P是对D的基本操作集。(f) 2 简单地说,数据结构是带有结构的数据元素的集合。(t) 3 判断带头结点的非空循环单链表(头指针为L)中指针p所指结点是最后一个元素结点 的条件是：p->next==L。(t) 4 线性表的链式存储结构具有可直接存取表中任一元素的优点。(f) 5 线性表的顺序存储结构优于链式存储结构。(f) 6. 在单链表P指针所指结点之后插入S结点的操作是： P->next= S ; S-> next = P->next;。(f) (顺序弄反了S-> next = P->next; P->next= S ;) 7 对于插入、删除而言，线性表的链式存储优于顺序存储。(t) 8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f) 9. 栈和队列是操作上受限制的线性表。(t) 10. 队列是与线性表完全不同的一种数据结构。(f) (栈和队列是操作上受限制的线性表) 11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。(f) (两端) 12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。(f) ( “如果需要,可对它们中的任一元素进行操作.” 这里的意思是在O(1)的时间来读和改某个元素。比如数组的直接索引。 栈：如果需要，每一次只能对栈顶的元素进行操作 队列：如果需要，每一次只能对两端，或者只能对队列头的元素进行操作。) 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(f) 14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的特殊情形。(f) (二叉树和树相互独立) 15 二叉树是一棵结点的度最大为二的树。(f) (二叉树和树相互独立) 16 赫夫曼树中结点个数一定是奇数。(t) 17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t) (LDR) 18 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历。(f) (后根遍历相当于中序遍历) 19. 通常，二叉树的第i层上有2i-1个结点。(f) (应该为1~2i-1个) 20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t) 21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(t) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树。(t) 23 邻接多重表可以用以表示无向图，也可用以表示有向图。(f) (只能表示无向图，有向图用十字链表) 24 可从任意有向图中得到关于所有顶点的拓扑次序。(f) (带环图没有) 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t)
1.什么是最小生成树？简述最小生成树的Prime算法的思想。 答：最小生成树就是构造一棵生成树，使得树上各边的代价之和最小。 普里姆算法(Prim)的基本思想： 从连通网络N = { V, E }中的某一顶点u0 出发，选择与它关联的具有最小权值的边(u0, v)，将其顶点加入到生成树的顶点集合U中。以后每一步从一个顶点在U中，而另一个顶点不在U中的各条边中选择权值最小的边(u, v),把它的顶点加入到集合U中。如此继续下去，直到网络中的所有顶点都加入到生成树顶点集合U中为止。 2.简述AOV网络中为何不能出现回路，如何判断AOV网络是否有回路？ 答：在AOV网络中，如果活动vi必须在vj之前进行，则称为存在有向边；在AOV网络中不能出现有向回路，如果出现了，则意味着某项活动应以自己作为先决条件。 如何检查AOV网是否存在有向环： 检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点(代表各个活动)排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。（1）这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。 （2）如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV 网络中必定不会出现有向环；相反，如果得不到满足要求的拓扑有序序列，则说明AOV网络中存在有向环，此AOV网络所代表的工程是不可行的。
3.为何需要采用循环队列？n个空间的循环队列，最多存储多少个元素？为什 么？ 答：循环队列以克服顺序队列的"假上溢"现象，能够使存储队列的向量空间得到充分的利用，所以采用循环队列。 n个空间的循环队列，最多存储n-1个元素，那是为了区别循环队列的队空和队满的条件。队空的条件是Q.front==Q.rear，而队满的条件是(Q.rear+1)%N==Q.front(N是数组中单元的总数)，因此，Q.rear所指向的数组单元处于未用状态。所以说，N个单元的数组所存放的循环队列最大长度是N-1。 4.简述堆的删除算法，其删除的是那个值？ 答：堆的删除算法：首先，移除根节点的元素（并把根节点作为当前结点）比较当前结点的两个孩子结点的元素大小，把较大的那个元素移给当前结点，接着把被移除元素的孩子结点作为当前结点，并再比较当前结点的孩子的大小，以此循环，直到最后一个叶子结点的值大于或等于当前结点的孩子结点或孩子结点的位置超过了树中元素的个数，则退出循环。最后把最后叶子结点的元素移给当前结点。 在堆的算法里面，删除的值为根值。 5.线索二叉树中，什么是线索，它是否唯一？可有根据什么顺序得到？
0一．是非题 1. 数据结构(应该是抽象数据类型)可用三元式表示（D，S，P）。其中：D是数据对象，S 是D上的关系，P是对 D的基本操作集。(f) 2 简单地说,数据结构是带有结构的数据元素的集合。(t) 3 判断带头结点的非空循环单链表（头指针为L）中指针p所指结点是最后一个元素结点 的条件是：p->next==L。(t) 4 线性表的链式存储结构具有可直接存取?表中任一元素的优点。(f) 5 线性表的顺序存储结构优于链式存储结构。(f) 6. 在单链表P指针所指结点之后插入S结点的操作是： P->next= S ; S-> next = P->next;。(顺序弄反了)(f) 7 对于插入、删除而言，线性表的链式存储优于顺序存储。(t) 8. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(f) 9. 栈和队列是操作上受限制的线性表。(t) 10. 队列是与线性表完全不同的一种数据结构。栈和队列是操作上受限制的线性表(f) 11. 队列是一种操作受限的线性表，凡对数据元素的操作仅限一端进行。对列不是(f) 12. 栈和队列也是线性表。如果需要，可对它们中的任一元素进行操作。(f) 13. 栈是限定仅在表头进行插入和表尾进行删除运算的线性表。(f) 14. 二叉树中每个结点有两个子结点，而对一般的树，则无此限制，所以，二叉树是树的 特殊情形。(f) 15 二叉树是一棵结点的度最大为二的树二叉树和树相互独立。(f) 16 赫夫曼树中结点个数一定是奇数。(t) 17 在二叉树的中序遍历序列中，任意一个结点均处在其左孩子结点的后面。(t) 18 假设B是一棵树，B′是对应的二叉树。则B的后根遍历相当于B′的后序遍历后根遍历相当于中序遍历。(f) 19. 通常，二叉树的第i层上有2i-1个结点。应该为1~2i-1个(f) 20. 中序线索二叉树的优点是便于在中序下查找直接前驱结点和直接后继结点。(t) 21 二叉树的先序遍历序列中，任意一个结点均处在其孩子结点的前面。(t) 22 由树结点的先根序列和后根序列可以唯一地确定一棵树。 (t) 23 邻接多重表可以用以表示无向图，也可用以表示有向图。只能表示无向图，有向图用十字链表(f) 24 可从任意有向图中得到关于所有顶点的拓扑次序带环图没有。(f) 25 有向图的十字链表是将邻接表和逆邻接表合二为一的链表表示形式。(t) 26 关键路径是AOE网中源点到汇点的最短路径。(f) 27 连通图G的生成树是一个包含G的所有n个顶点和n-1条边的子图。(f) 28 一个无向图的连通分量是其极大的连通子图。(t) 29 十字链表可以表示无向图，也可用以表示有向图。(f) 30 邻接表可以表示有向图，也可以表示无向图。（t ） 31. 二叉排序树的平均查找长度为O(logｎ)。(t) 32. 二叉排序树的最大查找长度与（LOG2N）同阶。(f) 33 选用好的HASH函数可避免冲突。哈希函数有几种处理冲突的方法(f) 34 折半查找不适用于有序链表的查找。(t) 35. 对于目前所知的排序方法，快速排序具有最好的平均性能。(t) 36 对于任何待排序序列来说，快速排序均快于冒泡排序。(f)
数据结构考试复习题集团档案编码：[YTTR-YTPT28-YTNTL98-UYTYNN08]
复习题集 一判断题 （√）1. 在决定选取何种存储结构时，一般不考虑各结点的值如何。 （√）2. 抽象数据类型与计算机内部表示和实现无关。 （×）3. 线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。 （×）4. 链表的每个结点中都恰好包含一个指针。 （×）5.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 （×）6. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（×）7. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （×）8. 线性表在物理存储空间中也一定是连续的。 （×）9. 顺序存储方式只能用于存储线性结构。 （√）10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）11.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（√）12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）13.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （×）14.二叉树的度为2。 （√）15.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （×）16.二叉树中每个结点的两棵子树的高度差等于1。 （√）17.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （√）18.具有12个结点的完全二叉树有5个度为2的结点。 （√）19.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 （×）20.在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。 （×）21.计算机处理的对象可以分为数据和非数据两大类。[计算机处理的对象都是数据]（×）22.数据的逻辑结构与各数据元素在计算机中如何存储有关。 （×）23.算法必须用程序语言来书写。 （×）24.判断某个算法是否容易阅读是算法分析的任务之一。 （×）25.顺序表是一种有序的线性表。[任何数据结构才用顺序存储都叫顺序表] （√）26.分配给顺序表的内存单元地址必须是连续的。 （√）27.栈和队列具有相同的逻辑特性。[它们的逻辑结构都是线性表]
贵州大学理学院数学系信息与计算科学专业 《数据结构》期末考试试题及答案 (2003-2004学年第2学期) 一、单项选择题 1．对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（）。 (A)、正确性(B). 可行性(C). 健壮性(D). 输入性 2．设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（）。 for(i=n-1；i>=0；i--) for(j=0；j
数据结构期中练习 学号姓名 一、选择题 1.数据结构是研究数据的（）以及它们之间的相互关系。 （A）理想结构，物理结构（B）理想结构，抽象结构 （C）物理结构，逻辑结构（D）抽象结构，逻辑结构 参考答案：C 2.数据结构是一门研究非数值计算的程序设计问题中计算机的（①）以及它们之间的（②）和运算等的学科。 ① （A）数据元素（B）计算方法（C）逻辑存储（D）数据映像 ② （A）结构（B）关系（C）运算（D）算法 参考答案：A B 3.判定一个栈ST(最多元素为m0)为空的条件是（）。 （A） ST-〉top!=0 （B）ST-〉top==0 （C）ST-〉top!=m0 （D）ST-〉top=m0 参考答案：B 4.判定一个栈ST(最多元素为m0)为栈满的条件是（）。 （A）ST->top!=0 （B）ST->top==0 （C）ST->top!=m0-1（D）ST->top==m0 参考答案：D 5.算法分析的目的是（）。 （A）找出数据结构的合理性（B）研究算法中的输入和输出的关系 （C）分析算法的效率以求改进（D）分析算法的易懂性和文档性 参考答案：C 6.稀疏矩阵一般的压缩存储方法有两种,即（）。 （A）二维数组和三维数组（B）三元组和散列 （C）三元组和十字链表（D）散列和十字链表
参考答案：C 7. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。 （A）64（B）63 （C）63.5 （D）7 参考答案：C 8. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行（） （A）s->next=p;p->next=s; （B） s->next=p->next;p->next=s; （C）s->next=p->next;p=s; （D）p->next=s;s->next=p; 参考答案：B 9.在一个单链表中，若删除p所指结点的后续结点，则执行（） （A）p->next=p->next->next; （B）p=p->next; p->next=p->next->next; （C）p->next=p->next; （D）p =p->next->next; 参考答案：A 10.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,该数组按列存放时,元素A[4][7]的起始地址为（）。 （A）SA+141（B）SA+180（C）SA+222（D）SA+225 参考答案：B 11. 一个栈的入栈序列是a,b,c,d,e,则栈的不可能的输出序列是（）。 （A） edcba（B）decba（C）dceab （D）abcde 参考答案：C 12.二维数组M的元素是4个字符(每个字符占一个存储单元)组成的串,行下标i的范围从0到4,列下标j的范围从0到5,M按行存储时元素M[3][5]的起始地址与M按列存储时元素( ) 的起始地址相同。 （A）M[2][4]（B）M[3][4]（C）M[3][5]（D）M[4][4] 参考答案：B 13.数组A[8][10]中,每个元素A的长度为3个字节,从首地址SA开始连续存放在存储器内,存放该数组至少需要的单元数是（）。 （A）80（B）100（C）240（D）270 参考答案：C
数据结构习题集含答案 目录
选择题 第一章绪论 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 ）。 A、空间复杂度和时间复杂度 B、正确性和简明性 C、可读性和文档性 D、数据复杂性和程序复杂性 8.计算机内部处理的基本单元是（B ） A、数据 B、数据元素 C、数据项 D、数据库 9.数据在计算机内有链式和顺序两种存储方式，在存储空间使用的灵活性上，链式存储 比顺序存储要（B ）。 A、低 B、高 C、相同 D、不好说 10.算法的时间复杂度取决于（ C ） A 、问题的规模B、待处理数据的初始状态 C、问题的规模和待处理数据的初始状态 D、不好说 11.数据结构既研究数据的逻辑结构，又研究物理结构，这种观点（B ）。 A、正确 B、错误 C、前半句对，后半句错 D、前半句错，后半句对 12.在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和静态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 13.线性表的顺序存储结构是一种( )的存储结构，线性表的链式存储结构是一种（ A ） 存储结构。 A、随机存取 B、顺序存取 C、索引存取 D、散列存取 14.*下列程序的时间复杂度是（A ） for (i=1; i<=n; ++i){ for (j=1; j<=n; ++j){ c [i][j]=0;
2012年数据结构期末考试题及答案 一、选择题 1．在数据结构中，从逻辑上可以把数据结构分为C。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．内部结构和外部结构 2．数据结构在计算机内存中的表示是指A。 A．数据的存储结构B．数据结构C．数据的逻辑结构D．数据元素之间的关系 3．在数据结构中，与所使用的计算机无关的是数据的A结构。 A．逻辑B．存储C．逻辑和存储D．物理 4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储C。 A．数据的处理方法B．数据元素的类型 C．数据元素之间的关系D．数据的存储方法 5．在决定选取何种存储结构时，一般不考虑A。 A．各结点的值如何B．结点个数的多少 C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便。 6．以下说法正确的是D。 A．数据项是数据的基本单位 B．数据元素是数据的最小单位 C．数据结构是带结构的数据项的集合 D．一些表面上很不相同的数据可以有相同的逻辑结构 7．算法分析的目的是C，算法分析的两个主要方面是A。 （1）A．找出数据结构的合理性B．研究算法中的输入和输出的关系 C．分析算法的效率以求改进C．分析算法的易读性和文档性 （2）A．空间复杂度和时间复杂度B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 8．下面程序段的时间复杂度是O（n2）。
s ＝0； for（I ＝0；i＜n；i＋＋） for（j＝0；j＜n；j＋＋） s ＋＝B[i][j]； sum ＝s ； 9．下面程序段的时间复杂度是O（n*m）。 for（i ＝0；i＜n；i＋＋） for（j＝0；j＜m；j＋＋） A[i][j] ＝0； 10．下面程序段的时间复杂度是O（log3n）。 i ＝0； while（i＜＝n） i ＝i * 3； 11．在以下的叙述中，正确的是B。 A．线性表的顺序存储结构优于链表存储结构 B．二维数组是其数据元素为线性表的线性表 C．栈的操作方式是先进先出 D．队列的操作方式是先进后出 12．通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着B 。 A．数据元素具有同一特点 B．不仅数据元素所包含的数据项的个数要相同，而且对应的数据项的类型要一致 C．每个数据元素都一样 D．数据元素所包含的数据项的个数要相等 13．链表不具备的特点是A。 A．可随机访问任一结点B．插入删除不需要移动元素 C．不必事先估计存储空间D．所需空间与其长度成正比 14．不带头结点的单链表head为空的判定条件是A。
第1章绪论 1 自测习题 二、选择题 1．以下数据结构中，属于线性结构的是 ( B ) A）有向图B）串C）线索二叉树D）B树 2．下列与数据元素有关的叙述中错误的是 (A) A）数据元素是有独立含义的数据最小单位 B）数据元素是描述数据的基本单位 C）数据元素可以称做结点 D）数据元素可以称做记录 3．以下术语中与数据的存储结构无关的是 (A) A）栈B）散列表C）顺序表D）双链表 4．以下数据结构中，属于线性结构的是 (B) A）有向图B）串C）线索二叉树D）B树 三、填空题 1．数据结构包括的三方面内容分别是：数据的逻辑结构、数据的存储结构和数据的运算。 2．数据元素是数据的基本单位，在某些情况下也可以称为结点、记录和顶点。
3．数据逻辑结构的4种基本形态包括集合结构、线性结构、树型结构和图（网）结构。 4．一个正确的算法应该具有5个特性：输入、输出、确定性、可行性和有穷性。 5．数据的存储结构包括顺序、链式、索引和散列四种。6．一个数据结构在计算机中的映象称为存储结构。 7．一个算法的效率主要是指该算法的时间效率和空间效率。 8．以下程序段的时间复杂度T（n）=_) O_____。 (2n sum=0; for(i=0 ; i 环链表 2．线性表是具有n 个 (B) 的有限序列。 A ）数据项 B ）数据元素 C ）表元素 D ）字符 3．若长度为n 的线性表采用链式存储结构，访问其第i 个元素的算 法时间复杂度为 (B) A ）O(1) B ）O(n) C ） O(n 2) D ）O(log 2n) 4．在长度为n 的顺序表中，若要删除第i （1≤i ≤n ）个元素，则 需要向前移动的元素的次数为 (B) A ）i B ）n-i C ）n-i+1 D ）n-i-1 5．在长度为n 的顺序表中第i （1≤i ≤n ）个位置上插入一个元素时， 为留出插入位置所需移动元素的次数为 (C) A ）n-i B ）i C ）n-i+1 D ）n-i-1 三、填空题 1．有一单链表结构如下： 图2-1 填空题1附图 若要删除值为c 的结点，应做的操作是 p->link=p->link->link 。 2．线性表L=( a 1,a 2,…a n )用数组存储。假定删除表中任一元素的概 … … data link 2005年－2006学年第二学期“数据结构”考试试题（A）姓名学号(序号)_答案隐藏班号 要求：所有的题目的解答均写在答题纸上（每张答题纸上要写清晰姓名、班号和学号），需写清晰题目的序号。每张答题纸都要写上姓名和序号。 一、单项选择题（每小题2分，共20分） 1．数据的运算a 。 A.效率与采用何种存储结构有关 B.是根据存储结构来定义的 C.有算术运算和关系运算两大类 D.必须用程序设计语言来描述 答：A。 2.链表不具备的特点是 a 。 A.可随机访问任一结点 B.插入删除不需要移动元素 C.不必事先估计存储空间 D.所需空间与其长度成正比 答：参见本节要点3。本题答案为：A。 3.在顺序表中删除一个元素的时间复杂度为 c 。 A.O(1) B.O(log2n) C.O(n) D.O(n2) 答：C。 4．以下线性表的存储结构中具有随机存取功能的是d 。 A.不带头结点的单链表 B.带头结点的单链表 C.循环双链表 D.顺序表 解D。 5.一个栈的进栈序列是a，b，c，d，e，则栈的不可能的输出序列是 c 。A.edcba B.decba C.dceab D.abcde 答：C。 6.循环队列qu的队空条件是 d 。 A. (qu.rear+1)%MaxSize==(qu.front+1)%MaxSize B. (qu.rear+1)%MaxSize==qu.front+1 C.(qu.rear+1)%MaxSize==qu.front D.qu.rear==qu.front 答：D。 7.两个串相等必有串长度相等且 b 。 A.串的各位置字符任意 B.串中各位置字符均对应相等 C.两个串含有相同的字符 D.两个所含字符任意 答：B。 8.用直接插入排序对下面四个序列进行递增排序，元素比较次数最少的是 c 。 A.94,32,40,90,80,46,21,69 B.32,40,21,46,69,94,90,80 C.21,32,46,40,80,69,90,94 D.90,69,80,46,21,32,94,40 答：C。 9.以下序列不是堆（大根或小根）的是 d 。 A.{100,85,98,77,80,60,82,40,20,10,66} B.{100,98,85,82,80,77,66,60,40,20,10} C.{10,20,40,60,66,77,80,82,85,98,100} D.{100,85,40,77,80,60,66,98,82,10,20} 第1章绪论 一、判断题 1.数据的逻辑结构与数据元素本身的容和形式无关。（√） 2.一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。（√） 3.数据元素是数据的最小单位。（×） 4.数据的逻辑结构和数据的存储结构是相同的。（×） 5.程序和算法原则上没有区别，所以在讨论数据结构时可以通用。（×） 6.从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。（√） 7.数据的存储结构是数据的逻辑结构的存储映象。（√） 8.数据的物理结构是指数据在计算机实际的存储形式。（√） 9.数据的逻辑结构是依赖于计算机的。（×） 10.算法是对解题方法和步骤的描述。（√） 二、填空题 1.数据有逻辑结构和存储结构两种结构。 2.数据逻辑结构除了集合以外，还包括线性结构、树形结构和图形结构。 3.数据结构按逻辑结构可分为两大类，它们是线性结构和非线性结构。 4.树形结构和图形结构合称为非线性结构。 5.在树形结构中，除了树根结点以外，其余每个结点只有1个前驱结点。 6.在图形结构中，每个结点的前驱结点数和后继结点数可以任意多个。 7.数据的存储结构又叫物理结构。 8.数据的存储结构形式包括顺序存储、链式存储、索引存储和散列存储。 9.线性结构中的元素之间存在一对一的关系。 10.树形结构中的元素之间存在一对多的关系。 11.图形结构的元素之间存在多对多的关系。 12.数据结构主要研究数据的逻辑结构、存储结构和算法（或运算）3个方面的容。 13.数据结构被定义为（D，R），其中D是数据的有限集合，R是D上的关系有限集合。 14.算法是一个有穷指令的集合。 15.算法效率的度量可以分为事先估算法和事后统计法。 16.一个算法的时间复杂度是算法输入规模的函数。 17.算法的空间复杂度是指该算法所耗费的存储空间，它是该算法求解问题规模的n的函数。 18.若一个算法中的语句频度之和为T(n)=6n+3nlog2n,则算法的时间复杂度为O（nlog2n）。 19.若一个算法的语句频度之和为T(n)=3n+nlog2+n2,则算法的时间复杂度为O（n2）。 20.数据结构是一门研究非数值计算的程序问题中计算机的操作对象，以及它们之间的关系和运算的学 科。 三、选择题 1.数据结构通常是研究数据的（A）及它们之间的相互关系。 A．存储结构和逻辑结构B．存储和抽象C．联系和抽象D．联系与逻辑 2.在逻辑上可以把数据结构分成（C）。 A．动态结构和静态结构B．紧凑结构和非紧凑结构 C．线性结构和非线性结构D．部结构和外部结构。 3.数据在计算机存储表示时，物理地址和逻辑地址相同并且是连续的，称之为（C）。 A．存储结构B．逻辑结构C．顺序存储结构D．链式存储结构 4.非线性结构中的每个结点（D）。 A．无直接前驱结点．B．无直接后继结点． 数据结构复习题答案 一、选择题 1.栈和队列的共同特点是( )。 A.只允许在端点处插入和删除元素 B.都是先进后出 C.都是先进先出 D.没有共同点 2.用链接方式存储的队列，在进行插入运算时 ( ). A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、 尾指针可能都要修改 3.以下数据结构中哪一个是非线性结构？ ( ) A. 队列 B. 栈 C. 线 性表 D. 二叉树 4.设有一个二维数组A[m][n]，假设A[0][0]存放 位置在644 ，A[2][2]存放位置在676(10)，每个 (10) 元素占一个空间，问A[3][3](10)存放在（）位 置，脚注 表示用10进制表示。 (10) A．688 B．678 C．692 D．696 5.树最适合用来表示( )。 A.有序数据元素 B. 无序数据元素 C.元素之间具有分支层次关系的数据 D.元素之间无联系的数据 6.二叉树的第k层的结点数最多为( ). A．2k-1 B.2K+1 C.2K-1 D. 2k-1 7.若有18个元素的有序表存放在一维数组A[19] 中，第一个元素放A[1]中，现进行二分查找，则 查找A［3］的比较序列的下标依次为( ) A. 1，2，3 B. 9，5，2， 3 C. 9，5，3 D. 9，4，2， 3 8.对n个记录的文件进行快速排序，所需要的辅 助存储空间大致为( ) A. O（1） B. O（n） C. O n） D. O（n2） （1og 2 9.对于线性表（7，34，55，25，64，46，20，10） 进行散列存储时，若选用H（K）=K %9作为散列 函数，则散列地址为1的元素有（）个， A．1 B．2 C．3 D．4 数据结构基础及深入及考试 复习资料 习题及实验参考答案见附录 结论 1、数据的逻辑结构是指数据元素之间的逻辑关系。即从逻辑关系上描述数据，它与数据的存储无关，是独立于计算机的。 2、数据的物理结构亦称存储结构，是数据的逻辑结构在计算机存储器内的表示（或映像）。它依赖于计算机。存储结构可分为4大类：顺序、链式、索引、散列 3、抽象数据类型：由用户定义，用以表示应用问题的数据模型。它由基本的数据类型构成，并包括一组相关的服务（或称操作）。它与数据类型实质上是一个概念，但其特征是使用与实现分离，实行封装和信息隐蔽（独立于计算机）。 4、算法：是对特定问题求解步骤的一种描述，它是指令的有限序列，是一系列输入转换为输出的计算步骤。 5、在数据结构中，从逻辑上可以把数据结构分成（ C ） A、动态结构和表态结构 B、紧凑结构和非紧凑结构 C、线性结构和非线性结构 D、内部结构和外部结构 6、算法的时间复杂度取决于（ A ） A、问题的规模 B、待处理数据的初态 C、问题的规模和待处理数据的初态 线性表 1、线性表的存储结构包括顺序存储结构和链式存储结构两种。 2、表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时，插入一个元素所需移动元素的平均次数为（ E ），删除一个元素需要移动的元素的个数为（ A ）。 A、(n-1)/2 B、n C、n+1 D、n-1 E、n/2 F、(n+1)/2 G、(n-2)/2 3、“线性表的逻辑顺序与存储顺序总是一致的。”这个结论是（ B ） A、正确的 B、错误的 C、不一定，与具体的结构有关 4、线性表采用链式存储结构时，要求内存中可用存储单元的地址（ D ） A、必须是连续的 B、部分地址必须是连续的C一定是不连续的D连续或不连续都可以 5、带头结点的单链表为空的判定条件是（ B ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 6、不带头结点的单链表head为空的判定条件是（ A ） A、head==NULL B、head->next==NULL C、head->next=head D、head!=NULL 7、非空的循环单链表head的尾结点P满足（ C ） A、p->next==NULL B、p==NULL C、p->next==head D、p==head 8、在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是（ B ） A、O(1) B、O(n) C、O(n2) D、O(nlog2n) 9、在一个单链表中，若删除p所指结点的后继结点，则执行（ A ） 一、选择题 1、一个n个顶点的无向连通图，其边的个数至少为（）。 A．n-1 B．n C．n+1 D．nlogn 2、以下数据结构中，（）是非线性数据结构。 A．树B．字符串C．队列D．栈 3、在长度为n的顺序表的第i个位置上插入一个元素（1≤i≤n+1），元素的移动次数为（）。 A．n –i+1 B．n –i C．i D．i-1 4、与线性表的链接存贮不相符合的特性是（）。 A．便于插、删运算B．需要连续的存贮空间 C．只能顺序查找D．存贮空间动态分配 5、顺序存放的循环队列的元素以数组A[m]存放,其头尾指针分别为front和rear，则当前队列中的元素个数 为（）。 A．(rear-front+m)%m B．rear-front+1 C．(front+rear+m)%m D．(rear-front)%m 6、一个有n个顶点的无向图最多有( )条边。 A．n(n-1)/2 B．n (n-1) C．n-1 D．n+1 7、设栈的入栈序列是1，2，3，4，则（）不可能是其出栈序列。 A．1，2，4，3 B．2，1，3，4 C．1，4，3，2 D．4，3，1，2， 8、从逻辑上可以把数据结构分为（）两大类。 A．动态结构、静态结构B．初等结构、构造型结构 C．线性结构、非线性结构D．树型结构、图型结构 9、某二叉树的先序序列和后序序列正好相反，则该二叉树一定是（） A．空或只有一个根结点B．高度等于其结点数 C．任一结点无左孩子D．任一结点无右孩子 10、已知一个有向图用邻接矩阵表示，要删除所有从第i个结点发出的边，应该（）。 A．将邻接矩阵的第i 行删除B．将邻接矩阵的第i 行元素全部置零 C．将邻接矩阵的第i 列删除D．将邻接矩阵的第i 列元素全部置零 11、算法分析的两个主要方面是（） A．空间复杂性和时间复杂性B．正确性和简明性 C．可读性和文档性D．数据复杂性和程序复杂性 12、线性表若采用链式存储结构时，要求内存中可用存储单元的地址( )。 A．必须是连续的B．部分地址必须是连续的 C．一定是不连续的D．连续或不连续都可以 13、具有6个顶点的无向连通图的生成树应有（）条边。 A．5 B．6 C．7 D．8 14、设栈的输入序列是A、B、C，则（）不可能是其出栈序列。 A．CBA B．CAB C．BCA D．ACB 15、有一个含头结点的单链表，头指针为head，则判断其是否为空的条件为（）。 A．head==NULL B．head->next==NULL C．head->next== head D．head ！=NULL 16、栈和队都是（） A．顺序存储的线性结构B．链式存储的非线性结构 C．限制存取点的线性结构D．限制存取点的非线性结构 17、在下述结论中，正确的是（） ①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树结点个数小于或等于深度相同的满二叉树。 A．①②③B．②③④C．②④D．①④ 18、以下数据结构中，（）是非线性数据结构。 《数据结构》课程复习资料 一、填空题: 1.设需要对5个不同的记录关键字进行排序，则至少需要比较________次，至多需要比较__________次。 2.设二叉排序树的高度为h，则在该树中查找关键字key最多需要比较_________次。 3.设在长度为20的有序表中进行二分查找，则比较一次查找成功的结点数有_________个，比较两次查 找成功有结点数有_________个。 4.数据结构从逻辑上划分为三种基本类型：___________、__________和___________。 5.在一个具有n个顶点的无向完全图中，包含有________条边，在一个具有n个顶点的有向完全图中， 包含有________条边。 6.向一棵B_树插入元素的过程中，若最终引起树根结点的分裂，则新树比原树的高度___________。 7.在堆排序的过程中，对任一分支结点进行筛运算的时间复杂度为________，整个堆排序过程的时间复 杂度为________。 8.在快速排序、堆排序、归并排序中，_________排序是稳定的。 9.在有n个叶子结点的哈夫曼树中，总结点数是_______。 10.一棵树T采用二叉链表存储，如果树T中某结点为叶子结点，则在二叉链表BT中所对应的结点一定 _______。 11.3.已知数组A［10］［10］为对称矩阵，其中每个元素占5个单元。现将其下三角部分按行优先次序存 储在起始地址为1000的连续的内存单元中，则元素A［5，6］对应的地址是_______。 12.在有n个结点的无向图中，其边数最多为_______。 13.取出广义表A=(x,(a,b,c,d))中原子x的函数是_______。 14.对矩阵采用压缩存储是为了___ ____。 15.带头结点的双循环链表L为空表的条件是_______。 16.设线性表中元素的类型是实型，其首地址为1024，则线性表中第6个元素的存储位置是。 17.对于顺序存储的栈，因为栈的空间是有限的，在进行运算时，可能发生栈的上溢，在进行运 算时，可能发生栈的下溢。 18.在双向链表中，每个结点有两个指针域，一个指向，另一个指向。 19.由一棵二叉树的前序序列和可唯一确定这棵二叉树。 20.折半查找的存储结构仅限于___ _，且是_ ___。 21.对于一个顺序存储的线性表，在表头插入元素的时间复杂度为____________,在表尾插入元素的时间复 杂度为________________。 22.在稀疏距阵所对应的三元组线形表中，每个三元组元素按____________为主序，__________为辅序的 次序排列。 23.中缀表达示3+X*（2.4/5-6）所对应的后缀表达示为______________。 24.在一棵高度为h的3叉树中，最多含有_______结点。 25.分析下面算法（程序段），给出最大语句频度，该算法的时间复杂度是__ __。 for (i=0;i数据结构期末考试试题含复习资料
数据结构练习试题和答案解析
数据结构复习题答案
数据结构(第4版)习题及实验参考答案数据结构复习资料完整版(c语言版)
数据结构复习题及答案
数据结构复习题及参考答案
相关主题
文本预览