(NEW)湖南大学信息科学与工程学院866数据结构历年考研真题汇编

2022年湖南大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e 的运算是（）。

A.head（tail（LS））B.tail（head（LS））C.head（tail（head（tail（LS））））D.head（tail（tail（head（LS））））2、下述文件中适合于磁带存储的是（）。

A.顺序文件B.索引文件C.哈希文件D.多关键字文件3、连续存储设计时，存储单元的地址（）。

A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}， E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>， <V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。

A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V75、下列关于AOE网的叙述中，不正确的是（）。

A.关键活动不按期完成就会影响整个工程的完成时间B.任何一个关键活动提前完成，那么整个工程将会提前完成C.所有的关键活动提前完成，那么整个工程将会提前完成D.某些关键活动若提前完成，那么整个工程将会提前完成6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。

A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝27、下列选项中，不能构成折半查找中关键字比较序列的是（）。

计算机专业基础综合数据结构（集合）历年真题试卷汇编1(总分：82.00，做题时间：90分钟)一、综合题(总题数：25，分数：72.00)1.试用关键字序列(33，10，45，20，53，43，31，15，65，40)，构造哈希(Hash)表，设哈希函数为：H(key)=key％11，其中key为关键字，％为求余运算符；用开放定址法处理冲突，用线性探测再散列法查找空位，用长度为14的数据元素组A[14]表示哈希表。

(1)画出该哈希表的存储结构图；(2)假定每个元素的查找概率相等，计算查找成功时的ASL；(3)计算查找不成功时的ASL。

【华中科技大学2007四、25(10分)】__________________________________________________________________________________________正确答案：(正确答案：成功 =(6*1+2*3+5+7)／10=24／10(3)ASL 失败=(4+3+2+1+2+1+1+2+1+9+8)／11=34／1 1。

计算方法参见上面58题(3)。

)2.采用哈希函数H(k)=3*k mod 13并用线性探测开放地址法处理冲突，在散列地址空间[0．．12]中对关键字序列22，41，53，46，30，13，1，67，51。

(1)构造哈希表(画示意图)；(2)装填因子；等概率下(3)成功的和(4)不成功的平均查找长度。

【北京工业大学2000三(8分)】【烟台大学2007四、4(10分)】__________________________________________________________________________________________正确答案：(正确答案：装填因子=9／13=0．7 (3)ASL SUCC =11／9 (4)ASL UNSUCC =29／13)3.设散列表长度为14，散列函数，其中i为键值中第一个字母在字母表中的序号，若键值的输入顺序为Jan，Feb，Mar，Apr，May，Jun，Jul，Aug，Sep，Oct，Nov，Dec，用拉链法处理冲突，要求：(1)构造散列表；(2)求出在等概率情况下，查找成功的平均查找长度。

计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编4(总分：60.00，做题时间：90分钟)一、综合题(总题数：13，分数：26.00)1.简述广义表属于线性结构的理由。

【西北大学2000一、5(3分)】（分数：2.00）__________________________________________________________________________________________ 2.数组、广义表与线性表之间有什么样的关系?【西北工业大学1998一、2(4分)】（分数：2.00）__________________________________________________________________________________________ 3.什么是广义表?请简述广义表和线性表的主要区别。

【北京大学1997二、2(5分)】（分数：2.00）__________________________________________________________________________________________4.求下列广义表的运算结果。

【南京航空航天大学1998三(10分)】(1)CAR(CDR(((a，b)，(c，d，(e，f)))(2)CDR(CAR(((a，6b)，(c，d，(e，f)))(3)CAR(CDR[(CAR(((a，b)，(e，f))))(4)CDR(CAR(CDR(((a，b)，(e，f))))(5)CDR(CDR(CAR(((a，b)，(e，f))))注：CAR运算相当于有些教材中的Head运算，CDR运算相当于Tail运算。

（分数：2.00）__________________________________________________________________________________________ 5.画出下列广义表的存储结构图，并利用取表头和取表尾的操作分离出原子e。

计算机专业基础综合数据结构（排序）历年真题试卷汇编1(总分72,考试时间90分钟)1. 单项选择题1. 下列序列中，( )是执行第一趟快速排序后所得的序列。

【福州大学1998一、9(2分)】A. [68，11，18，69] [23，93，73]B. [68，11，69，23] [18，93，73]C. [93，73][68，11，69，23，18]D. [68，11，69，23，18] [93，73]2. 适合并行处理的排序算法是( )。

【西安电子科技大学2005一、8(1分)】【电子科技大学2005一、8(1分)】A. 选择排序B. 快速排序C. 希尔排序D. 基数排序3. 一组记录的关键字为(46，79，56，38，40，84)，则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。

【北京交通大学2005一、8(2分)【燕山大学2001一、4(2分)】A. (38，40，46，56，79，84)B. (40，38，46，79，56，84)C. (40，38，46，56，79，84)D. (40，38，46，84，56，79)4. 下列排序算法中，( )算法可能会出现下面的情况：初始数据有序时，花费的时间反而最多。

【中南大学2005一、4(2分)】A. 快速排序B. 堆排序C. 希尔排序D. 冒泡排序5. 将一组无序的数据重新排列成有序序列，其方法有：( )。

【武汉理工大学2004一、8(3分)】A. 拓扑排序B. 快速排序C. 堆排序D. 基数排序6. 就平均性能而言，目前最好的内排序方法是( )排序法。

【西安电子科技大学1998一、9(2分)】A. 冒泡B. 希尔插，AC. 交换D. 快速7. 如果只想得到1000个元素组成的序列中第5个最小元素之前的部分排序的序列，用( )方法最快。

【清华大学1998一、2(2分)】A. 起泡排序B. 快速排列C. Shell排序D. 堆排序E. 简单选择排序8. 若要从1000个元素中选出前10个最小的元素，( )是最适合的算法。

计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编1计算机专业基础综合数据结构（数组和广义表）历年真题试卷汇编1(总分：64.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：34.00)1.数组A[0．．5，0．．6]的每个元素占5个字节，将其按列优先次序存储在起始地址为1000的内存单元中，则元素A[5，5]的地址是( )。

【南京理工大学2001一、13(1．5分)】A.1 175 √B.1 180C.1205D.12102.设7行6列的数组a以列序为主序顺序存储，基地址为1024，每个元素占2个存储单元，第4行第5列的元素(假定无第0行第0列)的存储地址是( )。

【华中科技大学2006一、3(2分)】A.1068B.1086 √C.1084D.10663.若6行5列的数组以列序为主序顺序存储，基地址为1000，每个元素占2个存储单元，则第3行第4列的元素(假定无第0行第0列)的地址是( )。

【华中科技大学2004一、4(1分)】A.1040 √B.1042C.1026D.备选答案A，B，C都不对二维数组A的元素都是6个字符组成的串，行下标i的范围从0到8，列下标j的范围从1到10。

从供选择的答案中选出应填入下列关于数组存储叙述中( )内的正确答案。

(1)存放A至少需要( )个字节；(2)A 的第8 N一和第5行共占( )个字节；(3)若A按行存放，元素A[8，5]的起始地址与A按列存放时的元素( )的起始地址一致。

【山东工业大学2000三、1(4分)】【山东大学1998三、1(4分)】（分数：6.00）(1).(1)A.90B.180C.240D.270E.540 √(2).(2)A.108 √B.1 14C.54D.60E.150(3).(3)A.A[8，5]B.A[3，10] √C.A[5，8]D.A[0，9]4.设二维数组A[1．．m，1,n](即m行n列)按行存储在数组研1一m*n]中，则二维数组元素A[i，j]在一维数组B中的下标为( )。

计算机专业基础综合数据结构（线性表）历年真题试卷汇编4(总分：66.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.静态链表中指针表示的是( )。

【中南大学2003二、2(1分)】A.下一元素的地址B.内存储器的地址C.下一元素在数组中的位置√D.左链或右链指向的元素的地址2.链表不具有的特点是( )。

【电子科技大学2012一、3(2分)】【福州大学1998一、8(2分)】【南京理工大学2005一、13(1分)】A.插入、删除不需要移动元素B.可随机访问任一元素√C.不必事先估计存储空间D.所需空间与线性长度成正比3.在n个结点的线性表的数组实现中，算法的时间复杂性是O(1)的操作是( )。

【哈尔滨工业大学2003二、1(1分)】A.访问第i个结点(1≤i≤n)和求第i个结点的直接前驱(2≤i≤n) √B.在第i个结点后插入一个新结点(1≤i≤n)C.删除第i个结点(1≤f≤n)D.以上都不对4.(1)静态链表既有顺序存储的优点，又有动态链表的优点。

所以，它存取表中第f个元素的时间与i无关。

(2)静态链表中能容纳的元素个数的最大数在表定义时就确定了，以后不能增加。

(3)静态链表与动态链表在元素的插入、删除上类似，不需做元素的移动。

以上错误的是( )。

【南京理工大学2000一、3(1．5分)】A.(1)，(2)B.(1) √C.(1)，(2)，(3)D.(2)5.静态链表与动态链表相比，其缺点是( )。

【北京理工大学2006九、5(1分)】A.插入、删除时需移动较多数据B.有可能浪费较多存储空间√C.不能随机存取D.以上都不是静态链表首先要定义一个一维数组空间，每个数组元素有两个分量，一是数据元素的值，二是指针。

指针指向下一个元素在数组中的位置(下标)，插入和删除时只需修改指针，不移动数据。

不能随机存取。

若定义数组太大，有可能浪费较多存储空间。

6.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为( )(1≤i≤n+1)。

计算机专业基础综合数据结构（图）历年真题试卷汇编5(总分：52.00，做题时间：90分钟)一、填空题(总题数：15，分数：30.00)1.构造连通网最小生成树的两个典型算法是__________。

【北京科技大学1998一、5】__________________________________________________________________________________________正确答案：(正确答案：普里姆(Ptim)算法和克鲁斯卡尔(Kruskal)算法)2.求图的最小生成树有两种算法，__________算法适合于求稀疏图的最小生成树。

【南京理工大学2001二、6(2分)】【北京交通大学2005二、7(2分)】__________________________________________________________________________________________正确答案：(正确答案：克鲁斯卡尔)3.Prim(普里姆)算法适用于求__________的网的最小生成树；Kruskal(克鲁斯卡尔)算法适用于求__________的网的最小生成树。

【厦门大学1999一、4(20％／4)】__________________________________________________________________________________________正确答案：(正确答案：边稠密边稀疏)4.克鲁斯卡尔算法的时间复杂度为__________，它对__________图较为适合。

【中科院计算所1999二、3(2分)】__________________________________________________________________________________________正确答案：(正确答案：O(eloge)边稀疏)5.下面描述的是一种构造最小生成树算法的基本思想。

计算机专业基础综合数据结构（串）历年真题试卷汇编2(总分：40.00，做题时间：90分钟)一、综合题(总题数：4，分数：8.00)1.如果两个串含有相等的字符，能否说它们相等?【西安电子科技大学2000一、3(5分)】（分数：2.00）__________________________________________________________________________________________ 2.设S1、S2为串，请给出使S1／／$2=S2／／S1成立的所有可能的条件(／／为连接符)。

【国防科技大学1999一】【长沙铁道学院1997三、5(3分)】（分数：2.00）__________________________________________________________________________________________ 3.已知：s=‘(xyz)+*’，t=’(x+z)*’。

试利用联结、求子串和置换等基本运算，将s转化为t。

【北方交通大学1996一、3(5分)】【山东科技大学2002一、6(5分)】（分数：2.00）__________________________________________________________________________________________ 4.s是字符数组，s[0]中存放的是该字符串的有效长度，假设s[1．．7]中字符串的内容为"abcabaa"，说明下列程序的功能及执行结果。

#define len 8 int k． n[len]， char s[len]=“7abcabaa”； void unknown3(char T[]) {int i， j； i=1； n[1]=0； j=0； while(i__________________________________________________________________________________________二、设计题(总题数：16，分数：32.00)5.设s、t为两个字符串，分别放在两个一维数组中，m、n分别为其长度，判断t是否为s的子串。

计算机专业基础综合数据结构（线性表）历年真题试卷汇编5(总分：64.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)1.线性表是一个( )。

【电子科技大学2010一、1(2分)】【江苏大学2005一、1(2分)】（分数：2.00）A.有限序列，可以为空√B.有限序列，不能为空C.无限序列，可以为空D.无限序列，不能为空解析：2.线性表的顺序存储结构是一种( )。

【北京理工大学2006五、3(1分)】（分数：2.00）A.随机存取的存储结构√B.顺序存取的存储结构C.索引存取的存储结构D.Hash存取的存储结构解析：3.(多选)在下列叙述中， ( )是错误的。

【华中科技大学2006一、1(2分)】（分数：2.00）A.线性表的逻辑顺序与物理顺序总是一致的√B.二叉树的顺序存储结构比链式存储结构节省存储空间√C.二叉树的度小于等于2D.每种数据结构都具有两种基本运算(操作)：插入、删除元素(结点) √解析：4.能在O(1)时间内访问线性表的第i个元素的结构是( )。

【电子科技大学2011一、2(2分)】（分数：2.00）A.顺序表√B.单链表C.单向循环链表D.双向链表解析：5.下面关于线性表的叙述中，错误的是哪一个?( )【北方交通大学2001一、14(2分)】（分数：2.00）A.线性表采用顺序存储，必须占用一片连续的存储单元B.线性表采用顺序存储，便于进行插入和删除操作√C.线性表采用链接存储，不必占用一片连续的存储单元D.线性表采用链接存储，便于插入和删除操作解析：6.线性表是具有n个( )的有限序列(n>0)。

【清华大学1998一、4(2分)】（分数：2.00）A.表元素B.字符C.数据元素√D.数据项E.信息项解析：7.单链表中，增加一个头结点的目的是( )。

【厦门大学2003一、1(2分)】（分数：2.00）A.使单链表至少有一个结点B.标识表结点中首结点的位置C.方便运算的实现√D.说明单链表是线性表的链式存储解析：8.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用( )存储方式最节省时间。

湖南师范大学数学与计算机学院
865数据结构历年考研真题汇编
最新资料，WORD格式，可编辑修改！
目录
2007年湖南师范大学数学与计算机学院842数据结构考研真题 ....................... 2005年湖南师范大学数学与计算机学院469数据结构考研真题 ....................... 2003年湖南师范大学数学与计算机学院数据结构考研真题 ........................... 说明：2005年数据结构科目代码是469，2007年是842。

2016年科目代码是865，
本书以此为准。

2007年湖南师范大学数学与计算机学院842数据结构考研真题2005年湖南师范大学数学与计算机学院469数据结构考研真题2003年湖南师范大学数学与计算机学院数据结构考研真题。

计算机专业基础综合数据结构（线性表）历年真题试卷汇编2(总分：98.00，做题时间：90分钟)一、综合题(总题数：12，分数：24.00)1.线性表的顺序存储结构具有三个弱点：第一，在作插入或删除操作时，需要移动大量元素；第二，由于难以估计，必须预先分配较大的空间，往往使存储空间不能得到充分利用；第三，表的容量难以扩充。

试问，线性表的链式存储结构是否一定能够克服上述三个弱点?请简述之。

【北京师范大学2003二、4(6分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：一般说链式存储结构克服了顺序存储结构的三个弱点。

首先，插入、删除不需移动元素，只修改指针，时间复杂度为O(1)；其次，不需要预先分配空间，可根据需要动态申请空间；其三，表容量只受可用内存空间的限制。

其缺点是因为指针增加了空间开销，当空间不允许时，就不能克服顺序存储结构的缺点。

)解析：2.线性结构包括__________、__________、__________和__________。

线性表的存储结构分成__________和__________。

【华北计算机系统工程研究所1999一、2(10分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：线性表、栈、队列、串；顺序存储结构、链式存储结构。

)解析：3.线性表(a 1，a 2，…，a n )用顺序映射表示时，a i和a i+1(1≤i≤n n )的物理位置相邻吗?链接表示时呢?【东南大学1996一、1(5分)】（分数：2.00）__________________________________________________________________________________________ 正确答案：(正确答案：顺序映射时，a i与a i+1的物理位置相邻；链表表示时，a i与a i+1的物理位置不要求相邻。

计算机专业基础综合数据结构（串）历年真题试卷汇编2(总分：40.00，做题时间：90分钟)一、综合题(总题数：4，分数：8.00)1.如果两个串含有相等的字符，能否说它们相等?【西安电子科技大学2000一、3(5分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：仅从两串含有相等的字符，不能判定两串是否相等，两串相等的充分必要条件是两串长度相等且对应位置上的字符相同(即两串串值相等)。

)解析：2.设S1、S2为串，请给出使S1／／$2=S2／／S1成立的所有可能的条件(／／为连接符)。

【国防科技大学1999一】【长沙铁道学院1997三、5(3分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：(1)S1和S2至少一个是空串；(2)两串串值相等(即两串长度相等且对应位置上的字符相同)；(3)两串中一个串长是另一个串长(包括串长为1仅有一个字符的情况)的数倍，而且长串就好像是由数个短串经过连接操作得到的。

)解析：3.已知：s=‘(xyz)+*’，t=’(x+z)*’。

试利用联结、求子串和置换等基本运算，将s转化为t。

【北方交通大学1996一、3(5分)】【山东科技大学2002一、6(5分)】（分数：2.00）__________________________________________________________________________________________正确答案：(正确答案：题中所给操作的含义如下：／／：连接函数，将两个串连接成一个串 substr(8，i，j)：取子串函数，从串s的第i个字符开始，取连续j个字符形成子串replace(s1，i，j，s2)：置换函数，用s2替换s1中从第i个字符开始的连续j个字符本题有多种解法，下面是其中的一种：(1)s1=substr(s，3，1) ／／取出字符：’y’ (2)s2=su bstr(s，6，1) ／／取出字符：‘+’ (3)s3=substr(s，1，5) ／／取出子串：‘(xyz)’ (4)s4=substr(s，7，1) ／／取出字符：‘*’ (5)s5=replace(s3，3，1，s2)／／形成部分串："(X+Z)"。