数据结构复习题及答案
数据结构习题
一、名词解释
1. 数据、数据元素、数据项、数据结构、数据的逻辑结构、数据物理结构、顺序存储、链式存储、算法、时间复杂度、空间复杂度。
2. 线性表、顺序表、单链表、双向链表、循环链表、双向循环链表、三个概念的区别：头指针、头结点、首元结点(第1个元素结点)。
3. 栈（顺序栈、链栈）、队列（顺序队、链队）、循环队列、递归、稀疏矩阵、三元组。
4. 树、叶子结点、结点的度、树的度、树的高(深)度、二叉树、遍历、满二叉树、完全二叉树、哈夫曼树、WPL、哈夫曼编码。
5. 图（有向、无向）、网、边、弧、度、入度、出度、完全图（有向、无向）、（强）连通图（分量）、（最小）生成树、邻接矩阵、邻接表、DFS、BFS。
6. 查找表、关键字、静态查找、动态查找、ASL、顺序查找、折半查找、分块查找、二叉排序树。
7、排序、内（外）排序、稳定性、插入（直接、希尔），交换（起泡、快速），选择（直接、堆），2路归并。
一、填空题
1.数据结构是研究数据的_逻辑结构__和___物理结构__，并在这种结构上定义相关的运算，设计实
现这些运算的算法，分析算法的效率。算法的效率包括时间和空间两个方面，分别称为___时间复杂度____和__空间复杂度___。
2.数据的基本单位是__数据元素__ ，数据的最小单位是__数据项_ 。
3.算法是对特定问题求解___步骤___的一种描述，是指令的有限序列。
4.一个算法的时间复杂度为(3n3+2n—7)，其数量级表示为O（n3）_。
5.一个算法具有5个特性：确定性、可行性、有穷性、输入和输出。
6.算法性能的分析和度量，可以从算法的时间复杂度和空间复杂度来评价算法的优劣。
7.数据的逻辑结构包括集合结构、线性结构、树形结构和图型结构四种类型。
8.数据结构在计算机中的表示称为数据的物理结构，它可以采用__顺序存储___或__链式存储_
两种存储方法。
9.线性表有两种存储结构，分别为顺序存储和链式存储。
10.链式存储的特点是利用指针来表示数据元素之间的逻辑关系。
11.若频繁地对线性表进行插入和删除操作，该线性表宜采用_链式存储__存储结构。
12.线性表中的数据元素之间具有一对一的线性关系，除第一个和最后一个元素外，其他数据
元素有且只有一个直接后继和直接前趋。
13.在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next=__p->next______和
p->next=__s______的操作。
14.在一个单链表中删除p的后继结点q时，应执行以下操作p->next= q->next。
15.对带头结点head的单链表，则判断其为空的条件为head->next=NULL。
16.对带头结点head的循环单链表尾结点(由p所指向)判非空的条件为p->next=head。
17.在栈结构中，允许插入的一端称为栈顶；在队列结构中，允许插入的一端称为队尾。
18.队列中元素的入队和出队应遵循__先进先出 ____原则，数据元素1，2，3，4，5按照次序入队
后，第一个出队的是__1 ____。
19.在循环队列中，存储空间为0～n-1。设队头指针front指向队头元素前一个空闲元素，队尾指
针指向队尾元素，那么其队空标志为rear=front，队满标志为(rear+1)% n=front。
20.设顺序表有19个元素，第一个元素的地址为200，且每个元素占3个字节，则第14个元素的存
储地址为239。
21.在一个长度为n的顺序表中删除第i个元素（1≤i≤n），需向前移动n-i个元素。
22.在一个长度为n的顺序表中第i个元素前（1≤i≤n），插入一个元素，需向后移动n-i+1
个元素。
23.在顺序存储的线性表中插入或删除一个元素平均约移动表中__50%_（或一半）_的元素。
24.在顺序表中访问任意一结点的时间复杂度均为 O(1) ，因此，顺序表也称为随机存取的数据
结构。
25.在n个结点的单链表中要删除已知结点*p，需找到它的前驱结点的地址，其时间复杂度为O（n）。
26.一个广义表为(a,(a,b),d,e,((i,j),k))，则该广义表的长度为__5___，深度为__3___。
27.已知广义表A=((a,b,c),(d,e,f))，则运算tail (head (tail(A)))=(e,f)__。
28.已知广义表Ls=(a,(b,c,d),e)，运用head和tail函数取出Ls中的原子b的运算是
_head(head(tail(LS)))___。
29.广义表((a,b),c,d)的表头是(a,b)表尾是(c,d)。
30.广义表(a,b,c,d)的表头是a 表尾是(b,c,d)___。
31.两个串相等的充分必要条件是:__串长相等___ 且 __对应的字符相等_。
32.不含任何字符的串称为空串其长度为0 。
33.对于稀疏矩阵的压缩存储，通常用一个三元组表示非零元素的信息，其中包括非零元素所在的
行、列以及它的值。
34.若二叉树中有20个叶子结点，则该二叉树有19 个度为2的结点。
35.若二叉树中度为2的结点有15个，则该二叉树有__16________个叶子结点。
36.深度为h且有__2^h-1____个结点的二叉树称为满二叉树。
37.深度为k的二叉树最多有_2^k-1个结点，最少有k个结点，第i 层上最多有
_2^(i-1)____个结点。
38.深度为5的满二叉树共有31个结点，其中有__16_____个叶子节点。
39.若深度为6的完全二叉树的第6层有3个叶结点，则该二叉树一共有34个结点。
40.深度为15的满二叉树上，第11层有 _2^(11-1)=1024个结点。
41.一棵具有100个结点的完全二叉树，它的深度为7，其中度为1的结点有1个。
42.某二叉树的后根遍历序列为abd，中根遍历序列为adb，则它的先根遍历序列为dab。
43.哈夫曼树是指对于一组带有确定权值的叶子结点构造的具有最小带权路径长度
的二叉树。
44.具有m个叶子结点的哈夫曼树共有2m-1个结点。
45.已知一棵哈夫曼树含有60个叶子结点，则该树中共有 59个非叶子结点。
46.在一个具有n个顶点无向完全图中，含有n(n-1)/2边；在一个具有n个顶点有向完全
图中，含有n(n-1)边。一个具有4个顶点的无向完全图有6条边。
47.具有n个顶点的连通图至少需有n-1条边。
48.一个连通图的生成树是该图的极小连通子图。若这个连通图有n个顶点，则它的生成树
有n-1条边。
49.在有向图的邻接矩阵中，第i行中非零元素的个数正好是第i个顶点的出度；第i列中非零
元素的个数正好是第i个顶点的入度。
50.在一个图中，所有顶点的度数之和等于所有边数的2倍。
51.在无向图G的邻接矩阵A中，若A［i］［j］等于1，则A［j］［i］等于1。
52.对二叉排序树进行中序遍历，可以得到按关键字从小到大排列的结点序列。
53.一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当折半查找值为82的
结点时，经过 4 次比较后查找成功。
54.在线性表中采用折半查找法查找一个数据元素，线性表中元素应该按值有序，并且采用___顺序
存储__存储方法。
55.在简单选择排序、堆排序、快速排列、归并排序四种排序方法中，排序方法稳定的是__归并排序。
56.冒泡排序是一种稳定的排序方法，对n个元素的序列进行冒泡排序时，最多需进行n-1趟。该
排序方法的时间复杂度为O(n2)。
57.给定序列{100，86，48，73，35，39，42，57，66，21}，按堆的定义，则它一定大根堆。
58.数据结构是指数据及其相互之间的_一种或多种关系____。当结点之间存在M对N（M：N）的联
系时，称这种结构为____图状结构_____。
59.队列的插入操作是在队列的__队尾___进行，删除操作是在队列的__队头__进行。
60.每次从无序表中顺序取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做__直接
插入_排序；每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做__简单选择(或直接选择)____排序。
61.二叉树的前序遍历序列为A，B，C，E，F，D，G，H，中序遍历序列为A，E，C，F，B，G，，H，
其后序遍历序列为__ E,F,C,G,H,D,B,A____。
62.对于一棵具有n个结点的二叉树，若一个结点的编号为i(0＜i＜n-1），则它的左孩子结点的编
号为2i，右孩子结点的编号为 2i+1，双亲结点的编号为 i/2 。
63.在一个具有6个顶点的无向完全图中，包含有15 条边，在一个具有6个顶点的有向完全
图中，包含有30条弧。
64.快速排序在平均情况下的时间复杂度为__O(nlog2n)__，在最坏情况下的时间复杂度为__
O(n2)__。
65.从一棵二叉排序树中查找一个元素时，若元素的值等于根结点的值，则表明__查找成功_____，
若元素的值小于根结点的值，则继续向__左子树______查找，若元素的大于根结点的值，则继续向__右子树______查找。
66.在循环单链表中，最后一个结点的指针域指向___首___结点。
67.假定一棵树的广义表表示为A（C，D（E，F，G），H（I，J）），则树中所含的结点数为_9_个，树
的深度为__3___，树的度为__3__。
68.通常从四个方面评价算法的质量：_正确性_、_可读性_、__健壮性__和__效率与低存储量
需求_。
69.假设一棵完全二叉树含1000个结点,则其中度为2的结点数为___499___。
70.一个算法的时间复杂度为(3n3+2n—7)／(5n)，其数量级表示为O(n2)。
71.在快速排序、堆排序和归并排序中，最坏时间复杂度为O(n2)的排序算法有_快速排序_____。
72.数据结构被形式地定义为（D, R），其中D是数据元素的有限集合，R是D上的关系有
限集合。
73.在归并排序中，进行每趟归并的时间复杂度为____O(n)_____，整个排序过程的时间复杂度为
___O(nlog2n)_______，空间复杂度为___ O(n)_____。
74.若一棵二叉树有10个叶结点，则该二叉树中度为2的结的点个数为__9___。
75.对用邻接矩阵表示的具有n个定点和e条边的图进行任一种遍历时，其时间复杂度为 O(n2)，
对用邻接表表示的图进行任一种遍历时，其时间复杂度为___ O(n+e) __。
76.从有序表（12，18，30，43，56，78，82，95）中依次二分查找43和56元素时，其查找长度分
别为__1____和___3___。
77.对于一棵具有n个结点的二叉树，用二叉链表存储时，其指针总数为_2n_个，其中_ n-1__个用
于指向孩子， n+1__个指针是空闲的。
78.从逻辑结构看，线性表是典型的___线性结构__，树是典型的___非线性结构___。
79.设二叉树中结点的两个指针域分别为lchild和rchild，则判断指针变量p所指向的结点为叶子
结点的条件是____p->lchild==NULL && p->rchild==NULL。
80.栈是一种__先进后出___表。队列又称为___先进先出___表。
81.若对序列(49，38，65，97，76，13，27，50)采用直接选择排序法排序，则第三趟结束后序列的
状态是__(13,27,38),97,76,49,65,50_。
82.利用关键码分别为10，20，30，40的四个结点，能构造出__14__种不同的二叉排序树.
83.设表中元素的初始状态是按键值递增的，分别用堆排序、快速排序、冒泡排序和归并排序方法对
其进行（按递增排序），__冒泡排序___最省时间， __快速排序___最费时间。
84.空串的长度是__0_；空格串的长度是__空格的个数_。串中所含字符个数称为该串的____长度_.
85.在n个结点的单链表中，在P指向的结点之后插入一个结点的时间复杂度为__ O(n)_。
86.设SQ为循环队列，存储在数组d[m]中，则SQ出队操作对其队头指针front的修改是__front=
（front+1）% m____。
87.树的度是指__树内各结点的度____的最大值。
88.已知链栈的结点结构为栈顶指针为top，则实现将指针p所指结点插入栈顶的语句依次为__
__p->next=top___和_top=p__。
89.堆排序的空间复杂度___ O(1)__。
90.深度为n(n>0)的二叉树最多有_____2^n-1___个结点。
91.设关键字序列为(K l，K2，…，K n)，则用筛选法建初始堆必须从第_n/2____个元素开始进行筛选。
92.图有_邻接矩阵___ 、____邻接表__等存储结构，遍历图有 _深度优先搜索____ 、 ___广度优
先搜索__等方法。
93.在一个有向图的邻接表中，一个顶点的链表中结点的个数等于这个顶点的__出度__ ，在逆邻接
表中，一个顶点的链表中结点的个数等于这个顶点的___入度__ 。
94.对于有10个元素的有序表采用二分查找，需要比较3次方可找到其对应的键值，则该元素在有
序表中的位置可能是_1，3，6，9___。
95.折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次
与表中元素______________比较大小。
96.在对一组记录关键字（54，38，96，23，15，72，60，45，83）进行冒泡排序时，整个冒泡排序
过程中需进行_8__趟才能完成。
97.对关键字序列(52，80，63，44，48，91)进行一趟快速排序之后得到的结果为__48，44，52，63，
80，91__。
98.在堆排序和快速排序中，若初始记录接近正序或反序，则选用_堆排序___；若初始记录基本无序，
则最好选用__快速排序___。
99.在对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序时，当把第7个记录
60插入到有序表时，为寻找插入位置至少需比较 __3________次。
100. 设一组记录关键字序列为(80，70，33，65，24，56，48)，则用筛选法建成的初始堆为_（80，70，56，65，24，33，48）或_(24，65，33，80，70，56，48)。
二、单选题
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．鉴别算法的可读性
6.某程序的时间复杂度为（3n+nlog2n+n2+8）, 其数量级表示为（）。
A．O（n） B．O（nlog2n） C．O（n2） D．O（log2n）
7.for（i=0；i for（j=0；j A［i］［j］=i*j； 上述程序段的时间复杂度为( ) A.O（n2） B.O（n） C.O（2n） D.O（1） 8.以下数据结构中哪一个是非线性结构？( ) A. 队列 B. 栈 C. 线性表 D. 二叉树 9.设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为( ) A.5 B.6 C.7 D.9 10.线性表采用链式存储结构时，要求内存中可用存储单元的地址( ) A. 必须是连续的 B. 必须是部分连续的 C. 一定是不连续的 D. 连续和不连续都可以 11.线性表是具有相同数据类型的n个__________的有限序列。 A.数据项 B.数据元素 C.表元素 D.字符 12.在一个具有n 个结点的有序单链表中插入一个新结点并仍然保持有序的时间复杂度是____。 A. O(1) B. O(n) C. O(n2) D. O(nlog2n) 13.用链接方式存储的队列，在进行插入运算时（） A. 仅修改头指针 B. 头、尾指针都要修改 C. 仅修改尾指针 D.头、尾指针可能都要修改 14.在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( ) A. n-i+1 B. i C. i+1 D. n-i 15.若带头结点的单链表的头指针为head，则该链表为空的判定条件是( ) A. head==NULL B. head->next==NULL C. head!=NULL D. head->next==head 16.已知栈的最大容量为4。若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行,则可能出现的出栈序列为（） A.5，4，3，2，1，6 B.2，3，5，6，1，4 C.3，2，5，4，1，6 D.1，4，6，5，2，3 17.若某线性表中最常用的操作是取第i 个元素和找第i个元素的前趋元素，则采用（）存储方式最节省时间。 A．单链表 B.双链表 C.单向循环 D.顺序表 18.对一个算法的评价，不包括如下（）方面的内容。 A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度 19.队列的删除操作是在（）进行。 A．队首 B．队尾 C．队前 D．对后 20.计算机识别、存储和加工处理的对象被统称为( ) A.数据 B.数据元素 C.数据结构 D.数据类型 21.串是任意有限个（） ①符号构成的序列②符号构成的集合 ③字符构成的序列④字符构成的集合 22.如果以链表作为栈的存储结构，则退栈操作时（） ①必须判别栈是否满②对栈不作任何判别 ③必须判别栈是否空④判别栈元素的类型 23.二分查找要求被查找的表是（） ①键值有序的链接表②链接表但键值不一定有序 ③键值有序的顺序表④顺序表但键值不一定有序 24.当初始序列已经按键值有序，用直接插入算法对其进行排序，需要循环的次数为（） ①n2 ②nlog2n ③log2n ④n-1 25.堆是一个键值序列{k1,k2,…, kn},对i=1,2,…,|_n/2_|,满足( ) ①ki≤k2i≤k2i+1 ②ki ③ki≤k2i且ki≤k2i+1(2i+1≤n)④ki≤k2i 或ki≤k2i+1(2i+1≤n) 26.队列的插入操作是在（）进行。 A．队首 B．队尾 C．队前 D．对后 27.一棵具有５层满二叉树中节点总数为（）。 A、３１ B、３２ C、３３ D、１６ 28.快速排序在最坏情况下的时间复杂度为（）。 A．O(log2n) B．O(nlog2n) C．0(n) D．0(n2) 29.广义表是线性表的推广，它们之间的区别在于( )。 A．能否使用子表 B．能否使用原子项 C．表的长度 D．是否能为空 30.如果某图的邻接矩阵是对角线元素均为零的上三角矩阵，则此图是( )。 A.有向完全图 B.连通图 C.强连通图 D.有向无环图 31.对n个关键字的序列进行快速排序，平均情况下的空间复杂度为( ) A.O(1) B.O(log2n) C.O(n) D.O(n log2n) 32.与线性表相比，串的插入和删除操作的特点是（） A.通常以串整体作为操作对象 B.需要更多的辅助空间 C.算法的时间复杂度较高 D.涉及移动的元素更多 33.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（）。 A.head= =NULL B.head–>next= =NULL C.head!=NULL D.head–>next= =head 34.在单链表中，指针p指向值为x的结点，能实现“删除x的后继”的语句是__________。 A. p=p->next ; B. p=p->next->next ; C. p->next=p ; D. p->next=p->next->next ; 35.一个栈的入栈序列是a，b，c，d，e，则栈的输出序列不可能是( ) A. dceab B. decba C. edcba D. abcde 36.若进栈序列为a，b，c，进栈过程中允许出栈，则以下_____是不可能得到的出栈序列。 A. a,b,c B. b,a,c C. c,a,b D. c,b,a 37.若进栈序列为１，２，３，４，进栈过程中允许出栈，则可能的出栈序列是_____。 A. ２，４，１，３ B. ３，１，４，２ C. ３，４，１，２ D. １，２，３，４ 38.设有一个栈，按A、B、C、D的顺序进栈，则可能为出栈序列的是( ) A.DCBA B.CDAB C.DBAC D.DCAB 39.一个队列的入队序列是1，2，3，4，则队列的输出序列是( ) A. 4,3,2,1 B. 1,2,3,4 C. 1,4,3,2 D. 3,2,4,1 40.一个最多能容纳m个元素的顺序存储循环队列Q，其头尾指针分别为front和rear，则判定该队列为满的条件是__________ A. (Q.rear+1)%m= =Q.front B. Q.front= =Q.rear C. Q.rear+1= =Q.front D. (Q.front+1)%m= =Q.rear 41.设数组Data[m]作为循环队列SQ的存储空间，front为队头指针，rear为队尾指针，则执行出队操作的语句为（）. A.front=front+1 B.front=(front+1)% m C.rear=(rear+1)%m D.front=(front+1)%(m+1) 42.假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为( ) A.(rear-front-1)％n B.(rear-front)％n C.(front-rear+1)％n D.(rear-front+n)％n 43.若用一个大小为6的一维数组来实现循环队列，且当前rear和front的值分别为0和3。当从队里中删除一个元素，再加入两个元素后，rear和front的值分别是（） A. 1和5 B. 5和1 C. 2和4 D. 4和2 44.两个字符串相等的条件是（） A. 串的长度相等 B. 含有相同的字符集 C. 都是非空串 D. 串的长度相等且对应的字符相同 45.如下陈述中正确的是______。 A．串是一种特殊的线性表B．串的长度必须大于零 C．串中元素只能是字母 D．空串就是空格串 46.一棵含18个结点的二叉树的高度至少为_______。 A. 3 B. 4 C. 5 D. 6 47.将一棵有40个结点的完全二叉树从上到下，从左到右依次对结点进行编号，根结点的编号为1，则编号为15的结点的左孩子的编号为_______。 A. 16 B. 30 C. 31 D.32 48.在程序的执行过程中，对实现函数的递归调用应该借助于_______结构。 A. 线性表 B. 栈 C . 队列 D. 树 49.具有100个结点的完全二叉树的深度为__________。 A.6 B. 7 C. 8 D. 9 50.已知二叉树的先序遍历序列为ABDECF，中序遍历序列为DBEAFC，则后序遍历序列为_______。 A．DEBAFC B．DEFBCA C． DEBCFA D．DEBFCA 51.如果在数据结构中每个数据元素只可能有一个直接前驱，但可以有多个直接后继，则该结构是( ) A. 栈 B. 队列 C. 树 D. 图 52.已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为（） A. 0 B. 1 C. 48 D. 49 53.具有100个结点的完全二叉树，其中含有__________个度为1的结点。 A.1 B. 0 C. 2 D. 不确定 54.已知二叉树的先序遍历序列为ABCD，中序遍历序列为BCDA，则后序遍历序列为_______。 A．ABCD B．BCDA C．CDBA D．DCBA 55.对一棵有100个结点的完全二叉树按层序编号，则编号为49的结点，它的左孩子的编号为（） A.99 B.98 C.97 D.50 56.有m个叶子结点的哈夫曼树，其结点总数是（） A.2m-1 B.2m C.2m+1 D.2(m+1) 57.无向图的邻接矩阵是一个_______。 A.对称矩阵 B.零矩阵 C.上三角矩阵 D.对角矩阵 58.广义表中元素分为( ) A．原子元素 B．表元素 C．原子元素和表元素 D．任意元素 59.广义表A=(( )，(a)，(b，(c，d)))的长度为( ) . A．2 B．3 C．4 D．5 60.广义表A：(( )，(a)，(b，(c，d)))的深度为( ) . A．2 B．3 C．4 D．5 61.若用邻接矩阵表示一个有向图，则其中每一列包含的″1″的个数为（） A．图中每个顶点的入度B．图中每个顶点的出度 C．图中弧的条数 D．图中连通分量的数目 62.邻接矩阵为对称矩阵的图是( ) A. 有向图 B. 带权有向图 C. 有向图或无向图 D. 无向图 63.在一个具有n个顶点的无向图中，要连通全部顶点至少需要的边数为( ) A. n/2 B. n C. n-1 D. n+1 64.下面的序列中________是大根堆。 A.1,2,8,5,3,9,10,4 B.1,5,10,6,7,8,9,2 C.9,8,7,6,4,8,2,1 D.9,8,7,6,5,4,3,1 65.一组记录的关键码为(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 66.对关键字序列（5，1，4，3，7，2，8，6）进行快速排序时，以第一个元素5为基准的一次划分的结果为（） A．（1，2，3，4，5，6，7，8）B．（1，4，3，2，5，7，8，6） C．（2，1，4，3，5，7，8，6）D．（8，7，6，5，4，3，2，1） 67.使用折半查找，线性表必须_______。 Ａ.以顺序方式存储Ｂ.以顺序方式存储，且元素已按值排好序 Ｃ.以链式方式存储Ｄ.以链式方式存储，且元素已按值排好序 68.已知8个元素（34，76，45，18，26，54，92，65），按照依次插入结点的方法生成一棵二叉排序树，则该树的深度为（） A.4 B.5 C.6 D.7 69.若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在折半查找关键字b的过程中，先后进行比较的关键字依次为（） A．f,c,b B．f,d,b C．g,c,b D．g,d,b 70.在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于( ) A.静态查找表 B.动态查找表 C.静态查找表与动态查找表 D.静态查找表或动态查找表 71.有一个有序表为：(2,5,8,11,15,16,22,24,27,35,50)当折半查找值为24的结点时，经过_____次比较后查找成功。 A. 1 B. 2 C. 3 D. 4 72.有一个有序表为：(21,32,41,45,62,75,77,82,95),当折半查找值为82的结点时，经过_____次比较后查找成功。 A. 1 B. 2 C. 4 D. 3 73.下面排序算法的时间复杂度最小的是_______。 A．直接插入排序B．简单选择排序 C．冒泡排序D．快速排序 74.以下排序方法中，稳定的排序方法是__________。 A. 直接插入排序和冒泡排序 B. 简单选择排序和归并排序 C. 冒泡排序和快速排序 D. 堆排序和基数排序 75.按排序过程中依据的原则分类，快速排序属于( ) A.插入类的排序方法 B.选择类的排序方法 C.交换类的排序方法 D.归并类的排序方法 76.在一棵二叉排序树中，若左子树不空，左子树上所有结点的值均（）根结点的值。 A．大于 B．小于 C．不小于 D．大于等于 75.用邻接表表示图进行深度优先遍历时，通常是采用（）来实现算法的。 A．栈 B. 队列 C. 树 D. 图 76. 用邻接表表示图进行广度优先遍历时，通常是采用（）来实现算法的。 A．栈 B. 队列 C. 树 D. 图 77.从一个顺序队列删除元素时，首先要（）。 A．前移一位队首指针 B.后移一位队首指针 C.取出队首指针所指位置上的元素 D.取出队尾指针所指位置上的元素 78.在一个具有n个顶点的无向图中，要连通所有顶点则至少需要（）条边。 A．n B．2n C．n-1 D．n+1 79.在有向图的邻接表存储表示中，顶点V在链表结点中出现的次数是（）。 A.顶点V的入度 B.顶点V的出度 C.顶点V的度 D.依附于顶点V的边的数目 80.由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。 A．74 B．23 C．51 D．53 81.设串sl=″Data Structures with ″，s2=″it″，则子串定位函数index的值为（）。 A．15 B．16 C．17 D．18 82.一棵深度为6的二叉树至多有（）个结点。 A．64 B．32 C．31 D．63 83. 将含100个结点的完全二叉树从根这一层开始，每层上从左到右依次对结点编号，根结点的编号 为1，编号为49的结点X的双亲编号为（）。 A．24B．25 C．23 D．无法确定 84. 树的后根遍历与其转换的相应二叉树的（）遍历的结果序列相同。 A.先序 B.中序 C.后序 D.层次遍历 85.链表适用于（）查找 A．顺序 B．二分法 C．顺序，也能二分法 D．随机 86. 折半查找有序表{6,15,30,37,65,70,72,89,99},若要查找元素37，需要依次与表中元素 __________进行比较。 A. 65，15，37 B. 68，30，37 C. 65，15，30 D. 65，15，30，37 87．下列排序方法中，稳定的排序方法为（）。 A.希尔排序 B.堆排序 C.快速排序 D.直接插入排序 88．当利用大小为N 的数组顺序存储一个栈时，假定用top = = N表示栈空，则退栈时，用（）语句修改top指针。 A．top++; B．top=0; C．top--; D．top=N; 89．在顺序表中，只要知道_______，就可在相同时间内求出任一结点的存储地址。 A．基地址B．结点大小 C．向量大小D．基地址和结点大小 90．在一棵二叉树中，第4层上的结点数最多为（）。 A．31 B．8 C．15 D．16 91．线性表的顺序存储结构是一种_______的存储结构。 A．随机存取 B．顺序存取C．索引存取D．散列存取 92.数据结构在计算机内存储器中的表示是指（） A.数据结构 B.数据元素之间的关系 C.数据的逻辑结构 D.数据的物理存储结构 93.下述几种排序方法中，要求内存最大的是（） Ａ. 插入排序Ｂ.快速排序Ｃ. 归并排序Ｄ. 选择排序 94.若长度为n的线性表采用顺序存储结构，则在表中第i个位置（1<=i<=n+1）插入一个新元素的算 法的时间复杂度为（） A.O(0) B.O(1) C.O(n) D.O(n2) 95.一个栈的输入序列为ABCDE，则不可能出现的输出序列是（） A.ABCDE B.EDCBA C.CABED D.BADCE 96.对序列（22，86，19，49，12，30，65，35，18）进行一趟排序后得到的结果如下：（18，12， 19，22，49，30，65，35，86），则可以认为使用的排序方法是（） A．选择排序B．冒泡排序C．快速排序D．插入排序 97.对二叉树的结点从1开始编号，要求每个结点的编号大于其左孩子（如果有的话）的编号，而小 于其右(孩子如果有的话）的编号，则可以采用（）次序的遍历实现二叉树的结点编号 A.先序 B.中序 C.后序 D.层次遍历 98. ________是一棵满二叉树。 A．二叉排序树 B．深度为5有31个结点的二叉树 C．有15个结点的完全二叉树D．哈夫曼（Huffman）树 99.某二叉树结点的中序序列为BDAECF,后序序列为DBEFCA,则该二叉树对应的森林包括（）棵 树 A.1 B.2 C.3 D.4 100. 下面关于图的存储的叙述中正确的是（） A.用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 B.用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 C.用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 D.用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 三、判断题：（对的打 ，错的打 ） （ ） 1.数据元素是数据处理的最小单位。 （ ） 2.数据项是数据处理的最小单位。 （ ） 3.线性表的顺序存储结构优于链式存储结构。 （ ） 4.顺序存储的线性表可以随机访问,链式存储的线性表只能顺序访问。 （ ） 5.在线性表的顺序存储结构中,逻辑上相邻的两个元素在物理位置上不一定相邻。 （ ） 6.线性表的顺序存储和链式存储都必须占用内存中的连续存储单元。 （ ） 7.栈和队列的存储方式,既可以顺序存储也可以链式存储。 （ ） 8.栈和队列都是操作受限制的线性表。 （ ） 9.栈的特点是先进后出,队列的特点是先进先出。 （ ） 10.空串是任意串的子串。 （ ） 11.串中任意个字符组成的子序列称为该串的子串。 （ ） 12.树型结构中每个结点都有一个直接前趋。 （ ） 13.二叉树中每个结点的度最大为2,因此二叉树是一种特殊的树。 （ ） 14.满二叉树中存在度为1的结点。 （ ） 15.完全二叉树中每个结点或者没有孩子或者有2个孩子。 （ ） 16.在任意一棵二叉树中,叶子结点的个数等于度为2结点的个数加1。 （ ） 17.由树转化为二叉树,其根结点的右子树总是空的。 （ ） 18.最小生成树是指边数最少的生成树。 （ ） 19. 一棵哈夫曼树有m 个叶子结点,则其结点总数为2m-1。 （ ） 20.树的先根遍历序列等同于该树对应的二叉树中序遍历序列。 （ ） 21. “顺序查找法”是指在顺序表上进行查找的方法。 （ ） 22.快速排序在任何情况下圴可得到最块的排序效果。 （ ） 23.在有向图中每个顶点的度等于各顶点的入度与出度之和。 （ ） 24.二叉排序树是用来进行排序的。 （ ） 25.衡量排序算法的两个主要性能指标是执行排序算法所需要的时间和执行排序算法所需要的附加空间。 （ ） 26.哈夫曼树是带权值的树,且权值较大的结点离树较近。 1．双链表中至多只有一个结点的后继指针为空。（ ） 2．在循环队列中，front指向队列中第一个元素的前一位置，rear指向实际的队尾元素，队列为满的条件是front=rear。（ ） 3．对链表进行插入和删除操作时，不必移动结点。（ ） 4．栈可以作为实现程序设计语言过程调用时的一种数据结构。（ ） 5．线性表的逻辑顺序与物理顺序总是一致的。（ ） 6．对有向图G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，则该图一定是完全图。( ) 7．边数很多的稠密图，适宜用邻接矩阵表示。（ ） 8．向二叉排序树插入一个新结点时，新结点一定成为二叉排序树的一个叶子结点。（ ） 9．键值序列{A，C，D，E，F，E，F}是一个堆。（ ） 10．二路归并时，被归并的两个子序列中的关键字个数一定要相等。（ ） 11. 非空线性表中任意一个数据元素都有且仅有一个直接前驱元素。( ) 12. 每种数据结构都应具备三种基本运算：插入、删除和搜索。（ ） 13. 当从一个最小堆中删除一个元素时，需要把堆尾元素填补到堆顶位置，然后再按条件把它逐层向下调整，直到调整到合适位置为止。( ) 14. 空串与由空格组成的串没有区别。( ) 15. 单链表可以实现随机存取。( ) 16. 深度为h的非空二叉树的第i层最多有2h-1 个结点。( ) 17. 完全二叉树就是满二叉树。( ) 18. 已知一棵二叉树的前序序列和中序序列可以唯一地构造出该二叉树。( ) 19. 非空二叉排序树的任意一棵子树也是二叉排序树。( ) 20. 有向图是一种非线性结构。( ) 21. 图的广度优先搜索算法通常采用递归算法求解。（ ） 22. 线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。（ ） 23. 折半查找方法适用于按值有序的线性链表的查找。( ) 24. 图的深度优先搜索是一种典型的回溯搜索的例子，可以通过递归算法求解。( ) 25. 选择排序过程中元素之间的比较次数与原始序列的状态无关。( ) 26．栈是一种线性结构。（ ） 27．顺序表中所有结点的类型必须相同。（ ） 28．对于一棵具有n个结点，其高度为h的二叉树，进行任一种次序遍历的时间复杂度为O(n)。( ) 29．递归定义的数据结构通常不需要用递归的算法来实现对它的操作。（ ） 30．用Ch1，Ch2表示两个字符，若Ord(Ch1)＜Ord(Ch2)，则称Ch1＜Ch2。（ ） 四、应用题： 1. 已知二叉树的先序序列和中序序列分别为ABCDEFG 和CBEDAFG ，要求： （1）画出该二叉树；（2）写出该二叉树的后序遍历序列。 2.已知一棵二叉树的中根遍历序列和后根遍历序列分别为BDCEAFHG 和DECBHGFA ，要求： （1）画出该二叉树；（2）写出该二叉树的先序遍历序列。 3.将下面的树转换为二叉树，写出转换后二叉树的先序、中序、后序的遍历序列。 4.若以（4，5，6，7，8）作为叶子结点的权值，要求：(1)试构造相应的哈夫曼树； (2)计算该哈夫曼树的带权路径长度；(3)写出各结点对应的哈夫曼编码。 5．以数据集{4，5，6，7，10，12，18}为结点权值，试构成哈夫曼树，并计算其带权路径长度为。 6. 有七个带权结点，其权值分别为3,7,8,2,6,10,14，要求：(1)试以它们为叶子结点构造一棵哈夫曼树；(2)计算该哈夫曼树的带权路径长度；(3)写出各叶子结点对应的哈夫曼编码。 7. 设一个无向图为G=(V,E),其中V={v1,v2,v3,v4，v5,v6,v7,v8}， E={(v1,v2),(v1,v3),(v2,v4),(v2,v5),(v4,v8),(v5,v8),(v3,v6),(v3,v7),(v6,v7)}, (1)画出该无向图; (2)画出其邻接表; (3) 根椐邻接表,写出从顶点v1出发进行深度优先和广度优先搜索得到的顶点序列。 8.设一个无向图为G=(V,E),其中V={v1,v2,v3,v4，v5,v6 }， E={(v1,v2),(v1,v3),(v2,v4),(v2,v5), (v3,v6),(v4,v5),(v5,v6) }, (1)画出该无向图; (2)画出其邻接矩阵， (3)根椐邻接矩阵,写出从顶点v1出发进行深度优先和广度优先搜索得到的顶点序列。 9. 对如下无向图，要求： R A B C E F G H I D （1）写出该图中每个顶点的度;（2）画出该图的邻接表； （3）根椐邻接表，分别写出从顶点A 出发进行深度优先和广度优先搜索得到的顶点序列。 题9图题12图 10.已知无向图如上中图所示，要求：（1）试给出该图的邻接矩阵；（2）根据邻接矩阵，分别写出从顶点A 出发的深度优先和广度优先遍历序列。 11.已知有向图的邻接表如下左图所示,试写出从顶点A 出发,对该图进行深度优先搜索和广度优先搜索得到的顶点序列。 12.对于如上右图所示的有向图，试给出：（1）邻接矩阵；（2）邻接表。 13.对如下图所示的无向图，试给出：（1）邻接矩阵；（2）根据邻接矩阵，分别写出从顶点A 出发的深度优先和广度优先遍历序列。 14．从空树起，依次插入关键字（8，12，5，7，9，1，13，10），构造一棵二叉排序树。 A C D E B （1）画出该二叉排序树； （2）画出从（1）所得树中插入关键字为6的结点之后的二叉排序树。 （3）画出从（2）所得树中删除关键字为12的结点之后的二叉排序树。 15.按序列（46，88，45，39，70，58，97，23）的输入顺序建立一颗二叉排序树. （1）画出该二叉排序树； （2）在（1）的基础上插入结点42后，画出对应的二叉排序树; (3) 在（2）的基础上删除结点88后，画出对应的二叉排序树。 16．从空树起，依次插入关键字37，50，42，18，48，12，56，30，23，构造一棵二叉排序树。（1）画出该二叉排序树； （2）画出从（1）所得树中删除关键字为50的结点之后的二叉排序树。 17. 从空树起，依次插入关键字（28，16，20，39，65，32，10），构造一棵二叉排序树。 （1）画出该二叉排序树； （2）画出从（1）所得树中插入关键字为88的结点之后的二叉排序树。 18.用直接插入排序算法对数据序列（47，33，61，82，72，11，25，57）进行升序排序，试写出每一趟的排序结果。 19. 写出利用简单选择排序方法对一组关键码为（54，38，96，23，15，72，60）的记录进行升序排序时，每趟排序的结果。 20．已知关键码序列{25，23，16，68，94，72，71，73}，如果采用堆排序，它是否为堆？如果不是堆，请把其调整为堆。 21.已知一组数值序列为(50，47，65，33，41，26，71，56)，请完成下面的各项操作： (1)采用直接插入排序法对该组序列作升序排序，并给出每一趟的排序结果。 (2)采用冒泡排序法对该组序列作升序排序，并给出每一趟的排序结果。 (3)采用快速排序法对该组序列作升序排序，并给出每一趟的排序结果。 (4)画出与该序列对应的完全二叉树；判断该序列是否为堆，如果不是，请调整为大根堆。 四、算法填空 1. 以下是在顺序表中第i个位置上插入一个值为x的新元素的算法。 顺序表的类型描述： #define MAXSIZE 20 typedef struct { int data[MAXSIZE]; int last ; }SeqList; 算法: int Insert_Seqlist(SqList *L,int i,int x) { int j; if ( L->last==MAXSIZE-1) { printf(“表满”); return (-1); } if ( i<1||i>L->last+2) { printf(“位置错”); return (0); } for (j= L->last ；j>=i-1；j--){ __ L->data[j+1]= L->data[j]____; L->data[i-1]=x; ___ L->last++____; return (1); } 2. 以下算法是在顺序栈中实现元素入栈的功能。 顺序表的类型描述： #define MAXSIZE 100 typedef struct { int data[MAXSIZE]; int top ; }SeqStack; 算法: int Push_SeqStack (SqList *s,int x) { if ( s->top== MAXSIZE -1) return (0); else { __s->top++_________; __s->data[s->top]=x_____; return (1); } } 3．以下是先序遍历二叉树的递归算法。 二叉树的二叉链表的类型定义为： typedef struct Node { char data; struct Node *lchild,*rchild; } BiTreeNode, *BiTree; 算法: void PreOrder (BiTree bt) { if ( bt==NULL ) return ; Visit(bt->data) ; PreOrder (____bt->lchild______); PreOrder (____bt->rchild______); } 4．已知二叉树中的结点类型BinTreeNode定义为： Struct BinTreeNode{ ElemType data； BinTreeNode *left，*right }； 其中data为结点值域，left和right分别为指向左、右子女结点的指针域。 下面函数的功能是返回二叉树BT中值为x的结点所在的层号，请在划有横线的地方填写合适内容。 Int NodeLevel(BinTreeNode * BT，ElemType X) { if(BT＝NULL) return 0；／／空树的层号为0 else if(BT一>data＝＝X) return 1; ／／根结点的层号为1 ／／向子树中查找x结点 else{ int cl＝NodeLevel(BT->left，X)； if(cl>＝1)return cl+1; int c2＝_ NodeLevel(BT-> right，X)__； if__(cl==0)|| (c2==0)_； ／／若树中不存在X结点则返回0 else return 0； } } 5. 以下是求二叉树的深度的递归算法。 二叉树的二叉链表的类型定义为： typedef struct Node { char data; struct Node *lchild,*rchild; 一、填空。 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. 数据的逻辑结构 B. 数据的存储结构 C. 数据的逻辑结构和存储结构 D. 数据的逻辑结构、存储结构及其基本操作 2、算法分析的两个主要方面是( A )。 A. 空间复杂度和时间复杂度 B. 正确性和简单性C. 可读性和文档性 D. 数据复杂性和程序复杂性 3、具有线性结构的数据结构是( D )。 A. 图 B. 树 C. 广义表 D. 栈 4、计算机中的算法指的是解决某一个问题的有限运算序列,它必须具备输入、输出、( B )等5个特性。 A. 可执行性、可移植性和可扩充性 B. 可执行性、有穷性和确定性 C. 确定性、有穷性和稳定性 D. 易读性、稳定性和确定性 5、下面程序段的时间复杂度是( C )。 fori0;im;i++ forj0;jn;j++ a[i][j]i*j; A. Om2 B. On2 C. Om*n D. Om+n 6、算法是( D )。 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 7、某算法的语句执行频度为(3n+nlog2n+n2+8),其时间复杂度表示( C )。 A. On B. Onlog2n C. On2 D. Olog2n 8、下面程序段的时间复杂度为( C )。 i1; whilein ii*3; A. On B. O3n C. Olog3n D. On3 9、数据结构是一门研究非数值计算的程序设计问题中计算机的数据元素以及它们之间的( B )和运算等的学科。 A. 结构 B. 关系 C. 运算 D. 算法 10、下面程序段的时间复杂度是( A )。 is0; whilesn i++;s+i; A. On B. On2 C. Olog2n D. On3 11、抽象数据类型的三个组成部分分别为( A )。 A. 数据对象、数据关系和基本操作 B. 数据元素、逻辑结构和存储结构 C. 数据项、数据元素和数据类型 D. 数据元素、数据结构和数据类型 12、通常从正确性、易读性、健壮性、高效性等4个方面评价算法的质量,以下解释错误的是(D)。 数据结构试题及答案 一、单项选择题 (1)一个算法应该就是（)。 A)程序???B）问题求解步骤得描述 C）要满足五个基本属性??D) A与C (2)算法指得就是（)。 A）计算机程序???B）解决问题得计算方法 C)排序算法???D）解决问题得有限运算序列。 (3)与数据元素本身得形式、内容、相对位置、个数无关得就是数据得(）。 A) 存储结构B) 逻辑结构C）算法D)操作 (4)从逻辑上可以把数据结构分为( ）两大类。 A）动态结构、静态结构??B) 顺序结构、链式结构 C）线性结构、非线性结构???D）初等结构、构造型结构 (5)下列叙述中正确得就是(）。 A)一个逻辑数据结构只能有一种存储结构 B）数据得逻辑结构属于线性结构,存储结构属于非线性结构 C）一个逻辑数据结构可以有多种存储结构,且各种存储结构不影响数据处理得效率 D）一个逻辑数据结构可以有多种存储结构,且各种存储结构影响数据处理得效率 (6)数据得基本单位就是（） ?A) 数据项??B) 数据类型C)数据元素??D)数据变量 (7)下列程序得时间复杂度为（) i=０；s＝０; wｈｉlｅ(s 一．是非题 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. 快速排序在最坏情况下的时间复杂度为（ 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．线性表的顺序存储结构是一种 的存储结构，线性表的链式存储结构是一种 的存储结构。 a. 随机存储； b.顺序存储； c. 索引存取； d. HASH 存取 2．一个栈的入栈序列是a,b,c,d,e ，则栈的不可能的输出序列是 。 a. edcba; b. decba; c. dceab; d.abcde 3．一个队列的入队序列是1，2，3，4，则队列的输出序列是 。 a. 4,3,2,1; b. 1,2,3,4; c. 1,4,3,2; d.3,2,4,1 4．在一个单链表中，已知p 结点是q 结点的直接前驱结点，若在p 和q 之间插入结点s ，则执行的操作是 。 a. s->nxet=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; 5．设有两个串p,q ，求q 在p 中首次出现的位置的运算称作 。 a.联接 b.模式匹配 c.求子串 d.求串长 6．二维数组M 的成员是6个字符（每个字符占一个存储单元）组成的串，行下标i 的范围从0到8，列下标j 的范围从1到10，则存放M 至少需要 个字节。 a. 90 b.180 c.240 d.540 7．在线索二叉树中，结点p 没有左子树的充要条件是 。 a. p->lch==NULL b. p->ltag==1 c. p->ltag==1且p->lch=NULL d. 以上都不对 8．在栈操作中，输入序列为（A ，B ，C ，D ），不可能得到的输出序列为：______ A 、（A ， B ， C ， D ） B 、（D ，C ，B ，A ） C 、（A ，C ，D ，B ） D 、（C ，A ，B ，D ） 9．已知某二叉树的后序序列是dabec ，中序序列是debac ，则它的先序序列是 。 A 、acbed B 、decab C 、deabc D 、cedba 10．设矩阵A 是一个对称矩阵，为了节省存储空间，将其下三角部分（见下图）按行序存放在一维数组B[1..n(n-1)/2]中，对任一上三角部分元素)(j i a ij ，在一维数组B 的存放位置是 。 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) 1.以下与数据的存储结构无关的术语是（ c ） C、哈希表 2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（ B ） B、108 3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（ C ） C、head–>next= =head 4.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（ D ） D、2，3，5，1，6，4 5.下列关键字序列中，构成小根堆的是（ A ） A、{12，21，49，33，81，56，69，41} 6.下列数据结构中，不属于二叉树的是（ A ） A、B树 7.用顺序存储的方法来存储一棵二叉树，存放在一维数组A[1..N]中，若结点A[i]有右孩子，则其右孩子是（ C ）。 C、A[2i+1] 8.设树T的高度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，则T中叶子数为（ D ） D、 8 9.有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应选择下 面哪个序列输入（ B ） B、37，24，12，30，53，45，96 10.对下面有向图给出了四种可能的拓扑序列，其中错误的是（ C ） C、5，1，6，3，4，2 11.m阶B-树中所有非终端（除根之外）结点中的关键字个数必须大于或等于( B ) B、[m/2]-1 12.散列文件也称为( C ) B 、索引文件 13.数据结构是（ D ） D、相互之间存在一种或多种特定关系的数据元素的集合 14.从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（ C ） C、线性结构和树型结构 15.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，则同样表示 单选题(每题2分，共20分) 1. 1. 对一个算法的评价，不包括如下(B )方面的内容。 A .健壮性和可读性 B .并行性 C .正确性 D .时空复杂度 2.2. 在带有头结点的单链表HL 中，要向表头插入一个由指针 p 指向 的结点，则执行(A )。 A. p->next=HL->next; HL->next=p; B. p->next=HL; HL=p; 都具有相同的(A )。 A.行号 B .列号 C .元素值 D .非零元素个数 9. 快速排序在最坏情况下的时间复杂度为(D )。 A. O(log 2n) B . O(nlog 2n) C . 0(n) D 10.10. 从二叉搜索树中查找一个元素时，其时间复杂度大致 为 A. O(n) B. O(1) C. O(log 2 n) D. O(n 二、 运算题(每题6分，共24分) 1. 1. 数据结构是指数据及其相互之间的 _________________ 。当结点之 间存在M 对N (M N)的联系时，称这种结构为 __________________________ 。 2. 2. 队列的插入操作是在队列的_ _尾 ________ 行，删除操作是在队 列的 ____ 首 _____ 行。 3. 3. 当用长度为N 的数组顺序存储一个栈时，假定用top==N 表示栈 C. p->next=HL; p=HL; 3. 3. A. C. D. HL=p; p-> next=HL; 对线性表，在下列哪种情况下应当采用链表表示? 经常需要随机地存取元素 B. 表中元素需要占据一片连续的存储空间 一个栈的输入序列为1 2 3， 4. 4. 列的是(C ) A. 2 3 1 C. 3 1 2 AOV 网 是一种(D ) 有向 图 B .无向图 (B ) 经常需要进行插入和删除操作 D.表中元素的个数不变 则下列序列中不可能是栈的输出序 B. 3 2 1 5. 5. 6. .无向无环图 D .有向无环图 采用 开放定址法处理散列表的冲突时，其平均查找长度( B. 高于链接法处理冲突 D .高于二分查找 7. 8. 6. A.低于链接法处理冲突 .与链接法处理冲突相同 7. 参数。 A.值 8. B)。 若需要利用形参直接访问实参时，应将形参变量说明为( B .函数 C .指针 D .引用 在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点 9. .0(n 2) (C )。 2 ) 数据结构期中练习 学号姓名 一、选择题 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章绪论 一、判断题 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．无直接后继结点． 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 某算法的时间复杂度是O(n 2 ) ，表明该算法（）。 A 问题规模是n2 B 问题规模与n2成正比 C 执行时间等于n2 D 执行时间与n2成正比 2、关于数据结构的描述，不正确的是（）。 A数据结构相同，对应的存储结构也相同。 B数据结构涉及数据的逻辑结构、存储结构和施加其上的操作等三个方面。 C数据结构操作的实现与存储结构有关。 D定义逻辑结构时可不考虑存储结构。 3、按排序策略分来，起泡排序属于（）。 A插入排序B选择排序C交换排序D归并排序 4、利用双向链表作线性表的存储结构的优点是（）。 A便于进行插入和删除的操作 B 提高按关系查找数据元素的速度 C节省空间D便于销毁结构释放空间 5、一个队列的进队顺序为1,2,3,4，则该队列可能的输出序列是（）。 A 1,2,3,4 B 1,3,2,4 C 1,4,2,3 D 4,3,2,1 6、 Dijkstra算法是按（）方法求出图中从某顶点到其余顶点最短路径的。 A按长度递减的顺序求出图的某顶点到其余顶点的最短路径 B按长度递增的顺序求出图的某顶点到其余顶点的最短路径 C通过深度优先遍历求出图中从某顶点到其余顶点的所有路径 D通过广度优先遍历求出图的某顶点到其余顶点的最短路径 7、字符串可定义为n（ n≥ 0）个字符的有限（）。其中，n是字符串的长度，表明字符串中字符的个数。 A集合B数列C序列D聚合 8、在二维数组A[9][10]中，每个数组元素占用 3 个存储单元，从首地址SA 开始按行连续存放。在这种情况下，元素A[8][5]的起始地址为（）。 A SA+141 B SA+144 C SA+222 D SA+255 9、已知广义表为L(A(u,v,(x,y),z),C(m,(),(k,l,n),(())),((())),(e,(f,g),h))，则它的长度是（）。 A2B3C4D5 10.对于具有n(n>1)个顶点的强连通图，其有向边条数至少有_____。 A. n+1 B. n C. n-1 D. n-2 11.一个递归算法必须包括 __________ 。 A. 递归部分 B . 结束条件和递归部分 C. 迭代部分 D. 结束条件和迭代部分 12.从逻辑上看可以把数据结构分为__________两大类。 A．动态结构、静态结构B．顺序结构、链式结构 C．线性结构、非线性结构D．初等结构、构造型结构 13、若在长度为n 的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。 A O(n) B O(1) C O(n 2) D O(log 2n) 14.采用顺序搜素方式搜索长度为 n 的线性表时，在等概率情况下，搜索成功时的平均搜索 长度为 __________。 A. n B. n/2 C . (n+1)/2 D. (n-1)/2 15、非空的循环单链表first的链尾结点（由p 所指向）满足（）。 A p->link==NULL; B P==NULL; 第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 数据结构复习题答案 一、选择题 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 第二章线性表一．名词解释 线性结构 2.数据结构的顺序实现 3.顺序表 4.链表二、填空题 1.为了便于讨论，有时将含n(n>=0)个结点的线性结构表示成(a 1，a 2 ,……a n )，其中每 个a i 代表一个______。a 1 称为______结点，a n 称为______结点，i称为a i 在线性表中的________ 或______。对任意一对相邻结点a i 、a i┼1 (1<=i 一、选择题 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、以下数据结构中，（）是非线性数据结构。数据结构复习题答案 2
数据结构与算法复习题库含答案
数据结构试题库答案
数据结构复习题附答案
数据结构复习题(附答案)
《数据结构》题库及答案
必看!!!!!数据结构期末复习题及部分答案解析
数据结构期末复习题答案
数据结构试题及答案(10套最新)
数据结构习题及答案 (9)
数据结构练习试题和答案解析
2015年数据结构期末考试题及答案
算法与数据结构题库与答案
数据结构基本复习题答案
数据结构复习题答案
数据结构各章复习题与答案
数据结构复习题及答案