数据结构测试.doc

精品文档数据结构测试一选择题（每题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=NULL Bp-next=headCp=NULL Dp=head5设单链表中指针p指向结点m，若要删除m之后的结点（若存在），则需修改指针的操作为（ A ）Ap-next=p-next-next; Bp=p-next; Cp=p-next-next; Dp-next=p;6某线性表最常用的操作是在最后一个元素之后插入一个元素和删除第一个元素，则采用（ A ）存储方式最节省运算时间。A单链表 B仅有头指针的单循环链表 C双链表 D仅有尾指针的单循环链表7栈和队列都是（ B ）A顺序存储的线性结构 B限定存取的线性结构 C链接存取的线性结构 D限定存储的非线性结构8一个栈的入栈序列是a，b，c，d，e，则栈的不可能的输出序列是（ C ）Aedcba Bdecba Cdceab Dabcde9具有n个单元的顺序存储的循环队列中，假定front和rear分别为队头指针和队尾指针，则判断队满的条件为（ D ）Arearn= =front Bfront+l=rear Crear= =front D(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的右子树结点个数为n,森林F中第一棵树的结点个数是（ ）Am-n Bm-n-1 Cn+1 D条件不足，无法确定13若下面几个符号串编码集合中，不是前缀编码的是（ ）。A0,10,110,1111 B11,10,001,101,0001 C00,010,0110,1000 Db,c,aa,ac,aba,abb,abc14引入二叉线索树的目的是（ ）A加快查找结点的前驱或后继的速度 B为了能在二叉树中方便的进行插入与删除C为了能方便的找到双亲 D使二叉树的遍历结果唯一15n个结点的线索二叉树上含有的线索数为（ ）A2n Bnl Cnl Dn二填空题（每空1分，共5分）1一个线性表常进行存取操作，很少进行插入和删除操作时，则采用顺序存储结构为宜。相反，当经常进行的是插入和删除操作时，则采用 链式 存储结构为宜。2栈顶的位置是随着 压栈 运算而变化的。 3已知一棵哈夫曼树含有60个叶子结点，则该树中共有_59_叶子结点。 4某树的前序序列为ABCED，后续序列为BECDA，则该树所转换成的二叉树的后续序列为 。三判断题：在你认为正确的题后（）中填写T，错误的填写F（每题1分，共5分）1数据的逻辑结构是指数据的各数据项之间的逻辑关系。（T）2顺序存储方式只能用于存储线性结构。（F）3线性表的顺序存储结构的优点是存储密度大，且插入、删除运算效率高。（F）4将一棵树转换为二叉树后，根结点没有左子树。（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的值：2假设以二叉链表表示二叉树，其类型定义如下：typedef struct 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 ; else return d; 返回值： 功能：五算法题（每题5分，共10分）1设计一