- 1、本文档共12页,可阅读全部内容。
- 2、原创力文档(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
2022年中央民族大学计算机科学与技术专业《数据结构与算法》科目
期末试卷A(有答案)
一、选择题
1、有一个100*90的稀疏矩阵,非0元素有10个,设每个整型数占2字节,则用三元组
表示该矩阵时,所需的字节数是()。
A.60B.66C.18000D.33
2、下列排序算法中,占用辅助空间最多的是()。
A.归并排序B.快速排序C.希尔排序D.堆排序
3、静态链表中指针表示的是()。
A.下一元素的地址
B.内存储器的地址
C.下一元素在数组中的位置
D.左链或右链指向的元素的地址
4、已知有向图G=(V,E),其中V={V1,V2,V3,V4,V5,V6,V7},E={V1,V2,
V1,V3,V1,V4,V2,V5,V3,V5,V3,V6,V4,V6,V5,V7,
V6,V7},G的拓扑序列是()。
A.V1,V3,V4,V6,V2,V5,V7B.V1,V3,V2,V6,V4,V5,V7
C.V1,V3,V5,V2,V6,V7D.V1,V2,V5,V3,V4,V6,V7
5、用不带头结点的单链表存储队列,其队头指针指向队头结点,队尾指针指向队尾结点,
则在进行出队操作时()。
A.仅修改队头指针
B.仅修改队尾指针
C.队头、队尾指针都可能要修改
D.队头、队尾指针都要修改
6、已知字符串S为“abaabaabacacaabaabcc”,模式串t为“abaabc”,采用KMP算法进行
匹配,第一次出现失配“”(s!=t)时,i=j=5,则下次开始匹配时,i和j的值分别
()。
A.i=1,j=0B.i=5,j=0C.i=5,j=2D.i=6,j=2
7、下列叙述中,不符合m阶B树定义要求的是()。
A.根结点最多有m棵子树B.所有叶结点都在同一层上
C.各结点内关键字均升序或降序排列D.叶结点之间通过指针链接
8、有关二叉树下列说法正确的是()。
A.二叉树的度为2
B.一棵二叉树的度可以小于2
C.二叉树中至少有一个结点的度为2
D.二叉树中任何一个结点的度都为2
9、每个结点的度或者为0或者为2的二叉树称为正则二叉树。n个结点的正则二叉树中
有()个叶子。
A.lognB.(n-1)/2C.logn+1D.(n+1)/2
22
10、分别以下列序列构造二叉排序树,与用其他三个序列所构造的结果不同的是()。
A.(100,80,90,60,120,110,130)
B.(100,120,110,130,80,60,90)
C.(100,60,80,90,20,110,130)
D.(100,80,60,90,120,130,110)
二、填空题
11、阅读下列程序,指出其功能,并写出空格处应填上的语句。
12、分别采用堆排序,快速排序,起泡排序和归并排序,对初态为有序的表,则最省时间
的是______算法,最费时间的是______算法。
13、线性表L=(a1,a2,…,an)用数组表示,假定删除表中任一元素的概率相同,则
删除一个元素平均需要移动元素的个数是______。
14、n个顶点的有向图用邻接矩阵array表示,下面是其拓扑排序算法,试补充完整。
注:(1)图的顶点号从0开始计。
(2)indegree是有n个分量的一维数组,放顶点的入度,
(3)函数crein用于计算顶点入度。
(4)有三个函数push(data),pop(),check()其含义为数据data入栈,出栈和测试栈是否空
(不空返回l,否则0)。
15、一个算法具有5个特性:______、______、______、有零个或多个输入、有一个或多个输
出。
16、设广义表L=((),()),则head
文档评论(0)