71远程数据结构与算法模拟题1
模拟题一、
一单选题
1.数据结构在计算机内存中的表示是指( )。
A. 数据的逻辑结构
B. 数据结构
C. 数据的存储结构
D.数据元素
2. 数据的( )包括集合、线性结构、树形结构和图状结构四种基本类型。
A.逻辑结构和存储结构
B.存储结构
C.逻辑结构
D.物理结构
3. 通常所说的时间复杂度是指( )。
A. 语句的频度和
B. 算法的时间消耗
C. 最坏时间复杂度
D. 渐近时间复杂度
4.线性表的顺序存储结构是通过( )的方式表示元素之间的关系。
A. 后继元素地址
B. 元素的存储顺序
C. 左、右孩子地址
D. 后继元素的数组下标
5. 在顺序栈S中插入元素e时，执行( )。
A. S.top--; *S.top = e;
B. *S.top = e; S.top++;
C. *S.top = e; S.top--;
D. S.top++; *S.top = e;
6. 一个队列的入列序列是1，2，3，4，则队列的输出序列是( )。
A. 4，3，2，1
B. 1，4，3，2
C. 1，2，3，4
D. 3，2，4，1
7. 对于稀疏矩阵的压缩存储只需存储( )。
A. 所有元素
B. 对角线上的元素
C. 零元素
D. 非零元素
8. 对二叉树从1开始编号，要求每个结点的编号大于其左右孩子的编号，同一结点的左右孩子中，其左孩子的编号小于其右孩子的编号，则可采用( )。
A. 从根结点开始的层次遍历
B. 先序遍历
C. 中序遍历
D. 后序遍历
9. 按二叉树的定义，具有3个结点的二叉树一共有( )种。
A. 2
B. 3
C. 4
D. 5
10. 对于具有n个顶点和e条边的有向图，采用邻接表表示，则表头向量的大小为( )。
A. n
B. n+1
C. n-1
D. n+e
11. 连通图的生成树是( )。
A. 极小连通子图
B. 顶点间可以无路径
C. 连通子图
D. 边数为顶点数
12. 快速排序方法在( )情况下最不利于发挥其长处。
A. 被排序数据已基本有序
B. 被排序的数据量太大
C. 被排序数据数目为奇数
D. 被排序数据中含有多个相同值
二填空题
1. ________中任何两个结点之间没有逻辑关系。
2. 在线性表中，一个数据元素可由若干数据项组成，常将此种数据元素称为_______。
3. 在一个单链表中，若删除p所指结点的后继结点，则执行
____________________________________________________________。
4. 栈的表尾称为________。
5. 入队操作要修改________。
6. 广义表是数据元素的有限序列，其元素可以是单个元素，也可以是________。
7. 深度为5的满二叉树的结点数为________。
8. 具有3个结点的树有________种。
9. Prim算法适用于边数较________的图。
10. 遍历是指按某种搜索路径访问二叉树的每个结点，而且每个结点仅被访问______。
11. 对二叉排序树进行________遍历，可以得到该二叉树所有结点构成的有序序列。
12. 具有20个记录的序列，采用起泡排序最多的比较次数为________。
三问答题
1. 请用C语言给出顺序表的类型定义。
2. 数据结构形式定义为(D, S)，其中D = { a，b，c，d，e }，S = { R }，R = {(a, b), (b, c), (c, d), (c, e), (d, e) }，画出其逻辑结构图。
3. 举例说明对相同的逻辑结构，同一种运算在不同的存储方式下实现，其效率不同。
4. 将如下树转换成二叉树。
5. 若某非空二叉树的先序序列和后序序列正好相同，试说明二叉树的形态及原因。
6. 以关键字序列{12，2，16，9，10，8，20}为例，写出执行快速排序算法的各趟排序结束时，关键字序列的状态。
四算法题
1. 下面算法的功能是：在无头结点的线性单链表中插入元素结点，即在第i个位置之前插入新的数据元素e 。请在空缺处填入相应的语句。
Status ListInsert_L(LinkList &L, int i, ElemType e)
{//L是该链表的头指针
if(i==1)
{
s=(LinkList)malloc(sizeof(LNode));
s->data=e;
(1)_________________________;
(2)_________________________;
}
else{ p=L;j=1;
while (p&&j
if(!p||j>i-1)return ERROR;
s=(LinkList)malloc(sizeof(LNode))
s->data=e;
(3)_______________________;
(4)_________________________;
}
return OK;
}
2. 试写出下面操作算法的功能。
void A(LinkList &La, SqList Lb) {
La=(LinkList)malloc(sizeof (LNode));
La->next=NULL;
p=La;
for (i=0; i<=Lb.length-1; i++){
q=(LinkList)malloc(sizeof(LNode));
q->data=Lb.elem[i];
p->next=q;
p=q;
}
q->next=NULL；
}