一、选择题 ( 每小题 1 分，共 10 分)

1、数据在计算机存储器内表示时，物理地址与逻辑地址不相同的，称之为（ ）。

A.存储结构 B.逻辑结构

C.链式存储结构 D.顺序存储结构

2、 算法分析的目的是（ ）。

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

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

3、广义表 A=（a），则表尾为（ ）。

A.a B.(( )) C.空表 D.(a)

4、如下陈述中正确的是（ ）

 A ．串是一种特殊的线性表 B ．串的长度必须大于零

 C ．串中元素只能是字母 D ．空串就是空白串

5、用某种排序方法对关键字序列（ 25，84，21，47，15，27，68，35，20）进行排序时，序

列的变化情况如下：

 20 ，15，21，25，47，27，68，35，84

 15 ，20，21，25，35，27，47，68，84

 15 ，20，21，25，27，35，47，68，84

则所采用的排序方法是（ ）

 A ．选择排序 B ．希尔排序 C ．归并排序 D ．快速排序

6、一个有 n 个顶点的无向图最多有（ ）条边。

 A.n B. n(n-1) C. n(n-1)/2 D.2n

7、对于哈希函数 H(key)= key%13, 被称为同义词的关键字是（）。

 A.35 和 41 B. 23 和 39 C. 15 和 44 D.25 和 51

8、若某线性表中最常用的操作是取第 i 个元素和找第 i 个元素的前趋元素，则采用（ ）存

储方式最节省时间。

A、单链表 B 、双链表 C 、单向循环 D 、顺序表

9、设数组 Data[0..m] 作为循环队列 SQ的存储空间， front 为队头指针， rear 为队尾指针，

则执行出队操作的语句为（ ）

A、front=front+1 B 、front=(front+1)% m

C、rear=(rear+1)%m D 、front=(front+1)%(m+1)

10、 设有一个无向图 G=（V，E）和 G’

=（V’，E’）如果 G’为 G的生成树，则下面不正

确的说法是（ ）

A、G’为 G 的子图

B 、G’为 G 的边通分量

C、G’为 G的极小连通子图且 V’=V

D 、G’为 G的一个无环子图

二、填空题 ( 每小题 1 分，共 20 分)

1、树有三种常用的存储结构，即孩子链表法，孩子兄弟链表法和 ______。

2、在带头结点单链表 L 中，表空的条件是 ______。

3、图的广度优先搜索方法类似于二叉树的 _________遍历。

4、在单链表 L 中，指针 p 所指结点有后继结点的条件是： __ 。

5、将两个或两个以上的有序表合并成一个新的有序表采用 排序算法较好。

6、在单链表 p 结点之后插入 s 结点的操作是： ___ _ ； 。

7、对于一个数据结构，一般包括 _________________三个方面的讨论？

8、算法好坏的度量我们一般用 和 。

9、下面程序段的时间复杂度为 ________。(n>1)

 sum=1 ；

 for (i=0;sum<n;i++) sum+=1;

10、基于时间的考虑时， 以 和 操作为主的线性表宜采用链表做存储结构。

11、对广义表 A=(x,((a,b),c,d)) 作运算 head(head(tail(A))) 后的结果 。

12、Exp = a b + (c d / e) f 的前缀式 : 。

13、一个栈的输入序列是： 1，2，3 则不可能的栈输出序列是 _______。

14、多个栈共存时，最好用 _______作为存储结构。

15、一棵深度为 k 且有 个结点的二叉树称为满二叉树。

16、表达式求值是 _______应用的一个典型例子。

17、设 T 和 P是两个给定的串，在 T 中寻找等于 P的子串的过程称为 __ _ ，又称 P为__ __ 。

18、广义表 (a,(a,b),d,e,((i,j),k)) 的长度是 _ ，深度是 _ 。

19、已知二叉树有 50个叶子结点，则该二叉树的总结点数至少是 ______。

20、带权路径长度最小的二叉树，又称最优二叉树，即 树 。

三、判断题（每小题 1 分，共 10 分）

1、“二分查找法”必需在有序表上进行。

2、在二路归并时，被归并的两个子序列中的关键字个数不一定相等。

3、在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。

4、通常递归的算法简单、易懂、容易编写，而且执行的效率也高。

5、一个广义表的表尾总是一个广义表。

6、对有向图 G，如果从任一顶点出发进行一次深度优先或广度优先搜索就能访问每个顶点，

则该图一定是完全图。

7、在一个有向图的拓朴序列中，若顶点 a 在顶点 b 之前，则图中必有一条弧 <a,b>。

8、霍夫曼树的结点个数不能是偶数。

9、哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根较近。

10、给定一棵树，可以找到唯一的一棵二叉树与之对应。

四、问答及运算题（每小题 5分，共 30分）

1、若有 100个学生，每个学生有学号，姓名，平均成绩，采用什么样的数据结构最方便，写

出这些结构？

2、什么是递归程序？ 递归程序的优、缺点是什么？

3、下面是用 c 语言编写的对不带头结点的单链表进行就地逆置的算法， 该算法用 L 返回逆置

后的链表的头指针，试在空缺处填入适当的语句。

void reverse （linklist &L ）{

p=null ；q=L；

while （q！=null ）

{ ; q->next=p ；p=q； __ ; }

 ___ __;

 }

4．已知一棵二叉树的前序和中序序列，求该二叉树的后序序列。

前序序列： A，B，C，D，E，F，G，H，I ，J

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

5、下列程序判断字符串 s 是否对称，对称则返回 1，否则返回 0；如 f("abba") 返回 1，f("abab")

返回 0；

 int f(________)

 {int i=0,j=0;

 while (s[j]) ________;

 for(j--; i<j && s[i]==s[j]; i++,j--);

 return( _______)

 }

6、什么是广义表？请简述广义表和线性表的主要区别。

五、分析题（每小题 5 分，共 30 分）

1、当你为解决某一问题而选择数据结构时，应从哪些方面考虑？

2、已知一组记录为 (46,74,53,14,26,38,86,65,27,34) ，给出采用直接插入排序法进行排序

时每一趟的排序结果。

3、给定权值 [5,10,12,15,30,40], 构造相应的哈夫曼树，要求具体步骤。

4、二叉树存储结构如下

typedef struct node

 {char data; struct node *lchild,*rchild;}*bitree;

}

以下程序为求二叉树深度的递归算法，请填空完善之。

 int depth(bitree bt) /*bt 为根结点的指针 */

{int hl,hr;  if (bt==NULL) return( ___);

 hl=depth(bt->lchild); hr=depth(bt->rchild);

 if( ___) _____ ；

 return(hr+1);

}

5、一个深度为 L 的满 K叉树有以下性质：第 L 层上的结点都是叶子结点，其余各层上每个结

点都有 K棵非空子树，如果按层次顺序从 1 开始对全部结点进行编号，求：

1）各层的结点的数目是多少？ 2 ）编号为 n 的结点的双亲结点（若存在）的编号是

多少？

3）编号为 n 的结点的第 i 个孩子结点（若存在）的编号是多少？

4）编号为 n 的结点有右兄弟的条件是什么？如果有，其右兄弟的编号是多少？

直接给出答案不必给出计算和推导过程。

标准答案

一、选择题 ( 每小题 1 分，共 10 分)

1、 C 2 、C 3 、C 4 、A 5 、D 6、 C 7 、D 8 、D 9 、D 10.B

二、填空题 ( 每小题 1 分，共 10 分)

1 、 双 亲 表 示 法 2 、 L->next == NULL 3 、 层 次 4 、 p->next!=null 5、 归 并 6、

s->next=p->next;p->next=s; 7 、逻辑结构、存储结构、操作（运算）。 8 、时间复杂度和

空间复杂度 9 、O(n) 10 、插入、删除 11 、（a，b） 12 、+ a b c / d e f

13、3 1 2 14 、链式存储结构 15 、2

k

+1 16、栈 17 、模式匹配 模式串 18 、5 3

19、99 20 、哈夫曼树

三、判断题 ( 每小题 1 分，共 10 分)

 1 ．对 2 ．对 3 ．对 4 ．错 5 ． 对

 6 ．错 7. 错 8. 对 9. 对 10. 对

四、问答及运算题 ( 每小题?分，共 30 分)

1、 将学号、姓名、平均成绩看成一个记录（元素，含三个数据项） ，将 100 个这样的记录存

于数组中。因一般无增删操作，故宜采用顺序存储。

typedef struct

 { int num;// 学号

char name[8];// 姓名

float score;/ 平均成绩

 }node ；

 node student[100];

2、一个函数在结束本函数之前，直接或间接调用函数自身，称为递归。

递归程序的优点是程序结构简单、清晰，易证明其正确性。缺点是执行中占内存空间

较多，运行效率低。

3、 L=L->next; ∥暂存后继

q=L; ∥待逆置结点

L=p; ∥头指针仍为 L

4、后序序列： C，B，F，E，I ，J，H，G，D，A 

5、char s[ ] j++ i >= j

6、线性表中的元素可以是各种各样的，但必须具有相同性质，属于同一数据对象。广义表中

的元素可以是原子，也可以是子表。即广义表是原子或子表的有限序列，满足线性结构的特

性。从某种意义上说，广义表属于线性结构。

五、分析题 ( 每小题 ?分，共30分)

1、通常考虑算法所需要的存储空间量和算法所需要的时间量。后者又涉及到四方面：程序运

行时所需输入的数据总量，对源程序进行编译所需时间，计算机执行每条指令所需时间和程

序中指令重复执行的次数。

2、 (0) [46] 74 53 14 26 38 86 65 27 34

(1) [46 74] 53 14 26 38 86 65 27 34

(2) [46 53 74] 14 26 38 86 65 27 34

(3) [14 46 53 74] 26 38 86 65 27 34

(4) [14 26 46 53 74] 38 86 65 27 34

(5) [14 26 38 46 53 74] 86 65 27 34

(6) [14 26 38 46 53 74 86] 65 27 34

(7) [14 26 38 46 53 65 74 86] 27 34

(8) [14 26 27 38 46 53 65 74 86] 34

(9) [14 26 27 34 38 46 53 65 74 86]

 3 、

4、 0 hl>hr hr=hl

5、(1)k h-1 (h 为层数 )

（2）因为该树每层上均有 K

h-1 个结点，从根开始编号为 1，则结点 i 的从右向左数第２个

孩子的结点编号为 ki 。设 n 为结点 i 的子女，则关系式 (i-1)k+2<=n<=ik+1 成立，因 i 是整

数，故结点 n 的双亲 i 的编号为 n-2)/k +1。

 (3) 结点 n(n>1) 的前一结点编号为 n-1（其最右边子女编号是 (n-1)*k+1 ），故结点 n 的

第 i 个孩子的编号是 (n-1)*k+1+i 。

(4) 根据以上分析，结点 n 有右兄弟的条件是，它不是双亲的从右数的 第一 子女，即

(n-1)%k!=0 ，其右兄弟编号是 n+1。