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

2022年内蒙古师范大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、n个结点的完全有向图含有边的数目（）。A.n*nB.n(n+1)C.n/2D.n*(n-1)2、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。A.13B.33C.18D.403、静态链表中指针表示的是（）。A.下一元素的地址B.内存储器的地址C.下一元素在数组中的位置D.左链或右链指向的元素的地址4、用不带头结点的单链表存储队列，其队头指针指向队头结点，队尾指针指向队尾结点，则在进行出队操作时（）。A.仅修改队头指针B.仅修改队尾指针C.队头、队尾指针都可能要修改D.队头、队尾指针都要修改5、在用邻接表表示图时，拓扑排序算法时间复杂度为（）。A.O(n)B.O(n+e)C.O(n*n)D.O(n*n*n)6、下列关于无向连通图特性的叙述中，正确的是（）。Ⅰ．所有的顶点的度之和为偶数Ⅱ．边数大于顶点个数减1Ⅲ．至少有一个顶点的度为1A．只有ⅠB．只有ⅡC．Ⅰ和ⅡD．Ⅰ和Ⅲ7、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。A．i＝1，j＝0B．i＝5，j＝0C．i＝5，j＝2D．i＝6，j＝28、有关二叉树下列说法正确的是（）。A.二叉树的度为2B.一棵二叉树的度可以小于2C.二叉树中至少有一个结点的度为2D.二叉树中任何一个结点的度都为29、设X是树T中的一个非根结点，B是T所对应的二叉树。在B中，X是其双亲的右孩子，下列结论正确的是（）。A.在树T中，X是其双亲的第一个孩子B.在树T中，X一定无右兄弟C.在树T中，X一定是叶结点D.在树T中，X一定有左兄弟10、就平均性能而言，目前最好的内排序方法是（）排序法。A.起泡B.希尔插入C.交换D.快速二、填空题11、下面程序的功能是用递归算法将一个整数按逆序存放到一个字符数组中。如123存放成321。请填空：12、设用希尔排序对数组{98，36，-9，0，47，23，1，8，10，7}进行排序，给出的步长（也称增量序列）依次是4，2，1则排序需______趟，写出第一趟结束后，数组中数据的排列次序______。13、按LSD进行关键字排序，除最次位关键字之外，对每个关键字进行排序时，只能用______的排序方法。14、在双向循环链表中，向p所指的结点之后插入指针f所指的结点，其操作是______、______、______、______。15、检索是为了在文件中寻找满足一定条件的记录而设置的操作。检索可以按______检索。也可以按______检索；按______检索又可以有______检索和______检索。16、在顺序存储的二叉树中，编号为i和j的两个结点处在同一层的条件是______。17、阅读下列程序说明和程序，填充程序中的______。【程序说明】本程序完成将二叉树中左、右孩子交换的操作。交换的结果如下所示（编者略）。本程序采用非递归的方法，设立一个堆栈stack存放还没有转换过的结点，它的栈顶指针为tp。交换左、右子树的算法为：（1）把根结点放入堆栈。（2）当堆栈不空时，取出栈顶元素，交换它的左、右子树，并把它的左、右子树分别入栈。（3）重复（2）直到堆栈为空时为止。18、模式串P=‘abaabcac’的next函数值序列为______。三、判断题19、倒排文件的目的是为了多关键字查找。（）20、倒排文件是对次关键字建立索引。（）21、设栈采用顺序存储结构。若已有i-1个元素入栈，则将第i个元素入栈时，入栈算法的时间复杂性为O（i）。（）22、稀疏矩阵压缩存储后，必会失去随机存取功能。（）23、一个树形的叶结点，在前序遍历和后序遍历下，皆以相同的相对位置出现。（）24、哈夫曼树度为1的结点数等于度为2和0的结点数之差。（）25、算法的优劣与算法描述语言无关，但与所用计算机有关。（）26、数据的逻辑结构是指数据的各数据项之间的逻辑关系。（）27、采用线性探测法处理散列时的冲突，当从哈希表删除一个记录时，不应将这个记录的所在位置置空，因为这会影响以后的查找。（）28、在索引顺序表中，实现分块查找，在等概率查找情况下，其平均查找长度不仅与表中元素个数有关，而且与每块中元素个数有关。（）四、简答题29、给出一组关键字：29，18，25，47，58，12，51，10，分别写出按下列各种排序方法进行排序时的变化过程：（1） 归并排序，每归并一次书写一个次序。（2） 快速排序，每划分一次书写一个次序。（3） 堆排序，先建成一个堆，然后每从堆顶取下一个元素后，将堆调整一次。30、三维数组A[1..10，-2..6，2..8]的每个元素的长度为4个字节，试问该数组要占多少个字节的存储空间?如果数组元素以行优先的顺序存储，设第一个元素的首地址是100，试求元素A[5，0，7]的存储首地址。31、设将n（n＞1）个整数存放到一维数组R中。试设计一个在时间和空间两方面都尽可能高效的算法，将R中存有的序列循左移P（0＜P＜n）个位置，即将R中的数据由（X0，X1，…，Xn－1）变换为（xp，xp＋1，…，xn－1，x0，x1，…，xp－1）。要求：（1） 给出算法的基本设计思想。（2） 根据设计思想，采用C或C＋＋或JAVA语言描述算法，关键之处给出注释。说明你所设计算法的时间复杂度和空间复杂度。五、算法设计题32、在一棵以二叉链表表示的二叉树上，试写出按层次顺序遍历二叉树的方法，统计树中具有度为1的结点数目的算法。33、设从键盘输入一整数的序列：a1，a2，a3，…，an，试编写算法实现：用栈结构存储输入的整数，当ai≠-1时，将ai入栈；当ai=-l时，输出栈顶整数并出栈。算法应对异常情况（入栈满等）给出相应的信息。34、假设有两个按元素值递增次序排列的线性表，均以单链表形式存储。请编写算法将这两个单链表归并为一个按元素值递减次序排列的单链表，并要求利用原来两个单链表的结点存放归并后的单链表。35、已知顺序表中有m个记录，表中记录不依关键字有序排列，编写算法为该顺序表建立一个有序的索引表，索引表中的每一项含记录的关键字和该记录在顺序表中的序号，要求算法的时间复杂度在最好的情况下能达到O（m）。

参考答案一、选择题1、【答案】D2、【答案】B3、【答案】C4、【答案】C5、【答案】B6、【答案】A7、【答案】C8、【答案】B9、【答案】D10、【答案】D二、填空题11、【答案】a+1；n%10【解析】通过递归算法，首先找到最高位的值，将其放到str对应的数组中，依次反向获取从高位到地位的值，将其放到数组中，完成了将整数逆序放到一个字符数组中。12、【答案】3；（10，7，-9，0，47，23，1，8，98，36）@13、【答案】稳定14、【答案】f->next=p->next；f->prior=p；p->next->prior=f；p->next=f。15、【答案】关键字；记录号；记录号；顺序；直接16、【答案】【解析】用顺序存储结构存储二叉树时，要按完全二叉树的形式存储，非完全二叉树存储时，要加“虚结点”。设编号为i和j的结点在顺序存储中的下标为s和t，则结点i和j在同一层上的条件是17、【答案】stack[tp]=t；p=stack[tp--]；p；++tp【解析】本题主要使用堆栈完成了二叉树左右子树交换的操作。首先根结点进栈，然后判断栈是否为空，如果不为空，则取栈顶元素，交换取出结点的左右指针。并将左右指针分别进栈，重复这一操作。完成二叉树左右孩子的交换。18、【答案】01122312三、判断题19、【答案】√20、【答案】√21、【答案】×22、【答案】√23、【答案】√24、【答案】×25、【答案】×26、【答案】×27、【答案】√28、【答案】√四、简答题29、答：（1）2一路归并第一趟：18，29，25，47，12，58，10，51。第二趟：18，25，29，47，10，12，51，58。第三趟：10，12，18，25，29，47，51，58。（2）快速排序第一趟：10，18，25，12，29，58，51，47。第二趟：10，18，25，12，29，47，51，88。第三趟：10，12，18，25，29，47，51，88。（3）堆排序建大堆：58，47，51，29，18，12，25，10。51，47，25，29，18，12，10，58。47，29，25，10，18，12，51，58。29，18，25，10，12，47，51，58。25，18，12，10，29，47，51，58。18，10，12，25，29，47，51，58。12，10，18，25，29，47，51，58。10，12，18，25，29，47，51，58。30、答：数组占的存储字节数=10*9*7*4=2520；A[5，0，7]的存储地址=100+[4*9*7+2*7+5]*4=1184。31、答：（1）算法的基本设计思想：先将n个数据由x0，x1，…，xp，…，xn－1原地逆置，得到xn－1，…，xp，xp－1，…，x0然后再