数据结构复习题.doc

A卷选择题。算法评价不包括<B)A健壮性和可读性B、并行性C、正确性D、时空复杂度2、对线性表,在下列哪种情况下应当采用链表表示<B)A经常需要随机地存取元素B经常需要进行插入和删除操作C表中元素需要占据一片连续的存储空间D表中元素个数不变3、在带结点的单链表HL中,要向表头插入一个由指针P指向的结点,则执行<A)A、p->next=HL->next,HL->next=p。B、p->next=HL,HL=pC、p->next=HL,p=HLD、HL=p,p->next=HL4、栈和对列的共同特征<只允许在端点处插入和删除元素)5、树最适合用来表示<元素之间具有分支层次关系的数据)6、任何一个无向连通图的最小生成树<一定有多棵)7、已知一个图,若从顶点a出发按深度搜索法进行遍历,则顶点序列为<D)AabcedfBabcefdCaebcfdDacfdebb5E2RGbCAPABecDf8、字符串的长度是指<串中所含字符的个数)9、非空广义表的表头<D)A不可能是子表B只能是子表C只能是原子D可以是子表或原子10、在一棵度为3的树中,度为3的结点个数为2,度为2的结点个数为1,则度为0的结点个数为<C)A4B5C6D711、设指针变量front表示链表队列的头指针,若指针rear表示链式队列的尾指针,指针变量指向将要插入队列的结点s,则入队列的操作序列为<C)p1EanqFDPwAfront->next=s,front=sBs->next=rear,rear=sDXDiTa9E3dCrear->next,rear=sDs->next=front,front=sRTCrpUDGiT12、设A=(D,R>,D={1,2,3,4},R={r},r={<1,2>,<2,3>,<3,4>,<4,1>},则A是<C)5PCzVD7HxAA线性结构B树型C图型D集合13、设某有向图的邻接表中有n个表头结点和m个表结点,则该图中有<C)条有向边AnBn—1CmDm-1jLBHrnAILg14、对于线性表<7,34,55,25,64,40,20,10)进行散列存储时,若选用H<K)=k%9作为散列函数,则散列地址为1的元素有<D)个xHAQX74J0XA、1B、2C、3D、415、设有6个结点的无向图,该图至少应有<A)条边才能确保是一个连通图A5B6C7D816、下面关于线性表的叙述错误的是<D)A线性表采用顺序存储必须占用一片连续的存储空间B线性表采用顺序存储不必占用一片连续的存储空间C线性表采用链式存储便于插入和删除操作的实现D线性表采用顺序存储便于插入和删除操作的实现17、设带有头结点的单向循环链表的头指针变量为head,则其判空条件<C)A、head=0,B、head->next=0C、head->next=headD、head!=018、组成数据额基本单位是<C)A数据项B数据类型C数据元素D数据变量19、在一个单链表中,若q所指结点是P所指结点的前驱结点,若在q与p之间插入一个s所指的结点,则执行<D)LDAYtRyKfEAs->link=p->link,p->link=sBp->link=s,s->link=qZzz6ZB2LtkCp->link=s->link,s->link=pDq->link=s,s->link=pdvzfvkwMI120、设某棵二叉树