吉林省计算机专升本考试历年真题.doc

C 语言程序设计辅导材料 1 吉林省普通高等学校专升本教育考试吉林省普通高等学校专升本教育考试 C 语言程序设计辅导材料 2 2003 年吉林省普通高等学校专升本教育考试年吉林省普通高等学校专升本教育考试 计算机科学技术专业综合试卷计算机科学技术专业综合试卷 一、填空题 1向栈中推入元素的操作是 。 2线性表中结点的集合是 ，结点间的关系是 。 3在双链表中要删除已知结点*p，其时间复杂度为 。 4已知数组 A116采用行序为主方式存储，每个元素占 4 个存储单元，并且 数组元素 A00的存储地址是 1000，数组元素 A84的地址是 。 5在栈中存取数据遵从的原则是 。 6广义表的长度是指 ，广义表的深度是指 。 7N 个顶点的连通图至少有 条边。 8深度为 k 的完全二叉树至少有 个结点，至多有 个结点。 9在各种查找方法中，平均查找长度与结点个数 n 无关的查找方法是 。 10已知完全二叉树的第 8 层有 8 个结点，则其叶子结点数是 。 11对一组记录（54，38，96，23，15，72，60，45，83）进行直接插入排序， 当把第 7 个记录 60 插入到有序表时，为寻找插入位置，需比较 次。 12拓扑排序算法是通过重复选择具有 个前驱顶点的过程来完 成。 二、单项选择题 1不带头结点的单链表 head 为空的判定条件是（ ） Ahead= =NULL Bhead-next= =NULL Chead-next= =head Dhead!=NULL 2设长度为 n 的链队列用单循环链表表示，若只设尾指针，则出队操作的时间 复杂度为（） AO(1) BO(log2n) CO(n) DO(n2) 3数组 A 中，每个元素 Aij的长度为 3 个字节，行下标 i 从 0 到 7，列下标 j 从 0 到 9，从首地址 SA 开始连续存放在存储器内，该数组按行存放时，元素 A74的起始地址为（） C 语言程序设计辅导材料 3 ASA+141 BSA+144 CSA+222 DSA+225 4某二叉树的后序遍历为 dabec，中序遍历为 debac，则前序遍历序列为（） Aacbed Bdecab Cdeabc Dcedba 5对于二叉树来说，第 i 层上至多有（）个结点。 A2i B2i-1 C2i-1 D2i-1-1 6递归函数 f(n)=f(n-1)+n (n1)的递归体是（ ） Af(1)=0 Bf(0)=1 Cf(n)=f(n-1)+n Df(n)=n 7在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的（）倍。 A1/2 B1 C2 D4 8已知图的邻接表如下所示，根据算法，则从顶点 0 出发按广度优先遍历的结 点序列是（） A0 3 2 1 B0 1 2 3 C0 1 3 2 D0 3 1 2 9对线性表进行二分查找时，要求线性表必须（） A以顺序方式存储 B以链接方式存储 C以顺序方式存储，且结点按关键字有序排列 D以链接方式存储，且结点按关键字有序排列 10如果要求一个线性表既能较快地查找，又能适应动态变化的要求，可以采 用（）查找。 A分块 B顺序 C二分 D散列 11设有 1000 个无序的元素，希望用最快的速度挑出其中前 10 个最大的元素， 最好采用（）法。 C 语言程序设计辅导材料 4 A冒泡排序 B快速排序 C堆排序 D基数排序 12非线性结构中，每个结点（） A无直接前趋 B只有一个直接前趋和后继 C只有一个直接前趋和个数不受限制的直接后继 D有个数不受限制的直接前趋和后继 13设高度为 h 的二叉树只有度为 0 和度为 2 的结点，则此类二叉树所包含的 结点数至少为（） A2h B2h-1 C2h+1 Dh+1 14矩阵是一个（） A对称矩阵 B三角矩阵 C带状矩阵 D稀疏矩阵 15散列文件是一种（） A顺序文件 B索引文件 C链接文件 D计算寻址文件 三、假设二叉树包含的结点数据为 1，3，7，2，12 1画出两棵高度最大的二叉树 2）画出两棵完全二叉树，要求每个双亲结点的值大于其孩子结点的值。 四、程序分析题 1程序： #include int x=1; main() func(x); printf(“%dn”,x); func(int x) C 语言程序设计辅导材料 5 x=3; 程序的执行结果是： 2程序： #include main() int a=2,*p,*pp; pp= p= printf(“%d,%d,%d”,a,*p,*pp); 程序的执行结果是： 3程序： #include main() char s80,c1,c2= ; int i=0,num=0; gets(s); while(si!=0) c1=si; if(i= =0) c2= ; else c2=si-1; if(c1!= i+; printf(“%d”,num); C 语言程序设计辅导材料 6 程序完成功能是： 4下面的函数 invert 的功能是将一个字符串的内容颠倒过来。程序有一处错误 请找出，度改正。 程序： void invert(char str) int i,j,k; for(i=0,j=strlen(str); ij; i+,j-) k=stri; stri=strj; strj=k; 5下面程序中有一处错误，请指出，并改正。 main() float a10; int i; for(i=0; inext=P; P-next=S; BS-next=P-next; P-next=S; CS-next=P-next; P=S; DP-next=S; S-next=P; 4一个栈的入栈序列为 1，2，n，其输出序列为 P1，P2，Pn，若 P1=n，则 Pi为（ ） Ai Bn-i Cn-i+1 D不确定 5数组 A 中，每个元素的长度为 3 个字节，行下标 i 从 1 到 8，列下标 j 从 1 到 10，从首地址 SA 开始连续存放在存储器内，该数组按行序存放时，元素 A85的起始地址为（ ） ASA+141 BSA+144 CSA+222 DSA+225 6将递归算法换成对应的非递归算法时，通常需要使用（ ） A栈 B队列 C链表 D树 7任何一棵二叉树的叶结点在前序、中序和后序遍历中的相对次序是（ ） A不发生改 B发生改变 C不能确定 D以上都不对 8已知一有向图的邻接表存储结构如下图所示，根据有向图的深度优先遍历算 法，从顶点 V1 出发，所得到的顶点序列为（ ） AV1V2V3V5V4 BV1V2V3V4V5 CV1V3V4V5V2 DV1V4V3V5V2 9快速排序方法在（ ）情况下最不利于发挥其长处。 A要排序的数据量太大 B要排序的数据中含有多个相同值 C要排序的数据已基本有序 D要排序的数据个数为奇数 10有一个长度为 12 的有序表，按二分查找法对该表进行查找，在表内各元素 等概率情况下查找成功所需的平均比较次数为（ ） A35/12 B37/12 C39/12 D43/12 C 语言程序设计辅导材料 9 11下面给定的四个数中最大的是（ ） A （38）10 B （00101011）2 C （1F）16 D （41）8 12若 x=4, y=-2, z=5，则表达式+x-y+z+的值为（ C ） A10 B11 C12 D13 13以下给定程序的输出结果为（ ） main() int x=12; while(x-); printf(“%d”,x); A1 B0 C11 D1 14有一二维数组 a34，其第 2 行第 3 列元素的正确表示方法是（ ） A p+=5; a4=c; A6 B11 C0 D4 三、算法设计与解答 1设有一组关键字19，01，23，14，55，20，84，27，68，11，10，77采用 哈希函数：H(key)=key%13,采用开放地址法的二次探测再散列方法解决冲突， 试在 018 的散列地址空间中对该关键字序列构造哈希表。 2试用普里姆法构造如图所示的一棵最小生成树。 （要求每加入一个结点，画 一个图） 3已知二叉树的先序遍历序列为“-,+,a,*,b,c,-,/,d,e,f”中序遍历序列为：“a,+,b,*,c,- ,d,/,e,-,f”，画出此二叉树，并写出它的后序遍历序列。 C 语言程序设计辅导材料 10 4二叉树采用链接存储结构，试设计一个算法计算一棵给定二叉树的单孩子结 点数。 （只写算法函数） int onechild(btree *b) 5已知线性表中的元素以值递增有序排列，并以单链表作为存储结构，试写一 高效的算法，删除表中所有值相同的多余元素（使得操作后的线性表中所有元 素的值均不相同） ，同时释放被删除结点空间，并分析你的算法的时间复杂度。 status Delete_Equal(Linklist i=1; while(i main() char s80; int i,num=0; 【1】 ; gets(s); while(si!=0) if(i= =0) else if(【2】 ) i+; printf(“num=%dn”,num); 3在已排好序的字符串 a，下面的程序是将字符串 b 的每个字符按顺序插入到 a 中。请将该程序填写完整。 #include main() char a30=”adeghkortuw”; char b =”flmsx”; int i,j,k; printf(“string a:%sn”,a); for(k=0; sk!=0; k+) j=0; while(sk=aj for(【1】 ) 【2】 aj=sk; printf(“string a:%sn”,a); 五、读程序写结果 1写出如下程序的执行结果 #include int m=5; int f1( ) C 语言程序设计辅导材料 12 m=m+3; return(m); main() int m=3; int m=10; m+; f1( ); m+=1; printf(“%dn”,m); 2写出下面程序的执行结果 void swap(int *r, int *s) int *t; t=r; r=s; s=t; main() int a=3,b=9; int *p,*q; p= q= printf(“%d,%dn”,*p,*q); swap(p,q); printf(“%d,%dn”,*p,*q); C 语言程序设计辅导材料 13 3写出下面程序的执行结果。 main() union struct int x; int y; n; int a; int b; e; e.a=5; e.b=4; e.n.x=e.a+e.b; e.n.y=e.a*e.b; printf(“%d,%dn”,e.n.x,e.n.y); 六、编程题 1编程实现求 1+1/2！+1/3！+1/n！，真到使最后一项 1/n！小于 10-4. 2从键盘输入 10 个数，将其存入一个数组中，处理使这 10 个数在原数组中逆 序存放。输出原数组和处理后数组。 （注：要求处理过程占用最少存储空间） 3将给定数组 a 中，10 个元素（初始值为 1001，1000，2001，1030，5201，4110，2111，3302，6013，3123）按每数各 位之和（千位+百位+十位+个位）从小到大排序。 C 语言程序设计辅导材料 14 2007 年吉林省普通高校专升本教育试点考试年吉林省普通高校专升本教育试点考试 计算机科学与技术专业综合试卷计算机科学与技术专业综合试卷 一一 、填空题、填空题(每空每空 2 分分，共共 40 分分) 1设有变量说明：int a=3,b=2; 则表达式 ab 的值为 。 2若有如下定义：int x=65；则语句 printf（“%c”，x） ；的输出结果是 。 3有条件表达式：ab?a:cd?c:d，若 a=1，b=2，c=3，d=4，则表达式的值为 。 4已知 int a 3=1，2，3，4，5，6，7；则数组 a 的第一维（行）的大小 是 。 5设有语句：int i；for（i=0；i,( 表示结点 a 到结点 b 是单向的)画出此结构对应的图形，并判断它属于哪种逻辑 结构？（6 分） 2将下面所示的森林转换成一棵二叉树（按字母序号顺序） ，并分别写出二叉 树的先序、中序、后序的遍历序列。 （6 分） 3假设用于通信的电文有 8 个字母 A,B,C,D,E,F,G,H 组成，各字母在电文中出 现的频率为 5%，25%，4%，7%，9%，12%，30%，8%，试为这 8 个字母设计 哈夫曼编码，并求其带权路长度 WPL。(要求权值集取5,25,4,7,9,12,30,8，按 照左子树权值小于右子树的权值的顺序构造哈夫曼树，并注明每个节点的权值。 ) (10 分) 4对下面的带权图按照普里姆法从顶点 V1出发构造一棵最小生成树，并求该 生成树的权值。 （要求：每加入一个结点，画一个图） （8 分） 5设有一组关键字（4，9，26，10，12，33，22，19） ，利用哈希函数为： H（key）=key%12，采用线性探测散列处理冲突，试在 010 的散列地址空间 中对该组关键字构造哈希表，并求在关键字的查找概率相等的前提下查找成功 的平均查找长度。 （要求：直接写出哈希表格，查找长度表示为分数形式） （10 分） 6对长度为 n 的记录序列进行快速排序时，所需要的比较次数依赖于这几个元 素的初始序列。点 n=8 时，在最好的情况下共需要进行多少次比较？（要求： 写出每一趟的划分情况和比较次数。 ） （10 分） C 语言程序设计辅导材料 19 四、算法设计题（共四、算法设计题（共 10 分）分） 试编写一个在带有头结点的双向循环链表中为 x 的结点之前，插入值为 y 的结 点的算法。 （要求：用 C 语言描述，结点类型定义为 dlnode） Status InsertPrior-L(DlinkList float fahr=0.0,celsius; upper=300;step=20; while(【1】 ) celsius= 【2】 ; printf(“%f%fn”,fahr,celsius); 【3】 ; 2求两数中的较大值。 #include main() int a ,b,max; printf(“please input:n”); scanf(“%d%d”, 【1】 ); 【2】 max=a; 【3】 max=b; printf(the max is :%dn“,max); 3输入一行字符，分别统计出其中英文字母、空格、数字和其他字符的个数。 #include main() C 语言程序设计辅导材料 20 char c; int letters=0,space=0,digit=0,other=0; printf(“please input characters n”); while(c=getchar()! =n) if(c=a s=0;count=0; for(i=0;i main() int count,num,total; count=0;total=0; while(count int a23=1,2,3,4,5,6; main() int i,j,b32; for(i=0;i main() int a 10=1,2,3,4,5,6,7,8,9,0; int *p,i; printf(“n”); for(p=a;pb 的输出值是（ ） A：ture B: false C：1 D：0 11int a=0,b=20,c=30 ,m,n;执行(m=a+) struct node *next; ; struct node *p,*q; 已知指针*p 和*q,p 指向单链表中的一个节点，将 q 指向的节点插入到 p 节 点的后面，写出语句序列。 五、程序填空题五、程序填空题 1补充以下程序，将 x 和 y 换值 void main() int x=5,y=3,temp; ; ; ; printf(“%d %d”,x,y); 2用插入排序对数组排序 int j; for(int i=2;i=0 j-; ; /* 插入 x */ 3以下程序功能是输入一个浮点型的数据，并输出，要求保留 2 位小数 void main() C 语言程序设计辅导材料 27 float x; ; printf(“ ”,x); 六、看程序写结果题六、看程序写结果题 1void main() int i; int a6=1,1; for(i=2;i int area(int x,int y) C 语言程序设计辅导材料 28 int z= PI*x*y; printf(“%d”,z); main() int a=4,b=5; area(a,b); 结果： 4main() int sage=70,s; s=sage/10; switch(s) case 9: case 8: case 7: case 6: pintf(“SUCCESS”); break; default: printf(“FAILED”); 结果： 七、编程题七、编程题 在一个灰图形脱色的时候，以如图所示的 RGB 图形矩阵为例，编写一个程序， 定义一个整型的二维数组，并在定义的时候将其初始化，用两个双 For 循环将 矩阵中所有小于 5 的元素赋值为 0，在用两个 For 双循环将修改后的二维矩阵 按行序输出。 36491 4800 269934 C 语言程序设计辅导材料 29 2012 年吉林省普通高等学校专升本教育考试年吉林省普通高等学校专升本教育考试 计算机科学与技术综合试题计算机科学与技术综合试题 2012.04.24 一、选择题一、选择题 1下面程序段的时间复杂度量级为（） for(i=1;ib) if(a+1) printf(“%dn“,a); elseprintf(“%dn“,a-); A：0B：1C：2D：3 15以下程序的输出结果是（） 。 #include“stdio.h“ main() int a=5,b=4,c=6,d; printf(“%dn“,d=ab?ac?a:c:b); A：5B：4C：4D：不确定 16程序的输出结果是（） 。 #include“stdio.h“ main() int x=1,y=0,a=0,b=0; switch(x) C 语言程序设计辅导材料 31 case 1: switch(y) case 0: a+; break; case 1: b+; break; case 2: a+; b+; break; printf(“a=%d,b=%dn“,a,b); A：a=2,b=15B：a=1,b=1 C：a=1,b=0D：a=2,b=2 17若定义：int a=511,*b=的输出结果是（） 。 A：无确定的值B：a 的地址C：512D：511 18运行下面的程序，如果从键盘上输入：ABC 时，输出的结果是（） 。 #include“stdio.h“ main() char ss10=“12345“; strcat(ss,“6789“); gets(ss); printf(“%sn“,ss); A：ABCB：ABC9 C：123456ABCD：ABC456789 19在以下给出的表达式中，与 do-while(E)语句中的(E)不等价的表达式是（） 。 A：(!E=0) B：(E0|E,0) C：(E=0) D：(E!=0) 20以下程序运行后，输出结果是（） 。 #include“stdio.h“ main() int aa44=1,2,3,4,5,6,7,8,3,9,10,2,4,2,9,6; int i,s=0; for(i=0;inext=p-next，后再修 改 即可。 8广义表(a),(b),c),(d)的表尾是 。 9访问单链表中的结点，必须沿着 依次进行。 10在长度为 n 的线性表中顺序查找元素 x 的时候，查找成功的平均查找长度 应该为 。 11定义 int x,y;执行 y=(x=1,+x,x+2);后，y 的值是 。 12设有 static char str=“Beijing“;则执行 printf(“%dn“,strlen(strcpy(str,“China“); 后的输出结果为 。 13在定义 int n56;后，第 10 个元素是 。 14若有数组定义：char array=“China“;则数组 array 所占的空间为 。 15执行下面的程序后，a 的值是 。 #define SQR(X) X*X main() int a=10,k=2,m=1; a/=SQR(k+m)/SQR(k+m); printf(“%dn“,a); 16若有以下程序段，输出结果是 。 C 语言程序设计辅导材料 33 char s=“141141abct“; printf(“%dn“,strlen(s); 17变量的指针，其含义是指该变量的 。 18表达式：(int)(double)9/2)-(9)%2 的值是 。 19在对文件进行操作的过程中，若要求文件的位置回到文件的开头，应当调 用的函数是 函数。 20在程序中，可把整型数以二进制形式存放到文件中的函数是 。 三、解答题三、解答题 1有一个含有 14 个数的序列（39,80,76,41,13,29,50,78,30,11,100,7,41,86） ， 写出使用希尔排序进行升序排序的每一趟结果。取增量：5、3、1。 2以下函数 creatlist 用来建立一带头节点的单链表，链表的结构如下图所 示，新的节点总是插入在链表的末尾，链表的头指针作为函数值返回。链表最 后一个节点的 next 域放入 NULL，作为链表的结束标志。data 为字符型数据域， next 为指针域。读入时字符以#表示输入结束（#不存入链表） 。请填空。 h0 struct node char data; struct node *next; ; 【 】reatelist() struct node *h,*s,*r; char ch; h=(struct node*)malloc(sizeof(struct node); r=h; ch=getchar(); while(ch!=#) s=(struct node*)malloc(sizeof(struct node); s-data= 【 】 ; C 语言程序设计辅导材料 34 r-next=s.r; r=s; ch=getchar(); r-next= 【 】 ; return h; 3已知一个连通图如图所示，给出图的邻接矩阵示意图。若从顶点 v1 出 发对该图进行遍历，分别给出一个按深度优先遍历和广度优先遍历顶点序列。 4如图所示是一个无向带权图，请按 Prim 算法求最小生成树。要求每加 入一条边画一个图。 ab d c e f 6 5 5 2 6 6 1 3 5已知一个 AOV 网，如图所示，写出所有的拓扑结构序列。 V1 V0 V5 V2 V3 V6 V4 6一个稀疏矩阵如下图所示，写出对应的三元组顺序表和十字链表存储表 示。 V1V2V