没有合适的资源?快使用搜索试试~ 我知道了~
数据结构期末复习题答案.doc
1.该资源内容由用户上传,如若侵权请联系客服进行举报
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
2.虚拟产品一经售出概不退款(资源遇到问题,请及时私信上传者)
版权申诉
0 下载量 143 浏览量
2021-10-06
08:35:53
上传
评论
收藏 338KB DOC 举报
温馨提示
![preview](https://dl-preview.csdnimg.cn/28613889/0001-b6c69b3dfe765a5d223ecb46f6ab44d7_thumbnail-wide.jpeg)
![preview-icon](https://csdnimg.cn/release/downloadcmsfe/public/img/scale.ab9e0183.png)
试读
16页
数据结构期末复习题答案.doc
资源推荐
资源详情
资源评论
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![tar](https://img-home.csdnimg.cn/images/20210720083646.png)
![](https://csdnimg.cn/release/download_crawler_static/28613889/bg1.jpg)
- -
1. 以下与数据的存储构造无关的术语是〔 c 〕
C、哈希表
2. 一个向量第一个元素的存储地址是 100,每个元素的长度为 2,那么第 5 个元素的地址是〔 B 〕
B、108
3. 假设带头结点的单向循环链表的头指针为 head,那么该链表为空的判定条件是〔C〕
C、head–>next= =head
4. 假设进栈序列为 1,2,3,4,5,6,且进栈和出栈可以穿插进展,那么不可能出现的出栈序列是〔 D 〕
D、2,3,5,1,6,4
5. 以下关键字序列中,构成小根堆的是〔 A 〕
A、{12,21,49,33,81,56,69,41}
6. 以下数据构造中,不属于二叉树的是〔 A 〕
A、B 树
7. 用顺序存储的方法来存储一棵二叉树,存放在一维数组 A[1..N]中,假设结点 A[i]有右孩子,那么其右孩子是〔 C 〕。
C、A[2i+1]
8. 设树 T 的高度为 4,其中度为 1、2、3、4 的结点个数分别为 4、2、1、1,那么 T 中叶子数为〔 D 〕
D、 8
9. 有数据{53,30,37,12,45,24,96},从空二叉树开场逐个插入数据来形成二叉排序树,假设希望高度最小,那
么应选择下面哪个序列输入〔 B 〕
B、37,24,12,30,53,45,96
10. 对下面有向图给出了四种可能的拓扑序列,其中错误的选项是〔 C 〕
C、5,1,6,3,4,2
11. m 阶 B-树中所有非终端〔除根之外〕结点中的关键字个数必须大于或等于( B )
B、[m/2]-1
12. 散列文件也称为( C )
B 、索引文件
13. 数据构造是〔 D 〕
D、相互之间存在一种或多种特定关系的数据元素的集合
14. 从逻辑关系来看,数据元素的直接前驱为 0 个或 1 个的数据构造只能是〔 C 〕
C、线性构造和树型构造
15. 设 p 为指向双向循环链表中某个结点的指针,p 所指向的结点的两个链域分别用 p→llink 和 p→rlink 表示,那么同样表
示 p 指针所指向结点的表达式是〔 D 〕
D、p→llink→rlink
16. 假设栈采用顺序存储方式存储,现两栈共享空间 V[1..m],top[i]代表第 i 个栈( i =1,2)栈顶,栈 1 的底在 v[1],栈 2
- - word.zl-
![](https://csdnimg.cn/release/download_crawler_static/28613889/bg2.jpg)
- -
的底在 V[m],那么栈满的条件是〔 B 〕
B、 top[1]+1=top[2]
17. 假设一棵二叉树有 11 个叶子结点,那么该二叉树中度为 2 的结点个数是〔 A 〕
A、10
18. 树的先根序列等同于与该树对应的二叉树的〔 A 〕
A、先序序列
19. 下面关于哈希(Hash,杂凑)查找的说确的是( C )
C、不存在特别好与坏的哈希函数,要视情况而定
20. 以下序列中,〔 D 〕是执行第一趟快速排序后所得的序列。
D、 [68,11,69,23,18] [93,73]
21. 以下关键字序列中,构成小根堆的是( D )
D、 (15,28,46,37,84,58,62,41)
22. ISAM 文件和 VASM 文件属于( C )
C、索引顺序文件
23. 下面程序段的时间复杂度为〔 C 〕
for (i=0; i<m; i++)
for (j=0; j<n; j++)
A[i][j]=i*j;
C、O(m*n)
24. 指针 p 和 q 分别指向某单链表中第一个结点和最后一个结点。假设指针 s 指向另一个单链表中某个结点,那么在 s 所指
结点之后插入上述链表应执行的语句为〔 A 〕
A、q->next=s->next;s->next=p;
25. 为便于判别有向图中是否存在回路,可借助于〔 D 〕
D、拓扑排序算法
26. 假设以 S 和 X 分别表示进栈和退栈操作,那么对初始状态为空的栈可以进展的栈操作系列是〔 D 〕
D、SSSXXSXX
27. 设有一顺序栈 S,元素 s1,s2,s3,s4,s5,s6 依次进栈,如果 6 个元素出栈的顺序是 s2,s3,s4,s6,s5,s1,那么栈的容量至
少应该是( B )
B、3
28. 假设以数组 A[m]存放循环队列的元素。队列的长度为 length,指针 rear 指向队尾元素的下一个存储位置,那么队头元
素所在的存储位置为〔B〕。
B、(rear-length+m)%m
29. 在一个链队列中,front 和 rear 分别为头指针和尾指针,那么插入一个结点 s 的操作为〔 D 〕。
- - word.zl-
![](https://csdnimg.cn/release/download_crawler_static/28613889/bg3.jpg)
- -
D、rear->next=s;rear=s;
30. 对于哈希函数 H(key)=key%13,被称为同义词的关键字是〔 D 〕
D、25 和 51
31. 采用二叉链表存储的 n 个结点的二叉树,共有空指针〔 A 〕个。
A、n+1
32. 连通网的最小生成树是其所有生成树中〔 D 〕
D、边的权值之和最小的生成树
33. 对记录序列(314,298,508,123,486,145)依次按个位和十位进展两趟基数排序之后所得结果为〔 B 〕
B、508,314,123,145,486,298
34. 任何一个无向连通图的最小生成树( C )。
C、一棵或多棵
35. 无向图的邻接矩阵是一个( C )
C、对称矩阵
36. 设无向图 G-=(V,E)和 G’=(V’,E’),如 G’为 G 的生成树,那么以下说法中不正确的选项是( B )。B、G’为 G 连通分量
37. 以 v1 为起始结点对以下图进展深度优先遍历,正确的遍历序列是〔 D 〕
D、 v1,v2,v5,v6,v7,v3,v4
38. 下面几个符号串编码集合中,不是前缀编码的是〔 B 〕
B、{0,1,00,11}
39. 希尔排序的增量序列必须是〔B 〕。
B、递减的
40. 采用起泡排序法对 n 个关键字进展升序排序,假设要使排序过程中比拟关键字的次数最多,那么初始时的序列应满足条
件〔 D 〕
D、关键字从大到小排列
41. 在以下部排序中( A )是不稳定的。
A、希尔排序
42. 分别以以下序列构造二叉排序树,与用其它三个序列所构造的结果不同的是( C )。
A、〔100,80, 90, 60, 120,110,130〕
43. 在查找过程中,冲突指的是〔 C 〕。
C、不同键值对应一样的存储地址
44. 对有 14 个元素的有序表 A[1..14]作二分查找,查找元素 A[4]时的被比拟元素依次为〔 D 〕。
D、A[7],A[3],A[5],A[4]
45. 以 v1 为起始结点对以下图进展广度度优先遍历,正确的遍历序列是〔 A 〕
A、 v1,v2,v3,v4,v5,v6,v7
- - word.zl-
![](https://csdnimg.cn/release/download_crawler_static/28613889/bg4.jpg)
- -
二、填空题(本大题共 10 小题,每题 2 分,假设有两个空格,每个空格 1 分,共 20 分)
1. 数据的物理构造包括 数据元素 的存储和数据之间关系的存储。
2. 假设一个算法中的语句频度之和为 T(n)=1921n+4nlogn,那么算法的时间复杂度为 nlogn。
3. 下面程序段的时间复杂度是 。
i=1;
while (i<=n) i=i*3;
4. 循环队列用数组 A[0..m-1]存放其元素值,其头尾指针分别是 front 和 rear ,那么当前队列的元素个数是 〔 rear-
front+m 〕 % m
5. 主要是使插入和删除等操作统一
6. 〔 n-1 〕 /2 。
7. 在单链表中设置头结点的作用是深度优先。
8. 线性表 L=〔a1,a2,…,an〕用数组表示,假定删除表中任一元素的概率一样,那么删除一个元素平均需要移动元素的个
数是 一样值关键字。
9. 一无向图 G=〔V,E〕,其中 V={a,b,c,d,e } E={(a,b),(a,d),(a,c),(d,c),(b,e)}现用某一种图遍历方法从顶点 a 开
场遍历图,得到的序列为 abecd,那么采用的是前移遍历方法。
10. 如果排序过程不改变 时间复杂度 之间的相对次序,那么称该排序方法是稳定的。
11. 从顺序表中删除一个元素时,表中所有在被删元素之后的元素均需出度一个位置。
12. 当问题的规模 n 趋向无穷大时,算法执行时间 T(n)的数量级被称为算法的 10 。
13. 假设以邻接矩阵表示有向图,那么邻接矩阵上第 i 行中非零元素的个数即为顶点 vi 的 sxssxxssxssxxx 。
14. 一棵含 999 个结点的完全二叉树的深度为 12 。
15. 假设 S 和 X 分别表示进栈和出栈操作,由输入序列“ABC〞得到输出序列“BCA〞的操作序列为 SSXSXX,那么由
“a*b+c/d〞得到“ab*cd/+〞的操作序列为 4 。
16. .如下图的有向无环图可以排出 L->next->next==L
17. 边 种不同的拓扑序列。
18. 从空树起,依次插入关键字 1l,27,35,48,52,66 和 73 构造所得的二叉排序树,在等概率查找的假设下,查找 成
- - word.zl-
剩余15页未读,继续阅读
资源评论
![avatar-default](https://csdnimg.cn/release/downloadcmsfe/public/img/lazyLogo2.1882d7f4.png)
![avatar](https://profile-avatar.csdnimg.cn/default.jpg!1)
gjmm89
- 粉丝: 15
- 资源: 19万+
![benefits](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-1.c8e153b4.png)
下载权益
![privilege](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-2.ec46750a.png)
C知道特权
![article](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-3.fc5e5fb6.png)
VIP文章
![course-privilege](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-4.320a6894.png)
课程特权
![rights](https://csdnimg.cn/release/downloadcmsfe/public/img/vip-rights-icon.fe0226a8.png)
开通VIP
上传资源 快速赚钱
我的内容管理 展开
我的资源 快来上传第一个资源
我的收益
登录查看自己的收益我的积分 登录查看自己的积分
我的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)