北京航空航天大学程序设计与数据结构试题
(2002年)
一、简答题
1. “数据结构”课程是计算机专业的基础课还是专业课，或者专业基础课？(2’)
2. 学习“数据结构”课程需要哪些课程作为它的基础(举例两门课程)？若没有这些知识，对学习“数据结构”课程可能会产生哪些影响？请举例说明(不超过100字)。(4’)
3. “数据结构”课程将为那些课程学习奠定必要的基础？请举例说明哪些课程(举例两门课程)用到了“数据结构”课程的哪些知识(不超过100字)。(4’)
二、(5’)
请推导出结论：具有n0个叶结点的哈夫曼树(Huffman)的分支总数为2(n0-1)。
三、单项选择题(2’x15)
1. 线性链表中各链接点之间的地址__________。
A)必须连续B)部分地址必须连续
C)不一定连续D)连续与否无所谓
2. 在非空线性链表中由p所指的链接点后面插入一个由q所致的链接点的
过程是依次执行动作__________。
A) link(q)←p; link(p)←q; B) link(q)←link(p); link(p)←q;
C) link(q)←link(p); p←q; D) link(p)←q; link(q)←p;
3. 在非空双向循环链表中由q所指的那个链接点前插入一个p指的链接点
的动作对应的语句依次为rlink(p)←q, llink(p)←llink(q), llink(q)←p, __________。(空白处为一条赋值语句)
A) rlink(q)←p B) rlink(llink(q))←p
C) rlink(llink(p))←p D) rlink(rlink(p))←p
4. 在初始为空的堆栈中依次插入元素f，e，d，c，b，a以后，连续进行了
三次删除操作，此时栈顶元素是__________。
A) c B) d C) b D) e
5. 若某堆栈的输入序列为1，2，3，……，n，输出序列的第1个元素为n，
则第i个输出元素为__________。
A) i B) n-i C) n-i+1 D)哪个元素无所谓
6. 求字符串T在字符串S中首次出现的位置的操作称为__________。
A)求串的长度B)求子串C)串的模式匹配D)串的连接
7. 若一棵度为7的树有8个度为1的结点，有7个度为2的结点，有6个
度为3的结点，有5个度为4的结点，有4个度为5的结点，有3个度为6的结点，有2个度为7的结点，该树一共有__________个叶结点。
A) 35 B) 28 C) 77 D) 78
8. 若一棵二叉树有1001个结点，且无度为1的结点，则叶结点的个数为
__________。
A)498 B)499 C)500 D)501
9. 已知某完全二叉树采用顺序存储结构，结点数据信息的存放顺序依次为
A、B、C、D、E、F、G、H，该完全二叉树的后序遍历序列为__________。
A)HDEBFGCA B)HEDBFGCA C)HDEBAFGC D)HDEFGBCA
10.若某带权图为G=(V，E)，其中V={v1，v2，v3，v4，v5，v6，v7，v8，v9，
v10}，E={(v1，v2)5，(v1，v3)6，(v2，v5)3，(v3，v5)6，(v3，v4)3，(v4，v5)3，(v4，v7)1，(v4，v8)4，(v5，v6)4，(v5，v7)2，(v6，v10)4，(v7，v9)5，(v8，v9)2，(v9，v10)2}(注：顶点偶对右下角的数据表示边上的权值)，则G的关键路径的长度为__________。
A)19 B)20 C)21 D)22
11.顺序查找法适合于存储结构为__________的线性表。
A)顺序存储结构或链式存储结构B)散列存储结构
C)索引存储结构D)压缩存储结构
12.当n足够大时，在按值有序的顺序表中进行折半查找，当查找概率相等
的情况下，其查找成功的平均查找长度是__________。
A)(n+1)/2 B)n/2 C)log2(n+1)-1 D)log2(n+1)
13.下述命题中，不成立的应是__________。
A)m阶B树中的每一个分支结点的子树的个数都小于或等于m
B)m阶B树中的每一个分支结点的子树的个数都大于或等于?m/2?
C)m阶B树中的任何一个结点的子树的高度都相等
D)m阶B树中有k个子树的分支结点包含k-1个关键字
14.已知散列范围为[0..9]，散列函数(哈希函数)为H(key)=key MOD 9，处理
冲突的方法为线性探测再散列法，依次插入关键字序列8，18，25，44，34，21，19，23后的哈希表为__________。
A)
B)
C)
D)
15.
A)插入排序法B)选择排序法C)拓扑排序法D)归并排序法
四、(15’)
请设计一个事件复杂度为O(n)，空间复杂度不超过O(2)的算法，该算法将数组A[0:n-1]中所有元素循环右移k个位置。
五、(15’)
已知某二叉树采用广义表形式作为输入，请写一非递归算法，建立该
二叉树的二叉链表存储结构。设该链接点构造为lchild data rchild，根结点地址为T。
关于采用广义表形式表示二叉树的约定如下：
●表中的一个字母表示一个结点的数据信息；
●每个根结点作为由子树构成的表的构成的表的名字放在表的前面；
●每个结点的左子树与右子树之间用逗号分开；若只有右子树而无左
子树，则逗号不能省略；
●整个广义表的末尾由一个特殊符号@作为表的结束标志。
例如：(A(B(D),C(F(,E),G))@表示某一棵二叉树，该二叉树的根结点数据信息为A。其中，数据信息为F的结点只有右子树，而无左子树。
六、(1’x10)
在下面给出的C函数实现中的__________处填上适当的内容，使其完成正确的功能。
函数说明：函数void ftoa(double f, char s[])将浮点数f转换成相应的字符串，并存放在s中，该函数最多只能转换小数点后四位，如123.45将转换成“123.45”，-123.456789将转换成“-123.4567”。
void ftoa(double f, char s[])
{
int i,j,len,c,n;
double sign;
if((sign=f)<0)
f=-f;
n=(int)f;
i=0;
do{
s[i++]=n%10+__________;
}while(__________);
if(sign<0)
__________;
len=i;
for(i=0,j=len-1;__________;__________){
c=s[i];
__________;
s[j]=c;
}
f-=(int)f;
s[len++]=__________;
for(i=0;i<4;i++){
f*=10;
s[len++]=__________;
}
while(s[len-1]==’0’)
__________;
s[len]=__________;
}
七、(15’)
命令tail用来打印文件中最后n行。命令格式为：
tail [-n] filename
其中
-n: n表示需要打印的行数，当省略此参数时，n的缺省值为10。
filename: 给定文件名。
例如，命令tail –20 example.txt表示打印文件example.txt的最后20行。
请用C语言实现该程序，该程序应具有一定的错误处理能力，例如能处理非法命令参数和非法文件名。
提示1：使用命令行参数；
提示2：可以使用下面的C库函数：
-int atoi(char *s)将数字串转换为相应整数；
-fopen, fclose, printf, fprintf, exit；
-fgets(char *s, int n, FILE *fp)从文件中读入一行；
-void *malloc(unsigned size), free申请和释放内存；
-strlen计算字符串长度；
-strcpy将一个字符串拷贝到另一个字符串中。
除此之外，不允许使用其它库函数。
数据库期末试题2010级 友情提醒：闭卷考试，有一定难度，英文，考试时间2小时，需要好好复习。建议好好做那份样卷（即09年试卷），大题目题型和那上面差不多，选择改为了判断，我们这届没有简答题。 题型：判断（10题），简答题（5题） 判断题没有记录，主要考基本概念。 简答题： （1）事务，串行化调度，两阶段锁协议 （2）Sql语句和关系代数语句写出查询 （3）ER图设计并写出关系主键，外键等 （4）给出函数依赖，并且推断属于何种范式（BCNF，第三范式） （5）题目给出关系表与关系代数表达式，求出运算结果
班号学号姓名成绩 《数据库系统概论》期末考试卷 注意事项：1、考试时间2小时； 2、答案写在答题纸上 题目： 一、……………………………………………………………( 分) 二、……………………………………………………………( 分) 三、……………………………………………………………( 分) 四、……………………………………………………………( 分) 五、……………………………………………………………( 分) 六、……………………………………………………………( 分)
一：单选题(本大题共12小题，每小题3分，共36分) 1. 对现实世界进行第一层抽象的是【 D 】 A. 用户数据模型 B. 物理数据模型 C. 逻辑数据模型 D. 概念数据模型 2. 以下不属于集合运算的是________。【 C 】 A. 并 B. 广义笛卡尔积 C. 除 D. 差 3. 若一个关系有函数依赖集（AB→CD, A→D），则可确定它最高属于：【 A 】 A. 1NF B. 2NF C. 3NF D. BCNF 4. 以下哪个SQL语句没有语法错误【 A 】 A. Grant select on TableA to User1 with grant option B. select count(a) from b where count(a)>3 C. insert into TableA set a=1, b=2 D. drop TableA where a=1 5. 定义学生对象来表示张三、李四等学生个体，这种抽象方法被称为【A】 A. 分类 B. 聚集 C. 类比 D. 概括 6. 哪一级封锁协议解决了读脏数据问题？【B】 A. 一级封锁协议 B.二级封锁协议 C. 三级封锁协议 D. 以上都不是 7. 工资表（职工号，岗位级别，岗位工资）中有如下约束：岗位级别低的职工的岗位工资 应低于岗位级别高的职工的岗位工资。这种约束属于什么约束类型？【 E】 A. 静态列级约束 B. 动态列级约束 C. 静态元组约束 D. 动态元组约束 E. 静态关系约束 F. 动态关系约束 8. 设有关系R（A，B，C）的值如下：
一、选择题 1.在逻辑上可以把数据结构分成（） A.线性结构和非线性结构 B.动态结构和静态结构 C.紧凑结构和非紧凑结构 D.内部结构和外部结构 2.单链表中各结点之间的地址（） A.必须连续 B.部分必须连续 C.不一定连续 D.以上均不对 3.在一个长度为n的顺序表中向第i个元素（0
第1章绪论 习题 1．简述下列概念：数据、数据元素、数据项、数据对象、数据结构、逻辑结构、存储结构、抽象数据类型。2．试举一个数据结构的例子，叙述其逻辑结构和存储结构两方面的含义和相互关系。 3．简述逻辑结构的四种基本关系并画出它们的关系图。 4．存储结构由哪两种基本的存储方法实现 5．选择题 （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．栈 6．试分析下面各程序段的时间复杂度。 （1）x=90;y=100; while(y>0) if(x>100) {x=x-10;y--;} elsex++; （2）for(i=0;i 北京航空航天大学现代远程教育 2015年3月份《数据库原理及应用》课程考试试卷 注意事项： 1、本试卷满分100分；考试时间：90分钟；考试形式：开卷 2、请将答案一律写在答题纸上，试卷上作答无效 3、考试结束后，考生将试卷及答题纸一并交回 4、请将条形码贴在答题纸的指定位置 学习中心______________姓名____________学号____________ 一、单项选择题（本大题共20小题，每小题1.5分，共30分） 1、第一代数据模型是指（）。 A．关系模型B．网络模型 C．面向对象模型D．人工智能模型 2、SQL语言中授权的操作是通过（）语句实现的。 A．CREATE B．REVOKE C．GRANT D．INSERT 3、SQL Server是一个基于（）。 A．层次模型的DBMS B．网状模型的DBMS C．关系模型的应用程序D．关系模型的DBMS 4、一个m:n联系转换为一个关系模式。关系的码为（）。 A．某个实体的码B．各实体码的组合 C．n端实体的码D．任意一个实体的码 5、手工处理阶段是（）。 A．计算机数据处理技术发展的初级阶段 B．计算机数据管理技术发展的初级阶段 C．计算机数据处理技术发展的中级阶段 D．计算机数据管理技术发展的中级阶段 6、在DBS中，DBMS和OS之间的关系是（）。 A．相互调用B．DBMS调用OS C．OS调用DBMS D．并发运行7、数据库保护的几个方面中，不包括的是（）。 A．控制数据冗余B．并发控制 C．完整性保护D．故障恢复 8、（）是长期存储在计算机内的有组织、可共享的数据集合。 A．数据库管理系统B．数据库系统 C．数据库D．文件组织 9、数据库系统包括（）。 A．DB、DBMS B．DB、DBA C．DB、DBMS、DBA、计算机硬件 D．DB、DBMS、DBA、OS、计算机硬件 10、SQL语言具有（）的功能。 A．关系规范化、数据操纵、数据控制 B．数据定义、数据操纵、数据控制 C．数据定义、关系规范化、数据控制 D．数据定义、关系规范化、数据操纵 11、部分匹配查询中有关匹配符“_”的正确的叙述是（）。 A．“_”代表任意单个字符 B．“_”可以代表零个或多个字符 C．“_”不能与“%”一同使用 D．“_”代表一个字符 12、规范化过程主要是为了克服数据库逻辑结构中的插入异常、删除异常以及（）的缺陷。 A．数据的不一致性B．结构不合理 C．冗余度大D．数据丢失 13、SQL 语言集数据查询、数据操作、数据定义和数据控制功能于一体，语句INSERT、DELETE、UPDATA实现下列（）功能。 A．数据查询B．数据操纵 C．数据定义D．数据控制 14、下列命题中不正确的是（）。 A．数据库减少了不必要的数据冗余 B．数据库中不存在冗余数据 Advanced Structural Dynamics Project The dynamic response and stability analysis of the beam under vertical excitation Instructor：Dr. Li Wei Name： Student ID： 1.Problem description and thepurpose of the project 1.1 calculation model An Eular beam subjected to an axial force. Please build thedifferential equation of motion and use a proper difference method to solve this differentialequation. Study the dynamic stability of the beam related to the frequency and amplitude of the force. As shown in the Fig 1.1. Fig1.1 1.2 purpose and process arrangement a.learninghow to create mathematical model of thecontinuous system and select proper calculation method to solve it. b.learning how to build beam vibration equation and solve Mathieu equation. https://www.doczj.com/doc/f69408065.html,ing Floquet theory to judgevibration system’s stability and analyze the relationship among the frequency and amplitude of the force and dynamic response. This project will introduce the establishment of the mathematical model of the continuous system in section 2, the movement equation and the numerical solution of using MATLAB in section 3,Applying Floquent theory to study the dynamic stability of the beam related to the frequency and amplitude of the force in section 4. In the last of the project, we get some conclusions in section 5. 2013年''数据结构与C程序设计〃（代码991）试题 一、单项选择题（本题共20分，每小题各2分） 1.对于长度为n的线性表.建立其对应的做链表的时间复杂度为（）。 A.0（1）： B. O（log2n）：? O（n）： D? O（n2）。 2.一般情况下，在一个双向链表中插入一个新的链结点，（）o A.需要修改4个抬针域内的指针： B.需要修改3个指针域内的指针： C.需要修改2个指针域内的抬针：D?只需要修改1个指针域内的指针。 3.假设用单?个字母表示中缀表达式中的一个运算数（或称运算对&）?并利用堆栈产生中缀表达式对应的后缀表达式。对于中缀表达式A+B*（C/D-E）,十从左至右扫描到运算数E时，堆栈中的运算符依次是（）。（注：不包含表达式的分界符） A.+*/-： B. +*（/-： C? +*-：? +*（-o 4.若某二叉排序树的前序遍历序列为50,20,40,30,80,60,70.则后序遍历序列为（）。 A. 30,40,20,50,70,60,80： B. 30,40,20,70,60,80,50： C. 70,60,80,50,30,40,20： D. 70,60,80,30,40,20,50. 5.分别以6, 3, 8, 12, 5Z 7对应叶结点的权值构造的哈夫曼（Huffman）树的深度为（）。 A. 6： B. 5： C? 4： D? 3。 &下列关于图的叙述中，错误的是（）0 A.根据图的定义，图中至少有一个顶点： B.根据图的定义.图中至少有一个顶点和一条边（弧）： C.具有n个顶点的无向图最女有n（n-l）/2条边； D.具有n个顶点的有向图最多有n（n-l）条边（弧）。 7.若在有向图G的拓扑序列中，顶点vi在顶点vj之前，则下列4种情形中不可能出现的是（）》 A.G中有弧 B.G中没有弧vvi,vj＞： C.G中有一条从顶点vi到顶点vj的路径： D?G中有一条从顶点vj到顶点vi的路径。 8.下列关于査找操作的叙述中.错误的是（）。 A.在顺序表中査找元素可以采用顺序查找法，也可以采用折半査找法： B.在链表中査找结点只能采用顺序査找法，不能采用折半査找法： C.一般情况下，顺序査找法不如折半查找法的时间效率商： D.折半査找的过程可以用一棵称之为''判定树"的二叉树來描述。 9.在一棵m阶B?树中，除根结点之外的任何分支结点包含关键字的个数至少是（）。 A. m/2-1： B? m/2： C? m/2-l： D? m/2° 10.若对序列（49, 38, 65, 97, 76, 13, 27f 49J进行快速排序，则第一趙排序结束（即确定了第1个分界元素的最终位宜）时.序列的状态是（）。 A. （13, 27, 49； 38, 49, 76, 97, 65）： B. （13, 38, 27, 49； 49, 76, 97, 65）： C. （13, 38, 49； 27, 49, 97, 76, 65）： D. （13, 38, 49；27t 49z 76, 97, 65）。 二、填空题（本题共20分，每小题各2分） 习 9解答 判断题： 1．用向量和单链表表示的有序表均可使用折半查找方法来提高查找速度。 答：FALSE (错。链表表示的有序表不能用折半查找法。) 2.有n 个数据放在一维数组A[1..n]中，在进行顺序查找时，这n 个数的排列有序或无序其平均查找长度不同。 答：FALSE (错。因顺序查找既适合于有序表也适合于无序表；对这两种表，若对于每个元素的查找概率相等，则顺序查找的ASL 相同，并且都是(n+1)/2；对于查找概率不同的情况，则按查找概率由大到小排序的无序表其ASL 要比有序表的ASL 小。) 3.折半查找是先确定待查有序表记录的范围，然后逐步缩小范围，直到找到或找不到该记录为止。( ) 答：TRUE 4.哈希表的查找效率主要取决于哈希表哈希表造表时选取的哈希函数和处理冲突的方法。 答：TRUE 5.查找表是由同一类型的数据元素(或记录)构成的集合。 答：TRUE 单选题： 6.对于18个元素的有序表采用二分(折半)查找，则查找A[3]的比较序列的下标为( )。 A. 1、2、3 B. 9、5、2、3 C. 9、5、3 D.9、4、2、3 答：D (第一次??2/)181(+ = 9,第二次??2/)81(+ = 4，第三次??2/)31(+ = 2, (第四次??2/)33(+ = 3，故选D. 7. 顺序查找法适合于存储结构为____________的线性表。 A.散列存储 B.顺序存储或链式存储 C.压缩存储 D.索引存储 答：B 8.对线性表进行二分查找时，要求线性表必须( )。 A ．以顺序方式存储 B. 以链接方式存储 C ．以顺序方式存储，且结点按关键字有序排序 D. 以链接方式存储，且结点按关键字有序排序 答：C 9.设哈希表长m=14，哈希函数为H(k) = k MOD 11。表中已有4个记录(如下图 2011 年硕士研究生入学考试 “数据结构与C语言程序设计”(科目代码:991)试题与答案 一、单项选择题(本题共20分，每小题各2分) 1．下列关于线性表的存储结构的叙述中，错误的是。 A．线性表的顺序存储结构中隐式地存储了数据元素之间的逻辑关系 B．线性表的顺序存储结构一定需要占用一片地址连续的存储空间 C．线性表的链式存储结构通过指针来反映数据元素之间的逻辑关系 D．线性表的链式存储结构占用的存储空间一定不连续 2．若front 和rear 分别表示链接队列的队头指针与队尾指针，则向队列中插入一个由p 指的新元素的过程是依次执行。 A．rear=p; front=p; B．front=p; rear=p; C．rear->link=p; rear=p; D．front->link=p; rear=p; 3．下列关于二叉树的叙述中，正确的是。 A．二叉树的度可以小于2 B．二叉树的度等于2 C．二叉树中至少有一个结点的度为2 D．二叉树中每一个结点的度都为2 4．若某二叉树有40个叶结点，则该二叉树的结点总数最少是。 A．78 B．79 C．80 D．81 5．若采用邻接矩阵存储一个有向图，且邻接矩阵主对角线以下元素均为0，则该有向图的拓扑序列。 A．存在且惟一B．存在但可能不惟一 C．不存在D．无法确定 6．下面关于AOE 网的叙述中，正确的是。 A．AOE 网是一个带权的连通图 B．AOE 网是一个带权的强连通图 C．AOE 网是一个带权的无回路的连通图 D．AOE 网是一个带权且无回路的有向图 7．下列关于线性表查找方法的叙述中，错误的是。 A．顺序查找法适合于采用顺序存储结构和链式存储结构的线性表的查找 B．对于相同元素，顺序查找法一定能够查找到表中首次出现的元素 C．对于相同元素，折半查找法一定能够查找到表中首次出现的元素 D．对于相同元素，折半查找法不一定能够查找到表中首次出现的元素 8．在二叉排序树中进行查找的平均时间效率主要与下列因素之一有关，该因素是。A．二叉排序树的深度B．二叉排序树中结点的个数的多少 C．被查找结点的度D．二叉排序树的存储结构 9．下列4 种排序方法中，每一趟排序结束时不一定能够确定一个元素排序最终位置的是。 A．插入排序B．快速排序 C．堆积(Heap)排序D．二路归并排序 2 10．下列4 种排序方法中，当待排序的序列中元素初始时已经按值有序，排序所花费的 一、单选题（共 25 道试题，共 100 分。）V 1. 数据库物理存储方式的描述称为( ) A. 外模式 B. 内模式 C. 概念模式 D. 逻辑模式 满分：4 分 2. DB、DBMS和DBS三者之间的关系是( ) A. DB包括DBMS和DBS B. DBS包括DB和DBMS C. DBMS包括DB和DBS D. 不能相互包括 满分：4 分 3. 在关系模型中，实现"关系中不允许出现相同的元组"的约束是通过______。 A. 候选键 B. 主键 C. 外键 D. 超键 满分：4 分 4. 数据库中只存放视图的 A. 操作 B. 对应的数据 C. 定义 D. 限制 满分：4 分 5. 从一个数据库文件中取出满足某个条件的所有记录形成一个新的数据库文件的操作是（）操作。 A. 投影 B. 连接 C. 选择 D. 复制 满分：4 分 6. 在SQL中，删除视图用______。 A. DROP SCHEMA命令 B. CREATE TABLE命令 C. DROP VIEW命令 D. DROP INDEX命令 满分：4 分 7. DBAS指的是______。 A. 数据库管理系统 B. 数据库系统 C. 数据库应用系统 D. 数据库服务系统 满分：4 分 8. 设有关系模式W(C,P,S,G,T,R),其中各属性的含义是：C课程,P教师,S学生,G成绩,T 时间,R教室，根据定义有如下数据依赖集：D={C→G，(S,C)→G,(T,R)→C,(T,P)→R,(T,S)→R}关系模式W的一个关键字是__，W的规范化程度最高达到__（）。 A. (S,C),1NF B. (T,R),3NF C. (T,P),4NF D. (T,S),2NF 满分：4 分 9. 设有关系R1和R2，经过关系运算得到结果S，则S是______。 A. 一个关系 B. 一个表单 C. 一个数据库 D. 一个数组 满分：4 分 10. （）是控制数据整体结构的人，负责三级结构定义和修改 A. 专业用户 B. 应用程序员 C. DBA D. 一般用户 满分：4 分 11. 数据库设计属于（）。 A. 程序设计范畴 B. 管理科学范畴 C. 系统工程范畴 D. 软件工程范畴 满分：4 分 12. 下述（）不是DBA数据库管理员的职责。 A. 完整性约束说明 B. 定义数据库模式 C. 数据库安全 D. 数据库管理系统设计 满分：4 分 13. 对象标识具有唯一性，其唯一性的范围是在____ A. 对象内 B. 类内 C. 类层次内 D. 系统内 满分：4 分 14. 已知关系R（P，Q，M，N），F是R上成立的函数依赖集，F={（P→Q，Q→M）}，则R 的侯选码是（）。 A. P B. Q C. PQ D. PN 满分：4 分 大学 《数据结构与算法分析》课程 习题及参考答案 模拟试卷一 一、单选题（每题 2 分，共20分） 1.以下数据结构中哪一个是线性结构？( ) A. 有向图 B. 队列 C. 线索二叉树 D. B树 2.在一个单链表HL中，若要在当前由指针p指向的结点后面插入一个由q指向的结点， 则执行如下( )语句序列。 A. p=q; p->next=q; B. p->next=q; q->next=p; C. p->next=q->next; p=q; D. q->next=p->next; p->next=q; 3.以下哪一个不是队列的基本运算？（） A. 在队列第i个元素之后插入一个元素 B. 从队头删除一个元素 C. 判断一个队列是否为空 D.读取队头元素的值 4.字符A、B、C依次进入一个栈，按出栈的先后顺序组成不同的字符串，至多可以组成( ) 个不同的字符串？ A.14 B.5 C.6 D.8 5.由权值分别为3,8,6,2的叶子生成一棵哈夫曼树，它的带权路径长度为( )。 以下6-8题基于图1。 6.该二叉树结点的前序遍历的序列为( )。 A.E、G、F、A、C、D、B B.E、A、G、C、F、B、D C.E、A、C、B、D、G、F D.E、G、A、C、D、F、B 7.该二叉树结点的中序遍历的序列为( )。 A. A、B、C、D、E、G、F B. E、A、G、C、F、B、D C. E、A、C、B、D、G、F E.B、D、C、A、F、G、E 8.该二叉树的按层遍历的序列为( )。 A．E、G、F、A、C、D、B B. E、A、C、B、D、G、F C. E、A、G、C、F、B、D D. E、G、A、C、D、F、B 9.下面关于图的存储的叙述中正确的是( )。 A．用邻接表法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 B．用邻接表法存储图，占用的存储空间大小与图中边数和结点个数都有关 C. 用邻接矩阵法存储图，占用的存储空间大小与图中结点个数和边数都有关 D．用邻接矩阵法存储图，占用的存储空间大小只与图中边数有关，而与结点个数无关 10.设有关键码序列(q，g，m，z，a，n，p，x，h)，下面哪一个序列是从上述序列出发建 堆的结果?( ) A. a，g，h，m，n，p，q，x，z B. a，g，m，h，q，n，p，x，z C. g，m，q，a，n，p，x，h，z D. h，g，m，p，a，n，q，x，z 二、填空题（每空1分，共26分） 1.数据的物理结构被分为_________、________、__________和___________四种。 2.对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为_________， 在表尾插入元素的时间复杂度为____________。 3.向一个由HS指向的链栈中插入一个结点时p时，需要执行的操作是________________; 删除一个结点时，需要执行的操作是______________________________（假设栈不空而 且无需回收被删除结点）。 4.对于一棵具有n个结点的二叉树，一个结点的编号为i(1≤i≤n)，若它有左孩子则左 孩子结点的编号为________，若它有右孩子，则右孩子结点的编号为________，若它有 双亲，则双亲结点的编号为________。 5.当向一个大根堆插入一个具有最大值的元素时，需要逐层_________调整，直到被调整 到____________位置为止。 6.以二分查找方法从长度为10的有序表中查找一个元素时，平均查找长度为________。 7.表示图的三种常用的存储结构为_____________、____________和_______________。 8.对于线性表（70，34，55，23，65，41，20）进行散列存储时，若选用H（K）=K %7 作为散列函数，则散列地址为0的元素有________个，散列地址为6的有_______个。 9.在归并排序中，进行每趟归并的时间复杂度为______，整个排序过程的时间复杂度为 ____________，空间复杂度为___________。 10.在一棵m阶B_树上，每个非树根结点的关键字数目最少为________个，最多为________ 个，其子树数目最少为________，最多为________。 三、运算题（每题 6 分，共24分） 1.写出下列中缀表达式的后缀形式： （1）3X/(Y-2)+1 （2）2+X*(Y+3) 2.试对图2中的二叉树画出其： (1)顺序存储表示的示意图； (2)二叉链表存储表示的示意图。 3.判断以下序列是否是小根堆? 如果不是, 将它调 图2 整为小根堆。 （1）{ 12, 70, 33, 65, 24, 56, 48, 92, 86, 33 } （2）{ 05, 23, 20, 28, 40, 38, 29, 61, 35, 76, 47, 100 } 4.已知一个图的顶点集V和边集E分别为： V={1,2,3,4,5,6,7}; 北航《算法与数据结构》在线作业二 单选题 一、单选题（共25 道试题，共100 分。） 1. 对顺序表上的插入、删除算法的时间复杂性分析来说，通常以（）为标准操作 A. 条件判断 B. 结点移动 C. 算术表达式 D. 赋值语句 -----------------选择：B 2. 在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（）。 A. HL=p;p->next=HL; B. p->next=HL;HL=p; C. p->next=HL;p=HL; D. p->next=HL->next;HL->next=p; -----------------选择：B 3. 线性表是一个具有n个（）的有限序列。 A. 表元素 B. 字符 C. 数据元素 D. 数据项 -----------------选择：C 4. 若给定的关键字集合为{20，15，14，18，21，36，40，10}，一趟快速排序结束时，键值的排列为( )。 A. 10，15，14，18，20，36，40，21 B. 10，15，14，18，20，40，36，21 C. 10，15，14，20，18，40，36，21 D. 15，10，14，18，20，36，40，21 -----------------选择：A 5. 按照二叉树的定义，具有3个结点的二叉树有（）种。 A. 3 B. 4 C. 5 D. 6 -----------------选择：C 6. 下列有关图遍历的说法中不正确的是（）。 A. 连通图的深度优先搜索是个递增过程 B. 图的广度优先搜索中邻接点的寻找具有“先进先出”的特征 C. 非连通图不能用深度优先搜索法 D. 图的遍历要求每个顶点仅被访问一次 -----------------选择：C 7. Substr('DATA STRUCTURE'，5，9)=（）。 A. STRUCTURE' B. 'ASTUCTUR' C. 'DATA STRUCTRUE' 数据结构与算法试题 一、单选题 1、在数据结构的讨论中把数据结构从逻辑上分为 (C ) A 内部结构与外部结构 B 静态结构与动态结构 C 线性结构与非线性结构 D 紧凑结构与非紧凑结构。 2、采用线性链表表示一个向量时,要求占用的存储空间地址(D ) A 必须就是连续的 B 部分地址必须就是连续的 C 一定就是不连续的 D 可连续可不连续 3、采用顺序搜索方法查找长度为n的顺序表时,搜索成功的平均搜索长度为( D )。 A n B n/2 C (n-1)/2 D (n+1)/2 4、在一个单链表中,若q结点就是p结点的前驱结点,若在q与p之间插入结点s,则执行( D )。 A s→link = p→link;p→link = s; B p→link = s; s→link = q; C p→link = s→link;s→link = p; D q→link = s;s→link = p; 5、如果想在4092个数据中只需要选择其中最小的5个,采用( C )方法最好。 A 起泡排序 B 堆排序 C 锦标赛排序 D 快速排序 6、设有两个串t与p,求p在t中首次出现的位置的运算叫做( B )。 A 求子串 B 模式匹配 C 串替换 D 串连接 7、在数组A中,每一个数组元素A[i][j]占用3个存储字,行下标i从1到8,列下标j从1到10。所有数组元素相继存放于一个连续的存储空间中,则存放该数 组至少需要的存储字数就是( C )。 A 80 B 100 C 240 D 270 8、将一个递归算法改为对应的非递归算法时,通常需要使用( A )。 A 栈 B 队列 C 循环队列 D 优先队列 9、一个队列的进队列顺序就是1, 2, 3, 4,则出队列顺序为( C )。 10、在循环队列中用数组A[0、、m-1] 存放队列元素,其队头与队尾指针分别为front与rear,则当前队列中的元素个数就是( D )。 A ( front - rear + 1) % m B ( rear - front + 1) % m C ( front - rear + m) % m D ( rear - front + m) % m 11、一个数组元素a[i]与( A )的表示等价。 A *(a+i) B a+i C *a+i D &a+i 12、若需要利用形参直接访问实参,则应把形参变量说明为( B )参数。 A 指针 B 引用 C 值 D 变量 13、下面程序段的时间复杂度为( C ) for (int i=0;i 北航2002年程序设计与数据结构试题 一、简答题（10’） 1. 数据结构课程是计算机专业的基础课还是专业课，或者专业基础课？（2’） 2. 学习数据结构课程需要哪些课程作为它的基础（举例两门课程）？若没有这些知识，对学习数据 结构课程可能会产生哪些影响？请举例说明（不超过100字）。（4’） 3. 数据结构课程将为那些课程学习奠定必要的基础？请举例说明哪些课程（举例两门课程）用到了 数据结构课程的哪些知识（不超过100字）。（4’） 二、（5’） 请推导出结论：具有0n 个叶结点的哈夫曼树（Huffman ）的分支总数为02(1)n -。 三、单项选择题（2’×15） 1. 线性链表中各链接点之间的地址________。 A. 必须连续 B. 部分地址必须连续 C. 不一定连续 D. 连续与否无所谓 2. 在非空线性链表中由p 所指的链接点后面插入一个由q 所致的链接点的过程是依次执行动作 ________。 A. link(q)←p; link(p)←q; B. link(q)←link(p); link(p)←q; C. link(q)←link(p); p ←q; D. link(p)←q; link(q)←p; 3. 在非空双向循环链表中由q 所指的那个链接点前插入一个p 指的链接点的动作对应的语句依次为 rlink(p)←q, llink(p)←llink(q), llink(q)←p, ________。（空白处为一条赋值语句） A. rlink(q)←p B. rlink(llink(q))←p C. rlink(llink(p))←p D. rlink(rlink(p))←p 4. 在初始为空的堆栈中依次插入元素f, e, d, c, b, a 以后，连续进行了三次删除操作，此时栈顶元素是 ________。 A. c B. d C. b D. e 5. 若某堆栈的输入序列为1, 2, 3, …, n ，输出序列的第1个元素为n ，则第i 个输出元素为________。 A. i B. n i - C. 1n i -+ D. 哪个元素无所谓 6. 求字符串T 在字符串S 中首次出现的位置的操作称为________。 A. 求串的长度 B. 求子串 C. 串的模式匹配 D. 串的连接 7. 若一棵度为7的树有8个度为1的结点，有7个度为2的结点，有6个度为3的结点，有5个度为 4的结点，有4个度为5的结点，有3个度为6的结点，有2个度为7的结点，该树一共有________个叶结点。 A. 35 B. 28 C. 77 D. 78 8. 若一棵二叉树有1001个结点，且无度为1的结点，则叶结点的个数为________。 A. 498 B. 499 C. 500 D. 501 9. 已知某完全二叉树采用顺序存储结构，结点数据信息的存放顺序依次为ABCDEFGH ，该完全二叉 树的后序遍历序列为________。 国家二级ACCESS机试选择题（数据结构与算法）模拟试卷15 (总分：64.00，做题时间：90分钟) 一、选择题(总题数：32，分数：64.00) 1.设循环队列为Q(1：m)，其初始状态为front=rear=m。经过一系列入队与退队运算后，front=15，rear=20。现要在该循环队列中寻找最大值的元素，最坏情况下需要比较的次数为 （分数：2.00） A.4 √ B.6 C.m-5 D.m-6 解析：解析：初始状态为：front=rear=m，rear-front=0，此时队列为空。经过一系列入队与退队运算后，front=15，rear=20。队尾大于队头，则队尾rear减队头front等于5个元素。此时队列中有5个元素，而查找最大项至少要比较n．1次，就是4次。因此选项A正确。 2.下列叙述中正确的是 （分数：2.00） A.循环队列属于队列的链式存储结构 B.双向链表是二叉树的链式存储结构 C.非线性结构只能采用链式存储结构 D.有的非线性结构也可以采用顺序存储结构√ 解析：解析：顺序存储方式不仅能用于存储线性结构，还可以用来存放非线性结构。例如，完全二叉树是属于非线性结构，但其最佳存储方式是顺序存储方式。 3.某二叉树中有n个叶子结点，则该二叉树中度为2l的结点数为 （分数：2.00） A.n+1 B.n-1 √ C.2n D.n／2 解析：解析：任意一棵二叉树，如果叶结点数为N 0，而度数为2的结点总数为N 2，则N 0 =N 2 +1；N 2 =N 0 -1。所以如果二叉树中有n个叶子结点，则该二叉树中度为2的结点数为n-1。因此选项B正确。4.下列叙述中错误的是 （分数：2.00） A.算法的时间复杂度与算法所处理数据的存储结构有直接关系 B.算法的空间复杂度与算法所处理数据的存储结构有直接关系 C.算法的时间复杂度与空间复杂度有直接关系√ D.算法的时间复杂度与空间复杂度没有必然的联系 解析：解析：算法的时间复杂度，是指执行算法所需要的计算工作量。算法的空间复杂度，是指执行这个算法所需要的内存空间。两者与算法所处理数据的存储结构都有直接关系，但两者之间没有直接关系，因此选项C错误。 5.设栈的顺序存储空间为S(0：49)，栈底指针bottom=49，栈顶指针top=30(指向栈顶元素)。则栈中的元素个数为 （分数：2.00） A.30 B.29 C.20 √ D.19 北航10秋学期《算法与数据结构》模拟题一 一、单项选择题（本大题共15小题，每小题2分，共30分） 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、对一个由n个整数组成的序列，借助排序过程找出其中的最大值，希望比较次数和移动次数最少，应选用（）方法 A．归并排序 B．直接插入排序 C．直接选择排序 D．快速排序。 7、在文件局部有序或文件长度较小的情况下，最佳的排序方法是（） A．直接插入排序 B．冒泡排序 C．直接选择排序 D．归并排序 8、对于C语言的二维数组DataType A[m][n],每个数据元素占K个存储单元，二维数组中任意元素a[i,j] 的存储位置可由（）式确定. A．Loc[i,j]=A[m,n]+[(n+1)*i+j]*k B．Loc[i,j]=loc[0,0]+[(m+n)*i+j]*k C．Loc[i,j]=loc[0,0]+[(n+1)*i+j]*k D．Loc[i,j]=[(n+1)*i+j]*k 广西科技大学2015 —2016 学年第 1 学期课程考核试题试卷 考核课程数据结构与算法（ B 卷）考核班级物联网141 学生数36 印数40 考核方式闭卷考核时间120 分钟 一、单项选择题（在每小题的四个备选答案中，选出一个正确答案。每小题1分，共33分） 1、算法是（）。 A. 计算机程序 B. 解决问题的计算方法 C. 排序算法 D. 解决问题的有限运算序列 2、一个顺序表的第一个元素的存储地址是90，每个元素的长度为2，则第8个元素的存储地址是（）。 A. 102 B. 104 C. 106 D. 108 3、在一个长度为n的顺序表中删除第i个元素，需要向前移动（）个元素。 A. n-i B. n-i+1 C. n-i-1 D. i+1 4、在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next==head，则（）。 A. p指向头结点 B. p指向尾结点 C. p的直接后继是头结点 D. p的直接后继是尾结点 5、在以下的叙述中，正确的是（）。 A. 线性表的顺序存储结构优于链表存储结构 B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况 C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况 D. 线性表的链表存储结构优于顺序存储结构 6、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入一个结点s，则执行（）。 A. s->next=p->next; p->next=s; B. p->next=s->next; s->next=p; C. q->next=s; s->next=p; D. p->next=s; s->next=q; 7、在双向循环链表中，在p指针所指的结点后插入一个指针q所指向的新结点，修改指针的操作是（）。 A. p->next=q; q->prior=p; p->next->prior=q; q->next=q; B. p->next=q; p->next->prior=q; q->prior=p; q->next=p->next; C. q->prior=p; q->next=p->next; p->next->prior=q; p->next=q; D. q->next=p->next; q->prior=p; p->next=q; p->next=q; 8、在单链表中，指针p指向元素为x的结点，实现删除x的后继的语句是（）。 A. p=p->next; B. p->next=p->next->next; C. p->next=p; D.p=p->next->next; 9、在表长为n的顺序表中，当在任何位置删除一个元素的概率相同时，删除一个元素所需移动的平均个数为（）。 A. (n-1)/2 B. n/2 C. (n+1)/2 D. n 10、将长度为n的单链表连接在长度为m的单链表之后的算法的时间复杂度为（）。 A. O(1) B. O(n) C. O(m) D. O(m+n) 11、线性表的顺序存储结构是一种（）存储结构。 A. 随机存取 B. 顺序存取 C. 索引存取 D. 散列存取 12、循环链表的主要优点是（）。 A. 不再需要头指针 B. 已知某结点位置后能容易找到其直接前驱 C. 在进行插入、删除运算时能保证链表不断开 D. 在表中任一结点出发都能扫描整个链表 13、在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是（）。北航15年3月《数据库原理及应用》试卷
高等结构动力学大作业
北航数据结构与程序设计真题-2013北航991真题与答案
数据结构与算法复习题10(C语言版)
北航2011年硕士研究生入学考试数据结构与C语言试题与答案
16春北航《数据库原理及应用》在线作业
数据结构与算法分析习题与参考答案
15秋北航《算法与数据结构》在线作业二100分答案
数据结构与算法试题
北航 1999-2002 程序设计与数据结构考研试题
国家二级ACCESS机试选择题(数据结构与算法)模拟试卷15
北航10秋学期《算法与数据结构》模拟题一
数据结构与算法试卷(B卷)
相关主题
文本预览