全国2012年1月自考数据结构导论考试试题-答案-笔记.doc

《全国2012年1月自考数据结构导论考试试题-答案-笔记.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、全国2012年1月高等教育自学考试数据结构导论试题课程代码：02142一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.结点按逻辑关系依次排列形成一条“锁链”的数据结构是(B)A.集合B.线性结构C.树形结构D.图状结构（任意两个结点可以邻接的结构）2.下面算法程序段的时间复杂度为(C)for(inti=0;i

2、n≥0）个表元素的有穷序列B.具有n（n≥0）个字符的有穷序列C.具有n（n≥0）个结点的有穷序列D.具有n（n≥0）个数据项的有穷序列4.单链表中删除由某个指针变量指向的结点的直接后继，该算法的时间复杂度是(D)注：1.插入与删除运算，顺序表与线性表的时间复杂度都为O（n）。2.查找运算，顺序表的时间复杂度为O（1）单列表的时间复杂度为O（n）A.O(1)B.O()C.O(log2n)D.O(n)5.关于串的叙述，正确的是(D)A.串是含有一个或多个字符的有穷序列B.空串是只含有空格字符的串C.空串是含有零个字符或含有空格字符的串注：空串不等于空格串D.串是含有零个或多个字符的有穷序列

3、6.栈的输入序列依次为1，2，3，4，则不可能的出栈序列是(D)A.1243B.1432C.2134D.4312(不符合后进先出原则)7.队列是(A)A.先进先出的线性表B.先进后出的线性表（栈）C.后进先出的线性表D.随意进出的线性表8.10阶上三角矩阵压缩存储时需存储的元素个数为(B)A.11B.56C.100D.1019.深度为k（k≥1）的二叉树，结点数最多有(B)A.2k个B.(2k-1)个C.2k-1个D.(2k+1)个10.具有12个结点的二叉树的二叉链表存储结构中，空链域NULL的个数为(B)A.11B.13注：孩子有n-1个，空子域有n+1个，指针域有2n个。C.23D

4、.2511.具有n个顶点的无向图的边数最多为(C)A.n+1B.n(n+1)C.n(n-1)/2D.2n(n+1)12.三个顶点v1,v2,v3的图的邻接矩阵为，该图中顶点v3的入度为(B)A.0B.1C.2D.313.顺序存储的表格中有60000个元素，已按关键字值升序排列，假定对每个元素进行查找的概率是相同的，且每个元素的关键字值不相同。用顺序查找法查找时，平均比较次数约为(B)A.20000B.30000C.40000D.6000014.外存储器的主要特点是(B)A.容量小和存取速度低B.容量大和存取速度低C.容量大和存取速度高D.容量小和存取速度高15.在待排数据基本有序的前提下

5、，效率最高的排序算法是(A)A.直接插入排序B.直接选择排序C.快速排序D.归并排序二、填空题(本大题共13小题，每小题2分，共26分)请在每小题的空格中填上正确答案。错填、不填均无分。16.数据的不可分割的最小标识单位是__数据项____，它通常不具有完整确定的实际意义，或不被当作一个整体对待。17.运算分为加工型运算和引用型运算，读取操作是__引用____运算。18.带有头结点的单向循环链表L（L为头指针）中，指针p所指结点为尾结点的条件是_p->next=L_____。19.在双链表中，前趋指针和后继指针分别为prior和next。若使指针p往后移动两个结点，则需执行语句_P=P-

6、>next->next____。注：1.向一个栈顶指针hs的栈中插入一个*s指针，须执行的操作为；s->next=hs;hs=s;2.单列表中指针p要删除其后面的A结点（直接后继）需要执行的操作为：p->next=p->next->next（下一个下一个原则）20.元素s1，s2，s3，s4，s5，s6依次进入顺序栈S，如果6个元素的退栈顺序为s2，s3，s4，s6，s5，s1，则顺序栈的容量至少为_3_____。21.稀疏矩阵一般采用的压缩存储方法是_三元组表_____。22.在一棵树中，___根___结点没有双亲。23.一棵具有n个结点的完全二叉树中，从树根起，自上而下、自左至右给所

7、有结点编号。设根结点编号为1，若编号为i的结点有父结点，那么其父结点的编号为__i/2__。注：左孩子：为2i，，右孩子为2i+1.1.序列中不能重复出现的路径叫简单路径。2.第一个顶点和最后一个顶点相同的路径称为回路或环。24.二叉树的二叉链表存储结构中判断指针p所指结点为叶子结点的条件是_（p->lchild=Null）&&（p->rchild=Null）_____。25.边稀疏的无向图采用__邻接表___存储较省空间。注：有向