2023年兴义民族师范学院计算机应用技术专业《数据结构与算法》科目期末试卷A（有答案）.docxVIP

2023年兴义民族师范学院计算机应用技术专业《数据结构与算法》科目期末试卷A（有答案） 一、选择题 1、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（　　）。 A.13 B.33 C.18 D.40 2、下述文件中适合于磁带存储的是（　　）。 A.顺序文件 B.索引文件 C.哈希文件 D.多关键字文件 3、算法的计算量的大小称为计算的（　　）。 A.效率 B.复杂性 C.现实性 D.难度 4、最大容量为n的循环队列，队尾指针是rear，队头：front，则队空的条件是（　　）。 A.（rear+1）MOD n=front B.rear=front C.rear+1=front D.（rear-1）MOD n=front 5、已知串S=aaab，其next数组值为（　　）。 A.0123 B.1123 C.1231 D.1211 6、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（　　）。 A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝2 7、下列叙述中，不符合m阶B树定义要求的是（　　）。 A．根结点最多有m棵子树 B．所有叶结点都在同一层上 C．各结点内关键字均升序或降序排列 D．叶结点之间通过指针链接 8、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（　　）。 A.二叉排序树 B.哈夫曼树 C.AVL树 D.堆 9、一棵非空的二叉树的前序序列和后序序列正好相反，则该二叉树一定满足（　　）。 A.其中任意一个结点均无左孩子 B.其中任意一个结点均无右孩子 C.其中只有一个叶结点 D.其中度为2的结点最多为一个 10、就平均性能而言，目前最好的内排序方法是（　　）排序法。 A.起泡 B.希尔插入 C.交换 D.快速 二、填空题 11、以下程序的功能是实现带附加头结点的单链表数据结点逆序连接，请填空完善之。 12、在有n个顶点的有向图中，每个顶点的度最大可达______。 13、建立索引文件的目的是______。 14、在一棵m阶B-树中，若在某结点中插入一个新关键字而引起该结点分裂，则此结点中原有的关键字的个数是______；若在某结点中删除一个关键字而导致结点合并，则该结点中原有的关键字的个数是______。 15、对于一个具有n个结点的单链表，在已知的结点半p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为______。 16、设有N个结点的完全二叉树顺序存放在向量A[1：N]中，其下标值最大的分支结点为______。 17、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。 18、已知U=‘xyxyxyxxyxy’；t=‘xxy’；ASSIGN（S，U）；ASSIGN（V， SUBSTR（S，INDEX（S，t），LEN（t）+1））； ASSIGN（m，’ww’），求REPLACE（S，V，m）=______。 三、判断题 19、倒排序文件的优点是维护简单。（　　） 20、对磁带机而言，ISAM是一种方便的文件组织方法（　　） 21、串是一种数据对象和操作都特殊的线性表。（　　） 22、二维以上的数组其实是一种特殊的广义表。（　　） 23、任何二叉树的后序线索树进行后序遍历时都必须用栈。（　　） 24、哈夫曼树度为1的结点数等于度为2和0的结点数之差。（　　） 25、数据的逻辑结构是指数据的各数据项之间的逻辑关系。（　　） 26、在任何情况下，归并排序都比简单插入排序快。（　　） 27、在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。 （　　） 28、采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（　　） 四、简答题 29、设目标为t=‘abcaabbabcabaacbacba’，模式为P=‘abcabaa’ （1）计算模式p的nextval函数值。 （2）不写出算法，只画出利用KMP算法进行模式匹配时每一趟的匹配过程。 30、阅读下面的算法，说明算法实现的功能。 31、已知有6个顶点（顶点编号为0～5）的有向带权图G，其邻接矩阵A 为上三角矩阵，按