数据结构(c语言版)程海英-课后习题.docx

《数据结构(c语言版)程海英-课后习题.docx》由会员分享，可在线阅读，更多相关《数据结构(c语言版)程海英-课后习题.docx（27页珍藏版）》请在第一文库网上搜索。

1、1.2.3.解释下列术语：数据、数据元素、数据对象、数据结构、存储结构、线性结构、算法、抽象数据类型。试举一个数据结构的例子，叙述其逻辑结构、存储结构及运算3方面的内容。选择题D在数据结构中，从逻辑上可以把数据结构分成（A.动态结构和静态结构C.线性结构和非线性结构2）与数据元素本身的形式、A.存储结构C.逻辑结构B.紧凑结构和非紧凑结构D.内部结构和外部结构内容、相对位置、个数无关的是数据的（B.存储实现D.运算实现3）通常要求同一逻辑结构中的所有数据元素具有相同的特性，这意味着（A.数据具有同一特点B.不仅数据元素所包含的数据项的个数要相同，而且对应数据项的类型要一致C.每个数据元素都一样

2、D.数据元素所包含的数据项的个数要相等4）以下说法正确的是（）。A.数据元素是数据的最小单位B.数据项是数据的基木单位C.数据结构是带有结构的各数据项的集合D.一些表面上很不相同的数据可以有相同的逻辑结构5）以下数据结构中，（）是非线性数据结构A.树B.字符串C.队D.栈4 .填空题D数据结构是一门研究非数值计算的程序设计问题中计算机的以及它们之1可的和运算等的学科。2） 数据结构被形式定义为（D,R）,其1PD是的有限集合，R是D上的有限集合。3） 数据结构包括数据的_、数据的和数据的这三个方面的内容。4） 线性结构中元素之间存在失系，树形结构中元素之间存在笑系，图形结构中元素之间存在关系。

3、5） 一个算法的效率可分为效率和效率。5 .试分析下面各算法的时间复杂度。1) x=90;y=100;whi1e(yO)if(x100)x=x-10;y-;e1sex+;2) for(i=0;ivn;i+)fbrG=O;jm;j+)aiU=O;3) for(inti=1;i=n;i+)fbr(intj=1;j=i;j4-+)s+;4) i=1;whi1e(i二n)i=i*2;5) i=0,s1=0,s2=0;whi1e(i+1y=o；whi1e(x=(y+1)*(y+1)y+;1 .线性表有两种存储结构，分别是顺序表和链表。试问：两种存储结构各有哪些主要优缺卢。八八2 .试分析线性表的特征并举

4、例说明。3 .选择题D在一个长度为n的顺序存储的线性表中，向第i个元素（IWiWn+1）位置插入一个新元素口寸，需要从后向前依次后移（）个元素。A.n-iCn-i-1B.n-i+1D.i2）在一个t度为n的顺序存储的线性表中，IW除第i个元素（IWiWn）时，需要从前向后依次前移（）个元素。A.n-iC.n-i-1B.n-i+1D.i3）在一个顺序表中任何位置插入一个元素的时间复杂性的量级为（）。A.O(n)C.0(1)B.O(n2)D.0(n2)4）在一个顺序表的表尾插入一个元素的时间复杂性的量级为（）。A.O（n）C.O（n*n）5）储最有利于进行（A.查找C.按值插入或IH除B.O（1）

5、D.O（1og2）线性表的链式存储比顺序存）操作。B.表尾插入或删除D.表头插入或删除6）在一个单链表中，若要在P所指向的结点之后插入一个新结点，则需要相继修改（）个指针域的值。A.1B.2C.3D.47）在一头指针为H的单链表中，若要向表头插入一个由指针p指向的结点，则应执行()操作。A.H=p;p-next=H;C.p-next=H;p=H;B.p-next=H;H=p;D.p-next=H-next;H-next=p;8）在一个表头指针为H的单链表中，若要在指针q所指结点的后面插入一个由指针p所指向的结点，则执行（）操作。A. q-next=p-next;p-next=q;B. pnex

6、t二qnext;q=p;C. qnext=pnext;pnext二pnext;Dp-next=q-next;q-next=p;4.填空题D顺序表中访问任意结点的时可复杂度均为，顺序表也称为随机存取的数据结构。2) 顺序表中逻辑上相邻的元素的物理位置相邻。单链表中逻辑上相邻的元素的物理位置相邻。3) 在单链表中，除了第一个结点外，任一结点的存储位置由指示。4)在n个结点的单链表中要IM除已知结点*P,需找到它的,其时间复杂度为O5)对于长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为,在表尾插入结点的时间复杂度为o6) 对于单链表，在表头插入结点的时间复杂性度为,在表尾插入结点的时间复杂

7、度为。5 .已知长度为n的线性表A采用顺序存储，编写时间复杂度为O(n)、空间复杂度为O(1)的算法，该算法删除线性表中所有值为item的数据元素。6 .设计一个算法，通过一遍扫描在单链表中确定值最大的结点。7 .编写在顺序表和带头结点的单链表上，统计出值为X的元素个数的算法，统计结果由函数值返回。&编写在顺序表和带头结点的单链表上，删除其值等于X的所有元素的算法。1 .栈和队列数据结构各有什么特点，什么情况下用到栈，什么情况下用到队列？2 .设有编号为1、2、3、4的4辆车，顺序进入一个栈式结构的站台，试写出这4辆车开出车站的所有可能的顺序（每辆车可能人站，可能不入站，时间也可能不相同）。3

8、 .选择题1） 栈的插入和删除操作在（）进行。A.栈顶B.栈底C.任意位置D.指定位子2）当利用大小为N的数组顺序存储一个栈时，假定用top=N表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。Atop+;B.top-;Ctop=0;Dtop=N-1;3）假定利用数组aN顺序存储一个栈，用top表示栈顶元素的下标位置，用top=1表示栈空，用top=N-I表示栈满，则该数组所能存储的栈的最大长度为（）A.N-IC.N+1B-ND.N+24）假定一个链接栈的栈顶指针用top表示，该链接栈为空的条件为（A.top!=NU11;C.top=NU11;B.top=top-next;

9、D.top!=top-next;5）在一个循环队列中，队首指针指向队首元素的（）位置。A.前一个C.当前B.后一个D.最后金八”y.rrf-,1.、4办工心人1J/）06）当利用大小为N的数组循环顺序存储一个队列时，该队列的最大长度为（M-OC.N7）时，首先需要（A.前移队首指针RM.1D.N+1从一个循环队列中删除元素）B.后移队首指针C.取出队首指针所指位置上的元素D.取出队尾指针所指位置上的元素8）假定循环队列的队首和队尾指针分别用f和I表示，则判断队空的条件为（）。A.f+1=rBr+1=fC.f=0Df=r4.填空题1) 队列的插入操作在进行,删除操作在进行。2)栈又称为表，队列又

10、称为表。3)在个用一维数组aN表示的顺序栈中，该栈所含元素的个数最少为个，最多为O4）假定一个链栈的栈顶指针为top,每个结点包含值域血ta和指针域next,当进行出栈运算时（假定栈非空），需要把栈顶指针top修改为的值。5）在带头结点的非空循坏链队中，假定队首和队尾指针分别为f和h当从中删除一个结点时，则需要将f-next赋值为的值。6）假定front和rear分别为链队的队首和队尾指针，则该链队中只有一个结点的条件为5 .假设正读和反读都相同的字符序列为“回文”，例如，abbT和NbcbT是回文，Ebc加，和oA-空串与空格串是相同的B. “te1”是“Te1eptone”的子串C.空串是

11、零个字符的串D.空串的长度等于1）07）以军嫌隹聊!勺是C是空格串A.BEIJING”是“BEIJING”的子串Bsomething”VttSomethiguC“BIT”=BITED.8）设有两个串S1和S2,则StrCompare（S1,S2）运算称做）0（B.模式匹配A.串连接D.串比较C.求子串）09）串的模式匹配是指（A.判断两个串是否相等B.对两个串比较大小C-找某字符在主串中第一次出现的位置D.找某子串在主串中第一次出现的第一个字符位置10)若SUbString(SUb,S,pos,1en)A示用Sub返向串S的笫pos个字符起长度为Ien的子串的操作，则对于S=DataStnIe

12、tUreSUbString(SUb,S,6,3)的结果为()。A1taStrB.Str”C“mi”D.以上均不正确11)若StrIndeX(S,T)表示求T在S中的位置的操作,则对于S=BeijingandNanjing”，T=jing”,Str1ndeX(S,T)的结果为(1A.2B.3C.4D.1612) S二“moming”，执行求子串函数SUbStr(S,2,2)后的结果为()。A.“mo”B.“or”C.“inD.“ng”13) SI=Good”,S2=Morning”,执行串连接函数ConcatStr(S1,S2)后的结果为()。A.GoodMomingB.GoodMorningC.“G00DM0RNINGD.44GOODMORNING14) S1二“good”,S2=morning”,执行函数SUbStr(S2,4,1enS