计算机专业基础综合数据结构（线性表）历年真题试卷汇编1

计算机学科专业基础综合数据结构-线性表(一)(总分104,考试时间90分钟)一、单项选择题1. 线性表是( )。

A. 一个有限序列，可以为空B. 一个有限序列，不可以为空C. 一个无限序列，可以为空D. 一个无限序列，不可以为空2. 在一个长度为n的顺序表中删除第i个元素(0＜=i＜=n)时，需向前移动____个元素。

A. n-iB. n-i+1C. n-i-1D. .i3. 在一个长度为n的顺序表中向第i个元素(0＜i＜n+1)之前插入一个新元素时，需向后移动( )个元素。

A. n-iB. n-i+1C. n-i-1D. .i4. 下述哪一条是顺序存储结构的优点?____A. 存储密度大B. 插入运算方便C. 删除运算方便D. 可方便地用于各种逻辑结构的存储表示5. 下面关于线性表的叙述中，错误的是哪一个?____A. 线性表采用顺序存储，必须占用一片连续的存储单元B. 线性表采用顺序存储，便于进行插入和删除操作C. 线性表采用链接存储，不必占用一片连续的存储单元D. 线性表采用链接存储，便于插入和删除操作6. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用____存储方式最节省时间。

A. 顺序表B. 双链表C. 带头结点的双循环链表D. 单循环链表7. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为____。

A. O(n)，O(n)B. O(n)，O(1)C. O(1)，O(n)D. O(1)，O(1)8. (1)静态链表既有顺序存储的优点，又有动态链表的优点，所以，它存取表中第i个元素的时间与i无关。

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

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

以上错误的是____。

A. (1)，(2)B. (1)C. (1)，(2)，(3)D. (2)9. 某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用____存储方式最节省运算时间。

计算机专业基础综合数据结构（排序）历年真题试卷汇编1(总分：72.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)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]枢轴是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)如何对一趟快速排序的结果在最短的时间内做出正确判断，这里给出建议：首先84应该不动，所以D排除了；接着40应调到序列首，所以A排除了；接着79应调到移走40的空位上，B排除了。

选择答案C，不必再继续做了(假定确有唯一正确答案)。

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个最小元素之前的部分排序的序列，用( )方法最快。

计算机专业基础综合数据结构（图）历年真题试卷汇编1(总分：60.00，做题时间：90分钟)一、单项选择题(总题数：20，分数：40.00)1.下列关于无向连通图特性的叙述中，正确的是( )。

【2009年全国试题7(2分)】I．所有顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1（分数：2.00）A.只有I √B.只有ⅡC.I和ⅡD.I和Ⅲ解析：解析：无向图中一条边要连接两个顶点，因此顶点的度数之和必为偶数。

n个顶点的无向连通图至少需要n-1条边。

无向连通图并不要求“至少有一个顶点的度为1”。

2.若无向图G=(V,E)中含有7个顶点，要保证图G在任何情况下都是连通的，则需要的边数最少是( )。

【2010年全国试题7(2分)】（分数：2.00）A.6B.15C.16 √D.21解析：解析：要保证n个顶点的无向图G在任何情况下都是连通的，则需要先由n-1个顶点组成完全图，从第n个顶点引一条到n-1任一顶点的边，则图肯定是连通的。

本题先由6个顶点组成完全图，需要6(6-1)／2=15条边，故按题目要求“需要的边数最少”是15+1=16。

3.对下图进行拓扑排序，可以得到不同拓扑序列的个数是( )。

【2010年全国试题8(2分)（分数：2.00）A.4B.3 √C.2D.1解析：4.下列关于图的叙述中，正确的是( )。

【2011年全国试题8(2分)】I．回路是简单路径Ⅱ．存储稀疏图，用邻接矩阵比邻接表更省空间Ⅲ．若有向图中存在拓扑序列，则该图不存在回路（分数：2.00）A.仅ⅡB.仅I、ⅡC.仅Ⅲ√D.仅I、Ⅲ解析：解析：图中第1个顶点和最后一个顶点相同的路径称为回路或环。

序列中所有顶点不重复出现的路径称为简单路径，邻接矩阵的大小只和顶点个数相关，存储稀疏图，用邻接表比邻接矩阵更省空间。

拓扑序列成功的前提是有向图中不存在回路。

5.对有n个结点、e条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是( )。

计算机专业基础综合数据结构（集合）历年真题试卷汇编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)求出在等概率情况下，查找成功的平均查找长度。

计算机专业基础综合数据结构（排序）历年真题试卷汇编1(总分：72.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：30.00)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]枢轴是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)如何对一趟快速排序的结果在最短的时间内做出正确判断，这里给出建议：首先84应该不动，所以D排除了；接着40应调到序列首，所以A排除了；接着79应调到移走40的空位上，B排除了。

选择答案C，不必再继续做了(假定确有唯一正确答案)。

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个最小元素之前的部分排序的序列，用( )方法最快。

数据结构试卷 1一、单选题1. 栈和队列的共同特点是 ()。

A.只允许在端点处插入和删除元素B.都是先进后出C.都是先进先出D.没有共同点2.用链接方式存储的队列，在进行插入运算时 ( ).A.仅修改头指针B.头、尾指针都要修改C.仅修改尾指针D.头、尾指针可能都要修改3.以下数据结构中哪一个是非线性结构？ ( )A. 队列B. 栈C. 线性表D. 二叉树4.设有一个二维数组 A[m][ n]，假设 A[0][0] 存放位置在644(10)，A[2][2] 存放位置在 676(10)，每个元素占一个空间，问A[3][3] (10)存放在什么位置？脚注 (10)表示用10进制表示。

A．688B． 678C．692D．6965.树最适合用来表示 () 。

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第 k 层的结点数最多为 ( ).A．2k-1B.2K+1 C.2K-1 D. 2 k-17. 若有 18 个元素的有序表存放在一维数组A[19] 中，第一个元素放 A[1] 中，现进行二分查找，则查找 A ［3］的比较序列的下标依次为 ()A. 1，2，3B. 9，5，2，3C. 9，5，3D. 9，4，2，38.对 n 个记录的文件进行快速排序，所需要的辅助存储空间大致为A. O（1）B. O （n）C. O（1og2n）D. O（n2）9.对于线性表（ 7，34， 55，25，64， 46，20，10）进行散列存储时，若选用 H（K）=K %9作为散列函数，则散列地址为 1 的元素有（）个，A．1B．2C．3D．410.设有 6个结点的无向图，该图至少应有 ()条边才能确保是一个连通图。

A.5B.6C.7D.8二、填空题1.通常从四个方面评价算法的质量：_________、 _________、 _________和_________。

2.一个算法的时间复杂度为 (n3+n2log2n+14n)/n2，其数量级表示为 ________。

计算机专业基础综合数据结构（串）历年真题试卷汇编1(总分：58.00，做题时间：90分钟)一、填空题(总题数：12，分数：24.00)1.设T和P是两个给定的串，在T中寻找等于P的子串的过程称为(1)，又称P为(2)。

【西安电子科技大学1998二、5(16／6分)】__________________________________________________________________________________________ 正确答案：(正确答案：(1)模式匹配 (2)模式串)2.串是一种特殊的线性表，其特殊性表现在(1) ；串的两种最基本的存储方式是(2)、(3)；两个串相等的充分必要条件是(4)。

【中国矿业大学2000一、3(4分)】__________________________________________________________________________________________ 正确答案：(正确答案：(1)其数据元素都是字符(2)顺序存储(3)链式存储(4)串的长度相等且两串中对应位置的字符也相等)3.使用“求子串”subString(S，pos，len)和“联结”concat(S1，s2)的串操作，可从串s=‘conduction’中的字符得到串t=”cont”，则求t的串表达式为__________。

【北京工业大学2005二、4(3分)】__________________________________________________________________________________________ 正确答案：(正确答案：t=concat(subStIling(s，1，3)，subString(s，7，1)))4.下列程序读入无符号十六进制数(出现的字母为小写)，将其转换为十进制数输出。

请将程序空缺部分补全。

int f(char *s) {int n=0，i；for(i=0；s[i]!="＼0"; i++)n=n*16+(1)；return n；} main() {char s[10]； scanf(“％s”，s)；printf(“％d＼n”(2) )； }【浙江大学2002二(6分)】__________________________________________________________________________________________ 正确答案：(正确答案：(1)(s[i]>=977 s[i]一87：s[i]-48) ／／"a"到"f"的ASCII码是97到102 (2)f(s)) 5.已知U=‘xyxyxyxxyxy’；t=‘xxy’；ASSIGN(S，U)；ASSIGN(V，SUBSTR(S，INDEX(s，t)，LENCt)+1)),ASSIGN(m，‘ww’)求REPLACE(S，y，m)=__________。

计算机专业基础综合数据结构（查找）历年真题试卷汇编1(总分108,考试时间90分钟)1. 单项选择题1. 顺序查找法适合于存储结构为____的线性表。

【北京航空航天大学2002年】A. 顺序存储结构或链式存储结构B. 散列存储结构C. 索引存储结构D. 压缩存储结构2. 若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度(ASL)为____。

【北京航空航天大学2004年】A. (n—1)／2B. n／2C. (n+1)／2D. n3. 当采用分块查找时，数据的组织方式为____。

【太原科技大学2007年】A. 数据分成若干块，每块内数据有序B. 数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大(或最小)的数据组成索引块C. 数据分成若干块，每块内数据有序，每块内最大(或最小)的数据组成索引块D. 数据分成若干块，每块(除最后一块外)中数据个数需相同4. 对有2500个记录的索引顺序表(分块表)进行查找，最理想的块长为____。

【华中科技大学2007年】A. 50B. 125C. 500D. [log22500]5. 下面关于二分查找的叙述正确的是____。

【南京理工大学1996年】A. 表必须有序，表可以顺序方式存储，也可以链表方式存储B. 表必须有序且表中数据必须是整型、实型或字符型C. 表必须有序，而且只能从小到大排列D. 表必须有序，且表只能以顺序方式存储6. 当n足够大时，在按值有序的顺序表中进行折半查找，当查找概率相等的情况下，其查找成功的平均查找长度是____。

【北京航空航天大学2002年】A. (n+1)／2B. n／2C. log2(n+1)一1D. log2(n+1)7. 在具有15个记录的排序连续顺序文件上采用折半查找方法查找一个文件中不存在的记录．需要进行____次关键字值的比较。

【北京航空航天大学2004年】A. 0B. 4C. 5D. 158. 对一个长度为50的有序表进行折半查找，最多比较____次就能查找出结果。

计算机专业基础综合数据结构（概论）历年真题试卷汇编1(总分：64.00，做题时间：90分钟)一、单项选择题(总题数：15，分数：32.00)1.以下哪个数据结构不是多型数据类型?( )【中山大学1999一、3(1分)】（分数：2.00）A.栈B.广义表C.有向图D.字符串√解析：2.以下数据结构中，( )是非线性数据结构【中山大学1999一、4】（分数：2.00）A.树√B.字符串C.队D.栈解析：3.下列数据中，( )是非线性数据结构。

【北京理工大学2001六、1(2分)】（分数：2.00）A.栈B.队列C.完全二叉树√D.堆解析：解析：栈、队列是线性结构，堆是元素的序列，存在一维数组中，可以看成是线性结构。

完全二叉树是非线性结构，只是由于双亲和子女编号间存在固定关系，用一维数组存储更好。

4.连续存储设计时，存储单元的地址( )。

【中山大学1999一、1(1分)】（分数：2.00）A.一定连续√B.一定不连续C.不一定连续D.部分连续，部分不连续解析：5.以下属于逻辑结构的是( )。

【西安电子科技大学应用2001一、1】（分数：2.00）A.顺序表B.哈希表C.有序表√D.单链表解析：6.算法的计算量的大小称为计算的( )。

【北京邮电大学2000二、3(20／8分)】（分数：2.00）A.效率B.复杂性√C.现实性D.难度解析：7.算法的时间复杂度取决于( )。

【中科院计算所1998二、1(2分)】（分数：2.00）A.问题的规模B.待处理数据的初态C.A和B √解析：计算机算法指的是(1)，它必须具备(2)这三个特陛。

【南京理工大学1999一、1(2分)】（分数：4.00）(1).(1)（分数：2.00）A.计算方法B.排序方法C.解决问题的步骤序列√D.调度方法解析：(2).(2)（分数：2.00）A.可执行性、可移植性、可扩充性B.可执行性、确定性、有穷性√C.确定性、有穷性、稳定性D.易读性、稳定性、安全性解析：8.一个算法应该是( )。

第2章线性表后面红色的答案一选择题1．下述哪一条是顺序存储结构的优点？（）【北方交通大学2001 一、4（2分）】A．存储密度大B．插入运算方便C．删除运算方便D．可方便地用于各种逻辑结构的存储表示2．下面关于线性表的叙述中，错误的是哪一个？（）【北方交通大学2001 一、14（2分）】A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

3．线性表是具有n个（）的有限序列（n>0）。

【清华大学1998 一、4（2分）】A．表元素B．字符C．数据元素D．数据项E．信息项4．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

【哈尔滨工业大学2001 二、1（2分）】A．顺序表B．双链表C．带头结点的双循环链表D．单循环链表5．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（）存储方式最节省运算时间。

【南开大学2000 一、3】A．单链表B．仅有头指针的单循环链表C．双链表D．仅有尾指针的单循环链表6．设一个链表最常用的操作是在末尾插入结点和删除尾结点，则选用( )最节省时间。

A. 单链表B.单循环链表C. 带尾指针的单循环链表D.带头结点的双循环链表【合肥工业大学2000 一、1（2分）】7．若某表最常用的操作是在最后一个结点之后插入一个结点或删除最后一个结点。

则采用（）存储方式最节省运算时间。

【北京理工大学2000 一、1（2分）】A．单链表B．双链表C．单循环链表D．带头结点的双循环链表8. 静态链表中指针表示的是（）. 【北京理工大学2001 六、2（2分）】A．内存地址B．数组下标C．下一元素地址D．左、右孩子地址9. 链表不具有的特点是（）【福州大学1998 一、8 (2分)】A．插入、删除不需要移动元素B．可随机访问任一元素C．不必事先估计存储空间D．所需空间与线性长度成正比10. 下面的叙述不正确的是（）【南京理工大学1996 一、10（2分）】A．线性表在链式存储时，查找第i个元素的时间同i的值成正比B. 线性表在链式存储时，查找第i个元素的时间同i的值无关C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成正比D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关11. 线性表的表元存储方式有(（1）)和链接两种。