填空题（ 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++；                    /＊求串长＊/
    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，模式串长度为m，则简单模式匹配算法的时间复杂度为 O（m＊n)  。
9。5。对n个记录进行快速排序时，递归调用而是用的栈所能达到的最大深度为O(n)，平均深度为O（log2n) .
7.1。克鲁斯卡尔算法的时间复杂度为O(eloge），它对稀疏图较为合适。
6。3。在一棵二叉树中，度为0的结点的个数为N0，度为2的结点个数为N2,则有N0= N2+1。
6.8 深度为k的完全二叉树至少有2k-1个结点，至多有2k-1 个结点。
7.3。具有n个结点e条边的有向图和无向图用邻接表表示，则邻接表的边结点个数分别为e和2e条。
7.5。若n个顶点的连通图是一个环，则它有n 棵生成树.
7.6。n个顶点的连通图用连接矩阵表示时，该矩阵至少有2（n—1)个非零元素。
7.7。有n个顶点的有向图，至少需要n条弧才能保证是连通的。
9。7。归并排序除了在递归是现实所用的log2n个栈空间外，还用n个辅助空间。
2.1.对于采用顺序存储结构的线性表，当随机插入一个数据元素时，平均移动表中n/2元素；
删除一个数据元素时，
平均移动表中(n-1)/2元素.
2.4.在一个长度为n的顺序存储结构的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时,需向后边移动
n-i+1个元素。
2。5。从长度为n的采用顺序存储结构的线性表中删除第i个元素（1≤i≤n）,需向前移动n-1个元素。
3。4。当两个栈共享一存储区时,存储区用一维数组stack（1，n)表示，两栈顶指针为top【1】与top【2】，则当栈1空时。top【1】为0，栈2空时top【2】为n+1，栈满的条件是top［1］+1==top［2]。
8.1。顺序查n个元素的顺序表，若查成功，则比较关键字的次数最多为n次；当使用监视哨时，若查失败，
则比较关键字的次数为n+1。
6。5.设一颗完全二叉树叶子结点数为k，最后一层结点数为偶数时，则该二叉树的高度为+1，最后一层结点数为奇数时,则该二叉树的高度为+1.
9.8.对n个记录建立一个堆的方法是：首先将要排序的所有记录分到一棵二叉树的各个结点中，然后从i=的结点ki，逐渐把以kn/2，kn/2-1kn/2—2,……为根的子树排成堆，直到以k1根的树排成堆，就完成了初次建堆的过程。
三、计算题
4.4。StrIndex(“MY STUDENT”,”STU"）=4。
5。5。求下列广义表的运算结果：Get Tail｛GetHead｛{{a，b｝,｛c,d｝｝｝}=（b)。
6。7.已知二叉树先序为ＡＢＤＥＧＣＦ，中序为ＤＢＧＥＡＣＦ，则后序一定是DGEBFCA。
5.8.广义表{a，{a，b},d，e,｛｛i，j},k｝｝的长度是5,深度是3。
6.9.具有10个叶子的哈夫曼树，其最大高度为9，最小高度为5先序中序后序遍历二叉树。
6。1。已知二叉树有50个叶子结点，则该二叉树的总结点数至少是99。
6。10.设F是一个森林，B是由F转换得到的二叉树,F中有n个非终端节点，则B中右指针域为空的结点有n+1个。
3.10。 表达式23+(（12＊13-2）/4+34＊5/7)+108/9的后缀表达式是23 12 3*2—4/34 5*7/++108 9/+。
3.3。 用s表示入栈操作。X表示出栈操作，若元素入栈的顺序为1，2，3,4，为了得到1,3，4，2出栈顺序，相应的s和x的操作串为SXSSXSXX。
5.6。广义表A=｛｛{a,b},｛c,d，e｝}｝，取出A中的原子e的操作是:GetTail(GetTail(GetTail(GetHead(A))））。
9.10。一组记录的键值为｛12，38,35，25，74，50，63,90｝，按二路归并排序方法对该序列进行一趟归并后的结果是{12，38，25，35,50，74，63,90｝.
3。9. 一个栈的输出序列是,1，2,3,4，5,则不同的输出序列有42种
4.6。设串S的长度为4，则S的子串个数最多为10。
6。6.有5种不同形态的二叉树可以按中序遍历得到相同的abc序列.
9.9。若用冒泡排序对关键字序列{50，45,35，19,9,3｝进行从小到大的排序,所需进行的关键字比较总次数是15.
5.1.二维数组A［6]［8］采用行序为主方式存储,每个元素占4个储存单元，已知A的起始储存地址｛基地址｝是1000，则A［2］[3]的地址是1076。
6。4.叶子权值(5,6,17,8，19)所构造的哈夫曼树带权路径长度为121。
8。2。在顺序表（8，11,15，19，25，26，30，33，42，48，50)中,用折半法查关键字20，需要的关键字比较次数为4。
8.3。对于具有144个记录的文件，若采用分块查法，且每块长度为8,则平均查长度为8。25或14。
5。2。设数组A［9］[10]，数组中任一元素均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么：
{1}存放该数组至少需要的单元数是270。
{2}存放数组的第8列的所有元素至少需要的单位数是27。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。