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

海南大学2010-2011学年度第1学期试卷 科目：《数据结构》试题 B 姓名： 学 号： 学院： 信息技术学院 专业班级： 成绩登记表（由阅卷教师用红色笔填写） 大题号 一 二 三 四 五 总分 得分 阅卷教师： 201 年 月 日 得分 评卷人 一、 选择题（共30分，每小题2分） 1.在一个长度为n的单链表的第i（0=in）个元素后面插入一个元素时，需要向后移动（　d　 ）个元素。 A．n-i B.n-i+1 C.n-i-1 D.0 2．线性表的顺序存储结构是一种（b ）的存储结构，线性结构的链式存储是一种（　c　）的存储结构。 A．随机存取 B.顺序存取 C.索引存取 D.散列存取 3.带头结点head的单向循环链表L为空的判断条件是（a　　） A. head==NULL B. head-next==NULL C. head-next==head D. head!=NULL 4.若某线性表最常用的操作是在最后一个元素之后插入一个元素和删除进入表中的最后一个元素，则采用（　b　 ）存储方式最节省运算时间和存储空间。 A.单链表 B.仅有头指针的单循环链表 C.双向链表 D.有头尾指针的单循环链表 5.设有一个顺序栈S，元素a b c d e f依次进栈，如果6个元素出栈的顺序是b d c f e a，则栈的容量至少应该是（　b　　　） A.2 B.3 C.5 D.6 6．向一个栈顶指针为top的带头结点的非空的链栈中删除结点，则其操作步骤是（　c　　） A.top-next=s; B.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) 7. 以下为平衡二叉排序树的查找算法, 假设表长为N，则算法的时间复杂度为（　d ） A）O（1） B） O（N） C） O（N*N） D） O（log2 N） bitree *search_fsortree(t, key) bitree *t; keytype key; { while(t!=NULL) { if(t-data==key) return(t); if(t-datakey) t=t-lchild; else t=t-rchild; } return(NULL); }/* SEARCH_FSORTTREE */ 8. 在解决计算机主机与打印机间速度不匹配问题时通常设置一个打印数据缓冲区，主机将要输出的数据依次写入该缓冲区，而打印机则从该缓冲区中取出数据打印。该缓冲区应该是一个（　　d　）结构 A、数组　　　B、线性表　　　C、堆栈　　　D、队列 9. 一棵有124个叶结点的完全二叉树，最多有（a ）个结点 A、247　　　　B、248　　　　C、249　　　D、251 10.一棵非空的二叉树的前序遍历序列和后序遍历序列正好相同，则该二叉树一定满足（　　c　） A.所有的结点均无左孩子 B.所有的结点均无右孩子 C.只有一个孤立的结点 D.是任意一棵二叉树 11. 已知字符A、B、C、D的使用频率（权值）分别为22，7，9，27。对其进行HUFFMAN编码，各字符对应的编码为（ 　c　　 ） A（001）B（100）C（110） D（0） A（100） B（101）C（0） D（11） A（11） B（100）C（111） D（0） A（100）B（1011）C（11） D（0） 12.在具有N个顶点和N条边的无向图的邻接表存储中，邻接表中结点的总数为（　　 ） A.N B.2N C.3N D.4N 13. 由同一关键字集合构造的各棵二叉排序树( ) A. 其形态不一定相同，但平均查找长度相同 B. 其形态不一定相同，平均查找长度也不一定相同 C. 其形态均相同，但平均查找长度不一定相同 D. 其形态均相同，平均