数据结构经典习题--每章都有

数据结构习题

第一章 ............................................................................................................................... 2 第二章 ............................................................................................................................... 3 第三章 ............................................................................................................................... 6 第四章 ............................................................................................................................... 7 第五章 ............................................................................................................................... 7 第六章 ............................................................................................................................... 9 第七章 ............................................................................................................................. 11 第九章 ............................................................................................................................. 13 第十章 ............................................................................................................................. 15 十二章 文件 .................................................................................................................... 16

1

第一章

一、 选择题

1.在数据结构中，与所使用的计算机无关的数据叫 结构。 A. 存储 B. 物理 C. 逻辑 D. 物理和存储 二、判断题

1．数据元素是数据的最小单位（ ）。 2．数据项是数据的基本单位（ ）。 三、基本概念

1.简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线 性结构、非线性结构。 2. 常用的存储表示方法有哪几种? 3.设三个函数f,g,h分别

为 f(n)=100n^3+n^2+1000 , g(n)=25n^3+5000n^2 , h(n)=n^1.5+5000nlgn 请判断下列关系是否成立： (1) f(n)=O(g(n)) (2) g(n)=O(f(n)) (3) h(n)=O(n^1.5)

(4) h(n)=O(nlgn)

◇ 这里我们复习一下渐近时间复杂度的表示法T(n)=O(f(n))，这里的\是数学符号，它的严格定义是\若T(n)和f(n)是定义在正整数集合上的两个函数，则T(n)=O(f(n))表示存在正的常数C和n0 ,使得当n≥n0时都满足0≤T(n)≤C·f(n)。\用容易理解的话说就是这两个函数当整型自变量n趋向于无穷大时，两者的比值是一个不等于0的常数。这么一来，就好计算了吧。第(1)题中两个函数的最高次项都是n^3,因此当n→∞时，两个函数的比值是一个常数，所以这个关系式是成立的。

2

第二章

一、 选择题

１.在一个长度为n的顺序表中，向第i个元素(1≤i≤n+1)之前插入一个新元素时，需向后移动 个元素。

A. n-1 B. n-i+1 C. n-i-1 D. I

2.线性表是 。 A. 一个有限序列，可以为空 B. 一个有限序列，不能为空 C. 一个无限序列，可以为空 D. 一个无限序列，不能为空

3.对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的，

删除一个元素时大约要移动表中的 个元素。 A. n+1 B. n-1 C. (n-1)/2 D. n 4.线性表采用链式存储时，其地址 。

A. 必须是连续的 B. 部分地址必须是连续的

C. 一定是不连续的 D. 连续与否均可以 5.设单链表中指针p指着结点(数据域为m)，指针f指着将要插入的新结点(数据域为x)，当x插在结点m之后时，只要先修改 后修改p->link=f即可。 A. f->link=p; B. f->link=p->link;

C. p->link=f->link; D. f=nil;

6.在双向链表存储结构中，删除p所指的结点时需修改指针 。 A. ((p->rlink) ->rlink) ->link=p; p->rlink=(p->rlink) ->rlink; B. (p->llink) ->rlink=p->rlink; (p->rlink) ->llink=p->llink; C. p->llink=(p->llink) ->llink; ((p->llink) ->llink) ->rlink=p;

D. ((p->llink) ->llink) ->rlink=p; p->llink=(p->llink) ->llink;

7.在双向链表存储结构中，删除p所指的结点的前趋结点（若存在）时需修改指

针 。

A. ((p->llink) ->llink) ->rlink=p; p->llink=(p->llink) ->llink; B. ((p->rlink) ->rlink) ->llink=p; p->rlink=(p->rlink) ->rlink; C. (p->llink) ->rlink=p->rlink; (p->rlink) ->llink=p->llink;

D. p->llink=(p->llink) ->llink; ((p->llink) ->llink) ->rlink=p;

8.根据线性表的链式存储结构，每个结点所含指针的个数，链表分为单链表和 。 A. 循环链表 B. 多重链表 C. 普通链表 D. 无头结点链表

9.从一个具有n个节点的单链表中查找其值等于x结点时，在查找成功的情况下，需 平 均比较 个结点。 A. n B. n/2 C. (n-1)/2 D. (n+1)/2

10.在一个单链表中，已知*q结点是*p结点的前驱结点，若在*q和*p之间插入*s结点， 则执行 。

A. s->next=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;

二、填空

1. 在线性结构中第一结点 _______，其余每个结点有且只有 _______；最后一个结点

________，其余每个结点有且只有 [________。 2. 对于顺序存储的线性表，当随机插入或删除一个元素时，约需平均移动表长 ___ 的

3

元素。

3. 对于长度为n的顺序表，插入或删除元素的时间复杂性为 ____ ；对于顺序栈或队

列，插入或删除元素的时间复杂性为 _______ 。

4.从顺序表中删除第i个元素时，首先把第i个元素赋给 _______ 带回，接着从 _______ 开始向后的所有元素均 ______一个位置，最后使线性表的长度 __ 。

5.在线性表的顺序存储中，元素之间的逻辑关系是通过 _____ 决定的；在线性表的链接存储中，元素之间的逻辑关系是通过 _____ 决定的。 6.一个单链表中删除*p结点时，应执行如下操作: (1)q=p->next;

(2)p->data=p->next->data;

(3)p->next= [1] q->next或p->next->next ; (4)free(q);

7.若要在一个单链表中的*p结点之前插入一个*s结点时，可执行如下操作: (1)s->next= [1] p->next ; (2)p->next=s; (3)t=p->data;

(4)p->data= [2] s->data ; (5)s->data= [3] t ;

8.对于线性表的顺序存储，需要预先分配好存储空间，若分配太多则容易造成存储空

间的 ______ ，若分配太少又容易在算法中造成 ____ ，因此适应于数据量变化不大的情况；对于线性表的链接存储(假定采用动态结点)，不需要 ____分配

存储空间，存储器中的整个 _____ 都可供使用，分配和回收结点都非常方便，能够有效地利用存储空间，在算法中不必考虑 ___ 的发生，因此适应数据量变化较大的情况。

三、判断题

1．顺序存储的线性表可以随机存取（ ）。

2．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性

因此，是属于同一数据对象（ ）。

3．在单链表中，任何两个元素的存储位置之间都有固定的联系，因为可以从头结点查

找任何一个元素（ ）。

4．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构（ ）。

5．链表的每个结点中，都恰好包含一个指针（ ）。

四、综合题

1. 线性表有两种存储结构：一是顺序表，二是链表。试问： (1)两种存储表示各有哪些主要优缺点?

(2)如果有n个线性表同时并存，并且在处理过程中各表的长度会动态发生变化，线性 表的总数也会自动地改变。在此情况下，应选用哪种存储结构?为什么? (3)若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么，应采用哪种存储结构?为什么?

2. 用线性表的顺序结构来描述一个城市的设计和规划合适吗?为什么?

3. 在单链表和双向表中，能否从当前结点出发访问到任一结点? 4. 编写下列算法

(1)向类型有list的线性表L的第i个元素（0≤i≤L.len）之后插入一个新元素x。

4

(2)从类型为list的线性表L中删除其值等于x的所有元素。

(3)将两个有序表A和B合并成一个有序表C，其中A，B，C均为list类型的变参。 5.编写下列算法，假定单链表的表头指针用HL表示，类型为linklist。 (1)将一个单链表中的所有结点按相反次序链接。 (2)删除单链表中第i个（i≥1）结点。 (3)删除单链表中由指针p所指向的结点。

(4)从带有附加表头结点的循环单链表中删除其值等于x的第一个结点。 (5)在单链表中指针p所指结点之前插入一个值为x的新结点。 (6)从循环单链表中查找出最小值。

(7)根据一维数组A(1:n)中顺序存储的具有n个元素的线性表建立一个带有附加表头结

点的单链表。

(8)请指出下面的过程执行p(5)和p(6)时分别输出的结果。 void P(int n); {

if n>0

{

p(n-2);

printf(\ } }

(9)假定用一个循环单链表表示队列（称此为循环链队），该队列只设一个队尾指针，设

队首指针，试编写下列算法：

(1)向循环链队插入一个元素为x的结点；

(2)从循环链队中删除一个结点（假定不需要保留被删除结点的值和不需要回收结

点）。

5

2. 对于二叉排序树，当所有结点的权都相等的情况下，最佳二叉排序树有何特点。 3. 试证明已知一棵二叉树的前序序列和中序序列，则可唯一地确定一棵二叉树。

第七章

一、 选择题

1.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 倍。

A. 1/2 B. 1 C. 2 D. 4 2.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为 。

A. n B. n+1 C. n-1 D. n+e

3.具有n个顶点的无向完全图，边的总数为 条。

A. n-1 B. n C. n+1 D. n*(n-1)/2 4.设图G有n个顶点和e条边，当G是非孤立顶点的连通图时有2e>=n,故可推得深度优先搜索的时间复杂度为 。

A. O(e) B. O(n) C. O(ne) D. O(n+e) 5.在无向图G的邻接矩阵A中，若A[i,j]等于1，则A[j,i]等于 。 A. i+j B. i-j C. 1 D. 0

6.图的深度优先或广度优先遍历的空间复杂性均为 。(访问标志位数组空间) A. O(n) B. O(e) C. O(n-e) D. O(n+e)

二、 填空

1.在图G的邻接表表示中，每个顶点邻接表中所含的结点数，对于无向图来说等于该 顶点的 ，对于有向图来说等于该顶点的 。

2.假定一个图具有n个顶点和e条边，则采用邻接矩阵表示的空间复杂性为 ， 采用邻接表表示的空间复杂性为 。 3.已知一个无向图的邻接矩阵如下所示，则从顶点A出发按深度优先搜索遍历得到的 顶点序列为 ，按广度优先搜索遍历得到的顶点序列为 A B C D E F ┏0 1 1 0 1 0┓A ┃1 0 1 0 1 1┃B ┃1 1 0 1 0 0┃C ┃0 0 1 0 0 1┃D ┃1 1 0 0 0 1┃E

┗0 1 0 1 1 0┛F

4.已知一个图如下所示，在该图的最小生成树中，各边的权值之和为 。 10

① ② 15 5 2 8 ⑤ 12

11

③ 3 ④

三、 判断题

1.有回路的图不能进行拓扑排序（ ）。 2.有回路的图不能进行拓扑排序（ ）。 3.连通分量是无向图中的极小连通子图（ ） 四、综合题

1.证明n个顶点的无向完全图的边数的n(n－1)/2。

2.证明一个有n个顶点，e条边的无向图G，必有∑dj ＝2e其中dj 为顶点j的度。 3.证明若无向图G的顶点度数的最小值大于或等于2，则G有一条回路。 4. 设无向图G如下图：

B E

A D G

C F 试给出

(1)该图的邻接矩阵；

(2)该图的邻接表；

(3)从A出发的“深度优先”遍历序列； (4)从A出发的“广度优先”遍历序列。

12

第九章

一、选择题

1.二分法查找 存储结构。

A. 只适用于顺序 B. 只适用于链式 C. 既适用于顺序也适用于链式 D. 既不适合于顺序也不适合于链式

2.已知一个有序表为(12、18、24、35、47、50、62、83、90、115、134)，当二分查找值为90的元素时， 次比较后查找成功；当二分查找值为47的元素时， 次比较后查找成功。 A. 1 B. 2 C. 3 D. 4

3.散列函数有一个共同性质，即函数值应当以 取其值域的每个值。 A. 最大概率 B. 最小概率 C. 平均概率 D. 同等概率 4.设散列地址空间为0～m－1,k为关键字，用p去除k，将所得的余数作为k的散列地址，

即H(k)＝k % p。为了减少发生冲突的频率，一般取p为 。 A. 小于m的最大奇数 B. 小于m的最大偶数

C. m D. 小于m的最大素数

二、填空

1. 假定在有序表A[1..20]上进行二分查找，则比较一次查找成功的结点数为 ， 比较两次查找成功的结点数为 ，比较三次查找成功的结点数为 ，比较四次查找成功结点数为 [4]8 ，比较五次查找成功的结点数为 ，平均查找长度为 。 2. 在索引查找或分块查找中，首先查找 ，然后再查找相应的 ，整个

索引查找的平均查找长度等于查找索引表的平均查找长度与查找相应子表的平均查找长度之 。

3. 在散列存储中，装填因子α的值越大，存取元素时发生冲突的可能性就 ，当α的值

越小，存取元素时发生冲突的可能性就 。

4. 给定线性表(18,25,63,50,42,32,90)，用散列方式存储，若选用h(K)=K % 9作为散列函

数，则元素18的同义词元素共有 个，元素25的同义词元素共有 个，元素50的同义词元素共有 个。 三、判断题

1.散列法存储的基本思想是由关键码的值决定数据的存储地址（ ）。

2.散列表的查找效率取决于散列表造表时选取的散列函数和处理冲突的方法（ ）。 3.m阶B-树每一个结点的子树个数都小于或等于m（ ）。 四、综合题

1.若对大小均为n的有序的顺序表和无序的顺序表分别进行顺序查找，试问在下面三 种情况下，分别讨论两者在等概率时，平均查找长度是否相同?

(1)查找不成功，即表中没有关键字等于给定值k的记录；

(2)查找成功，且表中只有一个关键字等于给定值k的记录；

(3)查找成功，且表中有若干个关键字等于给定值k的记录，一次查找要求找出所有记

录，此时的平均查找长度应考虑找到所有记录时所用的比较次数。

2.假定有n个关键字，它们具有相同的Hash函数值，用线性探测方法把这n个关键字 存入到Hash地址空间中要做多少次探测?

3.有一个2000项的表，欲采用等分区间顺序查找方法进行查找，问 (1)每块的理想长度是多少?

13

(2)分成多少块最为理想?

(3)平均查找长度是多少?

(4)若每块长度为20，平均查找长度是多少?

4.设A(k)有如下10个元素：2，4，6，8，10，12，14，16，18，20。若对A(k)分别查找x＝1，3，13，21，试跟踪下面过程的执行，并分析该程序段关于n的计算时间。 【程序段】 i=1;j=n; do {

k=(i+j)/2; if A(k)<=x i=k+1 else j=k-1

}while !(i>j);

5.设有一个已排序的整数数组a[1..n]，和一个整数x，研究下面用类C所表示的折半查找的五个程序段，指出哪些是正确的。 第一个：

i=1; j=n;

do{ k=(i+j)div 2;

if x>a[k] i=k+1; else j=k-1; }while !((a[k]=x) || (i>j)); 第二个: i=1; j=n; while (i<=j) { k=(i+j) / 2;

switch{

case x>a[k]: i=k+1; case x= =a[k]: return; case x

第三个：

i=1; j=n;

do{ k=(i+j) / 2; if x>a[k] i=k; else j=k

}while !((a[k]= =x) || (i>=j)); 第四个： i＝1; j=n;

do{ k=(i+j) / 2;

if xa[k] i=k+1; }while !(i>=j); 第五个：

14

i=1; j=n;

do{ k=(i+j) / 2;

if x=j);

第十章

一、选择题

1.目前以比较为基础的内部排序时间复杂度T(n)的范围是 ；其比较次数与待

排序的记录的初始排列状态无关的是 。

A. ①O(log2 n)～O(n) ②O(lon2 n)～O(n2 )

③O(nlog2 n)～O(n2 ) ④O(n)～O(n2 ) ⑤O(n)～O(nlog2 n) B. ①插入排序 ②先用二分法查找，找到后插入排序 ③快速排序 ④冒泡排序

2.设关键字序列为：3,7,6,9,8,1,4,5,2。进行排序的最小交换次数是 。 A. 6 B. 7 C. 8 D. 20 3.在归并排序过程中，需归并的趟数为 。

A. n B. √n C. log2 n向上取整

D. log2 n向下取整 4.一组记录排序码为(46、79、56、38、40、84)，则利用堆排序的方法建立的初始堆为 。 A. (79、46、56、38、40、80) B. (84、79、56、38、40、46)

C. (84、79、56、46、40、38) D. (84、56、79、40、46、38)

5.一组记录的关键码为(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) 6.在平均情况下快速排序的时间复杂性为 ，空间复杂性为 ；在最坏情况 下（如初始记录已有序），快速排序的时间复杂性为 ，空间复杂性为 。 A. O(n) B. O(log2 n) C. O(nlog2 n) D. O(n2 )

二、填空

1.在对一组记录(54,38,96,23,15,72,60,45,83)进行直接选择排序时，第四次选择和交换后，未排序记录(即无序表)为 。

2.在对一组记录(54,38,96,23,15,72,60,45,38)进行冒泡排序时，第一趟需进行相邻记

录交换的次数为 ，在整个冒泡排序过程中共需进行 趟后才能完成。 3.在归并排序中，若待排序记录的个数为20，则共需要进行 趟归并，在第三趟归并中，是把长度为 的有序表归并为长度为 的有序表。 4.在直接插入和直接选择排序中，若初始数据基本正序，则选用 ，若初始数

据基本反序，则选用 。

5 .在堆排序、快速排序和归并排序中，若只从节省空间考虑，则应首先选取

方法，其次选取 方法，最后选取 方法；若只从排序结果的稳定

性考虑，则应选取 ；若只从平均情况下排序最快考虑，则应选取 _______方法；若只从最坏情况下排序最快并且要节省内存考虑，则应选取 方法。

15

三、判断题

1.当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影

响时间复杂性的主要因素（ ）。

2.对于n个记录的集合进行快速排序，所需要的平均时间是O(nlog2 n)（ ）。 3.对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2 n)（ ）。 4.堆中所有非终端结点的值均小于或等于（大于或等于）左右子树的值（ ）。 四、综合题

1.在执行某种排序算法的过程中，出现了排序码朝着最终排序序列相反的方向移动， 从而认为该排序算法是不稳定的，这种说法对吗?为什么? 2.设有5000个无序的元素，希望用最快速度挑选出其中前10个最大的元素。在以下 的排序方法中，采用哪种方法最好?为什么?快速排序，堆排序，归并排序，基数排序的Shell排序。 3.证明对一个长度为n的任意文件进行排序，至少需要作nlog2 n比较。 4.判断下列序列是否是堆。若不是堆，则把它们依次调整为堆。 (1) (100，85，98，77，80，60，82，40，20，10，66)； (2) (100，98，85，82，80，77，66，60，40，20，10) (3) (100，85，40，77，80，60，66，98，82，10，20)； (4) (10，20，40，60，66，77，80，82，85，98，100)； 5.什么是内部排序？什么是排序方法的稳定性和不稳定性？

十二章 文件

一、综合题

1.试列出文件的存储结构以及其相应文件类型，并简略回答其特点。

16

三、判断题

1.当待排序的元素很多时，为了交换元素的位置，移动元素要占用较多的时间，这是影

响时间复杂性的主要因素（ ）。

2.对于n个记录的集合进行快速排序，所需要的平均时间是O(nlog2 n)（ ）。 3.对于n个记录的集合进行归并排序，所需要的平均时间是O(nlog2 n)（ ）。 4.堆中所有非终端结点的值均小于或等于（大于或等于）左右子树的值（ ）。 四、综合题

1.在执行某种排序算法的过程中，出现了排序码朝着最终排序序列相反的方向移动， 从而认为该排序算法是不稳定的，这种说法对吗?为什么? 2.设有5000个无序的元素，希望用最快速度挑选出其中前10个最大的元素。在以下 的排序方法中，采用哪种方法最好?为什么?快速排序，堆排序，归并排序，基数排序的Shell排序。 3.证明对一个长度为n的任意文件进行排序，至少需要作nlog2 n比较。 4.判断下列序列是否是堆。若不是堆，则把它们依次调整为堆。 (1) (100，85，98，77，80，60，82，40，20，10，66)； (2) (100，98，85，82，80，77，66，60，40，20，10) (3) (100，85，40，77，80，60，66，98，82，10，20)； (4) (10，20，40，60，66，77，80，82，85，98，100)； 5.什么是内部排序？什么是排序方法的稳定性和不稳定性？

十二章 文件

一、综合题

1.试列出文件的存储结构以及其相应文件类型，并简略回答其特点。

16

本文来源：https://www.bwwdw.com/article/v15t.html