数据结构练习
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
习题1 绪论
一、基本内容
数据、数据元素、数据对象、数据结构、存储结构和数据类型等概念术语的确定含义;算法设计的基本要求以及从时间和空间角度分析算法的
方法
快递客服问题件处理详细方法山木方法pdf计算方法pdf华与华方法下载八字理论方法下载
。 二、要点:
1. 熟悉各名词、术语的含义，掌握基本概念，特别是数据的逻辑结构和存储结构 2(理解算法五个要素的确切合义: 动态有穷性(能执行结束); 确定性(对于相同的输入执行相同的路径);有输入;有输出;可行性(用以描述算法的操作都是可以通过已经实现的基本的运算执行有限次来实现的)。
3. 掌握计算语句频度和估算算法时间复杂度的方法。
1.1 选择题
、数据信息在1. 数据结构是一门研究非数值计算的程序设计问题中,数据元素的?
计算机中的? 以及一组相关的运算等的课程。
? A(操作对象 ,(计算方法 ,(逻辑结构 ,(数据映象
? A(存储结构 ,(关系 ,(运算 ,(算法 2. 数据结构DS(Data Struct)可以被形式地定义为DS=(D，R)，其中D是? 的有限集合，R是D上的? 有限集合。
? A(算法 ,(数据元素 ,(数据操作 ,(数据对象
? A(操作 ,(映象 ,(存储 ,(关系 3. 在数据结构中，从逻辑上可以把数据结构分成 。
A(动态结构和静态结构 ,(紧凑结构和非紧凑结构
,(线性结构和非线性结构 ,(内部结构和外部结构
1
4. 算法分析的目的是? ，算法分析的两个主要方面是? 。
? A. 找出数据结构的合理性 B. 研究算法中的输入和输出的关系
C. 分析算法的效率以求改进 D. 分析算法的易懂性和文档性
? A. 空间复杂性和时间复杂性 B. 正确性和简明性
C. 可读性和文档性 D. 数据复杂性和程序复杂性 5. 计算机算法指的是? ，它必具备输入、输出和? 等五个特性。
? A. 计算方法 B. 排序方法
C. 解决问题的有限运算序列 D. 调度方法
? A. 可行性、可移植性和可扩充性 B. 可行性、确定性和有穷性
C. 确定性、有穷性和稳定性 D. 易读性、稳定性和安全性
1.2 填空题(将正确的答案填在相应的空中)
1(数据结构的三个要点是 数据元素的逻辑结构、数据在计算机中的存储结构和数据的运算。
1. 数据逻辑结构包括 线性结构、树形结构、图形结构三种类型，树形结构和图形结构合称为 非线性结构。
2. 在线性结构中，第一个结点 没有 前驱结点，其余每个结点有且只有1 个前驱结点;最后一个结点 没有 后续结点，其余每个结点有且只有 1 个后续结点。 3. 在树形结构中，树根结点 没有 前驱结点，其余每个结点有且只有 1 个直接前驱结点，叶子结点 没有 后续结点，其余每个结点的直接后续结点可以 任意多个 。 4. 在图形结构中，每个结点的前驱结点数和后续结点数可以 任意多个。 5. 线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多 关系，图形结构中元素之间存在 多对多 关系。
2
6. 算法的五个重要特性是有穷性、确定性、可行性、输入、输出。
227. 分析下面算法(程序段)，给出最大语句频度:n ， 时间复杂度:. O (n)。 for (i=0;i
1
while (x>=(y+1)*(y+1))
y++; ? T(n)=n 1/2 ? T(n)=O(n 1/2) ? 最坏的情况是y=0，那么循
1/2环的次数是n 次，这是一个按平方根阶递增的函数。
(4) x=91; y=100;
while(y>0)
if(x>100) {x=x-10;y--;}
else x++; ?T(n)=O(1) ? 这个程序总共循环运行了1000次，但是我们看到n没有? 没有。这段程序的运行是和n无关的，只是一个常数阶的函数。 4、算法的时间复杂度仅与问题的规模相关吗?
No, 事实上，算法的时间复杂度不仅与问题的规模相关，还与输入实例中的元素取值等相关，但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。
我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。
习题2 线性表
一、基本内容
线性表的逻辑结构定义和各种存储结构的描述方法;在线性表的两类存储结构(顺序的和链式的)上实现基本操作;一元多项式的表示及相加。
二、学习要点
1(了解线性表的逻辑结构特性是数据元素之间存在着线性关系，在计算机中表示这种关系的两类不同的存储结构是顺序存储结构和链式存储结构。用前者表示的线性表简称为顺序表，用后者表示的线性表简称为链表。
2(熟练掌握这两类存储结构的描述方法，如一维数组中一个区域的上、下界和长度之间的变换
公式
小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载
，链表中指针P和结点p的对应关系(结点p一,next是结点P的后继
5
等)，链表中的头结点、头指针和首元结点的区别及循环链表、双向链表的特点等。链表是本章的重点和难点。扎实的指针操作和内存动态分配的编程技术是学好本章的基本要求。
3(熟练掌握线性表在顺序存储结构上实现基本操作:查找、插入和删除的算法。
4(熟练掌握在各种链表结构中实现线性表操作的基本方法，能在实际应用中选用适当的链表结构。
5(从时间和空间复杂度的角度综合比较线性表两种存储结构的不同特点及其适用场合。
2.1 单项选择题
1. 一个向量(即一批地址连续的存储单元)第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是__ __。
A. 110 B. 108 C. 100 D. 120 2. 线性表的顺序存储结构是一种__ _的存储结构，而链式存储结构是一种__ _的存储结构。
A(随机存取 B(索引存取 C(顺序存取 D(散列存取 3. 线性表的逻辑顺序与存储顺序总是一致的，这种说法__ _。
A. 正确 B. 不正确
4. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址__ _。
A. 必须是连续的 B. 部分地址必须是连续的
C. 一定是不连续的 D. 连续或不连续都可以
5. 在以下的叙述中，正确的是__ _。
线性表的顺序存储结构优于链表存储结构
线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
6
线性表的链表存储结构适用于频繁插入/删除数据元素的情况
线性表的链表存储结构优于顺序存储结构
6. 每种数据结构都具备三个基本运算:插入、删除和查找，这种说法__ _。
A. 正确 B. 不正确
7. 不带头结点的单链表head为空的判定条件是____。
A. head= =NULL B. head->next= =NULL
C. head->next= =head D. head!=NULL
8. 带头结点的单链表head为空的判定条件是____。
A. head= =NULL B. head->next= =NULL
C. head->next= =head D. head!=NULL
9. 非空的循环单链表head的尾结点(由p所指向)满足____。
A. p->next= =NULL B. p= =NULL
C. p->next= =head D. p= =head
10. 在双向循环链表的p所指结点之后插入s所指结点的操作是____。
A. p->right=s; s->left=p; p->right->left=s; s->right=p->right;
B. p->right=s; p->right->left=s; s->left=p; s->right=p->right;
C. s->left=p; s->right=p->right; p->right=s; p->right->left=s;
D. s->left=p; s->right=p->right; p->right->left=s; p->right=s; 11.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入
s结点，则执行_。
A. s->next=p->next; p->next=s; B. p->next=s->next; s->next=p;
B. q->next=s; s->next=p; C. p->next=s; s->next=q; 12. 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行
7
____。
A. s->next=p; p->next=s; B. s->next=p->next; p->next=s;
C. s->next=p->next; p=s; C. p->next=s; s->next=p;
13. 在一个单链表中，若删除p所指结点的后续结点，则执行____。
A. p->next= p->next->next; B. p= p->next; p->next= p->next->next;
C. p->next= p->next; D. p= p->next->next;
14. 从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较____个结点。
A. n B. n/2 C. (n-1)/2 D. (n+1)/2
15. 在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是__ __。
2A. O(1) B. O(n) C. O (n) D. O (nlogn) 2
16. 给定有n个元素的向量，建立一个有序单链表的时间复杂度是__ __。
2A. O(1)) B. O(n) C. O (n) D. O (n*logn) 2
2.2 填空题(将正确的答案填在相应的空中)
1. 对于顺序表(采用顺序存储结构的线性表) (a，a，„, a)，设L表示一个元素12n
占用的存储单元个数，LOC(a)表示线性表第i个元素的地址，已知第1个元素的地址i
为LOC(a)，则LOC(a)= 1i
2. 向一个长度为n的顺序表的第i个元素(1?i?n+1)之前插入一个元素时，需向后移动_ n-i+1 _个元素。
3. 向一个长度为n的顺序表中删除第i个元素(1?i?n)时，需向前移动_ n-i ___个元素。
4. 单链表可以看做_线性表_的链式存储表示。
8
5. 在双链表中，每个结点有两个指针域，一个指向_前驱结点__，另一个指向_后继结点 __。
6.带头结点的单链表中，除头结点外，任一结点的存储位置是在其前驱结点的指针域中。 7.单链表中引入头结点的作用是在链表的第一个位置上行插入和删除等操作时无须进行特殊处理
8. 一个长为n的线性表，其排序时间性能最优为(O(n*Logn)。 2
9. 在一个单链表中p所指结点之前插入一个s (值为e)所指结点时，可执行如下操作:
q=head;
while (q->next!=p) q=q->next;
s= (struct node *)malloc(sizeof(struct node)); s->data=e;
q->next= s ; //填空
s->next= p ; //填空
10. 在一个单链表中删除p所指结点的后继结点时，应执行以下操作:
q= p->next;
p->next= _ q->next _; //填空
free( q _) ; //填空
11. 在一个单链表中p所指结点之后插入一个s所指结点时，应执行s->next= p->next 和p->next=_s_的操作。
12. 对于一个具有n个结点的单链表，在已知p所指结点后插入一个新结点的时间复杂度是_ O (1) _;在给定值为x的结点后插入一个新结点的时间复杂度是O (n) _。 13.第二章作业题
习题3 栈和队列
一、基本内容
9
栈和队列的结构特点;在两种存储结构上如何实现栈和队列的基本操作以及栈和队列在程序设计中的应用。
二、学习要点
1. 掌握栈和队列的特点。
2(熟练掌握栈类型的两种实现方法，即两种存储结构表示时的基本操作实现算法，特别应注意栈满和栈空的条件以及它们的描述方法。
3(熟练掌握循环队列的基本操作实现算法(持别注意队满和队空的描述方法。 4(理解递归算法执行过程中栈的状态变化过程。
3.1 单项选择题
1. 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是____。
A. edcba B. decba C. dceab D. abcde
2. 若已知一个栈的入栈序列是1，2，3，„，n，其输出序列为p1，p2，p3，„，pn，若p1=n，则pi为____。
A. i B. n=i C. n-i+1 D. 不确定
3. 栈结构通常采用的两种存储结构是____。
A. 顺序存储结构和链式存储结构 B.散列方式和索引方式
C.链表存储结构和数组 D.线性存储结构和非线性存储结构 4. 判定一个顺序栈ST(最多元素为m0)为空的条件是____。
A. top !=0 B. top= =0 C. top !=m0 D. top= =m0-1 5. 判定一个顺序栈ST(最多元素为m0)为栈满的条件是____。
A. top～=0 B. top= =0 C. top～=m0 D. top= =m0 6. 栈的特点是_B__，队列的特点是_A__。
A. 先进先出 B. 先进后出
10
7. 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行__ __。(不带空的
头结点)
A. HS—,next=s;
B. s—,next= HS—,next; HS—,next=s;
C. s—,next= HS; HS=s;
D. s—,next= HS; HS= HS—,next;
8. 从一个栈顶指针为HS的链栈中删除一个结点时，用x保存被删结点的值，则执行
_ __。(不带空的头结点) _
A. x=HS; HS= HS—,next; B. x=HS—,data;
C. HS= HS—,next; x=HS—,data; D. x=HS—,data; HS= HS—,next; 9. 一个队列的数据入列序列是1，2，3，4，则队列的出队时输出序列是____ 。
A. 4，3，2，1 B. 1，2，3，4
C. 1，4，3，2 D. 3，2，4，1
10. 判定一个循环队列QU(最多元素为m)为空的条件是____。
A. rear - front= =m B. rear-front-1= =m
C. front= = rear D. front= = rear+1 11. 判定一个循环队列QU(最多元素为m, m= =Maxsize-1)为满队列的条件是____。
A. (rear+1)% Maxsize = =front
B. rear-front-1= =m C. front= =rear D. front= = rear+1
12. 循环队列用数组A[0，m-1]存放其元素值，已知其头尾指针分别是front和rear，则当前队列中的元素个数是____。
A. (rear-front+m)%m B. rear-front+1 C. rear-front-1 D. rear-front
11
13. 栈和队列的共同点是____。
A. 都是先进后出 B. 都是先进先出
C. 只允许在端点处插入和删除元素 D. 没有共同点
3.2 填空题(将正确的答案填在相应的空中)
1. 向量、栈和队列都是 线性__结构，可以在向量的_任何___位置插入和删除元素;对于栈只能在_栈顶__插入和删除元素;对于队列只能在__队尾__插入元素和__队首__删除元素。
. 向栈中压入元素的操作是__先存入元素，后移动栈顶指针__。 3
4. 对栈进行退栈时的操作是__先移动栈顶指针，后取出元素__。
对于顺序栈存放在一维数组s[0...M]。
按课件中的定义:
top=0为栈空，x入栈时，s[top]=x;top++;即先存入元素，后移动栈顶指针
top=M时栈满，出栈时，top--;x=s[top]。即先移动栈顶指针，后取出元素
按有些参考书中定义:
top=-1表示栈空，x入栈时，top++，s[top]=x;即先移动栈顶指针，后存入元素
top=M-1表示栈满，出栈时， x=s[top];top--。即先取出元素，后移动栈顶指针
5. 在一个循环队列中，队首指针指向队首元素的__前一个位置__。 6. 从循环队列中删除一个元素时，其操作是__先移动队首元素，后取出元素__。 7. 在具有n个单元的循环队列中，队满时共有__ n-1__个元素。
8. 一个栈的输入序列是12345，则栈的输出序列43512是__不可能的__。 9. 一个栈的输入序列是12345，则栈的输出序列12345是__可能的__。
12
10.想象六辆列车位于图中堆栈的输入一边，列车编号为123456，按此顺序开进堆栈，且可在任意时刻开走，则能否得到32564l出站序列?能否得到154623出站序列?在可能的情况下，说明如何实现。能得到325641(实现过程为;Push，push，push，pop，pop，Push，push，pop，push，pop，pop，pop。不能得到154623。
11. 设循环队列存放在向量sq.data[o((m]中，则队头指针sq.front在循环意义下的加1
。若用牺牲一个单元的办法操作可用模运算表示为 (sq.front+1) MOD (m+1)
来区分队满和队空条件，则队满条件可表示为 (sq.rear+1) MOD (m+1),sq.front 。
12. 设顺序栈存放在一维数组s[M]，栈底位置是m-1，则栈空条件 top=0 ，栈满条件是 top=m 。
13.循环队列只有下溢，没有上溢。(错误)
14(队列和栈都是运算受限的线性表，只允许在表的两端进行运算。(正确) 15.栈有哪几种不同的存储结构?请分别画出在这些存储结构中元素a，b，c，J依次进
end 栈后堆栈的状态。链栈和顺序栈 a5
a6 5 a4 4 0 17.循环队列入队、出队算法如下: 6 3 1 2
入队算法:
3 1 2 start void en_cycque(int sq[],int start,int end,int x) 初始状态
{ if(((end+1)%M)==start) printf("overflow");
else { end=(end+1)%M; sq[end]=x; }
}
出队算法:
int dl_cycque(int sq[],int start,int end,int *q)
{ if(start==end) return(0);
13
else { start=(start+1)%M; *q=sq[start]; return(1); }
}
队列某个时刻的初始状态如图所示。
1).在初始状态上，画出a7、a8和a9入队后的状态图，
2).在初始状态上，画出a4、a5和a6出队后的状态图。
习题4 串
一、基本内容
串的 定义;串的三种存储表示:定长顺序存储结构、块链存储结构和堆分配存储
结构;串的各种基本操作的实现。
二、学习要点
1(熟悉串的基本操作的定义
2(掌握在串的定长顺序存储结构上实现串的各种操作的方法。
3. 掌握串的堆存储结构以及在其上实现串操作的基本方法。 4.1 单项选择题
1(以下叙述中正确的是 。
A.串是一种特殊的线性表 B.串的长度必须大于零
C.串中元素只能是字母 D.空串就是空白串 2(空串与空格串是相同的，这种说法____。
A. 正确 B. 不正确
3(串是一中特殊的线性表，其特殊性体现在____。
A. 可以顺序存储 B. 数据元素是一个字符
C. 可以链接存储 D. 数据元素可以是多个字符 4(设有两个串p和q，求q在p中首次出现的位置的运算称作____。
14
A. 连接 B. 模式匹配
C. 求子串 D. 求串长
5(设串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))的结果串是____。
A. BCDEF B. BCDEFG
C. BCPQRST D. BCDEFEF 6(设串的长度为n，则它的子串个数为 。
A.n B.n(n+1) C.n(n+1)/2 D.n(n+1)/2+1 4.2 填空题(将正确的答案填在相应的空中)
1(串的三种存储表示:定长顺序存储结构、块链存储结构和堆分配存储结构 2(两个串相等的充分必要条件是__两个串的长度相等且对应位置的字符相同__。 3(空串是__零个字符的串__，其长度等于__零__。
4(空格串是_由一个或多个空格字符组成的串__，其长度等于_其包含的空格个数___。 5(设s=’I,AM,A,TEACHER’,其长度是__14__。
6(串是由有限个字符构成的连续序列，串长度为串中字符的个数，子串是主串中字符构成的有限序列。(×)
7(如果一个串中的所有字符均在另一串中出现，则说前者是后者的子串。(×) 4.3 算法设计题
写一个递归算法来实现字符串逆序存储，要求不另设存储空间。
void reverse(char arr[])
{char ch; int i=1;
do{ch=getchar(); reverse(arr);
15
arr[i]=ch; i++; }while(ch!=’#’&&i0)个结点的满二
[log(n+1)]-1[log(n+1)]-1叉树共有 _2 [或(n+1)/2]___个叶子和__ 2 –1_[或(n-1)22
/2 ]_个非终端结点。层数:k=[log(n+1)] 2
8. 结点最少的树为__只有一个结点的树 __，结点最少的二叉树为_空的二叉树___。 9. 现有按中序遍历二叉树的结果为abc，问有__5__种不同形态的二叉树可以得到这一遍历结果，这些二叉树分别是____。
23
a c b c a
c a bb c ab
c a b c b
图6.8 树形5种
a
10. 由如图6.9所示的二叉树，回答以下问题: b c
de? 其中序遍历序列为_dgbaechif___; f
g h ? 其前序遍历序列为_abdgcefhi___; H
i
? 其后序遍历序列为_gdbeihfca___;
i 图6.9 一棵二叉树
(设有n个结点的完全二叉树顺序存放在向量a[l((n]中，对任一结点a[i]，若a[i]11
有父母，则其父母是 a[i/2] 。若a[i]有左子女，则左子女为 a[2i] ，若a[i]有右子女，则右子女 a[2i+1] ;i值最大的分支结点是 a[n/2] 。 12(设T是非空的二叉树，若T的先序序列和中序序列相同，则T的形态是所有左子树为空的二叉树，
，若T的先序序列和后序序列相同，则T的形态是 所有右子树为空的二叉树 ;若T的中序序列和后序序列相同，则T的形态是 具有0和1个结点的二叉树 。 13(二叉树是度数为2的有序树。( 正确 )
14(存在这样的二叉树，对它采用任何次序的遍历，其结果相同。(正确。空树或只有一个根结点的树)
15(完全二叉树中，若一个结点没有左孩子，则它必是树叶。(正确) 16(树形结构中，若结点A有4个兄弟，B是A的双亲，则B的度为 5 6.3 简答题
1. 根据二叉树的定义，具有三个结点的二叉树有5种不同的形态，请将它们分别画出。
24
图6.11 树形5种
2. 假设一棵 二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该
树。
E
BF
E AD H
E C G I
K
J
图6.12
3. 由如图6.9所示的二叉树，画出该二叉树对应的森林。
a
b c
a c f def 11 g h b h i e H k d i j i 图6.9 一棵二叉树 图 6.13 对应的森林
4. 已知一棵树如图6.14所示，转化为一棵二叉树，表示为____。
a a
b
b c d c
e d
e f g g i
图6.14 一棵图 6.15 一棵树的孩子兄弟表 树 示
5. 以数据集{4，5，6，7，10，12，18}为结点权值，画出构造Huffman树的每一步图
25
示，计算其带权路径长度为。
62
37 25
19 13 18 12
10 9 7 6
4 5
图6.16 Huffman树
6(设T是一棵二叉树，除叶子结点外，其它结点的度数皆为2，若T中有6个叶结点，试问:
(1)T树的最大可能深度Kmax,?最小可 能深度Kmin,, Kmax,6;Kmin,4 (2)T树中共有多少非叶结点? 非叶结点有5个。
(3)若叶结点的权值分别为1，2，3，4，5，6。请构造一棵哈夫曼树，并计算该哈夫曼树的带权路径长度wPl。 wPIf,4×(1+2)+3×3+2×(4+6+5),51 6.4 算法设计题
1. 编写按层次顺序(同一层自左至右)遍历二叉树的算法。
2(试编写算法，对一棵二叉树,统计叶子的个数。
3(试编写算法，对一棵二叉树根结点不变，将左、右子树进行交换，树中每个结点的左、右子树进行交换。
7. 假设用于通讯的电文仅有八个字母(a,b,c,d,e,f,g,h)组成，字母在电文中出现的频率分别为0.07, 0.19, 0.02, 0.06, 0.32, 0.03, 0.21, 0.10。试为这八个字母设计哈夫曼编码。
使用0-7的二进制表示形式是另一种编码
方案
气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载
。对于上述实例，比较两种方案的优缺点。
26
8. 试编写算法，对一棵以孩子-兄弟链表表示的树统计叶子的个数。假设一棵 二叉树的先序序列为EBADCFHGIKJ和中序序列为ABCDEFGHIJK。请画出该树。
习题7 图
一、 基本内容
图的定义和术语;图的存储结构:数组表示法和邻接表;图的两种遍历策略:深度优先搜索和广度优先搜索;图的连通性:连通分量和最小生成树;拓扑排序和关键路径;两类求最短路径问题的解法。二、学习要点
1.熟悉图的各种存储结构及其构造算法，了解实际问题的求解效率与采用何种存储结构和算法有密切联系。
2(熟练掌握图的两种搜索路径的遍历:遍历的逻辑定义、深度优先搜索的递归形式和广度优先搜索的算法。在学习中应注意图的遍历算法与树的遍历算法之间的类似和差异。树的先根遍历是一种深度优先搜索策略，树的层次遍历是一种广度优先搜索策略。
3(应用图的遍历算法求解各种简单路径问题，理解各种算法。
7.1 单项选择题
1(在一个图中，所有顶点的度数之和等于所有边数的____倍。
A. 1/2 B. 1 C. 2 D. 4 2(任何一个无向连通图的最小生成树 。
A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 3(在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的____倍。
A. 1/2 B. 1 C. 2 D. 4 4(一个有n个顶点的无向图最多有____条边。
A. n B. n(n-1) C. n(n-1)/2 D. 2n
27
5(具有4个顶点的无向完全图有____条边。
A. 6 B. 12 C. 16 D. 20 6(具有6个顶点的无向图至少应有____条边才能确保是一个连通图。
A. 5 B. 6 C. 7 D. 8 7(在一个具有n个顶点的无向图中，要连通全部顶点至少需要____条边。
A. n B. n+1 C. n-1 D. n/2 8(对于一个具有n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是____。
22 A. n B. (n-1) C. n-1 D. n
9(对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则表头向量的大小为_?___;所有邻接表中的接点总数是_?___。
? A. n B. n+1 C. n-1 D. n+e
? A. e/2 B. e C.2e D. n+e 10(已知一个图如图7.1所示，若从顶点a出发按深度搜索法进行遍历，则可能得到的一种顶点序列为__?__;按宽度搜索法进行遍历，则可能得到的一种顶点序列为__?__。
? A. a,b,e,c,d,f B. e,c,f,e,b,d C. a,e,b,c,f,d D. a,e,d,f,c,b
? A. a,b,c,e,d,f B. a,b,c,e,f,d C. a,e,b,c,f,d D.
a,c,f,d,e,b
a
c b e
f d
28
图 7.1 一个无向图
11(已知一有向图的邻接表存储结构如图7.2所示。
3 2 ^ 1
2 ^
4 5 3 ^
4 ^
4 2 5 ^
图7.2 一个有向图的邻接表存储结构
? 根据有向图的深度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。
A. v1,v2,v3,v5,v4 B. v1,v2,v3,v4,v5
C. v1,v3,v4,v5,v2 D. v1,v4,v3,v5,v2 ? 根据有向图的宽度优先遍历算法，从顶点v1出发，所得到的顶点序列是____。
A. v1,v2,v3,v4,v5 B. v1,v3,v2,v4,v5
C. v1,v2,v3,v5,v4 D. v1,v4,v3,v5,v2 12(采用邻接表存储的图的深度优先遍历算法类似于二叉树的____。
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历
13(采用邻接表存储的图的宽度优先遍历算法类似于二叉树的____。
29
A. 先序遍历 B. 中序遍历 C. 后序遍历 D. 按层遍历 14(关键路径是事件结点网络中 。
A.从源点到汇点的最长路径 B.从源点到汇点的最短路径
C.最长的回路 D.最短的回路
15(下面不正确的说法是 。
(1)在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小;
(2)AOE网工程工期为关键活动上的权之和;
(3)在关键路径上的活动都是关键活动，而关键活动也必在关键路径上。
A.(1) B.(2) C.(3) D.(1)、(2) 16(在图7.3所示的拓朴排列的结果序列为 。
A.125634 B.516234 C.123456 D.521634
图7.3有向图
17(一个有n个顶点的无向连通图，它所包含的连通分量个数为 。
A.0 B.1 C.n D.n+1
18(对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应邻接表中该顶点单链表中的结点数为 。
A.k1 B.k2 C.k1-k2 D.k1+k2 19(对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为 。
A.k1 B.k2 C.k1-k2 D.k1+k2
30
7.2 填空题(将正确的答案填在相应饿空中)
1(n个顶点的连通图至少_n-1_条边。
2(在无权图G的邻接矩阵A中，若(vi,vj)或,vi,vj,属于图G的边集合，则对应元素A[i][j]等于_1_，否则等于_0__。
3(在无向图G的邻接矩阵A中，若A[i][j]等于1，则A[j][i ]等于_1__。 4(已知图G的邻接表如图7.4所示，其从顶点v1出发的深度有限搜索序列为__ v1,v2,v3,v6,v5, v4__，其从顶点v1出发的宽度优先搜索序列为_ v1,v2,v5,v4,v3,
v6___。
v5 v4 v2 v1
v2 v5 v3
v3 v6
v4 ^
v5 v4 v6 v3
v6 ^
图7.4 图G的邻接表
5(已知一个有向图的邻接矩阵表示，计算第i个结点的入度的方法是_求矩阵第i列非零元素之和_。
6(已知一个图的邻接矩阵表示，删除所有从第i个结点出发的边的方法是__将矩阵第i行全部置为零。
31
7(遍历图的过程实质上是 对每个顶点查找其邻接点的过程; 。BFS遍历图的时间复杂度为 O(e)(e为图中的边数)，DFS遍历图的时间复杂度为 O(e); ，两者不同之处在于遍历图的顺序不同 ，反映在数据结构上的差别是 DFS采用栈存储访问过的结点，BFS采用队列存储访问过的结点。
8(一个图的 邻接矩阵 表示法是唯一的，而 邻接表 表示法是不唯一的。 9(有向图中的结点前驱后继关系的特征是 一个结点可能有若干个前驱，也可能有若干个后继 。
(若无向图G的顶点度数最小值大于等于 2 时，G至少有一条回路。 10
11(根据图的存储结构进行某种次序的遍历，得到的顶点序列是 唯一 的。
7.3 综合题
(已知如图7.5所示的有向图，请给出该图的: 1
1 5 (1)每个顶点的入/出度;
6
4 2 顶入出顶入出度
点 度 度 点 度 3
1 3 0 4 1 3
2 2 2 5 2 1
3 1 2 6 2 3
(2)邻接距阵;
32
0 0 0 0 0 0
1 0 0 1 0 0
0 1 0 0 0 1
0 0 1 0 1 1
1 0 0 0 0 0
1 1 0 0 1 0
(3)邻接表;
1 ^
2 4 1 ^
3 6 2 ^
4 ^ 6 5 3 5 1 ^
6 5 2 1 ^ (4)逆邻接表;
1 6 5 2 ^ 2 3 6 ^
3 4 ^
4 ^ 2
5 6 4 ^
6 4 3 ^ 5)强连通分量。 (
1 5
6
4 2
3
图7。5一个有向图 33
3(试列出图7.8中全部的拓扑排序序列。
1 2 4 3
5 6
图7.8 152364
152634
156234
561234
516234
512634
512364
(请用图示说明图7.9从顶点a到其余各顶点之间的最短路径。 4
5 b d 3 6
3 2 2 a f
5 3 e c 4
34
图7.9
W=6 W=5 b d 3
3 2 a f
W=9
3
e c 4 W=7 W=3
5(已知AOE网有9个结点:V1，V2，V3，V4，V5，V6，V7，V8，V9，其邻接矩阵如下:
(1)请画出该AOE图。
(2)计算完成整个
计划
项目进度计划表范例计划下载计划下载计划下载课程教学计划下载
需要的时间。
(3)求出该AOE网的关键路径。
? 6 4 5 ? ? ? ? ? ? ? ? ? 1 ? ? ? ? ? ? ? ? 1 ? ? ? ? ? ? ? ? ? 2 ? ? ? ? ? ? ? ? ? 9 7 ? ? ? ? ? ? ? ? 4 ? ? ? ? ? ? ? ? ? 2 ? ? ? ? ? ? ? ? 4 ? ? ? ? ? ? ? ? ? 5((1)该AOE图为:
35
125972
67
1194438
5
4264
(2)完成整个计划需要18天。
(3)关键路径为:(V1，V2，V5，V7，V9)和(V1，V2， V5，V8，V9，)
习题8 查找
一、基本内容
讨论查找表(包括静态查找表和动态查找表)的各种实现方法:顺序表、有序表、树表
和哈希表;关于衡量查找表的主要操作一一平均查找长度的讨论。 二、学习要点
1. 熟练掌握顺序表和有序表的查找万法。
2(熟悉静态查找树的构造方法和查找算法，理解静态查找树和折半查找的关系。
3(熟练掌握二叉排序树的构造和查找方法。
4(熟练掌握哈希表的构造方法，深刻理解哈希表与其他结构的表的实质性的差别。 8.1 单项选择题
1.顺序查找法适合于存储结构为____的线性表。
A. 散列存储 B. 顺序存储或链接存储
C. 压缩存储 D. 索引存储
2.对线性表进行二分查找时，要求线性表必须____。
A. 以顺序方式存储 B. 以链接方式存储
C. 以顺序方式存储，且结点按关键字有序排序
36
D. 以链接方式存储，且结点按关键字有序排序
3.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为____.
A. n B. n/2 C. (n+1)/2 D. (n-1)/2
4.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为____。
2A(O(n) B. O(nlogn) C. O(n) D. O(logn) 22
5.二分查找和二叉排序树的时间性能____。
A. 相同 B. 不相同
6.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，____次比较后查找成功。
A. 1 B. 2 C. 4 D. 8 7.设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点:addr (15)=4;
addr (38)=5; addr (61)=6; addr (84)=7如用二次探测再散列处理冲突，关键字为49的结点的地址是____。
A. 8 B. 3 C. 5 D. 9 8.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为____。
A. 35/12 B. 37/12 C. 39/12 D. 43/12
9(对于静态表的顺序查找法，若在表头设置岗哨，则正确的查找方式为 。
A.从第0个元素往后查找该数据元素 B.从第1个元素往后查找该数据元素
C.从第n个元素往开始前查找该数据元素 D.与查找顺序无关 10(解决散列法中出现的冲突问题常采用的方法是 。
A.数字分析法、除余法、平方取中法 B.数字分析法、除余法、线性探测法
C.数字分析法、线性探测法、多重散列法 D.线性探测法、多重散列法、链地址
37
法
11(采用线性探测法解决冲突问题，所产生的一系列后继散列地址 。
A.必须大于等于原散列地址 B.必须小于等于原散列地址
C.可以大于或小于但不能等于原散列地址 D.地址大小没有具体限制 12(对于查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于 。
A.静态查找表 B.动态查找表
C.静态查找表与动态查找表 D两种表都不适合
13.散列表的平均查找长度 。
A.与处理冲突方法有关而与表的长度无关 B.与处理冲突方法无关而与表的长度有关
与处理冲突方法有关而与表的长度有关 D.与处理冲突方法无关而与表的长C.
度无关
8.2 填空题(将正确的答案填在相应的空中)
1.顺序查找法的平均查找长度为_ (n+1)/2 __;折半查找法的平均查找长度为((n+1)*log2(n+1))/n-1_;哈希表查找法采用链接法处理冲突时的平均查找长度为
,,__1+(为装填因子)_。
2.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是_哈希表查找法___。
3.折半查找的存储结构仅限于_顺序存储结构___，且是有序的___。 4. 假设在有序线性表A[1..20]上进行折半查找，则比较一次查找成功的结点数为__1_，则比较二次查找成功的结点数为_2___，则比较三次查找成功的结点数为__4__，则比较四次查找成功的结点数为__8__，则比较五次查找成功的结点数为__5__，平均
38
查找长度为__37/10__。(依题意，构造一棵有序二叉树，共20个结点，第一层1个结点，第二层2个结点，第三层4个结点，第四层8个结点，第五层5个结点，则:ASL=(1*1+2*2+3*4+4*8+5*5)/20=74/20)
5. 对于长度为n的线性表，若进行顺序查找，则时间复杂度为__ O(n)_;若采用折半法查找，则时间复杂度为_O(logn)___; 2
6(已知有序表为(12，18，24，35，47，50，62，83，90，115，134)，当用折半查找90时，需进行 2 次查找可确定成功;查找47时，需进行 4 次查找成功;查
3 次查找才能确定不成功。 找100时，需进行
7(二叉排序树的查找长度不仅与 结点个数n 有关，也与二叉排序树的生成过程 有关。
8(一个无序序列可以通过构造一棵 二叉排序树 树而变成一个有序树，构造树的过程即为对无序序列进行排序的过程。
9(平衡二叉排序树上任一结点的平衡因子只可能是 0、1或-1。
10( 直接定址 法构造的哈希函数肯定不会发生冲突。
11(在散列函数H(key)=key%p中，p应取_素数___。
12(在散列存储中，装填因子的值越大，则_存取元素时发生冲突的可能性就越大;,
的值越小，则 存取元素时发生冲突的可能性就越小_____。 ,
13.折半查找算法如下，请在程序空白处补齐应有的字符。
typedef struct
{ int key;}JD;int binsrch(JD r[],int n,int k) { int low,high,mid,found;
low=1; high=n; found=0;
while(( )&&(found==0))
39
{ mid= ;
if(k>r[mid].key) ;
else if( ) found=1;
else high=mid-1;
}
if(found==1) return(mid);
else return(0);
}
8.3 综合练习题:
1. 画出对长度为10的有序表进行折半查找的判定树，并求其等概率时查找成功的平均查找长度。
5
2 8
1 3 6 9
4 7 10
ASL=(1*1+2*2+3*4+4*3)/10=2.9
2. 选取哈稀函数H(k)=(k)MOD 11。试在0-10的散列地址空间中对关键字序列(22,41,53,46,30,13,01,67)造哈希表
1)用开放定址法处理冲突，选用线性探测再散列处理冲突，即Hi=(H(k)+di) MOD m,
求等概率情况下查找成功时的平均查找长度。
2)用链地址法处理冲突,求等概率情况下查找成功时的平均查找长度。
40
0 1 2 3 4 5 6 7 8 9 10
22 1 46 41 30 13 67 53
1)
H(22)=22 MOD 11=0
H(41)=41 MOD 11=8
H(53)=53 MOD 11=9
H(46)=46 MOD 11=2
H(30)=30 MOD 11=8 冲突 H1=(8+1) MOD 11=9冲突
H2=(8+2) MOD 11=10不冲突
H(13)=13 MOD 11=2冲突 H1=(2+1) MOD 11=3不冲突
H(01)=1 MOD 11=1
H(67)=67 MOD 11=1冲突H1=(1+1) MOD 11=2冲突
H2=(1+2) MOD 11=3 冲突
H3=(1+3) MOD 11=4 不冲突 ASL=(1*5+2*1+3*1+4*1)/8=7/4
2)
41
0 1 2 3 4 5 6 7 8 9 10 ^ 22
^ 1 67
^ 46 13
41 30 ^
^ 53
ASL=(1*5+2*3)/8=11/8
3. 已知一组关键字{49，38，65，97，76，13，27，44，82，35，50}，画出由此生成的二叉排序树。
49
38 65
44 50 97 13
76 27
82 35
习题9 排序
一.基本内容
1.讨论比较各种内部排序方法，插入排序、交换排序、选择排序、归并排序的基本思想、算法特点、排序过程以及它们的时间复杂度分析。在每类排序方法中，从简单方法入手，重点讨论性能先进的高效方法(如，插入排序类中的希尔排序、交换排序类
42
中的快速排序、选择排序类中的堆排序等)。
二.学习要点
1.深刻理解排序的定义和各种排序方法的特点，并能加以灵活匝用。
2(了解各种方法的排序过程及其依据的原则。基于“关键字间的比较”进行排序的方法可以按排序过程所依据的不同原则分为插入排序、交换排序、选择排序、归并排序。
3(掌握各种排序方法的时间复杂度的分析方法。能从“关键字间的比较次数”分析排序算法的平均情况和最坏情况的时间性能。按平均时间复杂度划分，内部排序可分
2为三类:o(n)的简单排序方法，o(n?1ogn)的高效排序方法 2
4(理解排序方法“稳定”或“不稳定”的含义，弄清楚在什么情况下要求应用的排序方法必须是稳定的。
9.1 单项选择题
1. 在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是____。 A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序
2. 设有1000个无序的元素，希望用最快的速度挑选出其中前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. 38，46, 56，79， 40，84， C. 84，79，56，46，40，38 D. 84，56，79，40，46，38
43
5. 一组记录的关键码为(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 6. 一组记录的排序码为(25，48，16，35，79，82，23，40，36，72)，其中含有5个长度为2的有序表，按归并排序的方法对该序列进行一趟归并后的结果为____。 A. 16，25，35，48，23，40，79，82，36，72 B. 16，25，35，48，79，82，23，36，40，72
C. 16，25，48，35，79，82，23，36，40，72 D. 16，25，35，48，79，23，36，40，72，82
7. 排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为____。
A. 希尔排序 B. 起泡排序 C. 插入排序 D. 选择排序
8. 排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列的一端的方法，称为____。
A. 希尔排序 B. 归并排序 C. 插入排序 D. 选择排序
9. 用某种排序方法对线性表( 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
则所采用的排序方法是____。
44
A. 选择排序 B. 希尔排序 C. 归并排序 D. 快速排序 10. 下述几种排序方法中，平均查找长度最小的是____。
A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序 11. 下述几种排序方法中，要求内存量最大的是____。
A. 插入排序 B. 选择排序 C. 快速排序 D. 归并排序 12. 快速排序方法在____情况下最不利于发挥其长处。
A. 要排序的数据量太大 B. 要排序的数据中含有多个相同值
要排序的数据已基本有序 D. 要排序的数据个数为奇数 C.
9.2 填空题 (将正确的答案填在相应的空中)
1. 在对一组记录(54，38，96，23，15，72，60，45，83)进行直接插入排序时，当把第7个记录60插入到有序表时，为寻找插入位置需比较_3__。
2. 在利用快速排序方法对一组记录(54，38，96，23，15，72，60，45，83)进行快速排序时，共需递归调用的次数为_4__，其中第二次递归调用是对__23,38,15__一组记录进行快速排序。
3. 在堆排序，快速排序和归并排序中，若只从存储空间考虑，则应首先选取__堆排序__方法，其次选取__快速排序__方法，最后选取__归并排序__方法;若只从排序结果的稳定性考虑，则应选取__归并排序__方法;若只从平均情况下排序最快考虑，则应选取__快速排序__方法;若只从最坏情况下排序最快并且要节省内存考虑，则应选取_堆排序___方法。
4. 在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，排序是不稳定的有__希尔排序、选择排序、快速排序和堆排序__。 5. 在在插入排序、希尔排序、选择排序、快速排序、堆排序、归并排序和基数排序中，平均比较次数最少的排序是__快速排序__，需要内存容量最多的是_基数排序___。
45
6. 在堆排序和快速排序中，若原始记录接近正序或反序，则选用__堆排序__，若原始记录无序，则最好选用__快速排序__。
7. 在插入和选择排序中，若初始数据基本正序，则选用__插入__;若初始数据基本反序，则选用__选择__。
8. 对n个元素的序列进行起泡排序时，最少的比较次数是_n-1_。
9.按关键字从小到大排序。在插入排序方法中，如果待排序记录按关键字从小到大排列(正序)，则比较次数最少。对于快速排序而言，待排序记录在什么情况从小到大排列(正序)，算法出现最坏情况。
9.3 综合题
1. 以关键码序列(503,087,512,061,908,170,897,275,653,426)，为例，手工执行以下排序算法，写出每一趟排序结束时的关键码状态:
直接插入排序;
希尔排序(增量d[1]=5);
快速排序;
堆排序;
归并排序;
基数排序。
2. 判别以下序列是否为堆(小顶堆或大顶堆)。如果不是，则把它调整为堆(要求记录交换次数最少)。
(1)(100,86,48,73,35,39,42,57,66,21); (2)(12,70,33,65,24,56,48,92,86,33) (3)(103,97,56,38,66,23,42,12,30,52,06,20) (4)(05,56,20,23,40,38,29,61,35,76,28,100).
46
3. 已知一组关键字(49，38，65，97，76，13，27，48，55，4),现采用希尔排序法进行排序。已知增量序列为:{5，3，1},分别画出一趟、二趟和三趟排序的分组情况以及每一趟的排序结果。
47
浙公网安备 33021202002483