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

1第一章概论自测题答案姓名班级题号一二三四五六总分题分3315982015100得分一、填空题（每空1分，共33分）1.一个计算机系统包括硬件系统和软件系统两大部分。2.一台计算机中全部程序的集合，称为这台计算机的软件资源/（系统）。3.计算机软件可以分为系统软件和应用软件两大类。科学计算程序包属于应用软件，诊断程序属于系统软件（工具）。4.一种用助忆符号来表示机器指令的操作符和操作数的语言是汇编语言。5.数据结构是一门研究非数值计算的程序设计问题中计算机的操作对象以及它们之间的关系和运算等的学科。6.数据结构被形式地定义为（D,R），其中D是数据元素的有限集合，R是D上的关系有限集合。7.数据结构包括数据的逻辑结构、数据的存储结构和数据的运算这三个方面的内容。8.数据结构按逻辑结构可分为两大类，它们分别是线性结构和非线性结构。9.线性结构中元素之间存在一对一关系，树形结构中元素之间存在一对多关系，图形结构中元素之间存在多对多关系。10．在线性结构中，第一个结点没有前驱结点，其余每个结点有且只有1个前驱结点；最后一个结点没有后续结点，其余每个结点有且只有1个后续结点。11.在树形结构中，树根结点没有前驱结点，其余每个结点有且只有1个前驱结点；叶子结点没有后续结点，其余每个结点的后续结点数可以任意多个。12.在图形结构中，每个结点的前驱结点数和后续结点数可以任意多个。13．数据的存储结构可用四种基本的存储方法表示，它们分别是顺序、链式、索引和散列。14.数据的运算最常用的有5种，它们分别是插入、删除、修改、查找、排序。15.一个算法的效率可分为时间效率和空间效率。16.〖00年省统考〗任何一个C程序都由一个主函数和若干个被调用的其它函数组成。17.【00年省统考题】变量一经说明，就确定该变量的取值范围（即存储单元）及确定变量所允许的运算。2二、单项选择题（每小题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.计算机算法指的是：3A)计算方法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=%d,y=%d”,x,y);elseprintf(“输入数据错！”);试写出当x分别为18，8时的执行结果。答：运行结果为：x=18，y=36x=8，y=运行前的值，且从x＝30开始为数据错2.longintfact(n)intn;{longf;if(n1)f=n*fact(n-1);elsef=1;return(f);}main(){intn;longy;n=5;y=fact(n);printf(“%d,%ld\n”,n,y);}答：运行结果为：5，120此题为递归运算4五、【严题集1.8④】分析下面各程序段的时间复杂度（每小题5分，共20分）六、设有数据逻辑结构S=（D,R），试按各小题所给条件画出这些逻辑结构的图示，并确定相对于关系R，哪些结点是开始结点，哪些结点是终端结点？（每小题5分，共15分）1.【严蔚敏习题集P71.3②】D={d1,d2,d3,d4}R={(d1,d2),(d2,d3),(d3,d4)}答：d1→d2→d3→d4d1—无直接前驱，是首结点d4—无直接后继是尾结点2.D={d1,d2,…,d9}R={(d1,d2),(d1,d3),(d3,d4),(d3,d6),(d6,d8),(d4,d5),(d6,d7),(d8,d9)}答：此图为树形结构d1—无直接前驱，是根结点d2,d5,d7,d9—无直接后继是叶子结点3.D={d1,d2,…,d9}R={(d1,d3),(d1,d8),(d2,d3),(d2,d4),(d2,d5),(d3,d9),(d5,d6),(d8,d9),(d9,d7),(d4,d7),(d4,d6)}答：此图为图形结构d1，d2—无直接前驱，是开始结点d6,d7—无直接后继是终端结点(2)(3)2.s=0;fori=0;in;i++)for(j=0;jn;j++)s+=B[i][j];sum=s;答：O（n2）1.for(i=0;in;i++)for(j=0;jm;j++)A[i][j]=0;答：O（m*n）3.x=0;for(i=1;in;i++)for(j=1;j=n-i;j++)x++;解：因为x++共执行了n-1+n-2+……＋1=n(n-1)/2，所以执行时间为O（n2）4.i=1;while(i=n)i=i*3;答：O（log3n）5第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.顺序存储方式只能用于存储线性结构。错误。顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构，例如完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。（后一节介绍）6（×）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．线性表Ｌ在情况下适用于使用链式结构实现。（Ａ）需经常修改Ｌ中的结点值（Ｂ）需不断对Ｌ进行删除插入（Ｃ）Ｌ中含有大量的结