全国2012年1月自学考试数据结构试题.DOC

1、自考人网校专本套读 2018 春季招生进行中，零学历 2.5 年拿本科，支持学费分期，0 利率 0 手续费！应用市场搜索“自考人”下载自考 APP 神器，随时随地无忧备考，自测练习强化巩固，考试重点轻松装进口袋！全国 2012 年 1 月自学考试数据结构试题课程代码：02331一、单项选择题(本大题共 15 小题，每小题 2 分，共 30 分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。1.每个结点有且仅有一个直接前趋和多个(或无) 直接后继 (第一个结点除外)的数据结构称为（ ）A.树状结构 B.网状结构C.线性结构 D.层次结构

2、2.某线性表中最常用的操作是在最后一个元素之后插入元素和删除第一个元素，则最节省运算时间的存储结构是（ ）A.单链表 B.双链表C.仅有头指针的单循环链表 D.仅有尾指针的单循环链表3.已知一个栈的入栈序列是 1，2，3，n，其输出序列为 pl，p 2，p 3.，p n，若 p1 是 n，则 pi 是（ ）A.i B.n-iC.n-i+l D.不确定4.下面关于串的叙述中，正确的是（ ）A.串是一种特殊的线性表 B.串中元素只能是字母C.空串就是空白串 D.串的长度必须大于零5.无向完全图 G 有 n 个结点，则它的边的总数为（ ）A.n2 B.n(n-1)自考人网校专本套读 2018 春季招

3、生进行中，零学历 2.5 年拿本科，支持学费分期，0 利率 0 手续费！应用市场搜索“自考人”下载自考 APP 神器，随时随地无忧备考，自测练习强化巩固，考试重点轻松装进口袋！C.n(n-1)/2 D.(n-1)6.若一棵二叉树有 10 个 度为 2 的结点，5 个度为 1 的结点，则度为 0 的结点数是（ ）A.9 B.11C.15 D.不确定7.如图所示，在下面的 4 个序列中，不符合深度优先遍历的序列是（ ）A.acfdebB.aebdfcC.aedfbcD.aefdbc8.无论待排序列是否有序，排序算法时间复杂度都是 O(n2)的排序方法是（ ）A.快速排序 B.归并排序C.冒泡排序

4、D.直接选择排序9.已知二叉排序树 G，要输出其结点的有序序列，则采用的遍历方法是（ ）A.按层遍历 B.前序遍历C.中序遍历 D.后序遍历10.用 ISAM 和 VSAM 组织的文件都属于（ ）A.散列文件 B.索引顺序文件C.索引非顺序文件 D.多关键字文件11.对序列(15，9，7，8，20， -1，4)进行排序，第一趟排序后的序列变为(4，9，-1 ，8，20，7，15)，则采用的排序方法是（ ）A.选择 B.快速C.希尔 D.冒泡12.当采用分块查找时，数据的组织方式为（ ）A.数据分成若干块，每块内数据有序B.数据分成若干块，每块中数据个数必须相同C.数据分成若干块，每块内数据有序

5、，块间是否有序均可D.数据分成若干块，每块内数据不必有序，但块间必须有序13.下述编码中不是前缀码的是（ ）A.(00， 01，10 ，11) B.(0，1，00，11) C.(0，10，110，111) D.(1，01，000，001)14.若一个栈以向量 V1.n存储，初始栈顶指针 top 为 n+l，则 x 进栈的正确操作是（ ）A.top=top-1；Vtop=x B.Vtop=x；top=top+1自考人网校专本套读 2018 春季招生进行中，零学历 2.5 年拿本科，支持学费分期，0 利率 0 手续费！应用市场搜索“自考人”下载自考 APP 神器，随时随地无忧备考，自测练习强化巩固

6、，考试重点轻松装进口袋！C.top=top+1；Vtop=x D.Vtop=x；top=top-115.在一个以 head 为头结点指针的非空单循环链表中，指针 p 指向链尾结点的条件是（ ）A.p - data = - 1 B.p - next = NULLC.p - next - next=head D.p - next = head二、填空题(本大题共 10 小题，每小题 2 分，若有两个空格，每个空格 1 分，共 20 分) 请在每个空格中填上正确答案。错填、不填均无分。16.在数据的逻辑结构和存储结构中，与计算机无关的是_。17.线性表 L=(a1,a2,，an)用数组表示，假定删除

7、表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是_。18.设循环队列的容量为 50(序号从 0 到 49)，现经过一系列的入队和出队运算后，有front=11，rear=29； front=29，rear=11；在这两种情况下，循环队列中的元素个数分别是_和_。19.设 T 和 P 是两个给定的串，在 T 中寻找等于 P 的子串的过程称为_。20.已知三对角矩阵 A1010的每个元素占 2 个单元，现将其三条对角线上的元素逐行存储在起始地址为 1000 的连续的内存单元中，则元素 A67 的地址为_。21.若以(4，5，6，7，8)作为叶子结点的权值构造哈夫曼树，则其带权路径长度

8、是 _。22.有向图 G 如图所示，它的两个拓扑排序序列分别为 _和_。23.一组记录的关键字为 (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) 进行降序的堆排序，写出构建的初始堆 (小根堆)及前两趟重建堆之后序列状态。初始堆：第一趟：第二趟：27.设散列函数为

9、 H (key)=key 11，散列地址空间为 010，对关键字序列(27，13，55，32，18，49， 24，38，43) 用线性探查法解决冲突，构建散列表。现已有前 4 个关键字构建的散列表如下所示，请将剩余 5 个关键字填入表中相应的位置。自考人网校专本套读 2018 春季招生进行中，零学历 2.5 年拿本科，支持学费分期，0 利率 0 手续费！应用市场搜索“自考人”下载自考 APP 神器，随时随地无忧备考，自测练习强化巩固，考试重点轻松装进口袋！28.已知一棵二叉树的前序遍历和中序遍历序列分别为：ABCDEFG 和 CBDAEGF，请画出此二叉树，并给出后序遍历序列。29.已知如图所

10、示的带权无向图，请画出用普里姆算法从顶点 1 开始的最小生成树的构造过程。四、算法阅读题(本大题共 4 小题，每小题 5 分，共 20 分)30.阅读下列算法，并回答下列问题：(1)简述该算法的功能；(2)写出分别输入字符串：“abcba“ 和“abcbde“，调用算法函数的返回值。int symmetry(void) int i=0,j,k； .char str80；SeqStack s；InitStack(jRmid.key) (1) ；else (2) ；for (i=*n；i=low；i-)Ri+1=Ri；(3) ； +(*n)；(1)(2)(3)32.阅读下列算法，并回答下列问题：(

11、1)简述该算法中标号 s1 所指示的循环语句的功能；(2)简述该算法中标号 s2 所指示的循环语句的功能。LinkList Insertmnode(LinkList head，char x，int m)LinkNode*p，*q ，*s;int i; char ch；p=head-next；s1：while (pk-)if (Rk.keyRk+l.key)Rn+1=Rk；for (i=k+1；Ri.keyRn+1.key;i+)Ri-1=Ri;Ri-l=Rn+1；(1)(2)五、算法设计题(本题 10 分)34.假设以单链表表示线性表，单链表的类型定义如下：自考人网校专本套读 2018 春季招生进行中，零学历 2.5 年拿本科，支持学费分期，0 利率 0 手续费！应用市场搜索“自考人”下载自考 APP 神器，随时随地无忧备考，自测练习强化巩固，考试重点轻松装进口袋！typedef struct node DataType data；Struct node *next； LinkNode，* LinkList；编写算法，在一个头指针为 head 且带头结点的单链表中，删除所有结点数据域值为 x 的结点。函数原型为：LinkList delnode (LinkList head，DataType x)