下载文档原格式
2015年硕士研究生入学考试大纲考试科目名称：数据结构考试时间：180分钟，满分：150分一、考试要求：1．理解数据结构、算法、抽象数据类型(ADT)的基本概念。
2．掌握线性表、树、图等基本数据结构的ADT定义以及在顺序存储和链式存储下相关算法的实现，并能对算法的时间复杂度进行分析。
3．掌握“查找”和“排序”中主要算法的基本思想和特点。
4．能够运用学习的数据结构知识和技能进行问题的分析与求解，具备采用C或C++或JAVA语言设计与实现算法（编程）的能力。
二、考试内容：1．一般线性表（1）基于顺序存储的定义和实现（方式、特点）（2）基于链式存储的定义和实现（方式、特点）（3）线性表的应用2．特殊线性表（栈、队列、字符串、数组）（1）栈、队列、字符串、数组的基本概念、特点（2）栈和队列基于顺序存储的定义与实现（方式、特点）（3）栈和队列基于链式存储的定义与实现（方式、特点）（4）字符串基于顺序存储的定义与实现（能够求模式的失败函数）（5）数组的逻辑定义和顺序存储（6）特殊数组的存储（存储方式、占用空间情况、数组操作的实现、在一维存储空间中下标的计算）（7）稀疏矩阵的压缩存储及转置算法实现4．树与二叉树（1）二叉树①二叉树的定义、主要特征及相关特征的证明②二叉树基于顺序存储和链式存储的实现（方式、特点）③二叉树重要操作的实现（建立、遍历、计算叶子结点、结点、深度等算法实现）④线索二叉树的基本概念和构造（为什么加线索？如何记录线索？如何使用线索？）（2）树、森林①树的存储结构（重点掌握子女-兄弟表示）②森林与二叉树的相互转换③树和森林的遍历（3）特殊二叉树及应用①哈夫曼（Huffman）树和哈夫曼编码的构造过程②二叉排序树（重点掌握结点的插入和删除的思想和过程）③平衡二叉树（平衡的目的？如何达到平衡？）④堆（堆的构造和调整过程）5．图（1）图的基本概念（2）图的存储及基本操作①邻接矩阵存储（无向图、有向图、无向带权图、有向带权图）②邻接表存储（无向图、有向图、无向带权图、有向带权图）③各种存储方式下操作的算法实现（图的建立、遍历、插入边、删除边等）（3）图的遍历①深度优先遍历（思想、过程及算法实现）②广度优先遍历（思想、过程及算法实现）（4）图的基本应用（掌握算法的思想、过程）①最小生成树问题②最短路径问题③有向图与工程（AOV网与拓扑排序，AOE网与关键路径）6．查找（1）查找的基本概念（2）顺序查找法（监视哨法的思想和算法）（3）折半查找法（思想和算法）（4）B树及其基本操作、B+树的基本概念（思想和过程）（5）散列（Hash）表（Hash函数和解决冲突的方法的思想和过程）（6）查找算法的时间复杂度、平均查找长度的分析7．排序（1）排序的基本概念（2）基于“插入”思想的排序方法①直接插入排序②折半插入排序（思想和过程）③希尔排序（思想和过程）（3）基于“交换”思想的排序方法①冒泡排序（思想、过程和算法）②快速排序（思想、过程和算法）（4）基于“选择”思想的排序方法①简单选择排序（思想、过程和算法）②堆排序（思想和过程）（5）基于“归并”思想的排序方法二路归并排序（思想、过程）（6）各种常用内部排序算法的特点及应用三、考试形式和试卷结构1.考试时间：180分钟，满分：150分2.题型结构a:选择题(50分)b:应用题(50分)c:算法分析与设计(50分)3.答题方式：闭卷、笔试四、参考书目1. 数据结构（用面向对象方法与C++语言描述）（第2版）.殷人昆主编. 北京：清华大学出版社.2007.62. 数据结构（C语言版）.严蔚敏、吴伟民编著. 北京：清华大学出版社. 2007。
《数据结构》实验报告学号2015011512 姓名胡明禹专业数学与应用数学时间2018.4.3一、实验题目实验3 顺序栈基本操作二、实验目的1.熟练掌握顺序栈的实现和基本操作2.理解栈后进先出的特点3.熟练应用顺序栈解决实际问题三、算法设计分析（一）数据结构的定义数据结构是计算机存储、组织数据的方式。
数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。
（二）总体设计此处给出主要函数功能、及函数间调用关系的的描述。
例如：①初始化并建立一个新栈表函数②栈清空函数③栈判断是否为空函数④进栈函数⑤出栈函数⑥取栈顶元素函数⑦输出栈元素函数⑧计算栈中元素个数函数⑨销毁栈函数（1）主函数：统筹调用各个函数以实现相应功能void main()（2）①初始化并建立一个新栈表SqStack *InitStack(SqStack *s){int i;s=(SqStack*)malloc(sizeof(SqStack));s->top=-1;printf("输入顺序栈元素（以0结束）：\n");scanf("%d",&i);do{s->top++;//栈顶指针增加一s->data[s->top]=i; //将新插入元素赋值给栈顶空间scanf("%d",&i);while(i!=0);printf("成功\n");return s;}②栈清空函数void SetNULL(SqStack *s){//清空栈s->top=-1;//当栈存在一个元素时，top等于0,因此通常把空栈的条件定位top等于-1 }③栈判断是否为空函数int EMPTY(SqStack *s){//判断栈空if(s->top>=0)return 0;else return 1;}④进栈函数SqStack *Push(SqStack *s){//进栈int a;printf("插入数字：");scanf("%d",&a);if(s->top==maxsize-1)//判断是否栈满{printf("overflow");//溢出return NULL;}else{s->top++;//栈顶指针增加1s->data[s->top]=a;//将新插入元素赋值给栈顶空间}return s;}⑤出栈函数SqStack *Pop(SqStack *s){//出栈if(s->top==-1)//当栈存在一个元素时，top等于0,因此通常把空栈的条件定位top等于-1 {printf("underlow");return s;}else{s->top--;//栈顶指针减一printf("删除的栈顶元素：");printf("%d\n",(s->data[s->top+1]));//若栈不为空，则删除s的栈顶元素}return s;}⑥取栈顶元素函数void GetTop(SqStack *s){//取栈顶if(s->top==-1){printf("SqStack is empty");//当栈存在一个元素时，top等于0,因此通常把空栈的条件定位top 等于-1}else{printf("当前栈顶元素是：");printf("%d\n",(s->data[s->top]));//取栈顶元素地址}}⑦输出栈元素函数void print(SqStack *s){//输出栈int i=0;if(s->top==-1){printf("成功！");}while(i<=s->top){//遍历栈中所有元素printf("%d ",s->data[i]);i++;}}⑧计算栈中元素个数函数void Count(SqStack *s){//计算栈中元素int i=0;while(i<=s->top){i++;}printf("个数为%d",i);}⑨销毁栈函数int DestroyStack_Sq(SqStack *s){ //销毁一个顺序栈Sfree(s);s=NULL;return 1;}四、实验测试结果及结果分析（一）测试结果（此处给出程序运行截图）（二）结果分析成功完成了题目所要求的插入，删除，查找等基本操作。
数据结构试题一、单选题1、在数据结构的讨论中把数据结构从逻辑上分为（）A 内部结构与外部结构B 静态结构与动态结构C 线性结构与非线性结构D 紧凑结构与非紧凑结构。
2、采用线性链表表示一个向量时，要求占用的存储空间地址（）A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（）。
A nB n/2C (n-1)/2D (n+1)/24、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（）。
A s→link = p→link;p→link = s;B p→link = s; s→link = q;C p→link = s→link;s→link = p;D q→link = s;s→link = p;5、如果想在4092个数据中只需要选择其中最小的5个，采用（）方法最好。
A 起泡排序B 堆排序C 锦标赛排序D 快速排序6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（）。
A 求子串B 模式匹配C 串替换D 串连接7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。
所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（）。
A 80B 100C 240D 2708、将一个递归算法改为对应的非递归算法时，通常需要使用（）。
A 栈B 队列C 循环队列D 优先队列9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（）。
10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。
A ( front - rear + 1) % mB ( rear - front + 1) % mC ( front - rear + m) % mD ( rear - front + m) % m11、一个数组元素a[i]与（）的表示等价。
数据结构试题一、单选题1、在数据结构的讨论中把数据结构从逻辑上分为（）A 内部结构与外部结构B 静态结构与动态结构C 线性结构与非线性结构D 紧凑结构与非紧凑结构。
2、采用线性链表表示一个向量时，要求占用的存储空间地址（）A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（）。
A nB n/2 C(n-1)/2 D (n+1)/24、在一个单链表中，若q结点是p结点的前驱结点，若在q与p之间插入结点s，则执行（）。
A s→link= p→link;p→link= s;B p→link = s; s→link = q;C p→link= s→link;s→link= p;D q→link = s;s→link = p;5、如果想在4092个数据中只需要选择其中最小的5个，采用（）方法最好。
A 起泡排序B 堆排序C 锦标赛排序D 快速排序6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（）。
A 求子串B 模式匹配 C串替换 D 串连接7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。
所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（）。
A 80B 100C 240D 2708、将一个递归算法改为对应的非递归算法时，通常需要使用（）。
A 栈B 队列C 循环队列D 优先队列9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（）。
10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。
A ( front - rear + 1) % mB ( rear - front + 1) % mC ( front - rear + m) % mD ( rear - front + m) % m11、一个数组元素a[i]与（）的表示等价。
《数据结构》综合复习资料一、填空题1、数据结构是（）。
2、数据结构的四种基本形式为集合、（）、（）和（）。
3、线性结构的基本特征是:若至少含有一个结点，则除起始结点没有直接前驱外，其他结点有且仅有一个直接（）；除终端结点没有直接（）外，其它结点有且仅有一个直接（）。
4、堆栈的特点是（），队列的特点是（），字符串中的数据元素为（）。
5、字符串s1=“I am a student！”(单词与单词之间一个空格),s2=“student”,则字符串s1的长度为（），串s2是串s1的一个（）串，串s2在s1中的位置为（）。
6、KMP算法的特点：效率较（）；（）回溯，对主串仅需要从头到尾扫描（）遍，可以边读入边匹配。
7、广义表（（a），（（b），c），（（（d））））的长度为（），表头为（），表尾为（）。
8、ADT称为抽象数据类型，它是指（）。
9、求下列程序的时间复杂度，并用大O表示方法表示（）。
for( i=1 ; i<=n ; + + i)for( j=1 ; j<=i; + + j ){ ++x;a[i][j] = x;}10、以下运算实现在链栈上的退栈操作，请在_____处用适当句子予以填充。
int Pop(LstackTp *ls,DataType *x){ LstackTp *p;if(ls!=NULL){ p=ls;*x= ;ls= ;;return(1)；}else return(0);}11、用堆栈求中缀表达式a+b*c/d+e*f的后缀表达式，求出的后缀表达式为（）。
12、C语言中存储数组是采用以（）为主序存储的，在C语言中定义二维数组float a[8][10],每个数据元素占4个字节，则数组共占用（）字节的内存。
若第一个数据元素的存储地址为8000，则a[5][8]的存储地址为（）。
13、含零个字符的串称为（）串，用 表示。
其他串称为（）串。
任何串中所含字符的个数称为该串的（）。
一、单项选择题答题要求:每题只有一个正确的选项。
1分) 2.0以下字符型常量表达不正确的是（）A)'ABC''B)[ABC]C)’ABC’D)(ABC)参考答案：D2分) 2.0在数据库中存储的是（）A)数据B)数据模型C)数据以及数据之间的联系D)信息参考答案：C3分) 2.0在Visual FoxPro环境下，用LIST STRU命令显示表中每个记录的长度总计为60，用户实际可用字段的总宽度为（）A)60B)61C)59D)58参考答案：C4分) 2.0同一个数组中的所有数组元素的数据类型（）A)必须相同B)必须不同C)可相同也可不同D)不可改变参考答案：C5分) 2.0在数据管理技术的发展过程中，经历了人工管理阶段、文件系统阶段和数据库系统阶段。
在这几个阶段中，数据独立性最高的是（）阶段。
A)数据库系统B)文件系统C)人工管理D)数据项管理参考答案：A6分) 2.0假设一个表包含职工号（C，4）和工资（N，4）两个字段。
要求按工资升序、工资相同者按职工号升序排列，建立索引文件使用的命令是（）A)INDEX ON 工资/A，职工号/D TO CNB)SET INDEX ON 工资，职工号TO CNC)INDEX ON STR(工资，4)+职工号TO CND)INDEX ON 工资/A 职工号/A TO CN参考答案：C7分) 2.0设A=”123”，则2*&A的值为（）A)'' 2*&A''B)''2&123''C)246D)''2*123''参考答案：C8分) 2.0要判断数值型变量Y是否能够被2整除，错误的条件表达式为（）A)MOD(Y，2)=0B)INT(Y/2)=Y/2C)Y%2=0D)INT(Y/2)=MOD(Y，2)参考答案：D9分) 2.0函数运算YEAR(date( ))返回值的类型是（）A)逻辑型B)字符型C)备注型D)数值型参考答案：D10分) 2.0由计算机、操作系统、数据库管理系统、数据库、应用程序及用户组成的一个整体叫（）A)软件系统B)数据库系统C)管理系统D)文件系统参考答案：B11分) 2.0一个表的全部备注字段的内容存储在（）A)同一表备注文件B)不同表备注文件C)同一文本文件D)同一数据库文件参考答案：A12分) 2.0COPY TO命令的功能是（）A)复制表结构和表中数据B)只复制表结构C)只复制表中数据D)以上都不对参考答案：A13分) 2.0按照传统的数据模型分类，数据库可分为三种类型（）A)大型、中形和小型B)西文、中文和兼容C)层次、网状和关系D)数据、图形和多媒体参考答案：C14分) 2.0Visual FoxPro表文件有100条记录，当前记录号是11，执行命令LIST后，记录指针将指向（）A)第1条记录B)第100条记录C)第101条记录D)文件结束标识位置参考答案：D15分) 0将打开的表中全部记录删除的命令为ZAP，与之等价的命令是（）A)DELETE ALLB)DELETE ALL PACKC)DELETE PACKD)RECALL ALL参考答案：B16分) 2.0若要在表中真正删除记录，先用DELETE命令，再用（）A)RECALLB)PACKC)按ESC键D)不用其他命令参考答案：B17分) 2.0在Visual FoxPro中，用INDEX命令建立索引文件时，<关键字表达式>应该是（）A)只能由一个数值型字段组成B)可以由多个字段组成，但表达式的值必须是数值型、字符型、日期型、逻辑型C)只能是由数值型和字符型字段组成的合法表达式D)任意字段组成的合法表达式参考答案：B18分) 2.0函数SUBSTR（“”，3，2）的结果是（）A)23B)34C)12D)6参考答案：B19分) 2.0在SQL中，从数据库中删除表可以用（）A)DROP SCHEMA命令B)DROP TABLE命令C)DROP VIEW命令D)DROP INDEX命令参考答案：B20分) 2.0职工表及姓名索引文件都打开后，用FIND命令把指针指向姓“王”的记录，使指针指向下一个同姓记录的命令是（）A)GOTO NEXTB)CONTINUEC)SKIPD)FIND 王参考答案：C二、判断题答题要求:判断下列说法是否正确。
中国石油大学（北京）2009 ——2010学年第一学期《数据结构》期末考试试卷A （闭卷考试）班级：姓名：学号：分数：一、选择题（本大题共15小题，每题2分，共30分）1、算法分析的目的是（）。
A．找出数据结构的合理性B．研究算法中的输入和输出的关系C．分析算法的效率以求改进D．分析算法的易懂性和文档性2、以下数据结构中，哪一个是线性结构（）。
A．广义表B．二叉树C．稀疏矩阵D．串3、4个圆盘的Hanoi塔，总的移动次数为（）A．B．8 C．15 D．164、依次读入数据元素序列{a，b，c，d，e，f，g}进栈,每进栈一个元素，可要求下一个元素进栈或出栈，如此进行，下列哪种出栈为不可能序列（）A．(d ，e，c，f，b，g，a) B．(d ，e，c，f，b，g，a)C．(e ，f，d，g，b，c，a) D．(c ，d，b，e，f，a，g)5、在双向循环链表结点p之后．插入s的操作是（）。
A．p－>next=s ;s－>priou=p; p－>next－>priou=s ; s－>next=p－>next;B．p－>next－>priou=s; p－>next=s; s－>priou=p; s－>next=p－>next;C．s－>priou=p; s－>next=p－>next; p－>next=s; p－>next－>priou=s ;D．s－>priou=p; s－>next=p－>next; p－>next－>priou=s ; p－>next=s;6、对于循环队列（）。
A．无法判断队列是否为空 B. 无法判断队列是否为满C. 队列不可能满D.以上说法都不是7、若6行5列的数组以列序为主序顺序存储，基地址为1000，每个元素占2个存储单元，则第3行第4列的元素（假定无第0行第0列）的地址是（）A．1040 B．1042 C．1026 D．都不对8、广义表A=(a,b,(c,d),(e,(f,g)))，则操作Head(Tail(Head(Tail(Tail(A)))))的结果为（）A．(g) B．(d) C．c D．d9、下述编码中哪一个不是前缀码( )。
2015年数据结构期末考试题及答案,推荐文档(word版可编辑修改) 编辑整理：尊敬的读者朋友们：这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（2015年数据结构期末考试题及答案,推荐文档(word版可编辑修改)）的内容能够给您的工作和学习带来便利。
同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。
本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快业绩进步，以下为2015年数据结构期末考试题及答案,推荐文档(word版可编辑修改)的全部内容。
2012年数据结构期末考试题及答案一、选择题1．在数据结构中，从逻辑上可以把数据结构分为 C 。
A．动态结构和静态结构 B．紧凑结构和非紧凑结构C．线性结构和非线性结构 D．内部结构和外部结构2．数据结构在计算机内存中的表示是指 A 。
A．数据的存储结构B．数据结构C．数据的逻辑结构 D．数据元素之间的关系3．在数据结构中，与所使用的计算机无关的是数据的 A 结构。
A．逻辑B．存储C．逻辑和存储D．物理4．在存储数据时，通常不仅要存储各数据元素的值，而且还要存储 C .A．数据的处理方法B．数据元素的类型C．数据元素之间的关系D．数据的存储方法5．在决定选取何种存储结构时，一般不考虑 A 。
A．各结点的值如何B．结点个数的多少C．对数据有哪些运算D．所用的编程语言实现这种结构是否方便.6．以下说法正确的是 D 。
A．数据项是数据的基本单位B．数据元素是数据的最小单位C．数据结构是带结构的数据项的集合D．一些表面上很不相同的数据可以有相同的逻辑结构7．算法分析的目的是 C ，算法分析的两个主要方面是 A .（1）A．找出数据结构的合理性 B．研究算法中的输入和输出的关系C．分析算法的效率以求改进 C．分析算法的易读性和文档性（2）A．空间复杂度和时间复杂度 B．正确性和简明性C．可读性和文档性 D．数据复杂性和程序复杂性8．下面程序段的时间复杂度是O(n2) 。
目 录2000年中国石油大学（北京）数据结构考研真题2001年中国石油大学（北京）数据结构考研真题2002年中国石油大学（北京）数据结构考研真题2003年中国石油大学（北京）数据结构考研真题2004年中国石油大学（北京）数据结构考研真题2000年中国石油大学（北京）数据结构考研真题石油大学（北京）二000年研究生入学试题糙明数据结构共2页适用专业：计算机应用-、求解下^问题(7X6分〉1、判别以下序列是否为堆(小顶堆或大顶堆).如果不是,则把它调整为堆(要求记录交换次数最少).⑴<100,86,48,73,35,39,42,57,/66,21)<2)《05,56.20,23.40.38,29,61,35,76.28,100)(3)(103,97,56,38,66,23,42,12,30,52,06,的)2、宿线性浪进行二分法粉索的先决编中是什么？简述二分法检索的基本汶程及草平均检索长度，3、按照四则运算加、减、m,除和慕运算（t）优先关系的惯例，即出对下列算术衰达式求值时操作数栈和运算待栈的变化过程：A-BXC/D+E tF4、己知下列各始为广义表的存赭结构图，其结点的结构为,Uj数据结构的主要区别是什么，（2）分配算法的主要区别是什么？⑶回收算法的主要区别是什么？6、画出与下列己知序列时应的森林F：森林的先序次序访问序列为：ABCDEFGHIJKL森林的中序次序访问序列为：CBEFDGAJIKLH7、画出上面有向图的十字链袤.I''>■**，-*二、写算法（2X12分）1、从循环双向链表中新除第i<i^l）个结点，试写出其算法.2、已知一棵以链表存储的二叉材，如欲姚结点起，由上而下，逐孱打印各结瘁的数据，同一是结点宜左而右打印，试写出其算法.（要求所用变量必须注解）】*l,t土|>”.1三，分析与推导L一棵深度为H的满k义村有如下性质：第H层上•钓结点都是叶于结点,其余各层上每个嬉点都有! k棵非空亍树.如果按层次倾序从1开殖对全部结点编号，网（12分）（D各层的结点数目是多少？•⑵编号为p的结点的父结点（若存在〉的编号是多少？⑶编号为P的绪点的第i个儿子结点（若存在）的编号是多少？⑴漏号为p的结点宥兄弟的条件是什么？其兄弟的编号是什么？2、.画出下图所示的无向图的邻接多重表，使得其中母个无向边绡点宇曾一个顶点号小于第二个顶点号，旦每个顶点的各邻接边的链接顾序为它所邻接的顶点序号或'到大莉前序.列出深度优先和广度优先搜索遍历该图所得顶*律列和边序列.（12分）3、什么姑平衡二又树|?平衡二叉树有什么优点，用在什么堕方？试推导含12个结点的平衡二叉树%"的最大深陌,芥皿出一棵这样的平衡二又树.no分｝2001年中国石油大学（北京）数据结构考研真题石油大学（北京）2001年研究生入学试题考试科目：数据结构共2页适用专业：计算机应用求解下列间题'（8X6分）1.画出广义表（a.（（）,b）,（（（e））））的存储结构图.2.若二棵树中有度为1至m的结点数分别为m,任，…，n.（&衷示及数为m的结点个数）*谄推导也该树中有多少个叶结点n“的公式.3.请给出下而稀疏炬阵的漆——列表示法（即十字镂表法）存储结构.勺200。
数据结构题库及答案Excel1. 单链表的插入操作- 问题：请描述在单链表中插入一个新节点的步骤。
- 答案：首先确定插入位置，然后创建一个新节点。
将新节点的next指针指向原链表中该位置的节点。
接着，更新前一个节点的next指针指向新节点。
最后，如果插入位置是链表头部，则更新头指针。
2. 二叉树的遍历方法- 问题：请列举二叉树的三种基本遍历方法。
- 答案：前序遍历（根-左-右）、中序遍历（左-根-右）、后序遍历（左-右-根）。
3. 哈希表的冲突解决方法- 问题：在哈希表中，如何解决冲突？- 答案：常见的冲突解决方法有开放地址法（线性探测、二次探测、双重哈希）和链地址法。
4. 堆排序的基本原理- 问题：堆排序的基本原理是什么？- 答案：堆排序基于二叉堆数据结构，通过构建最大堆或最小堆，然后逐步将堆顶元素与堆尾元素交换，缩小堆的范围，最后得到有序序列。
5. 图的深度优先搜索（DFS）- 问题：请简述图的深度优先搜索（DFS）的基本思想。
- 答案：DFS从图的某个顶点开始，沿着邻接表的边尽可能深地搜索，直到无法继续为止，然后回溯到上一个顶点，继续搜索其他邻接顶点。
6. 快速排序算法的时间复杂度- 问题：快速排序算法的平均时间复杂度是多少？- 答案：快速排序算法的平均时间复杂度为O(n log n)。
7. 栈的后进先出（LIFO）特性- 问题：栈的后进先出特性是如何体现的？- 答案：栈的LIFO特性体现在元素的添加和删除操作都发生在栈顶，即最后添加的元素最先被删除。
8. 队列的先进先出（FIFO）特性- 问题：队列的先进先出特性是如何体现的？- 答案：队列的FIFO特性体现在元素的添加操作在队尾进行，而删除操作在队首进行，即最先添加的元素最先被删除。
9. 最小生成树的构造方法- 问题：请列举两种最小生成树的构造方法。
- 答案：普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法。
10. 动态规划的适用场景- 问题：动态规划适用于解决哪些类型的问题？- 答案：动态规划适用于具有重叠子问题和最优子结构特性的问题，如斐波那契数列、背包问题、最长公共子序列等。
中国石油大学（北京）远程教育学院期末考试《数据结构》课程设计1.课程设计题目从下面四个题目中任选一题完成。
1.1 通讯录的制作用单链表作为数据结构，结合C或者C++语言基本知识，编写一个班级的通讯录管理系统。
系统包括下面几方面的功能：第1：输入信息：输入某同学的信息；第2：显示信息：显示全部通讯录中学生的信息；第3：查找功能：实现按姓名进行查找，并给出查找信息；第4：删除功能：实现按姓名进行删除，并给出操作结果；第5：每名同学的信息包括：姓名、性别、电话、城市；第6：界面友好，每步给出适当的操作提示；第7：系统具有一定的容错能力。
1.2 图书管理系统设计一个计算机管理系统完成图书管理几本业务。
系统要满足下面基本要求：第1：每种图书的登记内容包括：书名、书号、作者、出版社、现存量和库存量；第2：采编入库：新购图书，确定书号后，登记到图书账目表中，如果表中存在该书，则只将库存量增加；第3：借阅：如果该书的库存量大于0，则借出一本，登记借阅者的书证号和归还期限，改变库存量；第4：归还：注销对借阅者的登记，改变该书的库存量；第5：界面友好，每步给出适当的操作提示；第6：系统具有一定的容错能力。
1.3 产品进销管理系统针对某个行业的库房产品进销存情况进行管理，系统要求具有下列功能：第1：采用一定的存储结构对库房的货品及其数量进行分类管理；第2：可以进行产品类的添加、产品的添加、产品数量的添加；第3：能够查询库房每种产品的总量、进货日期、销出数量、销售时间等；第4：每种产品至少包含信息：产品名、进货日期、进货数量、销出数量、销售时间、库存量；第5：界面友好，每步给出适当的操作提示；第6：系统具有一定的容错能力。
1.4 校园导航问题设计中国石油大学（北京）的校园平面图，至少包括10个场所，可以实现任意两个场所的最短路径。
2.课程设计报告书写规范课程设计报告包括该题目的需求分析、概要设计、详细设计、程序测试、感想与体会几部分内容。
一、单项选择题（每题1分，共40分）1.第2代计算机采用的电子元件是（C）。
A、集成电路B、电子管C、晶体管D、大规模集成电路2.一个完整的计算机系统包括（C ）。
A、主机B、系统软件和应用软件C、硬件系统和软件系统D、主机和外部设备3.Byte的意思是（ A ）A、字节B、字C、二进制位D、字长4.表示10种状态的二进制数至少需要（ C ）位二进制编码。
A、2B、3C、4D、55.操作系统是（ C ）的接口。
A、主机和外设B、系统软件和应用软件C、用户与计算机D、高级语言和机器语言6.某学校的排课软件属于（ C ）。
A、系统软件B、工具软件C、应用软件D、字处理软件7.下列存储器中，计算机断电后存储的信息会丢失的是（ A ）A、RAMB、ROMC、硬盘D、U盘8.下列文件名中，不正确的文件名是（ B ）。
A、ab.datB、zuo>ye.docC、hello world.cD、new.txt9.Word中的“格式刷”的作用是（ C ）A、选定刷过的文本B、填充颜色C、快速进行格式复制D、删除刷过的文本10.用Excel2003生成的文件默认的扩展名是（ B ）A、 .xslB、.xlsC、.sxlD、.lxs11.在EXCEL中，当某个单元格中输入的数值型数据时，出现一串“#”，说明（B ）A、输入不正确的数字B、单元格宽度不够C、输入错误的公式D、输入了非数字的字符12.管理Internet的协议是（ A ）A、TCP/IPB、ISO/OSIC、IPX/SPXD、HTTP/FTP13.网络上的web服务基于（ C ）协议A、HTMLB、FTPC、HTTPD、TCP14.下列关于电子邮件系统的叙述错误的是（ B ）。
A、通过E—Mail进行联系的双方不必在同一时间内收发信件B、当电子邮件到达时，你的电脑没开机，则邮件退回给发件人C、发送电子邮件使用SMTP协议D、可以把电子邮件同时发送给多人15.局域网中的计算机为了相互通信，必须安装（B ）。
中国石油大学（北京）现代远程教育学院
《数据结构》网考期末复习题
题库资料参考答案
答案在后面
一、选择题（本大题共15小题，每小题2分，共30分）
1.以下与数据的存储结构无关的术语是（）
A、循环队列
B、链表
C、哈希表
D、栈
2.一个向量第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是
（）
A、110
B、108
C、100
D、120
3.假设带头结点的单向循环链表的头指针为head,则该链表为空的判定条件是（）
A、head= =NULL
B、head–>next= =NULL
C、head–>next= =head
D、head!=NULL
4.若进栈序列为1，2，3，4，5，6，且进栈和出栈可以穿插进行，则不可能出现的出栈
序列是（）
A、2，4，3，1，5，6
B、3，2，4，1，6，5
C、4，3，2，1，5，6
D、2，3，5，1，6，4
5.下列关键字序列中，构成小根堆的是（）
A、{12，21，49，33，81，56，69，41}
B、{81，69，56，49，41，33，21，12}
C、{81，49，69，41，21，56，12，33}
D、{12，21，49，33，81，41，56，69}
6.下列数据结构中，不属于二叉树的是（）
A、B树
B、A VL树
C、二叉排序树
D、哈夫曼树
7.用顺序存储的方法来存储一棵二叉树，存放在一维数组A[1..N]中，若结点A[i]有右孩
子，则其右孩子是（）。
1。
一、单选：1、为便于判别有向图中是否存在回路,可借助于A.广度优先搜索算B.最小生成树算法C.最短路径算D.拓扑排序算法2、数据结构在逻辑上可以分为3、下述编码中（）不是前缀码。
4、下列陈述正确的是：对于哈希函数H（key）=key%17,被称为同义词的关键字。
5、若查找每个元素的概率相等，则在长度为n的顺序表上查找任一元素，查找成功的情况6有一个链队列中，front和rear分别为头指针和尾指针，则将一个p指针所指的结点插入队列应执行算法分析的目的是计算机中的算法指的是解决某一个问题的有限运算序列，它必须具备输入，输出在一个n个元素的有序单链表中查找具有给定关键字的结点，平均情况下的时间复杂性为二、填空：1、在对一组记录（13 25 3 9 38 17 46 29 6 31 ）进行希尔（shell）排序时，取d=3，则一趟希尔排序后记录：2、已知有向图的邻接表如下图所示：则该图中从结点1出发的广度优先遍历序列是（），深度优先遍历序列是（）3、在具有m个单元的循环队列中，队头指针为front，队尾指针为fear，则队满的条件是。
4、设有向无环图G中的有向边集合E=｛ab ac db de｝，请写出该有向图G的一种拓扑排序序列。
5、已知二叉树的前序遍历序列为ABDCEF，中序遍历序列为DBAEFC，则它的后序遍历序列为6、若用一个大小为8的数组来实现循环队列，且当rear和front的值分别为0.5.当从中删除一个元素，再加入两个元素后7、在一个长度为n的顺序表中,删除第i(1≤i≤n)个元素时，需要向前移动（）个元素8、一个采用了顺序存储结构的线性表，其长度为20，若在第5个元素前插入一个元素，需要移动（）个元素，若接着又将元素删除，那么需要移动（）个元素。
9、在对一组记录（53 41 96 22 16 75 61 46 88）进入堆排序时，根据初始记录构成初始堆（大栈堆）后，这10、假定一个有向图的顶点集为｛a b c d e f ｝边集为｛ac ae cf dc ed｝则出度为0的顶点个数为（），入度为1的顶点个数为（）三、简答题：已知一表为（43 21 67 9 40 78 2 41 70 90 ）按表中顺序依次插入初始为空的二叉排序树，要求（1）用括号法表示建立的二叉排序树（用#表示空树）（2）求出在等概率情况下查找成功的平均查找长度2、若一个无向连通图以邻接表作为存储结构，请设计一个函数，功能是删除图中的一条边（I j）,已知类型edgnd包含，类型AdjList表示顶点数组类型，每个数组元素包含first （指针成员）3、已知图G的邻接表如下图所示：请写出从顶点0出发，该图的深度优先遍历序列和广度优先遍历序列4、已知有n个顶点的有向图邻接表，编写一个函数求出该图中指定顶点的出度。
数据结构试题一、单选题1、在数据结构的讨论中把数据结构从逻辑上分为（）A 内部结构和外部结构B 静态结构和动态结构C 线性结构和非线性结构D 紧凑结构和非紧凑结构。
2、采用线性链表表示一个向量时，要求占用的存储空间地址（）A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 可连续可不连续3、采用顺序搜索方法查找长度为n的顺序表时，搜索成功的平均搜索长度为（）。
A nB n/2 C(n-1)/2 D (n+1)/24、在一个单链表中，若q结点是p结点的前驱结点，若在q和p之间插入结点s，则执行（）。
A s→link= p→link;p→link= s;B p→link = s; s→link = q;C p→link= s→link;s→link= p;D q→link = s;s→link = p;5、如果想在4092个数据中只需要选择其中最小的5个，采用（）方法最好。
A 起泡排序B 堆排序C 锦标赛排序D 快速排序6、设有两个串t和p，求p在t中首次出现的位置的运算叫做（）。
A 求子串B 模式匹配 C串替换 D 串连接7、在数组A中，每一个数组元素A[i][j]占用3个存储字，行下标i从1到8，列下标j从1到10。
所有数组元素相继存放于一个连续的存储空间中，则存放该数组至少需要的存储字数是（）。
A 80B 100C 240D 2708、将一个递归算法改为对应的非递归算法时，通常需要使用（）。
A 栈B 队列C 循环队列D 优先队列9、一个队列的进队列顺序是1, 2, 3, 4，则出队列顺序为（）。
10、在循环队列中用数组A[0..m-1] 存放队列元素，其队头和队尾指针分别为front和rear，则当前队列中的元素个数是（）。
A ( front - rear + 1) % mB ( rear - front + 1) % mC ( front - rear + m) % mD ( rear - front + m) % m11、一个数组元素a[i]和（）的表示等价。
A *（a+i）B a+iC *a+iD &a+i12、若需要利用形参直接访问实参，则应把形参变量说明为（）参数。
A 指针B 引用C 值D 变量13、下面程序段的时间复杂度为（） for (int i=0;i<m;i++)for (int j=0;j<n;j++)a[i][j]=i*j;A O(m2)B O(n2)C O(m*n)D O(m+n)14、下面程序段的时间复杂度为（）int f(unsigned int n) {if(n= =0 || n= =1) return 1;else return n*f(n-1);}A O(1)B O(n)C O(n2)D O(n!)15、线性表若是采用链式存储结构时，要求内存中可用存储单元的地址( )。
A 必须是连续的B 部分地址必须是连续的C 一定是不连续的D 连续或不连续都可以16、数据结构的定义为(D，S)，其中D是( )的集合。
A 算法 B数据元素 C 数据操作 D 逻辑结构17、算法分析的目的是( )。
A找出数据结构的合理性B研究算法中输入和输出的关系C分析算法的效率以求改进D分析算法的易懂性和文档性18、在一个单链表中，若p所指结点不是最后结点，在p之后插入s所指结点，则执行( )。
A s->link=p;p->link=s;B s->link=p->link;p->link=s;C s->link=p->link;p=s;D p->link=s;s->link=p;19、设单链表中结点结构为(data,link).已知指针q所指结点是指针p所指结点的直接前驱，若在*q和*p之间插入结点*s，则应执行下列哪一个操作（）A s->link=p->link; p->link=s;B q->link=s; s->link=pC p->link=s->link; s->link=p;D p->link=s; s->link=q;20、设单链表中结点结构为(data,link).若想摘除结点*p的直接后继，则应执行下列哪一个操作（）A p->link=p->link->link;B p=p->link; p->link=p->link->link;C p->link=p->link;D p=p->link->link;21、设单循环链表中结点的结构为（data,link）,且rear是指向非空的带表头结点的单循环链表的尾结点的指针。
若想删除链表第一个结点，则应执行下列哪一个操作（ D ）A s=rear; rear=rear->link; delete s;B rear=rear->link; delete rear;C rear=rear->link->link; delete rear;D s=rear->link->link;rear->link->link=s->link; delete s;s 为第一个结点硫22、设单循环链表中结点的结构为（data,link）,且first为指向链表表头的指针，current为链表当前指针，在循环链表中检测current是否达到链表表尾的语句是( D )。
A current->link =nullB first->link=currentC first=currentD current->link=first23、一个栈的入栈序列为a，b，c，则出栈序列不可能的是( C )。
A c,b,aB b,a,cC c,a,bD a,c,b24、栈的数组表示中，top为栈顶指针，栈空的条件是( A )。
A top=0B top=maxSizeC top=maxSizeD top=-125、栈和队列的共同特点是( C )。
A 都是先进后出B 都是先进先出C只允许在端点处插入和删除 D 没有共同点26、假定一个顺序存储的循环队列的队头和队尾指针分别为f和r ,则判断队空的条件为( D ).A f+1= =rB r+1= =f Cf= =0 D f= =r27、当利用大小为n 的数组顺序存储一个队列时，该队列的最大长度为（ B ）A n-2B n-1C nD n+128、当利用大小为n 的数组顺序存储一个栈时，假定用top= =n 表示栈空，则向这个栈插入一个元素时，首先应执行（）语句修改top指针。
A top++;B top--;C top=0;D top;29、设链式栈中结点的结构为（data, link）,且top是指向栈顶的指针。
若想摘除链式栈的栈顶结点，并将被摘除结点的值保存到x 中，则应执行下列（ A ）操作。
A x=top->data; top=top->link;B top=top->link; x=top->data;C x=top; top=top->link;D x=top->data;30、设循环队列的结构是：const int Maxsize=100;typedef int Data Type;typedef struct {Data Type data[Maxsize];Int front, rear;} Queue;若有一个Queue类型的队列Q，试问判断队列满的条件应是下列哪一个语句（ D ）A Q.front= = Q.rear;B Q.front - Q.rear= = Maxsize;C Q.front + Q.rear= = Maxsize;D Q.front= = (Q.rear+1)% Maxsize;31、设有一个递归算法如下：int fact (int n ){ if (n<=0) return 1;else return n*fact(n-1);}下面正确的叙述是（ B ）A 计算fact(n) 需要执行n次递归B fact(7)=5040C 此递归算法最多只能计算到fact(8)D 以上结论都不对32、设有一个递归算法如下int x (int n) {if (n<=3) return 1;else return x(n-2)+x(n-4)+1;}试问计算 x(x(8))时需要计算（ D ）次x函数。
A 8 次B 9 次 C16 次 D 18次33、设有广义表D(a,b,D),其长度为（ B ），深度为（ A ）A ∞B 3C 2D 534、广义表A(a),则表尾为（ C ）A aB (( ) )C 空表D （a）35、下列广义表是线性表的有（ C ）A E（a,(b,c)）B E(a,E) CE (a,b) D E(a,L( ) )36、递归表、再入表、纯表、线性表之间的关系为（ C ）A 再入表>递归表>纯表>线性表 B递归表>线性表>再入表>纯表C 递归表>再入表>纯表>线性表 D递归表>再入表>线性表>纯表37、某二叉树的前序和后序序列正好相反，则该二叉树一定是（ B ）的二叉树。
A 空或只有一个结点B 高度等于其结点数C 任一结点无左孩子D 任一结点无右孩子38、对于任何一棵二叉树T，如果其终端结点数为n0，度为2的结点为n2.,则( A )A n0= n2+1B n2= n0+1C n0= 2n2+1D n2=2n0+139、由权值分别为11，8，6，2，5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（B ）A 24B 73 C48 D 5340、已知一个顺序存储的线性表，设每个结点需占m个存储单元，若第一个结点的地址为da1,则第I 个结点的地址为（ A ）。
A da1+(I-1)*mB da1+I*mC da1-I*mD da1+(I+1)*m41、34 具有35个结点的完全二叉树的深度为( A )A 5B 6C 7D 842、对线性表进行折半搜索时，要求线性表必须（ C ）A 以链接方式存储且结点按关键码有序排列B 以数组方式存储C 以数组方式存储且结点按关键码有序排列 D以链接方式存储43、顺序搜索算法适合于存储结构为（ B ）的线性表。
A 散列存储B 顺序存储或链接存储C 压缩存储D 索引存储44、采用折半搜索算法搜索长度为n的有序表时，元素的平均搜索长度为（ C ）A O（n2）B O（n log2n）C O（log2n）D O（n）45、对于一个具有n个顶点和e条边的无向图，进行拓扑排序时，总的时间为( A )A nB n+1C n-1D n+e46、判断一个有向图是否存在回路，除了可以利用拓扑排序方法外，还可以利用（C ）。
