数据结构测试.doc

1、精品文档数据结构测试一选择题（每题2 分，共 30 分）1在数据结构中，从逻辑上可以把数据结构分成（C ）A动态结构和静态结构B紧凑结构和非紧凑结构C线性结构和非线性结构D内部结构和外部结构2算法分析的目的是（ C ）A给出数据结构的合理性B研究算法中的输入和输出关系C分析算法的效率以求改进D分析算法的易懂性和健壮性3线性表中各元素之间的关系是（C ）关系。A层次B网状C有序D集合4非空的循环单链表head 的尾结点 p 满足（ B ）Ap-next=NULLBp-next=headCp=NULLDp=head5设单链表中指针 p 指向结点 m，若要删除 m之后的结点（若存在），则需修改指针的

2、操作为（ A ）Ap-next=p-next-next;B p=p-next;Cp=p-next-next;D p-next=p;6某线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ A ）存储方式最节省运算时间。A单链表B仅有头指针的单循环链表C双链表D仅有尾指针的单循环链表7栈和队列都是（B ）A顺序存储的线性结构B 限定存取的线性结构C链接存取的线性结构D 限定存储的非线性结构8一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是（C ）AedcbaBdecbaC dceabD abcde9具有 n 个单元的顺序存储的循环队列中，假定 front和

3、rear 分别为队头指针和队尾指针，则判断队满的条件为（D ）。1 欢迎下载精品文档Arear n= =front B front+l=rearCrear= =frontD(rear+l)n=front10两个字符串相等的条件是（D ）A两串的长度相等B两串包含的字符相同C两串的长度相等，并且两串包含的字符相同D两串的长度相等，并且对应位置上的字符相同11在一棵度为 3 的树中，度为3 的结点数为2 个，度为 2 的结点数为 1 个，度为 1 的结点数为 2 个，则度为 0的结点数为（）个。A. 4B. 5C. 6D. 712设森林 F 对应的二叉树为B，它有 m个结点， B 的根为 p,p

4、的右子树结点个数为 n, 森林 F 中第一棵树的结点个数是（）Am-nBm-n-1Cn+1D条件不足，无法确定13若下面几个符号串编码集合中，不是前缀编码的是（）。A0,10,110,1111B 11,10,001,101,0001C00,010,0110,1000D b,c,aa,ac,aba,abb,abc14引入二叉线索树的目的是（）A加快查找结点的前驱或后继的速度B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲D使二叉树的遍历结果唯一15n 个结点的线索二叉树上含有的线索数为（）A2nB nlC n lDn二填空题（每空1 分，共 5 分）1一个线性表常进行存取操作，很少进

5、行插入和删除操作时，则采用顺序存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用链式存储结构为宜。2栈顶的位置是随着压栈运算而变化的。3已知一棵哈夫曼树含有60 个叶子结点，则该树中共有_59_叶子结点。4某树的前序序列为ABCED，后续序列为 BECDA，则该树所转换成的二叉树的后。2 欢迎下载精品文档续序列为。三判断题：在你认为正确的题后（）中填写T，错误的填写 F（每题 1 分，共5 分）1数据的逻辑结构是指数据的各数据项之间的逻辑关系。（T）2顺序存储方式只能用于存储线性结构。（F）3线性表的顺序存储结构的优点是存储密度大，且插入、删除运算效率高。（F）4将一棵树转换为二叉树后

6、，根结点没有左子树。（F）5完全二叉树中，若一个结点没有左孩子，则必是叶结点。（ T）四简答题（每题5 分，共 10 分）1简述下列算法的功能，并给出队列Q=12，34，25，4，8 在执行下列算法后的状态。void unknows(SqQueue &Q)SqStack S;int k;Initstack(S);while(!queueempty(Q)Dequeue(Q,k);Push(S,k);while(!stackempty(S)Pop(S,k);Enqueue(Q,k);功能：队列 Q的值：。3 欢迎下载精品文档2假设以二叉链表表示二叉树，其类型定义如下：typedef struct

7、node DataType data;struct node * lchild, * rchild;/左右孩子指针* BinTree ;阅读下列算法，并回答问题： 已知以 T 为根指针的二叉树如图所示， 写出执行 Demo2(T)之后的返回值； 简述算法 Demo2的功能。int Demo2( BinTree T)int d;if ( ! T) return 0;d = Demo2 ( T - lchild) +Demo2 ( T - rchild) ;if (T - lchild & T - rchild)return d + 1 ;elsereturn d; 返回值： 功能：五算法题（每题5 分，共 10 分）1设计一个算法，判断链表中数