2022年北京理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A
2022年北京理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A
一、选择题
1、下列说法不正确的是( )。
A.图的遍历是从给定的源点出发每个顶点仅被访问一次
B.遍历的基本方法有两种:深度遍历和广度遍历
C.图的深度遍历不适用于有向图
D.图的深度遍历是一个递归过程
2、下列排序算法中,占用辅助空间最多的是( )。
A.归并排序 B.快速排序 C.希尔排序D.堆排序
3、线性表的顺序存储结构是一种( )。
A.随机存取的存储结构 B.顺序存取的存储结构
C.索引存取的存储结构 D.Hash存取的存储结构
4、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7}, E={,,,,, ,,,},G的拓扑序列是( )。
A.V1,V3,V4,V6,V2,V5,V7 B.V1,V3,V2,V6,V4,V5,V7
C.V1,V3,V5,V2,V6,V7 D.V1,V2,V5,V3,V4,V6,V7
5、用不带头结点的单链表存储队列,其队头指针指向队头结点,队尾指针指向队尾结点,则在进行出队操作时( )。
A.仅修改队头指针
B.仅修改队尾指针
C.队头、队尾指针都可能要修改
D.队头、队尾指针都要修改
6、下列关于无向连通图特性的叙述中,正确的是( )。
Ⅰ.所有的顶点的度之和为偶数 Ⅱ.边数大于顶点个数减1 Ⅲ.至少有一个顶点的度为1
A.只有Ⅰ B.只有Ⅱ C.Ⅰ和Ⅱ D.Ⅰ和Ⅲ
7、排序过程中,对尚未确定最终位置的所有元素进行一遍处理称为一趟排序。下列排序方法中,每一趟排序结束时都至少能够确定一个元素最终位置的方法是( )。
Ⅰ.简单选择排序Ⅱ.希尔排序 Ⅲ.快速排序 Ⅳ.堆排 Ⅴ.二路归并排序
A.仅Ⅰ、Ⅲ、Ⅳ B.仅Ⅰ、Ⅱ、Ⅲ C.仅Ⅱ、Ⅲ、Ⅳ D.仅Ⅲ、Ⅳ、Ⅴ
8、一棵哈夫曼树共有215个结点,对其进行哈夫曼编码,共能得到( )个不同的码字。
A.107 B.108 C.214 D.215
9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中有( )个叶子。
A.log2n B.(n-1)/2 C.log2n+1 D.(n+1)/2
10、下面关于B和B+树的叙述中,不正确的是( )
A.B树和B+树都是平衡的多叉树 B.B树和B+树都可用于文件的索引结构
C.B树和B+树都能有效地支持顺序检索 D.B树和B+树都能有效地支持随机检索
二、填空题
11、对n个记录的表r[1..n]进行简单选择排序,所需进行的关键字间的比较次数为 。
12、有向图G=(V,E),其中V(G)={0,1,2,3,4,5},用 三元组表示弧及弧上的权d。E(G)为E(G)={<0,5,100>,<0, 2,10>,<1,2,5>,<0,4,30>,<4,5,60>,<3,5,10>,<2, 3,50>,<4,3,20>},则从源点0到顶点3的最短路径长度是 ,经过的中间顶点是 。
13、在单链表L中,指针P所指结点有后继结点的条件是 。
14、对于一个具有n个结点的单链表,在已知的结点半p后插入一个新结点的时间复杂度为 ,在给定值为x的结点后插入一个新结点的时间复杂度为 。
15、数据结构中评价算法的两个重要指标是 。
16、当两个栈共享一存储区时,栈利用一维数组stack(1,n)表示,两栈顶指针为top[1]与top[2],则当栈1空时,top[1]为 ,栈2空时, top[2]为 ,栈满时为 。
17、下列程序是快速排序的非递归算法,请填写适当的语句,完成该功能。
18、设T和P是两个给定的串,在T中寻找等于P的子串的过程称为 ,又称P为 。
三、判断题
19、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。( )
20、直接访问文件也能顺序访问,只是一般效率不高。( )
21、一个广义表可以为其他广义表所共享。( )
22、KMP算法的特点是在模式匹配时指示主串的指针不会变小。( )
23、一个树形的叶结点,在前序遍历和后序遍历下,皆以相同的相对位置出现。( )
24、深度为k的二叉树中结点总数小于等于2k-1。( )
25、为了很方便地插入和删除数据,可以使用双向链表存放数据。 ( )
26、线性表采用链表存储时,结点和结点内部的存储空间可以是不连续的。( )
27、对大小均为n的有序表和无序表分别进行顺序查找,在等概率查找的情况下,对于查找成功,它们的平均查找长度是相同的,而对于查找失败,它们的平均查找长度是不同的。( )
28、有向图中顶点V度等于其邻接矩阵中第V行中的1的个数。( )
四、简答题
29、阅读下面的算法,说明算法实现的功能。
30、三维数组A[1..10,-2..6,2..8]的每个元素的长度为4个字节,试问该数组要占多少个字节的存储空间?如果数组元素以行优先的顺序存储,设第一个元素的首地址是100,试求元素A[5,0,7]的存储首地址。
31、设有6个有序表A、B、C、D、E、F,分别含有10、35、40、50、60 和200个数据元素,各表中元素按升序排列。要求通过5次两两合并,将 6个表最终合并成1个升序表,并在最坏情况下比较的总次数达到最小。请回答下列问题。
(1) 给出完整的合并过程,并求出最坏情况下比较的总次数。
(2) 根据你的合并过程,描述n(n≥2)个不等长升序表的合并策略,并说明理由。
五、算法设计题
32、在一个循环链队中只有尾指针(记为rear,结点结构为数据域data,指针域next),请给出这种队列的入队和出队操作的实现过程。
33、编写递归算法,从大到小输出给定二叉排序树中所有关踺字不小于x的数据元素。要求你的算法的时间复杂度为O(log2(x+m)),其中,2为排序树中所含结点数,m为输出的关键字个数。
34、给定n×m矩阵A[a..b,c..d],并设
A[i,j]≤A[i+1,j](a≤i≤b-1,c≤j≤d)。设计一算法判定x的值是否在A 中,要求时间复杂度为O(m+n)。
35、设排序二叉树中结点的结构为下述三个域构成: Data:给出结点数据的值;left:给出本结点的左儿子结点的地址; right:给出本结点的右儿子结点的地址。设data域为正整数,该二叉树根结点地址为T。现给出一个正整数x。请编写非递归程序,实现将data 域之值小于等于x的结点全部删除掉。
免费领取资料
独家考研团队题型预测,考研英语近20年真题解析+高分范文,政治复习资料全集、最新政治热点,数学常考公式以及专业课等资料
方法1:扫码添辅导老师微信
微信号:xhdkaoyan
方法2:填写个人信息老师亲自联系您
-
考研英语历年真题
获取扫码添加老师微信
请注明:姓名-公司-职位
以便审核进群资格,未注明
则拒绝 -
考研数学历年真题
获取扫码添加老师微信
请注明:姓名-公司-职位
以便审核进群资格,未注明
则拒绝 -
考研政治各科历年真题
获取扫码添加老师微信
请注明:姓名-公司-职位
以便审核进群资格,未注明
则拒绝 -
专业课历年真题
获取扫码添加老师微信
请注明:姓名-公司-职位
以便审核进群资格,未注明
则拒绝 -
课程录播(视频)
获取扫码添加老师微信
请注明:姓名-公司-职位
以便审核进群资格,未注明
则拒绝