1、数据结构导论自考题模拟 9及答案解析(总分：100.00，做题时间：90 分钟)一、在每小题列出的四个备选项中只有一个是符合(总题数：15，分数：30.00)1.关于算法的描述，不正确的是_（分数：2.00）A.算法最终必须由计算机程序实现B.所谓最坏时间复杂度是指最坏情况下，估算算法执行时间的一个上界C.健壮的算法不会因非法的输入数据而出现莫名其妙的运行结果D.算法的优劣与算法描述语言无关2.线性表若采用链表存储结构，则要求内存中可用存储单元的地址_（分数：2.00）A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D.连续不连续都可以3.以下属于逻辑结构的是_（分数：2.00）A.
2、顺序表B.哈希表C.有序表D.单链表4.已知循环队列的存储空间为数组 data21，且当前队列的头指针和尾指针的值分别为 8和 3，则该队列的当前长度为_（分数：2.00）A.5B.6C.16D.175.对特殊矩阵采用压缩存储的目的主要是为了_（分数：2.00）A.表达变得简单B.对矩阵元素的存取变得简单C.去掉矩阵中多余元素D.减少不必要的存储空间6.将一棵有 1000个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为 1，则编号最大的分支结点的编号为_（分数：2.00）A.48B.49C.50D.517.若二叉树的中序遍历序列是 abcdef，且 c为根结点，
3、则_（分数：2.00）A.结点 c有两个孩子B.二叉树有两个度为 0的结点C.二叉树的高度为 5D.以上都不对8.已知森林 F=T 1 ，T 2 ，T 3 ，T 4 ，T 5 ，各棵树 T i (i=1，2，3，4，5)中所含结点的个数分别为7、3、5、1、2，则与 F对应的二叉树的右子树中的结点个数为_（分数：2.00）A.2B.3C.8D.119.在具有 6个顶点的无向图 G至少应有多少条边才能确保是一个连通图_（分数：2.00）A.8B.7C.6D.510.一个具有 n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是_ A.n-1 B.n+1 C.n2 D.(n+1)2（分数：2.0
4、0）A.B.C.D.11.索引顺序表的索引表在组织形式上是一个_（分数：2.00）A.顺序表B.单链表C.队列D栈12.静态查找表的运算包括_（分数：2.00）A.建表B.建表和查找C.查找和读表元D.建表、查找和读表中元表13.设散列表长 m=13，散列函数 h(key)=key%11。表巾已有 4个结点：h(15)=4，h(27)=5，h(39)=6，h(51)=7，其余地址为空，若采用二次探测法处理冲突，则关键字为 49的结点地址是_（分数：2.00）A.3B.5C.8D.914.下列四种排序方法中，要求附加的内存容量最大的是_（分数：2.00）A.插入排序B.选择排序C.快速排序D.归
5、并排序15.对于键值序列72，73，71，23，94，16，5，68，76，103用筛选法建堆，必须从键值为_的结点开始。（分数：2.00）A.103B.72C.94D.23二、填空题(总题数：13，分数：26.00)16.表示逻辑关系的存储结构可以有四种方式，即顺序存储方式、链式存储方式、 1 和散列存储方式。 （分数：2.00）17.当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用 1 作为其存储结构。 （分数：2.00）18.在双链表中间插入一个结点，需要修改 1 个指针。 （分数：2.00）19.一般地，将 1 设在链表的表头一端， 2 设在链表的表尾。 （分数：
6、2.00）20.顺序队列结构类型中有三个域：data、 1 和 2。 （分数：2.00）21.矩阵的非零元素个数很少的矩阵称为 1。 （分数：2.00）22.在具有几个结点的完全二叉树中，结点 i(2in)的左孩子结点是 1。 （分数：2.00）23.在 1 遍历二叉树的序列中，任何结点的子树上所有结点，都是直接跟在该结点之后。 （分数：2.00）24.以数据集4，5，6，7，10，12，18叶结点权值所构造的哈夫曼树其带权路径长度为 1。 （分数：2.00）25.设图 G有 n个点和 e条边，以邻接表为存储结构，进行深度优先搜索的时间复杂度为 1。 （分数：2.00）26.散列查找是由键值的
7、 1 确定散列表中的位置，进行存储式查找。 （分数：2.00）27.对于 n个记录的集合进行快速排序，在最坏的情况下的时间复杂度是 1。 （分数：2.00）28.一个序列中有 10000个元素，若只想得到其中前 10个最小元素，最好采用 1 方法。 （分数：2.00）三、应用题(总题数：5，分数：30.00)29.试分别画出下图所示树的孩子链表、孩子兄弟链表。 （分数：6.00）_30.画出下图所示的树对应的二叉树。 （分数：6.00）_31.已知序列(10，18，4，3，6，12，1，9，15，8)，请给出采用二路归并排序法对该序列进行升序排序时的每一趟结果。 （分数：6.00）_32.给定
8、表(19，14，22，01，66，21，83，27，56，13，10)。试按元素在表中的次序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。并求其在等概率情况下查找成功的平均查找长度。 （分数：6.00）_33.已知如下图所示，用普里姆(Prim)算法从顶点 A开始求最小生成树。在算法执行之初，顶点的集合U=A，B，边的集合 TE=(A，B)。试按照最小生成树的生成过程，分步给出加入顶点和边以后的集合 U和 TE的值。 （分数：6.00）_四、算法设计题(总题数：2，分数：14.00)34.写出判断带头结点的单链表 L的元素值是否是递增的算法。 （分数：7.00）_35.
9、设计一个用链表表示的直接插入排序算法。 （分数：7.00）_数据结构导论自考题模拟 9答案解析(总分：100.00，做题时间：90 分钟)一、在每小题列出的四个备选项中只有一个是符合(总题数：15，分数：30.00)1.关于算法的描述，不正确的是_（分数：2.00）A.算法最终必须由计算机程序实现 B.所谓最坏时间复杂度是指最坏情况下，估算算法执行时间的一个上界C.健壮的算法不会因非法的输入数据而出现莫名其妙的运行结果D.算法的优劣与算法描述语言无关解析：2.线性表若采用链表存储结构，则要求内存中可用存储单元的地址_（分数：2.00）A.必须是连续的B.部分地址必须是连续的C.一定是不连续的D
10、.连续不连续都可以 解析：考点 本题主要考查的知识点是线性表。 由于线性表的顺序存储方式要求占用连续的空间，存储分配只能预先进行，为了克服顺序表的缺点，采用链接方式存储线性表。3.以下属于逻辑结构的是_（分数：2.00）A.顺序表B.哈希表C.有序表 D.单链表解析：考点 本题主要考查的知识点是逻辑结构。 只有有序表属于逻辑结构，其他选项都属于存储结构。本题答案为 C。4.已知循环队列的存储空间为数组 data21，且当前队列的头指针和尾指针的值分别为 8和 3，则该队列的当前长度为_（分数：2.00）A.5B.6C.16 D.17解析：5.对特殊矩阵采用压缩存储的目的主要是为了_（分数：2.
11、00）A.表达变得简单B.对矩阵元素的存取变得简单C.去掉矩阵中多余元素D.减少不必要的存储空间 解析：6.将一棵有 1000个结点的完全二叉树从根这一层开始，每一层从左到右依次对结点进行编号，根结点编号为 1，则编号最大的分支结点的编号为_（分数：2.00）A.48B.49C.50 D.51解析：考点 本题主要考查的知识点是完全二叉树。 含 n个结节的完全二叉树的分支结点个数为 n/2，最大编号的分支结点的编号也为 n/2。7.若二叉树的中序遍历序列是 abcdef，且 c为根结点，则_（分数：2.00）A.结点 c有两个孩子 B.二叉树有两个度为 0的结点C.二叉树的高度为 5D.以上都不
12、对解析：考点 本题主要考查的知识点是二叉树的遍历。 中序序列是 abcdef，则 ab为根结点 c的左子树的中序序列，def 为根结点 c的右子树的中序序列，说明结点 c既有左子树叉有右子树。故本题答案为 A。8.已知森林 F=T 1 ，T 2 ，T 3 ，T 4 ，T 5 ，各棵树 T i (i=1，2，3，4，5)中所含结点的个数分别为7、3、5、1、2，则与 F对应的二叉树的右子树中的结点个数为_（分数：2.00）A.2B.3C.8D.11 解析：考点 本题主要考查的知识点是森林与二叉树的转换。 换二叉树中右子树的结点个数为第二棵至第五棵树中结点之和。故本题答案为 D。9.在具有 6个顶
13、点的无向图 G至少应有多少条边才能确保是一个连通图_（分数：2.00）A.8B.7C.6D.5 解析：10.一个具有 n个顶点的无向图，若采用邻接矩阵表示，则该矩阵的大小是_ A.n-1 B.n+1 C.n2 D.(n+1)2（分数：2.00）A.B.C. D.解析：11.索引顺序表的索引表在组织形式上是一个_（分数：2.00）A.顺序表 B.单链表C.队列D栈解析：12.静态查找表的运算包括_（分数：2.00）A.建表B.建表和查找C.查找和读表元D.建表、查找和读表中元表 解析：考点 本题主要考查的知识点是静态查找表的运算。 静态查找表是以具有相同特性的数据元素集合为逻辑结构，包括以下三种
14、基本运算：建表、查找和读表中元素。13.设散列表长 m=13，散列函数 h(key)=key%11。表巾已有 4个结点：h(15)=4，h(27)=5，h(39)=6，h(51)=7，其余地址为空，若采用二次探测法处理冲突，则关键字为 49的结点地址是_（分数：2.00）A.3B.5C.8D.9 解析：考点 本题主要考查的知识点是二次探测法。 按照二次探测法，键值 key的散列地址序列为 d 0 =H(key)，d i =(d 0 +i)mod m，其中，m 为散列表的长，i=1 2 ，-1 2 ，2 2 -2 2 ， 14.下列四种排序方法中，要求附加的内存容量最大的是_（分数：2.00）A
15、.插入排序B.选择排序C.快速排序D.归并排序 解析：考点 本题主要考查的知识点是归并排序的存储开销。 归并排序算法的时间复杂度为 O(nlog 2 n)，由于要用到和待排记录等数量的数组 b来存放结果，所以实现归并排序需要附加一倍的存储开销。15.对于键值序列72，73，71，23，94，16，5，68，76，103用筛选法建堆，必须从键值为_的结点开始。（分数：2.00）A.103B.72C.94 D.23解析：考点 本题主要考查的知识点是建堆的筛选过程。 将一个初始序列建成一个堆就是一个反复“筛选”的过程。其主要过程是：首先将要排序的所有键值看成一棵完全二叉树的各个结点(这时的完全二叉树
16、并不一定具备堆的特性)，根据完全二叉树性质最后一个非终端节点是第 个元素，即对于 的结点 k i 都没有孩子结点，因此以这样的 k i 为根的子树已经是堆，所以“筛选”只需从 开始，逐步把以 二、填空题(总题数：13，分数：26.00)16.表示逻辑关系的存储结构可以有四种方式，即顺序存储方式、链式存储方式、 1 和散列存储方式。 （分数：2.00）解析：索引存储方式17.当线性表的长度变化不大，易于事先确定其大小时，为了节约存储空间，宜采用 1 作为其存储结构。 （分数：2.00）解析：顺序表18.在双链表中间插入一个结点，需要修改 1 个指针。 （分数：2.00）解析：419.一般地，将
17、1 设在链表的表头一端， 2 设在链表的表尾。 （分数：2.00）解析：栈顶 栈底20.顺序队列结构类型中有三个域：data、 1 和 2。 （分数：2.00）解析：front rear21.矩阵的非零元素个数很少的矩阵称为 1。 （分数：2.00）解析：稀疏矩阵22.在具有几个结点的完全二叉树中，结点 i(2in)的左孩子结点是 1。 （分数：2.00）解析：2i23.在 1 遍历二叉树的序列中，任何结点的子树上所有结点，都是直接跟在该结点之后。 （分数：2.00）解析：先序24.以数据集4，5，6，7，10，12，18叶结点权值所构造的哈夫曼树其带权路径长度为 1。 （分数：2.00）解析
18、：16525.设图 G有 n个点和 e条边，以邻接表为存储结构，进行深度优先搜索的时间复杂度为 1。 （分数：2.00）解析：O(n+e)26.散列查找是由键值的 1 确定散列表中的位置，进行存储式查找。 （分数：2.00）解析：散列函数值27.对于 n个记录的集合进行快速排序，在最坏的情况下的时间复杂度是 1。 （分数：2.00）解析：O(n 2 )28.一个序列中有 10000个元素，若只想得到其中前 10个最小元素，最好采用 1 方法。 （分数：2.00）解析：堆排序三、应用题(总题数：5，分数：30.00)29.试分别画出下图所示树的孩子链表、孩子兄弟链表。 （分数：6.00）_正确答
19、案：()解析：所求孩子链表、孩子兄弟链表如下图所示： 30.画出下图所示的树对应的二叉树。 （分数：6.00）_正确答案：()解析：转换后的二叉树如下图所示： 31.已知序列(10，18，4，3，6，12，1，9，15，8)，请给出采用二路归并排序法对该序列进行升序排序时的每一趟结果。 （分数：6.00）_正确答案：()解析：初始状态：(10，18，4，3，6，1 2，1，9，15，8) 1趟：10，18，3，4，6，12，1，9，8，15 2趟：3，4，10，18，1，6，9，12，8，15 3趟：1，3，4，6，9，10，12，18，8，15 4趟：1，3，4，6，8，9，10，12，15
20、，18 第 4趟归并完毕，排序结束。32.给定表(19，14，22，01，66，21，83，27，56，13，10)。试按元素在表中的次序将它们依次插入一棵初始时为空的二叉排序树，画出插入完成后的二叉排序树。并求其在等概率情况下查找成功的平均查找长度。 （分数：6.00）_正确答案：()解析：所求二叉排序树如下图所示： 33.已知如下图所示，用普里姆(Prim)算法从顶点 A开始求最小生成树。在算法执行之初，顶点的集合U=A，B，边的集合 TE=(A，B)。试按照最小生成树的生成过程，分步给出加入顶点和边以后的集合 U和 TE的值。 （分数：6.00）_正确答案：()解析：U=A，B，G TE
21、=(A，B)，(A，G) U=A，B，G，I TE=(A，B)，(A，G)，(G，I) U=A，B，G，I，E TE=(A，B)，(A，G)，(G，I)，(I，E) U=A，B，G，I，E，D TE=(A，B)，(A，G)，(G，I)，(I，E)，(E，D) U=A，B，G，I，E，D，C TE=(A，B)，(A，G)，(G，I)，(I，E)，(E，D)，(D，C) U=A，B，G，I，E，D，C，H TE=(A，B)，(A，G)，(G，I)，(I，E)，(E，D)，(D，C)，(C，H) U=A，B，G，I，E，D，C，H，F TE=(A，B)，(A，G)，(G，I)，(I，E)，(E，D)
22、，(D，C)，(C，H)，(I，F)四、算法设计题(总题数：2，分数：14.00)34.写出判断带头结点的单链表 L的元素值是否是递增的算法。 （分数：7.00）_正确答案：()解析：算法描述如下： int list_isrising(LinkList L) LinkList p，q； p=L-next； if(p=NULL)return 0； if(p-next=NULL)return 1； /单个元素是递增的 while(p-next!=NULL) q=p-next； if(q-datap-data) return 0；/单链表 L的元素值非递增 else p=q； return 1；/单链表 L的元素值是递增 35.设计一个用链表表示的直接插入排序算法。 （分数：7.00）_正确答案：()解析：void sort(DLinkList H) pre=H-next； while(p!=H) p=pre-next； q=p-next； while(pre!=H)&(p-datapre-data) pre=pre-prior； if(pre!=p-prior) p-priorr-next=p-next； p-next-prior=p-prior； p-next=pre-next； pre-next-prior=p； p-prior=pre；pre-next=p； p=q；
