2023年计算机考研专业课数据结构部分真题.doc

2023 年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第 140 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项最符合试题规定。1为解决计算机主机与打印机之间速度不匹配问题，通常设立一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。该缓冲区的逻辑结构应当是 。A栈B队列C树D图2设栈 S 和队列 Q 的初始状态均为空，元素 a，b，c，d，e，f，g 依次进入栈S。若每个元素出栈后立即进入队列 Q，且 7 个元素出队的顺序是 b，d，c，f，e，a，g，则栈 S 的容量至少是。A1B2C3D43给定二叉树如图 A-1 所示。设 N 代表二叉树的根，L 代表根结点的左子树，R 代表根结点的右子树。若遍历后的结点序列是 3，1，7，5，6，2，4，则其遍历方式是。ALRNBNRLCRLNDRNL图 A-14下列二叉排序树中，满足平衡二叉树定义的是。ABCD5已知一棵完全二叉树的第 6 层（设根为第 1 层）有 8 个叶结点，则该完全二叉树的结点个数最多是。A39B52C111D1196将森林转换为相应的二叉树，若在二叉树中，结点 u 是结点 v 的父结点的父结点，则在本来的森林中，u 和 v 也许具有的关系是。父子关系兄弟关系u 的父结点与 v 的父结点是兄弟关系A只有B和C和D、和7下列关于无向连通图特性的叙述中，对的的是。所有顶点的度之和为偶数边数大于顶点个数减 1至少有一个顶点的度为 1A只有B只有C和D和8下列叙述中，不符合 m 阶 B 树定义规定的是。A根结点最多有 m 棵子树B所有叶结点都在同一层上C各结点内关键字均升序或降序排列 D叶结点之间通过指针链接9已知关键字序列 5，8，12，19，28，20，15，22 是小根堆（最小堆），插入关键字 3，调整后得到的小根堆是。A3，5，12，8，28，20，15，22，19二、综合应用题：第 4147 题，共 70 分。41（10 分）带权图（权值非负，表达边连接的两顶点间的距离）的最短途径问题是找出从初始顶点到目的顶点之间的一条最短途径。假设从初始顶点到目的顶点之间存在途径，现有一种解决该问题的方法： 设最短途径初始时仅包含初始顶点，令当前顶点 u 为初始顶点； 选择离 u 最近且尚未在最短途径中的一个顶点 v，加入到最短途径中，修改当前顶点 u=v； 反复环节，直到 u 是目的顶点时为止。请问上述方法能否求得最短途径？若该方法可行，请证明之；否则，请举例说明。42（15 分）已知一个带有表头结点的单链表，结点结构为：datalink假设该链表只给出了头指针 list。在不改变链表的前提下，请设计一个尽也许高效的算法，查找链表中倒数第 k 个位置上的结点（k 为正整数）。若查找成功，算法输出该结点的 data 域的值，并返回 1；否则，只返回 0。规定：1）描述算法的基本设计思想。2）描述算法的具体实现环节。3）根据设计思想和实现环节，采用程序设计语言描述算法（使用 C、C+或 Java 语言实现），关键之处请给出简要注释。2023 年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第 140 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项最符合试题规定。1若元素 a、b、c、d、e、f 依次进栈，允许进栈、退栈操作交替进行，但不允许连续三次进行退栈操作，则不也许得到的出栈序列是。Ad c e b f aBc b d a e fCb c a e f dDa f e d c b2某队列允许在其两端进行入队操作，但仅允许在一端进行出队操作。若元素 a、b、c、d、e 依次入此队列后再进行出队操作，则不也许得到的出队序列是。Ab a c d eBd b a c eCd b c a eDe c b a d3下列线索二叉树中（用虚线表达线索），符合后序线索树定义的是。ABCD4在图 B-1 所示的平衡二叉树中，插入关键字 48 后得到一棵新平衡二叉树。在新平衡二叉树中，关键字 37 所在结点的左、右子结点中保存的关键字分别是。A13，48B24，48C24，53D24，905在一棵度为 4 的树 T 中，若有 20 个度为 4 的结点，10 个度为 3 的结点，1 个度为 2 的结点，10 个度为 1的结点，则树 T 的叶结点个数是图 B-1。A41B82C113D1226对 n（n2）个权值均不相同的字符构导致赫夫曼树。下列关于该赫夫曼树的叙述中，错误的是。A该树一定是一棵完全二叉树B树中一定没有度为 1 的结点C树中两个权值最小的结点一定是兄弟结点D树中任一非叶结点的权值一定不小于下一层任一结点的权值7若无向图 G=(V, E)中具有 7 个顶点，要保证图 G 在任何情况下都是连通的，则需要的边数最少是。A6B15C16D21 8 对图 B-2 进行拓扑排序，可以得到不同的拓扑序列的个数是。A4B3C2D19已知一个长度为 16 的顺序表 L，其元素按关键字有序排列。若采用折半查找法查找一个 L 中不存在的元素，则关键字的比较次数最多的是。图 B-2A4B5C6D710采用递归方式对顺序表进行快速排序。下列关于递归次数的叙述中，对的的是 。A递归次数与初始数据的排列顺序无关B每次划分后，先解决较长的分区可以减少递归次数C每次划分后，先解决较短的分区可以减少递归次数D递归次数与每次划分后得到的分区的解决顺序无关11对一组数据（2，12，16，88，5，10）进行排序，若前三趟排序结果如下： 第一趟排序结果：2，12，16，5，10，88第二趟排序结果：2，12，5，10，16，88第三趟排序结果：2，5，10，12，16，88则采用的排序方法也许是。A冒泡排序B希尔排序 C归并排序 D基数排序二、综合应用题：第 4147 题，共 70 分。41（10 分）将关键字序列（7、8、30、11、18、9、14）散列存储到散列表中。散列表的存储空间是一个下标从 0 开始的一维数组，散列函数为 H(key)=(key×3) MOD 7，解决冲突采用线性探测再散列法，规定装填（载）因子为 0.7。1）请画出所构造的散列表。2）分别计算等概率情况下查找成功和查找不成功的平均查找长度。42（13 分）设将 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 语言描述算法，关键之处给出注释。3）说明你所设计算法的时间复杂度和空间复杂度。2023 年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：140 小题，每小题 2 分，共 80 分。下列每小题给出的四个选项中，只有一项符合题目规定。（请在答题卡上将所选项的字母涂黑。）1设 n 是描述问题规模的非负整数，下面程序片段的时间复杂度是。x=2；while(x<n/2)x=2*x；AO(log2n)BO(n)CO(nlog2n)DO(n2)2元素 a，b，c，d，e 依次进入初始为空的栈中，若元素进栈后可停留、可出栈，直到所有元素都出栈，则在所有也许的出栈序列中，以元素 d 开头的序列个数是。A3B4C5D63已知循环队列存储在一维数组 A0.n-1中，且队列非空时 front 和 rear 分别指向队头元素和队尾元素。若初始时队列为空，且规定第 1 个进入队列的元素存储在 A0处，则初始时 front 和 rear 的值分别是。A0，0B0，n-1Cn-1，0Dn-1，n-14若一棵完全二叉树有 768 个结点，则该二叉树中叶结点的个数是A257B258C384D3855若一棵二叉树的前序遍历序列和后序遍历序列分别为 1，2，3，4 和 4，3，2，1，则该二叉树的中序遍历序列不会是。A1，2，3，4B2，3，4，1C3，2，4，1D4，3，2，16已知一棵有 2023 个结点的树，其叶结点个数为 116，该树相应的二叉树中无右孩子的结点个数是。A115B116C1895D18967对于下列关键字序列，不也许构成某二叉排序树中一条查找途径的序列是。A95，22，91，24，94，71B92，20，91，34，88，35C21，89，77，29，36，38D12，25，71，68，33，348下列关于图的叙述中，对的的是。回路是简朴途径存储稀疏图，用邻接矩阵比邻接表更省空间若有向图中存在拓扑序列，则该图不存在回路A仅B仅、C仅D仅、9为提高散列（Hash）表的查找效率，可以采用的对的措施是。增大装填（载）因子设计冲突（碰撞）少的散列函数解决冲突（碰撞）时避免产生聚集（堆积）现象A仅B仅C仅、D仅、10为实现快速排序算法，待排序序列宜采用的存储方式是。A顺序存储B散列存储C链式存储D索引存储11已知序列 25，13，10，12，9 是大根堆，在序列尾部插入新元素 18，将其再调整为大根堆，调整过程中元素之间进行的比较次数是。A1B2C4D5二、综合应用题：4147 小题，共 70 分。请将答案写在答题纸指定位置上。41（8 分）已知有 6 个顶点（顶点编号为 05）的有向带权图 G，其邻接矩阵 A 为上三角矩阵，按行为主序（行优先）保存在如下的一维数组中。4 654 33 3 （1）写出图 G 的邻接矩阵 A。（2）画出有向带权图 G。（3）求图 G 的关键途径，并计算该关键途径的长度。42（15 分）一个长度为 L（L1）的升序序列 S，处在第 ëL/2ù 个位置的数称为 S 的中位数。例如，若序列 S1=（11，13，15，17，19），则 S1 的中位数是 15，两个序列的中位数是含它们所有元素的升序序列的中位数。例如，若 S2=（2，4，6，8，20），则 S1 和 S2 的中位数是 11。现在有两个等长升序序列 A 和 B，试设计一个在时间和空间两方面都尽也许高效的算法，找出两个序列 A 和 B 的中位数。规定：（ 1）给出算法的基本设计思想。（ 2）根据设计思想，采用 C 或 C+或 JAVA 语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。2023 年全国硕士研究生入学统一考试计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第 140 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项最符合试题规定。1求整数 n(n0)阶乘的算法如下，其时间复杂度是。int fact(int n)if (n<=1) return 1;return n*fact(n-1);A. O(log2n)B. O(n)C. O(nlog2n)D. O(n2)2已知操作符涉及+、-、*、/、(和)。将中缀表达式 a+b-a*(c+d)/e-f)+g 转换为等价的后缀表达式 ab+acd+e/f-*-g+时，用栈来存放暂时还不能拟定运算顺序的操作符，若栈初始时为空，则转换过程中同时保存在栈中的操作符的最大个数是。A5B7C8D113若一棵二叉树的前序遍历序列为 a, e, b, d, c，后序遍历序列为 b, c, d, e, a，则根结点的孩子结点。A. 只有 eB. 有 e、bC. 有 e、cD. 无法拟定4若平衡二叉树的高度为 6，且所有非叶结点的平衡因子均为 1，则该平衡二叉树的结点总数为。A. 10B. 20C. 32D. 335对有 n 个结点、e 条边且使用邻接表存储的有向图进行广度优先遍历，其算法时间复杂度是。AO(n)BO(e)CO(n+e)DO(n*e)6若用邻接矩阵存储有向图，矩阵中主对角线以下的元素均为零，则关于该图拓扑序列的结论是。A存在，且唯一B存在，且不唯一C存在，也许不唯一D无法拟定是否存在7对如下有向带权图，若采用迪杰斯特拉（Dijkstra）算法求从源点 a 到其他各顶点的最短途径，则得到的第一条最短途径的目的顶点是 b，第二条最短途径的目的顶点是 c，后续得到的其余各最短途径的目的顶点依次是。Ad,e,fBe,d,fCf,d,eDf,e,d8下列关于最小生成树的叙述中，对的的是 。最小生成树的代价唯一所有权值最小的边一定会出现在所有的最小生成树中使用普里姆（Prim）算法从不同顶点开始得到的最小生成树一定相同使用普里姆算法和克鲁斯卡尔（Kruskal）算法得到的最小生成树总不相同A仅B仅C仅、D仅、9已知一棵 3 阶 B-树，如下图所示。删除关键字 78 得到一棵新 B-树，其最右叶结点中的关键字是。A60B60, 62C62, 65D6510在内部排序过程中，对尚未拟定最终位置的所有元素进行一遍解决称为一趟排序。下列排序方法中，每一趟排序结束都至少可以拟定一个元素最终位置的方法是简朴选择排序希尔排序快速排序堆排序二路归并排序A仅、B仅、C仅、D仅、11对一待排序序列分别进行折半插入排序和直接插入排序，两者之间也许的不同之处是。A排序的总趟数B元素的移动次数C使用辅助空间的数量D元素之间的比较次数二、综合应用题：第 4147 题，共 70 分。41设有 6 个有序表 A、B、C、D、E、F，分别具有 10、35、40、50、60 和 200 个数据元素，各表中元素按升序排列。规定通过 5 次两两合并，将 6 个表最终合并成 1 个升序表，并在最坏情况下比较的总次数达成最小。请问答下列问题。1）给出完整的合并过程，并求出最坏情况下比较的总次数。2）根据你的合并过程，描述 N（N2）个不等长升序表的合并策略，并说明理由。42假定采用带头结点的单链表保存单词，当两个单词有相同的后缀时，则可共享相同的后缀存储 空间，例如，“loading”和“being”的存储映像如下图所示。设 str1 和 str2 分别指向两个单词所在单链表的头结点，链表结点结构为 ，请设计一个时间上尽也许高效的算法，找出由 str1 和 str2 所指向两个链表共同后缀的起始位置（如图中字符 i 所在结点的位置 p）。规定：1）给出算法的基本设计思想。2）根据设计思想，采用 C 或 C+或 JAVA 语音描述算法，关键之处给出注释。3）说明你所设计算法的时间复杂度。2023 年全国硕士研究生入学统一考试 计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：140 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只有一个选项符合试题规定。1.已知两个长度分别为 m 和 n 的升序链表，若将它们合并为一个长度为 m+n 的降序链表，则最坏情况下的时间复杂度是A. O(n)B. O(m´ n)C. O(min(m, n)D. O(max(m, n)2.一个栈的入栈序列为1, 2,3, ,n ，其出栈序列是 p1, p2 , p3 , pn 。若 p2 = 3 ，则 p3 也许取的个数是A. n - 3B. n - 2C. n -1D. 无法拟定3.若将关键字 1，2，3，4，5，6，7 依次插入到初始为空的平衡二叉树 T 中，则 T 中平衡因子为 0 的分支结点的个数是A. 0B. 1C. 2D. 34.已知三叉树 T 中 6 个叶结点的权分别是 2，3，4，5，6，7，T 的带权（外部）途径长度最小是A. 27B. 46C. 54D. 565.若 X 是后序线索二叉树中的叶结点，且 X 存在左兄弟结点 Y，则 X 的右线索指向的是A. X 的父结点B. 以 Y 为根的子树的最左下结点C. X 的左兄弟结点 YD. 以 Y 为根的子树的最右下结点6.在任意一棵非空二叉排序树 T1 中，删除某结点v 之后形成二叉排序树 T2，再将v 插入 T2 形成二叉排序树 T3。下列关于 T1 与 T3 的叙述中，对的的是I. 若v 是 T1 的叶结点，则 T1 与 T3 不同II. 若v 是 T1 的叶结点，则 T1 与 T3 相同III. 若v 不是 T1 的叶结点，则 T1 与 T3 不同IV. 若v 不是 T1 的叶结点，则 T1 与 T3 相同A. 仅 I、IIIB. 仅 I、IVC. 仅 II、IIID. 仅 II、IV7. 设图的邻接矩阵 A 如下所示。各顶点的度依次是é0101ùêúA = ê0011úê0100úêúë1000ûA. 1，2，1，2B. 2，2，1，1C. 3，4，2，3D. 4，4，2，28. 若对如下无向图进行遍历，则下列选项中，不是广度优先遍历序列的是A. h，c，a，b，d，e，g，fB. e，a，f，g，b，h，c，dC. d，b，c，a，h，e，f，gD. a，b，c，d，h，e，f，gabec df gh9. 下列 AOE 网表达一项包含 8 个活动的工程。通过同时加快若干活动的进度可以缩短整个工程的工期。下列选项中，加快其进度就可以缩短工程工期的是2c=94a=3g=6e=6d=442b=8h=924f=10A.c 和 eB. d 和 eC. f 和 dD. f 和 h10. 在一株高度为 2 的 5 阶 B 树中，所含关键字的个数最少是A.5B. 7C. 8D. 1411. 对给定的关键字序列 110，119，007，911，114，120，122 进行基数排序，则第 2 趟分派收集后得到的关键字序列是A. 007，110，119，114，911，120，122B. 007，110，119，114，911，122，120C. 007，110，911，114，119，120，122D. 110，120，911，122，114，007，119二、综合应用题：4147 小题，共 70 分。41. （ 13 分 ） 已知一个整数序列 A = (a0 , a1, , an-1) ， 其中 0 £ ai < n(0 £ i < n) 。若存在ap1 = ap2 = = apm = x 且m > n / 2(0 £ pk < n,1 £ k £ m) ，则称 x 为 A 的主元素。例如 A=( 0， 5，5，3，5，7，5，5 )，侧 5 为主元素；又如 A= ( 0，5，5，3，5，1，5，7 )，则A 中没有主元素。假设 A 中的 n 个元素保存在一个一维数组中，请设计一个尽也许高效的算法，找出 A 的主元素。若存在主元素，则输出该元素；否则输出-1。规定：（1）给出算法的基本设计思想。（2）根据设计思想，采用 C 或 C+或 Java 语言描述算法，关键之处给出注释。（3）说明你所设计算法的时间复杂度和空间复杂度。42. （10 分）设包含 4 个数据元素的集合 S= "do"，"for"，" repeat"，" while"，各元素的查 找概率依次为：p1=0.35，p2 = 0.15，p3=0. 15，p4=0.35。将 S 保存在一个长度为 4 的顺序表中，采用折半查找法，查找成功时的平均查找长度为 2.2。请回答：（1）若采用顺序存储结构保存 S，且规定平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？（2）若采用链式存储结构保存 S，且规定平均查找长度更短，则元素应如何排列？应使用何种查找方法？查找成功时的平均查找长度是多少？2023年全国硕士研究生入学统一考试计算机学科专业基础综合试题一、单项选择题：140小题，每小题2分，共80分。下列每题给出的四个选项中，只有一个选项是符合题目规定的。 1. 下列程常段的时间复杂度是count=0;for(k=1;k<=n;k*=2)for(j=1;j<=n;j+1)count+;A.O(log2n) B.O(n) C.O(nlog2n) D.O(n2)2. 假设栈初始为空，将中缀表达式转换为等价后缀表达式的过程中，当扫描到f时，栈中的元素依次是A B. C. D. 3. 循环两列放在一维数组A0M-1中，end1指向队头元素，end2指向队尾元素的后一个位置。假设队列两端均可进行入队和出队操作，队列中最多能容纳M-1个元素。初始时为空，下列判断队空和队满的条件中，对的的是A.队空：end1=end2； 队满：end1=(end2+1)modMB.队空：end1=end2; 队满：end2=(end1+1)mod(M-1)C.队空：end2=(end1+1)modM ; 队满：end1=（end2+1）modMD.队空：end1=（end2+1）modM; 队满：end2=(end1+1)mod(M-1)4. 若对如下的二叉树进行中序线索化，则结点x的左、右线索指向的结点分别是A.e,c B.e,a C.d,c D.b,a5. 将森林F转换为相应的二叉树T，F中叶结点的个数等于A.T中叶结点的个数 B.T中度为1的结点个数 C.T中左孩子指针为空的结点个数 D.T中右孩子指针为空的结点个数6. 5个字符有如下4种编码方案，不是前缀编码的是A.01,0000,0001,001,1 B.011,000,001,010,1C.000,001,010,011,100 D.000,001,010,011,1007. 对如下所示的有向图进行拓扑排序，得到的拓扑序列也许是A.3,1,2,4,5,6 B.3,1,2,4,6,5 C.3,1,4,2,5,6 D.3,1,4,2,6,58. 用哈希（散列）方法解决冲突（碰撞）时也许出现堆积（聚集）现象，下列选项中，会受堆积现象直接影响的是A.存储效率 B.数列函数 C.装填（装载）因子 D.平均查找长度9.在一棵具有15个关键字的4阶B树中，含关键字的结点数最多是A.5 B.6 C.10 D.1510. 用希尔排序方法对一个数据序列进行排序时，若第1趟排序结果为9,1,4,13,7,8,20,23,15，则该趟排序采用的增量（间隔）也许是A.2 B.3 C.4 D.511. 下列选项中，不也许是快速排序第2趟排序结果的是A.2,3,5,4,6,7,9 B.2,7,5,6,4,3,9 C.3,2,5,4,7,6,9 D.4,2,3,5,7,6,9二、综合应用题：4147小题，共70分。 41.（13分）二叉树的带权途径长度（WPL）是二叉树中所有叶结点的带权途径长度之和，给定一棵二叉树T，采用二叉链表存储，节点结构为：leftweightright其中叶节点的weight域保存该结点的非负权值。设root为指向T的根节点的指针，设计求T的WPL的算法。规定：（1）给出算法的基本设计思想；（2）使用C或C+语言，给出二叉树结点的数据类型定义；（3）根据设计思想，采用C或C+语言描述算法，关键之处给出注释。2023 年全国硕士研究生入学统一考试 计算机科学与技术学科联考计算机学科专业基础综合试题一、单项选择题：第 140 小题，每小题 2 分，共 80 分。下列每题给出的四个选项中，只 有一个选项最符合试题规定。1已知程序如下：int S(int n) return (n<=0)?0:s(n-1)+n; void main() cout<< S(1);程序运营时使用栈来保存调用过程的信息，自栈底到栈顶保存的信息依次相应的是。Amain()S(1)S(0)BS(0)S(1)main()Bmain()S(0)S(1)DS(1)S(0)main()2先序序列为 a,b,c,d 的不同二叉树的个数A13B14C15D163下列选项给出的是从根分别到达两个叶结点途径上的权值序列，能属于同一棵哈夫曼树的是A24,10,5 和 24,10,7B24,10,5 和 24,12,7C24,10,10 和 24,14,11D24,10,5 和 24,14,64现有一棵无反复关键字的平衡二叉树（AVL 树），对其进行中序遍历可得到一个降序序列。下列关于该平衡二叉树的叙述中，对的的是A根结点的度一定为 2B树中最小元素一定是叶结点C最后插入的元素一定是叶结点D树中最大元素一定是无左子树5设有向图 G=(V,E)，顶点集 V=V0,V1,V2,V3，边集 E=<v0,v1>，<v0,v2>，<v0,v3>，<v1,v3>。若从顶点 V0 开始对图进行深度优先遍历，则也许得到的不同遍历序列个数是。A2B3C4D56求下面带权图的最小（代价）生成树时，也许是克鲁斯卡（Kruskal）算法第 2 次选中但不是普里姆（Prim）算法（从 V4 开始）第 2 次选中的边是A(V1,V3)B(V1,V4)C(V2,V3)D(V3,V4)7下列选项中，不能构成折半查找中关键字比较序列的是。A500,200,450,180B500,450,200,180C180,500,200,450D180,200,500,4508已知字符串 S 为“abaabaabacacaabaabcc”，模式串 t 为“abaabc”。采用 KMP 算法进行匹配，第一次出现“失配”(sitj) 时，i=j=5，则下次开始匹配时，i 和 j 的值分别是Ai=1,j=0Bi=5,j=0Ci=5,j=2Di=6,j=29下列排序算法中，元素的移动次数与关键字的初始排列顺序无关的是A直接插入排序B起泡排序C基数排序D快速排序10已知小根堆为 8,15,10,21,34,16,12，删除关键字 8 之后需重建堆，在此过程中，关键字之间的比较次数是A1B2C3D411希尔排序的组内排序采用的是A直接插入排序B折半插入排序C快速排序D归并排序41（15 分）用单链表保存 m 个整数，结点的结构为：datalink，且|data|n（n 为正整数）。现 规定设计一个时间复杂度尽也许高效的算法，对于链表中 data 的绝对值相等的结点，仅保存第一次出 现的结点而删除其余绝对值相等的结点。例如，若给定的单链表 head 如下：则删除结点后的 head 为：规定：1）给出算法的基本设计思想。2）使用 C 或 C+语言，给出单链表结点的数据类型定义。3）根据设计思想，采用 C 或 C+语言描述算法，关键之处给出注释。4）说明你所设计算法的时间复杂度和空间复杂度。42（8 分）已知具有 5 个顶点的图 G 如下图所示。请回答下列问题：1）写出图 G 的邻接矩阵 A（行、列下标从 0 开始）。2）求 A2，矩阵 A2 中位于 0