1、数据结构导论自考题-3 及答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.下列说法正确的是( )A数据是数据元素的基本单位B数据元素是数据项中不可分割的最小标识单位C数据可由若干个数据元素构成D数据项可由若干个数据元素构成（分数：2.00）A.B.C.D.2.下面关于线性表的叙述，错误的是( )A顺序表是使用一维数组实现的线性表 B顺序表必须占用一片连续的存储单元C顺序表的空间利用率高于链表 D在链表中，每个结点只有一个链域（分数：2.00）A.B.C.D.3.带有头结点的单链表 head为空的判断条件是( )Ahead=NULL Bhe
2、ad-next=NULLChead-next=head Dhead!=NULL（分数：2.00）A.B.C.D.4.一个栈的输入序列为 123n，若输出序列的第一个元素是 n，则输出第 i(1in)个元素是( )A不确定 Bn-i+1Ci Dn-i（分数：2.00）A.B.C.D.5.用链接方式存储的队列，在进行删除运算时( )A仅修改头指针 B仅修改尾指针C头、尾指针都要修改 D头、尾指针可能都要修改（分数：2.00）A.B.C.D.6.如图所示二叉树的中序遍历序列是( )（分数：2.00）A.B.C.D.7.满二叉树( )二叉树。A一定是完全 B不一定是完全C不是 D不是完全（分数：2.0
3、0）A.B.C.D.8.某有向图的邻接矩阵 A如下，则该图中弧的条数是( )（分数：2.00）A.B.C.D.9.设某无向图的邻接表如题 9图所示，则该图的边的数目是( )（分数：2.00）A.B.C.D.10.一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当二分查找值为 82的结点时，查找成功时的比较次数为( )A1 B2C4 D8（分数：2.00）A.B.C.D.11.一个具有 n个顶点的无向连通图，它所包含的连通分量数为( )A0 B1Cn D不确定（分数：2.00）A.B.C.D.12.在散列函数 H(k)=k mod m中，一般来讲，m 应
4、取( )A奇数 B偶数C素数 D充分大的数（分数：2.00）A.B.C.D.13.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是( )A选择排序 B插入排序C冒泡排序 D快速排序（分数：2.00）A.B.C.D.14.排序趟数与序列的原始状态有关的排序方法是( )A插入排序法 B选择排序法C二路归并排序法 D快速排序法（分数：2.00）A.B.C.D.15.下列排序方法中，属于稳定的排序方法是( )A直接选择排序法 B快速排序法C冒泡排序法 D堆排序法（分数：2.00）A.B.C.D.二、填空题(总题数：13，分数：26.00)16.从逻辑关系上讲，数据结构主要分为两大类，它们
5、是_和_。（分数：2.00）填空项 1:_17.以下程序段的时间复杂度为_。for(i=0；in；i+)for(j=0；jm；j+)Aij=0；（分数：2.00）填空项 1:_18.设某非空双链表，其结点形式为 （分数：2.00）填空项 1:_19.线性表中结点具有 1 的关系。（分数：2.00）填空项 1:_20.队列中允许进行删除的一端为 1。（分数：2.00）填空项 1:_21.二维数组 A1020采用按行为主序的存储方式，每个元素占 4个存储单元，若 A00的存储地址为300，则 A010的地址为 1。（分数：2.00）填空项 1:_22.树的遍历主要有先序遍历、后序遍历和 1 三种。
6、（分数：2.00）填空项 1:_23.深度为 k的完全二叉树至少有 1 个结点。（分数：2.00）填空项 1:_24.有向图的极大强连通子图称为 1。（分数：2.00）填空项 1:_25.对于有向图，第 i个单链表中的结点个数为顶点 vi的 1。（分数：2.00）填空项 1:_26. 1是对每一个同义词都建一个单链表来解决冲突。（分数：2.00）填空项 1:_27.在待排序的 n个记录中任取一个记录，以该记录的键值作为标准，将所有记录分为两组，使得第一组中各记录的键值均小于或等于该键值，第二组中的各记录的键值均大于该键值；然后将该记录排在两组中间。再对所分成的两组分别使用上述方法，直到所有记录
7、都排在适当位置为止。这种排序方法称为 1。（分数：2.00）填空项 1:_28.在对一组记录关键字(54，38，96，23，15，72，60，45，83)进行冒泡排序时，整个冒泡排序过程中需进行 1 趟才能完成。（分数：2.00）填空项 1:_三、应用题(总题数：5，分数：30.00)29.设有一顺序队列 sq，容量为 5，初始状态时 sq.front=sq.rear=0，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理由后停止。(1)d，e，b 入队(2)d，e 出队(3)i，j 入队(4)b出队(5)n，o，p 入队（分数：6.00）_30.分别写出下图中树的先序、
8、后序和层次遍历的结点访问序列。（分数：6.00）_31.有一棵二叉树如图所示，试画出它的顺序存储结构示意图。（分数：6.00）_32.试给出下图的邻接矩阵和邻接表表示。（分数：6.00）_33.已知一组键值序列(13，12，16，17，15，14，11)，试采用二路归并排序法对该组序列作升序排序，并给出每一趟的排序结果。（分数：6.00）_四、算法设计题(总题数：2，分数：14.00)34.试编写算法判断两棵二叉树是否等价。若二叉树 T1和 T2等价，则 T1和 T2都是空的二叉树，或 T1和 T2的根结点的值相同，并且 T1的左子树与 T2的左子树是等价的，T 1的右子树与 T2的右子树是等
9、价的。（分数：7.00）_35.试写出二分查找的递归算法。（分数：7.00）_数据结构导论自考题-3 答案解析(总分：100.00，做题时间：90 分钟)一、单项选择题(总题数：15，分数：30.00)1.下列说法正确的是( )A数据是数据元素的基本单位B数据元素是数据项中不可分割的最小标识单位C数据可由若干个数据元素构成D数据项可由若干个数据元素构成（分数：2.00）A.B.C. D.解析：2.下面关于线性表的叙述，错误的是( )A顺序表是使用一维数组实现的线性表 B顺序表必须占用一片连续的存储单元C顺序表的空间利用率高于链表 D在链表中，每个结点只有一个链域（分数：2.00）A.B.C.D
10、. 解析：解析 本题主要考查的知识点是线性表。要点透析 顺序表是用一维数组实现的线性表，数组的下标可看成元素的相对地址，它们是逻辑上相邻的元素，存储在物理位置也相邻的单元中。在链表中，单链表中每个结点只有一个链域，而双链表中的结点有 prior和 next两个链域。3.带有头结点的单链表 head为空的判断条件是( )Ahead=NULL Bhead-next=NULLChead-next=head Dhead!=NULL（分数：2.00）A.B. C.D.解析：4.一个栈的输入序列为 123n，若输出序列的第一个元素是 n，则输出第 i(1in)个元素是( )A不确定 Bn-i+1Ci Dn
11、-i（分数：2.00）A.B. C.D.解析：5.用链接方式存储的队列，在进行删除运算时( )A仅修改头指针 B仅修改尾指针C头、尾指针都要修改 D头、尾指针可能都要修改（分数：2.00）A.B.C.D. 解析：6.如图所示二叉树的中序遍历序列是( )（分数：2.00）A.B. C.D.解析：解析 本题主要考查的知识点是二叉树的中序遍历。要点透析 中序遍历的方法是：若被遍历的二叉树为空，执行空操作；否则，依次执行下列操作：中序遍历左子树；访问根结点；中序遍历右子树。7.满二叉树( )二叉树。A一定是完全 B不一定是完全C不是 D不是完全（分数：2.00）A. B.C.D.解析：解析 本题主要考
12、查的知识点是满二叉树和完全二叉树的关系。要点透析 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。8.某有向图的邻接矩阵 A如下，则该图中弧的条数是( )（分数：2.00）A.B. C.D.解析：解析 本题主要考查的知识点是有向图的邻接矩阵。要点透析 有向图的邻接矩阵中的非零元素个数表示对应有向图的弧的条数。9.设某无向图的邻接表如题 9图所示，则该图的边的数目是( )（分数：2.00）A.B. C.D.解析：10.一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当二分查找值为 82的结点时，查找成功时的比较次数为( )A1 B2C4 D8（分数
13、：2.00）A.B.C. D.解析：解析 本题在 2008年 10月真题一大题 13小题考查过，主要考查的知识点是二分查找法。要点透析 二分查找法的基本思想是：每次将处于查找区间中间位置上的数据元素的键值与给定值 K比较，若不等则缩小查找区间并在新的区间内重复上述过程，直到查找成功或查找区间长度为 0(即查找不成功)为止。而本题中，第一次比较时查找区间为1，3，9，12，32，41，45，62，75，77，82，95，100，用 82与 45进行比较：第二次比较时查找区间为62，75，77，82，95，100，用 82与 77比较；第三次比较时查找区间为82，95，100，用 82与 95比较
14、：第四次比较时查找区间为82，则比较后查找成功。11.一个具有 n个顶点的无向连通图，它所包含的连通分量数为( )A0 B1Cn D不确定（分数：2.00）A.B. C.D.解析：解析 本题在 2008年 10月真题一大题 10小题考查过，主要考查的知识点是无向连通图的连通分量。要点透析 连通分量定义为无向图中的极大连通子图。由于本题中此图为无向连通图，即此图只有一个连通分量。12.在散列函数 H(k)=k mod m中，一般来讲，m 应取( )A奇数 B偶数C素数 D充分大的数（分数：2.00）A.B.C. D.解析：解析 本题主要考查的知识点是散列函数。要点透析 若选 m为偶数，则所得的散
15、列函数总是将奇数键值映射成奇数地址，偶数键值映射为偶数地址，因而增加了冲突的机会。通常选 m为小于或等于散列表容量的最小素数。13.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是( )A选择排序 B插入排序C冒泡排序 D快速排序（分数：2.00）A.B. C.D.解析：14.排序趟数与序列的原始状态有关的排序方法是( )A插入排序法 B选择排序法C二路归并排序法 D快速排序法（分数：2.00）A.B.C.D. 解析：解析 本题主要考查的知识点是快速排序法。要点透析 插入排序、选择排序、二路归并排序的排序趟数只与初始关键字个数有关，与其关键字序列初始状态无关。15.下列排序方法中
16、，属于稳定的排序方法是( )A直接选择排序法 B快速排序法C冒泡排序法 D堆排序法（分数：2.00）A.B.C. D.解析：二、填空题(总题数：13，分数：26.00)16.从逻辑关系上讲，数据结构主要分为两大类，它们是_和_。（分数：2.00）填空项 1:_ （正确答案：线性结构 非线性结构）解析：17.以下程序段的时间复杂度为_。for(i=0；in；i+)for(j=0；jm；j+)Aij=0；（分数：2.00）填空项 1:_ （正确答案：O(n*m)）解析：18.设某非空双链表，其结点形式为 （分数：2.00）填空项 1:_ （正确答案：q-next-prior=q-prior；）解析
17、：19.线性表中结点具有 1 的关系。（分数：2.00）填空项 1:_ （正确答案：一对一）解析：20.队列中允许进行删除的一端为 1。（分数：2.00）填空项 1:_ （正确答案：队列首）解析：21.二维数组 A1020采用按行为主序的存储方式，每个元素占 4个存储单元，若 A00的存储地址为300，则 A010的地址为 1。（分数：2.00）填空项 1:_ （正确答案：340）解析：22.树的遍历主要有先序遍历、后序遍历和 1 三种。（分数：2.00）填空项 1:_ （正确答案：层次遍历）解析：23.深度为 k的完全二叉树至少有 1 个结点。（分数：2.00）填空项 1:_ （正确答案：2
18、 k-1）解析：24.有向图的极大强连通子图称为 1。（分数：2.00）填空项 1:_ （正确答案：强连通分量）解析：25.对于有向图，第 i个单链表中的结点个数为顶点 vi的 1。（分数：2.00）填空项 1:_ （正确答案：出度）解析：26. 1是对每一个同义词都建一个单链表来解决冲突。（分数：2.00）填空项 1:_ （正确答案：链地址法）解析：27.在待排序的 n个记录中任取一个记录，以该记录的键值作为标准，将所有记录分为两组，使得第一组中各记录的键值均小于或等于该键值，第二组中的各记录的键值均大于该键值；然后将该记录排在两组中间。再对所分成的两组分别使用上述方法，直到所有记录都排在适
19、当位置为止。这种排序方法称为 1。（分数：2.00）填空项 1:_ （正确答案：快速排序）解析：28.在对一组记录关键字(54，38，96，23，15，72，60，45，83)进行冒泡排序时，整个冒泡排序过程中需进行 1 趟才能完成。（分数：2.00）填空项 1:_ （正确答案：5）解析：三、应用题(总题数：5，分数：30.00)29.设有一顺序队列 sq，容量为 5，初始状态时 sq.front=sq.rear=0，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理由后停止。(1)d，e，b 入队(2)d，e 出队(3)i，j 入队(4)b出队(5)n，o，p 入队（分
20、数：6.00）_正确答案：( )解析：30.分别写出下图中树的先序、后序和层次遍历的结点访问序列。（分数：6.00）_正确答案：(先序序列：ABEFKLCGDHIJ后序序列：EKLFBGCHIJDA层次序列：ABCDEFGHIJKL)解析：31.有一棵二叉树如图所示，试画出它的顺序存储结构示意图。（分数：6.00）_正确答案：(一棵二叉树只有先转换成完全二叉树后，才能用顺序存储结构进行存储。转换后的完全二叉树如图(a)所示。二叉树的顺序存储结构示意图如图(b)所示。)解析：32.试给出下图的邻接矩阵和邻接表表示。（分数：6.00）_正确答案：(邻接矩阵：邻接表：)解析：33.已知一组键值序列(
21、13，12，16，17，15，14，11)，试采用二路归并排序法对该组序列作升序排序，并给出每一趟的排序结果。（分数：6.00）_正确答案：(初始关键字：13 12 16 17 15 14 11第一趟：12 1316 1714 1511第二趟：12 13 16 1711 14 15第三趟：11 12 13 14 15 16 17)解析：四、算法设计题(总题数：2，分数：14.00)34.试编写算法判断两棵二叉树是否等价。若二叉树 T1和 T2等价，则 T1和 T2都是空的二叉树，或 T1和 T2的根结点的值相同，并且 T1的左子树与 T2的左子树是等价的，T 1的右子树与 T2的右子树是等价的
22、。（分数：7.00）_正确答案：(本题采用递归方法，步骤如下：(1)若 T1和 T2都是空树则等价。(2)若 T1和 T2有一个为空树，另一个是非空树，则不等价。(3)若 T1和 T2两个都是非空树且它们的根的值相等，比较它们的左、右子树。int same_tree(BinTree T1, T2) if(T1=NULL)else if(T1=NULL)|(T2=NULL)return(0);else if(T1-data=T 2-data)return(same_tree(T1-lchild, T 2-lchild)解析：35.试写出二分查找的递归算法。（分数：7.00）_正确答案：(算法描述如下：int binsearch_2(Sqtable R, KeyType k, int low,int high)int mid=(low+high)/2;if(R.elemmid.key=k) return mid;else if(R.elemmid.keyk)return binsearch 2(R, K, low, mid-1);else return binsearch_2(R, K, mid+1; high);)解析：
