数据结构a卷以及答案-考试用

《数据结构a卷以及答案-考试用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、承诺：我将严格遵守考场纪律，知道考试违纪、作弊的严重性，还知道请他人代考或代他人考者将被开除学籍和因作弊受到记过及以上处分将不授予学士学位，愿承担由此引起的一切后果。专业班级学号学生签名：华东交通大学2012—2013学年第一学期考试卷　　　　　　　　　　　　　　　　　　　　试卷编号：　　　　（A）卷数据结构课程课程类别：必开卷（仅限教材）：　　　　　考试日期：题号一二三四五六七八九十总分累分人签名题分2030103010×××××100得分×××××考生注意事项：1、本试卷共5页，总分100分，考试时间120分钟。2、考试结束后，考生不得将试卷、答题纸和草稿纸带出考场。得分

2、评阅人一、选择题(每题2分，共20分)1、在一个链队列中，若f，r分别为队首、队尾指针，则插入s所指结点的操作为()(A)f->next=c；f=s(B)r->next=s；r=s(C)s->next=r；r=s(D)s->next=f；f=s2、下面程序的时间复杂度为（）for(i=0;i

3、量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。(A)q=p->next；p->data=q->data；p->next=q->next；free(q)；(B)q=p->next；q->data=p->data；p->next=q->next；free(q)；(C)q=p->next；p->next=q->next；free(q)；(D)q=p->next；p->data=q->data；free(q)；5、含N个顶点的连通图中的任意一条简单路径，其长度不可能超过()(A)1(B)N/2(C)N-1(D)N6、设一组初始关键字记录关键字为(20，

4、15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为()。第4页共5页(A)10，15，14，18，20，36，40，21(B)10，15，14，18，20，40，36，21(C)10，15，14，20，18，40，36，2l(D)15，10，14，18，20，36，40，217、若在线性表中采用折半查找法查找元素，该线性表应该()。(A)元素按值有序(B)采用顺序存储结构(C)元素按值有序，且采用顺序存储结构(D)元素按值有序，且采用链式存储结构8、．n个节点的完全二叉树，编号为i的节点是叶子结点的条件是()。(A)i

5、=n(C)2*i+1>n(D)2*i>n9、如果只想得到1024个元素组成的序列中的前5个最小元素，那么用()方法最快。(A)起泡排序(B)快速排序(C)堆排序(D)直接选择排序10、对于线性表（7，34，77，25，64，49，20，14）进行散列存储时，若选用H（K）=K%7作为散列函数，则散列地址为0的元素有（）个，(A)1(B)2(C)3(D)4二、填空题(每空2分，共30分)得分评阅人1、对于一个长度为n的顺序存储的线性表，在表头插入元素的时间复杂度为（1），在表尾插入元素的时间复杂度为（2）。2、设查找表中有100个元素，如果用二分法查找方法查找数据元素X，则最多

6、需要比较__（3）_____次就可以断定数据元素X是否在查找表中3、若无向图G中有n个顶点m条边，采用邻接矩阵存储，则该矩阵中非0元素的个数为__（4）_______。4、若一棵二叉树中只有叶子结点和左、右子树皆非空的结点，设叶结点的个数为M，则左、右子树皆非空的结点个数为_（5）__。5、设数组data［0..m］作为循环队列SQ的存储空间(判断队列满，少用一个元素空间)，front为队头指针，rear为队尾指针，则执行出队操作的语句为(（6）)。6、设哈夫曼树中共有n个结点，则该哈夫曼树中有__（7）____个度数为1的结点。7、设一组初始记录关键字序列为(49，38，6

7、5，97，76，13，27，50)，则以d=4为增量的一趟希尔排序结束后的结果为__（8）。8、队列的插入操作在_（9）___进行，删除操作在（10）____进行。9、下面程序段的功能是建立二叉树的算法，请在下划线处填上正确的内容。typedefstructnode{intdata;structnode*lchild;____(11)____;}bitree;voidcreatebitree(bitree*&bt){scanf(“%c”,&ch);if(ch=='#')（12;第4页共5页else{bt