数据结构习题集_答案

《数据结构》习题集

第1章 绪论

1、填空题

(1)常见的数据结构有集合、_  线性      __结构，__ 树  _  __结构，__图    __结构等三种。

(2)常见的存储结构有__ 顺序存储    ___结构，__ 链式存储 ___结构等两种。

(3)数据的基本单位是_  数据元素   __，它在计算机中是作为一个整体来处理的。

(4)数据结构中的结构是指数据间的逻辑关系，常见的逻辑结构可分为两大类：__ 线性结构     ____和__   非线性结构    ___。

2、选择题

(1)数据结构是一门研究非数值计算的程序设计中计算机的   A      以及它们之间的    C   和运算等的学科。

（A）数据元素 （B）计算方法 （C）关系 （D） 数据映像

(2)在数据结构中，与所使用的计算机无关的是数据的  A      结构。

（A）逻辑 （B）存储 （C）物理 （D）逻辑与存储

3、应用题

(1)、给出以下算法的时间复杂度.

void fun(int n)

{

    int i=1,k=100;

    while(i    {

        k=k+1;

        i=i+2;

    }

}

上述算法的时间复杂度为：

___ O(n)      _____。

(2)、给出以下算法的时间复杂度.

void fun2(int n)

{

    int i=1,k=100;

    while(i    {

        i=i*10;

        k=k+1;

    }

}

上述算法的时间复杂度为：

___    O(log10n) ______。

第2章 线性表

1、填空题

(1)线性表按照存储结构不同主要有两种实现方式，一种是__顺序  _表，另一种是___  链  ___表。

(2)顺序表采用__随机___访问机制对数据元素进行访问。

(3)若在单链表结点p的后面插入一个新的结点s，则其操作序列为:

1____s->next=p->next _____________；

2___ p->next=s ___________________；

(4)在单向链表中，若要删除某个结点p，一般要找到__p的直接前驱        __结点，才能实现该操作。

2、选择题

(1)将两个各有n个元素的有序表归并成一个有序表，其最少的比较次数是     A     。

(A)n     (B)2n－1   (C)2n    (D)n-1

(2)在单链表中，如果在结点p之后插入一个新结点s，其操作为   A       。

（A）s->next=p->next; p->next=s;

（B）p->next=s; s->next=p->next;

（C）s->next=p; p->next=s->next;

（D）p->next=s; s->next=p;

(3)若长度为n的线性表采用顺序存储结构，在其第i个位置删除一个元素的算法的平均时间复杂度为(     C   )。(1≤i≤n)

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

(4)若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素需要移动的元素个数为(   B    )。(1≤i≤n+1)

(A)．n-i   (B)．n-i+1    (C). I    (D)．n-i-1

3、判断题

(1).线性表中每一个元素都有一个前驱和一个后继。（  错    ）

第3章 栈和队列

1、填空题

(1).栈和队列在本质上都是操作受限的_ 线性表    __________。

(2).栈的操作特点是__  后进先出    _。队列的操作特点是_    先进先出     __。

2、选择题

(1).消除递归不一定需要使用栈，此说法__ A  ____。 

(A). 正确     (B). 错误

(2).一个栈的进展序列为（1，2，3，4），则不可能得到的输出序列是__D__  __。

(A)（1，2，3，4）  (B)（4，3，2，1）

(C)（1，3，4，2）  (D)（3，1，2，4）

(3).用单循环链表表示队列，正确的说法是  B         。

(A)可设一个头指针使入队、出队都方便；

(B)可设一个尾指针使入队、出队都方便；

(C)必须设头尾指针才能使入队、出队都方便；

(D)无论如何,只可能使入队方便。

3、判断题

(1).栈的特点是先进先出。（   错    ）

(2).可以在队列的任意位置插入元素。（  错  ）

(3).递归程序化非递归程序必须用到栈。（    错   ）

(4).如果进栈的序列为（1，2，3，4），则（4，2，3，1）不可能是出栈序列。（ 对  ） 

(5).在用顺序表表示的循环队列中，可以设一个变量L作为标志位来区分队空或队满的条件，当L==0时表示队列为空，等L的值为空间的大小时表示队列为满。（ 对  ）

(6).当用数组做为栈的存储结构时，应把栈顶设在高地址哪一端，这样入栈、出栈不需要移动其他元素。（ 对 ）

(7).当用单链表作为栈的存储结构时，应把栈顶设置链表的头部，这样入栈、出栈不需要移动其他元素。（ 对 ）

第4章 串

1、选择题

(1).串是任意有限个（  D  ）

(A).符号构成的序列    (B).符号构成的集合

(C).字符构成的集合    (D).字符构成的序列

(2).串是一种特殊的线性表，其特殊性体现在（  B  ）

(A). 可以顺序存储

(B). 数据元素是一个字符

(C). 可以连接存储

(D). 数据元素可以是多个字符

(3).以下（ D   ）是“abcd321ABCD”的子串。

(A). abcd        (B). 321AB

(C). “abcABC” (D). “21AB”

(4).两个串相等必有串长度相等且（  B  ）。

(A). 串的各位置字符任意

(B). 串中各位置字符均对应相等

(C). 两个串含有相同的字符

(D). 两个所含字符任意

(5).设有两个串p和q，求q在p中首次出现的位置的运算称作（   B    ）

(A)．连接      (B)．模式匹配    (C)．求子串       (D)．求串长

(6).若串s=“software”，其子串的个数是（ C   ）。

(A). 8        (B). 37

(C). 36        (D). 9

2、判断题

(1).空串和空格串是同一个概念，二者没有区别。（  错    ）

(2).空格串就是由空格组成的串。（  对  ）

第5章 数组和广义表

1、填空题

(1).二维数组在内存中存储可以有两种存储方式，一种是__ 按行__优先存储，一种是   按列       优先存储。

(2).设广义表L＝(（），（），（（））)。则head(L)是（） ；tail(L)是 (（），（（））) ；L的长度是   3       ；L的深度是   3        。

(3).设广义表L＝(（a），（b），（（c））)，则head(L)是__    （a）            __；tail(L)是__  (（b），（（c））)   __。

2、选择题

(1).在C语言中，如果有数组定义  int  A[8][9]；假定每个整型数据占2字节，则数组元素A[4][4]的地址是（  A    ）。

(A). A+80        (B). A+76        (C).A+82        (D).以上都不对

(2).广义表A=（a,b,(c,d),(e,(f,g))）,则下面式子的值为(   D  )；

        Head(Tail(Head(Tail(Tail(A)))))

(A)．（g）        (B).(d)        (C).c        (D).d

3、判断题

(1)在C语言中，数组的存储采取的是行优先的方式。（ 对     ）

(2)广义表在本质上也是线性表，这种说法是错误的。（   对   ）

(3)广义表L的取表头操作是Head(L)，得到的是L中的第一个元素。（ 对  ）

(4)广义表L的取表尾操作是Tail(L)，得到的是L中的除了第一个元素外所有元素构成的表。（ 对  ）

(5)可以用三元组存储法来压缩存储稀疏矩阵。（ 对  ）

(6)已知广义表A=((a,b,c),(d,e,f)),从A中取出原子e的运算是head(tail(head(tail(A))))。(   对   )

第6章 树和二叉树

1、填空题

(1)一棵62个叶结点的完全二叉树,最多有__ 125______个结点。

(2)若规定仅有根的二叉树的高度为1，那么高为h的完全二叉树最多有  2h-1 ___个结点，最少有__2h-1     _个结点。

(3)设只包含有根结点的二叉树的高度为0，则高度为k的二叉树的最大结点数为___  2k+1-1 ____________，最小结点数为__  k+1 _____。

(4)设仅包含根结点的二叉树的高度为1，则高度为k的二叉树的最大结点数为___2k-1 ___，最小结点数为__  k  ___。

(5)在一棵二叉树中，如果度为2的结点个数为100，则叶子结点个数为  101    。

(6)在一棵哈夫曼树中，如果叶子结点个数为100，则度为1的结点总个数为     0     。

(7)在一棵哈夫曼树中，如果叶子结点个数为100，则度为2的结点总个数为     99     。

(8)在一棵哈夫曼树中，如果叶子结点个数为100，则结点总个数为     199     。

2、选择题

(1)具有N个结点的完全二叉树的深度是_ B ___。

(A)⌊ log2N ⌋           (B) ⌊ log2N ⌋+1 

(C) ⌊ log2(N) ⌋        (D) ⌊ log2N ⌋-1

(2)设二叉树的树根为第一层，则第i层上至多有_  _C____结点。

(A)1      (B)2      (C)2i-1      (D)2i-1

3、判断题

(1)二叉树的左右子树次序是严格的，不能够任意改变。（ 对     ）

(2)若根为第一层，则深度为k的满二叉树的结点数为2^k-1 。（ 对  ）

(3)二叉树的三叉链表存储结构可以方便的访问到双亲结点。   （ 对  ）

4、应用题

(1).请证明对于任何一棵二叉树，如果其终端结点数为n0，度为2的结点数为n2，则n0=n2+1。

见教材 P123

图1

（2）.设二叉树如图1所示。分别写出它的先序遍历、中序遍历、后序遍历序列。

先：ABCDEFGHIJ

中：BCDAFEHJIG

后：DCBFJIHGEA

(3).写出如图2所示二叉树的中序遍历结果。

    图2

中：ADBCHFEG

(4).已知某二叉树的前序遍历序列为：A B C D E F G和中序遍历序列为：C B E D A F G。请画出该二叉树并写出它的后序遍历序列。

 见教材  P154  例 6-5

(5).设一棵二叉树的先序遍历序列为abcde，中序遍历序列为badce，请画出对应的二叉树，并写出对应后序遍历序列。图3

二叉树见图3

后：bdeca

(6).在一段文字中，共出现a、b、c、d、e、f六种字符，每种字符出现的频率分别为7,9,12,22,23,27。请回答下列问题：

（a）什么是哈夫曼树？ 

     带权路径长度最小的二叉树。

100

（b）根据题目所给频率值，画出相应的哈夫曼树。

哈夫曼树见图4

（c）给出各个字符对应的哈夫曼编码。

7：1110

9：1111

12：110

22：00

23：01

27：10

5、读程序写结果

E

已知二叉树的结点结构如下：

 struct Node

{

    int data; 

    Node *lchild,*rchild;

};

某棵二叉树的形态如右图：

根据要求解答下题：