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

《《数据结构与算法》期末试题试卷a》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、XXXXXX学校2014-2015学年第一学期期末考试2014级计算机应用专业《数据结构与算法》试题A卷2015年01月19曰$主胃：¥试卷共4页，满分100分，考试时间为90分钟，考试方式为闭卷笔试。姓名：学号：一、选择题(每题1分，共31题，第31题2分，总32分)(1)设有如下遗产继承规则：丈夫和妻子可以互相继承遗产；子女可以继承父亲或母亲的遗产；子女间不能相互继承。表示该遗产继承关系最合适的数据结构应该是A•树B.C.数组D.二叉树(2)在数据结构中，从逻辑上可以把数据结构分成A.动态结构和静态结构C.线性结构和非线性结构B.紧凑结构和非紧凑结构D.内部结构和外部结构(3

2、)以下数据结构中不属于线性数据结构的是A.队列B.线性表C.二叉树D.栈(4)算法的时间复杂度是指(A.执行算法程序所需要的时间C.算法执行过程中所需要的基本运算次数(5)算法一般可以由哪几种控制结构组合而成(B.算法程序的长度D.算法程序中的指令条数A.循环、分支、递归C.循环、递归、选择B.顺序、循环、嵌套I).顺序、选择、循环(6)计算机算法指的是解决问题的步骤序列，它必须具备)这三个特性A.可执行性、可移植性、可扩充性C.确定性、有穷性、稳定性B.可执行性、确定性、有穷性I).易读性、稳定性、安全性(7)在单向循环链表中，若头指针为h，那么p所指结点为尾结点的条件是()(

3、8)带头结点的单链表head为空的判定条件是A.head==NULLB.head)0next==NULLC.headnextheadD.head!=NULL(9)对于栈操作数据的原则是A.先进先出B.后进先出C.后进后出I).不分顺序(10)有六个元素按6,5,4,3,2,1的顺序进栈，问下列哪一个不是合法的出栈序列？A.543612B.453126C.346521D.234156(11)栈s最多能容纳4个元素。现有6个元素按A,B，C,D，E，F的顺序进栈，问B.B,C,E,F,A,I)D.A,D,F,E,B,C下列哪一个序列是可能的出栈序列？A.E，D，C，B，A,FC.C,

4、B,E,D,A,F(12)设abcdef以所给的次序进栈，若在进栈操作时，允许退栈操作，则下面得不到的序列为A.fedcba)oB.bcafedC.dcefbaD.cabdef(13)输入序列为ABC,可以变为CBA时，经过的栈操作为(A.push,pop,push,pop,push,popB.push,push,push,pop,pop,popC.push,push,pop，pop,push,popD.push,pop,push，push,pop,pop(14)己知串S=’aaab’，其next数组值为()。A.0123B.1123C.1231D.1211(15)串”ababa

5、aababaa”的next数组为()A.012345678999C.011234223456B.012121111212I).0123012322345(16)若串S=”software”，其子串的数目是()A.8B.37C.36I).9-T17•广在•二•棵二•叉树士7••第卞赏的结京数最寥为“广了D.32D.ABCDFGB.DBAFGCC.ABDCFGA.ABCDEFGD.ADEBCFGA.8B.15C.16(18)对于下边的二叉树，其中序序列为(A.DBAFCG(19)对于下面的二叉树，其中序序列为((20)由权值分别为3,8,6,2,5的叶子结点生成一棵哈夫曼树，它的带权

6、路径长度为()。A.24B.48C.72D.53(21)二叉树的先序遍历和中序遍历如下：先序遍历：EFHIGJK中序遍历：HFIEJKG该二叉根的右子树的根是()。A.EB.FC.GD.H(20)具有127个结点的完全二叉树其深度为()。A.8B.7C.6D.5(20)哈夫曼树是()。A.满二叉树B.二叉排序树C.树的路径长度最短的二叉树D.带权路径长度最短的二叉树(21)由带权9,1，3,5,6的五个叶子结点生成的哈夫曼树的带权路径长度为()。A.50B.60C.52D.65(22)深度为k的完全二叉树所含叶结点的个数最多为()。A.2kB.2k-1C.kD.2k(23)具有1

7、0个叶结点的二叉树中有()个度为2的结点。A.8B.9C.10D.11(24)给定下列有向图，从顶点出发，其深度优先搜索序列为(D.12345(28)在顺序表(3,6,8,10,12,15,16,18,21，25,30)中，用折半法查找关键码值11，所需的关键码比较次数为()OA.2B.3C.4D.5(29)权值为｛1,2,6,8｝的四个结点构成的哈夫曼树的带权路径长度是()。A.18B.28C.19D.29010(30)对于有向图的邻接矩阵^101，该图共有()条弧。010A.