1、贵州大学 2014 年硕士研究生入学考试试题（所有试卷答案必须答在专用答题纸上，否则答案无效）考试科目名称： 程序设计与数据结构考试科目代码： 831一、选择题（单项选择题，25 个小题，每小题 2 分，共 50 分，下面每题给出的4 个选项中，只有一个选项最符合试题要求）1、程序经过编译生成的是（）。A、源文件B、目标文件C、可执行文件D、编译文件2、在一个 C 程序中（）。A、main 函数出现在所有函数之前，C 程序不一定都有 main 函数B、main 函数必须出现在所有函数之后，一个 C 程序必须有且仅有一个 main函数。C、main 函数可以在任何地方出现,一个C 程序必须有且仅
2、有一个main 函数。D、main 函数出现在固定位置，一个 C 程序可以有多个 main 函数。3、与 m=n- -完全等价的表达式是（）。A、n=n-1,m=nB、m=- -nC、m=n-1D、m=n,n=n-14、已知梯形的上底为 a，下底为 b，高为 h，面积用 s 表示，用 C 语言书写的正确的面积公式为（）。A、s=1/2*(a+b)*hB、s=1/2(a+b)hC、s=1.0/2*(a+b)hD、s=1.0/2*(a+b)*h 5、可用作用户标识符的一组标识是（）。A、voiddefineB、a3-3_123C、For_abcD、2asizeof6、已知 int i=3,j=5;
3、 float x=2.5; double y=5.0; 则y +=i -=j*=+ +x;的值为（）。A、-9B、-9.5C、-7.0D、-9.07、设 int a=4; 则表达式 a1 的运算结果和 a 的值分别为（）。A、0 和 3B、0 和 4C、1 和 3D、1 和 4 8、以下对二维数组 a 进行不正确的初始化的是（）。A、int a3=3,2,1,1,2,3;B、int a=3,2,1,1,2,3;第 8 页 共 8 页C、int a23=3,2,1,1,2,3;D、int a3=3,2,1,1,2,3;9、以下不能把字符串 China 赋给数组 s 的语句是（）。A、char s
4、10=C,h,i,n,aB、char s10=”China”;C、char s10; strcpy(s,”China”);D、char s10; s=”China”; 10、以下 4 个关于 C 语言的结论中，错误的是（）。A、用 while 语句实现的循环一定可用 for 语句实现；B、用 for 语句实现的循环一定可用 while 语句实现；C、用 do-while 语句实现的循环一定可用 while 语句实现；D、do-while 语句与 while 语句的区别是仅是关键字”while”出现的位置不同。11、C 语言中，在使用时分配存储空间的变量的存储类型是（）。A、static 和 a
5、utoB、static 和 registerC、auto 和 registerD、register 和 extern 12、有语句 int a3 = 1,2,3,4,5,6;则 a11的值是（）。A、1B、4C、5D 、 6 13、若有定义 int x,*p;，则以下赋值正确的表达式为（）。A、*p=&xB、p=xC、p=&xD、*p=*x 14、函数返回值的类型是由（）。A、return 语句中的表达式类型所决定。B、调用该函数时的主调函数类型所决定。C、调用该函数时系统临时决定。D、在定义该函数时所指定的函数类型所决定。15、若有以下语句：int a3,*p=a;则 &a2-p 的值是（）
6、。A、1B、2C、3D、4 16、数据结构在计算机内存中的表示是指（）。A、数据结构B、数据的逻辑结构C、数据的存储结构D、数据元素之间的关系17、数据结构在存储数据时，通常不仅要存储各数据元素的值，而且还要存储（）。A、数据的处理方式B、数据元素的类型C、数据的存储方式D、数据元素之间的关系18、对一个算法的评价，不包括如下（）方面的内容。A、健壮性和可读性B、正确性C、并行性D、时空复杂度19、线性表采用链式存储结构时，其地址（）。A、一定是不连续的B、必须是不连续的C、连续或不连续均可以D、部分必须是连续的20、对线性表，在下列哪种情况下应当采用链表表示？（）。A、经常需要随机地存取元素
7、B、经常需要进行插入和删除操作。C、表中元素需要占据一片连续的存储空间D、表中元素的个数不变21、一个队列的入队序列是 1, 2, 3, 4，则队列的输出序列是（）：A、4, 3, 2, 1B、1, 2, 3, 4C、1, 4, 3, 2D、3, 2, 4, 122、若串 S=”China”，则 S 的子串数目为（）A、1B、5C、15D、1623、在一棵高度为 n 的满二叉树中，其节点总数为（）A、2nB、2n-1C、2n-1D、2n-1-124、在一个单链表中，若 p 所指向结点不是最后结点，在 p 之后插入 s 所指向结点，则执行（）。A、s-next=p; p-next=s;B、s-n
8、ext=p-next; p-next=s; C、s-next=p-next; p=s;D、p-next=s; s-next=p;25、已知一棵二叉树的前序遍历结果为 ABCDEF，中序遍历结果为 CBAEDF， 则后序遍历结果为（）。A、CBEFDAB、FEDCBAC、CBEDFAD、不定二、名词解释（本题共 6 个小题，每小题 3 分，共 18 分）1、算法2、栈3、拓扑排序4、二叉树5、有向图6、邻接矩阵三、程序阅读题（本题共 4 个小题，每小题 4 分，共 16 分）1、读下列程序，写出程序的输出结果。#includevoid Swap(int a, int *b)int temp;te
9、mp = a; a = *b;*b = temp;void main()int a = 1, b = 2; int *p = &b; if(ab) Swap(a,p);printf(“%d,%d”, a,b);程序运行的结果为：2、读下面程序，写出程序的输出结果。#includevoid main()char *ps = “This is Guizhou University”; int n = 16;ps = ps+n; printf(“%sn”,ps);程序运行的结果为：3、读下列程序，写出程序的输出结果。#includeint m = 6, n = 5; void prt()int k
10、= 3,y;y = (+k)+(+m);printf(“m=%d,y=%dn”,m,y);int main()int a,m=2; m += 2;a = (n+)+m; prt();printf(“m=%d,a=%dn”,m,a); return 0;程序运行的结果为：4、读下列程序，写出程序的输出结果。#include#include char *ss(char *s)return s + strlen(s)/2;void main()char *p, *str = “abcdefgh”; p = ss(str); printf(“%sn”,p);程序运行的结果为：四、简答题（本题共 4 个
11、小题，每小题 4 分，共 16 分）1、数据元素之间的关系在计算机中有几种表示方法？各有什么特点？2、图 1 所示是一颗二叉树，分别写出该二叉树的先序遍历序列，中序遍历序列， 后序遍历序列。图 1 二叉树3、简述顺序表与链表的特点。4、简述逻辑结构与存储结构的关系。五、完善程序题（本题共 3 个小题 10 个空，每个空 2 分，共 20 分，请考生根据程序的上下文关系，在空框处填上适当内容，每个空框只填一个语句或一个表达式）。1、下面函数用于递归法求 xn，按要求完善程序。long cf(int x, int n)long k; if(n0)printf(“Data error!n”); ex
12、it(0);else if(n=0) (1) ; else k = (2) ; return (3) ;2、以下程序片段的功能是把输入的两个数从大到小排序并输出。#includevoid main()int a,b;(4) ;int p = &a; int q = &b;scanf(“%d,%d”,p,q); if(*pnext;(8) ;for(p=p-next;p!=NULL;p=(9) ) if(10) )m = p-data; return 0;六、应用题（本题共 2 个小题，每一个小题 10 分，第二小题 20 分，共 30 分） 1、有一个链表，设结点中包含学号，成绩及指向下一结点的结构体指针；写一函数实现：输出成绩高于平均成绩的学生学号。（要求：写出结构体定义）2、带权图 G 如图 2 所示，（1）写出图 G 的邻接矩阵；（6 分）（2）选择结点 1作为起始结点，使用克鲁斯卡尔算法求图 G 的最小生成树，要求用图形的形式写出其生成过程。（14 分）。图 2带权图 G
