下载文档原格式
广西科技大学 2024 年硕士研究生招生考试初试专业课试卷考试科目代码：817 考试科目名称：数据结构与程序设计考试时间：180分钟（本试题共 6 页）一、判断题（每小题1分，共10分）1．C语言中的输入语句只能用scanf实现。
2．for语句只能用于循环次数已经确定的情况下。
3．逻辑运算符两侧运算对象的数据类型只能是整型或字符类型。
4．局部变量只对main函数起作用，而全局变量对所有函数起作用。
5．若有定义，int k=2, *ptr1, *ptr2; 且ptr1和ptr2均已指向k，则ptr2=k;是正确的语句。
6．已知i=0，j=1，语句if(j++||++i);执行后i、j的值分别是1、2。
7．char s[5]="ABCDE"能够正确进行字符串赋值。
8．若有定义，int *point, a=4; point =&a;，则point、&a、*&point都代表地址。
9．在C语言中，二维数组元素在内存中的存放顺序是按行顺序存放。
10．不能用"r"方式打开一个并不存在的文本文件。
二、单项选择题（每小题1.5分，共30分）1．若C语言中一个int型数据在内存中占用两个字节，则int型数据的取值范围为____。
A．-128～127 B．-32768～32767C．0～65536 D．0～21474836472．有以下程序片段int k=5;while(k=1) k--;执行此程序片段，则描述正确的是____。
A．while循环执行4次B．循环体执行一次C．循环体一次也不执行D．死循环3．有如下函数调用语句fuc( rec1, rec2+rec3, (rec4, rec5) );该函数调用语句中，含有的实参个数是____。
A．3 B．4 C．5 D．有语法错误4．程序的三种基本结构是____。
A．顺序结构，循环结构，递归结构B．顺序结构，循环结构，选择结构C．选择结构，循环结构，递归结构D．顺序结构，选择结构，递归结构5．C语言中主函数的个数是____。
804数据结构与高级程序设计考卷1. 引言数据结构与高级程序设计是计算机科学与技术专业中一门重要的课程，旨在培养学生深入理解数据结构的原理和应用，并掌握高级程序设计技术。
本篇文章将围绕任务名称“804数据结构与高级程序设计考卷”展开，详细介绍数据结构与高级程序设计的相关内容。
2. 数据结构数据结构是指一组数据元素以及对这些数据元素之间关系的描述和操作。
在计算机科学中，常见的数据结构包括数组、链表、栈、队列、树、图等。
数据结构可以帮助我们更好地组织和管理数据，提高算法的效率。
2.1 数组数组是一种线性数据结构，它由一组连续的内存空间组成，用来存储相同类型的数据。
数组的特点是可以通过下标快速访问任意位置的元素。
例如，我们可以使用一个整型数组来存储学生成绩，通过下标可以快速获取某个学生的成绩。
2.2 链表链表是一种非连续的数据结构，它由一系列节点组成，每个节点包含数据和指向下一个节点的指针。
链表的特点是插入和删除操作的效率较高，但访问某个位置的元素需要遍历整个链表。
例如，我们可以使用链表来实现一个队列，插入和删除操作的时间复杂度都是O(1)。
2.3 栈和队列栈和队列是两种常见的数据结构，它们都是由线性表衍生而来。
栈是一种先进后出（Last In First Out，LIFO）的数据结构，类似于现实生活中的堆栈。
栈的插入和删除操作只能在栈顶进行，例如，我们可以使用栈来实现计算器的后缀表达式求值。
队列是一种先进先出（First In First Out，FIFO）的数据结构，类似于现实生活中的排队。
队列的插入操作（入队）在队尾进行，删除操作（出队）在队头进行，例如，我们可以使用队列来实现操作系统的进程调度。
2.4 树和图树和图是两种非线性的数据结构，它们在实际应用中非常重要。
树是一种层次结构，它由一组节点和连接节点的边组成。
树的一个节点可以有多个子节点，但每个节点只有一个父节点，例如，我们可以使用树来表示文件系统的目录结构。
数据结构考试试题及答案数据结构考试试题及答案数据结构是计算机科学中非常重要的一门课程，它涉及到了计算机程序设计中的数据组织、存储和管理等方面。
在学习数据结构的过程中，掌握基本的数据结构类型、操作和算法是非常重要的。
为了帮助大家更好地掌握数据结构，下面将提供一些常见的数据结构考试试题及答案。
一、选择题1. 下面哪个不是线性数据结构？A. 数组B. 链表C. 栈D. 队列答案：D. 队列2. 下面哪个数据结构可以实现先进先出（FIFO）的操作？A. 栈B. 队列C. 链表D. 树答案：B. 队列3. 下面哪个数据结构可以实现后进先出（LIFO）的操作？A. 栈B. 队列C. 链表D. 树答案：A. 栈4. 下面哪个数据结构可以实现快速查找和插入操作？A. 数组B. 链表C. 栈D. 队列答案：A. 数组5. 下面哪个数据结构可以实现快速查找和删除操作？A. 数组B. 链表C. 栈D. 队列答案：B. 链表二、填空题1. 请写出数组的插入操作的时间复杂度。
答案：O(n)2. 请写出链表的删除操作的时间复杂度。
答案：O(1)3. 请写出栈的出栈操作的时间复杂度。
答案：O(1)4. 请写出队列的入队操作的时间复杂度。
答案：O(1)5. 请写出二叉搜索树的查找操作的时间复杂度。
答案：O(log n)三、简答题1. 什么是数据结构？答案：数据结构是计算机存储、组织数据的方式，它定义了数据的逻辑结构和存储结构，以及对数据进行操作的算法。
2. 请解释什么是时间复杂度和空间复杂度。
答案：时间复杂度是衡量算法执行时间的度量，它表示算法执行所需的时间与问题规模之间的关系。
空间复杂度是衡量算法所需的存储空间的度量，它表示算法所需的存储空间与问题规模之间的关系。
3. 请解释什么是递归算法，并给出一个例子。
答案：递归算法是一种自己调用自己的算法。
一个经典的例子是计算斐波那契数列的第n项。
代码如下：```int fibonacci(int n) {if (n <= 1) {return n;}return fibonacci(n-1) + fibonacci(n-2);}```以上就是一些常见的数据结构考试试题及答案。
2018年上海海事大学攻读硕士学位研究生入学考试
试题
（重要提示：答案必须做在答题纸上，做在试题上不给分）考试科目代码828 考试科目名称数据结构及程序设计一．判断题（本题10分，每小题1分）
1．线性的数据结构可以顺序存储，也可以链接存储。
非线性的数据结构只能链接存储。
2．单链表从任何一个结点出发，都能访问到所有结点。
3．单链表形式的队列，头指针F指向队列的第一个结点，尾指针R指向队列的最后一个结点。
4．若在采用链式存储结构线性表中，元素按值有序，则该线性表可以采用折半查找法查找元素。
5．一个栈的输入序列为1, 2, 3, …, n，其输出序列的第二个元素为n的输出序列的个数有n-1种。
6．设串S的长度为n，则S的子串个数为n(n+1)/2。
7．若一个广义表的表头为空表，则此广义表亦为空表。
8．二叉树中除叶节点外，任一节点x，其左子树根节点的值小于该节点(x)的值，其右子树根节点的值大于该节点(x)的值，则此二叉树一定是二叉排序树。
9．网络的最小代价生成树是唯一的。
10．（99, 86, 46, 70, 34, 39, 45, 58, 66, 10 ）是堆。
二．填空题（本题20分，每空2分）
1．一个栈的输入序列是：1、2、3，则不可能的栈输出序列是⑴。
- 2018试题1/6 -。
广西科技大学 2023 年硕士研究生招生考试初试专业课试卷考试科目代码：817 考试科目名称：数据结构与程序设计（学）考试时间：180分钟（本试题共 8 页）一、判断题（每小题2分，共20分）1. C语言编译系统在判断一个量是否为“真”时，以0代表“假”，以非0代表“真”。
2. 在选择结构中，else总是与它前面最近的那个if相配套的。
3. 在switch语句中可以没有default语句。
4. 在循环结构中使用break语句或者continue语句，其作用是相同的。
5. for循环语句只能用于循环次数已知的情况。
6. 若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用顺序表存储最节省时间。
7.若一个栈的输入序列为{1, 2, 3, 4, 5}，则不可能得到{3, 4, 1, 2, 5}这样的出栈序列。
8. 若一搜索树（查找树）是一个有n个结点的完全二叉树，则该树的最小值一定在叶结点上.9. 某二叉树的前序和中序遍历序列正好一样，则该二叉树中的任何结点一定都无左孩子。
10. 图的广度优先遍历相当于二叉树的后序遍历。
二、选择题（每小题2分，共40分）1. 下列不属于C语言数据类型的是：A. intB. floatC. stringD. char2. 下面程序段的输出为：int a = 3, b = 5;if(a = b)printf("%d=%d", a, b);elseprintf("%d!=%d", a, b);A. 5=5B. 3=3C. 5!=3D. 3!=53.下面叙述正确的是:A. 2/3 与2.0/3.0 等价B. (int)2.0/3 与2/3 等价C. ++5 与6 等价D. 'A'与"A"等价4.在C语言中,函数返回值的类型最终取决于：A. 函数定义时在函数首部所说明的函数类型B. return语句中表达式值的类型C. 调用函数时主调函数所传递的实参类型D. 函数定义时形参的类型5.若函数调用时的实参为变量,下列关于函数形参和实参的叙述中正确的是：A. 函数的实参和其对应的形参共占同一存储单元B. 形参只是形式上的存在, 不占用具体存储单元C. 同名的实参和形参占同一存储单元D. 函数的形参和实参分别占用不同的存储单元6. 设int x=3, y=2，则表达式x / y的值是:A. 1.500000B. 1C. 1.5D. 以上都不对7. 以下程序的输出结果是：#include<stdio.h>int main()int x = 10;switch (x){case 30: printf("A");break;case 10: printf("B");case 20: printf("C");break;case 40: printf("D");}printf("E");}A. ABCDEB. ABCEC. BCDED. BCE8. C语言中有三种循环语句，为了方便循环流程的控制，经常会使用break语句，关于break语句的描述，正确的是:A. break语句可以出现在循环控制语句之外的任何地方B. 执行break语句的结果是本次循环必须执行完毕C. 执行到break，则直接跳出该循环体，继续执行循环体后面的语句D. break语句是终止本次循环的执行，然后测试循环条件，准备进行下一次循环过程9.以下能对二维数组a进行正确初始化的语句是:A. int a[2][ ] = {{1,0,1},{5, 3}};B. int a[ ][3] = {{1,2,3},{4,5,6}};C. int a[2][4] = {1,2,3,},{4,5},{6}};D. int a[ ][3] = {{1,0,1},{},{1,1}};10.定义下列结构体数组：struct stu{ char name[10]；int age；}a[5] = {"ZHAO",14, "WANG",15, "LIU",16, "ZHANG",17}；执行语句printf("%d, %s",a[2].age, a[1].name)的输出结果为:A. 15, ZHAOB. 16, WANGC. 17, LIUD. 17, ZHAO11.先序遍历图示二叉树的结果为:A. A，B，C，D，H，E，I，F，GB. A，B，D，H，I，E，C，F，GC. H，D，I，B，E，A，F，C，GD. H，I，D，B，E，F，G，A，C12.带头结点的单链表h为空的判定条件是:A. h == NULL;B. h->next == NULL;C. h->next == h;D. h != NULL;13.设一个堆栈的入栈顺序是1、2、3、4、5。
来源网络，造福学生———————欢迎下载，祝您学习进步，成绩提升———————2018年攻读硕士学位研究生入学考试试题科目代码与名称：846数据结构与C程序设计适用专业或方向：计算机科学与技术（各方向）考试时间：3小时满分：150分试题编号：B（必须在答题纸上答题，在试卷上答题无效，答题纸可向监考老师索要）第一部分数据结构（80分）B卷一、单项选择题（20个选题，每选题2分，共40分）（备注：答题时每连续的5个为一组，组与组之间要留有空隙,例如，ACCCD ACDAC)1.从逻辑结构来说，栈属于OA.树形结构B.散列表结构C.线性结构D.图状结构2.程序段for (i=0,k=0; i<100; i++)for (j=0; j<10000; j++) k++;的时间复杂度是。
A.0(1)B. 0(n*m)C. 0(n+m)D. 0(Max(n, m))3.若线性表釆用顺序存储结构，则在删除一个元素时需要移动的元素的次数与有关。
A.首地址B.元素的值C.线性表的有序性D.删除位置4.在一个带头结点的表长为5的循环单链表中，若其头指针为L,则在它的第一个元素结前插入S所指结点，则执行OA.s->next=L->next; L->next=s；B. L->next=s-〉next-〉next；C. s->next=L->next~>next； L~>next=sD. s->next=L-〉next； L->next=L;5.队列操作的特征是oA.先进先出B.先进后出C.插入在队头D.删除的是队尾6.在递归程序的执行过程中要用到。
A.栈B.循环结构C.顺序结构D.队列第1页，共7页7.用x表示入栈操作，用s表示出栈操作，若栈的初始状态为空，则下面—合法的操作序列。
A. xssssxxxB. xssxxsxxC. XXSXSSXD. SSSXXXXSSXX第2页，共7页第3页，共7页D. 19, 78, 32, 52, 12, 44, 66 .是错误的。
数据结构期末考试试题和标准答案及评分标准《数据结构》试题（A卷）（考试时间： 90分钟）一、单项选择题（本大题共15小题，每小题2分，共30分）（每题只有一个选项是正确的,将答案填写在括号内，错选、多选不得分）1.（）是组成数据的基本单位，是一个数据整体中相对独立的单元。
A．数据 B.数据元素 C.数据对象 D.数据结构2.算法计算量的大小称为算法的（）。
A.效率B.复杂度C.数据元素之间的关系??? ?D.数据的存储方法3.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入或删除运算，则采用以下（）方式最节省时间。
A.链式存储B. 索引存储C.顺序存储D.散列存储4.下述哪一条是顺序存储结构的优点？（）A.存储密度大?B.插入运算方便?C.删除运算方便?D.可方便地用于各种逻辑结构的存储表示5.在一个单链表中，若删除p所指结点的后续结点，则执行（）。
>next=p->next->next >next=p->next=p->next;p->next=p->next->next =p->next->next6.带头结点的单链表head为空的判定条件是（）。
==NULL >next==NULL >next==head !==NULL7.非空的循环单链表head的尾结点(由p所指向)满足（）。
>head==NULL ==NULL >next==head ==head8.下面关于线性表的叙述中，错误的是哪一个？（）A.线性表采用顺序存储，必须占用一片连续的存储单元。
B.线性表采用顺序存储，便于进行插入和删除操作。
C.线性表采用链式存储，不必占用一片连续的存储单元。
D.线性表采用链式存储，便于插入和删除操作。
9.队列操作的原则是（）。
A.后进先出B.先进先出C.只能进行插入D.只能进行删除10.栈中允许进行插入和删除的一端称为（）。
上海交通大学一九九七年硕士研究生入学考试试题
试题名称：数据结构及程序设计技术
试题编号：１９
题一（６分）有五个数依次进栈：1,2,3,4,5.在各种出栈的序列中，以3,4先出的序列有哪几个。
（３在４之前出栈）
题二（４分）试写出进栈操作，出栈操作算法的时间复杂性。
题三（４分）已知ＫＭＰ串匹配算法的模式串是AABBAAB,试写出改进后的NEXT信息帧。
题四（４分）设某通信电文由Ａ、Ｂ、Ｃ、Ｄ、Ｅ、Ｆ六个字符组成，它们在电文中出现的次数分别是16,5,9,3,20,1。
试画出编码用的哈夫曼树。
题五（５分）已知某排序平衡二叉树Ｔ具有下列特点：（１）结点的关键字均在1到9范围内；（２）在Ｔ中存在一个关键字为n1的叶结点，若删去该结点，立即插入一个关键字为n1的结点，得到的平衡树与原Ｔ不相同；（３）在Ｔ中存在另一个关键字为n2的非叶结点，删去它，并立即插入n2结点，得到与原Ｔ相同的平衡树；（４）在Ｔ中插入某n3结点后立即删除它，得到的平衡树与原Ｔ不相同。
试画出具有上述特点的最简单（结点个数最少）的平衡树Ｔ，并写明n1,n2,n3分别等于几？
题六（９分）某整型数组Ａ的１０个元素值依次为6,2,9,7,3,8,4,5,0,1,用下列各排序方法，将Ａ中元素由小到大排序。
（1）取第一个元素值６作为分割数，（2）试写出快速排序第一次分隔后Ａ中的结果。
（3）用堆排序，（4）试写出将第一个选出的数据放在Ａ的最后位置上，（5）将Ａ调整成堆后的Ａ中结果。
（6）用基数为３的基数排序法，（7）试写出第一次分配和收集后Ａ中的结果。
题七（１４分）某赋权有向图及它的单邻接表如下：
（1）试写出深度优先搜索顺序。
（2）画出深度优先生成树。
（3）将该图作为ＡＯＥ网络图，（4）试写出Ｃ的最早发生时间及活动ＦＣ的最晚开始时间。
（5）用Dijkstra算法计算源点Ａ到各顶点的最短路径，（6）试写出当计算出ＡＤ及ＡＧ的最短路径时，（7）Ａ到其它各点路径（中间结点）的值。
始点
2 3
3 2
1 2 1 3
1 5
终点
请在下列各题的（N）处，填写适当的Pascal语句（或其它成份），完成各题的程序。
题八（１０分）下列程序输入一个正整数N(０<n<10)，打印1,2,….,n各数字的全排列，例如输入n=3,打印123,132,213,231,312,321
program exam8(input,output);
const maxn=9;
var a:array[1..maxn] of integer;{放全排序一个值}
s:set of 1..maxn;{放１到９各数字的集合}
n:integer
procedure load(j:integer);{将Ｓ中数字装入到a中}
var j,k integer;
begin
for j:=1 to n do
if j in s
then begin
s:= (1)
a[i]:=j;
if i<n
then (2)
else for k:=1 to n do writen(a[k]);
(3)
end
end{load};
begin {main}
readln(n); s:=[1..n]; load(1)
end.
题九（１０分）下面的过程对二叉树进行后序遍历（非递归）。
假设已有栈的一些操作过程说明。
并说明树的结点类型：
type pointer= node;
node=record
data:integer ;
left,right :pointer
end;
procedure post(p:pointer);
var q:pointer;
begin
if p<> then
begin create_stack(s);{建立一个Ｓ栈，并初始化为空栈}
while (P<>nil) or not empty_stack(s){s栈不空} do
if p<>nil
then begin
push(s,p); {将Ｐ进栈}
push(s,p);{P作为标记进栈}
P:= （１）
end
else begin
pop(s,p);{将标记退出Ｓ栈}{退出到Ｐ中}
if p<>nil
then begin
push(s,nil){标记进栈}
（２）；
end
else begin
（3）；
write(q .data);{访问结点，打印结点数据}
end
end
end{post}
题十（８分）设结点的类型定义如下：
type
node=record data:integer; link:integer end;
在数组a中存放了１０个结点：
var a:array[1..10] of node;
假定在主程序中已经执行了下列语句：
for i:=1 to 10 do
begin a[i].data:=i, a[i].link:=0 end;
最初将１０个结点看成分别属于１０个集合，每个集合有且仅有一个结点，调用下面过程，判断data=m和data=n的两个结点是否在同一个集合中（最初肯定属于不同集合，除非m=n），若不在同一集合中，则将这两个结点合并到一个集合中。
否则，已在同一个集合中，什么也不做。
（此方法用于Kruskal求最小生成树的算法中）procedure merge_set(m,n:integer);
function find(k:integer):integer;
var f:integer;
begin
f:=k;
while a[k].link<>0 do f:=a[k].link;
(1) ;
end;
begin
m:=find(m); n:=frind(n);
if m<>n then (2)
end{merge_set}
题十一（１４分）设有数组变量说明：
var a:array[1..n] of record key:integer; next:0..n end;
假设各元素的key已有值，并且假设最大值＜＝９９９９，再假定在主程序已执行下面语句，已将各元素组成一个链；
for i:=Øto n-1 do a[i].next:=i+1;
a[i]:= Ø
下面是以10为基的基数排序法过程，将数组a按Key由小到大排序。
Procedure bucket_sorting;
Const maxkey=9999;
Var bucket,tail :array[0..9] of 0..n;
P,last:0..n;
i:=0..9;
d:integer;
begin
d:=1;
repeat
for i:=0 to 9 do tail[i]:= Ø;
{分解}
P：＝a[0].next;{a[0].next是链的第一个结点}
While P<> Ø do
Begin i:=a[p].key div d mod 10;
If (1)
Else a[ (2) ].next:=p;
Tail[i]:=p;
(3)
end
{收集}
last:=0
for i:=0 to 9 do
if (4)
then begin
a[last].next:= (5) ;
last:= (6)
end;
a[last].next:= Ø;
d:= (7)
until d>maxkey
end{bucket_sorting}
题十二（12分）下面是一个判断二叉树是否是排序平衡树的函数说明，若是排序平衡树，则返回值为真，否则返回值假，另外，以参数的形式返回二叉树的高度和最大最小结点值。
结点的类型定义与题九的定义相同。
Function isbalance(p:pointer;var h,min,max:integer)
Var hleft,hright,lmax,rmin:integer;
Begin
If p<>nil
then begin
if osbalance(p .left,hleft, (1) )
and isbalance(P .right,hright, (2) )
then begin
if hleft=0
then begin min:=p .data; lmax:=p .data-1 end;
if hright=0
then begin max:=p .data; rmin=p . data+1 end;
if hleft>hright
then h:=hleft+1 else h:=hright+1;
isbalanced:=(abs(hleft-hright)<=1)
and ( (3) )
and ( (3) )
end
else isbalanced:=false
end
else begin h:=0; isbalanced:=true end
end{isbalance}
来源：上海教育热线 202.120.8.177
雅舍考研之路/ky。
