精品工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷精品.pdf

2022年沈阳工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、n个结点的完全有向图含有边的数目（）。A.n*nB.n(n+1)C.n/2D.n*(n-1)2、下列说法不正确的是（）。A.图的遍历是从给定的源点出发每个顶点仅被访问一次B.遍历的基本方法有两种：深度遍历和广度遍历C.图的深度遍历不适用于有向图D.图的深度遍历是一个递归过程3、以下数据结构中，（）是非线性数据结构。A.树字符串B.队栈C.D.4、已知串S='aaab'，其next数组值为（）。A.0123B.1123C.1231D.12115、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l6、下列关于无向连通图特性的叙述中，正确的是（）。Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1A．只有Ⅰ．只有BⅡ．ⅠC和Ⅱ．ⅠD和Ⅲ7、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。A．i＝1，j＝0．Bi＝5，j＝0．i＝C5，j＝2．i＝D6，j＝28、有n（n>0）个分支结点的满二叉树的深度是（）。A.n2-1B.log（n+1）+12C.log（n+1）2D.log（n-l）29、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。A.二叉排序树哈夫曼树B.树堆C.AVLD.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、用一维数组存储二叉树时，总是以前序遍历顺序存储结点。（）24、对于有n个结点的二叉树，其高度为log2n。（）25、在外部排序过程中，对长度为n的初始序列进行“置换-选择”排序时，可以得到的最大初始有序段的长度不超过n/2。（）26、归并排序辅助存储为O（1）。（）27、连通图上各边权值均不相同，则该图的最小生成树是唯一的。（）28、采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的