2022年广东技术师范大学计算机科学与技术专业《数据结构与算法》科目期末试卷A(有答案)

2022年广东技术师范大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、将线性表的数据元素进行扩充，允许带结构的线性表是（）。A.串B.树C.广义表D.栈2、有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表示该矩阵时，所需的字节数是（）。A.60B.66C.18000D.333、若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值，为节省时间应采用的存储方式（）。A.单链表B.双向链表C.单循环链表D.顺序表4、已知有向图G=(V，E)，其中V={V1，V2，V3，V4，V5，V6，V7}，E=｛<V1，V2>，<V1，V3>，<V1，V4>，<V2，V5>，<V3，V5>，<V3，V6>，<V4，V6>，<V5，V7>，<V6，V7>｝，G的拓扑序列是（）。A.V1，V3，V4，V6，V2，V5，V7B.V1，V3，V2，V6，V4，V5，V7C.V1，V3，V5，V2，V6，V7D.V1，V2，V5，V3，V4，V6，V75、循环队列A[0..m-1]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是（）。A.（rear-front+m）%mB.rear-front+1C.rear-front-1D.rear-front6、下列关于无向连通图特性的叙述中，正确的是（）。Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1A．只有ⅠB．只有ⅡC．Ⅰ和ⅡD．Ⅰ和Ⅲ7、下列选项中，不能构成折半查找中关键字比较序列的是（）。A．500，200，450，180B．500，450，200，180C．180，500，200，450D．180，200，500，4508、下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序（）。A.二叉排序树B.哈夫曼树C.AVL树D.堆9、一个具有1025个结点的二叉树的高h为（）。A.11B.10C.11至1025之间D.10至1024之间10、在文件“局部有序”或文件长度较小的情况下，最佳内部排序的方法是（）。A.直接插入排序B.起泡排序C.简单选择排序D.快速排序二、填空题11、设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需______趟，写出第一趟结束后，数组中数据的排列次序______。12、下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：13、按LSD进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用______的排序方法。14、对于一个具有n个结点的单链表，在已知的结点半p后插入一个新结点的时间复杂度为______，在给定值为x的结点后插入一个新结点的时间复杂度为______。15、设单链表的结点结构为（data，next），next为指针域，已知指针px指向单链表中data为x的结点，指针py指向data为y的新结点，若将结点y插入结点x之后，则需要执行以下语句：______16、设正文串长度为n，模式串长度为m，则串匹配的KMP算法的时间复杂度为______。17、设有一个10阶对称矩阵A采用压缩存储方式（以行为主序存储：a11=1），则a85的地址为______。18、已知一循环队列的存储空间为[m..n]，其中n>m，队头和队尾指针分别为front和rear，则此循环队列判满的条件是______。三、判断题19、对磁带机而言，ISAM是一种方便的文件组织方法（）20、文件系统采用索引结构是为了节省存储空间。（）21、栈的输入序列是1，2，…，n，输出序列是a1，a2，…，an若ai=n（1≤i≤n）则有：ai>ai+1>…>an。（）22、广义表（（（a，b，c），d，e，f））的长度是4。（）23、深度为k的二叉树中结点总数小于等于2k-1。（）24、哈夫曼树度为1的结点数等于度为2和0的结点数之差。（）25、排序的稳定性是指排序算法中的比较次数保持不变，且算法能够终止。（）26、归并排序辅助存储为O（1）。（）27、当改变网上某一关键路径上任一关键活动后，必将产生不同的关键路径。（）28、若一个有向图的邻接矩阵对角线以下元素均为零，则该图的拓扑有序序列必定存在。（）四、简答题29、s是字符数组，s[0]中存放的是该字符串的有效长度，假设s[1..7]中字符串的内容为"abcabaa"，说明下列程序的功能及执行结果。30、对于具有n个叶结点且所有非叶结点都有左、右孩子的二叉树。(1)试问这种二叉树的结点总数是多少?(2)试证明2-（li-1）=1。其中：li表示第i个叶结点所在的层号（设根结点所在层号为1）。31、对下面的关键字集{30，15，21，40，25，26，36，37}若查找表的装填因子为0.8，采用线性探测再哈希方法解决冲突，做：（1）设计哈希函数；（2）画出哈希表；（3）计算查找成功和查找失败的平均查找长度；（4）写出将哈希表中某个数据元素删除的算法。五、算法设计题32、若x和y是两个采用顺序结构存储的串，编写一个比较两个串是否相等的函数。33、请编写完整的程序。如果矩阵A中存在这样的一个元素A[i，j]满足条件：A[i，j]是第i行中值最小的元素，且又是第j列中值最大的元素，则称之为该矩阵的一个马鞍点。请编程计算出m*n的矩阵A的所有马鞍点。34、试设计一个C语言算法（或C语言程序）：用单链表做存储结构，以回车符为结束标志，输入一个任意长度的字符串，然后判断该字符串是否为“回文”（正向读和反向读时，串值相同的字符串称为“回文”），输出信息“Yes”或“NO”；最后删除字符串并释放全部空间。例如：若输入“ABCD12321DCBA”是回文，则输出“Yes”。若输入“ABCD123DCBA”，不是回文，则输出“NO”。要求：定义相关数据类型，不得使用数组（顺序表）做字符串的存储结构和辅助存储空间。假定字符串的长度为n，试分析上述算法的时间复杂度。35、二路插入排序是将待排关键字序列r[1..n]中关键字分二路分别按序插入到辅助向量d[1..n]前半部和后半部（注：向量d可视为循环表），其原则为，先将r[1]赋给d[1]，再从r[2]记录开始分二路插入。编写实现2-路插入排序算法。

参考答案一、选择题1、【答案】C2、【答案】B3、【答案】D4、【答案】A5、【答案】A6、【答案】A7、【答案】A8、【答案】D9、【答案】C10、【答案】A二、填空题11、【答案】3；（10，7，-9，0，47，23，1，8，98，36）@12、【答案】a+1；n%10【解析】通过递归算法，首先找到最高位的值，将其放到str对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。13、【答案】稳定14、【答案】O（1）；O（n）15、【答案】py->next=px->next；px->next=py16、【答案】O（m+n）17、【答案】3318、【答案】（rear+1）%（n-m+1）==front三、判断题19、【答案】×20、【答案】×21、【答案】×22、【答案】×23、【答案】√24、【答案】×25、【答案】×26、【答案】×27、【答案】×28、【答案】√四、简答题29、答：本程序的功能是求字符串的nextval函数，程序执行结果是0110132。30、答：（1）根据二叉树中度为2的结点个数等于叶结点个数减1的性质，故具有n个叶结点且非叶子结点均有左子树的二叉树的结点数是2n-1。（2）证明：当i=1时，2-（1-1）=20=1，公式成立。设当i=n-1时公式成立，证明当i=n时公式仍成立。设某叶结点的层号为t，当将该结点变为内部结点，从而再增加两个叶结点时，这两个叶结点的层号都是t+1，对于公式的变化，是减少了一个原来的叶结点，增加了两个新叶结点，反映到公式中，因为2-（t-1）=2-（t+1-1）+2-（t+1-1），所以结果不变，这就证明当i=n时公式仍成立。证毕。31、答：（1）由于装填因子为0.8，关键字有8个，所以表长为8/0.8