数据结构综合题库

1 判断题

（ ）1. 数据的逻辑结构与数据元素本身的内容和形式无关。 （ ）2. 线性表的逻辑顺序与物理顺序总是一致的。

（ ）3. 若有一个叶子结点是二叉树中某个子树的前序遍历结果序列的最后一个结点，则它一定是该子树的中序遍历结果序列的最后一个结点。

（ ）4. 对于同一组待输入的关键码集合，虽然各关键码的输入次序不同，但得到的二叉搜索树都是相同的。

（ ）5. 最优二叉搜索树的任何子树都是最优二叉搜索树。

（ ）6. 在二叉搜索树上插入新结点时，不必移动其它结点，仅需改动某个结点的指针，使它由空变为非空即可。

（ ）7. 有n（n≥1）个顶点的有向强连通图最少有n条边。 （ ）8. 连通分量是无向图中的极小连通子图。 （ ）9. 二叉树中任何一个结点的度都是2。

（ ）10. 单链表从任何一个结点出发，都能访问到所有结点。 （ ）11.线性表的长度是线性表占用的存储空间的大小。 （ ）12.队列只能采用链式存储方式。

（ ）13.用邻接矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关。 （ ）14.由二叉树的先序序列和中序序列能唯一确定一棵二叉树。 （ ）15.图中一个顶点i的出度等于其邻接矩阵中第i列的非0元个数。 （ ）16. 线性表的链接存储，表中元素的逻辑顺序与物理顺序一定相同。

（ ）17.数据结构概念包括数据之间的逻辑结构，数据在计算机中的存储方式和数据的运算三

个方面。

（ ）18.线性表中的每个结点最多只有一个前驱和一个后继。 （ ）19.二叉排序树查找总比顺序查找速度快。

（ ）20.对具有n个顶点的连通图进行深度优先遍历，所得顶点序列是唯一的。 （ ）21.线性表中各个数据元素的类型必须是相同的。 （ ）22.B树是一种特殊的二叉树。 （ ）23.栈可视为一种特殊的线性表。 （ ）24.快速排序总是比其它排序方法快。

（ ）25.使用双向链表存储数据，可以提高查找（定位运算）的速度。 （ ）26.最小生成树是边数最少的生成树。

+

二、单选题

1 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动（ ）个元素。

A．8 B. 63.5 C. 63 D. 7 2 设有一个二维数组A[m][n]，假设A[0][0]存放位置在644（10），A[2][2]存放位置在676（10），每个元素占一个空间，则A[3][3]在（ ）位置，（10）表明用10进数表示。

A．692（10） B. 626（10） C. 709（10） D. 724（10） 3 N个顶点的连通图至少有（ ）条边。

A．N－1 B. N C. N＋1 D. 0 4 下面程序的时间复杂度为（ ）。 for(int i=0; i

22

A．O(m) B. O(n) C. O(m*n) D. O(m+n)

5 设单链表中结点的结构为(data, link)。 已知指针q所指结点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s,则应执行下列哪一个操作（ ）。

A．s->link=p->link; p->link =s; B. q->link=s; s->link =p;

C. p->link=s->link; s->link =q; D. p->link=s; s->link =q; 6 栈的插入和删除操作在（ ）进行。

A．栈顶 B. 栈底 C. 任意位置 D. 指定位置 7 若让元素1，2，3依次进栈，则出栈次序不可能出现哪种情况（ ）。

A．3，2，1 B. 2，1，3 C. 3，1，2 D. 1，3，2 8 广义表A(a),则表尾为（ ）。

A．a B. (()) C. 空表 D. （a） 9 采用邻接表存储的图的深度优先遍历算法类似于二叉树的（ ）。

A．中序遍历 B. 前序遍历 C. 后序遍历 D. 按层次遍历

10 每次从无序表中挑选出一个最小或最大元素，把它交换到有序表的一端，此种排序方法叫做（ ）排序。

A．插入 B. 选择 C. 交换 D. 外排序

11. 一个顺序表有255个对象，采用顺序搜索查找，平均数据比较次数为（ ）。 A．128 B. 127 C. 126 D. 255 12. 含5个结点（元素值均不相同）的二叉树搜索树有（ ）种。 A．54 B. 42 C. 36 D. 65

13．数据结构中，与所使用的计算机无关的是数据的 结构。

（A）存储； （B）物理； （C）逻辑； （D）物理和存储； 14． 在链表中进行操作比在顺序表中进行操作效率高。 （A）顺序查找； （B）折半查找； （C）分块查找； （D）插入； 15．树结构最适合于用来表示 。

（A）元素间具有分支和层次关系的数据； （B）无序数据； （C）有序数据； （D）元素间没

有关联的数据；

16．借助于栈，输入A、B、C、D四个元素，则不可能出现的输出序列为 。 （A）ABCD； （B）CABD； （C）DCBA； （D）BACD；

17. 从理论上讲，将数据以 结构存放，则查找一个数据所用时间不依赖于数据个数N。 A 二叉查找树； （B）链表； （C）二叉树； （D）散列表； 18.头指针为L的单循环链表，指针p所指结点为尾结点的条件为 。

（A）p→next = NULL； （B）p→next = L； （C）p = L； （D）p = NULL； 19直接选择排序的时间复杂度为 （n为元素的个数）。

2

A O(n)； (B) O(log2 n)； (C) O(n log2 n)； (D) O(n)。 20 散列存储中，碰撞（或称冲突）指的是 。

（A）两个元素具有相同序号； （B）不同的关键字对应于相同的存储地址； （C）两个记录的关键字相同； （D）数据元素过多；

三、填空题

1. 算法是一个有穷的指令集，它为解决某一特定任务规定了一个运算序列。它应具有输入、输

出、_______________、有穷性和可执行性等特性。

2. 当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的______ _ ___。 3. 在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是___________。

4. 当用长度为n的数组顺序存储一个栈时，若用top==n表示栈空，则表示栈满的条件为

____________________。

5. 对序列(49,38,65,97,76,27,13,50)采用快速排序法进行排序，以序列的第一个元素为基准

元素得到的划分结果是____________________ _______。

6. 对于一棵具有n个结点的树，该树中所有结点的度数之和为___________________。 7. 请指出在顺序表{5、11、23、35、51、64、72、85、88、90、98}中，用折半查找关键码30

需做______________次关键码比较。

8. 若线性表采用顺序存储结构，每个元素占用4个存储单元，第一个元素的存储地址为100,则

第12个元素的存储地址是__________________。

9. 在一个长度为n 的顺序表中，向第i个元素（1≤ i≤ n＋１）之前插入一个新元素时，需要

向后移动____________个元素。

10. 设有两个串p和q，求q在p中首次出现的位置的运算称作_____________。

11. 判定一个循环队列QU(最多元素为m)为满队列的条件是_______ __ ___。 12. 在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是____________条。 13. 对于一个具有n个顶点的图，若采用邻接矩阵表示 ，则矩阵大小为___________。 14.有N个顶点的无向连通图最少有_____________________条边。

15.在下图所示的链表中，若在指针p所指的结点之后插入数据域值相继为a和b的两个结点，则

可用下列两个语句实现该操作，它们依次是________________________ 和_________________________。

16.设根结点的层数为0，定义树的高度为树中层数最大的结点的层数。则高度为k的二叉树具有

的结点数目，最少为___________,最多为___________。

17．单链表中指针p所指结点只有一个后继结点的条件是 。 18．深度为k的满二叉树有 个结点。

19．设s =‘I AM A STUDENT’， t =‘GOOD WORKER’，CONCAT(Substr(s，6，2)，t) = 。

20．文件在外存储器组织结构的三种形式分别为 、 和 。

21．对广义表LS=(a, ((b, c), ( ), d), (((e))))进行HEAD和TAIL运算的结果分别

是 、 。

22 二维数组A[1..20，1..10]按行优先顺序存储，每个元素占4个单元，且A[1，1]的地址是1000，则A[18，9]的存储地址是 。

23. 深度为k的完全二叉树至少有 个结点，至多有 个结点。

24 ISAM文件由 、柱面索引、磁道索引和主文件组成。

25在单链表中，将指针p所指结点插到指针s所指结点后面的两步主要操作语句

为 ， 。

26．设二维数组A[1..20，1..10]按行优先存储，每个元素占4个单元，A[1，1]的地址是100，则A[5，5]的地址是 。

27．散列既是一种 方式，又是一种查找方法。

28 抽象数据类型定义由 部份组成。

四、程序阅读填空

1. 在顺序表中第 i 个位置插入新元素 x

template int SeqList::Insert (Type & x, int i){ if (i<0||i>last+1||last==MaxSize-1) return 0; //插入不成功 else {

last++;

for( ________________________;j>i;j--)

__________________________;

data[i] = x;

return 1; //插入成功 } }

2. 直接选择排序的算法

template void SelectSort(datalist & list)

{ for(int i=0; i

template viod SelectExchange(datalist & list, const int i){

int k = i;

for(int j=i+1;j< list.CurrentSize;j++)

if(list.Vector[j].getKey()

___ __________________;//当前具有最小关键码的对象

if(k!=i) Swap(list.Vector[i], list.Vector[k]); //交换 }

3、 删去链表中除表头结点外的所有其他结点

template void List :: MakeEmpty ( ) { ListNode *q;

while (first→link!=NULL){

__________________________;

__________________________;

//将表头结点后第一个结点从链中摘下 delete q; //释放它 }

last = first; //修改表尾指针 }

4、基于有序顺序表的折半搜索递归算法（Element为有序顺序表）

template int orderedList ::

BinarySearch(const Type & x, const int low, const int high)const {

int mid = -1;

if ( low <= high ) {

__________________________;

if ( Element[mid].getKey( ) < x )

mid = BinarySearch (__________________________); else if ( Element[mid].getKey( ) > x ) mid = BinarySearch ( x, low, mid -1 ); }

return mid; }

5、在顺序表中第 i 个位置插入新元素 x 。

int insert(sqlist *L, datatype x, int i) { int j;

if (L->n==maxsize) {cout<<”表满，不能插入！（上溢）\\n”; return –1; }

if( ) {cout<<”非法插入位置！\\n”; return 0;} for(j=L->n;j>=i;j--)

L->data[j]=L->data[j-1]; //节点后移 ; //插入x L->n++; //修改表长 Return 1; //插入成功 }

6、直接选择排序的算法

void SelectSort( list R, int n ) { int i, j, k;

for (i=1; i<=n-1;i++) { //n-1趟排序 ;

for(j=i+1;j<=n,j++) //在当前无序区中找键值最小的记录R[k] if(R[j].key

} }

五、简答题

1. 线性表可用顺序表或是链表存储，此两种存储表示各有哪些优缺点？

2. 设有一个输入数据的序列是{46,25,78, 62, 12, 37, 70, 29}，试画出从空树起，逐个输入

各个数据而生成的二叉搜索树。

3.用广义表的带表头结点的存储表示法表示下列集合。

A = ( ) B = (6, 2)

C = (‘a’,( 5, 3, ‘x’)) D = (B, C, A) E = (B, D)

4.上图所示为一有向图，请给出该图的下述要求：

（1）给出每个顶点的入度和出度；

（2）以结点3为起始结点，分别画出该图的一个深度优先生成树和一个宽度优先生成树； （3）给出该图的邻接矩阵； （4）给出该图的邻接表；

5. 对于如上图所示的有向图，试写出：

(1) 从顶点①出发进行深度优先搜索所得到的深度优先生成树； (2) 从顶点②出发进行广度优先搜索所得到的广度优先生成树；

6.已知二叉树的先序、中序和后序序列分别如下，但其中有一些已模糊不清，试构造出该二叉树。

先序序列 _BC_EF__ 中序序列 BDE_AG_H 后序序列 _DC_GH_A

7．分析下列两个程序段的运行时间（时间复杂度）。 void mystery (int n) { int i, j, k;

for (i =1; i < n; i++)

for (j = i+1; j <= n; j++) for (k = 1; k<= j; k++); }

void odd (int n)

{ int i, j, x = 0, y = 0; for (i =1; i <= n; i++) if odd(i)

{ for(j = i; j <= n; j++) x++; for( j = 1; j <= i; j++) y++; } }

9.有一组数据：25，50，70，21，4，18，100，43，7，12。现采用汽泡排序算法进行排序，写出每趟排序的结果，并标明第一趟数据的移动情况。

10. 数据结构与软件的关系是什么?。解决实际问题时，选取或者设计数据结构的原则是什么?。

11. 说明下列概念是否正确：①线性表在物理存储空间中也一定是连续的；②链表的物理存储结构具有同链表一样的顺序；③链表的删除算法很简单，因为当删去链表中某个结点后，计算机会自动地将后继的各个单元向前移动。使用双向链表存储数据，可以提高查找（定位）的速度。

12．写一个算法，借助栈将一个单链表倒置（提示：可以使用栈的基本运算）。也即，将下面的

单链表：

13描述以下概念的区别：头指针、头结点、首元结点。头指针变量和头结点的作用?。并比较顺序存储结构和链式存储结构的优缺点。

14哪些链表可以仅由一个尾指针来唯一确定。即从尾指针出发能访问到链表上任何一个结点。

15 设n为正整数，试确定下列三段程序中带下划线语句的频度。 (a) int i =1, k = 0；

while (i <= n–1) { k = k +10*i; i = i+1; }

(b) int i =1, j = 0；

while ((i+j) <= n) if (i>j) j++; else i++;

(c) int i =1, k = 0；

while (– i <= n –1) { k = k+10*i;

i++;

}

16 已知s =‘(xyz)+*’，t =‘(x+z)*y’，试利用联接、求子串和置换等串的基本运算，将s

转化为t。

17 有如下12个整数：23，37，7，79，29，43，73，19，31，61，23，47，按气泡排序方法将

这组整数排序，分别写出每遍处理后的数列。

18 逻辑结构与存储结构是什么关系?，有何区别?。

19 设计求解下列问题的C++语言算法，并分析其最坏情况时间复杂度及其数量级：1) 在数组

A[1…n]中查找值为k的元素，若找到则输出其位置i（1<=i<=n），否则输出0作为标志；2) 找出数组A[1…n]中元素的最大值和次最大值（本小题以数组元素的比较为标准操作）。 20 写出下面二叉树的中序遍历结果。

J

21 若栈为S，且已知pop(S) = A，试说明下列等式是否成立：Pop (push(S，A)) = push (S，

pop(S))；

22 对于下图，从顶点1出发，分别按深度优先搜索和广度优先搜索方法遍历，写出相应的顶点序列。

23．已知下图所示双向循环链表L=（a，b，c，d）。请写出将该表转换为L=（b，a，c，d）的简单操作。

24．对于给定字符串，1234+ –×/15678，试写出删除串中的‘+ –×/’的算法。

25 算法与程序有何不同?，为何要引出算法概念?，如何评价算法的时间、空间复杂性及好坏?。 26 已知线性表（a1，a2，…，an）中的元素值按递增有序排列，选用向量结构存放。试编写算法删除线性表中值介于c与d (c <= d)之间的元素。

27. 说明栈和队列与线性表的异同点。

28、给定一组元素值17、28、54、30、27、94、15、21、83、40，用这一组元素值构造一棵哈夫曼树。

29 如果队列中不设表头结点，如图所示，并令front＝rear＝null表示队列空，试写出实现队列的三个基本操作（入队、出队、判空）。

30、设一个有序文件的关键字为2，5，8，11，13，17，25，36，47，55，60，63，65，67，76，

84，当用折半查找算法查找关键字55时，试决定关键字的比较次数。 31、抽象数据类型（ADT）与面向对象方法有何关系? 使用ADT的优点有哪些?

32、给出一组关键字{12，2，16，30，8，4，10，20，6，18}。写出按下上升排序时，用汽泡排序方法排序的每一趟排序结束状态。

33、试写出一个将已知字符串所有字符倒过来重新排列的算法。例如ABCDEF改为FEDCBA。 34、 试描述数据结构的概念与程序设计语言中数据类型概念的区别。 35、 试设计算法，求循环链表中结点的个数，并删除表中的第一个结点a1。

27. 说明栈和队列与线性表的异同点。

28、给定一组元素值17、28、54、30、27、94、15、21、83、40，用这一组元素值构造一棵哈夫曼树。

29 如果队列中不设表头结点，如图所示，并令front＝rear＝null表示队列空，试写出实现队列的三个基本操作（入队、出队、判空）。

30、设一个有序文件的关键字为2，5，8，11，13，17，25，36，47，55，60，63，65，67，76，

84，当用折半查找算法查找关键字55时，试决定关键字的比较次数。 31、抽象数据类型（ADT）与面向对象方法有何关系? 使用ADT的优点有哪些?

32、给出一组关键字{12，2，16，30，8，4，10，20，6，18}。写出按下上升排序时，用汽泡排序方法排序的每一趟排序结束状态。

33、试写出一个将已知字符串所有字符倒过来重新排列的算法。例如ABCDEF改为FEDCBA。 34、 试描述数据结构的概念与程序设计语言中数据类型概念的区别。 35、 试设计算法，求循环链表中结点的个数，并删除表中的第一个结点a1。

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