川农《数据结构》在线作业一

(单选题) 1: 用链接方式存储的队列，在进行插入运算时(). A: 仅修改头指针 B: 头、尾指针都要修改 C: 仅修改尾指针

D: 头、尾指针可能都要修改 正确答案:

(单选题) 2: 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。

A: O(n) B: O(nlog2n) C: O(1) D: O(n2 ) 正确答案:

(单选题) 3: 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。A: q=p->next；p->data=q->data；p->next=q->next；free(q)；

B: q=p->next；q->data=p->data；p->next=q->next；free(q)；

C: q=p->next；p->next=q->next；free(q)； D: q=p->next；p->data=q->data；free(q) 正确答案:

(单选题) 4: 设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。

A: O(1) B: O(log2n) C: O(n4) D: O(n2 ) 正确答案:

(单选题) 5: 非空的循环单链表head的尾结点（由p所指向）满足（）。

A: p->next= =NULL B: p= =NULL C: p->next= =head D: p= =head 正确答案:

(单选题) 6: 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下标依次为( c d )

A: 1，2，3 B: 9，5，2，3 C: 9，5，3 D: 9，4，2，3 正确答案:

(单选题) 7: 设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。

A: BADC B: BCDA C: CDAB D: CBDA 正确答案:

(单选题) 8: 在一非空二叉树的中序遍历序列中，根结点的右边（）。

A: 只有右子树上的所有结点 B: 只有右子树上的部分结点 C: 只有左子树上的部分结点 D: 只有左子树上的所有结点 正确答案: B: O(n2)

C: O(n3) D: O(n4 ) 正确答案:

(单选题) 10: 一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。

A: 110 B: 108 C: 100 D: 120 正确答案:

(单选题) 11: 设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为（）。A: 2h

B: 2h-1 C: 2h+1 D: h+1 正确答案:

(单选题) 12: 线性表是一个具有n个（）的有限序列 A: 表元素 B: 字符 C: 数据元素 D: 数据项 正确答案:

(单选题) 13: 设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。

A: 2n B: n C: n/2 D: n(n-1) 正确答案:

(单选题) 14: 判定一个循环队列QU（最多元素为m0, m0=

=Maxsize-1）为满队列的条件是（）。

A: ((rear- front)+ Maxsize)% Maxsize = =m0 B: rear-front-1= =m0 C: front= =rear D: front= = rear+1 正确答案:

(单选题) 15: 判定一个循环队列QU（最多元素为m0）为空的条件是（）。

A: rear - front= =m0 B: rear-front-1= =m0 C: front= = rear D: front= = rear+1 正确答案:

(单选题) 16: 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是（）有限集合，R是D 上的关系有限集合。

A: 算法 B: 数据元素 C: 数据操作 D: 数据对象 正确答案:

(单选题) 17: 设a,b为一棵二叉树上的两个结点，在中序遍历时，a在b前的条件是（）。

A: a在b的右方 正确答案:

(单选题) 18: 设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是（）。

A: N0=N1+1 B: N0=Nl+N2 C: N0=N2+1 D: N0=2N1+l

正确答案:

(单选题) 19: 设无向图的顶点个数为n，则该图最多有（）条边。 A: n-1 B: n(n-1)/2 C: n(n+1)/2 D: 0 正确答案:

(单选题) 20: 一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是（）。

A: edcba B: decba C: dceab D: abcde 正确答案:

(单选题) 21: 设串s1='ABCDEFG'，s2='PQRST'，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串

A: BCDEF B: BCDEFG C: BCPQRST D: BCDEFEF 正确答案:

(单选题) 22: 设有一个二维数组A[m][n]，假设A[0][0]存放位置在4(10)，A[2][2]存放位置在676(10)，每个元素占一个空间，问A[3][3](10)存放在( )位置.脚注(10)表示用10进制表示。

A: 688 B: 678 C: 692 D: 696

s

的长度，则

con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是（）。

正确答案:

(单选题) 23: 向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行（）。(不带空的头结点)

A: HS—＞next=s;

B: s—＞next= HS—＞next;HS—＞next=s; C: s—＞next= HS;HS=s;

D: s—＞next= HS;HS= HS—＞next; 正确答案:

(单选题) 24: 线性表的顺序存储结构是一种（）的存储结构。 A: 随机存取 B: 索引存取 C: 顺序存取 D: 散列存取 正确答案:

(单选题) 25: 二维数组A中，每个元素A的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，该数组按行存放时，数组元素A[7][4]的起始地址为（）。

A: SA+141 正确答案:

(单选题) 26: 若已知一个栈的入栈序列是1，2，3，…，n，其输出序列为p1，p2，p3，…，pn，若p1=n，则pi为（）。

A: i B: n=i C: n-i+1 D: 不确定 正确答案:

(单选题) 27: 在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行（）。

A: s->next=p->next;p->next=s; B: p->next=s->next;s->next=p;

C: q->next=s;s->next=p; D: p->next=s;s->next=q; 正确答案:

(单选题) 28: 设一组初始记录关键字序列为(345，253，674，924，627)，则用基数排序需要进行（）趟的分配和回收才能使得初始关键字序列变成有序序列。

A: 3 B: 4 C: 5 D: 8 正确答案:

(单选题) 29: 设一组初始关键字记录关键字为(20，15，14，18，21，36，40，10)，则以20为基准记录的一趟快速排序结束后的结果为( )。

A: 10，15，14，18，20，36，40，21 B: 10，15，14，18，20，40，36，21 C: 10，15，14，20，18，40，36，2l D: 15，10，14，18，20，36，40，21 正确答案:

(单选题) 30: 判定一个顺序栈ST（最多元素为m0）为栈满的条件是（）。

A: top！=0 B: top= =0 C: top！=m0 D: top= =m0-1 正确答案:

(单选题) 31: 栈和队列的共同特点是( )。 A: 只允许在端点处插入和删除元素 B: 都是先进后出 C: 都是先进先出

D: 没有共同点 正确答案:

(单选题) 32: 按照二叉树的定义，具有3个不同数据结点的不同的二叉树有（）种。

A: 5 B: 6 C: 30 D: 32 正确答案:

(单选题) 33: 在一个单链表中，若删除p所指结点的后续结点，则执行（）。

A: p->next=p->next->next;

B: p=p->next;p->next=p->next->next;

(单选题) 34: 深度为5的二叉树至多有（）个结点。 A: 16 B: 32 C: 31 D: 10 正确答案:

(单选题) 35: 二维数组A中，每个元素的长度为3个字节，行下标i从0到7，列下标j从0到9，从首地址SA开始连续存放在存储器内，存放该数组至少需要的字节数是（）。

A: 80 B: 100 C: 240 D: 270 正确答案:

(单选题) 36: 在数据结构中，从逻辑上可以把数据结构分成（）。 A: 动态结构和静态结构 B: 紧凑结构和非紧凑结构

C: 线性结构和非线性结构 D: 内部结构和外部结构 正确答案:

(单选题) 37: 串是一中特殊的线性表，其特殊性体现在（）。 A: 可以顺序存储 B: 数据元素是一个字符 C: 可以链接存储

D: 数据元素可以是多个字符 正确答案:

(单选题) 38: 设某有向图中有n个顶点，则该有向图对应的邻接表中有（）个表头结点。

A: n-1 B: n C: n+1 D: 2n-1 正确答案:

(单选题) 39: 已知某二叉树的后序遍历序列是dabec，中序遍历序列是debac，它的前序遍历序列是（）。A: acbed

B: decab C: deabc D: cedba 正确答案:

(单选题) 40: 进行折半搜索的表必须是顺序存储的有序表。 A: 正确 B: 错误 正确答案:

(单选题) 1: 用链接方式存储的队列，在进行插入运算时(). A: 仅修改头指针 B: 头、尾指针都要修改 C: 仅修改尾指针

D: 头、尾指针可能都要修改 正确答案:

(单选题) 2: 设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（）。

A: O(n) B: O(nlog2n)

(单选题) 3: 设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为（）。A: q=p->next；p->data=q->data；p->next=q->next；free(q)；

B: q=p->next；q->data=p->data；p->next=q->next；free(q)；

C: q=p->next；p->next=q->next；free(q)； D: q=p->next；p->data=q->data；free(q) 正确答案:

(单选题) 4: 设二叉排序树中有n个结点，则在二叉排序树的平均平均查找长度为（）。

A: O(1) B: O(log2n) C: O(n4) D: O(n2 ) 正确答案:

(单选题) 5: 非空的循环单链表head的尾结点（由p所指向）满足（）。

A: p->next= =NULL B: p= =NULL C: p->next= =head D: p= =head 正确答案:

(单选题) 6: 若有18个元素的有序表存放在一维数组A[19]中，第一个元素放A[1]中，现进行二分查找，则查找A［3］的比较序列的下

标依次为( c d )

A: 1，2，3 B: 9，5，2，3 C: 9，5，3 D: 9，4，2，3 正确答案:

(单选题) 7: 设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为（）。

A: BADC B: BCDA C: CDAB D: CBDA 正确答案:

(单选题) 8: 在一非空二叉树的中序遍历序列中，根结点的右边（）。

A: 只有右子树上的所有结点 B: 只有右子树上的部分结点 C: 只有左子树上的部分结点 D: 只有左子树上的所有结点 正确答案:

(单选题) 9: 下面程序的时间复杂为（） for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；}

A: O(n) B: O(n2) C: O(n3) D: O(n4 ) 正确答案:

(单选题) 10: 一个向量（即一批地址连续的存储单元）第一个元素的存储地址是100，每个元素的长度为2，则第5个元素的地址是（）。

A: 110

B: 108 C: 100 A: 2h B: 2h-1 C: 2h+1 D: h+1 正确答案:

(单选题) 12: 线性表是一个具有n个（）的有限序列 A: 表元素 B: 字符 C: 数据元素 D: 数据项 正确答案:

(单选题) 13: 设某无向图有n个顶点，则该无向图的邻接表中有（）个表头结点。

A: 2n B: n C: n/2 D: n(n-1) 正确答案:

(单选题) 14: 判定一个循环队列QU（最多元素为m0, m0= =Maxsize-1）为满队列的条件是（）。

A: ((rear- front)+ Maxsize)% Maxsize = =m0 B: rear-front-1= =m0 C: front= =rear D: front= = rear+1 正确答案:

(单选题) 15: 判定一个循环队列QU（最多元素为m0）为空的条件是（）。

A: rear - front= =m0

B: rear-front-1= =m0 C: front= = rear D: front= = rear+1 正确答案:

(单选题) 16: 数据结构DS(Data Struct)可以被形式地定义为DS=（D，R），其中D是（）有限集合，R是D 上的关系有限集合。

A: 算法 B: 数据元素 C: 数据操作 D: 数据对象 正确答案: