《C语言数据结构》第1至9章自测题答案大全

只要记分牌上的时间还跳动，就不能轻言放弃。第一章概论自测题答案姓名班级题号一二三四五六总分题分3315982015100得分一、填空题（每空1分共33分）1.一个计算机系统包括硬件系统和软件系统两大部分2.一台计算机中全部程序的集合称为这台计算机的软件资源/（系统）3.计算机软件可以分为系统软件和应用软件两大类科学计算程序包属于应用软件诊断程序属于系统软件（工具）4.一种用助忆符号来表示机器指令的操作符和操作数的语言是汇编语言5.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科6.数据结构被形式地定义为（DR）其中D是数据元素的有限集合R是D上的关系有限集合7.数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容8.数据结构按逻辑结构可分为两大类它们分别是线性结构和非线性结构9.线性结构中元素之间存在一对一关系树形结构中元素之间存在一对多关系图形结构中元素之间存在多对多关系10．在线性结构中第一个结点没有前驱结点其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点其余每个结点有且只有1个后续结点11.在树形结构中树根结点没有前驱结点其余每个结点有且只有1个前驱结点；叶子结点没有后续结点其余每个结点的后续结点数可以任意多个12.在图形结构中每个结点的前驱结点数和后续结点数可以任意多个13．数据的存储结构可用四种基本的存储方法表示它们分别是顺序、链式、索引和散列14.数据的运算最常用的有5种它们分别是插入、删除、修改、查找、排序15.一个算法的效率可分为时间效率和空间效率16.〖00年省统考〗任何一个C程序都由一个主函数和若干个被调用的其它函数组成17.【00年省统考题】变量一经说明就确定该变量的取值范围（即存储单元）及确定变量所允许的运算二、单项选择题（每小题1分共15分）（B）1.通常所说的主机是指∶A)CPUB)CPU和内存C)CPU、内存与外存D)CPU、内存与硬盘（C）2.在计算机内部一切信息的存取、处理和传送的形式是∶A)ACSII码B)BCD码C)二进制D)十六进制（D）3.软件与程序的区别是∶A)程序价格便宜、软件价格昂贵；B)程序是用户自己编写的而软件是由厂家提供的；C)程序是用高级语言编写的而软件是由机器语言编写的；D)软件是程序以及开发、使用和维护所需要的所有文档的总称而程序只是软件的一部分（C）4.所谓裸机是指∶A)单片机B)单板机C)不装备任何软件的计算机D)只装备操作系统的计算机（D）5.应用软件是指∶A)所有能够使用的软件B)能被各应用单位共同使用的某种软件C)所有微机上都应使用的基本软件D)专门为某一应用目的而编制的软件（＊A）6.〖00年省统考〗C语言中的常量可分为整型常量、实型常量、字符型常量及(枚举)四种（A）符号常量（B）长整型常量（C）逻辑常量（D）二进制整数（＊C）7.编译程序的功能是∶A)发现源程序中的语法错误B)改正源程序中的语法错误C)将源程序编译成目标程序D)将某一高级语言程序翻译成另一种高级语言程序（A）8.系统软件中最重要的是∶A)操作系统B)语言处理系统C)工具软件D)数据库管理系统（C）9.可移植性最好的计算机语言是∶A)机器语言B)汇编语言C)高级语言D)自然语言（B）10.非线性结构是数据元素之间存在一种：A）一对多关系B）多对多关系C）多对一关系D）一对一关系（C）11.数据结构中与所使用的计算机无关的是数据的结构；A)存储B)物理C)逻辑D)物理和存储（C）12.算法分析的目的是：A)找出数据结构的合理性B)研究算法中的输入和输出的关系C)分析算法的效率以求改进D)分析算法的易懂性和文档性（A）13.算法分析的两个主要方面是：A)空间复杂性和时间复杂性B)正确性和简明性C)可读性和文档性D)数据复杂性和程序复杂性（C）14.计算机算法指的是：A)计算方法B)排序方法C)解决问题的有限运算序列D)调度方法（B）15.计算机算法必须具备输入、输出和等5个特性A)可行性、可移植性和可扩充性B)可行性、确定性和有穷性C)确定性、有穷性和稳定性D)易读性、稳定性和安全性三、简答题（每小题3分共9分）1．我们知道计算机只能执行机器指令为什么它能运行用汇编语言和高级语言编写的程序？答：靠汇编程序将汇编语言或高级语言翻译转换为目标程序（即机器语言）2.【严题集1.2②】数据结构和数据类型两个概念之间有区别吗？答：简单地说数据结构定义了一组按某些关系结合在一起的数组元素数据类型不仅定义了一组带结构的数据元素而且还在其上定义了一组操作3.简述线性结构与非线性结构的不同点答：线性结构反映结点间的逻辑关系是一对一的非线性结构反映结点间的逻辑关系是多对多的四、〖00年统考题〗阅读下列C程序段写出相应的执行结果（每小题4分共8分）1.printf(Inputx);scanf(%d&x);if(x=30)if(x20)y=x;elseif(x10)y=2*x;if(x0&&x30)printf(x=%dy=%dxy);elseprintf(输入数据错！);试写出当x分别为188时的执行结果答：运行结果为：x=18y=36x=8y=运行前的值且从x＝30开始为数据错五、【严题集1.8④】分析下面各程序段的时间复杂度（每小题5分共20分）六、设有数据逻辑结构S=（DR）试按各小题所给条件画出这些逻辑结构的图示并确定相对于关系R哪些结点是开始结点哪些结点是终端结点？（每小题5分共15分）1.【严蔚敏习题集P71.3②】D={d1d2d3d4}R={(d1d2)(d2d3)(d3d4)}答：d1→d2→d3→d4d1-无直接前驱是首结点d4-无直接后继是尾结点2.D={d1d2...d9}R={(d1d2)(d1d3)(d3d4)(d3d6)(d6d8)(d4d5)(d6d7)(d8d9)}答：此图为树形结构d1-无直接前驱是根结点d2d5d7d9-无直接后继是叶子结点3.D={d1d2...d9}R={(d1d3)(d1d8)(d2d3)(d2d4)(d2d5)(d3d9)(d5d6)(d8d9)(d9d7)(d4d7)(d4d6)}答：此图为图形结构d1d2-无直接前驱是开始结点d6d7-无直接后继是终端结点(2)(3)第2章自测卷答案姓名班级题号一二三四五六七总分题分1310101071040100得分一、填空（每空1分共13分）1.【严题集2.2①】在顺序表中插入或删除一个元素需要平均移动表中一半元素具体移动的元素个数与表长和该元素在表中的位置有关2.线性表中结点的集合是有限的结点间的关系是一对一的3.向一个长度为n的向量的第i个元素(1≤i≤n+1)之前插入一个元素时需向后移动n-i+1个元素4.向一个长度为n的向量中删除第i个元素(1≤i≤n)时需向前移动n-i个元素5.在顺序表中访问任意一结点的时间复杂度均为O(1)因此顺序表也称为随机存取的数据结构6.【严题集2.2①】顺序表中逻辑上相邻的元素的物理位置必定相邻单链表中逻辑上相邻的元素的物理位置不一定相邻7.【严题集2.2①】在单链表中除了首元结点外任一结点的存储位置由其直接前驱结点的链域的值指示8．在n个结点的单链表中要删除已知结点*p需找到它的前驱结点的地址其时间复杂度为O（n）二、判断正误（在正确的说法后面打勾反之打叉）（每小题1分共10分）（×）1.链表的每个结点中都恰好包含一个指针答：错误链表中的结点可含多个指针域分别存放多个指针例如双向链表中的结点可以含有两个指针域分别存放指向其直接前趋和直接后继结点的指针（×）2.链表的物理存储结构具有同链表一样的顺序错链表的存储结构特点是无序而链表的示意图有序（×）3.链表的删除算法很简单因为当删除链中某个结点后计算机会自动地将后续的各个单元向前移动错链表的结点不会移动只是指针内容改变（×）4.线性表的每个结点只能是一个简单类型而链表的每个结点可以是一个复杂类型错混淆了逻辑结构与物理结构链表也是线性表！且即使是顺序表也能存放记录型数据（×）5.顺序表结构适宜于进行顺序存取而链表适宜于进行随机存取错正好说反了顺序表才适合随机存取链表恰恰适于顺藤摸瓜（×）6.顺序存储方式的优点是存储密度大且插入、删除运算效率高错前一半正确但后一半说法错误那是链式存储的优点顺序存储方式插入、删除运算效率较低在表长为n的顺序表中插入和删除一个数据元素平均需移动表长一半个数的数据元素（×）7.线性表在物理存储空间中也一定是连续的错线性表有两种存储方式顺序存储和链式存储后者不要求连续存放（×）8.线性表在顺序存储时逻辑上相邻的元素未必在存储的物理位置次序上相邻错误线性表有两种存储方式在顺序存储时逻辑上相邻的元素在存储的物理位置次序上也相邻（×）9.顺序存储方式只能用于存储线性结构错误顺序存储方式不仅能用于存储线性结构还可以用来存放非线性结构例如完全二叉树是属于非线性结构但其最佳存储方式是顺序存储方式（后一节介绍）（×）10.线性表的逻辑顺序与存储顺序总是一致的错理由同7链式存储就无需一致三、单项选择题（每小题1分共10分）（C）1．数据在计算机存储器内表示时物理地址与逻辑地址相同并且是连续的称之为：（A）存储结构（B）逻辑结构（C）顺序存储结构（D）链式存储结构（B）2.一个向量第一个元素的存储地址是100每个元素的长度为2则第5个元素的地址是（A）110（B）108（C）100（D）120（A）3.在n个结点的顺序表中算法的时间复杂度是O（1）的操作是：（A）访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）（B）在第i个结点后插入一个新结点（1≤i≤n）（C）删除第i个结点（1≤i≤n）（D）将n个结点从小到大排序（B）4.向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变平均要移动个元素（A）8（B）63.5（C）63（D）7（A）5.链接存储的存储结构所占存储空间：（A）分两部分一部分存放结点值另一部分存放表示结点间关系的指针（B）只有一部分存放结点值（C）只有一部分存储表示结点间关系的指针（D）分两部分一部分存放结点值另一部分存放结点所占单元数（B）6.链表是一种采用存储结构存储的线性表；（A）顺序（B）链式（C）星式（D）网状（D）7.线性表若采用链式存储结构时要求内存中可用存储单元的地址:（A）必须是连续的（B）部分地址必须是连续的（C）一定是不连续的（D）连续或不连续都可以（B）8．线性表Ｌ在情况下适用于使用链式结构实现（Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入（Ｃ）Ｌ中含有大量的结点（Ｄ）Ｌ中结点结构复杂（C）9．单链表的存储密度（Ａ）大于1；（Ｂ）等于1；（Ｃ）小于1；（Ｄ）不能确定（B）10．设a1、a2、a3为3个结点整数P034代表地址则如下的链式存储结构称为P034P0--a13--a24--A30（Ａ）循环链表（Ｂ）单链表（Ｃ）双向循环链表（Ｄ）双向链表四、简答题（每小题5分共10分）1.【严题集2.3②】试比较顺序存储结构和链式存储结构的优缺点在什么情况下用顺序表比链表好？答：①顺序存储时相邻数据元素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的优点：存储密度大（＝1？）存储空间利用率高缺点：插入或删除元素时不方便②链式存储时相邻数据元素可随意存放但所占存储空间分两部分一部分存放结点值另一部分存放表示结点间关系的指针优点：插入或删除元素时很方便使用灵活缺点：存储密度小（1）存储空间利用率低顺序表适宜于做查找这样的静态操作；链表宜于做插入、删除这样的动态操作若线性表的长度变化不大且其主要操作是查找则采用顺序表；若线性表的长度变化较大且其主要操作是插入、删除操作则采用链表2.【严题集2.1①】描述以下三个概念的区别：头指针、头结点、首元结点（第一个元素结点）在单链表中设置头结点的作用是什么？答：首元结点是指链表中存储线性表中第一个数据元素a1的结点为了操作方便通常在链表的首元结点之前附设一个结点称为头结点该结点的数