1、数据结构与算法习题册（课后部分参考答案）数据结构与算法课程组目录目录课后习题部分第一章 绪论 .1第二章 线性表 .3第三章 栈和队列 .5第四章 串 .8第五章 数组和广义表 .10第六章 树和二叉树 .13第七章 图 .16第九章 查找 .20第十章 排序 .23课后习题部分 第一章绪论1第一章 绪论一. 填空题1. 从逻辑关系上讲，数据结构的类型主要分为 集合 、线性结构、树结构和 图结构。2. 数据的存储结构主要有 顺序存储和 链式存储 两种基本方法，不论哪种存储结构，都要存储两方面的内容：数据元素 和 数据元素之间的关系 。3. 算法具有五个特性，分别是 有穷性 、 确定性、可行性、
2、 输入 、 输出 。4. 算法设计要求中的健壮性指的是 算法在发生非法操作时可以作出处理的特性。二. 选择题1. 顺序存储结构中数据元素之间的逻辑关系是由 C 表示的，链接存储结构中的数据元素之间的逻辑关系是由 D 表示的。A 线性结构 B 非线性结构 C 存储位置 D 指针2. 假设有如下遗产继承规则：丈夫和妻子可以相互继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。则表示该遗产继承关系的最合适的数据结构应该是 B 。A 树 B 图 C 线性表 D 集合3. 算法指的是 A 。A 对特定问题求解步骤的一种描述，是指令的有限序列。B 计算机程序 C 解决问题的计算方法 D 数据处理
3、三. 简答题1. 分析以下各程序段，并用大 O 记号表示其执行时间。(1) (2)i=1;k=0; i=1;k=0;While(inext =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
4、in）和求第 i 个结点的直接前驱（2in ） B 在第 i 个结点后插入一个新结点（1in ）C 删除第 i 个结点（1in） 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. 线性结构的基本
5、特征是：每个元素有且仅有一个直接前驱和一个直接后继。 F 四. 简答题1. 分析下列情况下，采用何种存储结构更好些。(1)若线性表的总长度基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素。(2)如果 n 个线性表同时并存，并且在处理过程中各表的长度会动态发生变化。(3)描述一个城市的设计和规划。课后作业部分 第二章 线性表4 应选用顺序存储结构。很少进行插入和删除操作，所以空间变化不大，且需要快速存取，所以应选用顺序存储结构。 应选用链式存储结构。链表容易实现表容量的扩充，适合表的长度动态发生变化。 应选用链式存储结构。因为一个城市的设计和规划涉及活动很多，需要经常修改
6、、扩充和删除各种信息，才能适应不断发展的需要。而顺序表的插入、删除的效率低，故不合适。五. 算法设计1. 已知数组 An中的元素为整型，设计算法将其调整为左右两部分，左边所有元素为奇数，右边所有元素为偶数，并要求算法的时间复杂度为 O(n)。2. 线性表存放在整型数组 Aarrsize的前 elenum 个单元中，且递增有序。编写算法，将元素 x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。int insert (datatype A,int *elenum,datatype x) /*设 elenum 为表的最大下标*/if (*elenum=arrsize-1
7、) return 0; /*表已满，无法插入*/else i=*elenum;while (i=0 i-; Ai+1=x; /*找到的位置是插入位的下一位 */(*elenum)+;return 1; /*插入成功*/O（n）课后作业部分 第三章 栈和队列5第三章 栈和队列一. 填空题1. 设有一个空栈，栈顶指针为 1000H，现有输入序列为 1. 2. 3. 4. 5， 经过push，push，pop ，push，pop，push，push 后，输出序列是 23 ，栈顶指针为 1003H 。2. 栈通常采用的两种存储结构是 顺序栈 、 链栈 ；其判定栈空的条件分别是 TOP=-1 、 TOP
8、=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+12. 设栈 S 和队列 Q 的初始状态为空，元素 e1. e2. e3. e4. e5. e6 依次通过栈 S，一个元素出栈后即进入队列 Q，若 6 个元素出队的顺序是 e2. e4. e3. e6. e5. e1，则栈 S的容量至少应该是 C
9、 。A 6 B 4 C 3 D 23. 一个栈的入栈序列是 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，能否得到如下出栈序
10、列，若能，请写出操作序列，若不能，请说明原因。 C，E ，A ， B，D C，B ，A ， D，E课后作业部分 第三章 栈和队列6不能，因为在 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
11、). 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(
12、T,d); Push(S,d);/S 中如果存在 e，则删除它。(2) void algo2(Queue int d; InitStack(S);while(!QueueEmpty(Q)DeQueue(Q, d); Push(S, d);while(!StackEmpty(S)Pop(S, d); EnQueue(Q, d);/队列逆置课后作业部分 第三章 栈和队列7五. 算法设计1. 试写一个判别表达式中开、闭括号是否配对出现的算法BOOL BracketCorrespondency(char a)int i=0;Stack s;InitStack(s);ElemType x;while(a
13、i)switch(ai)case (:Push(s,ai);break;case :Push(s,ai);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则不是回文。试写一个算
14、法判别读入的一个以 为结束符的字符序列是否是“ 回文 ”。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;课后作业部分 第四章 串8第四章 串一. 填空题1. 不包含任何字符（长度为 0）的串 称为空串；由一个或多个空
15、格（仅由空格符）组成的串 称为空白串。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
16、，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 BCDEFEF4. 若串 S=”software”，其子串的数目是（ B ） 。 A 8 B 37 C 36 D 9三. 计算题1. 设 s=I AM A STUDENT, t=GOOD, q=WORKER, 求：1）Replace(s,
17、STUDENT,q) 2）Concat(t,SubString(s,7,8)1、 Replace(s,STUDENT,q)I AM A WORKER2、因为 SubString(s,7,8) STUDENTConcat(t,SubString(s,7,8)GOOD STUDENT四. 算法设计1. 利用 C 的库函数 strlen, strcpy（或 strncpy）写一个算法 void StrDelete(char *S,int t,int m) ，删除串 S 中从位置 i 开始的连续的 m 个字符。若 istrlen(S)，则没有字符被删除；若 i+mstrlen(S)，则将 S 中从位置 i 开始直至末尾的字符均被删去。提示：strlen 是求串长 (length)函数：int strlen(char s); /求串的长度
