2021年2021年数据结构期末考试试题和标准答案及评分标准.docx

精品word 可编辑资料 - - - - - - - - - - - - -学习资料收集于网络，仅供参考数据结构试题（ A 卷）（考试时间：90 分钟）一.单项挑选题 （本大题共 15 小题，每道题 2 分，共 30 分）（每题只有一个选项为正确的、 将答案填写在括号内，错选.多项不得分）1. （）为组成数据的基本单位，为一个数据整体中相对独立的单元；A数据B. 数据元素C. 数据对象D. 数据结构2. 算法运算量的大小称为算法的（）；A. 效率B.复杂度C.数据元素之间的关系D. 数据的储备方法 3.如某线性表最常用的操作为存取任一指定序号的元素和在最终进行插入或删除运算，就采纳以下（）方式最节约时间；A. 链式储备B.索引储备C.次序储备D.散列储备4. 下述哪一条为次序储备结构的优点？（）A. 储备密度大B.插入运算便利C.删除运算便利D.可便利地用于各种规律结构的储备表示5. 在一个单链表中，如删除p 所指结点的后续结点，就执行（）；A.p->next=p->next->nextB.p->next=p->next C.p=p->next;p->next=p->next->nextD.p=p->next->next6. 带头结点的单链表head 为空的判定条件为（）；A. head=NULLB.head->next=NULLC.head->next=headD.head.=NULL7. 非空的循环单链表head 的尾结点 ( 由 p 所指向 ) 满意（）；A.p->head=NULLB.p=NULLC.p->next=headD.p=head8. 下面关于线性表的表达中，错误选项哪一个？（）A. 线性表采纳次序储备，必需占用一片连续的储备单元；B. 线性表采纳次序储备，便于进行插入和删除操作；C.线性表采纳链式储备，不必占用一片连续的储备单元；D. 线性表采纳链式储备，便于插入和删除操作；9. 队列操作的原就为（）；A. 后进先出B. 先进先出C. 只能进行插入D. 只能进行删除10.栈中答应进行插入和删除的一端称为（）；A. 栈首B.栈尾C.栈顶D.栈底11假设以数组An 存放循环队列的元素，其首尾指针分别为front 和 rear，就当前队列中的元素个数为（）；A （rear-front+n ） %nB. rear-front+1C.(front-rear+n)%nD.(rear-front)%n12.最大容量为n 的循环队列，队尾指针为rear，队首指针为front ，就队空的判定条件为（）；A. （ rear+1） %n=frontB.rear=frontC.rear+1=front D.(rear-1)%n=front13. 将一个十进制的数转换成二进制的数，可以使用以下一种称为（）的数据结构；A. 图B.树C. 广义表D.栈14. 把一棵树转换为二叉树后，这棵二叉树的外形为（）；A. 有 2 种B. 有 3 种C. 有 4 种D. 唯独的15.一棵左右子树均不空的二叉树在先序线索化后，其中空链域的个数为（）；学习资料第 1 页，共 11 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -学习资料收集于网络，仅供参考A. 3B. 2C. 0D.不确定二.填空题 （本大题共 10 个空，每空 2 分，共计 20 分）1数据结构为讨论程序设计中运算机操作的以及它们之间的关系和运算的一门学科；2在一个单链表中，已知指针q 所指结点为指针p 所指结点的前驱结点，如在q 和 p 之间插入结点s，就应执行两条语句： ，；3字符串采纳结点大小为2 的链表作为其储备结构，为指链表的每个链结点的域中只存放了 2 个字符；4广义表（ a、b、c、d）的表尾为；5一棵深度为k 的二叉树，最多有个结点；6已知有向图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 的拓扑序列为 _ ；7. 有 n 个顶点的连通图至少有条边；8. 图的储备常采纳和两种方法；三.判定题 （本大题共 10 小题，每题 1 分， 共 10 分）（请在每道题后面的括号里写出答案，假如正确，请写“”，假如错误，请写“”）1. 线性表采纳链表储备时，结点和结点内部的储备空间可以为不连续的；（）2线性表就为次序储备的表；（）3. 当线性表的元素总数基本稳固，且很少进行插入和删除操作，但要求以最快的速度存取线性表中的元素时，应采纳次序储备结构；（） 4线性表的链式储备结构所需要的储备空间一般要多于次序储备结构；（）5. 串的长度为指串中所含不同字符的个数；（）6. 对稀疏矩阵进行压缩储备的目的为节约储备空间；（）7. 二叉树为非线性数据结构，所以它不能采纳次序储备结构储备；（）8. 任意一棵二叉树中至少有一个结点的度为2；（）9. 对线性表进行二分查找时，要求线性必需以次序方式储备，且结点按关键字有序排序；（）10. 采纳线性探测法解决冲突问题，所产生的一系列后继散列地址必需大于等于原散列地址；（）四.应用题 （本小题共 5 小题，每道题 6 分，共 30 分）1.简述以下算法的功能（假设栈和队列的元素类型均为int） (6 分 ) void fun1(Queue &Q)Stack S; int x;Initstack(S); While(.QueueEmpty(Q)DeQueue(Q、x);Push(S、x); While(.StackEmpty(S)Pop(S、x);学习资料第 2 页，共 11 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -学习资料收集于网络，仅供参考EnQueue(Q、x);2.请将如图 4.1 所示的一棵树转换成一棵二叉树；（ 6 分）ABCD EFG图 4.1 一棵树3. 给定叶结点(a、b、c、d、e、f、g)，权值分别为23、12、15、7、17、2、8，画出对应的哈夫曼树，并写出各叶结点的哈夫曼编码；（6 分）4. （ 6 分）已知图G的邻接表如图4.2 所示，就：从顶点 v1 动身的深度优先搜寻序列为_ ；从顶点 v1 动身的广度优先搜寻序列为_ ；图 4.2 图 G 的邻接表5.求构造图4.3 所示无向网的最小生成树（6 分）学习资料第 3 页，共 11 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -学习资料收集于网络，仅供参考图 4.3 无向网五.算法设计题 （本大题共 1 小题，每道题 10 分，共 10 分）1.已知查找表的数据元素类型如下： Typedef struct Rectypeintnum; char name8;Rectype;假设查找表中有n 个记录，并且为按num 降序次序储备TypedefRectypeSqlist100;要求：（ 1）写出对给定值K 进行二分查找的算法和main 函数；（ 2）二分查找算法的函数头部为“intbinsearch(SqlistR、intn、intK) “（ 3）在 main 函数中建立该查找表.调用二分查找算法，并输出查找结果；学习资料第 4 页，共 11 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -学习资料收集于网络，仅供参考数据结构试题（ B 卷）（考试时间：90 分钟）一.单项挑选题 （本大题共 15 小题，每道题 2 分，共 30 分）（每题只有一个选项为正确的、 将答案填写在括号内，错选.多项不得分）1在数据结构中，数据的（）结构为独立于运算机的；A. 规律B.储备C.散列D.索引2以下程序段的时间复杂度为（）；for(i=0;i<n;i+)x=x-2;A. O（ 2n）B. O（ n）C. O （ 1）D.O（ n2）3. 链式储备结构表示的线性表也称为（）；A. 链表B.次序表C.双链表D.物理表4. 不带头结点的单链表（头指针为head）为空的判定条件为（）；A head=NULLB head->next=head C head->next=NULLD head.=NULL5线性表如采纳次序结构时，要求内存中可用储备单元的地址（）；A肯定为不连续的B部分地址为连续的C肯定为连续的D连续不连续都可以6.对于单链表，在两个结点之间插入一新结点需要修改的指针共（）个；A.0B.1C.2D.47.如线性表中有n 个元素，算法（）在单链表上实现要比在次序表上实现效率更高；A. 删除全部值为x 的元素B. 在最终一个元素的后面插入一个新元素C.次序输出前k 个元素D.交换其中某两个元素的值8.对于次序表，拜访结点和增加.删除结点的时间复杂度分别为（）；A.O(n)O(n)B. O(1)O(n)C. O(n) O(1)D. O(1) O(1)9. 队列的删除操作为在（）进行；A队首B队尾C 队首前一单元D 队尾后一单元10. 以下关于栈的表达中，正确选项（）； A栈底元素肯定为最终入栈的元素B栈操作遵循先进后出的原就 C栈顶元素肯定为最先入栈的元素D以上三种说法都不对11.设栈 S 和队列 Q 的初始状态为空，元素 e1.e2.e3.e4.e5 和 e6 依次进入栈 S 、一个元素出栈后即进入 Q，如 6 个元素出队的序列为 e2.e4.e3.e6.e5 和 e1，就栈 S 的容量至少为（ ）个 ；A.3B. 4C.5D.612.假设为循环队列安排的向量空间为Q20、 如队列的长度和队头指针值分别为13 和 17，就当前尾指针的值为 ；A.10B.11C.12D.1313.银行业务叫号系统采纳了数据结构；A栈B 广义表C队列D图14. 根据二叉树的定义，具有3 个结点的不同外形的二叉树有A.3B.4C.5D.6 种；15. n 个结点的线索二叉树上含有的线索数为 ；A.0B.n-1C.n+1D.2n学习资料第 5 页，共 11 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -学习资料收集于网络，仅供参考二.填空题 （本大题共 10 个空，每空 2 分，共 20 分）1数据结构包含三个方面的内容，即数据的规律结构.数据的结构和对数据所施加的操作；2已知指针q 值为 NULL .指针 p 指向单链表L 中的某结点，就删除其后继结点（要求由指针 q 指向）的语句为， free(q)； 3设广义表L= （ a、( ) ） 、就 Head(L)=；4当且仅当两个串的相等并且各个对应位置上的字符都相等时，称这两个串相等；5.二叉树的第4 层结点数最多为个；6除了利用求关键路径的方法，仍可以利用方法判定出一个有向图为否有环（回路）；7图的遍历主要有和两种方法；8. 具有 4 个顶点的无向完全图有条边；三.判定题 （本大题共 10 小题，每题 1 分， 共 10 分）（请在每道题后面的括号里写出答案，假如正确，请写“”，假如错误，请写“”）1. 对于一个线性表， 采纳次序储备方式进行插入和删除结点时效率太低，采纳链式储备方式更好； （ ）2. 所谓静态链表就为始终不发生变化的链表；（）3. 在次序表中，最终一个元素有一个后继；（）4. 线性表就为链式储备的表；（）5. 串为一种特别的线性表，其特别性表达在数据元素可以为多个字符；（）6. 对稀疏矩阵进行压缩储备的目的为便于输入和输出；（）7. 任意一棵二叉树中的度可以小于2；（）8. 树形结构最适合用来表示元素之间具有分支层次关系的数据；（）9. 当采纳分块查找时，数据的组织方式为：数据分成如干块，每块内数据必需有序；（）10. 次序查找法适合于储备结构为次序储备或链式储备的线性表；（）四.应用题 （本小题共 5 小题，每道题 6 分，共 30 分）1. 下面为对二叉树进行操作的算法，其功能为（ 6 分）Void unknown(Btree BT)Btree p=BT、temp; If(p.=NULL) temp=p->lchild;p->lchild=p->rchild; p->rchid=temp; unknown(p->lchild);unknown(p->rchild);2. 请写出如图4.1 所示二叉树的先序遍历序列.中序遍历序列和后序遍历序列；（6 分）ABEC学习资料FD G第 6 页，共 11 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -学习资料收集于网络，仅供参考图 4.1 二叉树3已知如图4.2 所示的有向图，请给出： （共 6 分） 每个顶点的入度和出度； （ 2 分）图 4.2 有向图 邻接矩阵；（ 4 分）4. 要求用普里姆算法画出如图4.3所示无向网的最小生成树，假设从 a 顶点动身构造最小生成树，写出各条边加入生成树的次序（用权值表示）；（ 6 分）图 4.3 无向网5. 以下算法的运行结果为（栈的元素类型为char ） (6 分) void main() stack S;char x= a、y= b; initstack(S);push(S、x); push(S、y);printf(“ %c” 、x);printf(“ %c” 、y);pop(S、x); pop(S、y);printf(“ %c” 、x);printf(“ %c” 、y);学习资料第 7 页，共 11 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -学习资料收集于网络，仅供参考五.算法设计题 （本大题共 1 小题，每题 10 分，共 10 分）1. 已知查找表的数据元素类型如下：Typedef struct Rectypeintnum; char name8;Rectype;假设查找表中有n 个记录，并且为采纳次序储备TypedefRectypeSqlist100;要求：（ 1）写出对给定值K 进行从前端开头次序查找的算法和main 函数；（ 2）次序查找算法的函数头部为“intsearch(SqlistR、intn、intK) “（ 3）在 main 函数中建立该查找表.调用次序查找算法，并输出查找结果；学习资料第 8 页，共 11 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -学习资料收集于网络，仅供参考 数据结构（A 卷）试题标准答案及评分标准一.单项挑选题（本大题共15 小题，每道题2 分，共计30 分）1.B2.B3.C4.A5.A6.B7.C8.B9.B10.C11.A12.B13.D14.D15.C二.填空题（本大题共10 个空，每空2 分，共计20 分）1. 对象2.q->next=s、s->net=p3. 数据4. （ b、c、d ）k5.2 -16.v1、v3、v4、v6、v2、v5、v77.n-18. 邻接矩阵，邻接表（不分先后）三.判定题（本大题共10 小题，每道题1 分，共计 10 分）1.2.3.4.5.6.7. 8. 9.10.四.应用题（本大题共5 小题，每道题6 分，共 30 分）1利用栈将队列中的元素逆置（6 分）2.（ 6 分）ABECFD3.（ 6 分）其中：哈夫曼树（2.5 分）G哈夫曼编码（3.5 分） a:10b:110c:111d:0111e:00f:0110g:0114. （ 6 分）其中深度优先搜寻序列为v1、v2、v3、v6、v5、v4 (3分 )广度优先搜寻序列为v1、v2、v5、v4、v3、v6 (3分)5.（ 6 分）五.算法设计题 （ 10 分）intbinsearch(SqlistR、intn、intK)（ 5 分） int low=0、high=n-1、mid;while(low<=high)mid=(low+high)/2;if(Rmid.key=K)return mid;else if(Rmid.key>K)low=mid+1; elsehigh=mid-1;return -1; main() (5 分) SqlistR ; int n、k、i;scanf(“%d”、&n);for(i=0;i<n;i+)/*按 num 升序输入数据 */scanf( “%dn ”、&Ri.num);gets(Ri.name); scanf(“%d”、&k);i=binsearch(R、n、k);if(i=-1) printf(“nof found. ”);elseprintf( “found. ”);荆楚理工学院成人高等训练期末考试学习资料第 9 页，共 11 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -学习资料收集于网络，仅供参考 数据结构（B 卷）试题标准答案及评分标准一.单项挑选题（本大题共15 小题，每道题2 分，共计30 分）1.A2.B3.A4.A5.C6.C7.A8.B9.A10.B11.A12.A13.C14.C15.C二.填空题（本大题共10 个空，每空2 分，共计20 分）1. 储备（物理）2.q=p->next、p->next=q->next3.a4. 长度5.86. 拓扑排序7. 深度优先搜寻遍历，广度优先搜寻遍历（不分先后）8.6三.判定题（本大题共10 小题，每道题1 分，共计 10 分）1.2.3.4.5.6.7. 8.9. 10.四.应用题（本大题共5 小题，每道题6 分，共 30 分） 1（ 6 分）将二叉树中的左右子树交换2. （ 6 分）其中先序遍历序列为ABEFCD（G 2 分）中序遍历序列为EFBCGD（A 2 分）后序遍历序列为FEGDCB（A 2 分） 3. （ 2 分 4 分、 共 6 分）4.（ 6 分） ( 最小生成树4 分，次序 2 分，共 6 分)次序： 1、4、3、9、235.abba（6 分）五.算法设计题 （ 10 分）intsearch(SqlistR、intn、intK) (5 分) int i;for(i=0;i<n&&Ri.key.=K;i+);return i; main()（ 5 分） SqlistR ; int n、k、i;scanf(“%d”、&n);for(i=0;i<n;i+)scanf( “%dn ”、&Ri.num);gets(Ri.name); scanf(“%d”、&k);i=search(R、n、k);if(i>=n) printf(“nof found. ”); elseprintf( “found. ”);学习资料第 10 页，共 11 页 - - - - - - - - - -精品word 可编辑资料 - - - - - - - - - - - - -学习资料收集于网络，仅供参考学习资料第 11 页，共 11 页 - - - - - - - - - -