复习题
1．在下面的程序段的时间复杂度为 。
for (int i=1;i for (int j=1;j 2.栈中元素的进出原则是 ，队列中元素的进出原则 是 。 3.设指针p指向单链表中结点A，指针s指向被插入的结点X，则在结点A的前 面插入结点X时的操作序列为： 1) s->next=___________；2) p->next=s；3) t=p->data； 4) p->data=___________；5) s->data=t； 4.假设以行序为主序存储二维数组A=array[1..100,1..100],设每个数据元素 占2个存储单元，基地址为10，则LOC[6,6]= 。 5.表达式a*(b+c)-d/e的后缀表达式为 。 6.设一棵完全二叉树中有100个结点，则该二叉树的深度为__________；若用二 叉链表作为该完全二叉树的存储结构，则共有___________个空指针域。 7.设有向图G的存储结构用邻接矩阵A来表示，则A中第i行中所有非零元素 个数之和等于顶点i的________。 8.利用逐点插入法建立序列（50,72,43,85,75,20,35,45,65,30）对应的二叉排 序树以后，查找元素20要进行 次元素间的比较。 9.在活动图中，节点表示项目中各个工作阶段的里程碑，连接各个节点的边表 示活动，边上的数字表示活动持续的时间。在右边的活动图中，从A到J的关键路径长度是 ，从E开始的活动 启动的最早时间是 。 10.设一组初始记录关键字序列为(20，18， 22，16，30，19)，则根据这些初始关键字序列建成的初始大根堆序列为________________________。 11.已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为[0..6]，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，求出在查找每一个元素概率相等情况下的平均查找长度 。 12.设某无向图中顶点数和边数分别为n和e，所有顶点的度数之和为d，则 e=_______。 13．设二维数组A[0..10,0..20]按行优先顺序存储，每个元素占4个存储单元，A[2,1]的存储地址是1000，则A[5,6]的存储地址是 。 14．在循环单链表La（La为头指针）中，指针p所指结点为表尾的条件 。 15．设s=’YOU ARE STUDENT IT RIGHT OR WRONG’，顺序执行下列操作：SubString(sub1,s,1,8); SubString(sub2,s,20,5); StrCat(sub1,sub2); 则最后sub1的值为： 。 16．顺序存放的循环队列的元素以数组A[m]存放,其头尾指针分别为front和rear，则当前队列中的元素个数为 。 17．算法分析考虑的两个主要因素是 和 。 18．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结 点个数是 。 19．若待排序序列中具有相同关键字的记录在排好序后其相对位置发生了变化，则称这种排序方法是 。 20.为了保证图中的各顶点在遍历过程中访问且仅访问一次，需要为每个顶点设一个访问标志，因此要为图设置一个 ，用于标示图中每个顶点是否被访问过。 二、单项选择题 1.算法分析的两个主要方面是（ ）。 A．空间复杂性和时间复杂性 B．正确性和简明性 C．可读性和文档性 D．数据复杂性和程序复杂性 2.以下与数据的存储结构无关的术语是（ ）。 A．顺序队列 B．链表 C．有序表 D．链栈 3.以下数据结构中，（ ）是非线性数据结构。 A．树 B．字符串 C．队列 D．栈 4.线性表若采用链式存储结构时，要求内存中可用存储单元的地址( )。 A．必须是连续的 B．部分地址必须是连续的 C．一定是不连续的 D．连续或不连续都可以 5．设输入序列为1、2、3，则通过栈的作用后不可以得到的输出序列为（ ）。 A．3，1，2 B．3，2，1 A．a和(b,c) C．a 和((b,c)) C．1，3，2 D．1， 2，3 6.广义表（a,(b,c)）的表头和表尾分别为（ ）。 B．（a）和(b,c) D．(a) 和((b,c)) 7.栈和队列的共同特点是( )。 A．只允许在端点处插入和删除元素 B．都是先进后出 C．都是先进先出 D．没有共同点 8.下面程序段的时间复杂度为（ ）。 for (int i=1;i B．O(m*n) C．O(n*n) D．O(log2n) 9.在双向循环链表中，在p指针所指的节点后插入q所指向的新节点，其修改指针的操作是（ ）。 A．p->next=q;q->prior=p;p->next->prior=q;q->next=q; B．p->next=q;p->next->prior=q;q->prior=p;q->next=p->next; C．q->prior=p;q->next=p->next;p->next->prior=q;p->next=q; D．q->prior=p;q->next=p->next;p->next=q;p->next->prior=q; 10.设一条单链表的头指针变量为head且该链表没有头结点，则其判空条件是 （ ）。 A．head==NULL B．head->next==NULL D．head!=NULL C．head->next==head 11.判定一个队列Q（最多元素为m）为满队列的条件是（ ）。 A．Q->rear-Q->front = = m C．Q->front = = Q->rear 的方法称为（ ）。 A．归并排序 C．插入排序 B．Q->rear- Q->front-1= = m D．Q->front = = Q->rear+1 12.从未排序序列中挑选元素，并将其依次插入已排序序列（初始时为空）一端 B．冒泡排序 D．选择排序 13.若一组记录的排序码为(46,79,56,38,40,84)，则利用快速排序方法，以第一 个记录为基准得到的一次划分结果为（ ）。 A．38,40,46,56,79,84 C．40,38,46,56,79,84 14.串的长度是指（ ）。 A．串中所含不同字母的个数 C．串中所含不同字符的个数 B．串中所含字符的个数 D．串中所含非空格字符的个数 B．40,38,46,79,56,84 D．40,38,46,84,56,79 15.设有一个10阶的下三角矩阵A（包括对角线），按照从上到下、从左到右的 顺序存储到连续的55个存储单元中，每个数组元素占1个字节的存储空间，则A[5][4]地址与A[0][0]的地址之差为（ ）。 A．10 B．19 C．28 D．55 16.在下述结论中，正确的是（ ）。 ①只有一个结点的二叉树的度为0； ②二叉树的度为2； ③二叉树的左右子树可任意交换； ④深度为K的完全二叉树结点个数小于或等于深度相同的满二叉树； A．①②③ B．②③④ C．②④ D．①④ 17．AVL树是一种平衡的二叉排序树，树中任一结点的 。 A．左、右子树高度差的绝对值不超过1 B．左、右子树的高度均相同 C．左子树的高度均大于右子树高度 D．左子树的高度均小于右子树高度 18.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点 个数是（ ）。 A．9 A．n-1 B．11 B．n C．15 D．不确定 D．n+2 19.具有n个顶点的无向连通图的生成树应有（ ）条边。 C．n+1 20．一个有向图用邻接矩阵表示，要删除所有从第i个顶点发出的边，应该 。 A．将邻接矩阵的第 i 行删除 B．将邻接矩阵的第 i 行元素全部置零 C．将邻接矩阵的第 i 列删除 D．将邻接矩阵的第 i 列元素全部置零 21．已知一棵完全二叉树的第6层（设根为第1层）有8个叶结点，则完全二叉树的结点个数最多是 。 A．39 B．52 C．111 D．119 22.设有向无环图G中的有向边集合E={<1，2>，<2，3>，<3，4>，<1，4>}，则 下列属于该有向图G的一种拓扑排序序列的是（ ）。 A．1，2，3，4 B．2，3，4，1 C．1，4，2，3 D．1，2，4，3 23.对n个元素的表做顺序查找时，若查找每个元素的概率相同，则平均查找长 度为（ ）。 A．(n-1)/2 是 。 A．ADBEC B．BCDEA C．EBCAD D．EABCD 25．广义表(a,(b,c),d)的表头和表尾分别为 。 A．a和(b,c),d B．(a)和(b,c),d C．a和((b,c),d) D．(a)和((b,c),d) B．n/2 C．(n+1)/2 D．n 24．设某个栈的入栈序列是A,B,C,D,E，则下面4个选项中不可能的出栈序列