资源描述：
《【精品】数据结构B期末试卷》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、海南大学20010-2011学年度第1学期试卷科目：《数据结构》试题B姓名：学号：学院：信息技术学院专业班级：成绩登记表（由阅卷教师用红色笔填写）大题二三四五总分得分阅卷教师：201年月日得分评卷人一、选择题（共30分，每小题2分）1.在一个长度为n的单链表的第i（0Ui〈r））个元素后面插入一个元素时，需要向后移动（）个元素。A.n~iB.n-i+1C.n-i-1D.02.线性表的顺序存储结构是一种（）的存储结构，线性结构的链式存储是一种（）的存储结构。A.随机存取B.顺序存取C.索引存取D.散列存取3.带头结点head的单向循环链表L为空的判断条件是（）A
2、.head二二NULLB.head->next二二NULLC.head->next二二headD.head!=NULL4.若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除进入表中的最后一个元素，则采用（）存储方式最节省运算时间和存储空间。A.单链表B.仅有头指针的单循环链表C.双向链表D.有头尾指针的单循环链表5•设有一个顺序栈S,元素abcdef依次进栈，如果6个元素出栈的顺序是bdcfea,则栈的容量至少应该是（）A.2B.3C.5D.66.向一个栈顶指针为top的带头结点的非空的链栈中删除结点，则其操作步骤是()A.top->next=s;B
3、.s-〉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)6.以下为平衡二叉排序树的查找算法，假设表长为N,则算法的时间复杂度为()A)0(1)B)0(N)C)0(N*N)D)0(log2N)bitree*scarch_fsortree(tfkey)bitree*t;keytypekey;{while(t!=NULL){if(t~>data==key)return(t);if(t~>data>key)t=t->lch
4、ild;elset=t->rchild;}return(NULL);}/*SEARCH_FSORTTREE*/7.在解决计算机主机与打印机间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取岀数据打印。该缓冲区应该是一个()结构A、数组B、线性表C、堆栈D、队列8.一棵有124个叶结点的完全二叉树，最多有()个结点A、247B、248C、249D、2519.一棵非空的二叉树的前序遍历序列和后序遍历序列正好相同，则该二叉树一定满足()A.所有的结点均无左孩子B.所有的结点均无右孩子C.只有一个孤立的结点D.是
5、任意一棵二叉树10.已知字符A、B、C、D的使用频率(权值)分别为22,7,9,27。对其进行HUFFMAN编码，各字符对应的编码为()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)D)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.冒泡排序B.快速排序C.直接插入排序D.归并排序15•对序列(15,9,7,8,20,-1,4)进行排序，进行一趟排序后，数据的排列变为(4,9,7,8,-1,15,20),则采用的是()排序。A.选择排序B.快速排序C.希尔排序D.冒泡排序得分评卷人二、填空题(20分，每空2分)栈的逻辑特点是，队列的逻辑特点是。17、将含100个结点的完全二叉树从根开始，每层从左到
7、右依次对结点编号，根结点的编号为1,则编号为31的结点的双亲的编号为,其右子的编号为C18、设树F由Tl,T2,T3三棵子树组成，与F对应的二叉树为B。已知T1,T2,T3的结点数分别为x,y,z,则该二叉树B的左子树中有个结点，右子树中有个结点。(x・l,y+z)19、设链队列的队头指针为front,队尾指针为rear,队列为空的条件是,队列为满的条件是o20、在有向图中，以顶点v为终点的边的数目称为v的-21•堆是一个键值序列（灯k2,…,kJ,对i=l,2,…，卜;2」，满足（kiWkK且kWk2w（2i+lWn））得分评卷人三、应用题（共25分）22.
8、对下图所示的树，分别写出其先序和后序序
