1．填空题

1. 数据结构被形式地定义为（D, R），其中D是 数据元素 的有限集合，R是D上的 关系的 有限集合。

2. 数据结构包括数据的逻辑结构、数据的 存储结构    和数据的 运算结构      这三个方面的内容。

3. 数据结构按逻辑结构可分为两大类，它们分别是线性结构 和非线性结构  。

5．在线性结构中，第一个结点   没有  前驱结点，其余每个结点有且只有 1个前驱结点；最后一个结点   没有     后继结点，其余每个结点有且只有1个后继结点。

6. 在树形结构中，树根结点没有  前驱结点，其余每个结点有且只有 一个       个前驱结点；叶子结点没有  后驱       结点，其余每个结点的后继结点数可以   任意多个

7. 在图形结构中，每个结点的前驱结点数和后续结点数可以 是任以多 。

8. 数据的存储结构可用四种基本的存储方法表示，它们分别是顺序 、 链式 、 索引 和 散列。

9．数据的运算最常用的有5种，它们分别是   插入 、 删除、修改、 查找 、排序  。

11．数据结构是研讨数据的_（1）逻辑结构_和_（2）物理/_存储结构，以及它们之间的相互关系，并对与这种结构定义相应的_（3）操作/运算_，设计出相应的（4）算法_。

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

i=1;

WHILE i<n {  FOR (j=1 ;j< n ;j++)  {x=x+1;i=i*2}  }；

3、填空题

1.  向量、栈和队列都是    线性   结构，可以在向量的  任何      位置插入和删除元素；对于栈只能在   栈顶     插入和删除元素；对于队列只能在对尾      插入和  队首       删除元素。

2. 栈是一种特殊的线性表，允许插入和删除运算的一端称为   栈顶       。不允许插入和删除运算的一端称为    栈底    。

3.     队列   是被限定为只能在表的一端进行插入运算，在表的另一端进行删除运算的线性表。

4. 在具有n个单元的循环队列中，队满时共有      n-1      个元素。

5.  带表头结点的空循环双向链表的长度等于    0    。

4一5、填空题

1.          不包含任何字符（长度为0）的串               称为空串；     由一个或多个空格（仅由空格符）组成的串                            称为空白串。

4. 子串的定位运算称为串的模式匹配； 被匹配的主串  称为目标串，    子串称为模式。

6. 若n为主串长，m为子串长，则串的古典匹配算法最坏的情况下需要比较字符的总次数为(n-m+1)*m。

7. 假设有二维数组A_6×8，每个元素用相邻的6个字节存储，存储器按字节编址。已知A的起始存储位置（基地址）为1000，则数组A的体积（存储量）为      288 B      ；末尾元素A₅₇的第一个字节地址 为     1282   ；若按行存储时，元素A₁₄的第一个字节地址为  (8+4)×6+1000=1072            ；若按列存储时，元素A₄₇的第一个字节地址为       (6×7＋4)×6＋1000）＝1276        。

8. 设数组a[1…60, 1…70]的基地址为2048，每个元素占2个存储单元，若以列序为主序顺序存储，则元素a[32,58]的存储地址为        8950      。

9. 三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素

的     行下标    、      列下标       和     元素值        。

10. 求下列广义表操作的结果：

（1） GetHead【((a,b),(c,d))】===          （a,b）              ;     

（2） GetHead【GetTail【((a,b),(c,d))】】===       (c,d)        ;

（3） GetHead【GetTail【GetHead【((a,b),(c,d))】】】===     b      ;

（4） GetTail【GetHead【GetTail【((a,b),(c,d))】】】===     (d)       ;

6、填空题

2. 一棵深度为6的满二叉树有    n1+n2=0+n2=n0-1=31          个分支结点和 2的5次方=32           个叶子。

3．一棵具有２５７个结点的完全二叉树，它的深度为    9    。

4.  设一棵完全二叉树有700个结点，则共有     350   个叶子结点。

5. 设一棵完全二叉树具有1000个结点，则此完全二叉树有   500      个叶子结点，有 499    个度为2的结点，有  1    个结点只有非空左子树，有  0     个结点只有非空右子树。

6. 一棵含有n个结点的k叉树，可能达到的最大深度为  n    ，最小深度为      2    。

7. 二叉树的基本组成部分是：根（N）、左子树（L）和右子树（R）。因而二叉树的遍历次序有六种。最常用的是三种：前序法（即按N L R次序），后序法（即按      LRN     次序）和中序法（也称对称序法，即按L N R次序）。这三种方法相互之间有关联。若已知一棵二叉树的前序序列是BEFCGDH，中序序列是FEBGCHD，则它的后序序列必是       FEGHDCB             。

8. 中序遍历的递归算法平均空间复杂度为     0(n)         。

9. 用5个权值{3, 2, 4, 5, 1}构造的赫夫曼（Huffman）树的带权路径长度是   33      。

7、填空题

1. 图有   邻接矩阵  、  邻接表  ，等存储结构，遍历图有  深度优先遍历  、 广度优先遍历    、等方法。

2. 有向图G用邻接表矩阵存储，其第i行的所有元素之和等于顶点i的     出度  。

3. 如果n个顶点的图是一个环，则它有         n      棵生成树。

4. n个顶点e条边的图，若采用邻接矩阵存储，则空间复杂度为  O(n2)  。

5. n个顶点e条边的图，若采用邻接表存储，则空间复杂度为        O(n+e)  。

6. 设有一稀疏图G，则G采用    邻接表    存储较省空间。

7. 设有一稠密图G，则G采用    邻接矩阵 存储较省空间。

8. 图的逆邻接表存储结构只适用于 有向  图。

9. 已知一个图的邻接矩阵表示，删除所有从第i个顶点出发的方法是   将邻接矩阵的第i行全部置0  。

10. 图的深度优先遍历序列 不是    惟一的。

11. n个顶点e条边的图采用邻接矩阵存储，深度优先遍历算法的时间复杂度为  O(n2)    ；若采用邻接表存储时，该算法的时间复杂度为  O(n+e)  。

12. n个顶点e条边的图采用邻接矩阵存储，广度优先遍历算法的时间复杂度为   O(n2)     ；若采用邻接表存储，该算法的时间复杂度为  O(n+e)    。

13. 图的BFS生成树的树高比DFS生成树的树高        小或相等          。

14. 用普里姆(Prim)算法求具有n个顶点e条边的图的最小生成树的时间复杂度为    O(n2)   ；用克鲁斯卡尔(Kruskal)算法的时间复杂度是    O(elog2e)  。

15. 若要求一个稀疏图G的最小生成树，最好用    克鲁斯卡尔(Kruskal)   算法来求解。

16. 若要求一个稠密图G的最小生成树，最好用      普里姆(Prim)    算法来求解。

17. 用Dijkstra算法求某一顶点到其余各顶点间的最短路径是按路径长度      递增    的次序来得到最短路径的。

18.  拓扑排序算法是通过重复选择具有    0   个前驱顶点的过程来完成的。

 

9、填空题

1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是  顺序查找（线性查找）  。

2. 线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索  8   次。设有100个结点，用二分法查找时，最大比较次数是  7    。

3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为  2   ；比较四次查找成功的结点数为  8   ；平均查找长度为   3.7  。

解：显然，平均查找长度＝O（log2n）<5次（25）。但具体是多少次，则不应当按照公式

 来计算（即（21×log221）/20＝4.6次并不正确！）。因为这是在假设n＝2m-1的情况下推导出来的公式。应当用穷举法罗列：

全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7  ！！！

4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素    28，6，12，20    比较大小。

5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是  散列查找   。

6. 散列法存储的基本思想是由  关键字的值     决定数据的存储地址。

7. 有一个表长为m的散列表，初始状态为空，现将n（n<m）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。(而任一元素查找次数 ≤n-1)

 

1．应用软件是指_____D____.

A)所有能够使用的软件           B) 能被各应用单位共同使用的某种软件

C)所有微机上都应使用的基本软件 D) 专门为某一应用目的而编制的软件

2. 数据结构中，与所使用的计算机无关的是数据的     C   结构.

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

3. 算法分析的目的是__C__________

A) 找出数据结构的合理性       B) 研究算法中的输入和输出的关系

C) 分析算法的效率以求改进     D) 分析算法的易懂性和文档性

4. 计算机算法必须具备输入、输出和    B等5个特性。

A) 可行性、可移植性和可扩充性       B) 可行性、确定性和有穷性

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

5. 下面说法错误的是（A  ）

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

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

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

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

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

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

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

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

7．连续存储设计时，存储单元的地址（  A  ）。

A．一定连续    B．一定不连续 

C．不一定连续  D．部分连续，部分不连续

二、单项选择题

（  C ）1．数据在计算机存储器内表示时，物理地址与逻辑地址相同并且是连续的，称之为：

（A）存储结构      （B）逻辑结构      （C）顺序存储结构     （D）链式存储结构

（  B ）2. 一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是     

（A）110     （B）108         （C）100      （D）120

（  A  ）3. 在n个结点的顺序表中，算法的时间复杂度是O（1）的操作是：

（A）     访问第i个结点（1≤i≤n）和求第i个结点的直接前驱（2≤i≤n）

（B）      在第i个结点后插入一个新结点（1≤i≤n）

（C）      删除第i个结点（1≤i≤n）         （D） 将n个结点从小到大排序

（ B   ）4. 向一个有127个元素的顺序表中插入一个新元素并保持原来顺序不变，平均要移动  个元素

（A）8     （B）63.5         （C）63     （D）7

（  A  ）5. 链接存储的存储结构所占存储空间：

（A）   分两部分，一部分存放结点值，另一部分存放表示结点间关系的指针

（B）    只有一部分，存放结点值

（C） 只有一部分，存储表示结点间关系的指针

（D） 分两部分，一部分存放结点值，另一部分存放结点所占单元数

（  B  ）6. 链表是一种采用        存储结构存储的线性表；

（A）顺序     （B）链式         （C）星式      （D）网状

（   D ）7. 线性表若采用链式存储结构时，要求内存中可用存储单元的地址:

（A）必须是连续的        （B）部分地址必须是连续的

（C）一定是不连续的      （D）连续或不连续都可以

（  B  ）8． 线性表Ｌ在       情况下适用于使用链式结构实现。

（Ａ）需经常修改Ｌ中的结点值      （Ｂ）需不断对Ｌ进行删除插入

（Ｃ）Ｌ中含有大量的结点          （Ｄ）Ｌ中结点结构复杂

（  C  ）9． 单链表的存储密度

（Ａ）大于1； （Ｂ）等于1；  （Ｃ）小于1； （Ｄ）不能确定

（   B ）10． 设a1、a2、a3为3个结点，整数P0，3，4代表地址，则如下的链式存储结构称为

（Ａ）循环链表   （Ｂ）单链表  （Ｃ）双向循环链表    （Ｄ）双向链表

（    B   ）1.  栈中元素的进出原则是

Ａ．先进先出  Ｂ．后进先出  Ｃ．栈空则进  Ｄ．栈满则出

（     C  ）2.  若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为

   Ａ．i    Ｂ．n=i      Ｃ．n-i+1       Ｄ．不确定

（ b     ）3.  判定一个栈ST（最多元素为m0）为空的条件是

Ａ．ST->top<>0    Ｂ．ST->top=0      

Ｃ．ST->top<>m0       Ｄ．ST->top=m0

（    a  ）4.  判定一个队列QU（最多元素为m0）为满队列的条件是

   Ａ．QU->rear － QU->front = = m0   

Ｂ．QU->rear － QU->front －1= = m0 

   Ｃ．QU->front = = QU->rear          

 Ｄ．QU->front = = QU->rear+1

（    d  ）5．数组Ｑ［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为

（Ａ）r－f; （Ｂ）（n＋f－r）% n; （Ｃ）n＋r－f; （Ｄ）（n＋r－f）% n

（ B   ）1.  串是一种特殊的线性表，其特殊性体现在：

   Ａ．可以顺序存储       Ｂ．数据元素是一个字符     

Ｃ．可以链式存储        Ｄ．数据元素可以是多个字符

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

   Ａ．连接      Ｂ．模式匹配    Ｃ．求子串       Ｄ．求串长

（   D ）3.  设串s1=’ABCDEFG’，s2=’PQRST’，函数con(x,y)返回x和y串的连接串，subs(s, i, j)返回串s的从序号i开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1, 2, len(s2)), subs(s1, len(s2), 2))的结果串是：

   Ａ．BCDEF       Ｂ．BCDEFG     Ｃ．BCPQRST        Ｄ．BCDEFEF

（   A ）4.  假设有60行70列的二维数组a[1…60, 1…70]以列序为主序顺序存储，其基地址为10000，每个元素占2个存储单元，那么第32行第58列的元素a[32,58]的存储地址为      。（无第0行第0列元素）

  Ａ．16902    Ｂ．16904      Ｃ．14454       Ｄ．答案A, B, C均不对

(   B  ) 5. 设矩阵A是一个对称矩阵，为了节省存储，将其下三角部分（如      

右图所示）按行序存放在一维数组B[ 1, n(n-1)/2 ]中，对下三角部           

分中任一元素a_i,j(i≤j), 在一维数组B中下标k的值是：

Ａ．i(i-1)/2+j-1        Ｂ．i(i-1)/2+j    

Ｃ．i(i+1)/2+j-1        Ｄ．i(i+1)/2+j

6. 从供选择的答案中，选出应填入下面叙述   ？  内的最确切的解答，把相应编号写在答卷的对应栏内。

有一个二维数组A，行下标的范围是0到8，列下标的范围是1到5，每个数组元素用相邻的4个字节存储。存储器按字节编址。假设存储数组元素A[0,1]的第一个字节的地址是0。

存储数组A的最后一个元素的第一个字节的地址是   A   。若按行存储，则A[3,5]和A[5,3]的第一个字节的地址分别是  B   和  C   。若按列存储，则A[7,1]和A[2,4]的第一个字节的地址分别是  D   和  E   。

供选择的答案

A～E：①28   ② 44   ③ 76   ④ 92    ⑤ 108   ⑥ 116   ⑦ 132   ⑧ 176    ⑨ 184   ⑩ 188

答案：A＝   8       B＝    3        C＝    5         D＝    1             E= 6    

 

7. 从供选择的答案中，选出应填入下面叙述   ？   内的最确切的解答，把相应编号写在答卷的对应栏内。

有一个二维数组A，行下标的范围是1到6，列下标的范围是0到7，每个数组元素用相邻的6个字节存储，存储器按字节编址。那么，这个数组的体积是   A   个字节。假设存储数组元素A[1,0]的第一个字节的地址是0，则存储数组A的最后一个元素的第一个字节的地址是   B   。若按行存储，则A[2,4]的第一个字节的地址是  C   。若按列存储，则A[5,7]的第一个字节的地址是  D   。

供选择的答案

A～D：①12  ②66  ③72  ④96  ⑤114  ⑥120  ⑦156  ⑧234  ⑨276   ⑩282   (11)283  （12）288

答案：A＝   12       B＝   10         C＝     3        D＝   9              E=     

（  c  ）1． 不含任何结点的空树         。

（Ａ）是一棵树;                         （Ｂ）是一棵二叉树; 

（Ｃ）是一棵树也是一棵二叉树;           （Ｄ）既不是树也不是二叉树

（   c ）2．二叉树是非线性数据结构，所以             。

（Ａ）它不能用顺序存储结构存储;           （Ｂ）它不能用链式存储结构存储;   

（Ｃ）顺序存储结构和链式存储结构都能存储;  （Ｄ）顺序存储结构和链式存储结构都不能使用

（  c  ）3.  具有n(n>0)个结点的完全二叉树的深度为         。

(Ａ) élog₂(n)ù   (Ｂ) ë log₂(n)û   (Ｃ) ë log₂(n) û+1     (Ｄ) élog₂(n)+1ù

（ a   ）4．把一棵树转换为二叉树后，这棵二叉树的形态是           。

（Ａ）唯一的                          （Ｂ）有多种

（Ｃ）有多种，但根结点都没有左孩子    （Ｄ）有多种，但根结点都没有右孩子

6. 二叉树  A   。在完全的二叉树中，若一个结点没有  B   ，则它必定是叶结点。每棵树都能惟一地转换成与它对应的二叉树。由树转换成的二叉树里，一个结点N的左子女是N在原树里对应结点的  C   ，而N的右子女是它在原树里对应结点的  D    。

供选择的答案

A： ①是特殊的树   ②不是树的特殊形式   ③是两棵树的总称   ④有是只有二个根结点的树形结构

B:   ①左子结点   ② 右子结点  ③ 左子结点或者没有右子结点    ④ 兄弟

C～D： ①最左子结点         ② 最右子结点    ③ 最邻近的右兄弟        ④ 最邻近的左兄弟

       ⑤ 最左的兄弟     ⑥ 最右的兄弟

答案：A=    2       B=    1     C=  1        D＝     3     

（C ）1. 在一个图中，所有顶点的度数之和等于图的边数的      倍。

             A．1/2            B.  1             C.  2             D.  4

（  B   ）2. 在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的     倍。

             A．1/2            B.  1             C.  2             D.  4

（   B  ）3. 有8个结点的无向图最多有      条边。

             A．14            B.  28             C.  56             D.  112

（    C ）4. 有8个结点的无向连通图最少有      条边。

             A．5            B.  6             C.  7             D.  8

（     C）5. 有8个结点的有向完全图有      条边。

             A．14            B.  28             C.  56             D.  112

（    B ）6. 用邻接表表示图进行广度优先遍历时，通常是采用         来实现算法的。

A．栈            B. 队列            C.  树             D.  图

（   A  ）7. 用邻接表表示图进行深度优先遍历时，通常是采用         来实现算法的。

A．栈            B. 队列            C.  树             D.  图

 

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

（    C ）8. 已知图的邻接矩阵，根据算法思想，则从顶点0出发按深度优先遍历的结点序列是

（   D  ）9. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按深度优先遍历的结点序列是

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

（   B  ）10. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是

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

（    C ）11. 已知图的邻接矩阵同上题8，根据算法，则从顶点0出发，按广度优先遍历的结点序列是

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

 

（   A  ）14. 深度优先遍历类似于二叉树的

A．先序遍历      B.  中序遍历     C.  后序遍历    D.  层次遍历

（   D  ）15. 广度优先遍历类似于二叉树的

A．先序遍历      B.  中序遍历     C.  后序遍历    D.  层次遍历

（  A   ）16. 任何一个无向连通图的最小生成树

A．只有一棵     B.  一棵或多棵     C.  一定有多棵    D.  可能不存在

（  A   ）2． 折半查找有序表（4，6，10，12，20，30，50，70，88，100）。若查找表中元素58，则它将依次与表中          比较大小，查找结果是失败。

A．20，70，30，50      B．30，88，70，50      C．20，50     D．30，88，50

（    C ）3． 对22个记录的有序表作折半查找，当查找失败时，至少需要比较        次关键字。

A．3         B．4          C．5           D． 6

（   A  ）4. 链表适用于       查找

A．顺序       B．二分法      C．顺序，也能二分法      D．随机

（   C  ）5.  折半搜索与二叉搜索树的时间性能

             A. 相同       B.  完全不同        C. 有时不相同       D. 数量级都是O（log₂n） 

三．判断题

1. 数据元素是数据的最小单位。(  × )

2. 记录是数据处理的最小单位。 (×  )

3. 数据的逻辑结构是指数据的各数据项之间的逻辑关系；(  ×)

4．算法的优劣与算法描述语言无关，但与所用计算机有关。(  ×)

5．健壮的算法不会因非法的输入数据而出现莫名其妙的状态。(√   )

6．算法可以用不同的语言描述，如果用C 语言或PASCAL语言等高级语言来描述，则算法实际上就是程序了。(  ×  )

7．程序一定是算法。(×    )

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

9. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。(×)

10. 数据的逻辑结构说明数据元素之间的顺序关系,它依赖于计算机的储存结构. (×  )

（  ×）1. 链表的每个结点中都恰好包含一个指针。 

（  ×）2. 链表的物理存储结构具有同链表一样的顺序。

（  ×  ）3. 链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动将后续各个单元向前移动。

（  ×）4. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。

（  ×）5. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。

（  ×  ）6. 顺序存储方式的优点是存储密度大，且插入、删除运算效率高。

（  ×  ）7. 线性表在物理存储空间中也一定是连续的。

（  ×）8. 线性表在顺序存储时，逻辑上相邻的元素未必在存储的物理位置次序上相邻。

（  ×  ）9. 顺序存储方式只能用于存储线性结构。

（  ×）10. 线性表的逻辑顺序与存储顺序总是一致的。

× ）1. 在表结构中最常用的是线性表，栈和队列不太常用。

                     CPU就是队列     

（ √ ）2. 栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。

（ √ ）3. 对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。 

（  × ）4. 栈和链表是两种不同的数据结构。 

（    ×）5. 栈和队列是一种非线性数据结构。  

（  √）6. 栈和队列的存储方式既可是顺序方式，也可是链接方式。 

√ ）7. 两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。

（√ ）1. 若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。

（× ）2.二叉树中每个结点的两棵子树的高度差等于1。 

（√）3.二叉树中每个结点的两棵子树是有序的。    

（   ×）4.二叉树中每个结点有两棵非空子树或有两棵空子树。 

（  ×）5.二叉树中每个结点的关键字值大于其左非空子树（若存在的话）所有结点的关键字值，且小于其右非空子树（若存在的话）所有结点的关键字值。  

（   ×）6.二叉树中所有结点个数是2^k-1-1，其中k是树的深度。 

（×  ）7.二叉树中所有结点，如果不存在非空左子树，则不存在非空右子树。 

（×   ）8.对于一棵非空二叉树，它的根结点作为第一层，则它的第i层上最多能有2ⁱ－1个结点。

（   √）9.用二叉链表法（link-rlink）存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。

（  √ ）10. 具有12个结点的完全二叉树有5个度为2的结点。

四、简答题

1. 试比较顺序存储结构和链式存储结构的优缺点。在什么情况下用顺序表比链表好？

①顺序存储时，相邻数据元数素的存放地址也相邻（逻辑与物理统一）；要求内存中可用存储单元的地址必须是连续的。

优点：存储密度大存储空间利用率高。缺点：插入删除元素时不方便。

②链式存储时，相邻数据元素可随意存放，但所占存储空间分两部分，一部份存放结点值，另一部分存放表示结点间关系的指针

优点：插入或删除元素时很方便，使用灵活。缺点：存储密度小存储空间利用率低。

顺序表适宜于做查找这样的静态操作；链表宜于做插入删除这样的动态操作

若线性表的长度变化不大，其主要操作是查找，则采用顺序表；

若线性表的长度变化较大，其主要操作是，插入，删除操作，则采用链式表。

 

2 . 在单链表中设置头结点的作用是什么？

答：为了操作方便，通常在链表的首元结点之前附设一个结点，称为头结点，其作用是为了对链表进行操作时，可以对空表、非空表的情况以及对首元结点进行统一处理。

五、线性表具有两种存储方式，即顺序方式和链接方式。现有一个具有五个元素的线性表L={23，17，47，05，31}，若它以链接方式存储在下列100～119号地址空间中，每个结点由数据（占2个字节）和指针（占2个字节）组成，如下所示：

其中指针X，Y，Z的值分别为多少？该线性表的首结点起始地址为多少？末结点的起始地址为多少？

X=116  Y=0  Z=100 首地址=108  末地址=112

四、简答求解题

2. 设循环队列的容量为40（序号从0到39），现经过一系列的入队和出队运算后，有

① front=11，rear=19;    ② front=19，rear=11；问在这两种情况下，循环队列中各有元素多少个？

2.用队列长度计算公式：  (N＋r－f)% N

① L=（40＋19－11）% 40=8        ② L=（40＋11－19）% 40=32

五、算法设计

1.       假设一个数组squ[m]存放循环队列的元素。若要使这m个分量都得到利用，则需另一个标志tag，以tag为0或1来区分尾指针和头指针值相同时队列的状态是“空”还是“满”。试编写相应的入队和出队的算法。

这就是解决队满队空的三种办法之① 设置一个布尔变量以区别队满还是队空（其他两种见简答题）；

思路：一开始队空，设tag=0，若从rear一端加到与front指针相同时，表示入队已满，则令tag=1；

若从front一端加答：#define m0 100

     Correct(exp,tag)

      Char exp[m0];

      Int tag

      {char st[m0];

Int top=0,i=1;

Tag=1;

While(i<=m0 && tag)

{if(exp[i]==’(‘exp[i]==’[exp[i]==’{‘}

{top++

St[top]=exp[i];

}

If(exp[i]==’)’)

If(st[top]==’(‘)top__;

Else tag=0;

If(exp[i]==’)’)

If(st[top]==’{‘top--;

Else tag=0;

I++

}

If(top>0)tag=0;

}到与rear指针相同时，则令tag=0，表示出队已空。

三、计算题

1.       设s=’I AM A STUDENT’, t=’GOOD’, q=’WORKER’,

求Replace (s,’STUDENT’, q) 和Concat (SubString (s,6,2), Concat (t, SubString (s,7,8)))。

解(1)Replace(s,’STUDENT’,q)=’I AM A WORKER’

(2)因为 SubString(s,6,2)=’A’:   SubString(s,7,8)=’STUDENT’

Coucat(t,SubString(s,7,8))=’GOOD STUDENT’

所以Concat(SubString(s,6,2),Concat(t,SubString(s,7,8)))=’A GOOD STUDENT’

 

2. 已知主串s=’ADBADABBAABADABBADADA’,模式串pat=’ADABBADADA’。写出模式串的next函数值，并由此画出KMP算法匹配的全过程。解：（由演示程序得知）nextval函数值为0 1 0 2 1 0 1 0 4 0    在第12个字符处发现匹配！

s=’ADBADABBAABADABBADADA’

pat=’ADABBADADA

 

3.  用三元组表表示下列稀疏矩阵：

         解：三元素组表中的每个结点对应于稀疏矩阵的一个非零元素，它包含有三个数据项，分别表示该元素

       的    行下标     、  列下标           和   元素值         。

所以（1）可列表为：       （2）可列表为：

6     6     4

1     6     -2

2     5     9

4     3     5

6     5     3

（2）

8     8     5

3     2     3

3     6     8

5     4     6

       （1）

 

4. 下列各三元组表分别表示一个稀疏矩阵，试写出它们的稀疏矩阵。

         解：（1）为6*4矩阵，非零元素有6个。

1  2  0  0

12  0  0  0 

（2）为4*5矩阵，非零元素有5个。

3  0  0  0

0  0  0  4    1   0  0  0  0

0  0  6  0    0  0  0  9  0

16  0  0  0  0  8  0  0  6

       （1）     0  0  7  0  0

（2）

1.       写出将字符串反序的递推或递归算法，例如字符串为“abcsxw”，反序为“wxscba”

Void string reverse(stringtype s, stringtype &r)

{

       SteAssign(r,’’);

       For(i=Strlen(s);i;i--)

       {

       StrAssign(c,SubString(s,i,1));

       StrAssign(r,Concat(r,c));

       }

       }//String Reverse

五、算法设计题

1. 编写递归算法，计算二叉树中叶子结点的数目。

法一：核心部分为：

DLR(liuyu *root)    

{ if (root!=NULL)

 { if ((root->lchild==NULL)&&(root->rchild==NULL)){sum++; printf ("%d\n",root->data);}

  DLR (root->lchild);

  DLR (root->rchild); }

 Return (0);

}

 

3. 假设用于通信的电文仅由8个字母组成，字母在电文中出现的频率分别为0.07，0.19，0.02，0.06，0.32，0.03，0.21，0.10。试为这8个字母设计赫夫曼编码。使用0～7的二进制表示形式是另一种编码方

案。对于上述实例，比较两种方案的优缺点。

 

 

解：方案1；哈夫曼编码

先将概率放大100倍，以方便构造哈夫曼树。

 w={7,19,2,6,32,3,21,10}，按哈夫曼规则：【[（2,3），6], (7,10)】, ­……19, 21, 32

0      1     0   1   0   1 19              21  32 0              1 0   1 0   1 7           10 6 0              1 2   3

（100）

（40）      （60）

19     21     32   （28）

（17）             （11）

   7     10  6    （5）

                 2     3

 

 

方案比较：

 

 

字母编号 对应编码 出现频率 1 1100 0.07 2 00 0.19 3 11110 0.02 4 1110 0.06 5 10 0.32 6 11111 0.03 7 01 0.21 8 1101 0.10

字母编号 对应编码 出现频率 1 000 0.07 2 001 0.19 3 010 0.02 4 011 0.06 5 100 0.32 6 101 0.03 7 110 0.21 8 111 0.10

 

 

 

 

 

 

 

 

 

 

 

 

方案1的WPL＝2(0.19+0.32+0.21)+4(0.07+0.06+0.10)+5(0.02+0.03)=1.44+0.92+0.25=2.61

方案2的WPL＝3(0.19+0.32+0.21+0.07+0.06+0.10+0.02+0.03)=3

结论：哈夫曼编码优于等长二进制编码

三、分析求解题

1. 已知如图所示的有向图，请给出该图的:

（1）      

顶点 1 2 3 4 5 6 入度             出度

每个顶点的入/出度；

（2）       邻接矩阵；

（3）       邻接表；

（4）       逆邻接表。

                    

 

 

 

 

2. 请对下图的无向带权图：

（1）       写出它的邻接矩阵，并按普里姆算法求其最小生成树；

（2）       写出它的邻接表，并按克鲁斯卡尔算法求其最小生成树。

                                                                   

解：设起点为a。可以直接由原始图画出最小生成树，而且最小生成树只有一种（类）!

邻接矩阵为：   

 

最小生成树

3. 已知二维数组表示的图的邻接矩阵如下图所示。试分别画出自顶点1出发进行遍历所得的深度优先生成树和广度优先生成树。

 

 

 

4. 试利用Dijkstra算法求图中从顶点a到其他各顶点间的最短路径，写出    执行算法过程中各步的状态。

 

 

5．给定下列网G:

 

（1）试着找出网G的最小生成树，画出其逻辑结构图；

（2）用两种不同的表示法画出网G的存储结构图；

（3）用C语言（或其他算法语言）定义其中一种表示法（存储结构）的数据类型。

A        B———————C           E————F         G————D

解：（1 ）最小生成树可直接画出，如右图所示。

（2）可用邻接矩阵和邻接表来描述：

描述存储结构的数据类型可参见教材或电子教案： 注：用两个数组分别存储顶点表和邻接矩阵 #define INFINITY  INT_MAX             //最大值∞ #define MAX_VERTEX_NUM      20  //假设的最大顶点数（可取为7） Typedef  enum {DG, DN, AG,AN }   GraphKind; //有向/无向图，有向/无向网 Typedef   struct   ArcCell{          //弧（边）结点的定义   VRType     adj;         //顶点间关系，无权图取1或0；有权图取权值类型   InfoType   *info;    //该弧相关信息的指针   }ArcCell, AdjMatrix [ MAX_VERTEX_NUM ] [MAX_VERTEX_NUM ]; Typedef struct{                             //图的定义   VertexType vexs [MAX_VERTEX_NUM ] ;   //顶点表，用一维向量即可 AdjMatrix arcs;               //邻接矩阵 Int   Vernum,   arcnum;   //顶点总数（7），弧（边）总数（9） GraphKind kind;    //图的种类标志 }Mgraph;

 

 

 

 

 

邻接表为：

a

→

b

12

→

e

4

^

b

→

a

12

→

c

20

→

e

8

→

f

9

^

c

→

b

20

→

d

15

→

g

12

^

d

→

c

15

→

g

10

^

e

→

a

4

→

b

8

→

f

6

^

f

→

b

9

→

e

6

^

g

→

c

12

→

d

10

 

四、算法设计题

1. 编写算法，由依次输入的顶点数目、弧的数目、各顶点的信息和各条弧的信息建立有向图的邻接表。

解：Status Build_AdjList(ALGraph &G)

 //输入有向图的顶点数,边数,顶点信息和边的信息，以建立邻接表

{   …………….

return OK;

}//Build_AdjList

 

 

2. 试基于图的深度优先搜索策略写一算法，判别以邻接表方式存储的有向图中是否存在由顶点v_i到顶点v_j的路径（i≠j）。

int visited[MAXSIZE]; //指示顶点是否在当前路径上

int exist_path_DFS(ALGraph G,int i,int j)//深度优先判断有向图G中顶点i到顶点j

是否有路径,是则返回1,否则返回0

{

  if(i==j) return 1; //i就是j

  else

  {

visited[i]=1;

    for(p=G.vertices[i].firstarc;p;p=p->nextarc)

    {

      k=p->adjvex;

      if(!visited[k]&&exist_path(k,j)) return 1;//i下游的顶点到j有路径

    }//for

  }//else

}//exist_path_DFS

 

9、填空题

1. 在数据的存放无规律而言的线性表中进行检索的最佳方法是  顺序查找（线性查找）  。

2. 线性有序表（a1，a2，a3，…，a256)是从小到大排列的，对一个给定的值k，用二分法检索表中与k相等的元素，在查找不成功的情况下，最多需要检索  8   次。设有100个结点，用二分法查找时，最大比较次数是  7    。

3. 假设在有序线性表a[20]上进行折半查找，则比较一次查找成功的结点数为1；比较两次查找成功的结点数为  2   ；比较四次查找成功的结点数为  8   ；平均查找长度为   3.7  。

解：显然，平均查找长度＝O（log2n）<5次（25）。但具体是多少次，则不应当按照公式

 来计算（即（21×log221）/20＝4.6次并不正确！）。因为这是在假设n＝2m-1的情况下推导出来的公式。应当用穷举法罗列：

全部元素的查找次数为＝（1＋2×2＋4×3＋8×4＋5×5）＝74； ASL＝74/20=3.7  ！！！

4．折半查找有序表（4，6，12，20，28，38，50，70，88，100），若查找表中元素20，它将依次与表中元素    28，6，12，20    比较大小。

5. 在各种查找方法中，平均查找长度与结点个数n无关的查找方法是  散列查找   。

6. 散列法存储的基本思想是由  关键字的值     决定数据的存储地址。

7. 有一个表长为m的散列表，初始状态为空，现将n（n<m）个不同的关键码插入到散列表中，解决冲突的方法是用线性探测法。如果这n个关键码的散列地址都相同，则探测的总次数是 n(n-1)/2=（ 1＋2＋…＋n-1） 。(而任一元素查找次数 ≤n-1)

字母编号 对应编码 出现频率 1 1100 0.07 2 00 0.19 3 11110 0.02 4 1110 0.06 5 10 0.32 6 11111 0.03 7 01 0.21 8 1101 0.10

三、分析求解题

1. 对分（折半）查找适不适合链表结构的序列，为什么？用二分查找的查找速度必然比线性查找的速度快，这种说法对吗？

答：不适合！虽然有序的单链表的结点是按从小到大（或从大到小）顺序排列，但因其存储结构为单链表，查找结点时只能从头指针开始逐步搜索，故不能进行折半查找。

二分查找的速度在一般情况下是快些，但在特殊情况下未必快。例如所查数据位于首位时，则线性查找快；而二分查找则慢得多。

2．假定对有序表：（3，4，5，7，24，30，42，54，63，72，87，95）进行折半查找，试回答下列问题：

（1）       画出描述折半查找过程的判定树；

（2）       若查找元素54，需依次与哪些元素比较？

（3）       若查找元素90，需依次与哪些元素比较？

（4）       假定每个元素的查找概率相等，求查找成功时的平均查找长度。

解：

（1）  先画出判定树如下（注：mid=ë(1+12)/2û=6）：

30

5           63

3     7       42        87

             4    24      54    72      95

(2) 查找元素54，需依次与30, 63, 42, 54 等元素比较；

(3) 查找元素90，需依次与30, 63,87, 95, 72等元素比较；

（4） 求ASL之前，需要统计每个元素的查找次数。判定树的前3层共查找1＋2×2＋4×3=17次；

但最后一层未满，不能用8×4，只能用5×4=20次，

所以ASL＝1/12（17＋20）＝37/12≈3.08

 

3. 设哈希（Hash）表的地址范围为0～17，哈希函数为：H（K）＝K  MOD  16。K为关键字，用线性探测法再散列法处理冲突，输入关键字序列：

        （10，24，32，17，31，30，46，47，40，63，49）

造出Hash表，试回答下列问题：

（1）       画出哈希表的示意图；

（2）       若查找关键字63，需要依次与哪些关键字进行比较？

（3）       若查找关键字60，需要依次与哪些关键字比较？

（4）假定每个关键字的查找概率相等，求查找成功时的平均查找长度。

解： （1）画表如下：

0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17
32	17	63	49					24	40	10				30	31	46	47
1	1	6	3					1	2	1				1	1	3	3

（2）查找63,首先要与H(63)=63=15号单元内容比较，即63 vs 31 ,no;

然后顺移，与46,47,32,17,63相比，一共比较了6次！

（3）查找60,首先要与H(60)=60=12号单元内容比较，但因为12号单元为空（应当有空标记），所以应当只比较这一次即可。

（4） 对于黑色数据元素，各比较1次；共6次；

对红色元素则各不相同，要统计移位的位数。“63”需要6次，“49”需要3次，“40”需要2次，“46”需要3次，“47”需要3次，

所以ASL=（1*6+2*1+3*3+6*1）/11＝23/11

4．已知如下所示长度为12的表：

（Jan, Feb, Mar, Apr, May, June, July, Aug, Sep, Oct, Nov, Dec）

(1)    试按表中元素的顺序依次插入一棵初始为空的二叉排序树，画出插入完成之后的二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

(2)    若对表中元素先进行排序构成有序表，求在等概率的情况下对此有序表进行折半查找时查找成功的平均查找长度。

(3)    按表中元素顺序构造一棵平衡二叉排序树，并求其在等概率的情况下查找成功的平均查找长度。

(4)    解：

(5)   

(6)     

 

 

这样做您的博客会受到更多的关注：

    装饰个性博客，看看如何换上炫酷模板？

    完善个人资料，上传靓照当头像

    随便逛逛，点击屏幕右上方的随便逛逛，看看邻居的观点，留下您的宝贵评论

 

还想了解更多，欢迎去帮助中心找答案。也可以到博客首页浏览大事小情。

                                                                                                                                                                      新浪官博