填空题( 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.
Int f (char*s)
{
Int i=0,j=0;
while(s[j]) j++; /*求串长*/