e.i++f.i--g.a和c同时满足h.b和d同时满足
5.递归程序可借助于（c）转化为非递归程序。
a.线性表b.队列c:
栈d.数组
6.在下列数据结构中（c）具有先进先出（FIFO）特性，
（b）具有先进后出（FILO）特性。
a．线性表b．栈c．队列d．广义表
7.若对编号为1，2，3的列车车厢依次通过扳道栈进行调度，不能得到（e）的序列。
a:
1,2,3b:
1,3,2c:
2,1,3d:
2,3,1e:
3,1,2f:
3,2,1
8.在计算递归函数时，如不用递归过程，应借助于（b）这种数据结构。
a.线性表b.栈c.队列d.双向队列
9.若带头结点的链表只设尾结点指针。
下列选择中（c）最适用于队列。
a.单链表b.双向链表c.循环单链表d.双向循环链表
10.栈和队列的一个共同点是（c）。
a.都是先进先出b.都是先进后出
c.只允许在端点处插入和删除元素d.没有共同点
11.循环队列用数组A[0..m-1]存放其元素值，设头尾指针分别为front和rear，则当前队列中的元素个数是（c）。
a.rear-front-1b.rear-front+1
c.（rear-front+m）%md.rear-front
12.如下关于串的陈述中，正确的是（a,c）。
a.串是数据元素类型特殊的线性表b.串中的元素是字母
c.串中若干个元素构成的子序列称为子串d.空串即为空格串
13.对字符串s=’data-structure’执行操作replace（s,substring（s,6,8）,’bas’）
的结果是（b）。
a:
‘database’b:
‘data-base’c:
‘bas’d:
‘data-basucture’
14.对广义表A=（（a,（b））,（c,（））,d）执行操作gettail（gethead（gettail（A）））
的结果是：
（b）。
a:
（）b:
（（））c:
dd:
（d）
15.假设用于通讯的电文仅由6个字符组成，字母在电文中出现的频率分别为7,19,22,6,32,14。
若为这6个字母设计哈夫曼编码（设生成新的二叉树的规则是按给出的次序从左至右的结合，新生成的二叉树总是插入在最右），则频率为7的字符编码是（g），频率为32的字符编码是（c）。
a:
00b:
01c:
10d:
11
e:
011f:
110g:
1110h:
1111
16.对二叉排序树（c）可得到有序序列。
a:
按层遍历b:
前序遍历c:
中序遍历d:
后序遍历
17.设一棵二叉树BT的存储结构如下:
12345678
lchild23006000
dataABCDEFGH
rchild05408700
其中lchild，rchild分别为结点的左、右孩子指针域，data为结点的数据域。
则
该二叉树的高度为（d）；
第3层有（a）个结点（根结点为第1层）。
a．2b.3c.4d.5
18.先序遍历图示二叉树可得到（a）的序列。
a）ABHDEFICG
b）HBEDFIACG
c）HEIFDBGCA
（A）
／＼
（B）（C）
／＼＼
（H）（D）（G）
／＼
（E）（F）
＼
（I）
19.在有n个结点的二叉树的二叉链表表示中，空指针数（b）。
a.不定b.n+1c.nd.n-1
20.若某二叉树有20个叶子结点，有20个结点仅有一个孩子，则该二叉树的总结点数是（c）。
a．40b.55c.59d.61
21.已知某二叉树的先序遍历次序为abcdefg中序遍历次序为badcgfe，
则该二叉树的后序遍历次序为（c）。
层次遍历次序为（a）。
a:
abcdefgb:
cdebgfac:
bdgfecad:
edcgfba
.22.图示的三棵二叉树中（c）为最优二叉树。
A）B）C）
ca
27
abcddb
752445
abcd
7524
23.已知某二叉树的后序遍历和中序遍历次序分别为DBFGECA和BDACFEG。
则其先序遍历次序为（b），层次遍历次序为（a）。
a.abcdefgb.abdcefgc.abcdfegd.abcdegf
24.已知某树的先根遍历次序为abcdefg后根遍历次序为cdebgfa。
若将该树转换为二叉树,其后序遍历次序为（d）。
a.abcdefgb.cdebgfac.cdegbfad.edcgfba
25.设x和y是二叉树中的任意两个结点，若在先根序列中x在y之前，而在后根序列中x在y之后，则x和y的关系是（c）。
a.x是y的左兄弟b.x是y的右兄弟
c.x是y的祖先d.x是y的子孙
26.用三叉链表作二叉树的存储结构，当二叉树中有n个结点时，有（d）个空指针。
a.n-1b.nc.n+1d.n+2
27.对一棵完全二叉树进行层序编号。
则编号为n的结点若存在右孩子,其位序是（d）。
编号为n的结点若存在双亲,其位置是（a）。
a:
n/2b:
2nc:
2n-1d:
2n+1e:
nf:
2（n+1）
28.设森林F中有三棵树，第一、第二和第三棵树的结点个数分别为m1、m2和m3，则与森林F对应的二叉树根结点的右子树上的结点个数是（d）。
a.m1b.m1+m2c.m3d.m2+m3
29.下列二叉树中，（a）可用于实现符号不等长高效编码。
a:
最优二叉树b:
次优查找树c:
二叉平衡树d:
二叉排序树
30.邻接表存储结构下图的深度优先遍历算法类似于二叉树的（ a）遍历。
a.先根 b中根 c.后根 d.层次
31.设无向图G=（V,E）和G’=（V’,E’），若G’是G的生成树，则下面不正确的说法是（b）。
a.G’是G的子图 b.G’是G的连通分量
c.G’是G的无环子图 d.G’是G的极小连通子图且V’=V
32.任何一个连通图的最小生成树（b）。
a．只有一棵b有一棵或多棵c.一定有多棵d.可能不存在
33.已知某无向图的邻接表如下所示；
（e）是其原图。
（c）是按该邻接表遍历所得深度优先生成树。
（d）是按该邻接表遍历所得广度优先生成树。
0a321
1b30
2c430
3d5210
4e52
5f43
a.abb.abc.ab
cdcdcd
efefef
d.abe.abf.ab
cdcdcd
efefef
34.深度优先遍历图使用了数据结构（b），而广度优先遍历图使用了数据结构（c）。
a）数组b）栈c）队列d）线性表
35已知某有向图的邻接表存储结构如图所示。
0E21∧
1D034∧
2C
4
3B120∧
4A2∧
36.根据存储结构依教材中的算法其深度优先遍历次序为（d）。
广度优先遍历此序为（c）。
各强连通分量的顶点集为（h）。
a.abcde.B.edcba.C.ecdab.d.ecadb.
e.abc及edf.bc及aedg.ab及cedh.ac及bed
37.下列查找方法中（a）适用于查找单链表。
a.顺序查找B）折半查找C）分块查找D）hash查找
38.下列算法中（c）适用于求图的最小代价生成树。
（b）能对图作广度优先遍历。
a.DFS算法b.BFS算法c.Prim算法d.Dijkstra算法
39.关键路径是指在只有一个源点和一个汇点的有向无环网中源点至汇点（c）的路径。
a.弧的数目最多b.弧的数目最少c.权值之和最大d.权值之和最小
40.哈希表的查找效率取决于（d）。
a.哈希函数b.处理冲突的方法。
C.哈希表的装填因子。
D.以上都是
41.在Hash函数H（k）=kMODm中，一般来说，m应取（ c）。
a.奇数b.偶数c.素数d.充分大的数
42.在顺序表查找中，为避免查找过程中每一步都检测整个表是否查找完毕，可采用a方法。
a.设置监视哨b.链表存贮c.二分查找d.快速查找
43.静态查找表和动态查找表的区别在于（b）。
a.前者是顺序存储，而后者是链式存储
b前者只能进行查找操作，而后者可进行查找、插入和删除操作
c.前者只能顺序查找，而后者只能折半查找
d.前者可被排序，而后者不能被排序
44.在一个含有n个元素的有序表上进行折半查找，找到一个元素最多要进行（b）次元素比较。
a．log2（n）b.log2（n）+1c.log2（n+1）d.log2（n+1）+1
45.设输入序列为20,45,30,89,70,38,62，19依次插入到一棵2-3树中（初始状态为空），该B-树为（b）。
再删除38，该B-树为（f）。
（3062）（45）
（19，20）（3845）（70，89）（30（70）
（1920）（38）（62）（89）
a:
b:
（4570）（45）
（20）（62）（89）（20）（70）
（19）（30）（19）（30,38）（62）（89）
c:
d:
（3070）（45）
（19，20）（4562）（89）（20）（70）
（19）（30）（62）（89）
e:
f:
46.根据插入次序（80，90，100，110，85，70，75，60，72）建立二叉排序树。
图（a）是最终变化的结果。
若仍以该插入次序建立平衡二叉树。
图（c）是最终变化的结果。
8080
70907590
607585100607085100
7211072110
a:
b:
9090
7510080100
7080110757085110
6072856072
c:
d:
47.若有序表中关键字序列为：
14，20，25，32，34，45，57，69，77，83，92。
对其进行折半查找，则在等概率情况下，查找成功时的平均查找长度是（c）。
查找32时需进行（c）次比较。
a.1b.2c.3d.4
48.已知哈希表地址空间为A[9]，哈希函数为H（k）=kmod7，采用线性探测再散列处理冲突。
若依次将数据序列：
76,45,88,21,94,77,17存入该散列表中，则元素17存储的下标为（h）；在等概率情况下查找成功的平均查找长度为（c）。
a.0b.1c.2d.3
e.4f.5g.6h.7
49.若从二叉树的根结点到其它任一结点的路径上所经过的结点序列按其关键字递增有序，则该二叉树是（c）。
a.二叉排序树b.赫夫曼树c.堆d.平衡二叉树
50.当待排序序列的关键字次序为倒序时，若需为之进行正序排序，下列方案中（d）为佳。
a.起泡排序b.快速排序
c.直接插入排序d.简单选择排序
51.已知一组待排序的记录关键字初始排列如下：
56,26,86,35,75,19,77,58,48,42
下列选择中（d）是快速排序一趟排序的结果。
（c）是希尔排序
（初始步长为3）一趟排序的结果。
（a）是初始堆（大堆顶）。
a）86,75,77,58,42,19,56,35,48,26.
b）26,56,35,75,19,77,58,48,42,86.
c）35,26,19,42,58,48,56,75,86,77.
d）42,26,48,35,19,56,77,58,75,86.
52.下列排序算法中，（d）算法可能会出现：
初始数据有序时，花费的时间反而最多。
a.堆排序b.起泡排序c.归并排序d.快速排序
53.在下列排序方法中，（c）方法平均时间复杂度为0（nlogn），
最坏情况下时间复杂度为0（n2）；（d）方法所有情况下时间复杂度均为0（nlogn）。
a.插入排序b.希尔排序c.快速排序d.堆排序
三．填空题
1.数据结构通常有下列4类基本结构：
集合、、树型结构、图型结构。
设单链表中结点形式为datanext，若单链表长度大于等于2，指针p指向表中某个结点且p->next非空，此时若要删除指针p所指的结点，可以通过如下方法进行：
将p所指结点的后继的元素值复制到该结点，然后删除其后继结点。
相应的语句序列为：
；；；；
2.线性表的顺序存储结构是以来表示数据元素之间的逻辑关系的。
3.已知P是单链表中某一结点的指针，P既不是首元结点也不是尾元结点，Q是P的前驱结点指针。
当删除P结点时，链表的链接可用语句（）实现。
算法填空
StatusPreordertraverse（BitreeT,Status（*Visit）（Telemtypee））{
//先序非递归遍历二叉树。
Initstack（S）;Push（S,T）;
While（!
stackempty（S））
{While（gettop（S,p）&&_________________）
{if（!
Visit（p->data））returnERROR;
_____________________;
}
Pop（S,p）;
if（_______________）
{_______________;push（S,p->rchild）;}
}
returnok;
}
4.已知某树的先根遍历次序为abcdefg后根遍历次序为cdebgfa。
若将该树转换为二叉树,其后序遍历次序为（）。
层次遍历次序为（）。
5.已知某二叉树的先序遍历次序为afbcdeg后序遍历次序为cedbgfa。
其后序遍历次序为（）。
层次遍历次序为（）。
6.在二叉树的第i层上至少有_________个结点,至多有_________个结点,
深度为k的二叉树至多有_____________个结点.
7.对树的遍历有先序遍历树和后序遍历树。
若以二叉链表作树的存储结构,
则树的先序遍历可借用二叉树的遍历算法来实现,
而树的后序遍历可借用二叉树的遍历算法来实现。
8.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少是，至多是。
9.对任何一棵二叉树T,若其终端结点数为n0.度为2的结点为n2,则n0与n2的关系为（）。
10.如果对完全二叉树中结点从1开始按层进行编号，设最大编号为n；那么，可以断定编号为i（i>1）的结点的父结点编号为（）；所有编号（）的结点为叶子结点。
n个顶点的连通图至少有条边，至多有条边。
11.对于图的存储结构有（）、（）（）（）等方法。
12.在一个无向图的邻接表中，若表结点的个数是m，则图中边的条数是____________条。
13.若有序表中关键字序列为：
12，22，33，44，55，66，77，88，99对其进行折半查找，则在等概率情况下，查找成功时的平均查找长度是（）。
查找99时需进行（）次比较。
14.在哈希表中，处理冲突的方法有开放定址法，，等。
15.在二叉树的第i层上至少有_____个结点,至多有_____个结点,深度为k的二叉树至多有个结点.
16.对于一棵高度为K的二叉排序树，结点数最少可有个，最多可有个。
用 遍历对二叉排序树进行访问可得到有序序列。
17.已知Hash函数为H（K）=Kmod13，散列地址为0--14，用二次探测再散列
处理冲突，关键字（23，34，56，24，75，12，49,52，36，92）
的分布如图，则平均成功的查找长度为（）、平均失败的查找长度为（）。
18.一棵ｍ阶的Ｂ-树，第一层至少有一个结点；第二层至少有2个结点，
除根之外的所有非终端结点至少有（）棵子树，
树中每个结点至多有（）棵子树。
01234567891011121314
52
36
92
56
34
23
24
75
12
49
升级会员 