《数据结构》复习题.docx
《《数据结构》复习题.docx》由会员分享,可在线阅读,更多相关《《数据结构》复习题.docx(6页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、数据结构复习题一、填空题.数据结构中评价算法的两个重要指标是 和。1 .数据元素之间有多种关系,其中常见的关系、02 .线性表的顺序存储是用 实现的。3 .在长度为n的顺序表中插入一个元素,等概率的情况下的平均移动元素的次数 是 o.三个结点可构成 种不同形态的二叉树。4 .对于栈只能在(位置)插入和删除元素。5 .对矩阵压缩是为了 o.深度为k的完全二叉树至少有 个结点,至多有 个结点。6 .对于一棵具有n个结点的二叉树,当进行链接存储时,其二叉链表中的指针域的总数为 个,其中 个用于链接孩子结点。7 .对二叉排序树进行 遍历,可得到排好序的递增结点序列。8 . N个顶点的连通图的生成树含有
2、 条边。9 .己知有序表为(12, 18,24, 35,47, 50,62,83,90, 115, 134)当用二分法查找 90 时,需 次查找成功,47时 成功,查100时,需 次才能确定不成功。10 .算法的计算量的大小称为计算的.在线性表的顺序存储中,元素之间的逻辑关系是通过 决定的;在线性表的链接存储中,元素之间的逻辑关系是通过决定的。11 .对于一个具有N个结点的单链表,在已知的结点*P后插入一个新结点的时间复杂度为 ,在给定值为X的结点后插入一个新结点的时间复杂度为.12 .无论对于顺序存储还是链接存储的队列来说,进行插入或删除运算的时间复杂度均相同 为.13 .对于一棵具有n个结
3、点的树,该树中所有结点的度数之和为.在一个完全二叉树的顺序存储中,若一个结点的下标为i,则它的左子女结点的下标为 ,右子女结点的下标为.14 .对于一棵具有n个结点的二叉树,对应二叉链表中指针总数为一个,其中一个用于 指向子女结点,一个指针空闲着.以折半搜索方法搜索一个线性表时,此线性表必须是存储的表15 .在一个无向图中,所有顶点的度数之和等于所有边数的一倍。16 .在一个具有n个顶点的无向完全图中,包含有条边,在一个具有n个顶点的有向完全图中,包含有一条边。17 .在一个具有n个顶点的无向图中,要连通所有顶点则至少需要一条边。18 .对于一个具有n个顶点和e条边的有向图和无向图,在其对应的
4、邻接表中,所含边结点 分别为和条二、选择题1 .数组A0. 4,0. 3中含有元素的个数()。A. 55B. 20C. 36D. 16.下面关于线性表的叙述中,错误的是哪一个?()A.线性表采用顺序存储,必须占用一片连续的存储单元。B.线性表采用顺序存储,便于进行插入和删除操作。C.线性表采用链接存储,不必占用一片连续的存储单元。D.线性表采用链接存储,便于插入和删除操作。3 .若长度为n的线性表采用顺序存储结构,在其第i个位置插入一个新元素的算法的时间复 杂度为()(l=i=n+l)oA. 0(0) B. 0(1)C. 0(n)D, 0(n2).对于一个头指针为head的带头结点的单链表,判
5、定该表为空表的条件是( )oA. head=NULL B. =NULL C. =head D. head!=NULL.一个栈的输入序列为123n,若输出序列的第一个元素是n,输出第i (l=ilink = p; p-link = s;B. s-link = p-link; p-link = s;C. s-link = p-link; p = s;D. p-link = s; s-link = p;7 .设无向图的顶点个数为n,则该图最多有()条边。A. n-1B. n(n-l)/2 C. n(n+l)/2 D. 0 E. n2.下列排序算法中()不能保证每趟排序至少能将一个元素放到其最终的位置
6、上。A.快速排序B. shell排序C.堆排序 D.冒泡排.对线性表进行二分查找时,要求线性表必须()。A.以顺序方式存储B.以顺序方式存储,且数据元素有序C.以链接方式存储D.以链接方式存储,且数据元素有序.在下面的排序方法中,辅助空间为0 (n)的是()。A.希尔排序B.堆排序C.选择排序 D.归并排序11在下面的程序段中,对x的赋值语句的频度为()FOR i:=l TO n DOx:=x+l;A. 0(2n) B. 0(n) C. 0(n2)D. 0(log2n)12线性表是具有n个()的有限序列(n0)oA.表元素 B.字符 C.数据元素 D.数据项13若长度为n的线性表采用顺序存储结
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 数据结构 复习题
限制150内