数据结构模拟题及答案
一、 填空题 （每小题 1 分，共 20 分） ：
1、 栈是一种 _____________的线性表，队列是一种_____________的线性表(要求填特性)。
2、 ___________________是数据的基本单位，可由若干个_______________ 组成，______________是数据的最小单位。
3、 具有 354个结点的完全二叉树深度为 ________________，树中度为1的结点数为______________。
4、 数组的运算有 ______________________________________ 和____________________________。
5、 稀疏矩阵的压缩存储一般采用 _____________________________存储方式。
6、 广义表运算： tail ((( a, b ), ( c , ( d, e )))) =
_______________________ 。
7、 数据结构中评价算法的两个重要指标是 __________ 、
__________ 。
8、 一个算法具有 5个特性: 、 、 ，有零个或多个输入、有一个或多个输出。
9、 已知指针 p指向单链表L中的某结点，则删除其后继结点的语句是: 。
10、 Prim（普里姆）算法适用于求 ______ 的网的最小生成树；
kruskal（克鲁斯卡尔）算法适用于求 ______ 的网的最小生成树。
11、 N个顶点的连通图的生成树含有 ______ 条边。
12、 顺序查找 n个元素的顺序表，若查找成功，则比较关键字的次数最多为 __ __ 次；当使用监视哨时，若查找失败，则比较关键字的次数为_ _ __ 。
13、 若不考虑基数排序，则在内排序过程中，主要进行的两种基本操作是关键字的 __________ 和记录的 _________ 。
1 模拟试卷七
一、单项选择题（在每小题的四个备选答案中，选出一个正确的答案，并将其号码填在题干后的括号内。每小题1分，共10分）
1．假设执行语句S的时间为O（1），则执行下列程序段
for(i=1;i<=n;i++)
for(j=i;j<=n;j++)
S;
的时间为( )
A）O（n） B）O（n2）
C）O（n*i） D）O（n+i）
2．设栈最大长度为3，入栈序列为1，2，3，4，5，6，则不可能的出栈序列是（ ）。
A）1，2，3，4，5，6 B）2，1，3，4，5，6
C）3，4，2，1，5，6 D）4，3，2，1，5，6
3．设单链表的结点结构为(data,next)，已知指针q所指结点是指针p所指结点的直接前驱，如在*q与*p之间插入结点*s，则应执行的操作为（ ）。
A）s->next=p->next; p->next=s; B）q->next=s; s->next=p;
C）p->next=s-next; s->next=p; D）p->next=s; s-next=q;
4．串S='ABC DEF'的串长为（ ）。
A）3 B）4
C）7 D）8
5．下面二叉树按（ ）遍历得到的序列是FEDBIHGCA。
A）先序 B）中序
C）后序 D）层次
6．用Floyd算法求每一对顶点之间的最短路径的时间复杂度为（ ）。
A）O(n) B）O(n2)
C）O(n3) D）O(nlogn)
7．具有n个顶点的无向图，它可能具有的边数的最大值为（ ）。
A）(n2+n)/2 B）n2
C）(n2-n)/2 D）n
8．二分查找法要求被查找的表是（ ）。
数据结构与算法模拟习题（附参考答案）
一、单选题（共86题，每题1分，共86分）
1.具有5个顶点的有向完全图有多少条弧？
A、16
B、20
C、25
D、10
正确答案：B
2.下列程序的时间复杂度为（）。i = 0; s = 0;while(s <
n){i++;s = s + i;}
A、Θ(n)
B、Θ(1)
C、Θ(n2)
D、Θ(n½)
正确答案：D
3.栈和队列的共同点是（ ）。
A、没有共同点
B、只允许在端点处插入和删除元素
C、都是先进后出
D、都是先进先出
正确答案：B
4.下面描述中正确的为( )。
A、线性表的逻辑顺序与物理顺序总是一致的
B、线性表的顺序存储表示优于链式存储表示。
C、线性表若采用链式存储表示时所有结点之间的存储单元地址可连续可不连续。
D、二维数组是其数组元素为线性表的线性表。
正确答案：C
5.对N个不同的数据采用冒泡算法进行从大到小的排序，下面哪种情况下肯定交换元素次数最多？
A、从大到小排好的
B、元素无序
C、元素基本有序 D、从小到大排好的
正确答案：D
6.表达式3*2^(4+2*2-6*3)-5求值过程中当扫描到6时，对象栈和算符栈为（ ），其中^为乘幂 。
A、3, 2, 8；( * ^ -
B、3, 2, 4, 2, 2；( * ^ ( -
C、3, 2, 4, 1, 1；( ^ ( + -
D、3, 2, 8；( * ^ ( -
正确答案：D
7.二叉树的高度若根节点为高度1，一棵具有 1025 个结点的二叉树的高度为 ▁▁▁▁▁ 。
A、10～1024 之间
B、11～1025 之间
C、10
D、11
正确答案：B
8.数据采用链式存储结构时，要求( )
A、每个节点占用一片连续的存储区域
B、所有节点占用一片连续的存储区域
C、节点的最后一个数据域一定是指针类型
D、每个节点有多少个后继就设多少个指针域
正确答案：A
9.在N个结点的顺序表中，算法的时间复杂度为O(1)的操作是：
第一套题
1.下列程序的功能是：用直接插入法对给出的10个数进行由小到大排序，将哨兵放在r[n]中，被排序的数字放在r[0..n-1]中。请改正程序中的错误，使它能得出正确结果。
注意：不要更改已给程序的结构，不得增行或删行。
#include
main()
{int i;
int r[11]={0,2,1,4,3,7,6,5,9,8,10};
insertsort(r,10);
for(i=0;i<=9;i++) /*本行有错误*/ 改成 for(i=0;i<9;i++)
printf("%3d",r[i]);
}
insertsort(int r[],int n)
{int i,j;
for(i=1;i<=n-1;i++)
if(r[i]
{r[0]=r[i];
j=i-1;
do{
r[j+1]=r[j];
j--;
}while (r[0]
r[j+1]=r[0];
}
}
2.下列程序的功能是：在数组R[1..n]中顺序查找值为k的元素，成功时返回元素的位置，失败时返回0（r[0]为哨兵）。请在横线处填上适当的内容，并把横线删除，使它能得出正确的结果。
注意：不要更改已给程序的结构，不得增行或删行。
#include
int seqsearch(int r[],int n,int k)
{int i;
r[0]=k;
for(i=n;r[i]!=k; i--);
return i;
}
main()
{int r[11]={-1,3,4,2,6,5,8,7,9,0,1};
int p;
p=seqsearch(r,10,8);
printf("p=%d",p);
}
3.请写一个函数deletetlist，它的功能是： L是一个带头结点的单链表，删除表中第i个结点起的k个结点，同时释放被删结点的空间。
注意：部分源程序已经给出，请勿改动主函数main()和已给出的源程序，仅在deletelist函数中的大括号内填入你编写的若干语句。
