《数据结构与算法》期末试题试卷A

XXXXXX学校2014--2015学年第一学期期末考试

C. p=h D. p→next=h （8）带头结点的单链表head为空的判定条件是（ ）。

A. head = = NULL B. head → next = = NULL C. head → next = = head D. head ！= NULL （9）对于栈操作数据的原则是（ ）。

A.先进先出 B. 后进先出 C. 后进后出 D. 不分顺序 （10）有六个元素按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 （11）栈s最多能容纳4个元素。现有6个元素按A,B,C,D,E,F的顺序进栈，问下列哪一个序列是可能的出栈序列？（ ） A.E,D,C,B,A,F B. B,C,E,F,A,D C.C,B,E,D,A,F D. A,D,F,E,B,C

（12）设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为（ ）。

A. fedcba B. bcafed C.dcefba D. cabdef （13）输入序列为ABC,可以变为CBA时，经过的栈操作为（ ）。

A.push，pop，push，pop，push，pop B. push，push，push，pop， pop，pop C. push，push，pop， pop，push，pop D. push，pop，push，push，pop， pop （14）已知串S=’aaab’，其next数组值为（ ）。

A. 0123 B. 1123 C. 1231 D.1211 （15）串”ababaaababaa”的next数组为（ ）。

A. 012345678999 B. 012121111212 C. 011234223456 D. 0123012322345 （16）若串S=”software”，其子串的数目是（ ）。

A. 8 B. 37 C. 36 D. 9 2014级计算机应用专业《数据结构与算法》试题A卷

2015年01月19日

注意：

本试卷共4页，满分100分，考试时间为90分钟，考试方式为闭卷笔试。

姓名：______________________ 学号：________________________

一、选择题（每题1分，共31题，第31题2分，总32分）

（1）设有如下遗产继承规则：丈夫和妻子可以互相继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。表示该遗产继承关系最合适的数据结构应该是（ ）。

A.树 B.图 C.数组 D.二叉树 （2）在数据结构中，从逻辑上可以把数据结构分成（ ）。 A.动态结构和静态结构 B. 紧凑结构和非紧凑结构 C.线性结构和非线性结构 D. 内部结构和外部结构 （3）以下数据结构中不属于线性数据结构的是（ ）。

A.队列 B.线性表 C.二叉树 D.栈 （4）算法的时间复杂度是指（ ）。

A.执行算法程序所需要的时间 B. 算法程序的长度 C.算法执行过程中所需要的基本运算次数 D. 算法程序中的指令条数 （5）算法一般可以由哪几种控制结构组合而成（ ）。

A.循环、分支、递归 B. 顺序、循环、嵌套 C. 循环、递归、选择 D. 顺序、选择、循环

（6）计算机算法指的是解决问题的步骤序列，它必须具备（ ）这三个特性。

A. 可执行性、可移植性、可扩充性 B. 可执行性、确定性、有穷性 C.确定性、有穷性、稳定性 D. 易读性、稳定性、安全性 （7）在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是（ ）。

A. p=NULL B. p→next=NULL

《数据结构与算法》试题卷第1页（共6页） 《数据结构与算法》试题卷第2页（共6页）

XXXXXXX学校试题卷

（17）在一棵二叉树上，第5层的结点数最多为（ ）。

A. 8 B. 15 C. 16 D. 32 （18）对于下边的二叉树，其中序序列为（ ）。

A.DBAFCG B.DBAFGC C.ABDCFG D.ABCDFG A

B C D F G

（19）对于下面的二叉树，其中序序列为（ ）。

A.ABCDEFG B.ABCECFG C.DBEAFCG D.ADEBCFG A B C D E F G

（20）由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（ ）。

A.24 B.48 C.72 D.53 （21）二叉树的先序遍历和中序遍历如下：

先序遍历：EFHIGJK 中序遍历：HFIEJKG

该二叉根的右子树的根是（ ）。

A.E B. F C. G D. H （22）具有127个结点的完全二叉树其深度为（ ）。 A.8 B. 7 C. 6 D. 5

《数据结构与算法》试题卷第3页（共6页）

（23）哈夫曼树是（ ）。

A.满二叉树 B.二叉排序树

C.树的路径长度最短的二叉树 D.带权路径长度最短的二叉树 （24）由带权9,1,3,5,6的五个叶子结点生成的哈夫曼树的带权路径长度为（ ）。

A. 50 B. 60 C. 52 D. 65

（25）深度为k的完全二叉树所含叶结点的个数最多为（ ）。

A. 2k B. 2k -1 C. k D. 2k

（26）具有10个叶结点的二叉树中有（ ）个度为2的结点。

A.8 B. 9 C. 10 D. 11

（27）给定下列有向图，从顶点v1出发，其深度优先搜索序列为（ ）。

A.12534 B. 12435 C. 14325 D. 12345 3

2 1

4 5

（28）在顺序表（3,6,8,10,12,15,16,18,21,25,30）中，用折半法查找关键码值11，所需的关键码比较次数为（ ）。

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

（29）权值为{1,2,6,8}的四个结点构成的哈夫曼树的带权路径长度是（ ）。

A. 18 B. 28 C.19 D. 29 0 1 0 （30）对于有向图的邻接矩阵A= 1 0 1 ，该图共有（ ）条弧。 0 1 0 A. 0123 B. 1123 C. 1231 D.1211

《数据结构与算法》试题卷第4页（共6页）

XXXXXXX学校试题卷

二、填空题（每题2分，共10题，总20分） （1）数据的逻辑结构有__________、_________、_________、_________四种。 （2）数据的存储结构有_______、__________、__________、_________四种。 （3）线性结构元素之间是_______对________的关系；树形结构元素之间的关系是__________；图形结构元素之间的关系是_________。 （4）单链表的结点空间包括两部分，即_________域和___________域。 （5）单链表的__________和__________操作大多数情况下要优于顺序表。 （6）线性表中___________________称为表的长度。 （7）设长度为n的线性表顺序存储，若在它的第i-1和第i个元素之间插入 （2）已知二叉树的中序序列为DBHEIAFJCKG，先序序列为ABDEHICFJGK，请画出该二叉树。 （3）对于给定的5个实数W={8,5,13,2,6}，试构造哈夫曼树，并求出该树的最小带权路径长度。 一个元素，共需移动__________个元素。 （8）插入限定在表的一端，而删除限定在表的另一端进行的线性表称为____________，允许插入的一端称为___________。 （9）______________是限定仅在表尾进行或删除操作的线性表。 （10）队列的特点是__________________。 三、应用题（每题12分，共4题） （1）对下图进行如下操作： ○1写出其邻接矩阵。 ○2求从顶点V5出发的广度优先搜索遍历序列。 V1 V2 V3 （4）请分别写出下列二叉树的先序、中序和后序序列。 A B V4 V5 V6 D E C F I 《数据结构与算法》试题卷第5页（共6页） 《数据结构与算法》试题卷第6页（共6页） G H