数据结构期末测试题及答案

1、数据结构期末测试题及答案1线性表是具有n个( )的有限序列。 A、数据表B、字符C、数据元素(正确答案)D、数据项2在线性表中,除开始元素外,每个元素( )。 A、只有唯一的前趋元素(正确答案)B、只有唯一的后继元素C、有多个前趋元素D、有多个后继元素3下述( )是顺序存储结构的优点。 A、存储密度大(正确答案)B、插入运算方便C、删除运算方便D、方便地运用于各种逻辑结构的存储表示4线性表的顺序存储结构是一种( )。 A、随机存取的存储结构(正确答案)B、顺序存取的存储结构C、索引存取的存储结构D、散列存取的存储结构5一个顺序表所占用的存储空间大小与( )无关。 A、表的长度B、元素的存放顺序

2、(正确答案)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(Ii=MaxSizeC、Q.front=(Q.rear+1) % MaxSize(正确答案)D、Q.rear=(Q.front+1) % MaxSize9用链式存储方式的队列进行删除操作时需要( )。 A

3、、仅修改尾指针B、仅修改头指针C、头尾指针可能都要修改(正确答案)D、头尾指针都要修改10在一个链队列中, 假设队头指针为front,队尾指针为rear,x所指向的元素需要入队,则需要执行的操作为( )。 A、front=x, front=front.nextB、x.next=front.next,front=xC、rear.next=x, rear=xD、rear.next=x,x.next=null,rear=x(正确答案)11数组Qn用来表示一个循环队列,f为当前队列头元素的前一位置,r为队尾元素的位置,假定队列中元素的个数小于n,计算队列中元素的公式为 A、r-fB、(n+f-r)%

4、nC、n+r-fD、(n+r-f)% n(正确答案)12【判断题】栈和队列是一种非线性数据结构。_13【判断题】栈和队列的存储方式既可是顺序方式,也可是链接方式_14【判断题】队是一种插入与删除操作分别在表的两端进行的线性表,是一种先进后出型结构。 栈和队列综合应用已完成(正确答案)1下列关于栈的叙述中,错误的是( )。I. 采用非递归方式重写递归程序时必须使用栈 II. 函数调用时,系统要用栈保存必要的信息 III.只要确定了入栈次序,即可确定出栈次序 IV.栈是一种受限的线性表,允许在其两端进行操作 A、仅IB、仅I、II、IIIC、仅I、III、IV(正确答案)D、仅II、III、IV2

5、若栈S1中保存整数,栈S2中保存运算符,函数F()依次执行下述各步操作:_1)从S1中依次弹出两个操作数a和b. _2)从S2中弹出一个运算符op._3)执行相应的运算b op a._4)将运算结果压入S1中假定S1中的操作数依次是5, 8,3,2(2在栈顶),s2中的运算符依次是 、-、+(+在栈顶)。调用3次F()后,s1栈顶保存的值是( )。 A、-15B、15(正确答案)C、-20D、203已知循环队列存储在一维数组A0.n-1中, 且队列非空时front和rear分别指向队头元素和队尾元素。若初始时队列为空,且要 求第一个进入队列的元素存储在A0处,则初始时front和rear的值分

6、别是( )。 A、0 , 0B、0 , n-1(正确答案)C、n-1 , 0D、n-1 , n-14循环队列放在一维教组A0. M-1中，end1指向队头元素，end2指向队尾元素的后一个位置，假设队列两端均可进行入队和出队操作，队列中最多能容的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=(end

7、2+1)mod M 队满:end2=(end1+1)mod (M-1)5现有队列Q与栈S,初始时Q中的元素依次是1,2,3,4,5,6(1在队头),S为空。若仅允许下列3种操作: 出队并输出出队元素: 出队并将出队元素入栈; 出栈并输出出栈元素。 则不能得到的输出序列是( )。 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_”作为栈

8、的输入时,输出长度为3,且可用做C语言标识符的序列有( )个。 A、4B、5C、3(正确答案)D、68元素a,b,c,d,e依次进入初始为空的栈中,若元素进栈后可停留、可出栈,直到所有元素都出栈,则在所有可能的出栈序列中,以元素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,

9、且7个元素出队的顺序是bdcfeag,则栈S的容量至少是( )。 A、1B、2C、3(正确答案)D、411一个栈的输入序列为1,2,3,.,n ,输出序列的第一个元素是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+;(正

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

11、、度为4的树来说,( ) A、树的高度至多是n-3(正确答案)B、树的高度至多是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、既不是树也不是二叉树(正确答案)树

12、与二叉树测试（2）二叉树基础和性质已完成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中的叶子数为( ) A、4B、6C

13、、7D、8(正确答案)7在一棵度为4的树T中,若有20个度为4的结点,10 个度为3的结点,1个度为2的结点,10个度为1的结点,则树T的叶子结点个数是( )。 A、41B、82(正确答案)C、113D、1228已知一棵完全二叉树的第6层(设根为第1层)有8个叶子结点,则该完全二叉树的结点个数最多是( )。 A、39B、52C、111(正确答案)D、1199已知一棵完全二叉树的第6层(设根为第1层)有8个叶子结点,则该完全二叉树的结点个数最少是( )。 A、39(正确答案)B、52C、111D、11910、以下说法中,正确的是( )。 A、在完全二叉树中,叶子结点的双亲的左兄弟(若存在)一定不

14、是叶子结点(正确答案)B、任何一棵二叉树,叶子结点个数为度为2的结点数减1,即n0=n2-1C、完全二叉树不适合顺序存储结构,只有满二叉树适合顺序存储结构D、结点按完全二叉树层序编号的二叉树中,第i个结点的左孩子的编号为2i11具有10个叶子结点的二叉树中有( )个度为2的结点。 A、8B、9(正确答案)C、10D、1112假设一棵二叉树的结点个数为50, 则它的最小高度是( )。 A、4B、5C、6(正确答案)D、713设二叉树有2n个结点,且m n，则不可能存在( )的结点。 A、n个度为0B、2m个度为0C、2m个度为1(正确答案)D、2m个度为214设二叉树只有度为0和2的结点,其结点个数为15,则该二叉树的最大深度为( )。 A、4B、5C、8(正确答案)D、916若一棵深度为6的完全二叉树的第6层有3个叶子结点,则该二叉树共有( )个叶子结点。 A、17(正确答案)B、18C、19D、2017若一棵二叉树有126个结点,在第7层(根结点在