logo资料库

数据结构答案 李云清版.doc

发布时间：2022-06-05 发布人：admin 分类：说明书 资料大小：0.32M 资料格式：doc 举报 版权申诉
第1页 / 共91页
第2页 / 共91页
第3页 / 共91页
第4页 / 共91页
第5页 / 共91页
第6页 / 共91页
第7页 / 共91页
第8页 / 共91页
资料共91页，剩余部分请下载后查看
    1 数据结构 （C 语言版）（第2 版） 习题解析 揭安全 李云清 杨庆红 江西师范大学计算机信息工程学院 联系方式：janquan@163.com （习题答案仅供参考） 2 第1 章 绪论 1.1 什么是数据结构？ 【答】：数据结构是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存 储 于计算机中，并在这些数据上定义了一个运算集合。 1.2 数据结构涉及哪几个方面？ 【答】：数据结构涉及三个方面的内容，即数据的逻辑结构、数据的存储结构和数据的运算 集 合。 1.3 两个数据结构的逻辑结构和存储结构都相同，但是它们的运算集合中有一个运算的定义 不 一样，它们是否可以认作是同一个数据结构？为什么？ 【答】：不能，运算集合是数据结构的重要组成部分，不同的运算集合所确定的数据结构是 不 一样的，例如，栈与队列它们的逻辑结构与存储结构可以相同，但由于它们的运算集合不一 样， 所以它们是两种不同的数据结构。 1.4 线性结构的特点是什么？非线性结构的特点是什么？ 【答】：线性结构元素之间的关系是一对一的，在线性结构中只有一个开始结点和一个终端 结 点，其他的每一个结点有且仅有一个前驱和一个后继结点。而非线性结构则没有这个特点， 元 素之间的关系可以是一对多的或多对多的。 1.5 数据结构的存储方式有哪几种？ 【答】：数据结构的存储方式有顺序存储、链式存储、散列存储和索引存储等四种方式。
    1.6 算法有哪些特点？它和程序的主要区别是什么？ 【答】：算法具有（1）有穷性（2）确定性（3）0 个或多个输入（4）1 个或多个输出（5） 可 行性等特征。程序是算法的一种描述方式，通过程序可以在计算机上实现算法。 1.7 抽象数据类型的是什么？它有什么特点？ 【答】：抽象数据类型是数据类型的进一步抽象，是大家熟知的基本数据类型的延伸和发展。 抽象数据类型是与表示无关的数据类型，是一个数据模型及定义在该模型上的一组运算。对 一 个抽象数据类型进行定义时，必须给出它的名字及各运算的运算符名，即函数名，并且规定 这 些函数的参数性质。一旦定义了一个抽象数据类型及具体实现，程序设计中就可以像使用基 本 数据类型那样，十分方便地使用抽象数据类型。抽象数据类型的设计者根据这些描述给出操 作 的具体实现，抽象数据类型的使用者依据这些描述使用抽象数据类型。 1.8 算法的时间复杂度指的是什么？如何表示？ 【答】：算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同 的 机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法 在 同一台计算机上执行的时间也不一样，另外，算法执行的时间还与输入数据的状态有关，所 以 对于算法的时间复杂性，采用算法执行过程中其基本操作的执行次数，称为计算量来度量。 算 法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为n 的数据处理问题，用 T(n)表示算法基本操作的执行次数。为了评价算法的执行效率，通常采用大写O 符号表示算 法 的时间复杂度，大写O 符号给出了函数f 的一个上限。其它义如下： 3 定义：f (n)=O (g (n)) 当且仅当存在正的常数c 和n0，使得对于所有的n≥n0，有f (n) ≤c g(n)。 上述定义表明，函数f 顶多是函数g 的c 倍，除非n 小于n0。因此对于足够大的n (如n≥n0)， g 是f 的一个上限（不考虑常数因子c）。在为函数f 提供一个上限函数g 时，通常使用比 较 简单的函数形式。比较典型的形式是含有n 的单个项（带一个常数系数）。表1-1 列出了一 些 常用的g 函数及其名称。对于表1-1 中的对数函数logn，没有给出对数基，原因是对于任何 大 于1 的常数a 和b 都有logan =logbn/logba,所以logan 和logbn 都有一个相对的乘法系数 1/logba， 其中a 是一个常量。 表1-1 常用的渐进函数 1.9 算法的空间复杂度指的是什么？如何表示？ 【答】：算法的空间复杂度是指算法在执行过程中占用的额外的辅助空间的个数。可以将它 表
    示为问题规模的函数，并通过大写O符号表示空间复杂度。 1.10 对于下面的程序段，分析带下划线的语句的执行次数，并给出它们的时间复杂度T(n)。 （1） i++; （2） for(i=0;ia[j+1]) k=j; t=a[k]; a[k]=a[i]; a[i]=t; } （5）for(i=0;i
    （7）队列是一种特殊的线性表，其特殊性在于（ C ）。 A．插入和删除在表的不同位置执行 B．插入和删除在表的两端位置执行 C．插入和删除分别在表的两端执行 D．插入和删除都在表的某一端执行 （8）栈是一种特殊的线性表，具有（ B ）性质。 A．先进先出 B．先进后出 C．后进后出 D．顺序进出 （9）顺序循环队列中（数组的大小为n），队头指示front 指向队列的第1 个元素，队尾 指示rear 指向队列最后元素的后1 个位置，则循环队列中存放了n − 1 个元素，即循环队 列满 的条件为（ B ）。 A．(rear + 1)%n = front − 1 B．(rear + 1)%n = front C．(rear)%n = front D．rear + 1 = front （10）顺序循环队列中（数组的大小为6），队头指示front 和队尾指示rear 的值分别为3 和0，当从队列中删除1 个元素，再插入2 个元素后，front 和rear 的值分别为（ D ）。 A．5 和1 B．2 和4 C．1 和5 D．4 和2 2.2 什么是顺序表？什么是栈？什么是队列？ 5 【答】：当线性表采用顺序存储结构时，即为顺序表。栈是一种特殊的线性表，它的特殊性 表 现在约定了在这种线性表中数据的插入与删除操作只能在这种线性表的同一端进行（即栈 顶）， 因此，栈具有先进后出、后进先出的特点。队列也是一种特殊的线性表，它的特殊性表现在 约 定了在这种线性表中数据的插入在表的一端进行，数据的删除在表的另一端进行，因此队列 具 有先进先出，后进后出的特点。 2.3 设计一个算法，求顺序表中值为x 的结点的个数。 【答】：顺序表的存储结构定义如下（文件名seqlist.h）： #include #define N 100 /*预定义最大的数据域空间*/ typedef int datatype; /*假设数据类型为整型*/ typedef struct { datatype data[N]; /*此处假设数据元素只包含一个整型的关键字域*/ int length; /*线性表长度*/ } seqlist; /*预定义的顺序表类型*/ 算法countx（L,x）用于求顺序表L 中值为x 的结点的个数。 int countx(seqlist *L,datatype x) { int c=0; int i; for (i=0;ilength;i++) if (L->data[i]==x) c++; return c; } 2.4 设计一个算法，将一个顺序表倒置。即，如果顺序表各个结点值存储在一维数组a 中， 倒
    置的结果是使得数组a 中的a[0]等于原来的最后一个元素，a[1] 等于原来的倒数第2 个元 素，…，a 的最后一个元素等于原来的第一个元素。 【答】：顺序表的存储结构定义同题2.3，实现顺序表倒置的算法程序如下： void verge(seqlist *L) {int t,i,j; i=0; j=L->length-1; while (idata[i]; L->data[i++]=L->data[j]; L->data[j--]=t; } } 2.5 已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为x 的结 点， 使顺序表中的结点仍然是从小到大有序。 【答】：顺序表的定义同题2.3，实现本题要求的算法程序如下： 6 void insertx(seqlist *L,datatype x) {int j; if (L->lengthlength-1; while (j>=0 && L->data[j]>x) { L->data[j+1]=L->data[j]; j--; } L->data[j+1]=x; L->length++; } } 2.6 将下列中缀表达式转换为等价的后缀表达式。 (1) 5+6*7 (2) (5-6)/7 (3) 5-6*7*8 (4) 5*7-8 (5) 5*(7-6)+8/9 (6) 7*(5-6*8)-9 【答】： (7) 5+6*7 后缀表达式：5 6 7*+ (8) (5-6)/7 后缀表达式：5 6-7/ (9) 5-6*7*8 后缀表达式：5 6 7*8*- (10) 5*7-8 后缀表达式：5 7* 8- (11) 5*(7-6)+8/9 后缀表达式：5 7 6-*8 9/+ (12) 7*(5-6*8)-9 后缀表达式：7 5 6 8*-*9-
    2.7 循环队列存储在一个数组中，数组大小为n，队首指针和队尾指针分别为front 和rear， 请 写出求循环队列中当前结点个数的表达式。 【答】：循环队列中当前结点个数的计算公式是：(n+rear-front)%n 2.8 编号为1,2,3,4 的四列火车通过一个栈式的列车调度站，可能得到的调度结果有哪些？如 果 有n 列火车通过调度站，请设计一个算法，输出所有可能的调度结果。 【答】： 解题思路：栈具有先进后出、后进先出的特点，因此，任何一个调度结果应该是1，2，3，4 全排列中的一个元素。由于进栈的顺序是由小到大的，所以出栈序列应该满足以下条件：对 于 序列中的任何一个数其后面所有比它小的数应该是倒序的，例如4321 是一个有效的出栈序 列， 1423 不是一个有效的出栈结果（4 后面比它小的两个数2，3 不是倒序）。据此，本题可以 通过 算法产生n 个数的全排列，然后将满足出栈规则的序列输出。 产生n 个数的全排列有递归与非递归两种实现算法。 产生全排列的递归算法： 7 设R={r1,r2,…,rn}是要进行排列的n 个元素，Ri=R-{ri}。集合X 中元素的全排列记为 perm(X)。(ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀ri 得到的排列。R 的全 排 列可归纳定义如下： 当n=1 时，perm(R)=(r)，其中r 是集合R 中惟一的元素； 当n>1 时，perm(R)由(r1)perm(R1),(r2)perm(R2),…,(rn)perm(Rn)构成。 依此递归定义，可设计产生perm(R)的递归算法如下： 递归解法：(2_8_1.c) #include int cont=1; /*全局变量，用于记录所有可能的出栈序列个数*/ void print(int str[],int n); /*求整数序列str[]从k 到n 的全排列*/ void perm(int str[],int k,int n) {int i,temp; if (k==n-1) print(str,n); else { for (i=k;i
    {int i,j,k,l,m,flag=1,b[2]; for(i=0;istr[j]) {if (m==0) b[m++]=str[j]; else {if (str[j]>b[0]) {flag=0;} else b[0]=str[j]; } } } if(flag) /*满足出栈规则则输出str[]中的序列*/ { printf(" %2d:",cont++); for(i=0;i
    所有的排列，不能立即调整得太大，如本例中将数字6 与数字4 交换得到的排列为126453 就 不是排列124653 的下一个排列。为得到排列124653 的下一个排列，应从已考察过的那部分 数 字中选出比数字4 大，但又是它们中最小的那一个数字，比如数字5，与数字4 交换。该数 字 也是从后向前考察过程中第一个比4 大的数字，5 与4 交换后，得到排列125643。在前面数 字 1，2，5 固定的情况下，还应选择对应最小整数的那个排列，为此还需将后面那部分数字的 排 列颠倒，如将数字6，4，3 的排列顺序颠倒，得到排列1,2,5,3,4,6，这才是排列1，2，4， 6， 9 5，3 的下一个排列。按照以上想法可以编写非递归程序实现n 个数的全排列，对满足进出 栈 规则的排列则计数并输出。 /*本程序输出1 2 ... n 个序列进栈出栈的序列*/ #include int pl(int n) { int a[100]; /*最大处理范围为99 个数*/ int flag=1,flag1=0; FILE *rf ; int i,j,k,x,count=0; rf = fopen("stack.txt", "w") ; /*pl.txt 用于存放进出栈序列结果*/ for (i=1;i<=n;i++) /*初始序列*/ a[i]=i; while (flag) /* 还剩余未输出的排列*/ { flag1=1; /* 判断本次排列是否符合进栈出栈序列 */ for (i=1;i<=n;i++) { j=i+1; while (j<=n && a[j]>a[i]) j++; /* 找a[i]后第一个比a[i]小__________的元素a[j]*/ k=j+1; while (k<=n) /* 如果a[j]后还有比a[i]小且比a[j]大的元素,则此排列无效*/ {if ( a[k] a[j]) flag1=0; k++; } } if (flag1) { for (i=1;i<=n;i++) /*输出当前排列*/ { printf("%4d",a[i]); fprintf(rf,"%4d",a[i]);} printf("\n"); fprintf(rf,"\n"); count++; /*计数器加1*/ } i=n; /*从后向前找相邻位置后大前小的元素值*/ while (i>1 && a[i]
    分享到：
    赞 收藏

    相关推荐

    资料库

    考试认证

    共收录20637份资料，累计11个分类，关注成员有19位，主要包括：真题,美赛,软考,PMP,Linux/Unix认证,思科认证,微软认证,Oracle认证,华为认证,软考等考,其它

    热门标签

    真题 美赛 软考 PMP Linux/Unix认证 思科认证 微软认证 Oracle认证 华为认证 软考等考 其它

    最新资料