算法与数据结构复习(0910)

算法与数据结构复习题（0910）

基本要求

1．算法与数据结构基本概念 （1）数据、数据对象和数据结构 （2）抽象数据类型

（3）算法的特征及评价的标准 （4）数据的存储结构类型 2．线形结构

（1）顺序表的特点及存储结构 （2）链表的特点及存储结构 （3）栈的特点及基本操作 （4）队列的特点及基本操作 （5）顺序串和链串的存储结构 （6）二维数组的地址计算

（7）稀疏矩阵的概念及存储结构

（8）线性表的排序（插入、选择和交换） （9）线性表的查找（顺序、折半和分块） 3．树形结构

（1）二叉树的性质及存储结构 （2）二叉树的遍历 （3）线索二叉树

（4）树的存储结构

（5）树、二叉树与森林的转化方法 （6）哈夫曼树

（7）二叉排序树及平衡化 （8）堆排序树 （9）B-树 4．图形结构

（1）图的定义及存储结构

（2）图的深度优先和广度优先遍历。 （3）无向图的连通性和最小生成树 （4）拓扑排序 （5）关键路径

（6）单源最短路径 5．散列表（哈希表） （1）散列表的概念

（2）散列表解决散列冲突的方法（开放地址法、链地址法） （3）散列表的插入和删除 6．算法分析与设计基础 （1）分治与递归的关系 （2）贪心算法的思想

（3）回溯与分支限界算法的比较

（4）算法时间和空间复杂度的简单分析

1

一、单选题

1．数据结构被形式地定义为（D,R），其中D 是

A. 算法 B. 操作的集合 C. 数据元素的集合 D. 数据关系的集合 2．顺序表是线性表的

A. 顺序存储结构 B. 链式存储结构 C. 索引存储结构 D. 散列存储结构 3．下列程序段 for(i=1;i<=n;i++) A[i,j]=0; 的时间复杂度是

A. O(1) B. O(0) C. O(1+n) D. O(n)

4. 若线性表中最常用的操作是取第i个元素和查找该元素的前驱，则采用最能节省时间的存储方式是 A. 顺序表 B. 单链表 C. 双链表 D. 循环链表

5．在n个结点的顺序表中删除一个结点，至少要移动的结点个数为 A. n B. 0 C. n/2 D. 1

6．在一个单链表中，若删除*p结点的后继结点，则执行操作

A. q=p->next;p->next=q->next;free(q); B. p=p->next;p->next=p->next->next;free(p);

C. p->next=q->next;free(p->next); D. p=p->next->next;free(p->next);

7．在一个单链表中，已知*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 ;

8．设指针p指向双链表的某一结点，则双链表结构的对称性可以用下面的操作来反映

A. p->prior->next=p->next->next; B. p->prior->prior=p->next->prior;

C. p->prior->next=p-> next->prior; D. p->next->next= p->prior->prior;

9．如果以链栈为存储结构，则出栈操作时

A．必须判栈满 B．必须判别栈空 C. 判别栈中元素类型 D. 不必作任何判别

10．设有一个顺序栈，6个元素1、2 、3、4、5、6依次入栈，如果6个元素出栈的顺序是2、3、4、6、5、1，则

栈的容量至少应该是 A．2 B．3 C. 5 D. 6

11．设一个栈的输入序列为A，B，C，D，则借助一个栈所得到的输出序列不可能是

A．A，B，C，D B．D，C，B，A C. A，C，D，B D. D，A，B，C

12．循环队列A[O..m-1]存放其元素值，用front和rear分别表示队头及队尾，则循环队列满的条件是 A．(Q.rear+1)％m==Q.front B．Q.rear==Q.front+1

C．Q.rear+l=Q.front D．Q.real==Q.front 13．循环队列A[0．．m—1]存放其元素值，用front和rear分别表示指向队头及队尾元素的指针，则当前队列中的

元素数是

A．(rear-front+1+m)％m B．(rear-front+1)

C．(rear-front+m)％m +1 D．(rear-front+1+m)％m

14．稀疏矩阵一般的压缩存储方法有两种，它们是用

A．二维数组和三维数组 B．三元组和散列表 C．三元组和十字链表 D．哈希表和十字链表 15．对矩阵压缩存储是为了

A.方便运算 B.节省空间 C.方便存储 D.提高运算速度

16． 二维数组A的每个元素是由6个字符组成的串，其行下标i=0，l，?，8，列下标为j=1，2．?．10。设每个字符占一个字节,若按行先存储，元素A[8，5]的起始地址与A按列存储时起始地址相同的元素是

A．A[8，5] B．A[3，10] C．A[5，8] D．A[0，9] 17．字符串通常采用的两种存储方式是

A. 散列存储和索引存储 B. 索引存储和链式存储

C. 顺序存储和链式存储 D. 散列存储和顺序存储

18．将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为

2

1，则编号为49的结点的左孩子编号为

A. 98 B. 99 C. 50 D. 48

19．对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其 左孩子的编号小于其右孩子的编号，则可采用遍历方式是 A.先序 B.中序 C.后序 D.层次遍历 20．中序表达式A*(B+C)／(D-E+F)的后序表达式是 A．A*B+C/D-E+F B．AB*C+D/E-F C．ABC+*DE-F+/ D．ABCDEF*+/-+

21．有64个结点的完全二叉树的深度为

A. 8 B. 7 C. 6 D.5

22．某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是

A. 空或只有一个结点 B.高度等于其结点数 C. 任一结点无左孩子 D.任一结点无右孩子 23．下面的说法中正确的是

(1)任何一棵二叉树的叶子节点在三种遍历中的相对次序不变。 (2)按二叉树定义，具有三个节点的二叉树共有6种。 A．(1)，(2) B．(1) C．(2) D．(1)，(2)都错

24．二义树在线索化后，仍不能有效求解的问题是

A. 先序线索二叉树中求先序后继 B. 中序线索二叉树中求中序后继 C. 中序线索二叉树中求中序前趋 D. 后序线索二又树中求后序后继

25．无向图G=(V E)，其中V={a，b，C，d，e，f}，E={，，，，，，}，对该图进行深度优先排序，得到的顶点序列正确的是 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, b 26．以下说法不正确的是

A．无向图中的极大连通子图称为连通分量

B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D．有向图的遍历不可采用广度优先搜索 27．拓扑排序只能用于

A. 有向图 B. 有向无环图 C. 无向图 D. 有向连通图 28．设图G用邻接表存储，则拓扑排序的时间复杂度为 A．D(n) B．O(n+e) C．O(n×n) D．0(n×e)

29．.对有18个元素的有序表作二分查找，则查找A[3]的比较序列的下标为 A. 1，2，3 B. 9，5，2，3 C．9，5，3 D. 9，4，2，3 30．关于散列法查找说法正确的是

A．采用链地址解决冲突时，查找一个元素的时间是相同的

B．采用链地址解决冲突时，若规定插入总是在链首，则插入任一个元素的时间是相同的 C．采用链地址解决冲突容易引起聚集现象 D．再散列不易产生聚集 31．散列表的平均查找长度

A．与处理冲突方法有关而与表的长度无关 B．与处理冲突方法无关而与表的长度有关 C．与处理冲突方法有关而与表的长度有关 D．与处理冲突方法无关而与表的长度无关

32．设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字

为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是

3

A．8 B．3 C．5 D．9 33．对散列文件，以下说法错误的是

A．散列文件插入、删除方便，不需要索引区且节省存储空间 B．散列文件只能按关键字随机存取且存取速度快

C．经过多次插入、删除后，可能出现溢出桶满的情况 D．散列文件顺序存取方便

34．在平衡二叉树中插入一个结点后引起了不平衡，设最低(最接近于叶子)的不平衡点是A，并已知A的左、右孩

子的平衡因子分别为-1和0，则应进行的平衡旋转是 A．LL型 B．LR型 C．RL型 D．RR型

35．.在平衡二叉树中插入一个结点后造成了不平衡，设离插入点最近的不平衡结点A的平衡因子为-2，并已知插入

前A的左孩子的平衡因子为0，右孩子的平衡因子为1，则应调整以使其平衡，所作的平衡旋转是 A. LL型 B. LR型 C. RL型 D. RR型

36．.在n个结点且为完全二叉树的二叉排序树中查找一个键值，其平均比较次数的数量级为 A. O(n) B. O(log2

2n) C. O(nlog2n) D. O(n) 37．下面关于B-树和B+树的叙述中，不正确的结论是(A )。 A．B-树和B+树都能有效地支持顺序查找 B．B-树和B+树都能有效地支持随机查找 C．B+

-树和B树都是平衡的多叉树

D．B-树和B+树都可用于文件索引结构

38．在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是 A．G中有弧 B．G中有一条从Vi到Vj的路径 C．G中没有弧 D．G中有一条从Vj到Vi的路径 39．一个有n个顶点的无向连通图，它所包含的连通分量个数最多为 A．0 B．1 C．n D．n+l

40．任何一个无向连通图的最小生成树

A. 只有一棵 B. 有一棵或多棵 C. 一定有多棵 D. 可能不存在 41．关键路径是事件结点网络中

A．从源点到汇点的最长路径 B．从源点到汇点的最短路径 C．最长的回路 D．最短的回路

42．.下图的邻接表中，从顶点V1 出发采用深度优先搜索法遍历该图，则可能的顶点序列是

A. V1V2V3V4V5 B. V1V2V3V5V4 C. V1V4V3V5V2 D.V1V3V4V5V2 43．以下说法不正确的是

A．无向图中的极大连通子图称为连通分量

B．连通图的广度优先搜索中一般要采用队列来暂存刚访问过的顶点 C．图的深度优先搜索中一般要采用栈来暂存刚访问过的顶点 D．有向图的遍历不可采用广度优先搜索

44．.对记录序列(314，298，508，123，486，145)依次按个位和十位进行两趟基数排序之后所得结果为

A. 123，145，298，314，486，508 B. 508，314，123，145，486，298

C. 486，314，123，145，508，298

D. 298，123，508，486，145，314

4

45．排序算法中，算法可能会出现下面情况：初始数据有序时，花费的时间反而最多的是

A. 堆排序 B. 冒泡排序 C. 快速排序 D. SHELL排序

46．对于关键字序列(12，13，11，18，60，15，7，18，25，100)，用筛选法建堆，则开始结点的键值必须为 A. 100 B. 12 C. 60 D. 15

47．下列排序算法中，某一趟结束后未必能选出一个元素放在其最终位置上的是

A. 堆排序 B. 冒泡排序 C. 快速排序 D. 直接插入排序

48．已知数据表A中每个元素距其最终位置不远，则采用最节省时间的排序算法是

A. 堆排序 B. 希尔排序 C. 快速排序 D. 插入排序 49．下列排序算法中，在待排序数据已基本有序时，效率最高的排序方法是 A．插入 B．选择 C．快速 D．堆

50．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 A．n B．2n-1 C．2n D．n-1

二、填空题

1．算法的五个重要特性包括（有穷性 ）、确定性、可行性、输入和输出。抽象数据类型是指一个（数学模型 ）以及定义在该模型上的一组操作。

2．在线性结构中，开始结点没有结点，最后一个元素没有（后继）结点。线性表的逻辑结构是线性结构，其所含结点的个数称为线性表的（长度）。对一个线性表分别进行遍历和逆置运算，其最好的时间复杂度量级均为（O(n)）。 3．数据的逻辑结构包括线性结构、树形结构、图形结构、（集合类型）。从存储结构的概念上讲，顺序表是（线性 表 ）的顺序存储结构。若线性表中最常用的操作是取第i个元素和查找该元素的前驱，则采用的存储方式最能 节省时间的是（顺序表）。若最常用的操作是插入和删除第i个元素，则采用的存储方式最能节省时间的是（单

链表 ）。 4．为了便于在单链表中进行操作，常在链表中设置（头结点）。在一个不带头结点的单链表中，在表头插入或删除与在其他位置插入或删除操作过程不同，需要修改（头指针）。在单链表中设置头结点的作用是（便于操作），无论链表是否为空。使（头指针）均不为空。对于双向链表，在两个结点之间插入一个新结点需修改的指针共有（4个），单链表为（2个）。 5．已知栈的输入序列为1，2，3?．，n，输出序列为a1，a2，?，an，a2=n的输出序列共有（n-1）种输出序列。 队列的特性是先入先出，栈的特性是（后入先出）。如果以链栈为存储结构，则出栈操作时必须判别（栈空 )。

与顺序栈相比，链栈有一个明显的优势是( 不易出现栈满 )。

6．循环队列采用数组data[1．．n]来存储元素的值，并用front和rear分别作为其头尾指针。为区分队列的满和

空，约定：队中能够存放的元素个数最大为（n-l），也即至少有一个元素空间不用，则在任意时刻，至少可以知道一个空的元素的下标是（front） ；入队时，可用语句（rear=rear+1%n）求出新元素在数组data中的下标。 7．数组A[l..10，1..10]的每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续的内存单元中， 则元素A[5，6]的地址为（1270）。

8．两个串相等的充要条件是，两个串的长度相等，且其所对应各个位置的（字符）也相等。稀疏矩阵一般的压缩 存储方法有两种，它们是（三元组顺序表）和十字链表。

9．若某二叉树有20个叶子结点，有30个结点仅有一个孩子，则该二叉树的总结点数是（69）。已知二叉树有 50个叶子结点，则该二叉树的度为2的结点数是（51 ），该二叉树的总结点数至少是（99）。一棵二叉树L的高 度为h，所有结点的度或为0，或为2，则这棵二叉树最少的结点数为( 2h-1 )。 10．树t的存储结构为二叉链表bt，树t中的一个叶子结点在bt中满足条件（bt->lchild<>null&& bt->rchild<>null;）。 树t中的非叶子结点在bt中满足条件是（bt->lchild<>null|| bt->rchild<>null）。在有n个结点的二又链表中，值 为非空的链域的个数为（ n-1 ）个。在有n个叶子结点的哈夫曼树中，总结点数是（2n-1）。在树形结构中，根结点数只有（1个），其余每个结点有且仅有一个元素（前驱）结点。

11．具有10个顶点的无向图，边的总数最多为(45)。有向图G用邻接矩阵A存储，则顶点i的入度等于A中（ 第 i列1的元素之和 ）。对于含n个顶点和e条边的图，采用邻接矩阵表示的空间复杂度为（ O(n2) ）。连通图 是指图中任意两个顶点之间（都连通的无向图 ）。一个有n个顶点的无向连通图，它所包含的连通分量个数最

5

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