数据结构2016秋天大在线作业
《数据结构》在线作业二一、单选题：
1.设有n个关键字具有相同的Hash函数值，则用线性探测法把这n个关键字映射到HASH表中需要做( )次线性探测。 (满分:2.5)
A. n2
B. n(n+1)
C. n(n+1)/2
D. n(n-1)/2
2.对于一个具有n个顶点和e条边的无向图，若采用邻接表表示，则所有邻接表中的接点总数是( )。 (满分:2.5)
A. e/2
B. e
C. 2e
D. n+e
3.具有4个顶点的无向完全图有( )条边。 (满分:2.5)
A. 6
B. 12
C. 16
D. 20
4.顺序查找法适合于存储结构为( )的线性表。 (满分:2.5)
A. 散列存储
B. 顺序存储或链接存储
C. 压缩存储
D. 索引存储
5.设一组初始记录关键字序列为(60，80，55，40，42，85)，则以第一个关键字45为基准而得到的一趟快速排序结果是( )。 (满分:2.5)
A. 40，42，60，55，80，85
B. 42，45，55，60，85，80
C. 42，40，55，60，80，85
D. 42，40，60，85，55，80
6.在一个有向图中，所有顶点的入度之和等于所有顶点的出度之和的( )倍。 (满分:2.5)
A. 1/2
B. 1
C. 2
D. 4
7.设一个顺序有序表A中有14个元素，则采用二分法查找元素A的过程中比较 元素的顺序为( )。 (满分:2.5)
A. A，A，A，A
B. A，A，A，A
C. A，A，A，A
D. A，A ，A，A
8.不含任何结点的空树( )。 (满分:2.5)
A. 是一棵树
B. 是一棵二叉树
C. 是一棵树也是一棵二叉树
D. 既不是树也不是二叉树
9.用某种排序方法对线性表（ 25，84，21，47，15，27，68，35，20）进行排序时，元素序列的变化情况如下：⑴ 25，84，21，47，15，27，68，35，20；⑵ 20，15，21，25，47，27，68，35，84；⑶ 15，20，21，25，35，27，47，68，84；⑷ 15，20，21，25，27，35，47，68，84。则所采用的排序方法是( )。 (满分:2.5)
A. 选择排序
B. 希尔排序
C. 归并排序
D. 快速排序
10.设顺序线性表中有n个数据元素，则删除表中第i个元素需要移动( )个元素。 (满分:2.5)
A. n-i
B. n+l -i
C. n-1-i
D. i
11.设一组初始记录关键字序列为(Q，H，C，Y，P，A，M，S，R，D，F，X)，则按字母升序的第一趟冒泡排序结束后的结果是( )。 (满分:2.5)
A. F，H，C，D，P，A，M，Q，R，S，Y，X
B. P，A，C，S，Q，D，F，X，R，H，M，Y
C. A，D，C，R，F，Q，M，S，Y，P，H，X
D. H，C，Q，P，A，M，S，R，D，F，X，Y
12.快速排序方法在( )情况下最不利于发挥其长处。 (满分:2.5)
A. 要排序的数据量太大
B. 要排序的数据中含有多个相同值
C. 要排序的数据已基本有序
D. 要排序的数据个数为奇数
13.设有向无环图G中的有向边集合E={，，，}，则下列属于该有向图G的一种拓扑排序序列的是( )。 (满分:2.5)
A. 1，2，3，4
B. 2，3，4，1
C. 1，4，2，3
D. 1，2，4，3
14.采用二分查找方法查找长度为n的线性表时，每个元素的平均查找长度为( )。 (满分:2.5)
A. O（n2）
B. O(nlog2n)
C. O(n)
D. O(log2n)
15.设一组权值集合W=(15，3，14，2，6，9，16，17)，要求根据这些权值集合构造一棵哈夫曼树，则这棵哈夫曼树的带权路径长度为( )。 (满分:2.5)
A. 129
B. 219
C. 189
D. 229
16.下列各种排序算法中平均时间复杂度为O(n2 )是( )。 (满分:2.5)
A. 快速排序
B. 堆排序
C. 归并排序
D. 冒泡排序
17.散列表的平均查找长度( )。 (满分:2.5)
A. 与处理冲突方法有关而与表的长度无关
B. 与处理冲突方法无关而与表的长度有关
C. 与处理冲突方法有关而与表的长度有关
D. 与处理冲突方法无关而与表的长度无关
18.在所有排序方法中，关键字比较的次数与记录的初始排列次序无关的是( )。 (满分:2.5)
A. 希尔排序
B. 起泡排序
C. 插入排序
D. 选择排序
19.设一棵完全二叉树中有65个结点，则该完全二叉树的深度为( )。 (满分:2.5)
A. 8
B. 7
C. 6
D. 5
20.下述几种排序方法中，平均查找长度最小的是( )。 (满分:2.5)
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
21.设一组初始记录关键字的长度为8，则最多经过( )趟插入排序可以得到有序序列。 (满分:2.5)
A. 6
B. 7
C. 8
D. 9
22.树最适合用来表示( )。 (满分:2.5)
A. 有序数据元素
B. 无序数据元素
C. 元素之间具有分支层次关系的数据
D. 元素之间无联系的数据
23.采用顺序查找方法查找长度为n的线性表时，每个元素的平均查找长度为( ). (满分:2.5)
A. n
B. n/2
C.(n+1)/2
D.(n-1)/2
24.设指针变量p指向双向链表中结点A，指针变量s指向被插入的结点X，则在结点A的后面插入结点X的操作序列为( )。 (满分:2.5)
A. p->right=s； s->left=p； p->right->left=s； s->right=p->right；
B. s->left=p；s->right=p->right；p->right=s； p->right->left=s；
C. p->right=s； p->right->left=s； s->left=p； s->right=p->right；
D. s->left=p；s->right=p->right；p->right->left=s； p->right=s；
25.设一棵三叉树中有2个度数为1的结点，2个度数为2的结点，2个度数为3的结点， 则该三叉链权中有( )个度数为0的结点。 (满分:2.5)
A. 5
B. 6
C. 7
D. 8
26.堆的形状是一棵( )。 (满分:2.5)
A. 二叉排序树
B. 满二叉树
C. 完全二叉树
D. 平衡二叉树
27.下述几种排序方法中，要求内存量最大的是( )。 (满分:2.5)
A. 插入排序
B. 选择排序
C. 快速排序
D. 归并排序
28.设输入序列1、2、3、?、n经过栈作用后，输出序列中的第一个元素是n，则输出序列中的第i个输出元素是( )。 (满分:2.5)
A. n-i
B. n-1-i
C. n+l -i
D. 不能确定
29.有一个有序表为{1，3，9，12，32，41，45，62，75，77，82，95，100}，当二分查找值82为的结点时，( )次比较后查找成功。 (满分:2.5)
A. 1
B. 2
C. 4
D. 8
30.设哈希表长m=14，哈希函数H(key)=key%11。表中已有4个结点：addr(15)=4;addr(38)=5;addr(61)=6;addr(84)=7，如用二次探测再散列处理冲突，关键字为49的结点的地址是( )。 (满分:2.5)
A. 8
B. 3
C. 5
D. 9
31.设带有头结点的单向循环链表的头指针变量为head，则其判空条件是( )。 (满分:2.5)
A. head==0
B. head->next==0
C. head->next==head
D. head!=0
32.对于一个有向图，若一个顶点的入度为k1,、出度为k2，则对应逆邻接表中该顶点单链表中的结点数为( )。 (满分:2.5)
A. k1
B. k2
C. k1-k2
D. k1+k2
33.在一个图中，所有顶点的度数之和等于所有边数的( )倍。 (满分:2.5)
A. 1/2
B. 1
C. 2
D. 4
34.设指针变量top指向当前链式栈的栈顶，则删除栈顶元素的操作序列为( )。 (满分:2.5)
A. top=top+1;
B. top=top-1;
C. top->next=top;
D. top=top->next;
35.设顺序线性表的长度为30，分成5块，每块6个元素，如果采用分块查找，则其平均查找长度为( )。 (满分:2.5)
A. 6
B. 11
C. 5
D. 6.5
36.设指针q指向单链表中结点A，指针p指向单链表中结点A的后继结点B，指针s指向被插入的结点X，则在结点A和结点B插入结点X的操作序列为( )。 (满分:2.5)
A. s->next=p->next；p->next=-s；
B. q->next=s； s->next=p；
C. p->next=s->next；s->next=p；
D. p->next=s；s->next=q；
37.下面不正确的说法是( )。 (满分:2.5)
A. 在AOE网中，减小一个关键活动上的权值后，整个工期也就相应减小
B. AOE网工程工期为关键活动上的权之和
C. 在关键路径上的活动都是关键活动，而关键活动也必在关键路径上
D. 以上都不对
38.设数据结构A=(D，R)，其中D={1，2，3，4}，R={r}，r={，，，}，则数据结构A是（?）。 (满分:2.5)
A. 线性结构
B. 树型结构
C. 图型结构
D. 集合
39.一组记录的关键码为（46，79，56，38，40，84），则利用快速排序的方法，以第一个记录为基准得到的一次划分结果为( )。 (满分:2.5)
A. 38，40，46，56，79，84
B. 40，38，46，79，56，84
C. 40，38，46，56，79，84
D. 40，38，46，84，56，79
40.( )二叉排序树可以得到一个从小到大的有序序列。 (满分:2.5)
A. 先序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
《数据结构》在线作业一
一、单选题：
1.栈结构通常采用的两种存储结构是( )。 (满分:2.5)
A. 顺序存储结构和链式存储结构
B. 散列方式和索引方式
C. 链表存储结构和数组
D. 线性存储结构和非线性存储结构
2.假定在一棵二叉树中，双分支结点数为15，单分支结点数为30个，则叶子结点数为( )个。 (满分:2.5)
A. 15
B. 16
C. 17
D. 47
3.二叉树的第k层的结点数最多为( ). (满分:2.5)
A. 2k-1
B. 2K+1
C. 2K-1
D. 2k-1
4.串是一中特殊的线性表，其特殊性体现在( )。 (满分:2.5)
A. 可以顺序存储
B. 数据元素是一个字符
C. 可以链接存储
D. 数据元素可以是多个字符
5.带头结点的单链表head为空的判定条件是( )。 (满分:2.5)
A. head= =NULL
B. head->next= =NULL
C. head->next= =head
D. head!=NULL
6.一个栈的入栈序列a，b，c，d，e，则栈的不可能的输出序列是( )。 (满分:2.5)
A. edcba
B. decba
C. dceab
D. abcde
7.设高度为h的二叉树上只有度为0和度为2的结点，则此类二叉树中所包含的结点数至少为( )。 (满分:2.5)
A. 2h
B. 2h-1
C. 2h+1
D. h+1
8.如果某二叉树的前根次序遍历结果为stuwv，中序遍历为uwtvs，那么该二叉树的后序为( )。 (满分:2.5)
A. uwvts
B. vwuts
C. wuvts
D. wutsv
9.在用循环单链表表示的链式队列中，可以不设队头指针，仅在链尾设置队尾指针。 (满分:2.5)
A. 正确
B. 错误
10.设串s1='ABCDEFG'，s2='PQRST'，函数con(x,y)返回x和y串的连接串，subs(s,i,j)返回串s的从序号i的字符开始的j个字符组成的子串，len(s)返回串s的长度，则con(subs(s1,2,len(s2)),subs(s1,len(s2),2))的结果串是( )。 (满分:2.5)
A. BCDEF
B. BCDEFG
C. BCPQRST
D. BCDEFEF
11.在双向循环链表的p所指结点之后插入s所指结点的操作是( )。 (满分:2.5)
A. p->right=s;s->left=p;p->right->left=s;s->right=p->right;
B. p->right=s;p->right->left=s;s->left=p;s->right=p->right;
C. s->left=p;s->right=p->right;p->right=s;p->right->left=s;
D. s->left=p;s->right=p->right;p->right->left=s;p->right=s;
12.以下数据结构中哪一个是非线性结构？( ) (满分:2.5)
A. 队列
B. 栈
C. 线性表
D. 二叉树
13.若有18个元素的有序表存放在一维数组A中，第一个元素放A中，现进行二分查找，则查找A［3］的比较序列的下标依次为( c d) (满分:2.5)
A. 1，2，3
B. 9，5，2，3
C. 9，5，3
D. 9，4，2，3
14.下面程序的时间复杂为( )for（i=1，s=0； i<=n； i++） {t=1；for(j=1；j<=i；j++) t=t*j；s=s+t；} (满分:2.5)
A. O(n)
B. O(n2)
C. O(n3)
D. O(n4 )
15.设一组初始记录关键字序列(5，2，6，3，8)，以第一个记录关键字5为基准进行一趟快速排序的结果为( )。 (满分:2.5)
A. 2，3，5，8，6
B. 3，2，5，8，6
C. 3，2，5，6，8
D. 2，3，6，5，8
16.深度为5的二叉树至多有( )个结点。 (满分:2.5)
A. 16
B. 32
C. 31
D. 10
17.栈和队列的共同特点是( )。 (满分:2.5)
A. 只允许在端点处插入和删除元素
B. 都是先进后出
C. 都是先进先出
D. 没有共同点
18.从一个具有n个结点的单链表中查找其值等于x结点时，在查找成功的情况下，需平均比较( )个结点。 (满分:2.5)
A. n
B. n/2
C.(n-1)/2
D.(n+1)/2
19.非空的循环单链表head的尾结点（由p所指向）满足( )。 (满分:2.5)
A. p->next= =NULL
B. p= =NULL
C. p->next= =head
D. p= =head
20.设无向图的顶点个数为n，则该图最多有( )条边。 (满分:2.5)
A. n-1
B. n(n-1)/2
C. n(n+1)/2
D. 0
21.设一棵二叉树的深度为k，则该二叉树中最多有( )个结点。 (满分:2.5)
A. 2k-1
B. 2k
C. 2k-1
D. 2k -1
22.设无向图G中有n个顶点，则该无向图的最小生成树上有( )条边。 (满分:2.5)
A. n
B. n-1
C. 2n
D. 2n-1
23.设指针变量p指向单链表中结点A，若删除单链表中结点A，则需要修改指针的操作序列为( )。 (满分:2.5)
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)
24.判定一个循环队列QU（最多元素为m0）为空的条件是( )。 (满分:2.5)
A. rear - front= =m0
B. rear-front-1= =m0
C. front= = rear
D. front= = rear+1
25.设某棵二叉树的中序遍历序列为ABCD，前序遍历序列为CABD，则后序遍历该二叉树得到序列为( )。 (满分:2.5)
A. BADC
B. BCDA
C. CDAB
D. CBDA
26.向一个栈顶指针为HS的链栈中插入一个s所指结点时，则执行( )。(不带空的头结点) (满分:2.5)
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;
27.常对数组进行的两种基本操作是( )。 (满分:2.5)
A. 建立与删除
B. 索引和修改
C. 对数据元素的存取和修改
D. 查找与索引
28.在以下的叙述中，正确的是( )。 (满分:2.5)
A. 线性表的顺序存储结构优于链表存储结构
B. 线性表的顺序存储结构适用于频繁插入/删除数据元素的情况
C. 线性表的链表存储结构适用于频繁插入/删除数据元素的情况
D. 线性表的链表存储结构优于顺序存储结构
29.下面关于线性表的叙述错误的是( )。 (满分:2.5)
A. 线性表采用顺序存储必须占用一片连续的存储空间
B. 线性表采用链式存储不必占用一片连续的存储空间
C. 线性表采用链式存储便于插入和删除操作的实现
D. 线性表采用顺序存储便于插入和删除操作的实现
30.在一非空二叉树的中序遍历序列中，根结点的右边( )。 (满分:2.5)
A. 只有右子树上的所有结点
B. 只有右子树上的部分结点
C. 只有左子树上的部分结点
D. 只有左子树上的所有结点
31.数据结构是一门研究非数值计算的程序设计问题中,数据元素的( )、数据信息在计算机中的存储结构以及一组相关的运算等的课程。 (满分:2.5)
A. 操作对象
B. 计算方法
C. 逻辑结构
D. 数据映象
32.按照二叉树的定义，具有3个不同数据结点的不同的二叉树有( )种。 (满分:2.5)
A. 5
B. 6
C. 30
D. 32
33.设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={，，，，，，，}，则数据结构A是( )。 (满分:2.5)
A. 线性结构
B. 树型结构
C. 物理结构
D. 图型结构
34.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在q和p之间插入s结点，则执行( )。 (满分:2.5)
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;
35.若让元素1,2,3,4,5,6依次进栈，则出栈次序不可能出现( )种情况 (满分:2.5)
A. 435612
B. 325641
C. 135426
D. 123546
36.用链接方式存储的队列，在进行插入运算时( ). (满分:2.5)
A. 仅修改头指针
B. 头、尾指针都要修改
C. 仅修改尾指针
D. 头、尾指针可能都要修改
37.判定一个循环队列QU（最多元素为m0, m0= =Maxsize-1）为满队列的条件是( )。 (满分:2.5)
A.((rear- front)+ Maxsize)% Maxsize = =m0
B. rear-front-1= =m0
C. front= =rear
D. front= = rear+1
38.设有n个待排序的记录关键字，则在堆排序中需要( )个辅助记录单元。 (满分:2.5)
A. 1
B. n
C. nlog2n
D. n2
39.设某二叉树中度数为0的结点数为N0，度数为1的结点数为Nl，度数为2的结点数为N2，则下列等式成立的是( )。 (满分:2.5)
A. N0=N1+1
B. N0=Nl+N2
C. N0=N2+1
D. N0=2N1+l
40.设某无向图中有n个顶点e条边，则该无向图中所有顶点的入度之和为( )。 (满分:2.5)
A. n
B. e
C. 2n
D. 2e
**** Hidden Message *****
页:
[1]