【学历类职业资格】数据结构自考题-5及答案解析.doc
《【学历类职业资格】数据结构自考题-5及答案解析.doc》由会员分享,可在线阅读,更多相关《【学历类职业资格】数据结构自考题-5及答案解析.doc(14页珍藏版)》请在麦多课文档分享上搜索。
1、数据结构自考题-5 及答案解析(总分:110.00,做题时间:90 分钟)一、单项选择题(总题数:15,分数:30.00)1.对含有( )个结点的非空二叉树,采用任何一种遍历方式,其结点访问序列均相同。 AO B1 C2 D不存在这样的二叉树(分数:2.00)A.B.C.D.2.以下有关数据结构的叙述,正确的是 ( ) A线性表的线性存储结构优于链式存储结构 B二叉树的第 i 层上有 2i-1个结点,深度为 K 的二叉树上有 2k-1个结点 C二维数组是其数据元素为线性表的线性表 D栈的操作方式是先进先出(分数:2.00)A.B.C.D.3.对一棵非空二叉树进行中序遍历,则根结点的左边( )
2、A只有左子树上的所有结点 B只有右子树上的所有结点 C只有左子树上的部分结点 D只有右子树上的部分结点(分数:2.00)A.B.C.D.4.已知二叉树的中序序列和后序序列均为 ABCDEF,则该二叉树的先序序列为 ( ) AFEDCBA BABCDEF CFDECBA DFBDCEA(分数:2.00)A.B.C.D.5.树最适合用来表示( ) A有序数据元素 B无序数据元素 C元素之间具有分支层次关系的数据 D元素之间无联系的数据(分数:2.00)A.B.C.D.6.设 rear 是指向非空带头结点的循环单链表的尾指针,则删除起始结点的操作可表示为( ) As=rear; Brear=rear
3、next; rear=rearnext; free(rear); free(s); Crear=rearnextnext; Ds=rearnextnext; free(rear); rearnextnext=snext; free(s);(分数:2.00)A.B.C.D.7.判断一个有向图是否存在回路,除了可以利用拓扑排序方法,还可以利用( ) A求关键路径的方法 B求最短路径的 Dijkstra 方法 C广度优先遍历方法 D深度优先遍历方法(分数:2.00)A.B.C.D.8.线索二叉树是一种( )结构。 A物理 B逻辑 C存储 D线性(分数:2.00)A.B.C.D.9.用二叉链表表示具有
4、 n 个结点的二叉树时,值为空的指针域的个数为 ( ) An-1 Bn Cn+1 D2n(分数:2.00)A.B.C.D.10.对关键字序列(6,1,4,3,7,2,8,5)进行快速排序时,以第 1 个元素为基准的一次划分的结果为 ( ) A(5,1,4,3,6,2,8,7) B(5,1,4,3,2,6,7,8) C(5,1,4,3,2,6,8,7) D(8,7,6,5,4,3,2,1)(分数:2.00)A.B.C.D.11.如果我们采用二分查找法查找一个长度为 n 的有序表,则查找每个元素的平均比较次数( )对应的判定树的高度(假设树高 h2)。 A大于 B小于 C等于 D无法确定(分数:2
5、.00)A.B.C.D.12.在一个单链表中,已知 q 所指结点是 p 所指结点的直接前趋,若在 p,q 之间插入 s 结点,则执行( )操作。 Asnext=pnext;pnext=s; Bqnext=s;snext=p; Cpnext=snext;snext=p; Dpnext=s;snext=q;(分数:2.00)A.B.C.D.13.用数组 A0N-1存放循环队列的元素值,若其头尾指针分别为 front 和 rear,则循环队列中当前元素的个数为( ) A(rear-front+m)mod m B(rear-front+1)mod m C(rear-front-1+m)mod m D(
6、rear-front)mod m(分数:2.00)A.B.C.D.14.若用邻接矩阵表示一个有向图,则其中每一列包含的“1“的个数为 ( ) A图中每个顶点的入度 B图中每个顶点的出度 C图中弧的条数 D图中连通分量的数目(分数:2.00)A.B.C.D.15.下面程序段的时间复杂度为 ( ) for(i=0;im;i+) for(j=0;jn;j+) Aij=i*j; AO(m 2) BO(n 2) CO(m*n) DO(m+n)(分数:2.00)A.B.C.D.二、填空题(总题数:10,分数:20.00)16.广义表的深度是指 1。(分数:2.00)填空项 1:_17.有 m 个叶子结点(
7、又称外结点)的哈夫曼树,其结点总数是 1。(分数:2.00)填空项 1:_18.带有一个头结点的单链表 head 为空的条件是 1。(分数:2.00)填空项 1:_19.常用的索引顺序文件是_文件和_文件。(分数:2.00)填空项 1:_20.任意一棵具有 n 个结点的二叉树,若它有 m 个叶子,则该二叉树上度数为 1 的结点为 1 个。(分数:2.00)填空项 1:_21.散列函数的作用是: 1。(分数:2.00)填空项 1:_22.在按照顺序存储方式存储的数组中,元素 aij的存储地址应该是数组的 1 加上排在 aij前面的元素所占用的单元数。(分数:2.00)填空项 1:_23.广义表的
8、深度是指 1。(分数:2.00)填空项 1:_24.从树的根结点到树中的其余结点之间的路径 1 惟一的。(分数:2.00)填空项 1:_25.设二维数组 A1020,510按行优先存储,每个元素占 4 个存储单元,A10,5的存储地址是1000,则 A15,10的存储地址是 1。(分数:2.00)填空项 1:_三、解答题(总题数:3,分数:20.00)26.对序列(48,37,63,96,22,31,50,55,11)进行升序的堆排序,写出构建的初始(大根)堆及前两趟重建堆之后的序列状态。 初始堆: 第 1 趟: 第 2 趟:(分数:5.00)_(1)画出对表长为 13 的有序顺序表进行二分查
9、找的判定树; (2)已知关键字序列为(12,14,16,21,24,28,35,43,52,67,71,84,99),写出在该序列中二分查找 37 时所需进行的比较次数。(分数:10.00)_27.试分别画出具有 3 个结点的树和具有 3 个结点的二叉树的所有不同的形态。(分数:5.00)_四、算法阅读题(总题数:3,分数:30.00)28.写出下列程序段的输出结果。(假设此栈中元素的类型是 char) voide main( ) stack s; char x,y; InitStack(s) x=1,y=0 push(s,x); push(s,x); push(s,y); push(s,x)
10、; push(s,e); push(s,x); pop(s,x); push(s,h); while(!stackEmpty(s) pop(s,y); printf(y); prinft(x) (分数:5.00)_阅读下列算法,并回答问题: (1)设串 s=“OneWorldOneDream“,t=“One“,pos 是一维整型数组,写出算法 f32(s,t,pos)执行之后得到的返回值和 pos 中的值; (2)简述算法 f32 的功能。 int strlen(char*s); /*返回串 S 的长度*/ int index(char*st,char*t); /*若串 t 在串 st 中出现
11、,则返回在串 st 中首次出现的下标值,否则返回-1*/ int f32(char*s,char*t,int pos) int i,j,k,ls,It; Is=strlen(s); lt=strlen(t); if(ls=0| It=0)return-1; k=0; i=0; do j=index(s+i,t); if(j=0) posk+=i+j; i+=j+it; while(i+it=is return k; (分数:10.00)_二叉排序树的存储结构定义为以下类型: typedef int KeyType; typedef struct node KeyType key; /*关键字项
12、*/ InfoType otherinfo; /*其它数据项*/ struet node*lchild,*rchild; /*左、右孩子指针*/ BSTNode,*BSTree; 阅读算法 f33,并回答问题: (分数:15.00)填空项 1:_五、算法设计题(总题数:1,分数:10.00)29.写出向某个有序文件中插入一个记录的程序。(分数:10.00)_数据结构自考题-5 答案解析(总分:110.00,做题时间:90 分钟)一、单项选择题(总题数:15,分数:30.00)1.对含有( )个结点的非空二叉树,采用任何一种遍历方式,其结点访问序列均相同。 AO B1 C2 D不存在这样的二叉树
13、(分数:2.00)A.B. C.D.解析:2.以下有关数据结构的叙述,正确的是 ( ) A线性表的线性存储结构优于链式存储结构 B二叉树的第 i 层上有 2i-1个结点,深度为 K 的二叉树上有 2k-1个结点 C二维数组是其数据元素为线性表的线性表 D栈的操作方式是先进先出(分数:2.00)A.B.C. D.解析:3.对一棵非空二叉树进行中序遍历,则根结点的左边( ) A只有左子树上的所有结点 B只有右子树上的所有结点 C只有左子树上的部分结点 D只有右子树上的部分结点(分数:2.00)A. B.C.D.解析:4.已知二叉树的中序序列和后序序列均为 ABCDEF,则该二叉树的先序序列为 (
14、) AFEDCBA BABCDEF CFDECBA DFBDCEA(分数:2.00)A. B.C.D.解析:解析 对于前序遍历、中序遍历和后序遍历,将结点按其访问的先后次序排列起来,所得到的结点序列分别称为前序序列、中序序列和后序序列。5.树最适合用来表示( ) A有序数据元素 B无序数据元素 C元素之间具有分支层次关系的数据 D元素之间无联系的数据(分数:2.00)A.B.C. D.解析:6.设 rear 是指向非空带头结点的循环单链表的尾指针,则删除起始结点的操作可表示为( ) As=rear; Brear=rearnext; rear=rearnext; free(rear); free
- 1.请仔细阅读文档,确保文档完整性,对于不预览、不比对内容而直接下载带来的问题本站不予受理。
- 2.下载的文档,不会出现我们的网址水印。
- 3、该文档所得收入(下载+内容+预览)归上传者、原创作者;如果您是本文档原作者,请点此认领!既往收益都归您。
下载文档到电脑,查找使用更方便
5000 积分 0人已下载
下载 | 加入VIP,交流精品资源 |
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 学历 职业资格 数据结构 考题 答案 解析 DOC
