没有合适的资源?快使用搜索试试~ 我知道了~
首页南邮 数据结构C语言 陈惠南
南邮 数据结构C语言 陈惠南
需积分: 9 44 下载量 139 浏览量
更新于2023-06-01
6
收藏 1.55MB DOC 举报
本文为南邮 数据结构C语言 陈惠南 课后练习题答案,不仅包括计算题,选择题和填空题答案也有
资源详情
资源推荐
第一章概论
一、填空题
1、 数据的存储结构可用四种基本的存储方法表示,分别是顺序、 链式 、 索引 和 散列。
2、一个算法具有 5 个特性: 有穷性 、确定性、可行性,有零个或多个输入、有一个或多个
输出 。
3、 数据结构包括数据的 逻辑结构 、存储结构 和 运算(或基本操作)这三个方面的内容。
4、数据结构中评价算法的两个重要指标是 时间 效率和 空间 效率。
5、一个数据结构在计算机中的表示称为 存储结构 。
6、从逻辑上可以把数据结构分为线性结构、非线性结构两大类
7、数据逻辑结构除了集合以外,还包括线性结构、树形结构和 图形结构 。
8、数据的存储结构形式包括顺序存储、链式存储、索引存储和 散列存储 。
9 、 数据结构主要研究数据的逻辑结构、存储结构和算法(或运算)3 个方面的内容。
10、算法效率的度量可以分为事先估算和 事后统计法 。
二、单项选择题
1、 数据结构中,与所使用的计算机无关的是数据的是( C );
A、 存储结构 B、 物理结构 C、逻辑结构 D、 物理和逻辑结构
2、算法分析的目的是( C )
A) 找出数据结构的合理性 B) 研究算法中的输入和输出的关系
C) 分析算法的效率以求改进 D) 分析算法的易懂性和文档性
3、 计算机算法指的是( C )
A) 计算方法 B) 排序方法 C) 解决问题的有限运算序列 D) 调度方法
4、 计算机算法必须具备输入、输出和( B )等 5 个特性。
A) 可行性、可移植性和可扩充性 B) 可行性、确定性和有穷性
C) 确定性、有穷性和稳定性 D) 易读性、稳定性和安全性
5、从逻辑上可以把数据结构分为( C )两大类。
A)动态结构、静态结构 B)顺序结构、链式结构
C)线性结构、非线性结构 D)初等结构、构造型结构
6、下列数据中,( C)是非线性数据结构。
A.栈 B. 队列 C. 完全二叉树 D. 堆
7、算法分析的两个主要方面是( A )。
A) 空间复杂性和时间复杂性 B) 正确性和简明性
C) 可读性和文档性 D) 数据复杂性和程序复杂性
1
8、下面程序段的时间复杂度是( D )
i=1;
while(i<=n)
i=i*3;
A. O(3n) B.O(n) C.O(n
3
) D.O(log
3
n)
9、下面程序段的时间复杂度为( C )
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
x=x+1;
A. O(2n) B.O(n) C.O(n
2
) D.O(log
2
n
)
10、下面关于算法说法错误的是( D )
A.算法最终必须由计算机程序实现
B.为解决某问题的算法同为该问题编写的程序含义是相同的
C. 算法的可行性是指指令不能有二义性
D. 以上几个都是错误的
11、数据结构通常是研究数据的(A)及它们之间的相互关系。
A.存储结构和逻辑结构 B.存储和抽象
C.联系和抽象 D.联系与逻辑
12、数据在计算机中存储器内表示时,物理地址和逻辑地址相同并且是连续的,称之为(
C )。
A.存储结构 B.逻辑结构 C.顺序存储结构 D.链式存储结构
13、非线性结构中的每个结点( D )。
A.无直接前趋结点 B.无直接后继结点
C.只有一个直接前趋和一个直接后继结点 D.可能有多个直接前趋和多个直接后继结点
14、链式存储结构所占存储空间( A )。
A.分两部分,一部分存储结点的值,另一部分存放表示结点间关系的指针
B.只有一部分,存放结点的值
C.只有一部分,存储表示结点间关系的指针
D.分两部分,一部分存放结点的值,另一部分存放结点所占单元数
15、数据的基本单位是(B)。
A.数据结构 B.数据元素 C.数据项 D.文件
16、每个结点只含有一个数据元素,所有存储结点相继存放在一个连续的存储空间里。这
种存储结构称为(A)结构。
A.顺序存储 B.链式存储 C.索引存储 D.散列存储
2
17、每一个存储结点不仅含有一个数据元素,还包含一组指针,该存储方式是(B)存储方
式。
A.顺序 B.链式 C.索引 D.散列
18、算法分析的两个主要方面是(A)。
A.空间复杂性和时间复杂性 B.正确性和简明性
C.可读性和文档性 D.数据复杂性和程序复杂性
19、算法能正确的实现预定功能的特性称为算法的(A)。
A.正确性 B.易读性 C.健壮性 D.高效性
20、算法在发生非法操作时可以作出相应处理的特性称为算法的(C)。
A.正确性 B.易读性 C.健壮性 D.高效性
21、计算机算法必须具备输入、输出和(C)。
A.计算方法 B.排序方法
C.解决问题的有限运算步骤 D.程序设计方法
三、判断题
1. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构.(× )
2. 数据的逻辑结构是指数据的各数据项之间的逻辑关系;(× )
3. 数据的物理结构是指数据在计算机内的实际存储形式。(√ )
4.算法的优劣与算法描述语言无关,但与所用计算机有关。(× )
5.健壮的算法不会因非法的输入数据而出现莫名其妙的状态。(√ )
6.算法可以用不同的语言描述,如果用 C 语言或 PASCAL 语言等高级语言来描述,则算法
实际上就是程序了。(× )
四、简答题
1、当为解决某一问题而选择数据结构时,应从哪些方面考虑?
答:通常考虑算法所需要的存储空间量和算法所需要的时间量。后者又涉及到四方面:程序
运行时所需输入的数据总量,对源程序进行编译所需时间,计算机执行每条指令所需时间和
程序中指令重复执行的次数。
第 2 章 线性表
一、填空
1.当线性表的元素总数基本稳定,且很少进行插入和删除操作,但要求以最快的速度存取
线性表中的元素时,应采用顺序 存储结构。
3
2.顺序存储的线性表存储特点是用 物理位置的相邻 表示元素之间的逻辑关系,在顺序
表中插入或删除一个元素,移动的元素个数与 表长和该元素在表中的位置 有关。如果线性
表 L=(a1,a2,…,an)用数组表示,假定删除表中任一元素的概率相同,则删除一个元素
平均需要移动元素的个数是( n-1 ) /2 _;第 i 个元素(1<=i<=n)之前插入一个元素时,
需向后移动 n-i+1_个元素。如果要在第 1 个元素前插入一个元素,要后移 n 个元素;删除
第 i 个元素(1≤i≤n)时,需向前移动 n-i 个元素。
3.设单链表的结点结构为(data,next),next 为指针域,已知指针 px 指向单链表中 data
为 x 的结点,指针 py 指向 data 为 y 的新结点 , 若将结点 y 插入结点 x 之后,则需要执行
以下语句:__ py->next=px->next; _ px->next=py
4.在顺序表中访问任意一结点的时间复杂度均为 O(1) ,因此,顺序表也称为 随机存取
的数据结构。
5、链接存储的特点是利用__指针 来表示数据元素之间的逻辑关系。在单链表中,除了首
元结点外,任一结点的存储位置由 其直接前驱结点的链域的值 指示,查找结点都必须从头
结点开始,因此,链表也称为 顺序存取 的数据结构。在 n 个结点的单链表中要删除已知
结点*p,需找到它的前驱结点的地址,其时间复杂度为 O ( n ) ,在给定值为 x 的结点后插
入一个新结点的时间复杂度为 O(n) _。
7.已知指针 p 指向单链表 L 中的某结点,则删除其后继结点的语句是: u=p->next; 为空
表的条件是:_ L->next==L && L->prior==L p->next=u->next;
8.带头结点的双循环链表 L 中只有一个元素结点的条件是:L->next->next==L;
二、判断正误(在正确的说法后面打勾,反之打叉)
( × )1. 线性表的特点是每个元素都有一个前驱和一个后继。
( × )2. 链表的物理存储结构具有同链表一样的顺序。
( × )3. 链表的删除算法很简单,因为当删除链中某个结点后,计算机会自动地将后续的
各个单元向前移动。
( × )4. 取线性表的第 i 个元素的时间同 i 的大小有关.
( × )5. 顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取。
6. 顺序存储方式的优点是存储密度大,且插入、删除运算效率高。( × )
(√ )7.链表是采用链式存储结构的线性表,进行插入、删除操作时,在链表中比在顺序存
储结构中效率高。
( × )8. 线性表在顺序存储时,逻辑上相邻的元素未必在存储的物理位置次序上相邻。
( × )9. 顺序存储方式只能用于存储线性结构。
( × )10. 线性表的逻辑顺序与存储顺序总是一致的。
(× )11. 链表中的头结点仅起到标识的作用。
4
(√ )12. 顺序存储结构的主要缺点是不利于插入或删除操作。
(√ ) 13.线性表采用链表存储时,结点和结点内部的存储空间可以是不连续的。
14.顺序存储方式插入和删除时效率太低,因此它不如链式存储方式好。(× )
(× )15. 对任何数据结构链式存储结构一定优于顺序存储结构。
三、单项选择题
1.数据在计算机存储器内表示时,物理地址与逻辑地址相同并且是连续的,称之为( C
)
(A)存储结构 (B)逻辑结构 (C)顺序存储结构 (D)链式存储结构
2.一个向量第一个元素的存储地址是 100,每个元素的长度为 2,则第 5 个元素的地址是
( B )
(A)110 (B)108 (C)100 (D)120
3. 在 n 个结点的顺序表中,算法的时间复杂度是 O(1)的操作是( A )
(A) 访问第 i 个结点(1≤i≤n)和求第 i 个结点的直接前驱(2≤i≤n)
(B) 在第 i 个结点后插入一个新结点(1≤i≤n)
(C) 删除第 i 个结点(1≤i≤n)
(D) 将 n 个结点从小到大排序
4. 向一个有 127 个元素的顺序表中插入一个新元素并保持原来顺序不变,平均要移动( B
)个元素
(A)8 (B)63.5 (C)63 (D)7
5. 线性表( a1,a2,…,an)以链接方式存储时,访问第 i 位置元素的时间复杂性为( C)
A.O(i) B.O(1) C.O(n) D.O(i-1)
6. 链表是一种采用( B )存储结构存储的线性表;
(A)顺序 (B)链式 (C)星式 (D)网状
7. 线性表若采用链式存储结构时,要求内存中可用存储单元的地址( D )
(A)必须是连续的 (B)部分地址必须是连续的
(C)一定是不连续的 (D)连续或不连续都可以
8. 线性表L在( B )情况下适用于使用链式结构实现。
(A)需经常修改L中的结点值 (B)需不断对L进行删除插入
(C)L中含有大量的结点 (D)L中结点结构复杂
9. 单链表的存储密度( C )
(A)大于 1; (B)等于 1; (C)小于 1; (D)不能确定
10.对于一个头指针为 head 的带头结点的单链表,判定该表为空表的条件是( B )
5
剩余63页未读,继续阅读
我是一条小青龙i
- 粉丝: 3
- 资源: 6
上传资源 快速赚钱
- 我的内容管理 收起
- 我的资源 快来上传第一个资源
- 我的收益 登录查看自己的收益
- 我的积分 登录查看自己的积分
- 我的C币 登录后查看C币余额
- 我的收藏
- 我的下载
- 下载帮助
会员权益专享
最新资源
- zigbee-cluster-library-specification
- JSBSim Reference Manual
- c++校园超市商品信息管理系统课程设计说明书(含源代码) (2).pdf
- 建筑供配电系统相关课件.pptx
- 企业管理规章制度及管理模式.doc
- vb打开摄像头.doc
- 云计算-可信计算中认证协议改进方案.pdf
- [详细完整版]单片机编程4.ppt
- c语言常用算法.pdf
- c++经典程序代码大全.pdf
- 单片机数字时钟资料.doc
- 11项目管理前沿1.0.pptx
- 基于ssm的“魅力”繁峙宣传网站的设计与实现论文.doc
- 智慧交通综合解决方案.pptx
- 建筑防潮设计-PowerPointPresentati.pptx
- SPC统计过程控制程序.pptx
资源上传下载、课程学习等过程中有任何疑问或建议,欢迎提出宝贵意见哦~我们会及时处理!
点击此处反馈
安全验证
文档复制为VIP权益,开通VIP直接复制
信息提交成功