2023年最新的数据结构试题答案9篇数据结构试题答案(1) 数据结构专升本考试试题 （2023年3月） 一、单项选择题（本大题共20小题，每小题2分，共40分） 1对于一个算法，当输入非法数据时，也要能作出相应的处理，这种要求称为（ ）。 (A) 正确性 (B) 可行性 (C) 健壮性 (D) 输入性 2设S为C语言的语句,计算机执行下面算法时，算法的时间复杂度为（ ）。 for(i=n-1；i=0；i-) for(j=0；jnext; p-next= Q.front-next; （B）p=Q.front-next; Q.front-next=p-next; （C）p=Q.rear-next; p-next= Q.rear-next; （D）p=Q-next; Q-next=p-next; 9 Huffman树的带权路径长度WPL等于（ ） （A）除根结点之外的所有结点权值之和 （B）所有结点权值之和 （C）各叶子结点的带权路径长度之和 （D）根结点的值 10线索二叉链表是利用（ ）域存储后继结点的地址。 （A）lchild （B）data （C）rchild （D）root 11研究数据结构就是研究（ ）。 （A） 数据的逻辑结构 （B） 数据的存储结构 （C） 数据的逻辑结构和存储结构 （D） 数据的逻辑结构、存储结构及其基本操作 12算法分析的两个主要方面是（ ）。 （A）空间复杂度和时间复杂度 （B）正确性和简单性 （C）可读性和文档性 （D）数据复杂性和程序复杂性 13若一个线性表中最常用的操作是取第i个元素和找第i个元素的前趋元素，则采用（ ）存储方式最节省时间。 （A）顺序表 （B）单链表 （C）双链表 （D）单循环链表 14在一个长度为n的顺序表中，在第i个元素之前插入一个新元素时，需向后移动（ ）个元素。 （A） n-i （B） n-i+1 （C）n-i-1 （D）i 15非空的循环单链表head的尾结点p满足（ ）。 （A） p-next=head （B） p-next=NULL （C） p=NULL （D）p=head 16一个栈的输入序列为：a，b，c，d，e，则栈的不可能输出的序列是（ ）。 （A）a,b,c,d,e （B）d,e,c,b,a （C）d,c,e,a,b （D）e,d,c,b,a 17设SUBSTR(S,i,k)是求S中从第i个字符开始的连续k个字符组成的子串的操作，则对于S=Beijing E=(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 4. 画出向小根堆中加入数据4, 2, 5, 8, 3时，每加入一个数据后堆的变化。 四、阅读算法（每题7分，共14分） 1. LinkList mynote(LinkList L) /L是不带头结点的单链表的头指针 if(L ABC (BT-right); coutdata；p-next=q-next；free(q)； (B) q=p-next；q-data=p-data；p-next=q-next；free(q)； (C) q=p-next；p-next=q-next；free(q)； (D) q=p-next；p-data=q-data；free(q)； 4设有n个待排序的记录关键字，则在堆排序中需要（ ）个辅助记录单元。 (A) 1 (B) n (C) nlog2n (D) n2 5设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( )。 (A) 10，15，14，18，20，36，40，21 (B) 10，15，14，18，20，40，36，21 (C) 10，15，14，20，18，40，36，2l (D) 15，10，14，18，20，36，40，21 6设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（ ）。 (A) O(1) (B) O(log2n) (C) (D) O(n2) 7设无向图G中有n个顶点e条边，则其对应的邻接表中的表头结点和表结点的个数分别为（ ）。 (A) n，e (B) e，n (C) 2n，e (D) n，2e 8. 设某强连通图中有n个顶点，则该强连通图中至少有（ ）条边。 (A) n(n-1) (B) n+1 (C) n (D) n(n+1) 9设有5000个待排序的记录关键字，如果需要用最快的方法选出其中最小的10个记录关键字，则用下列（ ）方法可以达到此目的。 (A) 快速排序 (B) 堆排序 (C) 归并排序 (D) 插入排序 10.下列四种排序中（ ）的空间复杂度最大。 (A) 插入排序 (B) 冒泡排序 (C) 堆排序 (D) 归并排序 二、填空殖(每空1分 共20分) 1. 数据的物理结构主要包括_和_两种情况。 2. 设一棵完全二叉树中有500个结点，则该二叉树的深度为_；若用二叉链表作为该完全二叉树的存储结构，则共有_个空指针域。 3. 设输入序列为1、2、3，则经过栈的作用后可以得到_种不同的输出序列。 4. 设有向图G用邻接矩阵Ann作为存储结构，则该邻接矩阵中第i行上所有元素之和等于顶点i的_，第i列上所有元素之和等于顶点i的_。 5. 设哈夫曼树中共有n个结点，则该哈夫曼树中有_个度数为1的结点。 6. 设有向图G中有n个顶点e条有向边，所有的顶点入度数之和为d，则e和d的关系为_。 7. _遍历二叉排序树中的结点可以得到一个递增的关键字序列（填先序、中序或后序）。 8. 设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多需要比较_次就可以断定数据元素X是否在查找表中。 9. 不论是顺序存储结构的栈还是链式存储结构的栈，其入栈和出栈操作的时间复杂度均为_。 10. 设有n个结点的完全二叉树，如果按照从自上到下、从左到右从1开始顺序编号，则第i个结点的双亲结点编号为_，右孩子结点的编号为_。 11. 设一组初始记录关键字为(72，73，71，23，94，16，5)，则以记录关键字72为基准的一趟快速排序结果为_。 12. 设有向图G中有向边的集合E=，则该图的一种拓扑序列为_。 13. 下列算法实现在顺序散列表中查找值为x的关键字，请在下划线处填上正确的语句。 struct recordint key; int others; int hashsqsearch(struct record hashtable ,int k) int i,j; j=i=k % p; while (hashtablej.key!=k if (i=j) return(-1); if (_ ) return(j); else return(-1); 14. 下列算法实现在二叉排序树上查找关键值k，请在下划线处填上正确的语句。 typedef struct nodeint key; struct node *lchild; struct node *rchild;bitree; bitree *bstsearch(bitree *t, int k) if (t=0 ) return(0);else while (t!=0) if (t-key=k)_; else if (t-keyk) t=t-lchild; else_; 三、计算题(每题10分，共30分) 1.已知二叉树的前序遍历序列是AEFBGCDHIKJ，中序遍历序列是EFAGBCHKIJD，画出此二叉树，并画出它的后序线索二叉树。 2已知待散列的线性表为（36，15，40，63，22），散列用的一维地址空间为0.6，假定选用的散列函数是H（K）= K mod 7，若发生冲突采用线性探查法处理，试： （1）计算出每一个元素的散列地址并在下图中填写出散列表： 0 1 2 3 4 5 6 （2）求出在查找每一个元素概率相等情况下的平均查找长度。 3已知序列（10，18，4，3，6，12，1，9，18，8）请用快速排序写出每一趟排序的结果。 四、算法设计题(每题15分，共30分) 1 设计在单链表中删除值相同的多余结点的算法。 2 设计一个求结点x在二叉树中的双亲结点算法。 数据结构试卷（四） 一、选择题(每题1分共 20分) 1设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ ）。 (A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2) 2设一棵二叉树的深度为k，则该二叉树中最多有（ ）个结点。 (A) 2k-1 (B) 2k (C) 2k-1 (D) 2k-1 3设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为（ ）。 (A) n (B) e (C) 2n (D) 2e 4在二叉排序树中插入一个结点的时间复杂度为（ ）。 (A) O(1) (B) O(n) (C) O(log2n) (D) O(n2) 5设某有向图的邻接表中有n个表头结点和m个表结点，则该图中有（ ）条有向边。 (A) n (B) n-1 (C) m (D) m-1 6设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（ ）趟的分配和回收才能使得初始关键字序列变成有序序列。 (A)