专升本数据结构试题库及答案

专升本数据结构试题库及答案选择题1.数据结构是一门研究非数值计算的程序设计问题中计算机的（）以及它们之间的关系和运算等的学科。A.操作对象B.计算方法C.逻辑存储D.数据映象答案：A分析：数据结构研究操作对象及其关系和运算，A正确；计算方法侧重算法求解，B不符；逻辑存储是数据的存储方式，C不准确；数据映象不是数据结构核心研究内容，D错误。2.算法分析的目的是（）。A.找出数据结构的合理性B.研究算法中的输入和输出关系C.分析算法的效率以求改进D.分析算法的易懂性和文档性答案：C分析：算法分析主要是评估算法效率，从而改进算法，C正确；数据结构合理性不是算法分析主要目的，A错误；研究输入输出关系不是核心，B错误；易懂性和文档性不是算法分析主要目标，D错误。3.线性表的顺序存储结构是一种（）的存储结构。A.随机存取B.顺序存取C.索引存取D.散列存取答案：A分析：顺序存储结构可通过下标直接访问元素，是随机存取，A正确；顺序存取是按顺序依次访问，B错误；索引存取需索引表，C错误；散列存取基于散列函数，D错误。4.带头结点的单链表head为空的判定条件是（）。A.head==NULLB.head>next==NULLC.head>next==headD.head!=NULL答案：B分析：带头结点单链表，头结点本身存在，判断为空看头结点后继是否为空，B正确；head为空是无头结点情况，A错误；C一般是循环链表情况，D不能判断为空。5.栈和队列的共同点是（）。A.都是先进先出B.都是先进后出C.只允许在端点处插入和删除元素D.没有共同点答案：C分析：栈是先进后出，队列是先进先出，A、B错误；栈在栈顶操作，队列在队头队尾操作，都只允许在端点处操作，C正确，D错误。6.一个栈的入栈序列是a,b,c,d,e，则栈的不可能的输出序列是（）。A.edcbaB.decbaC.dceabD.abcde答案：C分析：栈先进后出，A可依次入栈再出栈得到；B先入a,b,c,d，d出栈，e入栈出栈，c,b,a依次出栈；D依次入栈一个出栈一个；C中d出栈后，c出栈，e出栈，此时栈顶是b，不可能a先出栈，C不可能。7.若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为（）。A.1和5B.2和4C.4和2D.5和1答案：B分析：循环队列删除元素front=(front+1)%6，加入元素rear=(rear+1)%6。初始front=3，删除一个元素后front=(3+1)%6=4；初始rear=0，加入两个元素后rear=(0+2)%6=2。8.串是一种特殊的线性表，其特殊性体现在（）。A.可以顺序存储B.数据元素是一个字符C.可以链式存储D.数据元素可以是多个字符答案：B分析：串的数据元素是字符，这是其特殊之处，B正确；顺序存储和链式存储是线性表通用存储方式，A、C错误；串数据元素是单个字符，D错误。9.若串S1=’ABCDEFG’，S2=’9898’，S3=’’，S4=’012345’，执行concat(replace(S1,substr(S1,3,2),S3),substr(S4,2,3))其结果为（）。A.ABCFG234B.ABCFG123C.ABCG123D.ABCG234答案：B分析：substr(S1,3,2)得到’CD’，replace(S1,substr(S1,3,2),S3)将’CD’替换为’’得到’ABCFG’，substr(S4,2,3)得到’123’，concat连接后为’ABCFG123’。10.二维数组A[10..20][5..10]采用行序为主序存储，每个元素占4个存储单元，且A[10][5]的存储地址是1000，则A[18][9]的地址是（）。A.1208B.1212C.1368D.1328答案：D分析：行序为主序，先算前面元素个数。每行元素个数为105+1=6个，前面有1810=8行，这8行元素个数为8×6，第18行前面有95=4个元素，总元素个数为8×6+4=52个，每个元素占4个单元，A[18][9]地址为1000+52×4=1328。填空题1.数据的逻辑结构分为线性结构和（非线性结构）。分析：数据逻辑结构主要分为这两类。2.算法的五个重要特性是有穷性、确定性、可行性、（输入）和输出。分析：算法基本特性包含这五点。3.线性表L=(a1,a2,…,an)用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（(n1)/2）。分析：删除第i个元素需移动ni个元素，平均移动个数为(0+1+…+(n1))/n=(n1)/2。4.设栈S和队列Q的初始状态为空，元素e1,e2,e3,e4,e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2,e4,e3,e6,e5,e1，则栈S的容量至少应该是（3）。分析：根据出队序列模拟入栈出栈过程，可知栈中最多同时存在3个元素。5.已知一个栈的进栈序列是1,2,3,…,n，其输出序列为p1,p2,p3,…,pn，若p1=n，则pi=（ni+1）。分析：p1=n说明先全部入栈再依次出栈，所以pi=ni+1。6.设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有front=11，rear=19，则循环队列中还有（8）个元素。分析：元素个数=(rearfront+40)%40=(1911+40)%40=8。7.设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是（BCDEFEF）。分析：len(s2)=5，subs(s1,2,len(s2))得到’BCDEF’，subs(s1,len(s2),2)得到’EF’，连接后为’BCDEFEF’。8.已知二维数组A[m][n]采用行序为主序存储，每个元素占k个存储单元，且第一个元素的存储地址为LOC(A[0][0])，则A[i][j]的存储地址为（LOC(A[0][0])+(i×n+j)×k）。分析：行序为主序，前面i行有i×n个元素，第i行前面有j个元素，总偏移量为(i×n+j)×k。判断题1.数据的物理结构是指数据在计算机内的实际存储形式。（√）分析：物理结构就是数据在计算机中的存储形式。2.算法的时间复杂度都与问题的规模有关。（×）分析：有些算法时间复杂度是常数级，与规模无关。3.线性表的顺序存储结构比链式存储结构更有利于随机存取。（√）分析：顺序存储可直接通过下标随机访问元素，链式存储需遍历。4.栈和队列都是限制存取点的线性结构。（√）分析：栈在栈顶操作，队列在队头队尾操作，都是限制存取点。5.串的长度是指串中不同字符的个数。（×）分析：串长度是串中字符个数，不是不同字符个数。6.二维数组是其数组元素为一维数组的一维数组。（√）分析：可看作数组元素是一维数组的一维数组。简答题1.简述线性表的顺序存储结构和链式存储结构的优缺点。答案：顺序存储结构优点：可随机存取元素，存储密度大；缺点：插入删除操作需移动大量元素，存储空间预先分配，可能造成浪费或不足。链式存储结构优点：插入删除操作方便，无需预先分配空间；缺点：不能随机存取，每个结点需额外指针域，存储密度小。分析：顺序存储基于数组，可直接通过下标访问；链式存储通过指针连接，插入删除只需修改指针。2.什么是栈的“上溢”和“下溢”现象？答案：“上溢”是指栈已满，再进行入栈操作导致栈空间不足的情况；“下溢”是指栈为空，再进行出栈操作的情况。分析：栈有容量限制，满时入栈会溢出，空时出栈不合理。3.简述队列的特点，并说明循环队列的作用。答案：队列特点是先进先出，即先进入队列的元素先出队。循环队列作用是解决普通队列假溢出问题，充分利用存储空间。分析：队列按进入顺序出队，普通队列删除元素后前面空间不能再利用，循环队列可循环使用空间。4.简述串的模式匹配的概念。答案：串的模式匹配是指在主串中查找子串（模式串）第一次出现的位置。分析：常用于文本搜索等场景。算法设计题1.设计一个算法，将一个带头结点的单链表就地逆置。```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefreverseList(head):prev=Nonecurr=head.nextwhilecurr:next_node=curr.nextcurr.next=prevprev=currcurr=next_nodehead.next=prevreturnhead```分析：通过遍历链表，依次改变结点指针方向实现逆置。2.设计一个算法，判断一个栈中的元素是否中心对称。```pythonclassStack:def__init__(self):self.items=[]defis_empty(self):returnlen(self.items)==0defpush(self,item):self.items.append(item)defpop(self):ifself.is_empty():returnNonereturnself.items.pop()defpeek(self):ifself.is_empty():returnNonereturnself.items[1]defsize(self):returnlen(self.items)defis_symmetric(stack):temp_stack=Stack()whilenotstack.is_empty():temp_stack.push(stack.pop())whilenottemp_stack.is_empty():item1=temp_stack.pop()stack.push(item1)item2=stack.pop()ifitem1!=item2:returnFalsereturnTrue```分析：先将栈元素放入临时栈，再依次比较两个栈出栈元素是否相同。3.设计一个算法，将两个有序链表合并为一个有序链表。```pythonclassListNode:def__init__(self,val=0,next=None):self.val=valself.next=nextdefmergeTwoLists(l1,l2):dummy=ListNode(0)curr=dummywhilel1andl2:ifl1.val<l2.va