17秋东北大学东大17春学期《数据结构Ⅱ》在线作业3
一、单选题（共 20 道试题，共 100 分。）
1.
n个顶点的强连通图中至少含有
A. n-1条有向边 B. n条有向边 C.
n(n-1)/2条有向边 D.
n(n-1)条有向边 正确答案： 2.
在线性表的下列运算中，不改变数据元素之间结构关系的运算是 A. 插入 B. 删除 C. 排序 D.
查找
正确答案： 3.
如果求一个连通图中以某个顶点为根的高度最小的生成树，应采用
A. 深度优先搜索算法 B. 广度优先搜索算法 C.
求最小生成树的prim算法 D. 拓扑排序算法 正确答案： 4.
已知含10个结点的二叉排序树是一棵完全二叉树，则该二叉排序树在等概率情况下查找成功的平均查找长度等于
A. 1.0 B. 2.9 C.
3.4 D. 5.5
正确答案： 5.
下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是
A. 分块查找 B. 顺序查找 C.
二分查找 D.
散列查找 正确答案： 6.
若某线性表最常用的操作是存取任一指定序号的元素和在最后进行插入和删除运算，则节省时间的存储方式是 A.
顺序表 B. 双链表 C.
带头结点的双循环链表 D.
单循环链表 正确答案： 7.
栈的两种常用存储结构分别为 A.
顺序存储结构和链式存储结构 B.
顺序存储结构和散列存储结构 C.
链式存储结构和索引存储结构 D.
链式存储结构和散列存储结构 正确答案： 8.
连通图是指图中任意两个顶点之间
A. 都连通的无向图 B. 都不连通的无向图
C. 都连通的有向图 D. 都不连通的有向图 正确答案： 9.
一个有向无环图的拓扑排序序列是
A. 一定唯一的 B. 一定不唯一的 C.
不一定唯一的 D. 都不对 正确答案： 10.
下面哪一方法可以判断出一个有向图是否有回路 A.
深度优先遍历 B. 求关键路径 C.
求最短路径 D.
A和C
正确答案： 11.
可有效提高次关键字查找效率的文件是
A. 顺序文件 B. 倒排文件 C.
散列文件 D.
VSAM文件 正确答案： 12.
通常将链串的结点大小设置为大于1是为了 A.
提高串匹配效率
B.
提高存储密度 C.
便于插入操作 D.
便于删除操作 正确答案： 13.
在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是
A. p=p->next; B. p->next=p->next->next; C.
p->next=p; D.
p=p->next->next; 正确答案： 14.
已知一棵含50个结点的二叉树中只有一个叶子结点，则该树中度为1的结点个数为 A. 0 B. 1 C. 48 D. 49
正确答案： 15.
ISAM文件和VSAM文件的区别之一是
A. 前者是索引顺序文件，后者是索引非顺序文件 B.
前者只能进行顺序存取，后者只能进行随机存取 C.
前者建立静态索引结构，后者建立动态索引结构 D.
前者的存储介质是磁盘，后者的存储介质不是磁盘 正确答案： 16.
对关键字序列(56，23，78，92，88，67，19，34)进行增量为3的一趟希尔排序的结果为 A.
(19，23，56，34，78，67，88，92)
B.
(23，56，78，66，88，92，19，34) C.
(19，23，34，56，67，78，88，92) D.
(19，23，67，56，34，78，92，88) 正确答案： 17.
无向图中一个顶点的度是指图中
A. 通过该顶点的简单路径数 B. 与该顶点相邻接的顶点数
C. 通过该顶点的回路数 D. 与该顶点连通的顶点数 正确答案： 18.
下列说法正确的是
(1)二又树按某种方式线索化后，任一节点均有指向前趋和后继的线索 (2)二叉树的前序遍历序列中，任意一个节点均处于在子孙节点前 (3)二叉排序树中任一节点的值大于其左孩子的值，小于右孩子的值 A.
(1)(2)(3) B.
(1)(2) C.
(1)(3) D.
前面的可选答案都不对 正确答案： 19.
对二叉树从1开始进行连续编号，要求每个结点的编号大于其左右孩子的编号，同一个结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用遍历方式是
A. 先序 B. 中序
C. 后序
D. 从根开始的层次遍历 正确答案： 20.
在一个单链表中，已知q结点是p结点的前驱结点，若在q 和p之间插入结点s，则执行操作
A. s->next=p->next;p->next=s; B. s->next=p; q->next=s C.
q->next=s;s->next=p; D.
p->next=s;s->next=q; 正确答案：