1、自考人网校专本套读 2018 春季招生进行中，零学历 2.5 年拿本科，支持学费分期，0 利率 0 手续费！应用市场搜索“自考人”下载自考 APP 神器，随时随地无忧备考，自测练习强化巩固，考试重点轻松装进口袋！全国 2010 年 1 月自学考试数据结构导论试题课程代码：02142一、单项选择题(本大题共 15 小题，每小题 2 分，共 30 分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.下述文件中适合于磁带存储的是（ ）A.顺序文件 B.索引文件C.散列文件 D.多关键字文件2.某二叉树的后根遍历序列为 dabec，中根遍历
2、序列为 debac，则先根遍历序列为（ ）A.acbed B.becabC.deabc D.cedba3.含有 n 个结点的二叉树用二叉链表表示时，空指针域个数为( )A.n-1 B.nC.n+1 D.n+24.在一个图中，所有顶点的度数之和与图的边数的比是( )A.12 B.11C.21 D.415.长度为 n 的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为( )A.O(1) B.O(1og2n)自考人网校专本套读 2018 春季招生进行中，零学历 2.5 年拿本科，支持学费分期，0 利率 0 手续费！应用市场搜索“自考人”下载自考 APP 神器，随时随地无忧备考，自测练习
3、强化巩固，考试重点轻松装进口袋！C.O(n) D.O(n2)6.下述几种排序方法中，要求内存量最大的是( )A.插入排序 B.快速排序C.归并排序 D.选择排序7.对 n 个不同值进行冒泡排序，在元素无序的情况下比较的次数为( )A.n-1 B.nC.n+1 D.n(n-1)28.对线性表进行二分查找时，要求线性表必须( )A.以顺序方式存储B.以链式方式存储C.以顺序方式存储，且结点按关键字有序排列D.以链接方式存储，且结点按关键字有序排列9.在表长为 n 的顺序表上做删除运算，其平均时间复杂度为( )A.O(1) B.O(n)C.O(nlog2n) D.O(n2)10.当利用大小为 n 的
4、数组顺序存储一个队列时，该队列的最大容量为( )A.n-2 B.n-1C.n D.n+111.有关插入排序的叙述，错误的是( )A.插入排序在最坏情况下需要 O(n2)时间B.插入排序在最佳情况可在 O(n)时间内完成C.插入排序平均需要 O(nlog2n)时间D.插入排序的空间复杂度为 O(1)12.有关树的叙述正确的是( )A.每一个内部结点至少有一个兄弟B.每一个叶结点均有父结点C.有的树没有子树D.每个树至少有一个根结点与一个叶结点。13.循环队列存储在数组元素 A0至 Am中，则入队时的操作为( )A.rear=rear+1 B.rear=(rear+1)(m-1)C.rear=(r
5、ear+1)m D.rear=(rear+1)(m+1)14.关于串的的叙述，不正确的是( )A.串是字符的有限序列B.空串是由空格构成的串C.替换是串的一种重要运算自考人网校专本套读 2018 春季招生进行中，零学历 2.5 年拿本科，支持学费分期，0 利率 0 手续费！应用市场搜索“自考人”下载自考 APP 神器，随时随地无忧备考，自测练习强化巩固，考试重点轻松装进口袋！D.串既可以采用顺序存储，也可以采用链式存储15.对称矩阵 ANN，A11为首元素，将下三角(包括对角线)元素以行优先顺序存储到一维数组元素 T1至TN(N+1)2中，则任一上三角元素 Aij存于 Tk中，下标 k 为(
6、)A.i(i-1) 2+j B.j(j-1)2+iC.i(j-i) 2+1 D.j(i-1)2+l二、填空题(本大题共 13 小题，每小题 2 分，共 26 分)请在每小题的空格中填上正确答案。错填、不填均无分。16.下列程序段的时间复杂度为_。for(i=1； i=n； i+)for(j=1； j=n； j+)for(k=1；k=n；k+)s=i+j+k；17.在数据结构中，各个结点按逻辑关系互相缠绕，任意两个结点可以邻接的结构称为_。18.在单链表中，存储每个结点有两个域，一个是数据域，另一个是指针域，指针域指向该结点_的。19.在栈结构中，允许插入的一端称为_。20.从一个长度为 n 的
7、顺序表中删除第 i 个元素(1in) 时，需向前移动_个元素。21.一个栈的输入序列是 1，2，3，n，输出序列的第一个元素是 n，则第 i 个输出元素为_。22.循环队列被定义为结构类型，含有三个域：data、front 和 rear，则循环队列 sq 为空的条件是_。23.一个 10 阶对称矩阵 A，采用行优先顺序压缩存储上三角元素，a 00 为第一个元素，其存储地址为 0，每个元素占有 1 个存储地址空间，则 a45 的地址为_。24.对于一棵满二叉树，若有 m 个叶子，则树中结点数为_。25.含有 n 个顶点和 n-1 条边的连通图 G 采用_ 存储结构较省空间。26.在图中，第一个顶
8、点和最后一个顶点相同的路径称为_。27.动态查找中两个元素 X， Y 存入同一个散列表时，X、Y 键值相同，则这种情况称为_。28.堆排序需_个记录大小的辅助存储空间。三、应用题(本大题共 5 小题，每小题 6 分，共 30 分)29.有一字符串的次序为-3*y+ay！2，试利用栈将输出次序改变为 3y*-ay！2+，试写出进栈和退栈的操作步骤。(用 push(x)表示 x 进栈，pop(x)表示 x 退栈)30.已知一棵二叉树的先根遍历序列为 ABCDEGHF，中根遍历序列为 CBEDAGFH，画出该二叉树。31.题 31 图中二叉排序树的各结点的值为 3240，标出各结点的值。自考人网校专本套读 2018 春季招生进行中，零学历 2.5 年拿本科，支持学费分期，0 利率 0 手续费！应用市场搜索“自考人”下载自考 APP 神器，随时随地无忧备考，自测练习强化巩固，考试重点轻松装进口袋！题 31 图32.下述矩阵表示一个无向网，画出该无向网，并构造出其最小生成树。33.什么是堆?写出对应于序列(10，20，7，75，41，67， 3，9，30，45) 的初始堆(堆顶元素取最小值)。四、算法设计题(本大题共 2 小题，每小题 7 分，共 14 分)34.二叉树按二叉链表形式存储，编写一个算法判别给定的二叉树是否为完全二叉树。35.试写出直接插入排序算法。
