全国2012年1月自考《数据结构导论》试题

发布日期:2019-11-28 17:33:34 编辑整理:新疆自考网 【字体: 【学历咨询】
立即购买

《自考视频课程》名师讲解,轻松易懂,助您轻松上岸!低至199元/科!

全国2012年1月自考《数据结构导论》试题 
课程代码:02142  
一、单项选择题(本大题共15小题,每小题2分,共30分) 
在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分。 
1.结点按逻辑关系依次排列形成一条“锁链”的数据结构是(      ) 
A.集合                                                            B.线性结构  
C.树形结构                                                     D.图状结构 
2.下面算法程序段的时间复杂度为(      ) 
for ( int i=0; i<m; i++) 
for ( int j=0; j<n; j++) 
a[i][j]=i*j; 
A. O(m2)                                                        B. O(n2)   
C. O(mn)                                                        D. O(m+n)  
3.线性结构是(      ) 
A.具有n(n≥0)个表元素的有穷序列              B.具有n(n≥0)个字符的有穷序列 
C.具有n(n≥0)个结点的有穷序列                 D.具有n(n≥0)个数据项的有穷序列  
4.单链表中删除由某个指针变量指向的结点的直接后继,该算法的时间复杂度是(      )  
A. O(1)                                                           B. O( )  
C. O(log2n)                                                      D. O(n) 
5.关于串的叙述,正确的是(      )  
A.串是含有一个或多个字符的有穷序列  
B.空串是只含有空格字符的串 
C.空串是含有零个字符或含有空格字符的串 
D.串是含有零个或多个字符的有穷序列 
6.栈的输入序列依次为1,2,3,4,则不可能的出栈序列是(      ) 
A.1243                                                            B. 1432  
C. 2134                                                           D.4312 
7.队列是(      ) 
A. 先进先出的线性表                                     B. 先进后出的线性表  
C. 后进先出的线性表                                      D.随意进出的线性表 
8.10阶上三角矩阵压缩存储时需存储的元素个数为(      ) 
A.11                                                                B.56  
C.100                                                              D.101 
9.深度为k(k≥1)的二叉树,结点数最多有(      ) 
A.2k 个                                                            B.(2k -1)个  
C.2k-1个                                                         D.(2k+1)个 
10.具有12个结点的二叉树的二叉链表存储结构中,空链域NULL的个数为(      ) 
A. 11                                                              B.13   
C. 23                                                              D. 25

11.具有n个顶点的无向图的边数最多为(      ) 
A.n+1                                                              B.n(n+1)  
C.n(n-1)/2                                                       D.2n(n+1) 
12.三个顶点v1,v2,v3的图的邻接矩阵为 ,该图中顶点v3的入度为(      ) 
A. 0                                                                B. 1  
C. 2                                                                D. 3 
13.顺序存储的表格中有60000个元素,已按关键字值升序排列,假定对每个元素进行查找的概率是相同的,且每个元素的关键字值不相同。用顺序查找法查找时,平均比较次数约为(      ) 
A.20000                                                          B.30000  
C.40000                                                          D.60000 
14.外存储器的主要特点是(      ) 
A.容量小和存取速度低                                    B.容量大和存取速度低 
C.容量大和存取速度高                                    D.容量小和存取速度高 
15.在待排数据基本有序的前提下,效率最高的排序算法是(      ) 
A.直接插入排序                                              B.直接选择排序  
C.快速排序                                                     D.归并排序 
二、填空题(本大题共13小题,每小题2分,共26分) 
请在每小题的空格中填上正确答案。错填、不填均无分。 
16.数据的不可分割的最小标识单位是______,它通常不具有完整确定的实际意义,或不被当作一个整体对待。 
17.运算分为加工型运算和引用型运算,读取操作是______ 运算。 
18.带有头结点的单向循环链表L(L为头指针)中,指针p所指结点为尾结点的条件是 ______。 
19.在双链表中,前趋指针和后继指针分别为prior和next。若使指针p往后移动两个结点,则需执行语句 ______。 
20.元素s1,s2,s3,s4,s5,s6依次进入顺序栈S,如果6个元素的退栈顺序为s2,s3,s4,s6,s5,s1,则顺序栈的容量至少为 ______。 
21. 稀疏矩阵一般采用的压缩存储方法是______ 。 
22. 在一棵树中,______ 结点没有双亲。 
23.一棵具有n个结点的完全二叉树中,从树根起,自上而下、自左至右给所有结点编号。设根结点编号为1,若编号为i的结点有父结点,那么其父结点的编号为 ______。 
24.二叉树的二叉链表存储结构中判断指针p所指结点为叶子结点的条件是______。 
25.边稀疏的无向图采用 ______存储较省空间。 
26.除第一个顶点和最后一个顶点相同外,其余顶点不重复的回路,称为 ______。 
27.二分查找算法的时间复杂度是 ______。 
28.要将序列{51,18,23,68,94,70,73}建成堆,则只需把18与 ______相互交换。
三、应用题(本大题共5小题,每小题6分,共30分) 
29.将题29图所示的一棵二叉树转换成对应的森林。 
全国2012年1月自考《数据结构导论》试题(图1)  
题29图 
30.给定权值{3,9,13,5,7},构造相应的哈夫曼(Huffman)树,并计算其带权路径长度。 
31.写出题31图的邻接矩阵和每个顶点的入度与出度。

 

全国2012年1月自考《数据结构导论》试题(图2)
题31图 
32. 二叉排序树的各结点的值依次为20~28,请在题32图中标出各结点的值。 

全国2012年1月自考《数据结构导论》试题(图3)
题32图 
33.用冒泡排序法对数据序列(55,38,65,97,76,138,27,49)进行排序,写出排序过程中的各趟结果。  
四、算法设计题(本大题共2小题,每小题7分,共14分) 
34.设线性表A =(a1, a2, …,am),B=(b1, b2, …,bn),试写一个按下列规则合并A,B为线性表C的算法,使得 
C=(a1, b1, …, am ,bm ,bm+1, …,bn) 当m≤n时; 
或者         C=(a1, b1, …, an ,bn ,an+1, …,am) 当m>n时。 
线性表A,B和C均以带头结点的单链表作为存储结构,且C表利用A表和B表中的结点空间构成。(注意:单链表的长度值m和n均未显式存储。) 
35. 二叉树的二叉链表类型定义如下: 
typedef struct btnode { 
datatype data;  
struct btnode *lchild,*rchild; 
} bitreptr; 
写出后根遍历根指针为t的二叉树的递归算法( void postorder (bitreptr *t) )。 


关注新疆自考网微信公众号

其他人还看了:
免责声明

《新疆自考网》免责声明:

1、由于各方面情况的调整与变化,本网提供的考试信息仅供参考,考试信息以省考试院及院校官方发布的信息为准。

2、本网信息来源为其他媒体的稿件转载,免费转载出于非商业性学习目的,版权归原作者所有,如有内容与版权问题等请与本站联系。联系邮箱:812379481@qq.com。

新疆自考-便捷服务