以下为《数据结构导论自考题模拟1》的无排版文字预览，完整格式请下载

下载前请仔细阅读文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。

数据结构导论自考题模拟1

一、单项选择题

? ?在每小题列出的四个备选项中只有一个是符合题目要求的。

1、要将现实生活中的数据转换为计算机所能表示的形式，其转移过程为( ? ?)

? ?A．原始数据、存储结构、逻辑结构 ? ?B．原始数据、逻辑结构、存储结构

? ?C．逻辑结构、存储结构、原始数据 ? ?D．逻辑结构、原始数据、存储结构

2、算法在发生非法操作时可以作出处理的特性称为( ? ?)

? ?A．正确性 ? ?B．易读性

? ?C．健壮性 ? ?D．时空性

3、下列算法的时间复杂度是( ? ?)

? ?for(i=0, j=0; i＜n; i++)

? ?c[i][j]=i+j;

? ?A．O(1) ? ?B．O(n)

? ?C．O(log2n) ? ?D．O(n2)

4、设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为( ? ?)

? ?A．5 ? ?B．6

? ?C．7 ? ?D．9

5、在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，该指针域用于存放一个指针，此指针指向该结点的( ? ?)

? ?A．直接前驱 ? ?B．直接后继

? ?C．开始结点 ? ?D．终端结点

6、对于一个具有n个元素的线性表，建立其单链表的最小时间复杂度为( ? ?)

? ?A．O(log2n) ? ?B．O(1)

? ?C．O(n2) ? ?D．O(n)

7、在循环链表的一个结点中有( ? ?)个指针。

? ?A．1 ? ? ?B．2

? ?C．0 ? ?D．3

8、栈和队列共同具有的特点是( ? ?)

? ?A．都是先进后出 ? ?B．都是先进先出

? ?C．只允许在端点进行操作运算 ? ?D．既能先进先出，也能先进后出

9、队列通常采用的两种存储结构是( ? ?)

? ?A．顺序存储结构和链式存储结构 ? ?B．散列方式和索引方式

? ?C．链表存储结构和数组 ? ?D．线性存储结构和非线性存储结构

10、一个栈的输入序列是12345，则下列序列中不可能是栈的输出序列的是( ? ?)

? ?A．23415 ? ?B．54132

? ?C．23145 ? ?D．15432

11、一个队列的输入序列是abcd，则队列的输出序列是( ? ?)

? ?A．acdb ? ?B．abcd

? ?C．adcb ? ?D．cbda

12、数组A[0…5，0…6]每个元素占5个单元，将其按列优先次序存储在起始地址为1000的连续内存单元中，则元素a[5][5]的地址为( ? ?)

? ?A．1175 ? ?B．1180

? ?C．1205 ? ?D．1210

13、按照二叉树的定义，具有3个结点的二叉树有( ? ?)

? ?A．3利 ? ?B．4种

? ?C．5种 ? ?D．6种

14、在一棵二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序( ? ?)

? ?A．都不相同

? ?B．完全相同

? ?C．先序序列和中序序列相同，而与后序序列不同

? ?D．中序序列和后序序列相同，而与先序序列不同

15、深度为6的二叉树最多拥有的结点数目是( ? ?)

? ?A．64 ? ?B．63

? ?C．32 ? ?D．31

二、填空题

16、数据的基本单位是______。

17、所有结点按一对一的邻接关系构成的整体就是______结构。

18、双向循环链表找前驱结点和后继结点的时间复杂度为______。

19、顺序表定位运算的基本操作是______。

20、带头结点的双向循环链表L为空的条件是______。

21、单链表表示法的基本思想是用______表示结点间的逻辑关系。

22、在一个用一维数组A[N]表示的循环队列中，该队列中的元素个数最少为______个，最多为______个。

23、在栈中，可进行插入和删除操作的 内容过长，仅展示头部和尾部部分文字预览，全文请查看图片预览。 2，T1与T2都是二叉树，并且T1与T2有顺序关系(T1在T2之前)。由此可知，3个结点的二叉树有5种。

14、B

[解析] 本题主要考查的知识点是在二叉树遍历中对叶子结点的访问顺序。

[要点透析] 显然遍历方法中的先序、中序、后序指的是对根的访问顺序，而对于叶子结点都采用先遍历左某某，后遍历右子树。

15、B

[解析] 本题主要考查的知识点是二叉树的性质。

[要点透析] 深度为k(k≥1)的二叉树至多有2k-1个结点。

二、填空题

16、数据元素 　 　 17、线性 　 　 18、O(1) 　 　 19、比较 　 　 20、(L-＞next==L)&&(L-＞prior==L) 　 　 21、指针 　 　 22、O ?N-1 　 　 23、栈顶 　 　 24、特殊矩阵 　 　 25、压缩存储 　 　 26、 　 　 27、12 　 　 28、n+1 　 　

三、应用题

29、满足条件的序列是：CDEBA，CDBEA，CDBAE。 　 　 30、逻辑结构反映数据元素之间的逻辑关系，而存储结构是数据结构在计算机中的表示，它包括数据元素的表示及其关系的表示。一种逻辑结构可以采用一种或几种存储方式来表达数据元素之间的逻辑关系，相应的存储结构称为给定逻辑结构的存储实现或存储映像。 　 　 31、一般地，运算是指在任何逻辑结构上施加的操作，即对逻辑结构的加工。一个运算的实现是指一个完成该运算功能的程序。

? ?相同点：运算与运算的实现都能完成对数据的“处理”或某种特定的操作。

? ?不同点：运算只描述处理功能，不包括处理步骤和方法，而运算实现的核心是处理步骤的规定，即算法没计。 　 　 32、(1)二叉链表示意图

? ?http://doc.001pp.com/newyfB12/tu/1304/zhl/zk/j/sjd11.9727CD.jpg

? ?(2)三叉链表示意图

? ?http://doc.001pp.com/newyfB12/tu/1304/zhl/zk/j/sjd11.979481.jpg

? ?(3)顺序存储结构爪意图

? ?http://doc.001pp.com/newyfB12/tu/1304/zhl/zk/j/sjd11.97D795.jpg 　 　 33、所求哈夫曼树如图所示：

? ?http://doc.001pp.com/newyfB12/tu/1304/zhl/zk/j/sjd11.98A092.jpg 　 　

四、算法设计题

34、算法如下：

? ?int count(head)

? ?Node * head;

? ?{

? ?Node * p;

? ?int n=0;

? ?p=head

? ?while ( p ! = NULL)

? ?{

? ? ?if (p-＞data=='D') n++;

? ? ?p=p-＞next;

? ?}

? ?return(n);

? ?} 　 　 35、本算法的基本思想是：先求左某某的叶子数，再求右子树的叶子数，两者相加就是根结点的叶子数，也就是对应二叉树的叶子数、

? ?int leafcount(BinTree T)

? ?//求二叉树T的叶子数

? ?{ if(T==NULL) leaf=0;

? ?//当二叉树为空时, 叶子数等于0

? ?else if((T-＞lchild==NULL)&&(T-＞

? ?rchild==NULL)) leaf=1;

? ?//当二叉树仅含一个根结点时, 叶子数为1

? ?else{ L==leafcount(T-＞lchild);

? ?//求左某某的叶子数

? ?R=leafcount(T-＞rchild);

? ?//求右子树的叶子数

? ?leaf=L+R;

? ?//左、右子树叶子数之和等于二叉树的叶子数

? ?}

? ?return(leaf);

? ?} 　 　

[文章尾部最后300字内容到此结束,中间部分内容请查看底下的图片预览]请点击下方选择您需要的文档下载。

1. 【最新版】华为岗位晋升制度
2. 加大高校党员发展工作的力度_改善党员结构_壮大党员队伍_陈某某
3. 公共基础知识点精简版
4. 数据结构_32学时教学大纲
5. --2数据结构复习大纲
6. 复习提纲_6月＿测绘工程
7. 吉大算法题汇总（C语言版）
8. 数据结构讨论题无答案
9. 硕士研究生入学考试自命题科目 考试大纲
10. 计算机二级公共基础考点 1
11. 考研作文规范
12. 工大834考试大纲
13. 小蝌蚪找妈妈 教学设计
14. 《数据结构(c语言版)》知识点概括
15. 1_《机械基础》课程报告任务书
16. 《数据结构》考试大纲
17. 蛋白质 教学设计
18. 计算机等级考试公共基础知识超强总结，栈、队列、树

以上为《数据结构导论自考题模拟1》的无排版文字预览，完整格式请下载

下载前请仔细阅读上面文字预览以及下方图片预览。图片预览是什么样的，下载的文档就是什么样的。