江西师范大学软件学院869C语言程序设计与数据结构历年考研真题汇编.pdf

目录2014年江西师范大学软件学院869C语言程序设计与数据结构A考研真题2014年江西师范大学软件学院869C语言程序设计与数据结构B考研真题2013年江西师范大学软件学院869C语言程序设计与数据结构A考研真题2013年江西师范大学软件学院869C语言程序设计与数据结构B考研真题2012年江西师范大学软件学院837C语言程序设计与数据结构考研真题2014年江西师范大学软件学院869C语言程序设计与数据结构A考研真题专业：120100管理科学与工程01、04方向科目：C语言程序设计与数据结构注：考生答题时，请写在考点下发的答题纸上，写在本试题纸或其他答题纸上的一律无效。一、简答题（共8小题，其中第7小题8分，其余每小题6分，共50分）1请至少列举三种以上C语言的主要数据类型。2简述C语言中条件表达式max=(ab)?a:b的执行过程。3简述C语言中break语句的作用。4请给出指针变量定义的一般形式，并举例说明。5若线性表的元素个数基本稳定，且很少进行插入和删除操作，但要求以最快速度存取表中的元素时，应采用何种存储结构？若在应用中经常增、删元素，则应采用何种存储结构？6对于一个栈，若输入序列为A,B,C，试写出至少三种可能的输出序列。7假设双链表结构的C语言描述如下：typedef int datatype;typedef struct dlink_nodedatatype info;struct dlink_node*llink,*rlink;dnode;8根据图1回答以下问题：（1）如何访问q指针所指结点的数据域？（2）如何访问q指针所指结点的直接前驱结点的数据域？图19什么叫满二叉树？二、填空题（5个空，每空2分，共10分）1若有语句int a=2；则计算表达式a+=a后，a的值为_。2若有说明和语句：int a=2,b;b=a+；则a和b的值分别是_、_。3若已定义int x=3,y=2，则表达式x&y的值为_。4设有语句 int a10;则共定义了_个数组元素。三、判断题，对打“”，错打“X”（5小题，每小题2分，共10分）1栈是一种可在两端进行插入或删除操作的线性表。2队列的存储方式只能是顺序存储，不能用链式存储。3如果两个字符串的长度相同，则它们相等。4完全二叉树的某结点若无左孩子，则它必是叶子节点。5一棵有n个顶点的生成树有且仅有n-1条边。四、应用题（3小题，每小题10分，共30分）1对于图2所示的二叉树，请回答以下问题：图2（1）结点C 的双亲为哪个结点？（2）结点F 的层次为多少？二叉树的高度(深度)为多少？（3）写出这棵二叉树的前序遍历序列。2设哈希表长度为11，使用哈希函数H(x)=x%11把一个整数值转换成哈希表的下标，现给定一组关键字序列为1，24，12，34，38，36，25，33的数据，试画出采用线性探测法解决冲突时所构造的哈希表。3对于图3所示的无向图G，试给出：图3（1）图中每个顶点的度。（2）该无向图的邻接矩阵。五、程序设计题（5小题，每小题10分，共50分）1试编写一个C语言程序，判断从键盘输入的一个整数能否被2和3整除。若能满足上述条件，则将其输出，否则输出不能同时被2和3整除的提示信息。2试编写一个C语言程序，从键盘为一个长度为10的整型一维数组输入数据，并输出数组中值最大的元素的下标值。3试编写一个C语言程序，先定义一个整数类型的数组a55，然后给数组a赋值，最后计算并输出a数组中每行的和。4设有一个线性表(a1,a2,a3，an)，其元素递增有序且按顺序存储于计算机内。要求设计一个算法void search(sequence_list sl,int x)在线性表中查找数值为 x 的元素（查找算法不限），若找到将其值与第一个元素的值进行交换，否则输出此元素不存在。假定程序中已有用C语言描述的顺序表结构如下：#define MAXSIZE 100/*预定义最大的数据域空间*/typedef int datatype;/*假设数据类型为整型*/typedef structdatatype aMAXSIZE;/*此处假设数据元素只包含一个整型的关键字域*/int size;/*线性表长度*/sequence_list;/*预定义的顺序表类型*/5试编写一个算法node*insert(node*headA,node*headB,datatypex)，实现把带头结点的headB单链表中值为x的所有结点依次插入到带头结点的headA单链表尾部。假定程序中已有如下说明：typedef int datatype;typedef struct link_nodedatatype info;struct link_node*next;node;2014年江西师范大学软件学院869C语言程序设计与数据结构B考研真题专业：120100管理科学与工程01、04方向科目：C语言程序设计与数据结构注：考生答题时，请写在考点下发的答题纸上，写在本试题纸或其他答题纸上的一律无效。一、简答题（共8小题，其中第7小题8分，其余每小题6分，共50分）1在C语言中，结构化程序设计有哪三种基本控制结构？2简述以下if语句的执行过程。if（表达式1）语句1;else if（表达式2）语句2;3简述C语言中break语句的作用。4请给出指针变量定义的一般形式，并举例说明。5常用的数据存储结构分为哪几种？6对于一个队列，若输入序列为a,b,d,e,f，试写出其对应的输出序列。7假设双链表结构的C语言描述如下：typedef int datatype;typedef struct dlink_node datatype info;struct dlink_node*llink,*rlink;dnode;8根据图1回答以下问题：（1）如何访问q指针所指结点的数据域？（2）如何访问q指针所指结点的直接后继结点的数据域？图19什么叫二叉树？二、填空题（5个空，每空2分，共10分）1在C语言中，实型变量的类型说明符有：_、double。2若已定义int a=1,b=2,c=3，则表达式a|b&c的值为_。3若有5=x=10，则其正确的C语言表达式是_。4执行下面程序段后，a的值为_。int a=4,b=6；a=a+b；5下面程序运行后,输出的结果是_。#include void main()int x=10,y=3;printf(“%dn”,y=x%y);三、判断题，对打“”，错打“X”（5小题，每小题2分，共10分）1栈的存储方式既可以是顺序存储，也可以是链式存储。2队列是一种特殊的线性表，具有先进先出的性质。3如果一个串中的所有字符均在另一个串中出现，则前者是后者的子串。4使用二分法检索时要求线性表有序并且采用顺序存储结构。5线性表若采用链式存储结构时，要求内存中可用存储单元的地址必须是连续的。四、应用题（3小题，每小题10分，共30分）1对于图2所示的二叉树，请回答以下问题：图2（1）二叉树的高度(深度)为多少？（2）该二叉树是否是满二叉树？是否是完全二叉树？（3）写出这棵二叉树的前序遍历序列。2假设用于通信的电文由6个字母A,B,C,D,E和F组成，各字母在电文中出现的相对频率分别为0.3，0.07，0.1，0.18，0.2和0.06，请根据字符出现频率构造对应的Huffman树，并为它们设计Huffman编码。3对于图3所示的无向图G，试给出：图3（1）该无向图从顶点A开始的深度优先（DFS）遍历结果。（2）该无向图从顶点A开始的广度优先（BFS）遍历结果。五、程序设计题（5小题，每小题10分，共50分）1有一函数：y=试编写一个C语言程序，从键盘上输入x的值，根据上面的函数，求出y的值，并输出。2假如某数列第1，2项分别为0和1，以后每个奇数编号的项是前两项之和，偶数编号的项是前两项之积，生成并打印该数列的前15项，生成的15个数存放在一维数组x中，并按每行5项的形式输出。3试编写一个C语言程序，先从键盘为一个整型二维数组a1010赋值，然后计算并输出a数组中各元素的最大值。4试编写一个算法int count_x(sequence_list sl,int x)，计算并返回顺序表中值为x的结点的个数。假定程序中已有用C语言描述的顺序表结构如下：#define MAXSIZE 100/*预定义最大的数据域空间*/typedef int datatype;/*假设数据类型为整型*/typedef struct datatype aMAXSIZE;/*此处假设数据元素只包含一个整型的关键字域*/int size;/*线性表长度*/sequence_list;/*预定义的顺序表类型*/5试编写一个算法node*insert(node*headA,node*headB)，实现把带头结点的headB单链表中值为偶数的所有结点依次插入到带头结点的headA单链表尾部。假定程序中已有如下说明：typedef int datatype;typedef struct link_node datatype info;struct link_node*next;node;2013年江西师范大学软件学院869C语言程序设计与数据结构A考研真题专业：120100管理科学与工程01、04方向科目：C语言程序设计与数据结构注：考生答题时，请写在考点下发的答题纸上，写在本试题纸或其他答题纸上的一律无效。一、简答题（共8小题，其中第5小题8分，其余每小题6分，共50分）1简述C语言中有哪些算术运算符。2简述C语言中，输出操作有哪些常用函数？3简述以下switch语句的执行过程。switch （表达式）case 常量1:语句1；case 常量2:语句2；case 常量3:语句3；.case 常量n:语句n；default:语句n+1；4简述C语言中 while 循环和 do-while 循环的异同。5什么叫串（字符串）？空串和空格串是否相同，为什么?6抽象数据类型堆栈的常用操作有哪些（至少写出三个）？7在顺序队列中，什么叫假溢出？8简述二叉树和一般树的主要区别。二、填空题（5个空，每空2分，共10分）1在C语言中，正确的标识符是由字母、_、下划线组成的，其中第一个字符应为字母或下划线。2若已定义int x=6,y=3，则计算表达式x-=y后的x值是_。3若有10 x100，则其正确的C语言表达式是_。4设有语句 int a34;则共定义了_个数组元素。5设有以下宏定义：#define M 3 则执行语句z=2*M+5;后，z的值是_。三、判断题，对打“”，错打“X”（5小题，每小题2分，共10分）1栈是一种特殊的线性表，具有先进后出的性质。2队列的存储方式既可是顺序存储，也可是链式存储。3对稀疏矩阵进行压缩存储是为了节省存储空间。4在一棵二叉树中，假定每个结点只有左子女，没有右子女，对它分别进行前序遍历和中序遍历，则具有相同的遍历结果。5树型结构是一种线性数据结构。四、应用题（3小题，每小题10分，共30分）1对于图1所示的二叉树：图1写出这棵二叉树的前序、中序和后序遍历序列。2设哈希表长度为11，哈希函数H(x)=x%11，给定的关键字序列为1，13，12，34，38，33，27，29。试画出线性探测法解决冲突时所构造的哈希表。3已知无向图G=(V,E)，其中V表示顶点集合，E表示边集合，且V=a,b,c,d,e,E=,，请画出无向图G，并写出该无向图G的邻接矩阵。五、程序设计题（5小题，每小题10分，共50分）1从键盘上输入10个评委的分数，去掉其中一个最高分和一个最低分，求出其余8个人的平均分，最后输出最高分，最低分和平均分。试编写一个C语言程序实现以上功能。2试编写一个C语言程序，求一分数序列 的前15项之和。3试编写一个C函数void inverted(int s,int n)，实现将数组s中的n个值按逆序重新存放。例如，原来存放的顺序为1,3,8,6,11，逆序存放后为11,6,8,3,1。4试编写一个算法node*dele(node*head,datatype x)，实现在带头结点的head单链表中删除值为x的结点。假定程序中已有如下说明：tpedef int datatype;typedef struct link_node datatype data;struct link_node next;node;5试编写一个算法int binsearch(seqlist L,datatype key)，实现用非递归的二分查找法在顺序表L中查找是否存在关键字为key的数据元素，若查找成功则返回所在位置，否则返回-1。假定程序中已有说明如下：#define maxsize 100/*预定义最大的数据域空间*/typedef int datatype;/*假设数据类型为整型*/typedef struct datatype datamaxsize;/*此处假设数据元素只包含一个整型的关键字域*/int len;/*线性表长度*/seqlist;/*预定义的顺序表类型*/2013年江西师范大学软件学院869C语言程序设计与数据结构B考研真题专业：120100管理科学与工程01、04方向科目：C语言程序设计与数据结构注：考生答题时，请写在考点下发的答题纸上，写在本试题纸或其他答题纸上的一律无效。一、简答题（共8小题，其中第8小题8分，其余每小题6分，共50分）1简述C语言中有哪些关系运算符。2.C语言中，输入操作有哪些常用函数？3简述以下if语句的执行过程。if（表达式1）语句1;else if（表达式2）语句2;else 语句3;4简述在C语言的循环语言中break语句与continue语句的区别。5抽象数据类型队列的常用操作有哪些（至少写出三个）？6二叉树的常见遍历方法有哪些？7什么叫函数的递归调用？8试分别列举出一个满二叉树和一个完全二叉树的例子。二、填空题（5个空，每空2分，共10分）1.C语言程序的三种基本结构是顺序结构、选择结构和_结构。2若已定义int x=4,y=2,z=3，则表达式x-y|z的值为_。3设有语句 int a50;则数组a的元素个数为_。4若有说明和语句：int a=5，b=6，y=6；b-=a；y=a+；则b和y的值分别是_、_。三、判断题，对打“”，错打“X”（5小题，每小题2分，共10分）1线性表中除了第一个节点和最后一个节点外，其余的结点有且仅有一个前驱结点和一个后继结点。2两个栈共享一片连续内存空间时，为提高内存利用率，减少溢出机会，应把两个栈的栈底分别设在这片内存空间的两端。3队列是一种特殊的线性表，其特殊性在于插入和删除操作都在表的同一端执行。4二叉树中任一个结点的度均为2。5哈夫曼树是带权路径长度最短的树，路径上权值较大的结点离根节点较近。四、应用题（3小题，每小题10分，共30分）1试分别画出具有3个结点的二叉树的五种不同形态。2假设通讯电文中只用到了A,B,C,D,E,F 6个字母，他们在电文中出现的相对频率分别为4，18，13，8,20和9，请根据字符出现频率构造对应的Huffman树，并为它们设计Huffman编码。3已知无向图G=(V,E)，其中V表示顶点集合，E表示边集合，且V=a,b,c,d,e,E=,，请画出无向图G，并写出该无向图从顶点a开始的深度优先（DFS）遍历结果。五、程序设计题（5小题，每小题10分，共50分）1从键盘输入一个字符串（字符中不包含空格），当输入回车时认为输入结束，假设输入的字符串存放在一个字符数组中，试编写一个C语言程序统计输入字符串中小写英文字母、大写英文字母、数字字符、其他字符的个数。2有一对兔子，从出生后第3个月起每月生一对兔子，小兔子长到第三个月后每月又生一对兔子，假如兔子都不死，试编写一个C语言程序求一年中可以繁殖成多少对兔子？提示：兔子的规律为数列1，1，2，3，5，8，13，.。3试编写一个C函数int isprime(int x)，判断整数x是否是素数，如果是素数，函数返回1，否则，返回0。所谓素数，是指除了1和本身之外，不能被其他任何整数整除的数。4试编写一个算法node*lkinsert(node*head,datatype x,datatypea)，实现在带头结点的head单链表中值为a的结点之后插入新元素x。假定程序中已有说明如下：tpedef int dataType;typedef struct link_node dataType data;struct link_node next;node;5试编写一算法void sort(table*L)，实现将顺序表L中的记录按排序码从小到大进行排序（排序算法不限）。假定程序中已有说明如下：#define MAXSIZE 100 /*顺序表中记录个数的最大值*/typedef int keytype;/*定义排序码类型为整数类型*/typedef structkeytype key;int other;/*记录中除排序码外的其他域*/recordtype;/*记录类型的定义*/typedef structrecordtype rMAXSIZE+1;int length;/*待排序顺序表中记录的个数*/table;/*待排序顺序表类型*/2012年江西师范大学软件学院837C语言程序设计与数据结构考研真题