[自学考试密押题库与答案解析]数据结构导论自考题模拟3

1、自学考试密押题库与答案解析数据结构导论自考题模拟3自学考试密押题库与答案解析数据结构导论自考题模拟3数据结构导论自考题模拟3一、单项选择题 在每小题列出的四个备选项中只有一个是符合题目要求的。 问题:1. 下列说法正确的是A.数据是数据元素的基本单位B.数据元素是数据项中不可分割的最小标识单位C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成答案:C问题:2. 下面关于线性表的叙述，错误的是A.顺序表是使用一维数组实现的线性表B.顺序表必须占用一片连续的存储单元C.顺序表的空间利用率高于链表D.在链表中，每个结点只有一个链域答案:D解析 本题主要考查的知识点是线性表。要点透析 顺序

2、表是用一维数组实现的线性表，数组的下标可看成元素的相对地址，它们是逻辑上相邻的元素，存储在物理位置也相邻的单元中。在链表中，单链表中每个结点只有一个链域，而双链表中的结点有prior和next两个链域。问题:3. 带有头结点的单链表head为空的判断条件是A.head=NULLB.head-next=NULLC.head-next=headD.head!=NULL答案:B问题:4. 一个栈的输入序列为123n，若输出序列的第一个元素是n，则输出第i(1in)个元素是A.不确定B.n-i+1C.iD.n-i答案:B问题:5. 用链接方式存储的队列，在进行删除运算时A.仅修改头指针B.仅修改尾指针

3、C.头、尾指针都要修改D.头、尾指针可能都要修改答案:D问题:6. 如图所示二叉树的中序遍历序列是 A.abcdgefB.dfebagcC.dbaefcgD.defbagc答案:B解析 本题主要考查的知识点是二叉树的中序遍历。要点透析 中序遍历的方法是：若被遍历的二叉树为空，执行空操作；否则，依次执行下列操作：中序遍历左子树；访问根结点；中序遍历右子树。问题:7. 满二叉树 二叉树。A.一定是完全B.不一定是完全C.不是D.不是完全答案:A解析 本题主要考查的知识点是满二叉树和完全二叉树的关系。要点透析 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树。问题:8. 某有向图的邻接矩阵A如下

4、，则该图中弧的条数是 A.5B.4C.3D.2答案:B解析 本题主要考查的知识点是有向图的邻接矩阵。要点透析 有向图的邻接矩阵中的非零元素个数表示对应有向图的弧的条数。问题:9. 设某无向图的邻接表如题9图所示，则该图的边的数目是 A.4B.5C.10D.20答案:B问题:10. 一个有序表为(1，3，9，12，32，41，45，62，75，77，82，95，100)，当二分查找值为82的结点时，查找成功时的比较次数为A.1B.2C.4D.8答案:C解析 本题在2008年10月真题一大题13小题考查过，主要考查的知识点是二分查找法。要点透析 二分查找法的基本思想是：每次将处于查找区间中间位置上

5、的数据元素的键值与给定值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比较：第四次比较时查找区间为82，则比较后查找成功。问题:11. 一个具有n个顶点的无向连通图，它所包含的连通分量数为A.0B.1C.nD.不确定答案:B解析 本题在2008年10月真题一大题10小题考查过，

6、主要考查的知识点是无向连通图的连通分量。要点透析 连通分量定义为无向图中的极大连通子图。由于本题中此图为无向连通图，即此图只有一个连通分量。问题:12. 在散列函数H(k)=k mod m中，一般来讲，m应取A.奇数B.偶数C.素数D.充分大的数答案:C解析 本题主要考查的知识点是散列函数。要点透析 若选m为偶数，则所得的散列函数总是将奇数键值映射成奇数地址，偶数键值映射为偶数地址，因而增加了冲突的机会。通常选m为小于或等于散列表容量的最小素数。问题:13. 排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是A.选择排序B.插入排序C.冒泡排序D.快速排序答案:B问题:14. 排序

7、趟数与序列的原始状态有关的排序方法是A.插入排序法B.选择排序法C.二路归并排序法D.快速排序法答案:D解析 本题主要考查的知识点是快速排序法。要点透析 插入排序、选择排序、二路归并排序的排序趟数只与初始关键字个数有关，与其关键字序列初始状态无关。问题:15. 下列排序方法中，属于稳定的排序方法是A.直接选择排序法B.快速排序法C.冒泡排序法D.堆排序法答案:C二、填空题问题:1. 从逻辑关系上讲，数据结构主要分为两大类，它们是_和_。答案:线性结构 非线性结构问题:2. 以下程序段的时间复杂度为_。 for(i=0；in；i+) for(j=0；jm；j+) Aij=0； 答案:O(n*m)

8、问题:3. 设某非空双链表，其结点形式为,若要删除指针q所指向的结点，则需执行下述语句段：q-prior-next=q-next；_。答案:q-next-prior=q-prior；问题:4. 线性表中结点具有_的关系。答案:一对一问题:5. 队列中允许进行删除的一端为_。答案:队列首问题:6. 二维数组A1020采用按行为主序的存储方式，每个元素占4个存储单元，若A00的存储地址为300，则A010的地址为_。答案:340问题:7. 树的遍历主要有先序遍历、后序遍历和_三种。答案:层次遍历问题:8. 深度为k的完全二叉树至少有_个结点。答案:2k-1问题:9. 有向图的极大强连通子图称为_。

9、答案:强连通分量问题:10. 对于有向图，第i个单链表中的结点个数为顶点vi的_。答案:出度问题:11. _是对每一个同义词都建一个单链表来解决冲突。答案:链地址法问题:12. 在待排序的n个记录中任取一个记录，以该记录的键值作为标准，将所有记录分为两组，使得第一组中各记录的键值均小于或等于该键值，第二组中的各记录的键值均大于该键值；然后将该记录排在两组中间。再对所分成的两组分别使用上述方法，直到所有记录都排在适当位置为止。这种排序方法称为_。答案:快速排序问题:13. 在对一组记录关键字(54，38，96，23，15，72，60，45，83)进行冒泡排序时，整个冒泡排序过程中需进行_趟才能完

10、成。答案:5三、应用题问题:1. 设有一顺序队列sq，容量为5，初始状态时sq.front=sq.rear=0，画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理由后停止。 (1)d，e，b入队 (2)d，e出队 (3)i，j入队 (4)b出队 (5)n，o，p入队 答案: (0)初态 (1)d、e、b入队 (2)d、e出队 (3)i、j入队 (4)b出队 第5步操作无法进行，因为队列已满。 问题:2. 分别写出下图中树的先序、后序和层次遍历的结点访问序列。 答案:先序序列：ABEFKLCGDHIJ 后序序列：EKLFBGCHIJDA 层次序列：ABCDEFGHIJKL

11、问题:3. 有一棵二叉树如图所示，试画出它的顺序存储结构示意图。 答案:一棵二叉树只有先转换成完全二叉树后，才能用顺序存储结构进行存储。转换后的完全二叉树如图(a)所示。二叉树的顺序存储结构示意图如图(b)所示。 问题:4. 试给出下图的邻接矩阵和邻接表表示。 答案:邻接矩阵： 邻接表： 问题:5. 已知一组键值序列(13，12，16，17，15，14，11)，试采用二路归并排序法对该组序列作升序排序，并给出每一趟的排序结果。答案: 初始关键字：13 12 16 17 15 14 11 第一趟： 12 1316 1714 1511 第二趟： 12 13 16 1711 14 15 第三趟： 1

12、1 12 13 14 15 16 17 四、算法设计题问题:1. 试编写算法判断两棵二叉树是否等价。若二叉树T1和T2等价，则T1和T2都是空的二叉树，或T1和T2的根结点的值相同，并且T1的左子树与T2的左子树是等价的，T1的右子树与T2的右子树是等价的。答案:本题采用递归方法，步骤如下： (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=T2-data) return(same_tree(T1-lchild, T2-lchild) 问题:2. 试写出二分查找的递归算法。答案:算法描述如下： int binsearch_2(Sqtable R, K