东师13秋《数据结构（高起专）》在线作业答案
东师《数据结构（高起专）》2013秋第一次在线作业试卷总分：100 测试时间：--
一、单选题（共20道试题，共60分。）
1.判断线索二叉树中某结点p有左子女的条件是 ( )。
A. p ! = NULL
B. p->lchild ! = NULL
C. p->ltag = = 0
D. p->ltag = = 1
满分：3分
2.已知一个顺序存储的线性表，设每个结点占c个单元，若第一个结点的地址为LOC(a0)，则第i个结点的地址为 ( )。
A. LOC(a0)+(i-1)*c
B. LOC(a0)+i*c
C. LOC(a0)-i*c
D. LOC(a0)+(i+1)*c
满分：3分
3.有m个叶结点的哈夫曼树所具有的结点数为 ( )。
A. m
B. m+1
C. 2m-1
D. 2m
满分：3分
4.在线索二叉树中，p所指结点没有左子树的充要条件是 ( )。
A. p->lchild = = NULL
B. p->ltag = = 1
C. p->ltag = = 1且p->lchild = = NULL
D. p->ltag = = 0
满分：3分
5.在链队列中，假设f和r分别为队首和队尾指针，则删除一个结点的操作是 ( )。
A. r = f->next;
B. r = r->next;
C. f = f->next;
D. f = r->next;
满分：3分
6.由3个结点可以构造出多少种不同的二叉树？( )
A. 15
B. 21
C. 30
D. 33
满分：3分
7.在k叉树中，度为0的结点称为 ( )。
A. 根
B. 叶
C. 祖先
D. 子孙
满分：3分
8.在n个结点的线索二叉树中线索的数目为 ( )。
A. n-1
B. n
C. n+1
D. 2n
满分：3分
9.下述二叉树中，哪一种满足性质：从任一结点出发到根的路径上所经过的结点序列按其关键字有序。( )
A. 二叉排序树
B. 哈夫曼树
C. AVL树
D. 堆
满分：3分
10.设有两个串s1和s2，求s2在s1中首次出现的位置的运算称为 ( )。
A. 求子串
B. 求串长
C. 联接
D. 模式匹配
满分：3分
11.由3个结点可以构造出多少种不同的有向有序树？( )
A. 9
B. 10
C. 11
D. 12
满分：3分
12.一个顺序栈一旦被说明，其占用空间的大小 ( )。
A. 可以改变
B. 不能固定
C. 已固定
D. 动态变化
满分：3分
13.在一个单链表中，已知q所指结点是p所指结点的前驱结点，若在p之前插入s所指结点，则执行 ( )。
A. p->next = s; s->next = q;
B. s->next = p->next; p->next = s;
C. p->next = s->next; s->next = p;
D. q->next = s; s->next = p;
满分：3分
14.对于3个结点a、b、c，可构成二叉树的不同形态数为 ( )。
A. 3
B. 4
C. 5
D. 6
满分：3分
15.head指向的带表头结点的单链表为空的判定条件是 ( )。
A. head = = NULL
B. head->next = = head
C. head ! = NULL
D. head->next = = NULL
满分：3分
16.单链表的存储密度 ( )。
A. 大于1
B. 等于1
C. 小于1
D. 不能确定
满分：3分
17.在具有n个结点的完全二叉树中，若设根结点的编号为1，则编号为i(i>1)的结点的双亲结点的编号是 ( )。
A. 2i
B. 2i+1
C. i/2
D. 不存在
满分：3分
18.在一个单链表中，在p所指结点之后插入s所指结点，则执行 ( )。
A. s->next = p; p->next = s;
B. s->next = p->next; p->next = s;
C. s->next = p->next; p = s;
D. p->next = s; s->next = p->next;
满分：3分
19.在下列情况中，可称为二叉树的是 ( )。
A. 每个结点至多有两棵子树的树
B. 哈夫曼树
C. 每个结点至多有两棵子树的有序树
D. 每个结点只有一棵右子树
满分：3分
20.每一个(存储)结点不仅含有一个数据元素，还包含一组指针，该存储方式是 ( )。
A. 顺序存储
B. 链接存储
C. 索引存储
D. 散列存储
满分：3分
二、判断题（共20道试题，共40分。）
1.用链表 ( lchild-rchild表示法 ) 存储的包含n个结点的二叉树，结点的2n个指针域中有n + l 个空指针。
A. 错误
B. 正确
满分：2分
2.任何一棵二叉树都可以不用栈实现前序线索二叉树的前序遍历。
A. 错误
B. 正确
满分：2分
3.二叉树的遍历结果不是唯一的。
A. 错误
B. 正确
满分：2分
4.对于插入、删除运算来说，链接存储结构一定优于顺序存储结构。
A. 错误
B. 正确
满分：2分
5.哈夫曼树的结点个数不能是偶数。
A. 错误
B. 正确
满分：2分
6.链表中的表头指针与表头结点起到相同的作用。
A. 错误
B. 正确
满分：2分
7.二叉树的中序遍历序列中，任意一个结点均处在其右子女结点( 若存在 )的前面。
A. 错误
B. 正确
满分：2分
8.二叉树的前序遍历序列中，任意一个结点均处在其子女结点( 若存在 )的前面。
A. 错误
B. 正确
满分：2分
9.给定一棵树，可以找到唯一的一棵二叉树与之对应。
A. 错误
B. 正确
满分：2分
10.数据的存储(物理)结构是指数据在计算机内的实际存储形式。
A. 错误
B. 正确
满分：2分
11.两个串相等的充分必要条件是两个串的长度相等且对应位置的字符相同。
A. 错误
B. 正确
满分：2分
12.数据的逻辑结构说明数据元素之间的顺序关系，它依赖于计算机的存储结构。
A. 错误
B. 正确
满分：2分
13.二叉树的叶结点，在前序遍历、中序遍历和后序遍历下皆以相同的相对位置出现。
A. 错误
B. 正确
满分：2分
14.空串与空格串是相同的。
A. 错误
B. 正确
满分：2分
15.若输入序列为1, 2, 3, 4, 5, 6，则通过一个栈可以输出序列1, 5, 4, 6, 2, 3。
A. 错误
B. 正确
满分：2分
16.顺序存储方式只能用于存储线性结构。
A. 错误
B. 正确
满分：2分
17.循环队列也存在空间溢出问题。
A. 错误
B. 正确
满分：2分
18.一棵树中的叶子数一定等于与其对应的二叉树的叶子数。
A. 错误
B. 正确
满分：2分
19.链接存储结构属静态存储方式。
A. 错误
B. 正确
满分：2分
20.中序遍历二叉链表存储的二叉树时，一般要用堆栈；中序遍历中序线索二叉树时，也必须使用堆栈。
东师《数据结构（高起专）》2013秋第二次在线作业
试卷总分：100 测试时间：--
一、单选题（共20道试题，共60分。）
1.广义表A=(a, b, ( c, d ) , (e，( f , g ) ) )，则式子head ( tail ( head ( tail ( tail ( A ) ) ) ) )的值为 ()。
A. ( g )
B. ( d )
C. c
D. d
满分：3分
2.在排序方法中，从未排序序列中依次取出元素与已排序序列中的元素进行比较，将其放入已排序序列的正确位置上的方法，称为 ()。
A. 直接选择排序
B. 冒泡排序
C. 直接插入排序
D. 希尔排序
满分：3分
3.将一个A 的三对角矩阵，按行优先次序存入一维数组B 中，A中元素A 在数组B中的位置K为 () 。
A. 193
B. 195
C. 197
D. 199
满分：3分
4.下列说法不正确的是 ()。
A. 图的遍历是从给定的源点出发每个顶点仅被访问一次
B. 遍历的基本方法有两种：深度优先遍历和广度优先遍历
C. 图的深度优先遍历不适用于有向图
D. 图的深度优先遍历是一个递归过程
满分：3分
5.设有100个关键字，用折半查找法进行查找时，最大比较次数为 ()。
A. 6
B. 7
C. 25
D. 50
满分：3分
6.设二维数组A按行优先顺序存储且每个元素占c个单元，则元素A的地址为 ()。
A. LOC(A) + (j*m+i)*c
B. LOC(A) + (i*n+j)*c
C. LOC(A) + [(j-1)*m+i-1]*c
D. LOC(A) + [(i-1)*n+j-1]*c
满分：3分
7.排序趟数与序列的原始状态有关的排序方法是 () 排序法。
A. 直接插入
B. 直接选择
C. 冒泡
D. 归并
满分：3分
8.一个有向无环图的拓扑排序序列 () 是唯一的。
A. 一定
B. 不一定
C. 可能
D. 三者均不对
满分：3分
9.下列四个序列中，哪一个是堆 () 。
A. 75 , 65 , 30 , 15 , 25 , 45 , 20 , 10
B. 75 , 65 , 45 , 10 , 30 , 25 , 20 , 15
C. 75 , 45 , 65 , 30 , 15 , 25 , 20 , 10
D. 75 , 45 , 65 , 10 , 25 , 30 , 20 , 15
满分：3分
10.在有向图G的拓扑序列中，若顶点Vi在Vj之前，则下列情形不可能出现的是 () 。
A. G中有弧＜Vi , Vj >
B. G中有一条从Vi到Vj 的路径
C. G中没有弧＜Vi , Vj >
D. G中有一条从Vj到Vi 的路径
满分：3分
11.广义表 (( a , b , c , d ) ) 的表头是 ()。
A. a
B. ( )
C. ( a , b , c , d )
D. ( b , c , d )
满分：3分
12.广义表 (( a , b , c , d ) ) 的表尾是 ()。
A. a
B. ( )
C. ( a , b , c , d )
D. ( b , c , d )
满分：3分
13.折半查找要求结点 ()。
A. 无序、顺序存储
B. 无序、链接存储
C. 有序、顺序存储
D. 有序、链接存储
满分：3分
14.分块查找要求表中的结点 ()。
A. 全部无序
B. 块之间无序
C. 全部有序
D. 块之间有序
满分：3分
15.设有100个关键字，用折半查找法进行查找时，最小比较次数为 ()。
A. 7
B. 4
C. 2
D. 1
满分：3分
16.求顶点间的最短路径问题，考虑的是下面的哪一种图 ()。
A. 无向图
B. 有向图
C. 带权的无向图
D. 带权的有向图
满分：3分
17.设有一个10阶的对称矩阵A，采用压缩存储方式，以行序为主存储，a11为第一个元素，其存储地址为100，每个元素占一个地址空间，则a 85的地址为 ()。
A. 112
B. 132
C. 118
D. 140
满分：3分
18.散列函数有一个共同的性质，即函数值应当以下面的哪一项来取其值域的每个值 ()。
A. 同等概率
B. 最大概率
C. 最小概率
D. 平均概率
满分：3分
19.对于二维数组A，数组的起始位置LOC(A)=1000，元素长度为2，则LOC(A)为()。
A. 1000
B. 1010
C. 1008
D. 1020
满分：3分
20.采用邻接表存储的图的深度优先遍历类似于二叉树的 ()。
A. 前序遍历
B. 中序遍历
C. 后序遍历
D. 层次遍历
满分：3分
二、判断题（共20道试题，共40分。）
1.对n个记录的文件进行堆排序，最坏情况下的执行时间是O(nlog2n )。
A. 错误
B. 正确
满分：2分
2.最佳二叉排序树是AVL树 ( 平衡二叉排序树 ) 。
A. 错误
B. 正确
满分：2分
3.从逻辑结构上看，n维数组的每个元素均属于n个向量。
A. 错误
B. 正确
满分：2分
4.对大小均为n的有序表和无序表分别进行顺序查找，在等概率查找的情况下，对于查找成功，它们的平均查找长度是相同的，而对于查找失败，它们的平均查找长度是不同的。
A. 错误
B. 正确
满分：2分
5.折半插入排序所需比较次数与待排序记录的初始排列状态无关。
A. 错误
B. 正确
满分：2分
6.需要借助于一个队列来实现DFS算法。
A. 错误
B. 正确
满分：2分
7.哈希表与哈希文件的唯一区别是哈希文件引入了“桶”的概念。
A. 错误
B. 正确
满分：2分
8.文件是记录的集合，每个记录由一个或多个数据项组成，因而一个文件可看作由多个记录组成的数据结构。
A. 错误
B. 正确
满分：2分
9.连通分量是无向图中的极大连通子图。
A. 错误
B. 正确
满分：2分
10.对一棵二叉排序树按前序方法遍历得到的结点序列是从小到大的序列。
A. 错误
B. 正确
满分：2分
11.哈希法(散列法)的平均查找长度不随表中结点数目的增加而增加，而是随负载因子的增大而增大。
A. 错误
B. 正确
满分：2分
12.对磁带机而言，ISAM是一种方便的文件组织方法。
A. 错误
B. 正确
满分：2分
13.对处理大量数据的外存介质而言，索引顺序存取方法是一种方便的文件组织方法。
A. 错误
B. 正确
满分：2分
14.归并排序的辅助存储空间代价为O(1 )。
A. 错误
B. 正确
满分：2分
15.若哈希表(散列表)的负载因子α < l，则可避免冲突的产生。
A. 错误
B. 正确
满分：2分
16.在执行某个排序算法过程中，出现了排序码朝着它最终排序位置相反的方向移动，则该算法是不稳定的。
A. 错误
B. 正确
满分：2分
17.对n个记录的文件进行直接插入排序，最好情况下的执行时间是O(n)。
A. 错误
B. 正确
满分：2分
18.在待排数据基本有序的情况下，快速排序效果最好。
A. 错误
B. 正确
满分：2分
19.AOV网的含义是以顶点表示活动的网。
A. 错误
B. 正确
满分：2分
20.需要借助于一个栈来实现DFS算法。
A. 错误
B. 正确
满分：2分
页:
[1]