长安大学软件工程专业大二2017年数据结构期末测试题

1、长安大学软件工程专业大二2017年数据结构期末测试题1线性表是具有n个( )的有限序列。 单选题 *A、数据表B、字符C、数据元素(正确答案)D、数据项2在线性表中,除开始元素外,每个元素( )。 单选题 *A、只有唯一的前趋元素(正确答案)B、只有唯一的后继元素C、有多个前趋元素D、有多个后继元素3下述( )是顺序存储结构的优点。 单选题 *A、存储密度大(正确答案)B、插入运算方便C、删除运算方便D、方便地运用于各种逻辑结构的存储表示4线性表的顺序存储结构是一种( )。 单选题 *A、随机存取的存储结构(正确答案)B、顺序存取的存储结构C、索引存取的存储结构D、散列存取的存储结构5一个顺序

2、表所占用的存储空间大小与( )无关。 单选题 *A、表的长度B、元素的存放顺序(正确答案)C、元素的类型D、元素中各字段的类型6在n个元素的线性表的数组表示中,时间复杂度为0(1)的操作是( )。I. 访问第i(1in)个结点和求第i (2in)个结点的直接前驱II. 在最后一个结点后插入一个新的结点 III.删除第1个结点IV. 在第i(1in)个结点后插入一个结点 单选题 *A、IB、II、IIIC、I、II(正确答案)D、I、II、III7在一个长度为n的顺序表中删除第i(I<i<n)个元素时,需向前移动( )个元素。 单选题 *A、nB、i-IC、n-i(正确答案)D、n-

3、i+18对于顺序表,访问第i个位置的元素和在第i个位置插入一个元素的时间复杂度为( )。 单选题 *A、O(n), O(n)B、O(n),0(1)C、0(1), O(n)(正确答案)D、0(1), 0(1)单链表1对于一个线性表既要求能够进行较快速地插入和删除,又要求存储结构能反 映数据之间的逻辑关系,则应该用( )。 单选题 *A、顺序存储方式B、链式存储方式(正确答案)C、散列存储方式D、以上均可以2对于顺序存储的线性表,其算法时间复杂度为0(1)的运算应该是( )。 单选题 *A、将n个元素从小到大排序B、删除第i(1in)个元素C、改变第i(1in)个元素的值(正确答案)D、在第i(1

4、in)个元素后插入一个新元素3设线性表中有2n个元素,( )在单链表上实现要比在顺序表上实现效率更高。 单选题 *A、删除所有值为x的元素(正确答案)B、在最后一个元素的后面插入一个新元素C、顺序输出前k个元素D、交换第i个元素和第2n-i-1个元素的值(i=0, .n-1)4在一个单链表中,已知q所指结点是P所指结点的前驱结点,若在q和p之间插入结点s,则执行( )。 单选题 *A、s.next=p.next; p.next=s;B、p.next=s.next; s.next=p;C、q.next=s; s.next=p;(正确答案)D、p.next=s; s.next=q;5将长度为n的单

5、链表链接在长度为m的单链表后面,其算法的时间复杂度是( )。 单选题 *A、0(1)B、O(n)C、O(m)(正确答案)D、O(n+ m)6单链表中，增加一个头结点的目的是为了( )。 单选题 *A、使单链表至少有一个结点B、标识表结点中首结点的位置C、方便运算的实现(正确答案)D、说明单链表是线性表的链式存储7在一个长度为n的带头结点的单链表h上,设有尾指针r,则执行( )操作与链表的表长有关。 单选题 *A、删除单链表中的第一个元素B、删除单链表中最后一个元素(正确答案)C、在单链表第一个元素前插入一个新元素D、在单链表最后一个元素后插入一个新元素8对于一个头指针为head的带头结点的单链

6、表,判定该表为空表的条件是( )。 单选题 *A、head= =nullB、head.next= =null(正确答案)C、head.next=headD、head!=null9对于一个头指针为head不带头结点的单链表,判定空表的条件为( )。 单选题 *A、head= =null(正确答案)B、head.next= =nullC、head.next=headD、head!=nullL10已知表头元素为c的单链表在内存中的存储状态如下表所示。 现将f存放于1014H处并插入表,若f在逻辑上位于a和e之间,则a,e,f的“链接地址”依次是( ) 单选题 *A、1010H,1014H,1004H

7、B、1010H,1004H,1014HC、1014H,1010H,1004HD、1014H,1004H,1010H(正确答案)11从一个具有n个结点的有序单链表中查找其值大于x的结点时,在查找成功的情况下,需要平均比较( )个结点。 单选题 *A、nB、n/2C、(n-1)/2D、(n+1)/2(正确答案)1若线性表最常用的操作是存取第i个元素及其前驱和后继元素的值,为了提高效率,应采用( )的存储方式。 单选题 *A、单链表B、双向链表C、单循环链表D、顺序表(正确答案)2一个线性表最常用的操作是存取任一指定序号的元素并在最后进行插入删除操作,则利用( )存储方式可以节省时间。 单选题 *A

8、、顺序表(正确答案)B、单链表C、双向链表D、单循环链表3设线性表有n个元素,严格说来,以下操作中,( )在顺序表上实现要比链表上实现的效率高。I. 输出第i(1in)个元素值II. 交换第3个元素与第4个元素的值III.顺序输出这n个元素的值 单选题 *A、IB、I、IIIC、I、II(正确答案)D、II、III4链式存储的存储结构所占存储空间( )。 单选题 *A、分为两部分,一部分存放结点值,另一部分存放表示结点间关系的指针(正确答案)B、只有一部分,存放结点值C、只有一部分,存储表示结点间关系的指针D、分两部分,一部分存放结点值,另一部分存放结点所占单元数5线性表若采用链式存储结构，要

9、求内存中可用存储单元的地址( ) 单选题 *A、必须是连续的B、部分地址必须是连续的C、一定是不连续的D、连续或不连续都可以(正确答案)6线性表L在(_ )情况下适用于使用链式结构实现。 单选题 *A、需经常修改L中的结点值B、需不断对L进行删除、插入(正确答案)C、L中含有大量的结点D、L中结点结构复杂7单链表的存储密度( ) 单选题 *A、大于1B、等于1C、小于1(正确答案)D、不能确定8在一个长度为n的顺序表中,在第i个元素( 1in+1)之前插人一个新元素时需移动( )个元素。 单选题 *A、n-iB、n-i+1(正确答案)C、n-i- 1D、i9线性表L=(a1, a2,., an

10、),下列陈述正确的是( )。 单选题 *A、每个元素都有一个直接前驱和-一个直接后继B、线性表中至少有一个元素C、表中诸元素的排列必须是由小到大或由大到小D、除第一个和最后一个元素外,其余每个元素都有一个且仅有一个直接前驱和直(正确答案)10、以下陈述错误的是( ) 单选题 *A、求表长、定位这两种运算在采用顺序存储结构时实现的效率不比采用链式存储结构时实现的效率低B、顺序存储的线性表可以随机存取C、由于顺序存储要求连续的存储区域,所以在存储管理上不够灵活(正确答案)D、线性表的链式存储结构优于顺序存储结构11在单链表中,要将s所指结点插入到p所指结点之后,其语句应为( ) 单选题 *A、s.

11、next=p; p.next=s;B、p.next = s; s.next = p.next;C、s.next = p.next; p.next = s.next;D、s.next = p.next; p.next= s;(正确答案)14【判断题】链表的每个结点中都恰好包含一个指针 填空题_15【判断题】链表的物理存储结构具有同链表一样的顺序 填空题_16【判断题】 单选题 *链表的删除算法很简单,因为当删除链中某个结点后,计算机会自动将后续各个单元向前移动。(正确答案)17【判断题】顺序表结构适宜于进行顺序存取,而链表适宜于进行随机存取 填空题_18【判断题】顺序存储方式的优点是存储密度大,

12、且插入、删除运算效率高。 填空题_19【判断题】线性表在物理存储空间中也一定是连续的 填空题_20【判断题】线性表在顺序存储时,逻辑上相邻的元素在存储的物理位置次序上一定相邻。 填空题_21【判断题】线性表的逻辑顺序与存储顺序总是一致的。 填空题_22【简答题】 单选题 *试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好?(正确答案)链式存储结构:(1)占用额外的空间以存储指针(浪费空间)(2)存取某个元素速度慢顺序存储结构:(1)空间利用率高(2)存取某个元素速度快23【简答题】 单选题 *描述头指针、头结点概念的区别，并简要说明在单链表中设置头结点的作用是什么?(正确

13、答案)首元结点是指链表中存储线性表中第一个数据元素a1的结点。为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，该结点的数据域中不存储线性表的数据元素，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。头指针是指向链表中第一个结点。1栈是( )。 单选题 *A、顺序存储的线性结构B、链式存储的非线性结构C、限制存取点的线性结构(正确答案)D、限制存储点的非线性结构2( )不是栈的基本操作。 单选题 *A、删除栈顶元素B、删除栈底元素(正确答案)C、判断栈是否为空D、将栈置为空栈3栈中元素的进出原则是( )。 单选题 *A、先进先出B、后进先出(正确

14、答案)C、栈空则进D、栈满则出4若一个栈用数组data1.n存储，初始栈顶指针top为n+1，则以下元素x进栈的正确操作是( )。 单选题 *A、top+;datatop=x;B、top-;datatop=x;(正确答案)C、datatop=x;top+;D、datatop=x;top-;5对一个初始为空的栈s执行操作 push(s, 5),push(s, 2), push(s, 4), pop(s, x), getTop(s,x)后,x的值应是( )。 单选题 *A、5B、2(正确答案)C、4D、06、以下有关顺序栈的操作中,正确的是( )。 单选题 *A、n个元素进入一个栈后,它们的出栈顺

15、序一定与进栈顺序相反(一次性进栈完毕后再出栈)(正确答案)B、若一个栈的存储空间为Sn,则对栈的进栈和出栈操作最多只能执行n次C、栈是一种对进栈和出栈操作的次序做了限制的线性表D、空栈没有栈顶指针7在实现顺序栈的操作时,在进栈之前应先判断栈是否( )。 单选题 *A、空B、满(正确答案)C、上溢D、下溢8在实现顺序栈的操作时,在出栈之前应先判断栈是否( )。 单选题 *A、空(正确答案)B、满C、上溢D、下溢9假定利用数组an顺序存储一个栈, 用top表示栈顶指针,用top=-1表示栈空,并已知栈未满,当元素 x进栈时所执行的操作为( ) 单选题 *A、a-top=xB、atop-=xC、a+

16、top=x(正确答案)D、atop+=x10设有一个空栈,栈顶指针为1000H,每个元素需要一个存储单元,执行Push、Push、Pop、Push、Pop、Push、Pop、Push操作后,栈顶指针的值为( )。 单选题 *A、1002H(正确答案)B、1003HC、1004HD、1005H11经过以下栈的操作后,变量x的值为( )。 InitStack(st); Push(st,a); Push(st,b); Pop(st, x); Top(st, x); 单选题 *A、a(正确答案)B、bC、NULLD、FALSE12 3个不同元素依次进栈,能得到( )种不同的出栈序列。 单选题 *A、4

17、B、5(正确答案)C、6D、713设a,b,c,d,e,f以所给的次序进栈,若在进栈操作时,允许出栈操作,则下面得不到的序列为( )。 单选题 *A、fedcbaB、bcafedC、dcefbaD、cabdef(正确答案)14用S表示进栈操作,用X表示出栈操作,若元素的进栈顺序是1234、为了得到1342的出栈顺序,相应的S和X的操作序列为( )。 单选题 *A、SXSXSSXXB、SSSXXSXXC、SXSSXXSXD、SXSSXSXX(正确答案)15【判断题】在表结构中最常用的是线性表,栈和队列不太常用。 填空题_16【判断题】栈是一种对所有插入、删除操作限于在表的一端进行的线性表,是一种

18、后进先出型结构。 填空题_17【判断题】一个栈的输入序列是12345,则栈的输出序列不可能是12345。 单选题 *队列基础测试已完成(正确答案)1栈和队列的主要区别在于( )。 单选题 *A、它们的逻辑结构不一样B、它们的存储结构不一样C、所包含的元素不一样D、插入、删除操作的限定不一样(正确答案)2队列的“先进先出”特性是指( )。I.最后插入队列中的元素总是最后被删除 II.当同时进行插入、删除操作时,总是插入操作优先入 III.每当有删除操作时,总要先做一次插入操作 IV.每次从队列中删除的总是最早插入的元素 单选题 *A、IB、I和IV(正确答案)C、II和IIID、IV3允许对队列

19、进行的操作有( )。 单选题 *A、对队列中的元素排序B、取出最近进队的元素C、在队列元素之间插入元素D、删除队头元素(正确答案)4一个队列的入队顺序是1,2,3.4.则出队的输出顺序是( )。 单选题 *A、4,3,2,1(正确答案)B、1,2,3,4C、1,4,3,2D、3,2,4,15循环队列存储在数组A0.n中,入队时的操作为( )。 单选题 *A、rear=rear+1B、rear=(rear+1) mod (n-1)C、rear= (rear+1) mod nD、rear=(rear+1) mod (n+1)(正确答案)6已知循环队列的存储空间为数组A21, front指向队头元素

20、的前一个位置,rear指向队尾元素,假设当前front和rear的值分别为8和3,则该队列的长度为( ) 单选题 *A、5B、6C、16(正确答案)D、177若用数组A0.5来实现循环队列,且当前rear和front的值分别为1和5,当从队列中删除一个元素,再加入两个元素后,rear和front的值分别为( )。 单选题 *A、3和4B、3和0(正确答案)C、5和0D、5和18假设一个循环队列QMaxsize的队头指针为front, 队尾指针为rear,队列的最大容量为MaxSize,除此之外,该队列再没有其他数据成员,则判断该队的列满条件是( )。 单选题 *A、Q.front=Q.rear

21、B、Q.front+Q.rear>=MaxSizeC、Q.front=(Q.rear+1) % MaxSize(正确答案)D、Q.rear=(Q.front+1) % MaxSize9用链式存储方式的队列进行删除操作时需要( )。 单选题 *A、仅修改尾指针B、仅修改头指针C、头尾指针可能都要修改(正确答案)D、头尾指针都要修改10在一个链队列中, 假设队头指针为front,队尾指针为rear,x所指向的元素需要入队,则需要执行的操作为( )。 单选题 *A、front=x, front=front.nextB、x.next=front.next,front=xC、rear.next=x

22、, rear=xD、rear.next=x,x.next=null,rear=x(正确答案)11数组Qn用来表示一个循环队列,f为当前队列头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数小于n,计算队列中元素的公式为 单选题 *A、r-fB、(n+f-r)% nC、n+r-fD、(n+r-f)% n(正确答案)12【判断题】栈和队列是一种非线性数据结构。 填空题_13【判断题】栈和队列的存储方式既可是顺序方式,也可是链接方式 填空题_14【判断题】队是一种插入与删除操作分别在表的两端进行的线性表,是一种先进后出型结构。 单选题 *栈和队列综合应用已完成(正确答案)1下列关于栈的叙述中

23、,错误的是( )。I. 采用非递归方式重写递归程序时必须使用栈 II. 函数调用时,系统要用栈保存必要的信息 III.只要确定了入栈次序,即可确定出栈次序 IV.栈是一种受限的线性表,允许在其两端进行操作 单选题 *A、仅IB、仅I、II、IIIC、仅I、III、IV(正确答案)D、仅II、III、IV2若栈S1中保存整数,栈S2中保存运算符,函数F()依次执行下述各步操作: 填空题_1)从S1中依次弹出两个操作数a和b. 填空题 *_2)从S2中弹出一个运算符op. 填空题_3)执行相应的运算b op a. 填空题_4)将运算结果压入S1中假定S1中的操作数依次是5, 8,3,2(2在栈顶)

24、,s2中的运算符依次是 *、-、+(+在栈顶)。调用3次F()后,s1栈顶保存的值是( )。 单选题 *A、-15B、15(正确答案)C、-20D、203已知循环队列存储在一维数组A0.n-1中, 且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空,且要 求第一个进入队列的元素存储在A0处,则初始时front和rear的值分别是( )。 单选题 *A、0 , 0B、0 , n-1(正确答案)C、n-1 , 0D、n-1 , n-14循环队列放在一维教组A0. M-1中，end1指向队头元素，end2指向队尾元素的后一个位置，假设队列两端均可进行入队和出队操作，队列中最

25、多能容的M-1个元素。初始时为空，下列判断队空和队满的条件中，正确的是( )。 单选题 *A、队空:end1=end2 队满:end1=(end2+1)mod M(正确答案)B、队空:end1=end2 队满:end2=(end1+1)mod (M-1)C、队空:end2=(end1+1)mod M 队满:end1=(end2+1)mod MD、队空:end1=(end2+1)mod M 队满:end2=(end1+1)mod (M-1)5现有队列Q与栈S,初始时Q中的元素依次是1,2,3,4,5,6(1在队头),S为空。若仅允许下列3种操作: 出队并输出出队元素: 出队并将出队元素入栈; 出

26、栈并输出出栈元素。 则不能得到的输出序列是( )。 单选题 *A、1,2,5,6,4,3B、2,3,4,5,6,1C、3,4,5,6,1,2(正确答案)D、6,5,4,3,2,16若已知一个栈的入栈序列是1,2,3,n,其输出序列为p1,p2,p3,pn,若p1=n,则pi为 单选题 *A、iB、n-iC、n-i+1(正确答案)D、不确定7设栈的初始状态为空, 当字符序列 “n1_”作为栈的输入时,输出长度为3,且可用做C语言标识符的序列有( )个。 单选题 *A、4B、5C、3(正确答案)D、68元素a,b,c,d,e依次进入初始为空的栈中,若元素进栈后可停留、可出栈,直到所有元素都出栈,则

27、在所有可能的出栈序列中,以元素d开头的序列个数是( )。 单选题 *A 3B 4(正确答案)C 5D 69若元素a,b,c,d,e,f依次进栈,允许进栈、退栈操作交替 进行,但不允许连续3次进行退栈操作,不可能得到的出栈序列是( )。 单选题 *A、dcebfaB、cbdaefC、bcaefdD、afedcb(正确答案)10设栈S和队列Q的初始状态均为空,元素abcdefg依次进入栈S。若每个元素出栈后立即进入队列Q,且7个元素出队的顺序是bdcfeag,则栈S的容量至少是( )。 单选题 *A、1B、2C、3(正确答案)D、411一个栈的输入序列为1,2,3,.,n ,输出序列的第一个元素是

28、i,则第j个输出元素是( )。 单选题 *A、i-j-1B、i-jC、j-i+1D、不确定(正确答案)12某栈的输入序列为a,b,c,d, 下面的4个序列中,不可能为其输出序列的是( )。 单选题 *A、a,b,c,dB、c,b,d,aC、d,c,a,b(正确答案)D、a,c,b,d13若一个栈用该数组data1.n存储，初始栈顶指针top为1，则以下元素x进栈的正确操作是。 单选题 *A、top+;datatop=x;B、datatop=x;top+;(正确答案)C、top-;datatop=x;D、datatop=x;top-;14【判断题】通常使用队列来处理函数或过程的调用。 填空题_1

29、5判断题】栈是实现过程和函数等子程序所必需的结构。 填空题_16【判断题】栈和队列都是限制存取点的线性结构。 填空题_17【判断题】队列逻辑上是一个下端和上端既能增加又能减少的线性表。 填空题_18【判断题】循环队列也存在空间溢出问题。 填空题_19【判断题】 单选题 *栈和队列的存储方式，既可以是顺序方式，又可以是链式方式。(正确答案)树与二叉树测试（1）树基础已完成1树最适合用来表示( )的数据。 单选题 *A、有序B、无序C、任意元素之间具有多种联系D、元素之间具有分支层次关系(正确答案)2对于一棵具有n个结点、度为4的树来说,( ) 单选题 *A、树的高度至多是n-3(正确答案)B、树

30、的高度至多是n-4C、第i层上至多有4(i-1)个结点D、至少在某一层上正好有4个结点3一棵有n个结点的树的所有结点的度数之和为( ) 单选题 *A、n-1(正确答案)B、nC、n+1D、2n4度为4、高度为h的树,( ) 单选题 *A、至少有h+3个结点(正确答案)B、至多有4h-1个结点C、至多有4h个结点D、至少有h+4个结点5假定一棵度为3的树中,结点数为50,则其最小高度为( ) 单选题 *A、3B、4C、5(正确答案)D、66不含任何结点的空树( )。 单选题 *A、是一棵树B、是一棵二叉树C、是一棵树也是一棵二叉树D、既不是树也不是二叉树(正确答案)树与二叉树测试（2）二叉树基础

31、和性质已完成1若一棵完全二叉树有768个结点,则该二叉树中叶子结点的个数是( )。 单选题 *A、257B、258C、384(正确答案)D、3852由3个结点可以构造出多少种不同的二叉树? ( ) 单选题 *A、2B、3C、4D、5(正确答案)3一棵完全二叉树上有1001个结点,其中叶子结点的个数是( )。 单选题 *A、250B、500C、254D、501(正确答案)4一个具有1025个结点的二叉树的高h为( ) 单选题 *A、11B、10C、11至1025之间(正确答案)D、10至1024之间6设树T的度为4,其中度为1,2,3和4的结点个数分别为4,2,1,1 则T中的叶子数为( ) 单选题