文档介绍：《算法与数据结构》习题3
一、单项选择题
1. 将一棵有100个结点的完全二叉树从根开始,每层从左到右依次对结点进行编号,根结点编号为1,则编号最大的非叶子结点的编号为( )。

2. 在待排序的元素序列基本有序的前提下,效率最高的排序算法是( )。
A、选择排序
B、插入排序
C、快速排序
D、归并排序
?( )

,访问结点和增加、删除结点的时间复杂度为( )。
(n) O(n)
B. O(n) O(1)
C. O(1) O(n)
D. O(1) O(1)
5. 对于一个头指针为head的带头结点的单链表,判定该表为空表的条件是( )
==NULL
→next==NULL
→next==head
!=NULL
6. 一个栈的输入序列为123…n,若输出序列的第一个元素是n,输出第i(1<=i<=n)个元素是( )。
A. 不确定
B. n-i+1
C. i
D. n-i
7. 有六个元素6,5,4,3,2,1 的顺序进栈,问下列哪一个不是合法的出栈序列?( )
A. 5 4 3 6 1 2
B. 4 5 3 1 2 6
C. 3 4 6 5 2 1
D. 2 3 4 1 5 6
8. 一个具有n个顶点的连通无向图的生成树中有( )条边。
A、n-1
B、n
C、n/2
D、n+1
9. 设计一个判别表达式中左,右括号是否配对出现的算法,采用( )数据结构最佳。

B. 队列
C. 线性表的链式存储结构
D. 栈
10. 设有两个串p和q,其中q是p的子串,求q在p中首次出现的位置的算法称为( )。

11. 串‘ababaaababaa’的next数组为( )。

12. 设有一个10阶的对称矩阵A,采用压缩存储方式,以行序为主存储,a11为第一元素,其存储地址为1,每个元素占一个地址空间,则a85的地址为( )。
A. 13
B. 33
C. 18
D. 40
13. 已知一算术表达式的中缀形式为A+B*C-D/E,后缀形式为ABC*+DE/-,其前缀形式为( )。
A.-A+B*C/DE
B. -A+B*CD/E
C.-+*ABC/DE
D. -+A*BC/DE
二、填空题
1. 在树形结构中,树根结点没有前驱结点,其余每个结点有且只有_______个前驱结点;叶子结点没有_______结点。
2. 若按层次顺序将一棵有n个结点的完全二叉树的所有结点编号为1到n,那么,当i为_______且不等于1时,结点i的左兄弟是结点i-1,否则结点i没有左兄弟;当i<=(n-1)/2时,结点i的右子女是_______,否则结点i没有右子女。
3. 在单链表中,除了首元结点外,任一结点的存储位置由指示。
4. 将下列表达式