2022年长治学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）.docxVIP

2022年长治学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案） 一、选择题 1、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（　　）。 A.j=r[j].next B.j=j+l C.j=j-next D.j=r[j]-next 2、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（　　）。 A.60 B.66 C.18000 D.33 3、静态链表中指针表示的是（　　）。 A.下一元素的地址 B.内存储器的地址 C.下一元素在数组中的位置 D.左链或右链指向的元素的地址 4、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（　　）。 A.（rear-front+m）%m B.rear-front+1 C.rear-front-1 D.rear-front 5、下列关于AOE网的叙述中，不正确的是（　　）。 A.关键活动不按期完成就会影响整个工程的完成时间 B.任何一个关键活动提前完成，那么整个工程将会提前完成 C.所有的关键活动提前完成，那么整个工程将会提前完成 D.某些关键活动若提前完成，那么整个工程将会提前完成 6、下列关于无向连通图特性的叙述中，正确的是（　　）。 Ⅰ．所有的顶点的度之和为偶数 Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ 7、下列叙述中，不符合m阶B树定义要求的是（　　）。 A．根结点最多有m棵子树 B．所有叶结点都在同一层上 C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接 8、一棵哈夫曼树共有215个结点，对其进行哈夫曼编码，共能得到（　　）个不同的码字。 A.107 B.108 C.214 D.215 9、一个具有1025个结点的二叉树的高h为（　　）。 A.11 B.10 C.11至1025之间 D.10至1024之间 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、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为______次；当使用监视哨时，若查找失败，则比较关键字的次数为______。 12、如果按关键码值递增的顺序依次将关键码值插入到二叉排序树中，则对这样的二叉排序树检索时，平均比较次数为______。 13、n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。 注：(1)图的顶点号从0开始计。 (2)indegree是有n个分量的一维数组，放顶点的入度， (3)函数crein用于计算顶点入度。 (4)有三个函数push(data)，pop()，check()其含义为数据data入栈，出栈和测试栈是否空(不空返回l，否则0)。 14、在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是______；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是______。 15、一个算法具有5个特性： ______、______、______、有零个或多个输入、有一个或多个输出。 16、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。 17、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。 18、设有N个结点的完全二叉树顺序存放在向量A[1：N]中，其下标值最大的分支结点为______。 三、判断题 19、对磁带机而言，ISAM是一种方便的文件组织方法（　　） 20、倒排文件是对次关键字建立索引。（　　） 21、KMP算法的特点是在模式匹配时指示主串的指针不会变小。（　　） 22、栈的输入序列是1，2，…，n，输出序列是a1，a2，…，an若 ai=n（1≤i≤n）则有：aiai+1…an。（　　） 23、中序遍历一棵二叉排序树的结点就可得到排好序的结点序列。（　　） 24、哈夫曼树度为1的结点数等于度为2和0的结点数之差。（　　） 25、为提高排序速度，进行外排序时，必须选用最快的内排序算法。（　　） 26、排序的稳定性是指排序算法中的比较次数保持不变，且算