北京航空航天大学2012年硕士研究生入学考试试题
“数据结构与C语言程序设计”（科目代码：991）
一、填空题(本题共20分，每小题各2分)
1．从总体上说，“数据结构”课程主要研究三个方面的内容。
2．若对某线性表最常用的操作是在表中插入元素或者删除表中元素，则对于顺序存储结构和链式存储结构这两种存储结构而言，线性表应该采用。
3．在长度为n的非空队列中进行插入或者删除操作的时间复杂度用大O符号表示
为。
4．若一棵度为4的树中度为1、2、3和4的结点个数分别为4、2、1和1，则该树中叶结点的个数为。
5．若某二叉树的中序遍历序列为B,A,F,D,G,C,E，按层次遍历序列为A,B,C,D,E,F,G，则该二叉树的后序遍历序列为。
6．将一棵结点总数为n、且具有m个叶结点的树转换为一棵二叉树以后，该二叉树中右子树为空的结点有个。
7．对于图G=(V,E) 与G^=(V^,E^)，若有V^包含于V，E^包含于E，则称G^是G的。8．在顺序表(6,15,30,37,65,68,70,72,89,99)中采用折半查找法查找元素37，与表中进行过比较的元素依次是。
9．若已知n个关键字值具有相同的散列函数值，并且采用线性探测再散列法处理冲突，那么，将这n个关键字值全部散列到初始为空的地址空间中，发生散列冲突的次数是。10．若长度为n的序列K=(k1,k2,…,kn)当且仅当满足ki≤k2i并且ki≤k2i+1(1≤i≤n/2)时，则称该序列为一个小顶堆积(Heap)。根据该定义，序列(26,5,77,1,61,11,59,48,15,19)对应的小顶堆积是。
二、简答题(本题共20分，每小题各5分)
1．如果一个具有100个顶点、200条边的有向图采用邻接矩阵存储，该邻接矩阵是否是稀疏矩阵？为什么？（这里我们假设：当矩阵中非零元素的数目小于整个矩阵总元素的数目的5%时认为该矩阵为稀疏矩阵）
2．一般情况下，建立散列表时难以避免出现散列冲突，常用处理散列冲突的方法之一是开放定址法，该方法的基本思想是什么？
3．若对序列(2,12,16,88,5,10)按值从小到大进行排序，前三趟排序的结果分别为：
第1趟排序的结果：(2,12,16,5,10,88)
第2趟排序的结果：(2,12,5,10,16,88)
第3趟排序的结果：(2,5,10,12,16,88)
请问：该结果是采用了选择排序法还是采用了(起)泡排序法得到的？为什么？
4．快速排序法的排序过程是递归的。若待排序序列的长度为n，则快速排序的最小递归深度与最大递归深度分别是多少？
三、综合题(本题共20分，每小题各5分)
1．若非空双向循环链表中链结点结构为llink data rlink，则依次执行下列4条语句的目的是在该链表中由q指的结点后面插入一个由p指的结点，其中1条语句有错误，请找出该语句，并写出正确的语句。
p->llink=q; /* 第1条语句*/ p->rlink=q>rlink; /* 第2条语句*/
q->rlink=p; /* 第3条语句*/ q->rlink->llink=p; /* 第4条语句*/
2．已知某完全二叉树的第7层有10个叶结点，请求出该完全二叉树的结点总数的最大值。（要求写出结论的求解过程）
3．证明：具有n个顶点的无向图最多有n(n-1)/2条边。
4．请分别写出对数据元素序列(80,30,50,10,90,20) 按值从大到小进行选择排序时每一趟的排序结果。
四、算法设计题（本题15分）
已知某具有n个顶点的有向图采用邻接表方法存储，其中，用以存储有向边信息的边结点类型为
typedef struct edge{
int adjvex; /* 某有向边的终止顶点在顶点结点中的位置*/
struct edge *next; /* 指向下一个边结点*/
}ELink;
用以存储顶点信息的顶点结点类型为
typedef struct ver{
int indegree; /* 某顶点的入度*/
vertype vertex; /* 某顶点的数据信息*/
ELink *link; / * 指向以该顶点为出发点的第一个边结点*/
}VLink;
并且n个顶点结点构成一个数组结构G[0..n-1]。请写一个算法，该算法判断给定的顶点序列V[0..n-1]={v1,v2,v3,…,vn}是否是该有向图的一个拓扑序列，若是该有向图的一个拓扑序列，算法返回1，否则，算法返回0。
五、单项选择题（本题共20分，每小题各2分）
1．在C语言中，标识符只能由字母、数字和下划线三种字符组成，并且第一个字符。A．必须是字母B．必须是下划线
C．必须是字母或者下划线D．可以是字母、数字和下划线之一
2．若整型变量x的初值为6，则计算表达式“x+=x-=x*x”之后，x的值是。
A．50B．60 C．-50 D．-60
3．下列4个程序段中，不是无限循环的是。
A．for(b=0,a=1; a>++b; a=k++) k=a; B．for( ; ; a++=k) ;
C．while(1) { a++; } D．for(k=10; ; k--) total+=k;
4．说明“double (*ptr)[N];”中的标识符ptr是。
A．N个指向double类型变量的指针
B．指向N个double类型变量的函数指针
C．一个指向由N个double类型元素组成的一维数组的指针
D．具有N个指针元素的一维指针数组，其每一个元素都只能指向double类型变量
5．下列4个叙述中，正确的是。
A．char *r=“china”;等价于char *r; *r=“china”;
B．char *ptr=“china”;等价于char *ptr; ptr=“china”;
C．char string[10]={“china”};等价于char stri ng[10]; string[ ]={“china”};
D．char str[4]=“abc”,temp[4]=“abc”;等价于char str[4]=temp[4]=“abc”;
6．在C程序中，语句“char *func(int x,int y);”表示。
A．对函数func的定义B．对函数func的调用
C．对函数func返回值类型的说明D．对函数func的原型说明
7．对于下列程序，若从键盘上输入：abc def<回车>，则输出结果是。
#include
#include
main( )
{ char *p,*q;
p=(char *)malloc(sizeof(char)*20);
q=p;
scanf(“%s%s”,p,q);
printf(“%s%s\n”,p,q);
}
A．defdef B．abcdef C．abc d D．d d
8．当说明一个结构体变量时系统分配给它的内存是。
A．结构中最后一个成员所需的内存量
B．结构中第一个成员所需的内存量
C．成员中占内存量最大者所需的容量
D．各成员所需内存量的总和
9．下列程序的输出结果为。
#define ABC(x) x*x
main( )
{ int a, k=3;
a=++ABC(k+1);
printf(“%d”,a);
}
A．8 B．9 C．14 D．17
10．若要以a+方式打开一个已经存在的文件，则下列叙述中，正确的是。
A．文件被打开时，原有的文件内容不被删除，位置指针移动到文件的末尾，可进
行添加和读操作
B．文件被打开时，原有的文件内容不被删除，位置指针移动到文件的开头，可进
行重写和读操作
C．文件被打开时，原有的文件内容被删除，只能进行写操作
D．以上三种说法都不正确
六、简答题（本题共20分，每小题各5分）
1．在C语言中，头文件的作用是什么?
2．在C语言中，#include “filename.h”和#include
3．在C语言中，全局变量和局部变量的主要区别是什么？
4．字符指针、浮点数指针、以及函数指针这三种类型的变量哪个占用的内存最大？为什么？
七、填空题（本题共20分，每小题各2分）
(说明：由于一些符号无法在本网站显示，本大题中的填空处用(i)表示第i个空----- “答疑”)
1．下列代码的功能包括：定义一个x数组，说明一个结构体，同时对变量t进行初始化，使得t的a成员的值为50，b成员的值为x数组的首地址。
请在空白处(方框内)填入合适的内容，以完成上述功能。
int x[5]={1,2,3,4,5};
struct{ int a,
int *b?
}t{ (1), (2) };
2．下列函数的功能是根据公式s=1-1/3+1/5-1/7+ … + 1/(2n+1)计算s的值，其中，n通过形参传入(n≥0)，计算结果通过形参指针传回。请在函数的空白处填入合适的内容，使函数完整。
void fun(float *sn,int n)
{ float s=0,w,f=-1;
int i;
for(i=0;i<=n;i++){
f= (1);
w=f/(2);
s+=w;
}
*sn=s;
}
3．下列程序实现将输入的一个小写字母循环后移5个位置后输出。例如，若输入字母…a?，则输出字母…f?，若输入字母…w?，则输出字母…b?。请在程序的空白处填入合适的内容，使程序完整。
#include
main( )
{ char c;
c=getchar( );
if(c>=…a?&& c<=…u?)
(1);
else if(c>=…v?&& c<=…z?)
(2);
putchar(c);
}
4．下列自定义函数的功能是实现两个字符串的比较。请在函数的空白处填入合适的内容，使函数完整。
int sstrcmp(char *s,char *t)
{
while(*s && *t && *s== (1) ){
s++; t++; }
return ( (2) );
}
5．下列程序的功能是将已经按升序排好序的两个字符串str1和str2中的字符再按升序归并到字符串str3中。请在程序的空白处填入合适的内容，使程序完整。
#include
main( )
{ char str1[ ]=“acegikm”;
char str2[ ]=“bdfhjlnpq”;
char str3[ ],*p;
int i=0,j=0,k=0;
while(str1[i]!=…\0?&& str2[j]!=…\0?){
if(str1[i] else (1) ; k++; } str3[k]=…\0?; if( (2) ) p=str2+j; else p=str1+i; strcat(str3,p); puts(str3); } 6．对于下列main函数，经过编译、连接后得到的可执行文件名为file.exe，并且已知在系统的命令状态下输入命令行“file Beijing Shanghai<回车>”后得到的输出结果是 Beijing Shanghai 请在函数的空白处填入合适的内容，使函数完整。 main(int argc,char *argv[ ]) { while( (1) ){ ++argv; printf(“%s\n”, (2) ); --argc; } } 7．下列程序的功能是打开两个已存在的文件file1和file2，并将file2拼接到file1的后面。请在程序的空白处填入合适的内容，使程序完整。 #include int main( ) { FILE *fp1,*fp2; if((fp1=fopen(“file1”,“ (1) ”))==NULL){ printf(“Cannot open file1!\n”); return 0; } if((fp2=fopen(“file2”,“ (2) ”))==NULL){ printf(“Cannot open file2!\n”); return 0; } while(!feof( (3) )) fputc( (4) ,fp1); fclose(fp1); fclose(fp2); } 8．设n>0。下列函数的功能是。 int fun(int n) { int count=0; while(n){ count++; n=n/10; } return count; } 9．下列程序的功能是。 #include #include main( ) { char str[81],*ptr1,*ptr2; int n; gets(str); n=strlen(str); ptr1=str; ptr2=str+n-1; while(ptr1 if(*ptr1!=*ptr2) break; else{ ptr1++; ptr2--; } } if(ptr1 else pr intf(“Y es!\n”); } 10．下列程序的功能是。(提示：ftell(*FILE)返回long类型的文件指针位置) #include void main( ) { FILE *fp; long position; fp=fopen(“file.tex”,“a”); fprintf(fp,“data”); position=ftell(fp); printf(“position=%ld\n”,position); fclose(fp); } 八、程序设计题（本题15分） 请编写一C语言程序，该程序的功能是确定字符串中首次出现的某字符在串中的位置(即该字符是字符串中的第几个字符)，然后从字符串中删除该字符。要求： (1) 如果未找到该字符，程序给出相应信息，否则，输出该字符在字符串中首次出现的位置，删除该字符(注：不考虑非首次出现的该字符的删除)，并且显示删除前后的字符串。 (2) 通过键盘输入字符串以及被确定的字符。 数据库期末试题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. 以下程序的输出结果是_______.#include main( ) { int num; for( num=0;num<=2;num++) printf(―%d‖,num); } （C） A. 1 B. 123 C. 012 D. 1234 2. 设有定义语句―char s[]=‖123‖;‖，则表达式―s[3]‖的值是（C） A. 1' B. '3' C. '\0' D. 存在语法错误 3. 不能进行＋＋和――运算的数据类型是（D） A. int型 B. long型 C. double型 D. 指针型 4. 若a为int类型，且其值为3，则执行完表达式a+=a-=a*a后，a的值是（C） A. 0 B. 8 C. -12 D. 10 5. 下列数组定义正确的是________。（D） A. int a[5],b[2,3]; B. char no(30); C. char x[]; D. int x[5]={1,2,3}; 6. 若a、b均为int型变量，且a=100，则对以下关于for循环语句： for(b=100;a!=b;++a,b++)printf(―————\n")；判断正确的是（C） A. 循环体只执行一次 B. 是死循环 C. 循环体一次也不执行 D. 输出———— 7. 语句if(!i) i++;中的条件表达式―!i‖等价于（A） A. i==0 B. i!=1 C. i!=0 D. –I 8. 函数原型语句正确的是（B） A. int Function(void a); B. void Function (int); C. int Function(a); D. void int(double a); 9. 下面程序输出结果是__________. main( ) { char a[]="programming", b[]="language"; char *p1,*p2; int i; p1=a; p2=b; for(i=0;i<7;i++) if(*(p1+i)==*(p2+i)) printf("%c",*(p1+i)); } （D） A. gm B. rg C. or D. ga 10. 下面程序的输出结果是_______. main() { int x=10,y=10; printf("%d %dn",x--,--y); } （A） A. 10 9 B. 9 9 C. 9 10 D. 10 10 11. 若变量已正确定义，执行语句scanf("%d%d%d ",&k1,&k2,&k3)；时，()是正确的输入。（B） A. 2030,40 B. 20 30 40 C. 20, 30 40 D. 20, 30,40 12. 设整型变量n=10,i=4,则赋值运算n%=i+1执行后，n的值是______。（D） A. 3 B. 2 C. 1 D. 0 13. 若k为整型，以下while循环()次. int k=10; while (k=0) k=k-1; （C） A. 10次 B. 无限循环 C. 一次不执行 D. 执行一次 14. 如果有char* ssl=―0123456789‖,则，sizeof（ssl）的值是（A） A. 4 B. 10 C. 11 D. 40 15. 以下不正确的C语言标识符是______。（C） A. AB1 B. _ab3 C. 4ab D. a2_b 二、判断题（共 10 道试题，共 40 分。） 1. 模运算符要求两侧均应为整型数据。（√） 2. 一个算法应该具备有穷性、确定性、输入、输出和有效性。（√） 3. 使用printf和scanf函数时，必须添加#include 1. 快速排序在最坏情况下的时间复杂度为（ D ）。 A．O(log 2n) B．O(nlog 2 n) C．O (n) D. O (n2) 2．设一棵二叉树的深度为k，则该二叉树中最多有（ D ）个结点。 A. 2k-1 B. 2k C.2k-1 D. 2k-1 3．二叉树中第i(i≥1)层上的结点数最多有（ C ）个。 A. 2i B. 2i C. 2i-1 D. 2i-1 4．设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为（ A ）。 A. p->next=p->next->next B. p=p->next C. p=p->next->next D. p->next=p 5．设栈S和队列Q的初始状态为空，元素E1、E2、E3、E4、E5和E6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出列的顺序为E2、E4、E3、E6、E5和E1，则栈S的容量至少应该是（ C ）。 A. 6 B. 4 C. 3 D. 2 6.设有以下四种排序方法，则（ B ）的空间复杂度最大。 A. 冒泡排序 B. 快速排 C. 堆排序 D. 希尔排序7．设结点A有3个兄弟结点且结点B为结点A的双亲结点，则结点B的度数数为（ B ）。 A. 3 B. 4 C. 5 D. 1 8．根据二叉树的定义可知二叉树共有（ B ）种不同的形态。 A. 4 B. 5 C. 6 D. 7 9．对一个算法的评价，不包括如下（ A ）方面的内容。 A．并行性 B．健壮性和可读性 C．正确性 D．时空复杂度10．在二叉排序树中插入一个结点的时间复杂度为（ C ）。 A．O(1) B．O(n) C．O(log 2 n) D．O(n2) 北京航空航天大学现代远程教育 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．数据库中不存在冗余数据 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分） 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 种排序方法中，当待排序的序列中元素初始时已经按值有序，排序所花费的 数据结构考试复习题集团档案编码：[YTTR-YTPT28-YTNTL98-UYTYNN08] 复习题集 一判断题 （√）1. 在决定选取何种存储结构时，一般不考虑各结点的值如何。 （√）2. 抽象数据类型与计算机内部表示和实现无关。 （×）3. 线性表采用链式存储结构时，结点和结点内部的存储空间可以是不连续的。 （×）4. 链表的每个结点中都恰好包含一个指针。 （×）5.链表的删除算法很简单，因为当删除链中某个结点后，计算机会自动地将后续的各个单元向前移动。 （×）6. 线性表的每个结点只能是一个简单类型，而链表的每个结点可以是一个复杂类型。（×）7. 顺序表结构适宜于进行顺序存取，而链表适宜于进行随机存取。 （×）8. 线性表在物理存储空间中也一定是连续的。 （×）9. 顺序存储方式只能用于存储线性结构。 （√）10.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）11.对于不同的使用者，一个表结构既可以是栈，也可以是队列，也可以是线性表。（√）12.栈是一种对所有插入、删除操作限于在表的一端进行的线性表，是一种后进先出型结构。 （√）13.两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。 （×）14.二叉树的度为2。 （√）15.若二叉树用二叉链表作存贮结构，则在n个结点的二叉树链表中只有n—1个非空指针域。 （×）16.二叉树中每个结点的两棵子树的高度差等于1。 （√）17.用二叉链表法存储包含n个结点的二叉树，结点的2n个指针区域中有n+1个为空指针。 （√）18.具有12个结点的完全二叉树有5个度为2的结点。 （√）19.二叉树的前序遍历序列中，任意一个结点均处在其孩子结点的前面。 （×）20.在冒泡法排序中，关键值较小的元素总是向前移动，关键值较大的元素总是向后移动。 （×）21.计算机处理的对象可以分为数据和非数据两大类。[计算机处理的对象都是数据]（×）22.数据的逻辑结构与各数据元素在计算机中如何存储有关。 （×）23.算法必须用程序语言来书写。 （×）24.判断某个算法是否容易阅读是算法分析的任务之一。 （×）25.顺序表是一种有序的线性表。[任何数据结构才用顺序存储都叫顺序表] （√）26.分配给顺序表的内存单元地址必须是连续的。 （√）27.栈和队列具有相同的逻辑特性。[它们的逻辑结构都是线性表] 一、单选题（共 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 分 北航《算法与数据结构》在线作业二 单选题 一、单选题（共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 ） C、哈希表 2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（B ） B、108 3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（C） C、head–>next= =head 4.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈序列是（ D ） D、2，3，5，1，6，4 5.下列关键字序列中，构成小根堆的是（ A ） A、{12，21，49，33，81，56，69，41} 6.下列数据结构中，不属于二叉树的是（ A ） A、B树 7.用顺序存储的方法来存储一棵二叉树，存放在一维数组A[1..N]中，若结点A[i]有右孩子，则其右孩子是（ C ）。 C、A[2i+1] 8.设树T的高度为4，其中度为1、2、3、4的结点个数分别为4、2、1、1，则T中叶子数为（ D ） D、 8 9.有数据{53，30，37，12，45，24，96}，从空二叉树开始逐个插入数据来形成二叉排序树，若希望高度最小，则应选择下 面哪个序列输入（ B ） B、37，24，12，30，53，45，96 10.对下面有向图给出了四种可能的拓扑序列，其中错误的是（ C ） C、5，1，6，3，4，2 11.m阶B-树中所有非终端（除根之外）结点中的关键字个数必须大于或等于( B ) B、[m/2]-1 12.散列文件也称为( C ) B 、索引文件 13.数据结构是（D ） D、相互之间存在一种或多种特定关系的数据元素的集合 14.从逻辑关系来看，数据元素的直接前驱为0个或1个的数据结构只能是（C ） C、线性结构和树型结构 15.设p为指向双向循环链表中某个结点的指针，p所指向的结点的两个链域分别用p→llink和p→rlink表示，则同样表示 一、选择题 1、下列数据中，为字符串常量的是（）。 A、'A' B、How do you do. C、$abc D、"house" 2、以下所列的C语言常量中，错误的是( )。 A、0xFF B、1.2e0.5 C、2L D、'\72' 3、以下程序的输出结果是（）。 main() {float x=3.6; int i; i=(int)x; printf("x=%f,i=%d\n",x,i); } A、x=3.,i=4 B、x=3 i=3. C、x=3,i=3 D、x=3.,i=3 4、若k是整型,则以下程序段的执行结果是:( ) k=-3; if(k<=0) printf("####") else printf("&&&&"); A、#### B、有语法错误,无结果 C、&&&& D、####&&&& 5、若x=2,y=3则x||y的结果是( )。 A、3 B、0 C、1 D、2 6、针对下列程序段回答问题( ). for(t=1;t<=100;t++) { scanf("%d",&x); if(x<0) continue; printf("%3d",t); } A、x>=0时什么也不输出 B、最多允许输出100个非负整数 C、printf函数永远也不执行 D、当x<0时整个循环结束 7、以下程序的执行结果是( )。 main() { int num = 0; while( num <= 2 ) { num++; printf( "%d,",num ); } } A、0,1,2 B、1,2,3, C、1,2,3,4, D、1,2, 8、选择正确的输入语句( )。:(其中:char string[20];)使得string的内容为"I am student". A、scanf("%s", string); B、scanf("%c", &string); C、scanf("%s", &string); D、gets(string); 9、对以下说明语句 int a[10]={6,7,8,9,10}; 的正确理解是（）。 A、将5个初值依次赋给a[6]至a[10] B、将5个初值依次赋给a[0]至a[4] C、因为数组长度与初值的个数不相同,所以此语句不正确 D、将5个初值依次赋给a[1]至a[5] 10、以下标识符中可以作为用户函数名的是（）. A、struct B、int C、union D、go_to 11、以下叙述错误的是（）. A、函数调用可以出现在一个表达式中 B、函数调用可以作为一个函数的形参 C、函数调用可以作为一个函数的实参 D、函数允许递归调用 12、若用数组名作为函数的实参，传递给形参的是（）。 A、数组第一个元素的值 北航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 ，该完全二叉 树的后序遍历序列为________。 2012年贵州大学数据结构复习题及答案 1、下面程序的时间复杂度为___C_ 。 for(i=0;i< m;i++) for(j=0;j< n;j++) A[i][j]=i*j; (A). O(m2) (B). O(n2) (C). O(m*n) (D). O(m+n) 2、在数据结构中，从逻辑上可以把数据结构分成__C__ 。 (A). 动态存储结构和静态存储结构 (B). 紧凑结构和非紧凑结 (C). 线形结构和非线性结构 (D). 内部结构和外部结构 3、下面程序的时间复杂度为__A__ 。 for(i=0;i< m;i++) for(j=0;j< t;j++) c[i][j]=0; for(i=0;i< m;i++) for(j=0;j< t;j++) for(k=0;k< n;k++) c[i][j]=c[i][j]+a[i][k]*b[k][j]; (A). O(m*n*t) (B). O(m+n+t) (C). O(m+n*t) (D). O(m*t+n) 4、下面程序的时间复杂度为__D__ 。 i=1；while(i<=n) i=i*5; (A). O(1) (B). O(n) (C). O(5*n) (D). O(log5n) 5、算法指的是_D__ 。 (A). 计算机程序 (B). 解决问题的步骤 (C). 排序算法 (D). 解决问题的有限运算序列 6、某程序的时间复杂度为（3n+nlog2n+n2+8），其数量级表示为 C (A). O(n) (B). O(nlog2n) (C). O(n2) (D). O(log2n) 7、数据结构是一门研究非数值计算的程序设计问题中的操作对象以及它们之间的__B____和运算的科学。 (A). 结构 (B). 关系 (C). 运算 (D). 算法 8、算法分析的目的是__C____。 (A). 找出算法的合理性 (B). 研究算法的输入/输出关系 (C). 分析算法的有效性以求改进 (D). 分析算法的易懂性 9、数据的基本单位是____B____。 (A). 数据 (B). 数据元素 (C). 数据项 (D). 结构体 10、与数据元素本身的形式、内存、相对位置、个数无关的是数据的____B_。 (A). 存储结构 (B). 逻辑结构 (C). 算法 (D). 操作 11、数据逻辑结构在计算机里的实现是___________A_______. (A). 存储结构 (B). 逻辑结构 (C). 算法 (D). 操作 1、在一个长度为n的顺序表中删除第i个元素（1≤i≤n）时，需要向前移动__A____个元素。 (A). n-i (B). n-i+1 (C). n-i-1 (D). i+1 2、线性表采用链式存储时，其地址___D_____。 (A). 必须是连续的 (B). 一定是不连续的 北航《语言程序设计》在线作业三 单选题判断题 一、单选题（共 10 道试题，共 40 分。） 1. 若有定义：int (*p)[3]; 则下列选项中，描述正确的是 . p是一个指向整型变量的指针 . p是一个指针数组名 . p是一个指针，它指向一个含有3个整型元素的一维数组 . 定义不合法 -----------------选择： 2. 表达式：10！=9的值是( ) . true . 非零值 . 0 . 1 -----------------选择： 3. 以下叙述中错误的是 . 对于oule类型数组，不可以直接用数组名对数组进行整体输入或输出 . 数组名代表的是数组所占存储区的首地址，其值不可改变 . 当程序执行中，数组元素的下标超出所定义的下标范围时，系统将给出“下标越界”的出错信息 . 可以通过赋初值的方式确定数组元素的个数 -----------------选择： 4. 若有说明语句：int w=2,x=3,y=3,z=4;则表达式w>x?w:z>y?z:x的值是 . 4 . 3 . 2 . 1 -----------------选择： 5. 下面程序的输出结果是__________. min() { int x=10,y=3; printf("%",y=x/y);} . 0 . 1 . 3 . 不确定的值 -----------------选择： 6. 给出说明语句：int =100,=40,=92; 则表达式(>)? + : +的值是( ). . 192 . 1 . 132 . 100 -----------------选择： 7. 当执行以下程序时，( )。#inlue 北航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 一、选择题。(每小题2分，共40分) (1) 计算机识别.存储和加工处理的对象被统称为____A____。 A.数据 B.数据元素 C.数据结构 D.数据类型 (2) 数据结构通常是研究数据的____ A _____及它们之间的联系。 A.存储和逻辑结构 B.存储和抽象 C.理想和抽象 D.理想与逻辑 (3) 不是数据的逻辑结构是____ A ______。 A.散列结构 B.线性结构 C.树结构 D.图结构 (4) 数据结构被形式地定义为北京航空航天大学《 数据库系统概论 》期末考试卷
北航11秋学期《C语言程序设计》在线作业
数据结构复习题(附答案)
北航15年3月《数据库原理及应用》试卷
北航数据结构与程序设计真题-2013北航991真题与答案
北航2011年硕士研究生入学考试数据结构与C语言试题与答案
数据结构考试复习题
16春北航《数据库原理及应用》在线作业
15秋北航《算法与数据结构》在线作业二100分答案
数据结构期末复习题答案
北航C语言期末模拟试题2012
北航 1999-2002 程序设计与数据结构考研试题
2012年贵州大学数据结构复习题及答案
15秋北航《C语言程序设计》在线作业三答案
北航10秋学期《算法与数据结构》模拟题一
数据结构复习题及答案(12级).
相关主题
文本预览