数据结构课后习题及答案.pdf

填空题（10*’1=10’）一、概念题2.2.当对一个线性表经常进行的是插入和删除操作时，采用链式存储结构为宜。2.3.当对一个线性表经常进行的是存取操作，而很少进行插入和删除操作时，最好采用顺序存储结构。2.6.带头结点的单链表L中只有一个元素结点的条件是L->Next->Next==Null。3.6.循环队列的引入，目的是为了克服假溢出。4.2.长度为0的字符串称为空串。4.5.组成串的数据元素只能是字符。4.8.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为模式匹配，又称P为模式。7.2.为了实现图的广度优先搜索，除一个标志数组标志已访问的图的结点外，还需要队列存放被访问的结点实现遍历。5.7.广义表的深度是广义表中括号的重数7.8.有向图G可拓扑排序的判别条件是有无回路。7.9.若要求一个稠密图的最小生成树，最好用Prim算法求解。8.8.直接定址法法构造的哈希函数肯定不会发生冲突。9.2.排序算法所花费的时间，通常用在数据的比较和交换两大操作。1.1.通常从正确性﹑可读性﹑健壮性﹑时空效率等几个方面评价算法的（包括程序）的质量。1.2.对于给定的n元素，可以构造出的逻辑结构有集合关系﹑线性关系树形关系﹑图状关系四种。1.3.存储结构主要有顺序存储﹑链式存储﹑索引存储﹑散列存储四种。1.4.抽象数据类型的定义仅取决于它的一组逻辑特性，而与存储结构无关，即不论其内部结构如何变化，只要它的数学特性不变，都不影响其外部使用。1.5.一个算法具有五大特性：有穷性﹑确定性﹑可行性，有零个或多个输入﹑有一个或多个输入。2.8.在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s->prior=p->prior;s->next=p;p->prior-next=s;。p->prior=s;2.9.在单链表中设置头结点的作用是不管单链表是否为空表，头结点的指针均不空，并使得对单链表的操作（如插入和删除）在各种情况下统一。3.1.队列是限制在表的一端进行插入和在另一端进行删除的线性表，其运算遵循先进先出原则。3.2.栈是限定尽在表位进行插入或删除操作的线性表。3.5.在链式队列中，判定只有一个结点的条件是(Q->rear==Q->front)&&(Q->rear!=NULL)。3.7.已知链队列的头尾指针分别是f和r，则将x入队的操作序列是node*p=(node*)malloc(node);p->next=x;p->next=NULL;if(r){r->next=p;r=p;}else{r=p;f=p;}。3.8.循环队列的满与空的条件是(rear+1)%MAXSIZE==fornt和(front=-1&&rear+1==MAXSIZE)。4.3.串是一种特殊的线性表，其特殊性表现在数据元素都是由字符组成。4.7.字符串存储密度是串值所占存储位和实际分配位的比值，在字符串的链式存储结构中其结点大小是可变的。5.3.所谓稀疏矩阵指的是矩阵中非零元素远远小于元素总数，则称该矩阵为矩阵中非零元素远远小于元素总数，则称该矩阵为稀疏矩阵。5.4.一维数组的逻辑结构是线性结构，存储结构是顺序存储结构；对二维或多维数组，分别按行优先和列优先两种不同的存储方式。7.4.在有向图的邻接矩阵表示中，计算第i个顶点入度的方法是求邻接矩阵中第i列非0元素的个数。7.10.AOV网中，结点表示活动，边表示活动之间的优先关系，AOE网中，结点表示事件，边表示活动。9.1.按排序过程中依据不同原则对内部排序方法进行分类，主要有选择排序﹑交换排序﹑插入排序归并排序等4类。9.3.在堆排序、快速排序和归并排序中若只从排序结果的稳定性考虑，则应选择归并排序方法；若只从平均情况下排序最快考虑，则应选择快速排序方法；若只从最坏情况下排序最快且要节省类存考虑，则应选择堆排序方法。9.4.直接插入排序用监视哨的作用是存当前要的插入记录，可又省去查找插入位置时对是否出界的判断。9.6.设表中元素的初始状态是按键值递增的，则直接插入排序最省时间，快速排序最费时间。4.9.下列程序判断字符串s是否对称，对称则返回1，否则返回0；如ƒ(“abba”)返回1，ƒ（”abab”）返回0.Intf(char*s){Inti=0,j=0;while(s[j])j++;/*求串长*/for(j--;i<j&&s[i]==s[j];i++,j++);return(i>=j);}二、结论题2.7.在具有n个结点有序单链表中插入一个新结点并仍然有序的时间复杂度为O(n)。2.10.对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为O(1)，在给定值为x的结点后插入一个新结点的时间复杂度为O(n)。4.1.设正文产长度为n，模式串长