内容发布更新时间 : 2024/11/8 16:41:17星期一 下面是文章的全部内容请认真阅读。
习 题 二
1 简述下列术语：线性表，顺序表，链表。
线性表：最常用且最简单的一种数据结构。一个线性表是n个数据元素的有限序列。 顺序表：是指用一组连续的存储单元一次存储线性表中的数据元素。物理结构和逻辑结构都相邻。
链表：逻辑结构相邻的数据元素物理结构不一定相邻。采用指针的形式连接起来。
2 何时选用顺序表，何时选用链表作为线性表的存储结构合适?各自的主要优缺点是什么?
不需要经常大量的修改表或需要随机存取的情况下可以选用顺序表；
相反需要经常大量的修改表，但不是频繁的随机存取的情况下可选用链式表。
3 在顺序表中插入和删除一个结点平均需要移动多少个结点?具体的移动次数取决于哪两个因素?
答：平均需要移动n/2个结点。表的长度，和要插入的位置。
4 链表所表示的元素是否有序?如有序，则有序性体现于何处?链表所表示的元素是否一定要在物理上是相邻的?有序表的有序性又如何理解?
答：有序。有序性体现在通过指针数据元素有序的相连。物理上不一定要相邻。
5 设顺序表L是递增有序表，试写一算法，将x插入到L中并使L仍是递增有序表。 Status ListInsert(SqList &L,int i,ElemType e) { if((i>L.length+1)||i<1) return ERROR; if(L.length>=L.listsize) { newbase=(ElemType *)realloc((L.listsize+LISTINCREMENT)*sizeof(ElemType)); if(!newbase) exit(-1); L.elem=newbase; L.listsize+=LISTINCREMENT; } ElemType *q,*p; q=&L.elem[i-1]; for(p=&L.elem[L.length-1];p>=q;p--) *(p+1)=*p; *q=e; L.length++; return OK; }
9 设A和B是两个按元素值递增有序的单链表，写一算法将A和B归并为按按元素值递减有序的单链表C，试分析算法的时间复杂度。
void ListInsert(SqList A,SqList B,SqList C) { ElemType *p,*q,*s; P=&A; q=&B; s=&C; while(p.next!=NULL||q.next!=NULL) { if(p.next.data<=q.next.data) { if(s.next!=NULL) p.next=s.next; s.next=p.next; p++; } else { if(s.next!=NULL) q.next=s.next; s.next=q.next; q++; } } while(p.next!=NULL) { p.next=s.next; s.next=p.next; } while(q.next!=NULL) { q.next=s.next; s.next=q.next; }
习 题 三
1 设有一个栈，元素进栈的次序为a, b, c。问经过栈操作后可以得到哪些输出序列？
Abc,acb,bac,bca,cba.
2 循环队列的优点是什么?如何判断它的空和满?
优点：可以克服顺序队列的“假上溢”现象，能够使存储队列的向量空间得到充分
利用。
判断循环队列的空或满不能以头尾指针是否相等来确定，一般是通过以下几种方法：
一是另设一布尔变量来区别队列的空和满。二是约定入队前，测试尾指针在循环意义下加1后是否等于头指针，若相等则认为队满。三是设置一计数器记录队列中元
素的总数，不仅可判别空或满，还可以得到队列中元素的个数 。
3 设有一个静态顺序队列，向量大小为MAX，判断队列为空的条件是什么？队列满的条件是什么？
队列为空：front=rear。队满：rear=MAX -1或front=rear (队首指针front ，一个队尾指针rear)
4 设有一个静态循环队列，向量大小为MAX，判断队列为空的条件是什么？队列满的条件是什么？
循环队列为空：front=rear 。 循环队列满：(rear+1)%MAX=front。 (队首指针front ，一个队尾指针rear)
5 利用栈的基本操作，写一个返回栈S中结点个数的算法int StackSize(SeqStack S) ，并说明S为何不作为指针参数的算法? intStackSize (SeqStack S) {//计算栈中结点个数 int n=0;
if(!EmptyStack(&S)) {
Pop(&S); n++; }
return n; }
上述算法的目的只要得到S栈的结点个数就可以了。并不能改变栈的结构。所以S不用指针做参数，以避免对原来的栈中元素进行任何改变。系统会把原来的栈按值传递给形参，函数只对形参进行操作，最后返回元素个数。
7 设Q[0,6]是一个静态顺序队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。 a, b, c, d入队 a, b, c出队
i , j , k , l , m入队 d, i出队
n, o, p, q, r入队
图解：
8 假设Q[0,5]是一个循环队列，初始状态为front=rear=0，请画出做完下列操作后队列的头尾指针的状态变化情况，若不能入对，请指出其元素，并说明理由。 d, e, b, g, h入队 d, e出队
i , j , k , l , m入队 b出队
n, o, p, q, r入队 图解：
习 题 四
⑵ 解释下列每对术语的区别：空串和空白串；主串和子串；目标串和模式串。
解：空串和空白串的区别：空串不含任何字符，它的长度为0，而空白串含有一个空格，它的长度为1.
主串和子串的区别：主串是相对于子串而言的，子串是主串中连续的一段，是主串的一个子集。
目标串和模式串的区别：目标串是在模式匹配中的主串，是相对于模式串运算的母串，而模式串是子串，是在主串中运算的子串。
⑵ 若x和y是两个采用顺序结构存储的串，写一算法比较这两个字符串是否相等。 解：
int streql(Hstring x, Hstring y) if(x[0]!=y[0]) return (0); else i=1;
while(x[i]==y[i]&&i if(i== x[0]) return (1) else return (0) 习 题 五 ⑴ 什么是广义表？请简述广义表与线性表的区别？ 广义表是零至多个元素的有限序列，广义表中的元素可以是原子，也可以是子表。从“元素的有限序列”角度看，广义表满足线性结构的特性：在非空线性结构中，只有一个称为“第一个”的元素，只有一个称为“最后一个”的元素，第一元素有后继而没有前驱，最后一个元素有前驱而没有后继，其余每个元素有唯一前驱和唯一后继。从这个意义上说，广义表属于扩充的线性结构（只不过元素并不具有同一类型：可以是原子，也可以是广义表）。当广义表中的元素都是原子时，广义表就蜕变为线性表。 广义表是线性表的推广，线性表是广义表的特例。当广义表中的元素都是原子时，即为线性表 ⑵ 一个广义表是(a, (a, b), d, e, (a, (i, j), k)) ，请画出该广义表的链式存储结构。