请在每小题的空格中填上正确答案。错填、不填均无分。
16下列程序段的时间复杂度为___________。
i1；
while（i
）
ii2；
17向一个长度为
的顺序表中第i（1≤i≤
）个元素之前插入一个元素时，需向后移动___________个元素。
18在循环双链表中，删除最后一个结点，其算法的时间复杂度为___________。
19队列的插入操作在队列的___________部分进行。
20一个栈的输入序列是1，2，3，…，
，输出序列的第一个元素是
，则第i个输出元素为___________。
21一个10阶对称矩阵A，采用行优先顺序压缩存储下三角，a00为第一个元素，其存储地址为1，每个元素占有1
个存储地址空间，则a85的地址为___________。
可编辑
f精选文档
22设字符串S″I□AM□A□STUDENT″（其中□表示空格字符），则S的长度为___________。
23在树形结构中，没有后继的结点是___________结点。
24一棵深度为
1的满二叉树中共有___________个结点。
25在无向图中，如果从顶点v到顶点v′有路径，则称v和v′是___________。
26无向完全图G采用___________存储结构较省空间。
27在顺序查找、二分查找、索引查找和散列查找四种查找方法中，平均查找长度与元素个数没有关系的查找方法
是___________。
28快速排序最好情况下的时间复杂度为___________。
三、应用题本大题共5小题，每小题6分，共30分
29稀疏矩阵A如下，写出矩阵A的三元组表及矩阵A的转置矩阵的三元组表。
030001
0
0
0
0
0
0

510000
0
0
0
0
4
0

300000
30一棵二叉树的前根遍历序列为ABCDEFG，中根遍历序列为CBDAEGF，试构造出该二叉树。
31下述矩阵表示一个无向连通网，试画出它所表示的连通网及该连通网的最小生成树。
112510
1
8
9


1282
5
9


4
1024
32给定表（80，90，50，70，75，60，40，100），试按元素在表中的顺序将它们依次插入一棵初始时为空的二
叉排序树，画出插入完成后的二叉排序树。
33试写出一组键值（46，58，15，45，90，18，10，62）应用直接插入排序算法从小到大排序后各趟的结果。
四、算法设计题本大题共2小题，每小题7分，共14分
34试分别写出二叉树的先根遍历和中根遍历的递归算法。
35试编写以单链表为存储结构实现直接选择排序的算法。
可编辑
f精选文档
2011年1月全国自考数据结构导论参考答案
可编辑
f精选文档可编辑
f精选文档可编辑
f精选文档
全国2010年10月自学考试数据结构导论试题
课程代码：021r