浙江理工大学数据结构与算法期末样卷 (3)

模拟试卷二参考答案一、单选题（每题2分，共20分）1．B 2．B 3．A 4．C 5．D 6．A 7．C 8．C 9．D 10．D二、填空题（每空1分，共26分） 1.集合结构 线性结构 树结构 图结构 2. O(n) 3.O(1) O(1) 4.7 2 25. 94 3 X Y * + 2 Y * 3 / -6. 16 317.孩子（或子）结点 双亲（或父）结点 8. 45 n(n-1)9.（12，36） （17,5,49） （74，82） （63） 10.减少1（或减少） 11. O(log 2n) O(nlog 2n) 12. n/m三、 运算题（每题6分，共24分） 1．线性表为：（90，40，78，50，34，60）2． 当前序序列为ABKCDFGHIJ ，中序序列为KBCDAFHIGJ 时，逐步形成二叉树的过程如下图4所示：图4 3．用克鲁斯卡尔算法得到的最小生成树为：(1,6)1, (2,4)1, (2,5)2, (5,7)2, (2,6)3, (3,5)7 4．见图5。

图5四、 阅读算法（每题7分，共14分） 1． (1) La=(26,34,57,79,100)(2)La=(57,79,100,34) (3)La=(79,34,57,26,100) 2．前序遍历链式存储的二叉树。

五、算法填空（每空2分，共8 分）(low<=high) K==A[mid].key Binsch(A,mid+1,hight,K) return -1六、编写算法（8分）bool Find(LNode* HL, ElemType &item) {LNode* p=HL; while pif (p->data==item){ return true; }else p=p->next; return false; }。

数据结构期末考试试题及答案一、选择题1. 以下哪种数据结构是线性存储结构？A. 树B. 图C. 栈D. 队列答案：C2. 在链表中，如果一个节点既没有前驱也没有后继，那么这个节点被称作什么？A. 首节点B. 尾节点C. 中间节点D. 孤立节点答案：B3. 树的度是指什么？A. 树中节点的个数B. 树中最大的层次数C. 树的分支数D. 树的节点的度的最大值答案：C4. 在二叉搜索树中，若要查找给定值的节点，当查找失败时应返回的值是？A. -1B. 0C. 1D. 该值本身答案：A5. 快速排序算法的时间复杂度最坏情况下是多少？A. O(n)B. O(nlogn)C. O(n^2)D. O(n!)答案：C二、填空题1. 在顺序表中，元素的物理位置相邻的特点是________，这使得顺序表在________操作上具有较高的效率。

答案：连续性；访问2. 链表相比顺序表的优势在于它能够动态地________存储空间，并且________操作不需要移动大量元素。

答案：分配和释放；插入与删除3. 栈是一种________的数据结构，只允许在________进行插入和删除操作。

答案：后进先出；栈顶4. 图的遍历算法主要有两种，分别是________和________。

答案：深度优先搜索；广度优先搜索5. 哈夫曼树是一种特殊的二叉树，它常用于数据压缩，其构建过程是基于________原则。

答案：最小权值三、简答题1. 请简述数组和链表的优缺点。

答案：数组通过索引直接访问元素，访问速度快，但大小固定，插入和删除操作需要移动大量元素。

链表元素通过指针连接，可以动态分配大小，插入和删除效率高，但访问速度较慢，因为需要从头开始遍历。

2. 什么是二叉树的前序遍历、中序遍历和后序遍历？答案：二叉树的前序遍历是先访问根节点，然后遍历左子树，最后遍历右子树。

中序遍历是先遍历左子树，然后访问根节点，最后遍历右子树。

后序遍历是先遍历左子树，然后遍历右子树，最后访问根节点。

《数据结构》期末考试试卷试题及答案第一部分：选择题（每题2分，共20分）1. 下面哪个数据结构是线性结构？A. 树B. 图C. 队列D. 网络流2. 下面哪个数据结构用于实现广度优先搜索算法？A. 栈B. 队列C. 散列表D. 堆3. 下面哪个数据结构用于实现深度优先搜索算法？A. 栈B. 队列C. 散列表D. 堆4. 下面哪个数据结构用于实现快速排序算法？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. 二叉树的节点最多有______个子节点。

3. 堆是一种特殊的______。

4. 散列表的查找效率取决于______。

5. 图的遍历算法包括______和______。

6. 快速排序算法的平均时间复杂度为______。

7. 哈希表中的冲突解决方法有______和______。

8. 最小树算法包括______和______。

9. 最短路径算法包括______和______。

10. 并查集算法用于解决______问题。

第三部分：简答题（每题10分，共50分）1. 请简述栈和队列的区别。

2. 请简述二叉搜索树的特点。

3. 请简述哈希表的原理。

4. 请简述图的深度优先搜索算法。

5. 请简述最小树算法的原理。

第四部分：编程题（每题20分，共50分）1. 编写一个函数，实现链表的插入操作。

数据结构与算法期末考试题及答案一、选择题1. 用于分离由加权无向边组成的完全连通图中连通分量中不相邻顶点的单纯形算法是（C）A. 最小生成树算法B. 广度优先搜索算法C. 最大流算法D. 关键路径算法2. 要设计一个使用图来表示的行业里的公司的决策问题，图的顶点应该表示（B）A. 公司拥有的资源B. 公司所面对的决策选择C. 公司内部的组织结构D. 公司的竞争对手3. 算法的计算时间复杂度O(log2n)中的n表示（A）A. 求解问题规模B. 求解算法所处理的数据量C. 求解问题中所涉及的参数量D. 求解算法所进行的求解步骤4. 以树形结构存储的优先队列中元素出队的操作时间复杂度是（C）A. O(1)B. O(n)C. O(log2n)D. O(n2)5. 以下关于贝尔曼-福特算法的描述错误的是（A）A. 贝尔曼-福特算法是求图 G=(V,E)最小生成树的法B. 贝尔曼-福特算法克服了Prim算法因存储顶点增量重复而带来的内存浪费C. 求解过程中，要维护贝尔曼-福特树中任意两个顶点之间的最短距离D. 贝尔曼-福特算法可以解决单源最短路径问题二、简答题1. 请说明拓扑排序的概念，以及如何使用拓扑排序解决求解关键路径的问题。

拓扑排序是指对有向无环图进行排序，得到一个顶点的线性序列，使得对于图中的每条有向边（u,v），均有u在v之前。

拓扑排序可用于求解关键路径，首先对所有活动按照拓扑排序的方法进行排序，计算该活动的最早开始时间ESi和最晚开始时间LSi，若ESi=LSi，则此活动运行期间不能延迟，为关键活动；若ESi≠LSi，则此活动可以合理推迟，不为关键活动。

算法与数据结构期末考试卷一、选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构被称为：A. 链表B. 栈C. 队列D. 数组2. 快速排序算法的时间复杂度在最坏情况下是：A. O(n)B. O(n log n)C. O(n^2)D. O(log n)3. 哈希表解决冲突最常用的方法是：A. 链地址法B. 线性探测法C. 二次探测法D. 双重哈希法4. 二叉树的遍历方式不包括：A. 前序遍历B. 中序遍历C. 后序遍历D. 广度优先遍历5. 堆排序算法是基于：A. 链表B. 栈C. 队列D. 堆...（此处省略其他选择题）二、简答题（每题10分，共20分）1. 请简述二叉搜索树与普通二叉树的区别。

2. 什么是递归？请举例说明递归在算法中的应用。

三、编程题（每题15分，共30分）1. 编写一个函数，实现对链表的反转。

2. 编写一个函数，实现快速排序算法。

四、综合应用题（每题15分，共30分）1. 描述如何使用哈希表实现一个简单的数据库索引系统。

2. 假设你有一个数组，其中包含了一些重复的数值，请编写一个算法来找出数组中出现次数超过数组长度一半的数值。

五、论述题（每题15分，共15分）1. 论述动态规划与贪心算法的区别，并给出一个动态规划问题的例子。

六、附加题（10分，可选做）1. 请设计一个算法，用于检测一个字符串是否是回文。

如果字符串是回文，请返回True，否则返回False。

注意：本试卷中所有题目的答案必须以书面形式给出，编程题需要提供完整的代码实现。

祝各位考生考试顺利，取得优异成绩。

数据结构期末考试试题及答案一、选择题1. 评价一个算法时间性能的主要标准是( )。

A、算法易于调试B、算法易于理解C、算法的稳定性和正确性D、算法的时间复杂度2. 计算机算法具备有输入、输出、（）等五个特性。

A、可行性、可移植性和可扩充性B、可行性、确定性和有穷性C、确定性、有穷性和稳定性D、易读性、稳定性和安全性3. 带头结点的单链表head为空的判定条件是（）。

A、head==NULLB、head->next==NULLC、head->next==headD、head！=NULL4. 以下关于线性表的说法不正确的是( )。

A、线性表中的数据元素可以是数字、字符、记录等不同类型。

B、线性表中包含的数据元素个数不是任意的。

C、线性表中的每个结点都有且只有一个直接前趋和直接后继。

D、存在这样的线性表：表中各结点都没有直接前趋和直接后继。

5. 在顺序表中，只要知道( )，就可在相同时间内求出任一结点的存储地址。

A、基地址B、结点大小C、向量大小D、基地址和结点大小6. ( )运算中，使用顺序表比链表好。

A、插入B、删除C、根据序号查找D、根据元素值查找7. 一个长度为n的顺序表中，向第i个元素之前插入一个新元素时，需要向后移动（）个元素A、n-iB、n-i+1C、n-i-1D、i8. ( )适合作为经常在首尾两端操作线性表的存储结构。

A、顺序表B、单链表C、循环链表D、双向链表9. 栈和队列的共同点是（）A、都是先进后出B、都是先进先出C、只允许在端点处插入和删除元素D、没有共同点10. 一个队列的入列序列是1 2 3 4，则队列的输出序列是( )。

A、4 3 2 1B、1 2 3 4C、1 4 3 2D、3 2 4 111. 队列与一般的线性表的区别在于( )。

A、数据元素的类型不同B、运算是否受限制C、数据元素的个数不同D、逻辑结构不同12. “假上溢”现象会出现在( )中。

A、循环队列B、队列C、链队列D、顺序队列二、填空题1．数据的逻辑结构被分为集合、线性结构、树形结构和图结构。

数据结构期末考试题及答案一、选择题（每题2分，共20分）1. 在数据结构中，线性表的顺序存储结构通常使用什么数据结构来实现？A. 链表B. 数组C. 栈D. 队列答案：B2. 以下哪个是二叉树的性质？A. 每个节点最多有两个孩子B. 每个节点最多有三个孩子C. 每个节点最多有四个孩子D. 每个节点最多有五个孩子答案：A3. 在图的遍历算法中，深度优先搜索（DFS）和广度优先搜索（BFS）的区别是什么？A. DFS使用队列，BFS使用栈B. DFS使用栈，BFS使用队列C. DFS和BFS都使用栈D. DFS和BFS都使用队列答案：B...20. 以下哪个排序算法的时间复杂度为O(n^2)？A. 冒泡排序B. 选择排序C. 插入排序D. 所有上述排序算法答案：D二、简答题（每题10分，共30分）1. 简述链表和数组的区别。

答案：链表和数组都是用来存储数据的线性数据结构。

数组是连续的内存空间，可以随机访问，但插入和删除操作效率较低；链表由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针，不支持随机访问，但插入和删除操作较为高效。

2. 什么是递归？请给出一个递归算法的例子。

答案：递归是一种算法设计技术，它允许函数调用自身来解决问题。

递归通常包含基本情况和递归情况。

例如，计算阶乘的递归算法：f(n) = n * f(n-1)，其中基本情况是f(1) = 1。

...三、算法设计题（每题25分，共50分）1. 给定一个整数数组，请设计一个算法找出数组中的第k大元素。

答案：可以采用快速选择算法，类似于快速排序的划分过程，通过随机选择一个元素作为基准，将数组分为两部分，一部分包含比基准大的元素，另一部分包含比基准小的元素。

然后根据k与基准元素的位置关系，决定是继续在左侧子数组还是右侧子数组中进行查找。

2. 描述如何使用哈希表解决字符串匹配问题。

答案：哈希表可以用于实现字符串匹配的KMP算法。

首先，构建模式字符串的前缀函数，该函数用于记录模式字符串中每个位置的最长相同前缀和后缀的长度。

江西财经大学－第学期期末考试试卷试卷代码：03266A 授课课时：112课程名称：数据结构与算法适用对象：本科一、单项选择题(从下列各题四个备选答案中选出一个正确答案，并将其代号写在答题纸相应位置处。

答案错选或未选者，该题不得分。

每小题2分，共24分。

)1.数据结构被形式地定义为(K,R)，其中K是数据元素的有限集，R是K上的___有限集。

A.操作B.映像C.存储D.关系2.线性表若采用链式存储结构时，要求内存中可用存储单元的地址____。

A.必须连续的B.部分地址必须连续的C.一定是不续的D.连续不连续都可以3.一个栈的入栈序列是a、b、c、d、e，则栈的不可能输出序列是____。

A.edcbaB.decbaC.dceabD.abcde4.一个队列的入队序列是1、2、3、4，则队列输出序列是____。

A.4、3、2、1B.1、2、3、4C.1、4、3、2D.3、2、4、15.栈和队列的共同点是____。

A.都是先进后出B.都是先进先出C.只允许在端点处插入、删除元素D.没有共同点6.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行____。

A. s->next = p->next; p->next=s;B. p->next = s->next; s->next = p;C. q->next = s; s->next = p;D. p->next = s; s->next = q;7.设串s1=‘ABCDEFG’，s2=‘PQRST’，函数con (x, y) 返回x与y串的连接串，函数subs (s, i, j) 返回串s的从序号i的字符开始的j个字符组成的子串，函数len (s) 返回串s的长度，则con (subs (s1, 2, len (s2)), subs (s1, len (s2), 2)) 的结果串是____。

浙江理工大学数据结构与算法期末样卷(1)模拟试卷二一、单选题（每题2分，共20分）1．在一个具有额外字段结点的单链表中hl中，若要向字段填入一个由指针p指向的结点，则继续执行()a.hl=p;p->next=hl;b.p->next=hl->next;hl->next=p;c.p->next=hl;p=hl;d.p->next=hl;hl=p;2．若顺序存储的循环队列的queuemaxsize=n,则该队列最多可以存储（）个元素a.nb.n-1c.n+1d.不确定3．下列哪一条就是顺序存储方式的优点？（）a.存储密度大b.插入和删除运算方便c.获取符合某种条件的元素方便d.查找运算速度快4．建有一个二维数组a[m][n]，假设a[0][0]放置边线在600(10)，a[3][3]放置边线在678(10)，每个元素占到一个空间，问a[2][3](10)存放在什么边线？(注释(10)则表示用10十进制则表示,m>3)a.658b.648c.633d.6535．下列关于二叉树遍历的叙述中，正确的是()a.若一个树叶就是某二叉树的中序结点的最后一个结点，则它必就是该二叉树的前序结点最后一个结点b.若一个点是某二叉树的前序遍历最后一个结点，则它必是该二叉树的中序遍历的最后一个结点c.若一个结点就是某二叉树的中序结点的最后一个结点，则它必就是该二叉树的前序最后一个结点d.若一个树叶是某二叉树的前序最后一个结点，则它必是该二叉树的中序遍历最后一个结点6．k层二叉树的结点总数最多为()a.2k-1b.2k+1c.2k-1d.2k-17．对线性表展开二分法搜寻，其前提条件就是()a.线性表以链接方式存储，并且按关键码值排好序b.线性表以顺序方式存储，并且按关键码值的检索频率排好序c.线性表以顺序方式存储，并且按关键码值排好序d.线性表以链接方式存储，并且按关键码值的检索频率排好序8．对n个记录进行堆排序，所需要的辅助存储空间为()a.o（1og2n）b.o（n）c.o（1）d.o（n2）9．对于线性表（7，34，77，25，64，49，20，14）展开杂凑存储时，若采用h（k）=k%7做为杂凑函数，则杂凑地址为0的元素存有（）个，a.1b.2c.3d.410．以下关于数据结构的描述中，恰当的就是()a.数组就是相同类型值的子集b.递归算法的程序结构比迭代算法的程序结构更为精炼c.树是一种线性结构d.用一维数组存储一棵全然二叉树就是有效率的存储方法二、填空题（每空1分，共26分）1．数据的逻辑结构被分成_________、________、__________和___________四种。

数据结构与算法测试题+参考答案一、单选题（共80题，每题1分，共80分）1、某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用什么存储方式最节省运算时间？A、仅有头指针的单循环链表B、双链表C、仅有尾指针的单循环链表D、单链表正确答案：C2、数据结构研究的内容是（）。

A、数据的逻辑结构B、数据的存储结构C、建立在相应逻辑结构和存储结构上的算法D、包括以上三个方面正确答案：D3、下列关于无向连通图特征的叙述中，正确的是：所有顶点的度之和为偶数边数大于顶点个数减1至少有一个顶点的度为1A、只有1B、1和2C、1和3D、只有2正确答案：A4、下面的程序段违反了算法的（）原则。

void sam(){ int n=2;while (n%2==0) n+=2;printf(“%d”,n);}A、确定性B、可行性C、有穷性D、健壮性正确答案：C5、对任意给定的含 n (n>2) 个字符的有限集 S，用二叉树表示 S 的哈夫曼编码集和定长编码集，分别得到二叉树 T1 和 T2。

下列叙述中，正确的是：A、出现频次不同的字符在 T2 中处于相同的层B、出现频次不同的字符在 T1 中处于不同的层C、T1 的高度大于 T2 的高度D、T1 与 T2 的结点数相同正确答案：A6、数据序列{ 3，2，4，9，8，11，6，20 }只能是下列哪种排序算法的两趟排序结果？A、快速排序B、选择排序C、插入排序D、冒泡排序正确答案：A7、设散列表的地址区间为[0,16]，散列函数为H(Key)=Key%17。

采用线性探测法处理冲突，并将关键字序列{ 26，25，72，38，8，18，59 }依次存储到散列表中。

元素59存放在散列表中的地址是：A、11B、9C、10D、8正确答案：A8、采用递归方式对顺序表进行快速排序，下列关于递归次数的叙述中，正确的是：A、每次划分后，先处理较短的分区可以减少递归次数B、递归次数与每次划分后得到的分区处理顺序无关C、递归次数与初始数据的排列次序无关D、每次划分后，先处理较长的分区可以减少递归次数正确答案：B9、以下数据结构中，（）是非线性数据结构。

浙江理工大学C程序设计试题(三)一、判断题（判断下列各小题，正确的在题后括号内打"√"，错的打"×"。

每小题1分，共10分）1. 结构体变量可以被整体赋值.2. 字符型数组中可以存放字符串3. 可以对整型数组进行整体输入、输出4. 在C语言程序中，在函数内部定义的变量称为静态局部变量。

5. 语句“b=+3;”和“b+=3;”运行后的结果是不一样的。

6.‘\f’是不正确的字符常量。

7. 运算符“+”不能作为单目运算符。

8. (a*x*x+bx+c)/(2*a)是合法的C语言表达式。

9.表达式!!3的值是1。

10.表达式~(2<<1)的值是-5。

二、单项选择题（在每小题的四个备选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。

每小题2分，共20分）1．在C语言中，不正确的unsigned char类型的常数是________A 32768B 0C 037D 0xDF2．当c的值不为0时，在下列选项中能正确将c的值赋给变量a、b的是______A c=b=a；B (a=c)‖(b=c)；C (a=c)&(b=c)；D a=c=b；3．在C语言类型中,int ,char, short等类型的长度是_________A.固定的B.由用户自己定义C.任意的D.与机器字长有关4．以下程序的输出结果是________main( ){int a= -1，b=1，k；if((++a<0) | | ! (b-- <=0))printf("%d-- %d\n"，a，b)；elseprintf("%d-- %d\n"，b，a)；}A -1--1B 0--1C 1--0D 0--05．设有程序段: t=6;a=7;b=8; if(a=b)t=a;,这段程序执行后,t的结果是______A. 6B.7C.8D.06．设a=1,b=2,c=3,d=4,则表达式:a>b?a:c>d?a:d的结果为___________A 4B 3C 2D 17.若a为二维数组,它有m列,则a[i][j]在数组中的位置是_________A. i*m+jB. j*m+iC. i*m+j-1D. i*m+j+18．设有如下定义：int x=l，y=-1；，则语句：printf("%d\n"，(x--&++y))；的输出结果是____ A 1 B 0 C -1 D 29.下面程序段不是死循环的是_____________A.int j=100;while(1){j=j%100+2;if(j>100)break;}B.for( ; ; );C.int k=0; do{ ++k;}while(k>=0);D.int s=36; while(s);--s;10.下列表达式中,错误的是______.A.2>1 ? a:bB.ijC.4.0%++2.0D.x*=y+8三、程序填空题（阅读以下程序说明和相应程序（段），在每小题提供的若干可选答案中，选出一个正确答案，并将正确答案的序号填在题干的括号内。

2022年浙江大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。

A.串B.树C.广义表D.栈2、哈希文件使用哈希函数将记录的关键字值计算转化为记录的存放地址，因为哈希函数是一对一的关系，则选择好的（）方法是哈希文件的关键。

A.哈希函数B.除余法中的质数C.冲突处理D.哈希函数和冲突处理3、静态链表中指针表示的是（）。

A.下一元素的地址B.内存储器的地址C.下一元素在数组中的位置D.左链或右链指向的元素的地址4、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。

A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front5、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l6、下列选项中，不能构成折半查找中关键字比较序列的是（）。

A．500，200，450，180 B．500，450，200，180C．180，500，200，450 D．180，200，500，4507、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。

A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，198、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。

A.二叉排序树B.哈夫曼树C.AVL树D.堆9、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（）个不同的码字。

2020-2021《数据结构与算法》期末课程考试试卷适用专业： 考试日期： 闭卷 所需时间：120分钟 总分：100分一、 选择题(每题1分, 共20题，总共20分)。

1.算法分析的目的是（ ） A ．辨别数据结构的合理性 B ．评价算法的效率C ．研究算法中输入与输出的关系D ．鉴别算法的可读性2.在一个单链表HL 中，若要在当前由指针p 指向的结点后面插入一个由q 指向的结点，则执行如下( )语句序列。

A. p=q; p->next=q;B. p->next=q; q->next=p;C. p->next=q->next; p=q;D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（ ）A. 在队列第i 个元素之后插入一个元素B. 从队头删除一个元素C. 判断一个队列是否为空D.读取队头元素的值4.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。

A ． 11 B.35 C. 19 D. 535.如下图所示的4棵二叉树中，（ ）不是完全二叉树。

6．下面关于线性表的叙述中，错误的是哪一个？（ ）A ．线性表采用顺序存储，必须占用一片连续的存储单元。

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

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

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

7．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ ）存储方式最节省运算时间。

A ．单链表B ．仅有头指针的单循环链表C ．双链表D ．仅有尾指针的单循环链表8. 若长度为n 的线性表采用顺序存储结构，在其第i 个位置插入一个新元素的算法的时间复杂度为（ ）(1<=i<=n+1)。

A. O(0)B. O(1)C. O(n)D. O(n 2)9. 若已知一个栈的入栈序列是1,2,3,…,n ，其输出序列为p 1,p 2,p 3，…，p N ,若p N 是n ，则p i 是( )。

2011-2012学年第一学期期末考查《数据结构》试卷（答案一律写在答题纸上，在本试卷上做答无效）一、选择（每题1分，共10分）1.长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法时间复杂度为（）A.O(0)B.O(1)C.O(n)D.O(n2)2.六个元素按照6，5，4，3，2，1的顺序入栈，下列哪一个是合法的出栈序列？（）A.543612B.453126C.346512D.2341563.设树的度为4，其中度为1、2、3、4的结点个数分别是4、2、1、2，则树中叶子个数为（）A.8B.9C.10D.114.设森林F对应的二叉树B有m个结点，B的右子树结点个数为n，森林F中第一棵树的结点个数是（）A. m-nB.m-n-1C.n+1D.m+n5.若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（）A.9B.11C.15D.不确定6.下列哪一个方法可以判断出一个有向图是否有环。

（）A.深度优先遍历B.拓扑排序C.求最短路径D.求关键路径7.第7层有10个叶子结点的完全二叉树不可能有（）个结点。

A.73B.234C.235D.2368.分别用以下序列构造二叉排序树，与用其他三个序列构造的结果不同的是（）A.（100,80,90,60,120,110,130）B.（100, 120, 110,130,80, 60,90）C.（100,60,80,90,120,110,130）D.（100,80, 60,90, 120, 130,110）9.对一组数据（84，47，25，15，21）排序，数据的排列次序在排序过程中变化如下：（1）84 47 25 15 21 （2）15 47 25 84 21 （3）15 21 25 84 47（4）15 21 25 47 84则采用的排序方法是（）A.选择排序B.起泡排序C.快速排序D.插入排序10.对线性表进行折半查找时，要求线性表必须（）A.以顺序方式存储B.以顺序方式存储，且数据元素有序C.以链接方式存储D.以链接方式存储，且数据元素有序二、填空（每空1分，共15分）1.数据结构中评价算法的两个重要指标是、空间复杂度。

浙 江 理 工 大 学二O一二年硕士学位研究生招生入学考试试题考试科目：数据结构 代码：991 （请考生在答题纸上答题，在此试题纸上答题无效）一、单选题(每题2分，共20分)1. 不带头结点的单链表simpleList为空的判定条件是。

A. simpleList == nullB. simpleList->next == nullC. simpleList->next = simpleListD. simpleList! = null2. 某线性表最常用的操作是在最后一个结点之后插入一个结点或删除第一个结点，故采用_______________存储方式最节省运算时间。

A. 单链表B. 仅有头结点的单循环链表C. 双链表D. 仅有尾指针的单循环链表3. 向一个栈顶指针为top的链栈中插入一个S所指结点时，则执行_______________________。

A. top->next = S;B. S->next = top->next; top->next = S;C. S->next = top; top = S;D. S->next = top; top = top->next;4. 一维数组和线性表的区别是_____________。

A. 前者长度固定，后者长度可变B. 后者长度固定，前者长度可变C. 两者长度均固定D. 两者长度均可变5. 设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分按行序存放在一维数组B[1, n(n-1)/2]中，对任一下三角部分中任一元素a ij(),在一组数组B的下标位置K的值是______。

A. i(i-1)/2+j-1B. i(i-1)/2+jC. i(i+1)/2+j-1D. i(i+1)/2+j6.在线索化二叉树中，P所指的结点没有左子树的充要条件是_______________________。

《数据结构与算法》期末考试试题及答案一、选择题A、94,32,40,90,80,46,21,691.在逻辑上可以把数据结构分A.P->NE某T=Q->NE某T;FREE(Q);B、32,40,21,46,69,94,90,80成（A）B.Q->NE某T=P;FREE(Q);C21,32,46,40,80,69,90,94A.线性结构和非线性结构D、90,69,80,46,21,32,94,40B.动态结构和静态结构C.Q->NE 某T=P->NE某T;FREE(Q);21.若用冒泡排序对关键字序C.紧凑结构和非紧凑结构D.P->NE某T=S;S->NE某T=P;列（18,16,14,12,10,8）进行从D.内部结构和外部结构2.单链表中各结点之间的地址（C）A.必须连续B.部分必须连续C.不一定连续D.以上均不对3.在一个长度为n的顺序表中向第i个元素（0<i<=n+1）之前插入一个新元素时，需向后移动（B）个元素。

A、n-iB、n-i+1C、n-i-1D、i4.插入和删除操作只能在一端进行的线性表，称为（C）。

A.队列B.线性表C.栈D.循环队列5、队列是仅允许在（）进行插入，而在（）进行删除。

(A)A.队尾，队首B.队尾，队尾C.队首，队尾D.队首，队首6.链表适合于（A）查找。

A.顺序B.二分C.随机D.顺序或二分7.数据的基本单位是（A）。

A.数据元素B.数据结构C.数据项D.数据对象8.下列哪个不是算法的特性（B）。

A.有穷性B.可数性C.可行性D.确定性9.在表长为n的顺序表中进行线性查找，它的平均查找长度为（B）。

A.ASL=nB.ASL=(n+1)/2C.ASL=n+1D.ASL=log2n10.一个线性表第一个元素的存储地址是320，每个元素的长度为3，则第五个元素的地址是(C）。

A.311B.328C.332D.31311.设front、rear分别为循环双向链表结点的左指针和右指针，则指针P所指的元素是双循环链表L的尾元素的条件是（D）。

数据结构与算法期末练习题（含答案）《数据结构与算法》期末练习⼀选择题1．以下与数据的存储结构⽆关的术语是（ D ）。

A．循环队列 B. 链表 C. 哈希表 D. 栈2. 算法的时间复杂度取决于（ A ）A．问题的规模 B. 待处理数据的初态 C. A和B D. 计算机cpu3. ⼀个栈的输⼊序列为1 2 3 4 5，则下列序列中不可能是栈的输出序列的是（ B ）。

A. 2 3 4 1 5B. 5 4 1 3 2C. 2 3 1 4 5D. 1 5 4 3 24. 有关静态链表的叙述：(1) 静态链表既有顺序存储的优点，⼜有动态链表的优点。

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

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

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

以上错误的是（ B ）A．（1），（2） B．（1） C．（1），（2）,(3) D.（2）5．对于有n 个结点的⼆叉树, 其⾼度为（ D ）A．nlog2n B．log2n C．?log2n?|+1 D．不确定6．从下列有关树的叙述中,选出正确的叙述（ C ）A．⼆叉树中每个结点有两个⼦结点,⽽树⽆此限制,因此⼆叉树是树的特殊情况。

B．当K≥1时⾼度为K的⼆叉树⾄多有2k-1个结点。

C．哈夫曼树是带权路径最短的树,路径上权值较⼤的结点离根较近。

D．在⼆叉树中插⼊结点,该⼆叉树便不再是⼆叉树。

7．设⽆向图的顶点个数为n，则该图最多有（ B ）条边。

A．n-1 B．n(n-1)/2 C． n(n+1)/2 D．0 E．n28．已知有向图G=(V,E)，其中V={V1,V2,V3,V4,V5,V6,V7}，E={, , , , , , , , },G的拓扑序列是（ A ）。

A．V1,V3,V4,V6,V2,V5,V7 B．V1,V3,V2,V6,V4,V5,V7C．V1,V3,V4,V5,V2,V6,V7 D．V1,V2,V5,V3,V4,V6,V79．下列排序算法中，其中（ D ）是稳定的。