算法与数据结构试卷b

《算法与数据结构试卷b》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、单选题(每小题2分，共30分)1、在含n个元素的顺序表中插入一个元素，设插入每个位置的概率相同，则平均需移动元素的次数为（）。A、nB、n/2C、(n-1)/2D、(n+1)/22、设在带哨兵结点的单链表中，链结点的指针域为next。若要删除指针p所指结点，设指针q指向其前驱结点，应使用的语句为（）。A、deletep;q->next=p->next;B、deletep;p->next=q->next;C、q->next=p->next;deletep;D、p->next=q->next;deletep;3、下列关于静态链表的说法正确的是（）。A、静态链表中的每个元素

2、都有一个指针域，存放下一元素在内存中的存储地址B、一个数组空间只能存放一条静态链表C、静态链表的扩充受到数组空间的局限D、在静态链表中插入和删除元素需要移动数组空间中的元素4、若用数组stack实现栈，让栈向数组下标增大方向增长，设置整型变量top指向当前栈顶元素所在数组单元下标。则将元素x入栈，应执行的语句为（）。A、stack[++top]=x；B、stack[top++]=x；C、stack[--top]=x；D、stack[top--]=x；福州大学2007～2008学年第二学期考试B卷第6页共6页5、若用循环数组实现队列，队首游标front指向队首元素的前一单元

3、，队尾游标rear指向队尾元素所在单元，设循环数组的单元个数为MaxSize。若使用总剩一个单元不利用的方法区分满空状态，则front和rear满足关系（）时队列为空。A、front==(rear+1)%MaxSizeB、front==rearC、front==(rear+2)%MaxSizeD、front==(rear-1)%MaxSize6、下列关于树的表示法说法正确的是（）。A、父结点数组表示法可以快速找到某结点的子结点，但查询父结点和兄弟结点可能要遍历整个数组B、若采用儿子表示法，并使用定长结点的多重链表结构，则表示一棵有n个结点度为d的树必有nd-n个空链域C、

4、左儿子右兄弟表示法方便查找父结点和兄弟结点，但不方便查找子结点D、儿子链表表示法适合于查找子结点，但不适合于查找父结点和兄弟结点7、利用前序线索链表进行二叉树的前序遍历时，若当前遍历结点存在右子树，则（）。A、由当前结点的后继线索可找到后继结点B、若当前结点有左子树，则后继结点为左子树中最左下结点C、若当前结点有左子树，则后继结点为左子树中最右下结点D、若当前结点无左子树，则后继结点为右子结点8、下列说法错误的是（）。A、具有n个顶点，n-1条边的无向图一定是生成树B、生成树是无向连通图的极小连通子图C、具有n个顶点，少于n-1条边的无向图一定是非连通图D、在生成树中每两

5、个顶点间有且仅有一条路径9、下列说法正确的是（）。A、无向图邻接矩阵第i行非零元素的个数是第i个顶点的度B、通过邻接表可以方便快速地判定两个顶点间是否有边或弧相连C、通过有向图的邻接表，可以方便地求出顶点的入度D、邻接表适用于表示稠密图10、图的广度优先搜索类似于树的（）。A、先序遍历B、中序遍历C、后序遍历D、层次遍历11、如果从无向图的任一顶点出发进行一次深度优先搜索即可访问所有顶点，则该图一定是（）。A、完全图B、连通图C、有回路D、一棵树12、平衡二叉树中结点的平衡因子不可能是（）。A、0B、-1C、1D、-213、对二叉搜索树进行（）可得到元素的递增序列。A、先

6、序遍历B、中序遍历C、后序遍历D、层次遍历14、对一个有向图进行拓扑排序，并判断有向图中是否存在回路，可以使用（）。A、无前趋顶点优先算法B、深度优先遍历算法C、广度优先遍历算法D、求最短路径的Dijkstra算法15、下列有关平衡二叉树的说法错误的是（）。A、平衡二叉树左子树和右子树高度之差的绝对值不大于1B、在平衡二叉树上执行插入操作，对离新插入结点最近的失衡祖先结点为根的子树进行平衡旋转后，一定能使二叉树恢复平衡C、第6页共6页在平衡二叉树上执行删除操作，对离被删结点最近的失衡祖先结点为根的子树进行平衡旋转后，一定能使二叉树恢复平衡D、在含有n个结点的平衡二叉树上执

7、行查找操作的时间复杂度为O(logn)二、填空题（每空1分，共13分）1、在带哨兵结点的单循环链表中，设链结点的后继指针域为next，指针last指向表尾结点，则判断该链表是否为空的表达式为。2、队列的操作原则为。3、若用循环数组实现队列，队首游标front指向队首元素前一单元，队尾游标rear指向队尾元素所在单元，设循环数组名为queue，循环数组的单元个数为MaxSize。则将队头元素出队并保存在x中，应执行的语句为；。4、不考虑树结点所存放的元素值，由3个结点可组成种不同形态的树。5、具有35个结点的二叉树的最小高度为，