数据结构课后习题第一二三四五六七章

第一章 绪论

1.1 简述下列概念：数据、数据元素、数据类型、数据结构、逻辑结构、存储结构、线性结构、非线性结构。 ● 数据：指能够被计算机识别、存储和加工处理的信息载体。

● 数据元素：就是数据的基本单位，在某些情况下，数据元素也称为元素、结点、顶点、记录。数据元素有时可以由若干数据项组成。

● 数据类型：是一个值的集合以及在这些值上定义的一组操作的总称。通常数据类型可以看作是程序设计语言中已实现的数据结构。

● 数据结构：指的是数据之间的相互关系，即数据的组织形式。一般包括三个方面的内容:数据的逻辑结构、存储结构和数据的运算。

● 逻辑结构：指数据元素之间的逻辑关系。

● 存储结构：数据元素及其关系在计算机存储器内的表示，称为数据的存储结构.

● 线性结构：数据逻辑结构中的一类。它的特征是若结构为非空集，则该结构有且只有一个开始结点和一个终端结点，并且所有结点都有且只有一个直接前趋和一个直接后继。线性表就是一个典型的线性结构。栈、队列、串等都是线性结构。

● 非线性结构：数据逻辑结构中的另一大类，它的逻辑特征是一个结点可能有多个直接前趋和直接后继。数组、广义表、树和图等数据结构都是非线性结构。

1.2 试举一个数据结构的例子、叙述其逻辑结构、存储结构、运算三个方面的内容。 答：

例如有一张学生体检情况登记表，记录了一个班的学生的身高、体重等各项体检信息。这张登记表中，每个学生的各项体检信息排在一行上。这个表就是一个数据结构。每个记录(有姓名，学号，身高和体重等字段)就是一个结点，对于整个表来说，只有一个开始结点(它的前面无记录)和一个终端结点(它的后面无记录)，其他的结点则各有一个也只有一个直接前趋和直接后继(它的前面和后面均有且只有一个记录)。这几个关系就确定了这个表的逻辑结构是线性结构。

这个表中的数据如何存储到计算机里，并且如何表示数据元素之间的关系呢? 即用一片连续的内存单元来存放这些记录(如用数组表示)还是随机存放各结点数据再用指针进行链接呢? 这就是存储结构的问题。

在这个表的某种存储结构基础上，可实现对这张表中的记录进行查询，修改，删除等操作。对这个表可以进行哪些操作以及如何实现这些操作就是数据的运算问题了。

1.3 常用的存储表示方法有哪几种? 答：

常用的存储表示方法有四种: ● 顺序存储方法：它是把逻辑上相邻的结点存储在物理位置相邻的存储单元里，结点间的逻辑关系由存储单元的邻接关系来体现。由此得到的存储表示称为顺序存储结构，通常借助程序语言的数组描述。

● 链接存储方法：它不要求逻辑上相邻的结点在物理位置上亦相邻，结点间的逻辑关系是由附加的指针字段表示。由此得到的存储表示称为链式存储结构,通常借助于程序语言的指针类型描述。

● 索引存储方法：除建立存储结点信息外，还建立附加的索引表来标识结点的地址。组成索引表的索引项由结点的关

1

键字和地址组成。若每个结点在索引表中都有一个索引项，则该索引表称之为稠密索引（Dense Index）。若一组结点在索引表中只对应一个索引项，则该索引表称为稀疏索引。

● 散列存储方法：就是根据结点的关键字直接计算出该结点的存储地址

1.4 设三个函数f,g,h分别为 f(n)=100n3+n2+1000 , g(n)=25n3+5000n2 , h(n)=n1.5+5000nlgn 请判断下列关系是否成立： (1) f(n)=O(g(n)) (2) g(n)=O(f(n)) (3) h(n)=O(n1.5) (4) h(n)=O(nlgn) 分析：

数学符号\的严格的数学定义：

若T（n）和f（n）是定义在正整数集合上的两个函数，则T（n）=O（f（n））表示存在正的常数C和n0，使得当n≥n0时都满足0≤T（n）≤C?f（n）。

通俗地说，就是当n→∞时，f(n)的函数值增长速度与T（n)的增长速度同阶。一般，一个函数的增长速度与该函数的最高次阶同阶。

即：

O(f(n))=n3 O(g(n))=n3 O(h(n))=n1.5 所以答案为： 答：

●（1）成立。 ●（2）成立。 ●（3）成立。 ●（4）不成立。

1.5 设有两个算法在同一机器上运行，其执行时间分别为100n2和2n,要使前者快于后者，n至少要多大? 分析：

要使前者快于后者，即前者的时间消耗低于后者，即： 100n2<2n 求解上式，可得 答：

n=15

1.6 设n为正整数，利用大\记号，将下列程序段的执行时间表示为n的函数。 (1) i=1; k=0; while(i

{ k=k+10*i;i++; } 分析： i=1; //1 k=0; //1 while(i

2

{ k=k+10*i; //n-1 i++; //n-1 }

由以上列出的各语句的频度，可得该程序段的时间消耗： T(n)=1+1+n+(n-1)+(n-1)=3n 可表示为T(n)=O(n)

(2) i=0; k=0; do{

k=k+10*i; i++; }

while(i

k=k+10*i; //n i++; //n }

while(i

由以上列出的各语句的频度，可得该程序段的时间消耗： T(n)=1+1+n+n+n+n=4n+2 可表示为T(n)=O(n)

(3) i=1; j=0;

while(i+j<=n) {

if (i>j) j++; else i++; } 分析：

通过分析以上程序段，可将i+j看成一个控制循环次数的变量，且每执行一次循环，i+j的值加1。该程序段的主要时间消耗是while循环，而while循环共做了n次，所以该程序段的执行时间为： T(n)=O(n)

(4)x=n; // n>1

while (x>=(y+1)*(y+1)) y++; 分析：

由x=n且x的值在程序中不变，又while的循环条件(x>=(y+1)*(y+1))可知：当(y+1)*(y+1)刚超过n的值时退出循环。

由(y+1)*(y+1)

3

(5) x=91; y=100; while(y>0)

if(x>100)

{x=x-10;y--;} else x++;

分析：

x=91; //1 y=100; //1

while(y>0) //1101 if(x>100) //1100 { x=x-10; //100 y--; //100 } else

x++; //1000

以上程序段右侧列出了执行次数。该程序段的执行时间为： T(n)=O(1)

1.7 算法的时间复杂度仅与问题的规模相关吗? 答：

算法的时间复杂度不仅与问题的规模相关，还与输入实例中的初始状态有关。但在最坏的情况下，其时间复杂度就是只与求解问题的规模相关的。我们在讨论时间复杂度时，一般就是以最坏情况下的时间复杂度为准的。

1.8 按增长率由小至大的顺序排列下列各函数：

2100, (3/2)n，(2/3)n， nn ,n0.5 , n! ，2n ，lgn ,nlgn, n(3/2) 答：

常见的时间复杂度按数量级递增排列,依次为:常数阶0(1)、对数阶0(log2n)、线性阶0(n)、线性对数阶0(nlog2n)、平方阶0(n2)、立方阶0(n3)、k次方阶0(nk)、指数阶0(2n)。 先将题中的函数分成如下几类： 常数阶：2100 对数阶：lgn

K次方阶：n0.5、n(3/2)

指数阶 (按指数由小到大排)：nlgn、(3/2)n、2n、 n!、 nn

注意：(2/3)^n由于底数小于1，所以是一个递减函数，其数量级应小于常数阶。 根据以上分析按增长率由小至大的顺序可排列如下：

(2/3)n < 2100 < lgn < n0.5 < n(3/2) < nlgn < (3/2)n < 2n < n! < nn

1.9 有时为了比较两个同数量级算法的优劣，须突出主项的常数因子，而将低次项用大\记号表示。例如，设T1(n)=1.39nlgn+100n+256=1.39nlgn+O(n), T2(n)=2.0nlgn-2n=2.0lgn+O(n), 这两个式子表示，当n足够大时T1(n)优于T2(n)，因为前者的常数因子小于后者。请用此方法表示下列函数，并指出当n足够大时，哪一个较优，哪一个较劣? 函数 大\表示 优劣 (1) T1(n)=5n2-3n+60lgn 5n2+O(n) 较差

4

(2) T2(n)=3n2+1000n+3lgn 3n2+O(n) 其次 (3) T3(n)=8n2+3lgn 8n2+O(lgn) 最差 (4) T4(n)=1.5n2+6000nlgn 1.5n2+O(nlgn) 最优

第二章 线性表

2.6 下述算法的功能是什么?

LinkList Demo(LinkList L){ // L 是无头结点单链表 ListNode *Q,*P; if(L&&L->next){

Q=L;L=L->next;P=L;

while (P->next) P=P->next; P->next=Q; Q->next=NULL; }

return L; }// Demo

答：

该算法的功能是：将开始结点摘下链接到终端结点之后成为新的终端结点，而原来的第二个结点成为新的开始结点，返回新链表的头指针。

关闭

2.7 设线性表的n个结点定义为(a0,a1,...an-1)，重写顺序表上实现的插入和删除算法：InsertList 和DeleteList.

解：算法如下:

#define ListSize 100 // 假定表空间大小为100

typedef int DataType;//假定DataType的类型为int型 typedef struct{

DataType data[ListSize];// 向量data用于存放表结点 int length; // 当前的表长度 } Seqlist;

//以上为定义表结构

void InsertList ( Seqlist *L, Datatype x, int i) {

//将新结点x插入L所指的顺序表的第i个结点ai的位置上，即插入的合法位置为：0<=i<=L->length int j;

if ( i < 0 || i > L -> length )

Error(\非法位置，退出，该函数定义见教材P7. if ( L->length>=ListSize ) Error(“overflow\

for ( j=L->length-1 ; j >= i ; j --)

5

L->data[ j+1]=L->data [ j ]; L->data[ i ]=x ; L->length++ ; }

void DeleteList ( Seqlist *L, int i )

{// 从L所指的顺序表中删除第i个结点ai,合法的删除位置为0<=i<=L->length-1 int j;

if ( i< 0 || i >= L-> length) Error( \

for ( j = i ; j < L-> length ; j++ )

L->data [ j ]=L->data [ j+1]; //结点前移 L-> length-- ; //表长减小 }

关闭

2.8 试分别用顺序表和单链表作为存储结构，实现将线性表(a0,a1,...an-1)就地逆置的操作，所谓\就地\指辅助空间应为O(1)。

答：

1. 顺序表：

要将该表逆置，可以将表中的开始结点与终端结点互换，第二个结点与倒数第二个结点互换，如此反复，就可将整个表逆置了。算法如下：

// 顺序表结构定义同上题

void ReverseList( Seqlist *L) {

DataType temp ; //设置临时空间用于存放data int i;

for (i=0;i<=L->length/2;i++)//L->length/2为整除运算 { temp = L->data[i]; //交换数据

L -> data[ i ] = L -> data[ L -> length-1-i]; L -> data[ L -> length - 1 - i ] = temp; } }

2. 链表： 分析：

可以用交换数据的方式来达到逆置的目的。但是由于是单链表，数据的存取不是随机的，因此算法效率太低。可以利用指针改指来达到表逆置的目的。具体情况入下：

(1)当链表为空表或只有一个结点时，该链表的逆置链表与原表相同。

(2)当链表含2个以上结点时，可将该链表处理成只含第一结点的带头结点链表和一个无头结点的包含该链表剩余

6

结点的链表。然后，将该无头结点链表中的所有结点顺着链表指针，由前往后将每个结点依次从无头结点链表中摘下，作为第一个结点插入到带头结点链表中。这样就可以得到逆置的链表。算法是这样的： 结点结构定义如下：

typedef char DataType; //假设结点的数据域类型的字符 typedef struct node{ //结点类型定义 DataType data; //结点的数据域 struct node *next;//结点的指针域 }ListNode;

typedef ListNode *LinkList; ListNode *p; LinkList head;

LinkList ReverseList( LinkList head )

{// 将head 所指的单链表(带头结点)逆置

ListNode *p ,*q ;//设置两个临时指针变量if( head->next && head->next->next) { //当链表不是空表或单结点时 p=head->next; q=p->next;

p -> next=NULL; //将开始结点变成终端结点

while (q)

{ //每次循环将后一个结点变成开始结点 p=q;

q=q->next ;

p->next = head-> next ; head->next = p; }

return head; }

return head; //如是空表或单结点表，直接返回head }

关闭

2.9 设顺序表L是一个递增有序表，试写一算法，将x插入L中，并使L仍是一个有序表。

答：

因已知顺序表L是递增有序表，所以只要从顺序表终端结点（设为i位置元素）开始向前寻找到第一个小于或等于x的元素位置i后插入该位置即可。

在寻找过程中，由于大于x的元素都应放在x之后，所以可边寻找，边后移元素，当找到第一个小于或等于x的元素位置i时，该位置也空出来了。 算法如下：

//顺序表存储结构如题2.7

void InsertIncreaseList( Seqlist *L , Datatype x )

7

{

int i;

if ( L->length>=ListSize) Error(“overflow\

for ( i=L -> length ; i>0 && L->data[ i-1 ] > x ; i--) L->data[ i ]=L->data[ i ] ; // 比较并移动元素 L->data[ i ] =x; L -> length++; }

关闭

2.10 设顺序表L是一个递减有序表，试写一算法，将x插入其后仍保持L的有序性。

答：

与上题相类似，只要从终端结点开始往前找到第一个比x大(或相等)的结点数据，在这个位置插入就可以了。（边寻找，边移动）算法如下：

void InsertDecreaseList( Seqlist *L, Datatype x ) {

int i;

if ( L->length>=ListSize) Error(“overflow\

for ( i=L -> length ; i>0 && L->data[ i-1 ] < x ; i--) L->data[ i ]=L->data[ i ] ; // 比较并移动元素 L->data[ i ] =x; L -> length++; }

关闭

2.11 写一算法在单链表上实现线性表的ListLength(L)运算。

解：

由于在单链表中只给出一个头指针，所以只能用遍历的方法来数单链表中的结点个数了。算法如下：

int ListLength ( LinkList L ) {

int len=0 ; ListNode *p;

p=L; //设该表有头结点 while ( p->next ) {

p=p->next;

8

len++; }

return len; }

关闭

2.12 已知L1和L2分别指向两个单链表的头结点，且已知其长度分别为m和n。试写一算法将这两个链表连接在一起，请分析你的算法的时间复杂度。

解：

分析：

由于要进行的是两单链表的连接，所以应找到放在前面的那张表的表尾结点，再将后表的开始结点链接到前表的终端结点后即可。该算法的主要时间消耗是用在寻找第一张表的终端尾结点上。这两张单链表的连接顺序无要求，并且已知两表的表长，则为了提高算法效率，可选表长小的单链表在前的方式连接。 具体算法如下：

LinkList Link( LinkList L1 , LinkList L2，int m,int n ) {//将两个单链表连接在一起 ListNode *p , *q, *s ;

//s指向短表的头结点,q指向长表的开始结点，回收长表头结点空间 if (m<=n)

{s=L1;q=L2->next;free(L2);} else {s=L2;q=L1->next;free(L1);} p=s;

while ( p->next ) p=p->next; //查找短表终端结点 p->next = q; //将长表的开始结点链接在短表终端结点后 return s; }

本算法的主要操作时间花费在查找短表的终端结点上，所以本算的法时间复杂度为： O(min(m,n))

关闭

2.13 设 A和B是两个单链表，其表中元素递增有序。试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)，请分析算法的时间复杂度。

解：

根据已知条件，A和B是两个递增有序表，所以可以先取A表的表头建立空的C表。然后同时扫描A表和B表，将两表中最大的结点从对应表中摘下，并作为开始结点插入C表中。如此反复，直到A表或B表为空。最后将不为空的A表或B表中的结点依次摘下并作为开始结点插入C表中。这时，得到的C表就是由A表和B表归并成的一个按元素值递减有序的单链表C。并且辅助空间为O(1)。 算法如下：

9

LinkList MergeSort ( LinkList A , LinkList B )

{// 归并两个带头结点的递增有序表为一个带头结点递减有序表 ListNode *pa , *pb , *q , *C ;

pa=A->next;//pa指向A表开始结点

C=A;C->next=NULL;//取A表的表头建立空的C表 pb=B->next;//pb指向B表开始结点 free(B);//回收B表的头结点空间 while ( pa && pb) {

if ( pb->data <= pa->data )

{ // 当B中的元素小于等于A中当前元素时，将pa表的开始结点摘下 q=pa;pa=pa->next; } else

{// 当B中的元素大于A中当前元素时，将pb表的开始结点摘下 q=pb;pb=pb->next;}

q->next=C->next;C->next=q;//将摘下的结点q作为开始结点插入C表 }

//若pa表非空，则处理pa表 while(pa){

q=pa;pa=pa->next;

q->next=C->next;C->next=q;} //若pb表非空，则处理pb表 while(pb){

q=pb;pa=pb->next;

q->next=C->next;C->next=q;} return(C); }

该算法的时间复杂度分析如下：

算法中有三个while 循环，其中第二个和第三个循环只执行一个。每个循环做的工作都是对链表中结点扫描处理。整个算法完成后，A表和B表中的每个结点都被处理了一遍。所以若A表和B表的表长分别是m和n，则该算法的时间复杂度O(m+n)

关闭

2.14 已知单链表L是一个递增有序表，试写一高效算法，删除表中值大于min 且小于max的结点(若表中有这样的结点)，同时释放被删结点的空间，这里min 和 max是两个给定的参数。请分析你的算法的时间复杂度。

解：

要解这样的问题，我们首先想到的是拿链表中的元素一个个地与max和min比较，然后删除这个结点。由于为已知其是有序链表，则介于min 和max之间的结点必为连续的一段元素序列。所以我们只要先找到所有大于min结点中的最小结点的直接前趋结点*p后，依次删除小于max的结点，直到第一个大于等于max结点*q位置，然后将*p结点

10

的直接后继指针指向*q结点。 算法如下：

void DeleteList ( LinkList L, DataType min , DataType max ) {

ListNode *p , *q , *s; p=L;

while( p->next && p->next->data <=min ) //找比min大的前一个元素位置 p=p->next;

q=p->next;//p指向第一个不大于min结点的直接前趋，q指向第一个大于min的结点 while(q &&q->datanext;

free(s);//删除结点，释放空间 }

p->next=q;//将*p结点的直接后继指针指向*q结点 }

关闭

2.15 写一算法将单链表中值重复的结点删除，使所得的结果表中各结点值均不相同解：

本题可以这样考虑，先取开始结点中的值，将它与其后的所有结点值一一比较，发现相同的就删除掉，然后再取第二结点的值，重复上述过程直到最后一个结点。

具体算法：

void DeleteList ( LinkList L ) {

ListNode *p , *q , *s; p=L-next;

while( p->next&&p->next->next) {

q=p;//由于要做删除操作，所以q指针指向要删除元素的直接前趋 while (q->next)

if (p->data==q->next->data)

{s=q->next;q->next=s->next;free(s);//删除与*p的值相同的结点 }

else q=q->next; p=p->next; } }

关闭

2.16 假设在长度大于1的单循环链表中，既无头结点也无头指针。s为指向链表中某个结点的指针，试编写算法删除结点*s的直接前趋结点。

11

解：

已知指向这个结点的指针是*s，那么要删除这个结点的直接前趋结点，就只要找到一个结点，它的指针域是指向*s的直接前趋，然后用后删结点法，将结点*s的直接前趋结点删除即可。

算法如下：

void DeleteNode( ListNode *s)

{//删除单循环链表中指定结点的直接前趋结点 ListNode *p, *q; p=s;

while( p->next->next!=s) p=p->next; //删除结点 q=p->next;

p->next=q->next; free(p); //释放空间 }

注意：

若单循环链表的长度等于1，则只要把表删空即可。

关闭

2.17 已知由单链表表示的线性表中，含有三类字符的数据元素(如：字母字符、数字字符和其它字符)，试编写算法构造三个以循环链表表示的线性表，使每个表中只含同一类的字符，且利用原表中的结点空间作为这三个表的结点空间，头结点可另辟空间。

解：

要解决这样的问题，只要新建三个头结点，然后在原来的单链表中依次查询，找到一类字符结点时，就摘下此结点链接到相应头结点指明的新链表中就是了。

算法如下：

//设已建立三个带头结点的空循环链表A,B,C且A、B、C分别是尾指针. void DivideList( LinkList L, LinkList A, LinkList B, LinkList C) {

ListNode *p=L->next, *q; while ( p ) {

if ( p->data>='a' &&p->data<='z'|| p->data>='A' &&p->data<='Z') {

q=p->next;

p=p->next;//指向下一结点

q->next=A->next;//将字母结点链到A表中 A->next=q;A=q;

12

}

else if( p->data>='0' && p->data<='9') { // 分出数字结点 q=p->next;

p=p->next;//指向下一结点

q->next=B->next;//将数字结点链到B表中 B->next=q;B=q; }

else { //分出其他字符结点 q=p->next;

p=p->next;//指向下一结点

q->next=C->next;//将其他结点链到C表中 C->next=q;C=q; } } }//结束

关闭

2.18 设有一个双链表，每个结点中除有prior、data和next三个域外，还有一个访问频度域freq，在链表被起用之前，其值均初始化为零。每当在链表进行一次LocateNode(L,x)运算时，令元素值为x的结点中freq域的值加1，并调整表中结点的次序，使其按访问频度的递减序排列，以便使频繁访问的结点总是靠近表头。试写一符合上述要求的LocateNode运算的算法。

解：

LocateNode运算的基本思想就是在双向链表中查找值为x的结点，具体方法与单链表中查找一样。找到结点*p后给freq域的值加1。由于原来比*p结点查找频度高的结点都排它前面，所以，接下去要顺着前趋指针找到第一个频度小于或等于*p结点频度的结点*q后，将*p结点从原来的位置删除，并插入到*q后就可以了。 算法如下：

//双向链表的存储结构

typedef struct dlistnode{ DataType data;

struct dlistnode *prior,*next; int freq; }DListNode;

typedef DListNode *DLinkList;

void LocateNode( LinkList L, DataType x) {

ListNode *p, *q;

p=L->next; //带有头结点 while( p&&p->data!=x ) p=p->next;

13

if (!p) ERROR(\双链表中无值为x的结点 else { p->freq++;//freq加1

q=p->prior;//以q为扫描指针寻找第一个频度大于或等于*p频度的结点 while(q!=L&&q->freqfreq) q=q->prior;

if (q->next!=p)//若* q结点和*p结点不为直接前趋直接后继关系， //则将*p结点链到* q结点后 {p->prior->next=p->next;//将*p从原来位置摘下 p->next->prior=p->prior;

q->next->prior=p;//将*p插入*q之后。 p->next=q->next; q->next=p; p->prior=q; } } } 关闭

第三章 栈和队列

3.1 设将整数1，2，3，4依次进栈，但只要出栈时栈非空，则可将出栈操作按任何次序夹入其中，请回答下述问题： (1)若入、出栈次序为Push(1), Pop(),Push(2),Push(3), Pop(), Pop( ),Push(4), Pop( ),则出栈的数字序列为何(这里Push(i)表示i进栈，Pop( )表示出栈)?

(2)能否得到出栈序列1423和1432?并说明为什么不能得到或者如何得到。

(3)请分析 1，2 ，3 ，4 的24种排列中，哪些序列是可以通过相应的入出栈操作得到的。

答：

(1)出栈序列为：1324

(2)不能得到1423序列。因为要得到14的出栈序列，则应做Push(1),Pop(),Push(2),Push (3),Push(4),Pop()。这样，3在栈顶，2在栈底，所以不能得到23的出栈序列。能得到1432的出栈序列。具体操作为：Push(1), Pop(),Push(2),Push(3),Push(4),Pop(),Pop(),Pop()。

(3)在1，2 ，3 ，4 的24种排列中，可通过相应入出栈操作得到的序列是： 1234,1243,1324,1342,1432,2134,2143,2314,2341,2431,3214,3241,3421,4321 不能得到的序列是：

1423,2413,3124,3142,3412,4123,4132,4213,4231,4312

关闭

3.2 链栈中为何不设置头结点? 答：

链栈不需要在头部附加头结点，因为栈都是在头部进行操作的，如果加了头结点，等于要对头结点之后的结点进行操作，反而使算法更复杂，所以只要有链表的头指针就可以了。

14

关闭

3.3 循环队列的优点是什么? 如何判别它的空和满?

答：

循环队列的优点是：它可以克服顺序队列的\假上溢\现象，能够使存储队列的向量空间得到充分的利用。判别循环队列的\空\或\满\不能以头尾指针是否相等来确定，一般是通过以下几种方法：一是另设一布尔变量来区别队列的空和满。二是少用一个元素的空间,每次入队前测试入队后头尾指针是否会重合，如果会重合就认为队列已满。三是设置一计数器记录队列中元素总数，不仅可判别空或满，还可以得到队列中元素的个数。

关闭

3.4 设长度为n的链队用单循环链表表示，若设头指针，则入队出队操作的时间为何? 若只设尾指针呢? 答：

当只设头指针时，出队的时间为1，而入队的时间需要n，因为每次入队均需从头指针开始查找，找到最后一个元素时方可进行入队操作。若只设尾指针，则出入队时间均为1。因为是循环链表，尾指针所指的下一个元素就是头指针所指元素，所以出队时不需要遍历整个队列。

关闭

3.5 指出下述程序段的功能是什么? (1) void Demo1(SeqStack *S){ int i; arr[64] ; n=0 ;

while ( StackEmpty(S)) arr[n++]=Pop(S); for (i=0, i< n; i++) Push(S, arr[i]); } //Demo1

(2) SeqStack S1, S2, tmp; DataType x;

...//假设栈tmp和S2已做过初始化 while ( ! StackEmpty (&S1)) {

x=Pop(&S1) ; Push(&tmp,x); }

while ( ! StackEmpty (&tmp) ) {

x=Pop( &tmp); Push( &S1,x); Push( &S2, x); }

(3) void Demo2( SeqStack *S, int m) { // 设DataType 为int 型

15

(2)判队空

int EmptyQueue( CirQueue *Q) { //判队空

return Q->front==Q->rear; }

(3)判队满

int FullQueue( CirQueue *Q) { // 判队满//如果尾指针加1后等于头指针，则认为满 return (Q->rear+1)%QueueSize== Q->front; }

(4)出队

DataType DeQueue( CirQueue *Q) { //出队

DataType temp; if(EmptyQueue(Q))

Error(\队已空，无元素可以出队\ temp=Q->Data[Q->front] ;//保存元素值

Q->front= ( Q->front+1 ) %QueueSize;//循环意义上的加1 return temp; //返回元素值 }

(5)入队

void EnQueue (CirQueue *Q, DataType x) { // 入队

if( FullQueue( Q))

Error (\队已满，不可以入队\ Q->Data[Q->rear]=x;

Q->rear=(Q->rear+1)%QueueSize; //rear 指向下一个空元素位置 }

(6)取队头元素

DataType FrontQueue( CirQueue *Q) { //取队头元素

if (EmptyQueue( Q))

Error( \队空，无元素可取\ return Q->Data[Q->front]; }

关闭

3.13 假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素站点(注意不设头指针) ，试编写相应的置空队、判队空 、入队和出队等算法。

21

解：

算法如下： //先定义链队结构:

typedef struct queuenode{ Datatype data;

struct queuenode *next;

}QueueNode; //以上是结点类型的定义

typedef struct{

queuenode *rear;

}LinkQueue; //只设一个指向队尾元素的指针

(1)置空队

void InitQueue( LinkQueue *Q)

{ //置空队：就是使头结点成为队尾元素 QueueNode *s;

Q->rear = Q->rear->next;//将队尾指针指向头结点

while (Q->rear!=Q->rear->next)//当队列非空，将队中元素逐个出队 {s=Q->rear->next;

Q->rear->next=s->next; free(s);

}//回收结点空间 }

(2)判队空

int EmptyQueue( LinkQueue *Q) { //判队空

//当头结点的next指针指向自己时为空队 return Q->rear->next->next==Q->rear->next; }

(3)入队

void EnQueue( LinkQueue *Q, Datatype x) { //入队

//也就是在尾结点处插入元素

QueueNode *p=(QueueNode *) malloc (sizeof(QueueNode));//申请新结点 p->data=x; p->next=Q->rear->next;//初始化新结点并链入 Q-rear->next=p;

Q->rear=p;//将尾指针移至新结点 }

(4)出队

Datatype DeQueue( LinkQueue *Q) {//出队,把头结点之后的元素摘下

22

Datatype t; QueueNode *p;

if(EmptyQueue( Q ))

Error(\

p=Q->rear->next->next; //p指向将要摘下的结点 x=p->data; //保存结点中数据 if (p==Q->rear)

{//当队列中只有一个结点时，p结点出队后，要将队尾指针指向头结点 Q->rear = Q->rear->next; Q->rear->next=p->next;} else

Q->rear->next->next=p->next;//摘下结点p free(p);//释放被删结点 return x; }

关闭

3.14 对于循环向量中的循环队列，写出求队列长度的公式。

解：

公式如下(设采用第二种方法，front指向真正的队首元素，rear指向真正队尾后一位置，向量空间大小：QueueSize Queuelen=(QueueSize+rear-front)%QueueSize

关闭

3.15 假设循环队列中只设rear和quelen 来分别指示队尾元素的位置和队中元素的个数，试给出判别此循环队列的队满条件，并写出相应的入队和出队算法，要求出队时需返回队头元素。

解：

根据题意，可定义该循环队列的存储结构： #define QueueSize 100

typedef char Datatype ; //设元素的类型为char型 typedef struct { int quelen; int rear;

Datatype Data[QueueSize]; }CirQueue; CirQueue *Q;

循环队列的队满条件是：Q->quelen==QueueSize

知道了尾指针和元素个数，当然就能计算出队头元素的位置。算法如下：

(1)判断队满

int FullQueue( CirQueue *Q)

{//判队满,队中元素个数等于空间大小

23

return Q->quelen==QueueSize; }

(2)入队

void EnQueue( CirQueue *Q, Datatype x) {// 入队

if(FullQueue( Q))

Error(\队已满，无法入队\ Q->Data[Q->rear]=x;

Q->rear=(Q->rear+1)%QueueSize;//在循环意义上的加1 Q->quelen++; }

(3)出队

Datatype DeQueue( CirQueue *Q) {//出队

if(Q->quelen==0)

Error(\队已空，无元素可出队\ int tmpfront; //设一个临时队头指针

tmpfront=(QueueSize+Q->rear - Q->quelen+1)%QueueSize;//计算头指针位置 Q->quelen--;

return Q->Data[tmpfront]; } 关闭

第四章 串

4.1 简述下列每对术语的区别：

空串和空白串；串常量和串变量；主串和子串；静态分配的顺序串和动态分配的顺序串；目标串和模式串；有效位移和无效位移。

答：

●空串是指不包含任何字符的串，它的长度为零。

空白串是指包含一个或多个空格的串，空格也是字符。

●串常量是指在程序中只可引用但不可改变其值的串。 串变量是可以在运行中改变其值的。

●主串和子串是相对的，一个串中任意个连续字符组成的串就是这个串的子串，而包含子串的串就称为主串。

●静态分配的顺序串是指串的存储空间是确定的，即串值空间的大小是静态的，在编译时刻就被确定。

动态分配的顺序串是在编译时不分配串值空间，在运行过程中用malloc和free等函数根据需要动态地分配和释放字符数组的空间(这个空间长度由分配时确定，也是顺序存储空间)。

24

●目标串和模式串:在串匹配运算过程中，将主串称为目标串，而将需要匹配的子串称为模式串，两者是相对的。

●有效位移和无效位移：在串定位运算中，模式串从目标的首位开始向右位移，每一次合法位移后如果模式串与目标中相应的字符相同，则这次位移就是有效位移(也就是从此位置开始的匹配成功)，反之，若有不相同的字符存在，则此次位移就是无效位移(也就是从此位置开始的匹配失败)。

关闭

4.2 假设有如下的串说明：

char s1[30]=\

(1)在执行如下的每个语句后p的值是什么? p=stchr(s1,'t'); p=strchr(s2,'9'); p=strchr(s2,'6'); (2)在执行下列语句后，s3的值是什么? strcpy(s3,s1); strcat(s3,\ (3)调用函数strcmp(s1,s2)的返回值是什么?

(4)调用函数strcmp(&s1[5],\的返回值是什么? (5)调用函数stlen(strcat(s1,s2))的返回值是什么?

解：

(1) stchr(*s,c)函数的功能是查找字符c在串s中的位置，若找到，则返回该位置，否则返回NULL。 因此:

执行p=stchr(s1,'t');后p的值是指向第一个字符t的位置, 也就是p==&s1[1]。

执行p=strchr(s2,'9');后p的值是指向s2串中第一个9所在的位置,也就是p==&s2[9]。 ` 执行p=strchr(s2,'6');之后，p的返回值是NULL。

(2)strcpy函数功能是串拷贝，strcat函数的功能是串联接。所以: 在执行strcpy(s3,s1); 后，s3的值是\ 在执行strcat(s3,\后，s3的值变成\

在执行完strcat(s3,s2);后，s3的值就成了\

(3)函数strcmp(串1，串2)的功能是串比较，按串的大小进行比较，返回大于0，等于0或小于0的值以表示串1比串2 大，串1等于串2 ，串1小于串2。因此在调用函数strcmp(s1,s2)后，返回值是大于0的数(字符比较是以ascii码值相比的)

(4)首先，我们要知道&s1[5]是一个地址，当放在函数strcmp中时，它就表示指向以它为首地址的一个字符串，所以在strcmp( &s1[5],\中，前一个字符串值是\用它和\比较，应该是后者更大，所以返回值是小于0的数。

(5)strlen是求串长的函数，我们先将s1,s2联接起来，值是\数一数有几个字符?是不是23个(空格也是一个)? 所以返回值是23。

关闭

25

4.3 设T[0..n-1]=\当用模式串匹配目标串T时，请给出所有的有效位移。算法NaiveStrMatch(T,P)返回的位移是哪一个位移。

解：

所有的有效位移i的值为：2，5，9。

算法NaveStrMatch(T,P)的返回值是第一个有效位移，因此是2。

关闭

4.4 利用C的库函数strlen,strcpy和strcat写一算法void StrInsert(char *S, char *T, int i),将串T插入到串S的第i个位置上。若i大于S的长度，则插入不执行。 解：

算法如下：

void StrInsert(char *S, char *T, int i) {//将串T插入到串S的第i个位置上 char *Temp; if(i<=strlen(S)) {

Temp=(char *)malloc(sizeof(char[Maxsize]));// 设置一个临时串 strcpy(Temp,&S[i]);//将第i位起以后的字符拷贝到临时串中

strcpy(&S[i], T);//将串T拷贝到串S的第i个位置处，覆盖后面的字符 strcat(S,Temp);//把临时串中的字符联接到串S后面 free( Temp ); } }

关闭

4.5 利用C的库函数strlen 和strcpy(或strncpy)写一算法void StrDelete(char *S,int i, int m)删去串S中从位置i开始的连续m个字符。若i≥strlen(S),则没有字符被删除；若i+m≥strlen(S),则将S中从位置i开始直至末尾的字符均删去。

解：

算法如下：

void StrDelete(char *S, int i ,int m) { //串删除

char Temp[Maxsize];//定义一个临时串 if(i+m

strcpy (Temp, &S[i+m]);//把删除的字符以后的字符保存到临时串中 strcpy( &S[i],Temp);//用临时串中的字符覆盖位置i之后的字符 }

else if(i+m>=strlen(S)&& i

26

strcpy(&S[i],\把位置i的元素置为'\\0'，表示串结束 } }

关闭

4.6 以HString为存储表示，写一个求子串的算法。

解：

HString 是指以动态分配顺序串为存储表示，其定义为： typedef struct { char *ch; int length; }HString;

void *substr( HString *sub,HString *s,int pos,int len)

{//用sub返回串s的第pos个字符起长度为len的子串。sub初始时为一空串 //pos的合法位置为0<=pos<=s->length-1 int i;

if (pos<0||pos>s->length-1||len<=0)

Error(\参数不合法，子串为空串 if (s->lengthlen=s->length-pos;//设置子串的串长 else sub->length=len; //设置子串的串长

sub->ch=(char *)malloc(len*sizeof(char));//为sub->ch申请结点空间

for(i=0;ilength;i++)//将s串中pos位置开始的共sub->length个字符复制到sub串中 sub->ch[i]=s->ch[pos+i]; }

关闭

4.7 一个文本串可用事先给定的字母映射表进行加密。例如，设字母映射表为：

a b c d e f g h i j k l m n o p q r s t u v w x y z

n g z q t c o b m u h e l k p d a w x f y i v r s j

则字符串\被加密为\试写一算法将输入的文本串进行加密后输出；另写一算法，将输入的已加密的文本串进行解密后输出。

解：

加密算法可以用两个串中字符的一一对应关系来实现，当输入一个字符时，由算法在串Original中查找其位置，然后用串Cipher中相应位置的字符去替换原来的字符就可以了。解密算法则恰恰相返。 设字母映射表的存储结构如下：

27

#define MaxStrSize 26 typedef struct{

char Original[MaxStrSize]; //可容纳26个字符，并依次存储在Original[0..n]中 char Cipher[MaxStrSize]; //可容纳26个字符，并依次对应Original表中的密码 int length; }SeqString;

void Encrypt( SeqString codetable) {//加密算法。 char ch; int i;

while((ch=getchar())!='\\0') { i=0;

while (i

if (i>=codetable.length) Error(\ else

printf(\ }

printf(\ }

void Decipher(SeqString Original , SeqString Cipher, char* T) {//解密算法。 char ch;

while((ch=getchar())!='\\0') { i=0;

while (i

if (i>=codetable.length) Error(\ else

printf(\ }

printf(\ }

关闭

4.8 写一算法void StrReplace(char *T, char *P, char *S),将T中首次出现的子串P替换为串S。注意：S和P的长度不一定相等。可以使用已有的串操作。

解：

28

由于S和P的长度不一定相等，所以在替换时可能要移动字符元素。我们可以用到前面设计的一系列算法。算法如下：

void StrReplace (char *T, char *P, char *S) {//串替换 int i , m;

m=strlen (P);//取得子串长度

i=StrMatch(T,P);//取得串匹配位置 StrDelete( T,i,m);//删除匹配处子串

StrInsert( T, S,i);//将S串插入到匹配位置处 }

关闭

4.9 将NaveStrMatch改写为输出目标串中所有与模式串匹配的有效位移。

解：

把相应的返回语句改为打印输出就可找到所有匹配位置。改写后如下： void NaveStrMatch (SeqString T, SeqString P) {

int i,j,k;

int m=P.lenth;//模式串长度 int n=T.length;//目标串长度

for (i=0; i

j=0; k=i;

while(j

k++;j++; }

if(j==m) printf(\ }//endfor

printf(\ }

关闭

*4.10 利用4.9的结果写一算法void StrReplaceAll(char *T, char *P, char *S),将T中出现的所有与P相等的不重叠子串替换为S，这里S和P的长度不一定相等。

解：

这个算法是具有实用性的，但是做起来比较难，简单的算法应是这样的，利用4.9的算法在串T中找到一个P的匹配成功，马上进行串替换，然后从替换后的下一个位置进行匹配，直到查找完所有的有效位移或者所有合法位移考查完毕也没有匹配成功。 算法如下：

29

void StrReplaceAll(char *T, char *P, char *S) {//全部替换 int i, j, k ; i=0;

while(i

j=0; k=i;

while(T[k]==P[j]) //进行匹配 {k++;j++;}

if(j==m){ //匹配成功

StrDelete( T,i,m);//删除匹配处子串

StrInsert( T, S,i);//将S串插入到匹配位置处

i+=strlen(S); //将查找位置移到替换后的下一个字符处，避免重复替换 }//endif else i++; }//endwhile }//end

关闭

4.11 若S和T是用结点大小为1的单链表存储的两个串，试设计一个算法找出S中第一个不在T中出现的字符。 解:

查找过程是这样的，取S中的一个字符(结点)，然后和T中所有的字符一一比较，直到比完仍没有相同的字符时，查找过程结束，否则再取S中下一个字符，重新进行上述过程。算法如下： 链串的结构类型定义: typedef struct node{ char data;

struct node *next;

}LinkStrNode; //结点类型

typedef LinkStrNode *LinkString; //LinkString为链串类型 LinkString S; //S是链串的头指针

char SearchNoin( LinkString S, LinkString T) {//查找不在T中出现的字符 LinkStrNode *p,*q; p=S; q=T; while (p)

{ //取S中结点字符

while(q&&p->data!=q->data)//进行字符比较 q=q->next;

if(q==NULL) return p->data;//找到并返回字符值 q=T; //指针恢复串T的开始结点

30

p=p->next; }

printf(\ return NULL; } 关闭

第五章 数组与广义表

5.1请按行及按列优先顺序列出四维数组A2*3*2*3的所有元素在内存中的存储次序，开始结点为a0000 。

解：

按行优先的顺序排列时，先变化右边的下标，也就是右到左依次变化，这个四维数组的排列是这样的：(将这个排列分行写出以便与阅读，只要按从左到右的顺序存放就是在内存中的排列位置) a0000 a0001 a0002 a0010 a0011 a0012 a0100 a0101 a0102 a0110 a0111 a0112 a0200 a0201 a0202 a0210 a0211 a0212 a1000 a1001 a1002 a1010 a1011 a1012 a1100 a1101 a1102 a1110 a1111 a1112 a1200 a1201 a1202 a1210 a1211 a1212

按列优先的顺序排列恰恰相反，变化最快的是左边的下标，然后向右变化，所以这个四维数组的排列将是这样的，(这里为了便于阅读，也将其书写为分行形式)： a0000 a1000 a0100 a1100 a0200 a1200 a0010 a1010 a0110 a1110 a0210 a1210 a0001 a1001 a0101 a1101 a0201 a1201 a0011 a1011 a0111 a1111 a0211 a1211 a0002 a1002 a0102 a1102 a0202 a1202

31

a0012 a1012 a0112 a1112 a0212 a0212

关闭

5.2 给出C语言的三维数组地址计算公式。

解：

因为C语言的数组下标下界是0，所以 Loc(Amnp)=Loc(A000)+((i*n*p)+k)*d

其中 Amnp表示三维数组。Loc(A000)表示数组起始位置。i、j、k表示当前元素的下标,d表示每个元素所占单元数。

关闭

5.3 设有三对角矩阵 An*n，将其三条对角线上的元素逐行地存储到向量B[0...3n-3]中，使得B[k]=aij,求： (1)用i , j 表示k的下标变换公式。 (2)用 k 表示 i,j 的下标变换公式。

(1) 解：

要求i,j 到k 的下标变换公式，就是要知道在k之前已有几个非零元素，这些非零元素的个数就是k的值，一个元素所在行为i,所在列为j,则在其前面已有的非零元素个数为： (i*3-1)+j-(i+1)

其中 (i*3-1)是这个元素前面所有行的非零元素个数，j-(i+1)是它所在列前面的非零元素个数 化简可得：

k=2i+j; // c下标是从0开始的。

(2) 解：

因为K和i,j是一一对应的关系，因此这也不难算出：

i=(k+1)/3 //k+1表示当前元素前有几个非零元素,被3整除就得到行号

j=(k+1)%3+(k+1)/3-1 //k+1除以3的余数就是表示当前行中第几个非零元素， //加上前面的0元素所点列数就是当前列号

关闭

5.4 设二维数组A5*6的每个元素占4个字节，已知Loc(a00)=1000，A共占多少个字节? A的终端结点a45的起始地位为何?按行和按列优先存储时，a25的起始地址分别为何?

解：

(1)因含5*6=30个元素，因此A共占30*4=120个字节。

(2)a45的起始地址为：

Loc(a45)=Loc(a00)+(i*n+j)*d=1000+(4*6+5)*4=1116

32

(3)按行优先顺序排列时， a25=1000+(2*6+5)*4=1068

(4)按列优先顺序排列时：(二维数组可用行列下标互换来计算) a25=1000+(5*5+2)*4=1108

关闭

5.5 特殊矩阵和稀疏矩阵哪一种压缩存储后会失去随机存取的功能?为什么?

答：

后者在采用压缩存储后将会失去随机存储的功能。因为在这种矩阵中，非零元素的分布是没有规律的，为了压缩存储，就将每一个非零元素的值和它所在的行、列号做为一个结点存放在一起，这样的结点组成的线性表中叫三元组表，它已不是简单的向量，所以无法用下标直接存取矩阵中的元素。

关闭

5.6 简述广义表和线性表的区别与联系。 答:

广义表是线性表的推广，线性表是广义表的特例。当广义表中的元素都是原子时，即为线性表。 关闭

5.7 画出下列广义表的图形表示：

(1) A(a,B(b,d),C(e,B(b,d),L(f,g))) (2) A(a,B(b,A)) 解:

(1)这是一个再入表。(2)则是一个递归表。

5.8 设广义表L=((),()),试问head(L),tail(L),L的长度，深度各为多少?

解：

●head(L)=() ●tail(L)=(()) ●L的长度为2 ●L的深度为2

5.9 求下列广义表运算的结果：

33

(1)head ((p,h,w)); (2)tail((b,k,p,h)); (3) head (((a,b),(c,d))); (4)tail(((a,b),(c,d))); (5)head(tail(((a,b),(c,d)))); (6)tailhead)(((a,b),(c,d)))).

答：

(1)head ((p,h,w))=p; (2)tail((b,k,p,h))=(k,p,h); (3)head (((a,b),(c,d)))=(a,b); (4)tail(((a,b),(c,d)))=((c,d)); (5)head(tail(((a,b),(c,d))))=(c,d); (6)tail(head(((a,b),(c,d))))=(b).

5.10 当三角矩阵采用题5.3所述的压缩存储时，写一算法求三对角矩阵在这种压缩存储表示下的转置矩阵。

解：

转置矩阵就是将矩阵元素的行号与列号互换，根据已知的三对角矩阵的特点，其转置矩阵对角线元素不变，非零的非对角线元素aij与aji互换位置。又知元素的下标和存放一维数组空间位置的关系：k=2i+j。我们可以设计出这个矩阵的转置算法：

#define N 10 //矩阵行、列数

#define Length (3*N-2)//压缩矩阵的长度 typedef struct{

int data[Length]; }DiaMatrix;

void TransMatrix(DiaMatrix * C) { //压缩三对角矩阵转置 int i, j; int t;

for(i=0; i=-1)

{ //将对应于行列号的压缩矩阵内的元素互换 t=C->data[2*i+j];

C->data[2*i+j]=C->data[2*j+i]; C->data[2*j+i]=t; }//endif }//end

5.11 当稀疏矩阵A和B均以三元组表作为存储结构时，试写出矩阵相加的算法，其结果存放在三元组表C中。

解：

矩阵相加就是将两个矩阵中同一位置的元素值相加。由于两个稀疏矩阵的非零元素按三元组表形式存放，在建立新的三元组表C时，为了使三元组元素仍按行优先排列，所以每次插入的三元组不一定是A的，按照矩阵元素的行列去找A中的三元组，若有，则加入C，同时，这个元素如果在B中也有，则加上B的这个元素值，否则这个值就不变;如果A中没有，则找B，有则插入C，无则查找下一个矩阵元素。

34

#define MaxSize 10 //用户自定义 typedef int DataType; //用户自定义 typedef struct { //定义三元组 int i,j;

DataType v; }TriTupleNode;

typedef struct

{ //定义三元组表

TriTupleNode data[MaxSize];

int m,n,t;//矩阵行，列及三元组表长度 }TriTupleTable;

//以下为矩阵加算法

void AddTriTuple( TriTupleTable *A, TriTupleTable *B, TriTupleTable *C) {//三元组表表示的稀疏矩阵A,B相加 int k,l;

DataType temp;

C->m=A->m;//矩阵行数 C->n=A->n;//矩阵列数 C->t=0; //三元组表长度 k=0; l=0;

while (kt&&lt)

{if((A->data[k].i==B->data[l].i)&&(A->data[k].j==B->data[l].j)) {temp=A->data[k].v+B->data[l].v; if (!temp)//相加不为零，加入C {C->data[c->t].i=A->data[k].i; C->data[c->t].j=A->data[k].j; C->data[c->t++].v=temp; }

k++;l++; }

if ((A->data[k].i==B->data[l].i)&&(A->data[k].jdata[l].j)) ||(A->data[k].idata[l].i)//将A中三元组加入C {C->data[c->t].i=A->data[k].i; C->data[c->t].j=A->data[k].j; C->data[c->t++].v=A->data[k].v; k++; }

if ((A->data[k].i==B->data[l].i)&&(A->data[k].j>B->data[l].j)) ||(A->data[k].i>B->data[l].i)//将B中三元组加入C

{C->data[c->t].i=B->data[l].i;

35

本文来源：https://www.bwwdw.com/article/og5r.html