2022年华南理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年华南理工大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、n个结点的完全有向图含有边的数目（）。A.n*nB.n(n+1)C.n/2D.n*(n-1)2、用数组r存储静态链表，结点的next域指向后继，工作指针j指向链中结点，使j沿链移动的操作为（）。A.j=r[j].nextB.j=j+lC.j=j->nextD.j=r[j]->next3、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。A.单链表B.双向链表C.单循环链表D.顺序表4、有六个元素6，5，4，3，2，1顺序入栈，下列不是合法的出栈序列的是（）。A.543612B.453126C.346521D.2341565、动态存储管理系统中，通常可有（）种不同的分配策略。A.1B.2C.3D.46、已知关键字序列5，8，12，19，28，20，15，22是小根堆（最小堆），插入关键字3，调整后的小根堆是（）。A．3，5，12，8，28，20，15，22，19B．3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D．3，12，5，8，28，20，15，22，197、下列关于无向连通图特性的叙述中，正确的是（）。Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1A．只有ⅠB．只有ⅡC．Ⅰ和ⅡD．Ⅰ和Ⅲ8、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。A.CBEFDAB.FEDCBAC.CBEDFAD.不定9、一个具有1025个结点的二叉树的高h为（）。A.11B.10C.11至1025之间D.10至1024之间10、一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为（）。A.（38，40，46，56，79，84）B.（40，38，46，79，56，84）C.（40，38，46，56，79，84）D.（40，38，46，84，56，79）二、填空题11、在哈希函数H（key）=key%p中，p值最好取______。12、在有n个顶点的有向图中，每个顶点的度最大可达______。13、已知有序表为（12，18，24，35，47，50，62，83，90，115，134）当用二分法查找90时，需______次查找成功，查找47时______成功，查找100时，需______次才能确定不成功。14、以下是用类C语言写出的算法，该算法将以二叉链表存储的二叉树中的叶结点按从左到右的顺序链成一个带头结点的双向循环链表，链接时，结点的Lchild域作为前链域，指向结点的直接前驱，结点的Rchild域作为后链域，指向结点的直接后继。算法中，使用一个顺序栈stack，栈顶指针为top，p，t为辅助指针，head为双向循环链表的头指针。试填充算法中的空格，使算法完整。15、一个算法具有5个特性：______、______、______、有零个或多个输入、有一个或多个输出。16、设有一个空栈，栈顶指针为1000H（十六进制），现有输入序列为l，2，3，4，5，经过PUSH，PUSH，POP，PUSH，POP，PUSH，PUSH之后，输出序列是______，而栈顶指针值是______。设栈为顺序栈，每个元素占4个字节。17、当两个栈共享一存储区时，栈利用一维数组stack（1，n）表示，两栈顶指针为top[1]与top[2]，则当栈1空时，top[1]为______，栈2空时，top[2]为______，栈满时为______。18、已知一循环队列的存储空间为[m..n]，其中n>m，队头和队尾指针分别为front和rear，则此循环队列判满的条件是______。三、判断题19、倒排序文件的优点是维护简单。（）20、直接访问文件也能顺序访问，只是一般效率不高。（）21、设模式串的长度为m，目标串的长度为n，当n≈m且处理只匹配一次的模式时，朴素的匹配（即子串定位函数）算法所花的时间代价可能会更为节省。（）22、二维以上的数组其实是一种特殊的广义表。（）23、树形结构中元素之间存在一对多的关系。（）24、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（）25、数据的逻辑结构是指数据的各数据项之间的逻辑关系。（）26、算法的优劣与算法描述语言无关，但与所用计算机有关。（）27、在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（）28、B-树中所有结点的平衡因子都为零。（）四、简答题29、请写出应填入下列叙述中（）内的正确答案。排序有各种方法，如插入排序、快速排序、堆排序等。设一数组中原有数据如下：15，13，20，18，12，60。下面是一组用不同排序方法进行一遍排序后的结果。（）排序的结果为：12，13，15，18，20，60（）排序的结果为：13，15，18，12，20，60（）排序的结果为：13，15，20，18，12，60（）排序的结果为：12，13，20，18，15，6030、s是字符数组，s[0]中存放的是该字符串的有效长度，假设s[1..7]中字符串的内容为"abcabaa"，说明下列程序的功能及执行结果。31、已知图的邻接矩阵为：当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出：(1)以顶点V1为出发点的唯一的深度优先遍历序列。当用邻接表作为图的存储结构，且邻接点都按序号从大到小排列时，试写出：(1)以顶点V1为出发点的唯一的深度优先遍历序列。(2)以顶点V1为出发点的唯一的广度优先遍历序列。(3)该图唯一的拓扑有序序列。五、算法设计题32、请用流程图或高级语言表示算法。已知有向图有n个顶点，请写算法，根据用户输入的数对建立该有向图的邻接表。即接受用户输入的<vi，vj>(以其中之一为0标志结束)，对于每条这样的边，申请一个结点，并插入到的单链表中，如此反复，直到将图中所有边处理完毕。提示：先产生邻接表的n个头结点(其结点数值域从1到n)。33、设计算法将一棵以二叉链表存储的二叉树按顺序方式存储到一维数组中（注：按层从上到下，由左到右）。34、设有顺序放置的n个桶，每个桶中装有一粒砾石，每粒砾石的颜色是红、白、蓝之一。要求重新安排这些砾石，使得所有红色砾石在前，所有白色砾石居中，所有蓝色砾石居后。重新安排时，对每粒砾石的颜色只能察看一次，并且只允许交换操作来调整砾石的位置。35、写出按后序序列遍历中序线索树的算法。

参考答案一、选择题1、【答案】D2、【答案】A3、【答案】D4、【答案】C5、【答案】C6、【答案】A7、【答案】A8、【答案】A9、【答案】C10、【答案】C二、填空题11、【答案】小于等于表长的最大素数或不包含小于20的质因子的合数12、【答案】2(n-1)13、【答案】2；4；3【解析】二分法查找元素次数列表查找100是找到115就停止了。14、【答案】p->Rchild=t；t->Lchild=p；p=t；t->Rchild!=null；t->Rchild；t->Lchild!=null；t->Lchild；p->Rchild=head；head->Lchild=p15、【答案】有穷性；确定性；可行性16、【答案】23；100CH17、【答案】0；n+1；top[1]+1=top[2]18、【答案】（rear+1）%（n-m+1）==front三、判断题19、【答案】×20、【答案】×21、【答案】√22、【答案】√23、【答案】√24、【答案】√25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、简答题29、答：①快速排序②起泡排序③直接插入排序④堆排序30、答：本程序的功