北京工业大学数据结构与C++程序设计考研真题试题2007年

–
运算处理

内容：建表、插入、删除、输出； 实现：利用指针变量作为函数参数，传递 线性表地址；
•void CreateList (SequenList *L) { • int n, i, mydata;
• printf("\nPlease input total number of data item\n");


int exp;
struct polyterm *next;

} TERM;

10．设有编号为1，2，3，4的四辆列车，顺序 进入一个栈式结构的车站，具体写出这四辆列 车开出车站的所有可能的顺序。


1， 2， 3， 4 1， 3， 4， 2 2， 1， 4， 3 2， 4， 3， 1 3， 4， 2， 1
–
人—机交互部分

内容：通过屏幕提示功能选择菜单； 通过键盘输入实现功能的选择； 要求：提示内容清晰易读，

键盘操作简单准确；

实现：循环扫描键盘，等待用户输入；
根据输入内容确定要执行的分支程序。










int main( ) { SequenList MyList,*L; char cmd; int i, t, x; L=&MyList; L->last=-1; do { do { clrscr( ); printf("\n\t c, C......Create List\n"); printf("\n\t i, I .....Insert"); printf("\n\t d, D......Delete"); •while •While ((cmd!='d')&&(cmd!='D')&& ((toupper(cmd)!='D')&& printf("\n\t q, Q......Quit\n\tYour choice:"); (cmd!='q')&&(cmd!='Q')&& (toupper(cmd)!='Q')&& cmd=getchar( );

已知一个图的顶点集 V 和边集 E 分别为：V={1,2,3,4,5,6,7}; E={(1,2)3,(1,3)5,(1,4)8,(2,5)10,(2,3)6,(3,4)15, (3,5)12,(3,6)9,(4,6)4,(4,7)20,(5,6)18,(6,7)25}; 用克鲁斯卡尔算法得到最小生成树，试写出在最小生成树中依次得到的各条边。 4. 画出向小根堆中加入数据 4, 2, 5, 8, 3 时，每加入一个数据后堆的变化。 四、阅读算法（每题 7 分，共 14 分） 1. LinkList mynote(LinkList L) {//L 是不带头结点的单链表的头指针 if(L&&L->next){ q=L；L=L－>next；p=L； S1： while(p－>next) p=p－>next； S2： p－>next=q；q－>next=NULL； 3. L； } 请回答下列问题： （1）说明语句 S1 的功能； （2）说明语句组 S2 的功能； （3）设链表表示的线性表为（a1,a2, …,an）,写出算法执行后的返回值所表示的线性 表。 2. void ABC(BTNode * BT) { if BT { ABC (BT->left); ABC (BT->right); cout<<BT->data<<' '; } } 该算法的功能是：
数据结构试卷（二）
一、选择题(24 分) 1．下面关于线性表的叙述错误的是（ ） 。 (A) 线性表采用顺序存储必须占用一片连续的存储空间 (B) 线性表采用链式存储不必占用一片连续的存储空间 (C) 线性表采用链式存储便于插入和删除操作的实现 (D) 线性表采用顺序存储便于插入和删除操作的实现 2．设哈夫曼树中的叶子结点总数为 m，若用二叉链表作为存储结构，则该哈夫曼树中总共 有（ ）个空指针域。 (A) 2m-1 (B) 2m (C) 2m+1 (D) 4m 3．设顺序循环队列 Q[0：M-1]的头指针和尾指针分别为 F 和 R，头指针 F 总是指向队头元素 的前一位置，尾指针 R 总是指向队尾元素的当前位置，则该循环队列中的元素个数为 （ ） 。 (A) R-F (B) F-R (C) (R-F+M)％M (D) (F-R+M)％M 4．设某棵二叉树的中序遍历序列为 ABCD，前序遍历序列为 CABD，则后序遍历该二叉树 得到序列为（ ） 。 (A) BADC (B) BCDA (C) CDAB (D) CBDA 5．设某完全无向图中有 n 个顶点，则该完全无向图中有（ ）条边。 2 2 (A) n(n-1)/2 (B) n(n-1) (C) n (D) n -1 6．设某棵二叉树中有 2000 个结点，则该二叉树的最小高度为（ ） 。 (A) 9 (B) 10 (C) 11 (D) 12 7．设某有向图中有 n 个顶点，则该有向图对应的邻接表中有（ ）个表头结点。 (A) n-1 (B) n (C) n+1 (D) 2n-1 8．设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字 5 为基准进行一趟快 速排序的结果为（ ） 。 (A) 2，3，5，8，6 (B) 3，2，5，8，6 (C) 3，2，5，6，8 (D) 2，3，6，5，8

一、选择题1. 算法的计算量的大小称为计算的（ B ）。

【北京邮电大学2000 二、 3（ 20/8 分）】A．效率 B.复杂性 C.现实性 D.难度2.算法的时间复杂度取决于（ C ）【中科院计算所1998二、1（2分）】A．问题的规模 B.待处理数据的初态 C. A 和 B3.计算机算法指的是（ C），它必须具备（ B）这三个特性。

(1) A ．计算方法 B.排序方法 C. 解决问题的步骤序列D. 调度方法(2) A ．可执行性、可移植性、可扩充性 B .可执行性、确定性、有穷性C. 确定性、有穷性、稳定性D.易读性、稳定性、安全性【南京理工大学1999一、1（2分）【武汉交通科技大学1996一、1（ 4 分）】4．一个算法应该是（B）。

【中山大学1998二、1（2分）】A ．程序B．问题求解步骤的描述C．要满足五个基本特性D．A 和 C.5.下面关于算法说法错误的是（D）【南京理工大学2000一、1（1.5分）】A．算法最终必须由计算机程序实现B.为解决某问题的算法同为该问题编写的程序含义是相同的C. 算法的可行性是指指令不能有二义性D.以上几个都是错误的6.下面说法错误的是（C）【南京理工大学2000一、2（1.5分）】(1）算法原地工作的含义是指不需要任何额外的辅助空间（ 2）在相同的规模n 下，复杂度O(n) 的算法在时间上总是优于复杂度nO(2 ) 的算法（ 3）所谓时间复杂度是指最坏情况下，估算算法执行时间的一个上界（ 4）同一个算法，实现语言的级别越高，执行效率就越低4A ． (1) B.(1),(2) C.(1),(4) D.(3)7．从逻辑上可以把数据结构分为（C）两大类。

【武汉交通科技大学1996一、4（2 分）】A．动态结构、静态结构B．顺序结构、链式结构C．线性结构、非线性结构D．初等结构、构造型结构8．以下与数据的存储结构无关的术语是（D）【。

北方交通大学2000二、1（ 2 分）】A．循环队列 B.链表 C.哈希表 D.栈9．以下数据结构中，哪一个是线性结构（D）？【北方交通大学2001一、 1（ 2 分）】A．广义表 B.二叉树 C.稀疏矩阵 D.串10．以下那一个术语与数据的存储结构无关？（ A 【）北方交通大学 2001 一、2（ 2 分）】A．栈 B.哈希表 C.线索树 D.双向链表11．在下面的程序段中，对x 的赋值语句的频度为（C）【北京工商大学2001 一、 10（ 3 分）】FOR i:=1 TO n DOFOR j:=1 TO n DOx:=x+1;A． O(2n)B． O(n)C2Dn ．O(n )． O(log 2 )12．程序段 FOR i:=n-1 DOWNTO 1 DOFOR j:=1 TO i DOIF A[j]>A[j+1]THEN A[j]与 A[j+1] 对换；其中 n 为正整数，则最后一行的语句频度在最坏情况下是（D）A. O （ n）B. O(nlogn)C. O(n3)D.O(n 2)【南京理工大学 1998 一、 1(2 分 ) 】13．以下哪个数据结构不是多型数据类型（D）【中山大学1999一、 3（1 分）】A．栈B．广义表C．有向图D．字符串14．以下数据结构中，（ A）是非线性数据结构【中山大学1999一、4】A．树B．字符串C．队D．栈15.下列数据中，（ C ）是非线性数据结构。

中国科学院研究生院2007年招收攻读硕士学位研究生入学统一考试试题科目名称：计算机软件基础 考生须知：1．本试卷满分为150分，全部考试时间总计180分钟。

2．所有答案必须写在答题纸上，写在试题纸上或草稿纸上一律无效。

数据结构部分（共70分）一、选择题（共10分，每题1分）1、对于顺序存储的线性表，访问结点和增加结点的时间复杂度为（ ）A ．O(n) O(n)B ．O(n) O(1)C ．O(1) O(n)D ．O(1) O(1)2、对于一个头指针为head 的带头结点的单链表，判断该表为空的条件是（ ）。

A ．head=NULLB ．head Ænext=NULLC ．head Ænext=headD ．head!=NULL3、在双向链表中删除指针p 所指的结点时需要修改指针（ ）。

A ．p Ællink Ærlink=p Ærlink ； p Ærlink Ællink=p ÆllinkB ．p Ællink=p Ællink Ællink ； p Ællink Ærlink=pC ．p Ærlink Ællink=p ；p Ærlink=p Ærlink ÆrlinkD ．p Ærlink=p Ællink Ællink ；p Ællink=p Ærlink Ærlink4、若一个栈的输入序列为1、2、3、…、n ，输出序列的第一个元素为i ，则第j 个输出元素为（ ）。

A ．i-j-1B ．i-jC ．j-i+1D ．不确定5、若度为m 的哈夫曼树中，其叶结点个数为n ，则非叶结点的个数为（ ）。

A ．n-1B ．/1n m −⎢⎥⎣⎦C ．D ．(1)/(1)n m −−⎢⎣⎥⎦/(1)1n m −−⎢⎥⎣⎦6、一棵二叉树的前序遍历序列为ABCDEFG ，它的中序遍历序列可能是（ ）。

2006级(嵌入式软件与系统、计算机应用方向)《数据结构》期终考试试卷答案一、单项选择题 (每题1分，共15分)答案：C, A, B, B, C, D, D, C, D, A, B, B, A, C, A二、已知一个无向图的顶点集为{ a , b , c , d , e , f }，其邻接矩阵如下所示(0-无边,1-有边)。

⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡00110001101110110111010001101010010fe d c b af e d c b a(1). 画出该图的图形；(2). 根据邻接矩阵从顶点a 出发进行广度优先遍历，画出相应的广度优先遍历树。

(15分) 解：(1). 该邻接矩阵所对应的的图2.1所示(2). 从顶点a 出发进行广度优先遍历的遍历树如图2.2所示三、已知一个散列表如下图所示：其散列函数为h (key ) = key % 13，处理冲突的方法为双重散列法，探查序列为:h i = (h (key ) + i * 3) % 13, i = 1, 2, …问：对表中关键字61进行查找时，所需进行的比较次数为多少？依次写出每次的计算公式和值。

(10分)解：在表中查找关键字61时，所需进行的计算公式如下:h (61) = 61 % 13 = 9h 1 = (9 + 1 * 3) % 13 = 12图2.1 图2.2 a b e d f ch 2 = (9 + 2 * 3) % 13 = 15 % 13 = 2由上过程可知：在表中查找关键字61时，需要进行3次比较。

四、阅读下面程序，回答问题 (10分)void function(Link **Head) {Link *pt1, *pt2, *tmp; pt1 = *Head;if (pt1 == NULL) return;pt2 = pt1->next; pt1->next = NULL;// 语句行S 1while (pt2 != NULL) { tmp = pt2->next;pt2->next = pt1; pt1 = pt2; pt2 = tmp; }*Head = pt1;// 语句行S 2}回答下列问题：(1). 说明语句行S 1和S 2的作用(指对单向链表中所起的作用)；(2). 简洁地给出函数function 的功能描述(非每条语句的语义说明)；(3). 若链表Head 的线性表形式为(a 1, a 2, …, a n )，写出函数执行后链表Head 的线性表形式。

1求两个数的和与差输入整数a和b,计算并输出a、b的和与差。

(例：输入2 -8;输出The sum is -6 The difference is 10)#include <stdio.h>int main(){int a,b,sum,diff;scanf(H%d%d n,&a,&b);sum=a+b;diff=a-b;printf(n The sum is %d\n H,sum);printf(n The difference is %d\n*\diff)；} 2 求平方根输入1个实数x,计算并输出其平方根 (保留1位小数)。

(例:输入17;输出The square root of 17.0 is 4.1)#include <stdio.h>#include <math.h>int main()(double x,root;scanf(n%lf n,&x);root=sqrt(x);printf(n The square root of %0.1f is % 0. lf\n n ,x,root);}3华氏温度转换为摄氏温度输入华氏温度f,计算并输出相应的摄氏温度c(保留2位小数)。

c = 5/9(f-32).(例：括号内是说明输入17.2 (华氏温度)输出The temprature is -8.22)#include <stdio.h>int main()(double f,c;scanf(H%lf n,&f);c=5.0/9.0*(f-32.0);printf(n The temprature is %0.2f\n n,c);} 4计算旅途时间输入2个整数timel和time2,表示火车的出发时间和到达时间，计算并输出旅途时间。

有效的时间范围是0000到2359, 不需要考虑出发时间晚于到达时间的情况。

例：括号内是说明输入712 1411 (出发时间是7：12,到达时间是14：11)输出The train journey time is 6 hrs 59 mins.#include <stdio.h>int main()(int timel,time2,hours,mins;scanf(n%d%d H,&timel,&time2);timel=timel/100*60+timel % 100;time2= time2/100*60+time2% 100;hours=(time2-timel)/60;mins=(time2-timel) % 60;printf(n The train journey time is %d hrs %d mins An'hours,mins);}5大写字母转换成小写字母输入一个大写英文字母，输出相应的小写字母。

C．视图中的元组 D．基本表中的元
组
5．对于下列语句，正确的描述是（ ）。
ALTER TABLE Product ADD order_date DATE DEFAULT ‘1985-01-01’
A．向 Product 表中增加一个名为“DATE”的属性 B．该属性有一个默认的值为“1985-01-01” C．该属性的数据类型是日期型 D．该属性可以指定为主码 四、 简答题（45 分） 1．DBA 的职责是什么？（5 分） 2．什么是数据库的完整性？为了维护数据库的完整性，DBMS 应该具备哪些功 能？（10 分） 3．什么是数据库的概念结构？试述其特点和设计策略。（10 分） 4．数据库系统中可能发生哪几类的故障？（12 分） 5．什么是数据挖掘？其目的是什么？涉及哪些技术？和传统分析方法的区别是 什么？（8 分） 五、 综合题（60 分）
北京工业大学 2007 年硕士研究生入学考试试题
科目代码：805
科目名称：数据库技术与应用 所有答案必须做在答题纸上，
做在试题纸上无效！
一、 填空（15 分，每空 1 分）
1．数据模型通常由_________、_________和_________部分组成。
A．1
B．2
C．3
D．4
三、 多项选择题（10 分，每题全选对得 2 分，漏选或多选得 0 分）
1．通过 CREATE USER 语句新创建的用户有（ ）权限。
A．CONNECT B．RESOURCE C．DBA D．创建一个新的数据库用户
2．使用 ODBC 开发应用系统，其体系结构由（ ）组成。
么全不做。
9．为了保证事务的隔离性和一致性，DBMS 需要对并发操作进行正确调度，这
些就是数据库管理系统中___________机制的责任。

delete(Dt,A) 初始条件：字典 Dt 存在，A 是字典元素 操作结果：删除数据 A
find(Dt,A) 初始条件：字典 Dt 存在，A 是字典元素 操作结果：查找字典数据，返回位置信息
（2）链式存储结构，方便更新
第 5 页 共 16 页
友情提供，请勿传播，谢谢合作--------picco
2006 真题答案
一．选择题 ADCBD 二．填空题 1.O(nu+tu) 三．解答题
2.A GOOD STUDENT
3.7、11、13、14
4.直接插入排序
4（1）35%13=9， h1(35)=35%11+1=13 H2(35)=(9+2*3)%11=4 四．抽象数据类型设计题
ADT dictionary{ 数据对象 D：D 是具有相同特性的数据元素的集合，每个元素由两部分组成，分别为关键码和属
2空间上直接插入排序不需额外的空间快速排序需要递归工作栈所以直接插入排序的空间性能更好时间上序列长度较小因为两个子序列分别有序直接插入排序比较次数较少但快速排序在序列基本有序时效率反而下降所以直接插入排序时间性能更好四
友情提供，请勿传播，谢谢合作--------picco
说明：此答案是我考研时所做，先整理出来，正确率足够使用，但不保证所有题都正确，请按自己的 情况酌情处理。另外我没有公开此档案，希望拿到的同学不要传播（我直接的朋友可以传给自己的真实同 学，但请间接朋友不要继续往下传），不要宣传从我这里得到，毕竟这样的独家资料对你们也有好处。这 份资料价值很高，我整理也很费劲，所以请尊重我的劳动。真题可以从王道论坛下载，从 1995 年的开始， 但我建议从 2003 年开始看，因为以前的题太旧了，跟现在的考试风格差别很大，所以我的答案也是从 03 年开始的。

第二章习题与解答一判断题1．线性表的逻辑顺序与存储顺序总是一致的。

2．顺序存储的线性表可以按序号随机存取。

3．顺序表的插入和删除操作不需要付出很大的时间代价，因为每次操作平均只有近一半的元素需要移动。

4．线性表中的元素可以是各种各样的，但同一线性表中的数据元素具有相同的特性，因此是属于同一数据对象。

5．在线性表的顺序存储结构中，逻辑上相邻的两个元素在物理位置上并不一定紧邻。

6．在线性表的链式存储结构中，逻辑上相邻的元素在物理位置上不一定相邻。

7．线性表的链式存储结构优于顺序存储结构。

8．在线性表的顺序存储结构中，插入和删除时，移动元素的个数与该元素的位置有关。

9．线性表的链式存储结构是用一组任意的存储单元来存储线性表中数据元素的。

10．在单链表中，要取得某个元素，只要知道该元素的指针即可，因此，单链表是随机存取的存储结构。

二单选题 (请从下列A，B，C，D选项中选择一项)1．线性表是( ) 。

(A) 一个有限序列，可以为空；(B) 一个有限序列，不能为空；(C) 一个无限序列，可以为空；(D) 一个无序序列，不能为空。

2．对顺序存储的线性表，设其长度为n，在任何位置上插入或删除操作都是等概率的。

插入一个元素时平均要移动表中的（）个元素。

(A) n/2 (B) n+1/2 (C) n -1/2 (D) n3．线性表采用链式存储时，其地址( ) 。

(A) 必须是连续的；(B) 部分地址必须是连续的；(C) 一定是不连续的；(D) 连续与否均可以。

4．用链表表示线性表的优点是（）。

(A)便于随机存取(B)花费的存储空间较顺序存储少(C)便于插入和删除(D)数据元素的物理顺序与逻辑顺序相同5．某链表中最常用的操作是在最后一个元素之后插入一个元素和删除最后一个元素，则采用( )存储方式最节省运算时间。

(A)单链表(B)双链表(C)单循环链表(D)带头结点的双循环链表6．循环链表的主要优点是( )。

(A)不在需要头指针了(B)已知某个结点的位置后，能够容易找到他的直接前趋(C)在进行插入、删除运算时，能更好的保证链表不断开(D)从表中的任意结点出发都能扫描到整个链表7．下面关于线性表的叙述错误的是( )。

一、选择题（每题1分，共20分）1．设 int b=2;表达式b/(b*2)的值是（）。

A. 0B. 0.5C. 0.500000D. 0.000002．下列标识符中不合法的标识符的是（）。

A. hot_doB. cat1C. _priD. 2ab3．以下程序的输出结果是（）。

void main(){int k=17；printf("%d，%o，%x \n"，k，k，k)；}A. 17，021，0x11B. 17，17，17C. 17，0x11，021D. 17，21，114．设x、y、z和k都是int型变量，则执行表达式：x=（y=4，z=16，k=32）后，x的值为（）。

A．4 B．16 C．32 D．525．下述程序段中，while循环执行次数是( )。

int k=0;while(k=1) k++;A. 无限次B. 有语法错误，不能执行C. 一次也不执行D. 执行一次6. 若要求在if后一对圆括号中表示a不等于0的关系,则能正确表示这一关系的表达式为（）。

A. a < > 0B. !aC. a=0D. a!=07．执行下述语句后,*(p+1)的值是( )。

char s[]= “ab”,*p；p=s;A.‘b’B. OC. 不定值D. 非法引用128．有以下语句:int b;char c[10];,则正确的输入语句是( )。

A. scanf("%d%s",&b,&c);B. scanf("%d%s",&b,c);C. scanf("%d%s",b,c);D. scanf("%d%s",b,&c);9．能正确表示a 和b 同时为正或同时为负的逻辑表达式是（ ）。

A. (a>=0‖b>=0)&&(a<0‖b<0)B. (a>=0&&b>=0)&&(a<0&&b<0)C. (a+b>0)&&(a+b<=0)D. a*b>010．C 语言中的逻辑运算结果，用（ ）表示逻辑“真”值。

计算机专业基础综合数据结构（排序）历年真题试卷汇编6(总分：108.00，做题时间：90分钟)一、单项选择题(总题数：44，分数：88.00)1.某内部排序方法的稳定性是指____。

【南京理工大学1997年】（分数：2.00）A.该排序算法不允许有相同的关键字记录B.该排序算法允许有相同的关键字记录C.平均时间为O(nlogn)的排序方法D.以上都不对√解析：解析：考查排序算法的稳定性。

如果排序前后有相同关键字的记录的前后顺序不变，则称此排序是稳定的。

2.若要求尽可能快地对序列进行稳定的排序，则应选____。

【北京邮电大学2001年】（分数：2.00）A.快速排序B.归并排序√C.冒泡排序D.根排序解析：解析：考查排序算法的稳定性及算法效率。

归并排序和冒泡排序是稳定的，冒泡排序的平均时间复杂度为O(n 2 )，归并排序的平均时间复杂度为O(nlog 2 n)。

3.下列排序方法中，____是稳定的排序方法。

【北方交通大学2001】（分数：2.00）A.直接选择排序B.二分法插入排序√C.希尔排序D.快速排序解析：解析：考查稳定的排序算法有哪些。

插入排序、冒泡排序、二路归并排序、基数排序是稳定的排序算法，选择排序、希尔排序、快速排序、堆排序属于不稳定排序。

4.对有n个记录的表做直接插入排序，在最好情况下，需比较____次关键字。

【华中科技大学2006年】（分数：2.00）A.n-1 √B.n+1C.n／2D.n(n-1)／2解析：解析：考查最好情况下直接插入排序比较次数。

在最好的情况下，即初始序列有序列，则每次循环只需与前一个元素比较1次，且不需要移动，总的比较次数为n—1。

5.对n个不同的数据利用冒泡法从小到大排序，在下列哪种情况下元素交换的次数最多____。

【北京交通大学2007年】（分数：2.00）A.从大到小排列好的√B.从小到大排列好的C.元素无序D.元素基本有序解析：解析：考查冒泡排序最差的情况。

练习1 分支1.若从键盘输入58，则以下程序段的输出结果是（58 58 58）：int main(void){int a;scanf(“%d”,&a);if (a>50) printf(“%d”,a);if(a>40) printf(“%d”,a);if(a>30) printf(“%d”,a);return 0;}2.下列程序运行的输出结果是（9）：没有遇到break语句，继续执行到switch语句结束int main(void){char c=’b’;int k=4;switch(c) {case ‘a’: k=k+1; break;case ‘b’: k=k+2;case ‘c’: k=k+3;}printf(“%d\n”,k);return 0;}练习2 循环一、读程序写结果1.阅读下列程序并回答问题：main(){inti,j,k=0,m=0;for(i=0;i<2;i++){; /*第6行*/for(j=0;j<3;j++)k++;m++; /*第9行*/}printf(“k=%d,m=%d\n”,k,m);}（1）程序的输出是___k=6,m=2___________。

（2）将第9行改为“m=m+k;“ ，程序的输出是____k=6,m=9_________。

（3）将第6行改为“k=0;”，将第9行改为“m=m+k;”，程序的输出是________k=3,m=6____________。

2.请阅读下面的程序,并回答下列问题#include <stdio.h>int main(){int digit=0,letter=0, other=0;charch;printf("Enter a line text:");do {ch = getchar();if((ch>= 'a' &&ch<= 'z' ) || ( ch>= 'A' &&ch<= 'Z'))letter ++;else if(ch>= '0' &&ch<= '9')digit ++;elseother ++;}while(ch!='\n');printf("letter=%d, digit=%d, other=%d\n", letter, digit, other); }(1)若在程序运行时输入 Today_is_2013/12/28<回车>letter=7, digit=8, other=5(2)简述程序的主要功能:统计输入字符串中字母数字和其他字符的个数。

南京邮电大学2007攻读硕士研究生入学考试数据结构试题（参考答案）一、判断题（每题2分，共12分，请答“是”或“否”）（）1．算法必须至少有一个输入，否则就不能称为一个算法。

【答案】否。

（）2．设有一个堆栈和一个队列。

现有元素序列（A，B，C，D），依次进栈，进栈允许出栈，出栈的元素被加入队列。

那么，从队列输出的元素序列可以是（D，C，B，A）。

【答案】是。

（）3．循环队列是一种链式队列。

【答案】否。

（）4．一棵二叉树中，必须有一个根结点，其余结点分属于左右两棵子二叉树。

【答案】否。

（）5．散列表在元素的存储位置和它的关键字之间建立了一个确定的函数关系，所以，无论是否表中存在同义词，在查找记录时，只需计算地址，而无需作关键字之间的比较。

【答案】否。

（）6．在胜方树上输出一个结点后，从根到该结点的路径上所有结点都必须更新。

【答案】是。

二、选择题（每题3分，共30分）1．现实生活中具有谱系结构的数据，在计算机处理时一般采用（）结构表示。

A．线性B．树C．图D．集合【答案】 B2．设后缀表达式：“4 3 * 2 9 3 / + 2 - /”，式中每个操作数均为一位整数，则表达式的值为（）。

A．6 B．4 C．8 D．A, B, C三者都不是【答案】 B3．设二叉树根结点的层次为1。

在所有含135个结点的二叉树中，最小高度是（）。

A．6 B．7 C．8 D．9【答案】 C4．设A、X和Y是二叉树B中的三个结点，X是A的左孩子，Y是A的左孩子。

T是与B对应得树；在T中，A是Y的（）。

A．孩子B．兄弟C．双亲D．祖先（非双亲）【答案】 D5．下面哪一种结构必定是完全二叉树（）。

A．哈夫曼树B．二叉搜索树C．A VL树D．堆【答案】 D6．在有序表（10, 20, 30, 40, 50, 60, 70, 80, 90）中以对半搜索算法查找元素30和45时，所需的关键字之间的比较次数分别为（）。

A．3, 3 B．3, 4 C．4, 4 D．A, B, C三者都不是【答案】 B7．假定从无向图G的任何一个顶点出发进行一次深度优先搜索，都可以访问图中的每个顶点，则该图一定是（）。

南昌大学2007～2008学年第二学期期末考试试卷6、在程序中执行到________语句时,将结束所在函数的执行过程,返回到调用该函数的位置。

7、以下程序main(）{int aa[4]［4］=｛{1,2，3，4｝,｛5，6,7,8},{3,9,10，2}，{4，2，9，6}｝;int i，s=0;for(i=0；i<4；i++) s+=aa［i][1］；printf（%d\n，s)；}程序运行后的输出结果是________________。

8、以下fun函数把ch中的大写字母转换成字母序列中的下一个大写字母，字母Z转换成字母A，其它字符不变,返回转换后的字母或其它字符.请填空。

char fun（char ch)｛if（ch= =’Z') ch=__________；else if（ch〉=’A’＆&ch<=’Y’) ch=__________；return ch;}9、下面程序的功能是：输出100以内能被3整除且个位数为6的所有整数。

#include 〈stdio。

h〉void main(void）{int i, j;for(i=0； i<10； i++) ｛j = i＊10+6；if （_____ _____ ） continue；printf(”％d "，j）;｝｝10、以下程序的功能是调用函数fun计算：m=1-2+3-4+…+9—10，并输出结果。

请填空。

int fun（int n)｛int m=0,f=1,i；for（i=1；i〈=n；i++)｛m+=i＊f；f= __________ ；｝return m；｝main（）{printf（”m=%d\n”，________ __）；｝11、下面程序段是输出两个字符串中对应字符相等的字符。

请选择填空。

char x[]="programming"；char y[]=”Fortran"；int i=0；while （_______________ __ __）｛if （x［i]==y[i］） printf （"%c",x［i］)；else i++;}｝12、以下程序从终端读入数据到数组中，统计其中正数的个数,并计算它们之和。

《数据结构》考研真题及解答目录2009 年试题 (1)填空题 (1)解答题 (2)2010 年试题 (2)填空题 (2)解答题 (4)2011 年试题 (4)填空题 (4)解答题 (5)2012 年试题 (6)填空题 (6)解答题 (7)2013 年试题 (8)填空题 (8)解答题 (9)2014 年试题 (10)填空题 (10)解答题 (11)2015 年试题 (12)填空题 (12)解答题 (14)2009 年试题填空题1.为解决计算机与打印机之间速度不匹配的问题，通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则依次从该缓冲区中取出数据。

该缓冲区的逻辑结构应该是A.栈B.队列C.树D.图2.设栈 S 和队列 Q 的初始状态均为空，元素 abcdefg 依次进入栈 S。

若每个元素出栈后立即进入队列 Q，且7 个元素出队的顺序是 bdcfeag，则栈 S 的容量至少是A．1 B.2 C.3 D.43.给定二叉树图所示。

设 N 代表二叉树的根，L代表根结点的左子树，R代表根结点的右子树。

若遍历后的结点序列为 3，1，7，5，6，2，4，则其遍历方式是A．LRN B.NRL C.RLN D.RNL4.下列二叉排序树中，满足平衡二叉树定义的是5.已知一棵完全二叉树的第 6 层（设根为第 1 层）有8 个叶结点，则完全二叉树的结点个数最多是A．39 B.52 C.111 D.1196.将森林转换为对应的二叉树，若在二叉树中，结点u 是结点v 的父结点的父结点，则在原来的森林中，u 和v 可能具有的关系是I．父子关系II.兄弟关系III.u 的父结点与v 的父结点是兄弟关系A.只有IIB.I 和IIC.I 和IIID.I、II 和III7.下列关于无向连通图特性的叙述中，正确的是I．所有顶点的度之和为偶数II.边数大于顶点个数减1 III.至少有一个顶点的度为1A.只有IB.只有IIC.I 和IID.I 和III8.下列叙述中，不符合 m 阶B 树定义要求的是A．根节点最多有m 棵子树 B.所有叶结点都在同一层上C．各结点内关键字均升序或降序排列 D.叶结点之间通过指针链接9.已知关键序列 5，8，12，19，28，20，15，22 是小根堆（最小堆），插入关键字 3，调整后得到的小根堆是A．3，5，12，8，28，20，15，22，19B.3，5，12，19，20，15，22，8，28C．3，8，12，5，20，15，22，28，19D.3，12，5，8，28，20，15，22，1910.若数据元素序列 11，12，13，7，8，9，23，4，5 是采用下列排序方法之一得到的第二趟排序后的结果，则该排序算法只能是A．起泡排序 B.插入排序 C.选择排序 D.二路归并排序解答题41.（10 分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。

2022年北京工业大学计算机科学与技术专业《数据结构与算法》科目期末试卷A（有答案）一、选择题1、用有向无环图描述表达式(A+B)*((A+B)／/A)，至少需要顶点的数目为（）。

A.5B.6C.8D.92、设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储， a11为第一元素，其存储地址为1，每个元素占一个地址空间，则a85的地址为（）。

A.13B.33C.18D.403、连续存储设计时，存储单元的地址（）。

A.一定连续B.一定不连续C.不一定连续D.部分连续，部分不连续4、在下列表述中，正确的是（）A.含有一个或多个空格字符的串称为空格串B.对n（n>0）个顶点的网，求出权最小的n-1条边便可构成其最小生成树C.选择排序算法是不稳定的D.平衡二叉树的左右子树的结点数之差的绝对值不超过l5、已知串S='aaab'，其next数组值为（）。

A.0123B.1123C.1231D.12116、循环队列放在一维数组A中，end1指向队头元素，end2指向队尾元素的后一个位置。

假设队列两端均可进行入队和出队操作，队列中最多能容纳M－1个元素。

初始时为空，下列判断队空和队满的条件中，正确的是（）。

A．队空：end1＝＝end2；队满：end1＝＝（end2＋1）mod MB．队空：end1＝＝end2；队满：end2＝＝（end1＋1）mod （M－1）C．队空：end2＝＝（end1＋1）mod M；队满：end1＝＝（end2＋1） mod MD．队空：end1＝＝（end2＋1）mod M；队满：end2＝＝（end1＋1） mod （M－1）7、已知字符串S为“abaabaabacacaabaabcc”，模式串t为“abaabc”，采用KMP算法进行匹配，第一次出现“失配”（s!＝t）时，i＝j＝5，则下次开始匹配时，i和j的值分别（）。

A．i＝1，j＝0 B．i＝5，j＝0 C．i＝5，j＝2 D．i＝6，j＝28、已知一棵二叉树的前序遍历结果为ABCDEF，中序遍历结果为CBAEDF，则后序遍历结果为（）。

2008年真题一、简答题<4’×5）1、写出影响算法执行的时间效率的主要因素，并指出哪些因素与算法的时间效率直接相关。

2、已知元素的入栈顺序为A,B,C,D,E，在所有可能的出栈顺序中，写出第一个出栈的元素为C 且第二个出栈的元素为D 的所有组合。

3、根据单词<Nov, Jul, Sept, Feb, Oct, Mar, May, Jun, Jan, Dec, Aug, Apr）的第一个字母在字母表中的顺序建立二叉排序树，当每个元素的查找概率相等时，求查找成功时的平均查找长度ASL。

4、证明：具有n 1> 2 条边。

-个顶点的无向图最多有n (n5、有人说，折半查找的时间效率一定比顺序查找的时间效率高，你怎么看待这种说法？为什么？二、算法设计题<10’）1] 中，请写出中序遍历该二叉树的非递归算法。

-已知一非空完全二叉树存放于数组BT[0..n三、算法设计题<10’）写出不带头结点的双向链表的插入排序算法。

四、简答题<4’×5）1、数据传输控制方式有哪些？2、引入线程的目的是什么？3、P, V 操作是如何实现互斥的的？4、什么是死锁？产生死锁的原因是什么？5、什么是文件系统？五、判断题<1’×10）略。

<基本上来自于历年真题）六、解答题<10’）某机器字长为16 位，采用段页式存储管理算法，页内偏移为12 位，段表和页表内容如下，给出4 个虚拟地址<二进制形式），问哪个地址产生缺段中断，哪个地址产生缺页中断，哪些地址可以转换为物理地址，并求转换后的物理地址。

<地址格式中段号占1 位，段内页号占3 位，页内偏移为12 位，另外，在给出的页表中，物理块号占6 位，最后又问该机器的最大物理内存是多少<答案：256 KB）。

）七、简答题<4’×4）1、利用等值演算的方法，写出求命题逻辑公式的主范式的方法。