《2008年四川西南交通大学程序设计与数据结构.doc》由会员分享，可在线阅读，更多相关《2008年四川西南交通大学程序设计与数据结构.doc（9页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、2008年四川西南交通大学程序设计与数据结构一、填空题（本大题共20个空，每空1分，共20分）1、设有定义：int x=1, y=2; 则表达式：2.0+x/y的值为： 。2、在C语言中字符串的存放，其最后一个字符称为“空字符”，也叫字符串的结束符，对应的转义字符是 ，其值为 。3、设有宏定义：#define AA 2-3 ，则3*AA的宏替换结果是 。4、设有定义：int a=3, b=2, c=1 ，则表达式：abc的值是 。5、定义一个名为a的二维数组，并对数组元素赋初值，其值为下列矩阵，则对应的定义语句为： 。 1.0 3.8 2.6 3.3 5.0 9.86、设有定义：char s=
2、”SWJTU”; 则数组占用的内存为 字节，s5的值为 。7、若有定义： inta5，*p=a ；则*（p+3）表示 ；*p+3表示 。8、在具有n个元素单元的循环队列中，若采用少用一个元素来解决队空队满时都有头尾指针相等的问题，队满时共有 个元素。9、带一个头结点的单链表head为空的条件是 。10、二维数组A1020采用列序为主序存储，每个元素占一个存储单元，并且A00的存储地址是200，则A612的地址是 。11、深度为k的完全二叉树至少有 个结点，至多有 个结点。12、在一棵二叉树中，度数为零的结点个数为n0，度数为2的结点个数为n2，则有n0= 。13、在无向图G的邻接矩阵A中，若A
3、ij等于1，则Aji等于 。14、对n个元素的序列进行冒泡排序时，最少的比较次数是 。15、以折半查找方法查找一个线性表时，此线性表必须是 存储的 表。二、单项选择题（本大题共30小题，每小题1分，共30分。在每小题列出的四个选项中只有一个选项是符合题目要求的答案）1、若有以下定义语句： char ; int b ;float c ;double d：则表达式 a+b*c-d 的值的类型是【 】。A.char B.int C.float D.double2、以下程序段中与语句k=ab?(bc?1:0):0；功能等价的是【 】。A.if(ab)&(bc) k=1; else k=0; B.if(
4、ab)|(bc) k=1; else k=0;C.if(a=b) k=0 ;else if(bb) k=1 ;else if(bc) k=1 ;else k=0;3、若程序中定义了以下函数，并将其放在调用语句之后，则在调用前需对该函数进行说明，以下选项中错误的说明是【 】。 double myadd(double a,double b) return (a+b) ;A.double myadd (double a,b); B.double myadd (double ,double);C.double myadd (double b,double a); D.double myadd (dou
5、ble x, double y)4、假定a和b均为int 型变量，则执行以下程序段后， b的值是【 】。 a=1; b=10; dob-=a ;a+ ; while (b-0); A.9 B.-2 C.-1 D.85、语句： printf(“%d” ,strlen(“abcn0121”)； 的输出结果是【 】。A.9 B.10 C.11 D.126、设有定义：int n=0,*P=&n , *q=&p ；则以下选项中，正确的赋值语句是【 】。A.p=1; B.*q=2; C.q=p D.*p=57、设有变量定义： int a10=1,2,3,4,5,6,7,8,9,10, *P=&a3，b；则
6、执行赋值语句 b=p5;后b的值是【 】A.5 B.6 C.8 D.98、在函数定义中未指定返回值类型，则其隐含的返回值类型是【 】。A.void B.int C.float D.编译出错9、若有函数原型: viod f( int a ); 和数组定义 int a10；则以下函数调用错误的是【 】。A.f(a) B.f(a+2) C.f(a0) D.f(&a0)10、设k为整型变量，与表达式 （！k）值完全相同的表达式是【 】。 A.k=0 B.k=1 C.k!=0 D.k!=111、以下程序运行后，输出结果是【 】。 int b ; void MyFunc( int a,int *c) b=
7、(a+) + (*c)+; void main(void) int a, c ; a=1 ;b=2 ;c=3 ; MyFunc (c, &a); printf(“%d%d%d”,a ,b ,c ); A.144 B.243 C.123 D.14312、以下函数的功能是【 】。 int fun(char *s1 ,char *s2) int i=0 ; while(s1i=s2i&s2i!=0)i+; return(s1i=0&s2i=0); A.将s2所指字符串赋给s1B.比较s1和s2所指字符串的大小，若s1比s2的大，函数值为1，否则函数值为0C.比较s1和s2所指字符串是否相等，若相等，
8、函数值为1，否则函数值为0D.比较s1和s2所指字符串的长度，若s1比s2的长，函数值为1，否则函数值为013、以下程序段是从键盘上依次输入数据给数组元素，程序的下划线处应填上【 】。void main (void) int a20 ,i=0； while(i20) scanf(“%d”, ); A.&ai B.&ai+1 C.&ai+ D.&ai+14、若文件型指针fp已指向某文件的末尾，则函数feof(fp)的返回值是【 】。A.0 B.-1 C.NULL D.非零值15、在数据结构中，从逻辑上可以把数据结构分成【 】。A.动态结构和静态结构 B.紧凑结构和非紧凑结构C.线性结构和非线性结
9、构 D.内部结构和外部结构16、在以下叙述中，正确的是【 】。A.线性表的顺序存储结构优于链式存储结构B.二维数组是其数据元素为线性表的线性表C.栈的操作方式是先进先出D.队列的操作方式是先进后出17、一个栈的入栈序列式a ,b ,c ,d ,e ,则不可能的出栈序列是【 】。A.edcba B.decba C.dceab D.abcde18、若已知一个栈的入栈序列是 1, 2, 3, ， n ，其输出序列为p1 ,p2 , p3, ,pn,若p1=n，则p1为【 】。A.i B.n=I C.n-i+1 D.不确定19、循环队列用数组 Am存放其元素值，已知其头尾指针分别是front 和rea
10、r，则当前队列中的元素个数是【 】。A.(rear-front+m)%m B.rear-front+1 C.rear-front -1 D.rear-front20、设串s1=”ABCDEFG, s2=”PQRST”, 函数con(x,y)返回x和y串的连接串， subs(s ,I ,j)返回串s的从序号i的字符开始的j个字符组成的子串 , len(s)返回串s的长度，则con(subs(s1 ,2 , len(s2), subs(s1 ,len (s2),2 )的结果串是【 】。A.BCDEF B.BCDEFG C.BCPQRST D.BCDEFEF21、设矩阵A是一个对称矩阵，为了节省存储
11、空间，将其下三角部分按行序存放在一维数组Bn(n-1)/2中，对下三角部分中任一元素ai,j（ij），在一维数组B中下标k的值是【 】。A.i(i-1)/2+j-1 B.i(i-1)/2+j C.i(i+1)/2+j-1 D.i(i+1)/2+j22、设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为【 】。A.2h B.2h-1 C.2h+1 D.h+123、在一个具有n个顶点的无向图中，要连通全部顶点至少需要【 】条边。A.n B.n+1 C.n-1 D.n/224、设哈希表长m=14,哈希函数H（key）=key%11.表中已有4个结点： addr(15)=
12、4，addr(38)=5，addr(61)=6，addr(84)=7，其余地址为空，如用线性探测在散列处理冲突，关键字为49的节点的地址是【 】。A.3 B.4 C.5 D.625、哈希表长度为m，哈希函数H(K)=K%P，一般来说P应取小于m的最大【 】。A.奇数 B.偶数 C.素数 D.合数26、若用邻接矩阵表示一个有向图，则其中每一列包含的1的个数为【 】。A.图中顶点的入度 B.图中顶点的出度C.图中弧的条数 D.图中连通分数的数目27、在对n个关键字进行直接选择排序的过程中，每一趟都要从无序区选出最小关键字元素，则在进行第i趟排序之前，无序区中关键字元素的个数为【 】。A.i B.i
13、+1 C.n-i D.n-i+128、下列排序算法中，其时间复杂度和记录的初始排列无关的是【 】。A.插入排序 B.堆排序 C.快速排序 D.冒泡排序29、对20个有序记录进行折半查找，查找成功的平均查找长度为【 】。A.5 B.37/10 C.39/10 D.41/1030、当初始数据有序时，不应采用【 】。A.堆排序 B.快速排序 C.基数排序 D.希尔排序三、阅读程序，按提示给出结果（共5小题，每小题4分，共20分）。1、下面的函数Func的功能是 。 float Func (float a , int N) int i, float s; for(i=0,s=0; iN ;s+=ai,
14、i+); return s/N; 2、以下程序运行后的输出结果是 。 void main(void) int x=1,y=0 ,a=0,b=0 ; switch(x) case 1:switch(y) case 0:a+;break; case 1:b+;break; case 2:a+;b+;break; printf(“%d %dn”,a ,b); 3、以下程序运行后的输出结果是 。 void main (void) int i=0,s=0; for(:) i+; if(i=3|i=5) continue; if(i=6) break; s+=i; printf(“%dn”,s); 4、下
15、面程序运行时，若输入234，则输出结果是 。 unsigned Func (unsigned Num) unsigned k=1; dok*=Num%10;Num/=10;while (Num); return k; void main(void) unsigned n; scanf(“%u”,&n); printf(“%d”,Func(n);5、下面程序运行时，若输入： 口口-893abc193，则输出结果是 。 int IsDigit (char c) return (c9)?0:1: long Func(char s ) long n; int Sign ; for(:*s=口：s+)；
16、 /口 表示空格 Sign=(*s=-)?-1:1; if(*s=+|*s=-)s+; for(n=0L:IsDigit(*s) :s+) n=10*n+(*s-0); return n*Sign; void main (void) char s81; gets(s); printf(“%ld”,Func(s); 四、程序填空（本大题共10个空，每空2分，共20分）1、以下程序从键盘输入数据到数组中，统计其中正数的个数，并计算它们之和。请填空。 void main(void) int i,a20,sum,count; sum=count=0; for(i=0;i20;i+) scanf(“%d
17、”, 【1】 ) ; for(i=0;i0) count+; sum+= 【2】 ; printf(“Count=%d ,Sum=%d”,count,sum); 2、以下函数的功能是删除字符串s中的所有数字字符，请填空。 void DelSpace (char *s) int n=0,i; for(i=0; si; i+) if( 【3】 ) sn+=si; sn= 【4】 ; 3、下面是折半查找算法，请填空。 int Search_Bin (SSTable ST , KeyType key) low =1 ;high=ST.length; /置区间初值 while(low=high) mid
18、= 【5】 ; if(ST.elemmid.key=key) return mid ; /找到待查元素 else if(keyST.elemmid.key) 【6】 ; /继续在前半区间进行查找 else low= 【7】 ； /继续在后半区间进行查找 return 0; / 顺序表中不存在待查元素 /Search_Bin4、下面为直接插入排序的算法，请填空。viod InsertSort(SqList &L) /对顺序表L作直接插入排序。 for(i=2; i=L.length; +i) if(L.ri.key L.ri-1.key) 【8】 ;/ 复制为监视哨 for(j=i-1;L.r0
19、.keyL.rj.key; -j) 【9】 ； / 记录后移 【10】 ； / 插入到正确位置 / InsertSort五、简要回答题（共5小题，每小题4分，共20分）1、某二叉树的前序遍历节点访问顺序是abdgcefh， 中序遍历的节点访问顺序是 dgbaechf ，则其后序遍历的节点访问顺序是什么？2、在队列的顺序存储结构中，为什么要采用循环队列的形式？3、在有向图的邻接矩阵中，如何判断入度或出度为零的顶点？在有向图邻接表中，又如何判断出度为零的顶点。4、为什么说线性表的顺序存储结构是一种随机存取结构？5、请求解下图的最小生成树。v1v4v3v2v6v56512635456六、程序设计（本
20、大题共4小题，每题10分，共40分）1、请编写函数 void Func(int *a,int *n); 它的功能是： 求出1到1000之内能被7或11整除、但不能同时被7和11整除的所有整数并将它们放在a所指的数组中，通过n返回这些数的个数。注：假设a所指的数组有足够的空间存储满足条件的数。2、编一个函数，用递归方法求n阶勒让德多项式的值。其中：多项式的值通过函数返回，多项式的阶n以及多项式的变量x通过函数参数传递。递归公式如下：3、有一个单链表，其结点的元素值以非递减有序排列，编写一个函数删除该单链表中多余的元素值相同的结点。4、设一棵二叉树以二叉链表为存储结构，设计一个算法求二叉树的高度。