下载文档原格式
. . . . .一、单选题第1章绪论1、在数据结构中，从逻辑上可以把数据结构分成A、动态结构和静态结构C、线性结构和非线性结构2、算法分析的两个主要方面是A、空间复杂性和时间复杂性C、可读性和文档性3、数据的不可分割的最小单位是B、紧凑结构和非紧凑结构D、内部结构和外部结构B、正确性和简明性D、数据复杂性和程序复杂性A、结点B、数据元素C、数据项D、数据对象4、在任何问题中，数据元素都不是孤立存在的，而是在它们之间存在着某种关系，这种数据元素相互之间的关系称为A、规则B、集合C、结构D、运算5、与程序运行时间有关的因素主要有以下四方面，其中与算法关系密切的是A、问题的规模C、机器执行速度二、判断题1、数据结构是带有结构的数据元素的集合。
2、程序越短，运行的时间就越少。
3、处理同一问题的算法是唯一的。
B、机器代码质量的优劣D、语句的执行次数4、一个完整算法可以没有输入，但必须有输出。
三、填空题1、______________是数据的基本单位，在计算机程序中通常作为一个整体进行考虑和处理。
2、______________结构的数据元素之间存在一对多的关系。
3、数据结构的形式化定义为(D，S)，其中D 是______________的有限集，S 是 D 上关系的有限集。
4、数据结构在计算机中的______________称为存储结构。
5、数据元素之间的关系在计算机中有两种不同的表示方法：顺序映象和非顺序映象，由此- 1 -得到两种不同的存储结构是______________存储结构和______________存储结构。
6、一个算法具有五个特性：______________、______________、______________、有零个或多个输入、有一个或多个输出。
7、评价一个算法的好坏应该从算法的正确性、可读性、___________和_________________等几方面进行。
四、解答题1、设n 为正整数。
根据两个有序单链表生成一个新的有序单链表，原有单链表保持不变。
要求新生成的链表中不允许有重复元素。
算法如下ListNode * Merge ( ListNode * L1, ListNode * L2 ){//根据两个带表头结点的有序单链表L1和L2, 生成一个新的有序单链表ListNode *first = new ListNode;ListNode *p1 = L1->link, *p2 = L2->link, *p = first, *q;while ( p1 != NULL && p2 != NULL ){q = new ListNode;if ( p1->data == p2->data ){ q->data = p1->data; p2 = p2->link; p1 = p1->link; }else if ( p1->data < p2->data ){ q->data = p1->data; p1 = p1->link; }else{ q->data = p2->data; p2 = p2->link; }p->link = q; p = q;}while ( p1 != NULL ){q = new ListNode; q->data = p1->data; p1 = p1->link;p->link = q; p = q;}while ( p2 != NULL ){q = new ListNode; q->data = p2->data; p2 = p2->link;p->link = q; p = q;}p->link = NULL;return first;}2．设有一个线性表(e0, e1, …, e n-2, e n-1) 存放在一个一维数组A[arraysize]中的前n个数组元素位置。
算法设计题打印部分假设有两个按元素值递增次序排列的线性表均以单链表形式存储。
请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表并要求利用原来两个单链表的结点存放归并后的单链表。
【北京大学1998 三、1 5分】类似本题的另外叙述有1设有两个无头结点的单链表头指针分别为hahb链中有数据域data链域next两链表的数据都按递增序存放现要求将hb表归到ha表中且归并后ha仍递增序归并中ha表中已有的数据若hb中也有则hb中的数据不归并到ha中hb的链表在算法中不允许破坏。
【南京理工大学1997 四、315分】PROCEDURE mergehahb 2已知头指针分别为la和lb 的带头结点的单链表中结点按元素值非递减有序排列。
写出将la 和lb两链表归并成一个结点按元素值非递减有序排列的单链表其头指针为lc并计算算法的时间复杂度。
【燕山大学1998 五20分】 2. 图编者略中带头结点且头指针为ha和hb的两线性表A和B 分别表示两个集合。
两表中的元素皆为递增有序。
请写一算法求A和B的并集AUB。
要求该并集中的元素仍保持递增有序。
且要利用A和B的原有结点空间。
【北京邮电大学1992 二15分】类似本题的另外叙述有1 已知递增有序的两个单链表AB分别存储了一个集合。
设计算法实现求两个集合的并集的运算A:A∪B【合肥工业大学1999 五、18分】2已知两个链表A和B分别表示两个集合其元素递增排列。
编一函数求A与B的交集并存放于A链表中。
【南京航空航天大学2001 六10分】3设有两个从小到大排序的带头结点的有序链表。
试编写求这两个链表交运算的算法即L1∩L2。
要求结果链表仍是从小到大排序但无重复元素。
【南京航空航天大学1996 十一10分】4己知两个线性表A B均以带头结点的单链表作存储结构且表中元素按值递增有序排列。
设计算法求出A 与B的交集C要求C另开辟存储空间要求C同样以元素值的递增序的单链表形式存贮。
A／＼B C ／＼ ＼D E F ／ 数据结构练习一一、单项选择题1．若某链表中最常用的操作是在最后一个结点之后插入一个结点和删除最后一个结点，则采用 存储方式最节省运算时间。
(1)单链表 (2)双链表(3)单循环链表 (4)带头结点的双循环链表2．设一个栈的输入序列为A ，B ，C ，D ，则借助一个栈所得到的输出序列不可能是(1)A ，B ，C ，D (2)D ，C ，B ，A (3)A ，C ，D ，B (4)D ，A ，B ，C3．串是 。
(1)不少于一个字母的序列 (2)任意个字母的序列(3)不少于一个字符的序列 (4)有限个字符的序列4．链表不具有的特点是 。
(1)可随机访问任一元素 (2)插入删除不需要移动元素(3)不必事先估计存储空间 (4)所需空间与线性表长度成正比5．在有n 个叶子结点的哈夫曼树中，其结点总数为 。
(1)不确定 (2)2n (3)2n+1 (4)2n-16．任何一个无向连通图的最小生成树(1)只有一棵 (2)有一棵或多棵 (3)一定有多棵 (4)可能不存在7．将一棵有100个结点的完全二叉树从根这一层开始，每一层上从左到右依次对结点进行编号，根结点的编号为1，则编号为49的结点的左孩子编号为 。
(1)98 (2)99 (3)50 (4)488.下列序列中， 是执行第一趟快速排序后得到的序列(排序的关键字类型是字符串)。
(1)[da ，ax ，eb ，de ，bb]ff[ha ，gc] (2)[cd ，eb ，ax ，da]ff[ha ，gc ，bb](3)[gc ，ax ，eb ，cd ，bb]ff[da ，ha] (4)[ax ，bb ，cd ，da]ff[eb ，gc ，ha]9．用n 个键值构造一棵二叉排序树，最低高度为 。
(1)n/2 (2)n (3)[log 2n] (4)[log 2n+1]10．二分查找法要求查找表中各元素的键值必须是 排列。
(1)递增或递减 (2)递增 (3)递减 (4)无序11.对于键值序列(12，13，11，18，60，15，7，18，25，100)，用筛选法建堆，必须从键值为 的结点开始。
【例2.5】假设有n（n>1）个线性表顺序地存放在顺序表S[1..m]中，令F[i]和R[i]指示第i个（1≤i≤n）表的第1个元素和最后1个元素在S中的位置，并设定R[i]<F[i+1]，F[n+1]=m+1，如图2.2所示。
试写出实现下列要求的算法：（1）在第i个表中的第j项后面插入1个元素，仅当整个[1..m]空间填满时，不允许进行插入操作。
（2）删除第i个表中的第j个元素，要求在删除第j个元素后，该表仍为顺序存储的线性表。
【解】本题实质上是将n个线性表（长度可能不相同）放在一个连续空间（长度为m），来解决这些线性表的插入和删除问题。
（1）的算法如下：void ins(i，j，x){int p，k;if (R[n]==m)cout << "上溢" << endl;else{for (p=n;p>=i+1;p--) //将i+1到n的线性表后移一个元素{for (k=R[p];k>=F[p];k--) //将第p个线性表后移一个元素S[k+1]=S[k];R[p]++;F[p]++; //第p个线性表的首尾元素位置均增1}for (p=R[i];p>=j+1;p--)//将第i个线性表中的第j个位置起的元素均后移S[p+1]=S[p];S[p]=x; //在第i个线性表的第j个位置处存放xR[p]++; //第p个线性表的R[p]增1}}（2）的算法如下：void del(i，j){for (p=F[i]+j-1;p<=m;p++) //元素前移覆盖要删除的元素S[p]=S[p+1];for (p=i;p<=n;p++) //第i个及以后的线性表的R[i]值减1R[p]--;for (p=i+1;p<=n;p++) //第i＋1个及以后的线性表的F[i]值减1F[p]--;}【例2.6】设A=(a1，a2，⋯，a m)和B=(b1，b2，⋯，b n)均为顺序表。
2.3 课后习题解答2.3.2 判断题1．线性表的逻辑顺序与存储顺序总是一致的。
（×）2．顺序存储的线性表可以按序号随机存取。
（√）3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。
（×）4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。
（√）5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。
（×）6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。
（√）7．线性表的链式存储结构优于顺序存储结构。
（×）8．在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。
（√）9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。
（√）10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
（×）11．静态链表既有顺序存储的优点，又有动态链表的优点。
所以它存取表中第i个元素的时间与i无关。
（×）12．线性表的特点是每个元素都有一个前驱和一个后继。
（×）2.3.3 算法设计题1．设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。
试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。
【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插入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)。
《数据结构与算法》课后习题答案2.3 课后习题解答2.3.2 判断题1 ?线性表的逻辑顺序与存储顺序总是一致的。
（X）2 ?顺序存储的线性表可以按序号随机存取。
（V）3?顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。
（X）4?线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此属于同一数据对象。
（V）5?在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定相邻。
（X）6 ?在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。
（V）7 ?线性表的链式存储结构优于顺序存储结构。
（X）&在线性表的顺序存储结构中，插入和删除时移动元素的个数与该元素的位置有关。
（V）9 ?线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。
（V）10. 在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。
（X）11. 静态链表既有顺序存储的优点，又有动态链表的优点。
所以它存取表中第i个元素的时间与i无关。
（X）12 ?线性表的特点是每个元素都有一个前驱和一个后继。
（X）2.3.3 算法设计题1.设线性表存放在向量A[arrsize]的前elenum个分量中，且递增有序。
试写一算法，将x 插入到线性表的适当位置上，以保持线性表的有序性，并且分析算法的时间复杂度。
【提示】直接用题目中所给定的数据结构（顺序存储的思想是用物理上的相邻表示逻辑上的相邻，不一定将向量和表示线性表长度的变量封装成一个结构体），因为是顺序存储，分配的存储空间是固定大小的，所以首先确定是否还有存储空间，若有，则根据原线性表中元素的有序性，来确定插入元素的插入位置，后面的元素为它让出位置，（也可以从高下标端开始一边比较，一边移位）然后插入x ，最后修改表示表长的变量。
int insert (datatype A[],int *elenum,datatype x) {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. 简述下列术语：数据、数据元素、数据对象、数据结构、存储结构、数据类型和抽象数据类型。
2. 在程序设计中，常用下列三种不同的出错处理方式：(1) 用exit语句终止执行并报告错误；(2) 以函数的返回值区别正确返回或错误返回；(3) 设置一个整型变量的函数参数以区别正确返回或某种错误返回。
试讨论这三种方法各自的优缺点，并编写算法，计算i!×2i 的值并存入数组a[0..arrsize-1] 的第i-1 个分量中(i=1,2,…,n)。
假设计算机中允许的整数最大值为maxint，则当n>arrsize 或对某个k(1≤k≤n) 使k!×2k>maxint 时，应按出错处理。
注意选择你认为较好的出错处理方法。
3. 在程序设计中，可采用下列三种方法实现输出和输入：(1) 通过scanf 和printf 语句；(2) 通过函数的参数显式传递；(3) 通过全局变量隐式传递。
试讨论这三种方法的优缺点，并编写算法求一元多项式的值，并确定算法中每一语句的执行次数和整个算法的时间复杂度。
注意选择你认为较好的输入和输出方法，本题的输入为ai (i=0,1,…,n)，x0 和n，输出为。
4. 设n 为正整数。
试确定下列各程序段中前置以记号@ 的语句的频度：(1) i=1; k=0;while ( i<=n-1) {@ k += 10 * i;i++;}(2) i=1; k=0;do {@ k +=10 * i;i++;} while(i<=n-1);(3) i = 1; k = 0;while (i<=n-1) {i++ ;@ k+= 10 * i;}(4) k=0;for( i=1; i<=n; i++) {for (j=i ; j<=n; j++)@ k++;}(5) for( i=1; i<=n; i++) {for (j=1; j<=i; j++) {for (k=1; k<=j; k++)@ x += delta;}(6) i=1; j=0;while (i+j<=n) {@ if (i>j ) j++ ;else i++ ;}(7) x=n; y=0; // n 是不小于1的常数while (x>=(y+1)*(y+1)) {@ y++;}(8) x=91; y=100;while (y>0 ) {@ if (x>100 ) { x -= 10; y- -; }else x++;}第二章线性表【基础知识题】1. 描述以下三个概念的区别：头指针，头结点，首元结点(第一个元素结点)。
