1、O（log3n）在顺序表中插入或删除一个元素，需要平均移动 元素，具体移动的元素个数与 有关。0025表中一半 表长和该元素在表中的位置0026 03C1判定一个栈ST（最多元素为m0）为空的条件是B、ST-top0 、ST-top=0 、ST-m0 、ST-top=m00027 02B2 向一个长度为n的向量的第i个元素（1in+1）之前插入一个元素时，需向后移动 n-i+1 个元素。0028 02B2 向一个长度为n的向量中删除第i个元素（1in）时，需向前移动 n-i 个元素。0029 02B1在顺序表中访问任意一结点的时间复杂度均为 ，因此，顺序表也称为 的数据结构。0029 O（1）
2、 随机存取0031 02B1在单链表中，除了首元结点外，任一结点的存储位置由 指示。0031其直接前驱结点的链域的值0032 02B2 在n个结点的单链表中要删除已知结点*p，需找到它的 ，其时间复杂度为 o（n） 。0032 前驱结点的地址 O（n）线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（ x ）0037 02D1顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。（ X ） 0045 02C1在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是（ A ）A、访问第i个结点（1in）和求第i个结点的直接前驱（2in） B、在第i个结点后插入一个新结点
3、（1in）C、删除第i个结点（1in）D、将n个结点从小到大排序0106 09F2 从循环单链表中查找出最大值.0106 int searchmax（linklist l） int max; int *p; p=l;max=p-data; p=p-next;while （p-nextnil） if （maxdata） max=p- return max;0107 09F2 从循环单链表中查找出最小值 .0107 int searchmin（linklist l）int min;int *p;p=l;min=p-p=p-if （mindata） min=p-return min;0112 03D
4、1 栈和队列都是线性表.（ ）0112 正确0116 03B1 栈的两个重要应用是_和_.0116 在编译系统运行计算机语言程序的过程中,利用栈进行语法检查,实现递归调用.0117 03A2 栈和队列都是运算受到限制的特殊的线性表,栈和队列有何不同?0119 03C1 用数组A存放循环队列的元素值,若其头指针为front,尾指针为rear,则循环队列中当前元素个数为（ A ）.A、 （rear-front+m） mod m B 、 （rear-front+1） mod mC 、（rear-front-1+m） mod m D 、 （rear-front） mod m0119 A0120 03A
5、2 设循环队列Q头指针为front,尾指针为rear,队列的最大容量为M,写出循环队列队满和队空的判定条件.0120 队满条件: （q.front+1）mod m=q.rear 队空条件: q.front=q.rear0122 03F2 给出循环队列的入队和出队算法.0122 int ENQUEUE（sequeue *sq;datatype x） if（sq-front=（sq-rear+1）%maxsize） printf（queue is full）; return NULL; else sq-rear=（sq-rear+1）%maxsize;datasq-rear=x; return（T
6、RUE）; datatype DEQUEUE（sequeue *sq） if（EMPTY（sq）queue is emptyfront=（sq-front+1）%maxsize; return（sq-front;0125 03F2 设计算法判断一个算术表达式的圆括号是否正确配对,（提示:对表达式进行扫描,凡遇（就进栈,遇）就退掉栈顶的,表达式被扫描完毕,栈就为空.）0125 boolean pair（b） stack s; s.top=0; i=1; ch=bi;while （ch!=） if （ch=） | （ch=） switch :push（s,ch）;break;if empty（s）
7、 pair=false;return; else pop（s）i=i+1;ch=bi;if empty（s） pair=true;else pair=false;0127 03B2 程序段的输出结果是_（队列中的元素类型QElem Type为char）。void main（ ）Queue Q; Init Queue （Q）;Char x=e; y=c;EnQueue （Q,h）; EnQueue （Q,r）; EnQueue （Q, y）;DeQueue （Q,x）; EnQueue （Q,x）; EnQueue （Q,a）;while（!QueueEmpty（Q） DeQueue （Q,y）
8、;printf（y）; ;Printf（x）;0127 stack0129 09E2 什么是二叉排序树,按如下关键字的插入次序生成一棵二叉排序树,试画出此二叉排序树 25,48,36,16,45,20,18,720129 二叉排序树或者是一棵空树,或者是具有如下性质的二叉树: （1）若它的左子树不空,则左子树上所有结点的值均小于根结点的值 ; （2）若它的右子树不空,则右子树上所有结点的值均大于根结点的值 ; （3）左右子树又各是一棵二义排序树. 25 16 48 20 36 72 18 450135 03E1 设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有 fr
9、ont=11，rear=19; front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？0135 用队列长度计算公式： （Nrf）% N L=（401911）% 40=8 L=（401119）% 40=320138 03F2 设两个栈共享向量空间V（1:m）,它们的栈底分别设在向量的两端,且进栈的每个元素只占一个分量,试写出这两个栈公用的栈操作算法pushi（i,x）,popi（i）,其中i为0或1,用以指示栈号0138 pushi（i,x）if s.top0=s.top1-1 printf（orerflowif i=0 s.top=s.top1+1;s.elems.ti
10、op=x; elses.top1=s.top0-1;s.elems.top=x;popi（i）if i=0 if s.top0=0 printf（underflow pop=s.elems.top0 s.top1=s.top1-1; else if s.top=m+1 printf（ pop=s.elems.top1; s.top1=s.top1+1;0140 03F1 设HS为一个链栈的栈顶指针,试写出退栈的算法,（回收被删除的结点）0140 linkstack *POPSTACK（top,datap）linkstack *top;datatype *datap; linkstack *p
11、if（top=NULL）printf（under flow return NULL） *data=top- p=top; top=top- free（p）; return top;0143 03E3 设有编号为1，2，3，4的四辆列车，顺序进入一个栈式结构的车站，具体写出这四辆列车开出车站的所有可能的顺序.0143 至少有14种。 全进之后再出情况，只有1种：4，3，2，1 进3个之后再出的情况，有3种，3,4,2,1 3,2,4,1 3,2,1,4 进2个之后再出的情况，有5种，2,4,3,1 2,3,4,1 2,1, 3,4 2,1,4,3 2,1,3,4 进1个之后再出的情况，有5种，1
12、,4,3,2 1,3,2,4 1,3,4,2 1, 2,3,4 1,2,4,30147 03E2 写出栈的顺序存储结构（即顺序栈）的类型定义.0147 顺序栈的结构:typedef int datatype;#define maxsize 64typedef structdatatype datamaxsize;int topseqstack;seqstack *s;0148 03A1 写出队列的顺序存储结构（顺序队列）的类型定义.0148 顺序队列的结构:datatype datamaxsizeint front rear;sequeue;sequeue *sq;0150 03B2 带有头结
13、点的链队列q,队头指针front,队尾指针rear,则置空队的算法描述为:q-front=malloc（sizeof（linklist）; _ ;0150 q-front-next=NULLrear=q-front;0153 06C2 已知完全二叉树有个结点，则整个二叉树有（ ）个度为的结点。 A、 0; B、 1; C、 2; D、 不确定0153 B0165 06E3 已知一棵二叉树中序和后序序列为分别为:BDCEAFHG和DECBHGFA画出这棵二叉树0168 06D1 哈夫曼树的带权路径长度WPL等于叶子结点的权值之和。（ ）0168 对0169 06E3 已知二叉树的先序、中序、后序
14、序列分别如下,但其中有一些已模糊不清,构造出该二叉树.先序: _23_5_78中序: 3_41_789后序: _42_65101690172 06B3 在有N（N0）个结点的二叉链表中，空链域的个数是：_。0172 N+1 以二叉链表作存贮结构，试写出中序遍历二叉树的算法。0178 INORDER（）bitree *t;if（t） INORDER（t-lchild）;|t%c|n,t-data）; INORDER（t-rchild）;0181 06B2 具有N个结点的完全二叉树的深度为_。0181 log2 n+1+1 或log2（n+1）0184 06A2 何谓哈夫曼树?何谓完全二叉树,它具
15、有哪些特点?0184 哈夫曼树：带权路径WPL最小的二叉树称最优二叉树或哈夫曼树。完全二叉树：若一棵二叉树至多只有最下面的两层上结点的度数可以小于，并且最下一层上的结点都集中在该层最左边的若干位置上，则此二叉树为完全二叉树。特点：只有最下面两层有叶子。 如果一个结点无左子树，那它一定是叶子。 完全二叉树中任一个结点的左子树深度为，其右子树深度为或。0190 06E3 已知二叉树的中序和先序序列分别为:中序序列:DEBAFCHG先序序列:ABDECFGH试构造该二叉树01900191 06A3 度为的树与二叉树的区别。0191 度为的树每个结点如度为子树无左右之分；而二叉树则有。0192 06F
16、2 试编写算法判断两棵二叉树是否等价,称二叉树T1和T2的根结点的值相同,并且T1的左子树与T2的左子树是等价的，T1的右子树和T2的右子树是等价的.0192 EQUBINTREE（t1,t2）bintree *t1,*t2;if（t1=NULL&t1=NULL） returnTRUEelseif（t1-data=t2-data&ERUBINTREE（t1-lchild,t2-lchild）&rchild,t2-rchild）return TRUE;return FALSE;0198 06E2 已知一棵度为m的树中有N1个度为1的结点,N2个度为2的结点,问该树中有多少片叶子.0198 N0=
17、1+（i-1）Ni（i=1 to m）0200 06E3 一个深度为L的满K叉树有如下性质:第L层上的结点是叶子结点,其余各层上每个结点都有K棵非空子树,如果按层次顺序从1开始对全部结点编号,问:（1） 各层的结点的数目是多少?（2） 编号为n的结点的双亲结点（若存在）编号是多少?（3） 编号为n的结点的第i个孩子（若存在）编号是多少?（4）编号为n的结点有右兄弟的条件是什么?其右兄弟的编号是多少?02001.K（I-1）（1=Irear QU-front = = m0 、QU-front 1= = m0 、QU-front = = QU-rear 、QU-rear+10291A0321 08
18、E2 用比较两个元素大小的方法在一个给定的序列中查找某个元素的时间复杂度下限是什么? 如果要求时间复杂度更小,你采用什么方法？此方法的时间复杂度是多少?0321 查找某个元素的时间复杂度下限，如果理解为最短查找时间，则当关键字值与表头元素相同时，比较1次即可。要想降低时间复杂度，可以改用Hash查找法。此方法对表内每个元素的比较次数都是O（1）。0356 07C1用邻接表表示图进行广度优先遍历时，通常是采用（ B ）来实现算法的。A、栈 B、队列 C、 树 D、 图0357 07C1用邻接表表示图进行深度优先遍历时，通常是采用（ A ）来实现算法的。A、栈 B、队列 C、 树 D、 图 035
19、8 07C2A0 2 4 3 1 5 6B. 0 1 3 6 5 4 2C. 0 4 2 3 1 6 5D.0 3 6 1 5 4 2建议：0 1 3 4 2 5 6已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是（ C ）0359 07C2已知图的邻接矩阵,根据算法，则从顶点0出发，按深度优先遍历的结点序列是（ C ）A、 0 2 4 3 1 5 6 B、 0 1 3 5 6 4 2 C、 0 4 2 3 1 6 5 D、 0 1 3 4 2 5 60360 07C2已知图的邻接矩阵，根据算法，则从顶点0出发，按广度优先遍历的结点序列是（ ）A、 0 2 4 3 6
20、5 1 B、 0 1 3 6 4 2 5 C、 0 4 2 3 1 5 6 D、 0 1 3 4 2 5 6（建议：0 1 2 3 4 5 6）0360B0361 07C2A、 0 2 4 3 1 6 5 B、 0 1 3 5 6 4 2 C、 0 1 2 3 4 6 5 D、 0 1 2 3 4 5 60361C0362 07C2已知图的邻接表如下所示，根据算法，则从顶点0出发按深度优先遍历的结点序列是（ ）A0 1 3 2 B. 0 2 3 1 C. 0 3 2 1 D. 0 1 2 30362D0363 07C2 已知图的邻接表如下所示，根据算法，则从顶点0出发按广度优先遍历的结点序列是
21、（ ）A、0 3 2 1 B、 0 1 2 3 C、 0 1 3 2 D、 0 3 1 203630364 07C1深度优先遍历类似于二叉树的（ A ）A、先序遍历 B、中序遍历 C、 后序遍历 D、 层次遍历0365 07C1广度优先遍历类似于二叉树的（ D ）A、先序遍历 B、 中序遍历 C、后序遍历 D、层次遍历0370 07B1n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为 O（n2） 。n个顶点e条边的图，若采用邻接表存储，则空间复杂度为 O（n+e） 。0372 07B1设有一稀疏图G，则G采用 邻接表 存储较省空间。设有一稠密图G，则G采用 邻接矩阵 存储较省空间。图的逆
22、邻接表存储结构只适用于 有向 图。已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是 将邻接矩阵的第i行全部置0 。图的深度优先遍历序列 不是 惟一的。n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为 O（n2） ；若采用邻接表存储时，该算法的时间复杂度为 O（n+e） 。n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为 O（n2） ；若采用邻接表存储，该算法的时间复杂度为 O（n+e） 。图的BFS生成树的树高比DFS生成树的树高 小或相等 。用普里姆（Prim）算法求具有n个顶点e条边的图的最小生成树的时间复杂度为 O（n2） ；用克鲁斯卡尔（Kruskal）算法的时间复杂度是 O（elog2e） 。若要求一个稀疏图G的最小生成树，最好用 克鲁斯卡尔（Kruskal） 算法来求解。若要求一个稠密图G的最小生成树，最好用 普里姆（Prim） 算法来求解。拓扑排序算法是通过重复选择具有 0 个前驱顶点的过程来完成的。0385 07E3已知如图所示的有向图，请给出该图的:（1）每个顶点的入/出度；（2）邻接矩阵；（3）邻接表；（4）逆邻接表。顶点123456入度出度03850386 07E3请对下图的无向带权图：（1）写出它的邻接矩阵;（2）写出它的邻接表。0386（1） ab
