2013河北省数据结构基础考资料

1、目前我国使用较广泛的浏览器是____。

A、ICQB、OICQC、IED、FTP2、因特网是属于____所有。

A、中国政府B、微软公司C、各接入单位共同D、美国政府3、直接运行在裸机上的最基本的系统软件，负责对各类资源进行统一控制、管理、调度和监督。

它是____。

A、操作系统B、语言处理程序C、数据库管理系统D、工具软件4、局域网组网完成后，决定网络使用性能的关键是____。

A、网络的拓扑结构B、网络的通信协议C、网络的传输介质D、网络的操作系统5、网络中计算机之间的通信是通过____实现的，它们是通信双方必须遵守的约定。

A、网卡B、通信协议C、磁盘D、电话交换设备6、若一台计算机的字长为4个字节，这意味着它____。

A、能处理的数值最大为4位十进制数9999B、能处理的字符串最多位4个英文字母组成C、在CPU中作为一个整体加以传送处理的代码为32位D、在CPU中运行的结果最大位2的32次方7、在Windows/中，鼠标的单击是指____A、移动鼠标使鼠标指针出现在屏幕上的某个位置B、按住鼠标左键，移动鼠标把鼠标指针移到某个位置后释放左键C、按下并快速地释放鼠标左键D、快速连续地两次按下并释放鼠标左键8、在Word中，对某个段落的全部文字进行下列设置，属于段落格式设置的是____。

A、设置为四号字B、设置为楷体字C、设置为1.5倍行距D、设置为4磅字间距9、通常所说的FTP协议是指____。

A、简单邮件传输协议B、提供远程登陆功能C、文件传输协议D、保证数据的传输10、65536 Kbytes 相当于____。

A、64MBB、64GBC、65.536MBD、65.536GB11、在Word 的编辑状态，设置了标尺，可以同时显示水平标尺和垂直标尺的视图方式是____。

A、普通方式B、页面方式C、大纲方式D、全屏显示方式12、电子邮件地址为student@，其中是____。

A、学校代号B、学生别名C、邮件服务器名称D、邮件账号13、1字节表示____位。

《软件基础与技术综合》考试大纲一、考试内容数据结构70分 + 数据库40分 + 软件工程40分（一）数据结构部分1. 数据结构基本概念(1) 数据结构的基本概念：数据、数据元素、数据结构、数据的逻辑结构、物理结构、算法等。

(2) 算法时间复杂度和空间复杂度的分析方法。

2. 线性表(1) 线性表的定义。

(2) 线性表的顺序存储结构和主要算法实现，如查找、插入和删除算法。

(3) 线性表的链式存储结构和主要算法实现，如查找、插入和删除算法。

(4) 循环链表、双向链表的特点。

(5) 从时间和空间复杂度的角度比较两种存储结构的不同特点及其适用场合。

(6) 线性表的应用，如线性表的合并算法。

3. 栈和队列(1) 栈的定义及特点，栈的顺序存储和链接存储结构，进栈出栈算法，顺序栈栈满和栈空的条件。

(2) 栈的应用，如表达式求值算法，借助栈深入理解递归算法。

(3) 队列的定义及特点，队列的顺序存储(循环队)和链接存储结构，进队出队算法，循环队列中队满及队空的条件。

4. 串和数组(1) 串的定义。

(2) 串的古典模式匹配算法。

(3) 数组地址的计算方法。

(4) 特殊矩阵的压缩存储方法。

5. 树和二叉树(1) 二叉树的定义和性质。

(2) 二叉树的两种存储结构：顺序存储和链式存储。

(3) 二叉树的创建和三种不同遍历算法，利用遍历算法实现二叉树的其他操作，如计算二叉树结点个数、叶子结点个数、二叉树的高度等算法。

(4) 线索二叉树的特性及构造方法。

(5) 树和森林的定义、存储结构与二叉树的转换方法。

(6) 树的应用，哈夫曼树及哈夫曼编码的构造算法、带权路径长度的计算。

6. 图(1) 图的定义和性质。

(2) 图的两种存储结构：邻接矩阵和邻接表。

(3) 图的两种遍历策略：深度优先搜索算法和广度优先搜索算法。

(4) 图的基本应用，包括拓扑排序算法、求解最短路径的迪杰斯特拉算法、构造最小生成树的两种算法（普里姆算法和克鲁斯卡尔算法）。

（ B ）。

A）front=front->next; B） rear=rear->next;C） rear=front->next; D） front=rear->next ;2、下面程序段的时间复杂度是( A )。

s =0;for( i =0; i<n; i++)for(j=0;j<n;j++)s +=B[i][j];sum = s ;A） O(n2) B） O(n)C） O(m*n) D）O(1)3、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( B )。

A）9 B）11 C）15 D）不能确定4、串的逻辑结构与（ D ）的逻辑结构不同。

A）线性表 B）栈C）队列 D）树5、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。

这样的排序方法是（ A ）。

A）直接选择排序 B）直接插入排序C）快速排序 D）起泡排序6、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( B )。

A）9 B）11 C）15 D）不能确定7、设有一个栈，元素的进栈次序为A, B, C, D, E,下列是不可能的出栈序列是（ C ）。

A） A, B, C, D, EB） B, C, D, E, AC） E, A, B, C, DD） E, D, C, B, A8、下面程序段的时间复杂度是( A )。

s =0;for( i =0; i<n; i++)for(j=0;j<n;j++)s +=B[i][j];sum = s ;A） O(n2) B） O(n)C） O(m*n) D）O(1)（ B ）。

A) rear=rear->next; B) front=front->next;C) rear=front->next; D) front=rear->next ;10、采用链结构存储线性表时，其地址（ B ）。

9.数据结构试卷(一) 一、单选题(每题 2 分，共 20 分) 1. 栈和队列的共同特点是 ( A. 只允许在端点处插入和删除元素 B .都是先进后出C. 都是先进先出D. 没有共同点 用链接方式存储的队列，在进行插入运算时 仅修改头指针 仅修改尾指针)。

2. A. C.3.4.5.6. A7. ( ). 头、尾指针都要修改 头、尾指针可能都要修改 ( ) B. 栈 C. 线性表D. 二叉树B. D. 以下数据结构中哪一个是非线性结构？ A. 队列设有一个二维数组 676(10)，每个元素占一个空间， 表示。

A ．688B ． 678 树最适合用来表示 ( )。

A. 有序数据元素 C.元素之间具有分支层次关系的数据 二叉树的第 k 层的结点数最多为 ( ). ．2k -1B.2K+1C.2K-1 若有 18 个元素的有序表存放在一维数组A[m][ n]，假设 A[0][0]存放位置在 644(io), A[2][2]存放位置在问 A[3][3] (10)存放在什么位置？脚注 (10)表示用 10进制C ． 692D ．696B.无序数据元素 D .元素之间无联系的数据 D. 2 k-1A[19] 中，第一个元素放 A[1] 中，现进行二 分查找，则查找 A : 3]的比较序列的下标依次为 ( 3 B. 9 ， 3 D. 9 ， 5， 4， 对 n 个记录的文件进行快速排序，所需要的辅助存储空间大致为 A. 1，2， C. 9，5， )2，3 2，38. A. O (1) B. O ( n ) C. O (1og 2n ) D. O (n2) 9. 对于线性表( 7， 34， 55， 25， 64， 46， 20， 10)进行散列存储时，若选用 H (K ) =K %9 作为散列函数，则散列地址为 1 的元素有(A ． 1B ．2C ．3 10. 设有 6 个结点的无向图，该图至少应有 (A.5B.6C.7D.8 二、填空题(每空 1 分，共 26 分) 1. 2.3. )个， D ． 4 )条边才能确保是一个连通图。

绝密★考试结束前全国2013年10月高等教育自学考试数据结构试题课程代码：02331请考生按规定用笔将所有试题的答案涂、写在答题纸上。

选择题部分注意事项：1. 答题前，考生务必将自己的考试课程名称、姓名、准考证号用黑色字迹的签字笔或钢笔填写在答题纸规定的位置上。

2. 每小题选出答案后，用2B铅笔把答题纸上对应题目的答案标号涂黑。

如需改动，用橡皮擦干净后，再选涂其他答案标号。

不能答在试题卷上。

一、单项选择题(本大题共15小题，每小题2分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其选出并将“答题纸”的相应代码涂黑。

错涂、多涂或未涂均无分。

1．算法的时间复杂度表征的是A．算法的可读性B．算法的难易程度C．执行算法所耗费的时间D．执行算法所耗费的存储空间2．对需要频繁插入和删除结点的线性表，适合的存储方式是A．顺序储存B．链式存储C．索引存储D．散列存储3．在头指针为head的循环链表中，判断指针变量P指向尾结点的条件是A．p->next->next==head B．p->next==headC．p->next->next==NULL D．p->next==NULL4．迪杰斯特拉(Dijkstra)算法的功能是A．求图中某顶点到其他顶点的最短路径B．求图中所有顶点之间的最短路径C．求图的最小生成树D．求图的拓扑排序序列5．若栈的进栈序列为1，2，3，4，5，则经过出入栈操作不可能．．．获得的出栈序列是A．4，5，3，2，1 B．4，3，5，1，2C．1，2，3，4，5 D．5，4，3，2，16．A是7×4的二维数组，按行优先方式顺序存储，元素A[0][0]的存储地址为1 000，若每个元素占2个字节，则元素A[3][3]的存储地址为A．1015 B．1016C．1028 D．10307．深度为4的完全二叉树的结点数至少为A．4 B．8C．13 D．158．若采用邻接矩阵A存储有向图G，则结点k的入度等于A中A．结点k对应行元素之和B．结点k对应列元素之和C．结点k对应行和列元素之和D．非零元素之和9．无向图G的邻接矩阵一定是A．对称矩阵B．对角矩阵C．三角矩阵D．单位矩阵10．下列关于有向带权图G的叙述中，错误．．的是A．图G的任何一棵生成树都不含有回路B．图G生成树所含的边数等于顶点数减1C．图G含有回路时无法得到拓扑序列D．图G的最小生成树总是唯一的11．在下列排序算法中，关键字比较次数与初始排列次序无关的是A．冒泡排序B．希尔排序C．直接插入排序D．直接选择排序1 2．对下图进行拓扑排序，可以得到的拓扑序列是A．a b c d e B．b a c d eC．b c a d e D．a b d c e13．下列线性表中，能使用二分查找的是A．顺序存储(2,12,5,6,9,3,89,34,25) B．链式存储(2,12,5,6,9,3,89,34,25) C．顺序存储(2,3,5,6,9,12,25,34,89) D．链式存储(2,3,5,6,9,12,25,34,89) 14．在下列查找方法中，平均查找长度与结点数量无直接关系的是A．顺序查找B．分块查找C．散列查找D．基于B树的查找15．下列排序算法中，时间复杂度为O(nlog2 n)的算法是A．快速排序B．冒泡排序C．直接选择排序D．直接插入排序非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。

1、向一个栈顶指针为hs的链栈中插入一个s结点时，应执行（ D ）。

A) hs->next=s; B) s->next=hs->next; hs->next=s;C) s->next=hs; hs=s; D) s->next=hs; hs=hs->next;2、栈进行插入和删除操作的特点是（ A ）。

A）LIFO B）FIFOC）FCFS D）HPF3、线性表的链接实现有利于（ A ）运算。

A）插入 B）读元素C）查找 D）定位4、在一个单链表中，已知q结点是p结点的前趋结点，若在q和p之间插入s结点，则须执行（ A ）。

A）q->next=s; s->next=p; B）s->next=p->next; p->next=s;C）p->next=s->next; s->next=p D）p->next=s; s->next=q;5、下列序列中，执行第一趟快速排序后得到的序列是（ A ）。

A）[d,a,e,d,b]f[h,g] B) [c,e,a,d]f[h,g,b]C) [g,a,e,c,b]f[d,h] D) [a,b,c,d,]f[e,g,h]6、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( B )。

A）9 B）11 C）15 D）不能确定7、设给定问题的规模为变量n，解决该问题的算法所需时间为Tn=O(f(n)),Tn表示式中记号O表示（ A ）。

A）一个数量级别 B）一个平均值C）一个最大值 D）一个均方值8、倘若在对串的插入、删除运算中，期望运算速度最快，则应采用（ C ）。

A）顺序表示法 B）单字符为结点的单链表表示法C）等量分块表示法 D）不等量分块表示法9、设给定问题的规模为变量n，解决该问题的算法所需时间为Tn=O(f(n)),Tn表示式中记号O表示（ A ）。

1、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。

29. ①试找出满足下列条件的二叉树1）先序序列与后序序列相同 2）中序序列与后序序列相同3）先序序列与中序序列相同 4）中序序列与层次遍历序列相同2、假设以邻接矩阵作为图的存储结构，编写算法判别在给定的有向图中是否存在一个简单有向回路，若存在，则以顶点序列的方式输出该回路（找到一条即可）。

（注：图中不存在顶点到自己的弧）有向图判断回路要比无向图复杂。

利用深度优先遍历，将顶点分成三类：未访问；已访问但其邻接点未访问完;已访问且其邻接点已访问完。

下面用0，1，2表示这三种状态。

前面已提到，若dfs（v）结束前出现顶点u到v的回边，则图中必有包含顶点v和u的回路。

对应程序中v的状态为1，而u是正访问的顶点，若我们找出u的下一邻接点的状态为1，就可以输出回路了。

void Print(int v,int start ) //输出从顶点start开始的回路。

{for(i=1;i<=n;i++)if(g[v][i]!=0 && visited[i]==1 ) //若存在边（v,i），且顶点i的状态为1。

{printf(“%d”,v);if(i==start) printf(“\n”); else Print(i,start);break;}//if}//Printvoid dfs(int v){visited[v]=1;for(j=1;j<=n;j++ )if (g[v][j]!=0) //存在边(v,j)if (visited[j]!=1) {if (!visited[j]) dfs(j); }//ifelse {cycle=1; Print(j,j);}visited[v]=2;}//dfsvoid find_cycle() //判断是否有回路，有则输出邻接矩阵。

visited数组为全局变量。

{for (i=1;i<=n;i++) visited[i]=0;for (i=1;i<=n;i++ ) if (!visited[i]) dfs(i);}//find_cycle3、证明由二叉树的中序序列和后序序列，也可以唯一确定一棵二叉树。

1、后序遍历最后访问根结点，即在递归算法中，根是压在栈底的。

采用后序非递归算法，栈中存放二叉树结点的指针，当访问到某结点时，栈中所有元素均为该结点的祖先。

本题要找p和q 的最近共同祖先结点r ,不失一般性，设p在q的左边。

后序遍历必然先遍历到结点p，栈中元素均为p的祖先。

将栈拷入另一辅助栈中。

再继续遍历到结点q时，将栈中元素从栈顶开始逐个到辅助栈中去匹配，第一个匹配（即相等）的元素就是结点p 和q的最近公共祖先。

typedef struct{BiTree t;int tag;//tag=0 表示结点的左子女已被访问，tag=1表示结点的右子女已被访问}stack;stack s[],s1[];//栈，容量够大BiTree Ancestor(BiTree ROOT,p,q,r)//求二叉树上结点p和q的最近的共同祖先结点r。

{top=0; bt=ROOT;while(bt!=null ||top>0){while(bt!=null && bt!=p && bt!=q) //结点入栈{s[++top].t=bt; s[top].tag=0; bt=bt->lchild;} //沿左分枝向下if(bt==p) //不失一般性，假定p在q的左侧,遇结点p时，栈中元素均为p的祖先结点{for(i=1;i<=top;i++) s1[i]=s[i]; top1=top; }//将栈s的元素转入辅助栈s1 保存if(bt==q) //找到q 结点。

for(i=top;i>0;i--)//；将栈中元素的树结点到s1去匹配{pp=s[i].t;for (j=top1;j>0;j--)if(s1[j].t==pp) {printf(“p 和q的最近共同的祖先已找到”)；return (pp);}｝while(top!=0 && s[top].tag==1) top--; //退栈if (top!=0)｛s[top].tag=1;bt=s[top].t->rchild;｝ //沿右分枝向下遍历}//结束while(bt!=null ||top>0)return(null);//ｑ、p无公共祖先｝//结束Ancestor2、二叉树的层次遍历序列的第一个结点是二叉树的根。

考研数据结构常考知识点一、知识概述《线性表》①基本定义：线性表就是数据像一条线似的排开的结构。

就好比班级里同学们站成一排，每个同学就是一个数据元素，前后顺序是明确的。

②重要程度：在数据结构中非常重要，是好多其他复杂结构的基础。

很多东西都是基于线性表来构建、理解的。

③前置知识：需要对变量、基本数据类型这些有了解。

像你得知道整数、字符这些基本的东西，就像盖楼之前得知道砖头是啥样的。

④应用价值：在存储数据顺序的时候非常有用。

比如图书馆按编号存书，每一本书就像线性表的一个元素。

《栈和队列》①基本定义：栈就像一个桶，东西只能从一头进出，先进后出。

而队列呢，像排队买东西，从一头进，另一头出，先进先出。

②重要程度：也是数据结构里常见的保存数据的方式，在程序运行中存储一些临时数据很有用。

③前置知识：线性表的知识，因为栈和队列可以看作是特殊的线性表。

④应用价值：在操作系统里任务调度可以用到队列，栈在表达式求值的时候可以用，像计算器计算式子的时候在后台可能就是用栈的方式去处理父子运算顺序的。

二、知识体系①知识图谱：线性表在数据结构里是基础中的基础，栈和队列是线性表的衍生。

②关联知识：树和图的一些遍历算法可能会用到栈或者队列辅助实现，比如树的深度优先遍历用栈方便，广度优先遍历用队列合适。

③重难点分析：线性表理解不难，但是运用起来要熟练有点难。

栈和队列重点是搞清楚它们进出数据的规则，难点是在不同问题里选择合适的结构。

④考点分析：线性表会考操作、存储结构之类的，栈和队列会考查入栈出栈、入队出队的操作顺序，还会结合一些应用题考查。

三、详细讲解【线性表- 理论概念类】①概念辨析：线性表就是n个数据元素的有限序列。

这里面每个元素都是单个数据，而且有顺序。

②特征分析：顺序性，每个元素都有固定的顺序位置。

还有有限性，元素个数是有限的。

③分类说明：可以分为顺序表，就是元素存在连续的存储单元里；还有链表，元素分布在不同的存储单元，通过指针联系起来。