《数据结构》复习资料.docx
《《数据结构》复习资料.docx》由会员分享,可在线阅读,更多相关《《数据结构》复习资料.docx(15页珍藏版)》请在三一办公上搜索。
1、数据结构复习资料1一、选择题1. 一棵二叉树中第6层上最多有()个结点。A. 2B. 31C. 32D. 642. 顺序表中数据元素的存取方式为()。A. 随机存取B. 顺序存取C. 索引存取D. 连续存取3. 设有无向图 G=(V,E),其中顶点集合 V=a,b,c,d,e,f,边集合 E=(a,b), (a,e), (a,c), (b,e), (c,f), (f,d), (e,d)。对G进行深度优先遍历,正确的遍历序列是()。A. a,b,e,c,d,fB. a,c,f,e,b,dC. a,e,b,c,f,dD. a,e,d,f,c,b4. 在待排元素序列基本有序的前提下,效率最高的排序方
2、法是()。A. 插入B. 选择C. 快速D. 归并5. 设表中含100个数据元素,用折半查找法进行查找,则所需最大比较次数为()。A. 50B. 25C. 10D. 76. 设哈希表地址范围为019,哈希函数H(key)=key%17,使用二次探测再散列法处理冲突。若表中已存放有关键字值为6、22、38. 55的记录,则再放入关键字值为72的记录时,其存 放地址应为()。A. 2B. 3C. 4D. 7E. 8F. 以上都不对7. 设对下图从顶点a出发进行深度优先遍历,则()是可能得到的遍历序列。A. acfgdebB. abcdefgC. acdgbefD. abefgcd8. 若需在O(n
3、log2n)的时间内完成对数组的排序,且要求排序是稳定的,则可选择的排序方 法是()。A. 快速排序B. 堆排序C. 归并排序D. 直接插入排序9. 设有一组关键字值(46,79,56,38,40,84),则用堆排序的方法建立的初始堆为()。A. 79,46,56,38,40,84B. 84,79,56,38,40,46C. 84,79,56,46,40,38D. 84,56,79,40,46,3810. 设广义表 L=(a,(),b,(c,d,e),则 Head(Tail(Tail(L)的值为()。A. bB. cC. (c)D. (c,d,e)11. 在树形结构中,数据元素间存在()的关系
4、。A. 一对一B. 一对多C. 多对多D. 除同属一个集合外别无关系12. 一棵度为3的树中,度为3的结点有2个,度为2的结点有2个,度为1的结点有2个, 则度为0的结点有()。A. 5个B. 6个C. 7个D. 8个13. ()是数据的不可分割的最小单位。A. 数据元素B. 数据对象C. 数据项D. 数据结构14. 直接插入排序在最好情况下的时间复杂度为()。A. O(logn)B. O(n)C. O(n*logn)D. O(n2)15. 以下属单链表优点的是()。A. 顺序存取B. 插入操作能在O(1)的时间复杂度上完成C. 插入时不需移动数据元素D. 节省存储空间16. 在长为n的顺序表
5、中删除一个数据元素,平均需移动()个数据元素。A. nB. n-1C. n/217. 若采用顺序映象,则数据元素在内存中占用的存储空间()。A. 一定连续B. 一定不连续C. 可连续可不连续18. 若用一个大小为6的数组来实现循环队列,且当前队尾指针rear和队头指针front的值 分别为0和3,当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为()。A. 1和 5B. 2 和 4C. 4 和 2D. 5和119. 串的长度是指()。A. 串中所含不同字母的个数B. 串中所含字符的个数C. 串中所含不同字符的个数D. 串中所含非空格字符的个数20. 设在一不带头结点的链队
6、列中,front和rear分别为其队头和队尾指针,则判定该队中 只有一个结点的条件是()。A. front-nextB. rear-nextC. front=rearD. front!二rear二、填空题1. 具有N个结点的无向完全图共有 条边。2. 数据结构课程是研究数据的、等三个方面的内容。3. 对一棵二叉排序树进行中序遍历时,得到的结点序列是一个。4. 已知二维数组a108采用行优先存储方式,每个元素占2个存储单元,第一个元素的 存储地址是1012,则元素a45的存储地址为。5. 画出具有3个结点的二叉树的所有形态:。6. 对于一个单链接存储的线性表,假定表头指针指向链表的第一个结点,则
7、在表头插入结点 的时间复杂度为,在表尾插入结点的时间复杂度为。7. 已知完全二叉树的第8层有8个结点,则其叶子结点数是。三、问答题1. 假设将循环队列定义为:以域变量rear和length分别指示循环队列中队尾元素的位置和内含元素的 个数,试写出其入队和出队算法(在出队算法中要返回队头元素)。2. 设有上三角矩阵(aij)nxn,将其上三角元素逐行存于数组Bm中(m充分大),使得Bk=aij,求用 i和j表示k的下标变换公式。3. 设n为正整数,则在下面的程序段中,语句“a+=2;”的频度为多少?for(x=0;xn;+x)for(y=0;y=n-1B . e=n-2C .e=n-3D . e
8、=n-43.能采用二分查找的数据结构是(A .线性表B.二叉树C.有序表D .哈希表4.下列哪一个不属于算法的性质()。A.输入性B.输出性C.可执行性D.可修改性5.一棵有n (n0)个结点的满二叉树共有()个叶子结点。A.2nB.2n-1C.2n+1D. (n-1)/26.假设指针p指向单链表中的某一结点,若在p指针的后面插入一个新结点q,只需修改下列哪个指针值即可()。A.p=q;q=p.next;B. p=q.next;q.next二p.nextC.p.next=q;q.next二p.next;D. q.next二p.next;p.next二q;7.若进栈系列为:a,b, c, d,则
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习资料
链接地址:https://www.31ppt.com/p-4927846.html