数据结构(C语言版)考研真题(A卷)
                   
编辑整理：
尊敬的读者朋友们：
这里是精品文档编辑中心，本文档内容是由我和我的同事精心编辑整理后发布的，发布之前我们对文中内容进行仔细校对，但是难免会有疏漏的地方，但是任然希望（数据结构(C语言版)考研真题(A卷)）的内容能够给您的工作和学习带来便利。同时也真诚的希望收到您的建议和反馈，这将是我们进步的源泉，前进的动力。
本文可编辑可修改，如果觉得对您有帮助请收藏以便随时查阅，最后祝您生活愉快 业绩进步，以下为数据结构(C语言版)考研真题(A卷)的全部内容。
密封线内不要写题
二O 一四年招收硕士研究生入学考试试题
考试科目代码及科目名称：　856 数据结构(C语言版）     
答题内容写在答题纸上,写在试卷或草稿纸上一律无效考完后试题随答题纸交回。
考试时间3小时,总分值  150  分。
一、选择题(10小题，每题2分，共20分）
1。 算法分析的主要内容是（    ）。
A）正确性    B)可读性和稳定性    C）简单性  D）空间复杂性和时间复杂性
2。 线性表若采用链式存储结构时，要求内存中可用存储单元的地址(    ）.
A）必须是连续的      B）部分地址必须是连续的
C）一定是不连续的    D）连续或不连续都可以
3. 设有6个元素按1、2、3、4、5、6的顺序进栈，下列不合法的出栈序列是（    )。
A）234165      B）324651      C)431256      D）546321
4. 设有二维数组A［1..12,1。.10]，其每个元素占4个字节，数据按行优先顺序存储,第一个元素的存储地址为100，那么元素A[5，5]的存储地址为（    ）.
A）76      B)176      C）276      D）376
5. 已知一棵二叉树的先序序列为ABDGCFK，中序序列为DGBAFCK，则后序序列为（    ）。
A）ACFKDBG      B)GDBFKCA      C）KCFAGDB      D）ABCDFKG
6。 在二叉树结点的先序,中序和后序序列中,所有叶子结点的先后顺序(    ）。
A）都不相同                      B）完全相同
C）先序和中序相同,而与后序不同    D）中序和后序相同，而与先序不同
武进区卫生局7。 图的深度优先遍历类似于二叉树的（    ）.
A）先序遍历      B）中序遍历      C）后序遍历    D）层次遍历
8。 下面（    ）算法适合构造一个稠密图G的最小生成树。
A） Prim算法      B）Kruskal算法      C）Floyd算法    D）Dijkstra算法
9. 对关键码{46，79,56,38,40,84｝采用堆排序，则初始化堆(小堆）后最后一个元素是(    )。
A）84      B)46      C）56      D）38
10。在Hash函数H（k)=k MOD m中，一般来讲m应取（    ）.
A）奇数      B）偶数      C)素数    D)充分大的数
二、填空题(10小题，每题2分，共20分)
1。 在单向链表某P结点之后插入S结点的操作是（      ）.
2。 线性表Ｌ用数组表示，假定删除表中任一元素的概率相同,则删除一个元素平均需要移动元素的个数是（      )。
3。 一个栈的输入序列是：1，2,3则不可能的栈输出序列是(      ）.
4. 一棵二叉树高度为h，所有结点的度或为0，或为2，则该二叉树最少有（      ）结点。
5. 在完全二叉树中，编号为i和j的两个结点处于同一层的条件是(      ）。
6. 若无向图G=（V,E），其中V=｛a，b,c,d，e ｝ E=｛（a,b),（a,d),（a,c)，(d，c）,(b，e）｝，现采用图的（      ）遍历方法从顶点a开始遍历图,得到的序列为abecd.
7. 求最短路径的Dijkstra算法的时间复杂度为（      ）。
8. 假定有k个关键字互为同义词，若用线性探测再散列法把这k个关键字存入散列表中，至少要进行（      ）次探测。
9。 设在已排序的线性表中共有元素n个，若用二分法查表中的元素.若查成功，至少要比较（      ）次
10。对一组记录（54，38,96，23，15,2,60，45,83）进行直接插入排序，当把第7个记录60插入到有序表时，为寻插入位置需比较（      )次。
三、综合应用题（7小题,每题10分，共70分)
1。 已知A[1.。N］是一棵顺序存储的完全二叉树，如何求出A[i］和A［j］的最近的共同祖先?
2。 请给出一棵哈夫曼树中分支数B与叶子节点数n0所满足关系式，并证明你的结论.
3. 下面的排序算法的思想是：第一趟比较将最小的元素放在r[0］中，最大的元素放在r[n-1]中，第二趟比较将次小的放在r[1］中，将次大的放在r[n-2]中，…，依次下去，直到待排序列为递增序。（注:〈—-〉 代表两个变量的数据交换）。
void  sort(SqList ＆r，int n) 
{  i=0;
while(    （1）    ） 
｛    min=max=i；
        for (j=i+1;    （2）    ;++j）
        {  if(    (3）    ) min=j; else if(r［j］.key>r[max］。key)  max=j; }
        if（    （4）    济南市安全教育平台登录入口） r［min]〈--〉r[i]；
        if(max!=n-i—1)
        { if（广州考试信息网    (5）    ） r［min］<-->r[n-i-1］； else r［max］〈-—>r[n—i—1］； ｝
        i++；
｝
}//sort
4。 如下图所示的AOE网
（1）写出所有的拓扑序列
(2）求各顶点代表的事件的最早发生时间和最迟发生时间
(3)求各条弧代表的活动的最早开始时间和最迟开始时间
（4）给出其关键路径
河南省教育厅网站5。 设哈希函数H(K）=3 K mod 11,哈希地址空间为0~10，对关键字序列（32，13,49，24，38,21，4，10）,按下述两种解决冲突的方法构造哈希表,并分别求出等概率下查成功时和查失败时的平均查长度ASLsucc和ASLunsucc。
（1)线性探测法    （2）链地址法
6。 全国有10000人参加竞赛，只录取成绩优异的前10名，并将他们从高分到低分输出.而对落选的其他考生，不需排出名次，问此种情况下,用何种排序方法速度最快？为什么？
7。 假定对有序表(3，4,5，17,24,35，40,54,58,72，80,123）进行折半查,试回答问题：
（1）画出描述折半查过程的判定树；
(2）若查元素54，需依次与那些元素比较？
（3）若查元素20，需依次与那些元素比较?
（4）分别求等概率情况下查成功和不成功时的平均查长度。
四、算法设计与编程(4小题,每题10分，共40分）
1。 设有一头指针为L的带有表头结点的非循环双向链表，其每个结点中除有pred(前驱指针)，data（数据）和next(后继指针）域外，还有一个访问频度域freq.在链表被启用前，其值均初始化为零。每当在链表中进行一次Locate（L,x）运算时，令元素值为x的结点中freq域的值增1,并使此链表中结点保持按访问频度非增（递减)的顺序排列，同时最近访问的结点排在频度相同的结点的最后,以便使频繁访问的结点总是靠近表头。试编写符合上述要求的Locate（L,x)运算的算法,该运算为函数过程，返回到结点的地址，类型为指针型。
2. 已知二叉树用下面的顺序存储结构,写出先序遍历该二叉树的算法。
广西省考进面名单公布
1
2
3
4
5
6
7
8
9
  data 
A
B
C
D
考研一般几月份报名E
F
G
H
I
  Lc
2
4
0
0
0
8
0
0
0
  Rc
3
5
6
0
7
9
0
0
0
3。 编写在后序线索二叉树中求任一结点直接前驱的算法(结点结构包括数据域data、左孩子域left、右孩子域right、左标志域ltag和右标志域rtag，标志域为0表示没有孩子，孩子域为线索).
4. 有n个记录存储在带头结点的双向链表中，现用双向冒泡排序法对其按上升序进行排序，请写出这种排序的算法。（注:双向冒泡排序即相邻两趟排序向相反方向冒泡）。