淮阴工学院数据结构期中试题及参考答案.doc
- 文档编号:14733975
- 上传时间:2023-06-26
- 格式:DOC
- 页数:5
- 大小:1.40MB
淮阴工学院数据结构期中试题及参考答案.doc
《淮阴工学院数据结构期中试题及参考答案.doc》由会员分享,可在线阅读,更多相关《淮阴工学院数据结构期中试题及参考答案.doc(5页珍藏版)》请在冰点文库上搜索。
淮阴工学院
题号
一
二
三
四
五
六
七
八
九
总分
得分
一、单项选择题(本大题共12小题,每小题2分,共24分)在每小题列出的四个备选项中只有一个是符合题目要求的,请将其代码填写在题后的括号内。
选错、多选或未选均无分。
1.按值可分解,数据类型通常可分为两类,他们是 【C】
A.静态类型和动态类型 B.原子类型和表类型
C.原子类型和结构类型 D.数据类型和指针类型
2.对于三个函数f(n)=2008+8+96000,g(n)=8+8n+2008和h(n)=8888nlogn+3n2,下列陈述中不成立的是 【C】
A.f(n)是O(g(n)) B.g(n)是O(f(n))
C.h(n)是O(n) D.h(n)是O()
3.指针p、q和r依次指向某循环链表中三个相邻的节点,交换节点*q和节点*r在表中的次序的程序段是【A】
A.p->next=r;q->next=r->next;r->next=q;
B.p->next=r;r->next=q;q->next=r->next;
C.r->next=q;q->next=r->next;p->next=r;
D.r->next=q; p->next=r;q->next=r->next;
4.若进栈次序为a,b,c,且进栈和出站可以穿插进行,则可能出现的含个元素的出站序列个数是【B】
A.3 B.5 C.6 D.7
5.假设以数组A[n]存放循环队列的元素,其头指针front指向队头元素的前一个位置、为指针rear指向队尾元素所在的存储位置,则在少用一个元素空间的前提下,队列满的判定条件为【D】
A.rear==front B.(front+1)%n==rear
C.rear+1==front D.(rear+1)%n==front
6.串的操作函数str定义为:
intstr(char*s){
char*p=s;
while(*p!
=’\0’) p++;
returnp-s;
}
则str(“abcde”)的返回值是 【C】
A.3 B.4 C.5 D.6
7.二维数组A[10][6]采用行优先的存储方法,若每个元素占4个存储单元,已知元素A[3][4]的存储地址为1000,则元素A[4][3]的存储地址为 【A】
A.1020 B.1024 C.1036 D.1240
8.对广义表L=(a,())执行操作tail(L)的结果是 【B】
A.() B.(()) C.a D.(a)
9.已知二叉树的中序序列和后序序列均为ABCDEF,则该二叉树的先序序列为 【A】
A.FEDCBA B.ABCDEF
C.FDECBA D.FBDCEA
10.已知森林F={,,,,},各棵树(i=1,2,3,4,5)中所含节点的个数分别为7,3,5,1,2,则与F对应的二叉树的右子树种的节点个数为 【D】
A.2 B.3 C.8 D.11
11.若非连通无向图G含有21条边,则G的顶点个数至少为 【B】
题12图
A.7 B.8 C.21 D.22
12.如图所示的有向图的拓扑序列是 【B】
A.c,d,b,a,e
B.c,a,d,b,e
c
C.c,d,e,a,b
D.c,a,b,d,e
二、填空题(本大题7小题,每题2分,若有两个空,每个空格1分,共14分)请在每个空格中填上正确答案。
错填、不填均无分。
1.数据的链式存储结构的特点是借助指示元素存储地址的指针表示数据元素之间的逻辑关系。
2.如果需要对线性表频繁进行插入或 删除 操作,则不宜采用顺序存储结构。
top1 top2
0n-1
栈1 栈2
3.如图所示,可以利用一个向量空间同时实现两个类型相同的栈。
其中栈1为空的条件是top1=0,栈2为空的条件是top2=n+1,则“栈满”的判定条件是 top1=top2+1 。
4.静态存储分配的顺序串在进行插入、置换和 连接 等操作时可能发生越界。
5.广义表L=(a,(b,()))的深度为 3 。
6.任意一棵完全二叉树中,度为1的节点数最多为 1 。
7.求最小生成树的克鲁斯卡尔算法耗用的时间与图中 边 的数目正相关。
三、解答题(本大题共4小题,每小题8分,共24分)
5
∧
4
3
1.如图所示,在nn矩阵A中,所有下标值满足关系式i+j (1)设n=10,元素存储在sa[p],写出下标p的值; p=8 (2)设元素存储在sa[k]中,写出有i,j和n计算k的一般公式。 题3-1图 k=i(i-1)/2+j+i-n-1 2.由字符集{s,t,a,e,i}及其在电文中出现的频度构建的哈夫曼树如图所示。 已知某段电文的哈夫曼编码为111000010100,请根据该哈夫曼树进行译码,写出原来的电文。 i s e a t 1 0 1 0 1 0 1 0 eatst 题3-2图 3.已知无向图G的邻接表如图所示, (1)画出该无向图; (2)画出该图的广度优先生成森林。 2 2 ∧ 1 2 ∧ 5 ∧ 4 ∧ 8 ∧ 8 ∧ 7 ∧ 3 ∧ 1 0 0 0 2 2 7 6 6 题3-3图 0 1 2 3 4 5 6 7 8 A B C D E F G H I 四、算法阅读题(本大题共3小题,每题8分,共24分) 1.阅读下列算法,并回答问题: (1)无向图G如图所示,写出算法f30(&G)的返回值; k=3 B C D A G F H (2)简述算法f30的功能。 求图中连通分量的数目 #defineMaxNum20 int visited[MaxNum]; voidDFS(Graph*g, int i); /*从顶点出发进行深度优先搜索,访问顶点时置visited[j]为1*/ intf30(Graph*g) { Inti,k; for(i=0;I visited[i]=0; for(i=k=0;I if(visited[i]==0) { K++; DFS(g,i); } return k; } 2.假设学生成绩按学号增序从年初在带头结点的单链表中,类型定义如下: typedef struct Node{ intid;/*学号*/ intscore; /*成绩*/ struct Node *next; }LNode, *LinkList; id score next 阅读算法f31,并回答问题; (1)设节点结构为,成绩链表A和B如图所示,画出执行算法f31(A,B)后节点A所指的链表; 1 70 5 56 4 48 3 90 2 40 A 5 75 4 65 2 38 B 题31图 (2)减速算法f31的功能。 Voidf31(LinkListA,LinkListB) { LinkList p,q; p=A->next; q=B->next; while(p&&q) { if(p->id p=p->next; elseif(p->if>q->id) q=q–>next; else { if(p->score<60) if(q->score<60) p->score=q->score; else p->score=60; p=p->next; q=q->next; } } } 3.阅读下列算法,并回答问题: (1)设串s=“OneWorldOneDream”,t=“One”,pos是一维整型数组,写出算法f32(s,t,pos)执行之后得到的返回值和pos中的值; (2)简述算法f32的功能。 intstr(char*s); /*返回串s的长度*/ intindex(char*st,char*t); /*若串t在串st中出现,则返回在串st中首次出现的下标值,否则返回-1*/ intf32(char*s,char*t,intpos[]) { inti,j,k,ls,lt; ls=strlen(s); lt=strlen(t); if(ls==0||lt==0) return-1; k=0; i=0; do{ j=index(s+I,t); if(j>=0) { Pos[k++]=i+j; I+=j+lt; } }while(i+lt<=ls&&j>=0); Returnk; } 五、算法设计题(本题14分) 34.假设线性表采用顺序存储结构,其类型定义如下: #defineListSize100 typedefstruct{ intdata[ListSize]; intlength; }SeqList,*Table; 编写算法,将顺序表L中所有值为奇数的元素调整到表的前端。 5
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 淮阴 工学院 数据结构 期中 试题 参考答案