数据结构(C语言版)考研真题(A卷)

第1页共3页二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）234165B）324651C）431256D）5463214.设有二维数组A[1..12,1..10]，其每个元素占4个字节，数据按行优先顺序存储，第一个元素的存储地址为100，那么元素A[5,5]的存储地址为（）。A）76B）176C）276D）3765.已知一棵二叉树的先序序列为ABDGCFK，中序序列为DGBAFCK，则后序序列为（）。A）ACFKDBGB）GDBFKCAC）KCFAGDBD）ABCDFKG6.在二叉树结点的先序，中序和后序序列中，所有叶子结点的先后顺序（）。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）84B）46C）56D）3810.在Hash函数H(k)=kMODm中，一般来讲m应取（）。A）奇数B）偶数C）素数D）充分大的数二、填空题（10小题，每题2分，共20分）1.在单向链表某P结点之后插入S结点的操作是（）。2.线性表Ｌ用数组表示，假定删除表中任一元素的概率相同，则删除一个元素平均需要移动元素的个数是（）。3.一个栈的输入序列是：1，2，3则不可能的栈输出序列是（）。4.一棵二叉树高度为h,所有结点的度或为0，或为2，则该二叉树最少有（）结点。5.在完全二叉树中，编号为i和j的两个结点处于同一层的条件是（）。第2页共3页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]中，…,依次下去，直到待排序列为递增序。（注：--代表两个变量的数据交换）。voidsort(SqList&r,intn){i=0;while((1)){min=max=i;for(j=i+1;(2);++j){if((3))min=j;elseif(r[j].keyr[max].key)max=j;}if((4))r[min]--r[i];if(max!=n-i-1){if((5))r[min]--r[n-i-1];elser[max]--r[n-i-1];}i++;}}//sort4.如下图所示的AOE网（1）写出所有的拓扑序列（2）求各顶点代表的事件的最早发生时间和最迟发生时间（3）求各条弧代表的活动的最早开始时间和最迟开始时间（4）给出其关键路径5.设哈希函数H（K）=3Kmod11，哈希地址空间为0～10，对关键字序列（32，13，49，24，38，21，4，10），按下述两种解决冲突的方法构造哈希表，并分别求出等概率下查找成功时和查找失败时的平均查找长度ASLsucc和ASLunsucc。（1）线性探测法（2）链地址法第3页共3页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.已知二叉树用下面的顺序存储结构，写出先序遍历该二叉树的算法。123456789dataABCDEFGHILc240008000Rc3560790003.编写在后序线索二叉树中求任一结点直接前驱的算法（结点结构包括数据域data、左孩子域left、右孩子域right、左标志域ltag和右标志域rtag，标志域为0表示没有孩子，孩子域为线索）。4.有n个记录存储在带头结点的双向链表中，现用双向冒泡排序法对其按上升序进行排序，请写出这种排序的算法。（注：双向冒泡排序即相邻两趟排序向相反方向冒泡）。