2023年香港浸会大学联合国际学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）.docxVIP

2023年香港浸会大学联合国际学院计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案） 一、选择题 1、已知广义表LS=（（a，b，c），（d，e，f）），用head和tail数取出LS中原子e的运算是（　　）。 A.head（tail（LS）） B.tail（head（LS）） C.head（tail（head（tail（LS）））） D.head（tail（tail（head（LS）））） 2、将两个各有N个元素的有序表归并成一个有序表，其最少的比较次数是（　　）。 A.N B.2N-1 C.2N D.N-1 3、以下与数据的存储结构无关的术语是（　　）。 A.循环队列 B.链表 C.哈希表 D.栈 4、向一个栈顶指针为h的带头结点的链栈中插入指针s所指的结点时，应执行（　　）。 A.h-next=s B.s-next=h C.s-next=h;h-next=s D.s-next=h-next;h-next=s 5、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（　　）。 A.543612 B.453126 C.346521 D.234156 6、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。初始时为空，下列判断队空和队满的条件中，正确的是（　　）。 A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod M B．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1） C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod M D．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1） 7、下列关于无向连通图特性的叙述中，正确的是（　　）。 Ⅰ．所有的顶点的度之和为偶数 Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ 8、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（　　）。 A.CBEFDA B.FEDCBA C.CBEDFA D.不定 9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（　　）。 A.其中任意一个结点均无左孩子 B.其中任意一个结点均无右孩子 C.其中只有一个叶结点 D.其中度为2的结点最多为一个 10、若查找每个记录的概率均等，则在具有n个记录的连续顺序文件中采用顺序查找法查找一个记录，其平均查找长度ASL为（　　）。 A.(n-1)/2 B.n/2 C.(n+1)/2 D.n 二、填空题 11、设m、n均为自然数，m可表示为一些不超过n的自然数之和，f（m， n）为这种表示方式的数目。例f（5，3）=5，有5种表示方式：3+2， 3+1+1，2+2+1，2+1+1+1，1+1+1+1+1。 ①以下是该函数的程序段，请将未完成的部分填入，使之完整。 ②执行程序，f（6，4）=______。 12、顺序查找n个元素的顺序表，若查找成功，则比较关键字的次数最多为______次；当使用监视哨时，若查找失败，则比较关键字的次数为______。 13、文件可按其记录的类型不同而分成两类，即______和______文件。 14、n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。 注：(1)图的顶点号从0开始计。 (2)indegree是有n个分量的一维数组，放顶点的入度， (3)函数crein用于计算顶点入度。 (4)有三个函数push(data)，pop()，check()其含义为数据data入栈，出栈和测试栈是否空(不空返回l，否则0)。 15、在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是______；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是______。 16、设数组A[0..8，1..10]，数组中任一元素A[i，j]均占内存48个二进制位，从首地址2000开始连续存放在主内存里，主内存字长为16位，那么 （1） 存放该数组至少需要的单元数是______。 （2） 存放数组的第8列的所有元素至少需要的单元数______。 （3） 数组按列存储时，元素A[5，8]的起始地址是______。 17、每一棵树都能唯一地转换为它所对应的二叉树。若已知一