数据结构(第3版)习题答案

1、高等学校精品资源共享课程 十二五普通高等教育国家级本科规划教材 绪论 3 什么是数据结构 【答】：数据结构是指按一定的逻辑结构组成的一批数据，使用某种存储结构将这批数据存储 于计算机中，并在这些数据上定义了一个运算集合。 数据结构涉及哪几个方面 【答】：数据结构涉及三个方面的内容，即数据的逻辑结构、数据的存储结构和数据的运算集 合。 一样，它们是否可以认 【答】：不能，运算集 一样的，例如，栈与队; 1-14鼻启童區也41喀电笋!3屎 组成!部分，不的运集合 【答】：线性结构元素 点，其他的每一个结点 素之间的关系可以是一 匮是什么构皿用 继继结点。而 多的。 MPM心出*MMi常;LIWI

2、1(.7 Vt JtSJOYJ 【答】： 【答】：算法具有（ 行性等特征。 【答】：抽象数据类型: 抽象数据类型是与表示 个抽象数据类型进行定 些函数的参数性质。 数据类型那样， 的具体实现， 使用抽象数据 ht-ii 1 nrirh 的“ 二忙灌曹:is:篙廿4 #玉弗 不 ，元 :一样, 展。 对一 多个输出（5 ）可 【答】：算法执行时间的度量不是采用算法执行的绝对时间来计算的，因为一个算法在不同的 机器上执行所花的时间不一样，在不同时刻也会由于计算机资源占用情况的不同，使得算法在 同一台计算机上执行的时间也不一样，另外，算法执行的时间还与输入数据的状态有关，所以 对于算法的时间复杂性，

3、采用算法执行过程中其基本操作的执行次数，称为计算量来度量。算 法中基本操作的执行次数一般是与问题规模有关的，对于结点个数为n的数据处理问题，用 0符号表示算法 T（n）表示算法基本操作的执行次数。为了评价算法的执行效率，通常采用大写 的时间复杂度，大写 0符号给岀了函数 f的一个上限。其它义如下： F；十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程 定义：f (n)=0 (g (n)当且仅当存在正的常数c和n ,使得对于所有的nn,有f (n) c g(n) 上述定义表明，函数f顶多是函数 g的c倍，除非 n小于n (因此对于足够大的n (如nn, g是f的一个上限(不考虑常数因

4、子c)(在为函数 f提供一个上限函数g时，通常使用比较 简单的函数形式(比较典型的形式是含有n的单个项(带一个常数系数)(表 1-1列岀了一些 常用的g函数及其名称(对于表1-1中的对数函数logn，没有给岀对数基，原因是对于任何大 于1的常数a和b都有logn =logn/loga,所以logn和logn都有一个相对的乘法系数1/loga， 其中a是一个常量。 表1-1常用的渐进函数 函数 名称 1 常数 log n 对数 n 线性 nlogn n 个 logn n 平方 n 立方 2 指数 n! 阶乘 算法的空间复杂度指的是什么如何表示 【答】：算法的空间复杂度是指算法在执行过程中占用的额

5、外的辅助空间的个数(可以将它表 示为问题规模的函数，并通过大写0符号表示空间复杂度。 对于下面的程序段，分析带下划线的语句的执行次数，并给岀它们的时间复杂度T(n)( (1) _i+ ; (2) for(i=0;i n;i+) if (aix) x=ai; (3) for(i=0;in;i+) for(j=0;j n;j+) printf(“ d ,i+j); (4) for (i=1;i=n_1;i+) k=i; for(j=i+1;jaj+1) k=j; t=ak; ak=ai; ai=t; (5) for(i=0;in;i+) for(j=0;j n;j+) +x;s=s+x; 【答】：

6、(1) O (1);( 2) O (n )；( 3) O (n);( 4) O ( n)；( 5) O (n) 5 .”】十二五普通高等教育国家级本科规划教材 高等学校精品资源共享课程 f 宁 第2章线性表及其顺序存储 选择题 （1）表长为n的顺序存储的线性表，当在任何位置上插入或删除一个元素的概率相等时, 插入一个元素所需移动元素的平均个数为（ E ），删除一个元素所需移动元素的平均个数 为（A ）o A.( n1) /2 B. n C. n+1 D. n1 E. n/2 F. (n+1)/2 G. (n 2)/2 （2）设栈S和队列 Q的初始状态为空， 元素 e1、 e2、e3、e4、 e

7、5 和 e6 依次通过栈 s, 一个元素岀栈后即进入队列 Q，若6个元素岀队的序列为 e2、e4、e3 ，、e6、e5 和e1,则栈S 的谷量至少应该为（C） o A. 6 B. 4 C. 3 D. 2 （3）设栈的输入序列为 1、2、3n,若输岀序列的第- 一个元素为 n，则第 i个输出的元素为 (B )o A.不确定 B. ni+1 C. i D. ni （4）在一个长度为 n 的顺序表中删除第 i 个、兀素（ 1=i=n) 时， 需向刖移动（A ）个 元素。 A. ni B. ni+1 C. ni1 D. i （5）若长度为 n的线性表采用顺序存储结构存储，在第 i个位置上插入一个新元素

8、的时 间复杂度为（A） A.插入和删除在表的不同位置执行 C.插入和删除分别在表的两端执行 （8）栈是一种特殊的线性表，具有（ B.插入和删除在表的两端位置执行 D.插入和删除都在表的某一端执行 B ）性质。 A.先进先岀B.先进后岀 C.后进后出 D.顺序进出 （9）顺序循环队列中（数组的大小为 n）,队头指示front指向队列的第 1个元素，队尾 指示rear指向队列最后元素的后1个位置，则循环队列中存放了 n 1个元素，即循环队列满 的条件为（B ） A. （rea叶1）%n=front1 C. （rear）%n=front （10）顺序循环队列中（数组的大小为 和0,当从队列中删除 1

9、个元素，再插入 A. 5 和 1B. 2 和 4 B. (rea叶1)% n=front D. rear+1=front 6），队头指示 2个元素后, front和队尾指示 rear的值分别为 3 front和rear的值分别为（ C. 1 和 5D. 4 和 2 A. O(n) B. O(1)C. O(n) D. O(n) (6)表达式 a*(b+c)d 的后缀表达式是（B )o A. abcd*+ B. abc+*dC. abc*+d D. +*abcd （7）队列是一种特殊的线性表，其特殊性在于（ C )o 7 什么是顺序表什么是栈什么是队列 十二五普通高等教育国家级本科规划教材高等学校

10、精品资源共享课程 【答】：当线性表采用顺序存储结构时，即为顺序表。栈是一种特殊的线性表，它的特殊性表 现在约定了在这种线性表中数据的插入与删除操作只能在这种线性表的同一端进行（即栈顶）， 因此，栈具有先进后出、后进先出的特点。队列也是一种特殊的线性表，它的特殊性表现在约 定了在这种线性表中数据的插入在表的一端进行，数据的删除在表的另一端进行，因此队列具 有先进先出，后进后出的特点。 设计一个算法，求顺序表中值为 x的结点的个数。 【答】：顺序表的存储结构定义如下（文件名）： #in elude #defi ne N 100 /*预定义最大的数据域空间 */ typedef int dataty

11、pe; typedef struct datatype dataN; int len gth; seqlist; /*假设数据类型为整型 */ /*此处假设数据元素只包含一个整型的关键字域*/ /*线性表长度*/ /*预定义的顺序表类型 */ 算法countx （ L,x）用于求顺序表L中值为x的结点的个数 int cou ntx(seqlist *L,datatype x) int c=0; int i; for (i=0;ile ngth;i+) if (L-datai=x) c+; return c; 设计一个算法，将一个顺序表倒置。即，如果顺序表各个结点值存储在一维数组a中，倒 置的结

12、果是使得数组a中的a0等于原来的最后一个元素，a1等于原来的倒数第 2个元 素，a的最后一个元素等于原来的第一个元素 【答】：顺序表的存储结构定义同题，实现顺序表倒置的算法程序如下: void verge（seqlist *L） int t,i,j; i=0; j=L-le ngth-1; while （idatai; L-datai+=L-dataj; L-dataj-=t; 已知一个顺序表中的各结点值是从小到大有序的，设计一个算法，插入一个值为x的结点, 使顺序表中的结点仍然是从小到大有序。 【答】：顺序表的定义同题，实现本题要求的算法程序如下: IM* TMCT void in sert

13、x(seqlist *L,datatype x) int j； if (L-le ngthle ngth-1; while (j=0 j-; L-dataj+1=x; L-le ngth+; 将下列中缀表达式转换为等价的后缀表达式。 (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 【答】： 5+6*7 后缀表达式 (8) (5-6)/7 后缀表达式 (9) 5-6*7*8 后缀表达式 (10)5*7-8 后缀表达式 (11)5*(7-6)+8/9 后缀表达式 (12)7*(5-6*8)-9

14、后缀表达式 循环队列存储在一个数组中，数组大小为 写岀求循环队列中当前结点个数的表达式。 5 6 7*+ 5 6-7/ 5 6 7*8*- 5 7* 8 5 7 6-*8 9/+ 7 5 6 8*-*9- 【答】：循环队列中当前结点个数的计算公式是: (n+rear-fr on t)% n n,队首指针和队尾指针分别为front和rear，请 编号为1,2,3,4的四列火车通过一个栈式的列车调度站，可能得到的调度结果有哪些如果 有n列火车通过调度站，请设计一个算法，输岀所有可能的调度结果。 【答】： 方法一： 算法思想：逐次输岀所有可能，用回溯法。即： 总体：对原始序列中的每一个元素，总是先入

15、栈，后出栈 1 .入栈后的操作：a.该元素出栈；b.下一个元素入栈； 2 岀栈后的操作：a.(栈中其他元素)继续岀栈；b.(原始序列中)下一个数入栈； 注意：回溯法，关键在于回溯，即在某分支结点X:处理X的一个子分支，再退回分支X， 接着处理 X的下一个子分支，若所有X的子分支处理完，再退回上一层分支节点。所谓“退回”， 实际上就是恢复。 程序代码： #in elude #defi ne MAX 26 typedef struct s char aMAX; int top; Stack; /*定义一些全局变量 */ Stack S;/*定义全局性的栈 */ char dMAX,seqMAX;

16、/*dMAX用于存储原始入栈序列，seqMAX用于存储输岀序列 */ int len;/*定义将通过栈的元素个数*/ in t cou nt=O; /*用于统计输岀序列的个数*/ void initStack(Stack *S) /* 初始化空栈 */ S-top=-1; void push(Stack *S, char x) /* 进栈 */ if (S-top=MAX) return; S_top+; S-aS-top=x; char pop(Stack *S)/* 岀栈 */ if (S-top=-1) pri ntf(ERROR, POP Empty Stack); return -1

17、; S-top-; return S-aS-top+1; int isEmpty(Stack *S)/* 判断栈是否为空 */ if (S-top=-1) return 1; return 0; void outSeq(char *seq, int len)/* 输岀顶点序列 */ int i; for(i=0; ile n; i+) prin tf(%2c,seqi); pri ntf(n); void scheduler(i nt pos, int seq_pos) -IMfe /*pos:处理到原始数据中的第pos个元素， seq_pos:若岀栈，应放在当前输岀数组的第seq_pos个位

18、置 */ int i=0;char t; /*对任何一个数，总是先进栈，再出栈。另外，这里不需要循环，类似于“查找数组中元 素”用递归*/ if(pos=le n cou nt+; int mai n() int i; pri ntf(nplease in put the num be scheduled:); scanf(%d, /*用len存储待调度的火车数量*/ for(i=0; i1 时，perm(R)由(r)perm(R),(r)perm(R),(r)perm(R成。 依此递归定义，可设计产生perm(R)的递归算法如下： 递归解法： #in clude int cont=1;/*全

19、局变量，用于记录所有可能的岀栈序列个数*/ void pr in t(i nt str,i nt n); /*求整数序列str从k到n的全排列*/ void perm(i nt str,i nt k,i nt n) int i,temp; if (k=n-1) print(str,n); else for (i=k;i n ;i+) temp=strk;strk=stri;stri=temp; perm(str,k+1,n); /* 递归调用 */ temp=stri;stri=strk;strk=temp; /*本函数判断整数序列str是否满足进岀栈规则，若满足则输岀*/ void pri

20、nt(i nt str,i nt n) int i,j,k,l,m,flag=1,b2; for(i=0;in;i+)/*对每个stri判断其后比它小的数是否为降序序列*/ m=0; for(j=i+1;jstrj) if (m=0) bm+=strj; else if (strjb0) flag=0; else b0=strj; if(flag)/*满足岀栈规则则输岀str中的序列*/ pri ntf( %2d:,c on t+); for(i=0;i n;i+) prin tf(%d,stri); pri ntf(n); int mai n() int str100, n,i; prin

21、tf(i nput a in t:); /* 输岀排列的元素个数 */ sca nf(%d, for(i=0;in;i+) /*初始化排列集合*/ stri=i+1; prin tf(i nput the result: n); perm(str,0, n); prin tf(n); return 0; 4时，输岀的结果如下图所示 当参与进出栈的元素个数为 一1Je h434224341141l AT2424334141422 22334113242243 ttlllll222223334 u p pl 2345678901234- n n 11 111 十OJ 该算法执行的时间复杂度为0(

22、n!)。随着n的增大，算法的执行效率非常的低。 非递归解法：() 对一组数穷尽所有排列，还可一种更直接的方法，将一个排列看作一个长整数，则所有排 列对应着一组整数，将这组整数按从小到大的顺序排成一个数列，从对应最小的整数开始，按 数列的递增顺序逐一列举每个排列对应的每一个整数，这能更有效地完成排列的穷举。从一个 排列找出对应数列的下一个排列可在当前排列的基础上作部分调整来实现。倘若当前排列为 1,2,4,6,5,3，并令其对应的长整数为124653。要寻找比长整数124653更大的排列，可从该排列 的最后一个数字顺序向前逐位考察，当发现排列中的某个数字比它前一个数字大时，如本例中 的6比它的前

23、一位数字4大，则说明还有可能对应更大整数的排列。但为顺序从小到大列举岀 所有的排列，不能立即调整得太大，如本例中将数字6与数字4交换得到的排列为126453就 不是排列124653的下一个排列。为得到排列124653的下一个排列，应从已考察过的那部分数 字中选岀比数字4大，但又是它们中最小的那一个数字，比如数字5,与数字 4交换。该数字 也是从后向前考察过程中第一个比4大的数字，5与4交换后，得到排列125643。在前面数字 1, 2，5固定的情况下，还应选择对应最小整数的那个排列，为此还需将后面那部分数字的排 列颠倒，如将数字 6，4，3的排列顺序颠倒，得到排列1,2,5,3,4,6，这才是

24、排列1，2，4，6， 5，3的下一个排列。按照以上想法可以编写非递归程序实现n个数的全排列，对满足进岀栈 规则的排列则计数并输出。 /*本程序输出1 2 . n个序列进栈出栈的序列*/ int pl( int n) int a100; int flag=1,flag1=0; FILE *rf ; int i,j,k,x,cou nt=O; rf = fope n( “，w); for (i=1;i=n ;i+) ai=i; while (flag) flag1=1; for (i=1;i=n ;i+) j=i+1; /*最大处理范围为99个数*/ #in elude /*用于存放进岀栈序列结果

25、 */ /*初始序列*/ /*还剩余未输岀的排列 */ /*判断本次排列是否符合进栈岀栈序列*/ while (jai) j+;/* 找 ai后第一个比ai小的元素 aj*/ k=j+1; while (k=n)/*如果aj后还有比 ai小且比aj大的元素，则此排列无效*/ if ( ak aj) flag1=0; k+; if (flag1) for (i=1;i1 * k=aj; /*交换两元素的值*/ aj=ai; ai=k; k=j+1; for ( i=k+1;i=k while (p if (p-in fo=x)return p else return NULL; B. node

26、*p=head;while (p return p; C. node *p=head-next;while (p return p; D. node *p=head;while (p-info!=x) p=p-next ;return p; (4) 线性表若采用链式存储结构时，要求内存中可用存储单元的地址(D )o A.必须是连续的B.部分地址必须是连续的 C. 一定是不连续的D.连续不连续都可以 (5) 在一个具有 n个结点的有序单链表中插入一个新结点并保持单链表仍然有序的时间 复杂度是(B )o A. 0(1)B. O(n)C. O(n)D. O(nlog) (6) 用不带头结点的单链表存

27、储队列时，其队头指针指向队头结点，其队尾指针指向队 尾结点，则在进行删除操作时( D )o A.仅修改队头指针B.仅修改队尾指针 C.队头、队尾指针都要修改D.队头，队尾指针都可能要修改 (7) 若从键盘输入 n个元素，则建立一个有序单向链表的时间复杂度为(B )o A. O(n)B.O(n)C. O(n)D. O(nxlog2) (8) 下面哪个术语与数据的存储结构无关(D )o A.顺序表B.链表C.散列表D.队列 (9) 在一个单链表中，若删除 p所指结点的后续结点，则执行(A )o A. p-next=p-next-next;B.p=p-next; p-next=p-next-next

28、; C. p-next=p-next;D.p =p-next-next; (10) 在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行(B ) A. s-next=p;p-next=s;B.s-next=p-next;p-next=s; C. s-next=p-next;p=s;D.p-next=s;s-next=p; 设计一个算法，求一个单链表中的结点个数。 【答】：单链表存储结构定义如下(相关文件：) #in clude 19 十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程 1*4* TMCT #in elude typedef struct node

29、int data; struct node *n ext; li nkno de; typedef li nknode *li nklist; /*尾插法创建带头结点的单链表*/ lin klist creatli nklist() lin klist head,r,s; int x; head=r=(li nklist)malloc(sizeof(li nkno de); printf(n请输入一组以0结束的整数序列：n); sca nf(%d, while (x) s=(li nklist)malloc(sizeof(li nkno de); s-data=x; r-n ext=s; r=

30、s; sca nf(%d， r- next=NULL; return head; /*输出带头结点的单链表*/ void pri nt(l in klist head) lin klist p; p=head-n ext; prin tf(List is:n); while(p) prin tf(%5d,p-data); p=p-n ext; prin tf(n); 基于上述结构定义，求单链表中的结点个数的算法程序如下： int cou nt(l in klist head) int c=0; lin klist p=head; while (p) # 高等学校精品资源共享课程 十二五普通高等

31、教育国家级本科规划教材 J i 高等学校精品资源共享课程 C+; p=p-n ext; return c; 设计一个算法，求一个带头结点单链表中的结点个数。 【答】：带头结点的单链表的存储结构定义同题，实现本题功能的算法程序如下() #i nclude int cou nt(l in klist head) int c=0; lin klist p=head-n ext; while (p) c+; p=p-n ext; return c; main()/*测试函数*/ li nklist head; head=creatl in klist(); prin t(head); prin tf(

32、nLen gth of head is:%d,cou nt(head); getch(); 当输入5个数据时，产生的输岀结果如下图所示: 请输人一组以虛吉車的整数序列, 10 20 30 40 50 0 List is: 1023 盹 4(4 o F lie ad is ：5 设计一个算法，在一个单链表中值为y的结点前面插入一个值为x的结点。即使值为 x的 新结点成为值为y的结点的前驱结点。 【答】： #i nclude void in sert(l in klist head,i nt y,i nt x) /*在值为y的结点前插入一个值为x的结点*/ lin klist pre,p,s; p

33、re=head; 23 十二五普通高等教育国家级本科规划教材 p=head-n ext; while (p p=p-n ext; if (p)/*找到了值为 y的结点*/ s=(li nklist)malloc(sizeof(li nkno de); s-data=x; s_n ext=p; pre_n ext=s; /*测试程序*/ /*创建单链表*/ /*输出单链表*/ void mai n() li nklist head; int y,x; head=creatli nklist(); prin t(head); printf(n 请输入 y与x的值:n); scanf(%d %d，

34、in sert(head,y,x); prin t(head); 程序的一种运行结果如下图所示: 请输入一组以0结東的整数序列： List is = 3196458 请输入y与x的值匚 lin klist p=head-n ext; switch (c) 十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程 TO- case a:/*判断带头结点的单链表head是否为升序*/ while (p else flag=0; break; case d:/*判断带头结点的单链表head是否为降序*/ while (p else flag=0; break; return flag; int

35、main() /* 测试程序 */ lin klist head; head=creatl in klist(); prin t(head); if (issorted(head,a) printf( 单链表 head 是升序排列的！n); else if (issorted(head,d) printf( 单链表 head 是降序排列的！n”); else printf(单链表 head 是无序的！n); 程序运行时的三种输岀结果如下图所示： 情输入一组如结東的整数序釧 10 20 30 40 50 0 10304050 犀链表也*是升序排列的！ 请输入一组以礎吉束的整数序列: 50 4迥

36、30 20 10 0 Liat is： 胴 40301(4 单链表血叔是降序排列的！ 请输入一组如纟掠的整数序列. 40 30 ?0 20 10 0 List is: 4902013 单链表he是无序的！ 设计一个算法，利用单链表原来的结点空间将一个单链表就地转置。 【答】： #in clude void verge(l in klist head) iMl十二五普通高等教育国家级本科规划教材 高等学校精品资源共享课程 lin klist p,q; p=head-n ext; head-next=NULL; while (p)/*每次从原表取一个结点插入到新表的最前面*/ q=p; p=p-n

37、 ext; q-n ext=head-n ext; head-n ext=q; int mai n() li nklist head; /*测试函数*/ head=creatl in klist(); prin t(head); verge(head); prin t(head); /*创建单链表*/ /*输出原单链表*/ /*就地倒置单链表*/ /*输出倒置后的单链表*/ 设计一个算法，将一个结点值自然数的单链表拆分为两个单链表，原表中保留值为偶数的 结点，而值为奇数的结点按它们在原表中的相对次序组成一个新的单链表。 【答】： #in clude lin klist sprit(l in k

38、list head) /*将带头结点的单链表head中的奇数值结点删除生成新的单链表并返回*/ linklist L,pre,p,r; L=r=(li nklist)malloc(sizeof(li nkno de); r- next=NULL; pre=head; p=head-n ext; while (p) if (p-data%2=1) /*删除奇数值结点*/ pre-n ext=p-n ext; r-n ext=p; else r=p; p=pre _n ext; /*保留偶数值结点*/ pre=p; p=p-n ext; # 十二五普通高等教育国家级本科规划教材高等学校精品资源共享

39、课程 29 /*置链表结束标记*/ r-n ext=NULL; return L; int mai n() lin klist head,L; head=creatli nklist(); prin t(head); L=sprit(head); /*测试函数*/ /*创建单链表*/ /*输出原单链表*/ /*分裂单链表head*/ printf（n原单链表为:n）; print（head）;/*输岀倒置后的单链表 */ prin tf（n分裂所得奇数单链表为:n）; prin t(L); 本程序的一组测试情况如下图所示。 请辑入一也以阵朿的整救序.纵 is = Liat - h諛肝得奇裁单狂

40、贡为： Litt it= 135? 设计一个算法，对一个有序的单链表，删除所有值大于x而不大于y的结点 【答】： #in clude void deletedata(li nklist head,datatype x,datatype y) /*删除带头结点单链表中所有结点值大于 lin klist pre=head,p,q; p=head-next; /* 初始化 */ x而不大于y的结点*/ while (p /*找第1 处大于x的结点位置*/ while (p /*找第1 处小于y的位置*/ q=pre-n ext; pre_n ext=p; /*删除大于x而小于y的结点*/ pre=q

41、_n ext; while (pre!=p)/*释放被删除结点所占用的空间*/ free(q); q=pre; pre=pre _n ext; void mai n() lin klist head,L; /*测试函数*/ datatype x,y; head=creatl in klist(); prin t(head); /*创建单链表*/ /*输出原单链表*/ prin tf(n请输入要删除的数据区间:n); sea nf(%d%d, deletedata(head,x,y); prin t(head); /*输出删除后的单链表*/ 设计一个算法，在双链表中值为y的结点前面插入一个值为x

42、的新结点。即使值为x的新 结点成为值为 y的结点的前驱结点。 【答】： 首先定义双链表的数据结构，相关文件 typedef int datatype; typedef struct dli nk_no de datatype data; struct dli nk_node *lli nk,*rl ink; dno de; typedef dno de* dli nklist; /*尾插法创建带头结点的双链表*/ dli nklist ereatdli nklist(void) ，内容如下： /*预定义的数据类型*/ /*双链表结点定义*/ /*双链表结点指针类型定义*/ dli nklist

43、 head,r,s; datatype x; head=r=(dlinklist) malloe(sizeof(dnode);/* 建立双链表的头结点 */ head-lli nk=head-rli nk=NULL; printf(n请输入双链表的内容：(整数序列，以0结束)n); sea nf(%d, while (x)/*输入结点值信息，以0结束*/ s=(dli nklist ) malloe(sizeof(d no de); s-data=x; s-rl in k=r-rli nk; /*将新结点s插入到双链表链尾*/ IM* s-lli nk=r; r-rlin k=s; r=s;

44、sca nf(%d， return head; /*输出双链表的内容*/ void pri nt(dli nklist head) dlinklist p; p=head-rli nk; prin tf(n双链表的内容是： n); while (p) prin tf(%5d,p-data); p=p-rli nk; 本题的求解程序如下： #in clude #i nclude void in sertxaty(dli nklist head,datatype y,datatype x) dli nklist s,p; */ !n); /*首先在双链表中找 y所在的结点，然后在 y前面插入新结点

45、 p=head-rli nk; while (p if (!p) printf(n双链表中不存在值为y的结点，无法插入新结点 else /*插入值为x的新结点*/ s=(dli nklist)malloc(sizeof(d no de); s-data=x; s-rli nk=p; s-lli nk=p-lli nk; p-lli nk-rli nk=s; p-lli nk=s; void main()/* 测试函数 */ dli nklist head; datatype x,y; 十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程 -IM* 用 head=creatdli nkl

46、ist(); prin t(head); prin tf(n请输入要输入的位置结点值y:n); sca nf(%d, prin tf(n请输入要输入的结点值x:n); sca nf(%d, insertxaty(head,y,x);/*在值为 y的结点前插入值为x的新结点*/ print(head);/*输岀新的双链表*/ getch(); 本程序的一组测试情况如下图所示。 情端入双链表的内容；(整数序列，如结束 飓链奇的內容是| L pri ntf(%5d,head-rli nk-data); void main()/* 测试函数 */ dli nklist head; head=creat

47、dli nklist(); prin t(head); prin tf(n从右向左打印的双链表的内容是:n); # .”十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程 vpri nt(head); getch(); 第输人双犍表的内容：整数序列结耒 1U ZV 孑臼50 3 如链舂旳内容是. 1630 4B C(t 城右问左打印的艰谴决的內呑是： 5 迥 42019- 本程序的一组测试情况如下图所示。 设计一个算法，将一个双链表改建成一个循环双链表。 【答】： #in elude #i nclude /*将一个双链表改成循环双链表*/ void dli nktocdli nk(d

48、li nklist head) dlinklist r; r=head; while (r-rlink)/* 寻找尾结点 */ r=r-rli nk; head-lli nk=r; r-rlin k=head; void pri ntcdli nk(dli nklist head) /*打印双链表*/ dli nklist p; p=head-rli nk; while (p!=head) pri ntf(%5d,p-data); p=p-rli nk; int main()/* 测试函数 */ dli nklist head; head=creatdli nklist(); dli nkto

49、cdli nk(head); prin tf(n循环双链表的内容是：n); prin tcdli nk(head); 31 .”】十二五普通高等教育国家级本科规划教材 高等学校精品资源共享课程 f 宁 第4章 字符串、数组和特殊矩阵 稀疏矩阵常用的压缩存储方法有（三元组顺序存储）和（十字链表）两种。 设有一个1010的对称矩阵 A采用压缩方式进行存储，存储时以按行优先的顺序存 储其下三角阵，假设其起始元素a的地址为1,每个数据元素占2个字节，则 a的地址为 （53 ）。 若串S= “ software，其子串的数目为（36 ）。 常对数组进行的两种基本操作为（访问数据元素）和（修改数组元素）。

50、 要计算一个数组所占空间的大小，必须已知（数组各维数）和（每个元素占用的空 间）。 对于半带宽为 b的带状矩阵，它的特点是：对于矩阵元素a，若它满足（卜j|b）， 则 a=0。 字符串是一种特殊的线性表，其特殊性体现在（该线性表的元素类型为字符）。 试编写一个函数，实现在顺序存储方式下字符串的strcompare （ S, S）运算。 【答】： #in elude #in elude #defi ne MAXSIZE 100 typedef struct char strMAXSIZE; int len gth; seqstri ng; /*函数strcompare（）的功能是：当s1s2时返

51、回1，当s1=s2时返回 0，当s1s2时返回-1*/ int strcompare（seqstring s1,seqstring s2） int i,m=0,le n; len= :; for（i=0;ii） m=1;break; else ifii） m=-1;break; return m; int mai n（） seqstri ng s1,s2; int i,m; pri ntf（i nput char to s1: n）; 33 十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程 gets; a=strlen; b pri ntf(in put char tOjD get

52、s; CE：件诒fc据结梅写作 ab baa t !/；_ T虽C拿打卜I 咅-b A matvix= =strle n; m=strcompare(s1, if(m=1) prin tf(s1： else if(m=-1) pr int else if(m=0) prin 试编写一个函数，实现在顺 【参考程序1】： /*本程序用来在顺序存储 能*/ a #in clude #in clude !nx Q a a 9 与储方 式下 字符 串的 1 r e( Q A 速匹配 已模式 7实现 I在字 符串 Q S中 Q b a a Q a r S， 用 运算。 替换所有 #in clude ype

53、def str 叫 a cha L strmaxs a fze- # defi ne maxsize 100 seqstr ing; T1岀现的可 */ b a ，开始下一步操作 5 6 7 2 3 ow_oprow;backtop.n 2 1 8 板軽梵 3 3 4 U b -ee1 if(top=0) return 0;/* 如果栈 oprow_backtop.ro -|oplin e_backtop.lin lop row/oprow/0; llefto right8-oprow+oplin while(oprow_8);/* 当 b a a oprow+; mai n() 说明查找结束

54、 岀 元票. a 3 M个棋子拿起 产ee 取112 */ 【N】十二五普通高等教育国家级本科规划教材高等学校精品资源共享课程 第6章树 树最适合用来表示具有（有序）性和（层次）性的数据。 在选择存储结构时，既要考虑数据值本身的存储，还需要考虑（数据间关系 ） 的存储。 对于一棵具有 n个结点的树，该树中所有结点的度数之和为（n-1 ）。 已知一棵树如图所示，试回答以下问题： （1）树中哪个结点为根结点哪些结点为叶子结点 【答】：A是根结点；E, G，H，I，C，J，K，L为叶结点。 （2）结点B的双亲为哪个结点其子女为哪些结点 【答】：B的双亲结点是 A,其子女结点为 E和F。 （3） 哪些

55、结点为结点I的祖先哪些结点为结点B的子孙 【答】：F, B，A是结点I的祖先结点；E，F，G，H, I是B的子孙结点。 （4） 哪些结点为结点D的兄弟哪些结点为结点K的兄弟 【答】：B，C，L是结点D的兄弟结点，J是结点K的兄弟结点。 （5）结点J的层次为多少树的高度为多少 【答】：结点 J的层次为3,树的高度为 4。 （6）结点A、C的度分别为多少树的度为多少 【答】：结点 A的度为4，结点C的度是0，树的度是 4。 （7）以结点B为根的子树的高度为多少 【答】：以结点 B为根的子树的高度是3。 （8）试给出该树的括号表示及层号表示形式。 【答】：该树的括号表示为：A（ B（ E, F（ G

56、, H , I）, C, D（ J, K）, L）,该树的层号 表示为：10A, 20B, 30E, 30F, 40G, 40H, 40I, 20C, 20D, 25J, 25K, 20L 试写岀图 所示树的前序遍历、后序遍历和层次遍历的结果。 【答】：前序遍历：ABEFGHICDJKL 后序遍历：EGHIFBCJKDLA 层次遍历：ABCDLEFJKGHI 试给出图 所示树的双亲表示法和数组方式孩子表示法的表示。 61 i： Mj -十二五普通高等教育国家级本科规划教材 高等学校精品资源共享课程 1*4* 左笊 【答】： 双亲表示法： data pare nt 0 A -1 1 B 0 2

57、C 0 3 D 0 4 E 1 5 F 1 6 G 5 7 H 5 8 I 5 9 J 3 10 K 3 11 L 0 数组方式的孩子表示法: data Child0 Child1 Child2 Child3 A 1 2 3 11 B 4 5 -1 -1 C -1 -1 -1 -1 D 9 10 -1 -1 E -1 -1 -1 -1 F 6 7 8 -1 G -1 -1 -1 -1 H -1 -1 -1 -1 I -1 -1 -1 -1 J -1 -1 -1 -1 K -1 -1 -1 -1 L -1 -1 -1 -1 0 1 2 3 4 5 6 7 8 9 10 11 已知一棵度为m的树中

58、有 n个度为1的结点，n个度为2的结点，；n个度为 m的结点，问该树中有多少个叶子结点 【答】： 树中结点总数n=n+n+n+n 树中结点的度数之和为n-1，且有：n-1= n+2 n+3 n+mn 所以叶子结点个数为：n=1+ n+2 n+(m-1) n 第7章二叉树 选择题。 （1）前序遍历和中序遍历结果相同的二叉树为（ F）;前序遍历和后序遍历结果相同的 二叉树为（B） A. 般二叉树 C.根结点无左孩子的二叉树 E.所有结点只有左子树的二叉树 （2）以下有关二叉树的说法正确的是（ B.只有根结点的二叉树 D.根结点无右孩子的二叉树 F.所有结点只有右子树的二叉树。 B ）。 A. 二叉

59、树的度为 2 C.二叉树中至少有一个结点的度为 B. 一棵二叉树的度可以小于2 2D. 二叉树中任一个结点的度均为2 （3）棵完全二叉树上有1001个结点，其中叶子结点的个数为（ D ） A. 250 B. 500 C. 254 D. 501 （4） 一棵完全二 二叉树有999个结点， 它的深度为（B）。 A. 9 B. 10 C. 11 D. 12 （5） 棵具有 5层的满二叉树所包含的结点个数为（B ）。 A. 15 B. 31 C. 63 D. 32 用一维数组存放完全二叉树：ABCDEFGHI则后序遍历该二叉树的结点序列为 （HIDEBFGCA ）。 有n个结点的二叉树，已知叶结点个数

60、为n,则该树中度为 1的结点的个数为 （n-2n+1 ）;若此树是深度为k的完全二叉树，则n的最小值为（2 ）。 设F是由T1、T2和T3三棵树组成的森林，与F对应的二叉树为 B。已知 T1、T2 和T3的结点数分别是n1、n2和n3,则二叉树 B的左子树中有（n1-1 ）个结点，二叉树 B的右子树中有（n2+n3 ）结点。 高度为k的二叉树的最大结点数为（2-1），最小结点数为（k ）。 对于一棵具有n个结点的二叉树，该二叉树中所有结点的度数之和为（n-1）。 图一棵二叉树 已知一棵二叉树如图所示，试求： （1）该二叉树前序、中序和后序遍历的结果； 【答】：前序： abdgecfh ；中序：