院系：—————— 专业班级：——————— 姓名：——————— 学号：——————
装 订 线
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. 53
5.如下图所示的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(n2)
9. 若已知一个栈的入栈序列是1,2,3,…,n，其输出序列为p1,p2,p3，…，pN,若pN是n，则pi是( )。
A. i B. n-i C. n-i+1 D. 不确定
10. 若栈采用顺序存储方式存储，现两栈共享空间]，top[i]代表第i个栈( i =1,2)栈顶，栈1的底在v[1]，栈2的底在V[m]，则栈满的条件是（ ）。
A. |top[2]-top[1]|=0 B. top[1]+1=top[2]
C. top[1]+top[2]=m D. top[1]=top[2]
11．下面关于串的的叙述中，哪一个是不正确的？（ ）
A．串是字符的有限序列 B．空串是由空格构成的串
C．模式匹配是串的一种重要运算 D．串既可以采用顺序存储，也可以采用链式存储
12. 设有数组A[i,j]，数组的每个元素长度为3字节，i的值为1 到8 ，j的值为1 到10，数组从内存首地址BA开始顺序存放，当用以列为主存放时，元素A[5，8]的存储首地址为( )。
A. BA+141 B. BA+180 C. BA+222 D. BA+225
13. 将一个A[1..100，1..100]的三对角矩阵，按行优先存入一维数组B[1‥298]中，A中元素A6665（即该元素下标i=66，j=65），在B数组中的位置K为（ ）。供选择的答案：A. 198 B. 195 C. 197 D.200
14. 设树T的度为4，其中度为1，2，3和4的结点个数分别为4，2，1，1 则T中的叶子数为（ ）
A．5 B．6 C．7 D．8
15. 在下述结论中，正确的是（ ）
①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。
A．①②③ B．②③④ C．②④ D．①④
16. 一个具有1025个结点的二叉树的高h为（ ）
A．11 B．10 C．11至1025之间 D．10至1024之间
17．一个n个顶点的连通无向图，其边的个数至少为（ ）。
A．n-1 B．n C．n+1 D．nlogn；
18. 设哈希表长为14，哈希函数是H(key)=key%11,表中已有数据的关键字为15，38，61，84共四个，现要将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是( )
A．8 B．3 C．5 D．9
19．当采用分快查时，数据的组织方式为 ( )
A．数据分成若干块，每块内数据有序
B．数据分成若干块，每块内数据不必有序，但块间必须有序，每块内最大（或最小）的数据组成索引块
C. 数据分成若干块，每块内数据有序，每块内最大（或最小）的数据组成索引块
D. 数据分成若干块，每块（除最后一块外）中数据个数需相同
20．有一组数据（15，9，7，8，20，-1，7，4） 用快速排序的划分方法进行一趟划分后数据的排序为 ( )（按递增序）。
A．下面的B，C，D都不对。 B．9，7，8，4，-1，7，15，20
C．20，15，8，9，7，-1，4，7 D. 9，4，7，8，7，-1，15，20
二、填空题(共10空，总共10分):
1.在具有n个单元的循环队列中，队满时共有 个元素。
2.若对关键字序列（43，02，80，48，26，57，15，73，21，24，66）进行一趟增量为3的希尔排序，则得到的结果为 。
3.二叉树中度为0的结点数为30，度为1的结点数为30，总结点数为 。
4.设有一个顺序栈S，元素sl，s2，s3，s4，s5，s6依次进栈，如果6个元素的出栈顺序为s2，s3，s4，s6，s5，sl，则顺序栈的容量至少应为 。
5.n（n＞0）个顶点的无向图最多有 条边。
6.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________，在表尾插入元素的时间复杂度为_ _ 。
7.数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。
8.当用长度为N的数组顺序存储一个栈时，假定用top==N表示栈空，则表示栈满的条件是_____________________。
三、应用题(共7小题，每小题10分，总共70分):
1．试对图1中的二叉树画出其：
(1)顺序存储表示的示意图；
(2)二叉链表存储表示的示意图。
2．编写从类型为List的线性表L中将第i个元素删除的算法，（假定不需要对i的值进行有效性检查,也不用判别L是否为空表。）void Delete(List& L, int i)
3．已知一棵二叉树的前序遍历的结果是ABKCDFGHIJ, 中序遍历的结果是KBCDAFHIGJ, 试画出这棵二叉树。
4．已知一个图的顶点集V为：V={1,2,3,4,5,6,7};其共有10条边。该图用如下边集数组存储：
起点 | 1 | 2 | 2 | 5 | 5 | 2 | 2 | 6 | 1 | 3 |
终点 | 6 | 4 | 5 | 4 | 7 | 6 | 7 | 7 | 7 | 5 |
权 | 1 | 1 | 2 | 2 | 2 | 3 | 3 | 4 | 5 | 7 |
试用克鲁斯卡尔算法依次求出该图的最小生成树中所得到的各条边及权值。
5．假定一棵二叉树广义表表示为a(b(c),d(e,f))，分别写出对它进行先序、中序、后序、按层遍历的结果。
6．写出利用直接选择排序对关键字序列 (40,24,80,39,43,18,20) 进行从小到大排序的每一趟结果。
7．用递归的算法编写出对存入在a[n+1]数组中的n个有序元素进行二分（又称折半）查（假定a[0]单元不用）的程序。int halfsearch(SSTable *a, KeyType k,int low,int high)
2020-2021《数据结构与算法》期末课程考试试卷答案
一、选择题(每题1分, 共20题，总共20分)。
1-10答案：BDABCBDC DB
11-20答案： BDBBD DCAC B A
二、填空题(共10空，总共10分):
1.答案：n-1 (15,02,21,24,26,57,43,66,80,48,73) 89 3 n(n-1)／2 O(n) O(1) 关系 图 top==0
三、应用题(共7小题，每小题10分，总共70分):
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论