资源描述：
《自学考试-数据结构导论自考题模拟3》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、数据结构导论自考题模拟3一、单项选择题在每小题列出的四个备选项中只有一个是符合题目要求的。丄、下列说法正确的是（）A・数据是数据元素的基木单位B.数据元素是数据项屮不可分割的最小标识单位C.数据可由若干个数据元素构成D.数据项可由若干个数据元素构成2、下面关于线性表的叙述，错误的是（）A・顺序表是使用一维数组实现的线性表B・顺序表必须占用一片连续的存储单元C・顺序表的空间利用率高于链表D.在链表中，每个结点只有一个链域3、带有头结点的单链表head为空的判断条件是（）A.head=NULLB・head->next=NULLC・head->next=headD・head!=NULL4
2、、一个栈的输入序列为123...n,若输出序列的第一个元素是n,则输出第个元素是（A.不确定B・n-i+1C・iD・n-i5、用链接方式存储的队列，在进行删除运算时*（）A.仅修改头指针B.仅修改尾指针C.头、尾指针都要修改D.头、尾指针可能都要修改6、如图所示二叉树的中序遍历序列是（）7、满二叉树（）二叉树。A.一定是完全B.不一定是完全C.不是D.不是完全8、某有向图的邻接矩阵A如下，则该图中弧的条数是（）•01］】00J0】.0••A・5B・4C・3D.29、设某无向图的邻接表如题9图所示，则该图的边的数目是（）vfiv.t■■2'11:13；32A■4A・4AA.4B.5C
3、・10D・2010、一个有序表为（1,3,9,12,32,41,45,62,75,77,82,95,100）,当二分查找值为82的结点吋，查找成功吋的比较次数为（）A・1B.2C・4D・811>一个具有n个顶点的无向连通图，它所包含的连通分量数为（）A・0B・1C.nD.不确定12、在散列函数H（k）=kmodm中，一般来讲，m应取（）A.奇数B.偶数C.素数D.充分大的数13.排序算法中，第一趟排序后，任一元素都不能确定其最终位置的算法是（）A・选择排序B.插入排序C.冒泡排序D.快速排序丄4、排序趟数与序列的原始状态有关的排序方法是（）A.插入排序法B.选择排序法C.二路归并排
4、序法D.快速排序法15、下列排序方法中，属于稳定的排序方法是（）A.直接选择排序法B•快速排序法C.冒泡排序法D・堆排序法二、填空题16、从逻辑关系上讲，数据结构主耍分为两大类，它们是和17、以下程序段的吋间复杂度为for（i=0；iprior->next=q->next；若要删除指针q所指向的结点,19、线性表中结点具有的关系。20、队列中允许进行删除的一端为o21、二维数组A[10][20]采用按行为主序的存储方式，每个元素占4
5、个存储单元，若A[0][0]的存储地址为300,则A[0][10]的地址为o22树的遍历主要右先序遍历、后序遍历和二种。23、深度为k的完全二叉树至少有个结点。24、有向图的极大强连通子图称为。25、对于有向图，第i个单链表中的结点个数为顶点匚的o26、是对每一个同义词都建一个单链表来解决冲突。27、在待排序的n个记录中任取一个记录，以该记录的键值作为标准，将所有记录分为两组，使得第一组屮各记录的键值均小于或等于该键值，第二组屮的各记录的键值均大于该键值；然后将该记录排在两组中间。再对所分成的两组分别使用上述方法，直到所有记录都排在适当位置为止。这种排序方法称为O28、在对一组记录
6、关键字(54,38,96,23,15,72,60,45,83)进行冒泡排序时，整个冒泡排序过程中需进行趟才能完成。三、应用题29、设有一顺序队列sq,容量为5,初始状态吋sq.front=sq.rear=0,画出做完下列操作后队列及其头尾指针的状态变化情况，若不能入队，请简述其理由后停止。⑴d,e,b入队(2)d,e出队(3)i,j入队(4)b出队(2)n,o,p入队30、分别写岀下图中树的先序、后序和层次遍历的结点访问序列。h:31、有一棵二叉树如图所示，试画出它的顺序存储结构示意图。32、试给出下图的邻接矩阵和邻接表表示。33、已知一组键值序列(丄3,12,16,17,15,1
7、4,11),试釆用二路归并排序法对该组序列作升序排序，并给出每一趟的排序结果。四、算法设计题34、试编写算法判断两棵二叉树是否等价。若二叉树口和T2等价，则口和T2都是空的二叉树，或口和空的根结点的值相同，并且口的左子树与玛的左子树是等价的，口的右子树与T2的右子树是等价的。35、试写岀二分查找的递归算法。答案:一.单项选择题2^D［解析］本题主要考查的知识点是线性表。［要点透析］顺序表是用一维数组实现的线性表，数组的下标可看成元素的相对地址，它们是逻辑上相邻的元素，
