数据结构学位考试试卷A.doc

O八-O九学年第一学期申请广州大学学士学位抽考课程试卷(A)课程名称数据结构考试形式(开/闭卷)系别专业班级学号姓名试题一二三四五六总分评卷人分值20**********得分考试时间:1月日答题时间:120分钟考试地点:考试形式:闭卷一、单项选择题(每题1分,只有一个正确答案)分值20得分线性表的链式存储比顺序存储最有利于进行()。 ,所有顶点的度数之和等于所有边数的()倍。 利用n个值作为叶子节点的权生成的哈夫曼树中共包含有()个节点。 +1 ×n ×n-1为了实现树的层次遍历算法,使用的一个辅助数据结构为()。 ,则栈的不可能的输出序列是()。,则判断队空的条件为()。!=rear!=NULL==NULL==rear在一个长度为N的数组空间中,顺序存储着一个队列,该队列的队首和队尾指针分别用front和rear表示,则该队列中的元素个数为()。A.(rear-front)%NB.(rear-front+N)%NC.(rear+N)%ND.(front+N)%N在一棵具有n个节点的二叉树的第i层上(根节点为第1层),最多具有()个节点。 +1 根据n个元素建立一棵二叉搜索树时,其时间复杂度为()。(n) (log2n) (n2) (nlog2n)n(n>1)个顶点的强连通图中至少含有()条有向边。-1 (n-1)/2 (n-1)输入序列为ABC,若变为CBA时,经过的栈操作为(),push,push,pop,pop,,pop,push,pop,push,,push,pop,pop,push,,pop,push,push,pop,pop若一棵二叉树具有10个度为2的结点,5个度为1的结点,则度为0的结点个数是(),若要在指针q所指节点的后面插入一个由指针p所指向的节点,则执行()操作。->next=p->next;p->next=q;->next=q->next;q=p;->next=p->next;p->next=q;->next=q->next;q->next=p;在一个带头节点的循环双向链表中,若要在指针p所指向的节点之后插入一个q指针所指向的节点,则需要对q->right赋值为()。->left >right >right->right>left->left假定利用数组a[N]顺序存储一个栈,用top表示栈顶指针,top=-1表示栈空,并已知栈未满,当元素x进栈时所执行的操作为()。[--top]=x;[top--]=x;[++top]=x;{top++}=x;如果一个元素序列基本有序时,则选用()方法较快。,其有多少种不同的形态(): 对于具有e条边的无向图,它的邻接表中有()个边节点。-1 (e-1) 下述二叉树中,哪一种满足性质:从任一结点出发到根的路径上所经过的结点序