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

《自学考试-数据结构导论自考题模拟1》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、数据结构导论自考题模拟1一、单项选择题在每小题列出的四个备选项中只有一个是符合题目要求的。丄、要将现实生活中的数据转换为计算机所能表示的形式，其转移过程为（）A・原始数据、存储结构、逻辑结构B.原始数据、逻辑结构、存储结构C.逻辑结构、存储结构、原始数据D.逻辑结构、原始数据、存储结构2、算法在发生非法操作时可以作出处理的特性称为（）A・正确性B.易读性C.健壮性D.时空性3、下列算法的时间复杂度是（）for（i=0,j=0;i

2、n）D・0（/）4、设顺序表有9个元素，则在第3个元素前插入一个元素所需移动元素的个数为（）A・5B・6C・7D・95、在单链表中，存储每个结点需要有两个域，一个是数据域，另一个是指针域，该指针域用于存放一个指针，此指针指向该结点的（）A.直接前驱B.直接后继C.开始结点D.终端结点6、对于一个具有n个元素的线性表，建立其单链表的最小时间复杂度为（）A.0（log2n）B・0（1）C・。（心D.0（n）7、在循环链表的一个结点中有（）个指针。A・1B.2C・0D・38、栈和队列共同具有的特点是（）A・都是

3、先进后LbB.都是先进先LL1C.只允许在端点进行操作运算D.既能先进先出，也能先进后出9、队列通常采用的两种存储结构是（）A.顺序存储结构和链式存储结构B.散列方式和索引方式C.链表存储结构和数组D.线性存储结构和非线性存储结构10、一个栈的输入序列是12345,则下列序列中不可能是栈的输出序列的是（）A.23415B・54132C.23145D・1543211>一个队列的输入序列是abed,则队列的输出序列是（）A.aedbB・abedC-adcbD・cbda12、数组A[0...5,0...6]每个

4、元素占5个单元，将其按列优先次序存储在起始地址为1000的连续内存单元中，则元素a[5][5]的地址为（）A.1175B.1180C.1205D・121013.按照二叉树的定义，具有3个结点的二叉树有（）A・3利B.4种C.5种D.6种丄4、在一棵二叉树结点的先序序列、中序序列和后序序列中，所有叶子结点的先后顺序（）A.都不相同B.完全相同C.先序序列和中序序列相同，而与后序序列不同D.中序序列和后序序列相同，而与先序序列不同15、深度为6的二叉树最多拥有的结点数目是（）A.64B.63C・32D・31二

5、、填空题16、数据的基木单位是o17、所有结点按一对一的邻接关系构成的整体就是结构。18、双向循环链表找前驱结点和后继结点的时间复杂度为。19、顺序表定位运算的基本操作是。20、带头结点的双向循坏链表L为空的条件是。21、单链表表示法的基本思想是用表示结点间的逻辑关系。22、在一个用一维数组A[N]表示的循环队列中，该队列中的元素个数最少为个，最多为个。23、在栈中，可进行插入和删除操作的一端称为o24、是指非零元素或零元素的分布有一定规律的矩阵。25、多个值相同的元素只分配一个存储空间，零元素不分配空间

6、，称为o26、具有10个叶子结点的二叉树中有个度为2的结点。27、已知一棵度为3的树有2个度为1的结点，3个度为2的结点，4个度为3的结点，则该树有个叶子结点。28、设F是一个森林，B是由F转换得到的二叉树。若F中有n个非终端结点，贝1拒中右指针域为空的结点有个。三、应用题29、有5个元素，其入栈次序为：A,B,C,D,E,在各种可能的出栈次序中，以元素C,D最先出栈（即C第一个且D第二个出栈）的次序有哪几个？30、逻辑结构与存储结构是什么关系？31、运算与运算的实现是什么关系？有哪些相同点和不同点？32

7、、分别画出题图所示二叉树的二叉链表、三叉链表和顺序存储结构。33、给定权值7,18,3,32,5,26,12,8,构造相应的哈夫曼树。四、算法设计题34、设某单链表中，存在多个结点其数据值均为D,试编写一算法统计该类结点的个数。35、以二叉链表作为存储结构，试编写求二叉树中叶子数的算法。答案：一、单项选择题1>B［解析］本题主要考查的知识点是计算机解决问题的步骤。［要点透析］在数学模型中，需要把原始数据按照某种方式组织起来，以便很好地体现数据之间的关系，数据及数据的组织方式称为数据的逻辑结构。为了能用计算

8、机加工处理，逻辑结构还必须转换为能被计算机存储的存储结构。2、C［解析］本题主要考查的知识点是算法的健壮性。［要点透析］算法的健壮性是指即使输入非法数据，算法也能适当地做岀反应或进行处理，不会产生预料不到的运行结果。3、B4、C［解析］木题主要考查的知识点是插入算法。［要点透析］插入算法的基本步骤是：①将结点ai，飭各后移一位以便腾出第i个位置；②将x置入该空位；③表长加一。5、B［解析］本题主要考查的知识点是单链表中的指针域