下载文档原格式
![数据结构练习题2[1]](https://img.taocdn.com/s1/m/113b2381d4d8d15abe234e3e.png)
1、3个结点可构成棵不同形态的树。
2、利用直接选择排序算法对n个记录进行排序，最坏的情况下，记录交换的次数为。
3、一个图的_______表示法是唯一的，而______表示法是不唯一的。
4、一棵深度为h的满二叉树上的结点总数为，一棵深度为h的完全二叉树上的结点总数的最小值为，最大值为。
5、在一棵完全二叉树中有n个结点，对这些结点按层序编号，若一个结点编号为69，则其双亲编号为，有左孩子的条件是，其左孩子编号为。
6、二维数组M的成员是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10，则存放M至少需要________个字节；M的第8列和第5行共占___________个字节；若M按行优先方式存储，元素M[8][5]的起始地址与当M按列优先方式存储时的________元素的起始地址一致。
7、设有一顺序栈S，元素s1,s2,s3,s4,s5,s6依次进栈，如果6个元素出栈的顺序是s2,s3,s4,s6,s5,s1,则栈的容量至少应该是________。
8、在线性表的顺序存储中，元素之间的逻辑关系是通过决定的；在线性表的链式存储中，元素之间的逻辑关系是通过_________决定的。
9、n个顶点的连通图的生成树有n-1条边。
10、通常数组只有______给定一组有定义的下标，存取相应的数据__和___给定一组有定义的下标，修改相应数据元素的值_____两种运算，因此常采用__顺序_______来存储数组。
11、3个节点可以构成 5 棵不同形态的二叉树。
12、对于一棵具有n个结点的二叉树，当它为一棵完全二叉树时具有最小高度，即为∟log2n」+1，当它为一棵单支树时具有最大高度，即为n 。
13、在一棵有n个结点的完全二叉树中，对这些结点按层序编号，若一个结点编号为59，则其双亲编号为，若一个结点编号为23，则其有右孩子的条件是。
14、数组M中每个元素的长度是3个字节，行下标i从1到8，列下标j从1到10，从首地址EA开始连续存放在存储器中。
第七章图一、选择题1．图中有关路径的定义是（）。
A．由顶点和相邻顶点序偶构成的边所形成的序列B．由不同顶点所形成的序列C．由不同边所形成的序列D．上述定义都不是2．设无向图的顶点个数为n，则该图最多有（）条边。
A．n-1 B．n(n-1)/2 C．n(n+1)/2 D．0 E．n23．一个n个顶点的连通无向图，其边的个数至少为（）。
A．n-1 B．n C．n+1 D．nlogn；4．要连通具有n个顶点的有向图，至少需要（）条边。
A．n-l B．n C．n+l D．2n5．一个有n个结点的图，最少有（B ）个连通分量，最多有（D ）个连通分量。
A．0 B．1 C．n-1 D．n6. 下列说法不正确的是（）。
A．图的遍历是从给定的源点出发每一个顶点仅被访问一次C．图的深度遍历不适用于有向图B．遍历的基本算法有两种：深度遍历和广度遍历D．图的深度遍历是一个递归过程7．无向图G=(V,E),其中：V={a,b,c,d,e,f},E={(a,b),(a,e),(a,c),(b,e),(c,f),(f,d),(e,d)}，对该图进行深度优先遍历，得到的顶点序列正确的是（）。
A．a,b,e,c,d,f B．a,c,f,e,b,d C．a,e,b,c,f,d D．a,e,d,f,c,b8. 在图采用邻接表存储时，求最小生成树的Prim 算法的时间复杂度为( )。
A. O(n)B. O(n+e)C. O(n2)D. O(n3)9. 求解最短路径的Floyd算法的时间复杂度为( )。
A．O（n） B. O（n+c） C. O（n*n）D. O（n*n*n）10．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={<V1,V2>,<V1,V3>,<V1,V4>,<V2,V5>,<V3,V5>,<V3,V6>,<V4,V6>,<V5,V7>,<V6,V7>},G的拓扑序列是（）。
第二章线性表一、选择题1.一个线性表第一个元素的存储地址是100,每个元素的长度为2,则第5个元素的地址是( )（A）110 （B）108（C）100 （D）120参考答案：B2. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（）个元素。
（A）64（B）63 （C）63.5 （D）7参考答案：C3.线性表采用链式存储结构时，其地址（）。
(A) 必须是连续的 (B) 部分地址必须是连续的(C) 一定是不连续的 (D) 连续与否均可以参考答案：D4. 在一个单链表中，若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;参考答案：B5.在一个单链表中，若删除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;参考答案：A6.下列有关线性表的叙述中，正确的是（）（A）线性表中的元素之间隔是线性关系（B）线性表中至少有一个元素（C）线性表中任何一个元素有且仅有一个直接前趋（D）线性表中任何一个元素有且仅有一个直接后继参考答案：A7.线性表是具有n个（）的有限序列（n≠0)（A）表元素（B）字符（C）数据元素（D）数据项参考答案：C二、判断题1.线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。
（）2.如果没有提供指针类型的语言，就无法构造链式结构。
（）3.线性结构的特点是只有一个结点没有前驱，只有一个结点没有后继，其余的结点只有一个前驱和后继。
一．判断题（下列各题，正确的请在前面的括号内打√；错误的打×）第1章（√）（1）数据的逻辑结构与数据元素本身的内容和形式无关。
（√）（2）一个数据结构是由一个逻辑结构和这个逻辑结构上的一个基本运算集构成的整体。
（×）（3）数据元素是数据的最小单位。
（×）（4）数据项是数据的基本单位。
（×）（5）数据的逻辑结构和数据的存储结构是相同的。
（√）（6）数据的逻辑结构是各数据元素之间的逻辑关系，是用户按使用需要而建立的。
（√）（7）数据的物理结构是指数据在计算机内实际的存储形式。
（√）（8）从逻辑关系上讲，数据结构主要分为线性结构和非线性结构两类。
（√）（9）数据的存储结构是数据的逻辑结构的存储映像。
（√）（10）算法是对解题方法和步骤的描述。
第2章（×）（1）链表的物理存储结构具有同链表一样的顺序。
（×）（2）链表的每个结点都恰好包含一个指针域。
（√）（3）线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。
（×）（4）链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。
（×）（5）顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。
（√）（6）数组元素的存储位置是下标的线性函数。
（√）（7）在单链表中，元素的存储位置用指针联系，所以可以从头结点开始查找任何一个元素。
（×）（8）顺序存储线性表的插入和删除操作不需要付出很大的代价，因为平均每次移动仅一半的元素。
（×）（9）顺序存储方式的优点是存储密度大，插入、删除效率高。
（×）（10）在单链表中，要取得某个元素，只要知道该元素的指针即可，因此单链表是随机存取的存储结构。
第3章（√）（1）大多数排序算法都有比较关键字大小和改变指向记录的指针或移动记录本身两种基本操作。
第六章图1、填空题一个有 n 个结点的无向图中,所有顶点的度数之和等于所有边数之和的 _2__倍。
一个有 n 个结点的强连通图,最多有 _n(n-1_/2__条边,最少有 ___n-1_ 条边。
在一个无向图中,所有顶点的度数之和等于所有边数之和的 __2____倍。
2、判断题1无向图的邻接矩阵一定是对称矩阵。
(√2有向图的邻接矩阵一定是对称矩阵。
(×3图的深度优先搜索路径是唯一的。
(×4图的广度优先搜索路径不是唯一的。
(√5一个图可能存在多棵最小生成树。
(√6无向图的邻接矩阵一定是对称的,有向图的邻接矩阵一定是不对称的。
(√7图的关键路径是指从源点到汇点的最短路径。
(×8用邻接矩阵法存储图,占用的存储空间数量只与图中边数有关,与结点个数无关。
(×9对一个图分别进行深度优先搜索和广度优先搜索,得到的结点序列一定是相同的。
(×10图的关键路径是指从源点到汇点的最长路径。
(√3、选择题1一个无向连通图的生成树是含有该连通图的全部顶点的 __A__。
A 、极小连通子图B 、极小子图C 、极大连通子图D 、极大子图 2具有 e 条边的有向图,它的邻接表中有 _D__个弧结点。
A 、 e-1B 、 2eC 、 2(e-1D 、 e3如果某图的邻接矩阵是对角线元素均为零的上三角矩阵,则此图是 __D__A 、无向图B 、完全图C 、强连通图D 、有向无环图4顶点个数为 n 的有向图最多有 __D_条弧。
A 、 n-1B 、 n(n-1/2C 、 n(n+1/2D 、 n(n-1应用题:1. 请给出图 1的所有最小生成树。
(10分图 1共两棵。
第一棵为:(5分错一条边扣 1分。
第二棵为:(5分错一条边扣 1分。
2. 请给出图 2的所有拓扑排序序列。
(16答案如下:仅有两个第一个:abcdefgh (错一个字符扣 1分第二个:abcdegfh (错一个字符扣 1分3、对于有向无环图(如图 3,写出它的所有不同的拓扑有序序列。
第一章绪论一．选择题1．下面关于算法说法正确的是（）A．算法最终必须由计算机程序实现B．为解决某问题的算法同为该问题编写的程序含义是相同的C．算法的可行性是指指令不能有二义性D．以上几个都是错误的2．以下哪一个术语与数据的存储结构无关？（）A．栈 B．哈希表 C．线索树 D．循环队列3．算法复杂度通常是表达算法在最坏情况下所需要的计算量，O(1)的含义是（）A．算法执行一步就完成B．算法执行1秒钟就完成C．算法执行常数步就完成 D．算法执行可变步数就完成4．数据结构研究的内容是（）。
A．数据的逻辑结构 B．数据的存储结构C．建立在相应逻辑结构和存储结构上的算法 D．包括以上三个方面5．一个正确的算法应该具有 5 个特性，除输入、输出特性外，另外 3 个特性是（）。
A．确定性、可行性、有穷性 B．易读性、确定性、有效性C．有穷性、稳定性、确定性 D．可行性、易读性、有穷性6．以下关于数据的逻辑结构的叙述中正确的是（）。
A．数据的逻辑结构是数据间关系的描述B．数据的逻辑结构反映了数据在计算机中的存储方式C．数据的逻辑结构分为顺序结构和链式结构D．数据的逻辑结构分为静态结构和动态结构7．下列时间复杂度中最坏的是（）A．O(1) B．O(n) C．O(log2n） D．O(n2)8．算法的时间复杂度取决于（）A．待处理数据的初态 B．问题的规模C．程序本身所占的空间 D．问题的规模和待处理数据的初态二．综合应用题1.有下列运行时间函数：（1）f1(n)=1000; （2）f2(n)=n2+1000n; （3）f3(n)=3n3+100n2+n+1;分别写出相应的大O表示的运算时间。
2.下面函数mergesort执行的时间复杂度为多少?假设函数调用为mergesort(1,n)，merge 函数时间复杂度为 O(n)void mergesort(int i,int j){int m;if(i!=j){mergesort(i,m);mergesort(m+1,j);merge(i,j,m);//本函数时间复杂度为 O(n)}}第二章线性表一．选择题1．下述哪一条是顺序存储结构的优点？（）A．存储密度大 B．插入运算方便C．删除运算方便 D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。
一、填空题1.数据结构包括、和三方面的内容。
2.数据的逻辑结构分为、、、。
3.数据的逻辑结构分为和两大类。
4.数据的存储结构被分为、、、。
5.数据的存储方式有、、和四种基本存储方式。
6.顺序存储和链式存储相比较的存储密度大，的插入删除方便。
7.在线性表的单链接存储结构中，每个结点包含有两个域，一个叫域，另一个叫域。
8.在线性表的单链接存储中，若一个元素所在结点的地址为P，则其后继结点的地址为，若假定P为一个数组a中的下标，则其后继结点的下标为。
9.在顺序存储的向量中，设第一个元素的地址为loc(k1)，每个元素占用的空间为M，则第i个元素ki的地址为loc(ki)=loc(k1)+(i-1)*M 。
10.在循环单链表中，最后一个结点的指针域指向结点。
11.队列的插入操作在进行，删除操作在进行。
12.一棵n个结点的树，其边数为条。
13.设二叉树根结点的层数为0，则第i层上最多有个结点。
14.在一棵二叉树中，第5层上的结点数最多为。
15.深度为 K 的完全二叉树，至少有个结点，至多有个结点。
16.深度为 8 (根的层次号为 1 )的满二叉树有个叶子结点。
17.深度为K的二叉树结点总数最大为。
18.深度为 k (根的层次号为 1 )的满二叉树有个叶子结点。
19.在完全二叉树中，对结点按层次编号，根结点编号为1。
若结点i有右子女，则右子女的编号为，左子女的编号为。
20.按后根次序周游树林，正好等同于按次序周游与之对应的二叉树。
21.按先根次序周游树林，正好等同于按次序周游对应的二叉树。
22.对一棵二叉排序树进行中序遍历时，得到的结点序列是一个。
23.在一个具有n个顶点的无向完全图中，包含有条边。
24.设有m个结点的无向图中，如果其边数为就称为完全图。
25.在图中，与结点相关的边的数目称为该结点的。
26.在有向图的邻接表和逆邻接表表示中，每个顶点邻接表分别链接着该顶点的所有和结点。
27.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为，在表尾插入元素的时间复杂度为。
习题二
一、选择题
1．在一个长度为n的顺序表中删除第i个元素（0＜i<n）时，需要向前移动( )个元素。
A．n-i B．n-i+1 C．n-i+1 D．i+1
2．从一个具有n个元素的线性表中查找其值等于x的结点时，在查找成功的情况下，需平均比较( )个元素结点。
A．n/2 B．n C．(n-1)/2 D．(n +1)/2 3．对一个具有n个元素的线性表，建立其单链表的时间复杂度为( )。
A．O(n) B．O(1) C．O(n2）D．O（long2n）4．线性表采用链式存储时，其地址( )。
A．必须是连续的B．一定是不连续的
C．部分地址必须连续D．连续与否均可以
5．在一个具有n个结点的有序单链表中插人一个新的结点，使得链表仍然有序，该算法的时间复杂度是( )。
A．O（long2n）B．O（l）C．O（n2）D．O（n）6．线性表是( )。
A．一个有限序列，可以为空B．一个有限序列，不可以为空
C．一个无限序列，可以为空D．一个无限序列，不可以为空7．在一个长度为n的顺序表中，向第i个元素（0一1＜n＋1）之前捕人一个新元素时，需要向后移动( )个元素。
A．n-i B．n-i＋1 C．n－i－1 D．i＋1
8．如果某链表中最常用的操作是取第i个结点及其前驱，则采用( )存储方式最节省时间。
A．单链表B．双向链表C．单循环链表D．顺序表9．一个顺序存储线性表的第一个元素的存储地址是90，每个元素的长度是2，则第6个元素的存储地址是（）。
A．98 B．100 C．102 D．106
10．下列排序方法中，某一趟结束后未必能选出一个元素放在其最终位置上的是( )。
A．堆排序B．冒泡排序C．直接插人排序D．快速排序11．对线性表进行二分查找时，要求线性表必须（）。
A．以顺序方法存储
B．以链接方法存储
C．以顺序方法存储，且结点接关键字有序排列
D．以链接方法存储，且结点接关键字有序排列
12．在顺序存储的线性表（a1……a n）中，删除任意一个结点所需移动结点的平均移动次数为( )
A．n B．n／2 C．(n-1)/2 D．（n＋l）/2 13．在线性表的下列存储结构中，读取元素花费的时间最少的是（）。
A．单链表B．双链表C．循环链表D．顺序表14．若某链表中最常用的操作为在最后一个结点之后插入一个结点和删除最后一个结点，则采用（）存储方式最节省时间。
A．双链表B．单链表C．单循环链表D．带头结点的双循环链表二、填空题
1．线性表（Linear List）是最简单、最常用的一种数据结构。
线性表中的元素存在着_ __的相互关系。
2．线性表中有且仅有一个开始结点，表中有且仅有一个终端结点，除开始结点外，其他每个元素有巨仅有一个，除终端结点外，其他每个元素有且仅有一个3．线性表是n（n>=0）个数据元素的_。
其中n为数据元素的个数，定义为线性表的。
当n为零时的表称为。
4．所谓顺序表（Sequential LISt）是线性表的，它是将线性表中的结点按其依次存放在内存中一组连续的存储单元中，使线性表中相邻的结点存放在的存储单元中。
5．单链表不要求逻辑上相邻的存储单元在物理上也一定要相邻。
它是分配一些的存储单元来存储线性表中的数据元素，这些存储单元可以分散在内存中的的位置上，它们在物理上可以是一片连续的存储单元，也可以是的。
因此在表示线性表这种数据结构时，必须在存储线性表元素的同时，也存储线性表的。
6．线性表的链式存储结构的每一个结点（Node）需要包括两个部分：一部分用来存放元素的数据信息，称为结点的；另一部分用来存放元素的指向直接后继元素的指针(即直接后继元素的地址信息)，称为或
7．线性链表的逻辑关系是通过每个结点指针域中的指针来表示的。
其逻辑顺序和物理存储顺序不再一致，而是一种存储结构，又称为。
8．如果将单链表最后一个结点的指针域改为存放链表中的头结点的地址值，这样就构成了。
9．为了能够快速地查找到线性表元素的直接前驱，可在每一个元素的结点中再增加一个指向其前驱的指针域，这样就构成了。
10．双向链表某结点的指针P，它所指向结点的后继的前驱与前驱的后继都是。
11．在单链表中，删除指针P所指结点的后继结点的语句是
_。
12．在双循环链表中，删除指针P所指结点的语句序列是P->prior->next＝p->next及_。
13．单链表是的链接存储表示。
14．
15．向一个长度为n的向量的第i个元素(l≤i≤n+1）之前插人一个元素时，需向后移动个元素。
16．删除一个长度为n的向量的第i个元素（l≤i≤n）时，需向前移动
个元素。
17．在单链表中，在指针P所指结点的后面插人一个结点S的语句序列是
18．在双循环链表中，在指针P所指结点前插人指针S所指的结点，需执行语句19．取出广义表A＝（（x，（a，b，c，d））中原子c的函数是。
20．在一个具有n个结点的有序单链表中插人一个新结点并使之仍然有序的时间复杂度为。
21．写出带头结点的双向循环链表L为空表的条件。
22．线性表、栈和队列都是_结构。
23．向栈中插人元素的操作是先移动栈针，再存人元素。
三、判断题
1．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。
（）
2．在具有头结点的链式存储结构中，头指针指向链表中的第一个数据结点。
( ) 3．顺序存储的线性表不可以随机存取。
（）
4．单链表不是一种随机存储结构。
（）
5．顺序存储结构线性表的插入和删除运算所移动元素的个数与该元素的位置无关。
( ) 6．顺序存储结构是动态存储结构，链式存储结构是静态存储结构。
（）7．线性表的长度是线性表所占用的存储空间的大小。
（）
8．双循环链表中，任意一结点的后继指针均指向其逻辑后继。
（）
9．线性表的惟一存储形式是链表。
（）。
