2010 年 1 月全国自考数据结构导论真题 一、单项选择题(本大题共 15 小题，每小题 2 分，共 30 分) 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号 内。错选、多选或未选均无分。 1.下述文件中适合于磁带存储的是（ ） A.顺序文件 C.散列文件 B.索引文件 D.多关键字文件 2.某二叉树的后根遍历序列为 dabec，中根遍历序列为 debac，则先根遍历序列为（ ） A.acbed C.deabc 3.含有 n 个结点的二叉树用二叉链表表示时，空指针域个数为( ) A.n-1 C.n+1 4.在一个图中，所有顶点的度数之和与图的边数的比是( ) A.1∶2 C.2∶1 B.becab D.cedba B.n D.n+2 B.1∶1 D.4∶1 5.长度为 n 的链队列用单循环链表表示，若只设头指针，则出队操作的时间复杂度为 ( ) A.O(1) C.O(n) 6.下述几种排序方法中，要求内存量最大的是( ) A.插入排序 C.归并排序 B.O(1og2n) D.O(n2) B.快速排序 D.选择排序 

7.对 n 个不同值进行冒泡排序，在元素无序的情况下比较的次数为( ) A.n-1 C.n+1 B.n D.n(n-1)／2 8.对线性表进行二分查找时，要求线性表必须( ) A.以顺序方式存储 B.以链式方式存储 C.以顺序方式存储，且结点按关键字有序排列 D.以链接方式存储，且结点按关键字有序排列 9.在表长为 n 的顺序表上做删除运算，其平均时间复杂度为( ) A.O(1) C.O(nlog2n) B.O(n) D.O(n2) 10.当利用大小为 n 的数组顺序存储一个队列时，该队列的最大容量为( ) B.n-1 D.n+1 A.n-2 C.n 11.有关插入排序的叙述，错误的是( ) A.插入排序在最坏情况下需要 O(n2)时间 B.插入排序在最佳情况可在 O(n)时间内完成 C.插入排序平均需要 O(nlog2n)时间 D.插入排序的空间复杂度为 O(1) 12.有关树的叙述正确的是( ) A.每一个内部结点至少有一个兄弟 B.每一个叶结点均有父结点 

C.有的树没有子树 D.每个树至少有一个根结点与一个叶结点。 13.循环队列存储在数组元素 A[0]至 A[m]中，则入队时的操作为( ) B.rear=(rear+1)％ D.rear=(rear+1)％ A.rear=rear+1 (m-1) C.rear=(rear+1)％m (m+1) 14.关于串的的叙述，不正确的是( ) A.串是字符的有限序列 B.空串是由空格构成的串 C.替换是串的一种重要运算 D.串既可以采用顺序存储，也可以采用链式存储 15.对称矩阵 A[N][N]，A[1][1]为首元素，将下三角(包括对角线)元素以行优先顺序存储到 一维数组元素 T[1]至 T[N(N+1)／2]中，则任一上三角元素 A[i][j]存于 T[k]中，下标 k 为 ( ) A.i(i-1)／2+j B.j(j-1)／2+i D.j(i-1)／2+l C.i(j-i)／2+1 二、填空题(本大题共 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 的顺序表中删除第 i 个元素(1≤i≤n)时，需向前移动____________个元 素。 21.一个栈的输入序列是 1，2，3，…，n，输出序列的第一个元素是 n，则第 i 个输出元素 

为____________。 22.循环队列被定义为结构类型，含有三个域：data、front 和 rear，则循环队列 sq 为空的 条件是____________。 23.一个 10 阶对称矩阵 A，采用行优先顺序压缩存储上三角元素，a00 为第一个元素，其存 储地址为 0，每个元素占有 1 个存储地址空间，则 a45 的地址为____________。 24.对于一棵满二叉树，若有 m 个叶子，则树中结点数为____________。 25.含有 n 个顶点和 n-1 条边的连通图 G 采用____________存储结构较省空间。 26.在图中，第一个顶点和最后一个顶点相同的路径称为____________。 27.动态查找中两个元素 X，Y 存入同一个散列表时，X、Y 键值相同，则这种情况称为 ____________。 28.堆排序需____________个记录大小的辅助存储空间。 三、应用题(本大题共 5 小题，每小题 6 分，共 30 分) 29.有一字符串的次序为-3*y+a／y！2，试利用栈将输出次序改变为 3y*-ay！2／+，试写出 进栈和退栈的操作步骤。(用 push(x)表示 x 进栈，pop(x)表示 x 退栈) 30.已知一棵二叉树的先根遍历序列为 ABCDEGHF，中根遍历序列为 CBEDAGFH，画出该 二叉树。 31.题 31 图中二叉排序树的各结点的值为 32～40，标出各结点的值。 题 31 图 32.下述矩阵表示一个无向网，画出该无向网，并构造出其最小生成树。 

33.什么是堆?写出对应于序列(10，20，7，75，41，67，3，9，30，45)的初始堆(堆顶元素 取最小值)。 四、算法设计题(本大题共 2 小题，每小题 7 分，共 14 分) 34.二叉树按二叉链表形式存储，编写一个算法判别给定的二叉树是否为完全二叉树。 35.试写出直接插入排序算法。