试卷代号：

钦州学院2014  年秋季学期  数计学院 期中考试试卷

课程：《数据结构》

注意事项：1. 考前请将密封线内的内容填写清楚。

            2. 所有答案请直接答在试卷上(或答题纸上)。

            3．考试形式：闭卷，

       4. 本试卷共 四 大题，满分100分，考试时间120分钟。

题 号	一	二	三	四	总分
得 分
评卷人

    一、单项选择题（每题2分，共30分）

1、           不是算法所必须具备的特性。

A. 有穷性    B．确切性   C．高效性    D．可行性

 

2、下面说法错误的是_______

（1）算法原地工作的含义是指不需要任何额外的辅助空间

（2）在相同的规模n 下，复杂度O(n)的算法在时间上总是优于复杂度O(2n)的算法

（3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界

（4）同一个算法，实现语言的级别越高，执行效率就越低

A．(1)     B.(1),(2)     C.(1),(4)       D.(3)   

 

3、在一个单链表中，删除指针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

 

4、若一个栈的入栈顺序是1，2，3，4，5，则栈的不可能的输出序列是

A. ｛5，4，3，2，1｝      B. ｛4，5，3，2，1｝

C. ｛4，3，5，1，2｝      D. ｛1，2，3，4，5｝

 

5、在数据结构中，与所使用的计算机无关的是数据的________结构

A 逻辑       B 存储         C 逻辑和存储     D 物理

 

6、已知循环队列的存储空间为数组A[21],front 指向队首元素的前一个位置， rear 指向队尾元素，假设当前front和rear 的值分别为8和3，则该长列的长度为_____________

 A.   5          B.  6             C. 16             D. 17

 

7、设广义表为A=（a, b,(c,d),(e,(f,g),(h,j) ) ) ,则 Head( Tail( Head( Tail( Tail(A))))) 的值为______________

A.   g            B.   d            C.  e          D.   h

 

8、将一棵50个结点的完全二叉树按层编号，由对编号为25的结点X，该结点（    ）

  A. 无左、右孩子                  B. 有左孩子、无右孩子

C. 有右孩子，无左孩子            D. 有左右孩子

 

9、广义表A=(a,(b),(),(c,d,e))的长度为（     ）

A. 4          B.    5          C.  6          D. 7

 

10、设非空单链表的数据域为data，指针域为next，指针p指向单链表中第i个结点，s指向生成的新结点，现将s结点插入到单链表中，使其成为第i个结点，下列算法段能正确完成上述要求的是（     ）

 A. s->next=p->next; p->next=s;      B. p->next=s; s->next=p->next;

 C. s->next=p->next; p->next=s ; 交换p->data和s->data

D.     p=s;s->next=p

E.       

11、对于顺序存储的线性表，访问某个元素和增加一个元素的时间复杂度为____

A．O（n）,O(n)    B. O(n) , O(1)     C. O(1), O(n)     D. O(1), O(1)

 

12、在双向循环链表中，在P指针所指的结点后插入q所指向的新结点，其修改指针的操作是      。

A、p－＞next=q; q－＞prior=p;p－＞next－＞prior=q;q－＞next=q;

B、q－＞prior=p;q－＞next=p－＞next;

p－＞next－＞prior=q;p－＞next=q;

C、p－＞next=q;p－＞next－＞prior=q;q－＞prior=p;q－＞next=p－＞next;

D、q－＞next=p－＞next;q－＞prior=p;p－＞next=q;p－＞next=q;

 

13、一个高度为h的满二叉树共有n个结点，其中有m个叶子结点，则有（     ）

A. n=h+m     B. h+m=2n         C. m=h-1           D. n=2m-1

 

14、在下述结论中，正确的是__________

①只有一个结点的二叉树的度为0; ②二叉树的度为2； ③二叉树的左右子树可任意交换;

④深度为K 的完全二叉树的结点个数小于或等于深度相同的满二叉树。

A．①②③          B．②③④       C．②④        D．①④

 

15、从栈顶指针为top的链栈中删除一个结点，用x保存被删除结点的值，则执行（ ）。
A.  x=top; top=top->next;        B. x=top->data; top=top->next;

C. top=top->next; x=top->data;   D. x=top->data;

 

二、判断题（共20分）

（      ）1、凡是空的单链表都是不含任何结点的。

（      ）2、在单链表中，要取得某个元素，只要知道该元素的指针即可。因此，单链表是随机存取的结构。

（      ）3、对于单链表来说，只有从头结点开始才能扫描表中全部结点。

（      ）4、对循环链表来说，从表中任一结点出发都能通过前后移动操作扫描整个循环链表。

（      ）5、无论是顺序队列还链接队列，插入和删除的时间复杂度都是O（1）。

（      ）6、完全二叉树中每个结点或者没有孩子或者有2个孩子。

（      ）7、若一个广义表的表头为空表，则此广义表也为空表。

（      ）8、二叉树就是结点度为2的树。

（      ）9、度为m的树中至少有一个度为m的结点。

（      ）10、链栈不需要头结点。

 

三、填空题（共20分）

1、在单链表中，p指针所指的结点为最后一个结点的条件是                    。

2、在一棵二叉树中，设度为2的结点有5个，度为1的结点有6个，则叶子结点的个数为                。

3、一棵8层的完全二叉树至少有__   _个结点，拥有100 个结点的完全二叉树的最大层数为______。

4、若用s[1]~s[m]作为顺序栈的存储空间，栈空的标志是栈指针的值等于m+1,则每进行一次出栈操作，需将top的值________;每进行一个进栈操作，需将top的值______。

5、设有一个10对称矩阵A采用压缩存储，a[0][0]的地址为1000，每个元素占2个节，则a[3][6]的存储地址为___________________。

6、n个结点的二叉树中如果有m个树叶，则一个有__________个度为1的结点，______个度为2的结点。

7、数据结构的逻辑结构包括           、           和           三种类型。

8、算术表达式a+b*3+4*（c-d）对应的后缀表达式为_                     _。

9、一个具有n个结点的单链表，在指针p所指结点后插入一个新结点的时候复杂度为_____;在给定值为x的结点后插入一个新结点的时间复杂度为___________

10、有如下递归过程：

void  reverse( int n)

  {

Printf(“%d”,n);

if (n/10 ！=0)

  reverse(n/10);

}

调用语句reverse(582)的结果是___________

四、应用题（共30分，）

1、写出算术表达式3*2^(4+2*2-6*3)-5的求值过程。

 

2、已知一棵二叉树的中序和后序序列如下，

    中序序列：C,B,D,E,A,G,I,H,J,F

    后序序列：C,E,D,B,I,J,H,G,F,A

画出该二叉树并求该二叉树的前序序列。

 

 

 

3、已经知一棵完全二叉树共有862个结点，试求：

（1）树的高度；

（2）叶子结点的个数

（3）单支结点数；

（4）最后一个非终端结点的序号。