数据结构复习题

Q =\。

求：STRLEN(s)=14，STRLEN(t)=4，SUBSTR(s，8，7)=\，SUBSTR(t，2，1)=\，INDEX(s，\，INDEX(s，t)=0，REPLACT(s，\，q)=\AM A WORKER\。

2. 已知下列字串：

A = \，f =\ MPLE\，c =\，d =\，b =\?\，g =\ S = CONCAT(a，CONCAT(CONCAT (b，SUBSTR(a，3，2))，SUBSTR(f，2，6))) T =REPLACE(f，SUBSTR(f，3，5)，c) U = CONCAT (SUBSTR(c，3，1)，d)

V = CONCAT(s，CONCAT(b，CONCAT(t，CONCAT(b，u))))

问s=\IS SMPLE\，t=\ GOOD\，v=\IS SMPLE A GOOD ONE\，STRLEN(s)=13，INDEX(v,g)=3，INDEX(u,g)各是什么=0？

3. 简述下列每对术语的区别： 空串和空格串

空串是不包含任何字符的串，长度为0，空格串指包含一个或者多个空格的串，空格也是字符

串变量和串常量

串常量是指在程序中只可引用但不可改变其值的串，串变量时可以再运行中改变其值的。

主串和子串是相对的，一个串中任意个连续的字符组成的串就是这个串的子串，而包含子串的串就称为主串

4. 两个字符串相等的充要条件是什么？串长度相等，并且各对应位置上的字符也相等

5. 设已知两个串为： S1 = “bc cad cabcadf”；

S2 = “abc”。

试求两个串长度，并判断S2串是否是S1的子串。如果S2是S1的子串，指出S2在S1中的起始位置。S1的长度是14，S2的长度是3，S2是S1的子串，S2在S1的起始位置为9

习 题 六

一、判断题

1. 二叉树是树的特殊情形。( 错 )

2. 二叉树的先序遍历序列中，任意结点均处在其孩子结点之前。( 对 ) 3. 二叉链表是一种逻辑结构。( 错 )

4. 由二叉树的先序序列和后序序列可以唯一确定一棵二叉树。( 错 ) 5. n个结点的完全二叉树不唯一。( 错 )

6. 树的后序遍历序列与其对应的二叉树的后序遍历序列相同。( 错 ) 7. 完全二叉树的某结点若无左孩子，则它必是叶子结点。( 对 ) 二、选择题

1. 将一棵树t转换为孩子兄弟链表表示的二叉树h，则t的后序遍历是h的( B ) A. 先序遍历 B. 中序遍历

C. 后序遍历 D. 层次遍历

2. 对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用( C)次序的遍历

实现编号。

A. 先序 B. 中序

C. 后序 D. 从根开始的层次遍历

3. 已知一棵完全二叉树中共有768个结点，则该树中共有( B )个叶子结点。 A. 383

B. 384

C. 385 D. 386

4. 先序遍历和中序遍历相同的二叉树为( D )。 A 只有根结点的二叉树 B. 根结点无左孩子的二叉树 C 一般二叉树

D. 只有根结点的二叉树和所有结点只有右子树的二 叉树

三、简答题

1. 一棵树的边集为{(a,b)，(b,e)，(a,c)，(c,g)，(a,d)，(d,i)，(c,f)，(c,h)，(d,j)，(i,k)},请画出此棵树的形态，并回答下列问题：

(1) 树的根是哪个结点？A

哪些是叶子结点？ efghjk 哪些是分支结点？ abcdi

(2) 各结点的度分别是多少？树的度是多少？4 结点 a b c d e f g h i j k 度 3 1 3 2 0 0 0 0 1 0 0

层次 1 2 2 2 3 3 3 3 3 3 4

(3) 各结点的层次分别是多少？树的深度是多少？3以d为根的子树深度是多少？3 (4) 结点i的双亲是哪个结点？d 祖先是哪个结点？A 孩子是哪些结点？K 兄弟是哪些结点？j

2. 树和二叉树有哪些区别？

树是无序树，而二叉树是有序树，二叉树的度不能大于2，它的两个分支是有先后顺序的。

3. 已知二叉树的后序和中序序列如下，构造出该二叉树，写出它的前序遍历序列。 后序序列：ABCDEFG 中序序列：ACBGDFE

GCABFDE

4. 假设用于通信的电文由字符集{a,b,c,d,e,f,g}中的字母构成，它们在电文中出现的频度分别为{0.31, 0.16, 0.10, 0.08, 0.11, 0.20, 0.04} (1) 为这7个字母设计哈夫曼编码。

a,b,c,d,e,f,g的编码分别为：11，102，010，1001，011，00，1000，

(2) 对这7个字母进行等长编码，至少需要几位二进制数？哈夫曼编码与等长编码相比，能使电文总长压缩多少？WPL=2.61

等长编码需要3bit，则压缩了（3-2.61）、3=13% 习 题 七

一、单项选择题

1. 一个有n个顶点的无向图最多有__C______条边。 A. n

B. n(n-1)

C. n(n-1)/2 D. 2n

2. 一个有4个顶点的无向完全图有__A______条边。 A. 6 B. 12 C. 16 D. 20

3. 一个有5个顶点的连通图至少有_B_______条边。

A. 3 B. 4 C. 5 D. 6 4. ____B____的邻接矩阵是对称矩阵。 A. 有向图 B. 无向图 C. AOV网 5. 邻接表是图的一种___B_____。 A. 顺序存储结构

B. 链接存储结构

C. 索引存储结构 D. 散列存储结构

6. 采用邻接表存储的图的深度优先遍历算法类似于二 叉树的___A_____。 A. 前序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历

7. 采用邻接表存储的图的广度优先遍历算法类似于二叉树的___D_____。 A. 前序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 8. 任何一个无向连通图___B_____最小生成树。 Ａ.只有一棵 B. 有一棵或多棵

C. 一定有多棵 D. 可能不存在

9. 一个图的__B______表示法是唯一的，而_____C___表示法是不唯一的。 A. 三元组 B. 邻接矩阵 C. 邻接表 D. 索引 二、简答题

1. 对图7.23所示有向图，回答下列问题：

(1) 该图是强连通图吗？若不是，则给出其强连通分量。 (2) 请给出从顶点1到顶点3的所有的简单路径。 (3) 请给出顶点1的度、入度和出度。

(4) 请给出其邻接矩阵、邻接表及逆邻接表。 习 题 八

一、单选题

1. 对线性表进行二分查找时,要求线性表必须 C 。 A. 以顺序方式存储 B. 以链接方式存储 C. 以顺序方式存储且结点按关键字有序排列

D. 以链接方式存储且结点按关键字有序排列

2. 采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为 C 。

A. n B. n/2 C. (n + 1)/2 D. (n-1)/2

3．采用二分查找长度为n的线性时，每个元素的平均查找长度为 D 。 A. O(n2) B.O (nlog2n)

C. O(n) D. O(log2n)

4. 有一个有序表为(5，7，8，22，32，40，45，62，70，77，82，97，100)，当二分查找值为82的结点时， C 次比较后查找成功。

A. 1 B. 3 C. 4 D. 8

5. 从一个具有n个结点的单链表中查找其值等于x结点时，查找成功的情况下，需平均比较 D 个结点。

A. n B. n/2 C. (n–1)/ 2 D. (n + 1)/2 二、填空题

1. 假设在有序线性表A[1]，…，A[20]上进行二分查找，则比较一次查找成功的结点数为 1 ，则比较二次查找成功的结点数为 2 ，则比较三次查找成功的结点数为 4 ，则比较四次查找成功的结点数为 8 ，则比较五次查找成功的结点数为 5 ，平均查找长度为 3.7 。

2. 在散列存储中，装填因子α的值越大，存取数据元素时发生冲突的可能性 越大 ；α的值越小，则发生冲突的可能性 越小 。

三、简答题

设有一组关键字(19，01，23，14，55，20，84，27，68，11，10，77)，采用哈希函数H(key) = key % 13

采用开放地址法的线性探测再散列方法解决冲突，试在[0…12]的散列地址空间中对该关键字序列构造哈希表。

0 1 2 3 4 5 6 7 8 9 10 11 12

77 1 14 55 27 68 19 20 84 23 11 10 2. 对上题中的关键字序列，采用链地址法，画出相应的哈希表。

3. 对有序表(5，8，27，36，45，48，57，72，89，95)，采用二分查找，画出二分查找过程的二叉判定树，并计算其平均查找长度。

习 题 九

一、单选题

1. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 D 。

A. 希尔排序 B. 冒泡排序

C. 直接插入排序 D. 直接选择排序

2. 设有1000个无序的元素，希望用最快的速度挑选出其中前10个最大的元素，最好选用 B 排序法。

A. 冒泡排序 C. 快速排序

B. 堆排序 D. 基数排序

3. 排序的元素序列基本有序的前提下，效率最高的排序方法是 A 。 A. 直接插入排序 B. 直接选择排序

C. 快速排序 D. 归并排序

4. 一组记录的排序码为(46，79，56，38，40，84)，则利用堆排序的方法建立的初始堆为 B 。

A. 79，46，56，38，40，80

B. 84，79，56，38，40，46 C. 84，79，56，46，40，38 D. 84，56，79，40，46，38

5. 一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 C 。

A. 38，40，46，56，79，84 B. 40，38，46，79，56，84 C. 40，38，46，56，79，84

D. 40，38，46，84，56，79

6. 排序方法中，从未排序序列中依次取出元素与已排序序列(初始时为空)中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 C 。

A. 希尔排序 B. 归并排序 C. 插入排序 D. 选择排序 7. 用一种排序方法对线性表(25，84，21，47，15，27，68，35，20)进行排序时，元素序列的变化情况如下：

初始： 25，84，21，47，15，27，68，35，20

第一趟：20，15，21，25，47，27，68，35，84 第二趟：15，20，21，25，35，27，47，68，84 第三趟：15，20，21，25，27，35，47，68，84 则所采用的排序方法是 D 。 A. 选择排序 B. 希尔排序 C. 归并排序 D. 快速排序

8. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是 B 。

A. O(1) B. O(n) C. O(n2) D. O( nlog2n)

9. 给定n个元素的向量，建立一个有序单链表的时间复杂度是 C 。 A. O(1) C. O(n2)

B. O(n) D. O(nlog2n)

1、给出下图的最小生成树

A 3 D 2 4 8 E 4 1 9 7 9

5 8 F G 6

C B 1 答案

A E D F G B C