19春北交《数据结构（专）》在线作业二[答案]满分答案
北交《数据结构（专）》在线作业二-0004
试卷总分:100 得分:0
一、 单选题 (共 38 道试题,共 95 分)
1.如果只想得到1024个元素组成的序列中第5个最小元素之前的部分排序的序列，用（ ）方法最快。
A.起泡排序
B.快速排序
C.简单选择排序
D.堆排序
2.设有1000个元素，用折半查找时，最大比较次数是（）。
A.1
B.7
C.10
D.25
3.由两个栈共享一个向量空间的好处是（ ）。
A.减少存取时间，降低下溢发生的机率
B.节省存储空间，降低上溢发生的机率
C.减少存取时间，降低上溢发生的机率
D.节省存储空间，降低下溢发生的机率
4.队列的删除操作是在（ ）进行。
A.队首
B.队尾
C.队前
D.队后
5.在稀疏矩阵的带行指针向量的链接存储中，每个行单链表中的结点都具有相同的（）。
A.行号
B.列号
C.元素值
D.地址
6.设循环队列Q[1..N-1]的头尾指针为F，R，当插入元素时尾指针R加1，头指针F总是指在队列中第一个元素的前一个位置，则队列中元素计数为（）。
A.R-F
B.N-（R-F）
C.（R-F+N）%N
D.（F-R+N）%N
7.某二叉树结点的前序序列为E、A、C、B、D、G、F，中序遍历为A、B、C、D、E、F、G。 该二叉树结点的后序序列为 ( )。
A.B,D,C,A,F,G,E
B.B,D,C,F,A,G,E
C.E,G,F,A,C,D,B
D.E,G,A,C,D,F,B
8.设单链表中指针p指着结点A，若要删除A之后的结点（若存在），则需要修改指针操作为（）。
A.p->next＝p->next->next
B.p＝p->next
C.p＝p->next->next
D.p->next＝p
9.带头节点的单链表 head 为空的判定条件（ ）。
A.head=NULL
B.head->next=NULL
C.head->next=head
D.head!=head
10.线性表的链接实现有利于（）运算。
A.插入
B.读表元
C.查找
D.定位
11.对下面四个序列用快速排序的方法进行排序，以序列的第一个元素为基础进行划分 。 在第一趟划分过程中，元素移动次数最多的序列是 ()。
A.82，75，70，16，10，90，68，23
B.23，10，16，70，82，75，68，90
C.70，75，68，23，10，16，90，82
D.70，75，82，90，23，16，10，68
12.判定一个顺序栈（最多元素为m个）为空的条件是（ ）。
A.top＝＝0
B.top＝＝m
C.top!＝0
D.top!＝m
13.顺序表中逻辑上相邻的节点其物理位置也（ ）。
A.一定相邻
B.不必相邻
C.按某种规律排列
D.无要求
14.设无向图的顶点个数为n，则该图最多有（）条边。
A.n-1
B.n(n-1)/2
C.n(n+1)/2
D.0
15.每次从无序表中取出一个元素，把它插入到有序表中的适当位置，此种排序方法叫做（）排序.
A.插入
B.交换
C.选择
D.归并
16.若让元素1，2，3依次进栈，则出栈次序不可能出现（）种情况。
A.3，2，1
B.2，1，3
C.3，1，2
D.1，3，2
17.具有65个结点的完全二叉树其深度为（）。
A.8
B.7
C.6
D.5
18.图的深度优先遍历类似于二叉树的（ ）。
A.先序遍历
B.中序遍历
C.后序遍历
D.层次遍历
19.若给定的关键字集合为{20，15，14，18，21，36，40，10}，一趟快速排序结束时，键值的排列为( )。
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，21
D.15，10，14，18，20，36，40，21
20.向顺序栈中压入新元素时，应当（ ）。
A.先移动栈顶指针，再存入元素
B.先存入元素，再移动栈顶指针
C.先后次序无关紧要
D.同时进行
21.两个串相等的充分必要条件是（ ）。
A.两个串的长度相等
B.两个串对应位置的字符相等
C.两个串的长度相等且对应位置的字符相同
D.以上条件都不正确
22.二叉树第i层上至多有（）结点。
A.2i
B.2的i次方
C.2i-1
D.2的i-1次方
23.计算机的算法是（ ）。
A.计算方法
B.排序方法
C.对特定问题求解步骤的一种描述
D.调度算法
24.邻接表是图的一种（ ）。
A.顺序存储结构
B.链式存储结构
C.索引存储结构
D.列存储结构
25.从一棵B_树删除元素的过程中，若最终引起树根结点的合并，则新树高度是（ ）。
A.原树高度加1
B.原树高度减1
C.原树高度
D.不确定
26.设有50行60列的二维数组A[50][60]，其元素长度为4字节，按行优先顺序存储，基地址为200，则元素A[18][25]的存储地址为（）。
A.3700
B.4376
C.3900
D.4620
27.由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为（）。
A.23
B.51
C.53
D.74
28.假设一个有n个顶点和e条弧的有向图用邻接表表示,则删除与某个顶点vi相关的所有弧的时间复杂度是()。
A.O(n)
B.O(e)
C.O(n+e)
D.O(n*e)
29.计算机的算法必须具备输入，输出和（ ）五个特性。
A.可行性，可移植性和可扩充性
B.可行性，确定性和有穷性
C.确定性，有穷性和稳定性
D.易读性，稳定性和安全性
30.在一个单链表HL中，若要向表头插入一个由指针p指向的结点，则执行（ ）。
A.HL=p;p->next=HL;
B.p->next=HL;HL=p;
C.p->next=HL;p=HL;
D.p->next=HL->next;HL->next=p;
31.对n个记录的文件进行堆排序，最坏情况下的执行时间为 ( )。
A.O(log2n)
B.O(nlogn)
C.O(n)
D.O(n*n)
32.在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为()。
A.e
B.2e
C.n*n－e
D.n*n－2e
33.对某二叉树进行前序遍历的结果为ABDEFC，中序遍历的结果为DBFEAC，则后序遍历的结果为（ ）。
A.DBFEAC
B.DFEBCA
C.BDFECA
D.BDEFAC
34.设有两个串（S1和S2），求S1在S2中首次出现的位置的运算称为（）。
A.连接
B.模式匹配
C.求子串
D.求串长
35.线性链表不具有的特点是（）。
A.随机访问
B.不必事先估计所需存储空间大小
C.插入与删除时不必移动元素
D.所需空间与线性表长度成正比
36.一个有顺序表有255个对象，采用顺序搜索法查表，平均搜索长度为（ ）。
A.128
B.127
C.126
D.255
