数据结构复习题.docx
《数据结构复习题.docx》由会员分享，可在线阅读，更多相关《数据结构复习题.docx（18页珍藏版）》请在冰点文库上搜索。
数据结构复习题
一、选择题
1．数据结构被形式地定义为（K，R），其中K是①的有限集合，R是K上的②有限集合。
①A．算法B数据元素C数据操作D逻辑结构
②A操作B映象C存储D关系
2．链表不具备的特点是。
A可随机访问任一结点B插入删除不需要移动元素C不必事先估计存储空间D所需空间与其长度成正比
3．若某表最常用的操作是在最后一个结点之间插入一个结点或删除最后一个结点，则采用存储方式最节省运算时间。
A单链表B给出表头指针的单循环链表C双链表D带头结点的双循环链表
4．栈的特点是①，队列的特点是②。
A先进先出B先进后出
5．一个栈的进栈序列是A，B，C，D，E，则栈的不可能的输出序列是。
A．EDCBAB。
DECBAC。
DCEABD。
ABCDE
6．串是一种特殊的线性表，其特殊性体现在。
A可以顺序存储B数据元素是一个字符C可以链接存储D数据元素可以是多个字符
7．一维数组和线性表的区别是。
A前者长度固定，后者长度可变B后者长度固定，前者长度可变C两者长度均固定D两者长度均可变
8.稀疏矩阵一般的压缩存储方法有两种，即C。
A．二维数组和三维数组B。
三元组和散列C。
三元组和十字链表D。
散列和十字链表
9．在线索化二叉树中，t所指结点没有左子树的充要条件是 B 。
A．t->left==NULL
B.t->ltag==1
C.t->ltag==1且t->left==NULL
D．以上都不对
10．设高度为h的二叉树上只有度为0和度为2 的结点， 则此类二叉树中所包含的结点数至少为 B 。
A．2hB.2h-1C.2h+1D.h+1
11．如图所示二叉树的中序遍历序列是 B 。
A．abcdgerB.dfebagcC.dbaefcgD.defbagc
12．某二叉树的先序遍历序列和后序列正好相反，则该二叉树一定是 D 。
A．空或只有一个结点
B．完全二叉树
C．二叉排序树
D．高度等于其结点数
13．在一个图中，所有顶点的度数之和等于所有边数的C倍。
A1/2B1C2D4
14．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的B倍。
A1/2B1C2D4
17、一个有n个顶点的无向图最多有C条边。
AnBn（n-1）Cn（n-1）/2D2n
15、具有4个顶点的无向完全图有A条边。
A6B12C16D20
16、采用邻接表存储的图的深度优先遍历类似于二叉树的A。
A先序遍历B中序遍历C后序遍历D按层遍历
17、采用邻接表存储的图的广度优先遍历类似于二叉树的D。
A先序遍历B中序遍历C后序遍历D按层遍历
18、顺序查找法适合于存储结构为B的线性表。
A．散列存储B。
顺序存储或链式存储C。
压缩存储D。
索引存储
19、对线性表进行折半查找时，要求线性表必须C。
A．顺序存储B。
以链接方式存储C。
以顺序存储，并且结点按关键字有序排列。
D．以链接方式存储，并且结点按关键字有序排列。
21．数据结构在计算机内存中的表示是指。
A数据的存储结构B数据结构C数据的逻辑结构D数据元素之间的关系
22．某线性表最常用的操作是在最后一个结点之后插入一个结点或删除一个结点，故采用存储方式最节省运算时间。
A单链表B仅有表头结点的单循环链表C双链表D仅有表尾指针的单循环链表
23．如果最常用的操作是取第i个结点及其前驱，则采用存储方式最节省运算时间。
A单链表B双链表C单循环链表D顺序表
24．栈和队列的共同点是。
A都是先进后出B都是先进先出C只允许在端点处插入和删除元素D没有共同点
25．空串与空白串是相同的，这种说法。
A正确B不正确
26．数组元素之间的关系，。
A是线性的B是树形的C既是线性的又是树形的D既不是线性的又不是树形的
27．树最适合用来表示C。
A．有序数据元素
B．无序数据元素
C．元素之间具有分支层次关系的数据
D．元素这间无联系的数据
28.如果T2是由有序树T1转换而来的二叉树，那么T1中结点的先序就是T2中结点的 A 。
A．先序
B．中序
C．后序
D．层次序
29、具有6个顶点的无向图至少应该有A条边才能确保是一个连通图。
A5B6C7D8
30、采用邻接表存储的图的深度优先遍历类似于二叉树的A。
A先序遍历B中序遍历C后序遍历D按层遍历
31、采用邻接表存储的图的广度优先遍历类似于二叉树的D。
A先序遍历B中序遍历C后序遍历D按层遍历
32、顺序查找法适合于存储结构为B的线性表。
A．散列存储B。
顺序存储或链式存储C。
压缩存储D。
索引存储
33、对线性表进行折半查找时，要求线性表必须C。
A．顺序存储B。
以链接方式存储C。
以顺序存储，并且结点按关键字有序排列。
D．以链接方式存储，并且结点按关键字有序排列。
34、二叉树为二叉排序树的充分必要条件是其中任一结点的值大于其左儿子的值，小于其右儿子的值，这种说法B。
A．正确B。
不正确
35．算法分析的目的是①，算法分析的两个主要方面是②。
①A找出数据结构的合理性B研究算法中的输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性
②A空间复杂度和时间复杂度B正确性和简明性C可读性与文挡性D数据复杂性和程序复杂性
36．与单链表相比，双链表的优点之一是。
A插入、删除操作更简单B可以进行随机访问C可以省略表头指针和表尾指针D顺序访问相邻结点更灵活。
37．一个队列的入队序列是1，2，3，4，则队列的输出序列是。
A．4，3，2，1B。
1，2，3，4C。
1，4，3，2D。
3，2，4，1
38．是“abcd321ABCD”的子串。
A．abcdB.321ABC.”abcABC”D.”21AB”
39．一个n*n的对称矩阵，如果以行序或列序放入内存，则容量为。
A.n*nB.n*n/2C.n*（n-1）/2D（n+1）*（n+1）/2
40．二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法 B 。
A．正确
B．错误
41．深度为15的二叉树至多有 个结点。
42、一个有19个顶点的无向图最多有条边。
43、具有n个顶点的无向图至少应该有c条边才能确保是一个连通图。
AnBn+1Cn-1Dn/2
44、顺序查找法适合于存储结构为B的线性表。
A．散列存储B。
顺序存储或链式存储C。
压缩存储D。
索引存储
45、对线性表进行折半查找时，要求线性表必须C。
A．顺序存储B。
以链接方式存储C。
以顺序存储，并且结点按关键字有序排列。
D．以链接方式存储，并且结点按关键字有序排列。
46.下列各选项中属于逻辑结构的是B。
A.哈希表B.有序表C.单链表D.顺序表
47.对于数据结构，以下叙述中不正确的是B。
A.数据的逻辑结构与数据元素本身的形式和内容无关
B.数据的逻辑结构是数据的各数据项之间的逻辑关系
C.数据元素是数据的基本单位
D.数据项是数据的最小单位
48.某算法的时间复杂度为O（n2），表明该算法的C。
A.问题规模是n2B.执行时间等于n2
C.执行时间与n2成正比D.问题规模与n2成正比
4.通常在单链表中增加一个头节点，其目的是为了C。
A.使单链表至少有一个节点B.标识表节点中首节点的位置
C.方便单链表运算的实现D.说明单链表是线性表的链式存储
49.删除某个双链表中的一个节点（非首、尾节点），需要修改B个指针域。
A.1B.2C.3D.4
50.栈和队列是两种不同的数据结构，但它们中的元素具有相同的B。
A.抽象数据类型B.逻辑结构
C.存储结构D.运算
51.元素a、b、c、d、e依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有的元素都出栈，则所有可能的出栈序列中，以元素d开头的序列有哪些？
52.设环形队列中数组的下标是0～N-1，其头尾指针分别为f和r（f指向队列中队头元素的前一个位置，r指向队尾元素的位置），则其元素个数为D。
A.r-fB.r-f-1C.（r-f）％N+1D.（r-f+N）％N
53.已知循环队列存储在一维数组A[0..n-1]中，且队列非空时front和rear分别指向队头元素和队尾元素。
若初始时队列空，且要求第一个进入队列的元素存储在A[0]处，则初始时front和rear的值分别是B。
A.0，0B.0，n-1C.n-1，0D.n-1，n-1
54.对于n阶（n≥2）对称矩阵，采用压缩方法以行序优先存放到内存中，则需要A个存储单元。
A.n（n+1）/2B.n（n-1）/2C.n2D.n2/2
55.一棵度为4的树T中，若有18个度为4的节点，10个度为3的节点，1个度为2的节点，9个度为1的节点，则树T的叶子节点个数是。
56.一个具有n（n≥2）个顶点的无向图，至少有①B个连通分量，最多有②D个连通分量。
A.0B.1C.n-1D.n
57.含有n（n≥2）个顶点的无向图的邻接矩阵必然是一个A。
A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵
58.设有98个元素的有序顺序表，用折半查找时，成功时最大的比较次数是。
59.已知一个长度为16的顺序表，其元素按关键字有序排序，若采用折半查找法查找一个不存在的元素，则平均关键字比较的次数是A。
A.70/17B.70/16C.60/17D.60/16
60.以下关于m阶B-树的叙述中正确的是C。
A.每个节点至少有两棵非空子树
B.树中每个节点至多有m/2-1个关键字
C.所有叶子节点均在同一层上
D.当插入一个关键字引起B-树节点分裂时，树增高一层
61.为提高散列（哈希）表的查找效率，可以采取的正确措施是D。
Ⅰ.增大装填（载）因子
Ⅱ.设计冲突（碰撞）少的散列函数
Ⅲ.处理冲突（碰撞）时避免产生聚集（堆积）现象
A.仅ⅠB.仅ⅡC.仅Ⅰ、ⅡD.仅Ⅱ、Ⅲ
62.数据序列{15,16,17,4,5,6,20,1,2}只能是C的两趟排序后的结果。
A.简单选择排序B.冒泡排序C.直接插入排序D.堆排序
63.用某种排序方法对顺序表{22,78,21,58,15,27,69,35,19}进行排序，各趟元素序列的变化情况如下：
（1）{22,78,21,58,15,27,69,35,19}
（2）{19,15,21,22,58,27,69,35,78}
（3）{15,19,21,22,35,27,58,69,78}
（4）{15,19,21,22,27,35,58,69,78}
则所采用的排序方法是B。
A.简单选择排序B.快速排序C.直接插入排序D.归并排序
64.若线性表最常用的运算是存取第i个元素及其前趋元素的值，则采用D存储方式节省时间。
A.单链表B.双链表
C.单循环链表D.顺序表
65.在一个具有n个结点的有序单链表中插入一个新结点使得仍然有序，其算法的时间复杂度为D。
A.O（log2n）B.O
（1）
C.O（n2）D.O（n）
66.一个n×n的对称矩阵A，如果采用以列优先（即以列序为主序）的压缩方式存放到一个一维数组B中，则B的容量为C。
A.n2B.
C.
D.
67.若一棵3次树中有a个度为1的节点，b个度为2的节点，c个度为3的节点，则该树中有D个叶子节点。
A.1+2b+3cB.a+2b+3cC.2b+3cD.1+b+2c
68.一棵完全二叉树中有401个叶子节点，则至少有个节点。
69.在含有n个结点的线索二叉树中，线索的数目为C。
A.n-1B.nC.n+1D.2n
73.有一个长度为12的有序表R[0..11]，按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为B。
A.35/12B.37/12C.39/12D.43/12
74.数据序列{8,9,10,4,5,6,20,1,2}只能是A的两趟排序后的结果。
A.直接插入排序B.冒泡排序C.简单选择排序D.堆排序
75.有一些内排序算法，在最后一趟排序结束前可能所有的数据都没有放在其最终的位置上，这些排序算法是C。
Ⅰ.希尔排序Ⅱ.快速排序Ⅲ.归并排序Ⅳ.堆排序
A.仅Ⅰ、ⅡB.仅Ⅱ、ⅢC.仅Ⅰ、ⅢD.仅Ⅰ、Ⅱ、Ⅳ
76.在以下排序方法中，关键字比较的次数与元素的初始排列次序无关的是D。
A.快速排序B.冒泡排序C.插入排序D.简单选择排序
77．若串S=“CHINAFZ”，其子串的个数是
78．一维数组和线性表的区别是A。
A前者长度固定，后者长度可变B后者长度固定，前者长度可变C两者长度均固定D两者长度均可变
二、解答题。
1、已知某二叉树的先序遍历序列是ABDGCEFH，中序遍历序列是DGBAECHF，给出它的后序遍历序列。
GDBEHFCA
2、设给定权集W={2，3，4，7，9}，请构造出关于W的一棵哈夫曼树，并求出带权路径长度WPL。
3、有一份电文中共使用5个字符A，B，C，D，E，它们出现的频率依次为4，7，5，2，9，请画出对应的哈夫曼树，并求出每个字符的哈夫曼编码。
A：
001B：
10C：
01D：
000E：
11
4.简要叙述堆和二叉排序树的区别，并给出关键字序列{23,26,32,71,48,40,99,75,53,87}调整为大根堆后的结果（直接画出调整后的大根堆）。
5.按关键字13、24、37、90、53的次序构造一棵平衡二叉树，回答以下问题：
（1）该平衡二叉树的高度是多少？
（2）其根节点的关键字是什么？
（3）其中经过了哪些调整（指出调整名称和次数）。
答：
如图1所示是构造平衡二叉树的过程，回答问题如下：
（1）该平衡二叉树的高度是3。
（2）根节点的关键字是24。
（3）其中经过了一次RR调整和一次RL调整。
图1构造平衡二叉树的过程
6.一棵二叉排序树按先序遍历得到的关键字序列为：
（70,38,30,47,40,48,82,60,95,100）。
回答以下问题：
（1）画出该二叉排序树。
（2）求在等概率条件下的查找成功的平均查找长度。
7.有一个无向带权图如图2所示，采用Dijkstra算法求顶点0到其他顶点的最短路径和最短路径长度，要求给出求解过程（即给出求最短路径中各步骤的S、dist和path值）。
图2一个无向图
8.将整数序列{14,15,27,23,14,30,6}中的数依次插入到一棵空的二叉排序树中，试构造相应的二叉排序树，要求用图形给出构造过程，不需编写程序。
9．求算法的时间复杂度为多少类型的题目？
10.指出以下关于堆及堆排序叙述的正确性。
（10分）
（1）任何一棵完全二叉树一定是一个堆。
（2）在大根堆中，最大的元素在根节点中，最小的元素一定在某个叶子节点中。
（3）在大根堆中，堆中任一节点的关键字均大于它的左、右孩子的关键字。
（4）在一个小根堆中，从根节点到某个叶子节点的路径上的所有结点的关键字正好构成一个递增序列。
（5）堆排序在最坏情况下的时间复杂度为O（n2）。
（6）堆排序是一种与初始排序序列无关的排序方法。
三、算法设计题
1.设计一个算法，将一个带头结点的数据域依次为a1，a2，…，an（n≥3）的双链表的所有结点逆置，即第一个结点的数据域变为an，即第二个结点的数据域变为an-1，…，最后一个结点的数据域为a1。
双链表中每个结点的类型如下：
typedefstructnhode
{ElemTypedata;
structnode*prior,*next;
}DLinkList;
解：
采用前插法建表，算法如下：
voidReverse（DLinkList*&h）
{DLinkList*p=h->next,*q=p->next;
h->next=NULL;
while（p!
=NULL）
{p->next=h->next;/*将p所指结点插入到头结点之后*/
p->prior=h;
p=q;
q=p->next;
}
}
2.假设二叉树采用二叉链存储结构进行存储，每个结点有data、lchild和rchild三个域。
设计一个算法，计算一棵给定二叉树中节点值为x的节点个数（注意在一棵二叉树中可能存在相同节点值的节点），并给出你所写出的算法的时间复杂度（设二叉树中结点个数为n）。
解：
对应的递归算法如下：
intFindSum（BTNode*b）
{if（b==NULL）return0;
if（b->data==x）
return（1+FindSum（b->lchild）+FindSum（b->rchild））;
else
return（FindSum（b->lchild）+FindSum（b->rchild））;
}
3.假设一个不带权的无向图采用邻接表G进行存储，设计一个算法FindaPath（G,u,v,&has），判断该图中顶点u到顶点v是否连通，如果连通，has为1，否则has为0，在调用该算法之前has置初值为0。
解：
对应的算法如下：
intvisited[MAXV]={0};//全局变量
voidFindaPath（ALGraph*G,intu,intv,bool&has）
//has表示uv是否连通，初始时has为0
{intw;
ArcNode*p;
visited[u]=1;
p=G->adjlist[u].firstarc;//p指向u的第一条边
while（p!
=NULL）
{w=p->adjvex;//w为u的邻接顶点
if（w==v）//从u到v找到一条路径，说经u到v是连通的
{has=1;
return;
}
elseif（visited[w]==0）//若顶点未标记访问，则递归访问之
FindaPath（G,w,v,has）;//从顶点w出发继续查找
p=p->nextarc//找u的下一个邻接顶点
}
}
4．有一个线性表（a1,a2,…,an），采用带头节点的单链表L存储，设计一个就地算法将其所有元素逆置。
所谓就地算法是指算法的空间复杂度为O
（1）。
解：
对应的算法如下：
voidReverse1（LinkList*&L）
{LinkList*p=L->next,*q;//p指向开始节点
L->next=NULL;
while（p!
=NULL）
{q=p->next;
p->next=L->next;//将*p节点插入到新建链表的前面
L->next=p;
p=q;
}
}
5．假设二叉树采用二叉链存储结构，设计一个算法把一棵含有n个节点的二叉树b复制到另一棵二叉树t中。
解：
对应的递归算法如下：
voidCopy（BTNode*b,BTNode*&t）
{if（b==NULL）
t=NULL;
else
{t=（BTNode*）malloc（sizeof（BTNode））;
t->data=b->data;//复制一个根节点*t
Copy（b->lchild,t->lchild）;//递归复制左子树
Copy（b->rchild,t->rchild）；//递归复制右子树
}
}
6.假设一个不带权的有向图G采用邻接表存储，设计一个算法判断图G中是否存在顶点i到顶点j的边，若存在这样的边返回1，否则返回0。
解：
对应的算法如下：
intHasArc（AGraph*G,inti,intj）//判断图G中是否存在边
{ArcNode*p;
p=G->adjlist[i].firstarc;
while（p!
=NULL&&p->adjvex!
=j）
p=p->nextarc;
if（p==NULL）
return0;
else
return1;
}
7.设ha=（a1,a2,…,an）和hb=（b1,b2,…,bm）是两个带头结点的循环单链表，编写将这两个表合并为带头结点的循环单链表hc的算法。
答案：
voidMerge（LinkList*ha,LinkList*hb,LinkList*&hc）
{LinkList*p=ha->next;
hc=ha;
while（p->next!
=ha）//找到ha的最后一个节点*p
p=p->next;
p->next=hb->next;//将ha的最后一个节点的next指向hb的第一个数据节点
while（p->next!
=hb）p=p->next;//找到hb的最后一个节点*p
p->next=hc;//构成循环单链表
free（hb）；//释放hb单链表的头节点
}
8.有两个串s1和s2，设计一个算法求一个这样的串，该串中的字符是s1和s2中公共字符（不是子串关系）。
答案：
SqStringCommChar（SqStrings1,SqStrings2）
{SqStrings3;
inti,j,k=0;
for（i=0;i{for（j=0;jif（s2.data[j]==s1.data[i]）
break;
if（j{s3.data[k]=s1.data[i];
k++;
}
}
s3.length=k;
returns3;
}
9.编写一个算法，判断给定的二叉树是否是二叉排序树。
KeyTypepredt=-32768;
//predt为全局变量,保存当前节点中序前趋的值,初值为-∞
boolJudgeBST（BSTNode*bt）
{boolb1,b2;
if（bt==NULL）
returntrue;
else
{b1=JudgeBST（bt->lchild）;//判断左子树
if（!
b1||predt>=bt->key）/
升级会员 