数据结构习题

二． 判断正误 ( 请判断每小题正确与否，如果正确则在题后的 【 】内填入，否
则填入。)
1. 线性表长度是线性表所占用的存储空间的大小。 〔 〕
2. 双循环链表中，任意一结点的后继指针均指向其逻辑后继。 〔 〕
3. 对链队做出队操作时不会改变队头指针的值 〔 〕
4. 如果 2 个串含有相同的字符则说这 2 个串相等。 〔 〕
5. 如果某二叉树中某结点的度为 1，则说明该结点只有一棵子树 〔 〕
6. 已知一棵树的先序序列和后序遍历序列则一定能构造出这棵树。 〔 〕
7. 二路归并时，被归并的两个子序列中的关键字个数一定要相等。 〔 〕
8. “顺序查找法”是指在顺序表上进行查找的方法。 〔 〕
9. n 个结点的有向图，若它有 n(n－1)条边，则它一定是强连通的。 〔 〕
10. 直接选择排序其时间复杂度不受数据的初始特征的影响，为 O(n2) 〔 〕
11. 数据的逻辑结构从逻辑关系上看与数据的存储方式有关，但独立于计算机。 ( )
12. 每一种逻辑结构都有适合自身的一个运算集合。 ( )
13. 数据的存储结构不仅有顺序存储结构和链式存储结构，还有索引结构与散列结构。 ( )
14. 若频繁地对线性表进行插入和删除操作，该线性表采用顺序存储结构更合适。 ( )
15. 若一棵二叉树的任一非叶子结点的度为 2，则该二叉树为满二叉树。 ( )
16. 2 路归并排序的核心操作是将 2 个有序序列归并为一个有序序列。 ( )
17. 在执行某个排序算法过程中，出现了排序码朝着最终排序序列位置 相反方向移动，则该算法是不稳定的。 ( )
18. 向二叉排序树中插入一个结点所需的比较次数可能大于此二叉排序树的高度。 ( )
19. 理想情况下，在散列表中查找一个元素的时间复杂性为 O(1)。 ( )
20. 二分查找要求待查找的表中关键字值应是有序的，但对存储结构没有限制。( )

1. 2. 3, 4. 5, 6. 7, 8. 9. 10, 11, 12, 13, 14. 15, 16. 17, 18, 19. 20. 我略知皮毛,以上部分答案还请斟酌!!

一、选择题 1．c 2．d 解析：a．完全二叉树可以用数组存储，树是非线性结构 b．链表且插入和删除运算效率高 c．链表也有双向链表 ，有两个指针域 3．a 4．a．顺序表可随机访问任一元素 5．d 6．这道题你是不是弄错了 全都对啊 7．d 满二叉树 ：结点总数目n=2^h -1 h为数高度 ，求出结点总数为255 满二叉树，只有度为0 和度为2 的结点，度为0 的结点等于度为1 结点数目+1 因此选d 8．c 这题不用画图就可做出来， 后序遍历序列是dabec，------》得到根节点是：c 前序遍历；根左右 所以第一个一定是c 只有a项符合 9. a 虽然你没给图 但是一般都是a相 因为见过好多这个题 中序遍历和层次遍历结果一样 10. d 11.c 12.b 在最坏情况:比较次数为___每次查找都要从第一个比较到最后一个，都要遍历n次 ： 总的比较次数n*n,平均比较次数就是n 13. c 二、填空题 1．出栈 2．n/2+n/(n+1) 1+2+3……n+n)/(n+1)=．n/2+n/(n+1) 3．1 4．设待排数据元素的关键字为（67，24，14，22，33，15，11，15），用选择法将其按升序排序，需要比较的次数为【 】。 5．13 6．11 3+6+2=11 *7．15 方法 同选择题 上那个满二叉树 8．无图 9. 16 和第七题一样的方法