济南大学-数据结构试卷

数据结构试卷（一）王彬一、单选题（每题2 分，共20分）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进制表示。

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

A.有序数据元素B.无序数据元素C.元素之间具有分支层次关系的数据D.元素之间无联系的数据6.二叉树的第k层的结点数最多为( d ).A．2k-1 B.2K+1 C.2K-1 D. 2k-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的元素有（ c d）个，A．1 B．2 C．3 D．410.设有6个结点的无向图，该图至少应有( )条边才能确保是一个连通图。

A.5B.6C.7D.8二、填空题（每空1分，共26分）1.通常从四个方面评价算法的质量：____ ____、________、________和_______。

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

………………………………………………密………………………………封………………………………线………………………………山东大学 2018-2019 学年 一 学期 数据结构 课程试卷A题号 一 二 三 四 五 六 七 八 九 十 总分 阅卷人得分学院 专业 级 学号 姓名一、线性结构（30分）。

1、已知线性表：（8，9，2，13，0，7，1，6，5），请完成以下题目。

⑴请描述公式化描述及链表描述的空间需求。

如果需要删除元素13，请描述各自的时间复杂度。

⑵ 请分别进行选择排序、插入排序、快速排序（以8为轴），并给出第一轮排序结束后各自的结果。

⑶ 设计散列表，散列函数为H （k)=k%7，散列表长度为11，请给出线性开型寻址的散列表。

⑷ 基于以上散列表，查找元素1，给出需要的查找次数。

⑸若使用单链表存储上述线性表，请阅读以下程序，并给出程序运行结果及其时间复杂度。

二、层次结构（35分）。

1. 二叉树的层次遍历序列为ABCDEFGHIJ ，中序遍历序列为DBGEHJACIF ，写出该二叉树的前序遍历序列。

2. 一个最大堆为（66，37，41，30，25，40，35，18），依次从中删除两个元素，写出最后得到的堆。

3. 有一份电文中共使用6个字符：A 、B 、C 、D 、E 、F ，它们的出现频率依次为10、6、5、2、15、4，试画出对应的赫夫曼树（请按左子树根节点的权小于等于右子树根节点的权的次序构造，左0右1），并求出每个字符的赫夫曼编码。

4. 对给定输入序列{ 19, 5, 7, 11, 26, 18, 16, 17 },构建AVL 树。

5. 在下列5阶B-树中首先插入关键字85，然后删除关键字70，画出插入元素和删除元素后的B-树。

三、网状结构（35分）。

1. 请给出从加权无向图中生成最小耗费生成树的两种方法，请分别描述其算法思想，并给出各自的时间复杂度。

2. 下面是某有向加权图(顶点A,B,C,D,E)的耗费邻接矩阵，先给出一个拓扑序列，然后，使用Dijkstra算法依次计算出顶点A 至其它各顶点的最短路径和最短路径长度。

大学计算机《数据结构》试卷及答案一、单选题（每小题2分，共8分）1、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为( )。

A nB n/2C (n+1)/2D (n-1)/22、在一个单链表中,若q所指结点是p所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行( )。

A s→link=p→link; p→link=s;B p→link=s; s→link=q;C p→link=s→link; s→link=p;D q →link=s; s→link =p;3、栈的插入和删除操作在（）进行。

A 栈顶B 栈底C 任意位置D 指定位置4、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）A 24B 71C 48D 53二、填空题（每空1分，共32分）1、数据的逻辑结构被分为_______、_______ 、_______和_______四种。

2、一种抽象数据类型包括______________和_____________两个部分。

3、在下面的数组a中链接存储着一个线性表，表头指针为a[o].next，则该线性表为_________________________________________________。

a 0 1 2 3 4 5 6 7 8data4、在以HL为表头指针的带表头附加结点的单链表和循环单链表中，判断链表为空的条件分别为________________和____________________。

5、用具有n个元素的一维数组存储一个循环队列，则其队首指针总是指向队首元素的___________，该循环队列的最大长度为__________。

6、当堆栈采用顺序存储结构时，栈顶元素的值可用———————表示；当堆栈采用链接存储结构时，栈顶元素的值可用_______________表示。

《数据结构》试卷（B卷）一、单项选择题1. 线性表是__A___。

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

A．n-i B．n-i+l C．n-i-1 D．i3. 线性表采用链式存储时，其地址_D___。

A．必须是连续的B．一定是不连续的C．部分地址必须是连续的D．连续与否均可以4. 从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较___C_个元素结点。

A．n/2 B．n C．（n+1）/2 D．（n-1）/25. 在双向循环链表中，在p所指的结点之后插入s指针所指的结点，其操作是_A D 。

A． p->next=s; s->prior=p;p->next->prior=s; s->next=p->next;B． s->prior=p; s->next=p->next;p->next=s; p->next->prior=s;C． p->next=s; p->next->prior=s;s->prior=p; s->next=p->next;D． s->prior=p; s->next=p->next;p->next->prior=s; p->next=s;6. 设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为__A___。

A．p->next=p->next->next; B．p=p->next;C．p=p->next->next; D．p->next=p;7. 在一个长度为n的顺序表中向第i个元素(0< i<n+l )之前插入一个新元素时，需向后移动__B_个元素。

数据结构试卷(A)答案数据结构试卷(A)答案一、单选题（共10题，每题2分）1. 答案：B解析：选项A和C的时间复杂度为O(n)，不符合题目要求。

选项D的时间复杂度为O(n^2)，也不符合题目要求。

选项B的时间复杂度为O(1)，是最优解。

2. 答案：C解析：选项A的时间复杂度为O(n)，不符合题目要求。

选项B和D的时间复杂度为O(n^2)，也不符合题目要求。

选项C的时间复杂度为O(logn)，是最优解。

3. 答案：A解析：选项B和D的时间复杂度为O(n^2)，不符合题目要求。

选项C的时间复杂度为O(logn)，也不符合题目要求。

选项A的时间复杂度为O(nlogn)，是最优解。

4. 答案：D解析：选项A和B的时间复杂度为O(n^2)，不符合题目要求。

选项C的时间复杂度为O(nlogn)，也不符合题目要求。

选项D的时间复杂度为O(n)，是最优解。

解析：选项A和D的时间复杂度为O(n^2)，不符合题目要求。

选项B的时间复杂度为O(nlogn)，也不符合题目要求。

选项C的时间复杂度为O(n)，是最优解。

6. 答案：B解析：选项A和C的时间复杂度为O(n^2)，不符合题目要求。

选项D的时间复杂度为O(n)，也不符合题目要求。

选项B的时间复杂度为O(1)，是最优解。

7. 答案：D解析：选项A和C的时间复杂度为O(n^2)，不符合题目要求。

选项B的时间复杂度为O(nlogn)，也不符合题目要求。

选项D的时间复杂度为O(n)，是最优解。

8. 答案：C解析：选项A和D的时间复杂度为O(n^2)，不符合题目要求。

选项B的时间复杂度为O(nlogn)，也不符合题目要求。

选项C的时间复杂度为O(n)，是最优解。

9. 答案：A解析：选项B和D的时间复杂度为O(n^2)，不符合题目要求。

选项C的时间复杂度为O(nlogn)，也不符合题目要求。

选项A的时间复杂度为O(n)，是最优解。

解析：选项A和B的时间复杂度为O(n^2)，不符合题目要求。

《数据结构》试卷答案及评分细则一、单项选择题（本题共10小题，每小题2分，共20分。

）1. C2. B3. C4. B5. B6. A7. A &D 9. C 10. A评分细则：每题正确得2分，错误不得分。

二、填空题（本题共10小题，每小题1分，共10分。

）1.集合线性结构树形结构图状结构（或网状结构）2.时间复杂度空间复杂度3.顺序4.物理上相邻指针5.23 100C6.两个串的值相等（或两个串的长度相等，且各个对应位置的字符都相等）7. 5&根结点左子树右子树9.广度优先遍历10.比较交换（移动）评分细则：每题正确得1分，错误不得分。

三、应用题（本题共4小题，每小题10分，共40分。

）1.解：设树T的总结点数为n,树T的分支数为B,度数为0, 1, 2, 3, 4 的结点个数分别为n0,nl,n2,n3,n4 ......................................... （1分）贝lj n=n0+nl+n2+n3+n4 （1）.............................. （2 分）B=0*n0+I*nl+2*n2+3*n3+4*n4 （2）.............................. （2 分）且n=B+l （3）.............................. （4 分）将（1）（2）（3）式联立，求得n0=8o .................................... （1分）评分细则：部分正确酌情给分。

评分细则：树的形状正确5分，后续遍历正确5分；树的形状正确，后序遍历后序遍历序列：FDBGHECA部分部分正确酌情给分。

0 1 2 3 4 5 6 7VI—V2V3 —AV4—►V5 —►V6 —►V7—►V8 —►2A357 A7 A6 A5A4A4A6A(1) 广度优先搜索序列:V1V2V3V4V5V6V7V8(2 ) 深度优先搜索序列:V1V2V4V8V5V3V6V7评分细则：邻接表中结点顺序可不与参考答案一致，搜索序列可不与参考答案一致，部分正确酌情给分。

（完整版）数据结构试题及答案《数据结构》自考复习思考试题○10一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

错选、多选或未选均无分。

1. 若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上( ) A. 操作的有限集合 B. 映象的有限集合C. 类型的有限集合D. 关系的有限集合2. 在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为( )A. n-i+1B. iC. i+1D. n-i3. 若不带头结点的单链表的头指针为head，则该链表为空的判定条件是( )A. head==NULLB. head->next==NULLC. head!=NULLD. head->next==head4. 引起循环队列队头位置发生变化的操作是( )A. 出队B. 入队C. 取队头元素D. 取队尾元素5. 若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不．可能出现的出栈序列是( )A. 2，4，3，1，5，6B. 3，2，4，1，6，5C. 4，3，2，1，5，6D. 2，3，5，1，6，46. 字符串通常采用的两种存储方式是( )A. 散列存储和索引存储B. 索引存储和链式存储C. 顺序存储和链式存储D. 散列存储和顺序存储7. 设主串长为n，模式串长为m(m≤n)，则在匹配失败情况下，朴素匹配算法进行的无效位移次数为( )A. mB. n-mC. n-m+1D. n8. 二维数组A［12］［18］采用列优先的存储方法，若每个元素各占3个存储单元，且第1个元素的地址为150，则元素A［9］［7］的地址为( )A. 429B. 432.C. 435D. 4389. 对广义表L=((a,b),(c,d),(e,f))执行操作tail(tail(L))的结果是( )A. (e,f)B. ((e,f))C. (f)D. ( )10. 下列图示的顺序存储结构表示的二叉树是( )11. n个顶点的强连通图中至少含有( )A. n-1条有向边B. n条有向边C. n(n-1)/2条有向边D. n(n-1)条有向边12. 对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为( )A. (19，23，56，34，78，67，88，92)B. (23，56，78，66，88，92，19，34)C. (19，23，34，56，67，78，88，92)D. (19，23，67，56，34，78，92，88)13. 若在9阶B-树中插入关键字引起结点分裂，则该结点在插入前含有的关键字个数为( ) A. 4 B. 5C. 8D. 914. 由同一关键字集合构造的各棵二叉排序树( )A. 其形态不一定相同，但平均查找长度相同B. 其形态不一定相同，平均查找长度也不一定相同C. 其形态均相同，但平均查找长度不一定相同.D. 其形态均相同，平均查找长度也都相同15. ISAM文件和VSAM文件的区别之一是( )A. 前者是索引顺序文件，后者是索引非顺序文件B. 前者只能进行顺序存取，后者只能进行随机存取C. 前者建立静态索引结构，后者建立动态索引结构D. 前者的存储介质是磁盘，后者的存储介质不是磁盘二、填空题(本大题共10小题，每空2分，共20分)16. 数据的逻辑结构在计算机存储器内的表示，称为数据的____________。

4.1. 2.3. 1. 2. 3.4.5.6.7. 9. 单选题(每题2分，共20分)1.对一个算法的评价，不包括如下(B )方面的内容。

A •健壮性和可读性B •并行性C .正确性D .时空复杂度2.在带有头结点的单链表HL 中，要向表头插入一个由指针P 指向的结 点，则执行(A ) 0A. p->n ext=HL->n ext; HL->n ext=p;B. p->n ext=HL; HL=p;C. p->n ext=HL; p=HL;D. HL=p; p-> next=HL;3.对线性表，在下列哪种情况下应当采用链表表示？( B )A.经常需要随机地存取元素B.经常需要进行插入和删除操作C.表中元素需要占据一片连续的存储空间D.表中元素的个数不变一个栈的输入序列为1 2 3,则下列序列中不可能是栈的 输出序列的是C ) A. 2 3 1 C. 3 1 2A0V 网是一种(D )0A .有向图B .无向图4.(5. B. 3 2 1 D. 1 2 3C .无向无环图D .有向无环图B )o6.采用开放定址法处理散列表的冲突时，其平均查找长度(A .低于链接法处理冲突 B.高于链接法处理冲突 C .与链接法处理冲突相同 D .高于二分查找7.若需要利用形参直接访问实参时，应将形参变量说明为(D )参数0A •值B .函数C .指针D •引用8.在稀疏矩阵的带行指针向量的链接存储中，每个单链表中的结点都具 有相同的(A )0 A •行号 B .列号 C .元素值 9. 快速排序在最坏情况下的时间复杂度为( A . O(log 2n) B . O(nlog 2n) C . D •非零元素个数 D )o 0(n)10.10.从二叉搜索树中查找一个元素时，其时间复杂度大致为 A. O(n) B. O(1) C. O(log 2 n)D. 0( n 2) D . 0(n 2) (C )o 运算题(每题6分，共24分) 1. 数据结构是指数据及其相互之间的 对N ( M : N )的联系时，称这种结构为 2.队列的插入操作是在队列的 尾 ______ 行，删除操作是在队列的首 ______ 行。

《数据结构》试题集及答案第⼀部分选择题(30分)⼀、⼀、项选择题（本⼤题共15⼩题，每⼩题2分，共30分）在每⼩题列出的四个选项中只有⼀个选项是符合题⽬要求的，请将正确选项前的字母填在题后的括号内。

1．算法指的是（）A ．计算机程序B ．解决问题的计算⽅法C ．排序算法D ．解决问题的有限运算序列2．线性表采⽤链式存储时，结点的存储地址（）A ．必须是不连续的B ．连续与否均可C ．必须是连续的D ．和头结点的存储地址相连续3．将长度为n 的单链表链接在长度为m 的单链表之后的算法的时间复杂度为（）A ．O （1）B ．O （n ）C ．O （m ）D ．O （m+n ）4．由两个栈共享⼀个向量空间的好处是：（）A ．减少存取时间，降低下溢发⽣的机率B ．节省存储空间，降低上溢发⽣的机率C ．减少存取时间，降低上溢发⽣的机率D ．节省存储空间，降低下溢发⽣的机率5．设数组data[m]作为循环队列SQ 的存储空间，front 为队头指针，rear 为队尾指针，则执⾏出队操作后其头指针front 值为（）A ．front=front+1B ．front=(front+1)%(m-1)C ．front=(front-1)%mD ．front=(front+1)%m6．如下陈述中正确的是（）A ．串是⼀种特殊的线性表B ．串的长度必须⼤于零C ．串中元素只能是字母D ．空串就是空⽩串A ．O （n 3）B ．O （n ）C ．O （n 2）D ．O （n 3）8．⼀个⾮空⼴义表的表头（）A ．不可能是⼦表B ．只能是⼦表C ．只能是原⼦D ．可以是⼦表或原⼦9．假设以带⾏表的三元组表表⽰稀疏矩阵，则和下列⾏表0 2 3 3 5对应的稀疏矩阵是（）A.08067000000050400000--B.08067000504000000300--C. 0806 0000 0200 5040 0000 --D.-10．在⼀棵度为3的树中,度为3的结点个数为2,度为2 的结点个数为1,则度为0的结点个数为( )A．4 B．5 C．6 D．711．在含n个顶点和e条边的⽆向图的邻接矩阵中,零元素的个数为( ) A．e B．2e C．n2－e D．n2－2e12．假设⼀个有n个顶点和e条弧的有向图⽤邻接表表⽰,则删除与某个顶点v i 相关的所有弧的时间复杂度是( )A．O(n) B．O(e) C．O(n+e) D．O(n*e)13．⽤某种排序⽅法对关键字序列（25，84，21，47，15，27，68，35，20）进⾏排序时，序列的变化情况如下：20，15，21，25，47，27，68，35，8415，20，21，25，35，27，47，68，8415，20，21，25，27，35，47，68，84则所采⽤的排序⽅法是（）A．选择排序B．希尔排序C．归并排序D．快速排序14．适于对动态查找表进⾏⾼效率查找的组织结构是（）A．有序表B．分块有序表C．三叉排序树D．线性链表15．不定长⽂件是指（）A．⽂件的长度不固定B．记录的长度不固定C．字段的长度不固定D．关键字项的长度不固定第⼆部分⾮选择题（共70分）17．在⼀个带头结点的单循环链表中，p指向尾结点的直接前驱，则指向头结点的指针head可⽤p表⽰为head= 。