数据结构题.doc

第六章树和二叉树
简答题
1、有一棵树的括号表示为A(B,C(E,F(G)),D),回答下面的问题：
这棵树的根结点是谁？
这棵树的叶子结点是什么？
结点C的度是多少？
这棵树的度是多少？
这棵树的深度是多少？
结点C的孩子结点是哪些？
结点C的双亲结点是谁？
2、若一棵度为4的树中度为1,2,3,4的结点个数分别是4,3,2,2，则该树中叶子结点的个数是多少？总结点个数是多少？
3、一棵高度为h的完全k次数，如果按照层次自上向下、自左向右的顺序从1开始对全部结点编号，试问：
最多有多少个结点？最少有多少个结点？
编号为q的结点的第i个孩子结点的编号是多少？
4、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数为 结点的总个数为
5、一棵完全二叉树有1001个结点，其中叶子结点的个数为
6、一棵高度为h的完全二叉树至少有 个结点。
7、一棵高度为5的完全二叉树至多有 个结点。
8、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树至少包含 个结点。
9、一个具有1025个结点的二叉树的高度h为
10、在一棵完全二叉树中，结点个数为n，则编号最大的分支结点的编号为
11、一棵二叉树的先序遍历为ABCDEF，中序遍历为CBAEDF，则后序遍历为
12、一棵二叉树的先序遍历为ABCDEFG，它的中序遍历可能为
A.CABDEFG B. ABCDEFG
C.DACEFBG D.ADCFEGB
思考：二叉树的先序和中序遍历相同的条件是？
二叉树的后序和中序遍历相同的条件是？
13、一棵二叉树的后序遍历为DABEC，中序遍历为DEBAC，则先序遍历为
14、一棵二叉树的先序遍历为EFHIGJK，中序遍历为HFIEJKG，则该二叉树根结点的右孩子为
16、根据使用频率为5个字符设计的赫夫曼编码不可能的是
A.111,110,10,01,00 B.000,001,010,011,1
C.100,11,10,1,0 D.001,000,01,11,10
17、根据使用频率为5个字符设计的赫夫曼编码不可能的是
A. 000,001,010,011,1 B.0000,0001,001,01,1
C. 000,001,01,10,11 D.00,100,101,110,111

18、设有13个值，用它们组成一棵赫夫曼树，则该赫夫曼树共有 个结点。
19、若以{4,5,6,7,8}作为叶子结点的权值构造赫夫曼树，则其带权路径长度是 ，各结点对应的赫夫曼编码为

20、以数据集{2,5,7,9,13}为权值构造一棵赫夫曼树，并计算其带权路径长度。
21、一棵二叉树的先序、中序和后序序列分别如下，其中有一部分未显示出来，试求出空格部分的内容，并画出二叉树。
先序遍历 B F ICEH G
中序遍历 D KFIA EJC
后序遍历 K FBHJ G A
15、如图所示的二叉树T2是由森林T1转换而来的二叉树，那么森林T1有 叶子结点。
G
J
I
H
F
D
C
E
B
A

第七章 图
1.在一个无向图中,所有顶点的度数之和等于所有边数的 倍。
A.1/2 B.1 C.2 D.4
2.在一个有向图中,所有顶点的入度之和等于所有顶点的出度之和
的 倍。
A．1/2 B.1 C.2 D.4
3.一个有n个顶点的无向图最多有 条边。
A.n B.n(n-1) C.n(n-1）/2 D.2n
4.具有4个顶点的无向完全图有 条边。
A.6 B.12 C.16 D.20
5.具有6个顶点的无向图至少应有 条边才能确保是一个连通图。
A.5 B.6 C.7 D.8
6.在一个具有n个顶点的无向图中,要连通全部顶点至少需要 条边。
A.n B.n+1 C.n-1 D.n/2
7.在有n个顶点的有向图中，每个顶点的度最大可达
8.对于一个具有n个顶点的无向图,若采用邻接矩阵表示,则该矩阵的大小
A.n B.(n-1)2 C.n-1 D.n2
9.对于一个具有n个顶点和e条边的无向图,若采用邻接表表示,则表头向量的大小为 ，所有邻接表中的结点总数是 。
10. 采用邻接表存储的图的深度优先遍历算法类似于二叉树的 。
A.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历
11. 采用邻接表存储的图的宽度优先遍历算法类似于二叉树的
A.先序遍历 B.中序遍历 C.后序遍历 D.按层遍历
12.一个有向图G的邻接表存储如图，现按深度优先遍历，从顶点v1出发，所得到的顶点序列是
v1
v3
v4
v2
4
5
2
^
^
^
v5
3
5
^
3
4
^

13. 一个如图的无向图，从顶点1出发进行深度优先遍历，，可得到的顶点序列是
14. 一个如图的无向图，从顶点1出发进行广度优先遍历，，可得到的顶点序列是

1
3
2
6
5
7
4

15. 已知图G的邻接表存储如图，从顶点v1出发，现按深度优先遍历所得到的顶点序列是 ；从顶点v1出发，现按广度优先遍历所得到的顶点序列是
v1
v3
v4
v2
4
6
2
^
^
^
v5
5
5
^
3
4
v6
6
3
^
^

16.图G是一个非连通无向图，共有28条边，则该图至少有 个顶点。
17.一个无向连通图的生成树是含有该连通图的全部顶点的
A.极小连通子图 B.极大连通子图
C.极小子图 D.极大子图
18.已知世界6大城市：北京B，纽约N，巴黎P，伦敦L，东京T，墨西哥M。试在由表中给出的交通网确定最小生成树。

B
N
P
L
T
M
B

109
82
81
21
124
N
109

58
55
108
32
P
82
58

3
97
92
L
81
55
3

95
89
T
21
108
97
95

113
M
124
32
92
89
113

19.普利姆算法适用于求 的网的最小生成树，克鲁斯卡尔算法适用于求 的网的最小生成树。
20.若一个有向图中顶点不能排列成一个拓扑序列，则可断定该有向图
A.是个有根有向图 B.是个强连通图
C.含有多个入度为0的顶点 D.含有顶点数目大于1的强连通分量
21.在AOV网中，顶点表示 ，有向边表示
22.关键路径是事件结点网络中
A.从源点到汇点的最长路径 B. 从源点到汇点的最短路径
C.最长的回路 D.最短的回路
23. 从源点到汇点的最长路径称关键路径，该路径上的活动称为

24.判定一个有向图是否存在回路除了可以利用拓扑排序方法外,还可以利用 .
A．求关键路径的方法 B.求最短路径的Dijkstra方法
C.宽度优先遍历算法 D.深度优先遍历算法
附加上课讲的五个大题。
一、 给出邻接表，画图，遍历并分别用普利姆和克鲁斯卡尔算法求最小生成树。
二、 给出有向带权图，用Dijkstra算法求从某一顶点出发到其他顶点的最短路径，要求给出求解过程。
三、 给出工程的AOE网，求完成工程的最短时间，并计算工期。

第九章　查找
1.顺序查找法适合于存储结构为 的线性表。
A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储
2.顺序查找法的平均查找长度为 ，二分查找法的平均查找长度为 ，分块查找法(以顺序查找确定块)的平均查找长度为 ，分块查找法(以二分查找确定块〉的平均查找长度为 。
3.顺序查找法查找长度为n的线性表时，平均比较次数为
4.对线性表进行二分查找时,要求线性表必须 。
A.以顺序方式存储 B.以链接方式存储
C.以顺序方式存储,且结点按关键字有序排序
D.以链接方式存储,且结点按关键字有序排序
5.己知一个有序表为(12,18,20,25,29,32,40,62,83,90,95,98),当二分查找值为29和90的元素时,分别需要 次和 次比较才能查找成功；若采用顺序查找时,分别需要 次和 次比较才能查找成功。
6.有一个有序表为{1,3,9,12,32,41,45,62,75,77,82,95,100},当二分查找值为82的结点时, 次比较后查找成功。
A.1 B.2 C.4 D.8
7.假设在有序线性表A[1..20]上进行二分查找,则比较一次查找成功的结点数为 ,则比较二次查找成功的结点数为 ,则比较三次查找成功的结点数为 ,则比较四次查找成功的结点数为 ,则比较五次查找成功的结点数为 ,平均查找长度为 。
8.有一个长度为12的有序表,按二分查找法对该表进行查找,在表内各元素等概率情况下查找成功所需的平均比较次数为
A.35/12 B.37/12 C.39/12 D.43/12
9.设有一个长度为100的已排好序的表，用二分查找进行查找，若查找不成功，至少比较 次。
A.9　 　 B.8　　 C.7　 　D.6
10.在分块查找方法中,首先查找 ,然后再查找相应的 。
11.长度为225的表,采用分块查找法,每块的最佳长度是 。
12.在分块查找中，若索引表各块内均用顺序查找，则有900个元素线性表分成 块最好；若分成25块，其平均查找长度为
13.在含有27个结点的二叉排序树上，查找关键字为35的结点，则依次比较的关键字有可能是
A.28,36,18,46,35 B.18,36,28,46,35
C.46,28,18,36,35 D.46,36,18,28,35
14.如图所示的一棵二叉排序树其查找成功的平均查找长度是 ；其不成功的平均查找长度是 。
62
74
30
56
15
48

62
74
30
56
15
48

15.在一棵平衡二叉树中，每个结点的平衡因子的取值范围是 。
16.如图所示的4棵二叉树， 是平衡二叉树。

17.具有5层结点的AVL树至少有 个结点。
18.在含有12个结点的平衡二叉树上，查找关键字为35的结点，则依次比较的关键字有可能是
A.46,36,18,20,,28,35 B.47,37,18,27,36
C.27,48,39,43,37 D.15,45,35
19.在含有15个结点的平衡二叉树上，查找关键字为28的结点，则依次比较的关键字有可能是
A.30,36 B.38,48,28
C.48,18,38,28 D.60,30,50,40,38,36
20.一棵深度为k的平衡二叉树，其每个非叶子结点的平衡因子均为0，则该树共有 个结点。
21.查找效率最高的二叉排序树是 。
A.所有结点的左子树都为空的二叉排序树
B.所有结点的右子树都为空的二叉排序树
C.平衡二叉树
D.没有左子树的二叉排序树
22.用二叉排序树查找，在最坏情况下，平均查找长度数量级为 ；当二叉排序树是一棵平衡二叉树时，ASL平均查找长度数量级为 。
23.按13,24,37,90,53的次序形成平衡二叉树，则该平衡二叉树高度 ，其根为 。
24.将整数序列{4,5,7,2,1,3,6}中的数依次插入到一棵空的平衡二叉树中，试构造相应的平衡二叉树。
25.输入关键字序列{16,3,7,11,9,26,18,14,15}，给出构造一棵AVL树的步骤。
26.关键字序列为{1,2,6,7,11,4,8,13,10,5,17,9,16,20,3,12,14,18,19,15}，创建一棵5阶B-树。对于该B-树，给出删除8,16,15,4这四个关键字的过程。
27.已知一组关键字为{21,33,12,40,68,59,25,51}，试依次插入关键字生成一棵3阶B-树；如果此后删除40，画出每一步执行后B-树的状态。
28.在散列函数H(key)=key%p中,p最好取 。
29.在哈希查找过程中，可用 来处理冲突。
A．除留余数法 B.数字分析法
C.线性探测再散列 D.关键字比较法
30．设哈希表长m=14,哈希函数H(key)=key%11。表中已有4个结点:
H(15)=4,H(38)=5,H(61)=6,H(84)=7,其余地址为空，如用二次探测再散列处理冲突,关键字为49的结点的地址是 。
A.8 B.3 C.5 D.9
31.假设有k个关键字互为同义词，若用线性探测再散列探查法把这k个关键字存入哈希表中，至少要进行 次探测。
32. 已知一个线性表为(38,25,74,63,52,48),假定采用H(k)=k%7计算散列地址进行散列存储,试分别求出利用线性探测的开放定址法处理冲突和利用链地址法处理冲突,在该散列表上进行查找的平均查找长度。
33. 己知线性表的元素为(87,25,310,8,27,132,68,95,187,123,70,63,47),散列函数为h(k)=k%13,采用链接法处理冲突。设计出这种链表结构,并求该表平均查找长度。
34.设散列表容量为7，给定表（30，36，47，52，34），散列函数H（K）＝k mod 6，采用线性探测解决冲突，要求：　　
（1）构造此散列表(散列地址为0~6)：　　　　 　　
（2）求查找34需要进行比较的次数。

第十章排序习题
1． 给出关键字序列{4，5，1，2，8，6，7，3，10，9}的直接插入排序过程和希尔排序过程（gap=5,2,1）。
2． 以下序列不是堆的是（）
A．{100，85，98，77，80，60，82，40，20，10，66}
B．{100，98，85，82，80，77，66，60，40，20，10}
C．{10，20，40，60，66，77，80，82，95，98，100}
D．{100，85，40，77，80，60，66，98，92，10，20}
3．以下序列是堆的是（）
A．{75，65，30，15，25，45，20，10}
B．{75，65，45，10，30，25，20，15}
C．{75，45，65，30，15，25，20，10}
D．{75，45，65，10，25，30，20，15}
4．已知序列{503，87，512，61，908，170，897，275，653，462}，写出采用堆排序法时的每一趟的结果。
5．以下关键字序列用快速排序法进行排序时速度最快的是()
A．{21，25，5，17，9，23，30}
B．{25，23，30，17，21，5，9}
C．{21，9，17，30，25，23，5}
D．{5，9，17，21，23，25，30}
6．对关键字{28，16，32，12，60，2，5，72}序列进行快速排序,第一趟从小到大一次划分结果为()
A．（2，5，12，16） 26 （60，32，72）
B．（5，16，2，12） 28 （60，32，72）
C．（2，16，12，5） 28 （60，32，72）
D．（5，16，2，12） 28 （32，60，72）
7．已知序列{503，87，512，61，908，170，897，275，653，462}采用快速排序法对序列作升序排序时的每一趟排序结果。
8．已知关键字序列{112，214，312，902，156，712，451，623，643，834}按低位到高位进行基数排序时每一趟的结果。

第四章 串
选择题、填空题
1.下列关于串的叙述中，正确的是（　　）　
A.一个串的字符个数即该串的长度　　
B.一个串的长度至少是1　　
C.空串是由一个空格字符组成的串
D.两个串S1和S2若长度相同，则这两个串相等
2.串是任意有限个
A.符号构成的集合 B.符号构成的序列
C.字符构成的集合 D.字符构成的序列
3.以下 是’abcd321ABCD’的子串。
A.abcd B.321AB
C.’abcABC’ D.’21AB’
4.两个串相等必须有串长度相等且
A．串的各位置字符任意
B.串中各位置字符均对应相等
C.两个串含有相同的字符
D.两个所含字符任意
5.若串s=’software’,其子串的个数是
A.8 B.37 C.36 D.9
6.空串是 ，其长度等于 。
7.设s=’abcd’,s1=’123’,则执行语句s2=StrInsert(s,2,s1)后，s2=
8. 设s=’abcd’,则执行语句s2=StrDelete(s,2,2)后，s2=
9. 设s=’abcd’,则执行语句s2=SubString(s,4,2)后，s2=
10.对于顺序表s，其初始化为空串的操作是
11.设有两个串p和q，求q在p中首次出现的位置的运算称作
12.已知t=’abcaabbcabcaabdab’,该模式串的next数组值为

13.模式串t=’abbaabcac’的next函数值为 ，nextval函数值为
算法设计题
1. 分别在顺序存储和一般链式存储两种方式下,用C语言写出实现把串s1复制到串s2的串复制函数strcpy(s1,s2)。
2.设计一个算法将一个链串s中的所有子串‘abc’删除。
3.设计一个算法判断链串s中所有元素是否为递增排列的。

8