991数据结构真题2013

1、采用链结构存储线性表时，其地址（ B ）。

A）必须是连续的 B）连续不连续都可以C）部分地址必须是连续 D）必须是不连续的2、设有一个栈，元素的进栈次序为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, A3、（ C ）在进行插入操作时，常产生假溢出现象。

A）顺序栈 B）循环队列C）顺序队列 D）链队列4、已知广义表L=((x,y,z),a,(u,t,w))，从L 表中取出原子项t 的操作是（ D ）。

A) Head(Head(Tail(Tail(L))))B) Tail(Head(Head(Tail(L))))C) Head(Tail(Head(Tail(L))))D)Head(Tail(Head(Tail(Tail(L)))))5、在一个单链表中，已知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;6、对待排序的元素序列进行划分，将其分为左、右两个子序列，再对两个子序列施加同样的排序操作，直到子序列为空或只剩一个元素为止。

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

A）直接选择排序 B）直接插入排序C）快速排序 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、n个顶点，e条边的有向图的邻接矩阵中非零元素有（ C ）个。

数据结构复习答案一、选择填空1.下面关于线性表的叙述中，错误的是哪一个？（）A）线性表采用顺序存储，必须占用一片连续的存储单元。

√B）线性表采用顺序存储，便于进行插入和删除操作。

C）线性表采用链接存储，不必占用一片连续的存储单元。

D）线性表采用链接存储，便于插入和删除操作。

2.若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则利用（）存储方式最节省时间。

√A）顺序表B）双链表C）带头结点的双循环链表D）单循环链表3.链表不具有的特点是（）。

A）插入、删除不需要移动元素√B）可随机访问任一元素C）不必事先估计存储空间D）所需空间与线性长度成正比4.若长度为n的线性表采用顺序存储结构，在其第i个位置插入一个新元素的算法的时间复杂度为（）(1<=i<=n+1)。

A）O(0) B）O(1) √C）O(n) D）O(n2)5.线性表（a1,a2,…,an）以链接方式存储时，访问第i位置元素的时间复杂度为（）。

A）O(i) B）O(1) √C）O(n) D）O(i-1)6.对于一个头指针为head的带头结点的单链表，判定该表为空表的条件是（）A）head==NULL B）head→next==NULL√C）head→next==head D）head!=NULL7.在单链表指针为p的结点之后插入指针为s的结点，正确的操作是：（）。

A）p->next=s;s->next=p->next; √B）s->next=p->next;p->next=s;C）p->next=s;p->next=s->next; D）p->next=s->next;p->next=s;8.设指针变量p指向单链表结点A，则删除结点A的后继结点B需要的操作为( )。

√A）p->next=p->next->next B）p=p->nextC）p=p->next->next D）p->next=p9.( )又称为FIFO表；( )又称为FILO表。

浙江理工大学二O一二年‎硕士学位研‎究生招生入‎学考试试题‎考试科目：数据结构代码：991 （请考生在答‎题纸上答题‎，在此试题纸‎上答题无效‎）一、单选题(每题2分，共20分)1. 不带头结点‎的单链表s‎i mple‎L ist为‎空的判定条‎件是。

A. simpl‎e List‎== nullB. simpl‎e List‎->next == nullC. simpl‎e List‎->next = simpl‎e List‎D. simpl‎e List‎! = null2. 某线性表最‎常用的操作‎是在最后一‎个结点之后‎插入一个结‎点或删除第‎一个结点，故采用__‎_____‎_____‎___存储‎方式最节省‎运算时间。

A. 单链表B. 仅有头结点‎的单循环链‎表C. 双链表D. 仅有尾指针‎的单循环链‎表3. 向一个栈顶‎指针为to‎p的链栈中‎插入一个S‎所指结点时‎，则执行__‎_____‎_____‎_____‎_____‎_。

A. top->next = S;B. S->next = top->next; top->next = S;C. S->next = top; top = S;D. S->next = top; top = top->next;4. 一维数组和‎线性表的区‎别是___‎_____‎_____‎。

A. 前者长度固‎定，后者长度可‎变B. 后者长度固‎定，前者长度可‎变C. 两者长度均‎固定D. 两者长度均‎可变5. 设矩阵A是‎一个对称矩‎阵，为了节省存‎储，将其下三角‎部分按行序‎存放在一维‎数),在一组数组‎B的下标位‎置组B[1, n(n-1)/2]中，对任一下三‎角部分中任‎一元素ai‎j(i jK的值是‎_____‎_。

A. i(i-1)/2+j-1B. i(i-1)/2+jC. i(i+1)/2+j-1D. i(i+1)/2+j6.在线索化二‎叉树中，P所指的结‎点没有左子‎树的充要条‎件是___‎_____‎_____‎_____‎_____‎。

中南大学考试试卷 2011 -- 2012 学年 一 学期 时间100分钟 数据结构 课程 48 学时 2 学分 考试形式： 闭 卷

专业年级： 信息、通信10 总分100分，占总评成绩 70 % 注：此页不作答题纸，请将答案写在答题纸上，考试时间2012年01月05号 印刷不清晰时请提问，怀疑题目有错误请直接在答题纸上指出并说明。

一、填空题(每小题2分，共20分) 1、若一个广义表为(a,(a,b),d,((i,j,( )),k),e),则该表深度为___ ，表的长度为___ 。 2、设数组A[0..n-1]为循环队列的存储空间，其队头、队尾指针分别为front和rear，则在队列非满时元素x入队的运算是___ 。 3、下面的二叉树对应的后序序列是___ 。

4、有n个结点的二叉树的链式存储结构中，空指针域的数目是___ 。 5、N个顶点的连通图至少有___ 条边。 6、若一个栈的输入序列是1,2，…,N，输出序列的第一个元素是N，则第I个输出元素是 ___ 。 7、对记录的关键字集合Key={50,26,38,80,70,90,8,30,40,20}进行排序，各趟排序结束时的结果为 50 26 38 80 70 90 8 30 40 20 50 8 30 40 20 90 26 38 80 70 26 8 30 40 20 80 50 38 90 70 8 20 26 30 38 40 50 70 80 90 其使用的排序方法是___ 。 8、在无向图中，所有顶点的度数之和等于所有边数的___ 倍。 9、利用筛选法将关键字序列（37，66,48,29,31,75）建成的大根堆为___ 。 10、能够成功完成拓扑排序的图一定是一个___ 。 二、问答及运算题（每小题10分，共50分） 1、按顺序输入顶点对：（1,2），（1,6），（2,6），（1,4），（6,4），（1,3），（3,4），（6,5），（4,5），（1,5），（3,5）， （1）画出对应的图； （2）用头插法构建相应的邻接表； （3）在该邻接表上，写出从顶点V2出发遍历得到的DFS和BFS序列（注：邻接表确立后，对应的序列是唯一的）。 2、任意一个有n个结点的二叉树，已知它有m个叶子节点，试证明非叶子结点有m-1个度数为2，其余度数为1。 3、假设通信电文使用的字符集为{a,b,c,d,e,f}，各字符在电文中出现的频度分别为：34、5、12、23、8、18，试为这6个字符设计哈夫曼编码。请先画出你所构造的哈夫曼树（要求树中左孩子节点的权值小于右孩子结点的权值），然后分别写出每个字符对应的编码。 4、对如下关键字符序列（265,301,751,129,937,863,742,694,076,438），写出执行基数排序算法各趟排序结束时，关键字序列的状态。 5、已知一棵二叉树的中序遍历序列为BAFDHGCE，后序遍历序列为BFHGDECA，请构造出这棵二叉树。

一、选择题1、从逻辑结构上可以把数据结构分为【 C 】。

A、动态结构和静态结构B、紧凑结构和非紧凑结构C、线性结构和非线性结构D、内部结构和外部结构2、在一个长度为n的顺序存储的线性表中，向第i个元素（1≤i≤n+1）之前插入一个新元素时，需要从后向前依次后移【 B 】个元素。

A、n-iB、n-i+1C、n-i-1D、i3、链表结构不具有下列【 B 】特点。

A、插入和删除无需移动元素B、可随机访问链表中的任意元素C、无需实现分配存储空间D、所需空间与结点个数成正比。

4、在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行【C】。

A、s->next = p->next; p->next = s;B、p->next = s->next; s->next = p;C、q->next = s; s->next = p;D、p->next = s; s->next = q;5、一个栈的入栈序列是1，2，3，4，5，则栈不可能输出的序列是【 C 】。

A、54321B、45321C、43512D、123456、判断一个队列Q（元素最多为M个）为空的条件是【 C 】。

A、Q->rear – Q->front = MB、Q->rear – Q->front -1 ==MC、Q->rear == Q->frontD、Q->rear + 1 == Q->front7、在一个链队列中，假设f和r分别指向队首和队尾，则插入s所指结点的运算是【 A 】。

A、r->next = s; r=s;B、f->next = s; f=s;C、s->next = r; r=s;D、s->next = f; f=s;8、深度为5的二叉树至多有【 A 】个结点。

A、31B、32C、16D、109、在一非空二叉树的中序遍历序列中，根结点的右边【 A 】。

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算法的基本思想。

阐述快速排序算法的基本步骤，并分析其平均时间复杂度和最坏时间复杂度。

2013年1月数据结构考试题
一、简答题（5分，共20分）
1.在十万的元素集合中，选出前十个最小的元素，写出冒泡排序，快速排序，堆排序的比较次数。

（哭哭哭。

考试一上来第一题就不会！）
2.给定序列，写出H(x)=x%13的线性开型寻址散列表，并求给定元素的比较次数（原谅我不记得序列。

）
3.给出树的前序中序遍历，求后序遍历（原谅我不记得前序中序序列。

）
4.(1)拓扑排序的算法思想(2)写出给定图的任两种拓扑排序
二、应用题（10分，共50分）
1.原题：第四章练习34前两问求等对角矩阵的映射公式和最多存储的元素个数
2.(1)给定序列构造成二叉树，调整为最大堆，写出最大堆序列(2)插入一个元素，写出再次调整的最大堆（原谅我不记得序列。

）
3.给定一段文字出现的频率，构造huffman树，写出每个汉字的huffman编码，并求出加权外部路径长度（呜呜呜呜呜，又是一个一点都不会问题。

）
4.将序列（16,3,7,11,9,26,18,14,15）依次插入，建立A VL树
5.(1)写出给定有向图的邻接矩阵和邻接表(2)用Dijkstra算法求该图的起始点到任一点的最短路径，写出过程
三、算法题（10，共30分）（太坑了，像我这种java就会helloWord的人基本是一点代码不会写啊）
1.定义一个Chain类的新函数，求有序集合A、B的A∩B，先给出类定义，再给算法实现
2.写一个算法，实现删除二叉搜索树中的最大元素操作，先描述算法思想，后给出代码实现，分析复杂性
3.写算法求图中最短路径（题干太长，因为根本不会，所以记不住题是什么。

）。

《数据结构》考研真题及解答目录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 分）带权图（权值非负，表示边连接的两顶点间的距离）的最短路径问题是找出从初始顶点到目标顶点之间的一条最短路径。