《数据结构》模拟试
题
快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题
一
一、单选题（每题 2 分，共20分）
1. 对一个算法的评价，不包括如下（ ）方面的内容。
A．健壮性和可读性 B．并行性 C．正确性 D．时空复杂度
二、填空题（每题 6 分，共24分）
1. 数据结构是指数据及其相互之间的______________。当结点之间存在M对N（M：N）的联系时，称这种结构为_____________________。
三、运算题（每题6分，共24分）
1. 已知一个65稀疏矩阵如下所示，
试题一参考答案
一、单选题（每题2分，共20分）
1.B 2.A 3.B 4.C 5.D 6.B 7.D 8.A 9.D 10.C
二、填空题（每空1分，共26分）
1. 联系 图（或图结构）
2. 尾 首
3. top==0
4. O（1） O（n）
5. 128 44 108
6. 3 3
7. 有序 n-1
8. 有序序列 后缀
表
关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf
达式（或逆波兰式）
9. 2n n-1 n+1
10. 2i+1 2i+2 (i-1)/2
11. 开放定址法 链接法
12. 快速 归并
三、 运算题（每题6分，共24分）
1. （1） ((1,5,1),(3,2,-1),(4,5,-2),(5,1,5),(6,3,7)) (3分)
（2） 三元组线性表的顺序存储表示如图7示。
2.
如图8所示。
3. DFS：
BFS：
4. 拓朴排序为： 4 3 6 5 7 2 1
四、阅读算法（每题7分，共14分）
1. (1) 判断n是否是素数（或质数）
（2）O（
）
2. 功能为：从初始点vi出发广度优先搜索由邻接表GL所表示的图。
五、算法填空（8 分）
(low+high)/2 high=mid-1 low=mid+1
六、 编写算法（8分）
ElemType DeleFront(LNode * & HL)
{
if (HL==NULL){
cerr<<"空表"<
next;
ElemType temp=p->data;
delete p;
return temp;
}
《数据结构》模拟试题二
一、单选题
1. 栈和队列的共同特点是( )。
A.只允许在端点处插入和删除元素
B.都是先进后出
C.都是先进先出
D.没有共同点
2、填空题
1. 通常从四个方面评价算法的质量：_________、_________、_________和_________。
三、运算题
1. 1. 在如下数组A中链接存储了一个线性表，表头指针为A [0].next，试写出该线性表。
《数据结构》模拟试题二参考答案
一、单选题（每题2分，共20分）
1.A 2.D 3.D 4.C 5.C 6.D 7.D 8.C 9.D 10.A
二、填空题（每空1分，共26分）
1. 正确性 易读性 强壮性 高效率
2. O(n)
3. 9 3 3
4. -1 3 4 X * + 2 Y * 3 / -
5. 2n n-1 n+1
6. e 2e
7. 有向无回路
8. n(n-1)/2 n(n-1)
9. （12，40） （ ） （74） （23,55，63）
10. 增加1
11. O(log2n) O(nlog2n)
12. 归并
三、运算题（每题6分，共24分）
1. 线性表为：（78，50，40，60，34，90）
2. 邻接矩阵：
邻接表如图11所示：
图11
3. 用克鲁斯卡尔算法得到的最小生成树为：
(1,2)3, (4,6)4, (1,3)5, (1,4)8, (2,5)10, (4,7)20
4. 见图12
图12
四、阅读算法（每题7分，共14分）
1. 1. （1）查询链表的尾结点
（2）将第一个结点链接到链表的尾部，作为新的尾结点
（3）返回的线性表为（a2,a3,…,an,a1）
2. 递归地后序遍历链式存储的二叉树。
五、算法填空（每空2分，共8 分）
true BST->left BST->right
六、编写算法（8分）
int CountX(LNode* HL,ElemType x)
{ int i=0; LNode* p=HL;//i为计数器
while(p!=NULL)
{ if (P->data==x) i++;
p=p->next;
}//while, 出循环时i中的值即为x结点个数
return i;
}//CountX
《数据结构》模拟试题三
一、单选题
1、在一个长度为n的顺序线性表中顺序查找值为x的元素时，查找成功时的平均查找长度（即x与元素的平均比较次数，假定查找每个元素的概率都相等）为 ( )。
A n B n/2 C (n+1)/2 D (n-1)/2
二、 填空题
1、数据的逻辑结构被分为__________、 ___________ 、________和________四种。
三、 运算题
1、已知一组记录的排序码为（46，79，56，38，40，80, 95，24），写出对其进行快速排序的每一次划分结果。
《数据结构》模拟试题三（答案）
一、单选题
题 号
1
2
3
4
答 案
C
D
A
B
二、填空题
1： 集合、线性、树、图；
2： 数据描述、操作声名；
3： （38，56，25，60，42，74）；
4： HL→next =NULL； HL=HL→next；
5： 前一个位置； n-1；
6： S.stack [S.top]; HS→data;
7： 5 31
8： 边结点、邻接点域、权域、链域；
9： 索引值域、开始位置域；
10： 10、3、3、B、I和J；
11： O（log2n）、O(nlog2n);
12： m 、 m - 1
3、运算题
1、
划分次序
划分结果
第一次
[38 24 40] 46 [56 80 95 79]
第二次
24 [38 40] 46 [56 80 95 79]
第三次
24 38 40 46 [56 80 95 79]
第四次
24 38 40 46 56 [80 95 79]
第五次
24 38 40 46 56 79 [80 95]
第六次
24 38 40 46 56 79 80 95
2、
0 1 2 3 4 5 6 7 8 9 10 11 12
78
15
03
57
45
20
31
23
36
12
查找成功的平均查找长度：ASL SUCC=14/10= 1.4
3、此二叉树的后序遍历结果是：EDCBIHJGFA
4、
图
深度优先序列
广度优先序列
邻接矩阵表示时
0，1，2，8，3，4，5，6，7，9
0，1，4，2，7，3，8，6，5，9
邻接表表示时
0，4，3，8，9，5，6，7，1，2
0，4，1，3，7，2，8，6，9，5
四、阅读算法，回答问题（每小题8分，共16分）
1、 1、 该算法的输入结果是：34 91 30 45 63 78
2、 2、 该算法的功能是：交换二叉树的左右子树的递归算法。
五、算法填空，在画有横线的地方填写合适的内容（10分）
1、1是：（low + high）/2;
2是： Binsch(A,low,mid–1,K);
3是： Binsch(A,mid+1,high,K);
4是： -1；
六、编写算法（10分）
根据编程情况，酌情给分。
{
Lnode *P=HL;
HL=NULL;
While (p!=null)
{
Lnode*q=p;
P=p→next;
q→next=HL;
HL=q;
}
}
《数据结构》模拟试题四
1、项选择题
1．算法指的是（ ）
A．计算机程序 B．解决问题的计算方法
C．排序算法 D．解决问题的有限运算序列
二、填空题
16．数据的逻辑结构是从逻辑关系上描述数据，它与数据的 无关，是独立于计算机的。
3、解答题
26．画出下列广义表的共享结构图形表示
P=（（（z）,(x,y)）,((x,y),x),(z)）
《数据结构》模拟试题四参考答案
一、 单项选择题（本大题共15小题，每小题2分，共30分）
1．D ２．Ｂ ３．Ｃ ４．Ｂ ５．Ｄ ６．Ａ ７．Ｃ ８，Ｄ ９，Ａ 10．Ｃ 11．Ｄ 12．Ｃ 13．Ｄ 14．Ｃ 15．Ｂ
二、填空题（本大题共10小题，每小题2分，共20分）
16．存储（或存储结构） 17.p－＞next－＞next 18．进栈和退栈 19．12 20．a4,8 21．384 22．abefcdg
23．快速排序、堆排序、希尔排序
24．２ 25.多关键字
三、解答题（本大题共4小题，每小题5分，共20分）
26．
图1 图2
27．
28．该图的图形为：
深度优先遍历序列为：abdce
广度优先遍历序列为：abedc
29．（１）对关键字35、20、33和48进行查找的比较次数为３、２、１、１；
（２）平均查找长度
四、算法阅读题（本大题共4小题，每小题5分，共20分）
30． ①S1=S1－>next
②s2=s2－>next
③s2(或s2!=NULL或s2&&!s1)
④s1(或s1!=NULL或s1&&!s2)
⑤return 0
31.（1）查询链表的尾结点
（2）将第一个结点链接到链表的尾部，作为新的尾结点
（3）返回的线性表为（a2,a3,…,an,a1）
32. ①(i＋1)%2(或1－i)
②Q－>rear[i]
③(Q－>rear[i]＋)%Maxsize
33.(1)Leafhead
F
H
G
D
∧
（2）中序遍历二叉树，按遍历序列中叶子结点数据域的值构建一个以Leafhead为头指针的逆序单链表（或按二叉树中叶子结点数据自右至左链接成一个链表）。
五、算法
设计
领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计
题（本题共10分）
34．（1）该函数的功能是：调整整数数组a[]中的元素并返回分界值i，使所有＜x的元素均落在a[1..i]上，使所有≥x的元素均落在a[i＋1..h]上。
（2）int f(int b[],int n) 或 int f(int b[],int n)
{ {
int p,q； int p,q；
p=arrange(b,0,n－1,0)； p=arrange(b,0,n－1,1)；
q= arrange(b,p+1,n－1,1)； q= arrange(b,0,p,0)；
return q－p； return p－q；
《数据结构》模拟试题五
一、选择题（20分）
1．组成数据的基本单位是（ ）。
(A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量
二、填空题(30分)
1. 设顺序循环队列Q[0：m-1]的队头指针和队尾指针分别为F和R，其中队头指针F指向当前队头元素的前一个位置，队尾指针R指向当前队尾元素所在的位置，则出队列的语句为F =____________;。
三、应用题（30分）
1．设完全二叉树的顺序存储结构中存储数据ABCDE，要求给出该二叉树的链式存储结构并给出该二叉树的前序、中序和后序遍历序列。
《数据结构》模拟试题五参考答案
一、选择题
1.C 2.C 3.D 4.C 5.A
6.C 7.C 8.B 9.B 10.B
二、填空题
1. (F+1) % m
2. O(n)，O(n)
3. 2n，n+1
4. s->next=p->next; s->next=s
5. n, 2e
6. m=2e
7. CBA
8. 4，16
9. i-j+1，0
10. n-1
三、应用题
1. 链式存储结构略，前序ABDEC，中序DBEAC，后序DEBCA。
2. 哈夫曼树略，WPL=78
3. (18,5,16,19,21,23)，(5，16，21，19，18，23)
4. 线性探测：
链地址法：
5. 深度：125364，广度：123456，最小生成树T的边集为E={(1，4)，(1，3)，(3，5)，(5，6)，(5,6)}
四、算法设计题
1. 设计判断单链表中结点是否关于中心对称算法。
typedef struct {int s[100]; int top;} sqstack;
int lklistsymmetry(lklist *head)
{
sqstack stack; stack.top= -1; lklist *p;
for(p=head;p!=0;p=p->next) {stack.top++; stack.s[stack.top]=p->data;}
for(p=head;p!=0;p=p->next) if (p->data==stack.s[stack.top]) stack.top=stack.top-1; else return(0);
return(1);
}
2. 设计在链式存储结构上建立一棵二叉树的算法。
typedef char datatype;
typedef struct node {datatype data; struct node *lchild,*rchild;} bitree;
void createbitree(bitree *&bt)
{
char ch; scanf("%c",&ch);
if(ch=='#') {bt=0; return;}
bt=(bitree*)malloc(sizeof(bitree)); bt->data=ch;
createbitree(bt->lchild); createbitree(bt->rchild);
}
3. 设计判断一棵二叉树是否是二叉排序树的算法。
int minnum=-32768,flag=1;
typedef struct node{int key; struct node *lchild,*rchild;}bitree;
void inorder(bitree *bt)
{
if (bt!=0)
{inorder(bt->lchild); if(minnum>bt->key)flag=0; minnum=bt->key; inorder(bt->rchild);}
}
《数据结构》模拟试题六
一、选择题(24分)
1．下面关于线性表的叙述错误的是（ ）。
(A) 线性表采用顺序存储必须占用一片连续的存储空间
(B) 线性表采用链式存储不必占用一片连续的存储空间
(C) 线性表采用链式存储便于插入和删除操作的实现
(D) 线性表采用顺序存储便于插入和删除操作的实现
二、填空题(24分)
1. 为了能有效地应用HASH查找技术，必须解决的两个问题是____________________和__________________________。
三、应用题(36分)
1． 设一组初始记录关键字序列为(45，80，48，40，22，78)，则分别给出第4趟简单选择排序和第4趟直接插入排序后的结果。
《数据结构》模拟试题六参考答案
一、选择题
1.D 2.B 3.C 4.A 5.A 6.C 7.B 8.C
二、填空题
1. 构造一个好的HASH函数，确定解决冲突的方法
2. stack.top++，stack.s[stack.top]=x
3. 有序
4. O(n2)，O(nlog2n)
5. N0-1，2N0+N1
6. d/2
7. (31，38，54，56，75，80，55，63)
8. (1，3，4，2)，(1，3，2，4)
三、应用题
1. (22，40，45，48，80，78)，(40，45，48，80，22，78)
2. q->llink=p; q->rlink=p->rlink; p->rlink->llink=q; p->rlink=q;
3. 2,ASL=91*1+2*2+3*4+4*2)=25/9
4. 树的链式存储结构略，二叉树略
5. E={(1，3)，(1，2)，(3，5)，(5，6)，(6，4)}
6. 略
四、算法设计题
1. 设有一组初始记录关键字序列（K1，K2，…，Kn），要求设计一个算法能够在O(n)的时间复杂度内将线性表划分成两部分，其中左半部分的每个关键字均小于Ki，右半部分的每个关键字均大于等于Ki。
void quickpass(int r[], int s, int t)
{
int i=s, j=t, x=r[s];
while(ix) j=j-1; if (inext)
{ for(q=hb;q!=0;q=q->next) if (q->data==p->data) break;
if(q!=0){ t=(lklist *)malloc(sizeof(lklist)); t->data=p->data;t->next=hc; hc=t;}
}
}
《数据结构》模拟试题七
一、选择题(30分)
1．设某数据结构的二元组形式表示为A=(D，R)，D={01，02，03，04，05，06，07，08，09}，R={r}，r={<01，02>，<01，03>，<01，04>，<02，05>，<02，06>，<03，07>，<03，08>，<03，09>}，则数据结构A是（ ）。
(A) 线性结构 (B) 树型结构 (C) 物理结构 (D) 图型结构
二、填空殖(48分，其中最后两小题各6分)
1. 数据的物理结构主要包括_____________和______________两种情况。
三、算法设计题(22分)
1． 设计在单链表中删除值相同的多余结点的算法。
《数据结构》模拟试题七参考答案
一、选择题
1.B 2.B 3.A 4.A 5.A
6.B 7.D 8.C 9.B 10.D
第3小题分析：首先用指针变量q指向结点A的后继结点B，然后将结点B的值复制到结点A中，最后删除结点B。
第9小题分析：9快速排序、归并排序和插入排序必须等到整个排序结束后才能够求出最小的10个数，而堆排序只需要在初始堆的基础上再进行10次筛选即可，每次筛选的时间复杂度为O(log2n)。
二、填空题
1. 顺序存储结构、链式存储结构
2. 9，501
3. 5
4. 出度，入度
5. 0
6. e=d
7. 中序
8. 7
9. O(1)
10. i/2，2i+1
11. (5，16，71，23，72，94，73)
12. (1，4，3，2)
13. j+1，hashtable[j].key==k
14. return(t)，t=t->rchild
第8小题分析：二分查找的过程可以用一棵二叉树来描述，该二叉树称为二叉判定树。在有序表上进行二分查找时的查找长度不超过二叉判定树的高度1+log2n。
三、算法设计题
1. 设计在单链表中删除值相同的多余结点的算法。
typedef int datatype;
typedef struct node {datatype data; struct node *next;}lklist;
void delredundant(lklist *&head)
{
lklist *p,*q,*s;
for(p=head;p!=0;p=p->next)
{
for(q=p->next,s=q;q!=0; )
if (q->data==p->data) {s->next=q->next; free(q);q=s->next;}
else {s=q,q=q->next;}
}
}
2. 设计一个求结点x在二叉树中的双亲结点算法。
typedef struct node {datatype data; struct node *lchild,*rchild;} bitree;
bitree *q[20]; int r=0,f=0,flag=0;
void preorder(bitree *bt, char x)
{
if (bt!=0 && flag==0)
if (bt->data==x) { flag=1; return;}
else {r=(r+1)% 20; q[r]=bt; preorder(bt->lchild,x); preorder(bt->rchild,x); }
}
void parent(bitree *bt,char x)
{
int i;
preorder(bt,x);
for(i=f+1; i<=r; i++) if (q[i]->lchild->data==x || q[i]->rchild->data) break;
if (flag==0) printf("not found x\n");
else if (i<=r) printf("%c",bt->data); else printf("not parent");
}
《数据结构》模拟试题八
一、选择题(30分)
1．设一维数组中有n个数组元素，则读取第i个数组元素的平均时间复杂度为（ ）。
(A) O(n) (B) O(nlog2n) (C) O(1) (D) O(n2)
二、填空题(42分)
1． 设有n个无序的记录关键字，则直接插入排序的时间复杂度为________，快速排序的平均时间复杂度为_________。
三、算法设计题(28分)
1． 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。
《数据结构》模拟试题八参考答案
一、选择题
1．C 2．D 3．D 4．B 5．C
6．A 7．B 8．A 9．C 10．A
二、填空题
1. O(n2)，O(nlog2n)
2. p>llink->rlink=p->rlink; p->rlink->llink=p->rlink
3. 3
4. 2k-1
5. n/2
6. 50，51
7. m-1，(R-F+M)%M
8. n+1-i，n-i
9. (19，18，16，20，30，22)
10. (16，18，19，20，32，22)
11. A[i][j]=1
12. 等于
13. BDCA
14. hashtable[i]=0，hashtable[k]=s
三、算法设计题
1. 设单链表中有仅三类字符的数据元素(大写字母、数字和其它字符)，要求利用原单链表中结点空间设计出三个单链表的算法，使每个单链表只包含同类字符。
typedef char datatype;
typedef struct node {datatype data; struct node *next;}lklist;
void split(lklist *head,lklist *&ha,lklist *&hb,lklist *&hc)
{
lklist *p; ha=0,hb=0,hc=0;
for(p=head;p!=0;p=head)
{
head=p->next; p->next=0;
if (p->data>='A' && p->data<='Z') {p->next=ha; ha=p;}
else if (p->data>='0' && p->data<='9') {p->next=hb; hb=p;} else {p->next=hc; hc=p;}
}
}
2. 设计在链式存储结构上交换二叉树中所有结点左右子树的算法。
typedef struct node {int data; struct node *lchild,*rchild;} bitree;
void swapbitree(bitree *bt)
{
bitree *p;
if(bt==0) return;
swapbitree(bt->lchild); swapbitree(bt->rchild);
p=bt->lchild; bt->lchild=bt->rchild; bt->rchild=p;
}
3. 在链式存储结构上建立一棵二叉排序树。
#define n 10
typedef struct node{int key; struct node *lchild,*rchild;}bitree;
void bstinsert(bitree *&bt,int key)
{
if (bt==0){bt=(bitree *)malloc(sizeof(bitree)); bt->key=key;bt->lchild=bt->rchild=0;}
else if (bt->key>key) bstinsert(bt->lchild,key); else bstinsert(bt->rchild,key);
}
void createbsttree(bitree *&bt)
{
int i;
for(i=1;i<=n;i++) bstinsert(bt,random(100));
}
《数据结构》模拟试题九
一、选择题(30分)
1．数据的最小单位是（ ）。
(A) 数据项 (B) 数据类型 (C) 数据元素 (D) 数据变量
二、填空题(共30分)
1. 设有一个顺序共享栈S[0：n-1]，其中第一个栈项指针top1的初值为-1，第二个栈顶指针top2的初值为n，则判断共享栈满的条件是____________________。
三、应用题(24分)
1. 设某棵二叉树的中序遍历序列为DBEAC，前序遍历序列为ABDEC，要求给出该二叉树的的后序遍历序列。
《数据结构》模拟试题九参考答案
一、选择题
1．A 2．B 3．A 4．A 5．D
6．B 7．B 8．B 9．C 10．C
二、填空题
1. top1+1=top2
2. 可以随机访问到任一个顶点的简单链表
3. i(i+1)/2+j-1
4. FILO，FIFO
浙公网安备 33021202002483