北航自主招生考试题目

1、第一部分数据结构一、是非判断题（本题共10分，每小题各1分）（对于下面给出的论述，你认为正确，请在小题后的括号中填入符号，否则，填入符号）1对算法进行分析的目的是为了提高算法的质量。 （ ）2一般情况下，双向链表比单向链表要占用更多的存储空间。 （ ）3将插入与删除操作限制在表的一端的线性表被称为堆栈。 （ ）4完全二叉树不一定是满二叉树，满二叉树一定是完全二叉树。 （ ）5利用二叉树的前序遍历序列和后序遍历序列一定可以构造出一棵二叉树。 （ ）6邻接表中边结点数目为偶数的图一定是无向图。 （ ）7拓扑排序不是检测有向图中是否存在回路的惟一方法。 （ ）8采用折半查找的线性表只要求表中元素按值

2、的大小有序排列就可以。 （ ）9对具有n个元素的序列进行插入排序，排序的总趟数为n-1。 （ ）10无论什么情况，快速排序法比其他排序法的时间效率都要高。 （ ）二、填空题（本题共15分，每小题各1分）1若长度为n的线性表采用顺序存储结构，当不溢出时，在其第i个位置(1in+1)插入一个新的数据元素之前需要依次移动（ ）个元素的位置。2在非空双向循环链表中由q指的链结点前面插入一个p指的链结点的过程对应的语句依次为：p-rlink=q; p-llink=q-llink; q-llink=p;（ ） 。（空白处为一条语句）3在实际应用中，当堆栈的最大长度难以估计时，堆栈最好采用（ ）存储结构。4

3、若a,b,c,d是初始为空的队列的输入序列，则此时该队列的输出序列是 （ ）。5若具有n个结点的二叉树采用二叉链表存储，则链表中有（ ）个指针域存放着NULL。6已知二叉树的前序遍历序列为ABDCEFG，中序遍历序列为DBCAFEG，其后序遍历序列为（ ）。7采用“逐点插入法”建立序列(54,28,16,34,73,62,95,60,26,43)的二叉排序树后，在该二叉排序树中查找到数据元素62时一共进行了（ ）次元素之间的比较。8在一个图中，所有顶点的度数之和等于所有边数的（ ）倍。9具有n个顶点的有向图最多有（ ）条边。10具有n个顶点的无向连通图采用邻接矩阵表示，邻接矩阵中至少有（ ）个

4、非零元素。11将数据元素2,4,6,8,10,12,14,16,18,20依次存放于一个一维数组中(设数组下标从0开始)，然后采用折半查找方法查找元素12，被比较过的数组元素的下标依次为（ ）。12若一个待散列存储的线性表为K=(18,25,63,50,42,32,9,45)，散列函数为H(k)=k MOD 9，则与元素18发生冲突的元素有（ ）个。13若对序列(1,2,5,3,4)采用泡排序法按元素值从小到大进行排序，则整个排序过程中进行的元素之间的比较次数为（ ）。14若对序列(tang, deng, an, wang, shi, bai, fang, liu)采用选择排序法按字典顺序进行

5、排序，则第三趟排序结束时序列的状态是（ ）。15设有10000个元素组成的序列，希望尽快挑选出其中前10个(仅挑出前10个!)最大值元，在不改变已有算法结构的前提下，插入排序法、快速排序法、堆积排序法和泡排序法这4种内排序算法中，最合适的是（ ） 。三、综合题（本题共15分，每小题各5分）1证明：具有n个结点的非空满二叉树，其叶结点的数目为(n+1)/2。2已知某带权连通图采用邻接矩阵存储，邻接矩阵以三元组表形式给出。邻接矩阵下三角形部分的元素（不包括主对角线上元素）对应的各三元组分别为 )，)，(5,2,4)，(5,3,(2,1,7)，(3,1,6)，(3,2,8)，(4,1,9)，(4,2

6、,4)，(4,3,6)，(5,1, (5,4,2)。请分别画出该连通图所有可能的最小生成树。3已知散列函数为H(key)=(key%3) MOD 11，散列地址空间为0.10，并且采用线性探测再散列法处理冲突。请画出在初始为空的散列表中依次插入22,41,53,8,46,30,1,31,66以后散列表的状态。四、算法设计题（本题10分） 结点的祖先定义为从根结点到该结点的所有分支上经过的结点。 已知非空二叉排序树采用二叉链表存储结构，链结点构造为 lchilddata rchild,根结点指针为T。请写一非递归算法, 依次打印数据信息为item的结点的祖先结点。设结点的数据信息分别为整数，并且

7、假设该结点的祖先结点存在。第二部分C语言程序设计五、单项选择题（本题共20分，每小题各1分）1一个C语言程序是由（ ）。A一个主程序和若干个子程序组成 B函数组成C若干过程组成 D若干子程序组成2当把以下四个表达式用作if语句的控制表达式时，其中有一个选项与其他三个选项的含义不同，这个选项是（ ）。Ak%2 Bk%2=1 C(k%2)!=0 D!k%2=13下列运算符中优先级最低的是（ ）。A+ B& C?: D!=4以下能够正确地定义整型变量a,b和c，并且为其赋初值5的语句是（ ）。Aint a=b=c=5; Bint a,b,c=5;Ca=5,b=5,c=5; Da=b=c=5;5若有说

8、明：double y=0.5,z=1.5; int x=10; 则能够正确使用C语言库函数的赋值语句是（ ）。Az=exp(y)+fabs(x); By=log10(y)+pow(y);Cz=sqrt(y-z); Dx=(int)(atan2(double)x,y)+exp(y-0.2);6以下对二维数组a的正确说明是（ ）。Aint a3; Bfloat a(3,4); Cdouble a14; Dfloat a(3)(4);7若有条件表达式 (exp) ? a+ : b-，则以下表达式中能够完全等价于表达式(exp)的是（ ）。A(exp=0) B(exp!=0) C(exp=1) D(e

9、xp!=1)8以下不正确的if语句形式是（ ）。Aif(ab&a!=b); Bif(a=b) a+=b;Cif(ab) a+;b+; Dif(a!=b) scanf(“%d”,&a) else scanf(“%d”,&b);9若有以下语句 int x=3; do printf(“%dn”,x-=2); while(!(-x);则上面程序段（ ）。A输出结果是1 B输出结果是3和0 C输出结果是1和-2 D是死循环10以下for循环语句的执行次数是（ ）。 for(x=0,y=0;(y=123)&(x4);x+);A执行4次 B执行3次 C是无限循环 D循环次数不定11设有如下程序段： t=0;

10、 while(printf(“*”) t+; if(tage D(*p).age20在C语言中，库函数fgets(str,n,fp)的功能是（ ）。A从str中读取至多n个字符到文件fpB从文件fp中读取长度为n的字符串存入str指向的内存C从文件fp中读取长度不超过n-1的字符串存入str指向的内存D从文件fp中读取n个字符串存入str指向的内存六、填空题（本题共15分，每小题各3分）1若运行以下程序时，从键盘输入2473（表示回车。下同），则下面程序的运行结果是（ ）。#include main( ) int c; while(c=getchar()!=n) switch(c-2) cas

11、e 0: case 1: putchar(c+4); case 2: putchar(c+4); break; case 3: putchar(c+3); default: putchar(c+2); break; printf(“n”):2当从键盘上输入18以后，下面程序的运行结果是（ ）。main( ) int x,u,i,j,a8; scanf(“%d”,&x); i=0; do u=x/2; a=x%2; i+; x=u; while(x=1); for(j=i-1;j=0;j-) printf(“%d”,aj);3以下程序的运行结果是（ ）。main( ) increment();

12、increment(); increment();increment() static int y=0; y+=1; printf(“%d”,y);4下面程序的运行结果是（ ）。#include main( ) static char a=“Language”,b=“programe”; char *p1,*p2; int i; p1=a; p2=b; for(i=0;i=7;i+) if(*(p1+i)=*(p2+i) printf(“%c”,*(p1+i);5以下程序用以输出结构体变量bt所占内存单元的字节数，请在程序的空白处（横线上方）填上适当内容。struct ps double i;

13、 char arr20;main( ) struct ps bt; printf(“bt size is :%dn”, （ ）);七、程序设计题（本题5分） 所谓“水仙花数”是指一个三位数，其各位数字立方之和等于该数本身。例如：153是一个“水仙花数”，因为135333=153。请编写输出1000以内所有“水仙花数”的程序。#include int main(void) int i, j, k; for (i = 1; i = 9; i +) for (j = 0; j = 9; j +) for (k = 0; k rlink=q; p-llink=q-llink; q-llink=p;（q

14、-llink-rlink-p ） 。（空白处为一条语句）3在实际应用中，当堆栈的最大长度难以估计时，堆栈最好采用（链式）存储结构。4若a,b,c,d是初始为空的队列的输入序列，则此时该队列的输出序列是 （）。5若具有n个结点的二叉树采用二叉链表存储，则链表中有（）个指针域存放着NULL。6已知二叉树的前序遍历序列为ABDCEFG，中序遍历序列为DBCAFEG，其后序遍历序列为（DCBFGEA）。7采用“逐点插入法”建立序列(54,28,16,34,73,62,95,60,26,43)的二叉排序树后，在该二叉排序树中查找到数据元素62时一共进行了（3）次元素之间的比较。8在一个图中，所有顶点的度

15、数之和等于所有边数的（2）倍。9具有n个顶点的有向图最多有（）条边。10具有n个顶点的无向连通图采用邻接矩阵表示，邻接矩阵中至少有（）个非零元素。11将数据元素2,4,6,8,10,12,14,16,18,20依次存放于一个一维数组中(设数组下标从0开始)，然后采用折半查找方法查找元素12，被比较过的数组元素的下标依次为（）。12若一个待散列存储的线性表为K=(18,25,63,50,42,32,9,45)，散列函数为H(k)=k MOD 9，则与元素18发生冲突的元素有（3）个。13若对序列(1,2,5,3,4)采用泡排序法按元素值从小到大进行排序，则整个排序过程中进行的元素之间的比较次数为

16、（4）。14若对序列(tang, deng, an, wang, shi, bai, fang, liu)采用选择排序法按字典顺序进行排序，则第三趟排序结束时序列的状态是（）。15设有10000个元素组成的序列，希望尽快挑选出其中前10个(仅挑出前10个!)最大值元，在不改变已有算法结构的前提下，插入排序法、快速排序法、堆积排序法和泡排序法这4种内排序算法中，最合适的是（堆排序）。三、综合题（本题共15分，每小题各5分）1证明：具有n个结点的非空满二叉树，其叶结点的数目为(n+1)/2。取个中间变量k表层数。2已知某带权连通图采用邻接矩阵存储，邻接矩阵以三元组表形式给出。邻接矩阵下三角形部分的

17、元素（不包括主对角线上元素）对应的各三元组分别为(2,1,7)，(3,1,6)，(3,2,8)，(4,1,9)，(4,2,4)，(4,3,6)，(5,1,)，(5,2,4)，(5,3,)，(5,4,2)。请分别画出该连通图所有可能的最小生成树。4-2 或者 5-2 所以不止一个3已知散列函数为H(key)=(key%3) MOD 11，散列地址空间为0.10，并且采用线性探测再散列法处理冲突。请画出在初始为空的散列表中依次插入22,41,53,8,46,30,1,31,66以后散列表的状态。四、算法设计题（本题10分）结点的祖先定义为从根结点到该结点的所有分支上经过的结点。已知非空二叉排序树采

18、用二叉链表存储结构，链结点构造为 lchilddata rchild,根结点指针为T。请写一非递归算法, 依次打印数据信息为item的结点的祖先结点。设结点的数据信息分别为整数，并且假设该结点的祖先结点存在。先找item父节点p，再找p父节点打印完设为p，再找其父节点。只要有关系就靠这关系找！第二部分C语言程序设计五、单项选择题（本题共20分，每小题各1分）1一个C语言程序是由（a）。A一个主程序和若干个子程序组成B函数组成C若干过程组成D若干子程序组成2当把以下四个表达式用作if语句的控制表达式时，其中有一个选项与其他三个选项的含义不同，这个选项是（a）。Ak%2Bk%2=1C(k%2)!=

19、0D!k%2=13下列运算符中优先级最低的是（c）。A+B&C?:D!=4以下能够正确地定义整型变量a,b和c，并且为其赋初值5的语句是（a ）。Aint a=b=c=5;Bint a,b,c=5;Ca=5,b=5,c=5;Da=b=c=5;5若有说明：double y=0.5,z=1.5; int x=10; 则能够正确使用C语言库函数的赋值语句是（）。Az=exp(y)+fabs(x);By=log10(y)+pow(y);Cz=sqrt(y-z);Dx=(int)(atan2(double)x,y)+exp(y-0.2);6以下对二维数组a的正确说明是（c）。Aint a3;Bfloat

20、 a(3,4);Cdouble a14;Dfloat a(3)(4);7若有条件表达式 (exp) ? a+ : b-，则以下表达式中能够完全等价于表达式(exp)的是（）。A(exp=0)B(exp!=0)C(exp=1)D(exp!=1)8以下不正确的if语句形式是（）。Aif(ab&a!=b);Bif(a=b) a+=b;Cif(ab) a+;b+;Dif(a!=b) scanf(“%d”,&a) else scanf(“%d”,&b);9若有以下语句int x=3;do printf(“%dn”,x-=2); while(!(-x);则上面程序段（）。A输出结果是1B输出结果是3和0C

21、输出结果是1和-2D是死循环10以下for循环语句的执行次数是（）。for(x=0,y=0;(y=123)&(x4);x+);A执行4次B执行3次C是无限循环D循环次数不定11设有如下程序段：t=0;while(printf(“*”)t+;if(tageD(*p).age20在C语言中，库函数fgets(str,n,fp)的功能是（）。A从str中读取至多n个字符到文件fpB从文件fp中读取长度为n的字符串存入str指向的内存C从文件fp中读取长度不超过n-1的字符串存入str指向的内存D从文件fp中读取n个字符串存入str指向的内存六、填空题（本题共15分，每小题各3分）1若运行以下程序时，从键盘输入2473（表示回车。下同），则下面程序的运行结果是（）。#include main( )int c;while(c=getchar()!=n)switch(c-2)case 0:case 1: putchar(c+4);case 2: putchar(c+4); break;case 3: putchar(