武汉理工大学2012数据结构考研真题

第1页，共4页武汉理工大学2012年研究生入学考试试题课程：数据结构一、单选题（在每小题的四个备选答案中选出一个正确答案，每小题3分，共45分。）1.若线性表最常用的操作是存取第i个元素及其前趋的值，则采用______存储方式节省时间。A.单链表B.双链表C.单循环链表D.顺序表2.设输入序列为1、2、3、4，则借助栈所得到的输出序列不可能是_________。A.1、2、3、4B.4、1、2、3C.1、3、4、2D.4、3、2、13.常对数组进行的两种基本操作是。A.建立与删除B.插入与修改C.查找与修改D.查找与插入4.数组Q［ｎ］用来表示一个循环队列，ｆ为当前队列头元素的前一位置，ｒ为队尾元素的位置，假定队列中元素的个数小于ｎ，计算队列中元素的公式为。A.r－fB.（n＋f－r）%nC.n＋r－fD.（n＋r－f）%n5.广义表((a，b，c，d))的表尾是。A．aB．()C．(a，b，c，d)D．((a，b，c，d))6.实现任意二叉树的后序遍历的非递归算法而不使用栈结构，最佳方案是二叉树采用存储结构。A.三叉链表B.广义表存储结构C.二叉链表D.顺序表存储结构7.在线索化二叉树中，P所指的结点没有左子树的充要条件是_________________。A.P-left==nullB.P-ltag=1C.P-ltag==1且P-left==nullD.以上都不对8.稀疏矩阵一般的压缩存储方法有两种，即__________。A.二维数组和三维数组B.三元组和散列C.三元组和十字链表D.散列和十字链表9.有n个结点的有向图的边数最多有。A.nB.n(n-1)C.n(n-1)/2D.2n10.带权有向图G用邻接矩阵A存储，则顶点i的入度等于A中。第2页，共4页A.第i行非无穷元素之和B.第i列非无穷元素之和C.第i行非零且非无穷元素个数D.第i列非零且非无穷元素个数11.采用邻接表存储的图的深度优先遍历算法类似于二叉树的_________________。A.先序遍历B.中序遍历C.后序遍历D.按层遍历12.链表适用于查找。A.顺序B．二分法C．顺序，也能二分法D．随机13.有一个长度为12的有序表，按二分查找法对该表进行查找，在表内各元素等概率情况下查找成功所需的平均比较次数为。A.35/12B．37/12C．39/12D．43/1214.快速排序在下列情况下最易发挥其长处。A.被排序的数据中含有多个相同排序码B.被排序的数据已基本有序C.被排序的数据完全无序D.被排序的数据中的最大值和最小值相差悬殊15.若一组记录的排序码为（46,79,56,38,40,84），则利用堆排序的方法建立的初始堆为。A.79,46,56,38,40,84B.84,79,56,38,40,46C.84,79,56,46,40,38D.84,56,79,40,46,38二、填空题（每空3分，共30分。）1.设n为正整数，求以下程序段中以记号@的语句的频度是__________。k=0;for(i=1;i=m;i++){for(j=1;j=n;j++)@k++;}2.在一个单链表中的P所指结点之前插入一个S所指结点时，可执行如下操作：S-next=P-next;P-next=S;T=P-data;P-data=_____①____;S-data=_____②____。第3页，共4页3.在单链表中，要删除某一指定的结点（该结点不为首元结点），必须找到该结点的_______________结点。4.在具有n个单元的循环队列中，队满时共有个元素。5.三维数组a[4][5][6](下标从0开始计，a有4×5×6个元素)，每个元素的长度是2，则a[2][3][4]的地址是_____________。（设a[0][0][0]的地址是1000，数据以行为主序方式存储）。6.5层完全二叉树至少有______________个结点。7.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的倍。8.在各种查找方法中，平均查找长度与结点个数n无关的查找方法是。9.设要将序列（Q,H,C,Y,P,A,M,S,R,D,F,X）中的关键码按字母序的升序重新排列，则冒泡排序一趟扫描的结果是。三、简答题（3题，共45分。）1.（6分）说明线性表、栈与队列的异同点。2.（19分）设二叉树BTree的存储结构如下：12345678910left00237580101datajhfdbacegiright0009400000其中，BTree为树根结点指针，left、right分别为结点的左、右孩子指针域，在这里使用结点编号作为指针域值，0表示指针域值为空；data为结点的数据域。请完成如下问题：(1)画出二叉树BTree的逻辑结构；(2)写出按先序、中序和后序遍历二叉树BTree所得到的结点序列；(3)画出二叉树BTree的后线索化树。3.（20分）已知如右图所示的有向图，请给出该图的:第4页，共4页(1)每个顶点的入/出度；(2)邻接矩阵；(3)邻接表；(4)逆邻接表。四、编程题：(每小题15分，共30分)1.如果一个线性表是由循环双链表来实现的，该链表只有表头指针而没有表尾指针。请编写算法实现对该线性表进行如下运算：(1)删除第一个元素；(2)删除最后一个元素；(3)在第一个元素前面插入新元素；(4)在最后一个元素的后面插入新元素。注：链表中的结点定义为如下:typedefstructnode{elemTypedata;structnode*prior;structnode*next;}DNode;2.有一个不带头结点的有序单链表（从小到大排序），表头指针为head，编写算法：(1)向该单链表中插入一个元素为x的结点，使插入后该链表仍然有序；(2)依次输出链表中的元素。顶点123456入度出度