1 / 7 一、单项选择题 ：（本大题共20小题，每题 2 分，共 30 分） （说明：将答案写在试卷后面的答题纸上） 分数 评卷人

1.计算机识别、存储和加工处理的对象被统称为( ) A.数据 B.数据元素 C.数据结构 D.数据类型 2.在具有n个结点的有序单链表中插入一个新结点并使链表仍然有序的时间复杂度是( ) A.O(1) B.O(n) C.O(nlogn) D.O(n2) 3.队和栈的主要区别是( ) A.逻辑结构不同 B.存储结构不同 C.所包含的运算个数不同 D.限定插入和删除的位置不同 4.链栈与顺序栈相比，比较明显的优点是( ) A.插入操作更加方便 B.删除操作更加方便 C.不会出现下溢的情况 D.不会出现上溢的情况 5.下列说法中正确的是（） A. 二叉树中任何一个结点的度都为2 B. 二叉树的度为2 C. 任何一棵二叉树中至少有一个结点的度为2 D. 一棵二叉树的度可以小于2 6.在一非空二叉树的中序遍历序列中，根结点的右边（） A. 只有右子树上的所有结点 B. 只有右子树上的部分结点 C. 只有左子树上的所有结点 D. 只有左子树上的部分结点 7.在一个具有N个顶点的无向完全图中，包含的边的总数是（） A. N(N-1)/2 B. N(N-1) C. N(N+1) D. N(N+1)/2 8.下面的程序在执行时，S语句共执行的（）次。 i=1; while (i<=n) {for(j=i;j{S; } i=i+1; }

A. n(n+1)/2 B. n(n-1)/2 C. n! D. 2n 9.设二叉树有n个结点，则其深度为（） A. n-1 B. n C. 5log2n+1 D. 不确定 2 / 7

10.已知一棵二叉树结点的先根序列为ABDGCFK，中根序列为DGBAFCK，则结点的后根序列为（） A. ACFKBDG B. GDBFKCA C. KCFAGDB D. ABCDFKG 11.任何一个带权的无向连通图的最小生成树（） A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在 12.已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，则它的前序遍历序列是（） A. acbed B. decab C. deabc D. cedba 13.设深度为k的二叉树上只有度为0和度为2的结点，则这类二叉树上所含结点总数量是（C）个 A. k+1 B. 2k C. 2k-1 D. 2k+1 14.下面程序的时间复杂性是（） For(i=1;i<=n;i++) For(j=1;j<=n;j++) {a[i][j]=i*j; }

A. O(2m) B. O(2n) C. O(m*n) D. O(m+n) 15.含N个顶点的连通图中的任意一条简单路径，其长度不可能超过（） A. 1 B. N/2 C. N-1 D. N 16. 下列说法正确的是（A） A.树的先根遍历序列与其对应的二叉树的先根遍历序列相同 B.树的先根遍历序列与其对应的二叉树的后根遍历序列相同 C.树的后根遍历序列与其对应的二叉树的先根遍历序列相同 D.树的后根遍历序列与其对应的二叉树的后根遍历序列相同 17.对于一个具有N个结点和E条边的无向图，若采用邻接表示，则表头向量的大小是(A) A. N B. N+1 C. N-E D. N-1 18.判断一个有向图是否存在回路，除了可以利用拓扑排序方法，还可以利用（） A.求关键路径的方法 B.求最短路径的Dijkstra方法 C.广度优先遍历方法 D. 深度优先遍历方法 19.一个队列的输入序列是1,2,3,4，则队列的输出序列是（） A,4,3,2,1 B.1,2,3,4 C.1,4,3,2 D.3,2,4,1 20.任何一个带权的无向连通图的最小生成树（B） A.只有一棵 B.有一棵或多棵 C.一定有多棵 D.可能不存在

得分 评卷人 复查人 一、 二、填空题（本大题共10小题，每小题1分，共10分） 请在每小题的空格中填上正确答案。错填、不填均无分。

（1）在线性表中插入或删除一个元素，需要平均移动 元素，具体移动的元素个数与 有关。 （2）顺序表中逻辑上相邻的元素的物理位置 紧邻，单链表中逻辑上相邻的元素物理位置 紧邻。 （3）在单链表中，除了首元结点外，任意结点的存储位置由 指示。 （4）记录的 结构是数据在物理存储器上的存储方式。 3 / 7

（5）在非空队列中，头指针始终指向 ，而尾指针始终指向 。 （6）N个顶点的连通图，至少有 条边。 （7）对于一个长度为n的线性表，假设表中各结点的查找概率相同，则在查找成功的情况下，平均查找长度为 ，如果k不在表中，则需要进行 次比较后才能确定查找失败。 (8)在二叉排序树中，其左子树中任何一个结点的关键字一定 其右子树的各结点的关键字。 （9）已知无向图G的结点数为n，边数为e，其邻接表表示中的表结点数与表头结点数之和为 。 （10）若二叉树的一个叶子是某子树的中序遍历序列中的第一个结点，则它必是孩子树的后序遍历序中的 个结点。 （11）有m个叶子结点(又称外结点)的哈夫曼树，其结点总数是 。 （12）如果一个图中有n条边，则此图的生成树含有 条边，所以生成树是图的边数 最少 的连通图 （13）由权值为1，2，3，4，5，6的六个叶子结点构成一棵哈夫曼树，则带权的路径的长度为 。 （14）在顺序队列中，应该有队头和队尾两个指针来指示，队头指针和队尾指针的初值在队列的初始化时均应该设置为 ，当对队列进行插入和删除的操作后，如果头指针和尾指针相等时，队列为 。 （15）树有三种常用的存储结构，即孩子链表法、孩子兄弟链表法和 。 （16）无向图的邻接矩阵是 的，并且主对角线上的元素的值为 。 （17）在结点数目相同的二叉树中， 的路径长度最短。 （18）栈和队列均可视为特殊的线性表，所不同的在于对这二种特殊线性表 和 运算的限定不一样。 16.当问题的规模n趋向无穷大时，算法执行时间T(n)的数量级被称为算法的____时间复杂度____。

17.下面程序段的时间复杂度为___________。 sum=1； for（i=0；sumsum+=1； 18.已知链表结点定义如下： typedef struct node{ char data［16］； struct node *next; } LinkStrNode； 如果每个字符占1个字节，指针占4个字节，则该链表的存储密度是___________。 19.使用一个100个元素的数组存储循环队列，如果采取少用一个元素空间的方法来区别循环队列的队空和队满，约定队头指针front等于队尾指针rear时表示队空。若为front=8，rear=7，则队列中的元素个数为___________。 20.3个结点可以组成___________种不同树型的二叉树。 4 / 7

21.用5个权值{3, 2，4，5，1}构造的哈夫曼(Huffman)树的带权路径长度是___________。 22.若无向图G中有n个顶点m条边，采用邻接矩阵存储，则该矩阵中非0元素的个数为___________。 23.影响排序效率的两个因素是关键字的___________次数和记录的移动次数。 24.对任一m阶的B树，每个结点中最多包含___________个关键字。 25.在链表的结点中，数据元素所占的存储量和整个结点所占的存储量之比称作________。

26.已知链栈的结点结构为 栈顶指针为top，则实现将指针p所指结点插入栈顶的语句依次为________和________。 27.空串的长度是________；空格串的长度是________。 28.在一棵度为3的树中，度为2的结点个数是1，度为0的结点个数是6，则度为3的结点个数是________。

得分 评卷人 复查人 三、名词解释（本大题共4小题，每小题3分，共12分） （1）栈：。 （2）树：。 （3）森林：。 （4）满二叉树：。 （5）数据：。

（6）数据对象：。 （7）数据结构：。 （8）算法： 得分 评卷人 复查人 四、简答题（本大题共4小题，每小题5分，共20分）

（1）简述算法的五个重要特性 （2）算法设计的基本要求

date next 5 / 7

（3）试描述数据结构和抽象数据类型的概念与程序设计语言中数据类型概念的区别 （4）简述二叉树的特点 （5）已知一棵度为k的树中有1n个度为1的结点，2n个度为2的结点，。。。kn个度为k的结点，问该树中有多少个叶子节点？ （7）写出下列树的先根序列和后根序列

A

CEFGHIJKBD

（8）已知如图所示的有向图，请给出该图的： （1） 每个顶点的入/出度 （2） 邻接矩阵

15

246

3 答案： 得分 评卷人 复查人 五、程序阅读题（本大题共4小题，每小题5分，共20分）

（1）简述以下算法的功能： status A (linkedlist L) { if (L&&L->next) {Q=L;L=L->next;P=L;