|
|
16春北航《算法与数据结构》在线作业三
一、单选题：
1.设有两个串（S1和S2），求S1在S2中首次出现的位置的运算称为( )。 (满分:4)
A. 连接
B. 模式匹配
C. 求子串
D. 求串长
2.串是任意有限个( ) (满分:4)
A. 符号构成的序列
B. 符号构成的集合
C. 字符构成的序列
D. 字符构成的集合
3.在一个图中，所有顶点的度数之和等于所有边数的( )倍。 (满分:4)
A. 1
B. 2
C. 3
D. 4
4.向顺序栈中压入新元素时，应当( )。 (满分:4)
A. 先移动栈顶指针，再存入元素
B. 先存入元素，再移动栈顶指针
C. 先后次序无关紧要
D. 同时进行
5.设深度为k的二叉树上只有度为0和度为2的节点，则这类二叉树上所含结点总数最少( )个 (满分:4)
A. k+1
B. 2k
C. 2k-1
D. 2k+1
6.栈操作的原则是（ ） (满分:4)
A. 栈顶删除
B. 先进先出
C. 后进先出
D. 栈顶插入
7.对下面四个序列用快速排序的方法进行排序，以序列的第一个元素为基础进行划分 。 在第一趟划分过程中，元素移动次数最多的序列是( )。 (满分:4)
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
8.对于顺序表的优缺点，以下说法错误的是 (满分:4)
A. 无需为表示结点间的逻辑关系而增加额外的存储空间
B. 可以方便地随机存取表中的任一结点
C. 插入和删除运算较方便
D. 由于顺序表要求占用连续的空间，存储分配只能预先进行(静态分配)
9.采用分块查找时,若线性表中共有625个元素,查找每个元素的概率相同,假设采用顺序查找来确定结点所在的块时,每块应分( )个结点最佳 (满分:4)
A. 10
B. 25
C. 6
D. 625
10.设矩阵A是一对称矩阵(aij=aji,1<=i,j<=8)，若每个矩阵元素占3个单元，将其上三角部分（包括对角线）按行序为主序存放在数组B中，B的首地址为1000，则矩阵元素a67的地址为（ ） (满分:4)
A. 1031
B. 1093
C. 1096
D. 1032
11.队列的插入操作是在( )进行。 (满分:4)
A. 队首
B. 队尾
C. 队前
D. 队后
12.设循环队列Q[1..N-1]的头尾指针为F，R，当插入元素时尾指针R加1，头指针F总是指在队列中第一个元素的前一个位置，则队列中元素计数为( )。 (满分:4)
A. R-F
B. N-（R-F）
C. （R-F+N）%N
D. （F-R+N）%N
13.算法分析的目的是( )。 (满分:4)
A. 找出数据结构的合理性
B. 研究算法中的输入和输出的关系
C. 分析算法的效率以求改进
D. 分析算法的易读性和文档性
14.计算机的算法是( )。 (满分:4)
A. 计算方法
B. 排序方法
C. 对特定问题求解步骤的一种描述
D. 调度算法
15.顺序表中逻辑上相邻的节点其物理位置也( )。 (满分:4)
A. 一定相邻
B. 不必相邻
C. 按某种规律排列
D. 无要求
16.线性结构中的一个结点代表一个 (满分:4)
A. 数据元素
B. 数据项
C. 数据
D. 数据结构
17.二分查找和二叉排序树的时间性能( )。 (满分:4)
A. 始终相同
B. 始终不相同
C. 根据情况确定
D. 以上说法均不正确
18.由权值分别为3,6,7,2,5的叶子结点生成一棵哈夫曼树，它的带权路径长度为( )。 (满分:4)
A. 23
B. 51
C. 53
D. 74
19.深度为6的二叉树最多有( )个结点 (满分:4)
A. 64
B. 63
C. 32
D. 31
20.在含n个顶点和e条边的无向图的邻接矩阵中,零元素的个数为( )。 (满分:4)
A. e
B. 2e
C. n的平方－e
D. n的平方－2e
21.对线性表进行二分查找时,要求线性表必须( )。 (满分:4)
A. 以顺序方式存储
B. 以链接方式存储
C. 以顺序方式存储
且结点按关键字有序排序
D. 以链接方式存储
且结点按关键字有序排序
22.在一个无向图中，所有顶点的度数之和等于所有边数的( )倍。 (满分:4)
A. 3
B. 2
C. 1
D. 1/2
23.若从二叉树的任一节点出发到根的路径上所经过的节点序列按其关键字有序，则该二叉树是( )。 (满分:4)
A. 二叉排序树
B. 哈夫曼树
C. 堆
D. AVL树
24.对有n个记录的有序表采用二分查找，其平均查找长度的量级为（ ） (满分:4)
A. O(log2n)
B. O(nlog2n)
C. O(n)
D. O(n2)
25.顺序队列的人队操作应为 ( ) (满分:4)
A. sq.rear=sq.rear+1 sq.data[sq.rear]=x
B. sq.data[sq.rear]=x sq.rear=sq.rear+1
C. sq.rear=(sq.rear+1)% maxsize; sq.data[sq.rear]=x
D. sq.data[sqrear]=x sq.rear=(sq.rear+1)% maxsize
|
|
