考研计算机综合数据结构试题

《考研计算机综合数据结构试题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、线性表（一）选择题：1．以下那一个术语与数据的存储结构无关？（）A．队列B.哈希表C.线索树D.双向链表2、一个算法应该是（B）。A．程序B．问题求解步骤的描述C．要满足五个基本特性D．A和C.3、数据结构中，与所使用的计算机无关的是数据的（）A．存储结构B．物理结构C．逻辑结构D．物理结构和存储结构4.算法的计算量的大小称为计算的（）。A．效率B．复杂性　C．现实性　D．难度5．下列说法，不正确的是（）。A．数据元素是数据的基本单位B．数据项是数据中不可分割的最小可标识单位C．数据可由若干个数据元素构成D．数据项可由若干个数据元素构成6．连续存储设计

2、时，存储单元的地址（）。A．一定连续B．一定不连续C．不一定连续D．部分连续，部分不连续7.线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂性为（）。A．O（i）B．O（1）C．O（n）D．O（i-1）8.对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（）。A．O(n)O(n)B.O(n)O(1)C.O(1)O(n)D.O(1)O(1)9.设单链表中结点的结构为（data，link）。已知指针q所指点是指针p所指结点的直接前驱，若在*q与*p之间插入结点*s，则应执行下列哪一个操作？（）。A．s－>link=p－>l

3、ink；p－>link=sB．q－>link=s；s－>link=pC．p－>link=s－>link；s－>link=pD．p－>link=s；s－>link=q10.在一个长度为n的顺序表的表尾插入一个新元素的渐进时间复杂度为（）。A．O（n）B．O（1）C．O（n2）D．O（log2n）11.表长为n的顺序存储的线性表，当在任何位置上插入一个元素的概率相等时，插入一个元素所需移动元素的平均个数为（）A．nB.n/2C.(n-1)/2D.(n+1)/212.循环链表的主要优点是（）A．不再需要头指针了。-31-B．已知某个结点的位置后，能很容易找到它的

4、直接前驱结点。C．在进行删除操作后，能保证链表不断开。D．从表中任一结点出发都能遍历整个链表。（二）应用题1、按增长率由小至大排列以下7个函数。2、数据的存储结构由哪四种基本的存储方法实现，并做以简要说明？3.线性表有两种存储结构：一是顺序表，二是链表。试问：（1）如果有n个线性表同时并存，并且在处理过程中各表的长度会动态变化，线性表的总数也会自动地改变。在此情况下，应选用哪种存储结构？为什么？（2）若线性表的总数基本稳定，且很少进行插入和删除，但要求以最快的速度存取线性表中的元素，那么应采用哪种存储结构？为什么？（三）算法设计题1．设计算法，求带表头的单

5、循环链表的表长。2.已知单链表L，写一算法，删除其重复结点。3.已知指针la和lb分别指向两个无头结点的单链表中的首结点。请编写函数完成从表la中删除自第i个元素开始的共len个元素并将它们插入到表lb中第j个元素之前，若lb中只有j-1个元素，则插在表尾。函数原型如下：intDeleteAndInsertSub(LinkList&la,LinkList&lb,inti,intj,intlen)；4．写一算法，将一带有头结点的单链表就地逆置，即要求逆置在原链表上进行，不允许重新构造新链表。图单链表的倒置25∧4525187629L29∧7625184525

6、L(a)(b)函数原型如下：voidLinkList_reverse(LinkList&L)；5．写一算法，将带有头结点的非空单链表中数据域值最小的那个结点移到链表的最前面。要求：不得额外申请新的链结点。函数原型如下：voiddelinsert(LinkList&L)；6．编写一个算法来交换单链表中指针P所指结点与其后继结点，HEAD是该链表的头指针，P指向该链表中某一结点。7．已知线性链表第一个链结点指针为list，请写一算法，将该链表分解为两个带有头结点的循环链表，并将两个循环链表的长度分别存放在各自头结点的数据域中。其中,线性表中序号为偶数的元素分解

7、到第一个循环链表中,序号为奇数的元素分解到第二个循环链表中。8.设A和B是两个单链表，其表中元素递增有序。-31-试写一算法将A和B归并成一个按元素值递减有序的单链表C，并要求辅助空间为O(1)。二、栈、队列和数组（一）选择题：1.一个栈的输入序列为1234，则（D）不可能是其出栈序列。A.1243B.2134C.1432D.43122.一个递归算法必须包括（B）。A.递归部分B.终止条件和递归部分C.迭代部分D.终止条件和迭代部分3.一个递归的定义可以用递归过程求解，也可以用非递归过程求解，但单从运行时间来看，通常递归过程比非递归过程（B）。A．较快B．

8、较慢C．相同D．以上答案都不对4.栈和队列都是（C）A．顺序存储的