专升本数据结构试题解析

第二部分练习题分析练习题的第二部分分析第一章简介1.1选择题算法的时间复杂性取决于(c)A)问题的规模b)待处理数据的初始状态C) A和b回答 c2.计算机算法表示解决问题的步骤顺序，并且(b)必须具有三个特性。a)可执行性、可移植性、可扩展性b)可执行性、确定性、贫穷性c)确定性、贫穷、稳定性d)可读性、稳定性、安全性回答 b5.数据结构在逻辑上可分为(c)两类。a)动态结构，静态结构b)顺序结构，链结构c)线性结构，非线性结构d)基本结构，构造结构回答 c6.在以下程序段中，为x指定值的语句频率为(c)for(I=0)；I=1；I-)for(j=1)；j=I；j)If (AjAj 1)Aj和Aj 1的交换；A.O(n)B) O(nlog2n)C) O(n3)D) O(n2)回答 d1.2填空2.可以为给定n个元素配置的逻辑结构是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _(1)集(2)线性结构(3)树状结构(4)图形结构或网格结构4.数据结构中评估算法的两个重要指标是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。答案算法的时间复杂性和空间复杂性。5.数据结构是讨论该数据的_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _(1)逻辑结构(2)物理结构(3)操作(运算)(4)算法。算法具有五个特性，具有零个或多个输入和一个或多个输出。【答案】(1)贫困性(2)确定性(3)可行性。9.被称为以下过程段落for(I=n)；i0；I-) 门1 x=x 1；门2for(j=n；j=I；J-) 门3y=y 1；门4语句1的执行频率为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _，语句2的执行频率为_ _ _ _ _ _ _ _ _ _ _ _【答案】(1)n 1 (2)n (3)n(n 3)/2 (4)n(n 1)/210.在下面的程序段中，x的赋值语句的频率为_ _ _ _ _ _ _ _ _ _ _ _ _(以n表示的函数)for(I=0)；in；I)for(j=0)；地；地。j)for(k=0)；kj；k)X=x delta【答案】1 (1 2) (1 2 3).(1 2.n)=n (n 1) (n 2)/6，O(n3)11.在下面的程序段中，带下划线的语句执行的次数的个数是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _I=1；while(I=I；j-)s；回答 (n 3)(n-2)/213.以下过程段的时间复杂性为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _。(n1)sum=1；for(I=0)；sumprior=q；q-next=p；p-prior-next=q；q-prior=p-prior；b)q-prior=p-prior；p-prior-next=q；q-next=p；p-prior=q-next；c)q-next=p；p-next=q；p-prior-next=q；q-next=p；d)p-prior-next=q；q-next=p；q-prior=p-prior；p-prior=q；回答 d4.在具有n个节点的单个已排序链接列表中插入新节点并保持其顺序的时间复杂性如下()A)O(nlog2n)B) O(1)C) O(n)D) O(n2)回答 c5.在使用h作为头指针的单个循环链中，p指针指向链的结束节点的条件为()A)p-next=NULLB) p-next=hC)p-next-next=hD) p-data=-1回答 b6.对于具有n个节点的线性表，设置单个链接表的时间复杂性如下()A)O(n) B) O(1) C)O(nlog2n) D) O(n2)回答 a8.从双向关联列表存储结构中删除p指向的节点时，必须修改指针()a)p-prior-next=p-nexttp-next-prior=p-prior；b)p-prior=p-prior-priorp-prior-next=p；c)p-next-prior=PP-next=p-next-nextd)p-next=p-prior-priorp-prior=p-next-next；回答 a9.如果路线表以链式存储，则该元素地址()a)必须连续b)必须不连续c)某些地址是否连续d)连续回答 d2.2填空1.定线表格L=(a1，a2，an)显示为数组，并且假定删除表中任意元素的概率相同，则删除一个元素时需要移动元素的平均数量为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _回答 (n-1)/22.在单个链接列表中设置第一个节点的角色是_ _ _ _ _ _ _ _ _ _ _ _ _ _ _。“回答”主要是统一插入和删除等操作，在第一个元素前插入元素，删除第一个节点，无需单独判断。此外，无论关联的列表是否为空，关联的列表头指针都不会更改。3.线表的顺序存储通过_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _反映元素之间的逻辑关系，而链存储结构则通过_ _ _ _ _ _ _ _ _ _ _ _ _ _ _反映元素之间的逻辑关系回答(1)数据元素的前后顺序(2)元素的指针4._ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _存储结构在访问操作频繁、插入和删除极少的情况下最节省时间。相反，使用_ _ _ _ _ _ _ _ _ _ _ _ _ _ _存储结构最节省时间。【答案】(1)顺序(2)链5.对于具有n个节点的单个链接，在已知节点*p之后插入新节点的时间复杂性为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _回答 (1)O(1)(2)O(n)7.对于双向连接的列表，需要修改的指针为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _【答案】(1)4 (2)28.循环单个列表的最大优点是_ _ _ _ _ _ _ _ _ _ _ _ _ _。所有节点都可以访问连接的列表中的每个元素。9.要在不领导节点的单个链接中的第一个节点*p节点之前插入*s节点，请执行以下操作：s-next=_ _ _ _ _ _ _ _ _ _ _ _ _ _；p-next=s；t=p-data；p-data=_ _ _ _ _ _ _ _ _ _ _ _ _ _ _；s-data=_ _ _ _ _ _ _ _ _ _ _ _ _ _ _；回答 (1)p-next (2)s-data(3) t10.线型表，其中每个元素占用4个存储设备，并且使用第一个地址为100的顺序存储结构，下标为11的(第12个)元素的存储地址为_ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _ _【回答】14411.引领节点的双环链接列表l中只有一个元素节点的条件是_ _ _ _ _ _ _ _ _ _ _ _ _。回答 L-next-next=L2.3判决问题1.取得线性表格第I个元素的时间与I的大小相关。()答案。【】2.先声表的特点是每个元素都有一个前兆，一个后缀答案。【】3.顺序存储方法的优点是存储密度高，插入、删除操作效率高()答案。【】4.如果连接了行列表，则节点的存储空间可能不连续()(也可以打印部分。)5.linklist是使用链存储结构的线性表，在执行插入、删除操作时，它在链接列表中的效率高于顺序存储结构()(也可以打印部分。)6.顺序存储方法只能用于存储线性结构()答案。【】线性结构、树状结构和图形结构可以按顺序存储表示法。9.顺序存储结构的主要缺点是对插入或删除操作不利()(也可以打印部分。)10.顺序存储方法不太有效地插入和删除，因此不如链存储方法()答案。【】2.4编程问题1.将序列表va中的数据元素设置为升序。通过在顺序表中的适当位置插入x，设计保持表顺序的算法。算法源代码Voidinsert _ sqlist (sqlistva，int x)/*在升序表va中插入x */ int I；if(va . length MAXSIZE)return；for(I=va . length-1；va . elemIXi=0；I-)va . elemI 1=va . elemI；va . elemI 1=x；Va.length/*Insert_SqList*/2.A=(a1，a2，am)和B=(b1，B2，bn)设置为顺序表，设计比较a，b大小的算法(算法中不要破坏原始表a和b)。算法分析比较顺序表a和b，将结果表示为返回值，值为1，表示ab。如果值为-1，则为AB.elemi？1:-1；if(a . length=b . length)return 0；Return A.lengthB.length？1:-1；/*当两个排序表可以相互比较的部分完全相同时，哪个更长，哪个更大*/*ListComp */3.已知指针ha和HB分别指向两个单个链路表的头节点，这两个链路表的长度分别称为m和n。设计连接两个连接列表的算法，使一个表中的第一个元节点连接到另一个表中最后一个节点的后面，假定指向连接列表中第一个节点的指针HC，请求算法在尽可能短的时间内完成连接操作。算法分析1)单个链路列表ha的头节点用作关联链路列表的头节点。也就是说，HC=ha2)找到指针p指向的单个链路列表ha的最后一个节点。即p-next=null；3)将单链路列表HB中的第一个元节点(不是头节点)连接到p之后，即p-next=h B- next；4)回收单列表HB的头节点空间算法源代码Void list concat (link list ha，link list HB，link list * HC)/*连接的列表HB在ha之后连接的列表hc*/* hc=