数据结构参考答案解析

数据结构参考答案解析

ID:39798351

大小:167.00 KB

页数:15页

时间:2019-07-11

数据结构参考答案解析_第1页
数据结构参考答案解析_第2页
数据结构参考答案解析_第3页
数据结构参考答案解析_第4页
数据结构参考答案解析_第5页
资源描述:

《数据结构参考答案解析》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、《数据结构》模拟卷A一、选择题1.在一个长度为n的顺序表的任一位置插入一个新元素的渐进时间复杂度为(A)。A.O(n)B.O(n/2)C.O(1)D.O(n2)2.带头结点的单链表first为空的判定条件是:(B)。A.first==NULL;B.first->link==NULL;C.first->link==first;D.first!=NULL;3.从逻辑上可以把数据结构分为(C)两大类。A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、非线性结构D.初等结构、构造型结构4.在系统实现递归调用时需利用递归

2、工作记录保存实际参数的值。在传值参数情形,需为对应形式参数分配空间,以存放实际参数的副本;在引用参数情形,需保存实际参数的(D),在被调用程序中可直接操纵实际参数。A.空间B.副本C.返回地址D.地址5.以下数据结构中,哪一个是线性结构(D)。A.广义表B.二叉树C.稀疏矩阵D.串6.以下属于逻辑结构的是(C)。A.顺序表B.哈希表C.有序表D.单链表7.对于长度为9的有序顺序表,若采用折半搜索,在等概率情况下搜索成功的平均搜索长度为(C)的值除以9。A.20B.18C.25D.228.在有向图中每个顶点的度等于该顶点

3、的(C)。A.入度B.出度C.入度与出度之和D.入度与出度之差9.在基于排序码比较的排序算法中,(C)算法的最坏情况下的时间复杂度不高于O(nlog2n)。A.起泡排序B.希尔排序C.归并排序D.快速排序10.当α的值较小时,散列存储通常比其他存储方式具有(B)的查找速度。A.较慢B.较快C.相同D.不同二、填空题1.二维数组是一种非线性结构,其中的每一个数组元素最多有______2___个直接前驱(或直接后继)。2.将一个n阶三对角矩阵A的三条对角线上的元素按行压缩存放于一个一维数组B中,A[0][0]存放于B[0]

4、中。对于任意给定数组元素B[K],它应是A中第_ë(K+1)/3û_行的元素。3.链表对于数据元素的插入和删除不需移动结点,只需改变相关结点的__指针__域的值。4.在一个链式栈中,若栈顶指针等于NULL则为__空栈_。5.主程序第一次调用递归函数被称为外部调用,递归函数自己调用自己被称为内部调用,它们都需要利用栈保存调用后的__返回_地址。6.在一棵树中,__叶子_结点没有后继结点。7.一棵树的广义表表示为a(b(c,d(e,f),g(h)),i(j,k(x,y))),结点f的层数为___3___。假定根结点的层数为

5、0。8.在一棵AVL树(高度平衡的二叉搜索树)中,每个结点的左子树高度与右子树高度之差的绝对值不超过_____1___。8.n(n﹥0)个顶点的无向图最多有__n(n-1)/2_条边,最少有___0_____条边。9.在索引存储中,若一个索引项对应数据对象表中的一个表项(记录),则称此索引为_稠密__索引,若对应数据对象表中的若干个表项,则称此索引为_稀疏___索引。三、判断题1.数组是一种复杂的数据结构,数组元素之间的关系既不是线性的也不是树形的(对)2.链式存储在插入和删除时需要保持物理存储空间的顺序分配,不需要保

6、持数据元素之间的逻辑顺序(错)3.在用循环单链表表示的链式队列中,可以不设队头指针,仅在链尾设置队尾指针(对)4.通常递归的算法简单、易懂、容易编写,而且执行的效率也高(错)5.一个广义表的表尾总是一个广义表(对)6.当从一个小根堆(最小堆)中删除一个元素时,需要把堆尾元素填补到堆顶位置,然后再按条件把它逐层向下调整,直到调整到合适位置为止(对)7.对于一棵具有n个结点,其高度为h的二叉树,进行任一种次序遍历的时间复杂度为O(h)(错)1.存储图的邻接矩阵中,邻接矩阵的大小不但与图的顶点个数有关,而且与图的边数也有关(

7、错)2.直接选择排序是一种稳定的排序方法(错)3.闭散列法通常比开散列法时间效率更高(错)四、运算题1.设有一个10´10的对称矩阵A,将其下三角部分按行存放在一个一维数组B中,A[0][0]存放于B[0]中,那么A[8][5]存放于B中什么位置。解:根据题意,矩阵A中当元素下标I与J满足I≥J时,任意元素A[I][J]在一维数组B中的存放位置为I*(I+1)/2+J,因此,A[8][5]在数组B中位置为8*(8+1)/2+5=41。2.这是一个统计单链表中结点的值等于给定值x的结点数的算法,其中while循环有错,请

8、重新编写出正确的while循环。intcount(ListNode*Ha,ElemTypex){//Ha为不带头结点的单链表的头指针intn=0;while(Ha->link!=NULL){Ha=Ha->link;if(Ha->data==x)n++;}returnn;}解:while(Ha!=NULL){if(Ha->data=

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。