下载文档原格式
绝密★考试结束前全国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．直接插入排序非选择题部分注意事项：用黑色字迹的签字笔或钢笔将答案写在答题纸上，不能答在试题卷上。
2013数据结构大题408
一、选择题
在一个二叉搜索树中，左子树的所有节点值：
A. 大于其父节点值
B. 小于其父节点值
C. 等于其父节点值
D. 与其父节点值无关
栈的基本操作不包括：
A. 入栈
B. 出栈
C. 取栈顶元素
D. 查找指定元素
链表中节点间的逻辑关系是通过：
A. 指针链接
B. 索引链接
C. 顺序存储
D. 关键字链接
在图的表示中，邻接矩阵适用于表示：
A. 稀疏图
B. 稠密图
C. 无向图
D. 有向图
在一个具有n个顶点的无向图中，若边数为n-1，则该图一定是：
A. 连通图
B. 非连通图
C. 树
D. 环
二、填空题
在线性表的顺序存储结构中，元素之间的逻辑关系是通过__________表示的。
二叉树的第i层最多有__________个节点（i ≥ 1）。
深度为k的二叉树最多有__________个节点。
在图的遍历中，深度优先搜索（DFS）通常使用__________作为辅助数据结构。
对于一个具有n个顶点和e条边的无向图，其邻接表表示需要的存储空间为__________。
三、简答题
简述什么是数据结构？并列举数据结构的两种基本类型。
描述冒泡排序算法的基本思想，并给出其时间复杂度分析。
什么是二叉树？简述二叉树的主要性质。
解释图的最小生成树算法——Prim算法的基本思想。
阐述快速排序算法的基本步骤，并分析其平均时间复杂度和最坏时间复杂度。
数据结构考试重点及部分答案自己做的答案不是很正确如果有问题请联系后面的大题不知道原题，所以不知道怎么做见谅！！！题型和分值选择题：15*2=30填空题：10*2=20解答题：5*4=20算法阅读题：5*4=20算法设计题：101 栈的进栈、出栈函数顺序，求一个表达式的顺序eg：进栈顺序是123 计算POP(S)+2 POP(S) =3+2*2=72 给定二叉排序树的数据求平均查找长度Eg：已知长度为9的表{16 ，3 ，7 ，11 ，9 ，26，18，14，15}，建立二叉顺序树后进行查找，则等概率的情况下查找成功的平均查找长度为（）二叉排序树（Binary Sort Tree）又称二叉查找树。
它或者是一棵空树；或者是具有下列性质的二叉树：（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值；（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值；（3）左、右子树也分别为二叉排序树；根据上述性质，按照给出的表，建立的树如下图：（旁边的数表示查找长度）平均查找长度为：（1+2+2+3+3+4+5+5+6）/9 = 31/93树的概念树是n(n>=0)个结点的有限集4 二重循环的平均时间复杂度的求解（使用嵌套、统计次数）时间复杂度：该算法的运行时间与问题规模的对应关系，时间复杂度用T（n）=O（f（n））来表示Eg：S=0for(i=1;i<=n;i++)for(j=1;j<=m;j++)s=s+1答案为0（n*m)求解算法复杂度时：1、首先确定核心操作。
很显然此算法中，核心的操作是s=s+1;2.这个算法中，存在两重循环。
第一重循环n次，第二重循环m次，总共执行核心操作n*m次。
3.确定此算法的时间复杂度为：O (n*m)若复杂度为 O (n*n)，则算法可以是如下的样子：S=0for(i=1;i<=n;i++)for(j=1;j<=n;j++)s=s+15 单链表中R是P的前驱，在P Q之间插入S，则则如何插入（语句表示）在相邻元素R、P之间插入一个值为X的数据元素的基本操作步骤：（1）生成一个数据域值为X的结点S（2）使X结点的指针域指向结点P：S->next=P->next（3）修改R结点的指针域指向结点X：P->next=S6 已知顺序表，求查找X的平均查找长度(n+1)/27栈的插入和删除的位置栈顶8 已知入队序列求出队序列原则：先进先出9 在图中，所有度数和等于边的几倍两倍10 邻接矩阵中行和列分别表示什么意思无向图邻接矩阵的第i行（或第i列）非零元素的个数正好是第i个顶点的度。
数据结构真题2013年10月(总分：100.01，做题时间：90分钟)一、{{B}}单项选择题{{/B}}(总题数：15，分数：30.00)1.算法的时间复杂度表征的是______∙ A.算法的可读性∙ B.算法的难易程度∙ C.执行算法所耗费的时间∙ D.执行算法所耗费的存储空间（分数：2.00）A.B.C. √D.解析：[考点] 算法的时间复杂度定义 [解析] (1)执行算法所耗费的时间，即时间复杂性；(2)执行算法所耗费的存储空间，主要是辅助空间，即空间复杂性；(3)算法应易于理解、易于编程、易于调试等，即可读性和可操作性。
因此表征算法时间复杂度的是执行算法耗费的时间，C正确。
2.对需要频繁插入和删除结点的线性表，适合的存储方式是______∙ A.顺序存储∙ B.链式存储∙ C.索引存储∙ D.散列存储（分数：2.00）A.B. √C.D.解析：[考点] 链式存储方式 [解析] 应该采用链式存储结构。
因为采用链式结构存储线性表，插入和删除操作需要从头结点起查找被插入或删除结点的前驱结点，并修改这些结点的指针域，查找过程平均移动指针域为表长的一半；而采用顺序结构存储线性表，插入和删除操作需要平均移动表中的一半元素。
但移动指针域操作比移动元素操作花费的时间少得多。
3.在头指针为head的循环链表中，判断指针变量P指向尾结点的条件是______∙ A.p-＞next-＞next==head∙ B.p-＞next==head∙ C.p-＞next-＞next==NULL∙ D.p-＞next==NULL（分数：2.00）A.B. √C.D.解析：[考点] 循环链表的特点 [解析] 循环链表的特点是单链表中最后一个结点(终端结点)的指针域不为空，而是指向链表的头结点，使整个链表构成一个环；循环结束的判断条件不再是P或P→next是否为空，而是他们是否等于头指针。
因此答案选B。
4.迪杰斯特拉(Dijkstra)算法的功能是______∙ A.求图中某顶点到其他顶点的最短路径∙ B.求图中所有顶点之间的最短路径∙ C.求图的最小生成树∙ D.求图的拓扑排序序列（分数：2.00）A. √B.C.D.解析：[考点] 迪杰斯特拉(Dijkstra)算法的功能[解析] Dijkstra(迪杰斯特拉)算法是典型的最短路径路由算法，用于计算从某个源点到其余各定点的最短路径。
《数据结构》考研真题及解答目录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 分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。
1、线索二叉树中某结点D，没有左孩子的条件是（ B ）。
A）D->Lchild=Null B) D->ltag=1C) D->Rchild=Null D) D->ltag=02、采用链结构存储线性表时，其地址（ B ）。
A）必须是连续的 B）连续不连续都可以C）部分地址必须是连续 D）必须是不连续的3、在数据结构中，从逻辑上可以把数据结构分为（ C ）。
A）动态结构和静态结构 B）紧凑结构和非紧凑结构C）线性结构和非线性结构 D）内部结构和外部结构4、在一个具有n个单元的顺序栈中，假定以地址低端（即0单元）作为栈底，以top作为栈顶指针，当做出栈处理时，top变化为（ C ）。
A）top不变 B）top=0 C）top-- D）top++5、用一维数组A进行顺序存储时，若起始地址为loc(A1)，元素长度为c，则A的第i个数组单元在存放地址loc(Ai)，等于（ B ）。
A）loc(A1)+i*c B）loc(A1)+(i-1)*cC）loc(A1)+i*c+1 D）loc(A1)+(i+1)*c6、若一棵二叉树具有10个度为2的结点，5个度为1的结点，则度为0的结点的个数是( B )。
A）9 B）11 C）15 D）不能确定7、与无向图相关的术语有（ C ）。
A）强连通图 B）入度C）路径 D）弧8、下列各种数据结构中属于线性结构的有（ A ）。
A）栈 B) 二叉树C) 广义表 D) 图9、用一维数组A进行顺序存储时，若起始地址为loc(A1)，元素长度为c，则A的第i个数组单元在存放地址loc(Ai)，等于（ B ）。
A）loc(A1)+i*c B）loc(A1)+(i-1)*cC）loc(A1)+i*c+1 D）loc(A1)+(i+1)*c10、设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针的操作为（ A ）。
A）p->next=p->next->next B）p=p->nextC）p=p->nexe->next D）p->next=p11、下面关于线性表的叙述中，错误的是哪一个？（ D ）A）线性表采用顺序存储，必须占用一片连续的存储单元。
目 录2013年山东师范大学855数据结构A历年考研真题2012年山东师范大学856数据结构A历年考研真题2011年山东师范大学856数据结构A历年考研真题2010年山东师范大学数据结构A历年考研真题2009年山东师范大学数据结构A历年考研真题2008年山东师范大学数据结构A历年考研真题2007年山东师范大学数据结构A历年考研真题2006年山东师范大学数据结构A历年考研真题2005年山东师范大学数据结构A历年考研真题2013年山东师范大学855数据结构人历年考研真题考试科E 注意事窿L 二填空顺席写在即L数却2.没不金具有6.砒＜818.在平A的9.Xf-■把第二、写算法题1.改计2,设ir3,缶.点4.气山东师范大学硕士研究生入学考试试题1名称：数据结构A试题编号；衣试卷尤5道大题《共H18个小题）,满分1知分；本卷风试收卷.答题另肯答飓卷,忤案一律与枇容四卷上,写任该试题卷I-.或单纸卜.均无没妾注意试卷沽洁，不要住试卷卜滁灿四须用瞌、您钢筮或网球堡拎题，*它均无泡.挞由龙许使用悴通计算嚣定•10分”本大尚共9小题，10个空.群空4分，将成埴在卜剧践地的件案，fe 题纸h）靖梅中评价算弁的两个收要指标是⑴和12U-个10X10的耐称矩阵A[10][10J.采取上三甜矩阵核行压缩存储的力式存一个一维数组B[]中，A（0][0）＞.；第一个元为,存放J BW1.AH中旬个数据元B[]中占个位挥顶A圆[5]在敏折BI]中的位置为〔3）：一算术表送式的中貂形式为A+BT-D E，后缀形式为ABC*+DE/-.倏前缓为（4"林F中有二棵树.第、第：，第二棵树聘结点个数分切为Ml. M2HI M3.林F双庇的二又树根结盘的右于树上的姑点个敦是（5）.6个质点的无向图至少W仃f6J条边彳•能确保是个连」也图.邻接表表示的圈进行任一种遍必时.其时间复杂度姑⑺*在肖序茹表AJL-0]上进律二分栗投,她比绞四次卉找成功的鳍点个数为徵.「义柑中而入一个帖点后造成J'不平也，&最低的不平衙结点为A,并已知拦核!■的平衡而J'为0,1,接f的平础于为1,则应作⑼型调整以使耳平衡。
