2022年数据结构(第二版) AB卷2试卷（试题）及答案.pdf

试卷三 一、单项选择题(在下列每小题四个备选答案中选出一个正确答案，并将其字母 标号填入题干的括号内。每小题2分，共30分) 1．数据结构可以形式化地定义为（S，△），其中S指某种逻辑结构，△是指（ ） A.S上的算法 B.S的存储结构 C.在S上的一个基本运算集 D.在S上的所有数据元素 2．下列说法正确的是（ ） A.线性表的逻辑顺序与存储顺序总是一致的 B.线性表的链式存储结构中，要求内存中可用的存储单元可以是连续的，也可 以不连续 C.线性表的线性存储结构优于链式存储结构 D.每种数据结构都具有插入、删除和查找三种基本运算 3．稀疏矩阵一般采用（ ）方法压缩存储。 A.三维数组 B.单链表 C.三元组表 D.散列表 4.在一个单链表中，若p↑结点不是最后结点，在p↑之后插入s↑结点，则实行( )。 A. s↑.next:=p ；p↑.next=s; B. s↑.next:=p↑.next;p↑.next:=s ； C. s↑.next:=p↑.next;p:=s; D. p↑.next:=s;s↑.next=p; 5.某个向量第一元素的存储地址为100，每个元素的长度为2，则第五个元素的地 址是( )。 A.110 B.108 C.100 D.120 6.下面的二叉树中，( )不是完全二叉树。 7.一组记录的排序码为(47、78、61、33、39、80)，则利用堆排序的方法建立的初始 堆为( )。 A.78 、47、61、33、39、80 B.80、78、61、33、39、47 C.80、78、61、47、39、33 D.80、61、78、39、47、33 8.假设left和right为双向链表中指向直接前趋结点和直接后继结点的指针域，现要 把一个指针s所指的新结点作为非空双链表中q所指地点( 中间结点)的直接后继 结点插入到该双向链表中，则下列算法段能正确完成上述要求的是( ) A.q-right=s; s-left=q; q-right-left=s; s-right=q-right; B.s-left=q; q-right=s; q-right-left=s; s-right=q-right; C.s-left=q; s-right=q-right; q-right-left=s; q-right=s; D.以上都不对 9. 由下列三棵树组成转的森林换成一棵二叉树为( ) 10. for （i=0 ；im ；i++） for （j=0 ；jt ；j++ ） c ［i］［j ］=0 ； for （i=0 ；im ；i++） for （j=0 ；jt ；j++ ） for （k=0 ；kn ；k++） c ［i］［j ］=c ［i］［j ］+a ［i］［k］*b ［k］［j ］； 上列程序的时间复杂度为（ ） A.O （m+n×t） B.O （m+n+t） C.O （m×n×t） D.O （m×t+n） 11.设循环队列的元素存放在一维数组Q ［0 ‥30］中，队列非空时，front指示队头 元素的前一个位置，rear指示队尾元素。如果队列中元素的个数为11，front的值 为25，则rear应指向的元素是（ ） A.Q ［4］