资源描述
数据构造与算法
习题册
（课后某些参照答案）
《数据构造与算法》课程组
目录
课后习题部分
第一章 绪论 1
第二章 线性表 3
第三章 栈和队列 5
第四章 串 8
第五章 数组和广义表 10
第六章 树和二叉树 13
第七章 图 16
第九章 查找 20
第十章 排序 23
第一章 绪论
一. 填空题
1. 从逻辑关系上讲，数据构造类型重要分为 集合 、线性构造、树构造和 图构造。
2. 数据存储构造重要有 顺序存储和 链式存储 两种基本办法，无论哪种存储构造，都要存储两方面内容：数据元素 和 数据元素之间关系 。
3. 算法具备五个特性，分别是 有穷性 、拟定性、可行性、输入 、输出 。
4. 算法设计规定中健壮性指是 算法在发生非法操作时可以作出解决特性。
二. 选取题
1. 顺序存储构造中数据元素之间逻辑关系是由 C 表达，链接存储构造中数据元素之间逻辑关系是由 D 表达。
A 线性构造 B 非线性构造 C 存储位置 D 指针
2. 假设有如下遗产继承规则：丈夫和妻子可以互相继承遗产；子女可以继承爸爸或妈妈遗产；子女间不能互相继承。则表达该遗产继承关系最适当数据构造应当是 B 。
A 树 B 图 C 线性表 D 集合
3. 算法指是 A 。
A 对特定问题求解环节一种描述，是指令有限序列。
B 计算机程序 C 解决问题计算办法 D 数据解决
三. 简答题
1. 分析如下各程序段，并用大O记号表达其执行时间。
(1) (2)
i=1;k=0; i=1;k=0;
While(i<n-1) do
{ {
k=k+10*i； k=k+10*i；
i++； i++;
} }while(i<=n)
⑴ 基本语句是k=k+10*i，共执行了n-2次，因此T(n)=O(n)。
⑵ 基本语句是k=k+10*i，共执行了n次，因此T(n)=O(n)。
2. 设有数据构造（D，R），其中D={1，2，3，4，5，6}，R={(1,2),(2,3),(2,4),(3,4),(3,5),(3,6),(4,5),(4,6)}。试画出其逻辑构造图并指出属于何种构造。
其逻辑构造图如下所示，它是一种图构造。
3. 求多项式A(x)算法可依照下列两个公式之一来设计：
⑴ A(x)=anxn+an-1xn-1+…+a1x+a0
⑵ A(x)=(…(anx+an-1)x+…+a1)x)+a0
依照算法时间复杂度分析比较这两种算法优劣。
第二种算法时间性能要好些。第一种算法需执行大量乘法运算，而第二种算法进行了优化，减少了不必要乘法运算。
第二章 线性表
一. 填空题
1. 在顺序表中，等概率状况下，插入和删除一种元素平均需移动 表长一半 个元素，详细移动元素个数与 表长 和 插入位置 关于。
2. 在一种长度为n顺序表第i（1≤i≤n+1）个元素之前插入一种元素，需向后移动
n-i+1 个元素，删除第i（1≤i≤n）个元素时，需向前移动 n-i 个元素。
3. 在单循环链表中，由rear指向表尾，在表尾插入一种结点s操作顺序是 s->next =rear->next；rear->next =s；rear =s;；删除开始结点操作顺序为q=rear->next->next；rear->next->next=q->next；delete q；。
二. 选取题
1.数据在计算机存储器内表达时物理地址与逻辑地址相似并且是持续，称之为： C
A存储构造 B逻辑构造 C顺序存储构造 D链式存储构造
2. 在n个结点顺序表中，算法时间复杂度是O（1）操作是： A
A 访问第i个结点（1≤i≤n）和求第i个结点直接前驱（2≤i≤n）
B 在第i个结点后插入一种新结点（1≤i≤n）
C 删除第i个结点（1≤i≤n） D 将n个结点从小到大排序
3. 线性表L在 B 状况下合用于使用链式构造实现。
A 需经常修改L中结点值 B 需不断对L进行删除插入
C L中具有大量结点 D L中结点构造复杂
4. 单链表存储密度 C
A不不大于1 B等于1 C不大于1 D不能拟定
三. 判断题
1. 线性表逻辑顺序和存储顺序总是一致。 F
2. 线性表顺序存储构造优于链接存储构造。 F
3. 设p，q是指针，若p=q，则*p=*q。 F
4. 线性构造基本特性是：每个元素有且仅有一种直接前驱和一种直接后继。 F
四. 简答题
1. 分析下列状况下，采用何种存储构造更好些。
(1)若线性表总长度基本稳定，且很少进行插入和删除操作，但规定以最迅速度存取线性表中元素。
(2)如果n个线性表同步并存，并且在解决过程中各表长度会动态发生变化。
(3)描述一种都市设计和规划。
⑴ 应选用顺序存储构造。很少进行插入和删除操作，因此空间变化不大，且需要迅速存取，因此应选用顺序存储构造。
⑵ 应选用链式存储构造。链表容易实现表容量扩充，适合表长度动态发生变化。
⑶ 应选用链式存储构造。由于一种都市设计和规划涉及活动诸多，需要经常修改、扩充和删除各种信息，才干适应不断发展需要。而顺序表插入、删除效率低，故不适当。
五. 算法设计
1. 已知数组A[n]中元素为整型，设计算法将其调节为左右两某些，左边所有元素为奇数，右边所有元素为偶数，并规定算法时间复杂度为O(n)。
2. 线性表存储在整型数组A[arrsize]前elenum 个单元中，且递增有序。编写算法，将元素x插入到线性表恰当位置上，以保持线性表有序性，并且分析算法时间复杂度。
int insert (datatype A[],int *elenum,datatype x) /*设elenum为表最大下标*/
{if (*elenum==arrsize-1) return 0; /*表已满，无法插入*/
else {i=*elenum;
while (i>=0 && A[i]>x) /*边找位置边移动*/
{A[i+1]=A[i];
i--;
}
A[i+1]=x; /*找到位置是插入位下一位*/
(*elenum)++;
return 1; /*插入成功*/
}
}
O（n）
第三章 栈和队列
一. 填空题
1. 设有一种空栈，栈顶指针为1000H，既有输入序列为1. 2. 3. 4. 5， 通过push，push，pop，push，pop，push，push后，输出序列是 23 ，栈顶指针为 1003H 。
2. 栈普通采用两种存储构造是 顺序栈 、链栈 ；其鉴定栈空条件分别是 TOP=-1 、 TOP=NULL ，鉴定栈满条件分别是 TOP=数组长度 、存储空间满 。
3. 栈 可作为实现递归函数调用一种数据构造。
4. 表达式a*(b+c)-d后缀表达式是 abc+*d- 。
二. 选取题
1. 若一种栈输入序列是1，2，3，…，n，输出序列第一种元素是n，则第i个输出元素是 D 。
A 不拟定 B n-i C n-i-1 D n-i+1
2. 设栈S和队列Q初始状态为空，元素e1. e2. e3. e4. e5. e6依次通过栈S，一种元素出栈后即进入队列Q，若6个元素出队顺序是e2. e4. e3. e6. e5. e1，则栈S容量至少应当是 C 。
A 6 B 4 C 3 D 2
3. 一种栈入栈序列是1，2，3，4，5，则栈不也许输出序列是 C 。
A 54321 B 45321 C 43512 D 12345
三. 判断题
1. 有n个元素依次进栈，则出栈序列有(n-1)/2种。 F
2. 栈可以作为实现过程调用一种数据构造。 T
3. 在栈满状况下不能做进栈操作，否则将产生“上溢”。 T
4. 在循环队列中，front指向队头元素前一种位置，rear指向队尾元素位置，则队满条件是 front=rear。 F
四. 简答题
1. 设有一种栈，元素进栈顺序为A，B，C，D，E，能否得到如下出栈序列，若能，请写出操作序列，若不能，请阐明因素。
⑴ C，E，A，B，D
⑵ C，B，A，D，E
⑴不能，由于在C、E出栈后，A一定在栈中，并且在B下面，不也许先于B出栈
⑵可以，设Ｉ为进栈操作，Ｏ为入栈操作，则其操作序列为IIIOOOIOIO。
2. 在操作序列push(1). push(2). pop. push(5). push(7). pop. push(6)之后，栈顶元素和栈底元素分别是什么？（push(k)表达k入栈，pop表达栈顶元素出栈。）
栈顶元素为6，栈底元素为1。
3. 在操作序列EnQueue(1). EnQueue(3). DeQueue. EnQueue(5). EnQueue(7). DeQueue. EnQueue(9)之后，队头元素和队尾元素分别是什么？（EnQueue(k)表达整数k入队，DeQueue表达队头元素出队）。
队头元素为5，队尾元素为9。
4. 简述如下算法功能（栈元素类型SElemType为int）。
(1) status algo1(Stack S,int e)
{
Stack T；int d；InitStack(T);
while(!StackEmpty(S)){
Pop(S,d);
if(d!=e) Push(T,d);
}
while(!StackEmpty(T)){
Pop(T,d)； Push(S,d);
}
}//S中如果存在e，则删除它。
(2) void algo2(Queue &Q)
{
Stack S； int d； InitStack(S);
while(!QueueEmpty(Q))
{
DeQueue(Q，d)；Push(S，d);
}
while(!StackEmpty(S))
{
Pop(S，d)；EnQueue(Q，d);
}
}//队列逆置
五. 算法设计
1. 试写一种鉴别表达式中开、闭括号与否配对浮现算法
BOOL BracketCorrespondency(char a[])
{
int i=0;
Stack s;
InitStack(s);
ElemType x;
while(a[i]){
switch(a[i]){
case '(':
Push(s,a[i]);
break;
case '[':
Push(s,a[i]);
break;
case ')':
GetTop(s,x);
if(x=='(') Pop(s,x);
else return FALSE;
break;
case ']':
GetTop(s,x);
if(x=='[') Pop(s,x);
else return FALSE;
break;
default:
break;
}
i++;
}
if(s.size!=0) return FALSE;
return TRUE;
}
2. 假设称正读和反读都相似字符序列为“回文”，例如，‘abba’和‘abcba’是回文，‘abcde’和‘ababab’则不是回文。试写一种算法鉴别读入一种以‘@’为结束符字符序列与否是“回文”。
Status SymmetryString(char* p)
{
Queue q;
if(!InitQueue(q)) return 0;
Stack s;
InitStack(s);
ElemType e1,e2;
while(*p){
Push(s,*p);
EnQueue(q,*p);
p++;
}
while(!StackEmpty(s)){
Pop(s,e1);
DeQueue(q,e2);
if(e1!=e2) return FALSE;
}
return OK;
}
第四章 串
一. 填空题
1. 不包括任何字符（长度为0）串 称为空串；由一种或各种空格（仅由空格符）构成串 称为空白串。
2. 设S=“A;/document/Mary.doc”，则strlen(s)= 20 ，“/”字符定位位置为 3 。
3. 若n为主串长，m为子串长，则串典型模式匹配算法最坏状况下需要比较字符总次数为 (n-m+1)*m 。
二. 选取题
1. 串是一种特殊线性表，其特殊性体当前： （ B ）
A可以顺序存储 B数据元素是一种字符
C可以链式存储 D数据元素可以是各种字符
2. 设有两个串p和q，求q在p中初次浮现位置运算称作：（ B ）
A连接 B模式匹配 C求子串 D求串长
3. 设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串连接串，
subs(s，i，j)返回串s从序号i开始j个字符构成子串，len(s)返回串s长度，则con(subs(s1，2，len(s2))，subs(s1，len(s2)，2))成果串是：（ D ）
A ‘BCDEF’ B ‘BCDEFG’ C ‘BCPQRST’ D ‘BCDEFEF’
4. 若串S=”software”，其子串数目是（ B ）。
A 8 B 37 C 36 D 9
三. 计算题
1. 设s=’I AM A STUDENT’，t=’GOOD’，q=’WORKER’，求：
1）Replace(s,’STUDENT’,q) 2）Concat(t,SubString(s,7,8)))
1、Replace(s,’STUDENT’,q)＝’I AM A WORKER’
2、由于SubString(s,7,8)＝‘ STUDENT’Concat(t,SubString(s,7,8))＝’GOOD STUDENT’
四. 算法设计
1. 运用C库函数strlen，strcpy（或strncpy）写一种算法void StrDelete(char *S,int t,int m) ，删除串S中从位置i开始持续m个字符。若i≥strlen(S)，则没有字符被删除；若i+m≥strlen(S)，则将S中从位置i开始直至末尾字符均被删去。
提示：strlen是求串长(length)函数：int strlen(char s)； //求串长度
strcpy是串复制(copy)函数：char *strcpy(char to,char from)；//该函数将串from复制到串to中，并且返回一种指向串to开始处指针。
void StrDelete(char *S，int i ,int m)
{ //串删除
char Temp[Maxsize];//定义一种暂时串
if(i+m<strlen(S))
{
strcpy (Temp，&S[i+m]);//把删除字符后来字符保存到暂时串中
strcpy( &S[i],Temp);//用暂时串中字符覆盖位置i之后字符
}
else if(i+m>=strlen(S)&& i<strlen(S))
{
strcpy(&S[i],"\0");//把位置i元素置为'\0'，表达串结束
}
}
第五章 数组和广义表
一. 填空
1. 假设有二维数组A6×8，每个元素用相邻6个字节存储，存储器按字节编址。已知A起始存储位置（基地址）为1000，则数组A体积（存储量）为 288 ；末尾元素A57第一种字节地址为 1282 ；若按行存储时，元素A14第一种字节地址为 1072；若按列存储时，元素A47第一种字节地址为 1276 。
2. 三元素组表中每个结点相应于稀疏矩阵一种非零元素，它包具有三个数据项，分别表达该元素行下标 、 列下标 和 元素值 。。
3. 广义表((a)，(((b),c)),(d))长度是 3 ，深度是 4 ，表头是 (a) ，表尾是(((b),c)),(d) 。
4. 已知广义表LS=(a，(b，c，d)，e)，用Head和Tail函数取出LS中原子b运算是Head(Head(Tail(LS))) 。
二. 选取题
1. 假设有60行70列二维数组a[1…60，1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列元素a[32,58]存储地址为 ( A )。（无第0行第0列元素）
A 16902 B 16904 C 14454 D 答案A，B，C均不对
2. 设矩阵A是一种对称矩阵，为了节约存储，将其下三角某些按行序存储在一维数组B[ 1，n(n-1)/2 ]中，下三角某些中任一元素ai,j(i≤j)，在一维数组B中下标k值是：( B )
A i(i-1)/2+j-1 B i(i-1)/2+j C i(i+1)/2+j-1 Di(i+1)/2+j
3. 一种n*n对称矩阵，用压缩存储办法解决其对称性质后存储，则其容量为：( C )。
A n*n B n*n/2 C (n+1)*n/2 D (n+1)*(n+1)/2
三. 计算题
1. 设有一种二维数组A[m][n]，假设A[0][0]存储位置在644，A[2][2]存储位置在676，每个元素占一种空间，问A[3][3]存储在什么位置？写出计算过程。
(676-644)/1=32
A[2][2]地址相对A[0][0]偏移量为32，则A[3][3]相较于A[0][0]偏移量为32*3/2=48
A[3][3]地址为48+644=692
2. 设A[9][9]是一种10*10对称矩阵，采用压缩存储方式存储其下三角某些，已知每个元素占用两个存储单元，其第一种元素A[0][0]存储位置在1000，求下面问题计算过程及成果：
给出A[4][5]存储位置。
A[4][5]是上三角某些，因此存在 A [5] [4]
若以行序为主序，则地址为1000+2（5（1+5）/ 2+4）=1036
若以列序为主序，则地址为1000+2（4（10+7）/ 2+5）=1062
给出存储位置为1080元素下标。
i(i+1)/2+j或j(10+10-j+1)/2+i=40
得i=9，j=4或i=8 j=5，A [8] [5] 或 A [9] [4]
3. 一种稀疏矩阵如图所示，则相应三元组线性表是什么？其相应十字链表是什么？
0 0 2 0
3 0 0 0
0 0 -1 5
0 0 0 0
4. 下列各三元组表分别表达一种稀疏矩阵，试写出它们稀疏矩阵。
0 2 0 0
12 0 0 0
3 0 0 0
0 0 0 4
0 0 6 0
16 0 0 0
四. 算法设计
1. 设计一种算法，计算一种三元组表表达稀疏矩阵对角线元素之和。
2. 若在矩阵A中存在一种元素ai,j（0≤i≤n-1，0≤j≤m-1），该元素是第i行元素中最小值且又是第j列元素中最大值，则称此元素为该矩阵一种鞍点。假设以二维数组存储矩阵A，试设计一种求该矩阵所有鞍点算法，并分析最坏状况下时间复杂度
void Saddle(int A[m][n])
//A是m*n矩阵,本算法求矩阵A中马鞍点.
{int max[n]={0}，//max数组存储各列最大值元素行号,初始化为行号0;
min[m]={0}，//min数组存储各行最小值元素列号,初始化为列号0;
i，j;
for(i=0;i<m;i++) //选各行最小值元素和各列最大值元素.
{for(j=0;j<n;j++)
{if(A[max[j]][j]<A[i][j]) max[j]=i； //修改第j列最大元素行号
if(A[i][min[i]]>A[i][j]) min[i]=j； //修改第i行最小元素列号.
}
for (i=0;i<m;i++)
{j=min[i]； //第i行最小元素列号
if(i==max[j])printf(“A[%d][%d]是马鞍点，元素值是%d”,i,j,A[i][j])；
}
}
}// Saddle
分析算法，外层for循环共执行m次，内层第一种for循环执行n次，第二个for循环最坏状况下执行m次，因此，最坏状况下时间复杂度为Ｏ(mn+mm)。
第六章 树和二叉树
一. 填空题
1. 树是n（n≥0）结点有限集合。在一棵空树中有 0 个元素；在一棵非空树中，有 且仅有一种 个根结点，别的结点提成m（m＞0）个 互不相交 集合，每个集合都是根结点子树。
2. 一棵二叉树第i（i≥1）层最多有 2i-1个结点；一棵有n（n>0）个结点满二叉树共有 (n+1)/2 个叶子结点和 (n-1)/2 个非终端结点。
3. 设深度为k二叉树上只有度为0和度为2结点，该二叉树结点数也许达到最大值是 2k-1 ，最小值是 2k-1 。
4. 深度为k二叉树中，所含叶子个数最多为 2k-1 。
5. 在顺序存储二叉树中编号为i和j两个结点处在同一层条件为：
二. 选取题
1. 前序遍历和中序遍历成果相似二叉树是（ D ）。
A 根结点无左孩子二叉树 B 根结点无右孩子二叉树
C 所有结点只有左子树二叉树 D 所有结点只有右子树二叉树
2. 序存储办法将完全二叉树中所有结点逐级存储在数组A[1] ~ A[n]中，结点A[i]若有左子树，则左子树根结点是（ D ）。
A A[2i-1] B A[2i+1] C A[i/2] D A[2i]
3. 完全二叉树中任一结点，若其右分支下子孙最大层次为h，则其左分支下子孙最大层次为（ C ）。
A h B h+1 C h或h+1 D 任意
4. 在线索二叉树中，一种结点是叶子结点充要条件为（ C ）。
A 左线索标志为0，右线索标志为1 B 左线索标志为1，右线索标志为0
C 左. 右线索标志均为0 D 左. 右线索标志均为1
5. 由权值为{3，8，6，2，5}叶子结点生成一棵哈夫曼树，其带权途径长度为（ C ）。
A 24 B 48 C 53 D 72
三. 简答题
1. 已知二叉树中序和后序序列分别为CBEDAFIGH和CEDBIFHGA，请构造出此二叉树，并写出此树后序遍历序列。
2. 将下图所示树转换为二叉树，
3. 图5-17所示二叉树转换为树或森林
4. 已知某字符串S中共有8种字符[A,B,C,D,E,F,G,H]，分别浮现2次. 1次. 4次. 5次. 7次. 3次. 4次和9次。
1）试构造出哈夫曼编码树，并对每个字符进行编码
E
H
2）问该字符串编码至少有多少位。
C
G
D
F
B
A
A:00000 B:00001 C:100 D:001 E:11 F:0001 G:101 H:01
其带权途径长度=2×5+1×5+3×4+5×3+9×2+4×3+4×3+7×2=98，因此，该字符串编码长度至少为98位。
四. 算法设计
1. 设计算法求二叉树结点个数
2. 以二叉链表为存储构造，编写算法求二叉树中结点x双亲
3. 编写算法互换二叉树中所有结点左右子树。
第七章 图
一. 填空题
1. 设无向图G中顶点数为n，则图G至少有 0 条边，至多有 n(n-1)/2 条边；若G为有向图，则至少有 0 条边，至多有 n(n-1) 条边。
2. 任何连通图连通分量只有一种，即是 它自身
3. 若一种有向图由邻接矩阵表达，则计算第j个顶点入度办法是 求矩阵第j列元素之和
4. 图深度优先遍历类似于树 先根 遍历，广度优先遍历类似于树 层序 遍历。
5. 对于具有n个顶点e条边连通图，运用Prim算法求最小生成树时间复杂度为Ｏ(n2)，运用Kruskal算法求最小生成树时间复杂度为 Ｏ(elog2e) 。
二. 选取题
1. 在一种无向图中，所有顶点度数之和等于所有边数（ C ）倍。
A 1/2 B 1 C 2 D 4
2. n个顶点强连通图至少有（ A ）条边。
A n B n+1 C n-1 D n×(n-1)
3. 含n 个顶点连通图中任意一条简朴途径，其长度不也许超过（ C ）。
A 1 B n/2 C n-1 D n
4. 对于一种具备n个顶点无向图用邻接矩阵存储，则该矩阵大小是（ D ）。
A n B (n-1)2 C n-1 D n2
5. 设无向图G=(V，E)和G' =(V'，E' )，如果G' 是G生成树，则下面说法中错误是（ B ）。
A G' 为 G子图 B G' 为 G连通分量
C G' 为G极小连通子图且V= V' D G' 是G一种无环子图
6. 鉴定一种有向图与否存在回路除了可以运用拓扑排序办法外，还可以用（ D ）。
A 求核心途径办法 B 求最短途径办法
C 广度优先遍历算法 D 深度优先遍历算法
7. 下面关于工程筹划AOE网论述中，不对的是（ B ）
A 核心活动不按期完毕就会影响整个工程完毕时间
B 任何一种核心活动提前完毕，那么整个工程将会提前完毕
C 所有核心活动都提前完毕，那么整个工程将会提前完毕
D 某些核心活动若提前完毕，那么整个工程将会提前完
三. 计算题
1. 已知一种连通图如图所示，试给出图邻接矩阵和邻接表存储示意图，若从顶点v1出发对该图进行遍历，分别给出一种按深度优先遍历和广度优先遍历顶点序列。
邻接矩阵表达如下：
深度优先遍历序列为：v1 v2 v3 v5 v4 v6
广度优先遍历序列为：v1 v2 v4 v6 v3 v5
邻接表表达如右：
2. 已知无向图G邻接表如下图所示，分别写出从顶点1出发深度遍历和广度遍历序列，并画出相应生成树。
深度优先遍历序列为：1，2，3，4，5，6
相应生成树为：
广度优先遍历序列为：1，2，4，3，5，6
相应生成树为：
3. 下图所示是一种无向带权图，请分别按Prim算法和Kruskal算法求最小生成树。
4. 如右图所示有向网图，运用Dijkstra算法求从顶点v1到其她各顶点最短途径。
从源点v1到其她各顶点最短途径如下表所示。
源点 终点 最短途径 最短途径长度
v1 v3 v1 v3 15
v1 v5 v1 v5 15
v1 v2 v1 v3 v2 25
v1 v6 v1 v3 v2 v6 40
v1 v4 v1 v3 v2 v4 45
5. 已知一种AOV网如下图所示，写出所有拓扑序列。
拓扑序列为：v0 v1 v5 v2 v3 v6 v4、v0 v1 v5 v2 v6 v3 v4、v0 v1 v5 v6 v2 v3 v4。
四. 算法设计
1. 设计算法，将一种无向图邻接表转换成邻接矩阵。
2. 设计算法，计算图中出度为零顶点个数。
3. 已知一种有向图邻接表，编写算法建立其逆邻接表
第九章 查找
一. 填空题
1. 顺序查找技术适合于存储构造为 顺序和链式存储 线性表，而折半查找技术合用于存储构造为 顺序存储 线性表，并且表中元素必要是 按核心码有序 。
2. 折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素 28，6，12，20 比较大小。
3. 在各种查找办法中，平均查找长度与结点个数n无关查找办法是 散列（哈希）查找 。
4. 为了能有效地应用哈希查找技术，必要解决两个问题是 构造散列函数 和 解决冲突。
5. 有一种表长为m散列表，初始状态为空，现将n（n<m）个不同核心码插入到散列表中，解决冲突办法是用线性探测法。如果这n个核心码散列地址都相似，则探测总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。
二. 选取题
1. 静态查找与动态查找主线区别在于（ B ）。
A 它们逻辑构造不同样 B 施加在其上操作不同
C 所包括数据元素类型不同样 D 存储实现不同样
2. 用n个键值构造一棵二叉排序树，其最低高度为（ D ）。
A n/2 B n C log2n D log2n+1
3. 散列技术中冲突指是（ D ）。
A 两个元素具备相似序号 B 两个元素键值不同，而其她属性相似
C 数据元素过多 D 不同键值元素相应于相似存储地址
4. 链表合用于 A 查找
A 顺序 B 二分法 C 顺序，也能二分法 D 随机
三. 简答题
1. 分别画出在线性表（a，b，c，d，e，f，g）中进行折半查找核心码e和g过程。
见下页
2. 画出对长度为10有序表进行折半查找鉴定树，并求其等概率时查找成功平均查找长度。
第1题答案
3. 设哈希（Hash）表地址范畴为0～17，哈希函数为：H（K）＝K MOD 16。
K为核心字，用线性探测法再散列法解决冲突，输入核心字序列：
（10，24，32，17，31，30，46，47，40，63，49）
构造出Hash表，试回答下列问题：
(1)画出哈希表达意图；
(2)若分别查找核心字63和60，分别需要依次与哪些核心字进行比较？
(3)假定每个核心字查找概率相等，求查找成功时平均查找长度。
解： （1）画表如下：
0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
32
17
63
49
24
40
10
30
31
46
47
（2） 查找63,一方面要与H(63)=63%16=15号单元内容比较，即63 vs 31 ,no;然后顺移，与46,47,32,17,63相比，一共比较了6次！
（3）查找60,一方面要与H(60)=60%16=12号单元内容比较，但由于12号单元为空（应当有空标记），因此应当只比较这一次即可。
（4） 对于黑色数据元素，各比较1次；共6次；对红色元素则各不相似，要记录移位位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，因此ASL=1/11（6＋2＋3×3）＝17/11=1.≈1.55
四. 算法设计
1. 编写算法求给定结点在二叉排序树中所在层数
2. 一种鉴别给定二叉树与否为二叉排序树算法，设此二叉树以二叉链表作存储构造。且树中结点核心字均不同。
解：注意仔细研究二叉排序树定义。易犯典型错误是按下述思路进行鉴别：“若一棵非空二叉树其左、右子树均为二叉排序树，且左子树根值不大于根结点值，又根结点值不不不大于右子树根值，则是二叉排序树”
（刘注：即不能只判断左右孩子状况，还要判断左右孩子与双亲甚至根结点比值也要遵循（左小右大）原则）。
若要采用递归算法，建议您采用如下函数首部：
bool BisortTree(BiTree T， BiTree&PRE)，其中PRE为指向当前访问结点前驱指针。
（或者直接存储前驱数值，随时与当前根结点比较）
一种美丽算法设计如下：
int last=0，flag=1； // last是全局变量，用来记录前驱结点值，只要每个结点都比前驱大就行。
int Is_BSTree(Bitree T) //判断二叉树T与否二叉排序树，是则返回1，否则返回0
{
if(T->lchild&&flag) Is_BSTree(T->lchild)；
if(T->data<last) flag=0； //与其中序前驱相比较，flag=0表达当前结点比直接前驱小，则及时返回
last=T->data；
if(T->rchild&&flag) Is_BSTree(T->rchild)；
return flag；
}//Is_BSTree
第十章 排序
一. 填空题
1. 排序办法有诸各种， 插入排序 法从未排序序列中依次取出元素，与已排序序列中元素作比较，将其放入已排序序列对的位置上。 选取排序 法从未排序序列中挑选元素，并将其依次放入已排序序列一端。互换排序是对序列中元素进行一系列比较，当被比较两元素为逆序时，进行互换； 冒泡排序 和 迅速排序 是基于此类办法两种排序办法，而 迅速排序是比冒泡排序效率更高办法； 堆排序 法是基于选取排序一种办法，是完全二叉树构造一种重要应用。
2. 一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻找插入位置需比较 3 次。
3. 对n个待排序记录序列进行迅速排序，所需要
展开阅读全文
浙ICP备2021020529号-1 | 浙B2-20240490 
