2021年《数据结构》期末试题(A卷)附答案及评分标准.docx

精品word 可编辑资料 - - - - - - - - - - - - - 《数据结构》试题（ A 卷） （考试时间： 90 分钟） 一、单项挑选题 （本大题共 15 小题，每道题 2 分，共 30 分） （每题只有一个选项是正确的 , 将答案填写在括号内，错选、多项不得分） （ ）是组成数据的基本单位，是一个数据整体中相对独立的单元； A．数据 B. 数据元素 C. 数据对象 D. 数据结构 算法运算量的大小称为算法的（ ）； 效率 B.复杂度 C.数据元素之间的关系 D. 数据的储备方法 3.如某线性表最常用的操作是存取任一指定序号的元素和在最终进行插入或删除运算， 就采纳以下（ ）方式最节约时间 ； 链式储备 B. 索引储备 C. 次序储备 D. 散列储备 下述哪一条是次序储备结构的优点？（ ） 储备密度大 B.插入运算便利 C.删除运算便利 D.可便利地用于各种规律结构的储备表示 在一个单链表中，如删除 p 所指结点的后续结点，就执行（ ）； A.p->next=p->next->next B.p->next=p->next C.p=p->next;p->next=p->next->next D.p=p->next->next 带头结点的单链表 head 为空的判定条件是（ ）； head==NULL B.head->next==NULL C.head->next==head D.head.==NULL 非空的循环单链表 head 的尾结点 ( 由 p 所指向 ) 满意（ ）； A.p->head==NULL B.p==NULL C.p->next==head D.p==head 下面关于线性表的表达中，错误选项哪一个？（ ） 线性表采纳次序储备，必需占用一片连续的储备单元； B. 线性表采纳次序储备，便于进行插入和删除操作； C.线性表采纳链式储备，不必占用一片连续的储备单元； D. 线性表采纳链式储备，便于插入和删除操作； 队列操作的原就是（ ）； 后进先出 B. 先进先出 C. 只能进行插入 D. 只能进行删除 10.栈中答应进行插入和删除的一端称为（ ）； 栈首 B. 栈尾 C. 栈顶 D. 栈底 11．假设以数组 A[n] 存放循环队列的元素，其首尾指针分别为 front 和 rear，就当前队列中的元素个数为（ ）； A ．（rear-front+n ） %n B. rear-front+1 C. (front-rear+n)%n D.(rear-front)%n 12.最大容量为 n 的循环队列，队尾指针是 rear，队首指针是 front ，就队空的判定条件是（ ）； A. （ rear+1） %n==front B.rear==front C.rear+1==front D.(rear-1)%n==front 将一个十进制的数转换成二进制的数，可以使用以下一种称为（ ）的数据结构； 图 B. 树 C. 广义表 D. 栈 把一棵树转换为二叉树后，这棵二叉树的外形是（ ）； 有 2 种 B. 有 3 种 C. 有 4 种 D. 唯独的 15.一棵左右子树均不空的二叉树在先序线索化后，其中空链域的个数是（ ）； 1 第 1 页，共 11 页 - - - - - - - - - - 精品word 可编辑资料 - - - - - - - - - - - - - A. 3 B. 2 C. 0 D. 不确定 二、填空题 （本大题共 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 的拓扑序列是 _ ； 有 n 个顶点的连通图至少有 条边； 图的储备常采纳 和 两种方法； 三、判定题 （本大题共 10 小题，每题 1 分， 共 10 分） （请在每道题后面的括号里写出答案，假如正确，请写“√” ，假如错误，请写“×” ） 1. 线性表采纳链表储备时，结点和结点内部的储备空间可以是不连续的； （ ）