《数据结构与算法设计》习题

1、作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 1、数据结构在计算机内存中的表示是指_。 A.数据的存储结构 B.数据元素 C.数据的逻辑结构 D.数据结构2、在数据结构中，数据的基本单位是_。 A. 数据项 B. 数据类型 C. 数据元素 D. 数据变量答案：A答案：C第一章第一章 习题习题( (习题一）习题一）.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 3、对于给定的、对于给定的n个元素，可以构造出的逻辑结构个元素，可以构造出的逻辑结构有有 、 、 、 四种。四种。答案：答案： 集合集合 线性结构线性结构 树结构树结构 图结构图结构

2、.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 4 设设n为正整数。试确定下列各程序段中前置以为正整数。试确定下列各程序段中前置以记号记号*的语句的执行次数：的语句的执行次数： (1) k=0; for(i=1;i=n;i+) for(j=i;j=n;j+) k+; * (2) i=1;j=0; while(i+jj)j+; * else i+; .作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 第二章第二章 习题习题( (习题二）习题二）1.单选题 1) 线性表的顺序存储结构是通过（ ）表示元素之间的关系 A. 后继元素地址 B. 元素的

3、存储顺序 C. 左、右孩子地址 D. 后继元素的数组下标 2) 在线性表顺序存储结构下，在第i个元素之前插入新元素一般需要（ ） 。 A. 移动元素 B. 修改头指针 C. 修改指针 D.申请新的结点空间 3) 若长度为n的线性表采用顺序存储结构，在其第i (1in+1)个位置之前插入一个新元素的算法的时间复杂度为（ ） 。 A. O(n) B. O(1) C. O(n2) D. O(log2n) .作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 4）在线性表的链式存储结构下，插入操作算法_。A) 需要判断是否表满B) 需要判断是否表空C) 不需要判断是否表满D) 需

4、要判断是否表空和表满5）若某线性表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点，则采用存储结构算法的时间效率最高的是_。A) 单链表 B) 给出表尾指针的单循环链表 C) 双向链表 D) 给出表尾指针双向循环链表答案：C答案：D.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 第二章第二章 习题习题( (习题三）习题三）2. 填空题填空题（1）在顺序表中插入或删除一个元素，需要平均移动）在顺序表中插入或删除一个元素，需要平均移动 元素，具体移动的元素个数与元素，具体移动的元素个数与 有关。有关。（2）顺序表中逻辑上相邻的元素的物理位置）顺序表中逻辑上

5、相邻的元素的物理位置 紧邻。紧邻。单链表中逻辑上相邻的元素的物理位置单链表中逻辑上相邻的元素的物理位置 紧邻。紧邻。（3）在单链表中，除了头结点外，任一结点的存储位置）在单链表中，除了头结点外，任一结点的存储位置由由 指示。指示。（4）在单链表中设置头结点的作用是）在单链表中设置头结点的作用是 表的一半表的一半 插入点的位置插入点的位置 一定或也一定或也不一定不一定 该结点的直接前趋该结点的直接前趋 在表的第一个元素结点之前插入新元素结点或删除在表的第一个元素结点之前插入新元素结点或删除第一个元素结点不需修改头指针第一个元素结点不需修改头指针.作者 (时间 2000年）北京理工大学计算机科学工

6、程系 秦怀青email 3. 在什么情况下用顺序表比链性表好？在什么情况下用顺序表比链性表好？ 解答：解答： 当我们经常要从线性表中存取指定位置的元素时当我们经常要从线性表中存取指定位置的元素时或当很少作插入、删除操作时，用顺序表比链性表好或当很少作插入、删除操作时，用顺序表比链性表好。 .作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 算法题算法题2.2. 指出下面算法的错误和低效之处，并将其改写指出下面算法的错误和低效之处，并将其改写成一个既正确又高效的算法。成一个既正确又高效的算法。.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email St

7、atus DeleteK（SqList &a ,int i, int k）/ 设线性表元素从设线性表元素从a.base1起存储起存储,从第从第i个元素起个元素起删除删除k个元素。个元素。 if( i1| k a.length) return ERROR; for( count=1; count=i+1;j-) a.elemj-1= a.elemj; a.length - ; /for return OK;/DeleteK0 01 1i-2i-2i-1i-1i in-1n-1 99 99 a1 a1 a2 a2ai-1ai-1 ai aiai+1ai+1 an an.作者 (时间 200

8、0年）北京理工大学计算机科学工程系 秦怀青email 解答解答 错误：移动元素的顺序有误；错误：移动元素的顺序有误； 低效：每次循环只删除了一个元素低效：每次循环只删除了一个元素.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 正确且高效的算法如下：正确且高效的算法如下：Status DeleteK（SqList &a ,int i, int k）/设线性表元素从设线性表元素从a.base1起存储起存储,从第从第i个元素起个元素起删除删除k个元素。个元素。 if ( i1| ka.length) return ERROR; for ( j=i+k;jnext;

9、 L-next = NULL; while ( p != NULL ) succ = p-next; / succ指向指向 *p 的后继的后继 p-next = L-next; L-next = p; / *p插入在头结点之后插入在头结点之后 p = succ; .作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 4.将两个非递减有序的有序单链表将两个非递减有序的有序单链表 la 和和 lb 归并归并为非递增的有序表。为非递增的有序表。 Typedef struct LNode int data; / 数据域数据域 struct Lnode *next; / 指针域指针

10、域 LNode, *LinkList; LinkList la, lb； / 单链表的头指针单链表的头指针 请用请用 la 和和 lb 中的结点合并生成一个新的非中的结点合并生成一个新的非递增的有序单链表递增的有序单链表 lc。合并完成后，原来的。合并完成后，原来的 la 和和 lb 成为空链表。成为空链表。.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 操作步骤操作步骤1)建空表建空表 Lc;2)依次从依次从 La 或或 Lb 中中“摘取摘取”元素值较小的元素值较小的结点插入到结点插入到 Lc 表中第一个结点之前直至其表中第一个结点之前直至其中一个表变空为止中一个

11、表变空为止;3)继续将继续将 La 或或 Lb 其中一个表的剩余结点插其中一个表的剩余结点插入在入在 Lc 表的表头结点之后表的表头结点之后; 4)释放释放 La 表和表和 Lb 表的表头结点。表的表头结点。.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email void union ( LinkList& Lc, LinkList& La, LinkList& Lb ) / 将非递减的有序表将非递减的有序表 La 和和Lb归并为非递增的归并为非递增的 / 有序表有序表Lc,归并之后，归并之后，La和和Lb表不再存在。表不再存在。 / 上述三个表均为

12、带头结点的单链表，上述三个表均为带头结点的单链表，Lc 表表 / 中的结点即为原中的结点即为原 La 或或 Lb 表中的结点。表中的结点。 / unionLc = new LNode; Lc-next = NULL;pa = La-next; pb = Lb-next; / 初始化初始化 / 归并归并delete La; delete Lb; / 释放释放La 和和 Lb的头结点的头结点.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email while ( pa != NULL | pb != NULL ) if ( pa =NULL ) q = pb; pb = pb-n

13、ext; else if ( pb = NULL ) q = pa; pa = pa-next; else if ( pa-data data ) q = pa; pa = pa-next; else q = pb; pb = pb-next; q-next = Lc-next; / 插入插入 Lc-next = q;.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 5已知一带有表头结点的单链表，结点结已知一带有表头结点的单链表，结点结构为如下：构为如下：假设该链表只给出了头指针假设该链表只给出了头指针 list。在不改。在不改变链表的前提下，请设计一个变链表的前提下

14、，请设计一个尽可能高尽可能高效效的算法，查找链表中倒数第的算法，查找链表中倒数第 k 个位置个位置上的结点（上的结点（k为正整数）。若查找成功，为正整数）。若查找成功，输出该结点的输出该结点的 data 的值，并返回的值，并返回 1；否；否则，返回则，返回 0。datadata linklink.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 问题关键问题关键如何尽可能高效？如何尽可能高效？常规算法常规算法对链表进行第一遍扫描，计算出链表的长度对链表进行第一遍扫描，计算出链表的长度len，然后进行第二遍扫描，计数到，然后进行第二遍扫描，计数到 len-k 的位的位置即

15、为需要查找的倒数第置即为需要查找的倒数第 k 个元素。个元素。算法时间复杂度：算法时间复杂度：O(n)。问题：问题：是否有更高效的算法是否有更高效的算法能否只进行一遍扫描即可完成？能否只进行一遍扫描即可完成？.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 算法的基本设计思想算法的基本设计思想假设链表的最后一个结点为倒数第假设链表的最后一个结点为倒数第 1 个个结点。结点。对链表进行扫描：用指针对链表进行扫描：用指针 p 和和 q 分别指分别指向两个结点，且保持指针向两个结点，且保持指针 p 和指针和指针 q 之之间的间的“距离距离”（包含的结点数）为（包含的结点数）

16、为 k，当当 p 指向最后一个结点时，指向最后一个结点时，q 指向的就指向的就是倒数第是倒数第 k 个结点个结点。.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 算法的详细实现步骤算法的详细实现步骤假表头指针为假表头指针为list，两个指针变量，两个指针变量 p 和和 q：1. 距离计数器距离计数器 count = 0；p=q=list-link，指向指向链表第一个数据结点；链表第一个数据结点；2. 若若 p 非空，则执行和；否则，转；非空，则执行和；否则，转；3. 如果如果count 小于小于 k，则，则 count = count + 1；否；否则则 q 指向下

17、一个结点；指向下一个结点；4. p 指向下一个结点，转步骤；指向下一个结点，转步骤；5. 若若 count 等于等于k，则查找成功，输出，则查找成功，输出 q 结点的结点的data值，返回值，返回 1；否则，返回；否则，返回 0。结束。结束。.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email int SearchRevk( pLinkList list, int k ) pLinkList p, q; int count;/* 距离计数器距离计数器 */p = q = list- link;/* p和和q指向第一个数据结点指向第一个数据结点 */count = 0;wh

18、ile ( p != NULL ) if ( count link; /* q指向下一结点指向下一结点 */ p = p- link; /* p指向下一个结点指向下一个结点 */if ( count = k ) /* 查找成功查找成功 */ printf(%dn, q-data);return 1;else return 0; /* 查找失败查找失败 */.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 6求循环小数求循环小数对于任意的真分数对于任意的真分数 N/M (0 N M 500)，均，均可以求出对应的小数。如果采用链表表示各个可以求出对应的小数。如果采用链表

19、表示各个小数，对于循环节采用循环链表表示。小数，对于循环节采用循环链表表示。head11/8 = 0.125 存储形式存储形式25 . .0. 6125 （循环节（循环节125）存储形式）存储形式5261head.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 算法设计算法设计模拟手工计算过程。模拟手工计算过程。关键：记录计算过程中的余数和对应的商，一关键：记录计算过程中的余数和对应的商，一旦发现余数出现重复，则找到循环节。旦发现余数出现重复，则找到循环节。算法实现算法实现动态申请有动态申请有 M 个元素的指针数组：以每次求个元素的指针数组：以每次求得的余数作为得的余

20、数作为下标下标，对应的数组元素保存，对应的数组元素保存该余该余数对应的商数对应的商。.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email void change( int n, int m, NODE * head ) NODE * * array; NODE * p=head; int k;array = ( NODE * ) malloc( sizeof( NODE * )* m );for ( k=0; knext = (NODE *) malloc( sizeof(NODE) ); p-next-data = n*10 /m; p-next-next = NULL

21、; n = 0; else 处理一般情况处理一般情况 .作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email else if ( arrayn = NULL ) / 若该余数第一次出现若该余数第一次出现 arrayn = p-next = (NODE *) malloc(sizeof(NODE) ); p-next-data = n * 10 / m; / 保存商保存商 n = n * 10 % m; / 余数扩大余数扩大10倍倍 p = p-next; else / 该余数不是第一次出现，则发现循环节该余数不是第一次出现，则发现循环节 p-next = arrayn; /

22、 建立环建立环 n = 0; .作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 求循环节求循环节编写一个尽可能高效的查找循环节起始点的函编写一个尽可能高效的查找循环节起始点的函数：数：NODE * find( NODE * head )。函数的返。函数的返回值为循环节的起点（即图中的指针回值为循环节的起点（即图中的指针p）。）。head11/8 = 0.125 存储形式存储形式25 . .0. 6125 （循环节（循环节125）存储形式）存储形式5261head.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 算法设计算法设计关键是要找出高效

23、算法。关键是要找出高效算法。1. 判断是否有环。判断是否有环。2. 在确认有环的情况下，找到环的开始。在确认有环的情况下，找到环的开始。.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email NODE * find( NODE * head, int * n ) int count=0, ring;NODE * p, * q;p = q = head-next;while ( p!=NULL & q!=NULL ) count +; p = p-next; / p指针一次走一步指针一次走一步 q = q-next; / q指针一次走两步指针一次走两步 if ( q!

24、=NULL ) q = q-next; if ( p = q ) break; / 找到重合点则退出找到重合点则退出if ( q = NULL )/ 如果不存在环则返回如果不存在环则返回*n =0;return NULL;.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email ring = 1;while ( q-next != p ) / 求环长求环长q = q-next;ring +;count = 0; q = p = head-next;while ( count next;while ( p != q )p = p-next;q = q-next;*n = rin

25、g;return p;.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 7将将n ( n1) 个整数存放到一维数组个整数存放到一维数组R中。中。试设计一个在时间和空间两方面都试设计一个在时间和空间两方面都尽可能尽可能高效高效的算法，将的算法，将 R 中保有的序列中保有的序列循环左循环左移移p（0pn）个位置，即将）个位置，即将R中的数据中的数据由：由：(x0, x1, , xp-1, xp, xp+1, , xn-1)变换为：变换为：(xp, xp+1, , xn-1, x0, x1, , xp-1).作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青em

26、ail 问题关键问题关键如何尽可能高效？如何尽可能高效？常规算法常规算法 一般的循环左移算法的时间复杂度肯定是比一般的循环左移算法的时间复杂度肯定是比较大的。较大的。 最差的一种方法：采用一个变量作为辅助空最差的一种方法：采用一个变量作为辅助空间，每次移动一位，反复进行移动间，每次移动一位，反复进行移动 K 次，则时次，则时间复杂度为间复杂度为O( n*k )。 另一种算法是采用另一种算法是采用 p 位辅助空间，空间复杂位辅助空间，空间复杂度度O( p )，时间复杂度，时间复杂度 O( n+p )。.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 基本设计思想基本设计

27、思想先将前面先将前面 p 个元素置反，再将后边个元素置反，再将后边 n-p 元素置元素置反，最后整体置反。反，最后整体置反。参考程序参考程序void leftShift( int r , int n, int p ) if ( p0 & pn ) rever(r, 0, n-1); rever(r, 0, n-p-1); rever(r, n-p, n-1); .作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email void rever( int a , int left, int right ) int k=lift, j=right, temp;while (

28、k 1；1-2；2-3；3-4；4-5；5-6；此时一次循环即将整个数组；此时一次循环即将整个数组移位完毕。移位完毕。.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 基本思想基本思想3. 当一次循环不能将整个数组完全移位时，可从第当一次循环不能将整个数组完全移位时，可从第 n-1位，再进行第（位，再进行第（1）步的操作；如果还没移完，继续）步的操作；如果还没移完，继续从第从第 n-2 位开始循环，依次类推。位开始循环，依次类推。4. 现在的关键之处是移动需要多少次循环。由数论性现在的关键之处是移动需要多少次循环。由数论性质可知：质可知：a. 当当 n 和和 p 的最

29、大公约数（记为的最大公约数（记为 gcd( n, p ) ）为）为 1 时时，一次循环必定将整个数组移动完毕。，一次循环必定将整个数组移动完毕。b. 当当 n 和和 p 的最大公约数（记为的最大公约数（记为gcd( n, p )）大于）大于 1 时，则需要的循环次数就是时，则需要的循环次数就是 gcd( n, p )！如如 n=6，p=2，gcd(6, 2) =2，第一次循环从第，第一次循环从第 6 位开位开始，第二次循环从第始，第二次循环从第 5 位开始，两次后完成！位开始，两次后完成！.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 定义：一个长度为定义：一个长度

30、为 L（L1）的升序序列）的升序序列 S，处，处在第在第 L/2 个位置的数称为个位置的数称为S的中位数。的中位数。例如，若序列例如，若序列 S1 = ( 11, 13, 15, 17, 19 )，则，则S1 的中位数是的中位数是 15。两个序列的中位数是含它们所有元素的升序两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若序列的中位数。例如，若 S2=(2, 4, 6, 8, 20)，则则 S1 和和 S2 的中位数是的中位数是 11。现有两个等长升序序列现有两个等长升序序列 A 和和 B，设计一个在，设计一个在时间和空间两方面都尽可能高效的算法，找时间和空间两方面都尽可能高效的算

31、法，找出两个序列出两个序列 A 和和 B 的中位数。的中位数。.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 基本设计思想基本设计思想分别求两个升序序列分别求两个升序序列A、B的中位数，设为的中位数，设为a和和b。求中位数的过程如下：。求中位数的过程如下：1. 若若a=b，则，则a或或b即为所求的中位数，结束；即为所求的中位数，结束；2. 若若ab，则舍弃，则舍弃A中较大一半，同时舍弃中较大一半，同时舍弃B中中较小一半，要求两次舍弃的元素个数相同。较小一半，要求两次舍弃的元素个数相同。4. 在保留的两个升序序列中，重复上述过程，在保留的两个升序序列中，重复上述过程，直到两个序列中均只含直到两个序列中均只含 1 个元素时为止，则个元素时为止，则较小者即为所求的中位数。较小者即为所求的中位数。.作者 (时间 2000年）北京理工大学计算机科学工程系 秦怀青email 基本设计思想基本设计思想int M_Search ( int A , int B , int n ) int start1, end1, mid1, start2