搜索
第一章习题判断题1．数据元素是数据的最小单位。()2．记录是数据处理的最小单位。()3．数据的逻辑结构是指数据的各数据项之间的逻辑关系。()4．算法的优劣与算法描述语言无关，但与所用计算机有关。()5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。(T)6．算法可以用不同的语言描述，如果用C语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。()7．程序一定是算法。()8．数据的物理结构是指数据在计算机内的实际存储形式。(T)9．数据结构的抽象操作的定义与具体实现有关。()10．在顺序存储结构中，有时也存储数据结构中元素之间的关系。()11．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()12．数据结构的基本操作的设置的最重要的准则是，实现应用程序与存储结构的独立。(T)13．数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构。()答案1．×2．×3．×4．×5．√6．×7．×8．√9．×10．×11．×12．√13．×填空题1．数据的物理结构包括____的表示和____的表示。2．对于给定的n个元素,可以构造出的逻辑结构有（1），（2），（3），（4）四种。3．数据的逻辑结构是指_____。4．一个数据结构在计算机中______称为存储结构。5．抽象数据类型的定义仅取决于它的一组（1），而与（2）无关，即不论其内部结构如何变化，只要它的（3）不变，都不影响其外部使用。6．数据结构中评价算法的两个重要指标是_______。7．数据结构是研讨数据的（1）和（2），以及它们之间的相互关系，并对与这种结构定义相应的（3），设计出相应的（4）。8．一个算法具有5个特性:（1）、（2）、（3），有零个或多个输入、有一个或多个输出。9．计算机执行下面的语句时，语句s的执行次数为_______。for(i=l；in-l；i++)for(j=n;j=i;j--)s；10.下面程序段的时间复杂度为________。if(n1)sum=1；for(i=0;sumn;i++)sum+=1;11．在有n个选手参加的单循环赛中，总共将进行______场比赛。答案1．数据元素数据元素间关系2．集合线性结构树形结构图状结构或网状结构3．数据的组织形式，即数据元素之间逻辑关系的总体而逻辑关系是指数据元素之间的关联方式或称“邻接关系”4．表示（又称映像）5．（1）逻辑特性（2）在计算机内部如何表示和实现（3）数学特性6．算法的时间复杂度和空间复杂度7．（1）逻辑结构（2）物理结构（3）操作（运算）（4）算法8．（1）有穷性（2）确定性（3）可行性9.(n+3)(n-2)/210.O(n)11.n(n-1)/2选择题(带*是超出目前知识点的题目)1．计算机算法指的是(1），它必须具备（2）这三个特性。(1)A．计算方法B．排序方法C．解决问题的步骤序列D．调度方法(2)A．可执行性、可移植性、可扩充性B．可执行性、确定性、有穷性C．确定性、有穷性、稳定性D．易读性、稳定性、安全性2．一个算法应该是（）。A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C．3．从逻辑上可以把数据结构分为（）两大类。A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构4*．以下与数据的存储结构无关的术语是（）。A．循环队列B．链表C．哈希表D．栈5．在下面的程序段中，对x的赋值语句的频度为（）。for(i=1;i=n;i++)for(j=1;j=n;j++)X++;A．O(2n)B．O(n)C．O(n2)D．O(log2n)6．以下数据结构中，（）是非线性数据结构。A．树B．字符串C．队D．栈7*．下列数据中，（）是非线性数据结构A．栈B．队列C．完全二叉树D．堆8．连续存储设计时，存储单元的地址（）。A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续9*．以下属于逻辑结构的是（）。A．顺序表B．哈希表C．有序表D．单链表答案1．1．C1．2．B2．B3．C4．D5．C6．A7．C8．A9．C应用题1．数据结构是一门研究什么内容的学科？2．数据元素之间的关系在计算机中有几种表示方法？各有什么特点？3．评价一个好的算法，您是从哪几方面来考虑的？4．根据数据元素之间的逻辑关系，一般有哪几类基本的数据结构？5．若将数据结构定义为一个二元组（D，R）,说明符号D，R应分别表示什么？6．若有100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写出这些结构？7．在编制管理通讯录的程序时,什么样的数据结构合适?为什么?第二章习题判断题1．链表中的头结点仅起到标识的作用。()2．顺序存储结构的主要缺点是不利于插入或删除操作。(T)3．线性表采用链表存储时，结点和结点内部的存储空间可以是不连续的。(T)4．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。()5．对任何数据结构链式存储结构一定优于顺序存储结构。()6．顺序存储方式只能用于存储线性结构。()7．集合与线性表的区别在于是否按关键字排序。()8．所谓静态链表就是一直不发生变化的链表。()9．线性表的特点是每个元素都有一个前驱和一个后继。()10．取线性表的第i个元素的时间同i的大小有关。()11．循环链表不是线性表。()12．线性表只能用顺序存储结构实现。()13．线性表就是顺序存储的表。()14．为了很方便的插入和删除数据，可以使用双向链表存放数据。(T)15．顺序存储方式的优点是存储密度大，且插入、删除运算效率高。()答案1．×2．√3．√4．×5．×6．×7．×8．×9．×10．×11．×12．×13．×14．√15．×填空题1．当线性表的元素总数基本稳定，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时,应采用_______存储结构。2．线性表L=（a1,a2,…,an）用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是________。3．设单链表的结点结构为(data,next)，next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点,若将结点y插入结点x之后，则需要执行以下语句:_______；______;4．在一个长度为n的顺序表中第i个元素（1=i=n）之前插入一个元素时，需向后移动________个元素。5．在单链表中设置头结点的作用是________。6．对于一个具有n个结点的单链表，在已知的结点*p后插入一个新结点的时间复杂度为________,在给定值为x的结点后插入一个新结点的时间复杂度为________。7．根据线性表的链式存储结构中每一个结点包含的指针个数，将线性链表分成________和_______。8．在双向循环链表中,向p所指的结点之后插入指针f所指的结点，其操作是_______、_______、_______、________。9．在双向链表结构中，若要求在p指针所指的结点之前插入指针为s所指的结点，则需执行下列语句：s-next=p；s-prior=________；p-prior=s；________=s；10．链接存储的特点是利用________来表示数据元素之间的逻辑关系。11．顺序存储结构是通过________表示元素之间的关系的;链式存储结构是通过________表示元素之间的关系的。12．对于双向链表,在两个结点之间插入一个新结点需修改的指针共______个，单链表为_______个。13．循环单链表的最大优点是：________。14．已知指针p指向单链表L中的某结点，则删除其后继结点的语句是：________15．带头结点的双循环链表L中只有一个元素结点的条件是：________16．在单链表L中，指针p所指结点有后继结点的条件是：__17．带头结点的双循环链表L为空表的条件是：________。18．在单链表p结点之后插入s结点的操作是：_______。答案1．顺序2．（n-1）/23．py-next=px-next;px-next=py4．n-i+15．主要是使插入和删除等操作统一，在第一个元素之前插入元素和删除。第一个结点不必另作判断。另外，不论链表是否为空，链表指针不变。6．O(1)，O(n)7．单链表，双向链表8．f-next=p-next;f-prior=p;p-next-prior=f;p-next=f;9．P-priors-prior-next10．指针11．物理上相邻指针12．4213．从任一结点出发都可访问到链表中每一个元素。14．u=p-next;p-next=u-next;free(u);15．L-next-next==L16．p-nextNULL17.L-next==L&&L-prior==L18．s-next=p-next;p-next=s;选择题1．下述哪一条是顺序存储结构的优点？（）A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（）A．线性表采用顺序存储，必须占用一片连续的存储单元。B．线性表采用顺序存储，便于进行插入和删除操作。C．线性表采用链接存储，不必占用一片连续的存储单元。D．线性表采用链接存储，便于插入和删除操作。3．线性表是具有n个（）的有限序列（n0）。A．表元素B．字符C．数据元素D．数据项E．信息项4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表6．静态链表中指针表示的是（）A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址7．链表不具有的特点是（）A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比8．下面的叙述不正确的是（）A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B．线性表在链式存储时，查找第i个元素的时间同i的值无关C．线性表在顺序存储时，查找第i个元素的时间同i的值成正比D．线性表在顺序存储时，查找第i个元素的时间同i的值无关9．(1)静态链表既有顺序存储的优点，又有动态链表的优点。所以，它存取表中第i个元素的时间与i无关。(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。(3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。以上错误的是（）A．（1），（2）B．（1）C．（1），（2）,(3)D．（2）10．若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1=i=n+1)。A．O(0)B．O(1)C．O(n)D．O(n2)11．对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。A．O(n)O(n)B．O(n)O(1)C．O(1)O(n)D．O(1)O(1)12．线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）A．O（i）B．O（1）C．O（n）D．O（i-1）13．非空的循环单链表head的尾结点p满足（）。A．p-link=headB．p-link=NILC．p=NILD．p=head14．循环链表H的尾结点P的特点是（）。A．P-NEXT=HB．P-NEXT:=H-NEXTC．P=HD．P=H-NEXT答案1．A2．B3．C4．A5．D6．C7．B8．B,C9．B10．C11．C12．C13．A14．A应用题1．线性表有两种存储结构：一是顺序表，二是链表。试问：（1）如果有n个线性表同时并存，并且在处理过程