1、2007 年 10 月全国自考（数据结构导论）真题试卷及答案解析(总分：70.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.在数据结构中，从逻辑上可以把数据结构分成_。（分数：2.00）A.线性结构和非线性结构B.紧凑结构和非紧凑结构C.动态结构和静态结构D.内部结构和外部结构2.for(i=0；iA.O(m 2 )B.O(n 2 )C.O(mn)D.O(m+n)3.设顺序表有 9 个元素，则在第 3 个元素前插入一个元素所需移动元素的个数为_。（分数：2.00）A.5B.6C.7D.94.设 P 为指向双向循环链表中某个结点的指针，p 所指向的结点的两个链域
2、分别用 pllink 和 prlink表示，则同样表示 P 指针所指向结点的表达式是_（分数：2.00）A.pllinkB.prlinkC.pllinkllinkD.pllinkrlink5.一个向量第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的存储地址是_。（分数：2.00）A.110B.108C.100D.1206.设有一个栈，按 A、B、C、D 的顺序进栈，则可能为出栈序列的是_（分数：2.00）A.DCBAB.CDABC.DBACD.DCAB7.在一个具有 n 个单元的顺序栈中，假定以地址低端(即 0 单元)作为栈底，以 top 为栈顶指针，则当做出栈处理时，
3、top 变化为_。（分数：2.00）A.top+B.top 一一C.top 不变D.top=08.除根结点外，树上每个结点_。（分数：2.00）A.可有任意多个孩子、一个双亲B.可有任意多个孩子、任意多个双亲C.可有一个孩子、任意多个双亲D.只有一个孩子、一个双亲9.图 C-1 辛树的度为_。 （分数：2.00）A.2B.3C.5D.810.有 4 个顶点的无向完全图的边数为_。（分数：2.00）A.6B.12C.16D.2011.设图的邻接矩阵为 （分数：2.00）A.有向图B.无向图C.强连通图D.完全图12.在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这
4、种方式主要适合于_。（分数：2.00）A.静态查找表B.动态查找表C.静态查找表与动态查找表D.静态查找表或动态查找表13.用散列函数求元素在散列表中的存储位置时，可能会出现不同的关键字得到相同散列函数值的冲突现象。可用于解决上述问题的是_。（分数：2.00）A.线性探测法B.除留余数法C.平方取中法D.折叠法14.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是_。（分数：2.00）A.选择排序B.插入排序C.冒泡排序D.快速排序15.在排序方法中，从未排序序列中挑选元素，并将其依次放入已排序序列(初始时为空)的一端的方法，称为_。（分数：2.00）A.希尔排序B.归并排序C.
5、插入排序D.选择排序二、填空题(总题数：13，分数：26.00)16.如果操作不改变原逻辑结构的“值”，而只是从中提取某些信息作为运算结果，则称该类运算为 1 型运算。（分数：2.00）填空项 1:_17.设有指针 head 指向不带表头结点的单链表，用 next 表示结点的一个链域，指针 p 指向与链表中结点同类型的一个新结点。现要将指针 p 指向的结点插入表中，使之成为第一个结点，则所需的操作为“pnext=head；”和“ 1”。（分数：2.00）填空项 1:_18.单链表中逻辑上相邻的两个元素在物理位置上 1 相邻。（分数：2.00）填空项 1:_19.在一个长度为 n 的数组中删除第
6、 i 个元素(1in)时，需要向前移动的元素的个数是 1。（分数：2.00）填空项 1:_20.设 F、C 是二叉树中的两个结点，若 F 是 C 的祖先结点，则在采用后根遍历方法遍历该二叉树时，F 和C 的位置关系为：F 必定在 C 的 1。（分数：2.00）填空项 1:_21.若用后根遍历法遍历图 C-2 所示的二叉树，其输出序列为 1。 （分数：2.00）填空项 1:_22.具有 n 个顶点的连通图至少需有 1 条边。（分数：2.00）填空项 1:_23.在无向图 G 的邻接矩阵 A 中，若 Aij等于 1，则 Aji等于 1。（分数：2.00）填空项 1:_24.设顺序表的表长为 n，且
7、查找每个元素的概率相等，则采用顺序查找法查找表中任一元素，在查找成功时的平均查找长度为 1。（分数：2.00）填空项 1:_25.在索引顺序表上的查找分两个阶段：一是查找 1，二是查找块。（分数：2.00）填空项 1:_26.文件的基本运算有检索和修改两类。而检索又有三种方式，它们是 1 存取、直接存取和按关键字存取。（分数：2.00）填空项 1:_27.在对一组关键字为(54，38，96，23，15，72，60，45，83)的记录采用直接选择排序法进行排序时，整个排序过程需进行 1 趟才能够完成。（分数：2.00）填空项 1:_28.冒泡排序是一种稳定排序方法。该排序方法的时间复杂度为 1。
8、（分数：2.00）填空项 1:_三、应用题(总题数：5，分数：10.00)29.分别写出图 C-3 中二叉树的先根、中根、后根遍历序列。 （分数：2.00）_30.设要将序列(Q，H，C，Y，P，A，M，S，R)按字母升序排序，请分别画出采用堆排序方法时建立的初始堆，以及第一次输出堆顶元素后经过筛选调整的堆的完全二叉树形态。（分数：2.00）_31.如图 C-4 所示，输入元素为 A，B，C，在栈的输出端得到一个输出序列 ABC，试写出在栈的输入端三个可能的输入序列。 （分数：2.00）_32.已知无向图 G 的邻接矩阵如图 C 一 5 所示。请画出该无向图，并写出按深度优先搜索时的访问序列。
9、（分数：2.00）_33.对长度为 20 的有序表进行二分查找，试画出它的一棵判定树。（分数：2.00）_四、算法设计题(总题数：2，分数：4.00)34.下面程序段为删除循环链表中第一个 info 域值等于 x 的结点，请填上程序中缺少的部分。循环链表的结构如图 C 一 6 所示： （分数：2.00）_35.设以二叉链表为二叉树的存储结构，结点的结构如下： lehild data rchild 其中 data 域为整数，试设计一个算法 void change(bitreptr r)：若结点左孩子的 data 域的值大于右孩子的 data 域的值，则交换其左、右子树。（分数：2.00）_200
10、7 年 10 月全国自考（数据结构导论）真题试卷答案解析(总分：70.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.在数据结构中，从逻辑上可以把数据结构分成_。（分数：2.00）A.线性结构和非线性结构 B.紧凑结构和非紧凑结构C.动态结构和静态结构D.内部结构和外部结构解析：2.for(i=0；iA.O(m 2 )B.O(n 2 )C.O(mn) D.O(m+n)解析：3.设顺序表有 9 个元素，则在第 3 个元素前插入一个元素所需移动元素的个数为_。（分数：2.00）A.5B.6C.7 D.9解析：4.设 P 为指向双向循环链表中某个结点的指针，p 所指向
11、的结点的两个链域分别用 pllink 和 prlink表示，则同样表示 P 指针所指向结点的表达式是_（分数：2.00）A.pllinkB.prlinkC.pllinkllinkD.pllinkrlink 解析：5.一个向量第一个元素的存储地址是 100，每个元素的长度为 2，则第 5 个元素的存储地址是_。（分数：2.00）A.110B.108C.100 D.120解析：6.设有一个栈，按 A、B、C、D 的顺序进栈，则可能为出栈序列的是_（分数：2.00）A.DCBA B.CDABC.DBACD.DCAB解析：7.在一个具有 n 个单元的顺序栈中，假定以地址低端(即 0 单元)作为栈底，以
12、 top 为栈顶指针，则当做出栈处理时，top 变化为_。（分数：2.00）A.top+B.top 一一 C.top 不变D.top=0解析：8.除根结点外，树上每个结点_。（分数：2.00）A.可有任意多个孩子、一个双亲 B.可有任意多个孩子、任意多个双亲C.可有一个孩子、任意多个双亲D.只有一个孩子、一个双亲解析：9.图 C-1 辛树的度为_。 （分数：2.00）A.2B.3 C.5D.8解析：10.有 4 个顶点的无向完全图的边数为_。（分数：2.00）A.6 B.12C.16D.20解析：11.设图的邻接矩阵为 （分数：2.00）A.有向图 B.无向图C.强连通图D.完全图解析：12.
13、在对查找表的查找过程中，若被查找的数据元素不存在，则把该数据元素插入到集合中。这种方式主要适合于_。（分数：2.00）A.静态查找表B.动态查找表 C.静态查找表与动态查找表D.静态查找表或动态查找表解析：13.用散列函数求元素在散列表中的存储位置时，可能会出现不同的关键字得到相同散列函数值的冲突现象。可用于解决上述问题的是_。（分数：2.00）A.线性探测法 B.除留余数法C.平方取中法D.折叠法解析：14.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是_。（分数：2.00）A.选择排序B.插入排序 C.冒泡排序D.快速排序解析：15.在排序方法中，从未排序序列中挑选元素，并
14、将其依次放入已排序序列(初始时为空)的一端的方法，称为_。（分数：2.00）A.希尔排序B.归并排序C.插入排序D.选择排序 解析：二、填空题(总题数：13，分数：26.00)16.如果操作不改变原逻辑结构的“值”，而只是从中提取某些信息作为运算结果，则称该类运算为 1 型运算。（分数：2.00）填空项 1:_ （正确答案：正确答案：引用）解析：17.设有指针 head 指向不带表头结点的单链表，用 next 表示结点的一个链域，指针 p 指向与链表中结点同类型的一个新结点。现要将指针 p 指向的结点插入表中，使之成为第一个结点，则所需的操作为“pnext=head；”和“ 1”。（分数：2.
15、00）填空项 1:_ （正确答案：正确答案：head=p）解析：18.单链表中逻辑上相邻的两个元素在物理位置上 1 相邻。（分数：2.00）填空项 1:_ （正确答案：正确答案：不一定）解析：19.在一个长度为 n 的数组中删除第 i 个元素(1in)时，需要向前移动的元素的个数是 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：ni）解析：20.设 F、C 是二叉树中的两个结点，若 F 是 C 的祖先结点，则在采用后根遍历方法遍历该二叉树时，F 和C 的位置关系为：F 必定在 C 的 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：后面）解析：21.若用后根遍历法遍历
16、图 C-2 所示的二叉树，其输出序列为 1。 （分数：2.00）填空项 1:_ （正确答案：正确答案：DBFHGECA）解析：22.具有 n 个顶点的连通图至少需有 1 条边。（分数：2.00）填空项 1:_ （正确答案：正确答案：n 一 1）解析：23.在无向图 G 的邻接矩阵 A 中，若 Aij等于 1，则 Aji等于 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：1）解析：24.设顺序表的表长为 n，且查找每个元素的概率相等，则采用顺序查找法查找表中任一元素，在查找成功时的平均查找长度为 1。（分数：2.00）填空项 1:_ （正确答案：正确答案：(n+1)2）解析：25.
17、在索引顺序表上的查找分两个阶段：一是查找 1，二是查找块。（分数：2.00）填空项 1:_ （正确答案：正确答案：索引表）解析：26.文件的基本运算有检索和修改两类。而检索又有三种方式，它们是 1 存取、直接存取和按关键字存取。（分数：2.00）填空项 1:_ （正确答案：正确答案：顺序）解析：27.在对一组关键字为(54，38，96，23，15，72，60，45，83)的记录采用直接选择排序法进行排序时，整个排序过程需进行 1 趟才能够完成。（分数：2.00）填空项 1:_ （正确答案：正确答案：8）解析：28.冒泡排序是一种稳定排序方法。该排序方法的时间复杂度为 1。（分数：2.00）填空
18、项 1:_ （正确答案：正确答案：O(n2)）解析：三、应用题(总题数：5，分数：10.00)29.分别写出图 C-3 中二叉树的先根、中根、后根遍历序列。 （分数：2.00）_正确答案：(正确答案：先根遍历序列：ABCDFGHE 中根遍历序列：BADGFHCE 后根遍历序列：BGHFDECA)解析：30.设要将序列(Q，H，C，Y，P，A，M，S，R)按字母升序排序，请分别画出采用堆排序方法时建立的初始堆，以及第一次输出堆顶元素后经过筛选调整的堆的完全二叉树形态。（分数：2.00）_正确答案：(正确答案： )解析：31.如图 C-4 所示，输入元素为 A，B，C，在栈的输出端得到一个输出序列
19、 ABC，试写出在栈的输入端三个可能的输入序列。 （分数：2.00）_正确答案：(正确答案：ABC ACB BAC 另：CBA、CAB 也可。 )解析：32.已知无向图 G 的邻接矩阵如图 C 一 5 所示。请画出该无向图，并写出按深度优先搜索时的访问序列。（分数：2.00）_正确答案：(正确答案： )解析：33.对长度为 20 的有序表进行二分查找，试画出它的一棵判定树。（分数：2.00）_正确答案：(正确答案：如下图 )解析：四、算法设计题(总题数：2，分数：4.00)34.下面程序段为删除循环链表中第一个 info 域值等于 x 的结点，请填上程序中缺少的部分。循环链表的结构如图 C 一
20、 6 所示： （分数：2.00）_正确答案：(正确答案：(1)q 一link (2)q 一link=P 一link (3)p 一link (4)p=P 一next)解析：35.设以二叉链表为二叉树的存储结构，结点的结构如下： lehild data rchild 其中 data 域为整数，试设计一个算法 void change(bitreptr r)：若结点左孩子的 data 域的值大于右孩子的 data 域的值，则交换其左、右子树。（分数：2.00）_正确答案：(正确答案：Void change(bitreptr r) bitreptr x： if(r!=NULL) if(r 一lchild&r一rchile&(r 一ichild 一datar-rchild 一date) change(r 一ichild)； change(rrchild)； )解析：
