13级数据结构期中试卷(打印)

数据结构期中考试试卷一、选择题（每题2分，共20分）1. 在数据结构中，线性结构的特点是什么？A. 元素之间存在一对一关系B. 元素之间存在一对多关系C. 元素之间存在多对多关系D. 元素之间存在一对一或多对多关系2. 以下哪个算法不是排序算法？A. 快速排序B. 归并排序C. 深度优先搜索D. 堆排序3. 在二叉树中，度为2的节点最多有多少个子节点？A. 1B. 2C. 3D. 44. 哈希表解决冲突的方法不包括以下哪一项？A. 分离链接法B. 开放寻址法C. 链地址法D. 树形结构法5. 以下哪个不是图的遍历算法？A. 深度优先搜索B. 广度优先搜索C. 动态规划D. 克鲁斯卡尔算法6. 栈的特点是？A. 后进先出B. 先进后出C. 先进先出D. 后进后出7. 以下哪个不是二叉搜索树的性质？A. 左子树上所有节点的值小于它的根节点的值B. 右子树上所有节点的值大于它的根节点的值C. 左子树和右子树都是二叉搜索树D. 所有节点的值都相等8. 在数据库中，索引的作用是什么？A. 增加数据存储空间B. 提高数据检索效率C. 降低数据插入速度D. 减少数据存储量9. 以下哪个不是图的存储结构？A. 邻接矩阵B. 邻接表C. 树形结构D. 边列表10. 递归算法的基本思想是什么？A. 将问题分解为更小的子问题B. 重复执行相同的操作C. 将问题转化为非递归形式D. 避免使用循环结构二、填空题（每题2分，共20分）1. 在数据结构中，______是一种特殊的线性表，只允许在一端进行插入和删除操作。

2. 排序算法中，______排序的时间复杂度为O(n^2)，适用于小规模数据的排序。

3. 在图的表示中，______矩阵可以有效地表示稠密图。

4. 哈希表中，______是指两个关键字通过哈希函数得到同一个哈希地址。

5. 栈和队列的主要区别在于，栈是______，而队列是先进先出。

6. 二叉树的遍历方式包括前序遍历、中序遍历和______遍历。

11-12学年2学期电⼦信息⼯程《数据结构》期中试卷11-12学年2学期电⼦信息⼯程《数据结构》期中试卷答题纸上只写班级姓名学号及每题答案。

1、单项选择题(本⼤题共30⼩题，每⼩题1分，共30分)在每⼩题列出的四个备选项中只有⼀个是符合题⽬要求的，请将其代码填写在题后的括号内。

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

1.数据的不可分割的最⼩标识单位是（）A.数据项B.数据记录C.数据元素D.数据变量2.for(i=0;ifor(j=0;jc[i][j]=0;for(i=0;ifor(j=0;jfor(k=0;kc[i][j]=c[i][j]+a[i][k]*b[k][j];上列程序的时间复杂度为（）A.O(m+n×t)B.O(m+n+t)C.O(m×n×t)D.O(m×t+n)3.若线性表最常⽤的操作是存取第i个元素及其前趋的值，那么最节省操作时间的存储⽅式是（）A.单链表B.双链表C.单循环链表D.顺序表4.设单链表中指针p指向结点A，要删除A之后的结点(若存在)，则修改指针的操作为（）A.p—>next=p—>next—>nextB.p=p—>nextC.p=p—>next—>nextD.p—>next=p5.向⼀个栈顶指针为hs的链栈中插⼊⼀个*s结点时，应执⾏的操作为（）A.hs—>next=s;B.s—>next=hs;hs=s;C.s—>next=hs—>next;hs—>next=s;D.s—>next=hs;hs=hs—>next;6.设循环队列的元素存放在⼀维数组Q[0‥30]中，队列⾮空时，front指⽰队头元素的前⼀个位置，rear指⽰队尾元素。

如果队列中元素的个数为11，front的值为25，则rear应指向的元素是（）A.Q[4]D.Q[15]7.定义⼆维数组A[1‥8，0‥10]，起始地址为LOC，每个元素占2L个存储单元，在以⾏序为主序的存储⽅式下，某数据元素的地址为LOC+50L，则在以列序为主序的存储⽅式下，该元素的存储地址为（）A.LOC+28LB.LOC+36LC.LOC+50LD.LOC+52L8.具有n个结点的⼆叉树，拥有指向孩⼦结点的分⽀数⽬是（）A.n-1B.nC.n+1D.2n9.对⼀棵有100个结点的完全⼆叉树按层序编号，则编号为49的结点，它的左孩⼦的编号为（）A.99B.98C.97D.5010.有m个叶⼦结点的哈夫曼树，其结点总数是（）A.2m-1B.2mC.2m+1D.2(m+1)11.有n个结点的⽆向图的边数最多为（）A.n+1B.n(n-1)/2C.n(n+1)D.2n(n+1)12.设图的邻接矩阵为，则该图为（）A.有向图B.⽆向图C.强连通图D.完全图13.⼆分查找算法的时间复杂度是（）B.O(nlog2n)C.O(n)14.已知8个元素(34，76，45，18，26，54，92，65)，按照依次插⼊结点的⽅法⽣成⼀棵⼆叉排序树，则该树的深度为（）A.4B.5C.6D.715.采⽤排序算法对n个元素进⾏排序，其排序趟数肯定为n-1趟的排序⽅法是（）A.插⼊和快速B.冒泡和快速C.选择和插⼊D.选择和冒泡16.从逻辑上可以把数据结构分为（）A.动态结构、静态结构B.顺序结构、链式结构C.线性结构、⾮线性结构D.初等结构、构造型结构17.关于算法的描述，不正确的是（）A.算法最终必须由计算机程序实现B.所谓时间复杂度是指最坏情况下，估算算法执⾏时间的⼀个上界C.健壮的算法不会因⾮法的输⼊数据⽽出现莫名其妙的状态D.算法的优劣与算法描述语⾔⽆关18.在单链表中，存储每个结点需要有两个域，⼀个是数据域，另⼀个是指针域，指针域指向该结点的（）A.直接前趋B.直接后继C.开始结点D.终端结点19.将两个各有n个元素的有序表合并成⼀个有序表，其最少的⽐较次数为（）A.nB.2n-1C.2nD.n220.栈和队列共同具有的特点是（）A.都是先进后出B.都是先进先出C.只允许在端点进⾏操作运算D.既能先进先出，也能先进后出21.若⽤⼀个有6个单元的数组来实现循环队列，rear和front的初值分别为0和3。

计算机专业基础综合数据结构（树和二叉树）历年真题试卷汇编13(总分：66.00，做题时间：90分钟)一、综合题(总题数：4，分数：12.00)1.已知下列字符A、B、C、D、E、F、G的权值分别为3、12、7、4、2、8，11，试填写出其对应哈夫曼树HT的存储结构的初态和终态。

【北京工业大学1998五(10分)】__________________________________________________________________________________________正确答案：(设T是一棵二叉树，除叶子结点外，其他结点的度数皆为2，若T中有6个叶结点，试问：（分数：6.00）(1).T树的最大可能深度Kmax=?最小可能深度Kmin=?__________________________________________________________________________________________ 正确答案：(正确答案：(1)T树的最大深度：Kmax=6(除根外，每层均是两个结点)。

T树的最小深度Kmin=4(具有6个叶子的完全二叉树是其中的一种形态)。

)(2).T树中共有多少非叶结点?__________________________________________________________________________________________ 正确答案：(正确答案：非叶子结点数是5(n2=n0—1)。

)(3).若叶结点的权值分别为1，2，3，4，5，6。

请构造一棵哈曼夫树，并计算该哈曼夫树的带权路径长度wp1。

【北京邮电大学1992一、3(15／3分)】__________________________________________________________________________________________正确答案：(正确答案：哈夫曼树见右图，其带权路径长度wp1=51。

数据结构13级期中考试参考答案五邑大学试卷（期中参考答案）课程：数据结构学期： 2021 至 2021 学年度第 2 学期一、单项选择题（10小题，每小题2分，共20分）1．若一个栈的输入序列是1，2，3，…，n，输出序列的第一个元素是n ，则第i个输出元素是（ D ）。

A．不确定 A．顺序表 A． 7B．n-i B．栈C．n-i-1 C．队列D．n-i+1 D．链表2．设计一个判别表达式中左右括号是否配对的算法，采用（ B ）数据结构最佳。

3．设有6个结点的无向图，该图至少应有（ C ）条边才能确保是一个连通图。

B. 6C. 5D. 4D．散列存取 D．O(nlog2n)4．线性表的顺序存储结构是一种（ A ）的存储结构。

A．随机存取 A．O(1)B．顺序存取 B．O(n)C．索引存取 C．O(n2)5．对于n个元素组成的线性表，建立一个有序单链表的时间复杂度是（ C ）。

6．任何一棵二叉树的叶子结点在前序、中序、后序遍历序列中的相对次序（ A ）。

A．肯定不发生改变 C．不能确定B．肯定会发生改变 D．有时发生变化B．从源点到终点的最短路径 D．最短的回路7．关键路径是AOE网中（ A ）。

A．从源点到终点的最长路径 C．最长的回路 for(i=0; i B． O(n)C． O(log2n) C．树形结构 D． O(n2) 8．下列算法的时间复杂度是（ B ）。

9．下列四种基本的逻辑结构中，数据元素之间关系最弱的是（ A ）。

A．集合 B. 线性结构 D. 图状结构 10．在单链表中，若p所指结点不是尾结点，在p之后插入s所指结点的操作是（ B ）。

A．s->next=p; p->next=s C．s->next=p->next; p=s; 二、填空题(10小题，19个空，每空2分，共38分) 1．表示有100个顶点，133条边的无向图的邻接矩阵有（266）个非零矩阵元素。

绝密★考试结束前全国2013年10月高等教育自学考试数据结构试题课程代码：02331请考生按规定用笔将所有试题的答案涂、写在答题纸上。

选择题部分注意事项：1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。

如需改动，用橡皮擦干净后，再选涂其他答案标号。

不能答在试题卷上。

一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。

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

1．算法的时间复杂度表征的是A．算法的可读性B．算法的难易程度C．执行算法所耗费的时间D．执行算法所耗费的存储空间2．对需要频繁插入和删除结点的线性表，适合的存储方式是A．顺序储存B．链式存储C．索引存储D．散列存储3．在头指针为head的循环链表中，判断指针变量P指向尾结点的条件是A．p->next->next==head B．p->next==headC．p->next->next==NULL D．p->next==NULL4．迪杰斯特拉(Dijkstra)算法的功能是A．求图中某顶点到其他顶点的最短路径B．求图中所有顶点之间的最短路径C．求图的最小生成树D．求图的拓扑排序序列5．若栈的进栈序列为1，2，3，4，5，则经过出入栈操作不可能．．．获得的出栈序列是A．4，5，3，2，1 B．4，3，5，1，2C．1，2，3，4，5 D．5，4，3，2，16．A是7×4的二维数组，按行优先方式顺序存储，元素A[0][0]的存储地址为1 000，若每个元素占2个字节，则元素A[3][3]的存储地址为A．1015 B．1016C．1028 D．10307．深度为4的完全二叉树的结点数至少为A．4 B．8C．13 D．158．若采用邻接矩阵A存储有向图G，则结点k的入度等于A中A．结点k对应行元素之和B．结点k对应列元素之和C．结点k对应行和列元素之和D．非零元素之和9．无向图G的邻接矩阵一定是A．对称矩阵B．对角矩阵C．三角矩阵D．单位矩阵10．下列关于有向带权图G的叙述中，错误．．的是A．图G的任何一棵生成树都不含有回路B．图G生成树所含的边数等于顶点数减1C．图G含有回路时无法得到拓扑序列D．图G的最小生成树总是唯一的11．在下列排序算法中，关键字比较次数与初始排列次序无关的是A．冒泡排序B．希尔排序C．直接插入排序D．直接选择排序1 2．对下图进行拓扑排序，可以得到的拓扑序列是A．a b c d e B．b a c d eC．b c a d e D．a b d c e13．下列线性表中，能使用二分查找的是A．顺序存储(2,12,5,6,9,3,89,34,25) B．链式存储(2,12,5,6,9,3,89,34,25) C．顺序存储(2,3,5,6,9,12,25,34,89) D．链式存储(2,3,5,6,9,12,25,34,89) 14．在下列查找方法中，平均查找长度与结点数量无直接关系的是A．顺序查找B．分块查找C．散列查找D．基于B树的查找15．下列排序算法中，时间复杂度为O(nlog2 n)的算法是A．快速排序B．冒泡排序C．直接选择排序D．直接插入排序非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。

A. SA+141B. SA+180C. SA+186D. SA+2107、用无回溯的模式匹配法（KMP法）求串“ababab”的next[j]的值为（）。

A. 010101B. 011221C. 011233D. 011234C.可链接存储D. 数据元素可以是多个字符8、链表不具有的特点是（）。

A. 可随机访问任一元素B. 插入删除不需要移动元素C. 不必事先估计存储空间D. 所需空间与线性表长度成正比9、中缀表达式A*(B+C)/(D-E+F)的后缀表达式是（）。

A. A*B+C/D-E+FB. AB*C+D/E-F+C. ABC+*DE-F+/D. ABCDEF*+/-+10、已知输入序列为abcd，经过输出受限的双端队列后能得到的输出序列是（）。

A. dacbB. cadbC. dbcaD. 以上都不是二、填空题（每空2.5分，共25分）【得分：】1、有如下递归函数：int func(int n){if(n<2) return(n);else return(func(n-1)+func(n-2));}执行语句printf(“%d\n”,func(4));的结果是。

2、若一个算法中的语句频度之和为T(n)=3n+n*log2n+n2，则算法的时间复杂度为O(_ ___)。

3、不带头结点的单链表head为空的条件是。

4、假设为循环队列分配的向量空间为Q[20]（下标从0开始），若队列的长度和队头指针值分别为13和17，则当前队尾指针的值为。

5、将一个A[15][15]的对称矩阵采用只存储下三角中元素的压缩存储（第一个元素为A[0][0]），按行优先存入一维数组B[120]中，A中元素[3][7]在B 数组中的位置为。

6、广义表运算式HEAD(TAIL((a,b,c),(x,y,z)))的结果是。

7、已知L是带头结点的非空单链表，删除首元结点的三条语句为：P=L->next;;free(P);8、表长为N的顺序表，当在任何位置上插入或删除一个元素的概率相等时，第2页共7页第 3 页 共 7 页……………………………………………装………………………………订…………………………线……………………………………………………此处不能书写此处不能书写此处不能书写 此处不能书写此处不能书写 此处不能书写此处不能书写插入一个元素所需移动元素的平均次数为： ；删除一个元素需要移动的元素个数为： 。

《数据结构》期中试卷专业________ 学号_________ 姓名________ 成绩_______一、选择题（本大题共50小题，每小题2分，共100分）1. 若广义表K满足head(K)=tail(K),则K为 ( )A.( )B.( ( ) )C. ( () ),( () )D.( (),(),() )2.若要求尽可能快地对实数数组进行稳定的排序，则应选( )A.快速排序B.堆排序C.归并排序D.基数排序3. 请指出在顺序表{2、5、7、10、14、15、18、23、35、41、52}中，用二分法查找关键码12需做（）次关键码比较。

A.2B.3C.4D.54．对包含N个元素的散列表进行查找，平均查找长度( ）A.为 O(log2N)B.为O(N)C.不直接依赖于ND.上述三者都不是5.一个栈的输入序列为1，2，3，4，下面哪一个序列不可能是这个栈的输出序列（）A. 1，3，2，4B. 2，3，4，1C. 4，3，1，2D. 3，4，2，16．下面关于图的存储的叙述中，哪一个是正确的。

（）A．用相邻矩阵法存储图,占用的存储空间数只与图中结点个数有关,而与边数无关B．用相邻矩阵法存储图,占用的存储空间数只与图中边数有关,而与结点个数无关C．用邻接表法存储图，占用的存储空间数只与图中结点个数有关，而与边数无关D．用邻接表法存储图，占用的存储空间数只与图中边数有关，而与结点个数无关7. 首先访问结点的左子树，然后访问该结点，最后访问结点的右子树，这种遍历称为( )A.前序遍历B.后序遍历C.中序遍历D.层次遍历8.对一棵查找树根结点而言，左子树中所有结点与右子树中所有结点的关键字大小关系是( )A.小于B.大于C.等于D.不小于9.下面关于B-树和B+树的叙述中，不正确的是 ( )A. B-树和B+树都是平衡的多分树B. B-树和B+树都是可用于文件的索引结构C. B-树和B+树都能有效地支持顺序检索D. B-树和B+树都能有效地支持随机检索10. 给定下列有向图和初始结点V1,按深度优先遍历的结点序列为( )A.V1，V2，V4，V5，V3B.V1，V3，V4，V5，V2C.V1，V2，V5，V3，V4D.V1，V2，V3，V4，V511. 在数据结构中，从逻辑上可以把数据结构分成（）。

《数据结构》期中测试班级：姓名：学号：一、填空题：1、在数据结构中，从逻辑上可以把数据结构分为集合、线性结构、树形结构和图状结构，其中树形结构和图状结构合称为非线性结构。

数据结构被形式地定义为二元组（D，S），其中D是数据元素的有限集合，S是D上关系的有限集合。

2、算法的五个重要特性是有穷性、确定性、可行性、输入和输出。

3、一个顺序表第一个元素的存储地址是100，每个元素的长度为3，则第6个元素的地址是115。

在顺序表中插入或删除一个元素，需要平均移动（n+1）/2个元素，具体移动的元素个数与插入或删除元素的位置有关。

顺序表中逻辑上相邻的元素的物理位置相邻。

单链表中逻辑上相邻的元素的物理位置不一定相邻。

单链表中，除了首元结点外，任一结点的存储位置由其前驱结点的指针域指示。

在单链表中设置头结点的作用是使第一个结点与其他结点的操作统一。

4、从一个具有n个结点的单链表中查找其值等于x的结点时，在查找成功的情况下，需平均比较（n+1）/2个结点。

在一个具有n个结点的有序单链表中插入一个新结点并仍然有序的时间复杂度是O（n）。

给定有n个元素的线性表，建立一个有序单链表的时间复杂度是O（n2）。

5、已知L是无表头结点的非空单链表，且指针p所指结点既不是首元结点，也不是尾元结点，试从下列提供的答案中选择合适的语句序列。

在p所指结点后插入s所指结点：4、1。

在p所指结点前插入s所指结点：7、11、8、4、1。

在表首插入s所指结点：5、12。

在表尾插入s所指结点：11、9、1、6。

1)p->next=s;2)p->next=p->next->next;3)p->next=s->next;4)s->next=p->next;5)s->next=L;6)s->next=NULL;7)q=p;8)while(p->next!=q) p=p->next;9)while(p->next!=NULL) p=p->next;10)p=q;11)p=L;12)L=s;13)L=p;6、已知指针p所指结点是某双向链表的中间结点，试从下列提供的答案中选择合适的语句序列。