没有合适的资源?快使用搜索试试~ 我知道了~
本科计算机信息第三学期《数据结构》参考答案.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 138 浏览量
2022-05-04
19:15:03
上传
评论
收藏 190KB DOC 举报
温馨提示
![preview](https://dl-preview.csdnimg.cn/85284488/0001-030e5a151ca7cc128c69093e9123af2a_thumbnail-wide.jpeg)
![preview-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/scale.ab9e0183.png)
试读
15页
本科计算机信息第三学期《数据结构》参考答案.doc
资源推荐
资源详情
资源评论
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![doc](https://img-home.csdnimg.cn/images/20210720083327.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![js](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![](https://csdnimg.cn/release/download_crawler_static/85284488/bg1.jpg)
《数据结构》模拟卷 A
一、选择题
1. 在一个长度为 n 的顺序表的任一位置插入一个新元素的渐进时间复杂度为( A )。
A. O(n) B. O(n/2) C. O(1) D. O(n
2
)
2. 带头结点的单链表 rst 为空的判定条件是:( B )。
A. rst == NULL; B. rst->link == NULL;
C. rst->link == rst; D. rst != NULL;
3. 从逻辑上可以把数据结构分为( C )两大类。
A.动态结构、静态结构 B.顺序结构、链式结构
C.线性结构、非线性结构 D.初等结构、构造型结构
4. 在系统实现递归调用时需利用递归工作记录保存实际参数的值。在传值参数情形,需
为对应形式参数分配空间,以存放实际参数的副本;在引用参数情形,需保存实际参
数的( D ),在被调用程序中可直接操纵实际参数。
A. 空间 B. 副本 C. 返回地址 D. 地址
5. 以下数据结构中,哪一个是线性结构( D )。
A.广义表 B. 二叉树 C. 稀疏矩阵 D. 串
6. 以下属于逻辑结构的是( C )。
A.顺序表 B. 哈希表 C.有序表 D. 单链表
7. 对于长度为 9 的有序顺序表,若采用折半搜索,在等概率情况下搜索成功的平均搜索
长度为( C )的值除以 9。
A. 20 B. 18 C. 25 D. 22
8. 在有向图中每个顶点的度等于该顶点的( C )。
A. 入度 B. 出度
C. 入度与出度之和 D. 入度与出度之差
9. 在基于排序码比较的排序算法中,( C )算法的最坏情况下的时间复杂度不高于
O(nlog
2
n)。
A. 起泡排序 B. 希尔排序 C. 归并排序 D. 快速排序
10. 当 α 的值较小时,散列存储通常比其他存储方式具有( B )的查找速度。
A. 较慢 B. 较快 C. 相同 D.不同
1
![](https://csdnimg.cn/release/download_crawler_static/85284488/bg2.jpg)
二、填空题
1. 二维数组是一种非线性结构,其中的每一个数组元素最多有______2___个直接前驱
(或直接后继)。
2. 将一个 n 阶三对角矩阵 A 的三条对角线上的元素按行压缩存放于一个一维数组 B 中,
A[0][0]存放于 B[0]中。对于任意给定数组元素 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___。假定根结点的层数为 0。
8. 在一棵 AVL 树(高度平衡的二叉搜索树)中,每个结点的左子树高度与右子树高度之
差的绝对值不超过_____1___。
9. n (n﹥0) 个顶点的无向图最多有__ n(n-1)/2_条边,最少有___0_____条边。
10. 在索引存储中,若一个索引项对应数据对象表中的一个表项(记录),则称此索引为 _
稠密__索引,若对应数据对象表中的若干个表项,则称此索引为_稀疏___索引。
三、判断题
1. 数组是一种复杂的数据结构,数组元素之间的关系既不是线性的也不是树形的(对)
2. 链式存储在插入和删除时需要保持物理存储空间的顺序分配,不需要保持数据元素之
间的逻辑顺序(错)
3. 在用循环单链表表示的链式队列中,可以不设队头指针,仅在链尾设置队尾指针(对)
4. 通常递归的算法简单、易懂、容易编写,而且执行的效率也高(错)
5. 一个广义表的表尾总是一个广义表(对)
6. 当从一个小根堆(最小堆)中删除一个元素时,需要把堆尾元素填补到堆顶位置,然
后再按条件把它逐层向下调整,直到调整到合适位置为止(对)
7. 对于一棵具有 n 个结点,其高度为 h 的二叉树,进行任一种次序遍历的时间复杂度为
O(h)( 错)
8. 存储图的邻接矩阵中,邻接矩阵的大小不但与图的顶点个数有关,而且与图的边数也
2
![](https://csdnimg.cn/release/download_crawler_static/85284488/bg3.jpg)
有关(错)
9. 直接选择排序是一种稳定的排序方法(错)
10. 闭散列法通常比开散列法时间效率更高(错)
四、运算题
1. 设有一个 1010 的对称矩阵 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 循环有错,
请重新编写出正确的 while 循环。
int count ( ListNode * Ha, ElemType x )
{ // Ha 为不带头结点的单链表的头指针
int n = 0;
while ( Ha->link != NULL ) {
Ha = Ha->link;
if ( Ha->data == x ) n++;
}
return n;
}
解:
while ( Ha != NULL ) {
if ( Ha->data == x ) n++;
Ha = Ha->link;
}
3. 已知一棵二叉树的前序和中序序列,求该二叉树的后序序列。
前序序列:A, B, C, D, E, F, G, H, I, J
中序序列:C, B, A, E, F, D, I, H, J, G
后序序列:
3
剩余14页未读,继续阅读
资源评论
![avatar-default](https://csdnimg.cn/release/downloadcmsfe/public/img/lazyLogo2.1882d7f4.png)
![avatar](https://profile-avatar.csdnimg.cn/default.jpg!1)
老帽爬新坡
- 粉丝: 83
- 资源: 2万+
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的C币 登录后查看C币余额
我的收藏
我的下载
下载帮助
![voice](https://csdnimg.cn/release/downloadcmsfe/public/img/voice.245cc511.png)
![center-task](https://csdnimg.cn/release/downloadcmsfe/public/img/center-task.c2eda91a.png)
安全验证
文档复制为VIP权益,开通VIP直接复制
![dialog-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/green-success.6a4acb44.png)