资源描述：
《数据结构数据结构试卷A2012201302总校1.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、总分一二三四五六题分100303010101010得分学 院班 级学 号姓 名……………○……………密……………○……………封……………○…………线………………………………东北大学考试试卷（A卷） 2012—2013 学年第 2 学期课程名称：数据结构┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄┄得分一、单选题（本题共15小题，每小题2分，共30分）题号123456789101112131415答案1．抽象数据类型ADT的三个组成部分是A．数据对象、数据关系和基本操作B．
2、数据元素、逻辑结构和存储结构C．数据项、数据元素和数据类型D．数据元素、数据结构和数据类型2.在下列对顺序表进行的操作中，算法时间复杂度为O(1)的是A.对顺序表中元素进行排序B.插入第i个元素C.删除第i个元素D.访问第i个元素的前驱3．设p指向单链表中的一个结点，s指向单链表表外待操作的结点，则下述程序段的功能是：s->next=p->next;p->next=s;t=p->data;p->data=s->data;s->data=t;A．删除结点pB．插入结点sC．在结点p之后插入结点sD．结点p与插入结点s的数据域互换4．如果入栈序列是1,3,5，…，97
3、,99，且出栈序列的第1个元素为99，则出栈序列中第30个元素是A．39B．41C．43D．455．用一个大小为1000的数组来实现循环队列，当前的队头和队尾指针分别为4和996，若要达到队列满的条件，可以继续入队的元素个数是A．5B．6C．7D．86．多维数组之所以有行优先顺序和列优先顺序两种存储方式是因为A．数组的元素处在行和列两个关系中B．数组的元素必须从左到右顺序排列C．数组的元素之间存在次序关系D．数组是多维结构，内存是一维结构7.已知一棵含50个结点的二叉树中只有一个叶子结点，则该二叉树与所对应的孩子兄弟链表表示的二叉树的高度相比A.前者比后者低B.前
4、者比后者高C.前者与后者相同D.不易确定8.假设一棵完全二叉树中的第6层上有24个叶子结点，则该二叉树的结点个数最多为A.55B.79C.81D.1279．设某棵二叉树的中序遍历序列为ABCDE，后序遍历序列为BADEC，则该二叉树的层次遍历序列为A．BADCEB．BCDAEC．CAEBDD．CBDAE10.如果某图的邻接矩阵是非对称矩阵，则此图一定不是A.有环图B.有向无环图C.强连通图D.上述答案有错11.若一个具有N个顶点和K条边的无向图（N>K）是一个森林，则该森林的数目一定是A．KB．NC．N-KD．112.已知哈希表的存储空间为T[0..18]，哈希函
5、数H（key）=key%17,并用线性探测再散列法处理冲突。哈希表中已插入下列关键字：T[5]=39，T[6]=57和T[7]=7，则下一个关键字23插入的位置是A.T[2]B.T[4]C.T[8]D.T[10]13．若有序表的关键字序列为（b,c,d,e,f,g,q,r,s,t），则在二分查找关键字为w的过程中，先后进行比较的关键字依次为A．f,r,s,tB．f,s,g,qC．g,q,s,tD．g,d,q,s14．对关键字序列（5，1，4，3，7）进行堆排序时，输出第2个元素后的序列结果为A．（1，3，4，5，7）B．（7，3，5，4，1）C．（1，4，3，5，
6、7）D．（7，4，5，3，1）15．下列排序算法中，时间复杂度不受数据初始状态影响，恒为0(nlog2n)的是A.归并排序B.冒泡排序C.直接选择排序D.快速排序得分二、应用题（本题共5小题，每小题6分，共30分）16.双端队列是一种插入和删除仅在线性表的两端都可进行的线性表。若允许一端进行插入和删除，另一端只允许删除的双端队列为输入受限的双端队列。假设输入序列为1，2，3，4。双端队列的左端为单输入端。试求：（1）画出输入受限的双端队列的示意图。（2）给出单输入端的输出端口不可能得到的输出序列。（至少5种）第1页（共4页）……………○……………密……………○……
7、………封……………○…………线………………………………19．已知一组初始记录关键字序列为(3，9，51，8，4，7，2，52)。试求：（1）给出该序列的快速排序的前三趟结果。（2）举例说明快速排序的不稳定性。20.已知一组初始记录关键字序列为(35，20，33，48，59，47，62，50，48)。其哈希函数为H(key)=key%13，处理冲突的方法为链地址法。试求：（1）设计哈希表。（2）在等概率查找时查找成功的平均查找长度。17．已知带有双亲指针域的二叉树的结点类型PTNnde逻辑结构如下所示：LchildDataParentRchild试求：（1）给出该二
8、叉树的存储
