2023年南京师范大学GIS专业研究生入学考试题集C语言

《C语言程序设计》考试试题（含数据结构）南师1999年GIS专业研究生入学《C语言程序设计》考试试题（含数据结构）2.voidJiecheng(intnum){ if(num<=0) printf("请输入正整数！"); intjc=0; for(inti=1;i<num;i++) { jc*=i; } printf("%d!=%d",num,jc);}南师2023年GIS专业研究生入学《C语言程序设计》考试试题（含数据结构）南师2023年GIS专业研究生入学《C语言程序设计》考试试题（含数据结构）

南师2023年GIS专业研究生入学《C语言程序设计》考试试题（含数据结构）

南师2023年GIS专业研究生入学《C语言程序设计》考试试题（含数据结构）

南师2023年GIS专业研究生入学《C语言程序设计》考试试题（含数据结构）一、填空题（每题5分，共20分）

（1）数据结构是数据的（

）和（

），以及它们之间的互相联系，并对这种结构定义相应的（

），设计出相应的（

），而保证通过这些运算后所得到的新结构是（

）结构类型。

（2）“4：30'40''”（

）；0.01E-20（

）；‘101’（

）；0x3c0（

）；-0.5F（

）；

A:合法的字符常量

B:合法的整形常量

C:合法的浮点数常量

D:合法的字符串常量

E:非法表达

请在括号内填入A、B、C、D、E

（3）本题程序输出结果是：（

）

#include<stdio.h>

#degineN5voidmain(void)

{

inti;

doublex,s=0;

for(i=1,x=1;i<=N;i++,x+=0.5)

s+=1/x;

printf("s=%.2f",s);

}

（4）根据线性表的链式存储结构形式，每个结点所含指针的个数，链表可分为（

）和（

）；而根据指针的联接方式，链表又可分为（

）和（

）；栈的特点是（

），队列的特点是（

）。二、选择题（每题5分，共20分）

（1）在数据结构中，与所有的计算机无关的数据叫（A）结构；链表是一种采用（B）存储结构存储的线性表；链表合用于（C）查找；在链表中进行（D）操作的效率比在顺序存储结构中进行（D）操作效率高；二分法查找（E）存储结构。

A)<1>存储

<2>物理

<3>逻辑

<4>物理和逻辑

B)<1>顺序

<2>网状

<3>星式

<4>链式

C)<1>顺序

<2>二分法

<3>顺序，也能二分法

<4>随机

D)<1>二分法查找

<2>快速查找

<3>顺序查找

<4>查找

E)<1>只合用于链表

<2>只合用于顺序

<3>即合用于顺序，也合用于链表

<4>即不合用于顺序，也不合用于链表

（2）若一个栈的输入序列是1、2、3、……、n,输出序列的第一个元素是n，则第i个输出元素是（

）

A)n-i

B)n-i+1

C)i

D)n+i-1

（3）若串S='NjnuGisc',其子串的数目是（

）

A)8

B)37

C)36

D)9

（4）下列程序段的运营结构是（

）

int

n=0;

while(n++<=2);

printf("%d",n);

A)

2

B)3

C)4

D)有语法错误三、程序设计（共计110分，请书写整洁，卷面有分）

（1）运用串的基本运算，编写一个算法删除串S1中所有S2子串。（本题15分）

（2）编写一程序，判断一个字符串是不是“回文数”。所谓回文数是从左至右或从右至左读起来都是同样的字符串。（本题15分）

（3）设计一个记录选票的算法，输出每个候选人的得票结果（假定采用单链表存放选票，候选人编号依次为1，2，3，……N,且每张选票选且只选一人）（本题15分）

（4）有几个人围成一圈，顺序排号。从第一个开始报数，凡报到4的人退出圈子，问最后留下的是几号。（本题15分）

（5）假设一个算术表达式中包含圆括号、方括号和花括号三种类型的括号，编写一个

算法判断其中的括号是否匹配。（本题15分）

（6）已知R[0……n-1]为整型数组，试设计实现下列运算的递归算法（本题15分）

<1>求数组R中的最大整数

<2>求n个整数之和

<3>求n各整数的平均值

（7）分别写出下图树的先序遍历、中序遍历和后序遍历的结果。写出中序遍历算法，算法中root指向二叉树的根。（本题20分）

南师2023年硕士研究生招生入学考试初试试卷科目名称：C语言程序设计（含数据结构）考生注意：所有答案必须写在答题纸上，否则无效，后果自负。一、填空题（每题5舒，共计20分）

(1)

每次从无序表中取出一个元素，把它插入有序表中的适当位置，此种排序法叫做____排序：每次从无序表中挑选出一个最小或最大元素，把它互换到有序表的一端，此种排序方法叫做____排序;每次直接或通过基准元素间接比较两个元素，若出现逆序排列时就互换它们的位置，此种排序方法叫做_______排序：每次使两个相邻的有序表合并成一个有序表的排序方法叫做________排序。快速排序在平均情况下的时间复杂度为____。（2）设输入元素为1,2,3，P和A，输入顺序为123PA，元素通过栈后到达输出序列。当所以元素均到达输出序列后_____________________________________序列可以作为C语言的标记符．(3)

己知sizeof(int)==4，请分析下面代码的运营过程并写出输出结果

unsigned

int

GetSize(int

a[],char

*strl)

{

return

sizeof(a)

+

Sizeof(strl);

}

int

main(){

int

a1[100];

char

*

strl="Welcome!";

printf("%d,_%d,_",sizeof(a1),

sizeof(strl));

printf("%d.",GetSize(a1,

strl));return0;}输出：________________________。(4)T是正则二叉树，即只有度为2和度为O的结点，它具有6个叶结点，那么树T的高度最多可以是____；最小可以是_____;树T的分支结点数是_____。假如T又是Huffman最优二叉树且各叶结点的权分别是1、2、3、4、5、6，则最优二叉树T的非叶结点的权之和是_____；权为1的叶结点所处层次是____。【注：树的根结点高度为O】二、选择题【每题5分．共计20分】(1)

下列说法中错误的是____。

A)数据结构是指互相之间存在-种或多种关系的数据元素的全体，

B)数据的逻辑结构与数据元索自身的内容和形式无关。

C)在索引顺序结构上实行分块查找，在等概率情况下，其平均查找长度不仅与子表

个数有关，并且与每一个子表中的记录个数有关。

D)每种数据结构都应具有三种基本运算：插入，删除，搜索。2)队列的特点是__A__，设循环队列用q[n]来存放，其头尾指针分别为f和r，则队满

条件是__B__,队列中的元素个数为C

。

A<1>先进先出<2>后进先出

<3>只进不出

<4>只出不进

B

<1>r=f

<2>r=(f+1)%n

<3>f=(r+1)%n

<4>f=r+1%n

C<1>r-f<2>r-f+1

<3>(r_f)%n

<4>(r-f+n)%n(3)

下图是带权的有向图G的邻接表达法。从结点V1出发深度遍历图G所得的结点

序列为__A__：广度遍历图G所得的结点序列为__B__;G的一个拓扑序列是__C__

从结点V1到V8的最短途径是__D__，从结点V1到V8的关键途径是___E___。(4)下面程序的运营结果是____#include<stdio.h>main(){

int

a=5,

b=4,c=3,rl,r2;rl=a>

b>c;r2=a>b&&b>C;printf

("%d

%d\n",rl,r2);}A)0

0

B)0

1

C)

10

D)11

E)有语法错误三、程序设计（共计1l0分，请书写整洁，卷面有分）(1)

设A和B是两个顺序表，其元素按从小到大的顺序排列。编写一个将A和B中相同元素组成一个新的从大到小的有序顺序表C的算法，并分析算法的时间复杂度。(本题15分）2）若线性表用单链表(带表头结点)作为存储结构，写出其就地逆置算法。(本题15分）(3)设定串采用顺序存储结构，求串s1和

s2的一个最长公共子串的长度，并指出该最长公共子串分别在sl和s2中的起始位置。（水题15分）(4)设单链表中存放

n个字符，试设计一个算法，使用栈判断该字符串是否中心对称，如xyzzyx即为中心对称字符串。（小题15分）(5)

编写算法找出从自然数1,2，…．n中任取r个数的所有组合。（本题15分）(6)

设计一个计算二叉树各结点的子孙个数的的算法。（本题15分）(7)

已知一棵二叉树的先序序列和中序序列，则可唯一地拟定一棵二叉树。（本题20分）<1>设计一个算法由先序序列和中序序列构造二叉树<2>若先序序列为abcdefg．中序序列为cbaefdg，画图构造相应的二叉树，并写出该二叉树的后序序列。

南师2023年GIS专业研究生入学《C语言程序设计》考试试题（含数据结构）

1.设计一个程序，将任何输入的字符串中的最长单词输出，并计算出其在字符串中的位置。（15分）2.试采用递归函数实现将任意位数的整数转换为字符串输出，规定在主函数中输入整数并调用递归函数实现转换并输出结果，对于负数也能解决（15分）3.以顺序存储结构表达串，设计算法，求串S中出现的第一个最长反复子串及其位置并分析算法的时间复杂度。（20分）4.运用2个栈S1和S2模拟一个队列，写出入队和出队的算法（可用栈的基本操作）（20分）5．编写一算法，以完毕在带头节点单链表M中第n个位置前插入元素X的操作。（20分）6．编写一个运用二分法查找某值X是否存在于一组已知数据X1、X2、X3、……Xn中的程序。（20分）7．试设计一个算法解决地图着色判断问题。设一地图有n个区域，用不多于4种颜色对这些区域进行着色，着色应满足的规定是相邻的区域颜色不可以相同。你的算法以一种着色方案（即哪一个区域着什么颜色）为输入，算法对该着色方案进行考察，若满足着色规定，则输出true,否则则输出false。（20分）（1）用C语言描述你为解决问题而设计的数据结构（逻辑结构，存储结构）。数据结构的设计应考虑对问题的清楚描述和算法的效率；（2）用C语言写出你的算法。算法应简洁、高效。对算法中的参数、变量、语句做必要的注释，以增长可读性；（3）简朴分析你的算法的空间开销和时间开销。

8．已知一棵树的边的结合为{(I,M),(I,N),(E,I),(B,E),(B,D),(C,B),(G,J),(G,K),(A,G),(A,F),(H,L),(A,H),(C,A)},试画出这棵树，并回答下列问题：（20分）（1）哪个是根节点？

（2）哪些是叶子节点？

（3）树的深度是多少？

（4）写出该树的前序遍历序列

南师2023年GIS专业研究生入学《C语言程序设计》考试试题

（1）设S为一个长度为n的字