2012年1月自考数据结构试题真题

《2012年1月自考数据结构试题真题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、全国2012年1月高等教育自学考试数据结构试题课程代码：02331一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.每个结点有且仅有一个直接前趋和多个(或无)直接后继(第一个结点除外)的数据结构称为（）A.树状结构B.网状结构C.线性结构D.层次结构2.某线性表中最常用的操作是在最后一个元素之后插入元素和删除第一个元素，则最节省运算时间的存储结构是（）A.单链表B.双链表C.仅有头指

2、针的单循环链表D.仅有尾指针的单循环链表3.已知一个栈的入栈序列是1，2，3，…，n，其输出序列为pl，p2，p3….，pn，若p1是n，则pi是（）A.iB.n-iC.n-i+lD.不确定4.下面关于串的叙述中，正确的是（）A.串是一种特殊的线性表B.串中元素只能是字母C.空串就是空白串D.串的长度必须大于零5.无向完全图G有n个结点，则它的边的总数为（）A.n2B.n(n-1)C.n(n-1)/2D.(n-1)6.若一棵二叉树有10个度为2的结点，5个度为1的结点，则度为0的结点数是（）A.9

3、B.11C.15D.不确定7.如图所示，在下面的4个序列中，不符合深度优先遍历的序列是（）A.acfdebB.aebdfcC.aedfbcD.aefdbc8.无论待排序列是否有序，排序算法时间复杂度都是O(n2)的排序方法是（）A.快速排序B.归并排序C.冒泡排序D.直接选择排序9.已知二叉排序树G，要输出其结点的有序序列，则采用的遍历方法是（）A.按层遍历B.前序遍历C.中序遍历D.后序遍历10.用ISAM和VSAM组织的文件都属于（）A.散列文件B.索引顺序文件C.索引非顺序文件D.多关键字文

4、件11.对序列(15，9，7，8，20，-1，4)进行排序，第一趟排序后的序列变为(4，9，-1，8，20，7，15)，则采用的排序方法是（）A.选择B.快速C.希尔D.冒泡12.当采用分块查找时，数据的组织方式为（）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块中数据个数必须相同C.数据分成若干块，每块内数据有序，块间是否有序均可D.数据分成若干块，每块内数据不必有序，但块间必须有序13.下述编码中不是前缀码的是（）A.(00，01，10，11)B.(0，1，00，11)C.(0，1

5、0，110，111)D.(1，01，000，001)14.若一个栈以向量V[1..n]存储，初始栈顶指针top为n+l，则x进栈的正确操作是（）A.top=top-1；V[top]=xB.V[top]=x；top=top+1C.top=top+1；V[top]=xD.V[top]=x；top=top-115.在一个以head为头结点指针的非空单循环链表中，指针p指向链尾结点的条件是（）A.p->data=-1B.p->next=NULLC.p->next->next=headD.p->next=h

6、ead二、填空题(本大题共10小题，每小题2分，若有两个空格，每个空格1分，共20分)请在每个空格中填上正确答案。错填、不填均无分。16.在数据的逻辑结构和存储结构中，与计算机无关的是______。17.线性表L=(a1,a2,…，an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是______。18.设循环队列的容量为50(序号从0到49)，现经过一系列的入队和出队运算后，有①front=11，rear=29；②front=29，rear=11；在这两种情况下

7、，循环队列中的元素个数分别是______和______。19.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为______。20.已知三对角矩阵A[10][10]的每个元素占2个单元，现将其三条对角线上的元素逐行存储在起始地址为1000的连续的内存单元中，则元素A[6][7]的地址为______。21.若以(4，5，6，7，8)作为叶子结点的权值构造哈夫曼树，则其带权路径长度是______。22.有向图G如图所示，它的两个拓扑排序序列分别为______和______。23.一组记录的关键字

8、为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为______。24.已知广义表A=(x，((a，b)，c，))，函数head(head(tail(A)))的运算结果是______。25.索引顺序文件既可以顺序存取，也可以______。三、解答题(本大题共4小题，每小题5分，共20分)26.对关键字序列(26，18，60，14，7，45，13，32)进行降序的堆排序，写出构建的初始堆(小根堆)及前两趟重建堆之后序列状态。初始堆：第