复习

一、选择题

1.计算机算法指的是       。

A．计算方法     B. 排序方法        C. 解决问题的步骤序列      D. 调度方法

2. 下面关于算法说法正确的是（    ）

A．算法最终必须由计算机程序实现

B. 为解决某问题的算法同为该问题编写的程序含义是相同的

C. 算法的可行性是指指令不能有二义性          D. 以上几个都是错误的

3．从逻辑上可以把数据结构分为（    ）两大类。

A．动态结构、静态结构       B．顺序结构、链式结构  

C．线性结构、非线性结构     D．初等结构、构造型结构

4．下面程序段中带下划线的语句的执行次数的数量级是(    )。

i=1;

while(i<n) 

{

for(j=1;j<=n;j++)

x=x+1 ;

i=i*2；

}

A． O(2n)       B．O(n)       C．O(n2)         D．O(nlog2n)   

5．以下数据结构中，（   A ）是非线性数据结构

A．树        B．字符串       C．队           D．栈

6. 算法分析的两个主要方面是（D）

  A. 数据复杂性和程序复杂性        B. 正确性和简明性

  C. 可读性和健壮性                D.空间复杂度和时间复杂度

7．下面关于线性表的叙述中，错误的是哪一个？（ B   ）

A．线性表采用顺序存储，必须占用一片连续的存储单元。

B．线性表采用顺序存储，便于进行插入和删除操作。

C．线性表采用链接存储，不必占用一片连续的存储单元。

D．线性表采用链接存储，便于插入和删除操作。

8．若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（  A  ）存储方式最节省时间。

A．顺序表      B．双链表        C．带头结点的双循环链表     D．单循环链表

9．某线性表中最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（   D ）存储方式最节省运算时间。

A．单链表     B．仅有头指针的单循环链表     C．双链表       D．仅有尾指针的单循环链表

10. 对于顺序存储的线性表，访问结点和增加、删除结点的时间复杂度为（  C  ）。

A．O(n)  O(n)      B. O(n)  O(1)       C. O(1)  O(n)        D. O(1) O(1)

11．非空的循环单链表head的尾结点p满足（   A  ）。

A．p.next = head     B．p.next = null      C．p = NULL        D．p= head

12．完成在双循环链表结点p之后插入s的操作是（  ?  ）.

A． p.next = s; s.prior = p; p.next.prev = s ; s.next = p.next;

B． p.next. prev = s; p.next = s; s. prev = p; s.next = p.next;

C． s.prev = p; s.next = p.next; p.next = s; p.next.prior = s ;

D． s.prev = p; s.next = p.next; p.next.prev = s ; p.next = s;

13．对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（B    ）

A．head == null  B．head.next == null    C．head.next == head   D．head != null

14. 一个栈的输入序列为123…n，若输出序列的第一个元素是n，输出第i（1<=i<=n）个元素是（ A ）。

A. 不确定          B. n-i+1          C.  i           D. n-i

15. 有六个元素6，5，4，3，2，1 的顺序进栈，问下列哪一个不是合法的出栈序列？（  ）

A. 5 4 3 6 1 2     B. 4 5 3 1 2 6     C. 3 4 6 5 2 1    D. 2 3 4 1 5 6 

16. 一个递归算法必须包括（   B ）。

A. 递归部分      B. 终止条件和递归部分     C. 迭代部分      D.终止条件和迭代部分

17. 表达式a*(b+c)-d的后缀表达式是( B )。

A．abcd*+-     B. abc+*d-    C. abc*+d-     D. -+*abcd

18. 用链接方式存储的队列，在进行删除运算时（ D   ）。

A. 仅修改头指针   B. 仅修改尾指针    C. 头、尾指针都要修改    D. 头、尾指针可能都要修改

19. 循环队列A[M]存放其元素值，用front和rear分别表示队头和队尾，则当前队列中的元素数是( A )。

A. (rear-front+m)%M              B. front-rear   

C. rear-front                    D. (front-rear+m)%M 

20. 最大容量为n的循环队列，队尾指针是rear，队头是front，则队空的条件是  （  B  ）。

     A. (rear+1) %n= front                   B. rear = front                                                          

C．rear+1 = front                        D. (rear-l) %n= front

21. 栈和队都是（ C    ）

A．顺序存储的线性结构       B. 链式存储的非线性结构

C. 限制存取点的线性结构     D. 限制存取点的非线性结构

22．串的长度是指（ B  ）

A．串中所含不同字母的个数      B．串中所含字符的个数

C．串中所含不同字符的个数      D．串中所含非空格字符的个数

23. 算法必须具备输入、输出和   B     等五个特性

A．可执行性、可移植性、可扩充性    B. 可行性、确定性、有穷性

C. 确定性、有穷性、稳定性           D. 易读性、稳定性、安全性  

24.设有一个10阶的对称矩阵A，采用压缩存储方式其下三角（含主对角元）元素，第一个元素为a11 ，其存储地址为1，每个元素占一个地址空间，则a85的地址为（ B   ）。

A. 13               B. 33                C. 18               D. 40

25. 假设以行序为主序存储二维数组A[100][100]，设每个数据元素占2个存储单元，基地址为10，则A[5][5]的地址为（D ）。    

A. 808              B. 818              C. 1010             D. 1020

27. 有一个100*90的稀疏矩阵，非0元素有10个，设每个整型数占2字节，则用三元组表

示该矩阵时，所需的字节数是（   B ）。

A. 60             B. 66                C. 18000             D. 33    

28. 对稀疏矩阵进行压缩存储目的是（ C   ）。

A．便于进行矩阵运算          B．便于输入和输出   

C．节省存储空间              D．降低运算的时间复杂度

30. 在下述结论中，正确的是（  D  ）

①只有一个结点的二叉树的度为0;  ②二叉树的度为2；  ③二叉树的左右子树可任意交换; ④深度为K的完全二叉树的结点个数小于或等于深度相同的满二叉树。 

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

31．若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点个数是（ B ）

A．9            B．11         C．15       D．不确定 

18. 一个具有1025个结点的二叉树的高h为（  C  ）

A．11          B．10        C．11至1025之间      D．10至1024之间

33．已知一棵二叉树的前序遍历结果为ABCDEF,中序遍历结果为CBAEDF,则后序遍历的结果为（    ）。

A．CBEFDA       B． FEDCBA       C． CBEDFA       D．不定    

34．下面的说法中正确的是（    ）.

（1）任何一棵二叉树的叶子结点在三种遍历中的相对次序不变；

（2）按二叉树定义，具有三个结点的二叉树共有6种。

A．(1)(2)   B．(1)   C．(2)    D．(1)、(2)都错  

35．某二叉树的前序序列和后序序列正好相反，则该二叉树一定是（D）的二叉树。

A．空或只有一个结点    B．任一结点无左子树    C．高度等于其结点数    D．任一结点无右子树

36．一棵二叉树高度为h,所有结点的度或为0，或为2，则这棵二叉树最少有(  B  )结点

A．2h     B．2h-1        C．2h+1         D．h+1   

二、判断题

1. 数据的逻辑结构是指数据的各数据项之间的逻辑关系。( X  ) 

2. 数据项是数据不可分割的最小单位。(    )            

3．数据的物理结构是指数据在计算机内的实际存储形式。(   ) 

4. 数据结构的抽象数据类型的定义与具体实现有关。(    ) 

5．顺序存储方式插入和删除时效率太低，因此它不如链式存储方式好。(    ) 

6. 链表是采用链式存储结构的线性表,进行插入、删除操作时，在链表中比在顺序存储结构中效率高。 (    )                            

8．两个字符串相等的充分必要条件是两串的长度相等且两串中对应位置的字符也相等。(  ) 

9. 广义表的取表尾运算，其结果通常是个表，但有时也可是个单元素值。（    ）

10.矩阵压缩存储后，必会失去随机存取功能。（    ）

11. 一个稀疏矩阵Am×n采用三元组形式表示，  若把三元组中有关行下标与列下标的值互换，并把m和n的值互换，则就完成了Am×n的转置运算。（    ）

三、填空

1．数据的物理结构包括    数据元素   的表示和    关系    的表示。

2. 对于给定的n个元素,可以构造出的逻辑结构有   队列  ，  栈  ，  线性表 ，__树_四种。

3．已知如下程序段

for(i=n; i>=1;i--)                     

{

x=x+1；                      {语句1}

for(j=n; j>=i; j--)                

 y=y+1;                     {语句2}

}

语句1执行的频度为  ；语句2执行的频度为 （8）.

4． (9)  zhan     _是限定仅在表尾进行插入或删除操作的线性表。

5．在作进栈运算时应先判别栈是否_(10)_;在作退栈运算时应先判别栈是否_(11)_；当栈中元素为n个，作进栈运算时发生上溢，则说明该栈的最大容量为_(12)_。

6. 循环队列的引入，目的是为了克服__(13)。                                  

7．用下标0开始的N元数组实现循环队列时，为实现下标变量M加1后在数组有效下标范围内循环，可采用的表达式M= __(14)_____

8．空格串是指由空格字符所组成的字符串，其长度等于___(15)__。 

9．设T和P是两个给定的串，在T中寻找等于P的子串的过程称为_(16)_，又称P为_(17)_。

10．中缀式a+b*3+4*（c-d）对应的前缀式为__(18)_，若a=1，b=2，c=3，d=4，则后缀式db/cc*a-b*+的运算结果为_(19)__。

11．深度为k的完全二叉树至少有___(20)_个结点，至多有___(2) ____个结点。

13．完全二叉树中，结点个数为n，则编号最大的分支结点的编号为___。

四、．程序题

1、假设有一棵二叉树BinTree，（定义如下），试编写程序judge判断它是否为一颗完全二叉树。

class Node{

Object data;

Node left, right, parent;

}

class BinTree{

Node root;

public boolean judge()

{

// 完善此处程序，注意此类中没有任何其他方法定义

}

}

2. 写出具有头指针的单链表List进行原地元素反序的代码。（所谓原地，是指不得创建其他辅助结构）

class Node{

    Object data;

    Node next;

}

Class List{

    Node root;

    public void reverse()

    {

      // 完善此代码

}

}

问答题

谈谈你所理解的数据结构的作用。

2015年1月9日XX大学XX学院考试题