第一章 绪论
单项选择题
1．在数据结构中，数据的基本单位是_____ ____。
A. 数据项 数据类型 数据元素 数据变量
2．数据结构中数据元素之间的逻辑关系被称为__ ____。
A. 数据的存储结构 数据的基本操作 程序的算法 数据的逻辑结构
3．在数据结构中，与所使用计算机无关的是数据的____ ___。
A. 存储结构 逻辑和物理结构 逻辑结构 物理结构
4．在链式存储结构中，数据之间的关系是通过____ ____体现的。
A. 数据在内存的相对位置 指示数据元素的指针
C. 数据的存储地址 指针
5．计算算法的时间复杂度是属于一种____ ___。
A. 事前统计的方法 事前分析估算的方法
C. 事后统计的方法 事后分析估算的方法
6．在对算法的时间复杂度进行估计的时候，下列最佳的时间复杂度是____ __。
A. n2 B. nlogn C. n D. logn
7．设使用某算法对n个元素进行处理，所需的时间是T(n)=100nlog2n+200n+2000，则该算法的渐近时间复杂度为____ ___。
A. O(O(O(O(nlog2n)
CDCBBDD
第二章 线性表
单项选择题
1．链表不具有的特点是____ ____。
A. 可随机访问任一元素 B. 插入和删除时不需要移动元素
C. 不必事先估计存储空间 D. 所需空间与线性表的长度正比
2．设顺序表的每个元素占8个存储单元。第1个单元的存储地址是100，则第6个元素占用的最后一个存储单元的地址为 。
A. 139 B. 140 C. 147 D. 148
3．在线性链表存储结构下，插入操作算法 。
A. 需要判断是否表满 B. 需要判断是否表空
C. 不需要判断表满 D. 需要判断是否表空和表满
4．在一个单链表中，若删除p所指结点的后继结点，则执行 。
A. p->next = p->next->next; B. p->next = p->next;
C. p = p->next->next; D. p = p->next; p->next = p->next->next;
5．将长度为n的单链表接在长度为m的单链表之后的算法时间复杂度为 。
A. O(n) B. O(1) C. O(m) D. O(m+n)
6．需要预分较大空间，插入和删除不需要移动元素的线性表，其存储结构是 。
A. 单链表 B. 静态链表 C. 线性链表 D. 顺序存储方式
ACCABB
填空题
1．在带表头结点的单链表中，当删除某一指定结点时，必须找到该结点的_____结点。
2．在单链表中，指针p所指结点为最后一个结点的条件是 。
3．将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是 。
4．在一个长度为n的顺序表中第i个元素（1≤i≤n）之前插入一个元素时，需向后移动元素的个数是 。
5．在长度为n的顺序表中插入一个元素的时间复杂度为 。
1前驱
2 p->next==NULL
3.1
4.n-i+1
5.O(n)
例题解析
【例2-1】 编写一个算法将一个单链表逆转，要求在原表上进行，不允许重新建链表。
解：该算法可以在遍历原表的时候将各结点的指针逆转，从原表的第一个结点开始，头结点的指针在最后修改成指向原表的最后一个结点，即新表的第一个结点。实现本题功能的函数如下：
void inverse(Lnode *h)
{s=h->next;
if(s==NULL) return;
q=NULL;
p=s;
while(p!=NULL)
{ p=p->next;
s->next=q; /*逆转指针*/
q=s; /*指针前移*/
s=p;
}
h->next=q; /*头指针h的后继是p*/
}
【例2-2】 编写一算法将两个按元素值递增有序排列的单链表A和B归并成一个按元素值递增有序排列的单链表C。
解：对于两个或两个以上的，结点按元素值有序排列的单链表进行操作时，应采用“指针平行移动，依次扫描完成”的方法。从两表的第一个结点开始顺链表逐个将对应数据元素进行比较，复制小的并插入c表尾。当两表中之一已到表尾，则复制另一个链表的剩余部分，插入到c表尾。设pa、pb分别指向两表当前结点，p指向c表的当前表尾结点。若设A中当前所指的元素为a，B中当前所指的元素为b，则当前应插入到 C中的元素c为
例如：A=(3,5,8,11)
B=(2,6,8,9,11,15,20)
则 C=(2,3,5,6,8,8,9,11,11,15,20)
实现本题功能的函数如下：
Lnode *hb(Lnode *pa,Lnode *pb)
{Lnode *p,*q,*pc;
pc=(Lnode*)malloc(sizeof(Lnode)); /*建立表c 的头结点pc*/
p=pc; /*p指向C表头结点*/
while(pa!=NULL&&pb!=NULL)
{
q=(Lnode*)malloc(sizeof(Lnode)); /*建立新结点q*/
if(pb->data {q->data=pb->data; /*B中结点值小，将其值赋给q的数据域*/ pb=pb->next; /*B中指针pb后移*/ } else {q->data=pa->data; /*相反，将A结点值赋给q的数据域*/ pa=pa->next; /*A中指针pa后移*/ } p->next=q; /*将q接在p的后面*/ p=q; /*p始终指向C表当前尾结点*/ } while(pa!=NULL) /*若表A比B长，将A余下的结点链在C表尾*/ {q=(Lnode*)malloc(sizeof(Lnode)); q->data=pa->data; pa=pa->next; p->next=q; p=q; } while(pb!=NULL) /*若表B比A长，将B余下的结点链在C表尾*/ {q=(Lnode*)malloc(sizeof(Lnode)); q->data=pb->data; pb=pb->next; p->next=q; p=q; } p->next=NULL; p=pc; /*p指向表C的头结点pc*/ pc=p->next; /*改变指针状态，使pc指向p的后继*/ free(p); /*释放p空间*/ return (pc); } 此算法的时间复杂度为O(m+n)，其中m，n分别是两个被合并表的表长。 第三章栈和队列 单项选择题 1．在初始为空的堆栈中依次插入元素f，e，d，c，b，a以后，连续进行了三次删除操作，此时栈顶元素是 。 A. ｃ B.ｄ C.ｂ D. ｅ 2．若某堆栈的输入序列是1，2，3，...，n，输出序列的第一个元素为n，则第i个输出元素为 。 A. i B. n-i C. n-i+1 D. 哪个元素无所谓 3．向一个栈顶指针为h的带头结点链栈中插入指针s所指的结点时，应执行 。 4．一个栈的入栈序列是 a，b，c，d，e，则栈的不可能的输出序列是 。 A. edcba B. decba C. dceab D. abcde 5．栈和队列的共同点是 。 A. 都是先进后出 都是先进先出 C. 只允许在端点处插入和删除元素 没有共同点 6．对于循环队列 。 A. 无法判断队列是否为空 无法判断队列是否为满 C. 队列不可能满 以上说法都不是 7. 若用一个大小为6的数组来实现循环队列，且当前队尾指针rear和队头指针front的值分别为0和3。当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为 。 A. 1和5和4和2和1 8. 判定一个循环队列 QU（最多元素为 m0）为满队列的条件是 。 9.判定一个循环队列 QU（最多元素为 m0）为空的条件是 。 BCDCCDACA 填空题 1．在求表达式值的算符优先算法中使用的主要数据结构是 。 2．设有一个空栈，现输入序列为1，2，3，4，5。经过push，push，pop，push，pop，push，pop，push后，输出序列是 。 3．仅允许在同一端进行插入和删除的线性表称为 。 7．在顺序栈s中，栈为空的条件是 ，栈为满的条件是_____。 4．用S表示入栈操作，X表示出栈操作，若元素入栈顺序为1234，为了得到1342出栈顺序，相应的S、X操作串为 。 5．用一个大小为1000的数组来实现循环队列，当前rear和front的值分别为0和994，若要达到队满的条件，还需要继续入队的元素个数是 。 1.栈 2. 2 3 4 3.栈 4.s.top==s.base, s.top-s.base>=s.stacksize SXSSXSXX 5.993 例题解析 【例3-1】 编程实现：用除法把十进制数转换成二进制数。 解：算法思想：用初始十进制数除以2把余数记录下来并且若商不为0则再用商去除以2直到商为0，这时把所有的余数按出现的逆序排列起来（先出现的余数排在后面，后出现的余数排在前面）就得到了相应的二进制数，如把十进制数35转换成二进制数的过程如图3-1所示。 图3-1 十进制数转换成二进制数的过程 由题意可知，我们可以用一个栈来保存所有的余数，当商为0时则让栈里的所有余数出栈则可以得到正确的二进制数，算法可描述如下： void conversion(){ Stack S; int n; InitStack(&S); printf("Input a number to convert:\\n"); scanf("%d",&n); if(n<0){ printf("\\nThe number must be over 0."); return; } if(n==0) Push(S,0); while(n!=0){ Push(S,n%2); n=n/2; } printf("the result is: "); while(!StackEmpty(*S)){ printf("%d", Pop(S)); } } } 第四章 串 单项选择题 1．串是一种特殊的线性表，其特殊性体现在 。 A. 可以顺序存储 数据元素是一个字符 C. 可以链接存储 数据元素可以是多个字符 2．设有两个串p和q，求q在p中首次出现的位置的运算称作 。 A. 连接 模式匹配 求子串 求串长 3．串是一个 B 的序列。 A. 不少于一个字母 B. 有限个字符 C. 不少于一个字符 D. 空格或字母 4．已知串s=’ABCDEFGH’，则s的所有不同子串的个数为 。 A. 8 B. 9 C. 36 D. 37 BBBD 填空题 1．两个串相等的充分必要条件是 。 2．空格串是 ,其长度等于 。 3．在串S=’tuition’中，以t为首字符且值不相同的子串有 个。 4. 使用“求子串”substring(S,pos,len)和“联接”concat(S1,S2)的串操作，可从串s=’conduction’中的字符得到串t=’cont’，则求t的串表达式为 。 1.两个串的长度相等且对应位置的字符相同 2.由一个或多个空格字符组成的串 其包含的空格个数 3. 10 4. concat(subString(s,1,3),substring(s,7,1)) 第五章 数组与广义表 单项选择题 1．常对数组进行的两种操作是 。 A. 建立与删除 索引和修改 查找和修改 查找与索引 2．假设8行10列的二维数组a[1..8, 1..10]分别以行序为主序和以列序为主序顺序存储时，其首地址相同，那么以行序为主序时元素a[3][5]的地址与以列序为主序时元素 ____ ___的地址相同。 A. a[5][3] B. a[8][3] C. a[1][4] D. 答案A、B、C均不对 3．将一个A[1..100,1..100]的三对角矩阵以行序为主序存入一维数组B[1..298]中，元素A[66，65]在B数组中的位置k等于____ ___。 A. 198 B. 197 C. 196 D. 195 4．稀疏矩阵一般的压缩存储方法有两种，即 。 A. 二维数组和三维数组 三元组和散列 C. 三元组和十字链表 散列和十字链表 5. 一个非空广义表的表头____ ___。 不可能是子表 只能是子表 只能是原子 可以是原子或子表 6. 设head(L)、tail(L)分别为取广义表表头、表尾操作，则从广义表L=((x,y,z),a,(u,v,w))中取出原子u的运算为____ ___。 C. head(tail(head(tail(L)))) D. head(head(tail(tail(L)))) 7．广义表(a,((b,(c,d,(e,f))),g))的深度为____ ___。 A. 3 B. 4 C. 5 D. 6 CDDCDDC 填空题 1．将下三角矩阵A[1..8,1..8]的下三角部分逐行地存储到起始地址为1000的内存单元中，已知每个元素占四个单元，则元素A[7,5]的地址为 。 2．二维数组A[0..9,0..19]采用行序为主方式存储，每个元素占一个存储单元，并且元素A[0,0]的存储地址是200，则元素A[6,12]的地址是 。 3．二维数组A[10..20,5..10]采用行序为主方式存储，每个元素占4个存储单元，并且元素A[10,5]的存储地址是1000，则元素A[18,9]的地址是 。 4．有一个10阶对称矩阵A，采用压缩存储方式（以行序为主序存储，且元素A[0,0]地址为1），则元素A[8,5]的地址是 。 5．设HAED[p]为求广义表p的表头函数，TAIL[p]为求广义表p的表尾函数，其中[] 是函数的符号，给出下列广义表的运算结果： HEAD[(a，b，c)]的结果是 。 TAIL[(a，b，c)]的结果是 。 HEAD[((a)，(b))]的结果是 。 TAIL[((a)，(b))]的结果是 。 HEAD[TAIL[(a，b，c)]的结果是 。 TAIL[HEAD((a，b)，(c，d))]的结果是 。 HEAD[HEAD[(a，b)，(c，d))]]的结果是 。 TAIL[TAIL[(a，(c，d))]]的结果是 。 ①a；②(b，c)；③(a)；④((b))；⑤b；⑥(b)；⑦a；⑧( ) 1. 1100 2. 332 3. 1208 4. 42 5. ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ 第6章 树和二叉树 选择题 1．以下说法错误的是 。 A.树形结构的特点是一个结点可以有多个直接前趋 B.线性结构中的一个结点至多只有一个直接后继 C.树形结构可以表达(组织)更复杂的数据 D.树(及一切树形结构)是一种"分支层次"结构 2. 如图6-2所示的 4 棵二叉树中， 不是完全二叉树。 图6-2 4 棵二叉树 3. 以下说法错误的是 。 A.完全二叉树上结点之间的父子关系可由它们编号之间的关系来表达 B.在三叉链表上，二叉树的求双亲运算很容易实现 C.在二叉链表上，求根，求左、右孩子等很容易实现 D.在二叉链表上，求双亲运算的时间性能很好 4. 如图6-3所示的 4 棵二叉树， 是平衡二叉树。 图6-3 4 棵二叉树 5. 如图6-4所示二叉树的中序遍历序列是 。 A. abcdgef B. dfebagc C. dbaefcg D. defbagc 图6-4 1 棵二叉树 6. 某二叉树的前序遍历结点访问顺序是 abdgcefh，中序遍历的结点访问顺序是dgbaechf，则其后序遍历的结点访问顺序是 。 A. bdgcefha B. gdbecfha C. bdgaechf D. gdbehfca 7. 将含有83个结点的完全二叉树从根结点开始编号，根为1号，后面按从上到下、从左到右的顺序对结点编号，那么编号为41的双亲结点编号为 。 A.42 B.40 C.21 D.20 8. 一棵二叉树如图6-5所示，其后序遍历的序列为 。 A. abdgcefh B. dgbaechf C. gdbehfca D. abcdefgh 图6-5 1 棵二叉树 9. 深度为 5 的二叉树至多有 个结点。 A. 16 B. 32 C.31 D.10 10. 设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数至少有 个。 A.kB.2C.2D.2k+1 11. 对含有 B 个结点的非空二叉树，采用任何一种遍历方式，其结点访问序列均相同。 A.0 B.1 C.2 D.不存在这样的二叉树 6-10 DDCCC 填空题 1. 有一棵树如图6-7 所示，回答下面的问题： 图6-7 1 棵二叉树 （1）这棵树的根结点是 ； （2）这棵树的叶子结点是 ； （3）结点 k3 的度是 ； （4）这棵树的度为 ； （5）这棵树的深度是 ； （6）结点 k3 的孩子是 ； （7）结点 k3 的双亲结点是 。 2. 深度为 k 的完全二叉树至少有 个结点，至多有 个结点，若按自上而下，从左到右次序给结点编号（从 1 开始），则编号最小的叶子结点的编号是 。 答：①2 ②2-1 ③2+1 3. 一棵二叉树的第 i（i≥1）层最多有 个结点；一棵有 n（n>0）个结点的满二叉树共有 个叶子和 个非终端结点。 答：① 2 ② ③ 4. 具有n个结点的完全二叉树的深度为 。 5. 哈夫曼树是带权路径度_______的树，通常权值较大的结点离根_______。 ①最短 ②较近 6．在________遍历二叉树的序列中，任何结点的子树上的所有结点，都是直接跟在该结点之后。 1.答：① k1 ② k2 k5 k7 k4 ③ 2 ④ 3 ⑤ 4 ⑥ k5，k6 ⑦ k1 2. ① ② ③ 3. ① ② ③ 4.floor(log2n)+1 5. ① ② 6. 先根 例题解析 【例6-1】由如图 6-1 所示的二叉树，回答以下问题。 （1）其中序遍历序列为 ① ； （2）其前序遍历序列为 ② ； （3）其后序遍历序列为 ③ ； （4）该二叉树的中序线索二叉树为 ④ ； （5）该二叉树的后序线索二叉树为 ⑤ ； （6）该二叉树对应的森林是 ⑥ 。 图6-1 1棵二叉树 解： ① 中序遍历序列为dgbaechif ② 前序遍历序列为abdgcefhi ③ 后序遍历序列为gdbeihfca ④ 该二叉树的中序线索二叉树如图 6.1.1(a)所示 ⑤ 该二叉树的后序线索二叉树如图6-1-1 (b)所示 ⑥ 该二叉树对应的森林如图6-1-2所示 图6-1-1 二叉树的中序线索二叉树和后序线索二叉树 图6-1-2 二叉树对应的森林 1．二叉树结点数值采用顺序存储结构，如表6-2所示。 表6-2 二叉树的顺序存储结构 （2）写出前序遍历，中序遍历和后序遍历的结果； （3）写出结点值 c 的父结点，其左、右孩子。 解： （1）该二叉树如图 6-9 所示。 图 6-9 1棵二叉树 （2）本题二叉树的各种遍历结果如下： 前序遍历：eadcbjfghi 中序遍历：abcdjefhgi 后序遍历：bcjdahigfa （3）c 的父结点为 d，左孩子为 j，没有右孩子。 2．有一份电文使用 5 个字符：a、b、c、d、e，它们的出现频率依次为 4、7、5、2、9，试画出对应的哈夫曼树（请按左子树根结点的权小于等于右子树根结点的权的次序构造），并求出每个字符的哈夫曼编码。 解：依题意，本题对应的哈夫曼树如图 6-15 所示。 各字符对应的哈夫曼编码如下： a：001 b：10 c：01 d：000 e：11 图6-15 一棵哈夫曼树 3．设给定权集 w={2，3，4，7，8，9}，试构造关于 w 的一棵哈夫曼树，并求其加权路径长度 WPL。 解：本题的哈夫曼树如图 6-16 所示。 图6-16 一棵哈夫曼树 其加权路径长度 WPL=7×2+8×2+4×3+2×4+3×4+9×2=80 4. 已知一棵二叉树的中序序列为 cbedahgijf，后序序列为cedbhjigfa，画出该二叉树的先序线索二叉树。 解：由后序序列的最后一个结点 a 可推出该二叉树的树根为 a，由中序序列可推出 a的左子树由 cbed 组成，右子树由 hgijf 组成，又由 cbed 在后序序列中的顺序可推出该子树的根结点为 b，其左子树只有一个结点 c，右子树由 ed 组成，显然这里的 e 是根结点，其右子树为结点 d，这样可得到根结点 a 的左子树的先序序列为：bcde；再依次推出右子树的先序序列为：fghij。因此该二叉树如图 6-17所示。 图 6-17 二叉树 设二叉树的先序线索链表如图 6-18所示。 图 6-18 二叉树的先序线索链表 第7章 图 单项选择题 1．在一个图中，所有顶点的度数之和等于所有边数的 倍。 A. 1/2 B. 1 C. 2 D. 4 2．在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的 B 倍。 A. 1/2 B. 1 C. 2 D. 4 3．具有 4 个顶点的无向完全图有 条边。 A. 6 B. 12 C. 16 D. 20 4．具有 6 个顶点的无向图至少应有 条边才能确保是一个连通图。 A. 5 B. 6 C. 7 D. 8 5．在一个具有 n 个顶点的无向图中，要连通全部顶点至少需要 条边。 A. n B. n+1 C. n-1 D. n/2 6．对于一个具有 n 个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是 。 A2 C. n-1 D. n2 7．对于一个具有 n 个顶点和 e 条边的无向图，若采用邻接表表示，则所有邻接表中的结点总数是 。 A. e/2 B. e C. 2e D. n+e 8．已知一有向图的邻接表存储结构如图 7-2 所示。 （1）根据有向图的深度优先遍历算法，从顶点 v1 出发，所得到的顶点序列是 。 A. v1，v2，v3，v5，v，v2，v3，v4，v5 C. v1，v3，v4，v5，v，v4，v3，v5，v2 （2）根据有向图的广度优先遍历算法，从顶点 v1 出发，所得到的顶点序列是 。 A. v1，v2，v3，v4，v，v3，v2，v4，v5 C. v1，v2，v3，v5，v，v4，v3，v5，v2 图7-2一个有向图的邻接表存储结构 9. 判定一个有向图是否存在回路除了可以利用拓扑排序方法外，还可以利用 。 A. 求关键路径的方法 求最短路径的 Dijkstra 方法 C. 广度优先遍历算法 深度优先遍历算法 1-5.CBAAC 6-9 DCCBD 填空题 1．n 个顶点的连通图至少 条边。 2．在无向图 G 的邻接矩阵 A 中，若 A[i][j]等于 1，则 A[j][i]等于 。 3．已知图G的邻接表如图 7-3 所示，其从顶点 v1 出发的深度优先搜索序列为 ，其从顶点 v1 出发的广度优先搜索序列为 。 图7-3 G的邻接表 4．设x,y是图G中的两顶点，则（x,y）与（y,x）被认为______边，但 5.已知一个图的邻接矩阵表示，删除所有从第 i 个结点出发的边的方法是 。 6．在有向图的邻接矩阵上，由第i行可得到第______个结点的出度，而由第j列可得到第___ ____个结点的入度。①i ②j 7. 在无向图中，如果从顶点v到顶点v’有路径，则称v和v’是______的。如果对于图中的任意两个顶点vi,vj∈V，且vi和vj都是连通的，则称G为______。①连通，②连通图 1. n-1 2. 1 3. 答：① v1，v2，v3，v6，v5，v② v1，v2，v5，v4，v3，v6 4. ① ② 5. 将矩阵第 i 行全部置为 0 5. ① ② 6. ① ② 例题解析 【例7-1】对m个顶点的无向图G，采用邻接矩阵，如何判别下列有关问题： （1）图中有多少条边？ （2）任意两个顶点i和j是否有边相连？ （3）任意一个顶点的度是多少？ 解： ⑴邻接矩阵非零元素个数的总和除以2。 ⑵当A[ i,j ]≠0时，表示两顶点i,j之间有边相连。 ⑶计算邻接矩阵上顶点对应行上非零元素的个数。 1．给出如图 7-4 所示的无向图G的邻接矩阵和邻接表两种存储结构。 图7-4 无向图G 解：图 G 对应的邻接矩阵和邻接表两种存储结构分别如图所示。 2．用广度优先搜索和深度优先搜索对如图 7-5 所示的图 G 进行遍历（从顶点1出发），给出遍历序列。 解：搜索本题图的广度优先搜索的序列为：1，2，3，6，4，5，8，7，深度优先搜索的序列为：1，2，6，4，5，7，8，3。 图7-5无向图G 3．使用普里姆算法构造出如图 7-6 所示的图 G 的一棵最小生成树。 图7-6无向图G 解：使用普里姆算法构造棵最小生成树的过程如图 7-11所示。 图 7-11 普里姆算法构造最小生成树的过程 4．使用克鲁斯卡尔算法构造出如图 7-7 所示的图 G 的一棵最小生成树。 图7-7 无向图G 解：使用克鲁斯卡尔算法构造棵最小生成树的过程如图 7-12所示。 图 7-12 克鲁斯卡尔算法构造最小生成树的过程 第8章 查找 单项选择题 1.顺序查找法适合于存储结构为 的线性表。 A. 散列存储 B. 顺序存储或链接存储 C. 压缩存储 C. 索引存储 2.对线性表进行折半查找时，要求线性表的存储方式是 。 A. 顺序存储 B. 链接存储 C. 以关键字有序排序的顺序存储 D. 以关键字有序排序的链接存储 3.对有 18 个元素的有序表作二分（折半）查找，则查找A[3]的比较序列的下标为 。 A. 1.2.3 B. 9.5.2.3 C. 9.5.3 D. 9.4.2.3 4.如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采用 查找方法。 A. 分块 B. 顺序 C. 二分 D. 散列 5.有一个有序表为{2，5，7，11，22，45，49，62，71，77，90，93，120}，当折半查找值为 90 的结点时，经过 次比较后查找成功。 A. 1 B. 2 C. 4 D. 8 6.设哈希表长 m=14，哈希函数 H(key)=key % 11。表中已有 4 个结点：addr(14)=3， addr(38)=5，addr(61)=6，addr(85)=8，其余地址为空，如用线性探测再散列处理冲突，关键字为 49 的结点的地址是 。 A. 7 B. 3 C. 5 D. 4 7.在采用链接法处理冲突的开散列表上，假定装填因子a 的值为 4，则查找任一元素的平均查找长度为 。 A. 3 B.3.5 C.4 D.2.5 1-4 BCDA 5-7CAA 填空题 1.在各种查找方法中，平均查找长度与结点个数 n 无关的查法方法是 。 2.二分查找的存储结构仅限于 。 3.在散列存储中，装填因子α的值越大，则 ；α的值越小，则 。 ① 存取元素时发生冲突的可能性就越大 ② 存取元素时发生冲突的可能性就越小 4.对于二叉排序树的查找，若根结点元素的键值大于被查元素的键值，则应该在二叉树的___________上继续查找。 5.高度为8的平衡二叉树至少有_______个结点。 6. 在散列函数 H(key)=key % p 中，p 应取 。 1. 散列表查找 2. 有序的顺序存储结构 3. ① ② 4. 左子树 5. 54 6. 素数 例题解析 【例8-1】设有一组关键字{19，01，23，14，55，20，84，27，68，11，10，77}，采用哈希函数：H(key)=key % 13 ,采用开放地址法的二次探测再散列方法解决冲突，试在 0～18 的散列地址空间中对该关键字序列构造哈希表。 解：依题意，m=19，二次探测再散列的下一地址计算公式为： d=H(key) d=( d+j*j) % m d=( d-j*j) % m； j=1，2，... 其计算函数如下： H(14)=14 % 13=1 (冲突) H(14)=(1+1*1) % 19=2 H(84)=84 % 13=6 (冲突) H(84)=(6+1*1) % 19=7 (仍冲突) H(27)=27 % 13=1 (冲突) H(27)=(1+1*1) % 19=2 (冲突) H(68)=68 % 13=3 (冲突) H(10)=10 % 13=10 (冲突) H(10)=(10+1*1) % 19=11 (仍冲突) H(77)=77 % 13=12 因此：各关键字的记录对应的地址分配如下： addr(27)=0 addr(01)=1 addr(14)=2 addr(55)=3 addr(68)=4 addr(84)=5 addr(19)=6 addr(20)=7 addr(10)=9 addr(23)=10 addr(11)=11 addr(77)=12 其他地址为空。 综合题 1.设散列表为 T［0..12］，散列函数为 H（key）= key%13，给定键值序列是｛39，36，28，38，44，15，42，12，06，25｝，请画出分别用拉链法和线性探查法处理冲突时所构造的散列表，并求出在等概率情况下，这两种方法查找成功和查找失败时的平均查找长度。 解 用散列函数 H（key）= key% 13计算出键值序列的散列地址。并用探查次数表示待查键值需对散列表中键值比较次数。 键值序列：｛39，36，28，38，44，15，42，12，06，25｝ 散列地址： 0，10，2，12，5，2，3，12，6，12 （1）线性探查法处理冲突 用线性探查法处理冲突构造的散列表见表8-1所示。 表8-1 用线性探查法处理冲突构造的散列表 ASL=（1×6+2×2+3×1+9×1）/10=2.2 设待查键值 k不在散列表中：若 H（k）= k% 13= d，则从 i=d开始顺次与 T［i］位置的键值进行比较，直到遇到空位，才确定其查找失败，同时累计 k键值的比较次数，例如若 k% 13= 0，则必须将 k与 T［0］、T［1］、…、T［8］中的键值进行比较之后，发现 T［8］为空，比较次数为 9、类似地可对 k% 13=1，2，3，…，12进行分析可得查找失败的平均查找长度。 ASL =（9+8+7+6+5+4+3+2+1+1+10）/13 = 59/13 = 4.54 （2）拉链法处理冲突 用拉链法处理冲突构造的散列表见图8-2所示。 图8-2 拉链法处理冲突构造的散列表 在等概率的情况下查找成功的平均查找长度： ASL=（1×7+2×2+3×1）/10=1.4 设待查键值 k不在散列表中，若 k% 13= d。则需在 d链表中查找键值为 k的结点，直到表尾，若不存在则查找失败，设 d链表中有 i个结点，则 k需与表中键值比较 i次，查找失败的平均长度为： ASL=（1+ 0+ 2+ 1+ 0+ 1+ 1+ 0+0+0+1+0+3）/13=10/13 = 0.77 2.线性表的关键字集合{87，25，310，08，27，132，68，95，187，123，70，63，7}，共有 13 个元素，已知散列函数为：H(k) = k % 13 ，采用拉链法处理冲突。设计出这种链表结构，并计算该表的成功查找的平均查找长度。 解：依题意，得到： H(87)=87 % 13=9 H(25)=25 % 13=12 H(310)=310 % 13=11 H(08)=08 % 13=8 H(27)=27 % 13=1 H(132)=132 % 13=2 H(68)=68 % 13=3 H(95)=95 % 13=4 H(187)=187 % 13=5 H(123)=123 % 13=6 H(70)=70 % 13=5 H(63)=63 % 13=11 H(47)=47 % 13=8 采用拉链法处理冲突的链接表如图8-3 所示。成功查找的平均查找长度： ASL=(1×10+2×3)/13=16/13=1 第9章 排序 单项选择题 1.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是 。 A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序 2.设有 10000 个无序的元素，希望用最快的速度挑选出其中前 10 个最大的元素，排序方法最好选用 。 A. 起泡排序 B. 快速排序 C. 堆排序 D. 基数排序 3.在待排序的元素序列基本有序的前提下，效率最高的排序方法是 。 A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序 4.一组记录的排序码为(46，79，56，38，40，84)，则利用堆排序的方法建立的初始堆为 。 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.在下列算法中， 算法可能出现下列情况：在最后一趟开始之前，所有的元素都不在其最终的位置上。 A．堆排序 B．冒泡排序 C．插入排序 D.快速排序 6.一组记录的关键码为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为 。 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 7.一组记录的排序码为(48，16， 79，35，82，23，36，72)，按归并排序的方法对该序列进行一趟归并后的结果为 。 A. 16 48 35 79 23 82 36 72 B. 16 35 48 79 82 23 36 72 C. 16 48 35 79 82 23 36 72 D. 16 35 48 79 23 36 72 82 8.排序方法中，从未排序序列中依次取出元素与已排序序列（初始时为空）中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 。 A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序 9.排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列（初始时为空）的一端的方法，称为 。 A. 希尔排序 B. 归并排序 C. 插入排序 D. 选择排序 1-5 DCABC 6-9 CACD 填空题 1.在对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第 8 个记录 45 插入到有序表时，为寻找插入位置需比较 次。 2.对于关键字序列（12，13，11，18，60，15，7，20，25，100），用筛选法建堆，必须从键值为 的关键字开始。 3.对 n个记录的表 r[1..n]进行简单选择排序，所需进行的关键字间的比较次数为 4.在插入和选择排序中，若初始数据基本正序，则选用 ；若初始数据基本反序则选用 。 插入排序 选择排序 5.对 n 个元素的序列进行起泡排序时，最少的比较次数是 。 6. 排序不需要进行记录关键字间的比较。 1. 5 2. 60 3. n(n-1)/2 4. ① ② 5. n-1 6. 基数 综合题 1.已知序列49．38，65，97，76，13，27，请给出采用起泡排序对该序列作升序排列的每一趟的结果。 2.已知序列{503，87，512，61，908，170，7，275，653，462}，采用快速排序法对该序列作升序排序时的每一趟的结果。 3.已知序列{265，301，751，129，937，863，742，694，076，438}，采用基数排序法对该序列作升序排序时的每一趟的结果。 4.已知序列{503，17，512，908，170，7，275，653，426，154，509，612，677，765，703，94}，请给出采用希尔排序法(d1=8)对该序列作升序排序时的每一趟的结果。 5.已知序列{35，，61，135，78，29，50}，请给出采用插入排序法对该序列作升序排序时的每一趟的结果。 6.已知序列{11，18，4，3，6，15，1，9，18，8}，请给出采用归并排序法对该序列作升序排序时的每一趟的结果。 1.解：根据起泡排序法的基本思想，比较无序区中相邻关键字。按照大小关系调整其位置，本题的解法是，通过比较已知序列中相邻关键字，并根据需要调整其位置、重复此过程直到没有关键字的位置交换为止，结果正好是关键字的升序排列。 依题意，采用起泡排序法排序的各趟的结果如下： 初始：49，38、65，97，76，13，27 第一趟；38，49，65，76，13，27，97 第二趟：38，49，65，13，27，76，97 第二趟：38，49．13，27，65，76，97 第四趟：38，13，27，49，65，76，97 第五趟：13，27，38，49，65．76，97 第六趟：13，27，38，49，65，76，97 第六题无元素交换，排序结束。 2.依题意，采用快速排序法排序的各趟的结果如下： 初始：503，87，512，61，908，170，7，275，653，462 第 1 趟：[462，87，275，61，170] 503 [7，908，653，512] 第 2 趟：[170，87，275，61] 462，503 [7，908，653，512] 第 3 趟：[61，87] 170 [275] 462，503 [7，908，653，512] 第 4 趟：61 [87] 170 [275] 462，503 [7，908，653，512] 第 5 趟：61，87，170 [275] 462，503 [7，908，653，512] 第 6 趟：61，87，170，275，462，503 [7，908，653，512] 第 7 趟：61，87，170，275，462，503 [512，653] 7 [908] 第 8 趟：61，87，170，275，462，503，512 [653] 7 [908] 第 9 趟：61，87，170，275，462，503，512，653，7 [908] 第 10 趟：61，87，170，275，462，503，512，653，7，908 3.依题意，采用基数排序法排序的各趟的结果如下： 初始态：265 301 751 129 937 863 742 694 076 438 第一趟：[] [301 751] [742] [863] [694] [265] [076] [937] [438] [129] 第二趟：[301] [] [129] [937 438] [742] [751] [863 265] [076] [] [694] 第三趟：[075] [129] [265] [301] [438] [] [694] [742 751] [863] [937] 4.依题意，采用希尔排序法排序的各趟的结果如下： 初始：503，17，512，908，170，7，275，653，426，154，509，612，677，765，703，94 第 1 趟(d1=8)：426，17，509，612，170，765，275，94，503，154，512，908，677，7，703，653 第 2 趟(d2=4)：170，17，275，94，426，154，509，612，503，765，512，653，677，7，703，908 第 3 趟(d3=2)：170，17，275，94，426，154，503，612，509，653，512，765，677，7，703，908 第 4 趟(d1=1)：17，94，154，170，275，426，503，509，512，612，653，677，703，765，7，908 5.依题意，采用直接插入排序法排序的各趟的结果如下 初始：(35)，61，135，78，29，50 第一趟：（35，，)6l，135，78，29，50 第二趟：(35，61，，)135，78，29，50 第三趟：(35，6l，，135)78，29，50 第四趟：(35，61，78，，135)29，50 第五趟：(29，35，61，78，．135)50 第六趟：(29，35，50，61，78，，135) 6. 依题意，采用归并排序法排序的各趟的结果如下： 初始：11，18，4，3，6，15，1，9，18，8 第 1 趟：[11，18] [3，4] [6，15] [1，9] [8，18] 第 2 趟：[3，4，11，18] [1，6，9，15] [8，18] 第 3 趟：[3，4，11，18] [1，6，8，9，15，18] 第 4 趟：[1，3，4，6，8，9，11，12，18，18] 第 4 趟归并完毕，则排序结束。下载本文
（1）画出二叉树表示； 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 e a f d g c j h i b
在等概率的情况下，查找成功的平均查找长度下标 0 1 2 3 4 5 6 7 8 9 10 11 12 T［0..12］ 39 12 28 15 42 44 06 25 36 38 查找成功探查次数 1 3 1 2 2 1 1 9 1 1 查找失败探查次数 9 8 7 6 5 4 3 2 1 1 2 1 10
