|
|
东北大学14春学期《数据结构Ⅰ》在线作业1
试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.
设p指向单链表中的一个结点，s指向待插入的结点，则下述程序段的功能是
s -> next = p -> next; p -> next = s;
t = p -> data; p -> data = s -> data; s ->data = t;
A. 结点p与结点s的数据域互换
B. 在p所指结点的元素之前插入元素
C. 在p所指结点的元素之后插入元素
D. 在结点p之前插入结点s
满分：5分
2.
BFS算法可用来解决单源最短路径问题的条件是当各边上的权值
A.
均相等
B. 均互不相等
C.
不一定相等
D. 任意值
满分：5分
3.
在头指针为head且表长大于1的单循环链表中，指针p指向表中某个结点，若p->next->next=
head,则
A. p指向头结点
B. p指向尾结点
C. p的直接后继是头结点
D. P的直接后继是尾结点
满分：5分
4.
抽象数据类型的三个组成部分分别为
A. 数据对象、数据关系和基本操作
B. 数据元素、逻辑结构和存储结构
C. 数据项、数据元素和数据类型
D. 数据元素、数据结构和数据类型
满分：5分
5.
在单链表中，指针p指向元素为x的结点，实现“删除x的后继”的语句是
A. p=p->next;
B. p->next=p->next->next;
C. p->next=p;
D. p=p->next->next;
满分：5分
6.
引入二叉线索树的目的是
A. 加快查找结点的前驱或后继的速度
B. 为了能在二叉树中方便的进行插入与删除
C. 为了能方便的找到双亲
D. 使二叉树的遍历结果唯一
满分：5分
7.
已知一棵树的前序序列为ABCDEF，后序序列为CEDFBA，则对该树进行层次遍历得到的序列为
A. ABCDEF
B. ABCEFD
C. ABFCDE
D. ABCDFE
满分：5分
8.
算法分析的目的是
A. 辨别数据结构的合理性
B. 评价算法的效率
C. 研究算法中输入与输出的关系
D. 鉴别算法的可读性
满分：5分
9.
下面关于线性表的叙述中，错误的是
A.
线性表采用顺序存储，必须占用一片连续的存储单元。
B.
线性表采用顺序存储，便于进行插入和删除操作。
C.
线性表采用链接存储，不必占用一片连续的存储单元。
D.
线性表采用链接存储，便于插入和删除操作。
满分：5分
10.
可有效提高次关键字查找效率的文件是
A. 顺序文件
B. 倒排文件
C. 散列文件
D. VSAM文件
满分：5分
11.
某带头结点的单链表的头指针为head，判定该链表为非空的条件是
A. head==NULL
B. head->next==NULL
C. head!=NULL
D. head->next!=NULL
满分：5分
12.
一棵完全二叉树上有1001个结点，其中叶子结点的个数是
A. 250
B. 500
C. 254
D. 以上答案都不对
满分：5分
13.
已知输入序列为abcd 经过输出受限的双向队列后能得到的输出序列有
A. dacb
B. cadb
C. bdac
D. 以上答案都不对
满分：5分
14.
下面哪一方法可以判断出一个有向图是否有回路
A.
深度优先遍历
B. 求关键路径
C.
求最短路径
D. A和C
满分：5分
15.
用二叉链表表示具有n个结点的二叉树时，值为空的指针域的个数为
A. n-1
B. n
C. n+1
D. 2n
满分：5分
16.
假设以数组A[m]存放循环队列的元素。已知队列的长度为length，指针rear指向队尾元素的下一个存储位置，则队头元素所在的存储位置为
A. (rear-length+m+1)％m
B. (rear-length+m)％m
C. (rear-length+m-1)％m
D. (rear-length)％m
满分：5分
17.
若将数据结构形式定义为二元组(K，R)，其中K是数据元素的有限集合，则R是K上
A. 操作的有限集合
B. 映象的有限集合
C. 类型的有限集合
D. 关系的有限集合
满分：5分
18.
十字链表的三元组表是稀疏矩阵的一种
A. 顺序存储结构
B. 链式存储结构
C. 索引存储结构
D. 散列存储结构
满分：5分
19.
连通网的最小生成树是其所有生成树中
A. 顶点集最小的生成树
B. 边集最小的生成树
C. 顶点权值之和最小的生成树
D. 边的权值之和最小的生成树
满分：5分
20.
下列查找算法中，平均查找长度与元素个数n不直接相关的查找方法是
A. 分块查找
B. 顺序查找
C. 二分查找
D. 散列查找
14春学期《数据结构Ⅰ》在线作业2
试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.
下列关键字序列中，构成小根堆的是
A.
{84，46，62，41，28，58，15，37}
B.
{84，62，58，46，41，37，28，15}
C.
{15，28，46，37，84，41，58，62}
D.
{15，28，46，37，84，58，62，41}
满分：5分
2.
在一个单链表中，若删除*p结点的后继结点，则执行操作
A. q=p->next;p->next=q->next;free(q);
B. p=p->next;p->next=p->next->next;free(p);
C. p->next=q->next;free(p->next);
D. p=p->next->next;free(p->next);
满分：5分
3.
以下数据结构中，属于线性结构的是
A.
广义表
B. 二叉树
C. 稀疏矩阵
D. 串
满分：5分
4.
上溢现象通常出现在
A.
顺序栈的入栈操作过程中
B. 顺序栈的出栈操作过程中
C.
链栈的入栈操作过程中
D. 链栈的出栈操作过程中
满分：5分
5.
对长度为n的关键字序列进行堆排序的空间复杂度为
A.
O（log2n）
B. O（1）
C.
O（n）
D. O（n*log2n）
满分：5分
6.
栈和队列都是
A. 限制存取位置的线性结构
B. 顺序存储的线性结构
C. 链式存储的线性结构
D. 限制存取位置的非线性结构
满分：5分
7.
为使平均查找长度达到最小,当由关键字集合{05,11,21,25,37,40,41,62,84}构建二叉排序树时,第一个插入的关键字应为
A. 05
B. 37
C. 41
D. 62
满分：5分
8.
一个含n个顶点和e条弧的有向图以邻接矩阵表示法为存储结构，则计算该有向图中某个顶点出度的时间复杂度为
A. O(n)
B. O(e)
C. O(n+e)
D. O(n2)
满分：5分
9.
某带头结点的单链表的头指针为head，判定该链表为非空的条件是
A. head==NULL
B. head->next==NULL
C. head!=NULL
D. head->next!=NULL
满分：5分
10.
顺序存储设计时，存储单元的地址
A.
一定连续
B. 一定不连续
C. 不一定连续
D. 部分连续，部分不连续
满分：5分
11.
在待排关键字序列基本有序的前提下，效率最高的排序方法是
A.
直接插入排序
B. 快速排序
C.
直接选择排序
D. 归并排序
满分：5分
12.
无向图中一个顶点的度是指图中
A. 通过该顶点的简单路径数
B. 与该顶点相邻接的顶点数
C. 通过该顶点的回路数
D. 与该顶点连通的顶点数
满分：5分
13.
n个顶点的强连通图中至少含有
A. n-1条有向边
B. n条有向边
C. n(n-1)/2条有向边
D. n(n-1)条有向边
满分：5分
14.
某二叉树的先序序列和后序序列正好相反，则该二叉树的特点一定是
A. 空或只有一个结点
B. 高度等于其结点数
C. 任一结点无左孩子
D. 任一结点无右孩子
满分：5分
15.
在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是
A.
G中有弧<Vi，Vj>
B. G中有一条从Vi到Vj的路径
C. G中没有弧<Vi,Vj>
D. G中有一条从Vj到Vi的路径
满分：5分
16.设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为
A. 4
B. 5
C. 6
D. 7
满分：5分
17.
设哈希表长为14，哈希函数H(key)=key％11，表中已有数据的关键字为15，38，61，84，四个，现将关键字为49的结点加到表中，用二次探测再散列法解决冲突，则放入的位置是
A. 8
B. 3
C. 5
D. 9
满分：5分
18.
树的先根序列等同于与该树对应的二叉树的
A. 先序序列
B. 中序序列
C. 后序序列
D. 层序序列
满分：5分
19.
在下列各种文件中，不能进行顺序查找的文件是
A. 顺序文件
B. 索引文件
C. 散列文件
D. 多重表文件
满分：5分
20.
. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为
A. X的双亲
B. X的右子树中最左的结点
C. X的左子树中最右结点
D. X的左子树中最右叶结点
14春学期《数据结构Ⅰ》在线作业3
试卷总分：100 测试时间：--
一、单选题（共20道试题，共100分。）
1.
在长度为n的顺序表中删除第i个元素(1≤i≤n)时，元素移动的次数为
A. n-i+1
B. i
C. i+1
D. n-i
满分：5分
2.
下列程序段 for(i=1;i<=n;i++) A[i,j]=0; 的时间复杂度是
A.
O(1)
B. O(0)
C.
O(1+n)
D. O(n)
满分：5分
3.
含n个关键字的二叉排序树的平均查找长度主要取决于
A. 关键字的个数
B. 树的形态
C. 关键字的取值范围
D. 关键字的数据类型
满分：5分
4.
下面关于数据结构正确的说法是
A. 一种数据类型
B. 数据的存储结构
C. 一组性质相同的数据元素的集合
D. 相互之间存在一种或多种特定关系的数据元素的集合
满分：5分
5.
已知一棵完全二叉树有64个叶子结点，则该树可能达到的最大深度为
A. 7
B. 8
C. 9
D. 10
满分：5分
6.
. 对长度为15的有序顺序表进行二分查找，在各记录的查找概率均相等的情况下，查找成功时所需进行的关键字比较次数的平均值为
A. 39/15
B. 49/15.
C. 51/15
D. 55/15
满分：5分
7.
对关键字序列（5，1，4，3，7，2，8，6）进行快速排序时，以第一个元素5为基准的一次划分的结果为
A.
（1，2，3，4，5，6，7，8）
B. （1，4，3，2，5，7，8，6）
C.
（2，1，4，3，5，7，8，6）
D. （8，7，6，5，4，3，2，1）
满分：5分
8.
除第一层外，满二叉树中每一层结点个数是上一层结点个数的
A. 1/2倍
B. 1倍
C. 2倍
D. 3倍
满分：5分
9.
深度为h的满m叉树的第k层的结点(1=<k=<h)数有
A. mk-1
B. mk-1
C. mh-1
D. mh-1
满分：5分
10.
假设以数组A[n]存放循环队列的元素，其头、尾指针分别为front和rear。若设定尾指针指向队列中的队尾
元素，头指针指向队列中队头元素的前一个位置，则当前存于队列中的元素个数为
A. (rear-front-1)％n
B. (rear-front)％n
C. (front-rear+1)％n
D. (rear-front+n)％n
满分：5分
11.
引入二叉线索树的目的是
A. 加快查找结点的前驱或后继的速度
B. 为了能在二叉树中方便的进行插入与删除
C. 为了能方便的找到双亲
D. 使二叉树的遍历结果唯一
满分：5分
12.
在一棵高度为k的满二叉树中，结点总数为
A. 2k-1
B. 2k
C. 2k-1
D. log2k+1
满分：5分
13.
某带头结点的单链表的头指针为head，判定该链表为非空的条件是
A. head==NULL
B. head->next==NULL
C. head!=NULL
D. head->next!=NULL
满分：5分
14.
已知一组关键字为{25,48,36,72,79,82,23,40,16,35}，其中每相邻两个为有序子序列。对这些子序列进行一趟两两归并的结果是
A.
{25,36,48,72,23,40,79,82,16,35}
B.
{25,36,48,72,16,23,40,79,82,35}
C.
{25,36,48,72,16,23,35,40,79,82}
D.
{16,23,25,35,36,40,48,72,79,82}
满分：5分
15.设有一个顺序栈的入栈序列是a、b、c，则3个元素都出栈的可能不同排列个数为
A. 4
B. 5
C. 6
D. 7
满分：5分
16.
下面的叙述不正确的是
A.
线性表在链式存储时，查找第i个元素的时间同i的值成正比
B. 线性表在链式存储时，查找第i个元素的时间同i的值无关
C. 线性表在顺序存储时，查找第i个元素的时间同i 的值成反比
D. 线性表在顺序存储时，查找第i个元素的时间同i的值无关
满分：5分
17.
链栈与顺序栈相比，比较明显的优点是
A.
插入操作更加方便
B. 删除操作更加方便
C.
不会出现下溢的情况
D. 不会出现上溢的情况
满分：5分
18.
已知一个散列表如图所示，其散列函数为H(key)=key％11，采用二次探查法处理冲突，则下一个插入的关键字49的地址为
012345678910
15386184
A. 2
B. 3
C. 8
D. 9
满分：5分
19.
在有向图G的拓扑序列中，若顶点Vi在顶点Vj之前，则下列情形不可能出现的是
A.
G中有弧<Vi，Vj>
B. G中有一条从Vi到Vj的路径
C. G中没有弧<Vi,Vj>
D. G中有一条从Vj到Vi的路径
满分：5分
20.
. 若X是二叉中序线索树中一个有左孩子的结点，且X不为根，则x的前驱为
A. X的双亲
B. X的右子树中最左的结点
C. X的左子树中最右结点
D. X的左子树中最右叶结点
满分：5分
|
|
