数据结构复习题11doc.docx
《数据结构复习题11doc.docx》由会员分享，可在线阅读，更多相关《数据结构复习题11doc.docx（17页珍藏版）》请在冰点文库上搜索。
数据结构复习题11doc
一、选择题
1.数据结构被形式地定义为（K，R），其中K是数据元素的冇限集合,K
是K上的关系有限集合。
2.裢衷不具备的特点是可随机访问任一结点。
3.若某表最常用的操作是在最后一个结点之间插入一个结点或删除最后一个结点，则采用带头结点的双循环链表存储方式最节省运算时间。
4.栈的特点是_先进先出_，队列的特点是_先进后出_。
5.一个栈的进栈序列是A,B,C,D，E,则栈的不可能的输出序列是DCEAB。
A.EDCBAB。
DECBAC。
DCEABD。
ABCDE
6.串是一•种特殊的线性表，特殊性体现在数据元索是_•个字符。
7.一维数组和线性表的区别是者长度固定，G者长度可变。
8.稀疏矩阵一般的压缩存储方法有两种，即_三元组和十字链表_。
9.在线索化二叉树中，t所指结点没有左子树的充要条件是B。
A.t->left=NULL
B.t->ltag==l（P189）
C.t->ltag==l且t->left==NULL
D.以上都不对
10.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所钮
含的结点数至少为§_。
（P158的例题）
八.2hB.2h-lC.2h+lD.h+1
11.如图所示二叉树的中序遍历序列是_B。
（P173）
A.
abcdgerB.dfebagcC.dbaefcgD.defbagc
中序遍历：
先左子树，再根，再右子树先序遍历：
先根，再左，后右
序遍历：
先充，右，最根
12：
某二叉树的先序遍历序列和后序列正好相反，则该二叉树一定是_高度等于其结点数_。
此种情况只冇单只+树冰会出现
13.在一个图中，所宥顶点的度数之和等于所宥边数的1倍。
P205
（每条边分别作为两个邻接点的度各计了一次y
14.在一个有句图中，所有顶点的入度之和等于所有顶点的出度之和的&倍。
A1/2B1C2D4
17、一个有n个顶点的无向图最多有n（n-l）/2条边。
P205完全图[完全无向图包含n（n-l）/2条边，完全宥向图包含n（n-1）]
15、具有4个顶点的无向完全阁有生条边。
e=4（4-1）/2=6
16、采用邻接表存储的图的深度优¥遍历类似于二叉树的先序遍历。
17、釆用邻接表存储的图的广度优先遍历类似于二叉树的按层遍历。
P211图的遍历
18、顺序杳找法适合于存储结构为尘的线性表。
P250-251
A.散列存储Bo顺序存储或链式^手储Co压缩存储Do索引存储
19、对线性表进行折半查找时，要求线性表必须P251
A.顺序存储B。
以链接方式存储Co以顺序存储，并且结点按关键字有序
排列。
D.以链接方式存储，并且结点按关键字有序排列。
（折半杳找要求线性表是宥序表即表中的关键字宥序）
21.数据结构在计算机内存中的表示是指。
A数据的存储结构B数据结构C数据的逻辑结构D数据元素之问的关系
22.某线性表最常用的操作是在最后一个结点之后插入一个结点或删除一个结
点，故采用存储方式最节省运算吋间。
A单链表B仅宥表尖结点的单循环链表C双链表D仅宥表尾指针的单循环链豈
23.如果最常用的操作是取第i个结点及其前驱，则采用存储方式最节
省运算吋间。
八单链表B双链表C单循环链表D顺序表
24.栈和队列的共同点是。
A都是先进后出B都是先进先出C只允许在端点处插入和删除元素D没冇共同点
25.空串与空白串是相同的，这种说法。
八正确B不正确
26.数组元素之间的关系，。
A是线性的B是树形的C既是线性的又是树形的I）既不是线性的又不
是树形的
27.树最适合用来表示_Q。
八.有序数据元索B.无序数据元素
C.元素之间具宥分支M次关系的数据D.元素这间无联系的数据
28.如果T2是由冇序树T1转换而来的二叉树，那么T1屮结点的先序就是T2屮
结点的A。
A.先序B.屮序C.后序D.层次序
29.具有6个顶点的无向图至少应该有i条边方能确保是一个连通图。
A5B6C7D8
30.采用邻接表存储的阁的深度优先遍W类似于二叉树的么。
A先序遍历B中序遍历C后序遍历D按层遍历
31.采用邻接表存储的图的广度优先遍历类似于二叉树的1
A先序遍历B中序遍历C后序遍历D按层遍历
32.顺序杳找法适合于存储结构为尘的线性表。
A.散列存储Bo顺序存储或链式^手储Co压缩存储Do索引存储
33.对线性表进行折半查找时，要求线性表必须
A.顺序存储B。
以链接方式存储Co以顺序存储，并且结点按关键字有序
排列。
D.以链接方式存储，并且结点按关键字有序排列。
34.二叉树为二叉排序树的充分必要条件是其中任一结点的值大于其左儿子的值，小于其右儿子的值，这种说法呈。
A.正确Bo不正确
35.算法分析的口的是①，算法分析的两个主要方面是②。
①八找出数据结构的合理性B研究算法中的输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性
②A空间复杂度和时间复杂度B正确性和简明性C可读性与文挡性D数据复杂性和程序复杂性
36.与单链表相比，双链表的优点之一是。
A插入、删除操作更简单B可以进行随机访问C可以省略表头指针和表尾指针D顺序访问相邻结点更灵活。
37.一个队列的入队序列是1，2,3,4,则队列的输出序列是。
A.4，3，2，1Bo1,2，3，4Co1，4，3，2Do3，2，4，1
38.是“abcd321ABCD”的子串。
A.abedB.321ABC.”abcABC”D.”21八B”
39.一个n*n的对称矩阵，如來以行序或列序放入内存，则容量为。
A.n*nB.n*n/2C.n*（n_l）/2D（n+1）*（n+1）/2
40.二叉树按某种顺序线索化后，任一结点均有指向其前驱和后续的线索，这种说法B。
八.正确B.错误
41.深度为15的二叉树至多宥_个结点。
42.一个有19个顶点的无向阁最多有条边。
43.具有n个顶点的无句图至少应该有条边才能确保是一个连通图。
AnBn+1Cn-1Dn/2
44.顺序查找法适合于存储结构为生的线性表。
A.散列存储Bo顺序存储或链式^储Co压缩存储Do索引存储
45.对线性表进行折半查找时，耍求线性表必须么
A.顺序存储B。
以链接方式存储Co以顺序存储，并且结点按关键
字有序排列。
D.以链接方式存储，并且结点按关键字有序排列。
46.下列各选项屮属于逻辑结构的是j_。
A.哈希表B.有序表C.单链表D.顺序表
47.对于数据结构，以下叙述中不止确的是B。
八.数裾的逻辑结构与数裾元素木身的形式和内容无关
B.数据的逻辑结构是数据的各数据项之间的逻辑关系
C.数据元素是数据的基本单位
D.数据项是数据的最小单位
48.某算法的时间复杂度为0（n2）,表明该算法的C。
A.问题规模是n2B.执行吋间等于r?
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指向队尾元素的位置），则艽元素个数为_Q_。
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）对称矩阵，采用压缩方法以行序优先存放到内存中，则需要j个存储单元。
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个连通分量,最多有②JL个连通分量。
A.0B.1C.n-1D.n
57.含有n（n^2）个顶点的无向图的邻接矩阵必然是•一个A。
A.对称矩阵B.零矩阵C.上三角矩阵D.对角矩阵
58.设有98个元素的有序顺序表，用折半杏找时，成功时最大的比较次数
是O
59.己知一个长度为16的顺序表，其元素按关键字有序排序，若采用折半查找法查找一个不存在的元素，则平均关键字比较的次数是_A。
A.70/17B.70/16C.60/17D.60/16
60.以下关于阶B-树的叙述中止确的是C。
八.每个节点至少有两棵非空子树
B.树中每个节点至多有「〃//21-1个关键字
C.所有叶子节点均在同一层上
D.当插入一个关键字引起B-树节点分裂时，树增高一层
61.为提高散列（哈希）表的杳找效率，可以采取的止确措施是D。
I.增大装填（载）因子
II.设计冲突（碰撞）少的散列函数
III.处理冲突（碰撞）吋避免产生聚集（堆积）现象
A.仅IB.仅IIC.仅I、IID.仅II、III
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}
A.简单选择排序B.快速排序C.直接插入排序
64.若线性表最常用的运算是存取第/个元素及其前趋元素的值，则采用_存储方式节省吋间。
A.单链表B.双链表C.单循环链表D.顺序表
65.在一个具有n个结点的有序单链表屮插入一个新结点使得仍然有序，其算法
则所采用的排序方法是_B。
D.归并排序
的时间复杂度为D。
A.O（log2n）B.0
（1）C.0（n2）D.0（n）
66.—个nXn的对称矩阵A,如果采用以列优先（即以列序为主序）的压缩方式存放到一个一维数组B中，则B的容量为C。
A.n2B.iC.D.^121
222
67.若一棵3次树中有a个度为1的节点，6个度为2的节点，e个度为3的节
点，则该树中有个叶子节点。
A.1+2Zh-3cB.ei^2l^3cC.2/^3cD.1+Zh-2c
68.—棵完全二叉树屮有401个叶子节点，则至少有个节点。
69.在含有n个结点的线索二义树屮，线索的数目为j。
A.n-1B.nC.n+1D.2n
73.有一个K度为12的有序表R[0..11],按折半查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为_^_。
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.有一些|A）排序算法，在最后-•趟排序结束前可能所有的数据都没有放在其最终的位置上，这些排序算法是_C。
I.希尔排序II.快速排序III.归并排序IV.堆排序
A.仅I、IIB.仅II、IIIC.仅I、IIID.仅I、II、IV
76.在以下排序方法中，关键字比较的次数与元素的初始排列次序无关的是
D_o
A.快速排序B.冒泡排序C.插入排序D.简单选择排序
77.若串S=“CHINAFZ”，其子串的个数是15P99
（含有n个相互不同字符的串有n（n+1）/2个真子串。
）
78.一维数组和线性表的区别是A。
A前者K度固定，后者K度可变B后者K:
度固定，前者K:
度可变C两
者长度均固定D两者长度均可变
二、解答题。
1、已知某二叉树的先序遍W序列是ABDGCEFH，屮序遍历序列是DGBAECHF,给出它的后序遍历序列。
GDBEHFCA
2、设给定权集W=｛2,3,4,7,9｝，请构造出关于W的一棵哈夫曼树，并求出带权路径长度WPL。
P193
3、宥一份电文中共使用5个字符A，B，C，D，E,它们出现的频率依次为4,7,5,2,9,请阃出对应的哈夫曼树，并求出每个字符的哈夫曼编码。
A：
001B：
10C：
01D：
000E：
11
4.简要叙述堆和二叉排序树的区别，并给！
li关键字序列{23,26,32,71,48,40,99,75,53,87}调整为大根堆后的结果（直接画出调整后的大根堆）
5.按关键字13、24、37、90、53的次序构造一棵Y•衡二叉树，回答以下M
（1）该平衡二叉树的高度是多少？
（2）其•根节点的关键字是什么？
（3）其中经过Y哪些调整（指出调整名称和次数）。
答：
如图1所示是构造Y•衡二叉树的过程，回答闷题如下:
（1）该平衡二叉树的高度是3。
（2）根节点的关键字是24。
（3）其中经过了一次RR调整和一次RL调整。
（4）
图1构造平衡二叉树的过程
6.—棵二叉排序树按先序遍历得到的关键字序列为.（70,38,30,47,40,48,82,60,95,100）。
回答以下问题：
（1）画出该二叉排序树。
（2）求在等概率条件下的齊找成功的平均杳找长度。
7.有一个无向带权图如图2所示，采用Dijkstra算法求顶点0到其他顶点的最短路径和最短路径长度，要求给出求解过程（即给出求最短路径屮芥步骤的'
S、dist和path值）。
8.将整数序列｛14,15,27,23,14,30,6｝中的数依次插入到一棵空的二叉排序树屮，试构造相应的二义排序树，要求用图形给出构造过程，不需编写程序。
P256
9.求算法的时间复杂度为多少类型的题目？
10.指出以下关于堆及堆排序叙述的正确性。
（10分）
（1）任何一棵完全二X树一定是一个堆。
«—定是完荃二X树
（2）在大根堆中，最大的元素在根节点中，最小的元素一定在某个叶子节
点^中1。
（3）在大根堆中，堆中任一节点的关键字均大于它的左、心孩子的关键字。
（4）在一个小根堆中，从根节点到某个叶了节点的路径上的所有结点的关键字正好构成一个递增序列。
（5）堆排序在最坏情况下的时间复杂度为0（4）。
（6）堆排序是一种与初始排序序列无关的i序方法。
三、算法设计题
1.设计一个算法，将一个带头结点的数据域依次为a，，a2，…，a„（n^3）的双链表的所有结点逆置，即第一个结点的数据域变为即第二个结点的数据
域变为a。
-，，…，最后一个结点的数据域为a，。
双链表中每个结点的类型如下:
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-〉rchiId））;else
return（EindSum（b->lchiId）+EindSum（b->rchiId））;
}
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表示U4v是否连途，初始时has为0
{intw;
ArcNode氺p;visited[u]=l;
p=G->adjlist[u].firstarc;//p指向u的第一•条込
while（p!
=NULL）
{w=p->adjvcx;//w为u的邻接顶点
if（w==v）//从到一条路径，说经u到v是连
通的
{has二1;
return;
}
elseif（visited[w>=0）//若顶点未标记访问，则递归访问
之
FindaPath（G,w,v,has）;//从顶点wfli发继续查找
p=p->nextarc//找u的下一个邻接顶点
}
}
4.宥一个线性表（&屯…，&）,采用带头节点的单链表L存储，设计一个
就地算法将苏所有元索逆置。
所谓就地算法是指算法的空间复杂度为0
（1）。
解：
对应的算法如下：
voidReversel（LinkList氺&L）
{LinkList*p=L->next,*q;//p指向开始节点
L-〉next=NULL;while（p!
:
NUI丄）
{q=p->next;
p->ncxt=L->ncxt;//将印节点插入到新建链表的前面
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;//复制一个根节点*七
Copy（b->lchild,t->lchild）;//递!
J3!
复制左子树
Copy（b->rchild,t-〉rchild）;//速归复制右子树
}
}
6.假设一个不带权的有向图G采用邻接表存储，设计一个算法判断图G中是否存在顶点i到顶点j的边，若存在这样的边返回1,否则返回0。
解：
对应的算法如下：
intHasArc（AGraph*G,inti,intj）//判断图G中是否存在边〈i,j>
{ArcNode*p;
p=G-〉adjlist[i].firstarc;while（p!
=NULL&&p->adjvex!
=j）
p=p->nextarc;if（p==NULL）
return0;else
return1;
}
7.设ha=（al,a2,•••,an）和hb=（bl,b2,…，bm）是W个带头结点的循环单链表，编写将这两个表合并为带头结点的循环单链表he的算法。
答案：
voidMerge（LinkList*ha,LinkList*hb,LinkList*&hc）
{LinkList*p=ha-〉next;
hc=ha;
while（p->next!
=ha）//找到ha的最后一个节点*p
p=p->next;
据节点
while（p->next!
=hb）p=p->next;//找到hb的最后一个节点*pp->next=hc;//构成循环单链表
free（hb）；//释放hb单链表的头节点
}
8.有两个申si和心，设计一个算法求一个这样的串，该串屮的字符是si和s2中公共字符（不是子串关系）。
答案：
SqStringCommChar（SqStringsi,SqStrings2）
{SqStrings3;inti,j,k=0;
for（i=0;i{for（j=0;jif（s2.data[j]==sl.data[i]）break;
if（j{s3.data[k]=sl.data[i];
k++;
}
}
s3.length=k;returns3;
}
9.编写一个算法，判断给定的二叉树是否是二叉排序树。
KeyTypepredt=-32768;
//predt为全局变量，保存当前节点中序前趋的值,初值为
boolJudgeBST（BSTNode*bt）
{boolbl,b2;
if（bt==NULL）
returntrue;else
{bl=JudgeBST（bt->lchild）;//判断左子树if（!
bl||predt>=bt->key）//判断根节点
returnfalse;predt=bt->key;
b2=JudgeBST（bt->rchild）;//判断右子树returnb2;
}
升级会员 