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

2022年沈阳工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案） 一、选择题 1、n个结点的完全有向图含有边的数目（　　）。 A.n*n B.n(n+1) C.n/2 D.n*(n-1) 2、下列说法不正确的是（　　）。 A.图的遍历是从给定的源点出发每个顶点仅被访问一次 B.遍历的基本方法有两种：深度遍历和广度遍历 C.图的深度遍历不适用于有向图 D.图的深度遍历是一个递归过程 3、以下数据结构中，（　　）是非线性数据结构。 A.树 B.字符串 C.队 D.栈 4、已知串S=aaab，其next数组值为（　　）。 A.0123 B.1123 C.1231 D.1211 5、在下列表述中，正确的是（　　） A.含有一个或多个空格字符的串称为空格串 B.对n（n0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树 C.选择排序算法是不稳定的 D.平衡二叉树的左右子树的结点数之差的绝对值不超过l 6、下列关于无向连通图特性的叙述中，正确的是（　　）。 Ⅰ．所有的顶点的度之和为偶数 Ⅱ．边数大于顶点个数减1 Ⅲ．至少有一个顶点的度为1 A．只有Ⅰ B．只有Ⅱ C．Ⅰ和Ⅱ D．Ⅰ和Ⅲ 7、已知字符串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 8、有n（n0）个分支结点的满二叉树的深度是（　　）。 A.n2-1 B.log2（n+1）+1 C.log2（n+1） D.log2（n-l） 9、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（　　）。 A.二叉排序树 B.哈夫曼树 C.AVL树 D.堆 10、对关键码序列28，16，32，12，60，2，5，72快速排序，从小到大一次划分结果为（　　）。 A.（2，5，12，16）26（60，32，72） B.（5，16，2，12）28（60，32，72） C.（2，16，12，5）28（60，32，72） D.（5，16，2，12）28（32，60，72） 二、填空题 11、对单链表中元素按插入方法排序的C语言描述算法如下，其中L为链表头结点指针。请填充算法中标出的空白处，完成其功能。 12、若用n表示图中顶点数目，则有______条边的无向图成为完全图。 13、n个顶点的有向图用邻接矩阵array表示，下面是其拓扑排序算法，试补充完整。 注：(1)图的顶点号从0开始计。 (2)indegree是有n个分量的一维数组，放顶点的入度， (3)函数crein用于计算顶点入度。 (4)有三个函数push(data)，pop()，check()其含义为数据data入栈，出栈和测试栈是否空(不空返回l，否则0)。 14、检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按______检索。也可以按______检索；按______检索又可以有 ______检索和______检索。 15、设T是一棵结点值为整数的二叉排序树，A是一个任意给定的整数。在下面的算法中，free_tree（T）在对二叉排序树丁进行后序遍历时释放二又排序树T的所有结点；delete_subtree（T，A），首先在二叉排序树 T中查找值为A的结点，根据查找情况分别进行如下处理：（1）若找不到值为A的结点，则返回根结点的地址（2）若找到值为A的结点，则删除以此结点为根的子树，并释放此子树中的所有结点，若值为A的结点是查找树的根结点，删除后变成空的二叉树，则返null；否则返回根结点的地址。 16、当两个栈共享一存储区时，栈利用一维数组stack（1，n）表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为______，栈2空时， top[2]为______，栈满时为______。 17、模式串P=‘abaabcac’的next函数值序列为______。 18、设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储： a11=1），则a85的地址为______。 三、判断题 19、倒排序文件的优点是维护简单。（　　） 20、哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。（　　） 21、广义表（（（a，b，c），d，e，f））的长度是4。（　　） 22、循环队列也存在空间溢出问题。（　　） 23、用一维数组存储二叉树时，总是以前序遍历顺序存储结