海南大学2010-2011数据结构B期末试卷

《海南大学2010-2011数据结构B期末试卷》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、海南大学2010-2011学年度第1学期试卷科目：《数据结构》试题B姓名：学号：学院：信息技术学院专业班级：成绩登记表（由阅卷教师用红色笔填写）大题号一二三四五总分得分阅卷教师：201年月日得分评卷人一、选择题（共30分，每小题2分）1.在一个长度为n的单链表的第i（0<=i

2、ad==NULLB.head->next==NULLC.head->next==headD.head!=NULL4.若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除进入表中的最后一个元素，则采用（　b　）存储方式最节省运算时间和存储空间。A.单链表B.仅有头指针的单循环链表C.双向链表D.有头尾指针的单循环链表5.设有一个顺序栈S，元素abcdef依次进栈，如果6个元素出栈的顺序是bdcfea，则栈的容量至少应该是（　b　　　）A.2B.3C.5D.6106．向一个栈顶指针为top的带头结点的非空的链栈中删除结点，则其操作步骤是（　c　　）A.top->next=s;B.s-

3、>next=top->next;top->next=s;free(s)C.s=top;top=top->next;free(s)D.s=top->next;top=top->next;free(s)7.以下为平衡二叉排序树的查找算法,假设表长为N，则算法的时间复杂度为（　d）A）O（1）B）O（N）C）O（N*N）D）O（log2N）bitree*search_fsortree(t,key)bitree*t;keytypekey;{while(t!=NULL){if(t->data==key)return(t);if(t->data>key)t=t->lchild;elset=t->rc

4、hild;}return(NULL);}/*SEARCH_FSORTTREE*/8.在解决计算机主机与打印机间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个（　　d　）结构A、数组　　　B、线性表　　　C、堆栈　　　D、队列9.一棵有124个叶结点的完全二叉树，最多有（a）个结点A、247　　　　B、248　　　　C、249　　　D、25110.一棵非空的二叉树的前序遍历序列和后序遍历序列正好相同，则该二叉树一定满足（　　c　）A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个孤立的结点D.

5、是任意一棵二叉树11.已知字符A、B、C、D的使用频率（权值）分别为22，7，9，27。对其进行HUFFMAN编码，各字符对应的编码为（　c　　）A）A（001）B（100）C（110）D（0）B）A（100）B（101）C（0）D（11）C）A（11）B（100）C（111）D（0）10A）A（100）B（1011）C（11）D（0）12.在具有N个顶点和N条边的无向图的邻接表存储中，邻接表中结点的总数为（　　）A.NB.2NC.3ND.4N13.由同一关键字集合构造的各棵二叉排序树()A.其形态不一定相同，但平均查找长度相同B.其形态不一定相同，平均查找长度也不一定相同C.其形态均相

6、同，但平均查找长度不一定相同D.其形态均相同，平均查找长度也都相同D.以上都不是14.设有1000个基本有序的元素，希望用最快的速度挑选出其中前10个最大的元素，最后选用（　　a　）排序法。A.冒泡排序B.快速排序C.直接插入排序D.归并排序15.对序列（15，9，7，8，20，-1，4）进行排序，进行一趟排序后，数据的排列变为（4，9，7，8，-1，15，20），则采用的是（　　b　）排序。A.选择排序B.快速排序C.希尔排序D.冒泡排序得分评卷人二、填空题（20分，每空2分）16.栈的逻辑特点是_后进先出__，队列的逻辑特点是_先进先出_。17、将含100个结点的完全二叉树从根开始，

7、每层从左到右依次对结点编号，根结点的编号为1，则编号为31的结点的双亲的编号为__15_______，其右子的编号为____63_____。18、设树F由T1，T2,T3三棵子树组成，与F对应的二叉树为B。已知T1,T2,T3的结点数分别为x，y，z，则该二叉树B的左子树中有__x-1个结点，右子树中有_y+z____个结点。（x-1,y+z）19、设链队列的队头指针为front，队尾指针为rear，队列为空的条件是___rear=